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

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.