用预测距离提升相关聚类的流式算法效率
Learning-Augmented Streaming Algorithms for Correlation Clustering
- 利用预测的顶点间距离指导聚类，改进流式处理
- 完整图下逼近比优于3，一般图下为O(log|E⁻|)
- 适合需要低内存高精度的实时聚类场景
研究相关聚类的流式算法。给定一个边以任意顺序到达的图，每条边标记为正或负，目标是将顶点划分为互不相交的簇，使不一致数最小。本文首次提出针对完全图和一般图的学习增强型流式算法，改进了最优空间-近似权衡。基于Cambus等（SODA'24）和Ahn等（ICML'15）的工作，算法使用由预测器提供的顶点对间距离预测。对于完全图，当预测质量良好时，算法实现优于3的近似比，仅需$ ilde{O}(n)$总空间；对于一般图，在预测质量良好时实现$O("log |E^-|)$近似比，且仅需$ ilde{O}(n)$总空间，优于现有非学习算法的空间效率。在合成数据和真实数据集上的实验表明，所提算法优于其非学习版本。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。