1 Introduction↩︎

Given a positive integer \(n\), two distributions \(\mathcal{P}_n\) and \(\mathcal{Q}_n\), and a graph collection \(\mathcal{H}_n\) in which every graph has exactly \(m\) edges, we study the recovery of a hidden graph \(H^*\) from a weighted complete graph \(A\) on \(n\) vertices and \(N = \binom{n}{2}\) edges. Hereafter, we abbreviate \(\mathcal{P}_n\), \(\mathcal{Q}_n\), and \(\mathcal{H}_n\) as \(\mathcal{P}\), \(\mathcal{Q}\), and \(\mathcal{H}\), respectively. First, \(H^*\) is sampled uniformly from \(\mathcal{H}_n\). Then each edge in \(H^*\) receives an independent weight from \(\mathcal{P}_n\), whereas each edge outside \(H^*\) receives an independent weight from \(\mathcal{Q}_n\). The task is to recover \(H^*\) from \(A\) given \(\mathcal{P},\mathcal{Q},\mathcal{H}\). Here the hidden edge set \(H^*\) is the signal, while the remaining edge weights constitute the noise. Besides its mathematical appeal, locating the information-theoretic limit of such recovery is also motivated by applications where data collections are costly, such as in brain imaging and whole-genome sequencing. Here, we require that \(m \to \infty\) as \(n \to \infty\), so that the recovery guarantees can be well-defined. We mainly focus on the following recovery guarantees:

• Almost exact recovery: An estimator achieves almost exact recovery if it finds \(\hat{H} \in \mathcal{H}\) such that, the number of overlapping edges between \(H^*\) and \(\hat{H}\) satisfies \(\Pr[|\hat{H} \cap H^*| <\) \((1 - \delta_n)m] \to 0\), for some sequence \(\delta_n\) that tends to \(0\) as \(n \rightarrow \infty\).

• Partial recovery: For a constant \(\lambda \in (0, 1)\), the goal is to find a \(\hat{H} \in \mathcal{H}\) such that \(|\hat{H} \cap H^*| \ge \lambda m\) with probability \(1-o_n(1)\).

If at any given signal-to-noise ratio, as \(n \to \infty\), one could either recover almost all of \(H^*\), or not even any constant fraction of \(H^*\), this is known as an All-or-Nothing (AoN) phenomenon.

Depending on the choice of \(\mathcal{H}_n\), this model captures many statistical inference questions. When \(\mathcal{H}_n\) consists of all isomorphic copies of a given graph \(H_n\), we refer to it as an isomorphic graph collection, denoted by \(\mathcal{H}_H\). Examples include:

• Planted cliques. The well-known planted clique problem [3] corresponds to \(\mathcal{H}\) being the set of \(k\)-cliques, and \(\mathcal{P}_n=\mathrm{Bern}(1)\) and \(\mathcal{Q}_n=\mathrm{Bern}(p)\) are Bernoulli distributions. Some recent examples are in complexity theory [4], cryptography [5], and algorithms such as MCMC [6], sum-of-squares and low-degree methods [7], [8].

• Gaussian hidden cliques and the sparse Wigner model. The Gaussian variant of planted cliques has also received a lot of attention in the machine learning community both for studying spectral algorithms [9], and as the sparse spiked Wigner model for sparse PCA [10]–[12]. Indeed, in the sparse spiked Wigner model, one needs to recover a sparse unit vector \(x\) from observing \(\sqrt{\mathrm{snr}}xx^\top + W\), where \(W\) is an independent Gaussian Wigner matrix. Notably, [13] showed an All-or-Nothing phenomenon for this model (in fact, for the general Gaussian additive model) under discrete prior: at any fixed signal-to-noise ratio, one could either recover the signal almost perfectly, or nothing at all. Under the discrete prior studied in [13], this AoN result rules out a distinct constant-fraction partial-recovery regime.

• Hamiltonian cycle recovery was studied in [14], motivated by genome assembly, where the hidden cycle represents the true order of genome segments and edge weights model experimental Hi-C reads [15]. They established sharp thresholds for exact recovery under suitable divergence conditions.

• Perfect matchings recovery was proposed in [16] to model moving objects/particles tracking. Since then, many variants have been proposed and studied, see, e.g.,  [17], [18] for exponential distribution on weights, and [19] for more general distributions and allowing the observation to be a sparse bipartite version of \(G(n,d/n)\) instead of a weighted complete graph.

• \(2k\)-nearest-neighbor (NN) graphs, which consist of \(n\) nodes on a ring, where each node is also connected to its \(2k\) nearest neighbors, was introduced by [1] as an improved approximation to genome assembly that takes advantage of longer-range but still nearby linkage information. This naturally generalizes Hamiltonian cycles, and it can also be seen as a variant of the celebrated Watts-Strogatz small-world graph model [20], [21], where a \(2k\)-NN graph is hidden in an unweighted random graph by a rewiring procedure.

We also consider non-isomorphic graph collections \(\mathcal{H}\) with the same number of vertices and edges, that are not generated by isomorphic copies of a single graph, and we name a few such examples:

• Uniform \(m\)-subgraphs are perhaps the most basic setting. We consider all subgraphs with \(m\) edges, ignoring structural constraints. Then, the set of edge weights can be viewed as an \(\binom{n}{2}\)-dimensional real-valued vector. The recovery of a hidden \(m\)-subgraph is therefore a discrete analog of sparse mean estimation problems [22], [23]. Indeed, in the \(m\)-sparse Gaussian location family, the mean \(\theta\in \mathbb{R}^{\binom{n}{2}}\) has at most \(m\) non-zeros. In these mean estimation problems, one is often more interested in the sample complexity in relation to an estimation error (often \(\ell_2\)). Our setting is more combinatorial in nature, as one tries to recover the mean \(\theta\) given only one sample, and the error is measured in Hamming distance.

• Trees were analyzed very recently in [24] via local weak convergence, using fixed-point equations to precisely characterize the fraction of correctly recovered edges by the minimum spanning tree, as well as its mean weight. Their approach is also applicable to the planted Hamiltonian cycle problem and the detection problem.

• \(k\)-factors can be seen as a generalization of perfect matchings. A \(k\)-factor is a spanning subgraph of degree \(k\). Indeed, \(1\)-factor corresponds to perfect matchings, and a \(2\)-factor consists of a set of cycles that spans the entire graph, and is closely related to Hamiltonian cycles. [14] show that within the exact recovery regime of the hidden Hamiltonian cycle model, a linear programming relaxation designed for \(2\)-factor can be used to recover the hidden Hamiltonian cycle with high probability.

1.1 Our results↩︎

By viewing the hidden graph as a structural “signal”, and the noisy edge weights as the “noise”, a natural question is:

What is the “signal-to-noise ratio” threshold for almost exact recovery of a structural “signal”? And if one only needs to recover a \(\lambda\) fraction of the hidden graph, how does the threshold change in terms of \(\lambda\)?

We give a unified answer that applies to a broad class of graphical structures and a broad class of distributions, by connecting the KL divergence between \(\mathcal{P}\) and \(\mathcal{Q}\), to the first moment threshold in Erdős-Rényi random graph models. Our characterization applies to collections of graphs \(\mathcal{H}\) that are uniformly sparse, and to distributions whose Rényi divergence satisfies a local Lipschitzness condition. In the following, we explain these conditions on \(\mathcal{H}\) and assumptions on distributions \(\mathcal{P}\) and \(\mathcal{Q}\) more formally.

Assumptions on graph collections. Before introducing the notion of uniformly sparse graphs, it is helpful to recall the first moment flat condition introduced by [2], under which they characterized the All-or-Nothing (AoN) threshold in Erdős-Rényi random graph model with a planted graph from isomorphic \(\mathcal{H}\). They further showed that first moment flatness is also necessary for many graph collections in the planted Erdős-Rényi random graph model to exhibit AoN. Intuitively, this condition asks that any \(H\in \mathcal{H}\) does not contain any particularly dense subgraph. More formally, for a graph collection \(\mathcal{H}\), let \(M=\left\vert\mathcal{H}\right\vert\) denote its cardinality and \(m\) denote the number of edges in each graph, the first moment threshold is defined as \(p_{1M}(\mathcal{H}) := M^{-\frac{1}{m}}\). Put differently, it is the threshold where the expected number of copies of all \(H \in \mathcal{H}\) in Erdős-Rényi graph \(G(n,p)\) equals \(1\). For an isomorphic graph collection \(\mathcal{H}_H\) consisting of all graphs isomorphic to graph \(H\), we further define the expectation threshold as \(p_E(\mathcal{H}_H) := \max_{J \subseteq H} p_{1M}(\mathcal{H}_J)\), where \(J\) is an edge induced subgraph of \(H\) (hereafter abbreviated as \(p_{1M}\) and \(p_E\) respectively). These are basic thresholds in random graph theory that serve as convenient lower bounds for the critical threshold.

The more general condition for graph collections used in our analysis is the following uniformly sparse condition. This is closely related to the growth condition for exponential scale AoN in Equation (3.6) of [2], but to handle non-isomorphic graph collections and general distributions, we adopt a slightly stronger form.

Intuitively, the condition \(\log(p_{1M}^{-1})=\omega(1)\) requires the graph to be sufficiently sparse, while the overlap probability condition rules out the presence of locally dense subgraphs. We will show in 6 that first moment flat graphs satisfying \(\log(p_{1M}^{-1}) = \omega(1)\) are always uniformly sparse. Furthermore, another sufficient condition for uniform sparsity is that the graph collection is sufficiently large. Examples include uniform \(m\)-subgraphs, trees, and \(k\)-factors.

