# Heterogeneous Dense Subhypergraph Detection

Mingao<EMAIL_ADDRESS>[ Zuofeng
<EMAIL_ADDRESS>[ Department of Statistics, North Dakota State
University,  Department of Mathematical Sciences, New Jersey Institute of
Technology,

###### Abstract

We study the problem of testing the existence of a heterogeneous dense
subhypergraph. The null hypothesis corresponds to a heterogeneous Erdös-Rényi
uniform random hypergraph and the alternative hypothesis corresponds to a
heterogeneous uniform random hypergraph that contains a dense subhypergraph.
We establish detection boundaries when the edge probabilities are known and
construct an asymptotically powerful test for distinguishing the hypotheses.
We also construct an adaptive test which does not involve edge probabilities,
and hence, is more practically useful.

62G10,

05C80,05C65,

detection boundary,

heterogeneous uniform hypergraph,

dense subhypergraph,

asymptotically powerful test,

###### keywords:

[class=MSC2020]

###### keywords:

and

##  1 Introduction

Suppose $(\mathcal{V},\mathcal{E})$ is an undirected $m$-uniform hypergraph on
$N:=|\mathcal{V}|$ vertices with an edge set $\mathcal{E}$. Each edge in
$\mathcal{E}$ contains exactly $m$ distinct vertices. Without loss of
generality, assume $\mathcal{V}=[N]:=\\{1,2,\ldots,N\\}$. The adjacency tensor
is an $m$-dimensional 0-1 symmetric array $A\in(\\{0,1\\}^{N})^{\otimes m}$
such that $A_{i_{1}i_{2}\ldots i_{m}}=1$ if and only if
$\\{i_{1},i_{2},\ldots,i_{m}\\}\in\mathcal{E}$. This implies that
$A_{i_{1}i_{2}\ldots i_{m}}=0$ if $\\{i_{1},i_{2},\ldots,i_{m}\\}$ contains
identical indexes, i.e., no self-loops are existent. Symmetry is defined as
$A_{i_{1}i_{2}\ldots i_{m}}=A_{j_{1}j_{2}\ldots j_{m}}$ if
$i_{1},i_{2},\ldots,i_{m}$ is a permutation of $j_{1},j_{2},\ldots,j_{m}$. Let
$p=\\{p_{i_{1}i_{2}\ldots i_{m}}\in[0,1]:1\leq i_{1}<i_{2}<\cdots i_{m}\leq
N\\}$ be a collection of edge-specific probability values. Let
$\mathcal{H}_{m}(N,p)$ denote the Erdös-Rényi $m$-uniform random hypergraph
(see [28] for $m=2$). Equivalently, $A_{i_{1}i_{2}\ldots i_{m}}$, $1\leq
i_{1}<i_{2}<\cdots i_{m}\leq N$, are independent Bernoulli variables with

$\mathbb{P}(A_{i_{1}i_{2}\ldots i_{m}}=1)=p_{i_{1}i_{2}\ldots i_{m}}.$ (1)

For a positive integer $n<N$, a subset $S\subset\mathcal{V}$ with $|S|=n$ and
a scalar $\rho_{S}>1$, let $\mathcal{H}_{m}(N,p;n,\rho_{S})$ denote an
$m$-uniform random hypergraph with a dense subhypergraph $S$. Equivalently,
$A_{i_{1}i_{2}\ldots i_{m}}$, $1\leq i_{1}<i_{2}<\cdots<i_{m}\leq N$, are
independent Bernoulli variables such that

$\mathbb{P}(A_{i_{1}i_{2}\ldots
i_{m}}=1)=\left\\{\begin{array}[]{cc}p_{i_{1}i_{2}\ldots
i_{m}}\rho_{S},&i_{1},i_{2},\ldots,i_{m}\in S,\\\ p_{i_{1}i_{2}\ldots
i_{m}},&\textrm{otherwise}.\end{array}\right.$ (2)

The assumption $\rho_{S}>1$ implies that the vertices within $S$ are more
possibly connected, so $S$ can be viewed as an underlying dense subhypergraph.
Since the Bernoulli probabilities in (1) and (2) are edge-specific, models
$\mathcal{H}_{m}(N,p)$ and $\mathcal{H}_{m}(N,p;n,\rho_{S})$ are both
heterogeneous. Given $A$, we are interested in the following hypothesis
testing problem:

(null hypothesis) $H_{0}$: $A\sim\mathcal{H}_{m}(N,p)$ (alternative
hypothesis) $H_{1}$: there exists an $S\subset\mathcal{V}$ with $|S|=n$ and a
$\rho_{S}>1$ $\displaystyle\textrm{such that
$A\sim\mathcal{H}_{m}(N,p;n,\rho_{S})$}.$

The null hypothesis in (1) says that $A$ follows an Erdös-Rényi $m$-uniform
random hypergraph. The alternative hypothesis says that $A$ follows an
$m$-uniform random hypergraph with an underlying dense subhypergraph. When
$m=2$, [5] derive detection boundaries for testing (1). There is a lack of
literature dealing with (1) for arbitrary $m$ which will be investigated in
this paper.

Given an observed hypergraph with an adjacency tensor $A$, a statistical test
$T$ for testing (1) is a function of $A$ such that $T=1$ if $H_{0}$ is
rejected and $T=0$ otherwise. Define the risk of $T$ as

$\phi_{N}(T)=\mathbb{P}_{0}(T=1)+\max_{|S|=n}\mathbb{P}_{S}(T=0).$

Here $\mathbb{P}_{0}$ and $\mathbb{P}_{S}$ are the probability measures under
$H_{0}$ and $H_{1}$, respectively. If $\phi_{N}(T)\to 0$ (or $\phi_{N}(T)\to
1$), we say that the test $T$ is asymptotically powerful (or asymptotically
powerless). In this paper, we provide conditions under which all tests for (1)
are asymptotically powerless. We also provide conditions under which (1) is
asymptotically distinguishable. As an initial stage, we consider the case of
known $p$ and construct an asymptotically powerful test statistic. We then
move forward to the more realistic unknown $p$ scenario and construct an
adaptive test statistic. Our work is a hypergrahic extension of [5]. There are
rich literature on classic homogeneous sub(hyper)graph detection or testing in
which $p_{i_{1}i_{2}\ldots i_{m}}$ is constant. For instance, [24, 19, 32, 11,
18, 13, 23, 31] proposed various detection algorithms. In stochastic block
models, various algorithms for detecting the underlying communities have been
proposed in [15, 16, 3, 9, 12, 21, 22, 26, 27, 20, 14, 1, 2], and [30]
established sharp boundaries for testing the existence of communities. More
references could be found in the survey paper [6]. Nonetheless, problem (1) is
more challenging than the above homogeneous scenarios due to degree
heterogeneity.

The rest of the paper proceeds as follows. In Section 2, we derive detection
boundaries with all model parameters being known. In Section 3, we construct
an adaptive test to address the unknown edge probabilities. All additional
proofs are deferred to Section 4.

##  2 Detection boundary when $p$ is known

In this section, we derive detection boundaries for testing (1) when $p$ is
known. Assume that $n,N\rightarrow\infty$ and

$\max\limits_{S\subset\mathcal{V},|S|=n}\max\limits_{\\{i_{1},\ldots,i_{m}\\}\subset
S}\rho_{S}^{2}p_{i_{1}i_{2}\ldots i_{m}}=o(1).$ (4)

Condition (4) implies that the hypergraph is suitably sparse. Let
$A_{D}=\sum_{i_{1},\ldots,i_{m}\in D}A_{i_{1}i_{2}\ldots i_{m}}$ which is the
number of edges of the subhypergraph restricted to the vertex set
$D\subset\mathcal{V}$. Under $H_{0}$, the edge rate is
$\mu_{D,m}=\mathbb{E}_{0}[A_{D}]/|D|^{(m)}$ with $|D|^{(m)}:=\binom{|D|}{m}$.
Here $\mathbb{E}_{0}$ is the expectation under $H_{0}$. Denote $x\wedge
y=\min\\{x,y\\}$, $x\vee y=\max\\{x,y\\}$ and $[x]_{+}=\max\\{x,0\\}$. Let

$h(x)=(x+1)\log(x+1)-x,\,\,\,\,\,\,\forall x\in[0,1]$

which is related to the Kullback-Leibler divergence between two Bernoulli
distributions. Consider the following two scenarios regarding
$n,N,m,\mu_{D,m}$.

  * Scenario 1.

There exist $\delta\in(0,0.5)$ and a positive sequence $\gamma_{N}=o(1)$ such
that $n=O(N^{0.5-\delta})$ and

$\max\limits_{S\subset\mathcal{V},|S|=n,}\max\limits_{D\subset
S,|D|<n/(N/n)^{\gamma_{N}}}\frac{|D|^{(m)}N}{N^{(m)}|D|}\frac{\mu_{D,m}}{\mu_{S,m}}\leq\delta,$
(5)
$\max\limits_{S\subset\mathcal{V},|S|=n,}\frac{1}{\mu_{S,m}}=o\left(\frac{n^{m-1}}{\log\frac{N}{n}}\right).$
(6)

  * Scenario 2.

Suppose $\log{n}=o(\log{N})$ and

$\max\limits_{S\subset\mathcal{V},|S|=n}\frac{1}{\mu_{S,m}}=o\left(\frac{\log\frac{N}{n}}{\log
n}\right)=o(1).$ (7)

The two scenarios above impose suitable assumptions on $n,N,m,\mu_{D,m}$. For
instance, (5) says that the ratio of $\mu_{D,m}$ to $\mu_{S,m}$ is well
controlled when $D\subset S$ has small cardinality, i.e., a small $D\subset S$
with large node degrees is nonexistent. Hence, (5) could be considered as a
measure of heterogeneity. Condition (6) or (7) requires the edge density in
the dense subhypergraph being not too small, which implies that the underlying
subhypergraph has enough signal to be detected. The conditions degenerate to
[5] when $m=2$. For $m\geq 3$ and $\mu_{S,m}=\mu_{S,2}$, condition (6) is
weaker than $m=2$. The theorem below provides a circumstance that the
hypotheses in (1) are asymptotically indistinguishable, which is a
generalization of [5] to arbitrary fixed $m\geq 3$. The indistinguishable
regions for $m\geq 3$ and $m=2$ are significantly different and the proof is
technically much more involved.

######  Theorem 2.1.

Under either Scenario I or Scenario II, all tests are asymptotically powerless
if there exists a constant $\epsilon\in(0,1)$ such that

$\max\limits_{\begin{subarray}{c}S\subset\mathcal{V}\\\
|S|=n\end{subarray}}\max\limits_{D\subset
S}\frac{|D|^{(m)}}{|D|}\frac{\mu_{D,m}h(\rho_{S}-1)}{\log\frac{N}{|D|}}\leq
1-\epsilon.$ (8)

Condition (8) is equivalent to that for any $S\subset\mathcal{V}$ with
$|S|=n$,

$h(\rho_{S}-1)\leq\frac{1-\epsilon}{\max\limits_{D\subset
S}\frac{|D|^{(m)}\mu_{D,m}}{|D|\log{\frac{N}{|D|}}}}.$ (9)

Theorem 2.1 says that if $\rho_{S}$ is close to one uniformly for $S$ of
cardinality $n$, then the hypotheses in (1) are indistinguishable. When $m=2$,
(8) degenerates to condition (5) in [5]. To gain more insights about how (8)
varies along with $m$, we suppose $\mu_{D,m}=\mu_{D,2}$ for $m\geq 3$, i.e.,
the edge rates are constant along with $m$. Since $|D|^{(m)}$ increases in
$m$, the RHS of (9) decreases in $m$, i.e., the range of $\rho_{S}$ becomes
smaller. This implies that testing (1) for general $m\geq 3$ becomes easier
than $m=2$. Proof of Theorem 2.1 proceeds by showing that the hypotheses in
(1) are asymptotically mutually contiguous under (8) which requires analyzing
the likelihood ratio statistic.

###### Proof of Theorem 2.1.

For $i_{1}<i_{2}<\cdots<i_{m}$, denote
$\mathbf{i}_{m}=\\{i_{1},\ldots,i_{m}\\}\subset D$ and denote $p_{i_{1}\ldots
i_{m}}$ as $p_{\mathbf{i}_{m}}$. Let
$\theta_{\mathbf{i}_{m}}(q)=\log\frac{q(1-p_{\mathbf{i}_{m}})}{p_{\mathbf{i}_{m}}(1-q)}$
for any $q\in(0,1)$, and
$\Lambda_{\mathbf{i}_{m}}(\theta)=\log(1-p_{\mathbf{i}_{m}}+p_{\mathbf{i}_{m}}e^{\theta})$.
Let $H_{p}(q)$ be the Kullback-Leibler divergence from $\text{Bern}(q)$ to
$\text{Bern}(p)$ defined as
$H_{p}(q)=q\log\frac{q}{p}+(1-q)\log\frac{1-q}{1-p}$, for $p,q\in(0,1)$. For a
given subset $S\subset[N]$ with $|S|=n$, the likelihood ratio statistics based
on (1) is equal to

$\displaystyle L_{S}$ $\displaystyle=$
$\displaystyle\frac{\prod_{\begin{subarray}{c}i_{1}<\cdots<i_{m}\\\
\mathbf{i}_{m}\in
S\end{subarray}}(\rho_{S}p_{\mathbf{i}_{m}})^{A_{\mathbf{i}_{m}}}(1-\rho_{S}p_{\mathbf{i}_{m}})^{1-A_{\mathbf{i}_{m}}}}{\prod_{\begin{subarray}{c}i_{1}<\cdots<i_{m}\\\
\mathbf{i}_{m}\in
S\end{subarray}}(p_{\mathbf{i}_{m}})^{A_{\mathbf{i}_{m}}}(1-p_{\mathbf{i}_{m}})^{1-A_{\mathbf{i}_{m}}}}=\exp\left\\{\sum_{\mathbf{i}_{m}\in
S}\left[A_{\mathbf{i}_{m}}\theta_{\mathbf{i}_{m}}(\rho_{S}p_{\mathbf{i}_{m}})-\Lambda_{\mathbf{i}_{m}}(\theta_{\mathbf{i}_{m}}(\rho_{S}p_{\mathbf{i}_{m}}))\right]\right\\}.$

Then it’s easy to express the unconditional likelihood ratio statistic as
$L=\binom{N}{n}^{-1}\sum_{|S|=n}L_{S}$. We adopt the likelihood ratio
truncation skill used in [4, 7] to get
$\tilde{L}=\binom{N}{n}^{-1}\sum_{|S|=n}L_{S}I_{\Gamma_{S}}$, where $I_{E}$ is
an indicator function for event $E$ and

$\Gamma_{S}=\left\\{\sum_{\mathbf{i}_{m}\in
D}A_{\mathbf{i}_{m}}\theta_{\mathbf{i}_{m}}(\rho_{S}p_{\mathbf{i}_{m}})\leq\sum_{\mathbf{i}_{m}\in
D}\zeta_{D}\theta_{\mathbf{i}_{m}}(\rho_{S}p_{\mathbf{i}_{m}}),\ all\ D\in
E_{S}\right\\},$

with $\zeta_{D}$ provided in Lemma 4.1. We will proceed by showing
$\mathbb{E}_{0}\tilde{L}=1+o(1)$ and $\mathbb{E}_{0}\tilde{L}^{2}\leq 1+o(1)$,
where $\mathbb{E}_{0}$ denotes expectation under $H_{0}$.

We begin with the first-order moment. It is easy to verify
$\mathbb{E}_{0}\tilde{L}=\mathbb{P}_{S}\Gamma_{S}$. Note that
$\theta_{\mathbf{i}_{m}}(\rho_{S}p_{\mathbf{i}_{m}})\sim\log\rho_{S}$
uniformly for all $\mathbf{i}_{m}\in S$ with $|S|=n$ by a similar proof of
equation (54) in [5]. By Bennett’s inequality, it follows that

$\displaystyle 1-\mathbb{P}_{S}\Gamma_{S}=\mathbb{P}_{S}\Gamma_{S}^{c}$
$\displaystyle\leq$ $\displaystyle\sum_{D\in
E_{S}}\mathbb{P}\left(\sum_{\mathbf{i}_{m}\in
D}A_{\mathbf{i}_{m}}>\zeta_{D}\sum_{\mathbf{i}_{m}\in
D}p_{\mathbf{i}_{m}}\right)\leq\sum_{D\in
E_{S}}\exp\left(-\rho_{S}\sum_{\mathbf{i}_{m}\in
D}p_{\mathbf{i}_{m}}h\left(\frac{\zeta_{D}}{\rho_{S}}-1\right)\right).$

By Lemma 4.2, we get

$\displaystyle 1-\min_{S\subset\mathcal{V},|S|=n}\mathbb{P}_{S}\Gamma_{S}$
$\displaystyle\leq$ $\displaystyle\max_{S\subset\mathcal{V},|S|=n}\sum_{D\in
E_{S}}\exp\left(-\rho_{S}\sum_{\mathbf{i}_{m}\in
D}p_{\mathbf{i}_{m}}h\left(\frac{\zeta_{D}}{\rho_{S}}-1\right)\right)$
$\displaystyle\leq$
$\displaystyle\max_{S\subset\mathcal{V},|S|=n}\sum_{k=m}^{n}\binom{N}{n}\exp\left(-\rho_{S}\sum_{\mathbf{i}_{m}\in
D}p_{\mathbf{i}_{m}}h\left(\frac{\zeta_{D}}{\rho_{S}}-1\right)\right)$
$\displaystyle\leq$
$\displaystyle\max_{S\subset\mathcal{V},|S|=n}\sum_{k=m}^{n}\exp\left(k\log\frac{ne}{k}-\rho_{S}\sum_{\mathbf{i}_{m}\in
D}p_{\mathbf{i}_{m}}h\left(\frac{\zeta_{D}}{\rho_{S}}-1\right)\right)$
$\displaystyle\leq$ $\displaystyle\sum_{k=m}^{n}e^{-k(c_{n}-1)}=o(1).$

Hence, $\mathbb{E}_{0}\tilde{L}=1+o(1)$.

We next consider the second-order moment. For $S_{1},S_{2}\subset\mathcal{V}$
with $|S_{1}|=|S_{2}|=n$, let $D=S_{1}\cap S_{2}$. Clearly, we have the
following

$\displaystyle\mathbb{E}_{0}\tilde{L}^{2}$ $\displaystyle=$
$\displaystyle\binom{N}{n}^{-2}\sum_{|S_{1}|=n,|S_{2}|=n}\mathbb{E}_{0}L_{S_{1}}I_{\Gamma_{S_{1}}}L_{S_{2}}I_{\Gamma_{S_{2}}}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{0}\left(I_{\Gamma_{S_{1}}}I_{\Gamma_{S_{2}}}\exp\left(\sum_{i_{m}\in
D}A_{\mathbf{i}_{m}}[\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}})+\theta_{\mathbf{i}_{m}}(\rho_{S_{2}}p_{\mathbf{i}_{m}})]-\Lambda_{\mathbf{i}_{m}}(\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}}))-\Lambda_{\mathbf{i}_{m}}(\theta_{\mathbf{i}_{m}}(\rho_{S_{2}}p_{\mathbf{i}_{m}}))\right)\right)$
$\displaystyle\leq$ $\displaystyle\mathbb{E}\left[I_{D\in
E_{S_{1}}}\mathbb{E}_{0}\left(I_{\Gamma_{S_{1}}}\exp\left(\sum_{\mathbf{i}_{m}\in
D}2A_{\mathbf{i}_{m}}[\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}})-2\Lambda_{\mathbf{i}_{m}}(\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}}))\right)\right)\right]$
$\displaystyle+\mathbb{E}\left[I_{D\not\in
E_{S_{1}}}\mathbb{E}_{0}\left(I_{\Gamma_{S_{1}}}\exp\left(\sum_{\mathbf{i}_{m}\in
D}2A_{\mathbf{i}_{m}}[\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}})-2\Lambda_{\mathbf{i}_{m}}(\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}}))\right)\right)\right]$
$\displaystyle=$ $\displaystyle R_{1}+R_{2}.$

