# Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Point

arXiv: https://arxiv.org/abs/2503.03923 · HTML: https://mlsanity.com/paper/2503.03923/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 5 Mar 2025.

## Builds on (most cited first, 13 of 13)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)

## Abstract (arXiv)

We study the problem of robustly estimating the edge density of ErdHos-R'enyi random graphs G(n, d^circ/n) when an adversary can arbitrarily add or remove edges incident to an η-fraction of the nodes. We develop the first polynomial-time algorithm for this problem that estimates d^circ up to an additive error O([√log(n) / n + η√log(1/η) ] · √d^circ + η log(1/η)). Our error guarantee matches information-theoretic lower bounds up to factors of log(1/η). Moreover, our estimator works for all d^circ ≥ Omega(1) and achieves optimal breakdown point η = 1/2. Previous algorithms [AJK+22, CDHS24], including inefficient ones, incur significantly suboptimal errors. Furthermore, even admitting suboptimal error guarantees, only inefficient algorithms achieve optimal breakdown point. Our algorithm is based on the sum-of-squares (SoS) hierarchy. A key ingredient is to construct constant-degree SoS certificates for concentration of the number of edges incident to small sets in G(n, d^circ/n). Crucially, we show that these certificates also exist in the sparse regime, when d^circ = o(log n), a regime in which the performance of previous algorithms was significantly suboptimal.