Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
This work addresses privacy-preserving graph analysis for researchers and practitioners handling sensitive network data, representing a strong specific gain rather than a broad paradigm shift.
The authors tackled the problem of estimating the parameter of an Erdos-Renyi graph with node differential privacy, developing a simple and computationally efficient algorithm that achieves near-optimal accuracy, nearly matching the information-theoretically optimal exponential-time algorithm.
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 on a small interval.