CS Paper Radar

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie, Samson Zhou

cs.DS ·submitted 2026-11-06 20:02 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

cs.DS ·2026-09-15 ·Chenglin Fan, Dahoon Lee, Euiwoong Lee
similarity 0.66
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.36

Optimal Approximation for Constrained Correlation Clustering via Repulsion

cs.DS ·2026-11-03 ·Yixin Cao, Ying Xu
similarity 0.66
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

Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee

cs.DS ·2026-11-04 ·He Sun, Yong Zhang, Yacong Zhou
theory similarity 0.65
Abstract · 41 pages, 3 figures, 1 table

Partitioning the vertex set of a graph $G=(V,E)$ into clusters is a classical problem in computer science. As vertices within clusters should be well connected and cuts between clusters sparse, Oveis Gharan and Trevisan (SODA 2014, [OGT14]) proposed to measure the partition quality using inner and outer conductance, i.e., the bi-criteria guarantee. Specifically, when partitioning $V$ into vertex-disjoint subsets $P_1,\ldots, P_k$, every subgraph induced by $P_i$ should have high conductance, while the conductance of $P_i$ in $G$ should be low. They studied the existence of such a partition and designed a polynomial-time algorithm achieving this guarantee. For more than a decade, their algorithm remained the only one achieving this guarantee on its output clusters. In this paper, we study faster cluster decomposition algorithms under the same setup as [OGT14] and prove three results: 1. We make their existential result algorithmic: Our algorithms run in nearly-linear time, and achieve the same bi-criteria guarantee as the one in [OGT14] up to constant factors, including the asymptotically tight dependence on $k$. 2. We prove that their existential result holds algorithmically under a much weaker condition on the initial disjoint subsets. To achieve this, we develop a general algorithm framework that boosts the approximation guarantee of a solution: given an $α$-approximate solution to the $k$-way conductance problem, if $ρ_G(k+1)/ρ_G(k)=Ω\left(α/\varepsilon\right)$, then a $(1+\varepsilon)$-approximate solution can be obtained using only $O(k(1+\logα))$ minimum $s$-$t$ cut computations. 3. We present a nearly-linear time algorithm that finds clusters with the bi-criteria guarantee. Our algorithm has the same guarantee as the one in [OGT14], which, for any unweighted graph of $n$ vertices and $m$ edges, runs in $\widetilde{O}(knm^2)$ time.

0.33

Competitive Random-Order Correlation k-Clustering

cs.DS ·2026-09-28 ·Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman, Omer Wasim, Tegan Wilson
theory similarity 0.63
Abstract · 58 pages, 5 figures, 1 table

Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is to compute a partition of the vertex set such that the total number of disagreements, i.e. the sum of edges between clusters, and non-edges within clusters, is minimized. In this paper, we study correlation $k$-clustering, in which the total number of clusters is restricted to $k$. Correlation $k$-clustering is NP-hard, and while previous work has presented a polynomial time approximation scheme for constant $k$, there are no known results for general $k$. Our first result is a polynomial-time constant-factor approximation algorithm for correlation $k$-clustering for general $k$. The main focus of this work is in the more challenging online setting. Noting that the best competitive ratio under adversarial arrivals is known to be $Ω(n)$, we concentrate on the well-studied random-order model, where vertices arrive in random order and on arrival of a vertex, edges to its earlier-arrived neighbors are revealed. We prove a surprising lower bound of $Ω(\log k)$-competitiveness for any online algorithm, which can be extended to $Ω(\log n)$ when $k = \text{poly}(n)$. Finally, the main result of this paper is a polylogarithmic upper bound on the competitive ratio for correlation $k$-clustering, using an algorithm inspired by the classic Pivot algorithm for correlation clustering. All theorems have been verified using Lean.

0.19

ExplainCC: Explaining Correlated Clusters by Node Labels

cs.LG cs.DS ·2026-10-28 ·Nadeesha Shyami Kumari Herath Mudiyanselage, Florian Adriaens, Nikolaj Tatti
top venue similarity 0.61
Abstract · Accepted to CIKM 2026

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.

0.35

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.60
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

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.59
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

Fully Dynamic Triangle and 4-Vertex Subgraph Counting: From Theory to Practice and Back Again

cs.DS ·2026-10-21 ·Kathrin Hanauer, Sophia Heck, Monika Henzinger, Leonhard Sidl
published similarity 0.59
Abstract · Short version to appear at ALENEX 2027

Counting small patterns is a core primitive in large-scale graph analytics, with numerous applications in data management and network analysis. As modern graphs are massive and continuously evolving, maintaining such counts efficiently under updates is essential. Although specialized dynamic algorithms for patterns with up to four vertices exist, they remain largely theoretical; practitioners instead rely on general-purpose or approximate methods. We present an in-depth study of two dynamic approaches by Eppstein et al. and Hanauer et al. for maintaining counts of triangles and all connected four-vertex subgraph patterns, both based on variants of heavy-light vertex partitioning. We introduce theoretical and practical optimizations and develop hybrid variants that combine complementary strengths of both approaches. Experiments on 56 large real-world and synthetic dynamic graphs show that our optimized algorithms outperform the original methods and strong static and dynamic baselines on nearly all instances, both in total running time and worst-case update time, with speedups of up to several orders of magnitude. We further provide practical guidelines for algorithm selection and tuning. To the best of our knowledge, this is the first comprehensive empirical study of heavy-light partitioning for dynamic subgraph counting, and our findings may inform other algorithms based on this technique.

0.39