随机删边的不完全图上，相关聚类逼近比显著优于普通图。
Correlation Clustering with Random Partial Information
- 从完整带符号图中随机删边生成不完全图，研究其聚类性能
- 对min-max和min-disagreement目标均获得优于O(√n)的逼近比
- 理论与实验结合，适用于随机缺失数据场景的聚类任务
相关聚类是基础的无监督学习问题。在完全图上，最小分歧和最小最大目标均有常数倍近似算法；但在一般（非完全）图上，最佳保证分别退化为O(log n)和O(√n)。这一差距引发疑问：是否存在一类不完全图可规避一般图的下界，逼近完全图的性能？本文研究从一个完整带符号图G中随机抽样得到的图类，其中每条边以概率q独立被删除。对于此类图实例，在min-max和min-disagreement目标下，我们证明了依赖于q的近似保证，显著优于一般图的已知界限。实验结果进一步表明，所提算法的近似比接近完全图的表现，且优于一般非完全图的最坏情况界。
原文摘要 · Abstract (English)
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。