Near-Optimal Correlation Clustering with Privacy
This addresses the need for privacy-preserving methods in unsupervised learning tasks like community detection, though it appears incremental as it builds on existing work with improved guarantees.
The paper tackles the correlation clustering problem by introducing a computationally efficient algorithm with provable privacy guarantees, achieving approximation results that are optimal up to logarithmic factors and stronger than prior work.
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.