CS Paper Radar

ExplainCC: Explaining Correlated Clusters by Node Labels

Nadeesha Shyami Kumari Herath Mudiyanselage, Florian Adriaens, Nikolaj Tatti

cs.LG cs.DS ·submitted 2026-10-28 18:50 UTC · v1
top venue

Abstract

An increasingly important requirement for clustering algorithms is that decisions and outcomes need to be clearly understandable for human users. We address this requirement for the Correlation Clustering (CC) problem, in case the objects to be clustered are accompanied by labels. In CC one seeks to partition a set of objects into clusters based on pairwise similarity and dissimilarity information. Our proposed model only considers clusters that can be explained by a label tree, which is essentially a decision tree that partitions the objects according to labels. The goal is to find an explainable partition of the data that minimizes the CC objective function. We formalize this problem from a theoretical viewpoint, and prove several hardness of approximation results, also when constraining the size of the tree. Our proposed greedy method finds locally optimal splits, and works recursively in a top-down approach. To efficiently compute the best split, we carefully maintain certain counters. An experimental evaluation demonstrates its effectiveness. The proposed algorithm processes graphs with over million edges in a few minutes, can find the ground truth in synthetic data, and is able to produce interpretable clusters in real world networks.

Comment
Accepted to CIKM 2026
DOI
10.1145/3799682.3840862

Closest papers

Nearest neighbours by meaning across the whole index.

Inductive Correlation Clustering with Graph Neural Networks

cs.LG cs.DS ·2026-08-27 ·Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan, André Panisson
top venue similarity 0.68
Abstract · Accepted at CIKM'26

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.

0.41

Optimal Approximation for Constrained Correlation Clustering via Repulsion

cs.DS ·2026-11-03 ·Yixin Cao, Ying Xu
similarity 0.65
Abstract · Superseding arXiv:2608.04883

The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.

0.15

CAESAR: Clustering via Autonomous Embedding-Space Agglomerative Reorganization

cs.LG ·2026-09-26 ·Ilan Bacry, Rémi Devaux, Antoine Jardin
benchmark similarity 0.62
Abstract · 14 pages, 3 figures

Clustering algorithms that operate on nearest-neighbor graphs, such as FINCH (First Integer Neighbor Clustering Hierarchy), depend heavily on the quality of the embedding space they are given. However, pretrained vision and language model embeddings are not optimized for this purpose. We propose CAESAR, a method that reorganizes a pretrained embedding space: a reorganization network is trained to pull mutual nearest neighbors together and push non-neighbors apart, yielding a reorganized embedding space substantially better suited to clustering. CAESAR offers a second major advantage: it never requires the number of clusters $K$. This matters because in realistic unsupervised settings, $K$ is typically unknown and discovering it is often part of the problem, yet most strong clustering methods take it as an input. We therefore design the entire CAESAR pipeline to infer $K$ rather than assume it is known. Empirically, reorganizing the embeddings consistently improves clustering over the raw space on both text and image datasets. Since the few deep clustering methods that also infer $K$ do not release their code, we complement controlled comparisons with methods that infer $K$ on the same embedding space by comparisons with strong deep clustering methods that are given the true $K$, giving them a substantial oracle advantage. Even so, CAESAR outperforms all of them on text, achieves the best results on the most challenging image benchmark and remains competitive on the others. Reorganizing pretrained embeddings thus emerges as a simple and powerful route to clustering realistic data, where classes overlap and the number of clusters is unknown.

0.18

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

cs.DS ·2026-11-06 ·Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie +1 more
similarity 0.61
Abstract

We present a fully dynamic algorithm for correlation clustering that supports \emph{vertex} insertions and deletions while maintaining an $O(1)$ approximation in polylogarithmic amortized update time. This resolves an open problem of vertex deletions posed by a recent line of work on dynamic correlation clustering. We adopt the min-disagreement objective for correlation clustering, i.e., given a signed complete graph $G=(V,E^+\cup E^-)$, we want to minimize the total number of $(+)$ edge crossing clusters and $(-)$ edges within clusters. The input is given in the adjacency list model, where each update inserts or deletes a node along with its full set of $(+)$ neighbors. Our main technical contribution is a fault-tolerant sparse-dense decomposition framework which unlike the existing decomposition-based frameworks allows for structural inconsistencies as long as the induced cost is bounded. We also show a separation between explicitly maintaining the (stronger) sparse-dense decomposition and maintaining a constant-factor approximation to correlation clustering, which may be of independent interest.