Assumptions on distributions. Let \(D_{\alpha}(\mathcal{P} \| \mathcal{Q}) := \frac{1}{\alpha-1} \log \mathbb{E}_{\mathcal{P}} \left[ \left( \frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}} \right)^{\alpha - 1} \right]\) be the Rényi divergence of order \(\alpha\) (in this paper we assume that \(\mathcal{P} \ll \mathcal{Q}\)). This family of divergences interpolates several classical discrepancy measures: in particular, \(\lim_{\alpha\to 1} D_{\alpha}(\mathcal{P}\|\mathcal{Q})=D_{\mathrm{KL}}(\mathcal{P}\|\mathcal{Q})\), and \(D_{2}(\mathcal{P}\|\mathcal{Q})=\log\bigl(1+\chi^{2}(\mathcal{P}\|\mathcal{Q})\bigr)\), where \(\chi^{2}(\mathcal{P}\|\mathcal{Q})\) denotes the chi-squared divergence, a natural quantity in second-moment arguments underlying contiguity and testing lower bounds. We focus on distributions with a stable Rényi divergence, which are satisfied by many natural distributions. These assumptions facilitate a unified analysis framework: they can be used both in deriving upper and lower bounds.

We will refer to distributions \(\mathcal{P}\) and \(\mathcal{Q}\) that satisfy these assumptions as Rényi-stable. In 7, we show that the above assumptions hold for many distributions (e.g., Bernoulli, Gaussian, and Exponential distributions), and in various regimes. We also provide some intuitions there.

Our main result is that the critical threshold for almost exact recovery is around \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \approx \log(p_{1M}^{-1})\). Recovering a \(\lambda\)-fraction of edges requires \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \gtrapprox \lambda \log(p_{1M}^{-1})\). Furthermore, when \(D_{2}(\mathcal{P} \| \mathcal{Q})\) is below \(\log(p_{1M}^{-1})\), constant fraction recovery becomes impossible.

The four parts of 1 are proved in [sec:almost-upper-bound,sec:almost-lower-bound,sec:partial-lower-bound,sec:12renyi-aon] respectively.

1 illustrates the recovery phase transition characterized in 1. The horizontal axis represents the KL divergence \(D_{\mathrm{KL}}(\mathcal{P}\|\mathcal{Q})\), while the vertical axis represents the fraction of edges attempted to be recovered. The green region labeled ‘All’ corresponds to part (1), where \(D_{\mathrm{KL}} \ge (1+\eta)\log(p_{1M}^{-1})\) and the MLE achieves almost exact recovery. The big red upper triangular region corresponds to part (3), where \(D_{\mathrm{KL}} \le (\lambda-\eta)\log(p_{1M}^{-1})\) and any algorithm fails to recover \(\lambda\) fraction of edges with any constant probability. For a fixed parametrization of the distribution pair, let \(\kappa_2\) denote the value of \(D_{\mathrm{KL}}\) at which \(D_2(\mathcal{P}\|\mathcal{Q})=\log(p_{1M}^{-1})\). By the monotonicity of Rényi divergence (\(D_{\mathrm{KL}} = D_1 \le D_2\)), \(\kappa_2\) is no larger than \(\log(p_{1M}^{-1})\). To the left of this point, the red rectangular area labeled ‘Nothing’ represents part (4), where \(D_2(\mathcal{P}\|\mathcal{Q}) \le (1-\eta)\log(p_{1M}^{-1})\), and any algorithm fails to recover any constant fraction of edges with any constant probability. While the regions defined by parts (3) and (4) partially overlap, their union gives the region in which the success probability of any recovery algorithm vanishes asymptotically.

For the all-or-nothing phenomenon (AoN), we adopt the definition of [2]. They identified two types of AoN, to unify treatment, we use the KL divergence as a common signal-to-noise scale: In the linear scale AoN regime, the phase transition is said to occur at \(D_{\mathrm{KL}} = D_{\mathrm{AoN}} \pm \varepsilon\); whereas in the exponential scale regime, the transition occurs at \(D_{\mathrm{KL}} = (1 \pm \varepsilon) D_{\mathrm{AoN}}\) for any constant \(\varepsilon > 0\). Unless otherwise specified, we will focus on the exponential-scale AoN regime in what follows.

Unlike almost exact recovery, the existence of AoN crucially depends on the choice of distribution. In particular, [2] proved that for \(\mathcal{P} = \mathrm{Bern}(1)\) and \(\mathcal{Q} = \mathrm{Bern}(p)\), there is an exponential scale AoN for \(\mathcal{H}\) that are first moment flat. For \(\mathcal{P} = \mathrm{Exp}(1/\mu)\), \(\mathcal{Q} = \mathrm{Exp}(1/n)\), [24] suggests that for \(\mathcal{H}\) being the set of trees or Hamiltonian paths, an AoN occurs in the exponential scale. If we restate these thresholds in terms of the KL divergence, they both occur at \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) = (1\pm o(1)) \log(p_{1M}^{-1})\).

Given item 1 and 4 in 1, if \(D_{2}(\mathcal{P} \| \mathcal{Q}) = (1+ o(1)) D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q})\), then one immediately has an exponential scale AoN at \(D_{\mathrm{KL}}(\mathcal{P}\|\mathcal{Q}) \approx \log(p_{1M}^{-1})\).

Not all distributions satisfy \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\). In 7.4, we show that distributions satisfying \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\) include Bernoulli and Exponential distributions under natural parameterizations. Two notable exceptions are \(\mathcal{P}=\mathrm{Bern}(\Theta(1)),\;\mathcal{Q}=\mathrm{Bern}(o(1))\), and Gaussian distributions.

For the first exception of Bernoulli, there is no AoN in general, and our partial recovery lower bound (item 3 in 1) is tight. In this case, the entire blue region of 1 can have partial recovery.

We prove this theorem in 9.

For the other exception of Gaussian distributions, AoN has been studied in the context of sparse PCA [13]. We show that AoN is universal for recovering hidden structures with Gaussian weights, by lifting the sharp threshold for almost exact recovery to an AoN through the I-MMSE relation for Gaussian channels. In particular, this means that the entire blue region of 1 corresponds to “Nothing” for Gaussian distributions.

Last but not least, we show in 8 that for sufficiently large \(\mathcal{H}\) and distributions satisfying 1, a simple top-\(m\) selection based on the likelihood ratio recovers almost all hidden edges with high probability, if the estimator is allowed to output an arbitrary \(m\)-edge subset rather than a member of \(\mathcal{H}\). Notable examples of sufficiently large \(\mathcal{H}\) include perfect matchings and Hamiltonian paths/cycles (see 3).

1.2 Technical overview and paper organization↩︎

The notion of uniform sparsity will play a recurring role throughout our analysis, as it allows a unified analysis of a broad class of structures, whether isomorphic or not. Two convenient sufficient conditions for uniform sparsity are first moment flat and sufficiently large. While our main focus is information-theoretic thresholds for estimators taking values in \(\mathcal{H}\), we note that for sufficiently large \(\mathcal{H}\) and distributions satisfying 1, a simple top-\(m\) selection already recovers almost all hidden edges if arbitrary \(m\)-edge subsets are allowed.

Our upper bound for almost exact recovery in 1 comes from the maximum likelihood estimator (MLE). We extend the approach of [1], which was designed for \(2k\)-NN graphs and for distributions whose log-MGF has a quadratic lowerbound near the boundary. We are able to generalize to a broad class of graphs – uniformly sparse graph collections, and to a wider family of Rényi-stable distributions. In essence, we use Chernoff bound together with union bound to control the deviations of likelihood. In particular, the optimal Chernoff exponent comes from balancing the deviations of edges inside and outside the hidden \(H\). The first moment threshold dictates what Chernoff exponent can beat the union bound, while the KL divergence dictates what Chernoff exponent can be achieved. This is established in 2.

In 3, we employ two information-theoretic methods: Our almost exact recovery lower bound (part (2) in 1) is based on a standard application of distance-based Fano’s inequality, and is established in 3.1. Notably, this simple lower bound does not require the assumption of Rényi-stability of \(\mathcal{P},\mathcal{Q}\). The key to a tight characterization is a good estimate for the mutual information, and controlling the growth rate of overlaps for uniformly sparse \(\mathcal{H}\). For partial recovery, however, standard Fano’s inequality based on mutual information does not yield a strong enough converse bound. Our partial recovery lower bound (part (3) in 1) is based on working with the Sibson’s \(\alpha\)-mutual information instead of the mutual information. We establish a distance-based variant of Fano’s inequality from Sibson’s \(\alpha\)-mutual information [25], from which we derive our lower bound by choosing an appropriate \(\alpha\) in 3.2. The existence of such \(\alpha\neq 1\) is guaranteed by Rényi stability.

4 focuses on the lower bound for the ‘Nothing’ phase and sufficient conditions for AoN. 4.1 generalizes the second moment method from [2] to weighted distributions, and substituting the corresponding “signal-to-noise ratio” part with \(D_2\). This proves part (4) of 1, demonstrating AoN for distributions with \(D_2=(1+o(1))D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)(\mathcal{P}\|\mathcal{Q})\). For our Gaussian AoN result in 3, we show in 4.2 that a sharp transition for almost exact recovery can be lifted to an AoN phenomenon with the help of an I-MMSE relation. I-MMSE relation (restated at 8) is most famously known for Gaussian distributions, and it would be interesting to see if there could be relaxation of the I-MMSE relation where such lifting is possible.

Last but not least, we also complement with an example where our partial recovery lower bound is tight in 9.

1.3 Related works↩︎

There has been significant recent progress on the problems of almost exact recovery and partial recovery. The most important part of our work is a unified approach across a broad class of graph structures, or a broad class of distributions, or both. In specific instances however, there are some prior works that give more refined phase transition than ours. We explain these instances where we fall short below.

[1] studied almost exact recovery in \(2k\)-NN graphs under certain assumptions on the distribution. They established a threshold on the KL divergence of the distribution: when \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) = (1 + \eta) \log(n) / k\), almost exact recovery is achievable, and they also proved that this threshold is information-theoretically necessary. Our result for almost exact recovery is a generalization both in terms of the hidden structure, and in terms of the distributions \(\mathcal{P}\) and \(\mathcal{Q}\).

