Phase Transition in the Generalized Stochastic Block Model

One of the most fundamental and natural problems in data science is to understand an underlying structure from data sets that can be viewed as networks. The problem is known as the clustering or community detection, and it appears in diverse field of studies involving real-world networks.

The stochastic block model (SBM) is one of the most fundamental mathematical models to understand the community structure in networks. An SBM is a random graph with $N$ nodes, partitioned into $K$ disjoint subsets, called the communities, $C_{1},C_{2},\dots,C_{K}$. One can characterize an SBM via its adjacency matrix, which is a symmetric (random) matrix $\widetilde{M}$, whose $(i,j)$-entry $\widetilde{M}_{ij}$ is a Bernoulli random variable depending only on the communities to which the nodes $i$ and $j$ belong. For the clustering of an SBM, it is often useful to analyze the eigenvalues of the adjacency matrix and their associated eigenvectors, which is known as a spectral method.

One of the most prominent examples of spectral methods is the principal component analysis (PCA) in which the behavior of the eigenvectors associated with the extremal eigenvalues are considered to obtain the community structure of the SBM. For an SBM with two communities, the expectation of its adjacency matrix $\widetilde{M}$ has a block structure, i.e.,

In the simplest case of a balanced SBM with $P_{11}=P_{12}=p$, $P_{12}=P_{21}=q$, and the two communities are of equal size, it can be easily checked that $\mathbb{E}[\widetilde{M}]$ has at most two non-zero eigenvalues, $N(p+q)/2$ and $N(p-q)/2$. Thus, if $N(p-q)/2$ is sufficiently large, the perturbation $\widetilde{M}-\mathbb{E}[\widetilde{M}]$ is negligible for the two largest eigenvalues $\widetilde{M}$ and it is possible to determine the community structure from the eigenvector associated with the second largest eigenvalue of $\widetilde{M}$. Equivalently, after subtracting $(p+q)/2$ from each entry, the (shifted) adjacency matrix becomes the sum of a rank-$1$ deterministic matrix and a random matrix with centered entries, and one can use the eigenvector associated with the largest eigenvalue of the shifted adjacency matrix for clustering.

The sum of a deterministic matrix and a random matrix has been extensively studied in random matrix theory. When the deterministic matrix is rank-$1$ and the random matrix is a Wigner matrix, it is called a (rank-$1$) spiked Wigner matrix. The behavior of the largest eigenvalue of a spiked Wigner matrix is known to exhibit a sharp phase transition depending on the ratio between the spectral norms of the deterministic part and the random part. This type of phase transition is called the BBP transition, after the seminal work of Baik, Ben Arous, and Péché [5] for spiked (complex) Wishart matrix. From the BBP transition, we can immediately see that the detection of the signal is possible via PCA when the signal-to-noise ratio (SNR) is above a certain threshold.

While the BBP transition has been proved for spiked Wigner matrices under various assumptions [20, 15, 8, 7], it is not directly applicable to the SBM, since the entries in a Wigner matrix are i.i.d. (up to symmetry constraint) whereas those in the adjacency matrix of an SBM are not. The proof of the BBP transition with an SBM is substantially harder. For example, unless the SBM is balanced, the empirical spectral distribution (ESD) of $\widetilde{M}$ does not even converge to the semi-circle distribution, which is the limiting ESD of a Wigner matrix; the limiting ESD in this case is not given by a simple formula as the semi-circle distribution but by an implicit formula via its Stieltjes transform.

In this section, we precisely define the matrix model that we consider in this paper and state our main theorem. We begin by introducing a shifted, rescaled matrix for a generalized stochastic block model with two communities.

For an adjacency matrix $\widetilde{M}$ in (1.1), if $P_{11}=p_{1}$, $P_{22}=p_{2}$, and $P_{12}=P_{21}=q$, then after shifting and rescaling, we find that

(See Appendix B for more detail.)

We remark that $H_{ij}$ are not necessarily Bernoulli random variables. The assumption on the finite moment means that the model is in the dense regime. The most typical balanced stochastic block model with two communities correspond to the choice of parameters $|S|=N/2$ and $\alpha_{1}=\alpha_{2}>1$.

Our main theorem is the following result on the phase transition for the spectral gap of GSBM.

We do not include the precise formulas for the critical value $\lambda_{c}$ and the gap $g$ in the statement of Theorem 2.1 for the general cases since they are lengthy but not particularly informative. The formulas for the special cases can be found in Section 3.

In this section, we focus on several specific models and check how the main result, Theorem 2.1, applies to them.

Recall that we denote by $\lambda_{1}$ and $\lambda_{2}$ the two largest eigenvalues of $M$. Let $\mu_{1}$ and $\mu_{2}$ be the two largest eigenvalues of $H$. From the result on the Wigner-type matrices, we find that $\mu_{1}$ and $\mu_{2}$ converge to the rightmost edge of the limiting ESD of $H$. By the Cauchy interlacing formula, we have the inequality

