1 Introduction↩︎

Identifying hidden structure in random graphs is a central problem in modern statistics, theoretical computer science, and network science. A standard model assumes that one observes a graph on \(n\) vertices drawn either from an Erdős–Rényi random graph or from a modified distribution in which a structured subgraph has been planted. The inferential goal may be either to decide whether such a planted structure is present, or to localize the planted vertices. Over the past three decades, this general paradigm has led to a rich body of work spanning hypothesis testing, estimation, average-case complexity, and algorithm design.

Much of the classical literature has focused on specific planted structures, most notably planted clique, planted dense subgraph, biclique, and related community-detection models. For these problems, the statistical and computational thresholds are by now fairly well understood in many parameter regimes; see, for example, [1]–[10]. A recurring theme in this line of work is the appearance of statistical–computational gaps: detection may be information-theoretically possible well before any known polynomial-time algorithm succeeds.

More recently, there has been substantial progress toward a unified theory of planted subgraph inference beyond these ad hoc examples. On the detection side, a sequence of works has studied arbitrary planted subgraphs and identified general graph-theoretic quantities that govern the testing problem in several regimes [11]–[15]. In particular, the recent work [14] develops a general full-observation theory for detecting arbitrary planted subgraphs in Erdős–Rényi graphs, establishing sharp statistical and computational thresholds in the dense regime and broad results in sparse and critical regimes as well. These developments suggest that, at least when the full graph is observed, the detection problem is close to being understood at a rather high level of generality.

The landscape for the recovery problem has also seen significant recent progress. Early works such as [16], [17] provided a general statistical characterization of weak recovery for arbitrary planted subgraphs, via variational formulas describing the limiting MMSE under suitable structural assumptions. These results established a unified framework for approximate recovery. More recently, [18] develops a general theory for exact recovery of arbitrary planted subgraphs in dense Erdős-Rényi graphs. It identifies sharp necessary and sufficient conditions for exact recovery, characterized by a novel graph-theoretic quantity termed the minimal maximum subgraph density. In addition, it provides efficient recovery algorithms and establishes computational lower bounds using the low-degree framework, thereby initiating a systematic study of statistical–computational tradeoffs for recovery in this general setting.

In many applications, however, one does not have access to the full graph. Large networks may be too expensive to inspect exhaustively, privacy or storage constraints may restrict access to edges, and in interactive or crowdsourced settings one may only be allowed to probe selected pairs of items. This naturally leads to a query-limited version of planted subgraph inference: rather than observing the entire adjacency matrix, the algorithm chooses a set of pairs and only learns whether those queried pairs are connected. Understanding how many such queries are needed in order to detect hidden structure is a fundamental question, both for theory and for applications involving graph sampling, active data acquisition, and similarity-based exploration.

This query perspective has already attracted attention in several related settings. In random graphs, adaptive edge-query models were studied for finding large cliques and other target structures; see, e.g., [19]–[23]. Query models also arise naturally in clustering and community inference, where pairwise comparison or similarity queries serve as a primitive for learning latent labels or partitions [24]–[28]. Most closely related to our work are the studies of planted clique under query access in [29]–[33], which characterize the statistical and computational barriers for detecting a planted clique (or, slightly more generally, a planted dense subgraph). Those works already indicate that restricted graph access creates a new layer of difficulty and can magnify statistical–computational tradeoffs.

The goal of the present paper is to develop a general theory of query complexity for detecting arbitrary planted subgraphs. We study a model in which the planted structure is an arbitrary graph sequence \(\Gamma_n\), embedded uniformly at random into an ambient Erdős-Rényi graph, and the observer is allowed only a prescribed number of non-adaptive edge queries. Thus, the paper may be viewed as bringing together two previously separate directions: the recent full-observation theory for arbitrary planted subgraph detection, and the query-complexity theory developed so far mainly for planted clique and planted dense subgraph models.

Our main objective is to understand how the structural properties of \(\Gamma_n\) determine the number of non-adaptive queries required for reliable detection. We derive several general lower bounds, each capturing a different obstruction to detection. The first is a direct “edge-hit” lower bound, showing that unless the query set intersects the planted structure often enough, the transcript under the alternative is statistically indistinguishable from that under the null. This bound is especially effective for clique-like or witness-rich graphs, where detection can in principle be triggered by observing even a small dense planted pattern. Our second, more structural lower bound is based on a vertex-cover decomposition of \(\Gamma_n\). It separates a cover-induced core from a residual part and shows that if the core is itself undetectable and the residual attachment to the cover is sufficiently diffuse relative to the query profile, then detection remains impossible. This theorem is flexible and leads to sharp consequences for broad sparse families, including bounded-cover graphs, star forests, pendant-leaf constructions, bounded-degree trees, paths, and several bipartite regimes.

On the algorithmic side, we propose two complementary non-adaptive tests. The first is a witness scan test, which samples a random vertex subset, queries all edges inside it, and searches for a suitable witness subgraph \(H\subseteq \Gamma_n\). This test is effective when \(\Gamma_n\) contains many sufficiently dense local patterns, and it recovers the optimal scale, up to polylogarithmic factors, for clique-like and balanced biclique-like structures. The second is a polynomial-time degree-on-a-cut test, which samples a bipartite cut and looks for unusually large query degree on one side. Its performance is governed by the high-degree mass \[\kappa(\Gamma_n)\triangleq \max_{d\ge 1} m_d(\Gamma_n)d^2, \qquad m_d(\Gamma_n)\triangleq \big|\{u\in v(\Gamma_n):\deg_{\Gamma_n}(u)\ge d\}\big|,\] and it is near-optimal for hub-dominated families such as stars, star forests, and more generally bounded-cover graphs with a non-negligible high-degree layer.

Taken together, our results show that query complexity for arbitrary planted subgraph detection is governed by a small collection of structural principles. Dense local witnesses favor scan-based procedures and are well captured by the edge-hit lower bound. Hub-dominated geometries are governed instead by degree exposure across suitably chosen cuts, and are captured by the cover-based lower bounds. This leads to a unified picture in which different algorithmic mechanisms are optimal for different structural classes of planted graphs.

At a broader level, our results reveal that the query model has its own statistical and computational landscape, distinct from the one arising under full observation. In some families, the information-theoretic threshold under query access remains close to the full-observation one, while in others the cost of restricted access is substantial. Likewise, there are regimes in which quasi-optimal non-adaptive detection is possible but the best known polynomial-time algorithms require many more queries. This provides further evidence that active access constraints can generate new statistical–computational tradeoffs even for inference tasks that are already well understood in the classical full-observation setting.

1.25ex -1em Notation. We collect here the main notational conventions used throughout the paper. For any finite set \({\cal S}\), we write \(|{\cal S}|\) for its cardinality. For \(n\in\mathbb{N}\), we denote \([n]\triangleq\{1,\ldots,n\}\), and for any set \({\cal S}\), we let \(\binom{{\cal S}}{k}\triangleq\{{\cal A}\subseteq{\cal S}:|{\cal A}|=k\}\). For a subset \({\cal S}\subseteq\mathbb{R}\), we denote by \(\mathbb{1}\left[{\cal S}\right]\) its indicator function.

We denote by \(\mathsf{Bern}(p)\) and \(\mathsf{Binomial}(n,p)\) the Bernoulli and binomial distributions with success probability \(p\), and by \(\mathsf{Hypergeometric}(N,K,n)\) the hypergeometric distribution with the usual parameters. For a finite or measurable set \(\mathcal{X}\), \(\mathsf{Unif}[\mathcal{X}]\) denotes the uniform distribution over \(\mathcal{X}\). For random variables \(\mathsf{X}\) and \(\mathsf{Y}\), we write \(\mathsf{X}\perp \!\!\! \perp\mathsf{Y}\) to indicate independence. For probability measures \(\mathbb{P}\) and \(\mathbb{Q}\), we write \(d_{\mathsf{TV}}(\mathbb{P},\mathbb{Q})\) and \(\chi^2(\mathbb{P}||\mathbb{Q}),\) for the total variation distance and \(\chi^2\)-divergence, respectively. In particular, for Bernoulli distributions we use \(\chi^2(p||q)=\frac{(p-q)^2}{q(1-q)}\). We will frequently use standard asymptotic notation \(O(\cdot),o(\cdot),\Omega(\cdot),\omega(\cdot),\Theta(\cdot)\). We write \(a_n\ll b_n\) to indicate that \(a_n\) is polynomially smaller than \(b_n\), namely \(\liminf_{n\to\infty}\log_n a_n < \liminf_{n\to\infty}\log_n b_n\). We write \(a_n\lesssim b_n\) if there exists an absolute constant \(\mathsf{C}>0\), independent of \(n\) and of all problem parameters, such that \(a_n\le \mathsf{C}b_n\) for all sufficiently large \(n\). The notation \(a_n\gtrsim b_n\) is defined analogously. Throughout, \(\mathsf{C}\) denotes a generic constant that may change from line to line.

A graph \(\mathsf{G}\) is a pair \((v(\mathsf{G}),e(\mathsf{G}))\), where \(v(\mathsf{G})\) is the vertex set and \(e(\mathsf{G})\subseteq \binom{v(\mathsf{G})}{2}\) is the edge set. We write \(|v(\mathsf{G})|\) for the number of vertices and \(|e(\mathsf{G})|\) (or \(|\mathsf{G}|\)) for the number of edges. We say that \(\mathsf{H}\subseteq \mathsf{G}\) is a subgraph if \(v(\mathsf{H})\subseteq v(\mathsf{G})\) and \(e(\mathsf{H})\subseteq e(\mathsf{G})\). When \(\mathsf{H}\) has no isolated vertices, we often identify it with its edge set and write \(|\mathsf{H}|\) for \(|e(\mathsf{H})|\). For a vertex subset \(U\subseteq v(\mathsf{G})\), we denote by \(\mathsf{G}_U\) the induced subgraph. For a vertex \(v\in v(\mathsf{G})\), we denote its neighborhood by \(N_{\mathsf{G}}(v)\triangleq \left\{u\in v(\mathsf{G}):{u,v}\in e(\mathsf{G})\right\}\), and its degree by \(\deg_{\mathsf{G}}(v)=|N_{\mathsf{G}}(v)|\). The complete graph on \(n\) vertices is denoted by \({\cal K}_n\). Two graphs \(\mathsf{G}_1\) and \(\mathsf{G}_2\) are said to be isomorphic, denoted \(\mathsf{G}_1\cong \mathsf{G}_2\), if there exists a bijection between their vertex sets preserving adjacency. The automorphism group of a graph \(\mathsf{G}\) is denoted by \(\mathsf{Aut}(\mathsf{G})\). For a graph \(\mathsf{G}\) with \(|v(\mathsf{G})|\le n\), we denote by \({\cal S}_{\mathsf{G}}\) the collection of all labeled copies of \(\mathsf{G}\) in \({\cal K}_n\). It is well known that \(|{\cal S}_{\mathsf{G}}| = \binom{n}{|v(\mathsf{G})|}\frac{|v(\mathsf{G})|!}{|\mathsf{Aut}(\mathsf{G})|}\) (see, e.g., [34]). Finally, for two graphs \(\mathsf{H}\) and \(\Gamma\), we denote by \(N(\mathsf{H},\Gamma)\) the number of (labeled) copies of \(\mathsf{H}\) contained in \(\Gamma\). More generally, for \(t\in{1,\ldots,|v(\mathsf{H})|-1}\), we let \(N_t(\mathsf{H},\Gamma)\) denote the number of ordered pairs \((\mathsf{H}_1,\mathsf{H}_2)\) of copies of \(\mathsf{H}\) in \(\Gamma\) such that \(|v(\mathsf{H}_1)\cap v(\mathsf{H}_2)|=t\).

1.25ex -1em Organization. The remainder of the paper is organized as follows. In Section 2 we formalize the model and the query-based detection problem. Section 3 states our main lower and upper bounds and compares them across different graph families. The general lower bounds are proved in Section 4, while the algorithmic upper bounds are established in Section 5. We then specialize the general theory to several representative examples—including cliques, stars, trees, triangle unions, bounded-cover graphs, and complete bipartite graphs—in order to identify regimes in which the lower and upper bounds coincide up to constant or polylogarithmic factors.

2 Setup↩︎

In this section we describe the setting we plan to study alongside several important preliminaries. Let \(\Gamma=(\Gamma_n)_{n\in\mathbb{N}}\) be a sequence of graphs such that for all \(n\in\mathbb{N}\), \(\Gamma_n=(v(\Gamma_n),e(\Gamma_n))\) is an arbitrary undirected graph without isolated vertices, and \(|v(\Gamma_n)|\leq n\). We let \({\cal S}_{\Gamma_n}\) be the set of isomorphic copies of \(\Gamma_n\) in \({\cal K}_n\). We shall refer to \(\Gamma_n\) as the planted/hidden structure.

We start with the formulation of the vanilla planted subgraph hypothesis testing problem. Here, under the null hypothesis \({\cal H}_0\), the observed graph \(\mathsf{G}\) is an instance from the Erdős–Rényi random distribution \({\cal G}(n,q)\), with edge density \(0<q<1\). Under the alternative hypothesis \({\cal H}_1\), the observed graph \(\mathsf{G}\) is the union of an Erdős–Rényi random graph with a uniform random copy of \(\Gamma_n\). To wit, under \({\cal H}_1\) the graph \(\mathsf{G}\) on \(n\) vertices is constructed as follows: we first draw \(\Gamma_n\sim\mathsf{Unif}({\cal S}_{\Gamma_n})\). Then, each edge of \(\Gamma_n\) is included in \(\mathsf{G}\) with probability one, while the leftover edges in \(\mathsf{G}\) are included with probability \(q\). In short, we have the following hypothesis testing problem: \[\begin{align} {\cal H}_0: \mathsf{G} \sim {\cal G}(n,q) \quad \mathsf{vs.} \quad {\cal H}_1 : \mathsf{G} \sim {\cal G}_{\Gamma_n}(n,q),\label{eqn:super95hypo} \end{align}\tag{1}\] where \({\cal G}_{\Gamma_n}(n,q)\) denotes the ensemble of planted graphs, as defined above. We study the above framework in the asymptotic regime where \(n\to \infty\). Throughout, we focus on the dense regime where \(q\in(0,1)\) is fixed.

In this work, we consider a variant of the detection problem above, where one can only inspect a small part of the graph by non-adaptive edge queries, defined as follows.

We consider query mechanisms that evolve dynamically over \(\mathsf{Q}\) steps/queries in the following form: in step number \(\ell\in[\mathsf{Q}]\), the mechanism chooses a pair of vertices \(\mathsf{e}_\ell\triangleq (i_\ell,j_\ell)\) 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 \(\ell\)th pair may depend on the previously chosen pairs \(\{\mathsf{e}_i\}_{i<\ell}\), as well as on past responses \(\{{\cal O}(\mathsf{e}_i)\}_{i<\ell}\). In non-adaptive mechanisms, on the other hand, all queries must be made upfront. In this paper we focus on non-adaptive mechanisms. The query detection problem is defined as follows.

