Federated Spectral Clustering via Secure Similarity Reconstruction
Authors: Dong Qiao
Chris Ding
Jicong Fan
Venue: NeurIPS 2023 poster (2023)
Keywords: clustering
federated learning
privacy

Abstract: Federated learning has a significant advantage in protecting information privacy. Many scholars proposed various secure learning methods within the framework of federated learning but the study on secure federated unsupervised learning especially clustering is limited. We in this work propose a secure kernelized factorization method for federated spectral clustering on distributed dataset. The method is non-trivial because the kernel or similarity matrix for spectral clustering is computed by data pairs, which violates the principle of privacy protection. Our method implicitly constructs an approximation for the kernel matrix on distributed data such that we can perform spectral clustering under the constraint of privacy protection. We provide a convergence guarantee of the optimization algorithm, reconstruction error bounds of the Gaussian kernel matrix, and the sufficient condition of correct clustering of our method. We also present some results of differential privacy. Numerical results on synthetic and real datasets demonstrate that the proposed method is efficient and accurate in comparison to the baselines.

Federated Spectral Clustering via Secure Similarity Reconstruction
Dong Qiao 1:2
Chris Ding' Jicong Fan 1,2+
"The Chinese University of Hong Kong, Shenzhen, China Shenzhen Research Institute of Big Data, Shenzhen, China
dongqiao0l ink. cuhk. edu. {chrisding, fanjicong' Ccuck. edu.
Abstract
Federated learning has significant advantage in protecting data and informa- tion privacy. Many scholars proposed various secure learning methods within the framework of federated learning but the study on secure federated unsupervised learning especially clustering is limited. We in this work propose secure kernel- ized factorization method for federated spectral clustering on distributed data. The method is non-trivial because the kemnel or similarity matrix for spectral clustering is computed by data pairs, which violates the principle of privacy protection. Our method implicitly constructs an approximation for the kernel matrix on distributed data such that we can perform spectral clustering under the constraint of privacy protection. We provide convergence guarantee of the optimization algorithm, reconstruction error bounds of the Gaussian kernel matrix, and the sufficient condi- tion of correct clustering of our method. We also present guarantees of differential privacy. Numerical results on synthetic and real datasets demonstrate that the proposed method is efficient and accurate in comparison to baselines.
Introduction
In the era of big data, human beings can analyze massive data in various fields due to the improvement of storage and computational capabilities of computing devices [Li et al. 2020b). Some popular fields such as artificial intelligence, machine learning, internet of things (loT), and cloud computing have seen explosive development over the past few years. Nevertheless, side effect of this trend is that individuals and organizations have more and more concerns about potential violation of privacy [airouuz et al. 2021].
result, it has become a challenge mine valuable information from user data but not to directly access it.
Federated learning Kairouz al. 2021 McMahan al. 2017 can train global model without retrieving dispersed data [Yang et al, 20118. This advantage has made it so popular that many scholars have put much effort into the study federated learning. For example, example.[Yang al. (2019] presented the definitions of horizontal federated learning, vertical federated learning, and federated transfer learning. Some
machine learning models were also presented. For instance, He er al. (2020) developed a federated group knowledge transfer algorithm to train small CNNs on edge devices. Chen al. (2018) proposed a protocol to conduct over nigh-dimensional data. Besides, Kim et al. (2018) proposed a block-chained federated learning architecture that enables on-device learning without any central coordination.
ridge regression
Regardless of the great progress of federated learning, it can be found that most of the existing studies are for supervised learning [Li al. 20200a Ghosh al. 2020). Note that collecting labeled data may deserve very high cost in real situations [Li el al. 2020b while unlabeled data are abundant. Thus,
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

is necessary and important to study federated learning for unsupervised learning [hhng et al. 2020
Tzinis al., [021;] Zhuang et al. 2021
Dennis et al. 2021 such as clustering [Ng g et al. 2001 Fan
and Chow 2017 an et al. 2018
2021 Fan 2021 Cai el al. 2022 Fan et al.) [022] For example, Li
et al. 2021 proposed a federated matrix factorization with privacy guarantee for recommendation
systems. Wang and Chang [022] proposed two federated matrix factorization algorithms that can be
used for federated clustering. Besides, there are some studies on federated spectral clustering. For instance, Wang et al. (2020) presented a federated multi-view spectral clustering method under the assumption that the data of each view are in one client. Hernández-Pereen Pereiia et al. [202T] developed a cooperative spectral clustering model to deal with distributed data but the model linear. However, the study on federated spectral clustering is still very limited and deserves more attention and effort.
In this paper, we propose a federated kernelized factorization method to reconstruct a similarity matrix for secure spectral clustering on distributed data. Our contributions are as follows.
We propose federated spectral clustering algorithm and provide convergence guarantee for the optimization.
We further propose to add noise to the data or the learned factors to enhance the security of clustering and provide guarantees of differential privacy.
We provide upper bounds for the reconstruction error of the true similarity matrix and theoretical guarantees for correct clustering.
We test our method on both synthetic data and real datasets in comparison to baselines, which verify the effectiveness of our method.
Notations We use y, y. and Y to denote scalar, vector, and matrix, respectively. The element of Y at row i and column j is denoted by Vij- We use || ||2 to denote the lg norm of a vector and use Tr(.), || [|,, and I1pp to denote the trace. Frobenius norm, and spectral norm of a matrix respectively. The for norm and f2,00 norm of matrix Y are defined as || maxig | and || max; v Vi respectively. K, IC, K, and k denote the kernel matrix, kernel function, number of clusters, and the number k in KNN, respectively. & denotes the feature map induced by X.
2 Federated Spectral Clustering (FedSC)
Suppose we have n data points of dimension m distributing in P clients. For convenience, we denote by X gmxxn the matrix composed of all the n data points and denote by X, RR the matrix composed of the Np data points in client Cp, where Np 2 1, p 1,.... P. and Ep N, n. p-1
Without loss of generality, we let X = [X1, X2.... Xp). which means 1 of X. Our goal is to perform spectral clustering on these data to partition them into K groups, under the constraint that the data in each client cannot leave the client itself and the privacy of the data should be protected as much as possible, though there could be a central server conducting clustering.
submatrices
The aforementioned task is non-trivial because in spectral clustering, the first step is constructing an adjacency matrix A E RR which has to evaluate the similarity between every data pair (z), x,,) using metric function -(.-) and hence violates the privacy constraint in the task. To solve the problem, we present a federated spectral clustering model in this section.
2.1 Similarity Reconstruction via Feature Space Factorization
In spectral clustering, for MM,,,), there are many choices such A nearest neighbor similarity and various kernel functions. Let KC(..) be a kernel function and we have
K(æ,, æ.)) (((x))T((EE)) d(x,),
(I)
where Φ : m + Rmn is feature map induced by the kernel function and does not need to be carried out explicitly. When it comes federated spectral clustering, the central server has no access
'The most widely-used kernel is the Gaussian kernel K( æx)) exp 2 x; x |13), of which the feature map is an infinite-order polynomial feature map and is hyperparameter controlling the smoothness.

---

to the raw data distributed in clients and hence cannot compute K( (ty) using However, if the central server can learn an effective approximation (denoted by ((x;)) for each ((x;)) without accessing Wi, (a (z)) be estimated, i.e.,
K(;;; my) = Φ(x;) ((x;))
(2)
Thus, inspired by Fan and Udell 2019 Fan al, 2021 we propose to approximate each ((x;) by
((x,)) - (Z)c;
where Z = [21 22. ....... zd] E Rmxd o ( ((2)) .... ((za)], and c; Rd. Both Z and
C2 are learned from individual columns of X and they can be regarded as intermediate variables avoiding the direct access of central server æ; (details of the learning will be introduced later). follows from ( and (3) that
(() cf ((Z) (Z)
(4)
Thus we can reconstruct the similarity between a; and zj via (4) For convenience, let K, xXX,X) = ( ( K.; = K( Z) = o ( O E Raxd and C = [e1, c2...., Cnl
Rdxn_ Then we have
K (1()) K
(5)
Now we use KEy as a reconstructed similarity matrix for spectral clustering. In the form of federated learning, we expand to
(X,)) = (Z)Cp. p p_
(6)
It indicates that Z is shared for all P clients and Cp is private for client cp. Note that (6) is matrix factorization problem in the feature space induced by a kernel on the data in client Cps Letting C [C)....y Cp]. we solve the following distributed optimization problem
P.
minimize F(Z,C) & Σ upfp(Z,Cp)
2, C
In (7) fo is a local objective function for client cp and W1, , wp are nonnegative weights for the clients. In this work, we let
fp = o((xp) - CZ)) + A I1c.p12 2
(8)
Tr(K(X x,)) TT(C, x,)) +TC, |
where À > is penalty parameter. To guarantee the privacy of information, problem shall be solved in the framework of federated learning.
2.2 FedSC by Similarity Reconstruction and Model Averaging
In this section, we develop a FedSC algorithm by similarity reconstruction and model averaging. As a classic and popular framework, FederatedAveraging (or FedAvg) is first introduced in [McMahan er al. (017) for federated learning. our work, the proposed FedSC is, therefore, built up based on the backbone of FedAvg as in Figure FedSC consists of two stages. The first stage, shown by the left plot of Figure is federated similarity reconstruction, which constructs similarity matrix in the manner of federated learning. The second stage, shown by the left plot of Figure [ is using the reconstructed similarity matrix to implement spectral clustering.
Stage Federated Similarity Reconstruction
Step D: As the startup settings for our algorithm, the shared variable Z (i.e., the dictionary matrix Z) and each local coefficient matrix Cp for p 1.2. ... are initialized randomly the central server and each client, respectively.
Note that do not show the data X, in the objective explicitly since it is absorbed into fp.
3

---

Aggregation Module for Shared Variable
Spectral Clustering Module
Σ pt.t
2
2g
0
D3 @
(25,6
Server
Zi
7
2
2-1
(4f.c))
(22.0))
y2
(f),
yF
Client
Client
Client
Client
Client
Client
(zf.cf)
2 (2g,c))
2
(Z2.C)
Local Update Module
Information Flow of Federated Speciral Clustering:
p = argmin/ (2 cp) 4p
Special Clasooiss
FedKMil
2 argminf (2.,. CT)
Figure 1: Diagram of the proposed FedSC. Stage (left plot): Federated Similarity Reconstruction
(Steps 1-5). Stage (right plot): Spectral Clustering (Steps 6-8).
Step 2) For each round 8, where 1 S s S S, the previous shared variable Z will firstly be broadcast to each participated client. After that, every client uses this received dictionary matrix to run its own iterative updates of local variables in the Local Update Module (LUM)
1 |(((x)) 6( OC 2
C arg min fz Cp) arg min C
C
C
arg min Zp C2) arg arg min & | - (Zz)); >
|
(10)
Zp
2
Step 3: Each client sends back its own dictionary matrix Z = 2,,..... . P. to the central server.
Step 4 The central server collects all (or a subset A of) these uploaded matrices {Z;)p= averages them into matrix Z in Aggregation Module (AM), i.e.,
P and
Z A
Σ Z
(11)
PEA--1
where i is the number of participated clients. our study, we the number of participating clients for each round Therefore, we use the notation P instead of |A*-1| in the sequel. This
aggregated dictionary matrix 2a will then be used to push the next round of federated iteration until the tolerance condition is broken.
Step 5) When Stage I comes an end, the spectral clustering will start.
Stage II Spectral Clustering
Step O: Each client sends
back ".S) back to the central server for the final aggregation of information.
Step D: The required similarity matrix is then constructed based on the obtained dictionary matrix
8 and coefficient matrix S in Spectral Clustering Module (SCM). Based this approximated similarity matrix, the standard spectral clustering is implemented as usual:
y SpectralClustering C (Z,
(12)
Step X The central server broadcasts its clustering results to every corresponding client.

---

2.3 Optimization Algorithm for Federated Similarity Reconstruction
As described the above section, altemnae updating of local variables is key solving the proposed FedSC problem. In the following two parts, we discuss the optimization for Z and C, respectively.
For client Cp. consider the corresponding local optimization problem
minimize fp C) Z,C
(13)
where (2, || (Z)) + |C| TT X,)) -TC
TTT(C= K[, + one-step update for C:
| Let the derivative of [pl (z C) w.r.t. C be zero, we get the following
6 (K( (Z" Z Zz -La) " Xp), p p-1.2.... P.
(14)
The derivative of (2, C) w.r.t. Z is
0C = σ² Xx W2 - ZW2) + σ²
IQz -ZQ2),
(15)
0z
where the intermediate variables are detailed as
Wz 2 = C o 10 X. 2
W2 = diag 1 W
Qz (0.5CC") Z)
Qz diag 1 Q2).
Here 1, and 1a are the column vectors with all elements of 1. Because of the kernel function. Z cannot be updated like Cp. Here, we use the gradient method to update At local iteration f, by setting Z Z the update scheme of Z is
052 (Zzz oz
z -.--1
Te
(16)
where T/+ the step size and can be set as the reverse of the Lipschitz constant of gradient if possible. We summarize the optimization details Algorithm (shown in Appendix A).
2.4 Convergence Analysis of The Proposed Algorithm
First of all, it is obvious that all local objective functions fp(:.)) for 1...., P are lower bounded. To analyze the convergence of Algorithm []]
we make two assumptions. The first one is the Lipschitz continuity of the gradient of the local objective functions.
Assumption 2.1. The gradients of all local objective functions fp(:-) for p 1,..., Liz-- Lipschitz continuous in Z. that
2 (Z C₁) Vzl, 11 F. S L.Z, Z 2-,t-111 11
(17)
In addition, there exist some lower and upper bounds for I.z,, i.e, 0 < Lz S L22 S Lz hold for all y 1,... P and 1, S. S.
The second assumption, similar to (Li et al. 2019 Lian et al. 2017 is follows. Assumption 2.2. The difference between the local gradient and the global gradient is bounded as 2 W2lp(Z,C) Cp) FzF(Z, I) Sc
Vp= l,..,.... P.
(18)
To build the convergence condition, we define the following iterative terms of a and C for all t 1...., Q and = I....,.: S:
Wp C -Cp- 1 112
(19)
Tz C²) Z 2 11
where the instantancous average zd defined as
(20)
PEA-
Based on the above assumptions, provide the following convergence guarantce for Algorithm
5

---

Theorem 2.3 (Convergence of Algorithm D. Suppose Assumption 2.1 and Assumption 2.2 S(1 + Q) be the total number of global and local rounds. Then the sequence (Z ,C") generated by Algorithm with stepsize 1 L/22 and wp = satisfies
2.2 hold. Let
9
S ΣΣ
D - T 11
16 PLz
TZ 00 C²) +
Tz (Z c*)
-
(21)
T
==1
where v = 1+
(119)Q--)(20-1) --41Q-1)(0++2/133
and D
2 Imen
+x + 4
The proof can be found in Appendix E We that when T + oo, the algorithm converges to finite value, which is small if Ç is small and Lg is close to Lz.
3 Security-Enhancee FedSC
In order to enhance the security of FedSC, we present two noise-augmented variants of the proposed algorithm in this section.
3.1 FedSC with Perturbed Data
We add random noise to the data each client and then perform Algorithm to reconstruct similarity matrix, which further improves the privacy of data. Specifically, the data X E mR is perturbed by noise matrix E Rm*xn to form the noisy data matrix
x E,
(22)
where Ei ~ ~N(0,03 o²). We then perform Algorithm with Gaussian kernel of parameter on X and obtain Z, = [C1, C2. Cpl. and
K C²K,
(23)
We have the following reconstruction (for the true similarity matrix KEN = 1- error bound Theorem 3.1 (Error bound of similarity matrix reconstruction). Suppose |X|,, = A, ||
TC, and 0 Z)C - x(X) S where 0, Tc, and ry are some nonnegative constants. Then with
2,00
the probability at least 1 - n(n - 1)e- the reconstructed similarity matrix Kas satisfies
KKB
K2r
S ,2 [ v29)² -20²] + +(Vdrc + 1y
(24)
where { = -=VV/ (m + 2/mm + 26).
Note that r is the hyperparameter of the Gaussian kernel. In our experiment, r' was automatically estimated as the mean all pairwise distances between data points, i.e., = Ex, ||, 2z 1|2- Assume FiE xzbal = (E)) for all i,j E [n]. k E [m], then ||æ;; - æ,, = O( which means ,22 is linear with m Thus, the reconstruction error |K K Kox is upper bounded by 0 Vidycc), where 22/0² can be regarded as signal-noise ratio. Therefore, the bound is useful. In general, Theorem 3. indicates that when the added noise small and the optimization makes 7 small, the reconstruction error for the true similarity matrix is less than small constant with high probability. This verified the effectiveness of our similarity reconstruction method.
should be pointed out that K2 is not guarantced to be a sparse matrix and hence the corresponding graph may not contain multiple connected components. We therefore operation to get sparse similarity matrix, which may also reduce the computational cost of eigenvalue decomposition when is very large. Specifically, we let
extra KNN-basel
K s = gulSprseMatrixyyXNNNR... k)
(25)
'We defer the proof for all theoretical results to the supplementary material.

---

which only keeps the largest & connections from each point to other points. Finally, we perform spectral clustering using Kag. The central server broadcasts the clustering results to each participating client.
As mentioned before, one can choose to inject some noise into its raw data to avoid privacy leakage. However, a question is how much noise we can add to the data the largest extent for the guarantee of correct clustering. We first present the following definitions.
Definition 3.2 (Local neighbor set), Suppose D; and æ; are data points of X E R with class labels L, and L, respectively, and let (N;( be the of the k-nearest neighbors of zG. We define
N initrr == (æ, E X|L; L, and 2, E (NN())))
(26)
Definition 3.3 (Global neighbor set). Suppose and z are data points of X E R=x" with class labels L, and Ly respectively. and let KNN(x;) be the point set of k-nearest neighbors of æz. We define
Noiglobal (xz E X X KNN(x:)).
(27)
If we call the local neighbor of data point the intra-class neighbor of æ;, another definition called inter-class neighbor of x can further introduced as follows.
Definition 3.4 (Inter-class neighbor set). Suppose æ; and a, are data points of data matrix Rmxa with class labels, La and L,j, respectively, and let KNN(æ;) be the point set of k-nearest
neighbors of a.. We define
N Niiinter {3; X X + T.g and x KNN():))
(28)
Based on the above definitions, the following definition is presented to determine whether a data point can be correctly clustered or not.
Definition 3.5 (Correct clustering). Suppose 2; R" and zy E R are data points of data matrix X E Rm 2;; is said to be correctly clustered with tolerance of e if
a. Kg max; (iinter) e for any of æj E N in
b. Kij ming Kintra) + for any of æ N Nicintte
Based on Definition 3.5
the following theorem gives the guarantee of our security-enhance FedSC.
Theorem 3.6 (Guarantee of noisy spectral clustering). Let B(o) 3/2 [(oE + /20)² - (Vdro + 1)y, Then with the probability of at least 1 n(n 1)e performing spectral clustering using Kiz yields correct clustering results if
B(a)
max
max Kinter) min( K innrr
(9
2
where
Kinter ik
=KKr vinter and K intrr
(Kr vintra like
ik
Based on Theorem 3.1 and Theorem 3.6 we can get bound on the variance of noise for FedSC with perturbed data:
2 B2) + 20
V20
(30)
where B, max; 4 indicates that the intensity of noise should not be too strong otherwise it may seriously affect the performance of federated spectral clustering. But, at least under this bound, one choose to inject as much noise as possible into the raw data to ensure data security and privacy.
1 [max (K Kinter)- ming Kintre]] and B, / + 1)y. This bound ik
Using Theorem 3.22 in [woork et al. 2014) and the post-processing property of differential privacy, we have the following privacy guarantee for this enhanced FedSC algorithm.
Proposition 3.7. FedSC with perturbed data given by (e, 3)difffrrenttllll private if 2 2CTx /s, where e² 2 ln1.220/)).
7

---

Based on this proposition and (30 we obtain the following privacy-utility trade-off:
2 2 1.25/ <os Vr B2) 202 V20
(31)
This ensures both clustering performance and (e, ddfiferrent privacy. In particular, if we substitute with the upper bound, can get a strong level of privacy but the worst utility. By the way, B₁ B2 is related to the property of the data. A larger B1 Bg means a better property for clustering, which further provides larger upper bound for the noise level o, yielding a stronger privacy guarantee.
3.2 FedSC with Perturbed Factors
In FedSC with perturbed factor, we added Gaussian noise to in every round of the optimization but added Gaussian noise to in the last round of the optimization. To more specific, C C + Ec. and 7 = Z + Ez, where the entries of Ec and Ez are drawn from (0, oz) and AV o3)) respectively. Then perform spectral clustering using the following reconstructed kernel matrix:
K2 Č ((,2))C
(32)
The following theorem shows the reconstruction error bound for the ground truth kernel matrix K Theorem 3.8. Assume [Øx (XX)l2,,
S % ||C||2, S Tc. Then with probability at least
1 (n + d)e=* it holds that
Rez
K
S Szo(72a + 2)
(33)
where 720 720 + vi (oola
ooCa toy + (1-
exp
+3 2"
and 3 2v 2t.
We see that, given fixed y, the reconstruction error becomes smaller if az and og are smaller. Based on Theorem 3.8and and Definitions 3.2-3.5, we can obtain a bound similar to that in Theorem 3.6 to guarantee correct clustering, which will not be detailed here.
Theorem 3.9. FedSC, assume (ax (llt,, l b || S tx. max () ||=; xحا1o T. P IZ 8p I rz Va, and 112,0 S Tc, we perturb {2;) p= Vs = 1,2,...,
......., S with noise drawn from N(O, o with the parameter oz 2 V(85A> (gz) log(e + (Ez/02))/E2) where Aggz) 2VdreTxn
(TX + T2) (Tx+T) and perturb {C 1p=1 with noise drawn from (N oZ) with the parameter ac 2 2cA-1 Vd-iidrx(rT + T)/((2Ec) for e² > 211(1.25/8c). Then, FedSC is (EC + + + (afdz)d)dfeenttaall private.
Theorem 3.9 shows that our FedSC with perturbed factors can protect the data privacy provided that the noises added C' and Z are sufficiently large. Similarly (3I). we can also get a privacy-utility trade-off using Theorem 3.8 and Theorem 3.9 which is detailed in Appendix B
Related Work
should be pointed out that the study on federated spectral clustering in literature is very limited. Besides our work, the only work that aims to address the problem is [Hernández-Prren et al, 2021] More introduction and discussion about the related work (federated matrix factorization//lusteer
(Yang et al. 2021 Ghosh et al. 2020; Dennis et af.) 2021] Wang and Chang 2022] and spectral
clustering Von Luxburg 2007 Jeemandez--eeedee et al. 2021] are in the supplementary material.
Experiments
5.1 Performance on similarity reconstruction
Taking the COIL20 dataset [Nene et al. 1996) as an example, we first obtain the similarity matrix from vanilla spectral clustering based on the same kernel function. Then, we use the proposed method to derive the estimated similarity matrix K&g which is actually approximation of ground truth. To

---

make it clearer, we also give the corresponding sparse similarity matrices by KNN sparsification (25). shows the similarity matrices constructed by different methods. We see that the proposed method can be able to successfully reconstruct the similarity matrix in the federated scenarios. The reconstruction errors on synthetic data, iris, banknote authentication, and COIL20 are in the supplementary material.
5.2 Clustering performance of FedSC
In this subsection, check the clustering performance of the proposed security- -enrrty- FedSC method on both synthetic and real-world datasets. The synthetic dataset is generated from concentric circles. The details are in the supplementary. This synthetic dataset is visualized in Figure (3a] Here,
we continue to adopt the aforementioned 20 as an example of real-world datasets.
Taking the synthetic dataset first group of cases helps illustrate the effective- ness of the proposed FedSC method. we first apply the vanilla spectral clustering method to the clean data. The predictive result is shown in Figure 3(b] It is clear that the vanilla spec- tral clustering method correctly clusters the data points lying in concentric circles. We then use the proposed FedSC method to cluster the data. One can find in Figure [3c] that almost all of the data points also have been grouped correctly. However, when we inject some volume of noise
example, the
(a)
(d)
Figure 2: Visualization of similarity matrices: (a) similarity matrix of vanilla spectral clustering; (b) approximated similarity matrix of the proposed method; (c) the corresponding sparse similarity matrices generated by KNN sparsification.
5
5
0
-5
-5
0
5
-5
-5
0
5
(a) Ground truth
(b) Vanilla SC
(c) FedSC
5
-5
-5
-5
-5
(d) Noisy data
Vanilla SC
FedSC
Figure 3: FedSC on concentric circles: (a) ground truth; (b) cluster assignment generated by vanilla SC; (c) cluster assignment generated by FedSC; (d) Noisy ground truth; (e) cluster assignment generated by vanilla SC on noisy data; cluster assignment generated by FedSC on noisy data.
into the raw data, things may change lot. Figure 3(d is actually the ground truth Figure 3(a) adding some Gaussian noise. When focusing on this noisy data of concentric circles, we see from Figure B(c) that the vanilla SC failed cluster the data points while the proposed FedSC method is still able to correctly cluster the data to some extent as in Figure 3(f) As we know, the similarity graph directly constructed from raw data could be very sensitive each data point. When we add too much noise, the similarity graph may fail to model the local neighborhood relationships which may be the reason why data points in Figure 3(e) are not separable for vanilla SC. Instead, FedSC based on matrix factorization in the high-dimensional feature space and has a potential denoising effect. Therefore, it possible for our method achieve better performance. The visualization of COIL.20 can be found in the supplementary material.

---

5.3 Comparison with baselines
We compare our method with the clustering method DSC proposed by [Hernández- Pereenn et al. 2021]. Because the existing literature on federated spectral clustering is rare, we here select both classic K-means and spectral clustering as the baselines. Two metries including accuracy and NMI are adopted to evaluate the clustering results on four datasets including iris (Dua and Grafi 2017).
COIL.20 [Nene el al. 1996], banknote authentication [Dua and Grafi 2017), and USPS (Hull 1994]. The details are in the supplementary material. Besides the clean data, we also consider adding noise to them to test the performance of methods under the condition of privacy protection. We directly
inject Gaussian noise with zero mean and variance o² to the raw matrix X E IR=x as X = X where E is Gaussian noise matrix, each element Ei of which is i...d. with oO)
Table | shows the clustering accuracy. Our FedSC almost always achieves comparable clustering results to vanilla SC. It even outperformed vanilla SC in some cases and K- K-means in most cases since FedSC has a potential denoising effect by approximating similarity matrix. More importantly FedSC significantly outperformed DSC in almost all cases. The reason is that DSC performs spectral clustering on each local dataset, which may lead to very unstable and inaccurate results.
Table 1: Comparison of clustering accuracy (X and X denote the data and corrupted data respectively). The results of NMI are in Section D.4
Kmeans
SC
DSC
FedSC
Iris
0.8933 + 0.0000
0.9000 + 0.0000
0.5480 + 0.0679
0.9000 + 0.0031
201120
0.6113 + 0.0534
0.8025 + 0.0009
0.1009 + 0.0100
0.7828 + 0.0231
X
Bank
0.6122 1 0.0000
0.5918 1 0.0000
0.5582 + 0.0045
0.7672 + 0.1457
USPS
0.6704 +: 0.0047
0.6635 1 0.0000
0.1686 + 0.0014
0.6596 + 0.0021
ORL
0.6325 1 0.0270
0.7865 1 0.0106
0.1653 1 0.0073
0.7235 1 0.0170
Iris
0.89-10 1: 0.0152
0.9120 1 0.0332
0.4533 1 0.0658
0.8993 1 0.0299
COIL20
0.6283 + 0.0484
0.8024 1 0.0020
0.0995 + 0.0122
0.7790 + 0.0213
X with 0.1c
Bank
0.6067 1 0.0022
0.6067 1: 0.0944
0.5558 + O. 0.0023
0.7168 1 0.1068
USPS
0.6732 = 0.0035
0.6647 + 0.0016
0.1690 O. 0.0007
0.6643 = 0.0022
ORL
0.6195 = 0.0329
0,7810 + 0.0065
0.1600 = 0.0089
0.7323 = 0.0250
Iris
0.8420 + 0.0274
0.8327 + 0.0267
0.4533 + 0.0674
0.8127 1 0.0404
COIL20
0.6422 = 0.0366
0.7997 + 0.0029
0.0981 = 0.0084
0.7793 = 0.0240
X with 0.3a
Bank
0.6020 = 0.0038
0.5859 + 0.0105
0.5588 = 0.0074
0.6046 = 0.0064
USPS
0.6704 = 0.0063
0.6720 + 0. 0.0044
0. = 0.0019
0.6884 = 0.0509
ORL
0.6098 = 0.0167
0.7885 + 0.0047
0.1665 + 0.0057
0.7417 + 0.0280
Iris
0.7740 = 0.0252
0.7313 + 0.0494
0.3833 = 0.0204
0.7540 + 0.0336
COIL20
0.6389 = 0.0296
0.7950 + 0.0080
0.1033 = 0.0167
0.7403 + 0.0294
X with 0.5g
Bank
0.6051 = 0.0076
0.5923 1 0.0094
0.5566 + 0.0030
0.6086 + 0.0073
USPS
0.6699 + 0.0031
0.7843 + 0.0030
0.1683 + 0.0017
0.7778 + 0.0062
ORL
0.5983 + 0.0295
0.7930 + 0.0172
0.1615 + 0.0096
0.7107 + 0.0345
Iris
0.6500 1 0.0420
0.6087 1 0.0468
0.3927 1 0.0349
0.6120 0.0455
C0IL20
0.6220 = 0.0627
0.7662 + 0.0172
0.0893 + 0.0055
0.6803 + 0.0198
X with 0.7a
Bank
0.6100 + 0.0112
0.6046 + 0.0144
0.5566 + 0.0035
0.6106 + 0.0107
USPS
0.6638 + 0.0044
0.7747 + 0.0040
0.1675
+ 0.0004
0.7587 = 0.0117
ORL
0.5723 + 0.0360
0.7860 + 0.0093
0.1613 1 0.0066
0.6910 1 0.0232
5.4
More numerical result
The (SNE visualization, clustering results in terms of NMI, the performance of FedSC with perturbed factors, etc, are in the supplementary material.
6 Conclusion
This paper has proposed a secure kernelized factorization method for federated spectral clustering on distributed data. We provide theoretical guarantees for optimization convergence, correct clustering, and differential privacy. The numerical experiments on synthetic and real image datasets verified the effectiveness of our method. To the best knowledge of the authors, this is the work that successfully addresses the problem of federated spectral clustering. One limitation of this work is that we haven't 't tested our FedSC on very large datasets, though the moderate-size datasets are sufficient to justify the effectiveness of our FedSC. Note that for large-scale datasets, the bottleneck of clustering the eigenvalue decomposition of the Laplacian matrix, not our FedSC algorithm.
10

---

Acknowledgments
This work was partially supported by the Youth program 62106211 of the National Natural Science Foundation of China, the General Program (CYJ202203324100208000 of Shenzhen Fundamental Research, the research funding 202100000 of Shenzhen Research Institute of Big Data, the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence, and the funding UDF01001770 770 of The Chinese University of Hong Kong, Shenzhen.
References
Jinyu Cai, Jicong Fan, Wenzhong Guo, Shiping Wang, Yunhe Zhang, and Zhao Zhang. Efficient deep embedded subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1-10, June 2022.
Yi-Ruei Chen, Amir Rezapour, and Wen-Guey Tzeng. Privacy-presern ridge regression on distributed data. Information Sciences, 451:34 49, 2018.
Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. In International Conference on Machine Learning, pages
PMLR, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ Theoretical Computer Science, 9(3-4):2 407, 2014.
Jicong Fan and Tommy W.S. Chow. Sparse subspace clustering for data with missing entries and high-rank matrix completion. Neural Networks, 93:36-44, 2017.
Jicong Fan and Madeleine Udell. Online high rank matrix completion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Jicong Fan, Zhaoyang Tian, Mingbo Zhao, and Tommy W.S. Chow. Accelerated low-rank repre- sentation for subspace clustering and semi-supervised classification on large-scale data. Neural Networks, 100:39-48, 2018.
Jicong Fan, Chengrun Yang, and Madeleine Udell. Robust non-linear matrix factorization for dictionary learning, denoising, and clustering. IEEE Transactions on Signal Processing, 69:1755- 1770, 2021.
Jicong Fan, Yiheng Tu, Zhao Zhang, Mingbo Zhao, and Haijun Zhang, simple approach to automated spectral clustering. In Advances in Neural Information Processing Systems, volume 35, pages 9907-9921. Curran Associates, Inc., 2022.
Jicong Fan. Large-scale subspace clustering via k-factorization. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, page 342-352 New York, NY, USA, 2021. Association for Computing Machinery.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586- 19597, 2020.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. Advances in Neural Information Processing Systems, 33: 14068- 14080, 2020.
Elena Hernández-PPeree Oscar Fontenla-Romero, Bertha Guijarro-Berdine and Beatriz Pérez- Sánchez. Federated learning approach for spectral clustering. In ESANN, 2021.
Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence, 16(5):550-554, 1994.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference machine learning, pages 1376-1386 1385. PMLR, 2015.

---

Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-210, 2021.
Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong-Lyun Kim. On-device federated learning via blockchain and its latency analysis. arXiv preprint arXIv:1808.03949, 2018.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint (00i:09907.02/89 2019.
Li Li Yuxi Fan, Mike Tse, and Kuo-Yi Yi Lin. A review of applications in federated learning. Computers & Industrial Engineering, 149:106854, 2020.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEK Signal Processing Magazine, 37(3):50 60, 2020.
Zitao Li, Bolin Ding, Ce Zhang, Ninghui Li, and Jingren Zhou. Federated matrix factorization with privacy guarantee. Proceedings of the VLDB Endowment, 15(4):900-9)) 913, 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efiicenn learning of deep networks from decentralized data. In Artificial intelli- gence and statisticy, pages 1273-1282. PMLR, 2017.
SA Nene, SK Nayar, and H Murase. Columbia university image library (coil-20). Technical Report CUCS-005-96, 1996.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001.
Efthymios Tzinis, Jonah Casebeer, Zhepei Wang, and Paris Smaragdis. Separate but together: Unsupervised federated learning for speech enhancement from non-iid data. In 2021 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA), pages 46-50. IEEE, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416 2007.
Shuai Wang and Tsung-Hue Hui Chang. Federated matrix factorization: Algorithm design and application to data clustering. IEEE Transactions on Signal Processing, 70: 70:1625-1640, 2022.
Hongtao Wang, Ang Li, Bolin Shen, Yuyan Sun, and Hongmei Wang. Federated multi-view spectral clustering. IEEE Access, 2002299900 2020.
Timothy Yang. Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: pet::::92.000 2018
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Enyue Yang, Yunfeng Huang, Feng Liang, Weike Pan, and Zhong Ming. Femf: Federated collec- tive matrix factorization for heterogeneous collaborative filtering. Knowledge-Bund Basse Systems, 220: 106946, 2021.
12

---

Fengda Zhang, Kun Kuang, Zhaoyang You, Tao Shen. Jun Xiao, Yin Zhang, Chao Wu, Yuet- ing Zhuang. and Xiaolin Li. Federated unsupervised representation learning. arXiv preprint arXiv:2010.08982, 2020.
Weiming Zhuang, Xin Gan, Yonggang Wen, Shuai Zhang, and Shuai Yi. Collaborative unsuper- vised visual representation learning from decentralized data. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages
2021.
13

---

A Framework of the Proposed Algorithm
In the beginning, Z and C for p = 2....... P are initialized randomly in the central server and clients, respectively. Then, Z is broadcast to every participating client and helps do the alternate updating of Zp and Cp based on the update schemes (T6) and (4). Afterward, the obtained matrix Zp is sent back to the central server and aggregated for the next round of training. When the tolerance condition is broken, both Z and C are sent back the central server for the subsequent clustering task.
Algorithm 1 Proposed Federated Similarity Reconstruction
Input: Distributed data {Xp. p E == 21,2.... P} clients weights {up : p E P}.
1: Initialize Z" server side and {Cp pppp=1 client sides.
2: Randomly choose AA C P with | P.
3: for round 1 to S do
4: Server side: compute - = EpEA-- Zz-
5: Broadcast z to clients Cp. E A"
6: Client side:
7:
for client p 1 to P in parallel do
8:
set =0 --
9:
update local variable C.
10:
C (AC(Z Zz.0) + AL2) XK
11:
update local variable Z
12:
for /. Q do
13:
p = 2 end for
7/ V 2 (Z
15:
denote z = Z
16:
if client p E - then
upload Z to the server
18:
end if end for
19:
20:
Randomly choose A Ç P with [A*]= P.
21:
end for
Output: Z, CpC 1,2....,
B More theoretical results about FedSC with perturbed factors
Based on Theorem 3.8 and Theorem
3.6 we can get a bound on the variance of noise for FedSC with
perturbed factors:
( -1 B
(34)
where Bi in Theorem 3.8 and clearly non-decreasing function with respect to az and ac, respectively. Therefore, it is a valid upper bound on both σz and ac-
max; 7 [max K Kiiner) ming ]intrra] and Tzelaz, ) is exactly the 7ac i6
Proof. By Theorems
3.8 and 3,6
we have
1ze (To + +2) < Bi
(35)
That is, we need solve a quadratic equation 7 2Tzc Bi 0 with both Tec 2 and B 2 Since the discriminant A 4B, 2 0, we have two roots - + 2 B, for this equation. Thus, it has 0 & Tze < -1 2 B, as desired.
This bound indicates that the intensity of noise should not be too strong otherwise it may seriously affect the performance of federated spectral clustering. But, at least under this bound, one can choose to inject as much noise as possible into the raw data to ensure data security and privacy.
14

---

Based on Theorem 3.9 and 34
we obtain the following privacy- utility trade-off:
Yzc 7zol 0z, 0c) < -1 =1
Bi
o% 2 / (85A log(e + (ez/6zz))ez
(36)
2 2cx 2e1 Vdrx + T)/(r=sc)
This ensures both clustering performance and (e, diffeerreel privacy. In partieular, if we increase the intensity of either oz or de to reach the upper bound of Yze. we can get a strong level of privacy but the worst utility. By the way, B₁ is related to the property of the data. larger B₁ means better property for clustering, which further provides a larger upper bound for the noise level, yielding a stronger privacy guarantee.
C More discussion on the privacy-utility trade-off of FedSC
Although theoretical results are presented in our study to ensure the security of FedSC, we still provide here some insight into methods of using Secure Aggregation other cryptographic techniques to handle pair-wise client functions (i.e., kernel function in our study). Even though the communication cost will be high, it might be alternative to reduce the DP noise levels. Specifically, it can be performed as follows.
Step 1: ZØ is posted to the central server;
Step 2: Central server aggregates z to get the global z
Step 3: Central server computes Kzz = K(ZS z and broadcast it to clients;
Step 4: For client and c E Cp.
E Cp. then client directly calculate K,j = c,Kzzeji if Cj E Cpr, then client firstly encrypts and transfers its G to client p', and then client p' also encrypts its Cy and use the cipher text to compute enc(Ke,)) = enc(ce) )eno(Kez) )enc(e)));;; Client p' transfers the result enc(Kig)) back to client p; Client p decrypts enc(Kii) to get Kaj.
Step 5: Each client p sends its estimated results K.y back to the central server without sending its own Cp;
Step Central Server checks whether these posted results from clients are compatible with each other in case of injection attacks and then performs spectral clustering.
This alternative does not send clients' C' the central server and gives an extra cross-validation process in the central server which may be useful to enhance security.
D More details and results of the experiments
should be pointed out that in Table 2 of the main paper, the signal-noise ratio is high as 12dB, which means the noise is tiny. The parameter d in our FedSC was automatically determined and has much larger value than that in the noiseless case. That is why the performance of FedSC in the noisy case is even better than that in the noiseless case of some datasets. In this appendix, we increase the noise level (a. = So, where a denotes the standard deviation of the clean data) and consider one more real dataset.
D.1 Dataset description
Synthetic data The synthetic data is generated from concentric circles. For 0 [0,2m]] i 1, 1. 1258, all the points of this synthetic dataset X E 22x1258 are generated by
Ia cos + en1 x2: (0:)) e:2
x; (x)
(37)
where 0p = 0. 01258 = 2n, and the remaining 0, are evenly spaced points between Og and 01258- The additive noise and are drawn from (0, o2). We let o. = 0.1az, where denotes the standard deviation of the data without the additive noise e. our experiment, we set hyperparameter r in (37) to 2 and 4.
15

---

-5
-5
-5
5
-5
5
(a)
(b)
Figure 4: Synthetic dataset of 2 concentric circles: (a) ground truth; (b) noisy data perturbed by Gaussian noise with mean and standard deviation 0.2std(X).
Real-world data Both iris and banknote authentication are from the UCI machine learning library. COIL20 is an image dataset from Columbia Imaging and Vision Laboratory. USPS a dataset for handwritten text recognition research. The details of the mentioned datasets shown in Table 2
Table 2: Summary of four real-world datasets
# of clusters
of attributes
# of instances
Iris
3
4
150
COIL20
20
20x20
1440
Bank
2
5
1372
USPS
10
16x
9298
ORL
40
92x112
400
The visualizations (by t-SNE
Van der Maaten and Hinton
2008 of three real-world datasets
shown in Figure 5
-20
1000
-100
-00
50
(a) Iris
(b) COIL20
(c) USPS
Figure 5: t-SNE visualization of some real-world datasets
D.2 Evaluation metrics
We use two metrics to evaluate the clustering performance of our method: accuracy and normalized mutual information (NMI). Between them, accuracy is affected by the misclassification rate of cluster assignment. The smaller the misclassification rate, the greater the accuracy. In this study, given data matrix X pmxn with sample points of m features, let L; and Lr; for i 1,2,...,?? be the true labels and predictive labels, respectively, the accuracy of predictive cluster assignment Ir is computed
1
accuracy - card (i]L; = Lri, i = 1, n.)).
(38)
NMI is normalized version of mutual information that measures the agreement of two cluster assignments without considering their permutations.
2T(1; Lr)
NMI H(L) + H(Lr)
(39)
16

