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

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.