提出首个近似比为log¹·⁵n的图标签选择算法，可高效选出代表性顶点。
An Approximation Algorithm for Graph Label Selection
- 基于标准预算约束，设计首个近似比达log¹·⁵n的算法
- 在真实数据集上验证，对大规模图仍保持高精度
- 适合需要可证明性能保障的大规模图分析场景
图标签选择问题中，给定一个n个顶点的图和预算k，目标是选出k个顶点的标签，以准确预测其余顶点的标签。该问题旨在从全图中提炼出一个小而具代表性的子集。本文首次提出在标准预算约束下，具有˜O(log¹·⁵n)近似比的算法。此前工作或依赖资源增强（允许使用远超k的标签顶点），或仅为无理论保证的启发式方法。最后，我们展示了该算法的实际启发式变体能扩展至比以往方法大得多的图，同时基本保持原有质量。
原文摘要 · Abstract (English)
In the graph label selection problem, one is given an $n$-vertex graph and a budget $k$, and seeks to select $k$ vertices whose labels enable accurate prediction of the labels on the remaining vertices. This problem formalizes distilling a small representative set from the whole graph. We present the first $\tilde{O}(\log^{1.5} n)$-approximation algorithm for graph label selection under the standard budget constraint. Prior work either relies on resource augmentation, allowing substantially more than $k$ labeled vertices, or consists primarily of heuristics without provable guarantees. Finally, we demonstrate that practical heuristic variants of our algorithm scale to significantly larger graphs than previous methods, while essentially retaining their quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。