Research map / Federated learning and privacy / Differential privacy
Differentially Private Gomory-Hu Trees
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 an epsilon-DP polynomial-time algorithm that outputs an approximate Gomory-Hu tree with tilde-O(n/eps) additive error for all-pairs min s-t cuts, via a new DP min isolating cuts primitive.
Problem
Releasing all-pairs minimum s-t cuts (APMC) in an undirected weighted graph under differential privacy with small additive error; prior bounds were O(n^{3/2}/eps) pure DP and sqrt(mn)/eps approximate DP.
Approach
Recursive Gomory-Hu construction (low-depth, Steiner-tree variant) where each min-isolating-cut step is privatized using a DP min s-t cut with penalty edges to a sink, a changing acceptance threshold across sampling levels, and noisy edges added to contracted instances so that each edge influences only one recursive branch, with budget split across levels.
Key results
- Epsilon-DP algorithm outputs approximate GH-tree with tilde-O(n/eps) additive error for all pairs s,t w.h.p., in tilde-O(n^2) time, improving prior O(n^{3/2}/eps) pure DP bound.
- New epsilon-DP min isolating cuts algorithm with tilde-O(n/eps) additive error.
- Corollaries: pure DP global min cut with tilde-O(n/eps) error in polynomial time, and minimum k-cut with multiplicative 2 and additive tilde-O(nk/eps) error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a pure-DP approximate Gomory-Hu tree instead of releasing a synthetic graph that preserves all cuts | APMC · APMC | additive error: O(n^{3/2}/\eps) -> \Tilde{O}(n/\eps) | Helped |
| Use a pure-DP approximate Gomory-Hu tree instead of the approximate-DP all-cuts algorithm | APMC · APMC | additive error: \tilde{O}(\sqrt{mn}/\eps) -> \Tilde{O}(n/\eps) | Helped |
| Introduce a private Min Isolating Cuts algorithm | Differentially private Gomory-Hu tree · Min Isolating Cuts | additive error: \tO(n/\eps) | Helped |
| Recover global Min Cut from the private Gomory-Hu tree | Differentially private Gomory-Hu tree · Global Min Cut | additive error: \tilde{O}(n/\eps) | Helped |
| Use the private Gomory-Hu tree to construct a minimum k-cut | Differentially private Gomory-Hu tree · Minimum k-cut | additive error: \tilde{O}(k^{1.5}/\eps) -> \tilde{O}(nk/\eps) | Mixed |
Surprising findings
- Pure-DP all-pairs min cut matches the tilde-O(n/eps) error of single-pair min cut up to polylog factors, closing the gap with synthetic-graph methods.
Limitations
- Error is tilde-O(n/eps) with polylog factors (up to lg^8 n in the approximate tree lemma), not tight in log factors
- Global min cut in polynomial time with pure DP and O(log n/eps) error remains open
- Releasing only cut values (not cuts) may admit better error; lower bound unknown
Experimental setup
Metrics: additive error of min s-t cut values approximation of Gomory-Hu tree
Baselines: Gupta-Roth-Ullman all-cuts synthetic graph (O(n^{3/2}/eps)) Liu-Upadhyay-Zou synthetic graph (sqrt(mn)/eps, approx DP) Laplace noise on all cut values (O(n/eps), approx DP)
Builds on: Gomory-Hu tree (Abboud et al. low-depth recursion) Dalirrooyfard et al. private min s-t cut Gupta-Roth-Ullman private cuts Isolating cuts lemma
Closest papers by meaning
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.88)
- Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition (ICML 2025 · similarity 0.87)
- On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.87)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.87)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.86)
- Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees (NeurIPS 2026 · similarity 0.86)
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.