Robust Estimation for Random Graphs
This addresses robust statistical estimation in graph models with adversarial corruptions, which is an incremental advance in graph theory and robust statistics.
The paper tackles robust estimation of the parameter p in Erdős-Rényi random graphs with adversarial node corruptions, achieving accuracy bounds like Õ(√(p(1-p))/n + γ√(p(1-p))/√n + γ/n) for γ < 1/60 with a spectral algorithm and extending to γ < 1/2 with an inefficient algorithm, while proving near-optimal lower bounds.
We study the problem of robustly estimating the parameter $p$ of an Erdős-Rényi random graph on $n$ nodes, where a $γ$ 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 + γ\sqrt{p(1-p)} /\sqrt{n}+ γ/n)$ for $γ< 1/60$. Furthermore, we give an inefficient algorithm with similar accuracy for all $γ<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.