# The Power of Two Matrices in Spectral Algorithms

Souvik Dhara⋆, Julia Gaudio†, Elchanan Mossel‡, Colin Sandon∣ Division of
Applied Mathematics, Brown University  Department of Industrial Engineering
and Management Sciences, Northwestern University  Department of Mathematics,
Massachusetts Institute of Technology  Department of Mathematics, École
Polytechnique Fédérale de Lausanne<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Spectral algorithms are some of the main tools in optimization and inference
problems on graphs. Typically, the graph is encoded as a matrix and
eigenvectors and eigenvalues of the matrix are then used to solve the given
graph problem. Spectral algorithms have been successfully used for graph
partitioning, hidden clique recovery and graph coloring. In this paper, we
study the power of spectral algorithms using two matrices in a graph
partitioning problem. We use two different matrices resulting from two
different encodings of the same graph and then combine the spectral
information coming from these two matrices.

We analyze a two-matrix spectral algorithm for the problem of identifying
latent community structure in large random graphs. In particular, we consider
the problem of recovering community assignments _exactly_ in the censored
stochastic block model, where each edge status is revealed independently with
some probability. We show that spectral algorithms based on two matrices are
optimal and succeed in recovering communities up to the information theoretic
threshold. On the other hand, we show that for most choices of the parameters,
any spectral algorithm based on one matrix is suboptimal. This is in contrast
to our prior works (2022a, 2022b) which showed that for the symmetric
Stochastic Block Model and the Planted Dense Subgraph problem, a spectral
algorithm based on one matrix achieves the information theoretic threshold. We
additionally provide more general geometric conditions for the
(sub)-optimality of spectral algorithms.

_Acknowledgement:_ S.D., E.M and C.S. were partially supported by Vannevar
Bush Faculty Fellowship ONR-N00014-20-1-2826. S.D. was supported by Simons-
Berkeley Research Fellowship and Vannevar Bush Faculty Fellowship
ONR-N0014-21-1-2887. E.M. and C.S. were partially supported by NSF award
DMS-1737944. E.M. was partially supported by Simons Investigator award
(622132) and by ARO MURI W911NF1910217. J.G. was partially supported by NSF
award CCF-2154100. Part of this work was completed while S.D. and C.S. were at
the MIT Mathematics Department, and also while S.D. was at The Simons
Institute for the Theory of Computing.

##  1\. Introduction

Spectral algorithms are some of the main tools in graph algorithms and
combinatorial optimization. Some famous and classical examples include
spectral algorithms for the hidden clique problem [4], graph bisection [6],
and graph coloring [3, 5]. These algorithms encode the graph into a matrix by
recording the status of each present/absent edge of the graph as an entry of
the matrix. The most natural encoding is the adjacency matrix representation,
where edges are encoded by the value $1$ and non-edges are encoded by the
value $0$. Given the encoding matrix, a small number of eigenvectors for this
matrix are used to solve the given graph problem.

> Our interest in this work lies in graph problems for which using multiple
> matrix representations gives an advantage over using a single matrix.

In particular, we are interested in the power of spectral algorithms in such a
scenario in the context of finding clusters in a planted partition model
called the Censored Stochastic Block Model (CSBM). In this model, there are
two clusters of approximate sizes $n\rho$ and $n(1-\rho)$, and the edges
inside each of the clusters appear independently with probabilities
$p_{1},p_{2}$ respectively, while edges between the two clusters appear with
probability $q$. Moreover, each edge status is revealed with probability
$t\log n/n$ for some fixed $t>0$. Thus the statuses of most edges are unknown.
The censored model was introduced to model the fact that in many social
networks, not all of the connections between individual nodes are known.

Given an instance of a censored graph with no vertex labels, the problem is to
recover the partitions _exactly_ with high probability. This is often referred
to as the _exact recovery problem_. We note that some applications of spectral
algorithms to the exact recovery problem use an additional combinatorial
clean-up stage (see e.g. [7, 16, 17]), but we follow [1, 9, 8] in studying
spectral algorithms that do not look at the graph after the top eigenvectors
have been found. This is partially motivated by the fact that most real
applications of spectral algorithms do not include a combinatorial clean-up
stage.

The classical case in the literature considers exact recovery in the
Stochastic Block Model where there is no censoring and
$p_{1},p_{2},q=\Theta(\log n/n)$. In order to achieve exact recovery up to the
information theoretic boundary, prior works used some trimming and post-
processing steps together with the spectral algorithm [7, 16, 17]. However,
the question of whether a direct spectral algorithm based on the top two
eigenvectors of the of the adjacency matrix would be optimal remained open
until the recent resolution by Abbe, Fan, Wang, and Zhong [1] for
$p_{1}=p_{2}$. In the _censored_ SBM, there are three possible observations
(present, absent, or censored), so spectral recovery using a binary-valued
adjacency matrix is suboptimal. Instead, one can use a ternary-valued encoding
matrix. It was recently shown in [9, 8] that, for some special cases of the
planted partition model such as the planted dense subgraph problem $(p_{2}=q)$
and the symmetric stochastic block model ($p_{1}=p_{2},\rho=1/2$), a spectral
algorithm based on the top two eigenvectors of a signed adjacency matrix is
optimal. This raises the question:

> _Are spectral algorithms based on the top eigenvectors of a signed adjacency
> matrix optimal for all censored stochastic block models?_

The main contributions of this article are as follows:

  1. (1)

In contrast with the success stories in [9, 8], whenever $p_{1},p_{2},q$ are
distinct, a spectral algorithm based on the top two eigenvectors of a signed
adjacency matrix is always suboptimal (Theorem 1.7 Part 2).

  2. (2)

We propose spectral algorithms with two encoding matrices, where we take an
appropriate linear combination of the corresponding top eigenvectors. We show
that these algorithms are always optimal (Theorem 1.10). The optimality of
spectral algorithms with two matrices is also shown in the more general
setting $k\geq 2$ communities (Theorem 1.12).

Thus, these results exhibit a strict separation between spectral algorithm
classes with one versus multiple encoding matrices, and this separation can be
realized for even elementary planted partition models. To our knowledge, this
general phenomena was not observed in the substantial prior literature for
recovery problems in the planted partition problems.

###  1.1. Model and Objective.

We start by defining the Censored Stochastic Block Model.

######  Definition 1.1 (Censored Stochastic Block Model (CSBM)).

Let $\rho\in(0,1)^{k}$ be such that $\sum_{i=1}^{k}\rho_{i}=1$ and let
$P\in(0,1)^{k\times k}$ be a symmetric matrix. Suppose we have $n$ vertices
and each vertex $v\in[n]$ is assigned a community assignment
$\sigma_{0}(v)\in[k]$ according to the distribution $\rho$ independently,
i.e., $\mathbb{P}(\sigma_{0}(v)=i)=\rho_{i}$ for $i\in[k]$.

  * $\triangleright$

For $u,v\in[n]$ and $u\neq v$, the edge $\\{u,v\\}$ exists independently with
probability $P_{\sigma_{0}(u)\sigma_{0}(v)}$. Self-loops do not occur.

  * $\triangleright$

For every pair of vertices $\\{u,v\\}$, its connectivity status is revealed
independently with probability $\frac{t\log n}{n}$, and is censored otherwise
for some fixed $t>0$.

The output is a random graph with edge statuses given by
$\\{\texttt{present},\texttt{absent},\texttt{censored}\\}$. The distribution
of this random graph is called the Censored Stochastic Block Model. We write
$G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$ to denote a graph generated from the
above model, with vertex labels removed (i.e., $\sigma_{0}$ unknown).

######  Definition 1.2 (Exact recovery).

Consider the $n\times k$ membership matrix $S_{0}$, where
$(S_{0})_{ui}=\mathbbm{1}\\{\sigma_{0}(u)=i\\}$, i.e., the $u$-th row
indicates the community membership of $u$. Given an estimator $\hat{\sigma}$,
construct $\hat{S}$ similarly as
$\hat{S}_{ui}=\mathbbm{1}\\{\hat{\sigma}(u)=i\\}$. We say that an estimator
achieves _exact recovery_ if there exists a $k\times k$ permutation matrix $J$
such that $\hat{S}J=S_{0}$.

###  1.2. Information theoretic boundary.

We start by discussing the information theoretic threshold. The result will be
stated in terms of a Chernoff–Hellinger divergence, introduced by Abbe and
Sandon [2].

######  Definition 1.3 (Chernoff–Hellinger divergence).

Given two vectors $\mu,\nu\in(\mathbb{R}_{+}\setminus\\{0\\})^{l}$, define

$\mathrm{CH}_{\xi}(\mu,\nu)=\sum_{i\in[l]}\big{[}\xi\mu_{i}+(1-\xi)\nu_{i}-\mu_{i}^{\xi}\nu_{i}^{1-\xi}\big{]}\quad\text{
for }\xi\in[0,1].$

The Chernoff–Hellinger divergence of $\mu$ and $\nu$ is defined as

$\begin{split}\Delta_{+}(\mu,\nu)=\max_{\xi\in[0,1]}\mathrm{CH}_{\xi}(\mu,\nu).\end{split}$
(1.1)

Define

$\begin{split}t_{c}:=\Big{(}\min_{i\neq
j}\Delta_{+}(\theta_{i},\theta_{j})\Big{)}^{-1},\quad\text{where
}\theta_{i}=(\rho_{r}P_{ri},\rho_{r}(1-P_{ri}))_{r\in[k]}\in\mathbb{R}^{2k}.\end{split}$
(1.2)

######  Theorem 1.4 (Information theoretic threshold).

Let $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$. If $t<t_{c}$, then for any
estimator $\hat{\sigma}$,

$\displaystyle\lim_{n\to\infty}\mathbb{P}(\hat{\sigma}\text{ achieves exact
recovery})=0.$

###  1.3. Spectral algorithms.

For comparing the performance of spectral algorithms with one matrix versus
spectral algorithms with more than one matrix, we first specialize to the case
of two communities.

To define spectral algorithms formally, we first define the threshold
procedures we allow to apply on vectors. These are the procedures that will be
applied to the leading eigenvectors of the encoding matrices.

Algorithm 1 Classify

1:Censored graph $G$ on $n$ vertices, vectors
$(u_{i})_{i=1}^{m}\subset\mathbb{R}^{n}$, and scalars,
$\gamma_{1},\dots,\gamma_{m},T\in\mathbb{R}$.

2:Community classification.

3:Compute possible score vectors
$U=\\{\sum_{i=1}^{m}s_{i}\gamma_{i}u_{i}\text{ for all }s_{i}\in\\{\pm
1\\}\\}.$

4:Compute possible assignments
$\hat{S}(U)=\\{\hat{\sigma}=\mathrm{sign}(u-T1):u\in U\\}$ and output a
community assignment $1+(1+\hat{\sigma})/2$ that maximizes the posterior
probability $\mathbb{P}(G\mid\hat{\sigma})$ over $\hat{\sigma}\in\hat{S}(U)$.

Since eigenvectors are determined up to a sign flip, Step 2 above is required
in order to resolve this sign ambiguity. This will be explained in more detail
in Remark 1.13.

######  Definition 1.5 (Signed adjacency matrix).

Given $y>0$ and a graph $G$ with edge statuses
$\\{\texttt{present},\texttt{absent},\texttt{censored}\\}$, define the signed
adjacency matrix $A(G,y)$ as the $n\times n$ matrix with

$\displaystyle A_{ij}$ $\displaystyle=\begin{cases}1&\text{if }\\{i,j\\}\text{
is present}\\\ -y&\text{if }\\{i,j\\}\text{ is absent}\\\ 0&\text{if
}\\{i,j\\}\text{ is censored}.\end{cases}$

Let us define the class of algorithms Spectral-One that use a single encoding
matrix.

######  Definition 1.6 (Spectral-One).

An algorithm $\mathcal{A}(G,y,a_{1},a_{2},T)$ in the Spectral-One class takes
a censored graph $G$ as input, an encoding parameter $y\in\mathbb{R}_{+}$, and
scalars $a_{1},a_{2},T\in\mathbb{R}$. The algorithm then computes the top two
eigenvectors $u_{1},u_{2}$ of $A=A(G,y)$, and gives the output of
$\textsc{Classify}((u_{i})_{i=1}^{2},(a_{i})_{i=1}^{2},T)$. We denote the
output of algorithm $\mathcal{A}$ in this class as
$\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}$.

For the two community case, we will always consider the parameters:

$P=\begin{pmatrix}p_{1}&q\\\
q&p_{2}\end{pmatrix}\quad\bar{\rho}=(\rho,1-\rho)\quad\text{and}\quad\rho,p_{1},p_{2},q\in(0,1).$
(1.3)

######  Theorem 1.7 (Failure of Spectral-One in most cases).

Let $G\sim\textsc{CSBM}_{n}^{2}(\bar{\rho},P,t)$ with $\bar{\rho},P$ given by
(1.3).

  1. (1)

Suppose that $p_{1},p_{2},q$ are not distinct. If $p_{1}=p_{2}=p$, then assume
$p+q\neq 1$. 111The case $p_{1}=p_{2}=p$, $\rho=\frac{1}{2}$ is covered in [9]
without the assumption $p+q\neq 1$. In this case, spectral algorithms succeed
for $t>t_{c}$. There exist explicitly computable constants
$y\in\mathbb{R}_{+}$ and $\gamma_{1},\gamma_{2}\in\mathbb{R}$ such that the
algorithm $\mathcal{A}=\mathcal{A}(G,y,\gamma_{1},\gamma_{2},0)$ from the
class Spectral-One satisfies

$\lim_{n\to\infty}\mathbb{P}(\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}\text{
achieves exact recovery})=1,\quad\text{ for any }t>t_{c}.$

In particular, Algorithm 5.1 produces such an estimator.

  2. (2)

Suppose that $p_{1},p_{2},q$ are distinct. There exists $\delta_{0}>0$ such
that, if $t<t_{c}+\delta_{0}$, then for any $\mathcal{A}\in\textsc{Spectral-
One}$,

$\lim_{n\to\infty}\mathbb{P}(\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}\text{
achieves exact recovery})=0.$

For the case $p_{1}=p_{2}$, Theorem 1.7 Part 1 generalizes the result of [9,
Theorem 2.2] to the case $\rho\neq 1/2$. Part 2 of the result is in sharp
contrast with the results in [9, 8]; together, these results essentially say
that the censored planted dense subgraph problem ($p_{2}=q$) and the symmetric
censored stochastic block models ($p_{1}=p_{2}$) are remarkably the only cases
where an algorithm from Spectral-One is successful222For the edge-case
$p_{1}=p_{2}=p$ and $p+q=1$, the rank of $\mathbb{E}[A]$ is 1 for the value of
$y$ that we would want to use. This is why it is ruled out in Theorem 1.7 Part
1. . The possible limitation of Spectral-One was shown in [8, Theorem 2.6] for
the special case of $q=1/2$, $p_{1}=1-p_{2}$ and $\rho=1/2$.

######  Remark 1.8.

It is worthwhile to note that the choice of encoding parameters $\\{1,-y,0\\}$
is completely general and one does not get a more powerful class of algorithms
by allowing an arbitrary ternary encoding. In fact, as our proof shows, if
$p_{1},p_{2},q$ are distinct, then even if one allows arbitrary encodings, the
Spectral-One algorithms still fail sufficiently near the threshold (see Remark
5.2).

Next, we will show that spectral algorithms with two matrices are always
optimal for the recovery of two communities. Let us define the class of
algorithms Spectral-Two that uses two encoding matrices instead of one.

######  Definition 1.9 (Spectral-Two).

An algorithm $\mathcal{A}(G,y_{1},y_{2},(a_{i})_{i=1}^{4},T)$ in the Spectral-
Two class takes as input a censored graph $G$, two encoding parameter
$y_{1},y_{2}\in\mathbb{R}_{+}$ with $y_{1}\neq y_{2}$ and
$(a_{i})_{i=1}^{4}\subset\mathbb{R}$, $T\in\mathbb{R}$. The algorithm
considers two signed adjacency matrices $A_{1}=A(G,y_{1})$ and
$A_{2}=A(G,y_{2})$, and computes their top two eigenvectors
$u_{1}^{r},u_{2}^{r}$, for $r=1,2$. Then the algorithm outputs
$\textsc{Classify}((u_{i}^{r})_{i,r=1,2},(a_{i})_{i=1}^{4},T)$. As before, we
denote the output of algorithm $\mathcal{A}$ from this class as
$\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}$.

######  Theorem 1.10 (Spectral-Two always succeeds in recovering two
communities).

Let $G\sim\textsc{CSBM}_{n}^{2}(\bar{\rho},P,t)$ with $\bar{\rho},P$ given by
(1.3). There exists a set $\mathcal{Y}\subset\mathbb{R}_{+}$ with
$|\mathcal{Y}|\leq 3$ such that for any $y_{1}\neq y_{2}$ and
$y_{1},y_{2}\notin\mathcal{Y}$, there exist explicit
$(a_{i})_{i=1}^{4}\subset\mathbb{R}^{4}$ such that the algorithm
$\mathcal{A}(G,y_{1},y_{2},(a_{i})_{i=1}^{4},0)$ from the class Spectral-Two
satisfies

$\lim_{n\to\infty}\mathbb{P}(\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}\text{
achieves exact recovery})=1,\quad\text{ for any }t>t_{c}.$

In particular, Algorithm 5.2 produces such an estimator.

Theorem 1.10 not only shows that Spectral-Two algorithms are always
successful, but also shows that the choice of the encoding parameters
$y_{1},y_{2}$ does not matter too much as long as $y_{1}\neq y_{2}$ and they
both lie outside a finite exception set. For example, we can choose
$y_{1},y_{2}\sim\text{Uniform}[0,1]$ independently. Avoiding the finite
exception set helps us ensure that $A_{1}$ and $A_{2}$ both have two
eigenvectors with large, distinct eigenvalues. On the other hand, in Theorem
1.7 1 for Spectral-One algorithms, the choice of the encoding is quite
important. In fact, for $p_{1}=p_{2}=p$ or $p_{1}=p$ and $p_{2}=q$, the only
choice of $y$ that yields an optimal algorithm is
$\log(\frac{1-q}{1-p})/\log\frac{p}{q}$. Thus, Spectral-Two algorithms leads
to a much broader and flexible class of algorithms as compared to Spectral-
One.

Finally, we show that Spectral-Two succeeds for the recovery of $k\geq 3$
communities, as long as the parameters $P,\rho$ satisfies certain conditions.
To this end, let us define Spectral-Two for general $k$.

Algorithm 2 Classify-Multiple

1:Censored graph $G$ on $n$ vertices, vectors
$(u_{i})_{i=1}^{m}\subset\mathbb{R}^{n}$, and scalars,
$\gamma_{1},\dots,\gamma_{m},T\in\mathbb{R}$.

2:Community classification.

3:Compute possible assignments $\hat{S}$ consisting of $\hat{\sigma}(\cdot;s)$
with $s\in\\{\pm 1\\}^{2k}$ such that
$\displaystyle\hat{\sigma}(j;s)=\operatornamewithlimits{argmax}_{i\in[k]}\sum_{i=1}^{m}s_{i}\gamma_{i}u_{i}.$

4:Output $\hat{\sigma}(\cdot;s)$ that maximizes the posterior probability over
$\mathbb{P}(G\mid\hat{\sigma})$ over $\hat{\sigma}\in\hat{S}$.

######  Definition 1.11 (Spectral-Two for $k\geq 3$ communities).

An algorithm $\mathcal{A}(G,y_{1},y_{2},(a_{i})_{i=1}^{2k},T)$ in this class
takes as input a censored graph $G$, two encoding parameter
$y_{1},y_{2}\in\mathbb{R}_{+}$ with $y_{1}\neq y_{2}$ and
$(a_{i})_{i=1}^{2k}\subset\mathbb{R}^{k}$, $T\in\mathbb{R}$. The algorithm
considers two signed adjacency matrices $A_{1}=A(G,y_{1})$ and
$A_{2}=A(G,y_{2})$, and computes their top $k$ eigenvectors
$(u_{i}^{1})_{i\in[k]},(u_{i}^{2})_{i\in[k]}$. Then the algorithm outputs
$\textsc{Classify-
Multiple}((u_{i}^{r})_{i\in[k],r=1,2},(a_{i})_{i=1}^{2k},T)$. As before, we
denote the output of algorithm $\mathcal{A}$ from this class as
$\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}$.

######  Theorem 1.12 (Success of Spectral-Two for $k\geq 3$ communities).

Let $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$ where $\rho\in(0,1)^{k}$ is such
that $\sum_{i}\rho_{i}=1$, and $P\in(0,1)^{k\times k}$ is a symmetric matrix.
Further, suppose that $P\cdot\text{diag}(\rho)$ has exactly $k$ distinct non-
zero eigenvalues. There exists a finite set $\mathcal{Y}\subset\mathbb{R}_{+}$
such that for any $y_{1}\neq y_{2}$ and $y_{1},y_{2}\notin\mathcal{Y}$, there
exist explicit constants $(a_{i})_{i=1}^{2k}\subset\mathbb{R}^{k}$ such that
the algorithm $\mathcal{A}(G,y_{1},y_{2},(a_{i})_{i=1}^{2k},0)$ from the class
Spectral-Two satisfies

$\lim_{n\to\infty}\mathbb{P}(\hat{\sigma}_{\scriptscriptstyle\mathcal{A}}\text{
achieves exact recovery})=1,\quad\text{ for any }t>t_{c}.$

In particular, Algorithm 6 produces such an estimator.

######  Remark 1.13.

The fact that the encoding parameters $y_{1},y_{2}$ lie outside a finite set
in Theorems 1.10 and 1.12 is required to ensure that $\mathbb{E}[A(G,y_{1})]$,
$\mathbb{E}[A(G,y_{2})]$ have $k$ distinct and non-zero eigenvalues. The
requirement of having $k$ non-zero eigenvalues is intuitive as we seek to
recover an underlying rank $k$ structure. On the other hand, the eigenvectors
of $A(G,y)$ can only be approximated up to an unknown orthogonal
transformation. This causes an ambiguity for defining the final estimator.
When the eigenvalues are distinct, this ambiguity can be resolved by going
over all possible sign flips $s$ and choosing the best among them, as in
Algorithm 1.3 Step 2, or Algorithm 1.3 Step 2.

