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

arXiv:2610.08872v1 Announce Type: cross 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 dlambda^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 qge 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(dlambda^2)^k, convergent exactly when dlambda^21 of Chin et al. for q=n^hi communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to 3imes 10^5 vertices confirm the threshold for q=2, the hard window for q=5, and the many-community scaling.

Source: arXiv cs.LG | 2026-10-08