THE LANDSCAPE OF THE PLANTED CLIQUE PROBLEM: DENSE SUBGRAPHS AND THE OVERLAP GAP PROPERTY

• 成果类型: Article
• 署名作者: Amarnik, David; Adik, Ilias
• 署名单位: Massachusetts Institute of Technology (MIT); New York University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP2003
• 发表日期: 2024
• 页码: 3375-3434
• 关键词: local algorithms; submatrix

摘要

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, 1/2). 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 + epsilon) log n for any epsilon > 0, but no polynomial-time algorithm is known for this task unless k = Omega (root 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 = Theta(root 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 Erdos-Renyi model G(n, 1/2) when K = n(0.5-epsilon) for arbitrary epsilon > 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.