Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

arXiv:2509.06777v2 Announce Type: replace Abstract: Graph Neural Networks (GNNs) suffer from oversquashing, where structural bottlenecks limit message propagation between distant nodes, hindering tasks that require long-range interactions. Existing remedies are limited: graph rewiring alters edge connectivity, compromising inductive bias, while increasing channel capacity adds parameters. In this work, we propose an efficient, model-agnostic framework that asynchronously updates node features across layers, unlike standard synchronous message passing. At each layer, only a centrality-guided batch of nodes updates, letting information propagate sequentially rather than compress simultaneously into fixed-capacity channels. We show theoretically that our framework's sensitivity bound decays more slowly with depth than synchronous message passing. We have applied the framework to six standard and two long-range graph classification benchmarks, and it achieves notable gains, including 5% and 4% improvements on REDDIT-BINARY and Peptides-struct, respectively.

Related

• Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges
• Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment
• LEAP: Local ECT-Based Learnable Positional Encodings for Graphs

Source: arXiv cs.LG | 2026-08-19