Sparse-pivot: Dynamic correlation clustering for node insertions
Authors: Mina Dalirrooyfard
Konstantin Makarychev
Slobodan Mitrović
Venue: ICML 2025 spotlightposter (2025)
Keywords: correlation clustering
dynamic
node insertions
Primary area: theory->optimization
TL;DR: A node-dynamic unweighted correlation clustering algorithm with poly log n amortized update time and 20 approximation.

Abstract: We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added.
Our algorithm has the amortized update time of $\log^{O(1)}(n)$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. 

We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al.~in practice.

SPARSE-PIVOT:
Dynamic correlation clustering for node insertions
Mina Dalirrooyfard Konstantin Makarychey Slobodan Mitrović
Abstract
with the given edge set. An edge (u, v) disagrees with the clustering if u and are placed in different clusters, while non-edge (u, v) disagrees if u and are placed in the same cluster.
We present a new Correlation Clustering algo- rithm for dynamic setting where nodes are added one time. In this model, proposed by Cohen- Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to ac- cess the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of (log ((1)))())))) (m)). Its approximation factor is 20 + e, which is substan- tial improvement over the approximation factor of the algorithm by Cohen-Addad al. We com- plement our theoretical findings by empirically evaluating the approximation guarantee of our al- gorithm. The results show that it outperforms the algorithm by Cohen-Adde Addad et al. in practice.
The problem was introduced by Bansal, Blum, and Chawla (2004). It can be easily solved a disagreement-free cluster- ing exists, as each cluster then corresponds to a connected component of the similarity graph G. However, when the classifier makes mistakes, and a disagreement-frre solution does not exist, the problem becomes NP-hard. In their origi- nal paper, Bansal, Blum, and Chawla proposed constant- factor approximation, which was subsequently improved in a series of works Charikar et al. (2005); Demaine et al. (2006); Chawla et al. (2015); 2023); Cao et al. (2024). In 2005, Ailon, Charikar, and Newman introduced combinatorial and LP-based algorithms with approximatios factors of 3 and 2.5, respectively. The best-known approximation factor for Correlation Clustering with Complete Information currently 1.437 (Cao, Cohen- Addad, Lee, Li, Newman, and Vogl, 2024). Nevertheless, the combinatorial algorithm by Ailon al. (2008), known as PIVOT, remains one of the preferred choices in practice due its simplicity and good empirical performance.
(n)).
al. (2022;
1. Introduction
In this paper, we present a new dynamic algorithm with node updates for the Correlation Clustering problem with com- plete information.' Correlation Clustering is well-studied problem that seeks to partition a set of objects into clusters based on their similarity. The problem is defined on set of items represented as nodes in graph, with similarity infor- mation provided through a set of edges. We assume that all pairs of nodes are classified as either "similar" or "dissim- ilar" by a noisy classifier. For every pair of similar nodes and v, there is an edge (u, v) between them (sometimes referred to as a positive edge). For every pair of dissimilar nodes u and v, no edge exists between them (such pairs are sometimes called negative edges). The objective is to find a clustering that minimizes the number of disagreements
Researchers have proposed various variants of PivoT that operate in parallel and streaming settings (Bonchi et al., 2014; Chierichetti et al., 2014; Pan et al., 2015; Cohen- Addad et al., 2021; Cambus et al., 2022: Behnezhad et al., 2022; 2023; Cambus al., 2022; Chakrabarty & Makarychev, 2023). Recently, there has been growing inter- est algorithms that support dynamic updates. Consider scenario where similarity information is received over time, requiring the clustering to be updated dynamically. Dalir- rooyfard, Makarychev, and Mitrovic (2024) showed how to maintain a (3 + -pparooximttoo clustering with constant update time per edge insertion or deletion (see also papers by Behnezhad et al. (2019) and Chechik & Zhang (2019)).
'Equal contribution scarch, Morgan Stanley, Canada. minaddmite edu. "Northwestern University, konstant meenrrtwwestere
'aachnne Learning
Re-
Chicago, Uniiersitty of edu. Corre-
USA.
Cohen-Addad, Lattanzi, Maggiori, and Parotsidis proposed algorithm designed for setting where nodes and edges are stored in a database. Over time, new nodes are added to the database along with their incident edges. After nodes are added, the dynamic algorithm updates the existing clus- tering. this model, each edge included the database immediately after both its endpoints are inserted; no ad-
California, Davis, USA. smi spondence to: Mina Dalirrooyfar < <minad @ edu..
Proceedings of the 4nnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
By complete information, it meant that for each pair of
nodes there information on their similarity.

---

Sparse-pivol: Dynamic correlation clustering for node insertions
ditional edges can be inserted or deleted afterward. The sequence of inserted nodes is non-adaptive, meaning it does not depend on the decisions of the clustering algorithm. Formally, we assume that the graph and the order of node ar- rivals are fixed in advance. Cohen-Addad et al. showed how to achieve a constant (albeit very large) approximation with an update time of log O(1) ni, measured terms of database operations defined as follows: (1) retrieving the degree of node v; (2) selecting a random neighbor of v; and (3) checking whether two nodes u and v are connected by edge. The database model was introduced by Assadi and Wang (2022). The algorithm by Cohen-Addad et al. was the first dynamic algorithm for node insertions with sublinear update time. Although provides constant approximation, the proof suggests that the constant is very large (the paper does not estimate it). In this work, we propose a (20 + 8)- approximation algorithm for Correlation Clustering with update time of Oz Ologg (1) n.) database operations per node
to the neighbor of u with the smallest rank. To reiterate, in this variant of PIVOT, each vertex u belongs to the clus- ter of p(u) if p(u) = p(p(u)), and to singleton cluster if p(u) # p(p(u)).
Behnezhad, Charikar, Ma, and Tan (2023) provide a dy- namic edge-insertion version of this algorithm with constant update time, A dynamic implementation of this algorithm for node insertions can be easily inferred and is presented in Algorithm 1. In this version, when the node u. being inserted is pivot, the algorithm runs the EXPLORE pro- cess. This process updates the pivot of each neighbor w of u and reassigns w and its neighbors to the cluster of u or singleton clusters, if necessary. We refer to the clustering produced by this algorithm as REFERENCE CLUSTTERING, as our algorithm aims to approximate this clustering.
Algorithm 1 Insertion for REFERENCE CLUSTERING
1: input node u, graph G, ordering म, pivot array p.
insertion.
2: Compute p(u)) = arg weN[] T(w).
In addition to node insertion, the algorithm by Cohen- et al. supports deleting random nodes. Our algorithm sup- ports a slightly weaker type of deletion: soft deletions of random vertices. When node is soft-deleted from the graph, it initially remains in the database but is marked as soft-deleted. Moreover, the classifier continues creating edges between newly arriving and soft-deleted nodes. Only when the algorithm requests their deletion are they purged from the database.
3: if p(u) = u:
4: Mark u as pivot.
5: Create a new cluster with u in it.
6: Run EXPLORF(U, G, T,
else if p(u) is pivot:
Put u in p(u)'s 's cluster.
9: else:
10: Make u singleton.
To motivate the model, consider the following example: An online store adds new items its stock daily and aims to cluster all items based on similarity. Whenever new item is added, the store runs classifier to identify items similar to the new one. A record for the new item is then created and inserted into the database, along with edges connecting to similar items. Instead of reclustering the entire dataset, the dynamic algorithm efficiently updates the clustering, requiring only (log)(1) n) operations per item insertion.
2.1. Making the REFERENCE CLUSTERING algorithm faster
The challenge with REFERENCE CLUSTERING is that, af- ter each insertion, it scans the entire neighborhood of the inserted node u, which can be as large as (n),, where is the size of the current graph. This makes this REFERENCE CLUSTERING prohibitively expensive. To improve the ef- ficiency, we perform this exhaustive search only for pivots. For non-pivot nodes u. we attempt to recover the unknown pivot by sampling O(log n) neighbors of u, examining the set of pivots of these sampled neighbors, and setting p( (u) to the neighbor with the smallest ranked among the neighbors scanned in this process (which could be the samples or their
2. Algorithm
Our algorithm is based on the 3-approximation variant of PIVOT. developed by Behnezhad, Charikar, Ma, and Tan (2023) for the semi-streaming model. Their algorithm in the static setting works as follows: First, it selects a random ordering x of all nodes. For each node u, it picks the neigh- bor of u with the smallest rank and stores this neighbor in the pivot array p: p(u)= = arg (()) ((w). Next, the algorithm identifies all nodes u such that p(u) = u, which we refer to as pivots. We call p(u) the pivot for node e. Then, the algorithm creates new cluster for every pivot and assigns it nodes v with p(r) u. All remaining unassigned nodes placed in singleton clusters. Note that for each node u in a singleton cluster, p(u) remains equal
Algorithm 2 EXPLORE
1: input pivot u, graph G, ordering т, pivot array p.
2: for all w E N(u]:
3: if (p((w)) > <()):
4: if w is pivot, i.e., p(w) = w:
5:
for all 2 where p(z) = w: if E Nu),, then p(=) +- u.
else make z singleton
8:
p(w) t u.
2

---

Sparse-pivot: Dynamic correlation clustering for node insertions
pivots). We show that this approach succeeds when the clus- ter C' in the reference clustering is sufficiently dense and u does not have too many neighbors outside of C.
that EXPLORE is called on every pivot u. This follows from the observation that if rr()) > T/d(() then :(()) > I/d(u) for all neighbors E N Mu.. The probability of this event is at most (1 - L/d(u)) d()) - poly(1/n).
Instead of selecting a random ordering of vertices ग, our al- gorithm assigns each value ru)) uniformly at random from the interval [o, 1]. This simplifies maintaining a random ordering in dynamic settings, where the exact number of nodes is not known in advance and also makes the logic of our algorithm bit simpler.
We define good nodes as follows: loosely speaking, a node is good if is connected to most nodes within its cluster and relatively few outside it. We show that good nodes in our clustering are assigned the same pivots as in the reference clustering (when our algorithm and REFERENCE CLUSTERING use the same ordering πτ) For now, let us assume that all nodes are good. If a good node u arrives after its pivot w, then u will join w's cluster when w seans all its neighbors, including u. If u arrives after w while more than 25% nodes in w's cluster have yet to arrive, then for at least one node v arriving after u, we will call EXPLORE, which will assign the correct pivot Here, we rely on the assumption that all nodes are good. Finally, if u arrives among the last 25% of nodes in w's cluster, then by the time u arrives, the algorithm will have assigned the correct pivot w to most of its neighbors in the reference cluster. Consequently, a high fraction of u's neighbors will have w as their pivot, and some of these neighbors will be included in the random sample of neighbors (see item (2)). Hence, u will also be assigned the correct pivot. Our full analysis can be found in Section 3.
We present our algorithm for node insertion in Algorithm 3. We use three main ideas:
(1) For vertices u with T(u) - a(aj. where L = Ollg n), we run EXPLORE on u if u is a pivot, similarly to REFER-
L.
ENCE CLUSTERING. If u is not pivot, we run EXPLORE on its pivot to update its cluster.
(2) For vertices u with (u) > a(a) we find pivot by examining the set of pivots of O(log n) random neighbors
of u and selecting the neighbor of u with smallest ranked in that set as a pivot for u.
(3) In the obtained tentative clustering, we identify certain nodes, remove them from their clusters, and place them into singleton clusters. Specifically, we remove nodes whose in-cluster degree is below a threshold t. The optimal value of t is determined by trying out (log n) possible choices. In particular, when a new cluster is made upon arrival of a pivot node, the subroutine BREAK- BREAK-CLUSTER removes some nodes from the cluster and makes them singletons. When the node inserted is not a pivot and is assigned to pivot v, CEATTECCLSSERR updates the set of nodes assigned to e that are put in singletons upon insertion of the new node (See Appendix A for details).
Let us now consider bad (not good) nodes. These nodes incur a very substantial cost in the reference clustering. If we could remove them from their reference clusters and place them into singleton clusters, the overall clustering cost would not increase iignificantly-in fact, it might even decrease. Unfortunately, our algorithm cannot identify these bad nodes; as a result, they may join clusters other than their own reference clusters. This can substantially increase the cost of those clusters. To address this issue, we partition each tentative cluster into two parts (see item (3)): the first part remains cluster, while the second part is broken into singleton clusters.
the subroutine
We now provide some motivation for the algorithm. First, we observe that the expected time required for finding pivots log)(1)
in items (1) and (2) is log O(1) n. In item (1), spend d(u log time with probability log n d(u). In item (2), we always spend Olog n) time by examining Oloogn) n) random neighbors and their pivots.
Theorem 2.1 provides the approximation guarantees of our algorithm which we call SPARSE-PIVOT.
We run the step described in item (3) after (roughly) every es insertions, where is the size of the cluster. In this step, we test O(log n) different thresholds and, for each choice of I, estimate the cost of the split defined by / by sampling random edges within the cluster (see Appendix A for details). Hence, the total running time of one such step is log (11) n, and the amortized cost per insertion is log 011) n.
Theorem 2.1. For any e < 1/1000, the expected cost of SPARSE-PIVOT with parameter is at most 4(1 + O()) times the expected cost of the REFERENCE CLUSTERING.
Our algorithm for soft deletions is very simple: We ignore them! In fact, we recompute the whole clustering again after (s)) many updates, where N is the number of nodes when we last recomputed the clustering. The recomputation is only necessary for deletions. Our running time guarantees are provided in Theorem 2.2.
We now discuss the approximation factor. Item (1) ensures that all pivots in the reference clustering are marked as pivots by our algorithm with high probability. Specifically, for every pivot u in the reference clustering, we have (u) < L/ d(u) with probability at least 1 - poly(1/n), ensuring
Theorem 2.2. Let T be the total number of updates. With high probability, Algorithm 3 runs in amortized poly(log { time.
3

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Algorithm 3 INSERT-NODDE-SPARSE-PPWY
A-light dc(u) S
ICI 3
where C C7
1: input node u to be inserted, current graph of size n, ordering T. pivot vector p.
aApoo if d(u) S cd(pa and is not light.
2: Let π (u) E [0, 1] be chosen uniformly at random.
A-heavy if d(u) 2 B|C), where C = C%
3: Let p(-) indicate the lowest rank neighbor of each node.
-poor, A-heavy or A-light, and A A-good otherwise.
A-bad if u
4:
Let B, indicate the set of nodes with pivot and let
C. C B2 be the nodes of B, that are in e's cluster. if (u)) S a/
A-lost if the number of A-bad neighbors of u in C7 (u) at least / times the number A-good neighbors of in CA (u).
5:
6:
Find v = arg (EN T(w).
7:
i = u:
8:
Make u a pivot: p(u) f- u, and make a new cluster with a it: Bg = [u]. Lu =0
We drop A- if the clustering algorithm is clear from the context.
9:
EXPLORE(U, G. TT, Cu + BREAK- CREAK-CLUSTTERDE B.).
10:
Definition 2.4 (Poor clusters). For a fixed ordering æ and clustering algorithm A, let C' be a cluster with pivot v. We call C an (A, a-poorr cluster if C' has at least one (A, a)- poor node.
11:
else if e # u and v is pivot:
12:
p(u) + B, t B, U (u).
13:
C. UUPAATB-CLUSTER B₂)
14:
if d() S )(U)
Definition 2.5 (Good and bad clusters). Let 7 < 1 be a constant. For a fixed ordering т and clustering algorithm A, we call a cluster C good it not (A, a-)-oor,, and has at least Y y good nodes. Otherwise, we call it bad.
15:
EXPLORE(U, G, P)
16:
else if v * u and v is not pivot:
17:
make u singleton.
18: else:
19:
Let S be a Ollog n) sized sample of Muu].
Remark 2.6. Note that instead of fixing the clustering algo- rithm A and ordering म, we can still have the above defini- tions if fix the clusters and pivots.
20:
Let arg (pte) (p(()). Let
0. :: -=*(s)
21:
if (()) T()):
Definition 2.7 (Cost of a cluster). Given a clustering, the cost of a cluster C is the number of non-edges inside C, and half of the number of edges with exactly endpoint in C.
22:
p(u) + B, + C (n).
23:
C. UD-AATTBCCLUTTERRG B₂)
24:
if u did not get clustered:
25:
make u a singleton, u does not have a pivot.
The cost of a clustering the sum of the cost of its clusters.
3. Analysis
2.2. Analysis Preliminaries
3.1. Analysis outline
We use subscript ref to refer to REFERENCE CLUSTERING. We fix time, and we compare the cost of our algorithm to the cost of REFERENCE CLUSTERING at this time. We refer to the current graph G. For node v, ordering x and clustering algorithm A, let (v) be the cluster of in A with respect to the ordering т. We drop the superscript π and subscript when it is clear from the context. The clus- tering algorithms that we consider throughout our analysis all define pivots for all non-singleton clusters.
First, we explain the intuition behind classifying nodes in Definition 2.3. Let the cost of node be half the number of non-neighbors has in its cluster, plus half the number of neighbors it has outside the cluster. Note that the sum of the costs of nodes in cluster equals the cost of the cluster. Consider A to be the reference clustering in Definition 2.3. A light node in cluster C' has lot of non-edges attached to it in C, and a heavy node has lot of edges attached to it that leave the cluster C. So both have a high cost. In fact, we show that if we make them singletons, the cost of the clustering does not change much. So, in sense, in our algorithm, we do not care how re hheav or reg-tight nodes are being clustered as long their cost is somewhat comparable to their cost as singletons.
Given a ordering and clustering algorithm A, let p (u) denote the pivot of u chosen by algorithm A. For set of nodes S, let ds (v) be the degree of in S, and let d(v) be the degree of v in the graph G. We will classify nodes depending on how their neighborhoods intersect the cluster to which they are assigned.
Consider poor nodes. A poor node has a much lower degree than its pivot. We show that if a cluster has at least one poor node, then any node in this cluster that is not heavy or light must be poor (Lemma 3.1). Then we show that, in fact, if we
Definition 2.3. Let a < 1 and 3 > 1. Let A be a clustering algorithm. For a fixed ordering n, we call vertex u
4

