Learning-Augmented Streaming Algorithms for Correlation Clustering
Authors: Yinhao Dong
Shan Jiang
Shi Li
Pan Peng
Venue: NeurIPS 2025 poster ()
Keywords: Correlation Clustering
graph streaming algorithms
learning-augmented algorithms
Primary area: theory
TL;DR: We introduce the first learning-augmented streaming algorithms for Correlation Clustering on both complete and general graphs, improving the best-known space-approximation tradeoffs.

Abstract: We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partition the vertices into disjoint clusters, such that the number of disagreements is minimized. In this paper, we give the first learning-augmented streaming algorithms for the problem on both complete and general graphs, improving the best-known space-approximation tradeoffs. Based on the works of Cambus et al. (SODA'24) and Ahn et al. (ICML'15), our algorithms use the predictions of pairwise distances between vertices provided by a predictor. For complete graphs, our algorithm achieves a better-than-$3$ approximation under good prediction quality, while using $\tilde{O}(n)$ total space. For general graphs, our algorithm achieves an $O(\log |E^-|)$ approximation under good prediction quality using $\tilde{O}(n)$ total space, improving the best-known non-learning algorithm in terms of space efficiency. Experimental results on synthetic and real-world datasets demonstrate the superiority of our proposed algorithms over their non-learning counterparts.

Learning-Augmented Streaming Algorithms for Correlation Clustering
Yinhao Dong'
Shan Jiang'
Shi Li23
Pan Peng
"School of Computer Science and Technology.
University of Science and Technology of China, Hefei, Anhui Province, China
Sccooo of Computer Science, Nanjing University, Nanjing, Jiangsu Province, China
"New Comerstone Science Laboratory
{yhdong, j__ ustc. ust...u..ccc.r shilionjul www.nuu..uuu..... edu. cn, ppenguustc. edu.
Abstract
We study streaming algorithms for Correlation Clustering. Given a graph arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is partition the vertices into disjoint clusters, such that the number of disagreements is minimized. In this paper, we give the first leamiig-auggmented streaming algorithms for the problem on both complete and general graphs, im- proving the best-known space-appros apace-aprrxximation tradeoffs. Based on the works of Cambus et al. (S0DA'24) and Ahn al. (ICML' 15), our algorithms use the predictions of pairwise distances between vertices provided by predictor. For complete graphs, our algorithm achieves better-than-3 approximation under good prediction quality, while using ((n) total space. For general graphs, our algorithm achieves an O(log] (F-)) approximation under good prediction quality using Ö(n) total space, improving the best-known non-learning algorithm in terms of space efficiency. Experimental results on synthetic and real-world datasets demonstrate the superiority of our proposed algorithms over their non-learning counterparts.
Introduction
Correlation Clustering is fundamental problem in machine learning and data mining, and it has wide range of applications, such as image segmentation [66]. community detection [86] 91]]
automated labeling (28), etc. Given graph G (V, = E E-), where each edge is labeled as positive (+) or negative (-), the goal is to find clustering C, i.e., a partition of V into disjoint clusters C1, ..,..., Cr, where is arbitrary, that minimizes the following cost:
(C) [u, v) E E+ Di + j, u E C, CjH++ 1((,,,)))) ET : C.H. (1)
That is, the number of positive edges between different clusters, plus the number of negative edges within the same cluster. (We often refer to this as the number of disagreements.)
The most commonly studied version of this problem is on complete graphs, introduced by Bansal [15), and known to be NP-hard and even APX-hard [31]. Hence, significant efforts have
been dedicated to designing approximation algorithms for this setting [5] 15
23 24
31
32 37 39)
24 In contrast, the problem on general graphs has received less attention. Charikar et al. [1 and Demaine et al. [44] proposed an Ollog zi -approximatioo algorithm via ball-growing based LP rounding. They also showed that this version equivalent to the minimum multicut problem, and is thus APX-hard and unlikely to admit tetter-than-O(lgg n)) approximations.
culminating
appoixaiooinntioon via linear program (LP) based rounding 23
*Coresponding Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Partially due to storage limitations and the rapidly growing volume of data, streaming algorithms for Correlation Clustering have received increasing attention recently. In this setting, a graph is represented as sequence of edge insertions or deletions, known as a graph stream. The objective to sean the sequence in a few number of passes, ideally, 1 pass and find high-quality clustering of the vertex set, while minimizing space usage. If the sequence contains only edge insertions, it is referred to as an insertion-only stream; if both insertions and deletions are allowed, it is referred to as dynamic stream. Since the output of the clustering inherently requires (2(n)) space (as each vertex needs a label to indicate its cluster membership), most previous research has primarily focused on the semi- streaminn model [50], i.e., the algorithm is allowed to use ((n) := O(n polylog n) space We note that the space used by the streaming algorithm can be further divided into the space for updating data structures during the stream and the space for post-processing.
A long line of prior work has focused on the complete graph setting If the total space of the algorithm is restricted to Ó()), then the best-known space-apaee pancee-pproximatiio tradeoff in dynamic streams is (3 + -ppproxxiimtioon algorithm 12 which uses ((s-11p)) total space. If only the space used for updating during the stream is restricted to (n)). then the best-known space-appres aprrrxiaproiiiiionnnn tradeoff in dynamic streams is achieved by an (agEST + E) -appooximmaioon algorithm [10), where 1.042 I QBEEST S 1.437 [24] denotes the best approximation ratio of any polynomial ternomial-timeeeeeeoo classical algorithm. However, this algorithm does not bound the space for post- processing, which can be significantly larger. For general graphs, the only known dynamic streaming algorithm is due to Ahn et al.
36 39
[4), which uses the multiplicative weight update method on the sparsified graph to achieve a 3(1 + E) log E |-apprxximation while using Ō( + (E-1) space.
In this paper, we explore new approaches that enable improved space-approximation tradeoffs on both complete and general graphs by leveraging ideas from learning-augmentie algorithms. A eaaniig--augmented algorithm uses predictions to enhance its performance. These algorithms stem from practical scenarios where machine learning techniques exploit data structure to exceed the worst-case guarantees of traditional algorithms. Our learning-augmente algorithms fit into the category of searning-augmentn
streaming algorithms [1 2 33 47 588 [1]. It is worth mentioning that both our work and previous efforts on poamiing-augentte streaming algorithms mainly focus on using predictors to improve the corresponding space-accuragy tradeoffs.
Now, we describe the prediction we are considering. We assume that the algorithm has oracle access to predictor II: : (M) + [0, 1] that predicts the pairwise distances du. between any two vertices and v in V. We believe such predictors are natural and arise many situations.
Example 1.1 (Multiple graphs on the same vertex set). It is common to define multiple graphs over the same vertex set. For example, in healtheare, patients can be represented as vertices, and different networks may capture relationships such as shared medical conditions (disease networks), visits to the same providers (provider networks), or participation in clinical trials. In biology, vertices might represent genes or proteins, with different networks reflecting notein-protein interactions, gene co-expression, or signaling pathways. Machine learning or data mining techniques can then be used to learn pairwise distances between nodes across these networks. If two patients genes/proteins are similar in one network, they often exhibit similar behavior in others.
Example 1.2 (Temporal graphs). A similar situation occurs in temporal graphs, where a sequence of graphs shares the same vertex set but has different edge sets over time. Pairwise distances learned from past graphs can help extract structural insights in the present or future.
Leveraging these distances across networks can greatly aid in exploring the cluster structure of any newly defined network over the same vertex set. We also remark that several other works have considered similar oracles for pairwise distance in different contexts, such as the query model 67 87
1.1
Our results
Our results are summarized in Table [ Using the above predictions, we give the first learning- augmented streaming algorithms for Correlation Clustering on both complete and general graphs. Specificallyy, for complete graphs, our algorithm beats the 3-approximation if the predictions are
'On the other hand, Assadi et al. M studied streaming algorithms using polylog n bits of space for estimating the optimum Correlation Clustering cost, while their algorithms do not find the clustering.
Note that one can directly treat 1 dye the pairwise similarity between and v.
2

---

Table I: Comparison of our main results with the best-known space-aprroximation tradeoffs in polynomial time. Here, n = I E (0, 1) and 2 1. All algorithms are single-pass, pass, and space is measured in words.
Best-known space-approximation
Setting
Our results
tradeoffs (without predictions)
E aapproximation.
Ō - n) total space 22
complete graphs, dynamic streams
(min 3) + approxxiiatinn O total space (Theorem 1.3
(QBEST + aaappoooiiation
Ō( space for updating,
poly(n) space for post-processing
10
general graphs, dynamic streams
( Jaaproximatiin.
( ([3log| E Daapproximation, Ō(=-3n total space (Theorem 1.4
0 E
total space 4
good, while still achieving a (3 + E) >-approximation even the predictor behaves poorly. For general graphs, our algorithm achieves (log EE ()approximmtton under good quality while using less space than the existing non-learning algorithm. Furthermore, our algorithms are simple and easily implementable. We will use parameter 3 2 1 to measure the quality of our predictor. Informally, we call a predictor ß-level if the cost of the clustering induced by the predictions is at most a / factor of the cost of the optimal solution. We refer to Section 3 for the formal definition. In short, the smaller B is, the higher the quality of the predictor.
For the complete graph setting, we have the following theorem. (In the following and throughout the paper, "with high probability" refers to the probability at least 1 - 1/n for some constant e > 0.)
Theorem 1.3. Let E (0, 1/4) and 3 2 1. Given oracle access to a 3-level predictor, there exists a single-pass streaming algorithm that, with high probability, achieves an expected (min{2.0633 3)++)- approximation for Correlation Clustering on complete graphs in dynamic streams. The algorithm uses Ó( 2n) words of space.
Note that our algorithm achieves a better-than-3 approximation in dynamic streams under good prediction quality, whereas the previous best-known semi-streaming algorithm in dynamic streams a (3 --approximmtton due to Cambus et al. [22). That is, our algorithm is both consistent and robust, desired for most natural learning-auge augmeenedd algorithms [80]. We further highlight that the recent (OBEST + --aaproxxmmation algorithm [0 does not bound the space usage during the post- processing phase, which may be larger than (n). On the other hand, while there exists a single- pagge--ass (1 s1++s--appe apappoxxinniio algorithm for dynamic streams [4] 18), requires exponential prooepronssiing time and is thus impractical. In contrast, our algorithm uses polynomial post-processing time.
Furthermore, also obtain algorithm for complete graphs in insertion-only streams (see Ap- pendix which differs from our algorithm in dynamic streams but achieves the same approximation ratio. It is simpler and more practical than the existing 1.847-approximation algorithm [39]
For general graphs, we present the following result on the approximation-spee spacee trade-off for streaming Correlation Clustering, using slightly different type of predictor.
Theorem 1.4. Let (0, 1/4) and 3 2 1. Given oracle access an adapted B-level predictor, there exists a single-pass streaming algorithm that, with high probability, achieves an (B log E l)- approximation for Correlation Clustering general graphs in dynamic streams. The algorithm uses Ó(E 22n words of space.
We remark that the above algorithm can be extended to work under the previous notion of predictors for a broad class of graphs (see Corollary F.I). Note that the best-known streaming algorithm for general graphs an O (log | I-approxiaiti while using Ō( 2n + [E']) words of space [4]. In contrast, our learning -aggmentedd algorithm attains comparable approximation ratio under good prediction quality, while using less space. We also note that it is standard to assume that the space required to implement/store the predictor is not included in the space usage of our algorithms, as is common in
streaming algorithms 2 33 58,66 61].
To complement our theoretical results, we conduct comprehensive experiments to evaluate our algorithms on both synthetic and real-world datasets. Experimental results demonstrate the superiority of our
algorithms. All the missing proofs are deferred to appendix.
3

---

1.2 Further related work
Correlation Clustering. In this paper, we study streaming algorithms for Correlation Clustering. In the era of big data, other sublinear models for this problem have also received considerable
attention in recent years, including uublinear-tima algorithms [22 23 39], the Massively Parallel
Computation (MPC) model [17 23
25
36
39 [1], and vertex/edge fully dynamic models [16 41]
From another perspective, we focus on the minimization version of Correlation Clustering, which aims to minimize the number of disagreements. Other variants of this problem have also been studied, such as maximizing agreements [89] or minimizing certain norms or all norms-of the
disagreement vector 26 30 42
56 63 82
Learning-augmentte algorithms. Leaming-augmmntedd algorithms, also known as algorithms with predictions, have been actively studied in the context of online algorithms [6]
7
9
13
59 68
77 83
data structures [5]] 73
79
85 90], graph algorithms [14
20
34
45
46
57
69
74 sublinear-
time algorithms 48 60 72, approximation algorithms 8
21
35
53
8 and mechanism
design 3
92, among others. Our work fits into the category
(graph) streaming algorithms.
2 Preliminaries
with V Throughout the paper, we let (V. F) be an undirected and unweighted graph |F| m, where each edge is labeled as positive or negative (i.e., F = E+ U E-). In some places of the paper, we identify the input graph only with the set of positive edges, i.e., G+ = (V. E and the negative edges are defined implicitly. For each vertex u E V. let Nu)) be the set of all neighbors of u and (u) be the set of positive neighbors of u (i.e., vertices that are connected by positive edge). Correspondingly, let deg(u) := [u]] be the degree of u, and similarly, deg + (u) == | (u)l- We use cC) to denote the cost of the clustering C on G, as defined in Eq. (T. We say an algorithm achieves an a-approximation it outputs clustering C on G
Notations.
such that OPT I (C) s OPT, where OPT denotes the cost of optimal solution on G.
Due to space limitations, we introduce additional technical preliminaries in Appendix A
3 The f-level predictor
In this section, we give the formal definition of a 3--level predictor.
Definition 3.1 (3-1evel predictor). For any /3 2 1, we call a predictor B-level, if it predicts the pairwise distances dwo [0, 1] between any two vertices u and u in G such that
(triangle inequality) due + dnw 2 dn for all u, v, E V.
Σ [U,N)EE+ duv + E(W,))E-- (1- drav) S B OPT.
Intuitively, smaller & indicates higher-quality predictor, and in this case dwo can be used to determine how likely u and u are in the same cluster of the optimal solution. However, we point out that the predictions can be completely independent of the input graph. In the worst case, the predictions can be arbitrarily bad, which is allowed for robustness a desired goal. We remark that Definition 3.I inspired by the metric LP formulation of Correlation Clustering. In sense, the 3-level predictor corresponds to a feasible solution to the LP.
algorithms since
Furthermore, for a general graph, we say pairwise distance predictor is an adapted f-level predictor satisfies the triangle inequality and L(..))E W duv + (u.)ER (1 duw) Σ B OPT,
where H + = (V, Et w') is an e-spectral sparsifier of G = (V, E+), which approximates all the cuts in G within a (1 =) factor.
Practical consideration of the predictor. As mentioned earlier, to cluster graph, we may use ML models such as graph neural networks (GNNs) to learn pairwise distances from related networks defined on the same vertex set. These models can be trained to extract meaningful distances. for example, by learning node embeddings that map vertices to Euclidean space. The distances between these embeddings naturally serve as pairwise distances and satisfy the triangle inequality. Although the second condition in Definition 3.1 is technical requirement for theoretical analysis,

---

our algorithms remain applicable even when the given pairwise distances do not strictly satisfy this condition. practice, as long as the distances are meaningful, they can be directly incorporated into our framework. We refer to Section 6 for empirical results.
4
Our algorithm for complete graphs in dynamic streams
4.1 Offline version
Overview. To better illustrate the algorithmic ideas, we first describe the offline version of our algorithm (see Algorithm 3 in Appendix C). The overall framework is similar to the algorithm proposed by Cambus et al. [22] Our algorithm takes G+ = EV, as input. Initially, we pick a random permutation over the vertices. Then we divide all vertices into interesting and uninteresting vertices based on the relationship between the rank and the positive degree of a vertex. Specifically, a vertex u is uninteresting if .. 2 Tu where Tu == &
log nt (or equivalently deg (u) 2 ou where deg (u)
Ta = n logg) ) and interesting otherwise. Here, & E (0, 1/4) and is a universal large constant. my
We run two pivot- based algorithms on the subgraph Suooe induced by the set of interesting vertices and obtain two clusterings. Finallyy output the clustering with the lower cost.
Specifically, the two pivot-based algorithms used the clustering phase are described as follows.
Algorithm TRUNCATEDPIVOT. This algorithm simulates the Paraliel Truncated-Pive algorithm by Cambus et al. [22] and produces the same clustering. This algorithm proceeds in iterations. Let ( denote the set of unclustered vertices in Gsurr at the beginning of iteration t. Initially, all the interesting vertices are unclustered. At the beginning of iteration i,, if (7()) of 0, then we pick the vertex from (()) with the smallest rank. Then we mark it as pivot and create pivot cluster (t() containing u and all of its unclustered positive neighbors in G At the end of iteration 6, we remove all vertices clustered in this iteration from (7(1), Then the algorithm proceeds to the next iteration. If (+)) = at the beginning of iteration t, then we know that all the interesting vertices are clustered. Now it suffices to assign each uninteresting vertex to a cluster. Each uninteresting vertex joins the cluster of pivot o with the smallest rank if (u, v) E E' and n. < Tu. Then each unclustered vertex E V creates a singleton cluster. Finally, we output all pivot clusters and singleton clusters. We defer its pseudocode (Algorithm 4 to Appendix [C
This algorithm has oracle access to 3-level predictor II. The algorithm closely resembles Algorithm T'RUNCATEDPIVOT. The differences are as follows:
Algorithm
(I) At iteration f, we create a pivot cluster g(t) containing u and add all the unclustered vertices in Gstore to ((t) with probability (1 -w- independently, where Puv - [(due) and duo II(u, v).
If (u, v) E E+, then (duv) = (duun); otherwise f(dww) = f (dwa.. We set f+(x) to be 0 if <a (3- )2 if x E [a, b), and 1 if b. where a 0.19 and i = 0.5095;
set f-xx) x. (2)
Each uninteresting vertex joins the cluster of pivot in the order of with probability (1 Pue) independently. if n. Tu- We defer its pseudocode (Algorithm 5 to Appendix
We have the following approximation guarantee of the offline algorithm.
Lemma 4.1. Let (0, 1/4) and 8 1. Given oracle access to a 3-level predictor, the offline algorithm (Algorithm) 3) achieves an expected (min(2.068) 3} + E) eapproxximation
4.2 Implementation in dynamic streams
In this subsection, we implement the offline algorithm in dynamic streams, as shown in Algorithm A key observation is that suffices to store the positive edges incident to interesting vertices since we apply pasot-based algorithms assign uninteresting vertices to pivot clusters. To this end, we maintain a certain number of 6-- samplers for each vertex, which can be achieved in dynamic streams (62). As we will see in the analysis, the fo-samplers allow us to recover the edges incident to all the interesting vertices with high probability. Thus simulate TRUNCATEDPIVor and TRUNCATEDPIVON WITHPRED using the stored information, and finally output the clustering with the lower cost.
the subgraph induced by interesting vertices and then try to
simulate the clustering phase of the offline algorithm. Specifically,
Note that in the final step, the cost of clustering cannot be exactly calculated, as our streaming algorithm cannot store the entire graph. To overcome this challenge, we borrow the idea from (18) and
5

---

Algorithm An algorithm for complete graphs in dynamic streams
Input: Graph G
E*) as an arbitrary-order dynamic stream of edges, oracle access to 8-level predictor II
Output: Elustering/Parttiionn of V into disjoint sets
Pre-processing phase
1: Pick a random permutation of vertices т V + (.)
2: for each vertex u E V do
3: Let deg 1 (u) +- O. Mark u as unclustered and interesting.
4: Let == { a l where e is a universal large constant.
5: Initialize 10c 10clog au independent fo-smpplers (with failure probability 1/10) for the adjacency vector of u (the row of the adjacency matrix of G+ that corresponds to u).
b Streaming phase
6: for each item (e: = (u, v), Ar (-1,1)) in the dynamic stream do
7: Update deg (log((n) (u), deg sogg*(() (v) and all the fo-samplers associated with and u.
8: Maintain an e-spectral sparsifier H+ for G+ using the algorithm of Theorem A.6
Post- Post-processing phase
9: A vertex u marks itself uninteresting if deg (u) 2 au-
10: Retrieve all incident edges of interesting vertices (with high probability) using the to samplers.
11: Let Gaore be the graph induced by the interesting vertices.
12: Ci TRUNCATEDPIVOTT (G+ Gatore, π)
13: C - SRNNCAATDDPVVOOWWHPRREDDDD
Gstore, IIII)
14: (C1) + Ecec, ( (()) Eu deg (u))
15: (C2) + Ecec, (20
(1c1) Euec deg" (u))
16: t arg min; 1,2 (C.))
17: return C,
utilize the graph sparsification technique [64 to estimate the clustering cost. Specifically, during the dynamic stream, we maintain an E-spectral sparsifier H for G using the algorithm Theorem We also maintain the positive degree deg+ for each vertex Then we can approximate the cost of a clustering up to (1 -ulliplilica error with high probability. The formal proof of Theorem 1.3 is deferred Appendix D.I
4.3 Analysis the offline algorithm
Since the final clustering returned by the offline algorithm is the one with the lower cost between those produced by the two pivot-based algorithms, we start by analyzing the costs of these two clusterings. For ease analysis, we separately examine the approximation ratios of the equivalent versions (Algorithms CKLPU-PIVOT and PAIRWISEDDSS) that produce these two clusterings.
Algorithm CKLPU-PIVOT (Algorithm 4 in (22). This algorithm proceeds in iterations. Let (+(t) denote the set of unclustered vertices at the beginning of iteration t. Initially, pick random permutation ι over vertices, and all the vertices are unclustered. At the beginning of iteration I, let 4 = n log Each unclustered vertex o with deg (v) 2 f creates a singleton cluster. We pick the (-th vertex in If is unclustered, then mark it as pivot and create pivol cluster ((t) containing u and all of its unclustered positive neighbors. At the end of iteration I, we remove vertices clustered in this iteration from (+)) and proceed to the next iteration. Finally, we output all pivot clusters and singleton clusters. We defer its pseudocode (Algorithm O to Appendix C
Algorithm PAIRWISEDISS. This algorithm has oracle access f--eeel predictor II. The only difference from Algorithm CKLPU-PIVOT is that at iteration t, create pivor cluster S(t containing u and add all unclustered vertices to S(t) with probability (1 Pav) independently. where P.. = f(d..) and d ITu, v). We defer its pseudocode (Algorithm) to Appendix C
The offline algorithm combination of CKLPU-PIVOT and PAIRWISEDISS that the offline algorithm can be equivalently viewed as a combination of Algorithms CKLPU-PIVOT and PAIRWISEDISS, assuming the same randomness is used.
We first show

---

Lemma 4.2 (Lemma 8 in (22)). the offtine algorithm (Algorithm 3) and CKLPU-PIVOT use the same permutation T, then TRUNCATEDPIVOT and CKLPU-PIVON output the same clustering.
Lemma 4.3. If the offline algorithm (Algorithm 3) and PAIRWISEDISS use the same permulation and predictions {dwe Juvev. then TRUNCATED same clustering with the same probability.
and PAIRWISEDISS output the
4.3.1 The approximation ratios of CKLPU-PIVOT and PAIRWISEDISS
Now it suffices to analyze Algorithms CKLPU-PIVOT and PAIRWISEDISS separately. We follow the analysis framework in (22). Specifically, we analyze the costs of pivot clusters and singleton clusters separately. For the former, we can directly apply the analysis of original pivot-based algorithms [2]. Note that here we only need to focus a subset of vertices (i.e., V Vsin where Vsin is the set of singletons). For the latter, we divide all the positive edges incident to singleton clusters (denoted as E into good edges (Egood) and bad edges (Etw)). Specifically, a singleton cluster to be good if the other endpoint was included in a pivot cluster before the singleton was created. Otherwise, the edge is bad. In other words, bad edges are those that either connect two singletons or the other endpoint was included in a pivot cluster after the singleton was created. The analysis in [22] shows that both the costs of good and bad edges be charged to the pivot clusters, allowing us to bound the overall clustering cost.
define positive edge incident to
The following lemma states the approximation guarantee of CKLPU-PIVOT, and thus that of the clustering returned by TRUNCATEDPIVOT.
Lemma 4.4 ((22). ). Let 1041/4). Let C₁ denote the clustering returned by TRUNCATEDPIVOT, then Elcoste (C1) S (3 + 12s) OPT + 1+4s,
2. where := c/2 1
Next, we focus the analysis of Algorithm PAIRWISEDISS.
Lemma 4.5. Let P denote the cost of pivot clusters returned by Algorithm PAIRWISEDISS. We have E[P] < 2.063 OPT.
Proof. Consider iteration t of PAIRWISEDISS, if vertex u considered in this iteration is unclustered (i.e., u E U then we call iteration t a pivot iteration. The key observation is that the pivot iterations in PAIRWISEDISS are equivalent to the iterations of a.0--approxiiatiion LP rounding algorithm [32
given that u is unclustered (i.e., u E U(t)), the conditional distribution of u is uniformly distributed in U((), and the cluster created during this iteration contains u and all the unclustered vertices v added with probability (1 Puv). Therefore,
directly apply the triangle-based analysis in (3)
Define L : E(unje duv + -(..)-E (1- Since the predictor is f-level, by Definition 3.1
the predictions (duv Ju,EV satisfy triangle inequality and T, S 3 OPT. It follows that for all pivot [dwn)uvvV
iterations 1, E[P(O] < 2.06 ("], where p(() is the cost induced by the pivot cluster created at iteration and (t) E(u.))EEngtt duv + ((aN)EE (oan))EEE-EE))( ngo duv) where Et() is the set
of edges decided at iteration 4, i.e., E(O) = {(u,,) E E U E U()); u E 5(0) or E 5t0). By linearity of expectation, we have ETP] Et pivot iteration 1T( S 2.06 L S 2.063 OPT. O
Corollary 4.6. Let E (0, 1/4). Let C2 denote the clustering returned by TTRNNCATEDPIVOTWTTT 1+4c n--2, where = c/2 - 1 2.
PRED. We have Elcostt < (2.0633 + 8.243z). OPT
We defer the proofs of Lemma
Corollary 4.6 and, finally, Lemma to Appendix D
5 Our algorithm for general graphs in dynamic streams
Overview of the algorithm Our algorithm is given in Algorithm 2 The core of our algorithm builds upon the ball- ball-growing framework in the work of Charikara et al. 31 and Demaine et al. [44). In algorithm,
apply this framework distance metrics. Specifically, during the streaming phase, we maintain an E-spectral sparsifier H : (V, E w²) for G+ F+).
sparsified graph and use the predictions dug as
At the same time, we store all arriving negative edges and track their space usage. If, at any point, this space exceeds Ö(n-2n) words, we immediately stop storing negative edges. Once the stream ends (i.e., after H has been constructed), we proceed to the post-processing phase and run the
7

---

Algorithm 2 An algorithm for general graphs in dynamic streams
Input: Graph G = (V, VV, E) as an arbitrary-order dynamic stream of edges, oracle access to adapted
8-level predictor II
Output: Clustering/Partttion of V into disjoint sets
> Streaming phase
Maintain E-spectral sparsifier H (V. w') for G using the algorithm of Theorem A.6
2: Meanwhile, store all arriving negative edges and track their space usage. If the space ever exceeds On) words, then stop storing negative edges and, after the stream ends, goto Line Post-processing phase
3: Run the post-processing phase of the algorithm by Ahn et al. 4 and return the clustering C₁.
4: Let VR f and ER + Et denote the sets of remaining vertices and edges, respectively,
5: Let C2 +- 0.
6: For any u, U V, duv = II(u,v).
7: while VR # 0 do
8: Let R = (VR, ER) denote the current graph. Pick an arbitrary vertex u E VR. Let Ta + 0. Increase Ta and grow ball Ba(u,r.) on R such that 0h (Ba(u,r.) 3 I 1) volg (Ba(u, rw)).
9:
10:
C2 f- C2 U Ba(u,
11:
Remove the vertices in Ba(u, rw) from Vi and the incident edges from Eg-
12:
return C2
ball-growing procedure H+ obtain the final clustering C2. On the other hand, if the total space for storing negative edges remains within ( throughout the stream, instead invoke the post-processing phase of the algorithm by Ahn et al. and return the resulting clustering C₁.
Next we describe the ball-growing procedure, which proceeds iteratively. We initialize the clustering C2 = 0. Let R == (VR, ER) denote the current graph at each iteration, where VR and Fn are sets of remaining vertices and edges, respectively. Initially, we set Vn = and En = F At each iteration, we select an arbitrary vertex u E Vn as the center and initialize its radius as gradually increase ra to grow a ball around until certain condition met. Then we all the vertices in the ball as new cluster, remove them along with their incident edges from the current graph, and proceed to the next iteration. This process is repeated until no vertices are left.
0. We
More precisely, for a vertex u E VR and a radius 2 O, we define the ball centered at with radius Tu as Ba(u,ra) = {u E VR due S ru). which consists of all vertices in R within distance at most Tu from u, where distances are measured according to the predictions.
We next define the value and volume associated with ball. Let 0H + (Ba(u, r.)) denote the value of the cut (Ba(u, u, rw), ), V Ba Pa)) in H
0h+ (Ba(u, rw))
Σ
(,.w)EE WE BB(uu,r By(,,ru)
Furthermore, we define the volume the ball Ba(u, in H+, denoted by vol (Ba(u,ra))
volg-(Ba(u,ra)) V
Σ
W/o dew +
Σ
wow - drv);
T
(0,0) E WE (alu)r))))n hod Ba(urr.)
where == E( W duo denotes the total volume of the graph H+
The ball is finalized once the cut value induced by the ball is at most (lognn times its volume. Specifically, we require that 0z+ (Ba(u, r.)) & 3ln(n + 1) vol + (Ba(u, ra)). This condition guaranteed by the following lemma:
For any vertex u, there exists a radius ra < 1/3 (which can be found in polynomial time) such that the corresponding ball Ba(u, Ta) satisfies Ön (Ba(,, S 3 In(x+1) volg+ (Ba(u, r.)).
Lemma 5.1 B1 52

---

5.1 Analysis of Algorithm 2
Space complexity. The space complexity of Algorithm{ dominated by maintaining the E-spectral sparsifier and storing the negative edges during the streaming phase. By Theorem A.6 and the condition in Line 2 the algorithm uses 3n) words of space.
Approximation guarantee. Recall the condition in Line remains within O( ?n) throughout the stream, then the resulting clustering C1 is given by the algorithm of Ahn et al. A. which has the following guarantee.
2 if the space used to store negative edges
Lemma 5.2 (C1) S 3(1 + e) log E OPT = Olog [) OPT.
Otherwise, we have E 2 and the clustering C2 is obtained via the ball- -roooig procedure. We now analyze the cost of C2, which consists of two parts: the number of positive edges that cross between different clusters, and the number of negative edges that lie in the same cluster. In the following, we bound these two quantíties separately.
Consider the weighted graph H == EV
U UE, .)). where the edge weights are defined as Vae = whe for (u, v) E Et and tuv = for (u,v) E ET. The positive and negative costs of C2 on H, denoted cost (C2) and cost # (C2) respectively, can be bounded by the following two lemmas.
Lemma 5.3. cost H (C2) S 3 In(n + 1) E E(w,)eE w dww.
Lemma 5.4. cost (C2) S 3 (u.w)EF- (1 duv).
Now are ready to bound the cost of C2 G. Lemma 5.5. (C2) O(3 log |) OPT.
Due to space limits, we defer the proofs of Lemma 5.3 Lemma 5.4 and Lemma 5.3 to Appendix
Proof of Theorem 1.4 Theorem follows from Lemma 5.2 and Lemma 5.5
Furthermore, if the input graph satisfies certain mild conditions, then the adapted 3-level predictor can be relaxed to the standard 3-level predictor (Definition 3.1. We defer the details to Appendix F4
6 Experiments
In this section, we evaluate our proposed algorithm for complete graphs empirically on synthetic and real-world datasets. All experiments conducted CPU with i7-13700H processor and 32 GB RAM. For all results, unless otherwise stated, we report the average clustering cost over 20 independent trials. Our source code is available in the supplementary material.
Datasets. 1) Synthetic datasets. These datasets are generated from the Stochastic Block Model (SBM). We use this model to plant ground-truth clusters. It samples positive edges between vertex pairs within the same cluster with probability p > 0.5, and samples positive edges across different clusters with probability (1 p). 2) Real-world datasets. We use EMAILCORE [70 99], FACE- BOOK 778. LASTEM [84,, and DBLP [93] datasets. For simplicity, for all datasets, we only simulate insertion-only streams of edges. We refer to Appendix G. for detailed descriptions of the datasets.
Predictor descriptions. 1) Noisy predictor. We use this predictor for datasets with available optimal clusterings. We form this predictor by performing perturbations on optimal clusterings. 2) Spectral embedding. We use this predictor for EMAILCORE and LASTEM. It first maps all vertices to Rd using the graph Laplacian, then clusters all vertices based their embeddings. For any two vertices u, v E V, we form the prediction du. based on the spectral embeddings u, v. 3) Binary classifier. We use this predictor for datasets with available ground- truth communities. This predictor constructed by training a binary classifier to predict whether two vertices belong to the same cluster using node features. The predictions (i.e., binary values in {0. 1)) then used as pairwise distances d, in our algorithms. We refer to Appendix G.2 for detailed descriptions the predictors.
Baselines. 1) (3 + (3++)--aproon appprooximtiio non-learning counterparts. For our algorithm for complete
graphs dynamic streams, the counterpart is Algorithm CKIPUU2 222 2) The agreement decomposition algorithm CLMNPT21 [36). Though the approximation ratio in theory is large

---

CRLPIDA CUMUUI21
Mipertoon
10 CAR-
CIMSPT21 ANViTV
077
371
012724
CLLP224
Ageeimm
22 26 24
Prediction (bets]
Prodition
155
1i5
135 Quality
1.30
3300
1550
(a) p 0.9, vary
(b) p 0.8, vary
(c) 0.7, vary B
(d) 2.8, vary 7
Figure 1: Performance of Algorithm I on synthetic datasets. We examine the effects of prediction
quality 3, SBM parameter p. and graph size n. We set ni 100 in and p 0.95
OPT CELRIDA CUMMPT2L
CILPUSA CLYNIT21
CALFU24
CALF-D4
CUMMPT2
CLMMITZ
Algrtnmm3
A.porthm
Agoddam
14
216 2T6 Preastio Quality
14c
Drssition Buakly (tsta)
Piscition Qualit total
Enboslaig Oimrrstin
(a) FB 0, vary 8
(b) FB 414, vary /
(c) FB 3980, vary /3 (d) CORF, vary d
Figure Performance of Algorithm I on real-world datasets. aap show the effect of ,3 on three FACEBOOK subgraphs. ( shows the effect of the dimension d of spectral embeddings on EMAILCORE. Note that a larger indicates higher prediction quality (i.e., a smaller 3).
Table 2: Clustering costs (x 1e3) of Algorithm I with binary classifiers as predictors, compared to its non-learning counterpart. The reported values are averaged over 5 runs.
Dataset
SBM
SBM
SBM
DBLP
Algorithm
(n 1200)
(n = 2400)
(n = 3600)
CKLPU24
105.3
524.8
1 114.3
537.5
Algorithm
35.9
145.6
324.9
247.1
(<e 701), this algorithm has been shown to give high-qualit, solutions in practice. Note that this algorithm requires multiple passes. For fairness, all baselines were implemented with equal effort.
Results on synthetic datasets. Figure shows the performance of Algorithm Ton synthetic datasets. 1) Varying 3 and We first examine the effect of B and (see Figures a (ch). When 3 is small, the cost of our algorithm is significantly lower than that of the (3 + E) approximation non-learning baseline. Even for large 3, our algorithm performs no worse. Notably. we observe that the algorithm of CLMNNT21 I outputs (near-)optimal solution. We attribute this to the fact that the SBM graphs contain many dense components, making them well-suited for this algorithm. Moreover, even when the ground-truth communities become less obvious (e.g., P = 0.7), the clustering cost of Algorithm [ is reduced by up to 26% compared to the algorithm of CKLPU24. 2) Varying Furthermore, investigate whether our algorithm scales well with graph size (see Figure a To clearly present our results, calculate the ratio between the cost of each algorithm and the optimal solution. The result demonstrates that our algorithm performs well consistently as the graph size increases.
Results on real-world datasets. Figure 2 shows the performance of Algorithm on real-world datasets. The results demonstrate that under good prediction quality, Algorithm I consistently
outperforms other baselines across all datasets used. For example, in Figure 2 ab. when 3 ~ 1.2, the average cost of our algorithm 15% lower than that of CLMNPT21 and 22% lower than that of CKLPU24. Besides, in Figure 2 d. our algorithm reduces the clustering cost by up to 14% compared to CLMNPT21. Even in case of poor predictions, Algorithm does not perform worse than its (3 2) aaappooximttionn counterpart without predictions.
Results based on binary classifiers as predictors. Table shows the performance of Algorithm | with binary classifiers as predictors, a more realistic setting. These experiments are performed on three SBM graphs with parameter p 0.95 and varying sizes, as well as the DBLP dataset (a sampled subgraph with 10 100 vertices). The results show that our consistently outperforms its non-learning counterpart across all datasets. For instance, on the SBM graph with 2 400 vertices, Algorithm reduces the clustering cost by 72% compared to CKLPUU2
algorithm
10

---

Acknowledgments and Disclosure of Funding
The work of YD, SJ, and PP is supported in part by NSFC Grant 62272431 and the Innovation Program for Quantum Science and Technology (Grant No. 2021ZD0302901), The work of SL is supported by the State Key Laboratory for Novel Software Technology and the New Cornerstone Science Foundation.
References
[1] Anders Aamand, Justin Y. Chen, Siddharth Gollapudi, Sandeep Silwal, and Hao Wu. Learning- augmented frequent directions. In the Thirteenth International Conference on Learning Repre- sentations (ICLR), 2025.
[2] Anders Aamand, Justin Y. Chen, Huy Le Nguyen, Sandeep Silwal, and Ali Vakilian. Improved frequency estimation algorithms with and without predictions. In Advances in Neural Infor- mation Processing Systems 36: Annual Conference on Neural Information Processing Systems (NeurIPS), 2023.
[3] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- Augmented Mechanism Design: Leveraging Predictions for Facility Location. In 23rd ACM Conference on Economics and Computation (EC), pages 497-528, 2022.
[4] Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation clustering in data streams. Algorithmica, 83(7):1980-22 2017, 2021. Conference version Proceedings of the 32nd International Conference on Machine Learning, ICML 2015.
[5] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1 2008.
[6] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. Comput. Syst. Sci., 144:103545, 2024.
[7] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms, 19(2):1:1111:34, 2023.
[8] Antonios Antoniadis, Marek Eliás, Adam Polak, and Moritz Venzin. Approximation algorithms for combinatorial optimization with predictions. In the Thirteenth International Conference on Learning Representations (ICLR), 2025.
[9] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. Discret. Optim., 48(Part 2):100778, 2023.
[10] Sepehr Assadi, Sanjeev Khanna, and Aaron Putterman. Correlation clustering and (de)sparsification: Graph sketches can match classical algorithms. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.
[11] Sepehr Assadi, Vihan Shah, and Chen Wang. Streaming algorithms and lower bounds for estimating correlation clustering cost. Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems (NeurIPS), 2023.
[12] Sepehr Assadi and Chen Wang. Sublinear time and space algorithms for correlation cluster- ing via sparse-dense decompositions. In 13th Innovations in Theoretical Computer Science Conference (ITCS), volume 215 of LIPIcs, pages 10:1-10:20, 2022.
[13) Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[14] Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, and Zhouzi Li. Graph searching with predictions. 14th Innovations Theoretical Computer Science Conference (ITCS), volume 251 of LIPIcs, pages 12:1-12:24, 2023.

---

[15] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning. 16:89-113,, 2004.
[16] Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, and Weiyun Ma. Correlation clustering beyond the pivot algorithm. In Forty-second second International Conference on Machine Learning (ICML). 2025.
[17] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Almost 3-approximate correlation clustering in constant rounds. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 720-731, 2022.
[18] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li- Ya-Y Tan. Single-pass streaming algorithms for correlation clustering. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages $19-849, 2023.
[19] András A. Benezúr and David R. Karger. Approximating s-t minimum cuts in Ö(n²) time. In Proceedings of the Twenty-Eightt Annual ACM Symposium on the Theory of Computing (STOC), pages 47-55, 1996.
[20] Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. On dynamic graph algorithms with predictions. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
2024.
[21] Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning- augmented maximum independent set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROXRANDOMM) volume 317 of LIPIcs, pages 24:1-24:18, 2024.
[22] Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, and Jara Uitto. (3 + -papproximetee correlation clustering algorithm in dynamic streams. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2861-2880, 2024.
[23] Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Solving the correlation cluster Ip in sublinear time. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.
[24] Nairen Cao, Vincent Johen-Addad Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster linear program for correlation clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1605-1616, 2024.
(25) Nairen Cao, Shang-Fn -En Huang, and Hsin-Hao Su. Breaking 3-factor approximation for correla- tion clustering in polylogarithmic rounds. Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 4154 2024.
[26] Nairen Cao, Shi Li, and Jia Ye. Simultaneously approximating all norms for massively par- allel correlation clustering. In 52rd International Colloquium on Automata, Languages, and Programming (ICALP), LIPlcs, 2025.
[27] loannis Caragiannis and Georgios Kalantzis. Randomized Gearning-Aummntte Auctions with Revenue Guarantees. In Proceedings of the Thirty-Thire International Joint Conference on Artificial Intelligence (IJCAI), pages 2687-2694, 2024.
[28] Deepayan Chakrabarti, Ravi Kumar, and Kunal Punera. A graph-theoretic approach to webpage segmentation. In Proceedings of the 17th International Conference on World Wide Web (WWW), pages 377-386, 2008.
[29] Sayak Chakrabarty and Konstantin Makarychev. Single-pass pivot algorithm for correlation clustering. keep simple! Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems (NeurIPS), 2023.
[30] Moses Charikar, Neha Gupta, and Roy Schwartz. Local guarantees in graph cuts and clustering. In Integer Programming and Combinatorial Optimization 19th International Conference (IPCO), volume 10328 of Lecture Notes in Computer Science, pages 136-147, 2017.
12

---

[31] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. Comput. Syst. Sci., 71(3):300-383, 2005.
[32] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near opti- mal LP rounding algorithm for correlation clustering on complete and complete k-pariite graphs. In Proceedings of the Serte-Seventh Annual ACM Symposium on Theory of Computing (STOC), pages 219-228, 2015.
[33] Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangic and four cycle counting with predictions in graph streams. In 10th International Conference on Learning Representations (ICLR), 2022.
[34] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via leamned predictions. In International Conference Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 3583-3602, 2022.
[35] Vincent Cohen-Addad, Tommaso d' J'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Pani- grabi.
approximation algorithms for maximum cut and related problems. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
[36] Vincent Cohen-Addal Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parot- sidis, and Jakub Tarnawski. Correlation clustering in constant many parallel rounds. In International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 2069-2075 2021.
[37] Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. In 64th IEEE Anmual Symposium on Foundations of Computer Science (FOCS), pages 1082-1104, 2023.
[38] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation clustering with sherali-adams. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 651 651-661, 2022.
[39] Vincent Cohen-Addad, David Rasmussen Lolck, Marein Pilipezuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang. Combinatorial correlation clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1617-1628, 2024.
[40] Riccardo
Sophie Klumper, Guido Schäfer, and Artem Tsikiridis. To trust or not to trust: Assignment mechanisms with predictions the private graph model. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), pages 11 1134-1544 2024.
[41] Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrovic. Pruned pivot: Correla- tion clustering algorithm for dynamic, parallel, and local computation models. In Forty-first International Conference on Machine Learning (ICML), 2024.
[42] Sami Davies, Benjamin Moseley, and Heather Newman. Simultancously approximating all no-ns in correlation clustering. In 51 International Colloquium on Automata, Languages, and Programming (ICALP), volume 297 of LIPlcs, pages 52:1-52:20. 2024.
[43] Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster furd-fulkrrson. In International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 7231-7249 2023.
[44] Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theor. Comput. Sci., 361 (2:31)111721118 2006.
[45] Adela Frances DePavia, Erasmo Tani, and Ali Vakilian. Learning-base algorithms for graph searching problems. In International Conference on Artificial Intelligence and Statisties (AIS- TATS), volume 238 of Proceedings of Machine Learning Research, pages 928-936, 2024.
13

---

[46] Michael Dinitz. Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS), pages 10393-10406, 2021.
[47] Yinhao Dong, Pan Peng, and Ali Vakilian. approximating MAX-CUT. 16th Innovations Theoretical Computer Science Conference (ITCS), volume 325 of LIPIcs, pages 44:1-44:24, 2025.
streaming algorithms for
[48] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-based support estimation in sublinear time. In 9th International Conference Learning Representations (ICLR), 2021.
[49] Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning- augmented k-means clustering. In 10th International Conference on Learning Representations (ICLR), 2022.
[50] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in semi-streaming model. Theor. Comput. Sci., 348(2-3):207-222) 2005.
[51] Paolo Ferragina and Giorgio Vinciguerra. The pgm-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proc. VLDB Endow., (3(8):1162-111) 2020.
[52] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi)eut theorems and their applications. SIAM J. Comput., 25(2):235-255 1996.
[53] Suprovat Ghoshal, Konstantin Makarychev, and Yury Markarychev. Constraint satisfaction problems with advice. In Proceedings of the 2025 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1222-1221, 2025.
[54] Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved Price of Anarchy via Predictions. In ACM Conference on Economics and Computation (EC), pages 529-557, 2022.
[55] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
[56] Holger S. G. Heidrich, Jannik Irmai, and Bjoern Andres. A 4-approximmatio algorithm for min max correlation clustering. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 238 of Proceedings of Machine Learning Research, pages 1945-1953, 2024.
[57] Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the complexity of algorithms with predictions for dynamic graph problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS), volume 287 of LIPlcs, pages 02:1-62:25, 2024.
[58] Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference on Learning Representations (ICLR), 2019.
[59] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS), pages
2021.
[60] Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning- based low-rank approximations. In Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7400-7410, 2019.
[61] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David Woodruff. augmented data stream algorithms. In 8th International Conference on Learning Representations (ICLR), 2020.
[62] Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for Lp samplers, finding duplicates in streams, and related problems. Proceedings of the 30th ACM SIGMOD-SIGACT: SIGART Symposium on Principles of Database Systems (PODS), pages 49-58, 2011.
14

---

[63] Sanchit Kalhan, Konstantin Makarychev, and Timothy Zhou. Correlation clustering with local objectives. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems (NeurIPS), pages 9341-9350, 2019.
[64] Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, and Jakab Tardos. Fast and space efficient spectral sparsification in dynamic streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1814-1833, 2020.
[65] Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 9 of LIPlcs, pages
2011.
[66] Sungwoong Kim. Chang Dong Yoo, Sebastian Nowozin, and Pushmeet Kohli. Image seg- mentation using higher-order correlation clustering, IEEE Trans. Pattern Anal. Mach. Intell., 36(9):171111774 2014.
[67] Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, and Wei Chen. Query-efficient correlation clustering with noisy oracle. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
[68] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1859-1877, 2020.
[69] Silvio Lattanzi, Ola Svensson, and Sergei Vassilvitskii. Speeding up bellman ford via minimum violation permutations. In International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 18584- 18598, 2023.
[70] Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1):2, 2007.
[71] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. httt:///saa..tante stanf edu/ June 2014.
[72] Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David P. Woodruff. Learning the positions in countsketch. In 7 11th International Conference on Learning Representations (ICLR), 2023.
[73] Honghao Lin, Tian Luo, and David P. Woodruff. Learning augmented binary search trees. In International Conference Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 13431-1344 2022.
[74] Quanquan C. Liu and Vaidehi Srinivas. The predicted dynamic model: Taking advan- tage of ML predictions, for free. CoRR, abs/2307 088990, 2023.
[75] László Lovász. Random walks on graphs: A survey. Combinatorics, Paul Erdōs is Eighty, 2(1):1-46, 1993.
[76] Pinyan Lu, Zongqi Wan, and Jialin Zhang Competitive Auctions with Imperfect Predictions. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), pages 1155-1183, 2024.
[77] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 1::44224: 2021.
[78] Julian J. McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems 25: 26th Annual Conference Neural Information Processing Systems (NIPS), pages 548-556, 2012.
[79] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems (NeurIPS), pages 462-471, 2018
[80] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions, page 646-662. Cambridge University Press, 2021.
15

---

[81] Thy Nguyen, Anamay Chaturvedi, and Huy Le Nguyen. Improved learning augmented algo- rithms for k-means and k-medians clustering. In 11th International Conference on Learning Representations (ICIRR), 2023.
[82] Gregory J. Puleo and Olgica Milenkovic. Correlation clustering and biclustering with locally bounded emrors. IEEE Trans. Inf. Theory, 64(6):4105-411 4119, 2018.
[83] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predic- tions. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems (NeurIPS), pages 9684-9693, 2018.
[84] Benedek Rozemberczki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors parametric models. In 29th ACM International Conference on 2020.
Information and Knowledge Management (CIKM), pages
[85] Atsuki Sato and Yusuke Matsui. Fast partitioned learned bloom filter. In Advances in Newral Information Processing Systems 36: Annual Conference on Neural Information Processing Systems (NeurIPS), 2023.
[86] Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Lacki, and Vahab Mirronii. Scalable community detection via parallel correlation clustering. Proc. VLDB Endow., 14(11):2305-2313, 2021.
[87] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. Kwikbucks: Correlation clustering with cheap-weak and expensive- strong signals. 11th International Conference on Learning Representations (ICLR), 2023,
[88] Daniel A. Spielman and Shang-Hur Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, 2011.
[89] Chaitanya Swamy, Correlation clustering: Maximizing agreements via semidefinite program- ming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 526 0666-27,45 2004.
[90] Kapil Vaidya, Eric Knorr, Michael Mitzenmacher, and Tim Kraska. Partitioned learned bloom filters. In 9th International Conference on Learning Representations (ICLR), 2021.
[91] Nate Veldt, David F. Gleich, and Anthony Wirth. A correlation clustering framework for community detection. In Proceedings of the 2018 World Wide Web Conference on World Wide Web (WWW), pages 439-448, 2018.
[92] Chenyang Xu and Pinyan Lu. Mechanism Design with Predictions. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI), pages 571-577, 2022.
[93] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst., 42(1):181-211, 2015.
[94] Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 555-564, 2017.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the claims made, which match our theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: For our theoretical results, point out all assumptions. In our experiments, we empirically evaluate the robustness our algorithms concerning different parameters, such as dataset size.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: The paper provides the full set of assumptions and a complete (and correct) proof for each theoretical result, either in the main paper or the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper fully discloses all the information needed to reproduce the main experimental results. Specifically, the paper provides the full set of pseudocodes for the algorithms (in Section 4.2 Section 3 Appendix C and Appendix [E] and clearly describes
the experimental setting (in Section 6 bjand Appendix G Additionally, the source code used
for the experiments is included in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibilitty In the case of closed-source models, it may be that access to the model is limited in
18

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The paper provides the source code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ https/cccppbccccceeeeeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The paper specifies the experimental setting in Section 6 and Appendix G
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars suitably in figures, see Figure Figure 2 and Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
19

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides information on the computer resources the beginning of Section 6
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neuripss. p inne
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses potential positive socictal impacts in Section T There is negative societal impacts of the work performed.
Guidelines:
20

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: For all code packages datasets used in the paper, we cite the original publications that produced them.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
21

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
22

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips: hect::/:/eerrrps.ccc//ooeeereere Cc//Confereeeees/222///.... for what should or should not be described.
23

---

A Additional technical preliminaries
In this paper, we frequently use graph sparsification techniques, we review the relevant definitions in this section.
fo-samplers. We first review the definition of -s-samllers.
Definition A.1 (fg-sampler 622 Let a E I be non-zero vector and & (0, 1). An Sn-Sampler for a returns FAIL with probability at most 6 and otherwise returns some index such that 2; # with probability [нυpp[æ]] where supp(æ)
{i + 0} is the support of æ.
The following theorem states that to samsarss can be maintained using single pass in dynamic streams.
Theorem A.2 (622). There exists a single-pass streaming algorithmm for maintaining an to- sampler for a non-zero vector a E I" (with failure pribability 8) in the dynamic model using O(log² nllog 5) bits of space.
Cut sparsifiers. Cut sparsifiers 19 are basic notion in graph sparsification.
Definition A.3 (Cut sparsifier (1)). Let H = (VH, Eh, w) be an undirected graph and let s E (0, 1). We say that reweighted subgraph H' (VH, E' w') is an E-cut sparsifier of if for any A VH.
(1 =)0 (A) S 0F (A)) $ (1+=)0=(A))
where (A()) E( Whe and 05 (A) E(uw)EF) who denote the weights of the cut (A, Vn \ A) in H and H², respectively.
Spectral sparsifiers. Spectral sparsifiers 88 are stronger notion than cut sparsifers.
Definition A.4 (Spectral sparsifier (88 Let H = (VH, Eu, w) be an undirected graph and let E E (0, 1). We say that a reweighted subgraph H' (VH, Fn w') an e-spectral sparsifier of H for any æ E R",
61-6)ær Ln < x LH < (1+ LHæ
which is equivalent
(H 3 LH I (1
where Lu and Lg denote the Laplacian matrix И and H', respectively.
It is easy to see that if H' is an e-spectral sparsifier of H, then H' is also an E-cut sparsifier of H. The following theorem states that an e-spectral sparsifier can be constructed using single pass and (( 2n log n.) space in insertion-only streams.
Theorem A.5 ((55). There exists a single-pass streaming algorithm for constructing an e-spectral sparsifier of an undirected graph in insertion-only streams using O(s nn n) space. The algorithm succeeds with high probability.
To construct spectral sparsifiers in dynamic streams, we use the following theorem.
Theorem A.6 (644). There exists a single-pass streaming algorithm for constructing an E-spectral sparsifier of an undirected unweighted graph in dynamic streams using (E=22n) space. The algorithm succeeds with high probability.
Effective resistances. Finally, we review the definition of effective resistances, which are used during the construction of spectral sparsifiers.
Definition A.7 (Efffective resistance). Given an undirected graph G = (V, F,, w) and a pair of vertices u. V. the effective resistance between u and v in G is defined
(I xx)
Ro(u,v) :=
#ER VERIVLLEEE 2=40
T.gac
where LG is the Laplacian matrix of G.
We will use the following lower bound on the effective resistance.

---

Lemma A.8 (75)). Let G EV, be an undirected unweighted graph. For any v E V, we have
RE(u, v) 2 deg(u) deg(v)
B Technical overview
In this section, we provide a high-level overview of our techniques.
B.1 Technical overview of our algorithms for complete graphs
Our algorithms for complete graphs (i.e., Algorithm | and Algorithm 8) rely on the influential PIVOT algorithm by Ailon et al. [5] and the LP rounding algorithm by Chawla al. [32] The PIVOT algorithm begins by selecting a random permutation и over the vertices of the graph. It then iteratively forms clusters by choosing the vertex with the smallest rank according to æ, along with neighbors in the graph. Once a cluster is formed, it is removed from the graph. This process continues until all vertices have been assigned clusters. The LP rounding algorithm first solves an LP corresponding to Correlation Clustering, and then applies a PivoT-based algorithm, using the LP solution to form clusters.
Next, we describe our algorithms. The high-level idea is to incorporate the above LP rounding approach with the "truncated" PivOT algorithms [22 29), where our predictions correspond feasible LP solution in some sense. Specifically, for dynamic streams, we maintain a certain number of fo-samplers during the stream and use them to derive truncated subgraph at the end of the stream. Then we run the PIVOT algorithm and the I.P rounding algorithm on the subgraph respectively and obtain two clusterings. Finally, we output the clustering with the lower cost. For insertion-only streams, we employ two different methods to store at most k neighbors for each vertex during the stream, then run the PIVOT algorithm on the two stored subgraphs. We obtain two clusterings and output the one with the lower cost.
The analysis is non-trivial. even in insertion-only streams. We categorize all clusters into pivot clusters and singleton clusters, and analyze their costs respectively. Our key observation is that the truncated version of the LP rounding algorithm is equivalent the algorithm that first samples subgraph G' according to the predictions and then runs the "truncated" PIVOT algorithms on G'. Our main technical contribution is prove that 1) the cost of pivot clusters produced by the truncated version of the LP rounding algorithm is at most 2.063 times the cost of optimal solution (Lemma 4.5 and Lemma E.7 2) the optimal solution on G' does not differ from the optimal solution on the original graph G by a lot (Lemmal E.9) In this way, our algorithms can keep the space small while achieving an approximation ratio better than 3 under good prediction quality.
B.2 Technical overview of our algorithms for general graphs
Our algorithm for general graphs (i.c., Algorithm 2} is inspired by the O | [)-approximation algorithm by Ahn et al. [4) which sparifies the positive subgraph G+ H+ stores all negative edges E- during the stream, and applies the multiplicative weight update method to approximately solve a linear program. The resulting LP solution then guides influential ball-growing procedure [3 44
on the sparsifier H
The high-level idea of our algorithm is incorporate the above algorithm with pairwise distance predictions, which, in sense, form a feasible LP solution. Specifically, we also maintain a sparsifier H for G+ during the stream and, in the post-processing phase, perform ball- ball-growing H using the predictions as distance metrics. Notably, we no longer need to store E during the stream, leading to improved space complexity.
However, the approximation guarantee of this straightforward approach includes a log n term, whereas our goal is to replace it with tighter log E term. This motivates to further refine the algorithm. Specifically, during the stream, we maintain the sparsifier H as before, while simultaneously storing the arriving negative edges and tracking their space usage. If at any point the space used to store negative edges exceeds Ö(s-2n) we immediately stop storing them. After the stream ends (at which point the sparsifier ready), we proceed with the ball-growing procedure as described above. Otherwise (i.c., if the space used by the negative edges never exceeds the threshold), we run the
25

---

Algorithm 3 Offline version of Algorithm
Input: Graph G = (V, E+), oracle access to 3-level predictor II
Output: Clustering/Partitionn of V into disjoint sets
I: Pick a random permutation of vertices т - (1,....,
2: Initially, all vertices are unclustered and interesting.
3: A vertex marks itself uninteresting if Tu 2 Tu where Tu := g. _ allggn deg"(u) (w) Here, E 1/4)
and universal large constant.
4: Let Gteer be the graph induced by the interesting vertices.
5: C1 <- "RUNNCATEDPIVOT(""" Gstere; πt)
6: C2 <- SRUNCCATEDPIVOTTTTPPEEEE " 7,, IT)
7: 6 arg arg 1,2 2 (C)))
8: return C;
Algorithm 4 TRUNCATEDPIVOTTCC H)
Input: Graph G = (V, E+,, induced subgraph H (VH, EHH) where VH S V and Eh C E*, [l,....,.
permutation क
Output: ClusteringParrtition of V into disjoint sets
1: Let U(I) <- Vn be the set unclustered vertices in Vj--
2: Let 1
3: while U(+)) + do
4: Let (?() be the vertex with the smallest rank.
5: Mark as pivot. Initialize a new pivot cluster 5(1) + {u}.
6: For each vertex v E U(() such that (u, v) E Еμ, add v to S(1)
7: Remove all vertices clustered at this iteration from U(t).
8: t t 1.
9: Each vertex u E VV VH joins the cluster of pivot u with the smallest rank, if (u, v) E E+ and
Te Tu.
10: Each unclustered vertex V creates singleton cluster.
11: return the final clustering C, which contains all pivot clusters and singleton clusters
post-processing phase of the algorithm by Ahn et al. 4 In this way, our algorithm keeps the space small while achieving a near O(log [E apapproximmai under good prediction quality.
C Omitted pseudocodes of Section
In this section, we give the omitted pseudocodes of Section 4 Algorithm and Algorithm 7
Algorithm Algorithm 4 Algorithm
D Omitted proofs of Section 4
D.1 Proof of Theorem
Space complexity. We first analyze the space complexity of Algorithm I For each vertex u E V, we mainly store its rank nu, positive degree dog (u), and 10clog n a. independent lo-samplers. We have the following lemma which states the space requirement of fo-samleers.
Lemma D.I (221). The fy-samplers used in Algorithm require On log n) words of space.
Furthermore, by Theorem A.6
the maintenance of an e-spectral sparsifier in dynamic streams requires
words of space. Therefore, the space complexity of Algorithm is ((s-2n) words.
Approximation guarantee. Next, analyze the approximation ratio of Algorithm We rely the following lemma.
Lemma D.2 (Lemma 2 in (22). The ly- fn-samplers allow us to recover the positive edges incident to all interesting vertices with high probability.
Therefore, Algorithm works with the same set of edges as Algorithm the clustering phase with high probability. This implies that both algorithms return the same clustering with the same
26

---

Algorithm 5 TAWIANCAATEDIPPTTTIHHHIIII
H, H,
Input: Graph G = (V. ), induced subgraph H = (Vr. E1r) where Vnr S V and En S E*, permutation x V. (I,..... .......,,,, .......]... n.,,
oracle access to a f3-evel predictor II
Output: Clustering/Partition of V into disjoint sets
1: Let (a) <- Vμ be the set of unclustered vertices in Vи.
2: Let
3: For any u, V. due [I[(,,)),
4: For any u, V. define Pue := f(dwo).
5: while ((t) * do
6: Let E ( be the vertex with the smallest rank.
7: Mark as pivot. Initialize a new pivot cluster 5(() <- {u}.
8: For each vertex E U add 5(9 with probability Pun) independently.
9:
Remove all vertices clustered this iteration from U
10:
(+ 1.
11: Each vertex E V VH joins the cluster of pivot in the order of π with probability (1 Pwv)
independently, if T. < Tu- 12: Each unclustered vertex E V creates a singleton cluster.
return the final clustering which contains all pivot clusters and singleton clusters
Algorithm CKI.PU-PIVOT(G**)
Input: Graph G+ EV)
Output: Clustering/Partition of V into disjoint sets
1: Pick random permutation of vertices V (I,....n).
2: Let ((()) <- V be the set of unclustered vertices.
3: for prt= wort=1...,.f do
4: Let l + log
5: Let be the t-th vertex in i (i.c., = nT)).
6: Each unclustered vertex v with deg" (v) 2 la creates a singleton cluster.
7:
if E ((t)) then
8:
Mark pivot. Initialize a new pivor cluster S(t) {u).
9: For each vertex E (+)) n U1)), add 51()_
10: Remove all vertices clustered this iteration from U(t)
11:
return the final clustering C, which contains all pivot clusters and singleton clusters
probability. On the other hand, if the high probability event of Lemma D.2 does not happen, then | produces clustering of cost at most ( which leads to an additive 1/ poly (n) term to the expected cost of Algorithm T compared to that of Algorithm This preserves the approximation ratio if OPT + 0.
We also need the following lemma which shows that the estimate costa(C) well approximates the cost of any clustering C of G.
Lemma D.3 (18)- Let 10. For any clustering C of V. the cost costa(C) is approximated by the estimate cC) = Ecee (10 + ((C) - Eneo deg up to multiplicative factor of =1 with high probability.
Therefore, Theorem 1.3 follows from Lemma 4.1 bound.
Lemma D.2
D.2 and Lemma D.3 by applying the union
D.2 Proof of Lemma
The proof is similar to that of Lemma 4.2 cases, the singleton clusters Van the same (with the same probability). Then we show that the randomized pivot-based algorithm runs on the same subgraph G [V) Vanl (with the same probability) in both cases, therefore outputting the same pivot clusters (with the same probability..
The proof idea is as follows: we first show that in both
Consider vertex u that unclustered the beginning of iteration (S n.), and becomes singleton cluster due Line 8 of Algorithm PAIRWISEDISS. By definition, is the smallest integer such that
27

---

Algorithm 7 PAIRWISEDISS(G II)
Input: Graph G+ = (V, E+), oracle access to 3-level predictor II Output: Clustering/Partition of V into disjoint sets
1: Pick random permutation of vertices π V - m..
2: For any u, U V. dyu [I( v).
3: For any u, U E V. define Puv := f(dwe).
4: Let (()) t V be the set of unclustered vertices.
5:
for
=rtt do
6: Let f E no
7:
Let u E be the t-th vertex in и (i.c.. == kT). 8: Each unclustered vertex o with deg (v) l creates singleton cluster.
9:
if u ((t)) then
10:
Mark u as pivot. Initialize a new pivor cluster S + {u}.
11:
For each vertex v E U add to ()() with probability (1 Puv) independently.
12:
Remove all vertices clustered this iteration from U(())
13:
return the final clustering C, which contains all pivot clusters and singleton clusters
deg*(u) (u) 2 5 nllog and hence t = [Tu]- Since Tu. we have deg*(u) (u)
logg which Su
corresoonds to u becoming uninteresting in Algorithm Since u is in singleton cluster, it did not join any pivot cluster, implying that for any vertex v & u, either (1) The 2 t, or (2) the event that is pivot and joins the cluster of satisfying Te t does not happen. This is equivalent to saying that the event that u joins the cluster of pivot u satisfying To < Ta does not happen, since x, is an integer. By Line II of Algorithm TRUNCATEDPIVOT WITHTREDD creates singleton cluster in Line Algorithm 3 with the same probability) as well.
Then u must be marked uninteresting (implying Tu 2 Tw), and u can neither be pivot nor join the cluster of pivot v satisfying Ty Tu. By definition of Ta. iteration [uu] is the smallest iteration such that deg+(u)
Now consider vertex that creates singleton cluster in Line 6 of Algorithm 3
log This implies that is unclustered at the beginning of iteration [T,] in [Tu Algorithm PAIRWISEDISS, and forms a singleton cluster that iteration (with the same probability).
Since the vertices forming singleton clusters are the same in both cases (with the same probability). the subgraph induced by the remaining vertices G [V \ V is the same (with the same probability) The same randomized pivot-based algorithm runs on G+(V Vsin] in both cases, which implies that the pivots will be the same (with the same probability). Finally, we observe that in both cases, non-pivot vertex u joins the cluster of pivot e such that n. < Ta in the order of x with probability - Puop independently. Hence, the pivot clusters are the same (with the probability).
D.3 Proof of Corollary 4.6
The analysis in 22 shows that the cost of good edges can be charged to the pivot clusters. The following lemma shows that the cost of bad edges can also be related the pivot clusters, allowing us to bound the overall clustering cost.
Lemma D.4 ((22). Let E E (0, 1/4). Let P denote the cost of pivol clusters, and let W denote the cost of the final clustering, then E[W] = EEP + [rra]] S (1 [ + A where == c/2 2/2-1
Then Corollary 4.6follows from Lemma 4.3 Lemma and Lemma 4.5
D.4 Proof of Lemma 4.1
Lemma 4.1 follows from Lemma 4.4 and Corollary 4.6 Note that Lemma we can substitute
e' : 12c, where can be arbitrarily small. If OPT > 1, then Efcosty (C1 < (3 12 OPT,
which gives a (3 + e') (3)) approximmtion in expectation. OPT = 0, then Elcost (C1) = 1/ (n)y
Similarly, in Corollary 4.6 we can substitute e' 8.248e.
28

---

E Our algorithm for complete graphs in insertion-only streams
In this section, we propose algorithm for complete graphs in insertion-only streams. This algorithm is different from our algorithm for dynamic streams (Algorithm D.. while achieving the same approximation guarantee with improved space complexity. is also simpler and more practical than the existing 28a7-approximation algorithm [39], which is based on local search and requires enumerating a large number of subsets of constant- size set, making it quite impractical.
Theorem E.1. Let (0, 1) and B 2 1. Given oracle access to a ß-level predictor, there exists single-pass streaming algorithm that, with high probability, achieves an expected (min(2.06,,3 3} + -)approxximation for Correlation Clustering complete graphs in insertion-only streams. The algorithm uses ( 2n log n) words of space.
E.1 Overview
We first briefly describe a single-pass (3 + -ppaproxiitttoon streaming algorithm by Chakrabarty and Makarychev [29]. Initially, the algorithm adds a positive self-loop for each vertex and picks The rank of u is denoted as Tu. Then it scans the input stream. For each vertex, the algorithm stores at most k positive neighbors with lowest ranks, where is a constant. Subsequently. it runs the PIVOT algorithm [5] on the stored graph, where it picks pivots in the order of x. Finally, puts unclustered vertices in singleton clusters.
random ordering π V + {l,.... n2).
Our main idea is to incorporate the above algorithm with the algorithm proposed by Chawla et al. 32]
Specifically, our algorithm employs two different methods to store at most k neighbors of each vertex. The first method is the same as the algorithm proposed by Chakrabarty and Makarychev [29] and the second method is adapted from the work of Chawla al. [32], which adds neighbors with
probabilities determined by predictions of pairwise distances. Finally, we obtain two clusterings
(denoted as Ci and C2) and output the one with the lower cost. Similar to Algorithm |
here we also
need to use the graph sparsification technique 65 to approximate the cost of a clustering.
E.2 The algorithm
Recall that we have oracle access to 3-level predictor 11, which can predict the pairwise distance duv E [0, 1] between any two vertices u and v in G.
Based on the predictions, we propose a single-pass semi-streaming algorithm which works in insertion- only streams. The pseudocode given in AlgorithmB We first pick random permutation of vertices V + f1, n). For each vertex u E V, we initialize two priority queues A(u) and B(u). each with a maximum size capped at k; where k a constant, Initially, we add u to both queues. During the streaming phase, we employ two distinct methods to retain at most k neighbors of each vertex. Specifically, for each edge (u, v) E E the stream, if (u, v) is a positive edge, we add u to A(v) and add A(u). Additionally, regardless of whether (u, v) is positive or negative, we add u to B(v) with probability (1 (L-Pue) and add v to Buu) with probability (1 Puw). where Pue = fdwe) and duo= 11(u, v). Note that if the size of any queue exceeds k then we remove the vertex with the highest rank from the queue. That is, A(u) maintains at most i positive neighbors of u with lowest ranks, while Buu) contains most i neighbors (not necessarily positive) of u with lowest ranks, the inclusion of which is probabilistic. Note that we define the rank of a vertex as its order in the permutation n, e.g., Tu is the rank of u.
After the streaming phase, we run Algorithm 9 on the truncated graphs induced by both sets of priority queues, i.e., (A(u)) and (B(4) Juer. Specifically, for each vertex u picked in the order of π, we determine the cluster to which u belongs. We try to find the vertex v with the lowest rank in the queue of such that is a pivot or u singleton and place it in a singleton cluster. Otherwise, we assign u to the cluster of u. In particular, if v = then we mark u as a pivot. Finally, we obtain two clusterings, each corresponding set of priority queues. We output the clustering with the lower cost.
such vertex u does not exist, then we mark
It is worth noting that in the final step. the cost of a clustering cannot be exactly calculated, as our streaming algorithm cannot store the entire graph. To overcome this challenge, we borrow the idea from the work of Behnezhad et al. [88 and utilize the graph sparsification technique [65] to estimate the the cost of a clustering. Specifically, during the streaming phase, we maintain an E-spectral sparsifier H+ for G using the algorithm of Theorem A.5 We also maintain the
29

---

Algorithm 8 An algorithm for complete graphs in insertion-only streams
Input: Complete graph G EV, -VEE== as an arbitrary-order stream of edges, oracle access
to a 3-level predictor II, integer
Output: Clustering/Partttion of V into disjoint sets
Pre-processing phase
1: Pick a random permutation of vertices т V (I....,m.
2: For any u, V. duv II(u, v).
3: For any u, U E V, define Puv == f(dw)).
4: for each vertex E V do
5: Create a priority queue A(u) with a maximum size and initialize A(u) < {u}.
6: Create priority queue B(u) with maximum size of & and initialize B(u) {u].
7: deg"(u)
(u) +
Streaming phase
8: for each edge
(u, v) do
9:
if e = (u, v) E E then
10:
Add to A(v). Add o A(u).
11:
[A(w)] > & (resp. IA(b)] k) then
12:
Remove the vertex with the highest rank from A(u) (resp. A(v)).
deg+(u) deg
deg (u) +, deg (u) k deg (u) +
14:
With probability (1 Puo). add to B()) and add v to B(u).
if [B(u]] (resp. [B(v] > k) then
16:
Remove the vertex with the highest rank from (u) (resp. B(v)).
17:
Maintain E-spectral sparsifier H for G+ using the algorithm of Theorem A.5
b Post- Post-processing phase
18: C1 CLUSTER(( V n, (A(u) A(u)JeEV) lev))
19: C2 + CLUSTER n., (B(u) Jue))
20: costo(()) + Σ Ccec (g0 (C)+ + (10)
E deg (u))
21: (C2) + (2 (+)+ ((0)
(C)
Enec deg (u))
22: i arg 1 (C.st
23: return C,
Algorithm 9 CLUSTER vV, (T(w))uev)
Input: Vertex set V. permutation of vertices V (l........ truncated neighbors of each vertex (T(u)
Output: Clustering/Partttion of V into disjoint sets
1: for each unclustered vertex u E V chosen in the order of π do
2: Find the vertex Tuu) with the lowest rank such that a pivot or v u, ie.. V f
arg min,g7((.) TTo is pivot or u u== u). if such a vertex e exists then
3:
4:
Put in the cluster of u. if then
5:
6:
Mark u as pivot.
7:
else
8: Put u a singleton cluster. Mark u as a singleton.
9: return the final clustering C
positive degree deg+t (u) for each vertex u. Then can approximate the cost of clustering up to (1 + multipliicaa error with high probability, by the guarantee of Lemma D.3
E.3 Analysis of Algorithm g
Space complexity. For each vertex u E V, we mainly store rank Tas positive degree deg (u). and at most 2k vertices. As we will see, we set k = O(1/e). Furthermore, by Theorem A.5 the maintenance of an e-spectral sparsifier in insertion-only streams requires O logn) n) words of space. Therefore, the total space complexity of Algorithm 8 is 0 log n) words.
30

---

Algorithm 10 CM-PIVOTTG,,
Input: Complete graph -V. -E-). integer kt
Output: Partition of vertices into disjoint sets
1: Let F(I) < V be the set of fresh vertices.
2: Let Ua) V be the set of unclustered vertices.
3: For each vertex E V. initialize counter K((1) (u) +- 0.
4: Let t-1,
5: while F(1) * 0 do
6: Choose a vertex w+() F()) uniformly at random.
7: if (()( E ( then
8:
Mark w(() as a pivot. Initialize new pivor cluster 5(t) t- {w(t)).
For each vertex v E (w((t) (tt), add v to S(t).
9:
else
11:
For each vertex E (w n U let (v) + ((((()) ) + Subsequently, all
vertices with ((++)((v) k are put into singleton clusters.
12: Let F(++)) <- F(O) \\r {w and remove all vertices clustered at this iteration from (7())
13:
Letle
14:
return the final clustering C, which contains all pivot clusters and singleton clusters
Correctness. Since the final clustering returned by our algorithm is the one with the lower cost between the two on the truncated graphs, we begin by analyzing their costs. Similar to the analysis of Algorithm [ for ease of analysis, we separately examine the approximation ratios of the corresponding offline versions (Algorithms CM-PIVOT and PATRWISEDISS2) that equivalently output these two clusterings.
Algorithm CM-PIVOT (2).. This algorithm proceeds in iterations. Let F(t) denote the set of fresh vertices and ((+)) denote the set of unclustered vertices at the beginning of iteration Additionally, we maintain a counter K<()) (u) for each vertex V. Initially, all the vertices are fresh and unclustered, with the counters set to uniformly random. If (t) is unclustered, then mark it as pivot and create cluster S(() containing (t) and all of its unclustered positive neighbors. Otherwise, we increment the counters for all unclustered positive neighbors of (!) Subsequently, vertices whose counters reach the value of k are assigned to singleton clusters. At the end of iteration f. we remove w(t) from F()) and remove all vertices clustered in this iteration from (+), Then the algorithm proceeds to the next iteration. Finally, output all pivot clusters and singleton clusters. The pseudocode is given in Algorithm T0
iteration t, we pick a vertex w(() from the set of fresh vertices F()
Algorithm PAIRWISEDISS2. This algorithm has oracle access to a 3-level predictor II (
[o, 1]. This algorithm closely resembles Algorithm CM-Pivor, differing in the following two aspects: (1) If wn (+t), then we create a cluster 5()) containing (* and add all unclustered vertices ((t) with probability (1 Pew(r)) independently, where Pew(t) f(dew()) and dew()) l1(,, ((t)). (2) If w(()) & ((t), we increment the counters for all unclustered vertices with probability (1 ). The pseudocode is given in Algorithm
E.3.1 Algorithm Bas combination of Algorithms CM-PivoT and PAIRWISEDISS2
(((+) + t, where We define permutation for Algorithms CM-PIVOT and PAIRWISEDISS2 ((()) is the vertex picked at iteration of Algorithms CM-PiVOT and PAIRWISEDISS2. Obviously, a uniformly random permutation over V. Therefore, we can also view Algorithms CM-Pivor and PAIRWISEDisS2 from an equivalent perspective: at the beginning of each iteration t, choose a vertex (() in the order of π. We have the following lemmas.
Lemma E.2 (Lemma 2.1 in (2)). Algorith S Algorithm CM-Pivor the same permutation n. then Algorithi CM-PIVOT and Line 18 of Algorithm & output the same clustering of V.
Lemma E.3. If Algorithm & and Algorithm PAIRWISDDISS2 use the same permutation and predictions (dha Ju, then Algorithm PAIRWISEDiSS? and Line 19 of Algorithm output the same clustering of V with the same probability.
31

---

Algorithm 11 PAIRWISEDISSIIG, 11,
Input: Complete graph G = (V. E -E-). oracle access a ff-level predictor II, integer k:
Output: Partition of vertices into disjoint sets
1: Let F(I) < V be the set of fresh vertices.
2: Let Ua) V be the set of unclustered vertices.
3: For each vertex E V. initialize a counter K (u) +- 0.
4: For any u, U V. due- [T,,, v).
5: For any u, E V, define Puv == f(dav).
6: Let f-
7: while [((t 40 do
8: Choose a vertex w(() E F()) uniformly at random.
9: if w(()) E ((t) then
10:
Mark w(() as pivot. Initialize new pivot cluster 5(1) <- (w'0).
11:
For each vertex v E UW,,, add to ((t) with probability (1 - Pow(o) independently.
else
13:
For each vertex E U+0)) let ((+))(v) + (v) - with probability (1 - ( ) independently. Subsequently, all vertices o with (x)+)(()) = k are put into singleton clusters.
14:
Let ((++1) r(()) \ {wl and remove all vertices clustered at this iteration from UT().
15:
Let 4 L 1.
16:
return the final clustering C, which contains all pivot clusters and singleton clusters
Proof. The proof is similar to that of Lemma E.2 Suppose that Algorithm 8 and Algorithm PATR- WISEDIss2 use the same permutation and predictions )dwo u..V,, we want to prove that for each vertex u E V. with the same probability, in both clusterings returned by Algorithm PAIRWISEDISS2 and Line 19 of Algorithm g u is either assigned to the same pivot, or u is placed into a singleton cluster.
We prove by induction on the rank Tu- Suppose that all vertices u with N. < Tu are clustered in the same way with the same probability. If is put into singleton cluster in the clustering returned by Line of Algorithm 8] then there must exist & vertices added to B(u) probabilistically. and their ranks are lower than π.. None of the vertices in ((u) are pivots. Since both algorithms use the same and [due),,vev
Algorithm PAIR these h vertices will cause the counter of u to increment 1: times probabilistically. Therefore, is also placed in a singleton cluster in the clustering returned by Algorithm PAIRWISEDISS2. And vice versa.
In Algorithm 8 if there are any pivots in Buu) (or u itself), then u will be assigned to the pivot with the lowest rank (denoted as v). We have Ty S Ta and has been added B(u) probabilistically. In Algorithm PAIRWISEDISS2, with the same probability, is marked as pivot and u is added to the cluster of And vice versa.
Therefore, Algorithm PATRWISEDISS2 and Line 19 of Algorithm cluster u in the same way with the same probability.
E.3.2 The approximation ratios of CM-PivoT and PAIRWISEDISS2
In order to analyze the approximation ratio of Algorithm it suffices to analyze Algorithms CM- PIvOT and PAIRWISEDISS2 respectively. We follow the analysis framework in the work of Chakrabarty and Makarychev [29]. We categorize all iterations into pivor iterations and single- ton iterations. Both iterations create some clusters. Consider iteration i of both algorithms. If wi()) E U(!), then iteration t is a pivot iteration; otherwise, it is singleton iteration. We say that an edge (u, v) is decided at iteration if both u and were not clustered at the beginning of iteration t (i.e., u, v E U(()) but at least one of them was clustered iteration decided, we can determine whether it contributes to the cost of the algorithm (i.e., the number of disagreements). Specifically,
Once an edge (u, v) is
if (u, v) E E+ then it contributes to the cost of the algorithm if exactly one of and is assigned the newly created cluster S(t); if (u, v) E then it contributes the cost of the algorithm if both u and v are assigned to the newly created cluster 5(1).
Let E(9 denote the set of decided edges at pivot iteration l. Specifically, E(O {(u, v) E E u, U10;; s(i) or s(0). Let p(() denote the cost of decided edges at pivot iteration t. We call the
32

---

clusters created in pivot iterations pivot clusters. Let P denote the cost of all pivot clusters. Therefore,
P = Et is pivor iteration p(a, Let S denote the cost of all singleton clusters. Therefore, the cost of the algorithm is equal to P + S.
Analysis of Algorithm CM-PIVOT. We have the following guarantees of Algorithm CM-PIVOT.
Lemma E.4 ((29). Let P1 denote the cost of pivot clusters returned by Algoritim CM-PIVOT, then E[Ai] I 3 OPT, where OPT is the cost of the optimal solution on G.
Lemma E.5
22 Let Si denote the cost of singleton clusters returned by Algorithm CM-PIVOT, then E|S < ОPT.
Therefore, we can bound the cost of the clustering returned by Line 18 of Algorithm g
Lemma E.6. Let P1 and S1 denote the costs of pivot clusters and singleton clusters, respectively, returned by Algorithm CM-PIVOT. Let C1 denote the clustering returned by Line 78 of Algorithm g Then E (ootta = E 1 + S < (3 6 OPT.
Proof. Lemma E.6 follows from Lemma
E.2 Lemma E.4 and Lemma
E.5
Analysis of Algorithm PAIRWISEDISS?. Next, we analyze the approximation ratio of Algo- rithm PAIRWISEDISS2. We first bound the cost of pivot clusters.
Lemma E.7. Let Pg denote the cost of pivot clusters returned by Algorithm PAIRWISEDISS2, then B[P]| S 2.06,3 OPT.
Proof. The key observation is that the pivot iterations Algorithm PAIRWISEDISS2 are equivalent to the iterations of 2.06- -.p--approoiitaiinn LP rounding algorithm by Chawla et al. [32] given that w(()) is unclustered (i.e., (0 E U the conditional distribution of ((( is uniformly distributed in U71), and the cluster created during this iteration contains wn(t) and all unclustered vertices added with probability (1 Po Therefore, we can directly apply the triangle-base analysis in the work of Chawla et al. [32] Define I. := (u. due + > (a.))E (1 due). Since the predictor
is B-level, by Definition 3.1 have that the predictions (duo)uree satisfy triangle inequality
and L < OPT. It follows that for all pivot iterations t, E[P( < 2.06 (() where P!
is the cost induced by the pivot cluster created at iteration t, and L = Σ [(w,)eEEtgg duv
Bn (1 d.v). By linearity of expectation, we have [[]]]
E >>
iteration p(()
Ee a pivot iteration [ < 2.06 S 2.063 OPT.
Then we bound the cost of singleton clusters returned by Algorithm PAIRWISEDISS2, denoted as S2 We highlight that this part is non-trivial. Different from the analysis in the work of Chakrabarty and Makarychev (29] which designs potential function and shows that it is submartingale, we consider an algorithm equivalent to Algorithm PAIRWISEDISS2. In this algorithm, subgraph G' := (V, E E"") where each edge (u, v) E E is added to E* with probability (1 - Pue) and added E' with the remaining probability. Then we perform Algorithm CM-PIVOT on G'. In other words, we first preround the 3-level predictions Ju,vvv to obtain a new instance G' and then Algorithm CM-PIVOT on G' where the positive edges are induced by the predictions. The pseudocode is given in Algorithm 12
construet random
We first show the equivalence of Algorithm PAIRWISEDISS2 and Algorithm PAIR-
WISEDISS2 DODEDISSWIIIIPPEROUUDDI
Lemma E.8. If Algorithm PAIRWISEDISS2 and Algorithm www.:SSSDDSS2WWHPPRRRRROOO
use the same permutation π and predictions {dae hu,ev, then they produce the same clustering with the same probability.
Proof. The randomness in both algorithms comes from two sources: (1) the uniformly random permutation vertices and (2) the probability that each vertex adjacent w(t) will join the cluster of (t( or increment its counter. The main difference between the two algorithms lies in the order in which the two sources of randomness are revealed: Algorithm PAIRWISEDISS2 can be viewed as choosing at the beginning and then performing iterations, where the randomness of all edges incident
33

---

Algorithm 12 PAIRWESDDSSVVVIPPRROONNNNGG
Input: Complete graph = (V. E -EE). oracle access f-level predictor II, integer k:
Output: Partition of vertices into disjoint sets
1: For any u, U V, dua [[ v).
2: For any u, 17 V, define Puv f(dwv).
3: Ex+ +0..
4: for each edge (u, v) E such that Pae < 1 do
5: add (u,)) to Ex+ with probability (1 - Puv)
6: E" + E
7: C CM-PIIOOTG' == (V,
EV E ),
8: return C
to ((() is revealed after (*)) is chosen. contrast, Algorithm
reveals the randomness of edges at the beginning, uses this information construct new instance, and then performs Algorithm CM-PIVOT on the new instance, where the randomness for и is revealed.
Note that the order of randomness does not affect the output. Therefore, if both algorithms the same ı and {duv ea,e,, then they will output the same clustering with the same probability.
Therefore, we can directly apply Lemma E.5 to G'. To this end, we first show that G' still well preserves the Correlation Clustering structure of G. by showing that the optimal solution on G' does not differ from the optimal solution G by a lot.
Lemma E.9. [ < (2, + 1) OPT, where OPT and OPT' are the costs of the optimal solutions on G and G', respectively.
Proof. Let C* be the optimal clustering on G with cost OPT. For any u, v E let z {0, indicate whether and are in the same cluster or not in C*. Specifically, if and are in the same cluster in C*, then zuv- = 0: otherwise, auo Let C be the optimal clustering on G' with cost OPT' Then we have
EOPTT = Elcosto (C"*) & E/costo (C*)]
=E (u,0)EE+
1x - Puv) + (1 x Puol +
Σ
[x Puv) + (1 aut
(u,v)EE-
Σ
Σ
(1 xato) +
Σ
Pun(1
2x + E
(1 Pur) 1)
(u,0)EE+
(u.)EE
(u,e)EE+
(u,D)EE
< +
Pun
(1 Duv)
(++
(u.N)EE-
+
2d
Σ duv) S (1+288) OPT,
(
(,,e)E
where the first step follows from coster (C = OPT', the second step follows from that C** the optimal clustering G", the third step follows from our construction of G'. the fifth step follows from
E(unet 2 Σ (x,)EE- (1- (1-2 2.n)) = OPT and (u,)) Puv 2x > (u, (1
Par) (2x" 1) E (u.))EE Puv + +aa ((,)))e (1 Pav) since 1 2x E (-1,11 the sixth step
f-
follows from our choice for Par, and the last step follows from E(.,))E++ 2d E(
d S 2(2, duv E(, (1 duv)) < 23 OPT.
Now we are ready to bound the cost of singleton clusters and, consequently, the final clustering returned by Algorithm PAIRWISEDISS2.
Lemma E. Let S2 denote the cost of singleton clusters returned by Algorithm PAISWISEDISS2, then (E(2) S
< k-1 OPT.
6(29+1)
Proof. By Lemma E.5 OPT.
Lemma
E.8 and Lemma E.9
have E[Sa] k-I
EOPT 6(28+1)
34

---

Corollary E.11. Let C2 denote the clustering returned by Line 19 of Algorithm g
then
c S2] - (2.063 + 6(26+1)) OPT.
Proof. Corollary E.11 follows from Lemma
Lemma
E.7 and Lemma E.
Proof of Theurem E.7
Theorem
follows from Lemma E.6
Corollary
and Lemma D.3
Remark, The reason our sampling-based approach works is mainly due to the fact that the rounding algorithm by Chawla et al. [32] equivalent to the algorithm that first samples a subgraph G' according to the prediction oracle and then runs the PiVOT algorithm on G'. Therefore, if Correlation Clustering algorithm A has a similar feature, i.c., can be viewed as procedure that first obtains core of the original graph (by using LP or other methods), and then applies the PIVOT algorithm on the core, then we can get roughly the same approximation ratio as A.
Omitted details of Section 5
F.1 Proof of Lemma 5.3
The positive cost C2 on H is
cost (C2) = cost (C2)
2 Σ
:h (C)
CEC₂
$ 2
In(n + 1) Σ
vol (C)
CEC₂
3
In(n 1)
Σ
duo
+
V*
2
(u,o)EE
CEC,
3ln(n +1).
Σ
(u,o)E
where the second-to-last step follows from the triangle inequality, and the final step uses the fact that V E(wo)e who and [Ca| S n.
F22
Proof of Lemma 5,4
Since
Σ (1 duv) Σ
Σ
-uvd)) 2 Σ Σ
11_2 2
1
(M,))EF-
CeCa (u,e)EE-=,,,ee s0
CECs (u,n) E suvec
(w, E ;U C),
3
CECa
where the second step follows from duv I 3/4 by triangle inequality, we have
cost 1 (C2) =
(u, v) : u Σ (1- dur).
CEC₂
(u.e)EE
F.3 Proof Lemma 5.5
To analyze the cost of C2 on the original graph G, we first show that the positive cost of C2 on G is close
to that on H. Since H+ is an e-spectral sparsifier G+, we have cost (C2) = 2/2 Ecec, 0c+ (C) S
1 Ecec, I-c 0 (C) = - cost + (C2). Therefore, by Lemma 5.3 and Lemma 5.4 the cost of C2 on G
1
costa((2)) (C2) + (C2) cost + cost z (C2) 1-s
cost (C2) + cost H (C2)
35

---

31n(n + +1)
Σ
Wundur +3
Σ
duw))
(u
(u,e)EB
53 (3+4:) In(n 1)
Σ
Wun +3
Σ
(1 dun)
(u.e)EBj
(u.N)ER-
$ + (3) In
Σ
woo duo +
Σ (u,e)EB
(1 - dwo)
= 0 [ET)) OPT,
(u.o)EET
where the second step follows from (Cst cost (C2), the third-to-last step uses the inequality
3 < 3 + 4s for any E (0, 1/4) and the last step follows from the definition of the adapted 3-level I-:
predictor and the fact that | n.
F,4 Results under bounded degree graphs
the input graph has bounded degree, then the adapted 3-level predictor can be relaxed to the standard 3-level predictor.
Corollary F.1. Let (0, and d, 2 Given oracle access B-level predictor, there exists a single-pass streaming algorithm that, with high probability, achieves an Ollog | 3d)- approximation for Correlation Clustering on general graphs with maximum degree d in dynamic streams. The algorithm uses (g))2)) words of space.
Proof. Recall that the e-spectral sparsifier H is constructed using the algorithm of Theorem A.6 sestancee-asse sampling [64]. Specifically, each edge (u, v) in the
which is based effective original graph G+ is sampled with probability Pav Clan [u, v), where C is a sufficiently large constant. For any edge (u, v) E Et, its weight is assigned by w'u Puu
S (o
Since the maximum degree of is d, by Lemma A.8 we have Ro(u, 2 ( (eg(uu) deg(o)
for all v E V. It follows that w'o S
2dd
for all (u, v) E Et.
Clan
Then it suffices to follow the proof of Lemma 5.5 to obtain
3 31 1)
(C2) I
Σ
w/ duo +3
Σ
(1 dwv)
1-E
(u.))E
(U,D)E
3: (nn
Σ
duo +3 Σ
(1 - duv)
(1-e)Clnn
(u.))EFt
(u,)EE--
I max
(1 ()+
(1+
1
3
Σ
duo +
Σ (u.ejE
(1 dlov)
C
n alnn)
(u,o)EE+
= =(dd) OPT,
where the third step uses the fact that 3c
I-E S. + for any E 1/2), that
In(n+]]
S + Inn for
Inn sufficiently large and that E+ C E+; and the last step follows from the definition of the 3-level predictor (Definition B.Ib.
Combining Lemma 5.2 with the above analysis yields Corollary F.1
G
Additional experiments
In this section, we provide detailed descriptions of the datasets and predictors used in the experiments. Additionally, we present further experimental results.
G.1 Detailed descriptions of datasets
In this subsection, we give a detailed description of the real-world datasets used in our experiments. Recall that we use EMAILCORE (70 94], FACEBOOK (78), LASTFM (84), and DBLP 9 from the
36

---

Table Statistics of datasets. Here, and m denote the number of vertices and edges in the original datasets.
Datasets
7
171
EMAILCORE
1005
25 571
FACEBOOK
4.0
324
LASTEM
7624
27 808
DBLP
317080
1 049 866
Stanford Large Network Dataset Collection Table
71 We provide basic statistics about these datasets in
EMAII.CORE is a directed network with 005 vertices and 25 571 edges. This network is constructed based email exchange data from large European research institution. Each vertex represents person in the institution. There is a directed edge (u, v) in the network if person u has sent at least one email to person v.
FACEBOOK an undirected network with 4 039 vertices and 88 324 edges. This network consists of friend lists of users from Facebook. Each vertex represents user in Facebook. There is an undirected edge (u, v) in the network if and are friends. Due to the computational bottleneck of solving the LP, we only use its three ego-networks: FB 0 (n 333, m 5 038), FB 414 (n 150, 3 3866),
FB 3980 (7 52, m 292).
LASTEM is undirected network with 7 624 vertices and 27 806 edges. This network is social network of LastEM users, collected from the public API. Each vertex represents LastFM user from an Asian country. There is an undirected edge (u, v) in the network if and are mutual followers.
DBLP an undirected co-authorship network with 317 080 vertices and 049 866 edges. Each vertex represents an author. There is an undirected edge (u, v) in the network if u and v publish least one paper together.
tround-truth communities are defined based on publication venues: authors who have published in the same journal or conference belong to the same community. For our experiments, we use sampled subgraph consisting of 10 vertices.
Remark. We treat the original edges in the datasets as positive edges and non-edges as negative implicitly. (For datasets used in experiments where binary classifiers employed predictors, the interpretation of positive and negative edges differs slightly. See Appendix G.2 for details.) For directed networks, convert all directed edges into undirected edges. We highlight that since we consider labeled complete graphs in the experiments, the number of edges scales quadratically w.r.t. the number of vertices, which leads to non-trivial instance sizes.
G.2 Detailed descriptions of predictors
Noisy predictor. We use this predictor for datasets with available optimal clusterings. We form this predictor by performing perturbations on optimal clusterings. Specifically, for any two vertices u, E V. u and v are in different clusters in the optimal clustering, then we set the prediction d to be cn. otherwise εo. where én E (0, 0.5). For synthetic datasets with p >> 0.9, we can assume that the ground truths are also optimal solutions. For other datasets, we use the powerful LP solver Gurobi [55] to get the optimal clusterings.
Spectral embedding. We use this predictor for EMAILCORE and LASTEM. first maps all the vertices to d-dimensional Euclidean space using the graph Laplacian, then clusters all the vertices based on their embeddings. For any two vertices u, E V, we form the prediction duy to be
1 (z....)) where Fu, E I are spectral embeddings of u and v, and (æa, 2.) is the dot 1
product of T. and V.. Note that larger d indicates higher-quality predictor.
Binary classifier. We use this predictor for datasets with available ground-truth communities. This predictor is constructed by training binary classifier (based on an MLP model) to predict whether two vertices belong to the same cluster using node features. this setting, the goal of Correlation Clustering aligns with that of community detection by treating edges between two vertices in the same
37

---

CV23
1.00
Ouoorin Got
CUMMPT21
D7T
CMCS
CUMMITTLL
Ageimm
Prodiction
13
155
Prodction
123
Erbedding
6010 oide 280 4010
Exbedding
(a) FB O, vary 3
(b) FB 414, vary
(c) EMAILCORE, vary d
(d) LASTEM, vary d
Figure 3: Performance of Algorithm 8 on real-world datasets. a bb show the effect of prediction
quality 33 on two FACEBOOK subgraphs, where we use noisy predictors ( (d) examine the effect
of the dimension d of spectral embeddings on SMMAT.CORE and LASTFM, where we use spectral embedding as the predictor. We set = 25 for a = 15 for (b.
for (c). and 50 for (d).
Table 4: Clustering costs (x le3) of Algorithm 8 with binary classifiers predictors, compared to its non-leaming counterpart. We set parameter 75 across all datasets. The reported values are averaged over 5 runs.
Dataset
SBM (n
SBM
SBM
DBLP
Algorithm
1200)
(n = 2400)
(n
3600)
CM23
99.3
385.7
901.6
236.4
Algorithm
35.9
155.3
324.9
214.9
(ground-truth) truth) community as positive edges and edges between two vertices in different communities as negative edges. The predictions provided by the binary classifier (i.e., binary values in {0, 1}) are then used as the pairwise distances duo in our algorithms.
G.3
Additional results
G.3.1 Performance of Algorithm 8 on real-world datasets
In this subsection, we present the results of our algorithm in insertion-only streams (Algorithm g on real-worid datasets, shown in Figure 3 The results show that under good prediction quality, Algorithm 8 consistently outperforms other baselines across all datasets used. For example. in Figure ap. when [ 1.2, the average cost of Algorithm 8 is 13% lower than that of CLMNPT21
and 17% lower than that of CKLPU24. Besides, in Figure c Algorithm 8 reduces the clustering cost by up to 14% compared to CLMNPT21. Even if the prediction quality poor, Algorithm does not perform worse than CM23 and achieves comparable performance to CLMNPT21 (on FACEBOOK subgraphs).
G.3.2 Performance of Algorithm 8 Jusing binary classifiers as predictors
In this subsection, we present the results of Algorithm X using binary classifiers as predictors, as shown in Table These experiments are performed on three SBM graphs with parameter p 0.95 and varying sizes, as well as the DBLP dataset (a sampled subgraph with 10000 vertices). The results demonstrate that Algorithm fonthhm@ccomm connsstently outperforms its non-learning counterpart across all datasets. For instance, the SBM graphs with 200 and 600 vertices, Algorithm 8 achieves a 64% reduction clustering cost compared to CM23.
G.3.3 Running time of our algorithms
In this subsection, we present the running time of our algorithms for complete graphs on three FACE- BOOK subgraphs, compared to their non-learning counterparts, as shown Table ( IT] and Table 6 (Algorithm 8). The results show that our saaning-augmentt significant time overheads. The slight increase running time is due to the additional steps of querying the oracles and calculating the costs of two clusterings. These steps both reasonable and acceptable. Moreover, in the streaming setting, space efficiency is typically the primary focus.
algorithms do not introduce
38

---

Table 5: Running time (ms) of Algorithm 1 (for dynamic streams) on FACEBOOK subgraphs, compared to its non-learning counterpart. For FB O, we set = 1.19. For FB 414, we set / = 1.12. For FB 3980, set 1.19.
Dataset
FB 0
FB 414
FB 3980
Algorithm
CKLPU24
138..16 639.22
165.55
7.32
Algorithm
163.35
7.69
Table 6: Running time (ms) of Algorithm 8 (for insertion-only streams) on FACEBOOK subgraphs, compared to its non-learning counterpart. For FB O, we set 1.19. For FB 414, we set / 1.12. For FB 3980, set 1.19.
Dataset
FB O
FB 414
FB 3980
Algorithm
CM23
30.65
6.67
0.97
Algorithm
81.31
16.58
2.12
39


Reviews:
[{"review_id": "oghj8HlixK", "reviewer": "Reviewer_RLqw", "summary": "The authors study streaming algorithms for Correlation Clustering, which use the predictions of pairwise distances between vertices provided by a predictor. Experimental results on synthetic and real-world datasets demonstrate the superiority. Experimental results on synthetic and real-world datasets demonstrate  the superiority of the proposed algorithms over their non-learning counterparts.", "questions": "1. The limitations are not discussed in the paper. This would be beneficial as it would present suggestions for future research that addresses the limitations of this work.\n\n2. A more in-depth discussion of computational complexity, runtime, and performance under hardware limitations is needed to better assess the practicality of the method.", "limitations": "1. I suggest that the author further enrich the experiments to verify the advantages of the model.\n\n2. The organizational structure of the article needs to be further optimized, including some background knowledge and related work additions", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The article has certain theoretical analysis and a clear explanation of the essence of the algorithm;\n\n2. The proposed method is relatively novel.\n\n3. The paper introduces an innovative idea that provides valuable insights into newly designed components, which could significantly benefit researchers in related fields.\n\nWeaknesses:\n\n1. I suggest that the author further enrich the experiments to verify the advantages of the model.\n\n2. The organizational structure of the article needs to be further optimized, including some background knowledge and related work additions\n\n3. The limitations are not discussed in the paper. This would be beneficial as it would present suggestions for future research that addresses the limitations of this work.\n\n4. A more in-depth discussion of computational complexity, runtime, and performance under hardware limitations is needed to better assess the practicality of the method.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the helpful and constructive comments. Please find our detailed responses below.\n>[Q1] The limitations are not discussed in the paper. This would be beneficial as it would present suggestions for future research that addresses the limitations of this work.\n\nWe conclude our limitations and potential future work as follows:\n1. For complete graphs, our algorithm achieves a $(\\min \\\\{2.06\\beta, 3\\\\}+\\varepsilon)$-approximation using $\\tilde{O}(n)$ total space. There is a still gap between our approximation ratio and the best-known $(\\alpha_\\text{BEST}+\\varepsilon)$-approximation [1] where $\\alpha_\\text{BEST}$ is the best approximation ratio of any polynomial-time classical/offline algorithm. It would be interesting to explore whether it is possible to achieve an $(\\alpha_\\text{BEST}+\\varepsilon)$-approximation while using $\\tilde{O}(n)$ **total** space (including the space for streaming and post-processing) under our prediction model.\n2. For general graphs, our algorithm achieves an $O(\\beta \\log |E^-|)$-approximation using $\\tilde{O}(n)$ total space. There is an extra $\\beta$ factor in the approximation ratio compared to the best-known $O(\\log |E^-|)$-approximation [2]. It would be interesting to explore whether it is possible to achieve a better-than-$O(\\log |E^-|)$-approximation using the same space under our prediction model, thus further improving the best-known space-approximation tradeoff.\n\nWe will include the above discussion in the revised version.\n\n[1] Sepehr Assadi, Sanjeev Khanna, and Aaron Putterman. Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms. STOC 2025.\n\n[2] Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation Clustering in Data Streams. ICML 2015.\n>[Q2] A more in-depth discussion of computational complexity, runtime, and performance under hardware limitations is needed to better assess the practicality of the method.\n\nWe have conducted experiments to analyze the runtime of our algorithms (see Appendix H.4.1). The results show that our learning-augmented algorithms do not introduce significant time overheads. The slight increase in running time over its non-learning counterpart is due to the additional steps of querying the oracles and calculating the costs of two clusterings. These steps are both reasonable and acceptable. \n\nSince space efficiency is typically the primary concern in the streaming setting, we also measured the empirical memory usage of our algorithm given the predictor information and compared it to its non-learning counterpart:\n- CKLPU24: 8.1 MB\n- Algorithm 1 (given the predictor): 19.3 MB\n\nThe results show that our algorithm uses slightly more memory. This is reasonable, as our algorithm computes two clusterings and thus needs to maintain two separate sets of data structures in order to output the clustering with lower cost. This overhead comes with the benefit of a better approximation guarantee. \n>[L1] I suggest that the author further enrich the experiments to verify the advantages of the model.\n\nThank you for the valuable suggestion! We will consider further enriching the experiments to better evaluate the effectiveness and advantages of our proposed algorithms.\n>[L2] The organizational structure of the article needs to be further optimized, including some background knowledge and related work additions.\n\nThank you for the valuable suggestion! Due to space limitations, we have placed further related work, additional technical preliminaries, and a technical overview including some background knowledge in Appendices A, B, and C. We will further optimize the organizational structure of the paper in the revised version."}, {"review_id": "X8adTnmFvk", "reviewer": "Reviewer_nHDZ", "summary": "The paper studies the correlation cclustering problem in the streaming setting and proposes a new learning augmented algorithm for this problem. More specifically, given a $\\beta$-level predictor, the algorithm can achieve an improved $(\\min(2.06\\beta, 3) + \\epsilon)$-approximation in the complete graph case and an improved space in the general graph setting. Here the prediction information we want to get from the predictor is roughly about the pairwise distance on the graph (but more complicated, formally). Finally, the paper also presents an empirical evaluation on both synthetic and real-world datasetss, which demonstrates the advantage of the proposed algorithm.", "questions": "For the binary classifier in the experiment. What is the split of the training and test data (like, is the experiment setting similar to the setting where we use part of the dataset for training and run the evaluation on the remaining part)?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The technical contribution of this paper is solid. The paper gives a rigorous analysis (which is based on two previous theoretical papers) to show that, given a good predictor, there are better algorithms for the correlation clustering problem in both complete graph and general graph setting.\n\n- The paper gives a somewhat detailed experiments section that suggests the advantage of the proposed algorithms.\n\n- The organization of the paper is clear.\n\nWeaknesses:\n\n- I agree it is natural to consider predicting the pair-wise distance in a graph. But the formal definition of the $\\beta$-level predictor is a bit artificial to me and it is not very clear to me whether this guarantee is easy to achieve in practice. Also, to get a better approximation ratio, the $\\beta$ needs to be small (< 1.5).\n\n- The algorithms proposed in this paper seem to be largely based on the previous purely theoretical work. From a technical perspective, the new algorithms are not super surprise to me (but I agree the theoretical work of this paper is solid).", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the helpful and constructive comments. Please find our detailed responses below.\n>[Q] For the binary classifier in the experiment. What is the split of the training and test data (like, is the experiment setting similar to the setting where we use part of the dataset for training and run the evaluation on the remaining part)?\n\nFor the binary classifier used in our experiments, we follow the standard ML practice of splitting the data into separate training (70%) and testing (30%) sets. We further remark that this predictor is used for datasets with available ground-truth communities. In this setting, the goal of Correlation Clustering aligns with that of community detection by treating edges between two vertices in the same (ground-truth) community as positive edges and edges between two vertices in different communities as negative edges. The predictions provided by the binary classifier on the entire dataset are then used as the pairwise distances in our Correlation Clustering algorithms.\n>[W1] I agree it is natural to consider predicting the pair-wise distance in a graph. But the formal definition of the $\\beta$-level predictor is a bit artificial to me and it is not very clear to me whether this guarantee is easy to achieve in practice. Also, to get a better approximation ratio, the $\\beta$ needs to be small (< 1.5).\n\nAs stated in Lines 146-154, we may use ML models such as graph neural networks (GNNs) to learn pairwise distances from related networks defined on the same vertex set. These models can be trained to extract meaningful distances, for example, by learning node embeddings that map vertices to a Euclidean space. The distances between these embeddings naturally serve as pairwise distances and satisfy the triangle inequality (the first condition in our definition). \n\nWhile the second condition in our definition is a technical requirement for theoretical analysis, our algorithms remain applicable in practice even when the given pairwise distances do not strictly satisfy this condition. As long as the distances are meaningful, they can be directly incorporated into our framework. In fact, in certain scenarios, the predictions are derived by applying slight perturbations to the optimal solution, which is an assumption commonly adopted in prior work on learning-augmented algorithms. In such cases, we can define $d_{uv}=0$ if $u$ and $v$ are predicted to be in the same cluster, and $d_{uv}=1$ if they are predicted to be in different clusters. We conjecture that for many graphs, there exists a small $\\beta$ such that the second condition in Definition 3.1 is satisfied. As our experimental results (see Section 6 and Appendix H) suggest, our algorithm performs much better in practice than the theoretical guarantee suggests."}, {"review_id": "rminrw0fD7", "reviewer": "Reviewer_WNQG", "summary": "This paper studied learning-augmented correlation clustering in data streams for complete and general graphs. The goal is to cluster vertices of a graph arriving in a stream to minimize disagreements—positive edges that cross clusters and negative edges that fall within them.\n\nThe most commonly-studied version of the problem uses complete graphs, meaning that there are ${n \\choose 2}$ edges in the graph, and each edge is annotated with either $(-)$ or $(+)$ labels. A more complicated version is on general graphs, in which we will lose the ability to ‘infer’ $(-)$ edges from the set of $(+)$ edges. In the offline setting, there are separations between the two cases: we could achieve 1.437-approximation in polynomial time for complete graphs, but we cannot obtain any $O(1)$-approximation for the version with general graphs under plausible complexity assumptions. \n\nThis paper studied semi-streaming algorithms for the paper in the presence of a learning-augmented oracle. The oracle in the paper predicts distances between vertex pairs. Ideally, if the predictions are always correct, the optimal solution will pay costs for negative edges with $(1-d_{u,v})$ and positive edges with $d_{u,v}$. The algorithm uses a parameter $\\beta$ to represent a multiplicative approximation of $\\text{OPT}$ for the cost induced by the above solution.\n\nThe main results of the paper are: $i).$ for the complete graph setting, an algorithm that achieves $(min{2.06β,3}+0.1)$-approximation in $O(n \\text{polylog}(n))$ space; and $ii).$ for the general graph setting, an algorithm that achieves $O(\\beta\\log{|E^-|})$-approximation in $O(n \\text{polylog}(n))$ space. All of these algorithms run in polynomial time for post-processing. \n\nThe paper further conducted some experiments, showing that the algorithm for complete graphs has competitive experimental performances. In particular, for synthetic dataset, the proposed algorithm has a competitive performance with algorithms based on agreement decompositions (which is known to be very good for experiments); for real-world datasets, the proposed algorithm outperforms other benchmarks.", "questions": "Some questions were asked in the weakness part of the paper. One additional comment: please make sure that the discussion in Table 1 is for the polynomial-time case only. If one only cares about the space complexity, as in the ‘theory aspect’ of streaming algorithms, you can simply store a cut sparsifier, enumerate all possible clusters (this takes $n^n$ time), and output the one with the smallest cost. This gives us a $(1+\\varepsilon)$-approximation in semi-streaming space, although it is a very impractical algorithm. One of the main contributions of Assadi,  Khanna, and Putterman [STOC’25] is to show the approximation can be done in *polynomial time*.", "limitations": "This work mostly concerns the theoretical foundation of ML, and I do not see any immediate negative societal impacts.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "My general opinion for this paper is supportive. The paper studied an important problem with learning-augmented oracles. It is nice to see that the learning-augmented oracle could work for both complete and general graphs. Learning-augmented algorithms are growing popular in the recent two years (e.g., by BDSW [APPROX’24]; CDGLP [NeurIPS’24]; MRTV [ITCS'25]), and although I have some reservations about whether the oracle prediction used in this paper is ‘natural’, it is good to see such addition to the literature.\n\nThe paper is also well-written, and despite the rapid developments of the literature in correlation clustering recently, the paper still did a decent job to emphasize the significance of their results.\n\nOn the flip side, I have the following main criticisms:\n- Whether the oracle prediction used in this paper is ‘natural’: this is somehow subjective, and it is definitely not the most natural oracle one would come up with. The motivation of the oracle seems highly related to the metric LP used by CMSY [STOC’15]. In other words, somehow the model is designed to be tailored to the techniques the authors had in mind. This does not look natural to me.\n- Most of the techniques used in this paper follow from existing work. For instance, in the algorithm for complete graphs, despite a rather involved description and analysis of the TRUNCATEDPIVOT algorithm, the analysis really follows from CKLPU [SODA’24]. The PAIRWISEDISS algorithm, together with the ball-growing algorithm for general graphs, does need some white-box adaptation of existing algorithms. However, these adaptations also do not seem to have much technical novelty.\n\nOverall, I think despite the criticism, the merits of the paper still outweigh the flaws. I think much of my opinion was influenced by the fact that the paper contains algorithms for both complete and general-case correlation clustering and the landscape of the literature (which considers learning-augmented graph algorithms more practical now).", "was_revised": true, "final_justification": "As per the discussion with the authors and the AC, although I still have reservations about whether the prediction is \"natural\" enough, I believe the paper contains enough contributions for acceptance. I'm supportive of its acceptance.", "rebuttal": "We sincerely thank the reviewer for the helpful and constructive comments. Please find our detailed responses below.\n>[W1] Whether the oracle prediction used in this paper is ‘natural’: this is somehow subjective, and it is definitely not the most natural oracle one would come up with. The motivation of the oracle seems highly related to the metric LP used by CMSY [STOC’15]. In other words, somehow the model is designed to be tailored to the techniques the authors had in mind. This does not look natural to me.\n\nOn the one hand, we believe that predicting pairwise distances in a graph is natural, as there are several practical situations where such predictions help exploit the clustering structure of related networks defined over the same vertex set (see examples in Lines 63-76). We also note that similar oracles for pairwise distances have been considered in prior work across different contexts [1, 2].\n\nOn the other hand, as stated in Lines 146-154, while the second condition in our predictor definition (Definition 3.1) is a technical requirement for theoretical analysis, our algorithms remain applicable in practice even when the predicted pairwise distances do not strictly satisfy this condition. As long as the distances are meaningful, they can be directly incorporated into our framework. In fact, in certain scenarios, the predictions are derived by applying slight perturbations to the optimal solution, which is an assumption commonly adopted in prior work on learning-augmented algorithms. In such cases, we can define $d_{uv}=0$ if $u$ and $v$ are predicted to be in the same cluster, and $d_{uv}=1$ if they are predicted to be in different clusters. We conjecture that for many graphs, there exists a small $\\beta$ such that the second condition in Definition 3.1 is satisfied. As shown in our experimental results (see Section 6 and Appendix H), our algorithm performs much better in practice than the theoretical guarantee suggests.\n\n[1] Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, and Wei Chen. Query-Efficient Correlation Clustering with Noisy Oracle. NeurIPS 2024.\n\n[2] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals. ICLR 2023.\n>[W2] Most of the techniques used in this paper follow from existing work. For instance, in the algorithm for complete graphs, despite a rather involved description and analysis of the TRUNCATEDPIVOT algorithm, the analysis really follows from CKLPU [SODA’24]. The PAIRWISEDISS algorithm, together with the ball-growing algorithm for general graphs, does need some white-box adaptation of existing algorithms. However, these adaptations also do not seem to have much technical novelty.\n\nWe have provided a technical overview in Appendix C. Here, we highlight our main technical novelty as follows:\n1. For complete graphs, the analysis of our algorithms with predictions is non-trivial. Our key observation is that the truncated version of the LP rounding algorithm by CMSY [STOC’15] is equivalent to a two-step procedure: first sampling a subgraph $G'$ based on the predictions, and then running a truncated version of the Pivot algorithms on $G'$. Our main technical contribution is to prove that 1) the cost of the pivot clusters produced by the truncated version of the LP rounding algorithm is at most $2.06\\beta$ times the cost of the optimal solution; 2) the cost of the optimal solution on $G'$ does not differ from that on the original graph $G$ by a lot. In this way, our algorithms keep the space small while achieving an approximation ratio better than $3$ under good prediction quality.\n2. For general graphs, we can incorporate our predictions into the existing ball-growing algorithm by performing ball-growing on a sparsifier $H^+$ for $G^+$, using the predictions as distance metrics. While this straightforward approach improves space complexity, it leads to an approximation ratio with an undesirable $\\log n$ term, which is suboptimal when $n > |E^-|$. To address this issue, we refine the algorithm by introducing a branching strategy in the streaming phase, based on the tracked space usage of $|E^-|$. In this way, our algorithm keeps the space small while achieving a near $O(\\log |E^-|)$-approximation under good prediction quality.\n\n>[Q] Please make sure that the discussion in Table 1 is for the polynomial-time case only. If one only cares about the space complexity, as in the ‘theory aspect’ of streaming algorithms, you can simply store a cut sparsifier, enumerate all possible clusters (this takes $n^n$ time), and output the one with the smallest cost. This gives us a $(1+\\varepsilon)$-approximation in semi-streaming space, although it is a very impractical algorithm. One of the main contributions of Assadi, Khanna, and Putterman [STOC’25] is to show the approximation can be done in *polynomial time*.\n\nThank you for the suggestion! Yes, we focus on polynomial-time semi-streaming algorithms. We will clarify this in the revised version."}, {"review_id": "qkKHBYjn2T", "reviewer": "Reviewer_S28r", "summary": "This paper tackles the problem of correlation clustering in the streaming setting (both insertion-only and dynamic streams) and proposes to augment classical streaming algorithms with predictions to improve performance. In correlation clustering, we receive a stream of edges (each labeled positive or negative) of a graph and aim to partition the vertices into clusters to minimize disagreements (positive edges across clusters plus negative edges within clusters). The authors introduce the first learning-augmented streaming algorithms for this problem. Their algorithms assume access to a predictor that provides pairwise “dissimilarity” scores between vertices (intended to estimate whether two vertices should be separated or not in the optimal clustering). Using these predictions, the paper’s algorithms achieve an approximation ratio better than 3 for clustering on complete graphs, which is the first time an approximation factor below 3 has been attained in the single-pass dynamic streaming model. For general (not necessarily complete) graphs, the paper presents a streaming algorithm that attains an $O(\\beta \\log |E^-|)$ approximation (here $|E^-|$ is the number of negative edges and $\\beta$ measures prediction error) using only $\\tilde O(n)$ space, improving the memory usage over the prior $O(|E^-|)$ space bound without predictions. The methods build upon and simplify prior techniques (notably the Pivot-based algorithms by Ahn et al. 2015 and Cambus et al. 2024) by incorporating predicted pairwise distances into the clustering decisions. The paper includes experiments on synthetic and real datasets, which indicate that the proposed learning-augmented algorithms outperform baseline streaming algorithms that do not use predictions.", "questions": "1. The theoretical model assumes an oracle predictor with a known $\\beta$-level of quality. How do the authors envision obtaining such a predictor in practice? For instance, could it be trained on smaller samples or past instances of similar clustering problems, and how sensitive is the algorithm’s performance to mis-specification of $\\beta$? \n\n2. The paper mentions the $1.847$-approximation insertion-only streaming algorithm by Cohen-Addad et al. (STOC 2024), noting that the new approach is much simpler and works in the dynamic setting. Could the authors elaborate on the performance gap here? For example, if we restrict to insertion-only streams, does the learning-augmented algorithm attain a similar 2.06 approximation, or could it be improved further? A brief discussion on whether the learning-augmented approach might close the gap to $1.847$ in insertion-only scenarios (or why that might be difficult) would be insightful.\n\n3. The general graph result uses an adapted $\\beta$-level predictor. Is this essentially the same notion of predictor quality as in complete graphs, or does it require a different adaptation (e.g., predicting distances in a sparsified graph or dealing with multicut structure)? It would be helpful if the paper clarified what adjustments are needed for the predictor in general graphs and whether obtaining such an adapted predictor is harder or easier than in the complete graph case.\n\n4. In practice, do the authors observe any memory overhead due to the learning-augmented approach (like needing to store predictor information)? If the space usage was tightened or if less space is available, how would the algorithm degrade?\n\n5. Limited Novelty - The algorithm is essentially formed by the truncation during the stream and the post-processing part. For the streaming phase, the idea is mainly from CKLPU [SODA’24] (cf. CM [NeurIPS’23]), and I do not see anything that is substantially novel. Am I understanding it correctly, or am I missing something? Also, the approximation factor is somewhat weak; to outperform the pivot-based approximation, there has to be a value of $\\beta$ where you need predictions with very high quality, correct?", "limitations": "The paper does acknowledge its limitations. The authors clearly state all necessary assumptions (e.g., the need for an oracle predictor and its quality parameter $\\beta$) and ensure the reader understands in which scenarios the theoretical guarantees hold. They also empirically test robustness by varying parameters like dataset size to see how the algorithm copes. The limitations I see are the following\n\n1. The focus on correlation clustering on cliques is primarily a theoretical problem. Existing streaming algorithms already offer better guarantees for this specific case.\n\n2. The novelty is somewhat limited, as the algorithm builds upon existing techniques and incorporates a learning component which does not mean that the novelty is significant. I again acknowledge that coming up with mathematical proofs and making the proof go through is not trivial.\n\n3. Unnatural Oracle: This is a significant drawback in the paper. The ML oracle used by the algorithm seems somewhat artificial, and its practical implementation may be challenging. On a very high-level intuition, the way I see it is \"Suppose we assume that we can predict similarities that could be used to obtain a good approximation of the optimal solution, then we have an approximation algorithm of that quality.\" Is my understanding correct? If yes, then the significance of the result is somewhat limited and seems heavily dependent on that assumption.\n\nRegarding societal impacts, the paper does not flag any negative consequences of this research, which seems reasonable given the theoretical nature of the work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Quality: \n\nS1 - The paper appears to be technically solid, providing rigorous theoretical results alongside empirical validation. The algorithms are described with clear theoretical guarantees: for complete graphs, the algorithm achieves an expected $(\\min{2.06\\beta, 3}+\\epsilon)$-approximation using $\\tilde O(n)$ space, and for general graphs an $O(\\beta \\log |E^-|)$-approximation with similar space usage. These results improve upon the best-known streaming trade-offs (e.g., beating the previous $3+\\epsilon$ approximation barrier in dynamic streams). The proofs build on established methods (Pivot algorithm and LP-based rounding) and adapt them to incorporate prediction errors, which is intellectually sound. The experimental section is a notable strength: by demonstrating performance gains on real and synthetic data, the authors bolster confidence that the theoretical improvements translate into practice. The paper’s claims are well-supported by the analysis. \n\nW1 - The reliance on an oracle predictor is a major weakness. The theory assumes a “$\\beta$-level” predictor which may be non-trivial to obtain in practice. While this assumption is clearly stated and the algorithm is robust to predictor error, it does mean the quality of results hinges on an external learning component. The paper could further discuss how one might train or derive such a predictor in real-world scenarios.\n\n\nClarity:\n\nS2 - The paper is well-written and organized, making a complex theoretical contribution accessible. The introduction clearly defines the correlation clustering problem and the streaming models, with helpful context on prior results and their limitations. Key concepts like the $\\beta$-level predictor are explained intuitively (the predictor’s quality $\\beta$ indicates how close the predicted clustering is to optimal), and the paper provides pointers to formal definitions in the text. The algorithms and theoretical results are presented with appropriate theorem statements and proofs.\n\nW2 - One area for improvement in clarity could be a more explicit discussion on practical usage of the predictor (perhaps a short example of how a predictor might be learned or an intuitive illustration of its inputs/outputs)\n\nSignificance:\n\n\nS3 - The contributions of this paper are significant, especially within the streaming and approximation algorithms community. Correlation clustering is a fundamental ML problem with many applications (e.g. community detection and image segmentation), and the streaming setting is increasingly relevant for large-scale data. Prior to this work, achieving better than a 3-approximation in a single-pass dynamic stream was an open challenge – this paper provides the first result to surpass that barrier by leveraging predictions. Moreover, the algorithm for general graphs significantly reduces memory requirements: it removes the dependence on storing all negative edges ($|E^-|$) by using predictions, which can be extremely beneficial when the graph is dense. In practical terms, if a reasonable predictor is available, one can now cluster streaming data with higher accuracy or using less memory than before. The paper also connects two areas (streaming algorithms and learning augmentation), demonstrating how machine learning predictions can be used to overcome traditional worst-case barriers.\n\nW3 - One caveat on significance is that the improvements are conditional on predictor quality. If no reliable predictor exists, the method falls back to the known 3-approximation and offers no worst-case gain. Thus, the result is very meaningful assuming the predictor can be trained or provided. Additionally, while the paper simplifies implementation compared to a state-of-the-art 1.847-approx algorithm, the achieved approximation (≈2.06) is still higher than 1.847. There remains a gap to close if one hopes to reach near-optimal clustering in streaming.\n\nOriginality:\n\n\nS4 - The idea of learning-augmented algorithms is a relatively recent trend, and this paper applies it in a novel way to the correlation clustering problem. To the best of my knowledge, there were no prior streaming algorithms for correlation clustering that incorporate predictions, so this represents a fresh contribution. The authors build on known techniques (like the Pivot algorithm by Ailon et al. and its streaming variants) but innovate by integrating a prediction oracle into the clustering process.\n\nW4 - One could argue that the paper’s techniques are incremental in the sense that they extend existing algorithms with an oracle rather than inventing a completely new clustering method. The core idea is largely based on existing approaches, and the main theoretical results are derived from previous work, which limits the paper’s novelty. However, I acknowledge that making this extension successful and theoretically analyzable is non-trivial.", "was_revised": true, "final_justification": "All my questions have been answered. After reading the comments from other reviewers and the comprehensive responses from the authors, I think there is no need to update my score. I keep my score to 4 and I incline to accept the paper.", "rebuttal": "We sincerely thank the reviewer for the helpful and constructive comments. Please find our detailed responses below.\n>[W1] The theory assumes a “$\\beta$-level” predictor which may be non-trivial to obtain in practice. While this assumption is clearly stated and the algorithm is robust to predictor error, it does mean the quality of results hinges on an external learning component. The paper could further discuss how one might train or derive such a predictor in real-world scenarios.\n\n>[Q1] How do the authors envision obtaining such a predictor in practice? For instance, could it be trained on smaller samples or past instances of similar clustering problems, and how sensitive is the algorithm’s performance to mis-specification of $\\beta$?\n\n>[W2] One area for improvement in clarity could be a more explicit discussion on practical usage of the predictor.\n\nWe highlight that our algorithms do NOT need to take $\\beta$ as input. The prediction quality $\\beta$ is only used for **theoretical** analysis (e.g., approximation guarantees) of the algorithms. \n\nIn practice, as stated in Lines 146-154, we may use ML models such as graph neural networks (GNNs) to learn pairwise distances from related networks defined on the same vertex set. These models can be trained to extract meaningful distances, e.g., by learning node embeddings that map vertices to a Euclidean space. Specifically, the model takes as input a related graph (e.g., a previous instance), represented via its adjacency matrix or feature matrix, and outputs an embedding vector for each vertex. The distances between these embeddings can then be computed, for example via inner products, and these naturally satisfy the triangle inequality, thereby serving as valid pairwise distances. \n>[Q2] The paper mentions the $1.847$-approximation insertion-only streaming algorithm by Cohen-Addad et al. (STOC 2024), noting that the new approach is much simpler and works in the dynamic setting. Could the authors elaborate on the performance gap here? For example, if we restrict to insertion-only streams, does the learning-augmented algorithm attain a similar 2.06 approximation, or could it be improved further? A brief discussion on whether the learning-augmented approach might close the gap to $1.847$ in insertion-only scenarios would be insightful.\n\nThank you for the insightful question. Indeed, we have also developed an algorithm for complete graphs in insertion-only streams (see Appendix F), which differs from our algorithm in dynamic streams but achieves the same approximation ratio. We are also interested in whether our prediction model could help close the gap to $1.847$ in insertion-only streams. We note that the $1.847$-approximation algorithm by Cohen-Addad et al. (STOC 2024) is a purely combinatorial algorithm based on local search. Specifically, their algorithm needs to implement a local search routine during the stream via sampling, which introduces the main source of impracticality. Since their framework is fundamentally different from ours -- and in particular, their local search implementation does not appear to use distance information -- it is not clear how our distance-based predictions will help the algorithm. However, it is worth exploring whether new kinds of prediction models could be designed to make their algorithm more efficient. We leave this as future work.\n>[Q3] The general graph result uses an adapted $\\beta$-level predictor. Is this essentially the same notion of predictor quality as in complete graphs, or does it require a different adaptation? It would be helpful if the paper clarified what adjustments are needed for the predictor in general graphs and whether obtaining such an adapted predictor is harder or easier than in the complete graph case.\n\nFor general graphs, the adapted notion of a $\\beta$-level predictor quality requires a slightly different formulation of prediction quality. Specifically, as described in Lines 142-145, the second condition becomes $\\sum_{(u,v)\\in E_H^+}w^\\prime_{uv}d_{uv} + \\sum_{(u,v)\\in E^-}(1-d_{uv}) \\le \\beta \\cdot \\mathrm{OPT}$, where $H^+:=(V,E_H^+,w')$ is an $\\varepsilon$-spectral sparsifier of $G^+=(V,E^+)$, which approximates all the cuts in $G^+$ within a $(1\\pm \\varepsilon)$ factor. This adaptation is introduced purely for theoretical analysis, as our algorithm for general graphs performs ball-growing on a sparsified graph. Thus, we can use the same method to obtain such a predictor as in the complete graph case; the only difference lies in the quality measurement. \n\nFurthermore, we note that our algorithm for general graphs (which uses the adapted predictor) can be extended to work under the same predictor definition as in the complete graph setting, for a broad class of graphs (i.e., bounded-degree graphs). We provide further details in Appendix G.4.\n>[Q4] In practice, do the authors observe any memory overhead due to the learning-augmented approach? If the space usage was tightened or if less space is available, how would the algorithm degrade?\n\nAs is standard in the literature of learning-augmented algorithms, we do NOT account for the memory required to implement or store the predictor; our focus is on the algorithmic complexity **given** a predictor. That said, to address your concern, we reran some experiments and measured memory usage of training the binary classifier used in Table 3 on the SBM ($n = 1200$) dataset. Total memory usage for training and storing predictor information is ~341.3 MB. \n\nWe also measured the memory usage of our algorithm given the predictor information and compared it to its non-learning counterpart:\n- CKLPU24: 8.1 MB\n- Algorithm 1 (given the predictor): 19.3 MB\n\nThe results show that our algorithm uses slightly more memory. This is reasonable, as our algorithm computes two clusterings and thus needs to maintain two separate sets of data structures in order to output the clustering with lower cost. This overhead comes with the benefit of a better approximation guarantee. Finally, we remark that although we are not able to limit/tighten the space usage during execution, it remains comparable to that of the non-learning baseline.\n>[Q5] The algorithm is essentially formed by the truncation during the stream and the post-processing part. For the streaming phase, the idea is mainly from CKLPU [SODA’24] (cf. CM [NeurIPS’23]), and I do not see anything that is substantially novel. Am I understanding it correctly, or am I missing something? Also, the approximation factor is somewhat weak; to outperform the pivot-based approximation, there has to be a value of $\\beta$ where you need predictions with very high quality, correct?\n\nRegarding your first question, your understanding is correct in some sense, as our algorithmic framework for complete graphs indeed builds upon CKLPU [SODA’24] and CM [NeurIPS’23]. However, we would like to emphasize that the analysis of our algorithms with predictions is non-trivial. We have provided a technical overview in Appendix C. Here, we highlight our main technical novelty: Our key observation is that the truncated version of the LP rounding algorithm by CMSY [STOC’15] is equivalent to a two-step procedure: first sampling a subgraph $G'$ based on the predictions, and then running a truncated version of the Pivot algorithm on $G'$. Our main technical contribution is to prove that 1) the cost of the pivot clusters produced by the truncated version of the LP rounding algorithm is at most $2.06\\beta$ times the cost of the optimal solution; 2) the cost of the optimal solution on $G'$ does not differ from that on the original graph $G$ by a lot. In this way, our algorithms keep the space small while achieving an approximation ratio better than $3$ under good prediction quality.\n\nRegarding your second point, your understanding is correct **from the theory aspect**. However, as shown in our experimental results (see Section 6 and Appendix H), our algorithm performs much better in practice than the theoretical guarantee suggests. Moreover, our algorithms remain applicable in practice even when the predicted pairwise distances do not strictly satisfy the formal definition (Definition 3.1). As long as the distances are meaningful, they can be directly incorporated into our framework.\n>[L3] The ML oracle used by the algorithm seems somewhat artificial, and its practical implementation may be challenging. On a very high-level intuition, the way I see it is \"Suppose we assume that we can predict similarities that could be used to obtain a good approximation of the optimal solution, then we have an approximation algorithm of that quality.\" Is my understanding correct?\n\nYes, your understanding is correct. However, a commonly adopted assumption in prior work on learning-augmented algorithms is that the predictions are derived by applying slight perturbations to the optimal solution, which is already a good approximation to the optimal one.\n\nWe believe that predicting pairwise distances in a graph is natural, as there are several practical situations where such predictions help exploit the clustering structure of related networks defined over the same vertex set (see examples in Lines 63-76). We also note that similar oracles for pairwise distances have been considered in prior work across different contexts [1, 2].\n\n[1] Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, and Wei Chen. Query-Efficient Correlation Clustering with Noisy Oracle. NeurIPS 2024.\n\n[2] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals. ICLR 2023."}]

Author rebuttal:

Meta-review: The paper studies learning augmented algorithms for the correlation clustering problem. By carefully combining an oracle which provides additional information, the authors are able to obtain a low space algorithm which have approximation quality comparable to the best algorithms without any space constraints. The reviewers did note that the prediction model maybe a bit unnatural, but were positive about the fact that this is an important first step. This was towards the top of my pile and I am recommending accept.
Decision: Accept (poster)