Research map / Federated learning and privacy / Differential privacy
Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
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 a polynomial-time (eps,delta)-DP algorithm for private graph cut sparsification with multiplicative error 1+gamma and additive error n^{1.25+o(1)}, built on a new private expander decomposition.
Problem
Differentially private synthetic graphs that approximate all cuts with multiplicative error 1+gamma; prior efficient methods incur O(n^1.5) additive error, while exponential-time methods reach O~(n).
Approach
Privately compute an expander decomposition of the input graph, then apply the O~(sqrt(nm)) additive-error synthetic graph to the inter-component (sparse) edges and a (1+alpha)-multiplicative private sparsifier to each dense expander component; the expander property makes the per-component error relatively small.
Key results
- Polynomial-time (eps,delta)-DP algorithm releases a non-negative synthetic graph approximating all cuts with multiplicative error 1+gamma and additive error n^{1.25+o(1)}, beating the prior O(n^1.5) barrier for efficient algorithms.
- Sparsifying the synthetic graph yields a sparse graph with O~(n/gamma^2) edges with the same guarantee.
- Applications: max-cut, max-bisection, max-k-cut, and min-bisection DP algorithms with improved additive error n^{1.25+o(1)}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use private expander decomposition to separate sparse inter-component edges from dense components | Private cut sparsifier · All cuts (n-node graphs) | additive error: O(n^{1.5}/\varepsilon) -> n^{1.25 + o(1)}/\varepsilon | Helped |
Limitations
- Additive error n^{1.25+o(1)} is still polynomially larger than the O~(n) achieved by exponential-time methods.
- Guarantee holds for graphs whose inter-component structure is handled only for dense expander parts; improvements for sparser graphs are not addressed.
- Hidden n^{o(1)} factors and polylog(1/delta) dependencies in the bound.
Experimental setup
Metrics: additive error on cut values multiplicative approximation factor number of edges of sparse output
Baselines: Laplace noise on all edges Gupta-Roth-Ullman Eliáš-Kapralov-Kulkarni-Lee Liu-Upadhyay-Zou Upadhyay-Upadhyay-Arora
Builds on: Gupta-Roth-Ullman cut release Eliáš-Kapralov-Kulkarni-Lee Liu-Upadhyay-Zou sqrt(mn) cut release Chuzhoy et al. expander decomposition Benczúr-Karger cut sparsifier
Closest papers by meaning
- Differentially Private Gomory-Hu Trees (NeurIPS 2025 · similarity 0.87)
- Quantum Speedup for Hypergraph Sparsification (ICML 2025 · similarity 0.86)
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.85)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.84)
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.84)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.84)
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.