edges are permitted, then the diagonals of $E$ would constitute $n$
independent random draws from a centered Bernoulli distribution, and therefore
a rescaled test statistic using the diagonal entries of $E$ would yield
asymptotic normality. In practice one does not observe the matrix $P$ so it
needs to be estimated. In Han et al. ((2019), the authors propose taking the
truncated eigendecomposition of $A$ and estimating $E$ as the residual. More
specifically, define

$\displaystyle\widehat{P}^{(d_{0})}\coloneqq\widehat{U}_{[1:d_{0}]*}\widehat{\Lambda}_{[1:d_{0}]}\widehat{U}_{[1:d_{0}]*}^{\top},$

that is, $\widehat{U}_{[1:d_{0}]*}$ and $\widehat{\Lambda}_{[1:d_{0}]}$
consist of the top $d_{0}$ eigenvectors and eigenvalues, respectively, as
before. From the preceding discussion, under the null hypothesis that
$d=d_{0}$, the residual $\widehat{E}^{(d)}\coloneqq A-\widehat{P}^{(d)}$ is
anticipated to behave approximately like the mean-zero matrix $E$, and test
statistics can be constructed using the entries of $\widehat{E}^{(d)}$.
Moreover, under the alternative $d_{0}<d$, the matrix $\widehat{E}^{(d_{0})}$
should contain some information about the matrix $P$ in it and will not
necessarily be approximately mean-zero.

A major technical difficulty is that the entries of the matrix
$\widehat{E}^{(d)}$ are not independent, and therefore the classical central
limit theorem does not apply by simply summing up the entries of
$\widehat{E}^{(d)}$. The idea proposed in Han et al. ((2019) is to _subsample_
the edges of $\widehat{E}^{(d)}$ in an independent fashion. More precisely,

$\displaystyle T_{n,d_{0},m}\coloneqq\frac{\sqrt{m}\sum_{i\neq
j}\widehat{E}^{(d_{0})}_{ij}Y_{ij}}{\sqrt{2\sum_{i\neq
j}\left(\widehat{E}^{(d_{0})}_{ij}\right)^{2}}},$ (17)

where $Y_{ij}$ are Bernoulli random variables satisfying
$\mathbb{P}[Y_{ij}=1]=m^{-1}$ for $i<j$ and $Y_{ij}=Y_{ji}$ otherwise. The
following result establishes the asymptotic distribution of $T_{n,d_{0},m}$.

######  Theorem 23 (Restatement of Theorems 3.1 and 3.2 of Han et al.
((2019)).

Suppose that $K$ and $B$ remain constant as $n\to\infty$, and suppose that
$A\sim P$ with $P=\rho_{n}ZBZ^{\top}$ with $n_{k}\asymp n_{l}$. Suppose that
$n\rho_{n}\geq n^{\eta}$ for some $\eta>0$. Suppose also that $P$ has $K$
distinct eigenvalues $\lambda_{1},\dots,\lambda_{K}$ satisfying $\min_{i\neq
j}\frac{|\lambda_{i}|}{|\lambda_{j}|}\geq 1+c_{0}$ for some constant $c_{0}>0$
for $\lambda_{i}\neq-\lambda_{j}$. Suppose that $B$ is fixed in $n$ with
$n_{k}\asymp n_{l}$, and suppose that

$\displaystyle n^{1-\eta/2}\ll m\ll\frac{n^{1+\eta}}{\log(n)}.$

Under the null hypothesis of $\mathrm{Rank}(B)=d_{0}$, as
$n\rightarrow\infty$,

$\displaystyle
T_{n,d_{0},m}\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}(0,1).$

If the one-sided alternative hypothesis $d>d_{0}$ holds and

$\displaystyle\left|\sum_{i\neq
j}\sum_{k=d_{0}+1}^{d}\lambda_{k}U_{ik}U_{jk}\right|\ll n\rho_{n},$

then as $n\to\infty$,

$\displaystyle T_{n,d_{0},m}-\frac{\sqrt{m}\sum_{i\neq
j}\sum_{k=d_{0}+1}^{d}\lambda_{k}U_{ik}U_{jk}Y_{ij}}{\sqrt{2\sum_{i\neq
j}\left(\widehat{E}^{(d_{0})}_{ij}\right)^{2}}}\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}(0,1).$

Finally, if instead

$\displaystyle\left|\sum_{i\neq
j}\sum_{k=d_{0}+1}^{d}\lambda_{k}U_{ik}U_{jk}\right|\gg\sqrt{m}\left(\sqrt{n\rho_{n}}+\sum_{d_{0}=1}^{d}|\lambda_{k}|\right),$

then $\mathbb{P}\left[|T_{n,d_{0},m}|>C\right]\to 1$ for any constant $C>0$.

The authors also determine other more general conditions on $m$ such that
asymptotic normality holds. The centering in Theorem 23 reflects the fact that
$\widehat{E}^{(d_{0})}$ contains information from the low-rank matrix in it
when $d_{0}<d$ as exhibited by the appearance of the eigenvalues $\lambda_{k}$
for $d_{0}+1\leq k\leq d$. Specialized to the setting of a full-rank
stochastic blockmodel, their results enable accurately estimating the number
of communities $K$; namely, the series of sequential tests
$d_{0}=1,2,\dots,d_{\max}$ will asymptotically reject at a fixed level
$\alpha$ unless $d=d_{0}$.

