Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

Kushal Bose, Swagatam Das · 2025

Read Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks by Kushal Bose, Swagatam Das (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06777.txt.

Introduction

Information that cannot reach distant nodes in a graph gets a new delivery scheme from Kushal Bose and one co-author in a 2025 machine learning paper. Graph neural networks pass messages between neighbors, but bottlenecks squash those messages, a flaw called oversquashing. Rewiring the graph distorts its meaning, and widening channels adds parameters.

Instead of updating every node at each layer together, their framework updates only a batch of nodes chosen by centrality, letting information travel sequentially rather than being compressed all at once. Theory shows the method's sensitivity fades more slowly with depth than standard message passing. Applied to eight graph classification benchmarks, including two long-range ones, it produced notable gains on several datasets. The framework works with existing models rather than replacing them, which makes it easy to adopt.

Catalog record

CREATORKushal Bose, Swagatam Das
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06777

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks Thanks: Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata, India. E-mail: [email protected], [email protected] Kushal Bose, Swagatam Das Abstract Graph Neural Networks (GNNs) suffer from Oversquashing, which occurs when tasks require long-range interactions. The problem arises from the presence of bottlenecks that limit the propagation of messages among distant nodes. Recently, graph rewiring methods modify edge connectivity and are expected to perform well on long-range tasks. Yet, graph rewiring compromises the inductive bias, incurring significant information loss in solving the downstream task. Furthermore, increasing channel capacity may overcome information bottlenecks but enhance the parameter complexity of the model. To alleviate these shortcomings, we propose an efficient model-agnostic framework that asynchronously updates node features, unlike traditional synchronous message passing GNNs. Our framework creates node batches in every layer based on the node centrality values. The features of the nodes belonging to these batches will only get updated. Asynchronous message updates process information sequentially across layers, avoiding simultaneous compression into fixed-capacity channels. We also theoretically establish that our proposed framework maintains higher feature sensitivity bounds compared to standard synchronous approaches. Our framework is applied to six standard graph datasets and two long-range datasets to perform graph classification and achieves impressive performances with a 5 % 5\% and 4 % 4\% improvements on REDDIT-BINARY and Peptides-struct, respectively. I Introduction Graph Neural Networks [ 1 ] , [ 2 ] , [ 3 ] predominantly aggregate localized information, which proves to be insufficient for tasks requiring long-range interactions, like molecular property predictions [ 4 ] , [ 5 ] . The interactions between the multi-hop nodes [ 6 ] can be leveraged by enhancing the size of neighborhoods. Yet, the increasing number of neighbors introduces the problem of compressing the growing amount of information in the fixed-dimensional vectors, which creates information bottlenecks. This phenomenon is commonly known as Oversquashing [ 7 , 8 ] that causes significant information loss, particularly affecting signals from distant nodes, crucial for the downstream task [ 9 ] . Fig. 1: The workflow of CAMP is presented. The degree centrality values are sorted in descending order. For a 3 -layered GNN model, the centrality set is divided into three disjoint subsets. In each layer, the features of the nodes belonging to the pertinent subset are updated. Graph adjacency alters at every layer, and the updated node features are carried forward to the next layer. Limitations of Related Works. Mitigating oversquashing begins with converting the input graph into a fully connected (FA) graph [ 7 ] and applying it to either the final layer or every layer of the base GNN model. Recent approaches have attempted to address oversquashing through graph rewiring methods [ 10 ] , [ 11 ] , [ 12 ] , [ 13 ] , [ 14 ] , [ 15 ] , which add edges as ”shortcuts” between long-distance nodes to facilitate multi-hop information flow. Nevertheless, FA or rewiring methods tamper with the original graph topology, potentially compromising the inductive bias and incurring information loss. As an alternative avenue, Graph Transformers (GTs) [ 16 ] enable global message passing between all pairs of nodes, but they introduce prohibitive computational complexity, particularly for large graphs. More recently, PANDA [ 17 ] proposed expanding the feature dimensions of high-centrality nodes. However, this approach increases model parameters and discards potentially valuable information when selecting top-ranked features. Motivation To eliminate those limitations, we design an efficient asynchronous message passing strategy that selectively updates node features across layers, unlike standard message passing architectures like GCN [ 18 ] , GAT [ 19 ] , GCNII [ 20 ] , etc. To the best of our knowledge, we are the first to introduce a novel asynchronous message passing framework to combat oversquashing. Our framework creates node batches in every layer based on some pre-defined criterion and updates features of the nodes belonging to those batches. In contrast, unselected nodes preserve their features from previous layers. Recently, GwAC [ 21 ] processes messages from nodes to their neighboring nodes at different times. Yet, this method overlooks the channel capacity and offers no solution to tackle oversquashing. On the contrary, our asynchronous framework explicitly manages fixed-capacity channels by accessing aggregated messages at some particular layer, preventing information overflow. This layer-dependent access prevents simultaneous compression of vast amounts of information, effectively utilizing the same channel capacity without modifying graph topology or increasing the model parameters. In this work , we propose a novel plug-and-play framework C entrality-aware A synchronous M essage P assing or CAMP that adopts node centrality (degree, betweenness, etc) as our selection criterion to create node batches. CAMP performs ordering (ascending or descending) of the node centrality values and partitions the whole set into multiple disjoint subsets, each corresponding to a distinct message-passing layer. The complete workflow is illustrated in Figure 1 . This partitioning ensures that every node gets a chance to exchange messages with its neighbors at some layer. In a network, the high-centrality nodes are regarded as potential bottlenecks in message propagation. By processing these critical nodes earlier, CAMP allows their updated representations to flow to low-centrality nodes in subsequent layers. This approach strategically manages the information flow through these bottleneck nodes. Thus, asynchronous feature updates prevent the simultaneous compression of exponentially growing neighborhood information into fixed-capacity channels, diminishing the effect of oversquashing. We also offer theoretical underpinnings to validate the efficacy of our proposed framework. Unlike PANDA, our framework does not require increasing the dimension of node features, thereby asserting learning in a low-parameter regime. Notably, PANDA performs synchronous message updates, which strictly differ from CAMP. Contribution Our contributions are summarized as: • Asynchronous Message Passing We design a generalized framework for performing asynchronous message passing that departs from the conventional synchronous updates in standard GNNs. The framework selects node batches at each layer based on pre-defined criteria and updates only those features, with CAMP specifically using node centrality measures to guide batch selection. Our approach seamlessly integrates with diverse GNN architectures as a plug-and-play solution. • Oversquashing Mitigation Asynchronous message updates enable the processing of larger volumes of information through fixed-capacity channels at different layers. This prevents the simultaneous compression of exponentially growing information into fixed-sized vectors, effectively addressing the oversquashing without increasing model parameters or modifying graph structure. • Theoretical Insights We provide a theoretical analysis demonstrating that CAMP mitigates oversquashing by enhancing feature sensitivity through its asynchronous updates. II Related Works The long-standing problem of Oversquashing undermines the prowess of GNNs, which is evident in the tasks that require multi-hop interactions. The oversquashing is first observed by [ 7 ] in the ambit of message-passing of GNNs. Several research attempts were made to navigate the challenging terrain of oversquashing, like [ 8 ] , [ 22 ] . Amidst all, rewiring emerged as the most enticing solution to tackle oversquashing. Earlier works like DropEdge [ 23 ] and GDC [ 24 ] perform rewiring operations to enable long-range information exchange. A different class of methods emerged with SDRF [ 10 ] , GTR [ 14 ] , BORF [ 25 ] , and SJLR [ 26 ] characterize the exploration of edge-based curvatures. Those

Read the complete text