mlsanityData to 14 Oct 2026

An Approximation Algorithm for Graph Label Selection

arXiv 2605.18623 ↗First posted 18 May 2026cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

15 of 30 references.

References · 15

  1. 2020A Survey of Deep Active Learningcited by 554
  2. 2021Dataset Distillation with Infinitely Wide Convolutional Networkscited by 218
  3. 2024xRAG: Extreme Context Compression for Retrieval-augmented Generation with One Tokencited by 125
  4. 2024Prompt Compression with Context-Aware Sentence Encoding for Fast and Improved LLM Inferencecited by 53
  5. 2020Graph Policy Network for Transferable Active Learning on Graphscited by 50
  6. 2022GALAXY: Graph-based Active Learning at the Extremecited by 29
  7. 2015Hierarchical Subquery Evaluation for Active Learning on a Graphcited by 21
  8. 2015S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classificationcited by 20
  9. 2022Information Gain Propagation: a new way to Graph Active Learning with Soft Labelscited by 16
  10. 2024What is Dataset Distillation Learning?cited by 13
  11. 2013Active Learning on Trees and Graphscited by 10
  12. 2020Diffusion-based Deep Active Learningcited by 10
3 more
  1. 2025Graph-Based Algorithms for Diverse Similarity Searchcited by 3
  2. 2025An Improved Quality Hierarchical Congestion Approximator in Near-Linear Timecited by 1
  3. 2025Improved Tree Sparsifiers in Near-Linear Timecited by 1

Built on by

Not cited yet.