Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks
TL;DR
This work proposes an efficient, model-agnostic framework that asynchronously updates node features across layers, unlike standard synchronous message passing, and shows theoretically that the framework's sensitivity bound decays more slowly with depth than synchronous message passing.
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.