# Computational and Statistical Thresholds in Multi-layer Stochastic Block
Models

Jing Lei  Carnegie Mellon University  Anru R. Zhang  Duke University  Zihan
Zhu  Duke University

###### Abstract

We study the problem of community recovery and detection in multi-layer
stochastic block models, focusing on the critical network density threshold
for consistent community structure inference. Using a prototypical two-block
model, we reveal a computational barrier for such multi-layer stochastic block
models that does not exist for its single-layer counterpart: When there are no
computational constraints, the density threshold depends linearly on the
number of layers. However, when restricted to polynomial-time algorithms, the
density threshold scales with the square root of the number of layers,
assuming correctness of a low-degree polynomial hardness conjecture. Our
results provide a nearly complete picture of the optimal inference in
multiple-layer stochastic block models and partially settle the open question
in [29] regarding the optimality of the bias-adjusted spectral method.

##  1 Introduction

A network records the pairwise interactions among a group of individuals.
Unlike traditional data that records attributes of individuals, each entry in
a network data measurement is indexed by a pair of individuals. A network data
on a group of $n$ individuals is often represented by an $n\times n$ matrix,
where the $(i,j)$th entry records the interaction between the individuals $i$
and $j$. Network data has wide applications in social and nature sciences, and
has led to a rich collection of methodological and theoretical developments in
statistics and machine learning. We refer to the books [17, 23, 25, 40] for
further readings on general network data analysis.

In recent years, the advancement of measurement technology and data storage
capability allows scientists to record multiple networks on the same group of
individuals. Such multi-layer networks often reveal more insights about the
underlying structure. For example, [47] used multi-layer network to analyze
the connectivity patterns between research articles using interaction measured
in different modes, including title, abstract, and keywords; [13] considered
cellphone networks defined through tower proximity, blue-tooth proximity, and
calls; in [28, 29, 32], multiple gene co-expression networks are constructed
at different developmental periods. Other examples include social science
[49], bioinformatics [52], and neural imaging [41]. See [24] for a general
introduction to multi-layer network data.

The emergence of multi-layer network data has inspired many corresponding
developments in statistical methods and theory. As the multi-layer extension
of the famous stochastic block model [SBM 19], the multi-layer stochastic
block model (MLSBM) is a very popular model for dynamic or multi-layer network
data due to its natural ability to model and recover latent communities, a
clustering structure that is expected to exist in many real-world networks. A
main challenge in working with multi-layer networks is that the data is now a
three-way tensor, where, unlike for matrix-valued single-layer network data,
spectral methods are neither easy to compute nor guaranteed to be consistent.
Existing methods deal with the tensor data by either aggregating over the
layers [18, 42, 31] or partially vectorizing the tensor to reduce to a matrix
form [43]. Likelihood and least-squares-based estimators are also considered
but may face computational challenges in the worst-case scenario [39, 28].
Recently, [8] considered a two-stage method that uses likelihood to refine an
initial spectral estimate obtained from aggregated layers.

In this work, we aim to provide insights into the understanding of the
fundamental limits of community detection and estimation in multi-layer
stochastic block models. In single-layer SBMs, it is well known that if the
community sizes are balanced, and the edge probabilities are of the same order
of magnitude, then consistent recovery of communities is possible if and only
if the average degrees diverge as the number of nodes increases, and such
recovery can be achieved using variants of spectral methods, which are
computationally feasible [2, 16, 30, 50]. When it comes to multi-layer SBMs,
the picture is less clear. When the number of layers diverges as the number of
nodes, the key question is to understand how the signal accumulates over the
layers. In the simplified setting of balanced community sizes and same-order
edge probabilities, some recent results suggest that the signal accumulates
linearly in the number of layers, and consistent community recovery is
possible if and only if the expected total degrees across all layers diverge
as numbers of nodes and layers increase [8, 42]. However, these results
require that the layers are all assortative mixing, i.e., nodes in the same
community are more likely to connect than nodes from different communities.
There are reasons to believe the assortative mixing assumption may make the
problem easier as it provides a simple way to aggregate over the layers, as
explained in [28, 29]. Without the assortativity assumption, the best known
upper bound results suggest that the signal accumulates proportional to the
square root of, instead of linearly in, the number of the layers [29].

The main contribution of this work is a characterization of the network
density threshold required for consistent community recovery and detection for
general multi-layer SBMs. Interestingly, we find that both the linear and
square-root signal accumulation rates are correct, in the sense that the
linear rate corresponds to the information-theoretic threshold, whereas the
square-root rate corresponds to the computational threshold when restricted to
polynomial-time algorithms assuming a hardness conjecture of low-degree
polynomials [LDLR, 26]. Such a computational gap not only reconciles existing
results on this topic, it also provides some insights into the source of
hardness of inference for multi-layer SBMs. The proofs of the main results
reveal that the computational hardness comes mainly from the unknown _layer
identity_. The term “layer identity” can be thought of as identifying each
layer as assortative mixing or disassortative mixing (the opposite of
assortative mixing). If we are provided with this knowledge, then the signal
accumulates linearly over the layers, otherwise, there is a computational cost
in finding the best way to aggregate information across the layers. See
section 2 for a more precise description.

### Related work

There is no gap between computational and information-theoretic thresholds for
single-layer SBMs. Instead, the multi-layer network is more like low-rank
tensor data, where similar gaps have been established for certain models,
including sparse principal components analysis [6], sparse submatrix recovery
[37], and tensor SVD [51]. These computational lower bound results all rely on
reducing the statistical inference problem to a conjectured computationally
hard problem, usually the planted-clique problem. A unique challenge posed by
the multi-layer SBM model is that the data entries are sparse Bernoulli, which
is hard to convert to the dense Bernoulli entries as required in the planted
clique model. Our theoretical development bypasses this difficulty by
considering an alternative framework for computational hardness, namely the
“low-degree polynomial” framework [26]. The low-degree polynomial framework
grew out of the Sum-of-Squares (SoS) hierarchy [44], where the hardness of a
problem is gauged by the performance of an increasingly more powerful
hierarchy of semidefinite relaxations of polynomial optimization problems.
Roughly speaking, we know that the likelihood ratio is most powerful in
distinguishing MLSBMs with different community structures, then it is
reasonable to conjecture computational hardness if the best low-degree
polynomial approximation to the likelihood ratio cannot distinguish these two
models. See [45] for recent developments of the low-degree polynomial
framework in estimation and [34] for an application in single-layer graphon
estimation.

##  2 Problem formulation and asymptotic regimes

A multi-layer SBM is a probabilistic model for a collection of random graphs
observed on a common set of nodes. For a pair of positive integers $(n,T)$,
let $[n]=\\{1,2,...,n\\}$ be the set of nodes, and $[T]$ the set of layers. A
multi-layer SBM with $K$ common communities generates independent Bernoulli
random variables

$A_{t}(i,j)\stackrel{{\scriptstyle\rm indep.}}{{\sim}}{\rm
Bernoulli}(B_{t}(\sigma_{i},\sigma_{j}))\,,~{}~{}1\leq i<j\leq n\,,~{}1\leq
t\leq T\,,$ (1)

where $\bm{\sigma}=(\sigma(i):i\in[n])\in[K]^{n}$ is a community membership
vector, with $\sigma(i)\in[K]$ denoting the membership of node $i$, and
$B_{t}\in[0,1]^{K\times K}$ is a symmetric matrix specifying the edge
probability between the communities in the $t$th layer.

The observed data are $T$ symmetric binary adjacency matrices
$\mathbf{A}=(A_{t}:t\in[T])$. In the theory and practice related to stochastic
block models, it is of interest to infer about the membership vector
$\bm{\sigma}$ from $\mathbf{A}$.

The hardness of inference problems related to $\bm{\sigma}$ depends on $n$,
$T$, $\mathbf{B}=(B_{t}:t\in[T])$, and $\bm{\sigma}$. In this work we focus on
the interplay between three quantities: the number of nodes $n$, the number of
layers $T$, and the overall network density. Here the network density is
reflected by the overall magnitude of the entries in $\mathbf{B}$.

To facilitate our discussion and simplify presentation, we focus on the case
$K=2$ and assume both $n$ and $T$ are even. Let
$\mathcal{S}_{n}=\\{\bm{\sigma}\in\\{0,1\\}^{n}:\sum_{i\in[n]}\sigma(i)=n/2\\}$
be the set of all balanced membership vectors $\bm{\sigma}$ on $n$ nodes. Let
$\rho\in(0,2/3)$ be a overall network density parameter. Define

$B^{(0)}=\begin{bmatrix}\frac{3}{2}\rho&\frac{1}{2}\rho\\\
\frac{1}{2}\rho&\frac{3}{2}\rho\end{bmatrix}\,,\quad
B^{(1)}=\begin{bmatrix}\frac{1}{2}\rho&\frac{3}{2}\rho\\\
\frac{3}{2}\rho&\frac{1}{2}\rho\end{bmatrix}\,.$ (2)

######  Definition 1.

Given the triplet $(n,T,\rho)$, we consider the following two MLSBM models.

  1. 1.

The balanced two-community model $P_{1,n}=P_{1}(n,T,\rho)$:

    1. (a)

$\bm{\sigma}\sim{\rm Uniform}(\mathcal{S}_{n})$;

    2. (b)

$\bm{\tau}\sim{\rm Uniform}(\mathcal{S}_{T})$;

    3. (c)

$B_{t}=B^{(\tau_{t})}$ for each $t\in[T]$, with $B^{(0)}$, $B^{(1)}$ given in
(2);

    4. (d)

Generate $\mathbf{A}$ according to (1).

  2. 2.

The null model $P_{0,n}=P_{0}(n,T,\rho)$:

$A_{t}(i,j)\stackrel{{\scriptstyle\rm indep.}}{{\sim}}{\rm Bernoulli}(\rho)$

for all $1\leq i<j\leq n$, $t\in[T]$.

We now discuss the rationale behind these choices of mixtures and priors.
First, the randomization on $\bm{\sigma}$ is a natural step in establishing
minimax lower bounds for estimating $\bm{\sigma}$ or detecting the existence
of community structure. Given an arbitrary estimator, we can compute the Bayes
risk under this prior in order to provide a minimax lower bound. Such a
uniform prior on $\bm{\sigma}$ has been used in minimax theory for single
layer SBMs [50]. Second, the randomization of $\bm{\tau}$ is crucial in
distinguishing the information-theoretic threshold and the computational
threshold. It turns out that not knowing the layer identity, e.g., the value
of $\tau(t)$ for each $t$, can make the inference about $\bm{\sigma}$
computationally hard but information-theoretically easy in certain regimes.
These two priors can be changed to the corresponding Bernoulli models (i.e.,
$\sigma(i)\stackrel{{\scriptstyle\rm iid}}{{\sim}}{\rm Bernoulli}(1/2)$) with
additional bookkeeping. Finally, we include the “null model” $P_{0,n}$ in
order to consider the detection problem: Whether it is possible to distinguish
$P_{1,n}$ from $P_{0,n}$. The low-degree polynomial framework can be applied
to such detection problems hence providing a lower bound for the estimation
problem. Below we will formally introduce the estimation problem and detection
problem.

### Asymptotic community recovery and detection

We are interested in the asymptotic behavior of estimators when
$n\rightarrow\infty$, $T\rightarrow\infty$, and $\rho\rightarrow 0$. It is
perhaps the easiest to relate $L$ and $\rho$ to $n$ by considering sequences
$(T_{n},\rho_{n})_{n=1}^{\infty}$, which makes it more natural to write the
corresponding mixture model sequence $P_{1,n}=P_{1}(n,T_{n},\rho_{n})$, and
$P_{0,n}=P_{0}(n,T_{n},\rho_{n})$ as in Definition 1. In the rest of this
paper, we will use $P_{1,n}$ to denote the joint distribution of
$(\mathbf{A},\bm{\sigma},\bm{\tau})$. Now we can define the recoverability and
distingshuishability of such model sequences.

######  Definition 2 (Recoverable and distinguishable model sequences).

  1. 1.

For a sequence $(T_{n},\rho_{n})_{n=1}^{\infty}$, we say the corresponding
MLSBM sequence $P_{1,n}$ defined in Definition 1 is _recoverable_ if there
exists a sequence of estimators
$\hat{\bm{\sigma}}(\mathbf{A})\in\mathcal{S}_{n}$ such that

$P_{1,n}(\ell_{n}(\hat{\bm{\sigma}},\bm{\sigma})\geq\epsilon)\rightarrow 0$

for any positive constant $\epsilon$, where

$\ell_{n}(\hat{\bm{\sigma}},\bm{\sigma})=n^{-1}\min\left\\{d_{\rm
Ham}(\hat{\bm{\sigma}},\bm{\sigma})\,,~{}d_{\rm
Ham}(\hat{\bm{\sigma}},1-\bm{\sigma})\right\\}$

is the normalized Hamming distance between $\hat{\bm{\sigma}}$ and
$\bm{\sigma}$ up to label permutation.

  2. 2.

For a sequence $(T_{n},\rho_{n})_{n=1}^{\infty}$, we say the corresponding
MLSBM sequence $(P_{1,n})$ defined in Definition 1 is _distinguishable_ from
$P_{0,n}$ if there exists a sequence of $\hat{\psi}$:
$\hat{\psi}(\mathbf{A})\in\\{0,1\\}$ such that