######  Remark 1.14.

The condition in Theorem 1.12 that $P\cdot\text{diag}(\rho)$ has distinct and
non-zero values can be relaxed. In fact, if $P^{\scriptscriptstyle(y)}$ is the
matrix such that
$P^{\scriptscriptstyle(y)}_{ij}:=\rho_{j}(P_{ij}-y(1-P_{ij}))$, then by Lemma
6.1, the same conclusions as Theorem 1.12 hold as long as there exists a $y$
such that $P^{\scriptscriptstyle(y)}$ has $k$ distinct and non-zero
eigenvalues. In fact, we can simply choose $y\sim\text{Uniform}((0,1))$.

###  1.4. Proof ideas

We now give a brief outline of the proofs. For a vertex $v$, we call
$d(v)=(d_{+j},d_{-j})_{j\in[k]}\in\mathbb{Z}_{+}^{2k}$ to be the _degree
profile_ of a vertex, where $d_{+j}=d_{+j}(v),d_{-j}=d_{-j}(v)$ respectively
denote the number of present and absent edges from $v$ to community $j$ for
$j\in[k]$. Let us re-scale $\bar{d}(v)=d(v)/t\log n$. The proof consists
mainly of two steps:

Step 1: Characterization of spectral algorithms using degree profiles. Given
any signed adjacency matrix $A=A(G,y)$, the starting point of our analysis is
to find a good $\ell_{\infty}$-approximation for the eigenvectors. Using a
recent general framework by Abbe, Fan, Wang and Zhong [1], we can show that
the two leading eigenvalues $u_{1},u_{2}$ of $A$ satisfy (see Corollary 4.2):

$\displaystyle\min_{s\in\\{\pm
1\\}}\bigg{\|}su_{i}-\frac{Au_{i}^{\star}}{\lambda_{i}^{\star}}\bigg{\|}_{\infty}=o\bigg{(}\frac{1}{\sqrt{n}}\bigg{)},\quad\text{
for }i\in[k],$

with probability $1-o(1)$, where $(\lambda_{i}^{\star},u_{i}^{\star})$ is the
$i$-th largest eigenvalue/eigenvector pair of $\mathbb{E}[A]$. Note that
$\mathbb{E}[A]$ is a rank-two matrix with $u_{i}^{\star}$’s taking the same
constant value corresponding to all vertices in the same community. The low
rank of $\mathbb{E}[A]$ allows us to express $Au_{i}^{\star}$ as a linear
combination of the degree profiles and thus drastically reduce the dimension
of the problem. Using this representation, any linear combination of the
$u_{i}^{\prime}s$ is also an expressible linear combination of degree
profiles. Hence, we show that spectral algorithms essentially are
asymptotically equivalent to classifying vertices depending on whether
$\langle w_{\scriptscriptstyle\mathrm{Spec}},\bar{d}(v)\rangle>(T+o(1))$ or
$\langle w_{\scriptscriptstyle\mathrm{Spec}},\bar{d}(v)\rangle<(T-o(1))$ for
some $w_{\scriptscriptstyle\mathrm{Spec}}\in\mathbb{R}^{2k},T\in\mathbb{R}$.

Step 2: Geometry of degree profiles. At this point, the problem reduces to
understanding whether, for a given vector $w$, a hyperplane orthogonal to $w$
can separate re-scaled degree profiles. To this end, for each community $i$,
we define a measure of _dissonance_ $\eta_{i}$ for rescaled degree profiles,
and define the $\delta$-_dissonance range_ as
$\mathrm{DR}_{\delta}(i):=\\{\bar{d}:\eta_{i}(\bar{d})\leq\delta\\}$. We show
that $\mathrm{DR}_{\delta}(i)$’s are closed and convex sets. Moreover, (1) if
$1/t<\delta$, then all the re-scaled degree profiles from community $i$ lie in
$\mathrm{DR}_{\delta}(i)$ and (2) if $\delta<1/t$, then the re-scaled degree
profiles from community $i$ are asymptotically _dense_ in
$\mathrm{DR}_{\delta}(i)$ (see Lemma 2.4). In a sense, one can think of
$\mathrm{DR}_{1/t}(i)$ as the cloud of re-scaled degree profiles arising from
community $i$.

$x^{\star}$$w^{\star}$$\mathrm{DR}_{\delta}(1)$$\mathrm{DR}_{\delta}(2)$Optimally
separating hyperplane Figure 1. Visualizing dissonance ranges of two
communities near $t_{c}$.

Next, consider the “hardest” scenario when $t=t_{c}$. In that case, we show
that the clouds $\mathrm{DR}_{1/t_{c}}(i)$ and $\mathrm{DR}_{1/t_{c}}(j)$
corresponding to communities $i$ and $j$ intersect only at a single point
$x^{\star}$ (see Lemma 2.9), and as $t$ increases away from $t_{c}$, the two
clouds gradually separate. Due to convexity, $\mathrm{DR}_{1/t_{c}}(i)$ and
$\mathrm{DR}_{1/t_{c}}(j)$ lie on two opposite sides of the tangent hyperplane
at $x^{\star}$. Let $w^{\star}$ be such that this tangent hyperplane is given
by $H^{\star}=\\{x:\langle w^{\star},x-x^{\star}\rangle=0\\}$. Then
$H^{\star}$ is the only hyperplane that separates the clouds of degree
profiles near $t_{c}$; see Figure 1. Thus, as long as we are trying to
separate clouds of degree profiles using this $H^{\star}$, we will succeed for
any $t>t_{c}$. However, if we try to separate the clouds with a different
hyperplane $\\{x:\langle w,x-x^{\star}\rangle=0\\}$ for some
$w\notin\mathrm{Span}(w^{\star})$, then we will fail sufficiently close to
$t_{c}$.

Combining this with the asymptotic characterization of spectral algorithms, it
thus remains to be seen whether we can choose the parameters of the spectral
algorithm in such a way that
$w_{\scriptscriptstyle\mathrm{Spec}}\in\mathrm{Span}(w^{\star})$. For
Spectral-One algorithms in the two community case, we show that
$w_{\scriptscriptstyle\mathrm{Spec}}$ takes values in a restricted set
$\\{w\in\mathbb{R}^{4}:\frac{w_{1}}{w_{2}}=\frac{w_{3}}{w_{4}}=y\\}$, no
matter the choice of the parameters. Thus, for Spectral-One algorithms,
generally $w_{\scriptscriptstyle\mathrm{Spec}}\notin\mathrm{Span}(w^{\star})$
except for the specific cases in Theorem 1.7 1. However, for Spectral-Two
algorithms, there always exists a way to choose the linear combinations in
such a way that
$w_{\scriptscriptstyle\mathrm{Spec}}\in\mathrm{Span}(w^{\star})$, which
ensures their optimality.

Information Theoretic Threshold. There is an alternate way of characterizing
the information theoretic boundary by observing that even the “best” estimator
will separate communities using the hyperplane $H^{\star}$ above. Consider the
problem of classifying a single vertex $v$ given $G$ and
$(\sigma_{0}(u))_{u\in[n]\setminus\\{v\\}}$. The MAP estimator for the
community assignment of $v$ is called the genie-based estimator. This is an
optimal estimator (even though it is not computable given $G$). Now, a direct
computation shows that genie-based estimator classifies a vertex in one of the
two communities based on whether $\langle w^{\star},\bar{d}(v)\rangle>0$ or
$\langle w^{\star},\bar{d}(v)\rangle<0$, with the same $w^{\star}$ as above
(see [9, Proposition 6.1]). Thus, in a sense, separating degree profiles based
on hyperplanes orthogonal to $w^{\star}$ is the optimal decision rule. When
$t<t_{c}$, the degree profile clouds of the two communities overlap
significantly, and therefore even the optimal estimator misclassifies a
growing number of vertices. This gives rise to the information theoretic
impossibility region for exact recovery when $t<t_{c}$.

###  1.5. Discussion

Theorems 1.10 and 1.12 prove optimality of spectral algorithms using two
matrices. The use of two matrices hinges on the fact that there are three
types of edge-information present, absent, and censored, and the information
about a vertex’s community coming from present and absent edges are of the
same order. We believe that our results generalize in a straightforward manner
to the scenario of labelled edges, where the possible edge statuses
$\\{\text{present,absent}\\}$ are replaced by $D$ different types. The case
with $D$ labels has been studied in [14] when there are two balanced
communities, and symmetric intra-community edge probabilities for each of the
$D$ types. In this case, [14] identified the information-theoretic threshold.
However, no efficient algorithms were provided. We believe that optimal
spectral algorithms in the general $D$-labeled edge scenario must use $D$
different encoding matrices.

We also believe that the framework of this paper can be extended beyond graphs
to other important machine learning problems with censoring on top of an
underlying low-rank structure. This may include non-square matrices (e.g.
items vs features matrix in recommender systems). We leave these as
interesting future research questions.

###  1.6. Notation.

Let $[n]=\\{1,,2,\dots,n\\}$. We often use the Bachmann?Landau asymptotic
notation $o(1),O(1)$ etc. For two sequences $(a_{n})_{n\geq 1}$ and
$(b_{n})_{n\geq 1}$, we write $a_{n}\asymp b_{n}$ as a shorthand for
$\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=1$. Given a sequence of probability
measures $(\mathbb{P}_{n})_{n\geq 1}$, a sequence of events
$(\mathcal{E}_{n})_{n\geq 1}$ is said to hold _with high probability_ if
$\lim_{n\to\infty}\mathbb{P}_{n}(\mathcal{E}_{n})=1$

For a vector $x\in\mathbb{R}^{d}$, we define
$\|x\|_{2}=(\sum_{i}x_{i}^{2})^{1/2}$ and $\|x\|_{\infty}=\max_{i}|x_{i}|$.
For $x\in\mathbb{R}^{d}$ and $r>0$, we denote the open $\ell_{2}$-ball of
radius $r$ around $x$ by $B_{2}(x,r)$. Similarly, for $X\subset\mathbb{R}^{d}$
and $r>0$, we denote the open $\ell_{2}$-ball of radius $r$ around $X$ by
$B_{2}(X,r)$. For a collection of vectors $(x_{i})_{i}\subset\mathbb{R}^{d}$,
we denote their linear span by $\mathrm{Span}((x_{i})_{i})$. Also, given a
subspace $\mathcal{Z}\subset\mathbb{R}^{d}$, the projection of $x$ onto
$\mathcal{Z}$ will be denoted by
$\mathrm{Proj}_{\scriptscriptstyle\mathcal{Z}}(x)$.

For a matrix $M\in\mathbb{R}^{n\times d}$, we use $M_{i\cdot}$ to refer to its
$i$-th row, represented as a row vector. Given a matrix $M$,
$\|M\|_{2}=\max_{\|x\|_{2}=1}\|Mx\|_{2}$ is the spectral norm,
$\|M\|_{2\to\infty}=\max_{i}\|M_{i\cdot}\|_{2}$ is the matrix $2\to\infty$
norm, and $\|M\|_{F}=(\sum_{i,j}M_{ij}^{2})^{1/2}$ is the Frobenius norm.
Whenever we apply a real-value function to a vector, it should be interpreted
as a coordinatewise operation.

Throughout, we condition on the event that the random community assignments
given by $\sigma_{0}$ are close to their expected sizes. Specifically, note
that, since $n_{j}:=\\{v:\sigma_{0}(v)=j\\}$ are marginally distributed as
$\text{Bin}\left(n,\rho_{j}\right)$, and therefore, for all
$\varepsilon\in(0,1)$,

$\begin{split}\left|n_{j}-n\rho_{j}\right|\leq\varepsilon n\end{split}$ (1.4)

with probability at least $1-2\exp(-\varepsilon^{2}n/2)$ by applying the
McDiarmid inequality. Throughout, the notation
$\mathbb{P}(\cdot),\mathbb{E}[\cdot]$ conditions on a fixed value of
$\sigma_{0}$ satisfying (1.4) with $\varepsilon=n^{-1/3}$.

###  1.7. Organization

We start analyzing the geometric properties of the degree profile clouds in
Section 2, which lies in the heart of all the proofs. Subsequently, in Section
3, we prove the impossibility result and also prove that the Maximum a
Posteriori (MAP) Estimator always succeeds up to the information theoretic
threshold. The entrywise bounds for the top eigenvectors are provided in
Section 4. Finally, we complete the proofs of Theorems 1.7, 1.10 in Section 5.

##  2\. Geometry of Degree Profiles

In this section, we develop the technical tools for Step 2 in Section 1.4. We
will develop these tools for general $k$-community CSBMs. Throughout, we fix
$\rho\in(0,1)^{k}$ such that $\sum_{i=1}^{k}\rho_{i}=1$ and let
$P\in(0,1)^{k\times k}$ be a symmetric matrix. Let us define degree profiles,
which will be the main object of analysis in this section.

######  Definition 2.1 (Degree profile).

Suppose that $G\sim\textsc{CSBM}_{n}^{k}(P,\rho,t)$. For a vertex $v$, we
define $d(v)=(d_{+r},d_{-r})_{r\in[k]}\in\mathbb{Z}_{+}^{2k}$ to be the
_degree profile_ of $v$, where $d_{+r}=d_{+r}(v)$ and $d_{-r}=d_{-r}(v)$
respectively denote the number of present and absent edges from $v$ to
community $r$ for $r\in[k]$.

In Section 2.1, we start by defining dissonance ranges for degree profiles in
each community, and prove their desirable analytic properties. In Section 2.2,
we use dissonance ranges to characterize the clouds of degree profiles. Next,
in Section 2.3, we provide a general criterion describing when degree profiles
cannot be separated by hyperplanes. Section 2.4 focuses on analyzing the
degree profiles in the “hardest” case when dissonance ranges barely overlap.
Finally, in Section 2.5, all the above analysis leads to a tractable criterion
for when we can separate clouds of degree profiles using hyperplanes.

###  2.1. Dissonance range and its properties.

Let us start by defining the dissonance range and obtaining some basic
analytic properties.

######  Definition 2.2 (Dissonance range).

Given $i\in[k]$ and $x\in\mathbb{R}_{+}^{2k}$, the _dissonance_ of $x$
relative to community $i$ is given by

$\eta_{i}(x)=\sum_{r=1}^{k}\bigg{[}x_{1,r}\log\bigg{(}\frac{x_{1,r}}{\mathrm{e}\rho_{r}P_{ri}}\bigg{)}+x_{2,r}\log\bigg{(}\frac{x_{2,r}}{\mathrm{e}\rho_{r}(1-P_{ri})}\bigg{)}\bigg{]}+1,$
(2.1)

where we regard the terms in these expressions as being $0$ if the
corresponding entry of $x$ is $0$. We also define the $\delta$-_dissonance
range_ relative to community $i$ by
$\mathrm{DR}_{\delta}(i):=\\{x:\eta_{i}(x)\leq\delta\\}$.

######  Lemma 2.3.

Fix $i\in[k]$ and $\delta>0$. Then $\mathrm{DR}_{\delta}(i)$ is a bounded,
closed and convex subset of $\mathbb{R}_{+}^{2k}$. Then, for any
$\delta^{\prime}>\delta$, there exist $\varepsilon>0$ such that

$\displaystyle
B_{2}(\mathrm{DR}_{\delta}(i),\varepsilon)\cap\mathbb{R}_{+}^{2k}\subset\mathrm{DR}_{\delta^{\prime}}(i).$

###### Proof.

We first show that $\mathrm{DR}_{\delta}(i)$ is bounded. Note that
$z\log(z)\to\infty$ if and only if $z\to\infty$. Thus, if
$\mathrm{DR}_{\delta}(i)$ were unbounded, then we could find a subsequence
$(x_{k})_{k\geq 1}\subset\mathrm{DR}_{\delta}(i)$ such that
$\eta_{i}(x_{k})\to\infty$. However, $\eta_{i}(x_{k})\leq\delta$ by definition
of $\mathrm{DR}_{\delta}(i)$. This leads to a contradiction and hence
$\mathrm{DR}_{\delta}(i)$ is bounded.

Next, since $\eta_{i}$ is continuous, we have that $\mathrm{DR}_{\delta}(i)$
is closed. Further, $\eta_{i}$ is a sum of convex function and hence it is
convex. Therefore, its sublevel set $\mathrm{DR}_{\delta}(i)$ is convex.

To show the last claim, note that $\eta_{i}$ is uniformly continuous on
$[0,b]^{2k}$ for any $b>0$. Thus, there exists $\varepsilon>0$ such that for
any $x,x^{\prime}\in[0,b]^{2k}$ with $\|x-x^{\prime}\|_{2}\leq\varepsilon$, we
have $|\eta_{i}(x)-\eta_{i}(x^{\prime})|\leq\delta^{\prime}-\delta$. This
proves
$B_{2}(\mathrm{DR}_{\delta}(i),\varepsilon)\cap\mathbb{R}_{+}^{2k}\subset\mathrm{DR}_{\delta^{\prime}}(i)$,
and completes the proof of the lemma. ∎

###  2.2. Relating dissonance range with degree profiles of CSBMs

Our next goal will be to identify which degree profiles are likely to occur in
CSBMs.

######  Lemma 2.4.

Fix $0<\delta<\delta^{\prime}$. Let $t\in(1/\delta^{\prime},1/\delta)$ and
$G\sim\textsc{CSBM}_{n}^{k}(P,\rho,t)$. The following holds with probability
$1-o(1)$:

  1. (1)

There exists $c>0$ such that for every $i\in[k]$ and $d\in\mathbb{Z}_{+}^{2k}$
such that $d/(t\log(n))\in\mathrm{DR}_{\delta}(i)$, there are at least $n^{c}$
vertices in community $i$ with degree profile $d$.

  2. (2)

For each $i\in[k]$ and for every vertex $v\in G$ in community $i$, the degree
profile of $v$ is of the form $xt\log(n)$ for some
$x\in\mathrm{DR}_{\delta^{\prime}}(i)$.

In order to prove this lemma, we need the Poisson approximation result stated
below. The proof of this follows from a straightforward application of
Stirling’s approximation and will therefore be provided in Appendix A.

######  Lemma 2.5.

Let $(S_{r})_{r\in[k]}$ be a partition of $[n]$ such that
$|S_{r}|=n\rho_{r}(1+O(\log^{-2}n))$ for all $r\in[k]$, where
$\rho\in(0,1)^{k}$. Suppose that $\\{W_{v}\\}_{v=1}^{n}$ is i.i.d. from a
distribution taking values in $\\{a,b,c\\}$ and, if $v\in S_{r}$,
$\mathbb{P}(W_{v}=a)=\alpha\psi_{r}$,
$\mathbb{P}(W_{v}=b)=\alpha(1-\psi_{r})$, and $\mathbb{P}(W_{v}=c)=1-\alpha$.
Fix $i\in[k]$. Also, let $V\subset S_{i}$ be such that $|V|=O(n/\log^{2}n)$.

For $x=a,b$, let $D_{x,r}:=\\#\\{v\in S_{r}:W_{v}=x\\}$ for
$r\notin[k]\setminus\\{i\\}$ and $D_{x,i}:=\\#\\{v\in S_{i}\cap
V^{c}:W_{v}=x\\}$. Let $D=(D_{a,r},D_{b,r})_{r\in[k]}$ and also let
$d=(d_{1,r},d_{2,r})_{r\in[k]}\in\mathbb{Z}_{+}^{2k}$ be such that
$\|d\|_{1}=o(\log^{3/2}n)$ and $\alpha=t\log n/n$. Then

$\displaystyle\mathbb{P}\left(D=d\right)\asymp\prod_{r=1}^{k}P\left(\rho_{r}\psi_{r}t\log
n;d_{1,r}\right)P\left(\rho_{r}(1-\psi_{r})t\log n;d_{2,r}\right),$

where $P(\lambda;m)$ is the probability that a $\mathrm{Poisson}(\lambda)$
random variable takes value $m$.

###### Proof of Lemma 2.4.

To prove the first part, fix $i\in[k]$ and let $d\in\mathbb{Z}_{+}^{2k}$ be
such that $d/(t\log(n))\in\mathrm{DR}_{\delta}(i)$. Recall that $n_{j}$ is the
number of vertices in community $j$ for every $j\in[k]$. By (1.4),
$\left|n_{j}-n\rho_{j}\right|\leq n^{\frac{2}{3}}$ for all $j\in[k]$, with
probability $1-o(1)$. In the subsequent proof, we always condition on this
event, even if it is not mentioned explicitly.

Let $S_{i}$ be a random set of $2n/\log^{2}(n)$ vertices in community $i$.
Next, let $S^{\prime}_{i}$ be the subset of $S_{i}$ consisting of all vertices
$v$ such that all the connections between $v$ and $S_{i}$ are censored. To
lower-bound the size of $S^{\prime}_{i}$, let $X$ be the number of revealed
connections among vertices in $S$. By a counting argument,
$|S^{\prime}_{i}|\geq|S_{i}|-2X$. Observe that
$\mathbb{E}[X]=\binom{2n/\log^{2}n}{2}\frac{t\log n}{n}=O(n/\log^{3}(n))$. The
Markov inequality then implies that $X=o(|S_{i}|)$ with high probability,
which implies $|S^{\prime}_{i}|\geq\frac{1}{2}|S_{i}|=\frac{n}{\log^{2}(n)}$.

Let $\mathscr{F}^{\prime}$ denote the sigma-algebra with respect to which
$S_{i}$ and $(n_{j})_{j\in[k]}$ are measurable, and let

$\mathscr{F}:=\mathscr{F}^{\prime}\cap\bigg{\\{}|n_{j}-n\rho_{j}|\leq
n^{\frac{2}{3}},\forall
j\in[k]\bigg{\\}}\cap\bigg{\\{}|S_{i}^{\prime}|\geq\frac{n}{\log^{2}(n)}\bigg{\\}}.$

Fix $v\in[n]$. Since $\mathrm{DR}_{\delta}(i)$ is bounded, we have that
$\|d\|_{1}=O(\log n)$. Thus, by Lemma 2.5,

$\begin{split}{cond-prob-simpl}&\mathbb{P}(d(v)=d\mid\mathscr{F}\cap\\{v\in
S_{i}^{\prime}\\})\\\ &\asymp\mathrm{e}^{-t\log
n}\prod_{j=1}^{k}\frac{\big{[}\rho_{j}P_{i,j}t\log(n)\big{]}^{d_{+j}}}{d_{+j}!}\frac{\big{[}\rho_{j}(1-P_{i,j})t\log(n)\big{]}^{d_{-j}}}{d_{-j}!}\\\
&\asymp
n^{-t}\prod_{j=1}^{k}\frac{(\rho_{j}P_{i,j}t\log(n))^{d_{+j}}}{\sqrt{2\pi
d_{+j}}(d_{+j}/\mathrm{e})^{d_{+j}}}\frac{(\rho_{j}(1-P_{i,j})t\log(n))^{d_{-j}}}{\sqrt{2\pi
d_{-j}}(d_{-j}/\mathrm{e})^{d_{-j}}}\\\
&=n^{-t}\prod_{j=1}^{k}\frac{1}{2\pi\sqrt{d_{+j}d_{-j}}}\bigg{(}\frac{\mathrm{e}\rho_{j}P_{i,j}t\log(n)}{d_{+j}}\bigg{)}^{d_{+j}}\bigg{(}\frac{\mathrm{e}\rho_{j}(1-P_{i,j})t\log(n)}{d_{-j}}\bigg{)}^{d_{-j}}\\\
&=\bigg{(}\prod_{j=1}^{k}\frac{1}{2\pi\sqrt{d_{+j}d_{-j}}}\bigg{)}n^{-t\eta_{i}(d/t\log
n)},\end{split}$ (2.2)

where in the final step, we have used the definition of $\eta_{i}$ from (2.1).
Next, since $d/(t\log(n))\in\mathrm{DR}_{\delta}(i)$, we have that
$\eta_{i}(d/t\log(n))\leq\delta$, and thus (LABEL:cond-prob-simpl) yields, for
all sufficiently large $n$,

$\begin{split}p_{n}:=\mathbb{P}(d(v)=d\mid\mathscr{F}\cap\\{v\in
S_{i}^{\prime}\\})\geq C\frac{n^{-t\delta}}{\log^{k}n}+o(n^{-1})\geq
n^{-t\delta(1+o(1))},\end{split}$ (2.3)

for some $C>0$. Next, if $d^{\prime}(v)$ denotes the degree profile of vertex
$v$ discarding all the present and absent edges in $S_{i}$, then
$d(v)=d^{\prime}(v)$ for all $v\in S_{i}^{\prime}$. Moreover, conditionally on
$\mathscr{F}^{\prime}$, $\\{d^{\prime}(v)\\}_{v\in S_{i}^{\prime}}$ are
independent. Thus, conditionally on $\mathscr{F}$, $|\\{v\in
S_{i}^{\prime}:d(v)=d\\}|$ is distributed as a
$\text{Bin}(|S_{i}^{\prime}|,p_{n})$ random variable. Note also that,
conditionally on $\mathscr{F}$, $|S_{i}^{\prime}|p_{n}\geq 2n^{c}$ for some
$c>0$. Thus, using concentration of binomial random variables, we conclude
that

$|\\{v\in
S_{i}^{\prime}:d(v)=d\\}|\geq\frac{1}{2}~{}|S_{i}^{\prime}|~{}p_{n}\geq n^{c}$

with probability at least $1-\exp(-c^{\prime}n^{c})$ for some $c^{\prime}>0$.
Observing that $|\\{d\in\mathbb{Z}_{+}^{2k}:d/(\log
n)\in\mathrm{DR}_{\delta}(i)\\}|=O\left(\text{polylog}(n)\right)=o(\exp(c^{\prime}n^{c}))$,
the claim follows by a union bound.

In order to prove the second part, we again use (LABEL:cond-prob-simpl). By
the union bound and [12, Corollary 2.4], there exists a sufficiently large
constant $C>0$ such that

$\begin{split}\mathbb{P}(\exists v\in[n]:\|d(v)\|_{1}>C\log
n)=o(n^{-1}).\end{split}$ (2.4)

Now, for any $d$ such that $d/(t\log n)\notin\mathrm{DR}_{\delta^{\prime}}(i)$
and $\|d\|_{1}\leq C\log n$, we can use (LABEL:cond-prob-simpl) to show that,
for all sufficiently large $n$, and fixed $v\in[n]$

$\displaystyle\mathbb{P}(d(v)=d)\leq(1+o(1))\bigg{(}\prod_{j=1}^{k}\frac{1}{2\pi\sqrt{d_{+,j}d_{-,j}}}\bigg{)}n^{-t\eta_{i}(d/t\log
n)}\leq n^{-t\delta^{\prime}}.$ (2.5)

Now,

$\displaystyle\mathbb{P}(\exists v\text{ with }\sigma_{0}(v)=i:d(v)/(t\log
n)\notin\mathrm{DR}_{\delta^{\prime}}(i))$ $\displaystyle\leq
n\mathbb{P}(d(v)=d\text{ for some }d/(t\log
n)\notin\mathrm{DR}_{\delta^{\prime}}(i)\text{ and }\|d\|_{1}\leq C\log
n)+o(1)$ $\displaystyle\leq n(C\log n)^{2k}n^{-t\delta^{\prime}}+o(1)=o(1),$

where in the last step we have used that $t\delta^{\prime}>1$. Hence the proof
is complete. ∎

###  2.3. Separating degree profiles using hyperplanes

As discussed in Section 1.4, the $\ell_{\infty}$ approximation guarantee for
the eigenvectors gives us an alternative characterization of spectral
algorithms in terms of separating degree profiles of different communities
using certain hyperplanes. The next proposition allows us to determine when
separation using hyperplanes is impossible. Before the statement we need a
couple of definitions. Let $V_{i}$ denote the vertices in community $i$.

######  Definition 2.6 (Separates communities).

We say that $w\in\mathbb{R}^{2k}$ _separates communities $(i,j)$ with margin
$\beta>0$_ if

$\min_{v\in V_{i}}w^{T}d(v)\geq\beta/2\quad\text{and}\quad\max_{v\in
V_{j}}w^{T}d(v)\leq-\beta/2.$

If $w$ separates communities $(i,j)$ with margin $\beta>0$, then computing the
weighted degree profile $w^{T}d(v)$ for each $v\in V_{i}\cup V_{j}$ allows us
to distinguish these two communities. Note that if $w$ separates communities
$(i,j)$ with margin $\beta$, then $-w$ also separates communities $(i,j)$ with
margin $\beta$. Next we define the scenario where a finite number of
hyperplanes cannot separate the two communities.

######  Definition 2.7 (Confuses communities).

Let $(w_{r})_{r=1}^{m}\subset\mathbb{R}^{2k}$ and let
$(\gamma_{r})_{r=1}^{m}\subset\mathbb{R}$. We say that
$[(w_{r})_{r=1}^{m},(\gamma_{r})_{r=1}^{m}]$ _confuses communities $(i,j)$ at
level $\beta$_ if there exist $u\in V_{i}$, $v\in V_{j}$, and
$s\in\\{-1,1\\}^{m}$ such that $s_{r}(w_{r}^{T}d(u)-\gamma_{r})>\beta$ and
$s_{r}(w_{r}^{T}d(v)-\gamma_{r})>\beta$ for all $1\leq r\leq m$.

In other words, there are representatives from communities $i$ and $j$, such
that both of their degree profiles appear on the same sides of all the
hyperplanes $\\{x:w_{r}^{T}x=\gamma_{r}\\}$. A larger value of $\beta$ means
that the pair of degree profiles is farther from the hyperplanes. Note that
the notion of confusion also rules out the possibility of separation with
multiple hyperplanes. We now prove the following proposition:

######  Proposition 2.8.

Let $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$,
$\mathcal{Z}\subset\mathbb{R}^{2k}$ be a linear subspace, and let $\delta>0$
be such that $t\delta<1$. Suppose further that there are communities $i$ and
$j$ such that the projections of $\mathrm{DR}_{\delta}(i)$ and
$\mathrm{DR}_{\delta}(j)$ onto $\mathcal{Z}$ overlap. Then, for any
$m\in\mathbb{N}$, there exists $\varepsilon>0$ such that for any unit vectors
$w_{1},...,w_{m}\in\mathcal{Z}$ and $\gamma_{1},...,\gamma_{m}\in\mathbb{R}$,
with probability $1-o(1)$, $[(w_{r})_{r=1}^{m},(\gamma_{r}\log n)_{r=1}^{m}]$
confuses communities $i$ and $j$ at level $\varepsilon\log(n)$.

###### Proof.

Let
$z_{0}\in\text{Proj}_{\mathcal{Z}}(\mathrm{DR}_{\delta}(i))\cap\text{Proj}_{\mathcal{Z}}(\mathrm{DR}_{\delta}(j))$.
There must exist $z_{i}\in\mathrm{DR}_{\delta}(i)$ and
$z_{j}\in\mathrm{DR}_{\delta}(j)$ such that
$\text{Proj}_{\mathcal{Z}}(z_{i})=\text{Proj}_{\mathcal{Z}}(z_{j})=z_{0}$.
Now, let $\delta^{\prime}=\frac{1}{2}\left(\delta+\frac{1}{t}\right)$, so that
$\delta<\delta^{\prime}<\frac{1}{t}$. By Lemma 2.3, there exists $\mu>0$ such
that
$B_{2}(\mathrm{DR}_{\delta}(i),\mu)\cap\mathbb{R}_{+}^{2k}\subseteq\mathrm{DR}_{\delta^{\prime}}(i)$
and
$B_{2}(\mathrm{DR}_{\delta}(j),\mu)\cap\mathbb{R}_{+}^{2k}\subseteq\mathrm{DR}_{\delta^{\prime}}(j)$.
So, if we let $\mu_{0}=\mu/3k$ and
$z^{\prime}_{0}=z_{0}+\text{Proj}_{\mathcal{Z}}(\mu_{0},\mu_{0},...,\mu_{0})$
then

$\displaystyle B_{2}(z^{\prime}_{0},\mu_{0})\cap\mathcal{Z}$
$\displaystyle=\text{Proj}_{\mathcal{Z}}(B_{2}(z_{i}+(\mu_{0},...,\mu_{0}),\mu_{0}))$
$\displaystyle\subseteq\text{Proj}_{\mathcal{Z}}(B_{2}(z_{i},\mu)\cap\mathbb{R}_{+}^{2k})$
$\displaystyle\subseteq\text{Proj}_{\mathcal{Z}}(\mathrm{DR}_{\delta^{\prime}}(i))$

By the same logic,
$B_{2}(z^{\prime}_{0},\mu_{0})\cap\mathcal{Z}\subseteq\text{Proj}_{\mathcal{Z}}(\mathrm{DR}_{\delta^{\prime}}(j))$.

Fix $m\in\mathbb{N}$, unit vectors $w_{1},\dots,w_{m}\in\mathbb{R}^{2k}$, and
$\gamma_{1},\dots,\gamma_{m}$. Then there exist $\varepsilon>0$, an open ball
$B\subseteq B_{2}(z^{\prime}_{0},\mu_{0})\cap\mathcal{Z}$, and
$s\in\\{-1,1\\}^{m}$ such that for all $x\in B$,

$s_{r}\left(w_{r}^{T}x-\frac{\gamma_{r}}{t}\right)>\frac{\varepsilon}{t}$

for all $1\leq r\leq m$. In other words, the open ball $B$ is separated from
all hyperplanes defined by $(w_{r},\gamma_{r})_{r=1}^{m}$.

Now, observe that for all sufficiently large $n$ there exist
$x_{i}\in\mathrm{DR}_{\delta^{\prime}}(i)\cap\text{Proj}^{-1}_{\mathcal{Z}}(B)$
and
$x_{j}\in\mathrm{DR}_{\delta^{\prime}}(j)\cap\text{Proj}^{-1}_{\mathcal{Z}}(B)$
such that $x_{i}t\log(n),x_{j}t\log(n)\subseteq\mathcal{Z}_{+}^{2k}$. Since
$t\delta^{\prime}<1$, by Lemma 2.4, with probability $1-o(1)$, there exist
vertices $u\in V_{i}$ and $v\in V_{j}$ such that $d(u)/(t\log(n))=x_{i}$ and
$d(v)/(t\log(n))=x_{j}$. By the above, we have

$s_{r}\left(w_{r}\frac{d(u)}{t\log
n}-\frac{\gamma_{r}}{t}\right)=s_{r}\left(w_{r}\frac{d(v)}{t\log
n}-\frac{\gamma_{r}}{t}\right)>\frac{\varepsilon}{t}$

for all $1\leq r\leq m$. Multiplying through by $t\log n$, we conclude that
$[(w_{r})_{r=1}^{m},(\gamma_{r}\log n)_{r=1}^{m}]$ confuses communities $i$
and $j$ at level $\varepsilon\log n$. ∎

###  2.4. When dissonance ranges barely overlap.

At this point, the key question is what hyperplanes can separate the rescaled
degree profiles from different communities. In order to answer that, we
consider the “hardest” case where
$t=t_{0}=1/\Delta_{+}(\theta_{i},\theta_{j})$, with $\theta_{i}$ defined by
(1.2). Define the $2k$-dimensional vector $w^{\star}$ as

$\begin{split}w^{\star}=\bigg{(}\log\frac{P_{ri}}{P_{rj}},\log\frac{1-P_{ri}}{1-P_{rj}}\bigg{)}_{r\in[k]}.\end{split}$
(2.6)

Below, we show that the hyperplane orthogonal to $w^{\star}$ almost separates
the dissonance ranges even for $t=t_{0}$. We also set up additional properties
that will help us to show that a hyperplane orthogonal to $w\neq w^{\star}$
cannot separate the dissonance ranges just above $t_{0}$, and also to
establish the impossibility of exact recovery (Theorem 1.4) below $t_{0}$.

######  Lemma 2.9.

Suppose that $1\leq i<j\leq k$ and let
$t_{0}=1/\Delta_{+}(\theta_{i},\theta_{j})$, where $\theta_{i}$ is defined by
(1.2). Then $\mathrm{DR}_{1/t_{0}}(i)$ and $\mathrm{DR}_{1/t_{0}}(j)$
intersect at a single point. Let $x^{\star}$ be this intersection point of
$\mathrm{DR}_{1/t_{0}}(i)$ and $\mathrm{DR}_{1/t_{0}}(j)$. Let
$H:=\\{x:\langle w^{\star},x-x^{*}\rangle\geq 0\\}$ be the half-space created
by the hyperplane through $x^{\star}$ perpendicular to $w^{\star}$. Then
$\mathrm{DR}_{1/t_{0}}(i)\cap H=\mathrm{DR}_{1/t_{0}}(i)$ and
$\mathrm{DR}_{1/t_{0}}(j)\cap H=\\{x^{\star}\\}$, i.e., the hyperplane
$\\{x:\langle w^{\star},x-x^{*}\rangle=0\\}$ separates
$\mathrm{DR}_{1/t_{0}}(i)\setminus\\{x^{\star}\\}$ and
$\mathrm{DR}_{1/t_{0}}(j)\setminus\\{x^{\star}\\}$. Also, there exists $r>0$
such that
$B_{2}(x^{\star}+rw^{\star},r\|w^{\star}\|_{2})\subset\mathrm{DR}_{1/t_{0}}(i)$
and
$B_{2}(x^{\star}-rw^{\star},r\|w^{\star}\|_{2})\subset\mathrm{DR}_{1/t_{0}}(j)$.
For $t<t_{0}$, the intersection $\mathrm{DR}_{1/t}(i)\cap\mathrm{DR}_{1/t}(j)$
has a non-empty interior.

###### Proof.

Recall the definition of $\Delta_{+}$ and $\mathrm{CH}_{\xi}$ from Definition
1.3. Let $\xi^{\star}$ be the maximizer of (1.1). We claim that
$0<\xi^{\star}<1$. Indeed,

$\displaystyle\Delta_{+}(\theta_{i},\theta_{j})=1-\min_{\xi\in[0,1]}\sum_{r\in[k]}\rho_{r}\left(P_{ri}^{\xi}P_{rj}^{1-\xi}+(1-P_{ri})^{\xi}(1-P_{rj})^{1-\xi}\right)=:1-\min_{\xi\in[0,1]}f(\xi).$

Now, $f(0)=f(1)=1$, and $f(1/2)<1$ by the AM-GM inequality. Therefore, the
minimum of $f$ is not attained at $\\{0,1\\}$, which proves $0<\xi^{\star}<1$.

Next, define the $2k$-dimensional vector

$\displaystyle
x^{\star}=\left(\rho_{r}P_{ri}^{\xi^{\star}}P_{rj}^{1-\xi^{\star}},\rho_{r}(1-P_{ri})^{\xi^{\star}}(1-P_{rj})^{1-\xi^{\star}}\right)_{r\in[k]}.$

Setting
$\frac{\mathrm{d}}{\mathrm{d}\xi}\mathrm{CH}_{\xi}(\theta_{i},\theta_{j})\big{|}_{\xi=\xi^{\star}}=0$
yields

$\begin{split}\sum_{r\in[k]}\bigg{[}\rho_{r}P_{ri}^{\xi^{\star}}P_{rj}^{1-\xi^{\star}}\log\frac{P_{ri}}{P_{rj}}+\rho_{r}(1-P_{ri})^{\xi^{\star}}(1-P_{rj})^{1-\xi^{\star}}\log\frac{1-P_{ri}}{1-P_{rj}}\bigg{]}=\langle
w^{\star},x^{\star}\rangle=0.\end{split}$ (2.7)

Also recall $\eta_{i}$ from (2.1). Then,

$\displaystyle\eta_{i}(x^{\star})-\eta_{j}(x^{\star})$
$\displaystyle=\sum_{r=1}^{k}\bigg{[}x_{1,r}^{\star}\log\bigg{(}\frac{x_{1,r}^{\star}}{\mathrm{e}\rho_{r}P_{ri}}\bigg{)}+x_{2,r}^{\star}\log\bigg{(}\frac{x_{2,r}^{\star}}{\mathrm{e}\rho_{r}(1-P_{ri})}\bigg{)}\bigg{]}$
$\displaystyle\qquad-\sum_{r=1}^{k}\bigg{[}x_{1,r}^{\star}\log\bigg{(}\frac{x_{1,r}^{\star}}{\mathrm{e}\rho_{r}P_{rj}}\bigg{)}+x_{2,r}^{\star}\log\bigg{(}\frac{x_{2,r}^{\star}}{\mathrm{e}\rho_{r}(1-P_{rj})}\bigg{)}\bigg{]}$
$\displaystyle=\sum_{r=1}^{k}\bigg{[}x_{1,r}^{\star}\log\bigg{(}\frac{P_{rj}}{P_{ri}}\bigg{)}+x_{2,r}^{\star}\log\bigg{(}\frac{1-P_{ri}}{1-P_{rj}}\bigg{)}\bigg{]}=\langle
w^{\star},x^{\star}\rangle=0.$

Therefore,

$\displaystyle\eta_{i}(x^{\star})$
$\displaystyle=\eta_{j}(x^{\star})=\xi^{\star}\eta_{i}(x^{\star})+(1-\xi^{\star})\eta_{j}(x^{\star})$
$\displaystyle=\sum_{r=1}^{k}\bigg{[}x_{1,r}^{\star}\log\bigg{(}\frac{x_{1,r}^{\star}}{\mathrm{e}\rho_{r}P_{ri}^{\xi^{\star}}P_{rj}^{1-\xi^{\star}}}\bigg{)}+x_{2,r}^{\star}\log\bigg{(}\frac{x_{2,r}^{\star}}{\mathrm{e}\rho_{r}(1-P_{ri})^{\xi^{\star}}(1-P_{rj})^{1-\xi^{\star}}}\bigg{)}\bigg{]}+1$
$\displaystyle=\sum_{r=1}^{k}\left[x_{1,r}^{\star}\log(1/\mathrm{e})+x_{2,r}^{\star}\log(1/\mathrm{e})\right]+1$
$\displaystyle=1-\sum_{r=1}^{k}\big{[}x_{1,r}^{\star}+x_{2,r}^{\star}\big{]}=\sum_{r=1}^{k}\left[\rho_{r}-\rho_{r}P_{ri}^{\xi^{\star}}P_{rj}^{1-\xi^{\star}}-\rho_{r}(1-P_{ri})^{\xi^{\star}}(1-P_{rj})^{1-\xi^{\star}}\right]=\Delta_{+}(\theta_{i},\theta_{j}).$

Therefore, $x^{\star}\in\mathrm{DR}_{1/t_{0}}(i)\cap\mathrm{DR}_{1/t_{0}}(j)$.
Next, observe that

$\displaystyle\nabla\eta_{i}(x^{\star})$
$\displaystyle=\bigg{(}\log\bigg{(}\frac{x_{1,r}^{\star}}{\mathrm{e}\rho_{r}P_{ri}}\bigg{)}+1,\log\bigg{(}\frac{x_{2,r}^{\star}}{\mathrm{e}\rho_{r}(1-P_{ri})}\bigg{)}+1\bigg{)}_{r\in[k]}$
$\displaystyle=\bigg{(}\log\bigg{(}\frac{P_{ri}}{P_{rj}}\bigg{)}^{\xi^{\star}-1},\log\bigg{(}\frac{1-P_{ri}}{1-P_{rj}}\bigg{)}^{\xi^{\star}-1}\bigg{)}_{r\in[k]}=(\xi^{\star}-1)w^{\star}.$

Similarly, we also have that

$\displaystyle\nabla\eta_{j}(x^{\star})$
$\displaystyle=\bigg{(}\log\bigg{(}\frac{x_{1,r}^{\star}}{\mathrm{e}\rho_{r}P_{rj}}\bigg{)}+1,\log\bigg{(}\frac{x_{2,r}^{\star}}{\mathrm{e}\rho_{r}(1-P_{rj})}\bigg{)}+1\bigg{)}_{r\in[k]}$
$\displaystyle=\bigg{(}\log\bigg{(}\frac{P_{ri}}{P_{rj}}\bigg{)}^{\xi^{\star}},\log\bigg{(}\frac{1-P_{ri}}{1-P_{rj}}\bigg{)}^{\xi^{\star}}\bigg{)}_{r\in[k]}=\xi^{\star}w^{\star}.$

By convexity of $\eta_{i}$ and $\eta_{j}$, for any $x\in[0,\infty)^{2k}$, we
have that

$\displaystyle\eta_{i}(x)$ $\displaystyle\geq\eta_{i}(x^{\star})+\langle
x-x^{\star},\nabla\eta_{i}(x^{\star})\rangle=\frac{1}{t_{0}}+\langle
x-x^{\star},(\xi^{\star}-1)w^{\star}\rangle$ (2.8)

and

$\displaystyle\eta_{j}(x)$ $\displaystyle\geq\eta_{j}(x^{\star})+\langle
x-x^{\star},\nabla\eta_{j}(x^{\star})\rangle=\frac{1}{t_{0}}+\langle
x-x^{\star},\xi^{\star}w^{\star}\rangle.$ (2.9)

The above equalities can hold only at $x=x^{\star}$ since $\eta_{i}$ and
$\eta_{j}$ are strictly convex. Now, for any $x\in\mathrm{DR}_{1/t_{0}}(i)$,
we have $\eta_{i}(x)\leq 1/t_{0}$. Thus, (2.8) implies that
$(\xi^{\star}-1)\langle x-x^{\star},w^{\star}\rangle\leq 0$, in which case, we
must have $\langle x-x^{\star},w^{\star}\rangle\geq 0$ for all
$x\in\mathrm{DR}_{1/t_{0}}(i)$, and therefore $\mathrm{DR}_{1/t_{0}}(i)\subset
H$. On the other hand, (2.9) implies that $\xi^{\star}\langle
x-x^{\star},w^{\star}\rangle\leq 0$, and since $0<\xi^{\star}<1$, the equality
holds if and only if $x=x^{\star}$. Therefore, $\mathrm{DR}_{1/t_{0}}(j)\cap
H=\\{x^{\star}\\}$, which proves the first part of the claim.

Next, observe that by continuity of the second derivatives of $\eta_{i}$ and
$\eta_{j}$, there must exist $r_{0},c>0$ such that for all $x$ with
$||x-x^{\star}||_{2}\leq r_{0}$,

$\displaystyle\eta_{i}(x)$ $\displaystyle\leq\eta_{i}(x^{\star})+\langle
x-x^{\star},\nabla\eta_{i}(x^{\star})\rangle+c\|x-x^{\star}\|_{2}^{2}$
$\displaystyle=\frac{1}{t_{0}}+\langle
x-x^{\star},(\xi^{\star}-1)w^{\star}\rangle+c\|x-x^{\star}\|_{2}^{2}$
$\displaystyle=\frac{1}{t_{0}}+c\|x-x^{\star}+(\xi^{\star}-1)w^{\star}/2c\|_{2}^{2}-\|(\xi^{\star}-1)w^{\star}\|_{2}^{2}/4c\leq\frac{1}{t_{0}},$

for
$\|x-x^{\star}+(\xi^{\star}-1)w^{\star}/2c\|_{2}\leq\|(\xi^{\star}-1)w^{\star}\|_{2}/2c$,
and

$\displaystyle\eta_{j}(x)$ $\displaystyle\leq\eta_{j}(x^{\star})+\langle
x-x^{\star},\nabla\eta_{j}(x^{\star})\rangle+c\|x-x^{\star}\|_{2}^{2}$
$\displaystyle=\frac{1}{t_{0}}+\langle
x-x^{\star},\xi^{\star}w^{\star}\rangle+c\|x-x^{\star}\|_{2}^{2}$
$\displaystyle=\frac{1}{t_{0}}+c||x-x^{\star}+\xi^{\star}w^{\star}/2c||_{2}^{2}-||\xi^{\star}w^{\star}||_{2}^{2}/4c\leq\frac{1}{t_{0}},$

for
$\|x-x^{\star}+\xi^{\star}w^{\star}/2c\|_{2}\leq\|\xi^{\star}w^{\star}\|_{2}/2c$.
In order to ensure that $\eta_{i}(x),\eta_{j}(x)\leq 1/t_{0}$, set
$r=\min(r_{0}/\|w^{\star}\|_{2},\xi^{\star}/c,(1-\xi^{\star})/c)/2$. The ball
of radius $r||w^{\star}||_{2}$ centered on $x^{\star}-rw^{\star}$ is
completely contained in $\mathrm{DR}_{1/t_{0}}(j)$ and the ball of radius
$r||w^{\star}||_{2}$ centered on $x^{\star}+rw^{\star}$ is completely
contained in $\mathrm{DR}_{1/t_{0}}(i)$, as desired.

Finally, for $t<t_{0}$, observe that
$B_{2}(\mathrm{DR}_{1/t_{0}}(i),\tilde{\varepsilon})\subset\mathrm{DR}_{1/t}(i)$
for some $\tilde{\varepsilon}>0$, and thus $x^{\star}$ is in the interior of
$\mathrm{DR}_{1/t}(i)$. Similarly, $x^{\star}$ is in the interior of
$\mathrm{DR}_{1/t}(j)$. Therefore, the intersection
$\mathrm{DR}_{1/t}(i)\cap\mathrm{DR}_{1/t}(j)$ has a non-empty interior. ∎

###  2.5. A necessary and sufficient condition for optimal recovery.

Finally, we combine the results of the above sections to give a condition for
when it is possible or impossible to separate degree profiles using
hyperplanes. Recall the notions of separating communities and confusing
communities from Definitions 2.6, 2.7.

######  Proposition 2.10.

Let $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$, $1\leq i<j\leq k$, and $w^{\star}$
be as in (2.6).

  1. (1)

If $t>1/\Delta_{+}(\theta_{i},\theta_{j})$, then there exists $\varepsilon>0$
such that $w^{\star}$ separates communities $i$ and $j$ with margin
$\varepsilon\log(n)$ with probability $1-o(1)$.

  2. (2)

Let $\mathcal{Z}\subset\mathbb{R}^{2k}$ be a linear subspace and
$w^{\star}\notin\mathcal{Z}$. There exists $\mu>0$ such that if
$t\Delta_{+}(\theta_{i},\theta_{j})<1+\mu$, then for every $m>0$ there exists
$\varepsilon>0$ such that the following holds with probability $1-o(1)$: For
every $z_{1},...,z_{m}\in\mathcal{Z}$ and
$\gamma_{1},...,\gamma_{m}\in\mathbb{R}$,
$[(z_{r})_{r=1}^{m},(\gamma_{r})_{r=1}^{m}]$ confuses communities $i$ and $j$
at level $\varepsilon\log(n)$.

###### Proof.

To prove the first part, define $t_{0}=1/\Delta_{+}(\theta_{i},\theta_{j})$,
so that $t_{0}<t$. By Lemma 2.9, there exists $x^{\star}$ such that
$\mathrm{DR}_{1/t_{0}}(i)\cap\mathrm{DR}_{1/t_{0}}(j)=\\{x^{\star}\\}$.
Additionally, the hyperplane $\\{x:\langle w^{\star},x-x^{\star}\rangle=0\\}$
separates $\mathrm{DR}_{1/t_{0}}(i)$ and $\mathrm{DR}_{1/t_{0}}(j)$. Note that
by (2.7), the hyperplane is equivalently written as $\\{x:\langle
w^{\star},x\rangle=0\\}$. Thus, for all $x\in\mathrm{DR}_{1/t_{0}}(i)$, we
have $\langle w^{\star},x\rangle>0$, while for all
$x\in\mathrm{DR}_{1/t_{0}}(j)$, we have $\langle w^{\star},x\rangle<0$.

Since $\mathrm{DR}_{1/t_{0}}(i)$ and $\mathrm{DR}_{1/t_{0}}(j)$ are both
closed, convex sets, $x^{\star}$ is neither in the interior of
$\mathrm{DR}_{1/t_{0}}(i)$ nor in the interior of $\mathrm{DR}_{1/t_{0}}(j)$.
Fix some $\delta\in(\frac{1}{t},\frac{1}{t_{0}})$. By Lemma 2.3, there exists
$\varepsilon^{\prime}>0$ such that
$B_{2}(\mathrm{DR}_{\delta}(i),\varepsilon^{\prime})\subset\mathrm{DR}_{1/t_{0}}(i)$.
Therefore, we can conclude that $x^{\star}\notin\mathrm{DR}_{\delta}(i)$.
Similarly $x^{\star}\notin\mathrm{DR}_{\delta}(j)$. Hence,
$\mathrm{DR}_{\delta}(i)\cap\mathrm{DR}_{\delta}(j)=\varnothing$. Also, since
$\mathrm{DR}_{1/t_{0}}(i)\backslash\\{x^{\star}\\}\subset\\{x:\langle
w^{\star},x\rangle>0\\}$, and
$\mathrm{DR}_{1/t_{0}}(j)\backslash\\{x^{\star}\\}\subset\\{x:\langle
w^{\star},x\rangle<0\\}$, we can conclude that the hyperplane $\\{x:\langle
w^{\star},x\rangle=0\\}$ separates $\mathrm{DR}_{\delta}(i)$ and
$\mathrm{DR}_{\delta}(j)$. Since dissonance ranges are closed by Lemma 2.3,
there exists $\varepsilon>0$ such that for any
$x^{\scriptscriptstyle(i)}\in\mathrm{DR}_{\delta}(i)$ and
$x^{\scriptscriptstyle(j)}\in\mathrm{DR}_{\delta}(j)$, we have

$\displaystyle\langle
w^{\star},x^{\scriptscriptstyle(i)}\rangle>\frac{\varepsilon}{2t}\quad\text{and}\quad\langle
w^{\star},x^{\scriptscriptstyle(j)}\rangle<-\frac{\varepsilon}{2t}.$

By Lemma 2.4, $d(u)/(t\log(n))\in\mathrm{DR}_{\delta}(i)$ for every $u\in
V_{i}$ with probability $1-o(1)$. Similarly,
$d(v)/(t\log(n))\in\mathrm{DR}_{\delta}(j)$ for every $v\in V_{j}$ with
probability $1-o(1)$. Therefore, with probability $1-o(1)$, we have that for
all $u\in V_{i}$ and $v\in V_{j}$,

$\displaystyle\langle
w^{\star},d(u)\rangle>\frac{\varepsilon}{2}\log(n)\quad\text{and}\quad\langle
w^{\star},d(v)\rangle<-\frac{\varepsilon}{2}\log(n).$

We conclude that $w^{\star}$ separates communities $i$ and $j$ with margin
$\varepsilon\log n$ with high probability.

Next, suppose that $w^{\star}\not\in\mathcal{Z}$. By Lemma 2.9, there exists
$r>0$ such that
$B_{2}(x^{\star}+rw^{\star},r\|w^{\star}\|_{2})\subset\mathrm{DR}_{1/{t_{0}}}(i)$
and
$B_{2}(x^{\star}-rw^{\star},r\|w^{\star}\|_{2})\subset\mathrm{DR}_{1/{t_{0}}}(j)$.
Next, let $w^{\prime}$ be the projection of $w^{\star}$ onto $\mathcal{Z}$.
The fact that $w^{\star}\notin\mathcal{Z}$ implies that
$w^{\star}-w^{\prime}\neq 0$ and $\|w^{\prime}\|_{2}<\|w^{\star}\|_{2}$. Let
$x^{\scriptscriptstyle(i)}=x^{\star}+r(w^{\star}-w^{\prime})$ and
$x^{\scriptscriptstyle(j)}=x^{\star}-r(w^{\star}-w^{\prime})$. We claim that
there exists a sufficiently small $r^{\prime}>0$ such that

$\displaystyle
B_{2}(x^{\scriptscriptstyle(i)},r^{\prime})\subset\mathrm{DR}_{1/t_{0}}(i)\quad\text{and}\quad
B_{2}(x^{\scriptscriptstyle(j)},r^{\prime})\subset\mathrm{DR}_{1/t_{0}}(j).$
(2.10)

Indeed, take $y\in B_{2}(x^{\scriptscriptstyle(i)},r^{\prime})$. Then,

$\displaystyle\|y-(x^{\star}+rw^{\star})\|_{2}\leq
r^{\prime}+r\|w^{\prime}\|_{2}.$

Since $\|w^{\prime}\|_{2}<\|w^{\star}\|_{2}$, we can pick $r^{\prime}$ such
that $\|y-(x^{\star}+rw^{\star})\|_{2}\leq r\|w^{\star}\|_{2}$, and therefore
$B_{2}(x^{\scriptscriptstyle(i)},r^{\prime})\subset
B_{2}(x^{\star}+rw^{\star},r\|w^{\star}\|_{2})\subset\mathrm{DR}_{1/t_{0}}(i)$.
The second conclusion of (2.10) follows similarly.

By (2.10), since $x^{(i)}$ and $x^{(j)}$ lie in interiors of
$\mathrm{DR}_{1/t_{0}}(i)$ and $\mathrm{DR}_{1/t_{0}}(j)$ respectively, there
exists $\mu>0$ such that, for any $t<t_{0}+\mu$, $x^{\scriptscriptstyle(i)}$
and $x^{\scriptscriptstyle(j)}$ also lie in interiors of
$\mathrm{DR}_{1/t}(i)$ and $\mathrm{DR}_{1/t}(j)$ respectively. Note that
$\mathrm{Proj}_{\mathcal{Z}}(x^{\scriptscriptstyle(i)})=\mathrm{Proj}_{\mathcal{Z}}(x^{\scriptscriptstyle(j)})$,
therefore the projections $\mathrm{DR}_{1/t}(i)$ and $\mathrm{DR}_{1/t}(j)$
onto $\mathcal{Z}$ overlap. The desired conclusion follows by Proposition 2.8.
∎

The above result yields a corollary which is useful in designing our
classification algorithm for $k\geq 3$ communities (Algorithm 6).

######  Corollary 2.11.

If $t>1/\Delta_{+}(\theta_{i},\theta_{j})$, then there exists $\varepsilon>0$
such that with probability $1-o(1)$

$\big{(}\log(P_{ri}),\log(1-P_{ri})\big{)}_{r\in[k]}\cdot d(v)>\max_{j\neq
i}\big{(}\log(P_{rj}),\log(1-P_{rj})\big{)}_{r\in[k]}\cdot
d(v)+\varepsilon\log(n)$

for all $i\in[k]$ and $v\in V_{i}$.

###### Proof.

Proposition 2.10 implies that with probability $1-o(1)$,

$\big{(}\log(P_{ri}),\log(1-P_{ri})\big{)}_{r\in[k]}\cdot
d(v)>\big{(}\log(P_{rj}),\log(1-P_{rj})\big{)}_{r\in[k]}\cdot
d(v)+\varepsilon\log(n)$

for every $i,j\in[k],i\neq j$ and $v\in V_{i}$ . The claim follows. ∎

##  3\. Achievability and Impossibility

Let us define the Maximum A Posteriori (MAP) estimator, which is the optimal
estimator of $\sigma_{0}$. Given a realization $G$ of the censored graph, the
MAP estimator outputs
$\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}\in\operatornamewithlimits{argmax}_{\sigma}\mathbb{P}(\sigma_{0}=\sigma\mid
G)$, choosing uniformly at random from the argmax set. In this section, we
start by proving Theorem 1.4, which is essentially equivalent to showing that
$\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}$ does not succeed in exact
recovery for $t<t_{c}$. Next we prove that, in the two community case, the
estimator $\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}$ always succeeds for
$t>t_{c}$. This shows the statistical achievability for the exact recovery
problem.

###  3.1. Impossibility

###### Proof of Theorem 1.4.

Recall that we have $t<t_{c}$ in this case where $t_{c}$ is given by (1.2).
Fix $i<j$ such that $t<t_{0}=1/\Delta_{+}(\theta_{i},\theta_{j})$. Using the
final conclusion of Lemma 2.9, we have that
$\mathrm{DR}_{1/t}(i)\cap\mathrm{DR}_{1/t}(j)$ contains an open ball. By Lemma
2.4 (1), there exists $d\in\mathbb{Z}_{+}^{2k}$ such that $d/(t\log
n)\in\mathrm{DR}_{1/t}(i)\cap\mathrm{DR}_{1/t}(j)$ and there are $L_{n}$ pairs
of vertices $\\{(u_{l},v_{l}):l\in[L_{n}]\\}$ with $u_{l}$’s from community 1,
$v_{l}$’s from community 2, and $L_{n}\to\infty$ such that
$d(u_{l})=d(v_{l})=d$ for all $l\in[L_{n}]$. Let
$\Sigma:=\operatornamewithlimits{argmax}_{\sigma}\mathbb{P}(\sigma_{0}=\sigma\mid
G)$. The above shows that $|\Sigma|\geq L_{n}$ with probability $1-o(1)$,
since swapping the labels of $u_{l}$ and $v_{l}$ leads to an equiprobable
assignment as they have the same degree profile. Now,
$\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}$ makes a uniform selection from
$\Sigma$. Thus, conditionally on $|\Sigma|\geq L_{n}$,
$\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}$ fails to recover community
labels of all the vertices in $\\{(u_{l},v_{l}):l\in[L_{n}]\\}$ with
probability at least $1-1/L_{n}$. Since $L_{n}\to\infty$ and $|\Sigma|\geq
L_{n}$ with probability $1-o(1)$, we have shown that
$\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}$ fails to achieve exact
recovery with probability $1-o(1)$. Since
$\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}$ fails, any other estimator
also fails in exact recovery, completing the proof. ∎

###  3.2. Statistical Achievability

######  Theorem 3.1.

Let $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$. If $t>t_{c}$, then

$\lim_{n\to\infty}\mathbb{P}(\hat{\sigma}_{\scriptscriptstyle\mathrm{MAP}}\text{
achieves exact recovery})=1.$

In order to prove Theorem 3.1, we require two concentration results. Given a
graph $\mathcal{G}=(V,E)$ and $W\subseteq V$, let $e(W)$ be the number of
edges with both endpoints in $W$.

######  Lemma 3.2 ([13, Corollary 2.3]).

Let $0\leq p_{n}\leq 0.99$ and let $\mathcal{G}$ be a sample from an Erdős-
Rényi random graph on vertex set $[n]$ and with edge probability $p_{n}$.
Then, with probability $1-o(1)$,

$\left|e(W)-\binom{|W|}{2}p_{n}\right|\leq O(\sqrt{np_{n}})|W|\quad\text{for
all }W\subseteq[n].$

######  Lemma 3.3.

Let $X_{1},X_{2},\dots,X_{n}$ be a sequence of independent discrete random
variables, whose support is a finite set $S$. Let $X=\sum_{i=1}^{n}X_{i}$ and
$Y=\sum_{i=1}^{n}|X_{i}|$. Let $L=\max\\{|x|:x\in S\\}$. Then for any
$\delta\in(0,1)$,

$\mathbb{P}\left(\left|X-\mathbb{E}\left[X\right]\right|\geq\delta|\mathbb{E}\left[X\right]|\right)\leq\exp\bigg{(}2-C\delta^{2}\frac{\left(\mathbb{E}[X]\right)^{2}}{L\mathbb{E}[Y]}\bigg{)},$

where $C>0$ is a universal constant.

The proof of Lemma 3.3 follows directly from [15, Theorem 1.3]. See Appendix B
for details. We will also need the following definitions in the proof of
Theorem 3.1.

######  Definition 3.4 (Permissible relabeling).

A permutation $\pi:[k]\to[k]$ is called a _permissible relabeling_ if
$\rho(i)=\rho(\pi(i))$ for all $i\in[k]$ and $P_{ij}=P_{\pi(i),\pi(j)}$ for
all $i,j\in[k]$. Let $\mathcal{P}(\rho,P)$ denote the set of permissible
relabelings.

######  Definition 3.5 (Discrepancy).

Given two assignments $\sigma,\sigma^{\prime}:[n]\to[k]$, their _discrepancy_
$\textsc{Disc}(\sigma,\sigma^{\prime})$ is defined as

$\min_{\pi\in\mathcal{P}(\rho,P)}\left\\{\mathrm{d}_{\scriptscriptstyle
H}((\pi\circ\sigma),\sigma^{\prime})\right\\},$

where $\mathrm{d}_{\scriptscriptstyle H}(\cdot,\cdot)$ denotes the Hamming
distance.

Note that, if an estimator $\hat{\sigma}$ satisfies
$\textsc{Disc}(\hat{\sigma},\sigma_{0})=0$ with high probability, then
$\hat{\sigma}$ achieves exact recovery. Next, let $E_{+}$ and $E_{-}$
respectively denote the sets of present and absent edges of $G$. For a
community assignment $\sigma$, communities $i,j\in[k]$ and $\Box\in\\{+,-\\}$,
define

$\displaystyle S^{ij}_{\scriptscriptstyle\Box}(G,\sigma)=\\{e=\\{u,v\\}\in
E_{\scriptscriptstyle\Box}:\\{\sigma(u),\sigma(v)\\}=\\{i,j\\}\\}\quad\text{and}\quad
s^{ij}_{\scriptscriptstyle\Box}(G,\sigma)=|S^{ij}_{\scriptscriptstyle\Box}(G,\sigma)|.$

For example, $s_{-}^{11}(G,\sigma)$ is the number of absent edges with both
endpoints in community 1 according to $\sigma$. Define

$\begin{split}z(G,\sigma)=2\sum_{i,j\in[k]:j\geq
i}\big{[}s^{ij}_{+}(G,\sigma)\log
P_{ij}+s^{ij}_{-}(G,\sigma)\log(1-P_{ij})\big{]}.\end{split}$ (3.1)

The idea is to show that the maximizer of $z(G,\sigma)$ yields a configuration
$\sigma$ with zero discrepancy. We state this in the following two lemmas
which deal with low and high values of discrepancies separately.

######  Lemma 3.6.

There exists $c\in(0,1)$ such that with high probability

$\begin{split}z(G,\sigma)<z(G,\sigma_{0})\quad\text{for all }\sigma\text{ such
that }0<\textsc{Disc}(\sigma,\sigma_{0})\leq cn.\end{split}$ (3.2)

For the high discrepancy case, we need to restrict the range of $\sigma$. To
that end, for any $\eta>0$, define

$\begin{split}{defn-sigma-
range}\Sigma_{0}(\eta):=\\{\sigma:[n]\mapsto[k]:|\\{v:\sigma(v)=i\\}|\in((\rho_{i}-\eta)n,(\rho_{i}+\eta)n),\
\forall i\in[k]\\}.\end{split}$ (3.3)

######  Lemma 3.7.

Fix any $c\in(0,1]$. There exists an $\eta>0$ such that with high probability

$\begin{split}z(G,\sigma)<z(G,\sigma_{0})\quad\text{for all
}\sigma\in\Sigma_{0}(\eta)\text{ such that
}\textsc{Disc}(\sigma,\sigma_{0})\geq cn.\end{split}$ (3.4)

###### Proof of Theorem 3.1.

Fix $c$ such that both the conclusions of Lemmas 3.6 and 3.7 hold. Let $\eta$
be picked according to Lemma 3.7. Rather than analyzing the MAP estimator, we
will analyze the estimator

$\overline{\sigma}=\operatornamewithlimits{argmax}_{\sigma\in\Sigma_{0}(\eta)}\\{z(G,\sigma)\\}.$

Lemmas 3.6 and 3.7 yield $\textsc{Disc}(\overline{\sigma},\sigma_{0})=0$, and
therefore $\overline{\sigma}$ succeeds in exact recovery, with high
probability. Since the MAP estimator is optimal, this also implies that the
MAP estimator succeeds in exact recovery with high probability. ∎

###### Proof of Lemma 3.6.

Let $\textsc{Disc}(\sigma,\sigma_{0})=\delta n$ for some $\delta>0$ (to be
chosen later). Let $\pi\in\mathcal{P}(\rho,P)$ be such that
$\mathrm{d}_{\scriptscriptstyle H}(\sigma\circ\pi,\sigma_{0})=\delta n$.
However, since $z(G,\sigma)=z(G,\sigma\circ\pi)$ for any
$\pi\in\mathcal{P}(\rho,P)$, we can without loss of generality assume that
$\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0})=\delta n$. Let us fix
$\Box\in\\{+,-\\}$. To prove (3.2), we start by analyzing
$s_{\scriptscriptstyle\Box}^{rj}(G,\sigma)-s_{\scriptscriptstyle\Box}^{rj}(G,\sigma_{0})$
with $r,j\in[k]$. Fix $r\neq j$. We decompose

$\begin{split}&s_{\scriptscriptstyle\Box}^{rj}(G,\sigma)-s_{\scriptscriptstyle\Box}^{rj}(G,\sigma_{0})\\\
&=\sum_{\\{u,v\\}\in
E_{\scriptscriptstyle\Box}}\mathbbm{1}_{\\{\\{\sigma(u),\sigma(v)\\}=\\{r,j\\},\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\\{r,i\\},i\neq
j\\}}+\sum_{\\{u,v\\}\in
E_{\scriptscriptstyle\Box}}\mathbbm{1}_{\\{\\{\sigma(u),\sigma(v)\\}=\\{r,j\\},\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\\{i,j\\},i\neq
r\\}}\\\ &\quad+\sum_{\\{u,v\\}\in
E_{\scriptscriptstyle\Box}}\mathbbm{1}_{\\{\\{\sigma(u),\sigma(v)\\}=\\{r,j\\},\\{\sigma(u),\sigma(v)\\}\cap\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\varnothing\\}}-\sum_{\\{u,v\\}\in
E_{\scriptscriptstyle\Box}}\mathbbm{1}_{\\{\\{\sigma(u),\sigma(v)\\}=\\{r,i\\},i\neq
j,\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\\{r,j\\}\\}}\\\ &\quad-\sum_{\\{u,v\\}\in
E_{\scriptscriptstyle\Box}}\mathbbm{1}_{\\{\\{\sigma(u),\sigma(v)\\}=\\{i,j\\},i\neq
r,\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\\{r,j\\}\\}}-\sum_{\\{u,v\\}\in
E_{\scriptscriptstyle\Box}}\mathbbm{1}_{\\{\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\\{r,j\\},\\{\sigma(u),\sigma(v)\\}\cap\\{\sigma_{0}(u),\sigma_{0}(v)\\}=\varnothing\\}}.\end{split}$
(3.5)

To analyze (LABEL:decomp-difference), denote the six terms above by (I), (II),
…, (VI) respectively.

Let $H_{\scriptscriptstyle\Box}(\sigma)$ be the graph on
$\\{v:\sigma(v)\neq\sigma_{0}(v)\\}$ where $\\{u,v\\}$ is an edge of
$H_{\scriptscriptstyle\Box}(\sigma)$ if and only if $\\{u,v\\}\in
E_{\scriptscriptstyle\Box}$. Let $e(H_{\scriptscriptstyle\Box}(\sigma))$
denote the number of edges in $H_{\scriptscriptstyle\Box}(\sigma)$. We will
show that

$\begin{split}\bigg{|}\text{(I)}-\sum_{i\in[k]\setminus\\{j\\}}\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)\bigg{|}\leq
3k\cdot e(H_{\scriptscriptstyle\Box}(\sigma)).\end{split}$ (3.6)

To compute (I), fix $i,r,j$, $r\neq j$ $i\neq j$, and consider two cases:

Case I: $i,j,r$ are distinct. Denote this contribution as (Ia). There are two
subcases. Suppose that the $r$-labeled vertex under $\sigma,\sigma_{0}$ is the
same vertex. Think of $u$ being such that $\sigma(u)=\sigma_{0}(u)=r$. The
number of such edges is
$\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)-\text{Err}_{\scriptscriptstyle\text{(I)}}$,
where $\text{Err}_{\scriptscriptstyle\text{(I)}}$ is the number of
$\\{u,v\\}\in E_{\scriptscriptstyle\Box}$ such that $\sigma(u)\neq
r,\sigma_{0}(u)=r,\sigma(v)=j,\sigma_{0}(v)=i$. To see this, note that the
summation
$\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)$ counts
all edges (present or absent depending on $\Box=+$ or $\Box=-$) from
$\\{v:\sigma(v)=j,\sigma_{0}(v)=i\\}$ to $\\{u:\sigma_{0}(u)=r\\}$. However,
this causes an over-counting because these edges may be incident to $u$’s with
$\sigma(u)\neq r$, resulting in the substraction of
$\text{Err}_{\scriptscriptstyle\text{(I)}}$. Note that
$\text{Err}_{\scriptscriptstyle\text{(I)}}$ is at most
$e(H_{\scriptscriptstyle\Box}(\sigma))$. Next, consider the second subcase,
where the $r$-labeled vertex under $\sigma,\sigma_{0}$ are different. Since
$i,j,r$ are distinct, such edges will have both endpoints in
$\\{v:\sigma(v)\neq\sigma_{0}(v)\\}$. Therefore,

$\begin{split}{distinct-
contributions}\bigg{|}\text{(Ia)}-\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)\bigg{|}\leq
2e(H_{\scriptscriptstyle\Box}(\sigma)).\end{split}$ (3.7)

Case II: $i=r$. Denote this contribution as (Ib). Since $r\neq j$, we only
need to consider the case where one of the endpoints is labeled $r$ by both
$\sigma,\sigma_{0}$. An argument identical to the first part of Case I shows

$\begin{split}{identical-
contributions}\bigg{|}\text{(Ia)}-\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)\bigg{|}\leq
e(H_{\scriptscriptstyle\Box}(\sigma)).\end{split}$ (3.8)

Combining (LABEL:distinct-contributions) and (LABEL:identical-contributions),
(3.6) follows immediately. Bounds similar to (3.6) also hold for Terms (II),
(IV), and (V). Term (III) is easily bounded by
$e(H_{\scriptscriptstyle\Box}(\sigma))$. Finally, we simply drop Term (VI) for
upper bounding (3.6).

For $r=j$, we get a similar decomposition as (LABEL:decomp-difference), except
that the second and fifth terms would be omitted. For each of the terms, we
can also prove (3.6). In particular,

$\left|\text{(I)}-\sum_{i\in[k]\setminus\\{j\\}}\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)\right|\leq(k-1)\cdot
e(H_{\scriptscriptstyle\Box}(\sigma))\leq 3k\cdot
e(H_{\scriptscriptstyle\Box}(\sigma)).$

Next, we need to bound $e(H_{\scriptscriptstyle\Box}(\sigma))$. Note that the
number of vertices in $H_{\scriptscriptstyle\Box}(\sigma)$ is
$\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0})$, where
$\mathrm{d}_{\scriptscriptstyle H}(\cdot,\cdot)$ denotes the Hamming distance.
Letting $\tau=\max_{a,b\in[k]}\max\\{P_{ab},1-P_{ab}\\}$, we see that there is
a coupling such that, with probability 1, $H_{\scriptscriptstyle\Box}(\sigma)$
is a subgraph of an Erdős-Rényi random graph on vertex set $[n]$ and edge
probability $\frac{\tau t\log n}{n}$. Applying Lemma 3.2, we obtain that with
probability $1-o(1)$

$\begin{split}{bound-Err-I}e(H_{\scriptscriptstyle\Box}(\sigma))\leq\frac{\tau
t\log n}{2n}\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0})^{2}+O(\sqrt{\log n})\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0})\quad\text{for all }\sigma\in[k]^{n}.\end{split}$ (3.9)

Combining (3.6) and (LABEL:bound-Err-I), we get an estimate for (I) in
(LABEL:decomp-difference). Similar estimates for (II), (IV), (V) can be
deduced using an identical argument. The term (III) can be directly bounded by
$e(H_{\scriptscriptstyle\Box}(\sigma))$ as well and (VI) can be dropped.
Therefore, (LABEL:decomp-difference) yields that with probability $1-o(1)$

$\begin{split}s_{\scriptscriptstyle\Box}^{rj}(G,\sigma)-s_{\scriptscriptstyle\Box}^{rj}(G,\sigma_{0})&\leq\sum_{i:i\neq
j}\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{{\scriptscriptstyle\Box}r}(v)+\sum_{i:i\neq
r}\sum_{u:\sigma(u)=r,\sigma_{0}(u)=i}d_{{\scriptscriptstyle\Box}j}(u)\\\
&\qquad-\sum_{i:i\neq
j}\sum_{v:\sigma(v)=i,\sigma_{0}(v)=j}d_{{\scriptscriptstyle\Box}r}(v)-\sum_{i:i\neq
r}\sum_{u:\sigma(u)=i,\sigma_{0}(u)=r}d_{{\scriptscriptstyle\Box}j}(u)\\\
&\qquad\quad+\frac{8k\tau t\log n}{n}\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0})^{2}+O(\sqrt{\log n})\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0}).\end{split}$ (3.10)

For $r=j$, a bound identical to (3.10) holds after omitting the second and the
fourth terms. Next, by Proposition 2.10 1, there exists $\varepsilon>0$ such
that for all $i,j\in[k]$ and $i>j$, with high probability,

$\begin{split}\langle
w^{\star}_{ij},d(v)\rangle=\sum_{r\in[k]}d_{+r}(v)\log\frac{P_{ri}}{P_{rj}}+d_{-r}(v)\log\frac{1-P_{ri}}{1-P_{rj}}\
\ \begin{cases}\geq\varepsilon\log n,\quad&\forall v:\sigma_{0}(v)=j\\\
\leq-\varepsilon\log n,\quad&\forall v:\sigma_{0}(v)=i\end{cases}\end{split}$
(3.11)

Let
$L=\sum_{i,j\in[k]}\sum_{r\in[k]}\big{|}\log\frac{P_{ri}}{P_{rj}}\big{|}+\big{|}\log\frac{1-P_{ri}}{1-P_{rj}}\big{|}$.
Thus, (3.10) yields

$\displaystyle z(G,\sigma)-z(G,\sigma_{0})$ $\displaystyle\leq
4\sum_{i,j\in[k]:i>j}\sum_{r\in[k]}\bigg{[}\bigg{(}\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{+r}(v)-\sum_{v:\sigma(v)=i,\sigma_{0}(v)=j}d_{+r}(v)\bigg{)}\log\frac{P_{ri}}{P_{rj}}$
$\displaystyle\quad+\bigg{(}\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}d_{-r}(v)-\sum_{v:\sigma(v)=i,\sigma_{0}(v)=j}d_{-r}(v)\bigg{)}\log\frac{1-P_{ri}}{1-P_{rj}}\bigg{]}$
$\displaystyle\qquad+\frac{8k^{3}L\tau t\log
n}{n}\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0})^{2}+O(\sqrt{\log
n})\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0})$
$\displaystyle=4\sum_{i,j\in[k]:i>j}\bigg{[}\sum_{v:\sigma(v)=j,\sigma_{0}(v)=i}\langle
w^{\star}_{ij},d(v)\rangle-\sum_{v:\sigma(v)=i,\sigma_{0}(v)=j}\langle
w^{\star}_{ij},d(v)\rangle\bigg{]}$ $\displaystyle\qquad+\frac{8k^{3}L\tau
t\log n}{n}\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0})^{2}+O(\sqrt{\log n})\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0})$ $\displaystyle\leq-4\mathrm{d}_{\scriptscriptstyle
H}(\sigma,\sigma_{0})\varepsilon\log n+\frac{8k^{3}L\tau t\log
n}{n}\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0})^{2}+O(\sqrt{\log
n})\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0}).$

Thus, for any $\delta\leq\frac{\varepsilon}{3k^{3}L\tau t}$, we can ensure
that $z(G,\sigma)-z(G,\sigma_{0})<0$ for all $\sigma$ with
$\mathrm{d}_{\scriptscriptstyle H}(\sigma,\sigma_{0})=\delta n$ with high
probability. Thus the proof follows by taking
$c=\frac{\varepsilon}{2k^{3}L\tau t}$. ∎

###### Proof of Lemma 3.7.

Fix $c\in(0,1]$. Define,

$\displaystyle\eta=\frac{1}{6}\left(\min\\{|\rho_{i}-\rho_{j}|:\rho_{i}\neq\rho_{j},i,j\in[k]\\}\land\min\\{\rho_{i}:i\in[k]\\}\right)\wedge\frac{c}{4k}.$
(3.12)

Throughout, we condition on the event that $\sigma_{0}\in\Sigma_{0}(\eta)$,
where $\Sigma_{0}(\eta)$ is defined in (LABEL:defn-sigma-range). Due to (1.4),
this conditioning event holds with high probablity. Fix an assignment
$\sigma\in\Sigma_{0}(\eta)$ satisfying $\textsc{Disc}(\sigma,\sigma_{0})\geq
cn$. The idea is to show that
$\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]\leq-Cn\log n$, and use the
concentration bound in Lemma 3.3 to conclude that (3.2) holds.

We first compute the expected difference
$\mathbb{E}[z(G,\sigma)-z(G,\sigma_{0})]$. Let
$V_{ij}:=\\{v:\sigma_{0}(v)=i,\sigma(v)=j\\}$ and $\nu_{ij}=|V_{ij}|$. Fix
$i,j,a,b$ such that $a\geq i$, $j\geq b$ and we also have $i\neq j$ or $a\neq
b$. Thus, $V_{ij}\cap V_{ab}=\varnothing$. The expected number of present
edges between $V_{ij}$ and $V_{ab}$ is $\nu_{ij}\nu_{ab}\times\alpha P_{ia}$,
where $\alpha=\frac{t\log n}{n}$. The contribution of these edges to
$\mathbb{E}[z(G,\sigma)-z(G,\sigma_{0})]$ is

$2\nu_{ij}\nu_{ab}\times\alpha
P_{ia}\times\left(\log(P_{jb})-\log(P_{ia})\right)=2\nu_{ij}\nu_{ab}\times\alpha\times
P_{ia}\log\frac{P_{jb}}{P_{ia}}.$

Similarly, the contribution from absent edges is

$2\nu_{ij}\nu_{ab}\times\alpha\times(1-P_{ia})\log\frac{1-P_{jb}}{1-P_{ia}}.$

Summing over all contributions, and noting that the contribution for the terms
with $i=j$ and $a=b$ is zero due to the presence of $\log$ terms, we obtain

$\displaystyle\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]$
$\displaystyle=2\alpha\sum_{i,j,a,b\in[k]:a\geq i,b\geq
j}\nu_{ij}\nu_{ab}\bigg{(}P_{ia}\log\frac{P_{jb}}{P_{ia}}+(1-P_{ia})\log\frac{1-P_{jb}}{1-P_{ia}}\bigg{)}$
$\displaystyle=-2\alpha\sum_{i,j,a,b\in[k]:a\geq i,b\geq
j}\nu_{ij}\nu_{ab}D_{\scriptscriptstyle\mathrm{KL}}\left(P_{ia},P_{jb}\right),$

where $D_{\scriptscriptstyle\mathrm{KL}}(\cdot,\cdot)$ denotes the
Kullback?Leibler divergence. Our goal is to upper-bound the expectation. Note
that all terms are nonpositive, so it suffices to bound a subset of the terms.
We treat two disjoint cases separately.

Case 1: For all $i$, there is at most one $j\in[k]$ such that
$\nu_{ij}\geq\frac{\eta n}{k}$. Fixing $i$, the pigeonhole principle then
implies that there is exactly one such $j$. But since
$\sum_{l}\nu_{il}\geq(\rho_{i}-\eta)n$, we know that

$\nu_{ij}\geq\rho_{i}n-(k-1)\frac{\eta n}{k}-\eta
n>\left(\rho_{i}-2\eta\right)n.$

Next we claim that we cannot have $\nu_{ij}>(\rho_{i}-2\eta)n$ and
$\nu_{i^{\prime}j}>(\rho_{i}-2\eta)n$ with $i\neq i^{\prime}$. Supposing
otherwise, we would have

$2(\rho_{l}-2\eta)n\leq\sum_{i}\nu_{il}\leq(\rho_{l}+\eta)n,$

which implies $\rho_{l}\leq 5\eta$. However, $\eta\leq\frac{\rho_{l}}{6}$ by
definition (3.12), and we have arrived at a contradiction. Hence, there exists
a unique permutation $\pi:[k]\to[k]$ such that
$\nu_{i,\pi(i)}>\left(\rho_{i}-2\eta\right)n$ for all $i\in[k]$.

Next, we argue that $\pi$ is not permissible. Indeed, if $\pi$ were
permissible, then

$\displaystyle\textsc{Disc}(\sigma,\sigma_{0})\leq\mathrm{d}_{\scriptscriptstyle
H}(\pi\circ\sigma,\sigma_{0})=\sum_{i}\sum_{j:\pi(j)\neq
i}\nu_{ij}=\sum_{i}\bigg{(}\sum_{j}\nu_{ij}-\nu_{i,\pi(i)}\bigg{)}\leq k\times
3\eta n<cn,$

where the second-to-last step uses $\sum_{j}\nu_{ij}\leq(\rho_{i}+\eta)n$ and
$\nu_{i,\pi(i)}>\left(\rho_{i}-2\eta\right)n$ and the last step follows from
(3.12). This leads to a contradiction and thus $\pi$ is not permissible.

Next, observe that

$\displaystyle\sum_{i,a}\nu_{i\pi(i)}\nu_{a\pi(a)}D_{\scriptscriptstyle\mathrm{KL}}\left(P_{ia},P_{\pi(i),\pi(a)}\right)$
$\displaystyle\geq
n^{2}\sum_{i,a}(\rho_{\pi(i)}-2\eta)(\rho_{\pi(a)}-2\eta)D_{\scriptscriptstyle\mathrm{KL}}\left(P_{ia},P_{\pi(i),\pi(a)}\right)$
$\displaystyle=n^{2}\sum_{i,a}(\rho_{i}-2\eta)(\rho_{a}-2\eta)D_{\scriptscriptstyle\mathrm{KL}}\left(P_{\pi(i),\pi(a)},P_{ia}\right)$
$\displaystyle\geq\frac{4}{9}n^{2}\sum_{i,a}\rho_{i}\rho_{a}\cdot
D_{\scriptscriptstyle\mathrm{KL}}\left(P_{\pi(i),\pi(a)},P_{ia}\right).$

Since $\pi(\cdot)$ is not permissible, there must exist $(i,a)$ for which
$P_{ia}\neq P_{\pi(i),\pi(a)}$, and thus the above term is at most
$C^{\prime}n^{2}$ for some constant $C^{\prime}>0$. Hence,
$\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]\leq-\frac{8\alpha
C^{\prime}n^{2}}{9}$.

Case 2: There exist $i,j,j^{\prime}$ with $j\neq j^{\prime}$ such that
$\nu_{ij},\nu_{ij^{\prime}}\geq\frac{\eta n}{k}$. Let $b\in[k]$ be such that
$P_{jb}\neq P_{j^{\prime}b}$. If no such $b$ exists, then communities $j$ and
$j^{\prime}$ are indistinguishable. In that case, $t_{c}=\infty$ and exact
recovery will be impossible for any fixed $t$. Let $a\in[k]$ be such that
$\nu_{ab}\geq\frac{n}{k}$, which is guaranteed to exist by the pigeonhole
principle. Then either

$P_{ia}\neq P_{jb}\text{ or }P_{ia}\neq P_{j^{\prime}b}.$

Therefore,

$\displaystyle-\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]$
$\displaystyle\geq 2\alpha\sum_{i,j,a,b\in[k]:a\geq i,b\geq
j}\nu_{ij}\nu_{ab}D_{\scriptscriptstyle\mathrm{KL}}\left(P_{ia},P_{jb}\right)$
$\displaystyle\geq\alpha\frac{\eta
n}{k}\cdot\frac{n}{k}\left(D_{\scriptscriptstyle\mathrm{KL}}\left(P_{ia},P_{jb}\right)+D_{\scriptscriptstyle\mathrm{KL}}\left(P_{ia},P_{j^{\prime}b}\right)\right)\geq\alpha
C^{\prime}n^{2}.$

Summarizing both cases, we have shown that there exists a constant
$C^{\prime\prime}>0$ such that

$\begin{split}\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]\leq-\alpha
C^{\prime\prime}n^{2}=-tC^{\prime\prime}n\log n.\end{split}$ (3.13)

We next apply Lemma 3.3 to establish concentration of the difference
$z(G,\sigma)-z(G,\sigma_{0})$. Letting $\mathscr{P},\mathscr{A}$ denote the
set of present and absent edges respectively, note that

$\displaystyle X$
$\displaystyle:=\frac{1}{2}\mathbb{E}[z(G,\sigma)-z(G,\sigma_{0})]$
$\displaystyle=\sum_{1\leq u<v\leq
n}\bigg{[}\mathbbm{1}_{\\{\\{u,v\\}\in\mathscr{P}\\}}\log\frac{P_{\sigma(u),\sigma(v)}}{P_{\sigma_{0}(u),\sigma_{0}(v)}}+\mathbbm{1}_{\\{\\{u,v\\}\in\mathscr{A}\\}}\log\frac{1-P_{\sigma(u),\sigma(v)}}{1-P_{\sigma_{0}(u),\sigma_{0}(v)}}\bigg{]}.$

Denote each term in the summation by $X_{uv}$. Then $X=\sum_{1\leq u<v\leq
n}X_{uv}$ is a sum of independent random variables conditionally on
$\sigma_{0}$, for any $\sigma\in[k]^{n}$. Let $Y=\sum_{1\leq u<v\leq
n}|X_{uv}|$. Then for any $\delta\in(0,1)$,

$\displaystyle\mathbb{P}\left(z(G,\sigma)-z(G,\sigma_{0})\geq(1-\delta)\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]\right)$
$\displaystyle\leq\exp\bigg{(}2-C\delta^{2}\frac{\left(\mathbb{E}[X]\right)^{2}}{L\mathbb{E}[Y]}\bigg{)},$

where $C$ is the universal constant from Lemma 3.3, and $L>0$ is a constant
depending on $P,t$. To upper-bound $\mathbb{E}[Y]$, note that for any $1\leq
u<v\leq n$

$\displaystyle\frac{\mathbb{E}\left[|X_{uv}|\right]}{|\mathbb{E}\left[X_{uv}\right]|}$
$\displaystyle=\frac{P_{\sigma_{0}(u),\sigma_{0}(v)}\left|\log\frac{P_{\sigma(u),\sigma(v)}}{P_{\sigma_{0}(u),\sigma_{0}(v)}}\right|+\left(1-P_{\sigma_{0}(u),\sigma_{0}(v)}\right)\left|\log\frac{1-P_{\sigma(u),\sigma(v)}}{1-P_{\sigma_{0}(u),\sigma_{0}(v)}}\right|}{\left|P_{\sigma_{0}(u),\sigma_{0}(v)}\log\frac{P_{\sigma(u),\sigma(v)}}{P_{\sigma_{0}(u),\sigma_{0}(v)}}+\left(1-P_{\sigma_{0}(u),\sigma_{0}(v)}\right)\log\frac{1-P_{\sigma(u),\sigma(v)}}{1-P_{\sigma_{0}(u),\sigma_{0}(v)}}\right|}.$

Taking a maximum on the right hand side over $\sigma\in[k]^{n}$, there exists
a constant $C^{(1)}>0$ depending on $P$ such that
$\mathbb{E}\left[|X_{uv}|\right]\leq C^{(1)}|\mathbb{E}\left[X_{uv}\right]|$
for all $u,v$. It follows that

$\displaystyle\mathbb{E}[Y]$ $\displaystyle\leq C^{(1)}\sum_{1\leq u<v\leq
n}\left|\mathbb{E}[X_{uv}]\right|\leq C^{(2)}n\log n,$

for some constant $C^{(2)}>0$. Also, by (3.13),
$|\mathbb{E}[X]|\geq\frac{tC^{\prime\prime}}{2}n\log n$. Therefore there
exists a constant $\tilde{C}>0$ such that

$\displaystyle\mathbb{P}\left(z(G,\sigma)-z(G,\sigma_{0})\geq(1-\delta)\mathbb{E}\left[z(G,\sigma)-z(G,\sigma_{0})\right]\right)$
$\displaystyle\leq\exp\big{(}2-\tilde{C}\delta^{2}n\log n\big{)}.$

Taking $\delta=\frac{1}{2}$ and using (3.13), we conclude that
$z(G,\sigma)-z(G,\sigma_{0})<0$ with probability at least
$1-\exp(2-\frac{\tilde{C}}{4}n\log n)$. Finally, we take a union bound over
the set $\\{\sigma:\textsc{Disc}(\sigma,\sigma_{0})\geq cn\\}$, whose
cardinality is at most $k^{n}$. Since $\exp(2-\frac{\tilde{C}}{4}n\log
n)k^{n}=o(1)$, we conclude that (3.4) holds with high probability.

∎

##  4\. Entrywise eigenvector bounds

Our analysis of spectral algorithms relies on precise entrywise control of
eigenvectors of adjacency matrices, which is guaranteed by the following
result. As before, on a fixed value of $\sigma_{0}$ satisfying (1.4) with
$\varepsilon=n^{-1/3}$.

######  Theorem 4.1.

Fix $k\in\mathbb{N}$, $\rho\in(0,1)^{k}$ such that $\sum_{i=1}^{k}\rho_{i}=1$,
a symmetric matrix $P\in(0,1)^{k\times k}$, and let
$G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$. Define $A=A(G,y)$ for some constant
$y>0$, and let $A^{\star}=\mathbb{E}[A]$. Let $(\lambda_{i},u_{i})$ and
$(\lambda_{i}^{\star},u_{i}^{\star})$ denote the $i$-th largest eigenpair of
$A$ and $A^{\star}$ respectively. Let $r,s$ be integers satisfying $1\leq
r\leq k$ and $0\leq s\leq k-r$. Let
$U=(u_{s+1},\dots,u_{s+r})\in\mathbb{R}^{n\times r}$,
$U^{\star}=(u^{\star}_{s+1},\dots,u^{\star}_{s+r})\in\mathbb{R}^{n\times r}$,
and
$\Lambda^{\star}=\text{diag}(\lambda^{\star}_{s+1},\dots,\lambda^{\star}_{s+r})\in\mathbb{R}^{r\times
r}$. Suppose that

$\begin{split}\Delta^{\star}:=(\lambda^{\star}_{s}-\lambda^{\star}_{s+1})\land(\lambda^{\star}_{s+r}-\lambda^{\star}_{s+r+1})\land\min_{i\in[r]}\left|\lambda^{\star}_{s+i}\right|>0,\end{split}$
(4.1)

where $\lambda_{0}^{\star}=\infty$ and $\lambda_{k+1}^{\star}=-\infty$. Then,
with probability at least $1-O(n^{-3})$,

$\inf_{O\in\mathcal{O}^{r\times r}}\left\|UO-
AU^{\star}\left(\Lambda^{\star}\right)^{-1}\right\|_{2\to\infty}\leq\frac{C}{\log\log(n)\sqrt{n}},$
(4.2)

for some $C=C(\rho,P,t,y)>0$, where $\mathcal{O}^{r\times r}$ denotes the set
of $r\times r$ orthogonal matrices.

######  Corollary 4.2.

Recall the notation from Theorem 4.1. If all eigenvalues of $A^{\star}$ are
distinct and nonzero, then with probability $1-O(n^{-3})$, for all $i\in[k]$,

$\min_{s\in\\{\pm
1\\}}\left\|su_{i}-\frac{Au_{i}^{\star}}{\lambda_{i}^{\star}}\right\|_{\infty}\leq\frac{C}{\log\log(n)\sqrt{n}},$

for some $C=C(\rho,P,t,y)>0$.

The proof of Theorem 4.1 relies on an entrywise eigenvector perturbation bound
derived in [1]. We provide the statement for a general random matrix $A$ here
for completeness, and will verify these general conditions subsequently for
$G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$. Also, we reuse the notation from
Theorem 4.1. Let $H=U^{T}U^{\star}$, with singular value decomposition given
by $H=\bar{W}\bar{\Sigma}\bar{V}^{T}$. Let
$\text{sgn}(H)=\bar{W}\bar{V}^{T}\in\mathbb{R}^{r\times r}$, which is an
orthonormal matrix, called the _matrix sign function_ [10]. Given this setup,
[1, Theorem 2.1 Part (2)] gives the following result.

######  Theorem 4.3 (Theorem 2.1 Part (2), [1]).

Let $A$ be a random matrix as described above. Suppose that the following
assumptions are satisfied, for some $\gamma>0$ and
$\varphi(x):\mathbb{R}_{+}\to\mathbb{R}_{+}$.

  1. (1)

(Properties of $\varphi$) $\varphi(x)$ is continuous and non-decreasing in
$\mathbb{R}_{+}$, $\varphi(0)=0$, and $\frac{\varphi(x)}{x}$ is non-increasing
in $\mathbb{R}_{+}$.

  2. (2)

(Incoherence) $\|A^{\star}\|_{2\to\infty}\leq\gamma\Delta^{\star}$, where
$\Delta^{\star}$ is defined in (4.1).

  3. (3)

(Row- and column-wise independence) For any $m\in[n]$, the entries in the
$m$th row and column are independent with others, i.e. $\\{A_{ij}:i=m\text{ or
}j=m\\}$ are independent of $\\{A_{ij}:i\neq m,j\neq m\\}$.

  4. (4)

(Spectral norm concentration) Define
$\kappa=\frac{1}{\Delta^{\star}}\max_{i\in[r]}|\lambda^{\star}_{s+i}|$, and
suppose $32\kappa\max\\{\gamma,\varphi(\gamma)\\}\leq 1$. Then, for some
$\delta_{0}\in(0,1)$,

$\mathbb{P}\left(\|A-A^{\star}\|_{2}\leq\gamma\Delta^{\star}\right)\geq
1-\delta_{0}.$

  5. (5)

(Row concentration) There exists $\delta_{1}\in(0,1)$ such that for any
$m\in[n]$ and $W\in\mathbb{R}^{n\times r}$,

$\mathbb{P}\left(\left\|(A-A^{\star})_{m,\cdot}W\right\|_{2}\leq\Delta^{\star}\|W\|_{2\to\infty}\varphi\left(\frac{\|W\|_{F}}{\sqrt{n}\|W\|_{2\to\infty}}\right)\right)\geq
1-\frac{\delta_{1}}{n}.$ (4.3)

Then, with probability at least $1-\delta_{0}-2\delta_{1}$,

$\left\|U\mathrm{sgn}(H)-AU^{\star}(\Lambda^{\star})^{-1}\right\|_{2\to\infty}\leq
C_{0}\Big{(}\kappa(\kappa+\varphi(1))(\gamma+\varphi(\gamma))\|U^{\star}\|_{2\to\infty}+\frac{\gamma}{\Delta^{\star}}\|A^{\star}\|_{2\to\infty}\Big{)},$

where $C_{0}>0$ is an absolute constant.

######  Remark 4.4.

Theorem 4.3 can be applied to the recovery of a single eigenvector $u_{l}$ by
setting $r=1$ and $s=l-1$. In that case, the requirement (4.3) simplifies to

$\mathbb{P}\left(\left|(A-A^{\star})_{m,\cdot}\cdot
w\right|\leq\Delta^{\star}\|w\|_{\infty}\varphi\left(\frac{\|w\|_{2}}{\sqrt{n}\|w\|_{\infty}}\right)\right)\geq
1-\frac{\delta_{1}}{n}$

for each $w\in\mathbb{R}^{n}$. The conclusion becomes

$\min_{s\in\\{\pm
1\\}}\left\|su_{k}-\frac{Au_{k}^{\star}}{\lambda_{k}^{\star}}\right\|_{\infty}\leq
C_{0}\Big{(}\kappa(\kappa+\varphi(1))(\gamma+\varphi(\gamma))\|u_{k}^{\star}\|_{\infty}+\frac{\gamma}{\Delta^{\star}}\|A^{\star}\|_{2\to\infty}\Big{)}.$

In order to prove Theorem 4.1, we verify the five conditions of Theorem 4.3.
The following lemma states properties of the eigenspace of $A^{\star}$.

######  Lemma 4.5.

Let $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$ where $\rho\in(0,1)^{k}$ is such
that $\sum_{i}\rho_{i}=1$, and $P\in(0,1)^{k\times k}$ is a symmetric matrix.
Define $A=A(G,y)$ as in Definition 1.5. Denote $A^{\star}=\mathbb{E}[A]$ and
let $(\lambda_{l}^{\star},u_{l}^{\star})_{l\in[k]}$ be the top $k$ eigenpairs.
Then there exists constants $(\nu_{l})_{l\in[k]}$ depending on $P$, $\rho$,
$t$, and $y$ such that

$\begin{split}{eq:lambda-star-
asymp}\lambda_{l}^{\star}=(1+o(1))\nu_{1}\log(n)\quad\text{for all
}l\in[k]\end{split}$ (4.4)

Moreover, if $y$ is such that $\nu_{l}$’s are distinct, then there exist
constants $(\zeta_{lj})_{l,j\in[k]}$ depending on $P$, $\rho$, $t$, and $y$
such that

$\begin{split}{eq:u-star-
asymp}u_{lu}^{\star}=(1+o(1))\frac{\zeta_{lj}}{\sqrt{n}}\quad\text{ for all
}u\in\\{v:\sigma_{0}(v)=j\\}\end{split}$ (4.5)

###### Proof.

Since $A^{\star}_{ij}=\Theta\big{(}\frac{\log n}{n}\big{)}$ for $i\neq j$, the
proof of (LABEL:eq:lambda-star-asymp) follows by a straightforward adaptation
of the proof of [8, Lemma 3.2]. Next, consider the matrix
$B^{\star}=A^{\star}+D$, where $D$ is a diagonal matrix whose $(u,u)$-th entry
is $P_{jj}-y(1-P_{jj})$ if $u\in\\{v:\sigma_{0}(v)=j\\}$. Then $B^{\star}$ has
rank $k$ with distinct eigenvalues, and the corresponding eigenvectors will
have the form in (LABEL:eq:u-star-asymp). The $1+o(1)$ corrections account for
the diagonal perturbation, which can be dealt with using identical arguments
as [9, Lemma 5.3]. ∎

Among the conditions in Theorem 4.3, only the fourth and the fifth are
substantial. We verify them in the two lemmas below.

######  Lemma 4.6.

Let $A$ be a symmetric and zero-diagonal random matrix. Suppose that the
entries $\\{A_{ij}:i<j\\}$ are independent, $A_{ij}\in[a,b]$ for two constants
$a<b$, and $\mathbb{E}[|A_{ij}|]\leq p$ for all $i,j$, where $\frac{c_{0}\log
n}{n}\leq p\leq 1-c_{1}$ for constants $c_{0},c_{1}>0$. Then, for any $c>0$,
there exists $c^{\prime}>0$ such that

$\mathbb{P}\left(\|A-\mathbb{E}[A]\|_{2}\leq c^{\prime}\sqrt{np}\right)\geq
1-2n^{-c}.$

###### Proof.

Let $A=A^{+}-A^{-}$, where $A^{+}_{ij}=\max\\{A_{ij},0\\}$ and
$A^{-}_{ij}=-\min\\{A_{ij},0\\}$ for all $i,j$. Then

$\displaystyle\|A-\mathbb{E}[A]\|_{2}\leq\|A^{+}-\mathbb{E}[A^{+}]\|_{2}+\|A^{-}-\mathbb{E}[A_{-}]\|_{2}.$
(4.6)

Note that $A^{+}$ and $A^{-}$ are symmetric and zero-diagonal matrices with
independent upper-triangular entries. Also, note that for all $i\neq j$,

$\max\big{\\{}\mathbb{E}[A_{ij}^{+}],\mathbb{E}[A_{ij}^{-}]\big{\\}}\leq\mathbb{E}[|A_{ij}|]\leq
p.$

If $b\leq 0$, then $\|A^{+}-\mathbb{E}[A^{+}]\|_{2}=0$. Otherwise, suppose
$b>0$. By [11, Theorem 5], for any $c>0$, there exists $c_{+}>0$ such that

$\displaystyle\mathbb{P}\left(\|A^{+}-\mathbb{E}[A^{+}]\|_{2}>c_{+}\sqrt{b}\cdot\sqrt{np}\right)$
$\displaystyle=\mathbb{P}\bigg{(}\bigg{\|}\frac{1}{b}A^{+}-\frac{1}{b}\mathbb{E}[A^{+}]\bigg{\|}_{2}>c_{+}\sqrt{\frac{np}{b}}\bigg{)}\leq
n^{-c}.$ (4.7)

Similarly, if $a\geq 0$, then $\|A^{-}-\mathbb{E}[A^{-}]\|_{2}=0$. Otherwise,
suppose $a<0$. By [11, Theorem 5], for any $c>0$, there exists $c_{-}>0$ such
that

$\displaystyle\mathbb{P}\left(\|A^{-}-\mathbb{E}[A^{-}]\|_{2}>c_{-}\sqrt{|a|}\sqrt{np}\right)$
$\displaystyle=\mathbb{P}\bigg{(}\bigg{\|}\frac{1}{|a|}A^{-}-\frac{1}{|a|}\mathbb{E}[A^{-}]\bigg{\|}_{2}>c_{-}\sqrt{\frac{np}{|a|}}\bigg{)}\leq
n^{-c}.$ (4.8)

Stated above in terms of upper bound on probabilities. Take
$c^{\prime}=c_{+}\sqrt{\max\\{b,0\\}}+c_{-}\sqrt{|\min\\{a,0\\}|}$. Combining
(4.6), (4.7), and (4.8) along with a union bound, the proof is complete. ∎

######  Lemma 4.7.

Let $r\in\mathbb{N}$ be a constant, and $W\in\mathbb{R}^{n\times r}$ be a
fixed matrix. Let $\\{Z_{i}\\}_{i=1}^{n}$ be independent random variables
where $\mathbb{P}(Z_{i}=1)=p_{i}$, $\mathbb{P}(Z_{i}=-y)=q_{i}$, and
$\mathbb{P}(Z_{i}=0)=1-p_{i}-q_{i}$. Finally, let
$\overline{Z}\in\mathbb{R}^{n}$, where
$\overline{Z}_{i}=Z_{i}-\mathbb{E}[Z_{i}]$ for $i\in[n]$. Then for any
$\beta\geq 0$,

$\mathbb{P}\bigg{(}\big{\|}\overline{Z}^{T}W\big{\|}_{2}\geq
r\frac{\max\\{1,y\\}(2+\beta)n}{1\lor\log\big{(}\frac{\sqrt{n}\|W\|_{2\to\infty}}{\|W\|_{F}}\big{)}}\|W\|_{2\to\infty}\max_{i}\\{p_{i}+q_{i}\\}\bigg{)}\leq
2r\exp\big{(}-\beta n\max_{i}\\{p_{i}+q_{i}\\}\big{)}.$

###### Proof.

Let $w_{j}=W_{\cdot j}$ denote the $j$th column of $W$, for $j\in[r]$. We will
show that

$\frac{r\|W\|_{2\to\infty}}{1\lor\log\big{(}\frac{\sqrt{n}\|W\|_{2\to\infty}}{\|W\|_{F}}\big{)}}\geq\sum_{j=1}^{r}\frac{\|w_{j}\|_{\infty}}{1\lor\log\big{(}\frac{\sqrt{n}\|w_{j}\|_{\infty}}{\|w_{j}\|_{2}}\big{)}}.$
(4.9)

Given (4.9), we then obtain

$\displaystyle\mathbb{P}\bigg{(}\big{\|}\overline{Z}^{T}W\big{\|}_{2}\geq
r\frac{\max\\{1,y\\}(2+\beta)n}{1\lor\log\big{(}\frac{\sqrt{n}\|W\|_{2\to\infty}}{\|W\|_{F}}\big{)}}\|W\|_{2\to\infty}\max_{i}\\{p_{i}+q_{i}\\}\bigg{)}$
$\displaystyle\leq\mathbb{P}\bigg{(}\sum_{j=1}^{r}\bigg{|}\sum_{i=1}^{n}W_{ij}\overline{Z}_{i}\bigg{|}\geq\max\\{1,y\\}(2+\beta)n\max_{i}\\{p_{i}+q_{i}\\}\sum_{j=1}^{r}\frac{\|w_{j}\|_{\infty}}{1\lor\log\big{(}\frac{\sqrt{n}\|w_{j}\|_{\infty}}{\|w_{j}\|_{2}}\big{)}}\bigg{)}$
(4.10)
$\displaystyle\leq\sum_{i=1}^{r}\mathbb{P}\bigg{(}\bigg{|}\sum_{i=1}^{n}W_{ij}\overline{Z}_{i}\bigg{|}\geq\frac{\max\\{1,y\\}(2+\beta)n\|w_{j}\|_{\infty}}{1\lor\log\big{(}\frac{\sqrt{n}\|w_{j}\|_{\infty}}{\|w_{j}\|_{2}}\big{)}}\max_{i}\\{p_{i}+q_{i}\\}\bigg{)}$
(4.11) $\displaystyle\leq 2r\exp\big{(}-\beta
n\max_{i}\\{p_{i}+q_{i}\\}\big{)}.$ (4.12)

Here (4.10) follows from (4.9) and the fact that $\|x\|_{2}\leq\|x\|_{1}$ for
any finite dimensional vector. Next, (4.11) follows by the union bound, and
(4.12) is an application of [9, Lemma 5.2].

It remains to prove (4.9). Since $\|w_{j}\|_{2}\leq\|W\|_{F}$ for all
$j\in[r]$, we obtain

$\displaystyle\sum_{j=1}^{r}\frac{\|w_{j}\|_{\infty}}{1\lor\log\big{(}\frac{\sqrt{n}\|w_{j}\|_{\infty}}{\|w_{j}\|_{2}}\big{)}}$
$\displaystyle\leq\sum_{j=1}^{r}\frac{\|w_{j}\|_{\infty}}{1\lor\log\left(\frac{\sqrt{n}\|w_{j}\|_{\infty}}{\|W\|_{F}}\right)}.$

Let $g(c,x):=\frac{x}{1\vee\log(cx)}$ for $c>0$. Then
$\frac{\partial}{\partial x}g(c,x)=1$ for $x<\mathrm{e}/c$, and
$\frac{\partial}{\partial x}g(c,x)=\frac{\log(cx)-1}{\log^{2}(cx)}>0$ for
$x>\mathrm{e}/c$. Therefore, $g(c,\cdot)$ is increasing for any $c>0$. Since
$\|w_{j}\|_{\infty}\leq\|W\|_{2\to\infty}$ for all $j$, we obtain

$\displaystyle\sum_{j=1}^{r}\frac{\|w_{j}\|_{\infty}}{1\lor\log\big{(}\frac{\sqrt{n}\|w_{j}\|_{\infty}}{\|W\|_{F}}\big{)}}=\sum_{j=1}^{r}g\bigg{(}\frac{\sqrt{n}}{\|W\|_{F}},\|w_{j}\|_{\infty}\bigg{)}\leq
rg\bigg{(}\frac{\sqrt{n}}{\|W\|_{F}},\|W\|_{2\to\infty}\bigg{)}=\frac{r\|W\|_{2\to\infty}}{1\lor\log\left(\frac{\sqrt{n}\|W\|_{2\to\infty}}{\|W\|_{F}}\right)},$

which completes the proof of (4.9). ∎

###### Proof of Theorem 4.1.

We now verify the conditions of Theorem 4.3 for the signed adjacency matrix
$A=A(G,y)$ when $G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$. Set

$\varphi(x)=r\frac{2\log(n)}{\Delta^{\star}}\max\\{1,y\\}(t+2)\bigg{(}1\lor\log\Big{(}\frac{1}{x}\Big{)}\bigg{)}^{-1}.$

Note that $\lim_{x\to 0^{+}}\varphi(0)=0$ and $\frac{\varphi(x)}{x}$ is non-
increasing on $\mathbb{R}_{+}$. Thus the first condition holds.

To verify the second condition, we find that
$\|A^{\star}\|_{2\to\infty}=\Theta\big{(}\frac{\log n}{\sqrt{n}}\big{)}$.
Applying Lemma 4.6 with $c=3$, and using the fact that
$|A^{\star}_{ij}|\leq\frac{t\log(n)}{n}\max_{i,j\in[k]}P_{ij}$, there exists
$c^{\prime}>0$ such that

$\mathbb{P}\left(\|A-\mathbb{E}[A]\|_{2}\leq
c^{\prime}\sqrt{\log(n)}\right)\geq 1-n^{-3}.$ (4.13)

By assumption, we have $\Delta^{\star}>0$. Moreover, by Lemma 4.5, we have
$\Delta^{\star}=\Theta(\log(n))$. Let
$\gamma=c^{\prime}\sqrt{\log(n)}/\Delta^{\star}$. Therefore,
$\|A^{\star}\|_{2\to\infty}\leq\gamma\Delta^{\star}$ is satisfied for $n$
large enough.

The third condition is immediate.

The second part of the fourth condition holds with $\delta_{0}=n^{-3}$ due to
(4.13). To verify the first part, note that $\kappa=\Theta(1)$ by Lemma 4.5
and $\gamma=o(1)$. Then $32\kappa\max\\{\gamma,\varphi(\gamma)\\}\leq 1$ for
all sufficiently large $n$.

To verify the fifth condition, fix $W\in\mathbb{R}^{n\times r}$ and $m\in[n]$.
By Lemma 4.7 with $p_{i}\in\\{\frac{t\log n}{n}P_{ab}:a,b\in[k]\\}$,
$p_{i}+q_{i}=\frac{t\log n}{n}$ and $\beta=\frac{4}{t}$, we obtain

$\mathbb{P}\bigg{(}\big{\|}\big{(}(A-A^{\star})_{m,\cdot}\big{)}\cdot
W\big{\|}_{2}\geq
r\frac{\max\\{1,y\\}(2+4/t)n}{1\lor\log\left(\frac{\sqrt{n}\|W\|_{2\to\infty}}{\|W\|_{F}}\right)}\|W\|_{2\to\infty}\frac{t\log
n}{n}\bigg{)}\leq 2r\exp\left(-\frac{4n}{t}\times\frac{t\log n}{n}\right),$

which can be re-written as

$\mathbb{P}\left(\big{\|}\big{(}(A-A^{\star})_{m,\cdot}\big{)}W\big{\|}_{2}\geq\Delta^{\star}\|W\|_{2\to\infty}\varphi\left(\frac{\|W\|_{F}}{\sqrt{n}\|W\|_{2\to\infty}}\right)\right)\leq
2rn^{-4}.$

Therefore, the fifth condition is satisfied with $\delta_{1}=2rn^{-3}$.

Applying Theorem 4.3, we conclude that with probability at least
$1-(1+4r)n^{-3}\geq 1-5rn^{-3}$,

$\displaystyle\inf_{O\in\mathcal{O}^{r\times r}}\left\|UO-
AU^{\star}\left(\Lambda^{\star}\right)^{-1}\right\|_{2\to\infty}$
$\displaystyle\leq
C_{0}\Big{(}\kappa(\kappa+\varphi(1))(\gamma+\varphi(\gamma))\|u_{k}^{\star}\|_{\infty}+\frac{\gamma}{\Delta^{\star}}\|A^{\star}\|_{2\to\infty}\Big{)}\leq\frac{C(P,\rho,t,y)}{\log\log(n)\sqrt{n}}.$

∎

##  5\. Performance of Spectral Algorithms

Throughout this section, we use the notation

$\displaystyle
y(p,q)=\frac{\log\frac{1-q}{1-p}}{\log\frac{p}{q}}\quad\text{for}~{}p\neq q.$
(5.1)

This will be the choice of $y$ value for which Spectral-One algorithms are
optimal in the cases stated in Theorem 1.7 1. Also, as before, we condition on
a fixed value of $\sigma_{0}$ satisfying (1.4) with $\varepsilon=n^{-1/3}$.

Recall that our spectral algorithms use the top two eigenvectors of the signed
adjacency matrix/matrices. In general, the signed adjacency matrix should have
two main eigenvectors which correspond (up to a potential sign flip) to the
main eigenvectors of the expected adjacency matrix. However, this could run
into complications if both eigenvalues are the same or one of the eigenvalues
is $0$. In order to address this, we have the following eigenvalue
characterization. The proof is provided in Appendix C.

######  Lemma 5.1.

Let $0<p_{1},p_{2},q<1$ be not all the same, $\rho\in(0,1)$ and define

$A^{\prime}=A^{\prime}(y):=\begin{pmatrix}p_{1}-y(1-p_{1})&q-y(1-q)\\\
q-y(1-q)&p_{2}-y(1-p_{2})\end{pmatrix}\begin{pmatrix}\rho&0\\\
0&1-\rho\end{pmatrix}$ (5.2)

for each $y>0$. Then all of the following hold.

  1. (1)

For any fixed $p_{1},p_{2},q,\rho\in(0,1)$, there exists a set $\mathcal{Y}$
with $|\mathcal{Y}|\leq 3$ such that the eigenvalues of $A^{\prime}$ are
distinct and nonzero for all $y\notin\mathcal{Y}$.

  2. (2)

If $p_{1}=p$, $p_{2}=q$, $p\neq q$, and $y=y(p,q)$ then the eigenvalues of
$A^{\prime}$ are distinct and nonzero.

  3. (3)

If $p_{1}=p_{2}=p$, $p\neq q$, and $y=y(p,q)$ then the eigenvalues of
$A^{\prime}$ are distinct and nonzero if and only if $p+q\neq 1$.

###  5.1. One matrix

In order to prove Theorem 1.7 1, we provide an algorithm which is an instance
of Spectral-One, that will succeed up to the information theoretic threshold
when

$\begin{split}\text{either }p_{1}=p_{2}=p,p\neq q\text{ and }p+q\neq
1\quad\text{or}\quad p_{1}=p\text{ and }p_{2}=q\neq p.\end{split}$ (5.3)

Algorithm 3 One-matrix community detection

1:Parameters $t>0$, $\rho\in(0,1)$, $p_{1},p_{2},q\in(0,1)$ satisfying (5.3)
and $G\sim\textsc{CSBM}_{n}^{2}(\bar{\rho},P,t)$.

2:Community classification $\hat{\sigma}\in\\{1,2\\}^{n}$.

3:Construct an $n\times n$ matrix $A=A(G,y)$ as defined in Definition 1.5.

4:Find the top two eigenpairs $(\lambda_{1},u_{1})\text{ and
}(\lambda_{2},u_{2})$ of $A$.

5:Compute $(a_{1},a_{2})$, the weights produced by Algorithm 5.1.

6:Let $U=\\{s_{1}a_{1}u_{1}+s_{2}a_{2}u_{2}:s_{1},s_{2}\in\\{\pm 1\\}\\}$. For
each $u\in U$, let $\hat{\sigma}(\cdot;u)=1+(1+\mathrm{sign}(u))/2$.

7:Return $\hat{\sigma}=\operatornamewithlimits{argmax}_{u\in
U}\mathbb{P}(G\mid\hat{\sigma}(\cdot;u))$.

Algorithm 4 Find weights (one matrix)

1:Parameters $t>0$, $\rho\in(0,1)$, $p_{1},p_{2},q\in(0,1)$ satisfying (5.3).

2:Weights $(a_{1},a_{2})$

3:Let $\mathcal{V}_{1}:=\\{i:i\leq\rho n\\}$ and define $B$ to be the
symmetric block matrix where $B_{ij}$ is $\frac{t\log
n}{n}[p_{1}-y(p_{1},q)(1-p_{1})]$ if $i,j\in\mathcal{V}_{1}$, $\frac{t\log
n}{n}[p_{2}-y(p_{2},q)(1-p_{2})]$ if $i,j\notin\mathcal{V}_{1}$, and
$\frac{t\log n}{n}[q-y(p_{1},q)(1-q)]$ if
$i\in\mathcal{V}_{1},j\notin\mathcal{V}_{1}$ or
$i\notin\mathcal{V}_{1},j\in\mathcal{V}_{1}$. Let the eigenpairs of $B$ be
denoted $(\gamma_{1},v_{1}),(\gamma_{2},v_{2})$.

4:Set $\alpha_{1}=\log\frac{p}{q}$. If $p_{1}=p_{2}=p$, set
$\alpha_{2}=-\alpha_{1}$. Otherwise ($p_{2}=q$), set $\alpha_{2}=0$. Let $z$
be a block vector with $z_{i}=\alpha_{1}$ if $i\in\mathcal{V}_{1}$ and
$z_{i}=\alpha_{2}$ if $i\not\in\mathcal{V}_{1}$.

5:Return $(a_{1},a_{2})$ satisfying  $\begin{split}\sqrt{n}\log
n\left(a_{1}\frac{v_{1}}{\gamma_{1}}+a_{2}\frac{v_{2}}{\gamma_{2}}\right)=z.\end{split}$
(5.4)

It is worthwhile to note that finding weights in Algorithm 5.1 does not
require any information about $\sigma_{0}$.

###### Proof of Theorem 1.7.

Let $n_{i}$ be the number of vertices in community $i$ for $i=1,2$. Throughout
the proof, we will condition on $\sigma_{0}$ satisfying
$\left|n_{i}-\rho_{i}n\right|\leq n^{2/3}$. This event has probability
$1-o(1)$ as shown earlier in (1.4).

First, suppose that (5.3) holds. We will first prove Theorem 1.7 1 by showing
Algorithm 5.1 succeeds up to the information theoretic limit. Let $A=A(G,y)$
with $y=y(p_{1},q)$, and define $A^{\star}=\mathbb{E}[A]$. Let
$(\lambda_{i},u_{i})$ and $(\lambda_{i}^{\star},u_{i}^{\star})$ denote the
$i$-th largest eigenpair of $A$ and $A^{\star}$ respectively. We claim that

$\begin{split}{eval-sep-A-star}\lambda_{1}^{\star}=(1+o(1))\nu_{1}\log
n,\quad\lambda_{2}^{\star}=(1+o(1))\nu_{2}\log n\quad\text{with
}\nu_{1}\neq\nu_{2},\nu_{1},\nu_{2}\neq 0.\end{split}$ (5.5)

Indeed, consider the matrix $B$ defined in Step 1 of Algorithm 5.1, whose
eigenvalues are $t\log n$ times the corresponding eigenvalues the matrix
$A^{\prime}$ defined in (5.2). Under the conditions of Theorem 1.7 1, Lemma
5.1 (Parts 2 and 3), shows that the non-zero eigenvalues of $B$ are
$\nu_{1}\log n$ and $\nu_{2}\log n$ with $\nu_{1}\neq\nu_{2}$. Next, suppose
$O$ is the permutation matrix such that, in $OA^{\star}O^{T}$, the rows and
columns corresponding to vertices in community 1 appear before those in
community 2. By Weyl’s theorem, the top two eigenvalues of $OA^{\star}O^{T}$
are within $1+o(1)$ multiplicative factor of those of $B$. Since $O$ is an
orthogonal matrix, (LABEL:eval-sep-A-star) follows immediately.

Using (LABEL:eval-sep-A-star), we can apply Corollary 4.2 and conclude that,
with probability $1-O(n^{-3})$,

$\left\|s_{1}u_{1}-\frac{Au_{1}^{\star}}{\lambda_{1}^{\star}}\right\|_{\infty}\leq\frac{C}{\sqrt{n}\log\log
n}~{}~{}~{}\text{and}~{}~{}~{}\left\|s_{2}u_{2}-\frac{Au_{2}^{\star}}{\lambda_{2}^{\star}}\right\|_{\infty}\leq\frac{C}{\sqrt{n}\log\log
n},$

for some $s_{1},s_{2}\in\\{-1,1\\}$ and some constant $C>0$. Consequently, for
any $a_{1},a_{2}\in\mathbb{R}$, with probability $1-o(1)$,

$\begin{split}{eq:vec-approximation-in-
proof}\left\|s_{1}a_{1}u_{1}+s_{2}a_{2}u_{2}-A\left(\frac{a_{1}}{\lambda_{1}^{\star}}u_{1}^{\star}+\frac{a_{2}}{\lambda_{2}^{\star}}u_{2}^{\star}\right)\right\|_{\infty}\leq\frac{C(|a_{1}|+|a_{2}|)}{\sqrt{n}\log\log
n}.\end{split}$ (5.6)

In Step 5 of Algorithm 5.1, we pick $(a_{1},a_{2})$ according to Algorithm
5.1. Let $\mathcal{V}_{1}^{\prime}:=\\{i:i\leq n_{1}(\sigma_{0})\\}$ and
define $B^{\prime},v_{1}^{\prime},v_{2}^{\prime}$ similarly as $B,v_{1},v_{2}$
in Algorithm 5.1 by replacing $\mathcal{V}_{1}$ by $\mathcal{V}_{1}^{\prime}$.
For $l=1,2$, note that $v_{l}$ takes some value $\frac{\zeta_{l1}}{\sqrt{n}}$
on $\mathcal{V}_{1}$ and $\frac{\zeta_{l2}}{\sqrt{n}}$ on
$\mathcal{V}_{1}^{c}$ for constants $\zeta_{l1},\zeta_{l2}$. Using identical
steps as [9, Lemma 5.3], we can argue that $v_{l}^{\prime}$ also takes value
$(1+o(1))\frac{\zeta_{l1}}{\sqrt{n}}$ on $\mathcal{V}_{1}^{\prime}$ and
$(1+o(1))\frac{\zeta_{l2}}{\sqrt{n}}$ on $(\mathcal{V}_{1}^{\prime})^{c}$.
Therefore,

$\displaystyle\sqrt{n}\log
n\left(a_{1}\frac{v_{1}^{\prime}}{\gamma_{1}}+a_{2}\frac{v_{2}^{\prime}}{\gamma_{2}}\right)=\tilde{z},$

where $\tilde{z}$ is a block vector taking values $(1+o(1))\alpha_{1}$ on
$\mathcal{V}_{1}^{\prime}$ and $(1+o(1))\alpha_{2}$ on
$(\mathcal{V}_{1}^{\prime})^{c}$. Next, note that the matrix $A^{\star}$ can
be obtained from $B^{\prime}$ by jointly permuting the row and column labels
and then setting the diagonal entries to be zero. Also, noting that
$\lambda_{l}^{\star}=(1+o(1))\gamma_{l}$, we can ensure that

$\begin{split}{form-lin-
comb}\sqrt{n}\log(n)\left(a_{1}\frac{u_{1}^{\star}}{\lambda_{1}^{\star}}+a_{2}\frac{u_{2}^{\star}}{\lambda_{2}^{\star}}\right)=z^{\star},\end{split}$
(5.7)

where $z^{\star}$ is a block vector taking value $(1+o(1))\alpha_{1}$ on
$V_{1}:=\\{v:\sigma_{0}(v)=+1\\}$ and $(1+o(1))\alpha_{2}$ on
$V_{2}:=\\{v:\sigma_{0}(v)=-1\\}$. Let

$\tau=A\left(a_{1}\frac{u_{1}^{\star}}{\lambda_{1}^{\star}}+a_{2}\frac{u_{2}^{\star}}{\lambda_{2}^{\star}}\right).$

Then, $\sqrt{n}\log(n)\tau=(1+o(1))Az^{\star}$. By (LABEL:form-lin-comb), with
probability $1-o(1)$, for each $v\in[n]$,

$\begin{split}{eq:tau}\sqrt{n}\log(n)\tau_{v}&=\alpha_{1}d_{+1}(v)-y\alpha_{1}d_{-1}(v)+\alpha_{2}d_{+2}(v)-y\alpha_{2}d_{-2}(v)+o(\log
n),\end{split}$ (5.8)

where $(d_{+1}(v),d_{-1}(v),d_{+2}(v),d_{-2}(v))$ denotes the degree profile
of $v$. Also, in this case, note that $w^{\star}$ in (2.6) simplifies to

$\displaystyle
w^{\star}=\bigg{(}\log\frac{p_{1}}{q},\log\frac{1-p_{1}}{1-q},\log\frac{q}{p_{2}},\log\frac{1-q}{1-p_{2}}\bigg{)}.$
(5.9)

In order to apply Proposition 2.10, we need to ensure that the coefficients of
(LABEL:eq:tau) coincide with $w^{\star}$ up to a scalar factor. There are two
cases to consider. First, suppose $p_{1}=p_{2}=p$, and $p\neq q$ (where we
rule out the case $\\{p+q=1,\rho\neq 1/2\\}$). Recalling that $y=y(p,q)$, we
obtain

$\displaystyle w^{\star}=(1,-y,-1,y)\log\left(\frac{p}{q}\right).$ (5.10)

Comparing (LABEL:eq:tau) and (5.10), we see that the choice
$\alpha_{1}=\log\frac{p}{q}$ and $\alpha_{2}=-\alpha_{1}$ equates the
coefficients of the leading terms of (LABEL:eq:tau) with the entries of
(5.10). These are the values of $(\alpha_{1},\alpha_{2})$ chosen in Algorithm
5.1 Step 2.

Next, suppose $p_{2}=q$ and recall that $p_{1}\neq q$. By our choice of
$y=y(p_{1},q)$, we have that

$\displaystyle w^{\star}=(1,-y,0,0)\log\left(\frac{p}{q}\right).$

In this case, we need $\alpha_{1}=\log\frac{p_{1}}{q}$ and $\alpha_{2}=0$,
which is also the case by our choice in Algorithm 5.1 Step 2. (Note that any
choice of the form $(\alpha_{1},\alpha_{2})=c(1,-1)$ would lead to
$\sqrt{n}\log(n)\tau_{v}-o(\log(n))\propto\langle w^{\star},d(v)\rangle$.)

Thus, in both cases, our choices of $(\alpha_{1},\alpha_{2})$ yield that, with
probability $1-o(1)$, $\sqrt{n}\log(n)\tau_{v}=\langle
w^{\star},d(v)\rangle+o(\log n)$ for each $v\in[n]$. By Proposition 2.10, we
conclude that for some $\varepsilon>0$,

$\displaystyle\sqrt{n}\log(n)\min_{v\in
V_{1}}\tau_{v}\geq\frac{1}{2}\varepsilon\log
n\quad\text{and}\quad\sqrt{n}\log(n)\max_{v\in
V_{2}}\tau_{v}\leq-\frac{1}{2}\varepsilon\log n$

with probability $1-o(1)$, and consequently

$\displaystyle\min_{v\in
V_{1}}\tau_{v}\geq\frac{\varepsilon}{2\sqrt{n}}\quad\text{and}\quad\max_{v\in
V_{2}}\tau_{v}\leq-\frac{\varepsilon}{2\sqrt{n}}.$

Finally, since
$\frac{C}{\sqrt{n}\log\log(n)}=o\big{(}\frac{1}{\sqrt{n}}\big{)}$, we conclude
with probability $1-o(1)$,

$\min_{v\in
V_{1}}\left(s_{1}a_{1}u_{1}+s_{2}a_{2}u_{2}\right)_{v}>\frac{\varepsilon}{3\sqrt{n}}\quad\text{and}\quad\max_{v\in
V_{1}}\left(s_{1}a_{1}u_{1}+s_{2}a_{2}u_{2}\right)_{v}<-\frac{\varepsilon}{3\sqrt{n}}.$

Therefore, thresholding the vector $s_{1}a_{1}u_{1}+s_{2}a_{2}u_{2}$ at zero
correctly identifies the communities with high probability. In other words,
$\mathrm{sign}(s_{1}a_{1}u_{1}+s_{2}a_{2}u_{2})$ coincides with the MAP
estimator. While $s_{1},s_{2}$ are unknown, the final step of Algorithm 1.3
chooses the best one among the four candidate community partitions arising
from the four possible sign combinations. By Theorem 3.1, we know that the MAP
estimator is the unique maximizer of the posterior probability. Therefore, the
spectral algorithm will identify the correct candidate. This completes the
proof of Theorem 1.7 1.

To prove Theorem 1.7 2, let $p_{1},p_{2},q$ be distinct. Notice that
(LABEL:eq:tau) would hold for any $\alpha_{1},\alpha_{2}$ and the
corresponding choices of $a_{1},a_{2}$. The particular choice of
$\alpha_{1},\alpha_{2}$ was only needed after (LABEL:eq:tau) to compare it
with $w^{\star}$. By Proposition 2.10 and (LABEL:eq:tau), in order for
Spectral-One algorithms to be successful, we must have
$w^{\star}=(\alpha_{1},-y\alpha_{1},\alpha_{2},-y\alpha_{2})$. Suppose for the
sake of contradiction that
$w^{\star}=(\alpha_{1},-y\alpha_{1},\alpha_{2},-y\alpha_{2})$ for some
$\alpha_{1},\alpha_{2}$. Since all the entries of $w^{\star}$ are nonzero, we
know that $\alpha_{1},\alpha_{2}\neq 0$. By taking coordinate ratios, we have
that

