Differentially Private Correlation Clustering
This addresses privacy concerns in unsupervised machine learning applications where individual data must be protected, representing a foundational step in the field.
The paper tackles the problem of performing correlation clustering under differential privacy constraints, proposing an algorithm that achieves subquadratic additive error compared to the optimal cost, in contrast to trivial quadratic errors from naive adaptations.
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)$.