An Approximation Algorithm for Graph Label Selection

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.

We develop an algorithm to pick a small number of representative vertices from a graph. In a social friendship network, that could be used to design a survey that represents all people as well as possible. Our algorithm comes with the first provable guarantee of its kind, and in practice runs much faster than previous methods while matching their quality. Picking representative subsets from graphs comes up a lot in machine learning, including in how large language models are given context.