Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

• URL: http://arxiv.org/abs/2509.06777v1
• Date: Mon, 08 Sep 2025 15:03:05 GMT
• Title: Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks
• Abstract summary: Graph Neural Networks (GNNs) suffer from Oversquashing, which occurs when tasks require long-range interactions.<n>We propose an efficient model-agnostic framework that asynchronously updates node features, unlike traditional synchronous message passing GNNs.<n>Our framework is applied to six standard graph datasets and two long-range datasets to perform graph classification.
• Score: 21.49824162847618
• License: http://creativecommons.org/licenses/by/4.0/
• 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\%$ and $4\%$ improvements on REDDIT-BINARY and Peptides-struct, respectively.

Related papers

• Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs [0.8188197619481464]
  Graph neural networks (GNNs) have achieved strong performance across various real-world domains.<n>They suffer from oversquashing, where long-range information is distorted as it is compressed through limited message-passing pathways.<n>We propose a novel graph learning framework that enriches node embeddings via cross-attentive cohesive subgraph representations.
  arXiv  Detail & Related papers  (2026-03-29T05:43:29Z)
• Reservoir-Based Graph Convolutional Networks [9.230324850974378]
  We propose RGC-Net (Reservoir-based Graph Convolutional Network), which integrates reservoir dynamics with structured graph convolution.<n>RGC-Net achieves state-of-the-art performance in classification and generative tasks, including brain graph evolution, with faster convergence and reduced over-smoothing.
  arXiv  Detail & Related papers  (2026-03-25T09:50:50Z)
• DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
  Graph Neural Networks (GNNs) are designed to process graph-structured data through neighborhood aggregations in the message passing process.<n>Message-passing enables GNNs to understand short-range spatial interactions, but also causes them to suffer from over-smoothing and over-squashing.<n>We propose a mechanism called emph information flow control to address over-smoothing and over-squashing with linear computational overhead.<n>We benchmark our model across 10 real-world datasets, including graphs with varying sizes, topologies, densities, and homophilic ratios, showing superior performance
  arXiv  Detail & Related papers  (2025-01-10T14:34:20Z)
• Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
  Graph-aware Logistic Regression (GLR) is a non-neural model designed for node classification tasks. Unlike traditional graph algorithms that use only a fraction of the information accessible to GNNs, our proposed model simultaneously leverages both node features and the relationships between entities.
  arXiv  Detail & Related papers  (2024-11-19T08:32:14Z)
• Multi-Scene Generalized Trajectory Global Graph Solver with Composite Nodes for Multiple Object Tracking [61.69892497726235]
  Composite Node Message Passing Network (CoNo-Link) is a framework for modeling ultra-long frames information for association. In addition to the previous method of treating objects as nodes, the network innovatively treats object trajectories as nodes for information interaction. Our model can learn better predictions on longer-time scales by adding composite nodes.
  arXiv  Detail & Related papers  (2023-12-14T14:00:30Z)
• STAG: Enabling Low Latency and Low Staleness of GNN-based Services with Dynamic Graphs [20.94927463359297]
  We propose STAG, a GNN serving framework that enables low latency and low staleness of GNN-based services. Experimental results show that STAG accelerates the update phase by 1.3x90.1x, and greatly reduces staleness time with a slight increase in response latency.
  arXiv  Detail & Related papers  (2023-09-27T05:15:02Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• DRew: Dynamically Rewired Message Passing with Delay [7.474662887810221]
  We propose a framework that performs a layer-dependent rewiring to ensure gradual densification of the graph. We also propose a delay mechanism that permits skip connections between nodes depending on the layer and their mutual distance. We validate our approach on several long-range tasks and show that it outperforms graph Transformers and multi-hop MPNNs.
  arXiv  Detail & Related papers  (2023-05-13T22:47:40Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• AEGNN: Asynchronous Event-based Graph Neural Networks [54.528926463775946]
  Event-based Graph Neural Networks generalize standard GNNs to process events as "evolving"-temporal graphs. AEGNNs are easily trained on synchronous inputs and can be converted to efficient, "asynchronous" networks at test time.
  arXiv  Detail & Related papers  (2022-03-31T16:21:12Z)
• Causal Incremental Graph Convolution for Recommender System Retraining [89.25922726558875]
  Real-world recommender system needs to be regularly retrained to keep with the new data. In this work, we consider how to efficiently retrain graph convolution network (GCN) based recommender models.
  arXiv  Detail & Related papers  (2021-08-16T04:20:09Z)
• Graph Convolutional Neural Networks with Node Transition Probability-based Message Passing and DropNode Regularization [32.260055351563324]
  Graph convolutional neural networks (GCNNs) have received much attention recently, owing to their capability in handling graph-structured data. This work presents a new method to improve the message passing process based on node transition probabilities. We also propose a novel regularization method termed DropNode to address the over-fitting and over-smoothing issues simultaneously.
  arXiv  Detail & Related papers  (2020-08-28T10:51:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.