Online and Consistent Correlation Clustering

Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos ParotsidisICML 2022 · OpenReview

Introduction

Clustering data that evolves over time usually forces a choice between a high-quality solution and a stable one. This paper introduces Agree-On, the first online correlation clustering algorithm that maintains a constant-factor approximation of the optimal solution while guaranteeing that each node only changes its cluster a logarithmic number of times ($O(\log n)$). By using "lazy" updates, the authors prove—and demonstrate experimentally—that it is possible to achieve both high-quality clusters and extreme stability.

The Challenge of Online Correlation Clustering

In Correlation Clustering, we are given a graph where edges are labeled as either positive (similar) or negative (dissimilar). The goal is to partition the nodes into clusters to minimize "disagreements": negative edges inside a cluster or positive edges between different clusters.

In many real-world applications, such as social networks or document deduplication, data arrives online—nodes appear one by one. Standard online algorithms face a harsh reality: if you never allow a node to change its cluster once assigned (zero "recourse"), the quality of your clustering can be $n$ times worse than the optimum. However, if you re-cluster from scratch every time a new node arrives, the assignments become "inconsistent." A node might jump between different clusters constantly, making the system unpredictable and expensive to maintain. This paper seeks the "sweet spot": maintaining a constant-factor approximation with minimal cluster re-assignments.

The Agree-On Algorithm

The authors propose the Agree-On algorithm, which builds upon a static "Agreement" subroutine. The core strategy relies on lazy updating through three main phases:

  1. Offline Re-clustering: When a new node $v_t$ arrives, the algorithm runs a static clustering algorithm on the current graph to determine the "ideal" current state.
  2. Initial Assignment: Instead of blindly following the new ideal, the algorithm tries to map the new clusters back to the old ones. It uses specific rules to identify "evolving clusters." If a new cluster largely overlaps with an old one, it retains the old cluster's ID.
  3. Assignment Refinement (Lazy Updates): The algorithm tracks an Origin Cluster—the version of the cluster when its ID was first assigned. It only forces a node to change to a new cluster ID if the current cluster has grown significantly (by a factor of at least 1.5x) compared to its origin.

By only moving nodes when clusters have grown substantially, the algorithm prevents "jitter" while ensuring the clustering doesn't drift too far from the mathematical optimum.

Experimental Setup

The authors evaluated their algorithm on four real-world graph datasets from the SNAP library: musae-facebook, email-Enron, ca-AstroPh, and cit-HepTh. Notably, the cit-HepTh dataset (a citation network of high-energy physics papers) was used as a primary benchmark because it includes natural timestamps, providing a realistic arrival order for the nodes.

Key Results and Insights

Theoretical Guarantees

The paper reinforces that a small amount of recourse (moving nodes) is the key to breaking the $\Omega(n)$ lower bound of strictly online algorithms. The most significant theoretical insight is that $O(\log n)$ recourse is sufficient to maintain a constant approximation. The authors also provide a matching lower bound, proving that no algorithm can do better than $\Omega(\log n)$ while maintaining a constant approximation.

Empirical Stability

On real-world data, the algorithm proved to be even more stable than the theory suggested.

Maximum recourse per node across datasets

As shown in the table above, the maximum recourse per node for Agree-On was exactly 1 across all tested datasets, meaning no node ever changed its cluster more than once. In contrast, the popular PIVOT baseline saw nodes changing clusters up to 14 times.

Clustering Quality

Despite its strict stability, Agree-On does not sacrifice clustering quality.

Correlation Clustering Objective over time

Agree-On consistently produced lower "disagreement" costs (the clustering objective) than the PIVOT baseline across almost all arrival points in the datasets. Furthermore, while the algorithm involves running a static clustering step, it can be implemented to run in $O(nm)$ total time for the entire sequence, making it practical for large graphs.

Limitations and Future Work

While the approximation is "constant," the paper focuses on proving the existence of this constant rather than optimizing it to be as small as possible (e.g., getting closer to the best-known offline factor of 2.06). Additionally, the current work focuses on unweighted graphs where edges are strictly $\{-1, +1\}$. Extending these tight recourse bounds to arbitrary edge weights remains an open challenge. Finally, the authors suggest that applying this "consistent" framework to other types of clustering, like k-means or facility location in online settings, is a promising next step.

Summary updated

Abstract

In the correlation clustering problem the input is a signed graph where the sign indicates whether each pair of points should be placed in the same cluster or not. The goal of the problem is to compute a clustering which minimizes the number of disagreements with such recommendation. Thanks to its many practical applications, correlation clustering is a fundamental unsupervised learning problem and has been extensively studied in many different settings. In this paper we study the problem in the classic online setting with recourse; The vertices of the graphs arrive in an online manner and the goal is to maintain an approximate clustering while minimizing the number of times each vertex changes cluster. Our main contribution is an algorithm that achieves logarithmic recourse per vertex in the worst case. We also complement this result with a tight lower bound. Finally we show experimentally that our algorithm achieves better performances than state-of-the-art algorithms on real world data.
BibTeX
@inproceedings{cohenaddad2022online,
  author = {Vincent Cohen-Addad and Silvio Lattanzi and Andreas Maggiori and Nikos Parotsidis},
  title = {{Online and Consistent Correlation Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=uCXjU024Ac},
}
Figure