Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Authors: Hongjie Chen, Jingqiu Ding, Yiding Hua, David Steurer
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of Erdős-Rényi 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. |
| Researcher Affiliation | Academia | Hongjie Chen ETH Zürich Jingqiu Ding ETH Zürich Yiding Hua ETH Zürich David Steurer ETH Zürich |
| Pseudocode | Yes | Algorithm 2.5 (Private coarse estimation for Erdős-Rényi random graphs). Input: 𝜂-corrupted Erdős-Rényi random graph 𝐴. Privacy parameter: 𝜀. Output: A sample from the distribution 𝜇𝐴,𝜀with support [0, 𝑛] and density d𝜇𝐴,𝜀(𝑑) exp( 𝜀 sos-score(𝑑; 𝐴)) |
| Open Source Code | No | The paper is theoretical and focuses on algorithm design and proofs, with no mention of releasing source code or providing repository links. |
| Open Datasets | No | The paper describes theoretical random graph models (Erdős-Rényi, inhomogeneous random graphs) as mathematical constructs for analysis and algorithm design, not as datasets used in experiments. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation with data, therefore no training/validation/test splits are discussed. |
| Hardware Specification | No | This theoretical paper focuses on algorithm design and proofs, and does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | This theoretical paper does not provide details on software dependencies with specific version numbers. |
| Experiment Setup | No | This theoretical paper describes algorithms and their mathematical properties, not experimental setups with hyperparameters or training configurations. |