# Phase transition for detecting a small
community in a large network

Jiashun Jin
Carnegie Mellon University
<EMAIL_ADDRESS>Zheng Tracy Ke
Harvard University
<EMAIL_ADDRESS>

Paxton Turner
Harvard University
<EMAIL_ADDRESS>

Anru R. Zhang
Duke University
<EMAIL_ADDRESS>
###### Abstract

How to detect a small community in a large network is an interesting problem,
including clique detection as a special case, where a naive degree-based
$\chi^{2}$-test was shown to be powerful in the presence of an Erdős-Renyi
background. Using Sinkhorn’s theorem, we show that the signal captured by the
$\chi^{2}$-test may be a modeling artifact, and it may disappear once we
replace the Erdős-Renyi model by a broader network model. We show that the
recent SgnQ test is more appropriate for such a setting. The test is optimal
in detecting communities with sizes comparable to the whole network, but has
never been studied for our setting, which is substantially different and more
challenging. Using a degree-corrected block model (DCBM), we establish phase
transitions of this testing problem concerning the size of the small community
and the edge densities in small and large communities. When the size of the
small community is larger than $\sqrt{n}$, the SgnQ test is optimal for it
attains the computational lower bound (CLB), the information lower bound for
methods allowing polynomial computation time. When the size of the small
community is smaller than $\sqrt{n}$, we establish the parameter regime where
the SgnQ test has full power and make some conjectures of the CLB. We also
study the classical information lower bound (LB) and show that there is always
a gap between the CLB and LB in our range of interest.

###  1 Introduction

Consider an undirected network with $n$ nodes and $K$ communities. We assume
$n$ is large and the network is connected for convenience. We are interested
in testing whether $K=1$ or $K>1$ and the sizes of some of the communities are
much smaller than $n$ (communities are scientifically meaningful but
mathematically hard to define; intuitively, they are clusters of nodes that
have more edges “within” than “across” (Jin, 2015; Zhao et al., 2012)). The
problem is a special case of network global testing, a topic that has received
a lot of attention (e.g., Jin et al. (2018; 2021b)). However, existing works
focused on the so-called balanced case, where the sizes of communities are at
the same order. Our case is severely unbalanced, where the sizes of some
communities are much smaller than $n$ (e.g., $n^{\varepsilon}$).

The problem also includes clique detection (a problem of primary interest in
graph learning (Alon et al., 1998; Ron & Feige, 2010)) as a special case.
Along this line, Arias-Castro & Verzelen (2014); Verzelen & Arias-Castro
(2015) have made remarkable progress. In detail, they considered the problem
of testing whether a graph is generated from a one-parameter Erdős-Renyi model
or a two-parameter model: for any nodes $1\leq i,j\leq n$, the probability
that they have an edge equals $b$ if $i,j$ both are in a small planted subset
and equals $a$ otherwise. A remarkable conclusion of these papers is: a naive
degree-based $\chi^{2}$-test is optimal, provided that the clique size is in a
certain range. Therefore, at first glance, it seems that the problem has been
elegantly solved, at least to some extent.

Unfortunately, recent progress in network testing tells a very different
story: the signal captured by the $\chi^{2}$-test may be a modeling artifact.
It may disappear once we replace the models in Arias-Castro & Verzelen (2014);
Verzelen & Arias-Castro (2015) by a properly broader model. When this happens,
the $\chi^{2}$-test will be asymptotically powerless in the whole range of
parameter space.

We explain the idea with the popular Degree-Corrected Block Model (DCBM)
(Karrer & Newman, 2011), though it is valid in broader settings. Let
$A\in\mathbb{R}^{n,n}$ be the network adjacency matrix, where
$A(i,j)\in\\{0,1\\}$ indicates whether there is an edge between nodes $i$ and
$j$, $1\leq i,j\leq n$. By convention, we do not allow for self-edges, so the
diagonals of $A$ are always 0. Suppose there are $K$ communities, ${\cal
C}_{1},\ldots,{\cal C}_{K}$. For each node $i$, $1\leq i\leq n$, we use a
parameter $\theta_{i}$ to model the degree heterogeneity and $\pi_{i}$ to
model the membership: when $i\in{\cal C}_{k}$, $\pi_{i}(\ell)=1$ if $\ell=k$
and $\pi_{i}(\ell)=0$ otherwise. For a $K\times K$ symmetric and irreducible
non-negative matrix $P$ that models the community structure, DCBM assumes that
the upper triangle of $A$ contains independent Bernoulli random variables
satisfying111In this work we use $M^{\prime}$ to denote the transpose of a
matrix or vector $M$.

$\mathbb{P}(A(i,j)=1)=\theta_{i}\theta_{j}\pi_{i}^{\prime}P\pi_{j},\qquad
1\leq i,j\leq n.$ (1.1)

In practice, we interpret $P(k,\ell)$ as the baseline connecting probability
between communities $k$ and $\ell$. Write
$\theta=(\theta_{1},\theta_{2},\ldots,\theta_{n})^{\prime}$,
$\Pi=[\pi_{1},\pi_{2},\ldots,\pi_{n}]^{\prime}$, and
$\Theta=\mathrm{diag}(\theta)\equiv\mathrm{diag}(\theta_{1},\theta_{2},\ldots,\theta_{n})$.
Introduce $n\times n$ matrices $\Omega$ and $W$ by $\Omega=\Theta\Pi
P\Pi^{\prime}\Theta$ and $W=A-\mathbb{E}[A]$. We can re-write (1.1) as

$A=\Omega-\mathrm{diag}(\Omega)+W.$ (1.2)

We call $\Omega$ the Bernoulli probability matrix and $W$ the noise matrix.
When $\theta_{i}$ in the same community are equal, DCBM reduces to the
Stochastic Block Model (SBM) (Holland et al., 1983). When $K=1$, the SBM
reduces to the Erdős-Renyi model, where $\Omega(i,j)$ take the same value for
all $1\leq i,j\leq n$.

We first describe why the signal captured by the $\chi^{2}$-test in Arias-
Castro & Verzelen (2014); Verzelen & Arias-Castro (2015) is a modeling
artifact. Using Sinkhorn’s matrix scaling theorem (Sinkhorn, 1974), it is
possible to build a null DCBM with $K=1$ that has no community structure and
an alternative DCBM with $K\geq 2$ and clear community structure such that the
two models have the same expected degrees. Thus, we do not expect that degree-
based test such as $\chi^{2}$ can tell them apart. We make this Sinkhorn
argument precise in Section 2.1 and show the failure of $\chi^{2}$ in Theorem
2.3.

In the Erdős-Renyi setting in Arias-Castro & Verzelen (2014), the null has one
parameter and the alternative has two parameters. In such a setting, we cannot
have degree-matching. In these cases, a naive degree-based $\chi^{2}$-test may
have good power, but it is due to the very specific models they choose. For
clique detection in more realistic settings, we prefer to use a broader model
such as the DCBM, where by the degree-matching argument above, the
$\chi^{2}$-test is asymptotically powerless.

This motivates us to look for a different test. One candidate is the scan
statistic Bogerd et al. (2021). However, a scan statistic is only
computationally feasible when each time we scan a very small subset of nodes.
For example, if each time we only scan a finite number of nodes, then the
computational cost is polynomial; we call the test the Economic Scan Test
(EST). Another candidate may come from the Signed-Polygon test family (Jin et
al., 2021b), including the Signed-Quadrilateral (SgnQ) as a special case. Let
$\hat{\eta}=({\bf 1}_{n}A{\bf 1}_{n})^{-1/2}A{\bf 1}_{n}$ and
$\widehat{A}=A-\hat{\eta}\hat{\eta}$. Define
$Q_{n}=\sum_{i_{1},i_{2},i_{3},i_{4}(dist)}\widehat{A}_{i_{1}i_{2}}\widehat{A}_{i_{2}i_{3}}\widehat{A}_{i_{3}i_{4}}\widehat{A}_{i_{4}i_{1}}$
where the shorthand $(dist)$ indicates we sum over distinct indices. The SgnQ
test statistic is

$\psi_{n}=\bigl{[}Q_{n}-2(\|\hat{\eta}\|^{2}-1)^{2}\bigr{]}/\sqrt{8(\|\hat{\eta}\|^{2}-1)^{4}}.$
(1.3)

SgnQ is computationally attractive because it can be evaluated in time
$O(n^{2}\bar{d})$, where $\bar{d}$ is the average degree of the network (Jin
et al., 2021b).

Moreover, it was shown in Jin et al. (2021b) that (a) when $K=1$ (the null
case), $\psi_{n}\rightarrow N(0,1)$, and (b) when $K>1$ and all communities
are at the same order (i.e., a balanced alternative case), the SgnQ test
achieves the classical information lower bound (LB) for global testing and so
is optimal. Unfortunately, our case is much more delicate: the signal of
interest is contained in a community with a size that is much smaller than $n$
(e.g., $n^{\varepsilon}$), so the signal can be easily overshadowed by the
noise term of $Q_{n}$. Even in the simple alternative case where we only have
two communities (with sizes $N$ and $(n-N)$), it is unclear (a) how the lower
bounds vary as $N/n\rightarrow 0$, and especially whether there is a gap
between the computation lower bound (CLB) and classical information lower
bound (LB), and (b) to what extent the SgnQ test attains the CLB and so is
optimal.

####  1.1 Results and contributions

We consider the problem of detecting a small community in the DCBM. In this
work, we specifically focus on the case $K=2$ as this problem already displays
a rich set of phase transitions, and we believe it captures the essential
behavior for constant $K>1$. Let $N\ll n$ denote the size of this small
community under the alternative. Our first contribution analyzes the power of
SgnQ for this problem, extending results of Jin et al. (2021b) that focus on
the balanced case. Let $\lambda_{1}=\lambda_{1}(\Omega)$. In Section 2.2, we
define a population counterpart $\tilde{\Omega}$ of $\hat{A}$ and let
$\widetilde{\lambda}=\lambda_{1}(\tilde{\Omega})$. We show that SgnQ has full
power if $\widetilde{\lambda}_{1}/\sqrt{\lambda_{2}}\to\infty$, which reduces
to $N(a-c)/\sqrt{nc}\to\infty$ in the SBM case.

For optimality, we obtain a computational lower bound (CLB), relying on the
low-degree polynomial conjecture, which is a standard approach in studying CLB
(e.g., Kunisky et al. (2019)). Consider a case where $K=2$ and we have a small
community with size $N$. Suppose the edge probability within the community and
outside the community are $a$ and $c$, where $a>c$. The quantity
$(a-c)/\sqrt{c}$ acts as the Node-wise Signal-to-Noise Ratio (SNR) for the
detection problem.222Note that the node-wise SNR captures the ratio of the
mean difference and standard deviation of Bernoulli($a$) versus
Bernoulli($c$), which motivates our terminology. When $N\gg\sqrt{n}$, we find
that the CLB is completely determined by $N$ and node-wise SNR; moreover, SgnQ
matches with the CLB and is optimal. When $N\ll\sqrt{n}$, the situation is
more subtle: if the node-wise SNR $(a-c)/\sqrt{c}\rightarrow 0$ (weak signal
case), we show the problem is computationally hard and the LB depends on $N$
and the node-wise SNR. If $(a-c)/\sqrt{c}\gg n^{1/2}$ (strong signal case),
then SgnQ solves the detection problem. In the range $1\ll(a-c)/\sqrt{c}\ll
n^{1/2}$ (moderate signal case), the CLB depends on not only $N$ and the node-
wise SNR but also the background edge density $c$. In this regime, we make
conjectures of the CLB, from the study of the aforementioned economic scan
test (EST). Our results are summarized in Figure 1 and explained in full
detail in Section 2.7.

Figure 1: Phase diagram ($(a-c)/\sqrt{c}=n^{-\gamma}$ and $N=n^{1-\beta}$).

We also obtain the classical information lower bound (LB), and discover that
as $N/n\rightarrow 0$, there is big gap between CLB and LB. Notably the LB is
achieved by an (inefficient) signed scan test. In the balanced case in Jin et
al. (2021b), the SgnQ test is optimal among all tests (even those that are
allowed unbounded computation time), and such a gap does not exist.

We also show that that the naive degree-based $\chi^{2}$-test is
asymptotically powerless due to the aforementioned degree-matching phenomenon.

Our statistical lower bound, computational lower bound, and the powerlessness
of $\chi^{2}$ based on degree-matching are also valid for all $K>2$ since any
model with $K\geq 2$ contains $K=2$ as a special case. We also expect that our
lower bounds are tight for these broader models and that our lower bound
constructions for $K=2$ represent the least favorable cases when community
sizes are severely unbalanced.

Compared to Verzelen & Arias-Castro (2015); Arias-Castro & Verzelen (2014), we
consider network global testing in a more realistic setting, and show that
optimal tests there (i.e., a naive degree-based $\chi^{2}$ test) may be
asymptotically powerless here. Compared with Bogerd et al. (2021), our setting
is very different (they considered a setting where both the null and
alternative are DCBM with $K=1$). Compared to the study in the balanced case
(e.g., Jin et al. (2018; 2021b); Gao & Lafferty (2017)), our study is more
challenging for two reasons. First, in the balanced case, there is no gap
between the UB (the upper bound provided by the SgnQ test) and LB, so there is
no need to derive the CLB, which is usually technical demanding. Second, the
size of the smaller community can get as small as $n^{\varepsilon}$, where
$\varepsilon>0$ is any constant. Due this imbalance in community sizes, the
techniques of Jin et al. (2021b) do not directly apply. As a result, our proof
involves the careful study of the $256$ terms that compose SgnQ, which
requires using bounds tailored specifically for the severely unbalanced case.

Our study of the CLB is connected to that of Hajek et al. (2015) in the Erdös-
Renyi setting of Arias-Castro & Verzelen (2014). Hajek et al. (2015) proved
via computational reducibility that the naive $\chi^{2}$-test is the optimal
polynomial-time test (conditionally on the planted clique hypothesis). We also
note work of Chen & Xu (2016) that studied a $K$-cluster generalization of the
Erdös-Renyi model of Arias-Castro & Verzelen (2014); Verzelen & Arias-Castro
(2015) and provided conjectures of the CLB. Compared to our setting, these
models are very different because the expected degree profiles of the null and
alternative differ significantly. In this work we consider the DCBM model,
where due to the subtle phenomenon of degree matching between the null and
alternative hypotheses, both CLB and LB are different from those obtained by
Hajek et al. (2015).

Notations: We use ${\bf 1}_{n}$ to denote a $n$-dimensional vector of ones.
For a vector $\theta=(\theta_{1},\ldots,\theta_{n})$, $\mathrm{diag}(\theta)$
is the diagonal matrix where the $i$-th diagonal entry is $\theta_{i}$. For a
matrix $\Omega\in\mathbb{R}^{n\times n}$, $\mathrm{diag}(\Omega)$ is the
diagonal matrix where the $i$-th diagonal entry is $\Omega(i,i)$. For a vector
$\theta\in\mathbb{R}^{n}$,
$\theta_{max}=\max\\{\theta_{1},\ldots,\theta_{n}\\}$ and
$\theta_{min}=\min\\{\theta_{1},\ldots,\theta_{n}\\}$. For two positive
sequences $\\{a_{n}\\}$ and $\\{b_{n}\\}$, we write $a_{n}\asymp b_{n}$ if
$c_{1}\leq a_{n}/b_{n}\leq c_{2}$ for constants $c_{2}>c_{1}>0$. We say
$a_{n}\sim b_{n}$ if $(a_{n}/b_{n})=1+o(1)$.

###  2 Main results

In Section 2.1, following our discussion on Sinkhorn’s theorem in Section 1,
we introduce calibrations (including conditions on identifiability and
balance) that are appropriate for severely unbalanced DCBM and illustrate with
some examples. In Sections 2.2-2.3, we analyze the power of the SgnQ test and
compare it with the $\chi^{2}$-test. In Sections 2.4-2.5, we discuss the
information lower bounds (both the LB and CLB) and show that SgnQ test is
optimal among polynomial time tests, when $N\gg\sqrt{n}$. In Section 2.6, we
study the EST and make some conjectures of the CLB when $N\ll\sqrt{n}$. In
Section 2.7, we summarize our results and present the phase transitions.

####  2.1 DCBM for severely unbalanced networks: identifiability, balance
metrics, and global testing

In the DCBM (1.1)-(1.2), $\Omega=\Theta\Pi P\Pi^{\prime}\Theta$. It is known
that the matrices $(\Theta,\Pi,P)$ are not identifiable. One issue is that
$(\Pi,P)$ are only unique up to a permutation: for a $K\times K$ permutation
matrix $Q$, $\Pi P\Pi=(\Pi Q)(Q^{\prime}PQ)(\Pi Q)^{\prime}$. This issue is
easily fixable in applications so is usually neglected. A bigger issue is
that, $(\Theta,P)$ are not uniquely defined. For example, fixing a positive
diagonal matrix $D\in\mathbb{R}^{K\times K}$, let $P^{*}=DPD$ and
$\Theta^{*}=\mathrm{diag}(\theta_{1}^{*},\theta_{2}^{*},\ldots,\theta_{n}^{*})$
where $\theta_{i}^{*}=\theta_{i}/\sqrt{D(k,k)}$ if $i\in{\cal C}_{k}$, $1\leq
k\leq K$. It is seen that $\Theta\Pi P\Pi^{\prime}\Theta=\Theta^{*}\Pi
P^{*}\Pi^{\prime}\Theta^{*}$, so $(\Theta,P)$ are not uniquely defined.

To motivate our identifiability condition, we formalize the degree-matching
argument discussed in the introduction. Fix $(\theta,P)$ and let
$h=(h_{1},\ldots,h_{K})^{\prime}$ and $h_{k}>0$ is the fraction of nodes in
community $k$, $1\leq k\leq K$. By the main result of Sinkhorn (1974), there
is a unique positive diagonal matrix $D=\mathrm{diag}(d_{1},\ldots,d_{K})$
such that $DPDh={\bf 1}_{K}$. Consider a pair of two DCBM, a null with $K=1$
and an alternative with $K>1$, with parameters $\Omega=\Theta{\bf 1}_{n}{\bf
1}_{n}^{\prime}\Theta\equiv\theta\theta^{\prime}$ and
$\Omega^{*}(i,j)=\theta_{i}^{*}\theta_{j}^{*}\pi_{i}^{\prime}P\pi_{j}$ with
$\theta_{i}^{*}=d_{k}\theta_{i}$ if $i\in{\cal C}_{k}$, $1\leq k\leq K$,
respectively. Direct calculation shows that node $i$ has the same expected
degree under the null and alternative.

There are many ways to resolve the issue. For example, in the balanced case
(e.g., Jin et al. (2021b; 2022)), we can resolve it by requiring that $P$ has
unit diagonals. However, for our case, this is inappropriate. Recall that, in
practice, $P(k,\ell)$ represents as the baseline connecting probability
between community $k$ and $\ell$. If we forcefully rescale $P$ to have a unit
diagonal here, both $(P,\Theta)$ lose their practical meanings.

Motivated by the degree-matching argument, we propose an identifiability
condition that is more appropriate for the severely unbalanced DCBM. By our
discussion in Section 1, for any DCBM with a Bernoulli probability matrix
$\Omega$, we can always use Sinkhorn’s theorem to define $(\Theta,P)$ (while
$\Pi$ is unchanged) such that for the new $(\Theta,P)$, $\Theta=\Theta\Pi
P\Pi^{\prime}\Theta$ and $Ph\propto{\bf 1}_{K}$, where
$h=(h_{1},\ldots,h_{K})^{\prime}$ and $h_{k}>0$ is the fraction of nodes in
community $k$, $1\leq k\leq K$. This motivates the following identifiability
condition (which is more appropriate for our case):

$\|\theta\|_{1}=n,\qquad Ph\propto{\bf 1}_{K},\quad\mbox{where $h_{k}$ is
fraction of nodes in ${\cal C}_{k}$, $1\leq k\leq K$}.$ (2.1)

######  Lemma 2.1.

For any $\Omega$ that satisfies the DCBM (1.2) and has positive diagonal
elements, we can always find $(\Theta,\Pi,P)$ such that $\Omega=\Theta\Pi
P\Pi^{\prime}\Theta$ and (2.1) holds. Also, any $(\Theta,P)$ that satisfy
$\Omega=\Theta\Pi P\Pi^{\prime}\Theta$ and (2.1) are unique.

Moreover, for network balance, the following two vectors in $\mathbb{R}^{K}$
are natural metrics:

$d=(\|\theta\|_{1})^{-1}\Pi^{\prime}\Theta{\bf 1}_{n},\qquad
g=(\|\theta\|)^{-2}\Pi^{\prime}\Theta^{2}\Pi{\bf 1}_{K},$ (2.2)

In the balanced case (e.g., Jin et al. (2021b; 2022)), we usually assume the
entries of $d$ and $g$ are at the same order. For our setting, this is not the
case.

Next we introduce the null and alternative hypotheses that we consider. Under
each hypothesis, we impose the identifiability condition (2.1).

