tcb@breakable

# Community Detection in the Hypergraph SBM:
Optimal Recovery Given the Similarity Matrix

Julia<EMAIL_ADDRESS>Department of Industrial
Engineering and Management Sciences, Northwestern University. Nirmit
<EMAIL_ADDRESS>Department of Computer Science,
Northwestern University.

###### Abstract

Community detection is a fundamental problem in network science. In this
paper, we consider community detection in hypergraphs drawn from the
_hypergraph stochastic block model_ (HSBM), with a focus on exact community
recovery. We study the performance of polynomial-time algorithms for community
detection in a case where the full hypergraph is unknown. Instead, we are
provided a _similarity matrix_ $W$, where $W_{ij}$ reports the number of
hyperedges containing both $i$ and $j$. Under this information model, Kim,
Bandeira, and Goemans [KBG18] determined the information-theoretic threshold
for exact recovery, and proposed a semidefinite programming relaxation which
they conjectured to be optimal. In this paper, we confirm this conjecture. We
also show that a simple, highly efficient spectral algorithm is optimal,
establishing the spectral algorithm as the method of choice. Our analysis of
the spectral algorithm crucially relies on strong _entrywise_ bounds on the
eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang,
and Zhong [AFWZ20], who developed entrywise bounds for eigenvectors of
symmetric matrices with independent entries. Despite the complex dependency
structure in similarity matrices, we prove similar entrywise guarantees.

##  1 Introduction

Community detection is the problem of partitioning a network into densely
connected clusters. As a fundamental network science problem, community
detection arises in numerous applications: sociology [GZFA10, NWS02], protein
interactions [CY06, MPN+99], image applications [SM00], natural language
processing [BKN11], webpage sorting [KRRT99] and many more.

In 1983, Holland et al. [HLL83] introduced the _stochastic block model_ (SBM),
a probabilistic generative model for networks with community structure. Since
then, community detection in the SBM has been intensely studied in the
probability, statistics, and theoretical computer science communities; see
[Abb17] for a survey. The (general) SBM is specified by two types of
parameters: community sizes and edge formation probabilities. The probability
that two vertices $i,j$ are connected by an edge depends only on the community
memberships of those vertices. Research on community detection in the SBM has
focused on questions of exact, partial, and weak recovery of the communities.
These questions have been approached from both the statistical and algorithmic
perspectives, with many exciting developments over the past few decades [DF89,
McS01, DKMZ11, MNS13, Mas14, AS15a, ABH16, AS15b].

In this paper, we consider an extension of the SBM to _hypergraphs_. A
hypergraph is a generalization of a graph that is able to capture higher-order
interactions. For example, an academic co-authorship network may be modeled as
a hypergraph, where each hyperedge represents the author list of a paper.
Formally, a hypergraph is specified by a set of vertices $V$ and a set of
hyper-edges $E$. Each hyperedge $e\in E$ is a subset of $V$. We specialize to
_uniform_ hypergraphs, where each hyperedge contains the same number of
vertices. A _$d$ -uniform hypergraph_ satisfies $|e|=d$ for all $e\in E$ (in
particular, a graph is $2$-uniform hypergraph). We then say that the
hypergraph has _order_ $d$.

We now describe the Hypergraph Stochastic Block Model (HSBM), which was first
proposed by Ghoshdastidar and Dukkipati [GD14]. We consider the version with
two balanced communities, and equal inter-community edge probabilities. The
model is specified by its order $d$ and two parameters $\alpha>\beta>0$.
First, a community assignment vector $\sigma^{*}\in\\{\pm 1\\}^{n}$ is sampled
uniformly at random from the set $\\{\sigma\in\\{\pm
1\\}^{n}:\langle\mathbf{1}_{n},\sigma\rangle=0\\}$, where
$\mathbf{1}_{n}\in\mathbb{R}^{n}$ is the vector of all ones.

Conditioned on $\sigma^{*}$, we sample a hypergraph $G=([n],E)$ as follows.
Each $e=\\{i_{1},i_{2},\dots,i_{d}\\}\in\binom{[n]}{d}$ appears as a hyperedge
independently with probability

$\displaystyle\operatorname*{\mathbb{P}}\left(e\in
E\right)=\begin{cases}\nicefrac{{\alpha\log
n}}{{\binom{n-1}{d-1}}}&\sigma^{*}(i_{1})=\sigma^{*}(i_{1})=\cdots=\sigma^{*}(i_{d})\\\
\nicefrac{{\beta\log n}}{{\binom{n-1}{d-1}}}&\text{otherwise}.\end{cases}$

We then write $G\sim\text{HSBM}(d,n,\alpha,\beta)$.

We say that an estimator $\hat{\sigma}_{n}$ _achieves exact recovery_ if

$\lim_{n\to\infty}\operatorname*{\mathbb{P}}\left(\hat{\sigma}_{n}\in\\{\pm\sigma^{*}_{n}\\}\right)=1.$

For clarity of presentation, we typically drop the dependence on $n$.

The information-theoretic threshold for exact recovery in the
$\text{HSBM}(d,n,\alpha,\beta)$ model was determined by Kim, Bandeira, and
Goemans [KBG18]: if
$\frac{1}{2^{d-1}}\left(\sqrt{\alpha}-\sqrt{\beta}\right)^{2}<1$, then exact
recovery is impossible, while if
$\frac{1}{2^{d-1}}\left(\sqrt{\alpha}-\sqrt{\beta}\right)^{2}>1$, then exact
recovery is possible. The maximum-likelihood estimator, which achieves the
threshold, is equivalent to solving a min-bisection problem [KBG18]. Since
min-bisection is NP-hard, this motivated the search for polynomial-time
algorithms for the exact recovery problem [GD15a, GD15b, GD17, ALS18, CLW19],
culminating in the work of Zhang and Tan [ZT21], whose algorithm applies to a
general class of HSBMs. Their results essentially show that there is no
statistical-computational gap for the exact recovery problem (see [ZT21,
Theorem 2] for a precise statement).

While the work of Zhang and Tan [ZT21] resolves the question of efficient
exact recovery even for general HSBMs, the result assumes that the hypergraph
is fully observed. Motivated by [KBG18, LKC20], we instead consider exact
community recovery given only the _similarity matrix_ of the hypergraph.

######  Definition 1.1 (Similarity Matrix).

Let $G=([n],E)$ be a hypergraph on $n$ vertices. The similarity matrix of $G$
is the zero-diagonal matrix $W$ whose entries are

$W_{ij}=\left|\left\\{e\in E:\\{i,j\\}\subset e\right\\}\right|$

for $i\neq j$. In other words, $W_{ij}$ counts the number of edges which
contain both $i$ and $j$. We also write $W=\mathcal{S}(G)$ to define the
similarity matrix transformation.

Suppose $G\sim\textnormal{HSBM}(d,n,\alpha,\beta)$, and we observe
$W=\mathcal{S}(G)$. Given only the restricted information present in $W$, when
is it possible to recover the communities exactly? Kim et al. [KBG18, Theorem
3] determined the information-theoretic threshold for exact recovery given
$W=\mathcal{S}(G)$. Letting

$I(d,\alpha,\beta)=\max_{t\geq
0}\frac{1}{2^{d-1}}\left[\alpha\left(1-e^{-(d-1)t}\right)+\beta\sum_{r=1}^{d-1}\binom{d-1}{r}\left(1-e^{-(d-1-2r)t}\right)\right],$
(1)

exact recovery given $W$ is not possible if $I(d,\alpha,\beta)<1$. Again, the
optimal estimator corresponds to solving a min-bisection problem [KBG18].
Therefore, Kim et. al. [KBG18] additionally proposed a semidefinite
programming (SDP) relaxation, showing that it succeeds in exact recovery if
$I_{\text{SDP}}(d,\alpha,\beta)>1$, where

$I_{\text{SDP}}(d,\alpha,\beta)=\frac{(d-1)}{2^{2d}}\cdot\frac{(\alpha-\beta)^{2}}{\left(\alpha\frac{d}{2^{d}}+\beta\left(1-\frac{d}{2^{d}}\right)\right)}.$

Note that $I_{\text{SDP}}(d,\alpha,\beta)>I(d,\alpha,\beta)$ for $d\geq 3$;
see Figure 1 for an illustration. The authors conjectured that the SDP
algorithm is optimal; i.e. it succeeds whenever $I(d,\alpha,\beta)>1$ [KBG18,
Conjecture 1.2]. Our first main contribution is to confirm this conjecture. We
note that there has been some follow-up work on community recovery from the
similarity matrix [LKC20, CZ20], but to our knowledge we are the first to
resolve [KBG18, Conjecture 1.2].

Figure 1: Visualization of $I(d,\alpha,\beta)=1$ and
$I_{\textnormal{SDP}}(d,\alpha,\beta)=1$ when $d=6$.

A natural question emerges: if the SDP algorithm is optimal, are other
efficient algorithms optimal as well? Given that spectral algorithms are more
efficient than SDPs, and motivated by the success of simple spectral
algorithms for other community detection problems [AFWZ20, SWZ19, DLS21,
DGMS22a, DGMS22b, DGMS22c], we ask:

_Do spectral algorithms achieve the information-theoretic threshold for exact
recovery from a similarity matrix?_

In this direction, our second main contribution is a spectral algorithm which
achieves the information-theoretic threshold. Moreover, our algorithm does not
require any clean-up phase. In order to analyze our spectral algorithm,
inspired by the work of [AFWZ20], we develop $\ell_{\infty}$ (entrywise)
bounds for the eigenvectors of similarity matrices of a large class of random
hypergraph models, which may be of independent interest. Roughly speaking, we
show that an eigenvector $u_{k}$ of a random similarity matrix $W$ is close to
its first order approximation $Wu_{k}^{*}/\lambda_{k}^{*}$ in the
$\ell_{\infty}$ norm under mild conditions, where
$(\lambda_{k}^{*},u_{k}^{*}$) is the corresponding eigenpair of
$\operatorname*{{\mathbb{E}}}{[W]}$.

#### Notation.

For any real numbers $a,b\in R$, we denote $a\vee b=\max\\{a,b\\}$ and
$a\wedge b=\min\\{a,b\\}$. Let $\textnormal{sgn}:\mathbb{R}\to\\{\pm 1\\}$ be
the function defined by $\textnormal{sgn}(x)=1$ if $x\geq 0$ and
$\textnormal{sgn}(x)=-1$ if $x<0$. We also extend the definition to vectors;
let $\textnormal{sgn}:\mathbb{R}^{n}\to\\{\pm 1\\}^{n}$ be the map defined by
applying the sign function componentwise.

We use the notation $\mathbb{R}_{+}=(0,\infty)$. For $n\in\mathbb{N}$, we
write $[n]=\\{1,2,\dots,n\\}$.We use the Bachmann–Landau notation $o(.)$,
$O(.)$, $\omega(.)$, $\Omega(.)$, $\Theta(.)$ etc. throughout the paper. For
nonnegative sequences $(a_{n})_{n\geq 1}$ and $(b_{n})_{n\geq 1}$, we write
$a_{n}\lesssim b_{n}$ to mean $a_{n}\leq Cb_{n}$ for some constant $C>0$. The
notation $\asymp$ is similar, hiding two constants in upper and lower bounds.
Moreover, we write $a_{n}\approx b_{n}$ as a shorthand for
$\lim_{n\rightarrow\infty}\frac{a_{n}}{b_{n}}=1$.

For any two vectors $x,y\in\mathbb{R}^{n}$, $\langle x,y\rangle$ represents a
standard inner product in $\mathbb{R}^{n}$; we define $\left\lVert
x\right\rVert_{2}=(\sum_{i=1}^{n}x_{i}^{2})^{1/2}$,
$\|x\|_{1}=\sum_{i=1}^{n}|x_{i}|$, and $\left\lVert
x\right\rVert_{\infty}=\max_{i}|x_{i}|$. For any matrix
$M\in\mathbb{R}^{n\times n}$, $M_{i\cdot}$ refers to its $i$-th row, which is
a row vector, and $M_{\cdot i}$ refers to its $i$-th column, which is a column
vector. The matrix spectral norm is $\left\lVert
M\right\rVert_{2}=\sup_{\left\lVert x\right\rVert_{2}=1}\left\lVert
Mx\right\rVert_{2}$, the matrix $2\rightarrow\infty$ norm is $\left\lVert
M\right\rVert_{2\rightarrow\infty}=\sup_{\left\lVert
x\right\rVert_{2}=1}\left\lVert Mx\right\rVert_{\infty}=\sup_{i}\left\lVert
M_{i\cdot}\right\rVert_{2}$, and the the matrix Frobenius norm is $\left\lVert
M\right\rVert_{F}=(\sum_{i=1}^{n}\sum_{j=1}^{n}M_{ij}^{2})^{1/2}$.

#### Organization.

Section 2 contains our main results along with their proof outlines, as well
as a discussion of future work. We show the optimality of the SDP relaxation
in Section 3. Finally, in Section 4, we present the analysis of the spectral
algorithm and the entrywise bounds on the eigenvectors of similarity matrices.

##  2 Models and results

###  2.1 Models

Recall the definition of $\textnormal{HSBM}(d,n,\alpha,\beta)$. We
additionally define a general model of random hypergraphs with independent
edges.

######  Definition 2.1 (General random hypergraph).

Let $d\in\\{2,3,\dots\\}$, $n\in\mathbb{N}$, and $p\in[0,1]^{\binom{[n]}{d}}$.
Define $H(d,n,p)$ to be the distribution on $d$-uniform hypergraphs with $n$
vertices, where each edge $e\in\binom{[n]}{d}$ appears in the hypergraph with
probability $p_{e}$, independently.

###  2.2 Results

Recall that $\sigma^{*}_{n}\in\\{\pm 1\\}^{n}$ denotes the true community
assignment vector. Let $G$ be a hypergraph on $n$ vertices, and let
$W=\mathcal{S}(G)$ be its similarity matrix. Kim, Bandeira, and Goemans
[KBG18] proposed the following SDP recovery algorithm.

Algorithm 1 SDP recovery algorithm [KBG18]

1:An $n\times n$ similarity matrix $W$

2:An estimate of community assignments

3:Solve the following SDP, where $X\in\mathbb{R}^{n\times n}$.
$\displaystyle\max{}$ $\displaystyle\langle W,X\rangle$ (2) subject to
$\displaystyle X_{ii}=1\text{ for all }i\in[n]$ $\displaystyle\langle
X,\mathbf{11}^{\top}\rangle=0$ $\displaystyle X\succeq 0.$

4:Let $X^{*}$ be the optimal solution, and let
$X^{*}=\sum_{i=1}^{n}\lambda_{i}v_{i}v_{i}^{\top}$ denote the
eigendecomposition of $X^{*}$, where
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$.

5:Return $\hat{\sigma}_{\text{SDP}}=\textnormal{sgn}(v_{1})$.

Our first main result states that the SDP relaxation achieves exact recovery
down to the information-theoretic threshold.

######  Theorem 1.

Fix $d\in\\{2,3,\dots\\}$ and $\alpha>\beta>0$ such that
$I(d,\alpha,\beta)>1$. Suppose $G\sim\textnormal{HSBM}(d,n,\alpha,\beta)$, and
let $W=\mathcal{S}(G)$. Let $X^{*}$ be the optimal solution to (2) with input
$W$. Then $X^{*}=\sigma^{*}{\sigma^{*}}^{\top}$ with probability $1-o(1)$. It
follows that the estimator $\hat{\sigma}_{\textnormal{\tiny{SDP}}}$ returned
by Algorithm 2.2 achieves exact recovery.

We also establish that the SDP continues to achieve exact recovery even under
a _monotone adversary_ model (Lemma 3.3).

Having shown optimality of the SDP relaxation, we propose a spectral algorithm
and establish its optimality.

Algorithm 2 Spectral recovery algorithm

1:An $n\times n$ similarity matrix $W$

