# Contextual Stochastic Block Model: Sharp Thresholds and Contiguity

Chen Lu Department of Mathematics, Massachusetts Institute of Technology,
Cambridge MA 02139, U.S.A. Subhabrata Sen Department of Statistics, Harvard
University, Cambridge, MA 02138, U.S.A.

###### Abstract

We study community detection in the _contextual stochastic block model_ [48,
16]. In [16], the second author studied this problem in the setting of sparse
graphs with high-dimensional node-covariates. Using the non-rigorous _cavity
method_ from statistical physics [33], they conjectured the sharp limits for
community detection in this setting. Further, the information theoretic
threshold was verified, assuming that the average degree of the observed graph
is large. It is expected that the conjecture holds as soon as the average
degree exceeds one, so that the graph has a giant component. We establish this
conjecture, and characterize the sharp threshold for detection and weak
recovery.

##  1 Introduction

The community detection problem arises routinely in diverse applications, and
has received significant attention recently in statistics and machine
learning. In the simplest version of this problem, given access to a graph,
one seeks to cluster the vertices into interpretable _communities_ or groups
of vertices, which are believed to reflect latent similarities among the
nodes. From a theoretical standpoint, this problem has been extensively
analyzed under specific generative assumptions on the observed graph; the most
popular generative model in this context is the _stochastic block model_ (SBM)
[22]. Inspired by intriguing conjectures arising from the statistical physics
community [29], community detection under the stochastic block model has been
studied extensively. As a consequence, the precise information theoretic
limits for recovering the underlying communities have been derived, and
optimal algorithms have been identified in this setting (for a survey of these
recent breakthroughs, see [1]).

In reality, the practitioner often has access to additional information in the
form of node covariates, which complements the graph information.
Statistically, it is natural to believe that clustering performance can be
significantly improved by combining this covariate information with the graph
structure. However, establishing this improvement in a formal context, and
deriving procedures which combine the two are not straightforward. In [48],
the authors formalize this question, and introduce a simple model for
community detection with node covariates. We use the same framework in this
paper.

We observe a graph $G=(V,E)$ on $n$ vertices drawn from the sparse Stochastic
Block Model $G(n,\frac{a}{n},\frac{b}{n})$. Formally, we sample a community
assignment vector $\sigma\in\\{\pm 1\\}^{n}$ uniformly; given $\sigma$, we
draw edges with probability

$\displaystyle\mathbb{P}[\\{i,j\\}\in
E]=\begin{cases}\frac{a}{n}\quad\textrm{if}\,\,\,\,\sigma_{i}=\sigma_{j},\\\
\frac{b}{n}\quad\textrm{o.w.}\end{cases}$

Let $\mathbf{A}=(A_{ij})\in\mathbb{R}^{n\times n}$ denote the adjacency matrix
of the graph $G$. We define the average degree parameter $d=\frac{a+b}{2}$ and
parametrize $a=d+\lambda\sqrt{d}$ and $b=d-\lambda\sqrt{d}$.

Further, at each node of the graph $G$, we observe a $p$-dimensional vector of
covariates $\\{B_{i}:1\leq i\leq n\\}$. The covariates are also correlated
with the underlying community assignment. Specifically, we observe

$\displaystyle B_{i}=\sqrt{\frac{\mu}{n}}\sigma_{i}u+Z_{i},$

where $u\sim\mathcal{N}(0,I_{p})$ is a latent gaussian vector, and
$Z_{i}\sim\mathcal{N}(0,I_{p})$. We construct the matrix
$\mathbf{B}=[B_{1},\cdots,B_{n}]^{\top}\in\mathbb{R}^{n\times p}$. In [48],
the authors introduce a semidefinite programming (SDP) based algorithm for
community detection in the above setting, which combines the graph with the
node covariates. However, their results do not identify the information
theoretic limits of community detection in this context, and do not identify
the optimal community detection algorithm in this setting.

Note that when one has access to either the graph information or the covariate
information, the information theoretic threshold is well known. Under the
parametrization of the SBM, where only $\mathbf{A}$ is given, detection of the
underlying community structure, as well as non-trivial recovery, are possible
if and only if $\lambda>1$. On the other hand, the case when only the
covariate information $\mathbf{B}$ corresponds to a Gaussian mixture
clustering problem. Under a high-dimensional asymptotic regime
$\frac{n}{p}\to\gamma\in(0,\infty)$, random matrix considerations based on the
BBP phase transition [5], and contiguity arguments based on the second moment
method [41] imply that non-trivial detection and recovery are possible if and
only if $\mu^{2}>\gamma$.

In [16], the second author and coauthors studied detection and recovery under
this model in a high-dimensional asymptotic regime
$\frac{n}{p}\to\gamma\in(0,\infty)$ [16], and conjectured the sharp
information theoretic limits in this problem: the underlying community
structure can be detected if and only if
$\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$. In particular, this suggests that upon
combining the graph information appropriately with the covariates, it is
statistically possible to improve upon the optimal performance based on any
single information source. The conjecture was derived using the non-rigorous
_cavity method_ from statistical physics [33], and rigorously established
under an additional high-degree asymptotic $d\to\infty$ (after $n\to\infty$).
However, numerical experiments in [16] suggest that this high-degree
asymptotic is unnecessary, and that the results are true as soon as $d>1$. In
this paper, we formally establish this conjecture. Throughout this article, we
will work under the same high-dimensional asymptotic
$\frac{n}{p}\to\gamma\in(0,\infty)$.

Our main contributions in this article are as follows.

  * (i)

We first examine the detection problem (1), and establish the sharp threshold
for mutual contiguity (see Theorem 1). The testing lower bound is derived
using a traditional second moment argument. The upper bound is significantly
more challenging—we devise a test statistic by counting certain appropriate
self-avoiding walks in the graph.

  * (ii)

Next, we turn to weak recovery, and establish that the threshold for weak
recovery coincides with that for detection in this context. To establish the
positive half of this result, we crucially utilize the self-avoiding walk
based estimation idea introduced in [32, 23]; however, the presence of the
graph data with the covariates makes this application significantly more
challenging. We devise estimates for the pairwise correlations of the
memberships by counting appropriate walk based statistics, and then perform
weak recovery by a subsequent projection and rounding step (we refer to
Section 5 for further details). This is one of the main technical
contributions of this article.

  * (iii)

We then turn to the contiguity regime, and derive a precise expansion of the
likelihood ratio in the contiguity regime in terms of appropriate cycle
statistics. In turn, this identifies the precise statistics which distinguish
the null from the alternative.

###  1.1 Main Results

Consider the hypothesis testing problem

$\displaystyle\mathrm{H}_{0}:(\lambda,\mu)=(0,0)\quad\textrm{vs.}\quad\mathrm{H}_{1}:(\lambda,\mu)\neq(0,0).$
(1)

We will denote the joint distributions of the data $(\mathbf{A},\mathbf{B})$
by $\mathbb{P}_{\lambda,\mu}$, and keep the dependence on $n,p$ implicit
throughout. Further, we will assume that we are above the threshold for
emergence of the giant component, i.e. $d>1$ [10, 25].

######  Theorem 1 (Detection).

If $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$, $\mathbb{P}_{\lambda,\mu}$ is
contiguous to $\mathbb{P}_{0,0}$. On the other hand, if
$\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$, the sequences $\mathbb{P}_{0,0}$ and
$\mathbb{P}_{\lambda,\mu}$ are mutually asymptotically singular.

Our next result addresses the threshold for weak recovery. We recall the
relevant notion of weak recovery in this context.

######  Definition 1 (Weak Recovery).

An estimator $\hat{\sigma}:=\hat{\sigma}(\mathbf{A},\mathbf{B})\in[-1,1]^{n}$
achieves weak recovery if there exists $\varepsilon>0$, independent of $n$,
such that

$\displaystyle\frac{1}{n}\mathbb{E}_{\lambda,\mu}[|\langle\sigma,\hat{\sigma}\rangle|]\geq\varepsilon$

as $n\to\infty$. We say that weak recovery is possible if there exists an
estimator $\hat{\sigma}$ which achieves weak recovery.

######  Theorem 2 (Weak Recovery).

If $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$, then weak recovery is impossible.
On the other hand, weak recovery is possible when
$\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$.

Finally, we turn to the contiguity phase
$\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$, and derive an expansion for the
likelihood ratio. We denote the likelihood ratio by

$\displaystyle
L_{n}=\frac{\mathrm{d}\mathbb{P}_{\lambda,\mu}}{\mathrm{d}\mathbb{P}_{0,0}}.$

In this regime, $\mathbb{P}_{\lambda,\mu}$ and $\mathbb{P}_{0,0}$ cannot be
distinguished with asymptotically negligible Type I and Type II errors.
Statistically, the natural problem of interest concerns optimal detection,
which is achieved by the likelihood ratio test (LRT). We will derive
asymptotic expansions of the likelihood ratio under the null and the
alternative. As a consequence, we will obtain the optimal power of the LRT.
Along the way, we will obtain a family of statistics which “determine" the
likelihood ratio. This will suggest computationally feasible statistics which
attain optimal detection performance in this contiguous regime. Similar
expansions for the likelihood ratio have been derived for _pure_ spiked
gaussian problems (the model $B$ and its symmetric analogue) in the recent
literature [8, 3, 17, 26, 39, 40]. Our approach in this regard will be
motivated by the techniques introduced in [8]. However, we note that in
contrast to this literature, we have _both_ a sparse random graph component,
and a gaussian model. This necessitates crucial technical modifications—we
emphasize the main differences in Section 3.

To this end, let us first introduce a class of cycle statistics. We will
denote $\omega$ as a cycle on the factor graph corresponding to the posterior
distribution [33], shown in Figure 1. Specifically, the factor graph is
denoted as $G_{\mathsf{F}}=(V_{\mathsf{F}},E_{\mathsf{F}})$. The vertices are
split into two groups $V_{\mathsf{F}}=V_{1}\cup V_{2}$, where $V_{1}$ denotes
vertices from the adjacency matrix $\mathbf{A}$, with $|V_{1}|=n$, and $V_{2}$
denotes vertices from the covariate matrix $\mathbf{B}$, so $|V_{2}|=p$. In
Figure 1, vertices in $V_{1}$ are shown by dots, and those in $V_{2}$ are
shown by squares. The edges also split into two groups
$E_{\mathsf{F}}=E_{1}\cup E_{2}$, where
$E_{1}=\\{\\{i_{1},i_{2}\\}:i_{1},i_{2}\in V_{1}\\}$, and
$E_{2}=\\{\\{i,j\\}:i\in V_{1},j\in V_{2}\\}$. We will refer to edges in
$E_{1}$ as $A$ edges, and edges in $E_{2}$ as $B$ edges. Because $B$ edges
must appear in consecutive pairs in a cycle, we refer to such pairs of $B$
edges as $B$ wedges. The graph of a cycle $\omega$ is denoted as
$G_{\omega}=(V_{\omega},E_{\omega})$. We use $k$ to denote the length of the
cycle, and $l$ to denote the number of $B$ wedges in the cycle. For a cycle
$\omega$, we denote $G_{\omega,A}=(V_{\omega,A},E_{\omega,A})$ the subgraph of
the $A$ edges, and $G_{\omega,B}=(V_{\omega,B},E_{\omega,B})$ is the subgraph
of $B$ edges.

Figure 1: The factor model corresponding to the posterior distribution. The
dots represent the nodes in the adjacency graph $\mathbf{A}$, while the
squares represent the variables corresponding to the Gaussian covariates
$\mathbf{B}$. An $A$ edge is highlighted in red, while a $B$-wedge is
indicated in blue.

######  Definition 2 (Cycles).

For $k\geq l$, we define

$\displaystyle Y_{n,k,l}=\frac{1}{n^{l}}\sum_{\omega}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}B_{e_{2}}$

where the sum is over length $k$ paths with $l$ $B$-wedges, and the product is
over the components of each path.

Our first result establishes the limiting distribution of these cycle
statistics under the null and alternative. To this end, it will be convenient
to introduce some notation for the relevant index set in this problem. Let us
define $\mathcal{J}\subset\mathbb{Z}\times\mathbb{Z}$ such that

$\displaystyle\mathcal{J}=\\{(k,0):k\geq 3\\}\cup\\{(k,l):k\geq l\geq 1\\}.$

######  Proposition 1.

The collection

$\displaystyle\\{Y_{n,k,l}:(k,l)\in\mathcal{J}\\}$

converges in distribution under both $\mathrm{H}_{0}$ and $\mathrm{H_{1}}$.
Further, the limiting random variables are independent under both
$\mathrm{H}_{0}$ and $\mathrm{H}_{1}$. Finally,

  * (i)

Under $\mathrm{H}_{0}$, $1\leq l\leq k$,

$\displaystyle Y_{n,k,0}\stackrel{{\scriptstyle
d}}{{\rightarrow}}\mathrm{Poi}\Big{(}\frac{1}{k}d^{k}\Big{)},\,\,\,\frac{Y_{n,k,l}-p\mathbf{1}_{k=l=1}}{\sqrt{\frac{1}{2k}\binom{k}{l}\frac{d^{k-l}}{\gamma^{l}}}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}\mathcal{N}(0,1).$

  * (ii)

Under $H_{1}$, for any $1\leq l\leq k$,

$\displaystyle Y_{n,k,0}\stackrel{{\scriptstyle
d}}{{\rightarrow}}\mathrm{Poi}\Big{(}\frac{1}{k}(d^{k}+(\lambda\sqrt{d})^{k})\Big{)},\,\,\,\,\,\frac{Y_{n,k,l}-p\mathbf{1}_{k=l=1}-\frac{1}{2k}\binom{k}{l}\frac{(\lambda\sqrt{d})^{k-l}\mu^{l}}{\gamma^{l}}}{\sqrt{\frac{1}{2k}\binom{k}{l}\frac{d^{k-l}}{\gamma^{l}}}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}\mathcal{N}(0,1).$

Finally, if $l\geq 1$, the distributional limits continue to hold for
$k_{n},l_{n}$ growing in $n$, as long as $l_{n}\leq k_{n}=o(\sqrt{\log n})$.

