Pivot based correlation clustering in the presence of good clusters
David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan · 2026
Read Pivot based correlation clustering in the presence of good clusters by David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12052.txt.
Introduction
Lolck, Thorup, and Yan sharpen a classic pivot method for correlation clustering. The classic algorithm earns a factor of three, and known tight cases rest on very good clusters. Their twist strips out all good clusters before each pivot step runs. That change pushes the proven approximation ratio just below three. Tests on synthetic data also look strong. The method beats both the classic pivot algorithm and the routine that locates good clusters.
Catalog record
| CREATOR | David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68351 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12052
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pivot based correlation clustering in the presence of good clusters David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan Abstract The classic pivot based clustering algorithm of Ailon, Charikar and Chawla [JACM’08] is factor 3, but all concrete examples showing that it is no better than 3 are based on some very good clusters, e.g., a complete graph minus a matching. By removing all good clusters before we make each pivot step, we show that this improves the approximation ratio to 2.9991 2.9991 . To aid in this, we also show how our proposed algorithm performs on synthetic datasets, where the algorithm performs remarkably well, and shows improvements over both the algorithm for locating good clusters and the classic pivot algorithm. 1 Introduction Correlation clustering is a fundamental clustering problem. The problem is modelled on an unweighted, undirected graph G=(V,E) , where the vertices correspond to the objects that are being clustered while the edges are pairwise similarity statements. In this setting, a clustering is then a partitioning of the graph, and how good a clustering is, is given by the number of pairs of vertices sharing an edge that was put in different clusters plus the number of pairs of vertices that was put in the same cluster without sharing an edge. 1 1 1 In some literature on correlation clustering it is common to model this problem as a complete graph, where each edge is labelled with either + or - . The two versions are equivalent, though since we are dealing with near-linear running times in the number of edges, the first formulation is in our case more advantageous as + and - edges start to lose the symmetry in their meaning to the algorithm. 1.1 Prior work The problem of correlation clustering was first introduced by Bansal, Bloom and Chawla [ 3 ] . They gave a constant approximation to this problem. This was since improved by Ailon, Charikar and Newman [ 1 ] who presented a 3 -approximate combinatorial linear time algorithm, called the pivot algorithm and a 2.5 -approximate LP-based algorithm. The pivot algorithm in particular has had a lot of influence on the development of algorithms for correlation clustering due to its simplicity. The algorithm works by randomly selecting a vertex, called the pivot, and then clustering it and all of its neighbours together. Then repeat on the remaining graph. Following the work of [ 1 ] , Chawla, Makarychev, Schramm, and Yaroslavtsev gave a near-optimal rounding for the standard LP relaxation achieving a 2.06 approximation [ 7 ] . More recently, Cohen-Addad, Lee, and Newman broke the integrality barrier of 2 for the standard LP by leveraging a constant number of rounds of the Sherali–Adams hierarchy, obtaining an (1.994+\varepsilon) -approximation [ 10 ] . Very recently, Cohen-Addad, Lee, Li, and Newman further improved the approximation guarantee to 1.73 via new rounding ideas based on preclustering and handling correlated rounding error [ 9 ] . After this work, a new LP framework was introduced by Cao, Cohen-Addad, Lee, Li, Newman, and Vogl, called the cluster LP , which lead to an approximation ratio of 1.485+\varepsilon [ 6 ] , which is the currently best known approximation ratio. In addition to the work on the approximation ratio, there have also been a lot of work on the running time of the clustering algorithms. A lot of the previous works that improved the approximation ratio has been focused on LP-based approaches, where running times are only really considered in-so-far they are polynomial. That said, there have been significant progress in this direction. Initially, the original pivot algorithm [ 1 ] trivially had a running time of O(m) with a 3 -approximation. A different algorithm was subsequently presented by Assadi and Wang that achieved a constant approximation ratio in sublinear time O(n\log^{2}n) . Building on this algorithm as a preprocessing step, an 1.847+\varepsilon approximate solution in time O(n\log^{2}n) was presented by Cohen-Addad, Lolck, Pilipczuk, Thorup, Yan and Zhang [ 11 ] . Finally, the authors of [ 4 ] showed that it is possible to match the best known approximation ratio of 1.485+\varepsilon even in the sublinear time setting. The problem however with the more recent results [ 11 , 4 ] is that while from a theoretical perspective, they achieve these results under some very high constant terms and exponential dependencies on \varepsilon , making them unsuitable for practical applications. So from this perspective, from the results so far presented, the pivot algorithm is the most practical algorithm so far presented in this paper from the perspective of theoretical guarantees. 1.2 Technical Overview In this work, we will be looking at presenting a new algorithm for correlation clustering, which both has a nice approximation ratio in theory while also performing well in practice. The way we will do this is by showing an algorithm which can be seen as a combination of the pivot algorithm by [ 1 ] which is a 3 approximation, and the atom-based clustering algorithm by [ 8 ] , which is only a constant approximation. The goal is to use the clusters that the atom-based clustering algorithm would find, but further process them such that we also include some vertices that belong to these clusters. Whenever we are unable to find any atoms, we will instead run a step of the pivot algorithm to proceed with the clustering. We will show that by combining these two algorithms, it is possible to get an algorithm that is better than each of them individually. Theorem 1 . Algorithm 1 is a 2.9991 approximation in time O(m\log n) . The reason why such a result is achievable is that the pivot algorithm and the atom-based algorithms have very different worst-case inputs. The pivot algorithm in general performs poorly on input where the input closely resembles disjoint cliques, with a couple of edges either added or removed sparsely. This is exactly the setting where the atom-based algorithm is able to locate atoms. Algorithm 1 Merge of pivot and atom-finding 1: Q \leftarrow \emptyset \triangleright Q is a multiset 2: for v\in V do 3: Add q(d(v)) copies of v to Q 4: while G is not empty do 5: if \exists v\in Q then 6: Remove v from Q . 7: Try to find a good cluster K near v ( Section 4 ) 8: if a good cluster K is found then 9: Construct a cluster C based on K ( Section 5 ), and remove C from G 10: else 11: Construct a cluster C by a normal pivot step ( Section 3 ), and remove C from G 12: if a cluster C was removed then 13: for e=(u,v)\in E with u\in C,v\not\in C do 14: Add p(d(v)) copies of v to Q The analysis we will follow will be based on the fact that after each operation we do, we can bound the ratio between the cluster we remove and the decrease of cost in the optimal solution after removing the cluster in expectation. This is the standard method that is typically used to analyse a lot of clustering algorithms. For this result, we need two notions of goodness for clusters, generally