# On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling

arXiv: https://arxiv.org/abs/2602.13684 · HTML: https://mlsanity.com/paper/2602.13684/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 14 Feb 2026.

## Builds on (most cited first, 10 of 10)

- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Correlation Clustering in Data Streams](https://mlsanity.com/paper/1812.02023/) (2018)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Almost 3-Approximate Correlation Clustering in Constant Rounds](https://mlsanity.com/paper/2205.03710/) (2022)
- [Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering](https://mlsanity.com/paper/2309.17243/) (2023)
- [Solving the Correlation Cluster LP in Sublinear Time](https://mlsanity.com/paper/2503.20883/) (2025)
- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering](https://mlsanity.com/paper/2505.21939/) (2025)
- [Improved Approximations for Ultrametric Violation Distance](https://mlsanity.com/paper/2311.04533/) (2023)

## Abstract (arXiv)

Correlation Clustering (CC) is a fundamental unsupervised learning primitive whose strongest LP-based approximation guarantees require Theta(n3) triangle inequality constraints and are prohibitive at scale. We initiate the study of sparsification--approximation trade-offs for CC, asking how much edge information is needed to retain LP-based guarantees. We establish a structural dichotomy between pseudometric and general weighted instances. On the positive side, we prove that the VC dimension of the clustering disagreement class is exactly n-1, yielding additive varepsilon-coresets of optimal size tildeO(n/varepsilon2); that at most binomn2 triangle inequalities are active at any LP vertex, enabling an exact cutting-plane solver; and that a sparsified variant of LP-PIVOT, which imputes missing LP marginals via triangle inequalities, achieves a robust frac103-approximation (up to an additive term controlled by an empirically computable imputation-quality statistic overlineGammaw) once tildeTheta(n3/2) edges are observed, a threshold we prove is sharp. On the negative side, we show via Yao's minimax principle that without pseudometric structure, any algorithm observing o(n) uniformly random edges incurs an unbounded approximation ratio, demonstrating that the pseudometric condition governs not only tractability but also the robustness of CC to incomplete information.