# Finding planted cliques using gradient descent

arXiv: https://arxiv.org/abs/2311.07540 · HTML: https://mlsanity.com/paper/2311.07540/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2023.

## Built on by (most cited first, 2 of 2)

- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)

## Abstract (arXiv)

The planted clique problem is a paradigmatic model of statistical-to-computational gaps: the planted clique is information-theoretically detectable if its size k≥ 2log2 n but polynomial-time algorithms only exist for the recovery task when k= Omega(√n). By now, there are many algorithms that succeed as soon as k = Omega(√n). Glaringly, however, no black-box optimization method, e.g., gradient descent or the Metropolis process, has been shown to work. In fact, Chen, Mossel, and Zadik recently showed that any Metropolis process whose state space is the set of cliques fails to find any sub-linear sized planted clique in polynomial time if initialized naturally from the empty set. We show that using the method of Lagrange multipliers, namely optimizing the Hamiltonian given by the sum of the objective function and the clique constraint over the space of all subgraphs, succeeds. In particular, we prove that Markov chains which minimize this Hamiltonian (gradient descent and a low-temperature relaxation of it) succeed at recovering planted cliques of size k = Omega(√n) if initialized from the full graph. Importantly, initialized from the empty set, the relaxation still does not help the gradient descent find sub-linear planted cliques. We also demonstrate robustness of these Markov chain approaches under a natural contamination model.