We shall show $R_{1}=o(1)$ and $R_{2}\leq 1+o(1)$. Since
$p_{\mathbf{i}_{m}}=o(1)$, we have

$\Delta_{\mathbf{i}_{m}}^{(1)}:=\log\left(1+\frac{p_{\mathbf{i}_{m}}(\rho_{S_{1}}-1)^{2}}{1-p_{\mathbf{i}_{m}}}\right)\leq
p_{\mathbf{i}_{m}}(\rho_{S_{1}}-1)^{2}.$

Besides,

$\mathbb{P}(|D|=k)\leq\exp\left(-k\left(\log\frac{Nk}{n^{2}}+O(1)\right)\right).$

Consequently, by the definition of $E_{S_{1}}$ one has

$\displaystyle R_{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[I_{D\not\in
E_{S_{1}}}\exp\left(\sum_{\mathbf{i}_{m}\in
D}\Delta_{\mathbf{i}_{m}}^{(1)}\right)\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[I_{D\not\in
E_{S_{1}}}\exp\left((1-\frac{\epsilon}{2})|D|\left(\log\frac{N|D|}{n^{2}}-\log\log\frac{N}{n}\right)\right)\right]$
$\displaystyle\leq$ $\displaystyle
1+\sum_{k=m}^{n}\exp\left(k\left(\log\frac{Nk}{n^{2}}-\log\log\frac{N}{n}\right)-k\left(\log\frac{Nk}{n^{2}}+O(1)\right)\right)=1+o(1).$

Note that
$\frac{\log\zeta_{D}}{\log\rho_{S_{1}}}\sim\frac{\theta_{\mathbf{i}_{m}}(\zeta_{D}p_{\mathbf{i}_{m}})}{\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}})}$
uniformly for $\mathbf{i}_{m}\in D$, $D\in E_{S_{1}}$ and $|S_{1}|=n$. For any
$x\in[0,1]$ and $D\in E_{S_{1}}$, we have