[2] investigated recovery in the classical Erdős-Rényi random model \(G(n,p)\). They studied both linear scale and exponential scale AoN and demonstrated that many planted subgraph recovery problems exhibit AoN. The requirement they impose on graphs to exhibit exponential scale AoN is precisely first moment flatness, together with either \(\log(p_{1M}^{-1})=\omega(1)\) or \(v(H)=n^{o(1)}\), and they characterized linear scale AoN for graph families that satisfy more stringent structural conditions. While [2] showed AoN for \(\mathcal{P}\) and \(\mathcal{Q}\) being Bernoulli distributions, we show that under a different parameterization of Bernoullis, there is no AoN. In fact, our partial recovery lower bound can be sharp.

[18] investigated the planted matching problem under exponential distributions on edge weight. In the All phase, they establish a linear scale phase transition, while in the Nothing phase, they employ the method of local weak convergence and analyze an associated system of ordinary differential equations (ODEs) to derive exact expressions for the expected overlap. After that, [19] provides an explicit lower bound and confirms the infinite-order phase transition conjectured in [17]. Subsequently, [24] studied the problem of recovering a planted Hamiltonian cycle or a spanning tree using the minimum spanning tree (MST). They derived, via a fixed-point equation, the asymptotic relation between a constant parameter \(\mu\) and the fraction of edges recovered. Rephrased in terms of the KL divergence, it corresponds to \(D_{\mathrm{KL}}(\mathcal{P}\|\mathcal{Q}) = (1+o(1)) \log(p_{1M}^{-1}/\mu)\), which implies an AoN transition on the exponential scale, while there is no AoN in the linear scale: partial recovery remains possible and the fraction of recovery varies smoothly with \(\mu\).

1.4 Discussions and open problems↩︎

Although our work unifies a broad class of hidden weighted graph recovery problems across various graph structures and edge weight distributions, several limitations and open problems remain. In particular, beyond uniformly sparse graph families, a complete understanding is still lacking.

In this paper, we mainly focus on the study of almost exact recovery and partial recovery. One may be tempted to ask for a unified understanding of the exact recovery thresholds. We note, however, that it would likely require a more detailed study of a local structure, which may vary across different graph structures, such as the “crossing” structure in [14]. Likewise, a unified understanding of AoN would also be desirable. On the distributional side, it remains unclear for which pairs of distributions \((\mathcal{P},\mathcal{Q})\) AoN should occur: at present, we only identify two independent sufficient, but not necessary, conditions that guarantee AoN. On the graph-structural side, [2] further shows that, under the \(G(n,p)\) planted model, for two broad class of graph collections, they established necessary and sufficient conditions for AoN to hold at linear or exponential scales. Furthermore, a very recent work [26] investigated more general graph structures under the \(G(n,p)\) planted model and analyzed their MMSE curves in regimes where AoN may fail to occur.

AoN also appears to be intimately tied to computational-statistical gaps in many statistical inference problems. We focus mainly on the statistical limits of recovery in this paper, and it would be nice to have a unified understanding of where AoN, or computational-statistical gaps could be found.

2 Almost exact recovery upper bound by MLE↩︎

We adapt the framework of [1] to uniformly sparse \(\mathcal{H}\) and Rényi-stable distributions.

Since \(H^*\) is chosen uniformly at random from \(\mathcal{H}\), the MLE coincides with the maximum a posteriori (MAP) estimator. Let \(\hat{H}_{\mathrm{MLE}}\) denote the graph in \(\mathcal{H}\) that maximizes the likelihood. By definition: \[\begin{align} \hat{H}_{\mathrm{MLE}} &= \mathop{\mathrm{arg\,max}}_{H \in \mathcal{H}} \prod_{e \in H} \frac{\mathrm{d}\mathcal{P}}{\mathrm{d}\mathcal{Q}}(A_e) = \mathop{\mathrm{arg\,max}}_{H \in \mathcal{H}} \sum_{e \in H} L_e, \end{align}\] where \(A_e\) is the weight of edge \(e\) in the observed graph \(A\), and \(L_e := \log \frac{\mathrm{d}\mathcal{P}}{\mathrm{d}\mathcal{Q}} (A_e)\) represents the log-likelihood ratio of \(A_e\). Since \(\mathcal{P} \ll \mathcal{Q}\), this Radon–Nikodym derivative is well-defined, and \(L_e\) is understood as an extended-real random variable. Let \(\mathcal{X}\) and \(\mathcal{Y}\) denote the distributions of \(\log \frac{\mathrm{d}\mathcal{P}}{\mathrm{d}\mathcal{Q}}\) under the measures \(\mathcal{P}\) and \(\mathcal{Q}\), respectively. Then, for any edge \(e\), the log-likelihood \(L_e\) independently follows the distribution \(\mathcal{X}\) if \(e \in H^*\), and follows the distribution \(\mathcal{Y}\) otherwise.

Define \(L(H) := \sum_{e \in H} L_e\). The MLE selects a graph \(\hat{H}_{\mathrm{MLE}}\) that maximizes \(L(H)\). We aim to show that, with high probability, every maximizer is close to the hidden graph \(H^*\). In fact, we will prove a slightly stronger statement: there exists a sequence \(\delta_n \to 0\) such that, with high probability, no graph \(H \in \mathcal{H}\) whose distance to \(H^*\) exceeds \(\delta_n m\) satisfies \(L(H) > L(H^*)\) (the distance is defined as the number of edges that appear in \(H^*\) but not in \(H\)).

Formally, the above analysis can be written as: \[\label{eq:MLE-1} \begin{align} \Pr\Bigl[|H^* \setminus \hat{H}_{\mathrm{MLE}}| > \delta_n m\Bigr] &\le \Pr\Bigl[\exists H \in \mathcal{H}, |H^* \setminus H| > \delta_n m,\;L(H) > L(H^*)\Bigr]. \end{align}\tag{1}\] Since every graph in \(\mathcal{H}\) has \(m\) edges, \(|H^*\setminus H|=|H\setminus H^*|\). Define \(\mathcal{H}(H^*,\ell) := \{H:|H\setminus H^*| = \ell, H \in \mathcal{H}\}\). By the union bound, we have: \[\label{eq:MLE-Union} \begin{align} \Pr\Bigl[\exists H \in \mathcal{H}, |H^* \setminus H| > \delta_n m,\;L(H) > L(H^*)\Bigr] &\le \sum_{\ell=\lceil \delta_n m\rceil}^m \Pr\Bigl[\exists H \in \mathcal{H}(H^*,\ell): L(H) > L(H^*)\Bigr]. \end{align}\tag{2}\]

We defer this proof to 5.1.

Proof of the almost exact recovery upper bound in 1. Combining 1 , 2 and 3 , we have: \[\begin{align} \Pr\Bigl[|H^* \setminus \hat{H}_{\mathrm{MLE}}| > \delta_n m\Bigr] &\le \sum_{\ell = \lceil \delta_n m\rceil}^{m} \Pr\Bigl[\exists H \in \mathcal{H}(H^*,\ell): L(H) > L(H^*)\Bigr]\\ &\le \sum_{\ell = \lceil \delta_n m\rceil}^{\infty} \exp\left( -(1+o(1))\frac{\ell\eta}{4\epsilon_n}\right) + \exp\left( -\frac{\ell \eta}{4} \cdot \log(p_{1M}^{-1}) + o(\log M)\right)\\ &= \frac{\exp(- (1+o(1))\frac{\delta_n m \eta}{4\epsilon_n}) }{1 - \exp(-(1+o(1))\frac{\eta}{4\epsilon_n})} + \frac{\exp(-\frac{\delta_n m \eta\log(p_{1M}^{-1})}{4} + o(\log M))}{1 - \exp(-\frac{\eta\log(p_{1M}^{-1})}{4})} = o(1). \end{align}\] Thus, the MLE achieves almost exact recovery. 0◻

3 Information-theoretic recovery lower bounds↩︎

In this section, we use information-theoretic tools to analyze the necessary conditions for almost exact recovery and partial recovery. For uniformly sparse \(\mathcal{H}\), our lower bound for almost exact recovery coincides with the upper bound established in 2. For partial recovery, the performance varies significantly across different distributions. While some distributions exhibit a sharp AoN phase transition, some other distributions show a phenomenon where the maximum overlap aligns with our partial recovery lower bound, decreasing linearly with the KL divergence.

3.1 Almost exact recovery lower bound by distance-based Fano’s inequality↩︎

Our information-theoretic lower bound for almost exact recovery is based on an application of the distance-based Fano’s inequality. To do so, inference problems are typically modeled as follows: the parameter \(X\) is drawn randomly from a set \(\mathcal{X}\), the observation \(Y\) and the estimator \(\hat{X}\) form a Markov chain \(X \rightarrow Y \rightarrow \hat{X}\). The marginal distributions of \(X\) and \(Y\) are denoted by \(P_X\) and \(P_Y\), respectively, and their joint distribution is denoted by \(P_{XY}\).

More specifically, in our setting, \(\mathcal{X} = \mathcal{H}\) and the parameter \(X\) is a graph sampled uniformly at random from \(\mathcal{X}\), the observation \(Y\) is a weighted complete graph, where the edge weights in \(Y\) are generated conditionally on \(X\), such that edges in \(X\) i.i.d. follow distribution \(\mathcal{P}\), and all other edges i.i.d. follow \(\mathcal{Q}\).

We defer this proof to 5.2.

We defer this proof to 5.2.

Proof of the almost exact recovery lower bound in 1.

Combining 4 with 5 finishes the proof. 0◻

3.2 Partial recovery lower bound using Sibson’s \(\alpha\)-Mutual Information↩︎

The standard Fano’s inequality does not yield a strong enough converse bound. For example, when the mutual information between the parameter and the observation is only a constant fraction of the parameter’s entropy, the inequality can at best conclude that the probability of partial recovery is no more than another constant. Therefore, we need stronger measures than mutual information to capture the fundamental limits of recovery more precisely in the low-information regime.