---

where [LL; Lr) is the mutual information between L and Lr, and H (L) and (Lr) are the entropy of L and Lr, respectively.
D.3 Parameter settings
In our experiments, we set some hyperparameters including Ac, d, and k for implementing the proposed FedSC. Among them, Ào as the penalty parameter of the regularization term is set to le -2 2. & is the hyperparameter of the KNN-based operation on the similarity matrix. We set k to the remaining
max(ceil (log(()) 1) based [Von Luxburg 2007 two parameters are as follows.
The details of methods
Setting of hyparameter function. Due to the distinct characteristics of the datasets, we adopt the following adaptive method determine the value r::
The hyperparameter r controls the smoothness of Gaussian kernel
Mean (Re(v D))
(40)
where c and D the distance matrix of data points, of which its element
Dij
x. x 12: for j.j 1.2....... ....,... n.
(41)
In reality, the global D cannot be obtained because FedSC does not allow data transmission. Then we compute Dp for each client Cp, I,..., P and then determine r as follows
Meel (D)))
(42)
P
where can be tuned.
Setting of hyparameter d The hyperparameter d controls the complexity of the approximation Φ(X) ((Z)C. We adaptively determine the value of d for each dataset:
= inf KEN
Σ
tol for & S }
(43)
where 8; denotes the i-th largest eigenvalue the kernel matrix K i = 1,....n. set the threshold tol to 0.99.
n. In our experiment,
worth noting that we use the same r in the vanilla SC and our FedSC for fair comparison, though D cannot be obtained in our FedSC. In addition, the setting of d relies on K that is also not obtainable our FedSC. We use this setting for convenience and in reality we need to determine d by other methods such as letting d ymm, where y is hyperparameter.
D.4 Clustering results
NMI results The average results of 10 repeated trials are reported in Table (ACC) and Table (NMI). Note that for the USPS dataset, only 5 trials are performed to save time due to its large number of sample points. We see that our FedSC outperformed Kmeans and DSC significantly in almost all cases and has at least comparable performance SC in most cases.
Inffuence of d The clustering accuracies with different are reported in Table
Results of FedSC with perturbed factors The results on COIL20 are reported in Table 5 where oz std Zp)) and ac (C"). Through this experiment, it can be observed that perturbing factors can have a more significant impact on the accuracy of clustering results than perturbing raw data. That is, perturbing factors more sensitive and can achieve specified level of differential privacy with weaker noise. Furthermore, it can be seen from Table 5 that the clustering performance more sensitive to oe than d2.
Malicious attack on C Due the kernel trick, the optimization problem is nonlinear and nonconvex. Hence, it is very difficult for potential attackers to recover the data X from the uploaded factors Z, C, especially when or Z, C are perturbed by noise. Nevertheless, the attacker may perform K-means the {C, } p=1 to obtain clustering results. However, we find that the clustering accuracy
17

---

Table 3: Comparison with existing clustering methods (NMI)
NMI
Kmeans
SC
DSC
FedSC
Iris
0.6356 = 0.0000
0.6647 = 0.0000
0.2516 = 0.0707
0,6708 = 0.0139
COIL20
0.7658 = 0.0143
0.8809 + 0.0006
0.1259 = 0.0225
0.8613 + 0.0144
Xo
Bank
0.1480 =
0.0000 0.0000
0.1228 = 0.0000
0.0122 0.0160
0.4901 0.3050
USPS
=6125=000002: 0.0026
0.8083 = 0.0000
1.0014
0.7972 0.0121
ORL
0.8343 = 0.0136
0.8980 + 0.0045
0.3970 0.0045
0.8525 - 0.0097
Iris
0.6267 + 0.0305
0.6878 + 0.0764
0.1458
+ 0.0794
0.6666 1 0.0600
COIL20
0.7721 + 0.0122
0.8805 + 0.0012
0.1214 + 0.0254
0.8529 + 0.0209
X, with 0.1o
Bank
0,1383 = 0.0039
0.1314 = 0.2010
0.0039 = 0.0081
0.3853 + 0.2390
USPS
0.6147 = 0.0022
0.8097 0.0016
0.0076 0.0010
0.7920 0.0133
ORL
0.8280 = 0.0153
0.8948 + 0.0019
0.3944 0.0074
0.8554 0.0104
Iris
0.5292 + 0.0528
0.5072 1 0.0442
0.1403 0.0792
0.5385 1 0.0594
COIL20
0.7745 + 0.0185
0.8767 + 0.0014
0.1174 #
0.8477 + 0.0188
X, with 0.3a
Bank
0.1327 0.0062
0.1031 0.0211
0.0253 0.0135
0.1489 - 0.0151
USPS
0.6112 0.0052
0.7927 + 0.0123
0.0070 = 0.0016
0.7837 = 0.0091
ORL
0.8136 = 0.0067
0.8974 = 0.0047
0.0069 0.3987
0.8578 - 0.0147
Iris
0.4316 + 0.0310
0.3912 0.0426
0.0710
0.0421
0.4046 + 0.0388
COIL20
0.7676 + 0.0148
0.8721 + 0.0061
0.1238 + 0.0286
0.8293 = 0.0168
X, with 0.5g
Bank
0.1408 = 0.0133
0.1189 0.0175
0.0059 = 0.0109
0.1521 = 0.0113
USPS
0.6088 + 0.0036
0.8049 + 0.0164
0.0059 : 0.0028
0.7951 = 0.0127
ORL
0.8058 + 0.0150
0.8970 0.0063
0.3977 0.0095
0.8381 + 0.0133
Iris
0.3025 + 0.0407
0.2755 + 0.0381
0.0715 #.0450
0.2773 1 0.0408
COIL20
0.7589 + 0.0234
0.8564 0.0141
0.0127 0.1032
0.7772 + 0.0196
Xn with 0.7o
Bank
0.1506 = 0.0208
0.1420 + 0.0262
0.0074
0.1577 = 0.0196
USPS
0.6007 = 0.0051
0.8004 0.0110
0.0042 = 0.0009
0.7636 = 0.0184
ORL
0.7877 = 0.0165
0.8944 = 0.0043
0.3946 0.0056
0.8236 = 0.0102
Table Accurcy of the proposed algorithm on COIL.2 (K 20)
d
7K
8K
9K
194 (SVD)
10K
11K
12K
Trial
0.7806
0.7882
0.7951
0.7944
0.7778
0.7979
0.7694
Trial
0.8035
0.7431
0.7819
0.8007
0.7812
0.8049
0.7792
Clean data
Trial
0.7562
0.7896
0.7569
0.8097
0.7708
0.7569
0.7764
Trial
0.7444
0.7771
0.7771
0.7889
0.7854
0.7903
0.7958
Trial 5
0.7965
0.7361
0.8014
0.7833
0.7632
0.7264
0.7694
Mean
0.7762
0.7668
0.7825
0.7954
0.7757
0.7753
0.7781
d
10K
20K
30K
749 (SVD)
40K
50K
60K
Trial
0.7708
0.7722
0.7764
0.8201
0.7000
0.7306
0.8139
Trial
0.7743
0.7889
0.7646
0.7882
0.7694
0.7451
0.7299
Noisy data
Trial
0.7375
0.7743
0.7167
0.7493
0.7792
0.7965
0.7299
Trial 4
0.7965
0.7688
0.8014
0.7736
0.7903
0.7382
0.7674
Trial 0.7493
0.7507
0.7576
0.7000
0.7792
0.8076
0.8194
Mean
0.7657
0.7710
0.7633
0.7662
0.7636
0.7636
0.7721
on C' lower than those of Kmeans, SC, and FedSC reported in Table [ For instance, the clustering accuracy on Iris is reported in Table.
Influence of P Table compares the clustering performance between using a single client (P 1) and using multiple ones (P= 8). clear that the operation of splitting data across multiple clients may lead to accuracy loss of clustering, which implies that method is valid.
More results on MNIST and CIFARIO We have already included datasets of high-dimensionnl images in Table | like USPS and COIL.0 with sizes 16 x 16 and 20 20, respectively. Nevertheless, further improve the experiment, we added the results of MNIST (28 28) and CIFAR1032 32)
in Table 8
18

