Research map / Learning theory and algorithms / Clustering
Correlation Clustering Beyond the Pivot Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Breaks the 3-approximation barrier for correlation clustering by locally modifying the Pivot output (moving vertices to singletons or to pivot clusters with subsampling), and shows the modified algorithm can be maintained in polylogarithmic time per label flip in the fully dynamic setting.
Problem
Correlation clustering has a 3-approximation barrier for the Pivot algorithm; it was open whether a (3-Ω(1))-approximation can be maintained in fully dynamic settings with polylogarithmic update time.
Approach
A ModifiedPivot algorithm that runs Pivot but locally moves dissimilar neighbors to singleton clusters and subsampled non-neighbors with similar neighborhoods into the pivot's cluster, analyzed via a fractional bad-triangle charging scheme with width below 3 and implemented via the dynamic randomized greedy MIS data structure.
Key results
- ModifiedPivot achieves an approximation factor below 3 (about 2.997 per the parameter analysis) in expectation for correlation clustering.
- The output can be maintained in polylogarithmic expected update time per label flip in the fully dynamic model against an oblivious adversary.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add local moves that send selected vertices to singleton clusters or the pivot's cluster | Pivot · Correlation clustering | approximation ratio: 3 -> <2.997 | Helped |
| Move dissimilar neighbors to singleton clusters | ModifiedPivot · Two disjoint cliques connected by one edge | expected cost: 3 -> 2 | Helped |
| Move selected non-neighbors with similar neighborhoods into the pivot's cluster | ModifiedPivot · Complete graph with one non-edge | expected cost: 3 -> null | Helped |
| Maintain the locally modified clustering after label updates | ModifiedPivot · Fully dynamic correlation clustering | approximation ratio: 3 -> (3-\Omega(1)) | Helped |
Limitations
- Approximation improvement is only marginal (below 3, about 2.997) and not optimized by the authors.
- Guarantee holds in expectation and against an oblivious adversary.
Experimental setup
Metrics: expected approximation ratio update time
Baselines: Pivot
Builds on: Pivot algorithm BDHSS fully dynamic correlation clustering
Closest papers by meaning
- Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! (NeurIPS 2023 · similarity 0.93)
- Atoms and Pivot Based Correlation Clustering (NeurIPS 2026 · similarity 0.92)
- Sparse-pivot: Dynamic correlation clustering for node insertions (ICML 2025 · similarity 0.89)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.87)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.87)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.