Abstract
Given an Erd\H{o}s-R\'enyi (ER) graph over n nodes, a gamma-fraction of which are subject to adversarial corruptions, the goal is to estimate p, the true edge probability of the ER model. We establish nearly-tight bounds on the estimation error as a function of p, gamma, and n. Specifically, we show that the additive error introduced by the corruption model scales roughly as gamma(p/n)^0.5. Our upper bound is an efficient iterative algorithm based on spectral properties of the adjacency matrix, and the lower bound is from a coupling after a reduction from directed random graphs. Time permitting we will discuss some extensions.
This talk is based on joint work with Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, and Huanyu Zhang.