No Change, No Gain: Empowering Graph Neural Networks with Expected Model Change Maximization for Active Learning
Authors: Zixing Song
Yifei Zhang
Irwin King
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Graph Neural Networks
Expected Model Change Maximization

Abstract: Graph Neural Networks (GNNs) are crucial for machine learning applications with graph-structured data, but their success depends on sufficient labeled data. We present a novel active learning (AL) method for GNNs, extending the Expected Model Change Maximization (EMCM) principle to improve prediction performance on unlabeled data. By presenting a Bayesian interpretation for the node embeddings generated by GNNs under the semi-supervised setting, we efficiently compute the closed-form EMCM acquisition function as the selection criterion for AL without re-training. Our method establishes a direct connection with expected prediction error minimization, offering theoretical guarantees for AL performance. Experiments demonstrate our method's effectiveness compared to existing approaches, in terms of both accuracy and efficiency.

No Change, No Gain: Empowering Graph Neural Networks with Expected Model Change Maximization for Active Learning
Zixing Song
Yifei Zhang
The Chinese University of Hong Kong New Territories, Hong Kong SAR zxsong0cse. cuhk. edu. hk
The Chinese University Hong Kong New Territories, Hong Kong SAR yfzhangocse. cuhk. edu .hk
Irwin King
The Chinese University of Hong Kong New Territories, Hong Kong SAR kingScse. cuhk. edu. hk
Abstract
Graph Neural Networks (GNNs) are crucial for machine learning applications with graph-structured data, but their success depends on sufficient labeled data. We present a novel active learning (AL) method for GNNs, extending the Ex- pected Model Change Maximization (EMCM) principle to improve prediction performance on unlabeled data. By presenting a Bayesian interpretation for the node embeddings generated by GNNs under the semi-supervised setting, we ef- ficiently compute the closed-form EMCM acquisition function as the selection criterion for AL without re-training. Our method establishes direct connection with expected prediction error minimization, offering theoretical guarantees for AI. performance. Experiments demonstrate our method's effectiveness compared existing approaches, in terms of both accuracy and efficiency.
1
Introduction
Graph Neural Networks (GNNs) have gained significant recognition in machine learning applications, particularly for graph-structured data [71, 32, 68]. Nevertheless, their efficacy is predominantly contingent the availability of ample labeled data. The labeling process, often demanding human intervention and domain knowledge, poses high costs real-world applications. Active Learning (AL) presents compelling solution to mitigate the issue of limited labeled data [1]. AL boosts the performance of passive learning by iteratively training a model based on the current set of labeled nodes and selecting the query nodes to expand this set based the different query heuristics the designed acquisition function. The main idea is to identify the most informative nodes for the oracle to annotate, thereby enhancing test node predictions upon their addition to the training set.
Recently, active learning methods for graph-structured data have seen an upsurge, adapting general active learning techniques to accommodate the non-IID nature of graphs [88, 89, 90]. Predominantly, these methods employ heuristic approaches, selecting nodes based on rudimentary measures such as uncertainty and influence score. While efficient, these strategies lack direct correlation with expected prediction performance on remaining unlabeled nodes-our primary concern. Hence, We advocate for performance-basee active learning methods, selecting nodes that directly optimize anticipated model performance [o],To balance efficiency, we employ the Expected Model Change Maximization
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(EMCM) algorithm [6, 7] from general active learning. EMCM chooses nodes maximizing expected model change in parameters or predictions, serving as a surrogate for expected prediction error.
Implementing the FMCM principle in GNNs is both challenging and meaningful. First, the acquisition function for EMCM calculates the expected model change following the addition of a single labeled node, without the need for re-training. Hence, a Bayesian probabilistic model is preferred in AL [2]. This approach allows for efficient updating of posterior belief's about the model's parameters or predictions upon introducing a new labeled node, aligning perfectly with performance-basse methods like EMCM. However, conventional GNNs lack Bayesian interpretation, while Bayesian GNNs impose significant computational demands, rendering precise approximation of the expected model change without re-training practically impossible. Therefore, a lightweight Bayesian probabílistic learning framework could enable the application of EMCM on graphs. Second, the direct adaptation of EMCM for GNNs, despite its computational advantages over other performance- based methods, remains impractical due to the large number of nodes, which is common in real-world cases. Third, a deep connection can be established between the EMCM method on graphs and the expected prediction error, offering a theoretical guarantee regarding the potentially optimal AL performance.
In light of these insights, we are the first extend the EMCM principle to GNNs, contributing in the following ways. First, we revisit the training process of the Simplified Graph Convolution (SGC) model [68] for the semi comi-supervised node classification as an example to obtain an equivalent view of a bi-level optimization problem. This motivates us to propose regularized single-level optimization learning framework that possesses a clear Bayesian interpretation. Second, we derive the posterior mean and variance of the node embeddings projected onto the truncated graph spectral subspace via the Laplace approximation. This enables the efficient computation of the acquisition function of EMCM for graphs through closed-form solution. Third, we provide theoretical insights into the proposed method, essentially equating to the selection of the node that directly minimizes the expected prediction errors of the remaining unlabeled nodes, assuming its addition to the training set. This theoretical interpretation aligns with the ultimate goal of AL. Fourth, We perform comprehensive experiments across several datasets, demonstrating the efficacy and efficiency of our proposed method.
2 Preliminary
2.1 Problem Formulation
We consider graph 9 EV,E) with |V| n nodes. Node feature vectors are represented as 2; RRd aggregated into a node feature matrix X [=T,.... _=]]] E Raxd The adjacency matrix of g is given as A E (0, 1 j (A E Rux* if the graph is weighted), aligned with edge set E. Assume there exists labeling oracle that can map each node (i V (I.... .n)) its ground-truth one-hot label vector y, E 13. c is the number of classes. The node set V is partitioned into the labeled node set Vi (V) = ni) and the unlabeled node set V., (V.l n.). At first, only the ground-truth labels of labeled nodes {y,jiev, are revealed to the learning model.
We investigate the bosl-based active learning setting on the aforementioned graph (Appendix (D.1)).
The learning model initially undergoes standard training on the labeled set Vi, hyr Subsequently, it identifies query node set V, from V., (V, C V.)) and solicits the labeling oracle for associated labels. Following this, the labeled and unlabeled sets are updated (V-- + Uy Vn < V. VVy). This training cycle and query node selection process repeats until the labeling budget B is depleted (Mi = nı + B). We distinguish between sequential active learning, where one node is selected to query the oracle (12y 1), and batch active learning, where batch of b nodes is chosen (V,1 = be E N+). The primary objective is to deduce the soft labels of nodes within the unlabeled set (ū.hev. (Ú, E [0, 1J9), utilizing the labeling oracle under a total labeling budget B.
More specifically, in each query node selection step under the transductive setting, we aim to solve Eq. (1) to choose the most informative node(s) and minimize the expected prediction error on the remaining unlabeled nodes. Here, E: Re x R + R- significs the selected loss function.
arg min I 1,-1V,1=6
(1)
2

---

2.2 Graph Neural Networks for Semi-supervised Node Classification
Graph Neural Networks (GNNs) excel in learning representations for graph-structured data [71, 62, 10, 57, 40, 95, 43, 92, 11, 61, 94, 59, 82, 60, 58, 39, 93, 9]. Among them, the Graph Convolutional Networks (GCN) [32] model is the most representative method. Considering the GCN or other GNN models for the node classification task under the semi-supervised setting, there are main steps during one iteration: (1) Forward pass that fuses both node features X and structure information into the low-dimensional representation node embeddings U(@) E RRe (before the softmax function) with the training parameters O and (2) Backward pass that updates è through gradient decent according to the training loss function over all labeled nodes as mine Eiev, (()( y:). Here, (,))) denotes the i-th row of (().. Typically, 2(.--) set as the cross-entropy loss after applying the Softmax function (() on node embedding (,))). Different GNNs mainly have different designs in the forward pass, but the backward pass remains the same in general. For a K -llayer GCN, we (o(A((..<(AXG)))) ((XO()) O ()( (K-1), Here A A ++I represents the adjacency matrix with the added self-loop and D I with the diagonal degree matrix D = diag(d), dd,) where dj = Σ, Aij. The normalized adjacency matrix is
optimize the training loss such that U( Å (
Á A AD 1/2, We denote e { 1-1 Note that GCN conducts linear transformation and non- linearity activation o(-) repeatedly. SGC [68] reduces this excess complexity by removing non-linearities and collapsing training parameters @ between consecutive layers. Similarly, a K-
layer SGC also optimizes the training loss such that the node embedding matrix U(O) is fixed as U(O)= XOo.
2.3 General Active Learning and Active Learning on Graphs
Active Learning (AL) [55] selects the most "informative" samples for querying, falling into three cat- egories: uncertainty-based representativeness-baas bbsed,, and performance based methods. Uncertainty- based methods target the most uncertain instances [83, 101, 50], using criteria like entropy and margin. Techniques like Query by Disagreement (QBD) and Query by Committee (QBC) [56, 16, 52] also reside here, employing uncertainty sampling reduce version space. Representativeness-bnn methods select samples best representing the input distribution, using methods such as density- weighting [14, 46, 27, 28] and clustering [49, 13, 72]. Performance-based methods directly optimize informativeness via Eq. (1) or surrogates, considering the impact of revealing an instance's 's label on future outcomes. Techniques like Expected Error Reduction (EER) [53], Expected Variance Reduction (EVR) [54], and Expected Model Change Maximization (EMCM) [6] are examples.
There is recent surging trend to explore AL strategies on graph-structured data. It is unsuitable to directly apply general AL techniques to GNNs since the nodes are not i.i.d. but linked with edges such that connected nodes tend to have the same label. AGE [4] and ANRMAB [18] incorporate node embedding density and PageRank centrality into their node selection. GEEM [51] adapts the Expected Error Reduction (EER) method for graphs, while RIM [89] accounts for noisy oracles in node labeling. Furthermore, ALG [88] optimizes the effectiveness of all nodes influenced by GNNs, and IGP [90] maximizes information gain propagation. Detailed reviews are found in Appendix B.
2.4 Motivations and Challenges
2.4.1 Bayesian Probabilistic Interpretations
Active learning strategies for graphs often directly utilize GCN or other GNN models as their back- bone [4. 88, 89, 90, 37], capitalizing on their exemplary representation learning abilities. However, under semi-supervised settings, these models typically lack a Bayesian probabilistic interpretation, fundamental aspect of AL that quantifies uncertainty for uncertainty-based methods and lays the groundwork for performance-basee posterior beliefs about the model parameters or predictions, assuming if new labeled data becomes available. Relying on GCN or GNN models without Bayesian interpretations may lead to inefficient sample selection and hinder learning progress. Therefore, integrating a Bayesian probabilistic inter- pretation within the GNN framework is desirable enhancement to active learning methodologies. Existing Bayesian GNNs provide dell-defined Bayesian interpretations [96, 24), yet they often come with significant computational costs. This renders them impractical for active learning environments,
methods, which incorporate prior knowledge and update the
3

---

where model re- re-training is imperative after each query set selection. To address these challenges, we aim introduce a lightweight, general Bayesian learning framework for GNN models. This will facilitate subsequent query node set selection by enabling rigorous, informed decision-making [17].
2.4.2 Efficient Computation
While numerous existing graph active learning methods extend uncertainty-based or representativeness--bae based methods for their simplicity and efficiency (Table 6 in Appendix B B.2), these approaches can be sensitive outliers and largely reliant on prerequisite density estimation functions or clustering algorithms. We instead advocate for performance-basee methods, which directly examine the potential impact on the model should an unlabeled node's label be revealed. Well-established methods such as EER [53] and EVR [54] and their graph-based adaptations [51] I are notorious for their extremely high computational overhead. As an alternative, we concentrate on the EMCM concept for AL on graphs. This approach selects nodes that yield the maximum expected model change, striking a balance between theoretical interpretations and computational costs. Our proposed general Bayesian learning framework for GNN models enables efficient computation of expected model changes using closed-form solutions. For graphs with an exceptionally large number of nodes, we further employ spectral approximation technique to curtail computational costs.
2.4.3 Solid Theoretical Guarantees
significant limitation of most current AL techniques for graphs the absence of theoretical connections with the expected prediction errors in Eq. (I), the ultimate goal in AL. CSAL [65] offers an in-depth theoretical analysis of label complexity within the context of AL on graphs, but it only verifies the existence of such an algorithm without presenting concrete implementation. This gap between theory and practice hinders the direct applicability of CSAL. To deploy AL algorithms in real-world situations, it is crucial to devise methods rooted in rigorous theoretical foundations that address this limitation, thereby enabling more efficient learning with fewer labeled examples.
3
Methodology
Our starting point is to propose Bayesian probabilistic learning framework for semi-supervised node classification task based on GNNs. Instead of following the existing literature [88, 90, 37] that use GNNs directly as the backbones for graph AL, our Bayesian probabilistic learning framework naturally supports the dynamic process of AL and allows for seamless updates of the model as new labeled data become available, thus eliminating the need for full model re-training during node selection. This key advantage of our Bayesian probabilistic learning framework paves the way for efficient and interpretable design of our subsequent acquisition function. Following the principle of Expected Model Change Maximization (EMCM) [6] general AL. we can adjust the likelihood and efficiently update posterior beliefs about the expected change in model parameters, assuming the label of a candidate node from the pool becomes available. More discussions are found Appendix
3.1 A Bayesian Probabilistic Learning Framework for GNNs under Semi-supervised Setting
3.1.1 Optimization View of SGC
We choose the SGC model [68] as an example for derivation and present a Bayesian probabilistic learning framework for the semi-supervised node classification. Recall that in Sec. 2.2. SGC aims to solve the following optimization problem Eq. (2) for semi-supervised node classification.
Σ ((S(U,())) v.), s.t. U()) = A xe.
min b
The objective function in Eq. (2) characterizes the backpropagation process, while the constraint in Eq. (2) describes forward propagation. Different GNNs typically exhibit unique forms of node embeddings U()) ) in Eq. (2). Notably, several recent studies [42, 102] have focused on unifying the forward pass of GNNs within an optimization framework, but these approaches neglect the backward pass for GNN training. Some research works integrate label information into the unifying framework for GNNs [84, 74], yet none them provide clear Bayesian interpretations. However, we can still transform the constraint in Eq. (2) into another optimization subproblem [102] based on Theorem 3.1.

---

Theorem 3.1. The forward pass of K-layer SGC, U()) xex optimizes the following
problem by performing K steps of gradient descent:
θ arg arg min Tr(UTLU), s.t. U = X6.
(0) - and L I- A is the normalized Laplacian matrix. Then,
Here, θ is initialized as
1-A
U()) = x6"
Therefore, Eq. (2) now becomes bi-level optimization problem as Eq. (3).
min 9
Σ
(S(U,(())) y.), s.t. U( xO
arg min U
TUUUU (3)
iEV
3.1.2 From Optimization View Bayesian Probabilistic View
Although Eq. (3) is an equivalent optimization view of SGC for semi-supervised node classification, it does not possess a clear Bayesian interpretation. The upper-level objective in Eq. (3) minimizes the supervision loss, and the lower-level constraint Tr(UTLU) minimizes the graph regularization loss, promoting the homophily assumption that connected nodes share the similar emhedddings/lbells. Therefore, motivated by [23], we absorb the lower-level constraint into the objective function itself as a relaxed single-level optimization problem in Eq. (4) by minimizing both two terms simultancously.
C= Σ (()(U.())) v.) + Trr (U(O)]LXU()))
min = iEV.
where Σ1 L AI with À as the balancing factor between two terms. The proposed optimization problem Eq. (4) immediately leads to a Bayesian probabilistic interpretation [67]. For notational simplicity, focus the detailed derivation of the binary case in the main body. In the special case of binary node classification, U(O) E =x can be reduced to u()) E R", and S(-) now becomes the Sigmoid function (+) in Eq. (5).
min u
C= Σ E(o((, + TI (u(O)TAA(())). = IEV:
(5)
Note that now u, (+) R and y1 10. Then Theorem 3.2 explicitly reveals the Bayesian probabilistic interpretation of the optimization framework in Eq. (5) [67].
Theorem 3.2. Solving Eq. (5) is equivalent to finding the maximum posteriori (MAP) estimate of the posterior probability distribution with the density PP(((( ()) y) as
P(((@)) yy) x ((u(E)) O)) exp (- (u())))
(6)
Here, the prior u(u(O)) follows Gaussian prior (O, 1 and the likelihood exp (- (e) defined by the likelihood potential (u)) = Eiev, ((((u(()) yi). = [yl]ev, E {0, 1)"
The Gaussian prior denotes prior belief over the distribution of the node embedding u(O) governed by the graph structure captured by the Laplacian matrix in the covariance term. It relates to the second trace term Eq. (5) or the forward pass of SGC. The likelihood (P ((@))) represents the underlying assumptions about how the observed labels yi are generated, determined by ((,,)). It relates to the first supervision loss term in Eq. (5) or the backward pass for training SGC.
Theorem 3.2 provides a clear Bayesian interpretation of SGC for semi-supervised node classification. The forward pass defines prior over node embeddings parametrized by O while the backward pass specifies the likelihood based on the supervision loss function. Together, they yield the posterior, guiding the update of node embeddings after observing limited labels. This insight enables the utilization of the EMCM method [6], which selects nodes leading maximum model change. For efficiency in query node selection, we focus on SGC in this work, despite more complex GNNs like GCN yielding a non-Gaussian prior in Eq. (6). The analysis of more complex GNNs, such as GCN, yields non-Gaussian prior while keeping all other aspects unchanged in Theorem 3.2. However, for computational efficiency in subsequent query node selection, adhere to the SGC model for now.
5

---

3.2 Expected Model Change Maximization for Graph Active Learning
3.2.1 Challenges for Applying EMCM on Graphs
We choose the EMCM method [6] for three main reasons. First, it is performance-bace approach that directly assesses the expected impact on the model if a sample is selected for query, aligning perfectly with the goal of AL. Second, it offers lower computational costs compared to other performance- methods like EER. Third, it is ideally supported by our proposed Bayesian probabilistic learning framework which provides an efficient way to estimate the expected model change without re-training. In the sequential active learning setting, our objective is to select the most informative node k- = arg maxkev A(k) with a designed acquisition function A(-). Similar to other performance-basee methods, EMCM utilizes look-ahead model [31] with the modified objective as C C ((o ()), y with from Eq. (5), where we add the unlabeled node Va with the hypothetical label D E {0, 1) due to the unavailability of the true label ylc- We select the node that could maximally change the node embeddings if it is added to the query set, via
ka arg max A(k) arg max VEV.
Σ My E((.1)
P(y kk) (k) u(O")ll..
(7)
KEV.
Here, Ô" arg min Ck O' = mig L and F(y. |k) is the predicted probability of label yk for node & estimated by the current model. The high-level motivation of Eq. (7) is that the generalization error changes only when the current model is updated. Nodes that do not update the node embeddings are useless for AL. Nodes causing significant model changes in terms of node embeddings are expected to lead to faster convergence to the optimal model. More detailed illustrations of EMCM can be found in Appendices B.3 and C.2.1.
Re-training the look-ahead model for the fixed node in Eq. (7) to obtain the exact solution is computationally infeasible due to the large number of unlabeled nodes. However, the proposed equivalent Bayesian learning framework Eq, (6) offers an efficient alternative. By utilizing rank-one updates of the current model's posterior mean and covariance (Eq. (5)). the posterior mean and covariance of the look-ahead model can be computed efficiently without the need for re- re-training. It significantly reduces the computational cost involved in applying the EMCM method graphs
3.2.2 Truncated Spectral Projection and Laplace Approximation for Efficiency
The computation of u(@") u( (()) through the Bayesian learning method in Eq. (6) still requires storing a large covariance matrix L E F=x=, Motivated by spectral clustering [48], we utilize the first m (m < n) smallest cigenvalues of L and their corresponding eigenvectors that contain important geometric information of the graph. Namely, we introduce A (ilag(A++A,, ......... Am +A) and V = iv',... y"] E R= where v' is the eigenvector corresponding to the i-th eigenvalue A₁. We can now project the node embedding u (() onto the space spanned by these eigenvectors by a = Viu(e), ). Based on the orthogonality of V (VTV = I), we can easily convert Eq. (5) as,
min E = Σ ((o(e. m) + Tr
(8)
TEVI
Eq. (8) now restricts the model latent space from R" to RT speeding up the model training and reducing the spatial complexity. similar Bayesian interpretation of Eq. (8) regarding a R" can be trivially extended from Theorem 3.2. We term this technique as truncated spectral projection.
To further reduce the computational overhead, we apply Laplace approximation on the posterior distribution of P(a | y) (instead of P(u(@) y)) corresponding to Eq. (6). The key idea is to approximate the non-Gaussian posterior via suitable Gaussian distributions here as obtain the analytical closed-form of the look-ahead model's 's posterior mean and covariance later [47].
Theorem 3.3. The Laplace approximation of the posterior distribution regarding a VT)(O) E T.m according to Eq. (8) and Eq. (6) is given as follows.
a y Nii Ca), & arg min E, Ca (Ax +
Σ Flolee (9) IE
a
Here, we define F((x,))
(z, v). e, represents the i-th standard basis vector Ozz

---

Theorem 3.3 gives a closed-form approximated Gaussian posterior distribution of a. Note that â = VTu(@") denotes the current model's č MAP estimator in Eq. (8) based on Theorem 3.2.
3.2.3 Expected Model Change Acquisition Function
Following the definition of C over ④ the look-ahead model now optimizes Ck. + ((o(e vt) with É in Eq. (8). We use â RiM to denote the look-ahead model's (R. MAP estimator. The exact value of à k. can be obtained by re-training the look-ahead model. We instead compute an approximation of * by one single step of Newton's 's method on the objective L without re-training, given by Theorem 3.4. Since the look-ahead model built upon the current model, using a single step of Newton's 's Method can quickly approximate the solution for L based on the local information (gradient and curvature) around the current model's MAP estimator [47].
Theorem 3.4. The look-ahead MAP estimator â h. can be obtained by performing one step of Newton's method on Elsl from the current MAP estimator à as
F(o(e) 1 ( oi (e]V)Ca(e[[V] VV(e
à k.u =
(10)
We define F(z. v) = 06 (x, (x, d (z. y). e; represents the i-th standard basis vector 3e
Now, we finally come back the original acquisition function for applying EMCM graphs in Eq. (7). The predicted probability of label yi can be set as the soft label prediction for node by Thanks to the truncated spectral projection (á = V a R. (T @ and Laplace approximation,
the current model (P = 1 k) = (()) (Plyi = 0 k) = 1
we can now measure the change of [lu(@") u(O")l2 via ||a A. 6x|2 due to the orthogonal invariance of 12 norm. Based on Theorem 3.4 and Eq. (7), the final designed acquisition function is
F(o(v(a).
A(K)
Σ ((.1)
P( 1|A:)O PP 01k))
Cavvllle
1 F'(o(V]á) w
(11)
V) as the k-th row vector of V. The proposed active learning algorithm expecteD mOdel Change maximizaTion On gRaphs (DOCTOR) in the sequential setting is presented in Algorithm 2 in Appendix D.2. For the batch active learning setting and the multi-class classification setting, we refer Appendices D.3 and D.4.
Here, P(y 1[k) = o(e]u(O)) and define
3.3 Theoretical Insights of the Proposed Method DOCTOR
We analyze the profound connection between the proposed EMCM method and the Expected Error Minimization (EEM) or EER method for graph active Icarning. We will show that the designed acquisition function Eq. (1I) will be reduced the one for EEM under some assumptions and thus it has a direct connection to the ultimate goal for graph AL in Eq. (1), For clarity, we focus on the fundamental regression task within the sequential AL setting. We choose the regression for theoretical analysis to get rid of the non-lime non-linear activation functions in the Bayesian learning framework (a (-) in Eq. (5)) from the beginning. We also fix the loss function E(.,)) as the common squared error loss.
Theorem 3.5. We assume ((x,y) = {x --y- y)² is used for the regression task in the sequential active learning selling (b=l). In the 1-th iteration step, the proposed DOCTOR algorithm aims to solve
max A(k) max kEV()
I/Cvvll..
(12)
kev
1+ vÍCaa
And the Expected Error Minimization on graphs aims solve min min! ( (() v.), Then.
arg min E
iev!" [() v4)l
arg max
1 + C ||Cavall.
(13)
k!)(")
RE
7

---

Table 1: Test accuracy (%) five datasets with the labeling budget (20 labels per class).
GEEM DOCTOR
Runmn g Time (6)
Method
Cora
Citeseer
PubMed
Reddit
ogbn-arxiv
22x
Random
78.9+-0.9
70.7++0.7
78.4+0.5
91.3++0.5
68.3==0.4
10x
7x
BBy
102x
AGE
82.3+0.5
71.4+0.5
79.4+0.7
91.5+004
68.7++0.3
ALG
82.6+-0.6
73.6+0.6
80.8+033
92.4++06
70.0=00.2
38x
40x
50% 56x
RIM
84.1+00.8
73.2+0.77
80.2:004
92.0=t.77
70.5
Cora
Cteseer
PubMed
IGP
86.3:10.7
75.81:0.4
83,5+0.5
93.3:104
70.9
GraphPart 8..
74.0+2..0
81.5116
92.71:10
72.3
Figure Running Time Com-
DOCTOR
86,9+0.7
7.,5+0.8
84.3+0.9
93.5+0.5
73.0++1.2
parison (at log scale).
Theorem 3.5 demonstrates the equivalence between the proposed DOCTOR algorithm and the EEM method on graphs, given certain basic assumptions. Consequently, from theoretical standpoint, DOCTOR can implicitly select the node that minimizes the expected prediction error if added into the training set during the next iteration, as directly correlated with the initial objective in Eq. (1). Moreover, DOCTOR offers significantly reduced computational overhead through truncated spectral projection and Laplace approximation, compared to EEM-based approaches like GEEM [51].
4 Experiments
We now verify the effectiveness of DOCTOR on five real-world graphs. We aim to evaluate DOCTOR in terms of prediction accuracy, efficiency, generalization ability, and interpretability (Appendix G).
4.1 Experimental Setup
Datasets We evaluate DOCTOR for the pool-hased active learning setting on five datasets, including three citation networks (i.e., Citeseer, Cora and PubMed) [32], one social network (Reddit) [22],
and one large-scale OGB dataset (ogbn-arxiv) [26]. Details can be found in Appendix F.I.
Baselines We compare DOCTOR with six state-of-the-arr baseline methods for active learning on graphs. Random selects the nodes to query randomly. AGE [4] Combines different query strategies parameters. ALG [88] select nodes that maximize the effective reception
linearly with field GCN. RIM [89] further considers the influence quality during node selection. IGP [90] choose nodes that maximize information gain propagation. GraphPart [41] selects representative nodes within each graph partition to query. Implementation details are referred to in Appendix F.2.
4.2 Experimental Results
Accuracy Comparison We compare DOCTOR with baselines for multi-class node classification in the batch AL. setting (Appendix D.4). We choose small set of two randomly sampled labeled nodes for each method as the initial pool. The query node size is fixed as b = 5 in each iteration and the labeling budget is fixed as 20 labels per class (B = 20c). The backbone is set as the SGC model. Table 1 shows the classification accuracy on five datasets with the same labeling budget. We repeat each method 10 times and report the mean and variance regarding the accuracy. Remarkably, the proposed DOCTOR achieves the best in all the cases and improves the second-bes baseline by nearly 1 % on some datasets. The improvement on the Reddit dataset rather marginal since it is designed for the inductive setting and DOCTOR is originally proposed for the transductive setting.
To show the influence of the labeling budget, we display the accuracy of different AL methods under different labeling budgets three citation datasets in Figure 2. We range the labeling budgets B from 2e to 20c with e as the number of classes. The results in Figure 2 demonstrate that with the increase in labeling budget, the accuracy of DOCTOR grows as well, outperforming many of the baselines with a greater margin.
Efficiency Comparison To evaluate the efficiency of DOCTOR, we conducted analysis of its running time per AI iteration alongside other baselines using the Cora dataset. We introduce another serformaaccebaased graph AL method called GEEM [51], which extends the EEM principle

---

80
85
75
80
Accurary (16)
Accuracy (%)
80
70
65
60
Rarsom
ISP
GraptPart
65
Grap
20
40 60
80
100
120
140
50
20
40
60
80
100
120
10
20
30
40
50
60
Size of labeling budget
Size labeling budget
Size of labeling budget
(a) Cora
(b) Citeseer
PubMed
Figure 2: Test accuracy with different labeling budgets on three datasets.
Expected Model Change (EMC)
20
Table 2: Test accuracy (%) of different methods with different backbone GNNs on the Citeseer dataset.
1.0
App roximmattee EMC in DOCTOR
Exact EMC via Re training
0.8
Test Erroo (%6)
Method SGC
GCN
APPNP
GraphSAGE:
0.6
training
Random
70.7100.7
70.810.8
71.011.,6
70.6::0.8
0.4
AGE
71.4++0.5
71.6+-0.6
71.3+005
71.4+0.7
0.2
12
ALG
73.6:10.6
73.810..
74.1:0.77
74.0110.9
RIM
73.2+00.7
73.0+0.8
73.3+0.88
73.2++0.9
0.0
IGP
75.8++0.4
75.4+0.9
75.5+0066
75.6+1.0
0
2
Node
4
6
8
GraphPart
74.0.12.0
74.311..6
74.5.1..
74.9.1..5
DOCTOR
76.5.10.8
76.2.10.7
76,6.10.9
76.4.0099
Figure 3: Interpretation Analysis.
for graphs. However, GEEM's scalability is extremely limited on large-scale datasets. We consider the training time GEEM as the baseline and measure the relative running time of each method. Figure illustrates these results, where the numbers atop each bar represent the multiplier improve- ment in running time compared to GEEM. Our method, DOCTOR, exhibits significant efficiency improvements, surpassing GEEM dozens of times while achieving comparable results to ALG, The more detailed time complexity of the proposed DOCTOR method can be found Appendix G.I.
Note that the acquisition function in the proposed DOCTOR algorithm is specifically designed for the SGC method [68]. Nonetheless, we can still substitute the backbone training model, SGC, with other GNNs in each iteration of the AL loop (line 5 in Algorithm 2) without any difficulties. The resulting acquisition function will be computed based on the new node embeddings generated by other GNNs without any other changes. We select some common GNNs, including GCN [32], APPNP [33] and GraphSAGE [22], to verify the generalization ability of the proposed acquisition function. We change the backbone model of other baselines accordingly as well. We fix the labeling budget as 20 labels per class. All experiments are conducted in the transductive AI setting the Citeseer dataset and the results summarized in Table 2. Like other baselines, the proposed acquisition function in the proposed DOCTOR method generalizes well other GNN backbone models without any significant changes regarding prediction accuracy, even though it is originally designed for SGC. The underlying reason is that apart from SGC, most other GNNs can also be incorporated into the proposed Bayesian learning framework with more complex forms of prior and the currently derived form of the acquisition function can approximate the exact solution when other GNNs are used backbones.
Generalization to Other GNNs
Interpretability We perform a case study on single iteration step of DOCTOR in the sequential AL setting using the Cora dataset. We choose one query node from pool of 10 randomly sampled unlabeled nodes for visualization purposes. We focus on one iteration step in the exact middle of the entire AL process. We compare the approximate EMC, computed based on Eq. (11) in the DOCTOR method, with the exact EMC, computed based on Eq. (7) by adding the node's label for re-training. use maximum value of the exact EMC among these nodes as the baseline, and we report all other EMC values in relative manner in Figure 3. The results show that our efficient computation of the designed acquisition function via truncated spectral projection and Laplace approximation approximates the exact solution quite well. Additionally, we sort the candidate nodes in descending

---

order based on the exact EMC value and obtain the respective test error by re re-training the model with the node's label. Figure 3 illustrates that by choosing the node that has the maximum approximate EMC value without re-training via the proposed acquisition function Eq. (11), we can minimize the test error on the remaining unlabeled nodes by adding this node to the labeled node set for the next. round of training. This key observation empirically validates the insights of Theorem 3.5.
5 Conclusion
In this work, we extend the EMCM principle for GNNs based on a provided Bayesian learning framework. This allows us to efficiently compute closed-form acquisition function that can be used select the most informative nodes label. The proposed DOCTOR method establishes theoretical connections with the ultimate goal of minimizing expected prediction error in AL. This makes it promising tool for training GNNs in real-world applications with limited labeled data.
Limitations
The acquisition function in DOCTOR is derived from the SGC model but has good generalizability other GNNs empirically. We leave the investigation of the closed-form MAP estimator of other GNNs as future work. The acquisition function in DOCTOR is originally designed for the sequential active learning setting, and we only use simple sampling method extend it for the batch active learning setting. We also leave the investigation of more advanced batch AL extension of DOCTOR as future work. The theoretical connection between our method with entropy minimization in terms of strictly proper scoring rules can be further investigated in detail [64]. Other potential applications of our method can be explored the hyperbolic space [76, 79, 77, 80, 78, 75, 81) or the natural language processing domain [34, 36, 35, 20, 19, 63, 44, 99, 100, 98].
Acknowledgements
The work described in this paper was partially supported by the National Key Research and Devel- opment Program of China (No. 2018AAA0100204 RGC Research Impact Fund (RIF), R5034-18 (CUHK 2410021), and RGC General Research Funding Scheme (GRF) 14222922 (CUHK 2151185).
References
[1] Charu C. Aggarwal, Xiangnan Kong, Quanquan Gu, Jiawei Han, and Philip S. Yu. Active learning: survey. Data Classification: Algorithms and Applications, pages 571-606. CRC Press, 2014.
[2] Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham M. Kakade. Gone fishing: Neural active learning with fisher embeddings. NeurlPS, pages 8927-8939, 2021.
[3] Mustafa Bilgic, Lilyana Mihalkova, and Lise Getoor. Active learning for networked data. In ICML, pages 79-86. Omnipress, 2010.
[4] Hongyun Cai, Vincent Wenchen Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. CoRR, abs/1 705.05085, 2017.
[5] Wenbin Cai, Muhan Zhang, and Ya Zhang. Batch mode active learning for regression with expected model change. IEEE Trans. Neural Networks Learn. Syst., 28(7):1668-16) 1681, 2017.
[6] Wenbin Cai. Ya Zhang, and Jun Zhou. Maximizing expected model change for active learning in regression. In ICDM, pages 51 60. IEEE Computer Society, 2013.
[7] Wenbin Cai, Yexun Zhang, Ya Zhang, Siyuan Zhou, Wenquan Wang, Zhuoxiang Chen, and Chris H. Q. Ding. Active learning for classification with maximum model change. ACM Trans. Inf. Syst., 36(2):15:1115:22 2017.
[8] Razvan Caramalau, Binod Bhattarai, and Tae-Kyun Kim. Sequential graph convolutional network for active learning. CVPR, pages 9583-9592, Computer Vision Foundation / IEEE, 1021.
10

---

[9] Yankai Chen, Yixiang Fang, Yifei Zhang, and Irwin King. Bipartite graph convolutional hash- ing for effective and efficient top-n search in hamming space. arXiv preprint arXiv:2304.00241, 2023.
[10] Yankai Chen, Yifei Zhang, Menglin Yang. Zixing Song, Chen Ma, and Irwin King. WSFE: wasserstein sub-gray sub-graph feature encoder for effective user segmentation in collaborative filtering. CoRR, abs/2305.044 2023.
[11] Yankai Chen, Yifei Zhang, Menglin Yang, Zixing Song, Chen Ma, and Irwin King. WSFE: wasserstein sub-graph feature encoder for effective user segmentation in collaborative filtering. In SIGIR, pages 2521 2525. ACM, 2023.
[12] Gautam Dasarathy, Robert D. Nowak, and Xiaojin Zhu. S2: an efficient graph based active learning algorithm with application to nonparametric classification. In COLT. volume 40 of JMLR Workshop and Conference Proceedings, pages 503-522. JMLR.org, 2015.
[13] Sanjoy Dasgupta and Daniel J. Hsu. Hierarchical sampling for active learning. In ICML, volume 307 of ACM International Conference Proceeding Series, pages 208-215. ACM, 2008.
[14] Pinar Donmez, Jaime G. Carbonell, and Paul N. Bennett. Dual strategy active learning. In ECML, volume 4701 of Lecture Notes in Computer Science, pages 116-177. Springer, 2007.
[15] Sergio Flesca, Domenico Mandaglio, Francesco Scala, and Andrea Tagarelli. Learning to active learn by gradient variation based instance importance. In ICPR, pages 2224-22222222 2230.. IEEE, 2022.
[16] Yoav Freund, H. Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Mach. Learn., 28(2-3):133-166 1997.
[17] Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 1183-1192. PMLR, 2017.
[18] Li Gao, Hong Yang. Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network representation learning. In I/CAI, pages 1142-2148. ijeai.org, 2018.
[19] Yifan Gao. Jingjing Li, Michael R Lyu. and Irwin King. Open-retrieval conversational machine reading, arXiv preprint arXiv:2102.08633 2021.
[20] Yifan Gao, Chien-Sheng Wu, Jingjing Li, Shafiq Joty, Steven CH Hoi, Caiming Xiong, Irwin King, and Michael Lyu. Discern: Discourse-aware entailment reasoning network for conversational machine reading. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2439 22499,2449994 2020.
[21] Quanquan Gu and Jiawei Han. Towards active learning on graphs: An error bound minimization approach. In ICDM, pages 882-887. IEEE Computer Society, 2012.
[22] William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pages 1034-1034, 2017.
[23] Haoyu Han, Xiaorui Liu, Haitao Mao, MohamadAli Torkamani, Feng Shi, Victor Lee, and Jiliang Tang. Alternteey optimized graph neural networks. 2023.
[24] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. ICML, volume 119 of Proceedings of Machine Learning Research, pages 4094 4104. PMLR, 2020.
[25] Shengding Hu, Zheng Xiong, Meng Qu, Xingdi Yuan, Mare-Alexandre Côté, Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. In NeurIPS, 2020.
[26] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB-LSC: large-scale challenge for machine learning on graphs. In NewrIPS Datasets and Benchmarks, 2021.
11

---

[27] Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. In NIPS, pages 892-900. Curran Associates, Inc., 2010.
[28] Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. IEEE Trans. Pattern Anal. Mach. Intell., 36(10):1936-199)) 1949, 2014.
[29] Ming Ji and Jiawei Han. A variance minimization criterion active learning on graphs. In AISTATS, volume 22 of JMLR Proceedings, pages 556-564. JMLR.org, 2012.
[30] Junteng Jia, Michael T. Schaub, Santiago Segarra, and Austin R. Benson. Graph-based semi-supervised & active learning for edge flows. KDD, pages 761-771. ACM, 2019.
[31] Yoon- Yoon-Yeong Kim, Kyungwoo Song. JoonHo Jang, and Il-Chul Moon. LADA: look-ahead data acquisition via augmentation for deep active learning. In NeurlPS, pages 2299-22930, 2021.
[32] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR (Poster). OpenReview.net, 2017.
[33] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR (Poster). OpenReview.net, 2019.
[34] Jingjing Li, Yifan Gao, Lidong Bing, Irwin King, and Michael R Lyu. Improving question generation with to the point context. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3216-3226, 2019.
[35] Jingjing Li, Zichao Li, Tao Ge, Irwin King, and Michael R Lyu. Text revision by on-the-fly representation optimization. pages 10956-10964, 2022.
[36] Jingjing Li, Zichao Li, Lili Mou, Xin Jiang, Michael Lyu, and Irwin King. Unsupervised text generation by learning from search. Advances in Neural Information Processing Systems, 33:10820-10833 2020.
[37] Xiaoting Li. Yuhang Wu, Vineeth Rakesh, Yusan Lin, Hao Yang. and Fei Wang. Smartquery: An active learning framework for graph neural networks through hybrid uncertainty reduction. In CIKM, pages 1199-4203 ACM, 2022.
[38] Yayong Li, Jie Yin, and Ling Chen. SEAL: semisupervised adversarial active learning on attributed graphs. IEEE Trans. Neural Networks Learn. Syst., 32(7):3 2021.
[39] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, Yuan Qi, and Jieping Ye. Tackling long-tailed distribution issue in graph neural networks via normalization. IEEE Transactions on Knowledge and Data Engineering, pages 1023.
[40] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, and Jieping Ye. Resnorm: Tackling long-tailed degree distribution issue in graph neural networks via normalization. CoRR, abs/2206.08181. 2022.
[41] Jiaqi Ma, Ziqiao Ma, Joyce Chai, and Qiaozhu Mei. baste active learning for graph neural networks. Transactions on Machine Learning Research, 2023. Survey Certification.
[42] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. unified view on graph neural networks as graph signal denoising. In CIKM, pages 1202-1211, 1. ACM, 2021.
[43] Yueen Ma, Zixing Song. Xuming Hu, Jingjing Li, Yifei Zhang, and Irwin King. Graph component contrastive learning for concept relatedness estimation. In AAAI, pages 13362- 13370. AAAI Press, 2023.
[44] Yueen Ma, Zixing Song. Xuming Hu. Jingjing Li, Yifei Zhang, and Irwin King. Graph component contrastive learning for concept relatedness estimation. Proceedings of the AAAI Conference on Artificial Intelligence, (7(1):13362-13777 Jun. 2023.
[45] Sofus A. Macskassy. Using graph-based metrics with empirical risk minimization to speed up active learning networked data. In KDD, pages 597-606. ACM, 2009.
12

---

[46] Andrew McCallum and Kamal Nigam. Employing EM and bool-based active learning for text classification. In ICML. pages 350-358. Morgan Kaufmann, 1998.
[47] Kevin Miller and Andrea L. Bertozzi. Model-change active learning in graph-based semi- supervised learning. CoRR, abs/ 10.07739, 2021.
[48] Andrew Y. Ng. Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849 856. MIT Press, 2001.
[49] Hieu Tat Nguyen and Amold W. M. Smeulders. Active learning using pre-clustering. In ICML, volume 69 of ACM International Conference Proceeding Series. ACM, 2004.
[50] Anant Raj and Francis R. Bach. Convergence of uncertainty sampling for active learning. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 18310-18331. PMLR, 2022.
[51] Florence Regol, Soumyasundar Pal, Yingxue Zhang, and Mark Coates. Active learning on attributed graphs via graph cognizant logistic regression and preemptive query generation. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 8041-8050. PMLR, 2020.
[52] Christoffer Rii,, Francisco Antunes, Frederik Hüttel, Carlos Lima Azevedo, and Francisco Pereira. Bayesian active learning with fully bayesian gaussian processes. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 12141-12153 Curran Associates, Inc., 2022.
[53] Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling estimation of error reduction. In ICML, pages 441-448. Morgan Kaufmann, 2001.
[54] Andrew I. Schein and Lyle H. Ungar. Active learning for logistic regression: an evaluation. Much. Learn., 68(3):235-265 2007.
[55] Burr Settles. Active learning literature survey. 2009.
[56] H. Sebastian Seung. Manfred Opper, and Haim Sompolinsky. Query by committee. In COLT, pages 287-294. ACM, 1992.
[57] Zixing Song and Irwin King. Hierarchical heterogencous graph attention network for syntax- aware summarization. In AAAI, pages 11340-11348 AAAI Press, 2022.
[58] Zixing Song. Yueen Ma. and Irwin King. Individual faimess in dynamic financial networks.
In NeurlPS 2022 Workshop: New Frontiers in Graph Learning, 2022.
[59] Zixing Song, Ziqiao Meng, Yifei Zhang, and Irwin King. Semi-supervised multi-label learning for graph-structured data. In CIKM, pages 1723-1733, ACM, 2021.
[60] Zixing Song, Xiangli Yang, Zenglin Xu, and Irwin King. Graph-based semi-supervised learning: A comprehensive review. IEEE Transactions on Neural Networks and Learning Systems, pages 1-21, 2022.
[61] Zixing Song, Yifei Zhang, and Irwin King. Towards an optimal asymmetric graph structure for robust semi-supervised node classification. In KDD, pages 1656-1665. ACM, 2022.
[62] Zixing Song, Yuji Zhang, and Irwin King. Towards fair financial services for all: A temporal GNN approach for individual faimesss transaction networks. In CIKM, pages ACM, 2023.
[63] Xin Sun, Tao Ge, Shuming Ma, Jingjing Li, Furu Wei, and Houfeng Wang. A unified strategy for multilingual grammatical error correction with pre-trained cross-lingual language model. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 4367-4374. International Joint Conferences on Artificial Intelligence Organization, 2022. Main Track.
13

---

[64] Wei Tan, Lan Du, and Wray L. Buntine. Diversity enhanced active learning with strictly proper scoring rules. In NeurlPS, pages 10906-10918, 2021.
[65] Yufei Tao, Hao Wu, and Shiyuan Deng. Cross-space active learning on graph convolutional networks. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 21133-21145. PMLR, 2022.
[66] Maximilian Thiessen and Thomas Gärtner. Active learning of convex halfspaces on graphs. In NeurIPS, pages 23413 221225, 2021.
[67] Nicolás Gareía Trillos, Daniel Sanz-Alonso, and Ruiyi Yang. Mathematical foundations of graph-based bayesian semi-supervised learning. CoRR, 0ttp/2207.01092 2022.
[68] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 6861-6871. PMLR, 2019.
[69] Wei Wu and Mari Ostendorf. Graph-based query strategies for active learning. IEEE Trans. Speech Audio Process., 21(2):260-26) 2013.
[70] Yuexin Wu, Yichong Xu, Aarti Singh, Yiming Yang, and Artur Dubrawski. Active learning for graph neural networks via node feature propagation. CoRR, abs/1910.07756 2019.
[71] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32(1):4 24, 2021.
[72] Binhui Xie, Longhui Yuan, Shuang Li, Chi Harold Liu, Xinjing Cheng, and Guoren Wang. Active learning for domain adaptation: An energy-based approach. In AAAI, pages 8708-8716. AAAI Press, 2022.
[73] Yu Xie, Shengze Lv, Yuhua Qian, Chao Wen, and Jiye Liang. Active and semi-supervised graph neural networks for graph classification. IEEE Trans. Big Data, 8(4):920- 992,922,, 2022.
[74] Rui Xue, Haoyu Han, MohamadAli Torkamani, Jian Pei, and Xiaorui Liu. Lazygon: Large- scale graph neural networks via lazy propagation. CoRR, abs/2302.01503, 2023.
[75] Menglin Yang. Zhihao Li. Min Zhou, Jiahong Liu, and Irwin King. Hief: Hyperbolic informative collaborative filtering. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2212-2221, 2022.
[76] Menglin Yang, Ziqiao Meng, and Irwin King. FeatureNorm: L2 feature normalization for dynamic graph embedding. In 2020 IEEE International Conference on Data Mining (ICDM), pages 731-740. IEEE, 2020.
[77] Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete- time temporal network embedding via implicit hierarchical learning in hyperbolic space. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1975-1985, 2021.
[78] Menglin Yang, Min Zhou, Jiahong Liu, Defu Lian, and Irwin King. Href: Enhancing col- laborative filtering via hyperbolic geometric regularization. In Proceedings of the ACM Web Conference 2022, pages 1462-2471, 2022.
[79] Menglin Yang. Min Zhou, Lujia Pan, and Irwin King. khgen: Tree-likeness modeling via continuous and discrete curvature learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2965-2977, 2023.
[80] Menglin Yang, Min Zhou, Hui Xiong, and Irwin King. Hyperbolic temporal network embed- ding. IEEE Transactions Knowledge and Data Engineering, 2022.
[81] Menglin Yang, Min Zhou, Rex Ying, Yankai Chen, and Irwin King. Hyperbolic representation learning: Revisiting and ad advancing. arXiv preprint arXiv:2306.00111 2023.
14

---

[82] Xiangli Yang. Zixing Song, Irwin King, and Zenglin Xu. A survey on deep semi- superssee learning. IEEE Transactions on Knowledge and Data Engineering, pages 1-20. 2022.
[83] Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G. Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. Int. J. Comput. Vis.,
1 113(2)1133127, 2015.
[84] Yongyi Yang. Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. In ICML,, volume 139 of Proceedings of Machine Learning Research, pages 11773-11783, PMLR, 2021.
[85] Xucying Zhan, Qingzhong Wang. Kuan-Hao Huang, Haoyi Xiong, Dejing Dou, and Antoni B. Chan. A comparative survey of deep active learning. CoRR, fbss2203.134500 2022.
[86] Hongjing Zhang, S. S. Ravi, and Ian Davidson. A graph-based approach for active learning in regression. In SDM, pages 280-288. SIAM, 2020.
[87] Jifan Zhang, Julian Katz-Samuels, and Robert D. Nowak. GALAXY: graph-based active learning the extreme. In JCML, volume 162 of Proceedings of Machine Learning Research, pages 26223-26233 PMLR, 2022.
[88] Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang, and Bin Cui. ALG: fast and accurate active learning framework for graph convolutional networks. In SIGMOD Conference, pages 2366-2374 ACM, 2021.
[89] Wentao Zhang, Yexin Wang, Zhenbang You, Meng Cao, Ping Huang, Jiulong Shan, Zhi Yang. and Bin Cui. RIM: reliable influence-based active learning graphs. In NeurlPS, pages 77978-27990, 2021.
[90] Wentao Zhang, Yexin Wang. Zhenbang You, Meng Cao, Ping Huang, Jiulong Shan, Zhi Yang, and Bin Cui. Information gain propagation: a new way to graph active learning with soft labels. In ICLR. OpenReview.net, 2022.
[91] Wentao Zhang, Zhi Yang, Yexin Wang, Yu Shen, Yang Li, Liang Wang, and Bin Cui. Grain: Improving data efficiency of graph neural networks via diversified influence maximization. Proc. VLDB Endow, 14(11):2433-2482 2021.
[92] Yifei Zhang, Yankai Chen, Zixing Song, and Irwin King. Contrastive cross-scale graph knowledge synergy. In KDD, pages 3422-3433, ACM, 2023.
[93] Yifei Zhang, Hao Zhu, Ziqiao Meng, Piotr Koniusz, and Irwin King. Graph-adaptive rectified linear unit for graph neural networks. In Proceedings of the ACM Web Conference 2022, 2022.
[94] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. COSTA: covariance- preserving feature augmentation for graph contrastive learning. In KDD, pages 2524-2534 ACM, 2022.
[95] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmen- tation for graph contrastive learning and beyond. In AAAI, pages 2023.
AAAI Press,
[96] Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay, Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI, pages 5829-5836. AAAI Press, 2019.
[97] Yuheng Zhang, Hanghang Tong, Yinglong Xia, Yan Zhu, Yuejie Chi, and Lei Ying. Batch active learning with graph neural networks via multi-agent deep reinforcement learning. In AAAI, pages 91 18 11-811266 AAAI Press, 2022.
[98] Yuji Zhang and Jing Li. Time will change things: An empirical study on dynamic language understanding in social media classification. arXiv e-prints, pages arXiv-22100 2022.
15

---

[99] Yuji Zhang, Jing Li, and Wenjie Li. Vibe: Topic-driven temporal adaptation for twitter classification. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (FMNLIP), Singapore, December 2023. Association for Computational Linguistics.
[100] Yuji Zhang, Yubo Zhang, Chumpu Xu, Jing Li, Ziyan Jiang, and Baolin Peng. #How YouTagTweett Learning user hashtagging preferences via personalized topic attention. In Proceedings of the 2021 Conference on Empirical Methods Natural Language Processing, pages 7811-7820, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
[101] Jingbo Zhu, Huizhen Wang, Benjamin K. Tsou, and Matthew Ma. Active learning with sampling by uncertainty and density for data annotations. IEEE Trans. Speech Audio Process., (8(6):133-1333) 2010.
[102] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In WWW, pages 1215-1226. ACM IW3C2, 2021.
[103] Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani. Combining active learning and semi- supervised learning using gaussian fields and harmonic functions. In ICML 2003 workshop on the continuum from labeled to unlabeled data in machine learning and data mining, volume 2003.
16


Reviews:
[{"review_id": "vH7ahxfWbx", "reviewer": "Reviewer_bxJi", "summary": "The authors propose an active learning method for GNNs, extending the Expected Model Change Maximization (EMCM) principle to GNNs. A Bayesian interpretation for the node embeddings generated by GNNs under the semi-supervised setting is presented. By establishing a connection with expected prediction error minimization, theoretical guarantees for AL performance are driven. The numerical experiments shows improved performance and runtime compared to the existing approaches.", "questions": "- It would be nice to add an ablation study about the approximations made in the model. I am curious to know the effect of number of retained eigenvalues/vectors in Laplacian approximation on the performance of the model and it relation to homophily (from a graph signal processing point of view, retaining smallest eigenvalues correspond to low-pass filtering of the signal over graph).", "limitations": "See above sections.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well-written and clearly motivated. The overall proposed active learning approach makes sense and seems sound (although I haven't check the proof details). I like the proposed approach for deriving Bayesian interpretation for GNNs. There are sufficient experiments to support the claims as well.", "weaknesses": "I don't see any glaring weakness other than Figure 1 not including the IGP (the closest model to the proposed in terms of performance). Probably better to move Figure 7 in appendix to the main manuscript. A minor comment: some of the equations in the appendix are out of bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very thoughtful and constructive review. We appreciate the recognition of our active learning approach and the Bayesian interpretation of GNN training. We are glad to know that you found our paper clear, well-motivated, and supported by sufficient experiments. We would also like to thank you for your suggestions for improvement and have addressed each of your points below. We hope these responses will address your concerns appropriately.\n\n\n## 1. Figure 1 and Figure 7. \n\nWe admire your suggestion. **We will shift Figure 7 from Appendix to the main manuscript and probably consider substituting Figure 7 for Figure 1.** In this way, we can better show the accuracy and running time comparison simultaneously in one figure and highlight the efficacy and efficiency of our method.\n\n## 2. Out of Bound Equations in the Appendix.\n\nThank you for bringing this to our attention. **We apologize for this oversight (lines 894,910) and will make sure to reformat the equations**.\n\n\n## 3. Ablation Study. \n\nYour suggestion for adding an ablation study on analyzing the effect of the number of retained eigenvalues/vectors is insightful. In particular, **we actually did a similar sensitivity analysis on the number of retained eigenvalues $m$ in Appendix G.3,** along with the balancing factor $\\lambda$. For a clearer presentation, we summarize the case when fixing $\\lambda = 5e-4$ with varying numbers of retained eigenvalues $m$ in the following table. More results can be referred to in Appendix G.3. **A larger $m$ usually leads to better performance since the approximation of the node embeddings projection will be more precise, but the improvement may be quite marginal if $m$ is too large with higher computational cost as well.**\n\n| #Retained eigenvalues $m$  |  10  |  20  |  50  |  100 |  200 |\n|:--------------------------:|:----:|:----:|:----:|:----:|:----:|\n|    Accuracy on Cora (%)    | 82.2 | 82.7 | 84.0 | 84.3 | 84.4 |\n|  Accuracy on Citeseer (%)  | 71.7 | 73.0 | 74.5 | 75.5 | 75.7 |\n\n## 4. Relation to homophily. \n\nWe highly appreciate your suggestions. Indeed, **we choose to retrain the top-$m$ smallest eigenvalues based on this exact motivation that it corresponds to a low-pass filter, and the graph signal is assumed to be smooth (a.k.a, it is a homophilous graph).** Therefore, when the homophily principle holds and the graph signals are smooth, **applying a low-pass filter by retaining the smallest eigenvalues in the truncated spectral projection could capture most of the important information present in the graph signal while reducing the computational cost significantly.** This makes it a relevant theoretical understanding of GNN models[1][2]. We will discuss more on its relationship with the homophily concept from graph signal processing (GSP) in Section 3.2.2, and illustrate why we choose to retain the smallest eigenvalues during Laplacian approximation more clearly. **For a formal theoretical analysis of the direct relationship between the model performance and the number of retained smallest eigenvalues from the GSP aspect, we leave it for future work since we need many more assumptions on the graph itself**, like how the graph is generated and the how the label is generated from the graph. Nonetheless, the investigation of this direction is very promising and can motivate new design of the active learning methods for GNNs.\n \n\n[1] Ma, Yao, et al. \"A unified view on graph neural networks as graph signal denoising.\" Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021\n\n[2] Dong, Xiaowen, et al. \"Graph signal processing for machine learning: A review and new perspectives.\" IEEE Signal processing magazine 37.6 (2020): 117-127.\n\n"}, {"review_id": "ZzP7c10Zpz", "reviewer": "Reviewer_zbTy", "summary": "The authors present yet another active learning approach for graph neural networks, claiming it to be novel. They attempt to build upon the classic expected model change maximization method but in a general active learning setting. To do so, they introduce a Bayesian interpretation of the SGC model, which supposedly unifies the training process of GNN models. Some approximation techniques are used, along with some theoretical analysis. ", "questions": "1. What are the inner connections between the unified Bayesian interpretations of GNNs and the subsequent proposed active learning method? A more compact explanation is preferred.\n2. What are the look-ahead models in Section 3.2.3? The term is frequently used, but little context is provided about this term. Is it the potentially trained model after some labels are given by the oracle?\n3. What about some possible extensions of this work? How does the proposed method deal with the noisy oracle?", "limitations": "There are no major limitations of this work. However, the reviewer has some open discussions about the extensions. For example, what if the label has noise? In real-world cases, there is no oracle in any application since even human experts can sometimes make mistakes. How can this model be adapted to the noisy oracle case? The reviewer would like to see the authors' thoughts on this question.\n", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The novelty of this paper is ok. It extends the existing literature on general active learning by being the first work to apply EMCM to graphs. The unified Bayesian view also brings some new insights.\n2. The method is well-motivated, with an intriguing theoretical analysis. The proposed method is also efficient both from the theoretical aspect and the experimental aspect.\n3. The writing is satisfying, with clear logic and notations. I believe this work can benefit researchers from both the GNN domain and the active learning field.", "weaknesses": "1. More discussions on the deep connection between the Bayesian interpretations of GNNs and the proposed active learning method DOCTOR should be provided.\n2. More background knowledge on the look-ahead models in active learning literature should be provided.\n3. More details on the experiments, like the hyperparameters settings, should be provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive review! We are glad to know that you found our paper novel, well-motivated, and well-written. We hope these responses will address your concerns appropriately. \n\n\n## 1. Connections between the unified Bayesian interpretations of GNNs and the subsequent proposed active learning method \n\nThe inner connections between the unified Bayesian interpretations of GNNs and the subsequent proposed active learning method are as follows. Under semi-supervised settings, current GNN models typically lack a Bayesian probabilistic interpretation. But in active learning,  Bayesian interpretation lays the groundwork for performance-based methods, where our proposed method belongs. It incorporates prior knowledge and updates the posterior beliefs about the model parameters or predictions, assuming if new labeled data becomes available. Our method bridges this gap. More discussions can be found in Sec. 2.4.1.\n\n\n## 2.Background knowledge on the look-ahead models\n\nThe performance-based methods usually consider the look-ahead model. We first hypothetically assume one candidate node $x_+^k$ from the pool of the unlabeled nodes is chosen for query, and its label is revealed as $y_+^k$ by the oracle. Then we analyze the potential influence of this candidate node ($x_+^k, y_+^k$) on the model's parameters or predictions if it is added to the labeled node set for the next round of training. **In fact, more discussions regarding the background knowledge of look-ahead models can be found in Appendix B.3.1.**\n\n\n## 3. Possible extensions of this work\n\nThanks for your insightful suggestion. One possible extension is to incorporate the case of a noisy oracle. For example, **we may consider integrating the techniques used in [1] to handle label noise in the oracle. We will leave it for future work since it is currently out of the scope of this work.**\n\n[1] Zhang, Wentao, et al. \"Rim: Reliable influence-based active learning on graphs.\" Advances in Neural Information Processing Systems 34 (2021): 27978-27990.\n"}, {"review_id": "62ns8OEs1h", "reviewer": "Reviewer_MppE", "summary": "This paper proposes a new active learning strategy based on EMCM principle under the task of graph node-level semi-supervised predictions. The most significant contributions of this paper are 1) extending the EMCM principle to GNNs leading to the MAP estimate correlated (interpretable) acquisition function on graphs, 2) proposing a regularized single-level optimization process to solve the bi-level optimization problem. The comprehensive experiments demonstrate the efficiency and effectiveness of the acquisition function.", "questions": "My questions are listed in weaknesses.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- S1: Great presentations.\n- S2: Equipping the AL acquisition function with Bayesian interpretability is a promising motivation.\n- S3: The techniques and explanations are largely sound.\n- S4: Promising experimental results.", "weaknesses": "- W1: The name of the method makes no sense: expecteD mOdel Change maximizaTion On gRaphs (DOCTOR). It fails to imply the AL strategy, making people hard to correlate this name with the method. I prefer a clear name: Graph Expected Model Change Maximization (GEMCM) that indicates both the task and method.\n- W2: Typo in Page 2, line 55: \"efficacy and efficacy\"\n- W3: Page 3, line 109: \"the nodes are not i.i.d. but linked with edges such that connected nodes tend to have the same label.\" I can't see the correlation between this challenge and the method. I suggest explaining it with the modeling of graphon.\n- W4: Line 218: Can you answer what if the hypothetical label is wrong? It can be the case that we have a high probability with a wrong label and a low change, but a low probability with the true label and a high change. It intuitively make no sense. This is a non-trivial limitation and should be mentioned.\n- W5: Can you discuss to what extent, your approximation is valid? I mean can you bound the difference between your approximation and the expectation?\n- W6: I expect the authors discussing the connection between the proposed method and strict proper scoring rules instead of only the EEM. I also expect the theoretical comparison between the proposed method and entropy minimization (may be in terms of strictly proper scoring rules).\n- W7: I'm confused by the reason why the forward propagation in the equation (2) is a constraint, and why this constraint can be transformed in to the optimization problem in Theorem 3.1. I suggest providing intuitive explanation here.\n- W8: Line 234: Can you adding an explanation for the reason why we maintain the smallest eigenvalues (high-frequency) and corresponding eigenvectors instead of the largest ones? I noticed literature believes that the high-frequency information leads to out-of-distribution problem. Is this belief correlated to your approximations here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$$\\textcolor{red}{\\text{The detailed rebuttal will be given if needed. Please let us know which point needs further clarification after reading this compact response.}}$$\n\nThanks for such a brilliant and constructive review! \n\n1. Model name. The new name is a great suggestion due to the implied interpretable meaning. We will change it to GEMCM.\n\n\n2. Typo. We will change the second \"efficacy\" to \"efficiency\".\n\n3. Graphon modeling. In fact, the non-i.i.d challenge is indeed not directly relevant to our proposed method. We include this challenge mainly because it hinders the direct application of general active learning techniques. We do agree that graphons can come into the picture as a mathematical tool to model large and complex graphs, capturing the non-i.i.d. characteristics of graph-structured data, including dependencies or homophily. We will include a discussion on the graphons.\n\n4. Hypothetical label. The hypothetical label is an artificially-assigned temporary label for an unlabeled node or sample when selecting the query node from the unlabeled pool. It is only an introduced term in the look-ahead model for active learning, and it can be assigned as an arbitrary label in the label space. Eq.(7) iterates all possible hypothetical labels $y_k^+$, and gets the corresponding model change $u(\\tilde{\\Theta}^*) - u(\\Theta)^*$, and weights it with the corresponding predictive probability $\\mathbb{P}(y_k^+ | k)$. Therefore, whether the hypothetical label is aligned with the actual hidden ground-truth label is not relevant here in the node selection stage, and we only care about how large will the final expected model change be if we add each candidacy node from the unlabeled pool into the next round of training. \n\n\n\n5. Bound on approximation error. \nFor the truncated spectral approximation, let us denote that the original Laplacian matrix $\\tilde{\\mathbf{L}} \\in \\mathbb{R}^{n \\times n}$ can be decomposed as $\\tilde{\\mathbf{L}} = \\bar{\\mathbf{V}}\\bar{\\boldsymbol{\\Lambda}}\\bar{\\mathbf{V}}^T$. We only keep the top-$m$ smallest eigenvalues in $\\bar{\\boldsymbol{\\Lambda}}$ and denote the new matrix as $\\boldsymbol{\\Lambda} \\in \\mathbb{R}^{m \\times m}$. Accordingly, the corresponding eigenvectors are kept in $\\bar{\\mathbf{V}}$ so we get $\\mathbf{V}\\in\\mathbb{R}^{n \\times m}$. Then we can now project the node embedding $\\mathbf{u}$ onto the space spanned by these truncated $m$ eigenvectors instead of all the $n$ eigenvectors. Therefore, the approximation error can be formulated as $\\|\\mathbf{V}^T\\mathbf{u} - \\bar{\\mathbf{V}}^T\\mathbf{u}\\|_2$. Assume the node embedding is bounded $\\|\\mathbf{u}\\|_2 \\leq C$. We have,\n$$\\|\\mathbf{V}^T\\mathbf{u} - \\bar{\\mathbf{V}}^T\\mathbf{u}\\|_2 = \\|(\\mathbf{V}^T - \\bar{\\mathbf{V}}^T)\\mathbf{u}\\|_2  \\leq \\|(\\mathbf{V}^T - \\bar{\\mathbf{V}}^T)\\|_F \\|\\mathbf{u}\\|_2 \\leq C \\|(\\mathbf{V}^T - \\bar{\\mathbf{V}}^T)\\|_F = C \\sqrt{n-m}.$$ \n\n\nFor Laplacian approximation, we apply it on top of $\\mathbb{P}(\\boldsymbol{\\alpha} \\mid \\mathbf{y})$. According to the Bernstein-von Mises Theorem, under some regularity conditions and the prior is positive, bounded and twice differentiable, we have $$\\text{sup}_{\\boldsymbol{z}} |\\mathbb{P}(\\boldsymbol{\\alpha} \\leq \\mathbf{z} | \\mathbf{y}) - \\mathbb{P}(\\tilde{\\boldsymbol{\\alpha}} \\leq \\mathbf{z})| \\stackrel{\\text{a.s.}}{\\approx} 0.$$ \n\nHere, $\\boldsymbol{\\alpha}$ is the true posterior without closed-form exact solution and $\\tilde{\\boldsymbol{\\alpha}}$ is the mean of the approximated Gaussian distribution via Laplacian approximation in Theorem 3.3. This result shows that our approximation is quite good from the aspect of the gap in terms of the cumulative distribution function.\n\n\n\n6. Strict proper scoring rules.\nThanks to the generalized active learning acquisition function (Eq.(1) in [1]), the lower bound function $\\mathcal{A}' (k)$ of our original acquisition function  $\\mathcal{A}(k)$ can now be incorporated into this framework. Other methods can also be incorporated into this generalized active learning acquisition function as well. If we set the functional $Q(\\mathbb{P}(\\boldsymbol{\\alpha} | L)) = I(\\mathbb{P}(\\boldsymbol{\\alpha} | L))$ as the mutual information, we can obtain the acquisition function used in [2] that is based on Shannon's entropy. If we set the functional as Eq.(6) in [1], we can get the acquisition function based on the strict proper scoring rules.\n\n[1] Tan, Wei, Lan Du, and Wray Buntine. \"Diversity enhanced active learning with strictly proper scoring rules.\" Advances in Neural Information Processing Systems 34 (2021): 10906-10918.\n\n\n\n7. Constraints in Eq.(2). \nIn Eq.(2), we first do one forward pass of SGC once, and then try to optimize the resulting training loss on the high level without caring about any further forward passes of SGC. Therefore, this one-time forward pass of the SGC model becomes a constraint in Eq.(2) because when we directly optimize the training loss over $\\boldsymbol{\\Theta}$, the output $\\mathbf{U}(\\boldsymbol)$ by the forward pass of SGC must be fixed. Theorem 3.1 focuses on the forward pass of SGC only. Theorem 3.1 provides an optimization perspective of the output (node embeddings) by the forward pass of SGC. Intuitively speaking, when we do forward pass of SGC, we inexplicitly try to minimize the total variations of node embeddings and the node embeddings must be smooth over this graph after the forward pass of SGC model, meaning that the node embeddings for two adjacent nodes should be similar. This corresponds to the homophily assumption of the graphs.\n\n\n8. Maintain the smallest eigenvalues\nIn fact, maintaining the smallest eigenvalues corresponds to applying a low-pass filter. Therefore, when we only keep the smallest eigenvalues, we actually remove high-frequency noises in the graph so that we can keep the most significant information in this graph. Hence, the approximation is completed in this manner. That is why we maintain the smallest eigenvalues. \n\n\n"}, {"review_id": "HHsRdgOYjd", "reviewer": "Reviewer_3rHV", "summary": "This work proposes a novel active learning method for graph neural networks, extending the classic expected model change maximization method in the general active learning setting. The proposed method starts from a new Bayesian interpretation of the SGC model and unifies the training process of GNN models, including both forward and backward passes. Then the authors analyze the challenges of applying EMCM on graphs and use some approximation techniques for efficient computation. Finally, the connection between the proposed method and the expected error minimization method is revealed from the theoretical aspect. ", "questions": "1.\tThe current setting is only designed for node classification tasks. What about link-level and graph-level tasks? The reviewer knows that this question may be out of the scope of this work, but the reviewer is curious about the potential of extending this work to tasks like link predictions. Can we directly use the DOCTOR algorithm? If not, what are the challenges?\n2.\tThe designed algorithm uses a simple sampling algorithm when dealing with the batch active learning setting. What are the possibilities of using other more advanced techniques to choose the query nodes in batches?\n", "limitations": "The reviewer generally agrees with the limitations discussed in Appendix H. This work currently only supports the batch active learning setting with a simple extended version of the sequential active learning solution. However, it is well-known that such a simple extension ignores the correlations between each query node in one batch, as they may reside within the same cluster in the embedding space. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tOriginality: The paper is novel in general, with new EMCM method adaption on graphs and new GNN training understanding from the Bayesian view. The paper is the first work to extend the classic expected model change maximization method in general active learning literature to graph-structured data. The new unified Bayesian view of the GNN training process is also interesting and enlightening to the field. Previous works only consider the feedforward pass of the training when trying to unify the GNNsf from the optimization perspective.\n2.\tQuality: The quality of this work is above average, with a clear motivation and an interesting theoretical analysis of the method. First, the proposed method is strongly motivated by the Bayesian view of the GNNs from the theoretical perspective. Theorem 3.2 reveals the Bayesian interpretation of the general GNN training process, which lays the foundation of the following proposed method. Second, the approximated expected model change in terms of node embeddings can be solved by an elegant closed-form solution in Eq.(11) without re-training the model, which is quite efficient after employing some well-known simple techniques in the spectral graph theory. Third, the paper also theoretically proves that the proposed DOCTOR algorithm will be reduced to the EEM method when some simple assumptions are made, showing that DOCTOR equivalently reduces the expected test error as well, just like the EEM method. Forth, the experiments are convincing, with SOTA baselines (most of them are after 2022) regarding both accuracy and efficiency comparison.\n3.\tClarity: The reviewer finds the paper easy to follow, perhaps since the reviewer is familiar with the related major references in both active learning and GNNs. The overall presentation of the paper is fairly ok, with clear notations and concise statements of the theorems. The case study in the experiments is also illustrative and supports Theorem 3.5 in a more concrete and empirical manner.\n4.\tSignificance: The reviewer thinks this paper makes some contributions to both the active learning community and the GNN community since it connects these two domains and solves a significant problem, that is, how to adapt the classic active learning algorithm to GNNs. This work chooses the expected model change maximization algorithm and solves the potential challenges of extending EMCM on graphs effectively. For researchers in the AL domain, this work provides a new adaption of EMCM specifically designed for GNNs. For researchers in the GNN domain, this work also presents a performance-based AL method for GNNs since most of the current graph active learning literature only focus on uncertainty-based or information-density-based methods without good theoretical interpretation.\n", "weaknesses": "There are several potential improvements in this paper.\n\n1.\tThe background knowledge of EMCM method in general active learning can be elaborated. The details behind Eq.(7) should be provided to give readers without active learning backgrounds more context. For example, the intuition behind the design of Eq.(7) can be discussed.\n\n2.\tFor the efficiency comparison, only three small-scale datasets are used. It is suggested to test the running time performance of the proposed method and other baselines on the large-scale dataset like the ogbn dataset.\n\n3.\tThe conclusion part is short. More future work can be added.\n\n4.\tSome typos should be fixed. For example, in line 219, \"embedding s\" should be \"embeddings\".\n\n5.\tOther comments in questions and limitations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful review! We are glad to know that you found our paper novel, sound, clear, and significant. We hope these responses will address your concerns appropriately. \n\n\n## 1. Background knowledge of EMCM method\n\n**The background knowledge of EMCM method in general active learning is discussed in Appendix B.3.** We introduce a high-level intuitive interpretation of the EMCM principle in AL (Eq.(7)) here. **The model change is a reasonable indicator for reducing the generalization error for the following two major reasons. First, The generalization capability can be changed if and only if the current model is changed. As a result, it is useless to query the instance that cannot update the current model in AL. Second, The data points significantly changing the current model is expected to produce a faster convergence speed to the true model,** and this is the underlying motivation behind the EMCM framework.\n\n\n\n\n## 2. Running time performance of the proposed method and other baselines on the large-scale dataset\n\nIn fact, **we compare the running time performance of the proposed method and other baselines in Appendix G.1.2, including one large-scale dataset, Reddit.** Figure 7 shows that our method is both accurate and efficient. **Just like the suggestions by Reviewer bxJi, we will move Figure 7 to the main body for better presentation.**\n\n\n\n\n## 3. Short conclusion\n\n**We will add more discussion in the conclusion part with the limitations of our method. The limitations and future works are discussed in Appendix H. We will also make sure there are no typos.**\n\n\n## 4. Extensions of the proposed method\n\nFor the extension of the link prediction task of our proposed method, we believe that we cannot directly apply the proposed algorithm because it is challenging to derive the new closed-form solution of the acquisition function on the link-level task since the starting Bayesian interpretation of GNNs only works for the node-level task. We leave the exploration of graph active learning methods for link-level tasks as future work. We also leave the exploration of more advanced batch active learning variants of our proposed method as future work. One possible solution is to incorporate the techniques[1] used in the general batch active learning task for EMCM. Both these directions are very promising extensions of our work.\n\n\n[1] Cai, Wenbin, Muhan Zhang, and Ya Zhang. \"Batch mode active learning for regression with expected model change.\" IEEE transactions on neural networks and learning systems 28.7 (2016): 1668-1681.\n\n"}]

Author rebuttal:

Meta-review: All reviewers acknowledged the contributions of this paper, so I would recommend to accept as spotlight.
Decision: Accept (spotlight)