$P_{1,n}(\hat{\psi}(\mathbf{A})=0)+P_{0,n}(\hat{\psi}(\mathbf{A})=1)\rightarrow
0\,.$

Intuitively, detection should be easier than recovery. We make this formal in
the following lemma.

######  Lemma 2.1 (Detection implies recovery).

Under the MLSBM specified in Definition 1, if $P_{1,n}$ is asymptotically
recoverable for a sequence $(T_{n},\rho_{n})$, then it is distinguishable for
$(T_{n}+2,\rho_{n})$ with polynomial additional computing time.

Lemma 2.1 implies that, asymptotically, the recovery problem is at least as
hard as the detection problem. The change from $T_{n}$ to $T_{n}+2$ makes no
difference in the asymptotic framework considered in this paper. Therefore, we
will provide upper bound results for recovery and lower bound results for
detection, and show that there is no gap between recovery and detection for
the MLSBM sequence considered.

### The range of model parameters

We will focus on a certain range of $T_{n}$ and $\rho_{n}$ that is of main
practical interest. First, it is natural to restrict $\rho_{n}$ such that
$\rho_{n}=o(1)$ and $\rho_{n}=\omega(n^{-2})$. In fact, the regime
$\rho_{n}=\Omega(\log n/n)$ would make the model $P_{1,n}$ easily recoverable
and detectable even when $T=1$ [30]. If $\rho_{n}=o(n^{-2})$, then most of the
layers will be completely empty, and it is natural to exclude such a scenario
because in practice only non-empty layers are relevant. Second, we will also
restrict to $T_{n}=\omega(1)$, which makes the problem sufficiently different
from single layer SBMs.

We summarize the range of $(T_{n},\rho_{n})$ as below for ease of reference.

######  Assumption 1 (Asymptotic regime of $(T_{n},\rho_{n})$).

When $n\rightarrow\infty$, we have $T_{n}\rightarrow\infty$,
$\rho_{n}\rightarrow 0$, $\rho_{n}^{-1}=o(n^{2})$.

If we further simplify $(T_{n},\rho_{n})$ as monomials of $n$, Assumption 1
corresponds to

$T_{n}=n^{a}\,,~{}~{}~{}\rho_{n}=n^{-b}\,,~{}~{}~{}~{}a>0,~{}~{}b\in(0,2)\,.$

Then we can summarize our main results in terms of the regime on the parameter
space $(a,b)\in(0,\infty)\times(0,2)$.

######  Theorem 2.2 (Simplified main result).

Let $T_{n}=n^{a}$, $\rho_{n}=n^{-b}$ for some $a>0$, $b\in(0,2)$. Then

  * •

without computational constraints, the MLSBM is recoverable if $1+a-b>0$; and
is not recoverable by any algorithm if $1+a-b<0$.

  * •

assuming the low-degree polynomial conjecture, the MLSBM is recoverable using
a polynomial-time algorithm if $1+a/2-b>0$, and not recoverable by any
polynomial-time algorithm if $1+a/2-b<0$.

The above results also hold for detection.

##  3 Computational lower and upper bounds

Now we present the computation thresholds for detection and recovery in the
multi-layer stochastic block model. The computational upper bound for recovery
(and hence detection) has been studied in [28, 29], in which a variant of
spectral clustering was proved to consistently recover the membership when
$nT_{n}^{1/2}\rho_{n}\gtrsim O(\sqrt{\log(n)})$.

######  Theorem 3.1 (Computational upper bound [28]).

If $nT_{n}^{1/2}\rho_{n}\geq C\sqrt{\log(n)}$ for some absolute constant
$C>0$, then MLSBM sequence $(P_{1,n}:n\geq 1)$ specified in Definition 1 is
asymptotically recoverable by a polynomial-time algorithm.

Next, we derive a nearly matching computational lower bound for detection in
MLSBM, up to a logarithm factor. Our proof is based on the low-degree
polynomial argument introduced and developed in [20, 26]. The basic intuition
behind this framework is that if a planted hidden structure cannot be detected
using low-degree polynomials of the input data, then it cannot be detected by
any polynomial time algorithm. A formal justification of this intuition is
stronger than proving “P$\neq$NP”, and hence instead of a rigorous proof we
can only realistically hope to have evidence for such an intuition. Much
evidence in favor of this conjecture has been gathered in the thesis work
[20]. On the other hand, many widely implemented polynomial algorithms that
achieve the best possible detection thresholds in various related problems,
including spectral methods and approximate message passing (see a survey by
[14]), can be expressed as low-degree polynomials [15, 26]. The low-degree
polynomial method can be seen as a “light version” of the sum-of-squares (SOS)
computational lower bounds, which is more straightforward to establish and
usually yields the same results for natural average-case hardness problems.
Low-degree polynomial computational hardness results have been successfully
obtained in a number of problems, such as the planted clique detection [5,
20], community detection in stochastic block models [20, 22], spiked tensor
models [20, 21, 26], spiked Wishart models [4], sparse PCA [12], spiked Wigner
model [26], clustering [9, 33, 36], planted vector recovery [38], certifying
RIP [11], independent component analysis [3], random $k$-SAT [7], and tensor
regression [10, 35]. It is also increasingly believed that the low-degree
polynomials method can encapsulate the fundamental principles that determine
the success or failure of sum-of-squares algorithms [20, 26].

Our argument for the computational lower bound relies on the following low-
degree polynomial conjecture, which is a specialized version of the more
general statement [20, Conjecture 2.2.4] adapted to our specific context.

######  Conjecture 3.2 (Low-degree polynomial conjecture: Conjecture 2.2.4 in
[20]).

Let $P_{0,n}$ and $P_{1,n}$ be two sequences of MLSBM defined in Definition 1
with parameters $(T_{n},\rho_{n})$ satisfying the asymptotic regime specified
in Assumption 1. If every polynomial $\psi$ of degree111Here the polynomial is
viewed as a multivariate polynomial with input vector
$\mathbf{A}\in\mathbb{R}^{{n\choose 2}\times T_{n}}$. at most
$D_{n}=\log^{1.01}(n)$ with $\mathbb{E}_{P_{0,n}}\psi^{2}=1$ and
$\mathbb{E}_{P_{0,n}}\psi=0$ satisfies $\mathbb{E}_{P_{1,n}}\psi=O(1)$
uniformly, then $P_{1,n}$ is not distinguishable from $P_{0,n}$ by any
polynomial-time algorithm.

######  Remark 1.

The original version of the conjecture in [20] is more general and requires
various forms of regularity conditions. These conditions can be directly
verified for our MLSBM sequence $(P_{0,n},P_{1,n})_{n\geq 1}$ specified in
Definition 1 with $(T_{n},\rho_{n})$ satisfying Assumption 1.

######  Remark 2 (Intuition of the low-degree polynomial conjecture).

The low-degree polynomial conjecture stems from the classical asymptotic
decision theory [27] and the sum-of-square optimization [20]. A typical
approach to study the statistical distinguishability between $P_{0,n}$ and
$P_{1,n}$ is by Le Cam’s contiguity [27]. Recall that for two sequences of
probability distributions, $(P_{0,n},P_{1,n})_{n\in\mathbb{N}}$, over a common
sequence of measurable spaces, we say $P_{1,n}$ is contiguous to $P_{0,n}$, if
for any sequence of events $(E_{n}:n\geq 1)$, $P_{0,n}(E_{n})\rightarrow 0$
implies $P_{1,n}(E_{n})\rightarrow 0$. It is well known that contiguity
implies statistical impossibility in distinguishing $P_{1,n}$ and $P_{0,n}$
since vanishing type I errors must imply vanishing power. Meanwhile,
contiguity can be established through the second-moment method, which is
essentially the likelihood ratio test: If $\mathbb{E}_{\mathbf{A}\sim
P_{0,n}}\\{[P_{1,n}(\mathbf{A})/P_{0,n}(\mathbf{A})]^{2}\\}$ remains bounded
as $n\rightarrow\infty$, then $P_{1,n}$ is contiguous to $P_{0,n}$.

When there are computational challenges in computing the exact value of the
likelihood ratio $L_{n}(\mathbf{A})$, it is natural to study the projection of
the likelihood ratio onto the subspace spanned by low-degree polynomials (the
exact definition is to be specified in Lemma 3.4 below). If the
$L^{2}(P_{0,n})$ norm of this projected likelihood remains bounded when
$n\rightarrow\infty$, it is reasonable to conjecture that no logarithmic-
degree polynomial can effectively distinguish $P_{0,n}$ and $P_{1,n}$.

Equipped with the low-degree polynomial conjecture, we now present our main
result on computational thresholds in MLSBM.

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

Assuming the low-degree polynomial conjecture 3.2, the MLSBM sequences
$(P_{1,n},P_{0,n})$ specified in Definition 1 with $\rho_{n}$ satisfying
Assumption 1 are not distinguishable by any polynomial-time algorithm if
$nT_{n}^{1/2}\rho_{n}\leq(1/2)(\log n)^{-1.4}$ for all $n$ large enough.

As detailed in the proof, the exponent of $-1.4$ can be improved to $-1.01$ if
$T_{n}\gg\log^{2.02}n$. Here the notion of “polynomial-time” means polynomial
in $n$, because when $\rho_{n}$ satisfies Assumption 1, the condition
$nT_{n}^{1/2}\rho_{n}\leq(1/2)(\log n)^{1.4}$ implies $T_{n}=O(n^{2})$ and
hence the total size of $\mathbf{A}$ is polynomial in $n$. Here we describe
the sketch of the proof, highlighting some key steps and techniques. The proof
consists of three main steps as summarized in the three lemmas below. The
detailed proofs of these lemmas are given in Appendix B.

The first step is to realize that among all low-degree polynomials of the
input data, the projected likelihood ratio has the largest $L^{2}(P_{0,n})$
norm, and hence is most likely to break contiguity, as required by
distinguishability.

######  Lemma 3.4.

(Proposition I.15 in [26]). For any positive integer $n$, given the data
$\mathbf{A}$ and two MLSBM models $P_{0,n}$ and $P_{1,n}$. Let
$L_{n}(\mathbf{A})=\frac{P_{1,n}(\mathbf{A})}{P_{0,n}(\mathbf{A})}$ be the
likelihood ratio. Define the norm $\lVert
f\rVert\coloneqq\sqrt{\mathbb{E}_{P_{0,n}}f^{2}(\mathbf{A})}$ and define
$f^{\leq D}$ as the projection of any function $f$ to the subspace of
polynomials of degree at most $D$. For any positive integer $D$, we have

$\lVert L_{n}^{\leq
D}(\mathbf{A})-1\rVert=\mathop{\sup}_{\begin{subarray}{c}\psi:{\rm
deg}(\psi)\leq D,\\\ \mathbb{E}_{P_{0,n}}\psi^{2}(\mathbf{A})=1,\\\
\mathbb{E}_{P_{0,n}}\psi(\mathbf{A})=0\end{subarray}}\mathbb{E}_{P_{1,n}}\psi(\mathbf{A}).$

The second step is a re-expression of the low-degree likelihood ratio. With
Lemma 3.4, we only need to bound $\|L_{n}^{\leq D_{n}}-1\|$. In the second
step, we use discrete Fourier basis expansion of $L_{n}^{\leq D_{n}}$ to re-
express this quantity in terms of the sizes of certain subsets of the indexing
set. Define the index set $\Lambda_{n}\coloneqq\\{(i_{1},i_{2},t):1\leq
i_{1}<i_{2}\leq n,1\leq t\leq T_{n}\\}$. For any $\alpha\subseteq\Lambda_{n}$,
and $i\in[n]$, $t\in[T_{n}]$, define
$u_{i,\alpha}=\sum_{(i^{\prime},j^{\prime},t^{\prime})\in\alpha}\mathds{1}(i=i^{\prime})+\mathds{1}(i=j^{\prime})$
and
$v_{t,\alpha}=\sum_{(i^{\prime},j^{\prime},t^{\prime})\in\alpha}\mathds{1}(t=t^{\prime})$
be the number of times the node index $i$ and layer index $t$ appear in
$\alpha$, respectively. Let $U_{\alpha}=\\{i\in[n]:u_{1,\alpha}\text{ is
odd}\\}$, and $V_{\alpha}=\\{t\in[T_{n}]:v_{t,\alpha}\text{ is odd}\\}$.
Finally define
$\Lambda_{n,a,r,k}=\\{\alpha\subseteq\Lambda_{n}:|\alpha|=a,~{}|U_{\alpha}|=2r,~{}|V_{\alpha}|=2k\\}$.
We have the following re-expression of $\|L_{n}^{\leq D_{n}}-1\|$.

######  Lemma 3.5 (Re-expression of LDLR).

Under the above notation,

$\displaystyle\lVert L_{n}^{\leq
D_{n}}(\mathbf{A})-1\rVert^{2}=\sum_{a=1}^{D_{n}}\left(\frac{\rho_{n}}{4(1-\rho_{n})}\right)^{a}\sum_{r=0}^{a}\sum_{k=0}^{[a/2]}|\Lambda_{n,a,r,k}|\frac{\binom{n/2}{r}^{2}\binom{T_{n}/2}{k}^{2}}{\binom{n}{2r}^{2}\binom{T_{n}}{2k}^{2}}\,.$

The third and final step is to control the size of the set
$\Lambda_{n,a,r,k}$.

######  Lemma 3.6.

[Controlling $|\Lambda_{n,a,r,k}|$] When $n$, $T_{n}$ are large enough, for
$a\leq D_{n}=\log^{1.01}n$ we have