In [25], the authors studied Sibson’s \(\alpha\)-mutual information and proposed Fano-type inequalities based on Sibson’s mutual information. We need a distance-based variant as follows:

We defer the proof to 5.3.

We defer the proof to 5.3.

Proof of the partial recovery lower bound in 1. Let \(\rho(X_1, X_2) = |X_1 \setminus X_2|\), by 2, for any uniformly sparse \(\mathcal{H}\), we have \[\begin{align} p^\star_{t} = \max_{H_1 \in \mathcal{H}} \sum_{\ell=m-t}^{m} \Pr_{H_2 \sim \mathcal{H}} [|H_1 \cap H_2| = \ell] &\le \sum_{\ell\ge m-t} \exp(-\ell \log(p_{1M}^{-1}) + o(\log M))\\ &\le \frac{\exp(-(m-t) \log(p_{1M}^{-1}) + o(\log M))}{1-\exp(-\log(p_{1M}^{-1}))}\\ &= \exp\left( - (m-t) \log(p_{1M}^{-1}) + o(\log M) \right). \end{align}\] Applying 4 and 5, the probability of recovering a \(\lambda\)-fraction of edges satisfies: \[\Pr[\rho(X, \hat{X}) \le (1-\lambda) m] \le \exp\left(\frac{\alpha-1}{\alpha}\left(-\lambda m \log(p_{1M}^{-1}) + o(\log M) + m D_\alpha(\mathcal{P} \| \mathcal{Q})\right)\right).\] If 2 holds, when \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \le (\lambda-\eta) \log(p_{1M}^{-1})\) for some constant \(\eta\), there exists a constant \(c > 0\) such that \(\alpha = 1 + \frac{c}{\log(p_{1M}^{-1})}\) satisfies \(\alpha\le \beta_n\), where \(\beta_n\) is the order from 2 with \(\theta=\frac{\eta/2}{\lambda-\eta}\). By monotonicity of Rényi divergence in its order, \[D_{\alpha}(\mathcal{P} \| \mathcal{Q}) \le \left(1+\frac{\eta/2}{\lambda-\eta}\right) D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \le (\lambda-\eta/2) \log(p_{1M}^{-1}).\] \[\begin{align} \implies \frac{\alpha-1}{\alpha} \left(-(1+o(1)) \lambda m \log(p_{1M}^{-1}) + m D_\alpha(\mathcal{P} \| \mathcal{Q})\right) &= \frac{cm (-\eta/2 + o(1))}{\alpha} \to -\infty, \end{align}\] which implies \(\Pr[\rho(X, \hat{X}) \le (1-\lambda) m] \to 0\) as \(n \to \infty\). Therefore, any algorithm designed to recover \(\lambda\) fraction of the hidden edges fails with high probability. 0◻

4 AoN under natural distributions↩︎

In this section, we present several sufficient conditions for AoN. While we analyzed the threshold for the ‘All’ phase in 2 and demonstrated its tightness at the exponential scale in 3.1, in this section we employ two distinct methods to provide sufficient conditions for the ‘Nothing’ phase. The first method generalizes the second moment method of [2]. The second one uses the I-MMSE relation for Gaussian to lift our almost exact recovery threshold to an AoN phenomenon. As a result, we are able to show AoN for several natural distributions, in addition to the Erdős-Rényi case studied in [2].

Before proceeding, we recall the definition of the minimum mean square error (MMSE). If we relax the recovery target from \(\hat{H} \in \mathcal{H}\) to \(\hat{X} \in \mathbb{R}^N\), let \(X_e := \mathbb{I}[e \in H^*],\;\forall e \in [N]\) and define the mean square error (MSE) as \(\mathrm{MSE}(\hat{X}) := \mathbb{E}[\|\hat{X} - X\|^2]\), then MSE is minimized when \(\hat{X}\) is chosen to be the conditional expectation \(\mathbb{E}[X \mid Y]\) and the MMSE is thus expressed as \[\mathrm{MMSE}:= \mathbb{E}\left[\|X - \mathbb{E}[X \mid Y]\|^2\right] = \mathbb{E}\left[\|X\|^2 - \langle X,\mathbb{E}[X \mid Y]\rangle\right] = \mathbb{E}\left[\|X\|^2\right] - \mathbb{E}\left[\|\mathbb{E}[X \mid Y]\|^2\right].\]

Intuitively, if MMSE is close to \(0\), one achieves almost exact recovery, while MMSE close to \(m\) means almost no recovery (Nothing). In the subsequent proof, we will use MMSE to demonstrate the hardness of recovery in terms of \(D_2\).

4.1 AoN under distributions with \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\)↩︎

We recall the Erdős-Rényi setting in [2]: the weight of every edge in the observed graph can only be \(0\) or \(1\), and only graphs where all edge weights are \(1\) have an identical non-zero posterior probability. Consequently, their partition function can be expressed as the number of graphs whose edge weights are all \(1\). By generalizing their definition of partition function to real-valued distributions, a similar second moment method remains applicable with respect to the second-order Rényi divergence \(D_2\). As discussed in 1, when \(D_2(\mathcal{P}\|\mathcal{Q}) = (1 + o(1)) D_{\mathrm{KL}}(\mathcal{P}\|\mathcal{Q})\), AoN occurs and it is visualized in 2.

As discussed earlier, the MMSE estimator is the posterior mean \(\mathbb{E}[X\mid Y]\). Here and below we identify a graph with its edge-incidence vector in \(\{0,1\}^N\). We will also use a posterior sample \(\hat{H}\sim \Pr[H\mid Y]\) as a convenient device; its conditional mean equals the posterior mean. In the hidden weighted model, the posterior distribution is proportional to the product of the likelihood ratios associated with the edges in the corresponding hidden structure: \[\Pr[\hat{H} \mid Y] = \frac{1}{Z(Y)} \prod_{e \in \hat{H}} \frac{\mathrm{d}\mathcal{P}}{\mathrm{d}\mathcal{Q}}(Y_e),\] where \(Z(Y)\) is the partition function \[Z(Y) := \sum_{H \in \mathcal{H}} \prod_{e\in H} \frac{\mathrm{d}\mathcal{P}}{\mathrm{d}\mathcal{Q}}(Y_e).\]

The following lemma can be viewed as a generalization of the second moment approach in Lemma 3.11 of [2] from Bernoulli inference model to general distributions through \(D_2\). Similar to contiguity arguments, we need to control a second moment, but we truncate the contribution from overlaps below \(o(m)\), since the uniformly sparse condition does not yield a useful upper bound on the overlap probability in this regime.

Proof of the “Nothing” recovery lower bound in 1.

By 2, for any constant \(\delta \in (0,1)\), \[\begin{align} \sum_{\ell \geq \delta m} \Pr_{H_1,H_2 \sim \mathcal{H}}[|H_1 \cap H_2| = \ell] \exp(\ell D_2(\mathcal{P}\|\mathcal{Q})) &\le \sum_{\ell \geq \delta m} \exp(\ell D_2(\mathcal{P}\|\mathcal{Q}) - \ell \log(p_{1M}^{-1}) + o(\log M))\\ &\le \sum_{\ell \geq \delta m} \exp((-\eta \ell+o(m)) \log(p_{1M}^{-1}))\\ &\le \frac{\exp((-\eta \delta m + o(m)) \log(p_{1M}^{-1}))}{1 - \exp(-\eta \log(p_{1M}^{-1}))} = o(1). \end{align}\] Applying 7, we have \(\mathbb{E}[\|\mathbb{E}[X|Y]\|^2] = m - \mathrm{MMSE}\le m (\delta + o(1))\). For any estimator \(\hat{X}\) satisfying \(\|\hat{X}\|^2 = m\), by Cauchy–Schwarz inequality, we have \[\mathbb{E}[X\cdot\hat{X}] = \mathbb{E}[\hat{X}\cdot \mathbb{E}[X\mid Y]] \le \sqrt{\mathbb{E}[\|\hat{X}\|^2]} \cdot \sqrt{\mathbb{E}[\|\mathbb{E}[X|Y]\|^2]} = m \sqrt{\delta + o(1)}.\] Thus, the expected overlap of any estimator satisfying \(\|\hat{X}\|^2=m\) is at most \(m \sqrt{\delta + o(1)}\). Since this holds asymptotically for any constant \(\delta\), Markov’s inequality implies that, for every fixed \(\lambda,\gamma>0\), choosing \(\delta\) sufficiently small gives \[\Pr[X\cdot \hat{X} \ge \lambda m]\le \gamma+o(1).\] Any graph estimator that outputs a member of \(\mathcal{H}\) can be identified with its edge-incidence vector \(\hat{X}\in\{0,1\}^N\); since every graph in \(\mathcal{H}\) has \(m\) edges, it satisfies \(\|\hat{X}\|^2=m\), and \(X\cdot\hat{X}=|H^*\cap \hat{H}|\). Therefore, graph estimators also satisfy the upper bound above. Hence no algorithm can recover any constant fraction of the edges with any constant probability.

4.2 AoN under Gaussian distributions↩︎

When \(\mathcal{P} = N(\mu, 1), \mathcal{Q} = N(0, 1)\), and \(\mu > 0\), we observe that \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) = \frac{1}{2} D_2(\mathcal{P} \| \mathcal{Q})\). In this case, the method presented above does not yield a tight threshold for the ‘Nothing’ phase. Intuitively, this is because there is insufficient concentration when the information approaches the threshold. Nevertheless, we can still prove the existence of AoN for all uniformly sparse \(\mathcal{H}\) using the Gaussian channel’s I-MMSE relation. Our proof has a similar flavor to the area-theorem style of establishing AoN in [27], while the I-MMSE relation allows us to establish the “Nothing” from “all” in a much more straightforward fashion.

