The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
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ℓ that aggregates from each vertex at distance k≤ℓ the attenuated evidence 2artanh(γk t(Xv)), 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, |ℰ(ℓ)−ℰ(ℓ')|≤ Cκ(ℓ+1)/3 for all ℓ'>ℓ, 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κℓ/2, the empirically sharp exponent. Above the threshold (κ>1), depth is geometrically productive: ℰ(ℓ) is driven to a branching-process floor of order at most 1/(κ−1) at any geometric rate κ−sℓ, 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 ℓ, 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.
Related
- Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
- Geometry-Aware Simplicial Message Passing
- Message-passing graph persistence
- Learned Score-Based Turbo Message Passing for Channel Recovery From Spatially Compressed Measurements
- Efficient Message Passing for Partial Differential Equation Priors
BibTeX
@misc{baranwal2026value,
title = {{The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy}},
author = {Aseem Raj Baranwal},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2607.16676},
eprint = {2607.16676},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.16676},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
AU - Aseem Raj Baranwal
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2607.16676
UR - https://arxiv.org/abs/2607.16676
AB - 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_ℓ that aggregates from each vertex at distance k≤ℓ the attenuated evidence 2artanh(γ^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, |ℰ(ℓ)−ℰ(ℓ')|≤ Cκ^(ℓ+1)/3 for all ℓ'>ℓ, 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κ^ℓ/2, the empirically sharp exponent. Above the threshold (κ>1), depth is geometrically productive: ℰ(ℓ) is driven to a branching-process floor of order at most 1/(κ−1) at any geometric rate κ^−sℓ, 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 ℓ, 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.
ER -