$|\Lambda_{n,a,r,k}|\leq 2^{1+5a/2}a^{4a/3}{n\choose 2r}{T_{n}\choose
2k}n^{a-r}T_{n}^{a/2-k}\,.$

If $T_{n}=\omega(D_{n}^{2})$, the term $a^{4a/3}$ in the above bound can be
strengthened to $a^{a}$ .

###### Proof of Theorem 3.3.

According to Conjecture 3.2, it suffices to prove that for every polynomial
$\psi$ of degree $D_{n}=\log^{1.01}(n)$ with
$\mathbb{E}_{P_{0,n}}\psi^{2}(\mathbf{A})=1$, the expectation
$\mathbb{E}_{P_{1,n}}\psi(\mathbf{A})$ is bounded as $n\rightarrow\infty$.
According to Lemma 3.4, the supremum of $\mathbb{E}_{P_{1,n}}\psi(\mathbf{A})$
among all polynomials $\psi$ such that $\deg{\psi}\leq D_{n}$ with zero mean
and unit variance under $P_{0,n}$ is equal to $\lVert L_{n}^{\leq
D_{n}}(\mathbf{A})-1\rVert$. Then it suffices to control $\lVert L_{n}^{\leq
D_{n}}(\mathbf{A})-1\rVert$.

Combining Lemma 3.5 and Lemma 3.6 we get

$\displaystyle\lVert L_{n}^{\leq D_{n}}(\mathbf{A})-1\rVert^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{a=1}^{D_{n}}\frac{\rho_{n}^{a}}{(4(1-\rho_{n}))^{a}}2^{1+5a/2}a^{4a/3}\sum_{r=0}^{a}\sum_{k=0}^{a/2}\frac{\binom{n/2}{r}^{2}\binom{T_{n}/2}{k}^{2}}{\binom{n}{2r}\binom{T_{n}}{2k}}n^{a-r}T_{n}^{a/2-k}$
$\displaystyle\leq$ $\displaystyle
8\sum_{a=1}^{D_{n}}\frac{\rho_{n}^{a}}{(4(1-\rho_{n}))^{a}}2^{5a/2}a^{4a/3}n^{a}T_{n}^{a/2}\leq
8\sum_{a=1}^{D_{n}}\xi_{n}^{a}\leq\frac{8\xi_{n}}{1-\xi_{n}}\,,$ (3)

with $\xi_{n}=2D_{n}^{4/3}\rho_{n}nT_{n}^{1/2}$. In the last line of (3), the
first inequality follows from some simple algebra whose detail is given in
Appendix B, the second and third inequalities follow from the sum of geometric
sequences and are valid whenever $\rho_{n}<1/2$ and
$\rho_{n}nT_{n}^{1/2}<(1/2)D_{n}^{-4/3}\leq(1/2)(\log
n)^{-4.04/3}\leq(1/2)(\log n)^{-1.4}$, which is guaranteed under the
assumption of the theorem for large enough $n$. ∎

##  4 Information-theoretic upper and lower bounds

###  4.1 Information-theoretic lower bound

Our main information-theoretic lower bound result shows that if
$nT_{n}\rho_{n}$ vanishes then no algorithm can consistently distinguish
$P_{1,n}$ and $P_{0,n}$, regardless of the computation power. Indeed, we will
show a stronger result: The community structure is not detectable even when
the layer identity $\bm{\tau}$ is known.

For $\bm{\tau}\in\mathcal{S}_{T_{n}}$, let $P_{1,\bm{\tau},n}$ be the
corresponding conditional distribution of $(\mathbf{A},\bm{\sigma})$ under
$P_{1,n}$ given $\bm{\tau}$. For $\bm{\tau}\in\mathcal{S}_{T_{n}}$,
$\bm{\sigma}\in\mathcal{S}_{n}$, $P_{\bm{\sigma},\bm{\tau}}$ denotes the
distribution of $\mathbf{A}$ given $(\bm{\sigma},\bm{\tau})$.

Our detection lower bound is established by bounding the $\chi^{2}$-divergence
between $P_{1,\bm{\tau},n}$ and $P_{0,n}$. Recall that for two distributions
$P$, $Q$ on the same sample space $\mathcal{X}$ with probability mass function
$q(x)$ and $p(x)$ respectively, their $\chi^{2}$-divergence is

$d_{\chi^{2}}(Q,P)=\mathbb{E}_{X\sim
P}\left(\frac{q(X)}{p(X)}-1\right)^{2}=\sum_{x\in\mathcal{X}}\frac{q^{2}(x)}{p(x)}-1\,.$

It is well-known that if $d_{\chi^{2}}(P_{1,n},P_{0,n})\rightarrow 0$ then
$P_{1,n}$ and $P_{0,n}$ are indistinguishable [48, Theorem 2.2].

######  Theorem 4.1.

(Detection lower bound in MLSBM). When $nT_{n}\rho_{n}\rightarrow 0$, we have

$d_{\chi^{2}}(P_{1,\bm{\tau},n},P_{0,n})=\sum_{\mathbf{A}}P_{1,\bm{\tau},n}^{2}(\mathbf{A})/P_{0,n}(\mathbf{A})-1=o(1)\,,~{}~{}\forall~{}\bm{\tau}\in\mathcal{S}_{T_{n}}\,.$

As a result,

$d_{\chi^{2}}(P_{1,n},P_{0,n})=o(1)$

and $P_{1,n}$, $P_{0,n}$ are indistinguishable.

The proof of Theorem 4.1 is given in Appendix C. The proof is based on a
direct expansion of the $\chi^{2}$-divergence and takes advantage of the
symmetry in $P_{1,\bm{\tau},n}$ and $P_{0,n}$. Intuitively, the expected
number of edges observed for a single node over all layers is approximately
$(n-1)T_{n}\rho_{n}$. If $nT_{n}\rho_{n}=o(1)$, then for most nodes there will
be no observed edges at all. In this case, it would be impossible to recover
the community for the majority of nodes. In fact, a similar lower bound result
for single-layer SBMs has been developed by [50], using an elegant
localization argument that also originates from the symmetry of $P_{1,n}$. Our
result not only extends to multi-layer SBMs but also provides a lower bound
for the detection problem, which, as shown in Lemma 2.1, is at least as hard
as the recovery problem.

###  4.2 Information-theoretic upper bound

We consider a variant of the maximum likelihood estimate (MLE) specialized to
the MLSBM in Definition 1. Given data $\mathbf{A}\in\\{0,1\\}^{{n\choose
2}\times T_{n}}$, we estimate $\bm{\sigma}$ and $\bm{\tau}$ together by
maximizing the blockwise edge count:

$(\hat{\bm{\sigma}}_{\rm mle},\hat{\bm{\tau}}_{\rm
mle})=\arg\max_{\bm{\sigma}\in\mathcal{S}_{n},\bm{\tau}\in\mathcal{S}_{T_{n}}}\sum_{(i,j,t):2|\sigma(i)+\sigma(j)+\tau(t)}A_{t}(i,j)\,.$
(4)

This estimate extends that of [1], who studied single-layer exact recovery of
the MLE.

The following result establishes consistency of $\hat{\bm{\sigma}}_{\rm mle}$
when $nT_{n}\rho_{n}\rightarrow\infty$.

######  Theorem 4.2.

Let $P_{1,n}$ be the sequence of MLSBM defined in Definition 1 with
$(T_{n},\rho_{n})$ satisfying Assumption 1. If
$nT_{n}\rho_{n}\rightarrow\infty$, then for any $\epsilon>0$

$\lim_{n\rightarrow\infty}P_{1,n}(\ell_{n}(\hat{\bm{\sigma}}_{\rm
mle},\bm{\sigma})\geq\epsilon)=0\,,$

where $\ell_{n}(\cdot,\cdot)$ is the Hamming loss function defined in
Definition 2. In other words, $P_{1,n}$ is asymptotically recoverable and
hence distinguishable from $P_{0,n}$.

It is remarkable that our information-theoretic thresholds for recovery and
detection have sharp rates: There is no gap in the rates of lower and upper
thresholds, and there is no gap between recovery and detection.

Theorem 4.2 is proved in Appendix C. The basic proof strategy is similar to
that of [1], who studied exact recovery in single-layer SBMs. Our contribution
is to extend this argument to the multi-layer case and to provide approximate
recovery instead of exact recovery. The idea is that if the MLE is different
from the truth, then there must be a subset of triplets $(i,j,t)$, over which
the realized Binomial random variable (i.e., the total edge count) deviates
from the expected value by at least a constant fraction. The probability of
this event decays exponentially fast in the Hamming distance between
$\hat{\bm{\sigma}}$ and $\bm{\sigma}$, which allows a union bound over all
possible realizations of $\hat{\bm{\sigma}}$ at any given Hamming distance,
and over all possible Hamming distances that are large enough.

##  5 Discussion

Our computational lower bound result shows that the bias-adjusted spectral
clustering applied to the squared adjacency matrices [29] achieves nearly the
optimal network density threshold among all polynomial-time algorithms
assuming the low-degree polynomial conjecture. Unlike the MLE considered in
Section 4.2, the bias-adjusted spectral method works for a more general class
of MLSBMs, allowing $B_{t}$ to vary arbitrarily as long as
$T_{n}^{-1}\rho_{n}^{-2}\sum_{t}B_{t}^{2}\succeq cI$ for some positive
constant $c$. It would be interesting to develop a corresponding method for
the information-theoretic upper bound that works for such more general MLSBMs.

Our computational lower bound uses the low-degree polynomial conjecture. It
would be possible to establish computational lower bound results using other
frameworks. The most natural extension, given the success of low-degree
polynomial approach used in this manuscript, would be to establish a sum-of-
squares lower bound. We conjecture that such a lower bound will be
qualitatively the same as our Theorem 4.1 due to the close relationship
between the LDLR and SoS frameworks, but the technical treatment will be much
more involved using SoS. Another possibility is the reduction technique, which
aims to show that solving the community detection/recovery problem in MLSBM is
at least as hard as some well-known computationally hard problems, such as the
planted clique problem or planted hyperclique problem. There, the sparsity in
our MLSBM model could pose some technical challenges.

### Acknowledgement

The research of ARZ and ZZ was supported in part by NSF Grant CAREER-2203741.
JL’s research is partially supported by NSF Grants DMS-2015492, DMS-2310764.

##  Appendix A Proofs for Section 2

###### Proof of Lemma 2.1.

Suppose $\mathbf{A}$ is a $(T_{n}+2)$-layer MLSBM. Let $\tilde{\mathbf{A}}$ be
obtained by taking the first $T_{n}$ layers from $\mathbf{A}$.

By recoverability assumption, there exists an estimate $\hat{\bm{\sigma}}$
such that when applied to $\tilde{\mathbf{A}}$,
$P_{1,n}(\ell_{n}(\hat{\bm{\sigma}},\bm{\sigma})\geq\epsilon)\rightarrow 0$
for any constant $\epsilon>0$.

Now consider the detection rule:

$\hat{\psi}=\left\\{\begin{array}[]{ll}1\,,&\text{if
}|\frac{4}{n^{2}}\sum_{i\in\hat{\bm{\sigma}}^{-1}(0),j\in\hat{\bm{\sigma}}^{-1}(1)}A_{T_{n}+1}(i,j)-\hat{\rho}_{n}|\geq
0.3\hat{\rho}_{n}\\\ 0\,,&\text{otherwise}\,.\end{array}\right.\,,$

where

$\hat{\rho}_{n}=\frac{\sum_{1\leq i<j\leq n}A_{T_{n}+2}(i,j)}{{n\choose
2}}\,.$

Suppose $\mathbf{A}\sim P_{1,n}$. Assume for now that $\bm{\tau}$ is equally
split in $[T_{n}]$. The case of unequal split of $\bm{\tau}$ in $[T_{n}]$ will
be discussed later. In this case, with high probability $\hat{\bm{\sigma}}$
differs from $\bm{\sigma}$ in at most $\epsilon n$ entries. Let
$k=|\hat{\bm{\sigma}}^{-1}(0)\cap\bm{\sigma}^{-1}(0)|$ then we have
$k\leq\epsilon n/2$.

Assume that $\bm{\tau}(T_{n}+1)=0$ (The case of $\bm{\tau}(T_{n}+1)=1$ can be
treated symmetrically). Then
$\\{A_{T_{n}+1}(i,j):\hat{\bm{\sigma}}(i)=0,~{}\hat{\bm{\sigma}}(j)=1\\}$
consists of $(n/2-k)^{2}+k^{2}$ terms with Bernoulli parameter $\rho_{n}/2$,
and $2k(n/2-k)$ terms with Bernoulli parameter $3\rho_{n}/2$. We can pick
$\epsilon$ small enough so that the average value of these Bernoulli
parameters is less than $0.55\rho_{n}$ because when $\epsilon\rightarrow 0$
the average approaches $1/2$.

Now a standard application of Bernstein’s inequality to these $n^{2}/4$
Bernoulli random variables yields

$\mathbb{P}\left[\frac{4}{n^{2}}\sum_{i\in\hat{\bm{\sigma}}^{-1}(0),j\in\hat{\bm{\sigma}}^{-1}(1)}A_{T_{n}+1}(i,j)\leq
0.6\rho_{n}\right]\geq 1-\exp\left[-cn^{2}\rho_{n}\right]\,.$ (5)

On the other hand, by our assumption, $\bm{\tau}(T_{n}+2)=1$. So the node
pairs in the layer $A_{T_{n}+2}$ consist of $(n/2)(n/2-1)$ Bernoulli random
variables with parameter $\rho_{n}/2$, and $n^{2}/4$ with parameter
$3\rho_{n}/2$. The total average of these Bernoulli parameters is
$\rho_{n}(1+1/(2n-2))$. Therefore, another round of Bernstein’s inequality
applied to $\sum_{1\leq i<j\leq n}A_{T_{n}+2}(i,j)$ yields

$\mathbb{P}\left[|\hat{\rho}_{n}-\rho_{n}|\leq 0.1\rho_{n}\right]\geq
1-2\exp(-cn^{2}\rho_{n})$ (6)

for some absolute constant $c>0$.

Therefore, $\hat{\psi}=1$ on the intersection of the events in (5), (6), and
$\ell_{n}(\hat{\bm{\sigma}},\bm{\sigma})\leq\epsilon n$, which has probability
converging to $1$.

If $\bm{\tau}$ is not evenly split in $[T_{n}]$. We consider a random
shuffling of the layers. Under a random shuffling, $\bm{\tau}$ is evenly split
in $[T_{n}]$ with probability $1/2$. Therefore, we repeat the random shuffling
$M$ times, with $M=M_{n}$ that diverges to $\infty$ slowly (for example,
$M_{n}=\log(n^{2}\rho_{n})$). Denote the result $\hat{\psi}_{m}$ for the
result of the above procedure obtained from the $m$th shuffling. Take
$\hat{\psi}=\max_{m}\hat{\psi}_{m}$. Then the probability of $\hat{\psi}=1$ is
reduced by at most $2^{-m}$, the chance that none of the $M$ shuffles produces
an even split of $\bm{\tau}$ in its first $T_{n}$ entries.

Now we turn to $P_{0,n}$. For the same reason as above, (6) still holds. But
now $A_{T_{n}+1}$ is also from the null model, and hence we must have

$\mathbb{P}\left[\left|\frac{4}{n^{2}}\sum_{i\in\hat{\bm{\sigma}}^{-1}(0),j\in\hat{\bm{\sigma}}^{-1}(1)}A_{T_{n}+1}(i,j)-\rho_{n}\right|\leq
0.1\rho_{n}\right]\geq 1-\exp\left[-cn^{2}\rho_{n}\right]\,.$ (7)

It is direct to check that on the intersection of (6) and (7), $\hat{\psi}=0$.
Because the probability $\hat{\psi}=1$ is exponentially small in
$n^{2}\rho_{n}$, this probability can sustain $M$ rounds of reshuffling using
union bound provided that $\log M\ll n^{2}\rho_{n}$. ∎

##  Appendix B Proofs for computational lower bound

###### Proof of Lemma 3.5.

The proof starts from decomposing the polynomial $L_{n}^{\leq D_{n}}$ by a
degree-$D_{n}$ orthogonal basis under $P_{0,n}$. Recall the definition of the
index set $\Lambda_{n}\coloneqq\\{(i_{1},i_{2},t):1\leq i_{1}<i_{2}\leq
n,1\leq t\leq T_{n}\\}$. For any subset $\alpha\subseteq\Lambda_{n}$ such that
$|\alpha|\leq D_{n}$, we consider the following degree-$|\alpha|$ polynomial:

$\chi_{\alpha}(\mathbf{A})=\prod_{(i_{1},i_{2},t)\in\alpha}\frac{\mathbf{A}_{t}(i_{1},i_{2})-\rho_{n}}{\sqrt{\rho_{n}(1-\rho_{n})}}\,.$

Since $\mathbf{A}_{t}(i,j)\stackrel{{\scriptstyle\rm indep.}}{{\sim}}{\rm
Bernoulli}(\rho_{n})$ under $P_{0,n}$, then it follows that
$\mathbb{E}_{P_{0,n}}\chi_{\alpha_{1}}(\mathbf{A})\chi_{\alpha_{2}}(\mathbf{A})=0$
for any index sets $\alpha_{1}\neq\alpha_{2}$, and
$\mathbb{E}_{P_{0,n}}\chi_{\alpha}(\mathbf{A})^{2}=1$ for any index set
$\alpha$. Therefore, $\\{\chi_{\alpha}(\mathbf{A}):|\alpha|\leq D_{n}\\}$
forms a degree-$D_{n}$ polynomial orthonormal basis, and any mean zero
polynomial with a degree no larger than $D_{n}$ can be represented by a linear
combination of this basis:

$f(\mathbf{A})=\sum_{\alpha\subseteq\Lambda_{n}:1\leq|\alpha|\leq
D_{n}}c_{\alpha}(f)\chi_{\alpha}(\mathbf{A})\,,$

where coefficients
$c_{\alpha}(f)=\mathbb{E}_{P_{0,n}}f(\mathbf{A})\chi_{\alpha}(\mathbf{A})$.
Recall that $L_{n}^{\leq D_{n}}$ is the projection of the likelihood ratio
$L_{n}$ on the subspace of degree-$D_{n}$ polynomial, then $\lVert L_{n}^{\leq
D_{n}}(\mathbf{A})-1\rVert$ can be rewritten as follows:

$\displaystyle\lVert L_{n}^{\leq D_{n}}(\mathbf{A})-1\rVert^{2}=$
$\displaystyle\sum_{1\leq|\alpha|\leq
D_{n}}\left[\mathbb{E}_{P_{0,n}}(L_{n}^{\leq
D_{n}}(\mathbf{A})-1)\cdot\chi_{\alpha}(\mathbf{A})\right]^{2}$
$\displaystyle=$ $\displaystyle\sum_{1\leq|\alpha|\leq
D_{n}}\left[\mathbb{E}_{P_{0,n}}(L_{n}(\mathbf{A})-1)\cdot\chi_{\alpha}(\mathbf{A})\right]^{2}$
$\displaystyle=$ $\displaystyle\sum_{1\leq|\alpha|\leq
D_{n}}(\mathbb{E}_{P_{0,n}}L_{n}(\mathbf{A})\cdot\chi_{\alpha}(\mathbf{A}))^{2}$
$\displaystyle=$ $\displaystyle\sum_{1\leq|\alpha|\leq
D_{n}}(\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A}))^{2}\,,$ (8)

where the first equality uses the property of orthonormal basis expansion, the
second uses the construction of $L_{n}^{\leq D_{n}}$, and the third uses
$\mathbb{E}_{P_{0,n}}\chi_{\alpha}(\mathbf{A})=0$ for all non-empty $\alpha$,
and the last one uses the property of likelihood ratio.

Next, we control $\sum_{1\leq|\alpha|\leq
D_{n}}(\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A}))^{2}$. To begin with, We
decouple the expectation $\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})$ as
$\mathbb{E}_{\bm{\sigma},\bm{\tau}}\mathbb{E}\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\\}$.
Given the membership $\bm{\sigma},\bm{\tau}$, $A_{t}(i_{1},i_{2})$ are
independent for any $(i_{1},i_{2},t)\in\Lambda_{n}$, namely,

$\mathbb{E}\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\\}=\prod_{(i_{1},i_{2},t)\in\alpha}\mathbb{E}\left\\{\frac{A_{t}(i_{1},i_{2})-\rho_{n}}{\sqrt{\rho_{n}(1-\rho_{n})}}\bigg{|}\bm{\sigma},\bm{\tau}\right\\}.$

Also, we remark that the following equation holds given the membership
$\bm{\sigma},\bm{\tau}$:

$\mathbb{E}\left\\{\frac{A_{t}(i_{1},i_{2})-\rho_{n}}{\sqrt{\rho_{n}(1-\rho_{n})}}\bigg{|}\bm{\sigma},\bm{\tau}\right\\}=\left\\{\begin{array}[]{l}\frac{\rho_{n}/2}{\sqrt{\rho_{n}(1-\rho_{n})}},~{}~{}\text{
if }2\mid\bm{\sigma}(i_{1})+\bm{\sigma}(i_{2})+\bm{\tau}(t);\\\
\frac{-\rho_{n}/2}{\sqrt{\rho_{n}(1-\rho_{n})}},~{}~{}\text{ if
}2\nmid\bm{\sigma}(i_{1})+\bm{\sigma}(i_{2})+\bm{\tau}(t)\\\
\end{array}\right.$

Combining the above equations, we calculate
$\mathbb{E}_{P_{1,n}}\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\\}$ as
follows,

$\displaystyle\mathbb{E}_{P_{1,n}}\left\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\right\\}$
$\displaystyle=\mathbb{E}\left\\{\prod_{(i_{1},i_{2},t)\in\alpha}\chi_{\alpha}(\mathbf{A}_{t}(i_{1},i_{2}))\big{|}\bm{\sigma},\bm{\tau}\right\\}$
$\displaystyle=\prod_{(i_{1},i_{2},t)\in\alpha}\left\\{\left(\frac{\rho_{n}/2}{\sqrt{\rho_{n}(1-\rho_{n})}}\cdot(-1)^{\bm{\sigma}(i_{1})+\bm{\sigma}(i_{2})+\bm{\tau}(t)}\right)\right\\}$
$\displaystyle=\left(\frac{\rho_{n}/2}{\sqrt{\rho_{n}(1-\rho_{n})}}\right)^{|\alpha|}\cdot(-1)^{\sum_{(i_{1},i_{2},t)\in\alpha}\left\\{\bm{\sigma}(i_{1})+\bm{\sigma}(i_{2})+\bm{\tau}(t)\right\\}}.$

Given the index set $\alpha$, for each $i\in[n]$ and $t\in[T_{n}]$, define
$u_{i,\alpha}\coloneqq\sum_{(i_{1}^{\prime},i_{2}^{\prime},t^{\prime})\in\alpha}\mathbf{1}_{i\in\\{i_{1}^{\prime},i_{2}^{\prime}\\}}$
and
$v_{t,\alpha}\coloneqq\sum_{(i_{1}^{\prime},i_{2}^{\prime},t^{\prime})\in\alpha}\mathbf{1}_{t=t^{\prime}}$.
Namely, $u_{i,\alpha}$ is the number of times that $i$ appears in $\alpha$ and
$v_{t,\alpha}$ is the number times that $t$ appears in $\alpha$. Using this
notation, we have
$\sum_{(i_{1},i_{2},t)\in\alpha}\left\\{\bm{\sigma}(i_{1})+\bm{\sigma}(i_{2})+\bm{\tau}(t)\right\\}\equiv\sum_{i\in[n],2\nmid
u_{i,\alpha}}\bm{\sigma}(i)+\sum_{t\in[T_{n}],2\nmid
v_{t,\alpha}}\bm{\tau}(t)\ (\mathrm{mod}\ 2)$. Then we have

$\mathbb{E}_{P_{1,n}}\left\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\right\\}=\left(\frac{\rho_{n}/2}{\sqrt{\rho_{n}(1-\rho_{n})}}\right)^{|\alpha|}\cdot(-1)^{\sum_{i\in[n],2\nmid
u_{i,\alpha}}\bm{\sigma}(i)+\sum_{t\in[T_{n}],2\nmid
v_{t,\alpha}}\bm{\tau}(t)}.$ (9)

Define $\kappa\coloneqq(\rho_{n}/2)/\sqrt{\rho_{n}(1-\rho_{n})}$ and recall
that
$\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})=\mathbb{E}_{\bm{\sigma},\bm{\tau}}\mathbb{E}\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\\}$,
we calculate $\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})$ as follows,

$\displaystyle\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})$
$\displaystyle=\frac{1}{\binom{n}{n/2}\binom{T_{n}}{T_{n}/2}}\sum_{\bm{\sigma}\in\mathcal{S}_{n},\bm{\tau}\in\mathcal{S}_{T_{n}}}\mathbb{E}\\{\chi_{\alpha}(\mathbf{A})|\bm{\sigma},\bm{\tau}\\}$
(10)
$\displaystyle=\frac{\kappa^{|\alpha|}}{\binom{n}{n/2}\binom{T_{n}}{T_{n}/2}}\sum_{\bm{\sigma}\in\mathcal{S}_{n},\bm{\tau}\in\mathcal{S}_{T_{n}}}(-1)^{\sum_{i\in[n],2\nmid
u_{i,\alpha}}\bm{\sigma}(i)+\sum_{t\in[T_{n}],2\nmid
v_{t,\alpha}}\bm{\tau}(t)}$
$\displaystyle=\frac{\kappa^{|\alpha|}}{\binom{n}{n/2}\binom{T_{n}}{T_{n}/2}}\sum_{\bm{\sigma}\in\mathcal{S}_{n}}(-1)^{\sum_{i\in[n],2\nmid
u_{i,\alpha}}\bm{\sigma}(i)}\cdot\sum_{\bm{\tau}\in\mathcal{S}_{T_{n}}}(-1)^{\sum_{t\in[T_{n}],2\nmid
v_{t,\alpha}}\bm{\tau}(t)}.$

For a given $\alpha$, recall the definition
$U_{\alpha}\coloneqq\\{i\in[n]:2\nmid u_{i,\alpha}\\}$ and
$V_{\alpha}\coloneqq\\{t\in[T_{n}]:2\nmid v_{t,\alpha}\\}$. We can rewrite
(10) as follows,