Let $\\{\upsilon_{k,l,j}:j\in\\{0,1\\},(k,l)\in\mathcal{J}\\}$ be collection
of random variables with the desired limiting distributions. Specifically,
$\upsilon_{k,0,0}\sim\mathrm{Poi}\Big{(}\frac{1}{k}d^{k}\Big{)}$ and for
$l\geq 1$, $\upsilon_{k,l,0}\sim\mathcal{N}(\mu_{k,l,0},\sigma_{k,l}^{2})$.
Similarly,
$\upsilon_{k,0,1}\sim\mathrm{Poi}\Big{(}\frac{1}{k}(d^{k}+(\lambda\sqrt{d})^{k})\Big{)}$,
and for $l\geq 1$,
$\upsilon_{k,l,1}\sim\mathcal{N}(\mu_{k,l,1},\sigma_{k,l}^{2})$. Here, the
means and variances $\mu_{k,l,0}$ and $\sigma^{2}_{k,l}$ are as specified in
Proposition 1 under the null, while $\mu_{k,l,1}$ denotes the mean under the
alternative.

######  Theorem 3.

Consider $(\lambda,\mu)$ satisfying $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$.
Then the following hold:

  1. 1.

$\mathbb{P}_{\lambda,\mu}$ and $\mathbb{P}_{0,0}$ are asymptotically mutually
contiguous.

  2. 2.

Under $H_{0}$, we have that

$\displaystyle
L_{n}\overset{d}{\rightarrow}\exp\Big{(}\sum_{k=1}^{\infty}\Big{[}\log(1-\lambda^{k}d^{k/2})\upsilon_{k,0,0}-\frac{1}{k}(\lambda\sqrt{d})^{k}+\sum_{1\leq
l\leq
k}\frac{\mu_{k,l,0}\upsilon_{k,l,0}-\frac{1}{2}\mu_{k,l,0}^{2}}{\sigma_{k,l}^{2}}\Big{]}\Big{)}.$

###  1.2 Related Literature

Covariate assisted clustering has been extensively studied across statistics,
machine learning and computer science using diverse perspectives. The
literature on this topic is quite diffuse, and its impossible to provide an
exhaustive survey of this area. However, for the convenience of the reader, we
survey the main methodological approaches, and discuss in-depth the main
results relevant for our work.

From a methodological standpoint, generative model based approaches are very
natural for this problem, and they have been extensively explored in this
setting [38, 21, 51, 50, 28, 31, 47, 20, 49]. On the other hand, model free
approaches, which cluster the nodes by optimizing a suitable loss function
have also been popular [9, 52, 18, 53, 37, 19, 15, 14, 44, 45]. Bayesian
methods [13, 6] provide another natural methodological approach for this
problem. We refer the interested reader to [12] for a survey of other
approaches.

In a separate direction [2, 30] study a version of community detection with
informative edges. [30] establishes only one side of the conjectured
information theoretic threshold in this setting.

More recently, [9, 52] analyze specific heuristic clustering algorithms under
the block model formalism. However, consistency guarantees in this setting are
derived for dense graphs, and under strong separability assumptions on the
connection probabilities. Further, they do not identify the precise
information theoretic thresholds for recovery. As a consequence, the precise
information theoretic gains obtained from the additional covariates remains
unclear.

Our work is closest in spirit to [48]. They study an SDP based framework for
community recovery. However, in contrast to our setting, they study low-
dimensional covariates. They formally establish that clustering accuracy is
improved upon combining the node information with the graph. In contrast, we
study high-dimensional covariates, and establish that the information
theoretic threshold is shifted in this setting.

Somewhat related to our inquiry, [27, 36] study local algorithms for
semisupervised clustering, i.e. when the true labels are given for a small
fraction of nodes. While these algorithms are local, our analysis is global,
and we capture the information theoretic limits in this problem.

###  1.3 Technical Contributions

The main contributions of this paper are the algorithm for weak recovery above
the threshold $\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$, and the asymptotic
distribution of the cycle statistics in Proposition 1. Contiguity below the
threshold follows from standard second moment arguments, and expansions of the
likelihood ratio in the contiguity phase are based on a version of Janson’s
small-subgraph conditioning method. The small-subgraph conditioning argument
follows the same template as [8], once the distribution of the cycle
statistics Proposition 1 is given. In this section, we elaborate on our main
technical contributions.

In prior work on community detection (see e.g. [35, 8, 23, 32]), weak recovery
has often been performed using statistics based on appropriate self-avoiding
walks. In particular, the wide-applicability of this idea was emphasized in
[23]. The general meta-algorithm introduced in [23] has the following steps:
(i) estimate the second moment $\sigma\sigma^{\mathrm{T}}$ using self-avoiding
walk statistics, and (ii) use a generic projection and rounding procedure to
derive the membership estimator. We follow the same strategy— the main
technical challenge is to construct the appropriate estimator for the second
moment. One might naturally suspect that an appropriate self-avoiding walk
based statistic might be relevant in our setting. However, we have two data
sources, encoded by the graph adjacency matrix and the matrix of gaussian
covariates. As a consequence, the relevant cycle statistics are not obvious in
this setting. A first idea is to consider the factor graph for this problem
(see Figure 1), and use self-avoiding walks of a fixed length. However, some
thought reveals that this is sub-optimal; to see this, consider a setting
where $\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$, but $\lambda^{2}<1$. In this
case, the block model alone does not contain any information regarding the
underlying community assignment, so the walks based purely on the sparse graph
will only contain noise.

Instead, we construct paths with edges from both the adjacency and covariate
matrices, whose ratio of edges is given by
$\lambda^{2}:\frac{\mu^{2}}{\gamma}$. Conceptually, each path is constructed
so that the contributions from the adjacency and covariate matrices reflect
the amount of information from each source respectively. This approach can be
potentially useful for other reconstruction problems which have multiple
information sources.

On the other hand, the distribution of the likelihood ratio in the contiguity
regime $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$ is determined by all cycles of
finite length. For cycles with edges coming solely from the adjacency or
covariance matrix, the distribution limits are Poisson [35] and Gaussian [8]
respectively. In our setting, we also encounter mixed-cycles, comprising edges
coming from both sources. Using a method of moments approach, we establish
that the limiting distribution of these mixed cycles are all independent
Gaussian random variables in the limit. Finally, we characterize the means and
variances of these cycles under the null and alternative. We expect the
general techniques to be useful in other settings as well.

Organization: The rest of the paper is structured as follows. We establish
Theorem 1 in Section 2. In Section 3 we establish the asymptotic expansion of
the likelihood ratio in the contiguity regime, and establish Theorem 3. We
establish Theorem 2 in Sections 4 and 5.

Acknowledgments: SS thanks Yash Deshpande, Andrea Montanari and Elchanan
Mossel for helpful conversations.

##  2 Detection

  * Proof of Theorem 1:

We start with a proof of the information theoretic lower bound. Fix
$\lambda,\mu$ such that $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$. We will use
the traditional second moment approach. First, consider a complete data
problem, where one observes the latent vectors $\sigma\in\\{\pm 1\\}^{n}$ and
$u\in\mathbb{R}^{p}$. We denote the corresponding distribution as
$\tilde{\mathbb{P}}_{\lambda,\mu}$. Thus we have,

$\displaystyle
L:=\frac{\mathrm{d}\mathbb{P}_{\lambda,\mu}}{\mathrm{d}\mathbb{P}_{0,0}}(\mathbf{A},\mathbf{B})=\frac{\mathbb{E}_{\sigma,u}\Big{[}\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\sigma,u)\Big{]}}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})},$

where $\mathbb{E}_{\sigma,u}[\cdot]$ calculates the expectation with respect
to the priors on $\sigma$ and $u$. Consider the event
$\mathcal{S}=\\{u:\|u\|_{2}\leq(1+\delta)\sqrt{p}\\}$, where $\delta>0$ will
be chosen appropriately. Define the truncated likelihood

$\displaystyle\tilde{L}=\frac{\mathbb{E}_{\sigma,u}\Big{[}\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\sigma,u)\mathbf{1}(u\in\mathcal{S})\Big{]}}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})}.$

Finally, we claim that if $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$, then there
exists a universal constant $C>0$ such that
$\mathbb{E}_{0,0}[\tilde{L}^{2}]\leq C<\infty$.. This establishes the desired
contiguity property. Indeed, let $\\{\mathcal{A}_{n}:n\geq 1\\}$ be any
sequence of events with $\mathbb{P}_{0,0}(\mathcal{A}_{n})\to 0$ as
$n\to\infty$. We have,

$\displaystyle\mathbb{P}_{\lambda,\mu}(\mathcal{A}_{n})=\mathbb{E}_{0,0}\Big{[}L\mathbf{1}_{\mathcal{A}_{n}}\Big{]}=\mathbb{E}_{0,0}[\tilde{L}\mathbf{1}_{\mathcal{A}_{n}}]+\mathbb{E}_{0,0}[(L-\tilde{L})\mathbf{1}_{\mathcal{A}_{n}}].$

Note that

$\displaystyle\mathbb{E}_{0,0}[(L-\tilde{L})\mathbf{1}_{\mathcal{A}_{n}}]\leq\mathbb{E}_{0,0}[(L-\tilde{L})]\leq\mathbb{P}_{\sigma,u}(u\notin\mathcal{S})\to
0$

as $n\to\infty$. Given this claim, by Cauchy-Schwarz inequality, we have,

$\displaystyle\mathbb{P}_{\lambda,\mu}(\mathcal{A}_{n})\leq\sqrt{\mathbb{E}_{0,0}[\tilde{L}^{2}]\,\mathbb{P}_{0,0}(\mathcal{A}_{n})}+o(1)\to
0$

as $n\to\infty$.

It remains to establish that $\mathbb{E}_{0,0}[\tilde{L}^{2}]\leq C<\infty$
for some universal $C>0$. To this end, by Fubini’s theorem, we note that

$\displaystyle\mathbb{E}_{0,0}[\tilde{L}^{2}]=\mathbb{E}_{(\sigma,u),(\tau,v)}\Big{[}\mathbb{E}_{0,0}\Big{[}\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\sigma,u)}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})}\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\tau,v)}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})}\mathbf{1}(u,v\in\mathcal{S})\Big{]}\Big{]}.$
(2)

Now, we have,

$\displaystyle\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\sigma,u)}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})}=\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A}|\sigma)}{\mathbb{P}_{0,0}(\mathbf{A})}\cdot\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{B}|\sigma,u)}{\mathbb{P}_{0,0}(\mathbf{B})}.$

We evaluate each term in turn. First, we have,

$\displaystyle\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A}|\sigma)}{\mathbb{P}_{0,0}(\mathbf{A})}=\prod_{i<j}W_{ij},W_{ij}=W_{ij}(\mathbf{A},\sigma)=\begin{cases}\frac{2a}{a+b}&\text{
if }\sigma_{i}=\sigma_{j},\ \ A_{ij}=1\\\ \frac{2b}{a+b}&\text{ if
}\sigma_{i}\not=\sigma_{j},\ \ A_{ij}=1\\\ \frac{n-a}{n-(a+b)/2}&\text{ if
}\sigma_{i}=\sigma_{j},\ \ A_{ij}=0\\\ \frac{n-b}{n-(a+b)/2}&\text{ if
}\sigma_{i}\not=\sigma_{j},\ \ A_{ij}=0\end{cases}$

Second, direct computation yields

$\displaystyle\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{B}|\sigma,u)}{\mathbb{P}_{0,0}(\mathbf{B})}$
$\displaystyle=\exp\Big{(}\sqrt{\frac{\mu}{n}}\sum_{i=1}^{n}\sigma_{i}Z_{i}^{\top}u-\frac{\mu}{2}\lVert
u\rVert^{2}\Big{)}.$

Therefore,

$\displaystyle\mathbb{E}_{(\sigma,u),(\tau,v)}\Big{[}\mathbb{E}_{0,0}\Big{[}\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\sigma,u)}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})}\frac{\tilde{\mathbb{P}}_{\lambda,\mu}(\mathbf{A},\mathbf{B}|\tau,v)}{\mathbb{P}_{0,0}(\mathbf{A},\mathbf{B})}\mathbf{1}(u,v\in\mathcal{S})\Big{]}\Big{]}$
$\displaystyle=\mathbb{E}_{(\sigma,u),(\tau,v)}\Big{[}\mathbf{1}(u,v\in\mathcal{S})\mathbb{E}_{0,0}\Big{[}\prod_{i<j}W_{ij}V_{ij}\exp\Big{(}\sqrt{\frac{\mu}{n}}\sum_{i=1}^{n}Z_{i}^{\top}(\sigma_{i}u+\tau_{i}v)-\frac{\mu}{2}(\lVert
u\rVert^{2}+\lVert v\rVert^{2})\Big{)}\Big{]}\Big{]},$

where $V_{ij}=V_{ij}(\mathbf{A},\tau)$ is defined similarly to $W_{ij}$. Under
$\mathbb{P}_{0,0}$, for any $(\sigma,u)$ and $(\tau,v)$, $\mathbf{A}$ and
$\mathbf{B}$ are independent. Setting
$\rho=\rho(\sigma,\tau)=\frac{1}{n}\langle\sigma,\tau\rangle$, we have,

$\displaystyle\mathbb{E}_{0,0}\Big{[}\exp\Big{(}\sqrt{\frac{\mu}{n}}\sum_{i=1}^{n}Z_{i}^{\top}(\sigma_{i}u+\tau_{i}v)-\frac{\mu}{2}(\lVert
u\rVert^{2}+\lVert v\rVert^{2})\Big{)}\Big{]}=\exp\Big{(}\frac{\mu}{n}\langle
u,v\rangle\langle\sigma,\tau\rangle\Big{)}.$

Using [35, Lemma 5.4], we have,

$\displaystyle\mathbb{E}_{0,0}\Big{[}\prod_{i<j}W_{ij}V_{ij}\Big{]}=(1+o(1))e^{-\lambda^{2}/2-\lambda^{4}/4}\exp\Big{(}\frac{\rho^{2}\lambda^{2}}{2}(d+n)\Big{)}.$

Plugging these back into (2), we obtain,

$\displaystyle\mathbb{E}_{0,0}[\tilde{L}^{2}]$
$\displaystyle\leq(1+o(1))e^{-\lambda^{2}/2-\lambda^{4}/4+\lambda^{2}d/2}\mathbb{E}_{(\sigma,u),(\tau,v)}\Big{[}\exp\Big{(}n\Big{(}\frac{\rho^{2}\lambda^{2}}{2}+\frac{\mu}{\gamma}\rho\frac{\langle
u,v\rangle}{p}\Big{)}\Big{)}\mathbf{1}(u,v\in\mathcal{S})\Big{)}\Big{]}.,$

