Differentially Private Correlation Clustering
Abstract
Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering. We propose an algorithm that achieves subquadratic additive error compared to the optimal cost. In contrast, straightforward adaptations of existing non-private algorithms all lead to a trivial quadratic error. Finally, we give a lower bound showing that any pure differentially private algorithm for correlation clustering requires additive error $\Omega$(n).
Cite
Text
Bun et al. "Differentially Private Correlation Clustering." International Conference on Machine Learning, 2021.Markdown
[Bun et al. "Differentially Private Correlation Clustering." International Conference on Machine Learning, 2021.](https://mlanthology.org/icml/2021/bun2021icml-differentially/)BibTeX
@inproceedings{bun2021icml-differentially,
title = {{Differentially Private Correlation Clustering}},
author = {Bun, Mark and Elias, Marek and Kulkarni, Janardhan},
booktitle = {International Conference on Machine Learning},
year = {2021},
pages = {1136-1146},
volume = {139},
url = {https://mlanthology.org/icml/2021/bun2021icml-differentially/}
}