General null model for the DCBM.  When $K=1$ and $h=1$, $P$ is scalar (say,
$P=\alpha$), and $\Omega=\alpha\theta\theta^{\prime}$ satisfies
$\|\theta\|_{1}=n$ by (2.1). The expected total degree is
$\alpha(\|\theta\|_{1}^{2}-\|\theta\|^{2})\sim\alpha\|\theta\|_{1}^{2}=n^{2}\alpha$
under mild conditions, so we view $\alpha$ as the parameter for network
sparsity. In this model, $d=g=1$.

Alternative model for the DCBM . We assume $K=2$ and that the sizes of the two
communities, ${\cal C}_{0}$ and ${\cal C}_{1}$, are $(n-N)$ and $N$,
respectively. For some positive numbers $a,b,c$, we have

$P=\left[\begin{array}[]{ll}a&b\\\ b&c\\\
\end{array}\right],\qquad\mbox{and}\qquad\Omega(i,j)=\left\\{\begin{array}[]{ll}\theta_{i}\theta_{j}\cdot
a,&\qquad\mbox{if $i,j\in{\cal C}_{1}$},\\\ \theta_{i}\theta_{j}\cdot
c,&\qquad\mbox{if $i,j\in{\cal C}_{0}$},\\\ \theta_{i}\theta_{j}\cdot
b,&\qquad\mbox{otherwise}.\\\ \end{array}\right.$ (2.3)

In the classical clique detection problem (e.g., Bogerd et al. (2021)), $a$
and $c$ are the baseline probability where two nodes have an edge when both of
them are in the clique and outside the clique, respectively. By (2.1),
$a\epsilon+b(1-\epsilon)=b\epsilon+c(1-\epsilon)$ if we write $\epsilon=N/n$.
Therefore,

$b=(c(n-N)-aN)/(n-2N).$ (2.4)

Note that this is the direct result of Sinkhorn’s theorem and the parameter
calibration we choose, not a condition we choose for technical convenience.
Write $d=(d_{0},d_{1})^{\prime}$ and $g=(g_{0},g_{1})^{\prime}$. It is seen
that $d_{0}=1-d_{1}$, $g_{0}=1-g_{0}$,
$d_{1}=\|\theta\|_{1}^{-1}\sum_{i\in{\cal C}_{1}}\theta_{i}$, and
$g_{1}=\|\theta\|^{-2}\sum_{i\in{\cal C}_{1}}\theta_{i}^{2}$. If all
$\theta_{i}$ are at the same order, then $d_{1}\asymp g_{1}\asymp(N/n)$ and
$d_{0}\sim g_{0}\sim 1$. We also observe that $b=c+O(a\epsilon)$ which makes
the problem seem very close to Arias-Castro & Verzelen (2014); Bogerd et al.
(2021), although in fact the problems are quite different.

Extension . An extension of our alternative is that, for the $K$ communities,
the sizes of $m$ of them are at the order of $N$, for an $N\ll n$ and an
integer $m$, $1\leq m<K$, and the sizes of remaining $(K-m)$ are at the order
of $n$. In this case, $m$ entries of $d$ are $O(N/n)$ and other entries are
$O(1)$; same for $g$.

####  2.2 The SgnQ test: limiting null, p-value, and power

In the null case, $K=1$ and we assume $\Omega=\alpha\theta\theta^{\prime}$,
where $\|\theta\|_{1}=n$. As $n\rightarrow\infty$, both $(\alpha,\theta)$ may
vary with $n$. Write $\theta_{\max}=\|\theta\|_{\infty}$. We assume

$n\alpha\to\infty,\qquad\mbox{and}\qquad\alpha\theta^{2}_{\max}\log(n^{2}\alpha)\to
0.$ (2.5)

The following theorem is adapted from Jin et al. (2021b) and the proof is
omitted.

######  Theorem 2.1 (Limiting null of the SgnQ statistic).

Suppose the null hypothesis is true and the regularity conditions (2.1) and
(2.5) hold. As $n\rightarrow\infty$, $\psi_{n}\rightarrow N(0,1)$ in law.

We have two comments. First, since the DCBM has many parameters (even in the
null case), it is not an easy task to find a test statistic with a limiting
null that is completely parameter free. For example, if we use the largest
eigenvalue of $A$ as the test statistic, it is unclear how to normalize it so
to have such a limiting null. Second, since the limiting null is completely
explicit, we can approximate the (one-sided) $p$-value of $\psi_{n}$ by
$\mathbb{P}(N(0,1)\geq\psi_{n})$. The p-values are useful in practice, as we
show in our numerical experiments.. For example, using a recent data set on
the statisticians’ publication (Ji et al., 2022), for each author, we can
construct an ego network and apply the SgnQ test. We can then use the
$p$-value to measure the co-authorship diversity of the author. Also, in many
hierarchical community detection algorithms (which are presumably recursive,
aiming to estimate the tree structure of communities), we can use the p-values
to determine whether we should further divide a sub-community in each stage of
the algorithm (e.g. Ji et al. (2022)).

The power of the SgnQ test hinges on the matrix
$\widetilde{\Omega}=\Omega-({\bf 1}_{n}^{\prime}\Omega{\bf
1}_{n})^{-1}\Omega{\bf 1}_{n}{\bf 1}_{n}^{\prime}\Omega$. By basic algebra,

$\widetilde{\Omega}=\Theta\Pi\widetilde{P}\Pi^{\prime}\Theta,\qquad\mbox{where
\; $\widetilde{P}=P-(d^{\prime}Pd)^{-1}Pdd^{\prime}P$}.$ (2.6)

Let $\tilde{\lambda}_{1}$ be the largest (in magnitude) eigenvalue of
$\widetilde{\Omega}$. Lemma 2.2 is proved in the supplement.

######  Lemma 2.2.

The rank and trace of the matrix $\widetilde{\Omega}$ are $(K-1)$ and
$\|\theta\|^{2}\mathrm{diag}(\tilde{P})^{\prime}g$, respectively. When $K=2$,
$\tilde{\lambda}_{1}=\mathrm{trace}(\widetilde{\Omega})=\|\theta\|^{2}(ac-b^{2})(d_{0}^{2}g_{1}+d_{1}^{2}g_{0})/(ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2})$.

As a result of this lemma, we observe that in the SBM case, $d=h$ and thus
$\widetilde{\lambda}_{1}=\lambda_{2}\asymp N(a-c)$. To see intuitively that
the power of the SgnQ test hinges on
$\tilde{\lambda}_{1}^{4}/\lambda_{1}^{2}$, if we heuristically replace the
terms of SgnQ by population counterparts, we obtain

$\displaystyle Q_{n}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},i_{2},i_{3},i_{4}(distinct)\end{subarray}}\hat{A}_{i_{1}i_{2}}\hat{A}_{i_{2}i_{3}}\hat{A}_{i_{3}i_{4}}\hat{A}_{i_{4}i_{1}}\approx\mathrm{trace}([\Omega-\eta\eta^{\prime}]^{4})=\mathrm{trace}(\widetilde{\Omega}^{4})=\tilde{\lambda}_{1}^{4}.$

We now formally discuss the power of the SgnQ test. We focus on the
alternative hypothesis in Section 2.1. Let $d=(d_{1},d_{0})^{\prime}$ and
$g=(g_{1},g_{0})^{\prime}$ be as in (2.2), and let
$\theta_{\max,0}=\max_{i\in{\cal C}_{0}}\theta_{i}$ and
$\theta_{\max,1}=\max_{i\in{\cal C}_{1}}\theta_{i}$. Suppose

$d_{1}\asymp g_{1}\asymp N/n,\qquad a\theta^{2}_{\max,1}=O(1),\qquad
cn\to\infty,\qquad c\theta^{2}_{\max,0}\log(n^{2}c)\to 0.$ (2.7)

These conditions are mild. For example, when $\theta_{i}$’s are at the same
order, the first inequality in (2.7) automatically holds, and the other
inequalities in (2.7) hold if $a\leq C$ for an absolute constant $C>0$,
$cn\to\infty$, and $c\log(n)\to 0$.

Fixing $0<\kappa<1$, let $z_{\kappa}>0$ be the value such that
$\mathbb{P}(N(0,1)\geq z_{\kappa})=\kappa$. The level-$\kappa$ SgnQ test
rejects the null if and only if $\psi_{n}\geq z_{\kappa}$, where $\psi_{n}$ is
as in (1.3). Theorem 2.2 and Corollary 2.1 are proved in the supplement.
Recall that our alternative hypothesis is defined in Section 2.1. By power we
mean the probability that the alternative hypothesis is rejected, minimized
over all possible alternative DCBMs satisfying our regularity conditions.

######  Theorem 2.2 (Power of the SgnQ test).

Suppose that (2.7) holds, and let $\kappa\in(0,1)$. Under the alternative
hypothesis, if $|\tilde{\lambda}_{1}|/\sqrt{\lambda_{1}}\to\infty$, the power
of the level-$\kappa$ SgnQ test tends to $1$.

######  Corollary 2.1.

Suppose the same conditions of Theorem 2.2 hold, and additionally
$\theta_{\max}\leq C\theta_{\min}$ so all $\theta_{i}$ are at the same order.
In this case, $\lambda_{1}\asymp cn$ and $|\tilde{\lambda}_{1}|\asymp N(a-c)$,
and the power of the level-$\kappa$ SgnQ test tends to $1$ if
$N(a-c)/\sqrt{cn}\to\infty$.

In Theorem 2.2 and Corollary 2.1, if $\kappa=\kappa_{n}$ and
$\kappa_{n}\rightarrow 0$ slowly enough, then the results continues to hold,
and the sum of Type I and Type II errors of the SgnQ test at
level-$\kappa_{n}$ $\rightarrow 0$.

The power of the SgnQ test was only studied in the balanced case (Jin et al.,
2021b), but our setting is a severely unbalanced case, where the community
sizes are at different orders as well as the entries of $d$ and $g$. In the
balanced case, the signal-to-noise ratio of SgnQ is governed by
$|\lambda_{2}|/\sqrt{\lambda}_{1}$, but in our setting, the signal-to-noise
ratio is governed by $|\tilde{\lambda}_{1}|/\sqrt{\lambda_{1}}$. The proof is
also subtly different. Since the entries of $P$ are at different orders, many
terms deemed negligible in the power analysis of the balanced case may become
non-negligible in the unbalanced case and require careful analysis.

####  2.3 Comparison with the naive degree-based $\chi^{2}$-test

Consider a setting where $\Omega=\alpha\Theta{\bf 1}_{n}{\bf
1}_{n}^{\prime}\Theta\equiv\alpha\theta\theta^{\prime}$ under the null and
$\Omega=\Theta\Pi P\Pi^{\prime}\Theta$ under the alternative, and (2.1) holds.
When $\theta$ is unknown, it is unclear how to apply the $\chi^{2}$-test: the
null case has $n$ unknown parameters $\theta_{1},\ldots,\theta_{n}$, and we
need to use the degrees to estimate $\theta_{i}$ first. As a result, the
resultant $\chi^{2}$-statistic may be trivially $0$. Therefore, we consider a
simpler SBM case where $\theta={\bf 1}_{n}$. In this case, $\Omega=\alpha{\bf
1}_{n}{\bf 1}_{n}$, and $\Omega=\Pi P\Pi^{\prime}$ and the null case only has
one unknown parameter $\alpha$. Let $y_{i}$ be the degree of node $i$, and let
$\hat{\alpha}=[n(n-1)]^{-1}{\bf 1}_{n}^{\prime}A{\bf 1}_{n}$. The
$\chi^{2}$-statistic is

$X_{n}=\sum_{i=1}^{n}(y_{i}-n\hat{\alpha})^{2}/[(n-1)\hat{\alpha}(1-\hat{\alpha})].$
(2.8)

It is seen that as $n\alpha\to\infty$ and $\alpha\to 0$,
$(X_{n}-n)/\sqrt{2n}\rightarrow N(0,1)$ in law. For a fixed level
$\kappa\in(0,1)$, consider the $\chi^{2}$-test that rejects the null if and
only if $(X_{n}-n)/\sqrt{2n}>z_{\kappa}$. Let $\alpha_{0}=n^{-2}({\bf
1}_{n}^{\prime}\Omega{\bf 1}_{n})$. The power of the $\chi^{2}$-test hinges on
the quantity $(n\alpha_{0})^{-1}\|(\Omega{\bf
1}_{n}-n\alpha_{0})\|^{2}=(n\alpha_{0})^{-1}\|\Pi Ph-(h^{\prime}Ph)^{-1}{\bf
1}_{n}\|^{2}=0$, if $Ph\propto{\bf 1}_{K}$. The next theorem is proved in the
supplement.

######  Theorem 2.3.

Suppose $\theta=\mathbf{1}_{n}$ and (2.7) holds. If
$|\tilde{\lambda}_{1}|/\sqrt{\lambda_{1}}\to\infty$ under the alternative
hypothesis, the power of the level-$\kappa$ SgnQ test goes to $1$, while the
power of the level-$\kappa$ $\chi^{2}$-test goes to $\kappa$.

####  2.4 The statistical lower bound and the optimality of the scan test

For lower bounds, it is standard to consider a random-membership DCBM (Jin et
al., 2021b), where $\|\theta\|_{1}=n$, $P$ is as in (2.3)-(2.4) and for a
number $N\ll n$, $\Pi=[\pi_{1},\pi_{2},\ldots,\pi_{n}]^{\prime}$ satisfies

$\pi_{i}=(X_{i},1-X_{i}),\qquad\mbox{where $X_{i}$ are iid
Bernoulli($\varepsilon)$ with $\varepsilon=N/n$}.$ (2.9)

######  Theorem 2.4 (Statistical lower bound).

Consider the null and alternative hypotheses of Section 2.1, and assume that
(2.9) is satisfied, $\theta_{\max}\leq C\theta_{\min}$ and $Nc/\log
n\to\infty$. If $\sqrt{N}(a-c)/\sqrt{c}\to 0$, then for any test, the sum of
the type-I and type-II errors tends to $1$.

To show the tightness of this lower bound, we introduce the signed scan test,
by adapting the idea in Arias-Castro & Verzelen (2014) from the SBM case to
the DCBM case. Unlike the SgnQ test and the $\chi^{2}$-test, signed scan test
is not a polynomial time test, but it provides sharper upper bounds. Let
$\hat{\eta}$ be the same as in (1.3). For any subset
$S\subset\\{1,2,\ldots,n\\}$, let ${\bf 1}_{S}\in\mathbb{R}^{n}$ be the vector
whose $i$th coordinate is $1\\{i\in S\\}$. Define the signed scan statistic

$\phi_{sc}=\max_{S\subset\\{1,2,\ldots,n\\}:|S|=N}{\bf
1}^{\prime}_{S}\big{(}A-\hat{\eta}\hat{\eta}^{\prime}\big{)}{\bf 1}_{S}.$
(2.10)

######  Theorem 2.5 (Tightness of the statistical lower bound).

Consider the signed scan test (2.10) that rejects the null hypothesis if
$\phi_{sc}>t_{n}$. Under the assumptions of Theorem 2.4, if
$\sqrt{N}(a-c)/\sqrt{c\log(n)}\to\infty$, then there exists a sequence $t_{n}$
such that the sum of type I and type II errors of the signed scan test tends
to $0$.

By Theorems 2.4-2.5 and Corollary 2.1, the two hypotheses are asymptotically
indistinguishable if $\sqrt{N}(a-c)/\sqrt{c}\to 0$, and are asymptotically
distinguishable by the SgnQ test if $N(a-c)/\sqrt{cn}\to\infty$. Therefore,
the lower bound is sharp, up to log-factors, and the signed scan test is
nearly optimal. Unfortunately, the signed scan test is not polynomial-time
computable. Does there exist a polynomial-time computable test that is
optimal? We address this in the next section.

####  2.5 The computational lower bound

Consider the same hypothesis pair as in Section 2.4, where $K=2$, $P$ is as in
(2.3)-(2.4), and $\Pi$ is as in (2.9). For simplicity, we only consider SBM,
i.e., $\theta_{i}\equiv 1$. The low-degree polynomials argument emerges
recently as a major tool to predicting the average-case computational barriers
in a wide range of high-dimensional problems (Hopkins & Steurer, 2017; Hopkins
et al., 2017). Many powerful methods, such as spectral algorithms and
approximate message passing, can be formulated as functions of the input data,
where the functions are polynomials with degree at most logarithm of the
problem dimension. In comparison to many other schemes of developing
computational lower barriers, the low-degree polynomial method yields the same
threshold for various average-case hardness problems, such as community
detection in the SBM (Hopkins & Steurer, 2017) and (hyper)-planted clique
detection (Hopkins, 2018; Luo & Zhang, 2022). The foundation of the low-degree
polynomial argument is the following low-degree polynomial conjecture (Hopkins
et al., 2017) :

######  Conjecture 2.1 (Adapted from Kunisky et al. (2019)).

Let $\mathbb{P}_{n}$ and $\mathbb{Q}_{n}$ denote a sequence of probability
measures with sample space $\mathbb{R}^{n^{k}}$ where $k=O(1)$. Suppose that
every polynomial $f$ of degree $O(\log n)$ with
$\mathbb{E}_{\mathbb{Q}_{n}}f^{2}=1$ is bounded under $\mathbb{P}_{n}$ with
high probability as $n\to\infty$ and that some further regularity conditions
hold. Then there is no polynomial-time test distinguishing $\mathbb{P}_{n}$
from $\mathbb{Q}_{n}$ with type I and type II error tending to $0$ as
$n\to\infty$.

We refer to Hopkins (2018) for a precise statement of this conjecture’s
required regularity conditions. The low-degree polynomial computational lower
bound for our testing problem is as follows.

######  Theorem 2.6 (Computational lower bound).

Consider the null and alternative hypotheses in Section 2.1, and assume
$\theta_{i}\equiv 1$ and (2.9) holds. As $n\to\infty$, assume $c<a$,
$c<1-\delta$ for constant $\delta>0$, $N<n/3$, $D=O(\log n)$, and
$\limsup_{n\to\infty}\left\\{\left(\log_{n}\frac{N}{\sqrt{n}}+\log_{n}\frac{a-c}{\sqrt{c}}\right)\vee\left(\sqrt{D/2-1}\log_{n}\frac{a-c}{\sqrt{c}}\right)\right\\}<0.$
For any series of degree-$D$ polynomials $\phi_{n}:A\to\mathbb{R}$, whenever
$\mathbb{E}_{H_{0}}\phi_{n}(A)=0,\textrm{Var}_{H_{0}}(\phi_{n}(A))=1$, we must
have $\mathbb{E}_{H_{1}}\phi_{n}(A)=o(1)$. This implies if Conjecture 2.1 is
true, there is no consistent polynomial-time test for this problem.

By Theorem 2.6, if both $(a-c)/\sqrt{c}\lesssim 1$ and $N(a-c)/\sqrt{cn}\to
0$, the testing problem is computationally infeasible. The region where the
testing problem is statistically possible but the SgnQ test loses power
corresponds to $N(a-c)/\sqrt{cn}\to 0$. If $N\gtrsim\sqrt{n}$, Theorem 2.6
already implies that this is the computationally infeasible region; in other
words, SgnQ achieves the CLB and is optimal. If $N=o(\sqrt{n})$, SgnQ solves
the detection problem only when $(a-c)/\sqrt{c}\gg n^{1/2}$, i.e. when the
node-wise SNR is strong. We discuss the case of moderate node-wise SNR in the
next subsection.

####  2.6 The power of EST, and discussions of the tightness of CLB

When $N=o(\sqrt{n})$ and $(a-c)/\sqrt{c}\to\infty$ both hold, the upper bound
by SgnQ does not match with the CLB. It is unclear whether the CLB is tight.
To investigate the CLB in this regime, we consider other possible polynomial-
time tests. The economic scan test (EST) is one candidate. Given fixed
positive integers $v$ and $e$, the EST statistic is defined to be
$\phi_{EST}^{(v)}\equiv\sup_{|S|\leq v}\sum_{i,j\in S}A_{ij}$, and the EST is
defined to reject if and only if $\phi_{EST}^{(v)}\geq e$. EST can be computed
in time $O(n^{v})$, which is polynomial time. For simplicity, we consider the
SBM, i.e. where $\theta={\bf 1}_{n}$, and a specific setting of parameters for
the null and alternative hypotheses.

######  Theorem 2.7 (Power of EST).

Suppose $\beta\in[1/2,1)$ and $0<\omega<\delta<1$ are fixed constants. Under
the alternative, suppose $\theta=\mathbf{1}_{n}$, (2.9) holds,
$N=n^{1-\beta}$, $a=n^{-\omega}$, and $c=n^{-\delta}$. Under the null, suppose
$\theta=\mathbf{1}_{n}$ and $\alpha=a(N/n)+b(1-N/n)$. If
$\omega/(1-\beta)<\delta$, the sum of type I and type II errors of the EST
with $v$ and $e$ satisfying $\omega/(1-\beta)<v/e<\delta$ tends to $0$.

