aiqbench analysis
This research establishes a fundamental theoretical limit for Graph Neural Networks on sparse graphs by linking network depth to the Kesten-Stigum ratio. It demonstrates that below this threshold, additional layers yield diminishing returns in error reduction, whereas above it, deeper architectures can geometrically improve performance up to an information-theoretic floor defined by isolated nodes. These findings provide a rigorous mathematical framework for determining optimal GNN depths without relying on empirical trial-and-error.
The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
arXiv:2607.16676v1 Announce Type: 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 $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\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}$, $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.
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.
27 pages, 4 figures, 1 table. Code reproducing all numerical results is included as ancillary files
Statistics Theory (math.ST); Machine Learning (cs.LG); Probability (math.PR); Machine Learning (stat.ML)
arXiv:2607.16676 [math.ST]
(or arXiv:2607.16676v1 [math.ST] for this version)
https://doi.org/10.48550/arXiv.2607.16676 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
above_z0.4_bp.npy
above_z0.4_bpflip.npy
above_z0.4_bpnse.npy
above_z0.4_err.npy
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
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
nc_k0.95_err.npy
nc_k0.95_nse.npy
nc_k1.00_err.npy
nc_k1.00_nse.npy
nc_k1.05_err.npy
nc_k1.05_nse.npy
nonmono_certify.py
(66 additional files not shown) You must enabled JavaScript to view entire file list.
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 457 words
Related coverage
Analytic-Walk Rotary Positional Encodings for Graphs
arXiv · Sep 30, 2026
LiftGCN: Efficient Energy-Preserving Graph Learning via Joukowski Spectral Lifting for Finite Element Stress Prediction
arXiv · Sep 16, 2026
Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes
arXiv · Sep 9, 2026
Spectral Flow Certificates for Depth-Aware Long-Range Propagation in Graph Neural Networks
arXiv · Jul 28, 2026