In this setting, let \(\mathrm{snr}= \mu^2\) denote the signal-to-noise ratio. The signal can be represented as a vector \(X \in \mathbb{R}^N\), where \(X_e = \mathbb{I}[e \in H^*] \;\forall e \in [N]\), and the observation is \(Y = \sqrt{\mathrm{snr}} X + Z\), with noise \(Z\) being i.i.d. \(N(0, 1)\). The I-MMSE relation states that

Finally, we are ready to complete the proof of AoN under Gaussian distributions.

Proof of 3. Since the Gaussian distribution satisfies 1, the corresponding upper bound for recovery has been established in 1: almost exact recovery is achievable at \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \ge (1 + \eta) \log(p_{1M}^{-1})\) for any constant \(\eta > 0\). Then by 11, it follows that no algorithm can recover any constant fraction of the edges with any constant probability when \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) = (1 - \eta) \log(p_{1M}^{-1})\) for any constant \(\eta > 0\). The same impossibility holds below this value by monotonicity of the Gaussian channel in the signal-to-noise ratio.

Acknowledgements↩︎

We thank Tselil Schramm for their insightful discussions and helpful comments on the second moment approach. JL is supported by the National Natural Science Foundation of China under Grant No. 62472212.

5 Missing Proofs↩︎

5.1 Missing proofs of almost exact recovery upper bound↩︎

Let \(L=\frac{\mathrm{d}\mathcal{P}}{\mathrm{d}\mathcal{Q}}\). Since \(\mathcal{P}\ll \mathcal{Q}\), we have \(\mathcal{P}(L=0)=0\), so \(X=\log L\) is well-defined under \(\mathcal{P}\). Under \(\mathcal{Q}\), however, \(Y=\log L\) may take the value \(-\infty\). All log MGFs are understood in the extended-real sense. Define \[\label{eq:log-mgf} \begin{align} \psi_P(\lambda) &= \log \mathbb{E}_{\mathcal{P}} [e^{\lambda X}] = \log \int L^\lambda\,\mathrm{d}\mathcal{P},\\ \psi_Q(\lambda) &= \log \mathbb{E}_{\mathcal{Q}} [e^{\lambda Y}] = \log \int L^\lambda\,\mathrm{d}\mathcal{Q}. \end{align}\tag{8}\]

Define the Legendre transforms by \[\label{eq:log-mgf-legendre} \begin{align} E_P(\tau) = \sup_{\lambda\in\mathbb{R}}\{\lambda\tau-\psi_P(\lambda)\},\qquad E_Q(\tau) = \sup_{\lambda\in\mathbb{R}}\{\lambda\tau-\psi_Q(\lambda)\}. \end{align}\tag{9}\]

Since \(\psi_P(0)=\psi_Q(0)=0\), both \(E_P(\tau)\) and \(E_Q(\tau)\) are nonnegative. Let \(D=D_{\mathrm{KL}}(\mathcal{P}\|\mathcal{Q})=\mathbb{E}_{\mathcal{P}}[X]\). By Jensen’s inequality, \[\psi_P(\lambda) = \log \mathbb{E}_{\mathcal{P}}[e^{\lambda X}] \ge \lambda \mathbb{E}_{\mathcal{P}}[X] = \lambda D.\] Thus \(E_P(D)=0\). Moreover, if \(0\le\tau\le D\), then for every \(\lambda>0\), \[\lambda\tau-\psi_P(\lambda) \le \lambda(\tau-D) \le 0.\] Since \(\lambda=0\) gives value \(0\), positive \(\lambda\) cannot increase the supremum. Hence \[E_P(\tau) = \sup_{\lambda\le 0}\{\lambda\tau-\psi_P(\lambda)\}, \qquad 0\le\tau\le D.\]

Similarly, for \(E_Q\), take \(\lambda<0\). If \(\mathcal{Q}(L=0)>0\), then \(\mathbb{E}_{\mathcal{Q}}L^\lambda=+\infty\). Otherwise, whenever the expectation is finite, the function \(x\mapsto x^\lambda\) is convex on \((0,\infty)\), and Jensen’s inequality gives \[\mathbb{E}_{\mathcal{Q}}L^\lambda \ge (\mathbb{E}_{\mathcal{Q}}L)^\lambda = 1.\] Therefore \(\psi_Q(\lambda)\ge0\) for all \(\lambda<0\), in the extended-real sense. Hence for every \(\tau\ge0\), \[\lambda\tau-\psi_Q(\lambda)\le0 \qquad \text{for all } \lambda<0.\] Again \(\lambda=0\) gives value \(0\), so negative \(\lambda\) cannot increase the supremum. Therefore \[E_Q(\tau) = \sup_{\lambda\ge 0}\{\lambda\tau-\psi_Q(\lambda)\}, \qquad \tau\ge0.\] Applying Chernoff bound: for \(\ell\) i.i.d. random variables \(X_1, \dots, X_\ell\) drawn from the distribution \(\mathcal{X}\), and \(\ell\) i.i.d. random variables \(Y_1, \dots, Y_\ell\) drawn from the distribution \(\mathcal{Y}\), we have: \[\label{eq:xy-chernoff} \Pr \left[ \sum_{i=1}^{\ell} X_i \le \ell \tau \right] \le e^{-\ell E_P(\tau)}, \quad \Pr \left[ \sum_{i=1}^{\ell} Y_i \ge \ell \tau \right] \le e^{-\ell E_Q(\tau)}.\tag{10}\]

Recall that \(\mathcal{H}(H^*,\ell) := \{H:|H\setminus H^*| = \ell, H \in \mathcal{H}\}\), define \(\mathcal{H}^\mathrm{in}(H^*,\ell) := \{H^*\setminus H: H \in \mathcal{H}(H^*,\ell)\}\) and \(\mathcal{H}^\mathrm{out}(H^*,\ell) := \{H\setminus H^*: H \in \mathcal{H}(H^*,\ell)\}\). For any \(\tau \in [0,D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q})]\), by union bound we obtain: \[\label{eq:MLE-chernoff-expand} \begin{align} &\Pr[\exists H \in \mathcal{H}(H^*,\ell): L(H) > L(H^*)]\\ &\le \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}^\mathrm{in}(H^*,\ell)|] \Pr\left[ \sum_{i=1}^{\ell} X_i \le \ell \tau \right] + \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}^\mathrm{out}(H^*,\ell)|] \Pr\left[ \sum_{i=1}^{\ell} Y_i \ge \ell \tau \right]\\ &\le \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}^\mathrm{in}(H^*,\ell)|] e^{-\ell E_P(\tau)} + \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}^\mathrm{out}(H^*,\ell)|] e^{-\ell E_Q(\tau)}.\\ \end{align}\tag{11}\]

When \(\mathcal{H}\) is uniformly sparse, by 2, we have \[\label{eq:H-out-bound} \begin{align} \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}^\mathrm{out}(H^*,\ell)|] \le \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}(H^*,\ell)|] &\le M \Pr_{H_1,H_2 \sim \mathcal{H}}[|H_1 \cap H_2| = m-\ell]\\ &\le \exp(\ell \log(p_{1M}^{-1}) + o(\log M)). \end{align}\tag{12}\]

Let \(\delta_n \to 0\) to be decided later and for all \(\ell \ge \delta_n m\), we have \[\label{eq:H-in-bound} |\mathcal{H}^\mathrm{in}(H^*,\ell)| \le \binom{m}{\ell} \le \left(\frac{e m}{\ell}\right)^\ell \le \left( \frac{e}{\delta_n} \right)^\ell.\tag{13}\]

On the interval \([0,D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q})]\), the function \(E_Q(\tau)\) is nondecreasing in \(\tau\), while \(E_P(\tau)\) is nonincreasing. We will use the following choice of \(\tau\) and lower bound the two exponents separately.

When \(D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \ge (1+\eta) \log(p_{1M}^{-1})\), by 1 there exists a sequence \(\epsilon_n \to 0\), such that for \(\lambda = -\frac{1}{\epsilon_n \log(p_{1M}^{-1})}\), \[D_{1+\lambda}(\mathcal{P} \| \mathcal{Q}) \ge \left(1-\frac{\eta/2}{1+\eta}\right) D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) \ge (1+\eta/2) \log(p_{1M}^{-1}).\]

Setting \(\tau = (1 + \eta/4)\log(p_{1M}^{-1})\), then \[\label{eq:Ep-lower-bound} \begin{align} E_P(\tau) &\ge \lambda \tau - \psi_P(\lambda)\\ &= \lambda((1+\eta/4)\log(p_{1M}^{-1}) - D_{1+\lambda}(\mathcal{P} \| \mathcal{Q}))\\ &\ge \lambda (-\eta/4) \log(p_{1M}^{-1}) = \frac{\eta}{4 \epsilon_n},\\ E_Q(\tau) &\ge 1\cdot \tau - \psi_Q(1) = \tau = (1 + \eta/4) \log(p_{1M}^{-1}). \end{align}\tag{14}\] By combining 13 ,  12 and 14 , and setting \(\delta_n = \exp(-\sqrt{1/\epsilon_n})\), then we have, \[\label{eq:MLE-chernoff-final} \begin{align} \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}^\mathrm{in}(H^*,\ell)|] e^{-\ell E_P(\tau)} &\le \exp\left( \ell \log\left(\frac{e}{\delta_n}\right) - \frac{\ell \eta}{4 \epsilon_n}\right) \le \exp\left( -(1+o(1))\frac{\ell \eta}{4 \epsilon_n}\right),\\ \mathbb{E}_{H^* \sim \mathcal{H}}[|\mathcal{H}(H^*,\ell)|] e^{-\ell E_Q(\tau)} &\le \exp\left( \ell \log(p_{1M}^{-1}) + o(\log M) - \ell (1+\eta/4) \log(p_{1M}^{-1}) \right)\\ &\le \exp\left( -\frac{\ell \eta}{4} \cdot \log(p_{1M}^{-1}) + o(\log M)\right).\\ \end{align}\tag{15}\]