We note that $\langle
u,v\rangle=\|u\|\|v\|\langle\frac{u}{\|u\|},\frac{v}{\|v\|}\rangle$,
$\|u\|,\|v\|\leq(1+\delta)\sqrt{p}$ on the event $\mathcal{S}$, and
$\langle\frac{u}{\|u\|},\frac{v}{\|v\|}\rangle\stackrel{{\scriptstyle
d}}{{=}}Y$, where $Y$ is the first coordinate of a uniform vector on the unit
sphere. Thus we have,

$\displaystyle\mathbb{E}_{0,0}[\tilde{L}^{2}]\leq(1+o(1))e^{-\lambda^{2}/2-\lambda^{4}/4+\lambda^{2}d/2}\mathbb{E}\Big{[}\exp\Big{(}n\Big{(}\frac{\lambda^{2}}{2}X^{2}+(1+\delta)^{2}\frac{\mu}{\gamma}XY\Big{)}\Big{)}\Big{]},$

where $X\stackrel{{\scriptstyle d}}{{=}}\rho(\sigma,\tau)$ and $Y$ is as
described above. It is easy to see that $Y\in[-1,1]$ has density

$\displaystyle
f_{Y}(y)=\frac{\Gamma(p/2)}{\Gamma((p-1)/2)\Gamma(1/2)}(1-y^{2})^{(p-3)/2}\leq
C\sqrt{n}(1-y^{2})^{p/2},$

for some universal constant $C>0$. Further, for
$s\in(\frac{2}{n}\mathbb{Z})\cap[-1,1]$,

$\displaystyle\mathbb{P}(X=s)=\frac{1}{2^{n}}{n\choose
n(1+s)/2}\leq\frac{C}{\sqrt{n}}\exp(nh(s)),$

where $h(s)=-(1+s)/2\log(1+s)-(1-s)/2\log(1-s)$. Using $h(s)\leq-s^{2}/2$,
direct computation now yields that

$\displaystyle\mathbb{E}\Big{[}\exp\Big{(}n\Big{(}\frac{\lambda^{2}}{2}X^{2}+(1+\delta)^{2}\frac{\mu}{\gamma}XY\Big{)}\Big{)}\Big{]}\leq
Cn\int_{\mathbb{R}^{2}}\exp\Big{[}n\Big{(}\frac{\lambda^{2}}{2}s^{2}+\frac{\mu}{\gamma}(1+\delta)^{2}sy-\frac{s^{2}}{2}-\frac{y^{2}}{2\gamma}\Big{)}\Big{]}dsdy<C^{\prime}$

for some universal constant $C^{\prime}$, provided
$\lambda^{2}+\frac{\mu^{2}}{\gamma}(1+\delta)^{2}<1$. This completes the
proof.

Next, we turn to the regime $\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$. We will
devise a test based on the cycle statistic $Y_{n,k,l}$ with

$\displaystyle\frac{l}{k}=\frac{\mu^{2}/\gamma}{\lambda^{2}+\mu^{2}/\gamma},$

and some $k$, to be chosen appropriately. For $k$ growing sufficiently slowly
in $n$, Proposition 1 implies that $Y_{n,k,l}/\sigma_{k,l}$ is approximately
$\mathcal{N}(0,1)$ under $\mathrm{H}_{0}$, while it is distributed as
$\mathcal{N}(\tilde{\mu},1)$ under $\mathrm{H}_{1}$. The non-centrality
parameter in this case is

$\displaystyle\tilde{\mu}$
$\displaystyle=\frac{1}{\sqrt{2k}}\Big{(}\binom{k}{l}(\lambda^{2})^{\alpha}\Big{(}\mu^{2}/\gamma\Big{)}^{\beta}\Big{)}^{1/2}=\exp\Big{(}\frac{1}{2}k\log(\lambda^{2}+\mu^{2}/\gamma)+o(1)\Big{)}.$

Thus for $k$ growing sufficiently slowly in $n$, we will get a sequence of
consistent tests. This establishes the positive side of the detection
threshold.

∎

##  3 Likelihood ratio expansion

Armed with the distributional characterization of Proposition 1, we can
characterlize the likelihood ratio expansion with a version of the small
subgraph conditioning argument relevant to our setting. This argument was
originally formalized by Robinson and Wormald [42, 43] in the context of
random d-regular graphs, and was utilized by [35] in their study of community
detection for the stochastic block model. On the other hand, inspired by a
version of this argument developed by Janson [24], Banerjee and Ma [8] develop
a Gaussian variant of this argument, and apply it to the study of contiguous
regimes for Gaussian matrices with low-rank perturbations. Our setting
naturally has a sparse graph, and a Gaussian component, and thus requires an
extension. We expect this result to be useful in many other settings.

######  Proposition 2 (Small subgraph conditioning method).

Let $\mathbb{P}_{n}$ and $\mathbb{Q}_{n}$ be two sequences of probability
measures, and let $\\{Y_{n,k,l}:(k,l)\in\mathcal{J}\\}$ be such that the
following conditions hold:

  1. 1.

$\mathbb{Q}_{n}$ is absolutely continuous w.r.t. $\mathbb{P}_{n}$.

  2. 2.

All finite dimensional distributions of $\\{Y_{n,k,l}:(k,l)\in\mathcal{J}\\}$
converge to the null distribution under $\mathbb{P}_{n}$, and to the
alternative distribution under $\mathbb{Q}_{n}$, as specified in Proposition
1.

  3. 3.

The likelihood ratio
$L_{n}=\frac{\mathrm{d}\mathbb{Q}_{n}}{\mathrm{d}\mathbb{P}_{n}}$ satisfies:

$\displaystyle\limsup_{n\rightarrow\infty}\mathbb{E}_{\mathbb{P}_{n}}{[L_{n}^{2}]}\leq\exp\Big{\\{}-\frac{1}{2}\log(1-(\lambda^{2}+\frac{\mu^{2}}{\gamma}))-\frac{\lambda^{2}}{2}-\frac{\lambda^{4}}{4}\Big{\\}}<\infty.$

Then, we have the following consequences:

  1. 1.

$\mathbb{P}_{n}$ and $\mathbb{Q}_{n}$ are asymptotically mutually contiguous.

  2. 2.

Under $\mathbb{P}_{n}$, we have that

$\displaystyle
L_{n}\overset{d}{\rightarrow}\exp\Big{(}\sum_{k=1}^{\infty}\Big{[}\log(1-\lambda^{k}d^{k/2})\upsilon_{k,0,0}-\frac{1}{k}(\lambda\sqrt{d})^{k}+\sum_{1\leq
l\leq
k}\frac{\mu_{k,l,0}\upsilon_{k,l,0}-\frac{1}{2}\mu_{k,l,0}^{2}}{\sigma_{k,l}^{2}}\Big{]}\Big{)}.$

Given Proposition 1, the proof of this proposition is identical to the proof
of Proposition 1 of [8], but with some Gaussian terms swapped out with Poisson
terms. Thus we omit the proof.

###  3.1 Proof of Proposition 1

We prove Proposition 1 in this section. Formally, fix
$(k_{1},l_{1}),\cdots,(k_{r},l_{r})\in\mathcal{J}$, and
$m_{1},\cdots,m_{r}\geq 1$. Without loss of generality, we assume that there
exists $r_{1}\leq r$ such that $l_{1}=\cdots=l_{r_{1}}=0$ and $l_{j}>0$ for
$j>r_{1}$. Further, assume that $k_{1}<k_{2}<\cdots<k_{r_{1}}$ and
$k_{r_{1}+1}<k_{r_{1}+2}<\cdots<k_{r}$. For convenience, we will denote

$\displaystyle Z_{n,k_{j},0}=Y_{n,k_{j},0},\,\,\,\,1\leq j\leq r_{1},$
$\displaystyle
Z_{n,k_{r_{1}+1},l_{r_{1}+1}}=Y_{n,k_{r_{1}+1},l_{r_{1}+1}}-p\mathbf{1}_{k_{r_{1}+1}=l_{r_{1}+1}=1},Z_{k_{j},l_{j}}=Y_{n,k_{j},l_{j}},\,\,\,\,\,j>r_{1}.$

We will show that for $j\leq r_{1}$, $Z_{n,k_{j},l_{j}}$ have Poisson limits,
and for $j>r_{1}$, $Z_{n,k_{j},l_{j}}$ have Gaussian limits. This is done with
the method of moments: we will establish that as $n\to\infty$,

$\displaystyle\mathbb{E}_{0,0}\Big{[}\prod_{j=1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}$
$\displaystyle\to\prod_{j=1}^{r_{1}}\mathbb{E}[\upsilon_{k_{j},l_{j},0}^{m_{j}}]\cdot\prod_{j=r_{1}+1}^{r}\sigma_{k_{j},l_{j}}\mathbb{E}[\xi_{j}^{m_{j}}],$
(3)
$\displaystyle\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}$
$\displaystyle\to\prod_{j=1}^{r_{1}}\mathbb{E}[\upsilon_{k_{j},l_{j},1}^{m_{j}}]\cdot\prod_{j=r_{1}+1}^{r}\sigma_{k_{j},l_{j}}\mathbb{E}[\xi_{j}^{m_{j}}],$

where $\\{\xi_{1},\xi_{2},\cdots\\}$ is a sequence of iid $\mathcal{N}(0,1)$
random variables. It is easy to verify that the random variables
$Z_{n,k_{j},l_{j}}$ satisfy Carleman’s condition, so (3) implies the desired
convergence in distribution in Proposition 1.

We first establish a _decoupling_ lemma, which will allow us to separate the
analysis of terms with $l=0$, which have Poisson limits, from terms with
$l>0$, which have Gaussian limits.

######  Lemma 1.

Fix $r\geq 1$ and $r_{1}\leq r$. Fix
$(k_{1},l_{1}),\cdots,(k_{r},l_{r})\in\mathcal{J}$, and
$m_{1},\cdots,m_{r}\geq 1$. Further assume that $l_{j}=0$ for $j\leq r_{1}$,
and $l_{j}>0$ for $r_{1}<j\leq r$. Then we have, as $n\to\infty$,

$\displaystyle\Big{|}\mathbb{E}_{0,0}\Big{[}\prod_{j=1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}-\mathbb{E}_{0,0}\Big{[}\prod_{j=1}^{r_{1}}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}\mathbb{E}_{0,0}\Big{[}\prod_{j=r_{1}+1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}\Big{|}\to
0,$
$\displaystyle\Big{|}\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}-\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=1}^{r_{1}}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=r_{1}+1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}\Big{|}\to
0.$

  * Proof:

We first establish the assertion under $\mathrm{H}_{0}$. We have

$\displaystyle\mathbb{E}_{0,0}\Big{[}\prod_{j=1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}=\mathbb{E}_{0,0}[T_{1}\cdot
T_{2}\cdot T_{3}],$ $\displaystyle T_{1}$
$\displaystyle=\prod_{j=1}^{r_{1}}\Big{(}\sum_{\omega_{j}}\prod_{e\in
E_{\omega_{j},A}}A_{e}\Big{)}^{m_{j}},$ $\displaystyle T_{2}$
$\displaystyle=\Big{(}\frac{1}{n^{l_{r_{1}+1}}}\sum_{\omega_{r_{1}+1}}\prod_{e\in
E_{\omega_{r_{1}+1},A}}A_{e}\prod_{e\in
E_{\omega_{r_{1}+1},B}}B_{e}-p\cdot\mathbf{1}(k_{r_{1}+1}=l_{r_{1}+1}=1)\Big{)}^{m_{r_{1}+1}},$
$\displaystyle T_{3}$
$\displaystyle=\prod_{j=r_{1}+2}^{r}\Big{(}\frac{1}{n^{l_{j}}}\sum_{\omega_{j}}\prod_{e\in
E_{\omega_{j},A}}A_{e}\prod_{e\in E_{\omega_{j},B}}B_{e}\Big{)}^{m_{j}}.$

Expanding, these terms may be expressed as

$\displaystyle T_{1}$
$\displaystyle=\prod_{j=1}^{r_{1}}\Big{(}\sum_{\omega_{j,1},\cdots,\omega_{j,m_{j}}}\prod_{q=1}^{m_{j}}\prod_{e\in
E_{\omega_{j,q},A}}A_{e}\Big{)},$ $\displaystyle T_{2}$
$\displaystyle=\frac{1}{n^{l_{r_{1}+1}m_{r_{1}+1}}}\sum_{\omega_{r_{1}+1,1},\cdots,\omega_{r_{1}+1,m_{r_{1}+1}}}\prod_{q=1}^{m_{r_{1}+1}}\Big{(}\prod_{e\in
E_{\omega_{r_{1}+1,q},A}}A_{e}\prod_{e\in
E_{\omega_{r_{1}+1,q},B}}B_{e}-p\cdot\mathbf{1}(k_{r_{1}+1}=l_{r_{1}+1}=1)\Big{)},$
$\displaystyle T_{3}$
$\displaystyle=\prod_{j=r_{1}+2}^{r}\Big{(}\frac{1}{n^{l_{j}m_{j}}}\sum_{\omega_{j,1},\cdots,\omega_{j,m_{j}}}\prod_{q=1}^{m_{j}}\prod_{e\in
E_{\omega_{j,q},A}}A_{e}\prod_{e\in E_{\omega_{j,q},B}}B_{e}\Big{)}.$

Thus we have,

$\displaystyle\mathbb{E}_{0,0}[T_{1}T_{2}T_{3}|\mathbf{A}]$
$\displaystyle=\frac{1}{n^{\sum_{j=r_{1}+1}^{r}l_{j}m_{j}}}\sum_{j\in[r],1\leq
q_{j}\leq
m_{j},\omega_{j,q_{j}}}\mathbb{E}_{0,0}\left[\begin{matrix}\Big{(}\prod_{j=1}^{r_{1}}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\times\\\
\prod_{q=1}^{m_{r_{1}+1}}\Big{(}\prod_{e\in
E_{\omega_{r_{1}+1,q},A}}A_{e}\prod_{e\in
E_{\omega_{r_{1}+1,q},B}}B_{e}-p\cdot\mathbf{1}(k_{r_{1}+1}=l_{r_{1}+1}=1)\Big{)}\times\\\
\prod_{j=r_{1}+2}^{r}\prod_{q_{j}=1}^{m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},A}}A_{e}\prod_{e\in
E_{\omega_{j,q_{j}},B}}B_{e}\end{matrix}\Big{|}A\right].$

Consider first the case $(k_{r_{1}+1},l_{r_{1}+1})\neq(1,1)$. In this case,

