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.