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

arXiv:2607.16676v2 Announce Type: replace-cross 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 kleell the attenuated evidence 2operatorname{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^2Delta. Below the threshold (kappaell, 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 ckappa^{ell/2}, the empirically sharp exponent. Above the threshold (kappa>1), depth is geometrically productive: E(ell) is driven to a branching-process floor of order at most 1/(kappa-1) at any geometric rate kappa^{-sell}, s17). 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.

Source: arXiv cs.LG | 2026-09-01