The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
Machine Learning
Summary
The authors study how deep graph neural networks (GNNs) need to be when working on sparse graphs for node classification tasks. They focus on a mathematical model (CSBM) where connections are few and noisy, analyzing how the 'depth' of information aggregation affects classification error. They find that a key number, called the Kesten-Stigum ratio, controls whether deeper layers help or not: if this ratio is below 1, adding layers quickly stops improving error; if above 1, more layers can keep improving error but only up to a certain limit. Their results also show that no matter how deep the network is, there is a fundamental error floor that can't be surpassed due to isolated nodes, and simulations confirm that an optimal finite depth exists for best performance.
Authors
Aseem Raj Baranwal
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_\ell$ that aggregates from each vertex at distance $k\le\ell$ the attenuated evidence $2\operatorname{artanh}(γ^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, $|\mathcal{E}(\ell)-\mathcal{E}(\ell')|\le Cκ^{(\ell+1)/3}$ for all $\ell'>\ell$, 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κ^{\ell/2}$, the empirically sharp exponent. Above the threshold ($κ>1$), depth is geometrically productive: $\mathcal{E}(\ell)$ is driven to a branching-process floor of order at most $1/(κ-1)$ at any geometric rate $κ^{-s\ell}$, $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 $\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 $κ$ that we identify.