Near-Optimal Correlation Clustering with Privacy

Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labeling 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 additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters.
BibTeX
@inproceedings{cohenaddad2022near,
  author = {Vincent Cohen-Addad and Chenglin Fan and Silvio Lattanzi and Slobodan Mitrović and Ashkan Norouzi-Fard and Nikos Parotsidis and Jakub Tarnawski},
  title = {{Near-Optimal Correlation Clustering with Privacy}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=wQVjGP5NbP9},
}
Figure