Fundamental Limits of Local Graph-neural-networks on High-Girth Graphs

We establish the exact performance limits of local, message-passing Graph Neural Networks (GNNs) on graphs with high girth. We prove upper bounds for any GNN with a receptive radius of $L$ on graphs with a maximum degree of $d$ and girth greater than $2L+1$. Our central contribution is a finite-dimensional linear program that characterizes the optimal performance of any $L$-local randomized algorithm on the infinite $d$-regular tree. We demonstrate that this value serves as a hard asymptotic ceiling for local GNNs on large, high-girth graphs and prove its tightness by constructing a GNN that achieves this bound.