$\displaystyle R_{1}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[I_{D\in
E_{S_{1}}}\mathbb{E}_{0}\left(\exp\left(\sum_{\mathbf{i}_{m}\in
D}2\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}})\left(xA_{\mathbf{i}_{m}}+(1-x)\zeta_{D}p_{\mathbf{i}_{m}}\right)-2\Lambda_{\mathbf{i}_{m}}(\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}}))\right)\right)\right],$

which is minimized at
$x=\frac{\theta_{\mathbf{i}_{m}}(\zeta_{D}p_{\mathbf{i}_{m}})}{2\theta_{\mathbf{i}_{m}}(\rho_{S_{1}}p_{\mathbf{i}_{m}})}\sim\frac{\log\zeta_{D}}{2\log\rho_{S_{1}}}$
by (50) in [5]. Plugging this into the above equation yields

$\displaystyle R_{1}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[I_{D\in
E_{S_{1}}}\mathbb{E}_{0}\exp\left(\sum_{\mathbf{i}_{m}\in
D}\Delta_{\mathbf{i}_{m}}^{(2)}\right)\right]\leq\sum_{k=m}^{n}\exp\left(k(-2c_{n}+O(1))\right)=o(1),$

where
$\Delta_{\mathbf{i}_{m}}^{(2)}=H_{p_{\mathbf{i}_{m}}}(\zeta_{D}p_{\mathbf{i}_{m}})-2H_{\rho_{S_{1}}p_{\mathbf{i}_{m}}}(\zeta_{D}p_{\mathbf{i}_{m}})$,
the second inequality follows from the proof of Theorem 1 in [5] and the last
step follows from Lemma 4.2. Then the proof is complete. ∎

Next, we shall show that the condition (8) in Theorem 2.1 is also necessary
for indistinguishability. Define the hypergraphic scan statistic as

$T_{n}=\max\limits_{D\subset\mathcal{V},|D|\leq
n}T_{D},\,\,\,\,\text{where}\,\,\,\,T_{D}=\frac{|D|^{(m)}}{|D|}\cdot\frac{\mu_{D,m}h\left([\frac{A_{D}}{\mathbb{E}_{0}[A_{D}]}-1]_{+}\right)}{\log\frac{N}{|D|}}.$
(10)

In the above, $\mathbb{E}_{0}[A_{D}]=\sum_{\textbf{i}_{m}\in
D}p_{\textbf{i}_{m}}$ which is available given that $p$ is known. For any
$S\subset\mathcal{V}$ with $|S|=n$, let

$D^{*}_{S}=\operatorname*{arg\,max}_{D\subset
S}\frac{|D|^{(m)}}{|D|}\cdot\frac{\mu_{D,m}}{\log\frac{N}{|D|}}.$

######  Theorem 2.2.

Suppose $n=o(N)$ and $\rho_{S}\mathbb{E}_{0}[A_{D^{*}_{S}}]\rightarrow\infty$.
The scan test $T_{n}$ is asymptotically powerful if there exists a constant
$\epsilon\in(0,1)$ such that

$\min\limits_{\begin{subarray}{c}S\subset\mathcal{V}\\\
|S|=n\end{subarray}}\max\limits_{D\subset
S}\frac{|D|^{(m)}}{|D|}\cdot\frac{\mu_{D,m}h(\rho_{S}-1)}{\log\frac{N}{|D|}}\geq
1+\epsilon.$ (11)

