An Approximation Algorithm for Graph Label Selection
Josia John, Simon Meierhans, Maximilian Probst Gutenberg · 2026
Read An Approximation Algorithm for Graph Label Selection by Josia John, Simon Meierhans, Maximilian Probst Gutenberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18623.txt.
Introduction
Josia John and two co-authors ask how few labeled points can stand for a whole graph. Given n nodes and a budget of k picks, their method picks the k points whose labels best forecast the rest. It gives the first log to the three halves guarantee under the usual budget rule. Older routes either spent far more labeled points than the budget allowed or gave rules of thumb with no proof. Lighter versions handle bigger graphs than older tools could, with quality left all but intact.
Catalog record
| CREATOR | Josia John, Simon Meierhans, Maximilian Probst Gutenberg |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51526 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18623
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Approximation Algorithm for Graph Label Selection Josia John, Simon Meierhans, Maximilian Probst Gutenberg Abstract In the graph label selection problem, one is given an n n -vertex graph and a budget k k , and seeks to select k 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 O ~ ( log 1.5 n ) \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 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. 1 Introduction Selecting a representative small subset of a large data set is a crucial task in various areas of machine learning, such as speeding up training ( 21 ; 28 ) and selecting diverse additional context for passing to a large language model (LLM) for improved inference ( 18 ; 6 ; 4 ) . In active learning, the training set, i.e. the labeled set , is not fixed but rather chosen by the learning algorithm itself to be as representative of the entire dataset as possible. For pairwise similarities between data points represented as a graph G=(V,E,w) , 10 introduced a natural objective for selecting such a labeled set. They fix k to be the maximum number of data points to be labeled, and aim to rule out that a large cluster of unlabeled points with few connections to the rest of the data set exists. Formally, they focus on selecting a set of nodes L , under the cardinality constraint |L|\leq k , which maximize the objective \Psi(L)\coloneqq\min_{C\subseteq V\setminus L}\frac{w(C,V\setminus C)}{|C|}. This yields the Graph Label Selection Problem (GLS), which requires finding \text{OPT}_{k}\coloneqq\max_{L\subset V:|L|\leq k}\Psi(L). Despite its early and natural formulation, algorithms with theoretical guarantees were lacking for a long time. 10 give some practical heuristics to maximize \Psi(L) . 5 presented an algorithm with theoretical guarantees on unweighted trees. Recently, 7 showed that the problem is NP-hard. Therefore, it is natural to consider approximation algorithms for this problem. There are two natural notions of approximation for this problem. The weaker notion, an \alpha -resource augment algorithm, uses budget \alpha\cdot k but is competitive with \text{OPT}_{k} , i.e., the optimal value obtained with much smaller budget k . An O(\log n) -resource algorithm was recently given in ( 7 ) . In ( 7 ) , it is stated as an interesting open problem to achieve a stronger and more natural version of approximation: they ask whether an algorithm exists that uses the given k and is \beta -competitive in \text{OPT}_{k} , i.e. the solution has quality at least \text{OPT}_{k}/\beta . In this article we resolve this question by presenting an efficient \tilde{O}(\log^{1.5}n) approximation algorithm for maximizing \Psi(L) , which does not rely on resource augmentation. Additionally, a relaxed version of our new algorithm has better runtime and can thus be scaled to larger instances. Theorem 1.1 . Given a graph G=(V,E,w) with weights in [1,\text{poly}(n)] , and a budget k\in\mathbb{N} , there exists a polynomial-time algorithm that returns a set L^{\prime} with • |L^{\prime}|\leq k and • \beta\cdot\Psi(L^{\prime})\geq\text{OPT}_{k} where \beta\in\tilde{O}(\log^{1.5}n) . To achieve our results, we go beyond previous greedy approaches that select labeled points one at a time. Instead, our algorithm captures global interactions between the labeled points, which is necessary for obtaining a guarantee on the approximation with a fixed budget. 1 1 1 Star graphs are a simple example that highlight this behavior. If the budget is k=n-1 , it is imperative not to select the center of the star which is the obvious greedy choice. Additionally, our algorithm is optimal on weighted trees (See Appendix A ) and seamlessly extends to vertex importances (See Appendix B ). We complement this theoretical result with a proof-of-concept experiment. We give an implementation of the algorithm where we replace the key primitive of finding sparse cuts with simple heuristics. Even with these simple heuristics, our algorithm essentially matches the quality of previous algorithms ( 7 ; 10 ; 5 ) while being significantly more scalable. Overview. Previous algorithms build the set L one by one. But the objective \Psi(L) is neither submodular nor supermodular ( 7 ) . This means it is unclear how to choose the next vertex without resorting to heuristics. We take a new approach and select the set L using Dynamic Programming. To be able to apply Dynamic Programming, we reduce the graph label selection problem twice. First, we reduce it to solving a problem on a weighted binary tree using a tree cut sparsifier . A tree cut sparsifier is a tree T spanning the same vertex set as the input graph such that every cut (S,V\setminus S) has approximately the same weight in G and in T . In ( 23 ) , a polynomial-time algorithm is given that constructs a tree cut sparsifier with approximation factor \beta=\tilde{O}(\log^{1.5}n) . We give the reduction in Section 3 . In Section 4 , we use a similar reduction as in ( 7 ) to reduce to a flow problem. However, while 7 need to solve this flow problem on a general graph, for us, it suffices to solve it on a binary tree. This allows us, in the final step in Section 5 , to solve the flow problem via Dynamic Programming (bypassing the need to solve the maximum flow problem). Related Work. • Active learning: We restrict our discussion of related work to graph-based approaches, and refer the reader to ( 25 ; 24 ) for surveys on classical and deep active learning, respectively. The problem of selecting L such that it maximizes our knowledge about the other vertices in the graph has been studied thoroughly ( 31 ; 10 ; 5 ; 8 ) from both combinatorial and deep learning ( 19 ; 15 ; 13 ; 30 ; 29 ) based angles. • Tree Cut Sparsifiers: The first polynomial-time algorithms for tree cut sparsifiers with polylogarithmic approximation was given by 11 . The above result by 23 improves the approximation factor significantly. A lower bound of \Omega(\log n) in the approximation, even existentially, is sketched in ( 23 ) . More recently, near-linear time algorithm achieving an approximation of \tilde{O}(\log^{2}n) were given ( 22 ; 1 ; 12 ) . • Diversity Sampling: Our algorithm can be seen as a form of diversity sampling. We refer the reader to ( 2 ) for a recent graph based algorithm in this space. 2 Preliminaries Misc. In this article, \tilde{O}(f(n)) -notation suppresses logarithmic factors in f(n) , i.e. is in O(f(n)\log^{c}(f(n))) for some constant c>0 . Graphs. We consider undirected, weighted graphs G=(V,E,w) where V denotes the vertex set and E\subseteq V\times V denotes the edge set. The function w:E\mapsto\mathbb{R} contains the non-negative edge weights. We let n denote the number of vertices |V| . For some set A\subseteq V , we denote by G[A] the subgraph induced by A , i.e. the