$\displaystyle\mathbb{E}_{0,0}[T_{1}T_{2}T_{3}]=\frac{1}{n^{\sum_{j=r_{1}+1}^{r}l_{j}m_{j}}}\times$
(4) $\displaystyle\sum_{j\in[r],1\leq q_{j}\leq
m_{j},\omega_{j,q_{j}}}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{j=1}^{r_{1}}\prod_{q_{j}\leq
m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\Big{(}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\Big{]}\mathbb{E}_{0,0}\Big{[}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},B}}B_{e}\Big{]}.$

On the other hand, a similar calculation yields

$\displaystyle\mathbb{E}_{0,0}\Big{[}\prod_{j=1}^{r_{1}}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}\mathbb{E}_{0,0}\Big{[}\prod_{j=r_{1}+1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}=\frac{1}{n^{\sum_{j=r_{1}+1}^{r}l_{j}m_{j}}}\times$
$\displaystyle\sum_{j\in[r],1\leq q_{j}\leq
m_{j},\omega_{j,q_{j}}}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{j=1}^{r_{1}}\prod_{q_{j}\leq
m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\Big{]}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\Big{]}\times$ (5)
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathbb{E}_{0,0}\Big{[}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},B}}B_{e}\Big{]}.$

To establish that the difference between the two quantities is $o(1)$, note
that if two cycles overlap on $m$-edges, we gain a factor $O(n^{m})$. However,
this naturally implies they overlap on at least $(m+1)$ vertices. As a result,
we lose a factor $n^{m+1}$ in choosing these cycles. As a result, the dominant
contributions arise from non-overlapping cycles, thus establishing the desired
claim in this case. The proof for $(k_{r_{1}+1},l_{r_{1}+1})=(1,1)$ is exactly
analogous.

Under $\mathbb{P}_{\lambda,\mu}$, if $(k_{r_{1}+1},l_{r_{1}+1})\neq(1,1)$, we
have,

$\displaystyle\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=1}^{r}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}=\frac{1}{n^{\sum_{j=r_{1}+1}^{r}l_{j}m_{j}}}\times$
$\displaystyle\mathbb{E}_{\sigma}\Big{[}\sum_{j\in[r],1\leq q_{j}\leq
m_{j},\omega_{j,q_{j}}}\mathbb{E}_{\lambda,\mu}\Big{[}\Big{(}\prod_{j=1}^{r_{1}}\prod_{q_{j}\leq
m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\Big{(}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\mid\sigma\Big{]}\times$
(6) $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},B}}B_{e}\mid\sigma\Big{]}\Big{]}.$

On the other hand,

$\displaystyle\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=1}^{r_{1}}Z_{n,k_{j},l_{j}}^{m_{j}}\Big{]}\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=r_{1}+1}^{r}(Z_{n,k_{j},l_{j}})^{m_{j}}\Big{]}=\frac{1}{n^{\sum_{j=r_{1}+1}^{r}l_{j}m_{j}}}\times$
$\displaystyle\mathbb{E}_{\sigma}\Big{[}\sum_{j\in[r],1\leq q_{j}\leq
m_{j},\omega_{j,q_{j}}}\mathbb{E}_{\lambda,\mu}\Big{[}\Big{(}\prod_{j=1}^{r_{1}}\prod_{q_{j}\leq
m_{j}}\prod_{e\in
E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\mid\sigma\Big{]}\mathbb{E}_{\lambda,\mu}\Big{[}\Big{(}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},A}}A_{e}\Big{)}\mid\sigma\Big{]}\times$
(7) $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=r_{1}+1}^{r}\prod_{q_{j}\leq
m_{j}}\prod_{e\in E_{\omega_{j,q_{j}},B}}B_{e}\mid\sigma\Big{]}\Big{]}.$

To see that the difference between the quantities is again $o(1)$, first
condition on the choice of $\sigma$, and consider the difference in the inner
sums. Again, if two cycles overlap on $m$ edges, we will gain a factor of
$O(n^{m})$, but we lose a factor of $n^{m+1}$ for the number of such choices.
Thus the dominant contribution again comes from the non-overlapping cycles.
The proof from $(k_{r_{1}+1},l_{r_{1}+1})=(1,1)$ follows analogously. ∎

Armed with Lemma 1, we turn to a proof of Proposition 1.

  * Proof of Propostion 1:

First we note that Lemma 1 immediately implies that the terms
$Z_{n,k_{i},l_{i}}$ with $i\leq r_{1}$ are asymptotically independent to the
terms $Z_{n,k_{j},l_{j}}$, with $j>r_{1}$. Moreover, the limiting
distributions of $\\{Y_{n,k,0}:k\geq 3\\}$ under both $\mathrm{H}_{0}$ and
$\mathrm{H_{1}}$ follows directly from [35, Theorem 3.1]. Thus, we have, as
$n\to\infty$,

$\displaystyle\mathbb{E}_{0,0}\Big{[}\prod_{j=1}^{r_{1}}Z_{n,k_{j},0}^{m_{j}}\Big{]}\to\prod_{j=1}^{r_{1}}\mathbb{E}[\upsilon_{k_{j},0,0}^{m_{j}}],\,\,\,\,\,\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{j=1}^{r_{1}}Z_{n,k_{j},0}^{m_{j}}\Big{]}\to\prod_{j=1}^{r_{1}}\mathbb{E}[\upsilon_{k_{j},0,1}^{m_{j}}].$

Thus it suffices to analyze the terms with $l>0$, and we show that in this
case $Z_{n,k,l}$ will have asymptotically Gaussian limits under
$\mathrm{H}_{0}$ and $\mathrm{H}_{1}$.

Calculation under $\mathrm{H}_{0}$: We establish the limiting distribution in
three steps.

    * (i)

Calculation of the mean and variance of $Y_{n,k,l}-p\mathbf{1}(k=l=1)$ under
the null.

    * (ii)

Verification of Wick’s formula.

    * (iii)

Verification of asymptotic independence.

We address (i), and calculate the means and variances of the cycle statistics.
Note that the case $l=k$ corresponds to the cycle statistics in [8], and we
can read off the null expectations and variances directly. Specifically, we
have,

$\displaystyle\mathbb{E}_{0,0}[Y_{n,k,k}-p\mathbf{1}(k=1)]=0,$
$\displaystyle\mathrm{Var}_{0,0}\Big{(}Y_{n,k,k}-\mathbf{1}(k=1)\Big{)}=(1+o(1))2k\gamma^{k}.$

We consider now the case $0<l<k$. We have

$\displaystyle\mathbb{E}_{0,0}[Y_{n,k,l}]=0.$

Moving onto the variance, we have,

$\displaystyle\mathbb{E}_{0,0}[Y_{n,k,l}^{2}]$
$\displaystyle=\frac{1}{n^{2l}}\sum_{\omega_{1},\omega_{2}}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{e_{1}\in
E_{\omega_{1},A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega_{1},B}}B_{e_{2}}\Big{)}\Big{(}\prod_{e_{1}\in
E_{\omega_{2},A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega_{2},B}}B_{e_{2}}\Big{)}\Big{]}$ (8)
$\displaystyle=\frac{1}{n^{2l}}\sum_{\omega}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega,B}}B_{e_{2}}\Big{)}^{2}\Big{]}+T_{1},$

where $T_{1}$ tracks the contribution from the pairs $(\omega_{1},\omega_{2})$
with $\omega_{1}\neq\omega_{2}$. First, observe that

$\displaystyle\frac{1}{n^{2l}}\sum_{\omega}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega,B}}B_{e_{2}}\Big{)}^{2}\Big{]}=\frac{1}{n^{2l}}\sum_{\omega}\mathbb{E}_{0,0}\Big{[}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega,B}}B_{e_{2}}^{2}\Big{]}=\frac{1}{n^{2l}}\sum_{\omega}\Big{(}\frac{d}{n}\Big{)}^{k-l}.$

It remains to count the number of length $k$ cycles with $l$ $B$-wedges. Any
such cycle has $k$-vertices of type $A$, and this choice can be done in
$n^{k}$ ways. The positions of the $B$-wedges can be chosen in ${k\choose l}$
ways. The $B$-vertices on the $B$-wedges can be chosen in $p^{l}$ ways.
Finally, we divide this count by $2k$ to account for overcounting due to
cyclic shifts. This implies

$\displaystyle\frac{1}{n^{2l}}\sum_{\omega}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega,B}}B_{e_{2}}\Big{)}^{2}\Big{]}=\frac{1}{n^{2l}}\sum_{\omega}\Big{(}\frac{d}{n}\Big{)}^{k-l}=\frac{1}{n^{2l}}\cdot\Big{(}\frac{d}{n}\Big{)}^{k-l}\cdot\frac{1}{2k}n^{k}{k\choose
l}p^{l}$ $\displaystyle=\frac{1}{2k}{k\choose
l}\frac{d^{k-l}}{\gamma^{l}}(1+o(1)).$

We will next establish that this is the dominant term in the asymptotic
variance, and that $T_{1}\to 0$ as $n\to\infty$. Note that a product term
corresponding to $(\omega_{1},\omega_{2})$ with $\omega_{1}\neq\omega_{2}$ has
a non-zero contribution provided they share exactly the same $B$-wedges. For
any two such cycles $(\omega_{1},\omega_{2})$, suppose they share $\alpha_{1}$
$A$ edges. Note that $\omega_{1}\neq\omega_{2}$, and thus
$0\leq\alpha_{1}<k-l$. As $\omega_{1}$ and $\omega_{2}$ cannot differ on
exactly one edge, in fact, this implies $\alpha_{1}\leq k-l-2$. Setting
$\alpha_{2}=k-l-\alpha_{1}$, we have,

$\displaystyle T_{1}$
$\displaystyle=\frac{1}{n^{2l}}\sum_{\omega_{1}\neq\omega_{2}}\mathbb{E}_{0,0}\Big{[}\Big{(}\prod_{e_{1}\in
E_{\omega_{1},A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega_{1},B}}B_{e_{2}}\Big{)}\Big{(}\prod_{e_{1}\in
E_{\omega_{2},A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega_{2},B}}B_{e_{2}}\Big{)}\Big{]}$
$\displaystyle=\frac{1}{n^{2l}}\sum_{\alpha_{2}=2}^{k-l}\sum_{|E_{\omega_{1},A}\cap
E_{\omega_{2},A}|=k-l-\alpha_{2}}\Big{(}\frac{d}{n}\Big{)}^{k-l+\alpha_{2}}.$

It remains to count the number of pairs $(\omega_{1},\omega_{2})$ with
$|E_{\omega_{1},A}\cap E_{\omega_{2},A}|=k-l-\alpha_{2}$ for all
$2\leq\alpha_{2}\leq k-l$. We derive a rough upper bound to the number of such
pairs as follows: there are $O(n^{k}p^{l})$ choices for the first cycle, and
$O(n^{\alpha_{2}-1})$ choices for the second cycle $\omega_{2}$, given
$\omega_{1}$. Thus we bound the number of such pairs as
$C(k,\gamma)n^{k+l+\alpha_{2}-1}$, where $C(k,\gamma)>0$ is independent of
$n$. Plugging in this bound, we obtain

$\displaystyle T_{1}\leq
C(k,\gamma)\frac{1}{n^{2l}}\sum_{\alpha_{2}=2}^{k-l}n^{k+l+\alpha_{2}-1}\cdot\Big{(}\frac{d}{n}\Big{)}^{k-l+\alpha_{2}}=O\Big{(}\frac{1}{n}\Big{)}.$

This controls $T_{1}$, and establishes the right order of the variance under
$\mathrm{H}_{0}$.

We next turn to (ii). We want to show that $Z_{n,k,l}$ are asymptotically
Gaussian by showing the limit of their moments (3). This is done by checking
that the limits of the moments satisfy Wick’s formula. Formally, we show that
for $W_{ni}\in\\{Z_{n,k_{r_{1}+1},l_{r_{1}+1}},\cdots,Z_{n,k_{r},l_{r}}\\}$,
$i\in[m]$, we have that

$\lim_{n\to\infty}\mathbb{E}[W_{n1}\cdots
W_{nm}]=\begin{cases}\sum_{\eta}\prod_{i=1}^{m/2}\mathbb{E}[W_{n\eta(i,1)}W_{n\eta(i,2)}]+o(1)&\textrm{if}\,\,m\,\,\textrm{even}\\\
o(1)&\textrm{o.w.}\end{cases}$ (9)

where $\eta$ is a partition of $[m]$ into $\frac{m}{2}$ blocks of size two,
and $\eta(i,j)$ denotes the $j$-th element of the $i$-th block, where
$j\in\\{1,2\\}$. Wick’s formula [46] then implies that the limiting
distribution must be Gaussian, as long as the limits of
$\mathbb{E}[W_{n\eta(i,1)}W_{n\eta(i,2)}]$ exist.

We will perform the calculations assuming that
$(k_{r_{1}+1},l_{r_{1}+1})\not=(1,1)$; the same calculations hold in the case
of equality and hence are omitted. For a choice of $W_{n1},\cdots,W_{nm}$, let
$\omega_{1:m}$ be a collection of cycles $\omega_{1},...,\omega_{m}$, such
that $\omega_{i}$ is of length $k_{i}$, with $l_{i}$ $B$ wedges and $x_{i}$
contiguous blocks of $A$ type edges and $B$ type wedges. Note then that

$\displaystyle\begin{aligned} &\mathbb{E}_{0,0}[W_{n1}\cdots W_{nm}]\\\
&=\mathbb{E}_{0,0}\Big{[}{n^{-\sum_{i}l_{i}}\sum_{\omega_{1:m}}\prod_{i\leq
m}\prod_{e_{1}\in E_{\omega_{i},A}}A_{e_{1}}\prod_{e_{2}\in
E_{\omega_{i},B}}B_{e_{2}}}\Big{]}\\\
&=n^{-\sum_{i}l_{i}}\sum_{\omega_{1:m}}\mathbb{E}_{0,0}\Big{[}{\prod_{i\leq
m}\prod_{e_{1}\in
E_{\omega_{i},A}}A_{e_{1}}}\Big{]}\mathbb{E}_{0,0}\Big{[}{\prod_{i\leq
m}\prod_{e_{2}\in\tilde{E}_{\omega_{i}}}B_{e_{2}}}\Big{]}\end{aligned}$ (10)

