Differentially private correlation clustering
Files
Published version
Date
2021-07-18
DOI
Authors
Bun, Mark
Elias, Marek
Kulkarni, Janardhan
Version
OA Version
Citation
M. Bun, M. Elias, J. Kulkarni. 2021. "Differentially private correlation clustering." 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 of Ω (n).
Description
License
Copyright 2021 by the author(s).