An Approximation Algorithm for Graph Label Selection
Josia John 1 Maximilian Probst Gutenberg 1 Simon Meierhans 1
arXiv:2605.18623v1 [cs.DS] 18 May 2026
Abstract
ists. Formally, they focus on selecting a set of nodes L, under the cardinality constraint |L| ≤ k, which maximize the objective
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 Õ(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.
Ψ(L) := min
C⊆V \L
w(C, V \ C) . |C|
This yields the Graph Label Selection Problem (GLS), which requires finding OPTk :=
max
Ψ(L).
L⊂V :|L|≤k
Despite its early and natural formulation, algorithms with theoretical guarantees were lacking for a long time. Guillory & Bilmes (2009) give some practical heuristics to maximize Ψ(L). Cesa-Bianchi et al. (2010) presented an algorithm with theoretical guarantees on unweighted trees. Recently, Cohen-Addad et al. (2025) 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 α-resource augment algorithm, uses budget α · k but is competitive with OPTk , i.e., the optimal value obtained with much smaller budget k. An O(log n)-resource algorithm was recently given in (Cohen-Addad et al., 2025).
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 (Nguyen et al., 2021; Yang et al., 2024) and selecting diverse additional context for passing to a large language model (LLM) for improved inference (Liskavets et al., 2025; Cheng et al., 2024; Bateni et al., 2025).
In (Cohen-Addad et al., 2025), 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 β-competitive in OPTk , i.e. the solution has quality at least OPTk /β. In this article we resolve this question by presenting an efficient Õ(log1.5 n) approximation algorithm for maximizing Ψ(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.
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), Guillory & Bilmes (2009) 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 ex-
Theorem 1.1. Given a graph G = (V, E, w) with weights in [1, poly(n)], and a budget k ∈ N, there exists a polynomial-time algorithm that returns a set L′ with
1 Department of Computer Science, ETH Zurich, Zurich, Switzerland. Correspondence to: Josia John <[email protected]>, Maximilian Probst Gutenberg <[email protected]>, Simon Meierhans <[email protected]>.
• |L′ | ≤ k and • β · Ψ(L′ ) ≥ OPTk
Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).
where β ∈ Õ(log1.5 n). 1
An Approximation Algorithm for Graph Label Selection
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
& Bilmes, 2009; Cesa-Bianchi et al., 2010; Dasarathy et al., 2015) from both combinatorial and deep learning (Mac Aodha et al., 2014; Kushnir & Venturi, 2020; Hu et al., 2020; Zhang et al., 2022b;a) based angles. • Tree Cut Sparsifiers: The first polynomial-time algorithms for tree cut sparsifiers with polylogarithmic approximation was given by Harrelson et al. (2003). The above result by Räcke & Shah (2014) improves the approximation factor significantly. A lower bound of Ω(log n) in the approximation, even existentially, is sketched in (Räcke & Shah, 2014). More recently, near-linear time algorithm achieving an approximation of Õ(log2 n) were given (Räcke et al., 2014; Agassy et al., 2025; Henzinger et al., 2025).
Additionally, our algorithm is optimal on weighted trees (See Section A) and seamlessly extends to vertex importances (See Section B). We complement this theoretical result with a proof-ofconcept 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 (Cohen-Addad et al., 2025; Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010) while being significantly more scalable.
• Diversity Sampling: Our algorithm can be seen as a form of diversity sampling. We refer the reader to (Anand et al., 2025) for a recent graph based algorithm in this space.
Overview. Previous algorithms build the set L one by one. But the objective Ψ(L) is neither submodular nor supermodular (Cohen-Addad et al., 2025). 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.
2. Preliminaries Misc. In this article, Õ(f (n))-notation suppresses logarithmic factors in f (n), i.e. is in O(f (n) logc (f (n))) for some constant c > 0.
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 \ S) has approximately the same weight in G and in T . In (Räcke & Shah, 2014), a polynomial-time algorithm is given that constructs a tree cut sparsifier with approximation factor β = Õ(log1.5 n). We give the reduction in Section 3. In Section 4, we use a similar reduction as in (Cohen-Addad et al., 2025) to reduce to a flow problem. However, while Cohen-Addad et al. (2025) 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).
Graphs. We consider undirected, weighted graphs G = (V, E, w) where V denotes the vertex set and E ⊆ V × V denotes the edge set. The function w : E 7→ R contains the non-negative edge weights. We let n denote the number of vertices |V |. For some set A ⊆ V , we denote by G[A] the subgraph induced by A, i.e. the graph obtained when restricting to the set of vertices in A. Trees. We use LT to denote the leaves of a tree T . If the tree is rooted, we denote the subtree of vertex v by Tv . Cuts. We define the weight of a cut A ⊆ V in some graph G = (V, E, w):
Related Work. X
wG (A, V \ A) := • Active learning: We restrict our discussion of related work to graph-based approaches, and refer the reader to (Settles, 2009; Ren et al., 2021) for surveys on classical and deep active learning, respectively.
w(u, v).
(u,v)∈E u∈A,v∈V \A
We also define the minimum cut separating two disjoint sets A, B ⊆ V, A ∩ B = ∅:
The problem of selecting L such that it maximizes our knowledge about the other vertices in the graph has been studied thoroughly (Zhu et al., 2003; Guillory
λG (A, B) :=
min
A⊆S⊆V \B
w(S, V \ S).
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.
Graph Label Selection (GLS) For convenience, we restate the definition of the Graph Label Selection Problem 2
An Approximation Algorithm for Graph Label Selection
here. We define the optimal solution to GLS on a graph G = (V, E, w) as
Proof. For the upper bound, we derive b T (L) = Ψ
OPTk :=
max
Ψ(L),
min ψTLT (S)
S⊆LT \L
λT (S, LT \ S) |S| S⊆LT \L 3.1 α · wG (S, V \ S) ≤ min |S| S⊆V \L
L⊂V :|L|≤k
=
where w(C, V \ C) . |C| C⊆V \L
Ψ(L) := min
min
= α · min ψG (S) = α · ΨG (L). S⊆V \L
3. Reducing to Binary Tree
The lower bound follows analogously.
Our algorithm reduces the graph label selection problem from a general graph to a related problem on a binary tree. We do so by first constructing a tree cut sparsifier for the given graph.
Corollary 3.5. Given a graph G = (V, E, w) and a corresponding α tree cut sparsifier T = (VT , ET , wT ). Let L′ be an optimal solution to LLS on T . Then L′ is a solution for GLS with approximation factor α.
Definition 3.1 (Tree Cut Sparsifier). A tree T = (VT , ET , wT ) is an α tree cut sparsifier for the graph G = (V, E, w) if the leaves LT = V , and for all A ⊆ V :
Proof. Let L∗ denote an optimal solution of GLS on G. Using Lemma 3.4, and optimality of L′ for LLS, we obtain b T (L′ ) αΨG (L′ ) ≥ Ψ b T (L′ ) ≥ Ψ b T (L∗ ) ≥ ΨG (L∗ ) Ψ
w(A, V \ A) ≤ λT (A, LT \ A) ≤ α · w(A, V \ A).
We have reduced GLS to LLS on trees. Now, we show that solving LLS on a binary tree is sufficient by constructing a binary tree cut sparsifier via standard reductions (Räcke & Shah, 2014).
Definition 3.2 (Sparsity on Subset). Given a graph G = (V, E, w), we define the sparsity of A in a superset C ⊃ A: λG (A, C \ A) . |A|
Lemma 3.6. Given an α tree cut sparsifier T of some graph G, we can compute a binary tree T ′ which is an α tree cut sparsifier of G too. This can be done in linear time.
Definition 3.3 (Leaf Label Selection Problem (LLS)). Given a tree T = (V, E, w) and a budget k ∈ N, find a set L ⊆ LT , |L| ≤ k that maximizes the objective b T (L) := Ψ
(optimality, 3.4)
=⇒ αΨG (L′ ) ≥ ΨG (L∗ ).
We now translate the graph label selection problem to the tree cut sparsifier. We call this new problem the leaf label selection problem. For this we need the notion of sparsity on the leaf set.
C ψG (A) :=
(3.4)
r a
r 0
min ψTLT (S).
S⊆LT \L
1 Note that this is different from the graph label selection problem in that we must choose L as a subset of the leaf set LT .
a ...
b 2
c 3
1
d 4
...
0 b
∞ 2
X c d 3
4
Figure 1. Decreasing degree by 1 by introducing a new vertex X with ∞ edge weight.
Proof. Given an internal vertex v with degree larger than 3, we can add an auxiliary vertex x as a child of v with infinite edge weight and attaching two of v’s children to x instead (see Figure 1). This introduces no new vertices with degree larger than 3 and reduces the degree of v by one, therefore iteratively applying this procedure results in a binary tree. Finally, we show that the resulting tree remains a tree cut sparsifier. We do so by showing it for a single step and applying induction. Firstly, any cut in the original
Now we reduce the GLS problem on general graphs to an LLS problem on trees with loss of factor α = Õ(log1.5 n) in the approximation. Lemma 3.4. Given a graph G = (VG , EG , wG ) and a corresponding α tree cut sparsifier T = (VT , ET , wT ). For any solution L ⊆ LT = V , we have: b T (L) ≤ α · ΨG (L). ΨG (L) ≤ Ψ 3
An Approximation Algorithm for Graph Label Selection s
construction can be reproduced in the new construction by cutting the same edges. Secondly, any cut with finite cut size in the new construction does not use the ∞ edge. Therefore, the requirement
T τ ∞
w(A, V \ A) ≤ λT (A, LT \ A) ≤ α · w(A, V \ A)
t
still holds.
Figure 2. The structure of TL,τ .
Combining the above we obtain the following lemma. Lemma 3.7 (Reduction of GLS to LLS). Given an α tree cut sparsifier over O(n)-vertices of G, then GLS on G with an approximation factor of α can be reduced to solving LLS on an O(n)-vertices binary tree instance after processing in O(n) time.
We notice that S ′ , L must be disjoint because all vertices in L have an edge of infinite capacity to t. We can write the size of this cut as the sum of two parts, the cut in the original tree T plus the edges from the new sink s to vertices in (V \ S ′ ) ∪ {t}. This yields
Proof. This follows immediately from Corollary 3.5 and Lemma 3.6.
wTL,τ (S ′ ∪ {s}, (V \ S ′ ) ∪ {t})
In the rest of this article, we therefore focus on solving LLS on binary trees.
The second part of the sum consists of the edges from {s} to the leaves LT \ S ′ . Each such edge has weight τ by construction, so the sum can be written as
= wT (S ′ , V \ S ′ ) + wTL,τ ({s}, (V \ S ′ ) ∪ {t}).
4. Reducing to Flow Problem
wTL,τ (S ′ ∪ {s}, (V \ S ′ ) ∪ {t})
In (Cohen-Addad et al., 2025), they construct a flow gadget inspired by the densest subgraph problem to obtain a resource augmented algorithm for graph label selection. We observe that a similar flow problem can be solved exactly on the binary tree T via dynamic programming. For this purpose, we construct a graph TL,τ such that for any parameter b T (L) ≥ τ if and only if the s-t-maxflow problem τ ≥ 0, Ψ on TL,τ has value n · τ where n = |LT | denotes the number of leaves in T .
= wT (S ′ , V \ S ′ ) + τ · |LT \ S ′ |. Now we have λTL,τ ({s}, {t}) = wT (S ′ , V \ S ′ ) + τ · |LT \ S ′ |. Plugging this into the LHS of the lemma statement λTL,τ ({s}, {t}) < τ · n, we get
Definition 4.1 (Flow Graph). Given a tree T = (V, E, w), a set L ⊆ LT , and a threshold τ ∈ R. We construct TL,τ :
wT (S ′ , V \ S ′ ) + τ · |LT \ S ′ | < τ · n =⇒
wT (S ′ , V \ S ′ ) < τ · (n − |LT \ S ′ |).
• Vertex Set: V ∪ {s, t}
Then, let S = S ′ ∩ LT . We have
• Graph Copy: Every edge e ∈ E is also present in TL,τ with the same weight.
λT (S, LT \S) ≤ wT (S ′ , V \S ′ ) < τ ·(n−|LT \S ′ |) = τ ·|S|.
• Source edges: For every leaf v ∈ LT , there is an edge (s, v) with weight τ in TL,τ .
So we have ψTLT (S) < τ . Because S, L are disjoint, this b T (L) < τ and concludes the proof. gives Ψ
• Sink edges: For every chosen leaf v ∈ L, there is an edge (v, t) with weight ∞ in TL,τ .
And now we show the other direction. If the solution b T (L) < τ , then the s-t-maxflow is less than τ · n. Ψ
We start by showing that if the s-t-mincut is less than τ · n, then L gives a solution with value less than τ . b T (L) < τ . Lemma 4.2. If λT ({s}, {t}) < τ · n, then Ψ
b T (L) < τ , then λT ({s}, {t}) < τ · n. Lemma 4.3. If Ψ L,τ
L,τ
b there is some S disjoint from Proof. By the definition of Ψ, L such that:
Proof. By the definition of mincut, there is some S ′ such that: ′
b T (L) = ψ LT (S) < τ Ψ T
′
λTL,τ ({s}, {t}) = wTL,τ (S ∪ {s}, (V \ S ) ∪ {t})
=⇒ 4
λT (S, LT \ S) < τ · |S|.
An Approximation Algorithm for Graph Label Selection
Now, by the definition of a minimum cut, there is some S ′ with S ⊆ S ′ ⊆ V \ (LT \ S) such that:
of value n · τ1 . In TL2 ,τ2 all edges outgoing from s were saturated, so now they have flow τ1 . We can change the capacity of these edges to τ1 , giving the graph TL2 ,τ1 with flow value n · τ1 .
wT (S ′ , V \ S ′ ) < τ · |S|. We analyze wTL,τ (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}). As above, we can split this up:
This monotonicity allows us to search for the optimal τ using binary search.
wTL,τ (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}) ′
′
Lemma 4.7. Given an algorithm that solves the sink selection problem, we can construct an algorithm solving the leaf label selection problem.
′
= wT (S , V \ S ) + wTL,τ ({s}, (V \ S ) ∪ {t}). We now bound wTL,τ ({s}, (V \ S ′ ) ∪ {t}) as in the proof of Lemma 4.2. We obtain
Proof. We binary search for τ . In every iteration we check whether the solution L to the sink selection problem on (T, τ ) has more or less than k vertices. We can use binary search because we have shown that |L| is monotone in τ in Lemma 4.6.
wTL,τ (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}) = wT (S ′ , V \ S ′ ) + τ · |LT \ S ′ | < τ · |S| + τ · |LT \ S ′ |.
Let us assume that the weights of the graph T are integral and lie between 1 and W . We call W the aspect ratio of the \C) 1 1 edge weights. T is connected, so we have w(C,V ≥ |C| ≥n , |C| b for every C ⊆ V \ L. So Ψ(L) ≥ 1/n. Further, for every 2 ·W \C) b C ⊆ V \ L, we have w(C,V ≤ ≤ n|C| ≤n2 ·W , so Ψ(L) |C| 2 n ·W . This means that the binary search runs in O(log(n2 · W )) = O(log(n · W )) time and finds the optimal solution in the polynomially bounded search space.2
And because S ⊆ S ′ , we have τ · |S| + τ · |LT \ S ′ | ≤ τ ·|LT | = τ ·n. This directly implies λTL,τ ({s}, {t}) < τ ·n and concludes the proof. We finally combine the two lemmas to get an equivalence statement. Corollary 4.4. b T (L) ≥ τ ⇐⇒ λT ({s}, {t}) = n · τ Ψ L,τ
In the next section we show how we can solve the sink selection problem using dynamic programming and thus resolve the final missing piece.
Proof. We have λTL,τ ({s}, {t}) ≤ n · τ because the degree of s is n · τ . Therefore, the corollary follows from Lemma 4.2 and Lemma 4.3.
Remark on prior work. After completing and submitting this work, we became aware that a problem equivalent to sink selection was previously solved by Andreev et al. (2009). We give our proof for completeness.
By the mincut-maxflow duality, we can obtain the value of the minimum cut by solving the s-t-maxflow problem on TL,τ . This motivates us to define a new problem which aims to construct a set L such that TL,τ has s-t-maxflow τ · n. We call this new problem the “sink selection problem”.
5. Solving the Flow Problem using Dynamic Programming
Definition 4.5 (Sink Selection Problem). Given a tree T = (V, E, w) and a parameter τ , find L ⊆ LT with minimal |L|, such that the s-t-maxflow in TL,τ has value n · τ .
In this section we provide an algorithm and proof for the sink selection problem. To describe our algorithm, we need the tree T to be rooted. Therefore, we fix a root arbitrarily on a non-leaf vertex.3
We observe that the sink selection problem is monotone in |L|.
We first provide intuition about this problem. Given a tree T , and a parameter τ , we interpret all leaves as sources of value τ . Now we need to choose some leaves L ⊆ LT as sinks of arbitrarily large capacity, such that the flow becomes routable. Of course we additionally want to choose L such that |L| is as small as possible.
Lemma 4.6. For any tree T , and two parameters τ1 ≤ τ2 , let L1 , L2 be the optimal solutions to the sink selection problem on T with parameters τ1 and τ2 respectively. Then |L1 | ≤ |L2 |
2
For a standard encoding of edge weights this could give O(poly(n)) runtime. However, the aspect ratio is typically not exponential. 3 Often hierarchical decompositions such as tree cut sparsifiers give rise to a natural root.
Proof. We show that if τ1 ≤ τ2 , then L2 is a solution to the sink selection problem on (T, τ1 ) too. By definition there is a s-t flow in TL2 ,τ2 with value n · τ2 . Now we multiply the flow on every edge with τ1 /τ2 . This results in a s-t flow 5
An Approximation Algorithm for Graph Label Selection
• Transition for vertices v ∈ V with two children c1 , c2 : bound(v,c1 ) (DP[c1 ][a]) DP[v][k] = max + bound(v,c ) (DP[c2 ][k−a])
We suggest using dynamic programming with the following state to resolve this problem. For some subtree of vertex v, denoted as Tv , and some number of allowed sinks k, record the maximum amount of flow we can inject into the subtree at the vertex v such that it can still be routed away.
0≤a≤k
2
Now we show a sort of monotony of the DP-state invariant. Then we show, by induction on the binary tree, that the base cases and the transitions preserve the invariant as described in Definition 5.2.
To formalize this, we extend Definition 4.1 of our flow gadget. The changes are highlighted in red: Definition 5.1 (Flow Graph). Given a tree T = (V, E, w), and a set L ⊆ LT , and a threshold τ ∈ R, and a injected flow f ∈ R. We construct TL,τ,f :
τ s
ℓ
• Vertex Set: V ∪ {s, t}
0 If v ̸∈ L ∞ If v ∈ L
f
• Copy: Every edge e ∈ E is also present in TL,τ,f with the same weight.
t
n
Figure 3. The structure of (Tl )L,τ,f for some leaf l. x1 s
• Source: For every leaf v ∈ LT , there is an edge (s, v) with weight τ in TL,τ,f . Additionally, there is a directed edge (s, root(T )) with weight f . If f is negative, the edge is directed the other way with weight −f .
s x2
c1
c2 τ
• Sink: For every chosen leaf v ∈ L, there is an edge (v, t) with weight ∞ in TL,τ,f . Now we can formalize the dynamic programming state. For some subtree of vertex v, denoted as Tv , and some number of allowed sinks k, what is the most amount of flow we can inject into the subtree at the vertex v?
τ
∞
∞
t
t
k1 = 2
k2 = 1
Figure 4. The structure of (Tc1 )L,τ,f and (Tc2 )L,τ,f for the children c1 , c2 of v. v
Definition 5.2 (DP-State). The following invariant should always hold:
f
a
b
s c1
DP[v][k] = max f | ∃L, |L| ≤ k : λ(Tv )L,τ,f ({s}, {t}) = nv · τ + f
c2 τ
τ
Where nv = |LTv |. If that set is empty, we define DP[v][k] = −∞.
∞
We give the base cases and transitions, and later prove correctness via the invariant stated above.
k = k1 + k 2
∞ t
Figure 5. The structure of (Tv )L,τ,f
Definition 5.3. We define an auxiliary “edge-bound” function for all edges (u, v) in G. x < −w(u, v) −∞ bound(u,v) (x) = w(u, v) x > w(u, v) x otherwise
Lemma 5.5. Given that DP[v][k] = f ≥ 0 at some vertex v and budget k, we have that λ(Tv )L,τ,f ′ ({s}, {t}) = nv · τ + f ′ for all f ′ with 0 ≤ f ′ ≤ f . Proof. The prove is by induction. The base cases are the leaves. For some leaf l ∈ LT we have DP[l][0] = −τ and DP[l][1] = ∞ by definition. The lemma does not cover the first case, so we only need to show it for the second case. We can look at Figure 3 and see that for any f ′ ∈ R there is a s-t flow of value τ + f ′ .
Definition 5.4. We define the following base cases and transitions: • Base cases for leaves l ∈ LT : ( −τ for k = 0 DP[l][k] = ∞ for k > 0
For the general case, as depicted in Figure 5, we notice that we can reduce it to two smaller instances as depicted in 6
An Approximation Algorithm for Graph Label Selection
Figure 4. Note that nv = nc1 + nc2 . Now we have two cases:
Now we discuss how the optimal solution for the sink selection problem can be recovered. For some L to be a solution to the sink selection problem, we need that the s-t-maxflow in TL,τ has value n · τ . The graphs TL,τ and TL,τ,f are equivalent for f = 0. The DP calculates f given some k. Using the DP monotony (Lemma 5.5) and the correctness of the DP (Lemma 5.6), we get that for all k where DP[root(T )][k] ≥ 0 there is a solution L with |L| = k. So we choose the smallest k with DP[root(T )][k] ≥ 0. The corresponding selection of vertices L can be recovered using standard DP backtracking techniques.
• a, b ≥ 0: We scale down both a and b by multiplying with f ′ /f . This is allowed by the induction hypothesis. • a < 0, b ≥ 0 or a ≥ 0, b < 0: We assume, without loss of generality, that a < 0, b ≥ 0. We set the new b′ = b − (f − f ′ ). We have f = a + b =⇒ b = f − a > f f ′ ≥ 0 =⇒ f − f ′ ≤ f =⇒ b′ = b − (f − f ′ ) > 0,
Runtime. We observe that our dynamic program has O(|VT | · k) states. Every transition can be computed in O(k) steps. The tree cut sparsifier is a binary tree with |LT | = |VG | = n leaves, so it has O(n) vertices. This gives a runtime of O(n · k 2 ) for the dynamic program. We need to run a binary search to find the optimal τ . So the total runtime of the algorithm is O(TT REE C UT S PARSIFIER +n·k 2 ·log(n·W )), where W is the aspect ratio of the edge weights and TT REE C UT S PARSIFIER is the time required to compute a tree cut sparsifier. Depending on this time, we get different runtime and approximation trade-offs. Using (Räcke & Shah, 2014) achieves total polynomial runtime with Õ(log1.5 n) approximation, yielding Theorem 1.1. Using (Agassy et al., 2025) achieves total Õ(n · k 2 ) runtime4 with Õ(log2 n) approximation.
so b′ ≥ 0, and we can apply the induction hypothesis. Note that the case a, b < 0 is impossible because f = a + b ≥ 0. Lemma 5.6. The DP calculated with base cases and transitions as described in Definition 5.4 satisfies the invariant Definition 5.2. Proof. We show this by induction on the binary tree. For the base case on a leaf v, we observe that Tv is just a single vertex. That means (Tv )L,τ,f looks as in Figure 3. If k = 0, this implies v ̸∈ L, forcing f = −τ . If k ≥ 1, we chose L = {v}, allowing arbitrarily large f . This immediately gives the base cases: ( −τ for k = 0 DP[l][k] = ∞ for k > 0
6. Experiments Our algorithm relies on tree cut sparsifiers, for which there currently are no open source implementations that we are aware of. However, they are usually constructed by repeatedly decomposing a graph along sparse cuts.5 Therefore, we use sparse-cut heuristics like M ETIS (Karypis & Kumar, 1997) to build a hierarchical decomposition resembling a tree cut sparsifier. We have implemented multiple such heuristics to compare them against each other and against the algorithms from (Cohen-Addad et al., 2025; Cesa-Bianchi et al., 2010; Guillory & Bilmes, 2009) on various graphs. Algorithm 1 describes how to achieve such a hierarchical decomposition given an algorithm B ISECT that cuts a graph into two parts.
Now we regard the transitions for a vertex v with two children c1 , c2 . We have budget k, and we can choose how to distribute that among the two children. The subgraphs of the two children are shown in Figure 4. Now we try to combine them, this is depicted in Figure 5. We get that f = a + b. For this to be a feasible solution, we need: a ≤ x1 , b ≤ x2 and |a| ≤ w(v, c1 ), |b| ≤ w(v, c2 ). So by using a = bound(v,c1 ) (x1 ) and b = bound(v,c2 ) (x2 ) and applying Lemma 5.5, we get feasibility of the DP solution. That is, the value calculated by the DP is always achievable, and the solution can be recovered using backtracking.
We construct T by first creating a root vertex r which corresponds to the whole graph G. Then we find a sparse cut (S, V \ S) in G using one of the heuristics. Now we create two new vertices a, b corresponding to the induced subgraphs G[S] and G[V \ S] respectively. We add edges (r, a) and (r, b) with weights equal to the weight of the cut w(S, V \ S), and recursively build the tree until arriving at
Now we need to show that the optimal solution can be reproduced with such a construction, and thus be found by the DP. We look at the optimal solution, it has some a, b with a + b = f and |a| ≤ w(v, c1 ), |b| ≤ w(v, c2 ). Also, it must choose some k1 , k2 with k1 + k2 ≤ k. By the induction hypothesis, the calculated DP solution at both c1 and c2 with budget k1 and k2 respectively is optimal, so it must be at least that of the optimal flow we are looking at. This directly implies that the DP finds an optimal construction.
4
For the aspect ratio of the edge weights W ∈ poly(n). For obtaining state-of-the-art guarantees on worst-case instances, additional delicate properties are necessary. 5
7
An Approximation Algorithm for Graph Label Selection
leaves corresponding to single vertices in G.
et al., 2010; Guillory & Bilmes, 2009). For nondeterministic algorithms we ran the experiment 10 times and show the standard deviation as a shaded area. We evaluate our algorithm with the following bisect algorithms/sparse cut heuristics:
Our choice of edge weights ensures that the resulting tree fulfills the lower bound property of a tree cut sparsifier: For all AG ⊆ VG we have wG (A, V \ A) ≤ λT (A, LT \ A). Algorithm 1 H IERARCHICAL D ECOMPOSITION
F IEDLER
Input: Graph G = (V, E, w) Output: Edgelist of Tree If |G| = 1, return ∅ A, B ← B ISECT(G) eA ← (V, A, wG (A, V \ A)) eB ← (V, B, wG (B, V \ B)) EA = H IERARCHICAL D ECOMPOSITION(G[A]) EB = H IERARCHICAL D ECOMPOSITION(G[B]) return {eA , eB } ∪ EA ∪ EB
F IEDLER BALANCED with β ∈ {0.01, 0.1} √ √ √ M ETIS with #samples ∈ { n, 10 n, 100 n} We test our algorithms on various real world graphs from the Stanford Network Analysis Project (SNAP) (Leskovec & Krevl, 2014): ca-GrQc
|V | =
4 158
|E| =
13 428
|V | = 21 363
|E| =
91 342
|V | =
|E| =
88 234
(Leskovec et al., 2007)
ca-CondMat In the following we describe which sparsest cut heuristics we used: F IEDLER and M ETIS (Spielman & Teng, 2004; Karypis & Kumar, 1997).
(Leskovec et al., 2007)
ego-facebook
4 039
(McAuley & Leskovec, 2012)
com-dblp
|V | = 317 080
|E| = 1 049 866
(Yang & Leskovec, 2012)
Sparsest cut via Fiedler Vector. We calculate the Fiedler vector of the graph and run spectral sweep to choose a cut with low sparsity (Spielman & Teng, 2004). The Fiedler vector, or algebraic connectivity, is the Eigenvector corresponding to the second smallest Eigenvalue of a graph Laplacian.6 See Algorithm 2 in Section C. We remark that the computation of the Fiedler vector could be performed on a GPU in a straightforward manner.
Additionally we tested on the Davis Southern Women Graph (|V | = 32, |E| = 89) for interpretable results on a small graph (Davis et al., 1941). The graphs were preprocessed by choosing the largest connected component and deleting self-loops. The experiments were run on a AMD Ryzen Threadripper PRO 7955WX processor (16 cores / 32 threads, up to 5.3 GHz). The different algorithms have very different runtime scaling behavior. Due to this we could not run all algorithms on all graphs, especially for large k. Therefore, some algorithms have more data points than others. For a runtime comparison see Table 1.
We also tested a slight adaptation of this algorithm which forces the bisection to be balanced. In this case the algorithm has an additional parameter β which specifies how balanced the cut should be. If a cut (A, B) is chosen with either min(|A|, |B|) ≤ n · β we disregard that cut and choose the next best one. This can give big runtime improvements at the expense of quality.7
Table 1. Runtime (seconds) of all algorithms on ca-GrQc for k ∈ {10, 50, 100}. Real time denotes wall-clock time; user time denotes CPU time spent in user mode. The runtimes should be interpreted with caution: the experiments were not conducted in a fully controlled environment (e.g., multiple processes were running concurrently), and the implementations were not tuned for performance. Nevertheless, the table provides a coarse comparison of orders of magnitude and relative trends across methods.
Sparsest cut with METIS (Karypis & Kumar, 1997). We use METIS (Karypis & Kumar, √ 1997) to calculate bisections. We run the algorithm O( n) times with different target partition weights. They are distributed geometrically between 1 and n/2. Then we choose the partition with the best sparsity. See Algorithm 3 in Section C. We point out that the METIS calls in this algorithm could be parallelized naively.
Budget Guillory Bilmes Cesa-Bianchi et al.
Experimental Setup.8 We compare our algorithm to the algorithms from (Cohen-Addad et al., 2025; Cesa-Bianchi
Cohen-Addad et al.
6
The smallest Eigenvalue is 0. This strategy ensures that the resulting tree cut sparsifier is balanced. 8 We provide the code used for running the experiments on GitHub: https://github.com/josia-john/ icml2026-graph-label-selection
Ours F IEDLER
7
time real user real user real user real user
k = 10 144 645 14 13 4967 67808 22 31
k = 50 842 1329 8 8 15586 222014 21 30
k = 100 1835 2303 13 12 22956 432845 22 31
Results. Both F IEDLER and M ETIS perform well overall, with F IEDLER BALANCED running a lot faster at the cost of 8
An Approximation Algorithm for Graph Label Selection Table 2. Performance of M ETIS on com-dblp.
quality. Figures 6 and 7 show the comparison. We achieve similar quality to current state of the art (Cohen-Addad et al., 2025). But our algorithm runs magnitudes faster. It has no problem running for many different values k on a graph like ca-CondMat, see Figure 7, while other algorithms struggle even for just one value k on smaller graphs like ca-GrQc.
Budget √ Ours (M ETIS n)
k = 5000 0.083
We present the first approximation algorithm for the graph label selection problem on general graphs that does not rely on resource augmentation. We also describe how to adapt the algorithm to give an optimal solution for the graph label selection problem on weighted trees.
Our algorithm can handle √ quite large graphs. Using M ETIS with #samples = n the algorithm runs within a few hours on com-dblp. We present those results in Table 2. For more results refer to Section C.
It remains an interesting open problem to scale algorithms to massive graphs. One of the main bottlenecks in our framework is the dynamic program. An approximate version of this dynamic program could be solvable in linear time.
Acknowledgements
0.40 0.35
The research of Simon Meierhans and Maximilian Probst Gutenberg leading to these results has received funding from grant no. 200021 204787 of the Swiss National Science Foundation. Simon Meierhans is supported by a Google PhD Fellowship.
0.30 0.25
Ψ(L)
k = 500 0.048
7. Conclusion
We remark that the quality often remains constant for a sequence of budgets because there are numerous disjoint sparse cut with equal sparsity (For example degree one vertices).
Guillory Bilmes Cesa-Bianchi et al. Ours (METIS √n) Ours (METIS 10 √n) Ours (METIS 100 √n) Ours (Fiedler) Ours (FiedlerBalanced 1%) Ours (FiedlerBalanced 10%) Cohen-Addad et al.
0.20 0.15 0.10 0.05 0.00 0
50
100
150
200
250
300
350
Impact Statement At present, our results are primarily theoretical in nature. In the future, the techniques presented in this paper could be used to improve the reasoning capabilities of large language models and should therefore be used with caution as models become more capable.
400
k
Figure 6. Comparison of all algorithms on ca-GrQc. Due to runtime constraints, we could not run all algorithms for every value of k.
0.5
Ours (METIS √n) Ours (METIS 10 √n) Ours (METIS 100 √n) Ours (Fiedler) Ours (FiedlerBalanced 1%) Ours (FiedlerBalanced 10%)
0.4
Ψ(L)
k = 50 0.030
0.3
0.2
0.1 0
200
400
600
800
1000
k
Figure 7. Comparison of our algorithm using different B ISECT algorithms on ca-CondMat.
9
An Approximation Algorithm for Graph Label Selection
References
Davis, A., Gardner, B. B., and Gardner, M. R. Deep South: A Social Anthropological Study of Caste and Class. University of Chicago Press, Chicago, IL, 1941.
Agassy, D., Dorfman, D., and Kaplan, H. Improved Tree Sparsifiers in Near-Linear Time, 2025. URL https: //arxiv.org/abs/2511.06574.
Guillory, A. and Bilmes, J. A. Label Selection on Graphs. In Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C., and Culotta, A. (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009. URL https://proceedings.neurips. cc/paper_files/paper/2009/file/ 90794e3b050f815354e3e29e977a88ab-Paper. pdf.
Anand, P., Indyk, P., Krishnaswamy, R., Mahabadi, S., Raykar, V. C., Shiragur, K., and Xu, H. Graph-Based Algorithms for Diverse Similarity Search, 2025. URL https://arxiv.org/abs/2502.13336. Andreev, K., Garrod, C., Golovin, D., Maggs, B., and Meyerson, A. Simultaneous source location. ACM Transactions on Algorithms (TALG), 6(1):1–17, 2009. Bateni, M., Cohen-Addad, V., Gu, Y., Lattanzi, S., Meierhans, S., and Mohri, C. Algorithmic Thinking Theory, 2025. URL https://arxiv.org/abs/2512. 04923. Cesa-Bianchi, N., Gentile, C., Vitale, F., and Zappella, G. Active Learning on Trees and Graphs. In Kalai, A. T. and Mohri, M. (eds.), COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pp. 320–332. Omnipress, 2010. URL http: //colt2010.haifa.il.ibm.com/papers/ COLT2010proceedings.pdf#page=328.
Harrelson, C., Hildrum, K., and Rao, S. A polynomial-time tree decomposition to minimize congestion. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pp. 34–43, 2003. Henzinger, M., Münk, R., and Räcke, H. An Improved Quality Hierarchical Congestion Approximator in NearLinear Time. arXiv preprint arXiv:2511.03716, 2025. Hu, S., Xiong, Z., Qu, M., Yuan, X., Côté, M.-A., Liu, Z., and Tang, J. Graph Policy Network for Transferable Active Learning on Graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10174–10185. Curran Associates, Inc., 2020. URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ 73740ea85c4ec25f00f9acbd859f861d-Paper. pdf.
Cheng, X., Wang, X., Zhang, X., Ge, T., Chen, S.-Q., Wei, F., Zhang, H., and Zhao, D. xRAG: extreme context compression for retrieval-augmented generation with one token. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9798331314385. Cohen-Addad, V., Lattanzi, S., and Meierhans, S. Algorithms and Hardness for Active Learning on Graphs. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff, K., and Zhu, J. (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 11200–11214. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr. press/v267/cohen-addad25a.html. Dasarathy, G., Nowak, R., and Zhu, X. S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification. In Grünwald, P., Hazan, E., and Kale, S. (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 503–522, Paris, France, 03–06 Jul 2015. PMLR. URL https://proceedings.mlr.press/v40/ Dasarathy15.html.
Karypis, G. and Kumar, V. METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Technical Report 97-061, University of Minnesota, Department of Computer Science and Engineering, 1997. URL https://hdl.handle.net/ 11299/215346. Kushnir, D. and Venturi, L. Diffusion-based deep active learning. arXiv preprint arXiv:2003.10339, 2020. Leskovec, J. and Krevl, A. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap. stanford.edu/data, June 2014. Leskovec, J., Kleinberg, J. M., and Faloutsos, C. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 1(1): 2, 2007. doi: 10.1145/1217299.1217301. URL https: //doi.org/10.1145/1217299.1217301. Liskavets, B., Ushakov, M., Roy, S., Klibanov, M., Etemad, A., and Luke, S. K. Prompt compression with contextaware sentence encoding for fast and improved LLM in-
10
An Approximation Algorithm for Graph Label Selection
ference. In Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence, AAAI’25/IAAI’25/EAAI’25. AAAI Press, 2025. ISBN 978-1-57735-897-8. doi: 10.1609/aaai. v39i23.34639. URL https://doi.org/10.1609/ aaai.v39i23.34639.
STOC ’04, pp. 81–90, New York, NY, USA, 2004. Association for Computing Machinery. ISBN 1581138520. doi: 10.1145/1007352.1007372. URL https://doi. org/10.1145/1007352.1007372. Yang, J. and Leskovec, J. Defining and Evaluating Network Communities Based on Ground-Truth. In 12th IEEE International Conference on Data Mining (ICDM 2012), pp. 745–754. IEEE Computer Society, 2012. doi: 10. 1109/ICDM.2012.138. URL https://doi.org/10. 1109/ICDM.2012.138.
Mac Aodha, O., Campbell, N. D., Kautz, J., and Brostow, G. J. Hierarchical Subquery Evaluation for Active Learning on a Graph. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2014.
Yang, W., Zhu, Y., Deng, Z., and Russakovsky, O. What is Dataset Distillation Learning? In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of McAuley, J. J. and Leskovec, J. Learning to Discover the 41st International Conference on Machine LearnSocial Circles in Ego Networks. In Advances in Neural ing, volume 235 of Proceedings of Machine LearnInformation Processing Systems 25 (NIPS 2012), pp. ing Research, pp. 56812–56834. PMLR, 21–27 Jul 548–556, 2012. URL https://proceedings. 2024. URL https://proceedings.mlr.press/ neurips.cc/paper/2012/hash/ 7a614fd06c325499f1680b9896beedeb-Abstract. v235/yang24am.html. html. Zhang, J., Katz-Samuels, J., and Nowak, R. GALAXY: Graph-based Active Learning at the Extreme. In Nguyen, T., Novak, R., Xiao, L., and Lee, J. Dataset Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, distillation with infinitely wide convolutional networks. C., Niu, G., and Sabato, S. (eds.), Proceedings In Proceedings of the 35th International Conference on of the 39th International Conference on Machine Neural Information Processing Systems, NIPS ’21, Red Learning, volume 162 of Proceedings of Machine Hook, NY, USA, 2021. Curran Associates Inc. ISBN Learning Research, pp. 26223–26238. PMLR, 17–23 9781713845393. Jul 2022a. URL https://proceedings.mlr. Räcke, H. and Shah, C. Improved Guarantees for Tree press/v162/zhang22k.html. Cut Sparsifiers. In Schulz, A. S. and Wagner, D. (eds.), Zhang, W., Wang, Y., You, Z., Cao, M., Huang, P., Shan, J., Algorithms - ESA 2014, pp. 774–785, Berlin, HeidelYang, Z., and Cui, B. Information gain propagation: a berg, 2014. Springer Berlin Heidelberg. ISBN 978-3-662new way to graph active learning with soft labels. arXiv 44777-2. preprint arXiv:2203.01093, 2022b. Räcke, H., Shah, C., and Täubig, H. Computing cut-based Zhu, X., Ghahramani, Z., and Lafferty, J. Semi-supervised hierarchical decompositions in almost linear time. In learning using Gaussian fields and harmonic functions. Proceedings of the Twenty-Fifth Annual ACM-SIAM SymIn Proceedings of the Twentieth International Conferposium on Discrete Algorithms, SODA ’14, pp. 227–238, ence on International Conference on Machine LearnUSA, 2014. Society for Industrial and Applied Matheing, ICML’03, pp. 912–919. AAAI Press, 2003. ISBN matics. ISBN 9781611973389. 1577351894. Ren, P., Xiao, Y., Chang, X., Huang, P.-Y., Li, Z., Gupta, B. B., Chen, X., and Wang, X. A Survey of Deep Active Learning. ACM Comput. Surv., 54(9), October 2021. ISSN 0360-0300. doi: 10.1145/3472291. URL https: //doi.org/10.1145/3472291. Settles, B. Active learning literature survey. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2009. Spielman, D. A. and Teng, S.-H. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the ThirtySixth Annual ACM Symposium on Theory of Computing, 11
An Approximation Algorithm for Graph Label Selection
A. Solving Graph Label Selection optimally on Weighted Trees
Let us analyze the set S materializing the mincut λT (A′ , LT \ A′ ) =
We show that we can solve Graph Label Selection optimally on weighted trees by constructing a perfect tree cut sparsifier for weighted trees. Then the result follows immediately from.
0 w2
1
w3
2 w5
w4
4
3
So we must choose S = A ∪ A′ . All ∞ edges are not contributing, so the cut is equivalent to the cut (A, V \ A) in G, giving
w6
6
5 w7
λT (A′ , LT \ A′ ) = wT (S, VT \ S) = wG (A, V \ A),
7
concluding our proof.
0 w1
w4
w3
2 w5
4
∞
w2
1 ∞
5
1’
w7
∞
7
5’
3
w6
∞
6
2’
B. Generalizing to Vertex Importance
0’
In this article we have described how to maximize the function Ψ(L) = minC⊆V \L w(C, V \C)/|C|. But our algorithm can easily be extended to allow for maximization of any function of the form w(C, V \C) min P , c∈C f (c)
Figure 8. Transforming a tree G (top) into a 1 tree cut sparsifier T (bottom). We connect a new leaf with weight ∞ to every internal vertex in G.
C⊆V \L
where f : V → R≥0 is an “importance” function of vertices. The standard label selection problem tries to maximize a sparsity metric. That would be f (v) = 1 for all v ∈ V . This extension allows us to optimize for many more metrics, with one important example being a conductance like metric:
Proof. Let G = (V, E, w) be a weighted tree. We construct a tree T = (VT , ET , wT ) as follows (see Figure 8). Start with G and for every internal vertex v ∈ V \ LG add a new leaf v ′ and an edge (v, v ′ ) with weight ∞.
w(C, V \C) vol(C) P Here we use the fact that vol(C) = c∈C deg(c). min
C⊆V \L
Now we have a natural one to one mapping between the leaves LT in T and the vertices V in G. For v ∈ LT it corresponds to v ∈ V , and for v ′ ∈ LT it corresponds to v ∈V.
The algorithm is almost the same as we have described above, the main difference is just the base cases of the dynamic program. Here we give the slightly modified proofs.
We show that given any A ⊆ V and its mapping to the leaves of the tree cut sparsifier A′ ⊆ LT with ′
′
wT (S, VT \ S).
For any vertex v ∈ A′ we must, by definition, have v ∈ S. For every vertex v ∈ LT \ A′ we must, by definition, have v ̸∈ S. This leaves us with internal vertices v ∈ VT \ LT . By our construction, every internal vertex v has a leaf v ′ , for which we know whether it is in S or not. Assuming v ′ ∈ S, if we would choose v ̸∈ S, then the edge (v, v ′ ) with weight ∞ would contribute to the cut size, making it ∞ too. So we must choose v ∈ S. If v ′ ̸∈ S, then v ̸∈ S by the same argument.
Lemma A.1. Given a tree G = (V, E, w). There is a 1 tree cut sparsifier for G.
w1
min
A′ ⊆S⊆VT \(LT \A′ )
′
We start by defining the new objective function, for both GLS and LLS.
′
A = {v | v ∈ A, v ∈ VT } ∪ {v | v ∈ A, v ̸∈ VT }
λT (A′ , LT \ A′ ) = wG (A, V \ A),
Definition B.1 (Graph Label Selection Problem with Vertex Importance). Given a graph G = (V, E, w), a vertex importance function f : V → R, and a budget k ∈ N, find a set L ⊂ V, |L| ≤ k that maximizes the objective
which implies that T is a 1 tree cut sparsifier according to Definition 3.1.
w(C, V \C) ΨfG (L) := min P C⊆V \L c∈C f (c)
the following holds:
12
An Approximation Algorithm for Graph Label Selection
Proof. Let L∗ be the optimal solution of GLS on G. Using Lemmas B.3 and B.4, and optimality of L′ for LLS, we get:
Definition B.2 (Leaf Label Selection Problem with Vertex Importance). Given a tree T = (V, E, w) and a budget k ∈ N, find a set L ⊆ LT , |L| ≤ k that maximizes the objective b f (L) = Ψ T
b f (L′ ) αΨf (L′ ) ≥ Ψ T b f (L′ ) ≥ Ψ b f (L∗ ) ≥ Ψf (L∗ ) Ψ T
λT (C, LT \ C) P C⊆LT \L c∈C f (c)
G
Reducing to Flow Problem. We define a new flow graph, with respect to the vertex importance function f :
In the following we describe how all three steps of our algorithm can be adapted to work with vertex importance.
Definition B.6 (Flow Graph with Vertex Importance). Given a tree T = (V, E, w), a vertex importance function f : V → R, a set L ⊆ LT , and a threshold τ ∈ R. We f construct TL,τ :
Reducing to Binary Tree. Given is the graph G = (V, E, w). From Lemma 3.6 we get that we have some binary α tree cut sparsifier T = (VT , ET , w). Now we need to show Lemma 3.4 with respect to the new importance function f : V → R.
• Vertex Set: V ∪ {s, t}
Lemma B.3. Given a graph G = (VG , EG , wG ) and a corresponding α tree cut sparsifier T = (VT , ET , wT ). For any solution L ⊆ LT = V we have:
f • Copy: Every edge e ∈ E is also present in TL,τ with the same weight.
• Source: For every leaf v ∈ LT , there is an edge (s, v) f with weight τ · f (v) in TL,τ .
b f (L) ≤ αΨf (L) Ψ T G
• Sink: For every chosen leaf v ∈ L, there is an edge f (v, t) with weight ∞ in TL,τ . P Lemma B.7. If λT f ({s}, {t}) < τ · v∈LT f (v), then L,τ b f (L) < τ . Ψ
Proof. b f (L) = Ψ T
T
min
min
C⊆LT \L
λT (C, LT \ C) P c∈C f (c)
T
α · wG (C, V \ C) P C⊆V \L c∈C f (c)
≤ min
Proof. By the definition of mincut, there is some S ′ such that:
= αΨfG (L)
λT f ({s}, {t}) = wT f (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}) L,τ
L,τ
′
We notice that S , L must be disjoint because all vertices in L have an edge of infinite capacity to t. We can write the size of this cut as the sum of two parts: The cut in the original tree T plus the edges from the new sink s to vertices in (V \ S ′ ) ∪ {t}:
Lemma B.4. Given a graph G = (VG , EG , wG ) and a corresponding α tree cut sparsifier T = (VT , ET , wT ). For any solution L ⊆ V = LT we have: b f (L) ≥ Ψf (L) Ψ T G
wT f (S ′ ∪ {s}, (V \ S ′ ) ∪ {t})
Proof.
L,τ
b f (L) = Ψ T
min
C⊆LT \L
= wT (S ′ , V \ S ′ ) + wT f ({s}, (V \ S ′ ) ∪ {t})
λT (C, LT \ C) P c∈C f (c)
L,τ
The second part of the sum is just the edges from {s} to leaves v ∈ LT \ S ′ . The edge (s, v) has weight τ · f (v), so the sum can be written as:
wG (C, V \ C) P ≥ min C⊆V \L c∈C f (c) = ΨfG (L)
wT f (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}) L,τ X = wT (S ′ , V \ S ′ ) + τ · f (v) v∈LT \S ′
Corollary B.5. Given a graph G = (V, E, w), a vertex importance function f , and a corresponding α tree cut sparsifier T = (VT , ET , wT ). Let L′ be the optimal solution of LLS on T . Then L′ is a solution for GLS with approximation factor α.
Now we have λT f ({s}, {t}) = wT (S ′ , V \ S ′ ) + τ · L,τ
13
X v∈LT \S ′
f (v).
An Approximation Algorithm for Graph Label Selection
Plugging this intoPthe LHS of the λT f ({s}, {t}) < τ · v∈LT f (v) we get:
Corollary B.9.
statement
b f (L) ≥ τ ⇐⇒ λ f ({s}, {t}) = τ · Ψ T T
L,τ
X
wT (S ′ , V \ S ′ ) + τ ·
v∈LT \S ′ ′
X
wT (S , V \ S ) < τ ·
=⇒
v∈LT
f (v)
v∈LT ′
P Proof. We have λT f ({s}, {t}) ≤ τ · v∈LT f (v) because L,τ P the degree of s is τ · v∈LT f (v). Then we just apply Lemmas B.7 and B.8.
f (v)
v∈S ′ ∩LT
Let us construct S = S ′ ∩ LT . We have λT (S, LT \ S) ≤ wT (S ′ , V \ S ′ ) < τ ·
X
Definition B.10 (Sink Selection Problem). Given a tree T = (V, E, w) and a parameter τ , find L ⊆ LT with minimal |L|, P f such that the s-t-maxflow in TL,τ has value τ · v∈LT f (v).
f (v)
v∈S
Because S, L are disjoint, this gives
The monotony from Lemma 4.6 holds just as in Section 4, so we can again find L using binary search.
λT (C, LT \ C) P min C⊆LT \L c∈C f (c) P τ· f (v) < P v∈S =τ f (v) v∈S
b f (L) = Ψ T
Solving the Flow Problem using Dynamic Programming. This part is pretty immediate. We can use the same DP-state f as in Section 5, just using the new flow graph TL,τ . The only thing that changes is the base cases for leaves. Instead of −τ , we now use −τ · f (v) at the leaf v. It’s easy to see that this base case agrees with the new DP-state. The proof that the transitions are correct still works here.
b f (L) < τ , then λ f ({s}, {t}) < τ · Lemma B.8. If Ψ T TL,τ P v∈LT f (v) b f , there is some S disjoint Proof. By the definition of Ψ from L such that:
C. Further Experiments
(S, LT \ S) b f (L) = λTP Ψ T v∈S f (v)
Algorithm 2 B ISECT (F IEDLER)
λT (S, LT \ S) < τ ·
=⇒
X
Input: Graph G = (V, E, w) and its Laplacian L Output: Bisection (A, B) of V
f (v)
v∈S
⃗v ← λ2 (L) ▷ the second eigenvector of L best ← (score : ∞, A : {}, B : {}) for t ∈ elements(⃗v ) do ▷ iterate over all values in ⃗v A ← {i | ⃗vi ≤ t} B ← {i | ⃗vi > t} wG (A,B) score ← min(|A|,|B|) if score < best.score then best ← (score, A, B) end if end for return (best.A, best.B)
Now, by the definition of mincut, there is some S ′ with S ⊆ S ′ ⊆ V \ (LT \ S) such that: X wT (S ′ , V \ S ′ ) < τ · f (v) v∈S ′
′
We analyze wT f (S ∪ {s}, (V \ S ) ∪ {t}). As above, we L,τ can split this up: wT f (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}) L,τ
= wT (S, V \ S) + wT f ({s}, (V \ S ′ ) ∪ {t}) L,τ
We can bound wTL,τ ({s}, (V \ S ′ ) ∪ {t}) just as above. It is the edges from s to leaves LT \ S ′ . That gives wTL,τ (S ′ ∪ {s}, (V \ S ′ ) ∪ {t}) X = wT (S ′ , V \ S ′ ) + τ · f (v) v∈LT \S ′
<τ ·
X v∈S
f (v) + τ ·
X v∈LT \S ′
X
f (v) ≤ τ ·
f (v)
v∈LT
This directly implies λT f ({s}, {t}) < τ · L,τ
f (v)
L,τ
X
f (v) < τ ·
X
P
v∈LT f (v).
14
An Approximation Algorithm for Graph Label Selection
Algorithm 3 B ISECT (M ETIS) Input: Graph G = (V, E, w) and a number of #samples. Output: Bisection (A, B) of V best ← (score : ∞, A : {}, B : {}) for w ∈ geomspace(1, n/2, #samples) do (A, B) ← METIS(G, tpwgts = [w/n, 1 − w/n]) wG (A,B) score ← min(|A|,|B|) if score < best.score then best ← (score, A, B) end if end for return (best.A, best.B)
2.0
Ψ(L)
1.5
Guillory Bilmes Cesa-Bianchi et al. Ours (METIS √n) Ours (METIS 10 √n) Ours (METIS 100 √n) Ours (Fiedler) Ours (FiedlerBalanced 1%) Ours (FiedlerBalanced 10%) Cohen-Addad et al.
1.0
0.5
0.0 0
50
100
150
200
250
300
350
400
k
Figure 9. Comparison of all algorithms on ego-facebook. Due to runtime constraints, we could not run all algorithms for every value of k.
Guillory Bilmes Cesa-Bianchi et al. Cohen-Addad et al. Ours (Best)
14 12
Ψ(L)
10 8 6 4 2 0 0
5
10
15
20
25
30
k
Figure 10. Comparison of all algorithms on the Davis Southern Women Graph. We include this figure to compare all algorithms for many different values of k. For “Ours (Best)” we ran our algorithm with all bisect algorithms and plotted the best result.
15