0.28

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

cs.DS ·2026-09-15 ·Chenglin Fan, Dahoon Lee, Euiwoong Lee
similarity 0.60
Abstract · 37 pages, 2 figures, in submission

We study \emph{pseudometric-weighted correlation clustering}, in which pairs have arbitrary positive or negative labels and nonnegative disagreement weights satisfying the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previous factor of $10/3$. The algorithm constructs an explicit feasible solution to the cluster LP with polynomial support and value at most $(1+\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the minimum integral clustering cost. Our main contribution is a weighted preclustering construction that witnesses a near-optimal clustering while bounding the total weight of admissible edges by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$. We obtain admissibility certificates from random walks, where the factor-two Ptolemy's inequality for pseudometrics reduces the required length of walks from $O(\log n)$ to a constant. We then bound the rounding error separately at each vertex and use the triangle inequality to control its weighted cost. Sampling and coverage corrections produce an exactly feasible solution, and the factor-two rounding completes the approximation algorithm.

0.37

Correlation Clustering with Random Partial Information

cs.DS cs.LG ·2026-08-17 ·Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
theory similarity 0.58
Abstract · 17 pages, 5 figures, 6 tables

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.

0.26

A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution

cs.LG cs.AImath.ST ·2026-10-16 ·Pintu Kumar, Nandyala Hemachandra
similarity 0.58
Abstract

Graph Convolutional Networks (GCNs) have demonstrated exceptional performance on graph-structured data. However, their success heavily relies on the availability of clean labels, an assumption that often fails in real-world scenarios. The learnability of GCNs is intrinsically linked to the neighborhood structure of nodes, making it critical to understand how this structure changes in the presence of label noise. In this work, we investigate how the neighborhood label distribution of a node changes under label noise. We mathematically derive that label noise smooths this distribution, which inherently increases its entropy and severely decreases interclass distinguishability. To address this challenge, we propose Leave-one-out Entropy Node Screening (LENS), an end-to-end framework that identifies noisy nodes by measuring the reduction in neighborhood entropy when a specific node is removed. LENS further incorporates a relabeling mechanism to recover and preserve valuable feature information instead of entirely discarding the identified noisy nodes. Crucially, the end-to-end computational overhead of LENS is remarkably low. Extensive evaluations demonstrate that our algorithm achieves state-of-the-art node classification accuracy while executing an order of magnitude faster than existing noise-robust approaches.

0.20

Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs

cs.LG stat.ML ·2026-10-05 ·Eraldo Pereira Marinho, Caetano Mazzoni Ranieri, Fabricio Aparecido Breve
benchmark similarity 0.58
Abstract · Submitted to Knowledge and Information Systems (KAIS). 32 pages, 6 figures

We introduce Round-Trip KNN Clustering (RTKNNC), a graph-based method for finding cluster structure at several neighbourhood scales without requiring the number of clusters in advance. Unlike approaches that first make a $k$-nearest-neighbour (KNN) graph undirected, RTKNNC keeps both directions of the neighbour relation: which points a given point selects and which points select it. Incoming selections are treated as weighted votes that help decide which local connections remain visible during a recursive forward-and-reverse traversal. Repeating the procedure for increasing $K$ reveals how groups persist or merge as the neighbourhood scale grows; for the reference inverse-square model before structural refinement, clusters can merge but do not split. Because graph connectivity can occasionally join distinct groups through a sparse bridge or a small region of overlap, we add an optional label-free refinement. It first tests whether an already formed component is better described by two or three Gaussian subpopulations, and accepts a subdivision only when the proposed groups are large enough and consistent with the visible KNN graph. Across eight synthetic datasets and $K=2,\ldots,16$, independent C and Python implementations produced identical partitions in all 120 reference runs. Refinement increased adjusted Rand index from $0.7817$ to $0.9627$ on a variable-density benchmark and from $0.8083$ to $0.9853$ on a sparse-bridge benchmark. Comparisons with seven external clustering methods show competitive performance while preserving a label-free cluster-construction process.

0.32