Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Not on the map. Why?
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).
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
18 of 39 references.
References · 18
- 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
- 2021Robust and Differentially Private Mean Estimationcited by 66
- 2021Differential privacy and robust statistics in high dimensionscited by 64
- 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
- 2022Robustness Implies Privacy in Statistical Estimationcited by 47
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
- 2023From Robustness to Privacy and Backcited by 27
- 2018High-dimensional estimation via sum-of-squares proofscited by 25
- 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
- 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
- 2015Private Graphon Estimation for Sparse Graphscited by 17
6 more
- 2017Exact tensor completion with sum-of-squarescited by 14
- 2018Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimationcited by 13
- 2019Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacycited by 13
- 2017Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networkscited by 9
- 2021Robust Estimation for Random Graphscited by 8
- 2024Private graphon estimation via sum-of-squarescited by 3
Built on by
Citing papers per year: 2025: 2.
2 papers.