# On the Price of Differential Privacy for Hierarchical Clustering

arXiv: https://arxiv.org/abs/2504.15580 · HTML: https://mlsanity.com/paper/2504.15580/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 22 Apr 2025.

## Builds on (most cited first, 22 of 22)

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy](https://mlsanity.com/paper/1905.10477/) (2019)
- [Private Hierarchical Clustering in Federated Networks](https://mlsanity.com/paper/2105.09057/) (2021)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Distances Release with Differential Privacy in Tree and Grid Graph](https://mlsanity.com/paper/2204.12488/) (2022)
- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [Shortest Paths and Distances with Differential Privacy](https://mlsanity.com/paper/1511.04631/) (2015)
- [Optimal Bounds on Private Graph Approximation](https://mlsanity.com/paper/2309.17330/) (2023)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Minimum spanning tree release under differential privacy constraints](https://mlsanity.com/paper/1801.06423/) (2018)
- [Node-Differentially Private Estimation of the Number of Connected Components](https://mlsanity.com/paper/2304.05890/) (2023)
- [Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds](https://mlsanity.com/paper/2203.16476/) (2022)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Differentially Private Range Query on Shortest Paths](https://mlsanity.com/paper/2212.07997/) (2022)
- [The Discrepancy of Shortest Paths](https://mlsanity.com/paper/2401.15781/) (2024)
- [Near-Universally-Optimal Differentially Private Minimum Spanning Trees](https://mlsanity.com/paper/2404.15035/) (2024)
- [Breaking the Linear Error Barrier in Differentially Private Graph Distance Release](https://mlsanity.com/paper/2204.14247/) (2022)
- [Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds](https://mlsanity.com/paper/2206.07554/) (2022)
- [Faster Private Minimum Spanning Trees](https://mlsanity.com/paper/2408.06997/) (2024)

## Abstract (arXiv)

Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clustering involve sensitive user information, therefore motivating recent studies on differentially private hierarchical clustering under the rigorous framework of Dasgupta's objective. However, it has been shown that any privacy-preserving algorithm under edge-level differential privacy necessarily suffers a large error. To capture practical applications of this problem, we focus on the weight privacy model, where each edge of the input graph is at least unit weight. We present a novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting. In particular, our algorithm achieves O(log1.5n/varepsilon) multiplicative error for varepsilon-DP and runs in polynomial time, where n is the size of the input graph, and the cost is never worse than the optimal additive error in existing work. We complement our algorithm by showing if the unit-weight constraint does not apply, the lower bound for weight-level DP hierarchical clustering is essentially the same as the edge-level DP, i.e. Omega(n2/varepsilon) additive error. As a result, we also obtain a new lower bound of tildeOmega(1/varepsilon) additive error for balanced sparsest cuts in the weight-level DP model, which may be of independent interest. Finally, we evaluate our algorithm on synthetic and real-world datasets. Our experimental results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.