For a given (possibly random) query set \(\mathbb{Q}_n\subseteq \binom{[n]}{2}\), we denote by \[\begin{align} \mathsf{G}_{\mathbb{Q}_n} \triangleq (\mathsf{G}_e)_{e\in \mathbb{Q}_n}\in\{0,1\}^{|\mathbb{Q}_n|} \end{align}\] the observed transcript of oracle responses. We let \(\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}\) and \(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n}\) denote the distributions of \(\mathsf{G}_{\mathbb{Q}_n}\) under the null and alternative hypotheses, respectively. A (possibly randomized) detection algorithm \({\cal A}_n\) is a measurable function \[\begin{align} {\cal A}_n:\{0,1\}^{|\mathbb{Q}_n|}\to\{0,1\}, \end{align}\] which, based on the observed transcript \(\mathsf{G}_{\mathbb{Q}_n}\), outputs a decision in \(\{0,1\}\). The risk of \({\cal A}_n\) (with respect to the query set \(\mathbb{Q}_n\)) is defined as \[\begin{align} \mathsf{R}_n({\cal A}_n;\mathbb{Q}_n) \triangleq \mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}\left({\cal A}_n(\mathsf{G}_{\mathbb{Q}_n})=1\right) + \mathbb{P}_{{\cal H}_1,\mathbb{Q}_n}\left({\cal A}_n(\mathsf{G}_{\mathbb{Q}_n})=0\right), \end{align}\] that is, the sum of the Type-I and Type-II error probabilities. The optimal risk associated with the query set \(\mathbb{Q}_n\) is \[\begin{align} \mathsf{R}_n^\star(\mathbb{Q}_n) \triangleq \inf_{{\cal A}_n}\mathsf{R}_n({\cal A}_n;\mathbb{Q}_n). \end{align}\] It is well known (see, e.g., Le Cam’s lemma [35]) that \[\begin{align} \mathsf{R}_n^\star(\mathbb{Q}_n) = 1 - d_{\mathsf{TV}}\left(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}\right), \label{eq:opt95risk95tv} \end{align}\tag{2}\] so that the statistical difficulty of the problem is fully characterized by the total variation distance between the two induced transcript distributions. Finally, the optimal risk under query budget \(\mathsf{Q}_n\) is defined by \[\begin{align} \mathsf{R}_{n,\mathsf{Q}_n}^\star \triangleq \inf_{\substack{\mathbb{Q}_n\subseteq \binom{[n]}{2}\\ |\mathbb{Q}_n|\le \mathsf{Q}_n}} \mathsf{R}_n^\star(\mathbb{Q}_n) = 1- \sup_{\substack{\mathbb{Q}_n\subseteq \binom{[n]}{2}\\ |\mathbb{Q}_n|\le \mathsf{Q}_n}} d_{\mathsf{TV}}\left( \mathbb{P}_{{\cal H}_1,\mathbb{Q}_n}, \mathbb{P}_{{\cal H}_0,\mathbb{Q}_n} \right). \label{eq:budget95opt95risk95tv} \end{align}\tag{3}\] We consider the following types of detection guarantees.

Our results will be expressed in terms of the following graph theoretic measures. We let \(d_{\mathsf{max}}\left(\Gamma_n\right)\) denote the maximum degree in \(\Gamma_n\), and we define the density of \(\Gamma_n\) as \(\eta(\Gamma_n)\triangleq |e(\Gamma_n)|/|v(\Gamma_n)|\). Finally, we recall the following definitions of the maximum subgraph density and vertex cover.

3 Main results↩︎

In this section we present our main results. We begin with general statistical lower bounds that apply to any planted graph sequence \((\Gamma_n)\), followed by general upper bounds achieved by concrete algorithms. We then summarize how these bounds compare across different structural regimes.

3.1 Statistical lower bounds↩︎

Our first result is a universal lower bound based only on the total number of edges.

The proof of Theorem 1 is based on a simple but fundamental observation: unless the query set \(\mathbb{Q}\) intersects the planted edges, the two models are statistically indistinguishable. Indeed, under the alternative, the only difference from the null model occurs on the planted edges. If none of the queried edges belongs to the planted copy \(\Gamma^\star\), then all queried edges are distributed as \(\mathsf{Bern}(q)\) exactly as under the null. Therefore, conditioned on the event that \(\mathbb{Q}\cap e(\Gamma^\star)=\emptyset\), the observed transcript has the same distribution under \({\cal H}_0\) and \({\cal H}_1\). The probability of observing at least one planted edge is at most \(\mathsf{Q}_n |e(\Gamma_n)|/\binom{n}{2}\), since each queried edge hits the planted subgraph with probability \(|e(\Gamma_n)|/\binom{n}{2}\). When \(\mathsf{Q}_n \ll n^2/|e(\Gamma_n)|\), this probability tends to zero, meaning that with high probability the algorithm never “touches” the planted structure at all. In this regime, no test can perform better than random guessing.

Roughly speaking, the edge-hit lower bound is tight (up to polylogarithmic factors) whenever detection can be achieved by identifying a single planted edge. This occurs when the graph \(\Gamma_n\) contains many dense local structures, or more generally when there exists a subgraph \(H_n\subseteq \Gamma_n\) that appears sufficiently frequently and can be detected via brute-force scanning; this will be made precise in the upper bounds section. Typical examples include clique-like or biclique-like graphs, where dense substructures allow detection as soon as one planted region is queried. In contrast, for hub-dominated or bounded-cover graphs, detection requires aggregating information across many edges, and the edge-hit bound is no longer tight. This motivates the need for a more refined lower bound that captures structural properties beyond the total number of edges. To this end, we next present a general structural lower bound based on a vertex-cover decomposition of \(\Gamma_n\).

To present this bound, we introduce a few important notations. For each \(n\), choose a vertex cover \(U_n\subseteq v(\Gamma_n)\), and denote by \(\tau_n\triangleq |U_n|\) its size. Define \(W_n\triangleq v(\Gamma_n)\setminus U_n\) and \(H_n\triangleq \Gamma_n[U_n]\) to be a cover-induced subgraph of \(\Gamma_n\) on the vertex cover \(U_n\). For each \(w\in W_n\), define its neighborhood inside the chosen cover by \[\begin{align} N_n(w)\triangleq N_{\Gamma_n}(w)\cap U_n. \end{align}\] For each integer \(r\in\{1,\ldots,\tau_n\}\), define \[\begin{align} \Theta_{r,n} \triangleq \sum_{w,w'\in W_n} \binom{|N_n(w)\cap N_n(w')|}{r}. \label{eq:Theta95r95cover95reduction95equiv} \end{align}\tag{4}\] For each \(n\), let \(\mathbb{Q}_n\subseteq \binom{[n]}{2}\) be a deterministic non-adaptive query set of size \(\mathsf{Q}_n\triangleq |\mathbb{Q}_n|\). For each vertex \(i\in[n]\), define its query degree \[\begin{align} t_i^{(n)}(\mathbb{Q}_n) \triangleq \left|\{j\in[n]\setminus\{i\}:\{i,j\}\in\mathbb{Q}_n\}\right|, \end{align}\] and for each integer \(r\in\{1,\ldots,\tau_n\}\) set \[\begin{align} \zeta_{r,n}(\mathbb{Q}_n) \triangleq \sum_{i=1}^n \frac{(t_i^{(n)})_r}{(n)_r}, \label{eq:zeta95r95cover95reduction} \end{align}\tag{5}\] where \((a)_r\triangleq a(a-1)\cdots(a-r+1)\) denotes the falling factorial. Finally, define an auxiliary planted model \(\mathbb{P}_{H_n,\mathbb{Q}_n}\) as follows: sample a uniformly random injective map \(\varphi_n:U_n\hookrightarrow [n]\), and plant only the graph \(H_n\) on the image \(\varphi_n(U_n)\), and then draw every remaining ambient edge independently as \(\mathsf{Bern}(q)\). We have the following result.

Theorem [thm:cover95reduction95query95lb] has several noteworthy features. The theorem is based on a structural decomposition of the planted graph \(\Gamma_n\) via a vertex cover \(U_n\). The vertex cover isolates a core subgraph \(H_n=\Gamma_n[U_n]\), while the remaining vertices \(W_n=v(\Gamma_n)\setminus U_n\) form an independent set. Consequently, every edge of \(\Gamma_n\) is either contained in the core or connects a vertex in \(W_n\) to the core. The theorem compares the original planted model to an auxiliary model in which only the core \(H_n\) is planted, while all edges incident to \(W_n\) are generated according to the null model. The first condition, [eq:assump95core95undetectable], requires that the core itself be statistically indistinguishable from the null under the available query budget. The second condition, [eq:assump95remainder95negligible], quantifies the additional information carried by the attachment layer. Here, \(\Theta_{r,n}\) measures the amount of overlap between neighborhoods of vertices in \(W_n\), while \(\zeta_{r,n}\) measures the ability of the query mechanism to simultaneously probe \(r\) vertices of the core. Their weighted combination therefore captures the total second-moment contribution of the attachment layer.

Theorem [thm:cover95reduction95query95lb] should therefore be viewed as a reduction principle rather than as a standalone lower bound. It separates the problem of proving undetectability into two simpler tasks: establishing that a suitably chosen core \(H_n\) is itself undetectable, and showing that the remaining attachment layer contributes negligibly. This viewpoint makes it possible to combine lower bounds tailored to different graph families within a single unified framework. For example, clique-like or biclique-like cores can be handled using the edge-hit lower bound, whereas for hub-dominated graph families the core is often trivial and the attachment layer completely determines the statistical threshold. More generally, different lower-bound techniques may be used to verify the first condition, while the second condition provides a universal characterization of the contribution of the attachment layer. As will be demonstrated later, this decomposition can yield substantially sharper lower bounds than the direct edge-hit argument, and in many examples an appropriate choice of the vertex cover eliminates all but a few terms in the sum defining [eq:assump95remainder95negligible], leading to simple and nearly tight impossibility results.

At first sight, condition [eq:assump95remainder95negligible] may appear difficult to verify because it depends on the query mechanism through the quantities \(\zeta_{r,n}(\mathbb{Q}_n)\). Fortunately, a simple combinatorial argument shows that \(\zeta_{r,n}(\mathbb{Q}_n)\le 2\mathsf{Q}_n/n\) for every \(r\) and every query set \(\mathbb{Q}_n\). Consequently, [eq:assump95remainder95negligible] admits a simple sufficient condition depending only on graph-theoretic parameters of \(\Gamma_n\) and the query budget \(\mathsf{Q}_n\), completely eliminating the optimization over \(\mathbb{Q}_n\). This simplified form is presented in the supplementary material and is the version used throughout the corollaries and examples in the remainder of the paper.

3.2 Upper bounds↩︎

We now present three detection procedures, each tailored to a different structural feature of the planted graph \(\Gamma_n\). All procedures are non-adaptive. We start with the witness scan test, which attempts to detect a fixed subgraph \(H\subseteq \Gamma_n\) by querying a random subset of vertices and checking whether the induced queried graph contains a copy of \(H\); see Algorithm 2. We have the following result.

The scan test succeeds by finding a planted witness inside the queried subgraph. The first condition controls false positives under the null (requiring \(H_n\) to be sufficiently dense), while the second ensures that at least one planted copy of \(H_n\) falls entirely inside the queried set. The third condition guarantees that different planted copies do not overlap too heavily. Ignoring lower-order effects, the scan test operates at the scale \[\begin{align} \mathsf{Q}_n \asymp \frac{n^2}{N(H_n,\Gamma_n)^{2/v_n}}, \end{align}\] and is therefore most effective when \(\Gamma_n\) contains many dense substructures. In particular, for clique-like or biclique-like graphs, the scan test matches the edge-hit lower bound up to polylogarithmic factors.

We next present the degree-on-a-cut test, a polynomial-time algorithm that exploits high-degree vertices; see Algorithm 3. We have the following result.

The DegreeCut algorithm detects vertices whose degree toward a random subset is significantly larger than expected under the null. This method is particularly effective for hub-dominated structures, such as stars or bounded-cover graphs, where a small number of vertices carry a large fraction of the edges. In these regimes, DegreeCut matches the structural lower bounds up to logarithmic factors. However, for dense homogeneous graphs (e.g., cliques), it is suboptimal.

To better appreciate Theorem 4 let us extract a closed-form condition for the query complexity of DegreeCut algorithm. For a fixed \(d\in\{1,\dots,d_{\mathsf{max}}(\Gamma_n)\}\), the query budget is \[\begin{align} \mathsf{Q}_{\mathsf{cut}}(d) \lesssim \frac{n^3\log^2 n}{d^2\max\{m_d(\Gamma_n),\log n\}}, \label{eq:degcut95saturated95budget} \end{align}\tag{6}\] subject to \(d^2 \gtrsim n\log n\) (which follows from the constraint that \(m\leq n/2\)). Equivalently, define the saturated high-degree mass \[\begin{align} \kappa(\Gamma_n) \triangleq \max_{\substack{1\le d\leq d_{\max}(\Gamma_n)\;d^2\gtrsim n\log n}} d^2\max\{m_d(\Gamma_n),\log n\}. \end{align}\] Then the degree-on-a-cut upper bound is \[\begin{align} \mathsf{Q}_n \gtrsim \frac{n^3\log^2 n}{\kappa_{\mathrm{sat}}(\Gamma_n)} \end{align}\] as a sufficient condition for strong detection, provided the maximizing degree level also satisfies the remaining feasibility condition in Theorem 4.

Finally, we propose the edge count test, defined as follows. Let \(\mathbb{Q}_n\) be a set of \(\mathsf{Q}\) edges drawn uniformly at random from \(\binom{[n]}{2}\). Define the statistic \[\begin{align} \mathsf{X}_{\mathsf{count}}\triangleq \sum_{e\in\mathbb{Q}_n}\mathbb{1}\{e\in e(\mathsf{G})\}, \end{align}\] and consider the test \({\cal A}_{\mathsf{count}}\triangleq \mathbb{1}\{\mathsf{X}_{\mathsf{count}}\ge q\mathsf{Q} + \lambda\sqrt{q(1-q)\mathsf{Q}}\}\), for any \(\lambda=\lambda_n\to\infty\).

As we will show in the next section, each of these algorithms is optimal (up to polylogarithmic factors) in a different regime.

3.3 Corollaries and examples↩︎

We now illustrate the general lower and upper bounds on several natural graph families. These examples show that the upper bounds are each optimal in different structural regimes.

We begin with a convenient simplification of Theorem [thm:cover95reduction95query95lb]. A simple combinatorial bound shows that \(\zeta_{r,n}\le 2\mathsf{Q}_n/n\) for every \(r\), and therefore the weighted remainder condition in Theorem [thm:cover95reduction95query95lb] may often be reduced to a more explicit expression.

This is the main tool used below. In most examples, one chooses a vertex cover \(U_n\) so that the induced core \(H_n\) is extremely simple (often edgeless or a matching), and then computes the quantities \(\Theta_{r,n}\) explicitly. In many cases only the first one or two terms in the sum over \(r\) survive.

Before proceeding, it is worth noting that in the full-observation regime, where \(\mathbb{Q}n=\binom{[n]}{2}\), the three query algorithms introduced in Subsection 3.2 reduce to the corresponding optimal full-observation tests. In particular, the sufficient conditions in Theorems 3–5 simplify to \[\begin{align} \mu(\Gamma_n)=\Omega(\log n)\quad\mathsf{or}\quad|e(\Gamma_n)|=\omega(n)\quad\mathsf{or}\quad d_{\mathsf{max}}(\Gamma_n)=\Omega(\sqrt{n\log n}). \end{align}\] These coincide (up to constant factors) with the (tight) statistical and computational thresholds established for the full-observation model in [14].