---

Sparse-pivot: Dynamic correlation clustering for node insertions
make the whole cluster singleton, the cost of the clustering does not change much on average. This is because the pivot of this cluster has a very high cost, and any node becomes the pivot of a poor cluster with low probability.
we have that |C|/3 I d(u) S ad(r). So 3ad(o) 2 |C| Now for any that is not heavy we have d(u) S 3 S 3a,d(f). Thus if is not light, then u is (A, 3a.3)-poor
In summary, we have shown that if we make the bad nodes (heavy, poor, or light) in the reference clustering singleton, the cost of the clustering does not change much (Lemma 3.2). We further show that we can make all the nodes in bad cluster singleton as well since the cost of this cluster is already too high. We call this clustering re
The following lemma shows that if, in REFERENCE CLUS- TERING, we make all the bad nodes and lost nodes singleton, the cost only increases by factor of (1 + O(e).
Lemma 3.2 (Cost of making bad and lost nodes singletons). Consider a clustering algorithm A where the probability of any node being pivot is at most 1/d(v). Let B be the algorithm that first runs A, and then makes A-heavy, A-light, (A, (A,3ax3)-pon and A-lost nodes singletons. Then E [cost - (1 + Te) [cost
We then show that in SPARSE- PIVOT, not only do we detect pivots correctly with high probability (Lemma 3.4), but also all the good nodes that are not lost, i.e., they do not have many bad neighbors, are assigned the correct pivot. We show this in two parts: Consider pivot v, and suppose C is the set of all the ref-good nodes with pivot that are not reost First, we show that if a good node E C arrives rather early compared to other nodes in C, at some point its pivot runs EXPLORE and it detects if u is clustered incorrectly (Lemma 3.5). If u arrives rather late, then the sampling procedure will hit one of the neighbors of in C that is correctly clustered and so correctly assigns v as the pivot of u (Lemma 3.6).
Proof. Let a' = 3a,3, and let A' be the algorithm that runs A and then makes the A-heavy and A-light nodes singleton. Let A" be the algorithm that runs A', and makes all the (A, - nodes singleton. For the clarity and brevity of
notation, we use d def 4a' 1+3/2-n' 1-5/2-a7 For any fixed ordering 3+1
n, by Lemma C.2, cost I 3-st0 and
B + 1
Cost S
B 1 cost
Now since we cluster the rgood nodes correctly with high probability, if we could detect ref-bad nodes in SPARSE-PIVOT. we could make them singletons, and thus get ref'. However, instead, if B, is the set of nodes that have as their pivot, we make a dense subset C, of B, one cluster, and make the rest of B, singleton. This step is crucial since there might be many (bad or lost) nodes incorrectly assigned to that increase the number of the non-edges in B, significantly. We show that the cost of making B. \ C2 singleton is at most 4 times the cost of making the ref bbdd nodes in B, singleton (Lemma 3.7).
Now note that the probability of any node v being a pivot in A' is at most the probability of any node being a pivot in A, which is at most 1 1/d(r). The cost of making (A, (A,a')- poor nodes singletons is, at most, the sum of their degrees. By Lemma C.I, that expected sum of (A, a')poor nodes degrees is upper bounded by 8- E2 [costa]. Hence, we have
Egr [cost S (1 + 8) E, [costar]
Finally, note that any A-lost node a Al-light node or A"- heavy node with parameter B/3. To see this, fix ordering w.
Now we begin our formal analysis. Let | 2 1+e a 4c3 eya log n. for some arbitrary large constant c. Let the number of samples when the inserted u satisfies ruu) > I//d(u) be at least 100 1 = Ollogn) n), where x = (9+) - c)/B.
< min( 24 393 ). and y S 5. Let L 2
Consider A-lost node u, and let C C (u). Let C" C
be the set of A-bad nodes in C. Let C" = CT,(u)
C\C' By the definition of A-lost nodes, we have (c) 2
(u). If u is not A'-light, then dcw(u) > |o"1/3. 8 II'... So u is A"-
So d(u) 2 (u) 2 Bdo= 2
3
3.2. Making all the bad and lost nodes singleton in Reference clustering
heavy node with parameter 9/3. By Lemma C.2, cost S 8+3 8-3 ".. So cost < 3-3 3-3cost
8-3
cost A". Putting all the steps
We show that if a cluster has one a-poor node, then all the nodes in that cluster are 30.3-poor.
together yields
8 8+1
3+3 EE, (costA)
Lemma 3.1. Let n be an ordering and A be a clustering algorithm. IFCA is an (A, a)poor cluster, then any u E CA which is not light or heavy is (A,3ax3)-pon
E, [cost
<
(1 + 5)
3 3-1
3-3
Now since 3 2 1ts, we have
S+1
3-1
<
3-3
8+3
< (1 + e).
and since a' < 1/13, we have 1+3/2-a'
2, and
a' <
Proof. Let v be the pivot of C' = CAA. First, since C' is an (A, -ooor cluster there is a node w E C that is (A, a)-
1-5/2-0
e/8 gives us 4a' 1+3/2-0' < E. So E, [cost < (1 +
T-5/2mn
poor. Since, by definition of poor nodes, w is not light,
')&E, [ S (1 + 7 E [cost
5

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Lemma 3.3. Consider a fixed ordering x and clustering algorithm A. If B is clustering algorithm that runs A and makes all A-bad and A-lost nodes, as well as all the nodes in bad clusters in A singleton, then cost(B) B) S (1 + Se (cos((A).
Lemma 3.6 shows that SPARSE-PIVOT identifies the pivot of all the good nodes that are not lost correctly.
Lemma 3.6. Fix clustering and its pivots that the ref- erence algorithm can produce. Let u be a pivot in that reference clustering and u be in the v's cluster. With high probability, any u that is ref-good and not ref-lost is as- signed to v by Algorithm 3.
Proof. Let A' be the algorithm that runs A and makes the A-bad nodes and A-lost nodes singleton. Then we can see B as running A' and making all the good nodes remain- ing in A-bad clusters singleton. Note that by Lemma 3.2 (A') V (1 + Te)cos((A). Note that in A' all poor clusters are singletons, since a poor cluster has at least one (A, a) poor node, and by Lemma 3.1 all the non-pivot nodes in this poor cluster that are not heavy or light are (A, 30:3)- poor. By definition of bad nodes, all the nodes a poor cluster are bad.
Proof. Let C =Cre First, if is among the first (1 -) fraction of the nodes of C(good with respect the dynamic ordering, then by Lemma 3.5, with high probability Algorithm 3 assigns to e's cluster.
So, second, consider the case when u is in the last e fraction of C'good] Let D refer to the ref-good neighbors of u that are among the first 1 fraction of the nodes of Clgood]. By Lemma 3.5, with high probability Algorithm assigns the nodes in D to e's cluster. We now lower-bound [D]. We will use that lower bound to show that the sampling process in Algorithm 3 (when (u)) < L/ d((()) will sample at least one node from D. and hence assign v to u's cluster.
Consider a bad cluster C' in A. The cost of C in A is at least (1 - C by Lemma C.3. Making the good nodes in C' singleton in A' adds at most 22 to the cost of A' since there are at most 7|C| good nodes in C, and the only cost added by making these nodes singleton is through the edges between them. So the total cost added to the cost of A' by making these good nodes singleton is at most
Since u is not ref-lost, by Definition 2.3, u has at most B times more ref-bad than ref-good neighbors in C. Hence, at least 1/(1 + 3) - |C| neighbors of u in C are ref-good. Also, observe that 1/(1 + 3) |C| E
[(1-) cos. So cost (B S cost(A')
3-
+ 2(17) cost(A).
3,2
Since Y S e/2, we have 2(-7) S (I- S 2 e. So
3-2
4n2
[C[good]| 2 (1/(1 + (8) - E) |C| of those neighbors are among the first 1 - fraction of Clgood]. Therefore, DD Z (1/(1 + B) e) IC). On the other hand, since u is a aaar---oou node, we have that d(u) < B- IC).
cost( [) $ (1 + (e))
n
3.3. SPARSE-PIVOT comparison to REFERENCE CLUSTERING
Finally, we conclude that
Let Paly be the pivot set of our algorithm and Prey be the pivot set of the reference clustering.
DI
DD 1/(1 + B) - d(u)
2
dinsere(u)
3
Lemma 3.4. Let L' = L/28. I E P.Pp. Prep then (T))= S L' L/(((r) holds with probability at least 1 - 1/n
where dinsere(u) is the degree of u at the time of insertion. Let ñ be the number of nodes when inserting u. If I == 1/(1+,9)=c the probability of not sampling any node in D is at most (1 - =)(s1, where S' is the sample set. Recall that |S| 2 100 log( ( log f. so this probability is at most 1/n 1/0 Note that if n is the current number of nodes, ñ 2 n/(1 + <) since we recompute everything when the number of updates is at most e times the number of nodes at last RECOMPUTE. So the probability that u is clustered correctly is at most 1 - (1 + c)/n 100.
Note that not only does Lemma 3.4 say that each pivot in REFERENCE CLUSTERING is also pivot in SPARSE- PIVOT, but it also provides stronger guarantee on x(v).
For the next Lemma, note that the definitions of light, poor, etc, are well-defined if the clustering is fixed (and not neces- sarily the ordering TT. We show that with high probability, one of the good nodes in Cref (v) triggers EXPLORE func- tion for v so that can correct its cluster.
Lemma 3.5. Fix a clustering and its pivots that REFER- ENCE CLUSTERING algorithm can produce. Consider a pivot e whose cluster (v) is good. Let Cre [good] be the good nodes in (Te Then, with high proba- bility, our algorishu assigns
Next, Lemma 3.7 aids us to compare REFERENCE CLUS- TERING with SPARSE- PIvOT clustering. Given pivot v and set B., let C2 be the set of nodes in B3, with degree at least f. Let cost B, (C,) be the cost of the clustering on B, where all the nodes in C, are clustered as one cluster and the nodes in B, \. C. as singletons. In particular, this cost equals half of the number of edges from B, to outside of B,, plus the number of edges with at least one endpoint in B, \ C, plus the number of non-edges in C..
the pivol of u, for any (1 (1-e))Cre(tu)) [good]] first nodes u of (eer(()]good) The "first" here is taken with respect to the dynamic ordering and the probability taken over rankings that produce the fixed clustering.
6

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Lemma 3.7. Consider a pivot v, and let C be the set of good nodes that are not lost in Cres(v). There is a threshold & E {1. (1 + e)...., (1 + e) e)[logn]+33 such that
E(cost(B)) V 4(1 50c (())s((()))))) < 4(1 230c) + (c)sE(cost(( )) S 4(1 ((oos)(())))rre)))) where the
last inequality uses the fact that < 1/1000.
cost B. (B) S I-2:
4. Random deletions
3.4. Putting it all together
Let no be the number of nodes in the graph just after the last recomputation. Our algorithm for deletions is quite simple:
Proof of Theorem 2.1. We refer TO REFERENCE CLUSTER- ING as ref and the clustering of SPARSE- PIVOT by B. Let A be the clustering algorithm that runs REFERENCE CLUS- TERING to obtain ref. and then makes all re ref-bad, ref-lost nodes as well as all the nodes in r-bd clusters singleton. Note
1. Ignore deletions.
2. After eno/6 updates, counting both insertions and dele- tions, recompute the clustering from scratch by treating all non-deleted nodes as if they had been inserted one by one again. These insertions are processed by Algorithm 3. Our recomputing procedure is described in Appendix B.
By Lemma 3.3, E( (ccot((A) (A)) < that all the nodes that are not singletons in A are good nodes that are not lost and are not in bad clusters in ref.
8e) ((cos((ref)
Next we show that E(cost( (B) < 4(1 + B(o)))(Cost((A) Consider a pivot U in REFERENCE CLUSTERING. By Lemma 3.4 V is also a pivot in SPARSE-PIVOT with high probability. We will compare clustering costs by dividing up the clusters into groups: We consider all the nodes that are in Bg for pivot e together and compare the cost of clustering these nodes in A and in B. We have two cases:
Recall that on a deletion update, a node to be deleted is cho- sen uniformly at random among the existing nodes. Observe that the choice of deletions is independent of the randomness used by our algorithm. At time I of the algorithm, let D, be the nodes deleted since the last clustering recomputation. We think of Dr as the nodes waiting to be deleted.
By construction, we have |D,] S eng/6. Since after the recomputation there are nn nodes in the graph, Dj is subset of (at least) no nodes, and hence Pr (u E Dr) < D D//o S </66. There is inequality instead of equality, as the eno/6 6 updates might contain insertions, resulting in a reduced probability of a node appearing in Dr.
Case 1: (re)(v) is a good cluster. Consider Be, the set of nodes that are assigned as their pivot, and C S B the set of nodes in B, that are clustered with v and are not singletons.
Let C. = {u E Beld(()= 2 1), and let cost ( BB (C+) be the cost of clustering all nodes in Ct as one cluster and the nodes in B. \ G. as singletons. Let t" be the threshold in {1, (1 +
Let CNO-DEL be the clustering obtained by 5-approximate REFERENCE CLUUSTERIGG time / where deletions D, are ignored. Let COEL be the clustering obtained by REFERENCE CLUSTERING at time / in which deletions D, are considered. Let P, S V x V be the node pairs that CXO-DEL pays for. We aim to lower-bound the expected number of pairs in P. that CDEL also pays for. Consider a pair e = {u, v} E Pa. We will lower-bound the probability that the clustering of u and v is the same in CouL as in CNO-DEL
<),-.. - (1 + e) [logn -1} where cost (g(/ee ) is minimized. By Theorem A.5, (B. s (1 220s) (B, ).
If C is the set of good nodes that are not lost in Cres(v), then by Lemma 3.6 all the nodes in C are correctly assigned to v, and so they are in B.. Note that A clusters the node in B, as follows: put all the nodes in G in one cluster and make all the nodes in By C. singleton. By Lemma 3.7, we have that cost (o.((B. S 1-2 cost((B..C...c so Cost(B,lC.) s 4( 4(14-200s) (o.((B.)()) < 4(1 + c30e)cost(B,,CC) since (1-2F)
Consider a node u; the exact same analysis applies to
First, assume that u is singleton in Cso DEL- This im- plies that the neighbor of u with smallest rank, w, is not a pivot. Node w is not a pivot because it has a neigh- bor w' with rank smaller than w. If none of w, w', or u is in Dr, then u is a singleton in CDEL. Since we have Pr (w E D, or w' Dr or E D,) S Pr(w E Dr) + Pr (w' D₂) + Pr (u D.) I e/2, then in this case, the clustering of u in COEL. is the same as in CXO-DEL with proba- bility at least 1 - e/2.
8 S 1/1000.
Case 2: (v) is a bad or poor cluster. We know that all the nodes in (t) are singletons in A. Let 1* be the threshold in {1, + e)...., (1 + e)[lgg]+ m] +1] where cost BB(Ce-) is minimized. So cost( By- CC.) is at most the cost of making B, single- ton, i.e. cost(B,(CCas (oae)))))m))) = cost(B, By The- orem A.5 cost B.|Ca) < (1+ 200s) C.-). So (o, < (1 + 220c) cost B.(0).
Second, assume that u is not a singleton in CNO-DEL- This implies that the highest- rank neighbor w of u a pivot. By deleting nodes, and unless w is deleted, w remains a pivot. So, unless u are in Dr, the clustering of u is the same in Com and CXO-DEL. Since we have Pr (w E Dr or u E D,) S
Finally, note that a node not in any B, is a singleton in both B and A. Putting the above two cases together, So we have
7

---

Sparse-pivot: Dynamic correlation clustering for node insertions
e/3, in this case, the clustering of in CoLL is the same as in CXO.DEL with probability least 1 - e/3.
(2) The drift dataset (Vergara et al., 2012; Rodriguez-Lujan et al., 2014) from ICO Machine Learning Repository (Dua et al., 2017), which includes 13,910 points embedded in space of 129 dimensions. A graph is constructed by placing an edge between two nodes if their Euclidean distance is less than a certain threshold. This setup is used to easily change the density of the graph and test how it affects the algorithms. The thresholds we choose are the same as in (Cohen-Addad et al.), and they are the mean of the distances between all nodes divided by c E {10, 15, 20, 25, 30}. The lower the threshold, the sparser the graph. The density of a graph is the ratio of the number of edges and the number of nodes.
This analysis implies that the clustering of a pair fu, v} is the same in CDEL as in CXO-DEL with probability at least 1 - 5e/6. Hence, by the linearity of expectation,
E [cost(Coai)] 2 (1 - 5e /6 2 (1 - s) cost(Cro-DDiL
5. Experiments
In this section, we empirically demonstrate that our ap- proximation guarantee is better than that of REFFRENCE CLUSTERING and the algorithm of (Cohen-Addad et al.). In the rest, we use DYNAMIC AGREEMENT to refer to the approach in (Cohen-Addad et al.).
Baselines We use three baselines: making all nodes single- tons, which we call SINGLETONS, DYVAMIC-AGREEMENT and REFERENCE CLUSTERING. We divide the cost of each algorithm by the cost of SINGLETONS. Since REFERENCE CLUSTERING handles only node insertions, we process dele- tions in a way similar to (Cohen-Addad et al.). Note that our results slightly differ from that of (Cohen- Aaden et al.) since they depend on the randomness of node arrivals. More- over, the running time depends on the machine in which the algorithm is being run. Nevertheless, the scale of results we obtain does reproduce that of (Cohen-Addad et al.).
Algorithm Parameters In SPARSE-PIVOT, for the BREAK-CLUSTER and UPDATE-CLUSTER subroutines we do the following: in BREAK-CLUSTER we consider Ologn) many candidates for C.., estimate their costs and pick one with the lowest cost. In UPDATE-CLUSTER we update our Ollog 11) estimates by adding the new node, and again pick the one with lowest cost. To simplify the code, we heuristically alter the BREAK-CLUSE CREASER and UPDATE- CLUSTER subroutines as follows. In BREAK-CIUSTTER, for each node B., we sample Ollog n) nodes in B.. If u is attached to half of them, CLUSTER, we add u to C.. even though u might not be attached to many nodes in C.. After at least B. nodes are added to B., we rerun BREAK-CLUSTER the reason we get a (20 - O(E)) approximation instead of a (5 + (e)) approximation is the BREAK-CLUSTER sub- routine, so depending on the application, one can replace this subroutine with a version that one sees fit. Furthermore, RECOMPUTE every time the number of deletions reaches eN, instead of the total number of updates. We ob- serve that this does not degrade the approximation guarantee and slightly improves the running time.
Results: Approximation Guarantee For all the datasets, our approximation guarantee is better than DYNAMIC- AGREEMENT and SINGLETONS. For SNAP graphs. we plot the correlation clustering objective every 50 steps. Fig- ure 1 shows this objective for one of these graphs, and the rest can be found in Appendix F. The average clustering
add u in C.. In UPDATE-
Note that
emal--Fnro
Iotative clastiting cisectives
0.6
We set the experiment parameters and the parameters for DYNAMIC-AGREEMENT be the same as in (Cohen-Addad et al.). We choose a random ordering for the arrival of the nodes, and at each step, with probability 0.8, we insert the next node, and with probability 0.2, we delete ran- dom node. If all the nodes have been inserted once, we delete them until no node is left. We set the parameter e for SPARSE-PIVES to be 0.1.
0.4
AGRESMENT
SNGLETONS
200
400
600
Mode Arrvetoleelerioos
Figure 1. Comparison of the correlation clustering objective across the four algorithms. The lower the plot, the better.
Datasets We use the same datasets as in (Cohen-Addad et al.) for complete comparison. We evaluate the algo- rithms on two types of graphs.
objective for the drift dataset graphs is shown in Table 1.
Results: Running time Our experiments focus on the so- lution quality of SPARSE-PIVOr' -PIOT.. Nevertheless, we com- pare the running times for completeness and illustrate that PPARSE-PIVOY is faster than DYNAMIC- AGBEECEGGEEENNNN in practice, see Appendix F.
(1) Sparse real-world graphs from SNAP (Jure, 2014): a social network (musae-facetll facebook), an email network (email- Enron), a collaboration network (ca-Asta AstrrsstrPhh, and a paper citation network (eit-HepThh)
8

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Density
DA
RC
SP
on Discrete Algorithms (SODA), pp. 819-849, SIAM, 2023.
235.36
0.69
0.59
0.6
114.87
0.59
0.64
0.49
Bonchi, F., Garcia-Soriano, D., and Liberty, E. Correlation clustering: from theory to practice. In KDDD, pp. 1972, 2014.
69.74
0.5
0.5
0.41
52.17
0.39
0.42
0.32
42.25
0.35
0.35
0.29
Cambus, M., Pai, S., and Uitto, J. A parallel algorithm for (3+t)-approxxmate correlation clustering. arXiv preprint arXiv:2205.07593, 2022.
Table Clustering Objective of DYNAMIC- AGREEMENT (DA), REFERENCE CLUSTERING (RF) and SPARSE- PIVOT (SP). The smaller the number, the better.
Cao, N., Cohen-Addad, V., Lee, E., Li, S., Newman, A.. and Vogl, L.. Understanding the cluster Ip for correlation clustering. In STOC, 2024.
Acknowledgements
K. Makarychev was supported by the NSF Awards CCF- 1955351 and BECS-2216970.
Chakrabarty, S. and Makarychev, K. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! In NeurIPS 2023, 2023.
S. Mitrovié was supported by the NSF Early Career Program No. 2340048 and the Google Research Scholar Program.
Charikar, M., Guruswami, V., and Wirth, A. Clustering with qualitative information. Journal of Computer and System Sciences, 71(3):300-383, 2005.
Impact Statement
This paper presents work that aims to advance algorithmic tools for data partitioning, a method used in the field of Machine Learning. There are many potential societal con- sequences of our work, none of which we feel must be specifically highlighted here.
Chawla, S., Makarychev, K., Schramm, T., and Yaroslavtsev, G. Near optimal Ip rounding algorithm for correlation clustering on complete and complete k- k-partite graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 219-228, 2015.
References
Chechik, S. and Zhang, T. Fully dynamic maximal indepen- dent set in expected poly-log update time. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 370-381. IEEE, 2019.
Ailon, N., Charikar, M., and Newman, A. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008
Chierichetti, F., Dalvi, N., and Kumar, R. Correlation clus- tering in mapreduce. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discov- ery and data mining, pp. 641-650, 2014.
Assadi, S. and Wang, C. Sublinear time and space al- gorithms for correlation clustering via sparse-dense de- compositions. In 13th Innovations in Theoretical Com- puter Science Conference (ITCS 2022). Schloss-Dagstund Leibniz Zentrum für Informatik, 2022.
Cohen-Addad, V., Lattanzi, S., Maggiori, A., and Parotsidis, N. Dynamic correlation clustering in sublinear update time. In Forty-first International Conference on Machine Learning.
Bansal, N., Blum, A., and Chawla, S. Correlation clustering. Machine learning. 56:89-113 2004.
Cohen-Addad, V., Lattanzi, S., Mitrović, S., Norouzi-Fard, A., Parotsidis, N., and Tamnaski,, Correlation clus- tering in constant many parallel rounds. In Interna- tional Conference on Machine Learning, pp. 2069-2078 PMLR, 2021.
Behnezhad, S., Derakhshan, M., Hajiaghayi, M., Stein, C., and Sudan, M. Fully dynamic maximal independent with polylogarithmic update time. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pp. 305-405. IEEF, 2019.
Cohen-Addad, V., Lee, E., and Newman, A. Correlation clustering with aherali-adams. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 651-661. IEEE, 2022.
Behnezhad, S., Charikar, M., Ma, W., and Tan, L.-Y. Almost 3-approximate correlation clustering in constant rounds. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 720-731. IEEE, 2022.
Cohen-Addad V., Lee, E.,, Li, S., and Newman, A. Han- dling correlated rounding error via preclustering: A 1.73- approximation for correlation clustering, arXiv preprint WwXiv:2309.17244 2023.
Behnezhad, S., Charikar, M., Ma, W., and Tan, L.-Y. Single- pass streaming algorithms for correlation clustering. In Proceedings of the 2023 Annual ACM-SIAM Symposium

---

Sparse-pivot: Dynamic correlation clustering for node insertions
falir,ooyfard, M., Makarychev, K., and Mitrovic, S. Pruned pivot: Correlation clustering algorithm for dynamic, par- allel, and local computation models. In Forty-first Inter- national Conference on Machine Learning, 2024.
Demaine, E. D., Emanuel, D., Fiat, A., and Immorlica, N. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361((-3): 2006.
Dua, D., Graff, C., et Uci machine learning repository, 2017. URL http://archive. ics. uci. edu/ml, 7(1):62, 2017.
Jure, L. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://snap. stanford. eduldata, 2014.
Pan, X., Papailiopoulos, D., Oymak, S., Recht, B., Ram- chandran, K., and Jordan, M. I. Parallel correlation clus- tering on big graphs. Advances in Neural Information Processing Systems, 28, 2015.
Rodriguez-Lujan, I., Fonollosa, J., Vergara, A., Homer, M., and Huerta, R. On the calibration of sensor arrays for pattern recognition using the minimal number of experi- ments. Chemometrics and Intelligent Laboratory Systems, 130:123-134, 2014.
Vergara, A., Vembu, S., Ayhan, T., Ryan, M. A., Homer, M. L., and Huerta, R. Chemical gas sensor drift compen- sation using classifier ensembles. Sensors and Actuators B: Chemical, 166:320-329 2012.
10

---

Sparse-pivot: Dynamic correlation clustering for node insertions
A. Implementing cost estimates
Our clustering procedures, e.g., Algorithm 3, for each pivot maintain two sets nodes: B, and C.. The set B, a set of nodes whose pivot is E. However, having B, as one cluster might sometimes be very far from an optimal clustering of the nodes within B. So, our algorithm computes a cluster C. By for which we can guarantee relatively low cost: details of this analysis provided in our proof of Theorem 2.1. To compute cluster Cu. our algorithm estimates the costs of several clusters and chooses C as the cluster with the lowest estimated cost. In this section, we describe how to estimate the cost of a cluster efficiently, that is, in only poly n, 1/s) time. We need to handle two cases: how to estimate the cost of a given cluster C' from scratch, i.c., in static manner, and how to maintain the cost estimate of a cluster under node insertions.
We need the former case for our recomputation or when we create an entirely new B, because v just becoming a pivot. might tempting to create new B, by "pretending" that the nodes of B, have been inserted one by one. However, this approach has small subtlety. Namely, when a node is inserted, only that point the edges incident our graph, and no edge between e and a node inserted in the future is known. On the other hand, if we "pretend" that an already existing sequence of nodes is just now inserted, then a currently processed node also has edges to its neighbors that have yet to be processed/inserted. This scenario slightly affects how we count edges and non-edges within B, or Co.
included in
A.1. Static version
A.1.1. WITHIN-CLUSTER COST ESTIMATE
We first design procedure to estimate the cost within cluster C, i.e. the number of non-edges within C, by spending only Ollogn) n) time per edge. It is provided as Algorithm 4. As shown by Lemma A.1, this estimate is tightly concentrated as
Algorithm 4 IN-CLUSTER CELLLSTER-COS--SSTTNNE COST-ESTIMATE
1: Input set C V
2: To 5 5-555 log(n))//
def
3: for .C.
4: Uniformly at random, sample two distinct nodes and w from C
5: if {w, b} is non-edge, then S < S+11
6: return 5 /TC
long the number of non-edges is in (((CC).. If the number of non-edges is lower, then their actual number is irrelevant to our algorithm. Updating this cost dynamically is more involved, and we elaborate on details in Appendix A.2.
Lemma A.1 (In-cluster cost estimate). Let C C V be of nodes. Then, for 1/2, Algorithm 4 (IN-CLUSTER-COM COST- ESTIMATE) uses O(IC) log(n)/=?) running time and outputs Y for which with high probability the following holds:
If the number of non-edges within C if at least 2c|C then Y is a 1 multiplicative approximation of that number of non-edges.
Otherwise, Y 3c|C/.
Proof. Let f be the number of non-edges in C. Let X₃ be random 0/1 variable equal 1 iff the i-th {u, w) pair sampled by Algorithm 4 is non-edge. Then,
[X,] = Pr (X+ 1) L
(1))
Let S' be the value of at the end of Algorithm 4. Since S' = ETe Xs, we have
E E|S TC (c()
(I)
Let
def S' (10)
TC

---

Sparse-pivot: Dynamic correlation clustering for node insertions
be the output of Algorithm Observe that E [Y] Therefore, the expected value of Y the desired one. In the rest, analyze the concentration bounds of this estimator.
Consider two cases based on the value of t.
Case 2 2=|C|. Recall that TC = log(n)/e'" Replacing the bounds on t and To in Equation (1) yields
[S'] 2 10|C|2 log n 2 g²
20
(2)
22 ((2
Since S' is a sum of independent 0/1 random variables, by the Chernoff bound, it holds that?
Pr E E|S =E [S]) nn" n
This now implies that for t 2 2e|C), with probability at least - n -6 Y is a (1 te) multiplicative approximation of
Case f < 2=|C|. In this case, we would like to claim that very likely holds that < 3E|CO). This can be argued by applying the Chernoff bound as follows.
Observe that for this value of we have
20 log n
E [8") <
2
Hence,
20 log n
Pr S > (1 c1+
S -6
22
Therefore, with probability at least n holds that
(1 ++8) 5) log (10)
Y <
< (1+e)2/C1 < 3c(C],
TC
for 1/2.
A.1.2. SINGLE-CLUSTEE SINGLETONS COST ESTIMATE
We now diseuss how to estimate the cost of B for given C, where C' is taken single cluster, while all the nodes in B - C' are singletons. By cost of B we mean the number of edges with at least one endpint in B - C' and the other endpoint in B, plus the number of non-edges in C. Note that the true correlation clustering cost of B is the above cost plus half of the edges from to outside B, but since we need these costs to compare different choices of B and the number of edges going outside of is indipendent of this choice, does not influence our comparison.
In this section, given two node subsets X and Y, we use e(X, Y) denote the number of edges with one endpoint in X and the other in Y. In particular, e(X, X) is the number of edges in G[X]. We abbreviate e(X, X) e(X).
First, the entire cost of C, denoted by cosl(C), equals the sum of e(C, V -C) and the number of non-edges within C. Observe that
[the number of non-edges within C). c(C)= = (1C)) 2
So, have
- 22(1C) [the number of non-edges within CJ.
Σ =(w,= =(C)) -
WEC
This now implies that
cost(C)= = Σ d(w) 2 2((0) + + [the number of non-edges within C].
WEC
TTh constant -6 can be made arbitrarily large by increasing the constant TC-
12

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Second, it remains to account for making the nodes in B C' singletons. The edges B are already accounted for by Ewec d(w)). To account for the cost of making B C singletons, the following procedure can be used:
For each node w E B C. iterate over all the edges in its adjacency list and
to an edge from E(w, C²) assign weight O; to an edge from E(we B - C) assign weight 1/2; and to an edge from E(w, V B) assign weight 1.
Observe that an edge (x, y with x, y E B C' is counted twice: once in the adjacency list of a and once in the adjacency list of y. Hence, the sum of these edge weights and cost(C) equals the cost of clustering B.
However, using the above procedure directly can result in running time that is too long. Instead, we would like procedure with the running time of B| poly n, 1/e)). Nevertheless, estimating the sum of the edge weights in the desired time is simple. We outline one such approach in Algorithm 5.
Algorithm 5 COST-ESTIMATE
I: Input node sets B and C' C B.
2: cost = Ewec d(w)= - 2( 2((() + IN-CLUSTER- CLUSTEER-COS--SSSMMAAEE COST-ESTIMATE((C)
3: Let 1 def 10 log(n//////
4: for w E B C:
5: Sample 1) edges incident to w, each edge sampled independently and uniformly at random
6: For S E {C, C, V B). let (sw be d(w)/n /n) multiplied by number of sampled edges incident S Zg-c(w) + Zvw)(w)
7: cost = cost + 2
8:
return (cost + 96 (1) 37E)
Let Zs(w) be as defined in Algorithm 5. Observe that E [Zs(w)] c(w, S). straightforward analysis, and identical to that presented in the proof of Lemma A. shows that for e(w, S) 2 2ed(w) the value of (s(w) computed in Algorithm 5 is with high probability a (1 = =) factor approximation of e(w, S). For e(w, S) < 2ed(ww. the same analysis yields that with high probability, it holds that (w) < 3Ed(w). Hence, when e(w, S) < 2ed(w), the estimate Zs(w) is not necessarily within + E factor of its expected value, and thus the error has to be accounted for differently. Next, we explain how to account for it.
Trivially, at least one among e(w, C), e(w, B C), and e(w, V - B) is at least d(w)/3 > 2ed(w), for e < 1/6. e(w, C) 2 d(w)/3, we charge each (s(w) < 3=d(w) the cost of E(w, C)) paid by Ewec d(w). This incurrs an extra cost of at most (2- 3ed(w))/ (d(w) /3) 18c per an edge in Fi,w, C). The analogous analysis applies to the case e(w, V - B)= 2 d(w)/3 3/3 and e(w, B C) 2 d(w)/3. The only difference is that Zn-c(w) is divided by 2 in Algorithm 5, so for that case, the analysis yields 36: increased cost per edge.
Overall, this analysis implies that, with high probability, cost in COST-ESTIMATE is a (1 + 37e) multiplicative and 9e additive approximation of the cost of clustering B. The additive approximation comes from Lemma A.1 and the fact that 3 W-CCLUSTER-COSS--ESSI COST-ESTIMATE(C figures in the output of COST-ESTIMATE.
Lemma A.2 (Cost estimate of single-cluster + singletons). Let E < 1/111. Given two node seis and C C B, let cost" (BIC) be the cost of clustering B in which C is single cluster and B - C are singletons, which defined to be the number non-edges in C' plus the number of edges in B with at least one endpoint in B C. Then, (CCOST-ESTIMATELD BB C) (BlpcootsttCC)))) (Algoritlum 5) outputs X, we have cost" (B C) X < (1 11le)cost* (BIC) + 27=|C). Moreover, the algorithms run in
O( B) (og(n)//))) (n²) time.
Note that since (1 37s) (BIC) S cost < (1+ 37e) (BC)) and X = (cost + 9ccc))) and & < 1/111 we have that cost" cost"(B|C) < X < (1 + (1ll))oosst (BIC)+ 27c
+
A. 1.3.3. COST COMPARISON
Let the estimate that Algorithm makes for cost" (BIC) be cost( C.). We show that cost( is good enough measure for choosing a C' with low cost(* B BCC).
Lemma A.3. cost" (B|C) Z |CI/4 then cost" (B(C( S cost (BCC) $ (1 + 2009) (B(C).
13

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Algorithm 6 COST-COMPARISON
1: Use Algorithm 5 compute (B(C) and (BIC(
2:
if cost( (*) < cost(B
3: return C'
4: else:
5: return C²
Proof. Since |C| 2 4c)st(B|C), by Lemma A.2, we have that cost (B() S (1 + (ie))cost(((()) + 27c|C] (1 (111))coos (BIC) + 108ecost" (BIC) s (1 + 219e)cos!* (BIC).
Lemma A.4. If cost" (BI - [C1/4, thenfor any C' such that C' C C C², we have cost (BIC) cost" (B|C*) and cost(B (osl(B C*).
- 1- 2 - dc(u). So CCI/2 < du).). Now we have cost" (BIC") 2 dc(u)= 2 CC/22 > cost" (BIC). Similarly, suppose C' C C². Take node E C² C. We know that cost" (B) (BCC) 2 dc(u), ) so (u( S [C/4. Moreover, cost" (B) (B|C") 2 |C| dc(u) > 1C1/2.
Proof. First suppose that C' C. Take node C)CC C², know that cost (BIC) IC|
So in both cases cost" (BIC") > |C|/2 > cost" (BsC)
Furthermore, by Lemma A.2 cost (Bst(B(() (BCC) < (1+ /|/4) 27=|C| and by Lemma A.3 we have cost cost(BICC) (1 + 210s) (BIC) 2 (1 + 2 So we have cost B|C") < cost B|C)..
We use Algorithm 6 to develop Algorithm that finds a dense cluster C, inside Bo, where B, the set of all the nodes that are assigned pivot v. Recall that Ce is the of nodes in B, with degree at least
Algorithm 7 BREAK-CLUSTER
1: Input Set By.
2: For any t > 0, let Ct- = {u E Bu, d(u)= 2 t}.
3: initialize 4, = 0, C₁ = Br.
4: for i (1, +1+ c), (1 ()+ (1 +1+ [lgg]]
5: C. #CCCTTTCOMPPPRISONCC,C C, Cp).
6: return C..
For any C' S B, let cost(B|()) be the cost of making C a cluster, and B C singletons. This cost is equal to half the number of edges with exactly one endpoint in B, plus the number of edges with one endpoint in B C and the other endpoint in B, plus the number of non-edges in C. In fact, cosl(B[C) is cost" (BIC) plus half the number of edges that leave B.
Theorem A.5. Let to be the threshold among 1, (1 + +)....... (1 (L+)) +))0)l where cost(BelCrr is minimized. Algorithm 7 returns C₁ then (,, S (1 cost) B. ).
Proof. First note that since cost B., is cost" (B, (C)) plus half the number of edges that leave Br, for any 1, t' we have (B, cost (B,]Cr+) cost" (B, (B,[C)) C.) cost" (e), and thus we can use cost" for comparing the costs, i.e. t* minimizes cost" Ci) as well cost B. Ct).
We prove the Theorem by induction: Suppose that for any j. is the threshold among 1, (1 ee), ..... (1 + E)d such that cost" (Bal (c,, is minimized, and the output of the for loop in Algorithm 7 for E
(1++)) is Cj Fix some i. Suppose that cost" ( (B, (,,) < (1 + 219c c00s)) BB, Ct,). Note that Cf = COST-COMPARISON Br, C,, ((++))+1,, coss) (B,ICa Ct.r))
We show that cost" (B, Ci.n)
< )
For case of notation let C1 = Ct,, C2 = Chur and C" = C(1t)441. So we have C2 = arg mincce cost" (Bal C.). Let ÕN C₁, and Õ₂ Cinn Assuming that cost" (B. < (1 + 219:) (B.(Ci), we need to show that cost" (B,( < (1 219=)cost* (B,(C2), where Õ₂-- = COST-COMPARISON C", C,))).
Note that C" C C. This is because Ō = Cū, and C' = C(Ite)++ where & (1++)) < (1 + s)it!, We prove the rest of the theorem in the following cases.
14

---

Sparse-pivol: Dynamic correlation clustering for node insertions
Case 1: cost" (BIC" < /4 In this case, by Lemma A.4 we know that cost" (BIC)) < cost" (BIC) and
(Bst( < (ost(B(C1) So C2 C². By induction hypothesis, we have cost" (BIC") cost" (B(C))
(L + (Bos))))stt(CCC) Since cost" (BIC") < (1 + 219=)coss* (BIC") and C2 E (C",Ci) we have cost" (B(C2)
cost" (B|C") S (1 cost))
Case 2: cost" (B[Ci < 10:1/4: Similar to ease 1, in this case by Lemma A.4 we know that cost" (BIC)) < cost" (BIC))
and cost cost(B cost( So C2 Cr. By induction hypothesis, we have cost" (B (B))) < (1+ 219:
21+2 cost (B
Since cost" [ (1) < (1 + 219e) (BIC") and C2 E {C', Ci}, we have cost" cost((B(2) = cost" (BIC,) & (1 +1+
2195)cool (B|C2).
Case 3: cost" (BIC") 2 |C"1/4 and (Bst > C21/4: In this case, by Lemma A.3 we have that cost(BIC') and (B)(( are (1 + 219:) approximations of cost" (BIC") and (B(C).
If cost (BCC) cost(B Ci), then have C2 C" If C2 C", then are done. So assume that C2 = C1, which means that cost" (BIC1) < cost" (BIC"). So we have cost" (BIC") I cost(BIC") S cost I (1 + 219:) cost) (B|C1) where the last inequality comes from the induction hypothesis. So we have cost" cost" (BICa) I (1 + 219c) (B) C2)
Similarly if cost B C*) > cost cost(B(C)) (B(C)), ). then we have C2= = Õ₁ If C2 C1, then we are done by induction hypothsis. So assume that C2 = C², which means that cost" cost"(B)(i) > cost" (BIC"). So we have cost" (B C1) S cost(B((r) <
(olC( S (1 + 219t)cost" (B(C"" ). So cost" cost"(BIC2) S (1 + 2105)) (BCC2).
Theorem A.6. Algorithm 7 runs in [B,] poly 1/s) time.
Proof. Note that Algorithm 7 calls Algorithm 6 O n) times. Each run of Algorithm 6 takes |B,l pooy())g(n). 1/e) time: this is because estimating cost( by Algorithm for a set C takes log(n)/E)) time.
A.2. Dynamic version: UPDATE-CLUSTERR(B, u)
The previous section describes how to estimate the cost of clustering B in which C C B is a cluster, while B - C are singletons. When a node is inserted, we cannot afford to estimate these costs from scratch. Rather, we want to update the estimate based on the inserted node.
1. INSERTING A NODE INTO B B-C C
Assume that we already have an estimate of the cost of clustering B as guaranteed by Lemma A.2; let cost be that estimate. Assume that node: = is inserted in B - C. Hence, will be singleton. When cost was computed no edge incident to
2 was in the graph. Thus, updating the cost estimate is easy in this case: the cost estimate of clustering C together and
B- - C + as singletons equals cost + d(z).
A.2.2. INSERTING A NODE INTO C
Assume that we already have an estimate of the cost of clustering as guaranteed by Lemma A.2; let cost be that estimate. Assume that a node 2 is inserted in C. Let cost be the new cost estimate we aim to obtain. Based on Line 2 of Algorithm 5, the difference cost' - cost contains three components: d(2); -2((((+2) + 2(()): and, + +) - 3- -OCLLLTTTEE-TTTTSSTTTAAATTAA can be updated in O(1) time - together with cost, we store the value of IN-CLUSTER- W.-CLUSTER-CCOSTESSTIIMEEE COST-ESTIMATEE(C) that led cost itself. So, it remains to describe how to obtain + z) in poly 1/e) time, as we do next.
3 CAG.LLSTR-CCST--SSTIIN
The first two components can be
updated in O11) time. Even 3-
Let Se be the value of S at the end of IN- ing to CLLLSTTER-COST-ASSTTAATTTA C + 2) that we aim to obtain. We initialize Sc+z Sc, and then update Sc-z as follow.
invocation. Let Sa+z be a value of S correspond-
First, given definition of TC on Line of Algorithm 4, to compute Sc+; we sample 5 log(n)/=² pairs (v, w) E (C + 2) x (C + 2), and for each non-edge (v. w) we increment Sc the same as Algorithm 4 does.
15

---

Sparse-pivot: Dynamic correlation clustering for node insertions
However, the (v, w)) pairs sampled by Algorithm 4 compute Se are simple from C' C, while for Sc+z would like each pair be sampled from (C + 2) x (C z). So, second, account for that, resample some of the pairs used in computing Sc. This also implies that while our algorithm estimates the cost of C by Algorithm 4, it also stores in array all the fu, w pairs it sampled within the for-loop. Let that array of samples be called Ac.
When computing Sc, pair {u, [u,w} is sampled with probability pc = -. However, when computing Sc+2, that same pair is sampled with probability PC+1 = 1/((= Let q PC/Pc41 So, in Ac. we resample pair {u, w) with probability 1-q. q. and otherwise, with probability q, {u, w) is not resampled. With this process, we have that {u, w) C remains unchanged with probability 1/(([/+)) as desired.
If a pair resampled, then the new pair is {z, u), where u a node from C' chosen uniformly at random. So, we have
(1) (1-199))
Pr ((2,u) u is sampled) 1 |
1
2
(1C1T1)
=
C
C| C[+1
(CI+T)
as we aim to achieve. But how many pairs are resampled? How does one choose which pairs to resample in poly(log n, 1/e) time?
The expected number of resampled pairs is
2
E ||Acl -11-0111111 -1- 4) = TC
(llog(n)/E")
|C| +
Hence, by direct application of the Chernoff bound, with high probability, the number of resampled pairs from Ag poly(logn, 1/s).
The final piece elaborates efficiently finding pairs to resample. Consider process that iterates over the elements in Ac and resamples each with probability 1 q. A downside is that this approach takes ((C')) time, which is too slow for our goal. Instead, we observe that the index of the first element resampled in Ac is drawn from the geometric distribution with parameter 1 - q. This observation leads to the following efficient procedure for resampling elements from Ac:
1. Initialize 0.
2. Repeat while S |Ac|:
sample an index j from the Geometric distribution with parameter 1 q:
i= i
if S |Ac|, resample the i-th (u, w) pair in Ag.
This latter approach enables us to spend time proportional to the number of resampled pairs - as opposed to |Acl - which we know is poly(log n, 1 /e)) with high probability.
Lemma A.7 (Dynamic cost estimate of single-cluster singletons). There exists an algorithm that, on a node insertion, updates COST-ESTIMATE((B, C)) in poly(log n, 1/e) time with high probability. The approximation guarantees are the same those stated in Lemma A.2.
A.2.3. UPDATE-CLUSTER(U u)
Subroutine UPDATE- CEAATE-CLUSTERBB.. u) is essentially BREAK-CLUSTER with the costs of C' and B C' updated dynamically as explained Appendices A.2.1 and A.2.2.
More precisely, when BREAK-CLUSTER is invoked, we store all the estimates (B, the sets B, and C,, for t= 1, (1++c), .).... (1 + e) logg Then, we use Lemma A.7 update these costs when is inserted into B, in poly n, E) time. Note that if d(u) 2 f, then joins C, and otherwise u joins B. CC. So each run of Algorithm 6 takes poly(log n, 1/e), and so UPDATE-COST(B.., u) works in poly (log 1/s) time.
B. Recompute
Let ng be the number of nodes the graph just after the last recompute. After /mg/6 updates, we perform a recomputation. Our RecOMpUte procedure is follows:
16

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Purge from the database soft-deleted nodes.
Assign to each node u a rank π (u) chosen uniformly at random from [0, 1].
Initialize p(u) = for all nodes u.
Sort the nodes in the increasing order with respect π.
Insert the nodes, one by one, in this sorted order. The insertions are handled by Algorithm 3, except that a new x(u) value not obtained within Algorithm 3, but is used the one computed in the first step of RECOMPUTE.
The nodes are processed in the ordering based on their π values for the following reasons. Given a node u, Algorithm performs updates or exploration only when ranks are smaller than (u)). In particular, the node v defined in that algorithm used only if (1) I (T)).
The running time of RECOMPUTE is constant factor of the rumning time used to process the insertions. To see that, charge recomputation running time to the eno/6 most recent updates. Observe that this kind of charge is applied to each update during only one RECOMPUTE. Hence, at most no + Eno/6 < 2no insertions are charged to eno updates. So, each update is charged 12/s insertions. Since an insertion takes poly(log n, 1/e) amortized time, this additional charge also takes poly(log n, 1/e) time per update.
C. Auxilary Lemmas
Lemma C.I. Let < be a constunt. Let A be clustering algorithm, where the probability of a node being pivol over all orderings is at most 1/d(v). The expected sum of the degrees of (A) a--ooor nodes is at most 4a 1+3/2 total expected cost of A.
times the 1-5/2aa
Proof. Let Niow( (v) be the neighbors of u with degree at most avd(v). Observe that Noow (v) is independent and A.
The sum of poor-node degrees in a cluster. First, we show that for any æ and v such that e a pivot in wrt to æ, the sum of the degrees of the (A, a-poo nodes in v's cluster most ad(v) min(3ad(v), NN (v)l).
Fix ordering of nodes where v is pivot in A. Note that if New (v) 0. then there no (A, a) -poor nodes in v's cluster, and the sum of degrees of all its (A, a:-poor nodes is zero. Hence, assume Now * 0. The size of v's cluster is at most (v)(vv) since the cluster size is at most three times the degree of an (A, a)-ooor node. The latter is the case as an (A, -pooo node u in a cluster C is not light by definition. Hence, (x) > |C|/3, which further implies |C| < (u) < 3d(u) < 33d(vv, where d(u) S ad(v) be definition of (A, a--poor nodes. So, the sum of degrees of all (A, -poor nodes in e's cluster is at most ad(vv) min(3ad(v), [Noww
The expected sum of poor-node degrees in A. Let Q be the of (A, -poo nodes the ordering æ. Let Pivot, be the event that is pivot in A. We have
Em
Σ d(uu) uEQ
Σ
Σ
d(u)
π
DEPT ref uEQENCT
Σ
Σ
d(u)
nn!
0
K PEEE ref
uEQTNITT
ad(v) min(3ad(v), (No (v))
n!
PE vef
(Nom (Non ad(() min(3ad(v),,
Σ
n!
x: V ref
Pr (Pivotu) ad(v) min(3ad(v), (v)
17

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Note that Pr (Pivol.))
_ in A. Hence, the expected sum of degrees of (A, appoor nodes in A is at most d(e)
Σ min(I (v)],
(v)], 3ad(v))
Σ
(M)
(3)
v.Niow
Lower bounding the cost of A. Now, we compare the above value to the cost of A. (The analysis we provide applies to the cost any clustering, even the one incurred by the optimal solution.) Fix a ordering т. All the costs below are defined wrt R, and we avoid the superseript x.
Recall that for vertex w, CA (w) denotes the cluster of in A. We define cost function cost redistribute the cost cost follows
2 (w)) + Enecatin) costa(u))
cost A (
[Ca(w))
In other words, in cost A, node w distributes 1/2 costa over the [Ca(w) nodes in C (ww),, and w itself pays for the remaining 1/2- cost (w) Note that c c 2 (ost and En cost ( = Σn. cost (w).
Now compute E (v) for with Npoor (v) + 0. Note that are not conditioning on being pivot here. Let t = pap and let t' = min 3ad(v)). We consider three cases based on [C^(v)]:
Case [Ca(o)] 2 d(v) + : then, there are at least & non-neighbors of in Ca(e) and hence costa(w) 2 t' Also, (w)) cost (w) 2 5
Case [Ca(0)] S d(u) - : then, at least neighbors of v are outside of CA(v) and hence cost (w) 2 (w)) cost こ 5/2
'' Again, 2
Case d(v) L' < (Ca(e)] s d(v) + 2: Let t" |Noww (v) n Ca()). The number of non -eighbess of node u E Npoor ( (v())
(1) is least [Ca(v)] - -d(u) 2 d(r) - 1' /2 ad((v) 2 (1 (1-5/2 5/2 ad)(r)), where we used the fact
that f1/2 < 3/2 ad()) (v). So
Σ (
cost 2
cost 2 (1 - 511-5/2-10 5 uc NENiou(t)nCAlt
Σ
Moreover, each node u E (1) \ Ca()), incurs one unit of cost. Also, by definition, 12 |N Therefore, A (v) 2 t". Recall that this case assumes [Ca(v)] d(v) /2 < d(o) 3/2 ad(v) = (1 + 3/2 a)d(v). This yields
2 cost 2t 2--+" +"+ t" (1/25/2.10 a)d(v) (
2t t t" t" 1 - 55/2
(4)
[CA(v)]
1+3/2
Observe that for x: E [0 and t 2 1" we have (1-x))² (1 x:)t., and hence 1. 1t 1" 1"xx 2 tr.. Thus, Equation (4) implies
1+ > 1 5/2
1 1- 5/2 a
2 cost
1 3/2
Therefore, in any case, (v) 1 1-11-/22- So, the total cost of clustering A is at least 1+3/2-a'
min((Noooo (1)) 3ad(v)) 1 - 55/2--.
1 3/2
(v)
Note that the above lower bound is deterministic; in particular, it holds for any randomness used by A. Comparing this
lower bound to Equation (3), conclude that the expected sum of degrees of poor nodes most 4a 1+3/2-a (expected) total cost of A, as advertised by the claim.
times the 1-5/2-a
18

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Lemma C.2 (Cost of making light and heavy singletons). Consider a fixed ordering n and a clustering algorithm A. Let A' be the algorithm that first runs A and, after, makes a subset of A-light and A-heavy nodes singletons. The cost of A' is at most 8-1
S+1 the cost of A.
Proof. For any algorithm B, let dfm (u), d (u) and d (u) be the number of neighbors of u inside its cluster, number of neighbors of u outside its cluster, and the number of non-neighbors of u inside its cluster, respectively. Note that since is fixed, algorithm / determines the clusters. Let cost denote the cost of algorithm B (with respect to πT). We have 2 cost R = 2., [dgue (u) + din(()), Let L be the set of A-light nodes that A' makes singletons, and H be the set of A-heavy nodes that A' makes singletons.
We can write the cost of algorithm A' as follows:
2cost =
Σ d(u)+ +
Σ HELUH
(doue(1) + +d (u)] S
Σ uELUH
[d(u) + (u))
+
Σ LUHH
(duua()) + dih (w)
HELUH
where the inequality comes from the fact that going from A' to A, any new cost on a node u & LUH is due to an edge inside u's cluster in that it attached to a node in L U H. We prove that Ed()) + d [u) I 3-1 EuELUH (d (u) +
S+1
dA sn (u)] Given this, we will have that cost S 8+1 costs
If is A-heavy, then d(u)= 2 (w)) 2 BBdgh (u). So dotn (u) 2 (3 11dd (u), and hence d(u) + d (u) = dotee (u) + 2d (u) < 3+1 doue
If is a light node, then we have that (u) S [Ca(u)1/3, so (u) S j (u), and hence d(u) + dí (u) done (u) + 2d (u) I du) + (u).
Lemma C.3. Consider a fixed ordering x and a clustering algorithm A, and consider a A-bad cluster C*.- Then, its cost is at least 3 (1-7)|CAPP
Proof. Recall that a bad cluster does not have any (ref, appoo nodes. So, all the bad nodes in a bad cluster are either light or heavy. Let C' Cves.
For light node u C, the cost of u is at least 2/C1/3, since dc(u)= |C|/3. For heavy node C. the cost of
is at least (B3 - 1)(CI/2, since u has at least (3 - 1)|C| neighbors outside C. So the cost of any bad node in C' is at least min {(3 - 1) 2/3] -C). There are at least (1 -)][C| many bad nodes in C. Thus, the total cost of C' is at least min {(B - 1)/2,2/3} -01 (1))) IC12. Since 3 2 4, min {(3 - 1)/2.2 = 2/3.
D. Ommited proofs
D.1. Proof of Lemma 3.4
It holds that Pr (I(1)= < L'/d(() DE Pres) = 11 probability:
Pr Pr(((()= -1-P((m(V) L'/d(u) DE P.es). and we upper-bound the latter
Pr ((()) L'/d(u) and Pres)
Pr (T((())= > L'/d(o) u uE
Pr Pr(uE Pres)
= d(v)) Pr(T(v) > T. /d(v(() and Vu E N(O) <()) > a()))
s <d(v) (1 S d(v) -
L' d(x)+1
d(u))
In the derivation, we used the fact that the entries of π are chosen independently and uniformly from range [0, 1]. Now note that d(u)e-L' S logn nct1 so Hence, Pr (()) S L /d((w) E Pres) 2 1 (c-1), as desired.
19

---

Sparse-pivol: Dynamic correlation clustering for node insertions
D.2. Proof of Lemma 3.5
Let L' = L/23. Let A be the set of first (1 (L-e)Crer())looodd good nodes in Cres(v) and let B be the set of last (C)oo())lgood good nodes in (ver(v). So (r))(o) = A U B.
First we introduce some notation: For two nodes u and w where w is inserted before the degree of vertex w at the time where u is inserted is denoted by (w). Recall that the current degree of w is denoted by d(w), and d(w) 2 (w).
Next, note that the pivot v comes after all the nodes in A, then since v is a pivot in REFERENCE CLUSTERING by Lemma 3.4 we have that whp T(v) S. L'/d(e) < L/d(o) and so scans its neighborhood and invokes EXPLORE(U) which assigns all these nodes to as their pivot. So suppose that comes before the nodes in B.
Now consider good node heavy, we have d(u)= S (1)) S Bd(v).
[good and suppose that comes after in the dynamic ordering. Since is not
We compute the probability that u is assigned to v's cluster and also that u invokes EXPLORE(U). In particular, we want conditioned on TTv) < (u)) i.e., in
to lower-bound the probability that x x(v) < (u) S (- and d( (v)
L
REFERENCE CLUSTERING is in C..
First note that if d(v) S L and d(u) s L, then both these conditions are satisfied. So we assume that max(d(u) d(v)) >
L >>7 L'B.
Next, recall that since v is a pivot in the REFERENCE CLUSTERING, by Lemma 3.4, we have that r(v) V /d)d(r) holds with probability 1 1/nn-1 for a large constant e by Lemma 3.4. Moreover, since (u) S d(v), the probability that (v) L is at least the probability that d(v) I n(u)- Similarly, the probability that (u) S an0(n) is at least the probability that (u)) aln (u) d(u). So:
Pr (u invokes EXPLORE(V) u E Cres(u)) L ((U) < ((u)= S (w) and (w)
L
(i)))= < <m(u)s) 1)
=Pr
S t(u)
L
L
2 Pr
((V) < 7(u) < d())
and d(v) <
(v)) < <>(u)= s
T())
= Pr
(()) < <(())= <
L
(T))) < <<()) $1)
max(d d(v))
L
(T)) < (u)) S (L,(T)) (on(v)((//(())) (L'/d(o) (((()))) L')(()))
= Pr
((V) < 7(1) < max(d(u),
+Pr a(() < m(1)= < max(d(u),
L
(T)) < <m)) S 1, m()) 12/((o) Pr(#(v) E'/((o)
2 Pr
L'
< <T())= < max(d(u),d(v))
L
L'
((()s1)) (1-n-ot)
d(v)
d(u)
If d(v) S d(u), then since d(u)= S (O) 3d(r) and 1/3 = L/2, we have
L'B
L
I/3
< ((u)= <1) (1- (1-n -
Pr (u invokes EXPLORE(T) u E Crer(u)) 2 Pr
< T(u)= <
d(uu)
d(u))
d(u)
d(u) 1/8 (1 (1-n-oth > L L'3
L - L/3
(1 - i- -c-1)
d(u)
L/2
(1 - -n -ot)) 2 aL/2 (1 - n -01)
> d(u)
d(u)
Nnote that d(u)= - T > 0 since we assume that max max(d(u) d(ui) > L T'B.
20

---

Sparse-pivot: Dynamic correlation clustering for node insertions
If d(()) 2 d(u). we use the fact that since is not (ax, A)-poor, we have d(u) 2 ad(()) and so
Pr (u invokes EXPLORE(U) u Cres(u)) ( Pr
L'
< <(u) -
L
L'
< ((u) $1 (1 (1-n
{())s1)
d(v)
d(o)
d(u)
L - L'
L/2
(1-n
2 d(v)
(1 (1-n-et))
d(u) 1
aL/2
(1 - n =
d(u)
The above inequality holds for each u E B. We show that with high probability, node in B invokes EXPLORE(U). First recall that (v) is a good cluster, so (w))ood) 2 7|C| 2 yd(u)/B. Thus we have |B] 2 ved(u)/B. Let 43"
<ra
Since (1 (1-n-cth) c+1 > 1/2, we have:
tL [B]
Pr (u invokes EXPLORE(()) N
So the probability that none of u. B invokes EXPLORE(U) is at most (1
1I.
) S Se-LL S n where we use
[
L 4e3 log n & log n. So with probability 1 n- EXPL.OR(()) is invoked by node in B, and all the nodes in A cya
going to be assigned to their pivot.
D.3. Proof of Lemma 3.7
Let k C* and let be the smallest power of (1 + +e) no smaller than 3. So 2 <15 2k(1+c) Let S = C* \ Cr. and let T = C. \ C². We refer to the clustering where C₁ is one cluster and all B, \ C2 is singleton as e1 and the clustering where C* is one cluster and all B, \ C" is singleton as e
The cost of C₁ and ex differ in edges and non-edges with one endpoint in S or T. They share any other cost associated to an edge or non-edge that is in disagreement with the clustering. So we only need to compare the excess cost that is not part of this common cost.
By the cost of a node ESUT, we mean the number of & S TU where we is in disagreement with the clustering plus half the number of S U T where is in disagreement with the clustering. We let cost denote the cost of u in clustering e E {e,, e* }. Let cC) Note that the total cost of e is the sum of the individual costs of u E S UT, plus the common cost between e and e*
First, assume that [T| S k. We show that cost(E;) S م cost(
Consider a node u E S. In C,, the cost of u at most /. since each node in has degree at most 4, and is a singleton in C,. In Cg. the cost of u is at least k-f since there are at least - t non-edges attached to u in C*. Note that for < [k(1+cc we 3
2 have cost(u)e. S t < 1- (T= t)/2 S 1-2. cost(u)e..
To compute the cost of E T, for set C recall that dc(u) is the degree of u inside C. So d(u) - dc. (u) is the number of edges attached to u outside C. In e the cost of u is the number of nodes attached to u outside of C2 plus the number of nodes not attached to u inside C, \ T. plus half of the number of nodes v E T that not attached to So
cost(u)e, d(u) de, (u) + (ICx) - |T' dayrr) + (IT)- - 1 d
< d( (1) do, (w) + (|Ca) - -171 donxr) + (17) - 10_-dr1 (u))
|C&l + d(u)- - - 1-22c, 1-2dc, 2dc,(u)
< [T] + |C nCl d(u) (w)
s 2k + 2dr(u) (u)
Meanwhile we have that there are at least d(u) dy (u) nodes attached to outside of T' so we have
cost(u)e, = d(uu) - du( + dr 22) - dr(u)
2
Note that when for t 2 2k/3, we have 2k + - (d) < 4( ((-dd(íx 1-2 cost((t)))
2 ) so cost(u)e, S 4cost(u)e And so cost(E 5
21

---

Sparse-pivot: Dynamic correlation clustering for node insertions
Now suppose that [T] k. Let cluster E₂ be the clustering where all the nodes in B, are singleton. In fact, C2 is the clustering for when 1. n. In this case, the cost of E2 is the cost of e* plus the number of edges between the nodes in C Now to bound cost(C"), the cost of cost(e*) is at least the number of edges with at least one endpoint in T. This value is at least t t|T)/2 /2. So cost( ) 2 //T Now since [T] 2 k and 2 2k/3, we have
We have (Cs) & cC*t((*)) + k²
3 . 1 2 /2, so cost(C2) S cost(C") + h2/ /2 S cost(C") + 3 1/71/2 & 4cost(e"))
E. Running Time Analysis
In Appendix B, we show that RECOMPUTE subroutine takes poly(log n, 1/e) amortized time per update. Next, analyze the running time of Algorithm 3 and prove Theorem 2.2.
Proof. We first introduce some notation: Let the degree of node w at the time of the insertion of node u be d(w) Recall that d(w) is the current degree of wo and d(w)= 2 d(")(w)
First note that if (u) > L/d(() (u), then the running time is Ollog n) plus the running time of UPDATE-CLUSTER, which is in poly (log n, }) S poly (log T, time; see Appendix A.2.3 for details.
Next, consider the case where Tu)) < L.d(t)()) For each such we set aside a budget of L/T(u) poly(log n, 1/e). In this case, the algorithm scans all the neighbors of u, which takes d(x) (u) < L/ π (u) time.
Next, we analyze the running time of EXPLORE. For this, consider a pivot node v. Note that when we run EXPLORE on a node v, we scan all its neighbors, and if a neighbor w also a pivot, we scan all of the neighbors of w as well and remove w from being a pivot. Observe that once node is removed from being pivot, it can never be pivot until the next recompute, when nodes get new ranks. We pay for scanning the neighbors of w from the budget of w, not v. This way, when node runs EXPLORE, it only needs to pay at most d(v)) from its budget.
Now note that a node u might run EXPLORE multiple times. In particular, v runs EXPLORE either when we are processing e, or when a neighbor of v, say u is being processed, and d(d) (v) < L/T(u). In the first case, we pay the cost of EXPLORE from e's budget. In the second case, we pay the cost from u's budget. Note that for a pivot node v, not only we have d(r) (w) < L/)(vv, but also we have d(v) < L/>(u) (see Lemma 3.4) whp.
(v)
So, in total, a pivot node only spends a budget of at most d(v) poly n. 1/8) < L//((V) poly n, 1/e): it spends (o) < d(v) for scanning all its neighbors when it is being inserted, (o) I d(v) when it runs EXPLORE, at most d(v) (possibly) when another pivot runs EXPLORE and removes v from being a pivot, and d(e) (v) d(r) poly (olgll n. 1/8) for running BRFAK-CLUSTER (Theorem A.6).
poly (loy n, 1/E) S
non-pivot node u spends at most 2L/ (w): once for scanning all its neighbors and once for paying for EXPLORE for its pivot v.
Since L n), each node spends poly n, 1/e) + O(log n/)()) Given that rr()) is chosen uniformly random from the range [0, 1]. in expectation, node spends poly (log n, 1/s) S poly(log T, 1/e) running time.
F. Experimenns-continneed
F.1 Approximation guarantee results
Below we include the approximation guarantee on the three remaining SNAP graphs.
F.2. Running Time
Even though theoretically, our running time (and DYNAMIC-AGREEMENT running time) is faster than REFERENCE CLUSTERING, this advantage only appears in very big graphs. This is because both algorithms have a lot of bookkceping. which means that the constant behind the Olog n) running time is rather big. Nevertheless, we show in Table 2 and Table that CEARSE-PIVON is faster than DYNAMIC- DYNAMIC-AGREEMENT
22

---

Sparse-pivot: Dynamic correlation clustering for node insertions
ca-AstroPh
1.0
Relative Clustering Objectives
0.8
0.6
0.4
DYNEMIC-AGREEMENT
SINGLETONS
RVOT-DYNAMIC
0.0
SPARSE PIVOT
0
100
200
300
400
500
Node Arrivals/Deletions
Figure 2. Correlation clustering cost for ca-astroph graph
dit-HepTh
1.6
1.4
Relative Clustering Objectives
1.2
1.0
0.6
0.4
DYNAMIC- AGREEMENT
SINGLETONS
PIVOT DYNAMIC
SPARSE-PIVOT
200
400
600
Node Ariialls/Deeetioss
Figure 3. Correlation clustering cost for cit-hepth graph
Density
DA
SP
253.36
36.75
31.91
114.87
43.08
29.69
69.74
50.77
26.36
52.17
49.27
23.36
42.25
41.23
25.14
Table 2. Running time comparison on Drift dataset
Graph
DA
SP
facecbook
8.14
3.31
email-Enron
9.69
4.48
cit-Hep'Th
20.24
11.53
ca-AstroPh
15.15
3.84
Table Running time comparison on SNAP datasets
23

---

Sparse-pivot: Dynamic correlation clustering for node insertions
facebook
1.2
10-
Relative Clustering Objectives
0.8
0.6
0.4
0.2
ATNAMIC-AGREEMEN
RIVO--YNAMIIC
0.0
SPARSE-PIVOT
100
200
300
400
500
600
700
Node Arrivals/Deletioss
Figure 4, Correlation clustcring cost for facebook graph
24


Reviews:
[{"review_id": "WwWQiPm6dI", "reviewer": "Reviewer_Tvij", "summary": "This paper introduces a new Correlation Clustering algorithm for node insertion / deletion in a dynamic setting. Upon node arrival its edges with all existing nodes are revealed, and we are allowed to make changes to the maintained clustering solution. The algorithm has constant approximation factor and sublinear amortized processing time per node arrival. which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. Empirical results show the new algorithm to outperform state of the art benchmarks.", "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": "> The experiment designs are quite simplified and could be improved in many ways. The results suffice to show that the proposed method outperforms state of the art, but it would be better if the authors also show how the running time scales with changing dataset sizes (number of nodes), the tradeoff between time and approximation ratio (controlled by ), etc.\n\nWe agree that a comprehensive experiment set up would compare running time vs. dataset size. However, the focus of our paper is on theoretical results and validation of the approximation factor. We include experiments to have a full comparison with previous work. \n\n> The paper needs some proof-reading. There are some notations that appear without being mentioned. I couldn't find the definition of the BREAK-CLUSTER and UPDATE-CLUSTER. They have never been formally defined in the main body but directly used. The analysis can also be organized better. I would suggest putting two main theorems about the run-time and approximation guarantees at the beginning of the section so that the reader doesn't have to skim through the whole section to find what the guarantees are.\n\nThanks for the suggestions on improving the writeup; we will incorporate them into the final version. On Page 3, we outline our main ideas. Idea number 3 is essentially Break-Cluster; we will emphasize this in the final version. It takes all the nodes assigned to a pivot v (set  B_v) and makes some of them singletons (so set C_v is the set of remaining nodes). Update-Cluster updates this set when a new node is assigned to pivot v. We will explain these subroutines before using them; right now, they are only described in detail in Appendix A.  \n\n> The algorithm assigns a uniformly random value between [0,1] to every node. The values are used to determine their relative order. Is this essentially the same with randomly shuffling the whole sequence of nodes offline, giving them ranks and treating the ranks as known information?\n\nYes, it is the same.\n\n> Do we have to know the size n in advance so that we can compute the threshold\nfor the algorithm to work?\n\nThat’s a great question. We do not need to know n in advance; that can be addressed by following standard techniques. Namely, when the graph size doubles, we recompute everything from scratch with the new n. This cost of recomputation is amortized over the run of the algorithm; specifically, it is charged to the steps when the current set of vertices arrived. We discuss a similar idea in Appendix B.", "claims_and_evidence": "The claims are well supported.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I checked the major claims.", "experimental_designs_or_analyses": "The experiment designs are quite simplified and could be improved in many ways. The results suffice to show that the proposed method outperforms state of the art, but it would be better if the authors also show how the running time scales with changing dataset sizes (number of nodes), the tradeoff between time and approximation ratio (controlled by $\\epsilon$), etc.", "relation_to_broader_scientific_literature": "The paper mostly builds on existing Pivot-based algorithms for correlation clustering but innovates the algorithm. It can be seen as another variant of online correlation clustering. It is also broadly related to online clustering or general online algorithm problems.", "essential_references_not_discussed": "There are other earlier papers that discuss online correlation clustering, although the settings are less general than this one, where changing previously made cluster assignment decisions are not allowed, but also studies pivot. Some of them are: \n\nMathieu, Claire, Ocan Sankur, and Warren Schudy. \"Online correlation clustering.\" arXiv preprint arXiv:1001.0920 (2010).\nCohen-Addad, Vincent, et al. \"Online and consistent correlation clustering.\" International Conference on Machine Learning. PMLR, 2022.\nLattanzi, Silvio, et al. \"Robust online correlation clustering.\" Advances in Neural Information Processing Systems 34 (2021): 4688-4698.", "other_strengths_and_weaknesses": "The theoretical results are quite insightful for the online correlation clustering community. The algorithm design is also original and gives strong results.", "other_comments_or_suggestions": "The paper needs some proof-reading. There are some notations that appear without being mentioned. I couldn't find the definition of the BREAK-CLUSTER and UPDATE-CLUSTER. They have never been formally defined in the main body but directly used. The analysis can also be organized better. I would suggest putting two main theorems about the run-time and approximation guarantees at the beginning of the section so that the reader doesn't have to skim through the whole section to find what the guarantees are.", "questions_for_authors": "1. The algorithm assigns a uniformly random value between [0,1] to every node. The values are used to determine their relative order. Is this essentially the same with randomly shuffling the whole sequence of nodes offline, giving them ranks and treating the ranks as known information?\n2. Do we have to know the size n in advance so that we can compute the threshold $L$ for the algorithm to work?", "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": "LWVfahItWh", "reviewer": "Reviewer_JpHJ", "summary": "This paper studies the correlation clustering problem on graphs in the dynamic setting. This variant of clustering is an important problem both in theory and practive, and has been extensively studied in different computational models.\n\nTraditionally, most of the algorithms in the dynamic graphs literature consider the setting where edges of the underlying graphs undergo updates, i.e., they are inserted or deleted. This paper considers a more challenging and the less-studied setting of node insertions; when a node is added, then all its incident neighbours are revelaed at intsertion. Naturally, one could simple simluate node insertions by inserting all edges incident to the inserted node – but since nodes can have deegree up to O(n), this leads to undiserable times.\n\nThe paper under reivew studies algorithms that beat such trivial bounds. In fact, for the correlation clustering problem, they propose an algorithm that approximates the optimal correlation clustering objective up to a factor of ~20, and runs in poly-logarithmic amortized time per node insertions and even *random* deletions. The prioir work by Cohen-Addad et al. achieved similar runtime guarantees, but at the cost of a much constant approximation.\n\nThe starting point of their algorithm is a 5-approximate algorithm due to Behnezhad et al. (a variant of the well-known PIVOT algorithm) in the semi-streaming setting. The idea is to take this algorithm and adapt it to the dynamic setting. Some technical ideas involve: picking random ranks for each node, and using this rank to classify nodes depending on their degree, and finally doing some clean-up, so that bad nodes cannot belong to clusters, etc. While these algorithmic steps make sense for the problem at hand, the adaption and especially the analysis are quite cumbersome and require special care. These type of algorithms are in my opinon the *whole grail* in algorith mdesign; easy to describe and understand, but not so trivial to analyse!\n\nI’m not very familiar with the algorithm by Cohen-Addad et al., but the algorirthm that the paper proposes looks very natural and *the right one* to me.\n\n## update after rebuttal\nThanks for the rebuttal. I keep my score as is.", "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": "> One downside is that the empirical improvements over previous algorithms don’t seem that large in practice on the benchmark data-sets.\n\nOn all the benchmark datasets, our algorithm always performs better than previous algorithms. In some cases, the running time improvement is 2-3x; please see Table 2 and Table 3 in the appendix.\n\n> Weaknesses: perhaps matching the 5-approximation of PIVOT would have been more exciting, at least from a theory perspective\n\nIndeed, this is quite an interesting direction for future work. The main bottleneck in achieving this with our approach and analysis is in Break-Cluster.", "claims_and_evidence": "Everything looks fine.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria make sense.", "theoretical_claims": "I did a pass on some of the proofs. I didn't have time to thoroughly check the correctness -- the approach looks very feasible though.", "experimental_designs_or_analyses": "everything is done properly; I also liked that the authors discussed some heuristic approaches to the theoretical algorithm that could lead to better peformance in practice. This work is an example of nice bridge between theory and practice; \n\nOne downside is that the emperical improvements over previous algorithms don’t seem that large in practice on the benchmark data-sets.", "relation_to_broader_scientific_literature": "Relevant to anyone working on clustering across all subcommunities of computer science.", "essential_references_not_discussed": "I didn't come across any.", "other_strengths_and_weaknesses": "Strengths: core problem in dynamic clustering with applications in practice; the node insertion/deletion setting is more challenging than edge updates; the algorithm comes with strong guarantees and easy to understand\n\nWeaknesses: perhaps matching the 5-approximation of PIVOT would have been more exciting, at least from a theory perspective.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "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": "5viOjfF0DS", "reviewer": "Reviewer_aRAg", "summary": "This paper presents \"SPARSE-PIVOT,\" a new dynamic correlation clustering algorithm designed for node insertions. The algorithm builds upon a variant of the PIVOT algorithm and aims to improve the update time and approximation factor compared to the existing state-of-the-art algorithm by Cohen-Addad et al. (ICML 2024). The main algorithmic idea is to combine a fast approximate pivot selection using random sampling with a refinement step that removes poorly clustered nodes. The paper claims an amortized update time of $O(\\log^{O(1)}(n))$  and an approximation factor of $20 + \\epsilon$. The theoretical analysis is complemented by experimental evaluation, showing better performance to previous methods.", "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 thank the reviewer for their kind and valuable feedback.", "claims_and_evidence": "The claims regarding the approximation factor and update time appear to be supported by the provided theoretical analysis. The evidence presented is convincing, with detailed proofs in the appendix. The experiment provides also a strong support, showing the benefits of the new method.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense. The dynamic setting with node insertions is a relevant problem, and comparing against the algorithm by Cohen-Addad et al. (2024) is a reasonable benchmark. The use of both real-world and synthetic datasets is appreciated.", "theoretical_claims": "I partially checked the correctness of proofs in the supplementary section. I reviewed Lemma 3.2, 3.3, 3.4, 3.5. I did not spot any obvious flaw.", "experimental_designs_or_analyses": "I checked the soundness of the experimental setup. The choice of datasets, baselines, and metrics appear appropriate.", "relation_to_broader_scientific_literature": "The paper situates itself well within the correlation clustering literature. It builds upon prior work on PIVOT and addresses the dynamic setting, which has seen growing interest. In particular, the authors consider the dynamic database model introduced recently by Cohen-Addad et al (2024). The relationship to other dynamic algorithms is clearly acknowledged.", "essential_references_not_discussed": "The paper appears to cite all essential references.", "other_strengths_and_weaknesses": "**Strengths:** \n  * The paper presents a novel and theoretically sound algorithm with a significantly improved approximation factor compared to the paper by Cohen-Addad et al. \n  * Provides solid empirical evidence on real-world and synthetic datasets, showcasing the practical effectiveness and improved performance of SPARSE-PIVOT. In particular, the evaluation demonstrates that the algorithm performs better than the main competitor.\n  *  I find the new adaptation of the pivot algorithm quite clever and insightful.\n  *  The paper is well-written and clearly explains the algorithm, theoretical analysis, and experimental results. The appendices provide detailed support for the main claims.\n\n**Weaknesses:** The database model seems a bit unrealistic, but to be fair this is a previously studied and accepted model.", "other_comments_or_suggestions": "Overall, the strengths outweigh the weaknesses. The paper provides a valuable contribution to the field of dynamic correlation clustering with both theoretical and practical significance.", "questions_for_authors": "No 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": {}}, {"review_id": "joJgzZhn5s", "reviewer": "Reviewer_mgYi", "summary": "The authors consider the classic Correlation Clustering problem which, given a complete graph with edges labeled either + or -, the goal is to find a partition of the vertices so as to minimize the number of + edges across parts plus the number of - edges within parts. \nThe has received a lot of attention since its introduction in the early 2000s.\n\nIn this paper, the authors consider the dynamic setting where nodes are iteratively inserted (and not removed) into the dataset and the goal is to maintain a partition that minimizes the Correlation Clustering objective at all time, while minimizing the total running time (a.k.a update time). \n\nThe authors improve an ICML'24 paper which showed how to maintain a very large constant factor approximation to the problem while making polylog n database queries (here a database query is a query of one of the following types: (1) retrieving the degree of a node v; (2) selecting a random neighbor of v; and (3) checking whether two nodes u and v are connected by an edge). In this paper, the authors provide an algorithm with polylog n update time that achieves a 20+epsilon-approximation.\n\nThe algorithm is a refinement of the classic pivot algorithm for Correlation Clustering, called Sparse-Pivot, which combines ideas from previous work on streaming algorithms, post-processing the clusters obtained, and a new sampling strategy to define the pivots (looking at O(log n) random neighbors).", "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": "> On the other hand, from a theoretical perspective, the technical novelty is not very high.\n\nWe believe our algorithm is intuitive and relatively simple, which we view as a clear advantage—particularly from an implementation standpoint. However, proving that those natural ideas significantly improve approximation guarantees of previous work turned out to be challenging. We would be happy to see a simpler analysis, though, if there is one.\n\n> No particular comments. Given that your algorithm seems to experimentally outperform ICML'24 and the pivot algorithm, I think it makes sense to experiment with it in a purely offline setting as well: could it be that your algorithm is the state-of-the-art for (offline) correlation clustering practical instances?\n\nWe do not think that our algorithm outperforms [1] in the offline setting.\nIntuitively, our algorithm outperforms Pivot because it “fixes” bad clusters made by Pivot. Those fixes are reflected by Break-Cluster method. Namely, if a cluster obtained by Pivot has many non-edges, Break-Cluster attempts to improve it by making some of the nodes singletons. We generally believe that studying this kind of local improvements is an excellent research direction. Some of the prior work, e.g., [1] that you referred to, performs this kind of local improvement, although not directly on Pivot clustering. We believe that there is room to perform relatively simple local improvements and also achieve an approximation better than 3.\n\n> I am wondering whether the result of the ICML'24 paper allows to define \"admissible\" edges in the sense of [1]. And so you could avoid the cleaning step by only performing pivot on the admissible edges. But that's maybe a long shot.\n[1] Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang: Combinatorial Correlation Clustering. STOC'24\n\nThese are great questions and good directions for future work. Having admissible edges in the sense of [1] requires maintaining pre-clustering dynamically, which might be challenging.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked most of the proofs.", "experimental_designs_or_analyses": "Yes, comparison to previous work (ICML'24) is done carefully.", "relation_to_broader_scientific_literature": "Looks good to me.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The paper makes a significant improvement over the approximation ratio and interestingly this turns out to be pretty relevant for practice as well, despite previous pivot-based approaches being not so strong in practice (in fact, as shown by the authors, the vanilla pivot algorithm performs worst than all-singletons). \nOn the other hand, from a theoretical perspective, the technical novelty is not very high.", "other_comments_or_suggestions": "No particular comments. Given that your algorithm seems to experimentally outperform ICML'24 and the pivot algorithm, I think it makes sense to experiment with it in a purely offline setting as well: could it be that your algorithm is the state-of-the-art for (offline) correlation clustering practical instances?", "questions_for_authors": "I am wondering whether the result of the ICML'24 paper allows to define \"admissible\" edges in the sense of [1]. And so you could avoid the cleaning step by only performing pivot on the admissible edges. But that's maybe a long shot.\n\n\n[1] Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang:\nCombinatorial Correlation Clustering. STOC'24", "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 paper addresses dynamic correlation clustering with a significant improvement in approximation factors and sublinear update times. It builds upon Pivot-based methods, refining them with a novel procedure to handle poorly formed clusters. The algorithm achieves a constant-factor approximation and delivers superior empirical results, consistently outperforming prior approaches. 

Reviewers commented on the clarity and organization, highlighting how it bridges theory and practice. Despite the algorithm’s seemingly simple design, the underlying analysis is nontrivial and yields substantial benefits in both solution quality and speed. Overall, this work marks an important advance in dynamic clustering research and suggests intriguing directions for future explorations.
Decision: Accept (spotlight poster)