Differentially Private Correlation Clustering
Mark Bun · Marek Elias · Janardhan Kulkarni
Keywords:
Embedding Approaches
Algorithms -> Representation Learning; Algorithms -> Structured Prediction; Applications
Computational Biology and Bioinform
Privacy, Anonymity, and Security
Social Aspects of Machine Learning
2021 Poster
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 Ω(n).
Video
Chat is not available.
Successful Page Load