Figure 2: Left: Null distribution of SgnQ ($n=500$). Middle and right: Power
comparison of SgnQ and $\chi^{2}$ ($n=100$, $N=10$, 50 repetitions). We
consider a 2-community SBM with $P_{11}=a$, $P_{22}=0.1$, $P_{12}=0.1$ (middle
plot) and $P_{12}=\frac{an-(a+0.1)N}{n}$ (right plot, the case of degree
matching).

Theorem 2.7 follows from standard results in probabilistic combinatorics (Alon
& Spencer, 2016). It is conjectured in Bhaskara et al. (2010) that EST attains
the CLB in the Erdös-Renyi setting considered by Arias-Castro & Verzelen
(2014); Verzelen & Arias-Castro (2015). This suggests that the CLB in Theorem
2.6 is likely not tight when $N=o(\sqrt{n})$ and $(a-c)/\sqrt{c}\to\infty$.
However, this is not because our inequalities in proving the CLB are loose. A
possible reason is that the prediction from the low-degree polynomial
conjecture does not provide a tight bound. It remains an open question whether
other computational infeasibility frameworks provide a tight CLB in our
problem.

####  2.7 The phase transition

We describe more precisely our results in terms of the phase transitions shown
in Figure 1. Consider the null and alternative hypotheses from Section 2.1.
For illustration purposes, we fix constants $\beta\in(0,1)$ and
$\gamma\in\mathbb{R}$ and assume that $N=n^{1-\beta}$ and
$(a-c)/\sqrt{c}=n^{-\gamma}$. In the two-dimensional space of
$(\gamma,\beta)$, the region of $\beta>1/2$ and $\beta<1/2$ corresponds to
that the size of the small community is $\gg\sqrt{n}$ and $o(\sqrt{n})$,
respectively, and the regions of $\gamma>0$, $-1/2<\gamma<0$ and $\gamma<-1/2$
correspond to ‘weak node-wise signal’, ‘moderate node-wise signal,’ and the
‘strong node-wise signal’, respectively. See Figure 1. By our results in
Section 2.4, the testing problem is statistically impossible if
$\beta+2\gamma>1$ (orange region). By our results in Section 2.2, SgnQ has a
full power if $\beta+\gamma<1/2$ (blue region). Our results in Section 2.5
state that the testing problem is computationally infeasible if both
$\gamma>0$ and $\beta+\gamma>1/2$ (green and orange regions). Combining these
results, when $\beta<1/2$, we have a complete understanding of the LB and CLB.

###  3 Numerical results

Simulations. First in Figure 2 (left panel) we demonstrate the asymptotic
normality of SgnQ under a null of the form $\Omega=\theta\theta^{\prime}$,
where $\theta_{i}$ are i.i.d. generated from $\mathrm{Pareto}(4,0.375)$.
Though the degree heterogeneity is severe, SgnQ properly standardized is
approximately standard normal under the null. Next in Figure 2 we compare the
power of SgnQ in an asymmetric and symmetric SBM model. As our theory
predicts, both tests are powerful when degrees are not calibrated in each
model, but only SgnQ is powerful in the symmetric case. We also compare the
power of SgnQ with the scan test to show evidence of a statistical-
computational gap. We relegate these experiments to the supplement.

Real data: Next we demonstrate the effectiveness of SgnQ in detecting small
communities in coauthorship networks studied in Ji et al. (2022). In Example
1, we consider the personalized network of Raymond Carroll, whose nodes
consist of his coauthors for papers in a set of 36 statistics journals from
the time period 1975 – 2015. An edge is placed between two coauthors if they
wrote a paper in this set of journals during the specified time period. The
SgnQ p-value for Carroll’s personalized network $G_{\mathsf{Carroll}}$ is
$0.02$, which suggests the presence of more than one community. In Ji et al.
(2022), the authors identify a small cluster of coauthors from a collaboration
with the National Cancer Institute. We applied the SCORE community detection
module with $K=2$ (e.g. Ke & Jin (2022)) and obtained a larger community
$G_{\mathsf{Carroll}}^{\,0}$ of size $218$ and a smaller community
$G_{\mathsf{Carroll}}^{\,1}$ of size $17$. Precisely, we removed Carroll from
his network, applied SCORE on the remaining giant component, and defined
$G_{\mathsf{Carroll}}^{\,0}$ to be the complement of the smaller community.
The SgnQ p-values in the table below suggest that both
$G_{\mathsf{Carroll}}^{\,0}$ and $G_{\mathsf{Carroll}}^{\,1}$ are tightly
clustered. Refer to the supplement for a visualization of Carroll’s network
and its smaller community labeled by author names. In Example 2, we consider
three different coauthorship networks $G_{\mathsf{old}}$,
$G_{\mathsf{recent}}$, and $G_{\mathsf{new}}$ corresponding to time periods
(i) 1975-1997, (ii) 1995-2007, and (iii) 2005-2015 for the journals AoS, Bka,
JASA, and JRSSB. Nodes are given by authors, and an edge is placed between two
authors if they coauthored at least one paper in one of these journals during
the corresponding time period. For each network, we perform a similar
procedure as in the first example. First we compute the SgnQ p-value, which
turns out to be $\approx 0$ (up to 16 digits of precision) for all networks.
For each $i\in\\{\mathsf{old},\mathsf{recent},\mathsf{new}\\}$, we apply SCORE
with $K=2$ to $G_{i}$ and compute the SgnQ p-value on both resulting
communities, let us call them $G_{i}^{0}$ and $G_{i}^{1}$. We refer to the
table below for the results. For $G_{\mathsf{old}}$ and $G_{\mathsf{recent}}$,
SCORE with $K=2$ extracts a small community. The SgnQ p-value further supports
the hypothesis that this small community is well-connected. In the last
network, SCORE splits $G_{\mathsf{new}}$ into two similarly sized pieces whose
p-values suggests they can be split into smaller subcommunities.

Example | Network | Size | SgnQ p-value | Communities | Sizes | SgnQ p-values
---|---|---|---|---|---|---
1 | $G_{\mathsf{Carroll}}$ | 235 | 0.02 | $(G_{\mathsf{Carroll}}^{\,0},G_{\mathsf{Carroll}}^{1})$ | (218, 17) | (0.134, 0.682)
2 | $G_{\mathsf{old}}$ | 2647 | 0 | $(G_{\mathsf{old}}^{0},G_{\mathsf{old}}^{1})$ | (2586, 61) | (0, 0.700)
| $G_{\mathsf{recent}}$ | 2554 | 0 | $(G_{\mathsf{recent}}^{0},G_{\mathsf{recent}}^{1})$ | (2540,14) | (0, 0.759)
| $G_{\mathsf{new}}$ | 2920 | 0 | $(G_{\mathsf{new}}^{0},G_{\mathsf{new}}^{1})$ | (1685,1235) | (0, 0)

Discussions: Global testing is a fundamental problem and often the starting
point of a long line of research. For example, in the literature of Gaussian
models, certain methods started as a global testing tool, but later grew into
tools for variable selection, classification, and clustering and motivated
many researches (e.g., Donoho & Jin (2004; 2015)). The SgnQ test may also
motivate tools for many other problems, such as estimating the locations of
the clique and clustering more generally. For example, in Jin et al. (2022),
the SgnQ test motivated a tool for estimating the number of communities (see
also Ma et al. (2021)). SgnQ is also extendable to clique detection in a
tensor (Yuan et al., 2021; Jin et al., 2021a) and for network change point
detection. The LB and CLB we obtain in this paper are also useful for studying
other problems, such as clique estimation. If you cannot tell whether there is
a clique in the network, then it is impossible to estimate the clique.
Therefore, the LB and CLB are also valid for the clique estimation problem
(Alon et al., 1998; Ron & Feige, 2010).

The limiting distribution of SgnQ is $N(0,1)$. This is not easy to achieve if
we use other testing ideas, such as the leading eigenvalues of the adjacency
matrix: the limiting distribution depends on many unknown parameters and it is
hard to normalize (Liu et al., 2019). The p-value of the SgnQ test is easy to
approximate and also useful in applications. For example, we can use it to
measure the research diversity of a given author. Consider the ego sub-network
of an author in a large co-authorship or citation network. A smaller p-value
suggests that the ego network has more than $1$ communitiy and has more
diverse interests. The p-values can also be useful as a stopping criterion in
hierarchical community detection modules.

Acknowledgments. We thank the anonymous referees for their helpful comments.
We thank Louis Cammarata for assistance with the simulations in Section A.3.
J. Jin was partially supported by NSF grant DMS-2015469. Z.T. Ke was supported
in part by NSF CAREER Grant DMS-1943902. A.R. Zhang acknowledges the grant NSF
CAREER-2203741.

##  Appendix

###  Appendix A Additional experiments

####  A.1 Visualization of Carroll’s network

In Figure 3, we display a subgraph of high-degree nodes of Raymond Carroll’s
personalized coauthorship network (figure borrowed with permission from Ji et
al. (2022)). On the right of Figure 3 is shown the small community extracted
by SCORE, and this cluster of size $17$ is labeled by author names.

Figure 3: Left: Carroll’s personalized network, figure taken from Ji et al.
(2022). Right: A small community of $17$ authors extracted by SCORE and whose
SgnQ p-value is $0.6818$.

####  A.2 SgnQ vs. Scan

In this section we demonstrate evidence of a statistical-computational gap by
means of numerical experiments.

We consider a SBM null and alternative model (as in Example 2 with
$\theta\equiv 1$) with

$P_{0}=\begin{pmatrix}\alpha&\alpha\\\ \alpha&\alpha\end{pmatrix},\qquad
P_{1}=\begin{pmatrix}a&b\\\ b&c\end{pmatrix}$

where $aN+b(n-N)=\alpha$. For this simple testing problem, we compare the
power of SgnQ and the scan test. In our experiments, we set $\alpha=0.2$ and
allow the parameter $a$ to vary from $a=\alpha$ to $a=a_{\max}\equiv an/N$.
Once $a$ and $\alpha$ are fixed, the parameters $b$ and $c$ are determined by

$\displaystyle c$ $\displaystyle=\frac{aN^{2}+\alpha n^{2}-2\alpha
nN}{(n-N)^{2}},$ $\displaystyle b$ $\displaystyle=\frac{nc-(a+c)N}{n-2N}.$

In particular, $a_{\max}$ is the largest value of $a$ such that $b\geq 0$.

Since the scan test $\phi_{sc}$ we defined is extremely computationally
expensive, we study the power of an ‘oracle’ scan test $\tilde{\phi}_{sc}$
which knows the location of the true planted subset $\mathcal{C}_{1}$. The
power of the oracle scan test is computed as follows. Let $\kappa$ denote the
desired level.

  1. 1.

Using $M_{cal}$ repetitions under the null, we calculate the (non-oracle) scan
statistic $\phi_{sc}^{(1)},\ldots,\phi_{sc}^{(M_{cal})}$ for each repetition.
We set the threshold $\hat{\tau}$ to be the empirical $1-\kappa$ quantile of
$\phi_{sc}^{(1)},\ldots,\phi_{sc}^{(M_{cal})}$.

  2. 2.

Given a sample from the alternative model, we compute the power using
$M_{pow}$ repetitions, where we reject if

$\tilde{\phi}_{sc}\equiv\mathbf{1}_{\mathcal{C}_{1}}(A-\hat{\eta}\hat{\eta}^{\prime})\mathbf{1}_{\mathcal{C}_{1}}>\hat{\tau}.$

In our experiments, we set $M_{cal}=75$ and $M_{pow}=200$.

Note that since $\tilde{\phi}_{sc}\leq\phi_{sc}$, the procedure above gives an
underestimate of the power of the scan test (provide the threshold is
correctly calibrated), which is helpful since this can be used to show
evidence of a statistical-computational gap.

In our plots we also indicate the statistical (information-theoretic) and
computational thresholds in addition to the power. Inspired by the sharp
characterization of the statistical threshold in (Arias-Castro & Verzelen,
2014, Equation (10)) for planted dense subgraph, in all plots we draw a black
vertical dashed line at the first value of $a$ such that

$(1/2)\sqrt{N}(a-c)/\sqrt{c(1-c)}>1.$

We draw a blue vertical dashed line at the first value of $a$ such that

$N(a-c)/\sqrt{nc}>1.$

Figure 4: The power of SgnQ (blue curve) and oracle scan (black curve) for
$n=30,N\in\\{4,6,7\\}$ (left) and $n=40,N\in\\{4,6,7\\}$ (right). The black
dashed line indicates the theoretical statistical threshold, and the blue
dashed line indicates the theoretical computational threshold.

####  A.3 $\chi_{2}$ vs. SgnQ

We also show additional experiments demonstrating the effect of degree-
matching on the power of the $\chi^{2}$ test. We compute the power with
respect to the following alternative models (as in Example 2 with
$\theta\equiv 1$) with

$P^{(1)}=\begin{pmatrix}a&b\\\ b&c\end{pmatrix},\qquad
P^{(2)}=\begin{pmatrix}a&c\\\ c&c\end{pmatrix}$

where $b=\frac{cn-(a+c)N}{n-2N}$, $c$ is fixed, and $a$ ranges from $c$ to
$a_{\max}^{\prime}=c(n-N)/N$ for the experiments with $P^{(1)}$. Similar to
before, $a_{\max}^{\prime}$ is the largest value of $a$ such that $b\geq 0$.
See Figure 5 for further details.

Figure 5: Power comparison of SgnQ and $\chi^{2}$ ($n=500$, $N=22$, 50
repetitions). We consider a 2-community SBM with $P_{11}=a$, $P_{22}=c$,
$P_{12}=c$ (left) and $P_{12}=\frac{an-(a+c)N}{n}$ (right plot, the case of
degree matching) where $c=0.05$ (top row) and $c=0.20$ (bottom row).

###  Appendix B Proof of Lemma 2.1 (Identifiability)

To prove identifiability, we make use of the following result from (Jin et
al., 2021c, Lemma 3.1), which is in line with Sinkhorn’s work Sinkhorn (1974)
on matrix scaling.

######  Lemma B.1 (Jin et al. (2021c)).

Given a matrix $A\in\mathbb{R}^{K,K}$ with strictly positive diagonal entries
and non-negative off-diagonal entries, and a strictly positive vector
$h\in\mathbb{R}^{K}$, there exists a unique diagonal matrix
$D=\mathrm{diag}(d_{1},d_{2},\ldots,d_{K})$ such that $DADh=1_{K}$ and
$d_{k}>0$, $1\leq k\leq K$.

We apply Lemma B.1 with $h=(h_{1},\ldots,h_{K})^{\prime}$ and $A=P$ to
construct a diagonal matrix $D=\mathrm{diag}(d_{1},\ldots,d_{K})$ satisfying
$DADh=1_{K}$. Note that $P$ has positive diagonal entries since $\Omega$ does.

Define $P^{*}=DPD$ and
$D^{*}=\mathrm{diag}(d_{1}^{*},\ldots,d_{n}^{*})\in\mathbb{R}^{n}$ where

$d_{i}^{*}\equiv d_{k}\qquad\text{if }i\in\mathcal{C}_{k}$

Observe that

$\Pi D^{-1}=(D^{*})^{-1}\Pi.$

Define $\Theta^{*}=\Theta(D^{*})^{-1}$, and let
$\theta^{*}=\mathrm{diag}(\Theta^{*})$. Next, let
$\overline{\Theta}=\frac{n}{\|\theta^{*}\|_{1}}\cdot\Theta^{*}$, let
$\overline{\theta}=\mathrm{diag}(\overline{\Theta})$, and let
$\overline{P}=\frac{\|\theta^{*}\|_{1}^{2}}{n^{2}}\cdot P^{*}$. Note that
$\|\overline{\theta}\|_{1}=n$ and $\overline{P}h\propto\mathbf{1}_{K}$.

Using the previous definitions and observations, we have

$\Omega=\Theta\Pi D^{-1}DPDD^{-1}\Pi^{\prime}\Theta=\Theta^{*}\Pi
P^{*}\Pi^{\prime}\Theta^{*}=\overline{\Theta}\Pi\overline{P}\Pi^{\prime}\overline{\Theta}$

which justifies existence.

To justify uniqueness, suppose that

$\Omega=\Theta^{(1)}\Pi P^{(1)}\Pi^{\prime}\Theta^{(1)}=\Theta^{(2)}\Pi
P^{(2)}\Pi^{\prime}\Theta^{(2)},$

where $\theta^{(i)}=\mathrm{diag}(\Theta^{(i)})$ satisfy
$\|\theta^{(i)}\|_{1}=n$ for $i=1,2$ and

$P^{(1)}h\propto\mathbf{1}_{K},\qquad P^{(2)}h\propto\mathbf{1}_{K}.$

Observe that

$\Pi
P^{(1)}\Pi^{\prime}\mathbf{1}_{n}=\alpha^{(1)}n\cdot\mathbf{1}_{n},\qquad\Pi
P^{(2)}\Pi^{\prime}\mathbf{1}_{n}=\alpha^{(2)}n\cdot\mathbf{1}_{n}.$

for positive constants $\alpha^{(i)},i\in\\{1,2\\}$. Since $\Omega$ has
nonnegative entries and positive diagonal elements, by Lemma B.1, there exists
a unique diagonal matrix $D$ such that

$D\Omega D\mathbf{1}_{n}=\mathbf{1}_{n}.$

We see that taking $D=\frac{1}{\sqrt{\alpha^{(i)}n}}(\Theta^{(i)})^{-1}$
satisfies this equation for $i=1,2$, and therefore by uniqueness,

$\frac{1}{\sqrt{\alpha^{(1)}n}}(\Theta^{(1)})^{-1}=\frac{1}{\sqrt{\alpha^{(2)}n}}(\Theta^{(2)})^{-1}.$

Since $\|\theta^{(1)}\|_{1}=\|\theta^{(2)}\|_{1}=n$, further we have
$\alpha^{(1)}=\alpha^{(2)}$, and hence

$\Theta^{(1)}=\Theta^{(2)}.$

It follows that

$\Pi P^{(1)}\Pi^{\prime}=\Pi P^{(2)}\Pi^{\prime},$

which, since we assume $h_{i}>0$ for $i=1,\ldots,K$, further implies that
$P^{(1)}=P^{(2)}$. ∎

###  Appendix C Proof of Theorem 2.1 (Limiting null of the SgnQ statistic)

Consider a null DCBM with $\Omega=\theta^{*}(\theta^{*})^{\prime}$. Note that
this is a different choice of parameterization than the one we study in the
main paper. In (Jin et al., 2021c, Theorem 2.1) it is shown that the
asymptotic distribution of $\psi_{n}$, the standardized version of SgnQ, is
standard normal provided that

$\|\theta^{*}\|\rightarrow\infty,\;\;\;\theta_{max}^{*}\rightarrow
0,\;\;\;\mbox{and}\;\;\;(\|\theta^{*}\|^{2}/\|\theta^{*}\|_{1})\sqrt{\log(\|\theta\|_{1}^{*})}\rightarrow
0.$ (C.1)

We verify that, in a DCBM with $\Omega=\alpha\theta\theta^{\prime}$ and
$\|\theta\|_{1}=n$, these conditions are implied by the assumptions in (2.5),
restated below:

$n\alpha\to\infty,\qquad\mbox{and}\qquad\alpha\theta^{2}_{\max}\log(n^{2}\alpha)\to
0$ (C.2)

In the parameterization of Jin et al. (2021c), we have
$\theta^{*}=\sqrt{\alpha}\theta$. First, $\|\theta^{*}\|^{2}\to\infty$ because
by (C.2),

$\|\theta^{*}\|^{2}\geq\frac{1}{n}\cdot\|\theta^{*}\|_{1}^{2}=\alpha
n\to\infty.$

Next, $\theta_{\max}^{*}\to 0$ because by (C.2),

$\theta_{\max}=\sqrt{\alpha}\theta_{\max}\to 0.$

To show the last part of (C.1), note that

$\displaystyle(\|\theta^{*}\|^{2}/\|\theta^{*}\|_{1})\sqrt{\log(\|\theta\|_{1}^{*})}\leq\sqrt{\alpha}\theta_{\max}\sqrt{\log(\sqrt{\alpha}n)}=\frac{1}{\sqrt{2}}\sqrt{\alpha}\theta_{\max}\sqrt{\log(\alpha
n^{2})}\to 0$

by (C.2). Thus (C.1) holds, and $\psi_{n}$ is asymptotically standard normal
under the null. ∎

###  Appendix D  Proof of Lemma 2.2 (Properties of $\tilde{\Omega}$)

######  Lemma.

The rank and trace of the matrix $\widetilde{\Omega}$ are $(K-1)$ and
$\|\theta\|^{2}\mathrm{diag}(\tilde{P})^{\prime}g$, respectively. When $K=2$,
$\tilde{\lambda}_{1}=\mathrm{trace}(\widetilde{\Omega})=\|\theta\|^{2}(ac-b^{2})(d_{0}^{2}g_{1}+d_{1}^{2}g_{0})/(ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2})$.