2:An estimate of community assignments

3:Compute the eigenpairs of $W$, denoted by $(\lambda_{i},u_{i})_{i=1}^{n}$,
where $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$.

4:Return $\hat{\sigma}_{\text{spec}}=\textnormal{sgn}(u_{2})$.

######  Theorem 2.

Fix $d\in\\{2,3,\dots\\}$ and $\alpha>\beta>0$ such that
$I(d,\alpha,\beta)>1$. Suppose $G\sim\textnormal{HSBM}(d,n,\alpha,\beta)$, and
let $W=\mathcal{S}(G)$. Let $u_{2}$ be the second eigenvector of $W$. Then
with probability $1-o(1)$, there exist $s\in\\{\pm 1\\}$ and
$\eta=\eta(d,\alpha,\beta)>0$ such that

$\sqrt{n}\min_{i\in[n]}s\sigma^{*}(i)u_{2,i}>\eta.$

As a result, the estimator $\hat{\sigma}_{\textnormal{\tiny{spec}}}$ produced
by Algorithm 2.2 on input $W$ achieves exact recovery.

Our proof of Theorem 2 crucially relies on _entrywise_ bounds on the second
eigenvector of the similarity matrix. To this end, we develop entrywise bounds
on the eigenvectors of similarity matrices of general random hypergraphs
(Definition 2.1), in the logarithmic degree regime. Specifically, we consider
$W=\mathcal{S}(G)$, where $G\sim H(d,n,p)$. Let
$(\lambda_{i},u_{i})_{i=1}^{n}$ denote the eigenpairs of $W$, where
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. Let
$W^{*}=\mathbb{E}[W]$, with ordered eigenpairs
$(\lambda_{i}^{*},u_{i}^{*})_{i=1}^{n}$. We use the convention
$\lambda_{0}=\lambda_{0}^{*}=\infty$ and
$\lambda_{n+1}=\lambda_{n+1}^{*}=-\infty$. We then define the following
eigengap quantity:

$\Delta_{k}^{*}=\min\\{\lambda_{k-1}^{*}-\lambda_{k}^{*},\lambda_{k}^{*}-\lambda_{k+1}^{*}\\}.$

Our entrywise guarantee requires a spectral separation assumption. The
assumption easily holds for similarity matrices of (general) HSBMs, in the
logarithmic degree regime.

######  A 1 (Spectral separation).

There is a constant $c_{1}>0$ such that $\frac{1}{c_{1}}\log
n\leq|\lambda_{k}^{*}|,|\Delta_{k}^{*}|\leq c_{1}\log n$.

Under this assumption, we state our entrywise guarantee.

######  Theorem 3.

Let $k\in\mathbb{N}$ and $d\in\\{2,3,\dots\\}$ be constants. Let
$p\in[0,1]^{\binom{[n]}{d}}$, where $\max_{e}p_{e}\leq\frac{c_{0}\log
n}{\binom{n-1}{d-1}}$. Let $G\sim H(d,n,p)$, and $W=\mathcal{S}(G)$. Suppose
that 1 holds with constant $c_{1}>0$. Then with probability $1-O(n^{-3})$,

$\min_{s^{*}\in\\{\pm 1\\}}\left\lVert
u_{k}-s^{*}\frac{W{u_{k}^{*}}}{\lambda_{k}^{*}}\right\rVert_{\infty}\leq\hskip
5.69054pt\frac{c\left\lVert u_{k}^{*}\right\rVert_{\infty}}{\log\log n},$

where $c>0$ is some constant depending only on $d,c_{0},$ and $c_{1}$.

###  2.3 Proof ideas

#### Showing optimality of the SDP.

We use a dual certificate strategy as in [KBG18]. The dual of (2) is given by

$\displaystyle\min{}$ $\displaystyle\text{trace}(D)$ (3) subject to
$\displaystyle D\text{ is }n\times n\text{ diagonal matrix,
}\nu\in\mathbb{R},$ $\displaystyle D+\nu\mathbf{11}^{\top}-W\succeq 0.$

The form of the dual motivates the following sufficient condition, whose proof
we include for completeness (see Appendix A).

######  Lemma 2.2.

Suppose there is a diagonal matrix $D\in\mathbb{R}^{n\times n}$ and
$\nu\in\mathbb{R}$ such that the following holds. Letting $S\triangleq
D+\nu\mathbf{11}^{\top}-W$, the matrix $S$ is positive semidefinite, its
second-smallest eigenvalue $\lambda_{n-1}(S)$ is strictly positive, and
$S\sigma^{*}=0$. Then $X^{*}=\sigma^{*}{\sigma^{*}}^{\top}$ is the unique
optimal solution to (2).

To apply Lemma 2.2, we let $D$ be the diagonal matrix whose diagonal entries
are specified by

$D_{ii}=\sum_{j\in[n]}W_{ij}\sigma^{*}(i)\sigma^{*}(j).$ (4)

Setting $\nu=1$, write $S=D+\mathbf{11}^{\top}-W$. By construction, we have
$S\sigma^{*}=0$. It remains to show

$\mathbb{P}\left(\inf_{x\perp\sigma^{*}:\|x\|_{2}=1}x^{\top}Sx>0\right)=1-o(1).$
(5)

This is where our proof diverges from [KBG18]; rather than showing (5),
[KBG18] proceeds through a different sufficient condition. Using steps similar
to the proof of [HWX16a, Theorem 2], we show that for all $x\perp\sigma^{*}$
such that $\|x\|_{2}=1$,

$x^{\top}Sx\geq\min_{i\in[n]}D_{ii}-\|W-W^{*}\|_{2},$ (6)

where $W^{*}$ is the expected value of $W$, conditioned on $\sigma^{*}$. It
remains to (1) lower-bound $D_{ii}$ for each $i\in[n]$ and (2) upper-bound
$\|W-W^{*}\|_{2}$.

To lower-bound $D_{ii}$, we condition on $\sigma^{*}$ and establish
concentration of $D_{ii}$ around its mean. To see why $D_{ii}$ should be
positive and bounded away from zero, it helps to rewrite (4) as follows:

$D_{ii}=\sum_{j\in[n]:\sigma^{*}(i)=\sigma^{*}(j)}W_{ij}-\sum_{j\in[n]:\sigma^{*}(i)\neq\sigma^{*}(j)}W_{ij}.$

While the values $\\{W_{ij}\\}_{j=1}^{n}$ are dependent, they are functions of
_independent_ random variables (namely, the hyperedge random variables). After
re-expressing $D_{ii}$ in terms of the underlying hyperedge random variables,
the proof proceeds by a Chernoff-style argument (Lemma 3.2). Whenever
$I(d,\alpha,\beta)>1$, we establish the existence of $\epsilon>0$ such that
for each $i$, $D_{ii}\geq\epsilon\log n$ with probability $1-o(n^{-1})$. A
union bound then implies $\min_{i\in[n]}D_{ii}\geq\epsilon\log n$ with high
probability.

To bound $\|W-W^{*}\|_{2}$, we directly apply the sharp result of Lee, Kim,
and Chung [LKC20, Theorem 4, Corollary 2], which shows that
$\|W-W^{*}\|_{2}=O\left(\sqrt{\log n}\right)$ with high probability.
Interestingly, we found a simple bound on the _expected_ spectral norm,
showing that $\mathbb{E}\left[\|W-W^{*}\|_{2}\right]=O\left(\sqrt{\log
n}\right)$. Markov’s inequality then implies a looser version of [LKC20,
Theorem 4, Corollary 2] (see Theorem 4 in Appendix B). Returning to (6), we
see that $x^{\top}Sx>0$ simultaneously for all $x$ satisfying
$x\perp\sigma^{*},\|x\|_{2}=1$, with high probability.

#### Analyzing the spectral algorithm.

Recall that $u_{2}$ denotes the second eigenvector of $W=\mathcal{S}(G)$.
Since our algorithm determines communities based on the signs of $u_{2}$, we
need precise bounds on each entry of $u_{2}$. A natural strategy would be to
compare $u_{2}$ to $u_{2}^{*}$, since
$u_{2}^{*}=\frac{1}{\sqrt{n}}\sigma^{*}$. Unfortunately,
$\|u_{2}-u_{2}^{*}\|_{\infty}$ is too large for our purposes, but still
$u_{2}$ recovers communities by sign. To gain some intuition for this
behavior, write

$u_{2}-u_{2}^{*}=\left(\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}-u_{2}^{*}\right)+\left(u_{2}-\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}\right).$

Figure 2: Consider $\textnormal{HSBM}(d,n,\alpha,\beta)$ for
$d=4,n=1000,\alpha=50,\beta=10$. The boxplots show three different errors over
100 realizations: (1)$\sqrt{n}\left\lVert
u_{2}-u_{2}^{*}\right\rVert_{\infty}$,
(2)$\sqrt{n}\|u_{2}^{*}-Wu_{2}^{*}/\lambda_{2}^{*}\|_{\infty}$, and (3)
$\sqrt{n}\|u_{2}-Wu_{2}^{*}/\lambda_{2}^{*}\|_{\infty}$.

We can think of the first term on the right hand side as the main term, while
the second represents a smaller-order term (see Figure 2). Such behavior was
also observed in the SBM setting [AFWZ20].

Our first step is to apply Theorem 3, showing that

$\min_{s^{*}\in\\{\pm
1\\}}\left\|u_{2}-s^{*}\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}\right\|_{\infty}=o(1/\sqrt{n})$
(7)

(see Corollary 4.1). Therefore, if we can show that the vector
$\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}$ has the same signs as $\sigma^{*}$ (up to
a global sign flip), then the same is true for $u_{2}$. Our goal is to show
that $\sigma^{*}$ and $Wu_{2}^{*}/\lambda_{2}^{*}$ have the same signs, i.e.

$\min_{i\in[n]}\sigma^{*}(i)\left(\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}\right)_{i}>0.$

Fixing the orientation $u_{2}^{*}=\frac{1}{\sqrt{n}}\sigma^{*}$, we obtain
that for $i\in[n]$,

$\sigma^{*}(i)\left(\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}\right)_{i}=\frac{\sigma^{*}(i)\sum_{j\in[n]}W_{ij}\sigma^{*}(j)}{\lambda_{2}^{*}\sqrt{n}}=\frac{D_{ii}}{\lambda_{2}^{*}\sqrt{n}},$

where $D_{ii}$ is defined in (4). As in the SDP analysis, we note that for
$\epsilon>0$ sufficiently small, $\min_{i\in[n]}D_{ii}\geq\epsilon\log n$ with
high probability, whenever $I(d,\alpha,\beta)>1$. Therefore, the vector
$\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}$ has the same signs as $\sigma^{*}$.
Moreover, the entries are of order $1/\sqrt{n}$; in turn, (7) implies that
$u_{2}$ also has the same signs as $\sigma^{*}$, up to a global sign flip.

#### Entrwise eigenvector analysis.

Abbe, Fan, Wang, and Zhong [AFWZ20] introduced a powerful entrywise
eigenvector bound, which has been used to show optimality of spectral
algorithms without the need of a clean-up stage [AFWZ20, DGMS22a, DGMS22b,
DGMS22c]. Unfortunately, the entrywise bound [AFWZ20, Theorem 2.1] does not
apply to $W=\mathcal{S}(G)$, since $W$ violates a certain independence
assumption. The independence assumption is critically used in a _leave-one-
out_ argument; we therefore carefully adapt this step. It also remains to
verify a certain _row concentration_ property of the matrix $W$.

For simplicity, let $\lambda=\lambda_{k}$, $\lambda^{*}=\lambda^{*}_{k}$ and
$\Delta_{k}^{*}=\Delta^{*}$. For clarity of presentation, we assume the
orientation $\langle u,u^{*}\rangle\geq 0$, and make similar simplifying
assumptions throughout the outline. Our goal is then to show

$\left\lVert u-\frac{W{u^{*}}}{\lambda^{*}}\right\rVert_{\infty}\lesssim\hskip
5.69054pt\frac{\left\lVert u^{*}\right\rVert_{\infty}}{\log\log n}.$

We first relate $\lambda$ to $\lambda^{*}$. By Weyl’s inequality,
$|\lambda-\lambda^{*}|\leq\|W-W^{*}\|_{2}$. [LKC20, Theorem 4] implies
$\|W-W^{*}\|_{2}\leq\gamma\lambda^{*}$ with high probability, for certain
$\gamma=\gamma_{n}=o(1)$. It then follows that
$|\lambda^{-1}-{\lambda^{*}}^{-1}|\lesssim\gamma|\lambda^{*}|^{-1}$. Using
this observation along with the triangle inequality, we can show

$\displaystyle\left\lVert u-\frac{Wu^{*}}{\lambda^{*}}\right\rVert_{\infty}$
$\displaystyle=\left\lVert\frac{Wu}{\lambda}-\frac{Wu^{*}}{\lambda}+\frac{Wu^{*}}{\lambda}-\frac{Wu^{*}}{\lambda^{*}}\right\rVert_{\infty}$
$\displaystyle\leq\left|\frac{1}{\lambda}-\frac{1}{\lambda^{*}}\right|\left\lVert
Wu^{*}\right\rVert_{\infty}+\frac{1}{|\lambda|}\left\lVert
W(u-u^{*})\right\rVert_{\infty}$
$\displaystyle\lesssim\frac{1}{|\lambda^{*}|}\left(\gamma\left\lVert
Wu^{*}\right\rVert_{\infty}+\left\lVert
W(u-u^{*})\right\rVert_{\infty}\right).$ (8)

Note that $u^{*}$ is a deterministic vector. Therefore, in order to bound the
term $\|Wu^{*}\|_{\infty}$, we derive a row concentration result (Lemma 4.4).
For a fixed vector $v\in\mathbb{R}^{n}$, our row concentration result controls
$\|Wv\|_{\infty}$ in terms of both $\|v\|_{\infty}$ and $\|v\|_{2}$.

Since $u$ depends on $W$, the second term in (8) requires a different strategy
than the first. We therefore apply the leave-one-out technique, motivated by
other works using a similar strategy [BBKY13, JMRT16, ZB18, AFWZ20]. Bounding
$\|W(u-u^{*})\|_{\infty}$ reduces to bounding
$\left|\left[W(u-u^{*})\right]_{m}\right|$ for each $m\in[n]$. To this end, we
fix $m\in[n]$ and define a random matrix $W^{(m)}$ which is independent of the
$m$-th rows and columns of $W$. Let $G^{(m)}$ be the hypergraph formed from
$G$ by deleting all hyperedges containing $m$, and let
$W^{(m)}=\mathcal{S}(G^{(m)})$ be its similarity matrix. Let $u^{(m)}$ be the
$k$-th eigenvector of $W^{(m)}$. Applying the triangle and Cauchy–Schwarz
inequalities, we obtain

$\displaystyle\left|\left[W(u-u^{*})\right]_{m}\right|$
$\displaystyle\leq\left|W_{m\cdot}(u-u^{(m)})\right|+\left|W_{m\cdot}(u^{(m)}-u^{*})\right|$
$\displaystyle\leq\left\lVert
W\right\rVert_{2\rightarrow\infty}\|u-u^{(m)}\|_{2}+|W_{m\cdot}(u^{(m)}-u^{*})|.$
(9)

Observe that $W_{m\cdot}$ and $u^{(m)}-u^{*}$ are independent by the leave-
one-out construction. Therefore, we can bound the second term in (9) using our
row concentration result. In order to bound $\|u-u^{(m)}\|_{2}$, we apply a
version of the Davis–Kahan $\sin(\theta)$ theorem [DK70], which yields

$\|u-u^{(m)}\|_{2}\lesssim\frac{\|(W-W^{(m)})u\|_{2}}{\Delta^{*}}.$