where $\tilde{E}_{\omega_{i}}$ are the edges of
$\tilde{G}_{\omega_{i}}=G_{\omega_{i}}/G_{\omega_{i},A}$, the quotient graph
where for each $j\leq x_{i}$, $G_{\omega_{i},\alpha_{j}}$, the graph of the
$j$th $A$ block in $\omega_{i}$, is identified as a vertex of
$\tilde{G}_{\omega_{i}}$. We denote the vertices of $\tilde{G}_{\omega_{i}}$
as
$\tilde{V}_{\omega_{i}}=\tilde{V}^{1}_{\omega_{i}}\cup\tilde{V}^{2}_{\omega_{i}}$,
where $\tilde{V}^{1}$ are the vertices inherited from $G_{\omega_{i}}$, and
$\tilde{V}^{2}$ are the vertices produced by the quotient operator. Among
$\tilde{V}^{2}$, we define the following equivalence relationship: if the
first and last vertices of $G_{\omega_{i},\alpha^{i}_{j}}$ and
$G_{\omega_{h},\alpha^{h}_{p}}$ are the same, then we consider the vertices in
$\tilde{G}_{\omega_{i}}$ and $\tilde{G}_{\omega_{h}}$, which correspond to the
quotient image of $G_{\omega_{i},\alpha^{i}_{j}}$ and
$G_{\omega_{h},\alpha^{h}_{p}}$ respectively, to be the same. In order for the
contribution of $\omega_{1:m}$ to be non-zero, the $B$ edges have to be
included at least twice, and we will call such a collection
$\tilde{G}_{\omega_{1:m}}$ a weak CLT sentence. Given a weak CLT sentence, we
define a partition $\eta(\tilde{G}_{\omega_{1:m}})$ of $[m]$ as follows: $i$
and $j$ are in the same partition if $\tilde{G}_{\omega_{i}}$ and
$\tilde{G}_{\omega_{j}}$ share at least one edge. As a result, we can express
(10) as follows:

$\displaystyle
n^{-\sum_{i}l_{i}}\sum_{G_{\omega_{1:m},A}}\operatorname{\mathbb{E}}_{0,0}\Big{[}{\prod_{e_{1}\in
E_{\omega_{1:m},A}}A_{e_{1}}}\Big{]}\sum_{\eta}\sum_{\begin{subarray}{c}\tilde{G}_{\omega_{1:m}}\\\
\eta(\tilde{G}_{\omega_{1:m}})=\eta\end{subarray}}\operatorname{\mathbb{E}}_{0,0}\Big{[}{\prod_{e_{2}\in\tilde{E}_{\omega_{1:m}}}B_{e_{2}}}\Big{]}.$

Let $t$ be the total number of vertices of $\tilde{G}_{\omega_{1:m}}$. Let us
consider the case where $\eta(\tilde{G}_{\omega_{1:m}})$ contains strictly
less than $\frac{m}{2}$ blocks, which includes all cases when $m$ is odd. In
this case [4, Lemma 4.10] implies that $t<\sum_{i}l_{i}$. Following the proof
of [8, Lemma 3], we note that the number of weak CLT sentences summed over is
bounded by

$\displaystyle
O\Big{(}\sum_{i}l_{i}\Big{)}^{O(\sum_{i}l_{i})}n^{t-\sum_{i}x_{i}}.$

This comes from the fact that $\sum_{i}x_{i}$ of the vertices are
automatically fixed from the quotient operator. As a result, for a particular
partition $\eta$, where $|\eta|<\frac{m}{2}$, we note that:

$\displaystyle
n^{-\sum_{i}l_{i}}\sum_{G_{\omega_{1:m},A}}\mathbb{E}_{0,0}\Big{[}{\prod_{e_{1}\in
E_{\omega_{1:m},A}}A_{e_{1}}}\Big{]}\sum_{\begin{subarray}{c}\tilde{G}_{\omega_{1:m}}\\\
\eta(\tilde{G}_{\omega_{1:m}}=\eta)\end{subarray}}\mathbb{E}_{0,0}\Big{[}{\prod_{e_{2}\in\tilde{E}_{\omega_{1:m}}}B_{e_{2}}}\Big{]}$
$\displaystyle=n^{-\sum_{i}l_{i}}\sum_{G_{\omega_{1:m},A}}\mathbb{E}_{0,0}\Big{[}{\prod_{e_{1}\in
E_{\omega_{1:m},A}}A_{e_{1}}}\Big{]}\sum_{\begin{subarray}{c}\tilde{G}_{\omega_{1:m}}\\\
\eta(\tilde{G}_{\omega_{1:m}}=\eta)\end{subarray}}O(1)^{O(\sum_{i}l_{i})}$
$\displaystyle=n^{-\sum_{i}l_{i}}O\Big{(}\sum_{i}l_{i}\Big{)}^{O(\sum_{i}l_{i})}n^{t-\sum_{i}x_{i}}\sum_{G_{\omega_{1:m},A}}\mathbb{E}_{0,0}\Big{[}{\prod_{e_{1}\in
E_{\omega_{1:m},A}}A_{e_{1}}}\Big{]}$
$\displaystyle=n^{-\sum_{i}l_{i}}O\Big{(}\sum_{i}l_{i}\Big{)}^{O(\sum_{i}l_{i})}n^{t-\sum_{i}x_{i}}O\Big{(}\frac{d}{n}\Big{)}^{\sum_{i}\sum_{j\leq
x_{i}}2\alpha^{i}_{j}}O(n)^{\sum_{i}\sum_{j\leq x_{i}}(2\alpha^{i}_{j}+1)}$
$\displaystyle=O\Big{(}\sum_{i}l_{i}\Big{)}^{O(\sum_{i}l_{i})}O(n)^{t-\sum_{i}l_{i}}.$

The penultimate line holds because for an $A$ block of length
$2\alpha^{i}_{j}$, there are $2\alpha^{i}_{j}+1$ vertices, for which there are
$O(n)$ options each. Thus the total number of choices for $E_{\omega_{1:m},A}$
is $O(n)^{\sum_{i}\sum_{j\leq x_{i}}(2\alpha^{i}_{j}+1)}$. Since
$t<\sum_{i}l_{i}$, we see that the contribution of such a term is $o(1)$.

We have thus shown that the leading order term of (10) consists of weak CLT
sentences whose partition $\eta(\tilde{G}_{\omega_{1:m}})$ has exactly
$\frac{m}{2}$ blocks. Note that this automatically implies that (10) is $o(1)$
if $m$ is odd, and that for $m$ even, the leading order weak CLT sentences
have partitions $\eta$ with only blocks of size two, which is exactly what we
need for (9). From our calculations in step (i), we see that the variances of
$Z_{n,k,l}$ under the null are as we claimed.

Finally, we verify step (iii), that for $l\geq 1$, $Z_{n,k,l}$ are
asymptotically independent. From the discussion above (9), this amounts to
checking that for $W_{ni}\not=W_{nj}$,
$\operatorname{\mathbb{E}}_{0,0}[W_{ni}W_{nj}]\overset{p}{\to}0$. Note that
this expectation equals $0$ if $l_{i}\not=l_{j}$. Thus it suffices to consider
the case $l_{i}=l_{j}$, $k_{i}<k_{j}$ and we have:

$\displaystyle\operatorname{\mathbb{E}}_{0,0}[W_{ni}W_{nj}]$
$\displaystyle=n^{-2l_{i}}\sum_{\omega_{i},\omega_{j}}\mathbb{E}_{0,0}\left[\prod_{e_{1}\in
E_{\omega_{i}}}A_{e_{1}}\prod_{e_{1}\in E_{\omega_{j}}}A_{e_{1}}\right]$ where
the sum is taken over $\omega_{i}$, $\omega_{j}$ that intersect on all $l_{i}$
$B$-wedges, which gives
$\displaystyle\operatorname{\mathbb{E}}_{0,0}[W_{ni}W_{nj}]$
$\displaystyle\leq
C(k_{i},d,\gamma)n^{-2l_{i}}\left(\frac{1}{n}\right)^{k_{i}+k_{j}-2l_{i}}n^{k_{i}+k_{j}-l_{i}-1}=o(1).$

This concludes the demonstration of Wick’s formula under $H_{0}$, and hence
proves the desired convergence in distribution.

Calculation under $\mathrm{H}_{1}$: We establish the desired result following
similar steps as the calculation under $\mathrm{H}_{0}$. First, we calculate
the means of the cycle statistics under $\mathrm{H}_{1}$.

We start by observing that the case $k=l=1$ follows directly from the
calculations in [8], while the $l=0$ cases correspond to $A$ type cycles, and
have been worked out in [35]. We consider the remaining cases. To this end,
note that under $\mathbb{P}_{\lambda,\mu}$, for any $B$-wedge
$B_{i_{1},j_{1}}B_{i_{2},j_{1}}$, we have,

$\displaystyle\mathbb{E}_{\lambda,\mu}[B_{i_{1},j_{1}}B_{i_{2},j_{1}}|\mathbb{\sigma}]=\frac{\mu}{n}\sigma_{i_{1}}\sigma_{i_{2}}.$

Now fix any cycle $\omega$ with $k-l$ A-edges and $l$ B-wedges.

$\displaystyle\mathbb{E}_{\lambda,\mu}[Y_{n,k,l}]=\frac{1}{n^{l}}\sum_{\omega}\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}B_{e_{2}}\Big{]}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\omega}\mathbb{E}_{\sigma}\Big{[}\prod_{e_{1}\in
E_{\omega,A}}\Big{(}\frac{d+\lambda\sqrt{d}\,\sigma_{e_{1}^{-}}\sigma_{e_{1}^{+}}}{n}\Big{)}\prod_{e_{2}\in
E_{\omega,B}}\Big{(}\frac{\mu}{n}\sigma_{e_{2}^{-}}\sigma_{e_{2}^{+}}\Big{)}\Big{]}.$

In the final equality, for an $A$-type edge $e_{1}$, we use
$e_{1}^{-},e_{1}^{+}$ to denote its end points. Similarly, for a $B$-wedge
$\\{i,j,k\\}$, we set $e^{-}=i$, $e^{+}=k$. Each cycle $\omega$ has $k-l$
$A$-edges and $l$ $B$ wedges, and thus

$\displaystyle\mathbb{E}_{\lambda,\mu}[Y_{n,k,l}]=\frac{\mu^{l}}{n^{k+l}}\sum_{\omega}\mathbb{E}_{\sigma}\Big{[}\sum_{z_{e}\in\\{d,\lambda\sqrt{d}\sigma_{e^{-}}\sigma_{e^{+}}\\}:e\in
E_{\omega,A}}\prod_{e\in E_{\omega,A}}z_{e}\prod_{e^{\prime}\in
E_{\omega,B}}\sigma_{e^{\prime-}}\sigma_{e^{\prime+}}\Big{]}$ (11)

Observe that we have a non-zero contribution in the sum above if and only if
$z_{e}=\lambda\sqrt{d}\sigma_{e^{-}}\sigma_{e^{+}}$ for all $e\in
E_{\omega,A}$; in this case, each term contributes $(\lambda\sqrt{d})^{k-l}$.
Note that the number of $k$ cycles with $l$ $B$-wedges is
$\frac{1}{2k}{k\choose l}n^{k}p^{l}$, and thus, upon simplification,

$\displaystyle\mathbb{E}_{\lambda,\mu}[Y_{n,k,l}]=(1+o(1))\frac{1}{2k}{k\choose
l}\Big{(}\frac{\mu}{\gamma}\Big{)}^{l}(\lambda\sqrt{d})^{k-l}.$

We turn to the calculation of the variance under $\mathrm{H}_{1}$. Note that
under $\mathrm{H}_{1}$, $B_{ij}=X_{ij}+Z_{ij}$, where
$X_{ij}=\sqrt{\frac{\mu}{n}}\cdot\sigma_{i}u_{j}$. Thus we have,

$\displaystyle Y_{n,k,l}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\omega}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}B_{e_{2}}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\omega}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}(X_{e_{2}}+Z_{e_{2}})$
$\displaystyle=T_{1}+T_{2}+T_{3},$

where

$\displaystyle T_{1}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\omega}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}Z_{e_{2}},$ $\displaystyle
T_{2}$ $\displaystyle=\frac{1}{n^{l}}\sum_{\omega}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}X_{e_{2}},$ $\displaystyle
T_{3}$ $\displaystyle=Y_{n,k,l}-T_{1}-T_{3}.$

The term $T_{1}$ can be analyzed exactly as under $\mathrm{H}_{0}$, and the
same arguments will show that
$T_{1}\overset{d}{\to}\mathcal{N}(0,\frac{1}{2k}\binom{k}{l}\frac{d^{k-l}}{\gamma^{l}})$.
We will establish that $T_{2}\stackrel{{\scriptstyle
P}}{{\to}}\frac{1}{2k}\binom{k}{l}\frac{(\lambda\sqrt{d})^{k-l}\mu^{l}}{\gamma^{l}}$,
and that $T_{3}\stackrel{{\scriptstyle P}}{{\to}}0$.

First, we will consider $T_{3}$. Note that
$\mathbb{E}_{\lambda,\mu}[T_{3}]=0$, and thus it suffices to establish that
$\mathbb{E}_{\lambda,\mu}[T_{3}^{2}]=o(1)$ as $n\to\infty$. Now, we can
express $T_{3}=\sum_{\omega}V_{n,k,l,\omega}$, where

$\displaystyle V_{n,k,l,\omega}=\frac{1}{n^{l}}\prod_{e\in
E_{\omega,A}}A_{e}\sum_{E_{\omega,f}\subsetneq E_{\omega,B}}\prod_{e\in
E_{\omega,f}}X_{e}\prod_{e\in E_{\omega,B}\backslash E_{\omega,f}}Z_{e}.$

Therefore,

$\displaystyle\mathbb{E}_{\lambda,\mu}[T_{3}^{2}]=\sum_{\omega_{1},\omega_{2}}\mathbb{E}_{\lambda,\mu}[V_{n,k,l,\omega_{1}}V_{n,k,l,\omega_{2}}]$
$\displaystyle:=\sum_{\omega_{1},\omega_{2}}\sum_{E_{\omega_{1},f}\subsetneq
E_{\omega_{1},B},E_{\omega_{2},f}\subsetneq
E_{\omega_{2},B}}\mathbb{E}_{\lambda,\mu}[V_{n,k,l,\omega_{1},E_{f,\omega_{1}}}V_{n,k,l,\omega_{2},E_{f,\omega_{2}}}],$

where we define

