PaperlayerView exact revision on arXiv

Source-linked AI summary

Inductive Correlation Clustering with Graph Neural Networks

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

arXiv:2608.27153v1cs.LGcs.DS

TL;DR

Existing Correlation Clustering methods face scalability problems and are transductive, requiring reruns on new instances. The paper introduces a GNN-based inductive formulation and framework for generalizing clustering to unseen graphs. Experiments report efficient, high-quality inductive solutions, competitive transductive performance, and a graph-pooling application.

  • Problem

    Existing Correlation Clustering algorithms scale poorly, often ignore node features, and require rerunning the algorithm for each new graph instance.

  • Method

    The paper introduces Inductive Correlation Clustering and CC-GNN, using GNNs to learn clustering functions from graph structure and node features, with NodeGNN and LinkGNN variants.

  • Results

    LinkGNN provides high-quality, computationally efficient inductive solutions, while NodeGNN achieves superior solution quality in transductive settings.

  • Takeaways & Limitations

    The framework generalizes clustering to unseen graphs and also serves as a learnable pooling layer for graph learning architectures.

  • Takeaways & Limitations

    The transductive matrix-factorization approach has O(|V|^2K) loss computation and is strictly transductive, failing to generalize to unseen data.

Abstract

from arXiv · show

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.

1 Introduction

Correlation Clustering groups similar objects and separates dissimilar ones, but existing methods face scalability limits, overlook node features, and must be rerun for each instance. The paper introduces Inductive Correlation Clustering and a GNN framework with transductive and inductive variants, validated on clustering and pooling tasks.

  • Correlation Clustering partitions graph nodes to minimize disagreements between missing within-cluster edges and existing between-cluster edges.
  • Existing Correlation Clustering algorithms are APX-hard, often scale poorly, ignore node features, and are inherently transductive.
  • Inductive Correlation Clustering generalizes Correlation Clustering to unseen graphs by leveraging graph structure and node features.
  • CC-GNN provides transductive NodeGNN and inductive LinkGNN variants within a scalable GNN-based training framework.
  • LinkGNN provides efficient, high-quality inductive solutions, while NodeGNN performs strongly on standard Correlation Clustering instances.
  • The framework is also used as a learnable pooling layer for deep graph learning architectures.

2 Related Work

Related work spans approximation algorithms, dynamic and streaming variants, inductive graph clustering, and graph pooling. This paper differs by learning across a distribution of graphs to cluster entirely new instances with low latency.

  • Correlation clustering: Correlation Clustering has a rich theoretical literature, but scalable implementations providing high-quality approximations remain scarce or simplified.
  • Correlation clustering: KwikCluster provides a 3-approximation in expectation for unweighted complete graphs, while ModifiedPivot improves the bound to 3 − ε0 for some ε0 > 0.
  • Correlation clustering variants: Online, active, streaming, and dynamic Correlation Clustering variants generally modify one continuing problem instance rather than generalizing across new graphs.
  • Inductive clustering on graphs: Most standard graph clustering techniques are transductive, whereas inductive approaches learn functions applicable to unseen problem instances.
  • Graph pooling: Graph pooling uses learnable clustering to coarsen graphs, manage computational complexity, and enhance GNN expressivity.

3 Inductive Correlation Clustering

Inductive Correlation Clustering learns a parameterized function that maps graph instances with node features to clustering assignments. Training minimizes clustering cost on observed graphs, with the objective of minimizing cost on disjoint unseen graphs.

  • Correlation Clustering partitions nodes into an unfixed number of clusters while minimizing disagreements.
  • The co-clustering matrix M = CC^T records whether each pair of nodes belongs to the same cluster and simplifies the cost formulation.
  • Because the exact objective is APX-hard, continuous relaxations constrain M values to [0, 1] with metric and symmetry constraints.
  • In the inductive setting, graphs are drawn from distribution D, and a parameterized function f_θ maps each graph instance to a clustering assignment.
  • Training selects parameters θ* that minimize clustering cost on training graphs, with the ultimate objective of minimizing cost on disjoint unseen test graphs.

