Robust Offline Active Learning on Graphs

Authors: yuanchen  wu
yubai  yuan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 05:04:01

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.

Main paper: 
 introduction: 
 In many graph-based semi-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 [29] 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 [36] in statistics. Traditional optimal experimental design methods select samples to maximize a specific statistical criterion [26, 19] . However, these methods often are not designed to incorporate network structure, therefore inefficient for graph-based learning tasks. On the other hand, selecting informative nodes on a network is studied extensively in the graph signal sampling literature [11, 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, a node's label often also depends on its individual covariates. Therefore, signal-sampling strategies that focus solely on network information may miss critical insights provided by covariates. are defined in the spatial domain, leveraging the message-passing 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 in 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 a 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 is 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 or online marketing tasks [32, 35] . Additionally, both network data and annotator-provided 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 of models on unlabeled nodes [7, 21] .To address these challenges, we propose an offline active learning on graphs framework for nodelevel prediction tasks. Inspired by the theory of graph signal recovery [11, 18, 28] and GNNs, we first introduce a 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.Building on this, we develop a greedy node query strategy. The labels of the queried nodes help identify 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-the contribution of queried nodes in recovering non-smooth components of a signal-and representativeness-the robustness of predictions against noise in the training data. Compared to existing methods, the proposed approach provides a 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 a 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 to high-frequency noise in node covariates. We provide a theoretical guarantee for the effectiveness of the proposed method in semi-supervised learning tasks. The generalization error bound is guaranteed even when the node labels are noisy. Our theoretical results also highlight an interesting trade-off between informativeness and representativeness in graph-based active learning. 
preliminaries: 
 We consider an undirected, weighted, connected graph G = {V, A}, where V = {1, 2, • • • , n} is the set of n nodes, and A ∈ R n×n is the symmetric adjacency matrix, with element a ij ≥ 0 denoting the edge weight between nodes i and j. The degree matrix is defined asD = diag{d 1 , d 2 , • • • , d n },where d i = 1≤i≤n a ij denotes the degree of node i. Additionally, we observe the node response vector Y ∈ R n×1 and the node covariate matrix X = (X 1 , • • • , X p ) ∈ R n×p , where the i th row, X i• , is the p-dimensional covariate vector for node i. The linear space of all linear combinations of {X 1 , • • • , X p } is denoted as Span{X 1 , • • • , X p }. The normalized graph Laplacian matrix is defined as L = I -D -1/2 AD -1/2 , where I is the n × n identity matrix. The matrix L is symmetric and positive semi-definite, with n real eigenvalues satisfying 0 = λ 1 ≤ λ 2 ≤ • • • ≤ λ n ≤ 2,Consider a graph signal f ∈ R n , where f (i) denotes the signal value at node i. For a set of nodes S, we define the subspace L S := {f ∈ R n | f (S c ) = 0}, where f (S) ∈ R |S| represents the values of f on nodes in S. In this paper, we consider both regression tasks, where f (i) is a continuous response, and classification tasks, where f (i) is a multi-class label.Since U serves as a set of bases for R n , we can decompose f in the graph spectral domain as f = n j=1 α f (λ j )U j , where α f (λ j ) = ⟨f , U j ⟩ is defined as the graph Fourier transform (GFT) coefficient corresponding to frequency λ j . From a graph signal processing perspective, a smaller eigenvalue λ k indicates lower variation in the associated eigenvector U k , reflecting smoother transitions between neighboring nodes. Therefore, the smoothness of f over the network can be characterized by the magnitude of α f (λ j ) at each frequency λ j . More formally, we measure the signal complexity of f using the bandwidth frequency ω f = sup{λ j |α f (λ j ) > 0}. Accordingly, we define the subspace of graph signals with a bandwidth frequency less than or equal to ω asL ω := {f ∈ R n | ω f ≤ ω}. It follows directly that ∀ω 1 < ω 2 , L ω1 ⊂ L ω2 .The key idea in graph-based semi-supervised learning is to reconstruct the graph signal f within a function space H ω (X, A) that depends on both the network structure and node-wise covariates, where the frequency parameter ω controls the size of the space to mitigate overftting. Assume that Y i is the observed noisy realization of the true signal f (i) at node i, active learning operates in a scenario where we have limited access to Y i on only a subset of nodes S, with |S| << n. The objective is to estimate f within H ω (X, A) using {Y i } i∈S by considering the empirical estimator of f asEQUATIONwhere l(•) is a task-specific loss function. We denote f * as the minimizer of (1) when responses on all nodes are available, i.e., f * = f V . The goal of active semi-supervised learning is to design an appropriate function space H ω (X, A) and select an informative subset of nodes S for querying responses, under the query budget |S| ≤ B, such that the estimation error is bounded as follows:∥f S -f * ∥ 2 2 ≤ ρ∥f * -f ∥ 2 2For a fixed B, we wish to minimize the parameter ρ > 0, which converges to 0 as the query budget B approaches n. 
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 representativeness to infer the labels of unannotated nodes in the network.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 a 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 Lω Span(X) := Span{Proj Lω X 1 , • • • , Proj Lω X p },where Proj Lω X i = j:λj ≤ω⟨X i , U j ⟩U j .Here, the choice of ω balances the information from node covariates and network structure. When ω = 2, H ω (X, A) spans the full column space of covariates, i.e., Span{X 1 , • • • , X p }, 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-consider, for example, the extreme case where |{U j | λ j ≤ ω}| = 2 and p ≫ 2-then Proj Lω X i reduces to Span{U 1 , U 2 }, resulting in a loss of critical information provided by the original X.By carefully choosing ω, however, this function space can offer two key advantages for estimating the graph signal. From a signal recovery perspective, H ω (X, A) imposes graph-based regularization over node covariates, enhancing generalizability when the dimension of covariates p exceeds the query budget or even the network size-conditions commonly encountered in real applications. Additionally, covariate smoothing filters out signals in the covariates that are irrelevant to networkbased prediction, thereby increasing robustness against potential noise in the covariates. From an active learning perspective, using H ω (X, A) enables a bottom-up query strategy that begins with a small ω 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 f can be approximated by its projection onto the space H ω (X, A). Specifically, letU d = {U 1 , U 2 , • • • , U d } ∈ R n×d stack the d leading eigenvectors of L, where d = arg max 1≤j≤n (λ j -ω) ≤ 0.The graph signal estimation is then given by U d U T d Xβ, where β ∈ R d is a trainable weight vector. However, the parameters β may become unidentifiable when the covariate dimension p exceeds d. To address this issue, we reparameterize the linear regression as follows:EQUATIONwhereβ = ΣV T 2 β and X = U d V 1 . Here, V 1 ∈ R d×r , V 2 ∈ R p×r, and Σ ∈ R r×r denote the left and right singular vectors and the diagonal matrix of the r singular values, respectively.In the reparameterized form (2), the columns of X serve as bases for H ω (X, A), thus dim(H ω (X, A)) = rank( X) = r ≤ min{d, p}. The transformed predictors X capture the components of the node covariates constrained within the low-frequency graph spectrum. A graph signal f ∈ H ω (X, A) can be parameterized as a linear combination of the columns of X, with the corresponding weights β identified via β = arg minEQUATIONwhere XS ∈ R |S|×r is the submatrix of X containing rows indexed by the query set S, and {f (i)} i∈S represents the true labels for nodes in S. To achieve the identification of f , it is necessary that |S| ≥ r; otherwise, there will be more parameters than equations in (3). More importantly, since rank( XS ) ≤ rank( X) = r, f is only identifiable if XS has full column rank. Notice that r increases monotonically with ω. If S is not carefully selected, the graph signal can only be identified in H ω ′ (X, A) for some ω ′ < ω, which is a subspace of H ω (X, A).We first define the identification of H ω (X, A) by the node query set S as follows:Definition 1 A subset of nodes S ⊂ V can identify the graph signal space H ω (X, A) up to frequency ω if, for any two functionsf 1 , f 2 ∈ H ω (X, A) such that f 1 (i) = f 2 (i) for all i ∈ S, it follows that f 1 (j) = f 2 (j) for all j ∈ V.Intuitively, the informativeness of a set S can be quantified by the frequency ω corresponding to the space H ω (X, A) that can be identified. To select informative nodes, we need to bridge the query set S in the spatial domain with ω in the spectral domain. To achieve this, we consider the counterpart of the function space H ω (X, A) in the spatial domain. Specifically, we introduce the projection space with respect to a subset of nodes S as follows:H S (X, A) := Span{X (S) 1 , • • • , X (S)p }, whereX (S) p (i) = X p (i) if i ∈ S 0 if i ∈ S cHere, X p (i) denotes the p-th covariate for node i in X. Theorem 3.1 establishes a connection between the two graph signal spaces H ω (X, A) and H S (X, A), providing a metric for evaluating the informativeness of querying a subset of nodes on the graph.Theorem 3.1 Any graph signal f ∈ H ω (X, A) can be identified using labels on a subset of nodes S if and only if:EQUATIONwhere S c denotes the complement of S in V.We denote the quantity ω(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 a given budget to maximize the bandwidth frequency ω(S), thus enabling the identification of graph signals with the highest possible complexity.To calculate the bandwidth frequency ω(S), consider any graph signal g and its components with non-zero frequency Λ g := {λ i | α g (λ i ) > 0}. We use the fact thatlim k→∞   j:λj ∈Λg c j λ k j   1/k = max λj ∈Λg (λ j ),where j:λj ∈Λg c j = 1 and 0 ≤ c j ≤ 1. Combined with the Rayleigh quotient representation of eigenvalues, the bandwidth frequency ω g can be calculated asω g = lim k→∞ ω g (k), where ω g (k) = g T L k g g T g 1/k.As a result, we can approximate the bandwidth ω g using ω g (k) for a large k. Maximizing ω(S) over S then transforms into the following optimization problem:S = arg max S:|S|≤B ω(S), where ω(S) := infEQUATIONwhere 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 a continuous relaxation of (5) .The selection procedure starts with S = ∅ and sequentially adds one node to S that maximizes the increase in ω(S) until the budget is reached. We introduce an n-dimensional vector t = (t 1 , t 2 , • • • , t n ) T with 0 ≤ t i ≤ 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 t = 1 S , where 1 S (i) = 1 if i ∈ S and 1 S (i) = 0 if i ∈ S c . We then consider the space spanned by the columns of D(t)X as Span{D(t)X}, and the following relation holds:H S c (X, A) = Span{D(1 S c )X}.Intuitively, Span{D(t)X} acts as a differentiable relaxation of the subspace H S (X, A), enabling perturbation analysis of the bandwidth frequency when a new node is added to S. The projection operator associated with Span{D(t)X} can be explicitly expressed asP(t) = D(t)X X T D(t 2 )X -1 X T D(t).To quantify the increase in ω(S) when adding a new node to S, we consider the following regularized optimization problem:EQUATION)The penalty term on the right-hand side of (6) encourages the graph signal ϕ to remain in H S c (X, A).As the parameter α approaches infinity and t = 1 S c , the minimization λ α (1 S c ) in (6) converges to ω(S) in (5) . The information gain from labeling a node i ∈ S c can then be quantified by the gradient of the bandwidth frequency as t i decreases from 1 to 0:EQUATION)where ϕ is the minimizer of (6) at t = 1 S c , which corresponds to the eigenvector associated with the smallest non-zero eigenvalue of the matrix P(1 S c )L k P(1 S c ). We then select the node i = arg max j∈S c ∆ j and update the query set as S = S ∪ {i}. The explicit representation of ∆ i in (7) can be found in Appendix B.5.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 Y (i) in (3), this noise term introduces both finite-sample bias and variance in the estimation of the graph signal f . As a 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:EQUATION)where s i is the weight associated with the probability of selecting node i into S.Specifically, the generalization error of the estimator in ( 8) is determined by the smallest eigenvalue of XT S XS , denoted as λ min ( XT S XS ). Given that λ min ( XT X) = 1, our goal is to increase the representativeness of S such that λ min ( XT S XS ) is lower-bounded by:EQUATIONHowever, the informative selection method in Section 3.2 does not guarantee (9) . To address this, we propose a sequential biased sampling approach that balances informative node selection with generalization error control.The key idea to achieve a lower bound for λ min ( XT S XS ) is to use spectral sparsification techniques for positive semi-definite matrices [15] . Let v i ∈ R 1×r denote the i-th row of the constrained basis X. By definition of X, it follows thatI r×r = n i=1 v T i v i .Inspired by the randomized sampling approach in [17] , we propose a biased sampling strategy to construct S with |S| ≪ n and weights{s i > 0, i ∈ S} such that i∈S s i v T i v i ≈ I.In other words, the weighted covariance matrix of the query set S satisfies λ min ( XT S W S XS ) ≈ 1, where W S is a diagonal matrix with s i on its diagonal. We outline the detailed sampling procedure as follows. After the (t-1) th selection, let the set of query nodes be S t-1 with corresponding node-wise weightsW t-1 = {s j > 0 | j ∈ S t-1 }. The covariance matrix of S t-1 is given by C t-1 ∈ R r×r , defined as C t-1 = XT St-1 XSt-1 = j∈St-1 s j v T j v j .To analyze the behavior of eigenvalues as the query set is updated, we follow [17] and introduce the potential function:EQUATIONwhere u t-1 and l t-1 are constants such that l t-1 < λ min (C t-1 ) ≤ λ max (C t-1 ) < u t-1 , and Tr(•) denotes the trace of a matrix. The potential function Φ t-1 quantifies the coherence among all eigenvalues of C t-1 . To construct the candidate set B m , we sample node i and update C t , u t , and l t such that all eigenvalues of C t remain within the interval (l t , u t ). To achieve this, we first calculate the node-wise probabilities {p i } n i=1 as:EQUATIONwheren i=1 p i = 1.We then sample m nodes into B m according to {p i } n i=1 . For each node i ∈ B m , the corresponding weight is given by s i = ϵ piΦt-1 , 0 < ϵ < 1. After obtaining the candidate set B m , we apply the informative node selection criterion ∆ i introduced in Section 3.2, i.e., selecting the node i = arg max i∈Bm ∆ i , and update the query set and weights as follows:if i ∈ S c t-1 : S t = S t-1 ∪ {i}, W t = W t-1 ∪ {s i }, if i ∈ S t-1 : s i = s i + ϵ p i Φ t-1 .We then update the lower and upper eigenvalue bounds as follows:EQUATION)The update rule ensures that u t -l t increases at a slower rate than u t , leading to the convergence of the gap between the largest and smallest eigenvalues of XT S W S XS , thereby controlling the condition number. Accordingly, the covariance matrix is updated with the selected node i as:EQUATIONWith the covariance matrix update rule in (13) , the average increment isE(C t ) -C t-1 = n i=1 p i s i v T i v i = ϵΦt-1 I. Intuitively, the selected node allows all eigenvalues of C t-1 to increase at the same rate on average. This ensures that λ min ( XT S XS ) continues to approach λ min ( XT 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 B m . Compared with the entire set of nodes, selecting from a subset serves as a regularization on informativeness maximization, achieving a balance between informativeness and representativeness for node queries.We summarize the biased sampling selection strategy in Algorithm 1. At a 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 B m . Intuitively, the covariance matrix on the updated S maintains lower-bounded eigenvalues if a node from B m is added to S. In the second stage, we select one node from B m based on the informativeness criterion in Section 3.2 to achieve a significant frequency increase in (7) .For initialization, the dimension of the network spectrum d, the size of the candidate set m, and the constant 0 < ϵ < 1 for spectral sparsification need to be specified. Based on the discussion at 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, we can set d = min{p, B}. The parameters m and ϵ jointly control the condition numberλmax( XT S W S XS ) λmin( XT S W S XS ) .Require: t = 0, C 0 = 0, the set of query nodes S 0 = ∅, the set of node weights W 0 = ∅, spectral dimension d, size of candidate set m, constant 0 < ϵ < 1/m, query budget B.Initialization: Compute SVD decomposition U T d X = V 1 ΣV T 2 , and set X = U d V 1 , r = rank( X), u 0 = 2r/ϵ, l 0 = -2r/ϵ, κ = 2r(1 -m 2 ϵ 2 )/(mϵ 2 ). while B > 0 doStep 1: Calculate Φ t as in (10) and the node-wise probabilities {p i } n i=1 using (11) .Step 2: Sample m nodes with replacement according to probabilities {p i } n i=1 to form the candidate set B m .Step 3: Select node i as i = arg max i∈Bm ∆ i and calculate its weightw i = ϵ piΦt . If i / ∈ S t , then update S t+1 = S t ∪ {i} and W t+1 = W t ∪ {s i } with s i = wi κ . Else if i ∈ S t , then update s i = s i + wi κ .Step 4: Update C t , u t , l t , B and t as:C t+1 = C t + w i v T i v i , u t+1 = u t + ϵ Φ t (1 -mϵ) , l t+1 = l t + ϵ Φ t (1 + mϵ) , B = B -1, t = t + 1.end while Query: Label all nodes in S through an external annotator.Output: Set of queried nodes S, annotated responses {Y i | i ∈ S}, smoothed covariates XS , and weights of queried nodes W.Based on the output from Algorithm 1, we solve the weighted least squares problem in (8):EQUATION)and recover the graph signal on the entire network as f = X β. The proposed method is illustrated for the regression task, with an extension to the classification task discussed in Appendix B.2. 
theoretical analysis: 
 In this section, we present a theoretical analysis of the proposed node query strategy. The results are divided into two parts: the first focuses on 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 a new node i is measured as the increase in bandwidth frequency, defined as ∆ i := ω(S ∪ {i}) -ω(S). We provide a step-by-step analysis of the proposed method by comparing the increase in bandwidth frequency with that of random selection. . Let ∆ R s and ∆ B s denote the increase in bandwidth frequency resulting from the s th 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 L S c . Then we have:E(∆ R s ) = Ω( 1 n ) (1), andE(∆ B s ) -E(∆ R s ) > Ω( 1 η 0 η 3 1 d 2 min ) -Ω( 1 n ) (2),where f = Ω(g) if c 1 ≤ | f g | ≤ c 2 for constants c 1 , c 2 when n is sufficient large. Inequality (2) holds given m satisfying ( n -m -d min n -m ) m ( n -m -d min n -d min ) dmin d min = O(1).The expectation E(•) is taken over the randomness of node selection. Both η 0 , η 1 are network-related quantities, whereη 0 ≜ #|{i : | di-d j * dmin | ≤ 1}| and η 1 ≜ max i ( di dmin ).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 a 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 1 For the underlying graph signal f , there exists a bandwidth frequency ω 0 such that f ∈ H ω0 (X, A). EQUATIONwhereα i := ⟨f , U i ⟩, supp(f ) := {i : 1 ≤ i ≤ n, |α i | > 0} and r d = rank(U T d X). E Y (•) 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-based active learning, which is controlled by the spectral dimension d. Since r d is a monotonic function of d, a larger d reduces representativeness among queried nodes, thereby increasing variance in controlling the condition number (i.e., the first three terms). On the other hand, a 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.  