Substituting 15 into 11 finishes the proof. 0◻

5.2 Missing proofs of almost exact recovery lower bound↩︎

Proof of 2. If there exists an algorithm that achieves almost exact recovery, then there exist sequences \(\epsilon_n, \delta_n \to 0\) such that \(\Pr\left[|H^* \setminus \hat{H}| > \delta_n m\right] \le \epsilon_n\). We apply the distance-based Fano’s inequality [29] (restated as 12) with distance function \(\rho(X_1, X_2) = |X_1 \setminus X_2|\) and \(t = \delta_n m\). It remains to verify its condition \(|\mathcal{X}|-N_t^{\min}>N_t^{\max}\). By 2, \[\begin{align} N_t^{\max} &= \max_{H_1 \in \mathcal{H}} M \sum_{\ell=0}^{\delta_n m} \Pr_{H_2 \sim \mathcal{H}} [|H_1 \cap H_2| = m-\ell]\\ &\le \sum_{\ell=0}^{\delta_n m} \exp(\ell \log(p_{1M}^{-1}) + o(\log M))\\ &\le 2\exp(\delta_n m \log(p_{1M}^{-1}) + o(\log M)) = \exp(o(\log M)). \end{align}\] Since \(N_t^{\min}\le N_t^{\max}\), and \(\log M = m\log(p_{1M}^{-1}) \to \infty\), the estimate above implies \(N_t^{\max} = M^{o(1)} = o(M)\). Hence, for all sufficiently large \(n\), \[|\mathcal{X}|-N_t^{\min} = M-N_t^{\min} \ge M-N_t^{\max} > N_t^{\max},\] so 12 is applicable. Since \(P_t \le \epsilon_n\), rearranging gives \[\begin{align} I(X; Y) &\ge (1-\epsilon_n) \log \left( \frac{|\mathcal{H}|}{N_t^{\max}} \right) - \log 2\\ &= (1-\epsilon_n) \left(\log M - \log N_t^{\max}\right)-\log 2 = (1 - o(1)) \log M. \end{align}\] 0◻

Proof of 3. By definition, for any distribution \(Q_Y\) we have \[\begin{align} I(X;Y) &= \mathbb{E}_{P_{XY}} \left[ \log \frac{\mathrm{d} P_{Y|X}}{\mathrm{d} P_Y} \right] = \mathbb{E}_{P_{XY}} \left[ \log \frac{\mathrm{d} P_{Y|X} \mathrm{d} Q_Y}{\mathrm{d} Q_Y \mathrm{d} P_Y} \right] \\ &= \mathbb{E}_{P_{XY}} \left[ \log \frac{\mathrm{d} P_{Y|X}}{\mathrm{d} Q_Y} \right] - D_{\mathrm{KL}}(P_Y \| Q_Y) \leq \mathbb{E}_{P_X} \left[ D_{\mathrm{KL}}(P_{Y|X} \| Q_Y) \right]. \end{align}\] Let \(Q_Y = \mathcal{Q}^{\otimes N}\), which means the weight of every edge in \(Y\) is independently drawn from the distribution \(\mathcal{Q}\). For a fixed \(X\), the edge weights in the conditional distribution \(P_{Y|X}\) are mutually independent. By the additivity of KL divergence under product distributions, we have \(D_{\mathrm{KL}}(P_{Y|X} \| Q_Y) = m \cdot D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q})\). Then we get 5 . 0◻

5.3 Missing proofs of partial recovery lower bound↩︎

Proof of 4.

We build upon the framework established in Theorem 7.2 of [25], with a simple modification for the setting of distance-based recovery lower bounds.

Theorem 5.3 of [25] has shown that \[I_{\alpha}(X; Y) = \sup_{f: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}} \frac{\alpha}{\alpha - 1} \log \mathbb{E}_{P_{XY}} \left[ e^{(\alpha - 1) f(X, Y)} \right] - \log \mathbb{E}_{P_X Q_Y^*} \left[ e^{\alpha f(X, Y)} \right],\] where \(Q_Y^*\) is the distribution that minimizes the divergence \(D_{\alpha}(P_{XY} \| P_X Q_Y)\).

Consider \(\alpha > 1, \;\beta > 0\), and let \(f(X, \hat{X}) = \frac{\beta}{\alpha - 1} \mathbb{I}[\rho(X, \hat{X}) \le t]\). Define \(\hat{p} = \Pr_{P_{X \hat{X}}}[\rho(X, \hat{X}) \le t]\) and \(\hat{q} = \Pr_{P_X Q_{\hat{X}}^*}[\rho(X, \hat{X}) \le t]\). Since \(X\) and \(\hat{X}\) are independent in \(\hat{q}\), define \(p^\star_t := \max_x [\sum_{x': \rho(x,x') \le t} P_X(x')]\), then \(\hat{q} \leq p^\star_t\). Therefore, \[\begin{align} I_{\alpha}(X; Y) &\geq I_{\alpha}(X, \hat{X}) \\ &\geq \frac{\alpha}{\alpha - 1} \log \left( \hat{p} e^{\beta} + 1 - \hat{p} \right) - \log \left( \hat{q} e^{\frac{\alpha}{\alpha - 1} \beta} + 1 - \hat{q} \right) \\ &\geq \frac{\alpha}{\alpha - 1} \log \left( \hat{p} (e^{\beta} - 1) + 1 \right) - \log \left( p^\star_t e^{\frac{\alpha}{\alpha - 1} \beta} + 1 - p^\star_t \right). \end{align}\]

Setting \(\gamma = e^\beta - 1\), and rearranging terms yields \[\Pr[\rho(X, \hat{X}) \le t] \leq \frac{\left( p^\star_t (\gamma + 1)^{\frac{\alpha}{\alpha - 1}} + 1 - p^\star_t \right)^{\frac{\alpha - 1}{\alpha}} \exp \left\{ \frac{\alpha - 1}{\alpha} I_\alpha(X, Y) \right\} - 1}{\gamma}.\]

Taking \(\gamma \to +\infty\), we obtain \[\Pr[\rho(X, \hat{X}) \le t] \le \left( p^\star_t e^{I_\alpha(X;Y)} \right)^{\frac{\alpha-1}{\alpha}}.\] 0◻

Proof of 5. Let \(Q_Y = \mathcal{Q}^{\otimes N}\), which means the weight of every edge in \(Y\) is independently drawn from the distribution \(\mathcal{Q}\). Then, we have: \[\begin{align} I_{\alpha}(X; Y) \le D_{\alpha}(P_{XY} \| P_X Q_Y) &= \frac{1}{\alpha-1} \log \mathbb{E}_{P_{XY}} \left[ \left( \frac{\mathrm{d} P_{XY}}{\mathrm{d} P_X Q_Y} \right)^{\alpha - 1} \right]\\ &= \frac{1}{\alpha-1} \log \mathbb{E}_{P_X} \left[\exp\left( (\alpha-1) D_\alpha(P_{Y|X} \| Q_Y) \right)\right].\\ \end{align}\] For a fixed \(X\), the edge weights in the conditional distribution \(P_{Y|X}\) are mutually independent. By the additivity property of Rényi divergence under product distributions [30], we have \(D_\alpha(P_{Y|X} \| Q_Y) = m \cdot D_\alpha(\mathcal{P} \| \mathcal{Q})\). Substituting into the above equation finishes the proof. 0◻

6 First moment flat and uniformly sparse graph collections↩︎

We present two sufficient conditions for uniform sparsity.

6.1 First moment flat implies uniform sparsity↩︎

2 presents several graph collections that are first moment flat.

We need a few lemmas before proving this theorem.

The case \(\ell=0\) is trivial, since the probability is at most \(1\). For \(\ell\ge1\), set \(\lambda=\ell/m\). For first moment flat \(\mathcal{H}\), we have \(\log(p_{E}^{-1}) = (1+o(1)) \log(p_{1M}^{-1})\) and \(\log(p_{1M}^{-1})=\omega(1)\). By 13, \[\begin{align} \Pr_{H_2 \sim \mathcal{H}}[|H_1 \cap H_2| = \lambda m] &\le \exp\left(- \lambda m \log(p_E^{-1}) + 2 \lambda m \log (e/\lambda)\right)\\ &\le \exp\left(- (1+o(1))\lambda m \log(p_{1M}^{-1}) + 2 \lambda m + 2 m\right)\\ &= \exp\left(- \lambda m \log(p_{1M}^{-1}) + o(\log M)\right).\\ \end{align}\] Therefore \(\mathcal{H}\) is uniformly sparse. 0◻

6.2 Sufficiently large graph collections are uniformly sparse↩︎

We also consider non-isomorphic graph collections \(\mathcal{H}\) that are sufficiently large: these are \(\mathcal{H}\) that satisfy \(\log (p_{1M}^{-1}) = (1 + o(1)) \log (N/m) = \omega(1)\). 3 presents several graph collections that are sufficiently large (the asterisks indicate that they are also first moment flat).

For sufficiently large \(\mathcal{H}\) and distributions satisfying 1, we also show in 8 that a simple top-\(m\) selection based on the likelihood ratio recovers almost all hidden edges with high probability, if arbitrary \(m\)-edge subsets are allowed.

When \(\log (p_{1M}^{-1}) = (1+o(1)) \log (N/m)\), since \(\log M = m \log (p_{1M}^{-1})\), by 14, we have \[\begin{align} \Pr_{H_2 \sim \mathcal{H}}[|H_1 \cap H_2| = \lambda m] &\le \frac{1}{M} \exp \left( (1-\lambda)m \log (N/m) + (1+\log 2)m\right)\\ &\le \exp \left( -m \log(p_{1M}^{-1}) + (1-\lambda) m \log (N/m) + (1+\log 2)m \right)\\ &\le \exp \left( -\lambda m \log(p_{1M}^{-1}) + (1-\lambda)m(\log (N/m)- \log(p_{1M}^{-1})) + (1+\log 2)m \right)\\ &\le \exp \left( -\lambda m \log(p_{1M}^{-1}) + o(\log M) \right).\\ \end{align}\] Therefore \(\mathcal{H}\) is uniformly sparse. 0◻

7 Rényi Divergence Stability for common distributions↩︎

We briefly recall the definition of Rényi divergence. For \(\alpha \in (0,1) \cup (1,+\infty)\), the Rényi divergence is defined as \[D_\alpha\left( \mathcal{P} \| \mathcal{Q} \right):= \frac{1}{\alpha - 1} \log \int \left(\frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}}\right)^{\alpha} \mathrm{d} \mathcal{Q}.\] When \(\alpha = 1\), the Rényi divergence coincides with the KL divergence: \[D_1(\mathcal{P} \| \mathcal{Q}) := \lim_{\alpha \to 1} D_\alpha\left( \mathcal{P} \| \mathcal{Q} \right)= D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right).\] Under this definition, Rényi divergence is non-decreasing in \(\alpha\), and continuous in \(\alpha\) on the domain \([0, 1] \cup \left\{ \alpha \in (1, \infty] \mid D_\alpha\left( \mathcal{P} \| \mathcal{Q} \right)< \infty \right\}\) (see [30]).