Our analysis so far is almost identical to that of [AFWZ20]; the main
difference arises here. Note that the $m$-th row and column $W-W^{(m)}$ are
the same as those of $W$. Since a hyperedge containing the vertex $m$
contributes to other entries of $W$, there will be additional non-zero entries
outside of the $m$-th row and column. This complication arises whenever $d\geq
3$, and is absent from the analysis of [AFWZ20], due to their independence
assumption. Still, we are able to prove a similar probabilistic bound on
$\left\lVert(W-W^{(m)})u\right\rVert_{2}$, using structural properties of
similarity matrices.

###  2.4 Discussion and future work

This paper contributes to a line of work which studies random graph inference
problems under restricted information. This paper considers _aggregated_
information through the similarity matrix transformation. Other recent works
consider _noisy_ or _censored_ [ABBS14, HWX16b, DGMS22a, DGMS22b, DGMS22c]
information models.

Our work shows that the spectral algorithm recovers communities from the
similarity matrix whenever the MLE does. Abbe et. al. [AFWZ20], who observed
the same phenomenon both in community detection and in the
$\mathbb{Z}_{2}$-synchronization problem, noted that such a phenomenon may be
more general. Indeed, our result adds to a growing list of examples where a
spectral algorithm matches the MLE [AFWZ20, DLS21, DGMS22a, DGMS22b, DGMS22c].
All of these results crucially rely on entrywise eigenvector bounds. Finally,
we note that a sharp phase transition occurs at $I(d,\alpha,\beta)=1$,
reiterating a common theme in community detection problems. In particular, the
spectral algorithm succeeds with high probability if $I(d,\alpha,\beta)>1$,
while any algorithm fails with high probability if $I(d,\alpha,\beta)<~{}1$.

Future directions include:

  1. 1.

Another widely studied problem in community detection is the Planted Dense
Subgraph (PDS) model[HWX16a, DGMS22b]. Consider its natural hypergraph
extension, where there is one dense community to be recovered of size
${\left\lfloor{\rho n}\right\rfloor}$ for a fixed $\rho\in(0,1)$. Intra-
community edges exist independently with probability $\alpha\log
n/\binom{n-1}{d-1}$ and other edges exist with probability $\beta\log
n/\binom{n-1}{d-1}$ for fixed constants $\alpha>\beta>0$. It can be verified
that 1 holds for $k\in[2]$, hence the the entrywise guarantees of eigenvectors
(Theorem 3) apply. Due to the non-symmetric nature of the problem, a single
eigenvector may not be an optimal estimator. However, we believe that some
linear combination of the two leading eigenvectors of the similarity matrix
would lead to an optimal spectral algorithm.

  2. 2.

We show that the SDP is robust to a monotone adversary who operates on the
similarity matrix. What can we say about an adversary who instead operates on
the hypergraph directly, by adding intra-community edges and removing inter-
community edges?

  3. 3.

[DLS21, Theorem 4] provides a sharp bound on $\|W-W^{*}\|_{2}$. Their proof is
similar in spirit to the combinatorial proof of Feige and Ofek [FO05], who
consider a symmetric matrix with independent entries. On the other hand, a
simpler proof is known in this setting [HWX16a], and is based on a
symmetrization trick. Using the symmetrization strategy, we were able to show
that $\mathbb{E}\left[\|W-W^{*}\|_{2}\right]=O\left(\sqrt{\log n}\right)$. Can
we then argue about $\|W-W^{*}\|_{2}$ through concentration?

##  3 Optimality of the SDP relaxation

For completeness, we include the proof of Lemma 2.2, which establishes the
uniqueness of the optimal solution $X^{*}=\sigma^{*}{\sigma^{*}}^{\top}$ by a
dual certificate strategy (see Appendix A). Here we focus on showing that the
choice of $D$ mentioned in (4) and $\nu=1$ satisfy the conditions in Lemma 2.2
with high probability whenever $I(d,\alpha,\beta)>1$ to show the theorem. We
begin by noting a spectral norm concentration result of Lee, Kim, and Chung
for general random hypergraphs [LKC20].

######  Lemma 3.1 (Theorem 4, [LKC20]).

Fix $d\in\\{2,3,\dots\\}$. Let $p\in[0,1]^{\binom{[n]}{d}}$, where
$\max_{e}p_{e}\leq\frac{c_{0}\log n}{\binom{n-1}{d-1}}$. Let $G\sim H(d,n,p)$,
and $W=\mathcal{S}(G)$. Let
$W^{*}\triangleq\operatorname*{{\mathbb{E}}}{[W]}$. Then there exists a
constant $C=C(d,c_{0})>0$ such that

$\operatorname*{\mathbb{P}}\left(\left\lVert W-W^{*}\right\rVert_{2}\leq
C\sqrt{\log n}\right)\geq 1-O(n^{-11}).$

Since hyperedges in the HSBM model appear with probability at most $\alpha\log
n/\binom{n-1}{d-1}$, Lemma 3.1 applies to $W=\mathcal{S}(G)$, where
$G\sim\textnormal{HSBM}(d,n,\alpha,\beta)$. We now prove a lemma that plays an
important role in proving the theorem. Roughly speaking, it provides a
probabilistic lower bound on $D_{ii}$ defined in (4) for any $i\in[n]$.

######  Lemma 3.2.

Let $d\in\\{2,3,\dots\\}$, and $\alpha>\beta>0$, such that
$I(d,\alpha,\beta)>1$. Then there exists a constant
$\epsilon:=\epsilon(d,\alpha,\beta)>0$ such that for any fixed $i\in[n]$, with
probability at least $1-o(n^{-1})$,

$\sum_{j\in[n]}W_{ij}\sigma^{*}(i)\sigma^{*}(j)\geq\epsilon\log n.$

###### Proof.

Fix $i\in[n]$, and let
$X\triangleq\sum_{j\in[n]}W_{ij}\sigma^{*}(i)\sigma^{*}(j)$. Let
$\mathcal{E}\coloneqq\binom{[n]}{d}$ be the set of possible edges. For each
$e\in\mathcal{E}$, let $A_{e}$ be the indicator that edge $e$ is present. Let
$\mathcal{E}^{(i)}:=\\{e\in\mathcal{E}:i\in e\\}$ represent the set of
potential edges incident on $i$.

For any edge $e\in\mathcal{E}^{(i)}$, let
$n_{i}(e):=|\\{j\in[n]\setminus\\{i\\}:\sigma^{*}(i)=\sigma^{*}(j)\\}|$ be the
number of vertices in $e$ that belong to the opposite community as $i$. We can
rewrite $X$ as follows

$\displaystyle X$ $\displaystyle=\sum_{e\in\mathcal{E}^{(i)}}\sum_{j\in
e,j\neq i}\sigma^{*}(i)\sigma^{*}(j)A_{e}$
$\displaystyle=\sum_{e\in\mathcal{E}^{(i)}}\left((d-1-n_{i}(e))-n_{i}(e)\right)A_{e}$
$\displaystyle=\sum_{e\in\mathcal{E}^{(i)}}\left(d-1-2n_{i}(e)\right)A_{e}$

Next, observe that for $r\in\\{0,1,\dots,d-1\\}$, the set
$\\{e\in\mathcal{E}^{(i)}:n_{i}(e)=r\\}$ has cardinality

$N_{r}:=\binom{n/2}{r}\binom{n/2-1}{d-1-r}.$

Let $\\{Y_{r}\\}_{r=0}^{d-1}$ be independent random variables, where
$Y_{r}\sim\text{Bin}(N_{r},q_{r})$, with

$q_{r}=\begin{cases}\nicefrac{{\alpha\log n}}{{\binom{n-1}{d-1}}},&\text{if
}r=0;\\\ \nicefrac{{\beta\log n}}{{\binom{n-1}{d-1}}},&\text{if }1\leq r\leq
d-1.\end{cases}$

We then further rewrite $X$ as follows:

$\displaystyle X$
$\displaystyle=\sum_{r=0}^{d-1}\sum_{e\in\mathcal{E}^{(i)}}\mathbbm{1}\\{n_{i}(e)=r\\}\left(d-1-2n_{i}(e)\right)A_{e},$

so that $X$ is equal to $\sum_{r=0}^{d-1}(d-1-2r)Y_{r}$ in distribution.

Let $h_{r}=d-1-2r$. Fix $\epsilon\in\mathbb{R}$ and $t\geq 0$. Exponentiating
and applying the Markov inequality,

$\displaystyle\operatorname*{\mathbb{P}}\left(X\leq\epsilon\log n\right)$
$\displaystyle\leq\operatorname*{\mathbb{P}}\left(e^{-tX}\geq
e^{-t\epsilon\log n}\right)$
$\displaystyle\leq\frac{\operatorname*{{\mathbb{E}}}{[e^{-tX}]}}{e^{-t\epsilon\log
n}}$ $\displaystyle=e^{t\epsilon\log
n}\operatorname*{{\mathbb{E}}}{[e^{-t\sum_{r=0}^{d-1}h_{r}Y_{r}}]}$
$\displaystyle=e^{t\epsilon\log
n}\prod_{r=0}^{d-1}\operatorname*{{\mathbb{E}}}{[e^{-th_{r}Y_{r}}]}$
$\displaystyle=e^{t\epsilon\log
n}\prod_{r=0}^{d-1}\left(1-q_{r}(1-e^{-th_{r}})\right)^{N_{r}}$
$\displaystyle\leq\text{exp}\left(t\epsilon\log
n-\sum_{r=0}^{d-1}N_{r}q_{r}(1-e^{-h_{r}t})\right).$ (10)

Here, the second equality is due to independence of the $Y_{r}$ random
variables, and the final step uses $1-x\leq e^{-x}$. Next,

$\displaystyle N_{r}$
$\displaystyle=\binom{n/2}{r}\binom{n/2-1}{d-1-r}=\frac{\binom{n/2}{r}\binom{n/2-1}{d-1-r}}{\binom{n-1}{d-1}}\binom{n-1}{d-1}$
$\displaystyle=(1+o(1))\frac{(n/2)^{r}}{(r)\,!}\cdot\frac{(n/2)^{d-1-r}}{(d-1-r)\,!}\cdot\frac{(d-1)!}{n^{d-1}}\cdot\binom{n-1}{d-1}$
$\displaystyle=(1+o(1))\frac{1}{2^{d-1}}\binom{d-1}{r}\binom{n-1}{d-1}.$

Substituting into (10), we obtain

$\displaystyle\mathbb{P}\left(X\leq\epsilon\log n\right)$
$\displaystyle\leq\exp\left(t\epsilon\log
n-\frac{(1+o(1))}{2^{d-1}}\bigg{(}\alpha(1-e^{-(d-1)t})+\sum_{r=1}^{d-1}\beta\binom{d-1}{r}(1-e^{-(d-1-2r)t})\bigg{)}\log
n\right).$

Let $t=t^{*}(d,\alpha,\beta)$, where

$t^{*}(d,\alpha,\beta)=\arg\max_{t\geq 0}\hskip
5.69054pt\frac{1}{2^{d-1}}\left(\alpha(1-e^{-(d-1)t})+\sum_{r=1}^{d-1}\beta\binom{d-1}{r}(1-e^{-(d-1-2r)t})\right):=\arg\max_{t\geq
0}\psi(t).$

We then obtain

$\displaystyle\operatorname*{\mathbb{P}}\left(X\leq\epsilon\log n\right)$
$\displaystyle\leq\text{exp}\big{(}t^{*}\epsilon\log n-I(d,\alpha,\beta)\log
n-o(\log n)\big{)}$ $\displaystyle\leq
n^{-I(d,\alpha,\beta)+t^{*}\epsilon+o(1)}.$

Note that $t^{*}\neq 0$ as $\lim_{t\rightarrow
0^{+}}\psi^{\prime}(t)=\frac{1}{2^{d-1}}\left(\alpha(d-1)+\beta\sum_{r=1}^{d-1}\binom{d-1}{r}(d-1-2r)\right)$
$=(\alpha-\beta)(d-1)/2^{d-1}>0$. Furthermore, since $I(d,\alpha,\beta)>1$,
one can choose $\epsilon=\epsilon(d,\alpha,\beta)>0$ sufficiently small such
that

$\operatorname*{\mathbb{P}}\left(\sum_{j\in[n]}W_{ij}\sigma^{*}(i)\sigma^{*}(j)\leq\epsilon\log
n\right)=o(n^{-1}).\nobreak\hskip 0.0pt\hskip 15.00002pt minus
5.0pt\nobreak\vrule height=7.5pt,width=5.0pt,depth=2.5pt_{\textnormal{~{}}}$

Finally, we make some important observations about the structure of $W^{*}$.
Observe that $W^{*}$ has a _block_ structure (up to the diagonal entries). In
particular, $W^{*}$ is a zero diagonal symmetric matrix whose non-diagonal
entries are given by

$W^{*}_{ij}=\begin{cases}p^{\prime}\triangleq\binom{n/2-2}{d-2}\frac{\alpha\log
n}{\binom{n-1}{d-1}}+\left(\binom{n-2}{d-2}-\binom{n/2-2}{d-2}\right)\frac{\beta\log
n}{\binom{n-1}{d-1}},&\text{if }\sigma^{*}(i)=\sigma^{*}(j);\\\
q^{\prime}\triangleq\binom{n-2}{d-2}\frac{\beta\log
n}{\binom{n-1}{d-1}},&\text{if }\sigma^{*}(i)\neq\sigma^{*}(j).\end{cases}$
(11)

Observe that $W^{*}$ can be decomposed as

$W^{*}=\left(\frac{p^{\prime}+q^{\prime}}{2}\right)\mathbf{11}^{\top}+\left(\frac{p^{\prime}-q^{\prime}}{2}\right)\sigma^{*}{\sigma^{*}}^{\top}-p^{\prime}\mathbf{I}.$
(12)

###### Proof of Theorem 1.

The proof uses ideas from the proof of [HWX16a, Theorem 2]. Let $\nu=1$ and
$S\triangleq D+\nu\mathbf{11}^{\top}-W=D+\mathbf{11}^{\top}-W$. The goal is to
show that $S$ satisfies the conditions mentioned in Lemma 2.2 with high
probability whenever $I(d,\alpha,\beta)>1$. Observe that, by definition of $D$
in (4), for any $i\in[n]$, we have
$D_{ii}\sigma^{*}(i)=\sum_{j\in[n]}W_{ij}\sigma^{*}(j)$; i.e.
$D\sigma^{*}=W\sigma^{*}$. Therefore, using the fact that
$\langle\mathbf{1},\sigma^{*}\rangle=0$, we get

$S\sigma^{*}=D\sigma^{*}+\mathbf{11}^{\top}\sigma^{*}-W\sigma^{*}=0.$

Therefore, it remains to show that

$\operatorname*{\mathbb{P}}\left(\left\\{\inf_{x\perp\sigma^{*}:\|x\|_{2}=1}x^{\top}Sx>0\right\\}\right)\geq
1-o(1).$

For any $x\perp\sigma^{*}$ such that $\left\lVert x\right\rVert_{2}=1$,

$\displaystyle x^{\top}Sx$
$\displaystyle=x^{\top}Dx+x^{\top}\mathbf{11}^{\top}x-x^{\top}(W-W^{*})x-x^{\top}W^{*}x$
$\displaystyle=x^{\top}Dx+(\mathbf{1}^{\top}x)^{2}-x^{\top}(W-W^{*})x-\left(\frac{p^{\prime}-q^{\prime}}{2}\right)(x^{\top}\sigma^{*})^{2}-\left(\frac{p^{\prime}+q^{\prime}}{2}\right)(\mathbf{1}^{\top}x)^{2}+p^{\prime}$
(using (12) to substitute $W^{*}$)
$\displaystyle=x^{\top}Dx+\left(1-(p^{\prime}+q^{\prime})/2\right)(\mathbf{1}^{\top}x)^{2}-x^{\top}(W-W^{*})x+p^{\prime}$
(since $x\perp\sigma^{*}$) $\displaystyle\geq
x^{\top}Dx+p^{\prime}-x^{\top}(W-W^{*})x$ (since
$p^{\prime},q^{\prime}=\Theta(\log n/n)$ are vanishing)
$\displaystyle\geq\min_{i\in[n]}D_{ii}-\left\lVert W-W^{*}\right\rVert_{2}.$
(by the definition of $\left\lVert.\right\rVert_{2}$ for matrices and the fact
$p^{\prime}\geq 0$)

