Optimal approximation improves constrained clustering to nearly twice optimal
Optimal Approximation for Constrained Correlation Clustering via Repulsion
Data Structures and Algorithms
Summary
Clustering groups similar data points, but making sure some points must or must not be grouped makes it tricky. The authors developed a new method called Repulsion that helps split data into clusters while respecting these strict rules. This approach gets very close to the best possible solution, improving on previous algorithms that were less precise. Their method uses clever steps that break down the problem, making it easier to find good groups efficiently.
What this means in practice
- •For data engineers: Create better automated data grouping tools that enforce strict must-link and cannot-link constraints efficiently and near-optimally.
- •For network security analysts: Improve methods to detect tightly-knit groups or suspicious clusters in network graphs where certain node pairs must or cannot be grouped together.
Authors
Yixin Cao, Ying Xu
Abstract
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.