numerical studies: 
 In this section, we conduct extensive numerical studies to evaluate the proposed active learning strategy for node-level prediction tasks on 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.We consider three different network topologies generated by widely studied statistical network models: the Watts-Strogatz model [33] for small-world properties, the Stochastic block model [13] for community structure, and the Barabási-Albert model [3] for scale-free properties. We compare our algorithm with several offline active learning methods: 1. D-optimal [26] selects subset of nodes S to maximize determinant of observed covariate information matrix X T S X S . 2. RIM [38] selects nodes to maximize the number of influenced nodes. 3. GPT [22] and SPA [27] 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 ( 14) on the labeled nodes, using the smoothed covariates X, to estimate the linear coefficient β and predict the response Ŷ for the unlabeled nodes. In Figure 1 , we plot the prediction MSE of the proposed method against baselines on unlabeled nodes for various levels of labeling noise σ 2 ∈ (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 to noise. The inferior performance of the baselines can be attributed to several factors. D-optimal and RIM fail to account for noise in the node covariates. Meanwhile, partition-based methods like GPT and SPA are highly sensitive to hyperparameters, such as the optimal number of partitions, which limits their generalization to networks lacking a clear community structure.We evaluate the proposed method for node classification tasks on real-world datasets, which include five networks with varying homophily levels (high to low: Cora, PubMed, Citeseer, Chameleon and Texas) and two large-scale networks (Ogbn-Arxiv and Co-Physics). In addition to the offline methods described in 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 a linear combination of heuristic metrics, while IGP selects nodes that maximize information gain propagation. Unlike regression, node classification with GNNs is a widely studied area of research. Previous works [22, 30, 38, 39] have demonstrated that the prediction performance of various active learning strategies on unlabeled nodes remains relatively consistent across different types of GNNs. Therefore, we employ Simplified Graph Convolution (SGC) [34] as the GNN classifier due to its straightforward theoretical intuition. Since SGC is essentially multi-class logistic regression on low-pass-filtered covariates, it can be approximately viewed as a 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 in Figure 1 demonstrate that the proposed algorithm is 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.e., 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 U d in Algorithm 1 toU d = {U 1 , • • • , U d , U n-d+1 , • • • , U n },combining eigenvectors corresponding to 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 2 summarizes the performance on two large-scale networks. The greatest improvement is observed in the Macro-F1 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 a graph-based offline active learning framework for node-level tasks. Our node query strategy effectively leverages both the network structure and node covariate information, demonstrating robustness to diverse network topologies and node-level noise. We provide theoretical guarantees for controlling generalization error, uncovering a novel trade-off between informativeness and representativeness in active learning on graphs. Empirical results demonstrate that our method performs strongly on both synthetic and real-world networks, achieving competitiveness with state-of-the-art methods on benchmark datasets. Future work could explore extensions to 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 Lanczos method [1] or Chebyshev polynomial approximation [16] during node selection. 
 
 Appendix: A.1 Proof of Theorem 3.1Proof : Consider the threshold frequency ω defined asEQUATIONand notice that 16 is true if and only ifEQUATION⇒ For ∀ϕ ∈ Proj Lω span(X) ∩ Proj L S c span(X) and ∀f ∈ Proj Lω span(X), we have g = ϕ + f ∈ Proj Lω span(X) by closure under addition and f (S) = g(S). Since Proj Lω span(X) can be identified by S, one must have f = g, which implies ϕ = 0. Hence, 17 is true.⇐ Given 17 is true, assume that Proj Lω span(X) cannot be identified by S. Then, by definition, there existsf 1 , f 2 ∈ Proj Lω span(X) such that f 1 (S) = f 2 (S) and f 1 ̸ = f 2 . Since (f 1 -f 2 )(S) = 0, f 1 -f 2 ∈ Proj L S c span(X). By clousure under addition, f 1 -f 2 ∈ Proj Lω span(X). However,f 1 -f 2 ∈ Proj Lω span(X) ∩ Proj L S cspan(X) is a contradiction with 17. Therefore, Proj Lω span(X) can be identified by S.A.2 Proof of Theorem 4.1Proof : Let U = {U 1 , U 2 , • • • , U n } be the eigenvectors of L = I -D -1/2 AD -1/2 and Λ = diag(λ 1 , λ 2 , • • • , λ n ).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 *L * = L + L (-i) , where L (-i) = -                   0 • • • L 1i • • • 0 . . . . . . . . . . . . . . . L i1 . . . L ii . . . L in . . . . . . . . . . . . . . . 0 • • • L ni • • • 0                  Define Λ * as the diagonal matrix containing eigenvalues of L * . Using the first order perturbation analysis [2] , we have Λ * ≈ Λ + diag(U T L (-i) U). Let L •i and L i• be the i th column and row of L, respectively. SinceL (-i) U j =                   -L 1i U ij . . . -L (-i) i• U j . . . -L ni U ij                   = -L •i U ij +                   0 . . . L ii U ij -L (-i) i• U j . . . 0                   = -L •i U ij +                   0 . . . (L ii -λ j )U ij . . . 0                   we have U T j L (-i) U j = -U ij (L i• U j ) + (L ii -λ j )U 2 ij = -U ij (λ j U ij ) + (L ii -λ j )U 2 ij =(1 -2λ j )U 2 ij since the diagonal entry of L is 1 Therefore, Λ * ≈ Λ +          (1 -2λ 1 )U 2 i1 . . . (1 -2λ n )U 2 in         Assume U 1 corresponding to the smallest non-zero eigenvalue of Λ * , then the increase of bandwidth frequency for node i is U 2 i1 . For random selection, where node i is queried with uniform probability,E(∆ R ) = 1 n n i=1 U 2 i1 ∝ 1 n For the proposed selection method, define R = diag(r 1 , r 2 , • • • , r n ), where r i = di dmin , then L =I -D -1/2 AD -1/2 = I + ϵ ′ D A0 +ϵ ′   (ϵ ′ d min ) -1 R -1 2 AR -1 2 -D A1   =A 0 + ϵ ′ A 1Next we perform matrix perturbation analysis, defineU 0 = I, Λ 0 = A 0 , Λ = Λ 0 + ϵ ′ Λ 1 , U = U 0 + ϵ ′ U 1where Λ, U approximate eigenvalues and eigenvectors of Λ * . Denote (U 1 ) k as the k th column of U 1 and assume d i ̸ = d j , we have(U 1 ) k = i̸ =k (U 0 ) ⊤ i A 1 (U 0 ) k (Λ 0 ) k -(Λ 0 ) i (U 0 ) i = i̸ =k A ik (ε ′ ) 2 (d i -d k ) √ d i √ d k e i (U ) k = (U 0 ) k + ε ′ (U 1 ) kTo satisfy ∥U k ∥ 2 = 1, we multiply τ as(τ U ) k = (τ U 0 ) k + ε ′ (τ U 1 ) k ⇒ recalculate U 1 by τ U 0 as (U 1 ) k = i̸ =k A ik τ 3 (ε ′ ) 2 (d i -d k ) √ d i √ d k e i ⇒ (τ U ) k = τ e k + i̸ =k A ik τ 4 ε ′ (d i -d k ) √ d i √ d k e i , choose ε ′ = τ 3 × 1 √ d k d 3 2 min ⇒ then ∥τ U k ∥ 2 = 1 if τ = 1 1 + i̸ =k A ik d i -d k d min 2 d i d minThen we consider the normalized τ U as U in the following analysis. Assume (U ) k is the eigenvector to the smallest non-zero eigenvalue, then at the t -1 stepE(∆) = E(U 2 ik) where E is in terms of the randomness in the proposed sampling procedure.Based on the approximation(U ) k = τ e k + i̸ =k A ik τ di-d k dmin × di dmin then # {U ik ̸ = 0} n i=1 = 1 + d k > d min Define S = {i ∈ {1, 2, • • • , n} : U ik ̸ = 0}and P 1 = P (the node being selected to query / ∈ S). Take p = min i∈S P(i), q = max i / ∈S P(i) and P(•) denotes the probability of being selected into candidate set size m. Denote k = d min , we first upper bound P 1 asP 1 ≤ n-k m q m (1 -q) n-k-m (1 -p) k k i=0 n-k m-i q m-k (1 -q) n-k-(m-i) k i p i (1 -p) k-i = n-k m k i=0 n-k m-i k i η i , where η = p(1 -q) (1 -p)qWe calculate the denominator ask i=0 n -k m -i k i η i = c 0 k i=0 n -k m -i 2 k i 2 k i=0 η 2i ≥ c 0 √ k + 1 n m 1 -η 2k+2 1 -η 2 > c 0 √ k + 1 n m .In addition, by Stirling's approximation, when n is largen m ∼ n 2πm(n -m) • n n m m (n -m) n-m n -k m ∼ n -k 2πm(n -k -m) • (n -k) n-k m m (n -k -m) n-k-mthen combining the above simplification, we haveP 1 < n -k n • n -m n -k -m • (n -k) n-k n n • (n -m) n-m (n -k -m) n-k-m × √ k + 1 c 0 ≤ n -k -m n -m m n -k -m n -k k × √ k + 1 c 0then we can lower bound the expected value of information gain asE(U 2 ik ) = i∈S P(i)U 2 i1 ≥ (1 -P 1 ) min i∈S U 2 ikNotice that P 1 is a monotone decreasing function of m given n and k fixed, then we can select a m 0 such thatn -k -m 0 n -m 0 m0 n -k -m 0 n -k k √ k ≤ δ c 0 , where δ < 1 is a constant, therefore E(U 2 ik ) > (1 -δ) min i∈S U 2 ik .Next we lower bound the quantity min i∈S U 2 ik . Denote η 1 := max i ( di dmin ) and η 0 := #|{i :| di-d k dmin | ≤ 1}|, we calculate the lower bound for min i∈S U 2 ik as min i∈S U 2 ik ≥ min   τ, τ 2 (di-d k ) 2 d 2 min × di dmin   ∀i ∈ S ≥ 1 (di-d k ) 2 d 2 min di dmin + 1 + (di-d k ) 2 d 2 min di dmin j̸ =1,j̸ =i 1 (dj -di) 2 d 2 min dj dmin ≥ 1 (di-d k ) 2 d 2 min di dmin   1 + o n (1) + j̸ =1,j̸ =i 1 (dj -di) 2 d 2 min dj dmin   ≈ 1 η 3 1   1 + j∈{i:| d i -d k d min |≤1} d 2 min + j / ∈{i:| d i -d k d min |<1} 1    ≥ 1 η 3 1 (η 0 d 2 min + d min -η 0 ) which implies min i∈S U 2 ik ≥ 1 η 3 1 (η 0 d 2 min + d min -η 0 )As a result, as long as m ≥ m 0 we haveE(U 2 ik ) ≥ 1 -δ η 3 1 (η 0 d 2 min + d min -η 0 ).Proof : Based on the assumption that f ∈ Proj Lω 0 span(X), we denoted 0 = |{1 ≤ j ≤ n | λ j ≤ ω 0 }| and U d0 = (U 1 , U 2 , • • • , U d0 ). Therefore, we can represent f = U d0 U T d0 Xβ for some parameter β ∈ R p×1 and ⟨f , U i ⟩ = U T i Xβ.For the query set S and the corresponding bandwidth frequency ω ≤ ω 0 , we similarly denote d = |{1 ≤ j ≤ n | λ j ≤ ω}| ≤ d 0 and U d = (U 1 , U 2 , • • • , U d ). We denote V n×r d = U d V 1 as the bases of Proj Lω span(X) where V 1 is obtained from SVD decomposition U T d X = V 1 ΣV T 2 where (V 1V i• , Y i , s i )} i∈S , f = arg min f ∈Proj Lω span(X) i∈S s i |Y i -f (i)| 2 ⇒arg min α∈R r d ×1 B i=1 | √ s i Y i -( √ s i V 1 (i), . . . , √ s i V r d (i))α| 2 ,where |S| = B. We have the least squares solutionα( f ) = A ⊤ A -1 A ⊤ W Y B 1whereEQUATIONWe assume Y = f + ε, where E (ε) = 0 and V ar(ε) = σ 2 . Notice the oracle f satisfiesf = arg min f ∈Proj Lω 0 span(X) n i=1 E Y Y i -f 2 (i)We decompose the space Proj Lω 0 span(X) asProj Lω 0 span(X) = Proj Lω span(X) Proj Lω span(X) c Then we decompose f = f 1 + f 2 , where f 1 ∈ Proj Lω span(X), f 2 ∈ Proj Lω span(X) c , then f 1 = arg min f ∈Proj Lω {span(X)} n i=1 E Y (Y i -f (i)) 2 Then we can represent f 1 (i) = (V 1 (i), . . . , V r d (i))α(f 1 ), by solving Aα(f 1 ) = W f 1 , we have α(f 1 ) = A ⊤ A -1 A ⊤ W f 1 2From 1 and 2 , we haven i=1 f (i) -f (i) 2 =∥ f -f ∥ 2 2 ≤ ∥ f -f 1 ∥ 2 2 + ∥f 1 -f ∥ 2 2 ≤ α f -α(f 1 ) 2 2 + ∥f 1 -f ∥ 2 2 ≤ A ⊤ A -1 A ⊤ W (Y B -(f 1 ) B ) 2 2 + ∥f 1 -f ∥ 2 2 ≤λ max A ⊤ A -1 ∥A ⊤ W Y B -(f 1 ) B ∥ 2 2 + ∥f 1 -f ∥ 2 2 Denote g i = Y i -f 1 (i), we have E S ∥A ⊤ W g∥ 2 = r d i=1 E S   B j=1 s 2 j V 2 i (j)|g j | 2  Denote α i = s i * p i for j ∈ S where p j is the probability of node j being selected to query. SinceE S [s j V i (j)(Y j -f 1 (j))] =α j E S 1 p j V i (j)(Y j -f 1 (j)) =α j n l=1 E Y [V i (l)(Y l -f 1 (l))] =0 since V i ⊥ f 2 we have E S ∥A ⊤ W g∥ = B j=1 E S r d i=1 s 2 j V 2 i (j)|g j | 2 ≤sup j s j r d i=1 |V i (j)| 2 × B j=1 E S s j g 2 j =sup j s j r d i=1 |V i (j)| 2 × B j=1 α j E S 1 p j g 2 j =sup j s j r d i=1 |V i (j)| 2 × B j=1 α j × n l=1 E Y (Y l -f 1 (l)) 2 Notice that n l=1 E Y (Y l -f 1 (l)) 2 = n l=1 E Y (Y l -f (l)) 2 + n l=1 (f (l) -f 1 (l)) 2 = nσ 2 + ∥f -f 1 ∥ 2 2 Notice that f = U d0 U T d0 Xβ and f 1 = U d U T d f , then f -f 1 = U d ′ U T d ′ Xβ = i>d ⟨f , U i ⟩U i where U d ′ = (U d+1 , • • • , U d0 ). Therefore, ∥f -f 1 ∥ = i>d,i∈supp(f ) ⟨f , U i ⟩ 2 .We first state and then prove the following Lemma 1.Lemma A.1 For the output from Algorithm 1 with B query budgets, we haveEQUATIONλ(A ⊤ A) ∈ 1 2 × 1 1 + m √ δ C0 2 , 8 3 × 1 1 -m √ δ C0 2 with probability 1 - 2 C,where δ = r d CC 2 0 mB , and C 0 is a constant such that C 2 0 = (m) 2 + max(2, 16 d )m.Using Lemma 1 we haveE∥ f -f ∥ 2 2 ≤λ min A ⊤ A ×   B j=1 α j   × sup j∈S s j r d i=1 |V i (j)| 2 × n j=1 E Y (Y j -f 1 (j)) 2 + ∥f -f 1 ∥ 2 2 ≤2(1 + m √ δ C 0 ) 2 × 4 3 × 10 × CC 2 0 r d m × 1 B × n j=1 E Y (Y j -f 1 (j)) 2 + ∥f -f 1 ∥ 2 2 ≤O 2( r d t B ) + r d t B ) 3/2 + ( r d t B ) 2 × (nσ 2 + i>d,i∈supp(f ) ⟨U i , f ⟩ 2 ) + i>d,i∈supp(f ) ⟨U i , f ⟩ 2 ,with probability larger than 1 -2m t where t > 2m. In the following, we prove Lemma 1 which is based on Theorem 5.2 in [5] and Lemma 3.5 and 3.6 in [17] .In the following, we denote the accumulated covariance matrix in the j selection as A j , the potential function asΦ uj ,lj (A j ) = Tr[(u j I -A j ) -1 ]+Tr[(A j -l j I) -1 ], and R i (u, l, A) = v i (uI -A) -1 v T i + v i (A -lI) -1 v T i , where v i is the ith row of V. Notice that n i=1 R i = Φ u,l (A).At each iteration of algorithm 1, the ith node is selected as one of m candidates with p * i = Ri Φ . For the m candidates, we define the following probabilityq i =    1 -η if i has maximum ∆ i among m candidates η m -1 otherwisewhere 0 < η < 1. Notice that when η goes to 0, the q i approximate the step 3 in Algorithm 1. Therefore, the probability of node k being query isp k = P (select k) =P ( select k Q k |k in B m ) • P (k in B m ) = p * k × q k E 1 p k v k v ⊤ k =E Bm E Q k |Bm 1 P (select k) v k v ⊤ k =E Bm k∈Bm P (select k|k ∈ B m ) • 1 P (select k) v k v ⊤ k =E Bm k∈Bm 1 P (k ∈ B m ) v k v ⊤ k = Ω P (B m ) × k∈Bm 1 P (k ∈ B m ) v k v ⊤ k = Bm∈Ω k∈Bm P (B m | k ∈ B m ) • v k v ⊤ kwhere Ω denote all C m n possible candidate set with choosing m nodes from n nodes, P (B m | k ∈ B m ) denotes the probability of selecting m -1 nodes into B m conditioning on k ∈ B m . Denote Ω k as all possible size m candidate sets with node k always in the set. ThenE 1 p k v k v ⊤ k = n k=1   B k m-1 ⊂Ω k P (B m | k ∈ B m )   • v k v ⊤ k = n k=1 v k v ⊤ k = I ϵ ( R i )p k v k v ⊤ k = ϵ ( R i )p * k q k v k v ⊤ k = ϵ R k q k v k v ⊤ k ⪯ϵ(uI -A) 1 q k ≤ mϵ η (uI -A)where we use the fact vv T ⪯ (v T B -1 v)B for any semi-positive definite matrix B. In addition,EQUATIONEQUATIONDefine ϵ ′ = mϵ η , we show in the following that E Φ uj ,lj (A j ) ≤ Φ uj-1,lj-1 (A j-1 ). From (19) we haveΦ uj ,lj (A j ) ≤ Φ uj ,lj (A j-1 ) + w ⊤ j-1 (u j I -A j-1 ) -2 w j-1 1 -ϵ - w ⊤ j-1 (A j-1 -l j I) -2 w j-1 1 + ϵ 3 Define ∆ u = u j -u j-1 = ϵ (1-ϵ ′ ) Rj and ∆ l = l j -l j-1 = ϵ (1+ϵ ′ ) Rj . Notice that ∂ ∂u Tr(uI -A) -1 = -Tr(uI -A) -2 < 0 ∂ ∂l Tr(A -lI) -1 = Tr(A -lI) -2 < 0at each step based on the design of u j and l j . and Φ u,l (A) is convex in terms of u and l. From 3 , we haveΦ uj ,lj (A j ) ≤ Φ uj ,lj (A j-1 )+ 1 1 -ϵ ′ Tr (u j I -A j-1 ) -2 w j-1 w ⊤ j-1 - 1 1 + ϵ ′ Tr (A j-1 -l j I) -2 w j-1 w ⊤ j-1 then with E(w k w T k ) = ϵ Ri I E Φ uj ,lj (A j ) ≤ Φ uj ,lj (A j-1 ) + ϵ (1 -ϵ ′ ) R i Tr (u j I -A j-1 ) -2 - ϵ (1 + ϵ ′ ) R i Tr (A j-1 -l j I) -2 ≤ Φ uj ,lj (A j-1 ) + ∆ u Tr (u j I -A j-1 ) -2 -∆ l Tr (A j-1 -l j ) -2 Define f (t) = Tr (u j-1 + t • ∆ u )I -A j-1 -1 + Tr A j-1 -(l j-1 + ∆ l • t)I -1 then ∂f (t) ∂t = -∆ u Tr (u j-1 + t • ∆ u )I -A j-1 -2 + ∆ l Tr A j-1 -(l j-1 + ∆ l • t)I -2Since f (t) is convex, we haveEQUATIONThen plugin (22) , we haveE Φ uj ,lj (A j ) ≤ Φ uj-1,lj-1 (A j-1 )Notice that for selection∆ uj -∆ lj ∆ uj = ε t(1-ε ′ ) -ε t(1+ε ′ ) ε t(1-ε ′ ) = 1 (1-ε ′ ) -1 (1+ε ′ ) 1 (1-ε ′ ) ≤ 2ε ′where t = R i . We consider that the selection process stops when at the iterationk that u k -l k ≥ 8r d /ϵ. Notice u 0 = 2r d ε , l 0 = -2r d ε , when stop at u k -l k ⩾ 8r d ε , we have u k -l k u k = (u 0 -l 0 ) + k-1 j=0 ∆ uj -∆ lj u 0 + k-1 j=0 ∆ uj ≤ 4r d /ε + k-1 j=0 ∆ uj -∆ lj 2r d /ε + (2ε ′ ) -1 k-1 j=0 ∆ uj -∆ lj ≤ 4r d /ε + 4r d /ε 2r d /ε + (2ε ′ ) -1 4r d /ε = 8r d /ε 2r d 1 + 1 ε ′ /ε = 4 1 + 1 ε ′ ≤ 4ε ′ Then we have u k l k = 1 -u k -l k u k -1 ≤ 1 + 4 (ε ′ ). Notice that u k -l k ⩾ 8r d ε =⇒ k-1 j=0 ∆ uj -∆ lj ≥ 4r d ε . Consider at the jth selection ∆ uj -∆ lj = ϵ 1 -ϵ ′ - ϵ 1 + ϵ ′ 1 R i = ε Φ uj ,lj (A j ) , ϵ ′ = 2ϵϵ ′ (1 -ϵ ′ )(1 + ϵ ′ ) Then P (finish selection after B times selectionz vectors) ≥P   B-1 j=0 ε Φ uj ,lj (A j ) ≥ 4r d ϵ   =P   B-1 j=0 Φ -1 uj ,lj (A j ) ≥ 4r d εϵ   ≥P B 2 B-1 j=0 Φ uj ,lj (A j ) ≥ 4r d εϵ =P   B j=0 Φ uj ,lj (A j ) ≤ B 2 εϵ 4r d   , ≥1 - 4n Bε , ≥1 - 2r d B • m η • ϵ 2where we use the result that E Φ uj ,lj (A j ) ≤ Φ u0,l0 (A 0 ) by recursively using E Φ uj ,lj (A j ) ≤ Φ uj-1,lj-1 (A j-1 ) and the fact that Φ u0,l0 (A 0 ) = ϵ.We consider the following reparametrization:ϵ = √ δ C 0 , 0 < δ, mid = 2r d (1 -m 2 ϵ 2 )/(mϵ 2 ).For the jth selection, α j = ϵ Φj 1 mid . From previous result, we haveu k l k = 1 -u k -l k u k -1 ≤ 1 + 4 (ε ′ ) with probability 1 -2/C with δ = CC 2 0 ηr d mB . Notice that u k = u 0 + k j=1 ϵ (1-ϵ ′ )Φj and l k = l 0 + k j=1 ϵ (1+ϵ ′ )Φj , andu k + l k = k j=1 ϵ Φ j 1 1 -ϵ ′ + 1 1 + ϵ ′ Then if stop at kth selection Φ k ≥ 2r d u k -l k = 2r d (u k-1 -l k-1 ) + ϵ Φ k 1 1-ϵ ′ -1 1+ϵ ′ ≥ 2r d 8r d ϵ + ϵ Φ k 1 1-ϵ ′ -1 1+ϵ ′ Denote c = 1 1-ϵ ′ -1 1+ϵ ′ , then Φ k ≥ 1 4 ϵ -c 8 ϵ 2 . We find C 0 such that cϵ = 2ϵ ′ ϵ 1-(ϵ ′ ) 2 < 1 then Φ k ≥ ϵ Therefore, u k -l k = u k-1 -l k-1 + ϵ Φ k 1 1 -ϵ ′ - 1 1 + ϵ ′ ≤ 8r d ϵ + ϵ Φ k 1 1 -ϵ ′ - 1 1 + ϵ ′ ≤ 8r d ϵ + 8 1 1 -ϵ ′ - 1 1 + ϵ ′ = 8r d ϵ + 16ϵ ′ 1 -(ϵ ′ ) 2 Then we choose C 0 large such that 16ϵ ′ 1-(ϵ ′ ) 2 < r d ϵ ⇒ u k -l k ≤ 9r d ϵ .Given that ϵ ′ = m η ϵ and ϵ = √ δ C0 , we choose appropriate C 0 to satisfy previous requirement on ϵ and ϵ ′ as         2ϵϵ ′ < 1 -(ϵ ′ ) 2 16ϵ ′ 1 -(ϵ ′ ) 2 < r d ϵ ϵ ′ < 1 Therefore, we choose C 0 such that C 2 0 > m η 2 + max(2, 16 r d ) × m η . Notice that u k -l k = k j=1 ϵ Φ j 1 1 -ϵ ′ - 1 1 + ϵ ′ ≥ 4r d ϵand mid is defined as mid= 4d ϵ 1 1-ϵ ′ -1 1+ϵ ′ , then k j=1 ϵ Φj ≥ mid. Also, k-1 j=1 ϵ Φ j ≤ mid ⇒ mid > k j=1 ϵ Φ j -8 > ϵ Φ j - 4ϵϵ ′ r d (1 -(ϵ ′ ) 2 ) k j=1 ϵ Φ j = 1 - 4ϵϵ ′ r d (1 -(ϵ ′ ) 2 ) k j=1 ϵ Φ j which implies mid ∈ 1 - 4ϵϵ ′ r d (1 -(ϵ ′ ) 2 ) , 1 • m j=1 ϵ Φ j = 1 - 4ϵϵ ′ r d (1 -(ϵ ′ ) 2 ) , 1 • u k + l k 1 1-ϵ ′ + 1 1+ϵ ′Notice that for the design matrix A in (18), we have 1 √ mid A = A k where A k is the accumulated covariance matrix when the query process stops at the kthe selection. Therefore, the eigenvalues ofA satisfy λ(A T A) = 1 mid λ(A T k A k ) ∈ l k mid , u k mid . Then l k mid , u k mid ⊂ l k u k +l k 1 1-ϵ ′ + 1 1+ϵ ′ , u k 1 - 4ϵϵ ′ r d (1-(ϵ ′ ) 2 ) • u k +l k 1 1-ϵ ′ + 1 1+ϵ ′Given that with high probability, 1 -4ϵ ′ ≤ u k l k ≤ 1 + 4ϵ ′ . Then for the lower bound,l k u k +l k 1 1-ϵ ′ + 1 1+ϵ ′ ≥ 1 (1 -(ϵ ′ ) 2 )(1 + 2ϵ ′ ) > 1 (1 + ϵ ′ )(1 + 2ϵ ′ ) > 1 2 × 1 (1 + ϵ ′ ) 2 = 1 2 1 (1 + m √ δ/(ηC 0 )) 2and upper boundu k 1 - 4ϵϵ ′ r d (1-(ϵ ′ ) 2 ) • u k +l k 1 1-ϵ ′ + 1 1+ϵ ′ ≤ 1 + 4ϵ ′ (1 + 2ϵ ′ )(1 -(ϵ ′ ) 2 ) -(1 + 2ϵ ′ ) 4ϵϵ ′ r d ≤ 4 3 × 1 + 4ϵ ′ (1 + 2ϵ)(1 -(ϵ ′ ) 2 ) , given 4ϵϵ ′ r d > 1 4 (1 -(ϵ ′ ) 2 ) < 8 3 × 1 1 -(ϵ ′ ) 2 < 8 3 1 1 -(m √ δ/(ηC 0 )) 2 .Then with probability larger than 1 -2 C , we haveEQUATIONFinally, check sup j∈S s j r d i=1 |V i (j)| 2 at the kth selection sup j∈S s j r d i=1 |V i (j)| 2 =sup j∈S ϵ Φ k • 1 mid × Φ k R j × r d i=1 |V i (j)| 2 = ϵ mid • sup j r d j=1 |V i (j)| 2 R j ≤ ϵ mid • 1 1 u k -l k + 1 u k -l k = ϵ mid × u k -l k 2 ≤ ϵ mid × 9 • r d ϵ 2 = 4.5r d mid ≤ 4.5r d 2r d (1-(ϵ ′ ) 2 ) ϵϵ ′ = 2.25 × ϵϵ ′ 1 -(ϵ ′ ) 2 ≤ 2.25 × 4δ = 10δThen we finish the proof of Lemma 1.In the representative sampling stage, the computational complexity of calculating the sampling probability is O(n). We then sample m nodes to formulate a candidate set B m , where the complexity of sampling m variables from a discrete probability distribution is O(m) [31] . Consequently, the complexity of the representative learning stage is O(n + m).In the informative selection stage, we calculate the information gain ∆ i for each node. This involves obtaining the eigenvector corresponding to the smallest non-zero eigenvalue of the projected graph Laplacian matrix, with a complexity of O(n 3 ) due to the singular value decomposition (SVD) operation. Subsequently, we compute ∆ i for each node in the candidate set B m based on their loadings on the eigenvector, which incurs an additional computational cost of O(mn). Therefore, the total complexity of our biased sampling method is O(n + m + nm + n 3 ). Given a node label query budget B, the overall computational cost becomes O(B n + m + nm + n 3 ) .When the dimension of node covariates p ≪ n, we can replace the SVD operation with the Lanczos algorithm to accelerate the informative selection stage. The Lanczos algorithm is designed to 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(kn 2 ) [14] . As a result, the complexity of the proposed biased sampling method reduces to O(pn 2 ). This is comparable to GNN-based active learning methods, as GNNs and their variations generally have a complexity of O(pn 2 ) per training update [6, 37] .Although our theoretical analysis is developed for node regression tasks, the proposed query strategy and graph signal recovery procedure are also applicable to classification tasks. Consider a Kclass classification problem, where the response on each node i is given by f (i) ∈ 1, 2, . . . , K. We introduce a dummy membership vector (Y 1 (i), . . . , Y K (i)), where Y c (i) = 1 if f (i) = c and Y c (i) = 0 otherwise. For each class c ∈ {1, 2, . . . , K}, we first estimate βc based on (14) with the training data { Xi• , Y c (i), s i } i∈S , and then compute the score for class c as fc = X βc . The label of an unqueried node j is assigned as f (j) = arg max 1≤c≤K { f1 (j), f2 (j), • • • , fK (j)}. Notice that the above score-based classifier is equivalent to the softmax classifier: Theorem 4.1 is derived using first-order matrix perturbation theory [2] on the Laplacian matrix L.EQUATIONIn 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 L S c . This assumption simplifies the analysis and the results by focusing on the perturbation of L S c , where L S c is the reduced Laplacian matrix with zero entries in the rows and columns indexed by S.The analysis can be naturally extended to the general setting by replacing L S c with P(1 S c )LP(1 S c ), where P(t) is the projection operator defined in Section 3.2. Moreover, under the assumption on the node covariates, the information gain ∆ i exhibits an explicit dependence on the network statistics, 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 d min is larger and η 0 , η 1 are smaller. Specifically, d min reflects the connectedness of the network, where a betterconnected network facilitates the propagation of label information and enhances the informativeness of a node's label for other nodes. A smaller η 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 η 0 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 η 0 is small. Additionally, the size of the candidate set m should be sufficiently large to ensure that informative nodes are included in B m .The RHS of (15) 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 H ω (X, A).The bias term in Theorem 4.2 can be further controlled if the true signal f exhibits decaying or zero weights on high-frequency network components. In addition to r d , the size of the candidate set m also influences the probability of controlling the generalization error. A small m places greater emphasis 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 MSE, the query complexity of our method is O(d), whereas random sampling incurs a complexity of O( d log d), where d > d. Our method outperforms random sampling in two key aspects: (1) The information-based 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 in a logarithmic factor reduction compared to random sampling.When calculating node-wise informativeness in (7) , we can enhance computational efficiency by avoiding the inversion of D(t). When t is in the neighborhood of 1 S c , we can approximate:P(t) ≈ D(t)X S c (X T S c X S c ) -1 X T S c D(t) = D(t)Z S c Z T S c D(t), where X S c = ((X 1 ) S c , • • • , (X p ) S c ) and Z S c = X S c (X T S c X S c ) -1/2. Then, the node-wise informativeness can be explicitly expressed as:EQUATIONWe find that this approximation yields very similar empirical performance compared to the exact formulation in (7) . 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, we can run the biased sampling procedure multiple times with different values of m 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 is 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] . Real-world networks For the proposed method and all baselines, we train a 2-layer SGC model for a 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 -2 and weight decay as 10 -4 .In Figure 2 , 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 scale-free structure in BA. 4 : A description of all datasets used in Section 5 and the hyperparameter settings for each dataset. We set ϵ = 0.001 for all networks. For heterophilic networks, we combine the eigenvectors corresponding to the d smallest and d largest eigenvalues.To gain deeper insights into the respective roles of representative sampling and informative selection in the proposed algorithm, we conduct additional experiments on a 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 is not a 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. In 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 a standard forward selection approach.As shown in Section 3.4, the representative sampling in steps 1 and 2 of Algorithm 1 is essential to control the condition number of the design matrix and, consequently, the prediction error given noisy network data. We illustrate in Figure 3a the condition number λmax( XT S W S XS ) λmin( XT S W S XS ) using the proposed method, and compare with the one using random selection. With m = 200, the proposed algorithm achieve a significantly lower condition number than random selection, especially when the number of query is small. In the Citeseer dataset, we investigate the prediction performance of Algorithm 1 when removing steps 1 and 2, i.e., setting the candidate set B m = S c t-1 for the t th selection. Figure 3b shows that, with representative sampling, the Macro-F1 score is consistently higher, with a 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 in improving the robustness of our query strategy to data noise.In addition, we examine the ability of the proposed method to 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 as 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.The implementation code for the proposed algorithm is available at github.com/Yuanchen-Wu/RobustActiveLearning/.  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - Missing connections to related theoretical literature on active learning on graphs. E.g. [1, 2]
[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.
[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.
- Presentation can be made clearer, see suggestions below.
questions: 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$"?
- Can you shed more light on the trade-off between informativeness and representativeness? Is there a standard way to quantify these?
- "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).
- 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?
- Presentation of the greedy algorithm can be improved say using an algobox.
- Line 127: prescence or abscence 
- Could you elaborate on the size of $m$ needed in Theorem 2? Can this be empirically estimated?
- What is the running time complexity for the proposed algorithm?
- Is it possible to empirically verify the tightness/looseness of the theoretical bounds?
- Repeated references [2] and [3]
limitations: limitations: Authors should elaborate further on the limitations, e.g. assumptions needed for the theoretical results.
paper_summary: paper_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.
strength_weakness: strength_weakness: - How does the proposed method perform on networks with varying levels of homophily and heterophily? Can it adapt to different types of network structures?
- Can the method be extended to online active learning scenarios, where nodes are queried in a sequential manner rather than in batches?
- 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?
- 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?

[1] Focus on Informative Graphs! Semi-supervised Active Learning for Graph-level Classification. Pattern Recognition 2024
questions: questions: See above.
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
- 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.

Minor remarks:
- 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.
- line 89: undefined symbol $\mathcal{B}$
questions: questions: - What is the computational efficiency of the proposed method?
- 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?
- 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: 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).
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

[1] Partition-based active learning for graph neural networks. TMLR 2023.
questions: questions: Please provide detailed experimental results for additional datasets.
limitations: limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.

Comments: title: Thanks for the comment
Thanks for the response and I will maintain my score.
Thank you for the feedback!
Response to AC's comments
Response to rebuttal
Follow-up on our response to your feedback
technical questions
Follow-up on our response to your feedback
Thank you for raising the score!
Thank you for your response!
comment: We thank the reviewer very much for the feedback. Please do let us know if there is any effect we can futher make to address your concerns. Thank you!
Thanks for the response and I will maintain my score.
We appreciate your valuable feedback, which has greatly improved our paper. If you have any further comments or questions, we would be more than happy to discuss and provide clarification.
We appreciate AC's insightful theoretical questions! The point-by-point responses are as follows:

**Q1** Denote the eigenvalue distribution $F(\omega)= \frac{1}{n}\sum_{i=1}^n\mathbf{1}(\lambda_i \leq \omega) $ and the eigenvector space $\mathbf{U_d} = \text{Span}(U_1,\cdots,U_d)$, where ${(\lambda_i)}_{i=1}^{n}$, and ${(U_i)}$ are eigenvalues and $d$-leading eigenvectors of the normalized graph laplacian. Assuming the frequency of $\mathbf{f}$ is lower than $\omega_0$, 
we have $\mathbf{f}\in \mathbf{U}_d$ with $d = \lceil nF(\omega_0) \rceil$. Wlog, we assume $r_d = d$ in Theorem 3, i.e, $\mathbf{f}$ has component on each $U_i,i=1,\cdots,d$. With MSE $\frac{1}{n}\mathbf{E}\| \hat{\mathbf{f}} - \mathbf{f}\|_2^2$ fixed, the label complexity of our method is $O(d)$, while that of passive learning is $O(\tilde{d}\log \tilde{d})$ [1] with $\tilde{d} = \lceil nF\big(\frac{n}{\mathcal{B}}F^{-1}(\frac{d}{n})\big)\rceil$ where $\mathcal{B}<n$ is the number of query. Notice that $\tilde{d}>d$ due to the monotonicity of $F(\cdot)$ and $\tilde{d} \rightarrow d$ as $\mathcal{B}$ increases. Our method improves in two aspects: (1) the information selection identifies $\mathbf{f}$ via $O(d)$ queries, and passive learning uses $O(\tilde{d})$ queries, though this improvement decreases as $\mathcal{B}$ increases. (2) Our method improves by a log factor compared to passive learning via actively controlling the condition number of the covariate matrix, therefore the estimation variance.

**Q2** In the real world, data labels aren’t always accurate/reliable. In this paper, we introduce label noise via a probabilistic model $Y_i = \mathbf{f}(i) + \epsilon_i$, where $Y_i$ and $\mathbf{f}(i)$ are the queried and true label on the $i$th node, and $(\epsilon_i)_{i=1}^n$ are independent errors satisfying $\mathbf{E}(\epsilon_i) = 0$ and $\mathbf{Var}(\epsilon_i) = \sigma^2$. Our noise model generalizes to different label types in applications. For continuous labels $Y_i$, one can set $\epsilon_i \sim \text{Normal}(0,\sigma^2)$. For binary label with $\mathbf{f}(i) = -1 \ \text{or} 1$, the typical noise model is $ Y_i = \mathbf{f}(i)$ with prob. $p>0.5$ and $ Y_i = - \mathbf{f}(i)$ with $1-p$. The binary noise model can be reparameterized via our noise model as $Y_i = \text{sign}(Y^*_i)$ where $Y^*_i = \mathbf{f}(i) + \epsilon_i$. The binary $\epsilon_i = 2\mathbf{f}(i)(1-p)$ with prob. $p$ and $\epsilon_i = -2\mathbf{f}(i)p$ with $1- p$, and $\mathbf{E}(\epsilon_i) = 0$ and $\mathbf{Var}(\epsilon_i) = 4p(1-p)$. Similarly, our noise model also accommodates multi-class labels via one-vs-other reparameterization. While most literature consider noise level $\sigma^2$ as constant, our method theoretically guarantees recovery as long as noise level $\sigma^2 = O(\mathcal{B}^\eta)$ with $\eta<1$. This result is useful when human labelling errors increase with workload. Additionally, our node selection strategy is invulnerable to label noise due to the offline nature, and our graph function space alleviates high-frequency noise in node features $\mathbf{X}$ due to network smoothing.

**Q3** For a random graph $G(n,p)$, one has both lower and upper bounds on the node degree with high probability. Specifically, with probability greater than $1 - \exp\big(-np(c-1)^2\big)$, the maximum node degree $d_{max} \leq cnp$ with constant $c>1$. Given $np \rightarrow \infty$, the difference in information gain between the proposed method and random sampling can be simplified as 
$$ \mathbf{E}(\Delta) - \mathbf{E}(\Delta_R) >  O(\frac{1}{ c^3 p^2 n^2}) -\frac{1}{n},$$
with probability larger than $1 - \exp\big(-np(c-1)^2\big)$. Therefore, the proposed method achieves larger information gain under the network sparsity regime $p = O(n^{-1/2}$), covering a broad range of real networks. 

**Q4** Following the same definition as in Q1, and assuming that the frequency of $\mathbf{f}$ is lower than $\omega$, the generalization error in Theorem 3 is 
$$  \frac{1}{n}\mathbf{E}\| \hat{\mathbf{f}} - \mathbf{f}\|_2^2 \leq O\Big(\frac{\text{rank}(\mathbf{U}_d^T\mathbf{X})}{\mathcal{B}}\Big),$$
where $d = nF(\omega)$, $\mathcal{B}$ is the number of queries, and $\mathbf{X}$ is node covariate matrix. With a fixed complexity of $\mathbf{f}$, the MSE decays at a rate of $\frac{1}{\mathcal{B}}$. The network topology affects the convergence rate through both the size of eigenvector space ($d$) and the alignment between two column spaces ($\mathbf{U}_d^T\mathbf{X}$). For illustration, we can obtain a looser bound as $O\Big(\frac{nF(\omega)}{\mathcal{B}}\Big)$. For random graph, the eigenvalue distribution of graph laplacian $F(\omega;n,p)$ can be analytically represented as the convolution of the standard normal distribution and the Wigner’s semi-circular distribution [2]. 

[1] Randomized algorithms for matrices and data. Found. and Trend. in Mach. Learn. (2011)\
[2] Spectral distributions of adjacency and Laplacian matrices of random graphs. Ann. of App. Prob. (2010)
I would like to thank the author's for their detailed answers and for the additional experiments. After carefully reading the responses I have decided to maintain my score.
We sincerely appreciate the time and effort you've put into reviewing our work, and we are truly thankful for your insightful, valuable, and encouraging feedback. 
In response to your constructive suggestions on numerical experiments, we have conducted additional experiments on real-world networks exhibiting different levels of homophily and heterophily (Table 1), as well as on synthetic networks with different topologies, including community structure, scale-free properties, and small-world properties (Figure 4). 

As a further supplement to Figure 4, we perform the proposed method with SoTA offline active learning methods on Erdős–Rényi random graph since many social and biological networks can be modeled via this model. The prediction MSE from different methods on **Erdős–Rényi graph** (n=100, p=0.25) with varying response noise are illustrated in the following table: 

| Method | $\sigma^2$=0.5 | $\sigma^2$=0.6 | $\sigma^2$=0.7 | $\sigma^2$=0.8 | $\sigma^2$=0.9 | $\sigma^2$=1.0 |
|------------|-------------------|-------------------|-------------------|-------------------|-------------------|-------------------|
| D-Optimal  | 0.48 &plusmn;  0.03            | 0.69  &plusmn;  0.04            | 0.93&plusmn;0.06                 | 1.22 &plusmn; 0.08               |  1.54&plusmn;      0.1       | 1.9 &plusmn; 0.12         |
| SPA        | 0.61 &plusmn;  0.05          | 0.88 &plusmn;  0.08    | 1.2 &plusmn;  0.1 |1.57 &plusmn;0.13 |1.99 &plusmn;  0.17 | 2.46 &plusmn;  0.21   |
| RIM       | 0.49 &plusmn;  0.02          | 0.7 &plusmn;  0.02    |0.95 &plusmn;  0.03 |1.24 &plusmn;0.04 |1.57&plusmn;  0.06| 1.94 &plusmn;  0.07   |
| GPT        |0.58 &plusmn;  0.04          | 0.83 &plusmn;  0.06    |1.13 &plusmn;  0.08 |1.48 &plusmn;0.1 |1.87&plusmn;  0.14| 2.31 &plusmn;  0.17 |
| Proposed   | **0.45**&plusmn;  0.01|**0.65**&plusmn;  0.02 |**0.89**&plusmn;  0.03|**1.16**&plusmn;  0.03|**1.47**&plusmn;  0.04|**1.81**&plusmn;  0.05|

Consistent with the results on other network topologies in figure 4, our method still outperforms other competing methods on Erdős–Rényi graph. 

Additionally, we discussed the computational overhead of the proposed method in details, and empirically demonstrated the scalability of our sampling algorithm on large-scale networks (Table 3). 

We sincerely hope our response adequately addresses your concerns and aids in the evaluation of our work. We look forward to further discussions with you.
Dear Authors and Reviewers,

Based on the current ratings, the paper is at borderline. Since the discussion with authors will end soon, I hope the authors or reviewers could clarify some of my questions so that I can make informed decision. My questions will be mostly theoretical, given the subject of the work.

1. The paper claims using active learning techniques to save labels. What is the obtained label complexity and how does it improve upon passive learning?

2. The paper claims robustness. How is the noise model related to applications and what is the theoretical noise tolerance?

3. In Theorem 2, it is shown that E(Delta) - E(Delta_R) is lower bounded by some quantity. Can you showcase how the lower bound scales under simple assumptions, say the random graph G(n, p) where there are n nodes and each pair is connected with probability p independently?

4. When does the generalization error in Theorem 3 vanish with respect to the sample size, at what rate? Again, can you show concrete results under the G(n, p) model?

Thanks,
Area Chair
We are very grateful for the time and effort you have devoted to reviewing our work, and we deeply appreciate your insightful, valuable, and encouraging comments.

In response to your questions, we conducted additional experiments to compare the proposed method with SoTA offline graph-based active learning methods (RIM, GPT, SPA, FeatProp), and online methods (AGE, IGP). The numerical comparisons are conducted on networks with various topologies and response noise (Figure 4), different levels of homophily (Table 1), and larger scales (Table 2). In these experiments, the performance of the proposed method is either best or close to the best one. In addition, we follow your suggestion to add error bars when presenting the results. 

We discuss the optimality of the generalization bound in Theorem 3 and illustrate the tightness via simulation in Figure 1. We also provide a detailed discussion of the computational complexity of the proposed method, which is at $\mathcal{O}(pn^2)$ where $n$ and $p$ are the number of nodes and node features, respectively.

We sincerely hope our response adequately addresses your concerns and will definitely incorporate these changes in the revised version. We look forward to your feedback with great anticipation.
We appreciate your recognition of the updated results and the improved score. If there are any other comments or questions, we would be pleased to discuss and clarify further!
We appreciate your valuable feedback, which has greatly improved our paper. If you have any further comments or questions, we would be more than happy to discuss and provide clarification.
Thank you for the detailed response. I raised my score to 5.
Thank you for the detailed response. I do not have further questions, and retain my current score.