Let \(\psi_Q\) be the log moment generating function (log MGF) of the random variable \(\log \frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}}\) under measure \(\mathcal{Q}\), defined in 8 then: \[D_\alpha\left( \mathcal{P} \| \mathcal{Q} \right)= \frac{1}{\alpha - 1} \psi_Q(\alpha).\] Using a Taylor expansion around \(\alpha = 1\), we obtain \[\psi_Q(\alpha) = \psi_Q(1) + \psi'_Q(1)(\alpha - 1) + \frac{1}{2} \psi''_Q(1)(\alpha - 1)^2 + o((\alpha - 1)^2),\] where \(\psi_Q(1) = 0\), \(\psi'_Q(1) = D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)\), and \(\psi''_Q(1) = \operatorname{Var}_{\mathcal{P}}[\log \frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}}]\). This yields the approximation \[D_\alpha\left( \mathcal{P} \| \mathcal{Q} \right)= D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)+ \frac{1}{2}(\alpha - 1) \operatorname{Var}_{\mathcal{P}}\left[\log \frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}}\right] + o(\alpha - 1).\] However, in our setting, each \(n\) corresponds to a pair of distributions \((\mathcal{P}_n, \mathcal{Q}_n)\), so a non-asymptotic bound is required. Intuitively, the Taylor expansion suggests that 1 is consistent with \(\operatorname{Var}_{\mathcal{P}}[\log \frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}}] = o(D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)^2)\), while 2 is consistent with \(\operatorname{Var}_{\mathcal{P}}[\log \frac{\mathrm{d} \mathcal{P}}{\mathrm{d} \mathcal{Q}}] = O(D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)^2)\).

7.1 Bernoulli distributions↩︎

By definition, the KL divergence and Rényi divergence between two Bernoulli distributions are given respectively by: \[\begin{align} D_{\mathrm{KL}}\left( \mathrm{Bern}(p) \| \mathrm{Bern}(q) \right)&= p \log \frac{p}{q} + (1-p) \log \frac{1-p}{1-q},\\ D_\alpha\left( \mathrm{Bern}(p) \| \mathrm{Bern}(q) \right)&=\frac{1}{\alpha-1} \log \left[ p^\alpha q^{1-\alpha}+(1-p)^\alpha (1-q)^{1-\alpha} \right]. \end{align}\]

7.1.1 \(\mathcal{P} = \mathrm{Bern}(1),\;\mathcal{Q} = \mathrm{Bern}(q)\)↩︎

In this case, \[D_{\mathrm{KL}}(\mathrm{Bern}(1)\|\mathrm{Bern}(q)) = D_{\alpha}(\mathrm{Bern}(1)\|\mathrm{Bern}(q)) = -\log q.\] It is evident that 1 and 2 hold.

7.1.2 \(\mathcal{P} = \mathrm{Bern}(p),\;\mathcal{Q} = \mathrm{Bern}(q)\) with fixed \(p \in (0,1)\) and \(D_{\mathrm{KL}}\left( \mathrm{Bern}(p) \| \mathrm{Bern}(q) \right)\to\infty\)↩︎

In this case we can only verify that 2 holds:

7.2 Gaussian distributions↩︎

By definition, the KL divergence and Rényi divergence between two Gaussian distributions are given respectively by: \[\begin{align} D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)&= \frac{\mu^2}{2},\\ D_\alpha\left( N(\mu,1) \| N(0,1) \right)&= \frac{\alpha \mu^2}{2}. \end{align}\]

For 1, take \(\alpha_n = 1 - D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)^{-1/2}\); for 2, take \(\beta_n = 1 + D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)^{-1/2}\). In both cases, the order parameter tends to \(1\) and its distance from \(1\) is \(\omega(1/D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right))\). Moreover, for any \(\alpha \in \{\alpha_n,\beta_n\}\), \[\begin{align} \Bigl|D_\alpha\left( N(\mu,1) \| N(0,1) \right)- D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)\Bigr| &= \frac{\mu^2}{2} |\alpha-1|\\ &= D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)^{1/2}\\ &= o(D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)). \end{align}\] We have \(D_\alpha\left( N(\mu,1) \| N(0,1) \right)= (1+o(1)) D_{\mathrm{KL}}\left( N(\mu,1) \| N(0,1) \right)\), which satisfies 1 and 2.

7.3 Exponential distributions↩︎

By definition, the KL divergence and Rényi divergence between two Exponential distributions are given respectively by: \[\begin{align} D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)&= \frac{\lambda_2}{\lambda_1} + \log\left(\frac{\lambda_1}{\lambda_2}\right) - 1,\\ D_\alpha\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)&= \frac{1}{\alpha - 1} \left[ \alpha \log\left( \frac{\lambda_1}{\lambda_2} \right) - \log\left( \alpha \frac{\lambda_1}{\lambda_2} + 1 - \alpha \right) \right].\\ \end{align}\] Since the exponential distribution is invariant under scaling up to a change in the rate parameter, without loss of generality, we can set \(t = \lambda_1 / \lambda_2\), then \[\begin{align} D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)&= \frac{1}{t} + \log t - 1,\\ D_\alpha\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)&= \frac{1}{\alpha - 1} \left[ \alpha \log (t) - \log\left( \alpha t + 1 - \alpha \right) \right].\\ \end{align}\]

7.3.1 \(\mathcal{P} = \mathrm{Exp}(\lambda_1),\;\mathcal{Q} = \mathrm{Exp}(\lambda_2)\) with \(\lambda_1 \gg \lambda_2\)↩︎

When \(t \gg 1\), \(D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)= (1+o(1)) \log t\), we will show that 1 and 2 holds:

For 1, take \(\alpha_n = 1-D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)^{-1/2}\); for 2, take \(\beta_n = 1+D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)^{-1/2}\). In both cases, the order parameter tends to \(1\) and its distance from \(1\) is \(\omega(1/D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right))\). Moreover, for any \(\alpha \in \{\alpha_n,\beta_n\}\), we have \(\left| h''(\xi) \right| = \frac{(1+o(1)) t^2}{(1+o(1)) t^2} = 1+o(1)\). Thus, there exists a constant \(c > 0\) such that \(\left| h''(\xi) \right| \leq c\), and \[\begin{align} \Bigl|D_\alpha\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)- D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)\Bigr| &\le c \cdot |\alpha - 1| = o(1).\\ \end{align}\] Therefore we have \(D_\alpha\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)= (1+o(1)) D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)\), which satisfies 1 and 2.

7.3.2 \(\mathcal{P} = \mathrm{Exp}(\lambda_1),\;\mathcal{Q} = \mathrm{Exp}(\lambda_2)\) with \(\lambda_1 \ll \lambda_2\)↩︎

When \(t \ll 1\), \(D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)= (1+o(1)) \frac{1}{t}\), we will show that 2 holds.

Let \(\alpha_n = 1 + \frac{c}{D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)}\), where \(c \in (0,\frac{1}{2})\) is a constant, then \[\begin{align} \frac{1}{2}|h''(\xi)| \le \frac{(t - 1)^2}{2\left( t - \delta |t - 1| \right)^2} &\le \frac{1}{2\left( t - \delta |t - 1| \right)^2} = \frac{1}{2\left( (1-c+o(1)) t \right)^2}\\ &\le (1+o(1)) \frac{1}{t^2} = (1+o(1)) \left[ D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)\right]^2. \end{align}\] Therefore, there exists a constant \(d > 0\) such that \[\begin{align} D_\alpha\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)&\le D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)+ d D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)^2 \cdot (\alpha-1).\\ \end{align}\] For any constant \(\theta > 0\), we can set \(c = \min\{\theta/d,1/4\}\), then \[D_\alpha\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right)\le (1+\theta) D_{\mathrm{KL}}\left( \mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2) \right).\]

7.4 Distributions with \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\)↩︎

We show that for \(\mathcal{P}=\mathrm{Bern}(1-o(1)),\;\mathcal{Q}=\mathrm{Bern}(o(1))\), and \(\mathcal{P}=\mathrm{Exp}(\lambda_1),\;\mathcal{Q}=\mathrm{Exp}(\lambda_2)\) with \(\lambda_1 \gg \lambda_2\), we have \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\).

7.4.1 \(\mathcal{P}=\mathrm{Bern}(1-o(1)),\;\mathcal{Q}=\mathrm{Bern}(o(1))\)↩︎

Intuitively, this can be seen as an extension to the planted Erdős-Rényi random graph model. Roughly speaking, in a standard planted model, the planted graph will always be a subgraph (corresponding to \(\mathcal{P}=\mathrm{Bern}(1)\)), while in our setting, we have to also consider the planted subgraph may undergo a random edge removal process. So an AoN in this case can be seen as an extension to [2].

