Technical Summary: Recovery of Planted Subgraphs

Problem Setup

This paper investigates the fundamental limits of recovering an arbitrary planted subgraph $\Gamma_n$ embedded within a dense Erdős–Rényi random graph $G(n, q_n)$. The model, denoted $G_{\Gamma_n}(n, p_n, q_n)$, generates a graph where edges within a hidden copy $\Gamma_n^*$ appear with probability $p_n$, while all other edges appear with probability $q_n$, where $q_n < p_n \leq 1$. The edge probabilities are fixed constants (the dense regime).

The primary inferential task is exact recovery: given an observed graph $G$, the goal is to identify the precise vertex set and edge structure of the planted subgraph $\Gamma_n^*$ with high probability as $n \to \infty$. The paper analyzes both the statistical limits (what is possible with unlimited computational power) and the computational limits (what is achievable by polynomial-time algorithms).

Methodology and Key Concepts

1. Onion Decomposition and Minimal Maximum Subgraph Density

A central contribution of the paper is the introduction of a structural characterization of the planted subgraph $\Gamma_n$ to determine recovery thresholds. The authors utilize the onion decomposition, a concept recently introduced in [LPRZ25], which iteratively peels off subgraphs layer by layer.

• Process: Starting with an empty set, the algorithm iteratively selects the maximal subgraph $H$ that maximizes the relative density $\eta(H | \Gamma^{(\ell-1)})$ among all extensions of the current layer.
• Key Quantity: The analysis hinges on a new graph-theoretic quantity termed the minimal maximum subgraph density, denoted $\mu_{\min}(\Gamma_n)$. This is defined as the maximum subgraph density of the final (and thus minimal) layer in the onion decomposition.
  $$\mu_{\min}(\Gamma_n) \triangleq \min_{S \subseteq \Gamma_n} \max_{S \subsetneq F \subseteq \Gamma_n} \eta(F|S)$$
  Intuitively, this quantity captures the "weakest link" in the subgraph's structure regarding density relative to its surroundings.

2. Statistical Analysis

The statistical limits are derived using information-theoretic tools, specifically Fano's inequality combined with a genie-aided argument.

• Lower Bound: The authors show that if $\mu_{\min}(\Gamma_n)$ is below a threshold proportional to $\frac{\log n}{d_{KL}(p||q)}$, exact recovery is statistically impossible. The proof involves revealing all but the final layer of the onion decomposition to the estimator and showing that the remaining uncertainty is too high.
• Upper Bound: A recursive peeling Maximum Likelihood Estimator (MLE) is proposed. This algorithm recovers the subgraph layer by layer, starting from the densest layer. The paper proves that if $\mu_{\min}(\Gamma_n)$ exceeds the threshold, this estimator achieves exact recovery with high probability.

3. Computational Analysis

For polynomial-time recovery, the paper employs two main frameworks:

• Convex Relaxation (Upper Bounds): The authors propose a computationally efficient algorithm based on Semidefinite Programming (SDP). This method relaxes the MLE by optimizing over a convex set of matrices, constrained by the nuclear norm of a diagonally shifted adjacency matrix. The success of this algorithm depends on the rank and coherence of the planted subgraph's adjacency matrix.
• Low-Degree Polynomial (LDP) Framework (Lower Bounds): To establish computational hardness, the paper adopts the low-degree polynomial framework from [SW22]. This framework tests whether any polynomial of degree $D = O(\log n)$ can correlate with the planted signal. The authors derive bounds showing that if the average density $\eta(\Gamma_n)$ is significantly smaller than $\sqrt{n}$, low-degree polynomials fail to recover the subgraph, even in a weak sense.

Key Results

1. Statistical Thresholds

The paper establishes a sharp statistical threshold for exact recovery in the dense regime:

• Impossibility: Exact recovery is statistically impossible if $\mu_{\min}(\Gamma_n) \leq (1-\epsilon) \frac{\log n}{d_{KL}(p||q)}$.
• Possibility: Exact recovery is possible (via the peeling MLE) if $\mu_{\min}(\Gamma_n) \geq C(1+\epsilon) \frac{\log n}{d_{KL}(p||q)}$.
• Implication: This result generalizes known thresholds for specific structures (e.g., planted cliques, where $\mu_{\min} \approx k/2$) to arbitrary subgraphs. It highlights that subgraphs with a dense core and a sparse appendage (e.g., a "kite" graph) may be statistically impossible to recover exactly because the sparse appendage drives $\mu_{\min}$ down, even if the core is dense.

2. Computational Thresholds and Gaps

• Efficient Algorithm: The proposed SDP-based algorithm succeeds if the product of the coherence and rank of the shifted adjacency matrix satisfies specific bounds involving $\sqrt{n}$. This recovers known results for cliques ($k \gtrsim \sqrt{n}$) and balanced bipartite graphs.
• Computational Hardness: Using the LDP framework, the paper shows that for subgraphs with average density $\eta(\Gamma_n) \ll \sqrt{n}$, recovery is computationally hard (no low-degree polynomial succeeds).
• Statistical-Computational Gap: The paper identifies regimes where recovery is statistically possible but computationally hard. For instance, for a planted clique of size $k$, recovery is statistically possible if $k \gtrsim \log n$, but computationally hard if $k \ll \sqrt{n}$.

3. Extensions

• Semi-Random Models: The authors demonstrate that both the optimal MLE and the efficient SDP algorithm are robust to a monotone adversary (who can delete edges outside the planted subgraph and add edges inside it). The recovery guarantees remain unchanged in this adversarial setting.
• Weaker Recovery Notions: For subgraphs where exact recovery is impossible due to sparse appendages (e.g., kites), the paper analyzes $\kappa$-exact recovery (recovering the first $\kappa$ layers of the onion decomposition) and almost-exact recovery (recovering the subgraph up to a vanishing Hamming distance). Tight thresholds are established for these weaker criteria.

Significance and Claims

The paper claims to provide a unified framework for the recovery of arbitrary planted subgraphs, moving beyond the study of specific families like cliques or dense blocks. Its primary significance lies in:

1. Characterizing Statistical Limits: Identifying $\mu_{\min}(\Gamma_n)$ as the governing quantity for the information-theoretic feasibility of exact recovery.
2. Bridging Detection and Recovery: Highlighting a distinct "detection-recovery gap." While detection of a subgraph may be possible in regimes where exact recovery is impossible (specifically for subgraphs with sub-logarithmic minimal maximum subgraph density), the paper clarifies the conditions under which these tasks diverge.
3. Computational Hardness Evidence: Providing rigorous lower bounds via the low-degree polynomial framework that align with the planted clique conjecture and extend it to general subgraph structures.
4. Robustness: Establishing that the proposed recovery methods are robust to monotone adversarial perturbations, a property not always guaranteed for spectral methods.

The authors acknowledge that while they characterize statistical limits tightly, a gap remains between their computational lower and upper bounds for general subgraphs, leaving the precise computational barrier for arbitrary planted subgraphs as an open question. They also note that their techniques are currently limited to the dense regime and extending them to sparse regimes requires further development.