Han et al. ((2019) tests whether the rank of $P$ is $d_{0}$, but it does not
include a goodness-of-fit test for specific submodels such as testing for
stochastic blockmodel goodness-of-fit. Lei ((2016) proposes a test
specifically designed for stochastic blockmodels by estimating the matrix $E$
using the estimated communities and then considers taking the largest
eigenvalue of an appropriately rescaled version. Using techniques from random
matrix theory, the author shows the associated null limiting distribution is
Tracy–Widom, but Han et al. ((2019) points out that this test empirically
performs poorly for sparser graphs. While the asymptotic distribution in Lei
((2016) is not asymptotically Gaussian and hence somewhat beyond the scope of
this paper, it highlights some of the fundamental difficulties of devising
principled statistical methodology for statistical network analysis:
statistical theory for network hypothesis testing is significantly affected by
associated asymptotic theory. Han et al. ((2019) relies on the limit theory
developed in Fan et al. ((2020), which in particular require that the sparsity
satisfies $n\rho_{n}=\omega(n^{\eta})$ for some $\eta>0$.

Per this section’s focus on testing, we remark in passing that using the
results in Tang et al. ((2022) or Xie ((2021) it is possible to devise single-
network tests for stochastic blockmodels with distributional guarantees.
Consider, for example, the setting that the block memberships are known. To
test the null hypothesis $B=B^{(0)}$ for some fixed $B^{(0)}$, the results in
Tang et al. ((2022) imply that the spectral estimator for $B$ is
asymptotically efficient; moreover, provided the asymptotic covariance can be
estimated consistently, a simultaneous confidence interval for the
vectorization of $B$ will be asymptotically valid, thereby yielding consistent
testing.

In classical two-sample testing, the user tests whether two sets of
observations plausibly arise from the same distribution or have similar
distributional properties. By analogy, two-graph testing seeks to determine
whether two graphs have similar network-centric distributional properties. One
version of the two-graph hypothesis test assumes that there is a known _a
priori_ correspondence between vertices, which is equivalent to testing
whether $P^{(1)}=P^{(2)}$, where $P^{(1)}$ and $P^{(2)}$ denote the
probability matrices for two observed adjacency matrices $A^{(1)}$ and
$A^{(2)}$. If the correspondence is not known, this test is equivalent to
testing whether $P^{(1)}=\Pi P^{(2)}\Pi^{\top}$, where $\Pi$ is a permutation
matrix. If one assumes the underlying $P$ matrix comes from a stochastic
blockmodel with random community assignments, without the assumption of a
correspondence, one can test whether the two graphs have the same underlying
distributions; this corresponds to testing the hypothesis
$(B^{(1)},\pi^{(1)})=(B^{(2)},\pi^{(2})$.

In many application settings, multiple graphs are vertex-matched, namely
graphs are observed on the same vertex set with known vertex correspondences.
For example, in time series of graphs, one observes the same network evolving
over time. Given a specific vertex of interest, its connectivity profile or
community membership may change over time. When $B^{(1)}=\gamma B^{(2)}$ for
some constant $\gamma$, Li and Li ((2018) considers testing whether the
community memberships between two networks are equal, with null hypothesis

$\displaystyle H_{0}:Z^{(1)}=Z^{(2)}.$

Their test statistic can be viewed as a re-weighted $\sin\Theta$ distance
between the estimated eigenvectors.

######  Theorem 24 (Restatement of Theorem 5 and Theorem 7 of Li and Li
((2018)).

Suppose that $A^{(1)}\sim P^{(1)}$ and $A^{(2)}\sim P^{(2)}$ with
$P^{(1)}=\rho_{n}Z^{(1)}B(Z^{(1)})^{\top}$ and $P^{(2)}=\rho_{n}\gamma
Z^{(2)}B(Z^{(2)})^{\top}$ where $B$ has the form

$\displaystyle B_{kl}$
$\displaystyle=\begin{cases}a&\textnormal{~{}if~{}}k=l;\\\
b&\textnormal{~{}if~{}}k=l,\end{cases}$

with $a$ and $b$ constants. Suppose that $K$ remains constant as $n\to\infty$
and that $n\rho_{n}\geq n^{1/2+\varepsilon}$ for some $\varepsilon>0$. Let
$\widehat{U}^{(1)}$ be the eigenvectors of $A^{(1)}$ and let
$\widehat{U}^{(2)}$ be the eigenvectors of $A^{(2)}$. Let
$\widehat{\Lambda}_{2}$ be the eigenvectors of $A^{(2)}$. Define

$\displaystyle T_{n,K}$
$\displaystyle=\frac{1}{Kn}\|(\widehat{U}^{(1)}W_{1,2}-\widehat{U}^{(2)})\widehat{\Lambda}_{2}\|_{F}^{2},$

where
$W_{1,2}=\operatorname*{arg\,min}_{W\in\mathbb{O}(d)}\|\widehat{U}^{(1)}W-\widehat{U}^{(2)}\|_{F}^{2}$
is the Frobenius optimal orthogonal matrix aligning $\widehat{U}^{(1)}$ and
$\widehat{U}^{(2)}$. Then, under the null hypothesis $H_{0}:Z^{(1)}=Z^{(2)}$
and provided each community size is order $n/K$, in the large-sample limit,

$\displaystyle\frac{T_{n,K}-\mu_{n}}{\sigma_{n}}\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}(0,1),$

where $\mu_{n}$ and $\sigma_{n}$ have the form

$\displaystyle\mu_{n}$
$\displaystyle=\gamma^{2}\rho_{n}b(1-\rho_{n}b)+\rho_{n}b(1-\rho_{n}b)+\frac{1}{K}\bigg{(}\gamma\rho_{n}a(1-\rho_{n}a)+\rho_{n}a(1-\rho_{n}a)-\big{(}\gamma^{2}\rho_{n}b(1-\rho_{n}b)+\rho_{n}b(1-\rho_{n}b)\big{)}\bigg{)};$
$\displaystyle\sigma^{2}_{n}$
$\displaystyle=\frac{2}{nK}\bigg{(}\big{(}\gamma^{2}\rho_{n}b(1-\rho_{n}b)+\rho_{n}b(1-\rho_{n}b)\big{)}^{2}+\frac{\big{(}\gamma^{2}\rho_{n}a(1-\rho_{n}a)+\rho_{n}a(1-\rho_{n}a)\big{)}^{2}-\big{(}\gamma^{2}\rho_{n}b(1-\rho_{n}b)+\rho_{n}b(1-\rho_{n}b)\big{)}^{2}}{K}\bigg{)}$
$\displaystyle\hskip 16.00003pt+o(1).$

Let $q_{\alpha/2}$ and $q_{1-\alpha/2}$ denote the quantiles of a standard
Gaussian distribution associated to $\alpha$, i.e., the $\alpha/2$ and
$1-\alpha/2$ quantiles. Under the local alternative
$\|Z^{(1)}-Z^{(2)}\|_{0}\geq\frac{CK}{n^{1-\varepsilon^{\prime}}\sqrt{\mu_{n}}}$,
with exactly $n/K$ vertices in each community, it holds that

$\displaystyle\mathbb{P}\bigg{[}q_{\alpha/2}<\frac{T_{n,K}-\mu_{n}}{\sigma_{n}}<q_{1-\alpha/2}\bigg{]}\to
1.$

The authors allow $a$ and $b$ to change in $n$ provided
$\frac{a-b}{a}\gtrsim\frac{K\log(n)}{n}$, reflecting the setting in which
perfect community recovery is information-theoretically possible ((Abbe,
2018). The stated asymptotic normality continues to hold when replacing the
parameters with suitable estimators, namely $\mu_{n}\mapsto\widehat{\mu}_{n}$
and $\sigma_{n}\mapsto\widehat{\sigma}_{n}$. The authors do not provide
explicit estimators but mention that they exist using previously established
results such as the methodology of Tang et al. ((2022).

The proof of Theorem 24 proceeds by applying the analysis leading to Theorem
5, which demonstrates that
$\|(\widehat{U}^{(1)}W_{1}-U^{(1)})\Lambda^{(1)}\|_{F}^{2}$ is asymptotically
Gaussian after appropriate normalization and scaling. This argument exploits
the particular structure of $B$ together with the approximation

$\displaystyle\|(\widehat{U}^{(1)}W-U^{(1)})\Lambda^{(1)}\|_{F}^{2}$
$\displaystyle\approx\|(A^{(1)}-P^{(1)})U^{(1)}\|_{F}^{2},$

which follows naturally from the discussion in Section 4.4; see Eq. 10.

Tang et al. ((2017a) proposes a similar test statistic to Li and Li ((2018)
based on Procrustes alignment of the scaled eigenvectors of each graph and
shows that their test statistic concentrates about a constant determined by
the distributions of each graph which can also be viewed as the analogue of
$\mu_{n}$ in the limit theorem for Li and Li ((2018). However, Tang et al.
((2017a) does not study the explicit limiting distribution of their test
statistic, and their main results depend primarily on a concentration
inequality for the Frobenius norm difference between the scaled eigenvectors;
see also Agterberg et al. ((2020); Athreya et al. ((2023) for similar
concentration results.

There have been a few other tests proposed for two graphs, such as Agterberg
et al. ((2020); Tang et al. ((2017b, a); Ghoshdastidar et al. ((2017, 2020),
but these either do not have associated asymptotic normality guarantees or are
not focused on stochastic blockmodels.

###  5.3 Multiple-Graph Asymptotics

The two-sample testing results in Theorem 24 are closely related to the
asymptotic theory derived for a single network in Theorem 5. Analogously,
testing procedures relying on similar theory will by necessity require first
embedding each individual network separately and then aligning them, say via
orthogonal Procrustes. In many practical situations networks may share some
structure such as communities but may contain some network-level differences
such as edge probabilities, so a _joint graph embedding_ may be desirable,
namely, an embedding that includes both shared information from each network
and individual vertex information within each network.

Assuming each graph has the same probability matrix, Levin et al. ((2019)
studies a joint embedding constructed from the scaled eigenvectors of the so-
called _omnibus_ matrix defined as follows. Suppose one observes $L$
independent vertex-matched graphs. The _omnibus matrix_ $\widehat{M}$ is
defined as the matrix

$\displaystyle\widehat{M}\coloneqq\begin{pmatrix}A^{(1)}&\frac{1}{2}(A^{(1)}+A^{(2)})&\cdots&\frac{1}{2}(A^{(1)}+A^{(L)})\\\
\frac{1}{2}(A^{(1)}+A^{(2)})&A^{(2)}&\cdots&\frac{1}{2}(A^{(2)}+A^{(L)})\\\
\vdots&\vdots&\ddots&\vdots\\\
\frac{1}{2}(A^{(1)}+A^{(L)})&\frac{1}{2}(A^{(2)}+A^{(L)})&\cdots&A^{(L)}\end{pmatrix}.$

Obtaining a single embedding for $\widehat{M}$ does not require additional
Procrustes alignment that would otherwise be needed if embedding each graph
separately. The authors derive asymptotic normality guarantees for the scaled
eigenvectors of $\widehat{M}$ when all the probability matrices are the same.

######  Theorem 25 (Theorem 1 of Levin et al. ((2019)).

Suppose $P^{(l)}\equiv ZBZ^{\top}$ with $\mathbb{P}[\tau(i)=k]=\pi_{k}$ and
that $K,L$ and $B={\nu\nu}^{\top}$ remain constant as $n\to\infty$. Let
$\widehat{U}_{\mathrm{OMNI}}$ and $\widehat{\Lambda}_{\mathrm{OMNI}}$ denote
the $Ln\times d$ and $d\times d$ matrices of leading eigenvectors and
eigenvalues of $\widehat{M}$ respectively. There exists a sequence of
orthogonal matrices $W_{*}$ such that as $n\to\infty$,

$\displaystyle\bigg{(}n^{1/2}\big{(}(\widehat{U}_{\mathrm{OMNI}}\widehat{\Lambda}_{\mathrm{OMNI}}^{1/2}W_{*})_{(n-1)l+i*}-{\nu}_{k*}\big{)}\bigg{)}\mid\tau(i)=k\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}\bigg{(}0,\frac{L+3}{4L}\mathbf{\Sigma}_{S}(k)\bigg{)},$

where $\mathbf{\Sigma}_{S}(k)$ is defined in Theorem 7.

The before-scaling asymptotic covariance matrix $\mathbf{\Sigma}_{S}(k)$ is
the same as the asymptotic covariance matrix for the rows of $\widehat{X}$ for
one network as in Section 4. The coefficient $\frac{L+3}{4L}$ simplifies to
one when $L=1$; in general, Pantazis et al. ((2022) shows that this
coefficient is determined by the choice of weights assigned to the diagonal
and off-diagonal block matrices. For example, if, instead of weighting each
block-diagonal element by the average of each corresponding matrix (i.e.,
$\frac{1}{2}$ weighting to both $A^{(i)}$ and $A^{(j)}$), one simply inputs
the average $\frac{1}{L}\sum_{l}A^{(l)}$, then the limiting variance is
instead scaled by $\frac{L^{2}+L-1}{L^{3}}\asymp\frac{1}{L}$, reflecting the
fact that variability shrinks as a larger number of networks $L$ is observed
together with this particular choice of weighting. See Pantazis et al. ((2022)
for further discussion on how the choice of weighting induces correlation
between rows of the associated embedding.

Theorem 25 requires $P^{(l)}=ZBZ^{\top}$ which can be restrictive. The
asymptotic normality of the omnibus embedding and associated bias was further
studied in Draves and Sussman ((2021) in the setting that
$P_{ij}^{(l)}=X_{i*}^{\top}C^{(l)}X_{j*}$, where $C^{(l)}$ is a diagonal
matrix with positive entries. The authors establish the following result.

######  Theorem 26 (Restatement of Theorem 1 of Draves and Sussman ((2021) for
Stochastic Blockmodels).

Suppose that $P^{(l)}=ZB^{(l)}Z^{\top}$ with $B={\nu}C^{(l)}{\nu}^{\top}$ for
some diagonal matrix $C^{(l)}$ with nonnegative diagonal elements, and suppose
that $\min_{i}\max_{l}C^{(l)}_{ii}>0$, with $A^{(l)}$ independent of
$A^{(l^{\prime})}$. Suppose further that ${\nu}$ remains constant as
$n\to\infty$. Suppose also that $\mathbb{P}[\tau(i)=k]=\pi_{k}$ and suppose
that $\sum_{k}\pi_{k}{\nu}{\nu}^{\top}$ is diagonal and full rank. Let
$\widehat{U}_{\mathrm{OMNI}}$ and $\widehat{\Lambda}_{\mathrm{OMNI}}$ be as in
Theorem 25. There exists an orthogonal matrix $W_{*}$ such that with high
probability it holds that

$\displaystyle\left\\{\bigg{(}\big{(}\widehat{U}_{\mathrm{OMNI}}\widehat{\Lambda}_{\mathrm{OMNI}}^{1/2}W_{*}\big{)}_{n(l-1)+i*}-\sqrt{C^{(l)}}{\nu}_{k*}\bigg{)}\mid\tau(i)=k\right\\}=\big{(}\widetilde{C}^{(l)}-\sqrt{C^{(l)}}\big{)}{\nu}_{k*}+N_{n(l-1)+i},$

where $\widetilde{C}^{(l)}=\frac{1}{2}\big{[}C^{(l)}C^{-1/4}+C^{1/4}\big{]}$
with $C=\frac{1}{L}\sum_{l}(C^{(l)})^{2}$, and $N_{n(l-1)+i}$ satisfies

$\displaystyle\|N\|_{2,\infty}$
$\displaystyle\lesssim\frac{L^{3/2}\log(nL)}{n^{1/2}}.$

This decomposition resembles the discussion in Section 4.4; however, there is
an additional term of the form
$\big{(}\widetilde{C}^{(l)}-\sqrt{C^{(l)}}\big{)}{\nu}_{k*}$ appearing on the
right hand side, and the term $N$ behaves as a first-order error, similar to
the bounds in Theorem 6. Succinctly, the rows of the scaled eigenvectors of
$\widehat{M}$ are biased away from $\sqrt{C^{(l)}}{\nu}_{k*}$, with bias
depending on the additional scaling factor $C^{(l)}$ associated to the $l$-th
network. The authors also prove a normality result for the rows of
$\widehat{U}\widehat{\Lambda}^{1/2}$ using this decomposition, which requires
additional expansions for the concentration of the noisy bias about its mean,
and the expansion of the term $N_{(l-1)+i}$ into a linear term plus a small-
order residual.

The _multilayer stochastic blockmodel_ posits that between graphs (layers) the
memberships remain constant while the probabilities of community membership
are allowed to vary between graphs. A number of algorithms have been proposed
for clustering the networks jointly based on spectral methods ((Chen et al.,
2022; Lei and Lin, 2022; Paul and Chen, 2020, 2016) or tensor decompositions
((Jing et al., 2021; Lei et al., 2020a; Lyu et al., 2023), though the focus of
these is often on weak recovery.

For the purpose of jointly clustering based on multiple graphs, having more
networks improves inference and clustering by boosting signal. Consider the
setting where $A^{(1)},\dots,A^{(L)}$ all satisfy
$\mathbb{E}[A^{(l)}]=\rho_{n}ZBZ^{\top}$ for some $\rho_{n}$, $Z$, and $B$ not
depending on $l$. Let $\bar{A}\coloneqq\frac{1}{L}\sum_{l}A^{(l)}$, and let
$\widehat{U}_{\mathrm{ave}}$ denote the leading $d$ eigenvectors of $\bar{A}$.
By an application of the $\ell_{2,\infty}$ bound in Chen et al. ((2021) (see
Theorem 1), the concentration of the leading eigenspace improves by a factor
of $L^{-1/2}$. Similarly, using the methods of proof in previous sections, one
could derive asymptotic normality guarantees for this averaged matrix as both
the number of vertices and the number of graphs tends to infinity, thereby
providing an initial justification for using more networks in jointly
clustering vertices.

The argument in the previous paragraph requires that the networks have the
same edge-probability matrices. Considering asymptotic normality, both Jones
and Rubin-Delanchy ((2021) and Arroyo et al. ((2021) study algorithms for
embeddings in specific multiple graph models that respectively subsume
particular instantiations of the multilayer stochastic blockmodel. In Arroyo
et al. ((2021) the authors study an algorithm for subspace recovery under the
assumption that each graph probability matrix shares a common subspace in the
sense that it can be factored via $US^{(l)}U^{\top}$, where $S^{(l)}$ is a
“score” matrix determining corresponding to graph $l$, and $U$ is an
orthonormal matrix (representing the common subspace). Observe that for a
multilayer stochastic blockmodel one may take $U=Z(Z^{\top}Z)^{-1/2}$ with
$S^{(l)}=(Z^{\top}Z)^{1/2}B^{(l)}(Z^{\top}Z)^{1/2}$.

Let $\widehat{U}^{(l)}$ be the leading $d$ eigenvectors of $A^{(l)}$, and
define $\widehat{U}_{\mathrm{MASE}}$ to be the leading $d$ eigenvectors of the
matrix $\sum_{l=1}^{L}\widehat{U}^{(l)}(\widehat{U}^{(l)})^{\top}$. Note that
$\widehat{U}_{\mathrm{MASE}}$ can also be considered the left singular vectors
of the matrix $[\widehat{U}^{(1)},\dots,\widehat{U}^{(L)}]$. Define

$\displaystyle\widehat{S}^{(l)}$
$\displaystyle\coloneqq\widehat{U}_{\mathrm{MASE}}^{\top}A^{(l)}\widehat{U}_{\mathrm{MASE}}.$

The authors prove the following asymptotic normality result for their
estimates $\widehat{S}^{(l)}$.

######  Theorem 27 (Restatement of Theorem 11 of Arroyo et al. ((2021) for
MLSBMs).

Suppose that $A^{(l)}\sim P^{(l)}$ with $P^{(l)}=\rho_{n}ZB^{(l)}Z^{\top}$
with $n_{k}\asymp n_{l}$ and $n\rho_{n}\gg\log(n)$, with $K,B^{(l)}$ held
constant as $n\to\infty$ and full rank. Define

$\displaystyle\Sigma^{(l)}_{\frac{2k+q(q-1)}{2},\frac{2k+q(q-1)}{2}}$
$\displaystyle=\sum_{s=1}^{n-1}\sum_{t=s+1}^{n}P_{st}^{(l)}(1-P_{st}^{(l)})\big{[}(U_{sk}U_{tq}+U_{tk}U_{sq})(U_{sk^{\prime}}U_{tq^{\prime}}+U_{sk^{\prime}}U_{tq^{\prime}})\big{]}.$

Let $\widehat{S}^{(l)}$ be defined as above. There exists a sequence of
orthogonal matrices $W$ such that

$\displaystyle\bigg{(}\Sigma^{(l)}_{\frac{2k+q(q-1)}{2},\frac{2k^{\prime}+q^{\prime}(q^{\prime}-1)}{2}}\bigg{)}^{-1/2}\big{(}W\widehat{S}^{(l)}W^{\top}-S^{(l)}+H^{(l)})_{kq}\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}(0,1),$

where $H^{(l)}$ is a stochastic offset term satisfying
$\mathbb{E}\|H^{(l)}\|_{F}=O(dL^{-1/2})$.

The authors study the vectorization of $\widehat{S}^{(l)}$ when the matrix
$\Sigma^{(l)}$ is assumed have smallest eigenvalue lower bounded by a
constant. Theorem 27 can be compared to, for example Theorem 15 or Theorem 14,
which demonstrates that the empirical eigenvalues of a single random graph are
biased. The primary difference is that the matrix $S^{(l)}$ takes the place of
the matrix of eigenvalues (albeit no longer diagonal); however, for large $L$
the bias term can be negligible.

In Zheng and Tang ((2022) the authors consider the explicit form of the bias
term $H^{(l)}$ when $n\rho_{n}\gg n^{1/2}$.

######  Theorem 28 (Restatement of Theorem 3.3 of Zheng and Tang ((2022)).

Instate the conditions of Theorem 27, and let $D^{(l)}$ denote the
${n+1\choose 2}\times{n+1\choose 2}$ diagonal matrix with diagonal elements of
the form $P^{(l)}_{k_{1}k_{2}}\left(1-P^{(l)}_{k_{1}k_{2}}\right)$ for
$k_{1}\leq k_{2}$. Define

$\displaystyle\widetilde{D}_{kk}^{(i)}$
$\displaystyle\coloneqq\sum_{q}P_{kq}^{(l)}(1-P_{kq}^{(l)}).$

Let $\mu^{(l)}$ denote the vector

$\displaystyle\mu^{(l)}$
$\displaystyle=\mathrm{vech}\bigg{(}\frac{1}{L}U^{\top}\widetilde{D}^{(l)}U(S^{(l)\top})^{-1}-\frac{1}{2L^{2}}\sum_{l^{\prime}=1}^{L}S^{(l)}(S^{(l^{\prime})})^{-1}U^{\top}\widetilde{D}^{(l^{\prime})}U(S^{(l^{\prime})\top})^{-1}\bigg{)}$
$\displaystyle\quad+\mathrm{vech}\bigg{(}\frac{1}{L}(S^{(l)\top})^{-1}U^{\top}\widetilde{D}^{(l)}U-\frac{1}{2L^{2}}\sum_{l^{\prime}=1}^{L}(S^{(l^{\prime})\top})^{-1}U^{\top}\widetilde{D}^{(l^{\prime})}U(S^{(l^{\prime})})^{-1}S^{(l)}\bigg{)},$

where $\mathrm{vech}$ is the half vectorization extracting the upper triangle
of a matrix, represented as a column vector. There exists a sequence of
orthogonal transformations $W$ such that

$\displaystyle\big{(}\Sigma^{(l)}\big{)}^{\dagger/2}\bigg{(}\mathrm{vech}\big{(}W\widehat{S}^{(l)}W^{\top}-S^{(l)}\big{)}-\mu^{(l)}\bigg{)}\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}\bigg{(}0,\Pi^{(l)}\bigg{)},$

where $(\cdot)^{\dagger}$ denotes the Moore–Penrose pseudoinverse and
$\Pi^{(l)}$ denotes a symmetric idempotent matrix. If $\Sigma^{(l)}$ is
invertible, then $\Pi^{(l)}=I$.

In other words, the stochastic bias term $H^{(l)}$ can be replaced with a
_deterministic_ bias term $\mu^{(l)}$ when $n\rho_{n}\gg n^{1/2}$. This
additional condition $n\rho_{n}\gg n^{1/2}$ is used to establish that the
random bias term concentrates sufficiently about its expectation $\mu^{(l)}$;
a similar requirement appears in Theorem 18. Informally, this condition is
required in order to demonstrate that residual terms of order
$(n\rho_{n})^{-1}$ are of smaller order than $n^{-1/2}$, the latter of which
is the rate of concentration about the expectation and the parametric rate of
convergence to asymptotic normality. The authors also uses this result to
obtain a Hotelling $T^{2}$ test statistic for testing if
$R^{(l)}=R^{(l^{\prime})}$, equivalently, if $B^{(l)}=B^{(l^{\prime})}$.

Zheng and Tang ((2022) also demonstrate the following result for the estimates
$\widehat{U}_{\mathrm{MASE}}$ obtained via the eigenvectors of
$\frac{1}{L}\sum_{l=1}^{L}\widehat{U}^{(l)}\widehat{U}^{(l)\top}$.

######  Theorem 29 (Theorem 3.2 of Zheng and Tang ((2022)).

Instate the conditions of Theorem 27, and suppose that
$n\rho_{n}\gg\log^{2}(n)$ with $L=O(1)$. There exists a sequence of orthogonal
matrices $W_{*}$ such that

$\displaystyle\bigg{(}L^{1/2}n\rho_{n}^{1/2}\big{(}(\widehat{U}_{\mathrm{MASE}}W_{*})_{i*}-U_{i*}\big{)}\bigg{)}\mid\tau(i)=k\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}\bigg{(}0,\mathbf{\Sigma}_{\mathrm{MASE}}(k)\bigg{)}$

with asymptotic covariance matrix given by

$\displaystyle\mathbf{\Sigma}_{\mathrm{MASE}}(k)$
$\displaystyle=\frac{n^{2}\rho_{n}}{L}\sum_{l=1}^{L}\big{(}S^{(l)}\big{)}^{-1}U^{\top}\Xi^{(l,i)}U\big{(}S^{(l)}\big{)}^{-1},$

where $\Xi^{(l,i)}$ is the diagonal matrix with elements of the form
$\Xi^{(l,i)}_{kk}=P_{ik}^{(l)}\left(1-P_{ik}^{(l)}\right)$.

The matrices $S^{(l)}$, $U$, and $\Xi^{(l,i)}$ change with $n$, but, due to
the regularity conditions imposed in Zheng and Tang ((2022), the matrix
$\mathbf{\Sigma}_{\mathrm{MASE}}(k)$ is well-defined. It is also possible to
show that

$\displaystyle\mathbf{\Sigma}_{\mathrm{MASE}}(k)$
$\displaystyle=\frac{1}{L}\sum_{l=1}^{L}\mathbf{\Sigma}_{U}(k),$

where $\mathbf{\Sigma}_{U}(k)$ is the covariance matrix appearing in Theorem
2. To prove Theorem 29, Zheng and Tang ((2022) demonstrate that
$\widehat{U}_{\mathrm{MASE}}$ behaves as an empirical average of the first-
order perturbations of each of the individual networks; namely with high
probability

$\widehat{U}_{\mathrm{MASE}}W-U=\frac{1}{L}\sum_{l=1}^{L}(A-P)U^{(l)}(\Lambda^{(l)})^{-1}+R_{\mathrm{MASE}}=\frac{1}{L}\sum_{l=1}^{L}(A-P)U(S^{(l)})^{-1}+R_{\mathrm{MASE}},$

where $R_{\mathrm{MASE}}$ is a residual term similar to the residual terms in
Eq. 10.

In Jones and Rubin-Delanchy ((2021), the authors consider a multiple random
graph model that subsumes the multilayer stochastic blockmodel by allowing for
general edge probabilities of the form $P^{(l)}=X\Lambda^{(l)}X^{\top}$, where
$\Lambda^{(l)}$ is a general symmetric matrix for the $l$-th graph. For
stochastic blockmodels, one parameterization is $X_{i}=Z_{i*}$ and
$\Lambda^{(l)}=B^{(l)}$, where $B^{(l)}$ is the block probability matrix for
the $l$-th graph. The authors define the “unfolded” matrix
$A_{\mathrm{unfold}}$ in the manner

$\displaystyle
A_{\mathrm{unfold}}\coloneqq[A^{(1)},A^{(2)},\dots,A^{(L)}]\in\\{0,1\\}^{n\times
nL}$

and consider estimating the scaled left and right singular vectors of the
matrix $\mathbf{P}_{\mathrm{unfold}}$, defined analogously.

######  Theorem 30 (Restatement of Theorem 3 of Jones and Rubin-Delanchy
((2021) for Multilayer SBMs).

Let
$\widehat{U}_{\mathrm{unfold}}\widehat{\Lambda}_{\mathrm{unfold}}\widehat{V}_{\mathrm{unfold}}^{\top}$
be the top $r$ truncated singular value decomposition of $A_{\mathrm{unfold}}$
above. Suppose that each $P^{(l)}$ satisfies
$P^{(l)}=\rho_{n}ZB^{(l)}Z^{\top}$ with $n\rho_{n}\gg\log^{c}(n)n^{1/2}$ for
some sufficiently large constant $c>0$. Suppose each
$B^{(l)}=\nu^{(l)}{I}_{p,q}(\nu^{(l)})^{\top}$ is rank $K$ with
$\mathbb{P}[\tau(i)=k]=\pi_{k}$, and suppose $L,K$ and $B$ are constant as
$n\to\infty$. There exists a sequence of invertible linear transformations $T$
depending on $n$ such that

$\displaystyle\bigg{(}n^{1/2}(\widehat{U}_{\mathrm{unfold}}\widehat{\Lambda}_{\mathrm{unfold}}^{1/2}T-e_{k})_{i*}\bigg{)}\mid\tau(i)=k\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}(0,\mathbf{\Sigma}_{\mathrm{unfold}}(k)),$

where the asymptotic covariance matrix satisfies

$\displaystyle\mathbf{\Sigma}_{\mathrm{unfold}}(k)$
$\displaystyle\coloneqq\begin{cases}\Delta_{\mathbf{B}}^{-1}\mathbf{B}\bigg{(}\Gamma^{(k,1)}\oplus\cdots\oplus\Gamma^{(k,L)}\bigg{)}\mathbf{B}^{\top}\Delta_{\mathbf{B}}^{-1},&\textnormal{~{}if~{}}\rho_{n}\equiv
1;\\\
\Delta_{\mathbf{B}}^{-1}\mathbf{B}\bigg{(}\Gamma^{(k,1)}_{o(1)}\oplus\cdots\oplus\Gamma^{(k,L)}_{o(1)}\bigg{)}\mathbf{B}^{\top}\Delta_{\mathbf{B}}^{-1}&\textnormal{~{}if~{}}\rho_{n}\to
0,\end{cases}$

where

$\displaystyle\mathbf{B}$ $\displaystyle\equiv
B_{\mathrm{unfold}}\coloneqq[B^{(1)},\dots,B^{(L)}],$
$\displaystyle\qquad\Delta_{\mathbf{B}},$
$\displaystyle\coloneqq\mathbf{B}\big{(}\mathrm{diag}(\pi)\otimes\mathbf{I}_{L}\big{)}\mathbf{B}^{\top},$
$\displaystyle\Gamma^{(k,l)}$
$\displaystyle\coloneqq\sum_{r=1}^{K}\pi_{r}B^{(l)}_{kr}(1-B^{(l)}_{kr})\nu^{(l)}(\nu^{(l)})^{\top},$
$\displaystyle\qquad\Gamma^{(k,l)}_{o(1)}$
$\displaystyle\coloneqq\sum_{r=1}^{K}\pi_{r}B^{(l)}_{kr}\nu^{(l)}(\nu^{(l)})^{\top},$

where $\oplus$ denotes the direct sum operator and $\otimes$ denotes the
Kronecker product.

The authors also prove similar results for the scaled right singular vectors,
and their results hold more generally, including for directed, bipartite, and
different dimension networks. They also allow for individual network sparsity
which we omit for simplicity.

Theorem 30 requires that $n\rho_{n}\gg\log^{c}(n)n^{1/2}$, which is a stronger
requirement than the minimal requirement $n\rho_{n}\gtrsim\log(n)$ for perfect
clustering when specialized to the single graph setting. Furthermore, the
asymptotic covariance is qualitatively similar to some of the results for
individual rows of scaled eigenvectors discussed in Section 4, only reflective
of the fact that there are multiple graphs. The appearance of the matrices
$\Delta_{\mathbf{B}}^{-1}$ and $\mathbf{B}$ in the definition of
$\mathbf{\Sigma}_{\mathrm{unfold}}(k)$ may informally be viewed as a “matrix
weighted average” of the individual network covariances; in fact, under the
condition that each matrix $B^{(l)}$ is the same, the covariance in Theorem 30
matches the corresponding variance in the single-network setting (e.g.,
Theorem 7), though now scaled by a factor of $L^{-1}$, which coincides with
the setting where adjacency spectral embedding is applied on the averaged
graph.

Many existing asymptotic normality results rely on the assumption that the
absolute value of the smallest nonzero eigenvalue of $P$ tends to infinity at
a rate faster than $\log(n)$. For the $K$-block balanced homogeneous
stochastic blockmodel with $n/K$ vertices in each community, its smallest
eigenvalue is $n(a-b)/K$, and hence this requires $n(a-b)/K\gtrsim\log(n)$. In
Huang et al. ((2020), the authors consider instead the setting that
$n(a-b)/K\ll 1$, meaning that as $n$ tends to infinity the $K$-means
clustering error need not decrease to zero; in fact, the $\ell_{2,\infty}$
results in Section 3.2 do not apply in this regime. More specifically, they
consider the multilayer SBM with $B^{(l)}$ of the form

$\displaystyle B^{(l)}_{kk^{\prime}}$
$\displaystyle=\begin{cases}a^{(l)}&\textnormal{~{}if~{}}k=k^{\prime};\\\
b^{(l)}&\textnormal{~{}if~{}}k\neq k^{\prime},\end{cases}$

for $1\leq l\leq L$, and they study the leading $K$ eigenvectors of the the
matrix $\sum_{l}w_{l}A^{(l)}$, where $w_{l}$ are nonnegative weights summing
to unity. Define

$\displaystyle\tau_{n}^{w}\coloneqq\frac{n\left(\sum_{l}w_{l}(a^{(l)}-b^{(l)})\right)^{2}}{\sum_{l}w_{l}^{2}\left(a^{(l)}(1-a^{(l)})+(K-1)b^{(l)}(1-b^{(l)})\right)},$
(18)

and suppose that $\lim_{n\to\infty}\tau_{n}^{w}=\tau_{\infty}^{w}<\infty$ with
$L$ remaining constant. When $\tau_{n}^{w}\to\infty$, it can be shown that
perfect clustering is information-theoretically possible. However, in Huang et
al. ((2020), the authors study the regime where $\tau_{n}^{w}\not\to\infty$,
which corresponds to a regime wherein perfect clustering is information-
theoretically impossible.

######  Theorem 31 (Restatement of Proposition 3 of Huang et al. ((2020)).

Suppose $P^{(l)}=ZB^{(l)}Z^{\top}$ for $1\leq l\leq L$ with $n/K$ vertices in
each community and where each $B^{(l)}$ is of the form

$\displaystyle B^{(l)}_{kk^{\prime}}$
$\displaystyle=\begin{cases}a^{(l)}&\textnormal{~{}if~{}}k=k^{\prime};\\\
b^{(l)}&\textnormal{~{}if~{}}k\neq k^{\prime},\end{cases}$

where $a^{(l)}$ and $b^{(l)}$ are allowed to depend on $n$, but $L$ and $K$
remain fixed as $n\to\infty$. For a given vector $w$, let $\tau_{n}^{w}$ be
defined as in Eq. 18. Let
$\tau_{\infty}^{w}\coloneqq\lim_{n\to\infty}\tau_{n}^{w}$, and suppose that
$\tau_{\infty}^{w}<\infty$. Further suppose that

  1. 1.

$\sum_{l}w_{l}^{2}\left(a^{(l)}(1-a^{(l)})+(K-1)b^{(l)}(1-b^{(l)})\right)\gtrsim\frac{\log^{4}(n)}{n}$;

  2. 2.

$\left[\sum_{l}w_{l}^{2}a^{(l)}(1-a^{(l)})\right]\left[\sum_{l}w_{l}^{2}b^{(l)}(1-b^{(l)})\right]^{-1}\to
1$.

Let $\eta_{1},\dots,\eta_{K}$ be the $(K-1)$-dimensional vectors such that the
matrix

$\displaystyle\begin{pmatrix}\frac{1}{\sqrt{K}}&\eta_{1}^{\top}\\\
\vdots&\vdots\\\
\frac{1}{\sqrt{K}}&\eta_{K}^{\top}\end{pmatrix}\in\mathbb{R}^{K\times K}$

is orthogonal. Define vectors $\mu_{1},\dots,\mu_{K}$ in the manner

$\displaystyle\mu_{k}$ $\displaystyle\coloneqq\begin{pmatrix}1\\\
\sqrt{\frac{K(\tau_{\infty}^{w}-K)}{\tau_{\infty}^{2}}}\eta_{k}\end{pmatrix}\in\mathbb{R}^{K}.$

Let $\widehat{U}^{(w)}$ denote the leading $K$ eigenvectors of the matrix
$\sum_{l}w_{l}A^{(l)}$. There exists a sequence of orthogonal matrices $W$
such that

$\displaystyle\bigg{(}n^{1/2}\big{(}\widehat{U}^{(w)}W\big{)}_{i*}\bigg{)}\mid\tau(i)=k\quad\xrightarrow{\operatorname{d}}\quad\mathcal{N}(\mu_{k},\mathbf{\Sigma}^{w}),$

where $\mathbf{\Sigma}^{w}$ is given by

$\displaystyle\mathbf{\Sigma}^{w}=\frac{K}{\tau_{\infty}^{w}}\begin{pmatrix}0&0\\\
0&I_{K-1}.\end{pmatrix}.$

The primary difference between the normality result in Theorem 31 and the
previous asymptotic normality results discussed in Section 4 is that since
$a-b\to 0$, the probability matrix collapses to that of an Erdős–Rényi random
graph in this asymptotic regime. The authors state a general scenario where
the technical conditions are that $a^{(l)}\gtrsim\frac{\log^{4}(n)}{n}$, and
$\frac{n(a^{(l)}-b^{(l)})^{2}}{a^{(l)}}\asymp 1$, which reflects sufficiently
dense networks with average expected degree of order at least $\log^{4}(n)$
but where the communities are nearly indistinguishable. On the other hand, for
the setting $a^{(l)}-b^{(l)}\asymp a^{(l)}\asymp b^{(l)}$, the literature
typically emphasizes _sparse_ graphs with distinguishable communities. In the
regime studied in Huang et al. ((2020), the optimal misclustering error need
not vanish in the limit, so their methodology is based on optimizing over
weight vectors $w$ that minimize the asymptotic Bayes-optimal misclustering
error defined by this limiting distribution. Huang et al. ((2020) further
establishes that any two rows of $\widehat{U}^{(w)}$ are asymptotically
independent.

The regime considered in Huang et al. ((2020) is therefore fundamentally
different from other other regimes studied in the literature, and several
extensions are possible. For example, the results in Huang et al. ((2020) are
for the balanced homogeneous stochastic blockmodel, but whether this can be
extended to other types of stochastic blockmodels or multiple stochastic
blockmodels with different block probability matrices is an open problem. In
particular, Huang et al. ((2020) propose an averaging procedure under the
assumption that each block probability matrix is positive definite, but this
averaging procedure may fail if the block probability matrices are
significantly different; for example, if some block probability matrices have
$b>a$. Therefore, an open problem is to determine optimal clustering
procedures in regimes where the cluster separation vanishes but the networks
remain dense. See Kadavankandy and Couillet ((2019) for related considerations
in a similar model setting.

The scaling in Theorem 31 is of the order $n^{1/2}$ as opposed to the scaling
$n\rho_{n}^{1/2}$ appearing in Theorem 2 and Theorem 3. Further, the limiting
covariance matrix is degenerate. When $\tau_{\infty}^{w}<\infty$, the leading
eigenvalues besides the first eigenvalue are no longer well-separated from the
other eigenvalues, since $n\rho_{n}\ll\log(n)$. Therefore, unlike the settings
discussed in Section 4, the matrix $A$ now consists of three parts: the first
is a rank-one matrix corresponding to the (large) leading eigenvalue, the
second part is a rank $K-1$ matrix corresponding to the bottom (small) $K-1$
nonzero eigenvalues, and the third part is a mean-zero matrix. The highly
spiked rank-one component contributes to the degeneracy in the asymptotic
covariance: since the rank-one component is well-separated from the other
eigenvalues, it exhibits qualitatively similar phenomena to the leading
eigenvectors when all the eigenvalues are spiked, and hence it is plausible
for the leading eigenvector to converge in probability to the all ones vector
after scaling by $n^{1/2}$. The second part of the matrix contributes to the
centering: scaling by $n^{1/2}$ stabilizes these expectations, though they are
now slightly biased away from the population eigenvectors. The remaining term
in the decomposition of $A$ is a mean-zero (inhomogeneous Wigner) matrix, and
the final scaling by $n^{1/2}$ is due to considerations stemming from random
matrix theory (e.g., Bai and Pan ((2012)). All three components contribute to
the asymptotic normality presented in Theorem 31.

In the works discussed so far, the number of layers $L$ is fixed while
$n\rightarrow\infty$. In many settings, one has $L\asymp n$, suggesting a need
for statistical theory in this regime. Several works consider settings where
all the network-level block probability matrices $B$ are positive
semidefinite, implying that an averaging procedure will suffice ((Chen et al.,
2022; Paul and Chen, 2016; Bhattacharyya and Chatterjee, 2018; Paul and Chen,
2020). This has been extended in a number of works, though existing theory is
focused on consistency ((Lei and Lin, 2022; Jing et al., 2021).

##  6 Discussion

This survey examines various forms of asymptotic normality arising in
stochastic blockmodels. As we have seen, properties of the underlying edge
probability matrix $B$ play an important role in determining the limiting
covariance matrix, the centering, and the scaling yielding asymptotic
normality. Further, a common theme has emerged for row vectors in graph
embeddings: for not-too-sparse networks, the rows of empirical embeddings are
asymptotically Gaussian about their population counterparts after proper
orientation, with asymptotic covariance impacted by spectral properties of the
$B$ matrix and scaling determined by the relationship between $n$ and
$\rho_{n}$. Consequently, cluster geometry and ‘point cloud shape’ depend on
the underlying network connectivity properties. Networks with communities that
are difficult to distinguish on the basis of connectivity patterns yield
highly elliptical cluster geometry relative to settings where communities have
well-separated, sufficiently different connectivity properties.

Beyond cluster geometry, aggregating information from spectral embeddings also
yields asymptotic normality, only now with scaling and centering determined by
higher-order fluctuations of certain leading-order linear terms, e.g., Eq. 10.
Further, spectral embeddings and related quantities are useful for hypothesis
testing and for parameter estimation. By understanding the geometry of
spectral embeddings, one can devise statistically principled test statistics
with explicit limiting distributions or asymptotically efficient estimators of
population parameters. Information-geometric properties can also _interact_
with latent space geometry; spectral estimators of population parameters
without refinement can lose statistical efficiency in rank-deficient
stochastic blockmodels. For multiple networks, the particular form of the
asymptotic distribution may depend also on the _interaction_ between different
edge probability matrices. Latent space geometry can substantially vary based
on the choice of spectral embedding and data aggregation, manifest in the
diverse expressions for resulting asymptotic covariance matrices, e.g.,
contrast Theorem 30 and Theorem 29.

Numerous open problems remain in the study of stochastic blockmodels. Below,
we conclude with a brief discussion of several pertinent topics.

  * •

Vanishing or weak signals. Beyond Huang et al. ((2020); Kadavankandy and
Couillet ((2019), comparatively few works in the literature address the
asymptotic distributional properties of spectral embeddings when the signal
strength in the model is either weak or vanishing. Such settings require the
further treatment of regularization and normalization when constructing matrix
representations of data and specifying the embedding method. More remains to
be done.

  * •

Asymptotic normality of other embeddings. This survey focuses on embeddings
derived from eigenvectors and eigenvalues of traditional adjacency or
Laplacian matrices. Other graph embeddings are also of interest, particularly
for applications, such as the eigenvectors of the _regularized Laplacian_
matrix ((Qin and Rohe, 2013), or the Node2Vec embedding procedure ((Grover and
Leskovec, 2016). Several recent works in this direction include Zhang and Tang
((2022a); Kloepfer et al. ((2021); Lin et al. ((2023); Barot et al. ((2021).

  * •

Choice of embedding. Different choices of embedding yield different forms of
asymptotic normality, including whether one chooses to scale or not scale the
eigenvectors by the eigenvalues or whether one uses the adjacency matrix or
Laplacian matrix. Several works have studied how different embedding choices
are favored over others depending on the type of underlying $B$ matrix ((Cape
et al., 2019b; Tang and Priebe, 2018; Priebe et al., 2019) but they are
limited to asymptotic regimes wherein perfect node clustering is possible. A
deeper theory-guided practice for embedding selection is broadly needed and of
interest to practitioners.

  * •

Multiple testing problems for networks. Throughout the natural and physical
sciences, analysts frequently encounter or construct multiple networks
corresponding to different populations, for example, brain graphs for healthy
subjects, high-risk subjects, and individuals diagnosed with a particular
disease. Multi-sample testing, discrimination, and comparison are consequently
of interest beyond the two-vertex or two-graph problems discussed in this
survey. To date, ongoing efforts in the study of multilayer or multiplex
networks are paving the way for a deeper statistical understanding and
applicable statistical toolkit for multiple graph inference ((Noroozi and
Pensky, 2022b; Fan et al., 2022b; Pensky and Wang, 2023; Pensky, 2019; Pensky
and Zhang, 2019; Zheng and Tang, 2022; Jones and Rubin-Delanchy, 2021; Jing et
al., 2021; Lei and Lin, 2022; Lei et al., 2020a; Chen et al., 2023; Lyu et
al., 2023).

  * •

Trade-offs between sparsity and the number of networks. Several works have
studied community detection with a large or growing number of sparse networks
((Jing et al., 2021; Lei and Lin, 2022; Lei et al., 2020a; Paul and Chen,
2020; Bhattacharyya and Chatterjee, 2018; Chen et al., 2022; Lyu et al.,
2023), still with a focus on consistency. It is of practical and theoretical
interest to study joint network embeddings and understand how resulting
cluster geometry reflects network sparsity and network sample size.

  * •

Covariates, dependencies, and model generalizations. In practical settings,
networks often have vertex covariates, and edges need not be independent. Some
recent works in the direction include Abbe et al. ((2022); Mele et al.
((2022); Ma and Nandy ((2023); Ma et al. ((2020); Mu et al. ((2022); Razaee et
al. ((2019); Zhang et al. ((2019); Xu et al. ((2022). It will be interesting
to further study model generalizations that incorporate such features.

## Acknowledgements

JA’s research was partially supported by a fellowship from the Johns Hopkins
Mathematical Institute of Data Science (MINDS) via NSF TRIPODS award
CCF-1934979, by the Charles and Catherine Counselman Fellowship, and by the
Acheson J. Duncan Fund for the Advancement of Research in Statistics. JC’s
research was partially supported by the National Science Foundation under
grants DMS-1902755 and SES-1951005.

## References

  * Abbe ((2018) Emmanuel Abbe.  Community Detection and Stochastic Block Models: Recent Developments.  _Journal of Machine Learning Research_ , 18(177):1–86, 2018.  ISSN 1533-7928.
  * Abbe et al. ((2020) Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  _The Annals of Statistics_ , 48(3):1452–1474, June 2020.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/19-AOS1854.
  * Abbe et al. ((2022) Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang.  An $\ell_p$ theory of PCA and spectral clustering.  _The Annals of Statistics_ , 50(4):2359–2385, August 2022.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/22-AOS2196.
  * Agterberg et al. ((2020) Joshua Agterberg, Minh Tang, and Carey Priebe.  Nonparametric Two-Sample Hypothesis Testing for Random Graphs with Negative and Repeated Eigenvalues.  _arXiv:2012.09828 [math, stat]_ , December 2020.
  * Agterberg et al. ((2022) Joshua Agterberg, Zachary Lubberts, and Carey E. Priebe.  Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence.  _IEEE Transactions on Information Theory_ , 68(7):4618–4650, July 2022.  ISSN 1557-9654.  doi: 10.1109/TIT.2022.3159085.
  * Airoldi et al. ((2008) Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing.  Mixed Membership Stochastic Blockmodels.  In _Advances in Neural Information Processing Systems_ , volume 21. Curran Associates, Inc., 2008.
  * Amini et al. ((2013) Arash A. Amini, Aiyou Chen, Peter J. Bickel, and Elizaveta Levina.  Pseudo-likelihood methods for community detection in large sparse networks.  _The Annals of Statistics_ , 41(4):2097–2122, August 2013.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/13-AOS1138.
  * Arroyo and Levina ((2022) Jesús Arroyo and Elizaveta Levina.  Overlapping Community Detection in Networks via Sparse Spectral Decomposition.  _Sankhya A_ , 84(1):1–35, June 2022.  ISSN 0976-8378.  doi: 10.1007/s13171-021-00245-4.
  * Arroyo et al. ((2021) Jesús Arroyo, Avanti Athreya, Joshua Cape, Guodong Chen, Carey E. Priebe, and Joshua T. Vogelstein.  Inference for Multiple Heterogeneous Networks with a Common Invariant Subspace.  _Journal of Machine Learning Research_ , 22(142):1–49, 2021.  ISSN 1533-7928.
  * Athreya et al. ((2016) A. Athreya, C. E. Priebe, M. Tang, V. Lyzinski, D. J. Marchette, and D. L. Sussman.  A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs.  _Sankhya A_ , 78(1):1–18, February 2016.  ISSN 0976-8378.  doi: 10.1007/s13171-015-0071-x.
  * Athreya et al. ((2018) Avanti Athreya, Donniell E. Fishkind, Minh Tang, Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, Keith Levin, Vince Lyzinski, Yichen Qin, and Daniel L. Sussman.  Statistical Inference on Random Dot Product Graphs: a Survey.  _Journal of Machine Learning Research_ , 18(226):1–92, 2018.  ISSN 1533-7928.
  * Athreya et al. ((2021) Avanti Athreya, Joshua Cape, and Minh Tang.  Eigenvalues of Stochastic Blockmodel Graphs and Random Graphs with Low-Rank Edge Probability Matrices.  _Sankhya A_ , November 2021.  ISSN 0976-8378.  doi: 10.1007/s13171-021-00268-x.
  * Athreya et al. ((2023) Avanti Athreya, Zachary Lubberts, Carey E. Priebe, Youngser Park, Minh Tang, Vince Lyzinski, Michael Kane, and Bryan W. Lewis.  Numerical Tolerance for Spectral Decompositions of Random Matrices and Applications to Network Inference.  _Journal of Computational and Graphical Statistics_ , 32(1):145–156, January 2023.  ISSN 1061-8600.  doi: 10.1080/10618600.2022.2082972.
  * Bai and Pan ((2012) Z. D. Bai and G. M. Pan.  Limiting Behavior of Eigenvectors of Large Wigner Matrices.  _Journal of Statistical Physics_ , 146(3):519–549, February 2012.  ISSN 1572-9613.  doi: 10.1007/s10955-011-0407-4.
  * Bandeira and Handel ((2016) Afonso S. Bandeira and Ramon van Handel.  Sharp nonasymptotic bounds on the norm of random matrices with independent entries.  _The Annals of Probability_ , 44(4):2479–2506, July 2016.  ISSN 0091-1798, 2168-894X.  doi: 10.1214/15-AOP1025.
  * Barot et al. ((2021) Aman Barot, Shankar Bhamidi, and Souvik Dhara.  Community detection using low-dimensional network embedding algorithms, November 2021.  arXiv:2111.05267 [cs, math, stat].
  * Bhatia ((1997) Rajendra Bhatia.  _Matrix Analysis_ , volume 169.  Springer, 1997.  ISBN 0-387-94846-5.
  * Bhattacharyya and Bickel ((2015) Sharmodeep Bhattacharyya and Peter J. Bickel.  Subsampling bootstrap of count features of networks.  _The Annals of Statistics_ , 43(6):2384–2411, December 2015.  ISSN 0090-5364.  doi: 10.1214/15-AOS1338.
  * Bhattacharyya and Chatterjee ((2018) Sharmodeep Bhattacharyya and Shirshendu Chatterjee.  Spectral Clustering for Multiple Sparse Networks: I.  _arXiv:1805.10594 [cs, math, stat]_ , May 2018.
  * Bickel et al. ((2013) Peter Bickel, David Choi, Xiangyu Chang, and Hai Zhang.  Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels.  _The Annals of Statistics_ , 41(4):1922–1943, August 2013.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/13-AOS1124.
  * Bickel et al. ((2011) Peter J. Bickel, Aiyou Chen, and Elizaveta Levina.  The method of moments and degree distributions for network models.  _Annals of Statistics_ , 39(5):2280–2301, October 2011.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/11-AOS904.
  * Cai et al. ((2021) Changxiao Cai, Gen Li, Yuejie Chi, H. Vincent Poor, and Yuxin Chen.  Subspace estimation from unbalanced and incomplete data matrices: $\ell_{2,\infty}$ statistical guarantees.  _The Annals of Statistics_ , 49(2):944–967, April 2021.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/20-AOS1986.
  * Cai and Zhang ((2018) T. Tony Cai and Anru Zhang.  Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics.  _Annals of Statistics_ , 46(1):60–89, February 2018.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/17-AOS1541.
  * Cape et al. ((2019a) Joshua Cape, Minh Tang, and Carey E. Priebe.  Signal-plus-noise matrix models: eigenvector deviations and fluctuations.  _Biometrika_ , 106(1):243–250, March 2019a.  ISSN 0006-3444.  doi: 10.1093/biomet/asy070.
  * Cape et al. ((2019b) Joshua Cape, Minh Tang, and Carey E. Priebe.  On spectral embedding performance and elucidating network structure in stochastic blockmodel graphs.  _Network Science_ , 7(3):269–291, September 2019b.  ISSN 2050-1242, 2050-1250.  doi: 10.1017/nws.2019.23.
  * Cape et al. ((2019c) Joshua Cape, Minh Tang, and Carey E. Priebe.  The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics.  _Annals of Statistics_ , 47(5):2405–2439, October 2019c.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/18-AOS1752.
  * Chen et al. ((2023) Li Chen, Jie Zhou, and Lizhen Lin.  Hypothesis testing for populations of networks.  _Communications in Statistics - Theory and Methods_ , 52(11):3661–3684, June 2023.  ISSN 0361-0926.  doi: 10.1080/03610926.2021.1977961.
  * Chen et al. ((2022) Shuxiao Chen, Sifan Liu, and Zongming Ma.  Global and individualized community detection in inhomogeneous multilayer networks.  _The Annals of Statistics_ , 50(5):2664–2693, October 2022.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/22-AOS2202.
  * Chen et al. ((2021) Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma.  Spectral Methods for Data Science: A Statistical Perspective.  _Foundations and Trends® in Machine Learning_ , 14(5):566–806, 2021.  ISSN 1935-8237, 1935-8245.  doi: 10.1561/2200000079.
  * Chung and Graham ((1997) Fan R. K. Chung and Fan Chung Graham.  _Spectral Graph Theory_.  American Mathematical Soc., 1997.  ISBN 978-0-8218-0315-8.  Google-Books-ID: 4IK8DgAAQBAJ.
  * Dasgupta et al. ((2004) A. Dasgupta, J.E. Hopcroft, and F. McSherry.  Spectral analysis of random graphs with skewed degree distributions.  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , pages 602–610, October 2004.  doi: 10.1109/FOCS.2004.61.  ISSN: 0272-5428.
  * Draves and Sussman ((2021) Benjamin Draves and Daniel L. Sussman.  Bias-Variance Tradeoffs in Joint Spectral Embeddings, December 2021.  arXiv:2005.02511 [math, stat].
  * Du and Tang ((2021) Xinjie Du and Minh Tang.  Hypothesis Testing for Equality of Latent Positions in Random Graphs.  _Bernoulli, to appear_ , May 2021.
  * Eldridge et al. ((2018) Justin Eldridge, Mikhail Belkin, and Yusu Wang.  Unperturbed: spectral analysis beyond Davis-Kahan.  In _Algorithmic Learning Theory_ , pages 321–358, April 2018\.
  * Fan et al. ((2020) Jianqing Fan, Yingying Fan, Xiao Han, and Jinchi Lv.  Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes.  _Journal of the American Statistical Association_ , 0(0):1–14, October 2020.  ISSN 0162-1459.  doi: 10.1080/01621459.2020.1840990.
  * Fan et al. ((2022a) Jianqing Fan, Yingying Fan, Xiao Han, and Jinchi Lv.  SIMPLE: Statistical inference on membership profiles in large networks.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 84(2):630–653, 2022a.  ISSN 1467-9868.  doi: 10.1111/rssb.12505.
  * Fan et al. ((2022b) Xing Fan, Marianna Pensky, Feng Yu, and Teng Zhang.  ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network.  _Journal of Machine Learning Research_ , 23(330):1–46, 2022b.  ISSN 1533-7928.
  * Fortunato ((2010) Santo Fortunato.  Community detection in graphs.  _Physics Reports_ , 486(3):75–174, February 2010\.  ISSN 0370-1573.  doi: 10.1016/j.physrep.2009.11.002.
  * Fortunato and Hric ((2016) Santo Fortunato and Darko Hric.  Community detection in networks: A user guide.  _Physics Reports_ , 659:1–44, November 2016.  ISSN 0370-1573.  doi: 10.1016/j.physrep.2016.09.002.
  * Füredi and Komlós ((1981) Z. Füredi and J. Komlós.  The eigenvalues of random symmetric matrices.  _Combinatorica_ , 1(3):233–241, September 1981\.  ISSN 1439-6912.  doi: 10.1007/BF02579329.
  * Gao and Lafferty ((2017) Chao Gao and John Lafferty.  Testing for Global Network Structure Using Small Subgraph Statistics.  _arXiv:1710.00862 [cs, math, stat]_ , October 2017.
  * Gao and Ma ((2021) Chao Gao and Zongming Ma.  Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing.  _Statistical Science_ , 36(1):16–33, February 2021.  ISSN 0883-4237, 2168-8745.  doi: 10.1214/19-STS736.
  * Ghoshdastidar et al. ((2017) Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, and Ulrike von Luxburg.  Two-Sample Tests for Large Random Graphs Using Network Statistics.  In _Proceedings of the 2017 Conference on Learning Theory_ , pages 954–977. PMLR, June 2017.  ISSN: 2640-3498.
  * Ghoshdastidar et al. ((2020) Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, and Ulrike von Luxburg.  Two-sample hypothesis testing for inhomogeneous random graphs.  _The Annals of Statistics_ , 48(4):2208–2229, August 2020.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/19-AOS1884.
  * Goldenberg et al. ((2009) Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg, and Edoardo M. Airoldi.  A Survey of Statistical Network Models.  _Foundations and Trends in Machine Learning_ , 2009.  doi: 10.1561/2200000005.
  * Grover and Leskovec ((2016) Aditya Grover and Jure Leskovec.  node2vec: Scalable Feature Learning for Networks.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, pages 855–864, New York, NY, USA, August 2016. Association for Computing Machinery.  ISBN 978-1-4503-4232-2.  doi: 10.1145/2939672.2939754.
  * Han et al. ((2019) Xiao Han, Qing Yang, and Yingying Fan.  Universal Rank Inference via Residual Subsampling with Application to Large Networks.  _arXiv:1912.11583 [math, stat]_ , December 2019.
  * Hoff et al. ((2002) Peter D. Hoff, Adrian E. Raftery, and Mark S. Handcock.  Latent Space Approaches to Social Network Analysis.  _Journal of the American Statistical Association_ , 97(460):1090–1098, 2002.  doi: 10.1198/016214502388618906.
  * Holland et al. ((1983) Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  _Social Networks_ , 5(2):109–137, June 1983.  ISSN 0378-8733.  doi: 10.1016/0378-8733(83)90021-7.
  * Huang et al. ((2020) Sihan Huang, Haolei Weng, and Yang Feng.  Spectral clustering via adaptive layer aggregation for multi-layer networks.  _arXiv:2012.04646 [cs, math, stat]_ , December 2020.
  * Jin ((2015) Jiashun Jin.  Fast community detection by SCORE.  _The Annals of Statistics_ , 43(1):57–89, February 2015.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/14-AOS1265.
  * Jin et al. ((2023) Jiashun Jin, Zheng Tracy Ke, and Shengming Luo.  Mixed membership estimation for social networks.  _Journal of Econometrics_ , February 2023.  ISSN 0304-4076.  doi: 10.1016/j.jeconom.2022.12.003.
  * Jing et al. ((2021) Bing-Yi Jing, Ting Li, Zhongyuan Lyu, and Dong Xia.  Community detection on mixture multilayer networks via regularized tensor decomposition.  _The Annals of Statistics_ , 49(6):3181–3205, December 2021.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/21-AOS2079.
  * Jones and Rubin-Delanchy ((2021) Andrew Jones and Patrick Rubin-Delanchy.  The multilayer random dot product graph, January 2021.  arXiv:2007.10455 [cs, stat].
  * Kadavankandy and Couillet ((2019) Arun Kadavankandy and Romain Couillet.  Asymptotic Gaussian Fluctuations of Spectral Clustering Eigenvectors.  In _2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_ , pages 694–698, December 2019.  doi: 10.1109/CAMSAP45676.2019.9022474.
  * Karrer and Newman ((2011) Brian Karrer and M. E. J. Newman.  Stochastic blockmodels and community structure in networks.  _Physical Review E_ , 83(1):016107, January 2011\.  ISSN 1539-3755, 1550-2376.  doi: 10.1103/PhysRevE.83.016107.
  * Kim et al. ((2018) Bomin Kim, Kevin H. Lee, Lingzhou Xue, and Xiaoyue Niu.  A review of dynamic network models with latent variables.  _Statistics Surveys_ , 12(none):105–135, January 2018.  ISSN 1935-7516.  doi: 10.1214/18-SS121.
  * Kloepfer et al. ((2021) Dominik Kloepfer, Angelica I. Aviles-Rivero, and Daniel Heydecker.  Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings, July 2021.  arXiv:2107.10014 [cs, math, stat].
  * Koltchinskii and Gine ((2000) Vladimir Koltchinskii and Evarist Gine.  Random matrix approximation of spectra of integral operators.  _Bernoulli_ , 6(1):113–167, February 2000.  ISSN 1350-7265.
  * Lancichinetti and Fortunato ((2009) Andrea Lancichinetti and Santo Fortunato.  Community detection algorithms: A comparative analysis.  _Physical Review E_ , 80(5):056117, November 2009\.  doi: 10.1103/PhysRevE.80.056117.
  * Lee and Wilkinson ((2019) Clement Lee and Darren J. Wilkinson.  A review of stochastic block models and extensions for graph clustering.  _Applied Network Science_ , 4(1):1–50, December 2019.  ISSN 2364-8228.  doi: 10.1007/s41109-019-0232-2.
  * Lei ((2016) Jing Lei.  A goodness-of-fit test for stochastic block models.  _The Annals of Statistics_ , 44(1):401–424, February 2016.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/15-AOS1370.
  * Lei and Lin ((2022) Jing Lei and Kevin Z. Lin.  Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models.  _Journal of the American Statistical Association_ , 0(0):1–13, March 2022.  ISSN 0162-1459.  doi: 10.1080/01621459.2022.2054817.
  * Lei and Rinaldo ((2015) Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  _Annals of Statistics_ , 43(1):215–237, February 2015.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/14-AOS1274.
  * Lei et al. ((2020a) Jing Lei, Kehui Chen, and Brian Lynch.  Consistent community detection in multi-layer network data.  _Biometrika_ , 107(1):61–73, March 2020a.  ISSN 0006-3444.  doi: 10.1093/biomet/asz068.
  * Lei ((2019) Lihua Lei.  Unified $\ell_{2\rightarrow\infty}$ Eigenspace Perturbation Theory for Symmetric Random Matrices.  _arXiv:1909.04798 [math, stat]_ , September 2019.
  * Lei et al. ((2020b) Lihua Lei, Xiaodong Li, and Xingmei Lou.  Consistency of Spectral Clustering on Hierarchical Stochastic Block Models.  _arXiv:2004.14531 [math, stat]_ , April 2020b.
  * Levin and Levina ((2019) Keith Levin and Elizaveta Levina.  Bootstrapping Networks with Latent Space Structure.  _arXiv:1907.10821 [math, stat]_ , July 2019.
  * Levin et al. ((2019) Keith Levin, Avanti Athreya, Minh Tang, Vince Lyzinski, Youngser Park, and Carey E. Priebe.  A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference.  _arXiv:1705.09355 [stat]_ , June 2019.
  * Li and Li ((2018) Yezheng Li and Hongzhe Li.  Two-sample Test of Community Memberships of Weighted Stochastic Block Models.  _arXiv:1811.12593 [math, stat]_ , November 2018.
  * Lin et al. ((2023) Christy Lin, Daniel L. Sussman, and Prakash Ishwar.  Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings.  _IEEE Transactions on Network Science and Engineering_ , 10(1):346–359, January 2023.  ISSN 2327-4697.  doi: 10.1109/TNSE.2022.3208520.
  * Lin et al. ((2020) Qiaohui Lin, Robert Lunde, and Purnamrita Sarkar.  On the Theoretical Properties of the Network Jackknife.  In _Proceedings of the 37th International Conference on Machine Learning_ , pages 6105–6115. PMLR, November 2020.  ISSN: 2640-3498.
  * Lin et al. ((2022) Qiaohui Lin, Robert Lunde, and Purnamrita Sarkar.  Trading off Accuracy for Speedup: Multiplier Bootstraps for Subgraph Counts, April 2022.  arXiv:2009.06170 [math, stat].
  * Lovász ((2012) László Lovász.  _Large Networks and Graph Limits_.  American Mathematical Soc., 2012.  ISBN 978-0-8218-9085-1.  Google-Books-ID: FsFqHLid8sAC.
  * Lu and Peng ((2013) Linyuan Lu and Xing Peng.  Spectra of Edge-Independent Random Graphs.  _The Electronic Journal of Combinatorics_ , pages P27–P27, November 2013.  ISSN 1077-8926.  doi: 10.37236/3576.
  * Lunde and Sarkar ((2019) Robert Lunde and Purnamrita Sarkar.  Subsampling Sparse Graphons Under Minimal Assumptions.  _arXiv:1907.12528 [math, stat]_ , August 2019.
  * Lyu et al. ((2023) Zhongyuan Lyu, Dong Xia, and Yuan Zhang.  Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition.  _Journal of Computational and Graphical Statistics_ , 0(0):1–17, January 2023.  ISSN 1061-8600.  doi: 10.1080/10618600.2022.2164289.
  * Ma et al. ((2020) Zhuang Ma, Zongming Ma, and Hongsong Yuan.  Universal Latent Space Model Fitting for Large Networks with Edge Covariates.  _Journal of Machine Learning Research_ , 21(4):1–67, 2020.  ISSN 1533-7928.
  * Ma and Nandy ((2023) Zongming Ma and Sagnik Nandy.  Community Detection with Contextual Multilayer Networks.  _IEEE Transactions on Information Theory_ , pages 1–1, 2023.  ISSN 1557-9654.  doi: 10.1109/TIT.2023.3238352.
  * Mao et al. ((2020) Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti.  Estimating Mixed Memberships With Sharp Eigenvector Deviations.  _Journal of the American Statistical Association_ , 0(0):1–13, April 2020.  ISSN 0162-1459.  doi: 10.1080/01621459.2020.1751645.
  * Matias and Robin ((2014) Catherine Matias and Stéphane Robin.  Modeling heterogeneity in random graphs through latent space models: a selective review.  _ESAIM: Proceedings and Surveys_ , 47:55–74, December 2014\.  ISSN 2267-3059.  doi: 10.1051/proc/201447004.
  * Mele et al. ((2022) Angelo Mele, Lingxin Hao, Joshua Cape, and Carey E. Priebe.  Spectral Estimation of Large Stochastic Blockmodels with Discrete Nodal Covariates.  _Journal of Business & Economic Statistics_, 0(0):1–13, October 2022.  ISSN 0735-0015.  doi: 10.1080/07350015.2022.2139709.
  * Modell and Rubin-Delanchy ((2021) Alexander Modell and Patrick Rubin-Delanchy.  Spectral clustering under degree heterogeneity: a case for the random walk Laplacian.  _arXiv:2105.00987 [stat]_ , May 2021.
  * Mu et al. ((2022) Cong Mu, Angelo Mele, Lingxin Hao, Joshua Cape, Avanti Athreya, and Carey E. Priebe.  On Spectral Algorithms for Community Detection in Stochastic Blockmodel Graphs With Vertex Covariates.  _IEEE Transactions on Network Science and Engineering_ , 9(5):3373–3384, September 2022.  ISSN 2327-4697.  doi: 10.1109/TNSE.2022.3177708.
  * Noroozi and Pensky ((2022a) Majid Noroozi and Marianna Pensky.  The Hierarchy of Block Models.  _Sankhya A_ , 84(1):64–107, June 2022a.  ISSN 0976-8378.  doi: 10.1007/s13171-021-00247-2.
  * Noroozi and Pensky ((2022b) Majid Noroozi and Marianna Pensky.  Sparse Subspace Clustering in Diverse Multiplex Network Model, June 2022b.  arXiv:2206.07602 [cs, stat].
  * Noroozi et al. ((2021a) Majid Noroozi, Marianna Pensky, and Ramchandra Rimal.  Sparse Popularity Adjusted Stochastic Block Model.  _Journal of Machine Learning Research_ , 22(193):1–36, 2021a.  ISSN 1533-7928.
  * Noroozi et al. ((2021b) Majid Noroozi, Ramchandra Rimal, and Marianna Pensky.  Estimation and clustering in popularity adjusted block model.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , page rssb.12410, February 2021b.  ISSN 1369-7412, 1467-9868.  doi: 10.1111/rssb.12410.
  * Pantazis et al. ((2022) Konstantinos Pantazis, Avanti Athreya, Jesus Arroyo, William N. Frost, Evan S. Hill, and Vince Lyzinski.  The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks.  _Journal of Machine Learning Research_ , 23(141):1–77, 2022.  ISSN 1533-7928.
  * Paul and Chen ((2016) Subhadeep Paul and Yuguo Chen.  Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel.  _Electronic Journal of Statistics_ , 10(2):3807–3870, January 2016.  ISSN 1935-7524, 1935-7524.  doi: 10.1214/16-EJS1211.
  * Paul and Chen ((2020) Subhadeep Paul and Yuguo Chen.  Spectral and matrix factorization methods for consistent community detection in multi-layer networks.  _The Annals of Statistics_ , 48(1):230–250, February 2020.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/18-AOS1800.
  * Pensky ((2019) Marianna Pensky.  Dynamic Network Models and Graphon Estimation.  _The Annals of Statistics_ , 47(4):2378–2403, 2019.  ISSN 0090-5364.
  * Pensky and Wang ((2023) Marianna Pensky and Yaxuan Wang.  Clustering of Diverse Multiplex Networks, March 2023.  arXiv:2110.05308 [stat].
  * Pensky and Zhang ((2019) Marianna Pensky and Teng Zhang.  Spectral clustering in the dynamic stochastic block model.  _Electronic Journal of Statistics_ , 13(1):678–709, January 2019.  ISSN 1935-7524, 1935-7524.  doi: 10.1214/19-EJS1533.
  * Priebe et al. ((2019) Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Minh Tang, Avanti Athreya, Joshua Cape, and Eric Bridgeford.  On a two-truths phenomenon in spectral graph clustering.  _Proceedings of the National Academy of Sciences_ , 116(13):5995–6000, March 2019.  doi: 10.1073/pnas.1814462116.
  * Qin and Rohe ((2013) Tai Qin and Karl Rohe.  Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel.  In _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.
  * Razaee et al. ((2019) Zahra S. Razaee, Arash A. Amini, and Jingyi Jessica Li.  Matched Bipartite Block Model with Covariates.  _Journal of Machine Learning Research_ , 20(34):1–44, 2019.  ISSN 1533-7928.
  * Rohe and Zeng ((2020) Karl Rohe and Muzhe Zeng.  Vintage Factor Analysis with Varimax Performs Statistical Inference.  _Journal of the Royal Statistical Society Series B, to appear_ , April 2020.
  * Rohe et al. ((2011) Karl Rohe, Sourav Chatterjee, and Bin Yu.  Spectral clustering and the high-dimensional stochastic blockmodel.  _The Annals of Statistics_ , 39(4):1878–1915, August 2011.  ISSN 0090-5364.  doi: 10.1214/11-AOS887.
  * Rubin-Delanchy et al. ((2022) Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey E. Priebe.  A statistical interpretation of spectral embedding: The generalised random dot product graph.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , n/a(n/a), 2022.  ISSN 1467-9868.  doi: 10.1111/rssb.12509.
  * Schaeffer ((2007) Satu Elisa Schaeffer.  Graph clustering.  _Computer Science Review_ , 1(1):27–64, August 2007.  ISSN 1574-0137.  doi: 10.1016/j.cosrev.2007.05.001.
  * Sengupta and Chen ((2018) Srijan Sengupta and Yuguo Chen.  A block model for node popularity in networks with community structure.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(2):365–386, 2018.  ISSN 1467-9868.  doi: 10.1111/rssb.12245.
  * Tang and Priebe ((2018) Minh Tang and Carey E. Priebe.  Limit theorems for eigenvectors of the normalized Laplacian for random graphs.  _The Annals of Statistics_ , 46(5):2360–2415, October 2018.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/17-AOS1623.
  * Tang et al. ((2017a) Minh Tang, Avanti Athreya, Daniel L. Sussman, Vince Lyzinski, Youngser Park, and Carey E. Priebe.  A Semiparametric Two-Sample Hypothesis Testing Problem for Random Graphs.  _Journal of Computational and Graphical Statistics_ , 26(2):344–354, April 2017a.  ISSN 1061-8600.  doi: 10.1080/10618600.2016.1193505.
  * Tang et al. ((2017b) Minh Tang, Avanti Athreya, Daniel L. Sussman, Vince Lyzinski, and Carey E. Priebe.  A nonparametric two-sample hypothesis testing problem for random graphs.  _Bernoulli_ , 23(3):1599–1630, August 2017b.  ISSN 1350-7265.  doi: 10.3150/15-BEJ789.
  * Tang et al. ((2022) Minh Tang, Joshua Cape, and Carey E. Priebe.  Asymptotically efficient estimators for stochastic blockmodels: The naive MLE, the rank-constrained MLE, and the spectral estimator.  _Bernoulli_ , 28(2):1049–1073, May 2022.  ISSN 1350-7265.  doi: 10.3150/21-BEJ1376.
  * von Luxburg ((2007) Ulrike von Luxburg.  A tutorial on spectral clustering.  _Statistics and Computing_ , 17(4):395–416, December 2007.  ISSN 1573-1375.  doi: 10.1007/s11222-007-9033-z.
  * Wasserman and Faust ((1994) Stanley Wasserman and Katherine Faust.  _Social Network Analysis: Methods and Applications_.  Cambridge University Press, November 1994.  ISBN 978-0-521-38707-1.  Google-Books-ID: CAm2DpIqRUIC.
  * Xie ((2021) Fangzheng Xie.  Euclidean Representation of Low-Rank Matrices and Its Statistical Applications.  _arXiv:2103.04220 [math, stat]_ , March 2021.
  * Xie ((2022) Fangzheng Xie.  Entrywise limit theorems of eigenvectors for signal-plus-noise matrix models with weak signals.  _Bernoulli, to appear_ , March 2022.  doi: 10.48550/arXiv.2106.09840.
  * Xie and Xu ((2021) Fangzheng Xie and Yanxun Xu.  Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure.  _Journal of the American Statistical Association_ , 0(0):1–14, July 2021.  ISSN 0162-1459.  doi: 10.1080/01621459.2021.1948419.
  * Xu et al. ((2022) Shirong Xu, Yaoming Zhen, and Junhui Wang.  Covariate-Assisted Community Detection in Multi-Layer Networks.  _Journal of Business & Economic Statistics_, 0(0):1–12, June 2022.  ISSN 0735-0015.  doi: 10.1080/07350015.2022.2085726.
  * Yan et al. ((2021) Yuling Yan, Yuxin Chen, and Jianqing Fan.  Inference for Heteroskedastic PCA with Missing Data, July 2021\.  Number: arXiv:2107.12365 arXiv:2107.12365 [cs, math, stat].
  * Yang et al. ((2021) Congyuan Yang, Carey E. Priebe, Youngser Park, and David J. Marchette.  Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering.  _Journal of Computational and Graphical Statistics_ , 30(2):422–441, April 2021.  ISSN 1061-8600.  doi: 10.1080/10618600.2020.1824870.
  * Zhang et al. ((2022) Hai Zhang, Xiao Guo, and Xiangyu Chang.  Randomized Spectral Clustering in Large-Scale Stochastic Block Models.  _Journal of Computational and Graphical Statistics_ , 0(0):1–20, January 2022.  ISSN 1061-8600.  doi: 10.1080/10618600.2022.2034636.
  * Zhang and Tang ((2022a) Yichi Zhang and Minh Tang.  Exact Recovery of Community Structures Using DeepWalk and Node2vec, October 2022a.  arXiv:2101.07354 [cs, stat].
  * Zhang and Tang ((2022b) Yichi Zhang and Minh Tang.  Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics, March 2022b.  Number: arXiv:2203.10262 arXiv:2203.10262 [cs, math, stat].
  * Zhang and Xia ((2022) Yuan Zhang and Dong Xia.  Edgeworth expansions for network moments.  _The Annals of Statistics_ , 50(2):726–753, April 2022.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/21-AOS2125.
  * Zhang et al. ((2020) Yuan Zhang, Elizaveta Levina, and Ji Zhu.  Detecting Overlapping Communities in Networks Using Spectral Methods.  _SIAM Journal on Mathematics of Data Science_ , 2(2):265–283, January 2020.  doi: 10.1137/19M1272238.
  * Zhang et al. ((2019) Yun Zhang, Kehui Chen, Allan Sampson, Kai Hwang, and Beatriz Luna.  Node Features Adjusted Stochastic Block Model.  _Journal of Computational and Graphical Statistics_ , 28(2):362–373, April 2019.  ISSN 1061-8600.  doi: 10.1080/10618600.2018.1530117.
  * Zhao ((2017) Yunpeng Zhao.  A survey on theoretical advances of community detection in networks.  _WIREs Computational Statistics_ , 9(5):e1403, 2017.  ISSN 1939-0068.  doi: https://doi.org/10.1002/wics.1403.
  * Zheng and Tang ((2022) Runbing Zheng and Minh Tang.  Limit results for distributed estimation of invariant subspaces in multiple networks inference and PCA, June 2022.  Number: arXiv:2206.04306 arXiv:2206.04306 [math, stat].
  * Zhu and Ghodsi ((2006) Mu Zhu and Ali Ghodsi.  Automatic dimensionality selection from the scree plot via the use of profile likelihood.  _Computational Statistics & Data Analysis_, 51(2):918–930, November 2006.  ISSN 0167-9473.  doi: 10.1016/j.csda.2005.09.010.