Theorem 2.2 can be proved similarly as Theorem 2 in [5]. Specifically, it
applies the Bennett’s inequality to show that the $\gamma_{N}$-risk of the
scan test $T_{n}$ tends to zero. Theorems 2.1 and 2.2 together depict a
detection boundary for testing (1).

##  3 An adaptive test

In practice, $p$ is often unknown so the test statistic $T_{n}$ may not be
applicable. Instead, we will propose a new test which is adaptive to the value
of $p$. This problem is challenging since $p$ contains $N^{(m)}$ unknown
parameters and estimation of these large amount of parameters seems
infeasible. To reduce the amount of overparametrization, consider a special
case that $p_{i_{1}\ldots i_{m}}=\prod_{k=1}^{m}W_{i_{k}}$ for an unknown
vector $W=(W_{1},\ldots,W_{N})$ with $W_{i}\in[0,1]$. When $m=2$, this is just
the rank-1 model studied in [5]. Moreover, assume that

$\left(\frac{W_{max}}{W_{min}}\right)^{m}=o\left(n^{\frac{m}{m+1}}\wedge\left[W_{min}^{m}\left(\frac{N}{n}\right)^{m-1-\delta_{m}}\right]\right),$
(12)

where $\delta_{m}=0$ for even $m$ and $\delta_{m}\in(0,1)$ for odd $m$,
$W_{max}=\max\left\\{W_{1},\ldots,W_{N}\right\\}$ and
$W_{min}=\min\\{W_{1},\ldots,W_{N}\\}$. Note that the RHS of (12) converges to
zero faster when $m$ is even. Condition (12) accommodates heterogeneity in the
hypergraph. To see this, consider $n=\sqrt{N}$ and
$W_{i}=\left(\frac{i}{N}\right)^{\frac{1}{k(m+1)}}$ in which $k\geq 4$ is a
constant. Since $\sum_{i=1}^{N}W_{i}\asymp\frac{k(m+1)}{k(m+1)+1}N$, it is
easy to verify that the average degree of node $N$ (of order $N^{m-1}$) is
approximately $N^{\frac{1}{k(m+1)}}$ times of the average degree of node 1 (of
order $N^{m-1-\frac{1}{k(m+1)}}$).

When the edge probability $p$ is unknown, we need to modify the scan test.
Essentially, we have to estimate $\mathbb{E}_{0}[A_{D}]$ for any subset
$D\subset\mathcal{V}$ by $\widehat{p}_{D,m}$ defined as follows:

$\widehat{p}_{D,m}=\frac{1}{2^{m}}\left(A_{\mathcal{V}}^{\frac{1}{m}}-\left(A_{\mathcal{V}}-2A_{D,D^{c}}\right)^{\frac{1}{m}}\right)^{m},$

where

$A_{D,D^{c}}=\frac{1}{m!}\sum_{k=1}^{t_{m}}\binom{m}{2k-1}\sum_{\begin{subarray}{c}\\{i_{1},\ldots,i_{2k-1}\\}\subset
D^{c}\\\ \\{i_{2k},\ldots,i_{m}\\}\subset D\end{subarray}}A_{i_{1}\ldots
i_{m}},$

$t_{m}=\frac{m}{2}$ for even $m$, and $t_{m}=\frac{m+1}{2}$ for odd $m$, and
$D^{c}=\mathcal{V}-D$. Define

$\widehat{p}_{D,m}^{*}=\widehat{p}_{D,m}\vee\frac{|D|^{m}}{N^{m-1}}\log^{2m}\frac{N}{|D|}.$

We then propose the following modified scan test statistic:

$\widehat{T}_{n}=\max\limits_{D\subset\mathcal{V},|D|\leq n}\widehat{T}_{D},\
\ \ \
\widehat{T}_{D}=\frac{\widehat{p}_{D,m}^{*}h\left([\frac{A_{D}}{\widehat{p}_{D,m}^{*}}-1]_{+}\right)}{|D|\log\frac{N}{|D|}}.$
(13)

Note that $\widehat{T}_{n}$ does not involve $p$ and hence is adaptive.
Theorem 3.1 shows that $\widehat{T}_{n}$ is asymptotically powerful under the
condition (11).

######  Theorem 3.1.

Suppose $n=o(N)$ and $\rho_{S}\mathbb{E}_{0}[A_{D^{*}_{S}}]\rightarrow\infty$.
If (11) holds, then the modified scan test $\widehat{T}_{n}$ is asymptotically
powerful.

Based on Theorem 3.1, the modified scan test $\widehat{T}_{n}$ still can
achieve the detection boundary in Theorem 2.2. Moreover, the rate
$n^{\frac{m}{m+1}}$ is optimal under Scenario I and Scenario 2 and it can’t be
improved.

The main ingredient in the proof of Theorem 3.1 is to show that
$\widehat{p}_{D,m}$ can accurately estimate $\mathbb{E}_{0}[A_{D}]$, hence,
$\widehat{T}_{n}$ will perform similarly as $T_{n}$. Before proving Theorem
3.1, let us provide a quick sketch on the estimation accuracy of
$\widehat{p}_{D,m}$. Under assumption (12), it can be shown that for any
$D\subset\mathcal{V}$, $\sum_{i\in\mathcal{V}-D}W_{i}-\sum_{i\in D}W_{i}$ is
non-negative for large $N$. Therefore, we have

$\displaystyle 2\sum_{i\in D}W_{i}$ $\displaystyle=$
$\displaystyle\sum_{i\in\mathcal{V}}W_{i}-\left(\sum_{i\in\mathcal{V}-D}W_{i}-\sum_{i\in
D}W_{i}\right)=\left[\left(\sum_{i\in\mathcal{V}}W_{i}\right)^{m}\right]^{\frac{1}{m}}-\left[\left(\sum_{i\in\mathcal{V}-D}W_{i}-\sum_{i\in
D}W_{i}\right)^{m}\right]^{\frac{1}{m}}.$

Note that

$\left(\sum_{i\in\mathcal{V}}W_{i}\right)^{m}=m!\mathbb{E}_{0}A_{\mathcal{V}}+\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\
\\{i_{1},\ldots,i_{m}\\}\subset\mathcal{V}\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}}$

and, by binomial formula,

$\displaystyle\left(\sum_{i\in\mathcal{V}-D}W_{i}-\sum_{i\in
D}W_{i}\right)^{m}$ $\displaystyle=$
$\displaystyle\left(\sum_{i\in\mathcal{V}-D}W_{i}+\sum_{i\in
D}W_{i}\right)^{m}-2\sum_{k=1}^{t_{m}}\binom{m}{2k-1}\left(\sum_{i\in\mathcal{V}-D}W_{i}\right)^{2k-1}\left(\sum_{i\in
D}W_{i}\right)^{m-2k+1}$ $\displaystyle=$ $\displaystyle
m!\mathbb{E}_{0}A_{\mathcal{V}}+\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\
\\{i_{1},\ldots,i_{m}\\}\subset\mathcal{V}\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}}-2\sum_{k=1}^{t_{m}}\binom{m}{2k-1}\left(\sum_{i\in\mathcal{V}-D}W_{i}\right)^{2k-1}\left(\sum_{i\in
D}W_{i}\right)^{m-2k+1}.$

By law of large number, it can be shown that
$A_{\mathcal{V}}=(1+o_{P}(1))\mathbb{E}_{0}[A_{\mathcal{V}}]$, and for any
$D\subset\mathcal{V}$, $A_{D,D^{c}}=(1+o_{P}(1))\mathbb{E}_{0}[A_{D,D^{c}}]$.
By assumption (12), it can be shown that, for any $D\subset\mathcal{V}$,

$\mathbb{E}_{0}[A_{D}]\gg\frac{1}{m!}\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\ \\{i_{1},\ldots,i_{m}\\}\subset D\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}},$

which leads to that

$\displaystyle\left(\sum_{i\in\mathcal{V}}W_{i}\right)^{m}$ $\displaystyle=$
$\displaystyle(1+o_{P}(1))m!A_{\mathcal{V}},$
$\displaystyle\left(\sum_{i\in\mathcal{V}-D}W_{i}-\sum_{i\in
D}W_{i}\right)^{m}$ $\displaystyle=$
$\displaystyle(1+o_{P}(1))m!A_{\mathcal{V}}-2(1+o_{P}(1))m!A_{D,D^{c}}.$

Hence, we get

