mlsanityData to 7 Oct 2026

Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees

arXiv 2302.00037 ↗First posted 31 Jan 2023cs.LG cs.CR cs.DScited by 5

Not on the map. Why?

Abstract (arXiv)

Hierarchical Clustering is a popular unsupervised machine learning method with decades of history and numerous applications. We initiate the study of differentially private approximation algorithms for hierarchical clustering under the rigorous framework introduced by (Dasgupta, 2016). We show strong lower bounds for the problem: that any ε-DP algorithm must exhibit O(|V|2/ ε)-additive error for an input dataset V. Then, we exhibit a polynomial-time approximation algorithm with O(|V|2.5/ ε)-additive error, and an exponential-time algorithm that meets the lower bound. To overcome the lower bound, we focus on the stochastic block model, a popular model of graphs, and, with a separation assumption on the blocks, propose a private 1+o(1) approximation algorithm which also recovers the blocks exactly. Finally, we perform an empirical study of our algorithms and validate their performance.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 22 of its 64 references that are in the map. First posted on arXiv 31 Jan 2023.

Builds on

22 of 64 references.

References · 22

  1. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  2. 2015A cost function for similarity-based hierarchical clusteringcited by 63
  3. 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
  4. 2016Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metricscited by 26
  5. 2014Community detection in sparse networks via Grothendieck's inequalitycited by 21
  6. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  7. 2015How Robust are Reconstruction Thresholds for Community Detection?cited by 20
  8. 2021Robust recovery for stochastic block modelscited by 18
  9. 2014A simple SVD algorithm for finding hidden partitionscited by 17
  10. 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
  11. 2021Differentially Private Correlation Clusteringcited by 13
  12. 2022Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRankcited by 12
10 more
  1. 2022Minimax Rates for Robust Community Detectioncited by 12
  2. 2019Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustlycited by 11
  3. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  4. 2019Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisectioncited by 8
  5. 2021Private Hierarchical Clustering in Federated Networkscited by 8
  6. 2022Near-Optimal Correlation Clustering with Privacycited by 6
  7. 2022Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depthcited by 6
  8. 2018Minimum spanning tree release under differential privacy constraintscited by 4
  9. 2014A novel brain partition highlights the modular skeleton shared by structure and functioncited by 3
  10. 2022Sublinear Algorithms for Hierarchical Clusteringcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 1.

5 papers.

  1. 2025Hyperbolic Continuous Structural Entropy for Hierarchical Clusteringcited by 3
  2. 2024Perturb-and-Project: Differentially Private Similarities and Marginalscited by 1
  3. 2025Differentially Private Synthetic Graphs Preserving Triangle-Motif Cutscited by 1
  4. 2025On the Price of Differential Privacy for Hierarchical Clusteringcited by 0
  5. 2026On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clusteringcited by 0