Correlation clustering is a classic unsupervised learning problem with broad applications, from community detection to duplicate removal and automated labeling. However, the pairwise preference data used in these tasks—such as social connections or medical similarities—often contains highly sensitive information.
Presented at NeurIPS 2022, this paper introduces a simple, computationally efficient algorithm for correlation clustering that strictly adheres to Differential Privacy (DP). By achieving a constant-factor approximation with a nearly optimal additive error, the authors significantly close the gap between private and non-private clustering performance.
The Challenge of Private Correlation Clustering
In standard correlation clustering, an algorithm receives a set of items and pairwise preferences (e.g., indicating whether two items should be grouped together or kept apart). The objective is to partition the items to minimize "disagreements"—specifically, positive edges between different clusters and negative edges within the same cluster.
Differential Privacy provides a mathematical guarantee that the presence or absence of a single edge will not significantly alter the algorithm's output, thereby protecting individual relationships. Unfortunately, privacy typically comes at the cost of accuracy. Previous DP algorithms for correlation clustering suffered from massive "additive errors" (errors that scale with the size of the dataset rather than the optimal solution), historically hovering around $O(n^{1.75})$.
A major technical hurdle in DP graph algorithms is the "bridge" problem: computing connected components is highly sensitive because a single edge can act as a bridge connecting two massive clusters. Altering that one edge drastically changes the output, making it difficult to maintain privacy without injecting overwhelming amounts of noise.
Methodology: Noised Agreement
To overcome these challenges, the authors adapt a recent non-private parallel algorithm for correlation clustering, carefully "privatizing" each step using Laplacian noise and rigorous sensitivity analysis. Their algorithm, Private Correlation Clustering using Noised Agreement, operates in four primary phases:
- High-Degree Filtering: The algorithm first identifies "high-degree" vertices. To do this privately, it adds Laplace noise to the degree of every vertex. Only vertices whose noisy degree exceeds a specific threshold are processed further.
- Noised Agreement: For every pair of vertices, the algorithm evaluates whether they "agree" by having similar neighborhoods. Laplace noise is added to the size of their neighborhood intersection. If this noisy intersection is sufficiently large, the edge is retained. This step naturally suppresses the "bridge" problem by ensuring that edges are only kept if they are supported by a robust shared neighborhood.
- Heavy vs. Light Classification: Vertices that lose too many neighbors during the filtering phase are classified as "light" and are eventually isolated into singleton clusters. This classification threshold is also protected using injected noise.
- Clustering via Connected Components: Finally, the algorithm computes the connected components of the remaining "heavy" vertices. Because the noised agreement step ensures a robust graph structure, the authors prove that a single edge change is highly unlikely to bridge or split components, making this final step inherently private.
Unlike mechanisms that require exponential time, this algorithm runs in polynomial time, making it theoretically viable for large-scale applications.
Theoretical Guarantees and Key Results
As a theoretical paper, the study does not rely on empirical datasets but instead validates its claims through rigorous mathematical proofs of privacy and approximation guarantees.
The authors establish a new state-of-the-art upper bound for unweighted complete graphs. For any privacy parameters $\epsilon$ and $\delta$, the algorithm returns a solution with a cost of:
$$ O(1) \cdot \text{OPT} + O\left(\frac{n \log^2 n \log(1/\delta)}{\epsilon^2}\right) $$
This reduces the additive error from $O(n^{1.75})$ to $O(n \log^2 n)$, a massive improvement. Furthermore, the algorithm maintains a constant approximation ratio ($O(1)$), meaning the multiplicative error scales linearly with the optimal non-private solution.
Crucially, the authors also prove a lower bound. They demonstrate that any $(\epsilon, \delta)$-DP algorithm in this setting must incur an additive error of at least $\Omega(n)$. Because their upper bound is $O(n \log^2 n)$, the proposed algorithm is "near-optimal," leaving very little room for future theoretical improvement.
Limitations and Future Directions
While the theoretical bounds are tight, the paper outlines several limitations and avenues for future research:
- Complete Graphs Only: The primary results apply to unweighted complete graphs (where every pair has a defined positive or negative preference). Real-world graphs, however, are often sparse or weighted. Extending these near-optimal bounds to general weighted graphs remains an exciting open challenge.
- Constant Factors: Although the multiplicative error is $O(1)$, the authors do not optimize this constant. In practice, a large constant factor could still yield sub-optimal clusterings.
- Practical Implementation: For the additive error to be negligible relative to $n$, the graph must be quite large or dense. Future work is needed to make these algorithms practical for smaller, real-world datasets where DP noise might currently overwhelm the underlying signal.
Summary updated