---

Table 5: Clustering accuracy (average over 10 trials) of FedSC with perturbed factors on COIL20.
On
0.05
0.1
0.15
Std
Mcan=Std
Sca
Mta
0.7831
0.6273=0.0291
0.6012:50.0391
0.4835+00.0526
0.05
0.7824+0.0016
0.6573=0.0243
0.6165 0.0286
0.4998+=000567 0.64531000186 0.621910.0467
Ox3
0.1
0.7817#0.0299
0.6625=0.0258 0.6526=0.0258
0,5508
0.15
0.788110.0222
0.590110.0326
Table Clustering accuracy among different ways
Kmeans
SC
DSC
FedSC
Attack on C'
Iris
0.8920 + 0.0028
0.9000 + 0.0000
0.5493 + 0.1263 0.9027 + 0.0064
0.6360 + 0.1557
E Proof for theorem on the convergence of FedSC algorithm
We derive the objective descent with respect to C and Z respectively.
Objective descent with w.r.t. C:
Based the update scheme 14 of C, have
Vctp cp) = (K(Z zo.0 + AI K(Z x,) where 2 Z-
(44)
= - =p 25-1..
According to the proposed FedSC problem 7
we have
fz 00 C,) fp
(Z 00
C
/ |1((xx) ol Z
1
C
X
c
- -1
2 1
-- --rr(c,- - Ix- X,))
マタ TTC - -Cp
(Op-1)7)
+ - C (C,-) K(Z zoo))
(45)
=-T((C, - (x,-- z000)
Al))C
+2 + C 1 [K(2 2o,0 + ALa))
ThIC C.- 12 K(Z 0 z + Aa C.
T.1
I 2 (Tin + +1) [C Cp- ||
where Pinin = Mmin (K(Z 2z
Summing it up from p 1 to P. we have
F C*) - F(z , - + A) Σ up
C Cp-11
(46)
p=1
Objective descent with w.r.t. Z: According Assumption 2.1
implies
F C*) - F( - C²) AZF(Zz O²), Z 1
T22
(47)
Li
+
19

---

Table 7: Clustering accuracy between using a single client and using multiple clients
Iris
COIL20
Bank
ORL
P 0.9007 = 0.0086
0.8073 = 0.0089
0.7536 0.1271 0.6821 + 0.1405
0.7937 = 0.0084 0.7112 = 0.0258
P P 8
0.8993 = 0.0165
0.8003 = 0.0049
Table 8: Clustering accuracy on MNIST and CIFARIO
Kmeans
SC
DSC
FedSC
MNIST
0.5448 = 0.0257
0.6265 = 0.0439
0.1292 0.0144
0.6139 = 0.0464
X
CIFARIO
0.2171 + 0.0132
0.2182 + 0.0133
0.1235 = 0.0062
0.2134 0.0131
MNIST
0.5402 = 0.0225
0.5755 0.0366
0.1337 = 0.0191
0.5606 = 0.0457
X with 0.3o
CIFARIO
0.2209 0.0154
0.2198 + 0.0172
0.1194 = 0.0051
0.2187 = 0.0125
MNIST
0.5711 0.0555
0.0329
0.1340 = 0.0135
0.5029 + 0.0264
X with 0.7a
CIFARIO
0.2202 + 0.0147
0.2205 + 0.0084
0.1209 = 0.0045
0,2134 + 0.0152
Now, we give bound on T.2. Lemma E.1. For any and t, it holds that
(ZZF(Z=-1 C*), z - Z
201-111 -
(48)
+(VZF(Z'(t C0 -2
Proof. Based on the update schemes of Z, have
Z ==a== Z
Fz c
I
= 2,,-1
Σ V2fp(Zz ,.))
PT, PEAA
(49)
1 Σ
0= P
V2lp(Z, C (2 2z--1)
PEA
Then, consider the following terms
(V2F(Z C²), z Z
1 Σ Vzlp(Zz , 1z 2 z Z zzt-1)
=(V2F(Z-H-CC C*
P
DEAL
(50)
= =- 1- zztt - -2-111"
+ (Vzz(ZZ'11) -,0) P
Σ
Vefp(Zp p .C)),
Z 1001--z--1 201111)
PEA
Based on Lemma 1, we continue to do the following derivation.
F(Z C*) - F(221-111 C*)
L2 Z 1 112 112
<
2
1 Σ
+ (V2F(Z 1 1, ,0")
22f(lzp* ,C2), 2 - -2-m----- z((-l)
P
PEAA
L Z 11
(51)
4
1
VzF(Z*111 100) 1
Σ
VzfalZp c.:)
13
P
A
20

---

where we used the fact that (xx v) S || + ll Vc > 0.
Now, we give bound T.3.
Lemma E.2. For any and t, it holds that
C²) P
Σ
VefplZz cp)
PEA.
(52)
16 p + +2(1+ p)
8
Σ
up(Lz )² Z -p--111
F
Proof. For any and 1, it holds that
1 Σ VefplZz"" .
VzF(Z 00)) ,0))
P
PEA
Fz ,C Σ
wp 225p ( ,c,
p=1
Up V2Jp cp) p
Σ
V2lp(Zp-11 C
1=1
DEA
(53)
p Σ
2
2
7 FZ ,Ce)-
up V2 1-1 ,.))
p=1
+2
Wp (Z c
1 P
Σ
VzlolZz p .2))
PEd
T.5
where we used the fact that |Σ ail12 s n Σm= 11:112 Firstly, we give bound on T.4:
V F 2
Σ
up V (2 1-1 c..)
p=1
P
11 ,.,,]] Σ up [z] c. - V2l1121
(54)
P
Σ
Up VzF(Z ,,, V2 c3)1 F
1=1
P
Σ
up (T.2,) )²| 2 11
y=1
where we used the fact that Vzfí(, C2) is L2, Lipschitz continuous.
21