Proof of Lemma 2.2. By basic algebra,

$\widetilde{\Omega}=\Theta\Pi\widetilde{P}\Pi^{\prime}\Theta,\qquad\mbox{where
$\widetilde{P}=(P-(d^{\prime}Pd)^{-1}Pdd^{\prime}P)$}.$

It is seen $\widetilde{P}d=Pd-(d^{\prime}Pd)^{-1}Pdd^{\prime}Pd=0$, so
$\mathrm{rank}(\widetilde{P})\leq K-1$. At the same time, since for any matrix
$A$ and $B$ of the same size,
$\mathrm{rank}(A+B)\leq\mathrm{rank}(A)+\mathrm{rank}(B)$, it follows
$\widetilde{P}\geq(K-1)$, as $\mathrm{rank}(P)=K$ and
$\mathrm{rank}(Pdd^{\prime}P)\leq 1$. This proves that
$\mathrm{rank}(\widetilde{P})=K-1$.

At the same time, since for any matrices $A$ and $B$,
$\mathrm{trace}(AB)=\mathrm{trace}(BA)$,

$\mathrm{trace}(\widetilde{\Omega})=\mathrm{trace}(\widetilde{P}\Pi^{\prime}\Theta^{2}\Pi)=\|\theta\|^{2}\mathrm{trace}(\widetilde{P}G)=\|\theta\|^{2}\mathrm{diag}(\tilde{P})^{\prime}g.$

This proves the second item of the lemma.

Last, when $K=2$, $\widetilde{\Omega}$ is rank $1$, and its eigenvalue is the
same as its trace. First

$\displaystyle(\tilde{P})_{11}$
$\displaystyle=a-\frac{(ad_{1}+bd_{0})^{2}}{ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2}}=(ac-b^{2})\frac{d_{0}^{2}}{ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2}}$
$\displaystyle(\tilde{P})_{22}$
$\displaystyle=c-\frac{(bd_{1}+cd_{0})^{2}}{ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2}}=(ac-b^{2})\frac{d_{1}^{2}}{ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2}}.$

Thus

$\tilde{\lambda}_{1}=\|\theta\|^{2}\mathrm{diag}(\tilde{P})^{\prime}g=\|\theta\|^{2}(ac-b^{2})\cdot\frac{d_{0}^{2}g_{1}+d_{1}^{2}g_{0}}{ad_{1}^{2}+2bd_{0}d_{1}+cd_{0}^{2}}$

This proves the last item and completes the proof of the lemma.

∎

###  Appendix E  Proof of Theorem 2.2 (Power of the SgnQ test) and Corollary
2.1

####  E.1 Setup and results

Notation: Given sequences of real numbers $A=A_{n}$ and $B=B_{n}$, we write
$A\lesssim B$ to signify that $A=O(B)$, $A\asymp B$ to signify that $A\lesssim
B$ and $B\lesssim A$, and $A\sim B$ to signify that $A/B=1+o(1)$.

Throughout this section, we consider a DCBM with parameters $(\Theta,P)$ where
$P\in\mathbb{R}^{2\times 2}$ has unit diagonals, and we analyze the behavior
of SgnQ under the alternative. At the end of this subsection we explain how
Theorem 2.2 and Corollary 2.1 follow from the results described next. Our
results hinge on

$\tilde{\lambda}\equiv\tilde{\lambda}_{1}=\mathrm{tr}(\tilde{\Omega}).$

Given a subset $U\subset[n]$, let $\theta_{U}\in\mathbb{R}^{|U|}$ denote the
restriction of $\theta$ to the coordinates of $U$. For notational convenience,
we let $S=\\{i:\pi_{i}(1)=1\\}$, which was previously written as
$\mathcal{C}_{1}$ in the main paper.

In a DCBM where $P$ has unit diagonals, our main results hold under the
following conditions.

$\displaystyle\Omega_{ij}$ $\displaystyle\lesssim\theta_{i}\theta_{j}$ (E.1)
$\displaystyle\|\theta\|_{\infty}$ $\displaystyle=O(1),\text{ and }$ (E.2)
$\displaystyle\|\theta\|_{2}^{2}$ $\displaystyle\to\infty.$ (E.3)
$\displaystyle(\|\theta\|_{2}^{2}/\|\theta\|_{1})\sqrt{\log(\|\theta\|_{1})}$
$\displaystyle\to 0.$ (E.4)

First we justify that these assumptions are satisfied by an equivalent DCBM
with the same $\Omega$ represented with the parameterization (2.1) and
satisfying (2.7). Thus all results proved in this section transfer immediately
to the main paper.

######  Lemma E.1.

Consider a DCBM with parameters $(\Theta^{*},P^{*})$ satisfying (2.1) and
satisfying (2.7). Define $\Theta=\mathrm{diag}(\theta)$ where

$\theta_{i}=\begin{cases}\sqrt{a}\theta_{i}^{*}&\quad\text{if }i\in S\\\
\sqrt{c}\theta_{i}^{*}&\quad\text{if }i\in S^{c},\end{cases}$

and

$P=\begin{pmatrix}1&\frac{b}{\sqrt{ac}}\\\
\frac{b}{\sqrt{ac}}&1\end{pmatrix}.$

Then

$\Omega=\Theta\Pi P\Pi\Theta=\Theta^{*}\Pi P^{*}\Pi^{\prime}\Theta^{*}$

and (E.1)–(E.4) are satisfied.

###### Proof.

The statement regarding $\Omega$ follows by basic algebra. (E.1) follows if we
can show that

$\displaystyle\frac{b}{\sqrt{ac}}\lesssim 1.$ (E.5)

Since

$b=\frac{cn-(a+c)N}{n-2N}=c\cdot\frac{n-N}{n-2N}-a\cdot\frac{N}{n-2N},$

we have $a\geq c\gtrsim b$, so (E.5) follows.

Next, (E.2) follows directly from $a\theta_{\max,1}^{2}\lesssim 1$ since
$c\theta_{\max,0}^{2}=o(1)$ by (2.7).

For (E.3),

$\|\theta\|_{2}^{2}\geq\frac{1}{n}\cdot\|\theta\|_{1}^{2}\geq cn\to\infty$

by (2.7).

For the last part, note that

$b=c\cdot\frac{n-N}{n-2N}-a\cdot\frac{N}{n-2N}\geq 0\Rightarrow
a\varepsilon\lesssim c.$

Thus,

$\displaystyle\frac{\|\theta\|_{2}^{2}}{\|\theta\|_{1}}$
$\displaystyle=\frac{a\|\theta_{S}^{*}\|_{2}^{2}+c\|\theta_{S^{c}}^{*}\|_{2}^{2}}{\sqrt{a}\|\theta_{S}^{*}\|_{1}+\sqrt{c}\|\theta_{S^{c}}^{*}\|_{1}}\lesssim\frac{a(N/n)\|\theta^{*}_{S^{c}}\|_{2}^{2}+c\|\theta_{S^{c}}^{*}\|_{2}^{2}}{\sqrt{c}\|\theta^{*}_{S^{c}}\|_{1}}$
$\displaystyle\lesssim\frac{c\|\theta_{S^{c}}^{*}\|_{2}^{2}}{\sqrt{c}\|\theta_{S^{c}}^{*}\|_{1}}\lesssim\sqrt{c}\theta_{\max,0}=o\big{(}\frac{1}{\sqrt{\log
cn^{2}}}\big{)}=o\big{(}\frac{1}{\sqrt{\log(\|\theta\|_{1}})}\big{)},$

which implies (E.4). Above we use that $a\geq c$ and $g_{1}\asymp d_{1}\asymp
N/n$, by assumption. Precisely, in the first line, we used

$\displaystyle a\|\theta^{*}_{S}\|_{2}^{2}\asymp
a\cdot(1-N/n)^{-1}\frac{N}{n}\|\theta^{*}_{S^{c}}\|_{2}^{2}\lesssim
c\|\theta^{*}_{S^{c}}\|_{2}^{2},$

and in the second line we used

$\displaystyle\|\theta\|_{1}$
$\displaystyle\geq\sqrt{c}\|\theta_{S^{c}}^{*}\|_{1}\asymp\sqrt{c}(1-N/n)^{-1}\|\theta^{*}\|_{1}\asymp\sqrt{c}n.$

∎

With Lemma E.1 in hand, we restrict in the remainder of this section to the
setting where $P$ has unit diagonals and (E.1)–(E.4) are satisfied.

Define $v_{0}=\mathbf{1}^{\prime}\Omega\mathbf{1}$, and let
$\eta^{*}=(1/\sqrt{v_{0}})\Omega\mathbf{1}$. Recall
$\tilde{\Omega}=\Omega-\eta^{*}\eta^{*\mathsf{T}}$, and
$\tilde{\lambda}=\mathrm{tr}(\tilde{\Omega})$. Our main result concerning the
alternative is the following.

######  Theorem E.1 (Limiting behavior of SgnQ test statistic).

Suppose that the previous assumptions hold and that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$. Then under the null
hypothesis, as $n\to\infty$, $\mathbb{E}[Q]\sim 2\|\theta\|_{2}^{4}$,
$\mathrm{Var}(Q)\sim 8\|\theta\|_{2}^{8}$, and
$(Q-\mathbb{E}Q)/\sqrt{\mathrm{Var}(Q)}\to N(0,1)$ in law. Under the
alternative hypothesis, as $n\to\infty$, $\mathbb{E}Q\sim\tilde{\lambda}^{4}$
and
$\mathrm{Var}(Q)\lesssim|\tilde{\lambda}|^{6}+|\tilde{\lambda}|^{2}\lambda_{1}^{3}=o(\tilde{\lambda}^{8})$.

Following Jin et al. (2021c), we introduce some notation:

$\displaystyle\widetilde{\Omega}=\Omega-(\eta^{*})(\eta^{*})^{\prime},\qquad\mbox{where}\quad\eta^{*}=\frac{1}{\sqrt{v_{0}}}\Omega{\bf
1}_{n},\;\;v_{0}={\bf 1}_{n}^{\prime}\Omega{\bf 1}_{n};$
$\displaystyle\delta_{ij}=\eta_{i}(\eta_{j}-\tilde{\eta}_{j})+\eta_{j}(\eta_{i}-\tilde{\eta}_{i}),\qquad\mbox{where}\quad\eta=\frac{1}{\sqrt{v}}(\mathbb{E}A){\bf
1}_{n},\;\;\tilde{\eta}=\frac{1}{\sqrt{v}}A{\bf 1}_{n},\;\;v={\bf
1}_{n}^{\prime}(\mathbb{E}A){\bf 1}_{n};$ $\displaystyle
r_{ij}=(\eta_{i}^{*}\eta_{j}^{*}-\eta_{i}\eta_{j})-(\eta_{i}-\tilde{\eta}_{i})(\eta_{j}-\tilde{\eta}_{j})+(1-\frac{v}{V})\tilde{\eta}_{i}\tilde{\eta}_{j},\qquad\mbox{where}\;\;V={\bf
1}_{n}^{\prime}A{\bf 1}_{n}.$

The ideal and proxy SgnQ statistics, respectively, are defined as follows:

$\displaystyle\widetilde{Q}_{n}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}(\widetilde{\Omega}_{ij}+W_{ij})(\widetilde{\Omega}_{jk}+W_{jk})(\widetilde{\Omega}_{k\ell}+W_{k\ell})(\widetilde{\Omega}_{\ell
i}+W_{\ell i})$ (E.6) $\displaystyle Q_{n}^{*}$
$\displaystyle=\sum_{i,j,k,\ell(dist)}(\widetilde{\Omega}_{ij}+W_{ij}+\delta_{ij})(\widetilde{\Omega}_{jk}+W_{jk}+\delta_{jk})(\widetilde{\Omega}_{k\ell}+W_{k\ell}+\delta_{k\ell})(\widetilde{\Omega}_{\ell
i}+W_{\ell i}+\delta_{\ell i}).$ (E.7)

Moreover, we can express the original or real SgnQ as

$\displaystyle
Q_{n}=\sum_{i,j,k,\ell(dist)}\bigg{[}(\widetilde{\Omega}_{ij}+W_{ij}+\delta_{ij}+r_{ij})$
$\displaystyle(\widetilde{\Omega}_{jk}+W_{jk}+\delta_{jk}+r_{jk})$
$\displaystyle(\widetilde{\Omega}_{k\ell}+W_{k\ell}+\delta_{k\ell}+r_{k\ell})(\widetilde{\Omega}_{\ell
i}+W_{\ell i}+\delta_{\ell i}+r_{\ell i})\bigg{]}.$

The next theorems handle the behavior of these statistics. Together the
results imply Theorem E.1. Again, the analysis of the null carries over
directly from Jin et al. (2021c), so we only need to study the alternative.
The claims regarding the alternative follow from Lemmas E.7–E.12 below.

######  Theorem E.2 (Ideal SgnQ test statistic).

Suppose that the previous assumptions hold and that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$. Then under the null
hypothesis, as $n\to\infty$, $\mathbb{E}[\tilde{Q}]=0$ and
$\mathrm{Var}(\tilde{Q})=8\|\theta\|_{2}^{8}\cdot[1+o(1)]$. Furthermore, under
the alternative hypothesis, as $n\to\infty$,
$\mathbb{E}[\tilde{Q}]\sim\tilde{\lambda}^{4}$ and
$\mathrm{Var}(\tilde{Q})\lesssim\lambda_{1}^{4}+|\tilde{\lambda}|^{6}=o(\tilde{\lambda}^{8})$.

######  Theorem E.3 (Proxy SgnQ test statistic).

Suppose that the previous assumptions hold and that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$. Then under the null
hypothesis, as $n\to\infty$,
$|\mathbb{E}[\tilde{Q}-Q^{*}]|=o(\|\theta\|_{2}^{4})$ and
$\mathrm{Var}(\tilde{Q}-Q^{*})=o(\|\theta\|_{2}^{8})$. Furthermore, under the
alternative hypothesis, as $n\to\infty$,
$|\mathbb{E}[\tilde{Q}-Q^{*}]|\lesssim|\tilde{\lambda}|^{2}\lambda_{1}=o(\tilde{\lambda}^{4})$
and
$\mathrm{Var}(\tilde{Q}-Q^{*})\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{3}+|\tilde{\lambda}|^{6}=o(\tilde{\lambda}^{8})$.

######  Theorem E.4 (Real SgnQ test statistic).

Suppose that the previous assumptions hold and that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$. Then under the null
hypothesis, as $n\to\infty$, $|\mathbb{E}[Q-\tilde{Q}]|=o(\|\theta\|_{2}^{4})$
and $\mathrm{Var}(Q-\tilde{Q})=o(\|\theta\|_{2}^{8})$. Furthermore, under the
alternative hypothesis, as $n\to\infty$,
$|\mathbb{E}[Q-Q^{*}]|\lesssim|\tilde{\lambda}|^{2}\lambda_{1}=o(\tilde{\lambda}^{4})$
and
$\mathrm{Var}(Q-Q^{*})\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{3}=o(\tilde{\lambda}^{8})$.

The previous work Jin et al. (2021c) establishes that under the assumptions
above, if $\|\theta_{S}\|_{1}/\|\theta\|_{1}\asymp 1$, then SgnQ distinguishes
the null and alternative provided that
$|\lambda_{2}|/\sqrt{\lambda_{1}}\to\infty$. To compare with the results
above, note that $\lambda_{2}\asymp\tilde{\lambda}$ if
$\|\theta_{S}\|_{1}/\|\theta\|_{1}\asymp 1$ (c.f. Lemma E.5 of Jin et al.
(2021c)). Thus when $K=2$, our main result extends the upper bound of Jin et
al. (2021c) to the case when $\|\theta_{S}\|_{1}/\|\theta\|_{1}=o(1)$. We note
that $|\tilde{\lambda}|\gtrsim|\lambda_{2}|$ in general (see Lemma E.3 and
Corollary E.1).

The theorems above apply to the symmetric SBM. Recall that in this model,

$\displaystyle\Omega_{ij}=\begin{cases}a&\quad\text{ if }i,j\in S\\\
c&\quad\text{ if }i,j\notin S\\\ \tilde{b}=\frac{nc-(a+c)N}{n-2N}&\quad\text{
otherwise. }\end{cases}$

where $N=|S|$ and $a,b,c\in(0,1)$. To obtain this model from our DCBM, set

$\displaystyle P=\begin{pmatrix}1&\tilde{b}/\sqrt{ac}\\\
\tilde{b}/\sqrt{ac}&1\\\ \end{pmatrix},$ (E.8)

and

$\displaystyle\theta=\sqrt{a}\mathbf{1}_{S}+\sqrt{c}\mathbf{1}_{S^{c}}.$ (E.9)

The assumption (E.1) implies that $\tilde{b}\lesssim\sqrt{ac}$, which is
automatically satisfied since we assume $a\geq c$.

In SBM, it holds that $\lambda_{2}=\tilde{\lambda}$ (see Lemma E.3).
Furthermore, explicit calculations in Section E.5 reveal that

$\displaystyle\lambda_{1}$ $\displaystyle\sim nc,\text{ and }$ (E.10)
$\displaystyle\lambda_{2}$ $\displaystyle=\tilde{\lambda}\sim N(a-c).$

In addition, with $P,a,\tilde{b},c$ as above, if we have

$\theta_{i}=\begin{cases}\rho_{i}\sqrt{a}&\qquad\text{if }i\in S\\\
\rho_{i}\sqrt{c}&\qquad\text{if }i\notin S\end{cases}$

for $\rho>0$ with $\rho_{\min}\gtrsim\rho_{\max}$ in the DCBM setting, a very
similar calculation, which we omit, reveals that

$\displaystyle\lambda_{1}$ $\displaystyle\asymp nc,\text{ and }$ (E.11)
$\displaystyle\tilde{\lambda}$ $\displaystyle\asymp N(a-c).$

With the previous results of this subsection in hand (which are proved in the
remaining subsections) we justify Theorem 2.2 and Corollary 2.1.

###### Proof of Theorem 2.2.

The SgnQ test has level $\kappa$ by Theorem 2.1, so it remains to study the
type II error. Using Theorem E.1 and Lemma E.1, the fact that the type II
error tends to $0$ directly follows from Chebyshev’s inequality and the fact
that $\|\hat{\eta}\|_{2}^{2}-1\approx\|\theta\|_{2}^{2}$ with high
probability. In particular, note that since
$|\tilde{\lambda}|\gg\sqrt{\lambda_{1}}$, the expectation of SgnQ under the
alternative is much larger than its standard deviation, under the null or
alternative. We omit the details as they are very similar to the proof of
Theorem 2.6 in (Jin et al., 2021c, Supplement,pgs. 5–6). ∎

###### Proof of Corollary 2.1.

This result follows immediately from (E.11) and Theorem 2.2. ∎

####  E.2 Preliminary bounds

Define $v_{0}=\mathbf{1}^{\mathsf{T}}\Omega\mathbf{1}$, and let
$\eta^{*}=1/\sqrt{v_{0}}\cdot\Omega\mathbf{1}$. For the analysis of SgnQ, it
is important is to understand
$\tilde{\Omega}=\Omega-\eta^{*}\eta^{*\mathsf{T}}$. The next lemma establishes
that $\tilde{\Omega}$ is rank one and has a simple expression when $K=2$.

######  Lemma E.2.

Let $f=(\|\theta_{S^{c}}\|_{1},-\|\theta_{S}\|_{1})^{\mathsf{T}}$ It holds
that

$\displaystyle\tilde{\Omega}=\frac{(1-b^{2})}{v_{0}}\cdot\Theta\Pi
ff^{\mathsf{T}}\Pi^{\mathsf{T}}\Theta.$

###### Proof.

Let $\rho_{0}=\|\theta_{S}\|_{1}$ and $\rho_{1}=\|\theta_{S^{c}}\|_{1}$. Note
that

$\displaystyle(\Omega\mathbf{1})_{i}=\theta_{i}\sum_{j}\theta_{j}\pi_{i}^{\mathsf{T}}P\pi_{j}=\begin{cases}\theta_{i}(\rho_{0}+b\rho_{1})&\quad\text{
if }i\in S\\\ \theta_{i}(b\rho_{0}+\rho_{1})&\quad\text{ if }i\notin
S.\end{cases}$

Hence

$\displaystyle
v_{0}=\mathbf{1}^{\mathsf{T}}\Omega\mathbf{1}=\rho_{0}^{2}+2b\rho_{0}\rho_{1}+\rho_{1}^{2}.$

If $i,j\in S$, then

$\displaystyle\tilde{\Omega}_{ij}=\theta_{i}\theta_{j}\big{(}1-\frac{(\rho_{0}+b\rho_{1})^{2}}{v_{0}}\big{)}=\theta_{i}\theta_{j}\cdot\frac{(1-b^{2})\rho_{1}^{2}}{v_{0}}$

Similarly if $i\in S$ and $j\notin S$,