$\displaystyle\mathbb{E}_{0}[A_{D}]$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}i_{1}<i_{2}<\cdots<i_{m}\\\
\\{i_{1},\ldots,i_{m}\\}\subset D\end{subarray}}W_{i_{1}}\cdots W_{i_{m}}$
(14) $\displaystyle=$ $\displaystyle\frac{1}{2^{m}m!}\left(2\sum_{i\in
D}W_{i}\right)^{m}-\frac{1}{m!}\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\ \\{i_{1},\ldots,i_{m}\\}\subset D\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}}$ $\displaystyle=$
$\displaystyle\frac{1+o_{P}(1)}{2^{m}}\left(A_{\mathcal{V}}^{\frac{1}{m}}-(A_{\mathcal{V}}-2A_{D,D^{c}})^{\frac{1}{m}}\right)^{m}-o(\mathbb{E}_{0}[A_{\mathcal{D}}])$
$\displaystyle=$
$\displaystyle(1+o_{P}(1))\widehat{p}_{D,m}-o(\mathbb{E}_{0}[A_{\mathcal{D}}]).$

Therefore, $(1+o_{P}(1))\widehat{p}_{D,m}=(1+o_{P}(1))\mathbb{E}_{0}[A_{D}]$,
i.e., $\widehat{p}_{D,m}$ is proven a good estimator of
$\mathbb{E}_{0}[A_{D}]$.

###### Proof of Theorem 3.1.

Firstly, we control the type I error. Note that for $a\geq b$,
$ah\left(\left[\frac{x}{a}-1\right]_{+}\right)\leq
bh\left(\left[\frac{x}{b}-1\right]_{+}\right)$. We only need to prove

$\max\limits_{n^{\frac{1}{m+1}}\leq|D|\leq
n}\frac{\mathbb{E}_{0}[A_{D}]}{\widehat{p}_{D,m}^{*}}\leq 1+o_{p}(1).$ (15)

Define $\mathcal{D}=\left\\{D\subset\mathcal{V}:n^{\frac{1}{m+1}}\leq|D|\leq
n,\widehat{p}_{D,m}^{*}\leq\mathbb{E}_{0}[A_{D}]\right\\}$. It suffices to
prove (15) for $D\in\mathcal{D}$. By the definition of
$\widehat{p}_{D,m}^{*}$, we have

$\frac{|D|^{m}}{N^{m-1}}\log^{2m}\frac{N}{|D|}\leq\widehat{p}_{D,m}^{*}\leq\mathbb{E}_{0}[A_{D}]\leq\left(\sum_{i\in
D}W_{i}\right)^{m},$

which implies $\sum_{i\in
D}W_{i}\geq\frac{|D|}{N^{\frac{m-1}{m}}}\log^{2}\frac{N}{|D|}$. Besides, by
assumption (12), we have $W_{min}\geq\frac{1}{N^{\frac{m-1-\delta_{m}}{m}}}$.
Hence,

