mlsanityData to 14 Oct 2026

Near-Optimal Correlation Clustering with Privacy

arXiv 2203.01440 ↗First posted 2 Mar 2022cs.LG cs.CR cs.DScited by 6

Not on the map. Why?

Abstract (arXiv)

Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labelling and many more. In the correlation clustering problem one receives as input a set of nodes and for each node a list of co-clustering preferences, and the goal is to output a clustering that minimizes the disagreement with the specified nodes' preferences. In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our approximation guarantees are stronger than those shown in prior work and are optimal up to logarithmic factors.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 13 of its 57 references that are in the map. First posted on arXiv 2 Mar 2022.

Builds on

13 of 57 references.

References · 13

  1. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  2. 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
  3. 2014Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphscited by 27
  4. 2021Locally Private k-Means in One Roundcited by 19
  5. 2021Correlation Clustering in Constant Many Parallel Roundscited by 15
  6. 2018Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimationcited by 13
  7. 2019Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacycited by 13
  8. 2021Differentially Private Correlation Clusteringcited by 13
  9. 2020Differentially private k-means clustering via exponential mechanism and max covercited by 8
  10. 2021Differentially Private Densest Subgraph Detectioncited by 7
  11. 2021Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositionscited by 7
  12. 2021Differentially Private Densest Subgraphcited by 6
1 more
  1. 2022Better Private Algorithms for Correlation Clusteringcited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 3; 2025: 1.

6 papers.

  1. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  2. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  3. 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
  4. 2023Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Roundscited by 3
  5. 2024A Differentially Private Clustering Algorithm for Well-Clustered Graphscited by 2
  6. 2025Differentially Private Synthetic Graphs Preserving Triangle-Motif Cutscited by 1