Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost
Authors: Sepehr Assadi
Vihan Shah
Chen Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Correlation Clustering
Graph Streaming Algorithms
Large-scale Clustering
Graph Learning
TL;DR: We give polylog(n) space single-pass streaming algorithms that approximate the optimal correlation clustering cost, and we provide memory-approximation trade-offs to justify our approximation.

Abstract: Correlation clustering is a fundamental optimization problem at the intersection of machine learning and theoretical computer science. 
Motivated by applications to big data processing, recent years have witnessed a flurry of results on this problem in the streaming model. 
In this model, the algorithm needs to process the input $n$-vertex graph by making one or few passes over the stream of its edges and using a limited memory, much smaller than the input size. 

All previous work on streaming correlation clustering have focused on semi-streaming algorithms with $\Omega(n)$ memory, whereas in this work, we study streaming algorithms with much smaller memory requirement of only $\text{polylog}{(n)}$ bits. This stringent memory requirement is in the same spirit of classical streaming algorithms that instead of recovering a full solution to the problem---which can be prohibitively large with such small memory as is the case in our problem---, aimed to learn certain statistical properties of their inputs. In our case, this translates to determining the ``(correlation) clusterability'' of input graphs, or more precisely, estimating the cost of the optimal correlation clustering solution. 

As our main result, we present two novel algorithms that in only $\text{polylog}{(n)}$ space are able to estimate the optimal correlation clustering cost up to some constant multiplicative factor plus some extra additive error. One of the algorithms outputs a $3$-multiplicative approximation plus $o(n^2)$ additive approximation, and the other one improves the additive error further down at the cost of increasing the multiplicative factor to some large constant. We then present new lower bounds that justify this mix of both multiplicative and additive error approximation in our algorithms.

Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost
Sepehr Assadi
Vihan Shah'
Chen Wang
University of Waterloo
*Rutgers University
sepehr@assadi info vihan. wwwwsssathwwaerroooooooooo wc4970cs rutgers edu
Abstract
Correlation clustering is a fundamental optimization problem at the intersection machine learning and theoretical computer science. Motivated by applications big data processing, recent years have witnessed a flurry of results on this problem in the streaming model. In this model, the algorithm needs to process the input 7- vertex graph by making one or few passes over the stream of its edges and using limited memory, much smaller than the input size.
All previous work on streaming correlation clustering has focused on semi- streaming algorithms with ((n) memory, whereas in this work, we study streaming algorithms with much smaller memory requirements of only polylog(n) bits. This stringent memory requirement is in the same spirit of classical streaming algo- rithms that instead of recovering full solution the problem problem-wiihh can be prohibitively large with such small memory as is the case in our problem- aimed to learn certain statistical properties of their inputs. In our case, this translates determining the "(correlation) clusterability" of input graphs, or more precisely, estimating the cost of the optimal correlation clustering solution.
As our main result, we present two novel algorithms that in only polylog(n) space are able to estimate the optimal correlation clustering cost up multiplicative factor plus some extra additive error. One of the algorithms outputs 3- m-ultipplicatiee approximation plus o(n²) additive approximation, and the other one further reduces the additive error at the cost of increasing the multiplicative factor some large constant. We then present new lower bounds that justify the mix of both multiplicative and additive error approximations in our algorithms.
constant
Introduction
Correlation clustering is fundamental optimization problem the intersection of machine learning and theoretical computer science. This problem was introduced by the work of [BBC04 ! with motivation document clustering, follows:
have complete graph G (V, E) whose edges are labeled by either (+) or (-). and the objective, known as disagreement minimization, to cluster the vertices so that the number of (+) edges across clusters and (-) edges inside the same clusters are minimized. Correlation clustering has since found broad applications in areas such as document categorization (BBC04] webpage segmentation (CKP08), microscopy imaging [ZYH44) and community detection VGWI8 SDE 21]. to name few.
There is abundant body of literature studying polynomial time algorithms for correlation clustering. BBC04 CMSY15) showed that there exists apppxxppxooiiaaioonn algorithm in polynomial time and
37th Conference on Neural Information Processing Systems (NeurIPS 2023),
HHistorically, some forms of the problem were mentioned in earlier works like (W89

---

the problem is NP-hard and even AaX-hard. Furthermore, [ACNO5] gave simple (combinatorial) poly-time 3-approximation algorithm that is widely used in practice. Very recently, breakthrough re- sults by [CLN22 CAIIN23] achieved 1.73 approximation in polynomial time. In addition, efficient algorithms are also explored for several variants of this problem like the agreement maximization objective [BBC04 Swa04, [GW03). weighted graphs [Swa04, [GW003 EF03] fixed number of clusters [GG06], fair clustering [AEKM20) SZ22], and others.
In recent years, with the rapid development of the 'big data era', there has been growing interest in algorithms for correlation clustering under sublinear models. general, learning algorithms under sublinear models are able to output the answer without processing or storing the entire inpur. For instance, [BGK13 AW22] gave algorithms to (upproximately) learn the clustering sublinear time, and [CLM 21 BCMT22] designed algorithms in the Massively Parallel Computation (MPC) model. Another widely popular model of sublinear algorithms- the focus of our paper-is the graph streaming model. In this model, the edges of the input graph are given to the algorithm one by one in a stream and the memory of the algorithm is desired be substantially smaller than the input. Here, [ACG+ 15) designed a streaming algorithm with Ó(n) memory that achieves 3-approximation with Olog log(n)) passes - here, is the number of vertices of the graph and thus the input size is O(n²) bits. The number of passes of these algorithms were later improved to ((1) by [CLM+21] and single pass by (AW22), albeit with much larger, yet still constant, approximation factor. Very recently, [BCMT23 further improved the approximation ratio of single-pass streaming algorithms to a 5-approximation in polynomial time and (1 + aapproximation in exponential-tines
The aforementioned line of work in IACG CLM [AW22] BCMT233 focused the (()) memory regime, otherwise known as the semi-streaming memory. Allowing for (1()) memory in these algorithms is necessary given that even outputting the solution, namely, the clustering of the input labeled graph, requires this much memory. Yet, in many application, (()) memory can still be quite large, and the implementations can require significant resource. In such cases, it is highly desirable to determine the "clusterability" of the input graph before running the actual clustering algorithm. If even the optimal cost for the input is high, it implies the clustering cannot provide any meaningful outcome, and we should not waste resources on these instances. This type of "value estimation" problem is extensively studied in the streaming literature, see e.g. [KKS15] GT19 ACL 22 BOS22 DKPP22
for several examples in this context. This raises the following fundamental question:
How well can we estimate the optimal correlation clustering cost with polylog(n)-
space streaming algorithms?
Despite the vast body of work on streaming correlation clustering in general, this question has received almost no attention so far. Indeed, to the best of our knowledge, the only prior work here is that of (ACG+ 15] who proved that any (finite) purely multiplicative factor approximation of the cost is not possible in o(n) space. This result however does not rule out any additive error approximation (say, in the spirit of [BCK13] for local query algorithms).
We remedy this state of affairs in this paper. Our main algorithmic results show that one can obtain a 3-approximation plus o(n?) additive approximation to the cost of optimal correlation clustering in only polylog(n) space the additive approximation can be further reduced at the cost of increasing the multiplicative approximation to some large constant. We then complement these results with new streaming lower bounds that further justify the necessity of the additive errors in our algorithms. Throughout, we will present algorithms the manner of insertion-only streams. However, we shall note that our algorithms can be extended to dynamic streams wherein the edges of the graph can be both inserted and deleted during the stream.
Our Contributions
To state our results, we need the following notation. Let OPT be the optimal cost for correlation clus- tering. We say an algorithm achieves an (a, apprroxxiatto of OPT if it gives an a-multiplicative with B additive approximation, namely, outputs number ALG such that
OPT < ALG < a OPT + B.
Here, and throughout, we use Ö(-) hide polylog terms the parameters.

---

Our first main result is a single-pass streaming algorithm that achieves an (0(1), ōn²) approximation with high probability poly(log n. 1/6) space.
Result 1. There is single-pass streaming algorithm that outputs an (O(1), ón²) approximation of the optimal correlation clustering cost with high probability and uses ( space.
"Here, and throughout, with high probability means with probability at least 1 - 1/n.
The 8 --Dddeeene of our algorithm ensures that by setting 6 n -0.19 can reduce the additive error down to 1.8 o(n²) and still achieve an osn)-space algorithm. On the flip side however, the leading constant multiplicative factor is quite large in this algorithm as we will see shortly, the algorithm is built on the sparse-dense decomposition idea from [AW22], which inevitably incurs a (worst-case) constant of at least 10". Our next result addresses this drawback: present another algorithm that achieves (3, 8n²) aapproxmmaaio in expectation with polylogn space at the cost of an exponential dependence on 6 in the space.
Result 2. There is single-pass streaming algorithm that outputs a (3, òn "approximatioo of the optimal correlation clustering cost in expectation and uses 20 polylog(1) space.
Compared to the algorithm Result the algorithm Result 2 is more suitable for instances whose optimal correlation clustering costs are large (e.g. OPT = ?((n")) )). In such case, we can pick á to be a small constant, and achieve a (3 + -)mulitiplicative approximation with polylog(n) space.
Since both of our upper bounds contain the ôn² additive error, we would naturally wonder to what extent these additive terms are necessary. We present two new lower bounds that partially address this question, and show that the additive errors are necessary to large extent. Our first lower bound shows that if only additive error is allowed, there no polylog(n) polylog(n)-space -space streaming algorithm in single pass achieves additive error substantially better than Onn)).
Result 3. No single-pace pass streaming algorithm with polylog(n) space can output a (1, n² n===) approximation of the optimal correlation clustering cost with sufficiently large constant probability of success for some o(1).
can also be interpreted as the additive counterpart of the lower bounds in LACG 15], which focus instead on the purely multiplicative approximation. Since our upper bound allows both approximations, we further provide a second lower bound showing that a (nz) additive error is necessary even both multiplicative and additive errors are allowed.
Result 3
Result 4, No single-pass streaming algorithm with even of n space can output (1.19, ((n))
approximation of the optimal correlation clustering cost with sufficiently large constant probability of success.
We now discuss the applicable scenarios for our algorithms. test instances with low vs. high correlation clustering costs (e.g. o(r²) vs. ((n2)) it suffices to run our algorithm in Result I with 5 1/ log(n) which uses Ó(1) space. On the other hand, to separate instances that are 'partially clusterable' (e.g. optimal cost of n² /1000) vs. instances that are 'not clusterable at all' (e.g. optimal cost of n²2 /5), suffices to run our algorithm in Result with 8 = (()) a small constant which uses ((1) space. The only case our algorithms are not able to deal with is to separate multiple 'well-clusterable instances which does not seem that motivated in practice either.
To further validate our algorithms, we conduct experiments of our algorithms with the stochastic block model (SBM) extensively studied in the literature (e.g.. [HLL83 ABH16 ZT23 Abb17a]). For correlation clustering, we can use variate of the model that plants clusters with sizes ((n) and samples (+) edges between the vertices the same cluster with large probability and (-) edges with low probability, and vice versa. Our implementation on the simulations of graph streams from the Stochastic Block Model shows that our algorithms consistently obtain approximations within factor of 3 for the optimal clustering cost, while only storing 0.04% ~ 3.6% 3 total edges when the graphs is moderately large. Furthermore, our algorithms are able to distinguish instances that are "well-cluserable" vs. "badly-clusterable" using very small memory.
Experiments
0..0% fraction of edges obtained by implementing the algorithm of Result in two-pass manner
3

---

2 Preliminaries
We now introduce the notation and the problem definition. For standard technical tools, please see the supplementary material.
Notation.
We use G = EV U FE) to denote labeled complete graph arriving in stream. For any vertex e, we denote by (v) all vertices that have an (+) edge from v, and we let N+ = f UN++() (v). Similarly, we denote by N NN) all vertices that have an (-) edge from v, and we let N c = foJuN (v). We use N+ A (+)()) (resp. N (u) A N (v)) to denote the
disjoint neighborhoods of and v, i.e. (u) A (t)) For fixed set of vertices A S V, we further let E (w. A) be the set of (+) edges between v and vertices in A, and E (v, A) be the set of (-) edges between e and vertices A.
(N+(U)UNT (0)) \ (N)
We use G = (V, to denote the positive subgraph of G with all the (+) edges, and we define G- (V, F analogously. Note that since we work with labelled complete graph, the information of G edges can be uniquely inferred from the positive subgraph G As such, when we work
with G+ only, we call (+) edge (u, v) E E+ an edge in G++ Similarly, we call (-) edge (u, E E" an non-edge in G++ We may omit G+ when the context is clear.
For fixed cluster C on labeled complete graph G. we use cost (C) to denote the total cost of correlation clustering on G by C (we omit G since is obvious by the context). Furthermore, we slightly abuse the notation to reload cost(-) occasions: 1) For an induced subgraph
function of cost on subgraphs of G' in the following S G. we let cost C, H) be the cost of C induced by the edges whose both endpoints are in H; 2) For two vertex sets A UU B C V. we let cost(C, (A, B)) be the cost of C induced by the edges with exactly one endpoint in A and one endpoint in B.
Finally, for a single edge (u, v). we use the notation edge-cost( C, (u,,)) to denote the cost induced by single edge (u, v) for clustering C. We may write short-hand notation edge-cost( (u, v)) when the context is clear that C is used.
Problem Definition
We now give the formal description the problem.
Problem 1 (Correlation Clustering Value Estimation). Given labeled complete graph G = (V, E-U E and a clustering C that partitions V into disjoint set of vertices C.. Ck, the cost of disagreement minimization correlation clustering on C is defined as
cost(C)= : {(., o) E E j s.t. u E C,, E C, + ((u,)) s.t. u.
Let OPT be the minimum cost over all possible clusterings. The Correlation Clustering Value Estimation problem asks for number ALG such that OPT < ALG < ((OPT) for some function f()) 2 x. If f(OPT) a OPT + 3 - n² for and B, we say that ALG is (a, B) approxxxxniiooonn of the value of correlation clustering this scenario.
We study algorithms for correlation clustering value estimation under the graph streaming model, where edges arrive after another in stream with the labels. We give more formal definition of the streaming model (and the more general dynamic streaming model) in the supplementary material.
3 An Algorithm based on Sparse-dense Decomposition
In this section, we present our first streaming algorithm that achieves (O(1), )pp))apppoximation for testing the value of correlation clustering in O(polylog(n) (onolylog(n//ool(((() /olly())) space, as long as > 1/polylog(n). We utilize the idea in [AW22] to test (O(1), 8n >appprxximate value of the sparse- dense decomposition-
correlation clustering cost, which in turn an ((1) approximation of the optimal cost. Our algorithm uses memory of Oppolylog (o/pooo(6)) bits, which is efficient for large-scale inputs. More formally, the guarantee our algorithm is as follows.
Theorem 1. There a (dynamic) streaming algorithm that with high probability gives a (O(1), approximation for the correlation clustering value and take space O
log (x))
words.
8
On a high level, our algorithm for Theorem uses the idea to approximate the value of optimal correlation clustering with sparse-dense decomposition (see supplementary material). It is shown in

---

that once we can find such a decomposition on G*, we can achieve an [[1-aappoxiimation by simply putting every sparse vertex into a singleton cluster and gathering each almost-clique K; in a separate cluster. Therefore, an approximation of the number of the aforementioned edges in a fixed decomposition will result in a good estimation of the cost.
AW22
However, since the sparse-dense decomposition is not unique, it is unclear how to estimate the edges for a fixed decomposition. On the other hand, an algorithm with polylog(n) space is necessarily oblivious of the decomposition since it takes (n) bits to write it down. To overcome the problem, we forgo the strict notion of the sparse-dense decomposition, and utilize the notion of E-sparse edges and e-dense non-edges (of G+) instead. We now formally define these notions as follows.
Definition 1. Fix an arbitrary graph G = (V, E) (which is not necessarily labeled and complete) and vertex pair (u, v) E G, we say
1. (u, u) is an e-sparse edge (resp. non-edge) if (u, v) E E (resp. (u, v) @ E) and (N(v) AN 8 . max max{deg(M) (deg(u), deg(v)).
2. (u, v) is an e-dense edge (resp. non-edge) if (u, v) E E (resp. (u, & E) and (N(e) (N))
e (de((e deg(v)).
Note that the definitions of the e-sparse and e-dense edges/non-edges are generic and not restricted to the labeled complete graph (or even the correlation clustering application). Similarly, the sketching tools we design in this section are also generic: we will use them in the context of correlation clustering later. We now prove the existence of the following tools.
Lemma 3.1. There exists dynamic streaming algorithm Tool-spr with parameters e, 6 that given any graph G = (V, E) in a stream and a pair of vertices u, v E V, satisfying the promise deg [u) 2 on and deg (v) 2 8n, with high probability outpus 'Yes" if (u, U) is at least E-sparse and "No" if
(u, v) is not 5 -spaass using ()) words of space.
Lemma 3.2. There exists dynamic streaming algorithm Tool-dns with parameters e, 5 that given any graph G = (V, E) in a stream and a pair of vertices u, v E V, satisfying the promise deg [u) 2 ön and deg* + (v) 2 8n, with high probubility outputs 'Yes" if (u, v) is at most E-dense and "No" if (u, 1)) is not &e-dense using (1)/=2)) words of space.
We defer the proofs off Lemmas 3. and 3.2 to the supplementary material, and use them as blackboxes in the rest of the paper. We now discuss how to use the e-sparse edges and e-dense non-edges (defined in Definition 1 in G+ to estimate the correlation clustering cost. In what follows, we use E epsrre to denote the set of E-sparse (positive) edges, and E de to denote the set of E-dense non-edges. Furthermore, for each vertex v. we use F Feedemee denote the set of e-dense non-edges incident on V. We let mi-sumee == E+ sparse denote the number of e-sparse edges, ye == 2 denote denote the number of e-dense
the number of s-dense non-edges and let m me-dense,e non-edges incident on v. Finally, we define i e-dense as follows.
F dense,,
Definition 2. For each vertex v define m e-demse, = min (m dense, deg dw)) Furthermore, let m. m--eee := ΣvEv m de-nsse
The intuition behind c is to count the non-edges (of G+) in Ed for at most deg (v) times. Our estimator for e-dense non-edges will estimate A z-demse instead of m for the following reason: it suffices estimate de since the number of non-edges inside each almost-clique at most du): on the other hand, if we estimate all E-dense non-edges, there could be a very large overhead since the non-edges between almost-cliques are also counted. We note that if m--deens.s m densse. o for all v E V then mi--sene twice mr-denso (since we are double counting edges). But this is 2-approximation in the worst case, and we do this to make calculations easier.
We prove the following lemmas that establish the connections between the aforementioned sets of edges and the edges from the sparse-dense decomposition. Due to space limits, we directly present the properties of our estimators, and defer the proof to the supplementary material.
Lemma 3.3. Suppose G = EV, is any labeled graph and V = Vepare LI K1 Ll... K₂ is an E-sparse-dense decomposition of G+ for 0 < S 1/360 and no < 1/20. Let CSDD be the cost of
5

---

correlation clustering when the clusters are the almost cliques and sparse vertices are in singleton 2 CsDD 2 OPT.
clusters. Then we have ho-E Mape -spurse + m² c-sparse Me 4c dense
We upper bound the cost of m mi-qurse and M e-densee by a function of OPT using charging argument.
Lemma 3.4. Suppose = (V, E) any labeled graph and OPT be the optimal correlation clustering cost, and let S 32 and B S 25 then m Spare
Be OPT and Be-dense S 8 OPT.
By Lemmas 3.3 and 3.4 if we are able to exactly recover mprre and d then would get an 0(1) approximation of OPT. Such task seems difficult, however, using Lemmas 3.1 and 3.2
design our tools for estimating sprse and me-eess with additive error.
Lemma 3.5. There exists a dynamic streaming algorithm with parameters e that given any graph G= (V,E) E) in a stream returns a value Zsp that is at least mi-uparse and at most m 2/8-sporse + ôn?
with high probability and uses Ologn/ n/=²0²) words of space.
Lemma 3.6. There exists a dynamic streaming algorithm with parameters e, 5 that given any graph G= GV, E) in a stream returns a value Zden that is at least g-dnss and at most in ge-dese ôn?
with high probability and uses Olog" n1/=20)) words of space.
Finalizing the proof sketch of Theorem 1
We are given a parameter 5 as input and we want the
additive error to be at most 8n. We fix 1/360, 77u 1/20 and 8' = 6 (2
2 2
moc
Run the algorithm in Lemma 3.5 with parameters and 8', and let the output be 2e Also, the algorithm in Lemma 3.5 with parameters T and 6', and let the output be Z Run the algorithm in with parameters 4e and 8', and let the output be Zden.
Lemma 3.6
Lemmas 3.3 to 3.6 imply that the cost Zec we output satisfies:
OPT < Zoo Zep (2/108) 7 7 S 50(1) OPT + dnn.
The space taken is (llog n2/5)) for both copies of Lemma 3.5 and Ollog² ((00g"n/0²) for Lemma 3.6 giving a total space of Olog" n/6²) words. This proves Theorem
An Algorithm based on Pivot
In this section, we give our second streaming algorithm that is (3 + 7, 6n²) -approxxmiiiion for the correlation clustering value for any choice of 5 and y < 1/2. The algorithm works in (ppolylgg(n)) space long as 8 Qi log logio) )- Consider the following formal statement:
Theorem 2. There a (dynamic) streaming algorithm that with high probability gives a (3+7, "-²))
approximation for the correlation clustering value and takes space O (27 22/00 log n words.
Our algorithm in Theorem 2 is inspired by the Local Cluster algorithm from [GKI3]. The Local Cluster algorithm samples 1/6 random vertices set U and computes the greedy maximal in- dependent set (MIS) M of U to get the cluster centers P1 P1.P2..... Pt. The clusters generated then are N+1 [p:] - - N and all the remaining vertices (called unclustered vertices) are clustered in their own singleton cluster. [BGK13] proved that the expected cost of this clustering is at most 3 OPT + n More formally, they showed the following:
Proposition 4.1 [GK13)). The expected cost of Local Cluster is at most 3- OPT + 5
To simulate the Local Cluster algorithm in a streaming manner, while forming cluster we need to know which of its neighbors are already clustered in previous clusters which requires new sketching tools (on G*) that are different from the ones we used in SSection 3 These tools estimate the number of non-edges within or the number of edges going out of the neighborhood of vertex (u) outside of the (+) neighborhood of a known set of vertices (S). other words, fix a graph G = (V, E), a vertex and a set S, we want to estimate the number of non-edges within or the number of edges going out of [[u] - N[S]. We again use the generic form to present the sketching tools and do not specify (+) edges. The formal definitions can be given follows.

---

Definition 3. A non-edge (x, v) is within N(u] [[S] iff: i) 2 & N[S] and it) & [[S] and (ii)
E Muu and y Nlu).
Definition 4. An edge (z, y) is going out of [[u] [ iff $ N| and id) & N[S] and vi)) Muj or y [I] but not both.
Definition 5. An edge (r,y) y) is unclustered w.r.t. 5 iff a & S[S] and ii) E N(S).
We also define Mmn uu, S) as the number of non-edges within [u] N| (u, S) as the number of edges going out of Nuu] _NS)). and (5) the number of unclustered edges w.r.t. S. We write Mae, me, and m. when u and S are clear from context.
Exactly recovering ma: mu and m. difficult, we have the following lemma about estimating the number of non-edges within Nuu] - N(S), the edges going out M(u] -iS)), and the unclustered edges with respect to S:
Lemma 4.2. There exist streaming algorithms called NE-Tool, E-Tool, and U-Tool that given and S before the stream, respectively compute with high probability i). the number of non-edges within; it). the number of edges going out of N Nul - [S]; and iti). the number of edges with unclustered w.r.t. S with overestimation of at most ôné and take space O(1/8²) words.
Using the tools have built far, present (3, 83,) approximation algorithm in expectation.
Algorithm 1. Simulation of the Local Cluster algorithm
Input: G = (V, E+ J E
) in (dynamic) stream
Output: (3, -aprrxxiaitio the correlation clustering value expectation
Pre-Processing:
1. Sample set U of 1/6 random vertices
2. Let ı be random permutation of the vertices in U
During the Stream:
1. Store (+) all edges between vertices of U
2. For all u E U and S C U compute E- U-Toll(S) with parameter 62/6 using the G+ subgraph.
Post-Processing:
1. Compute the greedy MIS M = P1.P........ of U in the order of (using edges stored between vertices of U).
2. So = 0. 2=0
3. For to
? 7 NE- + (E St-1).
SS = S (p.)
4. Output 7 = 7 + U-Tool(M)
Algorithm estimates mu, Mhe and me with at most 8nz additive error. We now show that with the exact values of ma, mue and me, we get the exact clustering value the Local Cluster algorithm.
Claim 4.3. The clustering value of Local Cluster is equal to m. + E; mnelps. S;- 1) +m S;-1).
Combining Lemma 4.2 and Claim 4.3 gives the following performance guarantees for Algorithm
Lemma 4.4. The output of Algorithm at least OPT with high probability and at most
3OPT dn in expectation.
Proof. Using Claim 4.3 we know that if the tools worked with no error, Algorithm I would give the exact clustering cost of Local Cluster. Also, we know that the tools do not underestimate and overestimate by n²n2 2/ with high probability (Lemma 4.2). We first note that at least OPT because of the above conditioning and the fact that the clustering cost of Local Cluster is at least OPT. Using Proposition 4.1 we know that the expected cost of the clustering when choosing random pivots is at most 3OPT + n Therefore, the clustering cost of Algorithm is between OPT and 3OPT n plus the overestimate.
7

