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.