Better Private Algorithms for Correlation Clustering. (arXiv:2202.10747v1 [cs.LG])

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 …

algorithms correlation lg