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 $Omega(n)$.

By admin