arxivmath.STcs.LGmath.PRstat.ML2026-07-18
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 $Δ=O(1)$, whose local weak limit is a broadcast-labelled Poisson Galton-Watson t…