# Joint Community Detection and Rotational Synchronization via Semidefinite
Programming

Yifeng Fan Department of Electrical and Computer Engineering, University of
Illinois at Urbana-Champaign, Champaign, IL. Yuehaw Khoo Department of
Statistics, University of Chicago, Chicago, IL. Zhizhen Zhao11footnotemark: 1

###### Abstract

In the presence of heterogeneous data, where randomly rotated objects fall
into multiple underlying categories, it is challenging to simultaneously
classify them into clusters and synchronize them based on pairwise relations.
This gives rise to the joint problem of community detection and
synchronization. We propose a series of semidefinite relaxations, and prove
their exact recovery when extending the celebrated stochastic block model to
this new setting where both rotations and cluster identities are to be
determined. Numerical experiments demonstrate the efficacy of our proposed
algorithms and confirm our theoretical result which indicates a sharp phase
transition for exact recovery.

Keywords: Community detection, synchronization, semidefinite programming,
rotation group, stochastic block model

##  1 Introduction

In the presence of heterogeneous data, where randomly rotated objects fall
into multiple underlying categories, it is challenging to simultaneously
synchronize the objects and classify them into clusters. A motivating example
is the 2D class averaging in cryo-electron microscopy single particle
reconstruction [17, 41, 49]. It aims to cluster images taken from similar
viewing directions, rotationally align and average those images in order to
denoise the experimental data. Joint clustering and synchronization is an
emerging area that connects community detection [1, 16, 32, 2, 19, 20] and
synchronization [39, 7, 18]. Recently, several works discussed simultaneous
classification and mapping (alignment) [4, 24] and proposed different models
and algorithms. In [4], the authors addressed simultaneous permutation group
synchronization and clustering via a spectral method with rounding and used
the consistency of the mapping for clustering. In [24], the authors noticed
that both rotational alignment and classification are problems over compact
groups and proposed a harmonic analysis and semidefinite programming based
approach for solving alignment and classification simultaneously.

In this paper, we consider joint community detection and rotational
synchronization under a specific probabilistic model, which extends the
celebrated stochastic block model (SBM) [9, 10, 11, 15, 21, 22, 28, 29, 30,
31] to incorporate both the community structure and pairwise rotations. In
particular, we inherit the $G(n,p,q)$-SBM setting [26, 19, 2, 20] for the
graph connection as shown in Figure 1. Given a network of size $n$ with $K$
underlying disjoint communities, a random graph is generated such that each
pair of vertices are independently connected with probability $p$ (resp. $q$)
if they all belong to the same cluster (resp. different clusters). In
addition, each node $i$ is associated with a rotation
$\bm{R}_{i}\in\mathrm{SO}(d)$ which is assumed to be unknown, and a pairwise
alignment $\bm{R}_{ij}$ is observed on each connected edge. The noisy
observation $\bm{R}_{ij}$ is generated according to the probabilistic model
considered in [41, 13, 14]. When $i$ and $j$ belong to the same cluster we
observe the clean measurement $\bm{R}_{ij}=\bm{R}_{i}\bm{R}_{j}^{\top}$. When
they are in different clusters, $\bm{R}_{ij}$ is assumed to be uniformly drawn
from $\mathrm{SO}(d)$. The model considered here is different from the
probabilistic model in [4].

Figure 1: An illustration of our probabilistic model. We show a network with
two underlying communities in blue and orange respectively. Each vertex $i$ is
associated with a rotation $\bm{R}_{i}\in\mathrm{SO}(d)$. Edges between
vertices within the same cluster (resp. across clusters) independently
connected with probability $p$ (resp. $q$) are shown in solid lines (resp.
dash lines). The pairwise alignment $\bm{R}_{ij}$ between vertex $i$ and
vertex $j$ is observed on each edge $(i,j)$.

For such probabilistic model, a naive two-stage approach for recovery is to
(1) directly apply existing methods for community detection under SBM, and (2)
perform rotational synchronization for each identified community separately.
However, such approach does not take advantage of the _cycle consistency_ of
the alignments within each cluster and _inconsistency_ of the alignments
across clusters, and thus the clustering result might be sub-optimal. Instead,
we can exploit such consistency of rotational alignments to further improve
the identification of communities. For example, for three nodes $i,j$ and $k$,
their pairwise alignments satisfy
$\bm{R}_{ij}\bm{R}_{jk}\bm{R}_{ki}=\bm{I}_{d}$ if they belong to the same
cluster. In fact, the notion of cycle consistency has already been used in
synchronization problems [39, 33, 40, 14, 12, 38].

###  1.1 Our contributions

To incorporate the consistency of alignments in clustering, we formulate a
series of optimization problems in different settings which aim to
simultaneously recover the community structure and individual rotations. To
solve these non-convex problems, we apply semidefinite relaxation to obtain a
polynomial time solutions. Each resulting _semidefinite programming_ (SDP) is
tailored to accommodate different cluster structures with known or unknown
cluster sizes. For the case of two clusters, we provide dual certificates of
the corresponding SDPs, and derive sharp exact recovery conditions of the SDP.
In particular, our analysis relies on two novel concentration inequalities for
random matrices: (1) Given a series of independent random matrices
$\\{\bm{R}_{i}\\}_{i=1}^{n}$ uniformly drawn from $\mathrm{SO}(d)$, we derive
a sharp tail bound for the Frobenius norm of $\sum_{i=1}^{n}\bm{R}_{i}$ at
$d=2$. (2) Given an $m\times n$ block matrix $\bm{S}\in\mathbb{R}^{md\times
nd}$ with independent blocks uniformly drawn from $\mathrm{SO}(d)$, we show
that the operator norm $\|\bm{S}\|\sim\sqrt{n}+\sqrt{m}$, which can be
regarded as an extension of the norm bound of random matrices with independent
entries [5, 47, 43].

###  1.2 Organization

The rest of this paper is organized as follows. In Section 2 we formally
define our probabilistic model and formulate non-convex optimization problems
to solve for the cluster identities and rotations. In Section 3 we propose SDP
relaxations, and prove conditions for exact recovery for the case when there
are two underlying communities. Numerical results are given in Section 4 to
evaluate the proposed algorithm and demonstrate the predicted phase transition
for exact recovery. We conclude with some future directions in Section 5. For
the clarity of the presentation, most the proofs are provided in Appendix.

###  1.3 Notations

Throughout this paper we use the following notations: given a matrix $\bm{X}$,
its transpose is denoted by $\bm{X}^{\top}$. An $m\times n$ matrix of all
zeros is denoted by $\bm{0}_{m\times n}$ (or $\bm{0}$ for brevity). An
$n\times n$ identity matrix is denoted by $\bm{I}_{n}$.
$\bm{1}_{n}\in\mathbb{R}^{n}$ represents a vector of length $n$ with all ones.
The maximum and minimum eigenvalues of $\bm{X}$ are denoted by
$\lambda_{\text{max}}(\bm{X})$ and $\lambda_{\text{min}}(\bm{X})$
respectively. $\|\bm{X}\|$ and $\|\bm{X}\|_{\mathrm{F}}$ denote the operator
norm and the Frobenius norm of $\bm{X}$ respectively. For two matrices
$\bm{X}$ and $\bm{Y}$, their inner product is written as
$\langle\bm{X},\bm{Y}\rangle=\textrm{Tr}(\bm{X}^{\top}\bm{Y})$. For two non-
negative functions $f(n)$ and $g(n)$, $f(n)=O(g(n))$ (resp.
$f(n)=\Omega(g(n))$) denotes if there exists a constant $C>0$ such that
$f(n)\leq Cg(n)$ (resp. $f(n)\geq Cg(n)$) for all sufficiently large $n$,
$f(n)=o(g(n))$ denotes for every constant $C>0$ it holds $f(n)\leq Cg(n)$ for
all sufficiently large $n$. Specifically, given a matrix $\bm{X}$ of size
$md\times nd$, we usually treat it as an $m\times n$ block matrix such that
$\bm{X}_{ij}\in\mathbb{R}^{d\times d}$ denotes its $(i,j)$-th block, and the
$i$-th block row (resp. $j$-th block column) of $\bm{X}$ is referred to as the
sub-matrix that contains $\bm{X}_{ij}$ for all $j=1,\ldots,n$ (resp.
$i=1,\ldots,m$).

##  2 Our probabilistic model and problem formulation

We state our probabilistic model for joint community detection and rotation
synchronization as following: We assume that $n$ agents in a network fall in
$K$ underlying communities and each agent $i$ is associated with a rotation
matrix $\bm{R}_{i}\in\mathrm{SO}(d)$. The size of the $k$-th cluster is
denoted by $m_{k}$, and $C_{k}$ denotes the set of nodes belonging to the
$k$-th cluster. Each agent $i$ has an underlying cluster label
$C(i)\in\\{1,\dots,K\\}$. A random graph $G=(V,E)$ with node set $V$ and edge
set $E$ is generated from the underlying community structure and rotations of
the agents such that each pair of nodes $(i,j)$ in the graph is connected with
probability $p$ if agents $i$ and $j$ are in the same cluster, i.e.,
$C(i)=C(j)$, and with probability $q$ if the agents are not in the same
cluster, i.e., $C(i)\neq C(j)$. In addition, a relative rotational
transformation $\bm{R}_{ij}$ is observed on each edge $(i,j)\in E$. If
$C(i)=C(j)$, we obtain $\bm{R}_{ij}=\bm{R}_{i}\bm{R}_{j}^{\top}$ which equals
to the ground truth pairwise alignment. while if $C(i)\neq C(j)$, we assume
$\bm{R}_{ij}$ is a random rotation uniformly drawn from $\mathrm{SO}(d)$.
Given the above, we construct an observation matrix
$\bm{A}\in\mathbb{R}^{nd\times nd}$ whose $(i,j)$-th block
$\bm{A}_{ij}\in\mathbb{R}^{d\times d}$ satisfies

$\bm{A}_{ij}=\begin{cases}\bm{R}_{i}\bm{R}_{j}^{\top},&\;\text{with
probability }p\text{ and when }C(i)=C(j),\\\
\bm{R}_{ij}\sim\text{Unif}(\mathrm{SO}(d)),&\;\text{with probability }q\text{
and when }C(i)\neq C(j),\\\ \bm{0},&\;\text{otherwise}.\end{cases}$ (1)

$\bm{A}$ can be viewed as an extension of the adjacency matrix such that each
$\bm{A}_{ij}$ is not a $\\{0,1\\}$-valued entry, but rather a matrix that
indicates the connectivity as well as the observed rotation from $j$ to $i$.
In addition, let us denote $\bm{M}^{*}\in\mathbb{R}^{nd\times nd}$ as the
clean observation matrix where

$\bm{M}_{ij}^{*}=\begin{cases}\bm{R}_{i}\bm{R}_{j}^{\top},&C(i)=C(j),\\\
\bm{0},&\;\text{otherwise}.\end{cases}$ (2)

When $p\\!=\\!1$ and $q\\!=\\!0$, $\bm{M}^{*}$ is identical with $\bm{A}$.
Furthermore, we define $\bm{V}^{(k)}\in\mathbb{R}^{nd\times d}$ that indicates
the cluster membership and individual rotations for each cluster $k$, whose
$i$-th block $\bm{V}_{i}^{(k)}\in\mathbb{R}^{d\times d}$ satisfies

$\bm{V}_{i}^{(k)}=\begin{cases}\bm{R}_{i},&\;i\in C_{k},\\\
\bm{0},&\;\text{otherwise}.\end{cases}$ (3)

Then it is clear to see that
$\bm{M}^{*}=\sum_{k=1}^{K}\bm{V}^{(k)}(\bm{V}^{(k)})^{\top}$. Specifically for
the case of two clusters, without loss of generality we can assume that the
first $m_{1}$ nodes belong to $C_{1}$ and the remaining $m_{2}$ nodes belong
to the other cluster $C_{2}$. Then the ground truth $\bm{M}^{*}$ defined in
(2) has the following form:

$\bm{M}^{*}=\bm{V}^{(1)}(\bm{V}^{(1)})^{\top}+\bm{V}^{(2)}(\bm{V}^{(2)})^{\top}=\begin{pmatrix}\widetilde{\bm{M}}_{1}^{*}&\bm{0}\\\
\bm{0}&\widetilde{\bm{M}}_{2}^{*}\end{pmatrix}.$ (4)

where $\widetilde{\bm{M}}_{1}^{*}\in\mathbb{R}^{m_{1}d\times m_{1}d}$ and
$\widetilde{\bm{M}}_{2}^{*}\in\mathbb{R}^{m_{2}d\times m_{2}d}$.

Based on the model, we state our problem of joint community detection and
synchronization as the following optimization program:

$\max_{\hat{\bm{R}}_{1},\ldots,\hat{\bm{R}}_{n}\in\mathrm{SO}(d),\;\hat{C}_{1},\ldots,\hat{C}_{K}}\sum_{i,j\in\hat{C}_{k},\forall
k}\left\langle\bm{A}_{ij},\;\hat{\bm{R}}_{i}\hat{\bm{R}}_{j}^{\top}\right\rangle,$
(5)

where $\hat{C}_{k}$ denotes the set of nodes identified for the $k$-th cluster
and $\hat{\bm{R}}_{i}\in\mathrm{SO}(d)$ denotes the rotation identified for
node $i$. Different from community detection under SBM, (5) aims to determine
$\\{\hat{C}_{i}\\}_{i=1}^{K}$ and $\\{\hat{\bm{R}}_{i}\\}_{i=1}^{n}$
simultaneously such that the cluster membership relies on both the edge
connections and the consistency of alignments. By introducing
$\bm{M}\in\mathbb{R}^{nd\times nd}$ with its $(i,j)$-th block

$\bm{M}_{ij}=\begin{cases}\hat{\bm{R}}_{i}\hat{\bm{R}}_{j}^{\top},&\;\hat{C}(i)=\hat{C}(j),\\\
\bm{0},&\;\text{otherwise},\end{cases}$ (6)

we can recast (5) as the following program:

$\displaystyle\max_{\bm{M}\in\mathbb{R}^{nd\times nd}}$
$\displaystyle\quad\left\langle\bm{A},\bm{M}\right\rangle\quad\mathrm{s.t.}\quad\text{$\bm{M}$
satisfies the form in \eqref{eq:Mform}}.$ (7)

Notably, if the size of each cluster is known, an additional constraint should
be added as

$\displaystyle\max_{\bm{M}\in\mathbb{R}^{nd\times nd}}$
$\displaystyle\quad\left\langle\bm{A},\bm{M}\right\rangle$ (8)
$\displaystyle\mathrm{s.t.}$ $\bm{M}$ has the form in (6), and
$|\hat{C}_{k}|=m_{k}$, $k=1,\ldots,K$.

Since directly solving (7) or (8) is clearly non-convex and computationally
intractable, in the following section we propose semidefinite relaxation to
efficiently solve them.

##  3 Semidefinite relaxation

For simplicity, in Sections 3.1–3.3, we focus on the case of two clusters
(i.e., $K\\!=\\!2$). In particular, we consider the following three scenarios:
(1) two cluster sizes $m_{1}=m_{2}=n/2$ are equal and known; (2) two cluster
sizes $m_{1},m_{2}$ are unequal and known; (3) two cluster sizes are unknown.
For each scenario, we develop its tailored SDP and provide corresponding
performance guarantee. In Section 3.4, we extend our approach to general cases
with an arbitrary number of underlying clusters.

###  3.1 Two equal-sized clusters with known cluster sizes

In this section, we study the case of two clusters where the cluster sizes
$m_{1}=m_{2}=m$ are equal and known to us. In this case, the ground truth
$\bm{M}^{*}$ in (4) satisfies the following convex constraints:

  1. 1.

$\bm{M}^{*}$ is positive semi-definite, i.e. $\bm{M}^{*}\succeq 0$.

  2. 2.

Each diagonal block of $\bm{M}^{*}$ is an identity matrix, i.e.
$\bm{M}^{*}_{ii}=\bm{I}_{d}$, $i=1,\ldots,n$.

  3. 3.

The $i$-th block row of $\bm{M}^{*}$ satisfies
$\sum_{j=1}^{n}\|\bm{M}^{*}_{ij}\|_{\mathrm{F}}\leq m\sqrt{d}$,
$i=1,\ldots,n$.

Notably, instead of the last constraint, we want the equality
$\sum_{j=1}^{n}\|\bm{M}^{*}_{ij}\|_{\mathrm{F}}\\!=\\!m\sqrt{d}$. However, the
norm equality constraint is non-convex and therefore a convex relaxation by
replacing “$=$” with “$\leq$” is needed. Based on these properties of
$\bm{M}^{*}$, a semidefinite relaxation of (8) can be stated as

$\displaystyle\bm{M}_{\text{SDP}}$
$\displaystyle=\operatorname*{arg\,max}_{\bm{M}\in\mathbb{R}^{nd\times
nd}}\quad\left\langle\bm{A},\bm{M}\right\rangle$ (9)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\quad\bm{M}\succeq
0,\quad\bm{M}_{ii}=\bm{I}_{d},\quad\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq
m\sqrt{d},\quad i=1,\ldots,n.$

As a result, (9) is a semidefinite program (SDP) which can be efficiently
solved by interior-point methods with polynomial complexity [46]. We remark
that in the context of community detection, SDPs similar to (9) have been
studied in [2, 19] on SBM with two equal-sized clusters. In their problem,
each $\bm{M}_{ij}$ is a scalar and a convex equality constraint
$\sum_{i=1}^{n}\bm{M}_{ij}=m$ can be imposed. In contrast, we use a convex
inequality constraint on $\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}$.

To characterize the performance of (9), we identify the conditions on the
model parameters $(p,q,n)$ such that (9) achieves exact recovery, i.e.,
$\bm{M}_{\text{SDP}}\\!=\\!\bm{M}^{*}$ as follows.

######  Theorem 3.1.

Let $p=\alpha\log n/n$ and $q=\beta\log n/n$. For sufficiently large $n$, (9)
achieves exact recovery with probability $1-n^{-\Omega(1)}$ if

$\alpha-\sqrt{2\ell\beta}\log\left(\frac{e\alpha}{\sqrt{2\ell\beta}}\right)>2,\quad\text{where}\quad\ell=\begin{cases}2,&\quad\text{when
$d>2$},\\\ 1,&\quad\text{when $d=2$}.\end{cases}$ (10)

Notice that the function $f(\tau):=\alpha-\tau\log(e\alpha/\tau)$
monotonically decreases for $\tau\in(0,\alpha]$, therefore Theorem 10 implies
the SDP (9) achieves exact recovery if $\beta$ is smaller than certain
threshold determined by $\alpha$. Also, we remark that in (10), the difference
between the case for $d=2$ and $d>2$ lies in the different concentration
inequalities of random rotation matrix used in the proof (see Section 3.1.1
for detail). However, we conjecture the condition for $d>2$ can be further
improved such that the constant factor $\ell$ can be smaller than $2$.
Although the condition in (10) is sufficient but may not be necessary, in
experiments we show the threshold of (10) sharply characterizes the empirical
phase transition boundary for exact recovery when $d=2$ (see Figure 3).

In the following section, we outline the key steps in the proof of Theorem 10
based on showing the dual certificate of the ground truth
$\bm{M}_{\text{SDP}}=\bm{M}^{*}$ for (9). The complete proofs of the lemmas in
Section 3.1 are deferred to Appendix B.1.

####  3.1.1 The sketch of proof

Our proof consists of the following three steps:

Step 1: Derive KKT conditions, uniqueness and optimality of $\bm{M}^{*}$. The
Lagrangian of the optimization problem (9) is,

$L(\bm{M},\bm{\Lambda},\bm{Z},\bm{\mu})=-\left\langle\bm{A},\bm{M}\right\rangle-\left\langle\bm{\Lambda},\bm{M}\right\rangle-\sum_{i=1}^{n}\left\langle\bm{Z}_{i},\bm{M}_{ii}-\bm{I}_{d}\right\rangle-\sum_{i=1}^{n}\bigg{\langle}\mu_{i},m\sqrt{d}-\sum_{j=1}^{n}\left\|\bm{M}_{ij}\right\|_{\mathrm{F}}\bigg{\rangle},$

where $\bm{\Lambda}$,
$\bm{Z}=\mathrm{diag}\left(\left\\{\bm{Z}_{i}\right\\}_{i=1}^{n}\right)$ and
$\bm{\mu}=\left\\{\mu_{i}\right\\}_{i=1}^{n}$ are the dual variables
associated with the constraints $\bm{M}\succeq 0,\;\bm{M}_{ii}=\bm{I}_{d}$ and
$\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq m\sqrt{d}$ for $i=1,\ldots,n$.
Then the KKT conditions at $\bm{M}=\bm{M}^{*}$ are listed as,

$\displaystyle\bullet\;\textit{Stationarity:}\;$
$\displaystyle-\bm{A}-\bm{\Lambda}-\mathrm{diag}(\\{\bm{Z}_{i}\\}_{i=1}^{n})+\bm{\Theta}+\bm{\Theta}^{\top}=\bm{0},$
(11)
$\displaystyle\bm{\Theta}=\left[\bm{\Theta}_{ij}\right]_{i,j=1}^{n},\quad\bm{\Theta}_{ij}=\begin{cases}\displaystyle\mu_{i}\bm{M}_{ij}^{*}/\sqrt{d},&\bm{M}_{ij}^{*}\neq\bm{0},\\\
\mu_{i}\bm{\alpha}_{ij},\;\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq
1,&\bm{M}_{ij}^{*}=\bm{0}.\end{cases}$ (12)
$\displaystyle\bullet\;\textit{Comp. slackness:}\quad\quad$
$\displaystyle\left\langle\bm{\Lambda},\bm{M}^{*}\right\rangle=0,\quad\bigg{\langle}\mu_{i},m\sqrt{d}-\sum_{j=1}^{n}\left\|\bm{M}_{ij}^{*}\right\|_{\mathrm{F}}\bigg{\rangle}=0,\;i=1,\ldots,n.$
(13) $\displaystyle\bullet\;\textit{Dual feasibility:}\;$
$\displaystyle\bm{\Lambda}\succeq 0,\quad\mu_{i}\geq 0,\quad i=1,\ldots,n.$
(14)

Notably, $\bm{\alpha}_{ij}$ in (12) can be chosen arbitrarily as long as
$\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq 1$, because the derivative of
$\|\bm{M}_{ij}\|_{\mathrm{F}}$ is undefined at $\bm{M}_{ij}=\bm{0}$. Based on
the KKT conditions, the following result establishes the uniqueness and
optimality of $\bm{M}^{*}$:

######  Lemma 3.2.

Given $\bm{M}^{*}$ defined in (2), suppose there exists dual variables
$\bm{\Lambda}$, $\bm{Z}$, $\\{\mu_{i}\\}_{i=1}^{n}$ and
$\left\\{\bm{\alpha}_{ij}\right\\}_{(i,j):M^{*}_{ij}=\bm{0}}$ that satisfy the
KKT conditions (11) - (14) as well as

$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*}),$ (15)

where $\mathcal{N}(\cdot)$ and $\mathcal{R}(\cdot)$ denote the null space and
column space respectively. Then $\bm{M}^{*}$ is the optimal and unique
solution to (9).

Step 2: Construct dual variables. Without loss of generality, we assume the
rotation matrix $\bm{R}_{i}=\bm{I}_{d}$ for each $i$. Then for any pair of
$(i,j)$ that $C(i)=C(j)$, we have $\bm{M}_{ij}^{*}=\bm{I}_{d}$ and
$\bm{A}_{ij}=r_{ij}\bm{I}_{d}$, where $r_{ij}\in\\{0,1\\}$ is a Bernoulli
random variable such that $\mathbb{P}\\{r_{ij}=1\\}=p$. Our next step is to
find dual variables that satisfy the conditions in Lemma 3.2. To this end,
inspired by [26] we make the following guess for the dual variables.

######  Lemma 3.3.

The following dual variables satisfy the KKT conditions (11) - (13) and
$\mu_{i}\geq 0,\;i=1,\ldots,n$ in (14):

$\displaystyle\bm{\Theta}_{ij}$
$\displaystyle=\begin{cases}\displaystyle\mu_{i}\bm{I}_{d}/\sqrt{d},&C(i)=C(j),\\\
\widetilde{\bm{\alpha}}_{i},&C(i)\neq C(j),\end{cases}\quad$
$\displaystyle\widetilde{\bm{\alpha}}_{i}=\frac{1}{m}\sum_{j:C(i)\neq
C(j)}\bm{A}_{ij}-\frac{1}{2m^{2}}\sum_{j:C(i)\neq
C(j)}\sum_{s:C(s)=C(i)}\bm{A}_{sj},$ $\displaystyle\mu_{i}$
$\displaystyle=\|\widetilde{\bm{\alpha}}_{i}\|_{\mathrm{F}},$
$\displaystyle\bm{Z}_{i}=\bigg{(}\frac{m\mu_{i}}{\sqrt{d}}+\sum_{s:C(s)=C(i)}\bigg{(}\frac{\mu_{s}}{\sqrt{d}}-r_{is}\bigg{)}\bigg{)}\bm{I}_{d},$

$\hskip
30.72902pt\bm{\Lambda}=-\bm{A}-\mathrm{diag}\left(\\{\bm{Z}_{i}\\}_{i=1}^{n}\right)+\bm{\Theta}+\bm{\Theta}^{\top}.$

When constructing the dual certificate, for fixed $i,j$ where $C(i)\neq C(j)$,
$\bm{\Theta}_{ij}$ can have many choices. Here we assume $\bm{\Theta}_{ij}$ is
identical for all $j$ when $i$ and $j$ are not in the same cluster. This
choice allows us to determine all dual variables via the KKT conditions and
(15). Now it remains to check under what condition on $(\alpha,\beta)$ does
$\bm{\Lambda}$ satisfy both $\bm{\Lambda}\succeq 0$ and (15). To this end, we
use the following property for $\bm{\Lambda}$.

######  Lemma 3.4.

Given the dual variables in Lemma 3.3, $\bm{\Lambda}$ can be expressed as

$\bm{\Lambda}=(\bm{I}_{nd}-\bm{\Pi})\underbrace{(\mathbb{E}[\bm{A}]-\bm{A}-\bm{Z}+p\bm{I}_{nd})}_{=:\widetilde{\bm{\Lambda}}}(\bm{I}_{nd}-\bm{\Pi}),\quad\text{where}\quad\bm{\Pi}=\left(\frac{1}{m}\right)\bm{M}^{*}.$
(16)

Then, $\bm{\Lambda}\succeq 0$ and
$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*})$ are satisfied if
$\widetilde{\bm{\Lambda}}\succ 0$.

Step 3: Find the condition for $\widetilde{\bm{\Lambda}}\succ 0$. Applying
Weyl’s inequality [42] yields
$\lambda_{\text{min}}(\widetilde{\bm{\Lambda}})\geq\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})-\|\mathbb{E}[\bm{A}]-\bm{\bm{A}}\|$.
Then for $\widetilde{\bm{\Lambda}}\succ 0$, it suffices to show

$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})>\|\mathbb{E}[\bm{A}]-\bm{\bm{A}}\|.$
(17)

To this end, we have the following bound for
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})$.

######  Lemma 3.5.

Let $p=\alpha\log n/n,q=\beta\log n/n$. For $n$ that is sufficiently large,

$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})\geq\min_{i}x_{i}-\max_{i}y_{i}-\max\\{\epsilon_{1},\epsilon_{2}\\}+p$

where

  1. 1.

$x_{i}:=\sum_{s:C(s)=C(i)}r_{is}$, which satisfies

$\min_{i}x_{i}\geq\frac{\tau}{2}\log n\quad\text{with probability}\quad
1-n^{1-\frac{1}{2}\left(\alpha-\tau\log\left(\frac{e\alpha}{\tau}\right)+o(1)\right)},$

for $\tau\in[0,\alpha)$ such that
$1-\frac{1}{2}\left(\alpha-\tau\log\left(\frac{e\alpha}{\tau}\right)+o(1)\right)<0$;

  2. 2.

$y_{i}:=\frac{m\mu_{i}}{\sqrt{d}}$, which satisfies

$\max_{i}y_{i}\leq\sqrt{\frac{\ell(c+1)\beta}{2}}\log n+o(\log
n)\quad\text{with probability}\quad
1-n^{-c},\quad\ell=\begin{cases}2,&\;d>2,\\\ 1,&\;d=2;\end{cases}$

  3. 3.

$\epsilon_{1}:=\frac{1}{\sqrt{d}}\sum_{s\in C_{1}}\mu_{s}$ and
$\epsilon_{2}:=\frac{1}{\sqrt{d}}\sum_{s\in C_{2}}\mu_{s}$, which satisfy

$\max\\{\epsilon_{1},\epsilon_{2}\\}\leq\frac{2c}{3}\log n+o(\log
n)\quad\text{with probability}\quad 1-n^{-c}.$

In Lemma 3.5, $x_{i}\sim\textrm{Binom}(m,p)$ follows the binomial
distribution, which is bounded by the result in [19, Lemma 2]. For $y_{i}$, it
depends on the bound of $\mu_{i}$, according to Lemma 3.3, this further relies
on bounding $\|\sum_{i=1}^{m}\bm{R}_{i}\|_{\mathrm{F}}$ where
$\\{\bm{R}_{i}\\}_{i=1}^{m}$ are i.i.d. random matrices uniformly drawn from
$\mathrm{SO}(d)$. When $d>2$, $\|\sum_{i=1}^{m}\bm{R}_{i}\|_{\mathrm{F}}$ is
bounded by matrix Bernstein inequality [45], and when $d=2$, a sharper result
is derived by explicitly computing the moments of
$\|\sum_{i=1}^{m}\bm{R}_{i}\|_{\mathrm{F}}$ and then apply Markov inequality,
which are detailed in Appendix A.2. For $\epsilon_{1}$ and $\epsilon_{2}$, by
definition they depend on the concentration of $\mu_{i}$ and are thus bounded
by Bernstein’s inequality [47].

It remains to bound $\|\mathbb{E}[\bm{A}]-\bm{A}\|$. If $\bm{A}$ is an
adjacency matrix where $\bm{A}_{ij}\in\\{0,1\\}$, the upper bound of
$\|\mathbb{E}[\bm{A}]-\bm{A}\|$ has been studied in the context of SBM (e.g.
[19, 25]). However, here $\bm{A}_{ij}$ is a random rotation matrix for
$C(i)\neq C(j)$ rather than being $\\{0,1\\}$-valued. Therefore, in Appendix
A.3, we derive an upper bound of the operator norm of a random block matrix in
Theorem A.7, which leads us to the following result for
$\|\mathbb{E}[\bm{A}]-\bm{A}\|$.

######  Lemma 3.6.

Let the two clusters be of size $m_{1}$ and $m_{2}$ $(m_{1}+m_{2}=n)$, and
$p,q=\Omega(\log n/n)$. Then for $\bm{A}$ defined in (1), it satisfies

$\|\mathbb{E}[\bm{A}]-\bm{A}\|\leq
c_{1}(\sqrt{pm_{1}}+\sqrt{pm_{2}})+c_{2}(\sqrt{qm_{1}}+\sqrt{qm_{2}})+O(\sqrt{\log
n})$

with probability $1-n^{-c}$ for $c>0$, where $c_{1},c_{2}>0$ are some
universal constants.

###### Proof of Theorem 10.

By applying the union bound on $\min_{i}x_{i}$, $\max_{i}y_{i}$ and
$\max\\{\epsilon_{1},\epsilon_{2}\\}$ in Lemma 3.5, we obtain

$\lambda_{\text{min}}(p\bm{I}_{d}-\bm{Z})\geq\bigg{(}\frac{\tau}{2}-\sqrt{\frac{\ell(c+1)\beta}{2}}-\frac{2c}{3}\bigg{)}\log
n+o(\log n),$

with probability $1-n^{-\Omega(1)}$, as long as the condition in Lemma 3.5
that

$1-\frac{1}{2}\left(\alpha-\tau\log\left(\frac{e\alpha}{\tau}\right)\right)<0$
(18)

is satisfied. Also, from Lemma 3.6, we have
$\|\mathbb{E}[\bm{A}]-\bm{A}\|=O(\sqrt{\log n})$ with high probability. This
implies, as $n$ is sufficiently large, (17) holds if
$\lambda_{\text{min}}(p\bm{I}_{d}-\bm{Z})=\Omega(\log n)$, that is equivalent
to $\frac{\tau}{2}-\sqrt{\frac{\ell(c+1)\beta}{2}}-\frac{2c}{3}>0$. By taking
$c\rightarrow 0$ to be sufficiently small, it reduces to
$\tau>\sqrt{2\ell\beta}$. It remains to ensure there exists a
$\tau\in(0,\alpha]$ that satisfies (18). To this end, since the LHS of (18) is
monotonically increasing for $\tau\in(0,\alpha]$, by choosing
$\tau\rightarrow\sqrt{2\ell\beta}$ the condition (18) becomes (10), which is
the condition for exact recovery. ∎

###  3.2 Two unequal-sized clusters with known cluster size

Now we consider the case where the two cluster sizes $m_{1},m_{2}$ are unequal
and known to us. In this case, the ground truth $\bm{M}^{*}$ still has the
form in (4) and convex relaxations similar to (9) can be applied. However,
unlike the equal-sized case, the row-sum constraint satisfies
$\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}=m_{1}\sqrt{d}$ if $i\in C_{1}$ and
$\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}=m_{2}\sqrt{d}$ if $i\in C_{2}$.
Therefore a convex constraint can be imposed as
$\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\max\\{m_{1},\;m_{2}\\}\sqrt{d}$.
So this imposes an upper-bound on the cluster sizes, based on the size of the
larger cluster. Besides, to incorporate the information of the smaller cluster
of the two, we consider an additional constraint on the sum of all blocks as
$\sum_{i,j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq(m_{1}^{2}+m_{2}^{2})\sqrt{d}$.
In this way, the resulting SDP is

$\displaystyle\bm{M}_{\text{SDP}}$
$\displaystyle=\operatorname*{arg\,max}_{\bm{M}\in\mathbb{R}^{nd\times
nd}}\quad\left\langle\bm{A},\bm{M}\right\rangle$ (19)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\quad\bm{M}\succeq
0,\quad\bm{M}_{ii}=\bm{I}_{d},\quad\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\max\\{m_{1},m_{2}\\}\sqrt{d},\quad\forall
i=1,\ldots,n,$
$\displaystyle\quad\sum_{i,j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\left(m_{1}^{2}+m_{2}^{2}\right)\sqrt{d}.$

For (19), the condition for exact recovery is derived as the following.

######  Theorem 3.7.

Let $p=\alpha\log n/n,q=\beta\log n/n$. Suppose $m_{1}=\rho n,m_{2}=(1-\rho)n$
for some $\rho\in(1/2,1)$ such that $m_{1}>m_{2}$. Let
$\tau_{1}^{*},\tau_{2}^{*}\in[0,\alpha)$ be the roots of the equations

$\alpha-\tau_{1}^{*}\log\left(\frac{e\alpha}{\tau_{1}^{*}}\right)=\frac{1}{\rho},\quad\alpha-\tau_{2}^{*}\log\left(\frac{e\alpha}{\tau_{2}^{*}}\right)=\frac{1}{1-\rho}.$
(20)

As $n$ is sufficiently large, (19) achieves exact recovery with probability
$1-n^{-\Omega(1)}$ if

$\begin{cases}\displaystyle\alpha>\frac{1}{1-\rho},\quad&\text{when
$\beta=0$},\\\
\displaystyle\alpha>\frac{1}{1-\rho},\quad\frac{\tau_{1}^{*}}{\delta_{2}}>1\quad\text{and}\quad\frac{\tau_{1}^{*}}{\delta_{1}}>\max\left\\{1-\frac{\tau_{2}^{*}}{2\delta_{2}},\;\frac{1}{2}\right\\},\quad&\text{when
$\beta>0$},\end{cases}$ (21)

where
$\delta_{1}:=\left(\frac{2}{\sqrt{\rho}}\\!+\\!\frac{1}{\sqrt{1-\rho}}\right)\sqrt{l\beta},\;\delta_{2}:=\left(\frac{1}{\sqrt{\rho}}\\!+\\!\frac{1}{\sqrt{1-\rho}}\right)\sqrt{l\beta}$.
$\ell=2$ when $d>2$ and $\ell=1$ when $d=2$.

Note that the function $f(\tau):=\alpha-\tau\log\left(e\alpha/\tau\right)$
monotonically decreases for $\tau\in[0,\alpha)$, and it satisfies
$f(\alpha)=0$ and $\lim_{\tau\rightarrow 0}f(\tau)=\alpha$. Therefore, there
exists a unique pair of solutions $\tau_{1}^{*},\tau_{2}^{*}$ of (20) for
$\tau_{1}^{*},\tau_{2}^{*}\in[0,\alpha)$ when $\alpha>1/(1-\rho)$. In the
following section, we outline the key steps for proving Theorem 3.7 and leave
the detail to Appendix B.2.

####  3.2.1 The sketch of proof

The steps for proving Theorem 3.7 are similar to those outlined in Section
3.1.1, while a considerable amount of effort is devoted to handle the
imbalanced clusters and the additional constraint
$\sum_{i,j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\left(m_{1}^{2}+m_{2}^{2}\right)\sqrt{d}$.

Step 1: Derive KKT conditions, uniqueness and optimality of $\bm{M}^{*}$. The
Lagrangian of (19) is given as

$\displaystyle L$
$\displaystyle=-\left\langle\bm{A},\bm{M}\right\rangle-\left\langle\bm{\Lambda},\bm{M}\right\rangle-\sum_{i=1}^{n}\left\langle\bm{Z}_{i},\bm{M}_{ii}-\bm{I}_{d}\right\rangle+\sum_{i=1}^{n}\bigg{\langle}\mu_{i},\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}-m_{1}\sqrt{d}\bigg{\rangle}$
$\displaystyle\quad+\nu\bigg{(}\sum_{i,j}\|\bm{M}_{ij}\|_{\mathrm{F}}-(m_{1}^{2}+m_{2}^{2})\sqrt{d}\bigg{)},$

where $\nu$ is the dual variable associated with the extra constraint. Then we
list the KKT conditions of (19) when $\bm{M}=\bm{M}^{*}$ as

$\displaystyle\bullet\;\textit{Stationarity:}\;$
$\displaystyle-\bm{A}-\bm{\Lambda}-\operatorname{diag}(\\{\bm{Z}_{i}\\}_{i=1}^{n})+\bm{\Theta}+\bm{\Theta}^{\top}=\bm{0},$
(22)
$\displaystyle\bm{\Theta}\\!=\\![\bm{\Theta}_{ij}]_{i,j=1}^{n},\quad\bm{\Theta}_{ij}\\!=\\!\begin{cases}\displaystyle(\mu_{i}+\nu)\bm{M}_{ij}^{*}/\sqrt{d},&\bm{M}_{ij}^{*}\neq\bm{0},\\\
(\mu_{i}+\nu)\bm{\alpha}_{ij},\;\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq
1,&\bm{M}_{ij}^{*}=\bm{0}.\end{cases}$ (23)
$\displaystyle\bullet\;\textit{Comp. slackness:}\quad$
$\displaystyle\left\langle\bm{\Lambda},\bm{M}^{*}\right\rangle=0,\quad\nu\bigg{(}\sum_{i,j}\|\bm{M}_{ij}^{*}\|_{\mathrm{F}}-(m_{1}^{2}+m_{2}^{2})\sqrt{d}\bigg{)}=0,$
(24)
$\displaystyle\bigg{\langle}\mu_{i},m_{1}\sqrt{d}-\sum_{j=1}^{n}\|\bm{M}^{*}_{ij}\|_{\mathrm{F}}\bigg{\rangle}=0,\quad
i=1,\ldots,n,$ (25) $\displaystyle\bullet\;\textit{Dual feasibility:}\;$
$\displaystyle\bm{\Lambda}\succeq 0,\quad\nu\geq 0,\quad\mu_{i}\geq 0,\quad
i=1,\ldots,n.$ (26)

Again, the following lemma establishes the uniqueness and optimality of
$\bm{M}^{*}$:

######  Lemma 3.8.

Given $\bm{M}^{*}$ defined in (2), suppose there exists dual variables
$\bm{\Lambda}$, $\bm{Z}$, $\\{\mu_{i}\\}_{i=1}^{n}$,
$\left\\{\bm{\alpha}_{ij}\right\\}_{(i,j):M^{*}_{ij}=\bm{0}}$ and $\nu$ that
satisfy the KKT conditions (22) - (26) as well as

$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*}).$ (27)

Then $\bm{M}^{*}$ is the optimal and unique solution to (19).

Step 2: Construct dual variables. Again, assuming $\bm{M}^{*}_{ij}=\bm{I}_{d}$
and $\bm{A}_{ij}=r_{ij}\bm{I}_{d}$ for any $(i,j)$ that $C(i)=C(j)$. we make
the following guess of the dual variables.

######  Lemma 3.9.

With a constant $\gamma\in[1/2,1]$, the following forms of the dual variables
satisfy (22) - (25) and $\nu\geq 0$, $\mu_{i}\geq 0$, for $i=1,\ldots,n$ in
(26).

$\displaystyle\widetilde{\bm{\alpha}}_{ij}$
$\displaystyle=\frac{1}{m_{1}}\sum_{s_{1}\in
C_{1}}\bm{A}_{s_{1}j}+\frac{1}{m_{2}}\sum_{s_{2}\in
C_{2}}\bm{A}_{is_{2}}-\frac{1}{m_{1}m_{2}}\sum_{s_{1}\in C_{1}}\sum_{s_{2}\in
C_{2}}\bm{A}_{s_{1}s_{2}},\quad i\in C_{1},j\in C_{2},$
$\displaystyle\bm{\Theta}_{ij}$
$\displaystyle=\begin{cases}\displaystyle(\mu_{i}+\nu)\bm{I}_{d}/\sqrt{d},&C(i)=C(j),\\\
\gamma\widetilde{\bm{\alpha}}_{ij},&i\in C_{1},j\in C_{2},\\\
(1-\gamma)\widetilde{\bm{\alpha}}_{ji}^{\top},&i\in C_{2},j\in
C_{1},\end{cases}\quad\quad\mu_{i}=\begin{cases}\displaystyle\max\\{0,\gamma\cdot\max_{j\in
C_{2}}\|\widetilde{\bm{\alpha}}_{ij}\|_{\mathrm{F}}-\nu\\},&\quad i\in
C_{1},\\\ \displaystyle 0,&\quad i\in C_{2},\end{cases}$ $\displaystyle\nu$
$\displaystyle=(1-\gamma)\max_{i\in C_{2},j\in
C_{1}}\|\widetilde{\bm{\alpha}}_{ji}\|_{\mathrm{F}},\hskip
7.11317pt\bm{Z}_{i}=\begin{cases}\displaystyle\bigg{(}\frac{m_{1}(\mu_{i}+\nu)}{\sqrt{d}}+\sum_{s\in
C_{1}}\bigg{(}\frac{\mu_{s}+\nu}{\sqrt{d}}-r_{is}\bigg{)}\bigg{)}\bm{I}_{d},&\quad
i\in C_{1},\\\ \displaystyle\bigg{(}\frac{2m_{2}\nu}{\sqrt{d}}-\sum_{s\in
C_{2}}r_{is}\bigg{)}\bm{I}_{d},&\quad i\in C_{2},\end{cases}$

$\hskip
24.18501pt\bm{\Lambda}=-\bm{A}-\mathrm{diag}\left(\\{\bm{Z}_{i}\\}_{i=1}^{n}\right)+\bm{\Theta}+\bm{\Theta}^{\top}.$

Furthermore, $\bm{\Lambda}$ can be simplified as the following form.

######  Lemma 3.10.

Given the dual variables in Lemma 3.9, $\bm{\Lambda}$ can be expressed as

$\bm{\Lambda}=(\bm{I}_{nd}-\bm{\Pi})\underbrace{(\mathbb{E}[\bm{A}]-\bm{A}-\bm{Z}+p\bm{I}_{nd})}_{=:\widetilde{\bm{\Lambda}}}(\bm{I}_{nd}-\bm{\Pi})\quad\text{where}\quad\bm{\Pi}:=\begin{pmatrix}\widetilde{\bm{M}}^{*}_{1}/m_{1}&\bm{0}\\\
\bm{0}&\widetilde{\bm{M}}^{*}_{2}/m_{2}\end{pmatrix}.$

Then, $\bm{\Lambda}\succeq 0$ and
$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*})$ are satisfied if
$\widetilde{\bm{\Lambda}}\succ 0$.

Different from Step 2 in Section 3.1.1, here, we adopt a new way to construct
$\bm{\Theta_{ij}}$ in order to obtain a threshold close to the empirical phase
transition line by tuning $\gamma$. The parameter $\gamma$ controls the values
of $\nu$, $\mu_{i}$, and the diagonal entries of $\bm{Z}_{i}$. As we shall see
in the next step, by adjusting $\gamma$, we can balance the diagonal values of
$\bm{Z}_{i}$ for $i\in C_{1}$ and $i\in C_{2}$, which helps to ensure
$\widetilde{\bm{\Lambda}}\succ 0$. We remark that our current construction of
the dual variables may still be sub-optimal, which indicates the condition in
(21) is sufficient but not necessary. Finding the optimal dual appears to be
challenging and is left for future work.

Step 3: Find the condition for $\widetilde{\bm{\Lambda}}\succ 0$. Again, by
using the same argument as in Section 3.1.1, one can see that for exact
recovery it suffices to show
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})>\|\mathbb{E}[\bm{A}]-\bm{\bm{A}}\|$.
Here we get the following bound for
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})$.

######  Lemma 3.11.

Let $p=\alpha\log n/n$, $q=\beta\log n/n$ and $\gamma\in[1/2,1]$. Suppose
$m_{1}=\rho n$ and $m_{2}=(1-\rho)n$ for some $\rho\in(1/2,1)$. $\delta_{1}$
and $\delta_{2}$ are defined in Theorem 3.7. We have

$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})\geq\min\\{\rho(\tau_{1}-\max\\{\gamma\delta_{1},\delta_{2}\\}),\;(1-\rho)(\tau_{2}-2(1-\gamma)\delta_{2})\\}\log
n-o(\log n)$

with probability $1-n^{-\Omega(1)}$ for some $\tau_{1},\tau_{2}\in[0,\alpha]$
such that

$\displaystyle
1-\rho\left(\alpha-\tau_{1}\log\left(\frac{e\alpha}{\tau_{1}}\right)\right)<0,\quad
1-(1-\rho)\left(\alpha-\tau_{2}\log\left(\frac{e\alpha}{\tau_{2}}\right)\right)<0.$
(28)

###### Proof of Theorem 3.7.

From Lemma 3.11, we get $\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})=O(\log n)$.
From Lemma 3.6, we have $\|\mathbb{E}[\bm{\bm{A}}]-\bm{A}\|=o(\sqrt{\log n})$.
Therefore, as $n$ is sufficiently large, the condition
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})>\|\mathbb{E}[\bm{\bm{A}}]-\bm{A}\|$
is satisfied if $\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})=\Omega(\log n)$,
which is equivalent to

$\min\\{\rho(\tau_{1}-\max\\{\gamma\delta_{1},\delta_{2}\\}),\;(1-\rho)(\tau_{2}-2(1-\gamma)\delta_{2})\\}>0.$
(29)

By defining $\bar{\tau}_{1}:=\max\\{\gamma\delta_{1},\delta_{2}\\}$ and
$\bar{\tau}_{2}:=2(1-\gamma)\delta_{2}$, (29) reduces to
$\tau_{1}>\bar{\tau}_{1}$ and $\tau_{2}>\bar{\tau}_{2}$. Now it remains to
check if (28) holds for some $\tau_{1},\tau_{2}\in[0,\alpha)$. To this end,
let $\tau_{1}^{*},\tau_{2}^{*}\in[0,\alpha)$ be the roots of the equations in
(20) (Notice that such $\tau_{1}^{*},\tau_{2}^{*}$ exist only if
$\alpha>1/(1-\rho)$). Since the function
$f(\tau):=\alpha-\tau\log\left(e\alpha/\tau\right)$ monotonically decreases
for $\tau\in[0,\alpha)$, then (28) holds only if $\tau_{1}<\tau_{1}^{*}$ and
$\tau_{2}<\tau_{2}^{*}$. Putting all these together, the condition for exact
recovery reduces to $\alpha>1/(1-\rho),\bar{\tau}_{1}<\tau_{1}<\tau_{1}^{*}$
and $\bar{\tau}_{2}<\tau_{2}<\tau_{2}^{*}$. Furthermore, since
$\gamma\in[1/2,1]$ is not specified, it suffices to ensure
$\bar{\tau}_{1}<\tau_{1}^{*}$ and $\bar{\tau}_{2}<\tau_{2}^{*}$ for some
$\gamma\in[1/2,1]$ such that the range of $\tau_{1},\tau_{2}$ is valid. This
leads to the condition in (21). ∎

###  3.3 Two clusters with unknown cluster size

In real applications, we usually have no information on cluster sizes. This
motivates us to seek an alternative approach that does not rely on such prior
knowledge. To this end, we consider a normalized ground truth
$\bar{\bm{M}}^{*}$, whose $(i,j)$-th block is defined as

$\bar{\bm{M}}^{*}_{ij}=\begin{cases}\frac{1}{m_{C(i)}}\bm{R}_{i}\bm{R}_{j}^{\top},&\;C(i)=C(j),\\\
\bm{0},&\;\text{otherwise}.\end{cases}$ (30)

Here $m_{C(i)}$ denotes the size of the cluster that $i$ belongs to. By
assumption that the first $m_{1}$ nodes form $C_{1}$ and the remaining $m_{2}$
nodes form $C_{2}$, we have

$\bar{\bm{M}}^{*}:=\frac{1}{m_{1}}\bm{V}^{(1)}(\bm{V}^{(1)})^{\top}+\frac{1}{m_{2}}\bm{V}^{(2)}(\bm{V}^{(2)})^{\top}=\begin{pmatrix}\frac{1}{m_{1}}\widetilde{\bm{M}}_{1}^{*}&\bm{0}\\\
\bm{0}&\frac{1}{m_{2}}\widetilde{\bm{M}}_{2}^{*}\end{pmatrix},$ (31)

where each diagonal block has been normalized by the corresponding cluster
size. Then $\bar{\bm{M}}^{*}$ satisfies the following structural properties:

  1. 1.

$\bar{\bm{M}}^{*}$ is positive semi-definite, i.e. $\bar{\bm{M}}^{*}\succeq
0$;

  2. 2.

The sum of the diagonal blocks satisfies
$\sum_{i}\bar{\bm{M}}^{*}_{ii}=2\bm{I}_{d}$;

  3. 3.

The $i$-th block row of $\bar{\bm{M}}^{*}$ satisfies
$\sum_{j=1}^{n}\|\bar{\bm{M}}^{*}_{ij}\|_{\mathrm{F}}\leq\sqrt{d}$, for
$i=1,\ldots,n$.

Based on these, we formulate the SDP for solving $\bar{\bm{M}}^{*}$ as

$\displaystyle\bm{M}_{\text{SDP}}$
$\displaystyle=\operatorname*{arg\,max}_{\bm{M}\in\mathbb{R}^{nd\times
nd}}\quad\left\langle\bm{A},\bm{M}\right\rangle$ (32)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\quad\bm{M}\succeq
0,\quad\sum_{i=1}^{n}\bm{M}_{ii}=2\bm{I}_{d},\quad\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\sqrt{d},\quad
i=1,\ldots,n.$

Due to the normalization factor, (32) differs from the previous SDPs that it
does not rely on the cluster sizes, and exact recovery is achieved if the
normalized $\bar{\bm{M}}^{*}$ is obtained. Besides, similar to (19) a sum of
all blocks constraint $\sum_{i,j=1}^{n}\|\bm{M}_{ij}\|_{F}\leq n\sqrt{d}$
could apply to (32), via the row sum constraint that
$\sum_{j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\sqrt{d}$ for all $i$ and is
thus redundant. Notably, in the context of community detection, similar
normalization has been studied [34, 48, 35] when cluster sizes are unknown,
where the row-sum constraint is formulated as $\sum_{j=1}^{n}\bm{M}_{ij}=1$.
In contrast, we use an inequality constraint for the sake of convexity. Here,
we obtain the following exact recovery guarantees for (32).

######  Theorem 3.12.

Let $p=\alpha\log n/n,q=\beta\log n/n$. Suppose $m_{1}=\rho n$ and
$m_{2}=(1-\rho)n$ for some $\rho\in(0,1)$. $\tau_{1}^{*},\tau_{2}^{*}$ are
defined in (20). As $n$ is sufficiently large, (32) achieves exact recovery
i.e. $\bm{M}_{\text{SDP}}=\bar{\bm{M}}^{*}$ with probability
$1-n^{-\Omega(1)}$ if

$\max\bigg{\\{}\frac{1}{\rho},\;\frac{1}{1-\rho}\bigg{\\}}<\alpha\leq\min\bigg{\\{}2\tau_{1}^{*},\;2\tau_{2}^{*},\;\tau_{1}^{*}+\tau_{2}^{*}-\bigg{(}\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{)}\sqrt{\ell\beta}\bigg{\\}},$
(33)

where $\ell=2$ when $d>2$ and $\ell=1$ when $d=2$.

The proof of Theorem 3.12 is deferred to Appendix B.3, as it follows a similar
structure as the one presented in Section 3.1.1, with a slight difference on
the construction of dual variables.

(a) $|\bar{\bm{M}}^{*}|$

(b) $|\bm{A}|$

(c) $|\bm{M}_{\text{SDP}}|$

(d) $|\bm{M}_{\text{round}}|$

(e) $\angle\bar{\bm{M}}^{*}$

(f) $\angle\bm{A}$

(g) $\angle\bm{M}_{\text{SDP}}$

(h) $\angle\bm{M}_{\text{round}}$

Figure 2: An example of rounding when $d=2$. We plot the matrix of amplitudes
(LABEL:sub@fig:unknown_example_a–LABEL:sub@fig:unknown_example_d) and rotation
angles (LABEL:sub@fig:unknown_example_e–LABEL:sub@fig:unknown_example_h)
defined in (34) for the ground truth $\bar{\bm{M}}^{*}$, the observation
matrix $\bm{A}$, the SDP result $\bm{M}_{\text{SDP}}$ by (32) and the rounding
result $\bm{M}_{\text{round}}$.

Rounding. In practice, we observe that an extra rounding procedure can improve
the recovery of $\bm{M}^{*}$. As an illustration, in Figure 2 we present an
example with 2D rotation and two equal-sized clusters. For the ease of
presentation, we choose to use a complex number to represent each
$\bar{\bm{M}}_{ij}^{*}$ such that
$\bar{\bm{M}}_{ij}^{*}=|\bar{\bm{M}}^{*}_{ij}|e^{\imath\theta_{ij}}$, where
$|\bar{\bm{M}}^{*}_{ij}|$ denotes the “amplitude” and $\theta_{ij}\in[0,2\pi]$
represents the rotation angle. Then we form two $n\times n$ matrices
$|\bar{\bm{M}}^{*}|$ and $\angle\bar{\bm{M}}^{*}$ that contain

$\text{amplitude:
}|\bar{\bm{M}}^{*}|_{ij}:=|\bar{\bm{M}}^{*}_{ij}|,\quad\text{and rotation
angle }\angle\bar{\bm{M}}^{*}_{ij}:=\theta_{ij}-\pi$ (34)

respectively. A similar procedure is applied to $\bm{A}$ and
$\bm{M}_{\textrm{SDP}}$. In Figures 2a and 2c, one can see that
$|\bm{M}_{\text{SDP}}|\neq|\bar{\bm{M}}^{*}|$ and thus exact recovery fails.
However, they have the same support on the two clusters. Moreover, in Figures
2e and 2g we observe $\angle\bm{M}_{\textrm{SDP}}=\angle\bar{\bm{M}}^{*}$,
meaning the rotational alignments are exactly recovered. These observations
inspire us to design the following rounding procedure. For each block of
$\bm{M}_{\textrm{SDP}}$ denoted by $(\bm{M}_{\textrm{SDP}})_{ij}$, we round it
to

$(\bm{M}_{\textrm{round}})_{ij}=\begin{cases}\displaystyle\frac{(\bm{M}_{\textrm{SDP}})_{ij}}{\|(\bm{M}_{\textrm{SDP}})_{ij}\|_{\text{F}}}\cdot\sqrt{d},&\quad\|(\bm{M}_{\textrm{SDP}})_{ij}\|_{\textrm{F}}\geq\epsilon,\\\
\bm{0},&\quad\text{otherwise},\end{cases}$ (35)

where $\epsilon$ is some small value for avoiding numerical issues. That is,
for each non-zero block of $\bm{M}_{\textrm{SDP}}$ we normalize its
“amplitude” (Frobenius norm) to be $\sqrt{d}$ and keep its “phase” unchanged.
Let $\bm{M}_{\textrm{round}}$ be the rounded solution based on all blocks of
$\bm{M}_{\textrm{SDP}}$, then in Figures 2d and 2h we obtain
$\bm{M}_{\textrm{round}}=\bm{M}^{*}$ which is equal to the unnormalized ground
truth in (2). Therefore, empirically, we observe exact recovery after an
appropriate rounding.

###  3.4 SDPs for general cluster structures

The SDP formulation can be easily extended to general cases with an arbitrary
number of clusters. When cluster sizes are known, the convex relaxation
introduced in (19) still applies to $\bm{M}^{*}$ in principle, and we can
formulate an SDP relaxation as

$\displaystyle\bm{M}_{\text{SDP}}$
$\displaystyle=\operatorname*{arg\,max}_{\bm{M}\in\mathbb{R}^{nd\times
nd}}\quad\left\langle\bm{A},\bm{M}\right\rangle$ (36)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\quad\bm{M}\succeq
0,\quad\bm{M}_{ii}=\bm{I}_{d},\quad\sum_{j}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq(\max_{i}m_{i})\sqrt{d},\quad
i=1,\ldots,n,$
$\displaystyle\quad\sum_{i,j=1}^{n}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\sqrt{d}\sum_{k=1}^{K}m_{k}^{2}.$

When the cluster sizes are unknown, an SDP similar to (32) can be designed as:

$\displaystyle\bm{M}_{\text{SDP}}$
$\displaystyle=\max_{\bm{M}\in\mathbb{R}^{nd\times
nd}}\quad\left\langle\bm{A},\bm{M}\right\rangle$ (37)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\quad\bm{M}\succeq
0,\quad\sum_{i}\bm{M}_{ii}=K\bm{I}_{d},\quad\sum_{j}\|\bm{M}_{ij}\|_{\mathrm{F}}\leq\sqrt{d},\quad
i=1,\ldots,n,$

which only requires the number of clusters $K$ as a parameter. Moreover, a
similar rounding procedure as in Section 3.3 can be used to improve the
solution by (37). Finding the exact recovery guarantee for both (36) and (37)
is an interesting but challenging task, which is left for future work.

##  4 Numerical results

This section is devoted to empirically investigating the performance of the
SDPs in Section 3. In Sections 4.1–4.3, we focus on experiments with two
clusters and 2D rotations ($d=2$). In Section 4.4, we include results for more
general settings, e.g., 3D rotations and the number of clusters is larger than
two. We generate the observation matrix $\bm{A}$ based on the model introduced
in Section 2. Then we evaluate the SDP solution by measuring the following
error metric:

$\text{Error}=\log(\|\bm{M}_{\text{SDP}}-\bm{M}^{*}\|_{\textrm{F}}).$ (38)

When cluster sizes are unknown and the SDP in (32) is adopted, the ground
truth $\bm{M}^{*}$ in (38) should be replaced by the normalized
$\bar{\bm{M}}^{*}$ defined in (30). For the case of two clusters, we evaluate
the phase transition of the condition $\widetilde{\bm{\Lambda}}\succ 0$
according to our guess of dual variables (e.g. in Lemmas 3.3 and 3.9) via the
following metric:

$\text{Failure rate}=1-\text{the rate that }\widetilde{\bm{\Lambda}}\succ
0\text{ is satisfied}.$ (39)

$\text{Failure rate}=0$ means that our construction of the dual variables
satisfy the optimality and uniqueness condition for $\bm{M}^{*}$ or
$\bar{\bm{M}}^{*}$ (e.g. in Lemmas 3.2, 3.8 and B.1) and the exact recovery is
guaranteed. For each experiment, we average the result over 10 different
realizations of the observation matrix $\bm{A}$.

(a) $n=50$

(b) $n=100$

(c) $n=150$

(d) $n=150$, by [19, Eq. (5)]

(e) Comparison of two thresholds

Figure 3: Results on two equal-sized clusters with known cluster size.
LABEL:sub@fig:two_equal_a–LABEL:sub@fig:two_equal_c Recovery error of
$\bm{M}_{\text{SDP}}$ by (9) with different $n$. The thresholds in Theorem 10
for $d=2$ and $d>2$ are shown in red solid curve and red dashed curve,
respectively. LABEL:sub@fig:sbm_sdp Recovery error by first performing
clustering on graph scalar edge connection using the SDP in [19, Eq. (5)] and
then synchronization, the exact recovery threshold
$\sqrt{\alpha}-\sqrt{\beta}=\sqrt{2}$ (see [19, Theorem 2]) is shown in red.
LABEL:sub@fig:compare_thresholds Comparison of the thresholds in Theorem 10
for $d=2$ (blue) and [19, Theorem 2] (red), exact recovery is guaranteed in
the region below each threshold. The recovery error is defined in (38).

###  4.1 Two equal-sized clusters

First, we consider two equal-sized clusters where the SDP in (9) is used for
recovery. In Figures 3a–3c we plot the recovery error with varying $\alpha$
and $\beta$ for $n=50,\,100,\,150$. In each plot, the red solid curve
corresponds to the threshold of the condition in Theorem 10 for $d=2$ . As we
can see, (9) achieves exact recovery within a wide range of $\alpha$ and
$\beta$. Also, the theoretical threshold closely fits the empirical phase
transition boundary, especially as $n$ is large, which indicates the sharpness
of the condition. In contrast, the red dash curve corresponds to the threshold
of the conditions given in Theorem 10 for $d>2$, which is slightly loose by a
constant factor $\sqrt{2}$.

In addition, we consider using the two-stage approach mentioned in the
introduction that first applies existing methods for community detection and
then performs synchronization for each community separately. We use the SDP
proposed in [19, Eq. (5)] to detect the cluster membership, which is proved to
achieve the information-theoretical limit as $n\rightarrow\infty$ [2, 19]. As
a result, Figure 4a displays the corresponding recovery error with $n=150$,
which exhibits worse performance than Figure 3c. In Figure 3e, we compare the
theoretical thresholds for exact recovery in Theorem 10 for $d=2$ and [19,
Theorem 2]. It is clear to see that, by incorporating the additional pairwise
alignment information, our method outperforms the classical community
detection method which only exploits the edge connectivity.

$(m_{1},m_{2})=(60,40)$ |  |
---|---|---
$(m_{1},m_{2})=(80,20)$ |  (a) Error of $\bm{M}_{\text{SDP}}$ |  (b) Failure rate
Figure 4: Results on two unequal-sized clusters with known cluster sizes.
LABEL:sub@fig:unequal_error Recovery error of the solution of (19);
LABEL:sub@fig:unequal_rate The failure rate defined in (39) for
$\widetilde{\bm{\Lambda}}$ in Lemma 3.10. The threshold given in Theorem 3.7
for $d=2$ is shown in red.

(a) $(m_{1},m_{2})=(600,400)$

(b) $(m_{1},m_{2})=(800,200)$

Figure 5: Results on two unequal-sized clusters with known cluster sizes,
large $n$. We plot the failure rate defined in (39) for
$\widetilde{\bm{\Lambda}}$ in Lemma 3.10. The threshold in Theorem 3.7 for
$d=2$ is shown in red.

###  4.2 Two unequal-sized clusters

Next, we consider two unequal-sized clusters where the cluster sizes
$(m_{1},m_{2})$ are given, and the SDP in (19) is used for recovery. We
simulate $\bm{A}$ under different settings of $(m_{1},m_{2})$, and plot the
recovery error with varying $\alpha$ and $\beta$ in Figure 4. By comparing the
results for $(m_{1},m_{2})=(60,40)$ and $(m_{1},m_{2})=(80,20)$, we find that
it gets more challenging to recover $\bm{M}^{*}$ if the cluster sizes are more
imbalanced. The red curve in each plot corresponds the threshold of the
sufficient conditions given in Theorem 3.7 for $d=2$. Clearly, there is a gap
between the empirical phase transition boundary and the theoretical threshold,
which implies the condition in Theorem 3.7 may not be necessary.

To understand why there exists such gap, we construct the dual variables
according to our construction in Lemma 3.9 for each realization of $\bm{A}$,
and in Figure 4b we plot the failure rate in (39) for
$\widetilde{\bm{\Lambda}}$ defined in Lemma 3.10. As a result, we see that in
some certain regime of $\alpha$ and $\beta$, even though our dual construction
does not satisfy such conditions, empirically we still observe exact recovery
of (19) in Figure 4a. This implies our guess of the dual variables in Lemma
3.9 is sub-optimal. In addition, to further verify the sharpness of the
conditions in Theorem 3.7. As $n$ is large, we test the failure rate under
different setting of $(m_{1},m_{2})$. As we can see in Figure 5, the threshold
of the condition in Theorem 3.7 sharply characterize the empirical phase
transition boundaries, which indicates the derived condition is tight based on
our guessed dual variables.

###  4.3 Two clusters with unknown cluster sizes

Here we consider two clusters with unknown cluster sizes, where (32) is used
for recovery. We simulate $\bm{A}$ with different settings of $(m_{1},m_{2})$.
In Figure 6a we plot the recovery error of the SDP solutions. Also, we apply
the rounding step (35) to further refine the SDP solutions and plot the error
after rounding in Figure 6b. As a result, one can see that the result after
rounding clearly exhibits certain improvement against the original one. In
addition, to check whether our construction of the dual variables in Lemma B.2
is optimal, in Figure 6c we show the failure rate in (39) for
$\widetilde{\bm{\Lambda}}$ in Lemma B.3. Again, we see that there is certain
regime of $\alpha,\beta$ where exact recovery by (32) is possible (see Figure
6a), but the constructed dual certificate fails to satisfy the condition,
indicating a lack of optimality in the choice of dual variables.

$(m_{1},m_{2})=(50,50)$ |  |  |
---|---|---|---
$(m_{1},m_{2})=(80,20)$ |  (a) Error of $\bm{M}_{\text{SDP}}$ |  (b) Error of $\bm{M}_{\text{round}}$ |  (c) Failure rate
Figure 6: Results on two clusters with unknown cluster sizes.
LABEL:sub@fig:unknown_a Recovery error of $\bm{M}_{\text{SDP}}$ by (32);
LABEL:sub@fig:unknown_b Recovery error of $\bm{M}_{\text{round}}$ by (35);
LABEL:sub@fig:unknown_c The failure rate defined in (39) for
$\widetilde{\bm{\Lambda}}$ in Lemma B.3.

(a) $(m_{1},m_{2})=(600,400)$

(b) $(m_{1},m_{2})=(800,200)$

Figure 7: Results on two clusters with unknown cluster sizes with large $n$.
We plot the failure rate defined in (39) for $\widetilde{\bm{\Lambda}}$ in
Lemma B.3. The threshold given in Theorem 3.12 for $d=2$ is shown in red.

While our guess of the dual variables is not optimal, as $n$ is large we are
able to sharply characterize when such a dual certificate fails to satisfy the
condition in Lemma B.2. This is demonstrated in Figure 7, where we show good
agreement between the predicted boundary in Theorem 3.12 and the empirical
boundary of the failure rate.

(a) Equal, by (9)

(b) Unequal, by (19)

(c) Unknown, by (32)

(d) Rounding, by (35)

Figure 8: Results on $\mathrm{SO}(3)$ group transformation. We plot the
recovery error under LABEL:sub@fig:SO3_pt_1 two equal-sized clusters, the
thresholds in Theorem 10 for $d=2$ and $d>2$ are shown in red solid and red
dash curve, respectively; LABEL:sub@fig:SO3_pt_2 two unequal-sized clusters,
the thresholds in Theorems 3.7 for $d=2$ and $d>2$ are shown in red solid and
red dash curve, respectively; LABEL:sub@fig:SO3_pt_3–LABEL:sub@fig:SO3_pt_4
two clusters with unknown cluster sizes. We test under $(m_{1},m_{2})=(25,25)$
for LABEL:sub@fig:SO3_pt_1, and $(m_{1},m_{2})=(30,20)$ for
LABEL:sub@fig:SO3_pt_2–LABEL:sub@fig:SO3_pt_4.

(a) $\bm{M}_{\text{SDP}}$ by (36)

(b) $\bm{M}_{\text{SDP}}$ by (37)

(c) $\bm{M}_{\text{round}}$ by (35)

Figure 9: Results on three clusters. We test under the setting
$(m_{1},m_{2},m_{3})=(25,25,25)$. We plot the recovery error under
LABEL:sub@fig:SDP_K_3_unequal known cluster sizes, recovered by (36);
LABEL:sub@fig:SDP_K_3–LABEL:sub@fig:SDP_K_3_round unknown cluster sizes,
recovered by (37) and rounded by (35) respectively.

###  4.4 3D rotations and $K=3$

Here we extend our experiments to $\mathrm{SO}(3)$ group transformation. In
Figure 8 we plot the recovery errors by SDPs on different scenarios under two
clusters. Similar to the results for $\mathrm{SO}(2)$, we observe sharp phase
transitions in the SDP solutions. Specifically, in Figures 8a and 8b we
display the thresholds for exact recovery derived in Sections 3.1 and 3.2,
respectively. One can see that exact recovery is still possible even above the
thresholds, which implies there is still some room for improvement of our
conditions. Also, we test the generalized SDPs proposed in (36) and (37),
under the setting of $K=3$ and $(m_{1},m_{2},m_{3})=(25,25,25)$. The plots of
recovery error are shown in Figure 9. As we can see, the proposed SDPs
achieves exact recovery with sharp phase transitions. In addition, the
rounding step is effective to further improve the SDP solutions in both cases.

##  5 Conclusion and open problems

In this paper, we propose to solve the community detection and rotational
synchronization simultaneously via semidefinite programming. Compared with the
existing SDP for community detection under SBM, our proposed SDPs not only
take into account the graph structure but also the additional information on
pairwise rotational alignments, which gives better clustering results. In
particular, for the case of two clusters we obtain sufficient conditions for
the SDPs to achieve exact recovery, which characterize the empirical phase
transition boundaries. In addition, we acquire new concentration inequalities
for the Frobenius norm of sum of random rotation matrices and the operator
norm of a random block matrix as interesting byproducts from our analysis.

There are several directions to be further explored. First, it is natural to
expect that the results obtained in this paper can be extended to a much more
general family of groups, such as symmetric group and orthogonal group. Also
our analysis can be applied to other probabilistic models on the pairwise
relations, such as the additive Gaussian model considered in [27]. In
addition, the conditions for exact recovery by (19) and (32) in the case of
unequal and unknown cluster sizes can be improved by finding a more optimal
construct of dual variables. For $d>2$, current results can be further
improved with a Frobenius norm bound on the sum of random rotation matrices
that is tighter than the one given in Theorem A.3. Furthermore, we note that
finding the information-theoretical limit of exact recovery on the proposed
probabilistic model is still an open problem. Finally, although the SDP can be
solved in polynomial time complexity, it is still computationally expensive
when the graph size is large, and one can consider spectral methods and
message passing algorithms in that situation.

##  Appendix A Important technical ingredients

This section is devoted to technical ingredients that support our proofs in
Appendix B. Specifically, we derive new matrix concentration inequalities for
random rotation matrices in Appendix A.2, and new upper bounds of the operator
norm of random block matrices in Appendix A.3.

###  A.1 A tail bound of Bernoulli trials

Our analysis relies on the following tail bound of a Bernoulli trail.

######  Lemma A.1 ([19, Lemma 2]).

Let $X\sim\mathrm{Binom}\left(m,\alpha\log n/n\right)$ for
$m\in\mathbb{N},\;\alpha=O(1)$, where $m=\rho n$ for some $\rho>0$. Let
$k_{n}=\tau\rho\log n$ for some $\tau\in(0,\alpha]$. Then for a sufficiently
large $n$,

$\mathbb{P}\left\\{X\leq
k_{n}\right\\}=n^{-\rho\left(\alpha-\tau\log(\frac{e\alpha}{\tau})+o(1)\right)}.$

###  A.2 Concentration inequalities for random rotation matrices

Given a series of i.i.d. random matrices $\bm{X}_{i}\in\mathbb{R}^{d\times d}$
for $i=1,\ldots m$ such that

$\bm{X}_{i}=\begin{cases}\bm{R}_{i},&\quad\text{with probability $q$},\\\
\bm{0},&\quad\text{otherwise},\end{cases}$ (40)

where $\bm{R}_{i}$ is a random rotation matrix with $\det(\bm{R}_{i})=1$,
uniformly drawn from $\mathrm{SO}(d)$ according to Haar measure. Our analysis
relies on bounding the Frobenius norm of $\bm{Z}=\sum_{i=1}^{m}\bm{X}_{i}$,
namely $\|\bm{Z}\|_{\mathrm{F}}$. In general, a fairly tight bound can be
obtained from matrix concentration inequalities such as matrix Bernstein [44,
Theorem 1.6], which is presented as following:

######  Theorem A.2 (Matrix Bernstein, [44, Theorem 1.6]).

Let $\bm{X}_{1},\ldots,\bm{X}_{m}\in\mathbb{R}^{d\times d}$ be independent,
centered random matrices and each one is uniformly bounded as

$\mathbb{E}[\bm{X}_{i}]=\bm{0}\quad\text{and}\quad\|\bm{X}_{i}\|\leq
L,\quad\text{for }i=1,\ldots,n.$

Let $\bm{Z}=\sum\limits_{i=1}^{n}\bm{X}_{i}$ and $v(\bm{Z})$ denotes the
matrix variance statistic of $\bm{Z}$ as

$v(\bm{Z})=\max\\{\|\mathbb{E}(\bm{Z}\bm{Z}^{\top})\|,\;\|\mathbb{E}(\bm{Z}^{\top}\bm{Z})\|\\}.$

Then for any $t>0$,

$\mathbb{P}\left\\{\|\bm{Z}\|\geq t\right\\}\leq
2d\exp\left(\frac{-t^{2}/2}{v(\bm{Z})+Lt/3}\right).$

As a result, by applying Theorem A.2 on $\bm{X}_{i}$ defined in (40) we get:

######  Theorem A.3.

Let $\bm{X}_{1},\ldots,\bm{X}_{m}\in\mathbb{R}^{d\times d}$ be i.i.d. random
matrices defined in (40) and $\bm{Z}=\sum\limits_{i=1}^{m}\bm{X}_{i}$,
$m=O(n)$. Then for any $t>0$,

$\mathbb{P}\left\\{\left\|\bm{Z}\right\|_{\mathrm{F}}\geq\sqrt{d}t\right\\}\leq
2d\exp\left(\frac{-t^{2}/2}{qm+t/3}\right).$ (41)

In other words,

$\frac{1}{\sqrt{d}}\|\bm{Z}\|_{\mathrm{F}}\leq\sqrt{2qm(c\log n+\log
2d)}\left(\sqrt{1+\frac{c\log n+\log 2d}{18qm}}+\sqrt{\frac{c\log n+\log
2d}{18qm}}\right)$ (42)

with probability $1-n^{-c}$ for any $c>0$.

###### Proof.

By definition of the operator norm and Frobenius norm
$\|\bm{Z}\|\leq\|\bm{Z}\|_{\mathrm{F}}\leq\sqrt{d}\|\bm{Z}\|$. Therefore, it
satisfies

$\mathbb{P}\\{\left\|\bm{Z}\right\|_{\mathrm{F}}\geq\sqrt{d}t\\}\leq\mathbb{P}\left\\{\left\|\bm{Z}\right\|_{\mathrm{2}}\geq
t\right\\},$

which enables us to bound $\left\|\bm{Z}\right\|_{\mathrm{F}}$ via
$\left\|\bm{Z}\right\|_{\mathrm{2}}$ by Theorem A.2. To this end, for $L$
defined in Theorem A.2, we have $\|\bm{X}_{i}\|\leq 1$ then $L=1$. For
$v(\bm{Z})$ we have
$\|\mathbb{E}(\bm{Z}^{\top}\bm{Z})\|=\left\|\sum_{i=1}^{m}\mathbb{E}\left[\bm{X}_{i}^{\top}\bm{X}_{i}\right]\right\|=\left\|\sum_{i=1}^{m}q\bm{I}_{d}\right\|=qm$,
similarly $\|\mathbb{E}(\bm{Z}\bm{Z}^{\top})\|=qm$ then it follows
$v(\bm{Z})=qm$. This leads to (41). Furthermore, by setting the RHS of (41) to
be $n^{-c}$ for $c>0$ and solve it we get (42). ∎

In our analysis, we are interested in the case of $m=\rho n,q=\beta\log n/n$
for some $\rho,\beta$ and $n\gg d$. Then (42) can be written as

$\displaystyle\frac{1}{\sqrt{d}}\|\bm{Z}\|_{\mathrm{F}}$
$\displaystyle=\sqrt{2c\rho\beta}\left(\sqrt{1+\frac{c}{18\rho\beta}}+\sqrt{\frac{c}{18\rho\beta}}\right)\log
n\approx\sqrt{2c\rho\beta}\log n$ (43)

where we use the approximation
$\left(\sqrt{1+\frac{c}{18\rho\beta}}+\sqrt{\frac{c}{18\rho\beta}}\right)\approx
1$ since usually $18\rho\beta\gg c$.

In particular, when the transformation is a $2$-dimensional rotation i.e.
$d=2$, we are able to obtain a result sharper than Theorem A.3 as following:

######  Theorem A.4.

Under the setting of Theorem A.3 with $d=2$, for a sufficiently large $m$

$\frac{1}{\sqrt{d}}\|\bm{Z}\|_{\mathrm{F}}\leq\sqrt{cqm\log n}(1+o(1))$

with probability $1-n^{-c}$ for any $c>0$.

###### Proof.

To begin with, by definition of $\bm{X}_{i}$ in (40), we can rewrite
$\bm{X}_{i}=r_{i}\bm{R}_{i}$ where $r_{i}$ is a Bernoulli random variable such
that $\mathbb{P}\\{r_{i}=1\\}=q$. Moreover, when $d=2$ each rotation matrix
$\bm{R}_{i}$ can be expressed as
$\bm{R}_{i}=\begin{pmatrix}\cos\theta_{i}&-\sin\theta_{i}\\\
\sin\theta_{i}&\cos\theta_{i}\end{pmatrix}$ for some $\theta_{i}\in[0,2\pi)$.
As a result,

$\frac{1}{d}\|\bm{Z}_{i}\|^{2}_{\mathrm{F}}=\left(\sum\limits_{i=1}^{m}r_{i}\sin\theta_{i}\right)^{2}+\left(\sum\limits_{i=1}^{m}r_{i}\cos\theta_{i}\right)^{2}=:x_{m}.$

We are going to bound $\frac{1}{\sqrt{d}}\|\bm{Z}_{i}\|_{\mathrm{F}}$ in terms
of $x_{m}$. Our technique is to compute the $k$-th moment of $x_{m}$ i.e.
$\mathbb{E}[x_{m}^{k}]$ for some integer $k\leq m$ followed by Markov’s
inequality. First,

$\mathbb{E}[x_{m}]=\mathbb{E}\Bigg{[}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}r_{i}r_{j}\left(\cos\theta_{i}\cos\theta_{j}+\sin\theta_{i}\sin\theta_{j}\right)\Bigg{]}=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\mathbb{E}\left[r_{i}r_{j}\right]\mathbb{E}\left[\cos(\theta_{i}-\theta_{j})\right].$

Next, in general $\mathbb{E}[x_{m}^{k}]$ is given as

$\displaystyle\mathbb{E}\left[x^{k}_{m}\right]=$
$\displaystyle\sum\limits_{i_{1},\ldots,i_{k}=1}^{m}\sum\limits_{j_{1},\ldots,j_{k}=1}^{m}\mathbb{E}\left[r_{i_{1}}r_{j_{1}}\cdots
r_{i_{k}}r_{j_{k}}\right]\mathbb{E}\left[\cos(\theta_{i_{1}}-\theta_{j_{1}})\cdots\cos(\theta_{i_{k}}-\theta_{j_{k}})\right].$
(44)

Let $s_{i}\in\\{-1,1\\}$ denotes a discrete variable for $i=1,\ldots,k-1$.
Then applying the property
$\cos(\alpha_{1})\cos(\alpha_{2})=\frac{1}{2}\left[\cos(\alpha_{1}+\alpha_{2})+\cos(\alpha_{1}-\alpha_{2})\right]$
recursively for $k-1$ times yields

$\cos(\theta_{i_{1}}-\theta_{j_{1}})\cdots\cos(\theta_{i_{k}}-\theta_{j_{k}})=\frac{1}{2^{k-1}}\sum\limits_{s_{1},\ldots,s_{k-1}\in\\{-1,1\\}}\cos\left((\theta_{i_{1}}\\!-\\!\theta_{j_{1}})\\!+\\!s_{1}(\theta_{i_{2}}-\theta_{j_{2}})\\!+\\!\cdots\\!+\\!s_{k-1}(\theta_{i_{k}}\\!-\\!\theta_{j_{k}})\right).$

Plugging this into (44) gives

$\displaystyle\mathbb{E}\left[x^{k}_{m}\right]$
$\displaystyle=\left(\frac{1}{2^{k-1}}\right)\sum\limits_{s_{1},\ldots,s_{k-1}\in\\{-1,1\\}}\sum\limits_{i_{1},\ldots,i_{k}}\sum\limits_{j_{1},\ldots,j_{k}}\mathbb{E}\left[r_{i_{1}}r_{j_{1}}\cdots
r_{i_{k}}r_{j_{k}}\right]\mathbb{E}\left[\cos\left(\theta_{i_{1}}\\!-\\!\theta_{j_{1}}\\!+\\!\cdots\\!+\\!\delta_{k-1}(\theta_{i_{k}}\\!-\\!\theta_{j_{k}})\right)\right]$
$\displaystyle\overset{(a)}{=}\sum\limits_{i_{1},\ldots,i_{k}}\sum\limits_{j_{1},\ldots,j_{k}}\mathbb{E}\left[r_{i_{1}}r_{j_{1}}\cdots
r_{i_{k}}r_{j_{k}}\right]\mathbb{E}\left[\cos\left(\theta_{i_{1}}-\theta_{j_{1}}+\theta_{i_{2}}-\theta_{j_{2}}+\cdots+\theta_{i_{k}}-\theta_{j_{k}}\right)\right].$
(45)

Here, ($a$) holds since
$\sum\limits_{i_{1},\ldots,i_{k}}\sum\limits_{j_{1},\ldots,j_{k}}\mathbb{E}\left[\cos\left(\theta_{i_{1}}\\!-\\!\theta_{j_{1}}\\!+\\!\cdots\\!+\\!s_{k-1}(\theta_{i_{k}}\\!-\\!\theta_{j_{k}})\right)\right]$
is identical for different choices of $\\{s_{i}\\}_{i=1}^{k-1}$, and there are
$2^{k-1}$ number of choices in total then the factor $1/2^{k-1}$ is cancelled
by summing all of them, and we can focus on the case that
$s_{1}=s_{2}=\cdots=s_{k-1}=1$. To proceed, let us denote
$S_{i}=\\{i_{1},\ldots,i_{k}\\}$ and $S_{j}=\\{j_{1},\ldots,j_{k}\\}$ as two
multisets (a multiset is a variant of a set that allows repeated elements)
that contain all $i$ and $j$ respectively, then

$\mathbb{E}\left[\cos\left(\theta_{i_{1}}-\theta_{j_{1}}+\theta_{i_{2}}-\theta_{j_{2}}+\cdots+\theta_{i_{k}}-\theta_{j_{k}}\right)\right]=\begin{cases}1,&\quad
S_{i}=S_{j},\\\ 0,&\quad\text{otherwise}.\end{cases}$

This holds because the sum of the random angles equals $0$ mod $2\pi$ if
$S_{i}=S_{j}$, otherwise it vanishes by taking the expectation. Therefore,
under $S_{i}=S_{j}$, let $m_{l}$ denotes the multiplicity of element
$l\in\left\\{1,\ldots,m\right\\}$ that either $S_{i}$ or $S_{j}$ contains,
then it satisfies

$\mathbb{E}[r_{i_{1}}r_{j_{1}}\cdots
r_{i_{k}}r_{j_{k}}]\overset{(a)}{=}\mathbb{E}[r_{1}^{2m_{1}}r_{2}^{2m_{2}}\cdots
r_{m}^{2m_{n}}]=\prod_{i=1}^{m}\mathbb{E}[r_{i}^{2m_{i}}]\overset{(b)}{=}q^{\tau(m_{1},\ldots
m_{m})}$

where $\tau(m_{1},\ldots m_{m})$ denotes the number of non-zero elements in
$\\{m_{1},\ldots,m_{m}\\}$, ($a$) holds because of $S_{i}=S_{j}$, and $(b)$
comes from $\mathbb{E}[r_{i}^{2m_{i}}]=q,\;\forall m_{i}>0$. Given the above,
in (45) the summation over all $i$ and $j$ can be instead summing over
$m_{1},\ldots,m_{m}$. That is,

$\displaystyle\mathbb{E}[x_{m}^{k}]=\sum\limits_{\begin{subarray}{c}m_{1},\ldots,m_{m}\geq
0\\\ m_{1}+\cdots+m_{m}=k\end{subarray}}\Pi(m_{1},\ldots
m_{m})q^{\tau(m_{1},\ldots m_{m})}.$ (46)

Here, $\Pi(m_{1},\ldots m_{m})$ denotes the number of combinations of
$\\{i_{1},j_{1},\ldots,i_{k},j_{k}\\}$ that satisfy $S_{i}=S_{j}$ with
multiplicity $\\{m_{1},\ldots,m_{m}\\}$. To determine it, notice that given a
fixed $\\{m_{1},\ldots,m_{m}\\}$ there are
${k\choose{m_{1},m_{2},\ldots,m_{m}}}$ number of combinations for either
$S_{i}$ or $S_{j}$ that satisfy it. Then we have $\Pi(m_{1},\ldots
m_{m})={k\choose{m_{1},m_{2},\ldots,m_{m}}}^{2}$. Plugging this into (46)
gives

$\displaystyle\mathbb{E}\left[x_{m}^{k}\right]=\sum\limits_{\begin{subarray}{c}m_{1},\ldots,m_{m}\geq
0\\\ m_{1}+\cdots+m_{m}=k\end{subarray}}q^{\tau(m_{1},\ldots
m_{m})}{k\choose{m_{1},\ldots,m_{m}}}^{2}=\sum\limits_{l=1}^{k}{n\choose
l}q^{l}\sum\limits_{\begin{subarray}{c}m_{1},\ldots,m_{l}\geq 1\\\
m_{1}+\cdots+m_{l}=k\end{subarray}}{k\choose{m_{1},\ldots,m_{l}}}^{2},$

where the RHS holds by fixing $\tau(m_{1},\ldots,m_{m})=l$ for $l=1,\ldots,k$.
Furthermore,

$\displaystyle\mathbb{E}\left[x_{m}^{k}\right]$ $\displaystyle={n\choose
k}q^{k}\underbrace{\sum\limits_{\begin{subarray}{c}m_{1},\ldots,m_{k}\geq 1\\\
m_{1}+\ldots+m_{k}=k\end{subarray}}{k\choose{m_{1},\ldots,m_{k}}}^{2}}_{=(k!)^{2}\text{
since $m_{1}=\cdots=m_{k}=1$}}+\sum\limits_{l=1}^{k-1}{m\choose
l}q^{l}\sum\limits_{\begin{subarray}{c}m_{1},\ldots,m_{l}\geq 1\\\
m_{1}+\cdots+m_{l}=k\end{subarray}}{k\choose{m_{1},\ldots,m_{l}}}^{2}$
$\displaystyle=\left(\frac{m!}{k!(m-k)!}\right)q^{k}(k!)^{2}+O(q^{k-1}m^{k-1})=k!q^{k}m^{k}+O(q^{k-1}m^{k-1})$
$\displaystyle\leq c_{0}k!q^{k}m^{k}$

where the last inequality holds for any constant $c_{0}>1$ with a sufficiently
large $m$.

Now we are ready to bound $x_{m}$ by applying Markov’s inequality as

$\displaystyle\mathbb{P}\left\\{x_{m}\geq t\right\\}$
$\displaystyle=\mathbb{P}\left\\{x_{m}^{k}\geq t^{k}\right\\}\leq
t^{-k}\mathbb{E}[x_{m}^{k}]\leq t^{-k}\cdot
c_{0}k!q^{k}m^{k}\leq\bigg{(}\frac{(c_{0}e\sqrt{k})^{1/k}kqm}{et}\bigg{)}^{k}$

where the last inequality uses the fact that $k!\leq
ek^{k+\frac{1}{2}}e^{-k}$. If we set $k=\lceil c\log n\rceil$ and

$t=(c_{0}e\sqrt{k})^{1/k}kqm=e^{\frac{1}{k}\log\left(c_{0}e\sqrt{k}\right)}kqm=(1+o(1))cqm\log
n,$

then we have

$\mathbb{P}\left\\{x_{n}\geq t\right\\}\leq
n^{-c\left(1+\log\frac{t}{(c_{0}e\sqrt{k})^{1/k}kqm}\right)}=n^{-c}.$

By definition of $x_{m}$, this further leads to
$\frac{1}{\sqrt{d}}\|\bm{Z}\|_{\mathrm{F}}\leq\sqrt{cqm\log n}(1+o(1))$ with
probability $1-n^{-c}$, which completes the proof. ∎

######  Remark 1.

When $d=2$, we can interpret $\frac{1}{\sqrt{d}}\|\bm{Z}\|_{\mathrm{F}}$ from
a random walk perspective: Suppose a random walk on a 2-D plane such that in
each step, with probability $q$ we take a unit-length step towards a random
direction uniformly drawn from $[0,2\pi)$, and with probability $1-q$ we stay
where we are. As a result, $\frac{1}{\sqrt{d}}\|\bm{Z}\|_{\mathrm{F}}$ can be
interpreted as the distance that we travel within $m$ steps where $r_{i}$
indicates whether we move or not in the $i$-th step, and $\theta_{i}$ stands
for the corresponding direction. In fact, such 2-D random walk with $q=1$ has
been originally studied by Rayleigh in [37, 36]. Let $p_{m}(r)$ be the
probability distribution of travelling a distance $r$ with $m$ steps, Rayleigh
showed that as $m\rightarrow\infty$,

$p_{m}(r)\sim\frac{2r}{m}e^{-r^{2}/m}.$

Therefore, asymptotically it satisfies $r\leq\sqrt{cm\log n}$ with probability
$1-n^{-c}$ for any $c>0$. Importantly, this bound agrees with the non-
asymptotic result in Theorem A.4, which indicates the sharpness of our result.

######  Lemma A.5.

Let $m_{1}=\rho n$ and $m_{2}=(1-\rho)n$ with $0<\rho<1$, and
$\bm{Z}_{1},\ldots,\bm{Z}_{m_{1}}\in\mathbb{R}^{d\times d}$ be i.i.d. random
matrices where each $\bm{Z}_{i}=\sum\limits_{j=1}^{m_{2}}\bm{X}_{j}$ is
independently generated as in Theorem A.3. Let
$\epsilon_{i}:=\frac{\|\bm{Z}_{i}\|_{\mathrm{F}}}{m_{2}\sqrt{d}}$. Then, when
$p,q=O(\log n/n)$

$\sum\limits_{i=1}^{m_{1}}\epsilon_{i}\leq\frac{2c}{3}\log
n+\rho\sqrt{\frac{qn}{1-\rho}}+\sqrt{\frac{2cq\rho\log
n}{1-\rho}}=\frac{2c}{3}\log n+o(\log n)$

with probability $1-n^{-c}$.

###### Proof.

By definition, each $\epsilon_{i}$ is bounded by $1$, then applying
Bernstein’s inequality [47, Theorem 2.8.4] yields

$\mathbb{P}\left\\{\sum\limits_{i=1}^{m_{1}}\left(\epsilon_{i}-\mathbb{E}\left[\epsilon_{i}\right]\right)\geq
t\right\\}\leq\exp\left(-\frac{t^{2}/2}{\sigma^{2}+Kt/3}\right)$ (47)

where $K=1$ is the boundary, and

$\sigma^{2}=\sum\limits_{i=1}^{m_{1}}\left(\mathbb{E}[\epsilon_{i}^{2}]-\mathbb{E}[\epsilon_{i}]^{2}\right)\leq\sum\limits_{i=1}^{m_{1}}\mathbb{E}[\epsilon_{i}^{2}]=\sum\limits_{i=1}^{m_{1}}\frac{\mathbb{E}\left[\|\bm{Z}_{i}\|_{\mathrm{F}}^{2}\right]}{m_{2}^{2}d}=\sum\limits_{i=1}^{m_{1}}\frac{q}{m_{2}}=\frac{q\rho}{1-\rho}$

is the variance of the sum. Then, by letting the RHS of (47) equal to $n^{-c}$
for $c>0$, we obtain

$\displaystyle\sum\limits_{i=1}^{m_{1}}\left(\epsilon_{i}-\mathbb{E}\left[\epsilon_{i}\right]\right)$
$\displaystyle\leq\frac{Kc}{3}\log n+\sqrt{\left(\frac{Kc}{3}\log
n\right)^{2}+2\sigma^{2}c\log n}$ (48) $\displaystyle\leq\frac{2Kc}{3}\log
n+\sqrt{2\sigma^{2}c\log n}$

with probability $1-n^{-c}$. Also, by Jensen’s inequality the expectation of
$\epsilon_{i}$ is bounded as

$\mathbb{E}[\epsilon_{i}]=\frac{1}{m_{2}\sqrt{d}}\mathbb{E}\left[\sqrt{\operatorname{Tr}(\bm{Z}_{i}^{\top}\bm{Z}_{i})}\right]\leq\frac{1}{m_{2}\sqrt{d}}\sqrt{\mathbb{E}\left[\operatorname{Tr}(\bm{Z}_{i}^{\top}\bm{Z}_{i})\right]}=\sqrt{\frac{q}{(1-\rho)n}}.$

Plugging this into (48) completes the proof. ∎

###  A.3 Operator norm of random (block) matrices

The following existing result provides an upper bound on the spectrum of an
Erdös–Rényi random graph.

######  Theorem A.6 ([19, Theorem 5]).

Let $\bm{E}\in\mathbb{R}^{n\times n}$ denotes the adjacency matrix of a graph
generated from the Erdös–Rényi model $\mathcal{G}(n,p)$, where the entries
$\\{E_{ij}:i<j\\}$ are independent and $\\{0,1\\}$-valued. Assume that
$\mathbb{E}[E_{ij}]\leq p$ where $p=\Omega(c_{0}\log n/n)$. Then for any
$c>0$, there exists $c_{1}>0$ such that,

$\|\bm{E}-\mathbb{E}[\bm{E}]\|\leq c_{1}\sqrt{np}$

with probability $1-n^{-c}$.

Another important result is the bound the spectrum of a random block matrix
with i.i.d random blocks. That is, let $\bm{S}\in\mathbb{R}^{m_{1}d\times
m_{2}d}$ be an $m_{1}\times m_{2}$ block random matrix where each block
$\bm{S}_{ij}\in\mathbb{R}^{d\times d}$ is i.i.d. such that

$\bm{S}_{ij}=\begin{cases}\bm{R}_{ij},&\quad\text{with probability $q$},\\\
\bm{0},&\quad\text{otherwise}.\end{cases}$ (49)

Here, $\bm{R}_{ij}$ is a random rotation matrix uniformly drawn from
$\mathrm{SO}{(d)}$. Then we have

######  Theorem A.7.

Let $\bm{S}\in\mathbb{R}^{m_{1}d\times m_{2}d}$ be an $m_{1}\times m_{2}$
random block matrix with i.i.d block $\bm{S}_{ij}$ defined in (49). Let
$m_{1},m_{2}=O(n)$. Then, for any $c>0$, there exists $c_{1},c_{2}>0$ such
that

$\|\bm{S}\|\leq c_{1}(\sqrt{qm_{1}}+\sqrt{qm_{2}})+c_{2}\sqrt{\log n}.$

with probability $1-n^{-c}$.

###### Proof.

Our technique is based on the moment method which is broadly used in random
matrix theory (see e.g. [3, 43]). We start from bounding $\|\bm{S}\|$ by the
trace of $\bm{S}\bm{S}^{\top}$ as

$\mathbb{E}\left[\|\bm{S}\|^{2k}\right]=\mathbb{E}\left[\|(\bm{S}\bm{S}^{\top})^{k}\|\right]\leq\mathbb{E}\left[\operatorname{Tr}{\left((\bm{S}\bm{S}^{\top})^{k}\right)}\right]$

which holds for any $k\in\mathbb{N}$. Then,
$\mathbb{E}\left[\operatorname{Tr}{\left((\bm{S}\bm{S}^{\top})^{k}\right)}\right]$
can be expanded as

$\mathbb{E}\left[\operatorname{Tr}{\left((\bm{S}\bm{S}^{\top})^{k}\right)}\right]=\sum\limits_{i_{1},\ldots,i_{k}\in[m_{1}]}\sum\limits_{j_{1},\ldots,j_{k}\in[m_{2}]}\mathbb{E}\left[\operatorname{Tr}{\left(\bm{S}_{i_{1}j_{1}}\bm{S}_{i_{2}j_{1}}^{\top}\bm{S}_{i_{2}j_{2}}\bm{S}_{i_{3}j_{2}}^{\top}\cdots\bm{S}_{i_{k}j_{k}}\bm{S}_{i_{1}j_{k}}^{\top}\right)}\right]$
(50)

where $[m_{1}]:=\\{1,\ldots,m_{1}\\}$ and $[m_{2}]:=\\{1,\ldots,m_{2}\\}$. Let
$G(U,V)$ be a complete bipartite graph with the set of nodes $U=[m_{1}]$ and
$V=[m_{2}]$. Then each $\bm{S}_{ij}$ for $i\in U,\;j\in V$ is associated with
an edge $(i,j)$ on the graph $G$. Furthermore, the matrix product
$\bm{S}_{i_{1}j_{1}}\bm{S}_{i_{2}j_{1}}^{\top}\cdots\bm{S}_{i_{k}j_{k}}\bm{S}_{i_{1}j_{k}}^{\top}$
can be treated as a walk that goes back and forth along $G$ and follows the
path

$i_{1}\rightarrow j_{1}\rightarrow i_{2}\rightarrow
j_{2}\rightarrow\cdots\rightarrow i_{k}\rightarrow j_{k}\rightarrow i_{1}$

which starts and ends at $i_{1}$ as a cycle with $2k$ steps. With this in
mind, let $(i_{1},j_{1},\ldots,i_{k},j_{k})$ denote this walk, since
$\mathbb{E}[\bm{S}_{ij}^{k}]=\bm{0}$ when $k$ is odd, the sum in (50) can be
restricted to even cycles on the graph $G$ where each distinct edge traversed
by the walk should be visited by an even number of times. Therefore, let $W$
denote the set of all such walks, then

$\displaystyle\mathbb{E}\left[\operatorname{Tr}{\left((\bm{S}\bm{S}^{\top})^{k}\right)}\right]$
$\displaystyle=\sum\limits_{(i_{1},j_{1},\ldots,i_{k},j_{k})\in
W}\mathbb{E}\left[\operatorname{Tr}{\left(\bm{S}_{i_{1}j_{1}}\bm{S}_{i_{2}j_{1}}^{\top}\bm{S}_{i_{2}j_{2}}\bm{S}_{i_{3}j_{2}}^{\top}\cdots\bm{S}_{i_{k}j_{k}}\bm{S}_{i_{1}j_{k}}^{\top}\right)}\right]$
$\displaystyle\overset{(a)}{=}\sum\limits_{(i_{1},j_{1},\ldots,i_{k},j_{k})\in
W}\mathbb{E}\left[\operatorname{Tr}{\left(\bm{R}_{i_{1}j_{1}}\bm{R}_{i_{2}j_{1}}^{\top}\\!\cdots\\!\bm{R}_{i_{k}j_{k}}\bm{R}_{i_{1}j_{k}}^{\top}\right)}\right]\mathbb{E}[r_{i_{1}j_{1}}r_{i_{2}j_{1}}\\!\cdots\\!r_{i_{k}j_{k}}r_{i_{1}j_{k}}]$
$\displaystyle\overset{(b)}{\leq}d\sum\limits_{(i_{1},j_{1},\ldots,i_{k},j_{k})\in
W}\mathbb{E}[r_{i_{1}j_{1}}r_{i_{2}j_{1}}\cdots
r_{i_{k}j_{k}}r_{i_{1}j_{k}}],$ (51)

where $(a)$ holds by rewriting $\bm{S}_{ij}=r_{ij}\bm{R}_{ij}$ for some
Bernoulli random variable $r_{ij}$ such that $r_{ij}=1$ with probability $q$
and $r_{ij}=0$ otherwise, $(b)$ holds because the product
$\bm{R}_{i_{1}j_{1}}\cdots\bm{R}_{i_{1}j_{k}}$ is a rotation matrix, therefore
$\|\bm{R}_{i_{1}j_{1}}\bm{R}_{i_{2}j_{1}}^{\top}\cdots\bm{R}_{i_{k}j_{k}}\bm{R}_{i_{1}j_{k}}^{\top}\|=1$
and

$\mathbb{E}\left[\operatorname{Tr}{\left(\bm{R}_{i_{1}j_{1}}\bm{R}_{i_{2}j_{1}}^{\top}\cdots\bm{R}_{i_{k}j_{k}}\bm{R}_{i_{1}j_{k}}^{\top}\right)}\right]\leq
d.$ (52)

To proceed, we introduce a series of i.i.d. symmetric random variables
$t_{ij}$ as

$t_{ij}=\begin{cases}1,&\text{with probability }\frac{q}{2},\\\ -1,&\text{with
probability }\frac{q}{2},\\\ 0,&\text{with probability }1-q.\end{cases}$

for $i\in[m_{1}],j\in[m_{2}]$. As a result, $t_{ij}$ has symmetric
distribution such that $\mathbb{E}[t_{ij}]^{2k-1}=0$ and
$\mathbb{E}[t_{ij}]^{2k}=q,\;\forall k\in\mathbb{N}$. Moreover, the summation
in (51) satisfies

$\displaystyle\sum\limits_{(i_{1},j_{1},\ldots,i_{k},j_{k})\in
W}\mathbb{E}[r_{i_{1}j_{1}}r_{i_{2}j_{1}}\cdots r_{i_{k}j_{k}}r_{i_{1}j_{k}}]$
$\displaystyle=\sum\limits_{(i_{1},j_{1},\ldots,i_{k},j_{k})\in
W}\mathbb{E}[t_{i_{1}j_{1}}t_{i_{2}j_{1}}\cdots t_{i_{k}j_{k}}t_{i_{1}j_{k}}]$
$\displaystyle\overset{(a)}{=}\sum\limits_{i_{1},\ldots,i_{k}\in[m_{1}]}\sum\limits_{j_{1},\ldots,j_{k}\in[m_{2}]}\mathbb{E}[t_{i_{1}j_{1}}t_{i_{2}j_{1}}\cdots
t_{i_{k}j_{k}}t_{i_{1}j_{k}}]$
$\displaystyle=\mathbb{E}\left[\operatorname{Tr}{\left((\bm{T}\bm{T}^{\top})^{k}\right)}\right]$
$\displaystyle\leq\min\\{m_{1},m_{2}\\}\mathbb{E}\left[\|\bm{T}\|^{2k}\right].$
(53)

Here, $\bm{T}\in\mathbb{R}^{m_{1}\times m_{2}}$ is the random matrix whose
$(i,j)$-th entry is $t_{ij}$, the equality $(a)$ holds since any walk
$(i_{1},j_{1},\ldots,i_{k},j_{k})\notin W$ that visits some edge by odd times
vanishes. Therefore, (53) enables us to bound
$\mathbb{E}\left[\operatorname{Tr}{\left((\bm{S}\bm{S}^{\top})^{k}\right)}\right]$
via $\mathbb{E}\left[\|\bm{T}\|^{2k}\right]$. To this end, by computing the
following quantities:

$\displaystyle\sigma_{k,1}$
$\displaystyle=\Bigg{(}\sum\limits_{i=1}^{m_{1}}\Bigg{(}\sum\limits_{j=1}^{m_{2}}\mathbb{E}\left[t_{ij}^{2}\right]\Bigg{)}^{k}\Bigg{)}^{1/2k}=m_{1}^{1/2k}\sqrt{m_{2}q},$
$\displaystyle\sigma_{k,2}$
$\displaystyle=\Bigg{(}\sum\limits_{j=1}^{m_{2}}\Bigg{(}\sum\limits_{i=1}^{m_{1}}\mathbb{E}\left[t_{ij}^{2}\right]\Bigg{)}^{k}\Bigg{)}^{1/2k}=m_{2}^{1/2k}\sqrt{m_{1}q},$
$\displaystyle\sigma_{k}^{*}$
$\displaystyle=\Bigg{(}\sum\limits_{i=1}^{m_{1}}\sum\limits_{j=1}^{m_{2}}\|t_{ij}\|_{\infty}^{2k}\Bigg{)}^{1/2k}=(m_{1}m_{2})^{1/2k}.$

Then applying [23, Theorem 4.9] yields the following bound on
$\mathbb{E}\left[\|\bm{T}\|^{2k}\right]$:

$\displaystyle\mathbb{E}\left[\|\bm{T}\|^{2k}\right]^{1/2k}$
$\displaystyle\leq\sigma_{k,1}+\sigma_{k,2}+C\sqrt{k}\sigma_{k}^{*}\leq
m_{2}^{1/2k}\sqrt{m_{1}q}+m_{1}^{1/2k}\sqrt{m_{2}q}+C\sqrt{k}(m_{1}m_{2})^{1/2k}$
$\displaystyle\leq
n^{1/2k}\left(\sqrt{m_{1}q}+\sqrt{m_{2}q}\right)+C\sqrt{k}n^{1/k}$

for some universal constant $C>0$. Furthermore, by setting $k=\lceil\gamma\log
n\rceil$ for some $\gamma>0$,

$\mathbb{E}\left[\|\bm{T}\|^{2k}\right]^{1/2k}\leq
e^{1/2\gamma}\left(\sqrt{m_{1}q}+\sqrt{m_{2}q}\right)+C^{\prime}\sqrt{\log n}$

for some $C^{\prime}>0$. Finally, by putting all the results together and
using Markov inequality,

$\displaystyle\mathbb{P}\\{\|\bm{S}\|\geq t\\}$
$\displaystyle=\mathbb{P}\\{\|\bm{S}\|^{2k}\geq t^{2k}\\}\leq
t^{-2k}\mathbb{E}\left[\operatorname{Tr}{\left((\bm{S}\bm{S}^{\top})^{k}\right)}\right]$
$\displaystyle\leq
d\min\\{m_{1},m_{2}\\}\Bigg{(}\frac{e^{1/2\gamma}(\sqrt{m_{1}q}+\sqrt{m_{2}q})+C^{\prime}\sqrt{\log
n}}{t}\Bigg{)}^{2\lceil\gamma\log n\rceil},$

for any $t>0$. By setting $\gamma=\frac{c}{2}+1$, for any $c>0$, we can
identify some $c_{1},c_{2}>0$ such that
$t=c_{1}(\sqrt{m_{1}q}+\sqrt{m_{2}q})+c_{2}\sqrt{\log n}$ and
$\mathbb{P}\\{\|\bm{S}\|\geq t\\}\leq n^{-c}$, which completes the proof. ∎

######  Remark 2.

It is worth noting that our result in Theorem A.7 is sharper than either the
one by using $\epsilon$-net argument (e.g. [47, Theorem 4.6.1]) or the one by
applying matrix Bernstein (e.g. [27, Lemma 5.14]). If using $\epsilon$-net
argument, we get $\|\bm{S}\|\leq c_{1}\sqrt{qnd}+c_{2}\sqrt{\log n}$ with high
probability for some $c_{1},c_{2}>0$, which has an additional factor of
$\sqrt{d}$ in the leading term compared to our result. If using matrix
Bernstein, we obtain $\|\bm{S}\|\leq
c_{1}\sqrt{q\max\\{m_{1},m_{2}\\}\left(\log nd+c_{2}\log n\right)}$ with high
probability for some $c_{1},c_{2}>0$, which is loose by a factor $\sqrt{\log
nd}$ compared to our result. These bounds are not adequate enough in our
analysis and thus it is necessary to have a sharp result as in Theorem A.7.

###### Proof of Lemma 3.6.

Let us define

$\bm{A}=\begin{pmatrix}\widetilde{\bm{A}}_{11}&\widetilde{\bm{A}}_{12}\\\
\widetilde{\bm{A}}_{12}^{\top}&\widetilde{\bm{A}}_{22}\\\
\end{pmatrix},\quad\mathbb{E}\left[\bm{A}\right]-\bm{A}=:\begin{pmatrix}\bm{S}_{11}&\bm{S}_{12}\\\
\bm{S}_{12}^{\top}&\bm{S}_{22}\end{pmatrix},\quad\bm{S}_{\text{in}}:=\begin{pmatrix}\bm{S}_{11}&\bm{0}\\\
\bm{0}&\bm{S}_{22}\end{pmatrix},\quad\bm{S}_{\text{out}}:=\begin{pmatrix}\bm{0}&\bm{S}_{12}\\\
\bm{S}_{12}^{\top}&\bm{0}\end{pmatrix},$

where the two diagonal blocks represent the two clusters, then by triangle
inequality
$\|\mathbb{E}[\bm{A}]-\bm{\bm{A}}\|=\|\bm{S}_{\text{in}}+\bm{S}_{\text{out}}\|\leq\|\bm{S}_{\text{in}}\|+\|\bm{S}_{\text{out}}\|.$
Moreover, notice
$\|\bm{S}_{\text{in}}\|=\max\left\\{\|\bm{S}_{11}\|,\;\|\bm{S}_{22}\|\right\\}\leq\|\bm{S}_{11}\|+\|\bm{S}_{22}\|$
and $\|\bm{S}_{\text{out}}\|=\|\bm{S}_{12}\|$, it holds

$\|\mathbb{E}[\bm{A}]-\bm{\bm{A}}\|\leq\|\bm{S}_{11}\|+\|\bm{S}_{22}\|+\|\bm{S}_{12}\|.$

As a result, we can bound $\bm{S}_{11}$, $\bm{S}_{22}$ and $\bm{S}_{12}$ them
separately. For $\bm{S}_{11}$, by definition
$\bm{S}_{11}=\mathbb{E}[\widetilde{\bm{A}}_{11}]-\widetilde{\bm{A}}_{11}$.
Then if we define $\bm{E}_{1}\in\mathbb{R}^{m_{1}\times m_{1}}$ be the
adjacency matrix of the subgraph on $C_{1}$ which is generated from the
Erdös–Rényi model $\mathcal{G}(m_{1},p)$, $\widetilde{\bm{A}}_{11}$ can be
expressed as $\widetilde{\bm{A}}_{11}=\bm{E}_{1}\otimes\bm{I}_{d}$ under the
assumption $\bm{R}_{i}=\bm{I}_{d}$ for $i=1,\ldots,n$, where $\otimes$ denotes
the tensor product. Therefore, we have

$\|\bm{S}_{11}\|=\|\mathbb{E}[\widetilde{\bm{A}}_{11}]-\widetilde{\bm{A}}_{11}\|=\|(\mathbb{E}[\bm{E}_{1}]-\bm{E}_{1})\otimes\bm{I}_{d}\|=\|\mathbb{E}[\bm{E}_{1}]-\bm{E}_{1}\|.$

This enables us to study $\|\bm{S}_{11}\|$ via
$\|\mathbb{E}[\bm{E}_{1}]-\bm{E}_{1}\|$, which is bounded by Theorem A.6 as
$\|\bm{S}_{11}\|\leq c_{1}\sqrt{pm_{1}}$ with probability $1-n^{-c}$ for some
$c_{1},c>0$. $\|\bm{S}_{22}\|$ is bounded in a similar manner and we do not
repeat. For $\|\bm{S}_{12}\|$, we apply Theorem A.7 and get
$\|\bm{S}_{12}\|\leq c_{2}(\sqrt{qm_{1}}+\sqrt{qm_{2}})+O(\sqrt{\log n})$ with
probability $1-n^{-c}$ for some $c_{2},c>0$. Combining these completes the
proof. ∎

##  Appendix B Proof of main results

This section is devoted to the proofs of theorems in Section 3. In Sections
B.1 and B.2 we provide detailed proofs for the lemmas and theorems presented
in Sections 3.1.1 and 3.2.1 respectively. In Section B.3 we consider the case
of two clusters with unknown cluster sizes.

###  B.1 Two equal-sized clusters with known cluster sizes

###### Proof of Lemma 3.2.

The optimality is immediately established since (9) is convex then KKT
conditions are sufficient for $\bm{M}^{*}$ being optimal [8]. For the
uniqueness, suppose there exists another optimal solution
$\widetilde{\bm{M}}\neq\bm{M}^{*}$, then the following holds:

$\displaystyle
0\overset{(a)}{=}\langle\bm{A},\widetilde{\bm{M}}-\bm{M}^{*}\rangle$
$\displaystyle\overset{(b)}{=}-\langle\bm{\Lambda},\widetilde{\bm{M}}-\bm{M}^{*}\rangle-\langle\mathrm{diag}(\\{\bm{Z}_{i}\\}_{i=1}^{n}),\widetilde{\bm{M}}-\bm{M}^{*}\rangle+\langle\bm{\Theta}+\bm{\Theta}^{\top},\widetilde{\bm{M}}-\bm{M}^{*}\rangle$
$\displaystyle\overset{(c)}{=}-\langle\bm{\Lambda},\widetilde{\bm{M}}-\bm{M}^{*}\rangle+\langle\bm{\Theta}+\bm{\Theta}^{\top},\widetilde{\bm{M}}-\bm{M}^{*}\rangle$
$\displaystyle\overset{(d)}{=}-\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle+\langle\bm{\Theta}+\bm{\Theta}^{\top},\widetilde{\bm{M}}-\bm{M}^{*}\rangle$
$\displaystyle\overset{(e)}{=}-\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle+2\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}\rangle,$
(54)

where ($a$) holds since both $\widetilde{\bm{M}}$ and $\bm{M}^{*}$ are optimal
and they should share the same primal value, i.e.,
$\langle\bm{A},\widetilde{\bm{M}}\rangle=\langle\bm{A},\bm{M}^{*}\rangle$;
($b$) follows from (11); ($c$) comes from the constraint in (9) that
$\bm{M}_{ii}^{*}=\widetilde{\bm{M}}_{ii}=\bm{I}_{d}$, for $i=1,\ldots,n$;
($d$) uses $\langle\bm{\Lambda},\;\bm{M}^{*}\rangle=0$ in (13); and ($e$)
holds because both $\widetilde{\bm{M}}$ and $\bm{M}^{*}$ are symmetric. To
proceed, let us rewrite

$\displaystyle\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}\rangle$
$\displaystyle=\langle\bm{\Theta},\widetilde{\bm{M}}\rangle-\langle\bm{\Theta},\bm{M}^{*}\rangle=\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\widetilde{\bm{M}}_{ij}\rangle-\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\bm{M}_{ij}^{*}\rangle.$
(55)

Then by plugging the explicit expression of $\bm{\Theta}_{ij}$ in (12) into
(55) we obtain

$\displaystyle\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\bm{M}_{ij}^{*}\rangle$
$\displaystyle\overset{(a)}{=}\sum\limits_{i}\sum\limits_{j:C(j)=C(i)}\frac{\mu_{i}}{\sqrt{d}}\langle\bm{M}_{ij}^{*},\bm{M}_{ij}^{*}\rangle=\sum\limits_{i}\mu_{i}m\sqrt{d},$
(56)
$\displaystyle\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\widetilde{\bm{M}}_{ij}\rangle$
$\displaystyle\overset{(b)}{=}\sum\limits_{i}\mu_{i}\bigg{(}\sum\limits_{j:C(j)=C(i)}\frac{1}{\sqrt{d}}\langle\bm{M}_{ij}^{*},\widetilde{\bm{M}}_{ij}\rangle+\sum\limits_{j:C(j)\neq
C(i)}\langle\bm{\alpha}_{ij},\widetilde{\bm{M}}_{ij}\rangle\bigg{)}$
$\displaystyle\overset{(c)}{\leq}\sum\limits_{i}\mu_{i}\bigg{(}\sum\limits_{j:C(j)=C(i)}\frac{1}{\sqrt{d}}\|\bm{M}_{ij}^{*}\|_{\mathrm{F}}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}+\sum\limits_{j:C(j)\neq
C(i)}\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\bigg{)}$
$\displaystyle\overset{(d)}{\leq}\sum\limits_{i}\mu_{i}\sum\limits_{j}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\overset{(e)}{\leq}\sum\limits_{i}\mu_{i}m\sqrt{d}$

where both ($a$) and ($b$) hold because $\bm{M}^{*}_{ij}=\bm{0},\;C(i)\neq
C(j)$; ($c$) follows from Cauchy-Schwartz inequality; ($d$) uses
$\|\bm{\alpha}_{ij}\|_{\textrm{F}}\leq 1$ in (12); ($e$) comes from
$\sum_{j}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\leq m\sqrt{d}$, for
$i=1,\ldots,n$ in (9). As a result, combining (55) and (56) yields
$\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}\rangle\leq 0$. Plugging this
back into (54) gives $\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle\leq 0$. On
the other hand, from $\bm{\Lambda}\succeq 0$ in (14) and
$\widetilde{\bm{M}}\succeq 0$ in (9) we have
$\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle\geq 0$. Then it holds that
$\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle=0$. With this in mind,
combining the assumption $\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*})$
with
$\bm{M}^{*}=\bm{V}^{(1)}(\bm{V}^{(1)})^{\top}+\bm{V}^{(2)}(\bm{V}^{(2)})^{\top}$
in (4), $\widetilde{\bm{M}}$ satisfies

$\widetilde{\bm{M}}=\bm{V}^{(1)}\bm{\Sigma}_{1}(\bm{V}^{(1)})^{\top}+\bm{V}^{(2)}\bm{\Sigma}_{2}(\bm{V}^{(2)})^{\top}$

for some $d\times d$ diagonal matrices $\bm{\Sigma}_{1},\bm{\Sigma}_{2}\succeq
0$. Furthermore, from the constraint in (9) that
$\widetilde{\bm{M}}_{ii}=\bm{I}_{d}$, we obtain
$\bm{\Sigma}_{1}=\bm{\Sigma}_{2}=\bm{I}_{d}$, then
$\widetilde{\bm{M}}=\bm{V}^{(1)}(\bm{V}^{(1)})^{\top}+\bm{V}^{(2)}(\bm{V}^{(2)})^{\top}=\bm{M}^{*}$
which contradicts with the assumption $\widetilde{\bm{M}}\neq\bm{M}^{*}$.
Therefore, $\bm{M}^{*}$ is the unique solution. ∎

###### Proof of Lemma 3.3.

Recall the assumption $\bm{R}_{i}=\bm{I}_{d},\;i=1,\ldots,n$. From (11) we get
$\bm{\Lambda}=-\bm{A}-\mathrm{diag}\left(\\{\bm{Z}_{i}\\}_{i=1}^{n}\right)+\bm{\Theta}+\bm{\Theta}^{\top}$,
plugging this into (15) yields

$\displaystyle\sum\limits_{j:C(j)=C(i)}\bm{\Theta}_{ij}+\bm{\Theta}_{ji}^{\top}-\bm{A}_{ij}=\bm{Z}_{i},\quad
i=1,\ldots,n$ (57) $\displaystyle\sum\limits_{j:C(j)\neq
C(i)}\bm{\Theta}_{ij}+\bm{\Theta}_{ji}^{\top}-\bm{A}_{ij}=\bm{0},\quad
i=1,\ldots,n.$ (58)

To determine $\bm{\Theta}_{ij}$, notice that (12) can be written as

$\bm{\Theta}_{ij}=\begin{cases}\displaystyle\mu_{i}\bm{M}_{ij}^{*}/\sqrt{d},&\;C(i)=C(j),\\\
\mu_{i}\bm{\alpha}_{ij},\;\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq 1,&\;C(i)\neq
C(j),\end{cases}$ (59)

where we use the fact $\bm{M}_{ij}^{*}\neq\bm{0}$ if and only if $C(i)=C(j)$.
Then let us consider the case when $C(i)\neq C(j)$. Importantly, our ansatz of
$\bm{\Theta}_{ij}$ is of the following form:

$\bm{\Theta}_{ij}=\widetilde{\bm{\alpha}}_{i},\quad\forall j:C(j)\neq C(i),$
(60)

for some $\widetilde{\bm{\alpha}}_{i}$. To solve it, plugging (60) into (58)
yields

$\displaystyle\widetilde{\bm{\alpha}}_{i}$
$\displaystyle=\frac{1}{m}\sum\limits_{j\in
C_{2}}\bm{A}_{ij}-\frac{1}{m}\sum\limits_{j\in
C_{2}}\widetilde{\bm{\alpha}}_{j}^{\top},\quad i\in C_{1},$ (61)
$\displaystyle\widetilde{\bm{\alpha}}_{j}$
$\displaystyle=\frac{1}{m}\sum\limits_{s\in
C_{1}}\bm{A}_{js}-\frac{1}{m}\sum\limits_{s\in
C_{1}}\widetilde{\bm{\alpha}}_{s}^{\top},\quad j\in C_{2}.$ (62)

By combining (61) and (62) we get

$\displaystyle\widetilde{\bm{\alpha}}_{i}-\frac{1}{m}\sum\limits_{s\in
C_{1}}\widetilde{\bm{\alpha}}_{s}=\frac{1}{m}\sum\limits_{j\in
C_{2}}\bm{A}_{ij}-\frac{1}{m^{2}}\sum\limits_{s\in C_{1}}\sum\limits_{j\in
C_{2}}\bm{A}_{sj},\quad i\in C_{1},$
$\displaystyle\widetilde{\bm{\alpha}}_{j}-\frac{1}{m}\sum\limits_{s\in
C_{2}}\widetilde{\bm{\alpha}}_{s}=\frac{1}{m}\sum\limits_{i\in
C_{1}}\bm{A}_{ji}-\frac{1}{m^{2}}\sum\limits_{s\in C_{2}}\sum\limits_{i\in
C_{1}}\bm{A}_{si},\quad j\in C_{2}.$

Then it is natural to guess $\widetilde{\bm{\alpha}}_{i}$ for $i\in C_{1}$ and
$\widetilde{\bm{\alpha}}_{j}$ for $j\in C_{2}$ has the form

$\widetilde{\bm{\alpha}}_{i}=\frac{1}{m}\sum_{s\in
C_{2}}\bm{A}_{is}-\bm{\alpha}^{(1)},\quad i\in
C_{1},\quad\widetilde{\bm{\alpha}}_{j}=\frac{1}{m}\sum_{s\in
C_{2}}\bm{A}_{js}-\bm{\alpha}^{(2)},\quad j\in C_{2}$

for some $\bm{\alpha}^{(1)}$ and $\bm{\alpha}^{(2)}$. By further plugging this
into (61) or (62) we obtain

$\bm{\alpha}^{(1)}+(\bm{\alpha}^{(2)})^{\top}=\frac{1}{m^{2}}\sum_{s_{1}\in
C_{1}}\sum_{s_{2}\in C_{2}}\bm{A}_{s_{1}s_{2}}.$

By symmetry we guess
$\bm{\alpha}^{(1)}=(\bm{\alpha}^{(2)})^{\top}=\frac{1}{2m^{2}}\sum_{s_{1}\in
C_{1}}\sum_{s_{2}\in C_{2}}\bm{A}_{s_{1}s_{2}}$, which leads to our guess of
$\widetilde{\bm{\alpha}}_{i}$ given in Lemma 3.3. Now it remains to determine
$\mu_{i}$: From (59) and (60) we see that when $C(i)\neq C(j)$,
$\|\bm{\Theta}_{ij}\|_{\mathrm{F}}=\mu_{i}\|\bm{\alpha}_{ij}\|_{\mathrm{F}}=\|\widetilde{\bm{\alpha}}_{i}\|_{\mathrm{F}}$.
Also, due to the constraint in (12) that
$\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq 1$, $\mu_{i}$ should satisfy
$\mu_{i}\geq\|\widetilde{\bm{\alpha}}_{i}\|_{\textrm{F}}$. Then we guess
$\mu_{i}=\|\widetilde{\bm{\alpha}}_{i}\|_{\mathrm{F}}$. As we shall see in
Lemma 3.4, this is to make $\mu_{i}$ as small as possible such that the
eigenvalues of $\bm{\Lambda}$ are greater and the condition
$\bm{\Lambda}\succeq 0$ benefits from it. To complete the proof, plugging
$\bm{\Theta}_{ij}$ in (69) with $\bm{M}_{ij}^{*}=\bm{I}_{d}$ into (57) yields
the form of $\bm{Z}$. ∎

###### Proof of Lemma 3.4.

Let us rewrite $\bm{A}$, $\bm{\Lambda}$ and $\bm{\Theta}$ into four blocks as

$\bm{A}=\begin{pmatrix}\widetilde{\bm{A}}_{11}&\widetilde{\bm{A}}_{12}\\\
\widetilde{\bm{A}}_{12}^{\top}&\widetilde{\bm{A}}_{22}\\\
\end{pmatrix},\quad\bm{\Lambda}=\begin{pmatrix}\bm{\Lambda}_{11}&\bm{\Lambda}_{12}\\\
\bm{\Lambda}_{21}&\bm{\Lambda}_{22}\end{pmatrix},\quad\bm{\Theta}=\begin{pmatrix}\widetilde{\bm{\Theta}}_{11}&\widetilde{\bm{\Theta}}_{12}\\\
\widetilde{\bm{\Theta}}_{21}&\widetilde{\bm{\Theta}}_{22}\end{pmatrix}$ (63)

where the two diagonal blocks represent $C_{1}$ and $C_{2}$ respectively. By
assumption the two diagonal blocks of $\bm{M}^{*}$ in (4) satisfy
$\widetilde{\bm{M}}^{*}_{1}\\!=\\!\widetilde{\bm{M}}^{*}_{2}\\!=\\!(\bm{1}_{m}\bm{1}_{m}^{\top})\otimes\bm{I}_{d}$.
Let
$\widetilde{\bm{\mu}}_{1}=\mathrm{diag}(\\{\mu_{i}\bm{I}_{d}\\}_{i=1}^{m})\in\mathbb{R}^{md\times
md}$ and
$\widetilde{\bm{\mu}}_{2}=\mathrm{diag}(\\{\mu_{i}\bm{I}_{d}\\}_{i=m+1}^{n})\in\mathbb{R}^{md\times
md}$ be two diagonal block matrices whose diagonal blocks are
$\mu_{i}\bm{I}_{d}$ for $i\in C_{1}$ and $i\in C_{2}$ respectively. Then from
Lemma 3.3 each block of $\bm{\Theta}$ can be expressed as

$\displaystyle\widetilde{\bm{\Theta}}_{11}=\frac{\widetilde{\bm{\mu}}_{1}\widetilde{\bm{M}}_{1}^{*}}{\sqrt{d}},$
$\displaystyle\quad\widetilde{\bm{\Theta}}_{12}=\frac{1}{m}\widetilde{\bm{A}}_{12}\widetilde{\bm{M}}_{2}^{*}-\frac{1}{2m^{2}}\widetilde{\bm{M}}_{1}^{*}\widetilde{\bm{A}}_{12}\widetilde{\bm{M}}_{2}^{*},$
$\displaystyle\widetilde{\bm{\Theta}}_{21}=\frac{1}{m}\widetilde{\bm{A}}_{21}\widetilde{\bm{M}}_{1}^{*}-\frac{1}{2m^{2}}\widetilde{\bm{M}}_{2}^{*}\widetilde{\bm{A}}_{21}\widetilde{\bm{M}}_{1}^{*},$
$\displaystyle\quad\widetilde{\bm{\Theta}}_{22}=\frac{\widetilde{\bm{\mu}}_{2}\widetilde{\bm{M}}_{2}^{*}}{\sqrt{d}}.$

Given the above, from Lemma 3.3, each block of $\bm{\Lambda}$ can be expressed
as

$\displaystyle\widetilde{\bm{\Lambda}}_{12}$
$\displaystyle=-\widetilde{\bm{A}}_{12}+\widetilde{\bm{\Theta}}_{12}+\widetilde{\bm{\Theta}}_{21}^{\top}=-\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{1}^{*}\right)\widetilde{\bm{A}}_{12}\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{2}^{*}\right),$
$\displaystyle\widetilde{\bm{\Lambda}}_{21}$
$\displaystyle=-\widetilde{\bm{A}}_{21}+\widetilde{\bm{\Theta}}_{21}+\widetilde{\bm{\Theta}}_{12}^{\top}=-\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{2}^{*}\right)\widetilde{\bm{A}}_{21}\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{1}^{*}\right),$
$\displaystyle\widetilde{\bm{\Lambda}}_{11}$
$\displaystyle=-\widetilde{\bm{A}}_{11}-\mathrm{diag}(\\{\bm{Z}_{i}\\}_{i=1}^{m})+\frac{1}{\sqrt{d}}\widetilde{\bm{\mu}}_{1}\widetilde{\bm{M}}_{1}^{*}+\frac{1}{\sqrt{d}}\widetilde{\bm{M}}_{1}^{*}\widetilde{\bm{\mu}}_{1}^{\top}$
$\displaystyle=-\widetilde{\bm{A}}_{11}-\mathrm{diag}\bigg{(}\bigg{\\{}\bigg{(}\frac{m\mu_{i}}{\sqrt{d}}+\sum\limits_{s\in
C_{1}}\bigg{(}\frac{\mu_{s}}{\sqrt{d}}-r_{is}\bigg{)}\bigg{)}\bm{I}_{d}\bigg{\\}}_{i=1}^{m}\bigg{)}+\frac{1}{\sqrt{d}}\widetilde{\bm{\mu}}_{1}\widetilde{\bm{M}}_{1}^{*}+\frac{1}{\sqrt{d}}\widetilde{\bm{M}}_{1}^{*}\widetilde{\bm{\mu}}_{1}^{\top}$
$\displaystyle=\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{1}^{*}\right)\bigg{(}-\widetilde{\bm{A}}_{11}-\mathrm{diag}\left(\\{\bm{Z}_{i}\\}_{i=1}^{m}\right)\bigg{)}\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{1}^{*}\right),$
$\displaystyle\widetilde{\bm{\Lambda}}_{22}$
$\displaystyle=\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{2}^{*}\right)\bigg{(}-\widetilde{\bm{A}}_{22}-\mathrm{diag}\left(\\{\bm{Z}_{i}\\}_{i=m+1}^{n}\right)\bigg{)}\left(\bm{I}_{md}-\frac{1}{m}\widetilde{\bm{M}}_{2}^{*}\right).$

Then, $\bm{\Lambda}$ can be simply expressed as

$\bm{\Lambda}=(\bm{I}_{nd}-\bm{\Pi})\left(-\bm{Z}-\bm{A}\right)(\bm{I}_{nd}-\bm{\Pi}).$
(64)

To proceed, notice that the expectation of $\bm{A}$ is given as

$\mathbb{E}[\bm{A}]=\begin{pmatrix}\mathbb{E}[\widetilde{\bm{A}}_{11}]&\mathbb{E}[\widetilde{\bm{A}}_{12}]\\\
\mathbb{E}[\widetilde{\bm{A}}_{21}]&\mathbb{E}[\widetilde{\bm{A}}_{22}]\end{pmatrix}=\begin{pmatrix}p\widetilde{\bm{M}}_{1}^{*}-p\bm{I}_{md}&\bm{0}\\\
\bm{0}&p\widetilde{\bm{M}}_{2}^{*}-p\bm{I}_{md}\end{pmatrix}=\begin{pmatrix}p\widetilde{\bm{M}}_{1}^{*}&\bm{0}\\\
\bm{0}&p\widetilde{\bm{M}}_{2}^{*}\end{pmatrix}-p\bm{I}_{nd},$

where $p\bm{I}_{nd}$ comes from the convention
$\bm{A}_{ii}=\bm{0},\;i=1,\ldots,n$. Then one can see that

$\displaystyle(\bm{I}_{nd}-\bm{\Pi})(\mathbb{E}[\bm{A}]+p\bm{I}_{nd})(\bm{I}_{nd}-\bm{\Pi})=\bm{0}.$
(65)

Therefore, by plugging (65) into (64) we obtain
$\bm{\Lambda}=(\bm{I}_{nd}-\bm{\Pi})\widetilde{\bm{\Lambda}}(\bm{I}_{nd}-\bm{\Pi})$
with $\widetilde{\bm{\Lambda}}$ defined in Lemma 3.3. This yields two
observations: (1) $\bm{\Lambda}\succeq 0$ is satisfied if
$\widetilde{\bm{\Lambda}}\succeq 0$; (2) $\bm{I}_{nd}-\bm{\Pi}$ is a
projection matrix such that
$\mathcal{N}(\bm{I}_{nd}-\bm{\Pi})=\mathcal{R}(\bm{M}^{*})$, which implies
$\mathcal{N}(\bm{\Lambda})\supseteq\mathcal{R}(\bm{M}^{*})$. When
$\widetilde{\bm{\Lambda}}\succ 0$, for all
$\bm{x}\notin\mathcal{R}(\bm{M}^{*})$, $\bm{\Lambda}\bm{x}\neq\bm{0}$ since
$\bm{x}\notin\mathcal{N}(\bm{I}_{nd}-\bm{\Pi})$. Combining it with the fact
that $\mathcal{N}(\bm{\Lambda})\supseteq\mathcal{R}(\bm{M}^{*})$, we have
$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*})$ if
$\widetilde{\bm{\Lambda}}\succ 0$. As a result, $\widetilde{\bm{\Lambda}}\succ
0$ ensures both $\bm{\Lambda}\succeq 0$ and
$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*})$ are satisfied. ∎

###### Proof of Lemma 3.5.

According to Lemma 3.4, notice that $\bm{Z}$ is a diagonal matrix, then
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})$ turns out to be the smallest
diagonal entry of $p\bm{I}_{nd}-\bm{Z}$. This leads to

$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})=\min_{i}\left(x_{i}-y_{i}-\epsilon_{C(i)}\right)+p\geq\min_{i}x_{i}-\max_{i}y_{i}-\max\\{\epsilon_{1},\epsilon_{2}\\}+p.$

with $x_{i},y_{i},\epsilon_{1},\epsilon_{2}$ defined in Lemma 3.5, and we can
bound them separately.

For $x_{i}$, recall that $r_{is}$ is a Bernoulli random variable with
$\mathbb{P}\\{r_{is}=1\\}=p$. Then $x_{i}\sim\textrm{Binom}\left(m,p\right)$
that follows a binomial distribution. Applying the existing tail bound in
Lemma A.1 with $\rho=1/2$ and the union bound yields the result for
$\min_{i}x_{i}$.

For $y_{i}$, by definition

$\displaystyle y_{i}$
$\displaystyle=\frac{m\|\widetilde{\bm{\alpha}}_{i}\|_{\mathrm{F}}}{\sqrt{d}}=\frac{m}{\sqrt{d}}\bigg{\|}\frac{1}{m}\sum\limits_{j:C(j)\neq
C(i)}\bm{A}_{ij}-\frac{1}{2m^{2}}\sum\limits_{j:C(j)\neq
C(i)}\sum\limits_{s:C(s)=C(i)}\bm{A}_{sj}\bigg{\|}_{\mathrm{F}}$
$\displaystyle\leq\underbrace{\frac{1}{\sqrt{d}}\bigg{\|}\sum\limits_{j:C(j)\neq
C(i)}\bm{A}_{ij}\bigg{\|}_{\mathrm{F}}}_{=:y_{i1}}+\underbrace{\frac{1}{2m\sqrt{d}}\bigg{\|}\sum\limits_{j:C(j)\neq
C(i)}\sum\limits_{s:C(s)=C(i)}\bm{A}_{sj}\bigg{\|}_{\mathrm{F}}}_{=:y_{i2}}=y_{i1}+y_{i2}.$

As a result, both $y_{i1}$ and $y_{i2}$ consist of $\|\sum_{i}\bm{X}_{i}\|$
where each $\bm{X}_{i}\in\mathbb{R}^{d\times d}$ is i.i.d. and uniformly
distributed in $\mathrm{SO}(d)$. This can be bounded by matrix concentration
inequalities such as matrix Bernstein [45] in general. Therefore, by applying
Theorem A.3 we obtain

$\displaystyle y_{i1}$ $\displaystyle\leq\sqrt{2qm(c\log n+\log
2d)}\left(\sqrt{1+\frac{c\log n+\log 2d}{18qm}}+\sqrt{\frac{c\log n+\log
2d}{18qm}}\right)$ (66) $\displaystyle\overset{(a)}{\approx}\sqrt{c\beta}\log
n$

with probability $1-n^{-c}$ for any $c>0$, where $(a)$ comes from (43).
Similarly, by applying Theorem A.3 on $y_{i2}$ we get $y_{i2}=o(\log n)$ with
high probability. Combining the results above and applying the union bound
yields the result for $\max_{i}y_{i}$.

For $\epsilon_{1}$ and $\epsilon_{2}$, by symmetry they should have the same
statistics, so let us focus on $\epsilon_{1}$, which satisfies

$\displaystyle\epsilon_{1}=\frac{1}{\sqrt{d}}\sum\limits_{s\in
C_{1}}\mu_{s}=\frac{1}{\sqrt{d}}\sum\limits_{s\in
C_{1}}\|\widetilde{\bm{\alpha}}_{s}\|_{\mathrm{F}}\leq\underbrace{\frac{1}{m\sqrt{d}}\sum\limits_{s\in
C_{1}}\Bigg{\|}\sum\limits_{j\in
C_{2}}\bm{A}_{sj}\Bigg{\|}_{\textrm{F}}}_{=:\epsilon_{1}^{(1)}}+\underbrace{\frac{1}{2m\sqrt{d}}\Bigg{\|}\sum\limits_{j\in
C_{2}}\sum\limits_{s\in
C_{1}}\bm{A}_{sj}\Bigg{\|}_{\mathrm{F}}}_{=:\epsilon_{1}^{(2)}}$
$\displaystyle=\epsilon_{1}^{(1)}+\epsilon_{1}^{(2)}.$

Then, by applying Lemma A.5 on $\epsilon^{(1)}_{1}$ with $m_{1}=m_{2}=m$ we
get $\epsilon^{(1)}_{1}=(3c/2)\log n+o(\log n)$ and
$\epsilon_{1}^{(2)}=y_{i2}=o(\log n)$ with probability $1-n^{-c}$, this leads
to the bound on $\epsilon_{1}$ and $\epsilon_{2}$. By further applying the
union bound we get the result on $\max\\{\epsilon_{1},\epsilon_{2}\\}$.

Specifically when $d=2$, a tighter bound on $y_{i}$ is obtained by applying
Theorem A.4 instead of Theorem A.3 for bounding $y_{i1}$ and $y_{i2}$, which
yields $y_{i1}\leq\sqrt{c\beta/2}\log n+o(\log n)$ and $y_{i2}=o(\log n)$ with
probability $1-n^{-c}$. The remaining is the save as above. ∎

###  B.2 Two unequal-sized clusters with known cluster sizes

###### Proof of Lemma 3.8.

The proof is very similar to the one for Lemma 3.2, with a tiny difference on
evaluating $\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}_{ij}\rangle$ in
(56), where in this case $\mu_{i}$ is replaced by $\mu_{i}+\nu$. Therefore we
do not repeat. ∎

###### Proof of Lemma 3.9.

First, we obtain
$\bm{\Lambda}=-\bm{A}-\text{diag}(\\{\bm{Z}_{i}\\}_{i=1}^{n})+\bm{\Theta}+\bm{\Theta}^{\top}$
from (22), then plugging this into (27) yields

$\displaystyle\sum_{j:C(j)=C(i)}\bm{\Theta}_{ij}+\bm{\Theta}_{ji}^{\top}-\bm{A}_{ij}=\bm{Z}_{i},$
$\displaystyle\quad i=1,\ldots,n$ (67) $\displaystyle\sum_{j:C(j)\neq
C(i)}\bm{\Theta}_{ij}+\bm{\Theta}_{ji}^{\top}-\bm{A}_{ij}=\bm{0},$
$\displaystyle\quad i=1,\ldots,n.$ (68)

Next, to determine $\bm{\Theta}_{ij}$, (23) can be rewritten as

$\bm{\Theta}_{ij}=\begin{cases}\displaystyle(\mu_{i}+\nu)\bm{I}_{d}/\sqrt{d},&\;C(i)=C(j),\\\
(\mu_{i}+\nu)\bm{\alpha}_{ij},\;\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq
1,&\;C(i)\neq C(j).\end{cases}$ (69)

Then one can check that our guess of $\bm{\Theta}_{ij}$ in Lemma 3.9 indeed
satisfies (68) and (69). It remains to determine $\nu$ and $\mu_{i}$ for
$i=1,\ldots,n$: From (25) we get $\mu_{i}=0,\;\forall i\in C_{2}$, since
$m_{1}>m_{2}$. Then from (69), due to the constraint
$\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq 1$, $\nu$ and $\mu_{i}$ satisfy

$\displaystyle\nu+\mu_{i}\geq\|\bm{\Theta}_{ij}\|_{\mathrm{F}},\quad\forall
i\in
C_{1}\quad\text{and}\quad\nu\geq\|\bm{\Theta}_{ij}\|_{\mathrm{F}},\quad\forall
i\in C_{2}.$

This leads to our guess of $\nu$ and $\mu_{i}$ in Lemma 3.9. Plugging this
back into (67) we obtain the expression of $\bm{Z}$. ∎

###### Proof of Lemma 3.10.

We follow the same route in Lemma 3.4 by first rewriting $\bm{A}$,
$\bm{\Lambda}$ and $\bm{\Theta}$ into four blocks as (63). Let
$\widetilde{\bm{\mu}}_{1}:=\text{diag}(\left\\{\mu_{i}\bm{I}_{d}\right\\}_{i=1}^{m_{1}})\in\mathbb{R}^{m_{1}d\times
m_{1}d}$. Then one can see that the four blocks of $\bm{\Theta}$ satisfy

$\displaystyle\widetilde{\bm{\Theta}}_{11}=\frac{(\widetilde{\bm{\mu}}_{1}+\nu\bm{I}_{m_{1}d})\widetilde{\bm{M}}_{1}^{*}}{\sqrt{d}},\quad\quad\quad\widetilde{\bm{\Theta}}_{22}=\frac{\nu\widetilde{\bm{M}}_{2}^{*}}{\sqrt{d}},$
$\displaystyle\widetilde{\bm{\Theta}}_{12}+\widetilde{\bm{\Theta}}_{21}^{\top}=\frac{1}{m_{1}}\widetilde{\bm{M}}_{1}^{*}\widetilde{\bm{A}}_{21}+\frac{1}{m_{2}}\widetilde{\bm{A}}_{12}\widetilde{\bm{M}}_{2}^{*}-\frac{1}{m_{1}m_{2}}\widetilde{\bm{M}}_{1}^{*}\widetilde{\bm{A}}_{12}\widetilde{\bm{M}}_{2}^{*}.$

By plugging these into the four blocks of $\bm{\Lambda}$, one can simplify
$\bm{\Lambda}$ as (we leave the detail to readers who are interested)

$\displaystyle\bm{\Lambda}$
$\displaystyle=(\bm{I}_{nd}-\bm{\Pi})(-\bm{Z}-\bm{A})(\bm{I}_{nd}-\bm{\Pi})=(\bm{I}_{nd}-\bm{\Pi})(\mathbb{E}[\bm{A}]-\bm{A}-\bm{Z}+p\bm{I}_{nd})(\bm{I}_{nd}-\bm{\Pi})$

where we use (65) that
$\left(\bm{I}_{nd}-\bm{\Pi}\right)(\mathbb{E}[\bm{A}]+p\bm{I}_{nd})\left(\bm{I}_{nd}-\bm{\Pi}\right)=\bm{0}$.
As a result, by using the same argument as in the proof of Lemma 3.4, one can
see that $\widetilde{\bm{\Lambda}}\succ 0$ ensures both $\bm{\Lambda}\succeq
0$ and $\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bm{M}^{*})$ are satisfied. ∎

###### Proof of Lemma 3.11.

We first define the following quantities and provide their individual
analysis.

$\displaystyle\sigma_{1}:=\max_{j\in
C_{2}}\bigg{\|}\frac{1}{m_{1}}\sum_{s_{1}\in
C_{1}}\bm{A}_{s_{1}j}\bigg{\|}_{\mathrm{F}},\quad$
$\displaystyle\sigma_{2}:=\max_{i\in
C_{1}}\bigg{\|}\frac{1}{m_{2}}\sum_{s_{2}\in
C_{1}}\bm{A}_{is_{2}}\bigg{\|}_{\mathrm{F}},$
$\displaystyle\sigma:=\bigg{\|}\frac{1}{m_{1}m_{2}}\sum_{s_{1}\in
C_{1}}\sum_{s_{2}\in C_{2}}\bm{A}_{s_{1}s_{2}}\bigg{\|}_{\mathrm{F}},\quad$
$\displaystyle\sigma^{(i)}:=\bigg{\|}\frac{1}{m_{2}}\sum_{s_{2}\in
C_{2}}\bm{A}_{is_{2}}\bigg{\|}_{\mathrm{F}}.$

By applying Lemma A.3 with the approximation in (43) and the union bound, one
can see that with probability $1-n^{-c}$, $\sigma_{1}$, $\sigma_{2}$ and
$\sigma$ are bounded by

$\displaystyle\sigma_{1}\leq\sqrt{\frac{2(1+c)\beta
d}{\rho}}\bigg{(}\frac{\log
n}{n}\bigg{)},\quad\sigma_{2}\leq\sqrt{\frac{2(1+c)\beta
d}{(1-\rho)}}\bigg{(}\frac{\log n}{n}\bigg{)},$ (70)

and $\sigma=o(\log n/n)$. Then, the dual variable $\nu$ given in Lemma 3.9 is
bounded as

$\displaystyle\nu$ $\displaystyle\overset{(a)}{\leq}(1-\gamma)\max_{i\in
C_{2},j\in C_{1}}\bigg{(}\bigg{\|}\frac{1}{m_{1}}\sum_{s_{1}\in
C_{1}}\bm{A}_{is_{1}}\bigg{\|}_{\mathrm{F}}+\bigg{\|}\frac{1}{m_{2}}\sum_{s_{2}\in
C_{2}}\bm{A}_{s_{2}j}\bigg{\|}_{\mathrm{F}}+\bigg{\|}\frac{1}{m_{1}m_{2}}\sum_{s_{1}\in
C_{1}}\sum_{s_{2}\in C_{2}}\bm{A}_{s_{1}s_{2}}\bigg{\|}_{\mathrm{F}}\bigg{)}$
(71)
$\displaystyle\overset{(b)}{=}(1-\gamma)\left(\sigma_{1}+\sigma_{2}+\sigma\right)\leq(1-\gamma)\sqrt{2(1+c)\beta
d}\bigg{(}\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{)}\bigg{(}\frac{\log
n}{n}\bigg{)}+o\bigg{(}\frac{\log n}{n}\bigg{)}$

with probability $1-n^{-c}$, where $(a)$ holds by triangle inequality and
$(b)$ uses the fact $\bm{A}_{ij}=\bm{A}_{ji}^{\top}$. Similarly, we can bound
$\max_{j\in C_{2}}\|\bm{\Theta}_{ij}\|_{\mathrm{F}}$ in Lemma 3.9 for any
$i\in C_{1}$ as

$\displaystyle\max_{j\in C_{2}}\|\bm{\Theta}_{ij}\|_{\mathrm{F}}$
$\displaystyle\leq\gamma\bigg{(}\max_{j\in
C_{2}}\bigg{\|}\frac{1}{m_{1}}\sum_{s_{1}\in
C_{1}}\bm{A}_{s_{1}j}\bigg{\|}_{\mathrm{F}}\\!+\\!\bigg{\|}\frac{1}{m_{2}}\sum_{s_{2}\in
C_{2}}\bm{A}_{is_{2}}\bigg{\|}_{\mathrm{F}}\\!+\\!\bigg{\|}\frac{1}{m_{1}m_{2}}\sum_{s_{1}\in
C_{1}}\sum_{s_{2}\in C_{2}}\bm{A}_{s_{1}s_{2}}\bigg{\|}_{\mathrm{F}}\bigg{)}$
$\displaystyle=\gamma\left(\sigma_{1}+\sigma+\sigma^{(i)}\right).$

Therefore, $\mu_{i}+\nu$ given in Lemma 3.9 satisfies

$\displaystyle\mu_{i}+\nu$ $\displaystyle=\max\left\\{\max_{j\in
C_{2}}\|\bm{\Theta}_{ij}\|_{\mathrm{F}},\;\nu\right\\}\leq\max\bigg{\\{}\gamma\left(\sigma_{1}+\sigma+\sigma^{(i)}\right),\;(1-\gamma)\left(\sigma_{1}+\sigma_{2}+\sigma\right)\bigg{\\}}$
(72)
$\displaystyle\leq\max\left\\{\gamma\sigma_{1},\;(1-\gamma)(\sigma_{1}+\sigma_{2})\right\\}+\gamma\left(\sigma+\sigma^{(i)}\right).$

Now we are ready to bound $\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})$.
According to Lemma 3.9, by defining

$\epsilon_{1}:=\min_{i\in C_{1}}\bigg{[}\sum_{s\in
C_{1}}\left(r_{is}-\frac{\mu_{s}+\nu}{\sqrt{d}}\right)-\frac{m_{1}(\mu_{i}+\nu)}{\sqrt{d}}\bigg{]},\quad\epsilon_{2}:=\min_{i\in
C_{2}}\sum_{s\in C_{2}}r_{is}\\!-\\!\frac{2m_{2}\nu}{\sqrt{d}},$ (73)

we have
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})=\min\\{\epsilon_{1},\;\epsilon_{2}\\}+p$,
and we can bound $\epsilon_{1},\epsilon_{2}$ separately. To this end, let
$x_{i}:=\sum_{s:C(s)=C(i)}r_{is}$ and it follows a Binomial distribution such
that $x_{i}\sim\mathrm{Binom}(m_{1},p)$ when $i\in C_{1}$ and
$x_{i}\sim\mathrm{Binom}(m_{2},p)$ when $i\in C_{2}$. Then, by applying Lemma
A.1 and the union bound we obtain

$\displaystyle\mathbb{P}\left\\{\min_{i\in C_{1}}x_{i}\leq\tau_{1}\rho\log
n\right\\}=n^{1-\rho\left(\alpha-\tau_{1}\log(\frac{e\alpha}{\tau_{1}})+o(1)\right)},$
(74) $\displaystyle\mathbb{P}\left\\{\min_{i\in
C_{2}}x_{i}\leq\tau_{2}(1-\rho)\log
n\right\\}=n^{1-(1-\rho)\left(\alpha-\tau_{2}\log(\frac{e\alpha}{\tau_{2}})+o(1)\right)}.$
(75)

for $\tau_{1},\tau_{2}\in[0,\alpha)$ which satisfy the conditions in (28). For
$\epsilon_{1}$, we have

$\displaystyle\epsilon_{1}$ $\displaystyle\geq\underbrace{\min_{i\in
C_{1}}\sum_{s\in C_{1}}r_{is}}_{=:\epsilon_{11}}-\underbrace{\sum_{s\in
C_{1}}\frac{\mu_{s}+\nu}{\sqrt{d}}}_{=:\epsilon_{12}}-\underbrace{\frac{m_{1}}{\sqrt{d}}\max_{i\in
C_{1}}(\mu_{i}+\nu)}_{=:\epsilon_{13}}=\epsilon_{11}-\epsilon_{12}-\epsilon_{13}.$

Then we can bound $\epsilon_{11},\epsilon_{12}$ and $\epsilon_{13}$
separately. $\epsilon_{11}$ is bounded by (74). For $\epsilon_{12}$, by
definition,

$\displaystyle\epsilon_{12}$
$\displaystyle\overset{(a)}{\leq}\frac{1}{\sqrt{d}}\sum_{i\in
C_{1}}\max\left\\{\gamma\sigma_{1},\;(1-\gamma)(\sigma_{1}+\sigma_{2})\right\\}+\gamma\left(\sigma+\sigma^{(i)}\right)$
$\displaystyle=\frac{m_{1}}{\sqrt{d}}\left(\max\left\\{\gamma\sigma_{1},\;(1-\gamma)(\sigma_{1}+\sigma_{2})\right\\}+\gamma\sigma\right)+\frac{1}{\sqrt{d}}\sum_{i\in
C_{1}}\sigma^{(i)}$
$\displaystyle\overset{(b)}{\leq}\max\bigg{\\{}\frac{\gamma}{\sqrt{\rho}},\;(1-\gamma)\bigg{(}\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{)}\bigg{\\}}\cdot\rho\sqrt{2(1+c)\beta}\log
n+\frac{3\gamma c}{2}\log n+o(\log n)$

with probability $1-n^{-c}$, where $(a)$ uses the bound of $\mu_{s}+\nu$ in
(72), $(b)$ comes from (70) for bounding $\sigma_{1}$ and $\sigma_{2}$, and
$\frac{1}{\sqrt{d}}\sum_{i\in C_{1}}\sigma^{(i)}$ is bounded by Lemma A.5.
Similarly, $\epsilon_{13}$ can be bounded as

$\displaystyle\epsilon_{13}$ $\displaystyle=\frac{m_{1}}{\sqrt{d}}\max_{i\in
C_{1}}\left(\max\left\\{\gamma\sigma_{1},\;(1-\gamma)(\sigma_{1}+\sigma_{2})\right\\}+\gamma\left(\sigma+\sigma^{(i)}\right)\right)$
$\displaystyle\overset{(a)}{=}\frac{m_{1}}{\sqrt{d}}\left(\max\left\\{\gamma(\sigma_{1}+\sigma_{2}),\;(1-\gamma)(\sigma_{1}+\sigma_{2})\right\\}+\gamma\sigma\right)\overset{(b)}{=}\frac{m_{1}}{\sqrt{d}}\left(\gamma(\sigma_{1}+\sigma_{2})+\gamma\sigma\right)$
$\displaystyle\leq\gamma\rho\bigg{(}\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{)}\sqrt{2(1+c)\beta}\log
n+o(\log n)$

with probability $1-n^{-c}$, where $(a)$ comes from $\max_{i\in
C_{1}}\sigma^{(i)}=\sigma_{1}$ and $(b)$ holds since $\gamma\geq 1/2$ by
assumption. Combining these individual results and applying the union bound
yields

$\epsilon_{1}\geq\tau_{1}\rho\log
n-\rho\max\bigg{\\{}\frac{2\gamma}{\sqrt{\rho}}+\frac{\gamma}{\sqrt{1-\rho}},\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{\\}}\sqrt{2(1+c)\beta}\log
n\\!-\\!\frac{3\gamma c}{2}\log n\\!-\\!o(\log n)$

with probability $1-n^{-\Omega(1)}$. By further taking $c\rightarrow 0$ to be
close to zero we get

$\displaystyle\epsilon_{1}$ $\displaystyle\geq\tau_{1}\rho\log
n-\rho\max\bigg{\\{}\frac{2\gamma}{\sqrt{\rho}}+\frac{\gamma}{\sqrt{1-\rho}},\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{\\}}\sqrt{\ell\beta}\log
n-o(\log n),$

Similarly, by combining (75) with the bound of $\nu$ in (71) and let
$c\rightarrow 0$, we get the bound for $\epsilon_{2}$ as

$\epsilon_{2}\geq\tau_{2}(1-\rho)\log
n-2(1-\gamma)(1-\rho)\bigg{(}\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\bigg{)}\sqrt{\ell\beta}\log
n-o(\log n)$

with probability $1-n^{-\Omega(1)}$. Plugging these into
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})=\min\\{\epsilon_{1},\;\epsilon_{2}\\}+p$
completes the proof.

Specifically when $d=2$, $\sigma_{1},\sigma_{2}$ and $\sigma$ can be bounded
by Theorem A.4 instead of Theorem A.3. The remaining proof is same as above,
therefore we do not repeat. ∎

###  B.3 Two clusters with unknown cluster sizes

Now we consider the SDP proposed in (32). Note in this case, we use the
normalized ground truth $\bar{\bm{M}}^{*}$ defined in (31). The proof
basically follows Section 3.1.1, and we will omit repetitive analysis.

##### Step 1: Derive KKT conditions, uniqueness and optimality of
$\bm{M}^{*}$.

The KKT conditions of (32) when $\bm{M}=\bar{\bm{M}}^{*}$ are given as

$\displaystyle\bullet\;\textit{Stationarity:}$
$\displaystyle-\bm{A}-\bm{\Lambda}-\bm{I}_{n}\otimes\bm{Z}+\bm{\Theta}+\bm{\Theta}^{\top}=\bm{0},$
(76)
$\displaystyle\bm{\Theta}\\!=\\![\bm{\Theta}_{ij}]_{i,j=1}^{n},\quad\bm{\Theta}_{ij}\\!=\\!\begin{cases}\displaystyle\mu_{i}\bar{\bm{M}}_{ij}^{*}/\|\bar{\bm{M}}_{ij}^{*}\|_{\mathrm{F}},&\bar{\bm{M}}_{ij}^{*}\\!\neq\\!\bm{0},\\\
\mu_{i}\bm{\alpha}_{ij},\;\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\leq
1,&\bar{\bm{M}}_{ij}^{*}\\!=\\!\bm{0}.\end{cases}$ (77)
$\displaystyle\bullet\;\textit{Comp. slackness:}\quad$
$\displaystyle\left\langle\bm{\Lambda},\bar{\bm{M}}^{*}\right\rangle=0,\quad\bigg{\langle}\mu_{i},\sqrt{d}-\sum\limits_{j=1}^{n}\|\bar{\bm{M}}^{*}_{ij}\|_{\mathrm{F}}\bigg{\rangle}=0,\quad
i=1,\ldots,n.$ (78) $\displaystyle\bullet\;\textit{Dual feasibility:}$
$\displaystyle\bm{\Lambda}\succeq 0,\quad\mu_{i}\geq 0,\quad i=1,\ldots,n.$
(79)

Again, the following result establishes the uniqueness and optimality of
$\bar{\bm{M}}^{*}$:

######  Lemma B.1.

Given $\bar{\bm{M}}^{*}$ defined in (30), suppose there exist dual variables
$\bm{\Lambda}$, $\bm{Z}$, $\\{\mu_{i}\\}_{i=1}^{n}$, and
$\left\\{\bm{\alpha}_{ij}\right\\}_{(i,j):M^{*}_{ij}=\bm{0}}$ that satisfy the
KKT conditions (76) - (79) as well as

$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bar{\bm{M}}^{*}).$ (80)

Then $\bm{M}=\bar{\bm{M}}^{*}$ is the optimal and unique solution to (32).

##### Step 2: Construct dual variables.

Again, we follow the assumption in Section 3.1.1 that $\bm{R}_{i}=\bm{I}_{d}$
for each $i$ and $\bm{A}_{ij}=r_{ij}\bm{I}_{d}$ for any $j$ with $C(j)=C(i)$.
Then we have $\bar{\bm{M}}_{ij}^{*}=\bm{I}_{d}/m_{1}$ for $i,j\in C_{1}$ and
$\bar{\bm{M}}_{ij}^{*}=\bm{I}_{d}/m_{2}$ for $i,j\in C_{2}$. Also, let us
define

$\sigma_{i}:=\sum\limits_{s:C(s)=C(i)}r_{is},\quad\sigma^{(1)}:=\frac{1}{m_{1}}\sum\limits_{s_{1}\in
C_{1}}\sum\limits_{s_{2}\in
C_{1}}r_{s_{1}s_{2}},\quad\sigma^{(2)}:=\frac{1}{m_{2}}\sum\limits_{s_{1}\in
C_{2}}\sum\limits_{s_{2}\in C_{2}}r_{s_{1}s_{2}}.$

We make the following guess of dual variables, in particular, we adopt the
assumption of $\bm{\Theta}$ in Lemma 3.9.

######  Lemma B.2.

With a constant $\gamma\in[0,1]$, the dual variables with the following forms
satisfy the KKT conditions (76) - (78) and $\mu_{i}\geq 0,\;i=1,\ldots,n$ in
(79).

$\displaystyle\widetilde{\bm{\alpha}}_{ij}$
$\displaystyle=\frac{1}{m_{1}}\sum\limits_{s_{1}\in
C_{1}}\bm{A}_{s_{1}j}+\frac{1}{m_{2}}\sum\limits_{s_{2}\in
C_{2}}\bm{A}_{is_{2}}-\frac{1}{m_{1}m_{2}}\sum\limits_{s_{1}\in
C_{1}}\sum\limits_{s_{2}\in C_{2}}\bm{A}_{s_{1}s_{2}},\quad i\in C_{1},\;j\in
C_{2},$ $\displaystyle\bar{\mu}_{1}$ $\displaystyle=2\max_{i\in
C_{1}}\bigg{\\{}\frac{m_{1}\gamma}{\sqrt{d}}\max_{j\in
C_{2}}\|\widetilde{\bm{\alpha}}_{ij}\|_{\mathrm{F}}\\!-\\!\sigma_{i}\bigg{\\}}\\!-\\!\sigma^{(2)},\;\;\bar{\mu}_{2}=2\max_{i\in
C_{2}}\bigg{\\{}\frac{m_{2}(1\\!-\\!\gamma)}{\sqrt{d}}\max_{j\in
C_{2}}\|\widetilde{\bm{\alpha}}_{ji}\|_{\mathrm{F}}\\!-\\!\sigma_{i}\bigg{\\}}\\!-\\!\sigma^{(1)},$
$\displaystyle\mu_{i}$
$\displaystyle=\begin{cases}\displaystyle\frac{\sqrt{d}}{m_{1}}\bigg{(}\sigma_{i}+\frac{\sigma^{(2)}}{2}+\frac{\max\left\\{\bar{\mu}_{1},\bar{\mu}_{2}\right\\}}{2}\bigg{)},&\;i\in
C_{1},\\\
\displaystyle\frac{\sqrt{d}}{m_{2}}\bigg{(}\sigma_{i}+\frac{\sigma^{(1)}}{2}+\frac{\max\left\\{\bar{\mu}_{1},\bar{\mu}_{2}\right\\}}{2}\bigg{)},&\;i\in
C_{2}.\end{cases}\quad\bm{\Theta}_{ij}=\begin{cases}\mu_{i}\bm{I}_{d}/\sqrt{d},&C(i)=C(j),\\\
\gamma\widetilde{\bm{\alpha}}_{ij},&i\in C_{1},j\in C_{2},\\\
(1-\gamma)\widetilde{\bm{\alpha}}_{ji}^{\top},&i\in C_{2},j\in
C_{1},\end{cases}$ $\displaystyle\bm{Z}$
$\displaystyle=\left(\sigma^{(1)}+\sigma^{(2)}+\max\left\\{\bar{\mu}_{1},\bar{\mu}_{2}\right\\}\right)\bm{I}_{d},\quad\quad\bm{\Lambda}=-\bm{A}-\bm{I}_{n}\otimes\bm{Z}+\bm{\Theta}+\bm{\Theta}^{\top}.$

######  Lemma B.3.

Given the dual variables in Lemma B.2, $\bm{\Lambda}$ can be expressed as

$\bm{\Lambda}=(\bm{I}_{nd}-\bar{\bm{M}}^{*})(\mathbb{E}[\bm{A}]-\bm{A}+(p-\epsilon)\bm{I}_{nd})(\bm{I}_{nd}-\bar{\bm{M}}^{*}),\quad\epsilon:=\sigma^{(1)}+\sigma^{(2)}+\max\left\\{\bar{\mu}_{1},\bar{\mu}_{2}\right\\}$

Then, $\bm{\Lambda}\succeq 0$ and
$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bar{\bm{M}}^{*})$ are satisfied if
$\widetilde{\bm{\Lambda}}\succ 0$.

##### Step 3: Find the condition for $\widetilde{\bm{\Lambda}}\succ 0$.

Again, by using the same argument as in Section 3.1.1 we get, for exact
recovery it suffices to ensure
$\lambda_{\text{min}}((p-\epsilon)\bm{I}_{nd})>\|\mathbb{E}[\bm{A}]-\bm{\bm{A}}\|$.
To this end, we have the following bound for
$\lambda_{\text{min}}((p-\epsilon)\bm{I}_{nd})$.

######  Lemma B.4.

Let $p=\alpha\log n/n,q=\beta\log n/n$ and
$\delta:=\left(\frac{1}{\sqrt{\rho}}+\frac{1}{\sqrt{1-\rho}}\right)\sqrt{\ell\beta}$,
where $\ell=2$ for $d>2$ and $\ell=1$ for $d=2$. Then
$\lambda_{\text{min}}((p-\epsilon)\bm{I}_{nd})$ satisfies

$\lambda_{\text{min}}((p-\epsilon)\bm{I}_{nd})\geq\min\\{\rho(2\tau_{1}-\alpha-2\gamma\delta),\;(1-\rho)(2\tau_{2}-\alpha-2(1-\gamma)\delta\\}\log
n+o(\log n)$

with probability $1-n^{-\Omega(1)}$ for $\tau_{1},\tau_{2}\in[0,\alpha)$ such
that

$\displaystyle
1-\rho\bigg{(}\alpha-\tau_{1}\log\bigg{(}\frac{e\alpha}{\tau_{1}}\bigg{)}\bigg{)}<0,\quad
1-(1-\rho)\bigg{(}\alpha-\tau_{2}\log\bigg{(}\frac{e\alpha}{\tau_{2}}\bigg{)}\bigg{)}<0.$
(81)

###### Proof of Theorem 3.12.

From Lemma B.4 we have $\lambda_{\text{min}}((p-\epsilon)\bm{I}_{nd})=O(\log
n)$ with high probability. Also from Lemma 3.6 we get
$\|\mathbb{E}[\bm{\bm{A}}]-\bm{A}\|=o(\sqrt{\log n})$ with high probability.
This implies as $n$ is large,
$\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})>\|\mathbb{E}[\bm{\bm{A}}]-\bm{A}\|$
satisfies as long as $\lambda_{\text{min}}(p\bm{I}_{nd}-\bm{Z})=\Omega(\log
n)$, which is equivalent to

$\min\\{\rho(2\tau_{1}-\alpha-2\gamma\delta),\;(1-\rho)(2\tau_{2}-\alpha-2(1-\gamma)\delta\\}>0.$
(82)

This further reduces to $\tau_{1}>\alpha/2+\gamma\delta$ and
$\tau_{2}>\alpha/2+(1-\gamma)\delta$. It remains to check (81) holds for some
$\tau_{1},\tau_{2}\in[0,\alpha)$. To this end, by using the same argument as
in the proof of Theorem 3.7, one can see that (81) holds as long as
$\tau_{1}<\tau_{1}^{*},\;\tau_{2}<\tau_{2}^{*}$ with
$\tau_{1}^{*},\tau_{2}^{*}$ defined in (20) (Notice that
$\tau_{1}^{*},\tau_{2}^{*}$ exist only if
$\alpha>\max\left\\{1/\rho,\;1/(1-\rho)\right\\}$). Therefore, putting all
these together the condition for exact recovery becomes

$\alpha>\max\left\\{\frac{1}{\rho},\;\frac{1}{1-\rho}\right\\},\quad\frac{\alpha}{2}+\gamma\delta<\tau_{1}<\tau_{1}^{*}\quad\text{and}\quad\frac{\alpha}{2}+(1-\gamma)\delta<\tau_{2}<\tau_{2}^{*}.$
(83)

Furthermore, since $\gamma\in[0,1]$ is not specified, it suffices to ensure
(83) holds for some $\gamma\in[0,1]$ such that the range of $\tau_{1}$ and
$\tau_{2}$ is valid. This leads to the conditions in (33). ∎

####  B.3.1 Proof of the lemmas

###### Proof of Lemma B.1.

The optimality of $\bar{\bm{M}}^{*}$ is immediately obtained since (32) is
convex then KKT conditions are sufficient for $\bar{\bm{M}}^{*}$ being optimal
[8]. For uniqueness, suppose $\widetilde{\bm{M}}\neq\bar{\bm{M}}^{*}$ is
another optimal solution. Similar to (54) in Section B.1, we have

$\displaystyle 0=\langle\bm{A},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle$
$\displaystyle=-\langle\bm{\Lambda},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle-\langle\bm{I}_{n}\otimes\bm{Z},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle+\langle\bm{\Theta}+\bm{\Theta}^{\top},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle$
$\displaystyle\overset{(a)}{=}-\langle\bm{\Lambda},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle+\langle\bm{\Theta}+\bm{\Theta}^{\top},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle$
$\displaystyle=-\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle+2\langle\bm{\Theta},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle$
(84)

where $(a)$ comes from $\sum_{i=1}^{n}\bm{M}_{ii}=2\bm{I}_{d}$ in (32). To
proceed, let us rewrite

$\displaystyle\langle\bm{\Theta},\widetilde{\bm{M}}-\bar{\bm{M}}^{*}\rangle$
$\displaystyle=\langle\bm{\Theta},\widetilde{\bm{M}}\rangle-\langle\bm{\Theta},\bar{\bm{M}}^{*}\rangle=\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\widetilde{\bm{M}}_{ij}\rangle-\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\bar{\bm{M}}_{ij}^{*}\rangle.$
(85)

Furthermore, by plugging (77) into (85) we obtain

$\displaystyle\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\bar{\bm{M}}_{ij}^{*}\rangle$
$\displaystyle=\sum\limits_{i}\sum\limits_{j:C(j)=C(i)}\frac{\mu_{i}}{\|\bar{\bm{M}}_{ij}^{*}\|_{\mathrm{F}}}\langle\bar{\bm{M}}_{ij}^{*},\bar{\bm{M}}_{ij}^{*}\rangle=\sum\limits_{i}\mu_{i}\sqrt{d},$
(86)
$\displaystyle\sum\limits_{i,j}\langle\bm{\Theta}_{ij},\widetilde{\bm{M}}_{ij}\rangle$
$\displaystyle=\sum\limits_{i}\mu_{i}\bigg{(}\sum\limits_{j:C(j)=C(i)}\frac{1}{\|\bar{\bm{M}}_{ij}^{*}\|_{\mathrm{F}}}\langle\bar{\bm{M}}_{ij}^{*},\widetilde{\bm{M}}_{ij}\rangle+\sum\limits_{j:C(j)\neq
C(i)}\langle\bm{\alpha}_{ij},\widetilde{\bm{M}}_{ij}\rangle\bigg{)}$
$\displaystyle\leq\sum\limits_{i}\mu_{i}\bigg{(}\sum\limits_{j:C(j)=C(i)}\frac{1}{\|\bar{\bm{M}}_{ij}^{*}\|_{\mathrm{F}}}\|\bar{\bm{M}}_{ij}^{*}\|_{\mathrm{F}}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}+\sum\limits_{j:C(j)\neq
C(i)}\|\bm{\alpha}_{ij}\|_{\mathrm{F}}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\bigg{)}$
$\displaystyle\leq\sum\limits_{i}\mu_{i}\sum\limits_{j}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\overset{(a)}{\leq}\sum\limits_{i}\mu_{i}\sqrt{d},$

where $(a)$ holds since
$\sum_{j}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\leq\sqrt{d}$ in (32). Then
combining (85) and (86) results in
$\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}\rangle\leq 0$, and plugging
this back into (84) gives $\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle\leq
0$. On the other hand, from $\bm{\Lambda}\succeq 0$ in (79) and
$\widetilde{\bm{M}}\succeq 0$ in (32) we have
$\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle\geq 0$. Therefore we conclude
$\langle\bm{\Lambda},\widetilde{\bm{M}}\rangle=0$ and
$\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}\rangle=0$. To proceed, by
$\mathcal{N}(\bm{\Lambda})=\mathcal{R}(\bar{\bm{M}}^{*})$ and the definition
of $\bar{\bm{M}}^{*}$ in (31), $\widetilde{\bm{M}}$ has the following form:

$\widetilde{\bm{M}}=\bm{V}^{(1)}\bm{\Sigma}_{1}(\bm{V}^{(1)})^{\top}+\bm{V}^{(2)}\bm{\Sigma}_{2}(\bm{V}^{(2)})^{\top},$
(87)

for some diagonal $\bm{\Sigma}_{1},\bm{\Sigma}_{2}\succeq 0$. Now it remains
to show $\bm{\Sigma}_{1}=\bm{I}_{d}/m_{1},\;\bm{\Sigma}_{2}=\bm{I}_{d}/m_{2}$.
To this end, from $\langle\bm{\Theta},\widetilde{\bm{M}}-\bm{M}^{*}\rangle=0$
we see $(a)$ in (86) holds with equality, i.e.
$\sum_{j=1}^{n}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}=\sqrt{d},\;\forall i$.
Then combining this with (87) yields the following for $i\in C_{1}$:

$\sum\limits_{j=1}^{n}\|\widetilde{\bm{M}}_{ij}\|_{\mathrm{F}}\overset{(a)}{=}\sum\limits_{j=1}^{n}\|\bm{R}_{i}\bm{\Sigma}_{1}\bm{R}_{j}^{\top}\|_{\mathrm{F}}\overset{(b)}{=}m_{1}\|\bm{\Sigma}_{1}\|_{\mathrm{F}}=\sqrt{d},\;\forall
i\in
C_{1}\quad\Rightarrow\quad\|\bm{\Sigma}_{1}\|_{\mathrm{F}}=\sqrt{d}/m_{1},$

where both $(a)$ and $(b)$ follow from (87). Similarly for $i\in C_{2}$ we can
obtain $\|\bm{\Sigma}_{2}\|_{\mathrm{F}}=\sqrt{d}/m_{2}$. Next, note for each
diagonal block of $\widetilde{\bm{M}}$ it satisfies

$\displaystyle\bigg{\|}\sum\limits_{i=1}^{n}\widetilde{\bm{M}}_{ii}\bigg{\|}_{\mathrm{F}}$
$\displaystyle\overset{(a)}{=}\bigg{\|}\sum\limits_{i\in
C_{1}}\bm{R}_{i}\bm{\Sigma}_{1}\bm{R}_{i}^{\top}\\!+\\!\sum\limits_{i\in
C_{2}}\bm{R}_{i}\bm{\Sigma}_{2}\bm{R}_{i}^{\top}\bigg{\|}_{\mathrm{F}}\\!\overset{(b)}{\leq}\\!\sum\limits_{i\in
C_{1}}\left\|\bm{R}_{i}\bm{\Sigma}_{1}\bm{R}_{i}^{\top}\right\|_{\mathrm{F}}\\!+\\!\sum\limits_{i\in
C_{2}}\left\|\bm{R}_{i}\bm{\Sigma}_{2}\bm{R}_{i}^{\top}\right\|_{\mathrm{F}}$
$\displaystyle\overset{(c)}{=}2\sqrt{d}\overset{(d)}{=}\bigg{\|}\sum\limits_{i=1}^{n}\widetilde{\bm{M}}_{ii}\bigg{\|}_{\mathrm{F}},$

where $(a)$ follows from (87); $(b)$ comes from triangle inequality; $(c)$
holds because $\|\bm{\Sigma}_{1}\|_{\mathrm{F}}=\sqrt{d}/m_{1}$ and
$\|\bm{\Sigma}_{1}\|_{\mathrm{F}}=\sqrt{d}/m_{2}$; $(d)$ follows from
$\sum_{i=1}^{n}\bm{M}_{ii}=2\bm{I}_{d}$ in (32). This implies $(b)$ holds with
equality, and further
$\bm{R}_{i}\bm{\Sigma}_{1}\bm{R}_{i}^{\top}=\bm{I}_{d}/m_{1},\;\forall i\in
C_{1}$ and
$\bm{R}_{i}\bm{\Sigma}_{2}\bm{R}_{i}^{\top}=\bm{I}_{d}/m_{2},\;\forall i\in
C_{2}$. It follows $\bm{\Sigma}_{1}=\bm{I}_{d}/m_{1}$ and
$\bm{\Sigma}_{2}=\bm{I}_{d}/m_{2}$, which indicates
$\widetilde{\bm{M}}=\bar{\bm{M}}^{*}$. ∎

###### Proof of Lemma B.2.

First, from (76) we get
$\bm{\Lambda}=-\bm{A}-\bm{I}_{n}\otimes\bm{Z}+\bm{\Theta}+\bm{\Theta}^{\top}$,
plugging this into (80) yields

$\displaystyle\sum\limits_{s:C(s)=C(i)}\left(\frac{\mu_{i}\bm{I}_{d}}{\sqrt{d}}+\frac{\mu_{s}\bm{I}_{d}}{\sqrt{d}}-\bm{A}_{is}\right)=\bm{Z},\quad$
$\displaystyle i=1,\ldots,n,$ (88) $\displaystyle\sum\limits_{s:C(s)\neq
C(i)}\left(\bm{\Theta}_{is}+\bm{\Theta}_{si}^{\top}-\bm{A}_{is}\right)=\bm{0},\quad$
$\displaystyle i=1,\ldots,n.$ (89)

Then, by summing (88) over $i\in C_{1}$ and $i\in C_{2}$ separately we get the
expression of $\bm{Z}$ as

$\displaystyle\bm{Z}=\bigg{(}\frac{2}{\sqrt{d}}\sum\limits_{s\in
C_{1}}\mu_{s}-\sigma^{(1)}\bigg{)}\bm{I}_{d}=\bigg{(}\frac{2}{\sqrt{d}}\sum\limits_{s\in
C_{2}}\mu_{s}-\sigma^{(2)}\bigg{)}\bm{I}_{d},$ (90)

Next, plugging (90) back into (88) yields expressions of $\mu_{i}$ as

$\displaystyle\mu_{i}$
$\displaystyle=\frac{\sqrt{d}}{m_{1}}\sigma_{i}+\underbrace{\bigg{(}\frac{1}{m_{1}}\sum\limits_{s\in
C_{1}}\mu_{s}-\frac{\sqrt{d}}{m_{1}}\sigma^{(1)}\bigg{)}}_{=:\bar{\mu}_{1}}=\frac{\sqrt{d}}{m_{1}}\sigma_{i}+\bar{\mu}_{1},\quad
i\in C_{1},$ (91) $\displaystyle\mu_{i}$
$\displaystyle=\frac{\sqrt{d}}{m_{2}}\sigma_{i}+\underbrace{\bigg{(}\frac{1}{m_{2}}\sum\limits_{s\in
C_{2}}\mu_{s}-\frac{\sqrt{d}}{m_{2}}\sigma^{(2)}\bigg{)}}_{=:\bar{\mu}_{2}}=\frac{\sqrt{d}}{m_{2}}\sigma_{i}+\bar{\mu}_{2},\quad
i\in C_{2}.$

Then plugging (91) into (90) yields

$\bm{Z}=\bigg{(}\sigma^{(1)}+\frac{2m_{1}}{\sqrt{d}}\bar{\mu}_{1}\bigg{)}\bm{I}_{d}=\bigg{(}\sigma^{(2)}+\frac{2m_{2}}{\sqrt{d}}\bar{\mu}_{2}\bigg{)}\bm{I}_{d}.$
(92)

Importantly, to make the LHS and RHS above identical, $\bar{\mu}_{1}$ and
$\bar{\mu}_{2}$ satisfy

$\bar{\mu}_{1}=\frac{\sqrt{d}}{2m_{1}}(\sigma^{(2)}+\bar{\mu}),\quad\bar{\mu}_{2}=\frac{\sqrt{d}}{2m_{2}}(\sigma^{(1)}+\bar{\mu})$
(93)

for some $\bar{\mu}$. Plugging (93) into (91) and (90) yields the expressions
of $\bm{Z}$ and $\mu_{i}$ in terms of $\bar{\mu}$, and we restrict
$\gamma\in[0,1]$ which ensures $\mu_{i}\geq 0$. To determine $\bar{\mu}$, we
adopt the guess of $\bm{\Theta}_{ij}$ and $\widetilde{\bm{\alpha}}_{ij}$ in
Lemma 3.9. From (77) we have
$\|\bm{\Theta}_{ij}\|_{\mathrm{F}}=\mu_{i}\|\bm{\alpha}_{ij}\|_{\mathrm{F}}$