Differentially Private Correlation Clustering

Mark Bun, Marek Eliás, Janardhan Kulkarni

Abstract

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

Introduction

Correlation clustering is a classic unsupervised learning task where, given a set of objects and pairwise labels indicating similarity (+) or dissimilarity (-), the goal is to partition the objects into clusters to minimize disagreements. Disagreements occur when similar items are placed in different clusters or dissimilar items are placed in the same cluster.

In many modern applications, these pairwise labels represent sensitive information, such as private transaction records or personal communications. A single change in a sensitive data point could flip a label, potentially altering the entire optimal clustering structure. This paper provides the first formal study of correlation clustering under the lens of differential privacy (DP), addressing the challenge of designing algorithms that remain robust to such changes while maintaining utility.

The Quadratic Barrier

A significant hurdle in private correlation clustering is that standard approximation algorithms, such as the popular "pivot" algorithm, are highly sensitive to input perturbations. Naive adaptations of these algorithms to satisfy DP typically result in a quadratic additive error ($O(n^2)$), which is no better than a random or trivial clustering. This research seeks to break this barrier by achieving subquadratic error bounds.

Methodology

Rather than modifying existing iterative clustering algorithms, the proposed approach utilizes a "synthetic graph release" strategy combined with a novel "cluster packing" technique.

1. Synthetic Graph Release

The algorithm first generates a "sanitized" version of the input graph using advanced DP mechanisms. This synthetic graph is designed to preserve the weights of all possible cuts (edges crossing between sets of vertices) within a specific error bound. For unweighted graphs, Linear Programming (LP) is used as a post-processing step to project synthetic edge weights back into a valid space while maintaining cut-preservation properties.

2. Cluster Packing (Binning)

A key technical innovation is the use of "binning" to manage how privacy noise scales. The additive error of synthetic graph releases often scales with the number of clusters ($k$). To mitigate this, the authors take the output of a non-private algorithm on the synthetic graph and "coarsen" it by merging small clusters into bins of a specific size. By keeping the effective number of clusters small (approximately $n^{1/4}$), the algorithm reduces the required privacy noise without significantly degrading the clustering objective.

A path graph partitioned into clusters $C_1, C_2, C_3$, illustrating the fundamental structure of correlation clustering where internal edges are similar (+) and external edges are dissimilar (-).

Key Results

The paper establishes several new upper and lower bounds for private correlation clustering:

  • Unweighted Complete Graphs: The algorithm achieves a 2.06-multiplicative approximation with an additive error of $O(n^{1.75}/\epsilon)$.
  • General Weighted Graphs: It achieves an $O(\log n)$-multiplicative approximation with an additive error of $O(n^{1.75}/\epsilon)$ under $(\epsilon, \delta)$-differential privacy.
  • Fixed Cluster Count: If the number of clusters $k$ is fixed and small, the additive error can be improved to $O(kn^{1.5})$.
  • Lower Bounds: The authors prove that for pure $\epsilon$-differential privacy, an additive error of at least $\Omega(n)$ is unavoidable, even on simple path graphs.

Discussion and Future Work

While the $O(n^{1.75})$ bound successfully breaks the quadratic barrier, it remains significantly higher than the theoretical $O(n \log n)$ error achievable by the computationally inefficient Exponential Mechanism. A major open question is whether a polynomial-time algorithm can bridge this gap and reach the $O(n \log n)$ additive error bound. Additionally, extending these results to handle highly skewed edge weights in general graphs remains a challenge for future research.

Summary updated

Abstract

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)$.
BibTeX
@inproceedings{bun2021differentially,
  author = {Mark Bun and Marek Eliás and Janardhan Kulkarni},
  title = {{Differentially Private Correlation Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=UyCJ_YcHKN},
}
Figure