We now use Lemma 3.2 and take a union bound over $i$ to obtain
$\min_{i\in[n]}D_{ii}\geq\epsilon\log n$ with probability $1-o(1)$. Moreover,
applying Lemma 3.1, $\left\lVert W-W^{*}\right\rVert_{2}\leq C\sqrt{\log n}$
with probability $1-O(n^{-11})$. Therefore, one can conclude that
$x^{\top}Sx\geq\epsilon\log n-C\sqrt{\log n}>0$ for any $x$ such that
$\left\lVert x\right\rVert_{2}=1$ and $x\perp\sigma^{*}$, completing the
proof.

We additionally show that the SDP is robust to a monotone adversary. Here, we
consider an adversary who can increase the value of $W_{ij}$ for any $(i,j)$
in the same community, and decrease the value of $W_{ij}$ for any $(i,j)$ in
opposite communities. The robustness of SDPs to monotone adversaries is well-
known (see e.g. [FK00, FK01]). While the monotone adversary appears to provide
helpful information, spectral algorithms generally fail under such a
semirandom model.

######  Lemma 3.3.

Consider the modified SDP based on (2), with $W$ replaced by $\widetilde{W}$
such that $\widetilde{W}_{ij}\geq W_{ij}$ if $\sigma^{*}(i)=\sigma^{*}(j)$,
and $\widetilde{W}_{ij}\leq W_{ij}$ if $\sigma^{*}(i)\neq\sigma^{*}(j)$. If
$I(d,\alpha,\beta)>1$, then $X^{*}=\sigma^{*}{\sigma^{*}}^{\top}$ is the
unique optimal solution to the modified SDP.

###### Proof.

Let $X$ be a feasible solution to the modified SDP, and let $X^{*}$ be the
unique optimal solution to (2), which is guaranteed by Theorem 1. Due to
uniqueness of $X^{*}$, we have $\langle W,X\rangle<\langle W,X^{*}\rangle$.
Since $X\succeq 0$, we can write

$\displaystyle X=\sum_{l=1}^{n}\lambda_{l}v_{l}v_{l}^{\top}$

as its eigendecomposition, where $\lambda_{l}\geq 0$ for all $l$. Then by the
Cauchy–Schwarz inequality,

$\displaystyle X_{ij}^{2}$
$\displaystyle=\left(\sum_{l=1}^{n}\lambda_{l}v_{l,i}v_{l,j}\right)^{2}$
$\displaystyle\leq\left(\sum_{l=1}^{n}\lambda_{l}v_{l,i}^{2}\right)\left(\sum_{l=1}^{n}\lambda_{l}v_{l,j}^{2}\right)$
$\displaystyle=X_{ii}\cdot X_{jj}$ $\displaystyle=1.$

Therefore, $|X_{ij}|\leq 1$ for all $i,j$, which implies
$\langle\widetilde{W}-W,X\rangle\leq\sum_{i,j\in[n]}|\widetilde{W}_{ij}-W_{ij}|=\langle\widetilde{W}-W,X^{*}\rangle$.
Consequently,

$\langle\widetilde{W},X\rangle=\langle
W,X\rangle+\langle\widetilde{W}-W,X\rangle<\langle
W,X^{*}\rangle+\langle\widetilde{W}-W,X^{*}\rangle=\langle\widetilde{W},X^{*}\rangle,$

establishing the unique optimality of $X^{*}$.

One could also consider another natural monotone adversary that operates
directly on the underlying hypergraph instead of on its similarity matrix.
More specifically, the adversary is allowed to add intra-community edges and
delete cross-community edges. It is not immediately clear whether an SDP
algorithm would be robust to such an adversary.

##  4 Optimal spectral recovery

In Section 4.1, we prove the optimality of Algorithm 2.2 (Theorem 2). In
Section 4.2, we present the proof of our general entrywise eigenvector bound
(Theorem 3).

###  4.1 Analysis of spectral algorithm

We first derive a corollary of Theorem 3, specific to HSBMs.

######  Corollary 4.1.

Fix $d\in\\{2,3,\dots\\}$ and $\alpha>\beta>0$. Let
$G\sim\textnormal{HSBM}(d,n,\alpha,\beta)$ and $W=\mathcal{S}(G)$. Then with
probability at least $1-O(n^{-3})$,

$\min_{s^{*}\in\\{\pm 1\\}}\left\lVert
u_{2}-s^{*}\frac{Wu_{2}^{*}}{\lambda_{2}^{*}}\right\rVert_{\infty}\leq\hskip
2.84526pt\frac{c}{\sqrt{n}\log\log n},$

where $c:=c(d,\alpha,\beta)$ is some positive constant that only depends on
$d,\alpha$, and $\beta$.

###### Proof.

Since each hyperedge exists with probability at most $\alpha\log
n/\binom{n-1}{d-1}$, we can set $c_{0}$ in Theorem 3 to $\alpha$. We now
verify 1. Let $W^{*}$ be the expectation of $W$ conditioned on $\sigma^{*}$,
whose entries are $p^{\prime}$ and $q^{\prime}$ as given by (11). By (12),
$W^{*}+p^{\prime}\mathbf{I}$ is a rank-2 matrix. Its non-zero eigenvalues are
$(p^{\prime}+q^{\prime})n/2$ and $(p^{\prime}-q^{\prime})n/2.$ Accounting for
the diagonal matrix $p^{\prime}I$, the eigenvalues of $W^{*}$ are given by

$\lambda_{1}^{*}=(1+o(1))(p^{\prime}+q^{\prime})n/2\text{ and
}\lambda_{2}^{*}=(1+o(1))(p^{\prime}-q^{\prime})n/2.$

Since $p^{\prime}\asymp q^{\prime}\asymp\log n/n$, we have
$\lambda_{1}^{*},\lambda_{2}^{*}\asymp\log(n)$. Furthermore,

$\Delta_{2}^{*}=\min\left\\{\lambda_{1}^{*}-\lambda_{2}^{*},\lambda_{2}^{*}-0\right\\}=(1+o(1))\min\left\\{q^{\prime}n,\frac{(p^{\prime}-q^{\prime})n}{2}\right\\}\asymp\log
n,$

hiding constants in $\alpha,\beta$ and $d$. Therefore, Theorem 3 applies.

It remains to verify that $\left\lVert
u_{2}^{*}\right\rVert_{\infty}=O(1/\sqrt{n})$. We already know that the second
eigenvector of $W^{*}+p^{\prime}\mathbf{I}$ is $\frac{1}{\sqrt{n}}\sigma^{*}$
by (12). Hence

$u_{2}^{*}=\frac{1+o(1)}{\sqrt{n}}\hskip 2.84526pt\sigma^{*}.$ (13)

###### Proof of Theorem 2.

Let us fix $s=s^{*}$ for which Corollary 4.1 holds. Using the corollary, with
probability $1-o(1)$,

$\sqrt{n}\min_{i\in[n]}s\sigma^{*}(i)u_{2,i}\geq\sqrt{n}\min_{i\in[n]}s^{2}\sigma^{*}(i)(Wu_{2}^{*})_{i}/\lambda_{2}^{*}-c(\log\log
n)^{-1},$ (14)

where $c$ is defined in Corollary 4.1. Note that $s^{2}=1$. Also, using (13),

$\displaystyle\sqrt{n}\sigma^{*}(i)(Wu_{2}^{*})_{i}=(1+o(1))\sum_{j\in[n]}W_{ij}\sigma^{*}(i)\sigma^{*}(j).$

By Lemma 3.2, if $I(d,\alpha,\beta)>1$, then there exists a positive constant
$\epsilon(d,\alpha,\beta)>0$ such that for a fixed $i\in[n]$,
$\sum_{j\in[n]}W_{ij}\sigma^{*}(i)\sigma^{*}(j)\geq\epsilon\log n$ with
probability $1-o(n^{-1})$. Therefore, a union bound implies that with
probability $1-o(1)$,

$\sqrt{n}\min_{i\in[n]}s^{2}\sigma^{*}(i)\frac{(Wu_{2}^{*})_{i}}{\lambda_{2}^{*}}\geq(1+o(1))\epsilon\log
n.$

Since $\lambda_{2}^{*}\asymp\log(n)$, (14) implies that there exists $\eta>0$
such that

$\displaystyle\sqrt{n}\min_{i\in[n]}s^{*}\sigma^{*}(i)(u_{2})_{i}$
$\displaystyle\geq(1+o(1))\epsilon\log n/\lambda_{2}^{*}-c(\log\log
n)^{-1}>\eta,$

with probability $1-o(1)$.

###  4.2 Entrywise analysis

We begin by recalling the setup of Theorem 3. For simplicity, let
$\lambda=\lambda_{k}$, $\lambda^{*}=\lambda^{*}_{k}$ and
$\Delta^{*}=\Delta_{k}^{*}$, dropping the subscript $k$. Let
$s=\text{sgn}(\langle u,u^{*}\rangle)$, so that $\langle su,u^{*}\rangle\geq
0$. Also, for any fixed $m\in[n]$, let $G^{(m)}$ denote the hypergraph after
deleting all the edges incident on $m$ and $W^{(m)}=\mathcal{S}(G^{(m)})$. Let
$(\lambda^{(m)},u^{(m)})$ be its $k$-th eigenpair. Let
$s^{(m)}=\textnormal{sgn}{\langle u^{(m)},u^{*}\rangle}$, so that $\langle
s^{(m)}u^{(m)},u^{*}\rangle\geq 0$. The notation $\lesssim$ and $\asymp$ hide
constants in $d,c_{0}$, and $c_{1}$ (defined as in Theorem 3) throughout this
section. Before proving the theorem, we require some additional observations
and results.

######  Observation 4.2.

$\left\lVert W^{*}\right\rVert_{2\rightarrow\infty}\lesssim\frac{\log
n}{\sqrt{n}}.$

###### Proof.

Recall that $\max_{e}p_{e}\leq\frac{c_{0}\log n}{\binom{n-1}{d-1}}$. Since
each entry $W_{ij}$ is a sum of $\binom{n-2}{d-2}$ Bernoulli random variables,
$\operatorname*{{\mathbb{E}}}{[W_{ij}]}=W^{*}_{ij}\lesssim\log n/n$.
Therefore,

$\left\lVert W^{*}\right\rVert_{2\rightarrow\infty}=\max_{i}\left\lVert
W^{*}_{i\cdot}\right\rVert_{2}\lesssim\sqrt{n}\max{|W^{*}_{ij}|}\lesssim\frac{\log
n}{\sqrt{n}}.\nobreak\hskip 0.0pt\hskip 15.00002pt minus 5.0pt\nobreak\vrule
height=7.5pt,width=5.0pt,depth=2.5pt_{\textnormal{~{}}}$

Define the function $\varphi:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ such
that $\varphi(x)=\frac{(4c_{0}+16)d}{\left(1\vee\log(1/x)\right)}$, where
$c_{0}$ is as in the statement of Theorem 3. We note the following properties
of $\varphi(\cdot)$.

######  Observation 4.3.

$\varphi(x)$ is non-decreasing and $\varphi(x)/x$ is non-increasing on
$\mathbb{R}_{+}$.

The next result provides a probabilistic upper bound on the inner product of a
row of $W-W^{*}$ and a fixed vector $v$, in terms of the function
$\varphi(\cdot)$. Intuitively, one can think that the rate of growth of
$\varphi(\cdot)$ essentially controls the strength of concentration bound.
Formally,

######  Lemma 4.4 (Row concentration).

For any $m\in[n]$ and any fixed non-zero $v\in\mathbb{R}^{n}$,

$\operatorname*{\mathbb{P}}\left(|(W-W^{*})_{m\cdot}v|\leq\left\lVert
v\right\rVert_{\infty}\varphi\left(\frac{\left\lVert
v\right\rVert_{2}}{\sqrt{n}\left\lVert v\right\rVert_{\infty}}\right)\log
n\right)\geq 1-O\left(\frac{1}{n^{4}}\right).$

###### Proof.

Recall the definition of $\mathcal{E}^{(m)}=\\{e\in\mathcal{E}:m\in e\\}$. Let
$v\in\mathbb{R}^{n}$ be a fixed vector. Let $X\triangleq(W-W^{*})_{m\cdot}v$.
It is convenient to rewrite $X$ as a sum of random variables
$\\{A_{e}\\}_{e\in\mathcal{E}^{(m)}}$:

$X=\sum_{e\in\mathcal{E}^{(m)}}\left(\sum_{j\in
e\setminus{\\{m\\}}}v_{j}\right)(A_{e}-\operatorname*{{\mathbb{E}}}[A_{e}]).$

Without loss of generality, assume that $\left\lVert
v\right\rVert_{\infty}=\frac{1}{d}$ (otherwise, $v$ may be scaled). By
Markov’s inequality, for any $\delta,t>0$,

$\operatorname*{\mathbb{P}}\left(X\geq\delta\right)\leq\operatorname*{\mathbb{P}}\left(e^{tX}\geq
e^{t\delta}\right)\leq
e^{-t\delta}\prod_{e\in\mathcal{E}^{(m)}}\operatorname*{{\mathbb{E}}}\left(e^{t(\sum_{j\in
e\setminus{\\{m\\}}}v_{j})(A_{e}-\operatorname*{{\mathbb{E}}}[A_{e}])}\right).$
(15)

For $e\in\mathcal{E}^{(m)}$, we can bound the logarithm of the moment
generating function as follows:

$\displaystyle\log\left(\operatorname*{{\mathbb{E}}}\left[e^{t(\sum_{j\in
e\setminus{\\{m\\}}}v_{j})(A_{e}-\operatorname*{{\mathbb{E}}}[A_{e}])}\right]\right)$
$\displaystyle=\log\left(\operatorname*{{\mathbb{E}}}\left[e^{t(\sum_{j\in
e\setminus{\\{m\\}}}v_{j})A_{e}}\right]\right)-t\left(\sum_{j\in
e\setminus{\\{m\\}}}v_{j}\right)\mathbb{E}[A_{e}]$
$\displaystyle=\log\left(1-p_{e}+p_{e}e^{t\sum_{j\in
e\setminus{\\{m\\}}}v_{j}}\right)-tp_{e}\left(\sum_{j\in
e\setminus{\\{m\\}}}v_{j}\right)$ $\displaystyle\leq p_{e}\left(e^{t\sum_{j\in
e\setminus{\\{m\\}}}v_{j}}-1\right)-tp_{e}\sum_{j\in
e\setminus{\\{m\\}}}v_{j},$ (16)

where we have used the fact that $\log(1+x)\leq x$ for $x>1$ in the last step.
Next, we use the fact that $e^{x}\leq 1+x+\frac{x^{2}}{2}e^{r}$ for $|x|\leq
r$ to further upper-bound (16) by

$\displaystyle p_{e}\left(1+t\sum_{j\in
e\setminus{\\{m\\}}}v_{j}+\frac{e^{td\left\lVert
v\right\rVert_{\infty}}}{2}\cdot t^{2}\left(\sum_{j\in
e\setminus{\\{m\\}}}v_{j}\right)^{2}-1\right)-tp_{e}\sum_{j\in
e\setminus{\\{m\\}}}v_{j}$ $\displaystyle=p_{e}\frac{e^{t}}{2}\cdot
t^{2}\left(\sum_{j\in e\setminus{\\{m\\}}}v_{j}\right)^{2}\leq\hskip
2.84526pt\frac{e^{t}p_{\max}t^{2}}{2}\cdot d\sum_{j\in
e\setminus{\\{m\\}}}{v_{j}}^{2},$

