Timezone: »

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

Thu Jul 22 09:00 AM -- 11:00 AM (PDT) @ Virtual
in Poster Session 5 »

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

Keywords: Privacy, Anonymity, and Security · Embedding Approaches · Algorithms -> Representation Learning; Algorithms -> Structured Prediction; Applications · Computational Biology and Bioinform · Social Aspects of Machine Learning
[ Slides] 

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