SBM is specified by parameters, such as $n,k,p,q$ in the symmetric case. Clustering is usually getting harder for larger $k$ and smaller gap $(p-q)$. Many existing works aim to understand in which regimes of these parameters it is possible to recover the hidden partition. In this regard, the state-of-the-art bound is given by Vu [Vu18]. Concretely, [Vu18] proved that, in the symmetric setting, there is an algorithm that recovers all clusters if $n\geq C\cdot k\left(\frac{\sigma\sqrt{k}+\sqrt{\log n}}{p-q}\right)^{2}$, where $\sigma^{2}\stackrel{{\scriptstyle\mathsf{def}}}{{=}}\max\left\{p(1-p),q(1-q)\right\}$ and $C$ is a constant.

Besides analyzing spectral algorithms in theory, the other purpose, which is the primary purpose of this paper, is to explain the usefulness of such algorithms in practice. Indeed, as we mentioned before, many spectral-based algorithms, as observed in practice, can filter the noise and address the curse of dimensionality [ARS⁺04, SEK04, ZLWZ09, KAH19]. Some representative algorithms are PCA and SVD. Furthermore, it has been observed that spectral algorithms used in practice, such as PCA or SVD, are usually very simple: they just project data points into some lower-dimension subspace, and no extra steps are conducted.

In stark contrast, most of the aforementioned theoretical algorithms have pre-processing or post-processing steps. For example, the idea in [LR15] is that one first applies SVD, and then runs a variant of K-means to clean up the clustering; the main algorithm in [Vu18] partitions the graph into several parts and uses these parts in different ways. As noted in [Vu18], these extra steps are only for the purpose of theoretical analysis: From the perspective of algorithm design, these extra steps appear redundant. Later on, [AFWZ20] coined the phrase vanilla spectral algorithms to describe spectral algorithms that do not include any additional steps. Both [Vu18] and [AFWZ20] conjectured that vanilla spectral algorithms are themselves good clustering algorithms. In practice, this is a widely-used heuristic; however, in theory, the analysis of vanilla spectral algorithms is not satisfactory due to the lack of techniques for analysis. We refer to [MZ22b] for a detailed discussion on barriers of the current analysis.

Our main focus is particularly on vanilla spectral algorithms for two reasons:

1. 1.

   Vanilla spectral algorithms are the most popular in practice—no extra steps are widely used. Plus, their performance seems good enough. The lack of theoretical analysis is mostly due to technical obstacles.

2. 2.

   A vanilla spectral algorithm is often simple and is not specifically designed for theoretical models such as SBM. In contrast, some complicated algorithms use extra steps which are designed for SBM. These steps made the analysis of SBM go through (as commented by [Vu18]). Meanwhile, these extra steps exploit specific structures and may cause ‘overfittings’ on SBM, which makes these algorithms less powerful in practice.

The main purpose of this paper is to theoretically understand the power of practically successful vanilla spectral algorithms. To this end, we study SBM as a preliminary demonstration. We do not aim to design algorithms for SBM that outperforms existing algorithms.

To study spectral algorithms in signal-plus-noise models, a key step is to understand how random noise perturbs the eigenvectors of a matrix. A commonly-used technical ingredient is the Davis-Kahan $\sin\Theta$ theorem (or its variant). However, this type of approach faces two challenges in the SBM.

• •

  Davis-Kahan leads to worst-case perturbation bounds. For perturbations caused by random noises, such as signal-plus-noise models, Davis-Kahan $\sin\Theta$ theorem is sometimes suboptimal.

• •

  These $\sin\Theta$ theorems only lead to bound on $2$-norm. However, in the SBM analysis, we may need $(2\to\infty)$-norm bounds. See [CTP19] for more discussions.

Previous works such as [AFWZ20, EBW18, PPV⁺19] mainly followed this approach. They proposed some novel ideas to (partially) address these two challenges, but only apply to the case of $k=O(1)$. In contrast, our approach, following the power-iteration-based analysis proposed by [MZ22b], completely avoids Davis-Kahan $\sin\Theta$ theorem and can handle the case of $k=\omega(1)$.

Inspired by power iteration methods, Mukherjee and Zhang [MZ22b] proposed a new approach to analyze the perturbation of random matrices. The idea is to approximate the eigenvectors of a matrix by its power. In fact, this method has been widely used in practice as a fast algorithm to approximate eigenvectors. However, there are two limitations of [MZ22b].

