Robust Offline Active Learning on Graphs
Authors: Yuanchen Wu
Yubai Yuan
Venue: NeurIPS 2024 poster (2024)
Keywords: Offline active learning
graph semi-supervised learning
graph signal recovery
network sampling
Primary area: active_learning

Abstract: We consider the problem of active learning on graphs for node-level tasks, which has crucial applications in many real-world networks where labeling node responses is expensive. In this paper, we propose an offline active learning method that selects nodes to query by explicitly incorporating information from both the network structure and node covariates. Building on graph signal recovery theories and the random spectral sparsification technique, the proposed method adopts a two-stage biased sampling strategy that takes both informativeness and representativeness into consideration for node querying. Informativeness refers to the complexity of graph signals that are learnable from the responses of queried nodes, while representativeness refers to the capacity of queried nodes to control generalization errors given noisy node-level information. We establish a theoretical relationship between generalization error and the number of nodes selected by the proposed method. Our theoretical results demonstrate the trade-off between Informativeness and representativeness in active learning. Extensive numerical experiments show that the proposed method is competitive with existing graph-based active learning methods, especially when node covariates and responses contain noises. Additionally, the proposed method is applicable to both regression and classification tasks on graphs.

Robust Offline Active Learning on Graphs
Yuanchen Wu Department of Statistics The Pennsylvania State University yqu5734dpsu. edu
Yubai Yuan Department of Statistics
The Pennsylvania State University
yvy5509Qpsu. edu
Abstract
We consider the problem of active learning on graphs for node-level tasks, which has crucial applications in many real-world networks where labeling node responses is expensive. In this paper, we propose offline active learning method that lects nodes to query by explicitly incorporating information from both the network structure and node covariates. Building on graph signal recovery theories and the random spectral sparsification technique, the proposed method adopts a two-stage biased sampling strategy that takes both informativeness and representativennss into consideration for node querying. Informativeness refers to the complexity of graph signals that are learnable from the responses of queried nodes, while representativenes. refers to the capacity of queried nodes to control generalization errors given noisy node-level information. We establish theoretical relationship between generalization error and the number of nodes selected by the proposed method. Our theoretical results demonstrate the trade-off between informativeness and representutiveness in active learning. Extensive numerical experiments show that the proposed method competitive with existing graph-based active learning methods, especially when node covariates and responses contain noises. Addition- ally, the proposed method is applicable to both regression and classification tasks graphs.
Introduction
In many graph-based cemi-supervised learning tasks for node-level prediction, labeled nodes are scarce, and the labeling process often incurs high costs in real-world applications. Randomly sampling nodes for labeling can be inefficient, as it overlooks label dependencies across the network. Active learning (2) addresses this issue by selecting informative nodes for labeling by human annotators, thereby improving the performance of downstream prediction algorithms.
Active learning is closely related to the optimal experimental design principle 33 in statistics. Traditional optimal experimental design methods select samples to maximize specific statistical criterion (26 19 However, these methods often are not designed incorporate network structure,
therefore inefficient for graph-based learning tasks. On the other hand, selecting informative nodes on network studied extensively in the graph signal sampling literature [T] 18
10 28 These
strategies are typically based on the principle of network homophily, which assumes that connected nodes tend to have similar labels. However, node's label often also depends on its individual covariates. Therefore, signal-sapliin strategies that focus solely on network information may miss critical insights provided by covariates.
Recently, inspired by the great success of graph neural networks (GNNs) 16 in graph-based
machine learning tasks, many GNN-based active learning strategies have been proposed. Existing methods select nodes to query by maximizing information gain under different criteria, including information entropy the number of influenced nodes [39], prediction uncertainty 22). expected error reduction g and expected model change (30). Most of these information gain measurements
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

are defined in the spatial domain, leveraging the message-passaaee framework of GNNs to incorporate both network structure and covariate information. However, their effectiveness in maximizing learning outcomes is not guaranteed and can be difficult to evaluate. This challenge arises from the difficulty of quantifying node labeling complexity the spatial domain due to intractable network topologies. While complexity measures exist for binary classification over networks [9], their extension to more complex graph signals incorporating node covariates remains unclear. This lack of well-defined complexity measures complicates performance analysis and creates misalignment between graph-based information measurements and the gradient used to search the labeling function space, potentially leading to sub-optimal node selection.
Moreover, from a practical perspective, most of the previously discussed methods operate in an online setting, requiring prompt labeling feedback from an external annotator. However, this online framework not always feasible when computational resources are limited [24] or when recurrent interaction between the algorithm and the annotator is impractical, such as in remote sensing online
marketing tasks [32 35 Additionally, both network data and annotator- prrovvddd- labels may contain
measurement errors. These methods often fail to account for noise in the training data [23] which
can significantly degrade the prediction performance models on unlabeled nodes 7 21.
To address these challenges, we propose an offline active learning on graphs framework for node- level prediction tasks. Inspired by the theory of graph signal recovery first introduce graph function space that integrates both node covariate information and network topology. The complexity of the node labeling function within this space is well-defined in the graph spectral domain. Accordingly, we propose a query information gain measurement aligned with the spectral- based complexity, allowing our strategy to achieve theoretically optimal sample complexity.
18 and GNNs, we
Building on this, we develop greedy node query strategy. The labels of the queried nodes help iden- tify orthogonal components of the target labeling function, each with varying levels of smoothness across the network. To address data noise, the query procedure considers both informativeness--tee contribution of queried nodes in recovering non-smooth components of signal-and representative- ness the robustness of predictions against noise in the training data. Compared to existing methods, the proposed approach provides provably effective strategy under general network structures and achieves higher query efficiency by incorporating both network and node covariate information.
The proposed method identifies the labeling function via bottom-up strategy- first identifying the smoother components of the labeling function and then continuing to more oscillated components. Therefore, the proposed method is naturally robust tigh-frequency noise in node covariates. We pro- vide a theoretical guarantee for the effectiveness of the proposed method in semi-supervise learning tasks. The generalization error bound is guaranteed even when the node labels are noisy. Our theoret- ical results also highlight an interesting trade-off between informativeness and representativeness in graph-based active learning.
2 Preliminaries
We consider an undirected, weighted, connected graph G = (V, A), where V == 21, . is the set of n nodes, and A E Raxx is the symmetric adjacency matrix, with element aij 2 0 denoting the edge weight between nodes i and j. The degree matrix is defined as D diag (dy dg. d. where dj = Eisign aij denotes the degree of node i. Additionally, we observe the node response vector Y Raxi and the node covariate matrix X (X1,... Xp) RRxp, where the 7th row, X,, is the p-dimensional covariate vector for node i. The linear space of all linear combinations of {X),- } denoted Span .pp. The normalized graph Laplacian matrix is defined as L C D 1/2 AIDAD 1/2, where I the n n identity matrix. The matrix L is symmetric and positive semi-definin definite, with n real eigenvalues satisfying 0- = X < x < ... < Xn < 2, and a corresponding set of eigenvectors denoted by U- = (U, U2.... Un). We use = O(a) to indicate |b| < M |a| for some M > O. For set of nodes S C V, |S| indicates its cardinality, and S V denotes the complement of S.
2.1 Graph signal representation
Consider graph signal f E RR", where f(i) denotes the signal value at node i. For a set of nodes S, we define the subspace Ls (f E ga |f(S) 0}, where f(S) e gg| represents the values of f

---

on nodes in S. In this paper, we consider both regression tasks, where f(i) is continuous response, and classification tasks, where f(i) is a multi-class label.
Since U serves as a set of bases for IR,,, we can decompose f in the graph spectral domain as f = Ej=1 Orr(A) (A,))U where (r())) = (f, Ug) is defined as the graph Fourier transform (GFT) coefficient corresponding to frequency Aj. From graph signal processing perspective, smaller eigenvalue indicates lower variation in the associated eigenvector U2. reflecting smoother transitions between neighboring nodes. Therefore, the smoothness of over the network be characterized by the magnitude of (x₂) ) at each frequency Aj. More formally, we measure the signal complexity of f using the bandwidth frequency wr sup(Ay Jar (Ay) 0}. Accordingly, we define the subspace of graph signals with a bandwidth frequency less than or equal to w as L == {f E R= wp S w). It
follows directly that Vai W2, Lu Lez
2.2 Active semi-supervised learning on graphs
The key idea in graph-based semi-supervised learning is to reconstruct the graph signal within function space (X, A) that depends on both the network structure and node-wise covariates, where the frequency parameter w controls the size of the space to mitigate overftting. Assume that Y; is the observed noisy realization of the true signal f(i) node i, active learning operates in scenario where we have limited access to Y; on only a subset of nodes S, with |S] << n. The objective is to estimate f within H. (X, A) using (Yi)ee by considering the empirical estimator of f as
fs
arg Σ gY).))))). (X.A) SES
where I(-) is a task-specific loss function. We denote f as the minimizer of ( when responses on all nodes available, i.e., f fv. The goal of active semi-supervised learning is design an appropriate function space H [X, A) and select an informative subset of nodes S for querying responses, under the query budget S S B, such that the estimation error bounded follows:
ffs 1 S pl - f
For a fixed B, we wish to minimize the parameter p > 0, which converges to 0 as the query budget B approaches n.
3 Biased Sequential Sampling
In this section, we introduce a function space for recovering the graph signal. Leveraging this function space, we propose an offline node query strategy that integrates criteria of both node informativeness and representativennss to infer the labels of unannotated nodes in the network.
3.1 Graph signal function space
In semi-supervised learning tasks on networks, both the network topology and node-wise covariates are crucial for inferring the graph signal. To effectively incorporate this information, we propose function class for reconstructing the graph signal that lies at the intersection of the graph spectral domain and the space of node covariates. Motivated by the graph Fourier transform, we define the following function class:
H X A) =Proj Span(X) X): = Span (Proj XI, Proj Xp).
where Proje. X, = Σ UX,,U
S:A,Sw Se
Here, the choice of w balances the information from node covariates and network structure. When 2, (X, A) spans the full column space of covariates, i.e., Span X,, XpJ. allowing for a full utilization of the original covariate space to estimate the graph signal, but without incorporating any network information. On the other hand, when is close to zero-cor consider, for example, the extreme case where [U; X < w}| = and >> t-thhe Proj X; reduces to Span(U,, U2}. resulting in loss of critical information provided by the original X.
By carefully choosing w, however, this function space can offer two key advantages for estimating the graph signal. From signal recovery perspective, H (X,A) imposes graph-based regularization
3

---

