Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
Authors: Konstantin Makarychev
Sayak Chakrabarty
Venue: NeurIPS 2023 poster (2023)
Keywords: correlation clustering
Pivot algorithm
streaming
TL;DR: We show that a variant of the Pivot algorithm for Correlation Clustering gives a (3+eps) approximation in the single-pass semi-streaming model with O(n/eps) words of memory.

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

Single-Pass Pivot Algorithm for Correlation Clustering, Keep it simple!
Sayak Chakrabarty Northwestern University
Konstantin Makarychev Northwestern University
Abstract
We show that a simple single- pass semi semi-streaming variant of the Pivot algorithm for Correlation Clustering gives (3 + =) aapproximation using O(n/s) words of memory. This a slight improvement over the recent results Cambus, Kuhn, Lindy, Pai, and Uitto, who gave (3 e) >approximation using On log n) words of memory, and Behnezhad, Charikar, Ma, and Tan, who gave a 5-approximation using (n) words of memory. One of the main contributions of this paper is that both the algorithm and its analysis are very simple, and also the algorithm is easy implement.
Introduction
In this paper, we provide simple single-pass streaming algorithm for Correlation Clustering. The Correlation Clustering model was introduced by Bansal, Blum, and Chawla [2004]. In this model, we have set of objects represented by vertices of graph. A noisy binary classifier labels all edges of the graph with "+" and "_" signs. We call edges labeled with a "+" sign positive edges and edges labeled with "_" sign negative edges. A positive edge indicates that the endpoints of the edge similar, and a negative edge indicates that the endpoints are dissimilar. Given a labeled graph, our goal is to find clustering that disagrees with the minimum number of edge labels. A positive edge disagrees with the clustering if its endpoints are different clusters, and a negative edge disagrees with the clustering if its endpoints are in the same cluster. We assume that the classifier can make many errors and, consequently, there may be no clustering that agrees with all labels of the graph.
Correlation Clustering has been widely studied in ML and theoretical computer science communities. was used for image-segmentation (Kim et al. [2014]), link prediction (Yaroslavtsev and Vadapalli [2018]), document clustering (Bansal et al. [2004]), community detection (Veldt et al. [2018), Shi et al. [2021]), and other problems.
In Section 1.1, we discuss various objectives and assumptions used for Correlation Clustering. We now focus on the most common setting, where the graph G is complete graph (i.e., we have "+" or "_" label for each pair of vertices u and v)), the classifier can make arbitrary mistakes, and the objective is to minimize the number of disagreements.
In their original paper, Bansal, Blum, and Chawla [2004] gave a constant factor approximation for Correlation Clustering on complete graphs. Charikar, Guruswami, and Wirth [2005] improved the approximation factor to 4. Then, Ailon, Charikar, and Newman [2008] proposed combinatorial and LP-based PIVOT algorithms, with approximation factors 3 and 2.5, respectively. The La-dd PIVOT algorithm was further improved by Chawla, Makarychev, Schramm, and Yaroslavtsev [2015], who provided a 2.06 approximation. Finally, Cohen-Addad, Lee, and Newman [2022b] and Cohen-Addad, Lee, Li, and Newman [2023] used Sherali-Adams relaxation for the problem to obtain 1.994 + e and 1.73 + e approximations, respectively. On the hardness side, Charikar, Guruswami, and Wirth [2005] proved that the problem is APX-Hard and thus unlikely to admit a PTAS.
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Most abovementioned algorithms use linear programming (LP) for finding a clustering. The number of constraints in the standard LP is ((n)) (due to "triangle inequality constraints"). Solving such LPs is prohibitively expensive for large data sets?. That is why, in practice, the algorithm of choice is the combinatorial PIVOT algorithm by Ailon et al. [2008] along with its variants. The approximation factor of this algorithm is 3.
To deal with massive data sets, researchers started exploring parallel (MPC) and semi-streaming algo- rithms. Recent works on MPC algorithms include Blelloch, Fineman, and Shun [2012], Chierichetti, Dalvi, and Kumar [2014], Pan, Papailiopoulos, Oymak, Recht, Ramchandran, and Jordan [2015], Ahn, Cormode, Guha, McGregor, and Wirth [2015], Ghaffari, Gouleakis, Konrad, Mitrović, and Rubinfeld [2018], Fischer and Noever [2019], Cambus, Choo, Mikknen,, and Uitto [2021]. Cohen- Addad, Lattanzi, Mitrović, Norouzi-Fart Fardd Parotsidis, and Tarnawski [2021], Assadi and Wang [2022], Cambus, Kuhn, Lindy, Pai, and Uitto [2022], Behnezhad, Charikar, Ma, and Tan [2022].
Streaming algorithms have been extensively studied by Chierichetti, Dalvi, and Kumar [2014], Ahn, Cormode, Guha, McGregor, and Wirth [2015], Ghaffari, Gouleakis, Konrad, Mitrovié, and Rubinfeld [2018], Cohen-Addad, Lattanzi, Mitrović, Norouzi-Fard, Parotsidis, and Tarnawski [2021]. Assadi and Wang [2022], Cambus, Kuhn, Lindy, Pai, and Uitto [2022]. Behnezhad, Charikar, Ma, and Tan [2022. 2023]. This year, Behnezhad, Charikar, Ma, and Tan [2023] designed a single-pass polynomial time semi-streaming 5-approximation algorithm that uses (n) words of memory. Then, Cambus, Kuhn, Lindy, Pai, and Uitto [2022] provided single-pass polynomial -ime semi- -mm-sttramingg (3 + approoximatoo algorithm that uses On log n) words of memory. Both algorithms are based on the combinatorial PIVOT algorithm.
Our Results. In this paper, we examine a simple semi-streaming variant of the Ailon, Charikar, and Newman [2008] combinatorial PIVOT algorithm that uses (n/E) words of memory and gives 3 + approximation. Our algorithm needs less memory than the algorithm by Cambus. Kuhn, Lindy, Pai, and Uitto [2022] and gives the same (3 + E) approximation guarantee. The algorithm is very simple and easy to implement. Its analysis is simple and concise.
We note that one can take advantage of the low memory footprint of our algorithm even in non- streaming setting. We provide some experimental results in Appendix (see Figure 2).
Semi-streaming Model. We consider the following single-pas, semi-streaming model formally defined by Feigenbaum, Kannan, McGregor, Suri, and Zhang [2005] (see also Muthukrishnan [2005]). The algorithm gets edges of the graph along with their labels from an input stream. The order of edges in the graph is arbitrary and can be adversarial. The algorithm can read the stream only once. We assume that the algorithm has Okk) words of memory, where & a constant. Thus, it cannot store all edges in the main memory. As in many previous papers streaming algorithms for Correlation Clustering, we shall assume that the stream contains only positive edges (if negative edges are present in the stream, our algorithm will simply ignore them). We prove the following theorem.
Theorem 1.1. Algorithm I (see Figure 1) is randomized polynomial-tin time semi- streaming algorithm with an approximation factor 3 + (1/k). The algorithm uses Okk) words of memory, where each word can store numbers between 1 and The algorithm spends at most Olog k) units of time for every edge it reads in the streaming phase. Then, it requires additional Olkn) units of time to find a clustering (in the pivot selection and clustering phase).
1.1 Related Work
In this paper, we consider the most commonly studied objective, MINDISAGREE, of minimizing the number of disagreements. Swamy [2004] and Charikar, Guruswami, and Wirth [2005] investigated complementary objective, MAXAGREE, of maximizing the number of agreements. They gave 0.766-approximation algorithms for MAXAGREE. Puleo and Milenkovic [2016), Chierichetti, Kumar, Lattanzi, and Vassilvitskii [2017], Charikar, Gupta, and Schwartz [2017], Ahmadi, Khuller, and Saha [2019], Kalhan, Makarychev, and Zhou [2019], Ahmadian, Epasto. Kumar, and Mahdian [2020], Friggstad and Mousavi [2021], Jafarov, Kalhan, Makarychev, and Makarychev [2021], Schwartz and Zats [2022], Ahmadian and Negahbani [2023], Davies, Moseley, and Newman [2023] considered several variants of fair and local objectives.
Veldt [2022] recently proposed practical linear programming algorithm for Correlation Clustering.
2

