Inductive Correlation Clustering with Graph Neural Networks

• URL: http://arxiv.org/abs/2608.27153v1
• Date: Thu, 27 Aug 2026 14:05:48 GMT
• Title: Inductive Correlation Clustering with Graph Neural Networks
• Abstract summary: Correlation Clustering (CC) is a formulation of optimization using a graph representation of the input and does not require a pre-specified number of clusters.<n>Existing CC algorithms suffer from significant scalability issues and are inherently transductive.<n>We bridge this gap by leveraging Graph Neural Networks (GNNs) to solve Inductive Correlation Clustering.
• Score: 10.700853727952792
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Unsupervised Graph Clustering with Deep Structural Entropy [25.38926876388394]
  DeSE is a novel unsupervised graph clustering framework incorporating Deep Structural Entropy.<n>It enhances the original graph with quantified structural information and deep neural networks to form clusters.<n>Our clustering assignment method learns node embeddings and a soft assignment matrix to cluster on the enhanced graph.
  arXiv  Detail & Related papers  (2025-05-20T07:38:06Z)
• Deep Cut-informed Graph Embedding and Clustering [36.17182061654739]
  We propose an innovative and non-GNN-based Deep Cut-informed Graph embedding and Clustering framework, namely DCGC.<n>For the encoding module, we derive a cut-informed graph embedding objective to fuse graph structure and attributes by minimizing their joint normalized cut.<n>For the clustering module, we utilize the optimal transport theory to obtain the clustering assignments.
  arXiv  Detail & Related papers  (2025-03-09T14:24:09Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• CueGCL: Cluster-aware Personalized Self-Training for Unsupervised Graph Contrastive Learning [49.88192702588169]
  We propose a Cluster-aware Graph Contrastive Learning Framework (CueGCL) to jointly learn clustering results and node representations.<n>Specifically, we design a personalized self-training (PeST) strategy for unsupervised scenarios, which enables our model to capture precise cluster-level personalized information.<n>We theoretically demonstrate the effectiveness of our model, showing it yields an embedding space with a significantly discernible cluster structure.
  arXiv  Detail & Related papers  (2023-11-18T13:45:21Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• DeepCut: Unsupervised Segmentation using Graph Neural Networks Clustering [6.447863458841379]
  This study introduces a lightweight Graph Neural Network (GNN) to replace classical clustering methods. Unlike existing methods, our GNN takes both the pair-wise affinities between local image features and the raw features as input. We demonstrate how classical clustering objectives can be formulated as self-supervised loss functions for training an image segmentation GNN.
  arXiv  Detail & Related papers  (2022-12-12T12:31:46Z)
• ClusterGNN: Cluster-based Coarse-to-Fine Graph Neural Network for Efficient Feature Matching [15.620335576962475]
  ClusterGNN is an attentional GNN architecture which operates on clusters for learning the feature matching task. Our approach yields a 59.7% reduction in runtime and 58.4% reduction in memory consumption for dense detection.
  arXiv  Detail & Related papers  (2022-04-25T14:43:15Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  We propose a novel attributed graph clustering network, namely Self-supervised Contrastive Attributed Graph Clustering (SCAGC) In SCAGC, by leveraging inaccurate clustering labels, a self-supervised contrastive loss, are designed for node representation learning. For the OOS nodes, SCAGC can directly calculate their clustering labels.
  arXiv  Detail & Related papers  (2021-10-15T03:25:28Z)
• Learning Hierarchical Graph Neural Networks for Image Clustering [81.5841862489509]
  We propose a hierarchical graph neural network (GNN) model that learns how to cluster a set of images into an unknown number of identities. Our hierarchical GNN uses a novel approach to merge connected components predicted at each level of the hierarchy to form a new graph at the next level.
  arXiv  Detail & Related papers  (2021-07-03T01:28:42Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Graph Clustering with Graph Neural Networks [5.305362965553278]
  Graph Neural Networks (GNNs) have achieved state-of-the-art results on many graph analysis tasks. Unsupervised problems on graphs, such as graph clustering, have proved more resistant to advances in GNNs. We introduce Deep Modularity Networks (DMoN), an unsupervised pooling method inspired by the modularity measure of clustering quality.
  arXiv  Detail & Related papers  (2020-06-30T15:30:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.