over node covariates, enhancing generalizability when the dimension of covariates exceeds the query budget or even the network size cren-coditions commonly encountered in real applications. Additionally, covariate smoothing filters out signals in the covariates that are irrelevant to network- based prediction, thereby increasing robustness against potential noise in the covariates. From an active learning perspective, using (X,, A) enables bottom-up query strategy that begins with small w to capture the smoothest global trends in the graph signal. As the labeling budget increases, is adaptively increased to capture more complex graph signals within the larger space H. (X, A).
The graph signal can be approximated by its projection onto the space (X, A). Specif- ically, let U2 {U1, U2, Ua) E Raxd stack the d leading eigenvectors of L, where = arg max maxis (Ay w) I O. The graph signal estimation is then given by U where 3 E R is trainable weight vector. However, the parameters 3 may become unidentifiable when the covariate dimension exceeds To address this issue, we reparameterize the linear regression as follows:
- =
(2)
where B VV? 3 and X
U,V, Here, V1 E Rdxr, V22 E RRxT and Σ R denote the left and right singular vectors and the diagonal matrix of the singular values, respectively.
In the reparameterized form 2 the columns of X serve as bases for H A), thus dim(H,. A)) rank(X) = < mi, The transformed predictors X capture the com- ponents of the node covariates constrained within the low-frequency graph spectrum. graph signal f H., A) can parameterized as linear combination of the columns of X, with the corresponding weights identified via
3 arg min (r(ii- 3)²
B iES
where Xs E R Sixr is the submatrix of X containing rows indexed by the query set S, and (f(i) represents the true labels for nodes in S. To achieve the identification of f, it is necessary that [8] 2 r: otherwise, there will be more parameters than equations in (3). More importantly. since rank(Xs) S rank(X) r, f only identifiable if Xg has full column rank. Notice that increases monotonically with w. If S is not carefully selected, the graph signal can only be identified H (X, A) for some w/ < w. which a subspace H., H,,(X, (X,A). A).
3.2 Informative node selection
We first define the identification of (X, A) by the node query set S as follows:
Definition 1 A subset of nodes S C V can identify the graph signal space H.( A) up to frequency
for any two functions f,, f2 H HX, (X, such that (i) = fz(1) for all S, it follows that f (i) = f2()) for all j E V.
Intuitively, the informativeness of set S can be quantified by the frequency w corresponding to the space (X, A) that can be identified. To select informative nodes, we need to bridge the query set S in the spatial domain with w in the spectral domain. To achieve this, we consider the counterpart of the function space H A) in the spatial domain. Specifically, we introduce the projection space
with respect to subset of nodes S follows: H HX, A) = (xan( ,.. ..., x())). where
(1) i
()) = 0
i
Here, (i) denotes the p-th covariate for node in X. Theorem 3.1 establishes connection between the two graph signal spaces (X( A) and Hs(X, A), providing a metric for evaluating the informativeness of querying subset of nodes the graph.
Theorem 3.1 Any graph signal f E (X, A) can be idenisfied using labels on a subset of nodes S and only if:
w < w(S)
inf Wg. cEHs((X.A)
(4)
where S denotes the complement S in V.

---

We denote the quantity w(S) in (4) as the bandwidth frequency with respect to the node set S. This quantity can be explicitly calculated and measures the size of the space H. (X. A) that can be recovered from the subset of nodes S. The goal of the active learning strategy is to select S within given budget to maximize the bandwidth frequency w(S), thus enabling the identification of graph signals with the highest possible complexity.
To calculate the bandwidth frequency wS)), consider any graph signal g and its components with non-zero frequency Ag := {>i Og (A:) > 0}. We use the fact that
1/k
lim k+000
Σ E.
= max (A)), A5EAg
where Σ Ej 9==1 = and 0 S cj S 1. Combined with the Rayleigh quotient representation of eigenvalues, the bandwidth frequency Wg can be calculated as
g L 1/k g g'g
W/g
lim (k()), where (g((:) k-000
As result, we can approximate the bandwidth wg using Wg (k) for a large Maximizing wS)) over S then transforms into the following optimization problem:
S arg max (S), where ((S) geHs 8: S|SB
inf
(k),
where B represents the budget for querying labels. Due to the combinatorial complexity of directly solving optimization problem (5) by simultaneously selecting S, we propose a greedy selection strategy as continuous relaxation of (5).
The selection procedure starts with S = and sequentially adds node S that maximizes
the increase in w(S) until the budget is reached. We introduce an n--dieensional vector = (4,, l., 1n)" with 0 < 4 1, and define the corresponding diagonal matrix D(t) with diagonal entries given by t. This allows us to encode the set of query nodes using = 1s. where Ls(i) = i S and (i) O if i 8 We then consider the space spanned by the columns of Dtt) as Span X)). and the following relation holds:
Hs. [X, A) = Span ((1g=)
Intuitively, Span D()) acts as a differentiable relaxation of the subspace H. Hs(X. (X, A), enabling perturbation analysis of the bandwidth frequency when new node is added to S. The projection operator associated with Span ( [t) can be explicitly expressed as
P(t) = D(t) (x D( xT
To quantify the increase in ((S) when adding a new node to S, we consider the following regularized optimization problem:
o L of (-P(())) TT t
(t min
(6)
The penalty term on the right-hand side of (6) encourages the graph signal á to remain in Hg= (X, A). As the parameter a approaches infinity and t = 1se, the minimization Xa (1sz) in (6) converges to (S)) in (5) The information gain from labeling a node i S can then be quantified by the gradient of the bandwidth frequency as f; decreases from 1 to O:
A, = (t)
2a x o PP(t)
Øt, t=1ge
Ot:
1=
where è is the minimizer of (6) at 1ss, which corresponds to the eigenvector associated with the smallest non-zero eigenvalue of the matrix P(1 C*p(ss=) We then select the node
i arg max jas: A, and update the query set as S S SU {1). The explicit representation of A, in
can be found in Appendix B.5.
5

---

3.3 Representative node selection
In real-world applications, we often have access only to a perturbed version of the true graph signals, denoted as Y = f + ç, where & represents node labeling noise that is independent of the network data. When replacing the true label f(i) with (i) in 33). this noise term introduces both inite-sample bias and variance in the estimation of the graph signal f. As result, we aim to query nodes that are sufficiently representative of the entire covariate space to bound the generalization error. To achieve this, we introduce principled randomness into the deterministic selection procedure described in Section 3.2 to ensure that S includes nodes that are both informative and representative. The modified graph signal estimation procedure is given by:
arg min Σ 84 (Y - (Xs). 3)²
(8)
3
YES
where s; the weight associated with the probability of selecting node into S.
Specifically, the generalization error of the estimator in 8 is determined by the smallest eigenvalue
of XJXs, denoted as Amin Xs)s Given that Amin X = 1, our goal is to increase the
representativeness of S such that Amin (X(Xs) is lower-bounded by:
Amin
X
2 (1 - 015) A1))
x x
(9)
However, the informative selection method in Section 3.2 does not guarantee (9. we propose a sequential biased sampling approach that balances informative node selection with generalization error control.
To address this,
The key idea to achieve lower bound for Amin (X is to use spectral sparsification techniques for positive semi-definite matrices [[3]. Let D; E R xr denote the i-th row of the constrained basis X. By definition of X, it follows that I,xr = Σ o/ v;. Inspired by the randomized sampling approach in [17,, propose biased sampling strategy construct S with [S] n and weights {s; > 0, E S} such that Eies 8. U2 x I. In other words, the weighted covariance matrix of the query set S satisfies Amin s
1, where Ws is diagonal matrix with s; on its diagonal.
We outline the detailed sampling procedure as follows. After the (t-1)tt selection, let the set of query nodes be S with corresponding node-wise weights W1-1 {s, 0 St-1}. The covariance matrix of S;- is given by C.-1 E R=**, defined as Ct-1 = X3,_, Xs.., = Σ Ejes,.. 8T0} Uy. To analyze the behavior of eigenvalues as the query set is updated, we follow 17 and introduce the potential funetion:
Φ = -
(10)
where ut-1 and 4-1 are constants such that 4-1 Amin (C--1) S Amax (Cix)( < ur-1, and Tr(-) denotes the trace of a matrix. The potential function 4,-1 quantifies the coherence among all eigenvalues of Ct-1- To construct the candidate set Bm, we sample node and update Ct, ug and 4 such that all eigenvalues of C remain within the interval (4,, uz). To achieve this, we first calculate the node-wiss probabilities 1/ as:
P = [u.(uc11/ - CC-1) + 1o(C--1-4-11 u2 //
(11)
where Σn= Pi = 1. We then sample m nodes into B,, according to {pr} For each node E Bm the corresponding weight given by 8; ,. 0 < < 1. After obtaining the candidate set Bm, we apply the informative node selection criterion A, introduced in Section 3.2, i.e. selecting the node i = arg ma R,,. A,, and update the query set and weights as follows:
if i E S St = = U (i), W: = W;-1 U (si).
if i E S s; = p
We then update the lower and upper eigenvalue bounds as follows:
ui 14-1 + T 1 e) 4 4-1 + 8 111 (ee)
(12)

---

The update rule ensures that 4, - increases at slower rate than ue, leading to the convergence of the gap between the largest and smallest eigenvalues of W sXs. thereby controlling the condition number. Accordingly, the covariance matrix is updated with the selected node i as:
C. Cc-1 + p.
of
(13)
With the covariance matrix update rule in (13), the average increment is E(C,) C--1 Ei=1 P.s,0, 0, = -i= Intuitively, the selected node allows all eigenvalues of Ct-1 to increase at the same rate on average. This ensures that Amia
A (X5Xs) continues to approach Amin (X' X) = 1 during the selection process, thus driving the smallest eigenvalue away from zero. Additionally, the selected node remains locally informative within the candidate set Bm. Compared with the entire set of nodes, selecting from subset serves as regularization informativeness maximization, achieving balance between informativeness and representativenes: for node queries.
3.4 Node query algorithm and graph signal recovery
We summarize the biased sampling selection strategy in Algorithm 1. At high level, each step in the biased sampling query strategy consists of two stages. First, we use randomized spectral sparsification to sample m < n nodes and collect them into a candidate set Bm Intuitively, the covariance matrix on the updated S maintains lower-bounded eigenvalues if node from B,, is added to S. In the second stage, we select one node from Bm based on the informativeness criterion in Section 3.2 to achieve a significant frequency increase 7
For initialization, the dimension of the network spectrum d, the size of the candidate set m, and the constant < 1 for spectral sparsification need be specified. Based on the discussion the end of Section 3.1, the dimension of the function space H.. (X, A) is at most B, where B is the budget for label queries. Therefore,
can set d (p, B). The parameters and jointly control the Amaas (X Xs)
condition number
Amai (X Xx)
Algorithm 1 Biased Sampling Query Algorithm
Require: t 0, Co 0, the set of query nodes Sp 0, the set of node weights Wo 0, spectral dimension d, size of candidate set m, constant () < < 1 1/m, query budget B.
Initialization: Compute SVD decomposition U = VIEV?" and set X = U,V, r= rank (X).
Ug = 2r/e, lo = -2r/e, K = 2r(1 - m)))) /mm²)).
while B > () do
Step 1: Calculate &2 as in (10) and the node-wise probabilities {pr)__ using
Step 2: Sample m nodes with replacement according probabilities {p.) )
form the
candidate set Bm-
Step 3: Select node as arg max B., A; and calculate its weight w; P.P.
If & St, then update S,+1 S, (i) and W++1 = W. U {s:) with 8; Wi
Else if E S,, then update =
Step 4:
Update Ct. Ur, le. and as:
C+1 =1==C++ w vi,
ue+1
Ut + p. - -me)"
441 = 4 +
p. + me)²
B = B t=t+1.
end while
Query: Label all nodes in S through an external annotator.
Output: Set of queried nodes S, annotated responses (Y; | E S}. smoothed covariates Xs. and weights of queried nodes W.
Based on the output from Algorithm I, we solve the weighted least squares problem in (8)
3 = arg min
Σ sy (Y
())
(14)
B
iES
and recover the graph signal on the entire network as p x The proposed method illustrated for the regression task, with an extension to the classification task discussed in Appendix B.2.
7

---

Theoretical Analysis
In this section, we present a theoretical analysis the proposed node query strategy. The results are divided into two parts: the first focuses the local information gain of the selection process, while the second examines the global performance of graph signal recovery. Given a set of query nodes S, the information gain from querying the label of new node i is measured as the increase in bandwidth frequency, defined as A; == w(S U (i)) w(S). We provide a step-by-step analysis of the proposed method by comparing the increase in bandwidth frequency with that of random selection.
Theorem 4.1 Define dmin = min(d.), where de denotes the degree of node i. Let S represent the set
of queried nodes prior to the 8hh selection. Denote the adjacency matrix of the subgraph excluding as (n=115))((=18)1 Let A and A denote the increase in bandwidth frequency resulting from the 8th label query on a node selected by random sampling and the proposed sampling method, respectively. Let j denote the node with the largest magnitude in the eigenvector corresponding to the smallest non-zero eigenvalue of Lg=. Then we have:
E(A.) = -2(-) (1), and E(D - E(A > 2 72
- (2),
TOTTi
min
where f - 2(g) if S S 02 for constants C1, 02 when n is sufficient large. Inequality (2) holds given m satisfying
n m dmii ym n m dmmn ydmss ddmin = O().
dmin
The expectation E(-) is taken over the randomness of node selection. Both no, T) are network-related quantities, where IJo A #[(i:
d dat
de S 1}| and th A max; deas
Theorem 4.1 provides key insights into the information gain achieved through different node label querying strategies. While random selection yields a constant average information gain, the proposed biased sampling method guarantees higher information gain under mild assumptions.
In Theorem 4.2, we provide the generalization error bound for the proposed sampling method under the weighted OLS estimator. To formally state Theorem 4.2, we first introduce the following two assumptions:
Assumption For the underlying graph signal f, there exists bandwidth frequency we such that f E Hop [X, A).
Assumption 2 The observed node-wise response Y, can be decomposed as f(i) &i, where (5 are independent random variables with E(E,) = 0 and Var(E, S o².
Theorem 4.2 Under Assumptions I and 2, for the graph signal estimation f obtained by training
14 on B labeled nodes selected by Algorithm 1, with probability greater than 1 2m where t > 2m, we have
Ey ff - fll2 s O
rat
+ 2
rat/33
3/2 33/2 + (BBBB
(aa))) x (no²+ 2+
+
Σ
af) +
Σ
B
B
(>d,tEmpp(())
(15)
where a; := (f, U.), supp(f) ==
(i 15 S aas > 0} and mank(U? X). Ey(-) denotes
the expected value with respect to the randomness in observed responses.
Theorem 4.2 reveals the trade-off between informativeness and representativeness in graph-bases active learning, which is controlled by the spectral dimension d. Since ra is monotonic function of d. a larger d reduces representativeness among queried nodes, thereby increasing variance controlling the condition number (i.e., the first three terms). On the other hand, larger d reduces approximation bias to the true graph signal (i.e., the fifth and last terms) by including more informative nodes for capturing less smoothed signals.
8

---

Proposed RIM SPA
2.5
Prediction MSE
1.5
Prediction MSE
1.5
Prediction MSE
D-oplimal
2.0
1.5
1.0-
Propoeed
Proposed
1.0
RIM
D-optimal
0.5
D-optimal
GPT
0.7
0.8
Noise Level
Nolse Level
Noise Level
(a) Small World
(b) Community
Scale-free
Figure 1: Prediction performance unlabeled nodes at different levels of labeling noise (a*). All three simulated networks have 100 nodes, with the number of labeled nodes fixed at 25.
Numerical Studies
In this section, we conduct extensive numerical studies evaluate the proposed active learning strategy for node-level prediction tasks both synthetic and real-world networks. For the synthetic networks, we focus on regression tasks with continuous responses, while for the real-world networks, we consider classification tasks with discrete node labels.
5.1 Synthetic networks
We consider three different network topologies generated by widely studied statistical network models: the Watts Stroggtz model [3 for small-world properties, the Stochastic block model [I3] for community structure, and the Barabási Albert model [3] for scale-free properties.
Node responses are generated as Y + 5. where f is the true graph signal and NO0 rn is Gaussian noise. The true signal constructed as Ua3, where f is linear coefficient and U, denotes the leading d eigenvectors of the normalized graph Laplacian of the synthetic network. Since our theoretical analysis assumes that the observed node covariates X contain noise, we generate as perturbed version of Ua by adding non-leading cigenvectors of the normalized graph Laplacian. The detailed simulation settings can be found in Appendix C.I.
We compare our algorithm with several offline active learning methods: 1. D-optimal 26 selects
subset of nodes S maximize determinant of observed covariate information matrix X RIM (38] selects nodes to maximize the number of influenced nodes. 3. GPT (22) and SPA [
split the graph into disjoint partitions and select informative nodes from each partition.
After the node query step, we fit the weighted linear regression from (4) on the labeled nodes, using the smoothed covariates X, to estimate the linear coefficient and predict the response Y for the unlabeled nodes. Figure we plot the prediction MSE of the proposed method against baselines on unlabeled nodes for varioss levels of labeling noise o² E (0.5, 0.6, 0.7, 0.8, 0.9, 1). The results show that the proposed method significantly outperforms all baselines across all simulation settings and exhibits strong robustness noise. The inferior performance of the baselines can be attributed to several factors. D-optimal and RIM fail to account for noise the node covariates. Meanwhile, partition-based methods like GPT and SPA are highly sensitive to hyperparameters, such as the optimal number partitions, which limits their generalization to networks lacking a clear community structure.
5.2 Real-world networks
We evaluate the proposed method for node classification tasks on real-world datasets, which include five networks with varying homophily levels (high low: Cora, PubMed, Citeseer, Chameleon and Texas) and two large-scale networks (Ogbn-Arxiv and Co-Physics). In addition to the offline methods described Section 5.1, we also compare our approach with two GNN-based online active learning methods AGE 4 and IGP (39. In each GNN iteration, AGE selects nodes to maximize linear combination heuristic metrics, while IGP selects nodes that maximize information gain propagation.

---

Table 1: Test accuracy (Micro-F1% on five real-world networks with varying levels of homophily. The edge homophily ratio h of a network is defined as the fraction of edges that connect nodes with the same class label. A higher h indicates network with stronger homophily.
Cora (8 0.5
Puhmed (á = 0.800
Citeseer (4 = 0.24)
Chamelcon ch -0.20
Texas (1 a.1
Atobeled andes
70
140
15
30
50
50
120
50
75
100
15
30
Randee
(822 2
14.5 1n
00
712
740 L6
78.4 05 51. = 04
16.3 + 100 =00
21
22
218=21
630
099333
=
11 150-+000
0.5500
175=12
053
677.005
114400
300
49:
236
07
085-3
77.4
k16-1
865
770
799
81S 1. 679
115-11
101
158-22
216-20
1
Viaa
0:03
11 961.200
15
M4 675
422
344
764-3:0
14
1744111
6177
785
667:1
7211100
758
137
314
708
761-1-16
1: M0 93222.00
15 265:20
755
044:222
102.132
255:29
220
122
14
7.7 1.7 11
789
066
02
12
15
35.
357
30
=5
7M5
27
Table Average query time (in sec- onds) per node.
Table 2: Test accuracy (Macro-F1 % and Micro-F1 16) on two real-world large-
scale networks: Ogbn-Arxiv (n 169, 343) and Co-Physics (n 34, 493).
Ogba Andv (Macro FI)
Oghn Aniv (Miere F1)
Co Physcss (Macro F1)
Datoeet
Size
Time
flabbled modes
100
320
640
1280
160
320
640
1280
10
20
40
Texa
183
0.19 0.00
Randon
219 1.4 17.511
15.0 14
6000 07
03500
183 1:38
669
1011
7.
Daamloo
2,77
11:14 0.1.
AGE
250
433
549
600
035
630
32
Con
0.10
OPT
29
08
164
400
05
667
96
05
258
838403
Clouer
13327
0.36 oi0
Progrool
13 M3=
14 1. 4.
53
98 1.D 613
14
648
1.
435
#6
DilPyyikx 14,43
OignnArstt: 100.343 2:331:0.3
Unlike regression, node classification with GNNs is a widely studied area of research. Previous works [22 30 (38 [3] have demonstrated that the prediction performance of various active learning strategics on unlabeled nodes remains relatively consistent across different types of GNNs. Therefore, we employ Simplified Graph Convolution (SGC) 34 the GNN classifier due to its straightforward theoretical intuition. Since SGC is essentially multi-class logistic regression on low-pass low-pass-filtered covariates, it can be approximately viewed special case of the regression model defined in (14). Thus, we conjecture that our theoretical analysis can also be extended to classification tasks and leave its formal verification for future work.
The results Figure demonstrate that the proposed algorithm highly competitive with baselines across real-world networks with varying degrees of homophily. Our method achieves the best performance on Cora (highest homophily) and Texas (lowest homophily, i.c., highest heterophily) and is particularly effective when the labeling budget is most limited. To handle heterophily in networks like Chameleon and Texas, we expand the graph signal subspace U2 in Algorithm [ to U. fU1,... Ua. Un-d+1. J. combining eigenvectors corresponding the d smallest and d largest eigenvalues. Admittedly, relying on a priori knowledge of label construction may be unrealistic, so developing adaptive methods for designing the signal subspace to effectively handle both homophily and heterophily remains a promising direction for future research.
Table summarizes the performance on two large-scale networks. The greatest improvement is observed in the Macro-Fl score on Ogbn-Arxiv, with an increase of up to 4.8% at 320 labeled nodes. Moreover, Table 3 demonstrates that our algorithm scales efficiently to large networks, with the time cost of querying a single node being approximately 2 seconds when n 169, 343.
Conclusion
We propose graph-based offline active learning framework for node-level tasks. Our node query strategy effectively leverages both the network structure and node covariate information, demonstrat- ing robustness diverse network topologies and node-level noise. We provide theoretical guarantees for controlling generalization error, uncovering a novel trade-off between informativeness and repre- sentativeness active learning on graphs. Empirical results demonstrate that our method performs strongly on both synthetic and real-world networks, achieving competitiveness with state-of-ther thetth-art art methods on benchmark datasets. Future work could explore extensions an online active learning setting that iteratively incorporates node response information to further enhance query efficiency. Additionally, scalability on large graphs could be improved by utilizing the Lanezos method [1] or Chebyshev polynomial approximation [16] during node selection.
10

---

References
[1] D. Kressner A. Susnjara, N. Perraudin and P. Vandergheynst. Accelcrated filtering on graphs using lanczos method. arXiv preprint Stt.:15090045377 2015.
[2] Bassam Bamieh. A tutorial on matrix perturbation theory (using compact matrix notation). arXiv preprint arXiv:2002.05001, 2020.
[3] A.-L. Barabasi and R. Albert. Emergence of scaling random networks. Science, 1999.
[4] H. Cai, V. W. Zheng, and K. Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint
2017.
[5] X. Chen and E. Price. Active regression via linear-sample sparsification. In Conference Learning Theory, pages 663-695. PMLR, 2019.
[6] Y. Qi D. Blakely, J. Lanchantin. Time and space complexity graph convolutional networks. Accessed on: Dec, 2021.
[7] J. Du and C. X. Ling. Active learning with human-like noisy oracle. In Proceedings of the 2010 IEEE International Conference on Data Mining(ICDM), 2010.
[8] Y. Zhang FF. Regol, S. Pal and M. Coates. Active learning on attributed graphs via graph cognizant logistic regression and preemptive query generation. In Proceedings of the 37th International Conference on Machine Learning (ICMI., 2020.
[9] X. Zhu G. Dasarathy, R. Nowak. S2: An efficient graph based active learning algorithm with application to nonparametric classification. In Proceedings The 28th Conference Learning Theory (COLT), 2015.
[10] R. Gribonval P. Vandergheynst G. Puy, N. Tremblay. Random sampling of bandlimited signals on graphs. Applied and Computational Harmonic Analysis, 2016.
[11] A. Gadde, A. Anis, and A. Ortega. Active semi-supervised learning using sampling theory for graph signals. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), 2014.
[12] Akshay Gadde, Aamir Anis, and Antonio Ortega. Active cemi-supereised learning using sampling theory for graph signals. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 492-501, 2014.
[13] M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 2002.
[14] G. Golub and C. Loan. Matrix computations. HU press, 2013.
[15] N. Srivastava J. Batson, D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 2013.
[16] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. Proceedings of the 5th International Conference on Learning Representations (ICLR), 2017.
[17] Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. SIAM Journal on Computing, 4766):315--2366 2018.
[18] P. Di Lorenzo, S. Barbarossa, and P. Banelli. Cooperative and Graph Signal Processing. Academic Press, 2018.
[19] DJ. Hsu M. Derezinski. MKK. Warmuth. Leveraged volume sampling for linear regression. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[20] J. Neter M. Kutner, C. Nachtsheim and W. Li. Applied Linear Statistical Models. McGraw- Hill//rwin, 2004.
[21] K. Santosh M.-R. Bouguelia, S. Nowaezyk and Verikas. Agreeing to disagree: active learning with noisy labels without crowdsourcing. 2018.

---

[22] J. Ma, Z. Ma, J. Chai, and Q. Mei. Partition- based active learning for graph neural networks. Transactions on Machine Learning Research, 2023.
[23] T. Maehara NT. Hoang and 'T. Murata. Revisiting graph neural networks: Graph filtering perspective. In Proceedings of the 25th International Conference on Pattern Recognition (ICPR), 2021.
[24] X. Chang P.-Y. Huang Z. Li X. Chen P. Ren, Y. Xiao and X. Wang. A survey of deep active learning. ACM Computing Surveys, 2020.
[25] E.L. Paluck, H. Shepherd, and P.M. Aronow. Changing climates of conflict: a social network experiment in 56 schools. Proceedings of the National Academy of Sciences, page 566-571, 2016.
[26] Pukelsheim. Optimal Design of Experiments (Classics in Applied Mathematics) (Classics in Applied Mathematics, 50). Society for Industrial and Applied Mathematics, 2018.
[27] L.. Yin R. Fajri, Y. Pei and Mykola Pechenizkiy. A structural-clustering based active learning for graph neural networks. In Symposium on Intelligent Data Analysis (IIAA), 2024.
[28] J. M. F. Moura S. Chen, A. Sandryhaila and J. Kovačević. Signal recovery on graphs: Variation minimization. IEEE Transactions on Signal Processing. 2016.
[29] B. Settles. Active learning literature survey. Technical report, University of Wisconsin Madison, 2010.
[30] Z. Song, Y. Zhang, and I. King. No change, no gain: Empowering graph neural networks with expected model change maximization for active learning. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[31] M. Vose. Linear algorithm for generating random numbers with a given distribution. IEEE Transactions on soflware engineering, 1991.
[32] W. Wang and WN. Street. Modeling and maximizing influence diffusion in social networks for viral marketing. Applied network science, 2018.
[33] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of "small-wood world' networks. Nature, 1998.
[34] F. Wu, A. H. S. Jr., T. Zhang, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
[35] A. Liu Y. Xu, X. Chen and C. Hu. A latency and coverage optimized data collection scheme for smart cities. In New Advances in Identification, Information and Knowledge in the Internet of Things, 2017.
[36] A. Singh Z. Allen-Zhu, Y. and Wang. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 2020.
[37] F. Chen G. Long C. Zhang P. Yu Z. Wu, S. Pan. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[38] W. Zhang, Y. Wang, Z. You, M. Cao, P. Huang, J. Shan, Z. Yang, and B. Cui. Rim: Reliable influence-based active learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[39] W. Zhang, Y. Wang, Z. You, M. Cao, P. Huang. J. Shan, Z. Yang, and B. Cui. Information gain propagation: a new way to graph active learning with soft labels. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
12

---

A Proofs
A.1 Proof of Theorem 3.1
Proof: Consider the threshold frequency defined as
< (S)
inf & gEPminge span X)
Wg:
(16)
and notice that 16 is true if and only if
Projr. span X) n Projr.. span X) = {0)-
(17)
+ For Vé E Span (X) n Projt.g span(X) (X) and vf E Projr.. span(X), we have g Φ ff e
Proi,, span(X) by closure under addition and ((S) g(S). Since Projr., span (X) can be identified
by S, one must have = g. which implies ø = 0. Hence, [7 is true.
+ Given 17 is true, assume that Projr., span X) cannot be identified by S. Then, by definition, there exists I1, f2 E Proju., (pann such that f (S) = f2(S) and fi & fz. Since (fi f2)(() = 0, (X). By clousure under addition, fi - f2 E Proju. span(pppnn)) However, f f2 E Projr, span(X) n Projige span(X) a contradiction with 17 Therefore, Projr., span(())
f f2 E
can be identified by S.
A.2 Proof of Theorem 4.1
Proof: Let U = U2..U...... "U,} be the cigenvectors of L = - D D-122 1/2 and A 2., diag 22, .An). Without loss of generality, we analyze the case when k 1 and the case of no repeated eigenvalues. The analysis for the case of repeated eigenvalues can be similar performed
with matrix perturbation analysis on degenerate case 2
After selecting node i, we have the reduced Laplacian matrix L
C1i
=' C(-), where ((-i)
=
Li
Cii
Lin
Lns
Define A as the diagonal matrix containing eigenvalues of L Using the first order perturbation analysis [2], we have A se A + diag(U"(((-)))) ()- Let L.₁ and C. be the 7th column and row of C. respectively. Since
Uij
c(-OU,
-c(-00
L., +
LnU
-/
= C.,UU +
(Ca - Us)
Lns Uij
13

---

we have
U U,y(C,UU)) + (C;: -
U,)(A + (C:: (Cn -
=(1 -22) since the diagonal entry of
Therefore,
(1- U
A+
22n U? km
Assume U1 corresponding to the smallest non-zero eigenvalue of A", then the increase of bandwidth frequency for node U1
For random selection, where node is queried with uniform probability,
E(Ax)=
Σ
U
1l
α
n 1=1
72
For the proposed selection method, define R = diag (1, r2, ,rn), where r, d. then
dmnn
- D 1/2 D-1/2AD A2 1/2 -1/2
I+ED te'
(e'dmin) AAR -
Ao
= Ao + é e'A1
Next we perform matrix perturbation analysis, define
Un = 1, Ao = Ag, A = An + An, U = Up + e'Ui
where U approximate eigenvalues and eigenvectors of A Denote (U1), the htth column of U₁ and assume d, * dj. we have
(U1) = Σ (Un). A (Uo)s (Uo), = EE Egt (Ao) (Av);
Aik
(E1) (d, dx) vd.vdx
igth
(U)x = (Uo) + E'(U)
To satisfy ||Ux|l2 = 1, we multiply as (TU); (TUO), +e' (TU1){
A
* recalculate Un by TUo as (Ui); = Σ 1gck
(E1)2 (d: dr) v /d,//e de Ci
A
(rU)) TTk Σ stk
Ci, choose E' = 7
El (di - db) / dd
d min
1
then ||1U1|12 1 lif
/ | + Eipk 7di-dg
Axt
14

---

Then we consider the normalized rU as U in the following analysis. Assume (U) is the eigenvector the smallest non-zero eigenvalue, then at the step
E(A) E
where E is in terms of the randomness in the proposed sampling procedure.
Based on the approximation
A
(U) Tek +
Σ
de dmnn
de
x
Oanin
then
# (U.h + + =1 du > dmin
Define S = {i E (1,2,...,,) . Ui + 0} and P1 P(the node being selected to query & S). Take p = min;es P(i).q = maxies P(i) and P.)) denotes the probability of being selected into
candidate set size Denote k dmin, we first upper bound P1 as
(n- (1 9) k-
p)
P1 S (2-h)
L= Am- qm (1 4) k- (m- 1) (1) p)
where = p(1 - 9)
(1 - p)g
Zi=0
(m-1)
We calculate the denominator as
k
k
k
n k
11¹ = co
71
>
1
i
8
0m0
1=
Cp
n
17
2k-2
Cp
n
Vk +
?
k
In addition, by Stirling's approximation, when is large
n
m
2am((n - m) m m)n-
n
k
n k 2mmm(n 1s m)
(n - k)
mm 8: m ) n
then combining the above simplification, we have
k
m
(n -
(n m) 1
V +1 Co
P
11
71
171 n1
(n k m m nー
n2 k
m
n1 - k m
m
k
co
then we can lower bound the expected value of information gain as
E(U = Σ P()UU 2 (1 - P1) min (U3)
seS
iES
Notice that P1 is monotone decreasing function of m given n and l fixed, then we can select mo such that
k mo
me
mg
& v s
8
n mg
n
co
where 8 << is constant, therefore E( (1 6) minjes (U?+).
15

---

Next we lower bound the quantity minjes (.)) Denote = max; _ and = {
dymds dmin
<
11/,
we calculate the lower bound for minkes (U as
72 (d.- d2
min (02) 2 min RES
ViES
di dmii
1
(d: d2 di + 1
(di- do d, doan
Σ
d2 dmnn
min
(d [d,-d,² d
3#Lizi
Omnn
(d,-d di dmin
Σ
min
(d (d,-d,) Amnn
dmin
1
Σ
d
Σ
jEft:
de
1
de de K+ man
mma
1
7/1 (Dod min
dman 170)
which implies
min XSS
(U+.
ni (nodl dmin 170)
As result, as long as 2 mo have
1- n Mnode + dmii 170)
E(U >
A.3 Proof of Theorem 4.2
Proof: Based on the assumption that f E Projı.., (X), we denote d, = K1 S sj S 1 S w
Ud, U X,3 for some parameter 3 E R and (f, U.) = U X,3. For the query set S and the corresponding bandwidth frequency w < X w|ll do and U (U1, U2, Ua). We denote V Vnxrz = V,Vi the bases of Projr. span X) where V/2 is obtained from SVD decomposition UfX VV where (Vi)axra and (V2)pxra are left and right singular vectors, respectively. The diagonal matrix Eraxra contains ra positive singular values with ra S min(d, p}. The estimation (11) at the end of section 3 is equivalent to the weighted regression problem of {(V,, i,, Y,, 8,) hes.
and Ud, = (U1, U2 ... ,Ud.). Therefore, we can represent
wo. similarly denote d K1
j=
arg min /ePro).., (X) iES
E& f(1)12
arg min
E - -Vo, .........VVVV..... (V))(1))
aEbrax1
where [S|= = B. have the least squares solution
ATWYB
16

---

where
(1)
A =
and W = diag(v 11....
(18)
88 V1 (B)
V8ra Vra (B)
We assume Y = =f+ e, where E (E) 0 and V Var(s)
= o². Notice the oracle f satisfies
arg min
Σ Ey (1))
wo span(X)
We decompose the space Proji... span (X) as Proj span (X) span
span
span span
Then decompose f= + f2, where E Proj span X); fo E (Projr, span(X)) then
Ey (Y, (i)) Σ
fi = arg min
SEPrOje., {)p 1=1
Then represent f1 (1) (Vi(1), .... Vr (a)) by solving Aa(fi) Wf. we have
a(f:) = AA -1 Wf, 2
From ① and
we have
Σ ((1) (())
=IIf - f & |5 - fill2 + || - f1
$ a (i) a(fi) | + ||f f
(A A) ATW (Ys (())
12 [[ fll2
SAmaz (ATA) -1 IA W (Ys (fi) 112 ||f fl12
Denote YY; -y,f((() we have
Zd Es
Es||A Wg W
j=1
Denote (;; = 8; * Pt for j E S where Pj the probability node j being selected to query. Since
1
Es [s, V.O)(, - +()) Es
V.()(Y, f(()))
Py
Ey VV(0) - (1))
1=1
0 since V. T fg
have
Es LA W
Σ Es
v (2
Ssup
V
x Σ
Es
(3,9,)
Ø=1
B
sup ,
x
Σ
Es
93
Pj
1=1
/=1
B
=sup
V(O)
X
0g
Ey (Y f(()))
1=1
17

---

Notice that
Ey (Vi - (V)-) = Σ Ey Ey - f(1)) +
(f(T) fi())) = =no² + 1lf f f2 Σ
1=1
Notice that f= Ud, U X3 and fi = U,U then f-fi = U2 U3 Eisa U,)U, where
Ud (Ua+1,'.. Ud,) Therefore, || fil Disdiiespp(r) (f, U.) We first state and then
prove the following Lemma
Lemma A.1 For the output from Algorithm with query budgets, we have
4
V. S 108, and
04
sup
SJ
3
jES
1
8
1
2 C
X(A A)
2
(1
my
2'
3
X
1
myd Co
with probability 1
where 8
T₂CCo mB
and Co is a constant such that C3 (m)) max(2, 10 ).
Using Lemma we have
E f112 SAmin (ATA)=
Σ
V.Oi?
x Σ Ey - f1())) + || f.l12
02
sup jES
8j
t=1
mv8
CCpra
n
<2(1 +
)² x 3
10
x
Ey - f())) + +I[f ff
Co
B
j=l
<0(2( 2(
Fat
+
rat
3/2
+
rat
(no² +
Σ
1)
Σ
(U,,))
B
B
B
(>d,(E))p)())
with probability larger than 2m
where > 2m.
t
In the following, we prove Lemma which is based on Theorem 5.2 in 5 and Lemma 3.5 and 3.6 in
In the following, we denote the accumulated covariance matrix in the j selection as Aj. the potential function as L, (A,) Tr[(u, A,,
and R2(v, 1, A) = (;(ul A)(ul-A)-a - - 8: (A 111-111-- -=,"" where U, is the ith row of V. Notice that Σ R, 4 (A, At each iteration of R. algorithm 1, the ith node is selected one of candidates with p#; # we define the following probability
For the candidates,
17
if has maximum A among m candidates
qi
1
otherwise
m
where 0 < 17 < 1. Notice that when n) goes to 0, the approximate the step 3 in Algorithm 1. Therefore, the probability of node being query
pk Pselect k) -P((select lk in Bm) P(k in Bm) Pt qk
Qx
18

---

1
1
E
4k
=E EQui Bm
P(select k)
Pk
E Bm
Σ
P(select k/ Bm)
1uek T
P(select k)
km
E Bm
Σ
P(k E Bm) Uk
kEBm
P(Bm)
x
Σ
P(k E Bm)) UK
kEBm.
Σ
P( l E Bm) URUk
Bm El KEB
where f2 denote all C. possible candidate set with choosing m nodes from n nodes, P(Bm 1: E Bm) denotes the probability selecting m 1 nodes into Bm conditioning k Bm. Denote S2g as all possible size m candidate sets with node kt always in the set. Then
E
URUK
T )
Σ
Σ
P(Bm E Bm)
UUUE =
2k Uk
Pk
k=1
Clt
R=1
Uk
Rk 2
Σ Rdjpk
Re)piak
Ze(uI - A)
ql:
mE (ul - A)
where use the fact vo (o BoTB) for any semi cemi-positive definite matrix B. In addition,
[ Ra)pE
Σ R
(.,(
Uk. then wai I me (ul - A), which implies for for any k = 1, ... n. Denote wp = / Σ Rime
n
any ls [1,n]
wi (ul A) wwww (ut A) 1
wk T (ut A) wk
17
ww (uI -
mE
n
Similarly, we have
w (A - -1)-111--- - me
1
Then from Lemma 3.3 and Lemma 3.4 in [? we have
T (ul - A) -2
Tr(uI - A - wwww T) < Tr(ul - -A) +
wg
(19)
1
71
Tr(A + + - (I) < Tr( - IT) w (A 11)-2up
(20)
1
(21)
Define e' = we show in the following that E (Quy (Aj)) S a uu (Aj-1)
From
19 we have
2 Lujy, (A₂) S Luyds (Ag-1) + W. - (uy - 2
- w WJI (A -1gT)
-
1-6
1 146
19

---

Define A. =, - -1--1 (1-2) Rj
and A 1 4-11 (1+e') R
Notice that
i Tr(ul A) -Tr(uul A) <0
du
0
Tr(A 11) = =Tr(A 11 <0
al
at each step based on the design of uy and 1y. and (A) is convex in terms of and From we have
1
P Puy,,(A)) s & Pay,, (Aj-1)+
Tr((us] ( A5-1) 1w
1 -
1
-
1
then with (ww = =In=
E ( (,ai) S Lugdy (Aj-1) (Ag-)) +
Tr((ur] -
(1 (1-6) Ri
Tr [[[[A---1]]]]]
(1+c)E R
A/Tr(4A-11144
Define
f(t) Tr[(u) A.). Ay-1] + - -11-111-0111+40
then
0f())
Tr - A + [ A..1))1 101-
Øt
Since f(t) is convex, we have
@f(t)
2 = Pa (Ag-1) & D (Aj-1)
(22)
dt
Then plugin (22 have
E (uuy (Aj)) S $ (Agz)))
Notice that for selection
A uj
A
4l- [(+c'
(1 (1-c))
(1+e')
2
x(-ee)
(1-27)
where 1 ERi We consider that the selection process stops when at the iteration A that up - 44 2
Sra/c. Notice uo 2ra lo = =2ra, when stop at UA 44 > Sea, we have
Uk
l
(uo 10) + j =
(a., Ai,)
uo + Σラ j= Auy
4ra/s +
(Auy (11))
=/==0
2ra/# + (25")
_j=0 (Au, - A1,)
4ra/ E + 4ra/E
2ra/s + (25") 4ra/e
8ra/e
2ra (1 /E
1+ $ 45'
20

---

Then we have (1 1 ----_
S 1 + (s').
Notice that up 4x 7
Brd
me
Σj=o (Au, -1,) 2 Ara
Consider at the jth selection
) 1
6.
Auj - Ofy = 1 1-d
1tc) Es
2ec'
6'=
L Dugdy (Aj)
(1 - e') (c)
Then
B B-1
4rd
P (finish selection after B times selection: vectors) 2p
Σ
2
1 uq
1 (Aj)
B
4rd
Σ
$ -
(Aj)
2
7t
1=0
B
4ra
2P
2
B
Pagil (A,)
j
13
=P
Σ
L (Aj) 5
4rd
/=0
>1 4n
Be
2rd
21 B.
c
where we use the result that E (ou,,1 (Ap)) < 1 Pu by recursively using E (Pu,,,, (Aj)) s
uu--1d5-1 (A--1) and the fact that + uo to (Ap)
We consider the following reparametrization:
Vo 0 0, mid = 2ra(1 - m²=2 2
ue (1 m2-4 ix
For the jth selection, 0j 3, mid
From previous result, we have
S <1+4(=))
ui
with probability 2/C with coarra mB
Notice that us 24 + Σ/= (I-ert
and 4
lo + Σド= -- and
Uy + 4
Σ
k 1
6
1 1 c +
)
1+c
j=1
Then if stop at kth selection
2rd
2ra
2
1x
(wk-1
1x-1) + tb.
1-ce
1te'
2rd
Sra
tr.
I+c
Denote
I-e 140. then t2 2 te ge2 We find Co such that or
1
--(2p
2c'c
< 1 then t2 2
21

---

Therefore.
c(1
c
1
8rd + D
1
1
ug 11 Uk-1 4-11 +
e-
1 1t c
1-
1+c
8rd +8
1
1
1 1-c
1+c
8rd
16c'
+
(d)
Then we choose Co large such that we choose appropriate Co to satisfy previous requirement on e and é' as
16c
ug 4. S Given that c' = m and c
v8 Co
T-(2
2ee' <1 - (6')²
166' Ta
(E7)2 e
6' <<
Therefore, we choose Co such that Cp
>
m
+ +max(2, 16) x m
1)
Notice that
k
1
4ra
Uk
4
$
1-
l+e
2
1=1
and mid is defined as mid-
then
2==1 42 2 mid. Also,
1-c 142
k mid = mid
8
j=l 4
k
4Ee'
4
ra (1 - (E')2)
4
= -(1
4ee'
Ta(1 - (E
which implies
mid
[1
ra(1 - (c))2)
4ee'
1
Σ
m
E
ra(1 - (c92).1
4ec'
Uk + 4
Notice that for the design matrix A in 188 we have Vmid covariance matrix when the query process stops at the kthe selection. Therefore, the eigenvalues of
LA = A& where A is the accumulated
A satisfy X(AT A) mid (ATAN)
m2 mid
Then
4
uk mid
Le
Uk
c
mid'
uc tit
(1 r ra(1-(er)))
Acet
+l
Given that with high probability, 1 1- 4-46'- < 4e < + 4e',
Then for the lower bound,
1 (1+c}2
1
> (1 e1) 2e')
x
(1-(6') (1())) 26')
2 2 mVb/(1Co))
22

---

and upper bound
1 46'
Aee'
(1 2c - (1-())) - (1 (2e)
dee'
ral1
(
1-2 1
rd
4
1 46'
Aee'
1
3
x
(1 + 2c) (c))2)²
given
rd
> 41 (6)3)
8
1
3
1-
1
8
31
(mv8/(1(o))
Then with probability larger than
2. we have
1
8
X(A A)
E
X
x
(1
+
my
2
3
1
my yyCu
)2
BCo
Consider aj
mid
k
k
6
4
mid E
1.
Φ
lec
1 11-c
3
j=1
j=1
r2(
(c)p)
4
(1-e')z
Finally, check sup jES
(sj
1i=1
(v(013) at the kth selection
1
sup jES
$
sup jES
mid
R2
V+(2)1
j=1
sup
mid
R2
mid
Uk 12
uk -
Uk
11:
9 Z1
4.5ra
X
X
c
mid
2
mid
2
mid
4.5ra
cc'
= 2.25 x
1- (e))2 2.25 x 46 = 106
2ra(1 (ra(1-(e')3
Then we finish the proof of Lemma 1.
B
More on Biased Sequential Sampling
B.1
Computational complexity
In the representative sampling stage, the computational complexity of calculating the sampling probability is (n). We then sample m nodes formulate a candidate set Bm, where the complexity of sampling m variables from a discrete probability distribution is ((m) 31.. Consequently, the complexity of the representative learning stage O(n + m))
In the informative selection stage, we calculate the information gain A, for each node. This involves obtaining the eigenvector corresponding the smallest non-zero eigenvalue of the projected graph Laplacian matrix, with a complexity of (nn)) due to the singular value decomposition (SVD) operation. Subsequently, we compute A; for each node in the candidate set Bm based on their loadings on the eigenvector, which incurs an additional computational cost of ((m)). Therefore, the total complexity of our biased sampling method is O(n + m + nun + n²)). Given a node label query budget B, the overall computational cost becomes O(B (n m + nmn + n))).
When the dimension of node covariates p & n,, we can replace the SVD operation with the Lanezos algorithm to accelerate the informative selection stage. The Lanczos algorithm is designed to
23

---

efficiently obtain the kth largest or smallest eigenvalues and their corresponding eigenvectors using a generalized power iteration method, which has a time complexity of O(k))) [4]. As a result, the complexity of the proposed biased sampling method reduces to (ppn²). This is comparable to GNN-based active learning methods, as GNNs and their variations generally have a complexity of Opm)² per training update 37].
B.2
Connection to classification tasks
Although our theoretical analysis developed for node regression tasks, the proposed query strategy and graph signal recovery procedure are also applicable to classification tasks. Consider a K- class classification problem, where the response on each node is given by f(i) E 2, ................................ K. We introduce a dummy membership vector (Y1 (i) Yx(i)), where Yo(i) = if f(i) = c and Y.(+) 0 otherwise. For each class E 21, ... Kj. we first estimate 3. based on (14) with the training data (X,-, Ya(t), 8: hes, and then compute the score for class as f. X..-- The label of an unqueried node j is assigned as f(j) = arg max maxi Sess (fi (j), f2(i), ... (i). Notice that the above score-based classifier is equivalent to the softmax classifier:
exp(fi)
exp(fx)
arg m ISe5K K
exp(f.)
E. exp(f..)
since the softmax function is monotonically increasing with respect to each score function {
B.3 Discussion on Theorem 4.1
Theorem 4.1 is derived using first-order matrix perturbation theory 2 the Laplacian matrix L. In Theorem 4.1, we assume that the column space of the node covariate matrix X is identical to the space spanned by the first d eigenvectors of Lge. This assumption simplifies the analysis and the results by focusing on the perturbation of Lg=, where Lg= the reduced Laplacian matrix with zero entries in the rows and columns indexed by S.
The analysis can naturally extended to the general setting by replacing Ls- with P(1s- (1(s ) where P(t) is the projection operator defined in Section 3.2. Moreover, under the assumption on the node covariates, the information gain A, exhibits an explicit dependence on the network statisties, providing a clearer interpretation of how the network structure influences the benefits of selecting informative nodes.
Theorem 4.1 indicates that the improvement of biased sampling is more significant when dmin is larger and rjo, ?) are smaller. Specifically, dmin reflects the connectedness of the network, where a better- connected network facilitates the propagation of label information and enhances the informativeness of node's 's label for other nodes. smaller 7/1 prevents the existence of dominating nodes, ensuring that the connectedness does not significantly decrease when some nodes are removed from the network.
Notice that the node j" is the most informative node for the next selection, and yo measures the number of nodes similar to j" in the network. Recall that the proposed biased sampling method considers both the informativeness and representativeness of the selected nodes. Therefore, the information gain is less penalized by the representativeness requirement if no is small. Additionally, the size of the candidate set m should be sufficiently large to ensure that informative nodes are included By
B.4 Discussion Theorem 4.2
The RHS of [5)) captures both the variance and bias involved in estimating f using noisy labels on sampled nodes. Specifically, the first three terms represent the estimation variance arising from controlling the condition number of the design matrix on the queried nodes. The fourth and fifth terms reflect the noise and unidentifiable components in the responses of the queried nodes, while the last term denotes the bias resulting from the approximation error of the space using (X,
The bias term in Theorem 4.2 can be further controlled if the true signal exhibits decaying or zero weights on high- grehueryy network components. In addition to ras the size of the candidate set m also influences the probability of controlling the generalization error. A small m places greater emphasis
24

---

on the representativeness criterion in sampling, increasing the likelihood of controlling the condition number but potentially overlooking informative nodes, thereby increasing approximation bias.
For a fixed prediction MSF, the query complexity of our method is ((d), whereas random sampling incurs a complexity of Od d), where > d. Our method outperforms random sampling in two key aspects: (1) The information- -aaaaatt-----edddddd selection identifies f with fewer queries than random sampling, as shown in Theorem 4.1, and (2) our method achieves an additional improvement by actively controlling the condition number of the covariate matrix, resulting logarithmic factor reduction compared to random sampling.
B.5 Calculation on node-wise information gain and hyperparameter tuning
When calculating node-wise informativeness in 7.. we can enhance computational efficiency by avoiding the inversion of (t)). When t in the neighborhood 1g-, we can approximate:
P(t) ~ 5 X ) 1x5. D(t) - Dst) Dgz)(t),
where Xg= ((X1)s=, (Xp)s=) and Zg= X
-1/2. Then, the node-wise infor-
mativeness can be explicitly expressed as:
A, 1,0 [Zs) (Z
Σ JRissisn
1etz0r0j (Zs)) ( (
(23)
We find that this approximation yields very similar empirical performance compared the exact formulation in Therefore, we adopt the formulation in 23 for the subsequent numerical experiments.
In practice, we can tune m to ensure that the covariance matrix is well-conditioned. Specifically, can the biased sampling procedure multiple times with different values of and select the largest m such that the condition number of the covariance matrix on the query set S is less than 10 [20]. This threshold a commonly accepted rule of thumb for considering a covariance matrix to be well-conditioned (20). Additionally, is typically fixed at a small value, following the protocol outlined in [17
C More on Numerical Studies
C.1 Experimental setups
Synthetic networks The parameters for the three network topologies are: Watts-Strogatz (WS)
model (K = 4. Sws = 0.1) for small world properties, Stochastic block model (SBM) (Noommumity 4, P., = 0.35, Pout 0.01) for community structure, and crraássi-Albert (BA) model (a = 3) for scale-free properties. We set n = 100 for all three networks. After generating the networks, consider them fixed and then simulate Y and X repeatedly using 10 different random seeds. By a slight abuse of notation, we set the node responses and covariates for SBM and WS as For
U1.1,8 + & and X U1:10 + MU13:54 where My idd (0.3,, 0.1) and B (5,5.
length
the BA model, we set Y = U1i53 + and X = U111 + MU45:59. where Mij N(0.5, 0.2) and 3
(,,..,,,,,, 1.....
length 5
length 10
Real-world networks For the proposed method and all baselines, we train a 2-layer SGC model for fixed 300 epochs. In SGC, the propagation matrix performs low-pass filtering on homophilic networks and high-pass filtering on heterophilic networks. During training, the initial learning rate is set to 10- and weight decay as 10-4
C.2 Visualization
we visualize the node query process on synthetic networks generated using SBM and BA, as described in Section 5.1. The figure clearly demonstrates that nodes queried by the proposed algorithm adapt to the informativeness criterion specific to each network topology, effectively aligning with the community structure in SBM and the cale-freee structure in BA.
In Figure 2
25

---

Dataset
#Nodes
Type
m
d
Dataset
#Nodes
Type
m
d
SBM
100
homophilic
50
10
Citeseer
3,327
homophilic
1000
100
WS
100
homophilic
50
10
Chameleon
2,277
heterophilic
800
30, 30
BA
100
homophilic
15
Texas
183
heterophilic
60
15,
Cora
2,708
homophilic
2000
200
Ogbn-Arxiv
169,343
homophilic
1000
120
Pubmed
19,717
homophilic
3000
60
Co-Physies
34,493
homophilic
3000
150
Table 4: description of all datasets used in Section and the hyperparameter settings for each dataset. We set = 0.001 for all networks. For heterophilic networks, we combine the eigenvectors corresponding to the smallest and d largest eigenvalues.
C.3 Ablation study
To gain deeper insights into the respective roles of representative sampling and informative selection in the proposed algorithm, we conduct additional experiments on New Jersey public school social network dataset, School [25]. which was originally collected to study the impact of educational workshops on reducing conflicts in schools. As School not benchmark dataset in the active learning literature, we did not compare the performance of our method against other baselines in Section 5.2 to ensure fairness. this dataset with n = 615 nodes, each node represents an individual student, and edges denote friendships among students. We treat the students' grade point averages (GPA) as the node responses and select p = 5 student features- grade level, race, and three binary survey responses- as node covariates using standard forward selection approach.
As shown in Section 3.4, the representative sampling in steps and 2 of Algorithm is essential control the condition number of the design matrix and, consequently, the prediction error given noisy network data. illustrate in Figure 3a the condition number Amaa (X² Wx) using the proposed
Amin (XT Xs)
method, and compare with the one using random selection. With m 200, the proposed algorithm achieve significantly lower condition number than random selection, especially when the number of query small. In the Citeseer dataset, we investigate the prediction performance of Algorithm 1 when removing steps and 2, i.e., setting the candidate set Bn S for the t selection. Figure (bjure33jssha shows that, with representative sampling, the Macro-Fl score is consistently higher, with performance gap of up to 15%. Given that node classification on Citeseer is found to be sensitive to labeling noise [38], this result validates the effectiveness of representative sampling improving the robustness of our query strategy to data noise.
In addition, examine the ability of the proposed method integrate node covariates for improving prediction performance. In the School dataset, we compare our method to one that removes node covariates during the query stage by setting X the identity matrix I. Figure 3c illustrates that the prediction MSE for GPA is significantly lower when incorporating node covariates, thus distinguishing our node query strategy from existing graph signal recovery methods [12] that do not account for node covariate information.
C.4 Code
The implementation code for the proposed algorithm is available github.com/ github.com/Yuanchent WwJRobussAcriveLLannngg
26

---

Community
1st
2nd
3rd
(a) Stochastic Block Model (SBM)
Degree
High
Medium
(b) Barabási-Alber model (BA)
Figure (a) SBM, nodes are grouped fxx assigned community; for (b) BA, nodes are grouped by degree. The integer on each node represents the node queried by the proposed algorithm in one replication.
School
Citeseer
School
In (oooddiionn number)
4
Proposed Random
Prediction MSE
0.45
With covariates
Without
3
Macro-F
0.40
2
0.30
with sampling Without samping
0.25
0.40
6 8 10
12 14 16 18 20
20
40
80 100 120
8 10 12 14 18 Number of Labeled Nodes
Number Labeled Nodes
Number of Labeled Nodes
(a)
(b)
(c)
Figure 3: Ablation study: (a) The condition number (log scale) of the design matrix of query nodes selected by proposed method and random sampling. The effectiveness of representative sampling and incorporating covariate information Algorithm 1.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We support the claims with theoretical analysis in Section and empirical performance in Section 5.
2. Limitations
Does the paper discuss the limitations the work performed by the authors? Answer: [Yes]
Question:
Justification: See Section 5.2 for the limitation in real-data studies and Section for future work direction.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: See section 3 and 4 for the main theorems with assumptions. See Appendix 3.1, 3.2 and 3.3 for the detailed proofs.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yss]
Justification: We include implementation details for both synthetic and real-world networks in Appendix B.1, B.2 and B.3.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use open-source datasets that can be readily downloaded online. The implementation details in Appendix are sufficient enough to reproduce the main experimental results.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We include implementation details for both synthetic and real-world networks in Appendix C.1.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
We include error bars for the numerical studies both synthetic and real- world networks.
Justification:
8. Experiments Compute Resources
28

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: The paper focuses mainly on theories and our algorithm is not deep learning based.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::/ss..aaaa......./ppaaaaaaa
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please see the introduction section where we briefly touch on the positive societal impacts.
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Please Appendix C.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Please see Appendix C.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [No]
Justification: Our experiment simulates the human labeling process in active learning. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
29


Reviews:
[{"review_id": "2P14AFaWAF", "reviewer": "Reviewer_4PW9", "summary": "The work proposes an offline/batch active learning method for querying labels for nodes of a graph. The setting assumes access to noisy responses for the subset of nodes queried by the active learner. On the theoretical side, gains are shown over random selection, and bounds are shown on the generalization error of the proposed method. On the empirical side, the proposed algorithms is evaluated against random selection and other relevant baselines, and ablation studies are provided.", "questions": "- What is the significance of assumptions (1) and (2)? (lines 93-94) Specifically, is there a way to evaluate how strong assumption (1) is in practice? Also what is meant by \"$\\bf f$ is influenced by node covariates $\\bf X$\"?\n- Can you shed more light on the trade-off between informativeness and representativeness? Is there a standard way to quantify these?\n- \"Robust\" in the title is a bit confusing as it may be read as adversarial robustness, while you only seem to consider random noise. Consider using an alternative like \"noise-tolerant\". Furthermore, it would be good to state the type of noise (independent, bounded variance) considered early on, in Sections 1 and 2 (e.g. lines 58, 85).\n- Is there any approximation or other guarantee known for the quality of the proposed greedy approach (line 119) for selecting $\\mathcal{S}$ to maximize the threshold frequency?\n- Presentation of the greedy algorithm can be improved say using an algobox.\n- Line 127: prescence or abscence \n- Could you elaborate on the size of $m$ needed in Theorem 2? Can this be empirically estimated?\n- What is the running time complexity for the proposed algorithm?\n- Is it possible to empirically verify the tightness/looseness of the theoretical bounds?\n- Repeated references [2] and [3]", "limitations": "Authors should elaborate further on the limitations, e.g. assumptions needed for the theoretical results.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Label efficient learning in structured settings is a fundamental learning problem with numerous applications.\n- The proposed approach for graph active learning has both theoretical and empirical verified advantages over random selection.\n- The meta-approach of balancing informativeness and representativeness can be useful in other contexts.\n- Authors provide empirical evaluation which show superiority of proposed approach, and ablation studies which investigate the role of algorithmic components.", "weaknesses": "- Missing connections to related theoretical literature on active learning on graphs. E.g. [1, 2]\n[1] Dasarathy, G., Nowak, R., & Zhu, X. (2015, June). S2: An efficient graph based active learning algorithm with application to nonparametric classification. In Conference on Learning Theory (pp. 503-522). PMLR.\n[2] Zhang, J., Katz-Samuels, J., & Nowak, R. (2022, June). Galaxy: Graph-based active learning at the extreme. In International Conference on Machine Learning (pp. 26223-26238). PMLR.\n- Presentation can be made clearer, see suggestions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W.1** \nWe appreciate the reviewer highlighting relevant literature. Both our method and [1] derive relation between the performance of graph-based active learning and sample complexity. [1] quantifies the complexity on the graph domain of network. In contrast, our method examines the complexity in the spectrum domain. Interestingly, both [1] and our theory suggest query budgets scale approximately linearly with the labelling function complexity given a fixed estimation error. Both [2] and our work provide theoretical comparisons with baseline query methods. [2] utilizes bisection algorithm in [1] to show their method achieves better sample balanceness. Our method offers theoretical comparison with random sampling on information gains. \n\n**Q.1**\nWe revise the assumption on the graph signal space for clarity.  Denote $\\mathbf{U_d}$ as the first $d$ leading eigenvectors of the normalized graph laplacian, and $X_i, i = 1,\\cdots, p$ as the $i$th node-wise feature vector. We assume that there exists $d$ for the target graph signal $\\bf{f}$ such that:\n$$  \\mathbf{f} \\in  \\text{Span}( \\mathbf{U_d  U_d^T} X_1, \\cdots, \\mathbf{U_d  U_d^T} X_p ).$$\nBased on this assumption, $\\bf{f}$ depends on both network topology and node features. We compare with the function space considered by graph convolutional networks (GCN). It is known [3] that the function space of GCN can be represented as $U\\hat{G}U^TX$ with $\\hat{G} = \\text{diag}(g(\\lambda_1),\\cdots,g(\\lambda_n) )$, where $(\\lambda_i)_{i=1}^n$\nare eigenvalues of the normalized graph laplacian, and $g(\\cdot)$ denotes polynomial functions. Given the same level of homophily in the GCN space such that $g(\\lambda_i) =0, i >d$,  we have \n$$U\\hat{G}U^TX \\approx \\text{Span}( \\mathbf{U_d  U_d^T} X_1, \\cdots, \\mathbf{U_d  U_d^T} X_p )$$\ngiven $\\mathbf{U_dX}$ is full rank. In other words, the proposed function space is almost as large as the GCN space, and can approximate complicated graph signals well. \n\n**Q.2**\nThe trade-off can be clearly illustrated by Theorem 3, which can be simplified as:\n\n$$\\frac{1}{n}\\mathbf{E}_Y\\| \\hat{\\mathbf{f}} - \\mathbf{f}\\|_2^2 \\leq    \\mathcal{O}( \\frac{r_d}{\\mathcal{B}}) +  \\mathcal{O}( 1+\\frac{r_d}{\\mathcal{B}}) \\times \\text{Bias}, $$\n\nwhere $\\text{Bias} = \\big( \\frac{1}{n}\\sum_{i>d,i\\in \\text{supp}(\\mathbf{f})}  \\alpha_i^2 \\big)$, $r_d$ is the rank of $\\mathbf{U_d X}$ , therefore the increasing function of $d$. A large $d$ lowers representativeness among queried nodes, thereby increaseing\nvariance in controlling of condition number ($r_d/\\mathcal{B}$), while it reduces $\\text{Bias}$ term by including nodes more informative for identifying less smoothed components in $\\bf{f}$. We show the trade-off via simulations on **Figure 2** of PDF, which checks MSE under different $d$. Compared to small $d$, both MSE and variance are larger with larger $d$ when query is small, while MSE and variance decrease faster as query increases. \n\n**Q.3**\nWe thank reviewer for the thoughtful suggestion! We highlight that robustness is in terms of label noise in both the abstract and introduction, and clearly define label noise in section 2. \n\n**Q.4**\nThe approximation guarantee of greedy algorithm can be acheived if the threshold frequency $\\omega(S)$ proposed in Theorem 1 satisfies submodularity. A function is submodular if \n$f(S \\cup\\{v\\})-f(S) \\geq f(T \\cup\\{v\\})-f(T) $   if  \\$S \\subseteq T $. Based on [4], if $f$ is submodular, then\n$f(S) \\geq(1-1 / e) \\cdot f\\left(S^*\\right)$,  where S is the set obtained via the greedy algorithm and $S^*$ is set as the global maximizer.  We can show that $\\omega(S)$ is submodular for star, path, and cycle-shaped networks [5]. One can replace the greedy algorithm with the branch-and-bound algorithm, which has stronger approximation guarantee towards global maximization at the cost of higher computational complexity [6]. In practice, we find the greedy algorithm is good enough to maximize the threshold frequency. \n\n**Q.5**\nWe improve presentation by using algobox.\n\n**Q.6**\nWe revise \"prescence\" to \"presence\".\n\n**Q.7**\nWe present the a refined lower bound on $m$. To achieve information gain, $m$ needs to satisfy: \n$$( \\frac{n - d_{min} - m}{n - m})^m \\times ( \\frac{n - d_{min} - m}{n - d_{min}})^{d_{min}} \\times \\sqrt{d_{min}} < 1,$$\nwhere $d_{min}$ is the smallest node degree in the network. We elaborate on $m$ derived under different $n$ and $d_{min}$ in **Figure 3** of PDF. The results show that $m$ should be larger when $n$ is larger and $d_{min}$ is smaller. In practice, we can run the biased sampling procedure multiple times with different values of $m$, and set $m$ as the largest one that the condition number of covariance matrix $\\tilde{X}^T_{\\mathcal{S}}W_S\\tilde{X}_{\\mathcal{S}}$  is less than a threshold, e.g.,10 based on the rule of thumb for a well-conditioned covariance matrix \\cite{Applied_regression}. \n\n**Q.8**\nPlease see global response.\n\n**Q.9**\nWith $d$ and $m$ fixed, Theorem 3 implies MSE decays at a rate of $\\frac{1}{\\sqrt{\\mathcal{B}}}$.  We demonstrate the relationship between MSE and $\\mathcal{B}$ on simulated data in **Figure 1** of PDF. The simulation demonstrates that the order of sample complexity in Theorem 3 matches the empirical results, implying the tightness of the generalization bound in Theorem 3.  Also see global response.\n\n**Q.10**\nWe remove repeated references.\n\n>**Ref**\n\n[1]Dasarathy et al. (2015). S2: An efficient graph based active learning algorithm with application to nonparametric classification. COLT.\\\n[2] Zhang et al. (2022). Galaxy: Graph-based active learning at the extreme. ICML.\\\n[3] Wu et al (2019). Simplifying graph convolutional networks. ICML.\\\n[4] Nemhauser et al. (1978). An analysis of the approximations for maximizing submodular set functions. Math. Prog. \\\n[5] Chung (1997). Spectral graph theory. Amer. Math. Soc., 1997.\\\n[6] Morrison et al (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Disc. Opt.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kV83MGvH64", "reviewer": "Reviewer_emFb", "summary": "The paper addresses the challenge of active learning on graphs where labeling node responses is costly. The authors propose an offline active learning method that selects nodes by incorporating both network structure and node covariates. The method leverages graph signal recovery theories and random spectral sparsification, employing a two-stage biased sampling strategy to balance informativeness and representativeness.", "questions": "See above.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a novel offline active learning approach that integrates network structure and node covariates.\n- The proposed method is validated through extensive experiments on both synthetic and real-world datasets, showcasing its robustness and effectiveness.", "weaknesses": "- How does the proposed method perform on networks with varying levels of homophily and heterophily? Can it adapt to different types of network structures?\n- Can the method be extended to online active learning scenarios, where nodes are queried in a sequential manner rather than in batches?\n- How does the performance of the proposed method compare with state-of-the-art graph neural network-based active learning methods [1] in a broader range of network topologies and noise conditions?\n- Is there a significant computational overhead associated with the two-stage biased sampling strategy, and how does it impact the scalability of the method for large-scale networks?\n\n[1] Focus on Informative Graphs! Semi-supervised Active Learning for Graph-level Classification. Pattern Recognition 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging our algorithm's novelty and providing insightful feedback! We address your concerns point by point below.\n## Weaknesses:\n>**(A) Performance on networks with varying levels of homophily and heterophily**\n\nThanks for raising an excellent point about the generalizability of our method to networks with different levels of homophily. Our method can be flexible in adjusting the heterophily in node selection. For example, we can construct space $\\bf{H}(\\bf{X},\\bf{A})$ based on eigenvectors of $\\mathcal{L}$ corresponding to large eigenvalues. To handle coexistence of homophily and heterophily, we can adjust the space by combining eigenvectors corresponding to either small or large eigenvalues.\n\nCurrent methods have primarily been tested on networks with homophily (e.g., Cora, Citeseer). To address your question, we conducted additional experiments and tested competitive baselines on two networks with strong heterophily (Texas and Chameleon). The results, summarized in **Table 2** of the PDF, show that our algorithm achieves the best performance on Cora (strongest homophily) and Texas (strongest heterophily), and is also competitive on other datasets.\n\n>**(B)  Extension to online active learning scenarios**\n\nThe proposed method can be directly extended into sequential query manner and online setting as long as the entire network among nodes to be queried are accessible before the query process starts, which guarantees that the function space $\\bf{H}(\\bf{X},\\bf{A})$ is fixed therefore the label information can be accumulated for signal recovery. The biased sampling procedure can select one node and query its label. With the updated set of labelled nodes, we can target a subspace of $\\bf{H}(\\bf{X},\\bf{A})$ that better fits current labels. In next query iteration, we select unlabelled node maximizing information gain on the identified subspace. Intuitively, we gradually shrink the search space during the sequential query, with the goal to find a small but informative function space to estimate graph single, which facilitates to reduce generalization error. \nIn summary, the proposed method can be extended into sequential learning scenario, and we reasonably conjecture that the performance of proposed method can be further improved under sequential learning scenario.  \n\n>**(C)  Performance with SoTA methods [1] in a broader range of network topologies and noise conditions**\n\nThank you for the suggestion! We would like to clarify that [1] is designed for graph-level classification task, which differs from our method that aims to node-level classification tasks literature. However, [1] is an interesting read, and we will discuss it in our literature review section.\n\nTo address your question, we consider three topologies using synthetic networks:  Watts–Strogatz model for **small world** property, Stochastic Block model for **community structure**, and Barabási-Albert model for **scale-free** property. After generating the network, we simulate observed response $\\mathbf{Y}=f+\\epsilon$,  where $f$ is weighted linear combination of leading eigenvectors and $\\epsilon \\sim N(0, \\sigma^2 I_n)$ with noise level $\\sigma^2\\in(0.5, 0.6, 0.7, 0.8, 0.9, 1)$. Based on **Figure 4** of the PDF, the proposed method outperforms SoTA offline active learning methods and is robust to noise.\n\n>**(D) Computational overhead and scalability for large-scale networks**\n\nThe complexity of our biased sampling method is $\\mathcal{O}(n+m+nm+n^3)$. When the budget of node label query is $\\mathcal{B}$, the total computational cost is then $\\mathcal{O}(\\mathcal{B}(n+m+nm+n^3))$. \n\nThe main complexity of the proposed sampling method originates from the SVD operation. When dimension of node feature $p<<n$, we can speed up the informative selection via replacing the SVD by Lanczos algorithm to obtain the $p$th largest or smallest eigenvalues and the corresponding eigenvectors. The time complexity of Lanczos algorithm is $\\mathcal{O}(pn^2)$ [2]. Then the complexity of the proposed biased sampling method is $\\mathcal{O}(pn^2)$ for single node query. This complexity is comparable to GNN-based network active learning methods since GNN in general has complexity $\\mathcal{O}(pn^2)$ in single training update [3].   \n\nIn terms of memory cost, the main cost is to store the $n$-by-$n$ graph laplacian matrix $\\mathcal{L}^k$. However, when the network is sparse, $\\mathcal{L}^k$ is also sparse given moderate $k$, which can be handled with memory-efficient sparse matrix formats such as Python SciPy package. More importantly, we do not need to store and SVD the $n$-by-$n$ $P_{\\mathcal{S}^c} L^k P_{\\mathcal{S}^c}$ to obtain its eigenvectors and eigenvalues for node selection.  Notice that for the rank-p projection matrix \n$P_{\\mathcal{S}^c} = Z_{\\mathcal{S}^c} Z_{\\mathcal{S}^c}^T$ where $Z_{\\mathcal{S}^c} \\in \\mathcal{R}^{n\\times p}$ is the base of $P_{\\mathcal{S}^c}$. Then we can first perform SVD on $p$-by-$p$ matrix $Z_{\\mathcal{S}^c}^T L^k  Z_{\\mathcal{S}^c} = U^T\\Sigma U$, and the desired eigenvalues and eigenvectors are $\\Sigma$ and $Z_{\\mathcal{S}^c}U^T$, respectively. During the process, we only need to store and SVD a $p$-by-$p$ and a $n$-by-$p$ matrix, which can be handled efficiently via GPU-based matrix multiplication even when $n$ is very large. We report the computational time of proposed method for one node query on multiple benchmark network data in **Table 3** of the PDF. The time cost of single querying is about 2 second when $n$ is about 170,000. \n\n>**References**\n\n[1] Focus on Informative Graphs! Semi-supervised Active Learning for Graph-level Classification. Pattern Recognition 2024\\\n[2] Golub, Gene H., and Charles F. Van Loan. Matrix computations. JHU press, 2013.\\\n[3] Wu, Zonghan, et al. \"A comprehensive survey on graph neural networks.\" IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "rFLUIEL5wK", "reviewer": "Reviewer_7FJA", "summary": "The paper proposes a strategy for collecting labeled data for a semi-supervised learning algorithm focused specifically on learning on graphs. The paper provides a theoretical analysis of the proposed method, capturing both the quality of the samples that are selected for labeling as well as the the prediction error of the overall learning procedure. Experimental results show that the method the applicability of the method to real-world datasets.", "questions": "- What is the computational efficiency of the proposed method?\n- How tight is the upper bound in Theorem 3? Would it be possible to compare it to numbers from simulations on some simple synthetic settings?\n- How does the method compare to online AL methods for graphs (e.g. [36, 37, 30] etc) or other offline AL methods for graphs?", "limitations": "While the paper discusses some of the limitations of the proposed approach, it would be good to have a more detailed section on the computation cost of running the method as well as show the impact of various hyperparameters of the method on performance (e.g. m, various properties of the network and the generating process for (X, Y) etc).", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The method proposed in the paper, as well as the problem setting are explained clearly.\n- The paper provides theoretical guarantees for the method that indicate its superiority compared to random sampling (Theorem 2) and characterize the error rate that can be achieved with this active SSL strategy (Theorem 3).", "weaknesses": "- The empirical analysis does not very convincingly suggest that the proposed method is better than the baselines considered. Moreover, it would be helpful if the figures showed confidence intervals or error bars.\n- The experimental results only compare with a few heuristics for data collection. It would be informative to consider other AL works proposed in the graph learning literature as baselines.\n- It is not very clear how the paper is positioned in the literature. It would help to have a related work section that can indicate prior works on AL and active SSL on graphs.\n- The clarity of the section 3 could potentially be improved, perhaps by reducing the amount of symbols to the ones that are strictly necessary and providing more clearly marked (e.g. with paragraph titles) intuitive descriptions of the steps that need to be taken and the obstacles that need to be overcome.\n\nMinor remarks:\n- lines 19-21: 3 different learning paradigms are mentioned in the first two sentences (active, semi-supervised and transductive learning). It would help if it was clearer early on how they are relevant for the problem that motivates this work.\n- line 89: undefined symbol $\\mathcal{B}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback, which greatly improves our paper! We address the reviewer's comments point by point below.\n\n>**Weakness 1: empirical analysis does not very convincingly**\n\nThank you for the comment! In the global response PDF, we included additional experiments on networks with various topologies (**Figure 4**) , varying levels of homophily (**Table 1**) and much larger scales (**Table 2**) . The proposed algorithm achieved the best prediction performance on three synthetic networks with different topologies, the large-scale network Arxiv, the homophily network Cora, and the heterophily network Texas.  For the other four datasets, it is fair to argue that our performance was also competitive. Given these promising results, we are excited to refine the current algorithm in future work, such as extending it to the online setting, to further enhance its empirical performance on different networks. In the updated numerical results, we have included **error bars** indicating standard deviation following your suggestion.\n\n>**Weakness 2:  compare with AL baselines**\n\nWe have included several more SoTA offline methods (RIM, GPT, SPA , FeatProp) and online methods (AGE, IGP)  graph active learning methods in the additional experiments on both synthetic and real-world networks. Please refer to **Experiments** in the global response for details.\n\n> **Weakness 3:  literature review on related works on graph-based active learning**\n\nMany graph-based active learning strategies have been proposed based on the principle of maximizing query gain across various information criteria that are defined on the graph domain. The effectiveness of maximizing the graph-domain-based information measurements is generally not guaranteed and challenging to analyze due to quantify complexity of graph signal on graph domain. While complexity measure of binary functions have been proposed for the graph domain [1], its extension to general graph signal with node-wise features remains unclear. Without an analyzable complexity measurement of the labeling function, information maximization may not align with the fastest direction of searching labeling function space. Moreover, most of the existing query information measurements rely on real-time label feedback and are not appliable in offline batch settings.\n\nWe propose a new active learning method on spectral domain based on graph spectral method. While spectral methods are utilized in graph sampling and signal reconstruction task [2,3], we utilize spectral methods to introduce a well-defined complexity measurement of labeling function and the associated query strategy in the spectral domain. \n\nOur method is also related to the active learning for regression problem, where learning performance is guaranteed via sample complexity analysis [4,5]. The most notable solution is to use importance sampling based on statistical leverage scores [6], which has sub-optimal sample complexity.  The sample complexity of active regression problems is studied under 𝑙𝑝 norm loss function [7]. Recently, it has been shown that the optimal sample complexity can be linear in terms of the number of regression parameters [8]. Existing methods along this line focus on linear regression [7, 8] or polynomial regression [9], whereas our method extends the theoretical guarantee of active regression learning to graph semi-supervised learning task.\n\n\n> **Weakness 4: better presentation for section 3**\n\nWe appreciate reviewer's feedback. We have revised the notation system in this paper to simplify and better present the proposed method. In addition, we re-organize the materials and add intuitive discussion to enhance the logic flow and readability. \n\n>**Weakness minor**:\n\nWe thank the reviewer for thoughtful comments. We have re-organized materials in introduction, and clearly define $\\mathcal{B}$ as the query budget before line 89. \n\n> **Q1: computational efficiency of the proposed method**\n\nPlease see global response on **computational cost**. \n\n> **Q2: tightness of the upper bound in Theorem 3 and empirical validation**\n\nWith $d$ and $m$ fixed, Theorem 3 implies MSE decays at a rate of $\\frac{1}{\\sqrt{\\mathcal{B}}}$ where $\\mathcal{B}$ is the query budget. We demonstrate the relationship between MSE and $\\mathcal{B}$ on simulated data in **Figure 1** of the global response PDF. The simulation demonstrates that the order of sample complexity in Theorem 3 matches the empirical results, implying the tightness of the generalization bound in Theorem 3. Please also see **Optimality of sample complexity** in global response.\n\n\n> **Q3: Compare to online and offline AL methods**\n\nPlease see Weakness 2 and **Experiments** in global response.\n\n>**References**\n\n[1] Dasarathy et al. (2015) S2: An efficient graph based active learning algorithm with application to nonparametric classification. COLT\n\n[2] Gadde et al. (2014). Active semi-supervised learning using sampling theory for graph signals. ACM SIGKDD\n\n[3] Shuman et al (2013). The emerging field of signal processing on graphs. IEEE \n\n[4] Kiefer & Wolfowitz (1959). Optimum designs in regression problems. The annals of mathematical statistics\n\n[5] Chaudhuri et al. (2015) Convergence rates of active\nlearning for maximum likelihood estimation. NeurIPS\n\n[6] Mahoney et al (2011). Randomized algorithms for matrices and data. Foundations & Trends in Machine Learning\n\n[7] Musco et al (2022). Active linear regression for p norms and beyond. IEEE \n\n[8] Chen & Price (2019). Active regression via linear-sample sparsification. COLT\n\n[9] Meyer et al. (2023) Near-linear sample complexity for lp polynomial regression. ACM", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "N1SxStBDPq", "reviewer": "Reviewer_hH2h", "summary": "This paper proposes an offline active learning method that selects nodes to query by explicitly incorporating information from both the network structure and node covariates. This paper establishs a theoretical relationship between generalization error and the number of nodes selected by the proposed method.", "questions": "Please provide detailed experimental results for additional datasets.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical analysis is sufficient.\n\n2. Offline graph active learning is important.\n\n3. The proposed method is easy to implement.", "weaknesses": "I appreciate the author's theoretical analysis, but the experimental section is clearly insufficient. Recent work on graph active learning[1] has been conducted on larger-scale datasets like Arxiv and Products. Conducting experiments solely on datasets such as Cora is not adequate.\n\n[1] Partition-based active learning for graph neural networks. TMLR 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging the theoretical analysis of our algorithm and for your insightful suggestions! We have carefully considered your concerns regarding the insufficient experimental results, and have worked diligently to address them.\n\n>**Weakness: Recent work on graph active learning[1] has been conducted on larger-scale datasets like Arxiv and Products. Conducting experiments solely on datasets such as Cora is not adequate.**\n\nTo demonstrate the scalability of our algorithms on larger-scale datasets, we conducted experiments on the two largest datasets (Co-Physics with n=34,493 and Ogbn-Arxiv with n=169,343) included in your suggested paper [1]. The results of our algorithm and the baseline methods are summarized in **Table 2** of the global response PDF.  The greatest improvement is observed in the Macro-F1 score on Arxiv, with a margin as large as 4.8% at 320 labeled nodes. We argue that this is particularly significant given that Arxiv (41 classes) is a class-imbalanced data, where Macro-F1 is a more appropriate metric for evaluation.\n\nInspired by your comment, we carefully examine computational cost of the proposed method. The complexity of our method is $\\mathcal{O}(n+m+nm+n^3)$ for a single node query. When dimension of node feature $p<<n$, we can speed up the informative selection via replacing the SVD by Lanczos algorithm to obtain the $p$th largest or smallest eigenvalues and the corresponding eigenvectors. The time complexity of Lanczos algorithm is $\\mathcal{O}(pn^2)$ [2]. Then the complexity of the proposed biased sampling method is $\\mathcal{O}(pn^2)$ for single node query. This complexity is comparable to GNN-based network active learning methods since GNN in general has complexity $\\mathcal{O}(pn^2)$ in single training update [3].   \n\nMore interestingly, we found that there is no need to store and perform SVD on the $n$-by-$n$ $P_{\\mathcal{S}^c} L^k P_{\\mathcal{S}^c}$ to obtain its eigenvectors and eigenvalues for node selection.  Notice that for the rank-p projection matrix \n$P_{\\mathcal{S}^c} = Z_{\\mathcal{S}^c} Z_{\\mathcal{S}^c}^T$ where $Z_{\\mathcal{S}^c} \\in \\mathcal{R}^{n\\times p}$ is the base of $P_{\\mathcal{S}^c}$. Then we can first perform SVD on $p$-by-$p$ matrix $Z_{\\mathcal{S}^c}^T L^k  Z_{\\mathcal{S}^c} = U^T\\Sigma U$, and the desired eigenvalues and eigenvectors are $\\Sigma$ and $Z_{\\mathcal{S}^c}U^T$, respectively. During the process, we only need to store and SVD a $p$-by-$p$ and a $n$-by-$p$ matrix, which can be handled efficiently via GPU-based matrix multiplication even when $n$ is large. We report the computational time of proposed method for one node query on multiple benchmark network data in **Table 3** of the PDF. The time cost of single querying is about 2 second when $n$ is about 170,000. \n\nTo the best of our knowledge, we did not find offline graph-based active learning methods in the current literature have been tested on the Products dataset (n=1,569,960) . We admit that it is difficult to re-run our method and all benchmark methods on this dataset within the limited rebuttal period. However, we appreciate the reviewer for pointing out this interesting dataset, and we will include these results in the final version of our paper.\n\n>**Question: Please provide detailed experimental results for additional datasets.**\n\nIn addition to larger-scale datasets, we also included additional datasets that cover a wide range of homophily and heterophily levels. Besides the benchmark homophily networks (Cora, Citeseer, and Pubmed), we conducted experiments on two heterophily networks (Texas and Chameleon). We also ran all the competitive baselines on these two datasets, as they were not included in the original papers of any of the baselines. The results are summarized in **Table 1** of the global response PDF. Our algorithm achieves the best performance in Cora and Texas and is comparable to the best baselines in Citeseer, Pubmed, and Chameleon.\n\nMoreover, we conducted simulation studies on synthetic networks with three different topologies: small-world property, community structure, and scale-free property. The results are summarized in **Figure 4** of the global response PDF. The proposed algorithm achieved the best performance in all three scenarios under different noise levels.\n\n**Summary:** Following your questions, we conducted experiments on additional networks of much greater size, different levels of homophily, and various topologies. The proposed algorithm achieved competitive, if not the best, performance in  every category, indicating its scalability, generalizability, and robustness.\n\n>**References**\n\n[1] Partition-based active learning for graph neural networks. TMLR 2023.\\\n[2] Golub, Gene H., and Charles F. Van Loan. Matrix computations. JHU press, 2013.\\\n[3] Wu, Zonghan, et al. \"A comprehensive survey on graph neural networks.\" IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We are grateful to all reviewers for their time and insightful feedback. We are encouraged that the reviewers found our work:

1. contributes on significant area with umerous applications (4PW9, hH2h)
2. novel and theoretically solid (4PW9, emFb, hH2h, 7FJA)
3. introduces the trade-off between informativeness and representativeness is useful and generalizable (4PW9)
4. shows superiority on extensive empirical data and synthetic data (4PW9, emFb)
5. easy to implement (hH2h)
6. well present (7FJA)

**Main contributions**:
- propose a new offline graph-based active learning method integrating both network and node features, and robust to random label noise. 
- introduce complexity measurement of labeling function and query information gain in the spectral domain. Proposed query strategy aligns with function complexity measurement in the spectral domain, thereby ensuring the learning performance.
- derive the generalization error bound for the proposed method, implying the noval trade-off between informativeness and representativeness in node query. 
- conduct extensive empirical and ablation studies to verify the superiority of the proposed method.   

We have revised our paper based on reviewers' feedback, which greatly improve our paper. Please find figures and tables in the attached one-page PDF. We summarize major revisions below:

**Empirical studies**
- compare  with multiple SoTA offline and offline active learning methods on five benchmark datasets with varying homophily levels (Table 1)
- compare with offline methods on large scale networks (Table 2)
- compare with offline methods on synthetic data with different network topologies and label noise levels (Figure 4)

**Theory analysis**
- disucss and verify the tightness of convergence rate in Theorem 3 via empirical studies (Figure 1)
- disucss and verify the trade-off between informativeness and representativeness via empirical studies (Figure 2)
- disucss and elaborate the candidate size needed for Theorem 2 (Figure 3)

**Computational cost**
- analyze the time complexity of the proposed method
- investigate running time on benchmark networks with different size and verify the scalability (Table 3) 

**General discussion**
- model assumption 
- relation with existing methods and theoretical results

**Common questions**

**Experiments**

Based on the reviewers' feedback, we have conducted additional experiments, summarized in the attached PDF as follows:

- **Figure 4**: simulation studies on three synthetic networks with different topologies (Small world property, community structure and scale-free property) under different noise level. 
- **Table 1**: experiments on real-world networks with different levels of homophily (Homophily networks: Cora, Citeseer and Pubmed; heterophily networks: Texas and Chameleon).
- **Table 2**: experiments on real-world large-scale networks (Ogbn-Arxiv and Co-Physics).

In these experiments, we compared the performance of the proposed algorithm with SoTA offline methods (RIM [1], GPT [2], SPA [3], FeatProp [4]) and online methods (AGE [5], IGP [6]) for graph active learning. The proposed algorithm achieved the best prediction performance on three synthetic networks with different topologies, the large-scale network Arxiv, the homophily network Cora, and the heterophily network Texas. For the other four datasets, its performance was also competitive. We hope the new experimental results justify the theoretical framework of our algorithm and address the reviewers' concerns.

**Computational cost**

The complexity of our biased sampling method is $\mathcal{O}(n+m+nm+n^3)$ where $n$ is number of nodes, $m\leq n$ is the size of candidate set. When the budget of node label query is $\mathcal{B}$, the total computational cost is then $\mathcal{O}(\mathcal{B}(n+m+nm+n^3))$. The main complexity of the proposed sampling method originates from the SVD operation. When dimension of node feature $p<<n$, we can speed up the informative selection via replacing the SVD by Lanczos algorithm to obtain the $p$th largest or smallest eigenvalues and the corresponding eigenvectors. The time complexity of Lanczos algorithm is $\mathcal{O}(pn^2)$ [7]. Then the complexity of the proposed biased sampling method is $\mathcal{O}(pn^2)$ for single node query. This complexity is comparable to GNN-based network active learning methods since GNN in general has complexity $\mathcal{O}(pn^2)$ in single training update [8].   

**Optimality of sample complexity**
When the target graph signal has finite complexity over spectral domain, or fast decay on its heterophily components, then the generalization error in Theorem 3 is dominated by the rarte factor $\mathcal{O}(1/\mathcal{B})$, which matches the optimal linear sample complexity in active learning tasks [9,10]. In addition, the MSE converges at the rate $\frac{1}{\sqrt{\mathcal{B}}}$, which is the optimal nonparametric convergence rate in statistics.

**References**

[1] RIM: Reliable Influence-based Active Learning on Graphs. NeurIPS 2021.

[2] Partition-based active learning for graph neural networks. TMLR 2023.

[3] A Structural-Clustering Based Active Learning for Graph Neural Networks. ISIDA 2024

[4] Active Learning for Graph Neural Networks via Node Feature Propagation. Arxiv 2021

[5] Active learning for graph embedding. Arxiv 2017

[6] Information gain propagation: a new way to graph active learning with soft labels. ICLR 2022

[7] Golub, Gene H., and Charles F. Van Loan. Matrix computations. JHU press, 2013.

[8] Wu, Zonghan, et al. "A comprehensive survey on graph neural networks." IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.

[9] Chen, Xue, and Eric Price. "Active regression via linear-sample sparsification." COLT. PMLR, 2019.

[10] Dasarathy, et al. "S2: An efficient graph based active learning algorithm with application to nonparametric classification." COLT, 2015.

Meta-review: This work studies active querying strategy on graph nodes in order to save label queries. Although reviewers found the empirical study can be expanded, reviewers also agree that the new algorithm and analysis are sound. Authors further clarified in the rebuttal that under certain regimes, the label complexity of the proposed approach is provably lower than that of passive learning (though with only a log factor). Under the classical random graph model, the information gain is provably higher.

Overall, while the saving in labels seems less appealing, the paper studies an important problem and has established a set of guarantees that may inspire a line of follow-up works, such as new algorithms that improve the label complexity and analysis on other graph models.
Decision: Accept (poster)