4 CC-GNN Framework

CC-GNN combines pivot-based local training with node-wise and link-wise GNN formulations for transductive and inductive correlation clustering. The link-wise approach uses distance-based co-clustering and connected components to generalize clustering to unseen graphs while reducing inference cost.

  • Framework overview: CC-GNN supports transductive NodeGNN and inductive LinkGNN variants for correlation clustering.The framework distinguishes node-wise optimization of C from edge-wise optimization of M.
  • Scalable training: Pivot-based sampling trains on batches formed from randomly selected pivots and their direct neighbors instead of the full graph.This adapts KwikCluster-style locality to reduce the cost of message passing and loss optimization.
  • Transductive NodeGNN: The node-wise method relaxes cluster assignments to C ∈ [0, 1]^{|V|×K} and uses a differentiable loss based on the signed adjacency matrix W.Softmax applied to GNN outputs satisfies the per-node assignment constraint, while the relaxation restricts solutions to at most K clusters.
  • Transductive NodeGNN: The node-wise loss costs O(|V|^2K) on the full graph, and choosing K ≪ |V| reduces overhead but restricts reachable solutions.As graph size grows, approximation quality drops unless K is scaled accordingly.
  • Inductive LinkGNN: LinkGNN optimizes a distance-based co-clustering matrix M from normalized node embeddings rather than fixed cluster assignments.The resulting matrix is symmetric and satisfies the required triangular inequalities, while hypersphere normalization imposes an additional relaxation constraint.
  • Inductive LinkGNN: At inference, LinkGNN thresholds M on existing edges and returns connected components, reducing computation of M from O(|V|^2F) to O(|E|F).Increasing the threshold sparsifies the auxiliary graph and produces more connected components.

5 Experimental Setup

The experiments evaluate CC-GNN across transductive, inductive, approximation-quality, and pooling settings using diverse graph datasets and established baselines. Performance is measured by normalized solution cost for CC and task-specific accuracy metrics for pooling.

  • Experimental goals: The experimental suite targets approximation quality, transductive performance, inductive generalization, and graph-pooling utility.The framework is evaluated across four research questions and corresponding benchmark settings.
  • Datasets: Standard CC benchmarks use individual unweighted social, citation, and email graphs without node features.These datasets come from the SNAP and SuiteSparse collections.
  • Datasets: Graph-level inductive benchmarks include synthetic, molecular, protein-association, and social-network graph collections.The datasets include EXPWL1, MUTAG, NCI1, OGBG-molhiv, OGBG-ppa, GitHub-Stargazers, and REDDIT-Binary.
  • Datasets and baselines: Pooling experiments use EXPWL1, MUTAG, NCI1, and OGBG-molhiv, comparing CCPool with six established graph-pooling methods.The baselines include DMON, HOSC, JBPool, ACC, k-MIS, and MaxCut Pooling.
  • Evaluation: CC performance is measured by solution cost normalized relative to the minimum cost achieved across all methods.Experiments report means over runs with standard errors of the mean.
  • Approximation-quality setup: Approximation-quality tests use 36-node SBM graphs with 10 random instances per configuration, varying the number of equal-sized blocks from 2 to 36.Intra-block and interblock connection probabilities are 0.8 and 0.1, respectively.
  • Model architectures and hyperparameters: NodeGNN and LinkGNN use single-layer GCN architectures without nonlinearities, while NodeGNN's maximum cluster count is set to min(10^4, |V|).The pooling implementation CCPool uses LinkGNN for cluster selection, sums pooled features, and connects clusters when an original edge exists.

6 Experimental Results and Discussion

