Sparse-pivot: Dynamic correlation clustering for node insertions

The authors consider the classic Correlation Clustering problem which, given a complete graph with edges labeled either + or -, the goal is to find a partition of the vertices so as to minimize the number of + edges across parts plus the number of - edges within parts. The has received a lot of attention since its introduction in the early 2000s.

In this paper, the authors consider the dynamic setting where nodes are iteratively inserted (and not removed) into the dataset and the goal is to maintain a partition that minimizes the Correlation Clustering objective at all time, while minimizing the total running time (a.k.a update time).

The authors improve an ICML'24 paper which showed how to maintain a very large constant factor approximation to the problem while making polylog n database queries (here a database query is a query of one of the following types: (1) retrieving the degree of a node v; (2) selecting a random neighbor of v; and (3) checking whether two nodes u and v are connected by an edge). In this paper, the authors provide an algorithm with polylog n update time that achieves a 20+epsilon-approximation.

The algorithm is a refinement of the classic pivot algorithm for Correlation Clustering, called Sparse-Pivot, which combines ideas from previous work on streaming algorithms, post-processing the clusters obtained, and a new sampling strategy to define the pivots (looking at O(log n) random neighbors).

This paper presents "SPARSE-PIVOT," a new dynamic correlation clustering algorithm designed for node insertions. The algorithm builds upon a variant of the PIVOT algorithm and aims to improve the update time and approximation factor compared to the existing state-of-the-art algorithm by Cohen-Addad et al. (ICML 2024). The main algorithmic idea is to combine a fast approximate pivot selection using random sampling with a refinement step that removes poorly clustered nodes. The paper claims an amortized update time of $O(\log^{O(1)}(n))$ and an approximation factor of $20 + \epsilon$. The theoretical analysis is complemented by experimental evaluation, showing better performance to previous methods.

This paper studies the correlation clustering problem on graphs in the dynamic setting. This variant of clustering is an important problem both in theory and practive, and has been extensively studied in different computational models.

Traditionally, most of the algorithms in the dynamic graphs literature consider the setting where edges of the underlying graphs undergo updates, i.e., they are inserted or deleted. This paper considers a more challenging and the less-studied setting of node insertions; when a node is added, then all its incident neighbours are revelaed at intsertion. Naturally, one could simple simluate node insertions by inserting all edges incident to the inserted node – but since nodes can have deegree up to O(n), this leads to undiserable times.

The paper under reivew studies algorithms that beat such trivial bounds. In fact, for the correlation clustering problem, they propose an algorithm that approximates the optimal correlation clustering objective up to a factor of ~20, and runs in poly-logarithmic amortized time per node insertions and even random deletions. The prioir work by Cohen-Addad et al. achieved similar runtime guarantees, but at the cost of a much constant approximation.

The starting point of their algorithm is a 5-approximate algorithm due to Behnezhad et al. (a variant of the well-known PIVOT algorithm) in the semi-streaming setting. The idea is to take this algorithm and adapt it to the dynamic setting. Some technical ideas involve: picking random ranks for each node, and using this rank to classify nodes depending on their degree, and finally doing some clean-up, so that bad nodes cannot belong to clusters, etc. While these algorithmic steps make sense for the problem at hand, the adaption and especially the analysis are quite cumbersome and require special care. These type of algorithms are in my opinon the whole grail in algorith mdesign; easy to describe and understand, but not so trivial to analyse!

I’m not very familiar with the algorithm by Cohen-Addad et al., but the algorirthm that the paper proposes looks very natural and the right one to me.

update after rebuttal

Thanks for the rebuttal. I keep my score as is.

This paper introduces a new Correlation Clustering algorithm for node insertion / deletion in a dynamic setting. Upon node arrival its edges with all existing nodes are revealed, and we are allowed to make changes to the maintained clustering solution. The algorithm has constant approximation factor and sublinear amortized processing time per node arrival. which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. Empirical results show the new algorithm to outperform state of the art benchmarks.

This paper addresses dynamic correlation clustering with a significant improvement in approximation factors and sublinear update times. It builds upon Pivot-based methods, refining them with a novel procedure to handle poorly formed clusters. The algorithm achieves a constant-factor approximation and delivers superior empirical results, consistently outperforming prior approaches.

Reviewers commented on the clarity and organization, highlighting how it bridges theory and practice. Despite the algorithm’s seemingly simple design, the underlying analysis is nontrivial and yields substantial benefits in both solution quality and speed. Overall, this work marks an important advance in dynamic clustering research and suggests intriguing directions for future explorations.