mlsanityData to 7 Oct 2026

Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy

arXiv 1905.10477 ↗First posted 24 May 2019cs.DS cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 2; 2024: 3; 2025: 2; 2026: 1.

13 papers.

Sort:

  1. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  2. 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
  3. 2023Privacy-Preserving Graph Machine Learning from Data to Computation: A Surveycited by 10
  4. 2022SoK: Differential Privacy on Graph-Structured Datacited by 9
  5. 2021Robust Estimation for Random Graphscited by 8
  6. 2022Near-Optimal Correlation Clustering with Privacycited by 6
  7. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  8. 2024Private graphon estimation via sum-of-squarescited by 3
  9. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  10. 2024On Differentially Private U Statisticscited by 2
  11. 2025It's My Data Too: Private ML for Datasets with Multi-User Training Examplescited by 0
  12. 2025On the Price of Differential Privacy for Hierarchical Clusteringcited by 0
1 more
  1. 2026Differentially Private Modeling of Disease Transmission within Human Contact Networkscited by 0