Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering

Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman

Introduction

Correlation Clustering is a fundamental problem in unsupervised machine learning and combinatorial optimization. Given a set of items and pairwise relationships categorized as either "similar" (+) or "dissimilar" (-), the objective is to partition the items into clusters that minimize the total number of "mistakes." A mistake occurs when a similar pair is placed in different clusters or a dissimilar pair is placed in the same cluster.

Despite its simple formulation, the problem is NP-hard. For over a decade, the research community faced a significant theoretical barrier: a 2-approximation ratio. While recent advancements utilizing the Sherali-Adams hierarchy—a method for strengthening linear programming (LP) relaxations—began to chip away at this limit, progress remained incremental, moving from 2.06 down to 1.994. This paper presents a major breakthrough, delivering a 1.73-approximation algorithm by introducing a novel preclustering framework that effectively manages the errors inherent in complex rounding techniques.

The Challenge: Correlated Rounding Errors

The primary obstacle in surpassing the 2-approximation barrier using higher-order LP hierarchies like Sherali-Adams has been the management of "correlated rounding" errors. These complex LPs provide fractional solutions that must be rounded to discrete clusters. However, the rounding process often introduces additive errors that are difficult to bound, particularly when dealing with the intricate dependencies between multiple vertices.

Previous attempts struggled because these errors would accumulate, negating the theoretical benefits of the more powerful LP relaxation. The authors identify that the key to unlocking the potential of the Sherali-Adams hierarchy lies not just in the rounding itself, but in preparing the graph structure before rounding occurs.

Methodology: The Preclustering Framework

The authors introduce a multi-stage algorithmic framework centered on a technique called preclustering. This process serves as the "secret sauce" that tames the rounding errors.

1. Identifying Atoms

The algorithm begins by identifying "atoms"—groups of vertices so tightly connected by positive edges and so sparsely connected to the rest of the graph that they are highly likely to belong to the same cluster in an optimal solution. By treating these atoms as single units and identifying "admissible" edges (pairs that are candidates for clustering), the algorithm bounds the "unsure" regions of the problem. This isolation ensures that the additive errors from subsequent rounding steps become negligible relative to the total cost.

2. Set-Based Rounding

Departing from traditional "pivot-based" methods that construct clusters one vertex at a time, the authors introduce a set-based rounding approach. Inspired by techniques in metric labeling, this method samples entire sets as clusters based on probabilities derived from the LP solution. This approach is particularly effective at minimizing mistakes on similar (+) edges.

3. Refined Pivot-Based Rounding

The authors also improve the analysis of classic pivot-based rounding. By leveraging the preclustering results, they can bypass many of the complex "corner cases" that previously hindered the efficiency and tightness of the analysis. This method remains highly effective at minimizing mistakes on dissimilar (-) edges.

4. The Hybrid Approach and Round-or-Cut

The final 1.73 bound is achieved through a hybrid strategy. The authors demonstrate that the weaknesses of set-based rounding (dissimilar edges) are the strengths of pivot-based rounding, and vice versa. By balancing these two methods, they achieve a significantly tighter overall approximation. To manage the computational complexity of the LP, they employ a "round-or-cut" framework, iteratively refining the solution by either finding a valid clustering or adding mathematical constraints (cuts) to the LP.

Theoretical Results

This work provides a mathematical proof for a $(1.73 + \epsilon)$-approximation for Correlation Clustering, applicable to any input graph. This represents a drastic improvement over the previous state-of-the-art of 1.994.

While the algorithm is proven to run in polynomial time ($n^{O(1/poly(\epsilon))}$), it is primarily a theoretical contribution. The use of the Sherali-Adams hierarchy and the ellipsoid method suggests that the constant factors in the running time are currently too high for practical application on massive real-world datasets, such as social networks with millions of nodes.

Conclusion and Future Directions

By successfully isolating rounding errors through preclustering, this paper moves the field past a long-standing roadblock. It demonstrates that the Sherali-Adams hierarchy is a potent tool for Correlation Clustering when combined with the right structural analysis.

Future research may focus on developing more efficient, perhaps combinatorial, algorithms that achieve the 1.73 ratio without the heavy computational machinery of high-order LP hierarchies. Additionally, the authors suggest that the 1.73 ratio may be a limitation of the current analysis rather than the hierarchy itself, leaving open the possibility of reaching a 1.5-approximation or better in the future.

Summary updated

BibTeX
@inproceedings{cohenaddad2023handling,
  author = {Vincent Cohen-Addad and Euiwoong Lee and Shi Li and Alantha Newman},
  title = {{Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering}},
  booktitle = {FOCS},
  year = {2023},
  doi = {10.1109/focs57990.2023.00065},
}
Figure