# Privacy-Preserving Community Detection for Locally Distributed Multiple
Networks††thanks: Xiangyu Chang and Shujie Ma are joint corresponding authors.

Xiao Guo
School of Mathematics, Northwest University
Xiang Li
School of Mathematical Sciences, Peking University
Xiangyu Chang
School of Management, Xi’an Jiaotong University
Shujie Ma
Department of Statistics, University of California, Riverside

###### Abstract

Modern multi-layer networks are commonly stored and analyzed in a local and
distributed fashion because of the privacy, ownership, and communication
costs. The literature on the model-based statistical methods for community
detection based on these data is still limited. This paper proposes a new
method for consensus community detection and estimation in a multi-layer
stochastic block model using locally stored and computed network data with
privacy protection. A novel algorithm named privacy-preserving Distributed
Spectral Clustering (ppDSC) is developed. To preserve the edges’ privacy, we
adopt the _randomized response_ (RR) mechanism to perturb the network edges,
which satisfies the strong notion of _differential privacy_. The ppDSC
algorithm is performed on the squared RR-perturbed adjacency matrices to
prevent possible cancellation of communities among different layers. To remove
the bias incurred by RR and the squared network matrices, we develop a two-
step bias-adjustment procedure. Then we perform eigen-decomposition on the
debiased matrices, aggregation of the local eigenvectors using an orthogonal
Procrustes transformation, and $k$-means clustering. We provide theoretical
analysis on the statistical errors of ppDSC in terms of eigen-vector
estimation. In addition, the blessings and curses of network heterogeneity are
well-explained by our bounds.

Keywords: Multi-layer stochastic block model, Distributed SVD, Bias-
correction, Differential privacy

##  1 Introduction

Advances in modern technology have facilitated the collection of multiple
network data from various sources (e.g., Facebook, LinkedIn, and Twitter) that
present disparate social ties (Kairouz et al., 2021). This data type can be
well represented by multi-layer networks (Mucha et al., 2010; Boccaletti et
al., 2014; Kivelä et al., 2014; Han et al., 2015), in which the nodes are the
entities of interest, and the network layers reflect their relationships
across different sources. As a result, the study of multi-layer networks has
received remarkable attention recently. Most existing works assume that all
network layers are stored in a single central machine, see, e.g., Paul and
Chen (2016); Bhattacharyya and Chatterjee (2018); Liu et al. (2018); Paul and
Chen (2020); Lei et al. (2020); Arroyo et al. (2021); MacDonald et al. (2022);
Lei and Lin (2022); Huang et al. (2022). However, in practice, the multi-layer
network is often locally stored because of the private ownership and the
communication cost among others (Dwork et al., 2014; Kairouz et al., 2021).
For example, consider a multi-layer friendship network obtained from different
social platforms, where the nodes are the common users of these platforms, and
the layers correspond to different social ties. In this network, neither the
users would like others to know what kind of users they are following
completely, nor are the platforms willing to share all the network information
because of the ownership. Thus, aggregating all network layers into one
central machine would be rather difficult in this scenario. To this end, the
analysis of the multi-layer networks should be naturally based on a
distributed and federated architecture.

In the literature, the multi-layer stochastic block model (multi-layer SBM)
(Han et al., 2015; Paul and Chen, 2016; Barbillon et al., 2017) has been
popularly used for community detection in multi-layer networks, in which each
layer is assumed to share the same unobserved community membership (Greene and
Cunningham, 2013; Liu et al., 2013). There are two major methodological
challenges to apply the multi-layer SBM for locally stored networks with
privacy-preserving constraints. First, because of the _privacy budget_ , the
_randomized response_ (RR) mechanism (Warner, 1965; Karwa et al., 2017; Ayed
et al., 2020) that simply flips all edges in the network with a certain
probability is often adopted to achieve _differential privacy_ (DP) (Dwork et
al., 2006, 2014; Mironov, 2017; Dong et al., 2022; Bi and Shen, 2022).
Although this method can greatly protect an individual’s privacy by ensuring
that no individual significantly influences the algorithm’s output, the RR
mechanism would bring bias into the multi-layer SBM. The existing community
detection methods (e.g., Paul and Chen (2020); Arroyo et al. (2021); Lei and
Lin (2022); Huang et al. (2022)) proposed for the exact multi-layer SBMs
cannot be directly applied in this scenario. Therefore, a bias-correction
procedure is needed for community detection and estimation in the composite
and RR-perturbed multi-layer SBM.

Second, directly sending the RR-perturbed networks, either with or without
bias-correction on the local machines to the central server, can bring large
communication cost or storage cost on the server, especially for large
networks. When the bias-correction is achieved on the local machines, the
networks become dense; when it is performed on the central server, it needs to
preserve all networks. Moreover, sending non-debiased sparse networks can be
also communication expensive when the network is large. Therefore, a
communication-efficient algorithm is of importance in our considered setting.

Motivated by the above problems, we propose a privacy-preserving Distributed
Spectral Clustering (ppDSC) algorithm for detecting the communities of locally
stored multi-layer networks with private preserving. To avoid possible
cancellation of the communities among different layers, we adopt the _squared_
adjacency matrix (Lei and Lin, 2022) as the input of ppDSC. Our proposed
algorithm consists of four steps given below.

  * •

Step 1: we conduct RR on the network located in each local machine to achieve
DP.

  * •

Step 2: we perform bias-correction on each local RR-perturbed network and then
obtain a bias-corrected network on each machine.

  * •

Step 3: we perform eigen-decomposition on each bias-corrected network and send
the top-eigenvectors of each network to the central server. Due to the
orthogonal ambiguity of subspaces, we average the _orthogonal transformed_
local eigenvectors using the _orthogonal Procrustes transformation_ (OPT)
(Schönemann, 1966; Cape, 2020; Charisopoulos et al., 2021) on the central
server. This method ensures that the transformed local eigen-vectors are
aligned with each other.

  * •

Step 4: we implement $k$-means clustering on the orthogonalized vector on the
central server to obtain the estimated communities.

We provide rigorous non-asymptotic analysis of the statistical errors of ppDSC
in terms of eigen-vector estimation and clustering. It turns out that both
errors consist of three parts: the _squared_ local, heterogeneity-induced and
centralized errors. The privacy effect is inherent in the first and third
parts.

###  1.1 Our contributions and related work

The contribution of this paper is multi-fold, summarized as follows.

First, we propose a novel community detection method for multiple networks
collected from different sources with privacy concerns. Our algorithm
satisfies the strong notion of DP. For network data, two notions of DP are
often used (Rastogi et al., 2009); one is _edge_ -DP, considered in our paper;
the other one is _node_ -DP, which conceals the inclusion or removal of a
particular node with all its adjacent edges. Under the framework of these two
notions, DP algorithms have been developed for several problems, including
graph statistics releasing (Nissim et al., 2007; Karwa et al., 2011; Imola et
al., 2021), synthetic graphs releasing (Qin et al., 2017), and generative
graph models estimation (Mir and Wright, 2012; Borgs et al., 2015; Karwa and
Slavković, 2016; Chang et al., 2021), among others. However, there are few
studies on privacy-preserving community detection using statistical models,
e.g., Nguyen et al. (2016); Ji et al. (2019); Hehir et al. (2021); Seif et al.
(2022). In particular, to the best of our knowledge, privacy-preserving
community detection for multi-layer networks has not been studied yet.

Second, we develop a bias-correction procedure to remove the bias brought by
RR in the multi-layer SBM, and theoretically investigate the effect of the
bias-correction on community detection. The previous works focused on deriving
the information-theoretical limits (Seif et al., 2022) and misclassification
rate of community detection in bias-corrected RR-perturbed SBMs (Hehir et al.,
2021). However, how the bias-correction procedure can affect the clustering
and estimation accuracy is still unclear, which is studied in our paper
through rigorous theoretical justification.

Third, we develop a communication-efficient algorithm, ppDSC, by which we only
need to send the top eigenvectors from the local machines to the central
server. The method is inspired by the distributed PCA proposed for other
scenarios in the divide-and-conquer paradigm (Fan et al., 2019; Bhaskara and
Wijewardena, 2019; Charisopoulos et al., 2021) and iterative paradigm (Garber
et al., 2017; Gang et al., 2019; Chen et al., 2021a; Li et al., 2021; Guo et
al., 2021). However, we incorporate the perturbation and bias-correction
procedure in our algorithm; as a result, it poses great challenges to derive
the theories, including the estimation error bounds.

Last but not least, we provide a series of novel bounds and explicitly show
how the bounds depend on the privacy parameters. These theoretical results
have not yet been established. In the special case without the privacy and
local computation demand, the error bounds of our algorithm reduce to that
given in Lei and Lin (2022). The bounds also review the effect of RR on
community detection. In particular, adding more network edges can lead to
larger error bounds than removing edges. Our established bounds can also help
to explain the blessings and curses of heterogeneity among the local networks.

###  1.2 Organizations

The rest of the paper is organized as follows. Section 2 introduces the
preliminaries of the model and DP. Section 3 develops the algorithm for
privacy-preserving community detection of locally stored networks. Section 4
studies the theoretical properties of ppDSC. Section 5 and 6 include the
simulation and real data experiments. Section 7 concludes the paper.

##  2 Problem formulation

In this section, we first present the multi-layer SBMs for modeling the
locally stored networks. Next, we introduce the DP and the RR mechanism for
privacy protection.

###  2.1 The model for locally stored networks

Suppose that $L$ aligned networks with $n$ common nodes are locally stored in
$L$ machines, respectively. The networks are binary and symmetric with the
adjacency matrix denoted by $A_{l}\in\\{0,1\\}^{n\times n},l=1,...,L$. We
consider the scenario that $A_{l}$’s share common communities but with
possibly different edge densities.

To model the above locally stored networks, we assume that $A_{l}$’s are
independently generated from the following multi-layer SBMs. The $n$ nodes are
assigned to $K$ non-overlapping communities with the community assignment of
node $i$ denoted by $g_{i}\in\\{1,...,K\\}$. Given the community assignments,
each entry $A_{l,ij}(i<j)$ of $A_{l}$ is generated independently according to

$A_{l,ij}\sim{\mathrm{Bernoulli}}(B_{l,g_{i}g_{j}}),\quad i<j,\;l=1,...,L,$
(1)

where $B_{l}$’s are link probability matrices, and the diagonal entries
$A_{l,ii}$’s are all 0. The heterogeneity among the networks is inherent in
$B_{l}$’s, and we will quantify it in the next section. Note that we assume
that $A_{l}$’s are generated locally at the machine $L$’s.

Model (1) is the multi-layer SBMs studied in Han et al. (2015); Paul and Chen
(2016) and so forth. When the adjacency matrices $A_{l}$’s are generated and
stored in the local machines, we consider DP and the RR mechanism for the
adjacency matrices for private protection.

###  2.2 Differential privacy and randomized response

Though the local networks $A_{l}$’s are not directly shared by all the local
machines, potential privacy breaches still exist (Dwork et al., 2017). DP
provides a rigorous framework for privacy-preserving data analysis (Dwork et
al., 2006). Generally, a DP algorithm pursues that its output appears similar
in probability if one individual changes the input data. By definition, DP
protects any individual’s privacy from an adversary who has access to the
algorithm output and even sometimes the rest of the data. In addition, it can
prevent other kind of attacks, say, the re-identification attack, the tracing
attack, and the membership attack, among others; see Dwork et al. (2017) for a
survey. In the context of networks, we consider the following notion of edge-
DP (Rastogi et al., 2009; Karwa et al., 2017).

######  Definition 1 (Edge-DP)

Let $A\in\\{0,1\\}^{n\times n}$ be the network whose edges are sensitive. For
any range $\mathcal{R}$, let $\mathcal{Q}(A)\in\mathcal{R}$ be a randomized
mechanism that generates some synthetic information from $A$, indicated by a
known parameter $\omega$. Then, $\mathcal{Q}(A)$ is said to be
$\epsilon$-edge-DP if

$\underset{{\tilde{A}}\in\mathcal{R}}{\max}\,\underset{A^{\prime},A,\,\Delta(A,A^{\prime})=1}{\max}\;\log\frac{\mathbb{P}_{\omega}(\mathcal{Q}(A)={\tilde{A}}\,|\,A)}{\mathbb{P}_{\omega}(\mathcal{Q}(A^{\prime})={\tilde{A}}\,|\,A^{\prime})}\leq\epsilon,$
(2)

where $\Delta(A,A^{\prime})=1$ means that $A$ and $A^{\prime}$ are neighboring
by differing only one edge.

###### Remark 1

We make the following remarks on the DP.

Edge-DP protects the privacy of network edges by ensuring that the algorithm’s
output does not reveal the inclusion or removal of any certain edge in the
network. In other words, edge-DP can protect against an adversary who knows
the algorithm’s output and the existence or not of edges between all pairs but
one pair of nodes.

The $\epsilon$ is often termed as the privacy budget. A smaller privacy budget
indicates stronger protection of privacy. Note that DP is the worst-case
definition, and the randomness in (2) only comes from the DP mechanism
$\mathcal{Q}$.

Like the general DP, edge-DP enjoys the post-processing property (Dwork et
al., 2014), that is, an $\epsilon$-edge-DP algorithm is still $\epsilon$-edge-
DP after any post process that does not use the knowledge about the original
network.

Edge-DP could be achieved by flipping the network edges with certain
probabilities, which is called the randomized response (RR) mechanism (Warner,
1965; Karwa et al., 2017; Ayed et al., 2020). The algorithm outputs a
perturbed adjacency matrix $\tilde{A}$ of $A$. Specifically, for each $i<j$,
when $A_{ij}=1$, $\tilde{A}_{ij}$ keeps to be 1 with probability $q$ and flips
to 0 otherwise. Similarly, when $A_{ij}=0$, ${\tilde{A}}_{ij}$ remains to be 0
with probability $q^{\prime}$ and changes to 1 otherwise. The diagonal entries
${\tilde{A}}_{ii}=0$. Note that $q$ and $q^{\prime}$ can be published
publicly. The relationship between $q,q^{\prime}$ and the privacy budget
$\epsilon$ is shown in the following proposition.

