Algorithms improve grouping accuracy as items arrive in random order
Competitive Random-Order Correlation k-Clustering
Data Structures and Algorithms
Summary
Grouping objects based on similarities is a common problem but is hard when the number of groups is fixed. The authors found a way to always get a solution within a reasonable range of the best, no matter how many groups there are. They focused on a scenario where objects arrive one by one in random order and you must decide their group immediately. Their method guarantees good performance compared to an ideal solution and improves upon previous limits for this online setting.
What this means in practice
- •For data engineers: Automatically assign data points to clusters in real-time as data streams in, with guarantees on clustering quality for many clusters.
- •For network operators: Group network nodes dynamically based on observed connections arriving over time to optimize maintenance or routing decisions.
Authors
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman, Omer Wasim, Tegan Wilson
Abstract
Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is to compute a partition of the vertex set such that the total number of disagreements, i.e. the sum of edges between clusters, and non-edges within clusters, is minimized. In this paper, we study correlation $k$-clustering, in which the total number of clusters is restricted to $k$. Correlation $k$-clustering is NP-hard, and while previous work has presented a polynomial time approximation scheme for constant $k$, there are no known results for general $k$. Our first result is a polynomial-time constant-factor approximation algorithm for correlation $k$-clustering for general $k$. The main focus of this work is in the more challenging online setting. Noting that the best competitive ratio under adversarial arrivals is known to be $Ω(n)$, we concentrate on the well-studied random-order model, where vertices arrive in random order and on arrival of a vertex, edges to its earlier-arrived neighbors are revealed. We prove a surprising lower bound of $Ω(\log k)$-competitiveness for any online algorithm, which can be extended to $Ω(\log n)$ when $k = \text{poly}(n)$. Finally, the main result of this paper is a polylogarithmic upper bound on the competitive ratio for correlation $k$-clustering, using an algorithm inspired by the classic Pivot algorithm for correlation clustering.