Correlation clustering is a foundational technique in unsupervised machine learning, used to partition items based on pairwise similarity or dissimilarity. However, when these relationships involve sensitive data—such as private communications or transaction records—standard clustering algorithms risk exposing individual connections. Presented at ICML 2021, this paper initiates the formal study of Differentially Private (DP) Correlation Clustering. The authors bridge the gap between high-utility clustering and rigorous privacy guarantees, providing the first algorithms that achieve subquadratic additive error while maintaining the best-known approximation ratios from non-private literature.
The Challenge of Private Correlation Clustering
In correlation clustering, an algorithm is given a set of items and labels indicating whether pairs are "similar" (+) or "dissimilar" (-). The objective is to partition them into clusters that minimize disagreements (i.e., positive edges between different clusters or negative edges within the same cluster).
Standard Differential Privacy (DP) in this context (edge privacy) requires that the presence or label of any single edge remains hidden. The core challenge is that correlation clustering is inherently "global." A single edge change can theoretically ripple through the entire clustering structure. Previous non-private algorithms, when naively adapted for privacy, result in an additive error of $O(n^2)$. Because $O(n^2)$ is on the order of the total number of possible edges in the graph, this trivializes the output and renders the clustering practically useless.
Methodology: Private Synthetic Graph Release
Rather than attempting to inject noise into existing iterative clustering algorithms (which often rely on highly sensitive local decisions), the authors employ a Private Synthetic Graph Release strategy:
- Synthetic Release: Using advanced DP mechanisms, the authors generate a "synthetic" version of the input graph. While this synthetic graph differs from the original, it is mathematically guaranteed to preserve the weights of all "cuts" (edges between sets of vertices) within a specific error bound.
- Post-processing LP: For unweighted graphs, a Linear Program (LP) is utilized to ensure the synthetic graph remains consistent and unweighted, effectively merging separate private releases of positive and negative edges.
- Non-Private Approximation: Because of the post-processing property of differential privacy, any state-of-the-art non-private clustering algorithm (such as the 2.06-approximation by Chawla et al.) can be run on the synthetic graph without compromising privacy.
- Cluster Coarsening: To maintain subquadratic additive error, the authors introduce a "coarsening" step that merges small clusters into larger bins, limiting the impact of the noise introduced during the synthetic release phase.
Key Insights and Theoretical Bounds
This research is primarily theoretical, focusing on algorithmic bounds and complexity across general graph classes rather than empirical dataset evaluation.
A major conceptual breakthrough in the paper is the realization that the objective functions for correlation clustering (MinDis and MaxAgr) can be expressed entirely in terms of graph cuts. By leveraging DP tools specifically designed to preserve cut values, the authors successfully protect individual edges while keeping the overall clustering structure intact.
Key Results: * Complete Graphs: For unweighted complete graphs, the algorithm achieves an additive error of $\tilde{O}(n^{1.75}/\epsilon)$ with a $2.06$ multiplicative approximation. This marks the first result to successfully break the trivial $O(n^2)$ error barrier. * General Graphs: For general weighted graphs, the approach achieves an $O(\log n)$ approximation with the same $O(n^{1.75})$ additive error. * Fixed Clusters: If the number of clusters $k$ is fixed and small, the additive error can be further reduced to $O(kn^{1.5})$.
The Path Lower Bound: Using coding theory (specifically the Gilbert-Varshamov bound), the authors also establish a fundamental lower bound. They prove that even on a simple path graph, any private algorithm must incur an additive error of at least $\Omega(n/\epsilon)$. This demonstrates that while the $n^{1.75}$ upper bound might be improvable, achieving a "perfect" private clustering with zero additive error is mathematically impossible.
Conclusion and Open Problems
This paper successfully overcomes the quadratic error barrier in differentially private correlation clustering, offering a robust theoretical foundation for future work. However, a notable limitation remains: the gap between the $O(n^{1.75})$ upper bound and the $\Omega(n)$ lower bound is still substantial for practical applications on moderately sized datasets.
The authors highlight an exciting open problem for the field: Can we design a polynomial-time DP algorithm that matches the $O(n \log n)$ error achievable by the computationally inefficient exponential mechanism? Closing this theoretical gap remains the "holy grail" for private correlation clustering.
Summary updated