{
  "abstract": "How deep does a graph neural network need to be on a sparse graph? We study its purest statistical form: node classification on the sparse contextual stochastic block model (CSBM) with average degree $Δ=O(1)$, whose local weak limit is a broadcast-labelled Poisson Galton-Watson tree. Prior work derived a message-passing classifier $h_\\ell$ that aggregates from each vertex at distance $k\\le\\ell$ the attenuated evidence $2\\operatorname{artanh}(γ^k t(X_v))$, with $γ$ the edge signal and $t$ a bounded likelihood-ratio transform of the feature. We prove that the value of depth is governed by a single number, the Kesten-Stigum ratio $κ=γ^2Δ$. Below the threshold ($κ<1$), the error sequence is Cauchy at a geometric rate, $|\\mathcal{E}(\\ell)-\\mathcal{E}(\\ell')|\\le Cκ^{(\\ell+1)/3}$ for all $\\ell'>\\ell$, so all layers beyond depth $O(\\log(1/ε))$ change the error by less than $ε$; conversely, under mild regularity each sufficiently deep layer still flips the decision with probability at least $cκ^{\\ell/2}$, the empirically sharp exponent. Above the threshold ($κ>1$), depth is geometrically productive: $\\mathcal{E}(\\ell)$ is driven to a branching-process floor of order at most $1/(κ-1)$ at any geometric rate $κ^{-s\\ell}$, $s<1$ (this bound has content only for $κ>17$). No local classifier of any depth beats the universal floor $e^{-Δ}Φ(-ζ)$ set by isolated roots ($ζ$ the feature signal-to-noise ratio), while the first layer provably helps by an explicit total-variation amount. Simulations with an exact belief-propagation baseline on the same trees show that the pairwise rule's error curve is mildly non-monotone in $\\ell$, so an optimal finite depth exists (an exact instance is certified in the appendix), while BP saturates strictly faster, at an effective per-layer ratio below $κ$ that we identify.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2607.16676",
  "author_total": 1,
  "authors": [
    {
      "name": "Aseem Raj Baranwal"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/3gs7pc86my1e0.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2607.16676",
  "fulltext_url": null,
  "id": "3gs7pc86my1e0",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2607.16676",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.PR"
    ],
    [
      "arxiv",
      "math.ST"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "arxiv",
      "stat.TH"
    ],
    [
      "openalex",
      "1702|Advanced Graph Neural Networks"
    ]
  ],
  "openalex": "W7169862855",
  "pdf_url": "https://arxiv.org/pdf/2607.16676",
  "pmcid": null,
  "pmid": null,
  "published": "2026-08-29",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/3gs7pc86my1e0.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:48Z",
      "native_id": "2607.16676",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2607.16676"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.PR",
      "subfield": "probability"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.ST",
      "subfield": "statistics"
    }
  ],
  "title": "The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy",
  "title_text": "The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy",
  "type": "preprint",
  "updated_at": "2026-10-30T12:17:54Z",
  "url": "https://research.draconitic.com/paper/3gs7pc86my1e0",
  "venue": "arXiv",
  "versions": []
}