🤖 machine learning

Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

This paper proposes an efficient, model-agnostic framework that mitigates oversquashing in Graph Neural Networks by replacing synchronous message passing with a centrality-guided asynchronous update mechanism, thereby enabling more effective long-range information propagation and achieving significant performance gains on graph classification benchmarks.

Original authors: Kushal Bose, Swagatam Das

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kushal Bose, Swagatam Das

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city where every person can only talk to their immediate neighbors. If you want to pass a message from one end of the city to the other, it must hop from person to person, layer by layer. In the world of artificial intelligence, specifically a field called graph neural networks, computers work in a similar way. They analyze data that is connected like a map, such as social networks or chemical molecules, by passing information between linked points. For simple tasks, this local chatting works perfectly. But when the computer needs to understand how two distant points relate to each other—like how a specific atom far away in a molecule affects its overall shape—the system hits a wall. As the message travels further, the computer tries to squeeze an ever-growing amount of information into a fixed-size container. Eventually, the container overflows, and the details get crushed or lost. This problem, known as "oversquashing," prevents these smart systems from solving complex puzzles that require seeing the big picture.

Researchers have tried to fix this by physically rewiring the map, adding new shortcuts between distant points so messages don't have to travel as far. Others have tried to build bigger containers to hold more information. However, these solutions often come with a cost: they either change the fundamental nature of the data or require so much extra computing power that they become impractical. A new study by Kushal Bose and Swagatam Das proposes a different approach. Instead of changing the map or the container size, they changed the timing of the conversation. They introduced a system called CAMP, which stands for Centrality-aware Asynchronous Message Passing. Rather than having every node in the network update its information at the exact same moment, this method updates them in a specific, staggered order.

The core idea relies on a simple observation: not all points in a network are equally important. Some nodes act as busy hubs, connecting many others, while others are more isolated. The researchers decided to process these hubs first. They calculated a "centrality score" for every node to determine its importance, then sorted them from most important to least important. The network is then divided into groups, with each group assigned to a different layer of the computer's processing steps. In the first layer, only the most critical nodes update their information. In the second layer, the next most critical group updates, using the fresh data from the first group. This continues until the least important nodes get their turn. By staggering the updates, the system avoids the bottleneck of trying to compress a massive amount of new information all at once. The information flows sequentially, allowing the fixed-size containers to handle the load without crushing the details.

To test if this timing trick actually worked, the team applied their method to six standard datasets used to train these networks, including chemical molecules and social networks, as well as two specialized datasets involving peptides, which are small protein chains. They paired their new timing system with two common types of graph neural networks and compared the results against existing methods that use rewiring or larger containers. The results were striking. On a dataset called REDDIT-BINARY, which involves classifying social network structures, the new method improved accuracy by 5 percent compared to the standard approach. On a dataset called Peptides-struct, which requires understanding the 3D shape of molecules, it improved performance by 4 percent. These gains were significant enough to place their method at the top of the leaderboard for several of the tests, often outperforming complex techniques that alter the graph's structure.

The researchers also looked at why this worked so well. They found that by updating nodes in a specific order, the system prevented the "smoothing" effect, where distinct features of different nodes eventually blur into one another as the network gets deeper. In standard systems, as layers stack up, the unique identity of each node gets washed out. The asynchronous approach kept the signals distinct for longer, allowing the network to maintain a clear sense of the differences between distant parts of the graph. The study showed that the method is particularly effective when the network has to handle long-range interactions, which are the exact scenarios where traditional systems tend to fail.

However, the study also noted a limitation. Calculating the importance scores for every node requires a significant amount of upfront work, especially for massive networks with millions of connections. While this pre-calculation was manageable for the medium-sized graphs used in the experiments, the authors acknowledge that their method might struggle with extremely large-scale networks found in real-world applications like global social media platforms. Despite this, the findings suggest that simply changing when information is processed can be just as powerful as changing how it is processed. By letting the most important parts of the network speak first, the system avoids the traffic jam that causes information loss, proving that sometimes, the best way to solve a complex problem is not to build a bigger road, but to manage the flow of traffic more wisely.

Technical Summary: Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

Problem Statement
Graph Neural Networks (GNNs) face a fundamental limitation known as oversquashing, where structural bottlenecks prevent effective message propagation between distant nodes. This phenomenon occurs when the exponentially growing amount of information from multi-hop neighbors must be compressed into fixed-dimensional feature vectors. Existing remedies have significant drawbacks:

