Local Differential Privacy-Preserving Spectral Clustering for General Graphs
Authors: Sayan Mukherjee
Vorapong Suppakitpaisarn
Venue: Accepted by TMLR ()

Abstract: Spectral clustering is a widely used algorithm to find clusters in networks. Several researchers have studied the stability of spectral clustering under local differential privacy with the additional assumption that the underlying networks are generated from the stochastic block model (SBM). However, we argue that this assumption is too restrictive since social networks do not originate from the SBM. Thus, we delve into an analysis for general graphs in this work. Our primary focus is the edge flipping method -- a common technique for protecting local differential privacy. We show that, when the edges of an $n$-vertex graph satisfying some reasonable well-clustering assumptions are flipped with a probability of $O(\log n/n)$, the clustering outcomes are largely consistent. Empirical tests further corroborate these theoretical findings. Conversely, although clustering outcomes have been stable for non-sparse and well-clustered graphs produced from the SBM, we show that in general, spectral clustering may yield highly erratic results on certain graphs when the flipping probability is $\omega(\log n/n)$. This indicates that the best privacy budget obtainable for general graphs is $\Theta(\log n)$.

Published in Transactions on Machine Learning Research (05/2025)
Local Differential Privacy-Preserving Spectral Clustering for General Graphs
Sayan Mukherjee" The University of Tokyo
aayondghhys.suutoooo......
Vorapong Suppakitpaisarn" The University of Tokyo
worapong@is....utokko..oo
Reviewed on OpenReview: https: // openreview. net/ met/ forum? id- 205060A
Abstract
Spectral clustering is a widely used algorithm to find clusters networks. Several researchers have studied the stability of spectral clustering under local differential privacy with the additional assumption that the underlying networks are generated from the stochastic block model (SBM). However, argue that this assumption is too restrictive since social networks do not originate from the SBM. Thus, we delve into analysis for general graphs in this work. Our primary focus is the edge flipiing method a common technique for protecting local differential privacy. We show that, when the edges of an n-vertex graph satisfying some reasonable well-clustering assumptions are flipped with a probability of O(log n/n), the clustering outcomes are largely consistent. Empirical tests further corroborate these theoretical findings. Conversely, although clustering outcomes have been stable for non- sparse and well-clustered graphs produced from the SBM, show that in general, spectral clustering may yield highly erratic results on certain well-clustered graphs when the flipping probability is w(log n/n). This indicates that the best privacy budget obtainable for general graphs is @llggn).
1 Introduction
As the demand for trustworthy artificial intelligence grows, the need to protect user privacy becomes more crucial. Several mothods have been proposed to address this concern. Among these, differential privacy the most common. Introduced by Dwork (2008), differential privacy measures the amount of privacy a system leaks by using metric called the privacy budget. This method involves corrupting users' information, then processing the corrupted data to obtain statistical conclusions while still maintaining privacy. Developing algorithms that accurately provide statistical conclusions from the corrupted information is topic of interest among many researchers such as /hu et al. (2017). One of the advantages of the differential privacy notion is that the information revealed from the users' sensitive information is quantified by a term called privacy budget. We say that an algorithm protects users' information when its privacy budget is small.
In this work, we are interested in a variant of differential privacy called local differential privacy introduced by Kasiviswanathan al. (2011). Unlike traditional differential privacy, local differential privacy does not allow the collection of all users' information before is corrupted. Instead, it requires users to corrupt their data at their local devices before sending them to central servers. This ensures that users' information is not leaked during transmission. As discussed by |Erlingsson et al. (2014) and Apple's Differential Privacy Team (2017), local differential privacy is used by companies for their services.
We focus on algorithms for social networks. In a social network, each user represented by a node, and their relationships with other users are represented by edges. The relationship or edge information is usually
* "Equal contribution.

---

