Computational Lower Bounds for Community Detection on Random Graphs

This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph $\mathcal{G}(N,q)$, where the edge probability within the community exceeds $q$ by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size $N$ grows and the graph becomes sparser according to $q=N^{-\alpha}$, there exists a critical value of $\alpha = \frac{2}{3}$, below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest $K$-subgraph.

• Publication year

  2014

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  2014-06-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1406.6625
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Finding Hidden Cliques of Size in Nearly Linear Time

  2015cited by this paper
• Consistency Thresholds for the Planted Bisection Model

  2014cited by this paper
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

  2014cited by this paper
• Exact Recovery in the Stochastic Block Model

  2014cited by this paper
• Community detection in dense random networks

  2014influential reference
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

  2014cited by this paper
• Consistency Thresholds for Binary Symmetric Block Models

  2014cited by this paper
• Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation

  2013cited by this paper
• A Proof of the Block Model Threshold Conjecture

  2013cited by this paper
• Community Detection in Sparse Random Networks

  2013influential reference
• Community Detection in Random Networks

  2013influential reference
• Jointly clustering rows and columns of binary matrices: algorithms and trade-offs

  2013cited by this paper
• Community detection thresholds and the weak Ramanujan property

  2013cited by this paper
• Computational Barriers in Minimax Submatrix Detection

  2013cited by this paper
• Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

  2013influential reference
• Robust convex relaxation for the planted clique and densest k-subgraph problems

  2013cited by this paper
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

  2013cited by this paper
• Statistical algorithms and a lower bound for detecting planted cliques

  2012influential reference
• Computational and statistical tradeoffs via convex relaxation

  2012cited by this paper
• Stochastic Block Models and Reconstruction

  2012cited by this paper
• Statistical and computational tradeoffs in biclustering

  2011cited by this paper
• Inapproximabilty of Densest κ-Subgraph from Average Case Hardness

  2011cited by this paper
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

  2011cited by this paper
• Minimax Localization of Structural Information in Large Noisy Matrices

  2011cited by this paper
• Computational complexity and information asymmetry in financial products

  2011cited by this paper
• Detection of a sparse submatrix of a high-dimensional noisy matrix

  2011cited by this paper
• Distributed user profiling via spectral methods

  2010cited by this paper
• Finding Hidden Cliques in Linear Time with High Probability

  2010cited by this paper
• Public-key cryptography from different assumptions

  2010cited by this paper
• Detecting High Log-Densities – an O ( n 1 / 4 ) Approximation for Densest k -Subgraph

  2010cited by this paper
• Nuclear norm minimization for the planted clique and biclique problems

  2009cited by this paper
• Finding hidden cliques in linear time

  2009cited by this paper
• Community detection in graphs

  2009cited by this paper
• Graph Partitioning via Adaptive Spectral Techniques

  2009cited by this paper
• How hard is it to approximate the best Nash equilibrium?

  2009cited by this paper
• Testing k-wise and almost k-wise independence

  2007cited by this paper
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005influential reference
• Spectral partitioning of random graphs

  2001cited by this paper
• Finding and certifying a large hidden clique in a semirandom graph

  2000cited by this paper
• Finding a large hidden clique in a random graph

  1998influential reference
• Hiding Cliques for Cryptographic Security

  1998cited by this paper
• Balls and Bins: A Study in Negative Dependence

  1996cited by this paper
• Expected Complexity of Graph Partitioning Problems

  1995cited by this paper
• Large Cliques Elude the Metropolis Process

  1992cited by this paper

• Robust Detection of Planted Subgraphs in Semi-Random Models

  2025cites this paper
• Recovering Small Communities in the Planted Partition Model

  2025cites this paper
• On optimal distinguishers for Planted Clique

  2025cites this paper
• The Quasi-Polynomial Low-Degree Conjecture is False

  2025cites this paper
• Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

  2025influential citation
• Statistical and computational challenges in ranking

  2025cites this paper
• Sharp Phase Transitions in Estimation with Low-Degree Polynomials

  2025cites this paper
• Detecting weighted hidden cliques

  2025cites this paper
• Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph

  2024cites this paper
• Computationally Efficient Reductions Between Some Statistical Models

  2024cites this paper
• Information-Theoretic Thresholds for Planted Dense Cycles

  2024cites this paper
• Statistical Inference of a Ranked Community in a Directed Graph

  2024cites this paper
• Performance Comparison of Estimation Methods in Network Analysis

  2024cites this paper
• Planted Clique Conjectures Are Equivalent

  2024influential citation
• Statistical and Computational Limits of Detecting and Recovering Hidden Submatrices

  2024cites this paper
• Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

  2023cites this paper
• Detection of Model-Based Planted Pseudo-Cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding

  2023cites this paper
• Finding planted cliques using gradient descent

  2023cites this paper
• Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials

  2023cites this paper
• Detecting a Planted Bipartite Graph

  2023influential citation
• Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

  2023influential citation
• Detection and Recovery of Hidden Submatrices

  2023cites this paper
• Bayes Optimal Learning in High-Dimensional Linear Regression With Network Side Information

  2023cites this paper
• Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles

  2023cites this paper
• Hardness Self-Amplification: Simplified, Optimized, and Unified

  2023cites this paper
• Detection of Dense Subhypergraphs by Low‐Degree Polynomials

  2023cites this paper
• Sum-of-Squares Lower Bounds for Densest k-Subgraph

  2023cites this paper
• Localized geometry detection in scale-free random graphs

  2023cites this paper
• Is Planted Coloring Easier than Planted Clique?

  2023cites this paper
• Detection-Recovery Gap for Planted Dense Cycles

  2023influential citation
• Planted Bipartite Graph Detection

  2023influential citation
• Public-Key Encryption from Homogeneous CLWE

  2022cites this paper
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials

  2022cites this paper
• Community Recovery in the Geometric Block Model

  2022cites this paper
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

  2022cites this paper
• Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs

  2022cites this paper
• Public-Key Encryption from Continuous LWE

  2022cites this paper
• Is it easier to count communities than find them?

  2022cites this paper
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning

  2022cites this paper
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering

  2021cites this paper
• Inferring Hidden Structures in Random Graphs

  2021cites this paper
• Convex Formulation for Planted Quasi-Clique Recovery

  2021cites this paper
• Logspace Reducibility From Secret Leakage Planted Clique

  2021cites this paper
• Introduction to Information Theory and Data Science.

  2021cites this paper
• Random Subgraph Detection Using Queries

  2021cites this paper
• Computational Barriers to Estimation from Low-Degree Polynomials

  2020influential citation
• Is the space complexity of planted clique recovery the same as that of detection?

  2020cites this paper
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits

  2020cites this paper
• Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection

  2020cites this paper
• Reducibility and Statistical-Computational Gaps from Secret Leakage

  2020influential citation
• Planted Models for the Densest $k$-Subgraph Problem

  2020cites this paper
• Statistical and Computational Rates in Graph Logistic Regression

  2020cites this paper
• The Strongish Planted Clique Hypothesis and Its Consequences

  2020cites this paper
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

  2020cites this paper
• Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function”

  2020cites this paper
• Phase transitions for detecting latent geometry in random graphs

  2019cites this paper
• More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning

  2019cites this paper
• Universality of Computational Lower Bounds for Submatrix Detection

  2019influential citation
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

  2019cites this paper
• The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs

  2019cites this paper
• Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

  2019cites this paper
• Optimal estimation in high-dimensional and nonparametric models

  2019cites this paper
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

  2019cites this paper
• Community detection in inhomogeneous random graphs.

  2019cites this paper
• Community detection in networks: a game-theoretic framework

  2019cites this paper
• Detecting a planted community in an inhomogeneous random graph

  2019cites this paper
• Statistical Inference and the Sum of Squares Method

  2018cites this paper
• Parallel tempering for the planted clique problem

  2018cites this paper
• Computational hardness of fast rates for online sparse PCA : improperness does not help

  2018cites this paper
• Optimal link prediction with matrix logistic regression

  2018cites this paper
• Notes on computational-to-statistical gaps: predictions using statistical physics

  2018cites this paper
• Connectivity in Random Annulus Graphs and the Geometric Block Model

  2018cites this paper
• Statistical and Computational Limits for Sparse Matrix Detection

  2018cites this paper
• Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits

  2018influential citation
• Planting trees in graphs, and finding them back

  2018cites this paper
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

  2018cites this paper
• The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference

  2018cites this paper
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval

  2018cites this paper
• Bipartite Stochastic Block Models with Tiny Clusters

  2018cites this paper
• Recovering a Single Community With Side Information

  2018cites this paper
• Diffusion Games over Social Networks

  2017cites this paper
• SDP-Hardness of Approximation for Densest k-subgraph

  2017cites this paper
• Spectral analysis of random graphs with application to clustering and sampling. (L'analyse spectrale des graphes aléatoires et son application au groupement et l'échantillonnage)

  2017cites this paper
• The Geometric Block Model

  2017cites this paper
• Guaranteed Tensor PCA with Optimality in Statistics and Computation

  2017cites this paper
• Information Limits for Recovering a Hidden Community

  2017cites this paper
• Query Complexity of Clustering with Side Information

  2017influential citation
• Tensor SVD: Statistical and Computational Limits

  2017cites this paper
• Inference in Sparse Graphs with Pairwise Measurements and Side Information

  2017cites this paper
• On the Statistical Limits of Convex Relaxations

  2016cites this paper
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

  2016cites this paper
• Average-case hardness of RIP certification

  2016cites this paper
• Semidefinite Programs for Exact Recovery of a Hidden Community

  2016cites this paper
• Spectral methods and computational trade-offs in high-dimensional statistical inference

  2016cites this paper
• Complexity of equilibrium in competitive diffusion games on social networks

  2016cites this paper
• Community Detection in Networks: understanding the fundamental limits of polynomial-time algorithms

  2015cites this paper
• Information limits for recovering a hidden community

  2015cites this paper
• The Hidden Subgraph Problem

  2015cites this paper
• Finding One Community in a Sparse Graph

  2015cites this paper
• Submitted to the Annals of Statistics STATISTICAL AND COMPUTATIONAL TRADE-OFFS IN ESTIMATION OF SPARSE PRINCIPAL COMPONENTS By

  2015cites this paper