# Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 23 May 2023.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Correlation Clustering in Data Streams](https://mlsanity.com/paper/1812.02023/) (2018)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Fast Combinatorial Algorithms for Min Max Correlation Clustering](https://mlsanity.com/paper/2301.13079/) (2023)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [Almost 3-Approximate Correlation Clustering in Constant Rounds](https://mlsanity.com/paper/2205.03710/) (2022)
- [Improved Approximation for Fair Correlation Clustering](https://mlsanity.com/paper/2206.05050/) (2022)
- [Min-Max Correlation Clustering via MultiCut](https://mlsanity.com/paper/1907.00117/) (2019)
- [Massively Parallel Correlation Clustering in Bounded Arboricity Graphs](https://mlsanity.com/paper/2102.11660/) (2021)
- [Tight Analysis of Randomized Greedy MIS](https://mlsanity.com/paper/1707.05124/) (2017)
- [Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ℓp-Distances](https://mlsanity.com/paper/1710.01431/) (2017)
- [Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover](https://mlsanity.com/paper/1802.08237/) (2018)

## Built on by (most cited first, 8 of 8)

- [Free and Customizable Code Documentation with LLMs: A Fine-Tuning Approach](https://mlsanity.com/paper/2412.00726/) (2024)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [MM-PoE: Multiple Choice Reasoning via. Process of Elimination using Multi-Modal Models](https://mlsanity.com/paper/2412.07148/) (2024)
- [CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Median](https://mlsanity.com/paper/2505.11725/) (2025)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)
- [Is Sliding Window All You Need? An Open Framework for Long-Sequence Recommendation](https://mlsanity.com/paper/2604.12372/) (2026)
- [Inductive Correlation Clustering with Graph Neural Networks](https://mlsanity.com/paper/2608.27153/) (2026)

## Abstract (arXiv)

We show that a simple single-pass semi-streaming variant of the Pivot algorithm for Correlation Clustering gives a (3 + ε)-approximation using O(n/ε) words of memory. This is a slight improvement over the recent results of Cambus, Kuhn, Lindy, Pai, and Uitto, who gave a (3 + ε)-approximation using O(n log n) words of memory, and Behnezhad, Charikar, Ma, and Tan, who gave a 5-approximation using O(n) words of memory. One of the main contributions of this paper is that both the algorithm and its analysis are very simple, and also the algorithm is easy to implement.