On hard limits of eigen-analysis based planted clique detection

We study the problem of detecting or discovering a planted clique embedded in a random graph. Using recent results from random matrix theory, we demonstrate the presence of a phase transition in eigen-analysis based methods for planted clique detection. The transition separates a regime in which eigen-analysis based methods will successfully detect the planted clique and the associated vertices from one in which the planted clique is present but is undetectable. We validate the prediction with numerical simulations.