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

DOI10.1007/S10208-014-9215-YMaRDI QIDQ896557zbMATH OpenOpenAlexFDO

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

(48)

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

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)