Research map / Federated learning and privacy / Differential privacy
On the Price of Differential Privacy for Hierarchical Clustering
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-weight-DP polynomial-time algorithm for Dasgupta-objective hierarchical clustering on graphs with edge weights at least 1 (O(log^1.5 n/eps) multiplicative error), and proves an Omega(n^2/eps) additive lower bound for weight-DP without the unit-weight assumption, plus an Omega(1/(eps log^2 n)) lower bound for balanced sparsest cut.
Problem
Differentially private hierarchical clustering under Dasgupta's objective, where edge-level DP forces an Omega(n^2/eps) additive error that makes outputs useless in practice.
Approach
Relax to weight-level DP with unit minimum edge weight: add a constant O(log n/eps) bump to every edge then Laplace(1/eps) noise to each edge weight (input perturbation), and run recursive balanced sparsest cut on the perturbed graph; the bump amplifies the gap so noise cannot make high-sparsity cuts look sparse, and post-processing keeps the whole tree eps-DP.
Key results
- Algorithm achieves O(log^1.5 n / eps) multiplicative approximation to optimal Dasgupta cost under eps-weight DP with unit minimum weights, in polynomial time.
- Weight-level DP lower bound of Omega(n^2/eps) additive error holds even for graphs with optimal HC cost O(n/eps), so unit-weight assumption is necessary for good bounds.
- Empirically the proposed algorithm yields substantially lower Dasgupta cost than input perturbation on SBM, HSBM, IRIS, WINE and BOSTON, and scales similarly to the non-private algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DP-HC instead of input perturbation | Hierarchical clustering under weight-level DP · Synthetic SBM and HSBM graphs | Dasgupta cost | Helped |
| Use DP-HC instead of input perturbation | Hierarchical clustering under weight-level DP · IRIS, WINE, and BOSTON | Additional Dasgupta cost | Helped |
| Vary ε across the tested values | DP-HC · IRIS, WINE, and BOSTON | Approximation error | No clear effect |
Surprising findings
- Without the unit-weight assumption, weight-level DP HC suffers the same Omega(n^2/eps) additive lower bound as edge-level DP.
- The exponential-time edge-level DP algorithm of Imola et al. becomes infeasible beyond about n=10 in experiments.
Limitations
- Multiplicative approximation is larger than the best non-private approximation (O(1)), leaving a gap.
- Results are for pure epsilon-DP; approximate-DP improvements are left open.
- The unit minimum weight assumption is required; without it only additive lower bounds of Omega(n^2/eps) hold.
Experimental setup
Datasets: IRIS WINE BOSTON synthetic SBM graphs synthetic HSBM graphs
Benchmarks: IRIS WINE BOSTON synthetic SBM synthetic HSBM
Metrics: Dasgupta's cost running time
Baselines: input perturbation single linkage average linkage complete linkage Imola et al. exponential mechanism
Builds on: Dasgupta's objective Imola et al. edge-level DP hierarchical clustering Laplace mechanism
Closest papers by meaning
- Making Old Things New: A Unified Algorithm for Differentially Private Clustering (ICML 2024 · similarity 0.89)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.89)
- Differentially Private Gomory-Hu Trees (NeurIPS 2025 · similarity 0.87)
- Poincaré Differential Privacy for Hierarchy-Aware Graph Embedding (AAAI 2024 · similarity 0.87)
- Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy (NeurIPS 2026 · similarity 0.87)
- Scalable Private Partition Selection via Adaptive Weighting (ICML 2025 · similarity 0.87)
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.