# An Approximation Algorithm for Graph Label Selection

arXiv: https://arxiv.org/abs/2605.18623 · HTML: https://mlsanity.com/paper/2605.18623/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 18 May 2026.

## Builds on (most cited first, 15 of 15)

- [A Survey of Deep Active Learning](https://mlsanity.com/paper/2009.00236/) (2020)
- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [xRAG: Extreme Context Compression for Retrieval-augmented Generation with One Token](https://mlsanity.com/paper/2405.13792/) (2024)
- [Prompt Compression with Context-Aware Sentence Encoding for Fast and Improved LLM Inference](https://mlsanity.com/paper/2409.01227/) (2024)
- [Graph Policy Network for Transferable Active Learning on Graphs](https://mlsanity.com/paper/2006.13463/) (2020)
- [GALAXY: Graph-based Active Learning at the Extreme](https://mlsanity.com/paper/2202.01402/) (2022)
- [Hierarchical Subquery Evaluation for Active Learning on a Graph](https://mlsanity.com/paper/1504.08219/) (2015)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Information Gain Propagation: a new way to Graph Active Learning with Soft Labels](https://mlsanity.com/paper/2203.01093/) (2022)
- [What is Dataset Distillation Learning?](https://mlsanity.com/paper/2406.04284/) (2024)
- [Active Learning on Trees and Graphs](https://mlsanity.com/paper/1301.5112/) (2013)
- [Diffusion-based Deep Active Learning](https://mlsanity.com/paper/2003.10339/) (2020)
- [Graph-Based Algorithms for Diverse Similarity Search](https://mlsanity.com/paper/2502.13336/) (2025)
- [An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time](https://mlsanity.com/paper/2511.03716/) (2025)
- [Improved Tree Sparsifiers in Near-Linear Time](https://mlsanity.com/paper/2511.06574/) (2025)

## Abstract (arXiv)

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 tildeO(log1.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.