---

We now calculate the overestimate. We use parameter 8² /6 for the tools thus the additive error in each tool is at most d2n2 /6. There are 1/6 pivots implying total additive error of at most 6n2/3 over all the copies of NE-Tool and E-ool.. U-Tool has an error of at most 8²n2² /6 implying that the overall error at most 8n² /2 + 5n /3 + n² /6 I òn² giving a (3, 6n²) approximation expectation.
We note that we condition on the high probability events for all copies of the tools and union bound over the failure probabilities. Thus, for the overall failure probability to be small we need 21/6 < poly(n). This requirement is trivially statisfied by the fact that 2 is the space bound Lemma 4.5). and the space bound for any streaming algorithm is at most (n²))
We now show the space bound of Algorithm
Lemma 4.5. The space of Algorithmm 1 is O 2 Jogn
words.
Proof. Each copy of the tools with parameter 82 takes Ollog words of space, and we compute the tools for all v U and _ U. Thus, the space used O(21/6 log n/8") words. Storing edges between vertices in U takes space at most 1/0² words which is lower order term. L
and 4.5 together give us a (3, dn²) approximation in expectation using O (24/ 11/4-Jogmm
Lemmas 4.4
60 log times in parallel and let Zmin be the minimum cost over all iterations. Zmin is (3 + 7, on? approximation with high probability.
space. We now prove Theorem 2 We run Algorithm
Claim 4.6. OPT < Zmin I (3 + 73+ + snn with high probability.
Thus, we get (3 + 7, ddn²) (ain")-approol approximation with high probability. Each parallel repetition of the words of space. Repeating O log log") times and re-scaling by factor 27/86 22/0061og"') 12
algorithm takes O no
logn
y
of _ gives a total space bound of O
words. This completes the proof of Theorem
7-80
5 A Lower Bound for O(n² Additive error
In this section, we show that if we only allow additive error, any streaming algorithm with poly- logarithm memory cannot cross an error barrier of M(n²²=) for some = o(1). Here, and throughout, we will refer this lower bound as the almost-quadrant iatd--uaariicccc lower bound. The lower bound is weaker than the linear lower bound of Sectionn 6 terms of the multiplicative factor since it only works for = 1. However, is much stronger the additive sense: the upper bounds obtained by our algorithms are Onn²), and the almost-quadratic lower bound matches this term up to Onn") factor this provides a strong justification of the additive error in our algorithms.
The formal statement of the almost-quadratic lower bound is as follows.
Theorem 3.
There exists constant C, such that any single-pass streaming algorithm that estimates the optimal value OPT of correlation clustering by a C-n purely additive error (i.e. an estimated value that is at most (OPT + C --=²=)) with probability least 09 has use memory of D (nf) bits, even on labeled complete graphs.
100
Note that Theorem 3 does not require the stream to be dynamic, which is in contrast to our upper bound results that work for dynamic streams. We obtain the almost-quadratic lower bound by a new reduction from the INDEX problem. On the high level, the instance we construct "hides' an 2(n===) gap between the yes and no cases inside case-invariant Ω (n²) cost. The reduction can be viewed as a more involved variant of the space lower bound for the exact correlation clustering in a very recent work [AAD*2 23). In nutshell, we modify their construction to "boost' the gap between yes and no cases, and apply new trick to separate the values of clustering. Due to space limits, we defer the proof of Theorem 3 to the supplementary material.
8

---

6 A Lower Bound for (n)) Additive error
In this section, we show that any dynamic streaming algorithm that gets a (c, approoxaiiii for e < 1.2 and (n) additive error needs 92 ( (vn) bits of space. Here, and throughout, we will call this lower bound the linear lower bound. Formally, we have:
Theorem 4. Let c E [1, }) and E (0, g - c). Any single-pass streaming algorithm that estimates the optimal value OPT of correlation clustering by a (c, En aapprxximaaionn (i.e. an estimated value that is at most (c- OPT + E - n)) with probability at least go has to use memory of (VT)) bits, even on labeled (complete) graphs.
100
Similar to the case in Theorem Theorem 4fdoes not require the stream to be dynamic. Comparing with the almost-quaen quadratic lower bound we show in [Section 5] the lower bound in Theorem is weaker in the additive sense. However, it allows the multiplicative approximation of the algorithm to be 1, while the lower bound in /Section JJonly rules out algorithms with purely additive errors.
Our lower bound uses the celebrated machinery from Boolean Hidden Hypermatching (BHH) and Gap Cycle Counting (GCC) pioneered by [УII]. The Gap Cycle Counting (GCC) lower bound states that for any algorithm to distinguish whether a graph consists of cycles with length 2t or cycles with length 4/ for some 2 2, a memory of Ω (n²-+) bits is necessary. On the high level, our plan is to show that for graphs similar to the ones prescribed in the GCC problem, the values of correlation clustering are different by an additive gap of On)). Therefore, by reduction argument, any algorithm that breaks this barrier of additive gap requires w (polylog(n)) memory.
Due to space limits, we defer the lower bound construction the supplementary material.
7 Experiments
We describe in this section the experiments of algorithms on the Stochastic Block Model and the Erdos-Reny random graphs. These experiments show that for a very natural family of graphs, our algorithms can achieve very competitive performance on the estimated cost values, and the performances are often much better than the worst-case theoretical analysis. Furthermore, our algorithms are capable of separating "well-clusterable" vs. "badly-clusterable" instances.
Experiment Settings Limited by space, we sketch the key settings of our experiment, and defer the full discussion to the full version in the supplementary material. As we have discussed, we perform our experiments on the data generated from the well-studied Stochastic Block Model (SBM) that plants ground-truth clusters with sizes M(2). samples (+) edge between vertex pairs (I,, xz) in the same planted cluster with probability p > 0.5, and samples (+) edges between vertex pairs (x,, in different clusters with probability 1 p. The SBM captures lot of real-world scenarios, including social networks [HLL83), community detection [Abb]7b], graph clustering [W19], and Bioinformatics MGC21 to name a few.
We test SBM instances that are reasonably "'luuserble", i.e., we set = 0.8 with vertices n = 500, 1000, and n 2000. Furthermore, we compare the costs estimated by algorithms for the SBM and the Redos-Renyi random graphs G(n, p) with 0.5. In this regime, the Erdos-Renyl graph does not appear have any clustering property, and the cost high. Under the n 1000 setting, we tested whether our algorithms can distinguish the costs between "good" (SBM with p= 0.95) and "bad" (Erdos-Renyl with p = 0.5) instances a property that can be extremely useful in practice.
We implement our algorithms based on our descriptions in Section 3 and [Section 4 with some relaxation of parameters. Notably, for the pivot-based algorithm, we slightly relax the requirement to allow 2-pass over the stream; as such, we can use the first pass to perform greedy MIS on the sampled vertex set, so we do not have to pay the 201155) factor in the space.
We evaluate the performances mainly based on two metrics: the multiplicative factor of the cost estimation (which we call the "competitive ratio")) and the fraction of the edges used. To overcome the possible effects of random seed, we fix our random seed from 0 to 14, and run 15 experiments We include the error bars and the curves of the competitive ratios and fraction of the edges. For the experiment to distinguish SBM and Erdos- graphs, we simply plot the two types of costs w.r.t. experiment runs, and give the distributions of the costs. All the experiments were conducted on two macbooks and public Colab clusters.

---

Experimental Results We first show that our algorithms are insensitive to the choice of parameters this property is evident by the figures we used the full version in the supplementary material. As such, we focus on the settings with 0.01 for the SDD-based algorithm and á = 0.1 for the pivot-based algorithm for the rest of this section.
Due to the space limit, we only discuss our algorithm based on sparse dense decomposition (SDD). The left plots in Figure I give the plots of the cost estimation for the SDD-based algorithm on 2000. The figures show that the approximation factor for this algorithm is roughly between 1 and 2, our algorithm consistently uses less than 4% of the edges in the graph.
The results for our SDD-base algorithm to distinguish between SBM instances with p = 0.95 and ER instances with p 0.5 with the SDD-bat DDD-based algorithm is shown in the right two plots of Figure From the figure, can be observed that the the SDD-based algorithm outputs drastically different clustering costs of the SBM instances left plot that the supports the costs are disjoint. As such, by simple linear threshold, our SDD algorithm is able to perfectly distinguish between both types of instances while using less than 10% of the edges (n 1000 case).
the Erdos Erdos-Renyl instances. We observe from the
800000
1.8-
700000
177
000000
0.034
500000
0.032
1.3-
100000
0.028
5D0wlly Exilmetion
Revl Cost
10 11
38.15
the
MuBifactor Exinttion Dost
200000
12
113000
V3200
123
.2.5
Figure 1: The performance of the SDD-based algorithm for cost estimation and instance clusterability distinguishing. Top 3 plots: the cost estimation of the SDD-based algorithm over 15 runs; Bottom plots: the costs of SBM and ER graphs estimated by the SDD-based algorithm over 15 runs.
Acknowledgments and Disclosure of Funding
Research supported in part by the Alfred P. Sloan Research Fellowship. Faculty of Mathematics Research Chair Award from University Waterloo, an NSF CAREER Grant CCF-2047061, gift from Google Research, and Rutgers Research Council Fulcrum Award.
10

---

References
[AAD+23] Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng. Jie Gao, and Chen Wang. Eval- uating stability in massive social networks: Efficient streaming algorithms for structural balance. In Nicole Megow and Adam D. Smith, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 1 11-13, 2023, Atlanta, Georgia, USA, volume 275 of LIPles, pages 58: 18:1-3, Schloss Dagstuhl Leibniz-Zentruu für Informatik, 2023.
[Abb17a] Emmanuel Abbe. Community detection and stochastic block models: Recent develop- ments. J. Mach. Learn. Res., 18:177:1-177:66, 2017.
[Abb17b] Emmanuel Abbe. Community detection and stochastic block models: recent develop- ments. The Journal of Machine Learning Research, 18(1 (1:4)6446665555 2017.
[ABH16] Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory, 62(1))471-487, 2016.
IACG 15] Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation clustering in data streams. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML. 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 2237 JMLR org, 2015.
[2] Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, and Chen Wang. Hierarchical clustering in graph streams: Single-pass algorithms and space lower bounds. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 4643 4702. PMLR, 2022.
[ACN05] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent infor- mation: ranking and clustering. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 684-693. ACM, 2005.
[AEKM20] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Fair correlation clustering. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 4195 4205. PMLR, 2020.
[AW22] Sepehr Assadi and Chen Wang. Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. In Mark Braverman, editor, 13th Innova- tions in Theoretical Computer Science Conference, ITCS 2022, January 31 February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 10: 1-1:20.. Schloss Dagstuhl Leibniz--eenrru für Informatik, 2022.
[BBC04] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Mach. Learn., 56(1-3):89-11 113, 2004.
[BCMT22] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Almost 3- approximate correlation clustering in constant rounds. In 63rd IEEE Annual Symposiam on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pages 720-731. IEEE, 2022.
[BCMT23] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li- Yang Tan. Single-pass stream- ing algorithms for correlation clustering. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithmss, SODA 2023 (to appear), 2023.
[BGK13] Francesco Bonchi, David Garcfa-Soriano, and Konstantin Kutzkov. Local correlation clustering. CoRR, abs//331..500000 2013.

