Learning-Augmented Streaming Algorithms for Correlation Clustering
This work addresses the challenge of efficient correlation clustering in streaming settings for data processing applications, representing an incremental improvement by integrating predictions into existing frameworks.
The paper tackles the problem of correlation clustering in streaming graphs by introducing learning-augmented algorithms that use predictions of pairwise distances to improve space-approximation tradeoffs. For complete graphs, it achieves a better-than-3 approximation with O~(n) space, and for general graphs, it achieves an O(log |E^-|) approximation with O~(n) space, outperforming non-learning methods in experiments.
We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partition the vertices into disjoint clusters, such that the number of disagreements is minimized. In this paper, we give the first learning-augmented streaming algorithms for the problem on both complete and general graphs, improving the best-known space-approximation tradeoffs. Based on the works of Cambus et al. (SODA'24) and Ahn et al. (ICML'15), our algorithms use the predictions of pairwise distances between vertices provided by a predictor. For complete graphs, our algorithm achieves a better-than-$3$ approximation under good prediction quality, while using $\tilde{O}(n)$ total space. For general graphs, our algorithm achieves an $O(\log |E^-|)$ approximation under good prediction quality using $\tilde{O}(n)$ total space, improving the best-known non-learning algorithm in terms of space efficiency. Experimental results on synthetic and real-world datasets demonstrate the superiority of our proposed algorithms over their non-learning counterparts.