######  Proposition 1 (Karwa et al. (2017))

The randomized response mechanism satisfies $\epsilon$-edge-DP with

$\epsilon\geq\log\max\left\\{\frac{q^{\prime}}{1-q},\frac{1-q}{q^{\prime}},\frac{1-q^{\prime}}{q},\frac{q}{1-q^{\prime}}\right\\}.$
(3)

According to (3), a typical choice of $q$ and $q^{\prime}$ is that

$q=q^{\prime}=\frac{\mathrm{e}^{\epsilon}}{1+\mathrm{e}^{\epsilon}},$ (4)

which has been proven to be optimal in maximizing the mutual information
between raw and RR-perturbed data (Ayed et al., 2020).

Although RR can achieve edge-DP, one can imagine that the resulting network
largely deviates from the original network. In the next section, we will see
how we can debias the perturbed networks so as to improve the algorithm’s
utility under the multi-layer SBMs.

##  3 Privacy-preserving community detection for locally distributed networks

This section proposes the privacy-preserving community detection algorithm for
locally distributed networks. Before that, we specify the centralized
estimator and develop a bias-adjustment procedure to remove the bias inherent
in the RR-perturbed networks.

_Notes and notation_. We use $\lambda_{\min}(A)$ to denote the smallest non-
zero eigenvalue of a given matrix $A$. Moreover, we use the projection
distance
$\mathrm{dist}(U,U^{\prime}):=\|UU^{\intercal}-U^{\prime}U^{\prime{\intercal}}\|_{2}$
to measure the subspace distance between any pair of orthogonal basis
$U,U^{\prime}\in\mathbb{R}^{n\times K}$. $\|A\|_{2}$ denotes the spectral norm
of matrix $A$ or the Euclidian norm of vector $A$ and $\|A\|_{\tiny F}$ denote
the Frobenius norm of matrix $A$. In addition, we use the following standard
notation for asymptotics. We write $f(n)\asymp g(n)$ or $f(n)=\Theta(g(n))$ if
$cg(n)\leq f(n)\leq Cg(n)$ for some constants $0<c<C<\infty$, $f(n)\lesssim
g(n)$ or $f(n)=O(g(n))$ if $f(n)\leq Cg(n)$ for some constant $C<\infty$, and
$f(n)\gtrsim g(n)$ or $f(n)=\Omega(g(n))$ if $f(n)\geq cg(n)$ for some
constant $c>0$. Finally, the constants throughout this work may be different
from place to place.

Recall that there are $L$ local machines, with each owning a symmetric binary
network adjacency matrix $A_{l},l=1,...,L$. $A_{l}$’s are assumed to be
generated from a multi-layer SBM. Denote the population of $A_{l}$ by
$P_{l}:=\Theta B_{l}\Theta^{\intercal}$, where $\Theta\in\mathbb{R}^{n\times
K}$ is the membership matrix which is formed by forcing $\Theta_{ig_{i}}=1$
and $\Theta_{ij}=0$ for $j\neq g_{i}$. We aim to recover the common membership
matrix $\Theta$ using the network information.

Without the privacy constraint, a common centralized approach is to perform
community detection algorithms on $\sum_{l}A_{l}$ (Bhattacharyya and
Chatterjee, 2018; Paul and Chen, 2020). However, direct summation of $A_{l}$’s
would lead to information loss when $A_{l}$’s are heterogeneous in the sense
of community pattern. In other words, if some $P_{l}$’s are positive
semidefinite, which present homophily social ties and others are negative
semidefinite, which indicate heterophily social ties (Kim and Leskovec, 2012),
then adding them up would cancel out some community signals. To alleviate
this, we consider the matrix

$M:=\frac{1}{Ln}\sum_{l=1}^{L}A_{l}^{2}$ (5)

studied in Lei and Lin (2022), which could accommodate different community
patterns. Note that Lei and Lin (2022) further developed a bias-correction
procedure to modify the diagonal elements of $M$. The centralized estimator is
then obtained by performing spectral clustering on $M$. Specifically, the
eigen-decomposition is first computed on $M$ to obtain the first $K$
eigenvectors, and then $k$-means is conducted on the resulting eigenvectors to
obtain $K$ communities. Hopefully, $M$ can approximate its population
counterpart

${Q}:=\frac{1}{L}\sum_{l=1}^{L}\frac{P_{l}^{2}}{n}:=\frac{1}{L}\sum_{l=1}^{L}{Q}_{l},$
(6)

whose eigenvector reveals the true communities in the sense that two rows of
the eigenvector matrix are identical if and only if the corresponding nodes
are in the same underlying communities (Rohe et al., 2011; Lei and Rinaldo,
2015; Zhang et al., 2022).

However, with the privacy constraint, we could only use the RR-perturbed
adjacency matrix instead of $A_{l}$ in (5), which is a biased estimator of
$P_{l}$. In the next subsection, we will develop a bias-adjustment procedure
to obtain a good estimator for $Q$.

###  3.1 Bias-adjustment

Our debiasing procedure involves two steps: in step 1, we build a debiased
estimator for the link probability matrix upon the RR-perturbed adjacency
matrix stored in each local machine; in step 2, we further remove the bias of
the diagonals caused by taking the square of the debiased estimated matrix
obtained in step 1.

Step 1. We now illustrate the necessity of bias-adjustment when dealing with
RR-perturbed data.

For $1\leq l\leq L$, we denote the RR-perturbed $A_{l}$ by ${\tilde{A}}_{l}$.
Specifically, for $i<j$, if $A_{l,ij}=1$,

${\tilde{A}}_{l,ij}=\begin{cases}1,\quad\mathrm{with\,probability}\,q,\\\
0,\quad\mathrm{otherwise},\end{cases}$ (7)

and ${\tilde{A}}_{l,ji}={\tilde{A}}_{l,ij}$. On the other hand, if
$A_{l,ij}=0$,

${\tilde{A}}_{l,ij}=\begin{cases}1,\quad\mathrm{with\,probability}\,1-q^{\prime},\\\
0,\quad\mathrm{otherwise},\end{cases}$ (8)

and ${\tilde{A}}_{l,ji}={\tilde{A}}_{l,ij}$. By (7) and (8) and taking
expectations for two times, we have

$\mathbb{E}({\tilde{A}}_{l,ij})=P_{l,ij}(q+q^{\prime}-1)+1-q^{\prime},$

which is biased from the true expectation $P_{l,ij}$ of $A_{l,ij}$. Therefore,
for $i\neq j$, the local machine only needs to debias ${\tilde{A}}_{l,ij}$ to
be

$\overline{A}_{l,ij}=\frac{{\tilde{A}}_{l,ij}-(1-q^{\prime})}{q+q^{\prime}-1}.$

We thus obtain the following debiased estimator $\overline{A}_{l}$ for
$P_{l}$,

$\overline{A}_{l}:=[{\tilde{A}}_{l}-(1-q^{\prime})\mathbf{1}\mathbf{1}^{\intercal}+\mathrm{diag}(1-q^{\prime})]/(q+q^{\prime}-1),$
(9)

where $\mathbf{1}$ denotes the vector with all entries being 1.

Step 2. Though $\overline{A}_{l}$ is the unbiased estimator for $P_{l}$, the
diagonal elements of $\overline{A}_{l}^{2}$ can cause bias for $P_{l}^{2}$. It
turns out that the error would be smaller if we further subtract
$\frac{\sum_{j}{\tilde{A}}_{l,ij}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}$ from
the $i$th diagonal elements of $\overline{A}_{l}^{2}$ provided that
$\max_{i,j,l}P_{l,ij}=o(1)$. In particular, this debiasing step is crucial
when $L$ is increasing. For the sake of saving space, the details are
relegated to Appendix A.

Combining the two steps of debiasing, we eventually obtain the following
estimator $\overline{M}$ for $Q$ defined in (6),

$\overline{M}:=\frac{1}{L}\sum_{l=1}^{L}\overline{M}_{l}$ (10)

with

$\overline{M}_{l}:=\frac{\overline{A}_{l}^{2}}{n}-\frac{(q^{\prime})^{2}}{n(q+q^{\prime}-1)^{2}}G_{l},$
(11)

where $G_{l}$ is a diagonal matrix with $G_{l,ii}=\sum_{j}{\tilde{A}}_{l,ij}$,
and $\overline{A_{l}}$ and ${\tilde{A}}_{l}$ are defined in (7)-(9). Note that
the second step of debiasing is in a similar spirit of Lei and Lin (2022)
except that their debiasing is performed on the original network matrix, while
ours is on the debiased RR-perturbed network matrix.

Therefore, with the privacy constraint, the ideal centralized estimator is to
perform spectral clustering on the debiased estimator $\overline{M}$. Noting
that $\overline{M}_{l}$’s are separable across different local machines. We
show in the next subsection how we can approximate the eigenvector of
$\overline{M}$ with the local computation.

###  3.2 Privacy-preserving distributed spectral clustering

Since DP enjoys the post-processing property, in principle, the local machines
can send the dense debiased estimators $\overline{M}_{l}$’s to the central
server where the spectral clustering is further performed on the aggregated
matrix $\overline{M}$. However, both the communication and computational cost
can be very high for sending the whole dense matrices $\overline{M}_{l}$’s and
performing the aggregation of these matrices on the central server, especially
when the matrix dimensions are large. Instead, we consider a more efficient
distributed algorithm described as follows.

We adopt the one-shot averaging framework in Charisopoulos et al. (2021) for
distributed computing performed on our debiased RR-perturbed network matrices.
That is, on the $l$th machine, we first compute the eigen-decomposition of
$\overline{M}_{l}$, and obtain the matrix $\hat{V}_{l}\in\mathbb{R}^{n\times
K}$ that consists of the first $K$ eigenvectors, for all $l=1,...,L$. On the
central server, we average all the local solutions. Note that direct averaging
is inferior due to the orthogonal ambiguity of the problem, i.e., for any
orthogonal matrix $Z$, $\hat{V}_{l}Z$ also forms a valid orthonormal basis of
the subspaces formed by $\hat{V}_{l}$. Hence, $\hat{V}_{l}$’s are not
guaranteed to be close to each other, even if their corresponding subspaces
are close. In light of this, the local $\hat{V}_{l}$’s must be aligned with
each other before averaging.

To avoid the orthogonal ambiguity of the problem, we use the _Procrustes
fixing_ strategy (Schönemann, 1966; Cape, 2020; Charisopoulos et al., 2021;
Guo et al., 2021). For two matrices $V_{1},V_{2}$ to be aligned, we can map
$V_{2}$ to $V_{1}$ using an orthogonal transformation solved by the following
optimization,

$Z:=\operatorname{arg\,min}_{Z\in\mathcal{O}_{K}}\|V_{1}-V_{2}Z\|_{F},$ (12)

where $\mathcal{O}_{k}$ denotes the set of $K\times K$ orthogonal matrices.
Note that (12) has a closed-form solution. Let the SVD of
$V_{2}^{\intercal}V_{1}$ be $LDR^{\intercal}$, then $Z:=LR^{\intercal}$ is the
solution to (12). In such a way, we can align local eigenspaces $\hat{V}_{l}$
to an arbitrarily chosen reference eigenspace, for example, $\hat{V}_{o}$,
after which the aligned eigenspaces can then be averaged and orthogonalized.

The proposed privacy-preserving Distributed Spectral Clustering (ppDSC)
algorithm is summarized in Algorithm 1. It should be noted that, in a real
scenario, the computation on the local machine may be fulfilled by a single
party or cooperated by different parties. For example, a party with data
ownership may desire to obtain good utility while preserving the data’s
privacy. Thus all the local steps are conducted within the party. It can also
happen that the RR perturbation is conducted by the data collection department
of a company, while the data analysis department could do the remaining bias-
correction and eigen-decomposition steps.

Algorithm 1 can achieve strong privacy protection in the DP’s framework.

###### Theorem 1

Define $A_{\mathrm{all}}:=(A_{1},...,A_{L})$. Denote the output of Algorithm 1
by $\mathcal{M}\in\mathcal{R}$. For $\epsilon$ satisfies (3), Algorithm 1 is
$\epsilon$-edge-DP in the following sense

$\underset{\mathcal{M}\in\mathcal{R}}{\max}\,\underset{A_{\mathrm{all}},A_{\mathrm{all}}^{\prime},\
\Delta(A_{\mathrm{all}},A_{\mathrm{all}}^{\prime})=1}{\max}\;\log\frac{\mathbb{P}(\mathcal{M}(A_{\mathrm{all}})\,|\,A_{\mathrm{all}})}{\mathbb{P}(\mathcal{M}(A_{\mathrm{all}}^{\prime})\,|\,A_{\mathrm{all}}^{\prime})}\leq\epsilon,$

where $\Delta(A_{\mathrm{all}},A_{\mathrm{all}}^{\prime})=1$ means that all
layers of the multi-layer network pairs $A_{\mathrm{all}}$ and
$A_{\mathrm{all}}^{\prime}$ are equal except one edge of one layer.

Algorithm 1 Privacy-preserving distributed spectral clustering (ppDSC)

1: Input: Network adjacency matrices $\\{A_{l}\\}_{l=1}^{L}$ owned by local
machines, number of clusters $K$, privacy parameters $q,q^{\prime}$, index of
reference solution $o$.

2: The local machines do:

3: for $l=1$ to $L$ do

4: RR-perturbation: Perturb $A_{l}$ to obtain ${\tilde{A}}_{l}$ using (7) and
(8);

5: Bias-correction: Constructs the debiased estimator $\overline{M}_{l}$
according to (11);

6: Eigen-decomposition: Performs eigen-decomposition on $\overline{M}_{l}$ and
denote the resulting eigen-spaces as $\hat{V}_{l}$.

7: end for

8: The central server does:

9: Procrustes fixing: $\tilde{V}_{l}:=\hat{V}_{l}Z_{l}$ with
$Z_{l}:=\operatorname{arg\,min}_{Z\in\mathcal{O}_{K}}\|\hat{V}_{l}Z-\hat{V}_{o}\|_{F}$
for each $l=1,...,L$;

