Differentially Private Correlation Clustering

Mark Bun, Marek Elias, Janardhan Kulkarni
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:1136-1146, 2021.

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 this Paper

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).} }
Endnote
%0 Conference Paper %T Differentially Private Correlation Clustering %A Mark Bun %A Marek Elias %A Janardhan Kulkarni %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-bun21a %I PMLR %P 1136--1146 %U https://proceedings.mlr.press/v139/bun21a.html %V 139 %X 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).
APA
Bun, M., Elias, M. & Kulkarni, J.. (2021). Differentially Private Correlation Clustering. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:1136-1146 Available from https://proceedings.mlr.press/v139/bun21a.html.

Related Material