Paper deep dive
Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs
Tanvir Hossain, Muhammad Ifte Khairul Islam, Lilia Chebbah, Charles Fanning, Esra Akbas
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/31/2026, 2:06:29 AM
Summary
The paper introduces 'Cross-attentive Cohesive Subgraph Embedding' (CaCoSE), a novel graph learning framework designed to mitigate the 'oversquashing' problem in Graph Neural Networks (GNNs). By decomposing graphs into cohesive k-core subgraphs, applying GNNs and SAGPool for local representation, and utilizing a cross-subgraph attention mechanism to capture global long-range dependencies, the model improves classification accuracy in both homophilic and heterophilic networks.
Entities (5)
Relation Signals (3)
CaCoSE → mitigates → Oversquashing
confidence 95% · we present a novel graph learning framework, that utilizes Cross-attentive Cohesive Subgraph Embeddings (CaCoSE) to alleviate oversquashing in GNNs.
CaCoSE → uses → k-core decomposition
confidence 95% · After decomposing graphs into dense cohesive k-core subgraphs, we construct edge-induced cohesive subgraphs
CaCoSE → uses → SAGPool
confidence 95% · Z k = SAGPool k (S k ,H k )
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.27529v1
- Canonical: https://arxiv.org/abs/2603.27529v1
Trouble viewing inline? Open PDF directly →
Full Text
46,141 characters extracted from source content.
Expand or collapse full text
Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs Tanvir Hossain 1 (), Muhammad Ifte Khairul Islam 1 , Lilia Chebbah 1 , Charles Fanning 2 , and Esra Akbas 1 1 Department of Computer Science, Georgia State University, Atlanta, GA 30302, USA 2 Department of Data Science and Analytics, Kennesaw State University, 1000 Chastain Road, Kennesaw, GA 30144, USA thossain5, mislam29, lchebbah1@student.gsu.edu, cfannin8@students.kennesaw.edu, eakbas1@gsu.edu Abstract. Graph neural networks (GNNs) have achieved strong per- formance 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 en- riches node embeddings via cross-attentive cohesive subgraph representa- tions to mitigate the impact of excessive long-range dependencies. This framework enhances the node representation by emphasizing cohesive structure in longe-range information but removing noisy or irrelevant connections. It preserves essential global context without overloading the narrow bottlenecked channels, which further mitigates oversquash- ing. Extensive experiments on multiple benchmark datasets demonstrate that our model achieves consistent improvements in classification accu- racy over standard baseline methods. Keywords: Oversquashing· Graph Decomposition· Graph Represen- tation Learning 1 Introduction Graph Neural Networks (GNNs) have shown strong performance in learning from graph-structured data by iteratively propagating information through lo- cal neighborhoods. While GNNs capture local signals effectively, n-hop neigh- borhood grows exponentially with distance, messages must pass through limited edges, causing important long-range information to be compressed into fixed-size node embeddings [2], referred as the oversquashing problem. Many studies have been proposed to understand and quantify oversquashing using node sensitiv- ity [25], effective resistance [8], and commute time [11]. To solve this issue, one of the most common strategy is graph rewiring, which adds edges to reduce struc- tural bottlenecks and improve information flow. However, these approaches often arXiv:2603.27529v1 [cs.LG] 29 Mar 2026 2Hossain et al. introduce significant computational overhead [18,25,24,10]. In addition, they rely on computationally intensive techniques, such as spectral decomposition [18] and optimal transport [24]. In real-world networks, critical information is often concentrated within densely connected regions that form cohesive subgraphs. When message passing aggre- gates information across these regions, long-range dependencies may still be forced through narrow inter-community bottlenecks, while dense regions dom- inate the aggregation process, further amplifying oversquashing. On the other hand, applying GNNs to these cohesive subgraphs allows capturing considerable task-relevant information for vertices in downstream graph analytics. Our pilot study (detailed in Section 2.6) illustrates that cohesion-sensitive graph partition shortens long-range dependencies while preserving homophily within subgraphs. In this paper, we present a novel graph learning framework, that utilizes Cross-attentive Cohesive Subgraph Embeddings (CaCoSE) to alleviate over- squashing in GNNs. After decomposing graphs into dense cohesive k-core sub- graphs, we construct edge-induced cohesive subgraphs guided by k-core values and learn node representations via GNN in each cohesive subgraph. Next, we apply graph pooling on these cohesive subgraphs that selectively filter out noisy or irrelevant connections while preserving task-relevant structures and embed them into subgraph embedding as critical global information. It is followed by a cross-subgraph attention mechanism that enriches subgraph embedding via capturing long range information across subgraphs. Finally, we combine these enriched subgraphs’ representations with the embeddings of nodes within the subgraphs. This combined node representation with enhanced message aggrega- tion captures both local subgraph and global long-range information for nodes, even in large-scale heterophilic networks. Our model architecture is provided in Figure 1 The contributions of our model is as follows. – This study opens up a new viewpoint to understand the reasons for over- squashing. While k-core decomposition benefits cohesive awareness among vertices, which provides essential locality for GNN operations, pooling en- hances the network’s homophily to attain meaningful global subgraph rep- resentations. – The cross-subgraph attention mechanism encodes essential global relations among all subgraphs. Merging node representation with enriched subgraph embeddings maintains both local and global connectivity, helping to alleviate the oversquahing problem in GNNs. – In a comprehensive experiment on multiple datasets, our model outperforms the standard baseline models in both node and graph classification tasks. 2 Preliminaries In this section, we describe the primary components of CaCoSE. Cross-attentive Cohesive Subgraph Embedding3 Input Graph, (1) Cohesive Subgraph Decomposition -- -- -- -- -- -- -- Attention Matrix -- -- -- + -- -- -- -- -- (2) Graph Learning (3) Cross-Subgraph Attention and Feature Combination (4) Final Prediction Fig. 1: Model Architecture. The CaCoSE framework first applies closure-aware k-core partitioning to extract cohesive edge-induced subgraphs (black). A GCN is used to learn node representations within each subgraph, followed by SAGPool to obtain compact subgraph embeddings (red). Next, a cross-attention mecha- nism captures the mutual information among subgraphs. The resulting represen- tations are concatenated with node representations and the average of attended subgraphs embeddings give the final graph representations (green). Finally, The refined nodes’ and graph’s representations are evaluated through MLP (orange). 2.1 Oversquashing. One of the major drawbacks of GNNs that occurs when information is severely bottlenecked due to its failure in useful message passing. According to [25], when a node t that is connected with another node s by an r-hop distance, the Jaco- bian operation δh (r+1) t /δx s denotes the change of the feature vector x s ’s impact on the (r + 1)st layer’s output of h (r+1) t . The quantification is observed from the absolute value |δh (r+1) t /δx s | of the Jacobian, where a negligible value indi- cates limited information propagation or oversquashing. In addition, as presented in [8], oversquashing can be associated with effective resistance between two node pairs. As low as the effective resistance is, the two nodes have more influence on each other during GNNs’ operations. 4Hossain et al. 2.2 Graph Neural Network. Graph neural networks (GNNs) embedded structural information in the graph via message propagation into node and graph representations. In graph convo- lution network (GCN), message propagation rule is defined as: H (l+1) = σ( ̃ D − 1 2 ̃ A ̃ D − 1 2 H (l) Θ (l) )(1) where, ̃ A = A + I N v denotes the adjacency matrix with the self-connections, ̃ D i = P j ̃ A ij degree matrix and Θ ∈ R d×h learnable weight matrix for h- dimensional embeddings. σ(.) indicates the ReLU(x) = max(0,x) activation. H (l) ∈ R N v ×h denotes the l th layer’s nodes’ embeddings matrix for h-dimension where H (0) = X. 2.3 Self-Attention Graph Pooling. Graph pooling captures the entire graph’s representation through compression. SAGPool [20] facilitates self-attentive graph learning through selecting impactful neighbors of vertices. It utilizes the (GCN) to measure the self-attention scores. Attn v = σ( ̃ D − 1 2 ̃ A ̃ D − 1 2 XΘ att )(2) Where Attn v ∈ R N v ×1 is calculated from ̃ A = A + I N , X and a learnable parameters’ matrix Θ att . Then utilizing the pooling ratio (PR) it selects the top-k node indices, idx = topk(Attn v ,⌈(PR)N v ⌉). Next, only considers the top- k vertices and their connections, Attn mask = Attn v [idx]. After the computation of top-k node indexes, the graph pooling of nodes’ features is measured as X out = X idx,: .⊙Attn mask and A out = A idx,idx . Finally, through a READOUT function the representation of the entire graph is computed as Z G = READOUT(X out ) . Here, READOUT is the global pooling function: sum, mean, or other advanced learnable aggregator. 2.4 k-core Decomposition. Cohesive subgraph decomposition is instrumental to determine the intended graph regions. The decomposition is performed by iteratively peeling away nodes whose degrees fall below the specified threshold: nodes with degree less than k are removed. In particular, if the graph has no isolated node, the original graph G can be denoted as 1-core. As indicated by hierarchy, G k max ⊆ ...G 3 ⊆ G 2 ⊆ G 1 , where, k ∈1, 2,...k max . A k-core subgraph is defined as follows. Definition 1. (k-core): For a given k ≥ 1, the k-core subgraph is represented from the graph G when each node in the subgraph belongs to the same (k) or more neighbors such that |N(v)|≥ k, where N(v) represents the number of neighbors of node v ∈ G k . Cross-attentive Cohesive Subgraph Embedding5 As the k-core is defined on nodes, we extend this concept to edges by introducing an edge score, defined as follows. Definition 2. (Edge score): In the context of k-core, for a graph G = (V,E) and k ≥ 1, an edge (u,v)∈ E can appear in multiple k-core subgraphs. The score of an edge is assigned as C(u,v) = maxk | (u,v)∈ G k (3) C(u,v) is computed for the highest k-valued subgraph where (u,v) exists. 2.5 Problem Statement. Our study addresses the challenge of oversquashing by introducing a cohe- sive subgraph decomposition framework along with graph pooling and a cross- subgraph attention mechanism. The primary objective is to enhance graph com- ponent features’ expressivity in downstream analytics tasks. In a formal sense, a graph is denoted as G = (V,E,X), where V is the vertex set, E is the edge set and X ∈ R N v ×d represents the initial feature vector of the vertices. The number of nodes is |V| = N v and d denotes the dimension of the nodes’ features. The graph will be partitioned into cohesion-centric subgraphs, such as S = S 1 ,S 2 ,..S k max where each S k ⊆ G corresponds to cohesion level k = 1, 2,..,k max . We apply the proposed CaCoSE model to these subgraphs. For node classification, the model trained on D v = (G, X,Y v ) to learn the map- ping f v : X→ Y v . Besides, for graph classification, it is trained on D G = (G,Y G ) to learn f G : G→ Y G . In both cases, the learned functions leverage the reduced graph complexity achieved through the CaCoSE framework. 2.6 Pilot Study GNNs struggle to learn long range dependencies due to the bottleneck effects in graph structure [2]. Cohesion-aware graph decomposition not only reduces burdens on bottlenecked channels, but also preserves essential structural proper- ties. However, in heterophilic networks, selecting task-relevant neighbors remains challenging due to cross-class mixing. This pilot study demonstrates that apply- ing k-core decomposition, followed by pooling (SAGPooling), preserves essential class-consistency among vertices even in heterophilic graphs. That enables GNNs to aggregate more reliable signals, producing stable node representations. Fig. 2 presents a pilot study on Cora (homophilic) and Chameleon (het- erophilic) datasets to examine how well subgraph decomposition preserves as- sortativity and disassortativity. According to Definition 1 and 2, we first com- pute edge scores and extract edge-induced dense subgraphs for top-three k−core values. Form Cora k ∈ 2, 3, 4 and from Chameleon k ∈ 61, 62, 63. Next, we compute the average number of paths (ANP) for vertices at hop distances n ∈ 4, 5 across original graphs, subgraphs and their homophilic counterparts H =(u,v)∈ E : y u = y v . The measures are presented in bar graphs. 6Hossain et al. According to Figs. 2(a) and 2(c), the subgraphs in both datasets retain the ho- mophilic and heterophilic (y u ̸= y v ) properties of their original graphs. While this preservation is often sufficient for homophilic networks to maintain task-relevant features, it becomes more challenging for heterophilic graphs like Chameleon. To extend the study, we apply SAGPool to each subgraph and repeat the ANP eval- uation on pooled subgraphs (PS-ANP). Interestingly, in the Chameleon dataset (Fig. 2(d)), the pooled subgraphs exhibit a higher ratio of homophilic paths to the total average number of paths per node compared to the initial evaluation. That facilitates effective representation learning in graph models [14]. Besides, it increases the ratio for the homophilic dataset. (a) ANP Cora(b) PS-ANP in Cora (c) ANP in Chameleon(d) PS-ANP in Chameleon Fig. 2: 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. 2(a) and 2(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. Cross-attentive Cohesive Subgraph Embedding7 3 Methodology 3.1 Cohesive Subgraph Decomposition. Density-informed subgraphs, called cohesive subgraphs, are crucial for effective graph structure learning where each vertex gains sufficient connectivity in a par- ticular region. Hence, learning the representation of vertices with these cohesive regions can capture adequate proximal insight for them. The k-core is one of the popular algorithms to obtain cohesion-focused subgraphs [9]. Theorem 1 (Closure-aware Edge Filtration CaEF). Let G kc denote the k-core of G = (V,E). For an edge e = (u,v) ∈ G k , where N(u) and N(v) are the neighbor set of node u and v, its triadic support is defined as S(u,v) =|N(u)∩ N(v)|(4) For k ≥ δ, if S(u,v) = 0 then (u,v) is removed from G k and reassigned to previous core C(u,v) = (k− 1), where δ denotes the edge filtering threshold. In this module, to partition a graph into cohesive subgraphs, CaCoSE employs the k-core decomposition algorithm in [6]. Initially, it calculates the edge coreness following Definition 2. For example, edge (v 4 ,v 6 ) is a part of both the 1-core and the 2-core subgraphs. As (2 > 1), the coreness score C(v 4 ,v 6 ) = 2. Similarly, (v 6 ,v 7 )∈ G 1 ∩ G 2 , hence, C(v 6 ,v 7 ) = 2. Simultaneously, we examine the existence of narrow edges in k-core sub- graphs. According to theorem (1), such edges are removed from k-core subgraph and reassigned to the (k − 1)-core subgraph. For example, in Figure 1 when k = 3, the edge (v 4 ,v 7 ) has no support. It may act as a noisy channel during neighborhood aggregation in GNNs. Hence, (v 4 ,v 7 ) is pruned from G 3 and as- signed to G 2 , then C(v 4 ,v 7 ) = 2. After assigning scores to each of the edges, the graph is decomposed into subgraphs corresponding to the same edge-score groups - S =S k k max k=1 , S k = (V S ,E S ), E S =(u,v)∈ E | C(u,v) = k (5) Note that S k ̸= G k , e.g S 3 ̸= G 3 . Although many nodes overlap across different subgraphs, they consistently carry the same weighted edges within each sub- graph. Hence, these score-based partitions avoid structural inconsistencies and preserve meaningful subgraphs for graph operations. 3.2 Subgraph Learning. In this part, CaCoSE, particularly aims to embed the topological information of all decomposed subgraphs into node representations. For this purpose, it applies the GCN to each subgraph and obtains the representation of each vertex h v ∈ H k separately. H k = GCN k (S k )(6) 8Hossain et al. H k ∈ R N v S ×h presents the node feature matrix, where N v S = |S k | denotes the number of vertices in the subgraph. Nevertheless, Just learning within subgraph get local cohesive information but loss global information. To get the global in- formation of each subgraph, CaCoSE attains subgraph embeddings via employing the self-attention graph pooling (SAGPool). Z k = SAGPool k (S k ,H k )(7) This pooling encodes essential global structural information of the subgraphs through relevant neighborhood selection, Z k ∈ R d S , where d S presents the pool- ing dimension. It effectively filters out candidate nodes’ task-irrelevant or noisy neighbors, even from highly heterophilic networks. Combining these subgraph embeddings with node embeddings provides crucial global information to ver- tices. 3.3 Cross-Subgraph Attention & Feature Combination. Cohesion-centric partitioning reduces bottleneck loads but causes loss of long- range dependency among vertices. Additionally, the subgraphs’ embeddings via pooling capture only local structural information while overlooking other sub- graphs. Hence, a way to recover global connectivity across partitions is required. The attention mechanism [27] enables the modeling of long-range dependen- cies through sequential learning. Toward this goal, cross-subgraph attention fa- cilitates communication and information propagation among distinct sequence subgraphs. In this stage, CaCoSE employs cohesion-sensitive subgraph attention to up- date the subgraph embeddings. Each subgraph embedding is processed through cross-attention to encode mutual information across regions. Attention [27] help in capturing essential awareness among entities. The pooled subgraphs’ embed- dings are represented as Z S = Z 1 ,Z 2 ...Z k max ⊤ ∈ R N S ×d S , where N S = |S| denotes the number of subgraphs and d S as feature dimension. From the sub- graphs feature matrix, the query, key, and value matrices are computed as Q = Z S W Q , K = Z S W K , V = Z S W V . Here, W Q ,W K ,W V are learnable weight matrices. Then, the attention scores are measured, and subgraphs representa- tions are updated as Attn S = softmax QK T √ d S , Z attn S = Attn S V(8) where Z attn S = Z attn 1 ,Z attn 2 ·Z attn k max T ∈ R N S ×d S presents the updated repre- sentation of subgraph, incorporating other subgraphs’ attentions where Attn S ∈ R N S ×N S denotes subgraphs’ attention matrix. It is noteworthy that the proce- dure of the attention mechanism seems like complete graph learning. Meanwhile, cohesion-sensitive partitions produce a smaller number of subgraphs; therefore, cross-subgraph attention adds only negligible computational overhead. The fi- nal graph representation is derived by taking the mean of the cross-attentive Cross-attentive Cohesive Subgraph Embedding9 subgraphs embeddings, preserving inter-subgraph relational information. Z G =Z attn S = Mean( Z attn 1 ,Z attn 2 ·Z attn k max )(9) CaCoSE obtains informative nodes’ embeddings by concatenating (∥) each sub- graph’s attentive features with its vertices representations. h v = h v ∥ Z attn k , v ∈ S k (10) If a node belongs to multiple subgraphs, a mapping (Map) function matches its occurrences, and all of its representations are summed. Such as, for v ∈ S l ,S m ,S n and S l ,S m ,S n ⊆ S, the final node representation is computed as: z v = X k∈l,m,n h v(k) (11) 3.4 Final Prediction. Decomposition reduces excessive information processing through bottlenecked channels in graph. Subsequently, selection-based learning provides compact and meaningful subgraph representations. Following that, cross-subgraph attention alleviates long-hop dependency by modeling interactions among vertices across different subgraphs. Finally, the processed node and graph representations (Z v ) and (Z G ) are passed through a multilayer perceptron (MLP) for final prediction. Experimental results validate the model’s ability in mitigating oversquashing and enhance performance on downstream inference. The detailed examination of the CaCoSE algorithm, its complexity, theoretical justification, and scalability analysis are available in Appendix A. 4 Related Works Graph Decompositions. Numerous graph decomposition algorithms are ap- plied to improve GNNs’ effectiveness. At the earlier stage of GNNs, spectral clus- tering [31,7] methods were much more popular along with the hierarchical [30] and modularity-based [26] clustering models. However, due to expensive eigen- value decomposition and clustering assignment steps, these methods encounter relatively higher time complexity. Cohesion-sensitive Decompositions. These algorithms are mostly applied to determine the interconnectedness between nodes in multiple network regions for solving different domain problems: graph compression [1], high-performance computing [22], analyzing social networks [9], etc. Only a few methods utilize these algorithms to enhance the effectiveness of GNNs. TGS [17] utilizes the k-truss algorithm for edge scoring and sparsifies noisy edges to mitigate over- smoothing in GNNs. Another model, CTAug [29], utilizes k-truss and k-core al- gorithms to provide cohesive subgraph awareness and improve graph contrastive 10Hossain et al. learning (GCL). Nonetheless, due to repetitive edge filtering for sparsification and GCL’s resource-expensive nature, both models require longer runtime. Oversquashing. Prior work [2] illustrates that due to bottlenecks in the graph, long-range neighborhood signals are distorted, which downgrades GNNs’ per- formance in downstream graph learning tasks. SDRF [25] proposed a curvature- based graph rewriting to detect edges responsible for the information bottleneck. FoSR [18] applies systematic edge addition operations in graphs in accordance with spectral expansion, while BORF [24] demonstrates the impacts of curva- ture signs for oversquashing and oversmoothing. However, due to dependency on intermediate layer output and subgraph matching with optimal transport, these models show inconsistency in large heterophilic graph operations. Another ap- proach, GTR [8], uses effective resistance and a repeated edge addition technique to reduce the impact of oversquashing in GNN. However, this method focuses on the entire graph’s information for edge rewiring, which increases complexity in executing large-scale graphs. Recently, GoKU [21] utilizes spectrum-preserving graph rewiring, first densifying the network and subsequently applying structure- aware graph sparsification. In contrast, LASER [5] adopts locality aware sequen- tial rewiring while considering multiple graph snapshots. GraphViT [16] lever- ages the Vision Transformers combined with MLP mixing mechanism to model long-range dependencies in graphs. On the other hand, LRGB [12] addresses the limitations of benchmark GNNs and Transformers in analyzing long-range ver- tex interactions. However, both approaches primarily focus on relatively ordered and structurally regular datasets. In contrast, our work concentrates on reducing oversquashing in complex, irregular real-world and social networks. 5 Experiment Results This section covers CaCoSE’s experiment outcomes’ information. First, it dis- cusses the datasets and baselines. Then, it describes the experimental setup and, finally, presents the model’s results compared to other models with various experiments. Note that, prior works [12,2] experiment on synthetic datasets (tree neighbors-match, ring transfer, etc.) are unsuitable for k-core due to their fixed structure. Hence, our experiment focuses on real-world complex networks. 5.1 Experimental Settings Datasets and Baselines. Our CaCoSE model is evaluated on 8 datasets (D v ) for the node classification task. Where five datasets are homophilic: Cora, CiteSeer, CoAuthor CS, Amazon Computers and Amazon Photos. Besides, three datasets are heterophilic: Chameleon, Squirrel and Texas. In case of graph classification tasks we experiment on six different datasets where four from social network domain: IMDB-BINARY, IMDB-MULTI, COLLAB and REDDIT-BINARY. Other two from the biomedical domian: MUTAG and PROTEINS. Cross-attentive Cohesive Subgraph Embedding11 Table 1: Node Classification Accuracy Comparison. Highest accuracy is bolded, second-best is underlined . OOM: Out of Memory in execution. M / D v CoraC.SeerCo. CSAm. CmpAm. PtoTexasCham.Squir. GCN84.2469.10 88.8687.7792.12 52.36 63.32 48.79 GAT 85.00 67.94 87.1388.4192.01 52.37 61.70 46.18 SAGE 83.60 67.76 88.4287.2291.58 56.05 62.64 47.15 LRGB 71.02 57.58 59.5070.3474.04 57.3646.93 30.49 BORF 83.68 67.08 90.52 89.7991.93 54.21 60.24 OOM FOSR 83.66 67.24 90.4489.8291.83 52.37 60.31 40.19 SDRF 84.04 67.42 90.5686.7991.71 52.63 60.74 43.02 GTR84.07 69.15 88.8785.3791.76 52.37 63.78 48.67 DR44.35 24.90 72.5071.4379.86 69.45 27.87 23.85 LASER 75.77 64.26 76.9038.6367.36 32.63 41.90 25.87 GOKU 82.66 66.08 90.04 OOM92.51 37.10 65.9046.74 CaCoSE 85.00 69.42 90.73 90.43 92.98 54.47 68.99 58.86 Table 2: Comparison of different methods on graph classification benchmarks. M/ D G MUTAGIMDB-BIMDB-MRDT-BCOLLABPROTEINS SDRF74.5362.9041.5385.4070.2266.88 FOSR75.8960.4037.3383.2569.8566.70 BORF 64.0060.8238.2084.92 OOM68.41 GTR76.0070.2045.33 89.65 68.0271.52 DR71.0053.6035.6073.6055.5472.23 LASER 68.0067.3045.4081.7071.3271.07 GOKU 74.5064.8042.4080.5569.0270.80 CaCoSE 76.99 73.20 49.14 85.7080.9571.79 Our model is compared with the 11 standard methods for the node classi- fication (NC) tasks: GCN [19], GAT [28], SAGE [15], LRGB [12], BORF [24], FoSR [18], SDRF [25], GTR [8], DR [3], LASER [5] and GOKU [21]. For graph classification (GC), we compare CaCoSE with seven methods (BORF, FOSR, SDRF, GTR, LASER and GOKU), excluding the first four baselines. Experimental Setup. We evaluate our model by running baselines’ codes for a fair comparison. Except for Cora (1208, 500, 500) and CiteSeer (1812, 500, 500), we split other datasets into 48%, 32%, and 20% for training, validation, and testing, respectively. In the case of graph classification (GC) for all datasets, the ratio is (80% : 10% : 10%). Each model runs for up to 250 iterations (NC) and 100 iterations (GC), with early stopping after 50 and 25 consecutive epochs without validation improvement, respectively. Nodes’ features are initialized with 1− hot encoding and hidden dimension in GNNs is set as 128. For a learning rate of 2.5e− 3, CaCoSE utilizes l 2 regularization with a weight decay of 1e− 4. The pooling ratio is set as 0.5 in both cases while the number of heads are set as 2 (NC) and 1 (GC). Beside, we set the CaEF threshold δ as 3. Finally, we split each dataset using 10 different seeds and report the mean accuracy as the final result. 12Hossain et al. (a) NC (PR)(b) NC (NH)(c) GC (PR)(d) GC (NH) Fig. 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, CoraCiteSeerTexasChameleon. For GC datasets IMDB-BCOLLABMUTAGPROTEINS. Table 3: Performance comparison across different values of δ. NC / δ34567GC / δ34567 Cora85.0084.8885.2284.9685.10RDT-B85.7083.5083.2083.1581.80 C.Seer69.4269.1268.9068.9669.00IMDB-B73.2071.6073.4072.7073.79 Cham.68.9968.7368.4668.5868.93PROT.71.7972.7772.0571.5272.41 5.2 Result Analysis Node Classification and Graph Classification. Table 1 demonstrates the comparison of our model with the baselines in the accuracy metric. In most cases, CaCoSE achieves a superior gain acc(CaCoSE)−acc(baseline) acc(baseline) ∗ 100 in (%) over other methods. Particularly on the dense heterophilic: Chameleon and Squirrel datasets it shows performance gains of 4.69% and 20.63%, respectively, over the nearest performing baselines GOKU and GCN. Table 2 presents the performance of our model in comparison to standard oversquashing addressing baselines. The CaCoSE achieves better or almost simi- lar performance over the baselines. Notably, on the IMDB-BINARY and COL- LAB datasets, it surpasses the other baselines with substantial gains of 4.27% and 13.50%, respectively, where the closest competing baselines are GTR and LASER. Sensitivity Analysis. We analyze the impact of the pooling ratio and num- ber of heads on model performance. As shown in Fig. 3(a), the accuracy curve for CaCoSE’s exhibits minimal fluctuation on four (NC) datasets for lower to higher pooling ratios. In contrast on GC datasets, in Fig. 3(c) MUTAG’s curve displays an uneven trend, while other three demonstrate a moderate movement. Regarding the number of heads, Fig. 3(b) illustrates that, our model experiences small-scale performance changes on the Texas and CiteSeer datasets with nearly identical on other two NC datasets. For the GC datasets (in Fig. 3(d)), there is a little fluctuation in the performance on IMDB-BINARY and COLLAB while PROTEINS exhibits a gradual increase in performance. Cross-attentive Cohesive Subgraph Embedding13 Furthermore, in Table 3, we analyze CaCoSE’s performance by changing the CaEF threshold δ across three NC datasets and three GC datasets. Generally, models performance is observed to decrease as the value of δ increase. However, fluctuates on some datasets, specially on IMDB-B and PROTEINS. We use δ = 3 as default value in our model. Analysis on Bridges in Heterophilic Networks. In experiments, CaCoSE shows outstanding performance on heterophilic networks. To determine the un- derlying reason, we analyze the bridge edges that act as the narrow channels in graphs. For each bridge edge, we examine the 2-hop neighborhood of its end- point nodes and color the vertices by class label. The same analysis is repeated on the corresponding edges in the decomposed subgraphs. In many cases, the neighborhoods around decomposed heterophilic bridges reveal latent homophily. (a) Chm (1976,473) (b) Chm-k 1c (1976,473) (c) Sqr (4799,358) (d) Sqr-k 1c (4799,358) Fig. 4: Snippets of Bridge Analysis. Edge (1976, 473) in Chameleon (Chm) and (4799, 358) in Squirrel (Sqr) datasets. k 1c denotes the 1−core subgraph and presents the Bridge Edges. Figure 4, illustrates the 2−hop surroundings of bridge edges in the both orig- inal graph (Figs 4(a) and 4(c)) and the edge-induced partitioned subgraph (Figs 4(b) and 4(d)). In the original graphs, bridge edges show strong heterophilic characteristics, causing cross-class contamination in GNN’s aggregation and re- ducing representational expressivity. After k-core decomposition, the surround- ings of bridge edges remain heterophilic and resemble star like pattern where hub node differs from its neighbors. However, most client nodes share the same class label. This allow a 2− layer GNN to effectively capture the homophilic structure. Hence, the partition preserves latent homophily in those subgraphs that enhances model’s performance. Ablation Study. In this analysis, we experiment with our model by alter- ing its components. Figure 5 illustrates the performance gains of the k-core decomposition in CaCoSE compared to alternative partition methods on six dif- ferent dataset. We use four NC datasets: two citations networks (Cora, CiteSeer) and two heterophilic networks (Chameleon, Squirrel). Besides, two GC datasets: 14Hossain et al. (a)(b)(c) Fig. 5: Performance gain (in %)−CaCoSE vs other Decompositions: Illus- trate 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 an- notated with the number of partitions. For instance, (M−4) presents Metis with four partitions. Green shades present the positive gains where red negative. . Table 4: Ablation study and performance comparison across datasets. Accuracy values exceeding CaCoSE are indicated in bold. ChangeComponentCoraC.SeerCham.PROT.IMDB-B Attentionwithout 84.42 68.38 69.2371.8773.00 Mechanismcross-Attention CaEFwithout CaEF84.96 68.41 68.7365.8973.10 SAGPool TopkPool84.94 69.20 65.6265.0972.90 DMon85.10 69.37 65.8274.5567.50 GMT84.70 69.74 65.2756.9060.71 GCN GAT83.31 68.86 65.4961.3371.70 SAGE83.92 69.12 60.0463.84 73.90 IMDB-BINARY and MUTAG. With a few exceptions, our model consistently achieves higher accuracy than other decompositions. Table 4 presents an ablation study on five datasets (three NC and two GC) to asses the contribution of different modules. First, we remove the attention mechanism, followed by the exclusion of the closure component (CaEF). In most cases, the fall in accuracy highlights the significance of these components in CaCoSE. Next, we replace SAGPool with alternative pooling methods, includ- ing TopKPool [13], DMonPool [26] and GMT [4]. With only a few exceptions, our model consistently outperforms these variants. Finally, we substitute the GCN backbone with GAT and GraphSAGE. Although GraphSAGE enables us to achieve higher accuracy on the IMDB-BINARY dataset, it performs worse on other datasets. Regarding GAT, our model consistently yields superior perfor- mance across all datasets. 6 Conclusion In a nutshell, our CaCoSE model successfully demonstrates its efficacy that facili- tates graph representation learning to overcome long-range dependency in GNNs. Cross-attentive Cohesive Subgraph Embedding15 Through cohesion-aware graph decomposition, it provides essential locality to the vertices. Besides, the SAGPool filters out noisy connections in networks and the attention mechanism provides crucial global information across subgraphs. Extensive experiments on benchmark datasets illustrate its consistency over the standard graph learning models. We expect this technique to open up new re- search directions: subgraph-wise graph rewiring, regional graph super-resolution, and parallel subgraph learning to develop robust graph representation learning models. References 1. Akbas, E., Zhao, P.: Truss-based community search: a truss-equivalence based in- dexing approach. Proceedings of the VLDB Endowment 10(11), 1298–1309 (2017) 2. Alon, U., Yahav, E.: On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205 (2020) 3. Attali, H., Buscaldi, D., Pernelle, N.: Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation. In: Forty-first International Con- ference on Machine Learning (2024) 4. Bacciu, D., Conte, A., Grossi, R., Landolfi, F., Marino, A.: K-plex cover pooling for graph neural networks. Data Mining and Knowledge Discovery 35(5), 2200–2220 (2021) 5. Barbero, F., Velingker, A., Saberi, A., Bronstein, M., Di Giovanni, F.: Locality- aware graph-rewiring in gnns. arXiv preprint arXiv:2310.01668 (2023) 6. Batagelj, V., Zaversnik, M.: An o (m) algorithm for cores decomposition of net- works. arXiv preprint cs/0310049 (2003) 7. Bianchi, F.M., Grattarola, D., Alippi, C.: Spectral clustering with graph neural networks for graph pooling. In: International conference on machine learning. p. 874–883. PMLR (2020) 8. Black, M., Wan, Z., Nayyeri, A., Wang, Y.: Understanding oversquashing in gnns through the lens of effective resistance. In: International Conference on Machine Learning. p. 2528–2547. PMLR (2023) 9. Chen, H., Conte, A., Grossi, R., Loukides, G., Pissis, S.P., Sweering, M.: On break- ing truss-based and core-based communities. ACM Transactions on Knowledge Discovery from Data 18(6), 1–43 (2024) 10. Chen, R., et al.: Redundancy-free message passing for graph neural networks. Ad- vances in Neural Information Processing Systems 35, 4316–4327 (2022) 11. Di Giovanni, F., Giusti, L., et al.: On over-squashing in message passing neural networks: The impact of width, depth, and topology. In: International conference on machine learning. p. 7865–7885. PMLR (2023) 12. Dwivedi, V.P., Rampášek, et al.: Long range graph benchmark. Advances in Neural Information Processing Systems 35, 22326–22340 (2022) 13. Gao, H., Ji, S.: Graph u-nets. In: international conference on machine learning. p. 2083–2092. PMLR (2019) 14. Gu, M., Yang, G., Zhou, S., Ma, N., Chen, J., Tan, Q., Liu, M., Bu, J.: Homophily- enhanced structure learning for graph clustering. In: Proceedings of the 32nd ACM international conference on information and knowledge management. p. 577–586 (2023) 15. Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017) 16Hossain et al. 16. He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., Bresson, X.: A generalization of vit/mlp-mixer to graphs. In: International conference on machine learning. p. 12724–12745. PMLR (2023) 17. Hossain, T., Saifuddin, K.M., et al.: Tackling oversmoothing in gnn via graph sparsification. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. p. 161–179. Springer (2024) 18. Karhadkar, K., Banerjee, P.K., Montúfar, G.: Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprint arXiv:2210.11790 (2022) 19. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016) 20. Lee, J., Lee, I., Kang, J.: Self-attention graph pooling. In: International conference on machine learning. p. 3734–3743. PMLR (2019) 21. Liang, L., Bu, F., Song, Z., Xu, Z., Pan, S., Shin, K.: Mitigating over-squashing in graph neural networks by spectrum-preserving sparsification. arXiv preprint arXiv:2506.16110 (2025) 22. Liu, Q.C., et al.: Parallel k-core decomposition with batched updates and asyn- chronous reads. In: Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. p. 286–300 (2024) 23. Malliaros, F.D., Giatsidis, C., Papadopoulos, A.N., Vazirgiannis, M.: The core de- composition of networks: Theory, algorithms and applications. The VLDB Journal 29(1), 61–92 (2020) 24. Nguyen, K., Hieu, N.M., Nguyen, V.D., Ho, N., Osher, S., Nguyen, T.M.: Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In: International Conference on Machine Learning. p. 25956–25979. PMLR (2023) 25. Topping, J., Di Giovanni, F., Chamberlain, B.P., Dong, X., Bronstein, M.M.: Un- derstanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522 (2021) 26. Tsitsulin, A., Palowitch, J., Perozzi, B., Müller, E.: Graph clustering with graph neural networks. Journal of Machine Learning Research 24(127), 1–21 (2023) 27. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information pro- cessing systems 30 (2017) 28. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. arXiv preprint arXiv:1710.10903 (2017) 29. Wu, Y., Wang, L., et al.: Graph contrastive learning with cohesive subgraph aware- ness. In: Proceedings of the ACM Web Conference 2024. p. 629–640 (2024) 30. Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. Advances in neural in- formation processing systems 31 (2018) 31. Zhang, X., Liu, H., Wu, X.M., Zhang, X., Liu, X.: Spectral embedding network for attributed graph clustering. Neural Networks 142, 388–396 (2021) Cross-attentive Cohesive Subgraph Embedding17 A Appendix A.1 Proof through Ollivier-Ricci Curvature Olliver-Ricci curvature [24]—denoted by κ(u,v)—is a measure of the local sim- ilarity of the neighborhoods of two vertices, typically by means of random walk measures centered at those vertices. This value is positive or negative when the overlap between the probability distributions of random walkers between N(u) and N(v) is large or small, respectively. Let G = (V G ,E G ) be a simple graph with shortest path distance d(u,v) for all u,v ∈ V G . Let Π(μ u ,μ v ) be the family of joint probability distributions of μ u and μ v , and take μ u to be the 1-step random walk measure given by μ u (v) = ( 1 deg(u) if v ∈ N(u) 0otherwise. Then define the L 1 -Wasserstein distance as W 1 (μ u ,μ v ) = inf π∈Π(μ u ,μ v ) X (p,q)∈V 2 G π(p,q)d(p,q) , which measures the minimum distance random walks between u and v must take to meet each other. The Ollivier-Ricci curvature is then κ(u,v) = 1− W 1 (μ u ,μ v ) d(u,v) . This carries the interpretation that whenever two random walkers are unlikely to meet, we have κ(u,v) < 0. Theorem 2. For all (u,v)∈ E G , if N(u)∩ N(v) =∅, then κ(u,v)≤ 0 Proof. For any π ∈ Π (μ u ,μ v ), consider the case of π(p,q) > 0 since π(p,q) = 0 contributes 0 to P (p,q)∈V 2 G π(p,q)d(p,q). Then p ∈ N(u) and q ∈ N(v) since P q∈V G π(p,q) = μ u (p) and P p∈V G π(p,q) = μ v (q) give p /∈ N(u)⇒ P q∈V G π(p,q) = 0 and q /∈ N(v) ⇒ P q∈V G π(p,q) = 0, respectively. But N(u)∩ N(v) = ∅, so p̸= q for all (p,q)∈ V 2 G with π(p,q) > 0. Thus, d(p,q)≥ 1. It follows that X (p,q)∈V 2 G π(p,q)d(p,q)≥ X (p,q)∈V 2 G π(p,q)· 1 = 1. Moreover, W 1 (μ u ,μ v )≥ 1. Since (u,v)∈ E G , we have d(u,v) = 1. Hence, κ(u,v) = 1− W 1 (μ u ,μ v )≤ 0. Thus, Theorem 2 shows that the edges removed by the CaEF in algorithm have nonpositive Ollivier-Ricci curvature; in other words, they correspond with bottlenecks. This approach can then be said to mitigate oversquashing by re- moving the message passing pathways associated with this class of bottlenecks. 18Hossain et al. Algorithm 1: CaCoSE Algorithm Input: A Graph G = (V,E) Output: Vertices (Z v ) and Graph’s (Z G ) Embeddings 1 # Measure Edge Score with k-core algorithm 2 C(u,v) = maxk | (u,v)∈ G k 3 # Apply CaEF Check if S(u,v) = 0 then assign previous core value as Edge score C(u,v) = C(u,v)− 1 4 S k =(u,v)∈ E : C(u,v) = k 5 # Extract subgraphs S 6 S =Edge-Subgraph(S k ) : k ∈ 1,..K max 7 foreach S k = (V S ,E S )∈ S do 8 H k = GCN k (S k ) 9 Z k = SAGPool(S k ,H k ) 10 Z attn S k = Attention(Z S k ) /* Apply Attention among Subgraphs ∀(Z S k ) */ 11 Z G = Mean( Z attn S 1 ,Z attn S 2 ...Z attn S k ) /* Graph’s Representation */ 12 Z v = zeros(N v , (d v + d S )) 13 foreach (H k ,Z attn k )∈ S k do 14 for h v ∈ H k do 15h v = (h v ∥ Z attn k ) /* Concatenation (∥) Operation */ 16 17z v = z v + h v /* Map v from H k to Z v */ 18 return Z G ,Z v A.2 Representation Learning by CaCoSE Algorithm 1 presents the execution of the CaCoSE model for k-core decompo- sition. In lines (2-3), at first, the input graph is decomposed with the k-core algorithm, where nodes achieve their coreness score. Next, CaCoSE explores all the edges and assigns the coreness scores as the edge weight. Additionally, it utilizes edge filtering (CaEF) to update specific narrow channels edge scores. In the next stage (lines 4-9), the CaCoSE extracts edge-induced subgraphs from the input graph based on the coreness scores. Note that, the k-core algorithm [23] iteratively removes the nodes with degree less than k as k increases. Thus, in each node removal stage, the (k− 1) value is assigned to the removed nodes. Then, on the partitioned subgraphs, it concurrently applies GCN for node representation learning as well as SAGPool to encode the entire subgraph’s information. In the next step (line 10), CaCoSE utilizes the attention mechanism across the subgraphs’ embeddings to capture the mutual information among them. Next, it takes the average of all the subgraph embeddings that represent the final representation of the graph (line 11). In the context of node embeddings (lines 12-17), each subgraph’s cross-attentive embeddings are concatenated with its node representations, while the shared nodes are mapped and their combined features are summed up in the vertices’ global feature matrix. Complexity. In worst case, the time complexities of k-core, SAGPool, and cross attention are O(V + E), O(V 2 ), and O(k 2 d). Hence the overall complexity of Cross-attentive Cohesive Subgraph Embedding19 CaCoSE is O(V 2 +V +E +k 2 d). Although looks complex, CaCoSE benefits from parallelizable k-core decompositions and efficient GPU execution of SAGPool and cross-attention. The detailed algorithm is omitted due to space constraints. Fig. 6: Scalability Test. This figure presents the maximum core value K max along the y-axis for networks generated with various combinations of graph size (#Nodes) and density (p). The value of K max is corresponds to the maximum number of subgraphs that can be extracted through k-core decomposition. Scalability. In this experiment, we apply the Erdős–Rényi graph generator to generate random networks of varying scale. During the generation process, we construct graphs with vertex count of 10 2 , 10 3 , 10 4 and 10 5 . For each graph size (#Nodes) we employ the edge creation probability p∈0.01, 0.05, 0.10, 0.25, 0.50. As the graph size increases, the number of possible edges-and consequently the total generated edges-grows significantly. For each generated graph, we compute the maximum core number (K max )m representing the highest number of subgraphs that can be extracted through the k-core decomposition. Figure 6 plots K max against the graph’s density p (x- axis) for networks having different scales (distinguished by colors and markers). Besides, each plot is annotated with the number of edges corresponding to each combination of graph size and density. The result depicts that even in extremely large and densely connected net- works, the maximum core value remains below 10 4 . In practical cases the value of K max is substantially smaller, this indicates that the number of extractable cohesive subgraphs via k-core decomposition is limited in realistic settings. Since, the real-world graphs are sparser and the resulting subgraphs sizes are smaller, it implies that the computational overhead introduced by the attention mechanism in our framework is negligible. It is worth noting that, the generation process was constrained by hardware capacity. For graphs with 10 4 vertices we limit the density p≤ 0.25, and for graph size with 10 5 , we consider p≤ 0.10.