• •

  Their analysis requires a nice structure of the mean matrix, i.e., all large eigenvalues are more or less the same.

• •

  Their algorithm is not vanilla as it has a ‘centering step’. Moreover, their algorithm requires the knowledge of parameters $p,q,k$, and particularly, the centering step alone requires the knowledge of $q$. In comparison, we only need to know $k$; further, we can also guess $k$ (by checking the number of large eigenvalues) and then make Algorithm 1 fully parameter-free.

To overcome these limitations, we introduce a novel ‘polynomial approximation + entrywise analysis’ method, which makes this analysis more robust and requires less structure. More details will be discussed in Section 1.4.

The difference between the parameters in our results and those in Vu’s paper is that we replaced $\sigma$ by $\sqrt{p}\log^{6}n$. If $p<0.9$, $\sigma$ and $\sqrt{p}$ are equal up to constant, so our bound is essentially the same as [Vu18] except for the $\log^{6}n$ factor. We believe the extra $\log^{6}n$ factor can be improved by future works. This term stems from the new concentration inequality we used as a black box. A refined analysis of this concentration inequality may remove this factor. Here are two example settings of parameters that satisfy the conditions in Theorem 1.1:

• •

  $q=\Theta(\frac{\log n}{n}),p=\Omega(\frac{k\log^{6}n}{\sqrt{n}})$;

• •

  $p-q=\Theta(1)$ and $k=O(\frac{\sqrt{n}}{\log^{6}n})$.

It is known that $P_{\widehat{G}_{k}}$ (resp., $P_{G_{k}}$) can be write as a polynomial of $\widehat{G}$ (resp., $G$). By Weyl’s inequality, the eigenvalues of $\widehat{G}$ are not too far from those of $G$. Therefore, in our case, one can find a simple polynomial $\varphi$ which only depends on $G$, such that $\varphi(\widehat{G})$ (resp., $\varphi(G)$) is a good approximation of $P_{\widehat{G}_{k}}$ (resp., $P_{G_{k}}$); this is formalized in Lemma 3.2. Then we have the following decomposition: $\left\|P_{\widehat{G}_{k}}E_{u}\right\|\leq 2\left\|\varphi(\widehat{G})E_{u}\right\|\leq 2\left\|\varphi(G)E_{u}\right\|+2\left\|\left(\varphi(\widehat{G})-\varphi(G)\right)E_{u}\right\|,$ where the first inequality follows from Lemma 3.2, which roughly says $\varphi(\widehat{G})$ is a good approximation of $P_{\widehat{G}_{k}}$.

1. 1.

   The first term, $\left\|\varphi(G)E_{u}\right\|$, is small with high probability. To see this, we use Lemma 3.2 again: $\left\|\varphi(G)E_{u}\right\|\leq\frac{3}{2}\left\|P_{G_{k}}E_{u}\right\|$. According to a known result (c.f. Proposition 2.4), $\left\|P_{G_{k}}E_{u}\right\|$ is small with high probability, largely because the projection $P_{G_{k}}$ and the vector $E_{u}$ are independent.

2. 2.

   The second term is the tricky part, and we draw on an entrywise analysis. Namely, we study every entry of $(\varphi(\widehat{G})-\varphi(G))E_{u}$, using the new inequality from [MZ22b]. See Lemma 3.3 for more details.

The upper bound for the noise term is encapsulated in Lemma 3.4.

The following argument is reminiscent of [Vu18]. Say $u\in V_{\ell}$. Note that $G\chi_{\ell}=\sqrt{s_{u}}\cdot G_{u}$ where $\chi_{\ell}=\frac{1}{\sqrt{s_{u}}}\cdot 1_{V_{\ell}}$ is the normalized characteristic vector of $V_{\ell}$ (i.e., $1_{V_{\ell}}(v)=1\iff v\in V_{\ell}$). It follows that

where the second inequality holds because $P_{\widehat{G}_{k}}\widehat{G}$ is the best $k$-rank approximation of $\widehat{G}$ and $\mathrm{rank}(G)=k$, and in the third inequality, we use $\left\|(P_{\widehat{G}_{k}}-I)\right\|_{2}\leq 1$, as $P_{\widehat{G}_{k}}$ is a projection matrix. Therefore,

A typical result in random matrix theory (c.f. Proposition 2.3) states that with high probability, $\left\|E\right\|_{2}=O(\sqrt{n})$. Combining Equation 2 and $s_{u}\approx n/k$, we get $\left\|(P_{\widehat{G}_{k}}-I)G_{u}\right\|=O(\sqrt{k}).$ And by our assumption on $n$, we have $\sqrt{k}=o((p-q)n/k)=o(\Delta)$.

