2022/03/02 by Vincent Cohen-Addad, Chenglin Fan, Cohen-Addad, Vincent +11 · 1 citation
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Random Matrices and Applications #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2203.01440
openalex publication_date 2022/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labelling 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 approximation guarantees are stronger than those shown in prior work and are optimal up to logarithmic factors.