Improving weighted clustering with triangle inequality guarantees
Pseudometric-Weighted Correlation Clustering via Spectral Preclustering
Data Structures and Algorithms
Summary
This paper improves a method for grouping things based on how much they disagree with each other, where the disagreements follow a triangle rule (the shortest path between two points is never longer than going through a third). The researchers created an algorithm that can find nearly the best grouping much faster than before. They combine mathematical tricks about distances and random choices to build groups step-by-step, ensuring the errors stay small. This work helps to make complicated clustering problems easier to solve while keeping accuracy.
What this means in practice
- •For data scientists: Optimize clustering of large datasets with weighted disagreements obeying triangle inequality for better grouping accuracy.
- •For machine learning engineers: Improve preprocessing steps in machine learning pipelines by producing high-quality clusters from weighted similarity data efficiently.
Authors
Chenglin Fan, Dahoon Lee, Euiwoong Lee
Abstract
We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previously best known factor of $10/3$. Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights. The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals. Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length. We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most $(1+\varepsilon)\mathrm{OPT}$. After rescaling $\varepsilon$, factor-$2$ rounding gives the stated approximation guarantee.