Year: 2021

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.

heading: 1 INTRODUCTION
text: 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., 2020; Wang et al., 2019; Li et al., 2019; Do et al., 2019). Despite their effectiveness and popularity, GNNs typically require a large amount of labeled data to achieve satisfactory performance. However, obtaining these labels is a time-consuming, laborious, and costly process. Therefore, how to do this economically and efficiently has attracted great attention both in academia and industry. One of the most popular strategies to tackle this challenge is 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 be provided by the oracle. As illustrated in Fig. 1, 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 ogbn-papers100M is 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, a specialist/expert in the subject areas of machine learning is incapable of labeling query instances with subject areas of finance (such as mathematical finance or computational finance), which is out of his domain knowledge.
In this paper, we propose a novel active learning paradigm for GNNs in which only soft labels are required. Two salient features of our paradigm are as follows:
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
0.5 0.3 0.2
Model Prediction
Oracle
Which category does it exactly belong to ?
Does it belong to the first category ?
Query
Oracle
1 0 0
0 0.6 0.4
Yes
No
Ground truth label
Our strategy
Previous strategy
Figure 1: An example of our new node labeling strategy.
[1, 0, 0]
[0.5, 0.3, 0.2]
[0, 0.4, 0.6]
0.5
0.4
0.1
[0.7, 0.16, 0.14]
IGP ( ) = H(0.7, 0.16, 0.14) – H(1/3, 1/3, 1/3)
Figure 2: An example of IGP.
classes. As illustrated in Fig.1, we allow relaxed queries such as “Does the sample belong to this class?” (e.g., the first class in Fig. 1), since this query is specific to the domain of experts, hence more ready to be answered. As far as we are concerned, no previous AL methods can deal with such 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 a single node. In this paper, we propose a 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) can 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 of a neighborhood region beyond a 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 a new AL 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 a large margin in five open graph datasets.

heading: 2 PRELIMINARY