Experiments show that CC-GNN provides strong approximation quality, transductive performance, inductive generalization, efficiency, and competitive graph-pooling results. Ablations identify architectural and algorithmic choices that affect quality, scalability, and transfer.

  • Approximation Quality: Both NodeGNN and LinkGNN stay within 1.05× of the exact optimum on synthetic SBM graphs, although error generally increases with the number of blocks.LinkGNN exhibits larger error than NodeGNN.
  • Transductive Performance: NodeGNN usually achieves the minimum transductive cost, while LinkGNN becomes best or second best on large datasets whose cluster counts exceed K=10,000.LinkGNN is not restricted by a maximum cluster count, improving scalability on email-Enron and cond-mat-2005.
  • Inductive Generalization and Efficiency: LinkGNN generalizes better than NodeGNN to unseen graphs, outperforming KwikCluster on 4 of 7 datasets and often approaching ModifiedPivot.NodeGNN overfits graph-specific cluster identities, whereas LinkGNN learns transferable structural patterns.
  • Inductive Generalization and Efficiency: LinkGNN inference is significantly faster than ModifiedPivot and KwikCluster because it does not retrain from scratch for each graph.Figure 4 compares normalized inductive costs, with error bars showing standard errors and values normalized per train/test split.
  • Application to Graph Pooling: CCPool matches dense pooling methods on molecular datasets while retaining sparse architectures’ ability to adapt to new graphs and avoid fixed cluster limits.On EXPWL1, fixed-K dense poolers can fail in inductive clustering tasks; SEP exceeded 48 hours on OGBG-molhiv without completing training.
  • Ablation Studies: Single-layer NodeGNN variants consistently perform best, while LinkGNN is less sensitive to architectural choices because it has substantially fewer parameters.Embedding-only LinkGNN performs best on ca-AstroPh but is transductive and cannot generalize to unseen graphs.
  • Ablation Studies: Pivot sampling reduces memory and training time without degrading quality, while L2 normalization speeds convergence 5x and constrains embedding distances to [0,1].Alternative rounding with Charikar’s method increases clustering costs because it assumes a different CC relaxation.
  • Ablation Studies: The training-optimized threshold, typically t≈0.90, transfers robustly to unseen graphs, while embedding dimension has little effect once sufficiently large.The sensitivity analysis evaluates solution quality across threshold choices rather than using only the training-selected threshold.

7 Conclusions

The paper introduces Inductive Correlation Clustering and CC-GNN to learn clustering functions for unseen graphs. Experiments support NodeGNN for transductive quality, LinkGNN for inductive generalization and efficient inference, and CCPool for graph classification.

  • Conclusions: Inductive Correlation Clustering learns a parameterized function that handles unseen graph instances.It extends standard Correlation Clustering with inductive generalization.
  • Conclusions: CC-GNN combines GNN-based local optimization with pivot-based sampling for scalable and efficient Correlation Clustering training.The framework includes NodeGNN and LinkGNN formulations.
  • Conclusions: NodeGNN achieves superior solution quality in transductive settings, while LinkGNN generalizes to new graphs with quality comparable to transductive baselines and lower inference time.These conclusions summarize the paper’s comprehensive experiments.
  • Conclusions: CCPool adapts LinkGNN into a learnable pooling mechanism that is competitive with state-of-the-art graph-classification techniques.The application targets hierarchical structural information in graph data.

GenAI Usage Disclosure

The authors disclose using generative AI tools only for coding assistance, proofreading, and editorial polishing. They retain responsibility for the research ideas, methods, experiments, analyses, and final content.

  • Usage Disclosure: Generative AI tools assisted with experimental-pipeline implementation and manuscript proofreading and editorial polishing.The disclosure describes the tools as assistive rather than authorship-bearing.
  • Usage Disclosure: The authors state that the research ideas, problem formulation, methods, experimental protocol, results interpretation, and final content are their own responsibility.They report reviewing and validating all AI-assisted code and text.
Loading 2608.27153v1…