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

arXiv: https://arxiv.org/abs/2405.16663 · HTML: https://mlsanity.com/paper/2405.16663/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 26 May 2024.

## Builds on (most cited first, 18 of 18)

- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017)
- [Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation](https://mlsanity.com/paper/1810.02183/) (2018)
- [Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy](https://mlsanity.com/paper/1905.10477/) (2019)
- [Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks](https://mlsanity.com/paper/1706.01143/) (2017)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)

## Built on by (most cited first, 2 of 2)

- [Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Point](https://mlsanity.com/paper/2503.03923/) (2025)
- [SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search](https://mlsanity.com/paper/2506.03657/) (2025)

## Abstract (arXiv)

We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of ErdHos-R'enyi random graphs and their generalization, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates. Two key ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy to robustness based on sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).