---

Initialization phase
Pick random ordering of vertices π V - (I.....n]
For each vertex u E V:
Create priority queue A(u) capped at size k and initialize A(u) = {u}.
Streaming phase
For each edge (u, v) E:
Add u to A(v). Add v to A(u). Remove the lowest ranked elements from A(u)
and A(v), if necessary, make sure that they contain at most &s elements.
Pivot selection and clustering
For each not-yet clustered vertex V chosen in the order of n: Find the highest ranked vertex e in A(u) such that v = u or e is a pivot i.e.,
V = argmin (v) : = u or is pivot}.
vEA(u)
If such vertex v exists, place u in the cluster of v. If u mark u as pivor. Else, place a singleton cluster. Mark u as a special singleton.
For each pivot vertex u, output the cluster consisting of all vertices clustered with u. Then, output all special singleton vertices, each in its own clusters.
Figure I: Semi- Somi-Streaming Algorithm for Correlation Clustering
Charikar, Guruswami, and Wirth [2005] and Demaine, Emanuel, Fiat, and Immorlica [2006] provided O(log n) approximation for Correlation Clustering on incomplete graphs and edge-weighed graphs. For the case when all edge weights are in the range (a,, 1]. Jafarov, Kalhan, Makarychev, and Makarychev [2020] gave a (3 + 1n a/p-appooooiiiiioinnn algorithm.
The problem has also been studied under the assumption that the classifier makes random semi- random errors by Bansal, Blum, and Chawla [2004], Elsner and Schudy [2009], Mathieu and Schudy [2010], Makarychev, Makarychev, and Vijayaraghavan [2015]. Online variants of Correlation Clustering were considered by Mathieu, Sankur, and Schudy [2010], Lattanzi, Moseley, Vassilvitskii, Wang, and Zhou [2021], Cohen-Addad, Lattanzi, Maggiori, and Parotsidis [2022a].
2 Single-Pass Streaming Algorithm
Our algorithm is an extension of the algorithm by Behnezhad, Charikar, Ma, and Tan [2023]. Loosely speaking, the algorithm works as follows: It picks a random ranking of vertices, scans the input stream and keeps only the top-ranked neighbours for every vertex u. Then, runs the Ailon, Charikar, and Newman [2008] PivoT algorithm on the graph that contains only edges from every vertex to its & tankedd neighbours. We provide the details below.
We shall assume that every vertex is connected with itself by positive edge. In other words, we include each vertex the set of its own (positive) neighbours. denote the set of positive neighbours of u by (u)). The algorithm first picks a random ordering of vertices π V - (1..... n2.. We say that vertex is ranked higher than vertex e according to π if TTu) < T()). Therefore, x = (1) is ) is the lowest ranked vertex. For every vertex u, we will keep
the highest ranked vertex, and π -1() track of its highest-ranked neighbours. We denote this set by A(u). We initialize each A(u) = (u). Then, for every positive edge (u, v) in the input stream, we add to the set of v's neighbours A(v) and a to the set of u's neighbours A(u). If A(u) or A(v) get larger than k. we remove the lowest ranked vertices from these sets to make sure that the sizes of A(u) and A(v) are most k. After we finish reading all edges from the input stream, we run the following variant of the PIVOT algorithm. We mark all vertices non-pivots. Then, consider vertices according to their ranking (i.e., x (1), - (2),......) x x>'((") (n)). For every vertex u, we find the highest ranked neighbour e in A(u), such that we declare u a pivor. If no such v in A(u) exists, we put u in its own cluster and declare a special singleton. We provide pseudo-code for this algorithm in Figure 1.
is pivor. If such exists, we place in the cluster of v. Moreover, if u
We use fixed-size priority queues to store sets A(u). Whenever we need add a vertex v to A(u). we insert into A(u) and remove the lowest-ranked element from A(u) if the size of A(u) is greater
3

