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 $\lambda$ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold $d\lambda^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-\mathrm{Corr}_D^2$. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for $q\ge 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 $\lambda$ carried by cycle counts is a series with terms of order $k(d\lambda^2)^k$, convergent exactly when $d\lambda^2<1$; below the threshold the relative error of every unbiased cycle-based estimator of $\lambda^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 $|\lambda|\sqrt{d}$ per iteration, and one EM step taken there leaves $\lambda$ unchanged. A signal-to-noise computation recovers the condition $d\lambda^{1/\chi}>1$ of Chin et al. for $q=n^\chi$ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to $3\times 10^5$ vertices confirm the threshold for $q=2$, the hard window for $q=5$, and the many-community scaling.

Information Theory (cs.IT); Machine Learning (cs.LG); Probability (math.PR); Statistics Theory (math.ST); Machine Learning (stat.ML)

arXiv:2610.08872 [cs.IT]

(or arXiv:2610.08872v1 [cs.IT] for this version)

https://doi.org/10.48550/arXiv.2610.08872 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.