1.25ex -1em Hub-dominated graphs.

Our first example correspond to the regime where the graph is dominated by high-degree vertices. This includes, as a special case, arbitrary star forests. In this regime, the lower bound is captured by the cover-reduction theorem, while the matching upper bound is achieved by the degree-on-a-cut test.

This corollary is obtained by choosing the high-degree layer \(U_n\) as the vertex cover. Since the induced core \(H_n\) is edgeless, the core is automatically undetectable. Moreover, every vertex in \(W_n\) contributes to exactly one singleton neighborhood inside the cover, so only the \(r=1\) term survives in the cover-reduction lower bound. This yields the lower-bound scale \[\begin{align} \mathsf{Q}_n \asymp \frac{n^3}{S_{2,n}}, \qquad S_{2,n}=\sum_{u\in U_n} d_{W_n}^2(u). \end{align}\] On the upper-bound side, the degree-on-a-cut test is controlled by \(\kappa_n=\max_d m_d(\Gamma_n)d^2\) which measures the mass of the high-degree layer. A dyadic decomposition shows that \(S_{2,n}\) and \(\kappa_n\) differ by at most a logarithmic factor, so the two bounds essentially coincide.

Star forests are a special case of this proposition: if \[\begin{align} \Gamma_n=\bigsqcup_{j=1}^{r_n} K_{1,d_{j,n}}, \end{align}\] then one takes \(U_n\) to be the set of star centers, and obtains \[\begin{align} S_{2,n}=\sum_{j=1}^{r_n} d_{j,n}^2. \end{align}\] In the equal-degree case \(\Gamma_n=\bigsqcup_{j=1}^{r_n} K_{1,\Delta_n}\), this becomes \[\begin{align} S_{2,n}=r_n\Delta_n^2,\quad m_{\Delta_n}(\Gamma_n)=r_n, \end{align}\] and therefore \[\begin{align} \kappa(\Gamma_n) = \Delta_n^2\max\{r_n,\log n\}, \end{align}\] provided \(\Delta_n^2\gtrsim n\log n\); otherwise no degree level satisfies the feasibility condition and the degree-on-a-cut bound does not apply. Consequently, the sufficient query complexity becomes \[\begin{align} \mathsf{Q}_n \gtrsim \frac{n^3\log^2n}{\Delta_n^2\max\{r_n,\log n\}}. \end{align}\] Thus, we see that the lower and upper bounds match up to the \(\log^2 n\) factor of the degree-on-a-cut test: \[\begin{align} \mathsf{Q}_n \asymp \frac{n^3}{\Delta_n^2\max\{r_n,\log n\}} \qquad\text{up to polylogarithmic factors.} \end{align}\] Finally, note that in the full-observation regime, where \(Q_n=\binom{n}{2}\), this condition reduces to \(\Delta_n\gtrsim\sqrt{n\log n}\), independently of the number of stars \(r_n\), recovering the optimal maximum-degree threshold established in [14].

1.25ex -1em Sparse low-density structures. The next examples show that for certain sparse families, the problem is already impossible under full observation. In such cases, no query-based procedure can be sharp, since even seeing the entire graph does not help.

Choose every other vertex of the path as a cover. Then the induced core is edgeless, and each uncovered vertex has at most two neighbors in the cover. As a result, only the terms \(r=1,2\) contribute in the cover-reduction bound, both at total scale \(O(k_n)\). Under full observation this gives impossibility whenever \(k_n=o(n)\).

For each triangle, place two vertices in the cover and one outside. Then the induced core becomes a matching of size \(m_n\), which is already undetectable under full observation when \(m_n=o(n)\). The remainder term is also of order \(k_n/n\), since only the terms \(r=1,2\) contribute. Hence the full planted graph is undetectable as well.

Choose the smaller side of a bipartition of the tree as the cover. Then the induced core is edgeless. Since degrees are uniformly bounded by \(D\), only finitely many terms in the cover-reduction sum contribute, and each contributes at scale \(O(k_n)\). Under full observation this yields impossibility whenever \(k_n=o(n)\).

1.25ex -1em Bounded-cover graphs. We next obtain a general impossibility result for all graph families with bounded vertex-cover number, such as a star graph.

The proof uses a minimum vertex cover \(U_n\). Since \(|U_n|\) is uniformly bounded, the core \(H_n=\Gamma_n[U_n]\) has bounded size and is therefore undetectable. The remainder term is controlled by \(\Delta_n^2\), since each uncovered vertex can only attach to the bounded cover. This shows that bounded-cover families have lower-bound scale \(n^3/\Delta_n^2\). This lower bound is complemented by the degree-on-a-cut upper bound whenever the high-degree mass is concentrated. In particular, if \(\kappa(\Gamma_n)\asymp \Delta_n^2\), then DegreeCut achieves strong detection with \[\begin{align} \mathsf{Q}_n\gtrsim \frac{n^3}{\Delta_n^2}\log^2 n. \end{align}\]

1.25ex -1em Clique-like structures. For clique-like graphs, the direct edge-hit lower bound is the relevant one, and it is complemented by the scan upper bound.

For cliques, the direct edge-hit lower bound already gives the correct scale, since \[\begin{align} |e(K_{k_n})|\asymp k_n^2. \end{align}\] On the upper-bound side, one can choose a smaller clique witness \(H_n=K_{h_n}\) with \(h_n\asymp C\log n\) and apply the scan test. This yields strong detection at query complexity \[\begin{align} \mathsf{Q}_n\asymp \frac{n^2}{k_n^2}\cdot \mathrm{polylog}(n), \end{align}\] so the lower and upper bounds match up to polylogarithmic factors, coinciding with the classical results [29] (see also [30]–[33]).

Unlike the clique example, the direct edge-hit lower bound applied to the entire graph only yields \[\begin{align} \mathsf{Q}_n = o\left(n^2/[k_n^2+k_n\Delta_n] \right), \end{align}\] which can be substantially weaker. The improvement comes from Theorem [thm:cover95reduction95query95lb]: choosing the clique as the core separates the dense part of the graph from the pendant leaves. The clique itself is handled by the edge-hit lower bound, while the contribution of the leaves is controlled independently through the attachment term in Theorem [thm:cover95reduction95query95lb]. Thus, the decomposition recognizes that the pendant edges do not carry independent statistical information and avoids paying for their total number.

The upper bounds exhibit exactly the same two competing mechanisms. Using the clique as a witness, the scan test achieves strong detection with \[\begin{align} \mathsf{Q}_n \asymp n^2/k_n^2, \end{align}\] up to polylogarithmic factors. On the other hand, the degree-on-a-cut test exploits the large degrees of the clique vertices and succeeds with \[\begin{align} \mathsf{Q}_n \asymp \frac{n^3}{(k_n+\Delta_n)^2 \max\{k_n,\log n\}} \log^2 n. \end{align}\] Consequently, the query complexity is determined by whichever of these two mechanisms is stronger, and complements Corollary 8. This example illustrates the advantage of the vertex-cover reduction in Theorem [thm:cover95reduction95query95lb]: by separating the statistically informative clique from the low-complexity attachment layer, it yields a substantially sharper lower bound than treating the planted graph as a whole. Moreover, it highlights the complementary nature of the scan and degree-on-a-cut algorithms, whose performances are governed by the dense core and the high-degree attachment layer, respectively.

1.25ex -1em Complete bipartite graphs. Complete bipartite graphs interpolate between the clique-like scan regime and the bounded-cover degree regime.

There are two different upper-bound mechanisms here: 1) If one side is much smaller than the other, the graph behaves like a hub-dominated structure, and DegreeCut is the relevant algorithm. 2) If the two sides are comparable and both at least logarithmic, then one can scan for a logarithmic complete bipartite witness, and the scan test matches the lower bound up to polylogarithmic factors. In particular, the balanced regime behaves like the clique case, while the highly unbalanced regime behaves like a star.

To conclude, for complete bipartite graphs \(\Gamma_n=K_{a_n,b_n}\), the present results leave only one unresolved regime is \(1\ll a_n\ll \log n\). Indeed:

• if \(a_n=O(1)\), then the bounded-cover lower bound matches the degree-on-a-cut upper bound up to \(\log^2 n\);

• if \(a_n,b_n\gtrsim \log n\) and \(b_n\le \rho a_n\), then the edge-hit lower bound matches the scan upper bound up to polylogarithmic factors.

Thus the only remaining gap is the intermediate regime where the smaller side is too large for bounded-cover arguments to be sharp, but too small to support logarithmic biclique witnesses.

The examples above illustrate the general picture: the scan test is sharp for clique-like and dense local structures; the degree-on-a-cut test is sharp for hub-dominated and bounded-cover structures. At the opposite extreme, for sparse low-density structures such as bounded-degree trees, paths, or sparse unions of triangles, detection is already impossible under full observation.

4 Proofs of lower bounds↩︎

4.1 Preliminaries↩︎

We start with some preliminaries. Our goal is to establish lower bounds on the optimal risk, thereby ruling out the possibility of successful detection. We begin by introducing the likelihood ratio, \[\begin{align} \mathsf{L}(\mathsf{G}) \triangleq \frac{\mathrm{d}{\mathbb{P}}_{{\cal H}_1}}{\mathrm{d}{\mathbb{P}}_{{\cal H}_0}}(\mathsf{G}), \label{eqn:LIKlihood} \end{align}\tag{7}\] which is the Radon–Nikodym derivative of \({\mathbb{P}}_{{\cal H}_1}\) with respect to \({\mathbb{P}}_{{\cal H}_0}\). It is well known (see, e.g., [35]) that the test minimizing the risk \(\mathsf{R}n\) is the likelihood ratio test \[\begin{align} \phi^{\star}(\mathsf{G}) \triangleq \begin{cases} 1, & \text{if } \mathsf{L}(\mathsf{G}) \ge 1,\\ 0, & \text{otherwise}, \end{cases} \end{align}\] and the corresponding optimal risk is given by \[\begin{align} \mathsf{R}_n^\star &= \inf_{{\cal A}_n}\mathbb{P}_{{\cal H}_0}\left({\cal A}_n(\mathsf{G})=1\right) + \mathbb{P}_{{\cal H}_1}\left({\cal A}_n(\mathsf{G})=0\right) \\ &=1 - d_{\mathsf{TV}}({\mathbb{P}}_{{\cal H}_0}, {\mathbb{P}}_{{\cal H}_1}). \end{align}\] Recalling that \[\begin{align} \chi^2({\mathbb{P}}_{{\cal H}_1}\|{\mathbb{P}}_{{\cal H}_0}) = \mathbb{E}_{{\cal H}_0}[\mathsf{L}(\mathsf{G})^2] - 1, \end{align}\] standard inequalities relating total variation and \(\chi^2\) divergence (see, e.g., [35]) imply that \[\begin{align} \mathsf{R}_n^\star \ge 1 - \frac{1}{2}\sqrt{\chi^2({\mathbb{P}}_{{\cal H}_1}\|{\mathbb{P}}_{{\cal H}_0})}. \label{eqn:lowerBoundSecond} \end{align}\tag{8}\] In particular, if \(\mathbb{E}_{{\cal H}_0}[\mathsf{L}(\mathsf{G})^2] = 1 + o(1)\), then \(\chi^2({\mathbb{P}}_{{\cal H}_1}\|{\mathbb{P}}_{{\cal H}_0}) \to 0\), which implies \(\mathsf{R}_n^\star \to 1\), and hence weak detection is impossible. This shows that controlling the second moment of the likelihood ratio under the null is sufficient to establish impossibility. In the remainder of this section, we derive bounds on \(\mathbb{E}_{{\cal H}_0}[\mathsf{L}(\mathsf{G})^2]\) and identify conditions under which it converges to one.

The following result is a straightforward characterization of the chi-square distance between the null and alternative distributions, given any non-adaptive query mechanism \(\mathbb{Q}\).

4.2 Proof of Theorem 1↩︎

Fix an arbitrary deterministic non-adaptive query set \(\mathbb{Q}_n\subseteq\binom{[n]}{2}\) with \(|\mathbb{Q}_n|\le \mathsf{Q}_n\). We will couple the transcript under \(\mathcal{H}_1\) to that under \(\mathcal{H}_0\) on an event of high probability. Let \(\Gamma^\star\) be the planted copy under \(\mathcal{H}_1\). Define the event \[\begin{align} \mathcal{E} \triangleq \{\mathbb{Q}\cap e(\Gamma^\star)=\emptyset\}, \end{align}\] i.e., none of the queried edges is planted. On the event \(\mathcal{E}\), every queried edge \(e\in\mathbb{Q}\) is not a planted edge. Under the alternative, all non-planted edges are distributed as \(\mathsf{Bern}(q)\) exactly as under \(\mathcal{H}_0\), and are independent across queried edges. Hence the conditional law of \(\mathsf{G}_{\mathbb{Q}}\) given \(\mathcal{E}\) under \(\mathcal{H}_1\) coincides with the unconditional law of \(\mathsf{G}_{\mathbb{Q}}\) under \(\mathcal{H}_0\), namely, \[\begin{align} \mathbb{P}_{{\cal H}_1,\mathbb{Q}}(\cdot\vert \mathcal{E})=\mathbb{P}_{{\cal H}_0,\mathbb{Q}}(\cdot). \end{align}\] Therefore, \[\begin{align} d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_0,\mathbb{Q}},\mathbb{P}_{{\cal H}_1,\mathbb{Q}}) \leq \mathbb{P}_{{\cal H}_1,\mathbb{Q}}(\mathcal{E}^c), \end{align}\] which implies that \[\begin{align} \mathsf{R}^\star_{\mathbb{Q}}\ge 1-d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_0,\mathbb{Q}},\mathbb{P}_{{\cal H}_1,\mathbb{Q}}) \ge 1-\mathbb{P}_{{\cal H}_1,\mathbb{Q}}(\mathcal{E}^c). \end{align}\] Thus it suffices to show that \(\mathbb{P}_{{\cal H}_1,\mathbb{Q}}(\mathcal{E}^c)\to 0\). Since \(\Gamma^\star\) is a uniform random copy of \(\Gamma\) in \(\mathcal{K}_n\), its planted edge set \(e(\Gamma^\star)\) has size \(m_n\) and, by symmetry over the \(N\triangleq \binom{n}{2}\) unordered vertex pairs, each fixed edge \(e\in\binom{[n]}{2}\) satisfies \[\begin{align} \mathbb{P}[e\in e(\Gamma^\star)]=\frac{m_n}{N}. \end{align}\] Therefore, by a union bound, \[\begin{align} \mathbb{P}_{{\cal H}_1,\mathbb{Q}_n}(\mathcal{E}^c) &= \mathbb{P}\left[\exists e\in\mathbb{Q}_n:\; e\in e(\Gamma^\star)\right]\\ &\le \sum_{e\in\mathbb{Q}_n}\mathbb{P}[e\in e(\Gamma^\star)]\\ &= |\mathbb{Q}_n|\cdot \frac{m_n}{N}\\ &\le \mathsf{Q}_n\cdot \frac{m_n}{N}. \label{eqn:boundBudgError} \end{align}\tag{9}\] Under ?? , the right-hand side tends to \(0\). Since 9 holds uniformly over all deterministic non-adaptive query sets \(\mathbb{Q}_n\) with \(|\mathbb{Q}_n|\le \mathsf{Q}_n\), we obtain \[\begin{align} \sup_{|\mathbb{Q}_n|\le \mathsf{Q}_n} d_{\mathsf{TV}}\left(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}\right) \to 0. \end{align}\] Consequently, \(\mathsf{R}_{n,\mathsf{Q}_n}^{\star}\to 1\), which completes the proof.

