Better Private Algorithms for Correlation Clustering
This work addresses privacy-preserving clustering for data analysis, representing an incremental improvement over prior methods in differential privacy.
The paper tackles the problem of correlation clustering under differential privacy constraints, improving previous results by achieving an O~(n^1.5) additive error for general graphs and O~(n√Δ*) for unweighted complete graphs compared to the optimal cost.
In machine learning, correlation clustering is an important problem whose goal is to partition the individuals into groups that correlate with their pairwise similarities as much as possible. In this work, we revisit the correlation clustering under the differential privacy constraints. Particularly, we improve previous results and achieve an $\Tilde{O}(n^{1.5})$ additive error compared to the optimal cost in expectation on general graphs. As for unweighted complete graphs, we improve the results further and propose a more involved algorithm which achieves $\Tilde{O}(n \sqrt{Δ^*})$ additive error, where $Δ^*$ is the maximum degrees of positive edges among all nodes.