ICML 2021spotlight28 citations
Differentially Private Correlation Clustering
Mark Bun, Marek Elias, Janardhan Kulkarni
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).
BibTeX
@InProceedings{pmlr-v139-bun21a,
title = {Differentially Private Correlation Clustering},
author = {Bun, Mark and Elias, Marek and Kulkarni, Janardhan},
booktitle = {Proceedings of the 38th International Conference on Machine Learning},
pages = {1136--1146},
year = {2021},
editor = {Meila, Marina and Zhang, Tong},
volume = {139},
series = {Proceedings of Machine Learning Research},
month = {18--24 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v139/bun21a/bun21a.pdf},
url = {https://proceedings.mlr.press/v139/bun21a.html},
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).}
}