We study the planted clique problem in random geometric graphs. Starting from a hard random geometric graph, we uniformly sample a set of vertices and add all missing edges among them, creating a hidden clique. The goal is to recover this planted set exactly. We compare two simple algorithms: one based on vertex degrees and one based on common neighbors. While the degree-based method succeeds only when the planted clique is large enough to stand out, the common-neighbors method exploits the graph's geometry and succeeds over a much wider range of parameters. In particular, in the connectivity regime, it can recover even very small planted cliques, including planted edges. We complement the theoretical guarantees with numerical experiments showing that the common-neighbors approach is also very effective for finite-size graphs.

Joint work with: Konstantin Avrachenkov, Andrei Bobu, and Nelly Litvak.