Published in Transactions on Machine Learning Research (05/2025)
sensitive because one might not want others to know that they have relationship with some particular individuals. One of the most common techniques for protecting user relationship information under the local differential privacy notion is randomized response or edge flipping, which is technique considered in Warner [1965), Mangat (1994), and Wang et al. (2016). In this technique, before sending their adjacency vector (which represents their friend list) to the central server, each bit. in the adjacency vector is flipped with a specified probability p. We obtain local differential privacy with the budget of (llo 1/p) by the flipping.
Because of the simplicity of randomized response, it has been extensively used part of many differen- tially private graph algorithms Imola et al. ) Hillebrand et al. (2025) These include graph clustering algorithms such as Ji et al. (2020); [Mohamed et al. (2022); Fu et al. (2023) One of the most widely used and scalable graph clustering a algorithms spectral clustering has also received a lot of attention in this context. We are particularly interested in the combination of randomized response and spectral clustering, because it has been shown in Peng & Yoshida (2020) that spectral clustering is robust against random edge removal. It could also be robust against edge flipping. Many analyses such as Hehir et al. (2022) have been recently done for this combination. However, all of these analyses assume that the input social networks are generated from the stochastic block model (SBM).
1.1 Our Contribution
We argue that assuming that the input graph is generated from the SBM is too restrictive. Thus, in this study, we consider the robustness of spectral clustering for general graphs. In what follows, let G be an n-vertex input graph. Our main contribution of Section 3 can be summarized by the following theorem:
Theorem 1.1 (Informal version of Theorem 3.1. Let G' be obtained from G via the edge flipping mechanism with probability p = Oloog/nn). Then, under some reasonable assumptions, the number of vertices misclas- sified by the spectral clustering algorithm by running il G' inslead of G is O(r(G) n) with probabilily 1 o(1), where r(G) is the spectral robustness defined in 2.1
We shall see later that r/( is a constant much smaller than 1 for well-clustered graphs. Theorem 1.1 implies that:
Spectral clustering is robust against edge flipping or the randomized response method with probability p = OOlog n/n), or privacy budget e ()logn).
(1.1)
The privacy budget 22( can be considered too large in many applications, which might limit the contri- bution of this work. However, this large privacy budget has also been considered in some previous works differentially private graph clustering such as Mohamed et al. (2022). As the authors prove that constant privacy budget can be achieved for non-sparse, well-clustered graphs generated by SBM, one might antici- pate a similar outeome for general non-sparse, well-clustered graphs. Howeover, in Section we show the following negative result that the edge flipping mechanism cannot achieve better privacy:
There is a family of non-sparse and well-clustered graphs for which edge flipping with probability = w(log n/n) massively changes the sparsest cut.
(1.2)
Our findings are depicted in Figure 1.1 This figure focuses on a segment of the Facebook network in the Stanford network analysis project (SNAP) described in Leskovee & Mcauley (2012). as sourced from the "0.edges" file, called as Facebook0 in this paper. We have modified each relationship this network with a 0.005 probability of flipping, and the figure displays the network both before and after these changes. Observations from the figure reveal significant additions and removals of edges, suggesting that we can protect user information via edge- tlgppfni For instance, the connectivity (or degree) of node 86 is notably higher after the flipping. However, it is worth noting that the clustering characteristics remain largely unchanged before and after the network modification.
One of the results of Mohamed et al. (022)) proves generated from the SBM. However, we found that no graphs in practice satisfy propertics of SBMs. For example, if a graph is generated from the SBM, its degree distribution should follow a mixture of two binomials. However, we found that none of the publicly available datasets at SNAP (Teskovee & Krevl,
assuming that the input social networks are
2

---

Published in Transactions on Machine Learning Research (05/2025)
(a)
(b)
Figure 1.1: part of the Facebook network detailed in Leskovee & Mcauley (2012) before and after flipping edges with probability of 0.005. The neighborhood (colored light pink) of node 86 changes lot after the
flipping.
2014) follow this degree distribution. This motivates us to make much weaker assumptions in this work. The only two assumptions we require are: 1) the social network has sufficient cluster structure and 2) its maximum degree sufficiently large. The SBM's considered by Mohamed et al. (2022) also satisly these assumptions (see Remark 2.13).
We use some ideas from the work of Peng & Yoshida (2020), who have studied the scnsitivity of spectral clustering algorithms. However, their work focuses on scenarios where each edge is removed with a specific probability. In contrast, local differential privacy not only removes edges but also adds edges to social networks. Furthermore, the number of edges added often much greater than those removed, especially for sparse networks. Thus, while our proof structure generally follows the outline of their proof, the core components (such Lemma 3.2 Lemma 3.3 and Theorem 4.1 are original and require careful probabilistic arguments.
Remark 1.2. For maney readers, it may seem counter-intuitive that the privacy budget increases with the number of users, given that differential privacy tends to be more effective with larger databases. This con be explained by considering the nature of the data being protected. In relational databases or general graph differential privacy, there are n pieces of information to protect. However, for local edge differential privacy, the protection extends to O(n²) bits of edge information.
Remark 1.3. Spectral clustering analysis under local differential privacy is relatively recent area of erplo- ration. However, there is subslantial body of work on graph clustering with differential privacy, evidenced by studies like Mohamed et al. (2022) and Wang et ol. (2013). Notably, a recent study by Chen et al. (2023) provides both upper and lower limits for privacy budgets pertaining to non-sparse graphs generated from the SBM.
2 Preliminaries
2.1 Notation
Edge-subsets. We assume that G (V, F(G)) is graph of n vertices. Also, assume that the set of nodes
V is n2.. For any subset F' C (b), we denote by GAF the graph (G))FF.. By F ~p (t), we mean that F is random subset of (k) such that each subset is taken with probability p.
3

---

Published in Transactions on Machine Learning Research (05/2025)
Cuts. For subset S S V of vertices, we denote by S the complement set V \ S. Further, given two subsets A, B C V with A n B = 2, let eg (A, B) denote the number of edges of G with one end- point in A and one in B. For any two sets of nodes S,S' C V, (S, is given by daize (S, = min (I5A5*) + (A5 |SAS| + [SS')). As |SAT| = [SAT], we can equivalently write dsize (S,5") = 2/SAS1 A cut (S, S) is similar to (S", 8*) if (S, is small.
Spectral Graph Theory. Any n x real symmetric matrix A has real cigenvalues. We denote the i-th smallest eigenvalue of A as AA(,), i.e. (A) S (A S ... S (A). For any graph G, the Laplacian matrix LG is given by DG-AG: where De is the diagonal degree matrix with (Dc) = dega(1) and Ag is the adjacency matrix of G.
In this work, we relate the performance of spectral clustering under the edge-fliping mechanism via the following quantity:
Definition 2.1 (Spectral robustness). We define the spectral robustness of the graph G as nGG) =
(LG)) where AGG) denotes the marimum degree of any verter of G. Aa(Taa)
2.2 Edge Differential Privacy under Randomized Response
The notion of s-edge differential privacy is defined as follows:
Definition 2.2 (s-edge differential privacy; Nissim et al. (2007)). Let G be a social nelwork and lei Y be a
randomized mechanism that outputs (G) from the social network G. For any E 0, any possible output of the mechanism Y denoted by y, and any two social networks G(1) = (V, (V,E((G) (G)) and ( (V, ((2) Pr|YicU) that differ by one edge, we say that Y is s-edge differentially private if e P: Se. We refer to the value of e as the privacy budget of Y.
Intuitively, a lower value of results in better privacy protection. In this research, for 0 S p S 0.3, we investigate a randomized mechanism Yp that seeks to generate a result highly similar to spectral clustering outcomes, using randomized response. The mechanism Y, is defined as Y, = SC o Fp. where Jp represents a randomized function that modifies the relationship between each node pair with a probability of p, and SC is function for computing spectral clustering. In other words, the randomized mechanism performs spectral clustering on GAF, in which (u, u) E F with probability of p for every u, V. The following theorem is shown in Wang et al. (2016).
Theorem 2.3 Wang et al. (2016)). The publication Yp is s-edge differentially privale whenever
Le S e p
Theorem 2.3 implics that Y, is e-edge diffcrential private for E 2 In(1 - p) - Inp. When is small, we have In(1 p) 2 0, and therefore the privacy budget of the publication Yp is 22log 1/p).
2.3 Spectral Clustering
For graph G, the general goal of clustering techniques is to find good cut (S such that ea(S, S) is small, and most of the edges of G are either concentrated in S or S. In order to avoid trivial cuts (for example where S comprises of a single vertex), it is customary to instead define the cul-ratio ag(S) so(S.8) and find cuts that minimize (S( (see Wei & Cheng (1989); ; Hagen & Kahng (1992)). a(G) = min ac(S)
[l||i]
eCSCV
is defined as the cut-ratio of G. Unless otheeisse specified, we shall denote by S the cut that achieves as(S*) (G).
Another widely used way of defining the cut-ratio is (S(())
(g(S.3)
This definition is used in Peng &
min( S),(S))
Yoshida 2020), Guattery & Miller 1995), and Kwok et al. 2013 We observe that these two definitions are related:
Lemma 2.4. 1 nac(S)) S dg(()) < nox(S))
4

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. For the left side of the inequality, note that 2 aaa((S) = | - (S). On the other hand, ((( (G) max (1), (8]) S n aG (5).
sc(S.S)
(c(S.S)
(c
2
[s||i| =
(c(S.3) eo(8.5)
max
j
Lemma 2.4 will be useful in converting results formulated using o'g to those using our cut-ratio 0g.-
Now we describe the spectral clustering algorithm. Spectral clustering uses the eigenvalues and eigenvectors of La compute a cut of S. Let us denote by SC₂ the following algorithm that clusters given graph G into two clusters:
Compute the second smallest eigenvector T = (V.....,Vi, vn of La using the Lanczos algorithm or an approximation method, such as the one proposed in Adii Saranurak 2024). Let U1.... Up distinet nodes of V such that Vva S ... Ve..
Return the cut (S,5), where S {oI,..., ) and in arg min ag (e 15ign
The cut-ratio of G can be quantified very preciscly via the famous Choeger's ' incquality.
Lemma 2.5 (Cheeger's Inequality; Cheeger 1971
Alon 1986)). >2(Lo) & na(G) S (BA(G)A((L))
We shall also use the following improvement of Lemma 2.5
Lemma 2.6 (Improved Cheeger Inequality; Kwok al.
2013) ). Let SC2(G) denote the cut given by the
Ag (ll 1G))
spectral clustering algorithum Then, ag (SC)((G)) 0
mAs(T-e)172
Lemma 2.5 and 2.6 give us a way of quantifying the quality of the cut output by SC2 in terms of the cut-ratio of G. Indeed, as La( < a(G),
A(G))/2
ag (c(2 0o
(G)
(2.1)
\a(Lo)
Let S* be the cut of with the smallest cut-ratio. While equation 2.1 can be interpreted as a measure of how close (G) is with S*, we shall need stability results from Peng & Yoshida (2020) to precisely bound daize (S)) Lemma 2.7 (Lemmaa 3.5 of Peng al. (2015) ). Let G = EV be any graph with optimal min-cut S*. Then, for any 2 1, if S S V satisfies ds((S) S p aG(S"), then (s,ze( = ( As(La))/2
(a((a))(G))11
.) .n.
The following lemma directly obtained from Lemma 2.7
Lemma 2.8 (Stability of min-cut). Let G = (V, E) be any graph with optimal min-cut St. Then, for any (>((G))(G))12
p21 1, S V satisfies (S( S p. ag("), then (S s 00( \a(Lo)
p) .n.
Proof. Observe that by Lemma 2.4 ac(S)= < (S") implies (S((S) < 2p a'c(S)). This lemma then follows from a direct application of Lemma 3.5 of Peng & Yoshida (0020)
2.4 Concentration Inequalities
We also require some concentration inequalities for random variables, which we present here. Lemma 2.9 (Hoeffding's inequality; [Hoefdding (1963)). Let XI...., Xn be independent random variables
such that a; < X; < b, almost surely. If S X1 + X then we have PrIS EES) t| < exp 2t /E a,
Lemma 2.10 (Chernoff bound; Mitzenmacher & Upfal 2017 For binomial random variable X with
mean and > O, we have Pr 2 4 + & exp 2utt
Lemma 2.11 (Weyl's Inequality; Weyl (1922)) For any real symmetric matrices M and H [M(M H) X(MM & | where || l| denotes the spectral norm of H.
5

---

Published in Transactions on Machine Learning Research (05/2025)
2.5 Assumptions
In order to demonstrate the robustness of spectral clustering, we require assumptions the social network
G and the probability of edge flipping. Recall that F <p (x) is the set of vertex pairs to be flipped.
Assumption 2.12. We assume the following:
1. p logn/1000 1/0n
2. (a) (G) N 10 log (La)),), (b) >2(L)) 2 1/10, (c) m()) Aa(La)A(G) Aa(La] is small,
(d) >z(GG) 2 10 n,
3. Let the minimum cuts of G and GDF be 55) and (S7,5p) respectivcly. Then each of (1 15+11s1 [Sp] have size al leust n/10.
Plausibility of Assumplion 2.12
The first assumption can be justified by our discussion in Section 2.2 where we note that to achieve a privacy budget of (llog n),, p should be ((1/n). We further note that, if G is a sparse social network with (()) edges and p > n/n, then as B(IF)) = On log n), G&F will have too much noise, and would become close to the Erdös-Rényi random graph F ~ ()..p). Spectral algorithms cannot perform well for these graphs. For example, it is shown in Chung& & Radcliffe (2011) that the eigenvalues of the normalized Laplacian LF are close to those of the expected values. A quick calculation shows that the second and third eigenvalues of I((F)) are both equal (and close to 1), implying the inefficiency of spectral clustering algorithms on G(n, p) for p asymptotically larger than logn/n.
On the other hand, one may think that values of p larger than logn/n, for example p 211 is achievable by the edge flipping mechanism if the input graph G' is not sparse. However, there are two issues with this: firstly, social networks are not dense in practice. We found that all publicly available social networks in SNAP (Leskovec & Krevl, 2014) are sparse. Secondly, we demonstrate in Section a well-clustered non-sparse graph, whose sparsest cut changes drastically when introducing noise p = wlog n/n).
The second assumption derives from usual properties of social networks. Recall that we have (LG) (2(T.) s... (TG)) < <2)G). This assumption asserts that there are big gaps between (TG)) (T(
and AGG).
First, we note that most social networks that we encounter in practice, have super-nodes (nodes of degree ((n)) (Baraáási & Albert 1999), justifying our assumption (a).
Assumption (b) ensures that G is well-connected: note that disconnected graphs have Xg(La) = and graphs that have small edge-separators have a small >² We also make a nole here that we can relax this assumption to any constant threshold Ag(L.) 2 @()), by changing the value of to used in Section 3.3 Conversely, the countercxample provided in Scction 4 has connectivity of O(1nn), implying that for the stability of SC2, the algebraic connectivity of G' cannot be too small.
Finally, (c) ensures that there is a gap between Aa(Lc) and X2(La), which ensures that the graph has good bi-cluster structure, which lets SC₂ find good clusters in G. The large gap between X2(Ga) and Ag (Le) is usually assumed in several works on spectral clustering such as Peng et al. (2015): Peng & Yoshida (0020) since the large gap implies that the graph is vell-clusterdd.
Observe that using inequalities (a), (b) and (c), we can deduce that Ag(Lo) implics our assumption of (d).
Aa(Lc)A(() As(Lo)n(G)
n which GGG
Our final assumption stems from the fact that usually social networks admit linearly sized clusters, and also we are usually interested in detecting clusters of larger size via the definition of the cut ratio (GG), for example. Moreover, our analysis in Equation 3.6 suggests that |Sp] and SSp] are close to the output [Sp| and F of SC2, which designed to output balanced cuts. This justifies our assumption of 1S 2 0.1n.
Remark 2.13. When dealing with SBM's with probabilities p = a log n/n inside each cluster and q = alogn/n between, the work of Deng et al. (2021) proves that >2(LG) I Obblgg n) and >g > blog n. Therefore, these SBM's satisfy Assumption 2.12 and the result for Randomized Response in Mohamed al. 2022) follows from our work.
6

---

Published in Transactions on Machine Learning Research (05/2025)
3 Main Theorem
We restate and prove a formal version of Theorem 1.1 in this section.
Theorem 3.1. Let G = E)) be a graph and satisfy Assumption 2.12 Let F ~p (2). Then, with
probability at least - 5n -855
ssse (C, =((())))))(G)))))(((()))))) n).
Proof Structure. Suppose S and Sp are the optimum min-cuts of G and GAF. Denote by S and Se the outputs of SC2 on G and GAF, respectively.
The key idea is to bound daize (S, using triangle incquality:
dgize (F,SF) dsize + (Si (Sp daize (Sp, Sp)-
(3.1)
We bound each the terms in their own subsection below. Observe that by Equations 3.2) we obtain
3.6
and 3.8
A2(Lo)A(C)) Aa(La)²
dzizo 50
n n O(nG))
with probability at least 1 1 4n - n -8/5 2 section, bound each term appearing in the right side of Equation 3..1
5n 8/5 completing the proof. In the remainder of this
3.1
The term dsize (S,
An upper bound this term is direct corollary of Cheeger's incquality and stability: observe that Lemma 2.8 and 2.1 give
\G(Lc) A/2
\a(Le)113 n = (AolLo)A(G)
daize (5,5") SO
(
(3.2)
\a(Lo)312
Aa(Lo)²
3.2
The term dgize ,
First, describe lemma to compare the eigenvalues and maximum degrees of GAF and G.
Lemma 3.2. Let G have vertices, and F G(n,y). Under Assumplion 2.12 with probability at least - 3n 21/11 all of the following hold:
(a) >2(GGAF) I X2(La), (b) >s(LGar) Ao(La)/10, (c) A(GDF) s A(GAF)&22(CG 2D(G).
Proof. Part (a). By monotonicity of A2, \2(LGAF) & A2(Lour). As de( S (2 + A2(Lma),, and < logn/10n F (and hence G)) is almost surely disconnected Erdös et al. (9600), implying X2 (e(LF.)) Hence, we have \2(LGAF) & Ag(Lou)) S d2(LG).
Part (b). For this part, we shall use Weyl's Incquality follows: suppose Fi F G and F2 Gn F be subgraphs of F on the vertex set V(G). By additivity of the Laplacian, LOAF - La Lp, LF. Now ||A]|2 = maxxeR" TTAr for any symmetric n X matrix A, which implies
||LAAF Lella max I LF xT Lpgal ZER"
max x LEx Xn (n (2F)). FeR"
By the union bound, note that for any v E V(G),
9
Pr(A(F) log n| & n Pr(degr(u) log n]
Pr (degg((v)) p(n 1) 4 4log]].
(3.3)
Using the Chernoff bound, the probability in (.3 is al most.
n exp (- 16(logn)
16(1og n)
32
< n exp
n exp
(- logn
-21/11
(3.4)
2(n - 1)p + llg
log n

---

Published in Transactions on Machine Learning Research (05/2025)
Thus |LGAF Lalla I 9 llg holds with probability at least 1 - n 21/1111 Assumption 2.12 2),
By Weyl's inequality and
9
As(Lo) >a(LGGF) S 9lgg I \z(Lo),
10
finishing the proof of (b).
Purt (c). Observe that for every vertex v E V(G), we have
degGar(1) (e) S deg 5 A(F).
Hence,
Pr (dgga=F(1) > (ega(e) AG)) < Pr(A(F) A()) Pr(A(F) > 10logn]
By a similar calculation to 3.3 and 3.44, we conclude that degcap(e) > dega(e) + A(G) holds with probability at most n- Again, by the union bound, with probability at least n - we have
degGAr(v) (v) + A(G) for all V(G).
(3.5)
Taking the maximum of 3.5 over all v, we see that (c) holds with probability at least 1 - n which is greater than 1- 221111
As the assertions of (a); (b), (c) each hold with probability least --" --11111 all of them simultaneously hold with probability at least 1 - 3n 21/11, completing proof of Lemma 3.2
Now, observe that by the same argument as at least 1 - 3n -2111,
3.2 in addition with Lemma 3.2 get that with probability
(
=0 (A
deine Sp) SO
-n=
(3.6)
As(LGar)
3.3
The term (S* S
For the remainder of this section, let to given by
To = 200 A(G)AA()))(( 200 /10lg...
In order to bound (S" St), we require the following rather technical lemma. Lemma 3.3. Let S* denote the minimum cut of G and Sp denote the minimum cut of G&F. Suppose n/2 2 11 2 en for some 1/2><>> 0. Further, suppose ag(Sp) 2 "00a((") Then,
4 (12 1)
Pr (104G4F(5t) - -GaFF(S)) < <) < exp
ag ag (S*))
(3.7)
25
As the proof is involved, we defer it to the end of this section.
First, we demonstrate the bound on (sime( , SF) using Lemma 3.3
We consider two cases:
Case (G(S)) s (SaG(S*): In this case, Lemma directly gives us (S ST)) S (a(Laa)(())) n.
o 0 (20
0 Aa(La)"
2/
Case 2. (g(S)) > (S*) In this case, setting e = 1/10 in Lemma 3.3 we note that the probability that (CAF(S*)) YoaGsF (St) is at most:
exp (2rg- 2)*
exp
%
(aa(S*) (s)))))))))))
< exp
(-160log A2(Lo)²)
2500%
2500
-160 n
-8/5
exp
100
8

---

Published in Transactions on Machine Learning Research (05/2025)
The last line follows from Assumption 2.12 2).
Hence, with probability at least 1
8/5 (GAF((") & m0GAr((3) holds.
By
Lemma
2.8 this implies , S
O AuALLAA)A((AA))
Together with Lemma
3.2
we obtain that with probability at least
Aa(Ga 1972
8/5 3n 21/11
A
AcLLOAF)(GAPP)12 \a(TGar)312
( (2aLbo)((C)
drizo , <
n1 ==
11, (3.8)
Xa(Tia)1/2
>a(Lo))
finishing upper bound on (
We now present our proof of Lemma 3.3
The main idea behind the proof follows: first, we show that Lemma 3.3 with SF replaced with any fixed subset A. Then, we the fact that
Proof. (Lemin 3.3
holds
Pr (100GGFF(55) (GAF(S*)) = Pr (100GsF(Sp) < (GGFF(S)) (a((s))) > roac(S"))
Σ
Pr(ST- = A) Pr (YOGGF (5%) aGAF(S") Sp A)
Pr (MOGAr(A) < oGAr(S")),
Arao())>ma0(55))
(3.9)
as ΣA Pr(Sp = A) 11 Now, we bound Pr (MOGAEF() < OGGF((")) for any fixed A.
Claim 3.4. Let S* denote the minimum cut of G. Suppose an any 7 >>> 1 and 2 IA en,
18 for some 1 >>>> 0. Then, for
Pr Pr(aagA(A)) - (GGF((")) < exp ( (S+)) .
(3.10)
25y²
Proof of Claim 3.4 Let YA == - - aGAFF(S") We wish to show that YA 2 0 with high probability,
For any tuple (x,y) V V, define X(ay)) as the boolean random variable such that X(z.)) if xy E E(GAF) and ((x.y) otherwise. As X(x,)) (g.a),, we abuse notation and write Xay shorthand for both these variables. Note that Xay are all mutually independent, and
((X()))) Pr(zy e B(GAF)) = P.
iee E(G), 1-p, ife E(G).
(3.11)
Further, for any subset C V, by definition
(GLF(A) = EGOF(A,A)
X(z.))) (a.))
Σ
[A| AAl
|
Which, by 3.11 implies
E(aGsF(A)) [A||A]
Σ E(X.) +
Σ
E(Xx)
(EFF((A,))
TEAXT)
(3.12)
(eg(A, -11 (1-p) | p- (G,A
|AJAA
= (1 2p) (c(A) +p.
9

---

Published in Transactions on Machine Learning Research (05/2025)
Let y denote the expectation of Ya. By linearity and 3.12
4
1 = B(Ya) = (1 2p) (Aac(A) - (G((S)))+++))))))))))))))))))))) + (7 ()-1)> >
5 (
(3.13)
As 7 > and p < 1/10. We also have μ > O, and Pr(YA < 0) Pr(YA - H -p). Now we shall use Hoeffding's inequality to provide an upper bound on Pr(Y4 < 0). To that end, YA has be rewritten as a sum of independent random variables. However,
YA = AJ|A]
Σ X. ΦεAXĀ
Σ
X
(3.14)
SS
x
As the two summations in YA have overlapping terms, we separate them follows. Let Zi 8" \ A, S* U.A Observe then,
Z2 8* A, Z3 = A Z4
5- = (Z) x Za) U (Z x Z4) (22 x 23) U (22 x Z4) A A = (3 x 2 U (Za x Z4) L (2 x Z1) U Z2 x Z4)
(3.15)
This lets break cach sum in 3.14 into four parts, and using X(m.y) X (v.z);
write Y as
XX=
X.
YA =
E
X +
E
Σ
|
|S*
A||A
|S*
(2(22x2))1(22x211
EE(2 (2
2E(2,x2.1
(3.16)
Note that all summands (.16] are independent of cach other. For simplicity, let us denote 23 == |Z for = ,,....,,. 4.
Since -ld S c.e |c| for any constant E I,, use Hoeffding's inequality to get Pr(Y <0) = Pr(Ya
# < -4) S exp( 2/² where D 4(1123 23 + 2224) (=>=23))2)t2)) (21+22()9+2a))
2 473( (2
21)))))2)22) After some caleulations, this leads to (
D 472 + (23 + 24)
4(22 23) 24)
87 + 2221)
(3.17)
(22 + 233 (2))((2 24)
(2) + +2) + 24
(2) + 22) + 24) + 23) + +24
(21 22) + 24)
(22 22)(2 + 24)
4/2
(3.18)
(22 + 23)² 1 24
(E) + (23 + 24)²
|5
A
n²/4
8/2
47²
< <47 2
(3.19)
|/
J.St 11
2nd/44
2nn2
Here 19 follows from the fact that n² n²/4 2 |
|5
A 2 en n/2. Therefore, in conjunction with ((7ac(A) ())-ac(8"))
|||||
3.13), we obtain Pr(YA < 0) I exp
2n²
< exp
25,
2n² as desired.
Now we return to our proof of Lemma 3.3
For any set A V with 2 14 2 en and ac(A) > rSa we
have Pr()0CGA((A) < OCAF(S*)) < exp
4(maa () ( 2n²) S exp 25n
4(76-1)
(0)
25%
When we plug this back into Equation 3.9 it gives our desired bound.
4 Instability of spectral clustering when p wllogn/n)
We now construct a family of random graphs G, whose sparsest cut (in expectation) drastically changes under edge flipping with = wlogn//n) The formal construction is given in Theorem 4.1 In the construction, we denote by G G(n p) a random graph generated according to the Erdös Rényi model with n nodes and connection probability p. Denote F g(n,p), p), and recall that the result of the odge flipping is GAF. Furthermore, we consider the matrices whose entries are the expected values of the corresponding entries in Le and LEAF. These matrices are denoted by [[[a]] and E[LGAF), respectively.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Theorem 4.1. Let 1/2 3> 1/10 be constont. Let G be graph vertices with verter set AU BUC, where |A| = Bn, [B] = G[A] = G(3n, 400 laglllgg"/nnn n/n), G = ((n, l/gn/n) and G[C] = ( B)n/2, 400 400 log" n//.. Further, suppose that every pair of vertices (x.y) y) with x E B and E C. are adjacent with a probability of 20 log n/n. Finally, let any pair of verlices (x,y) with x E and y E B U C are adjacent with probability 1/10n. visual representation of this construction showm in Figure 4-1 (left). Then, the following holds:
= (1- (1-18)m (1- -.) Suppose the induced subgraphs of G on A, B and C satisfy
G salisfies Assumplion 2.12 expectation. In other words, the expected mazimum degree of G, denoted by A, satisfies N 10 log nz (E(La)), the value of (e( larger than 1/10, the value of (((ELC))(()) is small, and Xa (B(( 2 10 {a(E(
2. When wlog lim AL noc AL =
B (1 - B)n/2
B (1- B)n/2
G((B),
log 12
dl)
C o(p)
G(IA), 400 log"
20 n
G(AA). ((mxx(p, log"
p -ppp)
a
|A| = BBn
IA| 8n
p- o(D)
10m
G(IC), 100 log
G(IC). (maxx log"
|C| = (1 B)m/2
|C| = (1 - B2n/2
Figure 4.1: The graph G (left) and the graph GAF where = g(n,p) (right). Dashed lines represent probabilistic edges between the parts A, B and C.
Proof of (1). It is straightforward to see that the expected maximum degree of G satisfies
A = (11 (1- -1) log n + -1-B)
-) n 20log n + Bn 10m = 200(1 - log n + O(logn.. (4.1)
n
Next, we observe that E[La] is block matrix with blocks corresponding to A, B, C. The first three eigenvectors of E[La] would therefore take constant values on the blocks A, B and C. The normalized eigenvector of Aı (E([a)) = 0 is constant on all three blocks, that of {g(E[Le]) is constant on A and B C (since the density of edges between B and C' is larger than between A and B UC,,, and that of {s(B[La]) can take different values on cach blocks. Suppose the cigenvector of (e[[[]] takes the value 22 on A and y/2 on B BUC C, then, by the fact that the sum of all elements of the eigenvector O, we must have 3xq (1 B)y2 0. Also, by the fact that the sum square of all elements of the eigenvector is we must have 3nrz + 9)ny? 1. This implies that I2- = + 1-8 and 8/2 FV (1 Let the second Bn
eigenvector of B[[a] be (u2))iv- Since (B([T] = EiistE (12,5 - v2,)),, we obtain that:
da (B(Ta]) Bn (1 B)n
(r2 - y2)² 3(1 3(1 3)
4
(4.2)
10n
10
3(1
Byn
10"
Now, as the eigenvector of >a (B(La)) will take values of, say, 43 on A, ya on B and 23 on C, then, because the
sum of all elements of the eigenvector is 0, they satisfy 323 + (1- 3) / (1- 2) = 0. Because the sum square of all elements of the cigenvector is 1, they satisfy 33.33 (11
82 2|
Additionally,
since the second and the third eigenvectors are orthogonal, we obtain that 222
1-8
2 92 Us 1 92.22 23
92-
Since fag + B)yz 0 and frz -(1 (1- 88)2, we obtain that 23 ya/2 23/2 0. By solving the three
11

---

Published in Transactions on Machine Learning Research (05/2025)
equations, we obtain that 23 = 0, ys - 1
23 F
Let the third cigenvector of B|Lc] be
/11-8n²
(1-
(Us,)vev- Since AB(B([cc)) = > "(id)E (V3,1 - V3,1)²
3(1 3)n?
+ (1 3)2n² 20 log
4
Aa (B((EL)
20(1 - (3) log n + 0(1) (4.3)
10n
(1-
4n
(1 - 8)m
For these values, we notice that m)G)) = in expectation.
200 1 B) log n:4
is small, thus satisfies Assumption 2.12
400(1 10001119)- 3)2
log n-10 5(1-8)
Proof of (2). Since GDF is obtained from randomly flipping adjacencies with probability p, observe that (Aa), where J is the all-oncs matrix. Note that the average degrees of the nodes of
[(AGaF)= = p1 2p) GAF are the entries [(AGAF)1 where 1 is the all-ones vector. Thus, E(AGLF) 1 = pm1 + 2 A.) For the diagonal degree matrices, this implies that E ((GGa)) = diag(E(AGAr)) In terms of the average Laplacian matrices, this gives us the relation
pnl + (1 - DG).
B[La^F]= pnl + (1 (1-2))())))) PJ - -(1--11-1 (1- (122))B(Ac) pm (1 (1- + BB)
(4.4)
Let {n1 1, 12,....., ) be the eigenvectors of T[[.a)- Observe that B[LGar]] 1 0, thus 1 is clearly an eigenvector of B| On the other hand, when * 1, by orthogonality we have that Jv: = 0, and thus,
ElLGoFly: pnvy + (1 11-2)BBLaJus = (pn + (1 (BLLa))))
(4.5)
Equation 4.5 implies that E[LGAF] and EE| [a] share the same eigenvectors, and moreover, since we assume that v 0.5 in this work, we obtain that for i + 1,
A (E|[Ga))) = pm + (1 2p)
(4.6)
Now, since np = w(logn) = (As(E()))) we obtain
lim (B(LOGF)) lim n-000 A3 \B(Ea(aa n-000 pm + (1 - Ap E T.a])
pn + (1 (1- 2p) (B LG)) 1.
(4.7)
Since the Laplacian matrices LG and LGAF closely resemble their expectations E[Lo] and E[LGaF] discussed in Chung Raddliffe (2011): Lu & Peng 2013), Theorem 4.1 implies that the graph G satisfies Assumption 2.12 Moreover, the ratio Aalbeas! close to one, indicating that spectral clustering is unlikely to yield accurate clustering results with high probability.
Xs[Lasr]
5 Experiments
We conduct experiments on real social networks to verify our theoretical results. In this work, we mainly use the network called "Social circles: Facebook" obtained from the Stanford network analysis project (SNAP), detailed in Leskovec Mcauley] (2012). We found that spectral clustering cannot find plausible results for some of those networks, duc the fact that there are many connected components, and also small sets of nodes with only one to two edges to the rest of the graph. Those small sets usually form a cluster in the outcomes of spectral clustering, which makes the outcomes undesirable. We therefore decided to eliminate all small node sets that have at most 10 outgoing edges.
We examine the graphs defined in the files "0.edges" and "1684.edges." We call the graphs as Facebook0 and Facebook1684. After removing nodes of small degree, there are n = 120 left in the first graph and n = 574 left in the sccond. As illustrated in Figure [..] the social network FacebookO composed of two clusters, both of which are quite sizable. Alternatively, the social network Facebook1684 is divided into three clusters. The first is small yellow cluster including nodes 0-15, followed by bigger cluster of yellow nodes, and
12

---

Published in Transactions on Machine Learning Research (05/2025)
210
1.70
1.50
1:20
0,002 Flipping Pockuiilit
(a)
(b)
Figure 5.1: (a): The social network Facebook1684 obtained from SNAP after pruning. Each node was assigned a color based on the spectral clustering outcomes. (b): We generated 100 graphs from the first graph FacebookO (Figure 1.1), and plotted the worst discrepancy daize between the outputs of the spectral clustering of the original and perturbed graphs for these 100 random runs.
dense cluster of blue nodes. For ease of reference, these clusters will be subsequently named Cluster A, Cluster B, and Cluster C, respectively. Both Facebook0 and Facebook1 684 have the attributes necessary for Assumption 2.12
Our main theorem ensures that the clustering outcomes remain mostly consistent when edges are flipped with probability p < logn The upper bound is about 0.004 for FacebookO and about 0.001 for Facebook 1684. We examine p {0.0001q 1 q S 50). For cach probability p and graph, we create 100 random graphs F with the given probability. Note that the original graph is represented by G. We then compute the difference between the clustering results of G (represented by SC2(G)) and that of GAF (represented by SC2(F)F)).
10s
The chart in Figure 5.1b shows the result we obtain from the first graph. The chart demonstrates the differ- ence between the clustering outputs, represented as the worst-case results across 100 randomly generated graphs for each probability setting. We present the worst outcome among the 100 trials to highlight that, even in the least favorable scenario, the distance remains small. This demonstrates the robustness of the method.
(C2(F)))). The values shown represent
Figure 5.1b reveals that, across all considered probabilitics, the clustering outcomes remain consistent in every random graph. In each instance, when comparing the original graph to the graph with flipped edges, a minimum of 116 nodes are assigned to the same clusters. Only a maximum of four nodes out 120 experience change their cluster placement.
For the second graph, the result is even more robust. For all the probabilities we have conducted the experiment, there no change in the clustering results by the edge flipping. These two experiments suggest that the clustering results exhibit strong resilience to edge flipping.
5.1 Results on Larger Flipping Probability
Our experiments In Figure 5.2 the flipping probability is raised above the level outlined in Assumption 2.12 with the network derived from the Facebook( network demonstrate that clustering outcomes remain stable as long as the flipping probability does not exceed 0.15.
In contrast, with the network derived from Facebook1684, the stability the results is preserved only when the flipping probability remains under 0.04. Utilizing spectral clustering on the original graph divides it into two segments: one combining clusters A and B, and another comprising cluster C. However, exceeding flipping probability of 0.04 occasionally alters the spectral clustering outcome to group consisting of
13

---

Published in Transactions on Machine Learning Research (05/2025)
430
100
90-
0.0
0.5
0.30
8.15
0.00
0.55
0.00
0.01
0.02
0,11
0044
015
Figping Prolubsikty
Finuing Prodabilie
(a)
(b)
Figure 5.2: The robustness results of the social networks upon the introduction of flipping probability that exceeds the value specified in Assumption 2.12 (a) for FacebookO network and (b) for 689 network.
cluster and another combining clusters and C. This variation seems reasonable, the latter grouping also yields low conductance.
Section 4 demonstrates that in certain networks, clustering outcomes are unstable when the probability exceeds the level specified in Assumption 2.12 However, our experiments indicate that this threshold may be higher for particular graph types. In future work, we plan to develop theoretical results for these specific graphs
5.2 Average Distances
While the maximum distances across the 100 iterations underscore the robustness the algorithm, we also present the average distances in Figure 5.3 to offer a more comprehensive assessment. The plots reveal that, although the worst-case distance can be large, the average distance remains relatively small even under high flipping probabilities. This suggests that spectral clustering with randomized response maintains robustness average, even when the flipping probability exceeds the theoretical bound established in our analysis.
150
45-
8.l1c. SC/OAFD
20-
100
8.5
2.0
25-
15-
810
oda
Floppig Probabilty
Floppin Probabilit
(b)
Figure 5.3: The average dsize results of the social networks upon the introduction of a flipping probability that exceeds the value specified Assumption 2.12 for (a) the Facebook0 work and (b) the Facebook168 network.
6 Concluding Remarks
In this manuscript, we demonstrate and empirically verify that under some assumptions, the spectral clus- tering algorithm is robust under the randomized response method. While primary objective is its
14

---

Published in Transactions on Machine Learning Research (05/2025)
in local differential privacy, our validation also confirms the robustness of spectral clustering against social networks containing inaccurate adjacency information. We demonstrate that the outcomes are robust when < / n/10n, but also acknowledge that the results can undergo significant alterations for larger values. This occurs because randomized response introduces an excessive number of edges to the graph in such cases. We are aiming to examine the robustnness of other local (approximate) differential privacy approaches (e.g.. as in Adhikari et al. (2020)) that do not add as many edges as the randomized response method.
Although in Peng & Yoshida 2020), there are results for spectral clustering with k clusters, cannot use ideas from those results in this work. Indeed, because also consider edge addition, we have to demonstrate many additional thcoretical results including Lemma 2.4 and Lemma 3.3 These analyses cannot be directly extended to the case when k > 2. We, anyway, believe that such an extension would be interesting future work.
Acknowledgements
We sincerely thank the anonymous reviewers for their valuable feedback and Prof. Kamalika Choudhury, the action editor, for their kind and thoughtful handling of our mamuscript. Sayan Mukherjee is supported by JSPS KAKENHI Grant Number 24K22830, and the Center of Innovations in Sustainable Quantum AT (JST Grant Number JPMJJPF221). Vorapong Suppakitpaisarn is supported by KAKENHI Grants JP21H05845, JP23H04377, and JP25K00369, as well as JST NEXUS Grant Number Y2024L0906031.
References
Maneesh Babu Adhikari, Vorapong Suppakit Arinjita Paul, and C Pandu Rangan. Two-stage frame- work for accurate and differentially private network information publication. In CSoNet 2020, pp. 267-2667222 279. Springer, 2020.
Decksha Adil and Thatchaphol Saramurak. Decremental (1+c) (1+c) -aprroxmmat maximum cigenvector: Dynamic power method. arXie preprint orXiv:2402.17920 2024.
Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83 96, 1986.
Apple's Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Research, 2017.
Albert-Tász16 Barabási and Réka. Albert. Emergence of scaling in random networks. Science, 286(5439)) 509 512, 1999.
Jeff Choeger. A lower bound for the smallest oigenvalue of the laplacian. In Problems in Analysis, pp. 195 200, 1971.
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel. Private estimation algorithms for stochastic block models and mixture models. Advances in Neural Information Processing Systems, 36:68134 68183, 2023.
Fan Chung and Mary Radcliffe. On the spectra of general random graphs. The Electronic Journal of Combinatorics, pp. P215-P215, 2011.
Shaofeng Deng, Shuyang Ling, and Thomas Strohmer. Strong consistency, graph laplacians, and the stochas- tic block model. The Journal of Machine Learning Research, 22(():5210-52 52535555,,3,3,, 2021.
Cynthia Dwork. Differential privacy: A survey of results. In TAMC 2008, pp. 1-19, 2008
Paul Erdós, Alfród Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5 (1):17 60, 1960.
Úlfar Erlingsson, Vasyl Pihur, and Alcksandra Korolova. RAPPOR: Randomized aggregatable privacy- preserving ordinal response. In SIGSAC 2014, pp. 1064-1067, 2014.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Nan Fu, Weiwei Ni, Sen Zhang, Lihe Hou, and Dongyue Zhang. GC-NLDP: A graph clustering algorithm with local differential privacy. Computers & Securily, 124:102967, 2023.
Stephen Gualtery and Gary L. Miller. On the performance of spectral graph partitioning methods. In SODA 1995, pp. 233 242, 1995.
Lars Hagen and Andrew B Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aider Aided Design of Integrated Circuits and Systems, 11(9):1074-1085, 1992.
Jonathan Hehir, Aleksandra Slavkovic, and Xiaoyue Niu. Consistent spectral clustering of network block models under local differential privacy, Journal of Privacy and Confidentiality, 12(2), 2022.
Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Cycle counting under local differential privacy for degeneracy-bounded graphs. In STACS 2025, pp. 49:1-49:22, 2025.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(31)):13 30, 1963.
Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In USENIX Security 2021, pp. 983-1000, 2021.
Tianxi Ji, Changqing Luo, Yifan Guo, Qianlong Wang, Lixing Yu, and Pan Li. Community detection in online social networks: A differentially private and parsimonious approach. IEEE Transactions on Computational Social Systems, 7(1):151-163, 2020.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793 826, 2011.
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lec, Shayan Ovcis Gharan, and Luca Trevisan. Improved Cheoger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In STOC 2013, pp. 11-20, 2013.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snag stanford. wdw/ /dta June 2014.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. NIPS 2012, 25, 2012.
Linyuan Lu and Xing Peng. Spectra of edge-independent random graphs. Electron. J. Combin., 20(4):Paper 27, 18, 2013. ISSN 1077-8926. doi: 10.37236/3577 URL https://doi. org/ 10. 37236/3576
Naurang S. Mangat. An improved randomized response strategy. Journal of the Royal Statistical Society:
Series B (Melhodological), 56(1):93 95, 1994.
Michael Mitzenmacher and Eli Upfal. Probubilily and computing: Randomization and probubilistic techniques in algorithms and data analysis. Cambridge University Press, 2017.
Mohamed S Mohamed, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. Differentially private community detection for stochastic block models. In ICML, 2022, pp. 15858-15899 2022.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In STOC 2007, pp. 75 84, 2007.
Pan Peng and Yuichi Yoshida. Average sensitivity of spectral clustering. In KDD 2020, pp. 1132-1140, 2020.
Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! In COLT 2015, pp. 442-1455 2015.
Yue Wang, Xintao Wu, and Leting Wu. Differential privacy preserving spectral graph analysis. In PAKDD 2013, pp. 329-340, 2013.
Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In EDBT//CDT Workshops, 2016.
16

---

Published in Transactions on Machine Learning Research (05/2025)
Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistioul Associalion, 60(309):63 69, 1965.
Yen-Chuen Wei and Chung- Kuan Cheng. Towards efficient hierarchical designs by ratio cut partitioning. In TCCAD 1989, pp. 298-3888 208,,00,1 1989.
Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleicheen (mit einer anwendung auf die theorie der hohtraumstrahlung). Mathematische Annalen, 71(4):441 479, 1912.
Tianqing Zhu, Gang Li, Wanlei Zhou, and S Yu Philip. Differentially private data publishing and analysis: A survey. IEEE Transactions on Knowledge and Dala Engineering, 29(8):1619 1638, 2017.
17


Reviews:
[{"review_id": "wnON8xty6m", "reviewer": "Reviewer_cShT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper evaluates the behavior of the algorithm both analytically and experimentally.\n\nWeaknesses:\n\nAn epsilon of log(n) can support extremely non private algorithms, yet the paper doesn't recommend against using such a high value for privacy, or justify why such a high epsilon still provides the effective privacy desired from the proposed mechanism.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper reasons about private clustering of n-vertex graphs with k=2 clusters (which additionally satisfy some other well-clustering guarantees.) In particular, they consider a previously studied local DP algorithm for producing a private copy of the input graph, and reason about the utility of running spectral clustering on this copy. While prior work in this area only considers graphs generated from the stochastic block model, this work considers a broader class of graphs, albeit still satisfying a number of assumptions on the clustering. They show that for this larger class of graphs, one must use a pretty high value for epsilon in order to preserve the desired utility of spectral clustering.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Ways to strengthen the work:\n\nGiven that a large part of the motivation of the paper is to study more general social networks, it would have helped to have some discussion of the ways in which the studied graphs represent existing social networks better than those generated by SBMs. Especially since this work is restricted to the case of two clusters.\n\nMinor comments:\n\nIt would be helpful for the definition of an individual to map to the definition of neighboring dataset. (The current introduction states that nodes are individuals, but then privacy guarantee considered in this work local-edge-DP.)\n\nThe introduction seems to imply that having a privacy budget $\\epsilon$ is unique to local differential privacy, this should be corrected since it may confuse readers.", "broader_impact_concerns": "An epsilon of log(n) can support extremely non private algorithms which I believe needs to be addressed in the manuscript and presentation if the work is accepted to TMLR.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CSFe2rOlnT", "reviewer": "Reviewer_ngYy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n**S1.** The paper provides a comprehensive treatment of the problem via theoretical and experimental results. The writing is mostly clear, and the submission is well-structured by giving most of the necessary background so that it is possible for a person who is not an expert in this particular area to understand it.\n\n**S2.** The theoretical analysis considers general graphs, a more realistic setting than the commonly assumed Stochastic Block Model (SBM), which seems a valuable contribution.\n\n**S3.** Submission is quite accurate from a mathematical perspective. The definitions, assumptions, and necessary lemmas are provided in the main text with proofs. I did not note errors or inconsistencies. However, I did not verify all the steps of the main theorem.\n\n## Weaknesses\n\n**W1.** Applicability/generalizability of presented experimental results seems limited as the conclusions are based on 2 graphs. The evidence is also not always presented for all claims.\n\n**W2.** Some definitions (e.g., in Section 2.1) and assumptions (e.g., about social network properties in Assumption 2.10) lack sufficient clarity. There are several requests for clarification in Section 4 related to notation.\n\n**W3.** Bound in (1.1) looks restrictive as large $n$, i.e., $10^6$, results in $\\epsilon > 6$, which seems a pretty weak DP guarantee in general. However, I know that for some ML applications, it can be more reasonable, but I do not know what is meaningful in this graph clustering with local DP context. Moreover, desirable small $\\epsilon < 1$ seems unreachable.\n\n\n### Minor questions\n\n- I am also curious why pure DP is considered. Has approximate DP been investigated in such a context?\n- It is a bit unclear why there is such a focus on this particular combination of clustering algorithm and DP mechanism. Why not other approaches?\n- The reasoning in the first sentence of the commentary on the plausibility of Assumption 2.10 is not fully clear to me as Section 2.2 reasons the privacy budget to be lower-bounded by $\\log 1/p$.\n- Why random graphs $\\mathcal{G}(n, p)$ appear in the proof for general graphs?\n- What is $B$-$B$ edge? Does it mean edges between vertices from set $B$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Submission studies the problem of spectral graph clustering stability under local $\\epsilon$-edge differential privacy constraints. In contrast to prior works, the authors analyze general graphs. They provide a high probability upper bound (depending on the spectral robustness of the graph) on the number of misclassified vertices for a flipped probability of $\\mathcal{O}(\\log n / n)$. In addition, they argue that a higher flipping probability of $\\omega(\\log n / n)$ may result in unstable private clustering for some graphs. Experiments on Facebook social networks support the theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please provide references to justify claims about the properties of social networks. Specifically:\n\n> “Social networks are not dense in practice.”\n> “The second assumption derives from usual properties of social networks.”\n\nCiting relevant literature would strengthen these statements.\n\n- A discussion on the technical novelty of the proofs and techniques would be valuable. Clarifying whether the derivations build upon existing methods or introduce fundamentally new ideas would help contextualize the contributions.\n\n### Minor Changes and Questions:\n- A table comparing results to prior works would improve clarity and provide better context alongside the textual description.\n\n- In Theorem 1.1, the phrase “small constant” $\\eta(G)$ should be specified more concretely. As currently stated, $\\eta(G) > 1$ would render the result meaningless since the number of misclassified vertices would exceed the total number of vertices $n$.\n\n- The notation $\\sim_p$ in Section 2.1 is unclear on first reading. Does it mean that each edge is sampled with probability $p$, or is it sampled uniformly among all subsets? The phrase “uniformly with probability $p$” is ambiguous and should be clarified.\n\n- Since $\\eta(G)$ plays a crucial role in the core result, defining its possible range and interpretation would be helpful for better understanding.\n\n- The description of the first step of the spectral clustering algorithm lacks clarity. How is “reordering” performed? What is the computational complexity of the method? What is meant by “approximate eigenvector computation”? How does this approximation impact the clustering and any associated privacy guarantees?\n\n- Lemma 2.6 relies on Lemma 3.5. For completeness, it would be useful to restate Lemma 3.5 (e.g., in the Appendix) and provide a more detailed proof.\n\n- In Figure 4.1, what does the notation $K$ represent? A brief explanation in the caption or main text would clarify this.", "broader_impact_concerns": "No concerns for this submission", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZnB9LyQUbV", "reviewer": "Reviewer_HF5H", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper lies in its first and third contributions. These results are the first of their kind to provide evidence for the performance of randomized response for graphs outside the SBM. The first theorem makes much more mild assumptions on the input graph than it being drawn from the SBM, and has some interesting proof techniques. The experimental design is well-founded.\n\nA primary weakness of the paper is that the results are a bit less significant from a privacy point of view. They are demonstrating that a privacy guarantee of \\epsilon > \\log(n) is necessary in order to be able to have utility from the algorithm. However, this would be considered quite low privacy in the broader literature. This is also unappealing given that the prior work shows that clustering is possible for small values of epsilon for SBM graphs using better algorithms.\n\nA second weakness is concerns about rigor. The clustering instability of the hard graph family seems to only hold in expectation, and I think a formal proof of instability is required. The argument in its current state is quite high-level, and it does make it clear what is special about the choice p = \\frac{\\log n}{n} for instability. Furthermore, the experimental data could be made less noisy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper contributes three primary results.\n\nFirst, a novel theorem demonstrating that a large class of graphs which are \"spectral clustering friendly\" are able to be again clustered when the graph is released using randomized response for each edge with probability p = \\frac{\\log n}{n}. This goes beyond prior work which only provides similar guarantees for graphs in the stochastic block model (SBM). \n\nSecond, they provide evidence that graph clustering is not robust to edge flipping probability of higher than \\frac{\\log n}{n} by constructing a hard graph family.\n\nThird, they empirically evaluate spectral clustering techniques on real world graphs, evaluating the effect of p on the clustering error.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The argument in Section 4 is too high-level, and could benefit from a formal theorem statement. In particular, it seems like the high-level argument could hold for any value of p, and it needs to be formally argued what happens when p suddenly becomes \\frac{\\log n}{n}.\n\nThe experimental graphs are too noisy, and while I think the high level trends are valid, I have concerns about reproducibility. Consider running each value of p 100 times and plotting the average clustering distance. This would show a nice, smooth upwards trend in the clustering error against p.\n\nIn Section 3, it would be nice to spend some time interpreting the obtained result, specifically for which graphs we can expect \\eta(G) to be small (possibly in terms of the sparsity of the graph). Furthermore, it would be helpful to make a comparison here to prior work---while that work makes much stronger assumptions about the graph, is it possible to apply Theorem 3.1 to SBM graphs and recover the prior results?", "broader_impact_concerns": "No broader impact statement is necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The results are sound, and supported by evidence. As a result the paper passes the TMLR acceptance bar.
Decision: Accept (poster)