We verify \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\) next.

\[\begin{align} D_{\mathrm{KL}}(\mathrm{Bern}(p) || \mathrm{Bern}(q)) &= p \ln \left( \frac{p}{q} \right) + (1-p) \ln \left( \frac{1-p}{1-q} \right) = - (1+o(1)) \log q,\\ D_2(\mathrm{Bern}(p) || \mathrm{Bern}(q)) &= \ln \left( \frac{p^2}{q} + \frac{(1-p)^2}{1-q} \right) = - (1+o(1)) \log q. \end{align}\]

7.4.2 \(\mathcal{P}=\mathrm{Exp}(\lambda_1),\;\mathcal{Q}=\mathrm{Exp}(\lambda_2)\) with \(\lambda_1 \gg \lambda_2\)↩︎

This setting was studied previously for almost exact recovery of planted matchings ([18], [19]) and spanning trees and Hamiltonian paths/cycles ([24]).

We verify \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\) next. \[\begin{align} D_{\mathrm{KL}}(\mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2)) &= \ln \left( \frac{\lambda_1}{\lambda_2} \right) + \frac{\lambda_2}{\lambda_1} - 1 = \ln \left( \frac{\lambda_1}{\lambda_2} \right)-1+o(1),\\ D_2(\mathrm{Exp}(\lambda_1) \| \mathrm{Exp}(\lambda_2)) &= \ln \left( \frac{\lambda_1^2}{2\lambda_1\lambda_2 - \lambda_2^2} \right) = \ln \left( \frac{\lambda_1}{\lambda_2} \right) - \ln(2) + o(1). \end{align}\] Therefore, the Bernoulli regime above and the exponential regime with \(\lambda_1 \gg \lambda_2\) both satisfy \(D_{2}= (1+ o(1)) D_{\mathrm{KL}}\).

7.5 Assumption 2 of [1] implies our 1↩︎

In Assumption 2 of [1], the authors stated the following assumption (with notation slightly modified to avoid conflicts):

where \(E_P\) is the Legendre transform defined in 9 , and \(D(P_n|Q_n)\) denotes \(D_{\mathrm{KL}}(P_n\|Q_n)\) in the notation of [1]. For \(\tau=(1-\theta)D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)\in [0,D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)]\), convexity gives \(E_P(\tau)=\sup_{\lambda\le0}\{\lambda\tau-\psi_P(\lambda)\}\), and Jensen’s inequality rules out \(\lambda<-1\) from improving over the value at \(\lambda=0\). Hence \(E_P(\tau)=\sup_{\lambda\in[-1,0]}\{\lambda\tau-\psi_P(\lambda)\}\). Therefore, by this assumption, after reducing \(c\) by a constant factor if necessary, for any \(\theta \in [0,1]\) there exists a \(\lambda \in [-1,0)\) satisfying \[\lambda \left((1 - \theta) D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)- D_{1+\lambda}(\mathcal{P} \| \mathcal{Q})\right) \geq c \theta^2 D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right).\] By the monotonicity of Rényi divergence in its order and \(\lambda<0\), we have \(D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)\ge D_{1+\lambda}(P_n \| Q_n) > (1 - \theta) D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)\). Moreover, \[-\lambda \ge \frac{c \theta^2 D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)}{\theta D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)} = c \theta.\] For any fixed \(\theta_0>0\), set \(\theta_n=D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)^{-1/2}\) and let \(\lambda_n<0\) be the order shift obtained above with \(\theta=\theta_n\). Let \(\alpha_n=1-(c/2)\theta_n\). Then \(\alpha_n\to 1\), \(1-\alpha_n=\omega(1/D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right))\), and \(\alpha_n\ge 1+\lambda_n\) for all sufficiently large \(n\). By monotonicity of Rényi divergence, \[D_{\alpha_n}(\mathcal{P}\|\mathcal{Q})\ge D_{1+\lambda_n}(\mathcal{P}\|\mathcal{Q})\ge (1-\theta_n)D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)\ge (1-\theta_0)D_{\mathrm{KL}}\left( \mathcal{P} \| \mathcal{Q} \right)\] for all sufficiently large \(n\). This implies that 1 holds.

8 Almost all hidden edges by top-\(m\) selection for sufficiently large \(\mathcal{H}\)↩︎

9 Tightness of the Partial Recovery Lower Bound↩︎

Proof of 2.

For any constant \(0 < \lambda < 1\), take \(\mathcal{H}\) to be the collection of all \(m\)-edge subgraphs of \(K_n\) with \(m=o(N)\) and \(m\to\infty\). Let \(\mathcal{P} = \mathrm{Bern}(\lambda),\mathcal{Q} = \mathrm{Bern}\left(\frac{(1-\lambda) m}{N-m}\right)\). We will demonstrate that this distribution is tight for the partial recovery lower bound in 3.2.

First we calculate the KL divergence: \[D_{\mathrm{KL}}(\mathcal{P} \| \mathcal{Q}) = \lambda \log \frac{\lambda}{\frac{(1-\lambda) m}{N-m}} + (1-\lambda) \log \frac{1-\lambda}{1 - \frac{(1-\lambda) m}{N-m}} = (1+o(1)) \lambda \log (N/m).\] This distribution also satisfies 2, which is proven in 7.1.2.

Next, we demonstrate that it is possible to recover a \(\lambda + o(1)\) fraction of edges in the hidden \(m\)-subgraph model, which satisfies the uniformly sparse condition and it is easier to analyze because under this model, any subgraph with \(m\) edges is a valid hidden subgraph.

In the \(m\)-subgraph model, the inference task can be described as follows: let \(X_1, \dots, X_m\) be i.i.d. samples drawn from distribution \(\mathcal{P}\), and \(Y_1, \dots, Y_{N - m}\) be i.i.d. samples drawn from distribution \(\mathcal{Q}\). Given the mixture of these \(N\) samples (with their indices randomly permuted), the goal is to select a subset of \(m\) indices such that at least a \(\lambda + o(1)\) fraction of the selected elements originate from the \(\mathcal{P}\)-distributed set.

Define \(X := \sum_{i=1}^m X_i\), \(Y := \sum_{j=1}^{N-m} Y_j\). Then \(\mathbb{E}[X] = \lambda m\), \(\mathbb{E}[Y] = (1 - \lambda)m\). We consider the following recovery strategy:

• If the total number of one-indices (i.e., \(X + Y\)) is less than \(m\), we select all available one-indices and fill the remaining \(m - (X + Y)\) positions arbitrarily with zero-indices. In this case, the number of correctly recovered \(\mathcal{P}\)-samples is at least \(X\).

• If \(X + Y \geq m\), we select any \(m\) one-indices. Since at most \(Y\) one-indices come from \(\mathcal{Q}\), the number of correctly recovered indices is at least \(m - Y\).

Hence, in either case, the number of correctly recovered indices is at least \(\min(X, m - Y)\). Using Chernoff bound, we have \[\begin{align} \Pr[|X - \mathbb{E}[X]| \ge \delta \mathbb{E}[X]] &\le 2 \exp\left(-\frac{\delta^2}{3} \cdot \mathbb{E}[X]\right),\\ \Pr[|Y - \mathbb{E}[Y]| \ge \delta \mathbb{E}[Y]] &\le 2 \exp\left(-\frac{\delta^2}{3} \cdot \mathbb{E}[Y]\right). \end{align}\] Setting \(\delta = m^{-1/3}\), we have \[\Pr[\min(X, m - Y) \le \lambda m - m^{2/3}] \le 4 \exp\left(-\frac{\min(\lambda, 1-\lambda)}{3} \cdot m^{1/3}\right).\] This implies that we can recover a \((1 + o(1))\lambda\) fraction of the hidden \(m\)-subgraph with high probability. Moreover, 3.2 shows that no fixed fraction strictly larger than \(\lambda\) can be recovered with high probability under this scaling.

10 Expectation threshold for \(2k\)-NN graphs↩︎

[1] established the almost exact recovery threshold for the \(2k\)-nearest-neighbor (\(2k\)-NN) graph. As noted in 2, the \(2k\)-NN graph is first-moment flat, which makes 1 applicable. Here we formally verify first-moment flatness by proving an upper bound on its expectation threshold.

We provide an upper bound on the stronger notion of the “modified subgraph expectation threshold”. Let \(M_{H',H}\) denote the number of subgraphs of \(H\) which are isomorphic copies of \(H'\), define \[\tilde{p}_E(H) = \min \left\{ p : \mathbb{E} M_{H', G(n, p)} \geq \frac{M_{H', H}}{2} \text{ for all edge induced subgraph } H' \subseteq H \right\}.\]

By definition, it is clear that \(p_E \le \tilde{p}_E\), in fact,  [32] established that \(p_c(H) \leq L \tilde{p}_E(H) \log e(H)\) for a universal constant \(L\).

In the remainder of this section, we follow the same convention and use “subgraph” to only refer to edge-induced subgraphs associated with a subset of edges, and simply write \(H'\subseteq H\). In particular, \(H'\) does not contain isolated vertices.

Combining [lem:PC-bound,lem:PC-bound-kNN] with \(\Delta=2k\) gives \[\tilde{p}_E(H) \le n^{-(1+o(1))/k}.\] Since \(p_E(H)\le \tilde{p}_E(H)\), we have \[\log(p_E(H)^{-1}) \ge (1+o(1))\frac{\log n}{k}.\] On the other hand, \(p_E(H)\ge p_{1M}(H)\) by definition, and for the \(2k\)-NN graph \(p_{1M}(H)=(1+o(1))(e/n)^{1/k}\). Hence \[\log(p_E(H)^{-1}) = (1+o(1))\frac{\log n}{k} = (1+o(1))\log(p_{1M}(H)^{-1}).\] Therefore, the \(2k\)-NN graph is first moment flat.

References↩︎

---

1. Accepted for presentation at the Conference on Learning Theory (COLT) 2026.↩︎