$\displaystyle V_{n,k,l,\omega,E_{f,\omega}}:=\frac{1}{n^{l}}\prod_{e\in
E_{\omega,A}}A_{e}\prod_{e\in E_{\omega,f}}X_{e}\prod_{e\in
E_{\omega,B}\backslash E_{\omega,f}}Z_{e}.$

This implies
$\mathbb{E}_{\lambda,\mu}[V_{n,k,l,\omega_{1},E_{f,\omega_{1}}}V_{n,k,l,\omega_{2},E_{f,\omega_{2}}}]$
is zero unless $E_{\omega_{1},B}\backslash
E_{\omega_{1},f}=E_{\omega_{2},B}\backslash E_{\omega_{2},f}$. Given
$\omega_{1},\omega_{2}$, the terms which affect the contribution by powers of
$n$ are the edges in $E_{\omega_{1},A}\cap E_{\omega_{2},A}$. The dominant
contribution arises from $\omega_{1},\omega_{2}$ such that
$|E_{\omega_{1},A}\cap E_{\omega_{2},A}|=0$—this follows using the same
reasoning used to identify the dominant order of the variance under
$\mathrm{H}_{0}$. Further, note that overlaps in the edges in
$E_{\omega_{1},f}$ and $E_{\omega_{2},f}$ affect the expectation, but only to
constant order. For a pair $(\omega_{1},\omega_{2})$ satisfying these
conditions

$\displaystyle\mathbb{E}_{\lambda,\mu}[V_{n,k,l,\omega_{1},E_{f,\omega_{1}}}V_{n,k,l,\omega_{2},E_{f,\omega_{2}}}]=\frac{1}{n^{2l}}\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{e\in
E_{\omega_{1},A}}A_{e}\prod_{e\in E_{\omega_{2},A}}A_{e}\prod_{e\in
E_{\omega_{1},f}}X_{e}\prod_{e\in E_{\omega_{2},f}}X_{e}\Big{]}.$

As $\omega_{1},\omega_{2}$ are both length $k$ cycles with $k-l$ $A$ edges and
$l$ B-edges, and $E_{\omega_{1},B}\backslash
E_{\omega_{1},f}=E_{\omega_{2},B}\backslash E_{\omega_{2},f}$, we have
$|E_{\omega_{1},f}|=|E_{\omega_{2},f}|:=x$. In turn, this implies that there
exists $C:=C(k,l)>0$ such that

$\displaystyle\mathbb{E}_{\lambda,\mu}[V_{n,k,l,\omega_{1},E_{f,\omega_{1}}}V_{n,k,l,\omega_{2},E_{f,\omega_{2}}}]$
$\displaystyle\leq
C\frac{1}{n^{2l+x}}\mathbb{E}_{\lambda,\mu}\Big{[}\prod_{e\in
E_{\omega_{1},A}}A_{e}\prod_{e\in E_{\omega_{2},A}}A_{e}\Big{]}\leq
C^{\prime}\frac{1}{n^{2k+x}},$

where $C^{\prime}:=C^{\prime}(k,l,\lambda,d)>0$ is a constant independent of
$n$. There are only finitely many choices of $E_{\omega_{1},f}$ and
$E_{\omega_{2},f}$, and therefore, for each $\omega_{1},\omega_{2}$,

$\displaystyle\sum_{E_{\omega_{1},f}\subsetneq
E_{\omega_{1},B},E_{\omega_{2},f}\subsetneq
E_{\omega_{2},B}}\mathbb{E}_{\lambda,\mu}[V_{n,k,l,\omega_{1},E_{f,\omega_{1}}}V_{n,k,l,\omega_{2},E_{f,\omega_{2}}}]\leq
C^{\prime\prime}\frac{1}{n^{2k+x}},$

for a larger constant $C^{\prime\prime}$. Finally, we sum over
$\omega_{1},\omega_{2}$. If the two cycles intersect on $x$ edges, they have
$x+1$ vertices in common. Thus the number of pairs $\omega_{1},\omega_{2}$
with $x$ common edges is $O(n^{2k+2l-x-1})$. Summing, we have the conclusion
that $\mathbb{E}_{\lambda,\mu}[T_{3}^{2}]=o(1)$.

Finally, we turn to $T_{2}$. For any $1\leq i_{1}<\cdots<i_{k}\leq n$, we let
$\mathbf{i}_{1:k}=(i_{1},\cdots,i_{k})$. Similarly, for $1\leq
j_{1}<\cdots<j_{l}\leq p$, set $\mathbf{j}_{1:l}=(j_{1},\cdots,j_{p})$.
Finally, given $\mathbf{i}_{1:k}$ and $\mathbf{j}_{1:l}$, let
$\mathcal{C}(\mathbf{i}_{1:k},\mathbf{j}_{1:l})$ denote the set of cycles with
$k-l$ $A$-edges and $l$ $B$-wedges on the chosen vertices. Armed with this
notation, we observe that

$\displaystyle T_{2}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\omega}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}X_{e_{2}}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\mathbf{i}_{1:k},\mathbf{j}_{1:l}}\sum_{\omega\in\mathcal{C}(\mathbf{i}_{1:k},\mathbf{j}_{1:l})}\prod_{e_{1}\in
E_{\omega,A}}A_{e_{1}}\prod_{e_{2}\in E_{\omega,B}}X_{e_{2}}.$

Given $\mathbf{i}_{1:k}$, let $\mathcal{C}(\mathbf{i}_{1:k})$ denote all
length $k$ cycles on the vertices $i_{1},i_{2},\cdots,i_{k}$, with $(k-l)$
edges colored to be of type $A$, and the remaining edges colored to be of type
$B$. For any edge in the cycle, let $t(e)\in\\{A,B\\}$ denote its type. This
implies

$\displaystyle T_{2}$
$\displaystyle=\frac{1}{n^{l}}\Big{(}\sum_{\mathbf{i}_{1:k}}\sum_{\omega\in\mathcal{C}(\mathbf{i}_{1:k})}\prod_{t(e)=A}A_{e}\prod_{t(e)=B}\sigma_{e^{-}}\sigma_{e^{+}}\Big{)}\Big{(}\Big{(}\frac{\mu}{n}\Big{)}^{l}\sum_{\mathbf{j}_{1:l}}\prod_{h=1}^{l}u_{j_{h}}^{2}\Big{)}.$

Note that for fixed $\mathbf{j}_{1:l}$, $u_{jh}^{2}$ are independent with mean
$1$, so law of large numbers gives

$\displaystyle\frac{1}{n^{l}}\sum_{\mathbf{j}_{1:l}}\prod_{h=1}^{l}u_{j_{h}}^{2}\stackrel{{\scriptstyle
P}}{{\to}}1.$

Thus it suffices to control the other term. In particular, it suffices to show
that

$\displaystyle\mathrm{Var}_{\lambda,\mu}\Big{(}\frac{1}{n^{l}}\Big{(}\sum_{\mathbf{i}_{1:k}}\sum_{\omega\in\mathcal{C}(\mathbf{i}_{1:k})}\prod_{t(e)=A}A_{e}\prod_{t(e)=B}\sigma_{e^{-}}\sigma_{e^{+}}\Big{)}\Big{)}=o(1)$

as $n\to\infty$. This amounts to checking that

$\displaystyle\mathbb{E}_{\lambda,\mu}\left[\frac{1}{n^{2l}}\Big{(}\sum_{\mathbf{i}_{1:k}}\sum_{\omega\in\mathcal{C}(\mathbf{i}_{1:k})}\prod_{t(e)=A}A_{e}\prod_{t(e)=B}\sigma_{e^{-}}\sigma_{e^{+}}\Big{)}^{2}\right]$
$\displaystyle=\mathbb{E}_{\lambda,\mu}\left[\frac{1}{n^{l}}\Big{(}\sum_{\mathbf{i}_{1:k}}\sum_{\omega\in\mathcal{C}(\mathbf{i}_{1:k})}\prod_{t(e)=A}A_{e}\prod_{t(e)=B}\sigma_{e^{-}}\sigma_{e^{+}}\Big{)}\right]^{2}+o(1).$

This turns out to be true because of the same argument for Lemma 1
(specifically the discussion after (Proof:)). This completes the proof.

∎

##  4 Weak Recovery under the Threshold

In the remaining two sections, we will prove Theorem 2. In this section, we
show the first part, that weak recovery is impossible when
$\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$. We follow the general proof scheme in
[7]. The proof is information theoretic, and the main idea is contained in the
following proposition.

######  Proposition 3.

When $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$, then for any fixed $r$, and any
two configurations
$(\sigma_{1},...,\sigma_{r}),(\tau_{1},...,\tau_{r})\in\\{\pm 1\\}^{r}$, we
have that as $n\to\infty$,

$\displaystyle\lVert\mathbb{P}_{\lambda,\mu}(\cdot\mid\sigma_{1:r})-\mathbb{P}_{\lambda,\mu}(\cdot\mid\tau_{1:r})\rVert_{\mathrm{TV}}\to
0.$

  * Proof:

The idea is to bound the total variation with a function of the second moment
of the likelihood ratios,

$\displaystyle
L_{\sigma,n}=\frac{\mathrm{d}\mathbb{P}_{\lambda,\mu}}{\mathrm{d}\mathbb{P}_{0,0}}(\cdot\mid\sigma_{1:r})\
,\
L_{\tau,n}=\frac{\mathrm{d}\mathbb{P}_{\lambda,\mu}}{\mathrm{d}\mathbb{P}_{0,0}}(\cdot\mid\tau_{1:r}),$

and then noting that because $r$ is fixed, the second moments of these
likelihood ratios will converge to a limit independent of $\sigma_{1:r}$ and
$\tau_{1:r}$, making the upper bound converge to $0$. However, as we have seen
in the other arguments, we need some truncation. Let us define the truncated
likelihood ratios

$\displaystyle\tilde{L}_{\sigma,n}$
$\displaystyle=\frac{\mathbb{E}_{\sigma_{-r},u}\left[\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\sigma_{1:r},\sigma_{-r},u\right)\mathbf{1}(u\in\mathcal{S})\right]}{\mathbb{P}_{0,0}\left(\mathbf{A},\mathbf{B}\right)}$
$\displaystyle\tilde{L}_{\tau,n}$
$\displaystyle=\frac{\mathbb{E}_{\tau_{-r},u}\left[\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\tau_{1:r},\tau_{-r},u\right)\mathbf{1}(u\in\mathcal{S})\right]}{\mathbb{P}_{0,0}\left(\mathbf{A},\mathbf{B}\right)},$

where $\sigma_{-r},\tau_{-r}\in\\{\pm 1\\}^{n-r}$ are the other coordinates,
and $\mathcal{S}=\\{\lVert u\rVert\leq 2\sqrt{p}\\}$. Define distributions
given by these truncated likelihood ratios:

$\displaystyle\mathbb{Q}_{\sigma,n}(\Omega\mid\sigma_{1:r})$
$\displaystyle=\frac{1}{\mathbb{P}_{n}\left(\mathcal{S}\right)}\mathbb{E}_{0,0}\left[\tilde{L}_{\sigma,n}\operatorname{\mathbbm{1}}(\Omega)\mid\sigma_{1:r}\right]$
$\displaystyle\mathbb{Q}_{\tau,n}(\Omega\mid\tau_{1:r})$
$\displaystyle=\frac{1}{\mathbb{P}_{n}\left(\mathcal{S}\right)}\mathbb{E}_{0,0}\left[\tilde{L}_{\tau,n}\operatorname{\mathbbm{1}}(\Omega)\mid\tau_{1:r}\right].$

From the proof of [8, Proposition 1], we know that
$\lVert\mathbb{P}_{\lambda,\mu}\left(\cdot\mid\sigma_{1:r}\right)-\mathbb{Q}_{\sigma,n}(\cdot\mid\sigma_{1:r})\rVert_{\mathrm{TV}}$
and
$\lVert\mathbb{P}_{\lambda,\mu}\left(\cdot\mid\tau_{1:r}\right)-\mathbb{Q}_{\tau,n}(\cdot\mid\tau_{1:r})\rVert_{\mathrm{TV}}$
both vanish as $n\to\infty$. Thus, to prove the proposition, it suffices to
check that
$\lVert\mathbb{Q}_{\sigma,n}(\cdot\mid\sigma_{1:r})-\mathbb{Q}_{\tau,n}(\cdot\mid\tau_{1:r})\rVert_{\mathrm{TV}}\to
0$. Note that

$\displaystyle\lVert\mathbb{Q}_{\sigma,n}(\cdot\mid\sigma_{1:r})-\mathbb{Q}_{\tau,n}(\cdot\mid\tau_{1:r})\rVert_{TV}=\frac{1}{\mathbb{P}_{n}\left(\mathcal{S}\right)}\mathbb{E}_{0,0}\left[|\tilde{L}_{\sigma,n}-\tilde{L}_{\tau,n}|\right]\leq\frac{1}{\mathbb{P}_{n}\left(\mathcal{S}\right)}\mathbb{E}_{0,0}\left[(\tilde{L}_{\sigma,n}-\tilde{L}_{\tau,n})^{2}\right]^{\frac{1}{2}},$

where we have used the Cauchy Schwarz inequality. Now, we have,

$\displaystyle\mathbb{E}_{0,0}\left[(\tilde{L}_{\sigma,n}-\tilde{L}_{\tau,n})^{2}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{0,0}\bigg{[}\frac{1}{\mathbb{P}_{0,0}\left(\mathbf{A},\mathbf{B}\right)^{2}}\operatorname{\mathbb{E}}_{\sigma_{-r},\tau_{-r},u,v}\Big{\\{}\big{(}\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\sigma_{1:r},\sigma_{-r},u\right)\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\sigma_{1:r},\tau_{-r},v\right)$
$\displaystyle\ \ \ \ \ \ \ \
+\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\tau_{1:r},\sigma_{-r},u\right)\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\tau_{1:r},\tau_{-r},v\right)$
$\displaystyle\ \ \ \ \ \ \ \
-2\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\sigma_{1:r},\sigma_{-r},u\right)\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\tau_{1:r},\tau_{-r},v\right)\big{)}\mathbf{1}(u,v\in\mathcal{S})\Big{\\}}\bigg{]}.$

Thus we just have to prove that the quantity

$\displaystyle\mathbb{E}_{0,0}\left[\frac{\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\sigma_{1:r},\sigma_{-r},u\right)\mathbb{P}_{\lambda,\mu}\left(\mathbf{A},\mathbf{B}\mid\tau_{1:r},\tau_{-r},v\right)}{\mathbb{P}_{0,0}\left(\mathbf{A},\mathbf{B}\right)^{2}}\mathbf{1}(u,v\in\mathcal{S})\right]$

