Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917946881736704 |
|---|---|
| author | Chen, Hongjie Ding, Jingqiu Hua, Yiding Tiegel, Stefan |
| author_facet | Chen, Hongjie Ding, Jingqiu Hua, Yiding Tiegel, Stefan |
| contents | We study the problem of robustly estimating the edge density of Erdős-Rényi 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([\sqrt{\log(n) / n} + η\sqrt{\log(1/η)} ] \cdot \sqrt{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 \geq Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_03923 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point Chen, Hongjie Ding, Jingqiu Hua, Yiding Tiegel, Stefan Data Structures and Algorithms Machine Learning We study the problem of robustly estimating the edge density of Erdős-Rényi 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([\sqrt{\log(n) / n} + η\sqrt{\log(1/η)} ] \cdot \sqrt{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 \geq Ω(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. |
| title | Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2503.03923 |