Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs

View PDF HTML (experimental)

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.

Subjects:

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

Cite as: arXiv:2603.27529 [cs.LG]

(or arXiv:2603.27529v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2603.27529

arXiv-issued DOI via DataCite

Submission history

From: Tanvir Hossain [view email] [v1] Sun, 29 Mar 2026 05:43:29 UTC (2,739 KB) [v2] Tue, 31 Mar 2026 04:46:36 UTC (2,739 KB)