Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs

• URL: http://arxiv.org/abs/2603.27529v3
• Date: Thu, 02 Apr 2026 11:50:22 GMT
• Title: Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs
• Abstract summary: 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.
• Score: 0.8188197619481464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) have achieved strong performance across various real-world domains. Nevertheless, they suffer from oversquashing, where long-range information is distorted as it is compressed through limited message-passing pathways. This bottleneck limits their ability to capture essential global context and decreases their performance, particularly in dense and heterophilic regions of graphs. To address this issue, we propose a novel graph learning framework that enriches node embeddings via cross-attentive cohesive subgraph representations to mitigate the impact of excessive long-range dependencies. This framework enhances the node representation by emphasizing cohesive structure in long-range information but removing noisy or irrelevant connections. It preserves essential global context without overloading the narrow bottlenecked channels, which further mitigates oversquashing. Extensive experiments on multiple benchmark datasets demonstrate that our model achieves consistent improvements in classification accuracy over standard baseline methods.

Related papers

• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks [16.5175121704107]
  Graph Neural Networks learn on graph-structured data by iteratively aggregating local neighborhood information.<n>In this work we inject randomized global embeddings of node features into standard GNNs, enabling them to efficiently capture long-range dependencies.<n> Experimental results on real-world graph learning tasks confirm that this strategy consistently improves performance over baseline GNNs.
  arXiv  Detail & Related papers  (2025-11-05T19:41:56Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  We propose ScaleGNN, a novel framework that adaptively fuses multi-hop node features for scalable and effective graph learning.<n>We show that ScaleGNN consistently outperforms state-of-the-art GNNs in both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-04-22T14:05:11Z)
• Using Subgraph GNNs for Node Classification:an Overlooked Potential Approach [13.947915030994851]
  SubGND (Subgraph GNN for NoDe) is a new subgraph-based classification framework for node classification.<n>We show that SubGND achieves performance comparable to or surpassing global message-passing GNNs.
  arXiv  Detail & Related papers  (2025-03-09T13:37:38Z)
• 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)
• Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey [0.0]
  Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, but their effectiveness is often constrained by two critical challenges. Oversquashing, where the excessive compression of information from distant nodes results in significant information loss, and oversmoothing, where repeated message-passing iterations homogenize node representations, obscuring meaningful distinctions. In this survey, we examine graph rewiring techniques, a class of methods designed to address these structural bottlenecks by modifying graph topology to enhance information diffusion.
  arXiv  Detail & Related papers  (2024-11-26T13:38:12Z)
• Multi-View Subgraph Neural Networks: Self-Supervised Learning with Scarce Labeled Data [24.628203785306233]
  We present a novel learning framework called multi-view subgraph neural networks (Muse) for handling long-range dependencies. By fusing two views of subgraphs, the learned representations can preserve the topological properties of the graph at large. Experimental results show that Muse outperforms the alternative methods on node classification tasks with limited labeled data.
  arXiv  Detail & Related papers  (2024-04-19T01:36:50Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• 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)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  We introduce the local augmentation, which enhances node features by its local subgraph structures. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner.
  arXiv  Detail & Related papers  (2021-09-08T18:10:08Z)

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.