Recovery of Planted Subgraphs

Jul 16, 2026

Understanding the fundamental limits of recovering planted subgraphs in random graphs addresses core questions in high-dimensional statistics and theoretical computer science. Existing research often targets structured families like cliques or dense blocks, while exact recovery of a general planted subgraph in Erdős–Rényi graphs is still not fully characterized. This work studies exact recovery for an arbitrary planted graph Γ embedded in a dense Erdős–Rényi model, providing sharp probabilistic thresholds, matching lower bounds, and computational feasibility results.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages101

Reading Time4 h 15 min

Contents

Introduction

Problem Setup and Preliminaries

Main Results

Statistical Lower Bound

Upper Bounds

Computational Bounds

Conclusion and Outlook

arXiv :2607 .00897v 1 [ cs .IT] 1 Jul 2026 Recovery of Planted Subgraphs Wasim Huleihel July 2, 2026 Abstract Understanding the fundamental limits of recovering planted subgraphs in random graphs is a central challenge in high-dimensional statistics and theoretical computer science. While existing work has largely focused on special subgraph families such as cliques, bicliques, or dense blocks, the exact recovery of a general planted subgraph in Erd˝os–R´enyi random graphs remains poorly understood. In this paper, we study the exact recovery of an arbitrary planted subgraph Γ = Γn embedded in a dense Erd˝os– R´enyi random graph G (n, qn), where edges within Γ are present independently with probability pn > qn. Our main results identify sharp conditions under which exact recovery is possible with high probability, and we establish matching lower bounds showing the necessity of these conditions. The resulting statistical threshold is characterized by a new graph-theoretic quantity, which we term the minimal maximum subgraph density. This quantity is defined as the maximum subgraph density of the smallest induced balanced subgraph of Γ . We then turn to the problem of recovery under polynomial-time constraints. We propose a computationally efficient recovery algorithm that applies to arbitrary planted subgraphs and analyze its performance in terms of certain spectral properties of the adjacency matrix. In addition, we derive computational lower bounds for recovery using the low-degree polynomial framework, establishing regimes where recovery is statistically possible but computationally hard. Finally, we consider several extensions of our setting, including recovery in semi-random models and weaker notions of recovery. W. Huleihel is with the School of Electrical Engineering and Computer Engineering, at Tel Aviv University, Tel Aviv 6997801, Israel (e-mail: [wasimh@tauex.tau.ac.il](wasimh@tauex.tau.ac.il)). Contents 1 Introduction 3 1.1 Main contributions ................................ 4 1.2 Related work ................................... 6 1.3 Notation ...................................... 9 2 Problem Setup and Preliminaries 10 3 Main Results 13 3.1 Statistical limits .................................. 13 3.2 Computationally efficient algorithm ....................... 16 3.3 Computational lower bounds ........................... 21 3.4 Extensions ..................................... 25 4 Statistical Lower Bound 31 5 Upper Bounds 34 5.1 Peeling MLE ................................... 35 5.2 Convex relaxation ................................. 40 6 Computational Bounds 45 6.1 Lower bound ................................... 45 6.2 Upper bounds ................................... 54 7 Conclusion and Outlook 62 A Auxiliary Lemmata 73 A.1 Equivalence of worst-case and Bayes risks .................... 73 A.2 Proof of Lemma 1 ................................. 75 A.3 Proof of Lemma 2 ................................. 76 A.4 Bounds on coherence ............................... 78 A.5 Spectral-degree bound on coherence ....................... 79 B Derivation of the Maximum Likelihood Estimator 80 C Lower Bound Via Bayes Risk Analysis 80 C.1 Preliminaries on detection ............................ 81 C.2 Generalized subgraph expectation threshold .................. 83 C.3 Proof of Theorem 1 ................................ 87 D Almost-exact recovery 90 D.1 Preliminaries and auxiliary results ........................ 90 D.2 Lower bound through detection ......................... 92 D.3 Lower bound in sub-logarithmic density regime ................ 95 1 Introduction The study of structured signals in networks lies at the intersection of graph theory, computer science, and statistics, with applications ranging from social networks to computational biology. A central question in this area is whether one can reliably reconstruct hidden or anomalous structur

FAQs

What recovery problem does the paper study?

The paper studies exact recovery of an arbitrary planted subgraph Γ embedded in a dense Erdős–Rényi random graph, aiming to pinpoint the planted structure from the observed graph.

What kind of results are provided for statistical recovery?

It identifies sharp high-probability conditions for when exact recovery is possible, and proves matching lower bounds showing these conditions are necessary.

How does the paper address computational limits on recovery?

It proposes a polynomial-time recovery algorithm and analyzes performance via spectral properties, then derives computational lower bounds using the low-degree polynomial framework, identifying regimes that are statistically possible but computationally hard.

Jul 16, 2026

Upload by Olivia Brown