which shows that $\lambda_{2}$ also converges to the rightmost edge of the limiting ESD of $H$.

From the minimax principle,

which shows that $\lambda_{1}$ is an increasing function of $\lambda$. Further, since $\lambda_{1}\geq\mu_{1}$ and

we find that $\lambda_{1}-\mu_{1}=o(1)$ if $\lambda=o(1)$ and $\lambda_{1}>\mu_{1}+1$ if $\lambda>2\mu_{1}+1$. Thus, since $\lambda_{1}$ is a continuous function of $\lambda$, conditional on $H$ there exists $\lambda_{c}$ such that the statement of Theorem 2.1 holds. It thus remains to show that $\lambda_{c}$ and $\mu$ are deterministic in the sense that the same statement holds without conditioning on $H$.

Our proof is based on the Stieltjes transform method in random matrix theory for which we use the following definition:

For the noise $H$, we consider its resolvent $G(z)$ defined by

for $z\in\mathbb{C}\backslash\mathrm{spec}\,(H)$. Note that the normalized trace $m:=N^{-1}\operatorname{Tr}G$ is equal to the Stieltjes transform of the empirical spectral distribution (ESD) of $H$.

To find the largest eigenvalue of $M=H+\lambda uu^{T}$, we recall that any eigenvalue $z$ of $M$ satisfies

which can be further decomposed into

Thus, if $z$ is not an eigenvalue of $H$, we find that $\det(H-zI)=0$, and hence

We now claim that $(H-zI)^{-1}\lambda uu^{T}$ has rank one. To prove the claim, we notice that for any $v\in\mathbb{R}^{N}$,

It implies that the range of $(H-zI)^{-1}\lambda uu^{T}$ is contained in $\mathrm{span}\,((H-zI)^{-1}\lambda u)$, which is a 1-dimensional space.

Since $(H-zI)^{-1}\lambda uu^{T}$ has rank 1, it has only one non-zero eigenvalue, which we call $\lambda_{0}$. Then, $\lambda_{0}$ is $-1$ for otherwise every eigenvalues of $I+(H-zI)^{-1}\lambda uu^{T}$ is non-zero, contradicting (4.3). Furthermore, it is also obvious that $(H-zI)^{-1}\lambda u$ is an eigenvector associated with the eigenvalue $-1$. Thus,

which leads us to the equation

For the noise matrix $H$, which is a Wigner-type matrix considered in [4], we have that

for any $z$ not contained in an open neighborhood of the support of the limiting ESD of $H$, where we let $\mathbf{m}:=(m_{1},m_{2},\dots,m_{N})$ be the solution to the quadratic vector equation (QVE)

is satisfied for $i,\ j=1,2,...,N$. (See Appendix A for the precise statement of (4.5).) We remark that the uniqueness of the solution $m$ for (4.6) is also known [3].

To solve the equations (4.4) and (4.6), we need to estimate $m(z)$ from the assumption on the community structure in Definition 2.1. Assume for the simplicity that $S=\{1,2,\dots,N_{1}\}$. From the symmetry, we have an ansatz

Then, we can rewrite (4.6) as

which can be further simplified (after omitting the $z$-dependence) to

We can thus conclude that if there exists real $z$ that solves (4.7) under the assumption

then $\lambda_{1}$ converges to $z$ with high probability. Since (4.8) is deterministic, we find that the gap $g$ is deterministic in the supercritical case $\lambda>\lambda_{c}$.

It remains to find the critical $\lambda_{c}$. Recall that we set $m:=N^{-1}\operatorname{Tr}G$. From the Stieltjes inversion formula, the (normalized) imaginary part of $m(z)$ corresponds to the density of the limiting ESD of $H$ at $\operatorname{Re}z$. Thus, after changing (4.7) as a single equation involving $z$ and $m$ only, i.e., $f(z,m)=0$, we find that the upper edge $L_{+}$ of the ESD of $H$ is the largest real number such that $f(L_{+},m)=0$ has a double root when considered as an equation for $m$. (Note that technically the condition can be checked by solving $f(L_{+},m)=0$ and $\frac{\partial}{\partial m}f(L_{+},m)=0$ simultaneously.) We can thus conclude that $\lambda_{c}$ is determined as the largest number such that when $\lambda=\lambda_{c}$ the solution $z$ for the equation (4.7) under the assumption (4.8) coincides with $L_{+}$. This in particular shows that $\lambda_{c}$ is also deterministic and completes the proof of Theorem 2.1.

In this paper, we considered the generalized stochastic block model with two communities. We showed the phase transition in the GSBM where the random part is the Wigner-type matrix, which extends the BBP transition. For the precise formulas, we discussed a hidden community model and unbalanced stochastic block model with Bernoulli distribution and Gaussian distribution at the Kesten–Stigum threshold. Both models can be improved for a non-Gaussian case.

We believe that it is possible to prove the phase transition for the sparse matrix in which the data matrix is not necessarily symmetric and most of the elements are composed of zeros. We also hope to extend our result to the GSBM with more than two communities.