# Differentially Private Correlation Clustering

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 17 Feb 2021.

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

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [A new correlation clustering method for cancer mutation analysis](https://mlsanity.com/paper/1601.06476/) (2016)

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

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Correlation Clustering with Active Learning of Pairwise Similarities](https://mlsanity.com/paper/2302.10295/) (2023)
- [Holistic Survey of Privacy and Fairness in Machine Learning](https://mlsanity.com/paper/2307.15838/) (2023)
- [Better Private Algorithms for Correlation Clustering](https://mlsanity.com/paper/2202.10747/) (2022)
- [Sharper Utility Bounds for Differentially Private Models](https://mlsanity.com/paper/2204.10536/) (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)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)

## Abstract (arXiv)

Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering. We propose an algorithm that achieves subquadratic additive error compared to the optimal cost. In contrast, straightforward adaptations of existing non-private algorithms all lead to a trivial quadratic error. Finally, we give a lower bound showing that any pure differentially private algorithm for correlation clustering requires additive error of Omega(n).