Timezone: »

Differentially Private Correlation Clustering
Mark Bun · Marek Elias · Janardhan Kulkarni

Thu Jul 22 09:00 AM -- 11:00 AM (PDT) @ Virtual

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).

Author Information

Mark Bun (Boston University)
Marek Elias (CWI)
Janardhan Kulkarni (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors