A Differentially Private Clustering Algorithm for Well-Clustered Graphs
Authors: Weiqiang He
Hendrik Fichtenberger
Pan Peng
Venue: ICLR 2024 poster (2024)
Keywords: differential privacy
graph clustering
semidefinite programming
spectral clustering
Primary area: societal considerations including fairness, safety, privacy
TL;DR: Differentially private spectral clustering that nearly matches non-private bounds

Abstract: We study differentially private (DP) algorithms for recovering clusters in well-clustered graphs, which are graphs whose vertex set can be partitioned into a small number of sets, each inducing a subgraph of high inner conductance and small outer conductance. Such graphs have widespread application as a benchmark in the theoretical analysis of spectral clustering.
We provide an efficient ($\epsilon$,$\delta$)-DP algorithm tailored specifically for such graphs. Our algorithm draws inspiration from the recent work of Chen et al., who developed DP algorithms for recovery of stochastic block models in cases where the graph comprises exactly two nearly-balanced clusters. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters, and the misclassification ratio almost matches the one of the best-known non-private algorithms. We conduct experimental evaluations on datasets with known ground truth clusters to substantiate the prowess of our algorithm. We also show that any (pure) $\epsilon$-DP algorithm would result in substantial error.

Published as a conference paper at ICLR 2024
A DIFFERENTIALLY PRIVATE CLUSTERING ALGO- RITHM FOR WELL-CLUSTERED GRAPHS
Weiqiang He'
Hendrik Fichtenberger"
Pan Pengl
'School of Computer Science and Technology, University of Science and Technology of China
Google Research
hwghwq@mail ustc. edu.cn
fichtembbrrgrr@goollecco
ppengeustc. edu.
ABSTRACT
We study differentially private (DP) algorithms for recovering clusters in well- clustered graphs, which are graphs whose vertex set can be partitioned into small number of sets, each inducing a subgraph of high inner conductance and small outer conductance, Such graphs have widespread application as benchmark in the theoretical analysis of spectral clustering. We provide an efficient (c,5)-DP algorithm tailored specifically for such graphs. Our algorithm draws inspiration from the recent work Chen et al. [NeurIPS who developed DP algorithms for recovery of stochastic block models in cases where the graph comprises actly two nearly- clusters. Our algorithm works for well-clustered graphs with nearly-balanced clusters, and the misclassification ratio almost matches the one of the best-known non-private algorithms. We conduct experimental evalua- tions on datasets with known ground truth clusters to substantiate the prowess of our algorithm. We also show that any (pure) c-DP algorithm would result in substantial error.
INTRODUCTION
Graph Clustering is a fundamental task in unsupervised machine learning and combinatorial opti- mization, relevant to various domains of computer science and their diverse practical applications. The goal of Graph Clustering is to partition the vertex set of a graph into distinct groups (or clus- ters) so that similar vertices grouped in the same cluster while dissimilar vertices are assigned to different clusters.
There exist numerous notions of similarity and measures of evaluating the quality of graph cluster- ings, with conductance being one of the most extensively studied (see c.g. (Kannan et al. 2004] Von Luxburg 2007 Gharan & Trevisan 2012)). Formally, let G (V, F)) be undirected graph. For any vertex u E V, its degree is denoted by do(u), and for any set S C V. its volume is vola(S) Enes (u). For any two subsets S.T C V, we define E(S, be the set of edges
between S and T.. For any nonempty subset C C V, the outer conductance and inner conductance defined by
oo (G, V vola(C)
min (G, SCC.vola(SS wl
4 (C,
Intuitively, vertex set C has low outer conductance, then it has relatively few connections to the outside, and if it has high inner conductance, then it is well connected inside. Based on this intuition, Gharan & Trevisan (2014) introduced the following notion of well-clustered graphs. A k-partition of a graph G (V,E) F.) is family of k disjoint vertex subsets CI,..., Cs of V such that the union U C2 = V. If there is some constant c E (0, 1] such that for every i [k]] volo(C.) > evola(G) 2em is satisfied, we call the k-partition (Ci)ie(k) c-balanced.
=
Definition 1.1 (Well-clustered graph). Given parameters k > 1, dim, Dna [0, 1). graph G (V, F)) is called (ki, Om, )ow) cclsttrblee if there exists a k-partition (Ci)veln) of V such that for
"Corresponding Author

---

Published as a conference paper at ICLR 2024
all [k], (Gn Qin and 4 oan C.) S Pow. Furthermore, if (Ciheeta) is c-balanced, G = (V, F)) is called e-halanced (ki Din clusterbbbe.......
If k-partition {Ci)ejk) satisfies the above two conditions on the inner and outer conductances, then we call the partition a ground truth partition of G. Gharan & Trevisan (2014) give a simple polynomial-time spectral algorithm to approximately find such partitioning. Since then, a plethora of works has focused on extracting the cluster structure of such graphs with spectral methods (see Section 1.1 For example, Czumaj et al. (2015): Peng et al. (2013); Chiplunkar et al. (2018); Peng (2020) Gluch et al. (2021) used well-clustered graphs as theoretical arena to gain better understanding of why spectral clustering is successful. They showed that variants of the widely used spectral clustering give good approximation of the optimal clustering in well-clustered graph.
In this paper, we study differentially private (DP) (see Definition 2.1 for the formal definition) al- gorithms for recovering clusters in well-clustered graphs. DP algorithms aim to enable statistical analyses of sensitive information on individuals while providing strong guarantees that no infor- mation of any individual is leaked (Dwork et al. 2006). Given the success of spectral methods for clustering graphs in non-private settings, surprisingly little is known about differentially private spectral clustering. Finding ways to leverage these methods in privacy-preserving way gradually bridges differential privacy and an area of research with many deep structural results and a strong toolkit for graphs. In this line of research, we obtain the following result.
Theorem 1. Let G = (V, E) be a c-balanced (k, Oins Doma) cllusteraale graph with its ground truth Then, there exists an algorithm that, for any c, k, Dins Dout
partition {C, (Ei) where tha = =O(k-) 4%
and graph G with n vertices and m 2 n
log(2/6)
edges that satisfies the preceding properties,
outputs k-partition ( such that
13 Done T
volg (CLC(C))C)))) -
vooa(Ca(()); for any i < k.
with probability 1 exp(-I((n)) where is a permutation over [K] := {1.....k). k}. Moreover, the algorithu is () for any input graph with respect to edge privacy and runs in polynomial time.
For more general trade-off between the parameters ā and the misclassification ratio of our al- gorithm, we refer to Lemma 4.3 We stress that the privacy guarantee of our algorithms holds for any input graph, and in particular, it does not depend on a condition that the graph is clusterable. In the non non-private setting, the best-known efficient algorithms achieve O Oout/ / misclassifica- tion ratio (for general well-clustered graphs) under the assumption that @our// [ 0 Okk33) (Peng et al. 2015). Thus, for balanced well-clustered graphs, our private algorithm almost matches the best-known non-private one in terms of approximate accuracy or utility.
Our private mechanism is inspired by the recent work of Chen et al. (2023). We design a simple Semi-Definite Program (SDP) and run spectral clustering on a noisy solution. To analyze our al- gorithm, extend the notion of strong convexity and prove the stability of the SDP. This allows us to show that the solution of the SDP has small sensitivity. In differential privacy, sensitivity is measure of how much function's 's value changes for small, but arbitrary and possibly adversar- ial changes in the data. For the non-private SDP solution, we show that applying classical privacy mechanisms and spectral clustering yields a differentially private clustering algorithm. Based on the analysis by Peng et al. (2015), we prove that our differentially private clustering algorithm achieves an approximate accuracy that nearly matches the non-private version. Furthermore, we remark that Chen et al. (2023) give a DP algorithm for recovery of stochastic block model (SBM) in cases where the graph comprises exactly two nearly-balances clusters. Our algorithm achieves a similar approx- imation accuracy to their weak recovery and supports l clusters.
To complement our results, we conduct an experimental evaluation on datasets with known ground truth clusters to substantiate the prowess of our algorithm. Furthermore, we show that any (pure) cDDP algorithm entails substantial error in its output (see Appendix D).
Theorem 2 (informal). Any algorithm for the cluster recovery of well-clustered graphs with failure probability y and misclassification rate cannot satisfy c-D
2la(T²z) on d-regular graphs.
d.
Sttictly speaking. Peng et al. (0055) stated their result in terms of so-called quantity T, which can be lower bounded by / Doa by higher Cheeger inequality (Lee al. 2014).
2

---

Published as a conference paper at ICLR 2024
This lower bound implies that, e.g., there is no e-DP algorithm for c (11) that misclassifies only a constant fraction of the input. On the other hand, Theorem confirms the existence of such an algorithm for (c, 6D.
1.1 RELATED WORK
Our results combine spectral clustering and differential privacy. After Dwork et al. (2006) system-
atically introduced the notion of differential privacy, various clustering objectives have been studied in this regime. Differentially private metric clustering (e.g., k-clustering) was studied in Nissim
al.] 20007: Wang al. (2015); Huang & Liu (2018); Shechner et al. (2020); Ghazi et al. (2020).
Correlation Clustering with differential privacy has been the subject of more recent works, e.g., Bun
al. (2022). In machine learning, the SBM and mixture models are used to model and approximate properties of real graphs. Differentially private recovery of these graphs or their properties has been studied in |Hehir et al. (2022): ) Mohamed et al. (2022);
al. (222T) Liu 2022); Cohen-Addad
Chen et al. ) Seif et al. (2023).
Spectral methods for graphs have long track of research that started before differential privacy was widely studied. One of the first theoretical analyses of these methods appeared in Spielman & Teng (196),. followed by several others, c.g., Von Luxburg 2007]; Gharan
Gharan & Trevisan (2014); Peng et al. 2015; ; Kolev & Mehlhorn ( Dey et al. (2019); Mizutani
22221). Indeed, there has been long line of research aiming at designing efficient algorithms for extracting clusters with small outer conductance (and with high inner conductance) in graph (Spielman & Teng [2004] Andersen al.)
2006 Gharan & Trevisan 2012] Zhu et al. 2013). Privacy-preserving spectral methods have been studied rather recently (Wang al. (2013); Arora & Upadhyay (2019); Cui et al. (202T)).
For well-clustered graphs, spectral clustering is the most commonly used and effective algorithm, which operates in the following two steps: (1) construct spectral embedding, mapping vertices into a k-dimensional real space. (2) use k-means or other algorithms to cluster the points in Euclidean
space. Spectral clustering has been applied in many fields and has achieved significant results (Alpert
& Yao
1995
Shi & Malik 2000) et al. [2001] Malik et al. 2001 Belkin & Niyogi 2001 Liu &
Zhang
2004
Zelnik-Manor & Peronal [2004] White & Smyth 2005 Von Luxburg 2007 Wang &
Dong
2012
Taşdemir] 2012 Cucuringu et al. 2016).
PRELIMINARIES
We use bold symbols to represent vectors and matrices. For vectors ut we define (u, v) V, its l norm and Eg norm,
u TTe v E, U, We denote by ||u||| == Σ, lusl. //ul|2 respectively. For matrices A and B, define B) = Ex, A., Denote by |AAll2 the spectral norm of A. Denote by ||A||| the Frobenius norm of A. A matrix A is said to be positive semidefinite if there matrix V such that A V V. denoted as A M Note that Aij = V; Uy. where vs is the i-th column of V and A is known as the Gram matrix of these vectors 8; i E [m]. For n 2 1, let [n] = .I.....n.. Let Diag(a1, ... , an) be the diagonal matrix with a1, 02 -r an on the diagonal. We denote N' (0. mxx as the distribution over Gaussian matrices with m x n entries, each having standard deviation a. For an n x m matrix M, we define the vectorization of M as the (n x m) middiennsional vector whose entries are the entries of M arranged in sequential order.
In this paper, we assume that G -V, E) is an undirected graph with |V| n vertices, |E| = m edges. For nonempty subset S C V. we define G[S] to be the induced subgraph on S and we denote by G(S) the subgraph G[S], where self-loops are added to vertices r E S such that their degrees in G' and G(S) are the same. For any two sets X and Y. the symmetric differ- ence of X and Y is defined as XAY == (X Y) UY \ X). For graph G = (V, E). let De Diag(do (1)))) (,))))d(())) (c())) ...
We denote by Ag the adjacency matrix and by Le the Laplacian matrix where LG = De - Ag. The normalized Laplacian matrix of G is defined by LG = 1:-1" LGD
Differential Privacy We consider edge-privacy and call two graphs = (V, E) and G' = =V', E') neighboring if it holds that V V' and [(E) U (E' \ E)] < 1. The definition of differential privacy is as follows:
3

---

Published as a conference paper at ICLR 2024
Definition 2.1 (Differential privacy). A randomized algorithm M is (c, -dfffeerreel private if all neighboring graphs G and G' and all subsets of outputs S. Pr[M(G) E < Pr([M( E S] + 6, where the probability is over the randomness of the algorithm.
DP mechanisms typically achieve privacy by adding noise, where the magnitude of the noise de- pends on the sensitivity of the function.
Definition 2.2 (Sensitivity of a function). Let f + -eessiiivvy and fz-sensifivity of are defined respectively as
RRd with domain 'D be a function. The
AS,
max
-(Y")l
max Y.Y'D ED
Y.YED ED
Y Y are neighboring
Y neighboring
Gaussian mechanism one of the most widely used mechanisms in differential privacy.
Lemma 2.3 (Gaussian mechanism). Let f D gd with domain D be an arbitrary d-dimensional function. For 0 < e, 5 S 1, the algorithm that adds noise scaled to N (0. A 2/.221og(// to each of the d components of f is (c, 6).P.
e²
k-means and spectral clustering Given set of n points Fi..... F, R the objective of k- means problem is to find a k-partition of these points, C = (CI C+). such that the sum of squared distances between each data point and its assigned cluster center (i.e., the average of all points in the cluster) is minimized. This optimization problem can be formally expressed as arg mine E/= Euec: [u- 1 Exec, -
It is known there exist polynomial time algorithms that approximate the optimum of the k-means within constant factor (see e.g. Kanungo et al. 2002 ; Ahmadian et al. (2019).
[c,
Peng et al. (2015) proved the approximation ratio of spectral clustering when eigenvectors satisfy certain properties. They showed the following lemma, whose proof is sketched in Appendix B
Lemma 2.4 (Peng et al. 2015 ). Let G = -V, E) be a graph and l E N. Let F - R² be the embedding defined by F Fuu) Vaolu) (fr (u).... ... fu(u)) where (fi is a set of orthogonal
bases in TR.. Let (S.) be a k-partition of G, and (ā: Vi be the normalized indicator vectors of the clusters {S:) where ge(u)= v de(u)
(5,) if E St, and ge(u) 0 otherwise. Suppose there is threshold 0 5% such that for each E [k]. there exists a linear combination of the
eigenvectors 91,- 9h with coefficients 8 9 3 g1 + g ghe and for each i E [k]],
llf: - 02 < A.
Let KMEANS be any algorithm for the k-means problem in R with approximation ratio APT. Let {A:) be a k-partition obtained by invoking KMFANS on the impul set { ((uu))uv Then, there exists a permutation a on {1,...,k] k)) such that vol (A,A..AA) = O(APT k2 (2) ( holds for every i [k].
3 STABILITY OF GENERALIZED STRONGLY CONVEX OPTIMIZATION
The following is a generalization of a result in Chen et al. (023) whose proof is deferred to Ap- pendix C It shows that if the objective function of SDP is generalized strongly convex (see Def- inition C.2) for some diagonal matrices D, and D2, then the fz-sensitivity of the sealed solution can be bounded by the f-sensitivvtty of the objective function.
Lemma 3.1 (Stability of strongly-convex optimization). Let y be a set of databases. Let K(Y) be family of closed convex subsets of R. parameterized by E y and let F(Y) be family of functions fy K((Y) + I, parameterized by Y EY, V. such that: (1) for adjacent databases Y, Y" E y, and X E XC(Y) there exist X' E KCYY') KC() satisfying (Xy ffy(X')) < a and (fr. fX') S a. (2) fy is (K, D1, D2) ja--strongly convex X E K(YY for some diagonal matrices D2 and D2 Then for Y,Y E X = arg x fy fY(X) and X" =
arg min ( fy. (x'(X'), holds D2DD2 - D2X'D, 1a0a--xX'DD < 12o
4

---

Published as a conference paper at ICLR 2024
4 PRIVATE CLUSTERING FOR WELL-CLUSTERED GRAPHS
In this section, we present our DP algorithm for well-clustered graph and prove Theorem
4.1 THE ALGORITHM
For e-balanced (ki, Pin, boau)-cllteerable graph G (V, E) with ground truth partition ([()))))- set -/2 Lijen), volc(C.)vol((C)) clusters have the same volume, then b = k-1
2m² Eie(y) volg(C.)?. Specifically, if all
We make use of the following SDP to extract the cluster structure of G. Note that the SDP assumes the knowledge of the parameter b, which has also been used in previous work (e.g., Guédon & Vershyyii (016)).
SDP (1)
SDP (2)
2 Σ (ū, ddddddddd)) a.VEV
min
Σ (u,))E
min X) + Am
D 1/2
Am
bm?
s.t.
(1/ū 8 (1dda())d
2 2bm
s.t. (DeLKV Da. x)
V.VVV
X 2 0, X;; 1 Vi
(u, 8) 2 0, for u, A. V
[ūll = 1, for VV
Intuitively, the SDP ensures significant sum of vector distances for all pairs of vertices, and the objective is to minimize the vector distances between endpoints of all edges, thereby achieving a configuration where inter-class vector distances large and intra-class vector distances small.
Let X be 1 times the Gram matrix these vector U1 U2. Un (i.c., X.,, 1 0; Uz). Lkv be the Laplacian of the complete graph set V. Let X 0 denote that all entries of X are non-negative. It is easy to see that the SDP (T) can be equivalently written in the form of SDP (2)
Bo.LyDDG.N Then the optimal solution of this SDP can be expressed as
Define domain D D
X Ru
bm
X
0, X 1 Vi
X = arg min XED
min LG. X) + Am
n
D XD /2
Now we are ready describe our algorithm whose pseudo-code is given in Algorithm That is, we first solve the aforementioned SDP to obtain solution X1 and then we add Gaussian noise to a sealed version of X,, denoted by X2. We then find the first eigenvectors of X₂ and obtain the corresponding spectral embedding (F(u) (u())ue Juev and then apply the approximation algorithm KMEANS on the embedding and output the final k partition (of the vertex set V).
Algorithm 1: Private Clustering
Input: Graph G (V, Output: A k- partitiion {Č, [
Let X1 = arg min X (L.. X) Am D x x/
Let X2 := n/D!! 1/2 W, where W N (o. 20 (A + 3) log(2/8) nxn
Let f2...... fir be the i eigenvectors of X2 corresponding to the first k smallest eigenvalues. Let F: VVG) R*, where F(u) d (u), fa(u), fu(
Apply (M))NN(F(u)) V) and let Ci...., , Cg be the output sets.
4.2 PROOF OF THEOREM
Privacy of the algorithm
5

---

Published as a conference paper at ICLR 2024
Lemma 4.1 (Stability). Let X(G,X) (LG,
Am D XD 1/2
and let g(G)
F''
1/2 DD G (argminxed ((, D The lz-sensitivity g, S 24 ( 3m
Proof. For two adjacent graphs G, G", we have || - ll, S 4, where || L Il,, is norm of the vectorizations of the matrix. And according to the range of X that X > 0, Xxi = 4
we have maxi, Xi I :. Thus, (Lc. X) ' , -
Without loss of generality, let G" have one more edge (u", u*) than G. In this case,
D / x X 1/2
D X 1/2
Σ
x Ido(u)da(w) - do (w)d
do (w))
1 n²
4 44+4 da(u)
n²
8m
+
4
12m
n²
n²
So f has L -sensiiivyy
12m
with respect to G.
Anm
Next, we prove that S(G, X) is
2m
D D' 2 -strongly convex with respect to X. The gradient
Am
VS(G, x) = LG +
Am X
2n
2
1/2
Let X, X' E K. then
f(G,X') = (LG,
n
D X'D
Am
= (La, x") + Am
n
D 1/2 X'D -D XD
D XD 1/2
D XD 1/2 D 12
dd
+ Am
(L,, X) + (LG, X' X) +
a
D 1/2 1/2
XD
Am
+ km
2n
D XD
1/2 1/2 1/2 X'D
G D
1/2
D XD + Am
D 1/2 X'D - -D 1/2
XD |
F
ff( LG. X' X)
2n
(Dd 1/2 XD 1/2 X' X'- X'-X> x}+
DG 1/2 X'D' 1/2 D XD 1/2
Am
Am
f( (Vf X), X' X
D
X'D
/
D 1/2 XD! 1/2 |
Am
That is S(G, X) is 2n 1/2 D
-strongly convex with respect to X.
By Lemma 3.1 [(G) s(G') 24(2-3)m
So the lg sensiiviyy Ag,2 S /24 (A + 3) m.
n
n²
Lemma 4.2 (Privacy). The Algorithm iis (c, 6)DP)
Proof. Consider X2 in the algorithm function of G. According Lemma 4.1 we get that the fz-sensitivity of X₂ is not greater than 224(A + 3)m. Combining with Lemma 2.3 get that the algorithm achieves (c, 5D-D..
Utility of the algorithm
Lemma 4.3 (Utility). Suppose that Sim -((ck X (
0
mi nkc Tog(22))
)}. For any
c-balanced (k. Oms &ma) (mm)) cllustrrabee graph, let (C. be k-partition obtained by the Algorithml (which invokes a k-means algorithm KMEANS with an upproximation ratio APT). Then, there exists a permutations on (1....,k) such that
volo (Mo(C.CCo())) 50 APT 4 δ
(9ow
+ log(2/0)
) vola(Co(1)
e2
with probability exp(-x((()

---

Published as a conference paper at ICLR 2024
Note that Theorem 1 follows by choosing constant-approoximaion k-means algorithm KMEANS
(so that APT = O(1) and setting À V 2lg(22/))
me? and letting m 2 n log(2/6)
To prove Lemma 4.3 we need the following lemma.
Lemma 4.4. Consider the SDP (7). if the input graph G = (V, F.) is a c-balanced (ki, Pnes Dow)- clusterable graph, the solution satisfies
(ld=-(dd(())d(())) S movoo(C,) Dou + W,EEC,
16 X
Σ
Vi
[kc
in
Oour +
16
Σ WEC,,vEC,,H#
(lā- - ((d 2 m²
2h
Din
Proof. As G E) is a e-balanced (ki, oia, dout) -clusterbbeeeee graph, there exists c-balanced partitioning {CiJie]k) of V and, for all i E [k], Pin (G, C+) 2 &in and PounGG C,) S Pour.
For s k; we have (G, C.) 1 S Cout- Summing yields Σ |E(C V vola(C.)
CJ) I dout E volg(C,) = dout volg(V) = 20 So the number of edges between clusters in G is not greater than Pomnm..
Now let us consider a feasible solution of the SDP (1. For every vertex u in the f-th cluster, assign unit vector v2 to ū. We can let v1, v2..... Ute be set of orthogonal bases, k S For this feasible solution, the value of the objective function is not greater than oou 2 2 jE( vola(C,)
Am
M + Am vola 2 m +
Thus, for any [k), we have [(u.)EGIC.)) - 512 I 20mm eigenvalue of the normalized Laplacian matrix Co(O.), we have
Let p be the second
E(un)eaIc. (l| +(
# vola()) min {aJuEV Enpeo, (I (d(w)dc(1)
Pin
So En,vec, - ( < vola(C;) 2dmm+ 8um
vola(Ct)
4 16m
10%
mnvol + for all i [k]]
By the definition of the SDP we know that En.vev (1/ū- - [1l2==]Bd((u))dc( 2 2bmn.
Thus, Σ
(l (llgdo())dll
2bm2 ΣiE(n) (mvolo(C.)
1dva 16
NEC,,E 40mnt 16
2bm
EiET vola(C;) = m² (2b
4dhm 16
Cin
Lemma 4.5. Consider the setting in Theorem 7 and Algorithm 1 with probability 1 1-exp(-(((n))
Dou + 3
6(A + 3)n log(2/0)
1x2 212 S 2m
2
+ 3/
m
2²
where is a matrix defined as: Zuv (do(w))a(v), if u, v are in same cluster; Zuo = 0 uf u. in different clusters.
Proof. According Lemma 4.4 for u, in same cluster C
Σ M,eEC,
n (nVdo())d(())x,1 J.o Zur) 2 Σ
(m (n[X1)as 1)2 1)ddc())d((())
u.DEC;
2
(n Xilxulu - - = Σ (l ((lo)dc(())dc(()
u.NEC;
M.ECC
16 40hout
< <mvolo(Ci)
X
02

---

Published as a conference paper at ICLR 2024
For u, in different clusters:
Σ
(nVdolu)do(t)x)) -Zwo) ) = Σ
da(()da(v)) ((edd())))((
VEC (4)
VEC,
$51
(2- -- 0112) (r(
MEC 141
MSC $51
1
20oat +
= hm
2
(1ā- Bl3d(())d(())) S sm²
2
MEC;,0EC, ipg
Combing these, we have:
nD 1/2
X2
1/2
S DD
1/2 " x
1/2
2
2
= Eun (nVda(u)do(()) [X1] Zuni
2
S
4m
Nutt Pi
uses W ~ ~N (0.24 (A+++) + m 1og(2/6) nxn
Algorithm
and we choose t = v in Lemma A.1
so with probability - exp( [(n))) || 2112 S
W
2
n
1122 x, D1/2 2
11 S 3//
V m. log(2/8) 6 + 4m
aut on
2m 2
dun 2 di
+ +31
G(A+3)n 1og(2/6)
m
Proof of Lemma 4.3 Let 7
2/
Poatt
3/ +
6(A+3)a log(2/6)
According to Lemma 4.5, with
m
probability 1 - (())), it holds that ||x2 - S 2ym
We denote the eigenvalues of the matrix X2 by μn 2 .... 2 pny with their corresponding orthonor- mal eigenvectors f1, fn. We denote the eigenvalues of the matrix Z by 11 2 2 En5 with their corresponding orthonormal eigenvectors [g1..... 9r., and let A Diag(/11, ,,,,, A = Di Vn). Then X₂ YAY 2
Let Y = [f,. fn
a set of orthog- onal bases in R", for every i E [n]. fi is the linear combination of eigenvector "1.... ,9n. We write ft as f: = ((4)
QAQT are the sigen-decompositions of X2, Z, respectively. As (g . ]
91 +... + ( 9n. where ((()) E R. By the definition of Z, we know that Z is composed of le rank-1 matrices of sizes [12l1/Cl,... ... ,(Cx]. respectively. Let these matrices be M1,M2, M2........ .... MM such that Mj E [C for each E [k]. For each j E [k]. note that the eigenvalues of Mj are vola(C)),0,
O. where the multiplicities of 0 is |Cyl - 1. So we have Pk+1 = = Vn = O, and 11, .. 2/ are equal to vola(C1), (.c(C)).....vllll. vvoa((a)) respectively. and
PA [M] (Ci) 2 2cm
By Lemma A.2 we have pa 2 2k X Z112 2 2m ( 7).
We apply Theorem A.3 with H = X2, Eo = YIs) Ei = Y -M|, Ao = AAj) A = A -K]
and H Z, Fo [())- F Q
[k] Ao = An). A1 = A. [k]. 11 = 1
1x41
|px|
Z
2m (f - ->) Therefore, by Theorem
A.3
we have
| pr XI 1k 112 = F. Eoll2 S
=I
FI (Z X2 X2
| Z 2 < 7k
"
"1
k
Thus we have Σj= (z)0)² = Q [kj fi
2 < Q
T
Y/N
||:
2
-
22²
for all i E [k].
1k
(o-7k)z
2
For all i E [k]]. let gi- = 81 91 +.... + Bl gn. then [| - g = ビ+ k+1
(3(0)
222
Te-
Note that our Algorithm
I invokes KMEANS algorithm on the input set the input set {F(u) (())))e J.e. 1/2 (fi (w), fa(u), -.., T= By Lemma 2.4 we know that the
where F(u) = do(u)
8

---

Published as a conference paper at ICLR 2024
output partition {(ibe(k)) satisfies:
volo(C,ACo()) < APT k22 2²
(c-ン vola (Cr(i))
(APT
Oou i + X boor2//1)) volo(Co(s)); for some permutation a on (1.....k) k.. L
Pin
5 EXPERIMENTS
To evaluate the empirical trade-off between privacy and utility of our algorithm, we perform ex- emplary experiments on synthetic datasets sampled from SBMs. As a baseline, we compare our algorithm to an approach based on randomized response described in Mohamed al. (2022). The algorithm based on randomized response generates a noisy output by flipping each bit of the ad- jacency matrix with some probability PRR (for undirected graphs, it flips single coin for opposing directed edges). It was shown that randomized response is e-DP for PRR 2 1/(1 =
Since randomized response is e-DP algorithm, we can gain by using (e, 6)-DP when the utility of randomized response becomes insufficient. Our hypothesis is that when the noise added the adjacency matrix by randomized response has roughly the same magnitude as the clustering signal, the output of Algorithm | still has significant utility. In particular, we consider the case where the difference between the empirical probability of intra- cluster edges and inter-cluster edges after randomized response is only a constant fraction of the original difference between these probabilities in the vanilla SBM graph.
interested in the utility improvement that
Implementation. We model the SDP (2) in CVXPY 1.3.2 and use SCS 3.2.3 as SDP solver. We use NumPy 1.23.5 for numerical computation and scikit-learn 1.3 for an implementation of k-means++.
For our algorithm, use b 1)/k and c. V n log(2/5] where e is trade-off constant that we fix for each SBM parameterization before sampling the input datasets. For randomized response, we replace the objective with arg min e La, X), i.e., we remove the regularizer term, and set PRR 1/(1+e")) +e*). The regularizer facilitates a trivial solution and is not needed because randomized response differentially private.
mec
Datasets and setup. We sample datasets from stochastic block model SBM(nn k. g) with k blocks, each of size nikk, intra-cluster edge probability p and inter-cluster edge probability q. We consider the sampled graphs instances of well-clustered graphs. For our experiments, we use
c = 1 and = 1/n². Since PAR = 1/(1 + e) z 0.27, we choose small values of p. q so that [p 9l = 0.2. For each parameterization, we sample 10 SBM graphs and run each algorithm 100 times to boost the statistical stability of the evaluation. See appendix for more details.
Parameters
RR+SDP
Algorithm |
k
p
9
AMI
NMI
AMI
NMI
100
2
0.20
0.00
5e-6
0.10
0.11
0.17
0.19
100
2
0.25
0.05
3.5e-6
0.10
0.11
0.14
0.15
100
2
0.30
0.10
2--6
0.09
0.10
0.26
0.27
150
3
0.20
0,00
3e-6
0.07
0.08
0.19
0.20
150
3
0.25
0.05
8e-7
0.06
0.06
0.57
0.58
150
3
0.30
0.10
7
0.06
0.07
0.35
0.55
Table Adjusted mutual information (AMI) and V-measure / normalized mutual information (NMI) RR+SDP and our algorithm. Reported numbers are modian values over 100 runs on the same graph, over 10 different graphs sampled from 9 BBM (n,, k. p)..
Evaluation. The evaluation of the comparison between RR+SDP and Algorithm I is shown in Table D We report the median over the repetitions, over the datasets, of the adjusted (AMI) and the normalized mutual information (NMI) between the ground truth clusters of the SBM model and the clustering reported by the algorithm as measure of the mutual dependence between these two (larger values are better). From the results, we see that the noisy adjacency matrix output by randomized response obfuscates most of the signal from the original adjacency matrix so that the solution of the SDP has low utility. On the other hand, we see that the regularizer term in the SDP and the noise added to the solution recovered significantly more information from the ground truth: Using Algorithm [ instead of randomized response can lead to (c, 6' diffferentially private solution with significantly improved quality, and consistently did so in our experiments.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
W.H. and P.P. are supported in part by NSFC grant 62272431 and "the Fundamental Research Funds for the Central Universities".
REFERENCES
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k- means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4): FOCS17-97, 2019.
Charles J Alpert and So-Zen Yao. Spectral partitioning: The more eigenvectors, the better. In Proceedings of the 32nd annual ACM/IEEE design automation conference, pp. 195-200, 1995.
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS00),, pp. 475- 486. IEEE, 2006.
Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. Advances in neural information processing systems, 32, 2019.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances neural information processing systems, 14, 2001.
Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In International Conference Machine Learning, pp. 1 1136--122 1146. PMLR, 2021.
Hongjie Chen, Vincent Cohen-Addad, Tommaso d' d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel. Private estimation algorithms for stochastic block models and mixture models. Advances Neural Information Processing Systems, 36, 2023.
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In 2018 IEEE 59th Anmual Symposium Foundations of Computer Science (FOCS), pp. 497-508. IEEE, 2018.
Vincent Coden-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub M Tarnawski. Near-optimal correlation clustering with privacy. 35:
33702-33715, 2022.
Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, and Richard Peng. Simple and scal- able constrained clustering: generalized spectral method. In Artificial Intelligence and Statistics, pp. 445-454. PMLR, 2016.
Yuyang Cui, Huaming Wu, Yongting Zhang, Yonggang Gao, and Xiang Wu. A spectral clustering algorithm based on differential privacy preservation. In International Conference Algorithms and Architectures for Parallel Processing, pp. 397-410. Springer, 2021.
Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceedings of the ferty-seventh annual ACM symposium on Theory of Computing, pp. 723-732, 2015.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii.
SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Tamal K Dey, Pan Peng. Alfred Rossi, and Anastasios Sidiropoulos. Spectral concentration and greedy k-clustering. Computational Geometry, 76:19-32, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284. Springer, 2006.
Shayan Oveis Gharan and Luca Trevisan. Approximating the expansion profile and almost opti- mal local graph clustering. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 187-196. IEBE, 2012.
10

---

Published as a conference paper at ICLR 2024
Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In Proceedings of the twenty- fifth anmual (CM-SIAM symposium on Discrete algorithms, pp. 1256-1266. SIAM, 2014.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approxi- mation ratios. Advances in Neural Information Processing Systems, 33:4040 4054, 2020.
Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, and Christian Sohler. Spec- tral clustering oracles in sublinear time. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1598-1617. SIAM, 2021.
Olivier Guédon and Roman Vershynin. Community detection in sparse networks via grothendieck's inequality. Probability Theory and Related Fields, 165(344):005-1049) 2016.
Jonathan Hehir, Aleksandra Slavkovic, and Xiaoyue Niu. Consistent spectral clustering of network block models under local differential privacy. Journal of Privacy and Confidentialityy 12(2), 2022.
Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM SIGMOD-SIGACT SSID-SIGAAT--IAAA Symposium on Principles of Database Systems, pp. 395 408, 2018.
Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 5135):9775155, 2004.
Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the eighteenth annual symposium on Computational geometry, pp. 10-18, 2002.
Pavel Kolev and Kurt Mehlhorn. A note on spectral clustering. In 24th Annual European Symposium Algorithms (ESA 16), volume 57, pp. 1-14, 2016.
James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher- order cheeger inequalities. Journal of the ACM (JACM), 61(6):1-30, 2014.
Daogao Liu. Better private algorithms for correlation clustering. Conference on Learning Theory, pp. 5391-5412. PMLR, 2022.
Rong Liu and Hao Zhang, Segmentation of 3d meshes through spectral clustering. In 12th Pacific Conference on Computer Gruphics and Applications, 2004. PG 2004. Proceedings. pp. 298-305. IEEE, 2004.
Jitendra Malik, Serge Belongie, Thomas Leung. and Jianbo Shi. Contour and texture analysis for image segmentation. International journal of computer vision, 43:7-27, 2001.
Tomohiko Mizutani. Improved analysis of spectral algorithm for clustering. Optimization Letters, 15:1303-1325, 2021.
Mohamed S Mohamed, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. Differentially private com- munity detection for stochastic block models. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Con- ference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp- 15898415894. PMLR, 17-23 Jul 2022.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and algorithm. Advances in neural information processing systems, 14, 2001.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pp. 75 84, 2007.
Pan Peng. Robust clustering oracle and local reconstructor of cluster structure of graphs. In Proceed- ings of the Fourteenth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 2953-2972. SIAM, 2020.
Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! In Conference learning theory, pp. 1423-1455. PMLR, 2015.

---

Published as a conference paper at ICLR 2024
Mohamed Seif, Andrea J Goldsmith, and H Vincent Poor Differentially private community de- tection over stochastic block models with graph sketching. In 2023 57th Annual Conference on Information Sciences and Systems (CISS), pp. 1-6. IEEE, 2023.
Moshe Shechner, Or Sheffet, and Uri Stemmer. Private k-means clustering with stability assump- tions. In International Conference on Artificial Intelligence and Statistics, pp. 2518-2528. PMLR, 2020.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888- -006,90,,-000 2000.
Daniel A Spielman and Shang-Hus Teng. Spectral partitioning works: Planar graphs and finite element meshes. In Proceedings of 37th conference on foundations of computer science, pp. 96-105. IEEE, 1996.
Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In László Babai (ed.), Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 81-90. ACM, 2004.
Kadim Taşdemir.
Vector quantization based upproximate spectral clustering of large datasets. Pat- tern Recognition, (133::33433044 2012.
Ulrike Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17:395 2007.
Lijun Wang and Ming Dong. Multi-level low-rank approximation-basee spectral clustering for im- age segmentation. Pattern Recognition Letters, 33(16):2206-25) 2015,222,22222 2012.
Yining Wang, Yu-Xiang Wang, and Aarti Singh. Differentially private subspace clustering. Ad- vances Neural Information Processing Systems, 28, 2015.
Yue Wang, Xintao Wu, and Leting Wu. Differential privacy preserving spectral graph analysis. In Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, April 14-17, 2013, Proceedings, Part II 17, pp. 329-340. Springer, 2013.
Scott White and Padhraic Smyth. A spectral clustering approach to finding communities in graphs. In Proceedings of the 2005 SIAM international conference data mining, pp. 274-285. SIAM, 2005.
Lihi Zelnik-Mann and Pietro Perona. Self-tuning spectral clustering. Advances in neural informa- fion processing systems, 17, 2004.
Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. A local algorithm for finding well- connected clusters. In International Conference on Machine Learning, pp. 396-404 PMLR, 2013.
A USEFUL TOOLS
The spectral norm of a Gaussian matrix has a high probability upper bound. The following lemma illustrates this fact.
Lemma A.1 (Concentration of spectral norm of Gaussian matrices), Let W (0, Then for any I, we have
t2
Pr(Vm Vn- - L Jmin (W)= < maax (W) V 2 2 2exp
(-
where )min(.) and m denote the minimum and the maximum singular values of a matrix, respectively.
Let W' be an n-by-n symmetric matrix with independent entries sampled from (0, d²). Then by the above fact, W' & 30 /n with probability least exp(-S((n))-
12

---

Published as a conference paper at ICLR 2024
When matrix undergoes slight perturbation under some conditions, its eigenvalues and eigenvec- tors do not experience significant changes. Lemma A.2 and Lemma A.3 illustrate this.
Lemma A.2 (Weyl's inequality). Let A and B be symmetric matrices. Let R A - B. Let
on 2 ... 2 On be the eigenvalues of A. Let B1 2 ... 2 In be the eigenvalues of B. Then for each E [n].
|as 8 I
||
Lemma A.3 (Davis-Kahan (in
Davis & Kahan 1970p). Let H = Eo Eg +
E A₁ and H Fo + F be symmetric real-valued matrices with Eo. Eι and Fo, F1 orthogonal. If the eigenvalues of Ao are contained in an interval (a, b), and the eigenvalues of A1 are excluded from the interval (a n, b + n)for some n > O, then for any unitarily invariant norm ||-1|
[ (H- H H)Eol
F Boll S
7
B DEFERRED PROOFS FROM SECTION
2
In this section, we give sketch of the proof of Lemma 2.4 restarted below.
Lemma B.1 (Peng et al. (015 Let G = (V, E)) be a graph and k E N. Let F V + IRt be the embedding defined by F(u) vdolu) (f) fu(u)) where {fi) a set of orthogonal
bases in R Let {S.) be k-partition of G, and {g. [ be the normalized indicator vectors de(u)
of the clusters (S:) where Āz(u) vSla(S.)
if E Si, and gz(u) 0 otherwise. Suppose there is a threshold 0 5k. such that for each [k). there exists a linear combination of the eigenvectors J1,-.. -h with coefficients 8/(1 Jr 3 91 + / Dbe and each i E [k]] Ilfe 9:ll 5.
Let KMEANS be any algorithm for the k-means problem in & with approximation ratio APT. Let {A.): be a k-partition obtained by invoking KMEANS on the input set {F(u)) ueV. Then, there exists a permutation a on {1....,kt ,,} such that (A)) = O(APT k2 82) ( holds for every i E [k].
Proof sketch. The following five properties given in Lemma B.2 are five key components proven in Peng et al. (2015). They start by demonstrating the first property based on the existing conditions. Then, they provide k centers for spectral embeddings and sequentially prove that all embedded points concentrate around their corresponding centers, the magnitudes of center vectors, and the distances. Finally, based on these properties, they establish the fifth one. With this fifth property, we can directly employ proof by contradiction to derive our conclusion.
LI
Lemma B.2. Consider the setting in Lemma 2.4 let Ç 2
10VE ((t) A
Vvol(S.) (D En Euec. d(u) [F(u) - call; for the
......... 3
T
for i E [k], and COST(C,,.... C+) mine ... oo ER
partition Ct, CI...., -Ck. The following statements hold:
1. For any # j. there exists E [k]] such that
2 A
10
2. All embedded points are concentrated around (+);
d(u))
- F()) S ko2
i= MES.
3. For every E [k] that
99 100vol(S.)
< |000 1
101
100vol(S.)
13

---

Published as a conference paper at ICLR 2024
4. For every + j. [k), it holds that
G² pp() p()) min (vol(S,), vol(S,)}
5. Suppose that, for every permutations 5 on f1....,ki k}. there exists such that vol (A,ASo()) 2 2evol (So()) for 100. then COST(A (........... A&) 2 10 10/
C DEFERRED PROOFS FROM SECTION
3
Lemma C.1 (See e.g. CCen et al. be a convex set. Then y K. is a minimizer of f over K. if and only if there exists a subgradient E Of(y") such that
2023 Let f R + R be a convex function. Let K. C R
wu w-シ 20)20 Vy E.K
Since the above lemma stated as a property of functions of vectors, in the following, we will treat a matrix its respective vectorization. Specifically, the vectorization of m X n matrix A is the mn x 1 column vector obtained by stacking the columns of the matrix A on top of one another. The inner product of matrices and B, well the & norm of matrix A, are defined as (A, () = Eis Aij Bi and ||,, Ein Aly, which are the same as the respective inner product and & norm of their vectorizations. Notice that |2, |A| p. which is the Frobenius norm of the matrix A.
Definition C.2 (Generalized strongly convex function). Let C mmx" be a convex set, f K. + R be a function, and D1, be diagonal matrices. The function f is called (x, D1, D2) -strongly convex if the following inequality holds for all X, X' K::
f(x') 2 ((x)+((()))) -IXX'XXVVXXX
XXVI(X)
K DIX'D - DIX
Lemma C.3 (Pythagorean theorem from strong convexity). Let S R be a convex set, f K. + R be function. Suppose I is (K, D₁, D2) -stronnyy convex for some diagonal matrices D and D2 Let X be a minimizer of f. Then for any E K. one has
2 DiXD2 D2 (1(X) ((X))).
k
Proof. By the definition of (K, D1. D2) -strongly convexity, for any subgradient E Of()),
f(x) f(x*(()))))))) x x g) DiXD22 DDX D211..1....
K
By Lemma C.I there exists subgradient g 0f(x*) such that (X x g) 2 Then the
result follows.
Proof of Lemma 3.1 The proof follows from Lemma CS and the proof of Lemma 4.1 in (Chen
et al. 2023).
D LOWER BOUND
In this section, we show that approximation algorithms for recovering the clusters of well-clustered, sparse graphs cannot satisfy pure e-DP for small error. Given a cluster membership vector u {-1,1}" 1 of graph G = (V, E) that assigns each vertex to of two clusters (labeled -1 and 1), and given ground truth vector ug E {-1, we define the misclassification rate err(u, ug) = (r)o(u) (n- min((u. (u, ua), (-u, uG)) (2n).. In other words, the miselassification rate is the minimum number of assignment changes that are required to turn ug into one of u and -u. is known that err a semimetric.
Lemma D.1 (Lemma 5.25, Chen et al. 2023 ). For any u, (-1, 1)", err is semimetric.
14

---

Published as a conference paper at ICLR 2024
Theorem 3. For Qins Pout E [0,1], 1), let G' be (2, Omn clussterle graph, and let 1/2. Then, any approximate algorithm with failure probability nj and misclassification rate Ç cannot satisfy for < (ell(//9e())/e/e d d-regular graphs.
Proof. We follow packing argument by Chen et al. (2023). Consider the set S = {p {-1,1)" 1'p p θ} equipped with the semimetric err. Let G be a balanced, d-regular, E S. Let B = B( 8(). Let aa #1, pp) be maximal 2{-packing of B. For every 0z P, there exists (2, Pin Jclusterrabe graph with cluster membership vector z; and (TTG(24) S 6ςdn: Since æy is balanced, the number of vertices j such that ( = -1 and (xG), = is equal to the number and ( -1 Consider perfect matching between these
(2, Oin: Oron clusterabble graph with cluster membership vector
of vertices j' such that (m two sets of vertices and, for each matched pair, swap their neighbors G to obtain Ha.-
By the maximality of P, have that B(zg, 6Ç) \ (,(((a,,,, 4()) 0. Otherwise, could extend P by p++,, where pp+1 is an element of the non-empty difference. This would contradict the maximality of P. Therefore, it follows that
B(, 4() 2 [B(a, 6() p
B 6C)
(n/2)
35n
66C
2
2/n
B [x 4C)
(n/2)²
18EC
2(n))
4
By group privacy and averaging argument, there exists i [p] so that
Pr(A(Ha))) S ((a,, () S exp(+(nd) Pr(A(G=m) B(xs, {)] S exple(nd) "
p
Now, assume that there is an (-approximate, c-DP algorithm with failure probability 17. By assump- tion, 1- Pr] (w,) S B(x,,()), Rearranging, obtain
2n
2Çn In 1866
In(1 n) In (1eq 22
II((n))
DeC
Se.
d
Sdn
Çdn
E DETAILS ON EXPERIMENTS
For reference and reproducibility, we provide some observations on the running times and scalability. The experiments were run on a single Google Cloud n2-standard- 128 instance. The CPU time (single core running time) for one run was about 2 minutes. The number of runs we performed is 100 per input graph, times 10 input graphs, times SBM parameterizations, times algorithms, i.e., 12,000 runs. The running times roughly scale follow as a function of the input size: for n 400 about 12 minutes, for n = 600 about 195 minutes, for n = 800 about 790 minutes.
15


Reviews:
[{"review_id": "KUfkMcx7hS", "reviewer": "Reviewer_ZCFz", "summary": "This submission studies differentially private (DP) algorithms for recovering clusters in well-clustered graphs, and it proposes a private algorithm that works for well-clustered graphs with k nearly-balanced clusters. The authors also show that any (pure) ϵ-DP algorithm would result in substantial error.", "questions": "1. The authors claim that this submission is inspired by a recent work of Chen et al, so what is the main difference between this submission and Chen et al's paper in the technique aspect?\n\n2. For two adjacent data sets (graph) D and D' differing in one edge, could it happen that D is well-clustered while D' is not?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The results seem interesting: The private algorithm in this submission works for\nk nearly balanced clusters while the previous reference only works for 2.\n\n2. The empirical results look promising, in comparison between RR+SDP and Algorithm 1.", "weaknesses": "1. The condition \"WELL-CLUSTERED GRAPHS\" may reveal sensitive information in edge privacy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QPNqmViqr3", "reviewer": "Reviewer_ApBn", "summary": "The paper gives a DP algorithm for well-clustered graphs. Here a \"well-clustered graph\" is similar to graphs generated from some stochastic block model, such that there exists an underlying partition of the graph, where edges between clusters are sparse (i.e, small outer-conductance) while each cluster internally is well-connected (large inner-conductance). The task is to recover this underlying partition in a differentially-private way.\nThe paper gives a spectral algorithm for the problem: first solve a SDP relaxation of the problem to extract the cluster structure, where (the assignment of) each vertex is embedded as a k-dimensional vector, then apply standard Gaussian DP scheme to (the Gram matrix of) the embedding vectors, which gives a perturbed version of the embedding. The final clustering is obtained by standard k-means clustering over the perturbed vectors.\nThe paper gives theoretical analysis on the algorithm performance, measured by the volume of the misclassified vertices, and prove it satisfy DP requirement.", "questions": "- I'm curious what's the relation of this well-clustered graph with stochastic block model? The SBM seems to attract much more research interests. Is the problem studied here a generalization of SBM, or a special case, or neither?\n- It would be very helpful if the authors can give some intuition & motivation of the SDP, in particular how the regularizer and the constraint (1) are designed.\n- I'm curious why the DP noise is applied to the Gram matrix X rather than directly to vectors associated with each vertex?\n- Proof of Lemma 4.4: I think the upper bound on $\\sum_{i=1}^k|E(C_i,V-C_i)|$ is $\\phi_\\text{out}\\cdot2m$, not $\\phi_\\text{out}\\cdot m/2$.\n- Proof of Lemma 4.4: Could you give a detailed explanation on how the second smallest eigenvalue $\\mu$ of $L_{G\\{C_i\\}}can be obtained by minimizing the quotient given in the paper.\n- In experiment the baseline is random response + SDP  *without regularizer*. Why do you remove the regularizer?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper gives the first DP algorithm for a hard (?) problem. The algorithm achieves good error bound and utility that are close to best-known non-private algorithms.\n- The algorithm given is very simple (maybe except for the SDP, whose formulation I believe lacks sufficient explanation), while the analysis seems quite non-trivial.", "weaknesses": "- I'm not familiar with spectral methods, so I'm not going to comment on technical merits. Although I can follow most proofs, I find it difficult to grasp the intuitions. One example is the SDP with the constraint (1). It would be much more reader-friendly if the authors can give intuitive summary of the ideas instead of directly jumping to proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "akrTkDjEsI", "reviewer": "Reviewer_vyy9", "summary": "This paper studies differentially private algorithms for cluster recovery on well-clusterable graphs. A well clusterable graph is an unweighted graph that has a bounded ratio between outer conductance and inner conductance. The notion of privacy is (eps, delta)-differntial privacy, and it is measured on neighboring graphs that have one edge difference. The goal is to minimize the (relative) number of points that are mis-clustered in every cluster, provided that the input graph is well clusterable into k clusters (and assuming k is known).\n\nThe main result achieves a misclassification ratio only slightly worse than the state-of-the-art non-private version with respect to the main parameters. The price of privacy is mostly on the requirement of the desntiy of graphs, i.e., the number of edges must be at least some poly(\\phi_in / \\phi_out) / eps^2 * log(1 / \\delta) factor larger than the number of vertices. Lower bounds were also obtained to justify this price of privacy. Finally, some experiments were provided to justify the usefulness of the new algorithm.", "questions": "- The presentation is technically heavy. It would be helpful to talk about more intuitions and less calculations in the main text.\n\n- In Theorem 1, n and m are not quantified. Also, the quantification of \\sigma is not very clear — “for every” or “exists”?\n\n- In the experiments, it would be nice to define or at least explain what AMI and NMI are, and what do they indicate. I’m not even sure if larger value is better.\n\n- I found only arXiv version is cited for several papers — are they published in a conference? Please check and update.\n\n- You mentioned that your experiments are to somehow verify that “when the noise added to the adjacency matrix by randomized response is balancing with its signal, the output of Algorithm 1 still has significant utility”, but I don’t see this clearly discussed. For instance, from what data did you see that the noise added by randomized response is balancing with its signal? And how exactly does your Algorithm 1 compare w.r.t. utility? \n\n- I may have missed something, but did you say the value of eps and delta that you use in the experiments?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The bound looks strong since it is very close to the non-private version — The privacy guarantee does not directly add to the misclassification ratio. The factor of poly(phi_in / phi_out) in the “price of privacy” seems to be natural and is probably necessary (even though the paper did not justify this).\n\n- The techniques are not particularly novel, but combining existing techniques and obtaining interesting results is also a solid contribution.\n\n- The paper is well-written and easy to read.", "weaknesses": "- One thing I’m not sure: does the balance parameter c also appear in the bound of Peng et al. 2015? This is not clearly discussed in your paper, and I think that this is very important.\n\n- Whether (eps, delta)-DP is necessary is not justified; the upper bound is (eps, delta)-DP and the lower bound is about eps-DP.\n\n- The approach requires to solve SDP which is heavy for larger datasets.\n\n- The experiment is not comprehensive and I find it not very convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CkbMTLxZR7", "reviewer": "Reviewer_viwC", "summary": "The paper studies differentially private clustering algorithms for balanced and well-clustered graphs. The notion of ‘’well-clustered’’ is defined by a high ratio between the inner and the outer conductances, and the notion of ‘’balanced’’ is defined by the graph volume. The paper considers the problem with any fixed $k$ number of clusters, which is a natural extension of a recent result by CCDEIST [Neurips’23] that studied the DP clustering algorithms for balanced and well-clustered instances with 2 clusters. Instead of using a cost function, the goal in this setting is to ‘’almost entirely’’ recover the clustering labels while still preserving the differential privacy. This is a reasonably strong goal given the strong assumption on the underlying instances. \n\nThe main result of the paper is an $(\\epsilon, \\delta)$-DP algorithm that recovers the clusters correctly up to an $O(\\log(1/\\delta)/\\epsilon^2)$ multiplicative factor on the *volume* of the (ground truth) cluster (assuming constant balance factor). The paper also provides a lower bound showing that we cannot hope for zero-error algorithms under this setting (unlike the exact recovery of CCDEIST [Neurips’23]). Finally, the paper conducts several experiments on synthetic datasets, and the results show that the proposed algorithm is competitive in the *utility* metric (but did not test for privacy).  \n\nThe main technical ingredient of the paper is a white-box adaptation of the results of CCDEIST [Neurips’23]. In particular, the algorithm uses a variate of the $\\ell_1$ sensitivity bound by CCDEIST [Neurips’23] for strongly convex functions and shows that their SDP objective function satisfies the desired convexity property. As such, they can get a levy on the level of Gaussian noise put on the output of the SDP solution. They further use known results in spectral clustering to show that the added noise level does not induce too much error on the utility.", "questions": "Defining balance with volume seems to be a strong notion since it rules out the case when the clusters have comparable sizes but different densities. In contrast, I believe setting of CCDEIST [Neurips’23] only requires the *vertices* in two clusters to be balanced. Do you have any comments on this front?\n\nCan you report the runtime of your experiments and the hardware for your experiments? I want to get a sense of how far this algorithm is from being implementable in the real world and in the industry. (Please note that a bad performance will not affect my score, so please don’t do it strategically :)))\n\nYour lower bound is for pure DP, can you get any result for pure $\\epsilon$-DP upper bound with your technique? In particular, since you have a bound for the $\\ell_{1}$ sensitivity of $f$, can you use Laplace mechanism to obtain a pure DP result?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "My general evaluation of the paper is positive: it studies an interesting problem, which in turn is a natural follow-up of a well-established result. The paper is well-written, and the technical steps are rigorous and easy to follow. The organization of the paper also looks quite nice.\n\nI checked the privacy proof, and things look correct to me, barring the details of the proof of Lemma 3.1. Unfortunately, due to the limits on the review timeline, I did not get a chance to verify the algebra for the utility proof – a spot-check indicates that nothing is wrong. \n\nFinally, I think the results have nice applications due to the widespread popularity of the SBM model and the fact that a lot of networks satisfy the ``clustered’’ property. The experiment results show that the running time of the algorithm is not too bad, at least on small-scale of data.", "weaknesses": "Presentation problems in the main theorem. a). DP is not formally defined before the statement of theorem 1. Please at least add a pointer to your definition in section 2. b). The notation for $G_1 \\Delta G_2$ is never defined. (And it’s never defined anywhere in the paper! :)) ) and c). The trade-off between the utility and the $(\\epsilon,\\delta)$-DP is not clear in the statement (although there is a lower bound on $m$), and it was unclear until Lemma 4.3. I would prefer to state the bound for general instances and factor the trade-off in the multiplicative error.\n\nThe notion of $(\\kappa, D_{1}, D_{2})$-strongly convex is not defined in the preliminary (and only becomes clear to me after looking into the proof).\n\nWhile I understand this is a mainly-theory paper, I would still suggest the authors spend more passages to properly motivate the study of the clustering of well-clustered graphs. I think CCDEIST [Neurips’23] has a nice example on this front by discussing the motivations from stochastic block models and downstream applications. Some discussion on this front is especially important for the broader appeal of the ICLR audiences.\n\nGiven the fact that the algorithm needs to run SDP, it’s unlikely that the algorithm can be scaled to modern social networks, which are the best candidates for well-clustered properties. Purely combinatorial algorithms would be much more helpful on this front.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)