Statistical inference on graphs
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.
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 |