10: Aggregation: Aggregates the local solutions according to
$\bar{V}:=\frac{1}{L}\sum_{l=1}^{L}\tilde{V}_{l}$;

11: Orthogonalization: Performs the QR decomposition to obtain
$\tilde{V},\tilde{R}={\rm qr}(\bar{V})$.

12: Clustering: Conduct $k$-means clustering on $\tilde{V}$ with cluster
number being $K$. The resulting clusters are formulated by the membership
matrix $\tilde{\Theta}$.

13: Output: The approximated eigen-space $\tilde{V}$ and the estimated
membership matrix $\tilde{\Theta}$.

##  4 Theoretical analysis

In this section, we theoretically study the ppDSC algorithm in terms of the
estimation accuracy of the eigenvectors and the misclassification rate.

To fix the ideas, we now recall and introduce some notations. We assume that
there are $L$ local networks whose adjacency matrices
$A_{l}\in\\{0,1\\}^{n\times n}$’s are generated from SBMs with layer-specific
link probability matrices $B_{l}$’s and a consensus membership matrix
$\Theta\in\mathbb{R}^{n\times K}$. We here assume that the number of
communities $K$ is known. When $K$ is unknown, we will investigate the method
and theory for the estimation of $K$, which is a model selection problem, as a
future research topic, as this current work focuses on estimation and
clustering analysis for a given model based on RR-perturbed network matrices.
The number of nodes within community $k$ is denoted by $n_{k}$. The privacy
parameters are denoted by $q,q^{\prime}$ ($1/2<q,q^{\prime}\leq 1$); see also
(7) and (8). Our goal is to use ppDSC (Algorithm 1) to recover the first $K$
eigenvectors $V$ of the underlying target matrix $Q$ defined in (6) and the
membership matrix $\Theta$.

The following assumptions are generally required to derive the theoretical
results for community detection.

######  Assumption 1 (Balanced communities)

The community is balanced such that for any $k\in\\{1,...,K\\}$,

$c\frac{n}{K}\leq n_{k}\leq C\frac{n}{K},$

for some constants $0\leq c\leq C$.

######  Assumption 2 (Sparsity)

The link probability matrix $B_{l}=\rho B_{l,0}$, where $\rho=o(1)$ and
$B_{l,0}$ is a $K\times K$ symmetric matrix with constant entries in $[0,1]$.

######  Assumption 3 (Full rank)

$\sum_{l}B_{l,0}^{2}$ is of full rank $K$ with
$\lambda_{{\min}}(\sum_{l}B_{l,0}^{2})\geq cL$.

######  Assumption 4 (Limited heterogeneity)

The heterogeneity among the link probability matrices $B_{l}$’s are limited as

$\max_{l}\|B_{l}\Delta^{2}B_{l}-\frac{1}{L}\sum_{l=1}^{L}B_{l}\Delta^{2}B_{l}\|_{2}\leq\mathcal{H}(n,\rho,L).$

with $\Delta:={\operatorname{diag}}(\sqrt{n_{1}},...,\sqrt{n_{K}})$.

###### Remark 2

Assumption 1 requires that the communities are balanced. Assumption 2
specifies the link probability matrices. In particular, we require that the
network sparsity $\rho=o(1)$. Assumption 3 requires the linear growth of the
aggregated squared link probability matrices in terms of its minimum
eigenvalue, which is trivially satisfied when $B_{l,0}$’s are equal and is
also used in Lei and Lin (2022). Assumption 3 combining with Assumptions 2 and
1 implies that $\sum_{l=1}^{L}B_{l}\Delta^{2}B_{l}$ is of full rank, and $Q$
is of rank $K$; see the proof of Corollary 1. Indeed, the full rank
requirement could be extended to the rank-deficient case; see Zhang et al.
(2022) for example. Assumption 4 bounds the maximum deviation of
$B_{l}\Delta^{2}B_{l}$’s from its average by $\mathcal{H}(n,\rho,L)$. For
simplicity, we call $\mathcal{H}$ the measure for the heterogeneity of locally
stored networks.

We first provide the following error decomposition theorem to present the
general error bound for the output eigen-space of ppDSC.

######  Theorem 2 (Error Decomposition)

Suppose Assumptions 1 and 4 hold, the output $\tilde{V}$ of Algorithm 1
satisfies

$\mathrm{dist}(\tilde{V},V)\lesssim{\max_{l}\frac{\|\overline{M}_{l}-Q_{l}\|_{2}^{2}}{\lambda_{{\min}}^{2}(Q)}}+{\frac{\mathcal{H}^{2}(n,\rho,L)}{\lambda_{{\min}}^{2}(Q)}}+\frac{\|\sum_{l}\overline{M}_{l}/L-Q\|_{2}}{\lambda_{{\min}}(Q)}:=\mathcal{I}_{1}+\mathcal{I}_{2}+\mathcal{I}_{3}.$

provided that both $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are smaller than a
small constant $c$.

###### Remark 3

The condition that $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are smaller than a
small constant $c$ is a standard condition (Damle and Sun, 2020; Charisopoulos
et al., 2021); it ensures that the maximum local error
$\max\|\overline{M}_{l}-Q\|_{2}$ is smaller than the eigen-gap
$\lambda_{{\min}}(Q)$, which further indicates that the $K$-largest
eigenvalues of $\overline{M}_{l}$ are separated from its remaining eigenvalues
by Weyl’s inequality. In Corollary 1, we show that this condition is satisfied
by our setting under mild conditions and further provide the explicit
expressions for $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$.

The decomposed three components
$\mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3}$ are explained as follows.
$\mathcal{I}_{1}$ corresponds to the maximum squared error of the local
estimators $\hat{V}_{l}$’s except that we use $Q$ in the denominator instead
of $Q_{l}$; see the Davis-Kahan theorem on the perturbation of eigenvectors
(Davis and Kahan (1970); see Lemma 3 in the Appendix). As a result, we only
require the averaged population matrix $Q:=\sum Q_{l}/L$ be of rank $K$, and
the local population matrix $Q_{l}$ can be rank deficient, which is one of the
benefits of combining the local eigenvectors. $\mathcal{I}_{2}$ corresponds to
the degree of heterogeneity. To distinguish, we call $\mathcal{H}$ the measure
for heterogeneity and call $\mathcal{I}_{2}$ the measure for _scaled
heterogeneity_. It is worth noting that the scaled heterogeneity
$\mathcal{I}_{2}$ affects the theoretical accuracy of $\tilde{V}$ according to
its magnitude compared to $\mathcal{I}_{1}$ and $\mathcal{I}_{3}$. Moreover,
$\mathcal{I}_{3}$ corresponds to the error of the centralized estimator
$\hat{V}:=\frac{1}{L}\sum_{l}\overline{M}_{l}$. $\mathcal{I}_{1}$ and
$\mathcal{I}_{2}$ can be regarded as the price needed to pay for the
distributed computation.

One of the contributions in Theorem 2 is that it explicitly explains how the
heterogeneity $\mathcal{H}$’s effect could be a curse or blessing to
$\mathcal{I}_{2}$ and possibly the final error bound. Note that $\mathcal{H}$
and $\lambda_{{\min}}(Q)$ jointly decide $\mathcal{I}_{2}$. Therefore, if the
local $B_{l}$’s are noisy from the signal such that combining them could hide
the true signal, i.e., $\mathcal{H}$ is large, and $\lambda_{{\min}}(Q)$ is
small, then the heterogeneity would be a curse. On the other hand, if the
local $B_{l}$’s are far from the signal but combining them would enhance the
signal, i.e., $\mathcal{H}$ is large, but $\lambda_{{\min}}(Q)$ can also be
large such that their ratio is small, then the heterogeneity would be a
blessing. We refer to the two simulated examples in Appendix C for more
illustrations on the aforementioned phenomena.

To make the bounds in Theorem 2 more specific, in the following we provide
Theorem 3 which establishes the estimation bounds of
$\|\sum_{l}\overline{M}_{l}/L-Q\|_{2}$. Note that we assume that the privacy
parameters $q,q^{\prime}$ relate to the privacy budget $\epsilon$ via (4). For
illustration, we interchange the use of $q,q^{\prime}$, and $\epsilon$. Note
that our results also hold for
$q=\frac{\mathrm{e}^{\epsilon_{1}}}{1+\mathrm{e}^{\epsilon_{1}}}$ and
$q^{\prime}=\frac{\mathrm{e}^{\epsilon_{2}}}{1+\mathrm{e}^{\epsilon_{2}}}$
with $\epsilon:=\max\\{\epsilon_{1},\epsilon_{2}\\}$ and $\epsilon_{1}$ and
$\epsilon_{2}$ being of the same order.

###### Theorem 3

Suppose Assumption 2 holds, and

$\epsilon\leq\alpha_{1}\cdot{\log}\,n\quad{and}\quad\log(L+n)\leq
n^{\alpha_{2}}$ (13)

for some constants $0<\alpha_{1}<1$ and $0<\alpha_{2}\leq 1-\alpha_{1}$, the
estimator $\overline{M}:=\frac{1}{L}\sum_{l}\overline{M}_{l}$ of $Q$ satisfies