$\displaystyle
y=\frac{\log\frac{1-q}{1-p_{1}}}{\log\frac{p_{1}}{q}}=y(p_{1},q)\quad\text{and}\quad
y=\frac{\log\frac{1-q}{1-p_{2}}}{\log\frac{p_{2}}{q}}=y(p_{2},q).$ (5.11)

Now, we claim that for any fixed $q\in(0,1)$, the function $y(p,q)$ is
strictly increasing. Indeed,

$\displaystyle\frac{\partial}{\partial
p}y(p,q)=\frac{\log\frac{p}{q}\times\frac{1}{1-p}-\log\frac{1-q}{1-p}\times\frac{1}{p}}{\log^{2}\frac{p}{q}}=\frac{1}{p\log\frac{p}{q}}\bigg{(}\frac{p}{1-p}-y(p,q)\bigg{)}.$
(5.12)

Using the fact that $1-\frac{1}{x}<\log x<x-1$ for any $x>0$,

$\displaystyle\text{ for any }p>q:\quad
y(p,q)=\frac{\log\frac{1-q}{1-p}}{\log\frac{p}{q}}<\frac{\frac{1-q}{1-p}-1}{1-\frac{q}{p}}=\frac{p}{1-p}$
(5.13) $\displaystyle\text{ for any }p<q:\quad
y(p,q)=\frac{\log\frac{1-q}{1-p}}{\log\frac{p}{q}}=\frac{\log\frac{1-p}{1-q}}{\log\frac{q}{p}}>\frac{1-\frac{1-q}{1-p}}{\frac{q}{p}-1}=\frac{p}{1-p}.$
(5.14)

Therefore, $\frac{\partial}{\partial p}y(p,q)>0$ for any $p\in(0,1)$, which
proves that $y(p,q)$ is strictly increasing. However, $p_{1}\neq p_{2}$ and
therefore $y(p_{1},q)\neq y(p_{2},q)$. Thus, (5.11) leads to a contradiction.
In other words, it is not possible to choose $\alpha_{1},\alpha_{2}$ so that
$w^{\star}=(\alpha_{1},-y\alpha_{1},\alpha_{2},-y\alpha_{2})$. The proof then
follows by applying Proposition 2.10 2. ∎

######  Remark 5.2.

Instead of using the encoding $\\{1,-y,0\\}$ for present, absent and censored
edges, we could have instead used a more general encoding of the form
$\\{c_{1},-yc_{2},c_{3}\\}$. In that case, the entrywise approximation would
still hold. One could go though the same steps to show that the decision rule
for the spectral algorithm would again be asymptotically based on determining
whether some linear expression such as (LABEL:eq:tau) is above or below a
certain threshold $T$. Thus, for $p_{1},p_{2},q$ which are distinct, an
identical argument shows that spectral algorithms with more general encoding
also do not succeed sufficiently close to $t_{c}$.

###  5.2. Two matrices

In this section, we will prove Theorem 1.10. Let us start by describing the
algorithm that always succeeds up to the information theoretic threshold in
the two community case.

Algorithm 5 Two-matrix community detection for two communities

1:Parameters $t>0$, $\rho,p_{1},p_{2},q\in(0,1)$ such that
$|\\{p_{1},p_{2},q\\}|\geq 2$, and
$G\sim\textsc{CSBM}_{n}^{2}(\bar{\rho},P,t)$.

2:Community classification $\hat{\sigma}\in\\{1,2\\}^{n}$.

3:Fix $y,\tilde{y}\notin\mathcal{Y}$ where $\mathcal{Y}$ is given by Lemma 5.1
Part (1). Construct two $n\times n$ matrices $A=A(G,y)$,
$\tilde{A}=A(G,\tilde{y})$ as defined in Definition 1.5.

4:Find the top two eigenpairs of $A$ and $\tilde{A}$, respectively denoting
them $((\lambda_{l},u_{l}))_{l=1,2}$ and
$((\tilde{\lambda}_{l},\tilde{u}_{l}))_{l=1,2}$.

5:Use Algorithm 5.2 on input $\left(t,\rho,\begin{pmatrix}p_{1}&q\\\
q&p_{2}\end{pmatrix},y,\tilde{y}\right)$ to compute the weights
$(c_{1},c_{2},\tilde{c}_{1},\tilde{c}_{2})$.

6:Let
$U=\\{s_{1}c_{1}u_{1}+s_{2}c_{2}u_{2}+\tilde{s}_{1}\tilde{c}_{1}\tilde{u}_{1}+\tilde{s}_{2}\tilde{c}_{2}\tilde{u}_{2}:s_{1},s_{2},\tilde{s}_{1},\tilde{s}_{2}\in\\{\pm
1\\}\\}.$ For each $u\in U$, let
$\hat{\sigma}(\cdot;u)=1+(1+\mathrm{sign}(u))/2$.

7:Return $\hat{\sigma}=\operatornamewithlimits{argmax}_{u\in
U}\mathbb{P}(G\mid\hat{\sigma}(\cdot;u))$.

Algorithm 6 Find weights (two matrices, two communities)

1:Parameters $t>0$, $\rho,p_{1},p_{2},q\in(0,1)$ such that
$|\\{p_{1},p_{2},q\\}|\geq 2$, and $y,\tilde{y}\notin\mathcal{Y}$,
$y\neq\tilde{y}$ where $\mathcal{Y}$ is given by Lemma 5.1 Part (1).

2:Weights $(c_{1},c_{2},\tilde{c}_{1},\tilde{c}_{2})$

3:Let $\mathcal{V}_{1}:=\\{i:i\leq\rho n\\}$ and define $B$ to be the
symmetric block matrix where $B_{ij}$ is $\frac{t\log
n}{n}[p_{1}-y(p_{1},q)(1-p_{1})]$ if $i,j\in\mathcal{V}_{1}$, $\frac{t\log
n}{n}[p_{2}-y(p_{2},q)(1-p_{2})]$ if $i,j\notin\mathcal{V}_{1}$, and
$\frac{t\log n}{n}[q-y(p_{1},q)(1-q)]$ if
$i\in\mathcal{V}_{1},j\notin\mathcal{V}_{1}$ or
$i\notin\mathcal{V}_{1},j\in\mathcal{V}_{1}$. Define $\tilde{B}$ similarly by
replacing $y$ by $\tilde{y}$. Let the eigenpairs of $B$ and $\tilde{B}$ be
$((\gamma_{l},v_{l}))_{l=1,1}$ and
$((\tilde{\gamma}_{l},\tilde{v}_{l}))_{l=1,2}$, respectively.

4:Solve the following system for
$\alpha_{1},\alpha_{2},\tilde{\alpha}_{1},\tilde{\alpha}_{2}$:
$\begin{split}{coeffs-2matrix}&\alpha_{1}+\tilde{\alpha}_{1}=\log\frac{p_{1}}{q},\quad-y\alpha_{1}-\tilde{y}\tilde{\alpha}_{1}=\log\frac{1-p_{1}}{1-q},\\\
&\alpha_{2}+\tilde{\alpha}_{2}=\log\frac{q}{p_{2}}\quad-y\alpha_{2}-\tilde{y}\tilde{\alpha}_{2}=\log\frac{1-q}{1-p_{2}}.\end{split}$
(5.15) Let $z$ be a block vector with $z_{i}=\alpha_{1}$ for
$i\in\mathcal{V}_{1}$ and $z_{i}=\alpha_{2}$ for $i\not\in\mathcal{V}_{1}$.
Define $\tilde{z}$ similarly by replacing $(\alpha_{1},\alpha_{2})$ by
$(\tilde{\alpha}_{1},\tilde{\alpha}_{2})$.

5:Return $(c_{1},c_{2},\tilde{c}_{1},\tilde{c}_{2})$ satisfying
$\begin{split}{two-z-choices}\sqrt{n}\log
n\left(c_{1}\frac{v_{1}}{\gamma_{1}}+c_{2}\frac{v_{2}}{\gamma_{2}}\right)&=z\quad\text{and}\quad\sqrt{n}\log
n\left(\tilde{c}_{1}\frac{\tilde{v}_{1}}{\tilde{\gamma}_{1}}+\tilde{c}_{2}\frac{\tilde{v}_{2}}{\tilde{\gamma}_{2}}\right)=\tilde{z}.\end{split}$
(5.16)

###### Proof of Theorem 1.10.

As in the proof of Theorem 1.7, we condition on $\sigma_{0}$ satisfying
$\left|n_{i}-\rho_{i}n\right|\leq n^{2/3}$. Fix
$y,\tilde{y}\notin\mathcal{Y}$, $y\neq\tilde{y}$ where $\mathcal{Y}$ is given
by Lemma 5.1 Part (1). Recall all the notation in Algorithms 5.2, 5.2. Let
$A^{\star}:=\mathbb{E}[A]$ and $\tilde{A}^{\star}:=\mathbb{E}[\tilde{A}]$, and
let $((\lambda_{l}^{\star},u_{l}^{\star}))_{l=1,1}$, and
$(\tilde{\lambda}_{l}^{\star},\tilde{u}_{l}^{\star}))_{l=1,2}$ be the top
eigenpairs of the corresponding matrices. Applying Corollary 4.2, we have that
with probability $1-o(1)$

$\displaystyle\left\|s_{1}c_{1}u_{1}+s_{2}c_{2}u_{2}+\tilde{s}_{1}\tilde{c}_{1}\tilde{u}_{1}+\tilde{s}_{2}\tilde{c}_{2}\tilde{u}_{2}-A\bigg{(}c_{1}\frac{u_{1}^{\star}}{\lambda_{1}^{\star}}+c_{2}\frac{u_{2}^{\star}}{\lambda_{2}^{\star}}\bigg{)}-\tilde{A}\bigg{(}\tilde{c}_{1}\frac{\tilde{u}_{1}^{\star}}{\tilde{\lambda}_{1}^{\star}}+\tilde{c}_{2}\frac{\tilde{u}_{2}^{\star}}{\tilde{\lambda}_{2}^{\star}}\bigg{)}\right\|_{\infty}$
$\displaystyle\leq\frac{C\left(|c_{1}|+|c_{2}|+|\tilde{c}_{1}|+|\tilde{c}_{2}|\right)}{\sqrt{n}\log\log
n},$

for some $s_{1},s_{2},\tilde{s}_{1},\tilde{s}_{2}\in\\{\pm 1\\}$. Let

$\tau=A\bigg{(}c_{1}\frac{u_{1}^{\star}}{\lambda_{1}^{\star}}+c_{2}\frac{u_{2}^{\star}}{\lambda_{2}^{\star}}\bigg{)}+\tilde{A}\bigg{(}\tilde{c}_{1}\frac{\tilde{u}_{1}^{\star}}{\tilde{\lambda}_{1}^{\star}}+\tilde{c}_{2}\frac{\tilde{u}_{2}^{\star}}{\tilde{\lambda}_{2}^{\star}}\bigg{)}.$

Using (LABEL:two-z-choices), we can repeat the arguments above (LABEL:eq:tau),
to show that $\sqrt{n}\log(n)\tau=(1+o(1))z^{\star}$, where $z_{i}^{\star}$ is
$\alpha_{1}+\tilde{\alpha}_{1}$ on $V_{1}:=\\{u:\sigma_{0}(u)=+1\\}$ and
$\alpha_{2}+\tilde{\alpha}_{2}$ on $V_{2}:=\\{u:\sigma_{0}(u)=-1\\}$.
Consequently, with probability $1-o(1)$, for each $v\in[n]$,

$\displaystyle\sqrt{n}\log(n)\tau_{v}$
$\displaystyle=d_{+1}(v)\left(\alpha_{1}+\tilde{\alpha}_{1}\right)-d_{-1}(v)\left(y\alpha_{1}+\tilde{y}\tilde{\alpha}_{1}\right)+d_{+2}(v)\left(\alpha_{2}+\tilde{\alpha}_{2}\right)-d_{-2}(v)\left(y\alpha_{2}+\tilde{y}\tilde{\alpha}_{2}\right)+o(\log
n).$

By Proposition 2.10 and (LABEL:coeffs-2matrix), there exists some
$\varepsilon>0$ such that with probability $1-o(1)$

$\displaystyle\sqrt{n}\log(n)\min_{v\in
V_{1}}\tau_{v}\geq\frac{1}{2}\varepsilon\log n\text{ and
}\sqrt{n}\log(n)\max_{v\in V_{2}}\tau_{v}\leq-\frac{1}{2}\varepsilon\log n$

with probability $1-o(1)$. The rest of the proof is identical to the final
part of the argument in the proof of Theorem 1.7 1. ∎

##  6\. More than two communities

In this section, we will prove Theorem 1.12. Similar to Lemma 5.1, we need the
following, whose proof is provided in Appendix C.

######  Lemma 6.1.

Let $\rho\in(0,1)^{k}$, and $P\in(0,1)^{k\times k}$ be a symmetric matrix. For
any $y>0$, let $P^{\scriptscriptstyle(y)}$ be the matrix such that
$P^{\scriptscriptstyle(y)}_{ij}=\rho_{j}(P_{ij}-y(1-P_{ij}))$ for all $i,j$.
Then, either (1) $P^{\scriptscriptstyle(y)}$ has a zero eigenvalue for all $y$
or (2) $P^{\scriptscriptstyle(y)}$ has repeated eigenvalues for all $y$ or (3)
there is a finite set $\mathcal{Y}$ such that $P^{\scriptscriptstyle(y)}$ has
distinct nonzero eigenvalues for all $y\not\in\mathcal{Y}$.

Consequently, if $P^{\scriptscriptstyle(0)}:=P\cdot\text{diag}(\rho)$ has $k$
distinct, non-zero eigenvalues, then (3) holds.

Let us describe the algorithm that always succeeds up to the information
theoretic threshold in the $k$-community case.

Algorithm 7 Two-matrix community detection for general $k\geq 3$ communities

1:Parameters $t>0$, $\rho\in(0,1)^{k}$ such that $\sum_{i}\rho_{i}=1$, a
symmetric matrix $P\in(0,1)^{k\times k}$, and also
$G\sim\textsc{CSBM}_{n}^{k}(\rho,P,t)$.

2:Community classification $\hat{\sigma}\in[k]^{n}$.

3:Fix $y,\tilde{y}\notin\mathcal{Y}$ where $\mathcal{Y}$ is given by Lemma
6.1. Construct two $n\times n$ matrices $A=A(G,y)$, $\tilde{A}=A(G,\tilde{y})$
as defined in Definition 1.5.

4:Find the top $k$ eigenpairs of $A$ and $\tilde{A}$, respectively denoting
them $((\lambda_{l},u_{l}))_{l\in[k]}$ and
$((\tilde{\lambda}_{l},\tilde{u}_{l}))_{l\in[k]}$. Let $U$ (respectively
$\tilde{U}$) be the $n\times k$ matrix whose $i$-th column is $u_{i}$
(respectively $\tilde{u}_{i}$).

5:Use Algorithm 6 on input $\left(t,\rho,P,y,\tilde{y}\right)$ to compute the
weight vectors $\left(c_{i},\tilde{c}_{i}\right)_{i\in[k]}$.

6:For $s\in\\{\pm 1\\}^{k}$, let $D^{\scriptscriptstyle(s)}:=\text{diag}(s)$.
For any $s,\tilde{s}\in\\{\pm 1\\}^{k}$, construct the estimator
$\begin{split}{estimator-k-
com}\hat{\sigma}(v;s,\tilde{s})=\operatornamewithlimits{argmax}_{i\in[k]}\Big{\\{}\big{(}UD^{\scriptscriptstyle(s)}c_{i}\big{)}_{v}+\big{(}\tilde{U}D^{\scriptscriptstyle(\tilde{s})}\tilde{c}_{i}\big{)}_{v}\Big{\\}}\quad\text{
for each }v\in[n].\end{split}$ (6.1)

7:Return $\hat{\sigma}=\operatornamewithlimits{argmax}_{s,\tilde{s}\in\\{\pm
1\\}^{k}}\mathbb{P}(G\mid\hat{\sigma}(\cdot;s,\tilde{s}))$.

Algorithm 8 Find weights (Two matrices, $k\geq 3$ communities)

1:Parameters $t>0$, $\rho\in(0,1)^{k}$ such that $\sum_{i}\rho_{i}=1$, a
symmetric matrix $P\in(0,1)^{k\times k}$, and $y,\tilde{y}\notin\mathcal{Y}$
where $\mathcal{Y}$ is given by Lemma 6.1.

2:Weight vectors
$\left(c_{i},\tilde{c}_{i}\right)_{i=1}^{k}\subset\mathbb{R}^{k}$.

3:For $k\geq 1$, let $\mathcal{V}_{k}:=\\{i:n\sum_{j=0}^{k-1}\rho_{j}\leq
i\leq n\sum_{j=1}^{k}\rho_{j}\\}$ with $\rho_{0}=0$. Define $B$ to be the
symmetric block matrix where $B_{uv}=\frac{t\log n}{n}[P_{ij}-y(1-P_{ij})]$ if
$u\in\mathcal{V}_{i}$ and $v\in\mathcal{V}_{j}$. Define $\tilde{B}$ similarly
by replacing $y$ by $\tilde{y}$. Let the top $k$ eigenpairs of $B$ and
$\tilde{B}$ be $((\gamma_{i},v_{i}))_{i\in[k]}$, and
$((\tilde{\gamma}_{i},\tilde{v}_{i}))_{i\in[k]}$. Let $V$ (respectively
$\tilde{V}$) be the $n\times k$ matrix whose $i$th column is
$\nicefrac{{v_{i}}}{{\gamma_{i}}}$ (respectively
$\nicefrac{{\tilde{v}_{i}}}{{\tilde{\gamma}_{i}}}$).

4:Solve the following system for $\\{\alpha_{ri}\\}_{r,i\in[k]}$,
$\\{\tilde{\alpha}_{ri}\\}_{r,i\in[k]}$:  $\begin{split}{z-star-
gen-k}\alpha_{ri}+\tilde{\alpha}_{ri}=\log\left(P_{ri}\right),\quad-y\alpha_{ri}-\tilde{y}\tilde{\alpha}_{ri}=\log\left(1-P_{ri}\right),\quad\forall
r,i\in[k].\end{split}$ (6.2) For $i\in[k]$, let $z_{i}$ (respectively
$\tilde{z}_{i}$) be the block vector with $z_{iv}=\alpha_{ri}$ (respectively
$\tilde{z}_{iv}=\tilde{\alpha}_{ri}$) when $v\in\mathcal{V}_{r}$.

5:Return $\left(c_{i},\tilde{c}_{i}\right)_{i=1}^{k}$ solving
$\begin{split}\sqrt{n}\log(n)Vc_{i}=z_{i}\quad\text{and}\quad\sqrt{n}\log(n)\tilde{V}\tilde{c}_{i}=\tilde{z}_{i}\quad\text{for
all }i\in[k].\end{split}$ (6.3)

###### Proof of Theorem 1.12.

The argument is identical to the proof of Theorem 1.10. We skip redoing all
the details for general $k\geq 3$ and instead give an overview of the steps.

Indeed, since $P\cdot\text{diag}(\rho)$ has $k$ distinct, non-zero eigenvalues
by our assumption, Lemma 6.1 implies that the eigenvalues of
$\mathbb{E}[A(G,y)]$ are also distinct for sufficiently large $n$. Applying
the entrywise bounds for the eigenvectors in Corollary 4.2 holds for general
$k$. The parameters (LABEL:z-star-gen-k) and (6.3) are chosen in such a way
that the approximating vector $\tau$ satisfies, with probability $1-o(1)$, for
all $v\in[n]$,

$\tau_{v}=\big{(}\log(P_{ri}),\log(1-P_{ri})\big{)}_{r\in[k]}\cdot d(v)+o(\log
n).$

The estimator described by (LABEL:estimator-k-com) is constructed so that for
some $s,\tilde{s}\in\\{\pm 1\\}^{k}$, we have

$\hat{\sigma}(v;s,\tilde{s})=\operatornamewithlimits{argmax}_{i\in[k]}\tau_{v}.$

Corollary 2.11 implies that for this pair $(s,\tilde{s})$, we have
$\hat{\sigma}(v;s,\tilde{s})=\sigma_{0}(v)$ for all $v$ with high probability.
Finally, the correct pair $s,\tilde{s}$ is chosen in Step 7, by again
appealing to statistical achievability (Theorem 3.1). ∎

######  Remark 6.2.

We can simplify the algorithms by taking $A$ and $\tilde{A}$ without any
ternary encoding if both $P\cdot\text{diag}(\rho)$ and
$(J-P)\cdot\text{diag}(\rho)$ have $k$ distinct, non-zero eigenvalues. Indeed,
define $A,\tilde{A}$

$\displaystyle A_{ij}=\begin{cases}1&\quad\text{if }\\{i,j\\}\text{ is
present}\\\ 0&\quad\text{if }\\{i,j\\}\text{ is absent or
censored}\end{cases}\quad\text{and}\quad\tilde{A}_{ij}=\begin{cases}1&\quad\text{if
}\\{i,j\\}\text{ is absent}\\\ 0&\quad\text{if }\\{i,j\\}\text{ is present or
censored.}\end{cases}$

We can simply set $\alpha_{ri}=\log(P_{ri})$ and
$\tilde{\alpha}_{ri}=\log(1-P_{ri})$, and choose $c_{i},\tilde{c}_{i}$
according to (6.3). With this choice, the estimator in (LABEL:estimator-k-com)
(optimized over the signs as in Algorithm 6 Step 5) achieves exact recovery up
to the information theoretic threshold.

Of course, such a simplification might not be possible for many possible
choices of parameters. For example, in the two community case, we can take
$\rho=1/2$, and $p_{1},p_{2},q$ such that $p_{1}p_{2}-q^{2}\neq 0$ but
$(1-p_{1})(1-p_{2})-(1-q)^{2}=0$. One such choice is
$p_{1}=\frac{23}{25},p_{2}=\frac{17}{25},q=\frac{3}{5}$.

## References