Information Gain Propagation: a New Way to Graph Active Learning with Soft Labels
Authors: Wentao Zhang
Yexin Wang
Zhenbang You
Meng Cao
Ping Huang
Jiulong Shan
Zhi Yang
Bin CUI
Venue: ICLR 2022 Poster (2022)
Keywords: Active Learning
Graph
Information Gain

Abstract: Graph Neural Networks (GNNs) have achieved great success in various tasks, but their performance highly relies on a large number of labeled nodes, which typically requires considerable human effort. GNN-based Active Learning (AL) methods are proposed to improve the labeling efficiency by selecting the most valuable nodes to label. Existing methods assume an oracle can correctly categorize all the selected nodes and thus just focus on the node selection. However, such an exact labeling task is costly, especially when the categorization is out of the domain of individual expert (oracle). The paper goes further, presenting a soft-label approach to AL on GNNs. Our key innovations are: i) relaxed queries where a domain expert (oracle) only judges the correctness of the predicted labels (a binary question) rather than identifying the exact class (a multi-class question), and ii) new criteria of maximizing information gain propagation for active learner with relaxed queries and soft labels. Empirical studies on public datasets demonstrate that our method significantly outperforms the state-of-the-art GNN-based AL methods in terms of both accuracy and labeling cost. 

Published as a conference paper at ICLR 2022
INFORMATION GAIN PROPAGATION: A NEW WAY TO GRAPH ACTIVE LEARNING WITH SOFT LABELS
Wentao Zhang', Yexin Wang'. Zhenbang You', Meng Cao², Ping Huang? Jiulong Shan", Zhi Yangl., Bin Cuil.3,4
I Schoool of CS, Peking University AApple
3 National Engineering Laboratory for Big Data Analysis and Applications
"Institute of Computational Social Science Peking University (Qingdao), China
1 wwentao.zang, yexinwang, zhenbangyou, liyang.cs, yangzhi, bin.cui pku.edu.cn menggaa, Huang_ping jishan) @apple.com
ABSTRACT
Graph Neural Networks (GNNs) have achieved great success in various tasks, but their performance highly relies on large number of labeled nodes, which typically requires considerable human effort. GNN-based Active Learning (AL) methods are proposed to improve the labeling efficiency by selecting the most valuable nodes to label. Existing methods assume an oracle can correctly categorize all the selected nodes and thus just focus on the node selection. However, such an exact labeling task is costly, especially when the categorization is out of the domain of individual expert (oracle). The paper goes further, presenting a soft-label approach to AL GNNs. Our key innovations are: i) relaxed queries where a domain expert (oracle) only judges the correctness of the predicted labels (a binary question) rather than identifying the exact class (a multi-class question), and ii) new criteria of maximizing information gain propagation for active learner with relaxed queries and soft labels. Empirical studies on public datasets demonstrate that our method significantly outperforms the state-of-the-ans GNN-based AL methods in terms of both accuracy and labeling cost.
INTRODUCTION
Graph Neural Networks (GNNs) have recently achieved remarkable success in various graph-based tasks, ranging from traffic networks, biology. to social networks (Zhang et al,, 2020b Wang et al.. 2019 Li al. 2019 Do al. 2019 Wu et al. 2020b). Despite their effectiveness and popularity, GNNs typically require a large amount of labeled data to achieve satisfactory performance. However, obtaining these labels is time-consuming. laborious, and costly process. Therefore, how do this cconomically and efficiently has attracted great attention both in academia and industry. One of the most popular strategies to tackle this challenge Active Learning (AL) (Aggarwal et al.) 2014). By combining model training and node selection for labeling, AL significantly reduces labeling cost by selecting the most valuable nodes to label.
However, previous AL methods assume the hard label (namely the exact label, that is, the label
specifying the exact class of the node) can always provided by the oracle. As illustrated in Fig. [ for any selected node, the active learners in the aforementioned methods ask questions like "which
category does it exactly belong to?". Such queries and assumptions exceed the capability of oracle in many labeling tasks requiring domain knowledge. For example, the task in to leverage the citation graph to infer the labels of the arXiv papers into 172 arXiv subject areas (a single-label, 172-class classification problem). In this example, specialist/expert in the subject areas of machine learning is incapable of labeling query instances with subject areas of finance (such as mathematical finance computational finance), which is out of his domain knowledge.
100M is
In this paper, we propose a novel active learning paradigm for GNNs in which only soft labels are required. Two salient features of paradigm are follows:

---

Published as a conference paper at ICLR 2022
dtritngy
Does it belong to the first callgooy?
01.0,00
[0, 04 0.6)
05
04
Crode
Qusry
0
Model Predician
Which cotegory does elactly belong
Ground truth label
[0.7, 0.16, 0.14]
Prov bus
(O) =H077 016,, Q144 H11/3, 1/3 1/3)
Figure 1: An example of our new node labeling strategy.
Figure 2: An example of IGP.
First, we propose relaxed queries where domain expert (oracle) only judges the correctness of the predicted labels (by GNN models) rather than the exact categorization. Specifically, we propose to select the class label with the highest predicted probability and then ask the oracle to judge whether the class label is correct rather than directly asking for the exact class label. In this way, the multi-class classification task is relaxed into a binary-class classification task for the oracle. Under such queries, if the model prediction is incorrect (we assume the oracle does not make mistakes), we annotate the node with the soft label by re-normalizing the model predicted softmax outputs over the remaining classes. As illustrated in Fig.1, we allow relaxed queries such as "Does the sample belong this class?" (e.g., the first class in Fig. D. since this query is specific to the domain of experts, hence concerned, no previous AI. methods can deal with such
more ready to be answered. As far relaxed queries.
Second, the node selection criteria in previous AL methods are specially designed for hard-labeling oracles. As one of the most commonly used AL query strategies, uncertainty sampling queries the labels of the nodes which current model is least certain with, ensuring the largest entropy reduction on a single node when given the hard label from oracle. However, under our relaxed queries, we prove that the uncertainty sampling cannot guarantee the largest information gain (i.e., entropy reduction) on single node. In this paper, we propose new criterion to explicitly maximize information gain propagation (IGP) for active learners with relaxed queries and soft labels on graph. As shown in Fig. 2 the labeled nodes (with color) propagate their label information with different influence magnitude and then reduce the uncertainty of adjacent unlabeled nodes (without color). Considering the influence propagation in GNNs, we select the nodes that can maximize expected information gain in total under the relaxed queries, i.e., reducing the aggregated uncertainty a neighborhood region beyond single node. To the best of our knowledge, this is the first work to propose the information gain propagation with relaxed queries, and showing that it is highly effective.
In summary, the core contributions of this work are the following: First, we provide paradigm for GNNs methodology with relaxed queries and soft labels. Second, we propose a novel node selection criterion that explicitly maximizes propagation of information gain under the new AL paradigm on GNNs. Third, experimental results show our paradigm significantly outperforms the compared baselines by large margin in five open graph datasets.
AL
2 PRELIMINARY
2.1 PROBLEM FORMULATION
Let G (V.E) with D = N nodes and |8| M edges be the graph, and c is the number of classes. X = .2.... NN) is the node feature matrix, the one-hot vector y: E R and and æ; E Rd are the ground-truti label and node feature for node E V, respectively. We consider a general AL setting in this work. Suppose the full node set V is partitioned into training set Veraens validation set Veal. and test set Veest, and Veroin
further be partitioned into the labeled set V and unlabeled set Vu, respectively. Given the labeling size B, the loss function E, the goal of graph-based AL is to select subset Vi Vtrain label, so that the model f trained with the supervision of Vi can get the lowest loss on Viest!
arg min EryeV [e (yi, Ut)) V
(1)
where is the softmax outputs of node 2 given by the model f.
Different from the previous setting, B is the labeling cost (i.c., money) rather than the size in our new scenario. As the experts are hard to annotate the node out of their domain, assume the conventional
2