---

than k. We remark that even though each u is always added to set A(u) in the beginning of the algorithm, may later be removed if is not among its top-neighbours.
We can reduce the memory usage of the algorithm by adding u to A(u) only if ((u) < 7()) and adding v to A(u) only if (w) < =(u). This change does not affect the resulting clustering because is always added to A(u), and, consequently, we never pick pivot v with (v) > T(u) at the clustering phase of the algorithm. Nevertheless, simplify the exposition, we will assume that we always add u to A(v) and v to A(u).
In this paper, we will call clusters special singleton clusters if they were created in the "else" clause of the clustering phase. That is, if they contain a single vertex u, which is not pivot. Note that some other clusters may contain a single vertex as well. We will not call them special singleton clusters.
Before analyzing the approximation factor of the algorithm, we briefty discuss its memory usage and running time. For every vertex u, we keep its rank rTu), set of its k highest ranked neighbors A(u), a pointer to the pivot if u is not a special singleton, and two bits indicating whether is a pivot and whether is special singleton cluster. Thus, the total memory usage is (Kk) words; each word is an integer that can store a number between 1 and n.
The running time of the initialization step is O(n). The worst-case running time of the streaming phase is O(m log k) where m is the number of positive edges (the algorithm needs to perform a constant number of priority queue operations for each edge in the stream; the cost of each operation is Ollo k)). The expected running time of the streaming phase of the algorithm is O(m + nk log k log (2m/((n) if m > nk. is (m) if m > nk log & log log k. The running time of the clustering phase (kn), since we need to examine all neighbors v of u in queue A(u).
2.1
Approximation Factor
We now show that the approximation factor of the algorithm is 3 + O(1kk. For the sake of analysis, we consider an equivalent variant of our algorithm that reveals the ordering π one step at time. This variant of the algorithm is not a streaming algorithm, per se. However, it produces exactly the same clustering as our single-pass streaming algorithm. Thus, it is sufficient to show that it has a 3 + ((1/k) approximation. The algorithm, which we will refer to as Algoritim 2, works as follows. Initially, it marks all vertices as unprocessed and not clustered. It also sets counter K₁ (u) = 0 for each u. We denote the set of all unprocessed vertices at step by V22 and the set of all non-clustered vertices by U.. Then, V1= = V and U1 = V. At step f, the algorithm picks a random vertex w, in V,. If w, is not yet clustered (w, E U2), then is marked as pivot, new cluster is created for wy, and all not yet clustered neighbours of w, including w. itself are added to the new cluster. If w, is already clustered, then the counter K₃ K2(v) is incremented by 1 for all not yet clustered neighbours of wi (i.e., K (v) = (x) + 1). After that, all vertices v, whose counter Kz+1 (v) got equal to & at this step, are put into special singleton clusters. We mark w/ as processed (by letting V4+1 = V, \ (w)) and mark all vertices clustered at this step as clustered (by removing them from U.).
We show that this algorithm outputs the same clustering as Algorithm 1. To this end, define an ordering π for Algorithm 2 as т w. + f, where w, the vertex considered step & of Algorithm 2. Clearly, π is a random (uniformly distributed) permutation. We prove the following lemma.
Lemma 2.1. If Algorithm and Algorithm 2 use the same ordering n, then they produce exactly the same clustering V.
Proof. We show that every vertex u assigned to the same pivot v in both algorithms, or u is put in a special singleton cluster by both algorithms assuming that Algorithms I and 2 use the same ordering и. The proof by induction on the rank (u). Consider vertex u and assume that all vertices u higher ranked than u are clustered in the same way by Algorithms I and 2. Both algorithms examine
'The probability that the i-th neighbour of is among the top & already considered neighbours of is min(k/t, 1). Thus, the probability that the i-th neighbour inserted in the priority queue A(u) is min(k/i, 1). The expected number neighbours inserted in the queue for vertex u at most + O(k log(1 + [N(w)))R)) Each insertion takes O(log k) units of time. Therefore, the total time spent on the insertion operations is upper bounded by (here we use Jensen's 's inequality for function log x))
Olog log k. Σ "
Ic + &s log (1 + IN(w))))) < O(kk log ks (1 + log (1+ 2m
)))
km

---

neighbours of in exactly the same order, x. Moreover, they only consider the top k neighbous:: Algorithm 1 does so because it stores neighbours of u in priority queue of size k; Algorithm 2 does so because it keeps track of the number, (u),, of examined neighbours of u and once that number equals k it puts u in special singleton cluster. Both algorithms assign u to the first found pivot vertex U or to a special singleton cluster if no such v exists among the top k neighbours of u. Hence, both algorithms cluster u in the same way.
We now analyze Algorithm 2. We split all steps of Algorithm 2 into pivot and singleton steps. We say that step / a pivot step if vertex W; which was processed at this step was not clustered at the beginning of the step (i.e., wy E Ut). We say that / is singleton step, otherwise (i.e., W; E Vt. \ U.). Observe that all clusters created at pivot steps are not special singleton clusters (even though some of them may contain single vertex; see above for the definition of special singleton clusters). In contrast, all clusters created at singleton steps are special singleton clusters. We will now show that the expected cost of clusters created at pivot steps is at most 30PT. Then, we will analyze singleton steps and prove that the cost of clusters created at those steps is at most O(1/k) OPT, in expectation (where O OT is the cost of the optimal solution).
We say that a positive or negative edge (u, v) is settled at step if both u and e were not clustered at the beginning of step / but u, c, or both and were clustered at step l. Note that once an edge (u, v) settled, we can determine if (u. is in agreement or disagreement with the clustering produced by the algorithm: For a positive edge u) E E+ if both and v belong to the newly formed cluster, then (u. v) in agreement with the clustering. For a negative edge (u, u) E F= if both u and e belong to the newly formed cluster, then (u, v) is in disagreement with the clustering. Similarly, only one of the endpoints u or belongs to the new cluster, then (u, v) is in agreement with the clustering for a negative edge (u, v) E E and in disagreement with the clustering for positive edge (u, v) E E+. In the latter case, we say that a positive edge (u, v) E E is cut by the algorithm, and we call (u, v) a cut edge.
We say that the cost of a settled edge is 0 if agrees with the clustering and if it disagrees with the clustering. Let P be the cost of all edges settled during pivot steps. Furthermore, let P+ be the cost of all positive edges and P- be the cost of all negative edges settled during pivot steps. Then, P= P- + P- If v is singleton cluster, let S(e) be the number of positive edges incident to v the algorithm cut when it created this cluster. Note, that some edges incident to might have been cut before was put in singleton cluster. We do not count these edges in S(v).
Every edge which is in disagreement with the clustering is (1) positive edge cut at a pivot step of the algorithm; (2) negative edge joined at pivot step of the algorithm: or (3) positive edge cut at a singleton step of the algorithm. Hence, the cost of the algorithm equals:
ALG = p + P + Σ S(v).
VEV
Lemma 2.2. We have E(P+ + P 30PT.
Remark: This lemma implics that E[Pt] < 30 We note that we could get a slightly stronger bound: E 1 20PT, which would yield slightly stronger upper bound on E|E, S(v)] (see below).
Proof. Observe that pivot steps are identical to the steps of the PIVOT algorithm. That is, given that W. belongs to Ue, the conditional distribution of w, is uniform in Ug and the cluster created at this step contains W; and all its positive neighbours. Let us fix optimal solution. Let O be the set of edges in the optimal solution that disagree with the classifier. Denote the cost of the optimal solution by OPT = |O"|. Ailon, Charikar, and Newman [2008] proved that the expected cost of the solution produced by the PIVOT algorithm is upper bounded by 3T. Furthermore, they showed that the expected cost of edges settled at step is upper bounded by 3 3E[AOPT.), where ΛOPT, is the number of edges from O" settled by PIVOT at step (see also Lemma 4 in Chawla et al. [2015]). Therefore, the expected total cost of all edges settled at pivot steps of our algorithm is upper bounded by 3E E is pivot step AO PT.). The number of all edges in O* settled at pivot steps is upper bounded by the size of O", which equals OPT. Hence, E[P+ + + P-1 30PT.
We now bound EIE,, S.)).. Fix a vertex v. Let Nww) be the set of all vertices connected with by a positive edge ("positive similar neighbours"), and (v)) be the number of positive neighbours of
5