$\displaystyle\tilde{\Omega}_{ij}=\theta_{i}\theta_{j}\big{(}b-\frac{(\rho_{0}+b\rho_{1})(b\rho_{0}+\rho_{1})}{v_{0}}\big{)}=-\theta_{i}\theta_{j}\cdot\frac{(1-b^{2})\rho_{0}\rho_{1}}{v_{0}}$

and

$\displaystyle\tilde{\Omega}_{ij}=\theta_{i}\theta_{j}\big{(}1-\frac{(b\rho_{0}+\rho_{1})^{2}}{v_{0}}\big{)}=\theta_{i}\theta_{j}\cdot\frac{(1-b^{2})\rho_{0}^{2}}{v_{0}}$

if $i,j\in S^{c}$. The claim follows. ∎

Let

$\displaystyle w=\Theta\Pi
f=\theta_{S}\|\theta_{S^{c}}\|_{1}-\theta_{S^{c}}\|\theta_{S}\|_{1}=\rho_{1}\theta_{S}-\rho_{0}\theta_{S^{c}}$

Using the previous lemma, we have the rank one eigendecomposition

$\displaystyle\tilde{\Omega}=\tilde{\lambda}\tilde{\xi}\tilde{\xi}^{\mathsf{T}},$
(E.12)

where we define

$\displaystyle\tilde{\xi}$
$\displaystyle=\frac{\rho_{1}\theta_{S}-\rho_{0}\theta_{S^{c}}}{\|\rho_{1}\theta_{S}-\rho_{0}\theta_{S^{c}}\|_{2}}=\frac{\rho_{1}\theta_{S}-\rho_{0}\theta_{S^{c}}}{\sqrt{\rho_{1}^{2}\|\theta_{S}\|_{2}^{2}+\rho_{0}^{2}\|\theta_{S^{c}}\|_{2}^{2}}},\text{
and }$ (E.13) $\displaystyle\tilde{\lambda}$
$\displaystyle=\frac{(1-b^{2})}{v_{0}}\cdot\big{(}\rho_{1}^{2}\|\theta_{S}\|_{2}^{2}+\rho_{0}^{2}\|\theta_{S^{c}}\|_{2}^{2}\big{)}.$
(E.14)

Lemma E.5 of Jin et al. (2021c) implies that if
$\|\theta_{S}\|_{1}/\|\theta\|_{1}\asymp 1$, then
$\lambda_{2}\asymp\tilde{\lambda}_{1}$ . If
$\|\theta_{S}\|_{1}/\|\theta\|_{1}=o(1)$, then this guarantee may not hold.
Below, in the case $K=2$, we express $\tilde{\lambda}$ in terms of the
eigenvalues and eigenvectors of $\Omega$. This allows us to compare
$\lambda_{2}$ with $\tilde{\lambda}$ more generally, as in Corollary E.1.

######  Lemma E.3.

Let $\Omega$ have eigenvalues $\lambda_{1},\lambda_{2}$ and eigenvectors
$\xi_{1},\xi_{2}$. Let $\tilde{\lambda}$ denote the eigenvalue of
$\tilde{\Omega}$. Then

$\displaystyle\tilde{\lambda}=\frac{\lambda_{1}\lambda_{2}\big{(}\langle\xi_{1},\mathbf{1}\rangle^{2}+\langle\xi_{2},\mathbf{1}\rangle^{2}\big{)}}{\lambda_{1}\langle\xi_{1},\mathbf{1}\rangle^{2}+\lambda_{2}\langle\xi_{2},\mathbf{1}\rangle^{2}}.$
(E.15)

###### Proof.

By explicit computation,

$\displaystyle\tilde{\Omega}$
$\displaystyle=\Omega-\eta^{*}\eta^{*\mathsf{T}}$
$\displaystyle=\lambda_{1}\big{(}1-\frac{\lambda_{1}\langle\xi_{1},\mathbf{1}\rangle^{2}}{v_{0}}\big{)}\xi_{1}\xi_{1}^{\mathsf{T}}+\lambda_{2}\big{(}1-\frac{\lambda_{2}\langle\xi_{2},\mathbf{1}\rangle^{2}}{v_{0}}\big{)}\xi_{2}\xi_{2}^{\mathsf{T}}-\frac{\lambda_{1}\lambda_{2}\langle\xi_{1},\mathbf{1}\rangle\langle\xi_{2},\mathbf{1}\rangle}{v_{0}}\big{(}\xi_{1}\xi_{2}^{\mathsf{T}}\xi_{2}+\xi_{1}^{\mathsf{T}}\big{)}$
$\displaystyle=\frac{\lambda_{1}\lambda_{2}}{v_{0}}\,\big{(}\langle\xi_{2},\mathbf{1}\rangle\xi_{1}+\langle\xi_{1},\mathbf{1}\rangle\xi_{2}\big{)}\cdot\big{(}\langle\xi_{2},\mathbf{1}\rangle\xi_{1}+\langle\xi_{1},\mathbf{1}\rangle\xi_{2}\big{)}^{\mathsf{T}}.$

From (E.13) and (E.14), it follows that

$\displaystyle\tilde{\xi}$
$\displaystyle=\frac{\langle\xi_{2},\mathbf{1}\rangle\xi_{1}+\langle\xi_{1},\mathbf{1}\rangle\xi_{2}}{\sqrt{\langle\xi_{1},\mathbf{1}\rangle^{2}+\langle\xi_{2},\mathbf{1}\rangle^{2}}}$
$\displaystyle\tilde{\lambda}$
$\displaystyle=\frac{\lambda_{1}\lambda_{2}}{v_{0}}\big{(}\langle\xi_{1},\mathbf{1}\rangle^{2}+\langle\xi_{2},\mathbf{1}\rangle^{2}\big{)}.$

∎

######  Corollary E.1.

It holds that

$\displaystyle|\lambda_{2}|\lesssim|\tilde{\lambda}|\lesssim\lambda_{1}.$
(E.16)

If $\lambda_{2}\geq 0$, then

$\displaystyle\lambda_{2}\leq\tilde{\lambda}\leq\lambda_{1}$ (E.17)

###### Proof.

Suppose that $\lambda_{2}\geq 0$. Then

$\displaystyle\lambda_{2}\big{(}\langle\xi_{1},\mathbf{1}\rangle^{2}+\langle\xi_{2},\mathbf{1}\rangle^{2}\big{)}\leq\lambda_{1}\langle\xi_{1},\mathbf{1}\rangle^{2}+\lambda_{2}\langle\xi_{2},\mathbf{1}\rangle^{2}=v_{0}\leq\lambda_{1}\big{(}\langle\xi_{1},\mathbf{1}\rangle^{2}+\langle\xi_{2},\mathbf{1}\rangle^{2}\big{)},$

implies (E.17).

Suppose that $\lambda_{2}<0$. Note that

$\displaystyle\lambda_{1}\big{(}\langle\xi_{1},\mathbf{1}\rangle^{2}+\langle\xi_{2},\mathbf{1}\rangle^{2}\big{)}\geq\lambda_{1}\langle\xi_{1},\mathbf{1}\rangle^{2}+\lambda_{2}\langle\xi_{2},\mathbf{1}\rangle^{2}=v_{0}\geq
0,$

which combined with (E.15) implies that $|\tilde{\lambda}|\geq|\lambda_{2}|$.

Next,

$\displaystyle\lambda_{2}$
$\displaystyle\leq\tilde{\xi}^{\mathsf{T}}\Omega\tilde{\xi}=\tilde{\lambda}+\langle\tilde{\xi},\eta^{*}\rangle^{2},$

which implies that

$\displaystyle|\tilde{\lambda}|\leq|\lambda_{2}|+\langle\tilde{\xi},\eta^{*}\rangle^{2}\leq\lambda_{1}+\|\eta^{*}\|_{2}^{2}\lesssim\lambda_{1}+\|\theta\|_{1}^{2}\lesssim\lambda_{1},$

where the last inequality follows from Lemma E.5. ∎

The next results are frequently used in our analyis of SgnQ.

######  Lemma E.4.

Let $v=\mathbf{1}^{\mathsf{T}}(\Omega-\mathrm{diag}(\Omega))\mathbf{1}$ and
$v_{0}=\mathbf{1}^{\mathsf{T}}\Omega\mathbf{1}$. Then

$\displaystyle v_{0}\sim v\sim\|\theta\|_{1}^{2}.$ (E.18)

###### Proof.

By (E.4), $\|\theta\|_{2}^{2}=o(\|\theta\|_{1})$. By (E.3),
$\|\theta\|_{1}\to\infty$. Hence

$\displaystyle
v=\mathbf{1}^{\mathsf{T}}(\Omega-\mathrm{diag}(\Omega))\mathbf{1}=\|\theta\|_{1}^{2}-\|\theta\|_{2}^{2}\sim\|\theta\|_{1}^{2}\sim
v_{0}=\mathbf{1}^{\mathsf{T}}\Omega\mathbf{1}.$

∎

The next result is a direct corollary of Lemmas E.2 and E.4.

######  Corollary E.2.

Define $\beta\in\mathbb{R}^{n}$ by

$\displaystyle\beta=\sqrt{\frac{|1-b^{2}|}{v_{0}}}\cdot\big{(}\|\theta_{S^{c}}\|_{1}\mathbf{1}_{S}+\|\theta_{S}\|_{1}\mathbf{1}_{S^{c}}\big{)}$
(E.19)

Then

$\displaystyle|\tilde{\Omega}_{ij}|\lesssim\beta_{i}\theta_{i}\beta_{j}\theta_{j}.$
(E.20)

######  Lemma E.5.

Let $\lambda_{1}$ denote the largest eigenvalue of $\Omega$. Then

$\displaystyle\lambda_{1}\gtrsim\|\theta\|_{2}^{2}.$ (E.21)

###### Proof.

Using the universal inequality $a^{2}+b^{2}\geq\frac{1}{2}(a+b)^{2}$, we have

$\displaystyle\lambda_{1}$
$\displaystyle\geq\frac{\theta^{\mathsf{T}}\Omega\theta}{\|\theta\|_{2}^{2}}\geq\frac{1}{\|\theta\|_{2}^{2}}\cdot\sum_{i,j}\theta_{i}\theta_{j}\Omega_{ij}\geq\frac{1}{\|\theta\|_{2}^{2}}\cdot\big{(}\sum_{i,j\in
S}\theta_{i}^{2}\theta_{j}^{2}+\sum_{i,j\notin
S}\theta_{i}^{2}\theta_{j}^{2}\big{)}$
$\displaystyle\geq\frac{\|\theta_{S}\|_{2}^{4}+\|\theta_{S^{c}}\|_{2}^{4}}{\|\theta\|_{2}^{2}}\gtrsim\|\theta\|_{2}^{2}.$

∎

######  Lemma E.6.

Define $\eta=\frac{1}{\sqrt{v}}(\Omega-\mathrm{diag}(\Omega))\mathbf{1}$. Then

$\displaystyle\eta_{i}\lesssim\eta_{i}^{*}\lesssim\theta_{i}$ (E.22)

###### Proof.

The left-hand side is immediate, so we prove that
$\eta_{i}^{*}\lesssim\theta_{i}$. We have

$\displaystyle(\Omega\mathbf{1})_{i}=\begin{cases}\theta_{i}(\|\theta_{S}\|_{1}+b\|\theta_{S^{c}}\|_{1})\quad\text{if
}i\in S\\\ \theta_{i}(b\|\theta_{S}\|_{1}+\|\theta_{S^{c}}\|_{1})\quad\text{if
}i\notin S\end{cases}$

Since $\Omega_{ii}=\theta_{i}^{2}$,

$\displaystyle\sqrt{v_{0}}\cdot\eta_{i}=\begin{cases}\theta_{i}(\|\theta_{S}\|_{1}+b\|\theta_{S^{c}}\|_{1})-\theta_{i}^{2}\quad\text{if
}i\in S\\\
\theta_{i}(b\|\theta_{S}\|_{1}+\|\theta_{S^{c}}\|_{1})-\theta_{i}^{2}\quad\text{if
}i\notin S.\end{cases}$

Since $b=O(1)$, $\theta_{i}=O(1)$, and $v_{0}\gtrsim\|\theta\|_{1}^{2}$ (c.f.
Lemma E.4),

$\displaystyle\eta_{i}^{*}\lesssim\frac{\theta_{i}\|\theta\|_{1}}{\sqrt{\|\theta\|_{1}^{2}}}=\theta_{i},$

as desired. ∎

We use the bounds (E.18) – (E.22) throughout. We also use repeatedly that

$\displaystyle\|\theta\|_{p}^{p}$
$\displaystyle\lesssim\|\theta\|_{q}^{q},\text{ if }p\geq q,$ (E.23)

which holds by (E.2), and

$\displaystyle\|\beta\circ\theta\|_{2}^{2}$ $\displaystyle=|\tilde{\lambda}|$
$\displaystyle|\beta_{i}|$ $\displaystyle\lesssim 1$
$\displaystyle\|\beta\circ\theta^{\circ 2}\|_{1}$
$\displaystyle\leq\|\beta\circ\theta\|_{2}\|\theta\|_{2}\lesssim\|\theta\|_{2}^{2},$
(E.24)

where the second line holds by Cauchy–Schwarz.

####  E.3 Mean and variance of SgnQ

The previous work Jin et al. (2021c) decomposes $\tilde{Q}$ and
$\tilde{Q}-Q^{*}$ into a finite number of terms. For each term an exact
expression for its mean and variance is derived in Jin et al. (2021c) that
depends on $\theta$, $\eta$, $v$, and $\tilde{\Omega}$. These expression are
then bounded using the inequalities (E.2), (E.3), (E.18), (E.21)–(E.23), as
well as an inequality of the form

$\displaystyle|\tilde{\Omega}_{ij}|\lesssim\alpha\theta_{i}\theta_{j}.$

In our case, an inequality of this form is still valid, but it does not attain
sharp results because it does not properly capture the signal
$|\tilde{\lambda}|$ from the smaller community. Instead, we use the inequality
(E.20), followed by the bounds in (E.24) to handle terms involving
$\tilde{\Omega}$.

Therefore, for terms of $\tilde{Q}$ and $\tilde{Q}-Q^{*}$ that do not depend
on $\tilde{\Omega}$, the bounds in Jin et al. (2021c) carry over immediately.
In particular, their analysis of the null hypothesis carries over directly.
Hence we can focus solely on the alternative hypothesis.

Furthermore, any terms with zero mean in Jin et al. (2021c) also have zero
mean in our setting : for every term that is mean zero, it is simply the sum
of mean zero subterms, and each mean zero subterm is a product of independent,
centered random variables (eg, $X_{1}$ below).

#####  E.3.1 Ideal SgnQ

The previous work Jin et al. (2021c) shows that
$\tilde{Q}=X_{1}+4X_{2}+4X_{3}+2X_{4}+4X_{5}+X_{6}$, where
$X_{1},\ldots,X_{6}$ are defined in their Section G.1. For convenience, we
state explicitly the definitions of these terms.

$\displaystyle X_{1}=\sum_{i,j,k,\ell(dist)}W_{ij}W_{jk}W_{k\ell}W_{\ell
i},\qquad
X_{2}=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{ij}W_{jk}W_{k\ell}W_{\ell
i},$ $\displaystyle
X_{3}=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{ij}\widetilde{\Omega}_{jk}W_{k\ell}W_{\ell
i},\qquad\;X_{4}=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{ij}W_{jk}\widetilde{\Omega}_{k\ell}W_{\ell
i},$ $\displaystyle
X_{5}=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{ij}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}W_{\ell
i},\qquad\;\,X_{6}=\sum_{i,j,k,\ell(dist)}\widetilde{\Omega}_{ij}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}.$

Since $X_{1}$ does not depend on $\tilde{\Omega}$, the bounds for $X_{1}$
below are directly quoted from Lemma G.3 of Jin et al. (2021c). Also note that
$X_{6}$ is a non-stochastic term.

######  Lemma E.7.

Under the alternative hypothesis, we have

$\displaystyle\mathbb{E}[X_{k}]$ $\displaystyle=0\text{ for }1\leq k\leq 5,$
$\displaystyle\mathrm{Var}(X_{1})$
$\displaystyle\lesssim\|\theta\|_{2}^{8}\lesssim\lambda_{1}^{4}$
$\displaystyle\mathrm{Var}(X_{2})$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{4}\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{2}$
$\displaystyle\mathrm{Var}(X_{3})$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{8}\,\|\theta\|_{2}^{2}\lesssim|\tilde{\lambda}|^{4}\lambda_{1}$
$\displaystyle\mathrm{Var}(X_{4})$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{8}\leq|\tilde{\lambda}|^{4}$
$\displaystyle\mathrm{Var}(X_{5})$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{12}\lesssim|\tilde{\lambda}|^{6},\text{
and }$ $\displaystyle\mathbb{E}[X_{6}]$
$\displaystyle=X_{6}\sim|\tilde{\lambda}^{4}|$

Since we assume $|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$ under the
alternative hypothesis, it holds that

$\displaystyle\mathrm{Var}(\tilde{Q})$
$\displaystyle\lesssim\lambda_{1}^{4}+|\tilde{\lambda}|^{6}.$

Theorem E.2 follows directly from this bound and that
$\mathbb{E}X_{6}=\mathbb{E}\tilde{Q}\sim\tilde{\lambda}^{4}$.

#####  E.3.2 Proxy SgnQ

The previous work Jin et al. (2021c) shows that

$\displaystyle\tilde{Q}-Q^{*}=U_{a}+U_{b}+U_{c},$

where

$\displaystyle U_{a}$
$\displaystyle=4Y_{1}+8Y_{2}+4Y_{3}+8Y_{4}+4Y_{5}+4Y_{6}$ $\displaystyle
U_{b}$ $\displaystyle=4Z_{1}+2Z_{2}+8Z_{3}+4Z_{4}+4Z_{5}+2Z_{6}$
$\displaystyle U_{c}$ $\displaystyle=4T_{1}+4T_{2}+F.$

These terms are defined in Section G.2 of Jin et al. (2021c), and for
convenience, we define them explicitly below. The previous equations are
obtained by expanding carefully $\tilde{Q}$ and $Q^{*}$ as defined in (E.6)
and (E.7). Thus, the terms on the right-hand-side above are referred as post-
expansion terms, and we can analyze each one individually. Now we proceed to
their definitions.

First $Y_{1},\ldots,Y_{6}$ are defined as follows.

$\displaystyle Y_{1}=\sum_{i,j,k,\ell(dist)}\delta_{ij}W_{jk}W_{k\ell}W_{\ell
i},\qquad\;\;Y_{2}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\widetilde{\Omega}_{jk}W_{k\ell}W_{\ell
i},$ $\displaystyle
Y_{3}=\sum_{i,j,k,\ell(dist)}\delta_{ij}W_{jk}\widetilde{\Omega}_{k\ell}W_{\ell
i},\qquad\;\;\;Y_{4}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}W_{\ell
i},$ $\displaystyle
Y_{5}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\widetilde{\Omega}_{jk}W_{k\ell}\widetilde{\Omega}_{\ell
i},\qquad\quad
Y_{6}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}.$

Next, $Z_{1},\ldots,Z_{6}$ are defined as follows.

$\displaystyle
Z_{1}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\delta_{jk}W_{k\ell}W_{\ell
i},\qquad\;\;Z_{2}=\sum_{i,j,k,\ell(dist)}\delta_{ij}W_{jk}\delta_{k\ell}W_{\ell
i},$ $\displaystyle
Z_{3}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\delta_{jk}\widetilde{\Omega}_{k\ell}W_{\ell
i},\qquad\;\;\;Z_{4}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\widetilde{\Omega}_{jk}\delta_{k\ell}W_{\ell
i},$ $\displaystyle
Z_{5}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\delta_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i},\qquad\quad
Z_{6}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\widetilde{\Omega}_{jk}\delta_{k\ell}\widetilde{\Omega}_{\ell
i}.$

Last, we have the definitions of $T_{1},T_{2}$, and $F$.

$\displaystyle
T_{1}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\delta_{jk}\delta_{k\ell}W_{\ell
i},\qquad\;\;T_{2}=\sum_{i,j,k,\ell(dist)}\delta_{ij}\delta_{jk}\delta_{k\ell}\widetilde{\Omega}_{\ell
i},$ $\displaystyle
F=\sum_{i,j,k,\ell(dist)}\delta_{ij}\delta_{jk}\delta_{k\ell}\delta_{\ell i}.$

The following post-expansion terms below appear in Lemma G.5 of Jin et al.
(2021c). The term $Y_{1}$ does not depend on $\tilde{\Omega}$, so we may
directly quote the result.

######  Lemma E.8.

Under the alternative hypothesis, it holds that

