An Approximation Algorithm for Graph Label Selection
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917514014883840 |
|---|---|
| author | John, Josia Meierhans, Simon Gutenberg, Maximilian Probst |
| author_facet | John, Josia Meierhans, Simon Gutenberg, Maximilian Probst |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18623 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Approximation Algorithm for Graph Label Selection John, Josia Meierhans, Simon Gutenberg, Maximilian Probst Data Structures and Algorithms Machine Learning 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. |
| title | An Approximation Algorithm for Graph Label Selection |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2605.18623 |