$\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})=\frac{\kappa^{|\alpha|}}{\binom{n}{n/2}\binom{T_{n}}{T_{n}/2}}\sum_{\bm{\sigma}\in\mathcal{S}_{n}}(-1)^{\sum_{i\in
U_{\alpha}}\bm{\sigma}(i)}\cdot\sum_{\bm{\tau}\in\mathcal{S}_{T_{n}}}(-1)^{\sum_{t\in
V_{\alpha}}\bm{\tau}(t)}.$

Let $V_{\alpha,1}=\\{t\in V_{\alpha}:\bm{\tau}(t)=1\\}$, and
$|V_{\alpha,1}|=r\in[0,|V_{\alpha}|]$. Then $(-1)^{\sum_{t\in
V_{\alpha}}\bm{\tau}(t)}=(-1)^{r}$. For a fixed $r\in[0,|V_{\alpha}|]$, the
number of $\bm{\tau}\in\mathcal{S}_{T_{n}}$ with $|V_{\alpha,1}|=r$ equals
${|V_{\alpha}|\choose r}{T_{-}-|V_{\alpha}|\choose T_{n}/2-r}$. Thus we have

$\sum_{\bm{\tau}\in\mathcal{S}_{T_{n}}}(-1)^{\sum_{t\in
V_{\alpha}}\bm{\tau}(t)}=\sum_{r=0}^{|V_{\alpha}|}(-1)^{r}\binom{|V_{\alpha}|}{r}\binom{T_{n}-|V_{\alpha}|}{T_{n}/2-r}\,.$
(11)

Similarly, we decompose $\sum_{\bm{\sigma}\in\mathcal{n}}(-1)^{\sum_{i\in
U_{\alpha}}\bm{\sigma}(i)}$ by the following equation:

$\displaystyle\sum_{\bm{\sigma}\in\mathcal{S}_{n}}(-1)^{\sum_{i\in
U_{\alpha}}\bm{\sigma}(i)}=\sum_{s=0}^{|U_{\alpha}|}(-1)^{s}\binom{|U_{\alpha}|}{s}\binom{n-|U_{\alpha}|}{n/2-s}.$
(12)

Combining (11) and (12), we calculate
$\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})$ as follows:

$\displaystyle\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})$ $\displaystyle=$
$\displaystyle\frac{\kappa^{|\alpha|}}{\binom{n}{n/2}\binom{T_{n}}{T_{n}/2}}\sum_{s=0}^{|U_{\alpha}|}(-1)^{s}\binom{|U_{\alpha}|}{s}\binom{n-|U_{\alpha}|}{n/2-s}\cdot\sum_{r=0}^{|V_{\alpha}|}(-1)^{r}\binom{|V_{\alpha}|}{r}\binom{T_{n}-|V_{\alpha}|}{T_{n}/2-r}$
$\displaystyle\stackrel{{\scriptstyle\displaystyle(a)}}{{=}}$
$\displaystyle\frac{\kappa^{|\alpha|}}{\binom{n}{|U_{\alpha}|}\binom{T_{n}}{|V_{\alpha}|}}\sum_{s=0}^{|U_{\alpha}|}(-1)^{s}\binom{n/2}{s}\binom{n/2}{|U_{\alpha}|-s}\cdot\sum_{r=0}^{|V_{\alpha}|}(-1)^{r}\binom{T_{n}/2}{r}\binom{T_{n}/2}{|V_{\alpha}|-r}\,,$
(13)

where $\displaystyle(a)$ is guaranteed by the fact

$\frac{\binom{|U_{\alpha}|}{s}\binom{n-|U_{\alpha}|}{n/2-s}}{\binom{n}{n/2}}=\frac{\frac{(n/2)!}{s!(n/2-s)!}\cdot\frac{(n/2)!}{(|U_{\alpha}|-s)!(n/2+s-|U_{\alpha}|)!}}{\frac{n!}{|U_{\alpha}|!(n-|U_{\alpha}|)!}}=\frac{\binom{n/2}{s}\binom{n/2}{|U_{\alpha}|-s}}{\binom{n}{|U_{\alpha}|}}.$

Now we propose the following useful lemma to calculate (13), we refer the
reader to Appendix B for a complete proof.

According to Lemma B.1, $\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})\neq 0$
only if $2\mid|U_{\alpha}|$ and $2\mid|V_{\alpha}|$, and in this case we have

$\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A})=\frac{\kappa^{|\alpha|}(-1)^{|U_{\alpha}|/2+|V_{\alpha}|/2}\binom{n/2}{|U_{\alpha}|/2}\binom{T_{n}/2}{|V_{\alpha}|/2}}{\binom{n}{|U_{\alpha}|}\binom{T_{n}}{|V_{\alpha}|}}\,.$
(14)

Plugging (14) into (13) and further into (8), we obtain the following
expression for $\lVert L_{n}^{\leq D_{n}}(\mathbf{A})-1\rVert^{2}$:

$\displaystyle\lVert L_{n}^{\leq D_{n}}(\mathbf{A})-1\rVert^{2}$
$\displaystyle=\sum_{1\leq|\alpha|\leq
D_{n}}(\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A}))^{2}=\sum_{a=1}^{D_{n}}\sum_{\alpha\subseteq\Lambda_{n},|\alpha|=a}(\mathbb{E}_{P_{1,n}}\chi_{\alpha}(\mathbf{A}))^{2}$
$\displaystyle=\sum_{a=1}^{D_{n}}\kappa^{2a}\sum_{\begin{subarray}{c}|\alpha|=a\\\
2\mid|U_{\alpha}|,2\mid|V_{\alpha}|\end{subarray}}\frac{\binom{n/2}{|U_{\alpha}|/2}^{2}\binom{T_{n}/2}{|V_{\alpha}|/2}^{2}}{\binom{n}{|U_{\alpha}|}^{2}\binom{T_{n}}{|V_{\alpha}|}^{2}}\,.$
(15)

Recall the definition
$\Lambda_{n,a,r,k}\coloneqq\\{\alpha\subseteq\Lambda_{n}:|\alpha|=a,|U_{\alpha}|=2r,|V_{\alpha}|=2k\\}$.
Using this notation, (15) can be rewritten as follows:

$\lVert L_{n}^{\leq
D_{n}}(\mathbf{A})-1\rVert^{2}=\sum_{a=1}^{D_{n}}\kappa^{2a}\sum_{r=0}^{a}\sum_{k=0}^{[a/2]}|\Lambda_{n,a,r,k}|\frac{\binom{n/2}{r}^{2}\binom{T_{n}/2}{k}^{2}}{\binom{n}{2r}^{2}\binom{T_{n}}{2k}^{2}}\,.\qed$

###### Proof of Lemma 3.6.

In this proof, we write $T$ for $T_{n}$ to simplify the notation.

To begin with, define
$\Omega_{n,a,r,k}\coloneqq\\{\alpha\subseteq[n]\times[n]\times[T_{n}]:|\alpha|=a,|U_{\alpha}|=2r,|V_{\alpha}|=2k\\}$,
where the definition of $U_{\alpha}$ and $V_{\alpha}$ is the same as in the
definition of $\Lambda_{n,a,r,k}$. We remark that the only difference between
$\Omega_{n,a,r,k}$ and $\Lambda_{n,a,r,k}$ is that for any
$\alpha\in\Omega_{n,a,r,k}$ and any tuple $(i_{1},i_{2},t)\in\alpha$, we do
not require $i_{1}<i_{2}$. Therefore,

$|\Lambda_{n,a,r,k}|\leq|\Omega_{n,a,r,k}|.$

In the remaining of this proof, we bound $|\Omega_{n,a,r,k}|$.

For an arbitrary $\alpha\subseteq[n]\times[n]\times[T]$, define
$x_{\alpha}(i)=\sum_{(i_{1},i_{2},t)\in\alpha}\left(\mathds{1}(i_{1}=i)+\mathds{1}(i_{2}=i)\right)$,
i.e., the total number of times $i$ appears in $\alpha$. Similarly, define
$y_{\alpha}(t)=\sum_{(i_{1},i_{2},t_{1})\in\alpha}\mathds{1}(t=t_{1})$.

Recall that a multi-set is a set that keeps track of the multiplicities of
each element. For example, a multiple set $\\{1,1,2\\}$ is the same as
$\\{1,2,1\\}$ but different from $\\{1,2\\}$ and $\\{1,2,2\\}$.

Let $\mathcal{I}_{a,r}$ be the collection of all multi-sets
$\beta\subseteq[n]\times[n]$ such that (i) there are exactly $2r$
$x_{\beta}(i)$’s being odd, and (ii) $|\beta|=a$, where $x_{\beta}(i)$ is
defined similarly as $x_{\alpha}(i)$.

Let $\mathcal{T}_{a,k}$ be the collection of all multi-sets
$\gamma\subseteq[T]$ such that (i) there are exactly $2k$ $y_{\gamma}(t)$’s
being odd, and (ii) $|\gamma|=a$.

For each $\alpha\in\Omega_{a,r,k}$. Write
$\alpha=\\{(i_{1},j_{1},t_{1}),...,(i_{a},j_{a},t_{a})\\}$. Define
$\beta=\\{(i_{1},j_{1}),...,(i_{a},j_{a})\\}$ and
$\gamma=\\{t_{1},...,t_{n}\\}$. Then $\beta\in\mathcal{I}_{a,r}$ and
$\gamma\in\mathcal{T}_{a,k}$. This defines a mapping
$h:\Omega_{a,r,k}\mapsto\mathcal{I}_{a,r}\times\mathcal{T}_{a,k}$. Given
$\beta\in\mathcal{I}_{a,r}$ and $\gamma\in\mathcal{T}_{a,k}$, there are at
most $a!$ ways to pair them, and the claimed result follows. So
$|h^{-1}(\beta,\gamma)|\leq a!$ for each
$(\beta,\gamma)\in\mathcal{I}_{a,r}\times\mathcal{T}_{a,r}$. Thus we arrive at
the following

$|\Omega_{n,a,r,k}|\leq|\mathcal{I}_{a,r}|\times|\mathcal{T}_{a,k}|\times
a!\,.$ (16)

Bounding $|\mathcal{I}_{a,r}|$. Now let $\mathcal{J}_{a,r}$ be the collection
of multi-sets consisting of elements in $[n]$ such that for each
$\delta\in\mathcal{J}_{a,r}$, (i) $|\delta|=2a$, and (ii) there are exactly
$2r$ $x_{\delta}(i)$’s being odd, where
$x_{\delta}(i)=\sum_{j\in\delta}\mathds{1}(i=j)$.

Each $\beta=\\{(i_{1},j_{1}),...,(i_{a},j_{a})\\}\in\mathcal{I}_{a,r}$ maps to
a $\delta=\\{i_{1},j_{1},...,i_{a},j_{a}\\}\in\mathcal{J}_{a,r}$. For
$\delta\in\mathcal{J}_{a,r}$, the inverse mapping is pairing up the elements
of $\delta$, and there are at most ${2a\choose a}$ possible ways. So we have

$|\mathcal{I}_{a,r}|\leq|\mathcal{J}_{a,r}|{2a\choose a}\,.$ (17)

Now we decompose $\mathcal{J}_{a,r}=\bigsqcup_{u=0}^{a-r}\mathcal{J}_{a,r,u}$,
where $\mathcal{J}_{a,r,u}$ consists of elements in $\mathcal{J}_{a,r}$ in
which the odd indices appear a total of $2r+2u$ times. We construct an element
$\delta$ in $\mathcal{J}_{a,r,u}$ in three steps. In order to specify an
element $\delta\in\mathcal{J}_{a,r}$, it is equivalent to specify
$x_{\delta}(i)$ for each $i\in[n]$. First, we pick $2r$ indices in $[n]$ for
which $x_{\delta}(i)$ is odd. There are ${n\choose 2r}$ ways for this step.
Second, we specify $x_{\delta}(i)$ for these $2r$ indices. This corresponds to
solving the equation $z_{1}+...+z_{2r}=u$ over non-negative integers
$z_{1},...z_{2r}$. The number of ways of doing this is ${u+2r-1\choose u}$.
Third, we need to specify $x_{\delta}(i)$ for the remaining $n-2r$ indices.
This corresponds to solving $z_{1}+...+z_{n-2r}=a-r-u$. There are
${n+a-3r-u-1\choose a-r-u}$ different ways. So we arrive at

$\displaystyle|\mathcal{I}_{a,r}|\leq$ $\displaystyle{2a\choose
a}|\mathcal{J}_{a,r}|$ $\displaystyle\leq$ $\displaystyle{2a\choose
a}{n\choose 2r}\sum_{u=0}^{a-r}{u+2r-1\choose u}{n+a-3r-u-1\choose a-r-u}$
(18) $\displaystyle\leq$ $\displaystyle 2{2a\choose a}(n+a-3r-1)^{a-r}$
$\displaystyle\leq$ $\displaystyle(1+o(1))2{2a\choose a}(n+a-1)^{a-r}\,,$ (19)

where the third inequality follows by the fact that when $a/n\leq D_{n}/n$ is
sufficiently small, the summands in the RHS are upper bounded by a geometric
sequence whose decay rate is at least $1/2$ so that the sum is bounded by
twice of the first term.

Now we turn to $|\mathcal{T}_{a,k}|$. Let $a_{T}=\min(a,T)$. For the same
decomposition and three-step construction for $\mathcal{J}_{a,r,u}$ we have

