The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
arXiv:2607.16676
2026
Architecture
2 ideas extracted · analyzed Aug 30, 2026
What the math gives to ML
The paper identifies the Kesten–Stigum ratio \(\kappa=\gamma^2\Delta\) as a quantitative control knob for useful message-passing depth on sparse graphs. Its classifier is not an ordinary uniform-hop GNN: evidence from distance \(k\) is passed through a shrinking nonlinear window \(2\operatorname{artanh}(\gamma^k z)\), which suppresses unreliable distant features. This yields a directly implementable depth rule: below \(\kappa=1\), only logarithmically many layers are needed for a target error tolerance, while above the threshold additional depth remains productive. The strongest transfer is a KS-calibrated graph architecture with distance-dependent attenuation and adaptive early stopping, especially for sparse GNNs where oversmoothing and noisy long-range aggregation are common.
Ideas from this paper
✓✓ Beats tuned baseline
2026
Replace uniform graph-convolution aggregation with a distance-aware message transform whose strength decays as \(\gamma^k\). At hop \(k\), transform the learned local evidence with \(2\operatorname{artanh}(\gamma^k z)\) before summation, so distant nodes have a provably shrinking influence window rather than accumulating unbounded noisy evidence.
Useful8/10
Difficulty5/10
Novelty6/10
✗ Mechanism failed
2026
Use the KS ratio to decide how many message-passing layers to execute per graph or per node, rather than selecting a fixed depth. In the subcritical regime, stop once the predicted remaining effect is below a tolerance; in the supercritical regime, continue until the observed logit change becomes small or a larger budget is reached.
Useful7/10
Difficulty5/10
Novelty5/10