heading: 2.1 PROBLEM FORMULATION
text: Let G = (V ,E) with |V| = N nodes and |E| = M edges be the graph, and c is the number of classes. X = {x1,x2...,xN} is the node feature matrix, the one-hot vector yi ∈ Rc and and xi ∈ Rd are the ground-truth label and node feature for node vi ∈ V , respectively. We consider a general AL setting in this work. Suppose the full node set V is partitioned into training set Vtrain, validation set Vval, and test set Vtest, and Vtrain can further be partitioned into the labeled set Vl and unlabeled set Vu, respectively. Given the labeling size B, the loss function `, the goal of graph-based AL is to select a subset Vl ⊂ Vtrain to label, so that the model f trained with the supervision of Vl can get the lowest loss on Vtest:
arg min Vl:|Vl|=B Evi∈Vtest [` (yi, ŷi)] , (1)
where ŷi is the softmax outputs of node vi given by the model f .
Different from the previous setting, B is the labeling cost (i.e., money) rather than the size in our new scenario. As the experts are hard to annotate the node out of their domain, we assume the conventional query cost c− 1 times as much as our relaxed query for each selected node. Correspondingly, the objective in our new scenario is
argmin Vl:M(Vl)=B Evi∈Vtest [` (yi, ŷi)] , (2)
where M(Vl) is the labeling cost for annotating Vl, and we focus on f being GNNs due to their state-of-the-art performance in many semi-supervised node classification tasks.

heading: 2.2 GRAPH NEURAL NETWORKS
text: Unlike the images, text or tabular data, where training data are independently and identically distributed, samples are connected by edges in the graph, and each node in a GNN can aggregate the node embedding or feature from its neighbors to enhance their embedding along edges. Let f ( A,X(k);W(k) ) be any GNN, where A is an adjacency matrix, X(k) is the feature matrix of k-th
layer, and W(k) 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(k+1) = f ( A,X(k),W(k) ) = δ ( D̃−1ÃX(k)W(k) ) , (3)
where X (and X(0)) is the original node feature, X(k) and X(k+1) are the embeddings of layer k and k+1 respectively. Besides, D̃ is the diagonal node degree matrix for normalization and Ã = A+ IN is the adjacent matrix with self connection, where IN is the identity matrix. Compared with the DNN layer which formulated as X(k+1) = δ ( X(k)W(k) ) , the feature matrix X(k) will be firstly
enhanced with the feature propagation operation D̃−1ÃX(k), and then boosts the semi-supervised node classification performance by getting more nodes involved in the model training.

heading: 2.3 ACTIVE LEARNING
text: Common AL. AL can improve labeling efficiency by selecting the most valuable samples to label. Considering the informativeness, Uncertainty Sampling (Yang et al., 2015; Zhu et al., 2008) selects the nodes which has the most uncertain model prediction. Besides, Query-by-Committee (Burbidge et al., 2007; Melville & Mooney, 2004) trains a committee of models, and selects samples according to the extent to which the models disagree. Furthermore, Density-based (Zhu et al., 2008; Tang et al., 2002) and Clustering-based (Du et al., 2015; Nguyen & Smeulders, 2004) and Diversity-based (Wu et al., 2020; Jiang & Gupta, 2021) methods can effectively select the most representative samples. All the methods above are proposed for binary or 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 et al., 2017) and ANRMAB (Gao et al., 2018) introduce the density of node embedding and PageRank centrality into the node selection criterion. Besides, ALG (Zhang et al., 2021a) proposes to maximize the effectiveness of all influenced nodes of GNNs. Recently, Grain (Zhang et al., 2021b) introduces a 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 a 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., 2021b) 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 assume the oracle knows the information of all categories, thereby being able to correctly annotate all the selected nodes. This is impractical if the oracle encounters some areas that they are not familiar with, especially when the number of categories is large. IGP is the first work to actively labeling graph data under domain-specific experts.

heading: 3 PROPOSED METHOD
text: 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 a single node to the full graph, we firstly
estimate the influence magnitude of graph propagation in Sec. 3.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.

heading: 3.1 INFORMATION GAIN
text: Different from the previous annotation method, which asks the oracle to directly provide annotated class l, the oracle in IGP only needs to judge whether the model prediction ŷ is correct. Rather than discard the incorrect prediction, we propose that both the correct and incorrect predictions will provide the information gain and thus enhance the label supervision.
An oracle is required to answer whether the model prediction is correct, i.e., ŷ belongs to class l. 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 as follows.
Definition 3.1 (Normalized Label). For node vi, the soft label (model predicted softmax output) is denoted as ŷi = [a1, a2, ..., ac]. The pseudo label (denoted as l) is set as the class with the highest value in ŷi. After the oracle judges whether vi belongs to class l, each element a′t in the normalized soft label ŷ′i = [a ′ 1, a ′ 2, ..., a ′ c] is defined as
a′t = { 1(t = l) vi belongs to class l at·1(t=l)∑
j 6=l aj vi does not belong to class l
(4)
After the query, ŷi is updated as the normalized soft label ŷ′i by Eq. 4 (See more details in Appendix B).
The oracle may agree with the pseudo label (denoted as vi+), or disagree (denoted as vi−). 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 vi, the IG of annotating it is defined as
IG(vi) = H(ŷi)− P (vi−)H(ŷ′i, vi−), (5)
where H is the entropy (well-known in the information theory), e.g., H(ŷi) = − ∑k
p=1 ap log ap (log always stands for log2 in this paper). Therefore, H(ŷi) and H(ŷ ′ i) stand for the entropy of vi before and after annotation respectively. Also, H(ŷ′i, vi+) and H(ŷ ′ i, vi−) are the two cases of H(ŷ′i) where vi+ and vi− occurs respectively.
IG is exactly the expectation of entropy reduction, as 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 a good measurement for the probability that the oracle will agree with the pseudo label, namely P (vi+).
Here following theorem shows the difference between IG and entropy.
Theorem 3.1. The node with the highest entropy is not necessarily the node that brings the highest IG.
The proof of this theorem can be found in Appendix A.
More examples about IG in differing cases, that is, the oracle may agree or disagree with the pseudo label, can be found in Appendix D.

heading: 3.2 INFLUENCE MAGNITUDE ESTIMATION
text: Each newly annotated node will propagate its label information to its k-hop neighbors in a k-layer GNN and correspondingly influences the label distribution of these nodes. Since the influence of a node on its different neighbors can be various, we measure it by calculating how much change in the input label of node vi affects the propagated label of node vj after k-steps propagation (Wang & Leskovec, 2020; Xu et al., 2018).
Definition 3.3 (Influence Magnitude). The influence magnitude score of node vi on node vj after k-step propagation is the L1-norm of the expected Jacobian matrix Îf (vj , vi, k) =∥∥∥E[∂X(k)j /∂X(0)i ]∥∥∥
1 . Formally, we normalize the influence magnitude score as:
If (vj , vi, k) = Îf (vj , vi, k)∑
vw∈V Îf (vj , vw, k) . (6)
For a k-layer GNN, the influence magnitude score If (vj , vi, k) captures the sum over probabilities of all possible influential paths with length of k from node vi to vj . Intuitively, node vi will influence vj by a larger extent and thus If (vj , vi, k) is larger if vi is easier to achieve at vj after the random walk. In our AL setting, larger If (vj , vi, k) means the label distribution of node vj will be influenced more by node vi if vi is labeled.

heading: 3.3 INFORMATION GAIN PROPAGATION
text: For a k-layer GNN, the supervision signal of one node can be propagated to 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, we 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 vj from the labeled node vi is defined as follows. Definition 3.4 (information gain propagation). Given the model predicted softmax outputs ŷi of node vi, the influence magnitude If (vj , vi, k) of node vi on vj , the information gain propagation of node vj from labeling node vi is defined as:
IGP (vj , vi, k) = H ( ∑ vm∈Vl If (vj , vm, k)ŷ ′ m ) −H  ∑ vm∈Vl∪{vi} If (vj , vm, k)ŷ ′ m  . (7) Since the new soft label ŷ′i is unavailable for node vi before the annotation, the expected information gain propagation (IGP) is calculated by
IGP (vj , vi, k) = P (vi+)IGP (vj , vi, k, vi+) + P (vi−)IGP (vj , vi, k, vi−), (8) where IGP (vj , vi, k, vi+) is the IGP when the oracle agrees with the pseudo label. In this case, ŷ′i is a one-hot vector according to E.q. 4.

heading: 3.4 MAXIMIZING INFORMATION GAIN PROPAGATION
text: To maximize the uncertainty of all the influenced nodes in the semi-supervised GNN training, we aim to select and annotate a subset Vl from V so that the maximum information gain propagation can be achieved according to Eq. 9. 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 Vl
F (Vl) = ∑
vi∈Vl ∑ vj∈RF (vi) IGP (vj , vi, k), s.t. Vl ⊆ V, |Vl| = B. (9)
where RF (vi) is the receptive field of node vi, i.e., the node itself with its k-hop neighbors in a k-layer GNN. Considering the influence propagation, the proposed objective can be used to find a subset Vl that can maximize the information gain of all influenced nodes as more as possible.

heading: 4 IGP FRAMEWORK

heading: 4.1 FRAMEWORK OVERVIEW
text: 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
Algorithm 1: Working pipeline of IGP Input: Initial labeled set V0, query batch size b. Output: Labeled set Vl
1 Stage 1: Node Selection 2 Vl = V0, Vb = ∅; 3 for t = 1, 2, . . . , b do 4 Select the most valuable node: vi = arg maxv∈Vtrain\Vl F (Vl ∪ {v}); 5 Vl = Vl ∪ {vi}, Vb = Vb ∪ {vi}, Vtrain = Vtrain \ {vi}; 6 Stage 2: Node Labeling 7 for vi ∈ Vb do 8 Judge the correctness of the predicted pseudo label ȳi; 9 if ȳi is correct (agreed by the oracle) then
10 Labeling vi with ŷi ′ according to Eq. 4; 11 else 12 Labeling vi with ŷi
′ according to Eq. 4; 13 Vl = Vl \ {vi}, Vtrain = Vtrain ∪ {vi}; 14 Return Vl
node. Considering both the influence magnitude and information gain, IGP further measures the information gain propagation of each unlabeled node and selects a batch of nodes that can maximize the 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.

heading: 4.2 WORKING PIPELINE
text: Node Selection. Without losing generality, consider a batch setting where b nodes are selected in each iteration. Algorithm 1 provides a sketch of our greedy selection method for GNNs. Given the training set Vtrain, and query batch size b, we first select the node vi, which generates the maximum marginal gain (Line 3). We then update the labeled set Vl, the oracle annotated set Vb, and the training set Vtrain (Line 4). This process is repeated until a batch of b nodes have been selected. Note that the normalized soft label ŷ′i is unavailable before the node labeling process. For better efficiency, we assume ŷ′i is the model predicted soft label ŷi in the node selection process. If ŷi is not confident (i.e.,[0.4,0.3,0.3] for a three-classification problem), it will be of little influence on the label distribution of its neighbors. On the contrary, if ŷi is closer to ŷ′i if it is confident. Consequently, it is reasonable to make such an assumption.
Node Labeling After getting a batch of the selected node-set Vb, we acquire the label from an oracle. As introduced before, different from previous works which require the oracle to annotate the hard label directly, the oracle in our framework only needs to judge the correctness of the pseudo label ȳi (Line 8). If ȳi is correct, we update its soft label ŷi
′ according to Eq. 4 (Line 10). Note that we can still get information gain even if ȳi is incorrect. For any node vi with an incorrect pseudo label, we firstly update its soft label ŷi
′ (Line 10). After that, we remove it from Vl and add it to Vtrain (Line 13). In this way, this node has the chance to 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, a node with smaller entropy contains contributes more to 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
L = − ∑
vi∈Vl,H(vi)=0
ŷ′i log ŷi + α ∑
vi∈Vl,H(vi)6=0
ŷ′ilog ŷ′i ŷi , (10)
where α is a hyper-parameter 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(vi) = 0), which is correctly predicted by the model; 2) soft labels (i.e., H(vi) 6= 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 a special case of KL divergence). Note that KL divergence measures the distance between the ground truth and the current prediction, and it is especially appropriate for methods with a basis of information theory.

heading: 4.3 EFFICIENCY OPTIMIZATION
text: 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 uninfluential nodes to dramatically reduce the amount of computation for evaluating the information gain propagation. For example, we can use the node degree or the distribution of random walkers throughout the nodes (Kim et al., 2017) to filter out a vast number of uninfluential nodes.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETTINGS
text: Datasets. We evaluate IGP in both inductive and transductive settings (Hamilton et al., 2017): three citation networks (i.e., Citeseer, Cora, and PubMed) (Kipf & Welling, 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 et al., 2019) and MVGRL (Hassani & Khasahmadi, 2020).
Baselines. We compare IGP with the following baselines: Random, AGE (Cai et al., 2017), ANRMAB (Gao et al., 2018), ALG (Zhang et al., 2021a), GRAIN (Zhang et al., 2021b)
Settings. For each method, we use the hyper-parameter tuning toolkit (Li et al., 2021a;b) or follow the original papers to find the optimal hyper-parameters. To eliminate randomness, we repeat each method ten times and report the mean performance. Specifically, for each method, we chooses a small set of labeled nodes as an initial pool – two nodes are randomly selected for each class.

heading: 5.2 PERFORMANCE COMPARISON
text: End-to-end Comparison. We choose the labeling budget as 20 labels per class to show the end-toend accuracy. Table 1 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.e., GRAIN, by 1.6-2.2% on the three citation networks, 0.9% on Reddit, and 0.6% on ogbn-arxiv.
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 of oracle labels from 2C to 20C (C is 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 of IGP grows fairly fast, thereby outperforming the baselines with an even greater margin.
Generalization. In 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., 2021) 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 is 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 a conclusion that IGP can generalize to 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, we 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 (IT)”); (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)”);(iv) without the normalized soft label and set the soft label uniformly (called “No Normalized Label (NL)”); Table 3 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 is 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 of 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 on other nodes. 4)If we remove normalized label and set the soft 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 is 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 has 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.

heading: 6 CONCLUSION
text: This paper presents Informatioin Gain Propagation (IGP), the first GNN-based AL method which explicitly considers AL with soft labels. Concretely, we provide a new way for active learners to exhaustively label nodes with a limited budget, using a combination of domain experts and GNN model. IGP allows us to use relaxed queries where domain expert (oracle) only judges the correctness of 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 a large margin, especially when the number of classes is large.

heading: 7 REPRODUCIBILITY
text: The source code of IGP can be found in Anonymous Github (https://anonymous.4open. science/r/IGP). To 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 is presented in Appendix F.2, and please refer to “README.md” in the Github repository for more details.

heading: A PROOFS
text: 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 a three classification problem. Assume there is a node s with soft label [1− 2a, a, a], where 0 ≤ a ≤ 13 so that 1− 2a ≥ a. Therefore, the entropy of s is given by
H(s) = −(1− 2a) log(1− 2a)− a log a− a log a = −(1− 2a) log(1− 2a)− 2a log a (11)
When the oracle gives a 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 s is given by IG(s) = (1− 2a)(H(s)− 0) + 2a(H(s)− 1) = H(s)− 2a (12) Take the derivatives of the above two variables, we have
dH(s)
da = [−(1− 2a) log(1− 2a)− 2a log a]′
= −{[(1− 2a) log(1− 2a)]′ + 2(a log a)′} = − {
[log(1− 2a) + 1 ln 2 ] ∗ (−2) + 2(log a+ 1 ln 2 ) } = 2[log(1− 2a)− log a]
= 2 log 1− 2a a
(13)
dIG(s)
da = d(H(s)− 2a) da
= dH(s)
da − 2
= 2 log 1− 2a a − 2 = 2(log 1− 2a a − 1)
(14)
Since 0 ≤ a ≤ 13 , dH(s) da is always greater than or equal to zero. In other words, H(s) increases with a.
However, dIG(s)da is greater than or equal to zero when 0 ≤ a ≤ 1 4 , and less than zero when 1 4 < a ≤ 1 3 . That being said, when a is less than 14 , IG(s) increases with a; nonetheless, when a is greater than 1 4 , IG(s) decreases with a, although H(s) keeps increasing in this case.
To give a specific counterexample, let a1 = 0.25 and a2 = 0.3 and denote these nodes as s1 and s2 respectively. Thus, the soft labels of s1 and s2 are [0.5, 0.25, 0.25] and [0.4, 0.3, 0.3], and we have H(s1) = 1.5, H(s2) ≈ 1.571, IG(s1) = 1 and IG(s2) ≈ 0.971. Evidently, H(s1) < H(s2) and IG(s1) > IG(s2).
Therefore, the theorem follows.

heading: B NORMALIZED LABEL
text: For a certain node, if the soft label given by the model is [a1, a2, ..., ac], and the oracle indicates that the node does not belong to class l, then the probability that the node belongs to class i (i 6= l) is given by
ai∑ j 6=l aj
(15)
In essence, this is a conditional probability. Formally, let j be the ground truth label of the node, and then our target can be expressed as P (j = i|j 6= l) (16) With the definition of conditional probability, the above can be transformed as follows
P (j = i|j 6= l) = P (j = i, j 6= l) P (j 6= l) = P (j = i) P (j 6= l) (17)
According to the known condition, P (j = i) = ai and P (j 6= l) = ∑
j 6=l aj . Therefore, the theorem follows. The theorem suggests that, when the oracle gives a negative answer, the normalized soft label should be set with accordance to the soft label given by the model, rather than the uniform distribution.
C INFORMATION GAIN (IG)
For node vi, the IG of annotating it is defined as IG(vi) = H(ŷi)− P (vi−)H(ŷ′i, vi−), (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 vi+, the hard label will be obtained, thus the entropy dropping to 0.
E[H(ŷi)−H(ŷ′i)] = P (vi+)(H(ŷi)−H(ŷ′i, vi+)) + P (vi−)(H(ŷi)−H(ŷ′i, vi−)) = P (vi+)(H(ŷi)− 0) + P (vi−)(H(ŷi)−H(ŷ′i, vi−)) = (P (vi+) + P (vi−))H(ŷi)− P (vi−)H(ŷ′i, vi−) = IG(vi) (19)

heading: D EXAMPLE OF EXPECTED INFORMATION GAIN
text: • Case 1: vi belongs to the oracle annotated class l. The prediction is correct in this case, and the information changes from the uncertain soft label to the one-hot label. Suppose the model predicted softmax outputs ŷi is [0.5, 0.3, 0.2], the label is changed into [1, 0, 0] and the corresponding information gain is defined as H([0.5, 0.3, 0.2]) − H([1, 0, 0]), where H(·) is the entropy function.
• Case 2: vi doesn’t belong to the oracle annotated class l. In 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 l. Similar to case 1, suppose the predicted label ŷi is [0.5, 0.3, 0.2], the soft label is changed into [0, 0.6, 0.4] and the corresponding information gain is defined as H([0.5, 0.3, 0.2]) − H([0, 0.6, 0.4]).

heading: E TIME COMPLEXITY ANALYSIS
text: Given a K-layer GNN, the propagation matrix (N ×N , with M nonzero values) and label matrix (N × c) 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 (Vl ∪ {v}) from unlabeled nodes requires O(KMc), where K is the number of layers of GNNs, M is the number of edges and c is the number of classes. All in all, the cost of selecting a batch of b nodes is O(bKMc). Suppose we filter out all but n nodes with a degree larger than a threshold and get the corresponding propagation matrix (n×N , with m nonzero values), we can reduce the overall time complexity to O(bKmc).

heading: F EXPERIMENTAL DETAILS
text: F.1 DATASET DESCRIPTION
Cora, Citeseer, and Pubmed1 are three popular citation network data-sets, and we follow the public training/validation/test split in GCN Kipf & Welling (2017b). In these three networks, papers from 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 to.
Reddit is a social network dataset derived from the community structure of numerous Reddit posts. It is a well-known inductive training dataset, and the training/validation/test split in our experiment is the same as that in GraphSAGE Hamilton et al. (2017). The public version provided by GraphSAINT2 Zeng et al. (2020) 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/validation/test split in our experiment is the same as the public version. The public version provided by OGB3is used in our paper.
For more specifications about the five aforementioned datasets, see Table 4.
1https://github.com/tkipf/gcn/tree/master/gcn/data 2https://github.com/GraphSAINT/GraphSAINT 3https://ogb.stanford.edu/docs/nodeprop/#ogbn-arxiv
F.2 IMPLEMENTATION DETAILS
For GPA Hu et al. (2020), to achieve the highest accuracy, we 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, we choose the model pre-trained on Cora and PubMed; for ogbn-arxiv, we choose the model pre-trained on PubMed and Reddit. Other hyper-parameters are all identical to 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-based selection criteria work well, GCN is trained for 200 epochs in each node selection iteration. AGE is implemented with its open-source version and ANRMAB in accordance with its original paper.
For ALG Zhang et al. (2021a) and GRAIN Zhang et al. (2021b), we follow the public code released by the original paper.
For the hyperparameter α, we set it as 1 in Citeseer, PubMed and ogbn-arxiv, and as 2 for Cora and Reddit. Besides, the degree for dismissing uninfluential nodes in IGP is 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 1.7.1 Paszke et 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 to 20c (c is the number of classes) and report the result in Figure 6. Compare to 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.

heading: H EFFICIENCY ANALYSIS
text: To test the efficiency of IGP, we also compare its running 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, we remove the propagation part in IGP and name this baseline IG.
We set the training time of GRAIN as the baseline, the relative training time and the test accuracy of each method are provided in Table 5. As shown in Table 5, our method IGP can get comparable efficiency as GRAIN while achieving the accuracy improvement of 0.9%. Besides, removing the propagation part in IGP will make the AL process a little faster, but it also leads to large performance degradation of 1.7% compared with IGP.

heading: I EXPLORATION OF HYPERPARAMETERS
text: Our proposed IGP has only one hyperparameter α, which controls the importance of the weak label. To investigate its impact on IGP, we set α to different values and then report the corresponding test accuracy with different base GNN models on different datasets. The experimental results in Table 6 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 to the choice of α 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 as 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 7(a), although more classes increase the complexity of a 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 on the quality of the soft label. To demonstrate this, we add a 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.

heading: K ANALYSIS OF SAMPLE COMPLEXITY
text: With a 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-perfect Oracle. By contrast, we could still leverage these data samples in a soft-label manner, thus reducing the error quickly than other AL algorithms.
Although some AL algorithms enjoy theoretical guarantees on 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 as graph data is no longer independent and identically distributed (iid), making the theoretical analysis of sample complexity extremely difficult for GNN-based AL.

heading: L ANALYSIS OF FILTERING DEGREE
text: 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 Table 7. Note that the threshold we used in the previous experiments is 15 in Reddit.
As shown in Table 7, the test accuracy only drops slightly by 0.2% when we increase the threshold from 0 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 a 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 to 0).

Review summaries:
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.

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*.     Main Contributions:   1). 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.   2). 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.