$\displaystyle|\mathcal{T}_{a,k}|\leq$
$\displaystyle\sum_{v=0}^{a_{T}/2-k}{T\choose 2k}{2k+v-1\choose
v}{T+a_{T}/2-3k-v-1\choose a_{T}/2-k-v}\,.$ (20)

If $T\gg a^{2}$, then $a_{T}=a$ and the same argument as in (19) leads to

$|\mathcal{T}_{a,k}|\leq 2{T\choose 2k}(T+a/2-3k-1)^{a/2-k}\,.$ (21)

In general, (20) can be bounded by

$\displaystyle|\mathcal{T}_{a,k}|\leq$ $\displaystyle{T\choose
2k}(a_{T}/2-k){a_{T}/2+k-1\choose a_{T}/2-k}{T+a_{T}/2-3k-1\choose a_{T}/2-k}$
$\displaystyle\leq$ $\displaystyle{T\choose
2k}(a_{T}/2-k)(a_{T}/2+k-1)^{(a_{T}/2-k)\wedge(2k-1)}{T+a_{T}/2-3k-1\choose
a_{T}/2-k}$ $\displaystyle\leq$ $\displaystyle{T\choose
2k}(a_{T}/2-k)(a_{T}/2+k-1)^{a_{T}/3-1}{T+a_{T}/2-3k-1\choose a_{T}/2-k}$
$\displaystyle\leq$ $\displaystyle{T\choose
2k}a_{T}^{a_{T}/3}(T+a_{T}/2-1)^{a_{T}/2-k}\,.$ (22)

Plugging (19) and (22) into (16), we have arrive at the bound

$\displaystyle|\Omega_{n,a,r,k}|\leq$
$\displaystyle(1+o(1))2\frac{(2a)!}{a!}a_{T}^{a_{T}/3}{n\choose 2r}{T\choose
2k}(n+a-1)^{a-r}(T+a_{T}/2-1)^{a_{T}/2-k}$ $\displaystyle\leq$ $\displaystyle
2^{1+a}a^{4a/3}{n\choose 2r}{T\choose
2k}(n+a-1)^{a-r}(T+a_{T}/2-1)^{a_{T}/2-k}$ $\displaystyle\leq$ $\displaystyle
2^{1+5a/2}a^{4a/3}{n\choose 2r}{T\choose 2k}n^{a-r}T^{a/2-k}\,,$

where the last inequality uses $n+a-1\leq 2n$ and $T+a_{T}/2-1\leq 2T$.

When $T\gg a^{2}$, the bound strengthens to

$\displaystyle|\Omega_{n,a,r,k}|\leq 2^{1+5a/2}a^{a}{n\choose 2r}{T\choose
2k}n^{a-r}T^{a/2-k}\,.\qed$

######  Lemma B.1.

For any positive integer $m$ and $0\leq k\leq m$, the following equation
holds:

$\sum_{i=0}^{k}(-1)^{i}\binom{m}{i}\binom{m}{k-i}=\left\\{\begin{aligned}
&0,~{}~{}&\text{if}~{}~{}2\nmid k;\\\
&(-1)^{k/2}\binom{m}{k/2},~{}~{}&\text{if}~{}~{}2\mid k.\\\
\end{aligned}\right.$

###### Proof of Lemma B.1.

For any positive integer $m$ and $0\leq k\leq m$, we consider the following
polynomial:

$g(x)=(1-x)^{m}(1+x)^{m}.$

We compute the coefficient of the $x^{k}$ term in $g(x)$, where we leverage
the following form,

$g(x)=\left(\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}x^{i}\right)\left(\sum_{i=0}^{m}\binom{m}{i}x^{i}\right).$

Therefore, the coefficient for $x^{k}$ is
$\sum_{i=0}^{k}(-1)^{i}\binom{m}{i}\binom{m}{k-i}$.

Besides, we remark that $g(x)=(1-x^{2})^{m}$, which further implies that

$g(x)=\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}x^{2i}.$

Thus, the coefficient of $x^{k}$ is zero if $2\nmid k$, and the coefficient is
$(-1)^{k/2}\binom{m}{k/2}$ if $2\mid k$. ∎

### Details for (3)

###### Proof.

Combining Lemma 3.5 and Lemma 3.6 we get

$\displaystyle\lVert L_{n}^{\leq D_{n}}(\mathbf{A})-1\rVert^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{a=1}^{D_{n}}\frac{\rho_{n}^{a}}{(4(1-\rho_{n}))^{a}}2^{1+5a/2}a^{4a/3}\sum_{r=0}^{a}\sum_{k=0}^{a/2}\frac{\binom{n/2}{r}^{2}\binom{T_{n}/2}{k}^{2}}{\binom{n}{2r}\binom{T_{n}}{2k}}n^{a-r}T_{n}^{a/2-k}$
$\displaystyle=$
$\displaystyle\sum_{a=1}^{D_{n}}\frac{\rho_{n}^{a}}{(4(1-\rho_{n}))^{a}}2^{1+5a/2}a^{4a/3}\left[\sum_{r=0}^{a}\frac{\binom{n/2}{r}^{2}}{\binom{n}{2r}}n^{a-r}\right]\left[\sum_{k=0}^{a/2}\frac{\binom{T_{n}/2}{k}^{2}}{\binom{T_{n}}{2k}}T_{n}^{a/2-k}\right]\,.$
(23)

It suffices to provide upper bounds for the two inner sums.

For $r\leq a\leq D_{n}=o(n)$, the terms in the sequence

$\frac{{n/2\choose r}^{2}}{{n\choose 2r}}n^{a-r}\,,\quad r=0,...,a$

are bounded by a geometric sequence with a decay rate of at least $1/2$ by
Stirling’s formula. Therefore their sum is bounded by twice the first term and
we get

$\displaystyle\sum_{r=0}^{a}\frac{\binom{n/2}{r}^{2}}{\binom{n}{2r}}n^{a-r}\leq
2n^{a}\,.$ (24)

By Stirling’s formula, when $1\leq k\leq T/2-1$, we have

$\frac{{T/2\choose k}^{2}}{{T\choose 2k}}\leq cT^{1/2}$

for some universal constant $c$. Therefore

$\displaystyle\sum_{k=0}^{a/2}\frac{\binom{T_{n}/2}{k}^{2}}{\binom{T_{n}}{2k}}T^{a/2-k}\leq
T_{n}^{a/2}+1+cT_{n}^{1/2}\sum_{k=1}^{(a/2)\wedge(T_{n}/2-1)}T_{n}^{a/2-k}$
$\displaystyle\leq$ $\displaystyle
T_{n}^{a/2}+1+2cT_{n}^{1/2}T_{n}^{a/2-1}\leq 2T_{n}^{a/2}\,.$ (25)

Plugging (24) and (25) into (23) leads to the desired result. ∎

##  Appendix C Proofs for information-theoretic bounds

###### Proof of Theorem 4.1.

First we expand the $\chi^{2}$ divergence between $P_{1,\bm{\tau},n}$ and
$P_{0,n}$.

$\displaystyle\sum_{\mathbf{A}}\frac{P_{1,\bm{\tau},n}^{2}(\mathbf{A})}{P_{0,n}(\mathbf{A})}$
(26) $\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{n/2}^{2}}\sum_{\mathbf{A}}\frac{\sum_{\bm{\sigma}_{1},\bm{\sigma}_{2}}P_{\bm{\sigma}_{1},\bm{\tau}}(\mathbf{A})P_{\bm{\sigma}_{2},\bm{\tau}}(\mathbf{A})}{P_{0,n}(\mathbf{A})}=\frac{1}{\binom{n}{n/2}^{2}}\sum_{\bm{\sigma}_{1}}\sum_{\bm{\sigma}_{2}}\sum_{\mathbf{A}}\frac{P_{\bm{\sigma}_{1},\bm{\tau}}(\mathbf{A})P_{\bm{\sigma}_{2},\bm{\tau}}(\mathbf{A})}{P_{0,n}(\mathcal{\mathbf{A}})}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{n/2}^{2}}\sum_{\bm{\sigma}_{1},\bm{\sigma}_{2}}\prod_{1\leq
i<j\leq
n,t\in[T_{n}]}\left(\frac{P_{\bm{\sigma}_{1},\bm{\tau}}(\mathbf{A}_{t}(i,j)=1)P_{\bm{\sigma}_{2},\bm{\tau}}(\mathbf{A}_{t}(i,j)=1)}{P_{0,n}(\mathbf{A}_{t}(i,j)=1)}\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left.+\frac{P_{\bm{\sigma}_{1},\bm{\tau}}(\mathbf{A}_{t}(i,j)=0)P_{\bm{\sigma}_{2},\bm{\tau}}(\mathbf{A}_{t}(i,j)=0)}{P_{0,n}(\mathbf{A}_{t}(i,j)=0)}\right).$

Since each membership $\bm{\sigma}\in\mathcal{S}_{n}$ has $n/2$ terms as $0$
and $n/2$ as $1$, we can fix $\bm{\sigma}_{1}$ and consider the sum for all
$\bm{\sigma}_{2}$. For $\bm{\sigma}_{1}$ and any $\bm{\sigma}_{2}$, define
sets

$\displaystyle\Omega_{1}=$ $\displaystyle\\{(i,j,t):1\leq i<j\leq
n,t\in[T],2\nmid\bm{\sigma}_{1}(i)+\bm{\sigma}_{1}(j)+\bm{\tau}(t),2\nmid\bm{\sigma}_{2}(i)+\bm{\sigma}_{2}(j)+\bm{\tau}(t)\\}$
$\displaystyle\Omega_{2}=$ $\displaystyle\\{(i,j,t):1\leq i<j\leq
n,t\in[T],2\nmid\bm{\sigma}_{1}(i)+\bm{\sigma}_{1}(j)+\bm{\tau}(t),2\mid\bm{\sigma}_{2}(i)+\bm{\sigma}_{2}(j)+\bm{\tau}(t)\\}$
$\displaystyle\Omega_{3}=$ $\displaystyle\\{(i,j,t):1\leq i<j\leq
n,t\in[T],2\mid\bm{\sigma}_{1}(i)+\bm{\sigma}_{1}(j)+\bm{\tau}(t),2\nmid\bm{\sigma}_{2}(i)+\bm{\sigma}_{2}(j)+\bm{\tau}(t)\\}$
$\displaystyle\Omega_{4}=$ $\displaystyle\\{(i,j,t):1\leq i<j\leq
n,t\in[T],2\mid\bm{\sigma}_{1}(i)+\bm{\sigma}_{1}(j)+\bm{\tau}(t),2\mid\bm{\sigma}_{2}(i)+\bm{\sigma}_{2}(j)+\bm{\tau}(t)\\}$

Let $c=|\bm{\sigma}_{1}^{-1}(1)\cap\bm{\sigma}_{2}^{-1}(1)|$. The sizes of
$\Omega_{j},j\in[4]$ satisfy:

$\displaystyle|\Omega_{1}|+|\Omega_{4}|$
$\displaystyle=(2c^{2}+2(n/2-c)^{2}-n/2)T_{n},$ (27)
$\displaystyle|\Omega_{2}|+|\Omega_{3}|$ $\displaystyle=4T_{n}(c(n/2-c))\,.$

The RHS of (26) can be rewritten by combining the same terms according to the
membership of the triplet $(i,j,t)$ in $\Omega_{k}$ ($1\leq k\leq 4$):

$\displaystyle\sum_{\mathbf{A}}\frac{P_{1,\bm{\tau},n}^{2}(\mathbf{A})}{P_{0,n}(\mathbf{A})}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{n/2}^{2}}\sum_{\bm{\sigma}_{1}}\sum_{\bm{\sigma}_{2}}\left(\frac{3\rho_{n}/2\cdot
3\rho_{n}/2}{\rho_{n}}+\frac{(1-3\rho_{n}/2)\cdot(1-3\rho_{n}/2)}{1-\rho_{n}}\right)^{|\Omega_{1}|}$
$\displaystyle\quad\times\left(\frac{3\rho_{n}/2\cdot\rho_{n}/2}{\rho_{n}}+\frac{(1-3\rho_{n}/2)\cdot(1-\rho_{n}/2)}{1-\rho_{n}}\right)^{|\Omega_{2}|}$
$\displaystyle\quad\times\left(\frac{\rho_{n}/2\cdot
3\rho_{n}/2}{\rho_{n}}+\frac{(1-\rho_{n}/2)\cdot(1-3\rho_{n}/2)}{1-\rho_{n}}\right)^{|\Omega_{3}|}$
$\displaystyle\quad\times\left(\frac{\rho_{n}/2\cdot\rho_{n}/2}{\rho_{n}}+\frac{(1-\rho_{n}/2)\cdot(1-\rho_{n}/2)}{1-\rho_{n}}\right)^{|\Omega_{4}|}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{n/2}^{2}}\sum_{\bm{\sigma}_{1}}\sum_{\bm{\sigma}_{2}}\left(\frac{1-3\rho_{n}/4}{1-\rho_{n}}\right)^{|\Omega_{1}|+|\Omega_{4}|}\left(\frac{1-5\rho_{n}/4}{1-\rho_{n}}\right)^{|\Omega_{2}|+|\Omega_{3}|}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{n/2}}\sum_{c=0}^{n/2}\binom{n/2}{c}^{2}\left(\frac{1-3\rho_{n}/4}{1-\rho_{n}}\right)^{2T_{n}(c^{2}+(n/2-c)^{2}-n/4)}\left(\frac{1-5\rho_{n}/4}{1-\rho_{n}}\right)^{4T_{n}(c(n/2-c))}.$
(28)

