The Fundamental Limits of Recovering Planted Subgraphs

Daniel Z. Lee ∘ and Francisco Pernice ∘ and Amit Rajaraman ∘ and Ilias Zadik † · 2025

Read The Fundamental Limits of Recovering Planted Subgraphs by Daniel Z. Lee ∘ and Francisco Pernice ∘ and Amit Rajaraman ∘ and Ilias Zadik † (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15723.txt.

Introduction

Daniel Lee, Francisco Pernice, Amit Rajaraman, and Ilias Zadik study a basic limit in network data analysis. A hidden shape, a planted subgraph, is buried inside a random graph full of noise. The question is how well anyone could recover the planted shape, even with the best possible method.

The authors focus on the minimum mean squared error as graphs grow large. Earlier work covered only cases where recovery jumps sharply from hopeless to perfect. Here they give a formula for the full error curve for any planted graph, written as an optimization over pairs of its subgraphs. They also show the best choices can be described fast enough to compute. The result extends to planted yes-no properties in random noise.

Catalog record

CREATORDaniel Z. Lee ∘ and Francisco Pernice ∘ and Amit Rajaraman ∘ and Ilias Zadik †
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-15723

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Fundamental Limits of Recovering Planted Subgraphs Thanks: ∘ CSAIL, Massachusetts Institute of Technology; † Department of Statistics and Data Science, Yale University. Email: {lee_d,fpernice,amit_r}@mit.edu, [email protected] Daniel Z. Lee ∘ and Francisco Pernice ∘ and Amit Rajaraman ∘ and Ilias Zadik † Abstract . Given an arbitrary subgraph H = H n H=H_{n} and p = p n ∈ ( 0 , 1 ) p=p_{n}\in(0,1) , the planted subgraph model is defined as follows. A statistician observes the union of the “signal,” which is a random “planted” copy H ∗ H^{*} of H H , together with random noise in the form of an instance of an Erdős–Rényi graph G ⁡ ( n , p ) G(n,p) . Their goal is to then recover the planted H ∗ H^{*} from the observed graph. Our focus in this work is to understand the minimum mean squared error (MMSE), defined in terms of recovering the edges of H ∗ H^{*} , as a function of p p and H H , for sufficiently large n n . A recent paper [ MNS+23 ] characterizes the graphs for which the limiting (as n n grows) MMSE curve undergoes a sharp phase transition from 0 0 to 1 1 as p p increases, a behavior known as the all-or-nothing phenomenon, up to a mild density assumption on H H . However, their techniques fail to describe the MMSE curves for graphs that do not display such a sharp phase transition. In this paper, we provide a formula for the limiting MMSE curve for any graph H = H n H=H_{n} , up to the same mild density assumption. This curve is expressed in terms of a variational formula over pairs of subgraphs of H H , and is inspired by the celebrated subgraph expectation thresholds from the probabilistic combinatorics literature [ KK07 ] . Furthermore, we give a polynomial-time description of the optimizers of this variational problem. This allows one to efficiently approximately compute the MMSE curve for any dense graph H H when n n is large enough. The proof relies on a novel graph decomposition of H H as well as a new minimax theorem which may be of independent interest. Our results generalize to the setting of minimax rates of recovering arbitrary monotone boolean properties planted in random noise, where the statistician observes the union of a planted minimal element A ⊆ [ N ] A\subseteq[N] of a monotone property and a random Ber ⁡ ( p ) ⊗ N \operatorname{Ber}(p)^{\otimes N} vector. In this setting, we provide a variational formula inspired by the so-called “fractional” expectation threshold [ Tal10 ] , again describing the MMSE curve (in this case up to a multiplicative constant) for large enough n n . August 9, 2026 1. Introduction Over the past two decades, several influential papers have addressed the limiting (normalized) minimum mean squared error (MMSE) in high-dimensional statistical models, including [ DMK+16 , LM17 , MT06 , RP19 ] among others. In this paper, we focus on understanding the limiting MMSE in the fundamental problem of recovering planted discrete structures from noisy random environments. A motivating example: planted clique. A very well-studied discrete high-dimensional model is the planted clique model, initially defined independently by Jerrum [ Jer92 ] and Kučera [ Kuč95 ] . To define it, we need two parameters, k=k_{n}\in\mathbb{N} and p=p_{n}\in(0,1) . We assume that the statistician observes the union of a “signal,” which is a k -clique chosen uniformly at random from the complete graph K_{n} , and the “noise,” which is an instance of an Erdős–Rényi graph G(n,p) . The goal of the statistician is to recover the planted clique from the observed graph. It should be noted that there is a large body of work dedicated to understanding the special case where p=1/2 and k=O(\sqrt{n}) . However, it is beneficial for us here to consider the more general case where k=k_{n} and p=p_{n} can scale arbitrarily with n . This generality has recently proven useful in circuit lower bounds [ GMZ23 ] and low-degree lower bounds [ YZZ24 ] , among others. The planted clique model has been studied extensively due to its conjectured computational hardness in certain regimes, and has interesting implications for other high-dimensional statistical models (see, e.g., [ BBH18 ] and references therein). From a purely statistical perspective, [ MNS+23 ] recently computed the limiting MMSE of the model as n grows to infinity, proving that it converges to a step function, a behavior known as the All-or-Nothing (AoN) phenomenon (initially discovered in the context of Gaussian sparse regression, first conjectured to hold in [ GZ22 ] and proven in [ RXZ20 ] ). The planted subgraph model. Motivated by the extensive study of models similar to the planted clique model, such as the planted matching model [ MMX21 , DWXY23 ] and the planted dense subgraph model [ DMW25 ] , the authors of [ MNS+23 ] initiated the study of the limiting MMSE for general planted subgraphs (also independently introduced in [ Hul22 ] and [ ABI+23 ] by the cryptography community). To define this model, for each n\in\mathbb{N} , fix any (unlabeled) subgraph H=H_{n} of the complete graph K_{n} and some p=p_{n}\in(0,1) . Next, draw a uniformly random copy H^{*} of H in the complete graph. The statistician observes the graph G on n vertices which is the edge union of the “signal” H^{*} with “noise,” which is an instance of G_{0}\sim G(n,p), i.e., G=H^{*}\cup G_{0} . It is easy to verify that this more general model subsumes the problems of planted clique and planted perfect matching as special cases. Following [ MNS+23 ] , the main object of interest for us is the (normalized) MMSE of the model, defined as (1.1) \mathrm{MMSE}_{n}(p)=\frac{1}{|H|}\min_{\hat{A}}\mathbb{E}\left[\|\mathbf{1}_{H^{*}}-\hat{A}(G)\|^{2}_{2}\right]=\frac{1}{|H|}\mathbb{E}\left[\|\mathbf{1}_{H^{*}}-\mathbb{E}[\mathbf{1}_{H^{*}}|G]\|^{2}_{2}\right], where by \mathbf{1}_{H^{*}} we refer the indicator vector of the edges of H^{*} , \mathbf{1}_{H*}\in\{0,1\}^{\binom{n}{2}} 1 1 1 Throughout the paper we identify a graph H with its edge set. Hence, by J\subseteq H we refer to the edge-induced subgraph J of H . Moreover, note that the MMSE ( 1.1 ) in the planted subgraph model is measured in terms of number of edges recovered. . Observe that \operatorname{MMSE}_{n}(p)\in[0,1] , since the trivial estimator \hat{A}=0 attains mean squared error 1 . The main result of [ MNS+23 ] is that for any ‘‘weakly dense’’ 2 2 2 This result concerns graphs H with |H| edges and v(H) vertices that satisfy |H|=\omega(v(H)\log v(H)). H=H_{n}, the planted subgraph model for H=H_{n} satisfies the AoN phenomenon (i.e., the MMSE converges to a step function) if and only if the graph H is balanced, in that \max_{J\subseteq H}\frac{|J|}{v(J)}=\frac{|H|}{v(H)}. 3 3 3 Technically, [ MNS+23 ] proves this equivalence for an asymptotic definition of balancedness, but we omit the details for the introduction. The main goal of this paper is to go beyond the AoN phenomenon, and characterize the MMSE curve for an arbitrary weakly dense H , for sufficiently large n . Kahn–Kalai thresholds and Bayesian approaches. An easy application of Bayes’ rule shows that the posterior distribution of the planted subgraph model is the uniform distribution among all the copies of H=H_{n} in the observed graph G=H^{*}\cup G_{0},G_{0}\sim G(n,p)

Read the complete text