Robust Online Correlation Clustering
Authors: Silvio Lattanzi
Benjamin Moseley
Sergei Vassilvitskii
Yuyan Wang
Rudy Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: online algorithms
correlation clustering
algorithms with predictions

Abstract: In correlation clustering we are given a set of points along with recommendations whether each pair of points should be placed in the same cluster or into separate clusters. The goal cluster the points to minimize disagreements from the recommendations. We study the correlation clustering problem in the online setting., where points arrive one at a time, and upon arrival the algorithm must make an irrevocable cluster assignment decision. While the online version is natural, there is a simple lower bound that rules out any algorithm with a non-trivial competitive ratio. In this work we go beyond worst case analysis, and show that the celebrated Pivot algorithm performs well when given access to a small number of random samples from the input. Moreover, we prove that Pivot is robust to additional adversarial perturbations of the sample set in this setting. We conclude with an empirical analysis validating our theoretical findings. 

Robust Online Correlation Clustering
Silvio Lattanzi Google Research silviol@goog/e com
Benjamin Moseley Carnegie Mellon University cmu edu
Sergei Vassilvitskii
Google Research bergeivggoogle
Yuyan Wang
Rudy Zhou
Carnegie Mellon University yuyanw@andrew. cmt.trrewww...eeoom.mm edu
Carnegie Mellon University rbz@andrew.c cmu edu
Abstract
correlation clustering we are given set of points along with recommendations whether each pair of points should be placed in the same cluster or into separate clusters. The goal is to cluster the points to minimize disagreements from the recommendations. We study the correlation clustering problem in the onlinc setting, where points arrive one at a time, and upon arrival the algorithm must make irrevocable cluster assignment decision. While the online version is natural, there a simple lower bound that rules out any algorithm with a non-trivial competitive ratio. In this work go beyond worst case analysis, and show that the celebrated Pivot algorithm performs well when given access to a small number of random samples from the input. Moreover, we prove that Pivot is robust additional adversarial perturbations of the sample set in this setting. We conclude with an empirical analysis validating our theoretical findings.
1 Introduction
Clustering is a central unsupervised learning problem, which comes in many flavors and variants. For instance we may consider different objectives for the clustering: k-clustering like k-means or k-median, spectral clustering, or correlation clustering. Or we may try to perform the clustering in different computational models batch, distributed, parallel, etc. A setting that has received a lot of interest in recent years is the online paradigm, see for instance, Zhang et al. [2004], Vidal [2006], Lattanzi and Vassilvitskii [2017], Cohen-Addad et al. [2019], Guo et [2020, 2021]. In online clustering elements arrive one by one and they are irrevocably assigned to clusters at arrival time.
key property of this setting is that the resulting clustering stable. This is particularly important in real-world systems where clusters are served directly to users used in downstream machine learning tasks, and so modifying the clustering has a high cost.
Clustering problems like k-median and k-means are well studied in the online setting, see for instance the groundbreaking work of Mcyerson [2001] and Liberty al. [2016]. This paper considers the onlinc correlation clustering problem, which is less understood. Correlation clustering was introduced by Bansal al. [2004]. In the problem we are given input a weighted graph with nodes, where positive edges represent similarities and negative edges represent dissimilarities between endpoints. partition of the nodes into clusters should minimize the sum of the negative edges contained in any cluster and the sum of positive edges between clusters. That is, minimizing the disugreements the clustering. Correlation clustering has many applications, for instance in finding clustering ensembles [onchi al., 2013], duplicate detection [Arasu et al., 2009], community mining [Chen et al., 2012], disambiguation tasks [Kalashnikov et al., 2008), and automated labelling [Agrawal et al., 2009, Chakrabarti et al., 2008].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

The problem is known to be NP-hard and admits approximation algorithms. For the most studied version of the problem, where the weights are restricted to be 1-1++1, and a 2.06 approximation algorithm was shown by Chawla et al. [2015]. When, in addition, the number of clusters is upper- bounded by k a polynomial time approximation scheme was shown to exist by Giotis and Guruswami [2005]. For arbitrary weights (log n) approximation is the best known [Demaine et al., 2006].
We consider the online correlation clustering problems when edges have weights in (-1++13. In the online sctting, nodes arrive one by onc and reveal their edges to nodes that have arrived previously. The algorithm needs to make an irrevocable cluster assignment when a node arrives. The most popular form of analysis of online algorithms is competitive analysis where the performance of the online algorithm is compared to the best (in hindsight) optimum solution.
It is impossible to design an online algorithm for correlation clustering that has a good competitive ratio. Consider the following example. Suppose that the first two nodes to arrive are connected by positive edge. The algorithm has to commit to either placing them in the same cluster, or in different clusters. If places them in the same cluster then the adversary places the remaining n 2 nodes as follows. The nodes are split evenly between two complete cliques with all positive edges. The two initial nodes are placed in different cliques and there are no positive edges between cliques except the single edge between the two initially arriving nodes. The optimal solution in hindsight makes 1 disagreement by placing the cliques into two separate clusters, while the algorithm makes least (n) disagreements.
On the other hand if the algorithm places the first two nodes into different elusters then the adversary chooses the remaining instance to be a single clique of positive edges containing the two nodes. The competitive ratio of the algorithm will be unbounded as the optimal has cost O and the algorithm has a positive objective value of at least one.
This lower bound example (first observed in Mathicu et al. [2010]) rules out finding good algorithm via competitive analysis, since every algorithm will have a worst case competitive ratio of (n)). However, in practice, instances requires going beyond worst case analysis. For a rich body of work on this topic see the recent text by Roughgarden [2020]. This line of work considers broadly applicable models that avoid pathological worst-case instances that are unlikely to occur in practice.
typically far from worst case. To rigorously study these situations
In practice, for online clustering problems, it is common to have some information about nodes that will arrive. For example when clustering temporal data we have access to last month's 'ss data and this data gives some insights on tomorrow's data. Motivated by this, it is natural to study model where one has access to few samples of the input data representing the past data that has been observed. Of course, if the sample is completely adversarial the problem has not become any casier. To overcome this limitation we follow previous work [Korula et al., 2018, Lykouris et al., 2018] and consider a setting where the algorithm has access to random sample of data.
The model considered as follows. Suppose that for any (potentially adversarially chosen) input, the algorithm is given small number of random samples from the input before the rest is revealed online. Can we prove that it is possible to design online algorithms that are near optimal? If possible, can the model be strengthened such that some of the sample is randomized while some is adversarial and we can design robust online algorithms for this more challenging setting? We answer positively to both questions in this work.
Our Contributions. We introduce the semi-online model for correlation clustering. In this model elements arrive online in adversarial order but beforehand a small random fraction of nodes are revealed. This setting captures situations where some part of the online input is available beforehand, a common case when analyzing temporal data. A similar semi-online model for bipartite matching is introduced by Kumar et al. [2019], where part of the input graph is predictable and known offline, while the remainder is unknown and arrives online.
We prove that the well-know Pivot algorithm [Ailon et al., 2008] obtains a constant fraction ap- proximation in the online setting when a small fraction of points selected at random is revealed beforchand, The key insight behind our proof is that the Pivot algorithm can use a small random sample to "sparsify" the input instance so that it is casily clusterable.
Furthermore, we show that even if a fraction of the sample is adversarially corrupted the Pivot algorithm can still recover a constant approximation. In other words, the approach is provably robust.
2