has a limit which is independent of $\sigma_{1:r}$ and $\tau_{1:r}$. But we
know that this is true because of the second moment calculations in Section 2,
so we are done. ∎

Then the impossibility of reconstruction follows from some technical
calculations. The proof of the next two results follow directly from
Proposition 6.2 and Theorem 2.2 of [7] respectively.

######  Proposition 4.

Let $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$. Let $S\subset[n]$ be such that
$|S|=r$, with $r$ finite and fixed, and let $u\in[n]$ be a single index such
that $u\not\in S$. Then, as $n\to\infty$, we have that

$\displaystyle\mathbb{E}_{\lambda,\mu}[\lVert\mathbb{P}_{\lambda,\mu}(\sigma_{u}\mid\mathbf{A},\mathbf{B},\sigma_{S})-\mathbb{P}_{0,0}(\sigma_{u})\rVert_{\mathrm{TV}}\mid\sigma_{S}]\to
0.$

######  Theorem 4.

If $\lambda^{2}+\frac{\mu^{2}}{\gamma}<1$, then reconstruction is impossible,
i.e. let the overlap be defined as

$\displaystyle
ov(\sigma,\tau)=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\tau_{i}-\left(\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\right)\left(\frac{1}{n}\sum_{i=1}^{n}\tau_{i}\right),$

then for any estimator $\hat{\sigma}(\mathbf{A},\mathbf{B})\in\\{\pm
1\\}^{n}$, we have that

$\displaystyle ov(\sigma,\hat{\sigma})\overset{p}{\to}0.$

Because $\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\overset{p}{\to}0$, and
$\frac{1}{n}\sum_{i=1}^{n}\hat{\sigma}_{i}$ is bounded, we see that
$\frac{1}{n}\langle\sigma,\hat{\sigma}\rangle\overset{P}{\to}0$, so weak
recovery is impossible.

##  5 Weak Recovery with Self Avoiding Walks

In this section we finish the proof of Theorem 2, by showing that weak
recovery is possible whenever $\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$. Because
weak recovery is possible as soon as either $\lambda^{2}>1$ [34, 32] or
$\frac{\mu^{2}}{\gamma}>1$ [5], we only need to consider the case that
$\lambda^{2}$, $\frac{\mu^{2}}{\gamma}<1$. We will construct an estimator
$\hat{\sigma}$ that is computable in quasi-polynomial time. We use a strategy
introduced in [23] in the context of community detection in the block model.
Under this approach, one seeks to design an appropriate set of “low-degree"
polynomials in the data $(\mathbf{A},\mathbf{B})$, and recover the signals
based on these polynomials. We note that in the specific context of community
detection, this approach was already latent in the approach of [32] and [11],
based on self-avoiding/non-backtracking walks.

We seek to calculate a polynomial $P(\mathbf{A},\mathbf{B})$, which estimates
$\sigma\sigma^{\mathrm{T}}$. Formally, suppose we had an estimator satisfying

$\displaystyle\mathbb{E}_{\lambda,\mu}\Big{[}\langle
P(\mathbf{A},\mathbf{B}),\sigma\sigma^{\mathrm{T}}\rangle\Big{]}\geq\delta\mathbb{E}_{\lambda,\mu}\Big{[}\|P(\mathbf{A},\mathbf{B})\|_{F}^{2}\Big{]}^{\frac{1}{2}}$
(12)

for some universal constant $\delta>0$. Then [23, Theorem 1] implies that
there exists $\delta^{\prime}=\delta^{\prime}(\delta)$, and an estimator
$\hat{\sigma}$ such that

$\displaystyle\frac{1}{n^{2}}\mathbb{E}_{\lambda,\mu}[\langle\sigma,\hat{\sigma}\rangle^{2}]\geq\delta^{\prime}.$

This ensures weak recovery in our setting. To construct the estimator
$\hat{\sigma}$, from the matrix $P(\mathbf{A},\mathbf{B})$ constructed above,
we compute a matrix $\Sigma$ with minimum Frobenius norm that satisfies the
following constraints:

$\displaystyle\operatorname{diag}(\Sigma)$
$\displaystyle=\operatorname{\mathbbm{1}}$ $\displaystyle\frac{\langle
P(\mathbf{A},\mathbf{B}),\Sigma\rangle}{\lVert
P(\mathbf{A},\mathbf{B})\rVert_{F}\cdot n}$ $\displaystyle\geq\delta^{\prime}$
$\displaystyle\Sigma$ $\displaystyle\succeq 0$

and then output the vector $\hat{\sigma}\in\\{\pm 1\\}^{n}$ obtained by taking
coordinate-wise signs of a centered Gaussian vector with covariance $\Sigma$.

######  Lemma 2.

The estimator $\hat{\sigma}$ achieves weak recovery whenever
$\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$.

  * Proof:

The proof of weak recovery follows immediately from the proof of [23, Lemma
3.5]. ∎

######  Remark 1.

This estimator takes $n^{O(\log n)/\text{poly}(\delta)}$ time to compute, as
we use certain Self Avoiding Walks (SAWs) of length $\Theta(\log n)$. The
running time can be improved to $n^{\text{poly}(1/\delta)}$ by the idea of
color coding, and more discussions on this improvement can be found in [23,
Section 2.5].

In the remainder of the section, we will construct an estimator and establish
(12).

###  5.1 Self Avoiding Walks

It remains to construct the polynomial $P(\mathbf{A},\mathbf{B})$. To this
end, we will use self avoiding walks on the underlying factor-graph. First,
for $i_{1},i_{2}\in[n]$ and $j\in[p]$, we define

$\displaystyle\hat{A}_{i_{1},i_{2}}$
$\displaystyle=\frac{2n}{a-b}\Big{(}A_{ij}-\frac{a+b}{2n}\Big{)},$
$\displaystyle\hat{B}^{j}_{i_{1},i_{2}}$
$\displaystyle=\frac{n}{\mu}B_{i_{1},j}B_{i_{2},j}=\frac{n}{\mu}\Big{(}\sqrt{\frac{\mu}{n}}\sigma_{i_{1}}u_{j}+Z_{i_{1},j}\Big{)}\Big{(}\sqrt{\frac{\mu}{n}}\sigma_{i_{2}}u_{j}+Z_{i_{2},j}\Big{)}.$
(13)

Direct computation yields that

$\displaystyle\mathbb{E}_{\lambda,\mu}[\hat{A}_{i_{1},i_{2}}|\sigma]=\sigma_{i_{1}}\sigma_{i_{2}},\,\,\,\,\mathrm{Var}_{\lambda,\mu}(A_{i_{1},i_{2}})=\frac{n}{\lambda^{2}},$
$\displaystyle\mathbb{E}_{\lambda,\mu}[\hat{B}^{j}_{i_{1},i_{2}}|\sigma]=\sigma_{i_{1}}\sigma_{i_{2}},\,\,\,\,\mathrm{Var}_{\lambda,\mu}(\hat{B}^{j}_{i_{1},i_{2}})=\frac{np}{\mu^{2}/\gamma}.$

Recall the factor graph, as shown in Figure 1. For $i_{1},i_{2}\in[n]$, we
will associate the weight $\hat{A}_{i_{1},i_{2}}$ to the $A$ edge
$\\{i_{1},i_{2}\\}$. Similarly, for $j\in[p]$, we associate the weight
$\hat{B}^{j}_{i_{1}}=\sqrt{\frac{\mu}{n}}B_{i_{1},j}$ to the $B$ edge
$\\{i_{1},j\\}$, and the weight $\hat{B}^{j}_{i_{1},i_{2}}$ to the $B$ wedge
$\\{i_{1},j,i_{2}\\}$.

Fix $i_{1},i_{2}\in[n]$, and let $k\geq l\geq 1$ be integers that we will
specify later. Consider a path $\alpha$ on the factor graph that starts at
$i_{1}$ and ends at $i_{2}$, which contains $k-l$ $A$ type edges, and $l$ $B$
type wedges. We will require that the $A$-type edges on the path are “self-
avoiding", i.e., no edge of type $A$ occurs more than once. Further, if
$j_{1},\cdots,j_{l}$ denote the vertices in $V_{2}$ which lie on the path
$\alpha$, we will require that these vertices are distinct. Let
$\mathcal{L}(i_{1},i_{2},k,l)$ denote the set of all such paths $\alpha$, for
any given $i_{1},i_{2}\in[n]$, and $k\geq l$. Given any path $\alpha$,
construct a polynomial on entries of $(\mathbf{A},\mathbf{B})$ by

$\displaystyle p_{\alpha}=\prod_{e\in\alpha}\mathrm{weight}(e),$

where $\mathrm{weight}(i_{1},i_{2})$ is $\hat{A}_{i_{1},i_{2}}$ and
$\hat{B}^{j}_{i_{1}.i_{2}}$ when the edge $(i_{2},i_{2})$ is of type $A$ and
$B$ respectively. Direct computation yields that

$\displaystyle\mathbb{E}_{\lambda,\mu}[p_{\alpha}|\sigma]=\sigma_{i_{1}}\sigma_{i_{2}},\,\,\,\,\,\mathrm{Var}_{\lambda,\mu}(p_{\alpha})=\Big{(}\frac{n}{\lambda^{2}}\Big{)}^{k-l}\Big{(}\frac{np}{\mu^{2}/\gamma}\Big{)}^{l}(1+o(1)).$
(14)

Thus we see that $p_{\alpha}$ is an unbiased estimator for
$\sigma_{i_{1}}\sigma_{i_{2}}$, but its large variance renders it useless on
its own. Fortunately, there are many paths
$\alpha\in\mathcal{L}(i_{1},i_{2},k,l)$, and we might hope that we can reduce
the variance by averaging over polynomials from different paths as follows

$\displaystyle
P_{i_{1},i_{2}}(\mathbf{A},\mathbf{B})=\frac{1}{|\mathcal{L}(i_{1},i_{2},k,l)|}\sum_{\mathcal{L}(i_{1},i_{2},k,l)}p_{\alpha}.$

Note that $P_{i_{1},i_{2}}$ is still an unbiased estimator for
$\sigma_{i_{1}}\sigma_{i_{2}}$. Finally, we set
$P(\mathbf{A},\mathbf{B})=\\{P_{i_{1},i_{2}}(\mathbf{A},\mathbf{B}):1\leq
i_{1}<i_{2}\leq n\\}$ to be the estimator for the matrix
$\sigma\sigma^{\top}$.

It remains to check (12) whenever $\lambda^{2}+\frac{\mu^{2}}{\gamma}>1$. We
establish this in the next lemma.

######  Lemma 3.

Assume $d>1$ and $\lambda^{2}+\frac{\mu^{2}}{\gamma}>1+\varepsilon$, for some
$\varepsilon>0$. Then there exists universal constants $C>0$ and $c>0$ such
that setting $k=C\log n/\varepsilon^{c}$ and $l:=l(k,\lambda,\mu,\gamma)\leq
k$ such that

$\displaystyle\mathbb{E}_{\lambda,\mu}\Big{[}\langle
P(\mathbf{A},\mathbf{B}),\sigma\sigma^{\mathrm{T}}\rangle\Big{]}\geq\delta\mathbb{E}_{\lambda,\mu}\Big{[}\|P(\mathbf{A},\mathbf{B})\|_{F}^{2}\Big{]}^{\frac{1}{2}}$
(15)

for some $\delta:=\delta(\varepsilon,C,c,\lambda,\mu,\gamma)>0$.

To prove this lemma, we will show that an entry-wise version holds:

$\displaystyle\mathbb{E}_{\lambda,\mu}\Big{[}P_{i_{1},i_{2}}(\mathbf{A},\mathbf{B})\cdot\sigma_{i_{1}}\sigma_{i_{2}}\Big{]}\geq\delta\mathbb{E}_{\lambda,\mu}\Big{[}P_{i_{1},i_{2}}(\mathbf{A},\mathbf{B})^{2}\Big{]}^{\frac{1}{2}}.$
(16)

By construction, we have that
$\mathbb{E}_{\lambda,\mu}[P_{i_{1},i_{2}}(\mathbf{A},\mathbf{B})\ \mid\
\sigma_{i_{1}}\sigma_{i_{2}}]=\sigma_{i_{1}}\sigma_{i_{2}}$. As a result, it
is easy to check that (16) is implied by the following:

$\displaystyle\mathbb{E}_{\lambda,\mu}[(\sigma_{i_{1}}\sigma_{i_{2}})^{2}]\cdot\sum_{\alpha,\beta\in\mathcal{L}(i_{1},i_{2},k,l)}\mathbb{E}_{\lambda,\mu}[p_{\alpha}\cdot
p_{\beta}]\leq\frac{1}{\delta^{2}}\cdot\sum_{\alpha,\beta\in\mathcal{L}(i_{1},i_{2},k,l)}\mathbb{E}_{\lambda,\mu}[p_{\alpha}\cdot(\sigma_{i_{1}}\sigma_{i_{2}})]\mathbb{E}_{\lambda,\mu}[p_{\beta}\cdot(\sigma_{i_{1}}\sigma_{i_{2}})].$
(17)

Intuitively, this inequality is saying that the correlation between different
self avoiding walks is not too large. The right hand side of the inequality is
easy to control: note that
$\mathbb{E}_{\lambda,\mu}[p_{\alpha}\cdot(\sigma_{i_{1}}\sigma_{i_{2}})]=\mathbb{E}_{\lambda,\mu}[(\sigma_{i_{1}}\sigma_{i_{2}})^{2}]=1$,
so the right hand side is equal to $\delta|\mathcal{L}(i_{1},i_{2},k,l)|^{2}$.
We see that this is given by

$\displaystyle|\mathcal{L}(i_{1},i_{2},k,l)|^{2}=(1+o(1))\binom{k}{l}^{2}n^{2(k-1)}p^{2l}.$
(18)

Thus we are left to control correlation between $p_{\alpha}$ and $p_{\beta}$,
given on the left hand side of (17).

###  5.2 Correlation of SAWs: Proof of (17)

We want an upper bound on the left hand side of (17), so we need to control
the correlation $\mathbb{E}\left[p_{\alpha}p_{\beta}\right]$, for paths
$\alpha,\beta\in\mathcal{L}(i_{1},i_{2},k,l)$. For this, we have to keep track
of the number of intersections. Let $\tilde{a}$ be the number of
$\hat{A}$-edge intersections, and $\tilde{b}$ be the number of $\hat{B}$-edge
intersections. In particular, we must have $\tilde{a}\leq k-l$, and
$\tilde{b}\leq l$.