Graph Rewiring: Methods that add edges (e.g., shortcuts) to improve connectivity alter the original graph topology, potentially compromising the inductive bias and incurring information loss.
Feature Expansion: Approaches like PANDA increase feature dimensions for high-centrality nodes, which adds model parameters and risks discarding valuable information during feature selection.
Global Attention: Graph Transformers enable global message passing but introduce prohibitive computational complexity for large-scale graphs.

Methodology: CAMP Framework
The authors propose CAMP (Centrality-aware Asynchronous Message Passing), a model-agnostic framework that addresses oversquashing without modifying graph structure or increasing parameter counts. Unlike standard synchronous GNNs where all node features are updated simultaneously at every layer, CAMP employs an asynchronous update strategy:

Node Selection via Centrality: The framework pre-computes node centrality scores (using measures such as Degree, Betweenness, Closeness, Load, or PageRank).
Layer-wise Partitioning: The set of nodes is partitioned into $L$ disjoint subsets, where $L$ is the number of GNN layers. The ordering of nodes (ascending or descending centrality) determines which subset is assigned to which layer.
Asynchronous Updates: At each layer $l$ , only the nodes in the assigned subset $C^{(l)}_n$ update their features by aggregating information from their neighbors. Nodes not in the current batch retain their features from previous layers (or initialization) and do not participate in the aggregation for that specific step.
Variable Hop Aggregation: This mechanism allows information to propagate sequentially. High-centrality nodes (potential bottlenecks) can be processed earlier or later depending on the dataset's information flow direction, allowing their updated representations to flow to low-centrality nodes in subsequent layers without saturating fixed-capacity channels simultaneously.

Theoretical Insights
The paper provides a theoretical analysis demonstrating that CAMP mitigates oversquashing by altering the sensitivity bound of message propagation.

In synchronous GNNs, the sensitivity bound decays exponentially with the network depth $L$ (the number of layers), leading to vanishing gradients for distant nodes.
In CAMP, the decay is governed by the length of the valid asynchronous walk ( $K(s, v)$ ) between nodes, which is bounded by the shortest path distance $d_G(s, v)$ rather than the total network depth $L$ .
Consequently, for deep networks, the CAMP bound remains bounded below by $(\alpha\beta)^{d_G(s,v)}$ , whereas the synchronous bound vanishes as $L \to \infty$ . This decoupling of contraction depth from network depth is the core mechanism for alleviating oversquashing.

Experimental Results
The framework was evaluated on six standard graph classification benchmarks (ENZYMES, MUTAG, PROTEINS, COLLAB, IMDB-BINARY, REDDIT-BINARY) and two long-range benchmarks (Peptides-func, Peptides-struct) using GCN and GIN backbones.

Performance Gains: CAMP achieved notable improvements, particularly on datasets with structural bottlenecks.
- REDDIT-BINARY: Achieved a ~24.5% improvement (84.96% accuracy with GCN vs. 68.25% baseline).
- Peptides-struct: Achieved a ~10.2% reduction in MAE (0.3138 vs. 0.3496 baseline).
- General Trends: CAMP consistently outperformed or matched state-of-the-art rewiring methods (SDRF, FoSR, BORF, GTR) and feature expansion methods (PANDA) across most datasets without increasing model parameters.
Oversmoothing Mitigation: Analysis of Dirichlet energy showed that CAMP maintains higher energy values in deeper layers compared to rewiring methods, indicating that node features remain distinguishable and oversmoothing is reduced.
Signal Propagation: CAMP demonstrated superior signal propagation relative to normalized effective resistance ( $R_{total}$ ), effectively overcoming obstacles in information flow.
Centrality Sensitivity: The optimal centrality measure (e.g., Closeness vs. PageRank) and ordering (ascending vs. descending) varied by dataset, suggesting that the choice depends on the specific information flow topology (e.g., tree-like structures vs. hub-based networks).

Significance and Limitations
The paper claims that CAMP offers a plug-and-play, model-agnostic solution that addresses oversquashing by managing information flow through asynchronous updates rather than structural modification. Its significance lies in:

Efficiency: It avoids the computational cost of global attention and the parameter overhead of feature expansion.
Inductive Bias Preservation: By not rewiring the graph, it maintains the original structural inductive bias.
Theoretical Guarantee: It provides a mathematical justification for why asynchronous updates prevent the exponential decay of sensitivity in deep networks.

Limitations:
The authors acknowledge that CAMP is not currently scalable to very large-scale graphs (e.g., OGB datasets) because computing certain centrality measures (like Betweenness) is computationally expensive during the pre-processing stage. The current experiments are limited to small-to-medium-sized molecular and social network graphs. Additionally, the framework's performance on Peptides-func was lower than the baseline, attributed to the task's reliance on local motifs rather than long-range interactions, where delayed updates offer no benefit.

Technical Summary: Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

More like this