Better Private Algorithms for Correlation Clustering

Daogao Liu
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:5391-5412, 2022.

Abstract

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{\Delta^*})$ additive error, where $\Delta^*$ is the maximum degrees of positive edges among all nodes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-liu22h, title = {Better Private Algorithms for Correlation Clustering}, author = {Liu, Daogao}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {5391--5412}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/liu22h/liu22h.pdf}, url = {https://proceedings.mlr.press/v178/liu22h.html}, abstract = {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{\Delta^*})$ additive error, where $\Delta^*$ is the maximum degrees of positive edges among all nodes.} }
Endnote
%0 Conference Paper %T Better Private Algorithms for Correlation Clustering %A Daogao Liu %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-liu22h %I PMLR %P 5391--5412 %U https://proceedings.mlr.press/v178/liu22h.html %V 178 %X 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{\Delta^*})$ additive error, where $\Delta^*$ is the maximum degrees of positive edges among all nodes.
APA
Liu, D.. (2022). Better Private Algorithms for Correlation Clustering. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5391-5412 Available from https://proceedings.mlr.press/v178/liu22h.html.

Related Material