---

Finally we analyze our finding empirically and verify that the theory is predictive of empirical results. We show that even on "adversarial" inputs the Pivot algorithm obtains good performance has access to small sample of the data. Without the sample, Pivot performs poorly. We further show similar behaviour can be observed when the sample is learned from historical data. These results demonstrate the connection between the theoretical model and practice.
Additional related work. The online correlation clustering problem has been studied by Mathieu ct al. [2010], where they give a -coppeiitee algorithm. However, their algorithm is allowed to re-assign points by merging clusters. Ailon [2008] show that the Pivot algorithm is 3-competitive when vertices arrive in random order.
Our setting is also closely related the algorithm with machine learning advice setting Lykouris and Vissil [2018). J. In this context, Ailon et al. [2018], Saha and Subramanian (2019) study the correlation clustering problem and show that is possible to obtain better performance guarantees using same-cluster queries.
Semi-Online Model for Correlation Clustering
In this paper, we consider the min min- mii-disagreement correlation clustering problem. We first introduce the offline version of the problem.
Definition (Correlation Clustering). The input is a complete signed graph = (V, on n vertices such that the edges are partitioned into positive and negative edges E E+ U UE, respectively.
The goal to partition vertices into clusters, e.g. V == C.... Cz, where k is arbitrary. to minimize the number of disagreements: number of positive edges with endpoints in different clusters plus the number of negative edges within each cluster. We can write this objective as: ExeHHuv E E+ E U &,HH+ E.- E E uuu M.H.
In the online model, the vertices of the graph arrive one-by-one online. The algorithm has to maintain a partition of all arrived vertices into clusters all times. Upon each vertex arrival, its edges (and their signs) to all previous arrivals are revealed. Then the algorithm must make an irrevocable cluster assignment for this arrival. We recall the lower bound in this setting due to Mathieu et al. [2010]. Lemma 1. [Mathieu et al., 2010] For any n, there exists an instance of online correaation clustering where vertices arrive in adversarial order such that every algorithm has competitive ratio M(n).
Semi-Online Model. As discussed, it is impossible obtain any positive result in the online model. Thus, we introduce the semi-onling model for correlation clustering.
Definition 2 (Semi- Online Correlation Clustering). Let G = (V, E) be a complete signed graph. In semi-online correlation clustering, there are two phases: an offtine and online phase.
First, in the offline phase, our algorithu is given the induced subgraph G for some vertex set S C V. Then, in the online phase, the remainder of the vertices V S arrive online. Upon each online arrival, the algorithm must allocate the vertex to a cluster, either starting a new singleton cluster, or assigning to a previously defined one.
The goal is to maintain a clustering of the vertices throughout to minimize the number of disagree- ments.
We will consider different models for how the offline vertices S are chosen. We note that if S is chosen adversarially, then the adversary can choose S to be a graph with only negative edges, and V \ S to be a lower bound instance of size S). This gives a lower bound of a(n [S]). Thus, we focus on models where is, at least, partially chosen randomly.
The algorithm we analyze for the semi-online correlation clustering is the natural adaptation of the Pivot algorithm developed by Ailon al. [2008]. We describe first.
Pivot algorithm
1. Initially, all vertices are unclustered.
2. Consider vertices v E V some order.
3. If is currently unclustered, then mark pivor, and make new cluster consisting of and its remaining unclustered, positive neighbors. Thus, the new cluster is (v) (u V ue Et, unclustered].
3

---