$\displaystyle\mathbb{E}_{0}[A_{D,D^{c}}]$ $\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{k=1}^{t_{m}}\binom{m}{2k-1}\left(\sum_{i\in\mathcal{V}-D}W_{i}\right)^{2k-1}\left(\sum_{i\in
D}W_{i}\right)^{m-2k+1}$ (16) $\displaystyle\geq$
$\displaystyle\frac{1}{m!}\sum_{k=1}^{t_{m}}\binom{m}{2k-1}(N-|D|)^{2k-1}W_{min}^{2k-1}\left(\sum_{i\in
D}W_{i}\right)^{m-2k+1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{m!}\sum_{k=1}^{t_{m}}\binom{m}{2k-1}\frac{(N-|D|)^{2k-1}}{N^{\frac{m-1-\delta_{m}}{m}(2k-1)}}\frac{\left(|D|\log^{2}\frac{N}{|D|}\right)^{m-2k+1}}{N^{\frac{m-1}{m}(m-2k+1)}}.$

For even $m$ and a constant $c_{1}>0$, using the last term $k=\frac{m}{2}$ in
(16), we have

$\mathbb{E}_{0}[A_{D,D^{c}}]\geq c_{1}|D|\log^{2}\frac{N}{|D|}.$

For odd $m$ and a constant $c_{2}>0$, using the last term $k=\frac{m+1}{2}$ in
(16), we have

$\mathbb{E}_{0}[A_{D,D^{c}}]\geq c_{2}N^{1+\delta_{m}}\geq
c_{2}|D|\log^{2}\frac{N}{|D|}.$

Take $c=\min\\{c_{1},c_{2}\\}$. For a constant $c_{0}>0$, by Bennett’s
inequality we get

$\displaystyle\mathbb{P}\left(\min_{D\in\mathcal{D}}A_{D,D^{c}}-\mathbb{E}_{0}[A_{D,\bar{D}}]\leq-\sqrt{2c\left(\frac{1}{c}+c_{0}\right)\mathbb{E}_{0}[A_{D,D^{c}}]|D|\log\frac{N}{|D|}}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=m}^{n}\sum_{|D|=k}\exp\left(-\mathbb{E}_{0}[A_{D,D^{c}}]h\left(\sqrt{\frac{2c\left(\frac{1}{c}+c_{0}\right)|D|\log\frac{N}{|D|}}{\mathbb{E}_{0}[A_{D,D^{c}}]}}\right)\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=m}^{n}\sum_{|D|=k}\exp\left(-c\left(\frac{1}{c}+c_{0}\right)|D|\log\frac{N}{|D|}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=m}^{n}\exp\left(k\log\frac{Ne}{n}\right)\exp\left(-c\left(\frac{1}{c}+c_{0}\right)k\log\frac{N}{k}\right)=o(1).$

Here, we used the fact that $h(x)\sim\frac{x^{2}}{2}$ for $x=o(1)$.
Consequently, we have

$A_{D,D^{c}}=(1+o_{p}(1))\mathbb{E}_{0}[A_{D,D^{c}}],$

uniformly for $D\in\mathcal{D}$. Obviously,

$A_{\mathcal{V}}=(1+o_{P}(1))\mathbb{E}_{0}[A_{\mathcal{V}}].$

By Lemma 4.6, we obtain

$\frac{\widehat{p}_{D,m}^{*}}{\mathbb{E}_{0}[A_{\mathcal{V}}]}\geq\frac{\widehat{p}_{D,m}}{\mathbb{E}_{0}[A_{\mathcal{V}}]}=1+o_{p}(1).$

Then by the proof of Theorem 2.2, the type I error goes to zero.

Next, we control type II error. Obviously, we have

$A_{D^{*},D^{*c}}=(1+o_{p}(1))\mathbb{E}_{1}[A_{D^{*},D^{*c}}],\ \ \ \
A_{\mathcal{V}}=(1+o_{P}(1))\mathbb{E}_{1}[A_{\mathcal{V}}].$

By assumption (12), since $\rho_{S}W_{min}^{m}\leq 1$, then
$\rho_{S}\ll\left(\frac{W_{min}}{W_{max}}\right)^{m}\left(\frac{N}{n}\right)^{m-1-\delta_{m}}$.
Then

$\displaystyle
1\leq\frac{\mathbb{E}_{1}[A_{D^{*},D^{*c}}]}{\mathbb{E}_{0}[A_{D^{*},D^{*c}}]}\leq
1+\frac{\mathbb{E}_{1}[A_{D^{*},C-D^{*}}]}{\mathbb{E}_{0}[A_{D^{*},D^{*c}}]}=1+\rho_{S}\frac{\mathbb{E}_{0}[A_{D^{*},C-D^{*}}]}{\mathbb{E}_{0}[A_{D^{*},D^{*c}}]}.$

For even $m$, we have

$\displaystyle\rho_{S}\frac{\mathbb{E}_{0}[A_{D^{*},C-D^{*}}]}{\mathbb{E}_{0}[A_{D^{*},D^{*c}}]}=O\left(\rho_{S}\frac{|D^{*}|(n-|D^{*}|)^{m-1}\vee|D^{*}|^{m}}{|D^{*}|(N-|D^{*}|)^{m-1}}\frac{W_{max}^{m}}{W_{min}^{m}}\right)=o(1).$

For odd $m$, we have

$\displaystyle\rho_{S}\frac{\mathbb{E}_{1}[A_{D^{*},C-D^{*}}]}{\mathbb{E}_{0}[A_{D^{*},D^{*c}}]}=O\left(\rho_{S}\frac{(n-|D^{*}|)^{m}\vee|D^{*}|^{m}}{(N-|D^{*}|)^{m}}\frac{W_{max}^{m}}{W_{min}^{m}}\right)=o(1).$

Hence,
$\mathbb{E}_{1}[A_{D^{*},D^{*c}}]=(1+o(1))\mathbb{E}_{0}[A_{D^{*},D^{*c}}]$.
Similarly we can get
$\mathbb{E}_{1}[A_{\mathcal{V}}]=(1+o(1))\mathbb{E}_{0}[A_{\mathcal{V}}]$.
Consequently, we have

$A_{D^{*},D^{*c}}=(1+o_{p}(1))\mathbb{E}_{0}[A_{D^{*},D^{*c}}],\ \ \ \
A_{\mathcal{V}}=(1+o_{P}(1))\mathbb{E}_{0}[A_{\mathcal{V}}].$

By Lemma 4.6, one has
$\widehat{p}_{D^{*},m}=(1+o_{p}(1))\mathbb{E}_{0}[A_{D^{*}}]$. Hence,

$\widehat{p}_{D^{*},m}^{*}=(1+o_{p}(1))\mathbb{E}_{0}[A_{D^{*}}]\vee\frac{|D^{*}|^{m}}{N^{m-1}}\log^{2m}\frac{N}{|D^{*}|}.$

If $\widehat{p}_{D^{*},m}^{*}=(1+o_{p}(1))\mathbb{E}_{0}[A_{D^{*}}]$, the
proof is the same as Theorem 2.2.

Next, we assume
$\widehat{p}_{D^{*},m}^{*}=\frac{|D^{*}|^{m}}{N^{m-1}}\log^{2m}\frac{N}{|D^{*}|}>\mathbb{E}_{0}[A_{D^{*}}]$.
Note that $h^{-1}(x)\geq\sqrt{x}$. Then condition (LABEL:cond:4) implies that

$\rho_{S}>\sqrt{\frac{N^{m-1}}{|D^{*}|^{m-1}}\frac{1}{\log^{2m-1}\frac{N}{|D^{*}|}}}.$

Recall that $W_{min}\geq\frac{1}{N^{\frac{m-1-\delta_{m}}{m}}}$. Hence,

$\frac{\mathbb{E}_{1}[A_{D^{*}}]}{\widehat{p}_{D^{*},m}^{*}}\geq\frac{\rho_{S}|D^{*}|^{m}W_{min}^{m}}{\frac{|D^{*}|^{m}}{N^{m-1}}\log^{2m}\frac{N}{|D^{*}|}}\geq\frac{\rho_{S}}{\log^{2m}\frac{N}{|D^{*}|}}\rightarrow\infty.$

Since $A_{D^{*}}=(1+o_{P}(1))\mathbb{E}_{1}[A_{D^{*}}]$ and $h(x-1)\sim x\log
x$ for $x\rightarrow\infty$, we have

$\displaystyle\widehat{p}_{D^{*},m}^{*}h\left(\left[\frac{A_{D^{*}}}{\widehat{p}_{D^{*},m}^{*}}-1\right]_{+}\right)$
$\displaystyle\geq$
$\displaystyle\widehat{p}_{D^{*},m}^{*}h\left(\left[\frac{\mathbb{E}_{1}[A_{D^{*}}]}{\widehat{p}_{D^{*},m}^{*}}-1\right]_{+}\right)$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{1}[A_{D^{*}}]\log\frac{\mathbb{E}_{1}[A_{D^{*}}]}{\widehat{p}_{D^{*},m}^{*}}$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{1}[A_{D^{*}}]\log\frac{\rho_{S}}{\log^{2m}\frac{N}{|D^{*}|}}$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{1}[A_{D^{*}}]\log\rho_{S}=\mathbb{E}_{0}[A_{D^{*}}]h(\rho_{S}-1)$
$\displaystyle\geq$ $\displaystyle(1+\epsilon)|D^{*}|\log\frac{N}{|D^{*}|}.$

Proof is complete. ∎

##  4 Proof of additional lemmas

In this section, we prove the lemmas. For a subset $S\subset\mathcal{V}$,
define

$E_{S}=\left\\{D\subset
S:(\rho_{S}-1)^{2}\mathbb{E}_{0}[A_{D}]>\left(1-\frac{\epsilon}{2}\right)|D|\left(\log\frac{N|D|}{n^{2}}-\log\log\frac{N}{n}\right)\right\\}.$

The following preliminary lemmas can be found in [5].

######  Lemma 4.1.

Under the conditions of Theorem 2.1, for any $S\subset\mathcal{V}$ with
$|S|=n$ and $D\in E_{S}$, there is an unique number $\zeta_{D}\geq 1$
satisfying

$(1+\epsilon)\mathbb{E}_{0}[A_{D}]h(\zeta_{D}-1)=|D|\log\frac{N}{|D|},$

and $\theta_{i_{1}\ldots i_{m}}(\zeta_{D}p_{i_{1}\ldots i_{m}})\leq
2\theta_{i_{1}\ldots i_{m}}(\rho_{S}p_{i_{1}\ldots i_{m}})$ for
$i_{1},\ldots,i_{m}\in D$.

######  Lemma 4.2.

Under the conditions of Theorem 2.1, we have

$c_{n}:=\min\limits_{S\subset\mathcal{V},|S|=n}\min\limits_{D\in
E_{S}}\left((1-\epsilon)\frac{|D|^{(m)}}{|D|}\rho_{S}\mu_{D,m}h\left(\frac{\zeta_{D}}{\rho_{S}}-1\right)-\log\frac{n}{|D|}\right)\rightarrow\infty.$

######  Lemma 4.3.

Under the conditions of Theorem 2.1, for any $S\subset\mathcal{V}$ with
$|S|=n$ and $D\in E_{S}$, we have

$\frac{\log\frac{n}{|D|}}{\log\frac{N}{n}}\left(\log\rho_{S}\vee
1\right)=o(1),\ \ \ \ \ \ \
\frac{\log\frac{N}{n}}{\log\rho_{S}}\rightarrow\infty.$

###### Proof of Lemma 4.3.

Firstly, we consider Scenario I. For any $S\subset\mathcal{V}$ with $|S|=n$,
define $\eta_{S}\geq\rho_{S}$ such that

$\frac{n^{(m)}}{n}\frac{\mu_{S,m}h(\eta_{S}-1)}{\log\frac{N}{n}}=1-\frac{2\epsilon}{3}.$

Hence, by (6), we get

$h(\eta_{S}-1)<\frac{n\log\frac{N}{n}}{n^{(m)}\mu_{S,m}}=o(1),$

which implies $\eta_{S}=1+o(1)$. Hence,
$h(\eta_{S}-1)\sim\frac{(\eta_{S}-1)^{2}}{2}$. If
$|D|<\frac{n}{\left(\frac{N}{n}\right)^{\gamma_{N}}}$, then we have

$\displaystyle(\rho_{S}-1)^{2}\frac{\mathbb{E}_{0}[A_{D}]}{|D|}$
$\displaystyle\leq$
$\displaystyle(\eta_{S}-1)^{2}\frac{|D|^{(m)}}{|D|}\mu_{D,m}$
$\displaystyle\leq$
$\displaystyle\delta(\eta_{S}-1)^{2}\frac{|S|^{(m)}}{|S|}\mu_{S,m}$
$\displaystyle=$
$\displaystyle\left(1-\frac{2\epsilon}{3}\right)\delta(\eta_{S}-1)^{2}\frac{\log\frac{N}{n}}{h(\eta_{S}-1)}$
$\displaystyle=$
$\displaystyle\left(1-\frac{2\epsilon}{3}\right)2\delta\log\frac{N}{n}$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{\epsilon}{2}\right)\left(\log\frac{N|D|}{n^{2}}-\log\log\frac{N}{n}\right).$

This is a contradiction to the fact that $D\in E_{S}$. As a result, we have
$|D|\geq\frac{n}{\left(\frac{N}{n}\right)^{\gamma_{N}}}$. Then the desired
result follows.

Under Scenario II, the proof is almost the same as in [5]. We omit it here. ∎

######  Lemma 4.4.

Under the assumption (12), we have $|D^{*}|\geq n^{\frac{1}{m+1}}$.

###### Proof of Lemma 4.4.

Note that the function $f(x)=(x-1)\cdots(x-m+1)/(\log N-\log x)$ is increasing
for $x\ll N$. Suppose $|D|<n^{\frac{1}{m+1}}$ for any $D\subset\mathcal{V}$,
then we have

