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

Aseem Raj Baranwal

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)…