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 $\Delta=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}(\gamma^k t(X_v))$, with $\gamma$ 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=\gamma^2\Delta$. Below the threshold ($\kappa<1$), the error sequence is Cauchy at a geometric rate, $|\mathcal{E}(\ell)-\mathcal{E}(\ell')|\le C\kappa^{(\ell+1)/3}$ for all $\ell'>\ell$, so all layers beyond depth $O(\log(1/\epsilon))$ change the error by less than $\epsilon$; conversely, under mild regularity each sufficiently deep layer still flips the decision with probability at least $c\kappa^{\ell/2}$, the empirically sharp exponent. Above the threshold ($\kappa>1$), depth is geometrically productive: $\mathcal{E}(\ell)$ is driven to a branching-process floor of order at most $1/(\kappa-1)$ at any geometric rate $\kappa^{-s\ell}$, $s<1$ (this bound has content only for $\kappa>17$). No local classifier of any depth beats the universal floor $e^{-\Delta}\Phi(-\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 $\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 $\kappa$ that we identify.