Correlation Clustering (CC) is a natural formulation of clustering in combinatorial optimization, which uses a graph representation of the input and does not require a pre-specified number of clusters. Given n objects and a pairwise similarity function, the goal is to cluster the objects so that similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its versatility, existing CC algorithms suffer from significant scalability issues and are inherently transductive: i.e., the algorithm must be executed from scratch for any new problem instance. In this work, we bridge this gap by leveraging Graph Neural Networks (GNNs) to solve Inductive Correlation Clustering, a novel generalization of the CC problem designed to handle unseen graph instances. By learning to exploit common structural patterns and node features during training, our framework generalizes to new graphs drawn from the same distribution with minimal computational overhead with respect to standard algorithms. We demonstrate the effectiveness and scalability of our approach through extensive experiments. Our framework not only excels in the inductive setting, e.g., lowering the inference time up to 5 order of magnitude, while maintaining an approximation ratio within 10% of the best baseline solution, but also achieves competitive results on standard (transductive) CC benchmarks. Finally, we showcase a practical application of our framework as a learnable pooling mechanism for graph classification. Our results indicate that our method serves as an efficient pooling layer, enhancing the ability of GNNs to capture hierarchical structural information in networks.
Figures & tables
Figure 1. (a) A toy graph instance where the optimal CC solution is highlighted by colored circles (ground truth). The corresponding node embeddings generated by LinkGNN are projected onto the unit circle ( F=2 ). Before training (b), embeddings are randomly distributed. After training (c), the model separates the nodes into 5 distinct angular sectors.
Figure 2. Example of pooling on the graph of Figure 1 with r=20% . (a) Red dotted lines indicate the 20% of edges connecting node pairs with the greatest embedding distance. (b) The pooling operation merges nodes within the same connected components and then re-introduce their original connections: the graph is significantly compressed, retaining fewer than 15% of original edges.
Dataset
# Graphs
# Nodes
# Edges
# Features
# Labels
Standard Correlation Clustering Benchmarks
polblogs ( Davis and Hu, 2011 )
1
1,224
16,715
–
–
ca-GrQc ( Jure, 2014 )
1
5,241
14,484
–
–
ca-HepTh ( Jure, 2014 )
1
9,875
25,973
–
–
ca-AstroPh ( Jure, 2014 )
1
18,771
198,050
–
–
email-Enron ( Jure, 2014 )
1
36,692
183,831
–
–
Table 1. Statistics for all datasets. Standard Correlation Clustering benchmark consist of individual graph instances, while the Graph-Level Tasks and Pooling benchmark consist of collections of graphs (# Nodes and # Edges report average values). We report node features and number of labels exclusively of datasets used in pooling experiments. In the case of OGBG-ppa, we use only the first 30,000 graphs of the dataset.
Figure 3. Approximation ratio analysis on synthetic Stochastic Block Model (SBM) graphs ( ∣V∣=36 ) relative to the optimal solution found by Gurobi. A ratio of 1.0 indicates an optimal solution. Shaded areas represent the standard error of the mean over 10 iterations. (a) Approximation ratio for NodeGNN ( K=36 ) and LinkGNN as a function of the number of blocks n (proxy for ground truth clusters). (b) Impact of the maximum cluster budget K on the approximation quality of NodeGNN for varying block densities.
NodeGNN
LinkGNN
KwikClus.
ModPivot
CFP
polblogs
1.00 ± 3e-4
1.05 ± 1e-3
1.36 ± 0.04
1.12 ± 4e-4
1.27 ± 2e-3
GrQc
1.00 ± 1e-3
1.39 ± 4e-3
1.52 ± 0.02
1.26 ± 0.01
2.04 ± 5e-3
HepTh
1.00 ± 1e-3
1.23 ± 2e-3
1.48 ± 0.02
1.20 ± 4e-3
1.81 ± 2e-3
AstroPh
1.00 ± 7e-4
1.35 ± 7e-4
1.70 ± 0.12
1.26 ± 0.01
1.76 ± 2e-3
Enron
1.14 ± 5e-3
1.01 ± 2e-4
2.40 ± 0.82
1.01 ± 4e-3
1.32 ± 8e-4
cond-mat
1.01 ± 5e-3
1.09 ± 3e-4
1.25 ± 0.02
1.01 ± 3e-3
1.45 ± 7e-4
Table 2. Normalized cost comparison in the transductive setting. Values for each dataset are normalized relative to the minimum cost achieved across all methods (1.0 indicates the best performance). The horizontal line separates standard Correlation Clustering benchmarks (top) from node classification datasets (bottom). Best performance for each dataset is in bold, while second best performance is underlined. At the bottom, number of times a method appears as best or second-best out of all datasets.
Figure 4. Comparison of methods in an inductive setting. Each point has error bars corresponding to the standard error of the mean, but are often too small. (I) was used to demark inductive methods, (T) for transductive ones. Values were normalized in each train/test split according to the minimum cost reached across methods.
LinkGNN
KwikCluster
ModifiedPivot
MUTAG
0.01 ± 2e-3
1e-3 ± 3e-5
0.21 ± 0.7
NCI1
0.04 ± 7e-3
0.08 ± 7e-4
5.70 ± 0.10
EXPWL1
0.02 ± 7e-4
0.36 ± 0.02
11.73 ± 0.09
Reddit
0.02 ± 1e-3
17.98 ± 1.85
633.36 ± 106.97
stargazers
0.09 ± 9e-3
6.37 ± 0.06
314.00 ± 10.96
ogbg-molhiv
0.20 ± 0.05
0.70 ± 4e-03
46.72 ± 0.31
Table 3. Inference time (in seconds) with the methods in the inductive setting of § 6.3 .
EXPWL1
MUTAG
NCI1
molhiv
Avg. Rank
CCPool
100.0 ± 0.0
84.2 ± 2.2
78.0 ± 0.7
80.1 ± 0.8
2.88
JBPool
98.7 ± 0.3
82.0 ± 2.3
78.9 ± 0.4
77.6 ± 0.9
4.75
HOSC
91.8 ± 0.7
85.1 ± 2.3
77.8 ± 1.0
79.0 ± 0.6
5.25
DMoN
96.3 ± 0.8
84.8 ± 1.9
77.5 ± 0.7
79.6 ± 0.8
4.75
ACC
93.3 ± 1.1
91.6 ± 1.9
78.0 ± 0.6
79.3 ± 0.8
3.50
k -MIS
99.8 ± 0.1
81.6 ± 2.7
77.9 ± 0.8
79.5 ± 0.8
4.50
Table 4. Accuracy of pooling methods on graph classification datasets. Accuracy is reported for all datasets except OGBG-molhiv, where ROC-AUC is used. For each dataset, best score is in bold and second-best is underlined. For OGBG-molhiv, SEP consistently exceeded our 48-hour time limit (OOT) without completing the training. Last column shows the average ranking of each method (lower is better).
Dataset
EMBOnly
Linear
1 Layer
2 Layers
3 Layers
NodeGNN
polblogs
1.06 ± 0.03
1.11 ± 5e-4
1.00 ± 2e-4
3.75 ± 2.38
25.89 ± 4.63
GrQc
2.36 ± 0.24
2.35 ± 2e-3
1.00 ± 6e-4
90.00 ± 9.79
2224.25 ± 0.00
HepTh
1.74 ± 0.02
1.64 ± 1e-3
1.00 ± 9e-4
3.66 ± 0.18
2965.73 ± 0.00
AstroPh
1.65 ± 6e-3
1.64 ± 2e-4
1.00 ± 1e-3
2.16 ± 0.04
1371.64 ± 0.00
Enron
1.50 ± 2e-3
1.56 ± 2e-3
1.12 ± 5e-3
5.71 ± 2.80
4003.65 ± 0.00
Table 5. Ablation study on model complexity of NodeGNN and LinkGNN , comparing the clustering cost (Eq. 10 ). The best model on each row is in bold; costs are normalized for each dataset across all methods used in the table.
Dataset
GCN
GraphSAGE
GIN
GAT
NodeGNN
polblogs
1.00 ± 2e-4
1.05 ± 1e-3
1.39 ± 0.05
1.68 ± 0.10
GrQc
1.00 ± 6e-4
1.30 ± 4e-3
30.00 ± 2.99
2.18 ± 0.08
HepTh
1.00 ± 9e-4
1.25 ± 1e-3
55.47 ± 8.22
2.18 ± 0.05
AstroPh
1.00 ± 1e-3
1.08 ± 9e-4
42.88 ± 7.06
2.26 ± 0.10
Enron
1.12 ± 5e-3
7.07 ± 0.87
1,056.9 ± 351.4
6.26 ± 0.58
Table 6. Ablation study on the message passing operation by comparing clustering costs. In all models, we use a single message passing layer. As in Table 5 , the costs are normalized for each dataset across all models used in the table. Best performance for each line is in bold.
Ablation
Approx. Ratio
Train time (s)
GPU (MB)
Baseline
1.0 ± 2e-03
190 ± 9
17751 ± 1091
No pivot
1.0 ± 7e-04
8166 ± 523
75709 ± 1287
No L2 norm.
1.0 ± 2e-03
918 ± 18
17751 ± 1091
Charikar clusters
1.1 ± 3e-03
197 ± 9
17748 ± 1092
Table 7. Ablation study on inductive algorithm design choices. We compute the cost ratio relative to the baseline configuration obtained without any ablation ("Baseline")).
D
t=0.25
t=0.50
t=0.90
t=0.95
t=1.00
16
232.50 ± 22.74
67.18 ± 7.62
1.06 ± 0.02
1.03 ± 8e-03
1.09 ± 9e-03
64
222.51 ± 23.73
61.47 ± 7.63
1.00 ± 2e-03
1.03 ± 9e-03
1.09 ± 9e-03
256
221.53 ± 23.98
61.75 ± 7.86
1.01 ± 5e-03
1.03 ± 9e-03
1.09 ± 9e-03
Table 8. Approximation ratio depending on embedding dimension D and threshold t selection. The ratio is computed with respect to the minimum across all configurations.
Graph Neural Networks (GNNs) have demonstrated remarkable success across diverse tasks. However, their generalization capability is often hindered by spurious correlations between node features and labels in the graph. Our analysis reveals that GNNs tend to exploit imperceptible statistical correlations in training data, even when such correlations are unreliable for prediction. To address this challenge, we propose the Spurious Correlation Learning Graph Neural Network (SCL-GNN), a novel framework designed to enhance generalization on both Independent and Identically Distributed (IID) and Out-of-Distribution (OOD) graphs. SCL-GNN incorporates a principled spurious correlation learning mechanism, leveraging the Hilbert-Schmidt Independence Criterion (HSIC) to quantify correlations between node representations and class scores. This enables the model to identify and mitigate irrelevant but influential spurious correlations effectively. Additionally, we introduce an efficient bi-level optimization strategy to jointly optimize modules and GNN parameters, preventing overfitting. Extensive experiments on real-world and synthetic datasets demonstrate that SCL-GNN consistently outperforms state-of-the-art baselines under various distribution shifts, highlighting its robustness and generalization capabilities.
Yuxiang Zhang, Enyan Dai
The Hong Kong University of Science and Technology (Guangzhou)
Training Graph Neural Networks on large graphs is challenged by the memory cost of storing all node representations across layers. We show that several existing scalable approaches can be written as structured modifications of the GNN propagation matrix, providing a unified perspective that exposes their respective limitations. In particular, graph coarsening replaces it by a low-rank approximation that enables spectral guarantees but assigns uniform representations to clustered nodes, while Cluster-GCN restricts the propagation matrix to intra-cluster connections that allow efficient batching but sever long-range information. These are complementary failures of the same decomposition of the graph into groups of nodes. To obtain the best of both worlds, we propose CoRe-GNN, which performs both propagations in parallel at each layer: a coarsened inter-cluster term capturing long-range structure, and a local intra-cluster term preserving per-node discriminability. We prove that CoRe-GNN inherits analogous approximation guarantees to those of graph coarsening, and introduce a natural cluster-based batching scheme that scales to graphs with millions of nodes. On node classification benchmarks spanning homophilic, heterophilic, large-scale, and long-range graphs, CoRe-GNN outperforms both graph coarsening and Cluster-GCN baselines. Notably, CoRe-GNN reaches competitive accuracy on long-range tasks, while remaining memory-efficient through batching.
Antonin Joly, Nicolas Keriven, Aline Roumy
CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE
We introduce Graph Neural Automata Clustering (G-NAC), an unsupervised clustering method in which observations interact as cells on a fixed neighborhood graph. A shared recurrent graph-neural cellular rule evolves latent domain states through local interactions, which are converted into a rank-based spectral affinity for partitioning. Across 73 clustering tasks from 57 benchmark datasets, G-NAC achieved a mean adjusted Rand index (ARI) of 0.7951, comparable to Genie at 0.7941 and higher than the other evaluated baselines. Empirical training time and GPU memory scaled approximately linearly from 5,000 to 100,000 nodes. Learned transition rules also transferred from smaller source graphs to independent 100,000-node samples generated under matched conditions. These results demonstrate a recurrent graph-clustering formulation while identifying dependencies on graph quality, readout design, and source-target similarity.