$\displaystyle|\mathbb{E}Y_{1}|$ $\displaystyle=0,\qquad$
$\displaystyle\mathrm{Var}(Y_{1})\lesssim\|\theta\|_{2}^{2}\|\,\|\theta\|_{3}^{6}\lesssim\lambda_{1}^{4}$
$\displaystyle|\mathbb{E}Y_{2}|$ $\displaystyle=0,\quad$
$\displaystyle\mathrm{Var}(Y_{2})\lesssim\|\beta\circ\theta\|_{2}^{2}\,\|\theta\|_{2}^{6}\lesssim|\tilde{\lambda}|\lambda_{1}^{3}$
$\displaystyle|\mathbb{E}Y_{3}|$ $\displaystyle=0,\quad$
$\displaystyle\mathrm{Var}(Y_{3})\lesssim\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{4}\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{2}$
$\displaystyle|\mathbb{E}Y_{4}|$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}\lesssim|\tilde{\lambda}|^{2}\lambda_{1},\quad$
$\displaystyle\mathrm{Var}(Y_{4})\lesssim\frac{\|\beta\circ\theta\|_{2}^{6}\,\|\theta\|_{2}^{6}}{\|\theta\|_{1}}\lesssim|\tilde{\lambda}|^{3}\lambda_{1}^{2}$
$\displaystyle|\mathbb{E}Y_{5}|$ $\displaystyle=0,\quad$
$\displaystyle\mathrm{Var}(Y_{5})\lesssim\frac{\|\beta\circ\theta\|_{2}^{6}\,\|\theta\|_{2}^{4}}{\|\theta\|_{1}}\lesssim|\tilde{\lambda}|^{3}\lambda_{1}$
$\displaystyle|\mathbb{E}Y_{6}|$ $\displaystyle=0,\quad$
$\displaystyle\mathrm{Var}(Y_{6})\lesssim\frac{\|\beta\circ\theta\|_{2}^{12}\|\theta\|_{2}^{2}}{\|\theta\|_{1}}\lesssim|\tilde{\lambda}|^{6}.$

As a result,

$\displaystyle|\mathbb{E}U_{a}|\lesssim|\tilde{\lambda}|^{2}\lambda_{1}=o(\tilde{\lambda}^{4}).$
(E.25)

Also using Corollary E.1 and that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$, we have

$\displaystyle\mathrm{Var}(U_{a})\lesssim\lambda_{1}^{4}+|\tilde{\lambda}|^{3}\lambda_{1}^{2}+|\tilde{\lambda}|^{6}.$
(E.26)

The terms below appear in Lemma G.7 of Jin et al. (2021c). The bounds on
$Z_{1}$ and $Z_{2}$ are quoted directly from Jin et al. (2021c).

######  Lemma E.9.

Under the alternative hypothesis, it holds that

$\displaystyle|\mathbb{E}Z_{1}|$
$\displaystyle\lesssim\|\theta\|_{2}^{4}\lesssim\lambda_{1}^{2},\qquad$
$\displaystyle\mathrm{Var}(Z_{1})\lesssim\|\theta\|_{2}^{2}\,\|\theta\|_{3}^{6}\lesssim\lambda_{1}^{4}$
$\displaystyle|\mathbb{E}Z_{2}|$
$\displaystyle\lesssim\|\theta\|_{2}^{4}\lesssim\lambda_{1}^{2},\quad$
$\displaystyle\mathrm{Var}(Z_{2})\lesssim\frac{\|\theta\|_{2}^{6}\,\|\theta\|_{3}^{3}}{\|\theta\|_{1}}\lesssim\lambda_{1}^{3}$
$\displaystyle|\mathbb{E}Z_{3}|$ $\displaystyle=0,\quad$
$\displaystyle\mathrm{Var}(Z_{3})\lesssim\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{6}\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{3}$
$\displaystyle|\mathbb{E}Z_{4}|$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{2}\,\|\theta\|_{2}^{2}\lesssim|\tilde{\lambda}|\lambda_{1},\quad$
$\displaystyle\mathrm{Var}(Z_{4})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{6}}{\|\theta\|_{1}}\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{2}$
$\displaystyle|\mathbb{E}Z_{5}|$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{2}\lesssim|\tilde{\lambda}|^{2}\lambda_{1},\quad$
$\displaystyle\mathrm{Var}(Z_{5})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\,\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}\lesssim|\tilde{\lambda}|^{4}\lambda_{1}$
$\displaystyle|\mathbb{E}Z_{6}|$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}\lesssim|\tilde{\lambda}|^{2},\quad$
$\displaystyle\mathrm{Var}(Z_{6})\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\,\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}\lesssim|\tilde{\lambda}|^{4}.$

Using Corollary E.1 and the fact that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$ under the alternative
hypothesis, we have

$\displaystyle|\mathbb{E}U_{b}|$
$\displaystyle\lesssim|\tilde{\lambda}|^{2}\lambda_{1},$ (E.27)

and

$\displaystyle\mathrm{Var}(U_{b})$
$\displaystyle\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{3}.$ (E.28)

The terms below appear in Lemma G.9 of Jin et al. (2021c). The bounds on
$T_{1}$ and $F$ are quoted directly from Jin et al. (2021c) since they do not
depend on $\tilde{O}mega$.

######  Lemma E.10.

Under the alternative hypothesis, it holds that

$\displaystyle|\mathbb{E}T_{1}|$
$\displaystyle\leq\frac{\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}\lesssim\lambda_{1},\quad$
$\displaystyle\mathrm{Var}(T_{1})\lesssim\frac{\|\theta\|_{2}^{6}\,\|\theta\|_{3}^{3}}{\|\theta\|_{1}}\lesssim\lambda_{1}^{3}$
$\displaystyle|\mathbb{E}T_{2}|$
$\displaystyle\leq\frac{\|\beta\circ\theta\|_{2}^{2}\,\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}\lesssim|\tilde{\lambda}|,\quad$
$\displaystyle\mathrm{Var}(T_{2})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{2}}\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{2}$
$\displaystyle|\mathbb{E}F|$
$\displaystyle\lesssim\|\theta\|_{2}^{4}\lesssim\lambda_{1}^{2},\quad$
$\displaystyle\mathrm{Var}(F)\lesssim\frac{\|\theta\|_{2}^{10}}{\|\theta\|_{1}^{2}}\lesssim\lambda_{1}^{3}$

Using Corollary E.1 and the fact that
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$ under the alternative
hypothesis, we have

$\displaystyle|\mathbb{E}U_{c}|$ $\displaystyle\lesssim\lambda_{1}^{2},$
(E.29)

and

$\displaystyle\mathrm{Var}(U_{c})$
$\displaystyle\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{2}.$ (E.30)

Using Corollary E.1 and that $|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$,
the inequalities (E.25)–(E.30) imply Theorem E.3.

#####  E.3.3 Real SgnQ

Our first lemma regarding real SgnQ plays the part of Lemma G.11 from Jin et
al. (2021c).

######  Lemma E.11.

Under the previous assumptions, as $n\to\infty$,

  * •

Under the null hypothesis,
$|\mathbb{E}[Q^{*}-\tilde{Q}^{*}]|=o(\|\theta\|_{2}^{4})$ and
$\mathrm{Var}(Q^{*}-\tilde{Q}^{*})=o(\|\theta\|_{2}^{8})$.

  * •

Under the alternative hypothesis, if
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$, then
$|\mathbb{E}[Q^{*}-\tilde{Q}^{*}]|\lesssim|\tilde{\lambda}|^{2}\lambda_{1}$
and
$\mathrm{Var}(Q^{*}-\tilde{Q}^{*})\lesssim|\tilde{\lambda}|^{2}\lambda_{1}^{3}$.

The following lemma plays the part of Lemma G.12 from Jin et al. (2021c).

######  Lemma E.12.

Under the previous assumptions, as $n\to\infty$,

  * •

Under the null hypothesis,
$|\mathbb{E}[Q-\tilde{Q}^{*}]|=o(\|\theta\|_{2}^{4})$ and
$\mathrm{Var}(Q-\tilde{Q}^{*})=o(\|\theta\|_{2}^{8})$.

  * •

Under the alternative hypothesis, if
$|\tilde{\lambda}|/\sqrt{\lambda_{1}}\to\infty$, then
$|\mathbb{E}[Q-\tilde{Q}^{*}]|\lesssim\lambda_{1}^{2}+|\tilde{\lambda}|^{3}$
and $\mathrm{Var}(Q-\tilde{Q}^{*})\lesssim\lambda_{1}^{4}$.

####  E.4 Proofs of Lemmas E.7–E.12

#####  E.4.1 Proof strategy

First we describe our method of proof for Lemmas E.7–E.10. We borrow the
following strategy from Jin et al. (2021c). Let $T$ denote a term appearing in
one of the Lemmas E.7–E.10, which takes the general form

$\displaystyle
T=\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}}c_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}}$

where

  * •

$m=O(1)$,

  * •

$\mathcal{R}$ is a subset of $[n]^{m}$,

  * •

$c_{i_{1},\ldots,i_{m}}=\prod_{(s,s^{\prime})\in
A}\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}$ is a nonstochastic
coefficient where $A\subset[m]\times[m]$ and
$\Gamma^{(s,s^{\prime})}\in\\{\tilde{\Omega},\eta^{*}\mathbf{1}^{\mathsf{T}},\eta\mathbf{1}^{\mathsf{T}},\mathbf{1}\mathbf{1}^{\mathsf{T}}\\}$,
and

  * •

$G_{i_{1},\ldots,i_{m}}=\prod_{(s,s^{\prime})\in B}W_{i_{s},i_{s^{\prime}}}$
where $B\subset[m]\times[m]$.

Since we are studying signed quadrilateral, one can simply take $m=4$ above,
though we wish to state the lemma in a general way.

Define a canonical upper bound
$\overline{\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}}$ (up to constant
factor) on $\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}$ as follows:

$\displaystyle\overline{\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}}=\begin{cases}\beta_{i_{s}}\theta_{i_{s}}\beta_{i_{s^{\prime}}}\theta_{i_{s^{\prime}}}\quad&\text{if
}\Gamma^{(s,s^{\prime})}=\tilde{\Omega},\\\ \theta_{i_{s}}\quad&\text{if
}\Gamma^{(s,s^{\prime})}\in\\{\eta^{*}\mathbf{1}^{\mathsf{T}},\eta\mathbf{1}^{\mathsf{T}}\\}\\\
1\quad&\text{otherwise}.\end{cases}$ (E.31)

Define

$\displaystyle\overline{c_{i_{1},\ldots,i_{m}}}=\prod_{(s,s^{\prime})\in
A}\overline{\Gamma_{i_{s},i_{s^{\prime}}}^{(s,s^{\prime})}}.$ (E.32)

By Corollary E.1 and Lemma E.6,

$\displaystyle|c_{i_{1},\ldots
i_{m}}|\lesssim\overline{c_{i_{1},\ldots,i_{m}}}.$

In Jin et al. (2021c), each term $T$ is decomposed into a sum of $L=O(1)$
terms:

$\displaystyle
T=\sum_{\ell=1}^{L}T^{(L)}=\sum_{\ell=1}^{L}\,\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}^{(\ell)}}c_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}}.$
(E.33)

In our analysis below and that of Jin et al. (2021c), an upper bound
$\overline{\mathbb{E}T}$ on $|\mathbb{E}T|$ is obtained by

$\displaystyle|\mathbb{E}T|$
$\displaystyle\leq\sum_{\ell=1}^{L}|\mathbb{E}T^{(\ell)}|\leq\sum_{\ell=1}^{L}\,\,\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}^{(\ell)}}|c_{i_{1},\ldots,i_{m}}|\cdot|\mathbb{E}G_{i_{1},\ldots,i_{m}}|$
$\displaystyle\leq\sum_{\ell=1}^{L}\,\,\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}^{(\ell)}}\overline{c_{i_{1},\ldots,i_{m}}}\cdot|\mathbb{E}G_{i_{1},\ldots,i_{m}}|$
$\displaystyle=:\overline{\mathbb{E}T}.$ (E.34)

Also an upper bound $\overline{\mathrm{Var}T}$ on $\mathrm{Var}T$ is obtained
by

$\displaystyle\mathrm{Var}T$ $\displaystyle\leq
L\sum_{\ell=1}^{L}\mathrm{Var}(T^{(\ell)})$ $\displaystyle\leq
L\sum_{\ell=1}^{L}\,\,\sum_{\begin{subarray}{c}i_{1},\ldots,i_{m}\in\mathcal{R}^{(\ell)}\\\
i_{1}^{\prime},\ldots,i_{m}^{\prime}\in\mathcal{R}^{(\ell)}\end{subarray}}|c_{i_{1},\ldots,i_{m}}c_{i_{1}^{\prime},\ldots,i_{m}^{\prime}}|\cdot\big{|}\mathrm{Cov}\big{(}G_{i_{1},\ldots,i_{m}},G_{i_{1}^{\prime},\ldots,i_{m}^{\prime}}\big{)}\big{|}$
$\displaystyle\leq
L\sum_{\ell=1}^{L}\,\,\sum_{\begin{subarray}{c}i_{1},\ldots,i_{m}\in\mathcal{R}^{(\ell)}\\\
i_{1}^{\prime},\ldots,i_{m}^{\prime}\in\mathcal{R}^{(\ell)}\end{subarray}}\overline{c_{i_{1},\ldots,i_{m}}}\cdot\overline{c_{i_{1}^{\prime},\ldots,i_{m}^{\prime}}}\cdot\big{|}\mathrm{Cov}\big{(}G_{i_{1},\ldots,i_{m}},G_{i_{1}^{\prime},\ldots,i_{m}^{\prime}}\big{)}\big{|}$
$\displaystyle=:\overline{\mathrm{Var}T}.$ (E.35)

In Lemmas E.7–E.10, all stated upper bounds are obtained in this manner and
are therefore upper bounds on $\overline{\mathbb{E}T}$ and
$\overline{\mathrm{Var}T}$.

Note that the definition of $\overline{\mathbb{E}T}$ and
$\overline{\mathrm{Var}T}$ depends on the specific decomposition (E.33) of $T$
given in Jin et al. (2021c). Refer to the proofs below for details including
the explicit decomposition. Again we remark that the difference between our
setting and Jin et al. (2021c) is that the canonical upper bound on
$|\tilde{\Omega}_{ij}|$ used in Jin et al. (2021c) is of the form
$\alpha\theta_{i}\theta_{j}$ rather than the inequality
$\beta_{i}\theta_{i}\beta_{j}\theta_{j}$ which is required for our purposes.

The formalism above immediately yields the following useful fact that allows
us to transfer bounds between terms that have similar structures.

######  Lemma E.13.

Suppose that

$\displaystyle T$
$\displaystyle=\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}}c_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}},$
$\displaystyle T^{*}$
$\displaystyle=\sum_{i_{1},\ldots,i_{m}\in\mathcal{R}}c^{*}_{i_{1},\ldots,i_{m}}G_{i_{1},\ldots,i_{m}},$

where

$\displaystyle|c_{i_{1},\ldots,i_{m}}|$
$\displaystyle\lesssim\overline{c^{*}_{i_{1},\ldots,i_{m}}}$

Then

$\displaystyle|\mathbb{E}T|\lesssim\overline{\mathbb{E}[T^{*}]}$

and

$\displaystyle\mathrm{Var}\,T\lesssim\overline{\mathrm{Var}\,T^{*}}.$

In the second part of our analysis, we show that Lemmas E.11 and E.12 follow
from Lemmas E.7–E.10 and repeated applications of Lemma E.13.

#####  E.4.2 Proof of Lemma E.7

The bounds for $X_{1}$ follow immediately from Jin et al. (2021c).

In (Jin et al., 2021c, Supplement, pg.37) it is shown that
$\mathbb{E}X_{2}=0$, and

$\displaystyle\mathrm{Var}(X_{2})=2\sum_{i,j,k,\ell(dist.)}\tilde{\Omega}_{ij}^{2}\cdot\mathrm{Var}(W_{jk}W_{k\ell}W_{\ell
i}).$

Thus by (E.1) and (E.2),

$\displaystyle\mathrm{Var}(X_{2})$
$\displaystyle\lesssim\sum_{i,j,k,\ell(dist.)}\tilde{\Omega}_{ij}^{2}\cdot\mathrm{Var}(W_{jk}W_{k\ell}W_{\ell
i})\lesssim\sum_{i,j,k,\ell}\beta_{i}^{2}\theta_{i}^{2}\beta_{j}^{2}\theta_{j}^{2}\cdot\Omega_{jk}\Omega_{k\ell}\Omega_{\ell
i}$
$\displaystyle\lesssim\sum_{i,j,k,\ell}\beta_{i}^{2}\theta_{i}^{2}\beta_{j}^{2}\theta_{j}^{2}\cdot\theta_{j}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{i}=\|\beta\circ\theta\|_{2}^{4}\,\|\theta\|_{2}^{4}$

In (Jin et al., 2021c, Supplement, pg. 38) it is shown that
$\mathbb{E}X_{3}=0$ and

$\displaystyle\mathrm{Var}(X_{3})$
$\displaystyle\lesssim\sum_{i,k,\ell(dist)}\big{(}\sum_{j\notin\\{i,k,\ell\\}}\tilde{\Omega}_{ij}\tilde{\Omega}_{jk}\big{)}^{2}\cdot\mathrm{Var}(W_{k\ell}W_{\ell
i}).$

By (E.20) and (E.24),

$\displaystyle\big{(}\sum_{j\notin\\{i,k,\ell\\}}\tilde{\Omega}_{ij}\tilde{\Omega}_{jk}\big{)}^{2}$
$\displaystyle\leq\beta_{i}^{2}\theta_{i}^{2}\,\beta_{k}^{2}\theta_{k}^{2}\,\,\|\beta\circ\theta\|_{2}^{4}$

Thus by (E.1) and (E.2),

$\displaystyle\mathrm{Var}(X_{3})$
$\displaystyle\lesssim\sum_{i,k,\ell}\beta_{i}^{2}\theta_{i}^{2}\,\beta_{k}^{2}\theta_{k}^{2}\,\,\|\beta\circ\theta\|_{2}^{4}\cdot\Omega_{k\ell}\Omega_{\ell
i}\lesssim\sum_{i,k,\ell}\beta_{i}^{2}\theta_{i}^{3}\,\beta_{k}^{2}\theta_{k}^{3}\,\,\|\beta\circ\theta\|_{2}^{4}\cdot\theta_{\ell}^{2}$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{8}\,\|\theta\|_{2}^{2}.$

In (Jin et al., 2021c, Supplement, pg. 38) it is shown that
$\mathbb{E}X_{4}=0$ and

$\displaystyle\mathrm{Var}(X_{4})\lesssim\sum_{i,j,k,\ell(dist.)}\tilde{\Omega}_{ij}^{2}\tilde{\Omega}_{k\ell}^{2}\cdot\mathrm{Var}(W_{jk}W_{\ell
i}).$

By (E.1) and (E.20),

$\displaystyle\mathrm{Var}(X_{4})$
$\displaystyle\lesssim\sum_{i,j,k,\ell}\beta_{i}^{2}\theta_{i}^{2}\beta_{j}^{2}\theta_{j}^{2}\beta_{k}^{2}\theta_{k}^{2}\beta_{\ell}^{2}\theta_{\ell}^{2}\cdot\theta_{j}\theta_{k}\theta_{\ell}\theta_{i}\lesssim\|\beta\circ\theta\|_{2}^{8}.$

In (Jin et al., 2021c, Supplement, pg. 39) it is shown that
$\mathbb{E}X_{5}=0$ and

$\displaystyle\mathrm{Var}(X_{5})$
$\displaystyle=2\sum_{i<\ell}\big{(}\sum_{\begin{subarray}{c}j,k\notin\\{i,\ell\\}\\\
j\neq
k\end{subarray}}\tilde{\Omega}_{ij}\tilde{\Omega}_{jk}\tilde{\Omega}_{k\ell}\big{)}^{2}\cdot\mathrm{Var}(W_{\ell
i}).$

We have

$\displaystyle\big{|}\sum_{\begin{subarray}{c}j,k\notin\\{i,\ell\\}\\\ j\neq
k\end{subarray}}\tilde{\Omega}_{ij}\tilde{\Omega}_{jk}\tilde{\Omega}_{k\ell}\big{|}\lesssim\beta_{i}\theta_{i}\|\beta\circ\theta\|_{2}^{4}\beta_{\ell}\theta_{\ell}.$

Thus by (E.1) and (E.2),

$\displaystyle\mathrm{Var}(X_{5})\lesssim\sum_{i,\ell}\big{(}\beta_{i}\theta_{i}\|\beta\circ\theta\|_{2}^{4}\beta_{\ell}\theta_{\ell}\big{)}^{2}\cdot\theta_{\ell}\theta_{i}\lesssim\|\beta\circ\theta\|_{2}^{12}.$

Note that $X_{6}$ is a nonstochastic term. Mimicking (Jin et al., 2021c,
Supplement, pg. 39), we have by (E.24),

$\displaystyle|X_{6}-\tilde{\lambda}^{4}|$
$\displaystyle\lesssim\sum_{i,j,k,\ell(not\,dist.)}\beta_{i}^{2}\theta_{i}^{2}\beta_{j}^{2}\theta_{j}^{2}\beta_{k}^{2}\theta_{k}^{2}\beta_{\ell}^{2}\theta_{\ell}^{2}\lesssim\sum_{i,j,k}\beta_{i}^{2}\theta_{i}^{2}\beta_{j}^{2}\theta_{j}^{2}\beta_{k}^{4}\theta_{k}^{4}\lesssim\|\beta\circ\theta\|_{2}^{6}\lesssim|\tilde{\lambda}|^{3}.$

This completes the proof. ∎

#####  E.4.3 Proof of Lemma E.8

The bounds on $Y_{1}$ carry over directly from (Jin et al., 2021c, Lemma G.5).

In (Jin et al., 2021c, Supplement, pg. 43) it is shown that
$\mathbb{E}Y_{2}=0$. To study $\mathrm{Var}(Y_{2})$, we write
$Y=Y_{2a}+Y_{2b}+Y_{2c}$ where as in (Jin et al., 2021c, Supplement, pg. 43),
we define

$\displaystyle Y_{2}$ $\displaystyle=$
$\displaystyle-\frac{1}{\sqrt{v}}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\
s\neq j\end{subarray}}\eta_{i}\widetilde{\Omega}_{jk}W_{js}W_{k\ell}W_{\ell
i}$ (E.38)
$\displaystyle-\frac{1}{\sqrt{v}}\sum_{i,k,\ell(dist)}\Bigl{(}\sum_{j\notin\\{i,k,\ell\\}}\eta_{j}\widetilde{\Omega}_{jk}\Bigr{)}W^{2}_{i\ell}W_{k\ell}$
$\displaystyle-\frac{1}{\sqrt{v}}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\Bigl{(}\sum_{j\notin\\{i,k,\ell\\}}\eta_{j}\widetilde{\Omega}_{jk}\Bigr{)}W_{is}W_{k\ell}W_{\ell
i}$ $\displaystyle\equiv$ $\displaystyle Y_{2a}+Y_{2b}+Y_{2c}.$ (E.39)

There it is shown that

$\displaystyle\mathrm{Var}(Y_{2a})\lesssim\frac{1}{v}\sum_{ijk\ell
s}\big{|}\eta_{i}\tilde{\Omega}_{jk}+\eta_{i}\tilde{\Omega}_{sk}+\eta_{k}\tilde{\Omega}_{ji}+\eta_{k}\tilde{\Omega}_{si}\big{|}^{2}\cdot\mathrm{Var}(W_{js}W_{k\ell}W_{\ell
i}).$

We have by (E.22)

$\displaystyle\big{|}\eta_{i}\tilde{\Omega}_{jk}+\eta_{i}\tilde{\Omega}_{sk}+\eta_{k}\tilde{\Omega}_{ji}+\eta_{k}\tilde{\Omega}_{si}\big{|}\lesssim\theta_{i}\beta_{j}\theta_{j}\beta_{k}\theta_{k}+\theta_{i}\beta_{s}\theta_{s}\beta_{k}\theta_{k}+\theta_{k}\beta_{j}\theta_{j}\beta_{i}\theta_{i}+\theta_{k}\beta_{s}\theta_{s}\beta_{i}\theta_{i}.$

Hence by (E.1), (E.2), and (E.18),

$\displaystyle\mathrm{Var}(Y_{2a})$
$\displaystyle\lesssim\frac{1}{v}\sum_{ijk\ell
s}\big{(}\theta_{i}\beta_{j}\theta_{j}\beta_{k}\theta_{k}+\theta_{i}\beta_{s}\theta_{s}\beta_{k}\theta_{k}+\theta_{k}\beta_{j}\theta_{j}\beta_{i}\theta_{i}+\theta_{k}\beta_{s}\theta_{s}\beta_{i}\theta_{i}\big{)}^{2}\cdot\theta_{j}\theta_{s}\theta_{k}\theta_{\ell}^{2}\theta_{i}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}}$

Next, in (Jin et al., 2021c, Supplement, pg. 43), it is shown that

$\displaystyle\mathrm{Var}(Y_{2b})$
$\displaystyle\lesssim\frac{1}{v}\sum_{\begin{subarray}{c}ik\ell(dist)\\\
i^{\prime}k^{\prime}\ell^{\prime}(dist)\end{subarray}}|\alpha_{ik\ell}\alpha_{i^{\prime}k^{\prime}\ell^{\prime}}|\cdot\mathbb{E}[W_{i\ell}^{2}W_{k\ell},W_{i^{\prime}\ell^{\prime}}^{2}W_{k^{\prime}\ell^{\prime}}]$

where
$\alpha_{ik\ell}=\sum_{j\notin\\{i,k,\ell\\}}\eta_{j}\tilde{\Omega}_{jk}$. By
(E.24),

$\displaystyle|\alpha_{ik\ell}|\lesssim\|\beta\circ\theta\|_{2}\|\theta\|_{2}\,\theta_{k}.$

By (E.1), (E.18), the inequalities above, and the casework in (Jin et al.,
2021c, Supplement, pg.44) on
$E[W_{i\ell}^{2}W_{k\ell},W_{i^{\prime}\ell^{\prime}}^{2}W_{k^{\prime}\ell^{\prime}}]$,

$\displaystyle\mathrm{Var}(Y_{2b})$
$\displaystyle\lesssim\frac{1}{v}\sum_{\begin{subarray}{c}ik\ell(dist)\\\
i^{\prime}k^{\prime}\ell^{\prime}(dist)\end{subarray}}\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}\theta_{k}\theta_{k^{\prime}}\mathbb{E}[W_{i\ell}^{2}W_{k\ell},W_{i^{\prime}\ell^{\prime}}^{2}W_{k^{\prime}\ell^{\prime}}]$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}}{v}\big{(}\sum_{ik\ell}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{2}+\sum_{ik\ell
i^{\prime}}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{i^{\prime}}+\sum_{ik\ell}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\big{)}$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{6}.$

Next, in (Jin et al., 2021c, Supplement, pg.44) it is shown that

$\displaystyle\mathrm{Var}(Y_{2c})\lesssim\frac{1}{v}\sum_{\begin{subarray}{c}ik\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\beta^{2}_{ik\ell}\mathrm{Var}(W_{is}W_{k\ell}W_{\ell
i})$

where $\alpha_{ik\ell}$ is defined the same as with $Y_{2b}$. Thus

$\displaystyle\mathrm{Var}(Y_{2c})\lesssim\frac{1}{v}\sum_{\begin{subarray}{c}ik\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}\theta_{k}^{2}\cdot\theta_{k}\theta_{\ell}^{2}\theta_{s}\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{8}}{\|\theta\|_{1}}.$

Combining the results for $Y_{2a},Y_{2b},Y_{2c}$ gives the claim for
$\mathrm{Var}(Y_{2})$.

In (Jin et al., 2021c, Supplement, pg.45) it is shown that $\mathbb{E}Y_{3}=0$
and the decomposition

$\displaystyle Y_{3}$
$\displaystyle=-\frac{2}{\sqrt{v}}\sum_{i,j,k,\ell(dist)}\eta_{i}\widetilde{\Omega}_{k\ell}W^{2}_{jk}W_{\ell
i}-\frac{2}{\sqrt{v}}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\
s\notin\\{j,k\\}\end{subarray}}\eta_{i}\widetilde{\Omega}_{k\ell}W_{js}W_{jk}W_{\ell
i}$ (E.40) $\displaystyle\equiv Y_{3a}+Y_{3b},$ (E.41)

is introduced. There it is shown that

$\mathrm{Var}(Y_{3a})=\frac{4}{v}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\
i^{\prime},j^{\prime},k^{\prime},\ell^{\prime}(dist)\end{subarray}}(\eta_{i}\widetilde{\Omega}_{k\ell}\eta_{i^{\prime}}\widetilde{\Omega}_{k^{\prime}\ell^{\prime}})\cdot\mathbb{E}[W^{2}_{jk}W_{\ell
i}W^{2}_{j^{\prime}k^{\prime}}W_{\ell^{\prime}i^{\prime}}].$

Using (E.1), (E.2) (E.24) and the casework in (Jin et al., 2021c, Supplement,
pg.45),

$\displaystyle\mathrm{Var}(Y_{3a})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{2}}\bigg{(}\sum_{ijk\ell}[\beta_{k}^{2}\beta_{\ell}^{2}+\beta_{i}\beta_{j}\beta_{k}\beta_{\ell}]\theta_{i}^{2}\theta_{j}^{2}\theta_{k}^{2}\theta_{\ell}^{2}+\sum_{ijk\ell
j^{\prime}k^{\prime}}\beta_{k}\beta_{\ell}^{2}\beta_{k^{\prime}}\theta_{i}^{3}\theta_{j}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{j^{\prime}}\theta_{k^{\prime}}^{2}\bigg{)}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}$

Similar to the study of $Y_{2a}$ we have

$\displaystyle\mathrm{Var}(Y_{3b})$
$\displaystyle\lesssim\frac{1}{v}\sum_{ijk\ell
s}\big{(}\theta_{i}\beta_{k}\theta_{k}\beta_{\ell}\theta_{\ell}+\theta_{\ell}\beta_{k}\theta_{k}\beta_{i}\theta_{i}+\theta_{i}\beta_{s}\theta_{s}\beta_{\ell}\theta_{\ell}+\theta_{\ell}\beta_{s}\theta_{s}\beta_{i}\theta_{i}\big{)}^{2}\cdot\mathrm{Var}(W_{sj}W_{jk}W_{\ell
i})$ $\displaystyle\lesssim\frac{1}{v}\sum_{ijk\ell
s}\big{(}\theta_{i}\beta_{k}\theta_{k}\beta_{\ell}\theta_{\ell}+\theta_{\ell}\beta_{k}\theta_{k}\beta_{i}\theta_{i}+\theta_{i}\beta_{s}\theta_{s}\beta_{\ell}\theta_{\ell}+\theta_{\ell}\beta_{s}\theta_{s}\beta_{i}\theta_{i}\big{)}^{2}\cdot\theta_{s}\theta_{j}^{2}\theta_{k}\theta_{\ell}\theta_{i}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}}.$

Combining the bounds on $\mathrm{Var}(Y_{3a})$ and $\mathrm{Var}(Y_{3b})$
yields the desired bound on $\mathrm{Var}(Y_{3})$.

Following (Jin et al., 2021c, Supplement, pg.46) we obtain the decomposition

$\displaystyle Y_{4}$
$\displaystyle=-\frac{1}{\sqrt{v}}\sum_{\begin{subarray}{c}i,j,\ell(dist)\\\
s\neq
j\end{subarray}}\Bigl{(}\sum_{k\notin\\{i,j,\ell\\}}\eta_{i}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\Bigr{)}W_{js}W_{\ell
i}-\frac{1}{\sqrt{v}}\sum_{\begin{subarray}{c}i,\ell(dist)\\\ s\neq
i\end{subarray}}\Bigl{(}\sum_{j,k\notin\\{i,\ell\\}}\eta_{j}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\Bigr{)}W_{is}W_{\ell
i}$ $\displaystyle\equiv Y_{4a}+Y_{4b}.$

First we study $Y_{4a}$, which is shown in Jin et al. (2021c) to have zero
mean and satisfy the following:

$\displaystyle\mathrm{Var}(Y_{4a})$
$\displaystyle\lesssim\frac{1}{v}\sum_{\begin{subarray}{c}ij\ell(dist)\\\
s\neq j\end{subarray}}\alpha_{ij\ell}^{2}\mathrm{Var}(W_{js}W_{\ell i})$

where
$\alpha_{ij\ell}=\sum_{k\notin\\{i,j,\ell\\}}\eta_{i}\tilde{\Omega}_{jk}\tilde{\Omega}_{k\ell}$.
Simlar to previous arguments, we have

$\displaystyle\mathrm{Var}(Y_{4a})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{2}}\sum_{ij\ell
s}\theta_{i}^{2}(\beta_{j}\theta_{j})^{2}(\beta_{\ell}\theta_{\ell})^{2}\|\beta\circ\theta\|_{2}^{4}\cdot\theta_{i}\theta_{j}\theta_{\ell}\theta_{s}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}}{\|\theta\|_{1}}.$

Next we study $Y_{4b}$ using the decomposition

$Y_{4b}=-\frac{1}{\sqrt{v}}\sum_{i,\ell(dist)}\beta_{i\ell}W^{2}_{\ell
i}-\frac{1}{\sqrt{v}}\sum_{\begin{subarray}{c}i,\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\beta_{i\ell}W_{is}W_{\ell
i}\equiv\widetilde{Y}_{4b}+Y_{4b}^{*}.$

from (Jin et al., 2021c, Supplement,pg.47). There it is shown that only
$\mathbb{E}\tilde{Y}_{4b}$ is nonzero and

$\displaystyle|\mathbb{E}\tilde{Y}_{4b}|\lesssim\frac{1}{\|\theta\|_{1}}\sum_{i,\ell}|\alpha_{i\ell}|\theta_{i}\theta_{\ell}.$

where
$\alpha_{i,\ell}=\sum_{j,k\notin\\{i,\ell\\}}\eta_{j}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}$.
In our case, we derive from (E.24),

$\displaystyle|\alpha_{i\ell}|\lesssim\beta_{\ell}\theta_{\ell}\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}.$

Using similar arguments from before,

$\displaystyle|\mathbb{E}\tilde{Y}_{4b}|\lesssim\frac{1}{\|\theta\|_{1}}\sum_{i\ell}\beta_{\ell}\theta_{\ell}\|\beta\circ\theta\|_{2}^{3}\|\theta\|_{2}\cdot\theta_{i}\theta_{\ell}\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}.$

Now we study $\mathrm{Var}(Y_{4b})$. Using the bound above on
$|\alpha_{i\ell}|$ and direct calculations,

$\displaystyle\mathrm{Var}(\widetilde{Y}_{4b})$
$\displaystyle=\frac{2}{v}\sum_{i,\ell(dist)}\alpha^{2}_{i\ell}\cdot\mathrm{Var}(W^{2}_{i\ell})\lesssim\frac{1}{\|\theta\|^{2}_{1}}\sum_{i,\ell}\beta_{\ell}^{2}\theta_{\ell}^{2}\|\beta\circ\theta\|_{2}^{6}\|\theta\|_{2}^{2}\cdot\theta_{i}\theta_{\ell}\lesssim\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{2}}{\|\theta\|_{1}},$
$\displaystyle\mathrm{Var}(Y^{*}_{4b})$
$\displaystyle\leq\frac{1}{v}\sum_{\begin{subarray}{c}i,\ell(dist)\\\
s\notin\\{i,\ell\\}\end{subarray}}\alpha^{2}_{i\ell}\cdot\mathrm{Var}(W_{is}W_{\ell
i})\leq\frac{1}{\|\theta\|_{1}^{2}}\sum_{i,\ell,s}\beta_{\ell}^{2}\theta_{\ell}^{2}\|\beta\circ\theta\|_{2}^{6}\|\theta\|_{2}^{2}\cdot\theta_{i}^{2}\theta_{\ell}\theta_{s}\leq\frac{\|\beta\circ\theta\|_{2}^{8}\|\theta\|_{2}^{4}}{\|\theta\|_{1}}.$

Combining the results above yields the required bounds on $\mathbb{E}Y_{4b}$
and $\mathrm{Var}(Y_{4b})$.

In (Jin et al., 2021c, Supplement, pg.48) it is shown that $\mathbb{E}Y_{5}=0$
and

$\displaystyle\mathrm{Var}(Y_{5})$
$\displaystyle\lesssim\frac{1}{v}\sum_{\begin{subarray}{c}j,k,\ell(dist)\\\
s\neq j\end{subarray}}\alpha^{2}_{jk\ell}\cdot\mathrm{Var}(W_{js}W_{k\ell})$

where

$\displaystyle\alpha_{jk\ell}\equiv\sum_{i\notin\\{j,k,\ell\\}}\eta_{i}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{\ell
i}.$

We have using (E.20), (E.24) and the triangle inequality,

$\displaystyle|\alpha_{jk\ell}|\lesssim\|\theta\|_{2}^{2}(\beta_{j}\theta_{j})(\beta_{k}\theta_{k})(\beta_{\ell}\theta_{\ell}).$

Thus, by similar arguments to before,

$\displaystyle\mathrm{Var}(Y_{5})\lesssim\frac{1}{\|\theta\|_{1}^{2}}\sum_{jk\ell}\big{(}\|\theta\|_{2}^{4}(\beta_{j}\theta_{j})^{2}(\beta_{k}\theta_{k})^{2}(\beta_{\ell}\theta_{\ell})^{2}\big{)}\theta_{j}\theta_{s}\theta_{k}\theta_{\ell}\lesssim\frac{\|\theta\|_{2}^{4}\|\beta\circ\theta\|_{2}^{6}}{\|\theta\|_{1}}.$

Next, in (Jin et al., 2021c, Supplement, pg.49) it is shown that
$\mathbb{E}Y_{6}=0$ and

$\displaystyle\mathrm{Var}(Y_{6})$
$\displaystyle=\frac{8}{v}\sum_{j,s(dist)}\Bigl{(}\sum_{i,k,\ell(dist)\notin\\{j\\}}\eta_{i}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}\Bigr{)}^{2}\cdot\mathrm{Var}(W_{js}).$

We have using (E.20), (E.24) and the triangle inequality,

$\displaystyle\big{|}\sum_{i,k,\ell(dist)\notin\\{j\\}}\eta_{i}\widetilde{\Omega}_{jk}\widetilde{\Omega}_{k\ell}\widetilde{\Omega}_{\ell
i}\big{|}\lesssim\beta_{j}\theta_{j}\|\beta\circ\theta\|_{2}^{5}\|\theta\|_{2}.$

Thus

$\displaystyle\mathrm{Var}(Y_{6})\lesssim\frac{1}{\|\theta\|_{1}^{2}}\sum_{j,s}\big{(}\beta_{j}^{2}\theta_{j}^{2}\|\beta\circ\theta\|_{2}^{10}\|\theta\|_{2}^{2}\big{)}\theta_{j}\theta_{s}\lesssim\frac{\|\beta\circ\theta\|_{2}^{12}\|\theta\|_{2}^{2}}{\|\theta\|_{1}}.$

This completes the proof. ∎

#####  E.4.4 Proof of Lemma E.9

The bounds on $Z_{1}$ and $Z_{2}$ carry over directly from (Jin et al., 2021c,
Lemma G.7) since neither term depends on $\tilde{\Omega}$.

We consider $Z_{3}$. In (Jin et al., 2021c, Supplement, pg.61), the
decomposition

$\displaystyle Z_{3}=$ $\displaystyle\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})\eta_{j}(\eta_{k}-\tilde{\eta}_{k})\widetilde{\Omega}_{k\ell}W_{\ell
i}+\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})^{2}\eta_{k}\widetilde{\Omega}_{k\ell}W_{\ell
i}$ (E.42) $\displaystyle+\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{i}-\tilde{\eta}_{i})\eta^{2}_{j}(\eta_{k}-\tilde{\eta}_{k})\widetilde{\Omega}_{k\ell}W_{\ell
i}+\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{i}-\tilde{\eta}_{i})\eta_{j}(\eta_{j}-\tilde{\eta}_{j})\eta_{k}\widetilde{\Omega}_{k\ell}W_{\ell
i}$ (E.43) $\displaystyle\equiv Z_{3a}+Z_{3b}+Z_{3c}+Z_{3d}.$ (E.44)

is introduced. We study each term separately.

In (Jin et al., 2021c, Supplement, pg.61) it is shown that
$\mathbb{E}Z_{3a}=0$ and the decomposition

$\displaystyle Z_{3a}$
$\displaystyle=\frac{1}{v}\sum_{i,j,k,\ell(dist)}\alpha_{ijk\ell}W^{2}_{jk}W_{\ell
i}+\frac{1}{v}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\ s\neq j,t\neq
k,(s,t)\neq(k,j)\end{subarray}}\alpha_{ijk\ell}W_{js}W_{kt}W_{\ell i}$
$\displaystyle\equiv\widetilde{Z}_{3a}+Z^{*}_{3a}.$

is introduced, where
$\alpha_{ijk\ell}\equiv\eta_{i}\eta_{j}\tilde{\Omega}_{k\ell}$. Then

$\displaystyle\mathrm{Var}(\tilde{Z}_{3a})\lesssim\sum_{\begin{subarray}{c}ijk\ell(dist)\\\
i^{\prime}j^{\prime}k^{\prime}\ell^{\prime}(dist)\end{subarray}}|\alpha_{ijk\ell}||\alpha_{i^{\prime}k^{\prime}j^{\prime}\ell^{\prime}}|\cdot|\mathrm{Cov}(W^{2}_{jk}W_{\ell
i},W_{j^{\prime}k^{\prime}}^{2}W_{\ell^{\prime}i^{\prime}})|.$

Using the casework in (Jin et al., 2021c, Supplement, pg.62), (E.1), (E.2),
and (E.24), we obtain

