Finding planted cliques using Markov chain Monte Carlo

Reza Gheissari, Aukosh Jagannath, Yiming Xu

TL;DR

This paper shows that Markov Chain Monte Carlo (MCMC) methods, specifically gradient descent, can successfully find a hidden "planted clique" in a random graph, a task previously thought to be intractable for such general methods. This is achieved by cleverly expanding the search space and initializing the process from the "full graph" state, overcoming limitations that plagued previous attempts.

What Problem Does This Paper Address?

The "planted clique problem" is a fundamental challenge in computer science and statistics. Imagine a large, random network (a graph). We've secretly hidden a smaller, perfectly connected group of nodes (a clique) within this network. The problem is to find this hidden clique. While we know it's theoretically possible to detect if the clique is large enough ($k \ge 2 \log_2 n$), finding it efficiently with algorithms is only guaranteed when the clique is quite large ($k = \Omega(\sqrt{n})$).

A significant gap exists: while specialized algorithms can find these cliques when they're $\Omega(\sqrt{n})$ in size, general-purpose optimization techniques like gradient descent or MCMC methods have historically failed. This is particularly true when these methods are restricted to searching only within the space of cliques and initialized from an empty state. This failure was even proven for sub-linear clique sizes by Chen, Mossel, and Zadik. The authors aim to bridge this gap by showing that a modified MCMC approach can work for the planted clique problem.

Methods

The core innovation lies in modifying the standard MCMC approach. Instead of restricting the search to only valid cliques, the authors allow the Markov chain to explore all possible subsets of vertices. To penalize non-clique subsets, they introduce a "Hamiltonian" (an energy function) that includes a penalty term for missing edges within a subset.

They then apply two MCMC variants to minimize this Hamiltonian:

  1. Gradient Descent: This is a direct minimization approach that moves towards lower energy states.
  2. Low-Temperature Gibbs Sampler: This is a relaxation of gradient descent, allowing for some probabilistic exploration around the minimum energy states, akin to a Metropolis process but with a modified state space.

Crucially, the success of these methods hinges on the initialization. They demonstrate that initializing the process from the full graph (all vertices included) is key, whereas initializing from the empty set still leads to failure, mirroring previous findings. They also explore the robustness of their approach against a "contaminated" planted clique model, where some non-clique vertices have a higher probability of forming edges.

Datasets

Not discussed in the paper. The problem is defined on synthetic random graphs generated according to specific models (Erdos-Renyi with a planted clique).

Key Insights and Ideas

  • Expanding the Search Space is Key: Restricting MCMC to only valid cliques is a major bottleneck. Allowing exploration of all subsets, with a penalty for non-cliques, unlocks success.
  • Initialization Matters Dramatically: The difference between starting from the "full graph" and the "empty set" is the difference between success and failure, even with the relaxed state space. This highlights the importance of the "starting point" in complex optimization landscapes.
  • MCMC Can Be Redeemed: This work demonstrates that general-purpose MCMC methods, often considered less powerful than specialized algorithms for hard problems, can be adapted to solve challenging statistical-to-computational gap problems.
  • Robustness to Contamination: The proposed methods show resilience even when the planted clique is "obscured" by a subset of non-clique vertices with higher edge probabilities.

Key Results

  • Success from Full Graph Initialization: Both gradient descent and its low-temperature Gibbs sampler successfully recover the planted clique of size $k = \Omega(\sqrt{n})$ when initialized from the full graph, in $O(n)$ steps.
  • Failure from Empty Set Initialization: When initialized from the empty set, even with the relaxed Hamiltonian, the algorithms fail to find the planted clique for sub-linear sizes ($k = O(n^\alpha)$ for $\alpha < 1$).
  • Robustness: The algorithms remain successful in finding the planted clique in a "contaminated" model where non-clique vertices have higher edge probabilities.

Limitations and Future Work

  • Sub-linear Clique Sizes: While the paper shows success for $k = \Omega(\sqrt{n})$, it confirms the failure for sub-linear clique sizes when initialized from the empty set. This aligns with theoretical hardness results.
  • Constant Factors: The paper notes that they are not careful about constant factors in their bounds, which might be important for practical performance.
  • Generalization: The authors suggest exploring MCMC approaches for other problems with similar statistical-to-computational gaps, particularly in the context of semi-random graph problems.
  • Positive Temperature Performance: While the proof for the Gibbs sampler holds for $\beta = \Omega(\log n)$, the authors expect similar success for $\beta = O(1)$, but the proof techniques are not sufficient for this case.

Summary updated

Abstract

The planted clique problem is a paradigmatic model of statistical-to-computational gaps: the planted clique is information-theoretically detectable if its size $k\ge 2\log_2 n$ but polynomial-time algorithms only exist for the recovery task when $k= \Omega(\sqrt{n})$. By now, there are many simple and fast algorithms that succeed as soon as $k = \Omega(\sqrt{n})$. Glaringly, however, no MCMC approach to the problem had been shown to work, including the Metropolis process on cliques studied by Jerrum since 1992. 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. Here, we redeem MCMC performance for the planted clique problem by relaxing the state space to all vertex subsets and adding a corresponding energy penalty for missing edges. With that, we prove that energy-minimizing Markov chains (gradient descent and a low-temperature relaxation of it) succeed at recovering planted cliques of size $k = \Omega(\sqrt{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.
BibTeX
@misc{gheissari2023finding,
  author = {Reza Gheissari and Aukosh Jagannath and Yiming Xu},
  title = {{Finding planted cliques using Markov chain Monte Carlo}},
  year = {2023},
  eprint = {2311.07540},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.07540},
}
Figure