---

Published as a conference paper at ICLR 2022
query cost 1 times much our relaxed query for each selected node. Correspondingly, the objective in our new scenario is
arg min Eeees [e (3 9k)]:
(2)
Vi (V))
where M(V) is the labeling cost for annotating Vi, and focus on being GNNs due to their state-of-the-art performance in many semi- ami-suuervised node classification tasks.
2.2 GRAPH NEURAL NETWORKS
Unlike the images, text or tabular data, where training data are independently and identically distributed, samples connected by edges in the graph, and each node in GNN aggregate the node embedding or feature from its neighbors to enhance their embedding along edges. Let (A,X(A) W()) be any GNN, where A is an adjacency matrix, X is the feature matrix of lo-th layer, and ( are the learned weights of k-th layer.
Taking the widely used Graph Convolution Network (GCN) Kipf & Welling 2017a as an example, each GCN layer can be formulated as:
x = = w()) = 5 'A (xx))))))))))))
(3)
where X (and ( is the original node feature, (*) and X (k+1) are the embeddings of layer k and k + respectively. Besides, D is the diagonal node degree matrix for normalization and À A +Iy is the adjacent matrix with self connection, where IN is the identity matrix. Compared with the (x(()
DNN layer which formulated as ( = = (())., the feature matrix ( will be firstly
enhanced with the feature propagation operation D x (4), and then boosts the semi-supervised node classification performance by getting more nodes involved in the model training.
2.3 ACTIVE LEARNING
Common AL. AL can improve labeling efficiency by selecting the most valuable samples to label.
Considering the informativeness, Uncertainty Sampling (Yang et al. [005 Zhu et al. 20088) selects the nodes which has the most uncertain model prediction. Based on ensembles (Zhang al., (220aa). Query-by-Comminee
(Burbidge et al. 2007 Melville & Mooney 2004) trains committee of models, and selects samples according to the extent to which the models disagree. Furthermore, Density- based (Zhu et al. 2008: TTagg et 2002) and Clustering-hased (Du et al. 2015 Nguyen & Smeulders 2004) and Diversity- based (Wu et al.] 2020aa Jiang & Gupta| 2021) methods can effectively select the most representative samples. All the methods above
proposed for binary multi-class classification, and some methods (Qi et al. 2008 Yan & Huang 2018) are proposed for the multi- label classification problem. Besides, considering the class imbalance, some methods (Aggarwal
et al. 2020 Attenberg & Provost 2010) are also proposed to tackle this issue with AL.
GNN-based AL. Despite the effectiveness of common AL methods, it is unsuitable to directly apply them to GNNs since the characteristic of influence propagation has not been considered. To tackle this issue, both AGE (Cai al., (2017) and ANRMAB (Gao al. 2018) introduce the density of node embedding and PageRank centrality into the node selection criterion. SEAL (Li et al. 2020 devises novel AL query strategy in an adversarial way, and RIM (Zhang al. 202 considers the noisy oracle in the node labeling process of graph data. Besides, ALG (Zhang et 102 proposes maximize the effectiveness of all influenced nodes of GNNs. Recently, Grain (Zhang al. 2021c) introduces new diversity influence maximization objective, which takes the diversity of influenced nodes into consideration.
Both AGE (Cai et al.) 2017) and ANRMAB (Gao et al. 2018) are designed for AL on GNNs, which adopt the uncertainty, density, and node degree to select nodes. ANRMAB improves AGE by introducing multi-armed bandit mechanism for adaptive decision-making, Considering the high training time of GNN, ALG (Zhang et al. 2021a) decouples the GNN model and proposes a new node selection metric that maximizes the effective reception field. Grain (Zhang et al. 202 further generalizes the reception field to the number of activated nodes in social influence maximization and introduces the diversity influence maximization for node selection. However, all these AL methods
3

---

Published as a conference paper at ICLR 2022
assume the oracle knows the information of all categories, thereby being able to correctly annotate all the selected nodes. This is impractical the oracle encounters some areas that they are not familiar with, especially when the number of categories is large. IGP is the first work actively labeling graph data under domain-specific experts.
PROPOSED METHOD
This section presents IGP, the first graph-based AL framework that considers the relaxed queries and soft labels. IGP can operate on any GNN model f- We measure the information gain of selecting a single node in Sec. 3.1 To extend the information gain of single node to the full graph, firstly estimate the influence magnitude of graph propagation in Sec. [.2 and then combine it with the
information gain and introduce the new criterion: information gain propagation in Sec. 3.3
Last, we
propose to select nodes which can maximize the information gain propagation in Sec. 3.4
3.1 INFORMATION GAIN
Different from the previous annotation method, which asks the oracle directly provide annotated class I, the oracle in IGP only needs to judge whether the model prediction y is correct. Rather than discard the incorrect prediction, propose that both the correct and incorrect predictions will provide the information gain and thus enhance the label supervision.
An oracle is required answer whether the model prediction is correct, i.e., ý belongs to class I. After the judgement of the oracle, the uncertainty of the node labels will be decreased. Therefore, we define the normalized soft label by combining the model prediction and oracle judgement follows. Definition 3.1 (Normalized Label). For node v, the soft label (model predicted softmax output) is denoted as ÿi [a1, ..,..., a.l. The pseudo label (denoted as l) is set the class with the highest value in yi- After the oracle judges whether vi belongs to class I, each element dg in the normalized soft label y (d1,0/y -., d defined
(t = ap1(t=)) 20
Us belongs to class 1 does not belong class
ai
After the query, Di is updated as the normalized soft label of by Eq. (See more details in Appendix B
The oracle may agree with the pseudo label (denoted as v,+), or disagree (denoted as us u--). In either cases, the entropy drops.
The expected information gain (IG) is calculated based on these two cases.
Definition 3.2 (Information Gain (IG)). For node the IG of annorating it is defined as
TG(v:) H():)) P(v:-)H((j v-)),
(5)
where H is the entropy (well-known in the information theory), e.g., H(Ú.) = - ap log Op (log always stands for log, in this paper). Therefore, H and H stand for the entropy of vi before and after annotation respectively. Also, H H 0,+)) and H (3/. u,-) are the two cases of H H()) where + and U, occurs respectively.
IG is exactly the expectation of entropy reduction, proved in Appendix C
The confidence of the model in the pseudo label is shown in the soft label. Hence, before the annotation, this is good measurement for the probability that the oracle will agree with the pseudo label, namely P P(v++).
Here following theorem shows the difference between IG and entropy. Theorem 3.1. The node with the highest entropy not necessarily the node that brings the highest IG.
The proof of this theorem be found in Appendix A
More examples about IG in differing cases, that is, the oracle may agree or disagree with the pseudo label, be found in Appendix
4

---

Published as a conference paper at ICLR 2022
3.2 INFLUENCE MAGNITUDE ESTIMATION
Each newly annotated node will propagate its label information to its k-hop neighbors in k-layer GNN and correspondingly influences the label distribution of these nodes. Since the influence of node on its different neighbors can be various, we measure it by calculating how much change in the input label of node U; affects the propagated label of node vy after k-steps propagation (Wang Leskoved 2020 Xu et al., 2018).
Definition 3.3 (Influence Magnitude). The influence magnitude score of node vi on node U4 after k-step propagation the Ll-norm of the expected Jacobian matrix Iy(Ug, vs = Blax!") /ax! |0] Formally, we normalize the influence magnitude score as:
1y(25, Vi,k) Iy(0,, ve. EnDev Ly(Ug, Vw: k)
(6)
For k-layer GNN, the influence magnitude score (U, . Ui k) captures the sum over probabilities of all possible influential paths with length of from node v to ej. Intuitively, node e; will influence vy by a larger extent and thus [U 0c, k) larger if o; is easier to achieve at vy after the random walk. In our AL setting, larger Ty(1) vs, k) means the label distribution of node vy will be influenced more by node 24 oz is labeled.
3.3 INFORMATION GAIN PROPAGATION
For k-layer GNN, the supervision signal of one node can be propagated its k-hop neighborhood nodes and then influences the label distribution of these neighbors. Therefore, it is unsuitable to just consider the information gain of the node itself in the node selection process. So, extend the information gain of a single node defined in Def. 3.2 to its k-hop neighbors in the graph. We firstly combine the influence magnitude with the normalized soft label and then measure the information gain propagation of all the influenced nodes. Concretely, the information gain propagation of node dy from the labeled node 2 is defined as follows.
Definition 3.4 (information gain propagation). Given the model predicted softmax outputs of node vn the influence magnitude I Ly(1,, vi, k) of node o, on új, the information gain propagation of node v from labeling node vú is defined as:
TGP( Us, k) = -H
Σ Ne EV
Ty(U, Un, k)
Σ
Ty(Uy, Um k)
(7)
Since the soft label ÿ/ is unavailable for node u, before the annotation, the expected information gain propagation (IGP) is calculated by
IGP v. k) = P(r,,) n4 k, x2+ + P(v;-) U/ k, 0;
(8)
where IGP(u, Us k. u.-) is the IGP when the oracle agrees with the pseudo label. In this case, g/ a one-hot vector according to E.q.
3.4 MAXIMIZING INFORMATION GAIN PROPAGATION
To maximize the uncertainty of all the influenced nodes in the semi-supervised GNN training, aim to select and annotate a subset Vi from V so that the maximum information gain propagation can be achieved according Eq. p Specifically, we optimize this problem by defining the information gain propagation maximization objective as below.
Objective. Specifically, we propose to maximize the following objective:
max F(M) Σ Σ IGP(e,, 8, s.t. Vi C [M] B.
(9)
V (yERF(())
where (F((v)) is the receptive field of node 24 i.c., the node itself with its k-hop neighbors in k-layer GNN. Considering the influence propagation, the proposed objective can used to find a subset V that can maximize the information gain of all influenced nodes as more possible.
5

---

Published as a conference paper at ICLR 2022
Update
Influence Magmotudd
Eoasie
Exser
Propegaled Information Gain
Redaxed
Timin
Vi Soft Labels
Information Gain
Normatized Labhel
GNN
Maximizing IGP
Selected Nodes
Model Training
Node Selection
Node Labeling
Figure 3: An overview of the proposed IGP framework.
Algorithm 1: Working pipeline IGP
Input: Initial labeled set Vo, query batch size b.
Output: Labeled set Vi
Stage 1: Node Selection
Vi = Vu. V/- =
for t 10=1,22 1,...., do
Select the most valuable node: o2 = arg max AV
F(UU
Vi = 142 U {u:). V/ = V Jo Verain = Verain \ {wi):
Stage 2: Node Labeling
for U; E 1/ do
Judge the correctness of the predicted pseudo label Di:
5t correct (agreed by the oracle) then
Labeling v; with D;' according to Eq.
11
else
Labeling vs with D'' according to Eq.
12
Vi Vi \. {1 Verain
Verain U {
14 Return VA
IGP FRAMEWORK
4.1 FRAMEWORK OVERVIEW
As shown in Fig. 3 for each batch of node selection, IGP first trains the GNN model with the soft labels. With the model prediction, IGP measures the expected information gain of labeling each node. Considering both the influence magnitude and information gain, IGP further measures information gain propagation of each unlabeled node and selects batch of nodes that can maximize information gain propagation on the graph. After that, with the relaxed queries, the oracle only judges the correctness of the model prediction, and the label distribution will be normalized correspondingly. At last, we re-train the GNN model with update the model prediction. The above process is repeated until the labeling cost B runs out.
4.2 WORKING PIPELINE
Node Selection. Without losing generality, consider batch setting where nodes selected in each iteration. Algorithm 1 provides sketch of our greedy selection method for GNNs. Given the training set Virain. and query batch size b, we first select the node v, which generates the maximum marginal gain (Line 3). We then update the labeled set V/, the oracle annotated set V,, and the training set Verain (Line 4). This process is repeated until a batch of b nodes have been selected. Note that the normalized soft label ÿ/ is unavailable before the node labeling process. For better efficiency, we assume 인 is the model predicted soft label yi in the node selection process. If yi not confident (f.e...0.4.0.330.. for classifasiiii problem), it will be of little influence the label distribution of its neighbors. On the contrary, yi is closer to ÿ if it confident. Consequently, is reasonable make such assumption.
Node Labeling After getting a batch of the selected node-set V4. we acquire the label from an oracle. As introduced before, different from previous works which require the oracle annotate the hard

---

Published as a conference paper at ICLR 2022
label directly, the oracle in our framework only needs to judge the correctness of the pseudo label ya (Line 8). If Di is correct, we update its soft label ğ according to Eq. 4 (Line 10). Note that we can still get information gain even if Y; is incorrect. For any node U with an incorrect pseudo label, firstly update its soft label ý; (Line 10). After that, we remove it from V/ and add it to Vtrain (Line 13). In this way, this node has the chance be re-selected in the next batch. Note that the model will produce a different label given the fact that the oracle rejects the previously predicted label.
Model Training Intuitively, node with smaller entropy contains contributes more the training process. In other words, a one-hot label contributes most, while other normalized soft labels also provide weak supervision. For GNN model training, we use the weighted loss function as follows
C
Σ HC
0f log Di +
Volog
(10)
(O
where a is hyper-parameterr which controls the importance of the incorrectly predicted nodes by the model. Note that the labeled set has two types of labels: 1) one-hot hard labels (i.e., H (vt) = 0), which is correctly predicted by the model: 2) soft labels (i.c., H (vy) + 0), which has incorrect model prediction but also provides weak supervision. We adopt the KL divergence as the loss function to learn from the weak supervised soft label in both cases (cross-entropy is just special case of KL. divergence). Note that KL divergence measures the distance between the ground truth and the current prediction, and is especially appropriate for methods with a basis of information theory.
4.3 EFFICIENCY OPTIMIZATION
By leveraging some recent works on scalable and parallelizable social influence maximization (Aral & Dhillon 2018), we could enable IGP to efficiently deal with large-scale graphs. The key idea is to identify and dismiss uninfiuential nodes to dramatically reduce the amount of computation for evaluating the information gain propagation. For example, distribution of random walkers throughout the nodes (Kim et al. 2017) to filter out a vast number of uninfluential nodes.
use the node degree or the
EXPERIMENTS
5.1
EXPERIMENTAL SETTINGS
Datasets. We evaluate IGP in both inductive and transductive settings (Hamilton et al. 2017): three citation networks (i.e.. Citeseer, Cora, and PubMed) (Kipf & WWellng 2017a). one large social network (Reddit), and one OGB dataset (ogbn-arxiv).
GNN Models. We conduct experiments using the widely used GCN model and demonstrate the generalization of IGP on other GNNs such as SGC (Wu et al. 2019), APPNP (Klicpera al. 2019) and MVGRL (Hassani & Khasahmadi 2020).
Baselines. We compare IGP with the following baselines: Random, AGE (Cai 2017
ANRMAB (Gao et al. 2018), GPA (Hu et al. 2020), SEAL (Li al. 2020 ALG (Zhang et al.
2021ap, and GRAIN (Zhang et al., 2021c)
Settings. For each method, we use the hyper- peree--rramtter tuning toolkit (Li et al. 2021a b) or follow the original papers to find the optimal hyper-parane parameters... To eliminate randomness, we repeat each method ten times and report the mean performance. Specifically, for each method, we chooses small set of labeled nodes as an initial pool two nodes are randomly selected for each class.
5.2 PERFORMANCE COMPARISON
End-to-end Comparison. We choose the labeling budget as 20 labels per class to show the end-to- end accuracy. Table I shows that GRAIN, ALG, AGE, and ANRMAB outperform Random in all the datasets, as they are specially designed for GNNs. GRAIN and ALG perform better than other baselines except for IGP because they consider the RF. However, IGP further boosts the accuracy by a significant margin. Remarkably, IGP improves the test accuracy of the best baseline, i.c., GRAIN, by 1.6-2.2% the three citation networks, 0.9% on Reddit, and 0.6% ogbn-arxiv.
7

---

Published as a conference paper at ICLR 2022
Table 1: The test accuracy (%) on different datasets with the same labeling budget.
Method
Citeseer
Reddit
ogbn-arxiv
Random
78.8(008)
70.8(+0.9)
78.9(=0.6)
(1+00))
68 (8.2(=0.4)
AGE
82.5( 71.4(+0.0)
79.4(-04)
91.6(+0.3)
68.9(+0.3)
ANRMAB
82.4(=0.5)
70.6(+0.6)
78.2(=0.3)
91.5(+0.3)
68.7(=022)
GPA
-2.8(-04))
71.6(+0.4)
79.9(-0.5
91.8(+0.2)
69.2(+0.3)
SEAL
72.1(10.4) 0.5)(-055)
80.3(104)
69.5(10.11) 92.1(10.3)
ALG
73.6(40.5)
92.4(10.3)
70.1(:0.2)
GRAIN
04.2(-0.3)
74.2(40.3)
818(-02)
70.3(=0.2) 92.5(+0.11)
IGP
-6,4
75.3.10.3)
93.4(10.2)
70.9(10.3)
8.5
Text accuracy(
IGP
Text 78
RANDOM
CDA
55
Size labeling budget
120
Size of labeling budget
Size of labeling budget
(a) Cora
(b) Citescer
(c) PubMed
Figure 4: The test accuracy across different labeling budgets for model training.
Accuracy under Different Labeling Budgets. To show the influence of the labeling budget, we test the accuracy of different AL methods under different labeling budgets on three citation datasets. Concretely, we range the budgets oracle labels from 2C to 20C (C the number of classes) and show the test accuracy of GCN in Figure 4 The experimental results demonstrate that with the increase of labeling budget, the accuracy IGP grows fairly fast, thereby outperforming the baselines with an even greater margin.
Generalization. addition to GCN, IGP can also be applied to a large variety of GNN variants. GCN, SGC, MVGRL, and APPNP are four representative GNNs (Chen et al.) (202)) which adopt different message passings. Unlike the coupled GCN, both SGC and APPNP are decoupled, while their orderings when doing feature propagation and transformation are different. Besides, MVGRL is a classic self-supervised GNN. We test the generalization ability of IGP by evaluating the aforementioned four types of GNNs on 20C (C' the number of classes) nodes selected by IGP and other baselines in the AL scenario, and the corresponding results are shown in Table 2 The results suggest that IGP consistently outperforms the other baselines, regardless of whether the GCC is decoupled. Moreover, the result also shows our proposed method IGP can significantly outperform the compared baselines on the top of more sophisticated self-supervised GNN such as MVGRL (Hassani & Khasahmadi 2020). As shown in the table, the test accuracy of IGP could outperform ALG and GRAIN by more than 1.8% on PubMed. Therefore, we draw conclusion that IGP can generalize different types of GNNs well.
Ablation study, IGP combines informative selecting, informative training, and information quantity in the method. To verify the necessity of each component, evaluate IGP on GCN by disabling one component at a time. We evaluate IGP: (i) without the node labeled with soft label when training (called "No Informative Training ITT)"); (ii) without the information gain propagation when selecting nodes (called "No Informative Selection (IS)"); (iii) without the influence magnitude and regarding the information among all the nodes as the same (called "No Information Quantity (IM)")x(iv) without the normalized soft label and set the soft label uniformly (called "No Normalized Label (NL)"); Table displays the results of these three settings, and from the table we can learn the following information. 1) If informative training is ignored, the test accuracy will decrease in all three datasets, e.g., the accuracy gap as large as 2.9% on PubMed. This is because informative training help utilizing the information of the nodes labeled by probability. 2) Lacking information selecting will lead to worse accuracy, since the information gain the nodes can not only benefit itself but also its neighbors in the graph. It is more important than other components since removing the information selecting will lead to a more substantial accuracy gap. For example, the gap on Cora is 2.5%, which is higher than the other gap (2.3%). 3) Information quantity also significantly impacts model accuracy on all datasets, because it will lead to a wrong preference on the nodes with larger degree, although some of them have little influence other nodes. 4)lf remove normalized label and set the soft
8

---

Published as a conference paper at ICLR 2022
Table 2: Test accuracy of different models on PubMed.
Method
SGC
APPNP
GCN
MVGRL
Random
77.6(10.88
79.2(110.6
78.9(10.6)
79.3(10.5)
AGE
78.8(+0.5)
79.9(10.5)
79.4(10.4)
79.9(10.4)
ANRMAB
77.8(+0.4)
78.7(+0.5)
78.2(+0.3)
78.9(+0.3)
GPA
79.5(1:0.6)
80.((10.4)
79.9(110.5)
80.4(10.3)
SEAL
79.8(=0.55)
80.5(+0.5)
80.3(+0.4)
80.7(+0.3)
ALGG
80.5(++0.4)
81.2(+0.5)
80.9(+0.3)
81.3(+0.2)
GRAIN
81.1(+0.3)
82.0++0.4)
8188(+0.2)
82.1(+0.1)
IGP
83.2(10.6)
83.7CEO.3)
83.6(10.55
83.9(10.4)
Table 3: Influence of different components in test accuracy(95)
Method
Cora
A
Citeseer
A
PubMed
A
No IT
84.1(=0.7)
-2.3
73.2(+0.3)
-2.6
80.7(=0.5)
-2.9
No IS
83.9(=0.5)
-2.5
73.1(=0.4)
-2.7
80.4(=0.4)
-3.2
No IM
84.5(=0.6)
-1.9
73.6(#0.5)
-2,2
81.5(=0.6)
-2.1
No NL
84.4(=0.5)
-2.0
73.4(+0.3)
-2.4
81.3(=0.4)
-2.3
IGP
86.4(110.6)
75.8(1-0.3)
83.6(=0.55)
IGP
AGE
Soft label
Hard label
None label
-50
-00
-100
-100
40
20
80
-40
20
40
80
Figure 5: The node distribution with different labels of different methods on the Cora dataset.
label uniformly, the test accuracy will decrease apparently. Although the performance degradation is smaller than no IT and no IS, the results still show the necessity of normalized label.
Interpretability To show the insight of IGP, we evaluate and draw the distribution of the nodes with soft labels (in red color) and hard labels (in blue color), also those without labels (in gray color) for two methods: AGE and IGP when the labeling budget 6C for Cora in GCN, the more information entropy the nodes have, the smaller its radium (one-hot labeled node has the largest radium). The result in Figure 5 shows that compared to AGE, IGP enough labeled nodes with a balanced distribution, both in probability and one-hot, which could explain the better performance of NC-ALG in node classification. We also show the influence on information entropy in Appendix.
CONCLUSION
This paper presents Informatioin Gain Propagation (IGP), the first GNN-based AL method which explicitly considers AL with soft labels. Concretely, we provide new way for active learners to exhaustively label nodes with a limited budget, using combination domain experts and
GNN model. IGP allows us to use relaxed queries where domain expert (oracle) only judges the correctness the predicted labels rather than the exact categorization, and ii) new criteria of maximizing information gain propagation for the active learner with relaxed queries and soft labels. Empirical studies on real-world graphs show that our approach outperforms competitive baselines by large margin, especially when the number of classes is large.

---

Published as a conference paper at ICLR 2022
7 REPRODUCIBILITY
The source code of IGP can be found Github ensure reproducibility, we have provided the overview of datasets in Section F.1 and Table 4 in Appendix F The detailed hyperparameter settings for our IGP can be found in Appendix F.2 Our experimental environment presented in Appendix F2 and please refer "README.md the Github repository for more details.
To
ACKNOWLEDGMENTS
This work is supported by NSFC (No. 61832001, 61972004), Beijing Academy of Artificial Intelligence (BAAI), and PKU-Tencent Joint Research Lab. Bin Cui is the corresponding author.
REFERENCES
Charu C Aggarwal, Xiangnan Kong, Quanquan Gu, Jiawei Han, and $ Yu Philip. Active learning: survey. In Data Classification: Algorithms and Applications, pp. 571-605 CRC Press, 2014.
Umang Aggarwal, Adrian Popescu, and Céline Hudelot. Active learning for imbalanced datasets. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 1428 1438-1437, 2020.
Sinan Aral and Paramveer S Dhillon. Social influence maximization under empirical influence models. Nature human behaviour, 2(6): -8277,5--2277 2018.
Josh Attenberg and Foster Provost. Why label when you search? alternatives to active learning for applying human resources to build classification models under extreme class imbalance. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 423 432, 2010.
Robert Burbidge, Jem Rowland, and Ross D King. Active learning for regression based on query by committee. In International conference on intelligent data engineering and automated learning, pp. 209-218. Springer, 2007.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint arXiv: I 7050 705.05585, 2017.
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented mlps. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 750-760, 2019.
Bo Du, Zengmao Wang, Lefei Zhang, Liangpei Zhang, Wei Liu, Jialie Shen, and Dacheng Tao. Exploring representativennss and informativeness for active learning. IEEE transactions cybernetics, 4-414:44- 2015.
Li Gao, Hong Yang, Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network representation learning. In Proceedings of the Twenty-Sevnnth International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, 2142-2148, 2018.
William L.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference Machine Learning, pp. 4116-4126. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2022
Shengding Hu, Zheng Xiong. Meng Qu, Xingdi Yuan, Mare-Alexandia Côté, Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Heinrich Jiang and Maya R. Gupta. Bootstrapping for batch active sampling. In KDD '21 The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 3086-3096, 2021.
Seungkeol Kim, Dongeun Kim, Jinoh Oh, Jeong-Hyon Hwang, Wook-Shin Han, Wei Chen, and Hwanjo Yu. Scalable and parallelizable influence maximization with random walk ranking and rank merge pruning. Information Sciences, 115:171-189, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017a.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. 2017b.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations. ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Jia Li, Zhichao Han, Hong Cheng, Jiao Su, Pengyun Wang, Jianfeng Zhang, and Lujia Pan. Predicting path failure in time-evolving graphs. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1279-1289, 2019.
Yang Li, Yu Shen, Wentao Zhang, Yuanwei Chen, Huaijun Jiang, Mingchao Liu, Jiawei Jiang, Jinyang Gao, Wentao Wu, Zhi Yang, al. Openbox: A generalized black-box optimization service arXiv preprint 0rXiv:2106.0042/1 2021a.
Yang Li, Yu Shen, Wentao Zhang, Jiawei Jiang, Bolin Ding, Yaliang Li, Jingren Zhou, Zhi Yang, Wentao Wu, Ce Zhang. et al. Volcanoml: Speeding up end-to-end automl via scalable search space decomposition. arXiv preprint arXiv:2107.0886) 2021b.
Yayong Li, Jie Yin, and Ling Chen. Seal: Semisupervised adversarial active learning on attributed graphs. IEEE Transactions on Neural Networks and Learning Systems, 32(7)3316--3147, 2020.
Prem Melville and Raymond Mooney. Diverse ensembles for active learning. In Proceedings of the (wenty-first international conference on Machine learning, pp. 74, 2004.
Hieu T Nguyen and Arnold Smeulders. Active learning using pre-clustering. In Proceedings of the twenty-first international conference on Machine learning, pp. 79, 2004.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances Neural Information Processing Systems, pp. 8024-8035, 2019.
Guo-Jun Qi, Xian-Sheng Hua, Yong Rui, Jinhui Tang, and Hong-Jiang Zhang. Two-dimensional active learning for image classification. 2008 IEEE conference on computer vision and pattern recognition, pp. 1-8. IEEE, 2008
Min Tang, Xiaoqiang Luo, and Salim Roukos. Active learning for statistical natural language parsing. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 120-127, 2002.
Hao Wang, Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du Han Wu, and Wen Su. MCNE: an end-to-end framework for learning multiple conditional network representations of social network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1064-1072, 2019.
11

---

Published as a conference paper at ICLR 2022
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propagation. CoRR, abs/2002.06755, 2020.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 6861-6871, 2019.
Jian Wu, Victor S. Sheng, Jing Zhang, Hua Li, Tetiana Dadakova, Christine Leon Swisher, Zhiming Cui, and Pengpeng Zhao. Multi-label active learning algorithms for image classification: Overview and future promise. ACM Comput. Surv., 53(2):28: 1-28:35, 2020a.
Shiwen Wu, Fei Sun, Wentao Zhang, and Bin Cui. Graph neural networks in recommender systems: survey, arXiv preprint wrXiv:2011.02200 2020b.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, pp- 5449-5458, 2018.
Yifan Yan and Sheng-Jun Huang. Cost-effective active learning for hierarchical multi-label classification. In IJCAI, pp. 2962-2968, 2018
Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. International Journal of Computer Vision, 11(())113-12)) 2015.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Wentao Zhang, Jiawei Jiang, Yingxia Shao, and Bin Cui. Snapshot boosting: fast ensemble framework for deep neural networks. Science China Information Sciences, 63(1):1-12, 2020a.
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 '21: International Conference Management of Data, Virtual Event, China, June 20-25, 2021, pp. 2376,2374, 2021a. la.
Wentao Zhang, Yexin Wang, Zhenbang You, Meng Cao, Ping Huang, Jiulong Shan, Zhi Yang, and Bin Cui. Rim: Reliable influence-ber based active learning on graphs. Advances in Neural Information Processing Systems, 34, 2021b.
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. 2021c
VLDB Endow,, 14(11):2473-244
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning graphs: A survey. IEEE Transactions Knowledge and Data Engineering, 2020b.
Jingbo Zhu, Huizhen Wang. Tianshun Yao, and Benjamin K Tsou. Active learning with sampling by uncertainty and density for word sense disambiguation and text classification. In Proceedings of the 22nd International Conference Computational Linguistics, pp. 1137-1144, 2008.
A PROOFS
Theorem A.1. The node with highest entropy (in terms of the soft label given by the model) is not necessarily the node that brings highest expected information gain.
Let us consider three classification problem. Assume there is node with soft label [] 2a, a, a).
where 0 < v 1/2 so that 1 2a 2 a. Therefore, the entropy of is given by
H (s) - 2a) log(1 - 2a. log a alog -(1 1 2a) log(1 2a) 2a Baloge (11)
12

---

Published as a conference paper at ICLR 2022
When the oracle gives negative answer, the soft label will become [0, 0.5, 0.5], and thus the entropy
will become -0.5 log 0.5 0.5 log 0.5 = log 2 = 1. Consequently, the expected information gain of is given by
( = (1 - (H) - 0) + 2a (+)) - 1) = H(s) 2a
(12)
Take the derivatives of the above two variables, we have
dH) da 1-(1 2a) log(1 2a) log a]'
{[(1 2a) log(1 - 2a)] + 2(a log a)'}
1
1
[Log(1 -2a) + 1n
* (-2) + 2(log a
(13)
In
2[log(1 1 -2a) loog a|
2og 1 1-24
aTG(s)
d(H((s) 20)
da
da (H(s) -2 da
(14)
1- 2a
2 log
a - 2a
2(log
Since 0 < a <
dH(s) always greater than or equal to zero. In other words, H()) increases with 3 da
greater than or equal to zero when 0 S a S 1. and less than zero when 1 < a S That being said, when a less than 4. (s) increases with a; nonetheless, when a greater than IG(s) decreases with a, although H keeps increasing in this case.
However, dfG(a)
To give specific counterexample, let 0₁ = 0.25 and d2 = 0.3 and denote these nodes as 81 and 82 respectively. Thus, the soft labels of s1 and $2 are [0.5, 0.25, 0.25) and [0.4, 0.3, 0.3], and we have ((s)) = 1.5, (322) se 1.571, [G(s = and (G())) ze 0.971. Evidently, H (s1) < (s2) and IG(ss) > IG(s)).
Therefore, the theorem follows.
B NORMALIZED LABEL
For a certain node, if the soft label given by the model is (a), (01,0,,... ac). and the oracle indicates that the node does not belong class I, then the probability that the node belongs to class i * () is given by
.2,...,
a
Σja aj
(15)
In essence, this is conditional probability. Formally, let be the ground truth label of the node, and then our target can be expressed as
P(j i (
(16)
With the definition of conditional probability, the above can be transformed follows
P(j - P(j P(j=i)
P(j i #
(17)
P(j #1)
#1
According to the known condition, P(j - a, and P(j 1)+ aj- Therefore, the theorem follows. The theorem suggests that, when the oracle gives negative answer, the normalized soft label should be set with accordance to the soft label given by the model, rather than the uniform distribution.
13

---

Published as a conference paper at ICLR 2022
Table 4: Overview of the Five Datasets
Dataset
#Nodes
#Features
#Edges
#Classes
#Truin/Val/Test
Task type
Description
Cora
2,708
1,433
5,429
1,208/500/1 ,000
Transductive
citation network
Citeseer
3,327
3,703
4,732
1,827/500/ ,000
Transductive
citation network
Puhmed
19,717
500
44,338
18,217/500/1,
Transductive
citation
oghn-arxiv
169,343
128
1,166,243
40
N0.9441/29,799/488 6,3
Transductive
citation network
Roddit
232,965
602
11,606.919
155.31022..99744.358
Inductive
social network
C INFORMATION GAIN (IG)
For node Us the IG of annotating it is defined as
TG(() (T)))) P(u: (H.
(18)
Starting from the expectation of entropy reduction, we show how it is transformed into IG as follows. Note that if the oracle agrees with the pseudo label, i.e., event t, the hard label will be obtained, thus the entropy dropping to O.
(iH) H(])
- + - + H(0,, v)-)
-
(19)
= (P(utt) + IG(u))
D EXAMPLE OF EXPECTED INFORMATION GAIN
Case I: vr belongs to the oracle annotated class l. The prediction correct this case, and the information changes from the uncertain soft label the onc-hot label. Suppose the model predicted softmax outputs ÿ, is [0.5, 0.3, 0.2). the label changed into [1. 0, 0] and the corresponding information gain is defined as H ((0.5, 0.3, 0.2)) H ([1, 0, 0J), where H.) is the entropy function.
Case e2 doesn't t belong to the oracle annotated class l. this case, the model prediction is incorrect, but the uncertainty of the soft label is also decreased because we have already known that the true label may belong to the remaining classes except for the class I. Similar to case 1, suppose the predicted label ÿ, is [0.5, 0.3, 0.2), the soft label is changed into [0. 0.6, 0.4] and the corresponding information gain defined as H [ 0.3, 0.2]) H[[0, 0.4.).
E TIME COMPLEXITY ANALYSIS
Given a K K-layer GNN, the propagation matrix (N X N, with M nonzero values) and label matrix (N x should be multiplicated K times in IGP. Therefore, in the stage of node selection (line 3-5 in Algorithm 1), selecting the node that maximizes the propagation of information gain F(V; U (x}) from unlabeled nodes requires O(K Mc), where K is the number of layers of GNNs, M is the number of edges and e is the number of classes. All in all, the cost of selecting batch of b nodes is O(K Me). Suppose we filter out all but n nodes with a degree larger than threshold and get the corresponding propagation matrix (n x N, with m nonzero values), we can reduce the overall time complexity to ObkKmc).
EXPERIMENTAL DETAILS
F.1 DATASET DESCRIPTION
Cora, Citeseer, and Pubmed are three popular citation network data-sets, and we follow the public training/yaliiatiionnest split in GCN Kipf Welling (2017b). In these three networks, papers from
14

---

Published as a conference paper at ICLR 2022
Sum of information entropy
8600
8400
8000
Other methods
IGP
Size labeling budget
Figure 6: the change of information entropy for the whole dataset when labeling hudget grows.
different topics are considered as nodes, and the edges are citations among the papers. The node attributes are binary word vectors, and class labels are the topics papers belong
Reddit is a social network dataset derived from the community structure of numerous Reddit posts. It is well-known inductive training dataset, and the training/validaationness split in experiment is the same as that GraphSAGE Hamilton et al. (2017). The public version provided by GraphSAINT Zeng al. (2000) is used in our paper.
ogbn-arxiv is a directed graph, representing the citation network among all Computer Science (CS) arXiv papers indexed by MAG. The training/validatioonness split in our experiment is the same the public version. The public version provided by OGB is used in our paper.
For more specifications about the five aforementioned datasets, see Table
F.2 IMPLEMENTATION DETAILS
For GPA Hu et al. 2020), to achieve the highest accuracy, directly use the pre-trained model by its authors on Github. Specifically, for Cora, we choose the model pre-trained on PubMed and Citeseer; for PubMed, we choose the model pre-trained on Cora and Citeseer; for Citeseer and Reddit, choose the model pre-trained on Cora and PubMed; for ogbn-arxiv, we choose the model pre-trained on PubMed and Reddit. Other tyyer--paramene are all identical the open-source code.
For AGE Cai et al. (2017) and ANRMAB Gao et al. (2018). to procure well-trained models and guarantee that their model--ased selection criteria work well, GCN trained for 200 epochs in each node selection iteration. AGE is implemented with its open- version and ANRMAB in accordance with its original paper.
For ALG[Zhang et al. (2021a) and GRAIN Zhang et al. (2021c), we follow the public code released by the original paper.
For the hyperparameter a, we set it as 1 in Citeseer, PubMed and ogbn-arxin arxiv, and as 2 for Cora and Reddit. Besides, the degree for dismissing uninfluential nodes IGP 8 for Cora, Citeseer, PubMed, and 15 for Reddit and ogbn-arxiv.
We carry out all the experiments on an Ubuntu 16.04 system with Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz, 4 NVIDIA GeForce GTX 1080 Ti GPUs and 256 GB DRAM. All the experiments are implemented in Python 3.6 with Pytorch Paszke al. 2019) on CUDA 10.1.
G INTERPRETABILITY ANALYSIS
We test the change of information entropy for Citeseer dataset when the labeling budget grows from 2c 20c the number of classes) and report the result in Figure Compare other methods that bring fixed information entropy decrease, IGP has much less information entropy and the gap becomes larger when the labeling budget grow, which explains the better performance of our method.
15

---

Published as a conference paper at ICLR 2022
Table 5: Performance along with running time on the Reddit dataset.
Method
ANRMAB
GPA
AGR
SEAL
ALG
IGP
GRAIN
Relative Ranning Time
340,00
331
8.25
4,00
1.63
1.38
1.25
1,00
Test (1
91,5020
91 8(20.2)
91.61 91.6(20.3)
92 (20.3)
92,4(20.3)
93.4(:0.2)
91.7(20.3)
92.5(=0.1)
Table 6: The test accuracy (%) on different hyperparameters the PubMed dataset
parameters
0=00
n==0.5
a=1
SGC
79.6(=0.7)
82.8(=0.6)
83.2(=0.6)
82.9(=0.5)
APPNP
80.4(.0.6)
83.4(-04)
83.7(-0.5)
83.6(10.5)
GCN
80.7(-04)
83.5(-0.5)
83.6(=0.5)
83.4(+0.6)
MVGRL
80.5(=0.6)
83.2(=0.5)
83.9(=0.4) 83.5(=0.4)
H EFFICIENCY ANALYSIS
To test the efficiency of IGP, also compare its rumning time per AL iteration with other baselines in a batch of node selection in the Reddit dataset. Besides, to measure the influence of the extra computational cost in maximizing the propagation of information gain in the local neighborhood, remove the propagation part in IGP and name this baseline IG.
We set the training time of GRAIN the baseline, the relative training time and the test accuracy of each method are provided in Table As shown in Table our method IGP can get comparable efficiency GRAIN while achieving the accuracy improvement of 0.9%. Besides, removing the propagation part in IGP will make the AI. process a little faster, but also leads to large performance degradation of 1.7% compared with IGP.
I EXPLORATION OF HYPERPARAMETERS
Our proposed IGP has only one hyperparameter a, which controls the importance of the weak label. To investigate its impact on IGP, we set different values and then report the corresponding test accuracy with different base GNN models on different datasets. The experimental results in Table show that removing the weak label will lead to large performance degradation in different models, which verifies the effectiveness of our proposed weak label. Besides, our method IGP is robust the choice of a since its performance is stable on different models when we increase from 0.5 to 2.
J INFLUENCE OF THE NUMBER OF CLASSES
To clarify the influence of the number of classes, we examine the model accuracies a function of the number of classes on the ogbn-arxiv dataset. Specifically, we gradually increase the number of classes and the corresponding number of nodes of the ogbn-arxiv dataset, and report the mean test accuracy of 10 runs with and without the soft-label. As shown in the newly added Figure ((a) although more classes increase the complexity of classification problem (thus a decreasing model accuracy), we see that the performance gain of adding soft labels decreases slightly as the number of classes increases.
The reason is that although the soft-max is taken over the remaining classes, the distribution of the output of soft-max (i.e.. soft label) is expected to be highly skewed, which can help to alleviate the effect of increased class number the quality of the soft label. To demonstrate this, add new Figure 7(b) showing the percentage of the node whose top-K accuracy is larger than 80%. As the percentages of top K class increases (i.e., K/total class number), more than 90% nodes only need the predicted top 20% classes to guarantee the top-K accuracy larger than 80%, which means few classes predominate the softmax distribution.
16

---

Published as a conference paper at ICLR 2022
With Set-old
Inobibiity of TTTT Cleeos
75
Walhon Sod-iabel
0.3
Tot eostnoy
74
12
0.4
-0
Number
Porcentage
(a) The influence of soft label.
(b) The analysis of class distribution.
Figure 7: (Left) The test accuracy of the different number of classes with and without the soft label. (Right) The relationship of probability and percentage of top-K K class in all the classes
Table 7: The test accuracy (%) with different filtering degrees on the Reddit dataset.
Filtering Degree
5
10
15
Test Accuracy (%) 93.6(+0.3) 93.5(=0.33
93.4(#0.22
93.4(=0.2)
K ANALYSIS OF SAMPLE COMPLEXITY
With non-perfect oracle, our method could reduce sample complexity compared with other AL strategies because we improve the utilization of queries and samples. Traditional AL algorithms have to discard the data samples of queries that have not obtained hard labels from non con-perfect Oracle. By contrast, could still leverage these data samples in soft-label manner, thus reducing the error quickly than other AI. algorithms.
Although some AL algorithms enjoy theoretical guarantees the traditional linear machine learning models (e.g., linear regression), analyzing the sample complexity of AL for deep learning is quite difficult due to the non-linear nature of neural networks. Most sample complexity is analyzed under the passive learning for neural networks in the literature. In addition to the non-linear nature of neural networks, the graph neural networks (GNNs) are even more complicated graph data is no longer independent and identically distributed (iid), making the theoretical analysis of sample complexity extremely difficult for GNN-based AL.
L ANALYSIS OF THE FILTERING DEGREE
To clarify how much accuracy would drop when we filter the small-degree nodes, we increase the filtering degree from 0 to 15 and then report the corresponding mean test accuracy of 10 runs with GCN in T Note that the threshold we used in the previous experiments 15 in Reddit.
As shown in Table 7 the test accuracy only drops slightly by 0.2% when we increase the threshold from to 15, meaning that our efficiency optimization will not introduce a large negative influence on the prediction ability of the GCN model. Compared with the uninfluential nodes with small node degrees, labeled nodes will larger degrees will propagate their label information to more adjacent nodes and thus make larger entropy reduction for the whole dataset. As result, nodes with larger degrees have a larger probability of being selected in IGP even if the efficiency optimization is not introduced (i.e., setting the filtering degree 0).
17


Reviews:
[{"review_id": "k5t0L4BzlzX", "reviewer": "Reviewer_tKPB", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n1.\tThe paper provides a relative new framework for GNNs where the information gain propagation is maximized. \n2.\tThe setting of relaxed queries seems to be facilitative in this case.\n3.\tResults show some advantage over other methods\nWeak points:\n1.\tMotivation: except for the motivation for the relaxed queries, I do not see much motivation and discussion in the paper, especially a discussion around the state of the art in this area and how it related to the proposed method. Based on section 4.4 is the only advantage of IGP over others is the use of relaxed queries? What about the query criteria itself? What are its advantages relative to prior works.\nThere are many other mssign motivation throught the paper for example after the IG definition why is this a good a good tool to use?\nWhy relaxed queries are important, where in real life could this make a difference?\n2.\tPaper organization: is section 2.3 meant to be related work? How is it related to section 4.4 on prior work?\n3.\tTechnical errors:\na.\tequation (8) isn’t that supposed to be v_i – on the last component?\nb.\tEquation (4) the indicator is on I – an index of a node equal l – a class? That is incorrect use of the two different symbols in the indicator function\nc.\tWith respect to what is the entropy in eq (7) computed? What are the probabilities?\n4.\tTheoretical foundations: there is no sample complexity analysis or any optimality analysis for the given criterion. The only theorem provided is a rather trivial one showing that entropy doesn’t coincide with IG selection criterion.\n5.\tClarity:\na.\tUnclear sentences like: “Since the influence magnitude is diverse to the influenced nodes…” what does it mean?\n6.\tExperimental validation: I am left unimpressed by the rate of improvement shown by the proposed algorithm. Moreover, the analysis lacks error bars and standard deviation for the 10 executions.\n", "summary_of_the_paper": "The paper proposes an active learning method for GNNs that is based on an information gain maximization where ethe information gain is obtained by querying a data point and looking at the influence of the queried node on the neighborhood relative to their previous information.  They also claim the setting of relaxing the oracle answer to be a binary confirmation of the most probable label. Experiments are presented where some advantage is shown for the method.", "summary_of_the_review": "Strong points:\n1.\tThe paper provides a relative new framework for GNNs where the information gain propagation is maximized. \n2.\tThe setting of relaxed queries seems to be facilitative in this case.\n3.\tResults show some advantage over other methods\nWeak points:\n1.\tMotivation: except for the motivation for the relaxed queries, I do not see much motivation and discussion in the paper, especially a discussion around the state of the art in this area and how it related to the proposed method. Based on section 4.4 is the only advantage of IGP over others is the use of relaxed queries? What about the query criteria itself? What are its advantages relative to prior works.\nThere is lacking motivation throughoutt the paper for example after the IG definition why is this a good a good tool to use?\nWhy relaxed queries are important, where in real life could this make a difference?\n2.\tPaper organization: is section 2.3 meant to be related work? How is it related to section 4.4 on prior work?\n3.\tTechnical errors:\na.\tequation (8) isn’t that supposed to be v_i – on the last component?\nb.\tEquation (4) the indicator is on I – an index of a node equal l – a class? That is incorrect use of the two different symbols in the indicator function\nc.\tWith respect to what is the entropy in eq (7) computed? What are the probabilities?\n4.\tTheoretical foundations: there is no sample complexity analysis or any optimality analysis for the given criterion. The only theorem provided is a rather trivial one showing that entropy doesn’t coincide with IG selection criterion.\n5.\tClarity:\na.\tUnclear sentences like: “Since the influence magnitude is diverse to the influenced nodes…” what does it mean?\n6.\tExperimental validation: I am left unimpressed by the rate of improvement shown by the proposed algorithm. Moreover, the analysis lacks error bars and standard deviation for the 10 executions.\n7.\tThere is not discussion of parameter tuning nor running time of the proposed method.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9pCUE2sm8cA", "reviewer": "Reviewer_owkR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The relaxed query setting is well motivated for AL and it seems to be applicable in real-life scenarios.\n2. The proposed AL criterion takes both information gain and influence magnitude into consideration, which can explicitly maximise the propagation of information gain. \n3. The source code of the paper is released to ensure the reproductivity of results.\n4. Overall, this paper is well-written, though there are some typos in equations and text.\n \nWeakness:\n1. No complexity analysis on the AL query criterion of IGP. As IGP needs to maximise the propagation of information gain in local neighbourhood, it is expected to incur extra computational overhead. \n2. Missing discussion and comparison with recently published GNN-based AL methods, e.g.,\nLi et al. SEAL: Semi-supervised adversarial active learning on attributed graphs, IEEE TNNLS, 32 (7), 3136-3147, 2021. \n\n3. The discussions on related work are respectively given in Section 2.3 and Section 4.4. Would it be better to combine the two sections?\n4. Some symbols used in Eq.(8) are incorrect. e.g., would it be v_i - in the last term? \n", "summary_of_the_paper": "This paper proposes a new GNN-based active learning (AL) method for graph data, under a relaxed query setting where the oracle can only judge the correctness of the predicted labels. A new AL query criterion is proposed to select the nodes that can maximise the information gain propagation (IGP) in local neighbourhood. \n", "summary_of_the_review": "This paper considers a new AL setting with relaxed queries. Under this setting, a new AL query criterion is proposed to incorporate soft labels and information gain propagation. The setting and idea of this paper are interesting, but there are some concerns, e.g,, the lack of computational analysis of the AL query criterion and comparison to some state-of-the-art GNN-based AL methods. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "4OeE9hu-oG", "reviewer": "Reviewer_QqqC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1.  The strengths:\n1.1. present using the relaxied queries to replace commonly-used exact labeling strategy for AL, i.e., only judging the correctness of the predicted labels (a binary question) rather than identifying the exact class (a multi-class question), doing so is relatively easier and to be my best knowledge, it seems hardly to be done before.\n1.2. provide a new criteria for active learner with the help of such relaxed queries and soft labels via maximizing defined the IGP. \n1.3. obtain significant performance boost comparing with SOTAs.\nOne the whole, the proposed method can have more flexibility, e.g., being applicable to a large variety of GNN variants.\n2. The  weaknesses:\n2.1 Class-imbalance problem;\n2.2. Due to GNN characteristics, IGP inherits possible oversmoothness problem.\nIn addition, please concern possible relation with \"Two-dimensional active learning for image classification\" availavle at internet.", "summary_of_the_paper": "The submissiom presents a GNN-based AL method using soft-label technique with 2 innovations different from existing works\n1. using relaxed queries and 2. building a new criteria of maximizing IGP for active learner with relaxed queries and soft labels. 3.outperforming SOTAs in performance.", "summary_of_the_review": "In this submission, in my opinion, the authors consider using relaxied queries to replace exact labeling for active learner and define a new criterion with IGP  for learning. Using the relaxied queries indeed provides the oracle a relatively easier labeling andthus more reliable. While Theorem 3.1 gives some insight. The authors provide their codes for REPRODUCIBILITY and the experiments are also relatively sufficiently conducted and compared, the results are convincing! ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4-CGJsubvc9", "reviewer": "Reviewer_5Qmn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality & Quality: The paper is well written and puts itself nicely in context of previous work. The overall presentation of the paper is good except a couple typos. The proposed approach is a novel adaptation of AL to graphs (to the best of my knowledge).\n\n\n\n1). The idea of soft-labeling is intriguing! Though, the example that the paper provides in Section 1 regarding arXiv subject categories is misleading. The paper argues that a node may belong to more than one categories, e.g., mathematical finance and computational finance and that is hard for a human labeler to classify. However, it is unclear how the proposed approach solves that problem since the approach still relies on a model to make the label prediction, e.g., mathematical finance in the case above and then the human accepts it. So, we still have the same problem that the example was provided to get rid of. This is so because the example of arXiv classification is more of a multi-label classification problem and hence not a good example to motivate this paper in my opinion. \n\n\n\n2). It will be interesting to see the model accuracies as a function of the number of classes. If the humans doesn't agree with the model, the label is discarded and a soft-max is taken over the remaining classes. So it will be interesting to see how this weak labeling by the remaining classes performs when the number of classes is large and hence the prediction problem is hard. \n\n\n\nSignificance: The paper addresses an important problem of active learning on graphs using soft-labels.", "summary_of_the_paper": "The paper proposes a new method active learning (AL) on graphs. Unlike other AL approaches, the proposed approach provides soft labels via *relaxed queries* to the *domain experts*. \n\n\n\nMain Contributions: \n\n1). The paper proposes a new innovative approach for graph active learning with soft labels. The key idea is to ask a human regarding whether the model prediction is correct or not (a binary classification task) as opposed to asking them the correct \"hard label\" of the node. The incorrect model predictions are also not \"thrown away\" and used as indirect supervision by performing a soft-max over the remaining classes. This leads to a new criteria for active learning, called \"maximizing information gain propagation\" as opposed to maximizing entropy as done by standard AL.\n\n\n2). Results are shown on a variety of real-world datasets which show the superior performance of the proposed method in achieving higher test accuracy with a certain labeling budget.", "summary_of_the_review": "The paper provides an intriguing idea of soft-labeling to improve active learning (AL) on graphs. It seems more efficient than the conventional AL approaches on graphs and is more cost efficient. The results are mostly strong, except it is unclear what is the impact of the number of classes on the output performance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new approach to graph-based active learning, using the query whether the predictions made by the current model are correct or not.
Although the theoretical underpinnings of the proposed approach are a bit weak, the problem formulation that is newly proposed in this paper makes sense from a practical point of view, and the paper makes a simple and interesting proposal that would be worth sharing with the community.
Decision: Accept (Poster)