Planted Bipartite Graph Detection

Asaf RotenbergA. Rotenberg is with the Department of Electrical Engineering-Systems at Tel Aviv university, Tel Aviv 6997801, Israel (e-mail:  ). The work of A. Rotenberg was supported by the ISRAEL SCIENCE FOUNDATION (grants No. 1734/21 and 1766/22)           Wasim HuleihelW. Huleihel is with the Department of Electrical Engineering-Systems at Tel Aviv university, Tel Aviv 6997801, Israel (e-mail:  ). The work of W. Huleihel was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1734/21).           Ofer ShayevitzO. Shayevitz is with the Department of Electrical Engineering-Systems at Tel Aviv university, Tel Aviv 6997801, Israel (e-mail:  ).   The work of O. Shayevitz was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1766/22).

We consider the task of detecting a hidden bipartite subgraph in a given random graph. Specifically, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over $n$ vertices with edge density $q$. Under the alternative, there exists a planted $k_{\s{R}} \times k_{\s{L}}$ bipartite subgraph with edge density $p>q$. We derive asymptotically tight upper and lower bounds for this detection problem in both the dense regime, where $q,p = \Theta\left(1\right)$, and the sparse regime where $q,p = \Theta\left(n^{-\alpha}\right), \alpha \in \left(0,2\right]$. Moreover, we consider a variant of the above problem, where one can only observe a relatively small part of the graph, by using at most $\mathsf{Q}$ edge queries. For this problem, we derive upper and lower bounds in both the dense and sparse regimes.

§ INTRODUCTION

The problem of detecting hidden structures in large graphs arises frequently in a vast verity of fields, such as, social networks analysis, computational biology, and computer vision, and have been well-studied in the literature in many interesting settings. It is quite clear by now, that the inference of such structures, especially in the high-dimensional regime, impose many statistical and computational challenges [1]. In this work, we study a hypothesis testing problem that underlies some of these challenges. To motivate this problem, at least mathematically, let us briefly review a few classical results. To that end, consider the following somewhat general formulation of the hidden subgraph detection problem. Observing a graph over $n$ vertices, assume our goal is to infer whether there is a hidden planted structure in the graph, or if it is purely random, say, a realization of an Erdős-Rényi random graph. Throughout the paper we denote the later by $\calG(n,q)$, namely, a random graph over $n$ vertices with edge probability $q$. If the planted structure is a fully connected subset of $k<n$ vertices, namely, a clique, then the above problem is well-known as the Planted Clique ($\mathsf{PC}$) problem (e.g., [2], [3], [4], [5]). If the planted structure is a realization of an Erdős-Rényi $\calG(k,p)$ random graph, then we get the well-studied Planted Dense Subgraph ($\mathsf{PDS}$) problem (e.g., [6], [7], [8]). Those problems have received widespread attention in the literature (also) because there is a region of parameters $(n,k,p,q)$ for which, while statistically possible, it appears to be computationally hard to solve the detection problem.

In this work, we focus on the case where the planted structure is a $k_{\s{R}} \times k_{\s{L}}$ bipartite subgraph with edge density $p>q$. If $p=1$, the planted structure is a complete bipartite graph with $k_{\s{R}}+k_{\s{L}}$ vertices and $k_{\s{R}} k_{\s{L}}$ edges. If $p<1$, each of the $k_{\s{R}} k_{\s{L}}$ possible edges exist with probability $p$, independently of other edges. Compared to the previously mentioned complete and dense subgraph structures, it seems that the “geometry" of bipartite graphs is richer, as we explain below. Specifically, as will be clear later on in the paper, the detection boundaries for general planted structures depend on the following quantity.

Fix a subgraph $\Gamma = (v(\Gamma),e(\Gamma))$ with a set of vertices $v(\Gamma)$ and a set of edges $e(\Gamma)$. The maximal subgraph degree of $\Gamma$ is defined as:

\begin{align}
m{\left(\Gamma \right)} \triangleq \max_{\emptyset\neq H \subseteq \Gamma} \frac{\vert e{\left(H\right)}\vert}{\vert v{\left(H\right)}\vert}.
\end{align}

Note that $\Omega \left(1\right) \leq m{\left(\Gamma \right)} \leq O \left(\vert v{\left(\Gamma\right)}\vert\right)$. As shown in [9, 10], the maximal subgraph degree plays an important role in the characterization of the subgraphs count in Erdős-Rényi random graphs. For the $\mathsf{PC}$ and $\mathsf{PDS}$ problems, it is clear that the maximal subgraph degree is $\frac{k-1}{2}$, while in the planted bipartite problem, we get,

\begin{align}
m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \frac{k_{\s{R}} k_{\s{L}}}{k_{\s{R}} + k_{\s{L}}}.
\end{align}

To see why this quantity is of any importance in our problem, let us consider a few special cases. For example, when $k_{\s{R}}=k_{\s{L}}$, that is, the planted structure is a balanced bipartite graph, the maximal subgraph degree is $\frac{k_{\s{R}} + k_{\s{L}}}{4} = \Theta \left(\vert v{\left({\mathsf{K}}_{\calR, \calL}\right)}\vert\right)$. In this case, we will prove that the statistical limits of the detection problem are similar to those of the $\mathsf{PC}$ and $\mathsf{PDS}$ problems. On the other hand, if $\min \left\{k_{\s{R}}, k_{\s{L}}\right\}= 1$, then the planted structure reduces to a star graph whose maximal subgraph degree is $\frac{k_{\s{R}} + k_{\s{L}} - 1}{k_{\s{R}} + k_{\s{L}}} = \Theta \left(1\right)$, and for which the statistical and computational limits are completely different (in particular, there is no a hard region), as proved in [11]. In fact, we conjecture that the maximal subgraph degree affects (at least partially) the statistical and computational limits of the detection problem. In the first part of this paper, we analyze the statistical barriers of bipartite subgraph detection for any values of $k_{\s{R}}$ and $k_{\s{L}}$. To the best of our knowledge, our work is the first to face a detection problem of a planted structure with geometry containing every possible value of the maximal subgraph degree.

In the second part of this paper, we consider a variant of the above detection problem, where one can only observe a relatively small part of the graph, by using at most $\mathsf{Q}$ edge queries. This problem is relevant, for example, in cases where access to connections (edges) between individuals may be expensive to obtain or limited, e.g., due to privacy concerns.

Related Work. The $\mathsf{PC}$ detection problem have been studied from many different perspectives in the last decades. Many polynomial-time algorithms have been proposed, including simple edge count, degree test [12], that achieves detection if $k=\Omega\left(\sqrt{n \log{n}}\right)$, and more sophisticated spectral approaches, e.g., [2] that succeed if $k=\Omega\left(\sqrt{n}\right)$. Statistical limits as well as the analysis of inferring algorithms are also studied in other subgraphs detection problems, including, e.g., community detection [13], [14]. It was first conjectured in [15] that the $\mathsf{PC}$ problem cannot be solved in polynomial-time if $k=o\left(\sqrt{n}\right)$, while an exhaustive scan succeeds if $k=\Omega\left(\log{n}\right)$. This $\mathsf{PC}$  conjecture has been used through reduction arguments in other high-dimensional problems, such as sparse $\mathsf{PCA}$ [16] and $\mathsf{PDS}$ [6], who observed an impossible-hard-easy phase transition phenomena. For recent surveys we refer the reader to [17, 18], and many references therein.

Most of the above high-dimensional detection problems typically deal with a planted structure whose elements are all either fully connected ($\mathsf{PC}$) or connected with some probability (e.g., $\mathsf{PDS}$). Accordingly, existing techniques used to determine the statistical and computational limits are specialized to this types of structures. Recently in [19] the detection and recovery problems of a general planted induced subgraph was considered; however, since the latent structure appears as an induced subgraph, the techniques and results in [19] are irrelevant to our setting, where we take a union of bipartite graph and the underlying Erdős-Rényi random graph. While our bipartite framework is still specific, it turns out, as mentioned above, that it covers asymptotically the entire range of possible maximal subgraph degrees, and that its analysis is technically interesting. Moreover, bipartite graphs have many theoretical and practical applications (see, e.g., [20], [21]), which provide further motivation for this paper.

The problem of finding cliques in an Erdős-Rényi random graph using $\mathsf{Q}$ edge queries was first considered in [22], where it was shown that any algorithm makes $\mathsf{Q}=O\left(n^{\alpha}\right), \alpha < 2$ adaptive (with some limitations) edge queries finds, in $l$ rounds, cliques of size at most $\left(2-\epsilon\right) \log_2{n}, \epsilon = \epsilon\left(\alpha, l\right) > 0$. This result was improved by [23], where the dependency of $\epsilon$ on $l$ was removed. On the other hand, there is a gap from the current state-of-the-art algorithms that find a clique of size at most $\left(1+\frac{\alpha}{2}\right) \log_2{n}$ by using $\mathsf{Q}=O\left(n^{\alpha}\right), \alpha < 2$ edge queries. The detection problem of a planted clique using $\mathsf{Q}$ edge queries was studied in [24], where it was proved that any algorithm makes $\mathsf{Q}=O\left(n^2/k^2\right)$ adaptive edge queries cannot solve the detection problem with probability tending to 1, while scan-based test achieves detection by using $\mathsf{Q}=\Omega\left(\frac{n^2 \log^2{n}}{k^2}\right)$ edge queries. This gap was later closed by [25], proving that detection is impossible if $\mathsf{Q}=o\left(\frac{n^2 \log^2{n}}{k^2}\right)$ edge queries. Moreover, [25] extended the results for the $\mathsf{PDS}$ case, and proposed a polynomial-time degree-based algorithm.

Notation. For a simple undirected graph $\s{G}$, denote its adjacency matrix by $\mathsf{A}$. Also, let $v\left(\s{G}\right)$ and $e\left(\s{G}\right)$ be the vertex set and the edges set of $\s{G}$, respectively. We denote the size of any finite set $\calS$ by $\vert \calS \vert$. Let $m{\left(\s{G}\right)}$ be the maximal subgraph degree of $\s{G}$, as defined in <ref>. Moreover, let $\Delta{\left(\s{G}\right)}$ be the maximal vertex degree of $\s{G}$, that is,
$\Delta{\left(\s{G}\right)} \triangleq \max_i \mathsf{deg}_{i}$, where $\mathsf{deg}_{i}$ is the degree of the $i^{\s{th}}$ vertex, that is, the number of edges with one end point at vertex $i$.
Let $\mathsf{N}_{{\mathsf{K}}_{\calR, \calL}}\triangleq\binom{n}{k_{\s{R}}}\binom{n-k_{\s{R}}}{k_{\s{L}}}$ denote the number of all possible $k_{\s{R}} \times k_{\s{L}}$ copies of bipartite graphs; we label those copies as ${\mathsf{K}}^{\left(1\right)}_{\calR, \calL}, {\mathsf{K}}^{\left(2\right)}_{\calR, \calL},\ldots,{\mathsf{K}}_{\calR, \calL}^{(\mathsf{N}_{{\mathsf{K}}_{\calR, \calL}})}$. Let $\left[n\right]$ denote the set of integers $\{1,2,\ldots,n\}$, for any $n\in\mathbb{N}$. For probability measures $\mathbb{P}$ and $\mathbb{Q}$, let $d_{\s{TV}}(\mathbb{P},\mathbb{Q})=\frac{1}{2}\int |\mathrm{d}\mathbb{P}-\mathrm{d}\mathbb{Q}|$ and $\chi^2(\mathbb{P}||\mathbb{Q}) = \int\frac{(\mathrm{d}\mathbb{P}-\mathrm{d}\mathbb{Q})^2}{\mathrm{d}\mathbb{Q}}$ denote the total variation distance and the $\chi^2$-divergence, respectively. Let $\s{Bern}(p)$ and $\s{Binomial}(n,p)$ denote the Bernoulli and Binomial distributions with parameter $p$ and $n$, respectively. We use
standard asymptotic notation: for two positive sequences $\{a_n\}$ and $\{b_n\}$, we write $a_n = O(b_n)$ if $a_n\leq Cb_n$, for some absolute constant $C$ and for all $n$; $a_n = \Omega(b_n)$, if
$b_n = O(a_n)$; $a_n = \Theta(b_n)$, if $a_n = O(b_n)$ and $a_n = \Omega(b_n)$, $a_n = o(b_n)$ or $b_n = \omega(a_n)$, if $a_n/b_n\to0$, as $n\to\infty$. Finally, for $a,b\in\mathbb{R}$, we let $a\vee b\triangleq\max\{a,b\}$ and $a\wedge b\triangleq\min\{a,b\}$.

§ PROBLEM FORMULATION

Let us describe the general setting of planted bipartite graph detection. We have a total of $n$ vertices. We pick $k_{\s{R}}$ out of $n$ vertices, uniformly at random, and denote this set by $\calR \subset \left[n\right]$. From the remaining $n-k_{\s{R}}$ vertices, we again pick another set of $k_{\s{L}}$ vertices, uniformly at random, and denote the obtained set by $\calL \subseteq \left[n\right] \backslash \calR$. We refer to $\calR$ and $\calL$ as the right and left planted sets, respectively. Let $\mathscr{E}\left(\calR, \calL\right)$ the set of edges $\left \{\left(i,j\right) : i<j, i \in \calR, j \in \calL \text{ or } i \in \calL, j \in \calR\right\}$, and let ${\mathsf{K}}_{\calR, \calL}$ be an empty graph on $n$ vertices, except for all the elements in $\mathscr{E}\left(\calR, \calL\right)$. Let $v\left({\mathsf{K}}_{\calR, \calL}\right) \triangleq \calR \cup \calL$ and $e\left({\mathsf{K}}_{\calR, \calL}\right) \triangleq \mathscr{E}\left(\calR, \calL\right)$ denote the set of vertices and edges of $\mathsf{K}_{\calR, \calL}$, respectively. Note that $\abs{v\left({\mathsf{K}}_{\calR, \calL}\right)} = k_{\s{R}}+k_{\s{L}}$ and $\abs{e\left({\mathsf{K}}_{\calR, \calL}\right) } = k_{\s{R}} k_{\s{L}}$. We refer to ${\mathsf{K}}_{\calR, \calL}$ as the planted structure. Finally, let ${\mathsf{K}}^{p}_{\calR, \calL}$ be the random graph obtain by keeping each edge in $e\left({\mathsf{K}}_{\calR, \calL}\right)$, with probability $p$. Consequently, our detection problem can be phrased as the following simple hypothesis testing problem: under the null hypothesis $\calH_0$, the graph $\s{G}$ is an Erdős-Rényi random graph $\calG(n,q)$ with edge density $0<q<1$, which might be a function of $n$. Under the alternative hypothesis $\calH_1$, a base graph $\s{\tilde{G}}$ is sampled from from $\calG(n,q)$, and we observe the union of this base graph with ${\mathsf{K}}^{p}_{\calR, \calL}$, i.e., $\s{G}=\s{\tilde{G}}\cup {\mathsf{K}}^{p}_{\calR, \calL}$, where we assume that $p>q$.
[PDBS Detection Problem]
The planted dense bipartite subgraph detection problem, denoted by $\mathsf{PDBS}{\left(n,k_{\s{R}},k_{\s{L}},p,q\right)}$, refers to the problem of distinguishing between the hypotheses:

\begin{align}
\calH_0: \s{G} \sim \calG(n,q) \quad \mathsf{vs}. \quad \calH_1 : \s{G} \sim \calG(n,q,k_{\s{R}},k_{\s{L}},p).\label{eqn:super_hypo}
\end{align}

We study the above framework in the asymptotic regime where $n\to \infty$, and $(k_{\s{R}},k_{\s{L}},p,q)$ may also change as a function of $n$. Throughout the paper we assume that $k_{\s{R}}+k_{\s{L}} = o\left(n\right)$. Observing $\s{G}$, the goal is to design a test $\phi:\p{0,1}^{\binom{n}{2}}\to \{0, 1\}$ that distinguishes between $\calH_0$ and $\calH_1$. Specifically, the average $\mathsf{Type}$ $\mathsf{I}$+$\mathsf{II}$ risk of a test $\phi$ is defined as
$\mathsf{R}_n (\phi) = \pr_{\calH_0}(\phi(\s{G}) = 1)+ \pr_{\calH_1}(\phi(\s{G}) = 0)$. A sequence of tests $\phi_n$ indexed by $n$ succeeds if $\lim_{n \to \infty} \mathsf{R}_n(\phi_n) = 0$, while if $\lim_{n \to \infty} \mathsf{R}_n(\phi_n)>0$, it fails. The above is summarized in the following definition.

Let $\pr_{\calH_0}$ and $ \pr_{\calH_1}$ be the distributions of $\s{G}$ under the uniform and planted hypotheses, respectively. A possibly randomized algorithm $\phi_n(\s{G}) \in \{0, 1\}$ achieves strong detection, if its $\mathsf{Type}$ $\mathsf{I}$+$\mathsf{II}$ risk satisfies $\lim_{n \to \infty} \mathsf{R}_n(\phi_n)=0$. On the other hand, if for all sequences of possibly randomized algorithms $\phi_n(\s{G}) \in \{0, 1\}$, the $\mathsf{Type}$ $\mathsf{I}$+$\mathsf{II}$ risk satisfies $\liminf_{n \to \infty} \mathsf{R}_n(\phi_n)>0$, then strong detection is impossible.

We study also a variant of Problem <ref>, where one can only investigate a small part of the graph, as follows.

Consider a graph $\s{G}=(\left[n\right],\mathscr{E})$ with $n$ vertices, where $\mathscr{E}$ denotes the set of edges. An oracle $\calO:\left[n\right]\times\left[n\right]\to\{0,1\}$, takes as input a pair of vertices $i,j\in\left[n\right]\times\left[n\right]$, and if $(i,j)\in\mathscr{E}$, namely, there exists an edges between the chosen vertices, then $\calO(i,j)=1$, otherwise, $\calO(i,j)=0$.

We consider query mechanisms that evolve dynamically over $\s{Q}$ steps/queries in the following form: in step number $t\in[\s{Q}]$, the mechanism chooses a pair of vertices $(i_t,j_t)$ and asks the oracle whether these vertices are connected by an edge or not. Generally speaking, either adaptive or non-adaptive query mechanisms can be considered. In the former, the chosen $t^{th}$ pair may depend on the previously chosen pairs $\{(i_\tau,j_\tau)\}_{\tau<t}$, as well as on past responses $\{\calO(i_\tau,j_\tau)\}_{\tau<t}$. In non-adaptive mechanisms, on the other hand, all queries must be made upfront. The query-$\s{PDBS}$ detection problem is defined as follows.
[Query-PDBS Detection Problem]
Consider the $\s{PDBS}$ detection problem in Problem <ref>. There is an oracle $\calO$ as defined in Definition <ref>. Find a set of queries $\calQ\subseteq\left[n\right]\times\left[n\right]$ such that
$\s{Q}=|\calQ|$ is minimum, and from the oracle answers it is possible to solve (as defined below) the detection problem in (<ref>). Henceforth, we denote this detection problem by $\mathsf{QPDBS}{\left(n,k_{\s{R}},k_{\s{L}},\mathsf{Q},p,q\right)}$.

A detection algorithm for Problem <ref>, makes up to $\s{Q}$ edge queries, and based on the query responses is tasked with outputting a decision.

§ MAIN RESULTS

For problem <ref> above, we characterize the statistical limits of detection. To that end, we derive impossibility results in the form of information-theoretic lower bounds that applies to all algorithms, providing conditions under which strong detection is impossible. We then propose several algorithms, analyze their performance, and show that our bounds are asymptotically tight. These bounds are summarized in Table <ref> below.

Detection Threshold

Bipartite Dense      $1 \asymp \min\left \{\frac{\log{\left(n^{1-o\left(1\right)}\right)}}{k_{\s{R}}\wedge k_{\s{L}}}, \frac{n }{\left(k_{\s{R}}\vee k_{\s{L}}\right)^2}\right \}$

Bipartite Sparse      $\chi^2(p||q) \asymp \min \left\{\frac{1}{k_{\s{R}} \wedge k_{\s{L}}},\frac{n^2}{k_{\s{R}}^2 k_{\s{L}}^2},\frac{n}{\left(k_{\s{R}} \vee k_{\s{L}}\right)^2}\right\}$

Bipartite subgraph detection thresholds.

Let us now review some of our results and discuss a few technical challenges. From an algorithmic perspective, the detection thresholds in Table <ref> are achieved by a combination of the following three procedures:

* Scan test: scans for the densest bipartite subgraph in the observed graph, and compare its size to a certain threshold.

* Count test: counts the number of edges in the observed graph, and compare this count to a certain threshold.

* Degree test: looks for the maximal vertex degree in the observed graph, and compare this degree to a certain threshold.

Precise definitions of the above procedures are given in Section <ref>. It should be emphasized that the above algorithms are by no means novel; the exact same algorithms were suggested for the $\mathsf{PC}$ and $\mathsf{PDS}$ problems in, e.g., [6, 8]. Nonetheless, there is an interesting a-priori non-trivial phenomenon that takes place in the case of bipartite subgraph detection. Specifically, for the $\mathsf{PC}$ problem we have the phase diagram shown in Figure <ref>. Note that the scan test is always at least as good as degree and count tests. Also, note that count and degree tests have the same performance.

every node=[font=]

1.5 * + 0.1

[->] (,) – (,) node[right] $k$;

at (* 0.7, 0) [below] $\Theta(\sqrt{n})$;
at (* 0.3, 0) [below] $\Theta(\log{n})$;
at (0, 0) [below] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 0.1 * ) – (0.3 * ,  0.1 * ) – (0.3 * , 0) – (0, 0);
[fill=red!25, draw=black] (0.3 * , 0) – (0.3 * , 0.1 * ) – (0.7 * , 0.1 * ) – (0.7 * , 0) – (0.3 * , 0);
[fill=green!25, draw=black] (0.7 * , 0) – (0.7 * , 0.1 * ) – (1.5 * , 0.1 * ) – (1.5 * , 0) – (0.7 * , 0);

at (* 0.15 , * 0.5) $\s{\mathbf{Statistically}}$;
at (* 0.15 , * 0.3) $\s{\mathbf{Impossible}}$;
at (* 0.5 , * 0.3) $\s{\mathbf{Scan}}$;
at (* 1.1 , * 0.3) $\s{\mathbf{Scan/Count/Degree}}$;

Phase diagram for detecting a planted clique of size $k$, as a function of $k$.

Now, even for the special case of complete bipartite, where $p=1$, the phase diagram shown in Figure <ref> is inherently different. The axes in Figure <ref> are the number of vertices in the right and left planted sets. Note that there exists a regime, depending on the values of $(k_{\s{R}},k_{\s{L}})$, in which the degree test is better than the scan test, in a stark contrast to the planted clique case. As we show later on in the paper, the same behaviour holds for the sparse case, where $p$ and $q$ decay with $n$ polynomially.

every node=[font=]
1.4 * + 0.1
1.4 * + 0.1

[->] (,) – (,) node[right] $k_{\s{R}}$;
[->] (,) – (,) node[above] $k_{\s{L}}$;

at (* 0.6, 0) [below] $\Theta(\sqrt{n})$;
at (* 0.2, 0) [below] $\Theta(\log{n})$;
at (0, 0) [below] $0$;

at (0, * 0.6) [left] $\Theta(\sqrt{n})$;
at (0, * 0.2) [left] $\Theta(\log{n})$;

[fill=gray!25, draw=black] (0, 0) – (0, 0.6 * ) – (0.2 * ,  0.6 * ) – (0.2 * ,  0.2 * ) – (0.6 * ,  0.2 * ) – (0.6 * , 0) – (0, 0);
[fill=blue!25, draw=black] (0, 0.6 * ) – (0,  -* 0.02) – (0.2 * ,  -* 0.02) – (0.2 * ,  0.6 * ) – (0, 0.6 * );
[fill=blue!25, draw=black] (0.6 * , 0) – (-* 0.02, 0) – (-* 0.02, 0.2 * ) – (0.6 * , 0.2 * ) – (0.6 * , 0);
[fill=red!25, draw=black] (0.2 * , 0.2 * ) – (0.2 * , 0.6 * ) – (0.6 * , 0.6 * ) – (0.6 * , 0.2 * ) – (0.2 * , 0.2 * );
[fill=purple!25, draw=black] (0.2 * , 0.6 * ) – (0.2 * , 1 * ) – (0.6 * , 0.6 * ) – (0.2 * , 0.6 * );
[fill=purple!25, draw=black] (0.6 * , 0.2 * ) – (1 * , 0.2 * ) – (0.6 * , 0.6 * ) – (0.6 * , 0.2 * );
[fill=green!25, draw=black] (0.2 * , 1 * ) – (0.2 * , -* 0.02) – (-* 0.02, -* 0.02) – (-* 0.02, 0.2 * ) – (, 0.2 * ) – (0.2 * , 1 * );

at (* 0.22 , * 0.14) $\s{\mathbf{Statistically}}$;
at (* 0.22 , * 0.06) $\s{\mathbf{Impossible}}$;
at (* 0.39 , * 0.39) $\s{\mathbf{Scan}}$;
at (* 0.34 , * 0.72) $\s{\mathbf{Scan/}}$;
at (* 0.34 , * 0.64) $\s{\mathbf{Degree}}$;
at (* 0.74 , * 0.32) $\s{\mathbf{Scan/}}$;
at (* 0.74 , * 0.24) $\s{\mathbf{Degree}}$;
at (* 0.95, * 0.1) $\s{\mathbf{Degree}}$;
[rotate=90] at (* 0.1, * 0.95) $\s{\mathbf{Degree}}$;
at (* 0.85, * 0.85) $\s{\mathbf{Scan/Count/Degree}}$;

Phase diagram for detecting a planted $k_{\s{R}} \times k_{\s{L}}$ complete bipartite.

Finally, we discuss some of the technical challenges in the proofs of our lower bounds. For Problem <ref>, as in many related problems (e.g., [6, 8]), deriving a lower bound on the $\mathsf{Type}$ $\mathsf{I}$+$\mathsf{II}$ risk of any algorithm boils down to upper bounding the moment-generating function of the intersection of two random copies of the planted bipartite subgraph. Using several interesting properties of the distribution of this intersection we were able to obtain asymptotically tight bounds.

Next, for Problem <ref>, we derive a lower bound for the adaptive setting by using a recent combinatorial approach [24], developed for the planted clique problem, and extend it to the bipartite detection problem. We then propose query versions for the scan, count, and degree tests described above, where the main challenge is choosing a set of queries to maximize the utility of each of these tests. Finally, we notice a gap that exists between the lower bound and the algorithms we proposed, and discuss the reasons and possible improvements.

§ STATISTICAL LIMITS

In this section, we determine the statistical limits of the planted bipartite subgraph detection problem, in the dense and sparse regimes. We start with Problem <ref> and then move forward to Problem <ref>.

§.§ Detecting a Planted Bipartite Graph (Problem <ref> )

Lower Bounds. The following results give necessary conditions for strong detection in the dense and sparse regimes (including the complete bipartite case of $p=1$).

Consider the $\mathsf{PDBS}{\left(n,k_{\s{R}},k_{\s{L}},p,q\right)}$ detection problem in Problem <ref>, and suppose that $q = \Theta \left(1\right)$ and $p = \Theta \left(1\right)$. Then, strong detection is impossible, if:

\begin{align}
\begin{split}
k_{\s{R}}\wedge k_{\s{L}} = o\left(\log{n^{1-o\left(1\right)}}\right)\ \s{and}\ \ \left(k_{\s{R}}\vee k_{\s{L}}\right)^2 = o\left(n\right).\label{dense regime lower bound result}
\end{split}
\end{align}

Consider the $\mathsf{PDBS}{\left(n,k_{\s{R}},k_{\s{L}},p,q\right)}$ detection problem in Problem <ref>, and suppose that $p=n^{-\alpha}$, for $\alpha \in (0,2]$, and $\vert p-q \vert = O{\left(q\right)}$. Then, strong detection is impossible, if:

\begin{align}
\begin{split}
\chi^2(p||q) = o\left(\min \left\{\frac{1}{k_{\s{R}}\wedge k_{\s{L}}}, \frac{n^2}{k_{\s{R}}^2 k_{\s{L}}^2}, \frac{n}{\left(k_{\s{R}}\vee k_{\s{L}}\right)^2}\right\}\right). \label{sparse regime lower bound result}
\end{split}
\end{align}

By the Cauchy–Schwarz inequality, the optimal risk $\mathsf{R}_n^\ast\triangleq\inf_{\phi_n}\s{R}_n(\phi_n)$ satisfies,

\begin{align}
\mathsf{R}^\ast \geq1-\frac{1} {2}\sqrt{\mathbb{E}_{\calH_0}\left[\left(\mathsf{L}\left(\s{G}\right)\right)^2\right]-1}. \label{risk lower bound sketch}
\end{align}

Therefore, in order to lower bound the optimal risk it is suffice to upper bound the second moment of $\mathsf{L}\left(\s{G}\right)$.
Then, it can be proved that,

\begin{align}
\mathbb{E}_{\calH_0}\left[\left(\mathsf{L}\left(\s{G}\right)\right)^2\right]
&\leq \mathbb{E}{\left[e^{\chi^2(p||q)\cdot {\vert e\left({\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL} \right)\vert}}\right]}.\label{L square bound sketch}
\end{align}

