Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
Abstract
We give a simple, computationally efficient, and node-differentially-private algorithm for estimating the parameter of an Erdos-Renyi graph---that is, estimating p in a G(n,p)---with near-optimal accuracy. Our algorithm nearly matches the information-theoretically optimal exponential-time algorithm for the same problem due to Borgs et al. (FOCS 2018). More generally, we give an optimal, computationally efficient, private algorithm for estimating the edge-density of any graph whose degree distribution is concentrated in a small interval.
Cite
Text
Ullman and Sealfon. "Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy." Neural Information Processing Systems, 2019.Markdown
[Ullman and Sealfon. "Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy." Neural Information Processing Systems, 2019.](https://mlanthology.org/neurips/2019/ullman2019neurips-efficiently/)BibTeX
@inproceedings{ullman2019neurips-efficiently,
title = {{Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy}},
author = {Ullman, Jonathan and Sealfon, Adam},
booktitle = {Neural Information Processing Systems},
year = {2019},
pages = {3770-3780},
url = {https://mlanthology.org/neurips/2019/ullman2019neurips-efficiently/}
}