Optimal Community Recovery by Spectrally Initialized Variational EM in General Stochastic Block Models
Abstract
We prove a Chernoff-exponent guarantee for the output of spectrally initialized batch variational EM after a prescribed iteration budget, without assuming global maximization of its variational objective. The iteration repeatedly estimates the entire block probability matrix and community proportions from the same sparse graph. We consider a fixed number of communities with proportions bounded away from zero and fixed, positive, distinct connectivity profiles; neither assortativity nor full rank is required. The algorithm uses simultaneous softmax updates without sample splitting or posterior thresholding. Its analysis must control the feedback between estimated parameters, soft labels and reused edges at an exponentially small risk scale. We establish a uniform one-step bound over data-dependent soft assignments whose random remainder has exponentially small expectation. Combined with an exponentially reliable regularized spectral initializer, this yields an unconditional expected misclassification rate bounded by exp{−(1−o(1))Jn} throughout the sparse, diverging-degree regime, where Jn is the minimum nodewise Chernoff information. Matching lower bounds establish first-order logarithmic minimax optimality on local parameter spaces allowing unknown connectivity and varying community counts. The algorithm also attains the sharp first-order exact-recovery threshold. Numerical experiments illustrate refinement gains and sensitivity to initialization and imbalance.
Related
- A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model
- Dynamics of Stochastic Hamiltonian systems I - Wong-Zakai Variational integrators
- Stochastic Linesearch Methods for Stochastic Variational Inequality Problems: Parameter-Free Schemes and Non-Monotone Variants
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Stochastic Optimal Control of Decoupled Reflected FBSDEs: A Variational Approach with Residual Reflection Terms
BibTeX
@misc{liu2026optimal,
title = {{Optimal Community Recovery by Spectrally Initialized Variational EM in General Stochastic Block Models}},
author = {Binghui Liu and Jiangzhou Wang and Man-Chung Yue},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04376},
eprint = {2610.04376},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04376},
}
RIS
TY - UNPB
TI - Optimal Community Recovery by Spectrally Initialized Variational EM in General Stochastic Block Models
AU - Binghui Liu
AU - Jiangzhou Wang
AU - Man-Chung Yue
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.04376
UR - https://arxiv.org/abs/2610.04376
AB - We prove a Chernoff-exponent guarantee for the output of spectrally initialized batch variational EM after a prescribed iteration budget, without assuming global maximization of its variational objective. The iteration repeatedly estimates the entire block probability matrix and community proportions from the same sparse graph. We consider a fixed number of communities with proportions bounded away from zero and fixed, positive, distinct connectivity profiles; neither assortativity nor full rank is required. The algorithm uses simultaneous softmax updates without sample splitting or posterior thresholding. Its analysis must control the feedback between estimated parameters, soft labels and reused edges at an exponentially small risk scale. We establish a uniform one-step bound over data-dependent soft assignments whose random remainder has exponentially small expectation. Combined with an exponentially reliable regularized spectral initializer, this yields an unconditional expected misclassification rate bounded by exp{−(1−o(1))J_n} throughout the sparse, diverging-degree regime, where J_n is the minimum nodewise Chernoff information. Matching lower bounds establish first-order logarithmic minimax optimality on local parameter spaces allowing unknown connectivity and varying community counts. The algorithm also attains the sharp first-order exact-recovery threshold. Numerical experiments illustrate refinement gains and sensitivity to initialization and imbalance.
ER -