Differentially Private Hierarchical Clustering with Provable Approximation Guarantees
Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, Vahab Mirrokni
Abstract
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 $\epsilon$-DP algorithm must exhibit $O(|V|^2/ \epsilon)$-additive error for an input dataset $V$. Then, we exhibit a polynomial-time approximation algorithm with $O(|V|^{2.5}/ \epsilon)$-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.
BibTeX
@inproceedings{icml2023_differentiallypr,
title = {Differentially Private Hierarchical Clustering with Provable Approximation Guarantees},
author = {Jacob Imola and Alessandro Epasto and Mohammad Mahdian and Vincent Cohen-Addad and Vahab Mirrokni},
booktitle = {ICML 2023},
year = {2023}
}