Note that (<ref>) is the moment generating function (MGF) of the intersection between two independent random copies of ${\mathsf{K}}_{\calR, \calL}$. Then, it is clear that

\begin{align}
\vert e\left({\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}\right)\vert = \vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert +  \vert \calR^{\left(1\right)} \cap \calL^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calR^{\left(2\right)}\vert,\label{bipartite intesection observation sketch}
\end{align}

and each of the random variables at the right-hand-side (r.h.s.) of (<ref>) is distributed as a certain Hypergeometric random variable. Using several properties of this distribution, we show that (<ref>) is upper bounded by a constant as long as (<ref>) and (<ref>) hold in the dense and sparse regimes, respectively.

Upper Bounds. We now describe our upper bounds. To that end, we propose three algorithms and analyze their performance. Define the statistics:

\begin{align}
\mathsf{Scan}{\left(\s{A}\right)} &\triangleq \max_{(\calR',\calL')\in\calS}{\sum_{\substack{i \in \calR', j \in \calL'}}\s{A}_{ij}},\label{algo:scan non-complete}\\
\mathsf{Count}{\left(\s{A}\right)}&\triangleq \sum_{i<j} \s{A}_{ij},\label{algo:count}\\
\mathsf{MaxDeg}{\left(\s{A}\right)}&\triangleq \max_{1\leq i\leq n}\sum_{j=1}^n \s{A}_{ij},\label{algo:degree}
\end{align}

where $\calS\triangleq\{(\calR',\calL')\subset\left[n\right]\times\left[n\right]:\vert \calR' \vert = k_{\s{R}},\vert \calL' \vert = k_{\s{L}}, \calR'\cap\calL'=\emptyset\}$. Then, our proposed tests are $\phi_{\s{Scan}}\triangleq\Ind\ppp{\mathsf{Scan}{\left(\s{A}\right)}\geq \tau_{\mathsf{Scan}}}$, $\phi_{\s{Count}}\triangleq\Ind\ppp{\mathsf{Count}{\left(\s{A}\right)}\geq \tau_{\mathsf{Count}}}$, and $\phi_{\s{Deg}}\triangleq\Ind\ppp{\mathsf{MaxDeg}{\left(\s{A}\right)}\geq \tau_{\mathsf{Deg}}}$. Note that the scan test exhibits an exponential computational complexity, and thus inefficient, while the count and maximum degree tests exhibit polynomial computational complexity, and hence efficient. The following result provides sufficient conditions under which the risk of each of the above tests is small.

Fix $\delta \in \left(0,1\right).$ Consider the $\mathsf{PDBS}{\left(n,k_{\s{R}},k_{\s{L}},p,q\right)}$ detection problem in Problem <ref>, and suppose that $p$ and $q$ are such that $\vert p-q \vert = O{\left(q\right)}$. Then,

* For $\tau_{\mathsf{Scan}} = k_{\s{R}} k_{\s{L}} \cdot \frac{p+q}{2}$, we have $\mathsf{R{\left(Scan\right)}} \leq \delta$, provided that:

\begin{align}
\chi^2(p||q) = \omega {\left(\frac{\log{\left(\frac{n}{k_{\s{R}}\vee k_{\s{L}}}\right)}+\frac{\log{\frac{2} {\delta}}}{k_{\s{R}}\vee k_{\s{L}}}}{k_{\s{R}}\wedge k_{\s{L}}}\right)}.
\end{align}

* For $\tau_{\mathsf{Count}}=\binom{n}{2}q + k_{\s{R}} k_{\s{L}} \frac{p-q}{2}$, we have $\mathsf{R{\left(Count\right)}} \leq \delta$, provided that:

\begin{align}
\chi^2(p||q) =\omega{\left(\frac{n^2}{ {\left(k_{\s{R}} k_{\s{L}}\right)}^2} \cdot \log{\frac{2}{\delta}}\right)}.
\end{align}

* For $\tau_{\mathsf{Deg}}=\left(n-1\right)q + k_{\s{R}}\vee k_{\s{L}} \frac{p-q}{2}$, we have $\mathsf{R{\left(MaxDeg\right)}} \leq \delta$, provided that:

\begin{align}
\chi^2(p||q) = \omega{\left(\frac{n}{ {\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2} \cdot \left(\log n + \log{\frac{2}{\delta}}\right)\right)}.
\end{align}

The following results follow from Lemma <ref>:

Consider the $\mathsf{PDBS}{\left(n,k_{\s{R}},k_{\s{L}},p,q\right)}$ detection problem in Problem <ref>, and suppose that $q = \Theta \left(1\right), p = \Theta \left(1\right)$, and $q<p$. Then, strong detection is possible, if:

\begin{align} \label{dense regime upper bound result}
\begin{split}
k_{\s{R}}\wedge k_{\s{L}} = \omega\left(\log{n^{1-o\left(1\right)}}\right)\ \s{or}\ \left(k_{\s{R}}\vee k_{\s{L}}\right)^2 = \omega\left(n\right).
\end{split}
\end{align}

The left-hand-side (l.h.s.) condition in Theorem <ref> guarantees that $\s{R}_n(\phi_{\s{Scan}})\to0$, as $n\to\infty$, while the second condition guarantees that $\s{R}_n(\phi_{\s{Deg}})\to0$, as $n\to\infty$ (in the dense regime, the count test is redundant). Note that the above result implies that in the dense regime, the statistical barrier depends on the bipartite planted graph through the quantities $k_{\s{R}}\wedge k_{\s{L}}$ and $k_{\s{R}}\vee k_{\s{L}}$, which are essentially (up to a constant), the maximal subgraph degree and the maximal vertex degree of the planted structure, respectively. In the sparse regime we have the following result.

Consider the $\mathsf{PDBS}{\left(n,k_{\s{R}},k_{\s{L}},p,q\right)}$ detection problem in Problem <ref>, and suppose that $p=n^{-\alpha}, \alpha \in (0,2], q<p$, and $\vert p-q \vert = O{\left(q\right)}$. Then, strong detection is possible, if:

\begin{align}
\begin{split}
\chi^2(p||q) = \omega\left(\min \left\{\frac{1}{k_{\s{R}}\wedge k_{\s{L}}}, \frac{n^2}{k_{\s{R}}^2 k_{\s{L}}^2}, \frac{n}{\left(k_{\s{R}}\vee k_{\s{L}}\right)^2}\right\}\right). \label{sparse regime upper bound result}
\end{split}
\end{align}

The three conditions in Theorem <ref> guarantee that the scan, count, and degree tests, achieve vanishing risk.

Phase Diagrams.
Let us summarize the statistical barriers for Problem <ref>. In the diagrams below we consider the asymptotic regime where the $x-$axis represents the number of planted vertices, i.e., $\vert v{\left({\mathsf{K}}_{\calR, \calL}\right)} \vert = k_{\s{R}}+k_{\s{L}} \triangleq k = \Theta(n^{\beta})$, and the $y-$axis represents the edges-density of the planted structure, i.e., $p = c q = \Theta(n^{-\alpha})$, where $c>1$. We assume without any loss of generality that $k_{\s{R}} \geq k_{\s{L}}$.

* Figure <ref> illustrates the balanced case where $k_{\s{R}} = \Theta(k_{\s{L}})$, for which $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(k\right)$. Interestingly, we note that the obtained phase diagram is the same as for the $\mathsf{PDS}$ problem (e.g., <cit.>), for which the maximal subgraph degree behaves the same. Note that the degree test is redundant in this case.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\alpha$;

at (, 0) [below] $1$;
at (* 0.667, 0) [below] $\frac{2}{3}$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (0, * 2) [left] $2$;
at (0, * 0.667) [left] $\frac{2}{3}$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 2 * ) – (0.667 * , 0.667 * ) – (0, 0);
[fill=red!25, draw=black] (0, 0) – (0.667 * , 0.667 * ) – (0.5 * , 0) – (0, 0);
[fill=green!25, draw=black] (0.5 * , 0) – (1 * , 2 * ) – (1 * , 0) – (0.5 * , 0);

at (* 0.4 , * 1.2) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.4 , * 0.2) $\s{\mathbf{Scan}}$;
at (* 0.8 , * 0.4) $\s{\mathbf{Count}}$;

Phase diagram for detecting the presence of a bipartite planted dense subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$, and $p = c q = \Theta(n^{-\alpha})$, in the balanced case: $k_{\s{R}} = \Theta(k_{\s{L}})$, that is, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(k\right)$.

* Figure <ref> shows  “lightly unbalanced" case, where $k_{\s{R}} = \Theta{\left(k\right)}$, and $\omega(\sqrt{k}) \leq k_{\s{L}} \leq o\left(k\right)$. In this regime, $\omega(\sqrt{k}) \leq m{\left({\mathsf{K}}_{\calR, \calL}\right)} \leq o\left(k\right)$, and we take $k_{\s{L}} = \Theta(k^{\frac{2}{3}})$.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\alpha$;

at (, 0) [below] $1$;
at (* 0.75, 0) [below] $\frac{3}{4}$;
at (* 0.667, 0) [below] $\frac{2}{3}$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (0, * 2) [left] $2$;
at (0, * 0.5) [left] $\frac{1}{2}$;
at (0, * 0.333) [left] $\frac{1}{3}$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 2 * ) – (1 * , 1 * ) – (0.667 * , 0.333 * ) – (0, 0);
[fill=red!25, draw=black] (0, 0) – (0.667 * , 0.333 * ) – (0.5 * , 0) – (0, 0);
[fill=blue!25, draw=black] (0.5 * , 0) – (1 * , 1 * ) – (1 * , 0) – (0.5 * , 0);
[fill=green!25, draw=black] (0.75 * , 0.5 * ) – (1 * , 1.333 * ) – (1 * , 1 * ) – (0.75 * , 0.5 * );

at (* 0.4 , * 1.2) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.4 , * 0.1) $\s{\mathbf{Scan}}$;
at (* 0.8 , * 0.25) $\s{\mathbf{Degree}}$;
[rotate=33] at (* 0.937, * 1) $\s{\mathbf{Count}}$;

Phase diagram for detecting the presence of a bipartite planted dense subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$, and $p = c q = \Theta(n^{-\alpha})$, in the lightly unbalanced case: $k_{\s{R}} = \Theta{\left(k\right)}$, and, for example, $k_{\s{L}} = \Theta{(k^{\frac{2}{3}})}$, and thus, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta{(k^{\frac{2}{3}})}$.

* Figure <ref> shows the “moderately unbalanced" case, where $k_{\s{R}} = \Theta{\left(k\right)}$, and $\omega(1) \leq k_{\s{L}} \leq O(\sqrt{k})$. In this regime, $\omega(1) \leq m{\left({\mathsf{K}}_{\calR, \calL}\right)} \leq O(\sqrt{k})$. Note that the count test is redundant.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\alpha$;

at (, 0) [below] $1$;
at (* 0.667, 0) [below] $\frac{2}{3}$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (0, * 2) [left] $2$;
at (0, * 0.333) [left] $\frac{1}{3}$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 2 * ) – (1 * , 1 * ) – (0.667 * , 0.333 * ) – (0, 0);
[fill=red!25, draw=black] (0, 0) – (0.667 * , 0.333 * ) – (0.5 * , 0) – (0, 0);
[fill=blue!25, draw=black] (0.5 * , 0) – (1 * , 1 * ) – (1 * , 0) – (0.5 * , 0);

at (* 0.4 , * 1.2) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.4 , * 0.1) $\s{\mathbf{Scan}}$;
at (* 0.8 , * 0.25) $\s{\mathbf{Degree}}$;

Phase diagram for detecting the presence of a bipartite planted dense subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$, and $p = c q = \Theta(n^{-\alpha})$, in the moderately unbalanced case: $k_{\s{R}} = \Theta{\left(k\right)}$, and $\omega(1) \leq k_{\s{L}} \leq O(\sqrt{k})$, and thus, $\omega(1) \leq m{\left({\mathsf{K}}_{\calR, \calL}\right)} \leq O(\sqrt{k})$.

* Finally, Figure <ref> shows the “extremely unbalanced" case, where $k_{\s{R}} = \Theta{\left(k\right)}$, and $k_{\s{L}} = \Theta\left(1\right)$. In this regime, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(1\right)$. This case is asymptotically equivalent to a planted star, that was studied in [11].
Note that both the count and the scan tests are redundant.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\alpha$;

at (, 0) [below] $1$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (0, * 2) [left] $2$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 2 * ) – (1 * , 1 * ) – (0.667 * , 0.333 * ) – (0.5 * , 0) – (0, 0);
[fill=blue!25, draw=black] (0.5 * , 0) – (1 * , 1 * ) – (1 * , 0) – (0.5 * , 0);

at (* 0.4 , * 1.2) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.8 , * 0.25) $\s{\mathbf{Degree}}$;

Phase diagram for detecting the presence of a bipartite planted dense subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$, and $p = c q = \Theta(n^{-\alpha})$, in the extremely unbalanced case: $k_{\s{R}} = \Theta{\left(k\right)}$, and $k_{\s{L}} = \Theta\left(1\right)$, and thus, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(1\right)$.

§.§ Detection Using Queries (Problem <ref>)

Lower Bounds. The following theorem is a general lower bound in the adaptive setting, i.e., when the $t^{\s{th}}$ query may depend on the outcome of previous queries.

Consider the $\mathsf{QPDBS}{\left(n,k_{\s{R}},k_{\s{L}},\mathsf{Q},p,q\right)}$ detection problem in Problem <ref>, with $q<p$. Then, strong detection is impossible using adaptive queries, if $\mathsf{Q} = o\left(n^2/(k_{\s{R}} k_{\s{L}})\right)$.

The proof of Theorem <ref> is based on a certain combinatorial argument developed in [24], for the problem of planted clique detection using queries, which we extend for the detection problem of planted bipartite graph using queries.

Upper Bounds. The following non-adaptive algorithms are query versions of those described in the previous subsection. Define the statistics:

\begin{align}
\mathsf{Scan^{Q}}{\left(\s{A}\right)} &\triangleq \max_{(\calR',\calL')\in\calS^{\mathsf{Q}}}{\sum_{\substack{i \in \calR', j \in \calL'}}\s{A}_{ij}}\label{algo:scan queries},\\
\mathsf{Count^{Q}}{\left(\s{A}\right)}&\triangleq \sum_{\left(i,j\right) \in \calQ} \s{A}_{ij}\label{algo:count queries},\\
\mathsf{MaxDeg^{Q}}{\left(\s{A}\right)}&\triangleq \max_{i \in \calS_1^{\mathsf{Q}}}\sum_{j \in \calS_2^{\mathsf{Q}}} \s{A}_{ij},\label{algo:degree queries}
\end{align}

