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

arXiv: https://arxiv.org/abs/1710.10936 · HTML: https://mlsanity.com/paper/1710.10936/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2017.

## Built on by (most cited first, 9 of 9)

- [Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Model](https://mlsanity.com/paper/2209.13762/) (2022)
- [Clustered Graph Matching for Label Recovery and Graph Classification](https://mlsanity.com/paper/2205.03486/) (2022)
- [Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms](https://mlsanity.com/paper/2202.04061/) (2022)
- [Perfect Spectral Clustering with Discrete Covariates](https://mlsanity.com/paper/2205.08047/) (2022)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [Directed Link Prediction using GNN with Local and Global Feature Fusion](https://mlsanity.com/paper/2506.20235/) (2025)
- [Simultaneous estimation of connectivity and dimensionality in samples of networks](https://mlsanity.com/paper/2508.12483/) (2025)
- [Random Dot Product Graphs as Dynamical Systems: Limitations and Opportunities](https://mlsanity.com/paper/2603.05703/) (2026)
- [Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding](https://mlsanity.com/paper/2603.11965/) (2026)

## Abstract (arXiv)

We establish asymptotic normality results for estimation of the block probability matrix B in stochastic blockmodel graphs using spectral embedding when the average degrees grows at the rate of ω(√n) in n, the number of vertices. As a corollary, we show that when B is of full-rank, estimates of B obtained from spectral embedding are asymptotically efficient. When 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 rk(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.