Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point

We study the problem of robustly estimating the edge density of Erdos Renyi random graphs $\mathbb{G}(n,d^{\circ }/n)$ when an adversary can arbitrarily add or remove edges incident to an $\eta$-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" width="400em" height="1.28em" viewBox="0 0 400000 1296" preserveAspectRatio="xMinYMin slice">​+ηlog(1/η)​⋅d∘​+ηlog(1/η)). Our error guarantee matches information-theoretic lower bounds up to factors of $\log (1/\eta )$. Moreover, our estimator works for all $d^{\circ }\ge \Omega (1)$ and achieves optimal breakdown point $\eta =1/2$.

Previous algorithms Acharya et al 2022, Chen et al 2024, 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 $\mathbb{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.