Differentially Private Correlation Clustering

2021/02/17 by Bun, Mark, Eliáš, Marek, Kulkarni, Janardhan · 1 citation
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2102.08885

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 of Ω(n).

Cited by

• Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

Related

• Better Private Algorithms for Correlation Clustering
• Near-Optimal Correlation Clustering with Privacy
• A note on differentially private clustering with large additive error
• Differentially Private Clustering: Tight Approximation Ratios
• Making Old Things New: A Unified Algorithm for Differentially Private Clustering