Correlation Clustering Beyond the Pivot Algorithm
Authors: Soheil Behnezhad
Moses Charikar
Vincent Cohen-Addad
Alma Ghafari
Weiyun ma
Venue: ICML 2025 poster (2025)
Keywords: Correlation Clustering
Primary area: general_machine_learning->clustering

Abstract: We study the classic correlation clustering problem. Given $n$ objects and a complete labeling of the object-pairs as either “similar” or “dissimilar”, the goal is to partition the objects into
arbitrarily many clusters while minimizing disagreements with 
the labels.

A classic Pivot algorithm for this problem, due to [Ailon et al STOC'05], obtains a 3-approximation for this problem. Over the years, this algorithm has been successfully implemented in various settings. The downside of the Pivot algorithm is that the approximation analysis of 3 is tight for it. While better approximations have been achieved in some settings, these algorithms are often hard to implement in various settings. For example, [Behnezhad et al FOCS19] showed that the output of Pivot can be maintained in polylog time per update in a dynamic setting, a bound that was improved to constant by [Dalirrooyfard et al ICML'24]. But obtaining a better approximation remains open.

In this paper, we present Modified Pivot, an algorithm that locally improves the output of Pivot. Our Modified Pivot algorithm can be implemented just as efficiently as Pivot in various settings. Our experiments show that the output of Modified Pivot on average makes less than 77\% of the mistakes made by Pivot. More surprisingly, we prove theoretically that Modified Pivot has approximation ratio $3-\epsilon_0$ for some absolute constant $\epsilon_0 > 0$. This, e.g., leads to a better than 3 approximation in the dynamic setting in polylog time, improving the 3-approximation obtained by [Behnezhad et al FOCS'19] and [Dalirrooyfard et al ICML'24].

Correlation Clustering Beyond the Pivot Algorithm
Soheil Behnezhad
Moses Charikar Vincent Cohen-Addad *3
Alma Ghafari Weiyun Ma
Abstract
1. Introduction
We study the classic correlation clustering prob- lem. Given n objects and complete labeling of the object-pairs either "similar" or "dissimilar", the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels.
Correlation clustering is a quintessential problem in data analysis, machine learning, and network science, where the task is to cluster set of objects based on pairwise rela- tionships. Each pair of objects is labeled as either "similar" or "dissimilar," and the goal is to produce clusters that best align with these labels. Formally, given n vertices and their pairwise labels, the task to partition them into arbitrarily many clusters so as to minimize the number of dissimilar labels inside clusters plus the number of similar labels that go across clusters. This problem has applications for various tasks such image segmentation (Kim et al., 2014), com- munity detection (Shi et al., 2021), disambiguation tasks (Kalashnikov et al., 2008), automated labeling (Agrawal et al., 2009; Chakrabarti et al., 2008), and document cluster- ing (Bansal et al., 2002), among others.
A classic PIVOT algorithm for this problem. due to Ailon et al. (STOC'0S), obtains a 3- approximation for this problem. Over the years, this algorithm has been successfully implemented in various settings. The downside of the PIvoT algorithm is that the approximation analysis of 3 is tight for it. While hetter approximations have been achieved in some settings, these algo- rithms are often hard to implement various set- tings. For example, Behnezhad et al. (FOCS' 19) showed that the output of PIvOT can be main- tained in polylog time per update in dynamic setting, bound that was improved to constant by Dalirrooyfare fard et al. (ICML'24). But obtaining a better approximation remains open.
The correlation clustering problem was introduced by Bansal, Blum, and Chawla (2002; 2004), who showed that (large) constant approximation can be achieved in polyno- mial time. There has been series of polynomial-time algo- rithms improving the approximation ratio (Charikar et al., 2003; Ailon et al., 2005; 2008; Chawla et al., 2014; Cohen- Addad et al., 2022; 2023), with the current best known being the 1.437-approximation by Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (2024). It also known that the problem is APX-hard (Charikar et al., 2003).
In this paper, we present MODIFIEDPIVOT, an al- gorithm that locally improves the output of PIVOT. Our MODIFIEDPIVOT algorithm can be imple- mented just efficiently PIvoT in various settings. Our experiments show that the output of MODIFIEDPIVOT on average makes less than 77% of the mistakes made by PIVOT. More sur- prisingly, we prove theoretically that MODIFIED- PivoT has approximation ratio Eg for some absolute constant Eo > 0. This, e.g., leads to a better than approximation in the dynamic setting in polylog time, improving the 3-approximation obtained by Behnezhad et al. (FOCS'19).
The 3-Approximation Barrier
A particularly simple and influential algorithm for correla- tion clustering is the PivoT algorithm of Ailon, Charikar, and Newman (2005). The PIVOT algorithm is remarkably simple: it picks random vertex clusters it with vertices that are similar to v, then removes this cluster and recurses on the remaining vertices.
In (Ailon et al., 2005), was shown that PIVOT obtains a 3-approximation for correlation clustering. Thanks to its simplicity, variants of the PIvOT algorithm have been ef- ficiently implemented in various models, leading to 3- or almost 3-approximations. Examples include the fully dy- namic model with polylogarithiic (Behnezhad et al., 2019) or constant Dalirrooyfard, Makarychev, and Mitrovic (2024) apdate-time, constant rounds of the strictly sublinear mas- sively parallel computations (MPC) model -Cohen-Addad
Equual contribution Northeastern University Stanford University 'Google Research. Correspondence to: So-
heil Behnezhad <ssbehnezhaad @ northeastern.edus Moses
Charikar moses @ cs. taaanooddddu>..... Vincent Cohen-
Addad <vcohenad @ gomi, Alma Ghafari <gha-
fari.m menothhestern..cdu Weiyun Ma < wyma@ sdanford.edu>..
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Correlation Clustering Beyond the Pivot Algorithm
al., 2021; Assadi & Wang, 2022; Behnezhad et al., 2022), single-pass of the semi-streaming model (Cambus al., 2024; Chakrabarty & Makarychev, 2023), distributed local and congest models (Behnezhad et al., 2022), and the classic RAM model where PIVOT takes linear-time to implement.
2. Our Techniques
In this section, we describe the informal intuition behind our new MODIFIEDPIVOT algorithm.
As standard, we model the input to correlation clustering as a graph G = (V, E) with the vertex set V corresponding to the objects and the edge-set E. representing the similar labels. In particular, an edge (u, v) E E implies u and v are similar and a non-edge (u, u) & E implies u and v are dissimilar.
Unfortunately, the 3-approximation analysis of the PIVOT algorithm is tight. That is, there are various inputs on which the PIVOT algorithm does not obtain any better than a 3- approximation. Because of this, and the fact that all better approximations require solving large linear programs, the 3-approximation has emerged as barrier for correlation clustering in various settings. In the case of dynamic inputs, for example, the following problem has remained open for more than 5 years since the paper of (Behnezhad et al., 2019):
It would be useful start with the PIVOT algorithm and discuss few examples on which it only obtains a 3- approximation. We will then discuss how MODIFIED- Pivor overcomes all of these examples and breaks the 3-approximation barrier.
Open Problem Is it possible to maintain a (111)
With the graphic view discussed above, the PIvor algorithm works as follows. It iteratively picks a vertex e, clusters u with its remaining neighbors, then removes this cluster from the graph. This continues until all vertices are removed.
approximation of correlation clustering in log ((1) n time per update?
We note that the problem above has been open even if one allows a much larger update-time of, say, linear n.
Problem 1: PIvoT Clusters Dissimilar Pairs. Our first example shows a scenario where the PIVOT algorithm, mis- takenly, clusters together vertices that have very different neighborhoods. Such mistakes alone cause the PIVOT algo- rithm to pay 3 times the optimum cost in these examples.
Our Contribution
We show how to break the 3-approximation bound by intro- ducing a new algorithm, MODIFIEDPIVOT, which we for- malize as Algorithm 1. Our algorithm modifies the output of PIVOT by locally moving some vertices to other existing clusters new singleton clusters. We present an analysis showing that this modification does indeed improve the ap- proximation to below 3. Importantly, our criteria for these local moves is extremely simple. This allows the MODI- FLEDPIVOT algorithm to be implemented as efficiently as the pivot algorithm in the dynamic setting.
Consider a graph composed of two disjoint cliques each on n/2 vertices connected by edge (u, e). The optimal solution is to put the two cliques in disjoint clusters, paying only a cost of one for the edge (u, v). In fact, this is exactly the clustering that PIVOT reports so long as its first PivoT is not one of the endpoints of the edge (u, v). However, one of the endpoints of the edge (u, 2) is selected as the first pivot, then the algorithm puts and v in the same cluster, paying a cost of 2. The figure below illustrates this. On the left hand side, we have the optimal clustering. On the right hand side, we have the output of PIVoT if one of the endpoints of the edge connecting the two cliques is picked as a pivot.
Theorem 1.1 (Fully Dynamic). There is an algorithm that maintains a 2. 2.99-approximatt correlation clustering by spending (poly log n) time per label update against an oblivious udversary. The bounds on the update-time and the approximation hold in expectation.
The proof of the Theorem 1.1 appears in Appendix B Theo- rem 1.1 resolves Open Problem 1.
We also implement MODIFIEDIIVOT and compare its out- put with PIVOT on various publicly available data sets. Our empirical data suggests that MODIFIEDPIVOT makes less than 77% of the mistakes made by PIvOT on average. See Section 6.
Note that the probability that one of u or e chosen as the first pivot is 2/n, therefore, the expected cost of Pivor in this example is
We also note that an independent work of (Cohen-Addad al., 2024) proposes a correlation clustering algorithm that obtains a better than 3-apprxximation which can be implemented in some settings (such as sublinear time). But it is unclear if the same algo- rithm be implemented in the dynamic setting. The techniques in the two papers are very different.
Prffirst pivot & {u, (1) + Prr ffistt pivot E {u, w)](n 2)
2 (n 10-2) 2) بب + 3,
(1 2/n)
n
n=000
2

---

Correlation Clustering Beyond the Pivot Algorithm
which is 3 times the optimum cost.
the PIVOT algorithm does too, except when the first pivot chosen one of the endpoints of the non-edge. In this case. the other endpoint of the non-edge will be put in singleton cluster, resulting in cost of n 2 as illustrated in the figure of the right hand side.
Fixing Problem 1: Moving Dissimilar Neighbors to Sin- gleton Clusters. Our idea for tixing Problem I is a natural one. Whenever our MODIFIEDPIVOr algorithm picks pivot v, we do not necessarily put all of its remaining neigh- bors in the cluster of U. Instead, if neighbor u of v has a very different neighborhood than v, we move it to a single- ton cluster. More formally, for some small constant 8 >> O, we first define the set D. to include neighbors of such that (w) n N()) X (u), where N (x) denotes the neighbor-set of vertex x in the current graph. Note that for sufficiently small 8, vertex u E Dy has non-edges to nearly all neighbors of so it can only improve the cost if we move such vertices to singleton clusters.
Note that the expected cost is 3 times the optimum cost of I in this case too, since:
Pr Prfsirst pivot & v)](1 (first pivot E {u, 2)]
2
= (1 - 2/n) + nn 22 3.
710000
Fixing Problem Moving Non-Neighhors Pivot's Cluster. To fix Problem 2, whenever we pick a pivot v, would like to identify set A, of non-neighbors of whose neighborhoods are similar to ((r) and move them to the cluster of u as well.
The problem with doing so is that the set Ag may be too large, and moving them to the cluster of will completely change its structure. This best described via an example. Consider a complete bipartite graph with vertex parts Vi, V/ where 1/2 > |V/|- Here the solution that puts all vertices in singleton clusters pays cost of [V/ [V2]. Therefore, OPT < |V/]- - [V/]. But now take the first pivot v, which with probability [VSI((IVI+ + V/2)
Let us now run this modified algorithm on the example of Problem 1. As before, if the first pivot is not one of the endpoints of (u, v). then the algorithm returns the optimal solution with a cost of 1. But now one of the endpoints of (u, v) is picked as the first pivot, the other endpoint will move singleton cluster. It can be confirmed that the cost is only n in this case. Therefore, the expected cost of the algorithm in this case will now be improved to 2 since
- o(1) belongs to the larger part 1/2 Now note that all the rest of vertices in 1/2 will have exactly the same neighborhood as v. Moving them all to the cluster of results in clustering all the vertices of the graph together, resulting in cost of (1% + (Vaa) for the non-edges inside V1 and V/2. The approximation ratio will then be at least
Pr[first pivot & (11) + Pr[first pivot E (n/)))
(12)))
(KE)) VS2
(12) VI
1/21 - w(1). 2
2 = (1-2/n) + (n/2) < 2.
In other words, not only moving similar neighbors to the cluster of the pivot does not improve the approximation to below 3, but worsens it to super-constant.
Problem 2: PIVOT Separates Similar Pairs. It turns out that moving vertices to singleton clusters not enough. Our next bad example for the PIVOT algorithm shows a scenario where the PivoT algorithm, mistakenly, separates vertices that have to be clustered together, causing it to pay times the optimum cost.
To fix this problem, we do not move all the vertices in Ag to the cluster of v. Instead, we subsample some | (v)) vertices in A, and only move these vertices to v's cluster. It is important to note that in case [N(v) < [A,]] as is the case in the complete bipartite example, we only move o(1) fraction of the vertices of A, to the cluster of v. Had this been a constant, our analysis would have been much simpler. However, we will need a much more global analysis to argue
Consider a graph on n vertices where all pairs are edges except one pair (u, v) which is a non-edge. The optimum solution here is to put everything in the same cluster, paying only a cost of one for the non-edge. This is exactly what
3

---

Correlation Clustering Beyond the Pivot Algorithm
that in case Ag is much larger than N(v), then the output of PIVOT is already better than 3-approximate.
3. The MODIFIEDPIVOT Algorithm
Our MODIFIEDPIVOT algorithm is formalized below as Algorithm 1. We emphasize that, the time complexity of MODIFIEDPIVOT algorithm and the PivOT algorithm are the same once the parameters of the algorithm are fixed.
Up to this point, we've presented a number of instances where the approximation ratio of the PivoT algorithm is no better than 3. We've ve also explored some local improvements that would improve the approx- imation on these instances. What remains to show is that these local improvements do indeed beat 3-approximation on all inputs.
The Final Analysis:
Let us provide some intuition about MODIFIEDPIVOT Simi- lar to PIVOT, it iteratively picks a random pivot v, and based on it identifies the following sets:
Cp: This is the set of neighbors of still in the graph plus vertex v itself. This is exactly the cluster that PIVOT would output for v, but we will modify it.
Our analysis follows the standard framework of charging mistakes on bad triangles, but has an important twist. As standard, we say three vertices {u, v, w) form a bad triangle if exactly two of the pairs {u, v), {u, w), {v, w) are edges. It's important to note that regardless of how these vertices are clustered, at least one pair within bad triangle must be incorrectly clustered. Consequently, if we can identify 3 edge-disjoint bad triangles within G. then we can infer that the optimum cluster cost is at least B. This holds even if we identify a fractional packing of bad triangles (Ailon al., 2005). This naturally provides a framework for analyzing the approximation ratio of correlation clustering al algorithms, where the mistakes made by the algorithm are blamed on bad triangles. The crux of the analysis will then be focused on formalizing the charging scheme, i.e., which triangle to charge for each mistake and analyzing how many times each pair (edge or non-edge) is charged.
De: These are vertices that belong to C, but have very different neighborhood than C., Intuitively, we would like to move vertices of D, to singleton clusters instead of putting them in the cluster of v.
D' This is a subsample of D,. Instead of moving all vertices of D, to singleton clusters, we only move vertices of D to singleton clusters to make sure that the cluster of does not dramatically differ from C. in size.
Ag: These are vertices that are not adjacent to the pivot v. but their neighborhoods are almost the same as C... Moving each of these vertices to C, will improve our cost, provided that we do not move too many of them inside.
The charging scheme used for the PIVOT algorithm by (Ailon et al., 2005) is highly local, in the sense that it charges any mistake to bad triangle involving this mistake. Our charging scheme (formalized as Algorithm 2) differs from this in two crucial ways:
A This is a subsample of Ay. We only move vertices of A', to the cluster of v to ensure, again, that the cluster of e remains relatively close to C, in size.
A: The set A is initially empty. Whenever we pick a pivot v, we move all the vertices of A, to A. We define this set because we do not want a vertex w to participate in A, and A,, for two different pivots u and v.
Charging triangles fractionally: Instead of charg- ing a single bad triangle integrally for each mistake, we charge various bad triangles fractionally. In other words, there is no one-to-one mapping between our mistakes and the triangles charged. Instead, we argue that sum of the charges to the bad triangles in total is as large as the mistakes we make (Lemma 4.5), and that sum of the charges involving each pair is not too large (Lemma 4.6).
The following observation shows that the output of MODI- FIEDPIVOT is a valid clustering. What remains is to analyze its approximation ratio, which we do in Section 4.
Observation The output of Algorithm 1 is always a valid clustering. That is, each vertex belongs to exactly one cluster of the output with probability 1.
Charging non-local triangles: When a pivot v is picked in our MODIFIEDPIVOT algorithm, unlike the analysis of (Ailon et al., 2005), we do not just charge bad triangles involving the pivot. For instance, in the example of the complete bipartite graph discussed above, we charge many bad triangles that do not in- volve the pivot. This is the key in our analysis to show that when A, is too large compared to Cv, the output of PivoT is already good.
Proof. First, observe that for every i, the set of vertices removed from V in the first i iterations of Algorithm is identical to the set of vertices clustered in the first itera- tions of PIvOT under the same random coin tosses. Since Algorithm 1 only removes a vertex from V if it has been clustered (either in the same iteration or an earlier iteration), this means that every vertex gets clustered at some point
4

---

Correlation Clustering Beyond the Pivot Algorithm
Algorithm 1 The MODIFIEDPIVOT algorithm.
Parameters: E (0, 1 8 [4x, k
A + 0.
while V *
Pick a vertex u E V u.a.r. and mark it as a pivol.
Let C. + [v] (()), where (2v) is the set of neighbors of still in V.
Let D, {u u (() and (M( n C.l 5 8| -1. 1}.
Let D' include mel [8|Co]]} vertices of D, uniformly at random.
Let A, : {w V C. and w & A and ACCl S e|C,1 1}.
Let A" include min(|Aul, []] vertices of A, uniformly at random.
Put each vertex (Dz A) U (Ap (A.) in singleton cluster.
Put all vertices of (C, U A()) \ (D' U A) the same cluster.
A A U A..
Remove vertices of C, from V. removed from V in this step and can be picked pivots later To clarify this, the vertices in A, will be allowed to be picked as pivots later on, but even if they start clusters they won't themselves be added to those clusters and will be put in singleton clusters.
We emphasize that even though vertices in A, get clustered here, they
in Algorithm 1. Moreover, if a vertex is clustered in some iteration of Algorithm 1, then it is either removed from V or added the set A the end of that iteration. Since Algorithm never clusters vertex that has been removed from or is already in A, this means that vertex cannot be clustered more than once. Thus Algorithm always outputs a valid clustering.
{a, (a,b), fa, c), {b, c} belongs to E. Let BT be the set of all bad triangles the graph.
Definition 4.3. Let A be a (possibly randomized) algo- rithm for correlation clustering. We say an algorithm S is a charging scheme width for A for every given output clustering C of A and every bad triangle t BT, algorithm S specifies real y1 such that:
4. Analysis of MODIFIEDPIVOT
Σ Vt 2 cost(C).
In this section, we analyze the approximation ratio of the MODIFIEDIIVT algorithm, proving the following theorem:
For every distinct u, v E V (which may or may not belong to E), holds that
Theorem 4.1. The clustering output by the MODIFIED- PIVOT algorithm has cost most 2.997 times the optimal cost in expectation.
Σ VI S.W.
EA
AE AETT
Remark 4.2. We note that we have not tried to optimize the approximation ratio in Theorem 4.1 as our main contribution the qualitative result that there is an algorithm maintaining the properties of the pivot algorithm while ensuring better approximation.
The following lemma shows why charging schemes useful.
Lemma 4.4. Let A be any (possibly randomized) correla- tion clustering algorithm. If there exists charging scheme of width for A, then for the clustering C produced by A,
The analysis still fits into the framework of charging bad triangles as in the original 3-approximation analysis of the PivoT algorithm (Ailon al., 2008). However, the triangles charged in our analysis are very different from (Ailon et al., 2008). We first provide the needed background on charging bad triangles in Section 4. 1, then formalize our analysis using this framework in Section 4.2.
Ex(cost(C)] S -pp((G.)..
Lemma 4.4 is a standard result in the literature and follows from a simple primal dual argument. See for example (Ailon et al., 2005) or (Behnezhad et al., 2022) for its proof.
4.1. Background on Charging Bad Triangles
4.2. Our Charging Scheme for Algorithm 1
Let us first overview the framework of charging bad tri- angles (Ailon et al., 2008). We say three distinct vertices {a, b, ef in V form a bad triangle if exactly two of the pairs
We formalize our charging scheme for MivI in Algorithm 2. Algorithm 2 proceeds exactly like MODIFIED- PIVOT and defines all the sets used by MODiFIEDPIVOT in
5

---

Correlation Clustering Beyond the Pivot Algorithm
Algorithm 2 Our charging scheme for MODIFIEDPIVOT. This algorithm is only used for the analysis of Algorithm 1.
1: Parameters: = E (0, 14 5 E [4x, k
2: A -0
3: while V +
4: Pick a vertex v E V uniformly at random and mark pivot
5:
C. + {v] (w)), where (v) the set of neighbors of still in
6:
D. [u] u E (v)) and (N) C $ 8 C -
7:
D' -ell []] vertices of Du u.a.r.
8:
A, (w I w E V Cv: 10 & A.IN(w))
I e|Crll -
9:
A + Aill [o]C vertices of A. u.a.r.
10:
for every (u, w) & E such that u, w E C.
if E D' and w & D then
V(o,uw))
else
14:
M(,,,w)) < 28/(1-35) (d)
15:
if [A. C/Cal then for every (u, w) E E where E Co, w E EVV Cv
16:
17:
if w E A then
18:
Do not charge a new triangle for (u, w)
19:
else
if w E Ag then
21:
22:
else if w E A, then
23:
if w E A then
24:
Moaaae) + 8
25:
else
26:
1 T
27:
else
28:
for every (u, w) E E where a E Co. w E V Cn
29:
w A then
Do not charge a new triangle for (u, w)
31:
else
32:
if Ag then VVauw 1
33:
34:
else
35:
V( 1 I-c
36:
for every bad triangle (u, w) such that u E N(v), w, E An, (w,x) $ F,, (u, E
(1/(1-5) 14.-1
38:
A + AUA,
39:
Remove vertices of C, from
40:
Output
forming its clusters. However, instead of returning clus-
that
tering, Algorithm returns a charge yt 2 0 for each bad triangle i BT. By proving Lemma 4.5 Appendix A.
Σ ye 2 cost(C). ME BT
we show that Algorithm 2 charges as many bad triangles as the cost paid by MODIFIEDPIVOT.
We then in Appendix A.2 prove Lemma 4.6 that shows Algorithm has width at most 2.997.
Lemma 4.5. Let y be the vector of charges returned by Algorithm and let C be the corresponding clustering re- turned by MODIFIEDPIVOT (Algorithm 1). Then it holds
Lemma 4.6. Let y be the charges returned by Algorithm
6

---

Correlation Clustering Beyond the Pivot Algorithm
For every pair (a, b) of vertices,
is clustered. If itself is a pivot, then elim(v) v.
EA [M(..)]] - 2.997.
(=) == {u E Nuu) =(elim(u)) S x ((elim(v)) Intuitively, these are the neighbors of v clustered no
Combining these lemmas and plugging them into Lemma 4.4 proves Theorem 4.1 that MODIFIEDPIVOT ob- tains a 2.997-aprroximation
later than v. The algorithm stores N (w) in a balanced binary search tree where each vertex is indexed by x =(elim(u)).
Let us start with some intuition on the type of bad triangles we charge based on the sets created in Algorithm 1, and how much we charge each triangle such that it satisfies two properties. First, the total charge of bad triangles is more than the cost of the algorithm, and second, each pair of vertices is charged at most by the approximation guarantee.
(*) = {u E N(u) <(elim(u)) 2 =<elim(v))) These are neighbors of clustered no sooner than v. The algorithm stores (+) in a BST indexed by the static vertex IDs.
Lemma 5.1 (Lemma 4.1 of (Behnezhad et al., 2019)). Let
A be the set of vertices whose pivot changes after inserting or deleting an edge (a, b). There is an algorithm to update all the data structures above in time
Note that, to charge a pair, we need to blame on bad triangle. To identify these costs in the proof of Lemma 4.5, at some iteration of the Algorithm I we go over all pairs with disagreement, that are distinguished based on C, D. A', A' sets corresponding to the pivot of that round. We assign a set of bad triangles to these disagree- ments, such that the charges on the bad triatngles cover the cost of disagreement.
ō (141- -iimin min min( mi)
Combined with the following lemma also proved in (Behnezhad et al., 2019), this implies that all the data struc- tures can be updated in polylogarithmic time.
The last step of the analysis is to show that, each pair is charged at most 2.997. To do so, for a given pair of vertices we need to go over all the bad triangles that is charged and contains this pair. This separates the analysis to different cases based on the choice of the pivot.
Lemma 5.2 (Lemma 5.1 of (Behnezhad al., 2019)). Let A be in Lemma 5.1. It holds for every X E (0, 1] that
1
E | min()((a)
X
O(log n).
5. Implementation in the Fully Dynamic Model
These two lemmas combined, imply that the update- time is polylogarithmic in expectation. We prove the following claims in Appendix B.
In this section, we prove Theorem 1.1 that a (3 --(1)- approximation of correlation clustering can be maintained by spending polylogarithmic time per update. Our starting point is the algorithm of Behnezhad, Derakhshan, Haji- aghayi, Stein, and Sudan (2019) which maintains a random- ized greedy maximal independent set, or equivalently, the output of the PivoT algorithm in polylogarithmic time.
Claim 1. Take vertices u and such that v is pivot and π (e) 2 (u)) Having access to the data structures above stored by (Behnezhad et al., 2019), it is possible to determine the values of (N) n Czl and AN, exactly in Ollo n) time.
For any vertex v, we draw real (v) from [0, 1] uniformly and independently. We say क (v) is the rank of v. Recall that the PIvoT algorithm iteratively picks pivot uniformly from the unclustered vertices and clusters it with its unclustered neighbors. Instead of doing this, we can process the vertices in the increasing order of their ranks, discarding vertices encountered that are already clustered. The resulting cluster- ing is equivalent. We can do the same for MODIFIEDPIVOT as well. Namely, each iteration of the while loop in Algo- rithm I picks the vertex in V with the smallest rank. Again, the resulting clustering is equivalent.
Proof of Theorem I.I. In addition to the data structures maintained by the algorithm of (Behnezhad al., 2019), for each vertex and each S E {C, D, D', A, A'), we store pointer Is(u) which takes the value of either a vertex v or I. If Is (u) = this implies that u E S.. If Is(u) =T, then u g S. for any v. For instance, if ( = v, we get that u E D'. Note that by having these pointers, we can also immediately maintain the sets D,, D',, A., A', for each pivot v. To do so, whenever Is(u) changes from v to v', we delete u from S, and insert it to S This can be done in O time by storing these sets as BSTs.
Background on the algorithm of (Behnezhad et al., 2019): The algorithm of (Behnezhad et al., 2019), for each vertex v maintains the following data structures dynamically:
Claim 2. The data structures (u), (u), Ia(u), (u) and L (w) can be maintained in
m) time.
This wraps up the discussion on how we efficiently maintain our data structures. Having all the sets C., D,, D', Au, A'
elim(r): This represents the pivot by which vertex v
7

---

Correlation Clustering Beyond the Pivot Algorithm
Average and Ausiccas Visggeement 'ar tnd fied rious Uniided by Heee
Aestage and Warkkhese Jhas sumertia Nodiiia Hies Unrieed by Plw.
PARINO NIgH CANA
Woral Cope
Figure 1. The x-axis of this plot represents each dataset. Note that disagreements of MODIFIEDPIVOT over Pivor less than I, that shows the improvement of our algorithm compared to PIVOT.
Figure 2. The x-axis of this plot represents stochastic block models with vertices and j clusters as i.
maintained explicitly, we can also maintain the cluster of each vertex formed by Algorithm 1 in polylogarithmic time, concluding the proof of Theorem 1.1.
specific number of nodes. The probability of edge be- tween two nodes within the same cluster is denoted as Pins while the probability of an edge between nodes in different clusters is Pout- The steps are as follows: Partition the set of nodes into & disjoint subsets representing clusters. For each pair of nodes within the same cluster, add an edge with prob- ability pin- For each pair of nodes in different clusters, add edge with probability Pout- By setting Pin sufficiently large and Pout small, we have dense and separable clusters. In our experiments, we set Pin = 0.1 and Pout 0.9.
6. Empirical Results
In this set of experiments, we compare the objective values of PIVOT and MODIFIEDPIVOT algorithms,, ensuring that both utilize the same randomness for the ordering of pivots.
Dataset The first set of data consists of selected graphs, which represent rife- applications in (Davis & Hu, 201 I). Our dataset is a selection that covers the following cate- gories: communication networks (email), collaboration net- works (Erdos991, Netscience), citation networks netaor,,,SmaGri,, biological networks (celegans-neurge and others (Harvard500, polblogs). Furthermore, this dataset has been featured in other studies on correlation clustering (Veldt, 2022; Veldt et al., 2018).
An optimal correlation clustering algorithm should ideally cluster all nodes within the same block into a single cluster. In these scenarios, PIVOT often fails to achieve this, produc- ing suboptimal clusters. PIVOT does not prune the neighbors of the chosen pivot between to blocks and misses portion of nodes inside each block.. In contrast, MODIFIEDPIVOT has the strategy to overcome both of this cases.
gelegans-meetbolle
6.1. Experiments
In most of these graphs, we observe that PIVOT outputs small clusters while ignoring vertices that have a similar neighborhood to the cluster. MODIFIEDPIVOT, however, accounts for these vertices by allowing them to join the cluster when they have sufficiently similar neighborhood.
For these experiments, we generate multiple permutations of vertex orderings to simulate different sequences in which pivots are selected. We emphasize that multiple random seeds per experiment have been used. For each permutation, we select values in the range [0.3, 0.8] for the parameters and 8. For each combination of and 5, we compute the clustering produced by MODIFIED and calculate its disagreements. We tested at most 8 choices for each of epsilon and delta in all the runs, which adds up to at most 64 combinations. We identify the parameter combination (s and ō) that yields the minimum disagreements for that specific permutation. We record the best parameters, the resulting clustering, and the corresponding disagreement
By increasing the parameter e and consequently expanding the size of the A,, set, these sparse instances tend to exhibit smaller objective values. This demonstrates the ad advantage of MODIFIEDPiVOT in handling sparse real-world graphs.
Stochastic Block Models As a benchmark for dense graphs, we use Stochastic Block Models (SBM). To generate an SBM, we define i clusters (or blocks), each containing
8

---

Correlation Clustering Beyond the Pivot Algorithm
values. Experiments in Figures and showcase the aver- age and worst-case performance of MODIFIED over PIVOT across all permutations that highlight improvements by MODIFIEDPIvOT over PIvOT. Note that in the plots, values less than represent the number of disagreements of MODIFIEDPIVOT is less than that of PIVOT.
In certain permutations, PIVOT can make drastic mistakes by creating poorly formed clusters (see the example Section 2). In contrast, PIvo has the flexibility to account for such bad permutations by adjusting the clusters of pivot, that is more amplified by adjusting the parameters and By doing so, MODIFIEDPIVOT accounts for the effects of an unfavorable pivot ordering, resulting in better cluster formations and significantly reduced disagreements. This adaptability highlights the robustness of MODIFIEDPIVOT compared to PIVOT, which is visualized in Figures and 2 by worst-case disagreement ratios.

---

Correlation Clustering Beyond the Pivot Algorithm
Acknowledgements
Cambus, M., Kuhn, F., Lindy, E., Pai, S., and Uitto, A (3 A)-Appoximaaee Correlation Clustering Algorithm in Dynamic Streams. In Proceedings of the 2024 ACM- SIAM Symposium on Discrete Algorithms. SODA 2024, 2024.
Soheil Behnezhad and Alma Ghafari were supported by NSF CAREER award CCF-2442812 and a Google Research Award.
Impact Statement
Cao, N., Cohen-Addad, V., Lee, E., Li, S., Newman, A., and Vogl, L. Understanding the cluster Ip for correlation clustering. In Proceedings of STOC'24, 2024.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chakrabarti, D., Kumar, R., and Punera, K. A graph- theoretic approach to webpage segmentation. Pro- ceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, pp. 377-386, 2008.
References
Agrawal, R., Halverson, A., Kenthapadi, K., Mishra, N., and Tsaparas, P. Generating labels from clicks. In Pro- ceedings of the Second International Conference Web Search and Web Data Mining, WSDM 2009, Barcelona, Spain, February 9-11, 11,120 2009, pp. 172-181, 2009.
Chakrabarty, S. and Makarychev, K. Single-pass pivot al- gorithm for correlation clustering. keep it simple! In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Ailon, N., Charikar, M., and Newman, A. Aggregating inconsistent information: ranking and clustering. In Pro- ceedings of the 37th Anmual ACM Symposium Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 684-693. ACM, 2005.
Charikar, M., Guruswami, V., and Wirth, A. Clustering with qualitative information. 44th Symposium on Founda- tions of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pp. 524 533. IEEE Computer Society, 2003.
Ailon, N., Charikar, M., and Newman, A. Aggregating in- consistent information: Ranking and clustering. J. ACM, 55(5):23:1-23:22 2008
Chawla, S., Makarychev. K., Schramm, T., and Yaroslavtsev, G. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. CoRR, abs/1412.0688 2014.
Assadi, S. and Wang, C. Sublinear time and space algo- rithms for correlation clustering via sparse-dense decom- positions. In 13th Innovations in Theoretical Computer Science Conference, ITCC 2022, January 31 February 3, 2022, Berkeley, CA, USA, pp. 10:1-10:20, 2022.
Cohen-Addad, V., Lattanzi, S., Mitrovic, S., Norouzi-Fard, A., Parotsidis, N., and Tarnawski, Correlation clus- tering in constant many parallel rounds. In Proceedings of the 38th International Conference on Machine Learn- ing, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2069-2078. PMLR, 2021.
Bansal, N., Blum, A., and Chawla, S. Correlation clustering. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-1 19 November 2002, Vancouver. BC, Canada, Proceedings, pp. 238, 2002.
Cohen-Addad, V., Lee, E., and Newman, A. Correlation clustering with sherali-adams. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pp. 651-661, 2022.
Bansal, N., Blum, A., and Chawla, S. Correlation clustering. Mach. Learn., 56(1-3):89-113,, 2004.
Behnezhad, S., Derakhshan, M., Hajiaghayi, M., Stein, C., and Sudan, M. Fully dynamic maximal independent set with polylogarithmic update time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pp. 382 405, 2019.
Cohen-Addad V., Lee, E., Li, S., and Newman, A. Han- dling correlated rounding error via preclustering: A 1.73- approximation for correlation clustering, In Proceedings of the 64th Annual Symposium Foundations of Com- puter Science (FOCS 2023), pp. 123-134. IEEE Com- puter Society, 2023.
Behnezhad, S., Charikar, M., Ma, W., and Tan, L. Almost 3-approximate correlation clustering in constant rounds. In 63d IEEE Annual Symposium on Foundations of Com- puter Science, FOCS 2022, Denver, CO, USA, October 31- November 2022, pp. 720-731, 2022.
Cohen-Addad, V., Pilipezuk, M., Lolek, D. R., Thorup, M., Yan, S., and Zhang, H. Combinatorial local search. In Proceedings of STOC'24, 2024.
10

---

Correlation Clustering Beyond the Pivot Algorithm
fali,,ooyfard, M., Makarychev, K., and Mitrovic, S. Pruned pivot: Correlation clustering algorithm for dynamic, par- allel, and local computation models. In Forty-first In- ternational Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL
id=saP7s0ZgyE..
Davis, T. A. and Hu, Y. The university of florida sparse matrix collection. ACM Trans. Math. Softw., 38(1), December 2011. ISSN 0098-3500.
doi: 10.1145/
2049662.20499633, URL https://dde //tp:////oo../..... 1145/2049662.24998
Kalashnikov, D. V., Chen, Z., Mehrotra, S., and Nuray- Turan, R. Web people search via connection analysis. IEEE Trans. Knowl. Data Eng., 20(11):1550-1565 2008.
Kim, S., Yoo, C. D., Nowozin, S., and Kohli, P. Image segmentation usinghigher-order correlation clustering. IEEE Trans. Pattern Anal. Mach. Intell., 36(9):1761- 1774, 2014.
Shi, J., Dhulipala, I.., Eisenstat, D., Lacki, J., and Mirrokni, S. Scalable community detection via parallel correla- tion clustering. Proc. VLDB Endow., 2021.
Veldt, N. Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 25060-22088 PMLR, 17-23 Jul 2022. URL pttp//oooccooooooooooooo ngs mlr. / v1 62. 2222222222 html.
Veldt, N., Gleich, D. F., and Wirth, A. A correlation clus- tering framework for community detection. In Proceed- ings of the 2018 World Wide Web Conference, WWW '18, pp. 439 439, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. ISBN 9781 9784450356398. doi: 10.
1144/3178896..186110, URL https: /dog 10. 10.1145/3178876.11888 3186110.

---

Correlation Clustering Beyond the Pivot Algorithm
A. Analysis of Algorithm 2
A.I. Algorithm Charges Enough Bad Triangles
In this section, we show that Algorithm 2 charges enough bad triangles.
Lemma A.I. Let y be the vector of charges returned by Algorithm and let C be the corresponding clustering returned by MODIHEDDIvOT (Algorithm 1). Then it holds that
Σ IEBT
y1 2 cost(C)
Proof. We prove by induction that the end of every iteration of the while loop, ExEBr BT Y upper bounds the number of mistakes made by Algorithm so far. Clearly this holds for the base case i 0.
Now consider iteration i 2 1. The set of vertices newly clustered in this iteration is C. A, \ A. (To avoid ambiguity, any mention of the set A during iteration in this proof specifically refers to its state before it is updated by A, in Line 12 of Algorithm or Line 38 of Algorithm 2.) To prove the inductive step, it suffices to show that the number of mistakes newly made by Algorithm in iteration i, which are precisely the mistakes that have at least one endpoint C. U A, and no endpoint in A, are upper bounded by the total amount of charge to bad triangles in Lines 12, 14, 21, 24, 26, 33, 35 and 37 in this iteration. Note that each of these mistakes (z, z) satisfies exactly one of the following conditions:
1. (x,2) & E and x, E C. D'
2. 22, E Dj, and U.A.
3. (x,2) E E C, and & EV \ (C, U A. UA).
4. 2x) & and v, E A
5. Either (x,2) 2) E F E Ar and = E V (C, U Ag), or (2, & E, E A', and E Co Dz-
6. (x, F A. A and E Co.
7. (x, E E Ar and z EV (V.UA)
We refer to the mistakes that satisfy condition (j) as Type (j) mistakes. e, denote the number of mistakes of Type (j) and let yt denote the total amount of charge to bad triangles in Line of Algorithm 2 in iteration i. We now prove the following statements (a)-(d) one by one, which collectively imply the inductive step:
1. C1 < y11-
To see this holds, we observe that each Type (1) mistake (x,, 2) where (z, 2) $ and x, E C. \ D', corresponds to bad triangle (v, xr, that is charged by in Line 12.
2. C2 Σ V13-
The total number of Type (2) mistakes (a, 2) where (z,z) E E, x E D', and E C. U U.,,, is at most
Σ (IN()) + < D (8 + [+ s 28) D.
ZED
On the other hand, the number of pairs (u, w) & E such that u, w C. and at least one of or is in D',, or
12

---

Correlation Clustering Beyond the Pivot Algorithm
equivalently, the number of bad triangles (v, u, w) that are charged in Line 14, is equal
[KC, ( ( lo (NV(u)
Σ DED
[C. (G.)((( = 1 (NN(N())
(
2
-c,, Σ (1,11 IC, (C,nN(w))) [(w) 1)
2
NED,
- -c.l-(81C,) 1) -
-8)
1
(161C.11 - -1))
2
2 (1
3 2 11
2
Thus the total amount of charge in Line 14 is at least
26
20)
| I
1- 2 2
which upper bounds the total number of Type (2) mistakes.
3. /f !/|A.l S I. then c3 S y19. Ca + c5 S y22, and ca 07 S 9/4-
In the case of | < & &CCol, Algorithm 2 charges in Lines 21, 24 and 26. We show the three inequalities separately.
To see that S /19, we observe that each Type (3) mistake (æx, 2) where (I, 2) E E, x E Co and V. C. \ A4 \ 4 corresponds to a bad triangle (v, x z) that is charged by in Line 21.
Next, show c4 + Cs S y22- The total number of Type (4) mistakes (I, 2) where (2,2) & E and x, A is most
(1A4.)
1 1 -1) 1) 1 (16 1) S 5 1%
For type (5) mistakes (z, where either (I, E E, x E A' and 2 E V V C. \ A'. or (z, & E. x E A' and z Cp \ D note that both cases we have = (C,) Thus the total number of Type (5) mistakes most
Σ [N() A 1) s =|A,11C.). ZEAR
On the other hand, the number of pairs (u, w) E E such that C2 and E A' or equivalently, the number of bad triangles (v, u, w) that charged in Line 24, is equal to
Σ (N(w) nC,l= Σ IC, (NV())))))) |AC (eIC.) 1)) 2 (1 ()))))A(,CCall WEA
Thus the total amount of charge in Line 24 is at least
8(1 - --), 2 (8 - ()-,)),,, 2 ( +e |4.11Col.
where the last two inequalities follows from e E (0, 1al and [4s, 2). This upper bounds the total number of Type (4) and (5) mistakes.
Last, we show Gg + Cy I 324- Note that each Type (6) mistake (x, 2) where (r, E E, x E A, \ A and 2 E C. corresponds to a bad triangle (v, 2, x) that is charged by + ف in Line 26. For each such (v, 2,x), we allocate a charge of cover Type (6) mistakes. It remains to show that the sum of remaining charge of = T-a to each of these
13

---

Correlation Clustering Beyond the Pivot Algorithm
triangles in Line 26 is sufficient cover Type (7) mistakes as well. To that end, let us count the number of bad triangles charged in Line 26, which is
Σ WEA
(N(w)
nC,l= =
E IC (N((w)CC.)
WEA,14 144
M |A [ (e|Col-
2 (1 A) \ A/
Thus the total amount of remaining charge can allocate for Type (7) mistakes is least
& 1 1 - =) 4.IIC.1 = =|A,, \ A.
We now show that the total number of Type (7) mistakes does not exceed this amount. Indeed, the total number of Type
(7) mistake (ær, where (I, z) E E, x E A. \ A', and E V C. \ A' is at most
Σ AA
[N())CC) $ |. \ A. 1) s s|Ae \ A.
4. If If|A Cl then c3 S y3o and C4 + c5 c6 + 07 S M/1 1/3.
In the case of |4al > k|Cel. Algorithm 2 charges Lines 33, 35 and 37.
We first show c3 S y/0- To see this holds, we observe that each Type (3) mistake (x, where (x, 2) E, x E C2 and V C. A, A corresponds to bad triangle (v, 2. 2) that is charged by 1 Line 33.
We then show 64 + 6s + G6 + 07 S M/1 + V3s. Recall that in the case of |A,l S k|Cccl. we showed 04 + 032 + cg + 07 S 1/2 + 1/44 Suppose for moment that Algorithm had charged each bad triangle (v, u, w) Line 35 by max (6, 1 + )
= 1
T-.. Then by the exactly same argument as we had for the case of [Aul S k|C.). we could
show that C4 cs + ce + S Ysı holds as well. However, in reality, Algorithm 2 only charges an amount of (1 1-6 to each bad triangle (v, u, w) in Line 35. Since there are at most |Aul choices for w A, and at most (|Cr] choices for u E C. \ {v), this results in a total charge deficit of at most T- [A.[(
cover this deficit, we show that y/3 2 enough bad triangles in Line 37, The total number of triplets (u, w, such that E (Nv)) and w, x e A. is equal to
- 1). To that end, we need to show that Algorithm 2 charges
(AAu) 2
(IC,1 (IC,1-1). 1).
Note that each pair (u, w) where (v) and A, can appear in at most |Apl - 1 such triplets, and each pair (w, x) where w, x E A, can appear in at most |C.l - 1 such triplets. Thus the total number of such triplets (u, x)) that do not satisfy the condition in Line 32 and are not charged in Line 37 is at most
Σ (u. WE N()), m
(lAo-
Σ
(CC,l-
(M. W,
Σ
Σ
(AA - 1)+
1
Σ
(1C,1 (1Cll-1) -1)
WEAr
(EC.)N(ww)
CEN(w))A
[N(w)
max 1, (1Cml
WEA.
< Ao 1)( -1),
where the last inequality follows from |A,| C.Cal and & > 1. Thus the number of bad triangles charged in Line 37 is at least
(1Avl) 2
(IC,) - 1) - |A.1( - 1)(14.) 1) 2 2 - (4) 1).
14

---

Correlation Clustering Beyond the Pivot Algorithm
Thus the total amount of charge in Line 37 is at least
5E/ (1 - =) 1 Am 1 2 - -)) 1)
5e (1 |
22 --21A.1Icol
|A 2
1-8
-
where the last inequality follows from S 14- This is sufficient to cover the total deficit of at most 25. 100((1Cl - -1) from Line 35.
We have proved statements (a)-(d) for iteration i. By induction, the proof is complete.
A.2. Algorithm 2 Has Width Smaller than 3
In this section, we prove that Algorithm 2, for any fixed pair of vertices, charges at most 2.997 bad triangles involving them in expectation. This upper bounds the width of Algorithm 2 by 2.997, and thus combined with Lemma 4.5 and Lemma 4.4 proves that Algorithm obtains a aprroxippooin
Let us for every pair (a, b) of the vertices use ((a.)) := involving both a and b. Our main result of this section is the following lemma.
Eig bet Ut to denote the total charges to the bad triangles
Lemma A.2. Let y be the charges returned by Algorithm 2. For every pair (a, of vertices,
E [Ma,6)] 2.997.
In order to prove Lemma 4.6, we start with a number of useful observations. When we say a pair (a, b) of vertices is charged in Algorithm 2, we mean that Algorithm 2 charges some bad triangle involving (a. 6).
Observation 2. Except for the bad triangles charged in Line 37 of Algorithm 2, whenever bad triangle / is charged in Algorithm 2, the pivot u chosen in that iteration must be part tf
Proof. Follows directly from the description of Algorithm 2.
Observation 3. Any edge (a, b) E F is charged at most one iteration of Algorithm 2. Any non-edge (a, b) & F. is charged in at most two iterations of Algorithm 2, and in particular, is charged in at most one iteration if none of the charges involving it take place in Line 37.
Proof. First, as shown in Observation 2, except for when triangle is charged in Line 37 of Algorithm 2, the pivot must be part of the bad triangle. This means that either or should be chosen as the pivot v or at least one of them must be adjacent v. In either case, at least one of u or v gets removed from V in iteration i. Note that, at least one of (a, b) is corresponded to either or v, as result of this at least one of the endpoints of (a, b) is removed from V. and therefore, (a, b) won't t be charged again.
Now, if (a, b) E E, consider the case where a bad triangle (u, w. is charged in Line 37. In this case, u E C. gets removed from V in this iteration but w and x remain in V. Crucially, observe that the two edges of this bad triangle, which are (u, v) and (u, w). are both adjacent to u. Therefore, in this case too, any edge that is part of a charged bad triangle has least one endpoint removed. Note that, (a, b) is corresponded to either (w. u) or (z, u). This means after charging (a, b) in Line 37 of Algorithm 2, we remove at least one of (a, b) from V. and consequently, we will not charge (a, b) in any future iterations.
If (a, b) & E, then it can be involved in multiple bad triangles (u, w, w)) charged in Line 37 of Algorithm 2 in one iteration. However, we will not be charging this non-edge in Line 37 again in any future iteration of Algorithm 2. This is because we will be appending w and x to the set A, which means that we will not be charging this pair as a member of Agr for a pivot of in future iteration. However, we might still charge this non-edge (a, b) in one more future iteration in a single line other than Line 37.
Let us group the bad triangles charged in Algorithm 2 in iteration based on the position of the pivot. Note that each charging line in the algorithm processes a particular kind of bad triangle. We define these sets based on whether a bad triangle includes a pivot e or not, and if yes what the adjacency state of is.
15

---

Correlation Clustering Beyond the Pivot Algorithm
Definition A.3. Let be the pivot chosen in some iteration i of Algorithm 2. Let X₂ be the set of bad triangles in the graph of iteration which involve the pivot and is adjacent the other vertices in f. Let Y, be the of bad triangles t in the graph of iteration i which involve the pivot and v is adjacent to exactly one other vertex of t. Finally, let Zo be the set of all bad triangles in the graph of iteration that are charged in this iteration but do not include the pivot v.
Now, we investigate the charges for each type of bad triangles. Observation 4. By the assumption that pivot v was picked iteration of Algorithm it holds that:
1. Any / E x, is charged by either one of the Lines 12 and 14 and therefore is charged at most by 1.
2. Any t E Y, is charged by either one of the Lines 21, 24, 26, 33 and 35 and therefore is charged at most by 1 + 1
3. Any & Zy is charged 5s/(1-s)
by only Line 37.
A.
Proof. We prove the three cases one by one below.
1. Note that followed by the charging scheme in Lines and 14 of Algorithm 2 we charge bad triangles including a pivot and its neighbors u and in iteration of the algorithm. That is by description, all the bad triangles in set X Note that the charge of is bounded by maximum charge of Lines 12 and 14 that is equal to max 1,
26 Note that by the
1-38"
choice of parameter 8 < & in Algorithm 1, we have 1- 6
26 S 1, and therefore, max(1, 1-35
26
2. The structure of triangles in Y,, is also the same as our charging cases in Lines 21, 24, 26, 33 and 35. Note that we charge bad triangles in iteration i including the pivot v, vertex E Cp and, w E V C.. In this case, each triangle is charged at most by max(6, 1, - - + 1-8.
3. Finally, by description any bad triangle in set Zy is charged by Line 37, charge each triangle in this set by 5e/(1-e) A
This completes the proof.
Definition A.4. We define (a) in iteration i of Algorithm 1 as the set of the remaining neighbors of a in V.
Definition A.5. Note that, for analyzing different bad triangles containing vertices a and b we need to define the sets where the third vertex is chosen from. Confirm that vertex e should be in neighborhood of a or b. We define the following sets based adjacency of vertex to a, b, or, both:
Na == N(a) (b)
N₂ ((6) \ (N(a) Ua),
Na.b == (N(a) n N())) \ b).
Note that these sets are defined based on the vertices remaining in the graph in iteration of Algorithm 1.
Definition A.6. Let us define V(a.b).8 the sum of the charges returned from Algorithm 2 for any bad triangle containing vertices (a, e) such that e S. That is, we define
Σ Vt-
(a,
To prove Lemma 4.6, we need to separate the analysis into two parts. Particularly, the analysis of the edges and non non-edges different, this is because the charging scheme is not symmetric with respect the adjacency of two vertices.
1.2.1. WIDTH ANALYSIS FOR EDGES
Claim 3. For any (a, b) E E we have:
1. E (a.b))).N..l =0
16

---

Correlation Clustering Beyond the Pivot Algorithm
2. E'y(a.)) I (N())AN(U) \ (a s -.c 0 o= a) - Nal.
3. Ely(a.)).N.
4. Maad), == a) $ (1 +
Proof. Here we prove each statement separately.
1. We do not charge in Algorithm 2 E ((a) n (()), as t will not form a bad triangle.
2. In this case, v is adjacent to exactly one of a or b due to the conditional event e (N (N()) {a, b). Let us assume without loss of generality that u is adjacent to a. We consider the following three cases which cover all possibilities:
|Ael S k:C:|::
Confirm that, Algorithm 2 implies that in this setting we will only charge bad triangle t = (a, b, v) E Y, The charges include Lines 21, 24 and 26. The maximum charge for is 1-c'
|A.l > k|C,] and b $ Aş: In this case if 6 & A. the only charge that applies to bad triangles t including (a, 6) is the charge in Line 33, this bounds the charge of (a, b) by 1 for each choice of the pivot.
|Apl > k|C.| and b E Ag:
In this case, there are two types of bad triangles that involve (a, b): bad triangles of type (a, b, c) E Zy charged in Line 37 and those of type (a, b, v) E Y, charged in Line 35. Note that we charge (a, b, U) in Line 35 by 1- - In Line 37, for any vertex such that E No O Ag charge (a, b..b,x) by 5e/(1-e) Since E Au. TA.1-1
there are at most |Apl 1 choices of x and so the total charge from such triangles involving (a,b) is at most se 3e/(1-E)
Se TA.1-1 (1Apl= 1) I-E- Combined with the charge of 1 T-E incurred in Line 35, this sums up to at most charge of 1 + 48
I-6"
3. In this case, since v a and a is adjacent to both endpoints of any bad triangle counted in N, all such bad triangles belong to X. by Definition A.3. By Observation 4, any bad triangle in X, is charged at most by 1. Since there are at most |Nal choices of the third vertex in bad triangles counted in (),, and each charged by at most 1 as discussed earlier, the total charges sum up at most [Naal.
4. In this case, since e = a the pivot adjacent to and is not adjacent to any vertex c E Nb. this means that all bad triangles in this form are an element Y, by Definition A.3. Note that, by Observation 4 we charge any triangle in Y, at most by 1 + - Confirm that, if we fix a, b and the pivot, there only [No] choices for the third vertex of the bad triangles charged in V(a.b).N, and each triangle is charged by at most 1 + T-e as mentioned. Therefore, the total charge of such triangles is at most (1 + [=g]l
This wraps up the proof of Claim 3.
Claim 4. For any (a, b) E E, it holds that
E [(.a)] = Pr[u- = a] Ely(a, | v a)
+ Pr[u = b] E(pca,a) -u= b]
+ Pr(u E (N())AN(b) (a, Elg(aM) I (N(a)AN(()) \ (a, 6]].
where u is the first pivot chosen at some iteration in Algorithm 2 that after processing at least one of a or b is removed.
Proof. Let condition on iteration i of the while loop in Algorithm 2 being the first iteration where at least one of a or b gets removed from V. Note that conditioned on this event, the pivot u of iteration i must be in set ((a) U ((b), and note that a and b themselves are part of this set too since (a, b) E E. Moreover, v is chosen uniformly from this set.
By Observation 3, no triangle involving (a, b) is charged before or after iteration i. Thus, suffices to calculate the expected charge to the triangles of (a, b) exactly in iteration i. For the rest of the proof, we use N(u) to denote the neighbors of
17

---

Correlation Clustering Beyond the Pivot Algorithm
any vertex still in V in iteration i. Let expand Ely(a,o)) based whether the pivot v of iteration i is chosen from the common neighbors of and b or not. We have:
B[M(a,)) Pr(e (b)) ((y(a Que M(a)AN(b)) + Pr(u E (a) n N()) Ely(a. I (()) (())-
First, by Claim we have Mly((, 1 ((aa) [b) 0. From this, we get that:
Elu Elu(a,))] = Pr(v ((a)AN(b)) Ely(a,))
N(a)AN(()).
Note that the structure of our analysis varies when pivot e is chosen as vertex o, b, or from the set of (N()) \ {a, b). To understand the differences we further expand Ely(a,))] conditioning each event describing whether a, b, or a vertex from the union of their neighborhood is chosen as a pivot.
E = Pr(v al (a lu=a =a] a]
+ Prfu- = E(y( lu= b]
+ Prfy E (N()))N(()) b)] Elu(aM) lue (N(a)AN(()) \ fa, b)].
Claim 5. For any (a,b) F the expected charge on e most
(3 + 5e I-s (INal (N6))
N + No Na +
Proof. By Claim 4, we expand E(y(a,s) 0 (()) as follows:
E (a, = Pr(u al Ely(o,)) v = a]
+ Pr(u b] E(y(a.5) v =
+ Pr|u E (N(a)AN(6) {a, b}] Ely(a,)) lve (N(a)AN(b) \ 61,
Here we proceed with exploring each possible event for the pivot using Claim 3. In the case where e = a for any bad triangle including a, we charge different values based on the third vertex. Here the charges for each choice of the third vertex e are when E Na and E Ns:
E E((((,))
| U a] =Elya,)), 1 a)
Ely(o,)).. 10= a) 1-2
|Nb1 + NNal-
By rewriting the above inequality for the case where we have:
E(y(a,)) b] -E 1 = b]
E Ela.,))).N 10= b) <
E 1
Nol + [Nol.
1
In the last case, where the pivot is not picked as any of a or b, we have:
B(y(a, I E (N(a)AN()) \ (a,b)) < 4s
1-6
Since Pr[p = a] Pr[u = 6] = Majunoo and Pr[u E (N(a)AN(I)) \ (a,6)) inequalities we give the following upper bound for E(y(a,))]:
NN (b] combining the above
E[Vta.o)] S
1
3 +
5e
(INal + IN61)
LI
Na +
|
No
+2
18

---

Correlation Clustering Beyond the Pivot Algorithm
Now, we separate the analysis for three cases, (C1) and based on the properties in each case, we determine an upper bound for the expected charge of any edge. We introduce a parameter I that will be For any of the following cases, we will use Claim 4 to expand the expected charge on each edge. To calculate the expected charge of the edge (a, b) conditioned on any event representing the state of the pivot with respect to the pair of (a. b). we need to determine all the bad triangles charged in Algorithm 2 in iteration i. Note that for the events where & E {a, b). the choices of the third vertex of a bad triangle in the form of (a, b, c), determines the charges on t.
minimize the charge over edges.
1. max[|Nal [N6 - 8.
2. max (| No.3 3. (N(a) N()) + 2 (N))
3. max[|NNal |. | g. (.Va)) N(6) + 2 شー [1(
Claim 6. In 1, the expected charge on (a, b) is at most
(1
3
5c I-8
046
Proof. To prove the claim, we use the upper bound from Claim and the condition in I:
3+ 5e
E Byaal S Na + No + |Na,bl +
(I + [Nb])
&
5
8
5z
3
3
No. + No + 2
0 0+0 0
1 -
Claim 7. In 2, the expected charge on (a, b) is at most 3 +
66 -6 2(++5)
2-76
1-6
2-35 33
Proof. Let us assume that (b6 (a), by this distinction between and b, we investigate each event representing different states for pivot:
1. v a:
In this event, we charge the pair (a, b) for any remaining vertex in the union of the neighborhood of a and b, this is because, any bad triangle has 2 adjacent vertices, and since we are charging all the bad triangles involving a, b, the third vertex should be either adjacent to or b. Now, by investigating any choice of vertex bad triangle with a, b, we compute the total charges related to whether e is picked from Na. No. or Na., we expand E E(y(o,b) V a] based on these choices for the third vertex:
N(a) U (()) that creates b. Note that, the different cases affecting the analysis,
Ely(a.)) | a) ElVia,)).N. 1 a)
+ ElV(a,))NNo. = a)
E(U(a.b),No U a)
E Ely(a,)),N. 10 a) + (1
|Nol.
1
Note that the inequality is resulted from Claim 3. Now we explore E(y(a,)).N. 1 = a). Since ((b) < [a)),, and based on the assumption of this claim, we have
5 (1 + (N6) < 8 |Na.
(Naa) +2
2 28
Moving the terms, this implics
(1-))((N(a)))))) + 2) < 8((Na)),
which using the fact that No = N(a) \ (N)(b) U b) it holds that:
((a) + 8(IN(a)) + 2) - < 8|C.).
19

---

Correlation Clustering Beyond the Pivot Algorithm
Note that the above inequality implies that (N(a) n N()) +1 8|C,] by Algorithm have b E Da- Thus, vertex joins D' with probability Pi,())..,1 Here we find a lower bound for this probability using the condition [2al
min Lo/Col1)
8|Co1 -
2 8 8 D
Del
0
Note that by Observation any edge is charged once, and then at least one of its endpoints is removed from the graph. The only choices of that change the charging of t depending whether D'2 contains b or not, are the vertices in Na. At this step, we can expand E M) v === a] conditioning on state of b with respect to D'.:
E (l,
= Prr[b D2 a) E(U(a,)).N. c-= a, $ D' + Pr[b E D' v = a) E(U(a.D).N. == a, D']-
In the first case, if & Dú; if c & D' we charge t by Line 12, otherwise we charge it by Line 14. Therefore in this case for each choice of c, we charge at most 1, and since we have Nal such bad triangles then:
Eiu(a, e a, b E DJ $ |Nal-
In the case where 6 D' we always charge by Line 14. This implies the following:
28
E Bly(o, v== a, E DJ
Nal-
1 3
Based on the bounds above, we get:
min Lo|Co1)
min Del, 181C,1]}.
28
Elj((,,).v.. 10= al
|.aol
|Del
Drol
1 1
26
min (Drrl, [81C.11}
25
1
|Nal
DDo
08 82
2 78
|Na
0+8
2 35
2. b:
As explored in event a, we differentiate between triangles by choices of the third vertex in f. Following this we expand Ely(a,,) b):
Ely(a,)) b] E(M((a,)).N. v +E(y(,,)) |0 v-= 6j + Ely(a.)).N. v b]
8 NNal + |N6/-
S
+
Confirm that the above inequality is simply resulted from Claim 3.
3. v (N())AN(() \ (a,b):
Directly by Claim we have:
Ely(a,)) IUE (N(a)AN((6) \ (a,b)) (1+ 48
8
20

---

Correlation Clustering Beyond the Pivot Algorithm
Finally, we have:
E Ely(a,o)] = Pr(m = a)
(11-0) 06+ 8 (1--0++0)
8 2-70
|Nal +
1 6
|Nal)
0+0 8 2 36
1 -
+ Pr/u = b]
[1+
E
[Naal + [Nvol
48
+ Pr/u E (N())AN(U) {a,bj) bH]
1 T
3 +
bs
--482-6
2-76
NNal +
3 + r |.vol
T-c
646
2-36
[Nall + Nol
|No + 2
Let a
26 [62
0-2
4.
2-38
Now, we give an upper bound on E[V(a,))) based on a:
3-
3+ 5e
Elyaa
(1-a) + -
- N + | -1-
Nai + N +
NNa, +2
3+
I-9
5e
(1 - -1- 21 + 11- -1
No. + [Nb]
+ [No,bl +2
5c
(1
②
3
2
5e
06 82 8 2 78
1 8
2(0 + 8)
2 35"
Claim 8. In 3, the expected charge on (a, b) is at most (1 - 2-8
3 5c
T-8
Proof. Note that by the condition in 3, we have:
(Naa) N()) +22 2 2-8 2 N(a)UN()(
this implies that:
1--2- (N(()
|N |N6 <
Using the inequality on the sum of Nal and |No,, and also the upper bound from Claim 5 we have:
1 E[y(a,)) S Na + |Nol + NN, 2
[ 3 + 1-E)
56 E) (INal + 1N61)]
8 2-5))
(3
56
< 1
5)
3
2
E
A.2.2. WIDTH ANALYSIS FOR NON-EDGES
Claim 9. For any (a,b) b) & E we have:
1. FYG..).NUNN) =0. 0.
2. E'y(as) E No.1] 11
3. E'aaa, 0 = a] $ (1 + - [
Proof. We prove the three parts one by one.
1. Note that, the triangle t = (a, b, c) such that c E N. U N₂ does not form a bad triangle as there exists only one edge in
21

---

Correlation Clustering Beyond the Pivot Algorithm
2. In this case, we have a Na.5 that means the pivot is adjacent both a and b. By Definition A.3 any bad triangle of this structure belongs to the set x By Observation 4 we charge such bad triangles at most by 1. Note that, for any fixed pair of vertices given the pivot, we have one such bad triangle, and therefore the total charge is bounded by 1.
3. Note that any triangle charged in this case is in Y,. This is because for any fixed pair of non-edge (a, ba, any bad triangle charged in &, with the condition that v = a, we have v is not adjacent to b but it is adjacent to the third vertex с chosen from the set No.b- By Definition A.3 any such bad triangle is in Y, and is charged at most by + as we discussed in Observation Summing up over choices of the third vertex, we get an upper bound of
(1 Na,bl over charges to all such bad triangles.
The proof is complete.
Claim 10. The expected charge over a pair of vertices (a, b) & E is expandable as follows in case the pair does not belong to the set E:
Ely(o,)) Pr(c- = a) Ely(o,)) u == a]
+ Pr[[ b] E( u /== b]
+ Pr|fu E No. Ely(a.0) v E Na,1] + 5 E 1 1
where V is the first pivot chosen at some iteration in Algorithm 2 that after processing v, at least one of a or b is removed.
Proof. Let us condition on iteration i of the while loop in Algorithm 2 being the first iteration where at least one of a or b gets removed from V. Note that conditioned on this event, the pivot e of iteration must be in set (()) U ((b) U {a, b). Moreover, is chosen uniformly from this set.
By Observation 3, any triangle involving (a, b) is charged in at most two iterations. We consider the charge from the iteration that results in removing at least one of the endpoints of this pair (iteration i), and sum it up with the maximum possible charge that could have happened in Line 37 of an earlier iteration in Algorithm 2. For the rest of the proof, we use N (u) to denote the neighbors of any vertex u still in V in iteration i.
Let us expand B)y( based on whether the pivot e of iteration is chosen from the common neighbors of and b or not. We use E(y(a,t) o'] to denote the additive expected charge for (a, b) resulted from the case where (a, b) is charged once before iteration i, and we use v' to denote the pivot picked at that earlier iteration. Taking this charge into account, it holds that:
Ely(a,)] = Pr[u E (a))N(b) Ely(a, JO E (a))
+ Pr[c E No.s U {a, b}] Ely(a,)) v Na.s U {a, b}l + Ely(a,)) o']
First, note that by Claim 9, Ely(a.)) / E N(a))N((())) = 0. From this, we get that
E[y(a,))] = Pr(p E No.s U {a, b)] ElD(o.,) | Na. U {a, by] + E[M(..8) | 07).
Note that the structure of our analysis varies when pivot v is chosen as vertex a, b, or from the set of Na.5. To understand the differences we further expand E)) conditioning on each event describing whether a, b, or a vertex from the intersection of their neighborhood chosen as a pivot.
E E(y((.a)] Pr(u- a] Ely(a,t) | v a)
+ Pr[u- b] Elv(a,0) v b=b) b]
+ Pr|u E No. Elvia.)) 1 E No,1l + Ely(a,)) o'].
Now, it only remains to prove that E(y(a,)) o'l S F - Note that, there exists at most one pivot o' charging any non-edge by Line 37 in Algorithm 2, however, for any third vertex c holding the properties of vertex u in Line 37 in iteration where we remove v', we charge (a, b, c) by - Since there are most |Carl choices for c, this gives an upper bound of
|Carl for this particular charges on (a, b). Since we only charge such bad triangles if |Arr| > kl A/Crr. J, this implics
5c
E[y(a.b) 1 1o1s
I-e
k
22

---

Correlation Clustering Beyond the Pivot Algorithm
Claim 11. For any (a,b) & E the expected charges over is most
Na.bl
5e
N + No Na.l
+2
k
Proof. Note that by Claim 10 we have:
E Bla(),)) Pr[u E(y(a,b) =-a
+ Priu b] Ely(a.b)) 1==
E k 1
+ Pr/u e No.o ElU(a.))
V [ +
Here we proceed with exploring each event using Claim 9. In the case where v = a for any bad triangle including a, b, we charge different values based on the third vertex. Here the charges for each choice of the third vertex are when c E No.6:
E. Bly() E {a, b)]
El) 1 a] Elyla,)),N.. 10
s 2(1 N/Na,ol-
For the case that the pivot picked from the common neighbors and we get:
E Ely(a.)) 10 No, 1.
Since Pr(v = a| = Pr(v = bj NijjuN(( and Pr(u E Na.) MoJMMM) inequalities we give the following upper bound for Elyr(a,))]:
|N.
combining the above
E Ely(a,t) S |Naa + |Nool + |N +
1
( 3 1-E)
25
Na,ol
+
I-c
k
Now, we separate the analysis for three cases, (D1) (D3), and based on the properties in each case, we determine an upper bound for the expected charge of any edge. We introduce a parameter À that will be set to minimize the charge over non-edges. For any the following cases, we will use Claim 10 to expand the expected charge on each edge. To calculate the expected charge of the non-edge (a, b) conditioned on any event representing the state of the pivot with respect to the pair of (a, b), we need determine all the bad triangles charged in Algorithm in iteration Note that for the events where {a, b), the choices of the third vertex of bad triangle / in the form of (a, b, c), determines the charges on
1. min|[N(@),INN()) < 3/-
2. (IN()N( A (N(O))N(()) +2< 14.1N( UN(())
3. min(|N(()),1N1)) (N( +22 I4= ((()))
Claim 12. Let us assume that N.l Z N₂ w.l.ogg. In the expected charge on (a, is at most
2+8 (28+2)
(3
2e 1-8)
+ 36
Proof. By Claim 11 and the condition in we have:
El E(y(a,o))
3
28
No,b
T-e
Na. + |Nol
|Na.bl +2
8
[N(b]
(3 33+
2s
+
I-6
[(b) +2
1
k
28
52
[(N((b) +2
3 +
+
k
X+ 5
3+
28
I-E
(26 + A)
1-8
23

---

Correlation Clustering Beyond the Pivot Algorithm
Note that the second inequality holds since we have |N(()) 2 |Na. and the claim assumption implies [N(b)] + 2 S
|Nal |ool + N + 2. Also, the last inequality holds since have [N(())] I 8. this concludes that 1 [N(6]]2
X+d X/6+2 X+26
Claim 13. In 2, the expected charge on (a, b) at most
25
(1+ 8 - 3 8 + 8 xxx) k
8/k
2e
5s
max
3 +
+
1
k
Proof. Here the analysis varies when pivot v is chosen as vertex a, b, or from the set of Na.b. To understand the differences we further expand E(y( by Claim 10 conditioning on whether a or b chosen pivot not:
El Ely(a.)) 2 Pr(u = a] E[V((a,)) u = a]
+ Pr[u = b] Eiy((, v = b]
5e
+ Pr(u E Na.o) Ely(a,)) U Na.6) +
1-5 k
We determine all the bad triangles charged in Algorithm 2 in iteration i by investigating each event based on the pivot separately:
1. ba:
Now, by checking any vertex e E Na.s. we find about each charging in Algorithm that charges triangle = (a, b, c). We explore Ely(a,o) | v = a]. and note that the analysis for the case where v = b is the same as that for v = a. Now, the condition in implies
(1 + +e + (NN) + < { UN)))
which in turn, results in
Na |Nb] + =((NV,b1 +2) < < +1.
Note that we have
N(a)AN(0) = No U..
This implies that:
+1 S E/N((a))-
+1
Note that the above inequality implies that (())NN(6 < {(IN(a)) + 1) E =(C,l - and therefore we can conclude E Ag. Observe that by Algorithm 2, the vertex b joins A', with probability min:|A.J]166C..11 Note that E Y,, and therefore the charges on different triangles vary whether of E A', or not. We also have two different charging schemes based on the size of A..
[A_]
|A.l S kcCCol: In this case, by the condition in Claim 13, we have
2
1/k
Thus we have:
k|C.]
1+1/8'
min [] [8|Ca [1]
8|C,1 1 C.Col
8 6/k
[g
k 8+X
When the size of A, is not too large compared to that of Cp, we charge any triangle t by 8 bf e A', and 1+ غ otherwise. Based on the probability that is chosen as a member of A', the expected number of triangles charged containing (a, b) can be written as follows:
Elyia,,).Na. 1 a] = =Pr(b & A/le a) E (),. 1 a. b $ A',
Pr A.le a. E. (lai,,))NNo.. 1U V= a, b A').
24

---

Correlation Clustering Beyond the Pivot Algorithm
In the first case, if & A we charge / by Line 26, Therefore in this for each choice of c, charge / 1 T-e- precisely we have:
most
Ely(a.b),Na. V= a, b A.] = 1 1-e) Nabbl
the case where E A' we always charge by Line 24. This implies the following:
E Bl 0 = a, b E A'l = 8|.o..l-
Using the expected charges above the following equality holds:
min min (lAol: 1.(C..11))) (1 E (
El,a,, u === a] = 1
[Na,
|Aoo
1-8)
min (1Apl, [81C.111, 8) |Na.,
AAp
min(1Arl: [8|C.]]} (1 1-5 1 -6) Nao
1 1
1 1-E
|Au
e +
(-
8 + 8 84x)
6/k
e -----) -6) 0) |Na.,bl
S 1 +
1-E
k
1
|A..] > k|C.||: When the size of A, significantly larger than that of Co. we always charge triangle by I Line 35:
Bl 10= a]= (1
E 1 |.a.bl
2. Na.6: Directly by Claim 9 have:
Ely(a,)) | No.1] S 1.
Finally, we can give upper bound for the expected charges (a, by the maximum charge in the above cases:
[1+10 I-E
(-2 8 )+x)
8/k
(1
-1+1---0
m] s Pr[u-
ba, max
No
-
5e
+ Priv E No,b] +
I-c
k
max
+
2e 1-c
8/k 8+2
1 I-c
-6)- I-c
55
Na
Na + [Nol
+ +NNabbl +2
k
2s
8
8 x (1 (
6/k
8
-8) -6).3
2s
1-c
58
< max
+
1-E E
1-E
E
k
Claim 14. In 3, the expected charge (a, b) is most (1-
(3
2c
1-8
Proof. By Claim 11 and the condition in we have:
E B) Naal + [N6 + |N +2
(3
3
28
Naa
<(1-
$ 31
8
3
2s
1 I-c
5s
1 1-
1 + 8
1 - E
Finally, we are ready to wrap up the proof of Lemma 4.6:
25

---

Correlation Clustering Beyond the Pivot Algorithm
Proof of Lemma 4.6 for any pair (a,b). Now, looking through the width analysis for edges and non-edges, prove Lemma 4.6, for any case described in Appendix A.2.1 and Appendix A.2.2, introduce set of values for parame- ters E, 6, X, and 0 that imply 2. 2.997-approximation We set e 0.007, 6 0.179, À 7.613, 0 7.055, and & = 12.295.
For any edge in E, we investigate the three cases (C1) - (C3). For each case, we prove that EYa,, < 2.997.
In by the upper bound Claim 6 and plugging in the parameters with introduced values we get:
E|Ya,b] (1-1
(1-
8 (3
5s
0 +
2.961.
In 2, by the upper bound in Claim 7 and plugging in the parameters with introduced values get:
5
05 - 8²
76 < 2.996.
EYaa 53+
1- 2(0 + 6)
2 35
In 3, by the upper bound in Claim 8 and plugging in the parameters with introduced values we get:
E| 5
2- (1-2-3
8
3
5e < 2.737.
1-6
For any non-edge in E, we investigate the three cases (D1) - (D3). For each case, prove that ( < 2.997.
In 1, by the upper bound in Claim 12 and plugging in the parameters with introduced values we get:
28
5e
B| <
3
+
I-E < 2.95.
28 x X
1
k
In 2, by the upper bound in Claim 13 and plugging in the parameters with introduced values we get:
2z -
(-h
8
= (1+----))
-0..3
2=
Se
E| max 3
+2
+ 1-E
2.996.
k
In by the upper bound in Claim 14 and plugging in the parameters with introduced values we get:
E|Ya,b1 s (1-
(1-1+t)
E
(3 3
5s + k
2.997.
1 1+E
1
This concludes the proof of Lemma 4.6.
B. Implementation in the Fully Dynamic Model
Claim 15. Take vertices and such that e is pivot and π (elim(u)) 2 (v). Having access to the data structures above stored by (Behnezhad al., 2019), it possible determine the values of [w) nC,, and AN) exactly in Ollog n) time.
Proof. To this, recall first that for each vertex E C., have clim(ww = Therefore, for any edge (u, w) E, because of the assumption i (elim(u)) 2 T(v), it holds that w E N (w). Recalling that N (u) is indexed by the eliminator ranks, and noting that in a BST, we can count how many elements are indexed by the same value in O n2) time, we get that we can immediately compute the value of [N(u) O C.l in O(logn) n) time. Also note that (N) = d,, (N))) Col where dy is the total number of neighbors of u whose eliminator rank at least (v). Such neighbors
can be both in
N- N-(u) and N+ (u). We can count the ones in N- (u) by simply using the properly indexed BST in O(log time, and can simply sum it up to | + (u)l since all neighbors of in N contribute to d,, This concludes the proof.
Claim 16. The data structures (u) (u), (u), To (u), Lae (u) can be maintained Ollog n) time.
26

---

Correlation Clustering Beyond the Pivot Algorithm
Proof. Below, we discuss how these data structures can be maintained in the same time as Lemma 5.1.
Io(u): Note that Ic(u) is equivalent elim(u), which is already maintained by (Behnezhad et al., 2019).
[u):: Suppose that (u) = v, i.e., u E D.. An update may change the value of Ip(u) under one of these events:
(i) the pivot of changes, (fi) some vertices leave or are added to C., changing the criteria [u) nCC.l S 8|Cur for u, or (iit) an edge is inserted deleted from u to some other vertex in C.. We discuss how to efficiently update (u) in each of these scenarios.
(i) Suppose that a vertex v is now marked as a pivot after some update. We argue that we can identify D, in O[CC,) log n) time. To do so, we go over all vertices of C. one by one, and apply the algorithm of Claim 15 on each to check whether they belong to D... Since, from earlier discussion,
already explicitly maintain C. which requires R((Col) time when is marked as pivot, this only increases the update-time by Oloo n) factor. (ii) Now suppose that vertex w added to C... this case, we go over all vertices of (w)),, and for each one u, recompute the value of (u) n C.l in Olog n) time as discussed to decide whether Ip [u) u. Note that must belong to set A (defined in Lemma 5.1), and its neighborhood N (w) has size most Oloog (oogg//((uu)) (w)) (see Proposition 3.1 of (Behnezhad et al., 2019)). Since π (w) 2 min mai(x((a) (=(a), (T)) where (a, b) is the edge update causing this change, the total running time of this step is upper bounded by
δ (14 -Alminn { {
min (in( (b)) (()) {
which is also spent by the algorithm of (Behnezhad et al., 2019) (Lemma 5.1). The process for when a vertex w is removed from C2 is similar.
(tie) In this case, simply re-evaluate (u) n C.l. which can be done in O(log n) using Claim 15.
La (w): To maintain LA (u), we maintain another pointer (u, e) for every pair of vertices and which is iff is a pivot, ((elim(u)) > (v). and Au) I e|Cul 1 (where with slight abuse of notation, NN) is the neighbors of u remained in the graph at the time that is chosen as a pivot). This way, T [u()) is exactly the vertex e minimizing T(D) such that LA (u, v) = 1. So let us see how we maintain LA (u, u) efficiently.
An update may change the value of (u, v) under one of these events: (i) whether v is a pivot changes, (ii) some vertices leave or are added to C,,, changing the criteria [N,)) S e|C,l - 1 for u, or (iit) an edge is inserted or deleted from u to some other vertex in C... We discuss how to efficiently update (u, v) in each of these scenarios.
(i) Suppose that e is marked as a pivot after edge update. We will show how to find all vertices w that satisfy (u) < e|C,1 - 1 in total time O(log n))x Since we can afford to spend this much time for every vertex in A due to Lemma 5.1, this will keep the update-time polylogarithmic.
To do so, we subsample @(log n) vertices in C. without replacement and call it S.. We then take Á = UxES, (x). Note that we have [x+( < O(log n n1/((x)) S ((logn/T(v) for each & E C. by (see Proposition 3.1 of (Behnezhad et al., 2019)). Hence, has size at most Oloog" n//(e)). We go over all vertices u in and check, using Claim 15, whether (u, v) = by spending (log n) time.
It remains to show that if (u, v) = 1, then u must belong to Å. Indeed, we show this holds with probability 1 1- --ppoly(n)) To see this, note that [a v) iff (Nw S e|C,l| 1. This means must adjacent to least a constant fraction of vertices in C.,. Since S. includes (Ioggn random samples from Cy, u is adjacent to at least one with probability 1 1 1/)oly(n))
(ii) Suppose a vertex w is added to C.,. In this case, we go over all vertices x of N (w) and on each reevaluate whether LA (z, v) 1 in Olog n) time using Claim 15. The needed running time O n/ (w=) for w. Similar case (fi) of updating (D),), this, overall, takes the same time in Lemma 5.1 keeping the update-time polylogarithmic.
(wii) In this case, we just reevaluate (u, v) in O(log n) time using Claim 15.
ID (u), (w): Note that A', and D' are simply random- random-subsamples of A, and D, respectively. Since we explicitly maintain A,, and D.,, we can also explicitly maintain these random subsamples as efficiently, and thus can maintain ID (u) and L (u) accordingly.
27


Reviews:
[{"review_id": "CDIrGShoHJ", "reviewer": "Reviewer_49Qm", "summary": "This paper studies the classic correlation clustering problem, where the objective is to partition objects into clusters while minimizing disagreements with given similarity and dissimilarity labels. The PIVOT algorithm by Ailon et al. (STOC’05) provides a 3-approximation for this problem, but its analysis is tight, and improving this bound has remained an open challenge.\n\nThe authors introduce MODIFIEDPIVOT, an extension of PIVOT that locally adjusts the clustering by moving vertices to different or new clusters. Their theoretical analysis proves that MODIFIEDPIVOT achieves an approximation ratio of 3 − Ω(1), improving prior results in dynamic settings. In particular, they show that in a fully dynamic environment, the algorithm maintains this improved approximation while handling updates in polylogarithmic time per operation (Theorem 1.1).\n\nAdditionally, the authors implement MODIFIEDPIVOT and evaluate it on real-world datasets, demonstrating that it makes less than 77% of the mistakes made by PIVOT on average, further validating its practical effectiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoughtful comments. We note that while indeed the improvement from 3 to 2.997 in the approximation ratio is rather small *quantitatively*, it breaks a longstanding barrier of 3-approximation for combinatorial algorithms and has an important *qualitative* value. Additionally, our experiments show that the improvement in the approximation ratio is much more drastic than this theoretical guarantee.\n\nIt is also worth pointing out that to break the 3-approximation analysis, our analysis deviates significantly from that of the original pivot algorithm and has to incorporate several new ingredients such as charging non-local triangles and fractional charges. Our hope is that these techniques prove useful in the future for providing analyses that go much below 3 or 2.997 approximations.\n\nThe time complexity of our Modified Pivot algorithm and the Pivot algorithm are the same once the parameters of the algorithm are fixed. We'll make sure to clarify this in the next version of the paper.", "claims_and_evidence": "The theoretical claims are supported by proofs while the benefit of the proposed algorithm over the standard pivot is supported by the conducted experiments.", "methods_and_evaluation_criteria": "Yes, both the proposed method and evaluation criteria make sense for the problem at hand.", "theoretical_claims": "Yes, they seem correct, although I did not check in detail.", "experimental_designs_or_analyses": "No issue found.", "relation_to_broader_scientific_literature": "The main contributions of this paper are closely tied to the classic PIVOT algorithm for correlation clustering, introduced by Ailon et al. (STOC’05), which is known to achieve a 3-approximation for the problem. The analysis of PIVOT is traditionally conducted through a charging scheme based on analyzing “bad triangles.”\n\nIn this paper, the authors introduce MODIFIEDPIVOT, an algorithm that improves upon the original PIVOT by achieving an approximation ratio of 3 − ε₀ for some absolute constant ε₀ > 0. This result is obtained through a novel charging scheme. MODIFIEDPIVOT provides a better-than-3 approximation in the dynamic setting with polylogarithmic time per update, improving the 3-approximation previously achieved by Behnezhad et al. (FOCS’19) and Dalirrooyfard et al. (ICML’24).", "essential_references_not_discussed": "Since the proposed MODIFIEDPIVOT algorithm relies on relocating certain nodes to new or alternative clusters compared to the standard PIVOT, it would be valuable for the authors to discuss related works (e.g., [1, 2]) that have applied local search optimization to the correlation clustering objective, starting from the solution provided by PIVOT. These studies have demonstrated the effectiveness of such an approach, aligning with the findings of this paper. While the authors provide a thorough characterization of cases where PIVOT fails, incorporating a discussion of related works would further strengthen the contextualization and significance of the proposed method.\n\n[1] An Efficient Local Search Algorithm for Correlation Clustering on Large Graphs. COCOA 2023.\n\n[2] In and out: Optimizing overall interaction in probabilistic graphs under clustering constraints. KDD 2020.", "other_strengths_and_weaknesses": "Strengths:\n\nS1) The paper effectively demonstrates, through examples and figures, where the standard PIVOT algorithm fails, which helps in clarifying the understanding of Algorithm 1.\n\nS2) The paper addresses an open problem in the literature: whether it is possible to maintain a 3 − Ω(1) approximation of correlation clustering in polylogarithmic time per update.\n\nS3) The charging scheme used to analyze the approximation factor of the proposed algorithm introduces some novel elements compared to the standard charging scheme applied to analyze the PIVOT algorithm.\n\nS4) The experiments empirically show that the MODIFIEDPIVOT algorithm leads to improvements in all cases across the datasets considered.\n\nWeaknesses:\n\nW1) The approximation factor of MODIFIEDPIVOT (2.997) is very close to that of the standard PIVOT (3). While there is an improvement, it appears to be quite marginal.\n\nW2) The time complexity overhead introduced by MODIFIEDPIVOT (in non-dynamic settings) compared to the standard PIVOT is not sufficiently addressed in the paper. Given that the improvement in the approximation factor (see W1) is relatively small, the additional computational cost may not be justified. A more detailed discussion of this trade-off would be valuable.\n\nW3) The description of the charging scheme algorithm (Algorithm 2) is not clear in the main paper. It would be beneficial to either move the pseudocode and the detailed explanation to the supplementary material, leaving only the intuition of the scheme in the main text, or provide a clearer and more detailed description within the main paper.\n\nW4) There is a need for a baseline that uses local search starting from the solution of PIVOT. If the such local search algorithm accepts only improvements, this would trivially preserve the 3-approximation of PIVOT, allowing for a clearer comparison and understanding of the potential benefits of the proposed modifications.", "other_comments_or_suggestions": "The explanation of the PIVOT algorithm before “Problem 1” repeats information already provided in the introduction, leading to some redundancy. It may be beneficial to streamline this section to avoid unnecessary repetition.\n\nOn page 2: “The figure below illustrates this. On the top, we have the optimal clustering. On the bottom, we have the output of PIVOT.”\n\nOn page 3, some edges in the first figure appear to be obscured by the blue shape representing the cluster. Clarifying or adjusting the visualization could improve readability and ensure all edges are clearly visible.", "questions_for_authors": "Q1) Could the authors clarify the time complexity overhead introduced by MODIFIEDPIVOT (in non-dynamic settings) compared to the standard PIVOT? Given that the improvement in the approximation factor (see W1) is relatively small, is the additional computational cost justified? A more detailed discussion of this trade-off would be appreciated.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "all8uXHr8D", "reviewer": "Reviewer_S7sb", "summary": "This paper presents a modification of the standard 3-approximation Pivot algorithm for correlation clustering (select a node in a graph, cluster it with its neighbors, and remove it) called ModifiedPivot, which avoids the worst-case errors of Pivot by clustering some its neighbors as singletons (if their neighborhood doesn't overlap well with the pivot's neighborhood), and by adding some of the pivots non-neighbors to the cluster (if they overlap well enough with the pivot's neighborhood). A careful analysis based on the bad triangle charging technique shows that the method has an approximation guarantee that is strictly better than 3, a barrier that standard pivot cannot overcome. Furthermore, modifiedPivot can be implemented in the fully-dynamic model with log^{O(1) n update time, providing the first better-than-three algorithm with such an update time in this model (previously, there was not even an O(n) update time for better-than-three approximation algorithms). In practice, the modified pivot algorithm leads to empirical improvements on a suite of real-world graphs and stochastic block models.\n\n## Update post rebuttal\nThanks for the reply and clarification. I maintain my positive view of the paper.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for pointing out the confusion regarding Algorithm 1, we will make sure to clarify this in the next version of the paper. To clarify this, the vertices in $A_v$ will be allowed to be picked as pivots later on, but even if they start clusters they won't themselves be added to those clusters and will be put in singleton clusters. This makes the algorithm easier to implement in the dynamic setting and elsewhere, because its output can be viewed as the output of the PIVOT algorithm which is then post-processed and locally improved. We will clarify this further in the text of the paper in its next version. \n\nIn our experiments, we tested at most 8 choices for each of epsilon and delta in all the runs, which adds up to at most 64 combinations. We will clarify this in the next version of the paper.", "claims_and_evidence": "Yes, the explanation of the algorithm itself at a high level is very sensible, and the main proof techniques and why they should be expected to work are outlined clearly. Several figures and discussions of the main techniques are provided throughout to help the reader. Empirical results also support the theoretical findings. Detailed proofs are provided to accompany the theoretical results, which are the main contribution of the paper.", "methods_and_evaluation_criteria": "The paper is primarily about theoretical results. The numerical experiments accompanying the theory are sensible and are performed on a standard collection of graphs used previously for correlation clustering experiments.", "theoretical_claims": "I followed the detailed explanation of the proof techniques that are provided at a high level throughout the text. The bad triangle charging scheme is standard in correlation clustering analysis and is a very sound approach. I confirmed at a high level that the pieces of the proof fit together and seem sound. However, the main technical results are contained in the dense 16 page appendix, and I did not check these for correctness.", "experimental_designs_or_analyses": "The experimental setup is sound.", "relation_to_broader_scientific_literature": "The text does a good job placing the paper within its broader context in the literature. In particular, there was previously no fully dynamic algorithm with even a linear update time that maintained a better than three approximation. Aside from settling this question in the fully dynamic setting, having a modified pivot algorithm that is practical and has a better than 3 approximation is a useful breakthrough result for correlation clustering. While better than 3 approximation algorithm exist, they are largely impractical. Meanwhile, there are many different practical methods that can achieve a 3-approximation or worse, but improving on factor 3 is a significant barrier.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "The key results of this paper is significant and has the potential to lead to other methods that break the factor-3 approximation barrier while actually being practical. It's also nice that the author have complemented their theoretical analysis with some experiments on real world graphs.\n\nOne small potential weakness in the experiments section is that it's unclear how many different epsilon and delta parameters were tried out in order to obtain the improved results. If in order to get good results, many parameter values need to be tested, then there is a runtime tradeoff to consider since standard pivot does not need to compute these. Thus, a more accurate comparison may be to run Pivot many times (with different permutations) and take the best result, if you are going to run to run ModifiedPivot many times (on the same permutation) with different choices of epsilon and delta. This is not a huge issue, as the main contributions of the paper are theoretical. However, depending on how many times parameter settings you need to try for epsilon and delta, there could be some weaknesses in the empirical results.", "other_comments_or_suggestions": "In Algorithm 1 you state \"We emphasize that even though vertices in $A_v$ get clustered here, they are not removed from $V$ in this step and so can be picked as pivots later.\"\n\nI'm confused by this and it seems contradictory. Saying that a node is already clustered (in this case as a singleton) suggests that in the final output clustering, the node will indeed just be in a singleton cluster. But saying that it could later be chosen as a pivot suggests that it could later be clustered with some of its neighbors (and significantly overlapping non-neighbors). I'm confused then as to how a node can simultaneously clustered already while possibly being a pivot later. I may have missed something, but I'm not sure how to reconcile this apparent contradiction.", "questions_for_authors": "How many choices of epsilon and delta do you have to test in your numerical experiments?\n\nCan you help me reconcile the apparent contradiction mentioned above in the \"other comments and suggestions\" section of my review?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oiFSNl8Kts", "reviewer": "Reviewer_fCwD", "summary": "The paper studied a variant of the pivot algorithm for correlation clustering and gave a dynamic implementation with polylog(n) update time and 2.997 approximation. Correlation clustering is a classical problem in TCS and machine learning. Here, we are given a labeled complete graph $G=(V, E^+ \\cup E^-)$, and the goal is to partition the vertices such that the total number of $(+)$ edges crossing clusters and $(-)$ edges inside the same clusters is minimized. \n\nIt is well known that the pivot algorithm could achieve a 3-approximation for correlation clustering in expectation. At a high level, the pivot algorithm samples a uniform permutation $\\pi$ for the set of vertices and recursively merges the yet-to-be-clustered neighbors of the lowest-ranked vertices to create clusters. \n\nThis paper follows a recent line of work that tries to break the 3-approximation barrier with combinatorial algorithms (e.g., CHS [SODA’24]; CLPTYZ [STOC’24]). The paper follows the framework of the pivot algorithm but additionally introduced some ideas in agreement decomposition as explored by, e.g., CLMNPT [ICML’21]; AW [ITCS’22]. In particular, the paper identifies the tackled the issues in the pivot algorithm of $i).$ merging neighbors with high disagreement neighborhoods and $ii).$ fails to merge non-neighbors with low disagreement neighborhoods. In this way, the paper obtained a $2.997$-approximation algorithm with much better empirical performances.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recommendation to run multiple experiments using different random seeds, especially since the Pivot algorithm is known to have instability. To clarify, Figures 1 and 2 already show both average and worst-case outcomes, based on multiple random seeds per dataset. As illustrated, our Modified Pivot algorithm demonstrates notably less instability compared to the pivot algorithm. We will emphasize this point more clearly in the revision.\n\nWe agree that writing the approximation number (2.997) explicitly in Theorem 1.1 improves readability. We will apply this change into the final version.", "claims_and_evidence": "Yes. The theoretical results are with proofs, and the algorithm design is reasonable.", "methods_and_evaluation_criteria": "Yes, the comparison of average and worst-case costs against the vanilla pivot algorithm shows the advantage of the modified pivot algorithm.", "theoretical_claims": "At a high level, the main technique of the paper resembles a blend of the pivot algorithm and the agreement decomposition algorithm. As discussed in the paper, the vanilla pivot algorithm suffers from the problem of clustering neighbors with a high disagreement and not being able to merge with non-neighbors with low disagreement. The intuitive fix of these problems would be to artificially add some of such vertices to the clustering formed by the vanilla pivot algorithm. Formally proving the approximation guarantee, on the other hand, requires some quite involved techniques in fractional triangle packing. I did not get time to carefully check the quantities in the charging argument, but the design makes sense to me in general.", "experimental_designs_or_analyses": "Yes, for the most part. However, from the experiment section, it is unclear whether the paper ran multiple experiments with different random seeds, especially given that the pivot algorithm is known to have a large variance for different choices of random seeds. See my comments in the criticism for details.", "relation_to_broader_scientific_literature": "Correlation clustering is an important problem in machine learning with broad applications. I believe the algorithm designed in this paper is quite practical.", "essential_references_not_discussed": "No missing essential references. On a side note, the cited work of CLMNPT [ICML’21] and AW [ITCS’22] did not use the pivot algorithm but instead used agreement decomposition. The current discussion on the right column of page 1 appears to allude that those results were also based on the pivot algorithm. Furthermore, there are some more recent results for correlation clustering in dynamic settings that are related to this work (e.g, ‘Dynamic Correlation Clustering in Sublinear Update Time’ [ICML’24] and ‘Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time’ [AISTATS’25]).", "other_strengths_and_weaknesses": "I’m in general supportive of the paper: correlation clustering is an important problem, and getting algorithms with both better theoretical bounds and empirical performances is an important direction to pursue. To the best of my knowledge, this is the first algorithm that achieves $<3$ approximation for dynamic correlation clustering in poly-logarithmic update time. Furthermore, compared to the combinatorial algorithm in CLPTYZ [STOC’24], the algorithm in this paper is much more practical. The paper also appears to be well-written, and the concepts are explained relatively well despite the charging argument being intrinsically involved. \n\nI do not see any major weaknesses in the work. However, I do think the paper could benefit from reporting the average cost for multiple runs of the pivot algorithm. This algorithm often suffers from instability and demonstrates very high costs in the worst case (see the experiments in, e.g., CLMNPT [ICML’21]; CLMP  [ICML’24]; BDPSW [AISATS’25]). Therefore, comparing the pivot algorithm with multiple random seeds looks more reasonable. (Maybe the paper already did so, but it’s unclear to me in the paper.)", "other_comments_or_suggestions": "I think $2.997$ is sufficiently smaller than $3$, so maybe writing this number out directly in Theorem 1.1 is better. $3-\\Omega(1)$ makes me think the $\\Omega(1)$ is some number like $10^{-10}$.", "questions_for_authors": "N/A, I do not have additional questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission presents an improved version of the classical pivot algorithm for correlation clustering. While the original version of this algorithm achieves a 3-approximation, the improved version achieves an approximation ratio of 2.997. While this seems to be a minor improvement, it break a long-standing barrier and is certainly a very important contribution. Also the experimental evaluation is valuable even though the reviewers have some comments on how to improve it. Overall, I consider this to be a strong contribution to ICML.
Decision: Accept (poster)