Near-Optimal Correlation Clustering with Privacy
Authors: Vincent Cohen-Addad
Chenglin Fan
Silvio Lattanzi
Slobodan Mitrović
Ashkan Norouzi-Fard
Nikos Parotsidis
Jakub Tarnawski
Venue: NeurIPS 2022 Accept (2022)
Keywords: Clustering
Correlation Clustering
Differential Privacy
Approximation Algorithms

Abstract: Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labeling and many more. In the correlation clustering problem one receives as input a set of nodes and for each node a list of co-clustering preferences, and the goal is to output a clustering that minimizes the disagreement with the specified nodes' preferences. In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters.

Near-Optimal Correlation Clustering with Privacy
Vincent Cohen-Addad
Chenglin Fan
Silvio Lattanzi Google Research si eilviol@google.co com
Google Research cohenaddaddgooglee com
Pennsylvania State University
fanchenglin@@mail..
Slobodan Mitrović
Ashkan Norouzi-Fard
Nikos Parotsidis Google Research
UC Davis
Google Research ashxannorruzz1@oogglee
smitrovic@ucdavis. edu
nikospāgoogle.c com
Jakub Tarnawski Microsoft Research
jakub www.aawwwwwiimiiooooooooooooo
Abstract
Correlation clustering is central problem in unsupervised learning, with applica- tions spanning community detection, duplicate detection, automated labeling and many more. In the correlation clustering problem one receives as input nodes and for each node a list of co-clustering preferences, and the goal is to output clustering that minimizes the disagreement with the specified nodes' preferences. In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters.
of
1 Introduction
Clustering is a central problem in unsupervised machine learning. The goal of clustering is to partition of input objects so that similar objects are assigned to the same part while dissimilar objects assigned to different parts of the partition. Clustering has been extensively studied throughout the years and many different formulations of the problem known. In this paper study the classic correlation clustering problem in the context of differential privacy.
In the correlation clustering problem [BCC44 one gets graph whose vertices are the objects to be clustered and whose edges represent clustering preferences between the objects. More specifically, the input of the problem is graph with positive and negative labels (and possibly with non-negative weights) on the edges, where positive edges represent similarities between vertices and negative edges represent dissimilarities. Then the correlation clustering objective asks to minimize the sum of (the weights of) positive edges across clusters plus the sum of (the weights) of negative edges within clusters. Thanks to its simple and elegant formulation. the problem has received much attention and it is used to model several practical applications including finding clustering ensembles (BGU13), duplicate detection [ARS09], community mining (CSX12), disambiguation tasks [CMNT08), automated labelling AHK+09 (CP08) and many more. this paper we focus the most studied version of the problem where all edges have unit weight. In this case the best known algorithm [CALN22) has an approximation guarantee 1.994, which improves over 2.06-approximation due [CMSY15] and a 2.5-approximation due to (ACN08]. Furthermore, when the number of clusters is upper-bounded by k. a polynomial-time approximation scheme is known [GGO5). In the weighted case O(log n) -approximation is known (DEF106), and improving
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

upon this would lead to a better approximation algorithm for the notoriously difficult multicut problem. For the maximization version of the problem, where the goal is to maximize the sum of (the weights of) the positive edges within clusters plus the sum of (the weights of) the negative edges across clusters, [CGW05 Swa04] gave a arr60aaaprooiiationn algorithm for the weighted case and PTAS is known for the unweighted case [BBC04]
Differential Privacy (DP) is the de facto standard for user privacy [DMNS06). and it is of fundamen- tal importance to design solutions for classic unsupervised problems in this setting. In differential privacy, the focus on datasets, G and G', that differ on a single entry. An algorithm A is (c, 6)- differentially private if the probabilities of observing any set of possible outputs S of A when run on two "almost identical" imputs G and G' are similar: Pr [A(G) E S] I e Pr [A(G") E S] 6. Over the last decade, there have been many works considering problems related to private graphs.
e.g., (HL.)099 RHMS09
GL.M+ 10 GRU12 BBDST3
KRSYIT KNRST3 BNSVI5 AC19
US19, BCSZI8 EKKL20
BEK21
NV21 FHS21
We briefly review two possible definitions
of privacy graphs.
Edge Privacy. In the edge privacy setting, two datasets are considered to be close if they differ on a single edge. [HLMJ09] introduced differentially edge-private algorithm for releasing the degree distribution of graph. They also proposed the notion of differential node privacy and highlighted some of the difficulties in achieving it. [GRU12 showed how to answer cut queries in private edge model. [BBDS12] improved the error for small cuts. [GLM 10) showed how to privately release a cut close to the optimal error size. [AU19] studied the private sparsification of graphs, which was exemplified by a proposed graph meta-algorithm for privately answering cut-queries with improved accuracy. [KKLL20 studied the problem of private synthetic graph release while preserving all cuts.
Recently, NV21 FHS21
proposed frameworks for the private densest subgraph problem.
Node Privacy. Node differential privacy requires the algorithm to hide the presence or absence of single node and the (arbitrary) set of edges incident to that node. However, node-DP is often difficult achieve without compromising accuracy, because even very simple graph statistics can be highly sensitive to adding or removing single node [NRSI3 BBDS13 BCSZ18).
Differentially private clustering has been extensively studied [DLL 17 CNX20 GKM20 CGKM21
LS20]. Nevertheless, until very recently no theoretical results were known for differentially private correlation clustering. In this context, the privacy is on the edges of the graph: namely, two graphs on the same set of vertices are adjacent if they differ by exactly one edge.
In recent work, [BEK21] obtained the first differentially private correlation clustering algorithm with approximation guarantees using differentially private synthetic graph release [GRU12 [KKL20) The framework proposed by [BEK2I is very elegant and general as it allows one to run any non- private correlation clustering approximation algorithm on a modified version of the input graph that ensures privacy. Namely, any a-approximation algorithm correlation clustering leads to differentially private approximation algorithm with multiplicative approximation a and additive approximation O /e). This applies to the more general weighted version of the problem. In the same paper, the authors also obtain an Q(n/c) /c) lower bound on the additive approximation of differentially private algorithms, even unweighted graphs that consist of a single path. However, the framework from [EK2T is rather impractical, and the additive error is far from matching the lower bound on the additive approximation. These results prompt the natural question of determining the best approximation guarantees (multiplicative and additive) that are possible under differential privacy.
As observed by [BE22]], instantiating the exponential mechanism [T007 over the space of all clusterings yields an algorithm with additive error Onn logn). However, it is not known how to efficiently sample from the exponential mechanism for correlation clustering. [BEK2]] state finding polynomial-time algorithm that matches the additive error of the exponential mechanism as an "exciting open problem given the prominent position correlation clustering occupies both in theory and practice".
Our Results and Technical Overview. In this paper we present new differentially private algorithm for the unweighted setting which achieves a constant multiplicative approximation and a nearly optimal On n) additive approximation (for fixed privacy parameters). More precisely, we show:
2

---

Theorem 1.1. For any e and ó there is an algoritim for min- disagiee correlation clustering on unweighted complete graphs that is (c. 6) differentiay private and returns a solution of cost (1))
OPT O a log n 1lg((1/8)
Our algorithm is given in Section as Algorithm Its privacy is proved in Section 4 Theorem 4.5
and Section Slis devoted to the approximation guarantees [hhorem 5.5).
The lower bound on the additive approximation in [BE22] does not preclude an (e, 0 algorithm for correlation clustering on complete graphs with sublinear error. More precisely, [BEK21 show an 2((/c) lower bound for weighted paths and an (n)) lower bound for unweighted paths both non-complete graphs against pure (c, D) algorithms. Nevertheless, we prove that linear error necessary even for complete unweighted graphs and (e, --privac,,, showing that our algorithm indeed near-optimal.
Theorem 1.2. Any -)-ffferrentllllyy private algorithm for correlation clustering on unweighted complete graphs has additive error (It) assuming S 1 and 5 < 0.1.
The proof of Theorem 1.2] is given in Appendix C
Our approach follows the recent result of [CALM for obtaining the first ((1)-rounds, O(1)- approximation algorithm for correlation clustering in the parallel setting. However, to obtain our bounds in the context of differential privacy we introduce several critical new ideas.
At a high level, the algorithm of [CALM trims the input graph in two steps. the positive edges between those vertices that have very similar neighborhoods of positive edges (such pairs of vertices are said to be in agreement). More precisely. for two nodes to be in agreement the size of the intersection of the positive neighborhoods should be larger than some threshold times the positive degrees of each endpoint. Second, it removes the positive edges whose endpoints have lost significant fraction of its positive neighbors during the first step (such vertex called a light vertex). Finally, the resulting clusters are given by the connected components induced by the remaining positive edges.
First, it only keeps
Our approach consists in making each of the above steps (agreement computation, light vertex computation, connected components) differentially private.
A natural way to make the agreement computation differentially private is to add Laplace noise to the size of the intersection of the neighborhoods for each pair of vertices u, and to decide that u, are in agreement if the noisy intersection size is larger than B times the positive degrees of u and v. One of the erucial challenges here is to make sure that the total amount of noise needed to make the entire procedure differentially private is bounded, so that we can still obtain strong approximation guarantees.
The second step, the computation of light vertices, can be made differentially private in a very natural way: simply add Laplace noise to the degree of each vertex after the removal of the edges whose endpoints are not in agreement and decide whether a vertex is light based on the noisy degree.
The third step, the connected components computation, is the most challenging. Here we need to argue that computing connected components the graph induced by the positive edges differentially private. In other words, we have to show that the graph induced by these edges has no "bridge", ; that is, there not single positive edge whose removal would increase the number of connected components. This is done by establishing new properties of the algorithm and showing that if all the previous steps have succeeded, the presence of bridge is in fact a very unlikely event. Moreover, to guarantee privacy, we must carefully modify the way we treat light vertices, as well as those of low degree.
Discussion of Recent Work. We note that the work of [CALM*21 has been followed by the work of AW22), who improved in the context of streaming algorithms; however, it is not clear that there would be a benefit in using the framework of AW22), whether in terms of running time, multiplicative, or additive approximation.
In concurrent and independent work, Liu 2m22 proposed an (c, 6)-DP algorithm that achieves a multiplicative approximation of Ollog n) and an additive error of Ö n= (og6)) for general
ve
weighted graphs (assuming constant and 8). improving upon the O n. log(n/8) error of BEK21
3

---

This result arises via more careful analysis of differentially private synthetic graph release in the case of correlation clustering. Furthermore, for unweighted complete graphs Liu obtained an algorithm with constant multiplicative approximation and an additive enror of Onn n V + log n) for fixed privacy parameters, where A is the maximum degree of positive edges in the graph. The latter is a pivot-based algorithm augmented with Laplace noise. This results in an O(n log" n) worst-case additive error. Our algorithm yields an additive error of O( log" n) (Thorem 1.1 which significantly improves upon the result of Liu.
2
Preliminaries
Correlation clustering. In the min-disagree variant of the correlation clustering problem in com- plete graphs one receives as input complete signed graph G = Ft, E-), where E+ (resp., D-) denotes the set of "+" edges (resp., "-"), and the objective to compute clustering = (Cl,...; C.} of V of minimum cost, which is the number "-" "-" plus the number of "+" edges whose endpoints belong to the distinct clusters.
edges whose endpoints part of the same cluster
In the sequel we will use G = (V, E) to refer to G EV, EE)) (with E = E.
Differential privacy. The definition of differential privacy (DP) is due to [DMNS06;; precise formulation introduced by [Dwo06].
the Definition 2.1 (Differential Privacy). A mechanism (randomized algorithm) M with domain G and range M, which we will write as M -> MM, is (c, diifferenntl private if for any two adjacent datasets G, G E G and set of outcomes S C M we have
Pr (M E S] S e Pr [M E +
Recall that in this work, two datasets (graphs) are adjacent if they have the same set of vertices and differ by one edge.
important property of differential privacy that we can compose multiple differentially private subroutines into a larger DP algorithm with privacy guarantees.
Lemma 2.2 (4D++14) Theorem B.1). Let M1 G Mi be randomized algorithm that is (61, (1,55))-PP. Further let M2 G x MM - M2 be a randomized algorithu such that for every fixed m2 E M1, the mechanism G a G + M2(G, m1) M2 is (E2, 62) Then the composed mechanism G - G + M2(G, (G)) E M2 is (EI E2, 81 + d
We also use the following property to analyse the privacy of our algorithm. Its proof can be found in Appendix A.I
Lemma 2.3. Let M1 G M1 be a randomized algorithm that is (c, DD- Suppose B C M1 is set of "bad outcomes" with Pr [M1(G) B) s 8" for any G E G. Further let M2 G x Mi - M2 be a deterministic algorithm such that for every fixed "non-bad" m. E MM B we have M2(G, m)) M2(G', ma) for adjacent G,G' G' G. Then the composed mechanism G 3 G + M2 (G)) E M2 is (6,6 + 5
If we have k mechanisms that are (e, 0)DD, their (adaptive) composition is (ke, -DP However, it is also possible to reduce the linear dependency on k in the first parameter to roughly VT: by accepting higher additive error.
Theorem 2.4 (Advanced Composition Theorem DRV1O)). For all 8' 2 O, an adaptive composition of (c, -)differryttially private mechanisms satisfies ('d.")--iffereentia privacy for
===220 2kln((/8) + ke(e" -1)
Let Lbp(b) be the Laplace distribution with parameter and mean We will use the following two properties of Laplacian noise.
Fact 2.5. Let Y ~ Lap(b) and z > 0. Then
Pr > 2] exp (-+)
Pr Pr|| > 2| exp (-1)-
and
Theorem 2.6 (DR 14), Theorem 3.6). Let : G + R$ be function. Denote by A f its 61- sensitivity, which is the maximum value of [G] - (((G)) over adjacent datasets G, G' E G. Then + (Y1..., Ys), where the variables Y; Lap( Af/e) are iid, is (e, -DP

---

Graph notation. Given an input graph G and a vertex v, we denote its set of neighbors by (v) and its degree by d(u) = [e)... As in [CALM*21], we adopt the convention that NNu)) for every e E V (one can think that we have self-loop at every vertex that is not removed at any step of the algorithm).
Private Algorithm for Correlation Clustering
In this section we formally define our algorithm, whose pseudo code is available in Algorithm 1 together with Definition 3.1] The algorithm uses number of constants, which we list here for easier reading and provide feasible settings for their values:
and d E (0, ( are user-provided privacy parameters.
3 and X, used the same way as in [CALM* 21), parametrize the notions of agreement
(Dfinition 3.1) and lightness (Line 3), respectively. For the privacy analysis, any B, X < 0.05 would be feasible. These parameters also control the approximation ratio, which
((1((3))) assuming that 8, À are small enough; as in [CALM+21], one can set e.g. B
À 0.8/38 x= 0.02.
Cagr. jage and are auxiliary parameters that control the noise used in computing agreements; they are functions of c and and are defined in Definition 3.1
3' and X' are used in the privacy analysis; both can be set to 0.1.
To is degree threshold; we return vertices whose (noised) degree is below that threshold as singletons, which incurs an additive loss O(Tn)) in the approximation guarantee. We set
8 logg()/))
To Ti +
where for the privacy analysis we require T₁ to be a large enough constant; namely, one take the maximum of the right- hand sides of (6
10 III (44, and
15); asymptotically in terms of and 6, this is of the order O (assuming e < O(1)). To additionally obtain a constant-facce approximation guarantee. we further require a polylogarithmic Ti, namely of the order O(log* n log(1/8)e -2) see Eq. 17 in the proof of Lemma 5.3
(T((1
The following notion central to our algorithm and is used as part of Line 2 Afgorithh Definition 3.1 (Noised Agreement). Let us define Eagr e/5.8, dagr 8/8, and
Mragt [n(1/
+ +1+1
(Note that y 2 22)) Further let H as defined in Line of Algorithm 1 For each pair of vertices u H. let Eu,y be independent random variable such that
1, 11,7/max(55 d(u), d(v)) 1n(1 In(1/0agt) ( ))
Eu,y Lap
max
Eagr
We say that two vertices u + E H are i-noised agreement if (N(w)AN(v)) + E,, < iB. max(d(u) d(v)).
u and are in 1-noised agreement, we also say that and are in noised agreement; otherwise they are not in noised agreement. We say that an edge (u, v) is in noised agreement if its endpoints are noised agreemens.
Note that we do not require that (u, v) E E, although Algorithm I will only look at agreement of edges.
4 Analysis of Privacy
Our analysis proceeds by fixing two adjacent datasets G, G' (i.e., G and G' are graphs on the same vertex set that differ by edge) and analyzing the privacy loss of each step of the algorithm. We
5

---

Algorithm 1: Private correlation clustering using noised agreement
Input :G = (V, F):: a graph
6: privacy parameters
Let d(v) d(v) Zo denote the noised degree of where Z, ~ Lap((/ee. Let
= fo V d(vv== 2 To} denote the set high-degree vertices. Discard from G the edges that are not in noised agreement (see Definition 3.1 (First compute the set these edges. Then remove this set. Note that this includes all edges with an endpoint not in H.)
3 Let ((u) be the number of edges incident to e discarded in the previous step, and define
((v) ((v) + Yu, where Y, Lap(8/e). Call vertex light if ((v) > Ad(v), and otherwise call v heavy.
Discard all edges whose both endpoints are light. Call the current graph G or the sparsified graph. Compute its connected components. Output the heavy vertices in each component C' as a cluster. Each light vertex is output as singleton.
compose steps up to Line 3 by repeatedly invoking Lemma 2.2 analyzing the privacy of step, that the intermediate outputs (states randomness of the algorithm) up to that point are the same between the two executions. Finally, we use Lemma 2.3 argue that the intermediate outputs before [ine 4Jare the same, then the output of (iie.. the final output of Algorithm 1) does not depend on whether the input was G or G', except on a small fragment of the probability space that we can charge the additive error 6.
which allows us to assume, when
We begin the analysis by reasoning about I Lemma 4.1. ConsiderLine as randomized algorithm that oulputs H. It is (e/4,0)-DP.
Proof. The sensitivity Ad of the function d is 2, as adding an edge changes the degree of two vertices by 1. Therefore, by Theorem 2.6, d is (c/4, 0)-DP. Furthermore, H is a function that only depends on the input (set of edges) deterministically via d.
Now we fix adjacent G, G"; in this proof we will think that the domain of Algorithm is G = G) and the notion of ((. -DDP" always refers these two fixed imputs. Denote {xx y)} E(G)) to be the edge on which G and G' differ.
Lemma 4.2. Under fixed H, consider Line 2 as a randomized algorithm that, given or G', outputs the noised-agee agreement status of all edges in E(G) U E(G'). It is (2.9 )-P
Note that Algorithm only computes the noised agreem-egreeeett status of edges that are present in its input graph (which might be the smaller of the two), but without loss of generality we can think that it computes the status of all edges in E(G) E(G") (and possibly does not use this information for the extra edge).
In the proof of Lemma 4.2 we apply the Advanced Composition Theorem the noised-agreemmnn status edges incident on x or to argue that the Laplacian noise En of magnitude roughly / (m d(v)) is sufficient.
Proof. We will show that the sequence
(IN(u) + En,, B max(d(u),d(()) (u E B(G)UE(G")
(2)
(which determines the noised-agreement status of these edges) has the desired privacy guarantee.
Define F. to be those edges E(G) U E(G')) that are adjacent to I, but are not (æ, y), and F, similarly. The sequence (2) can be decomposed into four parts (with independent randomness): on (E(G) U E(G")) \ (En Ey), on Ez, on Ey, and on (I,y).
For the first part, the function
((N))) 3 max(dd()), d(v)): (u, v) (EGG)E(())) (E)EE)) has sensitivity 0, as for these edges we have {u, v) {z. = 0.

---

For the second part, we will show that the sequence
(I)))) + Ex,0 3 max(d(r), d(o)) : (2) E Ex)
(3)
(1.2 1.20 DDD.. To that end, we use the Advanced Composition Theorem (heorem 2.4). Let k | we have l d(x:) (note that d is the degree function of the input graph, which might be the smaller of G, G", but we also have (xr, y) & F.y). Thus the sequence (3) can be seen as a composition of l functions (each with independent randomness), each of which is sum of function (N) (v)l 3 max(d(x), d(v)), which has sensitivity at most 1 + B, and Laplace noise Eg,y. which has magnitude least
7 7Vk k- 1n(1/66g (n(g/6agr)
max
Cagr
(where we used (ax(d()), 2 d(x) k). Define e, to be the inverse of this value, i.c.,
Eagr
6x = min min
1, Tykk In(1/dagr)
Thus by Theorem 2.6 each of the functions is ((1 + f)z,, 0)-DP. By Theorem 2.4 sequence is ((1 + B) B)c,, Oage DDP, where
2k In( (o(L//agree, + ke
V2 Cage
+2ke2
?
V2 Eagr
2
Eage
2k
122 (0gr)
Cagz
where for the first inequality we used that e (1+9) < 2e, for e, E [0, 1] since 3 < 0.05, and the last equality follows by substituting the value of (see Detinition 3.1) and reducing; our setting of ? in fact obtained by solving the quadratic equation 22cang
2e
7 In((1/0mg)) Eage.
Finally, we have 1 + 3 < 1.2, and thus the sequence 3 is (1.2eagr ) The third part is analogous to the second.
For the fourth part, the sensitivity of the function |N [N()) 3 max(d(x), d(y)) is 2 (when edge (x, y) is added, x and y disappear from (x)AN(()) and max(d(x), d(y)) increases by 1). The Laplace noise ExtY yields (e", ,0) -)ddifferenttal privacy with
(2 + B)
2.2 agr
0.5cagr
TV (5, d(x)) d(u)) In(1/8Ag)) V2 /5 5 ln(10)
where we used that B < 0.2, 2 /2 and dage < 0.5 < 0.1.
Finally, we have a composition of four mechanisms with respective guarantees (0, 00, (1.20agr Bage) (twice), and (0.5 0), and we can conclude proof the lemma using Lemma 2.2
Next we turn our attention Line
Lemma 4.3. Under fixed noised-agreement status of all edges in E(G) U E(G', consider Line 3 as a randomized algorithm that, given G or G', outputs the heavyllggtt status of all vertices. It is (e/4, D).
Proof. Under fixed noised-agreemmet status of all edges in F(G))F((G)) the function (I(x) - -x-(vv)
E V) is deterministic and we can reason about its sensitivity, which is at most max (X, 1- 1) < (when edge (x, y) is added, the degrees d(x) and d(y) increase by and 1(x), ((y) possibly increase by if x and y are not in noised agreement). Therefore the sequence (I(v) A d(v) v V) is (e/ 4, -D by Theorem 2.6, and determines the heavy/light status of all vertices.
7

---

Now we analyze the last line
Line 4).
Theorem 4.4, By state let us denote the noised-ar noised-agreemen agreement status of all edges in E(G)UE(G") and heavy/lgght status of all vertices. Under a fixed state, consider Line 4 as a deterministic algorithm that, given G or G', outputs the final clustering. Then this clustering does not depend on whether the imput graph is G or G', except on set of states that arises with probability at most 2 (when steps before Line 4 are executed on either of G or G.).
Appendix A.2 is devoted to the proof of Theorem 4.4 Here, to get a flavor the arguments, let us showcase what happens in the case when r and y are both heavy. If they are not in noised agreement, we are done; otherwise, the edge (zx y) impacts the final solution only x and y are not otherwise connected in the sparsified graph G. However, they are in fact likely to have many common neighbors in G. as they are in noised agreement and both heavy. Indeed, all noise were zero, this would mean that N (xx) (y) is large fraction of
d(y)) and that and y do not lose many neighbors in Line 2 We show that with probability 1 (6), all relevant noise is below a small fraction of max (d (x) ( d(w)), and the same argument still applies. To get this, it is crucial that the agreement noise e of magnitude only roughly / //ma((d (), d(v)) (as opposed to e.g. max(d(u), d(v))).
Once we have Theorem 4.4, Theorem 4.5. Algorithm 6).
we can conclude:
Proof. We repeatedly invoke Lemma 2.2 to argue that the part of Algorithm 1 consisting of Lines (that outputs noised-agreement and heavy/light statuses) is (e/4, 0) + (2.9 2.45 2.44prr2244.mr + (e/4, 0) (e, 6/ -DP by Lemmas 4. 1o to 4.3 (recall the setting of cagr and öagr in Definition 3.1). To conclude
the proof, we argue about the last step using Lemma 2.3 and Theorem 4.4, which incurs a privacy loss of (0, 6).
5 Analysis of Approximation
Vxv and Ā = Ry, let ALG-CC(3, be the algorithm from (CALM+21 that For vectors 3 E 20
uses Ba,e to decide an agreement between u and u and uses X, to decide whether v is light or heavy, Let ALG-CC(3, X, Evem) (stated as Algorithm 2) be variant of ALG-CC (,, that at the very first step removes Erems then executes the remaining steps, and finally (as in Algorithm 1) outputs light vertices singleton clusters.
Algorithm 2: ALGG-CC(3, Frem), used for the approximation analysis.
Input :G (V, F)): graph
3 R VxV agreement parameter
E RV, threshold for light vertices
Erem subset of edges to be removed
Remove the edges in Erem-
Discard from G the edges that are not in agreement, where u and v are in agreement if
IN (N) (u)AN(()) < Br,r max(d((), d(()). (First compute the set of these edges. Then remove this set.)
3 Let 1(v) be the number of edges incident to e discarded in the previous steps. Call a vertex u light if (vv) > Xv)(v,, and otherwise call e heavy.
Discard all edges whose both endpoints are light. Call the current graph G or the sparsified graph. Compute its connected components. Output the heavy vertices in each component C' as cluster. Each light vertex is output singleton.
The strategy of our proof is to map the behavior of Algorithm to the that of ALG-CC(B, X, E for carefully chosen 3, X, and Evem- We remark that ALG-CC is not actually executed by our DP- approach, but it is rather a hypothetical algorithm which, when appropriately instantiated, resembles approximation guarantees of olgolthm T] Moreover, ALG-CC has similar structure to the approach of 22) enabling to reuse some of the results from that prior work to establish approximation
8

---

guarantees for ALG-CC. We emphasize that the approximation guarantee from prior work we build on invoked black-box manner and the analysis presented in this paper is self-contained.
We begin by showing certain monotonicity properties with respect to input parameters B and À of ALG-CC. Given two vectors I and y labeled by a set S, we say that T S y iff Eg S V, for each S.
Lemma 5.1. Let ,3, E VXV and XL, , E
RY 20 such that 3U 2 BL and X 2 X
(i) u and u are in the same cluster of ALG-CC N Erem), then u and u are in the same cluster of ALG-CC(BU, Nu, Erem).
(ii) If u and are in different clusters of ALG-CC((U X8 Erem), then and different clusters of ALG-CC(3L, X Erem)-
The proof of Lemma 5.1 is given in Appendix B.I We now derive the following claim that enables us to sandwich cost (ALG-CCI X, ) between two other instances of ALG-CC.
Lemma 5.2. Let B,,,8 B3 E TR. 2 Then
V and XE, X, X E TR such that BB 2 B 2 BL and X 2 A
cost(ALG-CCBB) X, ))em))= cost(ALG-CC(B)) A Erem)) +
AL, Erem))
Proof. We first bound the cost of ALG-CC(3, Erem) incurred by "-" edges. If a "_" edge {u, 1} adds to the cost of clustering, it because u and v are the same cluster. Lemma 5.1 ( if and are in the same cluster of ALG-CC(B, X, Ermm) then they are in the same cluster of ALG-CC(BU XU, Eiem) as well. Hence, the cost of ALG-CC(3, X, Exem) incurred by s_" edges is upper-bounded by cost(ALG-CC(a) ,r,Eme)))
In a similar way, we upper-bound the cost of ALG CC, A, Evem) incurred by "+" edges by cost (ALG-CC(3L, X7, Eyem)). If a "+" edge fu. v) adds to the cost of clustering, it is be- cause u and v are different clusters. By Lemma 5.1 (ii), if u and v are different clus- ter of ALGG-CC(3, X, Frem), then they are in different clusters of ALG-CC(BL, X Frem) as well. Hence, the cost of the output of ALG-CC(3, A, Erem) incurred by "+" edges upper-bounded by cost(AL.co (ALLGG-C(C35 24, Frem)).
We now analyze the effect of removing edges incident vertices which are not in H defined on Line I of Algorithm I To simplify the analysis, we first ignore the step that outputs light vertices as singletons (Line of Algorithm annd Line 4f Alggorith 2p. For threshold T' Rgo let EsT subset of edges incident to vertices of degree at most
Lemma 5.3. Ler Algorithhmm 7 be version of Algorithm that does not make singletons of light vertices on Line 4 Assume that 5,3 + 2X < 1/1.1 and also assume that 3 and X are positive constants. With probability least n 2 Algorithm provides a solution which has O(1) multiplicative log log" (1/8) min(1.e"
and O
Th
additive approximation.
The proof of Lemma 5.3 is given in Appendix B.2 Lemma 5.3 does not take into account the cost incurred by making singleton-clusters from the light vertices, as performed on Line of Algorithm The next claim, whose proof is deferred to Apppeddix B.3, upper-bounds that cost as well.
Lemma 5.4. Consider all lights vertices defined in Line 4 of Algorithm 1 Assume that 5,3 2X < 1/1.1. Then, with probability at least 1 - n -2, making as singleton clusters any subset of those light vertices increases the cost of clustering by O(OPT/ >)²), where OPT denotes the cost of the optimum clustering for the input graph.
Combining Lemmas 5.3 233and 5.4 derive our final approximation guarantee.
Theorem S.5. Assume that 5,3- 2A < 1/1.1 and also assume that 3 and À are positive constants. Then, with probability at least n
< ((PT)) + +0 m log n log" (olog(1/))) min(1,"
cost AadoAllgoitmm

---

Future Work
natural to ask whether our algorithm is scalable and whether it might achieve good approxi- mation for real-worid datasets. To begin with, one might worry that our theoretical upper bound on the multiplicative approximation ratio a large constant. However, the practical approximation performance of the algorithm [CALM 211, which we build upon, has been shown to be very good (superior to pivot-based algorithms), even in regimes of parameters 8 and À where the theoretical bounds are not guaranteed to hold. Moreover, our algorithm is efficient and easy to implement.
Unfortunately, the additive approximation term is problematic. Recall that return as singletons all vertices whose (noised) degree is below a threshold To- To get our theoretical bounds on approx- imation, we require To be polylogarithmic we could forgo these bounds in lieu of hoping for good practical performance. However, we cannot proceed similarly with respect privacy; and To still needs to be a large constant in order to obtain our privacy guarantees (see Section 3 for more details on To). Due to this, for most settings of c and 8, unless the dataset very dense, the output of our algorithm will be close to that of the trivial (0, O>-DP algorithm that returns only singleton clusters.
n. Motivated by the experiments of [CALM 21].
We remark that the other known works differentially private correlation clustering also do not provide experimental evaluations, and they seem difficult to use in practice. The algorithm [BEK2T] involves approximately solving an exponential-size linear program using semidefinite programming inside a separation oracle. Liu [Liu22], similarly to us, outputs as singletons all vertices with degree below large polylogarithmic threshold. We believe that designing practically efficient and scalable algorithm for differentially private correlation clustering is a compelling open research direction.
On the theoretical side, it would be interesting to see whether our additive approximation bound can be improved in terms of the log" factor, well as the quadratic dependence on 1 1/c. Also, perhaps our lower bound (Theorem 1.2p can be strengthened, c.g. to (nn/e) as in [BEK21]. Furthermore, [CALM*2] can be implemented in O(1) parallel (MPC) rounds, it is natural to ask whether this approach can lead to an algorithm that is both parallel and private. Finally, we do not address version) of correlation clustering in this paper; in particular, finding a DP algorithm with optimal additive guarantee for weighted inputs is an interesting follow-up question.
the general weighted setting (nor the mexiiuum-agreente
References
[ACN08] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent informa- tion: ranking and clustering. Journal of the ACM (JACM), 15(5):1-27, 2008.
[AHK + 09] Rakesh Agrawal, Alan Halverson, Krishnaram Kenthapadi, Nina Mishra, and Panayi- otis Tsaparas. Generating labels from clicks. In Proceedings of the Second ACM International Conference on Web Search and Data Mining, pages 172-181, 2009.
[ARS09] Arvind Arasu, Christopher Ré, and Dan Suciu. Large-scale deduplication with con- straints using dedupalog. In 2009 IEEE 25th International Conference on Data Engineering, pages 952-963. IEFF, 2009.
[AU19] Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Informa- tion Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13378-13389, 2019.
[AW22] Sepehr Assadi and Chen Wang. Sublinear time and space algorithms for correla- tion clustering via sparse-dense decompositions. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 February 3, 2022, Berkeley, CA, USA, volume 215 of LIPles, pages 10:1-10:20. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022.
[BBC04] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56(1):89-113, 2004.
2004.
10

---

[BBDS12] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The johnson- lindenstrauss transform itself preserves differential privacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 410-419, IEEE Computer Society, 2012.
[BBDSI3] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 87-96. ACM, 2013.
[BCSZ18] Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. Revealing network structure, confidentially: Improved rates for mode-private graphon estimation. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Com- puter Science, FOCS 2018, Puris, France, October 7-9, 2018, pages 533-543, IEEE Computer Society, 2018.
[BDL+17] Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differentially private clustering high -ishdimmenionall euclidean spaces. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Leurning, ICML, volume 70 of Proceedings of Machine Learning Research, pages 322-331. PMLR, 2017.
[BEK21] Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In International Conference on Machine Learning, pages 1136-1144 PMLR, 2021.
[BGU13] Francesco Bonchi, Aristides Gionis, and Antti Ukkonen. Overlapping correlation clustering. Knowledge and information systems, 35(1):1-32, 2013.
[BNSV15) Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 634-649. IEEE Computer Society, 2015.
[CALM*21] Vincent Cohen-Addad Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fart Nikos Parotsidis, and Jakub Tarnawski. Correlation clustering in constant many parallel rounds. In International Conference on Machine Learning, pages 2069-2078.
PMLR, 2021.
[CALN22] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation clustering with sherali-adams. In IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, 2022.
[CGKM21] Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. CoRR, abs/2104.09733 2021.
[CGW05] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualita- tive information. Journal of Computer and System Sciences, 71(3):360-383, 2005.
[CKPO8] 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, pages 377-386. 2008
[CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal Ip rounding algorithm for correlationclustering on complete and complete k- k-partite graphs. In Proceedings of the ferth-seventh annual ACM symposium on Theory of computing, pages 219-228, 2015.
[CNX20] Anamay Chaturvedi, Huy L. Nguyen, and Eric Xu. Differentially private k-means clustering via exponential mechanism and max cover. CoRR, abs/2009.0122 2020.
[CSX12] Yudong Chen, Sujay Sanghavi, and Huan Xu. Clustering sparse graphs. In Proceedings of the 25th International Conference on Neural Information Processing Systems- Volume 2, pages 2212- 2012.

---

[DEFI06] Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172- 187, 2006.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265 225.284.22 Springer, 2006.
[DR+14] 14] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211 1-407, 2014.
[DRVI0] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51-60, 2010.
[Dwo06] Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings. Part II, pages 1-12, 2006.
[BKKL200] Marek Fliás, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the 2020 ACM-SIAM Symposium Discrete Algorithms,, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 560-578, 2020.
[FHS21] Alireza Farhadi. MohammadTaghh Hajiaghayi, and Elaine Shi. Differentially private densest subgraph. CoRR, abs/2 106.00508. 2021.
[GGO5] loannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. arXiv preprint cs/0504023, 2005.
[GKM20] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Ties Lin, editors, Advances in Neural Information Processing Systems, 2020.
[GLM+10) 10] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1106-1125, 2010.
[GRU12] Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Ronald Cramer, editor, Theory of Cryptography 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, volume 7194 of Lecture Notes in Computer Science, pages 339-356. Springer, 2012.
[HLMJ09] Michael Hay, Chao Li, Gerome Miklau, and David D. Jensen. Accurate estimation of the degree distribution of private networks. In Wei Wang, Hillol Kargupta, Sanjay Ranka, Philip S. Yu, and Xindong Wu, editors, ICDM 2009, The Ninth IEEE Interna- tional Conference Data Mining, Miami, Florida, USA, 6-9 December 2009, pages 169-178. IEEE Computer Society, 2009.
[KCMNT08] Dmitri V Kalashnikov, Zhaoqi Chen, Sharad Mehrotra, and Rabia Nuray-Turan. Web people search via connection analysis. IEEE Transactions on Knowledge and Data Engineering, 20(1 20(11))555--155, 2008
[KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. Amit Sahai, editor, Theory of Cryptography- 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013, Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 457-476. Springer, 2013.
12

---

[KRSY1I] Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. Proc. VLDB Endow., 4(11):1146-1157, 2011.
[Liu22] Daogao Liu. Better private algorithms for correlation clustering. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK. volume 178 of Proceedings of Machine Learning Research, pages 5391-5412. PMLR, 2022.
[LS20] Zhigang Lu and Hong Shen. Differentially private k-means clustering with guaranteed convergence. CoRR, abs/2002.01043, 2020.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94-103, 2007.
[NV21] Dung Nguyen and Anil Vullikanti. Differentially private densest subgraph detection. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8 $140-8151. PMLR, 2021.
[RHMS09] Vibhor Rastogi, Michael Hay, Gerome Miklau, and Dan Suciu. Relationship privacy: output perturbation for queries with joins. In Jan Paredaens and Jianwen Su, editors, Proceedings of the Twenty-Eigth ACM
Symposium on Principles of Database Systems, PODS 2009, June 19 July 2009, Providence, Rhode Island, USA, pages 107-116. ACM, 2009.
[Swa04] Chaitanya Swamy, Correlation clustering: maximizing agreements via semidefinite programming. In SODA, volume 4, pages 526-527. Citeseer, 2004.
[US19] Jonathan Ullman and Adam Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett, editors, Advances Neural Information P Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 3765-3775, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "kX3s3wqHi-f", "reviewer": "Reviewer_d5Yt", "summary": "The authors applied differential privacy to correlation clustering, using graph notations. They first added noise to the degree of vertices and discarded edges using the definition of noised agreement. The authors added noise to the number of edges and defined a vertex is light or heavy. Finally, they discarded the edge and output the heavy vertices in a cluster. Also, the authors proposed approximated method.", "questions": "I’ve never seen the term “(0,0)-differential private” before(In the proof of Lemma 4.2). Is it widely used? If not, what about using post-processing or saying \"it does not spend privacy budget\"? ", "limitations": "The authors assumed every weight of an edge is -1 or  1. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n- The authors carefully analyzed to support their argument, and provided time complexity.\n- The authors applied differential privacy to recent work, especially using noised agreement have novelty.\n\n[Weaknesses]\n- There are some minor issues in the paper. For example, in lines 20-21, the authors need to say the sum of the “absolute value” of negative edges to prevent confusion.\n- It seems that the privacy budget is wrongly calculated. In Line 1 of Algorithm 1, the authors added noise to every d(v). Since d(v) = |N(v)| where N is the set of neighbors of a vertex v, d(v)s(for v in V) are not independent, the privacy budget is accumulated by composition theorem. This implies the privacy budget is higher than the authors argued, exactly |G|/2 times higher than expected(The sensitivity of d is 2, as mentioned in line 227, and the sensitivity of d(v) is 1).\n- It would be better if the authors change the arXiv references in the final submission. For example, [CALM+21], which appears to have motivated the authors is accepted by ICML.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h_rRJe89XX", "reviewer": "Reviewer_rmrh", "summary": "The authors develop an approximation algorithm for correlation clustering in complete unweighted graphs with privacy guarantees. The additive error of their algorithm is stronger than prior work, while it is optimal up to polylogarithmic factors. It also matches the additive error of the exponential mechanism up to a logn factor. They also show that linear error is necessary even for complete unweighted graphs and (eps,delta)-privacy.", "questions": "-", "limitations": "No negative societal impact, as far as I could check. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n- the paper is very well written and organized\n- the additive error of their algorithm is stronger than prior work and optimal, up to polylog factors. To this end, the authors also prove that linear error is necessary even for complete unweighted graphs.\n- the authors borrow some ideas from [CALM21], however, a deeper analysis of the algorithm in [CALM21] and several novel ideas are developed. \n\nWeaknesses:\n- their results seem to only apply to complete unweighted graphs (in contrast to [BEK21] and [LIU22] )\n- some of the ideas were presented in [CALM21], however, the paper contains significant novel contributions", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MVw89PGCaZk", "reviewer": "Reviewer_SoYq", "summary": "The paper discusses the min-disagree correlation clustering problem. It gives an (\\eps, \\delta)-differentially private algorithm that provides O(1) multiplicative and O(n log^2n) additive approximation. The additive approximation is close to the optimal bound of \\Omega(n), which is also shown in the paper. Theorems 1.1 and 1.2 appropriately summarise the main results of the paper. ", "questions": "Even though the theoretical results in the paper are appreciated, it may be nice to have a discussion on the applied aspects of the results. Are there specific application scenarios where the results of this paper may be useful?", "limitations": "The work is theoretical. I do not see any negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The paper gives an improvement over previous work, improving the additive approximation guarantee. \n- The lower bound result also improves the previously known results.\n- The intuition behind the algorithm and the analysis is presented well.\n\n\nWeaknesses: \n- I do not find any significant weakness in the paper. One aspect that may not appeal to practitioners is that the results in this paper are theoretical. There are no experimental evaluations presented.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HEPeJE3Hfq-", "reviewer": "Reviewer_Kj4P", "summary": "This paper studies the correlation clustering problem under edge differential privacy constraints. In the correlation clustering problem, given a complete graph with + and – labels on the edges, the goal is to partition the vertices so as to minimize the number of + edges between parts, plus the – edges inside parts. With edge differential privacy (DP), Given two graphs on the same set of vertices that differ in only one edge, the goal is to make sure, for any set of outcomes of an algorithm, the probability of returning that outcome is roughly the same (within a multiplicative $e^\\epsilon$ and additive $\\delta$) for both graphs. This problem was studied by BEK21 where they give an $(\\epsilon, \\delta)$-DP algorithm that approximates the optimal clustering cost (OPT) with cost $O(1) OPT + O(n^{1.75}log(n/\\delta)/\\epsilon)$. There is also a concurrent paper of Liu22 with the additive term of $\\tilde{O}(n^{1.5}log(n/\\delta)/\\sqrt{\\epsilon})$. BEK21 also prove an $\\Omega(n)$ lowerbound on the additive approximation of DP algorithms on path graphs.\n\nThis paper improves the additive term to $O(nlog^2(n)log(n/\\delta)/{\\epsilon}^2)$. Inspired by CALM+21’s paper on correlation clustering in the parallel setting, they make the steps in that algorithm private in such a way to make sure the cost approximation remains within the mentioned bound. They also add to the lowerbound results by proving a linear lower bound on the approximation in complete unweighted graphs.\n", "questions": "As mentioned above, I recommend the authors elaborate on various aspects of the performance of their algorithm.", "limitations": "I do not see any serious limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem considered in this paper is natural and important. The paper is very well written, and the ideas are clearly presented. Although I did not check all the proofs in detail, the logic seems solid to me. The paper borrows ideas from the literature, but they had to do nontrivial work to prove the DP and cost guarantees.\n\nMy only comment for the authors is to elaborate on how well the algorithm scales. How parallelizable it is, or maybe bring empirical studies to argue about this. In general, this paper could benefit from empirical studies on how well the algorithm actually performs in practice. For example, the dependence on $\\epsilon$ is quadratic, what are some ranges of $\\epsilon$ that are used in practice. Or in general, please elaborate on the significance of your result in the real-world setting. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept