Robust Estimation for Random Graphs

Abstract

We study the problem of robustly estimating the parameter $p$ of an Erdős-Rényi random graph on $n$ nodes, where a $\gamma$ fraction of nodes may be adversarially corrupted. After showing the deficiencies of canonical estimators, we design a computationally-efficient spectral algorithm which estimates $p$ up to accuracy $\tilde{O}(\sqrt{p(1-p)}/n+\gamma \sqrt{p(1-p)}/\sqrt{n}+\gamma /n)$ for $\gamma <1/60$. Furthermore, we give an inefficient algorithm with similar accuracy for all $\gamma <1/2$, the information-theoretic limit. Finally, we prove a nearly-matching statistical lower bound, showing that the error of our algorithms is optimal up to logarithmic factors.

References in corpus (6)

• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Generalized Resilience and Robust Statistics
• Robust regression with covariate filtering: Heavy tails and adversarial contamination
• A General Method for Robust Learning from Batches
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Local Statistics, Semidefinite Programming, and Community Detection