where $\calS^{\mathsf{Q}}\triangleq\{(\calR',\calL')\subset\calS \times \calS:\vert \calR' \vert = s_0,\vert \calL' \vert = s_0, \calR'\cap\calL'=\emptyset\}$, and $\calS \subset [n], s \triangleq \vert \calS \vert$, such that $\binom{s}{2} = \mathsf{Q}$, and $s_0 \triangleq \left(1-\epsilon' \right) \frac{s k_{\s{R}} \wedge k_{\s{L}}}{n}$, for some $\epsilon'>0$; $\calQ$ is a set of some $\mathsf{Q}$ tuples: $\left(i, j\right), i \in \left[n\right], j \in \left[n\right], i<j$; $\calS_1^{\mathsf{Q}} \subseteq \left[n\right], \vert \calS_1^{\mathsf{Q}} \vert = s_1$ and $\calS_2^{\mathsf{Q}} \subseteq \left[n\right], \vert \calS_2^{\mathsf{Q}} \vert = s_2$, thus the total number of edge queries we have in (<ref>) is $s_1 \cdot s_2 = \mathsf{Q}$. Then, our proposed tests are, accordingly,   $\phi_{\s{Scan^{Q}}}\triangleq\Ind\ppp{\mathsf{Scan^{Q}}{\left(\s{A}\right)}\geq \tau_{\mathsf{Scan^{Q}}}}$, $\phi_{\s{Count^{Q}}}\triangleq\Ind\ppp{\mathsf{Count^{Q}}{\left(\s{A}\right)}\geq \tau_{\mathsf{Count^{Q}}}}$, and $\phi_{\s{Deg^{Q}}}\triangleq\Ind\ppp{\mathsf{MaxDeg^{Q}}{\left(\s{A}\right)}\geq \tau_{\mathsf{Deg^{Q}}}}$.
The following result provides sufficient conditions under which the risk of each of the above tests is small.

Consider the $\mathsf{QPDBS}{\left(n,k_{\s{R}},k_{\s{L}},\mathsf{Q},p,q\right)}$ detection problem in Problem <ref>, and suppose that $p$ and $q$ are such that $\vert p-q \vert = O{\left(q\right)}$. Then,

* For $\tau_{\mathsf{Scan^Q}} = \mathsf{Q} \frac{p+q}{2}$, we have $\mathsf{R{\left(Scan^Q\right)}} \to 0$, as $n \to \infty$, if:

\begin{align}
\mathsf{Q} = \omega \left(\frac{n^2 \log^2{n}}{\left(k_{\s{R}}\wedge k_{\s{L}}\right)^2 \chi^4(p||q)}\right).
\end{align}

* For $\tau_{\mathsf{Count^Q}}=\mathsf{Q} q + \mathsf{M}_0 \frac{p-q}{2}$, we have $\mathsf{R{\left(Count^Q\right)}} \to 0$, as $n \to \infty$, if:

\begin{align}
\mathsf{Q} = \omega\left(\frac{n^4}{k_{\s{R}}^2 k_{\s{L}}^2 \chi^2(p||q)}\right),
\end{align}

where $\mathsf{M}_0 = \left(1-\epsilon'\right) \mathsf{Q} \frac{k_{\s{R}} k_{\s{L}}}{\binom{n}{2}}$, for some $\epsilon' > 0$.

* For $\tau_{\mathsf{Deg^Q}}= s_2 q + \mathsf{N}_0 \frac{p-q}{2}$, we have $\mathsf{R{\left(Deg^Q\right)}} \to 0$, as $n \to \infty$, if $s_1 = \Omega\left(\frac{n \log{n}}{k_{\s{L}}}\right)$, $\chi^2(p||q) = \omega{\left(\frac{n \log{n}}{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2}\right)}$, and:

\begin{align}
\mathsf{Q} = \omega \left(\frac{n^3 \log^2{n}}{k_{\s{R}} k_{\s{L}} k_{\s{R}}\vee k_{\s{L}} \chi^2(p||q)}\right),
\end{align}

where $s_2 = \omega\left(\frac{n}{k_{\s{R}}}\right)$, and $\mathsf{N}_0=\left(1-\epsilon''\right) s_2 \frac{k_{\s{R}}}{n}$, for some $\epsilon'' > 0$.

The following results follow from Lemma <ref>.

Consider the $\mathsf{QPDBS}{\left(n,k_{\s{R}},k_{\s{L}},\mathsf{Q},p,q\right)}$ detection problem in Problem <ref>, where $q = \Theta \left(1\right), p = \Theta \left(1\right), q<p$. Then, strong detection is possible, if:

\begin{align} \label{dense regime queries upper bound result}
\begin{split}
\mathsf{Q} = \omega\left(\min \left \{ \frac{n^2 \log^2{n}}{\left(k_{\s{R}}\wedge k_{\s{L}}\right)^2 },\frac{n^3 \log^2{n}}{k_{\s{R}} k_{\s{L}} (k_{\s{R}}\vee k_{\s{L}}) }  \right\}\right).
\end{split}
\end{align}

The two conditions in Theorem <ref> guarantee that the scan and degree tests, achieve vanishing risk, as $n\to\infty$ (the count test is redundant in this case).

Consider the $\mathsf{QPDBS}{\left(n,k_{\s{R}},k_{\s{L}},\mathsf{Q},p,q\right)}$ detection problem in Problem <ref>, and suppose that $p=n^{-\alpha}, \alpha \in (0,2], q<p, \vert p-q \vert = O{\left(q\right)}$. Then, strong detection is possible, if:

\begin{align} \label{sparse regime queries upper bound result}
&\mathsf{Q} = \omega\left(\min \left \{ \frac{n^2}{\left(k_{\s{R}}\wedge k_{\s{L}}\right)^2 \chi^4(p||q)}, \frac{n^4}{k_{\s{R}}^2 k_{\s{L}}^2 \chi^2(p||q)}, \frac{n^3}{k_{\s{R}} k_{\s{L}} (k_{\s{R}}\vee k_{\s{L}}) \chi^2(p||q)} \cdot \calI_{n,k_{\s{R}},k_{\s{L}},p,q}  \right\}\right),
\end{align}

where $\calI_{n,k_{\s{R}},k_{\s{L}},p,q}=1$ if $\chi^2(p||q) = \omega{\left(\frac{n}{{\left(k_{\s{R}} \vee k_{\s{L}}\right)}^2}\right)}$, and $\calI_{n,k_{\s{R}},k_{\s{L}},p,q}=\infty$, otherwise.

The three conditions in Theorem <ref> guarantee that the scan, count, and degree tests, achieve vanishing risk.

Phase Diagrams.
Let us summarize the statistical barriers for Problem <ref>. In the diagrams below we consider the asymptotic regime where the $x-$axis represents the number of planted vertices, i.e., $v{\left({\mathsf{K}}_{\calR, \calL}\right)} = k_{\s{R}}+k_{\s{L}} \triangleq k = \Theta(n^{\beta})$, and the $y-$axis represents the number of queries, i.e., $\mathsf{Q} = \Theta(n^{\gamma})$, where $\gamma \in \left[0,2\right]$. Moreover, we only show the diagrams in the dense regime, where $p=\Theta\left(1\right), q=\Theta\left(1\right)$. We assume without any loss of generality that $k_{\s{R}} \geq k_{\s{L}}$.

* Figure <ref> shows the balanced case, where $k_{\s{R}} = \Theta(k_{\s{L}})$, implying that $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(k\right)$. As in the previous subsection, the obtained phase diagram is the same as in the $\mathsf{PDS}$ problem (see <cit.>), where the maximal subgraph degree is also $\Theta\left(k\right)$. Note that in the balanced case, the bounds we have derived are sharp.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\gamma$;

at (, 0) [below] $1$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (0, * 2) [left] $2$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 0) – (0, 0);
[fill=red!25, draw=black] (0, 2 * ) – (0.5 * , 2 * ) – (0.5 * , 1.5 * ) – (1 * , 0)  – (0, 2 * );
[fill=blue!25, draw=black] (0.5 * , 1.5 * ) – (0.5 * , 2 * ) – (1 * , 2 * ) – (1 * , 0) – (0.5 * , 1.5 * );

at (* 0.3 , * 0.6) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.43 , * 1.4) $\s{\mathbf{Scan}}$;
at (* 0.8 , * 1.4) $\s{\mathbf{Degree}}$;

Phase diagram for detecting the presence of a planted bipartite subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$, and the number of edge queries $\mathsf{Q} = \Theta(n^{\gamma})$, in the balanced case: $k_{\s{R}} = \Theta(k_{\s{L}})$, that is, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(k\right)$.

* Figure <ref> shows the moderately unbalanced case, where $k_{\s{R}} = \Theta{\left(k\right)}$, and $\Omega(k^{\epsilon}) \leq k_{\s{L}} \leq o\left(k\right)$, for some $\epsilon \in \left(0,1\right)$. In this regime, $\Omega(k^{\epsilon}) \leq m{\left({\mathsf{K}}_{\calR, \calL}\right)} \leq o\left(k\right)$, and we take $k_{\s{L}} = \Theta{(k^{\frac{1}{2}})}$. Note that there exists a regime where the degree test is better the scan test, and vise-versa.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\gamma$;

at (, 0) [below] $1$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (* 0.667, 0) [below] $\frac{2}{3}$;
at (0, * 2) [left] $2$;
at (0, * 1.333) [left] $\frac{4}{3}$;
at (0, * 0.5) [left] $\frac{1}{2}$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 0.5 * ) – (1 * , 0) – (0, 0);
[fill=red!25, draw=black] (0, 2 * ) – (0.5 * , 2 * ) – (0.5 * , 1.75 * ) –(0.667 * , 1.333 * )  – (0, 2 * );
[fill=blue!25, draw=black] (0.5 * , 1.75 * ) – (0.5 * , 2 * ) – (1 * , 2 * ) – (1 * , 0.5 * ) – (0.5 * , 1.75 * );

at (* 0.4 , * 0.7) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.4 , * 1.8) $\s{\mathbf{Scan}}$;
at (* 0.8 , * 1.4) $\s{\mathbf{Degree}}$;
[rotate=-18] at (* 0.6, * 1.27) $\s{\mathbf{Unknown}}$;

Phase diagram for detecting the presence of a planted bipartite subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$ and the number of edge queries $\mathsf{Q} = \Theta(n^{\gamma})$  in the moderately unbalanced case: $k_{\s{R}} = \Theta(k)$, and, for example, $k_{\s{L}} = \Theta(k^{\frac{1}{2}})$, that is, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(k^{\frac{1}{2}}\right)$.

* Finally, we show in Figure <ref>) the extremely unbalanced case, where $k_{\s{R}} = \Theta{\left(k\right)}$, and $k_{\s{L}} = \Theta\left(1\right)$. In this regime, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} = \Theta\left(1\right)$. Note that the scan test is redundant.

every node=[font=]
+ 0.1
* 2 + 0.1

[->] (,) – (,) node[right] $\beta$;
[->] (,) – (,) node[above] $\gamma$;

at (, 0) [below] $1$;
at (* 0.5, 0) [below] $\frac{1}{2}$;
at (0, * 2) [left] $2$;
at (0, * 1) [left] $1$;
at (0, 0) [left] $0$;

[fill=gray!25, draw=black] (0, 0) – (0, 2 * ) – (1 * , 0) – (0, 0);
[fill=blue!25, draw=black] (0.5 * , 2 * ) – (1 * , 2 * ) – (1 * , 1 * ) – (0.5 * , 2 * );
[fill=white!25, draw=black] (0, 2 * ) – (0.5 * , 2 * ) – (1 * , 1 * ) – (1 * , 0) – (0, 2 * );

at (* 0.3 , * 0.5) $\s{\mathbf{Statistically \ \ Impossible}}$;
at (* 0.85 , * 1.6) $\s{\mathbf{Degree}}$;
at (* 0.65 , * 1.2) $\s{\mathbf{Unknown}}$;

Phase diagram for detecting the presence of a planted bipartite subgraph, as a function of $k \triangleq k_{\s{R}}+k_{\s{L}} = \Theta(n^{\beta})$ and the number of edge queries $\mathsf{Q} = \Theta(n^{\gamma})$  in the extremely-unbalanced case: $k_{\s{R}} = \Theta(k)$, and $k_{\s{L}} = \Theta\left(1\right)$, that is, $m{\left({\mathsf{K}}_{\calR, \calL}\right)} =  \Theta\left(1\right)$.

Bounds Gap. It can be observed that our bounds for Problem <ref> are not tight in general. One exception is the balanced case in the dense regime, where our bounds are tight (up to a logarithmic factor). Note that this is exactly the case in which the maximal subgraph degree is asymptotically the same as that of a clique, where [24] obtained sharp detection bounds. Below are two possible reasons for the aforementioned gap.

* Theorem <ref> proof technique. In the lower bound proof, there is a loose transition, which we conjecture is the cause for the gap between the bounds. Specifically, the transition is an upper bound on the size of the set of sets-tuples such that there was a pair query among these first $\mathsf{Q}$ pair queries that queried at least one pair from this sets-tuple. We suspect that this bound is loose.

* Adaptive vs. non-adaptive. Another possible explanation for the gap is the fact that our algorithms are not adaptive, whereas our lower bound hold for adaptive schemes as well. That is, it is possible that there exist adaptive algorithms, with better performance than the ones we proposed, which will match our bound. However, we conjecture that this is not the reason for the gap.

§ PROOFS

§.§ Proof of Theorems <ref> and <ref>

We will prove that the risk of any algorithm can be lower bounded by some $\epsilon > 0$.  It is well known that the optimal test $\phi^\ast$ that minimizes the risk is the likelihood ratio test defined as:

\begin{align}
\phi^\ast\left(\s{G}\right) \triangleq \begin{cases}
1,\ &\text{if }\mathsf{L}\left(\s{G}\right) \geq 1\\
0,\ &\text{otherwise},
\end{cases}
\end{align}

where $\mathsf{L}\left(\s{G}\right) \triangleq \frac{\pr_{\calH_1}\left(\s{G}\right)}{\pr_{\calH_0}\left(\s{G}\right)}$.
The optimal risk, $\mathsf{R}\left(\phi^\ast\left(\s{G}\right)\right) \triangleq \mathsf{R}^\ast$, can be lower bounded using the Cauchy–Schwarz inequality as follows,

\begin{align}
\mathsf{R}^\ast &= 1-\mathsf{d_{TV}}\left(\pr_{\calH_0}, \pr_{\calH_1}\right)\\
&=1-\frac{1}{2}\mathbb{E}_{\calH_0}\vert\mathsf{L}\left(\s{G}\right)-1\vert   \\
&\geq1-\frac{1} {2}\sqrt{\mathbb{E}_{\calH_0}[\left(\mathsf{L}\left(\s{G}\right)\right)^2]-1}. \label{risk lower bound}
\end{align}

