The landscape of the planted clique problem: Dense subgraphs and the overlap gap property

We study the computational-statistical gap of the planted clique problem, where a clique of size k is planted in an Erdős–Rényi graph G(n,12). The goal is to recover the planted clique vertices by observing the graph. It is known that the clique can be recovered as long as k≥(2+ϵ)logn for any ϵ>0, but no polynomial-time algorithm is known for this task unless k=Ω(n). Following a statistical-physics inspired point of view, as a way to understand the nature of 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 present evidence of a phase transition for the presence of the overlap gap property (OGP) at k=Θ(n). OGP is a concept originating in spin glass theory and known to suggest algorithmic hardness when it appears. We further prove the presence of the OGP when k is a small positive power of n, and therefore, for an exponential-in-n part of the gap, 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 Erdős–Rényi model G(n,12) when K=n0.5−ϵ for arbitrary ϵ>0. Our methodology throughout the paper, is based on a certain form of overparametrization, which is conceptually aligned with a large body of recent work in learning theory and optimization.