$\displaystyle\small\|\overline{M}-Q\|_{2}\leq C\max$
$\displaystyle\bigg{\\{}\frac{(q\rho+1-q^{\prime})^{1/2}n^{1/2}\rho\log^{1/2}(L+n)}{(q+q^{\prime}-1)\sqrt{L}},$
$\displaystyle\quad\quad\quad\frac{(q\rho+1-q^{\prime})\log(L+n)}{(q+q^{\prime}-1)^{2}\sqrt{L}},\,\frac{((q+q^{\prime}-1)\rho+1-q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}\bigg{\\}},$
(14)

with probability larger than $1-O((L+n)^{-\nu})$ for some constant $\nu>0$.

Theorem 3 provides the error bound for the centralized estimator
$\sum_{l}\overline{M}_{l}/L$. The RHS of (3) indicates that the privacy
parameters $q$ and $q^{\prime}$ affect the accuracy of the estimated
eigenvectors. In addition, the influence of $q$ and $q^{\prime}$ on the final
bound is not equivalent.

First, we observe that the privacy parameters $q,q^{\prime}$ appear in the
numerators of the first two terms of (3) in the form $q\rho+1-q^{\prime}$.
Considering that $\rho=o(1)$, we can see that a large level of $q^{\prime}$ is
more desirable than a large level of $q$ for reducing the estimated error (3).
In other words, perturbing 0 to 1 is more harmful than perturbing 1 to 0 for
the model estimation. Second, when $\rho\leq
C\frac{(q\rho+1-q^{\prime})^{1/2}}{(q+q^{\prime}-1)}\cdot\frac{\log^{1/2}(L+n)}{n^{1/2}}$,
the RHS of (3) reduces to

$\max\left\\{\frac{(q\rho+1-q^{\prime})\log(L+n)}{(q+q^{\prime}-1)^{2}\sqrt{L}},\,\frac{((q+q^{\prime}-1)\rho+1-q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}\right\\},$

which matches the following bound without privacy-preserving up to log factors
derived in Lei and Lin (2022),

$\max\left\\{\frac{\rho\log^{1/2}(L+n)}{\sqrt{L}},\,\rho^{2}\right\\},$ (15)

provided that $q$ and $q^{\prime}$ both approach to 1.

The derivation of the bound for the single matrix $\overline{M}_{l}$ is
similar to that in Theorem 3. For the sake of space, we summarize the results
in Theorem B.1 in the Appendix.

Now we are ready to specify the unknown terms in Theorem 2.

###### Corollary 1

Suppose Assumptions 1-4 and condition (13) hold. If

$\rho\gtrsim\frac{(q\rho+1-q^{\prime})^{1/2}}{q+q^{\prime}-1}\cdot\sqrt{\frac{\log(n)}{n}}\quad{and}\quad\mathcal{H}\lesssim
n\rho^{2},$ (16)

then the output $\tilde{V}$ of Algorithm 1 satisfies

$\mathrm{dist}(\tilde{V},V)\lesssim\mathcal{I}_{1}+\mathcal{I}_{2}+\mathcal{I}_{3}$
(17)

with

$\mathcal{I}_{1}:=\frac{q\rho+1-q^{\prime}}{(q+q^{\prime}-1)^{2}}\cdot\frac{\log
n}{n\rho^{2}},\quad\mathcal{I}_{2}:=\frac{\mathcal{H}^{2}(n,\rho,L)}{n^{2}\rho^{4}},$
(18)

and

$\displaystyle\small\mathcal{I}_{3}:=\max$
$\displaystyle\bigg{\\{}\frac{(q\rho+1-q^{\prime})^{1/2}\log^{1/2}(L+n)}{(q+q^{\prime}-1)n^{1/2}\rho\sqrt{L}},\frac{(q\rho+1-q^{\prime})\log(L+n)}{(q+q^{\prime}-1)^{2}n\rho^{2}\sqrt{L}},\,\frac{((q+q^{\prime}-1)\rho+1-q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}n\rho^{2}}\bigg{\\}},$
(19)

with probability larger than $1-O((L+n)^{-\nu})-O(Ln^{-\nu})$ for some
constant $\nu>0$.

To make the upper bound (17) valid, $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$
both should be small enough. To this end, the technical condition (16) is
utilized to meet the requirement in Theorem 2. The results in Corollary 1 can
be simplified in various ways. For example, if we further require
$\rho\gtrsim\frac{(q\rho+1-q^{\prime})^{1/2}}{q+q^{\prime}-1}\cdot\sqrt{\frac{\log(L+n)}{n}}$,
then the first term in $\mathcal{I}_{3}$ dominate the second one. And the
bound would be further reduced to

$\frac{(q\rho+1-q^{\prime})^{1/2}\log^{1/2}(L+n)}{(q+q^{\prime}-1)n^{1/2}\rho\sqrt{L}}$
(20)

if $\mathcal{I}_{2}$ is suppressed by $\mathcal{I}_{1}$ and $\mathcal{I}_{3}$,
and
$L\lesssim\frac{(q+q^{\prime}-1)^{2}}{q\rho+1-q^{\prime}}\cdot\frac{n\rho^{2}\log(L+n)}{\log^{2}n}$.
As expected, we see in (20) that more local networks (large $L$) and less
stringent privacy-preserving demand (large $q$ and $q^{\prime}$) lead to a
smaller projection distance.

With Corollary 1 at hand, it is convenient to derive the following
misclassification error bound of ppDSC.

###### Theorem 4

Suppose the conditions in Corollary 1 all hold. Denote the set of
misclassified nodes by $\mathcal{M}$. Then, with probability larger
$1-O((L+n)^{-\nu})-O(Ln^{-\nu})$ for some constant $\nu>0$, Algorithm 1 has
misclassification rate upper bounded as

$\frac{|\mathcal{M}|}{n}\leq(\mathcal{I}_{1}+\mathcal{I}_{2}+\mathcal{I}_{3})^{2}$

with $\mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3}$ defined in (18) and
(19).

Note that the misclassification error is just the squared error of the eigen-
vectors $\tilde{V}$ in Corollary 1. Therefore, Theorem 4 can be similarly
discussed and simplified. We omit the discussion for the sake of space.

Finally, we discuss the necessity of the bias-adjustment procedure in Appendix
B. We investigate the deviation of the non-debiased matrix
$\tilde{M}:=\frac{1}{L}\sum_{l}\frac{1}{n}\tilde{A}_{l}^{2}$ from population
matrices $Q$ and
$\tilde{Q}:=\frac{1}{L}\sum_{l}\left((q+q^{\prime}-1)P_{l}+(1-q^{\prime})\textbf{1}_{n}\textbf{1}_{n}^{\intercal}\right)^{2}/{n}$,
respectively. It turns out that the bias-adjustment procedure can lead to a
smaller error of eigenvector and misclassification, no matter which population
matrix is used.

##  5 Simulations

In this section, we evaluate the finite sample performance of the proposed
algorithm. We show how the privacy parameters, the number of networks, and the
number of nodes affect the finite sample behavior of the resulting estimates.
In Appendix C, we test the effect of the heterogeneity on the performance of
the proposed algorithm.

#### Practical consideration.

To mimic the scenario considered in this work, we assume that all the
generated network datasets are private and locally distributed. To preserve
privacy, we assume that the data analyst can not use the original data
directly but can only use the _RR-perturbed_ networks. For the local
computation, we generally adopt the distributed SVD framework (Charisopoulos
et al., 2021) considered in this work.

#### Methods compared.

Our algorithm is denoted by ppDSC. We compare our algorithm, ppDSC, with the
following algorithms.

  * •

ppDSC-1b: computed according to Algorithm 1 but only with one-step bias-
correction (i.e., diagonal-debiasing) given in Lei and Lin (2022). Note that
our bias-correction for the diagonal elements is not identical to Lei and Lin
(2022);

  * •

ppDSC-2b: computed according to Algorithm 1 but without any bias-correction,
which corresponds to Charisopoulos et al. (2021);

  * •

Oracle: a centralized algorithm. It is obtained from the spectral clustering
based on the _debiased_ sum of squared RR-perturbed matrices (i.e.,
$\overline{M}$ defined in (10)). Though violating the local computation
constraint, this is used as a baseline algorithm.

#### Performance measures.

According to our theoretical analysis, we use the _projection distance_ to
measure the subspace distance between the estimated eigenvectors and the true
eigenvectors and use the _misclassification rate_ to measure the proportion of
misclassified (up to permutations) nodes.

#### Network-generation.

The local networks are generated independently from multi-layer SBMs with the
structure given in Section 3. Similar to Lei and Lin (2022), we fix $K=3$ with
balanced communities and set $B_{l}:=0.8B^{(1)}$ for $l=1,...,\lfloor
L/2\rfloor$ and $B_{l}:=0.6B^{(2)}$ for $l=\lfloor L/2\rfloor+1,...,L$ with

$\scriptsize B^{(1)}=W\begin{bmatrix}1.5&&\\\ &0.2&\\\
&&0.4\end{bmatrix}W^{\intercal}\approx\begin{bmatrix}0.62&0.22&0.46\\\
0.22&0.62&0.46\\\ 0.46&0.46&0.85\end{bmatrix},$

and

$\scriptsize B^{(2)}=W\begin{bmatrix}1.5&&\\\ &0.2&\\\
&&-0.4\end{bmatrix}W^{\intercal}\approx\begin{bmatrix}0.22&0.62&0.46\\\
0.62&0.22&0.46\\\ 0.46&0.46&0.85\end{bmatrix},$

where

$\scriptsize W=\begin{bmatrix}1/2&1/2&-\sqrt{2}/2\\\ 1/2&1/2&\sqrt{2}/2\\\
\sqrt{2}/2&-\sqrt{2}/2&0\end{bmatrix}.$

We evaluate the effect of $q,q^{\prime}$, $n$ and $L$ on the numerical
performance. The parameter set-up is as follows.

  * •

Effect of $L$: $n=210$, $q=q^{\prime}=0.9$, and $L$ ranges from 2 to 20.

  * •

Effect of $n$: $L=10$, $q=q^{\prime}=0.9$, and $n$ ranges from 15 to 300.

  * •

Effect of $q,q^{\prime}$: $L=10$, $n=210$, and $q$ and $q^{\prime}$ are equal
and range from 0.6 to 1.

#### Results.

The averaged results over 20 replications are displayed in Figure 1. We have
the following observations. First, as expected, as $q,q^{\prime}$, $n$, and
$L$ increase, the performance of all estimators improve. Second, our estimator
ppDSC is superior to the biased ppDSC-1b and ppDSC-2b except when the privacy
parameters $q,q^{\prime}$ become close to 1 and the sample size $n$ is large.
It is because that ppDSC-1b and ppDSC-2b ignore the bias caused by privacy-
preserving the networks and thus mis-specify the model. When $q,q^{\prime}$
become close to 1, the bias from privacy preservation does not matter much,
and then ppDSC-1b performs similarly to ppDSC. Third, as with extra local
computation demand, our method ppDSC is generally not better than the Oracle
estimator. However, when $q,q^{\prime}$, $n$, and $L$ become large, they are
getting close. This is consistent with our theoretical results.

(I) Projection distance

(a) Effect of $q,q^{\prime}$ (b) Effect of $n$

(c) Effect of $L$

(II) Misclassification rate

(d) Effect of $q,q^{\prime}$ (e) Effect of $n$

(f) Effect of $L$

Figure 1: Comparison of ppDSC, ppDSC-1b, ppDSC-2b and Oracle on the simulated
data. The effect of the privacy parameters $q,q^{\prime}$, the number of nodes
$n$, and the number of networks $L$ are shown, respectively. The projection
distance and misclassification rate are evaluated.

##  6 Real data analysis

In this section, we analyze the AUCS dataset (Rossi and Magnani, 2015), which
is a public dataset collected by the employees at the Department of Computer
Science of Aarhus University, to demonstrate the utility of the proposed
algorithm. Though privacy preservation is prominent nowadays, to the best of
our knowledge, networks known to be noisy and perturbed by the RR mechanism
are not currently available to the public. Hence, we regard the AUCS dataset
as the original data without any perturbation. We will mimic the actual setup
to see how the privacy and local computation affects the clustering
performance of the proposed algorithm.

#### Data description.

There are 61 employees (out of the total number of 142) who decided to join
the survey, consisting of professors, postdoctoral researchers, Ph.D.
students, and administration staff. Five types of relationships among the
employees are measured. Namely, current working relationships, repeated
leisure activities, regularly eating lunch together, co-authorship of a
publication, and friendship on Facebook. The first three relationships were
collected via a questionnaire. All the respondents answered all questions
indicating that the data was complete. And the last two relationships were
acquired online via the DBLP database and Facebook. As a result, the original
dataset consists of 5 undirected networks with 61 common nodes. Besides the
relationships, the research group labels that 55 out of 61 employees are
available. There are eight research groups ($K=8$) in total. Our analysis uses
the subnetworks of 55 employees with known labels.

#### Evidence of communities and heterogeneity.

The topology of networks with respect to different relationships is shown in
Figure 2 with colors indicating the research groups. It is clear to see that
the network structures are quite different. To take a closer look at the
community structures, we reorder the nodes according to their underlying
research groups (i.e., nodes corresponding to the same research group are
aligned next to each other). We further plot the corresponding network
adjacency matrices in Figure 3, where the whole network (Figure 3(a))
corresponds to the network that contains the edges of all five relationships.
The whole network shows conspicuous block structures in that nodes in the same
research group have more links than those across different research groups.
Hence, it is reliable to use the research group labels as the underlying
community memberships. Distinct from the whole network, we see that the
community structures of each network layer are heterogeneous in that some
communities are not evident or even missing to different extents.

(a) Work (b) Facebook (c) Leisure (d) Lunch (e) Coauthor

Figure 2: A visualization of the AUCS network where vertex colors represent
research groups. Each network corresponds to a specific relationship among the
vertices.

#### Practical consideration.

Though the AUCS dataset is publicly available, we note that some information
about individuals say the eating and working relationships are sometimes
sensitive and private. In addition, different relationships may be
investigated and owned by different parties. Therefore, we consider the
setting that the networks corresponding to each kind of relationship are
private and locally owned by different parties. We will see how the privacy
and local computation constraints affect the clustering performance of the
proposed algorithm.

#### Methods compared.

Consistent with the simulation experiments, we compare our method ppDSC with
ppDSC-1b, ppDSC-2b and Oracle. The detailed description of each method can be
found in Section 5. Generally, we study how the performance of each method
alters with the network number $L$ and the privacy parameters $q$ and
$q^{\prime}$. Regarding the effect of $L$, we mean that we use some of the
five local networks to construct the estimator to see how the number of used
networks affects the clustering performance. Regarding the effect of
$q,q^{\prime}$, we consider three cases, including $q,q^{\prime}$ both
varying, $q$ varying but $q^{\prime}$ being fixed, and $q^{\prime}$ varying
being $q$ being fixed, where the latter two cases aim to verify the different
effect of $q$ and $q^{\prime}$ indicated by the theory. The detailed setups
are as follows.

  * •

Effect of $L$: $q=q^{\prime}=0.9$, and $L$ ranges from 2 to 5.

  * •

Effect of $q,q^{\prime}$: $L=5$, and $q$ and $q^{\prime}$ are equal and range
from 0.6 to 1.

  * •

Effect of $q$: $L=5$, $q^{\prime}=0.95$, and $q$ ranges from 0.6 to 1.

  * •

Effect of $q^{\prime}$: $L=5$, $q=0.95$, and $q^{\prime}$ ranges from 0.6 to
1.

#### Results.

The averaged misclassification rates over 20 replications are displayed in
Figure 4. We have the following observations. First, as $L$ increases, the
misclassification rate of all four methods decreases, showing the benefits of
aggregating the information of local networks. Note that when $L=5$, a small
drop in terms of the clustering performance appears, partially because the
fifth network (i.e., the coauthor network) is rather sparse and has a weak
signal of communities. Second, as expected, as $q$ and $q^{\prime}$ increase,
the clustering performance of all four methods becomes better. We note that
the clustering performance with $q^{\prime}$ fixed to be 0.95 (See Figure
4(c)) is better than that with $q$ fixed to be 0.95 (See Figure 4(d)), which
shows that large $q^{\prime}$ is more desirable than large $q$. In other
words, perturbing 0 to 1 is more harmful than perturbing 1 to 0. This is
consistent with the theoretical results. Third, consistent with the simulation
results, the proposed method ppDSC is better than the biased method ppDSC-1b
and ppDSC-2b and is close to the baseline method Oracle as $q$ and
$q^{\prime}$ increase.

(a) Whole (b) Work (c) Facebook (d) Leisure (e) Lunch (f) Coauthor

Figure 3: A visualization of the network adjacency matrices of the AUCS
dataset. The nodes are permutated according to their underlying research
groups. (a) corresponds to the network adjacency matrix that contains all the
edges of the five relationships. (b)-(f) correspond to the adjacency matrices
of the five relationships among vertices, respectively.

(a) Effect of $L$ (b) Effect of $q,q^{\prime}$

(c) Effect of $q$ (d) Effect of $q^{\prime}$

Figure 4: Comparison of ppDSC, ppDSC-1b, ppDSC-2b and Oracle on the AUCS
network. The effect of the privacy parameters $q,q^{\prime}$ ($q,q^{\prime}$
synchronously vary, $q^{\prime}$ fixed but $q$ varies, $q$ fixed but
$q^{\prime}$ varies), and the number of networks $L$ are shown, respectively.
The misclassification rate with respect to the research group labels are
evaluated.

##  7 Conclusion

Driven by practical data collection and the associated analytic challenges, we
provide a powerful toolbox for community detection and estimation in multi-
layer SBMs based on locally stored networks with privacy protection. In the
toolbox, a new algorithm named ppDSC has been developed, and it is shown to be
both communication-efficient and privacy-aware. We also propose a two-step
bias-adjustment procedure to remove the biases caused by the RR perturbation
and take the square of the private-preserved network matrices. The procedure
is found to be effective both theoretically and numerically. Moreover, we have
rigorously investigated the misclassification rate of the algorithm. We show
how the privacy parameters affect the error bound. In particular, we
demonstrate the effect of heterogeneity among population networks and the
asymmetry roles of the privacy parameters $q$ and $q^{\prime}$ on the
estimation accuracy through rigorous theoretical justifications. The numerical
experiments well support our theoretical findings.

The proposed methodology can be extended to a variety of scenarios. First, the
ppDSC algorithm involves multiple steps. The methods used in some steps are
quite general and can be applied in other contexts. For example, the proposed
bias-adjustment procedure can be used in other stochastic block models in
different distributed SVD frameworks, e.g., Fan et al. (2019); Arroyo et al.
(2021). Second, it is well-known that privacy could be amplified by sampling
(Balle et al., 2018). With the same level of noise from privacy preservation,
a DP algorithm with sampled data leaks less privacy than that with all data.
Therefore, it is desirable to study the trade-off between privacy gain and
information loss when sampling the network entries in network analysis. Third,
for statistical convenience, we consider the local-DP (Duchi et al., 2018)
protection of networks. We may extend the proposed methods in the context of
central DP. Fourth, we focus on the distributed learning framework with only
one round of communication. It is desirable to extend the results to the
distributed framework with multiple rounds, say the communication-efficient
distributed power method (Li et al., 2021). Last but not least, the method and
theory for estimating $K$ can be an interesting topic to explore in the
future. (Fishkind et al., 2013; Li et al., 2020; Ma et al., 2021).

## Appendix

Appendix A provides the details of the bias-adjustment procedure. Appendix B
contains the additional theoretical results and discussions. Appendix C
contains the additional simulation experiment. Appendix D contains the
technical proofs for Theorems 1-4 and Corollary 1. Several auxiliary lemmas
are provided in Appendix E.

##  Appendix A Details of bias-adjustment

We illustrate how the diagonal elements of $\overline{A}_{l}^{2}$ would cause
bias for $P_{l}^{2}$, even though $\overline{A}_{l}$ is the unbiased estimator
of $P_{l}$. Denote the non-diagonal part of $P_{l}$ by
$P_{l1}:=P_{l}-{{\operatorname{diag}}}(P_{l})$, and denote the deviation of
$\overline{A}_{l}$ from $P_{l1}$ by $X_{l}:=\overline{A}_{l}-P_{l1}$. After
simple calculation, we obtain

$\displaystyle\overline{A}_{l}^{2}$
$\displaystyle=(X_{l}+P_{l1})^{2}=X_{l}^{2}+P_{l1}^{2}+X_{l}P_{l1}+P_{l1}X_{l}.$
(A.1)

Plugging in $P_{l1}^{2}=(P_{l}-{\operatorname{diag}}(P_{l}))^{2}$, we have

$\displaystyle\overline{A}_{l}^{2}-P_{l}^{2}$
$\displaystyle=E_{l,0}+E_{l,1}+E_{l,2}+E_{l,3}$ (A.2)

with

$\displaystyle E_{l,0}$
$\displaystyle:={-P_{l}\operatorname{diag}(P_{l})-\operatorname{diag}(P_{l})\cdot
P_{l}+(\operatorname{diag}(P_{l}))^{2}},$ $\displaystyle E_{l,1}$
$\displaystyle:=X_{l}(P_{l}-{\operatorname{diag}}(P_{l}))+(P_{l}-\operatorname{diag}(P_{l}))X_{l},$
$\displaystyle E_{l,2}$
$\displaystyle:=X_{l}^{2}-{\operatorname{diag}}(X_{l}^{2}),$ $\displaystyle
E_{l,3}$ $\displaystyle:={\operatorname{diag}}(X_{l}^{2}).$

We would see in Appendix D that the first three terms are actually all small.
While for the fourth term $E_{l,3}$, we now proceed to bound it. Note that

$\displaystyle(E_{l,3})_{ii}$
$\displaystyle=\sum_{j=1}^{n}X_{l,ij}^{2}=\sum_{j=1,j\neq
i}^{n}(\overline{A}_{l,ij}-P_{l,ij})^{2}$
$\displaystyle=\frac{1}{(q+q^{\prime}-1)^{2}}\sum_{j=1}^{n}\mathbb{I}({\tilde{A}}_{l,ij}=1)(1-(1-q^{\prime})-(q+q^{\prime}-1)P_{l,ij})^{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad+\frac{1}{(q+q^{\prime}-1)^{2}}\sum_{j=1}^{n}\mathbb{I}({\tilde{A}}_{l,ij}=0)(1-q^{\prime}+(q+q^{\prime}-1)P_{l,ij})^{2}$
$\displaystyle\leq\frac{\sum_{j=1}^{n}\mathbb{I}({\tilde{A}}_{l,ij}=1)(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}+\frac{n(1-q^{\prime}+(q+q^{\prime}-1)\kappa)^{2}}{(q+q^{\prime}-1)^{2}}$
$\displaystyle=\frac{\sum_{j}{\tilde{A}}_{l,ij}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}+\frac{n(1-q^{\prime}+(q+q^{\prime}-1)\kappa)^{2}}{(q+q^{\prime}-1)^{2}},$
(A.3)

where in the first inequality we assume that $q,q^{\prime}>1/2$ and
$\kappa=\max_{i,j,l}P_{l,ij}$. Hence, the error would be smaller if we further
subtract
$\frac{\sum_{j}{\tilde{A}}_{l,ij}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}$ from
the $i$th diagonal elements of $\overline{A}_{l}^{2}$ and assume
$\kappa=o(1)$. More importantly, as we aim to approximate
$\sum_{l=1}^{L}P_{l}^{2}$, this debiasing step is crucial when $L$ is
increasing.

##  Appendix B Additional theoretical results and discussions

###  B.1 Bound for $\overline{M}_{l}$

We provide the bound for the single matrix $\overline{M}_{l}$. As we will see,
due to the absence of $L$, the condition and the dominating term in the
resulting bound compared with the centralized bound is changed. The results
are summarized in Theorem B.1.

###### Theorem B.1

Suppose Assumption 2 holds, and $\epsilon\lesssim{\log}\,n$, the estimator
$\overline{M}_{l}$ for $Q_{l}$ satisfies

$\max_{l}\|\overline{M}_{l}-Q_{l}\|_{2}\leq
C\max\left\\{\frac{(q\rho+1-q^{\prime})^{1/2}n^{1/2}\rho\log^{1/2}(n)}{q+q^{\prime}-1},\,\frac{(q\rho+1-q^{\prime})\log
n}{(q+q^{\prime}-1)^{2}}\right\\},$ (B.1)

with probability larger than $1-O(Ln^{-\gamma})$, where $\gamma,C>0$ are some
fixed constants.

The proof of Theorem B.1 is included in Appendix D.

###  B.2 The effect of bias-adjustment

We theoretically show the effect of bias-adjustment. Denote the non-debiased
estimator by

$\tilde{M}:=\frac{1}{L}\sum_{l}\frac{1}{n}\tilde{A}_{l}^{2}$

and the corresponding population matrix by

$\tilde{Q}:=\frac{1}{L}\sum_{l}\left((q+q^{\prime}-1)P_{l}+(1-q^{\prime})\textbf{1}_{n}\textbf{1}_{n}^{\intercal}\right)^{2}/{n}.$

The following proposition provides the estimation error of $\tilde{M}$.

###### Proposition 2

Suppose Assumption 2 and condition (13) holds. Define

$\displaystyle\small\mathcal{I}:=\max\Big{\\{}\frac{(q\rho+1-q^{\prime})^{1/2}n^{1/2}[\rho+(1-q^{\prime})/(q+q^{\prime}-1)]\log^{1/2}(L+n)}{(q+q^{\prime}-1)\sqrt{L}},$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\frac{(q\rho+1-q^{\prime})\log(L+n)}{(q+q^{\prime}-1)^{2}\sqrt{L}},\,\frac{((q+q^{\prime}-1)\rho+1-q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}\Big{\\}},$

then the non-debiased estimator $\tilde{M}$ of $\tilde{Q}$ satisfies

$\displaystyle\scriptsize\|\tilde{M}-\tilde{Q}\|_{2}\lesssim(q+q^{\prime}-1)^{2}\mathcal{I}$
(B.2)

with probability larger than $1-O((L+n)^{-\nu})$ for some constant $\nu>0$.
Moreover, with the same probability,

$\|\tilde{M}-Q\|_{2}\lesssim(q+q^{\prime}-1)^{2}\mathcal{I}+\|\tilde{Q}-Q\|_{2}.$
(B.3)

The proof is similar to that of Theorem 3 provided in Appendix D; hence we
omit it. It can be easily seen that $\mathcal{I}$ is larger than (3) in
Theorem 3. Hence, if $q,q^{\prime}>c$ for some $c>1/2$, which implies that the
multiplier $(q+q^{\prime}-1)^{2}$ is a constant, then (B.2) and (B.3) are both
inferior than (3). To derive the bound for the eigen-vector and the
misclassification error bound, we note that we can either use (B.2) or (B.3).
What we need is only the minimum non-zero eigen-value of the corresponding
population matrix. Specifically, if we use (B.3), then the population matrix
is $Q$, which is the same as our setting. While if we use (B.2), then the
minimum non-zero eigen-value of $\tilde{Q}$ is required. Here, we consider the
two-parameter SBMs that $P_{l}$’s are homogeneous, with the inter-community
and cross-community probabilities being $a$ and $b$, respectively. In this
regime, the minimum non-zero eigen-value of
$(q+q^{\prime}-1)P_{l}+(1-q^{\prime})\textbf{1}_{n}\textbf{1}_{n}^{\intercal}$
is identical to that of $(q+q^{\prime}-1)P_{l}$, which implies that the error
for the eigen-vector (counterpart of Corollary 1) and the misclassification
error (counterpart of Theorem 4) totally depend on (B.3). As a result, we can
also see the accuracy gain in eigen-vector estimation and clustering.

##  Appendix C Additional numerical analysis and results

We conduct the following simulation to show the effect of heterogeneity.

#### Network-generation.

In Theorem 2, we show that the eigen-gap (i.e., $\lambda_{{\min}}(Q)$) divided
by the heterogeneity of connectivity matrices (i.e., $\mathcal{H}$ in
Assumption 4) can affect the estimation accuracy of the proposed algorithm
theoretically. The heterogeneity can lead to either accuracy gain or loss,
depending on the model structure of the network. To illustrate this phenomenon
numerically, we consider the following two models for demonstrating the curses
of heterogeneity and the blessings of heterogeneity, respectively.

  * •

_Model I (Curses of heterogeneity)._ We fix $K=2$, $L=12$, $q,q^{\prime}=0.8$
and let $n$ vary from 20 to 400. The communities are balanced. The networks
are generated from multi-layer SBMs and equally belong to the following four
different classes,

$B^{(i)}=0.25\cdot{\operatorname{diag}}(1,1)+\alpha C^{(k)}$

with

$\displaystyle C^{(1)}=\begin{pmatrix}0.1&0\\\ 0&0.1\end{pmatrix},\quad
C^{(2)}=-\begin{pmatrix}0.1&0\\\ 0&0.1\end{pmatrix},\quad
C^{(3)}=-\begin{pmatrix}0.1&0\\\ 0&0\end{pmatrix},\quad
C^{(4)}=-\begin{pmatrix}0&0\\\ 0&0.1\end{pmatrix}.$

For this model, one can imagine that larger $\alpha$ indicates larger
heterogeneity but a similar level of signal strength (eigen-gap). Therefore,
larger $\alpha$ leads to larger scaled heterogeneity (i.e., eigen-gap divided
by heterogeneity; see the discussions after Theorem 2 for the details). This
is verified in Figure C.1(a).

  * •

_Model II (Blessings of heterogeneity)._ We fix $K=2$, $L=12$,
$q,q^{\prime}=0.8$ and let $n$ vary from 20 to 400. The communities are
balanced. Similar to Arroyo et al. (2021), the networks are generated from
SBMs and equally belong to the following four different classes,

$B^{(i)}=0.25(11^{\intercal})+\alpha C^{(k)}$

with

$\displaystyle C^{(1)}=\begin{pmatrix}0.1&0\\\ 0&0.1\end{pmatrix},\quad
C^{(2)}=-\begin{pmatrix}0.1&0\\\ 0&0.1\end{pmatrix},\quad
C^{(3)}=\begin{pmatrix}0.1&0\\\ 0&0\end{pmatrix},\quad
C^{(4)}=\begin{pmatrix}0&0\\\ 0&0.1\end{pmatrix}.$

For this model, larger $\alpha$ indicates larger heterogeneity but stronger
signal strength (eigen-gap). Thus, the composite effects lead to larger
$\alpha$ corresponding to smaller scaled heterogeneity. See Figure C.2(a) for
the illustration.

#### Results.

The averaged results over 20 replications for _Model I_ and _II_ are displayed
in Figure C.1 and C.2, respectively. The results are consistent with the
theoretical results given in Theorem 2. For _Model I_ , we see that large
heterogeneity (i.e., large $\alpha$) leads to inferior performance of ppDSC,
especially in terms of the projection distance, which is partially because
that large $\alpha$ leads to large scaled heterogeneity (i.e., eigen-gap
divided by heterogeneity) in Theorem 2; see Figure C.1. For _Model II_ , the
results are on the opposite side in that large heterogeneity (i.e., large
$\alpha$) leads to performance gain of ppDSC, which is partially due to the
fact that large $\alpha$ leads to large eigen-gap and small scaled
heterogeneity; see Figure C.2. In addition, our estimator ppDSC is better than
the biased ppDSC-1b and ppDSC-2b, and is closer to the Oracle estimator.

(a) Population parameters (b) Projection distance (c) Misclassification rate

Figure C.1: Illustration for the curse of heterogeneity (_Model I_). (a)
corresponds to population parameters including the heterogeneity, eigen-gap
and their ratios against $\alpha$. (b) and (c) correspond to the projection
distance and misclassification rate of ppDSC, ppDSC-1b, ppDSC-2b and Oracle.

(a) Population parameters (b) Projection distance (c) Misclassification rate

Figure C.2: Illustration for the blessing of heterogeneity (_Model II_). (a)
corresponds to population parameters including the heterogeneity, eigen-gap
and their ratios against $\alpha$. (b) and (c) correspond to the projection
distance and misclassification rate of ppDSC, ppDSC-1b, ppDSC-2b and Oracle.

##  Appendix D Main proofs

###  D.1 Proof of Theorem 1

For $i\in\\{1,...,L\\}$, denote the RR-perturbed $A_{i}$ by ${\tilde{A}}_{i}$.
By Proposition 1, for each $i$, ${\tilde{A}}_{i}$ satisfies $\epsilon$-edge-
DP. Further, by the parallel composition theorem (McSherry, 2009),
$({\tilde{A}}_{1},...,{\tilde{A}}_{L})$ also satisfies $\epsilon$-edge-DP.
Finally, by the post-processing property of DP (Proposition 1), Algorithm 1
can achieve $\epsilon$-edge-DP. $\blacksquare$

###  D.2 Proof of Theorem 2

First, we note that we have a degree of freedom in choosing $V$. For
simplicity, we assume that the reference solution $\hat{V}_{o}$ in Algorithm 1
is already aligned with $V$ in that
$\arg\min_{Z\in\mathcal{O}_{K}}\|\hat{V}_{o}Z-V\|_{F}=I_{K}$. Otherwise, we
could work with $VZ$ for some $Z\in\mathcal{O}_{K}$ instead.

We will make use of the following result to prove, which is modified from
Charisopoulos et al. (2021) using the notation of this paper.

###### Proposition 3

Suppose

$\lambda_{{\min}}(Q)\geq\delta,\quad{for\;some\;}\delta>0$ (D.1)

and

$\|\overline{M}_{l}-Q\|_{2}\leq\frac{\delta}{8},\quad{for\;all\;}l=1,...,L.$
(D.2)

Then the output $\tilde{V}$ of Algorithm 1 satisfies that

${\mathrm{dist}}(\tilde{V},V)\lesssim\frac{1}{\delta^{2}}\max_{l}\|\overline{M}_{l}-Q\|_{2}^{2}+\frac{1}{\delta}\|\frac{1}{L}\sum_{l=1}^{L}\overline{M}_{l}-Q\|_{2}.$

We first have that

$\displaystyle\|\overline{M}_{l}-Q\|_{2}$
$\displaystyle\leq\|\overline{M}_{l}-Q_{l}\|_{2}+\|Q_{l}-Q\|_{2}$
$\displaystyle\leq\|\overline{M}_{l}-Q_{l}\|_{2}+C^{\prime}\mathcal{H}(n,\rho,L),$

where the last inequality follows from

$\displaystyle\|Q_{l}-Q\|_{2}$
$\displaystyle=\left\|\frac{P_{l}^{2}}{n}-\frac{1}{L}\sum_{i=1}^{L}\frac{P_{i}^{2}}{n}\right\|_{2}\leq\frac{1}{n}\|\Delta\|_{2}^{2}\|B_{l}\Delta^{2}B_{l}-\frac{1}{L}\sum_{i=1}^{L}B_{i}\Delta^{2}B_{i}\|_{2}$
$\displaystyle\leq
C\frac{1}{K}\|B_{l}\Delta^{2}B_{l}-\frac{1}{L}\sum_{i=1}^{L}B_{i}\Delta^{2}B_{i}\|_{2}\leq
C^{\prime}\mathcal{H}(n,\rho,L),$

by using the fact that

$P_{l}^{2}=\Theta B_{l}\Theta^{\intercal}\Theta
B_{l}\Theta^{\intercal}=\bar{\Theta}\Delta(B_{l}\Delta^{2}B_{l})\Delta\bar{\Theta}^{\intercal}$

with $\Delta:={\operatorname{diag}}(\sqrt{n_{1}},...,\sqrt{n_{K}})$,
$\bar{\Theta}:=\Theta\Delta^{-1}$, and
$\bar{\Theta}^{\intercal}\bar{\Theta}=\mathbb{I}$, and Assumptions 1 and 4. To
meet (D.1) and (D.2), we let $\delta\asymp\lambda_{\min}(Q)$ and enforce

$\|\overline{M}_{l}-Q_{l}\|_{2}\leq\frac{\lambda_{\min}(Q)}{16}\quad{and}\quad\mathcal{H}\leq\frac{\lambda_{\min}(Q)}{16C^{\prime}},$

which follows by our condition in Theorem 2. We can thus use the results in
Proposition 3 to obtain that,

$\mathrm{dist}(\tilde{V},V)\lesssim{\max_{l}\frac{\|\overline{M}_{l}-Q_{l}\|_{2}^{2}}{\lambda_{\min}^{2}(Q)}}+{\frac{\mathcal{H}^{2}(n,\rho,L)}{\lambda_{\min}^{2}(Q)}}+\frac{\|\sum_{l}\overline{M}_{l}/L-Q\|_{2}}{\lambda_{\min}(Q)}.$

The results of Theorem 2 are proved. $\blacksquare$

###  D.3 Proof of Theorem 3

We make use of the concentration tools developed in Lei and Lin (2022) to
prove. Recall that $\overline{M}=\frac{1}{L}\sum_{l=1}^{L}\overline{M}_{l}$
and (11), then we can decompose the difference between $\overline{M}$ and $Q$
as

$n\overline{M}-nQ=\sum_{l=1}^{L}\frac{1}{L}(n\overline{M}_{l}-nQ_{l}):=E_{0}+E_{1}+E_{2}+E_{3}-\sum_{l}\frac{1}{L}\frac{G_{l}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}},$

with $E_{i}:=\frac{1}{L}\sum_{l=1}^{L}E_{l,i}$ for $i=0,1,2,3$ and $E_{l,i}$
is the same with those in (A.2). Now, we bound these error terms,
respectively.

For
$E_{0}:=\sum_{l}\frac{1}{L}\left({-P_{l}}\cdot{\operatorname{diag}}(P_{l})-{\operatorname{diag}}(P_{l})\cdot
P_{l}+({\operatorname{diag}}(P_{l}))^{2}\right)$, we have

$\displaystyle\|E_{0}\|_{2}\leq
2\max_{l}\|{\operatorname{diag}}(P_{l})\|_{2}\max_{l}\|P_{l}\|_{{F}}+\max_{l}\|{\operatorname{diag}}(P_{l})\|_{2}^{2}\leq
Cn\rho^{2}.$

For
$E_{1}:=\sum_{l}\frac{1}{L}\left(X_{l}(P_{l}-\operatorname{diag}(P_{l}))+(P_{l}-\operatorname{diag}(P_{l}))X_{l}\right)$,
we would use the result in Lemma 1. To that end, we first show that each entry
of $(q+q^{\prime}-1)X_{l}$ satisfies the Bernstein tail condition (see
Definition 2). Given $i\neq j$, with slight abuse of notation, define

$Y_{l}:=(q+q^{\prime}-1)X_{l,ij}=(q+q^{\prime}-1)(\overline{A}_{l,ij}-P_{l,ij})={\tilde{A}}_{l,ij}-(1-q^{\prime})-(q+q^{\prime}-1)P_{l,ij}.$

Then

$\displaystyle
Y_{l}=\begin{cases}q^{\prime}-(q+q^{\prime}-1)P_{l,ij}\;\,\mathrm{with\;probability}\,\;qP_{l,ij}+(1-P_{l,ij})(1-q^{\prime}),\\\
q^{\prime}-1-(q+q^{\prime}-1)P_{l,ij}\;\,\mathrm{with\;probability}\,\;q^{\prime}(1-P_{l,ij})+P_{l,ij}(1-q),\end{cases}$

and for $k\geq 2$, we have

$\displaystyle{\mathbb{E}}|Y_{l}^{k}|$
$\displaystyle\leq|q^{\prime}-(q+q^{\prime}-1)P_{l,ij}|^{k}\Big{[}qP_{l,ij}+(1-P_{l,ij})(1-q^{\prime})\Big{]}$
$\displaystyle\quad\quad\quad+|(q+q^{\prime}-1)P_{l,ij}+1-q^{\prime}|^{k}\Big{[}q^{\prime}(1-P_{l,ij})+P_{l,ij}(1-q)\Big{]}$
$\displaystyle\leq\left(qP_{l,ij}+(1-P_{l,ij})(1-q^{\prime})\right)+\left((q+q^{\prime}-1)P_{l,ij}+1-q^{\prime}\right)$
$\displaystyle\leq
2\left(q\rho+1-q^{\prime}\right)\leq\frac{v_{1}}{2}k!R_{1}^{k-2},$ (D.3)

where $v_{1}:=4\left(q\rho+1-q^{\prime}\right)$ and $R_{1}:=1$, and we used
the fact that $P_{l,ij}=o(1)$. Hence, $(q+q^{\prime}-1)X_{l,ij}$ is
$(v_{1},R_{1})$-Bernstein. In addition, it holds that
$\|\sum_{l}(P_{l}-{\operatorname{diag}}(P_{l}))^{2}\|_{2}\leq\sum_{l}\|P_{l}-{\operatorname{diag}}(P_{l})\|_{{F}}^{2}\leq
Ln^{2}\rho^{2}$ and
$\max_{l}\|P_{l}-{\operatorname{diag}}(P_{l})\|_{2,\infty}\leq\sqrt{n}\rho$.
Applying Lemma 1, we obtain

$\displaystyle{\mathbb{P}}((q+q^{\prime}-1)L\|E_{1}\|_{2}\geq t)\leq
4n\cdot\exp\left\\{\frac{-t^{2}/2}{4(q\rho+(1-q^{\prime}))Ln^{3}\rho^{2}+\sqrt{n}\rho
t}\right\\}.$

Choosing $t=c(q\rho+1-q^{\prime})^{1/2}n^{3/2}L^{1/2}\rho\log^{1/2}(L+n)$, it
turns out that

$\sqrt{n}\rho t\leq c4(q\rho+(1-q^{\prime}))Ln^{3}\rho^{2},$

which is $\log^{1/2}(L+n)\leq c(q\rho+1-q^{\prime})^{1/2}nL^{1/2}$ and can be
certainly met if $\log^{1/2}(L+n)\leq c(1-q^{\prime})^{1/2}nL^{1/2}$, which
can be satisfied by the fact that
$q^{\prime}={\mathrm{e}}^{\epsilon}/(1+{\mathrm{e}}^{\epsilon})$ and the
condition (13). As a result, we have with probability larger than
$1-(L+n)^{-\beta}$ for some $\beta>0$ that

$\displaystyle\|E_{1}\|_{2}\leq
c\frac{(q\rho+1-q^{\prime})^{1/2}}{q+q^{\prime}-1}\cdot
n^{3/2}\rho\log^{1/2}(L+n)/\sqrt{L}.$

For
$E_{2}:=\sum_{l}\frac{1}{L}\left(X_{l}^{2}-{\operatorname{diag}}(X^{2}_{l})\right)$,
we would use the results in Lemma 2. For this purpose, we first show that
given an independent copy $(q+q^{\prime}-1)\tilde{X}_{l}$ of
$(q+q^{\prime}-1)X_{l}$, each $(q+q^{\prime}-1)^{2}X_{l,ij}\tilde{X}_{l,ij}$
satisfies the Bernstein tail condition. Actually, similar to the derivation of
(D.3), we can easily show that $(q+q^{\prime}-1)^{2}X_{l,ij}\tilde{X}_{l,ij}$
is $(v^{\prime}_{2},R^{\prime}_{2})$-Bernstein with
$v^{\prime}_{2}=8\left(q\rho+1-q^{\prime}\right)^{2}$ and $R^{\prime}_{2}=1$.
Then by Lemma 2, we obtain with probability larger than $1-O((L+n)^{-1})$ that

$\displaystyle\|E_{2}\|_{2}\leq
c\max\left\\{\frac{(q\rho+1-q^{\prime})n\log(L+n),(q\rho+1-q^{\prime})^{1/2}\sqrt{n}\log^{3/2}(L+n),\log^{2}(L+n)/\sqrt{L}}{\sqrt{L}(q+q^{\prime}-1)^{2}}\right\\}.$
(D.4)

Further, by the condition (13), we have $\log(L+n)\leq cn(1-q^{\prime})\leq
cn(q\rho+1-q^{\prime})$ and (D.4) reduces to

$\displaystyle\|E_{2}\|_{2}\leq
c\frac{(q\rho+1-q^{\prime})n\log(L+n)}{\sqrt{L}(q+q^{\prime}-1)^{2}}.$

For
$E_{3}-\sum_{l}\frac{1}{L}\frac{G_{l}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}$,
recalling (A), it is easy to see that

$\displaystyle\|E_{3}-\sum_{l}\frac{1}{L}\frac{G_{l}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}\|_{2}\leq
C\frac{n((q+q^{\prime}-1)\rho+1-q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}.$

Consequently, $E_{1}$, $E_{2}$ and $E_{3}$ are the main effects and we
obtained the results of Theorem 3. $\blacksquare$

###  D.4 Proof of Theorem B.1

The proof is similar to the that of Theorem 3. We here go through the main
steps.

Recalling (A.2) and (11), we can write

$n\overline{M}_{l}-nQ_{l}:=n\overline{M}_{l}-nP_{l}^{2}:=E_{l,0}+E_{l,1}+E_{l,2}+E_{l,3}-\frac{G_{l}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}.$

Next, we bound these error terms, respectively.

For
$E_{l,0}:={-P_{l}}\cdot{\operatorname{diag}}(P_{l})-{\operatorname{diag}}(P_{l})\cdot
P_{l}+({\operatorname{diag}}(P_{l}))^{2}$, we can easily show that

$\displaystyle\|E_{l,0}\|_{2}\leq cn\rho^{2}.$

For
$E_{l,1}:=X_{l}(P_{l}-{\operatorname{diag}}(P_{l}))+(P_{l}-{\operatorname{diag}}(P_{l}))X_{l}$,
using Lemma 1 with the same Bernstein tail condition as those in the proof of
Theorem 3, we can obtain that with probability larger than $1-n^{-\beta}$ for
some $\beta>0$,

$\displaystyle\|E_{l,1}\|_{2}\leq
c\frac{(q\rho+1-q^{\prime})^{1/2}}{q+q^{\prime}-1}n^{3/2}\rho\log^{1/2}(n),$

provided that $\log^{1/2}\,n\leq C(q\rho+1-q^{\prime})^{1/2}n$, which can be
implied by $\log n\leq Cn(1-q^{\prime})=C{n}/({1+{\mathrm{e}}^{\epsilon}})$ by
noting our condition $\epsilon\leq C{\log}\,n$.

For $E_{l,2}:=X_{l}^{2}-{\operatorname{diag}}(X^{2}_{l})$, using Lemma 2 with
the same Bernstein tail condition as the one used in the proof of Theorem 3,
we observe that with probability larger than $1-O(n^{-1})$,

$\displaystyle\|E_{l,2}\|_{2}\leq
c\max\left\\{vn\log(n),\,\sqrt{v}\sqrt{n}\log^{3/2}(n),\,\log^{2}(n)\right\\}/(q+q^{\prime}-1)^{2},$
(D.5)

where $v:=q\rho+1-q^{\prime}$. Note that by the condition that $\epsilon\leq
C{\log}\,n$, we have ${\log}\,n\leq Cn(1-q^{\prime})\leq
Cn(q\rho+1-q^{\prime})$, and thus the first term in (D.5) dominates and

$\displaystyle\|E_{l,2}\|_{2}\leq
c\frac{(q\rho+1-q^{\prime})n\log(n)}{(q+q^{\prime}-1)^{2}}.$

For the last two error terms
$E_{l,3}-\frac{G_{l}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}$, it is easy to
see that

$\displaystyle\|E_{l,3}-\frac{G_{l}(q^{\prime})^{2}}{(q+q^{\prime}-1)^{2}}\|_{2}\leq
c\frac{(1-q^{\prime}+(q+q^{\prime}-1)\rho)^{2}}{(q+q^{\prime}-1)^{2}}\cdot n.$

It is easy to see that $E_{l,0}\leq CE_{l,1}$. Now we show that $E_{3}\leq
CE_{2}$, for which we only need to show

$\displaystyle(1-q^{\prime}+(q+q^{\prime}-1)\rho)^{2}\leq
C(q\rho+1-q^{\prime}){\log}\,n.$

Actually, we have $(1-q^{\prime})^{2}\leq C\log\,n(1-q^{\prime})\leq
C\log\,n(q\rho+1-q^{\prime})$, and $((q+q^{\prime}-1)\rho)^{2}\leq
Cq\rho\log\,n\leq C(q\rho+1-q^{\prime}){\log}\,n$ by noting that $q>1/2$ and
$q+q^{\prime}-1\leq 1$. As a result, $E_{l,1}$ and $E_{l,2}$ dominate. After
using the union bound, we finally have

$\max_{l}\|\overline{M}_{l}-Q_{l}\|_{2}\leq
C\max\left\\{\frac{(q\rho+1-q^{\prime})^{1/2}n^{1/2}\rho\log^{1/2}(n)}{q+q^{\prime}-1},\,\frac{(q\rho+1-q^{\prime})\log
n}{(q+q^{\prime}-1)^{2}}\right\\},$

with probability larger than $1-O(Ln^{-\gamma})$ for some constant $\gamma>0$.
The results of Theorem B.1 are arrived. $\blacksquare$

###  D.5 Proof of Corollary 1

The proof of Corollary 1 follows directly from that of Theorem 2. First, we
need to show that $Q$ is of rank $K$ and provide the lower bound of
$\lambda_{K}(Q)$. Indeed, define
$\Delta={\operatorname{diag}}(\sqrt{n_{1}},...,\sqrt{n_{K}})$ and denote
$\bar{\Theta}:=\Theta\Delta^{-1}$, then $\bar{\Theta}$ is orthogonal and we
can write $Q$ as

$\displaystyle Q$
$\displaystyle=\frac{\rho^{2}}{nL}\bar{\Theta}\Delta(\sum_{l=1}^{L}B_{l,0}\Delta^{2}B_{l,0})\Delta\bar{\Theta}^{\intercal}$
$\displaystyle\succeq
c\frac{\rho^{2}}{L}\bar{\Theta}\Delta(\sum_{l=1}^{L}B_{l,0}B_{l,0})\Delta\bar{\Theta}^{\intercal}$
$\displaystyle\succeq
c{\rho^{2}}\bar{\Theta}\Delta^{2}\bar{\Theta}^{\intercal}$
$\displaystyle\succeq c{n\rho^{2}}\bar{\Theta}\bar{\Theta}^{\intercal},$ (D.6)

where we used Assumption 2 in the first equality, Assumption 1 in the first
and last inequality, and Assumption 3 in the second inequality. (D.5) implies
that $Q$’s rank is $K$ and $\lambda_{K}(Q)\geq cn\rho^{2}$.

Next, we specify the $\mathcal{I}_{1},\mathcal{I}_{2}$ and $\mathcal{I}_{3}$
and the corresponding condition in Theorem 2 that $\mathcal{I}_{1}$ and
$\mathcal{I}_{2}$ need to be smaller enough. Recall the bound for the single
matrix $\overline{M}_{l}$ in Theorem B.1, we find that when

$\rho\gtrsim\frac{(q\rho+1-q^{\prime})^{1/2}}{q+q^{\prime}-1}\cdot\sqrt{\frac{\log(n)}{n}},$
(D.7)

the bound in (B.1) reduces to the first term
$\frac{(q\rho+1-q^{\prime})^{1/2}n^{1/2}\rho\log^{1/2}(n)}{q+q^{\prime}-1}$
which is automatically smaller than $\lambda_{K}(Q)$ provided with (D.7). As a
result, $\mathcal{I}_{1}$ is specified under (D.7). For $\mathcal{I}_{2}$, we
do not specify it but only require the condition that

$\mathcal{H}\lesssim n\rho^{2}.$

For $\mathcal{I}_{3}$, the bound directly follows from Theorem 3.

As a result, the results of Corollary 1 have been arrived. $\blacksquare$

###  D.6 Proof of Theorem 4

The general proving strategy is same with Lei and Rinaldo (2015); Rohe et al.
(2011); Zhang et al. (2022), among others. To fix ideas, we now recall and
introduce some notation. $V$ denotes $K$ leading eigenvectors of $Q$ and
$\tilde{V}$ denotes the $K$ leading eigenvectors produced by Algorithm 1.
Likewise, $\tilde{V}^{\prime}={{\tilde{\Theta}}}{{X}}$ denotes the estimated
eigenvectors by the $k$-means with $\tilde{V}$ being its input, where
${\tilde{\Theta}}$ is the estimated membership matrix and ${{X}}$ denotes the
centriods.

First, we have that there exists $O\in\mathcal{O}_{K}$ such that

$\displaystyle\|{\tilde{V}^{\prime}}-VO\|_{\tiny F}^{2}$
$\displaystyle=\|{\tilde{V}^{\prime}}-\tilde{V}+\tilde{V}-VO\|_{\tiny F}^{2}$
$\displaystyle\leq 2\|VO-\tilde{V}\|_{\tiny F}^{2}+2\|\tilde{V}-VO\|_{\tiny
F}^{2}$ $\displaystyle=4\|\tilde{V}-VO\|_{\tiny F}^{2}$ $\displaystyle\leq
C\|\tilde{V}-VO\|_{2}^{2}\leq C\mathcal{S}^{2},$

where $\mathcal{S}:=\mathcal{I}_{1}+\mathcal{I}_{2}+\mathcal{I}_{3}$ with
$\mathcal{I}_{i}$’s defined in Corollary 1, the first inequality follows
because we assume that ${\tilde{V}^{\prime}}$ is the global solution minimum
of the following $k$-means objective and $VO$ is a feasible solution by Lemma
4,

$(\tilde{\Theta},X)=\underset{{{\Theta}\in\mathbb{M}_{n,K},{X}\in\mathbb{R}^{K\times
K}}}{{\mathrm{arg\;min}}}\;\|{\Theta}{X}-\tilde{V}\|_{\tiny F}^{2},$

and the last inequality follows from Corollary 1 and the fact that
$\min_{O\in\mathcal{O}_{K}}\|\tilde{V}-VO\|_{2}^{2}\lesssim\mathrm{dist}(\tilde{V},V)$.

Then, we begin to bound the fraction of misclassified nodes. Define

$\mathcal{M}=\\{i\in\\{1,...,n\\}:\;\|{\tilde{V}^{\prime}}_{i\ast}-({V}O)_{i\ast}\|_{\tiny\mathrm{2}}\geq\frac{\tau}{2}\\},$

with

$\tau=\min_{k\neq l}\sqrt{(n_{k})^{-1}+(n_{l})^{-1}}.$

Then we can see obviously that

$\frac{|\mathcal{M}|}{n}\leq C\mathcal{S}^{2}/(n\tau^{2})\leq
C^{\prime}\mathcal{S}^{2}.$

where the last inequality follows from Assumption 1.

Finally, we show that the nodes outside $\mathcal{M}$ are correctly clustered
to their underlying communities. Define $T_{k}:=G_{k}\backslash\mathcal{M}$,
where $G_{k}$ denotes the set of nodes within the true community $k$. $T_{k}$
is not an empty set provided that $|\mathcal{M}|<n_{k}$ for any $k$ by our
condition. Let $T=\cup_{k=1}^{K}T_{k}$. We will rightly see that the rows in
$(VO)_{T\ast}$ has a one to one correspondence with those in
${\tilde{V}^{\prime}}_{T\ast}$. On the one hand, for $i\in T_{k}$ and $j\in
T_{l}$ with $l\neq k$,
${\tilde{V}^{\prime}}_{i\ast}\neq{\tilde{V}^{\prime}}_{j\ast}$, otherwise the
following contradiction follows

$\displaystyle\tau\leq\|(VO)_{i\ast}-(VO)_{j\ast}\|_{2}\leq\|(VO)_{i\ast}-{\tilde{V}^{\prime}}_{i\ast}\|_{2}+\|(VO)_{j\ast}-{\tilde{V}^{\prime}}_{j\ast}\|_{2}<\frac{\tau}{2}+\frac{\tau}{2},$

where the last inequality is implied by the definition of $\mathcal{M}$ and
the first inequality is implied by Lemma 4 by noting

$Q=\frac{1}{L}\sum_{l}P_{l}^{2}=\frac{1}{L}\sum_{l}\Theta
B_{l}\Theta^{\intercal}\Theta
B_{l}\Theta^{\intercal}=\bar{\Theta}\Delta\frac{1}{L}\sum_{l}(B_{l}\Delta^{2}B_{l})\Delta\bar{\Theta}^{\intercal}:={\Theta}\overline{B}{\Theta}^{\intercal},$

where $\Delta={\operatorname{diag}}(\sqrt{n_{1}},...,\sqrt{n_{K}})$,
$\bar{\Theta}:=\Theta\Delta^{-1}$,
$\bar{\Theta}^{\intercal}\bar{\Theta}=\mathbb{I}$ and $\bar{B}$ is of full
rank by our condition (see (D.5) for explanations). On the other hand, for
$i,j\in T_{k}$, ${\tilde{V}^{\prime}}_{i\ast}={\tilde{V}^{\prime}}_{j\ast}$,
because otherwise ${\tilde{V}^{\prime}}_{T\ast}$ has more than $K$ distinct
rows which is contradict with the fact that the community size is $K$.

So far, we have arrived at the conclusion of Theorem 4. $\blacksquare$

##  Appendix E Auxiliary lemmas

We provide auxiliary lemmas that are used for proving the theorems in the
paper.

######  Definition 2 (Bernstein tail condition)

A random variable $Y$ is said to be $(v,R)$-Bernstein if
${\mathbb{E}}[|Y|^{k}]\leq\frac{v}{2}k!R^{k-2}$ for all integers $k\geq 2$.

######  Lemma 1 (Theorem 3 in Lei and Lin (2022))

Let $X_{1},...,X_{L}$ be a sequence of independent $n\times r$ random matrices
with zero-mean independent entries being $(v_{1},R_{1})$-Bernstein. Let
$H_{1},...H_{L}$ be any sequence of $r\times n$ non-random matrices. Then for
all $t>0$,

${\mathbb{P}}(\|\sum_{l=1}^{L}X_{l}H_{l}\|_{2}\geq t)\leq
4n\exp\left(-\frac{t^{2}/2}{v_{1}n\|\sum_{l}H_{l}^{\intercal}H_{l}\|_{2}+R_{1}\max_{l}\|H_{l}\|_{2,\infty}t}\right).$

$\blacksquare$

######  Lemma 2 (Theorem 4 in Lei and Lin (2022))

Let $X_{1},X_{2},...,X_{L}$ be independent $n\times n$ random symmetric matrix
with independent diagonal and upper diagonal entries. For any $l\in[L]$ and
any pair of $(i,j)(i\leq j)$, $X_{l,ij}$ is $(v_{1},R_{1})$-Bernstein, and
$X_{l,ij}\tilde{X}_{l,ij}$ is $(v^{\prime}_{2},R^{\prime}_{2})$-Bernstein
where $\tilde{X}_{l,ij}$ is an independent copy of $X_{l,ij}$. Then with
probability larger than $1-O((n+L)^{-1})$,

$\displaystyle\|\sum_{l}X_{l}^{2}-{\operatorname{diag}}(\sum_{l}X_{l}^{2})\|_{2}\leq
C$
$\displaystyle\Big{[}v_{1}n\log(L+n)\sqrt{L}+\sqrt{v_{1}}R_{1}\sqrt{Ln}\log^{3/2}(L+n)$
$\displaystyle\quad\quad+\sqrt{v^{\prime}_{2}}\sqrt{Ln}\log(L+n)+(R_{1}^{2}+R^{\prime}_{2})\log^{2}(L+n)\Big{]}.$

Moreover, if the squared entry $X_{l,ij}^{2}$ is $(v_{2},R_{2})$-Bernstein,
then with probability larger than $1-O((n+L)^{-1})$.

$\displaystyle\|{\operatorname{diag}}(\sum_{l}X_{l}^{2})-\mathbb{E}({\operatorname{diag}}(\sum_{l}X_{l}^{2}))\|_{2}\leq
C\left[\sqrt{v_{2}}\log(L+n)\sqrt{Ln}+R_{2}\log(L+n)\right].$

$\blacksquare$

######  Lemma 3 (Davis-Kahan theorem)

Let $Q\in\mathbb{R}^{n\times n}$ be a rank $K$ symmetric matrix with smallest
nonzero singular value $\gamma_{n}$. Let $M$ be any symmetric matrix and
$\hat{U},U\in\mathbb{R}^{n\times K}$ be the $K$ leading eigenvectors of $M$
and $Q$, respectively. Then there exists a $K\times K$ orthogonal matrix $O$
such that

$\|\hat{U}-UO\|_{F}\leq\frac{2\sqrt{2K}\|M-Q\|_{2}}{\gamma_{n}}.$

_Proof._ See Lei and Rinaldo (2015); Chen et al. (2021b), among others.
$\blacksquare$

###### Lemma 4

Define the population matrix $Q=\Theta\bar{B}\Theta^{\intercal}$. Suppose
$\bar{B}$ is of full rank and denote the eigen-decomposition of $Q$ by
${V}_{n\times K}{\Sigma}_{K\times K}{V}^{\intercal}_{K\times n}$. Then,
$V=\Theta X$ for some given matrix $X$. Specifically, for
$\Theta_{i\ast}=\Theta_{j\ast}$, we have ${V}_{i\ast}={V}_{j\ast}$; while for
$\Theta_{i\ast}\neq\Theta_{j\ast}$, we have
$\|{V}_{i\ast}-{V}_{j\ast}\|_{2}=\sqrt{(n_{g_{i}})^{-1}+(n_{g_{j}})^{-1}}$.

_Proof._ See Lei and Rinaldo (2015); Guo et al. (2020); Zhang et al. (2022),
among others. $\blacksquare$

## References

  * Arroyo et al. (2021) Jesús Arroyo, Avanti Athreya, Joshua Cape, Guodong Chen, Carey E Priebe, and Joshua T Vogelstein.  Inference for multiple heterogeneous networks with a common invariant subspace.  _Journal of Machine Learning Research_ , 22(142):1–49, 2021.
  * Ayed et al. (2020) Fadhel Ayed, Marco Battiston, and Federico Camerlenghi.  An information theoretic approach to post randomization methods under differential privacy.  _Statistics and Computing_ , 30(5):1347–1361, 2020.
  * Balle et al. (2018) Borja Balle, Gilles Barthe, and Marco Gaboardi.  Privacy amplification by subsampling: Tight analyses via couplings and divergences.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Barbillon et al. (2017) Pierre Barbillon, Sophie Donnet, Emmanuel Lazega, and Avner Bar-Hen.  Stochastic block models for multiplex networks: an application to a multilevel network of researchers.  _Journal of the Royal Statistical Society: Series A (Statistics in Society)_ , 180(1):295–314, 2017.
  * Bhaskara and Wijewardena (2019) Aditya Bhaskara and Pruthuvi Maheshakya Wijewardena.  On distributed averaging for stochastic k-PCA.  _Advances in neural information processing systems_ , 32:11026–11035, 2019.
  * Bhattacharyya and Chatterjee (2018) Sharmodeep Bhattacharyya and Shirshendu Chatterjee.  Spectral clustering for multiple sparse networks: I.  _arXiv preprint arXiv:1805.10594_ , 2018.
  * Bi and Shen (2022) Xuan Bi and Xiaotong Shen.  Distribution-invariant differential privacy.  _Journal of Econometrics_ , page In Press, 2022.
  * Boccaletti et al. (2014) Stefano Boccaletti, Ginestra Bianconi, Regino Criado, Charo I Del Genio, Jesús Gómez-Gardenes, Miguel Romance, Irene Sendina-Nadal, Zhen Wang, and Massimiliano Zanin.  The structure and dynamics of multilayer networks.  _Physics reports_ , 544(1):1–122, 2014.
  * Borgs et al. (2015) Christian Borgs, Jennifer Chayes, and Adam Smith.  Private graphon estimation for sparse graphs.  _Advances in Neural Information Processing Systems_ , 28:1369–1377, 2015.
  * Cape (2020) Joshua Cape.  Orthogonal procrustes and norm-dependent optimality.  _The Electronic Journal of Linear Algebra_ , 36:158–168, 2020.
  * Chang et al. (2021) Jinyuan Chang, Qiao Hu, Eric D Kolaczyk, Qiwei Yao, and Fengting Yi.  Edge differentially private estimation in the $\beta$-model via jittering and method of moments.  _arXiv preprint arXiv:2112.10151_ , 2021.
  * Charisopoulos et al. (2021) Vasileios Charisopoulos, Austin R Benson, and Anil Damle.  Communication-efficient distributed eigenspace estimation.  _SIAM Journal on Mathematics of Data Science_ , 3(4):1067–1092, 2021.
  * Chen et al. (2021a) Xi Chen, Jason D Lee, He Li, and Yun Yang.  Distributed estimation for principal component analysis: An enlarged eigenspace analysis.  _Journal of the American Statistical Association_ , pages 1–12, 2021a.
  * Chen et al. (2021b) Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al.  Spectral methods for data science: A statistical perspective.  _Foundations and Trends® in Machine Learning_ , 14(5):566–806, 2021b.
  * Damle and Sun (2020) Anil Damle and Yuekai Sun.  Uniform bounds for invariant subspace perturbations.  _SIAM Journal on Matrix Analysis and Applications_ , 41(3):1208–1236, 2020.
  * Davis and Kahan (1970) Chandler Davis and William Morton Kahan.  The rotation of eigenvectors by a perturbation. iii.  _SIAM Journal on Numerical Analysis_ , 7(1):1–46, 1970.
  * Dong et al. (2022) Jinshuo Dong, Aaron Roth, and Weijie J Su.  Gaussian differential privacy.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 84(1):3–37, 2022.
  * Duchi et al. (2018) John C Duchi, Michael I Jordan, and Martin J Wainwright.  Minimax optimal procedures for locally private estimation.  _Journal of the American Statistical Association_ , 113(521):182–201, 2018.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of Cryptography Conference_ , pages 265–284. Springer, 2006.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Dwork et al. (2017) Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman.  Exposed! a survey of attacks on private data.  _Annual Review of Statistics and Its Application_ , 4(1):61–84, 2017.
  * Fan et al. (2019) Jianqing Fan, Dong Wang, Kaizheng Wang, and Ziwei Zhu.  Distributed estimation of principal eigenspaces.  _Annals of statistics_ , 47(6):3009–3031, 2019\.
  * Fishkind et al. (2013) Donniell E Fishkind, Daniel L Sussman, Minh Tang, Joshua T Vogelstein, and Carey E Priebe.  Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown.  _SIAM Journal on Matrix Analysis and Applications_ , 34(1):23–39, 2013.
  * Gang et al. (2019) Arpita Gang, Haroon Raja, and Waheed U Bajwa.  Fast and communication-efficient distributed pca.  In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 7450–7454. IEEE, 2019.
  * Garber et al. (2017) Dan Garber, Ohad Shamir, and Nathan Srebro.  Communication-efficient algorithms for distributed stochastic principal component analysis.  In _International Conference on Machine Learning_ , pages 1203–1212. PMLR, 2017.
  * Greene and Cunningham (2013) Derek Greene and Pádraig Cunningham.  Producing a unified graph representation from multiple social network views.  In _Proceedings of the 5th annual ACM web science conference_ , pages 118–121, 2013.
  * Guo et al. (2020) Xiao Guo, Yixuan Qiu, Hai Zhang, and Xiangyu Chang.  Randomized spectral co-clustering for large-scale directed networks.  _arXiv preprint arXiv:2004.12164_ , 2020.
  * Guo et al. (2021) Xiao Guo, Xiang Li, Xiangyu Chang, Shusen Wang, and Zhihua Zhang.  Privacy-preserving distributed SVD via federated power.  _arXiv preprint arXiv:2103.00704_ , 2021.
  * Han et al. (2015) Qiuyi Han, Kevin Xu, and Edoardo Airoldi.  Consistent estimation of dynamic and multi-layer block models.  In _International Conference on Machine Learning_ , pages 1511–1520. PMLR, 2015.
  * Hehir et al. (2021) Jonathan Hehir, Aleksandra Slavkovic, and Xiaoyue Niu.  Consistency of privacy-preserving spectral clustering under the stochastic block model.  _arXiv preprint arXiv:2105.12615_ , 2021.
  * Huang et al. (2022) Sihan Huang, Haolei Weng, and Yang Feng.  Spectral clustering via adaptive layer aggregation for multi-layer networks.  _Journal of Computational and Graphical Statistics_ , pages 1–15, 2022.  doi: 10.1080/10618600.2022.2134874.
  * Imola et al. (2021) Jacob Imola, Takao Murakami, and Kamalika Chaudhuri.  Locally differentially private analysis of graph statistics.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 983–1000, 2021.
  * Ji et al. (2019) Tianxi Ji, Changqing Luo, Yifan Guo, Jinlong Ji, Weixian Liao, and Pan Li.  Differentially private community detection in attributed social networks.  In _Asian Conference on Machine Learning_ , pages 16–31. PMLR, 2019\.
  * Kairouz et al. (2021) 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.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Karwa and Slavković (2016) Vishesh Karwa and Aleksandra Slavković.  Inference using noisy degrees: Differentially private $\beta$-model and synthetic graphs.  _The Annals of Statistics_ , 44(1):87–112, 2016\.
  * Karwa et al. (2011) Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev.  Private analysis of graph structure.  _Proceedings of the VLDB Endowment_ , 4(11):1146–1157, 2011.
  * Karwa et al. (2017) Vishesh Karwa, Pavel N Krivitsky, and Aleksandra B Slavković.  Sharing social network data: differentially private estimation of exponential family random-graph models.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 66(3):481–500, 2017.
  * Kim and Leskovec (2012) Myunghwan Kim and Jure Leskovec.  Multiplicative attribute graph model of real-world networks.  _Internet mathematics_ , 8(1-2):113–160, 2012\.
  * Kivelä et al. (2014) Mikko Kivelä, Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter.  Multilayer networks.  _Journal of complex networks_ , 2(3):203–271, 2014.
  * Lei and Lin (2022) Jing Lei and Kevin Z Lin.  Bias-adjusted spectral clustering in multi-layer stochastic block models.  _Journal of the American Statistical Association_ , pages 1–13, 2022\.
  * Lei and Rinaldo (2015) Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  _The Annals of Statistics_ , 43(1):215–237, 2015\.
  * Lei et al. (2020) Jing Lei, Kehui Chen, and Brian Lynch.  Consistent community detection in multi-layer network data.  _Biometrika_ , 107(1):61–73, 2020.
  * Li et al. (2020) Tianxi Li, Elizaveta Levina, and Ji Zhu.  Network cross-validation by edge sampling.  _Biometrika_ , 107(2):257–276, 2020.
  * Li et al. (2021) Xiang Li, Shusen Wang, Kun Chen, and Zhihua Zhang.  Communication-efficient distributed svd via local power iterations.  In _International Conference on Machine Learning_ , pages 6504–6514. PMLR, 2021.
  * Liu et al. (2018) Fuchen Liu, David Choi, Lu Xie, and Kathryn Roeder.  Global spectral clustering in dynamic networks.  _Proceedings of the National Academy of Sciences_ , 115(5):927–932, 2018.
  * Liu et al. (2013) Jialu Liu, Chi Wang, Jing Gao, and Jiawei Han.  Multi-view clustering via joint nonnegative matrix factorization.  In _Proceedings of the 2013 SIAM international conference on data mining_ , pages 252–260. SIAM, 2013.
  * Ma et al. (2021) Shujie Ma, Liangjun Su, and Yichong Zhang.  Determining the number of communities in degree-corrected stochastic block models.  _Journal of machine learning research_ , 22(69), 2021.
  * MacDonald et al. (2022) Peter W MacDonald, Elizaveta Levina, and Ji Zhu.  Latent space models for multiplex networks with shared structure.  _Biometrika_ , 109(3):683–706, 2022.
  * McSherry (2009) Frank D McSherry.  Privacy integrated queries: an extensible platform for privacy-preserving data analysis.  In _Proceedings of the 2009 ACM SIGMOD International Conference on Management of data_ , pages 19–30, 2009.
  * Mir and Wright (2012) Darakhshan Mir and Rebecca N Wright.  A differentially private estimator for the stochastic kronecker graph model.  In _Proceedings of the 2012 Joint EDBT/ICDT Workshops_ , pages 167–176, 2012.
  * Mironov (2017) Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Mucha et al. (2010) Peter J Mucha, Thomas Richardson, Kevin Macon, Mason A Porter, and Jukka-Pekka Onnela.  Community structure in time-dependent, multiscale, and multiplex networks.  _science_ , 328(5980):876–878, 2010.
  * Nguyen et al. (2016) Hiep H Nguyen, Abdessamad Imine, and Michaël Rusinowitch.  Detecting communities under differential privacy.  In _Proceedings of the 2016 ACM on Workshop on Privacy in the Electronic Society_ , pages 83–93, 2016.
  * Nissim et al. (2007) Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  Smooth sensitivity and sampling in private data analysis.  In _Proceedings of the thirty-ninth annual ACM symposium on Theory of computing_ , pages 75–84, 2007.
  * Paul and Chen (2016) Subhadeep Paul and Yuguo Chen.  Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel.  _Electronic Journal of Statistics_ , 10(2):3807–3870, 2016.
  * Paul and Chen (2020) Subhadeep Paul and Yuguo Chen.  Spectral and matrix factorization methods for consistent community detection in multi-layer networks.  _The Annals of Statistics_ , 48(1):230–250, 2020\.
  * Qin et al. (2017) Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren.  Generating synthetic decentralized social graphs with local differential privacy.  In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , pages 425–438, 2017.
  * Rastogi et al. (2009) Vibhor Rastogi, Michael Hay, Gerome Miklau, and Dan Suciu.  Relationship privacy: output perturbation for queries with joins.  In _Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 107–116, 2009.
  * Rohe et al. (2011) Karl Rohe, Sourav Chatterhee, and Bin Yu.  Spectral clustering and the high-dimensional stochastic block model.  _The Annals of Statistics_ , 39(4):1878–1915, 2011.
  * Rossi and Magnani (2015) Luca Rossi and Matteo Magnani.  Towards effective visual analytics on multiplex and multilayer networks.  _Chaos, Solitons & Fractals_, 72:68–76, 2015.
  * Schönemann (1966) Peter H Schönemann.  A generalized solution of the orthogonal procrustes problem.  _Psychometrika_ , 31(1):1–10, 1966.
  * Seif et al. (2022) Mohamed Seif, Dung Nguyen, Anil Vullikanti, and Ravi Tandon.  Differentially private community detection for stochastic block models.  In _International Conference on Machine Learning_ , pages 15858–15894. PMLR, 2022.
  * Warner (1965) Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, 1965.
  * Zhang et al. (2022) Hai Zhang, Xiao Guo, and Xiangyu Chang.  Randomized spectral clustering in large-scale stochastic block models.  _Journal of Computational and Graphical Statistics_ , 31(3):887–906, 2022.