{
  "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-\\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 $λ$ 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 $|λ|\\sqrt{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\\times 10^5$ vertices confirm the threshold for $q=2$, the hard window for $q=5$, and the many-community scaling.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.08872",
  "author_total": 1,
  "authors": [
    {
      "name": "Soroor Ghandali"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/bfgajc8kh4z0x.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.08872",
  "fulltext_url": null,
  "id": "bfgajc8kh4z0x",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.08872",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.IT"
    ],
    [
      "arxiv",
      "math.PR"
    ],
    [
      "arxiv",
      "math.ST"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "arxiv",
      "stat.TH"
    ],
    [
      "openalex",
      "3109|Complex Network Analysis Techniques"
    ]
  ],
  "openalex": "W7220904192",
  "pdf_url": "https://arxiv.org/pdf/2610.08872",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-06",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/bfgajc8kh4z0x.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:42Z",
      "native_id": "2610.08872",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.08872"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.PR",
      "subfield": "probability"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.ST",
      "subfield": "statistics"
    }
  ],
  "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",
  "title_text": "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",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:48Z",
  "url": "https://research.draconitic.com/paper/bfgajc8kh4z0x",
  "venue": "arXiv",
  "versions": []
}