aiqbench analysis
This paper addresses the critical oversquashing problem in Graph Neural Networks by introducing an asynchronous message passing framework that improves long-range information propagation without altering graph topology or adding excessive parameters. Theoretically, it demonstrates a slower decay of sensitivity bounds with depth compared to standard synchronous methods, yielding measurable performance gains on complex benchmarks like REDDIT-BINARY and Peptides-struct.
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.
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.
Machine Learning (cs.LG)
arXiv:2509.06777 [cs.LG]
(or arXiv:2509.06777v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2509.06777 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 220 words
Related coverage
DuoGNN: Topology-aware Graph Neural Network with Homophily and Heterophily Interaction-Decoupling
arXiv · Aug 25, 2026
DeltaGNN: Graph Neural Network with Information Flow Control
arXiv · Aug 25, 2026
HI-MeshGraphNets: Efficient and Accurate Mesh-based Physics Learning with Hierarchical Multi-scale Graph Neural Networks
arXiv · Aug 17, 2026
Benchmarking Sheaf Neural Networks for Inductive Tasks
arXiv · Aug 4, 2026