4. Repeat until all vertices are clustered, and output the final clustering.
Pivot's performance critically depends on the ordering of the vertices. If the algorithm considers vertices in random order, then Pivot is a 3-approximation in expectation [Ailon et al.. 2008J.
Pivot can be adapted to the online setting by considering the vertices in their arrival order. As noted, this algorithm will perform poorly on adversarially ordered sequences; moreover as we will it has poor empirical performance well. In the semi-online model, the offlin phase to find better clusters for the online arriving vertices via the pivots computed in the offline phase.
take advantage of
Semi-Online Pivot
1. In the offline phase, randomly order the vertices in S and then using the random ordering run the Pivot algorithm on G[S].
2. In the online phase, we continue running the Pivot algorithm on the remainder of G given the pivots and resulting clustering on G[S]. Note that we consider vertices in the order they arrive online.
Note that the pivots chosen in the offline phase can potentially cluster vertices in the online phase. In particular, if vertex e arrives in the online phase, and u has a positive edge to pivot u chosen in the offline phase, then joins u's cluster. We will show that if S is en-sized random sample of the input, then Pivot is ( c-ompetiiive. Thus a small random sample is sufficient to circumvent the strong lower bounds any online algorithm. We also show that this style of algorithm is robust, even when S is not fully random, semi-online Pivot is guaranteed to perform well.
3 Warm-Up: Pivoting Using Random Sample
In this section, we consider the case where a random sample from V of size en for e E (0, 1). We call this the e-random sample model. The analysis of this setting will illustrate the main technical idcas. Later wc generalize to the case where the random sample has a fraction of adversarially chosen corruptions. In this section, prove the following.
Theorem 1. Fix an e E 10, and let have en samples chosen uniformly at random. Then semi-online Pivot is O )(+)-competitive in expectation.
We also complement our upper bound with matching lower bound.
Theorem 2. For any e E 1). every algorithm in the c-random sample model has competitive ratio !
Proof. To prove the lower bounds, it suffices consider < Fix a sufficiently large n such that + en S n. We define graph on n nodes. All edges are negative except those on set of vertices. The edges on L form a lower bound instance of size guaranteed by Lemma
The probability that the random sample S contains no vertex from L is: P(S n L = 0) = (1 1/9)... (1 algorithm is (2)) comppttiive,, because arrives in adversarial order.
1/c - (1 ع emn 2(1). Further, conditioned on this event, the cost of any
We now prove the upper bound. Our proof will proceed in two parts. First, bound the cost of semi-online Pivot on the random sample S. Recall that these vertices arrive in random order, so we can leverage the analysis of the original Pivot algorithm.
Second, we bound the cost of V \ S. The main difficulty here that S arrives in adversarial order. To overcome the Q(n) lower bound, we first prove more refined lower bound on the optimal solution in terms of the positive degrees (number positive edges incident on vertex) in the input graph. Then we show that running semi-random Pivot on S sparsifies the remaining graph on V \ S. That is, there are few positive edges on the nodes no adjacent to pivot in the sample. Finally, we relate the cost of Pivot to the positive degrees to complete the proof.

---

3.1 Pivot Preliminaries
Throughout this section, let OPT denote the number of disagreements made by the optimal offline algorithm on G and ALG denote the cost of semi-online Pivot. Note that OPT is fixed quantity, while ALG depends on the random choice of S and its order.
We begin with the concept of bad triangles, which we use to lower bound OPT and upper bound ALG.
Definition (Bad Triangle). bad triangle in is a triple of vertices. t t= ijk such that two edges among them are positive, and the remaining edge is negative. We let T denote the set of bad triangles in G.
By case analysis one can check that any clustering must make at least one disagreement in a bad trian- gle. Similarly, the Pivot algorithm makes a disagreement on edge ij if and only if there exists a bad triangle ijk of unclustered vertices such that k is chosen as pivot. This motivates the definition for any bad triangle of the event A, {one vertex of is chosen as a pivot while all three are unclustered). By linearity of expectation, we can write our expected cost as:
B[ALG]
Σ P(A.). LET
(1)
We emphasize that this expression holds for any distribution of arrivals. The only difference the probabilities of the A,'s. We will re-use the same notations and expression when we consider a random sample with corruptions later. However, for the remainder of this section, all probabilities are with respect to the e-random sample model unless otherwise noted.
To formalize the two main steps in our proof sketch, we decompose the above quantity into two parts: one for S and one for V S. To this end, we define for each bad triangle the events A {one vertex of t is chosen as pivot in S while all three are unclustered) and A {one vertex of is chosen as pivot in V AS while all three are unclustered].
We can write: E[ALG] cost(S) + cost(V \ [), where cost(S) Eier P(45) and cost(V S) =ier P(4,)) (55). We will analyze each of these two terms separately. In particular, we first show that (S) ((OPT) by relating to Pivot in random order. Then we show cost(V) ( by relating to the positive degrees. Combining these two bounds with the above expression for [LG completes the proof of Theorem 1.
3.2 Bounding Cost of S
We show CS) (OPr)) Because the vertices of S are a random subset of V and we can analyze them in random order. the first en arrivals of the e-random sample model are distributed identically to the first en arrivals in the model where all vertices arrive in random order. We rely on the next theorem from Ailon et al. [2008], which bounds the cost of Pivot when vertices arrive in random order.
Theorem 3. [Ailon et al., 2008] If vertices arrive in random order, then Pivot is 3-competitive in expectation.
Now we use that Equation (1) holds for both the c-random sample model and the random order model. We denote the former distribution with subscript S and the latter with subscript R. Let RAND de- note the cost running Pivot the random order model. Then applying Equation (1) and Theorem 3, we have: cos = Σter IPs (A5) ΣeET PR(AA) < EtET P (A,) = E RAND]] < 30Pт.
The second equality follows from the observation that the first en arrivals in the e-random sample model are distributed identically to the first en arrivals in the random order model, and the event A, does not depend on the arrival order of V \ S. Thus for any bad triangle t, (AA) PR(AA)) To understand the latter probability, in the random order model we use the convention that the ordered set S is the first en arrivals.
3.3 Bounding Cost of V A
We show cVs \ S) = 0 OPT. We begin with a lower bound on OPT terms of the positive degrees. Because every clustering must make at least one disagreement on each bad triangle, we can
5

---