where $\max_{e}p_{e}\triangleq p_{\max}$.

Substituting our bounds on the log of moment generating functions into (15),
we obtain

$\displaystyle\log(\operatorname*{\mathbb{P}}\left(X\geq\delta\right))$
$\displaystyle\leq-t\delta+\frac{e^{t}p_{\max}d}{2}t^{2}\sum_{e\in\mathcal{E}^{(m)}}\sum_{j\in
e\setminus{\\{m\\}}}{v_{j}}^{2}$
$\displaystyle\leq-t\delta+\frac{e^{t}p_{\max}d}{2}\cdot
t^{2}\binom{n-2}{d-2}\left\lVert v\right\rVert_{2}^{2},$

where the last step follows from the fact that each $j\neq m$ appears in
$\binom{n-2}{d-2}$ potential hyperedges in $\mathcal{E}^{(m)}$. Let
$t=1\bigvee\log\left(\frac{\sqrt{n}}{d\left\lVert v\right\rVert_{2}}\right)$.
Using the fact that $(1\lor\log x)^{2}\leq x$ for $x\geq 1$,

$\displaystyle\log(\operatorname*{\mathbb{P}}\left(X\geq\delta\right))$
$\displaystyle\leq-t\delta+\frac{e^{t}p_{\max}d}{2}\frac{\sqrt{n}}{d\left\lVert
v\right\rVert_{2}}\binom{n-2}{d-2}\left\lVert v\right\rVert_{2}^{2}.$

Observe that $\left\lVert v\right\rVert_{2}\leq\sqrt{n}\left\lVert
v\right\rVert_{\infty}=\sqrt{n}/d$, so that
$\log\left(\frac{\sqrt{n}}{d\|v\|_{2}}\right)\geq 0$. Therefore,
$e^{t}=e^{1\vee\log(\frac{\sqrt{n}}{d\|v\|_{2}})}\leq
e^{1+\log(\frac{\sqrt{n}}{d\|v\|_{2}})}\leq\frac{e\sqrt{n}}{d\|v\|_{2}}.$
Hence

$\log(\operatorname*{\mathbb{P}}\left(X\geq\delta\right))\leq-t\delta+\frac{ep_{\max}d}{2}\cdot\frac{\sqrt{n}}{d\left\lVert
v\right\rVert_{2}}\frac{\sqrt{n}}{d\left\lVert
v\right\rVert_{2}}\binom{n-2}{d-2}\left\lVert
v\right\rVert_{2}^{2}=-t\delta+\frac{e^{t}p_{\max}n\binom{n-2}{d-2}}{2d}.$

Let $a=\nicefrac{{8}}{{c_{0}}}$, and set
$\delta=~{}t^{-1}d^{-1}(2+a)p_{\max}n\binom{n-2}{d-2}.$ We then obtain the
bound

$\log(\operatorname*{\mathbb{P}}\left(X\geq\delta\right))\leq-\frac{(2+a)p_{\max}n}{d}\binom{n-2}{d-2}+\frac{ep_{\max}n\binom{n-2}{d-2}}{2d}\leq-\frac{ap_{\max}n\binom{n-2}{d-2}}{d}.$

By replacing $v$ with $-v$, we obtain a similar bound for the lower tail. The
union bound gives

$\operatorname*{\mathbb{P}}\left(|X|\geq\delta\right)\leq
2\exp\left(-\frac{ap_{\max}n\binom{n-2}{d-2}}{d}\right).$

Substituting in the value of $t$ and using $p_{\max}\leq\frac{c_{0}\log
n}{\binom{n-1}{d-1}}$,

$\operatorname*{\mathbb{P}}\left(|(W-W^{*})_{m\cdot}v|\geq\frac{(2+a)2c_{0}\log
n}{1\bigvee\log\left(\frac{\sqrt{n}}{d\left\lVert
v\right\rVert_{2}}\right)}\right)\leq 2e^{-\frac{a{c_{0}}\log n}{2}}.$

Finally, substituting the value of $a$,

$\operatorname*{\mathbb{P}}\left(|(W-W^{*})_{m\cdot}v|\leq\frac{4(c_{0}+4)\log
n}{1\bigvee\log\left(\frac{\sqrt{n}}{d\left\lVert
v\right\rVert_{2}}\right)}\right)\geq 1-2{n}^{-4}.$

Recalling that $\left\lVert v\right\rVert_{\infty}=1/d$ yields:

$\operatorname*{\mathbb{P}}\left(|(W-W^{*})_{m\cdot}v|\leq\frac{(4c_{0}+16)d\left\lVert
v\right\rVert_{\infty}\log n}{1\bigvee\log\left(\frac{\sqrt{n}\left\lVert
v\right\rVert_{\infty}}{\left\lVert v\right\rVert_{2}}\right)}\right)\geq
1-2{n}^{-4}.$

Since $\varphi\left(\frac{\left\lVert v\right\rVert_{2}}{\sqrt{n}\left\lVert
v\right\rVert_{\infty}}\right)=(4c_{0}+16)d/(1\vee\log\left(\frac{\sqrt{n}\left\lVert
v\right\rVert_{\infty}}{\left\lVert v\right\rVert_{2}}\right)$, the lemma
follows.

######  Lemma 4.5.

$\left\lVert W-W^{(m)}\right\rVert_{2}\lesssim\hskip 2.84526pt\left\lVert
W\right\rVert_{2\rightarrow\infty}$.

###### Proof.

Note that $W-W^{(m)}$ is the similarity matrix of the graph with edges present
only from $\mathcal{E}^{(m)}$. Consider any $i\neq m$. Since for any
$e\in\mathcal{E}^{(m)}$ with $\\{i,m\\}\subseteq e$, the label of $e$ is added
to exactly $(d-1)$ entries of the $i$-th row of $W-W^{(m)}$, we have

$\|(W-W^{(m)})_{i\cdot}\|_{1}=(d-1)W_{im}.$ (17)

Therefore
$\left\lVert(W-W^{(m)})_{i\cdot}\right\rVert_{2}\leq\left\lVert(W-W^{(m)})_{i\cdot}\right\rVert_{1}\leq(d-1)W_{im}$.
Hence we get

$\displaystyle\|W-W^{(m)}\|_{2}$ $\displaystyle\leq\|W-W^{(m)}\|_{F}$
$\displaystyle=\sqrt{\sum_{i\in[n]}\left\lVert(W-W^{(m)})_{i\cdot}\right\rVert_{2}^{2}}$
$\displaystyle\leq\sqrt{\left\lVert
W_{m\cdot}\right\rVert_{2}^{2}+\sum_{i\in[n]\setminus\\{m\\}}(d-1)^{2}W_{im}^{2}}$
$\displaystyle\lesssim\hskip 2.84526pt\sqrt{\left\lVert
W_{m\cdot}\right\rVert_{2}^{2}}\hskip 2.84526pt\leq\hskip 2.84526pt\left\lVert
W\right\rVert_{2\rightarrow\infty}.\nobreak\hskip 0.0pt\hskip 15.00002pt minus
5.0pt\nobreak\vrule height=7.5pt,width=5.0pt,depth=2.5pt_{\textnormal{~{}}}$

Let $\gamma=\gamma_{n}\coloneqq C/\sqrt{\log n}$, where $C=C(d,c_{0})>0$ is
the constant from Lemma 3.1. We define the following event:

$F_{0}:=\\{\left\lVert W-W^{*}\right\rVert_{2}\leq\gamma\log n=C\sqrt{\log
n}\\}.$

By Lemma 3.1, $\operatorname*{\mathbb{P}}\left(F_{0}\right)\geq 1-O(n^{-11})$.
Also,

$\gamma=o(1)\hskip 5.69054pt\text{and }\hskip
5.69054pt\varphi(\gamma)\lesssim\left(\frac{1}{1\vee\log\sqrt{\log
n}}\right)\lesssim\frac{1}{\log\log n}=o(1).$ (18)

We now derive some bounds on important quantities conditioned on the above
event.

######  Lemma 4.6.

Conditioned on $F_{0}$, we have $|\lambda^{*}|\asymp|\lambda|\asymp\log n$.

###### Proof.

Conditioned on the event $F_{0}$, Weyl’s inequality implies
$|\lambda-\lambda^{*}|\leq\left\lVert W-W^{*}\right\rVert_{2}\leq\gamma\log
n$. Therefore, $\lambda\in[\lambda^{*}-\gamma\log n,\lambda^{*}+\gamma\log
n]$. 1 (i.e. $|\lambda^{*}|\asymp\log n$) then ensures that
$|\lambda^{*}|\asymp|\lambda|\asymp\log n$.

######  Lemma 4.7.

Conditioned on $F_{0}$,

$\left\lVert W\right\rVert_{2\rightarrow\infty}\lesssim\gamma\log n\hskip
5.69054pt\textnormal{ and for all }m\in[n],\hskip 5.69054pt\left\lVert
W^{(m)}-W^{*}\right\rVert_{2}\lesssim\gamma\log n.$

###### Proof.

By the triangle inequality,

$\displaystyle\left\lVert W\right\rVert_{2\rightarrow\infty}\leq\left\lVert
W-W^{*}\right\rVert_{2}+\left\lVert
W^{*}\right\rVert_{2\rightarrow\infty}\hskip 2.84526pt\leq\hskip
2.84526pt\gamma\log n+\left\lVert
W^{*}\right\rVert_{2\rightarrow\infty}\lesssim\gamma\log n,$

where we use Observation 4.2 to get the last inequality. Similarly, using the
triangle inequality and Lemma 4.5,

$\|W^{(m)}-W^{*}\|_{2}\hskip 2.84526pt\leq\hskip 2.84526pt\left\lVert
W-W^{*}\right\rVert_{2}+\|W-W^{(m)}\|_{2}\hskip 2.84526pt\lesssim\hskip
2.84526pt\left\lVert W-W^{*}\right\rVert_{2}+\left\lVert
W\right\rVert_{2\rightarrow\infty}\lesssim\gamma\log n.\nobreak\hskip
0.0pt\hskip 15.00002pt minus 5.0pt\nobreak\vrule
height=7.5pt,width=5.0pt,depth=2.5pt_{\textnormal{~{}}}$

Having derived the above bounds, we now bound the $\ell_{2}$ and
$\ell_{\infty}$ norms of $(s^{(m)}u^{(m)}-u^{*})$ and $(su-s^{(m)}u^{(m)})$
using two variants of the Davis and Kahan sin$(\theta)$ theorem. For
completeness, we include the less well-known variant here, which is a special
case of [DLS21, Theorem 3].

######  Proposition 4.8 (Generalized Davis and Kahan sin$(\theta)$ theorem
[DLS21]).

Let $M\in\mathbb{R}^{n\times n}$ be a symmetric matrix and let $X$ be the
matrix that has the eigenvectors of $M$ as columns. Then $M$ can be decomposed
as
$M={X}\Lambda{X^{\top}}=X_{1}\Lambda_{1}{X_{1}}^{\top}+X_{2}\Lambda_{2}{X_{2}}^{\top}$,
where $X=[X_{1}\hskip 2.84526ptX_{2}]$ and
$\Lambda=\begin{bmatrix}\Lambda_{1}&0\\\ 0&\Lambda_{2}\end{bmatrix}.$ Suppose
$\delta=\min_{i}|(\Lambda_{2})_{ii}-\hat{\lambda}|$ is the absolute separation
of some $\hat{\lambda}$ from $\Lambda_{2}$, then for any vector $\hat{u}$ we
have

$\sin(\theta)\leq\frac{\|(M-\hat{\lambda}\mathbf{I})\,\hat{u}\|_{2}}{\delta},$

where $\theta$ is the canonical angle between the span of $X_{1}$ and
$\hat{u}$.

######  Lemma 4.9.

Conditioned on $F_{0}$,

$\max_{m\in[n]}\|s^{(m)}u^{(m)}-u^{*}\|_{2}\lesssim\gamma,$ (19)
$\max_{m\in[n]}\|su-s^{(m)}u^{(m)}\|_{2}\lesssim(\gamma\wedge\left\lVert
u\right\rVert_{\infty}),$ (20)
$\max_{m\in[n]}\|s^{(m)}u^{(m)}-u^{*}\|_{\infty}\lesssim(\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty}).$ (21)

###### Proof.

For any $m\in[n]$, we apply a variant of the Davis–Kahan sin$(\theta)$ theorem
[YWS14, Corollary 3] to get

$\|s^{(m)}u^{(m)}-u^{*}\|_{2}\hskip 2.84526pt\leq\hskip
2.84526pt\frac{2^{3/2}\left\lVert
W^{(m)}-W^{*}\right\rVert_{2}}{\Delta^{*}}\hskip 2.84526pt\lesssim\hskip
2.84526pt\frac{\gamma\log n}{\log n}=\gamma,$

where the second inequality follows from Lemma 4.7 and 1, concluding the proof
of (19). Similarly, we also get

$\|su-s^{(m)}u^{(m)}\|_{2}\hskip 2.84526pt\leq\hskip
2.84526pt\|su-u^{*}\|_{2}+\|s^{(m)}u^{(m)}-u^{*}\|_{2}\hskip
2.84526pt\lesssim\hskip 2.84526pt\frac{\left\lVert
W-W^{*}\right\rVert_{2}}{\Delta^{*}}+\gamma\hskip 2.84526pt\lesssim\hskip
2.84526pt\gamma.$ (22)

Therefore, $\langle su,s^{(m)}u^{(m)}\rangle\geq 0$. Let $\theta$ denote the
angle between $su$ and $s^{(m)}u^{(m)}$. Then

$\displaystyle\|su-s^{(m)}u^{(m)}\|_{2}\leq\sqrt{\|u\|_{2}^{2}+\|u^{(m)}\|_{2}^{2}-2\|u\|_{2}\|u^{(m)}\|_{2}\,\textnormal{cos
}\theta}\leq\sqrt{2-2\,\textnormal{cos}^{2}\theta}=\sqrt{2}\sin\theta.$

We then apply Proposition 4.8 with $M=W^{(m)},X_{1}=[u^{(m)}]$ and
$(\hat{\lambda},\hat{u})=(\lambda,u)$:

$\displaystyle\|su-s^{(m)}u^{(m)}\|_{2}\leq\sqrt{2}\sin\theta$
$\displaystyle\leq\frac{\sqrt{2}\left\lVert(W^{(m)}-\lambda)u\right\rVert_{2}}{|\lambda^{(m)}_{k+1}-\lambda|\wedge|\lambda-\lambda^{(m)}_{k-1}|}$
$\displaystyle\leq\frac{\sqrt{2}\left\lVert(W^{(m)}-W)u\right\rVert_{2}}{\left(\lambda_{k+1}-\lambda_{k}\right)\wedge\left(\lambda_{k}-\lambda_{k-1}\right)-\|W-W^{(m)}\|_{2}}$
$\displaystyle\lesssim\frac{\left\lVert(W-W^{(m)})u\right\rVert_{2}}{\Delta^{*}-2\|W-W^{*}\|_{2}-\|W-W^{(m)}\|_{2}}.$

Using 1, the definition of $F_{0}$, and Lemmas 4.5, 4.7, we can lower-bound
the denominator by

$\Delta^{*}-2\|W-W^{*}\|_{2}-\|W-W^{(m)}\|_{2}\gtrsim(1-\gamma)\log n.$

Since $\gamma=o(1)$ by (18), we obtain

$\displaystyle\|su-s^{(m)}u^{(m)}\|_{2}\lesssim\frac{\|(W-W^{(m)})u\|_{2}}{\log
n}.$

Let $v=(W-W^{(m)})u$. We have already seen that the $m$-th row of $W-W^{(m)}$
is the same as $W$, so that $v_{m}=\lambda u_{m}$. Therefore, we bound the
$m$-th entry of $v$ and the rest of its entries separately. Formally,

