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

DOI10.1007/S10208-014-9215-YzbMATH Open1347.05227arXiv1304.7047OpenAlexW2962704928MaRDI QIDQ896557FDOQ896557

Authors: Yash Deshpande, Andrea Montanari 

Publication date: 10 December 2015

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

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$.

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

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

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)

Cites Work

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

Cited In (36)

• Notes on computational-to-statistical gaps: predictions using statistical physics
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times
• A Unifying Tutorial on Approximate Message Passing
• Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs
• 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
• Cryptography from planted graphs: security with logarithmic-size messages
• Consistency of spectral clustering in stochastic block models
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• Finding a planted clique by adaptive probing
• Fundamental limits of weak recovery with applications to phase retrieval
• Parallel tempering for the planted clique problem
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Title not available (Why is that?)
• 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
• A Simple SVD Algorithm for Finding Hidden Partitions
• Distributed Discovery of Large Near-Cliques
• Submatrix localization via message passing
• On the computational tractability of statistical estimation on amenable graphs
• Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time
• The committee machine: computational to statistical gaps in learning a two-layers neural network
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Title not available (Why is that?)
• Convex optimization for the densest subgraph and densest submatrix problems
• Estimation of low-rank matrices via approximate message passing
• Sparsistency and agnostic inference in sparse PCA
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

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)