interpret a clustering as covering all bad triangles using edges (which are the disagreements that this clustering makes.) Further, every bad triangle has two positive edges, so we show that the number of bad triangles that any edge can cover is proportional to the positive degrees of its endpoints.
Lemma 2. Fix any clustering C and let E" denote the set of edges that C makes a disagreement on. Then [T] < EijeE a+ (i) + d+ (j), where dt (-) denotes the positive degree of a vertex.
Proof. C must make at least one disagreement each bad triangle. It follows, C' muss cover each bad triangle with at least one edge in E suffices to show that each ij E E' can be in at most dt (i) + at (j) bad triangles. To see this, consider two cases. If ij E E=, ,hen each bad triangle including ij must also have two positive edges ik and jk for some k. There can be at most min(d (d+ (+((() (i), d (j)) such k. Otherwise, ij E+. Then each bad triangle including ij must have one other positive edge either ik or jk for some k. There can be at most dt (i) + d' (j) such k. L
To understand the utility of the above lemma, it is informative to upper bound each d+(x) by the max positive degree, say d", Then Lemma 2 gives [T] = ((d*) OPP. Further, by Equation (1), the expected cost of Pivot (for any arrival distribution) is Eier P(A,) < (T). Combining these two inequalities gives that Pivot is O(d)) -approximaaii even in adversarial order. In the worst case, we have d² = (2()) (as in the standard (()) lower bound instance.)
To overcome this, note that some nodes in V \ S are "pre-clustered" by running Pivot on S. This occurs when a vertex in V \ S has a positive edge to a pivot in S. Bad triangles containing such vertices do not contribute to cost(V) ) .). so it suffices to consider the remaining subgraph of vertices in V S that are not pre-clustered. We show that this random subgraph has small positive degrees in expectation, applying Lemma 2 to this sparse random subgraph allows us to bound cost(V (S..
We can now show our key structural lemma about sparsification. The main idea of the proof is that a vertex has high positive degree, then it is likely that one of its positive neighbors becomes pivot in S. Due to space, the proof can be found in Section B.
Lemma 3. For any E V. define the random variable Nv to be O if is clustered by running Pivot on S (i.e. v E S or v has a positive edge to a pivot in S) or No Hunclustered positive neighbors of in V V(S) otherwise. Then EN, =(.)
To finish our bound on cost(V)) \ S), it remains to combine Lemma 2 with Lemma 3. To this end, we let G' denote the random subgraph of G induced by all vertices in V \ SS that are not clustered by the pivots chosen in S. The key properties of G' are:
Let T be the set of all bad triangles in G.. We have Eter 1 laye S |T"|. To see this, note
that if A y.8 occurs, then no vertex of t is pre-clustered by S. so t E: T'.
The positive degree in G' of vertex v is exactly N, (as defined in Lemma 3.) Note that here we use the fact that if u is clustered by running Pivot on S, N, 0, since e is not a vertex in G².
Let E' denote the edge set of G' and Ex the disagreements made by OPT on the whole graph G. Recall that OPT is defined G, so E is invariant. Then OPT induces clustering of G" that makes disagreements E' n E*
Using the above two lemmas and three properties, conclude: cost(V S) < E|T < EijEEEE (1) + di)( < Ener EN, + EN, o(})OPT. This completes the proof of Theorem 1.
4 Random Sample with Adversarial Corruptions
We now consider the case where S is random sample from V with adversarial corruptions. Our goal is to show that even with adversarial additions to S, pivot has strong approximation guarantees. We assume that generated by the following procedure, parameterized by c (0, and a E (0,c):
c Random Sample with a-Corruption
1. Given complete signed graph G = (V, E), an adversary chooses a fixed set A C V of an vertices.
2. Then uniform random subset R of size (e a) is drawn from V AA

---

3. Our algorithm is given S = R A in the offline phase.
We emphasize the order of events: first the adversary chooses A, and then a random sample R is drawn. In particular, the choice of A does not depend on R. Also, our algorithm is given S in the offline phase, but critically is unaware of which vertices belong A or R.
We briefly discuss some slight variants of our model and their tractability. Sampling (e - a)n from VA A rather than from V itself is mainly for technical convenience; the latter model admits similar theoretical guarantees, because R A is chose to uniform on V V A if R is a uniform random sample of V. However, if we change the order of events, first sample R. and then allow an adversary to remove/replace on vertices from the sample, then the competitive ratio degrades to (((o)). To see this, consider input graph consisting of lower-bound instance of size on guaranteed by Lemma 1 and all other edges are negative. The adversary can guarantee that the lower-bound instance is always outside the sample and thus arrives in adversarial order.
The main result of this section is that the corruptions do not degrade the performance of semi-online pivot; in particular, the algorithm performs if it had uncorrupted sample of size (e - a)n (under the mild assumption that a is at most a constant fraction of e.) We defer the proof of the next theorem to Section A
Theorem 4. For e. E (0,1) and a E (0, semi-online pivot in the c-random sample with a-- corruption model is O (c-ajs -competitive in expectation.
Similar to the random sample model, we have an almost matching lower bound for the c-random sample with a-corruption model under the mild assumption that the corruption is most half of the whole sample. The proof of the following theorem is similar to Theorem 2 and can be found in Scction B.
Theorem 5. For any E (0,1) and a E (0, 2) every algorithm in the e-random sample with a-corruption model has competitive ratio O2 --)
Proof Overview of Theorem 4: The proof of Theorem has the same structure Theorem 1; in particular, we split the cost of semi-online Pivot into an offline- and online phase. The offline- and online phases roughly correspond to S and V respectively. However, the corruptions introduce new challenges in both cases.
For the offline phase, random order model due to the adversarially chosen part of S. Instead, we prove a generalization of Theorem 3 via dual fitting that allows us to handle more general arrival distributions. Roughly, to bound the cost of the offline phase, it suffices to show that if A, occurs in the offline phase, then each vertex of has reasonable probability be the pivot that "causes" At-
longer argue that S is distributed as the first arrivals in the
For the online phase, we still argue by Lemma 2 that it suffices to show that the remaining vertices in the online phase have small positive degree. Here, we prove that even with adversarial corruptions, running Pivot in the offline phase still sparsifies the remaining graph.
Experiments
In this section, we empirically validate our theoretical findings. Specifically, we:
Demonstrate that Pivot's performance can be poor when the arrival sequence is chosen adversarially.
Verify that with small portion of nodes randomly drawn from the dataset (which refer to as advice), semi-online Pivot is competitive with offline Pivot in random order (which is 3 3-aaproxxmmttion to optimum). Further, we show that the result is robust across multiple parameter settings and additional corruptions.
Show that when the advice temporal (and not random) the performance is still strong.
Datasets. We use the following datasets from the Stanford Large Network Dataset Collection [Leskovec and Krevi, 2014]'. Each dataset is a social network where the nodes represent entities
hhtps://snap.stanfor..chht
ego-Facebook:
html, ego-
Gplus: https://snap.staantt wtw.fardd.aao.dd....ooooooo edw/data/ego Gplus.html, noe-Reddiffyperlinkks https://snap.stante wdw//ata/d/d/d/occcccocoo RedditHyyerlinks, htmll soc-sign bitioi--itoin-ote https://snap.stanntt www.uoord.dd/daaa//eeeeeeee edu/data/soc-sitte sign bitcoin- otc.
7

---

such as users or communities, and the edges represent connections between the entities such as communication or transactions. We use two non-temporal datasets: ego-Facebook and ego-Gilus [McAuley and Leskovee, 2012]; and two temporal datasets: soc-Reddittyperlinks [Kumar et al., 2018a] and soc-sign- bitcoin-ote [Kumar et al., 2016, 2018b]. The temporal datasets have timestamps on the edges representing when the connection happened. We refer to these datasets FACEBOOK, GPLUS, REDDIT and BITCOIN respectively. See Table for full description of the four data sources.
To generate signed complete graphs, on directed graphs we convert all ares into undirccted edges, and on weighted graphs we only keep the edges with positive weights. These edges represent the positive edges, and all the other edges are negative edges.
Table 1: Dataset desciption.
Datasel
(#Tdges, Nodes)
Edge Features
Edge Meaning
FACEBOOK
(4039, 88234) (107614, 13673453)
Undirected, unweighted, non-temporal
Users are friends
GPLUS
Directed, unweighted, non-temporal
One user follows another
REDDIT
(55863, 858490)
Directed, weighted, temporal
hyperlink between two subreddits
BITCOIN
(5881, 35592)
Directed, weighted, temporal
A trust rating between users
To perform a richer evaluation, we sub-sample from the datasets to obtain our input graphs in the following manner. The two non-temporal data sources, FACEBOOK and GPLUS, contain ego- networks which represent the lists of friends of pre-selected users and the connections among them. these ego-netwon networks which are sub uub-graphs induced from the entire graph by a subset of nodes. For the temporal data sources, we take all edges with timestamps falling into a time interval and all nodes induced on these edges.
We experiment
Performance Metrics. We use Pivot in uniformly random order as our benchmark. For each arrival order constructed, we conduct multiple trials, take the ratio of the average number of dixagreements for semi-online Pivot over that of random Pivot, and subtract 1 to measure relative improvement, which we call degradation.
Power of Advice. Our first experiment studies the benefit of random sample of nodes. We compare the performance of Pivot with and without advice under different element orderings.
We first test Pivot
uniform random ordering of the nodes. Recall that this is 3-approximation [Ailon et al., 2008] to the optimum. Then we test Pivot in the following adversarial orders: (1) node degree in descending order; (2) number of bad triangles in a node's 's neighborhood that contains this node, in descending order?; and (3) timestamp, in chronological order (only for temporal datasets.)
Next, we explore the performance of semi-online Pivot with advice in the e-random sample model. We produce the advice by randomly sampling an e-fraction of the nodes. Then, in the online phase, the remaining nodes arrive in adversarial order. We test the same adversarial orders before.
Table 2: Mean degradation and standard deviation in Pivot's performance on different sequences, 0.1, 30 trials.
Dataset
(4 Nodes, + Edges)
Random
Degree
Degree w. Advice
Bad Triangles
Bid Trinngles Advice
Time
w. Advice
Time
EaCeBoOx
(534,
108.51
+
%
3.53
N/A
N/A
FACEBOOx
(1034, 53498)
6.00 %
63.19 %
0.19 + 549
63.72
148 1 6.63 %
N/A
N/A
GpLUS
(1650, 166292)
0 20.79 %
133.46 %
9.90 + 23.30
133.66
-0.80 = 17.03 %
N/A
N/A
GPLUS
(3:55, 435569)
0::: 15.35
229.37 %
-3.95 9:95-t10 16.03
229 38 %
-3.91 12.78
N/A
N/A
1.31
139.26
1040%%
REDDIT
(7019. 20724)
0::: 11.36 %
690.05 %
21.28 1: 23.61 %
690.27 %
18.40
11.74 9
79.89%
4.59 1: 8.65
REDDIT
(1-042, 56567)
0:2: 20.23 %
822.60 %
11.09 1: 12.99 %
822.61 %
2.59 1 12.25 18
50,21 %
-1.01 1 H.11 1
Brrcons
(2979. 14695)
0.2: 21.83 8
1070,07
9.75 4: 24.32
1066.81 %
11,70 1: 25.48 8
579.06 $
8.50 2: 40.54 $
See Table 2 for data on the performance of Pivot in different scenarios. Each entry shows the level of degradation compared with fully random Pivot after 30 trials (mean + standard deviation). See Section C for results on all input graphs. The first two columns show the data source and the size of the graph instance. Column "Random" shows random Pivot's performance. Columns "Degree", "Bad Triangles" and "Time" give Pivot's performance on the three adversarial orders mentioned earlier, while the columns next these three show the performance of semi-online Pivot using the advice.
2 For a node with neighbors, this number is equivalent to its clustering coefficient times k(k-1)
'The original temporal datasets only have timestamps on edges. We consider the timestamp of any node to be the earliest timestamp of all edges adjacent to it.
8

---

Digres
100
Dagre
600
0.
0.1
0.5
34
0000
0/65
nd1s
0d0e
0.28
0.50
0irs
(i)
iii)
Figure (i) Degradation v.s. values, REDDIT, (# nodes, # edges) (14042, 56567). (ii)
Degradation v.s. values, when 0.2.
Compared with fully random sequence, adversarial sequence of online node arrivals can cause Pivot's performance to degrade significantly, from 2-10x. Sorting the nodes according to degrees or bad triangles in the neighborhood could causes Pivot's performance to be 1000% worse for some sub-samples. For the temporal node sequences, Pivot's performance is about 50 - 100% worse for REDDIT and 500% worse for BITCOIN. However, when 0.1, semi-online Pivot's performance is only slightly worse (about 10 20%) than fully random Pivot. Thus, with only small advice set, semi-online Pivot almost completely bridges the gap between adversarial and random order.
Robustness. Our next goal is to show that the gains of Pivot with advice are robust to different choices of well adversarial corruptions. Recall that for node set of size the advice has aa) randomly sampled nodes and an adversarially chosen nodes. For each of the four data sources, select sufficiently large sub-sample and change and while producing advice.
For corrupted advice, for any one of the three adversarial sequences, we choose first a fraction of nodes to be the corruptions (i.e. the "worst" nodes as evidenced by the experiments with advice). Then, we sample (e - on nodes from the remaining nodes to complete the advice. The online phase arrival order is the same in the adversarial sequence.
Figure 1(1) shows how degradation changes while ranges in [0.01, 0.5] and and (ii) shows how corruptions in the advice affect semi-online Pivot when = 0.2. Pivot's performance is robust against shrinking the size of the advice and against adding corruptions. For 2 0.05, or with the advice set corrupted by 25%, the performance remains constant. See Section C for results on more datasets.
(no corruptions).
Temporal Advice. Finally, learning the advice from prior temporal data is sufficient for Pivot to have good performance. We test both temporal datasets: REDDIT and BITCOIN. The advice is generated from older data just prior to the time interval of the test dataset. In particular, our advice consists of all nodes in the older dataset, which are incident on edges the test dataset (i.e. the old data that is related to the new data.) After the advice, the test data set arrives in adversarial order including temporal order, where vertices arrive in order of their timestamps.
Table 3: Degradation of semi-online Pivot when using advice from historical data, REDDIT, 100 trials, test dataset has the duration of 6 months.
Days
e-vilie
Random
Teggoe
Degroe w. Advice
Red Triangle
Red Triangle Advvice
Time
Time w Advioe
0.15
14.57 %
42.09 1: 25.19 %
675.12
36.85
20.26
52.08
34,76 d: 23.39
15
0.19
0 0::0
14.57 %
673.10 %
41.09 4 32.35 9
675.12 %
36.85
20.26
%
$2.08 %
36.58
37.41 %
0.22
14.57
675.40
30.76 1 23.27
675.12
36.43
32.97
52.08
41.66
48.21
32.24
Table 3 shows the results for REDDIT when we change the time interval used to generate the advice, which shown in Column "Days" in time unit of days. The time interval for the test dataset fixed to be 6 months. Column "c-value" gives the proportion of nodes in test dataset that appeared in
the old data, which corresponds the parameter in the e-random sample model. See Section for the results for BITCOIN. The rest of the table shows the degradation of Pivot using the advice from the corresponding historical data. Pivot's 's performance improves when we increase the time interval (equivalent to increasing e). Starting with 0.15 (time interval for old data/test data is 10

---

days/6 months), the temporal advice improves Pivot's performance on all adversarial orders. This demonstrates that Pivot works well empirically using advice from historical data.
Conclusion
By augmenting standard online algorithm for correlation clustering with small random sample of the data, we can overcome strong lower bounds for online correlation clustering. We give near- optimal algorithms for semi-online correlation clustering given random sample (with corruptions), and further this theory is predictive practical performance. Empirically, with only a small random sample, semi-online pivot is competitive with offline pivot in random order. Further, in temporal datasets, the sample can be practically obtained from past data. We show that semi-online models, where augment online algorithm with some offline information, be powerful tool in both theory and practice to improve the performance of online algorithms, and we believe they will find further applications in other problems.
Funding Sources
B. Moscley, Y. Wang and R. Zhou were supported in part by Google Research Award, an Infor Research Award, Cameeie Bosch Junior Faculty Chair and NSF grants CCF- CCF. 1845146, CCF-173387, and CMMI-1938909 B. Moseley additionally is a part time employee of Relational AI.
References
R. Agrawal, A. Halverson, K. Kenthapadi, N. Mishra, and P. Tsaparas. Generating labels from clicks. In Proceedings of the Second ACM International Conference on Web Search and Data Mining, pages 172-181, 2009.
N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008.
N. Ailon, A. Bhattacharya, and R. Jaiswal. Approximate correlation clustering using same-cluster queries. In Latin American Symposium on Theoretical Informatics, pages 14-27. Springer, 2018.
A. Arasu, C. Ré, and D. Suciu. Large-scale deduplication with constraints using dedupalog. In 2009 IEEE 25th International Conference on Data Engineering, pages 952-963. IEEE, 2009.
N. Bansal, A. Blum, and S. Chawla. Correlation clustering, Machine learning, 56(1):89-113, 2004.
F. Bonchi, A. Gionis, and A. Ukkonen. Overlapping correlation clustering. Knowledge and informa- tion systems, 35(1):1-32, 2013.
D. Chakrabarti, R. Kumar, and K. Punera. A grephthhe approach to webpage segmentation. In Proceedings of the 17th international conference World Wide Weh, pages 377-386, 2008
S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal Ip rounding algorithm for correlationclustering on complete and complete k-partite graphs. In Proceedings of the forty- seventh annual ACM symposium on Theory of computing, pages 219-228. 2015.
Y. Chen, Sanghavi, and H. Xu. Clustering sparse graphs Proceedings of the 25th International Conference on Neural Information Processing Systems- Volume 2, pages 2204-2212, 2012.
V. Cohen-Addad, N. Hjuler, N. Parotsidis, D. Saulpic, and C. Schwiegelshohn. Fully dynamic consistent facility location. In N Conference on Neural Information Processing Systems, 2019.
E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172-187 2006.
I. Giotis and V. Guruswami. Correlation clustering with a fixed number of clusters. arXiv preprint cs/0504023, 2005.
10

---

X. Guo, J. Kulkarni, S. Li, and J. Xian. On the facility location problem in online and dynamic models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques IAPPROX/RANDOM 2020). Schloss Dagssuhl-Leeinnizzzzemii
für Informatik, 2020.
X. Guo, J. Kulkarni, S. Li, and J. Xian. Consistent k-median: Simpler, better and robust. In International Conference on Artificial Intelligence and Statistics, pages 1135-1143. PMLR, 2021.
D. V. Kalashnikov, Z. Chen, S. Mehrotra, and R. Muray-Turan, Web people search via connection analysis. IEEE Transactions on Knowledge and Data Engineering, 20(1 10(11))1550-1555 2008
N. Korula, V. Mirrokni, and M. Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 in random order. SIAM Journal on Computing, 47(3):1056-1086 2018.
R. Kumar, M. Purohit, A. Schild, Z. Svitkina, and E. Vee. Semi-online bipartite matching. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 10:1000: 2019.
S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos. Edge weight prediction in weighted signed networks. In 2016 IEEE 16th International Conference Data Mining (ICDM), pages 221-230. IEEE, 2016.
Kumar, W. L. Hamilton, Leskovec, and D. Jurafsky. Community interaction and conflict on the web. In Proceedings of the 2018 world wide web conference, pages 933 933-943, 2018a.
S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 333 333-341, 341, 8b.
S. Lattanzi and Vassilvitskii. Consistent k-clustering. International Conference on Machine Learning, pages 1975-1984. PMLR, 2017.
J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. //snap. sww.saaaddd..... edu. data, June 2014.
http:
E. Liberty. R. Sriharsha, and M. Sviridenko. An algorithm for online k-means clustering. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pages 81-89, SIAM, 2016.
T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3296-3305. PMLR, 2018.
T. Lykouris, V. Mirrokni, and R. Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 114-122, 2018.
C. Mathieu, O. Sankur, and W. Schudy. Online correlation clustering. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, pages 573-584, 2010.
J. J. McAuley and J. Leskovec. Learning to discover social circles in ego networks. In NIPS, volume 2012, pages 548 56. Citeseer, 2012.
A. Meyerson. Online facility location. In Proceedings 42nd IEEE Symposium Foundations of Computer Science, pages 436-431. IEEE, 2001.
Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.
B. Saha and S. Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. arXiv preprint arXiv:1908.04976 2019.
R. Vidal. Online clustering of moving hyperplanes. Advances in Neural Information Processing Syytems, 19:1433-1440. 2006.
J. Zhang, Z. Ghahramani, and Y. Yang. A probabilistic model for online document clustering with application to novelty detection, Advances neural information processing systems, 17: 1617-1624, 2004.
11


Reviews:
[{"review_id": "YEGiU1X4NFk", "reviewer": "Reviewer_BymN", "summary": "The paper studies the standard correlation clustering problem in the *semi-online* model. In the most studied variant of correlation clustering, we are given a complete graph where each edge is either +1 or -1 and the goal is to partition vertices into clusters such that the total number of *disagreements* with the edge signs is minimize. The number of disagreements is the number of negative edges in clusters plus the number of positive edges between clusters. In the offline setting, the problem admits a constant factor approximation, but it is not possible to get a better than $\\Omega(n)$-competitive ration in the (adversarial) online setting.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper investigates the problem under the semi-online model. The intuition is that while the problem is hard under the general online setting, a simple Pivot algorithm gets competitive ratio 3 when the nodes arrive in a random order. To limit the amount of randomness in the sequence, authors proposed to consider the setting in which a randomly selected $\\epsilon$-fraction of nodes is given to the algorithm and then the rest of the input arrive in an adversarial order. They proved that with this limited amount of randomness (or advice) the standard Pivot algorithm gets $O(1/\\epsilon)$-competitive ratio and it is tight. Further, they considered the robust variant of the semi-online model where the adversary first picks an $\\alpha$-fraction of nodes, then a randomly picked $(\\epsilon-\\alpha)$-fraction of nodes is combined with the adversary’s pick and feed to the algorithm. Even in this case, under some mild condition the Pivot algorithm achieves $1/(\\epsilon-\\alpha)$-competitive ratio; in other words, the adversary cannot do a significant harm.  Besides, the paper has a nice connection to a recently popular line of research on learning-based algorithms (aka algorithms with predictions). In general, the algorithm and its analysis is clean and nice and I recommend acceptance of the paper.\n\n**Minor Comments**\n1.\tLine 42. a irrevocable -> an irrevocable  \n2.\tLine 140. Pivor -> Pivot\n3.\tLine 142. algroithm -> algorithm\n4.\tLine 304. sparsities -> sparsifies\n5.\tMention related work on correlation clustering on random order online setting.\n6.\tWhat happens if we change the order of items 1 and 2 in the robust model? Do we know that it becomes significantly harder? What is its status.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not foresee any such issues.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SD3-jkHo09", "reviewer": "Reviewer_uASx", "summary": "The authors of the paper consider an online variant of the well-known Correlation Clustering problem, under the minimum disagreements objective function. Specifically, there is a complete graph $G = (V,E)$ whose edges are partitioned into two sets, namely $E_+$ (positive edges), and $E_-$ (negative edges). In the offline version of the problem, the goal is to find a partition (otherwise called clustering) of $V$ into $C_1, C_2, ..., C_k$, such that the total number of negative edges inside the same cluster plus the total number of positive edges between clusters is minimized. In the online case, the vertices arrive one by one (and upon arrival we are also given the edges between the current vertex and previously arrived ones), the goal is to maintain a clustering at all times, by irrevocably assigning each vertex to a cluster. Here the goal is to achieve the optimal offline value with regards to disagreements.\n\nAlthough there exist approximation algorithms for the offline version, it is already shown that the online one does not admit any competitive algorithms with meaningful guarantees due to adversarial instances. The main contribution of the paper here is then introducing a semi-online model, in which reasonable competitive algorithms are achievable. This semi-online setting goes as follows.\n\n1) There is an offline phase, in which the algorithm is given a set $S \\subset V$, and is allowed to start constructing the clustering based on that.\n\n1) Then the remain $V \\setminus S$ vertices arrive in an online fashion (in any order, and the means even adversarially), and the algorithm should start making online irrevocable decisions.\n\nIn this model, the authors provide the following collection of results:\n\n1) They show that if $S$ is adversarially chosen, then any algorithm should have competitive ratio $\\Omega(n)$.\n\n2) If $S$ is a randomly chosen subset of $V$ with size $\\epsilon n$ for some $\\epsilon \\in (0,1)$, then the online extension of an already known algorithm (called Pivot) gives a $O(\\frac{1}{\\epsilon})$ competitive solution. Moreover, they show that is this case, the ratio $O(\\frac{1}{\\epsilon})$ is the best possible.\n\n3) They authors also consider a case where an adversary can corrupt the \"advice\" $S$. Here, the adversary can choose $\\alpha n$ elements of $S$, with the rest $(\\epsilon-\\alpha)n$ ones being again randomly selected. In this scenario, they show that the pivot algorithm achieves a $O(\\frac{\\epsilon}{(\\epsilon-\\alpha)^2})$ competitive solution. Finally, the latter result is complemented by a hardness theorem, showing in this scenario the best achievable ratio is $\\Omega(\\frac{1}{\\epsilon - \\alpha})$, and hence the given result is almost optimal.\n\nFinally the authors perform a substantial experimental evaluation that validates their theoretical results. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "CLARITY:\n\nThe paper in general is very well written, and I must admit that I enjoyed reading it. The only suggestion regarding clarity that I have is the following. In the description of semi-online Pivot in page 4, the author should have made it more clear that when a node $v$ arrives in the online phase, if there exists some pivot $u \\in S$ such that $\\{u,v\\} \\in E_+$ then $v$ will be placed in the cluster defined by $u$. In the current format, I feel like someone must read between the lines in order to understand this vital point.\n\nSIGNIFICANCE-ORIGINALITY:\n\nTo me the main contribution of this work is the introduction of the semi-online model for correlation clustering. From a practical perspective, it seems very reasonable to have some \"advice\" in the form of a random set $S \\subset V$. However, I'm not very convinced about the way adversarial corruption is model in the paper. I understand the concept of letting the adversary choose the set $A$ of size $\\alpha n$, but it seems more natural for the random set $R$ to be chosen from $V$ and not from $V \\setminus A$. How can this change alter your robust result? \n\nCORRECTNESS-TECHNICAL DETALS:\n\nI went through all the proofs, except the proof of Theorem 4 in Appendix A,  and all arguments appear sound to me. I really liked the proof of Theorem 1, and I think the way the authors broke down the analysis of semi-online pivot is quite elegant.\n\nCONFIDENCE:\n\nI have to admit that I am not really familiar with the literature on correlation clustering (my area of expertise is metric clustering). Nonetheless, from my perspective and given a brief look of related work, I still think that there is merit to this paper and that its contribution is actually significant.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours reading the paper + 1 hour thinking about the review + 1 hour writing the review"}, "extra_text": {}}, {"review_id": "7dKjkByRnv", "reviewer": "Reviewer_PVDb", "summary": "The paper considers the online correlation clustering problem in the context of having a sort of a soft start with an offline phase where they get a subset of vertices and the induced subgraph. They provide a modification of the pivot algorithm to carry out the online correlation clustering under the defined model. The algorithm has a $O(1/\\epsilon)$ competitive ratio if allowed a $\\epsilon n$ size initial offline set. The paper also argues about the robustness of the algorithm even when the $S$ could have adversarial corruptions.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The paper is well written and the arguments seem sound. They introduce a novel approach to use the established pivot algorithm along with an offline set of vertices to get an algorithm that gives a $O(1/\\epsilon)$ competitive ratio, compared to $\\Omega(n)$ bounds in the online setting (though they work in slightly different settings). The robustness arguments seem to provide additional support to the pivot algorithm being competitive in this setting. They also manage to provide matching lower bounds as well. \n\nTypos:\n140: “then Pivor is a 3-approximation in expectation” => “then Pivot is a 3-approximation in expectation”\n\nNotes:\nPlease check the citation style instructions and make sure to use \\cite and \\citet appropriately.\nMake algorithms slightly more readable if possible (using algorithm environments or something).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not necessarily discuss the limitations. The major limitation that could be noticed was that since the $S$ is derived from $V$ randomly we need to know the set of vertices. But this seems to be a direct artifact of the model.   \n\nAs the problem itself is a classical problem I don’t think it creates any major negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No major ethical concerns as far as I can see. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "4uRkRcrw7E", "reviewer": "Reviewer_AUhK", "summary": "This paper studies the effectiveness of the Pivot algorithm for the online correlation clustering problem under the mild assumption that a small sample of data is available beforehand. It provides improved guarantees for the algorithm's competitive ratio under the beyond worst-case analysis paradigm, specifically, it shows that the known competitive ratio lower bound can be bypassed using a semi-online algorithm. \nA rigorous theoretical analysis is provided, and it is complemented by experimental evaluations.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "# Originality\n\nAlthough the algorithm(pivot) that is being analyzed is not new, considering the recent interests in beyond worst-case scenarios, this paper introduces novel insights on how one can design online algorithms for similar problems. In my opinion, the semi-online setting is the correct lens to analyze and design algorithms for this problem and I believe this paper formulates this notion in a clean way. \n\n# Quality\n\nThe quality of the writing and the presentation is good in general. The results of this paper are placed well among the prior work and the contributions of this paper are clearly stated.\nFollowing are some of the typos.\n- line 22: used in a downstream -> used in downstream \n- line 140: fix reference to Ailon et at. [2008] at the end of the sentence\n- line 322: compete graphs -> complete graphs\n\n# Clarity\n\nThe clarity for the most part is good however, it can be improved in certain places.\n-  In the proof of theorem 1, line 267, 268 can the authors explain why the second inequality holds ($\\mathbb{E}[T'] \\le ...$)? is it because if this is not the case, OPT could have done better? \n- In experiments, in temporal advice(lines 370-375), what is the adversarial order when you state \"including temporal order\"? Can the authors please clarify more how the test data arrive in this case?\n\nApart from these, I have some further questions.\n- In section 4 random sample with adversarial corruptions in line 279, why is the order of events important? What happens for example if a random sample of $\\epsilon n$ is first chosen and an adversary changes an arbitrary fraction of size $\\alpha n$ from that sample? is there any technical difficulty for choosing this order of events?\n- Why is the competitive ratio in theorem 4 \"almost\" matching the lower bound in theorem 5? what are the difficulties of closing this gap? Can the authors please comment on this?\n\n# Significance\n\nHaving some prior knowledge of a small random sample in most cases is feasible and this paper shows how that can be exploited cleverly to develop an algorithm with guarantees much better than what is known from prior lower bounds. This and the fact that one can still hope to perform better with an adversarially corrupted sample up to a certain extent makes this result significant in my opinion.\n\nOverall, I believe this paper is very nicely written and adds nice contributions to the online correlation clustering problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some of the limitations are discussed. Assessing societal impact is not applicable. ", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers an online version of correlation clustering and shows that the well-known Pivot algorithm performs well in the setting. The result is not that surprising, but I think this is an important contribution nonetheless and warrants acceptance.
Decision: Accept (Poster)