$\displaystyle|v_{m}|$
$\displaystyle\leq|[Wu]_{m}|=|\lambda||u_{m}|\leq|\lambda|\left\lVert
u\right\rVert_{\infty},$ $\displaystyle|v_{i}|$
$\displaystyle\leq|[(W-W^{(m)})u]_{i}|\leq\|(W-W^{(m)})_{i\cdot}\|_{1}\left\lVert
u\right\rVert_{\infty}\lesssim W_{im}\left\lVert
u\right\rVert_{\infty},\textnormal{ for $i\neq m$},$

where the last inequality follows from (17). Therefore,

$\left\lVert v\right\rVert_{2}\hskip 2.84526pt\lesssim\hskip
2.84526pt\left\lVert u\right\rVert_{\infty}\sqrt{\lambda^{2}+\sum_{i\neq
m}W_{im}^{2}}\hskip 2.84526pt\lesssim\left\lVert u\right\rVert_{\infty}\hskip
2.84526pt\sqrt{{|\lambda^{*}|}^{2}+\left\lVert
W\right\rVert_{2\rightarrow\infty}^{2}},$ (23)

where the last step requires Lemma 4.6. Substituting the bound (23):

$\|su-s^{(m)}u^{(m)}\|_{2}\hskip 2.84526pt\lesssim\hskip
2.84526pt\frac{\left\lVert v\right\rVert_{2}}{\log n}\hskip
2.84526pt\lesssim\hskip 2.84526pt\frac{\left\lVert
u\right\rVert_{\infty}\sqrt{{|\lambda^{*}|}^{2}+\left\lVert
W\right\rVert_{2\rightarrow\infty}^{2}}}{\log n}\hskip 2.84526pt\lesssim\hskip
2.84526pt\left\lVert u\right\rVert_{\infty},$ (24)

where the last inequality follows from Lemma 4.7 and 1. Observe that (22) and
(24) together imply (20). Finally, to prove (21), we apply the triangle
inequality again and use (24).

$\|s^{(m)}u^{(m)}-u^{*}\|_{\infty}\leq\|su-s^{(m)}u^{(m)}\|_{2}+\left\lVert
u\right\rVert_{\infty}+\left\lVert
u^{*}\right\rVert_{\infty}\lesssim\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty},$

concluding the proof.

######  Lemma 4.10.

With probability at least $1-O(n^{-3})$,

$\left\lVert(W-W^{*})u^{*}\right\rVert_{\infty}\lesssim\left\lVert
u^{*}\right\rVert_{\infty}\log n\hskip 8.53581pt\textnormal{ and }\hskip
8.53581pt\left\lVert Wu^{*}\right\rVert_{\infty}\lesssim\left\lVert
u^{*}\right\rVert_{\infty}\log n.$

###### Proof.

To prove the first inequality, we apply Lemma 4.4. For each $m\in[n]$, we have
$|(W-W^{*})_{m\cdot}u^{*}|\leq\varphi(\frac{\left\lVert
u^{*}\right\rVert_{2}}{\sqrt{n}\left\lVert
u^{*}\right\rVert_{\infty}})\left\lVert u^{*}\right\rVert_{\infty}\log n$ with
probability $1-O(n^{-4})$. Using the monotonicity of $\varphi$ (Observation
4.3) and $\left\lVert u^{*}\right\rVert_{2}\leq\sqrt{n}\left\lVert
u\right\rVert_{\infty}$, we obtain
$|(W-W^{*})_{m\cdot}u^{*}|\leq\varphi(1)\left\lVert
u^{*}\right\rVert_{\infty}\log n$. Note that $\varphi(1)=O(1)$. Taking a union
bound over all $m\in[n]$, we have
$\left\lVert(W-W^{*})u^{*}\right\rVert_{\infty}\leq\varphi(1)\left\lVert
u^{*}\right\rVert_{\infty}\log n$, with probability at least $1-O(n^{-3})$.

To get the second inequality, we use the triangle inequality as follows.

$\left\lVert Wu^{*}\right\rVert_{\infty}\leq\left\lVert
W^{*}u^{*}\right\rVert_{\infty}+\left\lVert(W-W^{*})u^{*}\right\rVert_{\infty}\leq|\lambda^{*}|\left\lVert
u^{*}\right\rVert_{\infty}+\varphi(1)\left\lVert
u^{*}\right\rVert_{\infty}\log n\lesssim\left\lVert
u^{*}\right\rVert_{\infty}\log n.$

The last inequality in the above follows from 1.

######  Lemma 4.11.

With probability at least $1-O(n^{-3})$,

$\max_{m\in[n]}|W_{m\cdot}v^{(m)}|\lesssim(\gamma+\varphi(\gamma))(\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty})\log n.$

###### Proof.

We know that $\operatorname*{\mathbb{P}}\left(F_{0}\right)\geq 1-O(n^{-11})$
by Lemma 3.2. Conditioned on $F_{0}$, for all $m\in[n]$

$\displaystyle|W_{m\cdot}v^{(m)}|$
$\displaystyle\leq|W^{*}_{m\cdot}v^{(m)}|+|(W-W^{*})_{m\cdot}v^{(m)}|$ (by the
triangle inequality) $\displaystyle\leq\left\lVert
W^{*}\right\rVert_{2}\|v^{(m)}\|_{2}+|(W-W^{*})_{m\cdot}v^{(m)}|$ (by
definition of $\left\lVert.\right\rVert_{2}$)
$\displaystyle\lesssim\frac{\gamma\log
n}{\sqrt{n}}+|(W-W^{*})_{m\cdot}v^{(m)}|$ (by Observation 4.2 and (19))
$\displaystyle\leq\gamma\left\lVert u^{*}\right\rVert_{\infty}\log
n+|(W-W^{*})_{m\cdot}v^{(m)}|.$ (25)

We now focus on bounding the second term. We know that $v^{(m)}$ is
independent of randomness in the $m$-th row of $W$. Therefore, by the row
concentration (Lemma 4.4), for a fixed $m\in[n]$

$|(W-W^{*})_{m\cdot}v^{(m)}|\leq\|v^{(m)}\|_{\infty}\varphi\left(\frac{\|v^{(m)}\|_{2}}{\sqrt{n}\|v^{(m)}\|_{\infty}}\right)\log
n,$ (26)

holds with probability at least $1-O(n^{-4})$. Let $F$ be the event that (26)
holds simultaneously for all $m\in[n]$. By a union bound,
$\operatorname*{\mathbb{P}}\left(F\right)\geq 1-O(n^{-3})$. Conditioned on the
event $F$, let us consider two different cases.
_Case 1_ : Suppose
$\frac{\|v^{(m)}\|_{2}}{\sqrt{n}\|v^{(m)}\|_{\infty}}\leq\gamma$. Under this
case, we use the fact that $\varphi(x)$ is non-decreasing (Observation 4.3) in
(26) to get:

$|(W-W^{*})_{m\cdot}v^{(m)}|\leq\varphi(\gamma)\|v^{(m)}\|_{\infty}\log n.$

_Case 2_ : Suppose
$\frac{\|v^{(m)}\|_{2}}{\sqrt{n}\|v^{(m)}\|_{\infty}}>\gamma$. In this case,
multiplying and dividing (26) by 1,

$\displaystyle|(W-W^{*})_{m\cdot}v^{(m)}|$
$\displaystyle\leq\|v^{(m)}\|_{\infty}\varphi\left(\frac{\|v^{(m)}\|_{2}}{\sqrt{n}\|v^{(m)}\|_{\infty}}\right)\log
n$
$\displaystyle=\frac{\|v^{(m)}\|_{2}}{\sqrt{n}}\frac{\sqrt{n}\|v^{(m)}\|_{\infty}}{\|v^{(m)}\|_{2}}\varphi\left(\frac{\|v^{(m)}\|_{2}}{\sqrt{n}\|v^{(m)}\|_{\infty}}\right)\log
n$
$\displaystyle\leq\frac{\varphi(\gamma)}{\gamma}\frac{\|v^{(m)}\|_{2}}{\sqrt{n}}\log
n.$ (by Observation 4.3; $\varphi(x)/x$ is non-increasing.)

Combining both the cases, for all $m\in[n]$:

$|(W-W^{*})_{m\cdot}v^{(m)}|\leq\varphi(\gamma)\log
n\left(\|v^{(m)}\|_{\infty}\vee\frac{\|v^{(m)}\|_{2}}{\gamma\sqrt{n}}\right).$

Substituting bounds from (19) and (21) in the above, and then using the fact
that $\left\lVert u^{*}\right\rVert_{\infty}\geq\left\lVert
u^{*}\right\rVert_{2}/\sqrt{n}=1/\sqrt{n}$, we obtain

$|(W-W^{*})_{m\cdot}v^{(m)}|\lesssim\varphi(\gamma)\log
n\left(\left(\left\lVert u\right\rVert_{\infty}+\left\lVert
u^{*}\right\rVert_{\infty}\right)\vee\frac{\gamma}{\gamma\sqrt{n}}\right)\lesssim\varphi(\gamma)\left(\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty}\right)\log n.$

Finally, we substitute into (25):

$\displaystyle\max_{m\in[n]}|W_{m\cdot}v^{(m)}|$
$\displaystyle\lesssim\gamma\left\lVert u^{*}\right\rVert_{\infty}\log
n+\varphi(\gamma)(\left\lVert u\right\rVert_{\infty}+\left\lVert
u^{*}\right\rVert_{\infty})\log n$
$\displaystyle\leq(\gamma+\varphi(\gamma))(\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty})\log n,$

concluding the proof.

We finally prove the theorem.

###### Proof of Theorem 3.

Recall the definition of the event $F_{0}$ and
$\operatorname*{\mathbb{P}}\left(F_{0}\right)\geq 1-O(n^{11})$. Conditioned on
$F_{0}$, we have $|\lambda|\asymp|\lambda^{*}|$ by Lemma 4.6; we use this
throughout the proof.

We first bound $\left\lVert u\right\rVert_{\infty}$ in terms of $\left\lVert
u^{*}\right\rVert_{\infty}$ as we need our final bounds only in terms of the
latter. By the triangle inequality,

$\displaystyle\left\lVert u\right\rVert_{\infty}$
$\displaystyle=\left\lVert\frac{sWu}{\lambda}\right\rVert_{\infty}\leq\hskip
2.84526pt\left\lVert\frac{Wu^{*}}{\lambda}\right\rVert_{\infty}+\left\lVert\frac{W(su-u^{*})}{\lambda}\right\rVert_{\infty}\lesssim\hskip
2.84526pt\frac{1}{|\lambda^{*}|}\left(\left\lVert
Wu^{*}\right\rVert_{\infty}+\max_{m\in[n]}{|W_{m\cdot}(su-u^{*})|}\right)$
$\displaystyle\leq\hskip 2.84526pt\frac{1}{|\lambda^{*}|}\left(\left\lVert
Wu^{*}\right\rVert_{\infty}+\max_{m\in[n]}|W_{m\cdot}(su-s^{(m)}u^{(m)})|+\max_{m\in[n]}|W_{m\cdot}(s^{(m)}u^{(m)}-u^{*})|\right)$
$\displaystyle\leq\hskip 2.84526pt\frac{1}{|\lambda^{*}|}\left(\left\lVert
Wu^{*}\right\rVert_{\infty}+\left\lVert
W\right\rVert_{2\rightarrow\infty}\max_{m\in[n]}\|su-s^{(m)}u^{(m)}\|_{2}+\max_{m\in[n]}|W_{m\cdot}(s^{(m)}u^{(m)}-u^{*})|\right).$

In light of Lemma 3.1,
$\operatorname*{\mathbb{P}}\left(F_{0}\right)=1-O(n^{-11})$. We substitute the
derived bounds from Lemma 4.10 in the first term, Lemmas 4.7 and 4.9 in the
second term, and Lemma 4.11 in the third term. In particular, we obtain that
with probability at least $1-O(n^{-3})$,

$\displaystyle\left\lVert u\right\rVert_{\infty}$
$\displaystyle\lesssim\frac{1}{|\lambda^{*}|}\Big{(}\left\lVert
u^{*}\right\rVert_{\infty}\log n+(\gamma\log n)\left\lVert
u\right\rVert_{\infty}+(\gamma+\varphi(\gamma))(\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty})\log n\Big{)}$
$\displaystyle\lesssim\Big{(}(1+\gamma+\varphi(\gamma))\left\lVert
u^{*}\right\rVert_{\infty}+(\gamma+\varphi(\gamma)\left\lVert
u\right\rVert_{\infty}\Big{)}.\hskip 28.45274pt$ (using 1)

Using the fact that $\gamma,\varphi(\gamma)=o(1)$ from (18), we have that for
some constant $c_{3}>0$,

$\displaystyle\left\lVert u\right\rVert_{\infty}$ $\displaystyle\leq
c_{3}\left\lVert u^{*}\right\rVert_{\infty}+o(1)\left\lVert
u\right\rVert_{\infty}$ $\displaystyle(1-o(1))\left\lVert
u\right\rVert_{\infty}$ $\displaystyle\leq c_{3}\left\lVert
u^{*}\right\rVert_{\infty}$ $\displaystyle\left\lVert u\right\rVert_{\infty}$
$\displaystyle\leq\hskip 5.69054pt\frac{c_{3}}{1-o(1)}\left\lVert
u^{*}\right\rVert_{\infty}\lesssim\left\lVert u^{*}\right\rVert_{\infty}.$
(27)

Similarly, conditioned on $F_{0}$, we bound the quantity of interest. Using
the triangle inequality,

$\displaystyle\left\lVert su-\frac{Wu^{*}}{\lambda^{*}}\right\rVert_{\infty}$
$\displaystyle=\left\lVert\frac{sWu}{\lambda}-\frac{Wu^{*}}{\lambda}+\frac{Wu^{*}}{\lambda}-\frac{Wu^{*}}{\lambda^{*}}\right\rVert_{\infty}$
$\displaystyle\leq\left|\frac{1}{\lambda}-\frac{1}{\lambda^{*}}\right|\left\lVert
Wu^{*}\right\rVert_{\infty}+\frac{1}{|\lambda|}\left\lVert
W(su-u^{*})\right\rVert_{\infty}.$

Recalling that $|\lambda|\asymp|\lambda^{*}|$,

$\displaystyle\left\lVert su-\frac{Wu^{*}}{\lambda^{*}}\right\rVert_{\infty}$
$\displaystyle\lesssim\frac{1}{|\lambda^{*}|}\left(\gamma\left\lVert
Wu^{*}\right\rVert_{\infty}+\left\lVert
W(su-u^{*})\right\rVert_{\infty}\right)$
$\displaystyle\lesssim\frac{1}{|\lambda^{*}|}\left(\gamma\left\lVert
Wu^{*}\right\rVert_{\infty}+\left\lVert
W\right\rVert_{2\rightarrow\infty}\max_{m\in[n]}\|su-s^{(m)}u^{(m)}\|_{2}+\max_{m\in[n]}|W_{m\cdot}(s^{(m)}u^{(m)}-u^{*})|\right).$

We again substitute the bounds from Lemma 4.10 in the first term, Lemma 4.7
and 4.9 in the second term, and Lemma 4.11 in the third term. In particular,
we obtain that with probability at least $1-O(n^{-3})$,

$\displaystyle\left\lVert su-\frac{Wu^{*}}{\lambda^{*}}\right\rVert_{\infty}$
$\displaystyle\lesssim\frac{1}{|\lambda^{*}|}\Big{(}\gamma\left\lVert
u^{*}\right\rVert_{\infty}\log n+(\gamma\log n)\left\lVert
u\right\rVert_{\infty}+(\gamma+\varphi(\gamma))(\left\lVert
u\right\rVert_{\infty}+\left\lVert u^{*}\right\rVert_{\infty})\log n\Big{)}$
$\displaystyle\lesssim\Big{(}(\gamma+\varphi(\gamma))\left\lVert
u^{*}\right\rVert_{\infty}+(\gamma+\varphi(\gamma)\left\lVert
u\right\rVert_{\infty}\Big{)}$ (using 1)
$\displaystyle\lesssim(\gamma+\varphi(\gamma))\left\lVert
u^{*}\right\rVert_{\infty}$ (using $\left\lVert
u\right\rVert_{\infty}\lesssim\left\lVert u^{*}\right\rVert_{\infty}$ as shown
in (27)) $\displaystyle\lesssim\frac{\left\lVert
u^{*}\right\rVert_{\infty}}{\log\log n}.$ ($\gamma=O(\varphi(\gamma))$ and
using (18))

This is precisely the bound we need, concluding the proof.

## References

  * [Abb17] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  The Journal of Machine Learning Research, 18(1):6446–6531, 2017\.
  * [ABBS14] Emmanuel Abbe, Afonso S Bandeira, Annina Bracher, and Amit Singer.  Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery.  IEEE Transactions on Network Science and Engineering, 1(1):10–22, 2014.
  * [ABH16] Emmanuel Abbe, Afonso S. Bandeira, and G. Hall.  Exact recovery in the stochastic block model.  IEEE Transactions on Information Theory, 62:471–487, 2016.
  * [AFWZ20] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  Annals of statistics, 48 3:1452–1474, 2020.
  * [ALS18] Kwangjun Ahn, Kangwook Lee, and Changho Suh.  Hypergraph spectral clustering in the weighted stochastic block model.  IEEE Journal of Selected Topics in Signal Processing, 12(5):959–974, 2018.
  * [AS15a] Emmanuel Abbe and Colin Sandon.  Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670–688, 2015.
  * [AS15b] Emmanuel Abbe and Colin Sandon.  Recovering communities in the general stochastic block model without knowing the parameters.  In Advances in Neural Information Processing Systems, volume 28, 2015.
  * [BBKY13] Derek Bean, Peter J. Bickel, Noureddine El Karoui, and Bin Yu.  Optimal m-estimation in high-dimensional regression.  Proceedings of the National Academy of Sciences, 110(36):14563–14568, 2013.
  * [BKN11] Brian Ball, Brian Karrer, and M. E. J. Newman.  Efficient and principled method for detecting communities in networks.  Phys. Rev. E, 84:036103, Sep 2011.
  * [CLW19] I Eli Chien, Chung-Yi Lin, and I-Hsiang Wang.  On the minimax misclassification ratio of hypergraph community detection.  IEEE Transactions on Information Theory, 65(12):8095–8118, 2019\.
  * [CY06] Jingchun Chen and Bo Yuan.  Detecting functional modules in the yeast protein–protein interaction network.  Bioinformatics, 22(18):2283–2290, 07 2006.
  * [CZ20] Sam Cole and Yizhe Zhu.  Exact recovery in the hypergraph stochastic block model: A spectral algorithm.  Linear Algebra and its Applications, 593:45–73, 2020.
  * [DF89] Martin E. Dyer and Alan M. Frieze.  The solution of some random NP-hard problems in polynomial expected time.  Journal of Algorithms, 10(4):451–489, 1989.
  * [DGMS22a] Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon.  The power of two matrices in spectral algorithms.  2022\.  Forthcoming.
  * [DGMS22b] Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon.  Spectral algorithms optimally recover (censored) planted dense subgraphs.  arXiv preprint arXiv:2203.11847, 2022.
  * [DGMS22c] Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon.  Spectral recovery of binary censored block models.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3389–3416. SIAM, 2022.
  * [DK70] Chandler Davis and William Kahan.  The rotation of eigenvectors by a perturbation. iii.  SIAM Journal on Numerical Analysis, 7:1–46, 1970.
  * [DKMZ11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  Physical Review E, 84(6):066106, 2011.
  * [DLS21] Shaofeng Deng, Shuyang Ling, and Thomas Strohmer.  Strong consistency, graph Laplacians, and the stochastic block model.  J. Mach. Learn. Res., 22(117):1–44, 2021.
  * [FK00] Uriel Feige and Robert Krauthgamer.  Finding and certifying a large hidden clique in a semirandom graph.  Random Structures & Algorithms, 16(2):195–208, 2000.
  * [FK01] Uriel Feige and Joe Kilian.  Heuristics for semirandom graph problems.  Journal of Computer and System Sciences, 63(4):639–671, 2001.
  * [FO05] Uriel Feige and Eran Ofek.  Spectral techniques applied to sparse random graphs.  Random Structures & Algorithms, 27(2):251–275, 2005.
  * [GD14] Debarghya Ghoshdastidar and Ambedkar Dukkipati.  Consistency of spectral partitioning of uniform hypergraphs under planted partition model.  Advances in Neural Information Processing Systems, 27, 2014.
  * [GD15a] Debarghya Ghoshdastidar and Ambedkar Dukkipati.  A provable generalized tensor spectral method for uniform hypergraph partitioning.  In International Conference on Machine Learning, pages 400–409. PMLR, 2015.
  * [GD15b] Debarghya Ghoshdastidar and Ambedkar Dukkipati.  Spectral clustering using multilinear SVD: Analysis, approximations and applications.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
  * [GD17] Debarghya Ghoshdastidar and Ambedkar Dukkipati.  Consistency of spectral hypergraph partitioning under planted partition model.  The Annals of Statistics, 45(1):289–315, 2017.
  * [GZFA10] Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg, and Edoardo M. Airoldi.  A survey of statistical network models.  Found. Trends Mach. Learn., 2(2):129–233, feb 2010.
  * [HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social networks, 5(2):109–137, 1983.
  * [HWX16a] Bruce Hajek, Yihong Wu, and Jiaming Xu.  Achieving exact cluster recovery threshold via semidefinite programming.  IEEE Transactions on Information Theory, 62(5):2788–2797, 2016\.
  * [HWX16b] Bruce Hajek, Yihong Wu, and Jiaming Xu.  Achieving exact cluster recovery threshold via semidefinite programming: Extensions.  IEEE Transactions on Information Theory, 62(10):5918–5937, 2016\.
  * [JMRT16] Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi.  Phase transitions in semidefinite relaxations.  Proceedings of the National Academy of Sciences, 113(16):E2218–E2223, 2016.
  * [KBG18] Chiheon Kim, Afonso S Bandeira, and Michel X Goemans.  Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach.  arXiv preprint arXiv:1807.02884, 2018.
  * [KRRT99] Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins.  Trawling the web for emerging cyber-communities.  Computer Networks, 31(11):1481–1493, 1999.
  * [LKC20] Jeonghwan Lee, Daesung Kim, and Hye Won Chung.  Robust hypergraph clustering via convex relaxation of truncated mle.  IEEE Journal on Selected Areas in Information Theory, 1(3):613–631, 2020.
  * [Mas14] Laurent Massoulié.  Community detection thresholds and the weak Ramanujan property.  In Symposium on Theory of Computing, STOC 2014, page 694–703, New York, NY, USA, 2014. Association for Computing Machinery.
  * [McS01] Frank McSherry.  Spectral partitioning of random graphs.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529–537. IEEE, 2001.
  * [MNS13] Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture, 2013.
  * [MPN+99] Edward M. Marcotte, Matteo Pellegrini, Ho-Leung Ng, Danny W. Rice, Todd O. Yeates, and David Eisenberg.  Detecting protein function and protein-protein interactions from genome sequences.  Science, 285(5428):751–753, 1999.
  * [MU17] Michael Mitzenmacher and Eli Upfal.  Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis.  Cambridge university press, 2017.
  * [NWS02] M. E. J. Newman, D. J. Watts, and S. H. Strogatz.  Random graph models of social networks.  Proc. Natl. Acad. Sci. USA, 99:2566–2572, 2002.
  * [SM00] Jianbo Shi and J. Malik.  Normalized cuts and image segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.
  * [SWZ19] Liangjun Su, Wuyi Wang, and Yichong Zhang.  Strong consistency of spectral clustering for stochastic block models.  IEEE Transactions on Information Theory, 66(1):324–338, 2019.
  * [YWS14] Yi Yu, Tengyao Wang, and Richard J. Samworth.  A useful variant of the Davis–Kahan theorem for statisticians.  Biometrika, 102:315–323, 2014.
  * [ZB18] Yiqiao Zhong and Nicolas Boumal.  Near-optimal bounds for phase synchronization.  SIAM Journal on Optimization, 28(2):989–1016, 2018.
  * [ZT21] Qiaosheng Zhang and Vincent YF Tan.  Exact recovery in the general hypergraph stochastic block model.  arXiv preprint arXiv:2105.04770, 2021.

##  Appendix A Dual certificate

###### Proof of Lemma 2.2.

We first show that $X^{*}=\sigma^{*}{\sigma^{*}}^{\top}$ is an optimal
solution. For any $X$ satisfying the constraints in (2),

$\displaystyle\langle W,X\rangle$ $\displaystyle\leq\langle W,X\rangle+\langle
S,X\rangle$ (since $S,X\succeq 0$ ) $\displaystyle=\langle W,X\rangle+\langle
D+\nu\mathbf{11}^{\top}-W,X\rangle=\langle D,X\rangle$ (since $X$ is primal
feasible) $\displaystyle=\langle D,X^{*}\rangle$ (as $X^{*}_{ii}=X_{ii}=1$ for
all $i\in[n]$) $\displaystyle=\langle
W+S-\nu\mathbf{11}^{\top},X^{*}\rangle=\langle W,X^{*}\rangle+\langle
S,X^{*}\rangle=\langle W,X^{*}\rangle.$ (since $\langle
S,X^{*}\rangle=(\sigma^{*})^{\top}S\sigma^{*}=0$)

Therefore it only remains to establish the uniqueness of $X^{*}$. Consider an
optimal solution $\tilde{X}$. Then

$\displaystyle\langle S,\tilde{X}\rangle$ $\displaystyle=\langle
D+\nu\mathbf{11}^{\top}-W,\tilde{X}\rangle=\langle D-W,\tilde{X}\rangle$
(since $\langle\mathbf{11}^{\top},\tilde{X}\rangle=0$ ) $\displaystyle=\langle
D-W,X^{*}\rangle$ (as $\langle W,X^{*}\rangle=\langle W,\tilde{X}\rangle$ and
$X^{*}_{ii}=\tilde{X}_{ii}=1$) $\displaystyle=\langle S,X^{*}\rangle=0.$
(using $S\sigma^{*}=0$)

Since $\tilde{X}\succeq 0$ and $S\succeq 0$ and $\lambda_{n-1}(S)>0$, we
obtain that $\tilde{X}$ is also a rank-1 matrix and hence it must be a
multiple of $\sigma^{*}{\sigma^{*}}^{\top}$. Moreover, as $\tilde{X}_{ii}=1$
for all $i\in[n]$, it must be that
$\tilde{X}=X^{*}=\sigma^{*}{\sigma^{*}}^{\top}$.

##  Appendix B Spectral norm concentration for similarity matrices

######  Theorem 4 (Spectral norm expectation).

Let $d\in\\{2,3,\dots\\}$ be fixed. Let $p\in[0,1]^{\binom{[n]}{d}}$, where
$\max_{e}p_{e}\leq\nicefrac{{c_{0}\log n}}{{\binom{n-1}{d-1}}}$. Let $G\sim
H(d,n,p)$, and $W=\mathcal{S}(G)$ whose expectation is $W^{*}$. Then there
exists a constant $c\coloneqq c(d,c_{0})>0$ such that

$\operatorname*{{\mathbb{E}}}{[\left\lVert W-W^{*}\right\rVert_{2}]}\leq
c\sqrt{\log n}.$

######  Remark B.1.

By applying Markov’s inequality, we can show that for any function
$f(n)=\omega(1)$,

$\operatorname*{\mathbb{P}}\left(\left\lVert W-W^{*}\right\rVert_{2}\leq
f(n)\sqrt{\log(n)}\right)=1-o(1).$

In order to prove Theorem 4, we require the following result.

######  Lemma B.2.

Let $A$ be a random matrix with independent entries, where $A_{ij}\in[a,b]$
for two constants $a<b$. Suppose $\operatorname*{{\mathbb{E}}}{[|A_{ij}|]}\leq
q$ for all $i,j$, where $\frac{c_{2}\log n}{n}\leq q\leq 1-c_{3}$ for
arbitrary constants $c_{2},c_{3}>0$. Then, there exists a constant
$c^{\prime}\coloneqq c^{\prime}(c_{2},c_{3},a,b)>0$ such that

$\operatorname*{{\mathbb{E}}}{[\left\lVert
A-\operatorname*{{\mathbb{E}}}{[A}]\right\rVert_{2}]}\leq
c^{\prime}\sqrt{nq}.$

###### Proof.

We use ideas from [DGMS22a, Lemma 4.5], who showed a similar result for zero
diagonal, symmetric matrices with independent entries. We first construct a
symmetric matrix $B$ using $A$ to reduce it to the symmetric case. Let

$B=\begin{bmatrix}0&A\\\ A^{\top}&0\end{bmatrix}.$

Fix a vector $x\in\mathbb{R}^{n}$ such that $\left\lVert x\right\rVert_{2}=1$,
and consider the vector $y\in\mathbb{R}^{2n}$ such that
$y=\begin{bmatrix}\mathbf{0}_{n}\\\ x\end{bmatrix}$. Observe that $\left\lVert
y\right\rVert_{2}=1.$ Moreover,

$(B-\operatorname*{{\mathbb{E}}}[B])y=\begin{bmatrix}(A-\operatorname*{{\mathbb{E}}}[A])x\\\
\mathbf{0}_{n}\end{bmatrix}.$

Therefore,

$\left\lVert(B-\operatorname*{{\mathbb{E}}}[B])y\right\rVert_{2}=\left\lVert(A-\operatorname*{{\mathbb{E}}}[A])x\right\rVert_{2},$

so that

$\|(A-\mathbb{E}[A])x\|_{2}=\|(B-\mathbb{E}[B])y\|_{2}\leq\|B-\mathbb{E}[B]\|_{2}.$

Since $x$ was arbitrary, we have shown $\left\lVert
A-\operatorname*{{\mathbb{E}}}{[A]}\right\rVert_{2}\leq\left\lVert
B-\operatorname*{{\mathbb{E}}}{[B]}\right\rVert_{2}$, and therefore

$\operatorname*{{\mathbb{E}}}[\left\lVert
A-\operatorname*{{\mathbb{E}}}{[A]}\right\rVert_{2}]\leq\operatorname*{{\mathbb{E}}}[\left\lVert
B-\operatorname*{{\mathbb{E}}}{[B]}\right\rVert_{2}].$ (28)

Thus, it suffices to bound $\operatorname*{{\mathbb{E}}}[\left\lVert
B-\operatorname*{{\mathbb{E}}}{[B]}\right\rVert_{2}]$. Let
$B^{+}=\max\\{B,0\\}$, where the maximum is taken entrywise. Similarly, let
$B^{-}=-\min\\{B,0\\}$. Then we can write $B=B^{+}-B^{-}$. By the triangle
inequality,

$\mathbb{E}\left[\|B-\mathbb{E}[B]\|_{2}\right]\leq\mathbb{E}\left[\|B^{+}-\mathbb{E}[B^{+}]\|_{2}\right]+\mathbb{E}\left[\|B^{-}-\mathbb{E}[B^{-}]\|_{2}\right].$
(29)

Observe that $B^{+}$ and $B^{-}$ are nonnegative, zero-diagonal, symmetric
matrices with independent entries. Also, for all $i,j$,

$\max\\{\mathbb{E}[B^{+}_{ij}],\mathbb{E}[B^{-}_{ij}]\\}\leq\operatorname*{{\mathbb{E}}}[|B_{ij}|]\leq\max\operatorname*{{\mathbb{E}}}[|A_{ij}|]\leq
q.$

If $b\leq 0$, then $\left\lVert
B^{+}-\operatorname*{{\mathbb{E}}}[B^{+}]\right\rVert_{2}=0$. Otherwise it
follows from [HWX16a, Theorem 5] that there exists $c^{+}>0$ such that

$\mathbb{E}\left[\frac{1}{b}(\|B^{+}-\mathbb{E}[B^{+}]\|_{2})\right]\leq
c^{+}\sqrt{\frac{nq}{b}}.$

Similarly, if $a\geq 0$, then $\left\lVert
B^{-}-\operatorname*{{\mathbb{E}}}[B^{-}]\right\rVert_{2}=0$. Otherwise, we
again use [HWX16a, Theorem 5] to conclude that there exists a constant
$c^{-}>0$ such that

$\mathbb{E}\left[\frac{1}{|a|}(\|B^{-}-\mathbb{E}[B^{-}]\|_{2})\right]\leq
c^{-}\sqrt{\frac{nq}{|a|}}.$

Combining these with (28) and (29) we get

$\operatorname*{{\mathbb{E}}}[\left\lVert
A-\operatorname*{{\mathbb{E}}}{[A]}\right\rVert_{2}]\leq c^{\prime}\sqrt{nq},$

where $c^{\prime}=c^{+}\sqrt{\max\\{b,0\\}}+c^{-}\sqrt{|\min\\{a,0\\}|}$.

###### Proof of Theorem 4.

The symbols $\lesssim$ and $\asymp$ hide constants in $d,c_{0}$ throughout the
proof. Our goal is to bound
$\operatorname*{{\mathbb{E}}}{\left[\left\lVert\mathcal{S}(G)-\operatorname*{{\mathbb{E}}}{[\mathcal{S}(G)]}\right\rVert_{2}\right]}$.
Let $G^{\prime}$ be an independent copy of $G$. Observe that for a fixed
matrix $X$, the function $f(Y)=\|X-Y\|_{2}$ is convex. By Jensen’s inequality,

$\displaystyle\mathbb{E}\left[\|\mathcal{S}(G)-\mathbb{E}[\mathcal{S}(G)]\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\mathcal{S}(G)-\mathbb{E}[\mathcal{S}(G^{\prime})]\|_{2}\right]\leq\mathbb{E}\left[\|\mathcal{S}(G)-\mathcal{S}(G^{\prime})\|_{2}\right].$

We can extend the definition of $\mathcal{S}$ so that
$\mathcal{S}(G-G^{\prime})=\mathcal{S}(G)-\mathcal{S}(G^{\prime})$; i.e.
$G-G^{\prime}$ is a “hypergraph” with edges labeled by $\\{1,0,-1\\}$.

Let $R$ be a symmetric tensor of order $d$ and dimension $n$ with independent
Rademacher entries; i.e. the entries $\\{R(i_{1},i_{2},\dots,i_{d}):i_{1}\leq
i_{2}\leq\cdots\leq i_{d}\\}$ are mutually independent. Let $\circ$ denote the
edge-wise product. Since $G-G^{\prime}$ has the same distribution as
$(G-G^{\prime})\circ R$, we obtain

$\mathbb{E}\left[\|\mathcal{S}(G)-\mathbb{E}[\mathcal{S}(G)]\|_{2}\right]\leq\mathbb{E}\left[\|\mathcal{S}(G-G^{\prime})\|_{2}\right]=\mathbb{E}\left[\|\mathcal{S}((G-G^{\prime})\circ
R)\|_{2}\right]\leq 2\mathbb{E}\left[\|\mathcal{S}(G\circ R)\|_{2}\right],$
(30)

where the last inequality follows from the triangle inequality. Let
$p_{\max}\triangleq c_{0}\log n/\binom{n-1}{d-1}$ for simplicity. Also, we now
consider the hypergraph $G_{+}$ that is coupled to $G$ as follows. Each edge
$e$ that is not present in $G$ is present in $G_{+}$ with probability
$\frac{p_{\max}-p_{e}}{1-p_{e}}$ (independently across edges). Letting
$G^{(1)}\sim\textnormal{HSBM}(d,n,p_{\max},p_{\max})$, we see that
$(G+G_{+})\circ R$ has the same distribution as $G^{(1)}\circ R$. Also,
$\mathbb{E}\left[\mathcal{S}(G_{+}\circ R)~{}|~{}G\right]=0$. Using these
observations along with Jensen’s inequality, we obtain

$\displaystyle\mathbb{E}\left[\|\mathcal{S}(G\circ R)\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\mathcal{S}(G\circ
R)+\mathbb{E}\left[\mathcal{S}(G_{+}\circ
R)~{}|~{}G\right]\|_{2}\right]\leq\mathbb{E}\left[\|\mathcal{S}(G\circ
R)+\mathcal{S}(G_{+}\circ R)\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\mathcal{S}((G+G_{+})\circ
R)\|_{2}\right]=\mathbb{E}\left[\|\mathcal{S}(G^{(1)}\circ R)\|_{2}\right].$

Substituting this into (30), we have

$\mathbb{E}\left[\|\mathcal{S}(G)-\operatorname*{{\mathbb{E}}}{[\mathcal{S}(G)]}\|_{2}\right]\leq
2\mathbb{E}\left[\|S(G^{(1)}\circ R)\|_{2}\right].$ (31)

Let $K=d^{2}-d$ for ease of notation. Let $G^{(m)}$ and $R^{(m)}$ be
independent copies of $G^{(1)}$ and $R$ respectively for $m\in[K]$. Note that
$\operatorname*{{\mathbb{E}}}{[\mathcal{S}(G^{(m)}\circ R^{(m)})]}$ is the
zero matrix. Thus, adding the zero matrix, and then using Jensen’s inequality
we get

$\operatorname*{{\mathbb{E}}}{[\|\mathcal{S}(G^{(1)}\circ
R)\|_{2}]}=\operatorname*{{\mathbb{E}}}{\left[\left\lVert\mathcal{S}(G^{(1)}\circ
R^{(1)})+\sum_{m=2}^{K}\operatorname*{{\mathbb{E}}}{[\mathcal{S}(G^{(m)}\circ
R^{(m)})]}\right\rVert_{2}\right]}\leq\operatorname*{{\mathbb{E}}}\left[\left\lVert\sum_{m=1}^{K}\mathcal{S}(G^{(m)}\circ
R^{(m)})\right\rVert_{2}\right].$ (32)

Observe that $\sum_{m=1}^{K}\mathcal{S}(G^{(m)}\circ R^{(m)})$ is the sum of
_independent_ copies of random matrices with _dependent_ entries. The goal is
to re-express this same quantity as the sum of _dependent_ matrices with fully
_independent_ entries. To this end, let us consider the following
construction.

Observe that the random variable (label) associated with any fixed edge $e$ is
added to exactly $K$ entries of the similarity matrix when we apply the map
$\mathcal{S}(\cdot)$. Let $L(e)$ be a fixed ordered list of such locations.
Formally, $L(e):=(\mathsf{op}^{(1)}_{e},\dots,\mathsf{op}^{(|L(e)|)}_{e})$ is
an ordered list of all ordered pairs of $e$; i.e. $(i,j):i,j\in e$.

For $e\in\mathcal{E}$ and $m,\ell\in[K]$ let $X^{(e,m,\ell)}$ be the $n\times
n$ matrix which has only one non-zero entry:

$\displaystyle X_{ij}^{(e,m,\ell)}$
$\displaystyle=\begin{cases}A^{(m)}_{e}\circ
R^{(m)}_{e}&(i,j)=\mathsf{op}^{(\ell)}_{e}\\\ 0&\text{otherwise},\end{cases}$

where $A_{e}^{(m)}$ denotes the indicator random variable associated with the
edge $e$ in $G^{(m)}$. By construction,

$\sum_{m=1}^{K}\mathcal{S}(G^{(m)}\circ
R^{(m)})=\sum_{m=1}^{K}\sum_{e\in\mathcal{E}}\sum_{\ell=1}^{K}X^{(e,m,\ell)}$
(33)

We will now re-express this summation as the sum of _dependent_ matrices with
_independent_ entries. Let $Y=\sum_{i=1}^{\binom{n-2}{d-2}}X_{i}Z_{i}$, where
$X_{i}\sim\textnormal{Bern}(p_{\max})$ and $Z_{i}\sim\text{Rad}$ are
independent. Let $D$ be a diagonal matrix whose diagonal entries are i.i.d.
copies of $Y$. Let us consider matrices $C^{(1)},\dots,C^{(K)}$, where

$C^{(1)}=\sum_{e\in\mathcal{E}}\sum_{\ell=1}^{K}X^{(e,\ell,\ell)}+D$
$C^{(k)}=\sum_{e\in\mathcal{E}}\sum_{\ell=1}^{K}X^{(e,(\ell+k-1)\%K,\ell)}+(-1)^{k+1}D$

Here $\%$ represents a standard modulo operation, except $K\%K$ is $K$ instead
of $0$. Intuitively, $C^{(1)}$ is the matrix for which the $K$ locations
corresponding to a given edge “consult” $K$ independent copies of $G$. Observe
that all the entries of $C^{(1)}$ are independent copies of $Y$. To ensure
that we add the random variable associated with an edge of any given copy of
$G$ at all $K$ locations in the similarity matrix, we iterate over the list in
a cyclic manner when constructing $C^{(2)},\dots,C^{(K)}$. Note that $D$ has
the same distribution as $-D$. Therefore, from the symmetry all $C^{(k)}$s
have the same distribution. Moreover,

$\displaystyle\sum_{k=1}^{K}C^{(k)}$
$\displaystyle=\sum_{k=1}^{K}\sum_{e\in\mathcal{E}}\sum_{\ell=1}^{K}X^{(e,(\ell+k-1)\%K,\ell)}+(-1)^{k+1}D$
$\displaystyle=\sum_{e\in\mathcal{E}}\sum_{\ell=1}^{K}\sum_{k=1}^{K}X^{(e,(\ell+k-1)\%K,\ell)}+(-1)^{k+1}D$
$\displaystyle=\sum_{e\in\mathcal{E}}\sum_{\ell=1}^{K}\sum_{m=1}^{K}X^{(e,m,\ell)}$
$\displaystyle=\sum_{m=1}^{K}\mathcal{S}(G^{(m)}\circ R^{(m)}),$ (34)

where the last step follows from (33). Therefore, combining (31), (32), and
(34)

$\operatorname*{{\mathbb{E}}}{[\left\lVert W-W^{*}\right\rVert_{2}]}\leq
2\operatorname*{{\mathbb{E}}}{\left[\left\lVert\sum_{k=1}^{K}C^{(k)}\right\rVert_{2}\right]}\leq
2K\operatorname*{{\mathbb{E}}}{[\left\lVert C\right\rVert_{2}]},$ (35)

where $C$ has the same distribution as $C^{(1)}$. Each entry of $C$ is an
independent copy of $Y$. Let $F$ be the event that all the entries of $C$ are
in the range $[-4d,4d]$. By a union bound,

$\displaystyle\operatorname*{\mathbb{P}}\left(F^{\textnormal{c}}\right)$
$\displaystyle\leq\,n^{2}\cdot\operatorname*{\mathbb{P}}\left(|Y|\geq
4d\right)\leq\,n^{2}\cdot\operatorname*{\mathbb{P}}\left(\sum_{i=1}^{\binom{n-2}{d-2}}{X_{i}}\geq
4d\right).$

Since
$\sum_{i=1}^{\binom{n-2}{d-2}}{X_{i}}\sim\textnormal{Bin}\left(\binom{n-2}{d-2},p_{\max}\right)$,
by [MU17, Theorem 4.4, Equation 4.1]

$\operatorname*{\mathbb{P}}\left(F^{\textnormal{c}}\right)\leq
n^{2}\frac{e^{4d}}{\Theta(n/\log n)^{4d}}=O\left(\frac{1}{n^{4d-3}}\right).$

Therefore,

$\displaystyle\operatorname*{{\mathbb{E}}}{[\left\lVert C\right\rVert_{2}]}$
$\displaystyle=\operatorname*{\mathbb{P}}\left(F\right)\operatorname*{{\mathbb{E}}}{[\left\lVert
C\right\rVert_{2}\mid
F]}+\operatorname*{\mathbb{P}}\left(F^{\textnormal{c}}\right)\operatorname*{{\mathbb{E}}}{[\left\lVert
C\right\rVert_{2}\mid F^{\textnormal{c}}]}$
$\displaystyle\leq\operatorname*{{\mathbb{E}}}{[\left\lVert
C\right\rVert_{2}\mid
F]}+O\left(\frac{1}{n^{4d-3}}\right)\operatorname*{{\mathbb{E}}}[\|C\|_{F}\mid
F^{\textnormal{c}}]$
$\displaystyle\leq\operatorname*{{\mathbb{E}}}{[\left\lVert
C\right\rVert_{2}\mid F]}+O\left(\frac{1}{n^{4d-3}}\right)n\binom{n-2}{d-2}$
$\displaystyle=\operatorname*{{\mathbb{E}}}{[\left\lVert C\right\rVert_{2}\mid
F]}+O\left(n^{3-4d+1+d-2}\right)$
$\displaystyle\leq\operatorname*{{\mathbb{E}}}{[\left\lVert
C\right\rVert_{2}\mid F]}+o(1),$ (36)

where the second inequality uses the fact that each entry of $C$ is at most
$\binom{n-2}{d-2}$. Thus, it is only left to show
$\operatorname*{{\mathbb{E}}}{[\left\lVert C\right\rVert_{2}\mid
F]}=O(\sqrt{\log n})$. Note that the entries of $C$ are independent even after
conditioning on $F$. Moreover, the entries are bounded in $[-4d,4d]$. Thus

$\displaystyle\operatorname*{{\mathbb{E}}}{[|C_{ij}|\mid F]}$
$\displaystyle=\sum_{k=1}^{4d}k\cdot\operatorname*{\mathbb{P}}\left(|C_{ij}|=k\mid
F\right)\leq\sum_{k=1}^{4d}k\cdot\frac{\operatorname*{\mathbb{P}}\left(F\cap|C_{ij}|=k\right)}{\operatorname*{\mathbb{P}}\left(F\right)}=\sum_{k=1}^{4d}k\cdot\frac{\operatorname*{\mathbb{P}}\left(|C_{ij}|=k\right)}{1-o(1)}$
$\displaystyle\lesssim\sum_{k=1}^{4d}k\cdot\operatorname*{\mathbb{P}}\left(|C_{ij}|=k\right)\leq\operatorname*{{\mathbb{E}}}{[|C_{ij}|]}\leq\binom{n-2}{d-2}p_{\max}=\frac{\binom{n-2}{d-2}c_{0}\log
n}{\binom{n-1}{d-1}}\lesssim\frac{\log n}{n}.$

Therefore, by Lemma B.2 and the fact that $\operatorname*{{\mathbb{E}}}{[C\mid
F]}$ is the zero matrix, we obtain

$\operatorname*{{\mathbb{E}}}{[\left\lVert C\right\rVert_{2}\mid
F]}=\operatorname*{{\mathbb{E}}}[\left\lVert
C-\operatorname*{{\mathbb{E}}}{[C]}\right\rVert_{2}\mid F]\leq
c^{\prime}\sqrt{n\frac{\log n}{n}}\leq c^{\prime}\sqrt{\log n}.$

Substituting this back in (35) and using (36),

$\operatorname*{{\mathbb{E}}}{[\left\lVert W-W^{*}\right\rVert_{2}]}\leq
2K\operatorname*{{\mathbb{E}}}[\left\lVert C\right\rVert_{2}]\leq
2K\operatorname*{{\mathbb{E}}}[\left\lVert C\right\rVert_{2}\mid F]+o(1)\leq
2Kc^{\prime}\sqrt{\log n}+o(1)\leq c\sqrt{\log n},$

for some $c$ that depends on $d$ and $c_{0}$, concluding the proof.