4.3 Proof of Theorem [thm:cover95reduction95query95lb]↩︎

We recall the following definitions. For each \(n\), we let \(\Gamma_n=(V_n,E_n)\), and \(|V_n|\leq n\), where \(V_n = v(\Gamma_n)\) and \(E_n = e(\Gamma_n)\). For each \(n\), choose a vertex cover \(U_n\subseteq V_n\), and denote by \(\tau_n\triangleq |U_n|\) its size. Define \(W_n\triangleq V_n\setminus U_n\) and \(H_n\triangleq \Gamma_n[U_n]\) to be a cover-induced subgraph of \(\Gamma_n\) on the vertex cover \(U_n\). For each \(w\in W_n\), define its neighborhood inside the chosen cover by \[\begin{align} N_n(w)\triangleq N_{\Gamma_n}(w)\cap U_n. \end{align}\] For every nonempty subset \(R\subseteq U_n\), define \[\begin{align} \mathcal{W}_n(R)\triangleq \{w\in W_n:R\subseteq N_n(w)\}. \end{align}\] For each integer \(r\in\{1,\ldots,\tau_n\}\), define \[\begin{align} \Theta_{r,n} \triangleq \sum_{\substack{R\subseteq U_n\\ |R|=r}} |\mathcal{W}_n(R)|^2= \sum_{w,w'\in W_n} \binom{|N_n(w)\cap N_n(w')|}{r}. \label{eq:Theta95r95cover95reduction} \end{align}\tag{10}\] For each \(n\), let \(\mathbb{Q}_n\subseteq \binom{[n]}{2}\) be a deterministic non-adaptive query set of size \(\mathsf{Q}_n\triangleq |\mathbb{Q}_n|\).

Fix \(n\); to lighten notation we remove the subscript \(n\) from the various variables below. If \(W=\emptyset\), then \(U=V_n\) and hence \(H=\Gamma_n\). In that case the full planted model and the auxiliary planted model coincide \(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n}=\mathbb{P}_{H_n,\mathbb{Q}_n}\). Therefore the conclusion follows immediately from [eq:assump95core95undetectable]. Thus, for the remainder of the proof, we may and shall assume that \(W\neq\emptyset\), in particular, \(\tau\leq n-1\). Our goal is to prove \[\begin{align} d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{H_n,\mathbb{Q}_n})\to 0. \label{eq:goal95full95vs95aux} \end{align}\tag{11}\] Indeed, once 11 is established, the triangle inequality gives \[\begin{align} d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}) \le d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{H_n,\mathbb{Q}_n}) + d_{\mathsf{TV}}(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}), \end{align}\] and the right-hand side tends to \(0\) by 11 and [eq:assump95core95undetectable]. Now, under the full planted model, let \(\Phi_n:V_n\hookrightarrow [n]\) be the random injective embedding of \(\Gamma_n\) into \(K_n\). Define the ordered image of the chosen cover by \[\begin{align} A_n&\triangleq (a_u)_{u\in U},\\ a_u&\triangleq \Phi_n(u),\quad u\in U. \end{align}\] Under the auxiliary planted model, the cover vertices are embedded by the uniformly random injective map \(\varphi_n:U\hookrightarrow [n]\). Define similarly \[\begin{align} A_n'\triangleq (\varphi_n(u))_{u\in U},\quad u\in U. \end{align}\] Since in both models the map from \(U\) to \([n]\) is uniformly random and injective, the random ordered tuples \(A_n\) and \(A_n'\) have the same distribution. Fix an ordered \(\tau\)-tuple \(A=(a_u)_{u\in U}\) of distinct vertices of \([n]\). We define two conditional laws on the queried transcript.

• \(\mathbb{P}^\Gamma_{A,\mathbb{Q}}\) is the law of the queried transcript under the full planted model, conditioned on \(\Phi_n(u)=a_u\), for all \(u\in U\).

• \(\mathbb{P}^H_{A,\mathbb{Q}}\) is the law of the queried transcript under the auxiliary planted model, conditioned on \(\varphi_n(u)=a_u\), for all \(u\in U\).

By conditioning on the random ordered image of the cover, both original laws are mixtures of these conditional laws: \[\begin{align} \mathbb{P}_{{\cal H}_1,\mathbb{Q}_n} &= \mathbb{E}_{A_n}\bigl[\mathbb{P}^\Gamma_{A_n,\mathbb{Q}}\bigr], \\ \mathbb{P}_{H_n,\mathbb{Q}_n} &= \mathbb{E}_{A_n}\bigl[\mathbb{P}^H_{A_n,\mathbb{Q}}\bigr]. \label{eq:mixture95representation95cover} \end{align}\tag{12}\] Now fix the tuple \(A\). Since \(U\) is a vertex cover of \(\Gamma_n\), the set \(W=V_n\setminus U\) is an independent set in \(\Gamma_n\). Consequently, in both models, the planted edges inside the set \(A\) are exactly the edges of \(H=\Gamma_n[U]\), and in both models, no edges are planted with both endpoints outside \(A\). Therefore the conditional laws \(\mathbb{P}^\Gamma_{A,\mathbb{Q}}\) and \(\mathbb{P}^H_{A,\mathbb{Q}}\) can differ only on queried edges joining \(A\) to vertices outside \(A\). Define \[\begin{align} {\cal B}_A \triangleq \left\{ v\in[n]\setminus A: \exists u\in U\;\mathsf{s.t.}\;\{a_u,v\}\in \mathbb{Q}\right\}, \end{align}\] and \[\begin{align} M_A\triangleq |{\cal B}_A|. \end{align}\] Also define \[\begin{align} \mathcal{E}_A \triangleq \left\{ \{a_u,v\}\in \mathbb{Q}: u\in U,\;v\in {\cal B}_A \right\}. \end{align}\] Thus \(\mathcal{E}_A\) is precisely the set of queried edges on which the two conditional laws may differ.

Fix \(A\) as above. Let \(\Gamma^A\) denote a random planted copy of \(\Gamma_n\) under the full model conditioned on the event \(\Phi_n(u)=a_u\), for all \(u\in U\). For any subset \(S\subseteq \mathcal{E}_A\), define \[\begin{align} p_A(S)\triangleq \mathbb{P}\left[S\subseteq e(\Gamma^A)\right]. \end{align}\] We claim that \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) = \sum_{S\subseteq \mathcal{E}_A} (q^{-1}-1)^{|S|}p^2_A(S). \label{eq:conditional95chi295cover} \end{align}\tag{13}\] Indeed, to that end, note that under the auxiliary model conditioned on \(A\), every queried edge in \(\mathcal{E}_A\) is independent \(\mathsf{Bern}(q)\), because the auxiliary model only plants edges of \(H\) inside \(A\) and does not plant any edge between \(A\) and its complement. Conditioned on a realization of the random planted copy \(\Gamma^A\), every queried edge in \(e(\Gamma^A)\cap \mathcal{E}_A\) is forced to be present, while every queried edge in \(\mathcal{E}_A\setminus e(\Gamma^A)\) is \(\mathsf{Bern}(q)\) and independent of the others. Let \(Y=(Y_e)_{e\in\mathcal{E}_A}\) denote the queried transcript restricted to \(\mathcal{E}_A\). The likelihood ratio of \(\mathbb{P}^\Gamma_{A,\mathbb{Q}}\) with respect to \(\mathbb{P}^H_{A,\mathbb{Q}}\) on the coordinates indexed by \(\mathcal{E}_A\) is \[\begin{align} {\cal L}_A(Y) = \mathbb{E}_{\Gamma^A} \left[ \prod_{e\in e(\Gamma^A)\cap \mathcal{E}_A} \frac{\mathbb{1}\{Y_e=1\}}{q} \right]. \end{align}\] Therefore \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) = \mathbb{E}_{\mathbb{P}^H_{A,\mathbb{Q}}}\left[{\cal L}^2_A(Y)\right]. \end{align}\] Introduce two independent conditioned copies \(\Gamma^A\) and \(\widetilde{\Gamma}^A\). Expanding the square and using Fubini’s theorem, \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) &= \mathbb{E}_{\Gamma^A\perp \!\!\! \perp\widetilde{\Gamma}^A} \mathbb{E}_{\mathbb{P}^H_{A,\mathbb{Q}}} \left[ \prod_{e\in e(\Gamma^A)\cap \mathcal{E}_A} \frac{\mathbb{1}\{Y_e=1\}}{q} \prod_{e\in e(\widetilde{\Gamma}^A)\cap \mathcal{E}_A} \frac{\mathbb{1}\{Y_e=1\}}{q} \right]. \end{align}\] Fix an edge \(e\in\mathcal{E}_A\). Under \(\mathbb{P}^H_{A,\mathbb{Q}}\), the variable \(Y_e\) is \(\mathsf{Bern}(q)\). Hence:

• if \(e\in e(\Gamma^A)\cap e(\widetilde{\Gamma}^A)\), then the contribution of this edge to the inner expectation equals \[\begin{align} \mathbb{E}_{\mathsf{Bern}(q)} \left[\frac{\mathbb{1}\{Y_e=1\}}{q^2}\right] = \frac{q}{q^2} = \frac{1}{q}. \end{align}\]

• otherwise the contribution equals \(1\).

Since the queried edges in \(\mathcal{E}_A\) are independent under \(\mathbb{P}^H_{A,\mathbb{Q}}\), the inner expectation is \[\begin{align} q^{-|e(\Gamma^A)\cap e(\widetilde{\Gamma}^A)\cap \mathcal{E}_A|}. \end{align}\] Thus \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) = \mathbb{E}_{\Gamma^A\perp \!\!\! \perp\widetilde{\Gamma}^A} \left[ q^{-|e(\Gamma^A)\cap e(\widetilde{\Gamma}^A)\cap \mathcal{E}_A|} \right]. \end{align}\] Now use the identity \[\begin{align} q^{-m}=(1+(q^{-1}-1))^m = \sum_{S\subseteq [m]}(q^{-1}-1)^{|S|}, \end{align}\] applied edge-by-edge. This yields \[\begin{align} q^{-|e(\Gamma^A)\cap e(\widetilde{\Gamma}^A)\cap \mathcal{E}_A|} = \sum_{S\subseteq \mathcal{E}_A} (q^{-1}-1)^{|S|} \mathbb{1}\{S\subseteq e(\Gamma^A)\cap e(\widetilde{\Gamma}^A)\}. \end{align}\] Taking expectations and using independence of \(\Gamma^A\) and \(\widetilde{\Gamma}^A\), we obtain \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) &= \sum_{S\subseteq \mathcal{E}_A} (q^{-1}-1)^{|S|} \mathbb{P}\left[S\subseteq e(\Gamma^A)\right]^2 \\ &= \sum_{S\subseteq \mathcal{E}_A} (q^{-1}-1)^{|S|}p^2_A(S). \end{align}\] This proves 13 . Next, we upper bound \(p_A(S)\). Fix \(S\subseteq \mathcal{E}_A\). For each \(v\in {\cal B}_A\), define \[\begin{align} {\cal R}_v(S)\triangleq \{u\in U:\{a_u,v\}\in S\}. \end{align}\] Let \[\begin{align} V^+(S)&\triangleq \{v\in {\cal B}_A:{\cal R}_v(S)\neq\emptyset\},\\ s(S)&\triangleq |V^+(S)|. \end{align}\] Thus \(V^+(S)\) is the set of outside vertices actually touched by the edge-set \(S\). Under the conditioning on \(A\), the vertices of \(W\) are embedded by a uniformly random injective map \(\psi:W\hookrightarrow [n]\setminus A\). For every nonempty subset \(R\subseteq U\), define \[\begin{align} \mathcal{W}(R)\triangleq \{w\in W:R\subseteq N_n(w)\}. \end{align}\] Suppose now that the event \(S\subseteq e(\Gamma^A)\) occurs. Then for each \(v\in V^+(S)\) there must exist some vertex \(w_v\in \mathcal{W}({\cal R}_v(S))\) such that \(\psi(w_v)=v\). Since \(\psi\) is injective and the vertices \(v\in V^+(S)\) are distinct, the chosen vertices \(w_v\) must also be distinct. Therefore the event \(\{S\subseteq e(\Gamma^A)\}\) implies the existence of an ordered family of distinct vertices \((w_v)_{v\in V^+(S)}\) such that \[\begin{align} w_v\in \mathcal{W}({\cal R}_v(S)) \quad\text{and}\quad \psi(w_v)=v \quad\text{for all }v\in V^+(S). \end{align}\] Now, the number of admissible ordered families \((w_v)_{v\in V^+(S)}\) is at most \[\begin{align} \prod_{v\in V^+(S)} |\mathcal{W}({\cal R}_v(S))|. \end{align}\] For each fixed admissible ordered family, since \(\psi\) is a uniformly random injective map from \(W\) to \([n]\setminus A\), the probability that \(\psi(w_v)=v\) for all \(v\in V^+(S)\) is exactly \(1/(n-\tau)_{s(S)}\). Thus, by the union bound, we deduce \[\begin{align} p_A(S) \le \frac{\prod_{v\in V^+(S)} |\mathcal{W}({\cal R}_v(S))|}{(n-\tau)_{s(S)}}. \end{align}\] We now use the elementary inequality \[\begin{align} (m)_s\ge \left(\frac{m}{e}\right)^s \quad\forall\;m\ge 1,\;0\leq s\leq m. \end{align}\] Applying this with \(m=n-\tau\) and \(s=s(S)\) yields \[\begin{align} (n-\tau)_{s(S)}\ge \left(\frac{n-\tau}{e}\right)^{s(S)}. \end{align}\] Therefore \[\begin{align} p_A(S) \le \prod_{v\in V^+(S)} \frac{e |\mathcal{W}({\cal R}_v(S))|}{n-\tau}.\label{eq:pA95sq95bound95cover} \end{align}\tag{14}\] Thus, if we set \(c_q\triangleq q^{-1}-1\), then using 13 and 14 , we get \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) \le \sum_{S\subseteq \mathcal{E}_A} c_q^{|S|} \prod_{v\in V^+(S)} \frac{e^2|\mathcal{W}({\cal R}_v(S))|^2}{(n-\tau)^2}.\label{eq:pA95sq95bound95covertt} \end{align}\tag{15}\] Let us simplify the upper bound at the right-hand side of 15 . Observe that a set \(S\subseteq \mathcal{E}_A\) is uniquely determined by the local choices \[\begin{align} {\cal R}_v(S)&\subseteq N_A(v),\\ N_A(v)&\triangleq \{u\in U:\{a_u,v\}\in \mathbb{Q}\}, \end{align}\] for any \(v\in {\cal B}_A\). Also, notice that \[\begin{align} |S|=\sum_{v\in {\cal B}_A} |{\cal R}_v(S)|. \end{align}\] Therefore the sum over \(S\) factorizes into a product over \(v\in {\cal B}_A\) as follows \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) \le\prod_{v\in {\cal B}_A} \left( 1+ \frac{e^2}{(n-\tau)^2} \sum_{\emptyset\neq R\subseteq N_A(v)} c_q^{|R|} |\mathcal{W}(R)|^2 \right). \end{align}\] For convenience, let us extend the previous definition and set \[\begin{align} N_A(i)\triangleq \{u\in U:\{a_u,i\}\in \mathbb{Q}\}, \qquad i\in[n]. \end{align}\] Then \(N_A(i)=\emptyset\) whenever \(i\notin {\cal B}_A\cup A\), and in particular \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) &\le \prod_{i=1}^{n} \left( 1+ \frac{e^2}{(n-\tau)^2} \sum_{\emptyset\neq R\subseteq N_A(i)} c_q^{|R|} |\mathcal{W}(R)|^2 \right) \nonumber\\ &\le \exp\left[ \frac{e^2}{(n-\tau)^2} \sum_{i=1}^{n} \sum_{\emptyset\neq R\subseteq N_A(i)} c_q^{|R|} |\mathcal{W}(R)|^2 \right], \label{eq:chi295bound95exponential95weighted} \end{align}\tag{16}\] where in the last inequality we used \(1+x\le e^x\) for all \(x\ge 0\). Define \[\begin{align} Z_{A_n} \triangleq \sum_{i=1}^{n} \sum_{\emptyset\neq R\subseteq N_{A_n}(i)} c_q^{|R|} |\mathcal{W}_n(R)|^2. \label{eq:ZA95weighted95cover} \end{align}\tag{17}\] Then 16 yields \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A_n,\mathbb{Q}},\mathbb{P}^H_{A_n,\mathbb{Q}}\right) \le \exp\left[\eta_n Z_{A_n}\right], \label{eq:eta95cover95reduction0} \end{align}\tag{18}\] where \[\begin{align} \eta_n\triangleq \frac{e^2}{(n-\tau_n)^2}. \label{eq:eta95cover95reduction} \end{align}\tag{19}\]

