mlsanityData to 14 Oct 2026

Planted Bipartite Graph Detection

arXiv 2302.03658 ↗First posted 7 Feb 2023cs.DS cs.IT cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an ErdHos-R'enyi random graph over n vertices with edge density q. Under the alternative, there exists a planted k_mathsfR × k_mathsfL bipartite subgraph with edge density p>q. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where p,q = Thetaleft(1right), and the sparse regime where p,q = Thetaleft(n-αright), α ∈ left(0,2right]. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an "easy-hard-impossible" phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 33 of its 62 references that are in the map. First posted on arXiv 7 Feb 2023.

Builds on

33 of 62 references.

References · 33

  1. 2017Community Detection and Stochastic Block Modelscited by 319
  2. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  3. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  4. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  5. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  6. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  7. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 51
  8. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
  9. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  10. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  11. 2014Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatricescited by 29
  12. 2014Statistical and computational trade-offs in estimation of sparse principal componentscited by 26
21 more
  1. 2014Sparse CCA: Adaptive Estimation and Computational Barrierscited by 25
  2. 2018High-dimensional estimation via sum-of-squares proofscited by 25
  3. 2014Computational Lower Bounds for Community Detection on Random Graphscited by 22
  4. 2015MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channelcited by 22
  5. 2018Notes on computational-to-statistical gaps: predictions using statistical physicscited by 22
  6. 2013On the Complexity of Random Satisfiability Problems with Planted Solutionscited by 14
  7. 2019Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyondcited by 14
  8. 2016Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clusteringcited by 13
  9. 2019Universality of Computational Lower Bounds for Submatrix Detectioncited by 13
  10. 2015Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrixcited by 12
  11. 2015Sum-of-squares lower bounds for planted cliquecited by 12
  12. 2013Community Detection in Sparse Random Networkscited by 11
  13. 2015Sum-of-Squares Lower Bounds for Sparse PCAcited by 10
  14. 2016Average-case Hardness of RIP Certificationcited by 10
  15. 2013Do semidefinite relaxations solve sparse PCA up to the information limit?cited by 9
  16. 2015Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problemscited by 9
  17. 2019Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4cited by 9
  18. 2018Hidden Hamiltonian Cycle Recovery via Linear Programmingcited by 8
  19. 2019Finding a planted clique by adaptive probingcited by 6
  20. 2021Random Subgraph Detection Using Queriescited by 3
  21. 2021Inferring Hidden Structures in Random Graphscited by 2

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Optimal community detection in dense bipartite graphscited by 1
  2. 2025Robust Detection of Planted Subgraphs in Semi-Random Modelscited by 0