---

including v itself. We now define new quantity X1()). If e is not in a singleton cluster at step t, then let (v) be the number of positive edges incident on v cut in the first t- steps the algorithm. Otherwise, let (v) be the number of positive edges incident on v cut by the algorithm before was placed in the singleton cluster. The number of edges incident to v cut by the algorithm equals
(+) + S(v). Hence, the total number of cut positive edges equals 2 E EvEv (Xn+1(v) + 5()). It also equals p+ + EVEV S(U). Thus, EvEr Xn+1(e) (v) = =2 + LVEV S(v) and
E
Σ (o)
E E2P
E((e) - 60PT+ E
Σ
S(u)
VEV
NEV
DEV
We now show that E[S(v)] < 1/4 e[Xx+1(1)) for all e and, therefore,
6OPT
E
Σ
S(u)
k k-1
VEV
and
E[ALG] E pt + P +
Σ
S(w) $ (3+ 5(3 k- )
6
.EV
To finish the analysis of Algorithm 2, it remains to prove the following lemma. Lemma 2.3. We have E[S(v)] s <//x (()n+1(v)].
Proof. Define the following potential function:
(2)) 1(v & U.) Xi(v) Ke(v) (IN(0)) Xx(u)).
where 1(v & U2) is the indicator of event {u & Uz}. Let Fe be the state of the algorithm at the beginning step We claim that (u) is submartingale i.e., ElL141(u) Fi] 2 (u)..
Claim 2.4. (v) is submartingale.
Proof. Consider step of the algorithm. If is already clustered (i.c., & Ut), then all edges incident on are settled and terms 1(v & U2), Kz(v), and (v) no longer change. Hence, the potential function (v) does not change as well.
Suppose that E U.. If at step f, the algorithm picks wi not from the neighbourhood N(v), then v does not get clustered at this step and also Kz(v) does not change. The value of (1) may increase some neighbours of may get clustered. However, Xx(v) cannot decrease. Therefore, (1) (v)v), and E (v) (v) w, (N); Fi] 2 O.
Let us now assume that step the algorithm chooses w, from the neighbourhood of Then, is clustered with conditional probability at least
Pr W E N(v) nU w, E N(O)::)) = [(v) n U. [N(
because if the pivot is chosen in (())nU, then u is put in the cluster of w. We have (N) = [N(w)] - (v),,, since every clustered neighbour e contributes to the number of cut edges (v))). and the total number of v's positive neighhours equals (N)) Also, note that (N < (N()). Hence,
[N(o)--X(00 N(O)
Pr We E N(b) w, E N();:.)
With this conditional probability, 1(v & U2) gets equal to at step t, and, result, (,(v) increases by X1+I(U) 2 Xz(v). With the remaining probability, (v) increases by 1, and, as a result, (v) decreases by at most [N(e)] (v) & [N(u)] (1)... Thus,
[N(x) - X((v) xx(1)- [N(x)
X((r) [N(x) (((()) 0.
E (1)) we E N(v): Fi
This concludes the proof.

---

Since 11 (o) 0 and (.(v) is submartingale, we have E[ 2 0. Therefore,
E X (v)] E & Un+1) Xn+1(u)] 2 E (v) (IN(()) - (u))
o is in a singleton cluster, then Kn+1(u) = and ( + ((v) = [N()) (because all positive edges incident to u cut). Hence,
kS(v) Kn+1 (v) ((N(0)I-N+11(0))
I is not in singleton cluster, then S(v) 0. Thus, always have k:((v) < (n+1(1) (IN(e)
(t)) Consequently, 1 (1)] 2 {E])(
Acknowledgments and Disclosure of Funding
Konstantin Makarychev supported by NSF Awards 2216970. The authors would like to thank the anonymous reviewers for their valuable comments.
CCF- CCF-1934931, EECS-29
References
S. Ahmadi, S. Khuller, and B. Saha. Min-max correlation clustering via multicut. In Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings, pages 13 26. Springer, 2019.
Ahmadian and M. Negahbani. Improved approximation for fair correlation clustering, In Interna- tional Conference on Artificial Intelligence and Statistics, pages 9499-9516. PMLR, 2023.
S. Ahmadian, Epasto, R. Kumar, and M. Mahdian. Fair correlation clustering. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2020.
K. Ahn, G. Cormode, Guha, A. McGregor, and Wirth. Correlation clustering in data streams. In International Conference on Machine Learning, pages 2237-2246. PMLR, 2015.
N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008.
S. Assadi and C. Wang. Sublinear time and space algorithms for correlation clustering via sparse- dense decompositions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), 2022.
N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine learning, 56:89-113, 2004.
S. Behnezhad, M. Charikar, W. Ma, and L.-Y. Tan. Almost 3-approximate correlation clustering in constant rounds. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 720-731. IEBE, 2022.
Behnezhad, M. Charikar, W. Ma, and L.-Y. Tan. Single-pass streaming algorithms for correlation clustering. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), pages 819-849. SIAM, 2023.
G. F. Blelloch, J. T. Fineman, and J. Shun. Greedy sequential maximal independent set and matching are parallel on average. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures, pages 308-317, 2012.
M. Cambus, D. Choo, H. Miikonen, and J. Uitto. Massively parallel correlation clustering in bounded arboricity graphs. In 35th International Symposium on Distributed Computing (DISC 202 Schloss Dagsttull-Lcibnii-ZZeeiee
für Informatik, 2021. 2021.
M. Cambus, Kuhn, E. Lindy, S. Pai, and J. Uitto. A parallel algorithm for (3 + z) approximmte correlation clustering. arXiv preprint arXiv:2205.075:: 2022.
M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. Journal of Computer and System Sciences, 7 7103):360-38,, 2005.

---

M. Charikar, N. Gupta, and R. Schwartz. Local guarantees in graph cuts and clustering. In Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 136-147. Springer, 2017.
S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal Ip rounding algorithm for correlationclustering on complete and complete k-partite graphs. In Proceedings of the forty- seventh amnual ACM symposium on Theory of computing, pages 219-2219220 2222 2015.
Chierichetti, N. Dalvi, and R. Kumar. Correlation clustering in mapreduce. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 641-650, 2014.
Chierichetti, Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. Advances in neural information processing systems, 30, 2017.
V. Cohen-Addad, S. Lattanzi, S. Mitrovié, A. Norouzi-Fard, N. Parotsidis, and J. Tarnawski. Cor- relation clustering in constant many parallel rounds. In International Conference on Machine Learning, pages 2069-2078. PMLR, 2021.
V. Cohen-Addad, S. Lattanzi, A. Maggiori, and N. Parotsidis. Online and consistent correlation clustering. In International Conference on Machine Learning, pages 4157-4179. PMLR, 2022a.
V. Cohen-Addad, E. Lee, and A. Newman. Correlation clustering with 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 651-661. IEEE, 2022b.
In 2022 IEEE
V. Cohen-Addad, E. Lee, S. Li, and A. Newman. Handling correlated rounding error via preclustering: 1.73-approximation for correlation clustering. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2023.
S. Davies, B. Moseley, and H. Newman. Fast combinatorial algorithms for min max correlation clustering. In 40th International Conference on Machine Learning (ICML'23) 2023.
E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172-187, 2006.
M. Elsner and Schudy. Bounding and comparing methods for correlation clustering beyond ilp. In Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing, pages 27-27, 2009.
Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. On graph problems in a semi- streaming model. Theoretical Computer Science, 348(2-3):207-216 2005.
M. Fischer and A. Noever. Tight analysis of parallel randomized greedy mis. ACM Transactions on Algorithms (TALG), 16(1):1-13, 2019.
Z. Friggstad and R. Mousavi. Fair correlation clustering with global and local guarantees. In Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9-11, 2021, Proceedings 17, pages 414 427. Springer, 2021.
M. Ghaffari, T. Gouleakis, C. Konrad, S. Mitrović, and R. Rubinfeld. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium Principles of Distributed Computing, pages 129-138, 2018.
J. Jafarov, S. Kalhan, K. Makarychev, and Y. Makarychev. Correlation clustering with asymmetric classification errors. In International Conference on Machine Learning, pages 4641 46500. PMLR, 2020.
Jafarov, Kalhan, K. Makarychev, and Y. Makarychev. Local correlation clustering with asym- metric classification errors. In International Conference on Machine Learning, pages 4677-4686. PMLR, 2021.
S. Kalhan, Makarychev, and T. Zhou. Correlation clustering with local objectives. Advances in Neural Information Processing Systems, 32, 2019.

---

S. Kim, C. D. Yoo, S. Nowozin, and P. Kohli. Image segmentation usinghigher-order correlation clustering, IEEE transactions on pattern analysis and machine intelligence, 36(9):1761-1774. 2014.
S. Lattanzi, B. Moseley, S. Vassilvitskii, Y. Wang, and R. Zhou. Robust online correlation clustering. Advances in Neural Information Processing Systems, 34:4688 0694688-4688, 2021.
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Correlation clustering with noisy partial information. In Conference Learning Theory, pages 1321 1342. PMLR, 2015.
C. Mathieu and W. Schudy, Correlation clustering with noisy input. In Proceedings of the twenty-first anmual ACM-SIAM symposium on Discrete Algorithms, pages 712-728. SIAM, 2010.
C. Mathieu, O. Sankur, and W. Schudy. Online Correlation Clustering. In J.-Y. Marion and T. Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Sci- ence, volume 5 of Leibniz International Proceedings in Informatics (LJPless) pages 573-584, Dagstuhl, Germany, 2010. Schloss Bogstuul-LeibbizzZZan 939897-16-3. doi:
fuer Informatik, ISBN 978-3- URL http://drops dagstuhl. /dettuhllde//
opus/volltexxee22010//
Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 122):117-236, 2005.
X. Pan, D. Papailiopoulos, S. Oymak, B. Recht, K. Ramchandran, and M. I. Jordan. Parallel correlation clustering on big graphs. Advances in Neural Information Processing Systems, 28, 2015.
G. Puleo and O. Milenkovie. Correlation clustering and biclustering with locally bounded errors. In International Conference Machine Learning, pages 869-877. PMLR, 2016.
R. Schwartz and R. Zats. Fair correlation clustering in general graphs. In Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Schloss Ceassuull-eibbiizzeentee
für Informatik, 2022.
J. Shi, L. Dhulipala, D. Eisenstat, Łăcki, and V. Mirrokni. Scalable community detection via parallel correlation clustering. Proceedings of the VLDB Endowment, 14(11)2205-2233, 2021.
C. Swamy, Correlation clustering; maximizing agreements via semidefinite programming. In SODA, volume 4, pages 526-527. Citeseer, 2004.
N. Veldt. Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. In International Conference on Machine Learning, pages 22060-22083. PMLR, 2022.
N. Veldt, D. F. Gleich, and A. Wirth. correlation clustering framework for community detection. In Proceedings of the 2018 World Wide Web Conference, pages
2018.
G. Yaroslavtsey and A. Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under I, distances. In 35th International Conference on Machine Learning (ICML'18), 2018.

---

A Figures
1.5
K-nn graph for Gaussian mixture with K -25; 100,000 points
1.45
K-nn graph for Gaussian mixture with バ -50; 200,000 points
1.4
1.35
1.3
1.25
1.2
1.15
1.1
1.05
1
0.95
9
cost
Figure The cost of the clustering obtained by our algorithm comparing with the cost of the clustering obtained by the PIvoT algorithm for different values of k. The input graph is the K -earestt neighbour graph for the Gaussian mixture model.
10


Reviews:
[{"review_id": "3UyRgAgZCC", "reviewer": "Reviewer_tNUH", "summary": "This paper considers the problem of correlation clustering on a complete graph, where all the edges are assigned either \"+\" or \"-\". The goal is to come up with a clustering that maximizes agreement with the edge labels. This is a well studied problems in approximation algorithms. There is an elegant 3 approximation due to ACN called PIVOT: pick unclustered vertices in random order, create a cluster for each such vertex and all unclustered neighbors that have a + edge to it. The analysis is similarly simple and elegant. \n\nThis paper considers the semi-streaming model. where the edges arrive one at a time. It is not obvious how the ACN version of PIVOT works in this model, since we do not know all the neighbors of a vertex v when processing it. A recent paper due to Behnezhad et al gives a 5 approximation for a variant of PIVOT. Their algorithm  gives a 5 approximation in O(n) space, but its analysis is subtle and a little tedious. \n\nThis paper presents another variant of pivot which gives a 3 +eps approximation, again in O(n/eps) space. The analysis is arguably simpler (but to my taste, not as simple as the original PIVOT algorithm).  Previously, there was a 3 +eps algorithm, but that needed n log n space. ", "questions": "When you say that the stream only consists of positive edges, it is worht pointing out that you are working on the complete graph and the remainder of the edges are assumed to be negative.", "limitations": "none", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "It is nice to have both a simple algorithm and a simple analysis for a very natural problem. This paper deserves to be published somewhere. ", "weaknesses": "The contribution feels somewhat incremental.  We had a simple algorithm that gave a 5 approximation in O(n) space, as well as a 3 + eps approximation in O(n log n) space. This paper gives 3 + eps with a simple algorithm and analysis, and O(n/eps) space. In some sense, it gets the best of all worlds. \n\nI am not entirely convinced that either then space reduction or factor improvement ranks as a important enough contribution at a top ML venue like neurips. For calibration, I dont think this would get into a top tier theory venue, but I'd be fine with accepting it to a next-tier conference. If some area expert thinks this is the case, I'd be open to changing my mind. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__When you say that the stream only consists of positive edges, it is worth pointing out that you are working on the complete graph and the remainder of the edges are assumed to be negative.__\n\nThank you! That's correct. We will clarify this point in the final version of this paper."}, {"review_id": "PCiDr5eLsR", "reviewer": "Reviewer_mH8W", "summary": "This paper provides a streaming algorithm for correlation clustering on complete graphs that uses O(n/eps) space and has an approximation factor of 3+eps. The algorithm is based on the combinatorial pivot algorithm. \n\nThe prior results in the streaming setting give 5 approx in the better space of O(n); and another result with 3+eps approx in space O(n log n). They are also based on the combinatorial Pivot algorithm.\n\nThe best offline approximation for the problem achieves a factor below 2, but the best approximation factor based on the combinatorial pivot algorithm achieves a factor of 3.", "questions": "Minor comments:\nPage 1, sings -> signs\nIn description of Algorithm 2, did you mean U_1 = V as opposed to U_1=U?", "limitations": "NA", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Matches the best offline approximation based on combinatorial Pivot algorithm\n\nThe algorithm is simple and thus practical to implement, and the proof is very clean.", "weaknesses": "They provide a code in the supplementary material but no experimental results comparing this algorithm with the prior works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "You are right $U_1 = V$. Thank you!"}, {"review_id": "GlYSsPJxe1", "reviewer": "Reviewer_aXJT", "summary": "This paper demonstrates that the celebrated Pivot algorithm for (unweighted, complete) correlation clustering (with the min disagreements objective) can be adapted to the single-pass, semi-streaming setting, to yield a (3+\\eps)-approximation in expectation using O(n/eps) words of memory. (Note that the original Pivot algorithm gives a 3-approximation in expectation.) This improves on previous works that show a (3+\\eps)-approximation using O(n\\log n) words of memory, and a 5-approximation using O(n) words of memory. In the single-pass, semi-streaming setting, edges and their labels arrive online adversarially and the stream can only be read once. It is assumed that only positive edges arrive and the remaining edges in the complete graph are implicitly negative. \n\nThe Pivot algorithm chooses a random permutation of the vertices, visits each vertex in this order, and if a vertex is unclustered, makes that vertex a \"pivot.\" The pivot grabs its unclustered positive neighbors from the remaining sequence and forms a cluster. The algorithm proposed in this paper tweaks the Pivot algorithm by again choosing a random permutation of the vertices, but for each vertex it only retains positive edges to the top-k ranked neighbors in this permutation. It then runs Pivot on this subgraph, using the chosen random permutation. The analysis rests on controlling the cost of (positive) edges cut by special vertices called \"singleton vertices.\" These are vertices u whose top-k positive neighbors all come before u, but none are chosen as pivots, so u ends up in a singleton cluster. (Controlling the cost of other edges is done by reusing the analysis of Pivot, since these edges are cut by the pivot vertices.) The crux of the argument controlling the cost of singleton vertices is to show that a certain potential function is always positive in expectation, which in turn comes from showing it is a submartingale. ", "questions": "n/a", "limitations": "n/a", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The algorithm is a pleasingly simple variant of the Pivot algorithm. It lends insight into just how much \"wiggle room\" there is in the original Pivot algorithm, as it might a priori seem surprising that we only need retain the top-k ranked neighbors of each vertex. \n\n- The analysis (particularly the main lemma, which designs a novel potential function and shows it is a submartingale) is quite elegant. Moreover, it is substantially simpler than analyses in the aforementioned previous works on the semi-streaming setting. \n\n- This paper contributes to the growing literature on how the Pivot algorithm can be adapted to other models of computation (in addition to streaming, parallel models such as MapReduce). While the result itself is not a significant improvement over known results, and the algorithm is of comparable simplicity to previous ones, it provides a much cleaner analysis. ", "weaknesses": "While the paper is overall clear and well-written, it would be useful to give a bit more background comparing the proposed algorithm to those in prior work in the semi-streaming setting.  \n\nSome typos / omissions in the writing: \n- U_t on pg. 6 is seemingly meant as the complement of how it is defined on pg. 4 \n- D^+(v) = |N(v)| on pg. 5 \n- It would be good to add a line stating formally what it means to \"cut\" at an edge (although it is clear from context)\n\nAnd a suggestion: The use of the term singleton is a bit confusing, since, as the authors mention, not all singleton clusters correspond to \"singletons\" as defined in the Pivot selection and clustering section of Figure 1. It may be worth just using a distinct term altogether for such vertices.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestions! We will revise the introduction and include more background on the prior work. We will also use a different name for \"singletons\". Finally, we will fix the _typos/omissions_."}, {"review_id": "Gmru7Cc56O", "reviewer": "Reviewer_mSWo", "summary": "The paper studies the correlation clustering problem in the semi-streaming model obtaining a $(3+\\varepsilon)$-approximation to the problem with $O(\\frac{n}{\\varepsilon})$ words of memory. This is an improvement over [CKLPU'22] who gave the same approximation with $O(n\\log n)$ words of memory (I'm not sure of the dependence on $\\varepsilon$) and over [BCMT'22] who gave a 5-approximation with $O(n)$ words of memory. Moreover, the algorithm is extremely simple. It picks a a random ranking of the vertices and for each vertex keeps a list of its $k=O(1/\\varepsilon)$ highest ranked neighbors during the streaming phase. In post processing the algorithm goes through the vertices according to their rank, for each vertex $u$ finding the highest ranked vertex $v$ in its list such that $v=u$ or $v$ is a pivot. In the former case, $u$ is declared a pivot, in the latter case, $u$ is assigned to the cluster of $v$. If no such $v$ exists, $u$ is put in a singleton cluster. The analysis describes an equivalent offline algorithm which is analysed partly via an analogue to the  Pivot algorithm from [ACN'08] and partly via a martingale argument for singleton vertices relating their cost to that of the Pivot algorithm.", "questions": "What's the dependence on $\\varepsilon$ in [CKLPU'22]?\n\nl66: \".... has $O(n)$ words of memory where $k$ is a constant\": Do you mean $O(nk)$?\n\nl131: I think the runtime bound can be improved to $O((k\\log k \\log n)n+m)$ or something like that. Indeed, with the random order, you only need to update the priority queue with probability $k/i$ when the $i$'th neighbor arrives. \n\nl142: You define $U_t$ to be the unclustered vertices but latter on in the martingale argument (l206, l209, l216,...) you refer to $U_t$ as the set of clustered vertices. I think the indicator in the potential should be $1(v\\notin U_t)$.\n\nl195-196: Can you define $\\Delta OPT_t$ more clearly. When you say the optimal cost of the edges settled by PIVOT, you mean the cost of these edges in the optimal solution, right?\n\nl212 \"...must be a pivot chosen among non-clustered...\": Couldn't it also be because it's counter increased to $k$? It doesn't seem to matter for the argument?\n\nEquation above l217: The first inequality is an equality, right? And $v\\in U_{n+1}$ should be  $v\\notin U_{n+1}$?", "limitations": "No limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and the proofs are neat and readily checked to be correct. The algorithm is simple and I think it is nice and rare with a short paper with such a clean idea. Since furthermore, correlation clustering is of interest to many people in the Neurips community I think the paper should be accepted.", "weaknesses": "Perhaps the authors could have considered running some experiments on the quality of the clustering output by their algorihtm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The algorithm by [CKLPU'22] uses $n \\log(n)/\\epsilon$ words of memory.\n\n1. The memory usage is O(kn). It is linear in $n$ if $k$ is fixed. \n\n2. __l131: I think the runtime bound can be improved to ...__\nThank you! You are right.\n\n3. That's correct.\n\n4. You are right.\n\n5. __When you say the optimal cost of the edges settled by PIVOT, you mean the cost of these edges in the optimal solution, right?__ That's correct. We will revise the wording to make it clear.\n\n6. __l212 \"...must be a pivot chosen among non-clustered...\": Couldn't it also be because it's counter increased to $k$? It doesn't seem to matter for the argument?__ \nWe will more carefully explain what happens when the counter is increased to $k$. This case should be handled on l214, because in order for the counter $K_t(v)$ to get equal to $k$, it first needs to increase by 1.\n\n7. That's correct. Thank you!"}, {"review_id": "ugNKhoT7g7", "reviewer": "Reviewer_NEv2", "summary": "The paper shows a single-pass semi streaming algorithm for correlation clustering (minimizing disagreements) which computes a  $3+\\epsilon$ approximate solution using $O(n/\\epsilon)$ words. This should be compared with:\n * a 5-approximate algorithm using O(n) words\n * a $3+\\epsilon$ approximate algorithm using $O(n \\log n)$ words\n\nThe algorithm is a variant of the PIVOT algorithm combined with a simple sparsification technique which keeps $1/\\epsilon$ edges per each node.", "questions": "I'm afraid I can't think of a question that could affect my recommendation", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "* The paper improves the space usage for an important problem\n* The presentation is clear. Actually the entire paper, including all proofs (excl references) fits in 6 pages", "weaknesses": "While I appreciate the theoretical result and the simplicity, the improvement over the previous results seems quite small: i.e. it can be seen as either slightly reducing the approximation factor or space per vertex from $O(\\log n)$ to $O(1/\\epsilon)$. I'm not convinced that the problem of correlation clustering in a streaming setting is popular enough for this kind of improvement to be of sufficient interest to NeurIPS audience", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:
We thank the anonymous reviewers for their valuable comments. We are grateful to them for carefully reading our paper, giving us helpful suggestions, and providing a list of typos. We will address all the feedback we received in the final version of this paper and, of course, fix the typos and add necessary clarifications.

We believe that our paper offers significant theoretical and practical advancements in the study of the Correlation Clustering problem. The contribution of our work is twofold: (1) Our algorithm demonstrates improved memory usage compared to both streaming and non-streaming algorithms previously introduced. (2) It is significantly simpler than other Correlation Clustering algorithms, except for the original Pivot algorithm. This simplicity makes our algorithm easy to implement. Our reference implementation is concise, consisting of fewer than 50 lines of C++ code. Moreover, our proof is just 3-4 pages long, which makes it accessible and comprehensible. The reason why we highlight the simplicity of our algorithm is that, in practice, people prefer to use simple algorithms whenever possible. There are many known sophisticated algorithms for Correlation Clustering, but, in practice, the algorithm of choice is, due to its simplicity, the original Pivot algorithm. In the case of streaming algorithms, our algorithm is both better and substantially simpler than other algorithms.

Our algorithm can also be used in the non-streaming setting when the data is stored in a file. In this case, the advantage of our algorithm is that it uses much less memory than the standard Pivot. We conducted experiments with two synthetic data sets. The plot (provided in our response as a separate PDF file) shows that the performance of our variant of Pivot is essentially the same as the performance of the original Pivot for $k \geq 4$. These data sets are based on the K-nearest neighbor (K-nn) graphs for points generated through a Gaussian mixture model. We normalized the cost such that the standard Pivot algorithm's cost is set at 1. After running our Pivot variant 100 times on each graph, we averaged the costs. Please, note that k denotes the parameter of our algorithm, while K denotes the number of nearest neighbors in the K-nn graph.

Meta-review: The reviewers are split on this submission with some strongly supportive of the paper and some suggesting that the results are largely incremental.

The paper gives a new algorithm for correlation clustering in the low memory setting. The algorithm is a variant of the classical pivot algorithm with a simple and elegant analysis. The theoretical improvement over recent results are minor but the bounds seem to be as good as they can be. The original paper contained no experiments and thus it is hard to ascertain if the simplicity of the algorithm indeed translates into usefulness in practice. The rebuttal included some limited experiments that are more convincing and would strengthen the paper significantly if it is taken into account.
Decision: Accept (poster)