Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs
Authors: Tanvir Hossain, Muhammad Ifte Khairul Islam, Lilia Chebbah, Charles Fanning, Esra Akbas
Organizations: Department of Computer Science, Georgia State University, Atlanta, GA 30302, USA · Department of Data Science and Analytics, Kennesaw State University, 1000 Chastain Road, Kennesaw, GA 30144, USA
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.
Figures & tables
Figure 1: Pilot Study . Average number (#) of paths (ANP) per node for n∈{4,5} hop distances (HD) in Cora and Chameleon (Chm) datasets. Blue bars denote the original graph ( G ), its cores ( k ) and their (PS)-pooled subgraphs ( P−k ); green bars present their homophilic counterparts ( H−G , H−k and PH−k ). From right to left, the deep (blue & green) bar pairs (Figs. 1(a) and 1(c) ) with hatch (′∗′) present the ANP of original graph and its homophilic subgraph respectively; in other cases, more deeper bar color denotes more denser subgraph. K - thousand and, M|B - m|billion.
Figure 2: Architecture of CaCoSE\penalty(δ=3) .
M / Dv
Cora
C.Seer
Co. CS
Am. Cmp
Am. Pto
Texas
Cham.
Squir.
GCN
84.24
69.10
88.86
87.77
92.12
52.36
63.32
48.79
GAT
85.00
67.94
87.13
88.41
92.01
52.37
61.70
46.18
SAGE
83.60
67.76
88.42
87.22
91.58
56.05
62.64
47.15
LRGB
71.02
57.58
59.50
70.34
74.04
57.36
46.93
30.49
BORF
83.68
67.08
90.52
89.79
91.93
54.21
60.24
OOM
FOSR
83.66
67.24
90.44
89.82
91.83
52.37
60.31
40.19
Table 1: Node Classification Accuracy Comparison. Highest accuracy is bolded , second-best is underlined . OOM: Out of Memory in execution.
M/ DG
MUTAG
IMDB-B
IMDB-M
RDT-B
COLLAB
PROTEINS
SDRF
74.53
62.90
41.53
85.40
70.22
66.88
FOSR
75.89
60.40
37.33
83.25
69.85
66.70
BORF
64.00
60.82
38.20
84.92
OOM
68.41
GTR
76.00
70.20
45.33
89.65
68.02
71.52
DR
71.00
53.60
35.60
73.60
55.54
72.23
LASER
68.00
67.30
45.40
81.70
71.32
71.07
Table 2: Comparison of different methods on graph classification benchmarks.
Figure 3: Sensitivity Analysis . Varying Pooling Ratios (PR) and Numbers of Heads (NH). CaCoSE ’s settings for Node Classification (PR = 50% and NH = 2) and for Graph Classification (PR = 50% and NH = 1) are highlighted in bold. For NC datasets, Cora CiteSeer Texas Chameleon. For GC datasets IMDB-B COLLAB MUTAG PROTEINS.
Dv / δ
3
4
5
6
7
DG / δ
3
4
5
6
7
Cora
85.00
84.88
85.22
84.96
85.10
RDT-B
85.70
83.50
83.20
83.15
81.80
C.Seer
69.42
69.12
68.90
68.96
69.00
IMDB-B
73.20
71.60
73.40
72.70
73.79
Cham.
68.99
68.73
68.46
68.58
68.93
PROT.
71.79
72.77
72.05
71.52
72.41
Table 3: Performance comparison across different values of δ . In CaCoSE , δ=3 . Bold fonts indicate better accuracy than CaCoSE .
Figure 4: Snippets of Bridge Analysis . Edge (1976,473) in Chameleon (Chm) and (4799,358) in Squirrel (Sqr) datasets. k1 denotes the subgraph (S1) and presents the Bridge Edges.
Figure 5: Performance gain (in %) −CaCoSE vs other Decomp ositions: Illustrate on six datasets (4 NC and 2 GC). Louvain (Lv) , Metis (M) , Hierarchical (Hi) , and Random-Walk (Rw) . Except for Louvain, the other methods are annotated with the number of partitions, i.e, (M−4) presents Metis with 4 -partitions. Green and red shades present the positive and negative gains respectively.
Change
Component
Cora
C.Seer
Cham.
PROT.
IMDB-B
Attention
without
84.42
68.38
69.23
71.87
73.00
Mechanism
cross-Attention
CaEF
without CaEF
84.96
68.41
68.73
65.89
73.10
SAGPool
TopkPool
84.94
69.20
65.62
65.09
72.90
DMon
85.10
69.37
65.82
74.55
67.50
GMT
84.70
69.74
65.27
56.90
60.71
Table 4: Ablation Study and Performance Comparison across Datasets. Accuracy values exceeding CaCoSE are indicated in bold.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Scalability Test. This figure presents the maximum core value Kmax along the y -axis for networks generated with various combinations of graph size (#Nodes) and density (p) . The value of Kmax is corresponds to the maximum number of subgraphs that can be extracted through k -core decomposition.
Graph Neural Networks (GNNs) often struggle to capture long-range dependencies due to over-squashing -- a phenomenon in which the repeated compression of node embeddings into finite-size messages causes representations to collapse. Over-squashing is most often diagnosed as a property of the graph topology, with effective resistance serving as a principled measure of the bottleneck. We provide a complementary view on the matter: building on cellular sheaves, we introduce sheaf effective resistance, a generalization of effective resistance that depends on the sheaf attached to the graph, and we prove that for flat vector bundles, the over-squashing sensitivity in the Jacobian sense is upper bounded by a quantity related to the sheaf effective resistance between the nodes. The bottleneck thus need not lie in the graph itself: it can be relocated, and reduced, by adjusting the sheaf. We instantiate this idea in FlatNSD, a simple message-passing variant of Neural Sheaf Diffusion, and show that it implicitly learns to modulate total sheaf effective resistance, performing well on benchmarks designed to stress over-squashing without altering the original graph topology.
André Ribeiro, Germano Barcelos, Amauri H. Souza +2
Getulio Vargas Foundation · Federal University of Viçosa · Federal Institute of Ceará, 2δ AI +2
Graph Neural Networks are powerful models for learning from graph-structured data, yet their effectiveness is often limited by two critical challenges: over-squashing, where information from distant nodes is excessively compressed, and over-smoothing, where repeated propagation makes node representations indistinguishable. Both phenomena stem from the interaction between message passing and the input topology, ultimately degrading information flow and limiting the performance of GNNs. In this survey, we examine graph rewiring techniques, a class of methods designed to modify the graph topology to enhance information propagation in GNNs. We provide a comprehensive review of state-of-the-art rewiring approaches, delving into their theoretical underpinnings, practical implementations, and performance trade-offs.
Hugo Attali, Nathalie Pernelle, Davide Buscaldi +1
Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of k-hop neighbors grows rapidly with k. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain +2
University of Oxford · Imperial College London · Twitter