We study community recovery in the sparse symmetric stochastic block model with
q q q communities, average degree
d d d and signal strength
λ λ λ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold
d λ 2 = 1 dλ^2=1 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 D D polynomial rules is the trivial risk times
1 − C o r r D 2 1-\mathrm{Corr}_D^2 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 q\ge 5 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 ) 1-o(1) 1 − o ( 1 ) . Second, the Fisher information about
λ λ λ carried by cycle counts is a series with terms of order
k ( d λ 2 ) k k(dλ^2)^k k ( d λ 2 ) k , convergent exactly when
d λ 2 < 1 dλ^2<1 d λ 2 < 1 ; below the threshold the relative error of every unbiased cycle-based estimator of
λ k λ^k λ 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 |λ|\sqrt{d} ∣ λ ∣ d per iteration, and one EM step taken there leaves
λ λ λ unchanged. A signal-to-noise computation recovers the condition
d λ 1 / χ > 1 dλ^{1/χ}>1 d λ 1/ χ > 1 of Chin et al. for
q = n χ q=n^χ q = n χ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to
3 × 10 5 3\times 10^5 3 × 1 0 5 vertices confirm the threshold for
q = 2 q=2 q = 2 , the hard window for
q = 5 q=5 q = 5 , and the many-community scaling.