$\displaystyle\frac{|D|^{(m)}}{|D|}\frac{\mu_{D,m}}{\log\frac{N}{|D|}}$
$\displaystyle\leq$
$\displaystyle\frac{|D|^{(m)}}{|D|}\frac{W_{max}^{m}}{\log\frac{N}{|D|}}\leq\frac{|n^{\frac{1}{m+1}}|^{(m)}}{|n^{\frac{1}{m+1}}|}\frac{W_{max}^{m}}{\log\frac{N}{|n^{\frac{1}{m+1}}|}}$
$\displaystyle<$
$\displaystyle\frac{|n^{\frac{1}{m+1}}|^{(m)}}{|n^{\frac{1}{m+1}}|}\frac{n^{\frac{m}{m+1}}W_{min}^{m}}{\log\frac{N}{|n^{\frac{1}{m+1}}|}}\leq\frac{|n^{\frac{1}{m+1}}|^{(m)}}{|n^{\frac{1+m}{m+1}}|}\frac{n^{\frac{m+m}{m+1}}W_{min}^{m}}{\log\frac{N}{|S|}}$
$\displaystyle\leq$
$\displaystyle\frac{|S|^{(m)}}{|S|}\frac{W_{min}^{m}}{\log\frac{N}{|S|}}\leq\frac{|S|^{(m)}}{|S|}\frac{\mu_{S,m}}{\log\frac{N}{|S|}}.$

Hence, by the definition of $D^{*}$, we get $|D^{*}|\geq n^{\frac{1}{m+1}}$. ∎

######  Lemma 4.5.

Suppose $n,k\geq 2$ are fixed integers. Let
$f(x_{1},\ldots,x_{n})=\frac{\sum_{i=1}^{n}x_{i}^{k}}{\left(\sum_{i=1}^{n}x_{i}\right)^{k}}$
be a function on $x_{i}\in[a,b],i=1,2,\ldots n$ and $0<a<b<1$. Then

$\max_{x_{i}\in[a,b],i=1,\ldots,n}f(x_{1},\ldots,x_{n})\leq\frac{x_{0}(a^{k}-b^{k})+nb^{k}}{\left[x_{0}(a-b)+nb\right]^{k}}\leq\frac{1}{(k-1)n^{k-1}}\sum_{t=1}^{k-1}\left(\frac{b}{a}\right)^{t},$

where

$x_{0}=\frac{(a^{k}-b^{k})nb-kn(a-b)b^{k}}{(k-1)(a-b)(a^{k}-b^{k})}.$

###### Proof of Lemma 4.5.

Consider $f(x_{1},\ldots,x_{n})$ as a function of $x_{1}$ with the rest
arguments fixed. The derivative with respect to $x_{1}$ is equal to

$f_{x_{1}}=\frac{k\sum_{i=2}^{n}x_{i}}{\left(\sum_{i=1}^{n}x_{i}\right)^{k+1}}\left(x_{1}^{k-1}-\left[\left(\frac{\sum_{i=2}^{n}x_{i}^{k}}{\sum_{i=2}^{n}x_{i}}\right)^{\frac{1}{k-1}}\right]^{k-1}\right).$

When
$x_{1}>\left(\frac{\sum_{i=2}^{n}x_{i}^{k}}{\sum_{i=2}^{n}x_{i}}\right)^{\frac{1}{k-1}}$,
$f(x_{1},\ldots,x_{n})$ is increasing as a function of $x_{1}$. When
$x_{1}<\left(\frac{\sum_{i=2}^{n}x_{i}^{k}}{\sum_{i=2}^{n}x_{i}}\right)^{\frac{1}{k-1}}$,
$f(x_{1},\ldots,x_{n})$ is decreasing as a function of $x_{1}$. Hence, we get

$\max_{x_{1}\in[a,b]}f(x_{1},\ldots,x_{n})=\frac{a^{k}+\sum_{i=2}^{n}x_{i}^{k}}{\left(a+\sum_{i=2}^{n}x_{i}\right)^{k}}\vee\frac{b^{k}+\sum_{i=2}^{n}x_{i}^{k}}{\left(b+\sum_{i=2}^{n}x_{i}\right)^{k}}.$

Repeating this procedure for each $x_{2},\ldots,x_{n}$, we conclude

$\max_{x_{i}\in[a,b],i=1,\ldots,n}f(x_{1},\ldots,x_{n})=\max_{0\leq x\leq
n,x:integer}\frac{xa^{k}+(n-x)b^{k}}{\left[xa+(n-x)b\right]^{k}}\leq\max_{0\leq
x\leq n}\frac{x(a^{k}-b^{k})+nb^{k}}{\left[x(a-b)+nb\right]^{k}}.$

Let $g(x)=\frac{x(a^{k}-b^{k})+nb^{k}}{\left[x(a-b)+nb\right]^{k}}$ for $0\leq
x\leq n$. The derivative of $g(x)$ is

$g_{x}=\frac{(k-1)(a-b)(a^{k}-b^{k})}{\left[x(a-b)+nb\right]^{k+1}}\left(x_{0}-x\right).$

When $x<x_{0}$, $g(x)$ is increasing. When $x>x_{0}$, the $g(x)$ is
decreasing. Hence, $\max_{x\in[0,n]}g(x)=g(x_{0})$. Note that

$\displaystyle x_{0}(a^{k}-b^{k})+nb^{k}$ $\displaystyle=$
$\displaystyle\frac{(a^{k}-b^{k})nb-kn(a-b)b^{k}}{(k-1)(a-b)}+nb^{k}$
$\displaystyle=$
$\displaystyle\frac{n(a^{k-1}b+a^{k-2}b^{2}+\cdots+ab^{k-1}+b^{k})-nb^{k}}{k-1}$
$\displaystyle=$
$\displaystyle\frac{na^{k}}{k-1}\sum_{t=1}^{k-1}\left(\frac{b}{a}\right)^{t},$
$\displaystyle x_{0}(a-b)+nbk$ $\displaystyle=$
$\displaystyle\frac{knb}{k-1}-\frac{knb^{k}}{(k-1)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})}$
$\displaystyle=$
$\displaystyle\frac{kna}{k-1}\left(\frac{b}{a}-\frac{\left(\frac{b}{a}\right)^{k}}{\sum_{t=0}^{k-1}\left(\frac{b}{a}\right)^{t}}\right)\geq\frac{kna}{k-1}\left(1-\frac{1}{k}\right)=na.$

Hence, we have

$g(x_{0})\leq\frac{1}{n^{k}a^{k}}\frac{na^{k}}{k-1}\sum_{t=1}^{k-1}\left(\frac{b}{a}\right)^{t}=\frac{1}{(k-1)n^{k-1}}\sum_{t=1}^{k-1}\left(\frac{b}{a}\right)^{t}.$

∎

######  Lemma 4.6.

Under the assumption (12), if

$A_{\mathcal{V}}=(1+o_{P}(1))\mathbb{E}_{0}[A_{\mathcal{V}}],$
$A_{D,D^{c}}=(1+o_{P}(1))\mathbb{E}_{0}[A_{D,D^{c}}],$

uniformly for all $D\subset\mathcal{V}$ with $n^{\frac{1}{m+1}}\leq|D|\leq n$,
then

$\widehat{p}_{D,m}=(1+o_{p}(1))\mathbb{E}_{0}[A_{D}],$

uniformly for all $D\subset\mathcal{V}$ with $n^{\frac{1}{m+1}}\leq|D|\leq n$.
Under $H_{1}$, the above result still holds.

###### Proof of Lemma 4.4.

Define a function
$f(x,y)=\left(x^{\frac{1}{m}}-(x-2y)^{\frac{1}{m}}\right)^{m}$ for $x\geq 2y$.
At a fixed point $(a,b)$, the Taylor expansion is

$f(x,y)=f(a,b)+\frac{\partial f}{\partial x}(x^{*},y^{*})(x-a)+\frac{\partial
f}{\partial y}(x^{*},y^{*})(y-b),$ (17)

where $x^{*}$ is between $a$ and $x$, $y^{*}$ is between $b$ and $y$ and

$\frac{\partial f}{\partial
x}(x,y)=\left(x^{\frac{1}{m}}-(x-2y)^{\frac{1}{m}}\right)^{m-1}\left(x^{\frac{1-m}{m}}-(x-2y)^{\frac{1-m}{m}}\right),$
$\frac{\partial f}{\partial
x}(x,y)=\frac{2\left(x^{\frac{1}{m}}-(x-2y)^{\frac{1}{m}}\right)^{m}}{\left(x^{\frac{1}{m}}-(x-2y)^{\frac{1}{m}}\right)(x-2y)^{1-\frac{1}{m}}}.$

Under the assumption (12),
$\left(\frac{W_{max}}{W_{min}}\right)^{m}\ll\left(\frac{N}{n}\right)^{m-1-\delta_{m}}W_{min}^{m}\ll\left(\frac{N}{n}\right)^{m-1-\delta_{m}}$.
Then

$\frac{\mathbb{E}_{0}[A_{D,D^{c}}]}{\mathbb{E}_{0}[A_{\mathcal{V}}]}\leq\frac{\sum_{k=1}^{t_{m}}\binom{m}{2k-1}(N-n)^{2k-1}n^{m-2k+1}W_{max}^{m}}{N^{m}W_{min}^{m}}\ll\left(\frac{N}{n}\right)^{m-1-\delta_{m}}=o(1).$
(18)

