Planted Cliques, Iterative Thresholding and Message Passing Algorithms

Consider an Erdos-Renyi random graph on $n$ vertices constructed as follows. Each edge exists with probability 1/2, except for within a set of vertices of size $k$, which forms a clique (or complete subgraph). A simple argument yields that the planted clique is identifiable by exhaustive search as long as $k \ge 2\log n$. However, no computationally efficient algorithm is known to succeed for $k=o(\sqrt n)$. Further, the best available guarantees are due to spectral methods, which do not exploit the "sparsity" inherent in the problem.

I will describe an iterative algorithm based on belief propagation that provably finds cliques of size $k =\sqrt{n/e}$, which is beyond simple PCA. I will also provide some evidence that this algorithm saturates a threshold that is intrinsic to the problem.

This is joint work with Andrea Montanari.