Observe that $2T_{n}(c^{2}+(n/2-c)^{2}-n/4)+4T_{n}(c(n/2-c))={n\choose
2}T_{n}$, and hence

$\displaystyle\sum_{\mathbf{A}}\frac{P_{1,\bm{\tau},n}^{2}(\mathbf{A})}{P_{0,n}(\mathbf{A})}$
$\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{n/2}}\left(\frac{(1-3\rho_{n}/4)(1-5\rho_{n}/4)}{(1-\rho_{n})^{2}}\right)^{{n\choose
2}T_{n}/2}$
$\displaystyle\quad\times\sum_{c=0}^{n/2}\binom{n/2}{c}^{2}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2T_{n}(c^{2}+(n/2-c)^{2}-n/4)-{n\choose
2}T_{n}/2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{\binom{n}{n/2}}\left(\frac{(1-3\rho_{n}/4)(1-5\rho_{n}/4)}{(1-\rho_{n})^{2}}\right)^{{n\choose
2}T_{n}/2}$
$\displaystyle\quad\times\sum_{c=0}^{n/2}\binom{n/2}{c}^{2}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2T_{n}(c-n/4)^{2}}.$
(29)

Whenever $\rho_{n}=o((1/(n\sqrt{T_{n}}))$ and $n,T_{n}\rightarrow\infty$, we
have

$\left(\frac{(1-3\rho_{n}/4)(1-5\rho_{n}/4)}{(1-\rho_{n})^{2}}\right)^{{n\choose
2}T_{n}/2}=\left(1-\frac{\rho_{n}^{2}/16}{(1-\rho_{n})^{2}}\right)^{{n\choose
2}T_{n}/2}\rightarrow 1.$

Thus, we can drop the second term in the RHS of (29).

Next, let $\kappa=\kappa_{n}$ be such that $\kappa_{n}\rightarrow\infty$ and
$\kappa_{n}^{2}nT_{n}\rho_{n}\rightarrow 0$. For example, under the condition
$nT_{n}\rho_{n}\rightarrow 0$ we can pick
$\kappa_{n}=(nT_{n}\rho_{n})^{-1/3}$. Define $n_{1}=n/4-\kappa n^{1/2}$,
$n_{2}=n/4+\kappa n^{1/2}$. We decompose (29) into three terms:

$\displaystyle\sum_{\mathbf{A}}\frac{P_{1,\bm{\tau},n}^{2}(\mathbf{A})}{P_{0,n}(\mathbf{A})}=(1+o(1))\times$
$\displaystyle\frac{1}{\binom{n}{n/2}}\bigg{[}\underbrace{\sum_{0\leq c\leq
n_{1}}}_{\displaystyle\mathrm{(I)}}+\underbrace{\sum_{n_{1}<c<n_{2}}}_{\displaystyle\mathrm{(II)}}+\underbrace{\sum_{n_{2}\leq
c\leq
n/2}}_{\displaystyle\mathrm{(III)}}\bigg{]}\binom{n/2}{c}^{2}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2T_{n}(c-n/4)^{2}}.$

We remark that $\displaystyle\mathrm{(I)}=\displaystyle\mathrm{(III)}$ by the
symmetry of combination numbers and only have to handle (I) and (II). Next, we
are going to prove that

$\displaystyle{\mathrm{(I)}}=o(1)~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\displaystyle{\mathrm{(II)}}\leq
1+o(1).$

Bounding (II). For any $c\in[n_{1},n_{2}]$,

$\displaystyle\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2T_{n}(c-n/4)^{2}}\leq\left(1+\frac{\rho_{n}/2}{1-5\rho_{n}/4}\right)^{2\kappa^{2}nT_{n}}$
$\displaystyle\leq$ $\displaystyle(1+\rho_{n})^{2\kappa^{2}nT_{n}}\leq
e^{2\kappa^{2}nT_{n}\rho_{n}}\rightarrow 1,$

where we use the inequality $(1+x/y)^{y}\leq e^{x}$ for any $y>1,|x|\leq y$.
Plugging in the above inequality, we have

$\displaystyle\mathrm{(II)}\leq\frac{1}{\binom{n}{n/2}}\sum_{c=n_{1}}^{n_{2}}\binom{n/2}{c}^{2}e^{2\kappa^{2}nT_{n}\rho_{n}}\leq
1+o(1).$

Bounding (I). We decompose (I) into two terms: for $d\in(0,1/4)$,

$\displaystyle{\mathrm{(I)}}=\frac{1}{\binom{n}{n/2}}\bigg{[}\underbrace{\sum_{c=0}^{n/4-dn}}_{\displaystyle\mathrm{(IV)}}+\underbrace{\sum_{c=n/4-dn}^{n_{1}}}_{\displaystyle\mathrm{(V)}}\bigg{]}\binom{n/2}{c}^{2}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2T_{n}(c-n/4)^{2}}\,.$

For (IV), we have

$\displaystyle{\mathrm{(IV)}}\leq\frac{\sum_{c=0}^{n/4-dn}\binom{n/2}{c}^{2}}{\binom{n}{n/2}}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{n^{2}T_{n}/8}.$
(30)

Observe that $\frac{\sum_{c=0}^{n/4-dn}\binom{n/2}{c}^{2}}{\binom{n}{n/2}}$ is
the probability of a hypergeometric-$(n,n/2,n/2)$ random variable being less
than or equal to $n/4-dn$. Using Lemma C.1 with $N=n$, $K=m=n/2$, we obtain

$\frac{\sum_{c=0}^{n/4-dn}\binom{n/2}{c}^{2}}{\binom{n}{n/2}}=P({\rm
HG}(n,n/2,n/2)\leq n/4-dn)\leq e^{-4d^{2}n}.$

Plugging this inequality into (30), we have

$\displaystyle{\mathrm{(IV)}}\leq
e^{-4d^{2}n}e^{\rho_{n}n^{2}T_{n}}=e^{-n(4d^{2}-nT_{n}\rho_{n})}.$

Thus, $\displaystyle{\mathrm{(IV)}}\rightarrow 0$ for any constant $d>0$ and
$n,T_{n}\rightarrow\infty$.

For (V), we have

$\displaystyle{\mathrm{(V)}}$
$\displaystyle=\frac{1}{\binom{n}{n/2}}\sum_{c=n/4-dn}^{n_{1}}\binom{n/2}{c}^{2}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{T_{n}[2(c-n/4)^{2}]}$
(31)
$\displaystyle=\frac{1}{\binom{n}{n/2}}\sum_{r=\kappa\sqrt{n}}^{dn}\binom{n/2}{n/4-r}^{2}\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2r^{2}T_{n}}.$

First, observe that

$\left(\frac{1-3\rho_{n}/4}{1-5\rho_{n}/4}\right)^{2r^{2}T_{n}}=\left(1+\frac{\rho_{n}/2}{1-5\rho_{n}/4}\right)^{2r^{2}T_{n}}\leq
e^{2r^{2}T_{n}\rho_{n}}\,,$

Using the Stirling formula, we have

$\binom{n}{n/2}^{-1}\lesssim n^{1/2}\cdot 2^{-n}\,,$

and

$\displaystyle\binom{n/2}{n/4-r}^{2}$
$\displaystyle=\left(\frac{(n/2)!}{(n/4-r)!(n/4+r)!}\right)^{2}\lesssim
n^{-1}\cdot
2^{n}\left(\frac{n^{2}/16}{n^{2}/16-r^{2}}\right)^{n/2-2r}\left(\frac{n/4}{n/4+r}\right)^{4r}$
$\displaystyle=n^{-1}\cdot
2^{n}\left(1+\frac{1}{n^{2}/(16r^{2})-1}\right)^{n/2-2r}\left(1-\frac{1}{n/(4r)+1}\right)^{4r}$
$\displaystyle\leq n^{-1}\cdot 2^{n}\cdot
e^{\frac{n/2-2r}{n^{2}/(16r^{2})-1}}\cdot e^{-\frac{4r}{n/(4r)+1}}$
$\displaystyle=n^{-1}\cdot 2^{n}\cdot
e^{-r^{2}n^{-1}\left(\frac{2}{1/4+r/n}\right)}$ $\displaystyle\leq n^{-1}\cdot
2^{n}\cdot e^{-4r^{2}n^{-1}}\,,$

where the last inequality follows from $r\leq dn<n/4$.

Plugging the above three inequalities into (31), we obtain the following
bound:

$\displaystyle\displaystyle{\mathrm{(V)}}\lesssim$ $\displaystyle
n^{-1/2}\sum_{r=\kappa\sqrt{n}}^{dn}e^{-2r^{2}n^{-1}\left(2-nT_{n}\rho_{n}\right)}\leq
n^{-1/2}\sum_{r=\kappa\sqrt{n}}^{dn}e^{-2r^{2}/n}$ $\displaystyle\leq$
$\displaystyle
n^{-1/2}\int_{\kappa\sqrt{n}}^{\infty}e^{-2r^{2}/n}dr=\int_{\kappa}^{\infty}e^{-2s^{2}}ds\lesssim
e^{-2\kappa^{2}}\,,$

provided that $nT_{n}\rho_{n}\leq 1$ and $\kappa\geq 1$. In summary, we prove
that $\displaystyle{\mathrm{(I)}=\mathrm{(IV)}+\mathrm{(V)}}\rightarrow 0$ and
$\displaystyle{\mathrm{(II)}}\rightarrow 1$. These results together show that

$\sum_{\mathbf{A}}\frac{P_{1,\bm{\tau},n}^{2}(\mathbf{A})}{P_{0,n}(\mathbf{A})}=2\cdot\displaystyle{\mathrm{(I)}}+\displaystyle{\mathrm{(II)}}\rightarrow
1.\qed$

######  Lemma C.1 (Eq. (14) in [46]).

Let $X\sim\text{Hypergeometric}(N,K,m)$ and $p=K/N$. Then for $0<t<mK/N$ we
can derive the following bound:

$P(X\leq(p-t)m)\leq e^{-2t^{2}m}.$

###### Proof of Theorem 4.2.

To simplify notation, we denote

$A=\bm{\sigma}^{-1}(0)\,,\quad B=[n]\backslash A\,,\quad
C=\bm{\tau}^{-1}(0)\,,\quad D=[T_{n}]\backslash C\,.$

For disjoint node set $X$ and layer set $Y$, we use $e(X,X,Y)$ to denote the
number of distinct edges between nodes in $X$ and in layers indexed by $Y$:

$e(X,X,Y)=\sum_{i<j,(i,j,t)\in X^{2}\times Y}A_{t}(i,j)\,.$

Let $X^{\prime}$ be another node set disjoint with $X$, we use
$e(X,X^{\prime},Y)$ to denote the number of edges between $X$ and $X^{\prime}$
in layers indexed by $Y$:

$e(X,X^{\prime},Y)=\sum_{(i,j,t)\in X\times X^{\prime}\times Y}A_{t}(i,j)\,.$

With this notation, the MLE estimator in (4) can be equivalently written as

$\arg\max\max_{A\subseteq[n]:|A|=n/2,C\subseteq[T_{n}]:|C|=T_{n}/2}$

Let

$\displaystyle A_{w}=$ $\displaystyle A\cap\hat{\bm{\sigma}}_{\rm
mle}^{-1}(1)\,,\quad B_{w}=B\cap\hat{\bm{\sigma}}_{\rm mle}^{-1}(0)\,,$
$\displaystyle C_{w}=$ $\displaystyle C\cap\hat{\bm{\tau}}_{\rm
mle}^{-1}(1)\,,\quad D_{w}=D\cap\hat{\bm{\tau}}_{\rm mle}^{-1}(0)\,.$

In other words, $A_{w}$, $B_{w}$, $C_{w}$, and $D_{w}$ are the set of nodes or
layers for which the MLE memberships are incorrect.

Assume $d_{\rm Ham}(\hat{\bm{\sigma}}_{\rm mle},\bm{\sigma})\leq d_{\rm
Ham}(1-\hat{\bm{\sigma}}_{\rm mle},\bm{\sigma})$ (otherwise we will simply
consider $1-\hat{\bm{\sigma}}_{\rm mle}$ instead). Then we have
$|A_{w}|=|B_{w}|=k\in[0,n/4]$, and $|C_{w}|=|D_{w}|=s\in[0,T_{n}/4]$.

Use the correspondence

$\displaystyle\hat{A}=$ $\displaystyle\hat{\bm{\sigma}}^{-1}(0)=(A\backslash
A_{w})\cup B_{w}\,,\quad\hat{B}=\hat{\bm{\sigma}}^{-1}(1)=(B\backslash
B_{w})\cup A_{w}\,,$ $\displaystyle\hat{C}=$
$\displaystyle\hat{\bm{\tau}}^{-1}(0)=(C\backslash C_{w})\cup
D_{w}\,,\quad\hat{D}=\hat{\bm{\tau}}^{-1}(1)=(D\backslash D_{w})\cup C_{w}\,.$

Then through the construction of MLE, we have

$\displaystyle
e(\hat{A},\hat{A},\hat{C})+e(\hat{B},\hat{B},\hat{C})+e(\hat{A},\hat{B},\hat{D})\geq
e(A,A,C)+e(B,B,C)+e(A,B,D)\,,$

which is equivalent to

