Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio
Preprint
Abstract
Message passing neural networks (MPNNs) are powerful models for node classification but suffer from performance limitations under heterophily (low same-class connectivity) and structural bottlenecks in the graph. We provide a unifying statistical framework exposing the relationship between heterophily and bottlenecks through the signal-to-noise ratio (SNR) of MPNN representations. The SNR decomposes model performance into feature-dependent parameters and feature-independent sensitivities. We prove that the sensitivity to class-wise signals is bounded by higher-order homophily -- a generalisation of classical homophily to multi-hop neighbourhoods -- and show that low higher-order homophily manifests locally as the interaction between structural bottlenecks and class labels (class-bottlenecks). Through analysis of graph ensembles, we provide a further quantitative decomposition of bottlenecking into underreaching (lack of depth implying signals cannot arrive) and oversquashing (lack of breadth implying signals arriving on fewer paths) with closed-form expressions. We prove that optimal graph structures for maximising higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters. This yields BRIDGE, a graph ensemble-based rewiring algorithm that achieves near-perfect classification accuracy across all homophily regimes on synthetic benchmarks and significant improvements on real-world benchmarks, by eliminating the ``mid-homophily pitfall'' where MPNNs typically struggle, surpassing current standard rewiring techniques from the literature. Our framework, whose code we make available for public use, provides both diagnostic tools for assessing MPNN performance, and simple yet effective methods for enhancing performance through principled graph modification.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Graph Neural Networks for Graphs With Heterophily: A SurveyIEEE Transactions on Knowledge and Data Engineering, 2026
- Statistical Physics Analysis of Graph Neural Networks: Approaching Optimality in the Contextual Stochastic Block ModelPhysical Review X, 2025
- A survey on learning from graphs with heterophily: recent advances and future directionsFrontiers of Computer Science, 2025
- GraphWorld2022
- A Comprehensive Survey on Graph Neural NetworksIEEE Transactions on Neural Networks and Learning Systems, 2020
- Hierarchical Block Structures and High-Resolution Model Selection in Large NetworksPhysical Review X, 2014
- Stochastic blockmodels and community structure in networksPhysical Review E, 2011
- Random Dot Product Graph Models for Social Networks2007
- Stochastic blockmodels: First stepsSocial Networks, 1983
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952