Introduction
Correlation clustering is a robust framework for unsupervised learning that avoids the need to pre-specify the number of clusters. Given a set of items and a list of pairwise preferences—indicating whether two items should be grouped together or kept apart—the goal is to find a partition that minimizes the total number of disagreements (the sum of missing edges within clusters and existing edges between clusters).
While correlation clustering is widely used in applications ranging from social network analysis to medical record deduplication, these datasets often contain highly sensitive information. Protecting the privacy of individual relationships (edges) in the input graph is paramount. This paper addresses the challenge of designing a Differentially Private (DP) algorithm for correlation clustering that maintains high utility while providing rigorous privacy guarantees.
The Privacy-Utility Trade-off
In the context of differential privacy, the challenge is to ensure that the presence or absence of a single edge in the input graph does not significantly alter the resulting clustering. Prior to this work, private correlation clustering algorithms suffered from substantial "additive error"—the extra cost incurred solely to satisfy privacy constraints.
Previous state-of-the-art frameworks exhibited an additive error of $O(n^{1.75})$ for a graph with $n$ nodes. Given that the total number of possible edges is $O(n^2)$, an error of $n^{1.75}$ is quite large for practical applications. The authors of this paper sought to bridge this gap, aiming for an algorithm that achieves a constant-factor multiplicative approximation with an additive error approaching the theoretical lower bound.
Methodology: Private Graph Trimming
The authors adapt a non-private parallel algorithm (specifically from [CALM+21]) and introduce a three-step "privatization" pipeline. The core idea is to transform the input graph into a stable structure where the connected components represent the final clusters.
- Noised Agreement: In non-private settings, two nodes are said to "agree" if their neighborhoods are sufficiently similar. To privatize this, the authors calculate the intersection of neighborhoods and inject Laplace noise into the result. Edges are only retained between nodes that maintain a high agreement score despite the noise.
- Noised Lightness: The algorithm identifies "light" vertices—nodes that have lost a significant portion of their original neighbors during the agreement step. Laplace noise is again used to hide the exact identity of these vertices, ensuring that the removal process itself does not leak sensitive structural information.
- Private Connected Components: Finally, the algorithm discards edges connected to light vertices and identifies the connected components of the remaining graph. These components form the output clusters.
The technical breakthrough lies in the analysis of "bad events." The authors prove that the graph trimming process is robust enough that "bridge" edges—edges whose removal would fundamentally change the cluster decomposition—are extremely unlikely to exist. This stability is what allows the algorithm to satisfy $(\epsilon, \delta)$-differential privacy.
Key Results and Theoretical Bounds
The paper provides both a new upper bound (via the proposed algorithm) and a new lower bound, effectively characterizing the complexity of the problem:
- Near-Optimal Additive Error: The algorithm achieves an additive error of $O\left(\frac{n \log^2 n \log(1/\delta)}{\epsilon^2}\right)$. This is a significant improvement over the previous $O(n^{1.75})$ and concurrent work reaching $O(n^{1.5})$.
- Constant Multiplicative Approximation: The algorithm maintains an $O(1)$ multiplicative approximation, ensuring that the clustering quality scales linearly with the optimal non-private solution.
- Optimality Proof: The authors established a new lower bound of $\Omega(n)$ for additive error on complete graphs. This confirms that their $O(n \log^2 n)$ result is optimal up to logarithmic factors.
Discussion and Future Directions
This work demonstrates that simple mechanisms, like Laplace noise, can be highly effective when applied to the right stages of a graph-trimming process. By focusing on the stability of connected components, the authors have provided a path toward practical, private clustering.
However, some limitations remain. The current results are primarily optimized for unweighted complete graphs. Extending these tight bounds to general or weighted graphs—where edge weights represent varying degrees of similarity—remains an open area for research. Additionally, while the algorithm is theoretically efficient, the constant factors involved in the $O(1)$ approximation may be large, necessitating further empirical tuning for use on smaller, real-world datasets.
Summary updated