mlsanityData to 14 Oct 2026

Robust Estimation for Random Graphs

arXiv 2111.05320 ↗First posted 9 Nov 2021cs.DS cs.IT math.ITcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the problem of robustly estimating the parameter p of an ErdHos-R'enyi random graph on n nodes, where a γ fraction of nodes may be adversarially corrupted. After showing the deficiencies of canonical estimators, we design a computationally-efficient spectral algorithm which estimates p up to accuracy tilde O(√p(1-p)/n + γ√p(1-p) /√n+ γ/n) for γ < 1/60. Furthermore, we give an inefficient algorithm with similar accuracy for all γ <1/2, the information-theoretic limit. Finally, we prove a nearly-matching statistical lower bound, showing that the error of our algorithms is optimal up to logarithmic factors.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 35 of its 66 references that are in the map. First posted on arXiv 9 Nov 2021.

Builds on

35 of 66 references.

References · 35

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  4. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  5. 2016Learning from Untrusted Datacited by 90
  6. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  7. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  8. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  9. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  10. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  11. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 64
  12. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
23 more
  1. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  2. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  3. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  4. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  5. 2019Generalized Resilience and Robust Statisticscited by 37
  6. 2018High Dimensional Robust Sparse Regressioncited by 29
  7. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  8. 2015How Robust are Reconstruction Thresholds for Community Detection?cited by 20
  9. 2014Robust and computationally feasible community detection in the presence of arbitrary outlier nodescited by 17
  10. 2015Private Graphon Estimation for Sparse Graphscited by 17
  11. 2020High-Dimensional Robust Mean Estimation via Gradient Descentcited by 16
  12. 2017Learning Discrete Distributions from Untrusted Batchescited by 14
  13. 2019Local Statistics, Semidefinite Programming, and Community Detectioncited by 14
  14. 2018Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimationcited by 13
  15. 2019Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacycited by 13
  16. 2015Sum-of-squares lower bounds for planted cliquecited by 12
  17. 2019Optimal Robust Learning of Discrete Distributions from Batchescited by 10
  18. 2015Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problemscited by 9
  19. 2016Robust Learning of Fixed-Structure Bayesian Networkscited by 8
  20. 2019Efficiently Learning Structured Distributions from Untrusted Batchescited by 8
  21. 2020Learning Structured Distributions From Untrusted Batches: Faster and Simplercited by 8
  22. 2020A General Method for Robust Learning from Batchescited by 8
  23. 2015Learning Communities in the Presence of Errorscited by 7

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 2; 2024: 1; 2025: 2.

8 papers.

  1. 2022Minimax Rates for Robust Community Detectioncited by 12
  2. 2023Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptionscited by 7
  3. 2022Efficient List-Decodable Regression using Batchescited by 5
  4. 2022Robust estimation algorithms don't need to know the corruption levelcited by 4
  5. 2023Linear Regression using Heterogeneous Data Batchescited by 3
  6. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  7. 2025Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Pointcited by 0
  8. 2025SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Searchcited by 0