An Approximation Algorithm for Graph Label Selection
It provides the first provable approximation for a fundamental graph labeling problem, addressing a gap where prior work required resource augmentation or lacked guarantees.
The paper presents the first approximation algorithm for graph label selection with a provable guarantee of O(log^{1.5} n) under a strict budget constraint, scaling to large graphs while maintaining quality.
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.