Course description
The course provides an introduction to and overview of current research in random graph inference, with a particular focus on spectral methods and their applications to inference for independent-edge random graphs. Topics include concentration inequalities; analysis of matrix perturbations; spectral decompositions of graph adjacency and Laplacian matrices; consistent estimation of latent variables associated to vertices; clustering, community detection, and classification in networks; and multi-sample hypothesis testing for graphs. Emphasis will be on a framework for establishing classical properties—consistency, normality, and efficiency—for estimators of graph parameters. Students will read papers in the literature and are expected to participate actively in class. Recommended prerequisites EN.553.792 and EN.553.630.
Instructors and TA
- Avanti Athreya. Email: dathrey1 dot jhu dot edu
- Office Hours: Monday 3pm–5pm in Whitehead Hall 306D
- Minh Tang. Email: mtang10 dot jhu dot edu
- Office Hours: Friday 2pm–4pm in Whitehead Hall 306E
- Joshua Cape. Email: jcape1 dot jhu dot edu
- Office Hours: TBD in Whitehead 212
Syllabus and tentative schedule
| Date | Topics | Readings |
|---|---|---|
| 08/30 | Introduction and overview | |
| 08/31 | Random graphs models: Erdos-Renyi, stochastic blockmodels, preferential attachments | Bollobas et al., Hoff et al., Chung and Lu |
| 09/05 | Random dot product graphs, adjacency and Laplacian spectral embedding | Athreya et al. |
| 09/07 | Matrix concentration inequalities | Oliviera, Tropp, Lu and Peng |
| 09/10 | Matrix concentration inequalities (day 2) | Oliviera, Tropp, Lu and Peng |
| 09/12 | Matrix concentration inequalities (day 3) | Oliviera, Tropp, Lu and Peng |
| 09/14 | Subspace perturbation | Yu et al., Rohe et al. |
| 09/17 | Subspace perturbation (day 2) | Yu et al., Rohe et al. |
| 09/19 | Subspace perturbation (day 3) | Cai and Zhang |
| 09/21 | Clustering and spectral clustering | von Luxburg |
| 09/24 | Clustering and spectral clustering (day 2) | Belkin and Niyogi, Coifman and Lafon |
| 09/26 | Clustering and spectral clustering (day 3) | von Luxburg et al. |
| 09/28 | Estimation and consistency in stochastic blockmodel and random dot product graphs | Sussman et al., Sussman et al., Rohe et al. |
| 10/01 | Estimation and consistency in stochastic blockmodel and random dot product graphs (day 2) | Lyzinski et al. |
| 10/03 | Estimation and consistency in stochastic blockmodel and random dot product graphs (day 3) | Lyzinski et al., Cape et al. |
| 10/05 | A central limit theorem for scaled eigenvectors of random dot product graphs | Athreya et al. |
| 10/08 | Limit theorems for eigenvectors of the normalized Laplacian for random graphs | Tang and Priebe, Chernoff, Sarkar and Bickel |
| 10/10 | Limit theorems for eigenvectors of the normalized Laplacian for random graphs (day 2) | Tang and Priebe, Chernoff, Sarkar and Bickel |
| 10/12 | Limit theorems for eigenvectors of the normalized Laplacian for random graphs (day 3) | Tang and Priebe, Chernoff, Sarkar and Bickel |
| 10/15 | Asymptotically efficient estimators for stochastic blockmodels | Bickel et al., Tang et al. |
| 10/17 | Asymptotically efficient estimators for stochastic blockmodels (day 2) | Bickel et al., Tang et al. |
| 10/19 | Fall break | Candide, ou l’Optimisme |
| 10/22 | Asymptotically efficient estimators for stochastic blockmodels (day 3) | Bickel et al., Tang et al. |
| 10/24 | Two-sample semiparametric testing for random graphs | Tang et al. |
| 10/26 | Two-sample semiparametric testing for random graphs (day 2) | Tang et al. |
| 10/29 | Two-sample semiparametric testing for random graphs (day 3) | Levin et al. |
| 10/31 | Two-sample nonparametric testing for random graphs | Tang et al., Gretton et al. |
| 11/02 | Two-sample nonparametric testing for random graphs (day 2) | Tang et al., Gretton et al. |
| 11/05 | Universal singula value thresholding | Chatterjee, Xu |
| 11/07 | Universal singula value thresholding (day 2) | Chatterjee, Xu |
| 11/09 | Universal singula value thresholding (day 3) | Chatterjee, Xu |
| 11/12 | Breather day | The Corrs, Richie Havens |
| 11/14 | Exponential random graphs model | Shalizi and Rinaldo |
| 11/16 | Goodness-of-fit test in stochastic blockmodels | Lei, Wang and Bickel |
| 11/26 | Stochastic blockmodels and limit of detectability | Mossel et al., Abbe et al., Hajek et al., Abbe |
| 11/28 | Stochastic blockmodels and limit of detectability (day 2) | Mossel et al., Abbe et al., Hajek et al., Abbe |
| 11/30 | Stochastic blockmodels and limit of detectability (day 3) | Mossel et al., Abbe et al., Hajek et al., Abbe |
| 12/03 | All Caratheodory, all the time | Staying alive |
| 12/05 | Dynkin-Dynkin | Hey |
| 12/07 | Proof of the Riemann hypothesis using elementary linear algebra | Moskau |