Differentially Private Correlation Clustering
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)$.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningClusteringSimilar Papers 제목 키워드 기반
Differentially-Private Clustering of Easy Instances
Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. Despite significant resear…
ClusteringDifferentially Private k-Means Clustering with Guaranteed Convergence
Iterative clustering algorithms help us to learn the insights behind the data. Unfortunately, this may allow adversaries to infer the privacy of individuals with some background knowledge. In the worst case, the adversar…
ClusteringInference AttackA note on differentially private clustering with large additive error
In this note, we describe a simple approach to obtain a differentially private algorithm for k-clustering with nearly the same multiplicative factor as any non-private counterpart at the cost of a large polynomial additi…
ClusteringDifferentially Private Algorithms for Clustering with Stability Assumptions
We study the problem of differentially private clustering under input-stability assumptions. Despite the ever-growing volume of works on differential privacy in general and differentially private clustering in particular…
Clusteringk-Means SubClustering: A Differentially Private Algorithm with Improved Clustering Quality
In today's data-driven world, the sensitivity of information has been a significant concern. With this data and additional information on the person's background, one can easily infer an individual's private data. Many d…
Clustering