# Better Private Algorithms for Correlation Clustering

arXiv: https://arxiv.org/abs/2202.10747 · HTML: https://mlsanity.com/paper/2202.10747/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 16 references that are in the map.
- First posted on arXiv 22 Feb 2022.

## Builds on (most cited first, 6 of 6)

- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Private Rank Aggregation in Central and Local Models](https://mlsanity.com/paper/2112.14652/) (2021)

## Built on by (most cited first, 3 of 3)

- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)

## Abstract (arXiv)

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 TildeO(n1.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 TildeO(n √Delta^*) additive error, where Delta^* is the maximum degrees of positive edges among all nodes.