Search papers, labs, and topics across Lattice.
This paper introduces Inductive Correlation Clustering (ICC), a novel approach that utilizes Graph Neural Networks (GNNs) to address the scalability and transductive limitations of traditional correlation clustering algorithms. By training on common structural patterns and node features, the ICC framework can efficiently generalize to unseen graph instances, achieving a remarkable reduction in inference time by up to five orders of magnitude while maintaining a competitive approximation ratio. Extensive experiments validate the method's effectiveness, demonstrating its utility not only in clustering but also as a learnable pooling mechanism for graph classification tasks.
Achieving up to 5 orders of magnitude faster inference times, this GNN-based framework redefines scalability in correlation clustering while maintaining high accuracy.
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.