---

Secondly, we give bound on T.5:
P
Σ
wp
V
c.)
1 Σ
Velp(Z,''1 ,.)
p
PEA-
F
Σ
Σ
up W (z (
1-1 cCp)
p2
P'EA"
P=1
<>>
Σ
wp VziulZz
1 c4t)
(55)
P'EA"
1=1
ス up
Σ up V2 ,C) Jzlp(Zzz) (Z,-²1 c.,)
p=1
F
Σ
Wp'
Wp
Vzfp(Zp c
C - V 2 12 Φ
1-1 1ー
|
16
Thirdly, we give a bound on T.6:
V V F
(Z)'
..)) + V VzJp ,2))
V2F(Z (21 cc")
+ -C) cC)]
+ VZlv C5) V2/p (
(56)
+ V22 (Z (1 C.) - V2F(Z 4- (0)]
<4 V V2 C.) - V2 ,.
+4 V - - V -0002//(""-,00))
+4 V21 (.) - V21p 06)
+ (2 ,.))) - VzF(Z .C')
<4(L2, 1 z - || + 4(L22,)) )² z -Z,
2
+ +
Here, it the second time that we use the facts that | aill S n E |a:11
and that
Vzla(, C is -Lisschiz continuous.
Based on the bound of T.6, we derive the bound T.5.
22

---

Σ wp
12 (Zp cpt Σ
1 c.p)
DEAL
Σ
wpp
Σ
Wp
A(Li2,) z (
1r- + 1LL2,) )2
za
2 1|2 862
+
F
y==1
p=1
Bound of T.5
8
8
+
Σ
up
-Zp---111
P
p
(57)
Fourthly, based on the bounds of 7.4 and 7.5, we continue to derive the final required bound.
V 1ZF(Z 0²)
Σ
C
P
PEA"
Wp 12 )²2 2
1|?
+2
8C
8
Wp 222 2
p
p
P
p=1
Boand of T:3
Bound of T.4
16
8 p p up(L2,)
+ 2 +
Σ
P
20--111
(58)
Based on Lemma 2, we continue to do the following derivation.
Fl C*)
F(Z C*)
1
4
266²
+
+ +211+ + p
Σ
wpl (2,,)) )2 2
p=1
(59)
Bound of T.3
L
11 + 16
101--112
PL
2
8.
Σ wip (LZ,,)) )2 2 2
+
T,
p
Then, summing it up from / = 1 to Q yields
F C*) F(Zz. ,C)
L Q
16Q
2 --1-1 112 +
<
4
PL
t=1
(60)
Q
+
2
(1
+
8
Wpl
wp( L
Z
- 2
L3
t=1
T.7
Now, we give bound T.7.
23

---

Lemma E.3. For any it holds that
2
41.
Σ
(-1
(I2
|
2 +
812
(L2)
PL
(61)
j=0
41
Σ Σ
1-1 p
2r(L2,11
)3 z -3 |
222)
j=0p==1
Proof. Based on the update schemes of C' and Z, we have
Zzd
7
Vzlpp ( ,,,)
T.
(62)
Ze 2
Σ (z C.))
PL
PEA-
Consequently, we have
1 1-1
Z
Z
Vzln(Z (2 ,
T 1=0
(63)
1
Z = Z
V
PLC
where - = =
24

---

Based on the above identities,
Z 23-1113 ||3
1-1
2
Σ
Vzln Cp)
.
V
Zz 2 20 c))
PIz P
p
L7 j=0
V2fp(Zz51 .c) Σ V V2 C2)
(L3)²²
P
PEA"
S (L2)
Σ
1zfplzz..c3 V2Zz c2)
P
1=0
PEA
Σ
Vzla (2) 1251(z5) c.))
(L2)²
1=0
P'EA-
(64)
Σ
/ - V2lp(2z' ,
c
P
j=DP'EA'
(-1 P
2 - .. 2
Σ
Vzln
wp'
P
j=0p'=1
T.6
i-1
P
Z 2
Σ
Σ
)(12,)21123
z F + 4(L2, )2
Z
+852
(22 5=0p'1
Wp'
F
Bound of T.6
41
Σ
1-1
(1i7, 12
zp 2 + (IZ) 1'm
8/2
(L
1=0
41
ΣΣ
(T j² | 1 23 ||
222)
y=0
Based on Lemma 3, we give bound on T.7.
Lemma E.4. For any 8, it holds that
8Q(Q - 1)(Q
wp W2,,z,)) )2 |z
(65)
p 4QQ - 12
1=1
25

---

Proof. Based on Lemma 3, we have
P
Wpl (T&,)z))) 12
12.-111
||
p
F
f=1
Q P
4(t-11 1-2
8(t 1)26
wp (22,))
Σ
(12 )²
Za z
3 +
(L2)2P
p=1
ド=0
+
1(1 1)
1-2
Σ
up
(Iiz,) )²
2 -
p=0p'=1
Q 4(t - 1)
P
21-2
Q
8(t - -
Σ
wp(L2z) )²
Σ
2 2 + Σ
P
1.2
P
p=1
i=0
[=1
+
Q
4(t
1-2 P 1=0pml
Wp
(L )²
2 - 2
(66)
P
1=1
0
4(t 1)
P
wp(L2z) )
Lz
21-2
Σ
1 25 + Σ
Q
8(t 1)2C
P
L
P
1=1
p=1
1=0
1=1
Q
1(1
1-2 P
+
w/ (I:2,))) )2
2 z
P
j= y/=1
4(1 1)
L2
1-2
8QQQ -)2Q-11(2-
Σ
(1+ +
up(Li,)) 12 Z 2 F
L2
P
p=
1(Q
1)2 P
L Q
8Q(Q 1)(Q-1)22-113
+
Σ
4ip
(Tiz )2 1 z
2
P
p=1
Here, we used the inequality
Σ
4(t
1) 1-2
2 - 2
<
4(Q 1)2 Q
----111 12
(67)
P
P
1=0
Rearranging the above inequality, we have
Q
-Q(Q-11(2Q-1))
wp (LZ,))
| Z 1p. <
(68)
P- p-4(Q- 1000-113:0 1--(Q-1)((1)
Am
26

---

Based on Lemma 4, we continue to do the following derivation:
F
C*) F C*)
L
Q
|| + 16Q
$
Z
4
PLA
4
+
2 L7
(1
+
8 P
Wpl wp(L% (1 )22 $1 1
Zp.-111 2
t=1
T.7
L Q
1 1--2111 16Q5²
(69)
4
PT,
8Q(Q 11(22-1111
+
(1
L7
p
p P-4(Q-1130 + / LB3
- Bound of T.7
Li
Zaif -- F + /6Q
4 t=1
PL1
where 30 1 +
(P+8)(Q11(20))
P-41Q-1)a
Then, combining
46 and 69
yields
P 2 (mmn + 1)
L2 Q
Σ
Up Co - C5- 1/-111 +
Z
1|
4 1=1
p=1
(70)
16Q
< F( - F(Z cC*) +
PL
Derivation of the main result: Based 70
derive the convergence in terms of the iterative terms, Tc(Z%00 C*) and Tz (Z C*) for 8 2,2,.... S.
2
32QC2
To C*)
|F [F - Fl C²'] (7hmn + 1)P113
(71)
Tmmn +
Then, summing it up from s S yields
32SQ2
Σ To (²") < y mmn +1 [F(2.00 C))) - f]+
(72)
( (Tmin + +X)PL2
Similarly, we have
Q Σ (z t=1
(Z",tC")
0²)
-
4 - (0)]++++++++
64Qς2
(73)
P(Lž}²
Then, summing it up from S yields
645Q
Tz (
|F (0)
(74)
L
PL3
Lastly, combining
72 and 774h and dividing two sides of it by T= + Q) yields
$
S
..)) co) < 0 IF C2) - fl +
16
T u C²) +
ΣΣ (z
(75)
T
PLz
t=1
where
min +x + Lz
27

---

Proof for theorem on error bound on noisy similarity matrix
Proof. It follows from the triangle inequality of matrix norm that
K
K
Kas
K + K
K
(76)
S
K
KEz
K2
Karloo
Since X = X + E and ((X) = =((ZCC, we have
K E. (x(2)))
K RE x(X) = -XXX,
(77)
K = ((X))((()--))) = x)
where is a Gaussian noise matrix, of which Eis ~ N/ o²). Hence, we obtain
Ra - K Keo| <
K(X, x) + |x(( k(XX x)
(78)
Denote by æ; (or e;) the i-th column of X E gm (or E E R=x"),, i = I,... we first derive the upper bound of the second term of the RHS of (78) as follows:
K 22 K Ka = ||[(X x) K(X,
max 6.j
[C ã2,) K(x;, xI,1
||<x; + e.)
(2) e2)
2
max exp
2r
exp
2r
||<x; + +;))= - (zz e2)111 + ||2 xz
max ())
2r
(79)
[1; - xx)) + (e, -e,)1 - ||=; -x, 25112
max (J
2p
|le: ejll² + 2(x; e; - eji
max (J
2r
< max ())
(le; - 11/ + 2 - ej1l)
2,2
|le: - e 112 + 2 - 2,l12 lle; - -yyl2)
I max fJ 2r
where for the first inequality we have used the fact that the exponential function is locally Lipschitz continuous, i.c.,
ee - eal < I y/ for x. y < 0.
Now, let figure out the upper bound of ||e; eglli Note that
|le, e Σ (en e1j) 20
Eli Eij
(80)
/2o
1=1
i=1
where en represents the 1-th element of the column vector e;, k = 1,... m. It is clear that for I l...., m,
Ejeu Ety] = 0, var(eu etj] = 20
(81)
Hence, EN-ERL a standard Gaussian random variable drawn from (/0, 1). Based on this, we can /20 define a random variable as
m
Eli Etj 2
(82)
V 20
28

---

which is distributed according to the Chi-squared distribution with m degrees of freedom.
From Laurent and Massart 2000]. know that for any positive I, the Chi-squared variable Q with m degrees of freedom satisties
P(Q > m + 2/ml + 21) S -1-e e
(83)
Hence, a bound on ||e, -eyl- with probability 1- e E is
e; ej 1 2202==00000 2m 2//m + 21).
(84)
Using union bound for
we have
max 6.j
lee ej 111 = 20"Q s 20022 + 2/ 2t).
(85)
holds with probability at least - n(n 1) Assume [ S 0, then |2, - 2: S 20. For
convenience, let { V 22 + 2f. It follows from 79 and (85) that, with probability least 1 - 1-n(n- - 1)e
1
K 28 K Kew oloo I
20 + +2 25112 v20t
2T
-
0
g² + +2V2060
(86)
p2
1
[ot + v20)² 200
Now, we figure out the upper bound of the first term of the RHS of (8).. We have
K Kis-
K
(112)))((222)))
(002)00(((220)))00022200 (6000000000000000000000000000030 6(())
- ((000))00000()(((0000000-00)0)00
=
< (0(2) of o(x))
+ - ((
((((Z)C))l2.c -|0(2]C | + + - o(x))
|
2,00
2,00
(I()(Z))))l2, + +||0(8)/1 2000 /1 | - -(x 2000
(87)
where 11 is a norm such that | |X = max; X,,1 for real matrix X. Here we can just
assume that X Z)) - d5 xx)
7, 7 is some constant; this relies on the optimization.
2,
Moreover, assume |CI|2
TC. we have
| /
2,00 =1
(88)
[l(2)) [[((Z)ll max |CC.وl S VdTc
Hence, we can continue to do the derivation of the preceding inequality.
KE Kea < (10(2)C1122.0 + x 2.00 | - 6(x)
2,00
(89)
s (Vdro + 11h
29

---

As result, the overall bound is
Kis
Rzz
S
K Kzz
+ K - K
(90)
(ot + -20)² -20² + +VVdc++1l
where & (m + 2/mm + 2t).
G Proof for Theorem 3.6
Proof. For a data matrix X E R= it is perturbed by a Gaussian noise matrix E R=x* with (0, o²) form the noisy data matrix X X + E. Let K ((X,X) be the ground truth and Kaz = C' K(Z Z)C be the approximated similarity matrix by FedKMF algorithm Then, consider any two data points in X, H, and Fy,, with the identical label, we know that
Kiu Kij
(91)
yenter) and Kij Kzz)ij- where Ki..- max: ( (( Jik
After running FedKMF (Algorithm 1
the noisy matrix X, if the approximated similarity matrix K K B(r), then consider two points in X, x; and ăj, that are actually and
satisfies
2, perturbed by some noise, we have
K K2 Kiu Ki + Kiu Ki + Kij Kijj
(Kiu - Kin) + (Kij Kis)) + (Kin - Ki;)
S Kia -Kiul + +Kij - -Kil + +Kinu Kiz)
(92)
B(o) + B(()) + (Kiu Kiz)
(B) + +Ki -ii)
where K., = max ((Ka)) ) and Kij = (Kaa)it
3.5 T; and ã. can be correctly clustered only if the following inequality holds with some tolerance
Based on Definition
0.
K Sa
Kij c
(93)
Thus, combining inequalities 992 and 93
the bound function ((rr) satisfies
1 S/e (Kiu Kú))
Bla)
(94)
Similarly, if we consider any two data points in X, and 2,, with different labels, we know that
K S Kio
(95)
where K,. ming ((K ventra). lik
After running FedKMF algorithm
on the noisy matrix X, we have
K, Ki
Kij Kij + Ki Kir + Kiv K
(Kij - Kiz) + (Kiv Kii)) + (Kij Kiv)
1K1j Kijl + |K -Kiol +Kij Kiv)
(96)
S B(o) + B(o) + (Kij - Kiv)
=2((g) + (Kij Kix)
where K... max; ((K (Kan))aa Vintra)
30

---

Based on Definition 3.5 z; and y can be correctly clustered only if the following inequality holds with some tolerance 0.
(97)
Thus, combining inequalities (96) and 97
the bound function B(o) satisfies
B 2 (Kig - kw.)]
(98)
Then, with upper bounds B()). (94) and (98) we have
B(a) S min(e (K Kizh,-- (Ki,, Kio)).
(99)
where is the parameter of tolerance.
Alternatively, a slightly looser version is like
B(o) S min 1 [2c - (Kiu - K(v)]
min
1
(100)
or B(o) S c max
(Kiu - Kiv).
2 i
where K,, = max; (anx:((aaa ((Krr) ( and Kio = min K (Kz))tt )
H
Proof for Proposition 3.7
Proof.
The lz-sensitivity Dwork el al. 2014 of a function f N421 + R is:
(2
max
[ f(y)ll2
where a y denotes that and y are neighboring datasets. In our case, the function f(x) Then
[I(x) f(y)ll2 || ylla S 2Tx.
means (f( & 2Tx. Now using Theorem 3.22 [woork er al. 2014) and Lemma H.1 we get the desired result.
Lemma H.1 (Post-Processing Dwork et al. 2014). Let M N R be a randomized algorithm
that is (e, 8) diffferrentill private. Let h R +
R' be an arbitrary randomized mapping. Then h o M : 2 + R' is (E, differentially private.
I Proof for Theorem 3.8
Proof. Based on the assumptions |C||2,00 S Te, (Z)) ((X)ll,, 57, - C Ee for the
entry (Ec)y NO, og), and 7 = Z + Ez for the entry (Ez)iz ~ NN0,02)) we obtain
K K
((1)))))(((())) (x)
(01))) (6620776200022000000002200021100 - (x)xx((
(1))) (()) + ((x)
< 1 (( - 6(x) / 2,00 + +1 - ((() ///01110
2,00 122,0
(10(2)6)
+ +10(88)1220
| -(x))()) 120
2,00
2,00
(101)
31

---

where ||x(X) 2,,00 1. An upper bound on [())
can be obtained only if we derive the
2,00
upper bound on |o(ž) (6()
2,00
That is, if
Yzze it implies that 6(x0)12.0
|
-
+ +110(x)112, = 720 +1
(102)
2,00
2,00
which consequently gives
K 2z
K
7oo + 2)
(103)
20
Hence, we derive the upper bound on |0(2)Ō - o(x)) )
for the remaining proof.
2,00
|012) 6(x)
[0 2Z (( x(x) 2,00
=
2,00
|
+ +lØ0(Z)C
x6(X)l22n)
(104)
2,00
T22
where the second term |lØ(Z]C - o (X) bound on T.2.
1,,,00 s is the assumption. Next, we derive the upper
((())co(Zz))
0(
2,00
2,00
11 C)+ -
(() - C)
2,00 + (0((2) -(2))
2,00
(105)
s vdllEell2a
[0) (2)
|C1|2,
s <octaVd +
(22)) (Z))
T.3
where we used
1
< 1
d+ 2v + 21 with probability at least 1- ne Laurent and
Massart
2000 since is the fact that J/2 |Ecl2.00 xå where the entry (Ec)u (0, For
733, we have
10(2) -()) 2 = Tr((o(2)- o (Z)) ())
(2)))
=Tr(o" o (Z)
(106)
2d 2 2T (Z)o(Z) 2)
For T.4, we can obtain
d
d
(- | + (Ez).. - 1,
((T"(())(Z))) = Σ o" (z,)0(zz) = Σ exp
2r
j=1
d
(((E))..013
= Σ exp
(107)
2r
j=1
025
2 d dxxp
2,-2
where we use 1 0% [[
)
12 < 3
= d +
2 2/ with probability at least 1 1-de" -t Laurent and
Massart 2000 since it is the fact that || [(E)),.11 ~ x3 where the entry (Ez)ip ~ ~N(0, o2).
/zz
32

---

Hence, we can go back to give an upper bound on |0(2)C x(x)
2,00
|| 10 (X)
-
oc-ooaaad+ roya Sotoo 2d 1- (
(108)
2,00
2r²
Finally, we have
Kiz
Kar
S Szo(772 10772o+20 +2)
(109)
where
occa + 2/11-11111 2
10266
Yze = + vd
(110)
2p
J Proof for Theorem 3.9
Lemma J.I. Assume T ma || - x' 1l2 and || - x'112 S 2Tx, let (C,) 1p=1 be perturbed
by noise drawn from (0, o²) with the parameter a 2 2nA 20x varx((xx for > 211(1.25/6). Then, the Gaussian Mechanism that adds noise to
rte Jp=1 {C is (E, (E.,0)differentiall) private.
S TX. max(i.)) ||z - æi1l00 1,..., be perturbed by noise drawn from o2( with variance (8SA² log(e (E/5))/[²) where A(gz) evdrerxIu 1 (Tx +TZ) (xxAT)
Lemma J.2. Assume max(p Al 112.. 1|,,,, Tpllep op I Tz Vs, and ||, I TC. let {Z for
T.
j. Then, the Gaussian Mechanism that adds noise to 1Z for 1, S is (e, (..o)))fffeennilal private.
By Lemma J.2 the mechanism that adds Gaussian noise to Z for s = 1, S with variance (SSA"(gz) log(e= E + (ez/ (2z))//)/// /²²) satisfies (sz, ddifferrrett privacy under S-fold adaptive com- position for any EZ > and 82 E (0, By Lemma J.1 the Gaussian Mechanism that injects noise to C with parameter a 2 2c2- Vdxxxxx + ()((rEc) is (Ec. diffeferrenti private. Therefore, by Theorem 3.16 of [Dwork al. [0144), ,. the proposed algorithm that adds Gaussian noise to Z for s = 1,... S and C is (EC + ez, dc + 8z -differentially private. This finished the proof.
K Proof for Lemma .II
Proof. In our FedSC, for each column of C, we have
|| 201-211 2r
exp
(0(x) GK GK((Z
=
(111)
1 11 2r
exp
where G = (KC(2, 2) + ALa) We have
(x) (c(x"))) S [II
KCZ, Z, x')
(112)
where || llep denotes the spectral norm of matrix. Since exp(2) is locally Lipschitz continuous when have
1zz
x
||z x
exp
exp
2r
2r
2
(|z)
1|2
||z x 2'11))
2,2
(113)
2
(|æ
+2112
(z, - x'. - =x'))
2r2
12
(|æ - 2'113 + 2| - x' ||21| - x x'112)
2
33

---

Let Y = maxx, w0 ||z 2'1l and || -2'l2 S 2Tx.
Then the l2 fe-seiiity of is
2
A2(9c) I sup |G
(|
2211 2 + 2112, 2'llal1æ' x2112)
2y²
$ S|
Σ
1
(47 + +XTxx
2y2
(114)
j=1
2v 2vdTx(TX + T)
G
p2
2A dTx P)
p2
Then according to Theorem 3.22 in Dwork et al. 2014]. for c² > 2 ln(11225/0) the Gaussian Mechanism with parameter o > proof.
Vddxxixx (e. 8) differrentilly private. This finished the ,2g
L Proof for Lemma .I2
Proof. Proof Sketch The (c, diifferrrttt privacy of the proposed algorithm can be achieved by
injecting noise into Z for each local update and into C' at the final round. To prove this, we first compute the sensitivity of and for determining the differential privacy of them. Then, we use the adaptive composition Kairouzz ef al. 2015 to get the superposition of them which will give the final thcoretical result.
Now, the formal proof is as follows.
In our FedSC, consider one-step update of Z client of p
0f 2p.t-1 1)| 32
(
(115)
where the derivative is given by
01 2z
1 11) =
1
X, Wz ZWz) 2/2 (ZQz ZQz)
(116)
and Xp = [zp1>" ps- pp x p,;+1 pp,,1
For the simplicity of the proof, we omit the pair iteration parameters (s, t) and instead denote two adjacent local updates by kt and k for nonnegative k 2 1. Thus, we have the equivalent version of one-step update of Zp at client p
z k-1
Mh
W 2
+
2 12 2
Qz Zz-1Q2)
(117)
where X, = ppp ... Tpy Tp p, +1
Txx, J-
To compute the sensitivity of Zp. we give the counterpart of the above update as
(z,)) = = 7k
X
W
z k- 'Wz) + 22 p Q2 - 2 Q2)
(118)
where X = [xp.> Tp,
d'yy x2 22 +1,
x xpx,1. |.
Next, let's 's start to derive the upper bound on
- ( || term by term
/ (1 =
|
7k ,.
{X,
Wz 2 - (X, (X,W² (3-lWW))
7/ 72
(X, Wz
-x, - -1 (Wz - Wx2) 1
(119)
<
7k ?2
[x,
W'
p
k-1 Wz w
34

---

For T.1, we have
| x,W>ll = X2W2 X + X - W
(X xx) Wz + X (Wz -
(120)
13
14
For T.3, we have
|1x,, (x) Wzlle
= (Tpp p/p,) (-c3 2 K(mp, z2-1111
cc @ K( z 1111
Tpp
P:
(g 3 e3 mpp)) 2 K(( {pp,)) ;pp;))
p
10 o ,j 2 pp,) @ K(Z I .p,))12 (121)
Fp;
c | [| . 111
Tpp
2 ps
Tp: z
|C ||<(2, 1,,
Here, we use ||a @ bl1 = ((a (b o b) for a, b E Rd for the second equality; Cauchy-
Schwarz inequality for the second inequality; Vlla a = ||a]| for E Rdd for the third inequality.
Let Az.- = <() - KK(Z x²), then we have for T.4.
X (Wz W2)l1a
2/y {
c 1
(Kaapy 1 K(a'p, Zb-11)
2/1 ||
c
(K(ppys 2 K(zi,j Z 11)
2
(122)
(c, + oaj²"
(Dzz .0p;
2 4 2/ Az -.pp
/
||
| 2,00 A2z 1,87,112
Therefore, assume max |0, ||00// [1a} S vx. which means || =0'122 27x, we can get upper bound on T.1.
X2W2 X,W5llB
$ 1xxp x
Wz || + X (Wz W2)1
T.5
T.6
|pp 2// 11,
1Cl1,,00 |K(Z/-1 3pppy) )11
| 2,00
|
23
p3
2
-1C112200 (1155) -2/2, |1,
|K[( xp, )11
+
p
A22
1
1 1111 1,)
<2VdToTX (1 (1+ Tx(Tx+70
p2
(123)
Here, we also used the fact that || .xpp)112
, < Vd and the derived bound (x pd
on
|22--> xp, ll, given by K and ||C||,,0 S To given in Proof
35

---

Assume 12 S Tz Vk, we have for 7.2
1 - (Wz 12 = 7 xK (diag( 1 W2) diag diag(1 W
Z diag 1 (Wz W2)))lp
< 4 'I diag 1 (Wz W2))
= 1 I1
| - -
(124)
x - - || sp 1 ① (K(Ep, -/ K(x')) 22-
, 'I..p ||C|12,00
A2t :pp 11a
WTT +T)
Thus, we get the upper bounds on T.1 and T.2, respectively, and finally give an upper bound on 1 11.
2 (2 1
?h p2
1 x, + +1 (Wz W2
T.1
T.2
7k ,
2VdToTX (1 IX(TX +
-x((xx+T) 1) )
2 2d + +8)
(125)
s
p2
2
2/dTCTxMlc
(Tx + T)
1+ (Tx + T2)
,2
,2
Therefore, if we define Z, = p), the fz-sensitivity of gz is
A2(92) = sup x
11g2 (19z(Xp) 9z 12,
1 \
sup x
(126)
2v dTc
+ (Tx + +2) (Tx + T
r2
By Theorem 4.3 of [airouuz et al.
2015 the mechanism that adds Gaussian noise to Z for = 1, ... S with variance (8SA*(92) log(e e + (E2/ satisfies (Ez, 5z diffeerrent privacy under S-fold adaptive composition for any ez >> 0 and oz (0, 1). This finished the proof.
36


Reviews:
[{"review_id": "1cz009cFHl", "reviewer": "Reviewer_EUeG", "summary": "This paper introduces a secure kernelized factorization approach of spectral clustering. The proposed method works on distributed datasets while maintaining privacy. The proposed technique approximates the kernel matrix required as in the spectral clustering, in an effort to preserve the privacy. This paper analyses the convergence of the optimization algorithm and offers bounds on the reconstruction error of the kernel matrix. The efficacy of this proposed approach is supported by experiments on both synthetic and real image datasets.", "questions": "Please refer to the weakness section for questions. ", "limitations": "The authors addressed some of the limitations, e.g., the methods are not tested on very large datasets. However, there may be some other potential limitations as discussed in the weakness section. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper studies an interesting problem: federated spectral clustering with privacy considerations. Since clustering requires access to the data, it is non-trivial to do clustering while maintaining privacy. The proposed method seems novel to me.", "weaknesses": "The only major concern I have is the privacy claim in this paper, and it is a vital one. The proposed method is only meaningful when it is proven to be secure and private (while keeping good utility), otherwise one could simply use any clustering algorithms out there. However, the evidence regarding its privacy guarantee is not sufficient in my opinion. Therefore, I would suggest the authors put more efforts into grounding their claim on the privacy. \n\nConcretely, there are two (or three if more specifically) cases where security may be considered separately. \n1. No noise is injected, i.e., the method detailed in section 2 where no differential privacy is considered. In this case, it is implied that this federated algorithm can help privacy, e.g., see line 89 (To guarantee the privacy of information, problem (7) shall be solved\n90 in the framework of federated learning.) However, no evidence shows this federated operation can guarantee privacy. For example, one might apply the following idea to extract the local data $X_p$. Since equation (9) and (10) are quadratic minimization problem, they have explicit solutions. Therefore, by (10) it seems that one can write $Z^s_p$ as an expression of $X_p$ and $C^s_p$. Noting that by (9) $C^s_p$ can be written as an expression of $X_p$ and $Z^{s-1}$. Therefore, we have an equation of $Z^s, Z^{s-1}$ and $X_p$ for each $s$. Since $Z^s$ and $Z^{s-1}$ are known, can we solve $X_p$ from them? One argument for this idea not to work is that the dimension of the feature space may be high. However, there are also multiple such equations, i.e., $s=1,\\dots,S$. In general, the choice of the feature map $\\phi$, the number of communication rounds may also affect the level of privacy. Therefore, I am expecting to see such discussions regarding the \"privacy guarantee\" brought by the federated procedure.\n\n2. In addition to learning in a federated way, the author also considers adding noise to enhance privacy, as analyzed in a differential privacy way. I acknowledge that Proposition 3.7 and Theorem 3.8 shows the DP guarantee for the proposed approach. However, DP can be achieved by adding sufficiently large noise if not considering the utility. Therefore, it is important to see the privacy-utility trade-off. For example, theoretically, eq. 32 gives an upper bound on the variance of the noise of the clustering $\\sigma$, and proposition 3.7 gives a lower bound on the $\\sigma$ for the sake of differential privacy. Can one derive a trade-off relation from the two inequalities? Empirically, Table 1 shows the performance of the proposed method given certain level of noise being injected. Can the level of noise being associated with the level of DP guarantee?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank the reviewer for the comments. Our responses to your comments and questions are as follows.\n\n**Response to Weakness 1:**\n\nFirst, due to the kernel mapping, the minimization problem for $\\mathbf{Z}_p$ is nonconvex and has no closed-form solution. This implies that it is very difficult or even impossible to achieve its global minimum by common numerical methods when solving $\\mathbf{X}_p$ from $\\\\{\\mathbf{Z}^{s}\\\\} _{s=1}^S$. Thus, peeking at the privacy information from $\\\\{\\mathbf{Z}^{s}\\\\} _{s=1}^S$ is computationally difficult. On the other hand, to our own knowledge and experience, the existing literature on federated matrix factorization did not claim that federated settings can efficiently protect users' privacy. For example, Chai et al. [1] argued that gradient information may still leak users' raw data and had to adopt homomorphic encryption to enhance the distributed federated matrix framework. Similarly, this is exactly the reason why we choose to add noise to the data or factors for improving the security of the proposed framework.\n\n[1] Chai, D., Wang, L., Chen, K., $\\And$ Yang, Q. (2020). Secure federated matrix factorization. IEEE Intelligent Systems, 36(5), 11-20.\n\n**Response to Weakness 2:**\n\nIt is easy to derive a range of $\\sigma$ between the lower bound given by Proposition 3.7 and the upper bound given by Theorem 3.6. In particular, if we substitute $\\sigma$ with the upper bound, we can get a strong level of privacy but the worst utility. Analogously, we can also get such a case for Theorem 3.8.\n\nFor instance, Theorem 3.6 implies that, to ensure correct clustering, the noise (with standard deviation $\\sigma$) should satisfy the following inequality\n$$\\quad \\sigma \\leq \\frac{1}{\\xi}\\left[\\sqrt{r^2\\left(B_1-B_2\\right)+2 \\theta^2}-\\sqrt{2} \\theta\\right]$$\nOn the other hand, Proposition 3.7 indicates that, to ensure $(\\epsilon, \\delta)$ differential privacy, $\\sigma$ should obey\n$$\\quad \\sigma> 2 \\sqrt{2 \\ln (1.25 / \\delta)} \\tau_ X / \\varepsilon$$\n\nNow combining these two inequalities together, we obtain\n$$2 \\sqrt{2 \\ln (1.25 / \\delta)} \\tau_ X / \\varepsilon<\\sigma\\leq \\frac{1}{\\xi}\\left[\\sqrt{r^2\\left(B_1-B_2\\right)+2 \\theta^2}-\\sqrt{2} \\theta\\right]$$\nThis provides a privacy-utility trade-off.\nWhen the noise level $\\sigma$ is in the above range, we can get correct clustering while protecting privacy ($(\\epsilon, \\delta)$ differential privacy). By the way, $B_1-B_2$ is related to the property of the data. A larger $B_1-B_2$ means a better property for clustering, which further provide a larger upper bound for the noise level $\\sigma$, yielding a stronger privacy guarantee. We will add more discussion in our revised paper. Thank you again for the insightful comments.\n\nThe level of noise in Table 1 is directly related to the DP guarantee. For convenience, we show part of Table 1 below.\nThe first block shows the noise-free case. The second and third blocks are the cases with noise inject, where $0.3\\sigma_x$ and $0.5\\sigma_x$ are two specific examples of the $\\sigma$ in the DP guarantee. \n\n\\begin{matrix}\n\\hline & & \\text { Kmeans } & \\text { SC } & \\text { DSC } & \\text { FedSC } \\\\\\\\\n\\hline  & \\text { Iris } & 0.8933 \\pm 0.0000 & 0.9000 \\pm 0.0000 & 0.5480 \\pm 0.0679 & 0.9000 \\pm 0.0031 \\\\\\\\\n& \\text { COIL20 } & 0.6113 \\pm 0.0534 & 0.8025 \\pm 0.0009 & 0.1009 \\pm 0.0100 & 0.7828 \\pm 0.0231 \\\\\\\\\n{\\boldsymbol{X}} & \\text { Bank } & 0.6122 \\pm 0.0000 & 0.5918 \\pm 0.0000 & 0.5582 \\pm 0.0045 & 0.7672 \\pm 0.1457 \\\\\\\\\n& \\text { USPS } & 0.6704 \\pm 0.0047 & 0.6635 \\pm 0.0000 & 0.1686 \\pm 0.0014 & 0.6596 \\pm 0.0021 \\\\\\\\\n& \\text { ORL } & 0.6325 \\pm 0.0270 & 0.7865 \\pm 0.0106 & 0.1653 \\pm 0.0073 & 0.7235 \\pm 0.0170 \\\\\\\\\n\\hline & \\text { Iris } & 0.8420 \\pm 0.0274 & 0.8327 \\pm 0.0267 & 0.4533 \\pm 0.0674 & 0.8427 \\pm 0.0404 \\\\\\\\\n& \\text { COIL20 } & 0.6422 \\pm 0.0366 & 0.7997 \\pm 0.0029 & 0.0981 \\pm 0.0084 & 0.7793 \\pm 0.0240 \\\\\\\\\n{\\tilde{\\boldsymbol{X}} \\text { with 0.3 } \\sigma_x} & \\text { Bank } & 0.6020 \\pm 0.0038 & 0.5859 \\pm 0.0105 & 0.5588 \\pm 0.0074 & 0.6046 \\pm 0.0064 \\\\\\\\\n& \\text { USPS } & 0.6704 \\pm 0.0063 & 0.6720 \\pm 0.0044 & 0.1673 \\pm 0.0019 & 0.6884 \\pm 0.0509 \\\\\\\\\n& \\text { ORL } & 0.6098 \\pm 0.0167 & 0.7885 \\pm 0.0047 & 0.1665 \\pm 0.0057 & 0.7417 \\pm 0.0280 \\\\\\\\\n\\hline & \\text { Iris } & 0.7740 \\pm 0.0252 & 0.7313 \\pm 0.0494 & 0.3833 \\pm 0.0204 & 0.7540 \\pm 0.0336 \\\\\\\\\n& \\text { COIL20 } & 0.6389 \\pm 0.0296 & 0.7950 \\pm 0.0080 & 0.1033 \\pm 0.0167 & 0.7403 \\pm 0.0294 \\\\\\\\\n{\\tilde{\\boldsymbol{X}} \\text { with 0.5 } \\sigma_x}  & \\text { Bank } & 0.6051 \\pm 0.0076 & 0.5923 \\pm 0.0094 & 0.5566 \\pm 0.0030 & 0.6086 \\pm 0.0073 \\\\\\\\\n& \\text { USPS } & 0.6699 \\pm 0.0031 & 0.7843 \\pm 0.0030 & 0.1683 \\pm 0.0017 & 0.7778 \\pm 0.0062 \\\\\\\\\n& \\text { ORL } & 0.5983 \\pm 0.0295 & 0.7930 \\pm 0.0172 & 0.1615 \\pm 0.0096 & 0.7107 \\pm 0.0345 \\\\\\\\ \\hline\n\\end{matrix}\n\nBy the way, Figure 3 in our paper can also show the trade-off of privacy-utility, where the synthetic data are better posed. We will add more results of the synthetic data to quantify the trade-off of privacy-utility."}, {"review_id": "1NgfECzsRS", "reviewer": "Reviewer_cNYr", "summary": "This paper focuses on computing spectral clustering in the setting of horizontal federated learning. The main contributions of this paper are: (1) proposing a secure method for computing the adjacency matrix to achieve spectral clustering, (2) providing rigorous theoretical analysis to ensure the algorithm satisfies differential privacy, and (3) conducting experiments on multiple datasets to demonstrate the effectiveness of the proposed method, FedSC.", "questions": "See weakness.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n(1) The paper is logically organized and well-written, effectively introducing the work on FedSC.\n(2) The proposed method, FedSC, is simple and reasonable, with theoretical guarantees. The paper is comprehensive (although detailed proof examination was not conducted).", "weaknesses": "I believe the experimental section of the paper can be further improved:\n\n(1) In the Stage II Spectral Clustering phase of FedSC, when clients upload to the server, is there a significant risk of privacy leakage? Is the solution to add noise (as mentioned in Section 3.2)?\n\n(2) Are both Stage I and Stage II of FedSC updated in each epoch? Can the author evaluate the difference in runtime between the two stages of FedSC and baseline models?\n\n\n(3) Experimental section:\n\na. Although the paper has theoretically demonstrated the privacy of FedSC, there is still a lack of direct evidence in the experimental section to prove the privacy preservation of FedSC. It is suggested that the author report the clustering accuracy recovered by attackers from the data uploaded by clients to the server, as this would intuitively reflect the emphasized privacy of FedSC.\n\nb. I would recommend including a natural baseline is to perform FedSC using only one client (e.g., just perform some kind of dimension reduction if Z is not too high-diemensional), which can give us better sense of the loss due to splitting if any and reduce the influence of this potentially denoise step (which is not novel) in the comparison.\n\nc. Why does Table 1 show that FedSC outperforms SC (such as in the Bank dataset)?Can the author provide further explanation? Why does FedSC in the Bank dataset show a large standard deviation and unstable performance in Table 1, while baselines do not have this issue? \n\nd. Is FedSC in Table 1 considering only perturbed data? Why not consider FedSC with perturbed factors? The Iris dataset and other datasets used in experiments are too simplistic. Can higher-dimensional image datasets be considered to demonstrate the effectiveness of the method?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors sincerely appreciate the insightful comments made by the reviewer.\n\n**Response to weakness 1:**\n\nAs claimed by Chai et al.[1], the general framework of federated matrix factorization may still leak users' raw data. Therefore, extra measure needs to be taken for enhancing the security of algorithms. Our study chose to add noise to give differential privacy guarantees on the proposed framework. According to Proposition 3.7 and Theorem 3.8 in our paper, privacy can be protected when sufficient noise is added.\n\n[1] Chai, D., Wang, L., Chen, K., $\\And$ Yang, Q. (2020). Secure federated matrix factorization. IEEE Intelligent Systems, 36(5), 11-20.\n\n**Response to weakness 2:**\n\nNot like that. Stage I is a learning process for $\\mathbf{Z}$ and $\\\\{\\mathbf{C}_p\\\\} _{p=1}^P$ and has a number of epochs of training. After Stage I is completed, namely $\\mathbf{Z}$ and $\\\\{\\mathbf{C}_p\\\\} _{p=1}^P$ are well-learned, we perform Stage II, which just computes the adjacency matrix using $\\mathbf{Z}$ and $\\\\{\\mathbf{C}_p\\\\} _{p=1}^P$ and then conduct spectral clustering. The time complexity of Stage I is $\\mathcal{O}((dmn+d^2m+d^3)T)$ and the time complexity of Stage II is $\\mathcal{O}(d^2m+d^2n+Kn^2)$, where $T$ denotes the number of iterations in Stage I and $K$ denotes the number of clusters. We see that when $n$ is relatively small, the time cost of Stage I is higher. When $n$ is very large, the time cost of Stage II is higher (caused by eigenvalue decomposition). This is consistent with our numerical result.\n\n**Response to weakness 3(a):**\n\nWe are sorry that we cannot fully understand your question. If the following response does not accurately match your question, please do not hesitate to let us know.\n\nFirst, due to the kernel trick, the optimization problem is nonlinear and nonconvex and hence it is very difficult for the attackers to recover the data $\\mathbf{X}$ from the uploaded factors $\\mathbf{Z},\\mathbf{C}$, especially when $\\mathbf{X}$ or $\\mathbf{Z},\\mathbf{C}$ are perturbed by noise. Thus, the clustering accuracy on the recovered $\\mathbf{X}$ by attackers will be low. In addition, we suppose that the attackers use the upload $\\\\{\\mathbf{C}_p\\\\} _{p=1}^P$ to cluster the data via k-means. We find that the clustering accuracy is lower than those of Kmeans, SC, and FedSC reported in Table 1 in our paper. For instance, the clustering accuracy on Iris is reported in the following table.\n\n|      |       Kmeans      |         SC        |        DSC        |       FedSC       |  FedSC(Attacker)  |\n|:----:|:-----------------:|:-----------------:|:-----------------:|:-----------------:|:-----------------:|\n| Iris | $0.8920\\pm0.0028$ | $0.9000\\pm0.0000$ | $0.5493\\pm0.1263$ | $0.9027\\pm0.0064$ | $0.6360\\pm0.1557$ |\n\n**Response to weakness 3(b):**\n\nWe designed an extra experiment to compare the clustering performance between using a single client ($P=1$) and using multiple ones ($P=8$). The result can be shown here. It is clear that the operation of splitting data across multiple clients may lead to accuracy loss of clustering.\n\n\\begin{matrix}\n\\hline\n&  Iris                &  Coil20       &Bank        &ORL     \\\\\\\\ \\hline\nP = 1 & 0.9007\\pm 0.0086 &0.8073\\pm 0.0089  & 0.7536\\pm 0.1271& 0.7937\\pm0.0084 \\\\\\\\ \nP = 8 & 0.8993\\pm 0.0165 & 0.8003\\pm0.0049 & 0.6821\\pm0.1405 & 0.7112\\pm0.0258 \\\\\\\\ \\hline\n\\end{matrix}\n\n**Response to weakness 3(c):**\n\nAs we know, the similarity graph is a key ingredient of spectral clustering. As for vanilla spectral clustering, the similarity matrix $\\mathcal{K}(\\mathbf{X},\\mathbf{X})$ directly constructed from raw data could be very sensitive to noise and outliers. Instead, FedSC reconstructs $\\mathcal{K}(\\mathbf{X},\\mathbf{X})$ by $\\mathbf{C}^T\\mathcal{K}(\\mathbf{Z}, \\mathbf{Z})\\mathbf{C}$, which has a potential denoising effect. Therefore, it is possible for FedSC to achieve a better performance in some cases. The unstable phenomenon on the Bank dataset is caused by the random initialization of factor $\\mathbf{Z}$ and the number ($m$) of attributes of the data is only $5$ and the adaptively determined $d$ is also small, where the optimization is nonconvex. When we increased $d$, we found that the variance was reduced.\n\n**Response to weakness 3(d):**\n\nWe are very sorry to have you confused about this. In fact, we reported the performance of FedSC with perturbed factors in Table 5 of the supplementary material. On the other hand, we have already included datasets of high-dimensional images like USPS and COIL-20 with sizes $16\\times 16$ and $20 \\times 20$, respectively. Nevertheless, to further improve the experiment, we added the results of MNIST ($28\\times28$) and CIFAR-10($32\\times32$) here. \n\n|                               |         |       Kmeans      |         SC        |        DSC        |       FedSC       |\n|:-----------------------------:|:-------:|:-----------------:|:-----------------:|:-----------------:|:-----------------:|\n|          $\\mathbf{X}$         |  MNIST  | $0.5448\\pm0.0257$ | $0.6265\\pm0.0439$ | $0.1292\\pm0.0144$ | $0.6139\\pm0.0464$ |\n|                               | CIFAR10 | $0.2171\\pm0.0132$ | $0.2182\\pm0.0133$ | $0.1235\\pm0.0062$ | $0.2134\\pm0.0131$ |\n| $\\mathbf{X}$ with $0.3\\sigma$ |  MNIST  | $0.5402\\pm0.0225$ | $0.5755\\pm0.0366$ | $0.1337\\pm0.0191$ | $0.5606\\pm0.0457$ |\n|                               | CIFAR10 | $0.2209\\pm0.0154$ | $0.2198\\pm0.0172$ | $0.1194\\pm0.0051$ | $0.2187\\pm0.0125$ |\n| $\\mathbf{X}$ with $0.7\\sigma$ |  MNIST  | $0.5374\\pm0.0555$ | $0.5711\\pm0.0329$ | $0.1340\\pm0.0135$ | $0.5029\\pm0.0264$ |\n|                               | CIFAR10 | $0.2202\\pm0.0147$ | $0.2205\\pm0.0084$ | $0.1209\\pm0.0045$ | $0.2134\\pm0.0152$ |"}, {"review_id": "5l1JjpDxaV", "reviewer": "Reviewer_fSDW", "summary": "This paper solves unsupervised spectral clustering by reconstructing the similarity matrix under a Federated Learning (FL) and Differentially Private (DP) setting. The authors argue that since the similarity matrix requires computation across pairs of clients it might not be directly FL-compatible. Thus, the authors set out to approximate the feature-mapped matrix ($\\phi(X_p)$) for some client $p$ by an appropriate dictionary-coefficient product. The eventual similarity matrix is computed by the server by collecting each client's approximate dictionary-coefficient pair. In particular, since the raw data does not directly reach the server, the proposed algorithm FedSC is FL-compatible.\n\n The rest of the article demonstrates the convergence analysis of the proposed method, DP analysis and results, and empirical results. Especially, the FL results seem to converge well with large enough iterations for moderately sized datasets. However, the reviewer has some confusion regarding the DP results and their efficacy for high-dimensional matrices, the comparison against other traditional FL / distributed approaches, and the provided empirical results.", "questions": "The paper is well-written and presented. In particular, the authors demonstrate a general framework that can compute pair-wise client functions without relying on a distributed learning assumption. There are no major concerns for the FL-only work. For the DP-FL work point 2 in the weaknesses section is important to address as it might render the DP-FL solution impractical for high dimensions. Point 3 in the same section might provide an alternative solution that could be explored further.", "limitations": "The authors generally address most limitations well including the impact of large privacy noise and the impact of large-scale datasets (inherent limitation of spectral clustering).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper discusses a solution for the often under-studied field of Federated unsupervised learning. In particular, the authors propose a solution for spectral clustering that is FL-compatible while ensuring that the sum over the differences in the consecutive sequence terms generated by spectral clustering converges to a finite value over asymptotic $T$. \n\n1. Primarily, the authors manage to tackle the data pair problem faced in computing the similarity matrix. For simply computing the Gaussian kernel, a cross-term product between terms of different clients is required. Thus vanilla FL training no longer suffices without an assumption that clients are allowed to directly interact with one another. Thus, the general framework provided by the authors can be quite important for not only FL-based clustering but to reduce the communication cost of $O(N^2)$ required by non-private training where each client is allowed to interact with other clients. Here, $N$ is the total number of clients.\n2. The authors demonstrate the FL compatibility of FedSC via the proposed two-pronged optimization technique that generates a “close” similarity matrix to the original one while also ensuring that the errors generated due to FL are asymptotically small for a large number of iterations.\n3. Empirically, compared to previous FL spectral clustering approaches, the proposed FedSC performs the best for most scenarios. Furthermore, FedSC is Differential Privacy (DP) compatible too.\n4. The paper is clearly written and explores multiple avenues such as FL, DP-FL, and adding privacy noise to both the original data matrix as well as the outputs of the proposed algorithm.", "weaknesses": "Although the authors provide a unique approach to handling FL-based spectral clustering, some questions about their approach are detailed below.\n\n1. It is unclear why the assumption of $\\phi(X) = C\\phi(Z)$ is the best choice for the FL-only case. The aim of FL is to ensure that raw data is never transmitted to the server and the artifact transmitted to the server should not be easily invertible back to the raw data. Thus, instead of the proposed solution if we now approximate $\\phi(X) = f(Z) - C$ where $C$ is kept private to the client. Then, it might be interesting to understand whether such a transformation would suffice for FL and what benefits might the approach in the paper provide over this other approach (or another similar approach).\n2. The paper provides DP-FL guarantees for FedSC. However, the accuracy guarantee is weak for the high number of dimensions $m$ or high value of $d$ (dictionary and coefficient size). Particularly, from Thm. 3.1, the $l_{\\infty}$ norm is of the order $m$.\n3. Although this paper does not tackle a distributed setting, it will be beneficial to provide some insight into any possibilities of using Secure Aggregation or other cryptographic techniques to handle pair-wise client functions such as the kernel function. Although the communication cost will be high, there might be ways to reduce the DP noise levels.\n4. For the empirical evaluations, it is surprising that Vanilla spectral clustering performs worse than FedSC. Providing some intuition for this result will be helpful.\n5. Consider including a discussion section that demonstrates the benefits of the proposed approach over distributed learning (in terms of communication costs).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, the authors sincerely thank you for recognizing our work. We provide the responses to your five questions as follows.\n\n**Response to weakness 1:**\n\nThanks for the insightful comment. Our goal is to compute a kernel matrix $\\mathcal{K}(\\mathbf{X}, \\mathbf{X})$ without sending the data to the server. To achieve the goal, we consider $\\phi(\\mathbf{X}) = \\phi(\\mathbf{Z})\\mathbf{C}$ as it can be used to estimate the kernel matrix, i.e., $\\mathbf{C}^T\\mathcal{K}(\\mathbf{Z}, \\mathbf{Z})\\mathbf{C}\\approx \\mathcal{K}(\\mathbf{X}, \\mathbf{X})$, where we send $\\mathbf{Z},\\mathbf{C}$ instead of $\\mathbf{X}$ to the server. If we use $\\phi(\\mathbf{X}) = f(\\mathbf{Z}) - \\mathbf{C}$, we may not obtain an estimation for $\\mathcal{K}(\\mathbf{X}, \\mathbf{X})$. In other words, it could be difficult to find $f$ an $\\mathbf{C}$ to ensure $(f(\\mathbf{Z}) - \\mathbf{C})^\\top (f(\\mathbf{Z}) - \\mathbf{C})=f(\\mathbf{Z})^\\top  f(\\mathbf{Z})+\\mathbf{C}^\\top\\mathbf{C}-f(\\mathbf{Z})^\\top\\mathbf{C}-\\mathbf{C}^\\top f(\\mathbf{Z})$ is a good reconstruction of the kernel matrix, unless we replace $\\mathbf{C}$ with $\\phi(\\mathbf{C})$ and $f(\\mathbf{Z})$ with $\\phi(\\mathbf{Z})$. We will provide more explanation in the revised paper.\n\n**Response to weakness 2:**\n\nThe accuracy guarantee is actually not that bad since Theorem 3.1 implies that the reconstruction error increases linearly with $\\sqrt{d}$ and linear with ${m}$ but there is an $r^2$ in the denominator: $\\left\\Vert\\hat{\\boldsymbol{K}} _{\\tilde{x} \\tilde{x}}-\\boldsymbol{K} _{x x}\\right\\Vert _{\\infty} \\leq \\frac{1}{r^2}\\left[(\\sigma \\xi+\\sqrt{2} \\theta)^2-2 \\theta^2\\right]+\\left(\\sqrt{d} \\tau_C+1\\right) \\gamma$ where $\\xi=\\sqrt{(m+2 \\sqrt{m t}+2 t)}$. Note that $r$ is the hyperparameter of the Gaussian kernel. In our experiment, $r$ was automatically estimated as the mean of all pairwise distance between data points, _i.e._, $r = \\frac{1}{n^2}\\sum _{i,j}d(\\mathbf{x}_i, \\mathbf{x}_j)$. Note that $d(\\mathbf{x}_i, \\mathbf{x}_j)=\\Vert \\mathbf{x} _i - \\mathbf{x} _j \\Vert$ is linear with $\\sqrt{m}$. More intuitively, if we assume $|\\mathbf{x} _{ik} - \\mathbf{x} _{jk}| = \\mathcal{O}(\\varepsilon)$ for all $i, j \\in [n], k\\in[m]$, then $d(\\mathbf{x} _i, \\mathbf{x} _j) =  \\mathcal{O}(\\sqrt{m}\\varepsilon)$, which implies that $r=\\mathcal{O}(\\sqrt{m}\\varepsilon)$. To sum up, $r^2$ is linear with $m$, which indicates that the $\\ell _{\\infty}$ norm of the reconstruction error is only linear with $\\sqrt{d}$, not related to $m$. We will add this explanation to the revised paper. Thank you very much for raising the question that has made our theoretical result more meaningful and clearer.\n\n**Response to weakness 3:**\n\nThanks a lot for the nice suggestion. In our proposed framwork, both $\\mathbf{Z} _p^S$ and $\\mathbf{C} _p^S$ need to be posted to central server for estimating a similarity graph $\\mathbf{C}^T\\mathcal{K}(\\mathbf{Z}, \\mathbf{Z})\\mathbf{C}$, which may give more information to the central server even though we have some theoretical guarantees on the security of FedSC. If we we want to further enhance the security of the proposed framework using cryptographic methods, here is an alternative that can be shown. \n1. Step 1: $\\mathbf{Z} _p^S$ is posted to the central server; \n2. Step 2: Central server aggregates $\\mathbf{Z} _p^S$ to get the global $\\mathbf{Z}^S$; \n3. Step 3: Central server computes $\\mathcal{K} _{ZZ} = \\mathcal{K}(\\mathbf{Z}^S, \\mathbf{Z}^S)$ and broadcast it to clients; \n4. Step 4: For client $p$ and $\\mathbf{c} _i \\in \\mathbf{C} _p$, if $\\mathbf{c} _j \\in \\mathbf{C} _p$, then client $p$ directly calculate $\\hat{\\mathcal{K}} _{ij} = \\mathbf{c} _i\\mathcal{K} _{ZZ}\\mathbf{c} _j$; if $\\mathbf{c} _j \\in \\mathbf{C} _{p'}$, then client $p$ firstly encrypts and transfers its $\\mathbf{c} _i$ to client $p'$, and then client $p'$ also encrypts its $\\mathbf{c} _j$ and use the cipher text to compute $enc(\\hat{\\mathcal{K}} _{ij}) = enc(\\mathbf{c} _i^T)enc(\\mathcal{K} _{ZZ})enc(\\mathbf{c} _j)$; Client $p'$ transfers the result $enc(\\hat{\\mathcal{K}} _{ij})$ back to client $p$; Client $p$ decrypts $enc(\\hat{\\mathcal{K}} _{ij})$ to get $\\hat{\\mathcal{K}} _{ij}$. \n5. Step 5: Each client $p$ sends its estimated results $\\hat{\\mathcal{K}} _{ij}$ back to the central server without sending its own $\\mathbf{C} _p$; \n6. Step 6: Central Server checks whether these posted results from clients are compatible with each other in case of injection attacks and then performs spectral clustering. \n\nThis alternative does not send clients' $\\mathbf{C}$ to the central server and gives an extra cross-validation process in the central server which may be useful to enhance the security. We will discuss the possibilities of using Secure Aggregation or other cryptographic techniques to handle pair-wise client functions such as the kernel function.\n\n**Response to weakness 4:**\n\nAs we know, the similarity graph is a key ingredient of spectral clustering. As for vanilla spectral clustering, the similarity graph directly constructed from raw data could be very sensitive to each data point. Instead, FedSC is just to realize an approximation $\\mathbf{C}^T\\mathcal{K}(\\mathbf{Z}, \\mathbf{Z})\\mathbf{C}$ of $\\mathcal{K}(\\mathbf{X},\\mathbf{X})$ which may have potential denoising effect on the raw data. Therefore, it is possible for FedSC to achieve a better performance.\n\n**Response to weakness 5:**\n\nYes. It is important and interesting to show the benefits of our method over distributed learning since federated learning is closely related to distributed learning. \n"}, {"review_id": "pIXOLD3HXt", "reviewer": "Reviewer_Mxhk", "summary": "The paper proposes a secure kernelized factorization method for federated spectral clustering on distributed data. It provides convergence guarantee of the optimization, reconstruction error bound of similarity matrix, and sufficient condition of correct clustering. It also presents guarantees of differential privacy. The effectiveness of the proposed method is demonstrated by synthetic and real datasets.", "questions": "1. In equation (11), why not use a fixed number of participated clients?\n\n2. In Theorem 3.1, was the $\\ell_{2,\\infty}$ norm defined as the maximum of the $\\ell_2$ norms of the matrix columns? If yes, the definition of $\\theta$ and $\\tau$ can also use the $\\ell_{2,\\infty}$ norm.\n\n3. Does formula (27) ensure the symmetry?\n\n4. Section 3.1 considered perturbed data while section 3.2 considered perturbed factors. Which strategy is better?\n\n5. In Theorem 3.8, the definition of $\\Upsilon$ is related to $\\mathbf{z}_i$, which does not include an $s$ or $S$. Is it a typo? What is the connection between the privacy protection and the reconstruction of similarity matrix or the performance of spectral clustering.\n\n6. In Figure 3(e), it is not clear why vanilla SC failed but FedSC still worked well.\n\n7. In Table 1, it seems that the performance of the baseline DSC is not satisfactory in most cases. Can the authors explain more about the result?", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies federated spectral clustering, which is an important problem but was rarely studied in literature.\n\n2. The authors propose a federated spectral clustering algorithm and analyzed the convergence of the optimization algorithm. \n\n3. Besides the federated factorization model for similarity matrix reconstruction, the authors propose two approaches to enhancing the privacy of federated spectral clustering, one is to perturb the original data, the other is to perturb the learned factors.\n\n4. The authors provide a lot of theoretical guarantees for the proposed methods, including the reconstruction error (Theorem 3.1) of the true similarity matrix, condition of correct clustering (Theorem 3.6), and differential privacy analysis (Proposition 3.7 and Theorem 3.8). \n\n5. The numerical results show that the proposed FedSC is more effective than the baselines such as DSC.\n\nIn sum, this is a strong paper that addressed an important problem. It contains both theoretical analysis and numerical evaluation. The paper is well-written and easy to follow.", "weaknesses": "1. Some theoretical result and all the experimental results of FedSC with perturbed factors are in the supplementary material. I suggest the authors put them back to the main paper via adjusting the structure of the paper, e.g., simplifying Table 1 in the main paper.\n\n2. A few points haven’t been sufficiently explained. Please refer to the session of Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors sincerely appreciate the insightful comments made by the reviewer.\n\n**Response to weakness 1:**\n\nThis issue gets involved with the unexpected drop-out of participated clients in each round, which is actually a common phenomenon in network communication. But here, we just want to claim our model adopted the federated framework of model averaging. To concentrate on our topic, we have used a fixed number of participating clients (as claimed in lines 109 - 110.) and ignored the abnormal phenomenon.\n\n**Response to weakness 2:**\n\nThanks for pointing out. We will correct it.\n\n**Response to weakness 3:**\n\nIn general, the affinity matrix for spectral clustering is not necessarily symmetric. However, in (27), we have made $\\hat{\\boldsymbol{K}}_{\\tilde{x} \\tilde{x}}$ symmetric, which is to ensure the consistency with the kernel matrix to be reconstructed.\n\n**Response to weakness 4:**\n\nThrough our experiments, it can be observed that perturbing factors can have a more significant impact on the accuracy of clustering results than perturbing raw data. That is, perturbing factors are more sensitive and can achieve a specified level of DP with weaker noise. In terms of this, the latter may be better.\n\n**Response to weakness 5:**\n\nSorry about this typo. Since we only perturbed factor $\\\\{\\mathbf{C}_p^S\\\\} _{p = 1}^P$, it should be $\\mathbf{z}_i^S$. We will correct this. We aim at designing a secure spectral clustering for protecting users' raw data but still need to guarantee that the proposed algorithm has satisfactory accuracy. Specifically, privacy protection gives a lower bound on the variance of noise while reconstruction with good quality requires that the noise cannot break down some upper bound. The intensity of noise should meet the two requirements to help see the privacy-utility tradeoff.\n\n**Response to weakness 6:**\n\nAs we know, the similarity graph directly constructed from raw data could be very sensitive to each data point. When we added too much noise to the raw data, the similarity graph may fail to model the local neighborhood relationships which may be the reason why 3(e) is not separable for vanilla SC. Instead, FedSC is just to realize an approximation $\\mathbf{C}^T\\mathcal{K}(\\mathbf{Z}, \\mathbf{Z})\\mathbf{C}$ of $\\mathcal{K}(\\mathbf{X},\\mathbf{X})$ which could have potential denoising effect on the raw data. Therefore, it is possible for FedSC to achieve a better performance.\n\n**Response to weakness 7:**\n\nAs proposed by DSC, it performs spectral clustering on each local dataset, which may lead to very unstable results. Besides, the extra operation includes the second k-means on the local centroids to get the global centroids. This makes it less interpretable compared with the vanilla SC. These may be reasons why DSC did not perform well in our experiments."}]

Author rebuttal:
We sincerely thank the area chairs and all reviewers. We have responded to the comments given by the reviewers carefully.
Here we summarize a few important points of our rebuttal or revision.

1. For Reviewer EUeG, we provide a formula to present a privacy-utility trade-off, namely, a trade-off between privacy guarantee and clustering success.

2. For Reviewer cNYr, we added three experiments.
   * Clustering result on the data recovered by an attacker
   * Accuracy loss of splitting data across multiple clients
   * Experiments on two more image datasets, MNIST and CIFAR10

3. For reviewer fSDW, we theoretically showed that the kernel reconstruction error in terms of $\ell_{\infty}$-norm is not related to the data dimension via analyzing the property of hyperparameter $r$. Eventually, the error is linear with $\sqrt{d}$, which is quite tight.

Meta-review: This paper studies the problem of (kernelized) spectral clustering in the federated learning setting. While spectral clustering has been well studied in the past, applying existing results to the federated learning setting is not straightforward. This is particularly due to the fact that computing the kernel matrix requires calculating the inner products between (pairs of) data points (and hence sharing data). This paper proposes an approach for approximately calculating the kernel matrix and uses that for spectral clustering. The convergence of the proposed algorithm is studied. The authors also provided recovery results in the Gaussian kernel setting under certain assumptions. The reviewers had some initial concerns about the experiments section and setup. These concerns are addressed in the rebuttal period and hence I recommend acceptance of the manuscript.
Decision: Accept (poster)