Inductive Correlation Clustering with Graph Neural Networks

Francesco Paolo Nerini; Francesco Bonchi; Arijit Khan; André Panisson

cs.LGAug 27, 2026

Inductive Correlation Clustering with Graph Neural Networks

Authors: Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan, André Panisson

Organizations: Sapienza University of Rome, Italy · Intesa Sanpaolo AI Research, Italy · Bowling Green State University, OH, USA

Abstract

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.

Standard Correlation Clustering Benchmarks
Dataset	# Graphs	# Nodes	# Edges	# Features	# Labels
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 $\pm$ 3e-4	1.05 $\pm$ 1e-3	1.36 $\pm$ 0.04	1.12 $\pm$ 4e-4	1.27 $\pm$ 2e-3
GrQc	1.00 $\pm$ 1e-3	1.39 $\pm$ 4e-3	1.52 $\pm$ 0.02	1.26 $\pm$ 0.01	2.04 $\pm$ 5e-3
HepTh	1.00 $\pm$ 1e-3	1.23 $\pm$ 2e-3	1.48 $\pm$ 0.02	1.20 $\pm$ 4e-3	1.81 $\pm$ 2e-3
AstroPh	1.00 $\pm$ 7e-4	1.35 $\pm$ 7e-4	1.70 $\pm$ 0.12	1.26 $\pm$ 0.01	1.76 $\pm$ 2e-3
Enron	1.14 $\pm$ 5e-3	1.01 $\pm$ 2e-4	2.40 $\pm$ 0.82	1.01 $\pm$ 4e-3	1.32 $\pm$ 8e-4
cond-mat	1.01 $\pm$ 5e-3	1.09 $\pm$ 3e-4	1.25 $\pm$ 0.02	1.01 $\pm$ 3e-3	1.45 $\pm$ 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 $\pm$ 2e-3	1e-3 $\pm$ 3e-5	0.21 $\pm$ 0.7
NCI1	0.04 $\pm$ 7e-3	0.08 $\pm$ 7e-4	5.70 $\pm$ 0.10
EXPWL1	0.02 $\pm$ 7e-4	0.36 $\pm$ 0.02	11.73 $\pm$ 0.09
Reddit	0.02 $\pm$ 1e-3	17.98 $\pm$ 1.85	633.36 $\pm$ 106.97
stargazers	0.09 $\pm$ 9e-3	6.37 $\pm$ 0.06	314.00 $\pm$ 10.96
ogbg-molhiv	0.20 $\pm$ 0.05	0.70 $\pm$ 4e-03	46.72 $\pm$ 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 $\pm$ 0.0	84.2 $\pm$ 2.2	78.0 $\pm$ 0.7	80.1 $\pm$ 0.8	2.88
JBPool	98.7 $\pm$ 0.3	82.0 $\pm$ 2.3	78.9 $\pm$ 0.4	77.6 $\pm$ 0.9	4.75
HOSC	91.8 $\pm$ 0.7	85.1 $\pm$ 2.3	77.8 $\pm$ 1.0	79.0 $\pm$ 0.6	5.25
DMoN	96.3 $\pm$ 0.8	84.8 $\pm$ 1.9	77.5 $\pm$ 0.7	79.6 $\pm$ 0.8	4.75
ACC	93.3 $\pm$ 1.1	91.6 $\pm$ 1.9	78.0 $\pm$ 0.6	79.3 $\pm$ 0.8	3.50
k -MIS	99.8 $\pm$ 0.1	81.6 $\pm$ 2.7	77.9 $\pm$ 0.8	79.5 $\pm$ 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 $\pm$ 0.03	1.11 $\pm$ 5e-4	1.00 $\pm$ 2e-4	3.75 $\pm$ 2.38	25.89 $\pm$ 4.63
GrQc	2.36 $\pm$ 0.24	2.35 $\pm$ 2e-3	1.00 $\pm$ 6e-4	90.00 $\pm$ 9.79	2224.25 $\pm$ 0.00
HepTh	1.74 $\pm$ 0.02	1.64 $\pm$ 1e-3	1.00 $\pm$ 9e-4	3.66 $\pm$ 0.18	2965.73 $\pm$ 0.00
AstroPh	1.65 $\pm$ 6e-3	1.64 $\pm$ 2e-4	1.00 $\pm$ 1e-3	2.16 $\pm$ 0.04	1371.64 $\pm$ 0.00
Enron	1.50 $\pm$ 2e-3	1.56 $\pm$ 2e-3	1.12 $\pm$ 5e-3	5.71 $\pm$ 2.80	4003.65 $\pm$ 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 $\pm$ 2e-4	1.05 $\pm$ 1e-3	1.39 $\pm$ 0.05	1.68 $\pm$ 0.10
GrQc	1.00 $\pm$ 6e-4	1.30 $\pm$ 4e-3	30.00 $\pm$ 2.99	2.18 $\pm$ 0.08
HepTh	1.00 $\pm$ 9e-4	1.25 $\pm$ 1e-3	55.47 $\pm$ 8.22	2.18 $\pm$ 0.05
AstroPh	1.00 $\pm$ 1e-3	1.08 $\pm$ 9e-4	42.88 $\pm$ 7.06	2.26 $\pm$ 0.10
Enron	1.12 $\pm$ 5e-3	7.07 $\pm$ 0.87	1,056.9 $\pm$ 351.4	6.26 $\pm$ 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 $\pm$ 2e-03	190 $\pm$ 9	17751 $\pm$ 1091
No pivot	1.0 $\pm$ 7e-04	8166 $\pm$ 523	75709 $\pm$ 1287
No L2 norm.	1.0 $\pm$ 2e-03	918 $\pm$ 18	17751 $\pm$ 1091
Charikar clusters	1.1 $\pm$ 3e-03	197 $\pm$ 9	17748 $\pm$ 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 $\pm$ 22.74	67.18 $\pm$ 7.62	1.06 $\pm$ 0.02	1.03 $\pm$ 8e-03	1.09 $\pm$ 9e-03
$64$	222.51 $\pm$ 23.73	61.47 $\pm$ 7.63	1.00 $\pm$ 2e-03	1.03 $\pm$ 9e-03	1.09 $\pm$ 9e-03
$256$	221.53 $\pm$ 23.98	61.75 $\pm$ 7.86	1.01 $\pm$ 5e-03	1.03 $\pm$ 9e-03	1.09 $\pm$ 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.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

SCL-GNN: Towards Generalizable Graph Neural Networks via Spurious Correlation Learning
Mar 9, 2026Yuxiang Zhang, Enyan DaiGraph Neural Networks Spurious Correlation Robustness
The Hong Kong University of Science and Technology (Guangzhou)
CoRe-GNN: Multilevel Message passing on Coarsened graphs
Aug 3, 2026Antonin Joly, Nicolas Keriven, Aline RoumyGraph Neural Networks Graph Coarsening
CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE
G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation
Sep 21, 2026Keith Miller, Tristan CrawfordGraph Neural Networks Unsupervised Clustering

Mar 9, 2026J/K move · Enter open · S save

SCL-GNN: Towards Generalizable Graph Neural Networks via Spurious Correlation Learning

Yuxiang Zhang, Enyan Dai

The Hong Kong University of Science and Technology (Guangzhou)

Graph Neural Networks Spurious Correlation Robustness OOD Generalization

Open paper AskPDF arXiv

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.

Abstract

Clustering

Explore similar work

SCL-GNN: Towards Generalizable Graph Neural Networks via Spurious Correlation Learning

CoRe-GNN: Multilevel Message passing on Coarsened graphs

G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation