Research map / Learning theory and algorithms / Sample complexity
Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first polynomial-time SoS-based algorithm for robustly estimating the edge density of sparse Erdős–Rényi graphs under node corruptions, with near-optimal error and breakdown point 1/2.
Problem
Robust estimation of the edge density (average degree) of Erdős–Rényi random graphs when an adversary arbitrarily corrupts edges incident to an eta-fraction of nodes; prior efficient methods had suboptimal error in the sparse regime and/or breakdown points below 1/2.
Approach
Identifiability via a goodness condition requiring edge counts incident to every small node set to concentrate around their expectation (with d(G) plugged in); the proof is made efficient by constant-degree SoS certificates, using a degree-rescaled centered adjacency matrix spectral bound so that concentration holds in the sparse regime without requiring all node degrees to concentrate.
Key results
- Achieves additive error O([sqrt(log n / n) + eta sqrt(log(1/eta))] sqrt(d) + eta log(1/eta)) in polynomial time, improving on the prior eta log n bound in every regime.
- Works for all d >= Omega(1) (constant c) and for any eta < 1/2, reaching the optimal breakdown point 1/2 with a polynomial-time algorithm.
- Error matches the information-theoretic lower bound Omega(max{eta sqrt(d), eta}) up to a log(1/eta) factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the level-8 SoS estimator for robust edge-density estimation | Robust edge density estimation on G(n, d°/n) · Robust edge-density estimation on G(n, d°/n) | additive estimation error bound: √(log(n) · d°/n) + η√(log(1 / η) · d°)/(1 - 2η)^4 + η log(1 / η)/(1 - 2η)^2 | Helped |
| Replace the previous polynomial-time algorithm with the proposed estimator | Robust edge density estimation on G(n, d°/n) · Robust edge-density estimation on G(n, d°/n) | additive estimation error bound: O([√(log(n) / n) + η√(log(1/η))] · √d° + η log n) | Helped |
| Use the proposed estimator instead of the previous sparse-graph algorithm | Robust edge density estimation on G(n, d°/n) · Sparse robust edge-density estimation | additive estimation error bound: O(d°) | Helped |
| Use a polynomial-time SoS algorithm rather than prior efficient algorithms | Robust edge density estimation on G(n, d°/n) · Robust edge-density estimation | breakdown point: 1/2 | Helped |
Surprising findings
- The median of i.i.d. binomial samples under corruption achieves O(eta sqrt(d)) error, showing the graph setting loses only a sqrt(log(1/eta)) factor relative to the independent case.
- Strong concentration of all node degrees is not necessary; averaging over small sets washes out outlier degrees, enabling sparse-regime guarantees.
Limitations
- Error includes a log(1/eta) factor gap to the lower bound, and the authors leave open whether it is necessary for polynomial-time algorithms.
- Requires level-8 SoS relaxation, which is polynomial but high-degree in n.
- Lower bound is shown for oblivious adversaries while the algorithm targets adaptive adversaries.
Experimental setup
Datasets: synthetic Erdős–Rényi graphs G(n, d/n) with adversarial node corruptions
Metrics: additive estimation error bound breakdown point
Baselines: median estimator truncated median estimator prior polynomial-time robust edge density estimators (eta < 1/60) exponential-time breakdown-1/2 estimator
Builds on: sum-of-squares proofs-to-algorithms framework resilience-based robust statistics Chernoff and McDiarmid concentration
Closest papers by meaning
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.91)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.86)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.85)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.85)
- Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means (NeurIPS 2025 · similarity 0.85)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.