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

Abstract

Consider an Erdös-Renyi random graph in which each edge is present independently with probability 1/2, except for a subset $\sC_N$ 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 best known algorithm provably finds the clique in linear time with high probability, provided $|\sC_N|\ge 1.261\sqrt{N}$ \cite{dekel2011finding}. Spectral methods can be shown to fail on cliques smaller than $\sqrt{N}$. In this paper we describe a nearly linear time algorithm that succeeds with high probability for $|\sC_N|\ge (1+\eps)\sqrt{N/e}$ for any $\eps>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$ vertices). For large girth regular graphs of degree $(\Delta +1)$ we prove that `local' algorithms succeed if $|\sC_N|\ge (1+\eps)N/\sqrt{eΔ}$ and fail if $|\sC_N|\le(1-\eps)N/\sqrt{eΔ}$.

48 pages, 1 table, no figures

References in corpus (7)

• Message Passing Algorithms for Compressed Sensing
• Detection of an anomalous cluster in a network
• Finding large average submatrices in high dimensional data
• Computational Lower Bounds for Sparse PCA
• The Isotropic Semicircle Law and Deformation of Wigner Matrices
• Energy Landscape for large average submatrix detection problems in Gaussian random matrices
• Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Cited by in corpus (11)

• Consistency of spectral clustering in stochastic block models
• Computational barriers in minimax submatrix detection
• Finding One Community in a Sparse Graph
• On independent sets in random graphs
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Computational Lower Bounds for Community Detection on Random Graphs
• Sparsistency and agnostic inference in sparse PCA
• Synchronization over $Z_2$ and community detection in multiplex signed networks with constraints
• Random perturbation of low rank matrices: Improving classical bounds
• Statistical Algorithms and a Lower Bound for Detecting Planted Clique
• Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times