Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral

Abstract

We establish asymptotic normality results for estimation of the block probability matrix $\mathbf{B}$ in stochastic blockmodel graphs using spectral embedding when the average degrees grows at the rate of $\omega (\sqrt{n})$ in $n$, the number of vertices. As a corollary, we show that when $\mathbf{B}$ is of full-rank, estimates of $\mathbf{B}$ obtained from spectral embedding are asymptotically efficient. When $\mathbf{B}$ is singular the estimates obtained from spectral embedding can have smaller mean square error than those obtained from maximizing the log-likelihood under no rank assumption, and furthermore, can be almost as efficient as the true MLE that assume known $\mathrm{rk}(\mathbf{B})$. Our results indicate, in the context of stochastic blockmodel graphs, that spectral embedding is not just computationally tractable, but that the resulting estimates are also admissible, even when compared to the purportedly optimal but computationally intractable maximum likelihood estimation under no rank assumption.

34 pages, 2 figures

References in corpus (10)

• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Stochastic blockmodels and community structure in networks
• Matrix estimation by Universal Singular Value Thresholding
• Stochastic blockmodels with growing number of classes
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Rate-optimal graphon estimation
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• A nonparametric two-sample hypothesis testing problem for random dot product graphs

Cited by in corpus (5)

• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications