# Detecting Hidden Communities by Power Iterations with Connections to Vanilla
Spectral Algorithms

Chandra Sekhar Mukherjee
Department of Computer Science
University of Southern California
<EMAIL_ADDRESS>Research supported by NSF CAREER award
2141536. Jiapeng Zhang
Department of Computer Science
University of Southern California
<EMAIL_ADDRESS>Research supported by NSF CAREER award 2141536.

###### Abstract

Community detection in the stochastic block model is one of the central
problems of graph clustering. Since its introduction by Holland, Laskey and
Leinhardt (Social Networks, 1983), many subsequent papers have made great
strides in solving and understanding this model. In this setup, spectral
algorithms have been one of the most widely used frameworks for the design of
clustering algorithms. However, despite the long history of study, there are
still unsolved challenges. One of the main open problems is the design and
analysis of “simple”(vanilla) spectral algorithms, especially when the number
of communities is large.

In this paper, we provide two algorithms. The first one is based on the power-
iteration method. This is a simple algorithm which only compares the rows of
the powered adjacency matrix. Our algorithm performs optimally (up to
logarithmic factors) compared to the best known bounds in the dense graph
regime by Van Vu (Combinatorics Probability and Computing, 2018). Furthermore,
our algorithm is also robust to the “small cluster barrier”, recovering large
clusters in the presence of an arbitrary number of small clusters. Then based
on a connection between the powered adjacency matrix and eigenvectors, we
provide a “vanilla” spectral algorithm for large number of communities in the
balanced case. This answers an open question by Van Vu (Combinatorics
Probability and Computing, 2018) in the balanced case. Our methods also
partially solve technical barriers discussed by Abbe, Fan, Wang and Zhong
(Annals of Statistics, 2020).

In the technical side, we introduce a random partition method to analyze each
entry of a powered random matrix. This method can be viewed as an eigenvector
version of Wigner’s trace method. Recall that Wigner’s trace method links the
trace of powered matrix to eigenvalues. Our method links the whole powered
matrix to the span of eigenvectors. We expect our method to have more
applications in random matrix theory.

##  1 Introduction

Community detection (graph clustering) is a fundamental problem in computer
science that has applications in diverse areas including but not limited to
physics, social sciences and biology. Among others, the _stochastic block
model_ (SBM) is one of the most widely used frameworks for studying community
detection, offering both theoretical arena for rigorous analysis of
performance of clustering algorithms as well serving as a simulation benchmark
in practice. Before proceeding ahead we briefly describe the model. There is a
set of $n$ vertices $V=\\{v_{1},\ldots,v_{n}\\}$ with a hidden partition
$\\{V_{1},\ldots,V_{k}\\}$. A graph $G$ is then sampled through a random
process, governed by a $k\times k$ symmetric matrix $W$. For any pair of
vertices $v\in V_{i}$ and $u\in V_{j}$ an edge is added between them
independently at random with probability $W_{i,j}$. This sampling process is
called $SBM(n,\\{V_{i}\\}_{i=1}^{k},W)$ Naturally, intra cluster edge
probabilities are higher than inter cluster edge probabilities. Given such a
sampled graph $G(V,E)$ (its adjacency matrix being denoted as $A$), the task
is to recover the hidden partition.

From the perspective of theoretical computer science, there has been a lot of
progress towards understanding the information theoretic and computational
limits of solving the SBM problem since the 1980s [HLL83, BCLS87, DF89,
Bop87]. We refer to the recent survey by Abbe [Abb17] for a comprehensive list
of such results. In this paper we study one of the prominent problems in
relation to SBM, which is designing of simple spectral algorithm for community
detection. Spectral algorithms have a long history of being used in the random
graph paradigm [Bop87, AKS98, McS01, Vu18, AFWZ20, MPZ22]. Several papers in
this area have concentrated on finding simplest spectral algorithms,
(sometimes called vanilla algorithms [AFWZ20]) that can solve the SBM problem
[McS01, Vu18, AFWZ20].

##### Vanilla spectral algorithms: motivation and challenges

Spectral algorithms broadly refer to algorithms that analyze the eigenvectors
of the (random) adjacency matrix $A$. In this direction most works either
analyze the entries of the eigenvectors or the projection of $A$ onto the
eigenspace of the top eigenvectors. In general, there are several steps that
precede and/or follow the obtaining of the eigenvectors/eigenspace-projection.
For example, the projection is sometimes preceded by trimming steps (such as
random partition in [Vu18]), and the post projection embedding is then
subjected to further iterative cleaning ([YP14]) , or other clustering
techniques such as K-means ([LR15]) are then implemented. The goal of
obtaining a “vanilla” spectral algorithm is to avoid such steps. On a high
level, there are two motivations. The first is to understand if an algorithm
that just applies some threshold on the entries of the eigenvectors or the
rows of the projected matrix is able to recover the partition. This also gives
intuition about power of spectral algorithms used in practice that are often
“vanilla” in this sense (such as PCA).

The next is technical motivation. As we shall explain going forward, the
difficulty in obtaining a provably correct vanilla algorithm is due to certain
technical barriers in random matrix theory. Thus, analysis of vanilla spectral
algorithm promises to improve our understanding of these hurdles which may
have application in other problems/domains. One may refer to Section 1.1.2 for
a more detailed description on motivations and progress made so far.

Although there have been several efforts and progresses made towards designing
such algorithms [AFWZ20, EBW18, Vu18], the problem of obtaining a vanilla
spectral algorithm for large $k$ remains open. We describe the approaches and
limitations of existing work in Section 1.3.

Motivated by these questions and hurdles, in this paper we continue on the
direction of obtaining vanilla spectral algorithms for SBM through resolving
barriers in random matrix theory. In our first attempt, we focus on the
symmetric SBM framework ($\mathrm{SSBM}$).

######  Definition 1.1 (Symmetric SBM).

In this model, given an $n$-vertex set $V$ with a hidden partition
$V=\cup_{i=1}^{k}V_{i}$ such that $V_{i}\cap V_{j}=\emptyset$ for all $i\neq
j$, we say a graph $G=(V,E)$ is sampled from $\mathrm{SSBM}(n,k,p,q)$, if for
all pairs of vertices $v_{i},v_{j}\in V$,

  * •

an edge $(v_{i},v_{j})$ is added independently with probability $p$, if
$v_{i},v_{j}\in V_{\ell}$ for some $\ell$;

  * •

an edge $(v_{i},v_{j})$ is added independently with probability $q$,
otherwise.

Although $\mathrm{SSBM}$ is a basic version of $\mathrm{SBM}$, due to its
simplicity it’s often used as a starting point for design of community
detection algorithms, as in [AFWZ20]. Furthermore, we work in the “dense
graph” setting ( $q\gg\frac{\log n}{n}$) which is commonly the area of
interest for spectral algorithms [McS01, Vu18, AFWZ20].

Against this backdrop, we now describe the results of our paper on a high
level.

###  1.1 Our Contribution

Our contribution is two part.

In the algorithm part, we design a simple algorithm for the $\mathrm{SSBM}$
model based on powering of the adjacency matrix of $G$. Our algorithm is
simple, and matches the best known algorithms for large $k$ [Vu18, MPZ22] upto
logarithmic factor even in the presence of an arbitrary number of small (size
$<<\sqrt{n}$) clusters. Next, by connecting power matrix and eigenvectors of
symmetric matrix, we convert our power iteration algorithm into a “vanilla”
spectral algorithm for the balanced $\mathrm{SSBM}$ case, making significant
progress w.r.t open questions (in the balanced case) raised by [Vu18] and
[AFWZ20]. More details will be discussed in Section 1.1.2.

In doing so, we also make contribution in technical analysis. We give an
analysis of eigenspaces of random matrices by using power matrix, providing
another perspective to understand random matrices. Our analysis is built on a
random partition idea. We discuss more connections between our analysis and
known analysis in Section 1.3.

####  1.1.1 Our Algorithm to Recover the Largest Partition

Our first contribution is a simple algorithm based on the power iteration
method. Given the adjacency matrix $A$ of a graph $G$ drawn in from
$\mathrm{SSBM}(n,k,p,q)$, we obtain $B$ by subtracting each entry of $A$ by
$q$. That is, $B:=A-q\cdot 1^{n\times n}$, where $1^{n\times n}$ is all one
$n\times n$ matrix . We show that the largest partition of $G$ (under
reasonable constraints) can be recovered by comparing the euclidean distance
of rows of $B^{r}$ for $r\approx\log n$. We describe the procedure in
Algorithm 1.

For a vertex $v_{i}\in V$, let the $i$-th row of $A$ (and $B$) correspond to
$v_{i}$, and $V_{1}$ be the largest (hidden) partition of $G$. For any fixed
$v_{i}\in V_{1}$, we show that there is a threshold $\Delta$ such that with
high probability for all $v_{j}\in V_{1}$, the distance between the $i$-th and
$j$-th row of $B^{r}$ is less than $\Delta$. Otherwise ($v_{j}\not\in V_{1}$)
the distance is larger than $1.1\Delta$, which is sufficient to recover
$V_{1}$.

1: Input: A graph $G$ and parameters $p,q>0$.

2: Let $A$ be the adjacent matrix of $G$

3: $B\leftarrow A-q\cdot\mathbf{1}^{n\times n}$ COMMENT# (Here
$\mathbf{1}^{n\times n}$ is the all $1$ matrix.)

4: Let $\Delta>0$ and $r>1$ be parameters COMMENT# (We will explain how to
choose them later)

5: for $v_{i},v_{j}\in G$ do

6: if $\|B^{r}_{i}-B^{r}_{j}\|_{2}\leq\Delta$ then

7: Put $v_{i}$ and $v_{j}$ in a same cluster COMMENT# ($B^{r}_{i}$ represents
the $i$-th row of $B^{r}$)

8: end if

9: end for

10: Output the sets thus formed.

Algorithm 1 Detecting Communities by Power Iterations

The correctness of Algorithm 1 can be formalized as follows.

######  Theorem 1.2 (Recovering largest cluster).

There are constants $C,C_{0}>0$ such that the following holds. Let $p,q\leq
0.75$ be parameters such that $\max\\{p(1-p),q(1-q)\\}\geq C_{0}(\log n)/n.$
Let $G$ be a random graph sampled from $\mathrm{SSBM}(n,k,p,q)$, and let
$s^{*}$ be the size of the largest cluster. If $s^{*}\geq C\cdot(\log
n)^{7}\cdot\sqrt{p(1-q)}\cdot\sqrt{n}/(p-q)$, then with probability
$1-\mathcal{O}(1/n)$ one of the cluster output by Algorithm 1 is the largest
cluster of $G$ for suitable choice of $\Delta$ and $r$.

##### Comparison to best known result.

In the line of spectral algorithms, the state of the art for large $k$ is
provided by Vu [Vu18] which proved that if each cluster has size larger than
$C\cdot(\log n)\cdot\sqrt{p(1-q)}\cdot\sqrt{n}/(p-q)$, then a spectral
algorithm can recover all clusters. In fact, most community recovery
algorithms require “all” clusters to be large. This constraint was termed as
the “small cluster barrier” by Ailon et al. [ACX13]. Recently the work by
Mukherjee et al. [MPZ22] provided an algorithm for this problem building on
Vu’s algorithm that does not need any size constraint on the clusters that are
not the largest. They showed that if $(p-q)s^{*}\geq
C_{0}\sqrt{p(1-q)}\sqrt{n}\log n$, then their algorithm is able to recover the
largest cluster. Our algorithm is also able to bypass the small cluster
barrier and recover the largest cluster in the presence of small clusters. Our
algorithm has an additional $(\log n)^{6}$ factor than [MPZ22] but is far
simpler in comparison.

####  1.1.2 Towards Vanilla Spectral Algorithms

Now we discuss the study of simple (vanilla) spectral algorithms, further
describing the motivation, progress made so far and the open problems, before
recording our contribution.

There are two primary motivations. The first, as stated in [Vu18] is to design
theoretically provable natural algorithms. Many spectral algorithms used in
practice, such as PCA do not have any pre-processing or post-processing steps
akin to that of [LR15, Vu18, YP14]. The second is to simply understand the
power of just SVD projection in community recovery, and understanding the
extent of its success w.r.t information theoretic bounds, which was the
motivation in [AFWZ20].

Beyond these, since the present analysis is limited by certain hurdles in
random matrix theory (as we discuss in later sections), we hope that studying
this problem also furthers our understanding of random matrices, which is the
technical motivation of this paper.

Against this background, Abbe et al. in their beautiful work [AFWZ20] designed
a vanilla spectral algorithm for $k=2$ clusters that recovers up to the
information-theoretic bound. The algorithm is very simple. Obtain the second
eigenvector of $A$, and if an entry is positive, then the corresponding vertex
belongs to one cluster, otherwise to a different cluster. However, they could
not extend analysis for $k\geq 3$.

##### Spectral algorithms for large $k$:

In this paper we concentrate on the case of $k=\omega(\log n)$. In this domain
the seminal work by McSherry [McS01] provided a spectral algorithm to solve
the hidden partition problem. However, this algorithm required a combinatorial
and iterative partition of the vertices based on SVD projection of $A$.
McSherry asked whether this step can be simplified, and this was answered by
Vu [Vu18]. To our best knowledge, this is the simplest spectral algorithm for
$k=\omega(\log n)$. We describe this in Algorithm 2, described as the SVD-II
algorithm by Vu 111This is not exactly the same as Vu’s algorithm but captures
the main idea..

1: Input: A graph $G=(V,E)$ and parameters $p,q,k>0$.

2: Let $A$ be the adjacent matrix of $G$

3: Randomly partition $V$ into two parts $V_{1}$ and $V_{2}$

4: Let $A_{1}$ be the adjacency matrix of the subgraph induced by $V_{1}$

5: for $\bm{u}\in V_{2}$ do

6: Let $P^{k}_{A_{1}}\bm{u}$ be the projection of $\bm{u}$ into the space
spanned by the first $k$ eigenvectors of $A_{1}$

7: end for

8: Choose a parameter $\Delta>0$

9: for $\bm{u},\bm{v}\in V_{2}$ do

10: if $\|P^{k}_{A_{1}}\bm{u}-P^{k}_{A_{1}}\bm{v}\|_{2}\leq\Delta$ then

11: Put $\bm{u}$ and $\bm{v}$ in a same cluster

12: end if

13: end for

Algorithm 2 Vu’s Spectral Algorithm to Detect Hidden Communities (SVD II in
[Vu18])

In brief, the adjacency matrix $A$ is partitioned randomly in two halves
$A_{1}$ and $A_{2}$, and then columns of $A_{2}$ are projected onto the first
$k$ eigenvectors of $A_{1}$, and then the post projected columns of $A_{2}$
can be separated by clustering via distance based on some threshold. The key
reason behind this partition is that the eigenvectors of $A_{1}$ and the
columns of $A_{2}$ are uncorrelated, which aids the analysis. Once $A_{2}$ is
clustered, recovering the communities from $A_{1}$ is relatively
straightforward. Although this algorithm is simpler in comparison to [McS01],
there is a step that seems redundant. Specifically, the _partition before
projection_ step. This was also noted by Vu [Vu18], and he proposed the
following algorithm, that he named SVD-I.

##### SVD-I and the barrier in analysis

First we describe the conjectured algorithm by Vu [Vu18] in Algorithm 3.

1: Input: A graph $G=(V,E)$ and parameters $p,q,k>0$.

2: Let $A$ be the adjacency matrix of $G$

3: Let $P^{k}_{A}$ be the projection operator into the space spanned by the
first $k$ eigenvectors of $A$

4: Choose a parameter $\Delta>0$

5: for $\bm{u},\bm{v}\in V$ do

6: if $\|P^{k}_{A}\bm{u}-P^{k}_{A}\bm{v}\|_{2}\leq\Delta$ then

7: Put $\bm{u}$ and $\bm{v}$ in a same cluster

8: end if

9: end for

Algorithm 3 SVD I in [Vu18]

Note that compared to SVD-II, SVD-I does not have any partition. $A$ is simply
projected onto the space of its first $k$ eigenvectors. The main barrier in
analysis is as follows. In SVD-I, the eigenvectors and columns of $A$ are
correlated. This was also pointed out by Vu.

> _Compared to SVD I, the extra steps in SVD II are the random partitions,
> done in order to reduce correlation._

In this regard, SVD-I is a more natural and intuitive algorithm, akin to
widely popular algorithms used in practice such as principle component
analysis (PCA). The problem of whether SVD-I can be proven to be correct was
left as an open problem in [Vu18]. In this note Vu remarked

> _While SVD I could well win the contest for being the simplest algorithm,
> and perhaps the first one that most practitioners of the spectral method
> would think of, it is hard to analyse in the general case. In what follows,
> we analyse a slightly more technical alternative, SVD II_

This presence of correlation is the technical barrier that we address in this
paper. We show that a slightly different algorithm from SVD-I works in the
balanced case using our power iteration based analysis.

##### The $\mathrm{USSBM}$ model and our centered-SVD algorithm

The $\mathrm{USSBM}$ setup is the balanced case of the symmetric SBM case.
That is, if there are $k$ hidden partitions, then each vertex is assigned a
partition uniformly at random. This implies the size of the partitions are
fairly balanced. We note that the $\mathrm{USSBM}$ could be the first step
towards the general $\mathrm{SBM}$ problem.

In this paper, our main focus is on addressing the correlation barrier in
[Vu18]. In this model we show Algorithm 4 recovers the hidden communities
under conditions comparable to that of the more complex SVD-II algorithm by Vu
[Vu18].

1: Input: A graph $G=(V,E)$ and parameters $p,q,k>0$.

2: Let $A$ be the adjacent matrix of $G$

3: $B\leftarrow A-q\cdot\mathbf{1}^{n\times n}$ COMMENT# (This is the extra
step compared to SVD-I)

4: Let $P^{k}_{B}$ be the projection operator into the space spanned by the
first $k$ eigenvectors of $B$

5: Choose a parameter $\Delta>0$ depending on $n,k,p,q$

6: for $\bm{u},\bm{v}\in V$ do

7: if $\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|_{2}\leq\Delta$ then

8: Put $\bm{u}$ and $\bm{v}$ in a same cluster

9: end if

10: end for

Algorithm 4 Centered-SVD

As we aim for a vanilla algorithm, the idea is very simple. Given the
adjacency matrix $A$, shift each entry by $q$ to obtain $B$. Then project the
columns of $B$ onto the span of the first $k$ eigenvectors of $B$, and cluster
based on a threshold on distance between the projected rows. We have the
following theorem for its correctness.

######  Theorem 1.3 (Centered SVD algorithm).

There are constants $C_{0},C_{1}>0$ such that the following holds. Let
$p,q\leq 0.75$ be parameters such that $\max\\{p(1-p),q(1-q)\\}\geq C_{0}(\log
n)/n$. Let $G$ be a random graph sampled from $\mathrm{USSBM}(n,k,p,q)$. If
$n\geq C_{1}\cdot(\log n)^{14}\cdot p(1-q)\cdot k^{2}/(p-q)^{2}$ then the
centered SVD (Algorithm 4) recovers all the clusters with probability
$1-\mathcal{O}(1/n)$.

To the best of our knowledge, this is the first spectral algorithm without
pre-SVD partition or post-SVD trimming steps that recover algorithm in the
balanced case for $p,q=o(1)$ and $k=\omega(\log n)$. In fact, our parameters
are comparable to that of SVD-II, which is a more complex (non-vanilla)
algorithm. We finish this discussion with some remarks about our algorithm.

######  Remark 1.4 (Notes on centering).

We further emphasize that even though we slightly deviate from SVD-I, our
additional step of shifting is not synthetic. The step of shifting each entry
of $A$ by $q$ is essentially a centering step. Centering is a common step done
in clustering algorithms, even beyond the $\mathrm{SBM}$ setup.

For example, the algorithm PCA can be thought of as SVD projection of the
centered matrix. Centering is done to remove the effect of the top eigenvector
of the matrix, which often aligns close to the data mean and does not reveal
knowledge about cluster identities. Our analysis of the centered-SVD algorithm
thus provides insight towards the success of simple algorithms used in
practice.

Furthermore, $A$ and $B$ are only separated by a constant ($q$). Thus we
believe an analysis of the eigenspace of $A$ is also possible in a similar
manner. This remains an interesting problem.

Now we describe the outline of our proofs.

###  1.2 Proof Outlines

####  1.2.1  Proof Outline of Theorem 1.2

We first revisit some notations. Recall that $A\sim\mathrm{SSBM}(n,k,p,q)$ is
the adjacency matrix of the random graph, and $B:=A-q\cdot 1^{n\times n}$ is
the matrix obtained by shifting each entry of $A$ by $q$. As described in
Algorithm 1, we aim to recover the largest cluster based on the $\ell_{2}$
distance of rows of the power matrix $B^{r}$ where $r=\log n$.

Specifically, our goal is the following. Let $v_{i}$ and $v_{j}$ be two
vertices corresponding to the $i$-th and $j$-th row of $A$ (and thus, $B$). We
want to show that if $v_{i}$ and $v_{j}$ both belong to a large enough cluster
then the distance of $i$-th and $j$-th row of $B^{r}$ is small. On the other
hand, if $v_{i}$ belongs to a large enough cluster and $v_{j}$ belongs to a
different cluster, the distance between the rows of $B^{r}$ is much larger.
This allows us to recover a large cluster through distance based separation.

With this aim, we decompose $B=L+R$ where $L:=\mathbb{E}[B]$ is the “structure
part” of this matrix containing the hidden community information, and $R$ is
the “noise part”. We notice that $R$ is a symmetric matrix where each entry is
a $0$ mean independent random variable.

In this regard, we can write $B^{r}$ as $(L+R)^{r}$ and our aim is to show
that when considering the distance between two rows of $B^{r}$, the distance
due to $L^{r}$ is the dominating component. Here $L$ is a well structured
matrix. By a simple calculation, for any two vertices $v_{i}$ and $v_{j}$,

  * •

If $v_{i}$ and $v_{j}$ belong to the same cluster, then the distance between
$i$-th and $j$-th row of $L^{r}$ is $0$.

  * •

Otherwise if $v_{i}\in V_{\ell}$ and $v_{j}\in V_{\ell^{\prime}}$ are from two
different clusters, the distance between their rows is more than
$\max\left\\{\sqrt{|V_{\ell}|}(p-q)^{r}|V_{\ell}|^{r-1},\sqrt{|V_{\ell^{\prime}}|}(p-q)^{r}|V_{\ell^{\prime}}|^{r-1}\right\\}$.

We then show that the $\ell_{2}$ norm of rows of $B^{r}-L^{r}$ is small
(compared to the gap provided by $L^{r}$) by using ideas from random matrix
theory and concentration bounds on low degree polynomials. We use a two step
decomposition to achieve this. In the first step we decompose

$B^{r}=(L+R)^{r}=L^{r}+\underbrace{L^{r-1}R+L^{r-2}RB+\cdots
LRB^{r-2}}_{M}+RB^{r-1}$

This is a decomposition based on the first location of $R$ in the product
terms.

##### Analysis of $M$.

We first show that the $\ell_{2}$ norm of rows of $M$ is small with high
probability. To achieve this, we start by showing that the absolute value of
entries of $L^{t}R$ is sufficiently small (with high probability), which is
fairly straightforward as the entries of $L^{t}R$ is just a linear combination
of independent random variables $R_{i,j}$. This gives us an upper bound on the
norm of rows of $L^{t}R$. We shall show that once this is upper bounded,
bounding the norm of rows of $L^{t}RB^{r-t-1}$ follows from some useful tools
of random matrix theory [FK81, Vu05].

##### Analysis of $RB^{r-1}$.

Then, we are left with bounding the term $RB^{r-1}$. This time we decompose
based on the first location of $L$, obtaining

$RB^{r-1}=\underbrace{RLB^{r-2}+R^{2}LB^{r-3}+\cdots
R^{r-1}L}_{M^{\prime}}+R^{r}$

We can view $R^{r}$ as a completely noisy component. One can also get a high
level intuition behind the success of power method from the analysis of
$R^{r}$. According to condition of Theorem 1.2, we have that spectral norm of
$L$ is much larger than that of $R$. However, the $\ell_{2}$ norm of rows of
$L$ corresponding to the largest cluster can still be smaller than the
$\ell_{2}$ norm of rows of $R$. But when we raise the matrix to its $r$-th
power for a large enough $r$, we will observe that rows of $L^{r}$ have much
higher norm than that of $R^{r}$. This shows that powering reduces the effect
of noise on the $\ell_{2}$ norm of the rows.

##### Analysis of $M^{\prime}$.

Finally, we upper bound norm of rows of $M^{\prime}$, for which we bound the
absolute value of the entries of $R^{t}L$. This is our main technical
contribution. We observe that each entry of this matrix is a low degree
($t\leq\log n$) polynomial of the random variables $R_{i,j}$ where there is
correlation between the different monomials. We use a random partition based
analysis to bound the entries, and this is arguably the most non-trivial step
in our analysis.

##### Analyzing entries of $R^{t}L$ via random partition.

We can write down the $(a,b)$-th entry of $R^{t}L$ (where $1\leq a,b\leq n$)
as

$(R^{t}L)_{a,b}=\sum\limits_{(\ell_{1},\ldots,\ell_{t})\in[n]^{t}}R_{a,\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},b}$

Then $(R^{t}L)_{a,b}$ is a sum of multivariate monomials, where each monomial
is uniquely defined by an index list $\mathcal{L}=(\ell_{1},\ldots,\ell_{t})$.
Against this setup, we divide the lists $\mathcal{L}$ into several groups
through an encoding (that we describe in Section 5) into a $t$-length array
$X$ based on duplicacy in the entries of the index lists. All the index lists
that are mapped into the same encoding $X$ are assigned into a group
$\zeta_{X}$. Let the set of all $X$ be $\mathcal{X}$. Then we have

$(R^{t}L)_{a,b}=\sum_{X\in\mathcal{X}}\underbrace{\left(\sum_{(\ell_{1},\ldots,\ell_{t})\in\zeta_{X}}R_{a,\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},b}\right)}_{Z^{t}_{a,b}(X)}$

We show that $|\mathcal{X}|\leq t^{t}$ and then upper bound
$\left|Z^{t}_{a,b}(X)\right|$ for any arbitrary $X$, and complete the proof
through an union bound.

For the purpose of explanation, here we focus on the group
$\zeta_{X^{\prime}}$ such that any index list
$(\ell_{1},\ldots,\ell_{t})\in\zeta_{X^{\prime}}$ is made of $t$ many
different values. As a consequence, $Z^{t}_{a,b}(X^{\prime})$ is a multilinear
polynomial. As we shall see, this fact simplifies our analysis. Note that
$Z^{t}_{a,b}(X^{\prime})$ is a “sum of correlated product terms” (SOP), as the
same random variable $R_{i,j}$ can occur in many monomials.

Against this setup, we layout our random partition idea. Let $T$ be a random
partition of $\\{1,\ldots,n\\}$ into $t$ many sets $T_{1},\ldots,T_{t}$ where
each element in $[n]$ is assigned to one of the $t$ many sets uniformly at
random. Then we denote

$|S_{T}|:=\left|\sum\limits_{\ell_{1}\in T_{1},\ldots,\ell_{t}\in
T_{t}}R_{a,\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},b}\right|=\Bigg{|}\sum\limits_{\ell_{1}\in
T_{1},\ldots,\ell_{t-1}\in T_{t-1}}R_{a,\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-2},\ell_{t-1}}\underbrace{\left(\sum_{\ell_{t}\in
T_{t}}R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},j}\right)}_{F(t-1,\ell_{t-1})}\Bigg{|}$

We first observe that for each $\ell_{t-1}$, $F(t-1,\ell_{t-1})$ is a
summation of independent random variables with range in $[-1,1]$. Hence we can
apply a Chernoff bound on random variables $R_{\ell_{t-1},\ell_{t}}$ where
$\ell_{t-1}\in T_{t-1}$ and $\ell_{t}\in T_{t}$ to upper bound
$|F(t-1,\ell_{t-1})|$. Assume that we upper bound this quantity by $\beta$
with high probability. We can carry out this process recursively to analyze
$S_{T}$. Precisely, we have

$|S_{T}|=\Bigg{|}\sum\limits_{\ell_{1}\in T_{1},\ldots,\ell_{t-2}\in
T_{t-2}}R_{a,\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-3},\ell_{t-2}}\underbrace{\sum_{\ell_{t-1}\in
T_{t-1}}R_{\ell_{t-2},\ell_{t-1}}F(t-1,\ell_{t-1}}_{F(t-2,\ell_{t-2})})\Bigg{|}$

We want to upper bound $\left|F(t-2,\ell_{t-2})\right|$ in a similar manner.
Here observe that since $R_{\ell_{t-2},\ell_{t-1}}$ is a zero mean random
variable, so is $R_{\ell_{t-2},\ell_{t-1}}F(t-1,\ell_{t-1})$, as
$F(t-1,\ell_{t-1})$ is a constant for any $\ell_{t-1}\in T_{t-1}$. This is
because we have already sampled (fixed) the random variables
$R_{\ell_{t-1},\ell_{t}}$.

Furthermore, as $|R_{\ell_{t-2},\ell_{t-1}}\cdot F(t-1,\ell_{t-1})|\leq\beta$
with high probability, we can then apply Chernoff bound to upper bound
$\left|F(t-2,\ell_{t-2})\right|$. We keep repeating this step recursively and
bound $|S_{T}|=\left|F(0,\ell_{0})\right|$ with high probability for any fixed
$T$. The crux here is that $T_{1},\dots,T_{t}$ are disjoint, so we can
iteratively apply the Chernoff bound $t$ times.

However, for any fixed partition $T$, $S_{T}$ does not cover all monomials in
$Z^{t}_{a,b}(X^{\prime})$. But as $T$ is designed uniformly at random, any
monomial in $Z^{t}_{a,b}(X^{\prime})$ has an equal and a relatively large
chance of being represented in $S_{T}$. We use this fact to show
$|Z^{t}_{a,b}(X^{\prime})|\leq f(t)\cdot\mathbb{E}_{T}[|S_{T}|]$ for a
reasonably small $f(t)$.

We have so far bound $|S_{T}|$ with high probability only for any fixed $T$.
What we want is to bound $\mathbb{E}[|S_{T}|]$. Here taking a union bound on
all choices of $T$ is not a possibility due to the fact that there can be
exponentially many such sets $T$. Instead we use Markov’s higher moment ideas
to obtain bounds, which completes our proof.

We remark that the intuition behind our encoding scheme is to generalize the
conversion from SOP into POS beyond the simple case described above, which is
aided by our scheme. Next, we consider the summation $Z^{t}_{a,b}(X)$ for a
generic $X\in\mathcal{X}$. Here we encounter sums of monomials where
individual variables may have degree more than $2$ in the monomials. We use
similar arguments as the case above to bound the sum for all such groups. Then
taking an union bound on all $Z^{t}_{a,b}(X)$ upper bounds $|(R^{t}L)_{a,b}|$.
Again, once the absolute value of the entries of $R^{t}L$ is bounded, an upper
bound on the norm of rows of $R^{t}LB^{r-t-1}$ follows.

The complete proof of the random partition analysis can be found in Section 5.
Next we describe the outline of the proof for our centered SVD algorithm,
which builds up on the power iteration.

####  1.2.2  Outline of Theorem 1.3

We use our analysis in the spectral algorithm for the $\mathrm{USSBM}$ model.
The key observation is as follows. Let $P^{k}_{B}$ be the SVD projection
operator onto the first $k$ eigenvectors of $B$. Let $\bm{u}$ and $\bm{v}$ be
the $i$-th and $j$-th column of $B$. Then we show that the distance between
$P^{k}_{B}\bm{u}$ and $P^{k}_{B}\bm{v}$ is well approximated by the distance
between the $i$-th and $j$-th row of $B^{r+1}$. Then the result follows from
the power iteration method. This analysis implies that in the centered case,
the partition step for reducing correlation described in SVD-II is indeed a
technical step, and is not a necessity (at least for the nearly balanced
case). To the best of our knowledge, this is the first analysis of a “simple”
spectral algorithm that is applicable for $p,q=o(1)$ and $k=\omega(\log n)$.
Next, we discuss some connections between our result and existing works.

###  1.3 Connections to Other Techniques

In this section, we discuss connections between our analysis and some standard
techniques in random matrix theory, and the challenges therein. We believe
that our method can be helpful in resolving some barriers in previous
analysis.

##### An analogue of Wigner’s trace method.

In random matrix theory, it is very important to understand the distribution
of eigenvalues (or singular values) of random matrices. However, it is always
not easy to analyze eigenvalues directly. To solve this question, Wigner
[Wig58] proposed to use the following equality:

$\sum_{i}\lambda_{i}(A)^{k}=\mathbf{Trace}(A^{k}),$

where $\lambda_{i}$ is the $i$-th singular value of $A$. Then this question
can be translated to the analysis of the diagonal entries (trace) of the power
matrix $A^{k}$. Please see [FK81, Vu05] for more details. The entries of
$A^{k}$ is a more intuitive notion than eigenvalues and we have combinatorial
tools, such as the tree encoding scheme [FK81, Vu05], to analyze it. However,
in many applications (including but not limited to analysis of vanilla
spectral algorithms), one needs to analyze the eigenvectors of $A$, and/or the
eigenspace formed by top eigenvectors of $A$. In this direction, our idea can
be considered as a link between entries of power matrices and projection onto
eigenspace for random matrices, as we analyze eigenspace projection (Theorem
1.3) through entry-wise analysis (not only diagonal entries) of $A^{k}$.

Next, we discuss some of the standard tools used in the analysis of
eigenvectors and eigenspaces, along with their limitations and potential ways
forward.

##### Beyond Davis-Kahan.

The SBM problem can be thought as a “structure+noise” problem, where the mean
($\mathbb{E}[A]$) contains the hidden partition and $R:=A-\mathbb{E}[A]$ is
the random perturbation (noise). One of the core ideas behind the spectral
algorithms is to show that the eigenspaces due to the top eigenvectors of $A$
and $\mathbb{E}[A]$ are similar. In this direction, the Davis-Kahan
$\sin(\Theta)$ theorems [DK69] are arguably the most standard way of bounding
the distances between these eigenspaces. However, although Davis-Kahan is
tight when the perturbation is chosen adversarially, it is sometimes sub-
optimal when the perturbation is random, as is the case of the SBM problem.
Then one needs to either use Davis-Kahan $\sin(\Theta)$ more subtly, or avoid
it altogether. Please see [EBW18] for more discussions about Davis-Kahan and
SBM. In this direction, Eldridge et al. [EBW18] made an effort to analyze SBM
beyond Davis-Kahan (a part of their proof also used power iteration). However,
their analysis seems complicated and hard for large $k$ (the number of
clusters). Furthermore, Abbe et al. [AFWZ20] also indicated some vague
connections between power iteration and Davis-Kahan. They comment,

> _Nevertheless, we believe the iterative perspective is helpful to many other
> (nonconvex) problems where a counterpart of Davis-Kahan theorem is absent._

To summarize, power iteration based techniques seems to be promising in
analysis of many applications beyond the limits of Davis-Kahan.

##### Beyond individual eigenvector analysis.

Although the aforementioned works improved on Davis-Kahan bounds, a common
theme in both of the papers is analysis of the individual eigenvectors.
Specifically, they analyze the distance between individual eigenvectors of the
expectation and perturbed matrices. However, if the expectation matrix
$\mathbb{E}[A]$ has high duplicity for any one eigenvalue (which is the case
with the balanced SBM model,
$\lambda_{2}(\mathbb{E}[A])=\cdots=\lambda_{k}(\mathbb{E}[A])$), either the
methods do not apply directly, or there is an adversarial cost in the bounds
depending on this duplicity.

In comparison, we do not analyze individual eigenvectors. Our analysis studies
the whole eigenspace generated by top eigenvectors. We note that McSherry
[McS01] and then Vu [Vu18] (SVD-II) also analyzed whole eigenspace. Hence,
they do not have the multiple eigenvalue barrier. However, they needed to use
a partition step in their algorithm to analyze it, to reduce correlation. In
contrast, we analyze the entries of power matrices, which addresses the
technical barriers mentioned above.

###  1.4 Conclusion and Future Directions

In this paper we present a simple algorithm based on the power iteration
method to recover communities in the $\mathrm{SSBM}$ model. Our algorithm
works in the presence of small clusters, with recovery conditions being
logarithmically close to the state of the art [Vu18, MPZ22].

Next, we connect SVD projection to the power iteration method in the (almost)
balanced case, and obtain a vanilla spectral algorithm for $k=\omega(\log n)$
and $p,q=o(1)$, with recovery guarantee comparable to that of Vu [Vu18].

The central idea behind analysis of entries of power matrices of $B$ (the
shifted adjacency matrix) is the random partition technique. We analyze
entries of powers of the matrices as low degree polynomials, that can be seen
as a sum of correlated monomials. We convert these into product of sums of
lower-degree uncorrelated monomials. This perspective allows us to improve on
restrictions of related existing works, such as the pre-projection partition
of Vu [Vu18], and need for number of clusters to be constant ([EBW18]) among
others. Furthermore, we believe these tools can be of independent interest in
analysis of the “structure+noise” model.

##### Challenges.

In the current form we can only establish the link between the power iteration
method and SVD projection when the top $k$ eigenvectors of $A$ have similar
eigenvalues. This is the reason we only focus on the uniform $\mathrm{SSBM}$
model. Extending this method for a more general case remains a very
interesting research direction.

Another question of interest is replacing the shifting procedure in the power
iteration method. Analyzing whether a shifting procedure based on $A$ (instead
of knowledge of $q$) works is an interesting vertical, making the algorithm
more practical.

##  2 Preliminaries

Here we define the notations and definitions we use throughout the paper. We
start with spectral properties of the random matrices related to the graph
generated through $\mathrm{SSBM}$.

##### Eigenvalues of the (centered) adjacency matrix

Recall that we are given the random adjacency matrix $A$ that is sampled
according to the underlying $\mathrm{SSBM}$ framework. In this paper we work
with the centered adjacency matrix $B$, which is obtained by subtracting $q$
from every entry of $A$. The expectation matrix of $B$, denoted as
$\overline{B}$ is thus a block diagonal matrix, with each entry being $p-q$ or
$0$. Then we have that $\lambda_{i}(\overline{B})=(p-q)|V_{i}|,1\leq i\leq k$.
The primary difference in our algorithm from SVD I is that we consider the
matrix $B$ instead of $A$. Now, we define some norm notations, followed by
results on spectral norms of symmetric matrices.

######  Definition 2.1 (Norm-related notations).

For any matrix $M$, we denote by $M_{i}$ the $i$-th row of $M$. In this
direction, for a matrix $M$,

  * •

$\|M\|$ denotes the spectral norm of the matrix.

  * •

$\|M_{i}\|$ denotes the $\ell_{2}$-norm of the $i$-th row of $M$

  * •

$\|M\|_{row}$ denotes the maximum of the $\ell_{2}$-norm of the rows of $M$.

######  Lemma 2.2 (Norm of a random matrix [Vu18]).

There is a constant $C_{0}>0$ such that the following holds. Let $E$ be a
symmetric matrix whose upper diagonal entries $e_{ij}$ are independent random
variables where $e_{ij}=1-p_{ij}$ or $-p_{ij}$ with probabilities $p_{ij}$ and
$1-p_{ij}$ respectively, where $p_{ij}\in[0,1]$. Let
$\sigma^{2}:=\max_{ij}\\{p_{ij}(1-p_{ij})\\}$. If $\sigma^{2}\geq C_{0}\log
n/n$, then

$\Pr[\|E\|\geq C_{0}\sigma n^{1/2}]\leq n^{-3}$

######  Lemma 2.3 (Weyl’s inequality).

Let $A=\overline{A}+E$ be a matrix. Then
$\lambda_{t+1}(A)\leq\lambda_{t+1}(\overline{A})+\|E\|$.

We have the following simple corollary.

######  Corollary 2.4.

Let $A=\overline{A}+E$ be the empirical adjacency matrix. Then with
probability at least $1-n^{-3},$we have that

$\lambda_{i}(\overline{A})-C_{0}\sigma
n^{1/2}\leq\lambda_{i}(A)\leq\lambda_{i}(\overline{A})+C_{0}\sigma n^{1/2}$

for every $i\in[n]$.

Next we write down the Chernoff-Hoeffding bound for small probability events.

######  Theorem 2.5 (Chernoff Hoeffding bound [Hoe63]).

Let $X_{1},\ldots,X_{n}$ be i.i.d random variables that can take values in
$\\{0,1\\}$, with $\mathrm{E}[X_{i}]=p$ for $1\leq i\leq n$. Then we have

  1. 1.

$\Pr\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}\geq p+\varepsilon\right)\leq
e^{-D(p+\varepsilon||p)n}$

  2. 2.

$\Pr\left(\frac{1}{n}\sum_{i=1}^{n}X_{i}\leq p-\varepsilon\right)\leq
e^{-D(p-\varepsilon||p)n}$

We have now also presented the notions needed to define a suitable constant
$C$ in Theorem 1.2.

######  Definition 2.6 (The constant $C$).

We define $C:=C_{0}\cdot 10^{7}$ where $C_{0}$ is the constant referred in
Lemma 2.2.

Thus, under the condition of Theorem 1.2 we have $(p-q)s^{*}\geq 10^{6}\cdot
C_{0}\cdot\sqrt{p(1-q}\cdot\sqrt{n}\cdot(\log n)^{7}$.

We conclude this section by defining some more notations and assumptions that
we use throughout the paper.

  1. 1.

We denote the vertices of the graph with the corresponding row/column. For two
integers $i$ and $j$, we write $i\sim j$ if the $i$-th and $j$-th vertices
belong to the same cluster, and $i\nsim j$ otherwise.

  2. 2.

For the cluster $V_{\ell}$, we denote the size of the cluster by $s_{\ell}$.
Furthermore, by $s^{*}$ and $s_{\min}$ we denote the size of the largest and
the smallest cluster respectively.

##  3 Analysis of the Power-iteration Method

In this section, we prove Theorem 1.2. Recall that
$A\sim\mathrm{SSBM}(n,k,p,q)$ is the adjacency matrix and $B:=A-q\cdot
1^{n\times n}$ is the centered matrix. Let $V_{1}$ be the largest hidden
cluster with $s^{*}=|V_{1}|$. Theorem 1.2 aims to show that there exists some
threshold $\Delta$ such that with high probability for any $v_{i}$ and
$v_{j}$,

  1. 1.

If $v_{i},v_{j}\in V_{1}$ then $\|B^{r}_{i}-B^{r}_{j}\|\leq\Delta/2$.

  2. 2.

If $v_{i}\in V_{1}$ and $v_{j}\not\in V_{1}$, then
$\|B^{r}_{i}-B^{r}_{j}\|\geq\Delta$.

This separation shows that Algorithm 1 is able to detect $V_{1}$ correctly,
which finishes the proof Theorem 1.2. We choose
$\Delta:=0.5\sqrt{s^{*}}(p-q)^{r}(s^{*})^{r-1}$ for Algorithm 1.

Continuing from Section 1.2.1, we decompose $B=L+R$ where $L=\mathbb{E}[B]$ is
the structure part and $R$ is the noise part. Hence, $B^{r}$ can be decomposed
as

$B^{r}=L^{r}+M+M^{\prime}+R^{r}$ (1)

where $M=L^{r-1}R+L^{r-2}RB+\dots+LRB^{r-2}$ and
$M^{\prime}=RLB^{r-2}+R^{2}LB^{r-3}+\cdots+R^{r-1}L$.

As we discussed in Section 1.2.1, we would like to show that $L^{r}$ is the
dominant part in $B^{r}$. That is,
$\|B_{i}^{r}-B_{j}^{r}\|\approx\|L_{i}^{r}-L_{j}^{r}\|$ for every $i,j$. From
Equation 1 we have for any $i,j$

$\displaystyle\left|\|B^{r}_{i}-B^{r}_{j}\|-\|L^{r}_{i}-L^{r}_{j}\|\right|$
$\displaystyle\leq$
$\displaystyle\|(B^{r}_{i}-L^{r}_{i})-(B^{r}_{j}-L^{r}_{j})\|$
$\displaystyle\leq$
$\displaystyle\|M_{i}-M_{j}\|+\|M_{i}^{\prime}-M_{j}^{\prime}\|+\|R^{r}_{i}-R^{r}_{j}\|$
$\displaystyle\leq$ $\displaystyle
2(\|M\|_{row}+\|M^{\prime}\|_{row}+\|R^{r}\|_{row})$

The proof then progresses in the following manner.

  * •

Lemma 3.2 first shows there is separation on $L$. That is, for every
$v_{i},v_{j}\in V_{1}$, $\|L_{i}^{r}-L_{j}^{r}\|=0$; for every $v_{i}\in
V_{1}$ and $v_{j}\not\in V_{1}$, $\|L_{i}^{r}-L_{j}^{r}\|\geq 2\Delta$

  * •

Corollary 3.6 shows that $\|M\|_{row}\leq 0.1\Delta$ with probability
$1-\mathcal{O}(1/n)$.

  * •

Lemma 3.7 shows that $\|R^{r}\|_{row}\leq 0.1\Delta$ with probability
$1-\mathcal{O}(1/n)$.

  * •

Corollary 3.9 shows that $\|M^{\prime}\|_{row}\leq 0.1\Delta$ with probability
$1-\mathcal{O}(1/n)$.

Then we get that if $v_{i}\in V_{1}$ with $|V_{1}|=s^{*}$, for any $i\sim j$
we have with probability $1-\mathcal{O}(1/n)$, $\|B^{r}_{i}-B^{r}_{j}\|\leq
0.6\Delta$. On the other hand, if $i\nsim j$ then $\|B^{r}_{i}-B^{r}_{j}\|\geq
2\Delta-0.6\Delta\geq 1.4\Delta$. This completes the proof.

Now we obtain these bounds. The conditions on $s^{*}$ and $p,q$ are the same
as in Theorem 1.2 in all of the following lemmas/corollaries, and thus we do
not repeat them in each statement.

###  3.1 Bounding the Maximum Norm of the Rows

We start by recording some facts about $L$ and $R$.

######  Fact 3.1.

Let $L,R$ be the matrices defined above. We have the following properties for
them.

  1. 1.

For every $r\geq 1$ and $i,j\in V_{\ell}$, $L^{r}_{i,j}=(p-q)^{r}\cdot
s_{\ell}^{r-1}$

  2. 2.

For every $r\geq 1$ and $i\not\sim j$, and $L^{r}_{i,j}=0$

  3. 3.

$R_{i,j}$ are zero mean independent random variables (modulo the symmetry)

  4. 4.

For every $i,j\in V_{\ell}$, $R_{ij}=1-p$ or $-p$ with probabilities $p$ and
$1-p$ respectively. For every $i\not\sim j$, $R_{ij}=1-q$ or $-q$ with
probabilities $q$ and $1-q$ respectively.

  5. 5.

The maximum variance of $R_{i,j}$, $\sigma^{2}$ is upper bounded by $p(1-q)$.

Now we analyze $\|L^{r}_{i}-L^{r}_{j}\|$, obtaining the following result.

######  Lemma 3.2.

Let $L$ be the matrix defined above. Let $v_{i}\in V_{1}$. Then for every
$i\sim j$, $\|L_{i}^{r}-L_{j}^{r}\|=0$. Otherwise if $i\nsim j$ then
$\|L_{i}^{r}-L_{j}^{r}\|\geq 2\Delta$.

###### Proof.

If $i\sim j$, then according to Fact 3.1, the $i$-th and $j$-th row are same
in $L^{r}$, and thus $\|L^{r}_{i}-L^{r}_{j}\|=0$.

On the other hand, if $i\nsim j$, then the $i$-th and $j$-th row of $L^{r}$
differ in at least $s^{*}$ positions because $v_{i}\in V_{1}$. If we consider
the $i$-th row, there are $s^{*}$ positions where
$(L^{r})_{i,\ell}=(p-q)^{r}(s^{*})^{r-1}$ and $(L^{r})_{j,\ell}=0$. This
implies
$\|L^{r}_{i}-L^{r}_{j}\|\geq\sqrt{s^{*}}\cdot(p-q)^{r}(s^{*})^{r-1}\geq
2\Delta$. ∎

We spend rest of the section upper bounding the maximum $\ell_{2}$ norm of
rows of $M,M^{\prime}$ and $R^{r}$ with high probability. We start by upper
bounding $\|B\|$.

######  Lemma 3.3.

Let $L$ and $R$ be the matrices defined above. Then

$\Pr[\|B\|\geq(p-q)s^{*}+C_{0}\sigma n^{1/2}]\leq n^{-3}$

###### Proof.

We recall that $B=L+R$. Hence, $\|B\|\leq\|L\|+\|R\|$. By Fact 3.1, we also
have that $\|L\|=(p-q)s^{*}$, which implies

$\Pr[\|B\|\geq(p-q)s^{*}+C_{0}\sigma n^{1/2}]\leq\Pr[\|R\|\geq C_{0}\sigma
n^{1/2}]\leq n^{-3}$

where the second inequality follows from Lemma 2.2. ∎

Now we observe a simple and useful property on the $\ell_{2}$ norm of product
of matrices, that follows from the definition of spectral norm.

######  Fact 3.4.

For any $n\times n$ matrices $B$ and $C$,

$\|B\cdot C\|_{row}\leq\|B\|_{row}\cdot\|C\|$

##### Bounding the rows of $M$.

Recall that $M=L^{r-1}R+L^{r-2}RB+\dots+LR\cdot B^{r-2}$. To bound each of the
individual term, we first look at the matrix $L^{t}R$ for $1\leq t\leq r-1$.

######  Lemma 3.5.

With probability at least $1-n^{-3}$, the absolute value of all entries of
$L^{t}R$ is upper bounded by $96\cdot(\sqrt{p(1-q)}\cdot\sqrt{s^{*}}\cdot\log
n)\cdot(p-q)^{t}\cdot(s^{*})^{t-1}$ for $t\leq\log n$.

###### Proof.

For each pair $(i,j)$, the $(i,j)$-th entry of $L^{t}R$ is

$\sum_{\ell}L^{t}_{i,\ell}\cdot R_{\ell,j}$

Let the $i$-th vertex belong to $V_{a}$ for some $a$. Then by Fact 3.1, we
have that

$\sum_{\ell}L^{t}_{i,\ell}\cdot R_{\ell,j}=\sum_{\ell\in
V_{a}}L^{t}_{i,\ell}\cdot R_{\ell,j}+\sum_{\ell\not\in
V_{a}}L^{t}_{i,\ell}\cdot
R_{\ell,j}=(p-q)^{t}\cdot(|V_{a}|)^{t-1}\cdot\sum_{\ell\in V_{a}}R_{\ell,j}$

We notice that $\sum_{\ell\in V_{a}}R_{\ell,j}$ is a summation of at most
$s^{*}$ many zero-mean independent random variables. Then by the Chernoff
bound (Theorem 2.5), we have that

$\Pr\left[\left|\sum_{\ell\in V_{a}}R_{\ell,j}\right|\geq 48\sqrt{p\cdot
s^{*}}\cdot\log n\right]\leq n^{-5}$

Then the absolute value of $(i,j)$-th entry of $L^{t}R$ is upper bounded by
$(p-q)^{t}\cdot(s^{*})^{t-1}\cdot 48\sqrt{p}\cdot\sqrt{s^{*}}\cdot\log n$ with
probability $1-n^{-5}$. Here we use that $1\geq\sqrt{1-q}\geq 1/2$ and then
taking an union bound on all $n^{2}$ $(i,j)$-pairs completes the proof. ∎

We use this result to upper bound $\|M\|_{row}$.

######  Corollary 3.6.

Let $r=\log n$ and $\Delta=0.5\sqrt{s^{*}}(p-q)^{r}(s^{*})^{r-1}$. Then the
$\ell_{2}$ norm of each row of the matrix $M=L^{r-1}R+L^{r-2}RB\dots+LR\cdot
B^{r-2}$ is upper bounded by $0.1\Delta$ with probability
$1-\tilde{\mathcal{O}}(n^{-3})$.

###### Proof.

We have with probability $1-\mathcal{O}(n^{-3})$, all entries of $L^{t}R$ are
upper bounded by

$h_{t}:=96\cdot(\sqrt{p(1-q)}\cdot\sqrt{s^{*}}\cdot\log
n)\cdot(p-q)^{t}\cdot(s^{*})^{t-1}.$

Thus, the $\ell_{2}$-norm of any row of $L^{t}R$ is upper bounded by
$h_{t}\sqrt{n}$. Then from Fact 3.4 we have
$\|L^{t}RB^{r-t-1}\|_{row}\leq\|L^{t}R\|_{row}\cdot\|B\|^{r-t-1}$.
Substituting $\|B\|$ from Lemma 3.3 we get

$\|L^{t}RB^{r-t-1}\|_{row}\leq h_{t}\sqrt{n}\cdot\left((p-q)s^{*}+C_{0}\sigma
n^{1/2}\right)^{r-t-1}$

with probability $1-\mathcal{O}(n^{-3})$. Then the fact that
$(p-q)s^{*}\geq(\log n)^{7}C_{0}\sigma\sqrt{n}$ and $r-t-1\leq\log n$ gives us
the bound

$\|L^{t}RB^{r-t-1}\|_{row}\leq(192\sqrt{p(1-q)}\sqrt{n}\log
n).\cdot\sqrt{s^{*}}\cdot(p-q)^{r-1}(s^{*})^{r-2}$

Since $M=L^{r-1}R+L^{r-2}RB+\dots+LR\cdot B^{r-2}$ we have

$\|M\|_{row}\leq\|L^{r-1}R\|_{row}+\|L^{r-2}RB\|_{row}+\dots+\|LRB^{r-2}\|_{row}.$

Then by a union bound, we have with probability $1-\mathcal{O}(r\cdot n^{-3})$

$\|M\|_{row}\leq r\cdot(192\sqrt{p(1-q)}\sqrt{n}\log
n)\cdot\sqrt{s^{*}}\cdot(p-q)^{r-1}(s^{*})^{r-2}$

Substituting $r\cdot(192\sqrt{p(1-q)}\sqrt{n}\log n)<0.1(p-q)s^{*}$ then
completes the proof.

∎

##### Bounding the Rows of $R^{r}$.

Now we upper bound rows of $R^{r}$.

######  Lemma 3.7.

With probability $1-\mathcal{O}(n^{-3})$, the $\ell_{2}$ norm of all rows of
$R^{r}$ is upper bounded by $0.1\Delta$ for $r=\log n$.

###### Proof.

We know that $\|R^{r}\|_{row}\leq\|R^{r}\|$. Combined with Lemma 2.2 this
implies that with probability $1-\mathcal{O}(n^{-3})$,

$\|R^{r}\|_{row}\leq\|R^{r}\|\leq\|R\|^{r}\leq(C_{0}\sqrt{p(1-q)}\cdot\sqrt{n})^{r}.$

Now we use $(p-q)s^{*}\geq 10000C_{0}(\log n)^{7}\sigma\sqrt{n}$ to get the
following inequality.

$\|R^{r}\|_{row}\leq(C_{0}\sigma\sqrt{n})^{r}\leq\left(\frac{(p-q)s^{*}}{(\log
n)^{7}}\right)^{r}\leq 0.1\Delta$

∎

##### Bounding the rows of $M^{\prime}$.

Here we want to bound the norm of rows of
$M^{\prime}=RLB^{r-2}+\ldots+R^{r-1}L$. To bound the norm of rows of
$R^{t}LB^{r-t-1}$, we start with bounding the norm of rows of $R^{t}L$. In
this direction we obtain the following result.

######  Lemma 3.8.

The absolute value of each entry of $R^{t}L$ is upper bounded by

$C_{2}\sqrt{p(1-q)}(\log n)^{6}\cdot((p-q)\sqrt{s^{*}})((p-q)s^{*})^{t-1}$

for $t\leq\log n$ with probability $1-\mathcal{O}(n^{-3})$ for some constant
$C_{2}<0.05C$.

Due to the non trivial and technical nature of the proof, we place it in
Section 5. Finally, we use the aforementioned result to bound
$\|M^{\prime}\|_{row}$.

######  Corollary 3.9.

The maximum $\ell_{2}$-norm of the rows of $M^{\prime}$ is upper bounded by
$\|M^{\prime}\|_{row}\leq 0.1\Delta$ with probability
$1-\tilde{\mathcal{O}}(n^{-3})$.

###### Proof.

We have $M^{\prime}=RLB^{r-2}+\ldots+R^{r-1}L$. This implies
$\|M^{\prime}\|_{row}\leq\|RLB^{r-2}\|_{row}+\ldots+\|R^{r-1}L\|_{row}$. Lemma
3.8 gives upper bounds for each entries of $R^{t}L$ with probability
$1-\mathcal{O}(n^{-3})$. Then we have

$\|R^{t}L\|_{row}\leq\sqrt{n}\cdot\left(C_{2}\sqrt{p(1-q)}(\log
n)^{6}\cdot(p-q)\sqrt{s^{*}}\cdot((p-q)s^{*})^{t-1}\right)$

with probability $1-\mathcal{O}(n^{-3})$. Furthermore
$\|R^{t}LB^{r-t-1}\|_{row}\leq\|R^{t}L\|_{row}\cdot(\|B\|)^{r-t-1}$. This
implies that with probability $1-\mathcal{O}(n^{-3})$,

$\|R^{t}LB^{r-t-1}\|_{row}\leq 2C_{2}\sqrt{p(1-q)}(\log
n)^{6}\sqrt{n}\cdot\sqrt{s^{*}}\cdot(p-q)^{r-1}(s^{*})^{r-2}$

for all $1\leq t\leq r-1$. Summing over the $r-1$ terms we get with
probability $1-\mathcal{O}(\log n\cdot n^{-3})$,

$\|M^{\prime}\|_{row}\leq 2C_{2}\sqrt{p(1-q)}(\log
n)^{7}\sqrt{n}\cdot\sqrt{s^{*}}\cdot(p-q)^{r-1}(s^{*})^{r-2}$

Substituting $2C_{2}\sqrt{p(1-q)}(\log n)^{7}\sqrt{n}\leq 0.1(p-q)s^{*}$
results in the bound $\|M^{\prime}\|_{row}\leq
0.1\sqrt{s^{*}}(p-q)^{r}(s^{*})^{r-1}\leq 0.1\Delta$ with probability
$1-\mathcal{O}(\log n\cdot n^{-3})$.

∎

This completes our proof of Theorem 1.2.

##  4 An Analysis of Simple Spectral Algorithms

In this section we use the analysis of the power iteration method (Algorithm
1) to prove the correctness of the centered-SVD algorithm (Algorithm 4) and
thus prove Theorem 1.3. Let us first briefly recall the algorithm. We are
given the random adjacency matrix $A$ from $\mathrm{USSBM}(n,k,p,q)$, where
the $k$ hidden communities are formed by putting each vertex into the
communities uniformly at random (this implies that the communities are fairly
balanced). Let $P^{k}_{B}$ the projection operator onto the eigenspace of the
top $k$ eigenvectors of the shifted adjacency matrix $B$. Let $v_{i}$ and
$v_{j}$ be the $i$-th and $j$-th vertices of $G$ and correspondingly the
$i$-th and $j$-th row (column) of $B$ be $\bm{u}$ and $\bm{v}$ respectively.
We intend to show with high probability that there is a threshold $\Delta$ so
that if $v_{i}$ and $v_{j}$ belong to the same community then
$\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|\leq\Delta$. Otherwise if they belong to
different communities then $\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|\geq
1.1\Delta$. As we focus on the more specific $\mathrm{USSBM}$ case here, we
show that this recovery works for all clusters (in comparison to Algorithm 1
where we consider recovering the largest cluster).

Furthermore we work under the condition that $n\geq C^{2}\cdot k^{2}(\log
n)^{14}\cdot p(1-q)/(p-q)^{2}$. We now give a sketch of the proof. It can be
broken down into two steps.

##### Sketch of proof

  * •

First we show that in the $\mathrm{USSBM}$ case under the condition of Theorem
1.3, all communities are separable using the power analysis method. That is,
for $r=\log n$ and a threshold
$\Delta^{\prime}:=0.5\sqrt{n/k}(p-q)^{r+1}(n/k)^{r}$ we show in Lemma 4.2 that
with probability $1-\mathcal{O}(1/n)$ if two vertices $v_{i}$ and $v_{j}$
belong to the same community then $\|B^{r+1}_{i}-B^{r+1}_{j}\|\leq
0.7\Delta^{\prime}$. Otherwise if they belong to different communities then
$\|B^{r+1}_{i}-B^{r+1}_{j}\|\geq 1.2\Delta^{\prime}$.

  * •

Next we connect $P^{k}_{B}$ with $B^{r}$. We show that if $\bm{u}$ is the
$i$-th column of $B$, then $P^{k}_{B}\bm{u}$ is well approximated by
$\frac{1}{(p-q)^{r}(n/k)^{r}}\cdot B^{r+1}_{i}$. In fact, we prove in Lemma
4.4 that
$\|P^{k}_{B}\bm{u}-\frac{B^{r+1}_{i}}{(p-q)^{r}(n/k)^{r}}\|=o\left(\frac{\Delta^{\prime}}{(p-q)^{r}(n/k)^{r}}\right)$
with probability $1-\mathcal{O}(n^{-2})$.

From hereon we denote $s:=n/k$, $f_{r}:=\frac{1}{(p-q)^{r}(s)^{r}}$ and define
the threshold of Algorithm 4 as
$\Delta:=f_{r}\cdot\Delta^{\prime}=0.5(p-q)\sqrt{s}$. Then combining the
results above we get the following.

For any two vertices $v_{i}$, $v_{j}$ and corresponding columns/rows $\bm{u}$
and $\bm{v}$,

  1. 1.

If $v_{i},v_{j}\in V_{\ell}$ for some $\ell$ then by the triangle inequality,

$\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|\leq\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|+\|f_{r}B^{r+1}_{i}-f_{r}B^{r+1}_{j}\|+\|P^{k}_{B}\bm{v}-f_{r}B^{r+1}_{j}\|$

From Lemma 4.2 with probability $1-\mathcal{O}(1/n)$ we have
$\|f_{r}B^{r+1}_{i}-f_{r}B^{r+1}_{j}\|\leq f_{r}\cdot 0.7\Delta^{\prime}\leq
0.7\Delta$.

Next, both $\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|$ and
$\|P^{k}_{B}\bm{v}-f_{r}B^{r+1}_{j}\|$ are upper bounded by $o(\Delta)$ from
Lemma 4.4. Combining the two we get that
$\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|\leq 0.7\Delta+o(\Delta)\leq 0.8\Delta$
with probability $1-\mathcal{O}(1/n)$.

  2. 2.

Similarly if $v_{i}\in V_{\ell}$ and $v_{j}\in V_{\ell^{\prime}}$ then

$\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|\geq\|f_{r}B^{r+1}_{i}-f_{r}B^{r+1}_{j}\|-\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|-\|P^{k}_{B}\bm{v}-f_{r}B^{r+1}_{j}\|$

Here the first term is lower bounded by $f_{r}1.2\Delta^{\prime}=1.2\Delta$
and the next two terms are upper bounded by $o(\Delta)$. This implies
$\|P^{k}_{B}\bm{u}-P^{k}_{B}\bm{v}\|\geq 1.1\Delta$ with probability
$1-\mathcal{O}(1/n)$, which completes the proof.

Now, we obtain Lemma 4.2 and 4.4, to obtain separation based on $B^{r}$ and
then upper bound $\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|$.

###  4.1 Separation in the Rows of Power Matrix in the USSBM Case

We start with formalizing the balancedness in the size of the communities.
Since each vertex is assigned a community uniformly at random, the expected
size of any cluster is $s:=n/k$. Under the choices of parameters $p,q,k,n$
from Theorem 1.3 we have $n/k\gg\sqrt{n}(\log n)^{7}$ and then applying
Chernoff’s bound on the size of the communities we get

######  Fact 4.1 (Size of the clusters).

In the $\mathrm{USSBM}(n,k,p,q)$ model under the condition of Theorem 1.2, for
any cluster $V_{i}$ we have $\Pr(|V_{i}-n/k|\geq\frac{1}{(\log n)^{5}}\cdot
n/k)\leq n^{-4}$.

This gives us a relation between the largest and smallest cluster in the
$\mathrm{USSBM}$ framework. Let $s^{*}$ and $s_{\min}$ be the sizes of the
largest and the smallest clusters respectively. We then have the following
lemma.

######  Lemma 4.2.

Let $\Delta^{\prime}=0.5\sqrt{s}(p-q)^{r+1}(s)^{r}$. In the $\mathrm{USSBM}$
case under the condition of Theorem 1.3, if $v_{i}$ and $v_{j}$ belong to the
same cluster then $\|B^{r+1}_{i}-B^{r+1}_{j}\|\leq 0.7\Delta^{\prime}$ and
$\|B^{r+1}_{i}-B^{r+1}_{j}\|\geq 1.2\Delta^{\prime}$ otherwise.

###### Proof.

Recall that

$\left|\|B^{r+1}_{i}-B^{r+1}_{j}\|-\|L^{r+1}_{i}-L^{r+1}_{j}\|\right|\leq
2(\|M\|_{row}+\|M^{\prime}\|_{row}+\|R^{r+1}\|_{row})$

Now combining Corollary 3.6, Lemma 3.7 and Corollary 3.9 we have that with
probability $1-\mathcal{O}(1/n)$,
$2(\|M\|_{row}+\|M^{\prime}\|_{row}+\|R^{r+1}\|_{row})\leq
0.1\sqrt{s^{*}}(p-q)^{r+1}(s^{*})^{r}$. Fact 4.1 implies that for any
$r\leq\log n$ with probability $1-\mathcal{O}(n^{-4})$,

  * •

$(s^{*})^{r+1}\leq s^{r+1}\cdot(1+\log^{-5}n)^{r+1}\leq
s^{r+1}\cdot(1+\log^{-4}n)\leq 1.01s^{r+1}$.

  * •

$(s_{\min})^{r+1}\geq s^{r+1}\cdot(1-\log^{-5}n)^{r+1}\geq
s^{r+1}\cdot(1-\log^{-4}n)\geq 0.99s^{r+1}$.

Thus we get with probability $1-\mathcal{O}(1/n)$,

$2(\|M\|_{row}+\|M^{\prime}\|_{row}+\|R^{r}\|_{row})\leq
0.33\sqrt{s}\cdot(p-q)^{r+1}s^{r}\leq 0.7\Delta^{\prime}$

Next, Lemma 3.2 implies that if $v_{i}$ and $v_{j}$ do not belong to the same
community then
$\|L^{r+1}_{i}-L^{r+1}_{j}\|\geq\sqrt{s_{\min}}(p-q)^{r+1}(s_{\min})^{r}\geq
0.99\sqrt{s}(p-q)^{r+1}s^{r}\geq 1.9\Delta^{\prime}$ with probability
$1-\mathcal{O}(1/n)$.

Combining this we get that with probability $1-\mathcal{O}(1/n)$
$\|B^{r+1}_{i}-B^{r+1}_{j}\|\leq 0.7\Delta^{\prime}$ if $v_{i}$ and $v_{j}$
belong to the same cluster, and $\|B^{r+1}_{i}-B^{r+1}_{j}\|\geq
1.9\Delta^{\prime}-0.7\Delta^{\prime}\geq 1.2\Delta^{\prime}$, which completes
the proof.

∎

Next, we connect the SVD projection with the power matrix.

###  4.2 Relation Between Eigenspace and Power Matrix

We aim to show that $\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|=o(\Delta)$ with high
probability. To obtain this we first show that
$\|f_{r}B^{r+1}_{i}\|=\Theta(\Delta)$ and then
$\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|=o(\|f_{r}B^{r+1}_{i}\|)$.

######  Lemma 4.3.

Let $\Delta=0.5(p-q)\sqrt{s}$. Then under the condition of Theorem 1.3 we have
$\|f_{r}B_{i}^{r+1}\|=\Theta(\Delta)$ with probability $1-\mathcal{O}(1/n)$
for any $i$.

###### Proof.

Recall that $B^{r+1}_{i}=L^{r+1}_{i}+M_{i}+M^{\prime}_{i}+R^{r+1}_{i}$. From
Section 3 we have that with probability $1-\mathcal{O}(1/n)$,
$\|M\|_{row}+\|M^{\prime}\|_{row}+\|R^{r}\|_{row}\leq
0.15\sqrt{s^{*}}(p-q)^{r+1}(s^{*})^{r}\leq 0.16\sqrt{s}(p-q)^{r+1}s^{r}$.
Furthermore,

  * •

$\|L^{r+1}_{i}\|\geq\sqrt{s_{\min}}(p-q)^{r+1}(s_{\min})^{r}\geq
0.99\sqrt{s}(p-q)^{r+1}s^{r}$ with probability $1-\mathcal{O}(n^{-3})$.

  * •

$\|L^{r+1}_{i}\|\leq\sqrt{2s^{*}}(p-q)^{r+1}(s^{*})^{r}\leq
2.2\sqrt{s}(p-q)^{r+1}s^{r}$ with probability $1-\mathcal{O}(n^{-3})$.

Thus, with probability $1-\mathcal{O}(1/n)$ we have

$\displaystyle\|f_{r}B^{r+1}_{i}\|\geq
f_{r}(\|L^{r+1}_{i}\|-\|M\|_{row}-\|M^{\prime}\|_{row}-\|R^{r}\|_{row})\geq(p-q)^{-r}s^{-r}\cdot
0.5\sqrt{s}(p-q)^{r+1}s^{r}$ $\displaystyle\geq 0.5\sqrt{s}(p-q)\geq
0.5\Delta$

Similarly, with probability $1-\mathcal{O}(1/n)$, $\|f_{r}B^{r+1}_{i}\|\leq
5\Delta$. This completes the proof.

∎

Furthermore, let us also upper bound $\Delta$. Recall that
$(p-q)s\gg\sqrt{p(1-q)}\sqrt{n}(\log n)^{7}$. This implies

$\Delta=0.5(p-q)\sqrt{s}\geq(\log n)^{7}/\sqrt{n}$ (2)

We then have the following bound on $\|f_{r}B^{r+1}_{i}-P^{k}_{B}\bm{u}\|$.

######  Lemma 4.4.

Let $\Delta=0.5(p-q)\sqrt{s}$, $f_{r}=\frac{1}{(p-q)^{r}s^{r}}$ and the
relation between $n$ and $k$ be as stated in Theorem 1.3. Let $\bm{u}$ be the
$i$-th column of $B$. Then with probability $1-\mathcal{O}(n^{-4})$ we have

$\|P^{k}_{B}\bm{u}-f_{r}B^{r+1}_{i}\|=o(\Delta)$

###### Proof.

We first note that $B^{r+1}_{i}=B^{r}\bm{u}$. This follows from the fact that
$\bm{u}$ is the $i$-th column of $B$ and that $B$ is a symmetric matrix. Then
we observe $P^{k}_{B}\bm{u}-f_{r}B^{r}\bm{u}$.

Let $\bm{p_{i}},1\leq i\leq n$ be the $n$ the orthonormal eigenvectors of $B$
in descending order of eigenvalues
$\lambda_{1}(B)\geq\ldots\geq\lambda_{n}(B)$. We denote $\lambda_{i}(B)$
simply as $\lambda_{i}$. Then any column $\bm{u}$ can be represented as
$\bm{u}=\sum_{j=1}^{n}\langle\bm{p_{j}},\bm{u}\rangle\bm{p_{j}}$. It implies
$B^{r}\bm{u}=\sum_{j=1}^{n}(\lambda_{i})^{r}\langle\bm{p_{j}},\bm{u}\rangle\bm{p_{j}}$.

On the other hand, as $P^{k}_{B}$ is the projection operator onto the top $k$
eigenvectors of $B$, we have
$P^{k}_{B}=\sum_{i=1}^{k}\langle\bm{p_{i}},\bm{u}\rangle\bm{p_{i}}$.
Substituting these descriptions we get

$\displaystyle f_{r}B^{r}\bm{u}-P^{k}_{B}\bm{u}$
$\displaystyle=\sum_{j=1}^{n}f_{r}(\lambda_{j})^{r}\langle\bm{p_{j}},\bm{u}\rangle\bm{p_{j}}-\sum_{i=1}^{k}\langle\bm{p_{i}},\bm{u}\rangle\bm{p_{i}}$
$\displaystyle=\sum_{i=1}^{k}(f_{r}(\lambda_{i})^{r}-1)\langle\bm{p_{i}},\bm{u}\rangle\bm{p_{i}}+\sum_{j=k+1}^{n}f_{r}(\lambda_{j})^{r}\cdot\langle\bm{p_{j}},\bm{u}\rangle\bm{p_{j}}$
$\displaystyle\leq\sum_{i=1}^{k}\left|f_{r}(\lambda_{i})^{r}-1\right|\langle\bm{p_{i}},\bm{u}\rangle\bm{p_{i}}+\sum_{j=k+1}^{n}f_{r}(\lambda_{j})^{r}\cdot\langle\bm{p_{j}},\bm{u}\rangle\bm{p_{j}}$
$\displaystyle\implies\|f_{r}B^{r}\bm{u}-P^{k}_{B}\bm{u}\|^{2}$
$\displaystyle\leq\sum_{i=1}^{k}(\left|f_{r}(\lambda_{i})^{r}-1\right|^{2}\langle\bm{p_{i}},\bm{u}\rangle)^{2}+\sum_{j=k+1}^{n}(f_{r}(\lambda_{j})^{2r}\langle\bm{p_{j}},\bm{u}\rangle)^{2}$
(3)

Now we analyze $f_{r}(\lambda_{i})^{r}$. Recall that
$\lambda_{i}=\lambda_{i}(B)$ and $B=L+R$. Then Weyl’s inequality implies
$\lambda_{i}(L)-\|R\|\leq\lambda_{i}(B)\leq\lambda_{i}(L)+\|R\|$ for $i\leq k$
and $\lambda_{i}(B)\leq\|R\|$ for $i>k$ as $L$ has rank $k$. In this
direction, $\lambda_{i}(L)=(p-q)|V_{i}|$ where $V_{i}$ is the $i$-th largest
community. Furthermore, $\|R\|\leq C_{0}\sqrt{p(1-q)}\sqrt{n}$ with
probability $1-\mathcal{O}(n^{-3})$. We also have $(p-q)s_{\min}\geq
C_{0}\sqrt{p(1-q)}\sqrt{n}(\log n)^{7}$. We then have two observations.

  1. 1.

Let $i\leq k$. Then
$|\lambda_{i}(B)-(p-q)s|\leq\|R\|+(p-q)(s^{*}-s)+(p-q)(s-s_{\min})$ Then with
probability $1-\mathcal{O}(n^{-3})$ this implies
$|\lambda_{i}(B)-(p-q)s|\leq(p-q)s(\log n)^{-6}+2(p-q)s(\log
n)^{-4}\leq(p-q)s(\log n)^{-3}$. This implies
$f_{r}(\lambda_{i})^{r}=1\pm(\log n)^{-3}$ and thus
$(f_{r}(\lambda_{i})^{r}-1)^{2}=o((f_{r}\lambda_{i})^{2r})$.

  2. 2.

Let $i>k$. Then $\lambda_{i}\leq(p-q)s(\log n)^{-5}$ with probability
$1-\mathcal{O}(n^{-3})$. Then with the same probability
$f_{r}(\lambda_{i})^{r}\leq f_{r}(p-q)^{r}s^{r}(\log n)^{-5r}\leq(\log
n)^{-5r}\ll n^{-2}$.

Substituting this in Equation (4.2) we get

$\displaystyle\|f_{r}B^{r}\bm{u}-P^{k}_{B}\bm{u}\|^{2}=$
$\displaystyle\sum_{i=1}^{k}o(f_{r}(\lambda_{i})^{r})^{2}(\langle\bm{p_{i}},\bm{u}\rangle)^{2}+\sum_{j=k+1}^{n}\frac{1}{n^{4}}(\langle\bm{p_{j}},\bm{u}\rangle)^{2}$
$\displaystyle=$ $\displaystyle o(\|f_{r}B^{r+1|}\|^{2})+o(n^{-2})$ [From
definition of $f_{r}B^{r+1}$ and $\|u\|^{2}\leq n$] $\displaystyle=$
$\displaystyle o(\Delta^{2})$ [Lemma 4.3 and Equation (2)]

This implies that with probability $1-\mathcal{O}(n^{-3})$ we have
$\|f_{r}B^{r+1}_{i}-P^{k}_{B}\bm{u}\|=o(\Delta)$ for any $i$ and then applying
union bound on $i$ completes the proof. ∎

##  5 Proving Entry-wise Concentration Bounds of via Random Partition

In this section we bound the absolute value of the entries of $R^{t}L$ for any
$t\leq\log n$, proving Lemma 3.8. Let us first recall the statement of the
lemma. We want to show that with high probability ($1-\mathcal{O}(n^{-3})$)
the absolute value of entries of $R^{t}L$, denoted as $(R^{t}L)_{a,b}$ is
upper bounded by

$\left|(R^{t}L)_{a,b}\right|\leq C_{2}\sqrt{p}(\log
n)^{6}\cdot(p-q)\sqrt{s^{*}}\cdot((p-q)s^{*})^{t-1}$

for some constant $C_{2}$. We first expand $(R^{t}L)_{a,b}$ as follows.

$(R^{t}L)_{a,b}=\sum_{\ell_{1},\ldots,\ell_{t}}R_{a,\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},b}$

Thus, each entry of $R^{t}L$ is a sum of multivariate monomials, with the
degree of each monomial being $t+1$. We can denote each monomial with their
index list $\mathcal{L}:=(\ell_{1},\ldots,\ell_{t})\in[n]^{t}$ which
establishes a one-to-one correspondence between monomials $P_{\mathcal{L}}$
and index lists $\mathcal{L}$. Then we have
$(R^{t}L)_{a,b}=\sum_{\mathcal{L}\in[n]^{t}}P_{\mathcal{L}}$.

Against this setting, we break the set of $\mathcal{L}$ into several groups
based on the similarity of the indices. We define an encoding of the lists to
a $t$-length array $X$. Then all $\mathcal{L}$ that map into the same encoding
$X$ form one such group. The encoding is as follows.

######  Definition 5.1 (Encoding index lists to $X$).

Given any index list $\mathcal{L}=(\ell_{1},\ldots,\ell_{t})\in[n]^{t}$, we
encode it into a $t$-length array $X$ as follows.

  * •

Set $X[1]=1$.

  * •

For all $i\geq 2$, let $y:=\max\\{X[1],\ldots,X[i-1]\\}$. If
$\ell_{i}\neq\ell_{j}$ for all $j<i$, we set $X[i]=y+1$. Otherwise,
$X[i]=X[j]$ for any $j<i$ s.t $\ell_{i}=\ell_{j}$.

Let the set of all such $X$ be $\mathcal{X}$. Then the size of $\mathcal{X}$
follows simply from its definition.

######  Lemma 5.2.

The size of $\mathcal{X}$ is upper bounded by $t^{t}$, i.e. $|\mathcal{X}|\leq
t^{t}$.

Now, corresponding to any $X\in\mathcal{X}$, we define by $Z^{t}_{a,b}(X)$ the
sum of monomials $P_{\mathcal{L}}$ such that $\mathcal{L}$ maps to that
particular $X$. Let $t^{\prime}:=\max\\{X[1],\ldots,X[t]\\}$. Then
$Z^{t}_{a,b}(X)$ can be expressed as follows,

$Z^{t}_{a,b}(X)=\sum_{\begin{subarray}{c}\ell_{1},\ldots,\ell_{t^{\prime}}\in([n])^{t^{\prime}}\\\
\text{ s.t }\ell_{i_{1}}\neq\ell_{i_{2}}\forall
i_{1},i_{2}\in[t^{\prime}]\end{subarray}}R_{a,\ell_{X[1]}}R_{\ell_{X[1]},\ell_{X[2]}}\cdots
R_{\ell_{X[t-1]},\ell_{X[t]}}L_{\ell_{X[t]},b}$

And we have the inequality

$|(R^{L})_{a,b}|\leq\sum_{X\in\mathcal{X}}\left|Z^{t}_{a,b}(X)\right|$ (4)

We prove upper bounds on $\left|Z^{t}_{a,b}(X)\right|$ for any arbitrary $X$
with probability $1-(t^{-t}\cdot n^{-5})$, and then use Lemma 5.2 to upper
bound the total value using a union bound.

We first prove it for the simplest case, which is for the encoding $X$ where
all indices are different. That is, the corresponding $X$ has $X[i]=i,1\leq
i\leq t$. We denote $W^{t}_{a,b}:=Z^{t}_{a,b}(X)$ for this particular $X$, and
bound $\left|W^{t}_{a,b}\right|$. Then we extend our result for a generic
$X\in\mathcal{X}$.

### The case with all different indices.

In this part we denote $\ell_{0}:=a$ and $\ell_{t+1}:=b$ for ease of
presentation. We want to to upper bound the sum

$\left|W^{t}_{\ell_{0},\ell_{t+1}}\right|=\left|\sum_{(\ell_{1},\ldots,\ell_{t}):\ell_{x}\neq\ell_{y}\forall
x,y}R_{\ell_{0},\ell_{1}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},\ell_{t+1}}\right|$

We use a random partition idea to bound this summation. Let
$[n]:=\\{1,\ldots,n\\}$. We partition $[n]$ into $t$ many sets
$T=\\{T_{1},\ldots,T_{t}\\}$ by putting each element into one of the sets
uniformly at random. Then we consider the summation

$W^{t}_{\ell_{0},\ell_{t+1}}(T)=\sum\limits_{\ell_{1}\in
T_{1},\ldots,\ell_{t}\in
T_{t}}R_{\ell_{0},\ell_{1}}R_{\ell_{1},\ell_{2}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},\ell_{t+1}}$

As $T$ is a partition formed uniformly at random, the probability that any
monomial of $W^{t}_{\ell_{0},\ell_{t+1}}$ is present in
$W^{t}_{\ell_{0},\ell_{t+1}}(T)$ is $(1/t)^{t}$. Then we have

$\displaystyle
W^{t}_{\ell_{0},\ell_{t+1}}=t^{t}\cdot\underset{T}{\mathbb{E}}[W^{t}_{\ell_{0},\ell_{t+1}}(T)]$
$\displaystyle\implies$
$\displaystyle\left|W^{t}_{\ell_{0},\ell_{t+1}}\right|=t^{t}\left|\underset{T}{\mathbb{E}}[W^{t}_{\ell_{0},\ell_{t+1}}(T)]\right|$

We then have the following Lemma.

######  Lemma 5.3.

For any $0<t<\log n$ and $\ell_{0},\ell_{t+1}$ we have
$\left|W^{t}_{\ell_{0},\ell_{t+1}}\right|\leq
t^{t}\cdot\underset{T}{\mathbb{E}}\left[\left|W^{t}_{\ell_{0},\ell_{t+1}}(T)\right|\right]$.

Against this setup we first upper bound
$\left|W^{t}_{\ell_{0},\ell_{t+1}}(T)\right|$ for a fixed $T$, and then obtain
$\underset{T}{\mathbb{E}}[|W^{t}_{\ell_{0},\ell_{t+1}}(T)|]$ using the higher
moment method.

##### Analyzing $\left|W^{t}_{\ell_{0},\ell_{t+1}}(T)\right|$ for a fixed $T$:

Since all of the random variables in any monomial is different, we can write

$\left|W^{t}_{\ell_{0},\ell_{t+1}}(T)\right|=\left|\sum_{\ell_{1}\in
T_{1},\ldots,\ell_{t-1}\in T_{t-1}}R_{\ell_{0},\ell_{1}}\cdots
R_{\ell_{t-2},\ell_{t-1}}\sum_{\ell_{t}\in
T_{t}}R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},\ell_{t+1}}\right|$

To bound this term we define

$F(i,\ell_{i})=\sum_{\ell_{i+1}\in T_{i+1},\dots,\ell_{t}\in
T_{t}}R_{\ell_{i},\ell_{i+1}}\cdots
R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},\ell_{t+1}}$

This implies for every $i$ and $\ell_{i-1}$,
$\left|F(i-1,\ell_{i-1})\right|=\left|\sum_{\ell_{i}\in
T_{i}}R_{\ell_{i-1},\ell_{i}}F(i,\ell_{i})\right|.$ We plan to recursively
upper bound $\left|F(i,\ell_{i})\right|$ in the descending order of $i$,
starting with $F(t-1,\ell_{t-1}):=\sum_{\ell_{t}\in
T_{t}}R_{\ell_{t-1},\ell_{t}}L_{\ell_{t},\ell_{t+1}}$ and ending at
$\left|F(0,\ell_{0})\right|$. We upper bound this using the fact that since
$R_{\ell_{i-1},\ell_{i}}$ is a zero mean random variable, so is
$R_{\ell_{i-1},\ell_{i}}F(i,\ell_{i})$. Then an upper bound on
$\left|F(i,\ell_{i})\right|$ allows us to apply Chernoff bound on this sum.

Recall that any column of $L$ has at most $s^{*}$ non zero ( each $(p-q)$ )
entry and $R_{i,j}$ is a zero-mean independent random variable which is either
$1-p$ with probability $p$ and $-p$ otherwise, or $1-q$ with probability $q$,
or $-q$ otherwise. Then Chernoff bound (Theorem 2.5) implies the following.

######  Corollary 5.4.

For all $\ell_{t-1}\in T_{t-1}$,

$\Pr(\left|F(t-1,\ell_{t-1})\right|\geq 96(p-q)\sqrt{p}\sqrt{s^{*}}(\log
n)^{3})\leq n^{-4(\log n)^{2}}.$

Then applying the definition recursively we have the following lemma.

######  Lemma 5.5.