$\displaystyle e(A\backslash A_{w},A\backslash
A_{w},C_{w})+e(A_{w},A_{w},C_{w})+e(B\backslash B_{w},B\backslash
B_{w},C_{w})+e(B_{w},B_{w},C_{w})$ $\displaystyle+e(A\backslash
A_{w},A_{w},C\backslash C_{w})+e(B\backslash B_{w},B_{w},C\backslash
C_{w})+e(A\backslash A_{w},B_{w},D\backslash D_{w})$
$\displaystyle+e(B\backslash B_{w},A_{w},D\backslash D_{w})+e(A\backslash
A_{w},B\backslash B_{w},D_{w})+e(A_{w},B_{w},D_{w})$ $\displaystyle\leq$
$\displaystyle e(A\backslash A_{w},A\backslash
A_{w},D_{w})+e(A_{w},A_{w},D_{w})+e(B\backslash B_{w},B\backslash
B_{w},D_{w})+e(B_{w},B_{w},D_{w})$ $\displaystyle+e(A\backslash
A_{w},A_{w},D\backslash D_{w})+e(B\backslash B_{w},B_{w},D\backslash
D_{w})+e(A\backslash A_{w},B_{w},C\backslash C_{w})$
$\displaystyle+e(B\backslash B_{w},A_{w},C\backslash C_{w})+e(A\backslash
A_{w},B\backslash B_{w},C_{w})+e(A_{w},B_{w},C_{w})\,.$ (32)

All terms are sums of distinct independent Bernoulli random variables. The
Bernoulli parameters are $3\rho_{n}/2$ on the LHS and $\rho_{n}/2$ on the RHS.
The number of terms on each side is the same, which equals

$\displaystyle N_{k,s}:=$
$\displaystyle\left(\frac{n}{2}-k\right)\left(\frac{n}{2}-k-1\right)s+k(k-1)s+4\left(\frac{n}{2}-k\right)k\left(\frac{T_{n}}{2}-s\right)+\left(\frac{n}{2}-k\right)^{2}s+k^{2}s$
$\displaystyle\gtrsim$
$\displaystyle\left(\frac{n}{2}-k\right)^{2}s+\left(\frac{n}{2}-k\right)k\left(\frac{T_{n}}{2}-s\right)$
$\displaystyle\gtrsim$ $\displaystyle n^{2}s+nT_{n}k\,.$

Let $E_{k,s}$ denote the event that $|A_{w}|=k$, $|C_{w}|=s$. Then using the
Bernstein’s inequality for the event in (32), union bound over the choice of
$A_{w}$, $B_{w}$, $C_{w}$, $D_{w}$, and the fact that $\log{n\choose m}\leq
m\log(n/m+1)$, we have, for some universal constant $c>0$

$\displaystyle\mathbb{P}(E_{k,s})\leq$ $\displaystyle{n/2\choose
k}^{2}{T_{n}/2\choose s}^{2}\exp\left[-c(n^{2}s+nT_{n}k)\rho_{n}\right]$
$\displaystyle\leq$
$\displaystyle\exp\left[-c(n^{2}s+nT_{n}k)\rho_{n}-2k\log(n/k+1)-2s\log(T_{n}/s+1)\right]\,.$

Because the function $\log(1+x)/x$ is monotone decreasing on $[1/4,\infty)$
with maximum value less than $1$, we have

$s\log(T_{n}/s+1)\leq(T_{n}/4)\log(5)\leq T_{n}/2\,.$

Thus if $k\geq\epsilon n$ for some fixed constant $\epsilon>0$, we have

$\displaystyle\mathbb{P}(E_{k,s})\leq$
$\displaystyle\exp\left[-c(n^{2}s+nT_{n}k)\rho_{n}-2k\log(1+\epsilon^{-1})-T_{n}\right]$
$\displaystyle\leq$
$\displaystyle\exp\left[-cn^{2}\rho_{n}s-(c/2)nT_{n}k\rho_{n}\right]$

whenever

$nT_{n}\rho_{n}\geq 8c^{-1}\log(1+\epsilon^{-1})\,,\quad\text{and
}n^{2}\rho_{n}\geq 4/(c\epsilon)\,.$

Then we have the error bound, for large enough $n$,

$\displaystyle P_{1,n}(\ell_{n}(\hat{\bm{\sigma}}_{\rm mle},\bm{\sigma})\geq
2\epsilon)$ $\displaystyle\leq$ $\displaystyle\sum_{k\in[\epsilon
n,n/4],s\in[0,T_{n}/4]}\exp\left[-cn^{2}\rho_{n}s-(c/2)nT_{n}k\rho_{n}\right]$
$\displaystyle=$ $\displaystyle\sum_{k=\epsilon
n}^{n/4}e^{-(c/2)nT_{n}\rho_{n}k}\sum_{s=0}^{T_{n}/4}e^{-cn^{2}\rho_{n}s}$
$\displaystyle\leq$
$\displaystyle\frac{2}{cnT_{n}\rho_{n}}\times\frac{1}{cn^{2}\rho_{n}}=o(1)\,,$

where the last inequality uses $\sum_{k=a}^{b}e^{-\beta
k}\leq\beta^{-1}\int_{a\beta}^{\infty}e^{-u}du\leq\beta^{-1}e^{-a\beta}$. ∎

## References

  * [1] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall.  Exact recovery in the stochastic block model.  IEEE Transactions on information theory, 62(1):471–487, 2015.
  * [2] Emmanuel Abbe and Colin Sandon.  Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery.  2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670–688, 2015.
  * [3] Arnab Auddy and Ming Yuan.  Large dimensional independent component analysis: Statistical optimality and computational tractability.  arXiv preprint arXiv:2303.18156, 2023.
  * [4] Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein.  Computational hardness of certifying bounds on constrained pca problems.  Innovations in Theoretical Computer Science, 2020.
  * [5] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin.  A nearly tight sum-of-squares lower bound for the planted clique problem.  SIAM Journal on Computing, 48(2):687–735, 2019.
  * [6] Quentin Berthet and Philippe Rigollet.  Optimal detection of sparse principal components in high dimension.  The Annals of Statistics, pages 1780–1815, 2013.
  * [7] Guy Bresler and Brice Huang.  The algorithmic phase transition of random k-sat for low degree polynomials.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 298–309. IEEE, 2022.
  * [8] Shuxiao Chen, Sifan Liu, and Zongming Ma.  Global and individualized community detection in inhomogeneous multilayer networks.  The Annals of Statistics, 50(5):2664–2693, 2022.
  * [9] Damek Davis, Mateo Díaz, and Kaizheng Wang.  Clustering a mixture of gaussians with unknown covariance.  arXiv preprint arXiv:2110.01602, 2021.
  * [10] Ilias Diakonikolas, Daniel M Kane, Yuetian Luo, and Anru Zhang.  Statistical and computational limits for tensor-on-tensor association detection.  In The Thirty Sixth Annual Conference on Learning Theory, pages 5260–5310. PMLR, 2023.
  * [11] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira.  The average-case time complexity of certifying the restricted isometry property.  IEEE Transactions on Information Theory, 67(11):7355–7361, 2021\.
  * [12] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira.  Subexponential-time algorithms for sparse pca.  Foundations of Computational Mathematics, pages 1–50, 2023.
  * [13] Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov.  Clustering with multi-layer graphs: A spectral perspective.  IEEE Trans. Signal Processing, 60(11):5820–5831, 2012.
  * [14] Oliver Y Feng, Ramji Venkataramanan, Cynthia Rush, Richard J Samworth, et al.  A unifying tutorial on approximate message passing.  Foundations and Trends® in Machine Learning, 15(4):335–536, 2022.
  * [15] David Gamarnik, Aukosh Jagannath, and Alexander S Wein.  Low-degree hardness of random optimization problems.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 131–140. IEEE, 2020.
  * [16] Chao Gao, Zongming Ma, Anderson Y Zhang, and Harrison H Zhou.  Achieving optimal misclassification proportion in stochastic block model.  arXiv preprint arXiv:1505.03772, 2015.
  * [17] Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, and Edoardo M Airoldi.  A survey of statistical network models.  Foundations and Trends® in Machine Learning, 2(2):129–233, 2010.
  * [18] Qiuyi Han, Kevin Xu, and Edoardo Airoldi.  Consistent estimation of dynamic and multi-layer block models.  In International Conference on Machine Learning, pages 1511–1520, 2015.
  * [19] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social networks, 5(2):109–137, 1983.
  * [20] Samuel Hopkins.  Statistical inference and the sum of squares method.  PhD thesis, Cornell University, 2018.
  * [21] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer.  The power of sum-of-squares for detecting hidden structures.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720–731. IEEE, 2017.
  * [22] Samuel B Hopkins and David Steurer.  Efficient bayesian estimation from few samples: community detection and related problems.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 379–390. IEEE, 2017.
  * [23] Alan Julian Izenman.  Network Models for Data Science.  Cambridge University Press, 2023.
  * [24] Mikko Kivelä, Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter.  Multilayer networks.  Journal of Complex Networks, 2(3):203–271, 2014.
  * [25] Eric D Kolaczyk.  Statistical analysis of network data.  Springer, 2009.
  * [26] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira.  Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio.  In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1–50. Springer, 2019.
  * [27] Lucien Le Cam.  Asymptotic methods in statistical decision theory.  Springer Science & Business Media, 2012.
  * [28] Jing Lei, Kehui Chen, and Brian Lynch.  Consistent community detection in multi-layer network data.  Biometrika, 107(1):61–73, 2020.
  * [29] Jing Lei and Kevin Z Lin.  Bias-adjusted spectral clustering in multi-layer stochastic block models.  Journal of the American Statistical Association, pages 1–13, 2022\.
  * [30] Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  The Annals of Statistics, 43(1):215–237, 2015.
  * [31] Keith Levin, Asad Lodhia, and Elizaveta Levina.  Recovering shared structure from multiple networks with unknown edge distributions.  The Journal of Machine Learning Research, 23(1):86–133, 2022.
  * [32] Fuchen Liu, David Choi, Lu Xie, and Kathryn Roeder.  Global spectral clustering in dynamic networks.  Proceedings of the National Academy of Sciences, 115(5):927–932, 2018.
  * [33] Matthias Löffler, Alexander S Wein, and Afonso S Bandeira.  Computationally efficient sparse clustering.  Information and Inference: A Journal of the IMA, 11(4):1255–1286, 2022.
  * [34] Yuetian Luo and Chao Gao.  Computational lower bounds for graphon estimation via low-degree polynomials.  arXiv preprint arXiv:2308.15728, 2023.
  * [35] Yuetian Luo and Anru R Zhang.  Tensor clustering with planted structures: Statistical optimality and computational limits.  The Annals of Statistics, 50(1):584–613, 2022.
  * [36] Zhongyuan Lyu and Dong Xia.  Optimal estimation and computational limit of low-rank gaussian mixtures.  The Annals of Statistics, 51(2):646–667, 2023.
  * [37] Zongming Ma and Yihong Wu.  Computational barriers in minimax submatrix detection.  The Annals of Statistics, pages 1089–1116, 2015.
  * [38] Cheng Mao and Alexander S Wein.  Optimal spectral recovery of a planted vector in a subspace.  arXiv preprint arXiv:2105.15081, 2021.
  * [39] Catherine Matias and Vincent Miele.  Statistical clustering of temporal networks through a dynamic stochastic block model.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(4):1119–1141, 2017.
  * [40] Mark Newman.  Networks: an introduction.  Oxford University Press, 2009.
  * [41] Subhadeep Paul and Yuguo Chen.  A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging.  Annals of Applied Statistics, 14(2), 2020.
  * [42] Subhadeep Paul and Yuguo Chen.  Spectral and matrix factorization methods for consistent community detection in multi-layer networks.  The Annals of Statistics, 48(1):230–250, 2020.
  * [43] Marianna Pensky.  Dynamic network models and graphon estimation.  The Annals of Statistics, 47(4):2378–2403, 2019.
  * [44] Prasad Raghavendra, Tselil Schramm, and David Steurer.  High dimensional estimation via sum-of-squares proofs.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3389–3423. World Scientific, 2018.
  * [45] Tselil Schramm and Alexander S Wein.  Computational barriers to estimation from low-degree polynomials.  The Annals of Statistics, 50(3):1833–1858, 2022.
  * [46] Matthew Skala.  Hypergeometric tail inequalities: ending the insanity.  arXiv preprint arXiv:1311.5939, 2013.
  * [47] Wei Tang, Zhengdong Lu, and Inderjit S Dhillon.  Clustering with multiple graphs.  In International Conference on Data Mining (ICDM), pages 1016–1021. IEEE, 2009.
  * [48] Alexandre B. Tsybakov.  Introduction to Nonparametric Estimation.  Springer, New York, 2009.
  * [49] Kevin S Xu and Alfred O Hero.  Dynamic stochastic blockmodels for time-evolving social networks.  IEEE Journal of Selected Topics in Signal Processing, 8(4):552–562, 2014.
  * [50] Anderson Y Zhang and Harrison H Zhou.  Minimax rates of community detection in stochastic block models.  The Annals of Statistics, 44(5):2252–2280, 2016.
  * [51] Anru Zhang and Dong Xia.  Tensor svd: Statistical and computational limits.  IEEE Transactions on Information Theory, 64(11):7311–7338, 2018\.
  * [52] Jingfei Zhang and Jiguo Cao.  Finding common modules in a time-varying network with application to the drosophila melanogaster gene regulation network.  Journal of the American Statistical Association, 112(519):994–1008, 2017.