Note that the contribution to correlation depends only on how many
intersections there are, and does not depend on the other edges of $\alpha$
and $\beta$. Computations show that each $\hat{A}$-edge intersection
contributes a factor of $O(n/\lambda^{2})$, and each $\hat{B}$-edge
intersection contributes a factor of $O(n/\mu)$, so the total contribution of
such an intersection would simply be

$O(1)\left(\frac{n}{\lambda^{2}}\right)^{\tilde{a}}\left(\frac{n}{\mu}\right)^{\tilde{b}}.$

Now we calculate the number of pairs
$\alpha,\beta\in\mathcal{L}(i_{1},i_{2},k,l)$ that intersect on $\tilde{a}$
$A$ edges and $\tilde{b}$ $B$ edges. First we will calculate the number of
pairs $\alpha$ and $\beta$ that intersect on the smallest number of vertices,
given the number of edge intersections. The smallest numbers of vertex
intersections are $\tilde{a}+\lfloor\tilde{b}/2\rfloor$ $V_{1}$ vertices, and
$\lceil\tilde{b}/2\rceil$ $V_{2}$ vertices. This is achieved when both paths,
$\alpha$ and $\beta$, begin with $k-l$ consecutive $A$ edges, and end with $l$
$B$ wedges, and intersect on the first $\tilde{a}$ $\hat{A}$-edges, as well as
the last $\tilde{b}$ $\hat{B}$-edges. In this case, there are
$2(k-1)-(\tilde{a}+\lfloor\tilde{b}/2\rfloor)$ free $V_{1}$ vertices for the
two paths to choose, and $b_{1}+b_{2}-\lceil\tilde{b}/2\rceil$ free $V_{2}$
vertices for the paths to choose, which means that the total number of such
pairs is

$n^{2(k-1)-\tilde{a}-\lfloor\tilde{b}/2\rfloor}p^{2l-\lceil\tilde{b}/2\rfloor}.$

A similar calculation shows that number of pairs of paths that intersects on
the least number of vertices contributes the leading order term. This is
because if two paths intersected on $r$ more vertices, then the total number
of paths will decrease by a factor of $l^{O(r)}n^{-O(r)}$. Thus the total
contribution in the correlation (in (17)) is:

$\displaystyle
O(1)n^{2(k-l-1)-\tilde{a}-\lfloor\tilde{b}/2\rfloor}p^{2l-\lceil\tilde{b}/2\rfloor}\left(\frac{n}{\lambda^{2}}\right)^{\tilde{a}}\left(\frac{n}{\mu}\right)^{\tilde{b}}$
$\displaystyle=O(1)n^{2(k-1)}p^{2l}\left((\lambda^{2})^{-\tilde{a}}\left(\frac{\mu^{2}}{\gamma}\right)^{-\tilde{b}/2}\gamma^{\lceil\tilde{b}/2\rceil-\tilde{b}/2}\right).$

Thus, summing over possible number of intersections, we have that:

$\displaystyle\begin{aligned} &\ \ \ \
\sum_{\alpha,\beta\in\mathcal{L}(i_{1},i_{2},k,l)}\mathbb{E}_{\lambda,\mu}[p_{\alpha}\cdot
p_{\beta}]\\\ &\leq O(1)n^{2(k-1)}p^{2l}\sum_{\tilde{a}\leq
l-m}\sum_{\tilde{b}\leq
2m}\left((\lambda^{2})^{-\tilde{a}}\left(\frac{\mu^{2}}{\gamma}\right)^{-\tilde{b}/2}\gamma^{\lceil\tilde{b}/2\rceil-\tilde{b}/2}\right)\\\
&\leq
O(1)n^{2(k-1)}p^{2l}(\lambda^{2})^{-(k-l)}\left(\frac{\mu^{2}}{\gamma}\right)^{-l}.\end{aligned}$
(19)

Thus, to achieve the bound in (17), we just need to show that (18) really is
an upper bound of (19). That amounts to showing

$\displaystyle\binom{k}{l}^{2}\gtrsim(\lambda^{2})^{-(k-l)}\left(\frac{\mu^{2}}{\gamma}\right)^{-l}.$

Let us now choose
$\frac{l}{k}=\frac{\mu^{2}/\gamma}{\lambda^{2}+\mu^{2}/\gamma}$, and hence
$\frac{k-l}{k}=\frac{\lambda^{2}}{\lambda^{2}+\mu^{2}/\gamma}$. Note that we
are assuming $\lambda^{2}+\mu^{2}/\gamma>1$, so $\lambda^{2}>\frac{k-l}{k}$,
and $\mu^{2}/\gamma>\frac{l}{k}$. As a result, we see that

$\displaystyle\ \ \ \
\binom{k}{l}^{2}=\exp\left(-2l\log\frac{l}{k}-2(k-l)\log\frac{k-l}{k}+o(1)\right)$
$\displaystyle\gtrsim\exp\left(-l\log\frac{\mu^{2}}{\gamma}-(k-l)\log\lambda^{2}\right)=(\lambda^{2})^{-(k-l)}\left(\frac{\mu^{2}}{\gamma}\right)^{-l}$

which is exactly what we wanted to show.

## References

  * [1] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  arXiv preprint arXiv:1703.10146, 2017.
  * [2] Christopher Aicher, Abigail Z Jacobs, and Aaron Clauset.  Learning latent block structure in weighted networks.  Journal of Complex Networks, 3(2):221–248, 2014.
  * [3] Ahmed El Alaoui and Michael I Jordan.  Detection limits in the high-dimensional spiked rectangular model.  arXiv preprint arXiv:1802.07309, 2018.
  * [4] Greg W Anderson and Ofer Zeitouni.  A clt for a band matrix model.  Probability Theory and Related Fields, 134(2):283–338, 2006.
  * [5] Jinho Baik, Gérard Ben Arous, and Sandrine Péché.  Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices.  Annals of Probability, pages 1643–1697, 2005.
  * [6] Ramnath Balasubramanyan and William W Cohen.  Block-lda: Jointly modeling entity-annotated text and entity-entity links.  In Proceedings of the 2011 SIAM International Conference on Data Mining, pages 450–461. SIAM, 2011.
  * [7] Debapratim Banerjee.  Contiguity and non-reconstruction results for planted partition models: the dense case.  Electronic Journal of Probability, 23, 2018.
  * [8] Debapratim Banerjee and Zongming Ma.  Asymptotic normality and analysis of variance of log-likelihood ratios in spiked random matrix models.  arXiv preprint arXiv:1804.00567, 2018.
  * [9] Norbert Binkiewicz, Joshua T Vogelstein, and Karl Rohe.  Covariate-assisted spectral clustering.  Biometrika, 104(2):361–377, 2017.
  * [10] Béla Bollobás, Svante Janson, and Oliver Riordan.  The phase transition in inhomogeneous random graphs.  Random Structures & Algorithms, 31(1):3–122, 2007.
  * [11] Charles Bordenave, Marc Lelarge, and Laurent Massoulié.  Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE, 2015.
  * [12] Cécile Bothorel, Juan David Cruz, Matteo Magnani, and Barbora Micenkova.  Clustering attributed graphs: models, measures and methods.  Network Science, 3(3):408–444, 2015.
  * [13] Jonathan Chang and David M Blei.  Hierarchical relational models for document networks.  The Annals of Applied Statistics, pages 124–150, 2010.
  * [14] Hong Cheng, Yang Zhou, and Jeffrey Xu Yu.  Clustering large attributed graphs: A balance between structural and attribute similarities.  ACM Transactions on Knowledge Discovery from Data (TKDD), 5(2):12, 2011.
  * [15] TA Dang and Emmanuel Viennet.  Community detection based on structural and attribute similarities.  In International conference on digital society (icds), pages 7–12, 2012.
  * [16] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel.  Contextual stochastic block models.  In Advances in Neural Information Processing Systems, pages 8581–8593, 2018.
  * [17] Ahmed El Alaoui, Florent Krzakala, Michael Jordan, et al.  Fundamental limits of detection in the spiked wigner model.  Annals of Statistics, 48(2):863–885, 2020.
  * [18] Jaume Gibert, Ernest Valveny, and Horst Bunke.  Graph embedding in vector spaces by node attribute statistics.  Pattern Recognition, 45(9):3072–3083, 2012.
  * [19] Stephan Gunnemann, Ines Farber, Sebastian Raubach, and Thomas Seidl.  Spectral subspace clustering for graphs with feature vectors.  In Data Mining (ICDM), 2013 IEEE 13th International Conference on, pages 231–240. IEEE, 2013.
  * [20] Tuan-Anh Hoang and Ee-Peng Lim.  On joint modeling of topical communities and personal interest in microblogs.  In International Conference on Social Informatics, pages 1–16. Springer, 2014.
  * [21] Peter D Hoff.  Random effects models for network data.  na, 2003.
  * [22] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social networks, 5(2):109–137, 1983.
  * [23] Samuel B Hopkins and David Steurer.  Efficient bayesian estimation from few samples: community detection and related problems.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 379–390. IEEE, 2017.
  * [24] Svante Janson.  Random regular graphs: Asymptotic distributions and contiguity.  Combinatorics, Probability and Computing, 4(4):369–405, 1995.
  * [25] Svante Janson, Tomasz Luczak, and Andrzej Rucinski.  Random graphs, volume 45.  John Wiley & Sons, 2011.
  * [26] Iain M Johnstone, Alexei Onatski, et al.  Testing in high-dimensional spiked models.  Annals of Statistics, 48(3):1231–1254, 2020.
  * [27] Varun Kanade, Elchanan Mossel, and Tselil Schramm.  Global and local information in clustering labeled block models.  IEEE Transactions on Information Theory, 62(10):5906–5917, 2016\.
  * [28] Myunghwan Kim and Jure Leskovec.  Latent multi-group membership graph model.  arXiv preprint arXiv:1205.4546, 2012.
  * [29] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang.  Spectral redemption in clustering sparse networks.  Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.
  * [30] Marc Lelarge, Laurent Massoulié, and Jiaming Xu.  Reconstruction in the labelled stochastic block model.  IEEE Transactions on Network Science and Engineering, 2(4):152–163, 2015.
  * [31] Jure Leskovec and Julian J Mcauley.  Learning to discover social circles in ego networks.  In Advances in neural information processing systems, pages 539–547, 2012.
  * [32] Laurent Massoulié.  Community detection thresholds and the weak ramanujan property.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 694–703. ACM, 2014.
  * [33] Marc Mezard and Andrea Montanari.  Information, physics, and computation.  Oxford University Press, 2009.
  * [34] Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture.  Combinatorica, pages 1–44, 2013.
  * [35] Elchanan Mossel, Joe Neeman, and Allan Sly.  Reconstruction and estimation in the planted partition model.  Probability Theory and Related Fields, 162(3-4):431–461, 2015.
  * [36] Elchanan Mossel and Jiaming Xu.  Local algorithms for block models with side information.  In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 71–80. ACM, 2016.
  * [37] Jennifer Neville, Micah Adler, and David Jensen.  Clustering relational data using attribute and link information.  In Proceedings of the text mining and link analysis workshop, 18th international joint conference on artificial intelligence, pages 9–15. San Francisco, CA: Morgan Kaufmann Publishers, 2003.
  * [38] Mark EJ Newman and Aaron Clauset.  Structure and inference in annotated networks.  Nature Communications, 7:11863, 2016.
  * [39] Alexei Onatski, Marcelo J Moreira, Marc Hallin, et al.  Asymptotic power of sphericity tests for high-dimensional data.  The Annals of Statistics, 41(3):1204–1231, 2013.
  * [40] Alexei Onatski, Marcelo J Moreira, Marc Hallin, et al.  Signal detection in high dimension: The multispiked case.  The Annals of Statistics, 42(1):225–254, 2014.
  * [41] Amelia Perry, Alexander S Wein, Afonso S Bandeira, Ankur Moitra, et al.  Optimality and sub-optimality of pca i: Spiked random matrix models.  The Annals of Statistics, 46(5):2416–2451, 2018.
  * [42] Robert W. Robinson and Nicholas C. Wormald.  Almost all cubic graphs are hamiltonian.  Random Structures & Algorithms, 3(2):117–125, 1992.
  * [43] Robert W. Robinson and Nicholas C. Wormald.  Almost all regular graphs are hamiltonian.  Random Structures & Algorithms, 5(2):363–374, 1994.
  * [44] Arlei Silva, Wagner Meira Jr, and Mohammed J Zaki.  Mining attribute-structure correlated patterns in large attributed graphs.  Proceedings of the VLDB Endowment, 5(5):466–477, 2012.
  * [45] Laura M Smith, Linhong Zhu, Kristina Lerman, and Allon G Percus.  Partitioning networks with node attributes by compressing information flow.  ACM Transactions on Knowledge Discovery from Data (TKDD), 11(2):15, 2016.
  * [46] Gian-Carlo Wick.  The evaluation of the collision matrix.  Physical review, 80(2):268, 1950.
  * [47] Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng.  A model-based approach to attributed graph clustering.  In Proceedings of the 2012 ACM SIGMOD international conference on management of data, pages 505–516. ACM, 2012.
  * [48] Bowei Yan and Purnamrita Sarkar.  Covariate regularized community detection in sparse graphs.  Journal of the American Statistical Association, pages 1–12, 2020\.
  * [49] Jaewon Yang, Julian McAuley, and Jure Leskovec.  Community detection in networks with node attributes.  In Data Mining (ICDM), 2013 IEEE 13th international conference on, pages 1151–1156. IEEE, 2013.
  * [50] Tianbao Yang, Rong Jin, Yun Chi, and Shenghuo Zhu.  Combining link and content for community detection: a discriminative approach.  In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 927–936. ACM, 2009.
  * [51] Hugo Zanghi, Stevenn Volant, and Christophe Ambroise.  Clustering based on random graph model embedding vertex features.  Pattern Recognition Letters, 31(9):830–836, 2010.
  * [52] Yuan Zhang, Elizaveta Levina, and Ji Zhu.  Community detection in networks with node features.  Electronic Journal of Statistics, 10(2):3153–3178, 2016.
  * [53] Yang Zhou, Hong Cheng, and Jeffrey Xu Yu.  Graph clustering based on structural/attribute similarities.  Proceedings of the VLDB Endowment, 2(1):718–729, 2009.