Hence, we get
$f(\mathbb{E}_{0}[A_{\mathcal{V}}],\mathbb{E}_{0}[A_{D,D^{c}}])=(1+o(1))\mathbb{E}_{0}[A_{\mathcal{V}}]$
uniformly in $D$. For $(x,y)=(A_{\mathcal{V}},A_{D,D^{c}})$ and
$(a,b)=(\mathbb{E}_{0}[A_{\mathcal{V}}],\mathbb{E}_{0}[A_{D,D^{c}}])$, we also
have

$\frac{\partial f}{\partial x}(x^{*},y^{*})=1+o_{p}(1),\ \ \ \frac{\partial
f}{\partial y}(x^{*},y^{*})=2+o_{p}(1).$

By (17), it’s easy to check

$\frac{2^{m}\widehat{p}_{D,m}}{\mathbb{E}_{0}[A_{\mathcal{V}}]}=\frac{f(A_{\mathcal{V}},A_{D,D^{c}})}{f(\mathbb{E}_{0}[A_{\mathcal{V}}],\mathbb{E}_{0}[A_{D,D^{c}}])(1+o(1))}=1+o_{p}(1).$

It suffices to show
$\mathbb{E}_{0}[A_{\mathcal{V}}]=2^{m}\mathbb{E}_{0}[A_{D}]$. To this end, by
(14) and (18), we only need to prove

$\mathbb{E}_{0}[A_{D}]\gg\frac{1}{m!}\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\ \\{i_{1},\ldots,i_{m}\\}\subset D\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}},$ (19)

for any $|D|\geq n^{\frac{1}{m+1}}$. Note that

$\mathbb{E}_{0}[A_{D}]=\frac{1}{m!}\left(\sum_{i\in
D}W_{i}\right)^{m}-\frac{1}{m!}\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\ \\{i_{1},\ldots,i_{m}\\}\subset D\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}}.$

Obviously, $\sum_{\begin{subarray}{c}|\\{i_{1},i_{2},\ldots,i_{m}\\}|\leq
m-1\\\ \\{i_{1},\ldots,i_{m}\\}\subset D\end{subarray}}W_{i_{1}}\cdots
W_{i_{m}}$ can be written as a summation of products of $\sum_{i\in
D}W_{i}^{k}$, $k=1,2,\ldots,m$. By Lemma 4.5 and assumption (12), for the term
$\sum_{i\in D}W_{i}^{k}$ with $k\geq 2$, we have

$\frac{\sum_{i\in D}W_{i}^{k}}{(\sum_{i\in
D}W_{i})^{k}}=O\left(\frac{1}{|D|^{k-1}}\left(\frac{W_{max}}{W_{min}}\right)^{k-1}\right)=O\left(\frac{o(n^{\frac{k-1}{m+1}})}{n^{\frac{k-1}{m+1}}}\right)=o(1).$

Hence, (19) holds. Under $H_{1}$, the result can be similarly proved. ∎

## References

  * [1] Ahn, K., Lee, K. and Suh, C. (2016). Community recovery in hypergraphs, 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton). DOI: 10.1109/ALLERTON.2016.7852294.
  * [2] Ahn, K., Lee, K. and Suh, C. (2018). Hypergraph Spectral Clustering in the Weighted Stochastic Block Model. IEEE Journal of Selected Topics in Signal Processing 12(5), 2018.
  * [3] Angelini, M., Caltagirone,F., Krzakala, F. and Zdeborova, L. (2015). Spectral detection on sparse hypergraphs. Allerton Conference on Communication, Control, and Computing, 66-73.
  * [4] Arias-Castro, E. and Verzelen, N. (2014). Community detection in dense random networks. Annals of Statistics, 42, 3: 940-969.
  * [5] Bogerd, K., Castro, R., Hofstad, R. and Verzelen, N. (2019). Detecting a planted community in an inhomogeneous random graph. Bernoulli, 27, 1159–1188.
  * [6] Bi, X., Tang, X., Yuan, Y., Zhang, Y. and Qu, A. (2021). Tensors in statistics. Annual Review of Statistics and Its Application, 8.
  * [7] Butucea, C. and Ingster, Y. (2013). Detection of a sparse submatrix of a high-dimensional noisy matrix. Bernoulli, 195B, 2652-2688.
  * [8] Bulo S. and Pelillo, M. (2009). New Bounds on the Clique Number of Graphs Based on Spectral Hypergraph Theory. Learning and Intelligent Optimization. LION 2009,45-58.
  * [9] Bolla, M. (1993). Spectra, euclidean representations and clusterings of hypergraphs. Discrete Mathematics, 117(1), 19-39.
  * [10] Bollobás, B. and Erdös, P. (1976). Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 80, 419-427.
  * [11] Bhangale, A., Gandhi, R. and Kortsarz, G. (2017). Improved approximation algorithm for the dense-3-subhypergraph problem. https://arxiv.org/abs/1704.08620
  * [12] Chertok, M. and Keller, Y. (2010). Efficient high order matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(12), 2205-2215.
  * [13] Chlamtac, E., M. Dinitz, C. Konrad, G. Kortsarz, and G. Rabanca. The Densest k-Subhypergraph problem. SIAM Journal on Discrete Mathematics. 32 (2):1458–77.
  * [14] Florescu, L. and Perkins, W. (2016). Spectral thresholds in the bipartite stochastic block model. 29th Annual Conference on Learning Theory, 49: 943-959.
  * [15] Ghoshdastidar, D. and Dukkipati, A. (2014). Consistency of spectral partitioning of uniform hypergraphs under planted partition model.  Advances in Neural Information Processing Systems (NIPS), 397-405.
  * [16] Ghoshdastidar, D. and Dukkipati A. (2017). Consistency of spectral hypergraph partitioning under planted partition model. The Annals of Statistics, 45(1), 289-315.
  * [17] Hall, P. and Heyde, C. C. (2014). Martingale limit theory and its application. Academic press.
  * [18] Hu, S., Wu, X. and Chan, T-H. (2017). Maintaining densest subsets efficiently in evolving hypergraphs Proceedings of the 2017 ACM on Conference on Information and Knowledge Management,929-938,Singapore.
  * [19] Kim, S. 2011. Higher-order correlation clustering for image segmentation. Advances in Neural Information Processing Systems 1530–8.
  * [20] Ke, Z., Shi, F. and Xia, D. (2020). Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration. https://arxiv.org/pdf/1909.06503.pdf.
  * [21] Kim, C., Bandeira,A. and Goemans, M. (2017). Community detection in hypergraphs, spiked tensor models, and sum-of-squares. 2017 International Conference on Sampling Theory and Applications (SampTA), 124-128.
  * [22] Lin, C., Chien, I. and Wang, I. (2017). On the fundamental statistical limit of community detection in random hypergraphs.  Information Theory (ISIT), 2017 IEEE International Symposium, 2178-2182.
  * [23] Luo, Y. and Zhang, A. (2020). Open problem: average-case hardness of hypergraphic planted clique detection. Proceedings of Machine Learning Research, 1-4, 2020.
  * [24] Liu, H., Jan, L. and Yan, S. (2015). Dense subgraph partition of positive hypergraphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37, 3:541-554.
  * [25] Peng, X. (2016). The Ramsey number of generalized loose paths in hypergraphs. Discrete Mathematics 339 (2):539–46.
  * [26] Rodriguez, J. A. (2009). Laplacian eigenvalues and partition problems in hypergraphs. Applied Mathematics Letters, 22(6), 916-921.
  * [27] Rota Bulo, S. and Pelillo, M. (2013). A game-theoretic approach to hypergraph clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(6), 1312-1327.
  * [28] Soderberg, B.(2002). General formalism for inhomogeneous random graphs. Phys. Rev. E. 66,066121.
  * [29] Verzelen, N., Arias-Castro, E.(2015). Community detection in sparse random networks. Ann. Appl. Probab., 25, 6:3465–3510.
  * [30] Yuan, M., Liu, R., Feng, Y. and Shang, Z. (2018). Testing community structures for hypergraphs. arXiv preprint arXiv:1810.04617.
  * [31] Yuan, M. and Shang, Z. (2021). Sharp detection boundaries on testing dense subhypergraph. https://arxiv.org/abs/2101.04584
  * [32] Zhou, D., Huang, J. and Scholkopf, B. (2006). Learning with hyper graphs: Clustering, classification, and embedding. Advances in Neural Information Processing Systems. 6:1601–8.