mlsanityData to 7 Oct 2026

Differentially Private Correlation Clustering

arXiv 2102.08885 ↗First posted 17 Feb 2021cs.LG cs.CR cs.DScited by 13

Not on the map. Why?

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).

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

Builds on

3 of 25 references.

References · 3

  1. 2014Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphscited by 27
  2. 2015Parallel Correlation Clustering on Big Graphscited by 14
  3. 2016A new correlation clustering method for cancer mutation analysiscited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 4; 2023: 4; 2024: 3; 2025: 1.

13 papers.

Sort:

  1. 2021Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Boundscited by 12
  2. 2022Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRankcited by 12
  3. 2022Near-Optimal Correlation Clustering with Privacycited by 6
  4. 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
  5. 2023Correlation Clustering with Active Learning of Pairwise Similaritiescited by 5
  6. 2023Holistic Survey of Privacy and Fairness in Machine Learningcited by 4
  7. 2022Better Private Algorithms for Correlation Clusteringcited by 3
  8. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  9. 2023Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Roundscited by 3
  10. 2024A Differentially Private Clustering Algorithm for Well-Clustered Graphscited by 2
  11. 2025Differentially Private Synthetic Graphs Preserving Triangle-Motif Cutscited by 1
  12. 2024Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Bettercited by 0
1 more
  1. 2024Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Timecited by 0