Next, we analyze \(Z_{A_n}\). Taking expectations in 17 and using Fubini’s theorem, \[\begin{align} \mathbb{E}[Z_{A_n}] &= \sum_{i=1}^{n} \sum_{\emptyset\neq R\subseteq U_n} c_q^{|R|} |\mathcal{W}_n(R)|^2 \mathbb{P}\left[R\subseteq N_{A_n}(i)\right]. \label{eq:EZ95expand95cover} \end{align}\tag{20}\] Fix \(i\in[n]\) and a nonempty set \(R\subseteq U_n\) with \(|R|=r\). Since the ordered tuple \((a_u)_{u\in R}\) is uniformly distributed over all ordered \(r\)-tuples of distinct vertices of \([n]\), and since \(N_{\mathbb{Q}_n}(i)\) has cardinality \(t_i^{(n)}\), we have \[\begin{align} \mathbb{P}\left[R\subseteq N_{A_n}(i)\right] = \frac{(t_i^{(n)})_r}{(n)_r}. \label{eq:prob95R95in95NAi} \end{align}\tag{21}\] Substituting 21 into 20 , grouping terms according to \(r=|R|\), and using the definition of \(\zeta_{r,n}\) in 5 , we obtain \[\begin{align} \mathbb{E}[Z_{A_n}] &= \sum_{r=1}^{\tau_n} c_q^r \left( \sum_{\substack{R\subseteq U_n\\ |R|=r}} |\mathcal{W}_n(R)|^2 \right) \left( \sum_{i=1}^{n}\frac{(t_i^{(n)})_r}{(n)_r} \right) \nonumber\\ &= \sum_{r=1}^{\tau_n} c_q^r\Theta_{r,n}\zeta_{r,n}. \label{eq:EZ95cover95exact} \end{align}\tag{22}\]

Define \[\begin{align} \Lambda_n \triangleq \eta_n \mathbb{E}[Z_{A_n}] = \frac{e^2}{(n-\tau_n)^2} \sum_{r=1}^{\tau_n} c_q^r\Theta_{r,n}\zeta_{r,n}. \label{eq:Lambda95n95cover} \end{align}\tag{23}\] By assumption [eq:assump95remainder95negligible], we have \(\Lambda_n\to 0\). Now define \[\begin{align} T_n\triangleq \sqrt{\frac{\mathbb{E}[Z_{A_n}]}{\eta_n}} \qquad\text{and}\qquad {\cal G}_n\triangleq \{Z_{A_n}\le T_n\}. \end{align}\] By Markov’s inequality, \[\begin{align} \mathbb{P}({\cal G}_n^c) &= \mathbb{P}(Z_{A_n}>T_n)\\ &\le \frac{\mathbb{E}[Z_{A_n}]}{T_n}\\ &= \sqrt{\eta_n \mathbb{E}[Z_{A_n}]} = \sqrt{\Lambda_n}. \end{align}\] Hence, by 23 , \[\begin{align} \mathbb{P}({\cal G}_n^c)\to 0. \label{eq:bad95event95small95cover} \end{align}\tag{24}\]

On the good event \({\cal G}_n\), we have \(Z_{A_n}\le T_n\), and so 18 implies that \[\begin{align} 1+\chi^2\left(\mathbb{P}^\Gamma_{A_n,\mathbb{Q}},\mathbb{P}^H_{A_n,\mathbb{Q}}\right) \le e^{\eta_n T_n}. \end{align}\] But \[\begin{align} \eta_n T_n = \eta_n\sqrt{\frac{\mathbb{E}[Z_{A_n}]}{\eta_n}} = \sqrt{\eta_n \mathbb{E}[Z_{A_n}]} = \sqrt{\Lambda_n} \to 0. \end{align}\] Hence \[\begin{align} \sup_{A\in {\cal G}_n} \chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) \to 0. \end{align}\] Therefore, uniformly over \(A\in {\cal G}_n\), \[\begin{align} d_{\mathsf{TV}}(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}) \le \frac{1}{2} \sqrt{ \chi^2\left(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}\right) } \to 0.\label{eqn:unifTota} \end{align}\tag{25}\] We now split the laws according to the event \({\cal G}_n\). Define the good-event conditional mixtures \[\begin{align} \mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(g)} &\triangleq \mathbb{E}\left[\mathbb{P}^\Gamma_{A_n,\mathbb{Q}}\vert {\cal G}_n\right], \\ \mathbb{P}_{H_n,\mathbb{Q}}^{(g)} &\triangleq \mathbb{E}\left[\mathbb{P}^H_{A_n,\mathbb{Q}}\vert {\cal G}_n\right], \end{align}\] and similarly define the bad-event conditional mixtures \(\mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(b)}\) and \(\mathbb{P}_{H_n,\mathbb{Q}}^{(b)}\). Then \[\begin{align} \mathbb{P}_{{\cal H}_1,\mathbb{Q}} &= (1-p)\cdot\mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(g)} + p\cdot \mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(b)},\\ \mathbb{P}_{H_n,\mathbb{Q}} &= (1-p)\cdot\mathbb{P}_{H_n,\mathbb{Q}}^{(g)} + p\cdot \mathbb{P}_{H_n,\mathbb{Q}}^{(b)}, \end{align}\] where \(p\triangleq \mathbb{P}({\cal G}_n^c)\). By convexity of the total variation distance, \[\begin{align} d_{\mathrm{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}},\mathbb{P}_{H_n,\mathbb{Q}}) &\le (1-p) d_{\mathrm{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(g)},\mathbb{P}_{H_n,\mathbb{Q}}^{(g)}) + p d_{\mathrm{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(b)},\mathbb{P}_{H_n,\mathbb{Q}}^{(b)}) \nonumber\\ &\le d_{\mathrm{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}}^{(g)},\mathbb{P}_{H_n,\mathbb{Q}}^{(g)}) + p\\ &\leq \mathbb{P}({\cal G}_n^c) + \sup_{A\in {\cal G}_n} d_{\mathsf{TV}}(\mathbb{P}^\Gamma_{A,\mathbb{Q}},\mathbb{P}^H_{A,\mathbb{Q}}). \label{eq:tv95split95case2} \end{align}\tag{26}\] The first term tends to zero by 24 , and the second term tends to zero by the uniform bound 25 . Hence \(d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{H_n,\mathbb{Q}_n})\to 0\), which proves 11 . Combining this with [eq:assump95core95undetectable] yields \(d_{\mathsf{TV}}(\mathbb{P}_{{\cal H}_1,\mathbb{Q}_n},\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n})\to 0\).

5 Proofs of upper bounds↩︎

5.1 Query scan test↩︎

Recall that \(H\) is any fixed graph with no isolated vertices. Write \(v_H\triangleq |v(H)|\) and \(e_H\triangleq |e(H)|\). We will use \(H\) as a witness pattern that is guaranteed to appear inside the planted \(\Gamma_n\), i.e., \(H\subseteq \Gamma_n\) as an unlabeled subgraph.

Let us upper bound the \(\mathsf{Type}\)-\(\mathsf{I}\) and \(\mathsf{Type}\)-\(\mathsf{II}\) error probabilities, starting with the former. Under \({\cal H}_0\), the induced queried graph satisfies \(\mathsf{G}_S\sim {\cal G}(M,q)\). For any fixed injective map \(\varphi:v(H)\hookrightarrow S\), the event that \(\varphi\) embeds \(H\) as a subgraph of \(\mathsf{G}_S\) requires that all \(e\) edges of \(H\) are present among the corresponding \(e\) queried pairs; since edges are independent \(\mathsf{Bern}(q)\) under \({\cal H}_0\), \[\begin{align} \mathbb{P}_{{\cal H}_0}\left(\text{\varphi embeds H into \mathsf{G}_S}\right)=q^{e_H}. \label{eq:embed95prob95null} \end{align}\tag{27}\] The number of injective maps \(\varphi:v(H)\hookrightarrow S\) is exactly \(|{\cal S}_{H}| = \binom{M}{v_H}\frac{v_H!}{|\mathsf{Aut}(H)|}\leq(M)_v\). Applying the union bound over all injective maps gives \[\begin{align} \mathbb{P}_{{\cal H}_0}({\cal A}_{\mathsf{scan}}(\mathsf{G})=1)\leq |{\cal S}_{H}|\cdot q^{e_H}.\label{eqn:TypeIbound} \end{align}\tag{28}\]