Thus, it is sufficient to prove that $\mathbb{E}_{\calH_0}\left[(\mathsf{L}\left(\s{G}\right)\right)^2]$ lies in the interval $(1,5)$. Next, note that the following holds:

\begin{align}
\mathbb{E}_{\calH_0}\left[\left(\mathsf{L}\left(\s{G}\right)\right)^2\right] &= \sum_{\s{G}'} \pr_{\calH_0}\left(\s{G}'\right) \cdot \frac{\left(\pr_{\calH_1}\left(\s{G}'\right)\right)^2}{\left(\pr_{\calH_0}\left(\s{G}'\right)\right)^2}    \\
&=\mathbb{E}_{{\mathsf{K}}^{\left(1\right)}_{\calR, \calL},{\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\left[\sum_{\s{G}'}{\pr_{\calH_0}\left(\s{G}'\right)} \cdot \frac{\pr_{\calH_1}\left(\s{G}' \vert {\mathsf{K}}^{\left(1\right)}_{\calR, \calL}\right) \cdot \pr_{\calH_1}\left(\s{G}' \vert {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}\right)}{\left(\pr_{\calH_0}\left(\s{G}'\right)\right)^2}\right],
\end{align}

where ${\mathsf{K}}^{\left(1\right)}_{\calR, \calL},{\mathsf{K}}^{\left(2\right)}_{\calR, \calL}$ are independent and uniformly distributed over all ${\mathsf{K}}_{\calR, \calL}$ copies. For $(i,j)\in\binom{\left[n\right]}{2}$, let $f(\s{A}_{ij}) \triangleq \p{\frac{p}{q}}^{\s{A}_{ij}}\p{\frac{1-p}{1-q}}^{\s{A}_{ij}}$, where $\s{A}$ is the adjacency matrix. Then,

\begin{align}
&\mathbb{E}_{{\mathsf{K}}^{\left(1\right)}_{\calR, \calL},{\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\left[\sum_{\s{G}'}{\pr_{\calH_0}\left(\s{G}'\right)} \cdot \frac{\pr_{\calH_1}\left(\s{G}' \vert {\mathsf{K}}^{\left(1\right)}_{\calR, \calL}\right) \cdot \pr_{\calH_1}\left(\s{G}' \vert {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}\right)}{\left(\pr_{\calH_0}\left(\s{G}'\right)\right)^2}\right]    \\ &=\mathbb{E}_{{\mathsf{K}}^{\left(1\right)}_{\calR, \calL},{\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\left[\mathbb{E}_{\calH_0}\left[ \frac{\pr_{\calH_1}\left(\s{G}' \vert {\mathsf{K}}^{\left(1\right)}_{\calR, \calL}\right) \cdot \pr_{\calH_1}\left(\s{G}' \vert {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}\right)}{\pr_{\calH_0}\left(\s{G}'\right) \cdot \pr_{\calH_0}\left(\s{G}'\right)}\right]\right]    \\
&=\mathbb{E}_{{\mathsf{K}}^{\left(1\right)}_{\calR, \calL},{\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\left[\prod_{(i,j) \in {\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\mathbb{E}_{\calH_0}\left[\left(f\left(\s{A}_{ij}\right)\right)^2\right] \cdot \prod_{(i,j) \in {\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \triangle {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\mathbb{E}_{\calH_0}\left[f\left(\s{A_{ij}}\right)\right] \right]    \\
&=\mathbb{E}_{{\mathsf{K}}^{\left(1\right)}_{\calR, \calL},{\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\left[\prod_{e \in {\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}}\left(1+\chi^2(p||q)\right) \cdot 1 \right]    \\
&=\mathbb{E}\left[\left(1+\chi^2(p||q)\right)^{\vert e\left({\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}
\right)\vert}\right] \label{L square equal} \\
&\leq \mathbb{E}{\left[e^{\chi^2(p||q)\cdot {\vert e\left({\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL} \right)\vert}}\right]}. \label{L square bound}
\end{align}

Thus, in order to lower bound the risk it is suffice to upper bound (<ref>) by some constant $c<5$. Note that (<ref>) is simply the MGF of the intersection between two random copies of ${\mathsf{K}}_{\calR, \calL}$. Next, our main observation is the fact that

\begin{align}
\vert e\left({\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}\right)\vert = \vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert + \vert \calR^{\left(1\right)} \cap \calL^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calR^{\left(2\right)}\vert,
\end{align}

which follows from the structure of bipartite graphs. Then, by Cauchy–Schwartz inequality,

\begin{align}
&\mathbb{E}^2{\left[e^{\chi^2(p||q) \vert e\left({\mathsf{K}}^{\left(1\right)}_{\calR, \calL} \cap {\mathsf{K}}^{\left(2\right)}_{\calR, \calL}\right)\vert}\right]} = \mathbb{E}^2{\left[e^{\chi^2(p||q) \left( \vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert + \vert \calR^{\left(1\right)} \cap \calL^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \right)}\right]} \\
&\hspace{3cm}\leq \mathbb{E}{\left[e^{2 \chi^2(p||q) \vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert}\right]} \cdot \mathbb{E}{\left[e^{2\chi^2(p||q) \vert \calR^{\left(1\right)} \cap \calL^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calR^{\left(2\right)}\vert}\right]} \label{Cauchy–Schwarz Sparse Full}.
\end{align}

Let us start by bounding the first term in (<ref>). Since $\calR^{\left(1\right)}$ and $\calR^{\left(2\right)}$ are chosen uniformly at random, note that given $H\triangleq\vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert$, we have,

\begin{align}
\vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \preceq \mathsf{Hypergeometric}\left(n-H,k_{\s{R}},k_{\s{R}}\right).
\end{align}

Thus, since we assume that $k_{\s{R}} + k_{\s{L}} = o\left(n\right)$, the above is stochastically dominated by $\mathsf{Binomial}\left(k_{\s{R}},c_1 \cdot \frac{k_{\s{R}}}{n}\right)$, for some constant $c_1 >0$, for all possible values of $H$ (clearly $H \leq k_{\s{L}}$). Therefore, by the law of total probability we get,

\begin{align} \label{after CS start}
\mathbb{E}{\left[e^{2 \chi^2(p||q) \vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert}\right]} &= \mathbb{E}{\left[\mathbb{E}{\left[e^{2 \chi^2(p||q) \vert \calR^{\left(1\right)} \cap \calR^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert} \mid  \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert = H\right]}\right]} \\
&\leq \mathbb{E}{\left[e^{2 \chi^2(p||q) \mathsf{Binomial}\left(k_{\s{R}},c_1 \cdot \frac{k_{\s{R}}}{n}\right) \cdot \vert \calL^{\left(1\right)} \cap \calL^{\left(2\right)}\vert} \right]} \\
&\leq \mathbb{E}{\left[e^{2 \chi^2(p||q) \mathsf{Binomial}\left(k_{\s{R}},c_1 \cdot \frac{k_{\s{R}}}{n}\right) \cdot \mathsf{Binomial}\left(k_{\s{L}},c_2 \cdot \frac{k_{\s{L}}}{n}\right)} \right]} \\
&\triangleq \mathbb{E}{\left[e^{2 \chi^2(p||q) B_1 \cdot B_2} \right]}, \label{MGF B1 B2}
\end{align}

where $B_1 \triangleq \mathsf{Binomial}\left(k_{\s{R}},c_1 \cdot \frac{k_{\s{R}}}{n}\right)$ and $B_2 \triangleq \mathsf{Binomial}\left(k_{\s{L}},c_2 \cdot \frac{k_{\s{L}}}{n}\right)$, for some constants $c_1>0$, $c_2 > 0$. Similarly, the second term in (<ref>) can be bounded as follows:

\begin{align}
\mathbb{E}{\left[e^{2 \chi^2(p||q) \vert \calR^{\left(1\right)} \cap \calL^{\left(2\right)}\vert \cdot \vert \calL^{\left(1\right)} \cap \calR^{\left(2\right)}\vert}\right]} \leq \mathbb{E}{\left[e^{2 \chi^2(p||q) B_3 \cdot B_4} \right]},
\end{align}

where $B_3 \triangleq \mathsf{Binomial}\left(k_{\s{R}},c_3 \cdot \frac{k_{\s{L}}}{n}\right)$ and $B_4 \triangleq \mathsf{Binomial}\left(k_{\s{L}},c_4 \cdot \frac{k_{\s{R}}}{n}\right)$, for some constants $c_3>0$, $c_4 > 0$.
From now on, we assume without any loss of generality that $k_{\s{R}} \geq k_{\s{L}}$. Next, we consider the dense and the sparse regimes separately.

§.§.§ Dense Regime: Theorem <ref>

We have:

\begin{align}
\mathbb{E}{\left[e^{2 \chi^2(p||q) B_1 \cdot B_2} \right]} &\leq \mathbb{E}{\left[e^{2 \chi^2(p||q) B_1 \cdot k_{\s{L}}} \right]}\\
&={\left(1+c_1 \frac{k_{\s{R}}}{n} \left(e^{2 \chi^2(p||q) k_{\s{L}}}-1\right)\right)}^{k_{\s{R}}},\label{eqn:by2}
\end{align}

where the inequality is because $B_2 \leq k_{\s{L}}$, and the equality follows from the MGF of the binomial random variable $B_1$. Now, since $2^{\frac{1}{k_{\s{R}}}}-1 \geq \frac{\log{2}}{k_{\s{R}}}$, equation (<ref>) is upper bounded by, say, 2, if

\begin{align}
c_1 \frac{k_{\s{R}}}{n} \left(e^{2 \chi^2(p||q) k_{\s{L}}}-1\right) \leq \frac{\log{2}}{k_{\s{R}}},
\end{align}

which is equivalent to

\begin{align}
2 \chi^2(p||q) k_{\s{L}} \leq \log{\left(1+\frac{n}{{k^2_{\s{R}}}} \frac{\log{2}}{c_1}\right)}. \label{dense full cond}
\end{align}

Since $\chi^2(p||q) = \Theta\left(1\right)$ in the dense regime, the last condition holds
when ${k^2_{\s{R}}} = o\left(n\right)$ if,

\begin{align}
k_{\s{L}} \leq \tilde{C} \log{\left(n^{1-o\left(1\right)}\right)},\label{dense explicit cond}
\end{align}

for some constant $\tilde{C}>0$. On the other hand, if ${k^2_{\s{R}}} = \omega\left(n\right)$, we get that (<ref>) can never hold true. Next, for the second term of (<ref>), we can repeat (<ref>)–(<ref>), and get that

\begin{align}
2 \chi^2(p||q) k_{\s{L}} \leq \log{\left(1+\frac{n}{k_{\s{R}} {k_{\s{L}}}} \frac{\log{2}}{c_3}\right)},
\end{align}

which is a weaker condition compared to (<ref>), since $k_{\s{R}} \geq k_{\s{L}}$. Combining the above, we conclude that the optimal risk is positive if ${k_{\s{R}}}^2 = o\left(n\right)$, and (<ref>) hold. Removing the assumption that $k_{\s{R}} \geq k_{\s{L}}$, these conditions can be expressed as,

\begin{align}
k_{\s{R}}\wedge k_{\s{L}} = o\left(\log{\left(n^{1-o\left(1\right)}\right)}\right), \text{ and } \left(k_{\s{R}}\vee k_{\s{L}}\right)^2 = o\left(n\right),
\end{align}

as claimed.

§.§.§ Sparse Regime: Theorem <ref>

In the sparse regime, i.e., when $p=n^{-\alpha}$, for $\alpha \in (0,2]$, and $\vert p-q \vert = O{\left(q\right)}$, we ignore logarithmic factors as they are insignificant, relatively to $p$. First, for reasons that will become clear shortly, assume that

\begin{align}
\label{lower bound sparse full cond 1}
2\chi^2(p||q) k_{\s{L}} \leq 1.
\end{align}

Substituting the MGF of the binomial random variable $B_1$ in (<ref>), and get:

\begin{align}
\mathbb{E}{\left[e^{2 \chi^2(p||q) B_1 \cdot B_2} \right]} &= \mathbb{E}{\left[\left(1+c_1 \frac{k_{\s{R}}}{n} \left(e^{ 2 \chi^2(p||q) B_2}-1\right)\right)^{k_{\s{R}}}\right]}.
\end{align}

Then, note that $B_2 \leq k_{\s{L}}$, and thus, combining with (<ref>), we have $\chi^2(p||q) B_2 \leq 1$. Therefore, using the fact that $e^x - 1\leq x + x^2$ for $x < 1.79$, we obtain

\begin{align}
&\mathbb{E}{\left[\left(1+c_2 \frac{k_{\s{R}}}{n} \left(e^{ 2 \chi^2(p||q) B_2}-1\right)\right)^{k_{\s{R}}}\right]} \nonumber\\
&\hspace{2.5cm}\leq \mathbb{E}{\left[\left(1+c_1 \frac{k_{\s{R}}}{n} \left(2 \chi^2(p||q) B_2 + \left(2 \chi^2(p||q) B_2\right)^2\right)\right)^{k_{\s{R}}}\right]} \\
&\hspace{2.5cm}\leq \mathbb{E}{\left[\left(1+c_1 \frac{k_{\s{R}}}{n} 4 \chi^2(p||q) B_2\right)^{k_{\s{R}}}\right]}.
\end{align}

Next, using the fact that $1+x\leq\exp(x)$, for any $x\geq0$, and the MGF of the binomial random variable $B_2$, we get

\begin{align}
\mathbb{E}{\left[e^{c_1 \frac{k_{\s{R}}^2}{n} \left(4 \chi^2(p||q) B_2 \right)}\right]} = \left(1+c_2\frac{k_{\s{L}}}{n}\left(e^{c_1 \frac{k_{\s{R}}^2}{n} 4 \chi^2(p||q)}-1\right)\right)^{k_{\s{L}}} \label{after two MGFs}.
\end{align}

Since $2^{\frac{1}{k_{\s{L}}}}-1 \geq \frac{\log{2}}{k_{\s{L}}}$, equation (<ref>) is upper bounded by, say, 2, if

\begin{align} \label{after CS first term}
\chi^2(p||q)\leq \frac{1}{4 c_1} \cdot \frac{n}{k_{\s{R}}^2} \cdot {\log{\left(1+\frac{n}{k_{\s{L}}^2}  \frac{\log 2}{c_2}\right)}}.
\end{align}

Next, for the second term in (<ref>), we repeat the same arguments (<ref>)–(<ref>) and (<ref>)–(<ref>), and get the condition that,

\begin{align} \label{after CS second term}
\chi^2(p||q)\leq \frac{1}{4 c_3} \cdot \frac{n}{k_{\s{R}} k_{\s{L}}} \cdot {\log{\left(1+\frac{n}{k_{\s{R}} k_{\s{L}}}  \frac{\log 2}{c_4}\right)}}.
\end{align}

Now, if $k_{\s{R}} k_{\s{L}} = O\left(n\right)$, then $k_{\s{L}}^2 = O\left(n\right)$, and we get from (<ref>) and (<ref>) the sufficient condition,

\begin{align} \label{lower bound sparse full cond 3}
\chi^2(p||q)\leq C' \cdot \frac{n}{k_{\s{R}}^2},
\end{align}

for some constant $C' > 0$. On the other hand, if $k_{\s{R}} k_{\s{L}} = \omega\left(n\right)$, using $x < \log\left(1+x\right)$, for $x\geq0$, we get from (<ref>) and (<ref>) the condition

\begin{align} \label{lower bound sparse full cond 2}
\chi^2(p||q)\leq C'' \cdot \frac{n}{k_{\s{R}}^2 k_{\s{L}}^2},
\end{align}

for some constant $C'' > 0$. Combining (<ref>), (<ref>), (<ref>), and removing the assumption that $k_{\s{R}} \geq k_{\s{L}}$, we obtain that the optimal risk is positive if,

\begin{align}
\chi^2(p||q) \leq C \cdot \min \left\{\frac{1}{k_{\s{R}}\wedge k_{\s{L}}},\frac{n^2}{k_{\s{R}}^2 k_{\s{L}}^2},\frac{n}{\left(k_{\s{R}}\vee k_{\s{L}}\right)^2}\right\},
\end{align}

for some constant $C > 0$, as claimed.

§.§ Proof of Lemma <ref>

§.§.§ Scan Test

Under $\calH_0$, for any $\calR' \subset \left[n\right], \vert \calR' \vert = k_{\s{R}}, \calL' \subset \left[n\right], \vert \calL' \vert = k_{\s{L}}, \calR' \cap \calL' = \emptyset$ we have that $\sum_{\substack{i \in \calR', j \in \calL'}}\s{A}_{ij} \sim \mathsf{Binomial}{\left(k_{\s{R}} k_{\s{L}}, q\right)}$. Recalling the definition of $\mathsf{Scan}{\left(\s{A}\right)}$, note that the maximum is taken over a set of size $\binom{n}{k_{\s{R}}}\binom{n-k_{\s{R}}}{k_{\s{L}}}$, which can be bounded as follows,

\begin{align}
\binom{n}{k_{\s{R}}}\binom{n-k_{\s{R}}}{k_{\s{L}}} \leq \binom{n}{k_{\s{R}}}\binom{n}{k_{\s{L}}} \leq \left(\frac{3n}{k_{\s{R}}}\right)^{k_{\s{R}}} \left(\frac{3n}{k_{\s{L}}}\right)^{k_{\s{L}}} \leq \left(\frac{3n}{k_{\s{R}}\vee k_{\s{L}} }\right)^{2 k_{\s{R}}\vee k_{\s{L}}},
\end{align}

where the last inequality is because $\left(\frac{n}{x}\right)^x$ is monotonically non-decreasing if $x=o\left(n\right)$. Thus, by the union bound and Bernstein's inequality we have:

\begin{align}
\pr_{\calH_0}{\left(\mathsf{Scan}{\left(\s{A}\right)} \geq \tau_{\mathsf{Scan}}\right)} &\leq \sum_{\substack{\calR' \subset \left[n\right], \vert \calR' \vert = k_{\s{R}} \\ \calL' \subset \left[n\right], \vert \calL' \vert = k_{\s{L}} \\ \calR' \cap \calL' = \emptyset}}{\pr_{\calH_0}{\left[\sum_{\substack{i \in \calR', j \in \calL'}}\s{A}_{ij} \geq \tau_{\mathsf{Scan}}\right]}}    \\
&\leq \left(\frac{3n}{k_{\s{R}}\vee k_{\s{L}} }\right)^{2 k_{\s{R}}\vee k_{\s{L}}} \cdot\exp{\left(-
\frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2 \cdot {\left(p-q\right)}^2/4}{2k_{\s{R}} k_{\s{L}} q+k_{\s{R}} k_{\s{L}}\cdot{\left(p-q\right)}/3}\right)}    \\
&\leq \exp{\left(k_{\s{R}}\vee k_{\s{L}} \cdot \log{\left(\frac{n}{k_{\s{R}}\vee k_{\s{L}}}\right)}-C'\cdot k_{\s{R}} k_{\s{L}} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C' > 0$. On the other hand, Under $\calH_1$, if ${\mathsf{K}}_{\calR, \calL}$ is planted,
there exist some sets $\calR^{\ast}, \calL^{\ast}$ such that $\sum_{\substack{i \in \calR^{\ast}, j \in \calL^{\ast}}}\s{A}_{ij} \sim \mathsf{Binomial}{\left(k_{\s{R}} k_{\s{L}}, p\right)}$. Therefore, by the multiplicative Chernoff's bound, we have:

\begin{align}
\pr_{\calH_1}{\left(\mathsf{Scan}{\left(\s{A}\right)} \leq \tau_{\mathsf{Scan}}\right)} &\leq \pr_{\calH_1}{\left[\sum_{\substack{i \in \calR^{\ast}, j \in \calL^{\ast}}} \s{A}_{ij} \leq \tau_{\mathsf{Scan}}\right]}    \\
&\leq \exp{\left(-
\frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2 \cdot {\left(p-q\right)}^2/4}{2k_{\s{R}} k_{\s{L}} p}\right)}   \\
&\leq \exp{\left(-C''\cdot k_{\s{R}} k_{\s{L}} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C'' > 0$. Thus, we obtain that:

\begin{align}
\mathsf{R{\left(Scan\right)}} \leq 2 \cdot \exp{\left(k_{\s{R}}\vee k_{\s{L}} \cdot \log{\left(\frac{n}{k_{\s{R}}\vee k_{\s{L}}}\right)}-C'\cdot k_{\s{R}} k_{\s{L}} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

which is less than $\delta$ provided that:

\begin{align}
\chi^2(p||q)=\frac{{\left(p-q\right)}^2}{q\left(1-q\right)} &\geq C {\left[\frac{k_{\s{R}}\vee k_{\s{L}}}{k_{\s{R}} k_{\s{L}}} \cdot \log{\left(\frac{n}{k_{\s{R}}\vee k_{\s{L}}}\right)}+\frac{\log{\frac{2} {\delta}}}{k_{\s{R}} k_{\s{L}}}\right]}\\&=C
{\left[\frac{\log{\left(\frac{n}{k_{\s{R}}\vee k_{\s{L}}}\right)}+\frac{\log{\frac{2} {\delta}}}{k_{\s{R}}\vee k_{\s{L}}}}{k_{\s{R}}\wedge k_{\s{L}}}\right]},
\end{align}

for some $C>0$, which completes the proof.

§.§.§ Count Test

Under $\calH_0$, we have $\mathsf{Count}{\left(\s{A}\right)} \sim \mathsf{Binomial}{\left(\binom{n}{2}, q\right)}$. Therefore, by Bernstein's inequality,

\begin{align}
\pr_{\calH_0}{\left(\mathsf{Count}{\left(\s{A}\right)} \geq \tau_{\mathsf{Count}}\right)}
&\leq \exp{\left(-
\frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2 \cdot {\left(p-q\right)}^2/4}{2{\binom{n}{2}}q+k_{\s{R}} k_{\s{L}}\cdot{\left(p-q\right)}/3}\right)}    \\
&\leq \exp{\left(-C'\cdot \frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2}{n^2} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C' > 0$. On the other hand, under $\calH_1$, the statistics $\mathsf{Count}{\left(\s{A}\right)}$ distributed as the
independent sum of $\mathsf{Binomial}{\left(k_{\s{R}} k_{\s{L}}, p\right)}$ and $\mathsf{Binomial}{\left(\binom{n}{2} - k_{\s{R}} k_{\s{L}}, q\right)}$. Therefore, by the multiplicative Chernoff's bound, we have:

\begin{align}
\pr_{\calH_1}{\left(\mathsf{Count}{\left(\s{A}\right)} \leq \tau_{\mathsf{Count}}\right)}
&\leq \exp{\left(-
\frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2 \cdot {\left(p-q\right)}^2/4}{2{\binom{n}{2}}q+2\cdot k_{\s{R}} k_{\s{L}}\cdot{\left(p-q\right)}}\right)}    \\
&\leq \exp{\left(-C''\cdot \frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2}{n^2} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C'' > 0$. Thus, we obtain that:

\begin{align}
\mathsf{R{\left(Count\right)}} \leq 2 \cdot \exp{\left(-C\cdot \frac{{\left(k_{\s{R}} k_{\s{L}}\right)}^2}{n^2} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

which is less than $\delta$ provided that:

\begin{align}
\chi^2(p||q)=\frac{{\left(p-q\right)}^2}{q\left(1-q\right)} \geq \frac{n^2}{C\cdot {\left(k_{\s{R}} k_{\s{L}}\right)}^2} \cdot \log{\frac{2}{\delta}},
\end{align}

for some $C>0$, which completes the proof.

§.§.§ Degree Test

Under $\calH_0$ we have $\sum_{j} \s{A}_{ij} \sim \mathsf{Binomial}{\left(n-1, q\right)}$, therefore by the union bound and Bernstein's inequality, we have:

\begin{align}
\pr_{\calH_0}{\left(\mathsf{MaxDeg}{\left(\s{A}\right)} \geq \tau_{\mathsf{Deg}}\right)}
&\leq n \cdot \exp{\left(-
\frac{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2 \cdot {\left(p-q\right)}^2/4}{2\left(n-1\right)q+k_{\s{R}}\vee k_{\s{L}}\cdot{\left(p-q\right)}/3}\right)}    \\
&\leq \exp{\left(\log{n}-C'\cdot \frac{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2}n \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C' > 0$. On the other hand, under $\calH_1$, there is at least one row $i^\ast$ such that $\sum_{j} \s{A}_{i^\ast j}$ can be represented as the
independent sum of $\mathsf{Binomial}{\left(k_{\s{R}}\vee k_{\s{L}}, p\right)}$ and $\mathsf{Binomial}{\left(n-1- k_{\s{R}}\vee k_{\s{L}}, q\right)}$. Therefore, by the multiplicative Chernoff's bound, we have:

\begin{align}
\pr_{\calH_1}{\left(\mathsf{MaxDeg}{\left(\s{A}\right)} \leq \tau_{\mathsf{Deg}}\right)}
&\leq \exp{\left(-
\frac{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2 \cdot {\left(p-q\right)}^2/4}{2\left(n-1\right)q+2\cdot k_{\s{R}}\vee k_{\s{L}}\cdot{\left(p-q\right)}}\right)}    \\
&\leq \exp{\left(-C''\cdot \frac{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2}n \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C'' > 0$. Thus, we obtain that:

\begin{align}
\mathsf{R{\left(Deg\right)}} \leq 2 \cdot \exp{\left(\log{n}-C\cdot \frac{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2}n \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

which is less than $\delta$ provided that:

\begin{align}
\chi^2(p||q)=\frac{{\left(p-q\right)}^2}{q\left(1-q\right)} \geq \frac{n}{C\cdot {\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2} \cdot \left(\log n + \log{\frac{2}{\delta}}\right),
\end{align}

for some $C>0$, which completes the proof.

§.§ Proof of Theorem <ref>

We follow the technique used in [24], developed for the planted clique case, with some modifications.

§.§.§ Proof Step 1: Reduction

Let us define a new simpler hypothesis testing problem $(\tilde{\mathcal{H}}_{0}, \tilde{\mathcal{H}}_{1})$ and relate it to the original hypothesis testing problem. Under both $\tilde{\mathcal{H}}_{0}$ and $\tilde{\mathcal{H}}_{1}$ the $n$ elements are “right-handed" or “left-handed" or “ambidextrous" according to the following role.
Under $\tilde{\mathcal{H}}_{0}$ all $n$ elements are ambidextrous. Under $\tilde{\mathcal{H}}_{1}$, on the other hand, we do the following:

* Pick two disjoint sets $\calR$, $\calL$ uniformly at random from $\left[n\right]$. The elements in $\calR$ are right-handed and the elements in $\calL$ are left-handed.

* The leftover elements, i.e., $\left[n\right] \backslash \left(\calR \cup \calL\right)$ are ambidextrous.

Given the above hypothesis testing problem, we consider query mechanisms that evolve dynamically over $\mathsf{Q}$ queries in the following form: in the $t \in[\mathsf{Q}]$ query, the mechanism chooses a pair of elements $\left(\tilde{i}_{t}, \tilde{j}_{t}\right)$, and asks the oracle whether we have a right-left pair, i.e., $\tilde{i}_{t} \in \calR, \tilde{j}_{t} \in \calL$ or $\tilde{j}_{t} \in \calR, \tilde{i}_{t} \in \calL$.
If we have a right-left pair, the query response is “yes", otherwise, the response is “no". Below, we refer to the above type of queries as pair queries (note to the difference between this type of queries and the edge queries in the original problem). Using those $\mathsf{Q}$ queries, the detection algorithm outputs a decision in $\{0,1\}$. Note that the main difference between the above hypothesis testing problem and the original one is that in the former the graph structure in the original problem is completely removed.

Note that there is a direct correspondence between the above $(\tilde{\mathcal{H}}_{0}, \tilde{\mathcal{H}}_{1})$ detection problem, and our original problem. Specifically, given the answer to a pair query,
the answer to an edge query can be simulated as follows:

* If the pair query response is “yes”, then the answer to the corresponding edge query is $"1"$ with probability $p$, and $"0"$, otherwise.

* If the pair query response is “no”, then the answer to the corresponding edge query is $"1"$ with probability $q$, and $"0"$, otherwise.

Thus, for any algorithm $\calA$ that makes $\mathsf{Q}$ adaptive edge queries in Problem <ref>, there exists a corresponding algorithm $\tilde{\calA}$ that makes at most $\mathsf{Q}$ adaptive pair queries, in $(\tilde{\mathcal{H}}_{0}, \tilde{\mathcal{H}}_{1})$, with some probability $\delta > 0$.

§.§.§ Proof Step 2: Combinatorial Step

Let $\tilde{\calA}$ be some algorithm, whose set of $\mathsf{Q}$ adaptive pair queries is  $\left
\{\left(\tilde{i}_1,\tilde{j}_1\right), \ldots, \left(\tilde{i}_{\mathsf{Q}},\tilde{j}_{\mathsf{Q}}\right) \right\}$,
and let $\calE_{\mathsf{Q}}$ denote the event that the first $\mathsf{Q}$ adaptive pair queries of $\tilde{\calA}$ all evaluate to false. We prove (<ref>) by determining the conditional law of $\left(\calR^\ast, \calL^\ast \right)$, given the event $\calE_{\mathsf{Q}}$. where $\calR^\ast$ and $\calL^\ast$ are the chosen right-handed and left-handed disjoint sets accordingly, under $\tilde{\mathcal{H}}_{1}$. Let $\calC_\mathsf{Q}$ denote the set
of sets-tuples such that there was a pair query among these first $\mathsf{Q}$ pair queries that
queried at least one pair from this sets-tuple. Specifically, each element in $\calC_\mathsf{Q}$ is of the form $\left(\calR , \calL\right)$, where $\calR \subseteq \left[n\right], \calL \subseteq \left[n\right]$ are two disjoint sets satisfying $\vert \calR \vert = k_{\s{R}}, \vert \calL \vert = k_{\s{L}}$, and there is at least one edge pair $\left(\tilde{i}_t,\tilde{j}_t \right)$, where either $\tilde{i}_{t} \in \calR, \tilde{j}_{t} \in \calL$ or $\tilde{j}_{t} \in \calR, \tilde{i}_{t} \in \calL$, that is:

\begin{align}
\calC_\mathsf{Q} &= \left\{\left(\calR, \calL\right): \calR \subseteq \left[n\right], \calL \subseteq \left[n\right], \calR \cap \calL = \emptyset, \vert \calR \vert = k_{\s{R}}, \right.\nonumber\\
&\left.\quad\quad\quad\quad\quad\quad\vert \calL \vert = k_{\s{L}}, \exists t \in \mathsf{Q}: \left(\tilde{i}_t,\tilde{j}_t \right) \in \left\{\calR, \calL\right\}\right\}.
\end{align}

Given $\calE_{\mathsf{Q}}$, all pair queries evaluated to false. Thus, for all element $\left(\calR, \calL\right) \in \calC_\mathsf{Q}$, we have:

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \vert \calE_{\mathsf{Q}}\right)} = 0,
\end{align}

since otherwise a pair query would have evaluated to true. Now, let us consider an element $\left(\calR, \calL\right)$ that is not in $\calC_\mathsf{Q}$. By Bayes's rule we have that,

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \vert \calE_{\mathsf{Q}}\right)} = \frac{\pr_{\tilde{\mathcal{H}}_{1}}{\left(\calE_{\mathsf{Q}} \vert \left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right)\right)} \cdot \pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \right)}}{\pr_{\tilde{\mathcal{H}}_{1}}{\left( \calE_{\mathsf{Q}}\right)}}.
\end{align}

The prior on $\left(\calR^\ast, \calL^\ast \right)$ is uniform, therefore,

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \right)} = \frac{1}{\binom{n}{k_{\s{R}}} \cdot \binom{n-k_{\s{R}}}{k_{\s{L}}}}.
\end{align}

Now, since $\left(\calR, \calL\right) \not\subseteq \calC_\mathsf{Q}$ then the answers to the pair queries $\left
\{\left(\tilde{i}_1,\tilde{j}_1\right), \ldots, \left(\tilde{i}_{\mathsf{Q}},\tilde{j}_{\mathsf{Q}}\right) \right\}$ are necessarily all false (due to definition of $\calC_\mathsf{Q}$). Therefore, for every $\left(\calR, \calL\right) \not\subseteq \calC_\mathsf{Q}$ we have

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\calE_{\mathsf{Q}} \vert \left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right)\right)} = 1.
\end{align}

That is, we have shown that for every $\left(\calR, \calL\right) \not\subseteq \calC_\mathsf{Q}$ the following holds

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \vert \calE_{\mathsf{Q}}\right)} = \frac{1}{\binom{n}{k_{\s{R}}} \cdot \binom{n-k_{\s{R}}}{k_{\s{L}}} \cdot \pr_{\tilde{\mathcal{H}}_{1}}{\left( \calE_{\mathsf{Q}}\right)}}.
\end{align}

Altogether, we have shown that the conditional law of $\left(\calR^\ast, \calL^\ast \right)$ given $\calE_{\mathsf{Q}}$ is given by

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \vert \calE_{\mathsf{Q}}\right)} = \frac{1}{\binom{n}{k_{\s{R}}} \cdot \binom{n-k_{\s{R}}}{k_{\s{L}}} \cdot \pr_{\tilde{\mathcal{H}}_{1}}{\left( \calE_{\mathsf{Q}}\right)}} \cdot \Ind \left \{\left(\calR, \calL\right) \not\subseteq \calC_\mathsf{Q}\right \}.
\end{align}

Notice that this conditional probability is equal for all $\left(\calR, \calL \right)\not\in\calC_\mathsf{Q}$. Therefore,

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left(\left(\calR, \calL\right) = \left(\calR^\ast, \calL^\ast \right) \vert \calE_{\mathsf{Q}}\right)} = \frac{1}{\binom{n}{k_{\s{R}}} \cdot \binom{n-k_{\s{R}}}{k_{\s{L}}} - \vert \calC_\mathsf{Q} \vert} \cdot \Ind \left \{\left(\calR, \calL\right) \not\subseteq \calC_\mathsf{Q}\right \}.
\end{align}

Putting together the previous results, we obtain

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left( \calE_{\mathsf{Q}}\right)} = 1 - \frac{\vert \calC_\mathsf{Q} \vert}{\binom{n}{k_{\s{R}}} \cdot \binom{n-k_{\s{R}}}{k_{\s{L}}}}.
\end{align}

Now, we can upper bound $\vert \calC_\mathsf{Q} \vert$ as follows,

\begin{align} \label{bound C_q}
\vert \calC_\mathsf{Q} \vert \leq  \mathsf{Q} \cdot \binom{n-2}{k_{\s{R}}-1} \cdot \binom{n-k_{\s{R}}-1}{k_{\s{L}}-1},
\end{align}

since after we choose the first right-left pair, we are left with $\binom{n-2}{k_{\s{R}}-1} \cdot \binom{n-k_{\s{R}}-1}{k_{\s{L}}-1}$ options for the other elements. Combining the above, we get that

\begin{align}
\pr_{\tilde{\mathcal{H}}_{1}}{\left( \calE_{\mathsf{Q}}\right)} \geq 1 - \mathsf{Q} \cdot \frac{\binom{n-2}{k_{\s{R}}-1} \cdot \binom{n-k_{\s{R}}-1}{k_{\s{L}}-1}}{\binom{n}{k_{\s{R}}} \cdot \binom{n-k_{\s{R}}}{k_{\s{L}}}} = 1 - \mathsf{Q} \cdot \frac{k_{\s{R}} k_{\s{L}}}{n \left(n-1 \right)},
\end{align}

which is strictly positive if,

\begin{align}
\mathsf{Q} = o\left(\frac{n^2}{k_{\s{R}} k_{\s{L}}}\right). \label{adaptive queries lower bound result}
\end{align}

Finally, note that independently of the choice of $\tilde{\calA}$, if (<ref>) holds, all of the pair queries will evaluate to false with strictly positive probability, which concludes the proof.

§.§ Proof of Lemma <ref>

§.§.§ Query Scan Test

As $\calR, \calL$, and $\calS$ are chosen uniformly at random, and since $\calR$ and $\calL$ are disjoint, note that the following holds under $\calH_1$:

\begin{align}
\min \left\{\vert \calR \cap \calS\vert, \vert \calL \cap \calS\vert\right\} \succeq \mathsf{Hypergeometric}\left(n,k_{\s{R}}\wedge k_{\s{L}},s\right).
\end{align}

Also, recall that,

\begin{align}
\mathbb{E}\left[\mathsf{Hypergeometric}\left(n,k_{\s{R}}\wedge k_{\s{L}},s\right)\right] = \frac{s k_{\s{R}}\wedge k_{\s{L}}}{n}, \\ \Var\left(\mathsf{Hypergeometric}\left(n,k_{\s{R}}\wedge k_{\s{L}},s\right)\right) \leq \frac{s k_{\s{R}}\wedge k_{\s{L}}}{n}.
\end{align}

Thus, by Chebyshev's inequality:

\begin{align}
&\pr{\left( \min \left\{\vert \calR \cap \calS\vert, \vert \calL \cap \calS\vert\right\} < \left(1-\epsilon' \right) \frac{s k_{\s{R}}\wedge k_{\s{L}}}{n} \right)} \\& \leq \pr{\left(\mathsf{Hypergeometric}\left(n,k_{\s{R}}\wedge k_{\s{L}},s\right) < \left(1-\epsilon' \right) \frac{s k_{\s{R}}\wedge k_{\s{L}}}{n} \right)} \\
&\leq \frac{1}{\epsilon'^2 \frac{s k_{\s{R}}\wedge k_{\s{L}}}{n}},
\end{align}

which goes to $0$ as $n \to \infty$ if $s = \omega \left(\frac{n}{k_{\s{R}}\wedge k_{\s{L}}}\right)$. Therefore, let $s_0 \triangleq \left(1-\epsilon' \right) \frac{s k_{\s{R}}\wedge k_{\s{L}}}{n}$. Thus, under $\calH_1$, if ${\mathsf{K}}_{\calR, \calL}$ is planted, conditioning on $\min \left\{\vert \calR \cap \calS\vert, \vert \calL \cap \calS\vert\right\} \geq s_0$,
there exist $\calR^{\ast}, \calL^{\ast}$ such that $\sum_{\substack{i \in \calR^{\ast}, j \in \calL^{\ast}}}\mathsf{A}_{ij} \succeq \mathsf{Binomial}{\left({s_0}^2, p\right)}$. Therefore, by the multiplicative Chernoff's bound, we have:

\begin{align}
\pr_{\calH_1}{\left(\mathsf{Scan}{\left(\mathsf{A}\right)} \leq \tau_{\mathsf{Scan}}\right)} &\leq \pr_{\calH_1}{\left(\mathsf{Scan}{\left(\mathsf{A}\right)} \leq \tau_{\mathsf{Scan}}\right)} \\
&\leq \pr_{\calH_1}{\left[\sum_{\substack{i \in \calR^{\ast}, j \in \calL^{\ast}}} \mathsf{A}_{ij} \leq \tau_{\mathsf{Scan}} \right]} \\
&\leq \exp{\left(-
\frac{{\left({s_0}^2\right)}^2 \cdot {\left(p-q\right)}^2/4}{2 {s_0}^2 p}\right)}\\
&\leq \exp{\left(-C''\cdot {s_0}^2 \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C'' > 0$. Under $\calH_0$, for any $\calR' \subset \left[n\right], \vert \calR' \vert = s_0, \calL' \subset \left[n\right], \vert \calL' \vert = s_0, \calR' \cap \calL' = \emptyset$ we have that $\sum_{\substack{i \in \calR', j \in \calL'}}\mathsf{A}_{ij} \sim \mathsf{Binomial}{\left({s_0}^2, q\right)}$. Now, note that in the definition of $\mathsf{Scan}{\left(\mathsf{A}\right)}$, the maximum is taken over a set of size at most $\binom{n}{s_0}\binom{n-s_0}{s_0}$, which can be upper bounded as,

\begin{align}
\binom{n}{s_0}\binom{n-s_0}{s_0} \leq \binom{n}{s_0}\binom{n}{s_0} \leq \left(\frac{3n}{s_0}\right)^{2 s_0},
\end{align}

Thus, by the union bound and Bernstein's inequality we have:

\begin{align}
\pr_{\calH_0}{\left(\mathsf{Scan}{\left(\mathsf{A}\right)} \geq \tau_{\mathsf{Scan}}\right)} &\leq \sum_{\substack{\calR' \subset \left[n\right], \vert \calR' \vert = s_0 \\ \calL' \subset \left[n\right], \vert \calL' \vert = s_0 \\ \calR' \cap \calL' = \emptyset}}{\pr_{\calH_0}{\left[\sum_{\substack{i \in \calR', j \in \calL'}}\mathsf{A}_{ij} \geq \tau_{\mathsf{Scan}}\right]}}    \\
&\leq \left(\frac{3n}{s_0}\right)^{2 s_0} \cdot\exp{\left(-
\frac{{\left({s_0}^2\right)}^2 \cdot {\left(p-q\right)}^2/4}{2 {s_0}^2 q + {s_0}^2\cdot{\left(p-q\right)}/3}\right)}    \\
&\leq \exp{\left(s_0 \cdot \log{n}-C'\cdot {s_0}^2 \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C' > 0$. Therefore, we obtain that,

\begin{align}
\mathsf{R{\left(Scan\right)}} &\leq 2 \cdot \exp{\left(s_0 \cdot \log{n}-C'\cdot {s_0}^2 \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)} \\&
= 2 \cdot \exp{\left(\frac{s k_{\s{R}}\wedge k_{\s{L}}}{n} \cdot \log{n}-C'\cdot {\left(\frac{s k_{\s{R}}\wedge k_{\s{L}}}{n}\right)}^2 \cdot \chi^2(p||q)\right)},
\end{align}

which, since $s =\Theta \left(\sqrt{\mathsf{Q}}\right)$, goes to $0$ as $n \to \infty$ provided that:

\begin{align}
\mathsf{Q} = \omega \left(\frac{n^2 \log^2{n}}{\left(k_{\s{R}}\wedge k_{\s{L}}\right)^2 \chi^4(p||q)}\right),
\end{align}

which completes the proof.

§.§.§ Query Count Test

As ${\mathsf{K}}_{\calR, \calL}$ is chosen uniformly at random over all possible copies, each edge has the same probability to exist. That is, under $\calH_1$, let $\mathsf{M}$ be the number of planted edges that have been queried by the algorithm, and note that the following holds:

\begin{align}
\mathsf{M} \sim \mathsf{Hypergeometric}\left(\binom{n}{2}, \vert e\left({\mathsf{K}}_{\calR, \calL}\right) \vert ,\mathsf{Q}\right) \equiv \mathsf{Hypergeometric}\left(\binom{n}{2}, k_{\s{R}} k_{\s{L}} ,\mathsf{Q}\right).
\end{align}

\begin{align}
\mathbb{E}\left[\mathsf{M} \right] = \mathsf{Q} \frac{k_{\s{R}} k_{\s{L}}}{\binom{n}{2}}, \quad \Var\left(\mathsf{M}\right) \leq \mathsf{Q} \frac{k_{\s{R}} k_{\s{L}}}{\binom{n}{2}}.
\end{align}

Thus, by Chebyshev's inequality:

\begin{align}
\pr{\left(\mathsf{M} \leq \left(1-\epsilon'\right) \mathsf{Q} \frac{k_{\s{R}} k_{\s{L}}}{\binom{n}{2}}\right)} \leq \frac{1}{\epsilon'^2 \mathsf{Q} \frac{k_{\s{R}} k_{\s{L}}}{\binom{n}{2}}},
\end{align}

which goes to $0$ as $n \to \infty$ if $\mathsf{Q} = \omega\left(\frac{\binom{n}{2}}{k_{\s{R}} k_{\s{L}}}\right)$. Accordingly, let $\mathsf{M}_0$ be $\left(1-\epsilon'\right) \mathsf{Q} \frac{k_{\s{R}} k_{\s{L}}}{\binom{n}{2}}$, and note that under $\calH_1$, conditioning on $\mathsf{M} \geq \mathsf{M}_0$ the edge count $\mathsf{Count}{\left(\mathsf{A}\right)}$ stochastically dominates the independent sum of $\mathsf{Binomial}{\left(\mathsf{M}_0, p\right)}$ and $\mathsf{Binomial}{\left(\mathsf{Q} -\mathsf{M}_0, q\right)}$. Therefore, by the multiplicative Chernoff's bound, we have:

\begin{align}
\pr_{\calH_1}{\left(\mathsf{Count}{\left(\mathsf{A}\right)} \leq \tau_{\mathsf{Count}}\right)}
&\leq \exp{\left(-
\frac{{\left(\mathsf{M}_0\right)}^2 \cdot {\left(p-q\right)}^2/4}{2{\mathsf{Q}}q+2\cdot \mathsf{M}_0\cdot{\left(p-q\right)}}\right)}    \\
&\leq \exp{\left(-C''\cdot \frac{{\left(\mathsf{M}_0\right)}^2}{\mathsf{Q}} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C'' > 0$. Under $\calH_0$, we have $\mathsf{Count}{\left(\mathsf{A}\right)} \sim \mathsf{Binomial}{\left(\mathsf{Q}, q\right)}$. Thus, Bernstein's inequality implies that

\begin{align}
\pr_{\calH_0}{\left(\mathsf{Count}{\left(\mathsf{A}\right)} \geq \tau_{\mathsf{Count}}\right)}
&\leq \exp{\left(-
\frac{{\left(\mathsf{M}_0\right)}^2 \cdot {\left(p-q\right)}^2/4}{2{\mathsf{Q}}q+\mathsf{M}_0\cdot{\left(p-q\right)}/3}\right)}    \\
&\leq \exp{\left(-C'\cdot \frac{{\left(\mathsf{M}_0\right)}^2}{\mathsf{Q}} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C' > 0$.
Thus, we obtain that:

\begin{align}
\mathsf{R{\left(Count\right)}} \leq 2 \cdot \exp{\left(-\tilde{C}\cdot \frac{{\left(\mathsf{M}_0\right)}^2}{\mathsf{Q}} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)} = 2 \cdot \exp{\left(-C\cdot \mathsf{Q} \frac{k_{\s{R}}^2 k_{\s{L}}^2}{n^4} \cdot \chi^2(p||q)\right)},
\end{align}

which goes to $0$ as $n \to \infty$ provided that:

\begin{align}
\mathsf{Q} = \omega\left(\frac{n^4}{k_{\s{R}}^2 k_{\s{L}}^2 \chi^2(p||q)}\right),
\end{align}

which completes the proof.

§.§.§ Query Degree Test

Without any loss of generality, assume that $k_{\s{R}} \geq k_{\s{L}}$. Under $\calH_1$, let $\mathsf{M}$ be the number of planted vertices in the set $\calL$, that have been chosen by the algorithm in the set $\calS_1$.
Thus, as $\calL$ and $\calS_1$ are chosen uniformly at random, we have:

\begin{align}
\mathsf{M} \sim \mathsf{Hypergeometric}\left(n, k_{\s{L}}, s_1\right).
\end{align}

Therefore we have:

\begin{align}
\mathbb{E}\left[\mathsf{M} \right] = s_1 \frac{k_{\s{L}}}{n}, \quad \Var\left(\mathsf{M}\right) \leq s_1 \frac{k_{\s{L}}}{n}.
\end{align}

Thus, by Chebyshev's inequality:

\begin{align}
\pr{\left(\mathsf{M} \leq \left(1-\epsilon'\right) s_1 \frac{k_{\s{L}}}{n}\right)} \leq \frac{1}{\epsilon'^2 s_1 \frac{k_{\s{L}}}{n}},
\end{align}

which goes to $0$ as $n \to \infty$ if $s_1 = \Omega\left(\frac{n \log{n}}{k_{\s{L}}}\right)$. Accordingly, let $\mathsf{M}_0$ be $\left(1-\epsilon'\right) s_1 \frac{k_{\s{L}}}{n}$, and note that $\mathsf{M}_0 \geq 1$ if $s_1 = \Omega\left(\frac{n \log{n}}{k_{\s{L}}}\right)$.
Similarly, let $\mathsf{N}$ be the number of planted vertices in the set $\calR$, that have been chosen by the algorithm in the set $\calS_2$. Thus, as $\calR$ and $\calS_2$ are chosen uniformly at random, we get

\begin{align}
\mathsf{N} \sim \mathsf{Hypergeometric}\left(n, k_{\s{R}}, s_2\right).
\end{align}

\begin{align}
\mathbb{E}\left[\mathsf{N} \right] = s_2 \frac{k_{\s{R}}}{n}, \quad \Var\left(\mathsf{N}\right) \leq s_2 \frac{k_{\s{R}}}{n}.
\end{align}

Chebyshev's inequality implies that

\begin{align}
\pr{\left(\mathsf{N} \leq \left(1-\epsilon'\right) s_2 \frac{k_{\s{R}}}{n}\right)} \leq \frac{1}{\epsilon'^2 s_2 \frac{k_{\s{R}}}{n}},
\end{align}

which goes to $0$ as $n \to \infty$ if $s_2 = \omega\left(\frac{n}{k_{\s{R}}}\right)$. Therefore, let $\mathsf{N}_0$ be $\left(1-\epsilon'\right) s_2 \frac{k_{\s{R}}}{n}$.
Under $\calH_1$, conditioning on $\mathsf{M} \geq \mathsf{M}_0 \geq 1$ and $\mathsf{N} \geq \mathsf{N}_0$, there is at least one row $i^\ast$ such that $\sum_{j \in \calS_2} \mathsf{A}_{i^\ast j}$ stochastically dominates the
independent sum of $\mathsf{Binomial}{\left(\mathsf{N}_0, p\right)}$ and $\mathsf{Binomial}{\left(s_2-\mathsf{N}_0, q\right)}$.
Therefore, by the multiplicative Chernoff's bound,

\begin{align}
\pr_{\calH_1}{\left(\mathsf{MaxDeg}{\left(\mathsf{A}\right)} \leq \tau_{\mathsf{Deg}}\right)}
&\leq \exp{\left(-
\frac{{\left(\mathsf{N}_0\right)}^2 \cdot {\left(p-q\right)}^2/4}{2 s_2 q+2\cdot \mathsf{N}_0\cdot{\left(p-q\right)}}\right)}    \\
&\leq \exp{\left(-C''\cdot \frac{{\left(\mathsf{N}_0\right)}^2}{s_2} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C'' > 0$. Under $\calH_0$ we have $\sum_{j \in \calS_2} \mathsf{A}_{i j} \sim \mathsf{Binomial}{\left(s_2, q\right)}$. Then, by the union bound and Bernstein's inequality,

\begin{align}
\pr_{\calH_0}{\left(\mathsf{MaxDeg}{\left(\mathsf{A}\right)} \geq \tau_{\mathsf{Deg}}\right)}
&\leq n \cdot \exp{\left(-
\frac{{\left(\mathsf{N}_0\right)}^2 \cdot {\left(p-q\right)}^2/4}{2  s_2 q+\mathsf{N}_0\cdot{\left(p-q\right)}/3}\right)}    \\
&\leq \exp{\left(\log{n}-C'\cdot \frac{{\left(\mathsf{N}_0\right)}^2}{s_2} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)},
\end{align}

for some constant $C' > 0$. Thus, we obtain that:

\begin{align}
\mathsf{R{\left(Deg\right)}} \leq 2 \cdot \exp{\left(\log{n}-\tilde{C}\cdot \frac{{\left(\mathsf{N}_0\right)}^2}{s_2} \cdot \frac{{\left(p-q\right)}^2}{q\left(1-q\right)}\right)} = 2 \cdot \exp{\left(\log{n}-\tilde{C}\cdot \frac{s_2 k_{\s{R}}^2}{n^2}  \cdot \chi^2(p||q)\right)},
\end{align}

which goes to $0$ as $n \to \infty$, if

\begin{align} \label{s_2 cond}
s_2 = \omega \left(\frac{n^2 \log{n}}{k_{\s{R}}^2 \chi^2(p||q)}\right).
\end{align}

Since, be definition, $s_2$ is at most $n$, we get from (<ref>) the condition (after removing the assumption of $k_{\s{R}} \geq k_{\s{L}}$):

\begin{align}
\chi^2(p||q) = \omega{\left(\frac{n \log{n}}{{\left(k_{\s{R}}\vee k_{\s{L}}\right)}^2}\right)}.
\end{align}

Finally, note that by definition of the algorithm, the total number of queries is $\Theta \left(s_1 \cdot s_2\right)$. Thus, since we also required that $s_1 = \Omega\left(\frac{n \log{n}}{k_{\s{L}}}\right)$, combining with (<ref>), we get the condition of (after removing the assumption of $k_{\s{R}} \geq k_{\s{L}}$):

\begin{align}
\mathsf{Q} = \omega \left(\frac{n^3 \log^2{n}}{k_{\s{R}} k_{\s{L}} k_{\s{R}}\vee k_{\s{L}} \chi^2(p||q)}\right),
\end{align}

which completes the proof.

§ CONCLUSION

In this work, we studied the problem of detecting a planted bipartite structure in a large random graph. We derived asymptotically tight lower and upper bounds in both the dense and sparse regimes. It turns out that the, seemingly simple, bipartite structure has essentially a rich geometry, which produces a surprising phase diagram for the detection problem, as can be seen in, for example, Figure <ref>. Among other results, we observed an interesting phenomenon where, for example, in the planted complete bipartite problem, there is a regime in which a degree-based polynomial-time algorithm achieves detection, while an exhaustive scan test, which has exponential complexity and typically optimal, fails. We then considered a variant of the above problem, where one can only observe a relatively small part of the graph, by using a limited amount of queries. For this problem, we proposed query versions for the scan, count, and degree tests, and were able to derive a lower bound which is not tight in general. An interesting future work is to close this gap.

[1]
T. Cai and Yihong Wu.
Statistical and computational limits for sparse matrix detection.
Annals of Statistics, 48, 01 2018.

[2]
Noga Alon, Michael Krivelevich, and Benny Sudakov.
Finding a large hidden clique in a random graph.
Random Structures and Algorithms, 13(3-4):457–466, 1998.

[3]
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur
Moitra, and Aaron Potechin.
A nearly tight sum-of-squares lower bound for the planted clique
In 2016 IEEE 57th Annual Symposium on Foundations of Computer
Science (FOCS), page 428–437, 2016.

[4]
Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres.
Finding hidden cliques in linear time with high probability.
Probability and Computing, page 29–49, 2014.

[5]
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying
Statistical algorithms and a lower bound for detecting planted
J. ACM, 64(2), 2014.

[6]
Bruce Hajek, Yihong Wu, and Jiaming Xu.
Computational lower bounds for community detection on random graphs.
In Proceedings of The 28th Conference on Learning Theory,
40:899–928, 2015.

[7]
Yudong Chen and Jiaming Xu.
Statistical-computational tradeoffs in planted problems and submatrix
localization with a growing number of clusters and submatrices.
Journal of Machine Learning Research, 17(27):1–57, 2016.

[8]
Matthew Brennan, Guy Bresler, and Wasim Huleihel.
Reducibility and computational lower bounds for problems with planted
sparse structure.
In Proceedings of the 31st Conference On Learning Theory,
75:48–166, 2016.

[9]
Paul Erdős and Alfréd Rényi.
On the evolution of random graphs.
Publication of Mathematics Institute of Hungian Academy of
Sciences, 5:1761, 1960.

[10]
Béla Bollobás.
Threshold functions for small subgraphs.
Mathematical Proceedings of the Cambridge Philosophical
Society, 90(2):197–206, 1981.

[11]
Laurent Massoulie, Ludovic Stephan, and Don Towsley.
Planting trees in graphs, and finding them back.
In Proceedings of the 32nd Conference on Learning Theory,
99:2341–2371, 2019.

[12]
Ludek Kucera.
Expected complexity of graph partitioning problems.
Discrete Applied Mathematics, 57(2):193–212, 1995.

[13]
Ery Arias-Castro and Nicolas Verzelen.
Community detection in dense random networks.
The Annals of Statistics, 42(3):940–969, 2014.

[14]
Nicolas Verzelen and Ery Arias-Castro.
Community detection in sparse random networks.
The Annals of Applied Probability, 25(6):3465–3510, 2015.

[15]
Mark Jerrum.
Large cliques elude the metropolis process.
Random Structures and Algorithms, 3(4):347–359, 1992.

[16]
Quentin Berthet and Philippe Rigollet.
Complexity theoretic lower bounds for sparse principal component
In Proceedings of the 26th Annual Conference on Learning
Theory, 30:1046–1066, 2013.

[17]
Emmanuel Abbe.
Community detection and stochastic block models: Recent developments.
J. Mach. Learn. Res., 18:6446–6531, 2017.

[18]
Yihong Wu and Jiaming Xu.
Statistical problems with planted structures: Information-theoretical
and computational limits.
ArXiv, abs/1806.00118, 2018.

[19]
Wasim Huleihel.
Inferring hidden structures in random graphs.
IEEE Transactions on Signal and Information Processing over
Networks, 8:855–867, 2022.

[20]
Armen S. Asratian, Tristan M. J. Denley, and Roland Häggkvist.
Bipartite graphs and their applications.
Cambridge University Press, 1998.

[21]
Georgios A Pavlopoulos, Panagiota I Kontou, Athanasia Pavlopoulou, Costas
Bouyioukos, Evripides Markou, and Pantelis G Bagos.
Bipartite graphs in systems biology and medicine: a survey of methods
and applications.
Gigascience, 7:1–31, 2018.

[22]
Uriel Feige, David Gamarnik, Mikl´os Z. R´acz, and Prasad Tetali.
Finding cliques using few probes.
Random Structures and Algorithms, 56(1):142–153, 2020.

[23]
Ryan Alweiss, Chady Ben Hamida, Xiaoyu He, and Alexander Moreira.
Finding cliques using few probes.
Combinatorics, Probability and Computing, page 1–16, 2020.

[24]
Mikl´os Z. R´acz and Benjamin Schiffer.
Finding a planted clique by adaptive probing.
ALEA Latin American Journal of Probability and Mathematical
Statistics, 17:775–790, 2020.

[25]
Wasim Huleihel, Arya Mazumdar, and Soumyabrata Pal.
Random subgraph detection using queries.
arXiv preprint arXiv:2110.00744, 2021.