TL;DR
This paper investigates how much information (specifically, how many edges) is needed to maintain strong approximation guarantees for Correlation Clustering (CC) when using LP-based methods. They show a crucial dichotomy: for "pseudometric" instances, sparse information is sufficient, but for general instances, even a small amount of missing information can lead to arbitrarily bad results.
What Problem Does This Paper Address?
Correlation Clustering (CC) is a fundamental problem in machine learning and data analysis, aiming to partition data points into clusters to minimize disagreements (e.g., similar items in different clusters, dissimilar items in the same cluster). The best-known theoretical guarantees for CC rely on solving a complex Linear Program (LP) with a prohibitive number of constraints for large datasets. This leads to a practical challenge: how can we achieve these strong guarantees with less data, specifically by observing only a subset of the available edges? This paper tackles the question of "sparsifiability" – what's the minimum number of edges we need to observe to retain LP-based approximation guarantees for CC?
Methods
The authors introduce a structural dichotomy based on whether edge weights satisfy the "pseudometric condition" (a form of triangle inequality).
- Pseudometric Instances:
- Additive Coresets: They leverage VC dimension theory to show that a small subset of edges (specifically, $O(n/\epsilon^2)$) can form an "additive coreset," preserving the cost of any clustering within an additive error.
- Constraint Sparsification: They prove that at an optimal LP solution, only a small, constant number of triangle inequality constraints are linearly independent, enabling efficient LP solving via cutting planes.
- Sparse LP-PIVOT: They develop a modified LP-PIVOT algorithm that imputes missing LP marginals using triangle inequalities. They establish a sharp threshold of $\tilde{O}(n^{3/2})$ sampled edges as necessary and sufficient for this imputation to work well. Under a "good-witness" condition, this achieves near-optimal approximation.
- General Instances:
- Lower Bound: Using a "hidden heavy negative clique" construction and Yao's minimax principle, they prove that any algorithm observing $o(n)$ edges cannot achieve a constant-factor approximation. This highlights that without pseudometric structure, each edge provides independent information, and sparsification fails.
Datasets
The paper uses a variety of synthetic and real-world datasets for evaluation:
- Synthetic Pseudometric: Generated with Euclidean distances and positive/negative edges based on a median threshold.
- Synthetic General: Random weights with positive/negative edges.
- Stochastic Block Model (SBM): Standard benchmark for community detection.
- Political Blogs: Real-world dataset with known ground truth communities.
- Facebook Ego-network: Another real-world social network dataset.
- Hidden Clique: A synthetic benchmark designed to test lower bounds.
- Metric Violation Sweep: Instances where metric properties are progressively violated.
Key Insights and Ideas
- Pseudometric Structure is Key: The paper's central insight is that the pseudometric condition is not just about tractability but also about robustness to incomplete information. It allows information to "propagate" across unobserved edges via triangle inequalities.
- $O(n^{3/2})$ is a Critical Threshold: For pseudometric instances, $\tilde{O}(n^{3/2})$ sampled edges are shown to be both necessary and sufficient for effective triangle-based imputation in LP-PIVOT. This is a significant finding for practical sparse CC algorithms.
- LP Constraints are Redundant: The proof that only a constant number of triangle inequalities are linearly independent at an LP vertex is a powerful result for understanding the structure of CC LPs and enables efficient cutting-plane solvers.
- General Instances are Fragile: The $o(n)$ lower bound for general instances is stark. It implies that without the structure provided by pseudometric weights, even a small amount of missing edge information can completely break approximation guarantees.
Key Results
- Additive Coresets: Achieved with $O(n/\epsilon^2)$ edges, preserving clustering costs within $\epsilon W$.
- Sparse LP-PIVOT (Pseudometric): Achieves near-optimal approximation with $\tilde{O}(n^{3/2})$ sampled edges under a "good-witness" condition. A robust bound is provided even without this condition, parameterized by an imputation quality statistic $\Gamma_\omega$.
- Lower Bound (General): Any algorithm observing $o(n)$ edges has an unbounded approximation ratio.
- Constraint Sparsification: LP solvers can identify the exact optimum using only a small, constant number of active triangle constraints.
- Experimental Validation: The $O(n^{3/2})$ threshold for witness density was confirmed empirically. Sparse LP-PIVOT matched full LP-PIVOT performance at this threshold on pseudometric instances. The robust statistic $\Gamma_\omega$ was shown to be a good predictor of performance.
Limitations and Future Work
- Gap in Pseudometric Sparsity: While $\tilde{O}(n^{3/2})$ edges are sufficient for imputation, the lower bound for general CC is $o(n)$, leaving a gap for pseudometric instances. Further characterization is needed.
- Good-Witness Condition: The paper verifies this condition for tree metrics and empirically on Euclidean instances, but a general proof for pseudometric or near-metric instances is missing.
- Access Models: The current analysis assumes uniform sampling for edge observation. Exploring adaptive or degree-biased sampling could potentially reduce the number of required edges.
- Sign Imputation: The paper assumes signs are known. Handling partially observed signs is a direction for future work.
- Multiplicative Coresets: Obtaining true multiplicative $(1 \pm \epsilon)$-coresets remains an open challenge, especially for general instances.
Summary updated