Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
Abstract
We study community recovery in the sparse symmetric stochastic block model with q communities, average degree d and signal strength λ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold dλ2=1 and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-D polynomial rules is the trivial risk times 1−CorrD2. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for q≥ 5 there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability 1−o(1). Second, the Fisher information about λ carried by cycle counts is a series with terms of order k(dλ2)k, convergent exactly when dλ2<1; below the threshold the relative error of every unbiased cycle-based estimator of λk stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by |λ|√d per iteration, and one EM step taken there leaves λ unchanged. A signal-to-noise computation recovers the condition dλ1/χ>1 of Chin et al. for q=nχ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to 3× 105 vertices confirm the threshold for q=2, the hard window for q=5, and the many-community scaling.
Related
- Information-Computation Inversion in Pseudo-Marginal MCMC
- An information-geometric formulation of distributed computation
- First-Order Optimization under Uniform Nondegeneracy: Geometry, Computation, and Information
- Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks
- Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
BibTeX
@misc{ghandali2026slow,
title = {{Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models}},
author = {Soroor Ghandali},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08872},
eprint = {2610.08872},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08872},
}
RIS
TY - UNPB
TI - Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
AU - Soroor Ghandali
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08872
UR - https://arxiv.org/abs/2610.08872
AB - We study community recovery in the sparse symmetric stochastic block model with q communities, average degree d and signal strength λ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold dλ^2=1 and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-D polynomial rules is the trivial risk times 1−Corr_D^2. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for q≥ 5 there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability 1−o(1). Second, the Fisher information about λ carried by cycle counts is a series with terms of order k(dλ^2)^k, convergent exactly when dλ^2<1; below the threshold the relative error of every unbiased cycle-based estimator of λ^k stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by |λ|√d per iteration, and one EM step taken there leaves λ unchanged. A signal-to-noise computation recovers the condition dλ^1/χ>1 of Chin et al. for q=n^χ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to 3× 10^5 vertices confirm the threshold for q=2, the hard window for q=5, and the many-community scaling.
ER -