Algorithms and Hardness for Active Learning on Graphs
Authors: Vincent Cohen-Addad
Silvio Lattanzi
Simon Meierhans
Venue: ICML 2025 poster (2025)
Keywords: graph
active learning
label selection
resource augmented algorithms
approximation algorithms
Primary area: theory->active_learning_and_interactive_learning
TL;DR: We present the first algorithm with theoretical guarantees for an established active learning problem on general graphs

Abstract: We study the offline active learning problem on graphs. In this problem, one seeks to select k vertices whose labels are best suited for predicting the labels of all the other vertices in the graph.
Guillory and Bilmes (Guillory & Bilmes, 2009) introduced a natural theoretical model motivated by a label smoothness assumption. Prior to our work, algorithms with theoretical guarantees were only known for restricted graph types such as trees (Cesa-Bianchi et al., 2010) despite the models simplicity. We present the first O(log n)-resource augmented algorithm for general weighted graphs. To complement our algorithm, we show constant hardness of approximation.

Algorithms and Hardness for Active Learning on Graphs
Vincent Cohen-Addad
Silvio Lattanzi'
Simon Meierhans
Abstract
on the weighted similarity graph G = EV w) where the
We study the offline active learning problem on graphs. In this problem, one seeks to select k vertices whose labels are best suited for predicting the labels of all the other vertices in the graph. Guillory and Bilmes (Guillory & Bilmes, 2009) introduced natural theoretical model motivated by label smoothness assumption. Prior to our work, algorithms with theoretical guarantees were only known for restricted graph types such as trees et al., 2010) despite the models simplicity. We present the first Ollog r))rruource augmented algorithm for general weighted graphs. To complement our algorithm, we show constant hardness of approximation.
goal is to maximize v(() subject to a cardinality constraint k
max LCViLLSk
Concretley, they show that for any consistent labeling y, i.e. y(v) = ((v) for all v E L, we have
y - 1リ- S
1
Σ
w(i,g) (y(1) y(i)
(L)
(iJ)ER
Σ (1J)
w(.j)) (1)))) ((})))
where the first sum small by assumption and the second sum is (approximately) minimized by a suitable prediction algorithm (See Theorem I in (Guillory & Bilmes, 2009)), We therefore focus on maximizing V (L) in this article.
1. Introduction
Graph learning has wide array of applications across vari- domains spanning Web Spam detection, genomics, text classification, face detection and many more (Chang & Ye- ung, 2006; Goldberg & Zhu, 2006; Herbster & Lever, 2009; Shin et al., 2009). In active learning, one is presented with a large unlabeled data set and given the opportunity to un- cover the labels of some small number of points. Obtain- ing labeled data points is often costly, and therefore these should be chosen carefully. Guillory and Bilmes (Guillory & Bilmes, 2009) introduced simple graph based abstrac- tion where every vertex corresponds to data point, and edges encode similarities between data points. For vertex labels y E {0, 10, they assume that
Intuitively, the objective asks to position the labeled data points such that disconnecting a large chunk unlabeled data points cuts a lot of edge weight. (Guillory Bilmes, 2009) present some evidence that solving this problem ex- actly might be hard, and give practical heuristic algorithms.
Gentile, Vitale and Zappella presented the first algorithm with theoretical guarantees under the assump- tion that G is an unweighted tree (Cesa-Bianchi et al., 2010). Their algorithm introduces constant error. In the conclusion, they speculate:
"We also believe that an extension general graphs of our algorithm does actually exist. How- ever, the complexity of the methods employed in (Guillory & Bilmes, 2009) suggests that tech- niques based on minimizing Te (L) on general graphs are computationally very expensive." (Cesa- Bessa-Bianchi al., 2010), page 17.
Σ
wii,)) - (1) -y0
(U))EE
is small and show that then in order to optimize label selec- tion one can then focus on selecting a set nodes L for the objective
(L) def min
V
V CV/IC CCVIL
In the meantime, they suggest sampling a random spanning tree as a plausible heuristic for applying their algorithm to general unweighted graphs.
'Google *ETH Zurich, Switzerland. Correspondence to: Simon Meierhans <mssmmon @iif.ethz.ch..
In this article, we show that an efficient and reasonably simple resource augmented algorithm for maximizing v (L) on general graphs exists.
Proceedings of the prnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Algorithms and Hardness for Active Learning on Graphs
Theorem 1.1. Given graph G (V, E, w) with polyno- mially bounded integral edge weights and budget k. there exists an algorithm that returns set L' such that
the graph compared to its size. This reveals some similarity with our problem. Loosely speaking, we aim to select the set L such that GIV \ Lj does not contain very dense sub- graph. This motivates us to construct a similar flow gadget for maximizing (-))
|T/| S Ollog [V]) k and
(L()) 2 maxIevAAss (L).
In our flow gadget, adding vertices to L corresponds to adding new edges, which increases the maximum flow. This yields simple greedy rule we exploit in our algorithm:: Add the vertex whose edge increases the maximum flow the most to L. This measure is submodular, and we are thus able to give guarantees via standard submodular function maximization.
The algorithm runs in time k- EVIVI (IVI+ + [B])++(()) where o1) + 0 as [V] oo.
We point out that such resource augmented algorithms loosely competitive, i.e. our algorithm approxi- mates max V (A:) well for most budgets (Young, 2002; Roughgarden, 2021).
Finally, our flow gadget still requires guess for the value maxiais (L) similar to the guessed average degree ó for densest subgraph. We use binary search obtain our full algorithm.
To complement our algorithm, we also give the first hardness result for maximizing Vr (T...
Theorem 1.2 (Hardness of Approximation). It is NP-hard to decide if
Related work. We restrict our attention to graph problems, and point the reader to (Settles, 2009; Ren al., 2021) for surveys on classical and deep active learning.
maxLeViILIsK (T.) S 2 or
Multiple classic approaches for the passive problem where I. is fixed have been proposed (Blum & Chawla, 2001; Blum et al., 2004; Belkin et al., 2004; Bengio et al., 2006). These introduce the use of smoothness assumptions on the labels.
maxIev;AA|aR (L) 2 3
for general unweighted graphs and labelling budgets k.
We complement our theoretical results with proof-of- concept experiments on both synthetic and real world graphs showing that our algorithm has better experimental perfor- mances than the heuristics presented in (Guillory& & Bilmes, 2009; Cesa- Bianchi et al., 2010).
The active case where the set L is not fixed has received considerable attention (Zhu et al., 2003; Guillory & Bilmes, 2009; Desa-Bianchi et al., 2010; Dasarathy et al., 2015) in the case where the vertices are either selected one-by-one or all at once. Recent approaches have incorporated deep learning (Mac Aodha et al., 2014; Kushnir & Venturi, 2020; Hu et al., 2020; Zhang ct al., 2022b;a). In (Zhang et al., 2022a), learned functions are combined with graph based combinatorial techniques based on (Dasarathy et al., 2015), showing that interesting synergies can emerge when classic approaches are combined with deep learning. Unfortunately, no previous work provides any theoretical guarantees on general graphs.
Technical overview. The most direct template algorithm for approximating max L| (L)
is to build the set L one by one. Our algorithm and the previous algorithms of (Guil- lory& & Bilmes, 2009) and Biesa-Bianchi et al., 2010) all follow this approach. Because the (-) objective is nei- ther submodular nor supermodular", it priori unclear how to choose the next vertex to add without resorting to heuristics." 4
To resolve this issue, we develop a new perspective moti- vated by the densest subgraph problem. In this well-studied problem, one seeks to find an induced subgraph with max- imum average degree (Goldberg, 1984; Boob et al., 2020: Chekuri et al., 2022). Given some target degree 5, (Gold- berg, 1984) proposed a flow gadget for deciding if a sub- graph of average degree 8 exists. Intuitively, a dense sub- graph is cluster which has few connections to the rest of
Roadmap. In Section 2, we introduce some standard nota- tion. Then, we formally introduce the graph label selection problem in Section 3. In Section 4 we reduce the problem to an equivalent problem involving flows, and in Section 5 we present a greedy approximation algorithm exploiting that flow perspective. We show that the problem hard to approximate in Section 6, and present experiments on small graphs in Section 7. Finally, in Section 8 we show that our algorithm can be generalized to vertex importances.
In the numher of vertices [V].
TTo the best of our knowledge.
3 See Appendix A.
2. Preliminaries
*F.g. (Guillory & Bilmes, 2009) suggest adding random ver- tex from current witness cut C' minimizing minogyvz (C, V
Graphs. We consider undirected weighted graphs = (V, F, u)) where V denotes the vertex set and F. C V x V
C)/[C/.
2

---

Algorithms and Hardness for Active Learning on Graphs
denotes the edge set. The vector R contains integral edge weights.
cut and the cut containing all vertices have sparsity oc and O respectively for notational convenience.
We associate an edge-vertex incidence matrix B E I ExV with the graph G. This matrix has exactly two nonzero entries per row. For the edge e = (u, v), we have (ee, u) and B (e, v) = 1. Because the edges of G are undirected, we associate some arbitrary direction with the edges to define the matrix B.
We then define the graph label selection objective as intro- duced in (Guillory & Bilmes, 2009), and introduce slack parameter on the cardinality of the set of selected vertices similar to (Cesa-Bianchi et al., 2010).
Definition 3.2 (Graph Label Selection (GLS)), Given a
graph G = (V, E, w) and a budget S [V], we let
Induced subgraphs. Given some set A C V. we let G[A] denote the induced subgraph on A, i.c. the graph obtained when restricting to the set of vertices in A.
(L)
def =
min CCVLL
Cc
denote the minimum sparsity U2 obtained by cut C' that does not include any vertex in L. The learning set selection objective is then given by
Cuts. For a set C' C V sometimes referred to as cut, we let E[C, V. \ C)) denote the subset of E that only contains edges with exactly one endpoint in C, i.e. the set of edges that cross the cut. Furthermore, we let w (C,VV C) def
(L). LEVILLIK
max
Eee Eeerc, E(C, w(e) denote the sum of the weights of the edges going across the cut.
We call any solution L' such that [L| S s k and
(1 ((+))((E))
max (L)
Flows. For graph G - (V, w) with edge vertex incidence matrix B, we call flow R feasible if -w < f S We say such flow routes the demand
LEV:LL Sk
solution with slack s E Rg0 and error e.
d d B f. In this article, we are interested in flows that route s-t demands, i.e. demand vectors d = a<1, 1.). Maximizing the amount of flow a > such that feasible flow routing exists called the maximum flow problem. Due to recent progress on the more general min-cost flow problem (Chen et al., 2023; van den Brand et al., 2023; Chen et al., 2024; van den Brand et al., 2024), this problem can be solved time m Ologg" 3/4 m log log m) log U where U is an upper bound on the edge weights of G (van den Brand et al., 2024).
We then define the associated decision problem. Definition 3.3 (Thresholded Graph Label Selection (T-GLS)). Given a graph G = (V, E, w). budget k S [V] and a threshold T E Rxo, the thresholded graph label selec- tion problem with slack s is to either
certify that max (L) < <rO
output a set L with | S s such that V(L) 2 T.
Every s-t flow can be decomposed into a set of s-t paths and cycles, and removing all cycles does not change feasibility and the routed demands. By duality, the maximum amount of flow that can be sent from s to with a feasible flow is equal the min-cut mi) w V VC,V\ C).
Solving GLS and weight range compression. Given a (slack s) solution to the T-GLS problem, a (slack 8) solution to the graph label selection problem can be obtained in a straightforward fashion via binary search.
Lemma 3.4. Assume to be given an algorithm T-GLS that solves the T-GLS problem with slack s. Then, there exists an algorithmm that solves the GLS problem for a graph G with slack s using Ollog nU)) calls to T-GLS(G, (G, T, k) where U is upper bound on the edge weights in G.
3. The Graph Label Selection Problem
In this section, we formally define the graph label selection problem. We first define the sparsity of a cut.
Definition 3.1 (Sparsity). For a graph G (V, E, w) and cut @ C V, we let
Proof. The smallest non-trivial threshold is 1/n and the largest is n U-U Furthermore, all thresholds are representable as fractions a/3 where a E [nU] and 3 E [m.] Therefore, a binary search is guaranteed to find a solution of slack s after (log nt) steps.
c def (CC
IC|
Furthermore, we let u def oo, and Vy def 0.
Notice that in Definition 3.1 the cardinality of C' is not bounded by /V1/2 in contrast to the usual definition of spar- sity in the context of vertex expansion. We let the empty
Given Lemma 3.4, we focus on obtaining an algorithm for solving the T-GL. problem.
3

---

Algorithms and Hardness for Active Learning Graphs
(Sink). For every vertex I L, the graph G L.r contains edge (1,t) with weight W +
Observation 4.2. We observe that G a subgraph of GI. if CL
3
We recall the definition of min-cuts from the preliminaries. Definition 4.3 (s-t min-cut), Given graph G = (V, E, w) and two vertices 8, I, the s-t min-cut is given by
Figure 1. On the left hand side, the hest vertex to select into L given budget k 1 is labeled in red. On the right hand side, the best vertices to select given a budget of l = 3 are labeled in red. For this simple graph, selecting the initially best vertex can turn out to be mistake. The amount of error can be increased by increasing the size of star. See also Appendix
mincuto (s, def
min CCVI
w WC,,V\
Next, we relate min-cuts in graphs GL,- to the T-GLS prob- lem. We first state simple observation.
4. Graph Label Selection: A Flow Problem in Disguise
Observation 4.4. mincul (s, 1) S TT
In this section, we take on a flow perspective of the T-GLS problem (Definition 3.3). This yields a new and powerful way to evaluate the usefulness of vertices in conjunction with an existing label set L. Although the GLS problem (Definition 3.2) is neither submodular nor supermodular, this new measure of usefulness of vertices with respect to particular threshold is submodular. We refer the interested reader to Figure for a simple example illustrating some pitfalls and Appendix A for more thorough explanation of submodularity.
Proof. The cut {s} achieves this value regardless of L. Claim 4.5. If minctu (s, < kn.TT then (L) <
Proof. Fix cut S V that achieves the minimum value (SS, V2., \S) mincut G2,- (s, t). Then, let C = S.V.
We first show that L = Assume for the sake of a contradiction that v E L n C. Then, the edge (u, () is in the cut with value W + 1. But removing the vertex from the cut merely adds edges of weight dega(() + 7 to the cut while removing an edge of weight W + ++++1 1. Since dega(v) + < W + T + 1, this contradicts the minimality of S.
Our approach is inspired by Goldbergs reduction from dens- est subgraph to maximum flow (Goldberg, 1984). The dens- est subgraph problem asks to find a set C' C V such that EeePage m(e))
is maximized, which corresponds to the in- duced subgraph with largest average degree. If the graph A-regular, i.e. (v) A, then the density of the subgraph G[C] is directly related to the sparsity of the cut C
We then have
[C]
w (M
mincut
Go,s (s,
graph
<T. IVI
E wee)
w (C, (VV))
max CCV
|C| =
A
min CCV
by Definition 4.1 and our assumption on the value of the min-cut. We directly obtain
|C|
density
sparsity
(CC
We next present flow gadget which captures the sparsity of cuts directly (See also Figure 2).
by canceling terms. Thus, is a sparser than 7 cut that does not contain any vertex in L,, and VT(). S w (C, C)/[CI < T by Definition 3.2.
Definition 4.1 (Flow Graph). Assume to be given an undi- rected graph G = (V, E, w), a set L and a threshold т. Let W denote the sum of the edge weights of G. We then construct graph Gr,r as follows.
Claim 4.6. (f) < r, then mincut G.,, (s.t) < n
Proof. Consider set C C V that certifies (TT. < r, i.e. set C such that w C) < T I.|. Then the cut {s} has value n + (C, V C) - - < T.
(Vertex set). The vertex set of GL, V U (s,t).
(Copy). Every edge e E F is present in Gr,r with the same weight.
Together, Claim 4.5 and Claim 4.6 show an equivalence between s-t min-cuts in GL,, and the T-GLS problem (Def- inition 3.3).
(Source). For every vertex a E V, the graph GL, contains an edge (s, v) with weight r.
4

---

Algorithms and Hardness for Active Learning Graphs
G
Figure 2. On the left, a graph G is displayed with some vertices in I. which are displayed in red. To obtain the graph GL.- as in Definition 4.1, vertices and are added, source s connected every vertex with an edge of weight J, and every vertex in L connected to the sink with an edge of infinite weight co. Now, consider an s-t cut whose left side does not contain as C' in final panel. We observe that total weight |C i V 7. If the weight of the blue edges is less than the weight of the orange edges, then V (L) <.
vertices in L, such blue edges is w(C n V.V. C) and total weight of the orange edges
Lemma 4.7. There is a L of size [L] S k such that
Algorithm 1 T-GLLS T,
(L) 2 T if and only if there exists set L with LL] s k such that mincut (s,t) T.
Input: Graph G = (V, F, w) with n = [ and ELED w(e) = W, threshold T E R, and budget & e [I.....n. L t 0; s [2 log, nW + +2]
Proof. The lemma directly follows from Claim 4.5 and Claim 4.6.
while [L]
l and mincut Go., (s, < nn.7 do u +- arg max .E mincut Grasos (s,
L L Lu {u)
By the min-cut max-flow duality, we observe the following corollary.
end while return L
Corollary 4.8. There is a set L of size [L] < k such that (L) 2 t if and only if there exists set of L with L S k such that the s-t max-flow in Gr, is
Proof. We first observe that the value of the maximum flow in the graph only increases throughout the execution of the greedy algorithm by Observation 4.2. Therefore, the gap y between the current flow and n 7 only decreases.
5. Greedy Approximately Solves Label Selection
Throughout, there a flow supported on at most i ex- tra edges with gap by max (T) > and Claim 4.5. Any such flow routes least g flow over these k edges. Fix integral such flow f. By the pigeonhole principle, routes at least [g/k] over one of the extra edges. Fixing such an edge, and removing all flow paths from to crossing other newly added edges shows that there exists an individual edge that decreases the gap by at least [g/k]]
Given the flow perspective obtained in the previous section, natural greedy criterion for selecting vertices to add to L presents itself: Simply choose the vertex which increases the maximum-flow the most.
Greedy algorithm. In this paragraph, describe our algo- rithm for selecting the set I. given threshold 7. First, we initialize L = 0. Then, while the s-t min-cut in GI.r is not n- 7 and L < 2 log, nW + + k. we iterate over all vertices v E V \ L and compute mincut (zuco) (s, t). We then choose the vertex that achieves the largest min-cut and add it to L. See also Algorithm 1.
Now, consider i consecutive steps of the algorithm with initial gap 9. As long as the gap has not halved, it gets decreased by at least g/ //2k: every step by the argument pre- sented in the previous paragraph with gap g/2. Therefore, the gap gets halved after k steps.
Since the gap is an integer, we conclude that running the algorithm for [2 log(nW) + 21 steps achieves gap because the gap gets halved every ie steps and at most nW the start.
Analysis. In this section, we show that Algorithm solves the T-GLS problem (Definition 3.3).
Lemma 5.1. For a graph G = (V.E, such that maxj.v (L) 2 т, the greedy algorithm finds a set of size T! at most O(log n) k such that Vi (T.) 2 T.
Together with Corollary 4.8, this concludes the proof.
5

---

Algorithms and Hardness for Active Learning on Graphs
Theorem 5.2. There is an algorithm that solves the T-GLS problem (Definition 3.3) for graph with n. vertices and m edges of total weight W with slack Olog RT) that runs in time Onk nW) (2n + m. 2W + 1) where M(2n + m, 20 + 1) denotes the time it takes to compute a maximum flow on a graph with 2n-mm edges with capacities
1. slack Olog nU) and error 0 in (n + m log" 2 U time and;
2. slack ( and ervor e > 0 in O(nk) (n + m))+0()) llog c-1 time.
bounded by 2W+ +
Proof. The first item directly follows from Theorem 5.2 and Lemma 3.4 with current algorithms for computing maxi- mum flows (Chen et al., 2023; van den Brand et al., 2024)
Proof. By Lemma 5.1, we are guaranteed to find a set of size at most (log NT) k whenever a set of size l exists. The runtime bound directly follows from the description of our algorithm.
where we notice that V (L) I U for L + V. The second item follows by Theorem 5.4 and a slightly refined threshold search, where we first find the largest edge weight w w(e) such that the threshold w (e)/n can be achieved, but 2n w(e) cannot by binary search. Such an edge is guaranteed to exist since the optimal threshold has to fall into that range for some edge with largest weight in a witness cut. We may assume e < 1 with no loss of generality. This implies that once we found such a range we can perform binary search with small enough é' </ until we find a close enough approximation. The runtime follows directly.
G
Extremely large edge weights. The guarantee on in Theorem 5.2 becomes meaningless when grows very large, which can happen on graphs with extremely large edge weights w(e) >> n 011), Fortunately, we can avoid this issue by slightly relaxing the guarantee on (I') and rounding edge weights.
Definition 5.3 (Relaxed Thresholded Graph Label Selection (RT-GLS)). Given a graph G = (V, E, w), budget & < [V] and a threshold 7 E Te the thresholded graph label selection problem with slack s and error e is to either
This directly implies Theorem 1.1 as corollary.
certify that maxi.v (L) < T
output set L with |L| S k such that (L) >
Proof of Theorem 1.1. Directly follows from the first item of Theorem 5.5.
(1 (1-e).r.
Given error e, the magnitude of the relevant edge weights can be reduced drastically.
6. Hardness of Approximation
In this section, show hardness of approximation. We first relate our problem to independent sets.
Theorem 5.4. There is an algorithm for RT-GLS (Defini- tion 5.3) for graph with n vertices and edges with slack s (log n/e) that runs in time Onk log 2) M(n + m, W') where M (2n + m, W') denotes the time it takes to compute a maximun flow on a graph with 2n + m edges with weights bounded by W = On (2).
Lemma 6.1. Assume to be given a A-regular unweighted
graph G = (V, E), and threshold T = A. Then (L) 2 A if \ L is an independent set, and (L) S (2A 2)/2 otherwise.
Proof. We first remove all edges with weight less than er (2n) from the graph. For any cut, these edges contribute at most cT 2 mass. Edges with weight larger than 27 n can be reduced to 27- without affecting the solution, since any cut that includes such edges has ratio at least 2r. This reduces all the edge weights to the range [cT (2m), 2T n] Dividing all the edges by et /10 and rounding up again intro- duces at most error eT/2 when sealing back to the original magnitude. We then obtain our result via running the al- gorithm from Theorem 5.2 on the graph with the rounded down edge weights and scaling up the solution.
Proof. If two vertices u in V L are be adjacent, they form a cut C = {u, e} of value Ve = (2A 1)/2 < A that does not include a vertex in L.. Otherwise, V / is an independent set and we obtain (L)) 2 3 directly.
See Figure for an illustration of our reduction from maxi- mum independent set on regular graphs.
D
Proof of Theorem 1.2. The maximum independent set prob- lem is NP-hard even on graphs which are 3-regular (Fleis- chner et al., 2010; Alimonti & Kann, 2000). Therefore, the theorem follows from Lemma 6.1, since we could otherwise test for the existence of independent sets of size n - k for arbitrary k.
We conclude this section with our main result.
Theorem 5.5. There is an algorithm that solves the GLS problem (Definition 3.2) for a graph with maximum integral edge weight U with
6

---

Algorithms and Hardness for Active Learning on Graphs
the largest connected component (4158 vertices).
Results. We report the results for the simple graphs in Table 1. For S(50) our algorithm and (Cesa-Bianchi Bianchi et al., 2010) always choose the center of the star, but (Guillory & Bilmes, 2009) often chooses 3 leaves. For 3C(10,30, 10), our algorithm and the algorithm of (Guillory & Bilmes, 2009) always chooses one vertex from each clique, which the algorithm of (Cesa-Biancee et al., 2010) fails to do.
Figure 3. This figure shows two graphs with vertices in L depicted in red. On the left hand side, the non-labeled vertices form an independent set, Therefore, 7 = A = 3. On the right hand side, they do not. Choosing two connected vertices proves that there is a cut of sparsity 4/2 = 2.
We plot the trade-off between budget and ratio for the Davis southern woman graph in Figure 4.
Finally, we report he results for the SNAP graphs in Table 2.
7. Experiments
In all the experiments we notice that our algorithm obtains better performance than previous work.
To complement our theoretical results, we run a proof-of- concept experiment where we compare our algorithm prac- tical performance with the previous algorithms of (Guillory & Bilmes, 2009) and that the algorithm of (Guillory & Bilmes, 2009) is heuristic, whereas the algorithm of Beeac-Biancch et al., 2010) guaran- tees constant slack on unweighted trees. To handle arbitrary unweighted graphs, the authors suggest to sample a random spanning tree of the graph before running their algorithm.
We remark that when the size of the label set approaches n, our algorithm gets outperformed by (Guillory & Bilmes, 2009). A simple reason for this behavior is that for a star graph our algorithm always includes the center, whereas the algorithm of (Guillory & Bilmes, 2009) sometimes picks all the leaves. For h = n 1, it is advantageous to pick all the leaves (See Figure 1).
et al., 2010). We recall
We point the interested reader to Appendix C for additional experiments on synthetic graphs
Experimental setup. For all experiments, gorithm of (Guillory& & Bilmes, 2009) for maximizing (-) and the algorithm of -eesa-Bianchi et al., 2010) 10 times and report the mean and standard deviation for the achieved ratio V (L.. Since our algorithm is deterministic, we simply report the ratio. We don't allow any slack the budget k when evaluating the algorithms."
the al-
Interpretable Example Graphs for k =
Graph
S(50)
3C(10, 30, 10)
(Guillory Bilmes, 2009)
0.16
1.0 + 0.0
(Cesa-Bianchi al., 2010) Ours
1.0
0.1 + 0.03
1.0
1.0
Table I. Experimental results for interpretable example graphs rounded to two digitis after the decimal point.
We first evaluate the algorithms on two simple graphs that cause the previous heuristic algorithms to fail. The first such graph is the star on 50 vertices, which we denote as S(50). The second graph 3C(10, 30, 10) is obtained by taking path consisting of 3 vertices, and replacing the central vertex with a clique of size 30 and the two degree one vertices with a clique of size 10 each.
8. Generalizing to Vertex Importances
If the data set contains outliers, our methods are highly en- couraged to label them. (Guillory & Bilmes, 2009) point out that this leads to sub-par performance on many real- world data sets. We present natural remedy for this issues by generalizing the GLS problem to vertex importances f V + Rzo- The vertex importance function allows re- moving weight from outliers. A particularly natural function is f(-) = deg(-). Then, sparsity corresponds to conductance and vertices that are very dissimilar to all other vertices re- ceive a low importance.
We then explore the full trade-off between budget k and T (T.) for the Davis southern woman graph (Davis et al., 1941). This is small graph modeling social circle con- sisting of 32 vertices.
Finally, we run experiments on two real world graphs from the Stanford Network Analysis Project (SNAP) (Leskovec & Krevi, 2014). The graph ca-GrQc models the Arxiv GR-QC (General Relativity and Quantum Cosmology) collaboration network and ego-Facebook is a Facebook friend network. Since ca-GrQe is not connected, we run the algorithms on
Definition 8.1 (Importance Sparsity). For a graph G
'With small budget, labeling vertices with high degree is generally advantageous since they cover a large part of the graph. When the budget approaches n., these are vertices for which one can learn lot without laheling them, and it therefore becomes advantageous to label their neighborhood instead.
'We provide the code used for running the experiments label__
under https:/// //t/////ttttb// www.tttww..c.e.eeeeeeeeeee seles selection.
7

---

Algorithms and Hardness for Active Learning Graphs
Graph
ca-GrQe (n = 4158)
ego-Facebook (n 4039)
Budget
k = 10
k = 50
h: = 100
k = 10
= 50
k: = 100
GB
0.015=0.000
0.066=0.0011
0.132=0.011
0.076=0.008
0.396=0..055
0.777+0.055
BGVZ
0.054+1.0006
0.002
0.002
0.037
0.300
0.831
Ours
0.091
0.215
0.333
1.0
1.0
1.080
Table This table compares the ratio vr achieved by GB (Guillory & Bilmes, 2009), BGVZ
et al., 2010) and our
algorithm for several budgets on real world graphs from the Stanford Network Analysis Project (Leskovec Krevl, 2014). We round to three digits after the decimal point.
Davis Southern Woman
solution with slack E Rgo-
Guillory Bilmes
Cesa-Bianchi et al.
Next, show that our algorithm can be extended to also solve the I-GLS problem directly.
Ours
Theorem 8.3. Assume be given a graph G = (V, E, w) alongside vertex function f V Rz0 and bud- get k, such that w(e) E 1122....IVjoul
and f(v) E {1, 21. IV....I/ea (0))} for all E E and E V respectively. Then, there exists an algorithm that returns a set L' such that
0
5
25
30
|T'| S O(loglVV and
VV()) 2 maxLeVaLISE (L.).
Figure 4. The full trade-off between the budget and the achieved threshold for the Davis southern woman graph (Davis et al., 1941).
The algorithm runs in time k [V] (VV [E)) where o11) goes to as [V] approaches infinity.
Remark 8.4. We assume that the similarity vector w and the vertex importances f(-) are polynomially bounded in [V] for ease of presentation. Slightly relaxing the objective allows removing this assumption analogously Theorem 5.5.
(V. F,, w), positive vertex function f V ~ R20 and cut 1 C V. we let
ve def WCCV
S(V)
Since the proof of Theorem 8.3 directly follows the outline of the proof of Theorem 1.1 we only sketch the alterations and include a full proof in Appendix for completeness.
where f(V) def Ever f(e). Furthermore, we let vol def and v4 def 0.
Notice that for the constant function f(-) = 1, we obtain V/ c for all C and Definition 8.1 therefore generalizes Definition 3.1. We then define the I-GLS problem, which is a generalization of the GLS problem Definition 3.2.
Proof sketch of Theorem 8.3. To incorporate the impor- tance function f V + R200 into the flow gadget from Definition 4.1, we simply multiply the edge weight of (s, v) with the importance f(v) of vertex for every edge adjacent to We furthermore increase the weight of the edges (u, for E L sufficiently such that they are still effectively infinite.
Definition 8.2 (I-GLS). Given a graph G (V, E, w), positive vertex function f V + Rzo and budget
k < V.. we let
Then, by following the proof outline of Claim 4.5 and Claim 4.6, we directly observe that this altered gadget de- cides the threshold version of Definition 8.2. This again enables solve the problem using binary search.
T
def
min CCViL
T.C
The I-GLS objective is then given by
max (L).
T (L).
LCViLLIK
9. Conclusion
We call any solution L' such that LL| and
We present the first approximation algorithm for maximizing the graph label selection objective V/ (L) ) in a general graph with theoretical guarantees, and extend the case where
v (L))
max y yL( LEViLLik
8

---

Algorithms and Hardness for Active Learning on Graphs
not all data points are equally important. We also show that maximizing (T. to high accuracy is NP hard. Finding better resource augmented algorithms well as finding approximation algorithms for (L) without relaxing the cardinality constraint remain interesting open problems." ? Furthermore, it is interesting whether our lower bound can be strengthened or extended to more natural graph instances.
delberg. ISBN 978-3-540-27819-11
Bengio, Y., Delalleau, O., and Roux, N. Label propagation and quadratic criterion. Semi-Supervised Learning, 09 2006. doi: 10.755 7 000.0001000
Blum, A. and Chawla, S. Learning from labeled and un- labeled data using graph mincuts. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML '01, pp. 19-26, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558607781.
Although our algorithm is relatively practical, runs time much larger than linear. This prevents from scaling to large real world graphs. However, it is encouraging that much faster approximation algorithms for the densest sub- graph problem have been developed (Chekuri et al., 2022). is an interesting research direction to understand whether similar techniques could drastically improve the scalability for graph label selection, which would enable gathering experimental results on larger scale. We remark that sub- modular optimization is highly sensitive to adversarial noise (Hassidim & Singer, 2017), and therefore approximate flow oracles as developed in (van den Brand et al., 2024) cannot be used directly to speed up our algorithm.
Blum, A., Lafferty, J., Rwebangira, M. R., and Reddy, R. Semi-supervised learning using randomized min- cuts. In Proceedings of the Twenty-Firs. International Conference Machine Learning, ICML '04, pp- 13, New York, NY, USA, 2004. Association for Comput- ing Machinery. ISBN 1581138385, doi: 10.1145/ 0015330.1015422 URL attps://dol org.:/1 1 1145/1015330 1015429..
Acknowledgments
Boob, D., Gao, Y., Peng, R., Sawlani, S., Tsourakakis, C., Wang, D., and Wang, J. Flowless: Extracting densest subgraphs without flow computations. In Pro- ceedings of The Web Conference 2020, WWW '20, pp. 573-583, New York, NY, USA, 2020. Associa- tion for Computing Machinery. ISBN 9781450370233. doi: 10. 1..1141//66442333881011
Simon Meierhans is supported by Google PhD Fellowship and grant no. 200021 204787 of the Swiss National Science Foundation.
Impact Statement
URL https: //doi. 3380140.
org / 10.
This paper presents work whose goal advance the field of Machine Learning. The nature of our work is mainly theoretical, and thus our insights might find use in various areas.
Cesa-Bianchi, N., Gentile, C., Vitale, F., and Zappella, G. Active learning on trees and graphs. In COLT 2010: the 23rd conference learning theory, Haifa, Israel, June 27-29, 2010, pp. 320-332. COLT, 2010.
References
Chang, H. and Yeung, D.-Y. Graph laplacian kernels for object classification from single example. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 06), volume 2, pp. 2011- 2016. IEFF, 2006.
Alimonti, P. and Kann, V. Some apx-completeness results for cubic graphs. Theoretical Computer Science, 237(1):123- 134, 2000. ISSN 0304-3975.
doi: http:///ohoan///000o000004449919 com/
URL sttps::/www.scceeceeet/ee httpa////artcceeeaa//////9993339
Chekuri, C., Quamrud, K., and Torres, M. R. Densest Sub- graph: Supermodularity, lterative Peeling, and Flow, pp. 1531-1555. Society for Industrial and Applied Mathematics, 2022. doi:
Belkin, M., Matveeva, I., and Niyogi. P. Regularization and semi-supervised learning on large graphs. In Shawe- Taylor, J. and Singer, Y. (eds.), Learning Theory, pp. 624-638, Berlin, Heidelberg, 2004. Springer Berlin Hei-
URL https: : /ttpbswww..see//eee siam. 1137/1 0057/1.981111 07 64.
"We remark that the example in Figure 1 hints that greedy algorithms might not be suitable to obtain the latter.
Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M. P., and Sachdeva, S. Almost-linear-ting algorithms for maximum flow and minimum-cos flow. Commun. ACM, 66(12):85 92, November 2023. ISSN 0001-0782. doi: 10..440/ URL https: doii org/10. 1145/36100 0940.
'aaing to evaluate the flow gadget [V] times to add the first edge is the practical bottleneck of our algorithm. Thereafter, one can prioritize checking vertices that provided high benefit in the previous round and exploit that the benefit is monotonically de- creasing.
9

---

Algorithms and Hardness for Active Learning Graphs
Chen, L., Kyng, R., Liu, Y. P., Meierhans, S., and Probst Gutenberg, M. Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, S-l shortest path, and minimum-cost flow. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 1165-1173, New York, NY, USA, 2024, Asso- ciation for Computing Machinery. ISBN 9798400703836. doi: 10. 1451111 3649745.. URL https::/cco. org/ / 10. 111111/33610 215.///366666...646665555
URL TRthttt/////preediiii ngs ml prwss/ hassidim haa.ddiimaa...tt html.
Herbster, M. and Lever, G. Predicting the labelling of a graph via minimum p-seminorm interpolation. In NIPS Workshop 2010: Nenworks Across Disciplines: Theory and Applications, 2009.
Hu, S., Xiong. Z., Qu, M., Yuan, X., Côté, M.-A., Liu, Z., and Tang, Graph policy network for transferable active learning on graphs. In Larochelle, H., Ran- zato, 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 http://///p cc ccc/sappr__fille/pppee////////22
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 Ma- chine Learning Research, pp. 503-522, Paris, France, 03- 06 Jul 2015. PMLR. htRpst:::: /proceedinggs mlr. press / / v 1000v4/Daaaaae /aw.aaaaaaaaaa...a .ttml.
73 37140088ccec25550000000d33333333 Paper. pdf.
Davis, A., Gardner, B. B., Gardner, and R., M. Deep South; a social anthropological study of caste and class. Univer- sity of Chicago Press, 1941.
Kushnir, D. and Venturi, L. Diffusion-based deep active learning. arXiv preprint arXiv:2003. 10339, 2020.
Leskovec, J. and Krevl, A. SNAP Datasets: Stan- ford large network dataset collection. http://snap. stanford. wewerdddddueeee aaw/ddatta June 2014.
Fleischner, H., Sabidussi, G., and Sarvanov, V. I. Maximum independent sets 3- and 4-regular hamiltonian graphs.
Discrete Mathematics, 310220)2742-2749, 2010. ISSN 0012-365X.
Mac Aodha, O., Campbell, N. D., Kautz, J., and Brostow, G. Hierarchical subquery evaluation for active learning on a graph. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2014.
URL https///oooor//10000111....ssss: com/
doi:
/ /tt0//00110000000000000 0001974.
Graph Theory Dedicated to Carsten Thomassen on his 60th Birthday.
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. 11111/..4115/342...
Goldberg, A. B. and Zhu, X. Seeing stars when there aren't 't semi-supervised learning for sentiment categorization. In Proceedings of TextGraphs: The first workshop on graph based methods for natural language processing, pp. 45-52, 2006.
many stars:
Roughgarden, T. Resource Augmentation, pp. 72-92, Cam- bridge University Press, 2021.
Goldberg, A. V. Finding a maximum density subgraph. Technical report, University of California at Berkeley, USA, 1984.
Settles, B. Active learning literature survey. Technical report, University of Wisconsin Madiison Department of Computer Sciences, 2009.
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::/prcceeeinggg. neurips... oc cc/paper_filee/ppeeeeeeeeeeeeeee
Shin, H., Tsuda, K., and Schölkopf. B. Protein functional class prediction with combined graph. Expert Systems with Applications, 36(2):3284 3292, 2009.
htaper_fflles/speer//20/////1 90794e e pdf.
van den Brand, J., Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M. P., Sachdeva, S., and Sidford, A. A deterministic almost-linean time algorithm for minimum- cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 503-514, 2023. doi: 10. LL000FFOCS599990222...0000
Hassidim, A. and Singer, Y. Submodular optimization under noise. In Kale, S. and Shamir, O. (eds.), Pro- ceedings of the 2017 Conference on Learning The- ory, volume 65 of Proceedings of Machine Learn- ing Research, pp. 1069-1122. PMLR, 07-10 Jul 2017.
van den Brand, J., Chen, L., Kyng. R., Liu, Y. P., Meierhans, S., Gutenberg, M. P., and Sachdeva, Almost- linear time
10

---

Algorithms and Hardness for Active Learning Graphs
algorithms for decremental graphs: Min-cost flow and more via duality. In 2024 IEEE 65th Annual Symposium Foundations of Computer Science (FOCS), pp. 2010- 2032, 2024. doi: A..1099/FCCS012262222000000001
Watts, D. J. and Strogatz, S. H. Collective dynamics of "small-world networks. Nature, 343466644)))44444444 1998. doi: 1038/39939 URL utttttp:://ooo.rrg
10. 1038/03///000 1030//0998...
Young. On-line file caching, Algorithmica, 33(3):371-383,
2002. doi: 1010007/00055-000-014455. URL https:
Zhang. J., Katz-Samuels, J., and Nowak, R. GALAXY: Graph-based active learning the extreme. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C.. Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 26223-26238 26238. PMLR, 17-23 Jul 2022a. URL https: /ptppppeeongss..... mlr. press/vl 62/ whwpgg222 html.
Zhang, W. Wang, Y.. You, Z., Cao, M., Huang, P., Shan, J., Yang, Z., and Cui, B. Information gain propagation: a new way to graph active learning with soft labels. arXiv preprint arXiv:2203. 0/093, 2022b.
Zhu, X., Ghahramani, Z., and Lafferty, J. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the Twentieth International Confer- ence on International Conference on Machine Learn- ing, ICML'03, 03, pp. 912-919, AAAI Press, 2003. ISBN 1577351894.

---

Algorithms and Hardness for Active Learning Graphs
A. Submodularity
Submodular functions are an important function class combinatorial optimization. We first state one of multiple equivalent definitions of submodularity.
Definition A.1. A function f 2 + called submodular for all X, Y E and a E A such that X C we have f(X - (a)) f(X) 2 -
- {a])
((Y).
Intuitively, this corresponds to the notion diminishing returns. We re-consider the simple example from Figure I in Figure 5, and observe that (XX U {a}) (X) = 0 whereas ViY U {a}) v = 2.
X
Figure 5. A star graph with 3 leaves and sets X = {02). Y fuz, hs and a = v4 is counterexample to vr(-) being submodular. We have ((X)= (Y)
well as (XU(a)) = 1. But (YUU))) which implies -(XU(a))- (XX) W(YU(a))-V())
Therefore the function (-) is not submodular.
Next, we define supermodularity.
Definition A.2. A function f 2 + IR is called supermodular, if f is submodular.
Unfortunately, the function (-) is also not supermodular. To show this, we consider line graph on 4 vertices in Figure 6.
Y
X
Figure 6. We let Y (ez, v4 and X (ex). Then, we have (X) 1/3 and V\(Y) 1/2. For u2, obtain VIX (a)) 1, and (Y (f})) = 1. We obtain (X (a)) ((x) > (Y V (YY),, which shows that the function (+(-) is not supermodular either.
In contrast to the function (-),, the function 2" R defined by f(A) mincut (s, (See Definition 4.1) is submodular. Recall that every vertex v E A corresponds adding an edge (u, b) G We can observe that all the extra flow that can be routed when adding the edge (a,t) to Gy can also be routed when adding (a, t) to Gx.
B. Proof of Theorem 8.3
To prove Theorem 8.3, first introduce generalization of our flow gadget. Definition B.1 (f-Flow Graph). Assume to be given an undirected graph = (V, E, w). a function f + R2o, set and threshold r. Let W denote the sum of the edge weights of G. We then construct graph C%,, as follows.
(Vertex set), The vertex set of @f V (s,
(Copy). Every edge E is present in //,, with the same weight.
(Source). For every vertex E V. the graph GL,, contains an edge (s, v) with weight f(v) -
(Sink). For every vertex 1 E T., the graph G contains edge (1, t) with weight W + f(r) -
We then show analogous claims Claim 4.5 and Claim 4.6.
12

---

Algorithms and Hardness for Active Learning Graphs
Claim B.2. If minnnuua (8, 1) < I(V) T, then v (L) <.
Proof. Fix some s-t min-cut C in G As in the proof of Claim 4.5, we have that C V # 0 as otherwise mincuta (s, = f(V) We then have
wCC,V10)+ (C) ()
mincut G2. (s,t)
<T.f(V)
and obtain ((C.V) S(C) by reordering and f(V) - f(V \C) f(C). This concludes the proof of the claim.
Claim B.3. (T) < t, then mincutaa. G2.- (8, < ((C)
Proof. Consider a set C S V that centifies V (L) T, i.e. set such that w (C, V C) TT.((C), Then the cut {s) UC has value [(V)T + w(C, V C) S(C) ((C) T. This concludes the proof of the claim.
Proof of Theorem 8.3. We first show that there an algorithm that either
certify that max / (L) < r or
output a set with L| S l such that T (L) 2
using ||| calls to maximum flow oracle. This generalization of the T-GLS problem (Definition 3.3) can be solved by adapting flow gadget to G/,, (Definition B.1). By Claim B.2 and Claim B.3 the set L achieves threshold if and only if the s-t min-cut in 8/,, is 7 f(V).
By an analogous argument to the proof of Lemma 5.1, the greedy algorithm with slack Ollog n) finds a solution obtaining threshold 7 if size solution achieving threshold tau exists.
The theorem follows from standard binary search analogous to the proof of Lemma 3.4.
C. Additional Experiments on Synthetic Graphs
We explore the trade-off' between budget and objective for various Watts-Strogatz random graphs with 50 vertices. We let Wttts-Strogatz500, d, p) refer to the Watts-Strogatz graph with average degree and re-linking probability p (Watts Strogatz, 1998) and perform experiments for the graphs Sutts-Strogat((50, 4, 0.1), Watts- Satts-Strogatz(51) 4, 0.2),, Watts- Strogatz(50,, 8, 0.1) and Satts-Strogatt(50,. 8, 0.2).
For each of these graphs, al., 2010) for all budgets k and plot the mean and standard deviation after 10 experiments for the algorithms involving randomization.
algorithm well as the algorithms of (Guillory & Bilmes, 2009) and Desa-Bianchi
The results of our experiments are shown in Figures 7 to 10. We again observe that our algorithm outperforms the previous algorithms.
13

---

Algorithms and Hardness for Active Learning Graphs
Watts Strogatz(50,, 4, 0.1)
5
Guillory Bilmes
Cesa-Bianchi et al.
4
Ours
3
2
1
0
0
10
20
30
40
50
k
Figure 7. Trade-off between the budget & and the achieved threshold for Watts-Strogatz random graph with degree 4 and rewiring probability 0.1 on 50 vertices (Watts & Strogatz, 1998).
Watts Strogatz(50,, 4, 0.2)
Guillory Bilmes
5
Cesa-Bianchi et al.
Ours
4
33
2
1
0
10
20
30
40
50
k
Figure Trade off between the budget & and the achieved threshold for Watts-Strogatz random graph with degree 1 and rewiring probability 0.2 on 50 vertices (Watts & Strogatz, 1998).
14

---

Algorithms and Hardness for Active Learning Graphs
Watts Strogatz(50, 8, 0.1)
10
Guillory Bilmes
Cesa-Bianchi et al.
Ours
10
20
30
40
50
k
Figure 9. Trade-off between the budget & and the achieved threshold for a Watts-Strogatz random graph with degree 8 and rewiring
probability p 0.1 50 vertices (Watts & Strogatz, 1998).
Watts Strogatz(50, 8, 0.2)
Guillory Bilmes
10
Cesa-Bianchi et al.
Ours
C
10
20
k
Figure 10. Trade-off between the budget &s and the achieved threshold for a Watts-Strogatz random graph with degree 8 and rewiring probability 0.2 50 vertices (Watts & Strogatz, 1998).
15


Reviews:
[{"review_id": "LqFHbGDHBA", "reviewer": "Reviewer_qHp3", "summary": "This paper tackles the problem of *active learning on graphs* under a label smoothness assumption. The authors study how to select a set of $k$ labeled vertices in a graph such that the labels can best predict all other vertices’ labels. The core contributions are two-fold: **(1)** a new **approximation algorithm** (with resource augmentation) that is the first to offer theoretical guarantees on general graphs, and **(2)** a **hardness result** proving that no efficient algorithm can achieve high accuracy in general without relaxing the problem. Specifically, they present an algorithm that, using an $O(\\log n)$ larger label budget, achieves an objective value at least as good as the optimal set of $k$ labels. In complement, they prove it is NP-hard to distinguish whether the optimal value is small (2) or moderately larger (3), implying a constant-factor hardness of approximation for the exact budget-$k$ problem. Beyond theory, the paper includes proof-of-concept experiments on both synthetic graphs and real-world graph datasets, which indicate that the proposed method outperforms prior heuristics on this task.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer qHp3,\n\nThank you for your thoughtful review, we will address your comments in the final version. Here we will focus on responding to the points you raised. \n\n1) Scalability: We agree that the scalability, together with removing the resource augmentation requirement, is the main research question left open by our work. Given the progress on linear time algorithms for the related densest subgraph problem, we hope that further work can remove this deficit. This might come at the cost of further relaxing the theoretical guarantees. \n\n2) Resource Augmentation Requirement: We agree with your assessment that a proper approximation algorithm that does not expand the budget would be interesting from a theoretical and practical point of view. A theoretical reason for the observed practical performance of our algorithm in this regime is that a resource augmented algorithm is also competitive for many values of $k$. This phenomenon is observed in a classic text by Tim Roughgarden and called loosely competitive (https://arxiv.org/abs/2007.1323).\n\n3) Experiment Limitations: Due to the large number of maximum flow computations, we were unable to scale up our experiments to larger graphs. In our implementation (see supplementary material) we already parallelize the implementation of the algorithm to enable our current experiments in a reasonable timescale. We hope that future work motivated by these preliminary experiments will significantly reduce the time complexity. \n\n4) Focus on Batch Selection: We focus on the batch selection problem as previous work in the area. We agree that an appropriate model of adaptivity could serve as a starting point for further fruitful research. We will leave it as an open direction for future work in the final version \n\n5) Minor Clarity Issues: We will go over the writeup again to further improve the exposition and clarity of the proofs. \n\n6) Experiment Limitations: Using maximum flow as a subroutine, and calling it at least as often as there are vertices, unfortunately means that this algorithm does not scale to large graphs as is. We already parallelized part of the implementation (see supplementary material) to enable the current experiments. As discussed in the first point, improving the scalability is a major open problem, now that a polynomial time solution has been found.", "claims_and_evidence": "The paper’s claims are generally well-supported by theoretical arguments and empirical validation. The **approximation guarantee** (the first efficient algorithm with theoretical bounds for general graphs) is clearly stated and backed by rigorous proofs. The **hardness result**, which demonstrates NP-hardness of achieving high accuracy for the considered objective, is convincingly justified by a known reduction from a well-studied NP-hard problem. Experimentally, the authors substantiate their claim of improved performance by comparing the proposed algorithm to baselines (Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010) on both synthetic and real-world graphs, consistently showing superior results. The authors responsibly qualify their contributions by explicitly noting limitations such as resource augmentation and computational complexity, making their claims balanced and credible.\n\nGuillory & Bilmes, 2009: Label selection on graphs.\nCesa-Bianchi et al., 2010: Active learning on trees and graphs.", "methods_and_evaluation_criteria": "The proposed methodology leverages a reduction of the graph label selection problem to a **flow-based formulation** inspired by the densest subgraph problem. The authors introduce a *flow gadget*, where labeling vertices translates into adding edges to increase the max-flow, enabling a greedy selection process. Though the original objective $\\Psi(L)$ is neither submodular nor supermodular, the derived surrogate measure (flow increase) is submodular, allowing established submodular optimization guarantees. They complement this with a binary search approach to efficiently pinpoint feasible threshold values. Technical assumptions (like polynomially bounded edge weights) are clearly stated and justified, with full details provided in appendices.\n\nThe evaluation methods—worst-case approximation analysis and empirical $\\Psi(L)$ values—are appropriate for the theoretical nature of the paper. Empirically, the authors demonstrate improvements over baseline methods through controlled experiments on both synthetic and real-world graphs. While the evaluation does not directly address prediction accuracy, the chosen proxy ($\\Psi(L)$) suitably reflects the intended smoothness goal. Overall, the methods and evaluation criteria are thoughtfully designed, effectively validating the proposed approach.", "theoretical_claims": "The theoretical claims are significant and appear correct based on the provided material. The main results include:\n\n- **Approximation Algorithm (Theorem 1.1):** By allowing a factor-$O(\\log n)$ more labels than the budget $k$, the algorithm achieves an objective equal to the optimal solution for exactly $k$ labels. The authors provide a plausible proof sketch (detailed proofs in Appendix B), relying on standard submodularity and flow techniques. The assumptions (e.g., polynomially bounded integral weights) are clearly stated and reasonable.\n\n- **Hardness Result (Theorem 1.2):** The authors show it is NP-hard to distinguish between cases where the optimal value is at most 2 or at least 3, implying constant-factor hardness of approximation. This reduction from known NP-hard problems on 3-regular graphs seems correct and convincing, clearly establishing the problem’s theoretical difficulty.\n\n- **Generalization to Weighted Vertex Importance:** The paper extends the approximation results to scenarios with vertex importance weights, offering a generalization that appears logically sound and consistent, though I did not verify proofs exhaustively.\n\nOverall, the theoretical contributions are rigorous, clearly presented, and supported by well-known techniques. While the runtime complexity ($(|V|+|E|)^{1+o(1)}$ per iteration) is slightly super-linear and somewhat limits practical scalability, it does not undermine the theoretical validity of the results presented.", "experimental_designs_or_analyses": "The proposed method uses a flow-based formulation inspired by the **densest subgraph** problem, constructing a flow gadget to guide greedy vertex selection. Although the original label selection objective ($\\Psi(L)$) is neither submodular nor supermodular, the authors identify a submodular surrogate measure (flow increase), enabling standard greedy approximation techniques. They combine this with binary search for threshold estimation, clearly outlining assumptions and deferring details to appendices.\n\nThe evaluation methodology (theoretical approximation ratio, empirical objective values) is suitable for the paper's goals. Empirical results on synthetic corner-case graphs and two real-world graphs from SNAP consistently demonstrate better performance over baseline methods (Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010). A notable limitation is the relatively small scale of experiments (max ~4k nodes), acknowledged by authors due to computational complexity. Nonetheless, the experiments convincingly support the claims within the tested scope. Reproducibility is reasonably addressed through clear descriptions and standard datasets, though explicit code release is not mentioned.\n\nGuillory & Bilmes, 2009: Label selection on graphs. Cesa-Bianchi et al., 2010: Active learning on trees and graphs.", "relation_to_broader_scientific_literature": "The paper positions itself clearly within existing literature, referencing both foundational works and recent advancements in relevant fields, specifically:\n\n- **Graph-based Semi-supervised Learning:**\n  (Blum & Chawla, 2001; Zhu et al., 2003; Belkin et al., 2004; Bengio et al., 2006).\n- **Active Learning on Graphs:**\n  (Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010; Dasarathy et al., 2015)\n- **General and Deep Active Learning:**\n  (Settles, 2009; Ren et al., 2021; Mac Aodha et al., 2014; Kushnir & Venturi, 2020)\n- **Algorithmic Graph Theory (densest subgraph):**\n  (Goldberg, 1984; Boob et al., 2020; Chekuri et al., 2022)\n\nOverall, the paper effectively builds upon previous theoretical frameworks (e.g., Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010) and clearly outlines how it extends prior limitations, such as handling general graphs rather than special cases (trees). While the paper does not deeply explore sequential active learning, this omission is justified given its scope.\n\n### Standard Citations:\n\n- Blum, A., & Chawla, S. (2001). *Learning from labeled and unlabeled data using graph mincuts.* ICML.\n- Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). *Semi-supervised learning using Gaussian fields and harmonic functions.* ICML.\n- Belkin, M., Matveeva, I., & Niyogi, P. (2004). *Regularization and semi-supervised learning on large graphs.* COLT.\n- Guillory, A., & Bilmes, J. A. (2009). *Label selection on graphs.* NeurIPS.\n- Cesa-Bianchi, N., Gentile, C., Vitale, F., & Zappella, G. (2010). *Active learning on trees and graphs.* COLT.\n- Dasarathy, G., Nowak, R., & Zhu, X. (2015). *S2: An efficient graph-based active learning algorithm.* COLT.\n- Settles, B. (2009). *Active learning literature survey.* University of Wisconsin-Madison.\n- Ren, P., et al. (2021). *A survey of deep active learning.* ACM Computing Surveys.\n- Mac Aodha, O., Campbell, N. D., Kautz, J., & Brostow, G. J. (2014). *Hierarchical subquery evaluation for active learning on a graph.* CVPR.\n- Kushnir, D., & Venturi, L. (2020). *Diffusion-based deep active learning.* arXiv preprint arXiv:2003.10339.\n- Goldberg, A. V. (1984). *Finding a maximum density subgraph.* Technical report, UC Berkeley.\n- Boob, D., et al. (2020). *Flowless: Extracting densest subgraphs without flow computations.* WWW.\n\nOverall, the literature review is thorough and clearly situates the paper’s contribution within the broader field.", "essential_references_not_discussed": "No essential references appear missing. Literature coverage seems thorough, and relevant works are adequately cited.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- Theoretical novelty: providing approximation guarantees for general graphs.\n- Creative algorithmic insights: clever use of max-flow reduction and submodular optimization framework.\n- Well-presented theoretical results with careful, rigorous reasoning.\n- Useful extension to vertex importance scenarios.\n\n**Weaknesses:**\n\n- *Scalability:* A notable weakness is that the proposed algorithm is **computationally intensive**, with a runtime that is super-linear in the number of vertices. The authors admit it doesn’t scale to very large graphs. In an era where graphs can have millions of nodes, an algorithm that likely struggles beyond a few thousand nodes has limited immediate application. This is somewhat inherent given the complexity of the problem, but it does mean the practical impact is curtailed until further optimizations are found.\n- *Resource Augmentation Requirement:* The approximation guarantee is achieved by using up to $O(k \\log n)$ labels instead of $k$. From a theoretical perspective this is fine (and indeed common in approximation algorithms), but from a practical standpoint, it means the method might need substantially more labeled data than one’s budget in order to guarantee optimal results. In the experiments, they ran it with exactly $k$ labels and it still outperformed others, but there’s no guarantee in that regime. In scenarios where label budget is strict, one might wonder how suboptimal the greedy picks could be if cut off at $k$. This gap between theory (with augmentation) and practice (fixed budget) is worth noting as a weakness, though the empirical evidence suggests the algorithm still performs well without augmentation.\n- *Focus on Batch Selection:* The paper addresses the *offline* (batch) selection problem. It does not consider the fully sequential active learning setting where one can query a label, update the model, and then choose the next query. The batch selection is an important scenario on its own (and often needed for parallel labeling), but it’s inherently a restricted version of active learning. The contribution is still valuable, but it doesn’t solve the entire active learning problem on graphs – only the one-shot selection version. Future work might need to explore how these results extend (or not) to an interactive setting.\n- *Minor Clarity Issues:* While generally well-written, some parts of the proof sketches and the description of the approach are dense. For instance, the flow gadget construction might be hard to follow for readers not versed in network flow. The paper relies on the appendix for full clarity. Additionally, some terminology like “constant slack” (used to describe the prior tree algorithm’s approximation) or “resource augmentation” could have been defined in a more reader-friendly way early on. These are relatively minor weaknesses in exposition.\n- *Experiment Limitations:* The experiments, as mentioned, are on small graphs and a limited number of datasets. The paper might have benefited from at least one medium-scale experiment (if feasible) or some discussion on how the algorithm behaves as graph size grows (e.g., a plot of runtime or objective vs. $n$). Reproducibility could also be enhanced by providing pseudocode (the algorithm is described in prose but pseudocode could help implementers) – though perhaps it’s included in the appendix or could be derived from the description.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hoUG4oBqY7", "reviewer": "Reviewer_3ZDj", "summary": "The authors propose an approximation algorithm (or, more specifically, a resource augmented algorithm) for the graph label selection problem (GLS). GLS is an abstraction of the active learning task of selecting a small set of data points to label out of a pool of unlabeled data. \n\nThe main contribution of the authors is an algorithm with theoretical guarantees on the quality of the solution for *general graphs*, whereas previous works propose approximation algorithms on restricted types of graphs. Moreover, the authors present a proof on the hardness of approximation for GLS in general graphs.\n\n## update after rebuttal\nNot much to add. After reading the other reviews, I maintain my original score and review that this paper is above the acceptance bar.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 3ZDj,\n\nWe thank you for your work reviewing our paper. Here we focus on responding to your question and the points you raised. \n\n1) ``In Figure 4, the heuristic of Guilroy and Bilmes has better performance than your proposed method for $k \\geq 30$. This is not acknowledged or mentioned in the text. Do you have any explanation as to why the heuristic is better in this case?\": This behaviour appears because when k approaches the number of vertices, it is no longer necessarily beneficial to select vertices which have a lot of neighbors. \nThis  can be illustrated well by considering a star graph on say $n$ vertices with budget $k = n - 1$. Counterintuitively, The best solution for this example is to pick all the leaves. This solution achieves score $n - 1$.  \nSince our algorithm follows a greedy approach, it will always pick the star center and then all but one of the leaf vertices. This only achieves score $1$. The heuristic of Guilroy and Bilmes on the other hand, as long as the star center is unlabeled,  will always sample a vertex from a set that contains the star center, but also all but one of the currently unlabeled leaves. Some simple calculations show that this means that the algorithm actually has a reasonably large chance of around $1/\\log n$ to not include the star center and obtain the optimal solution. Since the gap between the two solutions is $n - 1$, this very significant influences the expectation in this degenerate scenario. We will add a discussion of this phenomenon to our article. \n\n2) We will proofread and edit section 6 and 7 to improve the writing in our article.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I checked all the theorems and lemmas to the best of my ability. The theoretical results are the bulk of the contribution.\n\nThere seem to be typos / inconsistencies in Section 6 and Lemma 6.1. This whole section seems somewhat carelessly written compared to the rest of the paper. In particular, halfway through the proof of Lemma 6.1, the authors switch from talking about $\\Delta$-regular graphs to the specific case of $\\Delta=3$.", "experimental_designs_or_analyses": "Yes. I read through the description of the datasets and the metrics. No issues identified.", "relation_to_broader_scientific_literature": "The key contributions of the paper are clearly novel and provide new insights on the hardness of GLS. Since GLS is a simplified version of the active learning task, the paper contributes theoretical results on the hardness of active learning. This is one core task in machine learning / data science.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "Proofread Section 6 and Section 7. The writing is sloppy compared to the rest of the paper.", "questions_for_authors": "In Figure 4, the heuristic of Guilroy and Bilmes has better performance than your proposed method for k >= 30. This is not acknowledged or mentioned in the text. Do you have any explanation as to why the heuristic is better in this case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m9PjCWT5oB", "reviewer": "Reviewer_gCbm", "summary": "The authors study a \"Graph Label Selection\" (GLS) problem of Blum and Chawla and Guillory and Bilmes, which, given a graph G=(V,E) and parameter k, asks the learner to find a subset |L|=k of vertices maximizing the unnormalized min-cut outside of $L$:\n\n$\\Psi(L)=\\min_{C \\subset V \\setminus L} \\frac{e(C,V\\setminus C)}{|C|}$\n\nThis problem is related to active learning on graphs, where finding a subset with large $\\Psi(L)$ leads to a generalization error upper bound for labeling the vertices of the graph assuming labels between points with edges are similar on average.\n\nThe authors prove two main results:\n\n1) Via reduction to independent set, it is NP-Hard to determine whether $\\Psi(L) \\leq 2$ or $\\Psi(L) \\geq 3$\n\n2) There is a poly time algorithm for GLS on any graph with *log(|V|) slack*, i.e. it is possible to find L of size $O(k\\log(|V|))$ such that $\\Psi(L) \\geq \\max_{|L'|=k} \\Psi(L')$\n\nThe authors also give some experimental evidence that executing their algorithm with no slack is as good or better than prior heuristics on many datasets.\n\nThe main new technical contribution of the work is an algorithm for building such $L$ by equating the computation of $\\Psi(L)$ to mincut/maxflow in a closely related auxiliary graph. The authors then show that by greedily finding the vertex which maximizes the auxiliary min-cut, one iteratively halves the gap to the true $\\Psi(L)$ value every k steps, resulting in the $k\\log(|V|)$ slack bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer gCbm,\n\nWe thank you for your work reviewing our paper, we will address your points in the final version. Here we will focus on discussing  the points you raised. \n\n1) Motivation of GLS: Thanks for the suggestion. We will include a discussion of the motivation behind the GLS objective in our article to better motivate the question. \n\n2) Hardness of approximation: Hardness of approximation results that are either stronger or capture more parameter regimes are certainly interesting questions for future research. Given the problem definition, it is plausible that the problem might inherit the hardness of sparsest cut, although we were not able to prove it. An additive approximation may also be possible.\n\n3) Thank you for pointing out some typos in our article.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes. The proofs seem fine.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The key contribution of this paper is a new algorithm for the graph label selection problem (itself related to active learning on graphs) for *arbitrary* underlying graphs with $O(\\log(|V|))$ slack. Previously algorithms (with slack) were only known for trees, with heuristic methods suggested for general graphs. The authors also prove the first NP-hardness result for GLS with no slack, though this aspect is not particularly surprising given typical hardness of such graph-based combinatorial problems.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "It would be helpful if the authors included more discussion how the studied problem is actually related to learning on graphs. From my understanding looking up previous works, finding $L$ with large $\\Psi(L)$ corresponds to a learning strategy of Blum and Chawla getting good generalization error assuming that most pairs of vertices with edges are given the same label. This motivates the GLS (with slack) problem, since it essentially shows that if one can achieve low error using $k\\log(|V|)$ label queries assuming the $k$-GLS value is small.\n\nThe algorithm and proofs presented in the paper are simple and natural, which I view as a strength, especially since previously algorithms were only known for trees. Giving an algorithm for general graphs therefore seems like a big advance on the problem, even if prior methods for trees had constant vs logarithmic slack.\n\nI find the hardness result presented a bit weak. While it is formally true the result implies 3/2-approximating GLS is NP-hard, it is only for a very specific setting of parameters. Could one hope to achieve an algorithm with additive error? What about when the GLS value is large (indeed generally it seems one might hope for this in the downstream learning application?). Can one prove hardness for learning GLS with constant slack for general graphs?", "other_comments_or_suggestions": "Typo in Lemma 6.1 proof, should say Psi(L) \\geq Delta\n\n“he results”", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the paper is interesting and worth publishing at ICML. I agree with the assessment as well.
Decision: Accept (poster)