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

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.
Ancillary-file links:
Ancillary files (details):
- above_z0.4_flip.npy
- above_z0.4_nse.npy
- above_z0.6_bp.npy
- above_z0.6_bpflip.npy
- above_z0.6_bpnse.npy
- above_z0.6_err.npy
- above_z0.6_flip.npy
- above_z0.6_nse.npy
- above_z0.9_bp.npy
- above_z0.9_bpflip.npy
- above_z0.9_bpnse.npy
- above_z0.9_err.npy
- above_z0.9_flip.npy
- above_z0.9_nse.npy
- below_z0.4_bp.npy
- below_z0.4_bpflip.npy
- below_z0.4_bpnse.npy
- below_z0.4_err.npy
- below_z0.4_flip.npy
- below_z0.4_nse.npy
- below_z0.6_bp.npy
- below_z0.6_bpflip.npy
- below_z0.6_bpnse.npy
- below_z0.6_err.npy
- below_z0.6_flip.npy
- below_z0.6_nse.npy
- below_z0.9_bp.npy
- below_z0.9_bpflip.npy
- below_z0.9_bpnse.npy
- below_z0.9_err.npy
- below_z0.9_flip.npy
- below_z0.9_nse.npy
- d10_above_err.npy
- d10_above_nse.npy
- d10_below_err.npy
- d10_below_nse.npy
- deep_below_bp.npy
- deep_below_err.npy
- deep_below_flip.npy
- deep_below_flipbp.npy
- experiments.py
- fig2_k0.333_err.npy
- fig2_k0.333_errbp.npy
- fig2_k0.333_flip.npy
- fig2_k0.333_flipbp.npy
- fig2_k0.653_err.npy
- fig2_k0.653_errbp.npy
- fig2_k0.653_flip.npy
- fig2_k0.653_flipbp.npy
- fig2_k0.923_err.npy
- fig2_k0.923_errbp.npy
- fig2_k0.923_flip.npy
- fig2_k0.923_flipbp.npy
- graph_above.npy
- graph_below.npy
- kappa_bp.py
- nc_k0.95_bp.npy
- nc_k0.95_err.npy
- nc_k0.95_nse.npy
- nc_k1.00_bp.npy
- nc_k1.00_err.npy
- nc_k1.00_nse.npy
- nc_k1.05_bp.npy
- nc_k1.05_err.npy
- nc_k1.05_nse.npy
- nonmono_certify.py