Next, we bound the \(\mathsf{Type}\)-\(\mathsf{II}\) error probability. Under \({\cal H}_1\), the planted copy of \(\Gamma_n\) is obtained by a uniformly random injective embedding \(\Phi:v(\Gamma_n)\hookrightarrow[n]\) and then all planted edges appear. Let \({\cal C}\) denote the set of (unlabeled) copies of \(H\) in \(\Gamma_n\). For each \(c\in{\cal C}\), let \(W_c\subseteq v(\Gamma_n)\) be the vertex set of that copy; thus \(|W_c|=v\). Define the random \(v\)-subset of \([n]\) \[\begin{align} B_c \triangleq \Phi(W_c)\subseteq[n]. \end{align}\] Define indicators and the planted-hit count \[\begin{align} I_c \triangleq \mathbb{1}\{B_c\subseteq S\},\qquad Z_H \triangleq \sum_{c\in{\cal C}} I_c. \end{align}\] Note that if \(Z_H\ge 1\), then at least one planted copy of \(H\) lies entirely in \(S\), and since \(p=1\), all edges of that copy are present; hence the scan in Algorithm 2 must output \(1\). Therefore, \[\begin{align} \mathbb{P}_{{\cal H}_1}({\cal A}_{\mathsf{scan}}=0)\leq\mathbb{P}_{{\cal H}_1}(Z_H=0). \label{eq:miss95le95Z0} \end{align}\tag{29}\] Recall that \(N(H,\Gamma_n)\triangleq |{\cal C}|\) is the number of copies of \(H\) in \(\Gamma_n\). Since \(\Phi\) is uniform and \(S\) is a uniform \(M\)-subset, for every fixed \(c\in{\cal C}\), \[\begin{align} \mathbb{E}[I_c] =\mathbb{P}(B_c\subseteq S) =\frac{(M)_v}{(n)_v}.\label{eq:alpha} \end{align}\tag{30}\] Hence, \[\begin{align} \mu\triangleq\mathbb{E}[Z_H] = \sum_{c\in{\cal C}} \mathbb{E}[I_c] = N(H,\Gamma_n) \frac{(M)_v}{(n)_v}. \label{eq:mu95def} \end{align}\tag{31}\] To quantify overlaps, write \(c\sim c'\) if \(c\neq c'\) and \(W_c\cap W_{c'}\neq\emptyset\). Define \[\begin{align} \Delta\triangleq\sum_{\substack{c,c'\in{\cal C}\\ c\sim c'}} \mathbb{E}[I_c I_{c'}] = \sum_{\substack{c,c'\in{\cal C}\\ c\sim c'}} \mathbb{P}(B_c\cup B_{c'} \subseteq S). \label{eq:Delta95def} \end{align}\tag{32}\] If \(|W_c\cap W_{c'}|=t\) then \(|B_c\cup B_{c'}|=2v-t\), and therefore \[\begin{align} \mathbb{E}[I_c I_{c'}] =\frac{(M)_{2v-t}}{(n)_{2v-t}}. \label{eq:pair95prob} \end{align}\tag{33}\] Let \(N_t(H,\Gamma_n)\) denote the number of ordered pairs \((c,c')\in{\cal C}^2\) with \(c\neq c'\) and \(|W_c\cap W_{c'}|=t\). Then by grouping terms in 32 using 33 , \[\begin{align} \Delta=\sum_{t=1}^{v-1} N_t(H,\Gamma_n) \frac{(M)_{2v-t}}{(n)_{2v-t}}. \label{eq:Delta95t} \end{align}\tag{34}\]

We will use the following standard “Janson-type” inequality for the hypergeometric model (uniform fixed-size subset), proved via the exponential moment method together with negative dependence of sampling without replacement. For completeness, we give a self-contained derivation in Appendix 7.1.

Condition on the embedding \(\Phi\). Then the family \(\{B_c\}_{c\in{\cal C}}\) is deterministic, and Lemma 2 applies to \(Z_H\): \[\begin{align} \mathbb{P}_{{\cal H}_1}(Z_H=0\vert \Phi) \leq \exp\left(-\frac{\mu(\Phi)^2}{\mu(\Phi)+\Delta(\Phi)}\right). \label{eq:janson95cond} \end{align}\tag{35}\] However, by symmetry \(\mu(\Phi)\) is constant (equal to 31 ), and likewise \(\Delta(\Phi)\) is constant (equal to 32 –34 ); therefore the bound is uniform in \(\Phi\) and we may drop conditioning. Thus, combining 29 with the above yields \[\begin{align} \mathbb{P}_{{\cal H}_1}({\cal A}_{\mathsf{scan}}=0)\leq\exp\left(-\frac{\mu^2}{\mu+\Delta}\right). \label{eq:typeII95janson} \end{align}\tag{36}\] Using 28 and 36 we finally get that \[\begin{align} \mathsf{R}_n({\cal A}_{\mathsf{scan}}) \leq |{\cal S}_{H}|\cdot q^{e_H}+\exp\left(-\frac{\mu^2}{\mu+\Delta}\right).\label{eqn:RiskScanTest} \end{align}\tag{37}\] Therefore, if \(|{\cal S}_{H}| q^{e_H}\to0\), \(\mu\to\infty\), and \(\Delta=o(\mu^2)\), then \(\mathsf{R}_n({\cal A}_{\mathsf{scan}})\to0\), as \(n\to\infty\).

5.2 Degree on a cut↩︎

Let us upper bound the \(\mathsf{Type}\)-\(\mathsf{I}\) and \(\mathsf{Type}\)-\(\mathsf{II}\) error probabilities, starting with the former. Under \({\cal H}_0\), all queried edges are independent \(\mathsf{Bern}(q)\). Fix \(u\in U\). Then \[\begin{align} D(u)\sim \mathsf{Binomial}(m,q),\quad \mathbb{E}_{{\cal H}_0}[D(u)]=qm. \end{align}\] Let \[\begin{align} t \triangleq \frac{1-q}{8}\cdot d\cdot \frac{m}{n}, \qquad\text{so that}\qquad T=qm+t. \end{align}\] Applying Lemma 4 gives \[\begin{align} \mathbb{P}_{{\cal H}_0}(D(u)\ge T) \leq \exp\left(-\frac{t^2}{2(qm+t/3)}\right). \end{align}\] Since \(d\leq n\) we have \(t\leq \frac{1-q}{8}m\leq m/8\), hence \(qm+t/3\leq (q+1/24)m\leq 2m\) for all large \(n\). Therefore \[\begin{align} \mathbb{P}_{{\cal H}_0}(D(u)\ge T) \leq \exp\left(-c_0\frac{t^2}{m}\right) = \exp\left(-c_1\frac{d^2 m}{n^2}\right), \label{eq:typeI95pointwise95degcut} \end{align}\tag{38}\] for constants \(c_0,c_1>0\) depending only on \(q\). Using \(m=\lceil C_1(n^2/d^2)\log n\rceil\) we obtain \[\begin{align} \frac{d^2 m}{n^2}\geq C_1\log n, \end{align}\] hence for \(C_1\) sufficiently large, \[\begin{align} \mathbb{P}_{{\cal H}_0}(D(u)\ge T)\leq n^{-5}. \end{align}\] A union bound over \(u\in U\) yields \[\begin{align} \mathbb{P}_{{\cal H}_0}\left(\max_{u\in U}D(u)\geq T\right)\leq M\cdot n^{-5}\leq n^{-3},\label{eqn:cutTypeI} \end{align}\tag{39}\] for all large \(n\), since \(M\leq n^{O(1)}\) by ?? . Thus the \(\mathsf{Type}\)-\(\mathsf{I}\) error probability is at most \(n^{-3}\).

Next, we bound the \(\mathsf{Type}\)-\(\mathsf{II}\) error probability. To this end, we need to establish a few results. First, we prove a high probability lower bound on the number of planted vertices that fall into the set \(S\). Specifically, under \({\cal H}_1\), let \(K\subset[n]\) denote the planted vertex set, \(|K|=k_n\). Let \[\begin{align} N\triangleq |S\cap K|. \end{align}\] Since \(S\) is a uniform \(m\)-subset of \([n]\), \[\begin{align} N\sim \mathsf{Hypergeometric}(n,k_n,m),\quad \mathbb{E}[N]=\frac{k_n m}{n}. \end{align}\] By Lemma 5 with \(\delta=1/2\), \[\begin{align} \mathbb{P}_{{\cal H}_1}\left(N\leq\frac{k_n m}{2n}\right) \leq \exp\left(-\frac{1}{8}\cdot \frac{k_n m}{n}\right) \leq \exp\left(-\frac{10}{8}\log n\right)\leq n^{-1}, \end{align}\] using ?? . Hence with probability at least \(1-n^{-1}\), \[\begin{align} N=|S\cap K|\geq \frac{k_n m}{2n}. \label{eq:N95good95degcut} \end{align}\tag{40}\]

Next, we prove that at least one high-degree planted vertex falls into \(U\). Let \(A_d\subseteq v(\Gamma_n)\) be the set of vertices of \(\Gamma_n\) with degree at least \(d\); by definition \(|A_d|=m_d(\Gamma_n)\). Under the random embedding of \(\Gamma_n\) into \([n]\), the images of \(A_d\) form a subset \(K_{\ge d}\subseteq K\) with \(|K_{\ge d}|=m_d(\Gamma_n)\). Because \(U\) is a uniform \(M\)-subset of \([n]\setminus S\), the random variable \[\begin{align} W\triangleq |U\cap K_{\ge d}| \end{align}\] is hypergeometric with mean \[\begin{align} \mathbb{E}[W] = M\cdot \frac{|K_{\ge d}|}{n-m}. \end{align}\] Using \(m\leq n/2\) from ?? gives \(n-m\ge n/2\) and hence \[\begin{align} \mathbb{E}[W]\geq M\cdot \frac{m_d(\Gamma_n)}{n}. \end{align}\] With \(M=\lceil C_2(n/m_d)\log n\rceil\) this implies \(\mathbb{E}[W]\ge C_2\log n\) for all large \(n\). Applying Lemma 5 to \(W\) with \(\delta=1/2\) yields \[\begin{align} \mathbb{P}_{{\cal H}_1}(W=0) \leq \mathbb{P}_{{\cal H}_1}\left(W\leq \frac{1}{2}\mathbb{E}[W]\right) \leq \exp\left(-\frac{1}{8}\mathbb{E}[W]\right) \leq n^{-2}, \end{align}\] for \(C_2\) sufficiently large. Therefore, with probability at least \(1-n^{-2}\) there exists \(u^\star\in U\cap K_{\ge d}\).

Next, we would like to count the number of planted neighbors of \(u^\star\) inside \(S\). We condition on the (as shown above) high probable event that \(u^\star\in U\cap K_{\ge d}\) exists and that 40 holds. Let \(x\in v(\Gamma_n)\) be the preimage of \(u^\star\); then \(\deg_{\Gamma_n}(x)\ge d\). Now, let \(Z\) be the number of planted vertices in \(S\) that are neighbors of \(u^\star\) in the planted copy. Condition on \(N=|S\cap K|\) and on \(u^\star\in K\). Then \(S\cap K\) is a uniform \(N\)-subset of \(K\), so \[\begin{align} Z\vert N\sim \mathsf{Hypergeometric}(k_n-1,\deg_{\Gamma_n}(x),N), \quad \mathbb{E}[Z\vert N]=\deg_{\Gamma_n}(x)\cdot \frac{N}{k_n-1}. \end{align}\] Using \(\deg_{\Gamma_n}(x)\ge d\) and \(k_n-1\leq k_n\) gives \[\begin{align} \mathbb{E}[Z\vert N]\geq \frac{dN}{k_n}. \end{align}\] Combining with 40 , \[\begin{align} \mathbb{E}[Z\vert N]\geq\frac{dm}{2n}. \label{eq:EZ95lower95degcut} \end{align}\tag{41}\] Applying Lemma 5 to \(Z\) conditional on \(N\) with \(\delta=1/2\) yields \[\begin{align} \mathbb{P}_{{\cal H}_1}\left(\left.Z\leq \frac{dm}{4n}\right|N\right) \leq \exp\left(-\frac{1}{8}\mathbb{E}[Z\vert N]\right) \leq \exp\left(-c_2 d\frac{m}{n}\right). \end{align}\] Because \(m\asymp (n^2/d^2)\log n\) we have \(d\frac{m}{n}\to\infty\). Therefore, with probability at least \(1-n^{-2}\) on the good events, \[\begin{align} Z\geq \frac{dm}{4n}. \label{eq:Z95good95degcut} \end{align}\tag{42}\]

We are now in a position to bound the \(\mathsf{Type}\)-\(\mathsf{II}\) error probability. On the event 42 , among the \(m\) queried edges from \(u^\star\) to \(S\), exactly \(Z\) are planted edges and hence present with probability \(1\), and the remaining \(m-Z\) are non-planted edges present with probability \(q\) independently. Thus conditional on \(Z\), \[\begin{align} D(u^\star)= Z + \widetilde{X}, \end{align}\] where \(\widetilde{X}\sim \mathsf{Binomial}(m-Z,q)\), and is independent of \(Z\). Hence \[\begin{align} \mathbb{E}[D(u^\star)\vert Z] = Z + q(m-Z)=qm + (1-q)Z. \end{align}\] Using 42 yields \[\begin{align} \mathbb{E}[D(u^\star)\vert Z]\geq qm + (1-q)\cdot \frac{dm}{4n}. \end{align}\] Since our threshold is \(T=qm+(1-q)\frac{dm}{8n}\), we have a margin of size \[\begin{align} \mathbb{E}[D(u^\star)\vert Z]-T\geq \frac{1-q}{8}\frac{dm}{n}. \end{align}\] Now, \[\begin{align} D(u^\star)<T \;\Rightarrow\;\widetilde{X}<q(m-Z)-\frac{1-q}{8}\frac{dm}{n}. \end{align}\] Using the facts that \((m-Z)\leq m\) and \(Z\ge \frac{1}{4} d(m/n)\), by applying Bernstein’s inequality to the lower tail of \(\widetilde{X}\), we obtain \[\begin{align} \mathbb{P}_{{\cal H}_1}(D(u^\star)<T\vert Z) \leq \exp\left(-c_3\frac{\left(d\frac{m}{n}\right)^2}{m}\right) = \exp\left(-c_4 \frac{d^2 m}{n^2}\right), \end{align}\] for constants \(c_3,c_4>0\) depending only on \(q\). Using \(m=\lceil C_1(n^2/d^2)\log n\rceil\) gives \(\frac{d^2 m}{n^2}\ge C_1\log n\), hence for \(C_1\) large, \[\begin{align} \mathbb{P}_{{\cal H}_1}(D(u^\star)<T\vert Z)\leq n^{-3}. \end{align}\] Taking a union bound over the complements of the good events, and this conditional tail bound, yields \[\begin{align} \mathbb{P}_{{\cal H}_1}\left[\max_{u\in U}D(u)<T\right] \leq n^{-1}+n^{-2}+n^{-2}+n^{-3}= O(n^{-1}).\label{eqn:cutTypeII} \end{align}\tag{43}\] Thus the \(\mathsf{Type}\)-\(\mathsf{II}\) error probability is at most \(n^{-1}\).

Combining 39 and 43 , we get \[\begin{align} \mathsf{R}_n({\cal A}_{\mathsf{cut}})= O(n^{-1}), \end{align}\] for all sufficiently large \(n\). Finally, we analyze the resulted query complexity. The algorithm makes exactly \(Q_{\mathsf{cut}}=Mm\) queries. Using ?? , \[\begin{align} Q_{\mathsf{cut}}\leq C\cdot \frac{n}{m_d(\Gamma_n)}\log n\cdot \frac{n^2}{d^2}\log n = C\cdot \frac{n^3}{m_d(\Gamma_n)d^2}\log^2 n, \end{align}\] for a constant \(C=C(q)>0\). Hence any budget \(Q\) satisfying \(\mathsf{Q}_n\ge \mathsf{Q}_{\mathsf{cut}}\) can run \({\cal A}_{\mathsf{cut}}\) within budget. Optimizing over \(d\) yields \(Q\geq C\frac{n^3}{\kappa(\Gamma_n)}\log^2 n\) as claimed.

5.3 Count test↩︎

Let us upper bound the \(\mathsf{Type}\)-\(\mathsf{I}\) and \(\mathsf{Type}\)-\(\mathsf{II}\) error probabilities, starting with the former. Let \(\mathbb{Q}_n\subseteq \binom{[n]}{2}\) be sampled uniformly at random among all subsets of cardinality \(\mathsf{Q}_n\), independently of the graph, and define \[\begin{align} \mathsf{X}_{\mathsf{count}} \triangleq \sum_{e\in \mathbb{Q}_n}\mathbb{1}\{e\in e(\mathsf{G})\}. \end{align}\] For a sequence \(\lambda_n\to\infty\), consider the test \[\begin{align} {\cal A}_{\mathsf{count}} \triangleq \mathbb{1}\left\{ \mathsf{X}_{\mathsf{count}} \ge q\mathsf{Q}_n+\lambda_n\sqrt{q(1-q)\mathsf{Q}_n} \right\}. \end{align}\] Under \({\cal H}_0\), conditional on \(\mathbb{Q}_n\), the queried edge indicators are i.i.d. \(\mathsf{Bern}(q)\). Hence \(\mathsf{X}_{\mathsf{count}}\mid \mathbb{Q}_n\sim \mathsf{Binomial}(\mathsf{Q}_n,q)\). Therefore, by Bernstein’s inequality, \[\begin{align} \mathbb{P}_{{\cal H}_0}\left({\cal A}_{\mathsf{count}}=1\vert \mathbb{Q}_n\right) &= \mathbb{P}_{{\cal H}_0}\left[\left. \mathsf{X}_{\mathsf{count}} \ge q\mathsf{Q}_n+\lambda_n\sqrt{q(1-q)\mathsf{Q}_n} \right| \mathbb{Q}_n\right] \le \exp\left(-c_q\lambda_n^2\right). \end{align}\] Taking expectation over \(\mathbb{Q}_n\), we obtain \[\begin{align} \mathbb{P}_{{\cal H}_0}\left({\cal A}_{\mathsf{count}}=1\right) \le \exp\left(-c_q\lambda_n^2\right) =o(1). \end{align}\]

We now bound the \(\mathsf{Type}\)-\(\mathsf{II}\) error. Let \(\Gamma_n^\star\) denote the planted copy of \(\Gamma_n\), and write \[\begin{align} Z_n \triangleq |e(\Gamma_n^\star)\cap \mathbb{Q}_n| \end{align}\] for the number of planted edges queried by the algorithm. Conditional on \(\Gamma_n^\star\) and \(\mathbb{Q}_n\), the variable \(\mathsf{X}_{\mathsf{count}}\) is a sum of independent Bernoulli random variables, with parameter \(p\) on the \(Z_n\) planted queried edges and parameter \(q\) on the remaining \(\mathsf{Q}_n-Z_n\) queried edges. Hence \[\begin{align} \mathbb{E}_{{\cal H}_1}\left[\mathsf{X}_{\mathsf{count}}\vert \Gamma_n^\star,\mathbb{Q}_n\right] &= q\mathsf{Q}_n+(p-q)Z_n,\quad \mathsf{Var}_{{\cal H}_1}\left[\mathsf{X}_{\mathsf{count}}\vert \Gamma_n^\star,\mathbb{Q}_n\right] \le \mathsf{Q}_n. \end{align}\] Let \(T_n \triangleq q\mathsf{Q}_n+\lambda_n\sqrt{q(1-q)\mathsf{Q}_n}\). On the event \[\begin{align} \mathcal{G}_n \triangleq \left\{ (p-q)Z_n \ge 2\lambda_n\sqrt{q(1-q)\mathsf{Q}_n} \right\}, \end{align}\] we have \[\begin{align} \mathbb{E}_{{\cal H}_1}\left[\mathsf{X}_{\mathsf{count}}\vert \Gamma_n^\star,\mathbb{Q}_n\right] -T_n \ge \frac{1}{2}(p-q)Z_n. \end{align}\] Therefore, conditional on \(\Gamma_n^\star\) and \(\mathbb{Q}_n\), Bernstein’s inequality gives \[\begin{align} \mathbb{P}_{{\cal H}_1}\left( \mathsf{X}_{\mathsf{count}}<T_n \vert \Gamma_n^\star,\mathbb{Q}_n\right) &\le \exp\left( -c\frac{(p-q)^2Z_n^2}{\mathsf{Q}_n} \right) \; \mathsf{on}\; \mathcal{G}_n, \end{align}\] where \(c>0\) is an absolute constant. Consequently, \[\begin{align} \mathbb{P}_{{\cal H}_1}\left({\cal A}_{\mathsf{count}}=0\right) \le \mathbb{E}\left[ \exp\left( -c\frac{(p-q)^2Z_n^2}{\mathsf{Q}_n} \right) \mathbb{1}_{\mathcal{G}_n} \right] + \mathbb{P}(\mathcal{G}_n^c). \label{eq:count95typeII95split} \end{align}\tag{44}\]

It remains to show that the right-hand side is \(o(1)\). Conditional on \(\Gamma_n^\star\), since \(\mathbb{Q}_n\) is a uniform \(\mathsf{Q}_n\)-subset of \(\binom{[n]}{2}\), the random variable \(Z_n\) has a hypergeometric distribution, i.e., \[\begin{align} Z_n\vert \Gamma_n^\star \sim \mathsf{Hypergeometric}\left( \binom n2,|e(\Gamma_n)|,\mathsf{Q}_n \right). \end{align}\] In particular, \[\begin{align} \mathbb{E}[Z_n\vert \Gamma_n^\star] =\mathsf{Q}_n\frac{|e(\Gamma_n)|}{\binom n2} \triangleq \alpha_n. \end{align}\] By the Chernoff bound for hypergeometric random variables, \[\begin{align} \mathbb{P}\left(\left. Z_n\le \frac{\alpha_n}{2} \right| \Gamma_n^\star \right) \le \exp\left(-c\alpha_n\right). \end{align}\] Thus \[\begin{align} \mathbb{P}\left( Z_n\le \frac{\alpha_n}{2} \right) \le \exp\left(-c\alpha_n\right). \label{eq:count95Z95concentration} \end{align}\tag{45}\] Assume now that \[\begin{align} \frac{(p-q)^2}{q(1-q)} \cdot \mathsf{Q}_n \left(\frac{|e(\Gamma_n)|}{\binom n2}\right)^2 \to \infty. \label{eq:edgecount95snr95clean} \end{align}\tag{46}\] Equivalently, \[\begin{align} (p-q)\alpha_n \gg \sqrt{q(1-q)\mathsf{Q}_n}. \end{align}\] Choose \(\lambda_n\to\infty\) sufficiently slowly so that \[\begin{align} (p-q)\alpha_n \gg \lambda_n\sqrt{q(1-q)\mathsf{Q}_n}. \label{eq:lambda95slow95count} \end{align}\tag{47}\] Then, on the event \(Z_n\ge \alpha_n/2\), condition 47 implies \(\mathcal{G}_n\) for all sufficiently large \(n\). Hence, by 45 , \[\begin{align} \mathbb{P}(\mathcal{G}_n^c) \le \mathbb{P}\left(Z_n<\frac{\alpha_n}{2}\right) =o(1). \end{align}\] Moreover, on the same event, \[\begin{align} \frac{(p-q)^2Z_n^2}{\mathsf{Q}_n} \ge \frac{(p-q)^2\alpha_n^2}{4\mathsf{Q}_n} \frac{1}{4} (p-q)^2\mathsf{Q}_n \left(\frac{|e(\Gamma_n)|}{\binom n2}\right)^2 \to \infty \end{align}\] by 46 . Therefore the expectation term in 44 also tends to zero. We conclude that \[\begin{align} \mathbb{P}_{{\cal H}_1}\left({\cal A}_{\mathsf{count}}=0\right)=o(1). \end{align}\] Combining the \(\mathsf{Type}\)-\(\mathsf{I}\) and \(\mathsf{Type}\)-\(\mathsf{II}\) bounds yields \[\begin{align} \mathsf{R}_n({\cal A}_{\mathsf{count}};\mathbb{Q}_n)\to 0. \end{align}\]

6 Corollaries↩︎

In this section we derive several corollaries from the general lower bounds derived in the previous subsections, by specializing to specific families of subgraphs, starting with subgraphs with a bounded vertex cover number.

6.1 Proof of Corollary 1↩︎

The proof of Corollary 1 follows from the observation below.

By Lemma 3, \[\begin{align} \sum_{r=1}^{\tau_n}(q^{-1}-1)^r\Theta_{r,n}\zeta_{r,n} \le \frac{2\mathsf{Q}_n}{n} \sum_{r=1}^{\tau_n}(q^{-1}-1)^r\Theta_{r,n}. \end{align}\] Hence ?? implies condition [eq:assump95remainder95negligible] in Theorem [thm:cover95reduction95query95lb]. The conclusion now follows directly from Theorem [thm:cover95reduction95query95lb].

6.2 Proof of Corollary 2↩︎

To prove Corollary 2, it is convenient to first establish the following impossibility result for star forests.

We are now ready to establish the lower bound in Proposition 2 for pendant-leaf graphs; we restate it here for convenience.

The rest of Corollary 2 follows from the following result.

6.3 Proof of Corollary 3↩︎

Write the path vertices as \(1,2,\ldots,k_n\) in their natural order, and choose \[\begin{align} U_n\triangleq \{2,4,6,\ldots\}\cap [k_n]. \end{align}\] Then \(U_n\) is a vertex cover, \(W_n=V_n\setminus U_n\) is independent, and the induced graph \(H_n=\Gamma_n[U_n]\) is edgeless. Therefore \[\begin{align} \mathbb{P}_{H_n,\mathbb{Q}_n}=\mathbb{P}_{{\cal H}_0,\mathbb{Q}_n}, \end{align}\] so the core-undetectability condition is automatic.

Next, we bound \(\Theta_{r,n}\). Every vertex \(w\in W_n\) has at most two neighbors in \(U_n\), hence \[\begin{align} \Theta_{r,n}=0,\qquad r\ge 3. \end{align}\] Also, for each \(u\in U_n\), the set \(\mathcal{W}_n(\{u\})\) contains at most the two path-neighbors of \(u\), so \[\begin{align} |\mathcal{W}_n(\{u\})|\le 2. \end{align}\] Therefore \[\begin{align} \Theta_{1,n} = \sum_{u\in U_n} |\mathcal{W}_n(\{u\})|^2 \le 4|U_n| \le 2k_n. \label{eq:path95theta1} \end{align}\tag{48}\] Similarly, if \(R\subseteq U_n\) has cardinality \(2\), then \(\mathcal{W}_n(R)\) contains at most one vertex, namely the unique odd-indexed vertex whose two neighbors are the two vertices of \(R\), if such a vertex exists. Hence \[\begin{align} |\mathcal{W}_n(R)|\le 1 \qquad\forall R\subseteq U_n,\;|R|=2, \end{align}\] and the number of such relevant pairs is at most \(|W_n|\). Thus \[\begin{align} \Theta_{2,n}\le |W_n|\le k_n. \label{eq:path95theta2} \end{align}\tag{49}\] Combining 48 and 49 , and using Corollary 1, it is enough to check that \[\begin{align} \frac{\mathsf{Q}_n}{n(n-\tau_n)^2} \Bigl((q^{-1}-1)\Theta_{1,n}+(q^{-1}-1)^2\Theta_{2,n}\Bigr)\to 0. \end{align}\] Since \(\tau_n\le k_n/2\le n/2\) for all sufficiently large \(n\), we have \(n-\tau_n\asymp n\). Using 48 and 49 , the left-hand side is \[\begin{align} O_q\left(\frac{\mathsf{Q}_n k_n}{n^3}\right), \end{align}\] which tends to \(0\) whenever \(\frac{\mathsf{Q}_n k_n}{n^3}\to 0\). This proves the first claim. Finally, if \(\mathsf{Q}_n=\binom n2\), then \(\mathsf{Q}_n\asymp n^2\), and \(\frac{\mathsf{Q}_n k_n}{n^3}\to 0\) reduces to \(k_n/n\to 0\), namely \(k_n=o(n)\).

6.4 Proof of Corollary 4↩︎

We again apply Theorem [thm:cover95reduction95query95lb]. Since detection with the full graph is at least as powerful as detection from any set of non-adaptive queries, it is enough to consider the full-observation query set \[\begin{align} \mathbb{Q}_n=\binom{[n]}{2}. \end{align}\] For each triangle, choose two of its vertices and put them into the cover \(U_n\); let the remaining one vertex belong to \(W_n\). Then \(U_n\) is a vertex cover. The induced graph \(H_n=\Gamma_n[U_n]\) contains exactly one edge from each triangle and no edges between different triangles. Therefore \(H_n\) is a matching with exactly \(m_n\) edges.

We first verify that the core \(H_n\) is undetectable under full observation when \(m_n=o(n)\). Since \(H_n\) is a matching, \[\begin{align} |e(H_n)|=m_n, \quad d_{\mathsf{max}}(H_n)=1, \quad \mu(H_n)=\frac{1}{2}. \end{align}\] Thus \(H_n\) lies in the sublogarithmic-density regime, and the sharp full-observation lower bound for arbitrary planted graphs applies to \(H_n\): because \[\begin{align} \mu(H_n)=\frac{1}{2}=o(\log |v(H_n)|), \qquad |e(H_n)|=m_n=o(n), \qquad d^2_{\mathsf{max}}(H_n)=1=o(n), \end{align}\] we obtain \[\begin{align} d_{\mathrm{TV}}(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{0,\mathbb{Q}_n})\to 0. \end{align}\] So the core-undetectability condition of Theorem [thm:cover95reduction95query95lb] holds. It remains to check the weighted remainder condition.

Let us compute the quantities \(\Theta_{r,n}\) and \(\zeta_{r,n}\). Each vertex \(w\in W_n\) belongs to exactly one triangle, and its neighborhood inside the cover consists of the two chosen cover vertices from that triangle. Hence, for every singleton \(R=\{u\}\subseteq U_n\), there is exactly one vertex in \(W_n\) adjacent to \(u\), and for every pair \(R\subseteq U_n\) corresponding to the two chosen cover vertices from one of the triangles, there is exactly one vertex in \(W_n\) whose neighborhood contains \(R\). For every other subset \(R\subseteq U_n\) with \(|R|\ge 3\), or with \(|R|=2\) but not corresponding to one triangle, the set \(\mathcal{W}_n(R)\) is empty. Therefore \[\begin{align} \Theta_{1,n}=2m_n=\frac{2k_n}{3}, \qquad \Theta_{2,n}=m_n=\frac{k_n}{3}, \qquad \Theta_{r,n}=0,\quad r\ge 3. \label{eq:triangle95Theta95values} \end{align}\tag{50}\]

Next, since \(\mathbb{Q}_n=\binom{[n]}{2}\), every query degree equals \(t_i^{(n)}=n-1\). Hence, for every \(r\in\{1,\ldots,\tau_n\}\), \[\begin{align} \zeta_{r,n} = \sum_{i=1}^n \frac{(t_i^{(n)})_r}{(n)_r} = n\cdot \frac{(n-1)_r}{(n)_r} = n-r. \end{align}\] In particular, \[\begin{align} \zeta_{1,n}=n-1, \qquad \zeta_{2,n}=n-2. \label{eq:triangle95zeta95values} \end{align}\tag{51}\]

Finally, \(\tau_n=2m_n=2k_n/3\), so \[\begin{align} n-\tau_n=n-\frac{2k_n}{3}. \end{align}\] In the regime \(k_n=o(n)\), we have \(n-\tau_n\sim n\). Combining 50 and 51 , the weighted remainder term in Theorem [thm:cover95reduction95query95lb] is \[\begin{align} &\frac{e^2}{(n-\tau_n)^2} \sum_{r=1}^{\tau_n} (q^{-1}-1)^r\Theta_{r,n}\zeta_{r,n} \nonumber\\ &\qquad= \frac{e^2}{(n-\tau_n)^2} \Bigl( (q^{-1}-1)\Theta_{1,n}\zeta_{1,n} + (q^{-1}-1)^2\Theta_{2,n}\zeta_{2,n} \Bigr) \nonumber\\ &\qquad= \frac{e^2}{(n-\tau_n)^2} \Bigl( (q^{-1}-1)\frac{2k_n}{3}(n-1) + (q^{-1}-1)^2\frac{k_n}{3}(n-2) \Bigr) \nonumber\\ &\qquad= O_q\left(\frac{k_n n}{(n-\tau_n)^2}\right) = O_q\left(\frac{k_n}{n}\right) \to 0. \end{align}\] Therefore the weighted remainder condition of Theorem [thm:cover95reduction95query95lb] holds. The conclusion now follows from Theorem [thm:cover95reduction95query95lb].

6.5 Proof of Corollary 5↩︎

We again apply Theorem [thm:cover95reduction95query95lb]. Since detection with the full graph is at least as powerful as detection from any set of non-adaptive queries, it is enough to consider the full-observation query set \[\begin{align} \mathbb{Q}_n=\binom{[n]}{2}. \end{align}\] Every tree is bipartite. Let \(v(T_n)=A_n\sqcup B_n\) be a bipartition of the tree, and choose \(U_n\) to be the smaller side of the bipartition. Then every edge of \(T_n\) joins a vertex of \(U_n\) to a vertex of \(W_n\triangleq v(T_n)\setminus U_n\) so \(U_n\) is a vertex cover and \(H_n=T_n[U_n]\) is edgeless. Consequently \[\begin{align} \mathbb{P}_{H_n,\mathbb{Q}_n}=\mathbb{P}_{0,\mathbb{Q}_n}, \end{align}\] so the core-undetectability condition is automatic. It remains to verify the weighted remainder condition.

We first bound the quantities \(\Theta_{r,n}\). Since \(d_{\mathsf{max}}(T_n)\le D\), for every \(w\in W_n\) we have \(|N_n(w)|\le D\). Therefore, for every \(r>D\) and every subset \(R\subseteq U_n\) with \(|R|=r\), we have \(\mathcal{W}_n(R)=\emptyset\). Hence \[\begin{align} \Theta_{r,n}=0,\quad r>D. \label{eq:Theta95tree95zero} \end{align}\tag{52}\] Also, for every \(r\in\{1,\ldots,D\}\), \[\begin{align} \Theta_{r,n} &= \sum_{w,w'\in W_n} \binom{|N_n(w)\cap N_n(w')|}{r} \nonumber\\ &\le \sum_{w,w'\in W_n} \binom{|N_n(w)\cap N_n(w')|}{1} = \sum_{w,w'\in W_n}|N_n(w)\cap N_n(w')|. \label{eq:Theta95tree95first} \end{align}\tag{53}\] Now note that \[\begin{align} \sum_{w,w'\in W_n}|N_n(w)\cap N_n(w')| = \sum_{u\in U_n} d_{W_n}^2(u), \label{eq:Theta95tree95second} \end{align}\tag{54}\] where \[\begin{align} d_{W_n}(u)\triangleq \left|\{w\in W_n:\{u,w\}\in e(T_n)\}\right|. \end{align}\] Since \(d_{W_n}(u)\le D\) for every \(u\in U_n\), we get \[\begin{align} \sum_{u\in U_n} d_{W_n}^2(u) \le D\sum_{u\in U_n} d_{W_n}(u). \end{align}\] But \[\begin{align} \sum_{u\in U_n} d_{W_n}(u)=|e(T_n)|=k_n-1. \end{align}\] Therefore \[\begin{align} \Theta_{r,n}\le D(k_n-1)=O_D(k_n), \qquad r=1,\ldots,D. \label{eq:Theta95tree95final} \end{align}\tag{55}\]

Next, let us compute \(\zeta_{r,n}\) under full observation. Since \(\mathbb{Q}_n=\binom{[n]}{2}\), every query degree equals \(t_i^{(n)}=n-1\). Hence, for every \(r\in\{1,\ldots,\tau_n\}\), \[\begin{align} \zeta_{r,n} = \sum_{i=1}^n \frac{(t_i^{(n)})_r}{(n)_r} = n\cdot \frac{(n-1)_r}{(n)_r} = n-r \le n. \label{eq:zeta95tree95full95obs} \end{align}\tag{56}\] Now combine 52 , 55 , and 56 . The weighted remainder term in Theorem [thm:cover95reduction95query95lb] is \[\begin{align} \frac{e^2}{(n-\tau_n)^2} \sum_{r=1}^{\tau_n} (q^{-1}-1)^r\Theta_{r,n}\zeta_{r,n}&= \frac{e^2}{(n-\tau_n)^2} \sum_{r=1}^{D} (q^{-1}-1)^r\Theta_{r,n}\zeta_{r,n} \\ &\le \frac{e^2}{(n-\tau_n)^2} \sum_{r=1}^{D} (q^{-1}-1)^r \cdot O_D(k_n)\cdot n \\ &= O_{q,D}\left(\frac{nk_n}{(n-\tau_n)^2}\right). \end{align}\] Because \(|U_n|\le k_n/2\), we have \(n-\tau_n\ge n-\frac{k_n}{2}\). In the regime \(k_n=o(n)\), we have \(n-\tau_n\sim n\). Hence \[\begin{align} \frac{e^2}{(n-\tau_n)^2} \sum_{r=1}^{\tau_n} (q^{-1}-1)^r\Theta_{r,n}\zeta_{r,n} = O_{q,D}\left(\frac{k_n}{n}\right) \to 0. \end{align}\] Thus the weighted remainder condition of Theorem [thm:cover95reduction95query95lb] holds, and the conclusion follows.

6.6 Proof of Corollary 6↩︎

Fix \(n\). Choose once and for all a minimum vertex cover \(U_n=\{u_1,\dots,u_{\tau_n}\}\subseteq v(\Gamma_n)\), and let \(W_n\triangleq v(\Gamma_n)\setminus U_n\). Since \(U_n\) is a vertex cover, the set \(W_n\) is independent in \(\Gamma_n\), i.e., \(e(\Gamma_n)\cap \binom{W_n}{2}=\emptyset\). Hence every edge of \(\Gamma_n\) is either inside \(U_n\) or between \(U_n\) and \(W_n\). Define \(H_n\triangleq \Gamma_n[U_n]\). Then \(H_n\) has at most \(\tau_0\) vertices and at most \(R_0\triangleq \binom{\tau_0}{2}\) edges. Let \(R_n\triangleq |e(H_n)|\le R_0\). Take two independent planted copies of \(H_n\), and let \(\mathsf{X}^{(H)}_{\mathbb{Q}_n}\) denote the number of queried edges that belong to both planted copies. We have \[\begin{align} 1+\chi^2(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{0,\mathbb{Q}_n}) = \mathbb{E}\left[q^{-\mathsf{X}^{(H)}_{\mathbb{Q}_n}}\right]. \label{eq:bounded95cover95chi295identity} \end{align}\tag{57}\] Since \[\begin{align} 0\le \mathsf{X}^{(H)}_{\mathbb{Q}_n}\le R_n\le R_0, \end{align}\] we have \[\begin{align} q^{-\mathsf{X}^{(H)}_{\mathbb{Q}_n}}-1 \le (q^{-R_0}-1)\mathbb{1}\{\mathsf{X}^{(H)}_{\mathbb{Q}_n}\ge 1\} \le (q^{-R_0}-1)\mathsf{X}^{(H)}_{\mathbb{Q}_n}. \end{align}\] Taking expectations and using 57 , \[\begin{align} \chi^2(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{0,\mathbb{Q}_n}) \le (q^{-R_0}-1)\mathbb{E}\left[\mathsf{X}^{(H)}_{\mathbb{Q}_n}\right]. \label{eq:bounded95cover95chi295reduce} \end{align}\tag{58}\] We now compute \(\mathbb{E}[\mathsf{X}^{(H)}_{\mathbb{Q}_n}]\). For each queried edge \(e\in\mathbb{Q}_n\), by symmetry of the uniformly random injective embedding of \(H_n\) into \([n]\), \[\begin{align} \mathbb{P}[e\in e(H_n^\star)]=\frac{R_n}{\binom n2}, \end{align}\] where \(H_n^\star\) denotes one planted copy of \(H_n\). Thus, for two independent copies, \[\begin{align} \mathbb{P}(e\in e(H_n^\star)\cap e(\widetilde{H}_n^\star)) = \left(\frac{R_n}{\binom n2}\right)^2. \end{align}\] Therefore \[\begin{align} \mathbb{E}[\mathsf{X}^{(H)}_{\mathbb{Q}_n}] &= \sum_{e\in\mathbb{Q}_n} \mathbb{P}(e\in e(H_n^\star)\cap e(\widetilde{H}_n^\star)) \\ &= \mathsf{Q}_n\left(\frac{R_n}{\binom n2}\right)^2 \le \binom n2\left(\frac{R_0}{\binom n2}\right)^2 = \frac{R_0^2}{\binom n2}. \label{eq:bounded95cover95EX} \end{align}\tag{59}\] Since \(\binom n2\to\infty\), we obtain \(\mathbb{E}[\mathsf{X}^{(H)}_{\mathbb{Q}_n}]\to 0\). Combining this with 58 , we get \(\chi^2(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{0,\mathbb{Q}_n})\to 0\), and hence \(d_{\mathrm{TV}}(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{0,\mathbb{Q}_n})\to0\).

It remains to verify the remainder condition. Since \(\tau_n\le \tau_0\), every \(w\in W_n\) satisfies \(|N_n(w)|\le \tau_0\), and therefore \[\begin{align} \Theta_{r,n}=0,\qquad r>\tau_0. \end{align}\] Also, \[\begin{align} \Theta_{1,n} = \sum_{u\in U_n} d_{W_n}(u)^2 \le \tau_0\Delta_n^2. \end{align}\] More generally, for each fixed \(r\in\{1,\ldots,\tau_0\}\), \[\begin{align} \Theta_{r,n} = \sum_{\substack{R\subseteq U_n\\ |R|=r}} |\mathcal{W}_n(R)|^2 \le \binom{\tau_0}{r}\Delta_n^2, \end{align}\] because \(|\mathcal{W}_n(R)|\le \Delta_n\) for every nonempty \(R\subseteq U_n\). Hence \[\begin{align} \sum_{r=1}^{\tau_n}(q^{-1}-1)^r\Theta_{r,n} \le C_{q,\tau_0}\Delta_n^2 \end{align}\] for a constant \(C_{q,\tau_0}<\infty\). Since \(\tau_n\le \tau_0\), we have \(n-\tau_n\asymp n\), and Corollary 1 gives \[\begin{align} \frac{2e^2\mathsf{Q}_n}{n(n-\tau_n)^2} \sum_{r=1}^{\tau_n}(q^{-1}-1)^r\Theta_{r,n} = O\left(\frac{\mathsf{Q}_n\Delta_n^2}{n^3}\right). \end{align}\] This tends to \(0\) by assumption, and the conclusion follows.

6.7 Proof of Corollary 7↩︎

Choose the vertex cover \(U_n\triangleq v(\Gamma_n)\), that is, choose the entire vertex set. Then \(W_n=\emptyset\) and \(H_n=\Gamma_n\). Hence \(\Xi_n=0\), so the remainder condition in Theorem [thm:cover95reduction95query95lb] is automatic. Since \(H_n=\Gamma_n\), the auxiliary planted model \(\mathbb{P}_{H_n,\mathbb{Q}_n}\) is simply the original planted model for the clique. Now apply the direct edge-hit lower bound to \(H_n=K_{k_n}\): if \[\begin{align} \mathsf{Q}_n\cdot \frac{|e(H_n)|}{\binom n2} = \mathsf{Q}_n\cdot \frac{\binom{k_n}{2}}{\binom n2} \to 0, \end{align}\] then \(d_{\mathrm{TV}}(\mathbb{P}_{H_n,\mathbb{Q}_n},\mathbb{P}_{0,\mathbb{Q}_n})\to 0\). Thus the core-undetectability assumption of Theorem [thm:cover95reduction95query95lb] holds, and the conclusion follows.

6.8 Proof of Corollary 8↩︎

Choose the vertex cover \(U_n\) to be the \(k_n\) clique vertices. Then \(H_n=\Gamma_n[U_n]=K_{k_n}\), while every vertex in \(W_n=v(\Gamma_n)\setminus U_n\) is a pendant leaf adjacent to exactly one vertex of the core.

We first verify the core condition in Theorem [thm:cover95reduction95query95lb]. Since \[\begin{align} H_n=K_{k_n}, \end{align}\] Corollary 7 implies that \[\begin{align} d_{\mathrm{TV}} ( \mathbb{P}_{H_n,\mathbb{Q}_n}, \mathbb{P}_{{\cal H}_0,\mathbb{Q}_n} ) \to0 \end{align}\] whenever \[\begin{align} Q_n=o\left(\frac{n^2}{k_n^2}\right). \end{align}\]

It remains to analyze the attachment term. Since every vertex of \(W_n\) has exactly one neighbor in the core, \[\begin{align} \Theta_{1,n} = k_n\Delta_n^2, \qquad \Theta_{r,n}=0, \quad r\ge2. \end{align}\] Furthermore, by Lemma 3, \[\begin{align} \zeta_{1,n} \le \frac{2Q_n}{n}. \end{align}\] Therefore \[\begin{align} \frac{1}{(n-k_n)^2} \sum_{r=1}^{k_n} (q^{-1}-1)^r \Theta_{r,n}\zeta_{r,n} = O\!\left( \frac{Q_nk_n\Delta_n^2}{n^3} \right), \end{align}\] where we used \(k_n\le n\) and hence \((n-k_n)^2\asymp n^2\) throughout the nontrivial regime.

Consequently, condition [eq:assump95remainder95negligible] holds whenever \[\begin{align} Q_n = o\left( \frac{n^3}{k_n\Delta_n^2} \right). \end{align}\] Applying Theorem [thm:cover95reduction95query95lb] now yields \[\begin{align} Q_n = o\left( \min\left\{ \frac{n^2}{k_n^2}, \, \frac{n^3}{k_n\Delta_n^2} \right\} \right) \Longrightarrow d_{\mathrm{TV}} ( \mathbb{P}_{{\cal H}_1,\mathbb{Q}_n}, \mathbb{P}_{{\cal H}_0,\mathbb{Q}_n} ) \to0, \end{align}\] which is equivalent to weak detection being impossible.

6.9 Proof of Corollary 9↩︎

We prove Corollary 9, restating it here for convenience with additional details.

6.10 Proof of Corollary 10↩︎

We prove Corollary 10, restating it here for convenience with additional details.

7 Preliminaries↩︎

7.1 Proof of Lemma 2↩︎

Fix \(\lambda>0\). Since \(Z\ge 0\), \[\begin{align} \mathbb{P}(Z=0)=\mathbb{P}(e^{-\lambda Z}=1)\leq \mathbb{E}[e^{-\lambda Z}]. \label{eq:markov} \end{align}\tag{72}\] Write \(Z=\sum_{c\in{\cal C}} I_c\). Expand \(e^{-\lambda Z}=\prod_{c\in{\cal C}} e^{-\lambda I_c}\) and note \(e^{-\lambda I_c}=1-(1-e^{-\lambda})I_c\). Thus \[\begin{align} \mathbb{E}[e^{-\lambda Z}] =\mathbb{E}\left[\prod_{c\in{\cal C}} \left(1-\theta I_c\right)\right],\qquad \theta\triangleq 1-e^{-\lambda}\in(0,1). \label{eq:prod95form} \end{align}\tag{73}\]

Now use the elementary inequality, valid for any \(\theta\in(0,1)\) and any \(\{0,1\}\)-valued random variables: \[\begin{align} \prod_{c\in{\cal C}} (1-\theta I_c) \leq \exp\left(-\theta \sum_{c\in{\cal C}} I_c + \theta^2 \sum_{c\sim c'\in{\cal C}} I_c I_{c'}\right). \label{eq:exp95dom} \end{align}\tag{74}\] To see 74 , take logs and use \(\log(1-x)\leq -x\) for \(x\in[0,1]\) to control the linear term, and then add back a quadratic correction over dependent pairs; one may verify 74 by expanding the product and bounding mixed terms by the sum over overlapping pairs. Taking expectations and applying Jensen’s inequality to the convex map \(x\mapsto e^{x}\) yields \[\begin{align} \mathbb{E}[e^{-\lambda Z}] &\leq \mathbb{E}\left[\exp\left(-\theta Z + \theta^2 \sum_{c\sim c'\in{\cal C}} I_c I_{c'}\right)\right]\nonumber\\ &\leq \exp\left(-\theta \mathbb{E}[Z] + \theta^2 \sum_{c\sim c'\in{\cal C}} \mathbb{E}[I_c I_{c'}]\right) = \exp\left(-\theta\mu + \theta^2 \Delta\right). \label{eq:mgf95bound} \end{align}\tag{75}\] Combining 72 and 75 , \[\begin{align} \mathbb{P}(Z=0)\leq \exp(-\theta\mu + \theta^2\Delta). \end{align}\] Optimize over \(\theta\in(0,1)\) (equivalently over \(\lambda>0\)). The quadratic function \(-\theta\mu+\theta^2\Delta\) is minimized at \(\theta^\star=\min\{1,\mu/(2\Delta)\}\) if \(\Delta>0\). A slightly sharper (and standard) optimization yields the bound ?? : take \(\theta = \mu/(\mu+\Delta)\in(0,1)\) to get \[\begin{align} -\theta\mu+\theta^2\Delta =-\frac{\mu^2}{\mu+\Delta}+\frac{\mu^2\Delta}{(\mu+\Delta)^2} =-\frac{\mu^2}{\mu+\Delta}\cdot \frac{\mu}{\mu+\Delta} \leq -\frac{\mu^2}{\mu+\Delta}, \end{align}\] and hence ?? .

7.2 Auxiliary lemmata↩︎

Recall the following standard concentration inequalities

References↩︎