---

[BOS22] Tomer Berg, Or Ordentlich, and Ofer Shayevitz. On the memory complexity of uniformity testing. Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 3506-3523, PMLR, 2022.
[CALLN23] Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling corre- lated rounding error via preclustering: A 1.73-approximation for correlation clustering, 2023.
[CGW03] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with quali- tative information. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 524-533 IEEE Computer Society, 2003.
[CKPO8] Deepayan Chakrabarti, Ravi Kumar, and Kunal Punera. A theph-the approach to webpage segmentation. In Jinpeng Huai. Robin Chen, Hsiao-Wuee Hon, Yunhao Liu, Wei- Ying Ma, Andrew Tomkins, and Xiaodong Zhang, editors, Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008, pages 377-386. ACM, 2008
[CLM+21] Vincent Cohen-Addad Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi- Nikos Parotsidis, and Jakuh Tarnawski. Correlation clustering in constant many parallel rounds. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2069-2078. PMLR, 2021.
[CLN22] Vincent Addan, Euiwoong Lee, and Alantha Newman. Correlation clustering with sherali-adams. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pages 65 661. IEEE, 2022.
[CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 219-228, ACM, 2015.
[DKPP22] Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, and Thanasis Pittas. Streaming algorithms for high-dimensional robust statistics. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 5061-5117. PMLR, 2022.
[EF03]
Dotan Emanuel and Amos Fiat. Correlation clustering minimizing disagreements on arbitrary weighted graphs. In Giuseppe Di Battista and Uri Zwick, editors, Algorithmms ESA 2003. 11th Annual European Symposium, Budapest, Hungary, September 16-19 19,1,, 2003, Proceedings, volume 2832 of Lecture Notes in Computer Science, pages 208 -20.. Springer, 2003.
[GG06] Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. Theory Comput., 2(13):249-266 266, 2006.
[GT19] Venkatesan Guruswami and Runzhou Tao. Streaming hardness of unique games. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology Cambridge, MA, USA, volume 145 of I.Plcss, pages 5:1-5:12. Schloss Dagstuhl- Leibniz-7entrum für Informatik, 2019.
[GW89] Martin Grötschel and Yoshiko Wakabayashi. A cutting plane algorithm for clustering problem. Math. Program., 45(1-3):59-96, 1989.
12

---

[HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109- 1983.
[KKS15] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In Piotr Indyk, editor, Proceedings of the Twenty-Sixih Annual ACM-AICMAII SIAM Symposium on Discrete Algorithms, SODA 2015. San Diego, CA, USA, January 4-6, 2015, pages 1663-282. SIAM, 2015.
[LW19] Clement Lee and Darren J Wilkinson. A review of stochastic block models and extensions for graph clustering. Applied Network Science, 4(1):1-50, 2019.
[MGC2I] Leonardo Morelli, Valentina Giansanti, and Davide Cittaro. Nested stochastic block models applied the analysis of single cell data. BMC bioinformatics, 22(1):1-19, 2021.
[SDE+21] Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Lacki, and Vahab S. Mirrokni. Scalable community detection via parallel correlation clustering. Proc. VLDB Endow., (((1)):2305-2113 2021.
[Swa04] Chaitanya Swamy. Correlation clustering: maximizing agreements via semidefinite programming. In Ian Munro, editor, Proceedings of the Fiffeenth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 526-527. SIAM, 2004.
[S722] Roy Schwartz and Roded 7ats. Fair correlation clustering in general graphs. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANOMM 2022, September 19-21, 2022, University of Illinois, Terbana-Chappaige USA (Virtual Conference), volume 245 of LIPlcs, pages 37:1-37:19, Schloss Dagstuhl- Leibniz- Zentrum für Informatik, 2022.
[VGW18] Nate Veldt, David Gleich, and Anthony Wirth. A correlation clustering framework for community detection. In Pierre-Antoine Champin, Fabien Gandon, Mounia Lalmas, and Panagiotis G. Ipeirotis, editors, Proceedings of the 2018 World Wide Web Conference World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pages 439-448. ACM, 2018
[VY11] Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. In Dana Randall, editor, Proceedings of the Twenty- Second Annual ACM-SIAM Symposium on Discrete Algorithmss SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 11-25. SIAM, 2011.
[TT23] Qiaosheng Eric Zhang and Vincent Y. F. Tan. Exact recovery in the general hypergraph stochastic block model. IEEE Trans. Inf. Theory, 69(1) 2023.
[ZYH14] Chong Zhang, Julian Yarkony, and Fred A. Hamprecht. Cell detection and segmen- tation using correlation clustering. Polina Golland, Nobuhiko Hata, Christian Barillot, Joachim Hornegger, and Robert D. Howe, editors, Medical Image Computing and Computer-Assee Assisted Intervention MICCAI 2014 17th International Conference, Boston, MA, USA September 14-18, 2014, Proceedings, Part I, volume 8673 of Lecture Notes in Computer Science, pages 9-16. Springer, 2014.
13


Reviews:
[{"review_id": "J4X2K9xnl9", "reviewer": "Reviewer_YPdG", "summary": "This paper studies the correlation clustering problem in the streaming setting. Unlike previous work they consider algorithms with space much smaller than the number of vertices and only find the cost of the optimal clustering, not the clustering itself. They define an (alpha, beta) approximation to be an additive error of alpha*OPT + beta. Their \"result 1\" and \"result 2\" are for any constant delta > 0 streaming algorithms with approximations of (O(1), delta n^2) and (3, delta n^2) respectively and space O~(1/delta^5) and O~(2^O(1/delta)) respectively. Their \"result 3\" and \"result 4\" are impossibility results. They also give some experimental results.\n", "questions": "Any comments on the weaknesses mentioned in that section?\n\n=== Misc comments not really questions but I'm not sure where else to put them =====\n\nAbstract: replace \"improves the additive error further down\" with \"further reduces the additive error\"\n\nCorrelation clustering appeared (but by a different name) in a 1989 paper by GROTSCHEL and WAKABAYASI titled \"A CUTTING PLANE ALGORITHM FOR A CLUSTERING PROBLEM\"\n(https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.468.4826&rep=rep1&type=pdf). I'm guessing there are probably even earlier papers somewhere. So the 2004 paper you cite as introducing the correlation clustering problem actually reintroduced it.\n\ncost(C) is defined twice, first in section 2.1 and then in section 2.2. Also the definition in section 2.1 is incomplete since it doesn't say whether the cost is the number of disagreements or the number of agreements or something else, though the word \"cost\" does hint that it's probably the number of disagreements.\n\nUsing the shape of the brackets to distinguish N^-[] from N^-() and N^+[] from N^+() is a bit weird since when bracket shape is used to distinguish notations the two notations are usually totally unrelated, not variations of the same thing. I would prefer a more traditional notation, e.g. overbar on the N for the version that includes the vertex itself.\n", "limitations": "See weaknesses section for some limitations. No societal impact issues.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 1, "strengths": "The paper is well written.\n\nThe impossibility results (\"result 3\" and \"result 4\") look interesting, though I haven't had time to read the proofs.", "weaknesses": "The first and biggest weakness of this paper is the \"result 1\" and \"result 2\" in the intro can straightforwardly be beaten using known techniques. In particular one can get a (1, delta n^2) approximation in poly(delta) space and time poly(n) + 2^poly(1/delta). To do this simply take a random sample of k = Theta~(1/delta^4) vertices, solve correlation clustering on the sample with an algorithm with delta k^2 additive error, and then scale up the cost by a factor of (n/k)^2. (If one-sided error is desired as in this paper's definitions you also need to subtract roughly delta n^2 from the estimate.) The key idea is the fact that to get delta n^2 additive error it suffices to consider clusterings with O(1/delta) clusters, which makes correlation clustering an instance of the well-studied MAX-CSP family. A sample size of k being enough to approximate the value of MAX CSPs to an additive error first appeared in a paper by Arora, Frieze, K and Karpinski (AFKK) in the 1990s IIRC. (I'll try to track down the exact citation and some more details in a comment to be added this weekend.) For the approximation algorithm one can either use that general-purpose AFKK algorithm or one of the published PTASs for correlation clustering with a constant number of clusters, e.g. [8] in https://en.wikipedia.org/w/index.php?title=Correlation_clustering&oldid=1147372897 (which includes this problem despite the title not mentioning it). The algorithms I mentioned aren't very practical so for experiments you could use applying a branch and bound solver such as SciP, CPLEX, or Gurobi to the correlation clustering integer program for the sample only, which should scale to a sample size of something like 50 vertices, or use any algorithm for correlation clustering (but with worse performance guarantee). To do the random sampling in a streaming fashion keep track of the k vertices with the smallest hashes seen so far and any edges between them.\n\nAnother big weakness of this paper is that correlation clustering instances large enough to not fit on one machine and hence be interesting for streaming algorithms are likely to be sparse, i.e. have o(delta n^2) positive edges. In practice one can therefore probably do better than their result 1 or result 2 (or the algorithm I sketched above) by simply returning the number of positive weight edges, which is a trivial upper-bound on OPT (it's the cost of the all-singletons clustering). I can't rule out the existence of applications where this sort of guarantee would be useful, I'm just not aware of any.\n\nAnother weakness of this paper is streaming models are only useful for a somewhat narrow circumstance: instances are small enough that you have enough time to pass all the data through one machine but large enough that you don't have space to store the full data on one machine. Many streaming results also work in a distributed model such as MPC, which is more practically relevant in my experience, but the authors don't discuss distributed models so I can't tell without reading everything in detail.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review and the critical new idea. Please find our responses below. \n\n**Point 1: The suggested $(1, \\delta n^2)$-approximation algorithm.** Thank you for raising this observation. If we understand it correctly, the key idea of your suggestion is to reduce the min-disagreement with $\\delta \\cdot n^2$ additive error to max-agreement correlation clustering with $\\delta \\cdot n^2$ additive error. Also, it is okay to work with just $1/\\delta$ clusters when the additive error is $\\delta n^2$. Finally, use some sparsification results to solve the $(1/\\delta)$-cluster version of CSP on a small sample. This is a very nice approach that we did not consider previously, and it does indeed seem to us also that an approach along these lines might indeed be plausible. \n\nThat being said, we did not find this approach trivial/straightforward, nor could we even be fully convinced at this stage yet that it works without complete proof. If this algorithm was known previously, we have missed it and would appreciate a reference to this result. However, we would like to point out that approaches like this have been tried for (max-agreement) correlation clustering, say paper ``Sublinear Algorithms for MAXCUT and Correlation Clustering’’ by Bhaskara et al. [ICALP’18], and they appear to require substantially more work to address the subtle issues raising in this context, than being a straightforward application of known tools (these tools themselves are also not exactly simple to begin with). In addition, as your review also points out, such an algorithm would require using highly sophisticated “post-processing” algorithms that make the runtime of the algorithm quite high (we suspect at the very least $n^{1/\\delta}$-type bound), and the implementation in practice infeasible (although from a purely theoretical result, such a bound fully complements our lower bounds and is obviously of its own interest surely). This is in contrast to our approach which offers practical streaming algorithms with quite straightforward implementations. Thus, we do not see your suggestion as rendering our results trivial and we stand by the contribution of our paper as providing the first truly-sublinear space streaming algorithms for this fundamental problem. \n\nWe will be happy to try out the suggested algorithm idea in detail and write a proof in a future version; alternatively, we can also leave the idea since it is not originally from us. We will be happy to hear your opinion on this front.\n\n**Point 2: Concerns about the model.** We were actually rather surprised by the comments about the perceived impracticality of streaming algorithms in general. While we do understand that certain companies, say, Google, may indeed have a strong preference for MapReduce-style computation frameworks, this is certainly not across the board and is quite application-oriented, as is evidenced by the vast amount of work on various streaming platforms. Indeed, streaming algorithms are not designed for processing 20-TB size graphs, but they can target 1-TB size graphs quite easily by making one sequential pass over them very quickly and using RAM for the much smaller memory needed for the algorithm, which gives tremendous speed-up compared to directly running the algorithm on a 1-TB size graph. We refer the reviewer to the papers ''GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams’’ by Tench et al. and ''Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems’’ by Besta et al. for instances. \n\nThat being said, our results **immediately** extend to these other models as well in the same standard way that prior streaming algorithms do.  Since both of our algorithms are based on *linear sketches*, they naturally imply fully scalable MPC algorithms with constant number of rounds – we only need an MPC with $O(n^{c}\\cdot \\text{polylog} \\ {n/\\delta})$ space per machine and the number of round is $O(1/c)$. The algorithm has to simply run the linear sketch locally, and broadcast with the standard communication tree, and correctness is guaranteed by the properties of linear sketches. In fact, it appears both of our algorithms can be executed in the stronger PRAM model with $O(1)$ depth and $\\text{polylog}\\ {n}$ work – we can check the details on whether it works in future versions. \n\n**Point 3: Concerns about the correlation clustering instances being sparse.** We believe there are many streaming applications where large graphs have $\\Theta(n^2)$ edges. One toy example is the stochastic block model (SBM) we studied in the experiment section, in which the instances have $\\Omega(n^2)$ the intra-block edges alone (which do not even contribute to the cost). The SBM has been studied extensively in the literature, and it captures a wide range of social network applications, e.g., community detection. \n\nThe SBM is also a prime example to show that simply returning the number of edges gives a bad approximation for the correlation clustering cost. Note when $p$ is large in the SBM, most edges do not contribute to the cost, and simply counting the number of edges would give a terrible approximation (both in theory and in practice). One can take another example: for Erdos-Renyi graphs with $p=0.5$ and an instance from SBM with $p=0.95$, the numbers of positive edges are roughly the same, but the costs are very different.\n\n**MISC comments.** We appreciate the reviewer’s effort to catch the MISC issues. We will fix them accordingly in future versions of the paper. "}, {"review_id": "yUvPfXWbb4", "reviewer": "Reviewer_DYBZ", "summary": "The authors initiate a study of the correlation clustering problem in streams, in the setting when only the *cost* of the clustering needs to be output. Prior work on correlation clustering in streams focused on the \"semi-streaming\" model, in which the clustering must be output but a space of $\\tilde\\Theta(n)$ is allowed. On the other hand, the authors obtain algorithms using space $o(n)$ and even $\\mathrm{poly}\\log(n)$ when only the cost but not the clustering itself is required. The problem of computing the cost is motivated as a measure of the \"clusterability\" cost, and can be used to determine whether it makes sense to compute a clustering or not. \n\nThe authors provide both upper bounds and lower bounds for this problem. For upper bounds, the authors show that in $\\mathrm{poly}\\log(n)$ bits of space, one can obtain a mixed additive-multiplicative error guarantee, with $O(1)$ multiplicative error and $o(n^2)$ additive error. The authors also give show that a purely relative error guarantee cannot be obtained in $\\mathrm{poly}\\log(n)$ space by showing that an approximation with $c = O(1)$ multiplicative error and $\\epsilon n$ additive error requires $\\Omega(\\sqrt n)$ space, for some choices of constant $c$ and $\\epsilon$. Another lower bound that the authors give show that an algorithm achieving a purely additive $n^{2-\\epsilon}$ error requires $\\Omega(n^\\epsilon)$ space. Thus, one cannot hope for too much better than the algorithms given by the authors in general. Furthermore, the authors argue that the $o(n^2)$ additive error is in fact highly useful in practice. Indeed, for a typical application of detecting \"clustered\" communities in a stochastic block model where edges within communities are connected with probability p > 0.5 (say 0.8) and edges between communities with probability p < 0.5 (say 0.2), the $o(n^2)$ additive error algorithm suffices. The practical uses of the algorithm are verified empirically.\n\nIn terms of techniques, the authors give two upper bounds, one based on the classic Pivot algorithm and another based on sparse-dense decompositions developed in prior work. In both cases, the authors carefully implement the algorithms in the streaming setting by running the algorithms only on \"heavy hitter\" vertices and by gathering necessary statistics using sketching techniques. ", "questions": "See weaknesses.", "limitations": "The authors have thoroughly discussed the limitations (e.g. the additive error) and justified it (e.g. lower bounds).", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This work provides both a novel streaming problem with many interesting open questions and nice practical motivations, as well as an interesting and highly nontrivial upper bound. The gap between the upper bounds and lower bounds in this work are highly intriguing, and I would expect this work to stimulate many interesting follow-up works to tighten the results. Thus, the problem that is introduced is extremely interesting. The algorithmic techniques used in the upper bound seem to be a combination of prior work (known algorithms for correlation clustering combined with heavy hitters), but making this go through requires a lot of work in the analysis and is highly nontrivial. ", "weaknesses": "Just a couple of comments on the empirical results (however this is not that significant since the contribution of this work is primarily theoretical):\n* The axes in Figure 1 (and all the figures in the appendix in the supplementary material) are illegible. Please take advantage of the space availability in the supplementary material to provide better plots.\n* If $n = 1000, 2000$, then a semi-streaming algorithm would hypothetically use only roughly n/n^2 ~ 0.1% of the edges, so 4% or 10% of the edges does not seem that impressive in comparison at first glance. Are there any comparisons to semi-streaming algorithms in terms of empirical performance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your detailed review and your positive feedback. Here are our responses to the questions:\n\n**Point 1: Problems with the axes in the Figures.** Thanks for spotting out the issue, and we will fix the figures by making the text on the axes larger.\n\n**Point 2: Implementation of semi-streaming and the percentage of edges used.** We are not aware of any prior implementations of streaming correlation clustering algorithms. It appears that there are quite some barriers to implementing a complete large-scale semi-streaming correlation clustering system (or even large-scale semi-streaming in general) – some aspects that are assumed to not be problems in theory, e.g., polylog(n) overheads, I/O speed, and the need of external memory, become quite problematic in practical systems.  Take the connected components sketch for an example: the algorithm was known since Ahn et al. [SODA’12], yet the first implementation was only given until quite recently by Tench et al., [SIGMOD’22] (`GraphZeppelin’). The practical implementation of correlation clustering in semi-streaming space seems to be a very interesting problem on its own.\n\nWith regard to the percentage of edges saved, we suspect that the leading constant makes the percentage of stored edges rather high when $n$ is not too large (n=1000 or n=2000). Also, the log factors may become large in practice: for instance, when $n=2000$, $n/n^2=0.05$%, but $n \\log^{3}n / n^2=65.9$% (log with base 2, a typical semi-streaming bound). These factors may have contributed to the discrepancy between the theoretical bound and the practical performances and would affect semi-streaming algorithms too."}, {"review_id": "jpNwgSDqyo", "reviewer": "Reviewer_nMDo", "summary": "The paper gives polylog space streaming algorithm for approximately computing the value of the cost of correlation clustering. An algorithm for finding the (approximate) correlation clustering in polylog space is known to be not possible. It is also known that approximately computing the cost within a multiplicative factor is not possible in polylog space. This paper designs polylog space streaming algorithm for approximating the cost within a constant multiplicative plus an O(n^2) additive factor. They show that such an additive factor is necessary. The techniques used are sparse-dense decomposition of [AW22] and local correlation clustering of [BGK13].", "questions": "- Some of the other queries are mentioned above within the other fields.", "limitations": "This work is mostly theoretical. There are no negative societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The theoretical results are novel, well-motivated, and consistent with the known results. All the bounds are well justified. There aren't significant gaps in the presented results.\n2. The paper is well written. The results are well-motivated, related work is clearly stated, and the main ideas are clearly outlined in the allowed space.\n3. Experimental results show the capability of the algorithm to distinguish between high and low clusterable instances of random graphs generated in the stochastic block model.", "weaknesses": "1. Using some space to motivate the practical aspects of cost estimation (instead of computing the solution) will be useful for the readers. In the current version, this aspect of the motivation is pointed to the previous works.\n2. The experimental section also does not help with point (1) since it separates random graphs based on clusterability. A discussion on a real world example may help. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and your positive feedback. Our responses are as follows.\n\n**Point 1: Practical motivation.** Thanks for pointing this out, and we will add the discussion of the motivations in our later version. The motivation can be described roughly as follows. In large-scale applications, sometimes we want to know if the instances are worth clustering or not as resources might be limited; or rather, how much better it would be if we do clustering (trying to understand ‘clusterability’ of the instances). If we can test the clustering cost with only $\\text{polylog} \\ {n}$ space, then such a task can be accomplished in a local machine (as opposed to using a large cluster as in semi-streaming). \nWe could also use the value to differentiate between different classes of graphs that have different clustering costs. \n\nWe also agree that adding real-world examples will help, and we intend to make changes in the final version. \nIn our current paper, we believe that separating random graphs with SBMs *is already* a toy example for real-world applications. Consider two types of social networks: one is more structured (like SBM); the other is more chaotic (random graph-like). Our algorithm allows the users to classify different types of social networks in this regard."}, {"review_id": "4OQOAy7dHE", "reviewer": "Reviewer_E8E2", "summary": "The paper studies correlation clustering in the streaming model where the edges of the underlying graph are updated one  at a time. Where previous work has focused on the semi streaming model with $\\Omega(n)$ space, they consider more classic streaming with a polylogarithmic number of bits. Here it is not possible to describe the full clustering, so the goal is to estimate the \\emph{cost} of the correlation clustering. They consider $(a,b)$-approximation algorithms where if the optimal cost is $OPT$, the algorithm provides an estimate of at least $OPT$ but at most $a\\cdot OPT+b$. Their first result is a single-pass streaming algorihtm that is an $(O(1),\\delta n^2)$-approximation using $polylog (n)/\\delta^5$ space. Here the constant in the $O$-notation is rather large. However, they also present an algorithm which is an $(3,\\delta n^2)$-approximation in expectation using $2^{O(1/\\delta)} polylog(n)$ space. The first of these results is inspired by the sparse-dense decomposition [AW'22]. At a very high level, using sample based approached, they estimate the number of so called $\\varepsilon$-sparse and $\\varepsilon$-dense edges and relate these to the optimal clustering cost. This can be done for vertices of degree at least $\\delta n$ and the vertices with smaller degrees can contribute at most $\\delta n^2$ to the total cost (this is where the additive term comes from). This is by no means trivial and requires substantial technical work. For the second algorithm, they simulate an algorithm from an unpublished manuscript [BGK13].\n\nThe paper also provides lower bounds showing that an $(1,n^{2-\\varepsilon})$-approximation requires $n^\\varepsilon$ space (this is via a reduction from the INDEX problem) and that an $(1.19,O(n))$-approximation requires $\\Omega(\\sqrt{n})$ space.\n\nThe paper also provides experiments demonstrating the performance of their algorithms on the stochastic block model (SBM) and for Erdos-Renyi random graphs (ER). It is of interest that their algorithms are able to distinguish the clusterable setting in SBM from that the ER $G(n,p)$ which are not clusterable at all.", "questions": "l85: This seems incorrect. To get sublinear space, you put $\\delta=n^{-0.19}$ and then the additive error is $n^{1.81}$ \n\nl104-110: This section is a little clumsily written and could use a rewriting to make it clearer \n\nl119: What does $0.04\\% \\sim 3.6\\%$ mean? \n\nl276-277: $S_i$ and $m_u$ have not been defined \n\nl347-348: This seems unsurprising. Could it be proved by some union bound approach? ", "limitations": "The authors have adequately addressed limitations. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "It is in interesting problem to study the correlation clustering problem in the low space regime both from a theoretical and practical perspective. The paper is well written and the proofs that I looked at in the supplementary material also seem to be clearly written (I only looked at a few of them so I cannot vouch for correctness, however I gave a 4 for soundness based on the ones I checked). The technical contribution of the paper seems impressive, in particular since they also provide lower bounds for the problem.", "weaknesses": "It is a little unclear which ideas are novel and which ideas are inspired from previous work e.g., [AW'22].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and your positive feedback and also for catching all our tiny errors. Below are our responses:\n\n**Point1: Which ideas are new and which are existing.**\nGetting approximate clustering in $\\tilde{O}(n)$ space via the algorithms (SDD/Pivot) was already known. The novel idea here lies in estimating the costs of these algorithms within polylog(n) space only (especially since it requires exponentially larger $\\Omega(n)$ memory to directly run SDD/Pivot).\n\nThe main idea for the SDD algorithm was that we could get an $O(1)$ approximation to the cost using epsilon sparse and epsilon dense edges. We then built the estimators to estimate the number of these edges with an additive error.\n\nThe main idea for the pivot algorithm was that we could do the greedy MIS (to find the pivots) after the stream. Then we built estimators to estimate the cost of the clusters.\n\n**Point 2: Questions/MISC comments.**\n\nL85: Yes, you are right we made a calculation error. Thanks for the catch! What we meant to say was setting delta to $n^{0.19}$ would make the space $o(n)$ and the error $o(n^2)$. We will fix this.\n\nL104-110: We agree that this paragraph is not very well written. We will rewrite it in the final version.\n\nL119: What we mean here is the following: The fraction of total edges stored by the Pivot-based algorithm is 0.04%.\nThe fraction of total edges stored by the SDD-based algorithm is 3.6%.\n\nL276-277: $S_i$ and $m_u$ are defined in the full version (supplementary material), but when we were creating the conference version, it appears there are some nuaunce ordering issues (e.g., $S_i$ is defined in the algorithm box, which appears before claim 4.2; but in the conference version it appears later). We will fix this in the final version.\n\nL347-348: We can prove that an Erdos-Renyi random graph with p=0.5 has an optimal clustering cost of $\\Omega(n^2)$ using charging arguments similar to [AW22]. We are not familiar with the ``union bound approach’’ mentioned in the review – we will be happy to learn more from you about this.\n"}]

Author rebuttal:

Meta-review: Most reviewers agreed that the problem studied is well-motivated and the technical results are solid, except one reviewer who commented that "Result 1" and "Result 2" of this paper can "straightforwardly be beaten using known techniques". The authors addressed this criticism; however, we have not received any further response from that reviewer. Based on my examination of the authors' response, it seems that the criticism cannot be adequately justified without working out the actual proofs.
Decision: Accept (poster)