Finding Hidden Cliques of Size $$\sqrt{N/e}$$ N / e in Nearly Linear Time

Consider an Erdos---Renyi random graph in which each edge is present independently with probability $$1/2$$1/2, except for a subset $$\mathsf{C}_N$$CN of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of Dekel et al. (ANALCO. SIAM, pp 67---75, 2011) provably identifies the clique $$\mathsf{C}_N$$CN in linear time, provided $$|\mathsf{C}_N|\ge 1.261\sqrt{N}$$|CN|?1.261N. Spectral methods can be shown to fail on cliques smaller than $$\sqrt{N}$$N. In this paper we describe a nearly linear-time algorithm that succeeds with high probability for $$|\mathsf{C}_N|\ge (1+{\varepsilon })\sqrt{N/e}$$|CN|?(1+?)N/e for any $${\varepsilon }>0$$?>0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on $$N$$N vertices). For large-girth regular graphs of degree $$(\varDelta +1)$$(Δ+1) we prove that so-called local algorithms succeed if $$|\mathsf{C}_N|\ge (1+{\varepsilon })N/\sqrt{e\varDelta }$$|CN|?(1+?)N/eΔ and fail if $$|\mathsf{C}_N|\le (1-{\varepsilon })N/\sqrt{e\varDelta }$$|CN|≤(1-?)N/eΔ.