2025/03/05 by Chen, Hongjie, Ding, Jingqiu, Hua, Yiding +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2503.03923
We study the problem of robustly estimating the edge density of Erdős-Rényi random graphs G(n, d^∘/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^∘ up to an additive error O([√(log(n) / n) + η√(log(1/η)) ] ⋅ √(d^∘) + ηlog(1/η)). Our error guarantee matches information-theoretic lower bounds up to factors of log(1/η). Moreover, our estimator works for all d^∘ ≥ Ω(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^∘/n). Crucially, we show that these certificates also exist in the sparse regime, when d^∘ = o(log n), a regime in which the performance of previous algorithms was significantly suboptimal.