论文标题
更好的私人算法用于关联集群
Better Private Algorithms for Correlation Clustering
论文作者
论文摘要
在机器学习中，相关聚类是一个重要的问题，其目标是将个人分为与成对相似性相关的组。在这项工作中，我们重新审视了差异隐私约束下的相关聚类。特别是，我们改善了先前的结果并获得了$ \ tilde {o}（n^{1.5}）$添加性错误与一般图表的最佳成本相比。至于未加权的完整图，我们进一步改善了结果，并提出了一种更涉及的算法，该算法可以实现$ \ tilde {o}（n \ sqrt {δ^*}）$添加误差，其中$δ^*$是所有nodes中最大的正边缘。
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.
