Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust

Estimating the edge density of large graphs while protecting individual privacy is a major challenge in data analysis. Existing methods either compromise accuracy by adding excessive noise or are computationally infeasible. Furthermore, real-world datasets are often incomplete or contain errors, requiring robust estimation techniques. Differential privacy provides a rigorous guarantee that individual data points are protected, while robustness ensures accuracy even when data is corrupted. Combining privacy and robustness is highly desirable but computationally difficult.

This research introduces a novel algorithm that overcomes these limitations. It uses sum-of-squares techniques, known for solving complex polynomial optimization problems, to create a robust estimator. It then combines this estimator with an exponential mechanism to ensure differential privacy. Theoretical analysis proves that this combined approach achieves optimal accuracy (up to logarithmic factors) and runs in polynomial time. The algorithm is also shown to be robust against adversarial data corruptions.