The major novelty of our analysis is using the polynomial $\varphi$. [MZ22b] used a centering step to make the mean matrix nicely structured, while in our analysis, we used polynomial approximation to address this issue. Another difference is that in [MZ22b], the centering step appears explicitly in the algorithm. By contrast, our polynomial approximation only appears in the analysis — the algorithm is vanilla.

As a byproduct, we developed new techniques for studying eigenspace perturbation, a typical topic in random matrix theory. Our high-level idea is “polynomial approximation + entrywise analysis”. That is, we reduce the analysis of eigenspace perturbation to the analysis of a simple polynomial (of matrix) under perturbation. We have more tools to deal with the latter.

Note that $G=H+q\mathbf{1}_{n}\mathbf{1}_{n}^{\top}$, where $H=\begin{pmatrix}(p-q)J_{s_{1}}&\mathbf{0}&\mathbf{0}&\mathbf{0}\\ \mathbf{0}&(p-q)J_{s_{2}}&\mathbf{0}&\mathbf{0}\\ \mathbf{0}&\mathbf{0}&\ddots&\mathbf{0}\\ \mathbf{0}&\mathbf{0}&\mathbf{0}&(p-q)J_{s_{k}}\end{pmatrix}.$ Without loss of generality, assume that $s_{1}\geq s_{2}\geq\cdots\geq s_{k}$. It is easy to see that the eigenvalues of $H$ are $(p-q)s_{1},\dots,(p-q)s_{k},0.$ Viewing $G$ as a rank-one perturbation of $H$, we have the following theorem that characterizes eigenvalues of $G$. Its proof, in Appendix C, readily follows from a theorem in [BNS79], which studies eigenvalues under rank-one perturbation.

Let $\mu\stackrel{{\scriptstyle\mathsf{def}}}{{=}}(p-q)\frac{n}{k}$, and let $\psi(t)$ be the quadratic polynomial such that $\psi(\lambda_{1}(G))=\psi(\mu)=1,\psi(0)=0$, i.e., $\psi(t)\stackrel{{\scriptstyle\mathsf{def}}}{{=}}-\frac{1}{\lambda_{1}(G)\mu}(t-\lambda_{1}(G))(t-\mu)+1\stackrel{{\scriptstyle\mathsf{def}}}{{=}}At^{2}+Bt,$ where $A=-\frac{1}{\lambda_{1}(G)\mu},B=\frac{1}{\lambda_{1}(G)}+\frac{1}{\mu}$. Finally, let $\varphi(t)\stackrel{{\scriptstyle\mathsf{def}}}{{=}}(\psi(t))^{r}$ where $r\stackrel{{\scriptstyle\mathsf{def}}}{{=}}\log n$.

Here we give some intuition for the choice of $\varphi$. Let $\widehat{G}=\sum_{i=1}^{n}\widehat{\lambda}_{i}v_{i}v_{i}^{\top}$ be the spectral decomposition of $\widehat{G}$. Then $\varphi(\widehat{G})=\sum_{i=1}^{n}\varphi(\widehat{\lambda}_{i})v_{i}v_{i}^{\top},P_{\widehat{G}_{k}}=\sum_{i=1}^{k}v_{i}v^{\top}.$ The spectral decomposition of $\varphi(\widehat{G})-P_{\widehat{G}_{k}}$ is $\varphi(\widehat{G})-P_{\widehat{G}_{k}}=\sum_{i=1}^{k}(\varphi(\widehat{\lambda}_{i})-1)v_{i}v^{\top}+\sum_{i=k+1}^{n}\varphi(\lambda_{i})v_{i}v^{\top}.$ Hence,

Recall that $\widehat{\lambda_{i}}-\lambda_{i}(G)$ is bounded by Weyl’s inequality. Plus, when the partition is balanced, Theorem 3.1 shows that the eigenvalues of $G$ is nicely distributed: Except for $\lambda_{1}(G)$, other eigenvalues are all close to $\mu$. Hence, our choice of $\varphi$ makes $\left\|\varphi(\widehat{G})-P_{\widehat{G}_{k}}\right\|_{2}$ small, and thus $\varphi(\widehat{G})$ is a good approximation of $P_{\widehat{G}_{k}}$. Formally, we have the following lemma.