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

approximate message passingaverage case complexitybelief propagationlocal algorithmsrandom graphssparse recovery

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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 eigenvalues of random symmetric matrices
• The isotropic semicircle law and deformation of Wigner matrices
• The Rotation of Eigenvectors by a Perturbation. III
• Universality in polytope phase transitions and message passing algorithms
• What Can be Computed Locally?

Cited in

(48)

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