Timezone: »

 
Poster
Near-Optimal Correlation Clustering with Privacy
Vincent Cohen-Addad · Chenglin Fan · Silvio Lattanzi · Slobodan Mitrovic · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #718
in Poster Session 5 »

Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labeling and many more. In the correlation clustering problem one receives as input a set of nodes and for each node a list of co-clustering preferences, and the goal is to output a clustering that minimizes the disagreement with the specified nodes' preferences. In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters.

Keywords: Clustering · differential privacy · Approximation Algorithms · Correlation Clustering

Author Information

Vincent Cohen-Addad (Google research)
Chenglin Fan (Sorbonne University)
Silvio Lattanzi (Google Research)
Slobodan Mitrovic (UC Davis)
Ashkan Norouzi-Fard (Google Research)
Nikos Parotsidis (Google Research)
Jakub Tarnawski (Microsoft Research)

More from the Same Authors