Let $\left|F(i,\ell_{i})\right|,1\leq i<t-1$ be less than $\beta$ for all
$\ell_{i}\in T_{i}$ with probability $p_{\beta}$. Then

$\Pr\left(\left|F(i-1,\ell_{i-1})\right|\leq\beta\cdot 96\sqrt{p}\sqrt{n}(\log
n)^{3}\right)\geq(1-n^{-5(\log n)^{2}})p_{\beta}$

###### Proof.

From the definition of $F(i-1,\ell_{i-1})$ we have

$\left|F(i-1,\ell_{i-1})\right|=\left|\sum_{\ell_{i}\in
T_{i}}R_{\ell_{i-1},\ell_{i}}F(i,\ell_{i})\right|$

Here $R_{\ell_{i-1},\ell_{i}}F(i,\ell_{i})$ are zero mean random variables,
and with probability $p_{\beta}$, $|F(i,\ell_{i})|\leq\beta$ for all
$\ell_{i}$. Then from the Chernoff bound we have

$\Pr\left(\left|\sum_{\ell_{i}\in T_{i}}\
R_{\ell_{i-1},\ell_{i}}F(i,\ell_{i})\right|\geq\beta\cdot
96\sqrt{p}\sqrt{|T_{i}|}(\log n)^{3}\right)\leq n^{-5(\log n)^{2}}$

Then applying $|T_{i}|\leq n$ completes the proof. ∎

Next using the recursive definition of $F(i,\ell_{i})$ along with Lemma 5.5 we
upper bound $|W^{t}_{\ell_{0},\ell_{t+1}}(T)|$.

######  Lemma 5.6.

For any fixed partition $T$ and $t\leq\log n$ the sum
$\left|W^{t}_{\ell_{0},\ell_{t+1}}(T)\right|$ is upper bounded by
$C_{t}:=(96\sqrt{p}(p-q)\sqrt{s^{*}}(\log n)^{3})\cdot(96\sqrt{p}\sqrt{n}(\log
n)^{3})^{t-1}$ with probability $1-n^{-3(\log n)^{2}}$.

###### Proof.

From Corollary 5.4 we have that

$\Pr\left(\left|F(t-1,\ell_{t-1})\right|\leq 96\sqrt{p}(p-q)\sqrt{s^{*}}(\log
n)^{3}\right)\geq 1-n^{-4(\log n)^{2}}$

for all values of $t-1$. Then application of Lemma 5.5 $t-1$ times give us

$\Pr\left(\left|F(0,\ell_{0})\right|\leq(96\sqrt{p}(p-q)\sqrt{s^{*}}(\log
n)^{3})\cdot(96\sqrt{p}\sqrt{n}(\log n)^{3})^{t-1}\right)\geq
1-t^{2}n^{-4(\log n)^{2}}$

and putting $t\leq\log n$ completes the proof. ∎

Furthermore $W^{t}_{\ell_{0},\ell_{t+1}}(T)$ is the sum of $n^{t}$ many
monomials for any fixed $T$, and the absolute value of each monomial is less
than $p-q$. This gives us the following fact.

######  Fact 5.7.

For any fixed partition $T$ of $[n]$ into $t$ many sets,
$\left|W^{t}_{\ell_{0},\ell_{t+1}}(T)\right|\leq(p-q)n^{t}$.

Now we analyze $\underset{T}{\mathbb{E}}[|W^{t}_{\ell_{0},\ell_{t+1}}(T)|]$
using the higher moment method.

##### Upper bounding the expectation.

Let $\beta$ be the number of possible partitions of $[n]$ into $T$ many
uniformly formed sets. Since each partition is chosen with equal probability,
we have
$S:=\underset{T}{\mathbb{E}}[|W^{t}_{\ell_{0},\ell_{t+1}}(T)|]=\frac{1}{\beta}\sum_{T}|W^{t}_{\ell_{0},\ell_{t+1}}(T)|$.
Then Markov’s inequality implies
$\Pr(S\geq\gamma)\leq\frac{\mathbb{E}[S^{c}]}{\gamma^{c}}$ for any $c>0$. We
are now left with needing an upper bound on $\mathbb{E}[S^{c}]$.

######  Lemma 5.8.

For any $0<c<\log n$, we have $\mathbb{E}[S^{c}]\leq(C_{t})^{c}$

###### Proof.

We have

$\displaystyle\mathbb{E}[S^{c}]=\mathbb{E}\left[\left(1/\beta\sum_{T}|W^{t}_{\ell_{0},\ell_{t+1}}(T)|\right)^{c}\right]=(1/\beta)^{c}\sum_{T_{1},\ldots,T_{c}}\mathbb{E}\left[|W^{t}_{\ell_{0},\ell_{t+1}}(T_{1})|\cdot|W^{t}_{\ell_{0},\ell_{t+1}}(T_{2})|\cdots|W^{t}_{\ell_{0},\ell_{t+1}}(T_{c})|\right]$

We now analyze
$\mathbb{E}\left[|W^{t}_{\ell_{0},\ell_{t+1}}(T_{1})|\cdot|W^{t}_{\ell_{0},\ell_{t+1}}(T_{2})|\cdots|W^{t}_{\ell_{0},\ell_{t+1}}(T_{c})|\right]$.
From Lemma 5.6 we have that for any fixed $T$,
$\Pr(|W^{t}_{\ell_{0},\ell_{t+1}}(T)|\geq C_{t})\leq n^{-3(\log n)^{2}}$. This
implies

$\Pr\left(\prod_{i\in[c]}\left|W^{t}_{\ell_{0},\ell_{t+1}}(T_{i})\right|\geq
C_{t}^{c}\right)\leq c\cdot n^{-3(\log n)^{2}}\leq n^{-2(\log n)^{2}}$

From Fact 5.7 we have $|W^{t}_{\ell_{0},\ell_{t+1}}(T)|\leq(p-q)n^{t}$. Then
using $ct\leq(\log n)^{2}$ we get that for $T_{1},\ldots,T_{c}$,

$\mathbb{E}\left[|W^{t}_{\ell_{0},\ell_{t+1}}(T_{1})|\cdot|W^{t}_{\ell_{0},\ell_{t+1}}(T_{2})|\cdots|W^{t}_{\ell_{0},\ell_{t+1}}(T_{c})|\right]\leq(1-n^{-2(\log
n)^{2}})(C_{t})^{c}+n^{-2(\log n)^{2}}(p-q)^{c}n^{ct}\leq(C_{t})^{c},$

as $c,t\leq\log n$. Since there are a total of $\beta^{c}$ terms, the lemma
then follows. ∎

Then combining with higher moment method we have the following result by
setting $\gamma=32\cdot\log n\cdot C_{t}$ and $c=\log n$.

######  Corollary 5.9.

For any $\ell_{0},\ell_{t+1}$ and $t<\log n$ we have
$|W^{t}_{\ell_{0},\ell_{t+1}}|\leq t^{t}\cdot 32\cdot\log n\cdot C_{t}$ with
probability $1-\log n^{\log n}n^{-5}$.

This completes analysis of the summation of all monomials where
$\ell_{1},\ldots,\ell_{t}$ are all different. Next we extend our proof to a
generic $X$.

### Monomials with arbitrary individual degrees

Next we bound the absolute value of the sum of the monomials with any index
ordering $X\in\mathcal{X}$. Recall the definition

$Z^{t}_{a,b}(X)=\sum_{\begin{subarray}{c}\ell_{1},\ldots,\ell_{t^{\prime}}\in([n])^{t^{\prime}}\\\
\text{ s.t }\ell_{i_{1}}\neq\ell_{i_{2}}\forall
i_{1},i_{2}\in[t^{\prime}]\end{subarray}}R_{a,\ell_{X[1]}}R_{\ell_{X[1]},\ell_{X[2]}}\cdots
R_{\ell_{X[t-1]},\ell_{X[t]}}L_{\ell_{X[t]},b}$

and that $t^{\prime}:=\max\\{X[1],\ldots,X[t]\\}$. Here we define the
representative monomial

$\mathcal{P}^{(t^{\prime})}(1,\ldots,t^{\prime},\ell_{1},\ldots,\ell_{t^{\prime}}):=R_{a,\ell_{X[1]}}R_{\ell_{X[1]},\ell_{X[2]}}\cdots
R_{\ell_{X[t-1]},\ell_{X[t]}}L_{\ell_{X[t]},b}$

Let $\mathcal{L}_{S}:=\\{\ell_{i}\\}_{i\in S}$ for any
$S\subseteq[t^{\prime}]$. Then we have

$Z^{t}_{a,b}(X)=\sum_{\begin{subarray}{c}\ell_{1},\ldots,\ell_{t^{\prime}}\in([n])^{t^{\prime}}\\\
\text{ s.t }\ell_{i_{1}}\neq\ell_{i_{2}}\forall
i_{1},i_{2}\in[t^{\prime}]\end{subarray}}\mathcal{P}^{(t^{\prime})}\left([t^{\prime}],\mathcal{L}_{[t^{\prime}]}\right)$

Furthermore, we fix all the indices $\ell_{i}$ that are to be assigned $a$.
Since at most one of the index can be assigned as $a$, we define by
$Z^{t}_{a,b}(X,i)$ as the sum of monomials of $Z^{t}_{a,b}(X)$ for which
$\ell_{i}=a$. Furthermore, $Z(X,0)$ is the case where none of the indices are
$a$. Then

$\left|(R^{t}L)_{a,b}\right|\leq\sum_{X\in\mathcal{X}}\sum_{0\leq i\leq
t^{\prime}}\left|Z^{t}_{a,b}(X,i)\right|$ (5)

Here we upper bound $\left|Z^{t}_{a,b}(X,0)\right|$ for any arbitrary $X$
using our analysis of $W^{t}_{a,b}$ and then extend it to complete the proof.
First we describe a sketch of our proof.

##### Sketch of proof

We start with a random partition of $[n]\setminus\\{a\\}$ into $t^{\prime}$
many sets $T=\\{T_{1},\ldots,T_{t^{\prime}}\\}$ and upper bound the term

$Z^{t}_{a,b}(X,0,T):=\sum_{\begin{subarray}{c}\ell_{i}\in T_{i}\\\ 1\leq i\leq
t^{\prime}\end{subarray}}\mathcal{P}^{(t^{\prime})}\left([t^{\prime}],\mathcal{L}_{[t^{\prime}]}\right)$

Then, as before we have

$Z^{t}_{a,b}(X,0)=(t^{\prime})^{t^{\prime}}\cdot\underset{T}{\mathbb{E}}\left[Z^{t}_{a,b}(X,0,T)\right]\implies\left|Z(X,0)\right|\leq
t^{t}\cdot\underset{T}{\mathbb{E}}\left[\left|Z^{t}_{a,b}(X,0,T)\right|\right]$

We upper bound $|Z^{t}_{a,b}(X,0,T)|$ with high probability and then the upper
bound on expectation follows from the higher moment method. Let us now focus
on $Z^{t}_{a,b}(X,0,T)$.

In case of $W^{t}_{a,b}$, we start with a sum of $t+1$ degree monomials, and
recursively bound a certain sum based on the index $\ell_{i}$ at each round,
starting from $\ell_{t}$ and proceeding in the decreasing order. After each
round, we are left with bounding a sum of monomials of degree one less than
the previous round.

In contrast, for $Z^{t}_{a,b}(X,0,T)$ we start with $\ell_{t^{\prime}}$ and go
down. Since some indices may appear in multiple random variables, the degree
of the monomial may go down arbitrarily after each step. The crux of the idea
is to ensure that after we have taken a sum on $\ell_{i}$, there are still
random variables with $\ell_{j},j<i$ as their indices for all $j$. This is
ensured by the way our encoding scheme is defined. Now we lay out the details.

##### Upper bounding $\left|Z^{t}_{a,b}(X,0,T)\right|$.

Note that in $Z^{t}_{a,b}(X,0,T)$, the domain of each index $\ell_{i}$ is
unique (as $T$ is a disjoint partition of $[n]\setminus\\{a\\}$). We also
denote the monomial $\mathcal{P}(S,\mathcal{L}_{S})$ simply as
$\mathcal{P}_{S}$ for ease of representation. Then we have the following
definition.

######  Definition 5.10.

Let $S_{t}=[t^{\prime}]$. Then, given the monomial
$\mathcal{P}^{(t^{\prime})}\left({S_{t^{\prime}},\mathcal{L}_{S_{t^{\prime}}}}\right)$,

  1. 1.

$\mathcal{P}^{(i,i)}$ denotes the product of variables in $\mathcal{P}^{(i)}$
that have $\ell_{i}$ as one of their indices.

  2. 2.

$\mathcal{P}^{(i-1)}$ denotes the monomial obtained by removing
$\mathcal{P}^{(i,i)}$ from $\mathcal{P}^{(i)}$.

That is,

$\mathcal{P}^{(i)}_{S_{i}}=\mathcal{P}^{(i-1)}_{S_{i-1}}\cdot\mathcal{P}^{(i,i)}_{S_{i}^{\prime}}$

where $S_{i}$ is the set of indices present in the variables of the monomial
$\mathcal{P}^{(i)}$ and $S_{i}^{\prime}$ is the set of indices present in the
variables of the monomial $\mathcal{P}^{(i,i)}$.

Here note that $\ell_{i}\notin S_{i-1}$ and if $\deg(\mathcal{P}^{(i,i)})>0$,
then $\ell_{i}\in S_{i}^{\prime}$. This in turn implies the following
identity.

$\mathcal{P}^{(t^{\prime})}_{S_{t}}=\prod_{1\leq i\leq
t^{\prime}}\mathcal{P}^{(i,i)}_{S_{i}^{\prime}}$ (6)

Then we have a simple lemma which is a consequence of our encoding scheme 5.1.

######  Lemma 5.11.

For any $1\leq i\leq t^{\prime}$,
$\deg\left(\mathcal{P}^{(i,i)}_{S_{i}^{\prime}}\right)\geq 1$.

###### Proof.

This can be proven by induction. We start with $\mathcal{P}^{(t^{\prime})}$.
Recall that $\mathcal{P}^{(t^{\prime}-1)}$ is obtained by removing all
variables $R_{\ell_{X[i],X[i+1]}}$ or $L_{X[t],b}$ from
$\mathcal{P}^{(t^{\prime})}$ that contain $\ell_{t^{\prime}}$ as an index.
Furthermore, in the monomial $\mathcal{P}^{(t^{\prime})}$, $\ell_{t^{\prime}}$
has the right-most first appearance, as $t^{\prime}$ has the highest value in
the corresponding $X$. Thus, the first variable from left in which
$\ell_{i},i<t^{\prime}$ is first present is strictly left of the first
appearance of $\ell_{t^{\prime}}$. Thus, all such variables are present in
$\mathcal{P}^{(t^{\prime}-1)}$.

Similarly consider any $\mathcal{P}^{(i)}$ such that it has at least one
variable with $\ell_{j}$ as an index for any $j\leq i$. Then if
$\mathcal{P}^{(i,i)}$ is removed, the first variable in which $\ell_{j},j<i$
appears is still present in $\mathcal{P}^{(i-1)}$. This completes the proof.

∎

Furthermore, it is also easy to see that if $X[t]=\alpha$ then
$\deg\left(\mathcal{P}^{(\alpha,\alpha)}\right)\geq 2$, as it is product of at
least $L_{\ell_{\alpha},b}$ and some $R_{\ell_{\alpha},\ell_{i^{\prime}}}$.
Having established this setup, we now upper bound
$\left|Z^{t}_{a,b}(X,0,T)\right|$. To this end we define

$F(S_{i},\mathcal{L}_{S_{i}}):=\sum_{\ell_{i+1}\in
T_{i+1},\ldots,\ell_{t^{\prime}}\in T_{t^{\prime}}}\left(\prod_{t^{\prime}\geq
j>i}\mathcal{P}^{(j,j)}(S_{j}^{\prime},\mathcal{L}_{S_{j}^{\prime}})\right)$
(7)

Then,

$F(S_{i-1},\mathcal{L}_{S_{i-1}})=\sum_{\ell_{i}\in
T_{i}}\mathcal{P}^{(i,i)}(S_{i}^{\prime},\mathcal{L}_{S_{i}^{\prime}})F(S_{i},\mathcal{L}_{S_{i}})$

and $Z^{t}_{a,b}(X,0,T)=F(S_{0},\mathcal{L}_{S_{0}})$ where $S_{0}=\emptyset$.

We first obtain a bound on sum of variables of the form $\sum_{i\in
T_{i}}R^{c}_{i,j}$ where $c\geq 2$. We shall use this result as in this part
we deal with sum of monomials where the variables may have higher individual
degrees.

######  Lemma 5.12.

Let $c\geq 2$ and $T\subseteq[n]$ so that $p(1-q)\cdot|T|\geq 1$. Then with
probability $1-n^{-4\log(n)^{2}}$ we have

$\left|\sum_{i\in T}R^{c}_{i,j}\right|\leq 192p(1-q)\cdot|T|\cdot(\log n)^{3}$

###### Proof.

Recall that $R_{i,j}$ is a zero mean random variable with one of the two
distributions.

  1. 1.

If $i\sim j$, then $R^{c}_{i,j}$ is $(1-p)^{c}$ with probability $p$, and
$(-p)^{c}$ with probability $1-p$. Then

$E[R^{c}_{i,j}]=(1-p)^{c}p+(-p)^{c}(1-p)=p(1-p)\cdot((1-p)^{c-1}-(-p)^{c-1})$

Since $\left|(1-p)^{c-1}-(-p)^{c-1}\right|\leq 1$, we have
$\left|E[R^{c}_{i,j}]\right|\leq p(1-p)$.

  2. 2.

If $i\nsim j$ then $R^{c}_{i,j}$ is $(1-q)^{c}$ with probability $q$ and
$(-q)^{c}$ otherwise. Then $\left|E[R^{c}_{i,j}]\right|\leq q(1-q)$.

Thus, the random variable is two valued with the two points being less than
$1$ distance apart, and has expectation upper bounded as $|E[R^{c}_{i,j}]|\leq
p(1-q)$. Then Chernoff’s theorem (Theorem 2.5) implies that with probability
$1-n^{-4(\log n)^{2}}$,

$\displaystyle-p(1-q)|T|-192\sqrt{p}\sqrt{|T|}(\log n)^{3}\leq\sum_{i\in
T}R^{c}_{i,j}\leq p(1-q)|T|+192\sqrt{p}\sqrt{|T|}(\log n)^{3}$
$\displaystyle\implies$ $\displaystyle\left|\sum_{i\in
T}R^{c}_{i,j}\right|\leq p(1-q)|T|+192\sqrt{p}\sqrt{|T|}(\log n)^{3}$
$\displaystyle\implies$ $\displaystyle\left|\sum_{i\in
T}R^{c}_{i,j}\right|\leq 192p(1-q)|T|(\log n)^{3}$

∎

We then have the following result

######  Lemma 5.13.

Let $\deg(\mathcal{P}^{(i,i)})=w_{i}$. If
$\left|F(S_{i},\mathcal{L}_{S_{i}})\right|\leq\beta$ with probability
$p_{\beta}$, then

  1. 1.

If $X[t]=i$, then with probability $p_{\beta}(1-n^{-3(\log n)^{2}})$

$\left|F(S_{i-1},\mathcal{L}_{S_{i-1}})\right|\leq\beta\cdot
96(p-q)\sqrt{p}\sqrt{s^{*}}(\log n)^{3}\cdot(96\sqrt{p}\sqrt{n}(\log
n)^{3})^{w_{i}-1}$

  2. 2.

Otherwise with probability $p_{\beta}(1-n^{-3(\log n)^{2}})$

$\left|F(S_{i-1},\mathcal{L}_{S_{i-1}})\right|\leq\beta\cdot(96\sqrt{p}\sqrt{n}(\log
n)^{3})^{w_{i}}$

###### Proof.

Equation (7) implies that

$F(S_{i-1},\mathcal{L}_{S_{i-1}})=\sum_{\ell_{i}\in
T_{i}}\mathcal{P}^{(i,i)}(S_{i}^{\prime},\mathcal{L}_{S_{i}^{\prime}})F(S_{i},\mathcal{L}_{S_{i}})$

We analyze the first case here, and the second case then follows. As in Lemma
5.5, we
$\mathcal{P}^{(i,i)}(S_{i}^{\prime},\mathcal{L}_{S_{i}^{\prime}})F(S_{i},\mathcal{L}_{S_{i}})$
is a zero mean random variable. And since $X[t]=i$, then for some
$S\subseteq[i]$ and $c_{j}$ being positive integers,

$\mathcal{P}^{(i,i)}=\prod_{j\in S}R^{c_{j}}_{\ell_{i},\ell_{j}}\cdot
L_{\ell_{i},b}$

Here note that $w_{i}\geq 2$ as $\mathcal{P}^{(i,i)}$ contains
$L_{\ell_{i},b}$ and at least one variable from $R$. The following events then
happen with probability $(1-n^{-3(\log n)^{2}})p_{\beta}$.

  * •

If $w_{i}=2$, then
$\mathcal{P}^{(i,i)}=R_{\ell_{i},\ell_{i^{\prime}}}L_{\ell_{i},b}$ for some
$i^{\prime}$ and $\left|F(S_{i-1},\mathcal{L}_{S_{i-1}})\right|$ can be
directly upper bounded by $\beta\cdot 96(p-q)\sqrt{p}\sqrt{s^{*}}(\log n)^{3}$
from Lemma 5.5 (scaling the variables with $1/\beta$ and applying Chernoff
bound).

  * •

Otherwise, if $w_{i}>2$, $\left|\mathbb{E}[\mathcal{P}^{(i,i)}]\right|\leq
p(1-q)$. Then Lemma 5.12 implies that with probability
$p_{\beta}\cdot(1-n^{-3(\log n)^{2}})$,

$\displaystyle\left|F(S_{i-1},\mathcal{L}_{S_{i-1}})\right|$
$\displaystyle\leq\beta\cdot 96(p-q)\cdot p(1-q)s^{*}(\log n)^{3}$
$\displaystyle\leq 96(p-q)\sqrt{p}\sqrt{s^{*}}(\log
n)^{3}\cdot(96\sqrt{p}\sqrt{n}(\log n)^{3})^{w_{i}-1}$ [As
$s^{*}\leq\sqrt{s^{*}}\sqrt{n}$]

The case for $X[t]\neq i$ also follows in the same manner. ∎

This result gives us an upper bound on $\left|Z^{t}_{a,b}(X,0,T)\right|$ by
iterating $t^{\prime}-1$ times through Lemma 5.13.

######  Corollary 5.14.

Let $t^{\prime}\leq\log n$ and $T=\\{T_{1},\ldots,T_{t^{\prime}}\\}$ be any
fixed partition. Recall that $C_{t}=(96\sqrt{p}(p-q)\sqrt{s^{*}}(\log
n)^{3})\cdot(96\sqrt{p}\sqrt{n}(\log n)^{3})^{t-1}$. Then we have

$\Pr\left(\left|Z^{t}_{a,b}(X,0,T)\right|\leq C_{t}\right)\geq 1-n^{-2(\log
n)^{2}}$

Finally, to bound the expectation, as before we have

$|Z^{t}_{a,b}(X,0)|\leq(t^{\prime})^{t^{\prime}}\underset{T}{\mathbb{E}}[|Z^{t}_{a,b}(X,0,T)|]$
(8)

Once we have an upper bound for an arbitrary $T$, the same analysis as for
$W^{t}_{\ell_{0},\ell_{t+1}}$ follows for obtaining
$\mathbb{E}_{T}[|Z^{t}_{a,b}(X,0,T)|]$, where in we get
$\mathbb{E}_{T}[|Z^{t}_{a,b}(X,0,T)|]\leq 32\log n\cdot C_{t}$ and then get
the following bound on $Z(X,0)$ from Equation 8 (we skip redoing the
calculation for brevity).

######  Corollary 5.15.

$\Pr\left(\left|Z(X,0)\right|\leq t^{t}\cdot 32\log n\cdot C_{t}\right)\geq
1-(\log n)^{\log n}n^{-5}$

The same bound follows for any $Z^{t}_{a,b}(X,i)$ as we merely fix one of the
indices to a single value ($a$) and then randomly partition
$[n]\setminus\\{a\\}$ into $T^{\prime}$ many sets. That is, Corollary 5.15
implies

$\Pr\left(\left|Z(X,i)\right|\leq t^{t}\cdot 32\log n\cdot C_{t}\right)\geq
1-(\log n)^{\log n}n^{-5}$ (9)

We can now summarize to complete the proof.

##### Proof of Lemma 3.8

Combining Equations (5) and (9) via an union bound on all $(t+1)\cdot t^{t}$
possibilities, we get with probability $1-\mathcal{O}(n^{-4})$,

$\displaystyle|(R^{t}L)_{a,b}\leq 32\cdot(t+1)\cdot t^{2t}\cdot\log n\cdot
C_{t}$ $\displaystyle\leq 32\cdot 2^{t}\cdot(t^{2})^{t}\cdot\log
n\cdot(96\sqrt{p}(p-q)\sqrt{s^{*}}(\log n)^{3})\cdot(96\sqrt{p}\sqrt{n}(\log
n)^{3})^{t-1}$ $\displaystyle\leq 32\cdot 2^{t}\cdot((\log n)^{2})^{t}\log
n\cdot(96\sqrt{p}(p-q)\sqrt{s^{*}}(\log n)^{3})\cdot(96\sqrt{p}\sqrt{n}(\log
n)^{3})^{t-1}$ [Substituting $t\leq\log n$] $\displaystyle\leq 128\cdot
96\sqrt{p}(p-q)\sqrt{s^{*}}(\log n)^{6}\cdot(192\sqrt{p}\sqrt{n}(\log
n)^{5})^{t-1}$ $\displaystyle\leq 12228(p-q)(\log
n)^{6}\cdot((p-q)\sqrt{s^{*}})\cdot((p-q)s^{*})^{t-1}$ [ $(p-q)s^{*}\gg
192\sqrt{p}\sqrt{n}(\log n)^{5}$]

This completes the proof.

## References

  * [Abb17] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  The Journal of Machine Learning Research, 18(1):6446–6531, 2017\.
  * [ACX13] Nir Ailon, Yudong Chen, and Huan Xu.  Breaking the small cluster barrier of graph clustering.  In International conference on machine learning, pages 995–1003. PMLR, 2013.
  * [AFWZ20] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  Annals of statistics, 48(3):1452, 2020.
  * [AKS98] Noga Alon, Michael Krivelevich, and Benny Sudakov.  Finding a large hidden clique in a random graph.  Random Structures & Algorithms, 13(3-4):457–466, 1998.
  * [BCLS87] Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser.  Graph bisection algorithms with good average case behavior.  Combinatorica, 7(2):171–191, 1987.
  * [Bop87] Ravi B Boppana.  Eigenvalues and graph bisection: An average-case analysis.  In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 280–285. IEEE, 1987.
  * [DF89] Martin E. Dyer and Alan M. Frieze.  The solution of some random np-hard problems in polynomial expected time.  Journal of Algorithms, 10(4):451–489, 1989.
  * [DK69] Chandler Davis and W. M. Kahan.  Some new bounds on perturbation of subspaces.  Bulletin of the American Mathematical Society, 75(4):863 – 868, 1969.
  * [EBW18] Justin Eldridge, Mikhail Belkin, and Yusu Wang.  Unperturbed: spectral analysis beyond davis-kahan.  In Firdaus Janoos, Mehryar Mohri, and Karthik Sridharan, editors, Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pages 321–358. PMLR, 07–09 Apr 2018\.
  * [FK81] Zoltán Füredi and János Komlós.  The eigenvalues of random symmetric matrices.  Combinatorica, 1(3):233–241, 1981.
  * [HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social networks, 5(2):109–137, 1983.
  * [Hoe63] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30, 1963.
  * [LR15] Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  The Annals of Statistics, 43(1):215–237, 2015.
  * [McS01] Frank McSherry.  Spectral partitioning of random graphs.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529–537. IEEE, 2001.
  * [MPZ22] Chandra Sekhar Mukherjee, Pan Peng, and Jiapeng Zhang.  Recovering unbalanced communities in the stochastic block model with application to clustering with a faulty oracle.  arXiv preprint arXiv:2202.08522, 2022.
  * [Vu05] V. H. Vu.  Spectral norm of random matrices.  In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 423–430, New York, NY, USA, 2005. Association for Computing Machinery.
  * [Vu18] Van Vu.  A simple svd algorithm for finding hidden partitions.  Combinatorics, Probability and Computing, 27(1):124–140, 2018.
  * [Wig58] Eugene P Wigner.  On the distribution of the roots of certain symmetric matrices.  Annals of Mathematics, pages 325–327, 1958.
  * [YP14] Seyoung Yun and Alexandre Proutière.  Accurate community detection in the stochastic block model via spectral algorithms.  ArXiv, abs/1412.7335, 2014.