Finding hidden cliques of size N/e in nearly linear time

DOI10.1007/S10208-014-9215-YMaRDI QIDQ896557zbMATHOpenAlexFDO

Authors Yash Deshpande, Andrea Montanari

Publication date 10 December 2015

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7047

zbMATH Keywords

sparse recoveryrandom graphslocal algorithmsapproximate message passingbelief propagationaverage case complexity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Consider an Erd"os-Renyi random graph in which each edge is present independently with probability 1/2, except for a subset $s{C}_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 $|s{C}_N|ge1.261sqrtN$ cite{dekel2011finding}. Spectral methods can be shown to fail on cliques smaller than $sqrtN$. In this paper we describe a nearly linear time algorithm that succeeds with high probability for $|s{C}_N|ge(1+eps)sqrtN/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 $|s{C}_N|ge(1+eps)N/sqrteDelta$ and fail if $|s{C}_N|le(1-eps)N/sqrteDelta$.

Recommendations

• Finding hidden cliques in linear time
• Finding hidden cliques in linear time with high probability
• Finding hidden cliques in linear time with high probability
• scientific article; zbMATH DE number 1303602
• scientific article; zbMATH DE number 1380608
• Finding and certifying a large hidden clique in a semirandom graph
• On approximating the number of \(k\)-cliques in sublinear time
• On approximating the number of k-cliques in sublinear time
• Algorithms – ESA 2005

Cites work

• scientific article; zbMATH DE number 5968943 (Why is no real title available?)
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Detection of an anomalous cluster in a network
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Finding hidden cliques in linear time
• Finding hidden cliques in linear time with high probability
• Finding large average submatrices in high dimensional data
• Graphical models, exponential families, and variational inference
• Information, Physics, and Computation
• Iterative reconstruction of rank-one matrices in noise
• Large Cliques Elude the Metropolis Process
• Locality in Distributed Graph Algorithms
• Modern Coding Theory
• Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
• Nuclear norm minimization for the planted clique and biclique problems
• On colouring random graphs
• On combinatorial testing problems
• On the concentration of eigenvalues of random symmetric matrices
• Optimal detection of sparse principal components in high dimension
• Optimal solutions for sparse principal component analysis
• Probabilistic graphical models.
• Rejoinder
• Robust principal component analysis?
• Statistical algorithms and a lower bound for detecting planted cliques
• Survey of local algorithms
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The Rotation of Eigenvectors by a Perturbation. III
• The eigenvalues of random symmetric matrices
• The isotropic semicircle law and deformation of Wigner matrices
• Universality in polytope phase transitions and message passing algorithms
• What Can be Computed Locally?

Cited in

(41)

• Finding hidden cliques in linear time with high probability
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• A Unifying Tutorial on Approximate Message Passing
• Superlogarithmic cliques in dense inhomogeneous random graphs
• Universality of approximate message passing algorithms
• Finding cliques using few probes
• Parallel tempering for the planted clique problem
• Computational barriers in minimax submatrix detection
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Tensor clustering with planted structures: statistical optimality and computational limits
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Finding hidden cliques in linear time
• Distributed Discovery of Large Near-Cliques
• Cryptography from planted graphs: security with logarithmic-size messages
• Convex optimization for the densest subgraph and densest submatrix problems
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• Estimation of low-rank matrices via approximate message passing
• How to hide a clique?
• Consistency of spectral clustering in stochastic block models
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The committee machine: computational to statistical gaps in learning a two-layers neural network
• Submatrix localization via message passing
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Finding hidden cliques in linear time with high probability
• Finding a planted clique by adaptive probing
• Asymptotic optimality of constant-order policies for lost sales inventory models with large lead times
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• On the computational tractability of statistical estimation on amenable graphs
• Fundamental limits of weak recovery with applications to phase retrieval
• A Simple SVD Algorithm for Finding Hidden Partitions
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Computational barriers to estimation from low-degree polynomials
• Sparsistency and agnostic inference in sparse PCA
• Finding one community in a sparse graph
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

Describes a project that uses

Uses Software

• LAS

This page was built for publication: Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896557)