The Limits of Recovering Planted Subgraphs

Abstract

Given an arbitrary subgraph H = Hₙ and p = pₙ ∈ (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* of H, together with random noise in the form of an instance of an Erdős–Rényi graph ´ G(n, p). Their goal is to then recover the planted 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*, as a function of p and H, for large n. A recent paper [MNS⁺23] characterizes the graphs for which the limiting (as n grows) MMSE curve undergoes a sharp phase transition from 0 to 1 as p increases, a behavior known as the all-or-nothing phenomenon, up to a mild density assumption on 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ₙ, up to the same mild density assumption. This curve is expressed in terms of a variational formula over pairs of subgraphs of H, and is inspired by the celebrated subgraph expectation thresholds from probabilistic combinatorics [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 when n is large. The proof relies on a novel graph decomposition of 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] of a monotone property and a random Ber(p)^⊗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 n.