# The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy

arXiv: https://arxiv.org/abs/2607.16676 · HTML: https://mlsanity.com/paper/2607.16676/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 18 Jul 2026.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Contextual Stochastic Block Model: Sharp Thresholds and Contiguity](https://mlsanity.com/paper/2011.09841/) (2020)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Global and Local Information in Clustering Labeled Block Models](https://mlsanity.com/paper/1404.6325/) (2014)
- [Analysis of Corrected Graph Convolutions](https://mlsanity.com/paper/2405.13987/) (2024)

## Abstract (arXiv)

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 Delta=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 2operatornameartanh(γ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 kappa=γ2Delta. Below the threshold (kappa<1), the error sequence is Cauchy at a geometric rate, |E(ℓ)-E(ℓ')|≤ Ckappa(ℓ+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 ckappaℓ/2, the empirically sharp exponent. Above the threshold (kappa>1), depth is geometrically productive: E(ℓ) is driven to a branching-process floor of order at most 1/(kappa-1) at any geometric rate kappa-sℓ, s<1 (this bound has content only for kappa>17). No local classifier of any depth beats the universal floor e-DeltaPhi(-zeta) set by isolated roots (zeta 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 kappa that we identify.