The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property

Abstract

In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size $k$ is planted in an Erdos Renyi graph $G(n,\frac{1}{2})$ resulting in a graph $G\left(n,\frac{1}{2},k\right)$. The goal is to recover the planted clique vertices by observing $G\left(n,\frac{1}{2},k\right)$ . It is known that the clique can be recovered as long as $k\ge \left(2+\epsilon \right)\log n$ for any $\epsilon >0$, but no polynomial-time algorithm is known for this task unless $k=\Omega \left(\sqrt{n}\right)$. Following a statistical-physics inspired point of view as an attempt to understand this computational-statistical gap, we study the landscape of the "sufficiently dense" subgraphs of $G$ and their overlap with the planted clique. Using the first moment method, we study the densest subgraph problems for subgraphs with fixed, but arbitrary, overlap size with the planted clique, and provide evidence of a phase transition for the presence of Overlap Gap Property (OGP) at $k=\Theta \left(\sqrt{n}\right)$. OGP is a concept introduced originally in spin glass theory and known to suggest algorithmic hardness when it appears. We establish the presence of OGP when $k$ is a small positive power of $n$ by using a conditional second moment method. As our main technical tool, we establish the first, to the best of our knowledge, concentration results for the $K$-densest subgraph problem for the Erdos-Renyi model $G\left(n,\frac{1}{2}\right)$ when $K=n^{0.5-\epsilon }$ for arbitrary $\epsilon >0$. Finally, to study the OGP we employ a certain form of overparametrization, which is conceptually aligned with a large body of recent work in learning theory and optimization.

70 pages, 3 Figures. Added Figure 1 (phase diagram), and a new result proving that the OGP implies the failure of an MCMC family to recover the planted clique

References in corpus (11)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Local algorithms for independent sets are half-optimal
• Algorithmic thresholds for tensor PCA
• Suboptimality of local algorithms for a class of max-cut problems
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Average-case Hardness of RIP Certification
• Following the ground-states of full-RSB spherical spin glasses
• Analysing Survey Propagation Guided Decimation on Random Formulas
• Finding a Large Submatrix of a Gaussian Random Matrix

Cited by in corpus (14)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Computational Barriers to Estimation from Low-Degree Polynomials
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Optimizing Mean Field Spin Glasses with External Field
• The Overlap Gap Property in Principal Submatrix Recovery
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Group testing and local search: is there a computational-statistical gap?
• Finding Planted Cliques in Sublinear Time
• On the Cryptographic Hardness of Learning Single Periodic Neurons
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Solving Random Parity Games in Polynomial Time
• Logspace Reducibility From Secret Leakage Planted Clique