$\displaystyle\mathrm{Var}(\tilde{Z}_{3a})$
$\displaystyle\lesssim\frac{1}{v^{2}}\big{(}\sum_{ijk\ell}[\beta_{k}^{2}\beta_{\ell}^{2}+\beta_{k}\beta_{\ell}\beta_{i}\beta_{j}]\theta_{i}^{3}\theta_{j}^{3}\theta_{k}^{3}\theta_{\ell}^{3}+\sum_{ijk\ell
j^{\prime}k^{\prime}}\beta_{k}\beta_{\ell}^{2}\beta_{k^{\prime}}\theta_{i}^{3}\theta_{j}^{2}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{j^{\prime}}^{2}\theta_{k^{\prime}}^{2}\big{)}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{4}}.$

Similarly,

$\displaystyle\mathrm{Var}(Z_{3a}^{*})$
$\displaystyle\lesssim\frac{1}{v^{2}}\bigg{(}\sum_{ijk\ell
st}\beta_{k}^{2}\beta_{\ell}^{2}\theta_{i}^{3}\theta_{j}^{3}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{s}\theta_{t}+\sum_{ijk\ell
st}[\beta_{k}^{2}\beta_{\ell}\beta_{j}+\beta_{k}\beta_{\ell}^{2}\beta_{j}]\theta_{i}^{2}\theta_{j}^{3}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{s}^{2}\theta_{t}\bigg{)}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\|\theta\|_{1}^{2}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}\|\theta\|_{1}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{2}}.$

It follows that

$\displaystyle\mathrm{Var}(Z_{3a})\lesssim\|\beta\circ\theta\|_{2}^{4}.$

Next, in (Jin et al., 2021c, Supplement, pg.63), it is shown that
$\mathbb{E}Z_{3b}]=0$ and the decomposition

$Z_{3b}=\frac{1}{v}\sum_{\begin{subarray}{c}i,j,\ell(dist)\\\ s\neq
j\end{subarray}}\beta_{ij\ell}W^{2}_{js}W_{\ell
i}+\frac{1}{v}\sum_{\begin{subarray}{c}i,j,\ell(dist)\\\
s,t(dist)\notin\\{j\\}\end{subarray}}\beta_{ij\ell}W_{js}W_{jt}W_{\ell
i}\equiv\widetilde{Z}_{3b}+Z^{*}_{3b}.$

is given. Using (Jin et al., 2021c, Supplement, pg.63) we have

$\displaystyle\mathrm{Var}(\tilde{Z}_{3b})$
$\displaystyle\lesssim\sum_{\begin{subarray}{c}i,j,\ell,s,t\\\
i^{\prime},j^{\prime},\ell^{\prime},s^{\prime},t^{\prime}\end{subarray}}|\alpha_{ij\ell}||\alpha_{i^{\prime}j^{\prime}\ell^{\prime}}||\mathrm{Cov}(W_{js}^{2}W_{\ell_{i}},W_{j^{\prime}s}^{\prime
2}W_{\ell^{\prime}i^{\prime}})|.$

where

$\displaystyle\alpha_{ij\ell}=\sum_{k\notin\\{i,j,\ell\\}}\eta_{i}\eta_{k}\widetilde{\Omega}_{k\ell}.$

Using (E.24), (E.18), and similar arguments to before,

$\displaystyle|\alpha_{ij\ell}|\lesssim\theta_{i}(\beta_{\ell}\theta_{\ell})\|\theta\|_{2}^{2}.$

By the casework in (Jin et al., 2021c, Supplement, pg.63), (E.1), and (E.2),

$\displaystyle\mathrm{Var}(\tilde{Z}_{3b})$
$\displaystyle\lesssim\frac{1}{v^{2}}\bigg{(}\sum_{ij\ell
s}\beta_{\ell}^{2}\|\theta\|_{2}^{4}\theta_{i}^{3}\theta_{j}\theta_{\ell}^{3}\theta_{s}+\sum_{ij\ell
sj^{\prime}s^{\prime}}\beta_{\ell}^{2}\|\theta\|_{2}^{4}\theta_{i}^{3}\theta_{j}\theta_{\ell}^{3}\theta_{s}\theta_{j^{\prime}}\theta_{s^{\prime}}+\sum_{ij\ell
s}\beta_{\ell}\beta_{j}\|\theta\|_{2}^{4}\theta_{i}^{2}\theta_{j}^{2}\theta_{\ell}^{2}\theta_{s}^{2}\bigg{)}$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{6}\|\theta\|_{1}+\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{6}\|\theta\|_{1}^{3}+\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{8}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{6}}{\|\theta\|_{1}}.$

By a similar argument,

$\displaystyle\mathrm{Var}(Z_{3b}^{*})\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{8}}{\|\theta\|_{1}}.$

Hence by (E.2),

$\displaystyle\mathrm{Var}(Z_{3b})\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{8}}{\|\theta\|_{1}}\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{6}.$

For $Z_{3c}$, in (Jin et al., 2021c, Supplement, pg.64), it is shown that
$\mathbb{E}Z_{3c}=0$ and the decomposition

$Z_{3c}=\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\ t\neq
k\end{subarray}}\alpha_{ik\ell}W^{2}_{i\ell}W_{kt}+\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
s\notin\\{i,\ell\\},t\neq k\end{subarray}}\alpha_{ik\ell}W_{is}W_{kt}W_{\ell
i}\equiv\widetilde{Z}_{3c}+Z^{*}_{3c}.$

is given. We have

$\displaystyle|\alpha_{ik\ell}|=|\sum_{j\notin\\{i,k,\ell\\}}\eta_{j}^{2}\widetilde{\Omega}_{k\ell}|\lesssim(\beta_{k}\theta_{k})(\beta_{\ell}\theta_{\ell})\|\theta\|_{2}^{2}.$

By the casework in (Jin et al., 2021c, Supplement, pg.65)

$\displaystyle\mathrm{Var}(\tilde{Z}_{3c})$
$\displaystyle\lesssim\sum_{\begin{subarray}{c}ik\ell(dist)\\\
s\notin\\{i,\ell\\},t\neq
k\end{subarray}}\sum_{\begin{subarray}{c}i^{\prime}k^{\prime}\ell^{\prime}(dist)\\\
s^{\prime}\notin\\{i^{\prime},\ell^{\prime}\\},t^{\prime}\neq
k^{\prime}\end{subarray}}|\alpha_{ik\ell}\alpha_{i^{\prime}k^{\prime}\ell^{\prime}}||\mathbb{E}W_{i\ell}^{2}W_{kt}W_{i^{\prime}\ell^{\prime}}^{2}W_{k^{\prime}t^{\prime}}|$
$\displaystyle\lesssim\frac{\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\sum_{ik\ell
t}\bigg{[}\beta_{k}^{2}\beta_{\ell}^{2}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{t}+\beta_{k}^{2}\beta_{\ell}\beta_{i}\theta_{i}^{2}\theta_{k}^{3}\theta_{\ell}^{2}\theta_{t}+\beta_{k}\beta_{\ell}^{2}\beta_{t}\theta_{i}^{1}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{t}^{2}$
$\displaystyle\quad+\beta_{k}\beta_{\ell}\beta_{t}\beta_{i}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}+\beta_{k}^{2}\beta_{\ell}\beta_{i}\theta_{i}^{2}\theta_{k}^{3}\theta_{\ell}^{2}\theta_{t}^{1}+\beta_{k}\beta_{\ell}^{2}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{t}^{2}+\beta_{k}^{2}\beta_{\ell}^{2}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{t}\bigg{]}$
$\displaystyle\quad+\sum_{ik\ell
ti^{\prime}\ell^{\prime}}\bigg{[}\beta_{k}^{2}\beta_{\ell}\beta_{\ell^{\prime}}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{2}\theta_{t}\theta_{i^{\prime}}\theta_{\ell^{\prime}}^{2}+\beta_{k}\beta_{\ell}\beta_{\ell^{\prime}}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}\theta_{i^{\prime}}\theta_{\ell^{\prime}}^{2}\bigg{]}$

We have by (E.2) and (E.24) that

$\displaystyle\sum_{ik\ell
t}\bigg{[}\beta_{k}^{2}\beta_{\ell}^{2}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{t}+$
$\displaystyle\beta_{k}^{2}\beta_{\ell}\beta_{i}\theta_{i}^{2}\theta_{k}^{3}\theta_{\ell}^{2}\theta_{t}+\beta_{k}\beta_{\ell}^{2}\beta_{t}\theta_{i}^{1}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{t}^{2}+\beta_{k}\beta_{\ell}\beta_{t}\beta_{i}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}$
$\displaystyle\quad+\beta_{k}^{2}\beta_{\ell}\beta_{i}\theta_{i}^{2}\theta_{k}^{3}\theta_{\ell}^{2}\theta_{t}^{1}+\beta_{k}\beta_{\ell}^{2}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{t}^{2}+\beta_{k}^{2}\beta_{\ell}^{2}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{3}\theta_{t}\bigg{]}$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{1}^{2}+\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}\|\theta\|_{1}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{1}^{2}$

and

$\displaystyle\sum_{ik\ell
ti^{\prime}\ell^{\prime}}\bigg{[}\beta_{k}^{2}\beta_{\ell}\beta_{\ell^{\prime}}\theta_{i}\theta_{k}^{3}\theta_{\ell}^{2}\theta_{t}\theta_{i^{\prime}}\theta_{\ell^{\prime}}^{2}+\beta_{k}\beta_{\ell}\beta_{\ell^{\prime}}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}\theta_{i^{\prime}}\theta_{\ell^{\prime}}^{2}\bigg{]}\lesssim\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}\|\theta\|_{1}^{3}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\|\theta\|_{1}^{2}$

Thus

$\displaystyle\mathrm{Var}(\tilde{Z}_{3c})$
$\displaystyle\lesssim\frac{\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{1}^{2}+\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}\|\theta\|_{1}^{3}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\|\theta\|_{1}^{2}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}}$

To study $Z_{3c}^{*}$, in (Jin et al., 2021c, Supplement, pg.65) the
decomposition

$Z_{3c}^{*}=\frac{1}{v}\sum_{i,k,\ell(dist)}\alpha_{ik\ell}W_{ik}^{2}W_{\ell
i}+\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
s\notin\\{i,\ell\\},t\neq
k,(s,t)\neq(k,i)\end{subarray}}\alpha_{ik\ell}W_{is}W_{kt}W_{\ell i}\equiv
Z_{3c,1}^{*}+Z_{3c,2}^{*}$

is used, where recall
$\alpha_{ik\ell}=\sum_{j\notin\\{i,k,\ell\\}}\eta_{j}^{2}\widetilde{\Omega}_{k\ell}$.
Using a similar argument as before, we have

$\displaystyle\mathrm{Var}(Z_{3c,1}^{*})$
$\displaystyle\lesssim\frac{\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\bigg{(}\sum_{ik\ell}\beta_{k}^{2}\beta_{\ell}^{2}\theta_{i}^{2}\theta_{k}^{3}\theta_{\ell}^{3}+\sum_{ik\ell
k^{\prime}}[\beta_{k}\beta_{k^{\prime}}\beta_{\ell}^{2}+\beta_{k}\beta_{k^{\prime}}\beta_{i}\beta_{\ell}]\theta_{i}^{3}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{k^{\prime}}^{2}\bigg{)}$
$\displaystyle\lesssim\frac{\|\theta\|_{2}^{4}}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{2}+\|\theta\|_{2}^{4}\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{3}^{3}+\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{4}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{10}}{\|\theta\|_{1}^{4}}.$

We omit the argument for $Z_{3c,2}^{*}$ as it is similar and simply state the
bound:

$\displaystyle\mathrm{Var}(Z_{3c,2}^{*})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

Combining the results for $\tilde{Z}_{3c}$ and $Z_{3c}^{*}$, we have

$\displaystyle\mathrm{Var}(Z_{3c})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}}\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}.$

Next we study $Z_{3d}$, which is defined as

$Z_{3d}=\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}(\eta_{k}\eta_{j}\tilde{\Omega}_{j\ell})(\eta_{i}-\tilde{\eta}_{i})(\eta_{k}-\tilde{\eta}_{k})W_{\ell
i}=\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\ s\neq i,t\neq
k\end{subarray}}\alpha_{ik\ell}W_{is}W_{kt}W_{\ell i}$

where
$\alpha_{ik\ell}=\sum_{j\notin\\{i,k,\ell\\}}\eta_{k}\eta_{j}\tilde{\Omega}_{j\ell}$.
We see that $\mathbb{E}Z_{3d}=0$. To study the variance, we use a similar
decomposition to that of $Z_{3c}$. Write

$\displaystyle Z_{3d}=\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
t\neq
k\end{subarray}}\alpha_{ik\ell}W^{2}_{i\ell}W_{kt}+\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
s\notin\\{i,\ell\\},t\neq k\end{subarray}}\alpha_{ik\ell}W_{is}W_{kt}W_{\ell
i}\equiv\widetilde{Z}_{3d}+Z^{*}_{3d}.$

Mimicking the arguments for $\widetilde{Z}_{3c}$ and $Z^{*}_{3c}$ we obtain

$\displaystyle\mathrm{Var}(\tilde{Z}_{3d})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}},$

and

$\displaystyle\mathrm{Var}(Z^{*}_{3d})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{10}}{\|\theta\|_{1}^{4}}.$

Hence

$\displaystyle\mathrm{Var}(Z_{3d})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}}.$

Combining the results for $Z_{3a},\ldots,Z_{3d}$, we have

$\displaystyle\mathbb{E}Z_{3}=0,\quad\mathrm{Var}(Z_{3})$
$\displaystyle\lesssim\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}.$

We proceed to study $Z_{4}$. In (Jin et al., 2021c, Supplement,pg.67) the
following decomposition is given:

$\displaystyle Z_{4}$
$\displaystyle=2\sum_{i,j,k,\ell(dist)}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})\widetilde{\Omega}_{jk}\eta_{k}(\eta_{\ell}-\tilde{\eta}_{\ell})W_{\ell
i}$ (E.45)
$\displaystyle+\sum_{i,j,k,\ell(dist)}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})\widetilde{\Omega}_{jk}(\eta_{k}-\tilde{\eta}_{k})\eta_{\ell}W_{\ell
i}$ (E.46)
$\displaystyle+\sum_{i,j,k,\ell(dist)}(\eta_{i}-\tilde{\eta}_{i})\eta_{j}\widetilde{\Omega}_{jk}\eta_{k}(\eta_{\ell}-\tilde{\eta}_{\ell})W_{\ell
i}$ (E.47) $\displaystyle\equiv Z_{4a}+Z_{4b}+Z_{4c}.$ (E.48)

There it is shown that $\mathbb{E}Z_{4a}=0$. To study $\mathrm{Var}(Z_{4a})$,
we note that $Z_{4a}$ and $Z_{3c}$ have similar structure. In particular we
have the decomposition

$\displaystyle Z_{4a}=\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
t\neq
k\end{subarray}}\alpha_{ik\ell}W^{2}_{i\ell}W_{kt}+\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
s\notin\\{i,\ell\\},t\neq k\end{subarray}}\alpha_{ik\ell}W_{is}W_{kt}W_{\ell
i}\equiv\widetilde{Z}_{4a}+Z^{*}_{4a}.$

where
$\alpha_{ik\ell}=\sum_{j\notin\\{i,k,\ell\\}}\eta_{j}\eta_{\ell}\tilde{\Omega}_{k\ell}$.
Mimicking the argument for $\tilde{Z}_{3c}$ we have

$\displaystyle\mathrm{Var}(\tilde{Z}_{4a})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}}{\|\theta\|_{1}^{4}}\bigg{(}\sum_{ik\ell
t}\big{[}\beta_{k}^{2}(\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}+\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t})+\beta_{k}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}+\beta_{k}\beta_{t}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}$
$\displaystyle\quad+\beta_{k}^{2}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}+\beta_{k}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}\big{]}+\sum_{ik\ell
ti^{\prime}\ell^{\prime}}\big{[}\beta_{k}^{2}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}\theta_{i^{\prime}}\theta_{\ell^{\prime}}^{2}+\beta_{k}\beta_{t}\theta_{i}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{t}^{2}\theta_{i^{\prime}}\theta_{\ell^{\prime}}^{2}\big{]}\bigg{)}$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}}{\|\theta\|_{1}^{4}}\big{(}\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}\|\theta\|_{1}+\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}\|\theta\|_{1}+\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}\|\theta\|_{1}^{3}+$
$\displaystyle\quad\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{4}\|\theta\|_{1}^{2}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}}.$

For $\tilde{Z}_{4a}^{*}$ we adapt the decomposition used for
$\tilde{Z}_{4c}^{*}$:

$Z_{4a}^{*}=\frac{1}{v}\sum_{i,k,\ell(dist)}\alpha_{ik\ell}W_{ik}^{2}W_{\ell
i}+\frac{1}{v}\sum_{\begin{subarray}{c}i,k,\ell(dist)\\\
s\notin\\{i,\ell\\},t\neq
k,(s,t)\neq(k,i)\end{subarray}}\alpha_{ik\ell}W_{is}W_{kt}W_{\ell
i}=:Z_{4a,1}^{*}+Z_{4a,2}^{*}$

Mimicking the argument for $Z_{3c,1}^{*}$ and $Z_{3c,2}^{*}$, we have

$\displaystyle\mathrm{Var}(Z_{4a,1}^{*})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}}{\|\theta\|_{1}^{4}}\big{(}\sum_{ik\ell}\beta_{k}^{2}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}+\sum_{ik\ell
k^{\prime}}\beta_{k}\beta_{k^{\prime}}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{k^{\prime}}^{2}\big{)}\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{8}}{\|\theta\|_{1}^{4}},$

and

$\displaystyle\mathrm{Var}(Z_{4a,2}^{*})$
$\displaystyle\lesssim\frac{\|\beta\circ\theta\|_{2}^{2}\|\theta\|_{2}^{2}}{\|\theta\|_{1}^{4}}\sum_{ik\ell
st}\big{[}\beta_{k}^{2}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{s}\theta_{t}+\beta_{k}\beta_{t}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{s}\theta_{t}^{2}+\beta_{k}\beta_{s}\theta_{i}^{2}\theta_{k}^{2}\theta_{\ell}^{2}\theta_{s}^{2}\theta_{t}^{2}\big{]}$
$\displaystyle\lesssim\frac{\|\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}^{2}}.$

It follows that

$\displaystyle\mathrm{Var}(Z_{4a})\lesssim\frac{\|\beta\circ\theta\|_{2}^{4}\|\theta\|_{2}^{6}}{\|\theta\|_{1}}.$

Next we study

$\displaystyle Z_{4b}$ $\displaystyle=\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}\eta_{i}(\eta_{j}-\tilde{\eta}_{j})\widetilde{\Omega}_{jk}(\eta_{k}-\tilde{\eta}_{k})\eta_{\ell}W_{\ell
i}=\sum_{\begin{subarray}{c}i,j,k,\ell\\\
(dist)\end{subarray}}\alpha_{ijk\ell}(\eta_{j}-\tilde{\eta}_{j})(\eta_{k}-\tilde{\eta}_{k})W_{\ell
i}$ $\displaystyle=\frac{1}{v}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\
s\neq j,t\neq k\end{subarray}}\alpha_{ijk\ell}W_{js}W_{kt}W_{\ell i}$

where $\alpha_{ijk\ell}=\eta_{i}\eta_{\ell}\widetilde{\Omega}_{jk}$. Mimicking
the study of $Z_{3a}$, we have the decomposition

$\displaystyle Z_{4b}$
$\displaystyle=\frac{1}{v}\sum_{i,j,k,\ell(dist)}\alpha_{ijk\ell}W^{2}_{jk}W_{\ell
i}+\frac{1}{v}\sum_{\begin{subarray}{c}i,j,k,\ell(dist)\\\ s\neq j,t\neq
k,(s,t)\neq(k,j)\end{subarray}}\alpha_{ijk\ell}W_{js}W_{kt}W_{\ell i}$
$\displaystyle\equiv\widetilde{Z}_{4b}+Z^{*}_{4b}.$

Further we have, using (E.1), (E.2), (E.20), and (E.24), we have

$\displaystyle\mathrm{Var}(\tilde{Z}_{4b})$
$\displaystyle\lesssim\frac{1}{\|\theta\|_{1}^{4}}\bigg{(}\sum_{ijk\ell}\big{[}\,[\beta_{j}^{2}\beta_{k}^{2}+\beta_{j}\beta_{k}\beta_{\ell}\beta_{i}]\theta_{i}^{3}\theta_{j}^{3}\theta_{k}^{3}\theta_{\ell}^{3}\big{]}+\sum_{ijk\ell
j^{\prime}k^{\prime}}\beta_{j}\beta_{k}\beta_{j^{\prime}}\beta_{k^{\prime}}\theta_{i}^{3}\theta_{j}^{2}\theta_{k}^{2}\theta_{\ell}^{3}\theta_{j^{\prime}}^{2}\theta_{k^{\prime}}^{2}\bigg{)}$