Research map / Learning theory and algorithms / Sample complexity
Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first polynomial-time, differentially node-private, and robust estimator of edge density for Erdős-Rényi and inhomogeneous random graphs, using a sum-of-squares exponential mechanism, with matching lower bounds up to log factors.
Problem
Estimating the edge density of Erdős-Rényi and inhomogeneous random graphs under node differential privacy and adversarial node corruption, in polynomial time and with near-optimal error.
Approach
A sum-of-squares relaxation of a robust degree-estimation program is used as the score function of an exponential mechanism, turning robustness into node privacy with polynomial running time; the score sensitivity is bounded by 1 under node-neighboring graphs.
Key results
- Private and robust estimator for Erdős-Rényi graphs with error O(sqrt(log n)/(n sqrt(p)) + log^2 n/(eps n sqrt(np)) + eta log n/sqrt(np)), polynomial time.
- Information-theoretic lower bounds Omega(log(1/beta)/(eps n sqrt(np))) for privacy and Omega(R eta) for robustness show optimality up to log factors.
- Constant-factor approximation of degree in sparse regime (d << log n) with eta constant, which prior robust algorithms cannot provide.
Limitations
- Relies on sum-of-squares relaxations whose exact pseudo-expectation computation is only approximate; bit-complexity assumptions needed.
- Requires eps at least about log(n)/n and degree lower bounds (constant expected degree) for the guarantees.
- Robustness and privacy constants are only specified up to unspecified small constants.
Experimental setup
Metrics: relative error of edge density estimate
Baselines: Borgs et al. Lipschitz extension Sealfon and Ullman smooth sensitivity Laplace mechanism on empirical edge density
Builds on: Hopkins et al. 2023 sum-of-squares exponential mechanism Borgs et al. node-private graph statistics Sealfon and Ullman smooth sensitivity Asi et al. robustness-to-privacy reduction
Closest papers by meaning
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.91)
- Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy (NeurIPS 2026 · similarity 0.86)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.86)
- Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition (ICML 2025 · similarity 0.85)
- Breaking the curse of dimensionality in structured density estimation (NeurIPS 2024 · similarity 0.85)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.