Transfer Active Learning For Graph Neural Networks
Authors: Shengding Hu
Meng Qu
Zhiyuan Liu
Jian Tang
Venue:  (2020)
Keywords: Active Learning
Graph Neural Networks
Transfer Learning
Reinforcement Learning

Abstract: Graph neural networks have been proved very effective for a variety of prediction tasks on graphs such as node classification. Generally, a large number of labeled data are required to train these networks. However, in reality it could be very expensive to obtain a large number of labeled data on large-scale graphs. In this paper, we studied active learning for graph neural networks, i.e., how to effectively label the nodes on a graph for training graph neural networks. We formulated the problem as a sequential decision process, which sequentially label informative nodes, and trained a policy network to maximize the performance of graph neural networks for a specific task. Moreover, we also studied how to learn a universal policy for labeling nodes on graphs with multiple training graphs and then transfer the learned policy to unseen graphs. Experimental results on both settings of a single graph and multiple training graphs (transfer learning setting) prove the effectiveness of our proposed approaches over many competitive baselines. 

Under review as a conference paper at ICLR 2020
TRANSFER ACTIVE LEARNING FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have been proved very effective for variety of prediction tasks on graphs such as node classification. Generally, a large number of labeled data required to train these networks. However, in reality it could be very expensive to obtain a large number of labeled data on large-scale graphs. In this paper, studied active learning for graph neural networks, i.e., how effectively label the nodes on a graph for training graph neural networks. We formulated the problem as a sequential decision process, which sequentially label informative nodes, and trained a policy network to maximize the performance of graph neural networks for a specific task. Moreover, we also studied how to learn universal policy for labeling nodes on graphs with multiple training graphs and then transfer the learned policy unseen graphs. Experimental results on both settings of a single graph and multiple training graphs (transfer learning setting) prove the effectiveness of our proposed approaches over many competitive baselines.
INTRODUCTION
Graphs encode the relations between different objects and are ubiquitous real-world. Learning effective representations of graphs is critical to a variety of applications. Recently, graph neural net- works (Kipf & Welling/ 2016 Veličković et al. (017)) have been attracting growing attention, which iteratively update node representations by combining information of the nodes and their neighbors. They have been proved effective many applications such as node classification (Kipf & Welling 2016 Veličković et al. 2017) and link prediction (Zhang & Chen 2018 Cao al. 2018)).
Despite the appealing performance, the training of graph neural networks typically requires massive labeled data (Yang et al. 2016). However, in many domains such as healthcare, a large number of labeled data may not be available, and could be very expensive to obtain labeled data. Therefore, in this paper we focus on how to minimize human efforts in obtaining labeled data. Specifically, study active learning for graph neural networks. In other words, our goal is to select informative nodes on graphs and query for their labels train graph neural networks.
There are already some existing work that studied active learning for graphs (Gadde et al. 2014 Ji Han| (2012 Cai et al.) 2017). which generally used some optimization theory or proposed different kinds of heuristics (c.g., using the degree of nodes or the entropy of predicted label distributions) to select informative nodes for labeling. However, the nodes selected by these heuristics may not be optimal for specific task. Moreover, these rules are usually domain specific, which are difficult to generalize to new graphs.
In this paper, we formulate active learning on graphs as sequential decision process and aim to learn a policy network to sequentially pick the informative nodes for optimizing specific task. Taking the node classification as an example, we define the state as the graph with the node information as whether the nodes are selected or not and their label distributions predicted by current graph neural networks. The action is picking the next node for labeling, After node is picked, we retrain the graph neural network by adding the new picked node into the training set. The performance gain the validation data set is defined as the reward. A policy network, which encodes the state with another graph neural network and predicts the next node to label, is trained to optimize the performance of graph neural network for the specific task.

---

Under review as a conference paper at ICLR 2020
The above approach allows to learn a policy to select informative labeled nodes for training graph neural networks on a single graph. However, a more important question is whether the learned pol- icy can be transferred to new unseen graphs. Therefore, we further study transfer active learning for graph neural network, which aims to learn a universal policy with multiple training graphs to generalize to new graphs. Given multiple training graphs, straightforward solution is to learn single policy across multiple training graphs. Such an approach works reasonable well in practice. However, in some cases, the optimal policy on different graphs may be different from each other. Therefore, we allow each graph to have a graph-specife policy, which is an instantiation of the uni- versal policy on a different graph. During training. each graph-specific policy is trained to maximize the performance of its own task and meanwhile regularized by the universal policy, and the knowl- edge learned by different graph-specific policies is dynamically distilled into the universal policy by minimizing the KI. divergence between the action distributions. With such a strategy, the universal policy can acquire knowledge from multiple graphs, and is therefore capable of transferring to new graphs.
We evaluate our proposed methods on the standard semi-supervised node classification task, in which the policy is trained and evaluated on single graph, and the transfer active learning set- ting, in which the universal policy is trained with multiple graphs and evaluated on new graphs. Experimental results on both settings prove the effectiveness of our proposed approaches over many competitive baselines.
RELATED WORK
There are some existing work on active learning for graphs. Early studies Guillory & Bilmes,
2009 Ji & Ham, 2012] Gadde et al. 2014) typically formalized the task as an optimization problem.
There are also works on semi-superrised classification on graphs with very few labeled data, such as Gallagher et al. 2008); Lin & Cohen (2010). Nevertheless, these methods are very computa- tional expensive and cannot scale up to wallworldd graphs. Some recent studies (Cai et al., 2017) approached active learning by linearly combining several hand-crafted features including the uncer- tainty of the predictions, structure features such as centrality, and semantic features. More recently, Abel & Louzoun (2019) proposed to take the diversity of node's neighbors in terms of label into consideration and choose the node to be labeled in more regional perspective. However, the la- beled nodes selected by these heuristics may not be optimal for the specific task while our policy network is trained optimize the performance of the specific task. Moreover, these heuristics could be difficult to generalize to new unseen graphs.
Our work is also related learning to learn strategies for active learning. |Fan et al. (017)) studied using reinforcement learning for active learning on the task of Named Entity Recognition (NER), where they need decide which sentence should be queried to label the Named Entity inside it. They formalized the sentence selection as a sequential decision process to sequentially select the sentences to be labeled. Similarly, Liu al. (2018a) used imitation learning to train an active learning policy for NER tasks. Liu et al. (2018b) applied reinforcement learning algorithm to learn the policy for active learning on Neural Machine Translation tasks. |Bachman et al. (017)) proposed to learn the policy network for active learning via meta-Learning. Different from these works, in this paper we focus on active learning for graphs, in which the data (the nodes) to be labeled are highly correlated, and hence the problem is more challenging. Moreover, our goal is learn a unified policy for active learning to transfer across different domains or graphs.
METHODOLOGY
3.1 PROBLEM DEFINITION
Graph neural networks have been proved effective in a variety of predictive tasks on graphs but require many labeled data for training. In this paper, we focus on how to minimize humans' efforts in obtaining labeled data on graphs (i.e. active learning) for training graph neural networks. Take the node classification and aim to learn a policy to select the most informative nodes and further query for their labels for training graph neural networks. Formally, for a graph G (Va, FG, FG, Lo), where VG. FG. Fe
example. We formulate the problem as sequential decision process
2

---

Under review as a conference paper at ICLR 2020
training graph
test
gresh
BG
Test
Tu
training graph g
unlabeled
State
labeleclnodes
GG
GCN
selected nodes
concalenatee
Figure I: Overview of our model. The green box represents the components that forming the state. After that state is passed in to GCN to obtain probability distribution TG- Universal policy is distilled from To and applied to test graphs.
and LG stand for nodes, edges, node features and node labels respectively, we aim at learning
policy TG. which selects sequence of nodes Vi S VG from the training set with the size of Vi controlled by a given budget. We expect that the graph neural network trained with the labels of V has the optimal prediction performance on test sets of G.
Although active learning on single graphs is important, in practice we care more about whether the learned policy can transfer to unseen graphs. Therefore, we further propose to study transfer active learning for graph neural networks, where a universal policy is learned on multiple training graphs and evaluated on unseen test graphs. Formally, given a set of training graphs Svain. we seek to learn universal policy Tu for selecting informative labeled nodes on graphs, which able to transfer to new unseen graphs in the test graph set G' E S
We first introduce our approach for learning policy network on a single graph and then introduce how to learn a universal policy with multiple training graphs.
3.2 ACTIVE LEARNING ON A SINGLE GRAPH
Recall that our goal is to learn a policy for selecting a set of nodes for annotation, such that graph neural network trained with the labels of the selected nodes can have the optimal performance on test nodes. We formalize the problem as sequential decision process (a.k.a., Markov decision process. We define the state as the current graph with the node attributes as whether they are picked or not and their label distributions predicted by the current graph neural network, and the action as picking a node for which we query the label. Once a node is picked, we will add this node into training set and retrain the graph neural network, which will update the state. The performance gain on validation set is treated as the intermediate reward. The goal is to maximize the total sum of the reward, i.c., the final performance of the graph neural network. More specifically, for the state representation, we define the node features as follows:
Heuristic Features. One effective criterion to active learning is the uncertainty of the prediction given by the training model, i.c., the entropy of the label distribution computed by the current graph neural network. Moreover, we also use the degree of a node, which widely used in existing graph active learning methods (Cai et al. 2017). The details of heuristic features are presented in Appendix. Note that all the heuristies we use are transferable to other unseen graphs. Structural Features. Another observation is that nodes with similar structural roles should be similarly informative. Therefore, we also use some structural features. Specifically, we use the Struc2vec model (Figueiredo et al., (017)) to learn latent representation for each node, which captures the local role of nodes. Struc2vec model allows joint training over different graphs, so once we learn the latent representations for all nodes of the graph that we are interested in, transfer learning can be done on this unified semantic space.
Historical Features. Another important information is the historical information, i..., which nodes are already annotated and which nodes are not. Motivated by that, we add an extra dimen- sion in the feature vector of node, where means the node is already annotated, and otherwise.
3

---

Under review as a conference paper at ICLR 2020
Moreover, also average the struc2vec features of all previously annotated nodes to capture the historical information.
After getting the feature vector x defined above for each node at the state 8, pass them to 2-layer graph convolutional networks to propagate the information of a node to its neighbors, and the final node representation, i.e., the state representation, is computed z GCN(x
We solve the problem by training a policy network т, which defines a distribution over actions conditioned states, ie., the probability of selecting node given the current state (aas)) We parameterize the policy network with a linear energy-based model as follows:
π (a = u|s) = Z
exp(w (w' z
(I)
where weight vector, and the normalization term.
Our goal is to maximize the total sum of reward following the policy л, which can be characterized by the following objective function:
Oc(T) = -E,dd (s) (a (ra a)),
(2)
where (s) = - - PPr(s the policy т, with Pr(50 + s, ki π) being the probability that the agent arrives at state 8 in the k-th step starting from state Su. and being the decay factor. (s a) is the reward function that graph, which is computed as the performance gain on the validation set after taking action a at s. Such an objective function
k π) is the stationary state distribution graph G induced by
be effectively optimized by using the REINFORCE algorithm (Williams) 1992], where we sample some trajectories from the policy, and further update the parameters.
Next, we introduce how we learn unified policy in the transfer learning setting.
3.3 TRANSFER ACTIVE LEARNING ON MULTIPLE GRAPHS
The above approach focuses on active learning on a single graph. In practice, more important problem is learn universal policy from multiple training graphs, and further transfer the policy to unseen graphs. Towards this goal, we propose two effective approaches, i.e., joint training approach and a distillation approach.
3.3.1 JOINT TRAINING APPROACH
The joint training approach is quite straightforward. Basically, the universal policy म. is parameter- ized by using the policy network proposed in Section 3.2 We train the universal policy jointly on all the training graphs, resulting the following objective function:
O Joint (TT)
Σ OG(TT).
(3)
GESEn
where Og is the objective function on each single graph defined in Eq. 2 Such an approach can be effectively optimized by stochastic gradient descent, where combining the gradient computed from each single graph based on Eq. 3
The problem of the joint training approach is that different graphs could have different optimal policies. Next, we introduce a more advanced approach to solve the problem.
3.3.2 DISTILLATION APPROACH
Inspired by Teh et al. (2017). in the distillation approach, besides the universal policy Ta we also introduce graph-specific policy TG for each training graph G E Suain- Each graph-specific policy can be viewed as an instantiation of the universal policy on the corresponding graph, which aims at maximizing the performance (i.e., the total sum of the reward) for the specific task on that graph.
To coordinate the collaboration of different policies, we propose to minimize the following KL. divergence between the action distributions computed by n. and each πo:
Σ Ge
Egndey (s) [[
4

---

Under review as a conference paper at ICLR 2020
Intuitively, with this term, the universal policy serves bridge connect different graph-specific policies. such that different graph-specific policies can exchange information during training. Mcan- while, by minimizing the KL divergence, the knowledge learned by different graph-specific graph policies will be effectively distilled into the universal query policy, which can be further applied to other graphs for active learning.
The overall objective function of the distillation approach is further obtained by combining the objective function each single graph and the above regularization term, which can be formally written as follows:
ODisin (Tu {TO))
Σ GES
OO(TT)
Csa Σ
[
(5)
GESmm
where Cx. is hyperparameter to control the weight of the KL. term.
For each graph-specific policy TG, it can be optimized by the REINFORCE algorithm. Formally, by taking a series of actions with Ta on graph G. we obtain a trajectory {(G.. dG.t, rG.:))=-1 With the trajectory, the value of each state-action pair (sG,,, aG.)) can be further estimated as follows:
(56,,
/' tra, + Cu LogTu(aa,,sea Ca. log (30,0, p=t
(6)
When computing Qra (SG.e) u..:), besides the reward ra,, received each step, two other terms are also incorporated to shape the reward function. For the first term log Ty (ac.alsa,.) . it gives an action larger reward if the action receives large probability from the universal policy Ta. In this way, the universal policy provides extra guidance to regularize each graph-specific policy. For the second term log मh (aG. (&,,),, it improves exploration by increasing the entropy of Th (a,,) which is commonly used in the reinforcement learning literature (Schulman et al. (2017).
With the estimated Q value, we can further estimate the gradient for the parameters Og of na as follows:
T Σ Qna (G. ag.1) Vec log (og,olac,lsc..).
Vec Disun (Tu, (Tc))
Meanwhile, the universal policy can also be optimized through stochastic gradient descent. Specifi- cally, we treat the trajectories generated by graph-specific policies as expert trajectories, and estimate the gradient for the parameters 0g of the universal policy follows:
T
Ve,, Disiin (Tu, {TG))
Σ
Ve, log Tag, (ac.11sa.)..
GESuia
By using the trajectories from graph-specific policies as expert trajectories, we can effectively distill the knowledge into the universal policy, which can be further applied unseen graphs.
The detailed optimization algorithm is summarized in Alg. 1.
Algorithm Pseudo code of our distillation-based approach.
1:
procedure OPTIMIZEPOLICY ((G))
episode do for graph do
4: initialize classification network and train with random initial seeds for step < Nuudge Nued do
5:
6:
feed Sa. CNN and generate कह according !T) action ae,, +- sample action from कе
8:
reward ra.t, new state &G.++1 +- update classification network using action update To. nu according to (7). respectively
9:
10:
end for end for
12:
end for
13:
end procedure
5

---

Under review as a conference paper at ICLR 2020
Table 1: Dataset statistics
Graphs
Nodes
Edges
Edge density
Features
Classes
Cora
2708
5278
0,0014
1433
7
Citseer
3327
4676
0,0008
3703
Pubmed
19718
44327
0,0002
500
Coauthor-es
18333
81894
0.0005
6805
67
Cora-full
18707
62421
0,0004
8710
15
ppi
20
2245.3
61318.4
0.0248
50
121 (multilabel)
EXPERIMENT
In this section, we empirically evaluate our proposed active learning approaches several datasets. Specifically, we consider active learning on single graphs, transfer active learning on homologous graphs and transfer active learning on heterogeneous graphs.
4.1 DATASETS
Active learning on single graphs. We utilize three benchmark datasets for node classification, i.e., Cora (Sen et al. 2008), Citeseer (Sen et al. 2008) and Pubmed (Namata et al.) 2012).
Transfer active learning on homologous graphs. For transfer active learning, we consider set of homologous graphs from the PPI dataset (20 graphs) (Zitnik & Leskoved (017). where each graph is constructed based on the interactions between proteins. We randomly partition the 20 graphs into 4 groups. Within each group, two graphs are used for training, one graph for validation and the other two for test. For each training graph, split all the nodes to train/validation/test sets with a ratio of 3:1:1. As there are too many node categories (121 categories in total), we randomly select 10 categories as our prediction target.
Transfer active learning on heterogeneous graphs. To test whether our learned policy can transfer across graphs with different structures, we also consider a group of heterogencous graphs. Specifically, we incorporate two extra graphs, i.e., Coauthor- CS and Cora-Full from Shchur et al. (2088), besides Cora, Citeseer and Pubmed. The Cora and Citeseer datasets are used for training, and we evaluate the learned policy the Pubmed, Coauthor-CS and Cora-Full datasets.
The statistics of datasets are presented in Table where for the PPI dataset, we report the average statistics of its 20 graphs.
4.2 COMPARED ALGORIHTM
We compare the following algorithms in experiment.
(1) Random Policy. At each state, the policy randomly selects node and queries for its label. (2) Entropy-base Policy. At each state, we predict the label distribution for each node by using the current graph neural network, and further compute the entropy. The policy selects the node with the maximum entropy for annotation. (3) Centrality-based policy. This policy selects the node with the largest degree to query for the node label. (4) AGE (Cai et al. 2017). AGE is an active learning method for training graph neural networks. At each state, AGE measures the informativeness of each node by linearly combining several heuristics, including the entropy of the predicted label distribution, PageRank score and the cluster assignment. Then it selects the most informative node to annotate. To apply AGE to the transfer learning setting, we learn the optimal weight of different heuristics on the training graphs, and further transfer the weight unseen graphs. (5) DAG-Single. Our proposed approach to active learning on single graphs. (6) DAG-Joint. Our joint training approach transfer active learning for graph neural networks. (7) DAG-Distill. Our distillation- based approach to transfer active learning, where a universal and a set of graph-specific policies are learned in a collaborative way.
4.3 PARAMETER SETTINGS
All the compared methods aim to select set of nodes, for which query the node labels. Then a prediction graph neural network is trained by using the selected nodes, and the reward function is defined according to the performance of the graph neural network. In our experiments, we two-

---

Under review as a conference paper at ICLR 2020
Table 2: Active learning on single graphs
Cora
Citeseer
Pubmed
Method
Micro-f1
Macro-f1
Micro-f1
Macro-fl
Micro-f1
Macro-f1
Random
66.5 + 4.5
58.2 + 8.0
60.7 + 5.9
53.0 + 6.5
68.1 5.6
66.5 + 7.0
Entropy
68.0 + 3.6
62.3 5.8
62.4 4.0
56.2 3.7
69.8 4.4
68.5 1
Centrality
51.7 + 9.2
36.8 + 13.4
47.2 11.7
38.3 + 12.8
69.0 + 4.6
67.3 5.9
AGE
71.8 + 3.8
67.4 17.4:55
68.9
61.8 2.5
74.7 + 4.3
72.8 + 6.0
DAG-Single
73.2 + 2.2
66.9 - 4.0
71.1 2.0
62.4 - 2.7
79.1 + 2.3
78.0 2.1
Table 3: Transfer active learning on homologous graphs (PPI dataset)
0-4
5.9
10-14
15-19
Method
Micro-fl
Macro-fl
Micro-f1
Macro-fl
Micro-f1
Macro-f1
Micro-fl
Macro-f1
Random
5124 3.4
31.0
50.3 1.34.88. 5.8
41.6
7.0
43.3
32.1 18
20.6 7.2
15.4
Entropy
47.5 + 3.7
22.2 + 6.5
40.0 + 9.8
28.8 + 9.1
34.4 + 7.7
21.7 + 79
13.6 + 7.5
10.1 + 5.3
Centrality
49.5 4.4
26.2
8.2
46.1
10.0
35.8
11.3
39.6 7.2
25.2 11.0
21.1
13. 74
AGE
1.3
41.4 2.3
2.0
512
48.7 2.3
4.0
32.0 25
2..0
DAG-Joint
53.1 1 1.0
42.0
1.3
56.6 1.5
52.9 = 1.8
49.4
104410
13.5.3 L8
34.5 = 1.6
31.6 2 211
DAG-Distill
53.2 + 1.0
42.1 = 1.4
56.7 = 1.4
53.1 = 1.6
49.7 + 1.2
43.6 +
1.6
34.2 = 1.7
31.3
2 2.0
layer graph convolutional network (Kipf & Welling. 2016 the prediction graph neural network, which is optimized by the Adam optimizer (Kingma & Ba 2014 with weight decay of 0.0005.
Active learning on single graphs. On single graphs, we use SGD optimize our policy network with a learning rate as 0.01. The hidden dimension of the policy network is set to 128. The total budget (i.e., the total number of nodes to select) is set as 5 x Netass by default, with Netass being the number of node classes on each dataset.
Transfer active learning. On homologous graphs, the budget for active learning is set to 20, The weight of the KI. term for the distillation approach is set to 0.0001. On heterogeneous graphs, we set the budget for active learning to x Nelnss by default, and the weight of the KI. term 0.0001.
We do 50 experiments for each setting and report the mean and standard error of micro-fl and macro-fl. Note that because AGE is much slower than our algorithms, for Cora-full dataset, we only report the mean and standard error of 10 experiments when using AGE as the strategy.
4.4 COMPARISON WITH BASELINE ALGORITHMS
In this section, we compare approach DAG against the baseline algorithms.
Active learning on single graphs. Table 2 presents the result of active learning on single graphs. Compared with the random policy and policies using simple heuristics such as entropy and centrality, our approach significantly outperforms them, since we consider more useful features. The AGE method also explores several features, but our approach still achieves better results especially large graphs (Pubmed). This is because our approach parameterizes the policy network by using a deep architecture, which has better capacity than AGE, AGE simply combines features in linear way. Moreover, DAG is trained by using a reinforcement learning framework, which can do exploration more effectively.
Transfer active learning. Table 3 and table 4 present the results of transfer active lcarning. We see that both of our proposed approaches (DAG-Joim) and DAG-Distill) significantly outperform all the baseline methods, showing that they can indeed learn an effective universal policy to transfer to the unseen graphs. Comparing DAG-Joint and DAG-Distill, we see that the simple joint training approach DAG-Joint achieves close results to DAG-Distill on the PPI dataset. This is because the graphs in the PPI dataset are homologous, which implies that different graphs have similar optimal policies, and therefore the policy learned by DAG-Joint is reasonably effective. On heterogeneous graphs, DAG-Distill achieves relatively better results.
4.5 PERFORMANCE UNDER DIFFERENT BUDGETS
The previous results have proved the effectiveness of our proposed approaches on single graphs and in the transfer learning settings, where a fixed number of budget (i.e., the total number of nodes to

---

Under review as a conference paper at ICLR 2020
Table 4: Transfer active learning on heterogencous graphs
Pubmed
Coauthor-cs
Cora- full
Method
Micro-fl
Macro-fl
Micro-fl
Macro-fl
Micro-fl
Macro-fl
Random
68.1 + 5.6
66.5 + 7.0
85.0 + 3.0
71.4 6.2
46.3 1.8
33.8 + 1.9
Entropy
69.8 4.4
68.5+ 5.6
82.2 + 4.5
77.7 5.9
47.1 + 1.6
33.1
1.8
Centrality
69.0 + 4.6
67.3 + 5.9
68.4 + 12.9
46.3 + 17.8
31.4 9.1
18.0 9.0
AGE
74.7 + 4.3
72.8+ 6.0
88.1+ 1.7
80.6 + 5.7
49.1 1.4
37.1 +
DAG-Joint
75.6 - 3.5
71.6 = 6.7
88.9 1.3
83,9
51,4 - 1.2
39.8 + 1.3
DAG-Distill
76.4 3.1
73.3 = 5.5
89.3 = 1.1
85.6 + 2.6
49.8 + 1.3
38.1
1.4
query) is considered. Next, we study the performance the compared algorithms under different budgets, where two cases are considered. In the first case, we train our policy on Cora and Citeseer with a budget in {2, 5, 10, 20). and then we evaluate the learned policy on Pubmed by using the same budget. In the second casc, train the policy on graphs of the PPI datasets with a budget in {1,2, 5, 10). Afterwards, the learned policy is applied to other graphs under the same budget.
The results presented in Figure 2 We that our proposed approach outperforms the strongest baseline algorithm AGE in most cases. Moreover, when the budget is small, DAG achieves relatively large improvement over AGE, which demonstrates that the policy trained by our approach can indeed learn to select the most informative nodes in a graph. addition, one goal of active learning is to reduce the annotation efforts by achieving good performance with fewer annotations. In the first case, we see that the graph neural network trained by our approach achieves micro-fl score of 76% with 15 annotations, whereas AGE achieves the same micro-fl score with 30 annotations. Therefore, our proposed approach can indeed help reduce the annotation efforts by learning an effective universal policy on several training graphs.
4.6 CASE STUDY AND ABLATION STUDY
We also conduct some study show what the nodes selected by trained policy network and an ablation study to show the importance different types of node features for representing the states. The results available the appendix (Section A.I and A.2
rindoo
IENEC
DAC-D
20
bedgei Jox dhoul
booged
Figure 2: Performance of DAG-Distill under different budgets. Vertical lines represent the standard error of experiments
CONCLUSION
This paper studies active learning for graph neural networks, where two different settings are con- sidered, i.e., active learning single graphs and transfer active learning multiple graphs. We for- malize the problem as a sequential decision making process, and propose a policy gradient method single graphs. For transfer reinforcement learning, joint training approach and distillation- based approach are proposed. Experimental results prove the effectiveness of our approaches. the future, plan our approach in larger datasets, where large number of graphs available.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Roy Abel and Yoram Louzoun. Regional based query in graph active learning. CoRR, Abs//100.08841,, 2019. URL htttttttp///xiiii .rg/ hts///bs//e// 1906. 08541]
Philip Bachman, Alessandro Sordoni, and Adam Trischler. Learning algorithms for active learning.
In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 301-310, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL http:// ml http:///.........eeeeee///////aa
html
YongYun Cai, Vincent Wenchen Zheng, and Kevin Chen- Chang. Active learning for graph embedding. CoRR, abs/1705.05085, 2017. URL
Zhu Cao, Linlin Wang, and Gerard De Melo. Link prediction via subgraph embedding-basee convex matrix completion. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Meng Fang, Yuan Li, and Trevor Cohn. Learning how to active lear: A rentooreentt learning approach. CoRR, 0tts/178.00200 2017. URL http:::taarxv...or/////// htth//bb//1111
Daniel R. Figueiredo, Leonardo Filipe Rodrigues Ribeiro, and Pedro H. P. Saverese. struc2vec: Learning node representations from structural identity. CoRR, abs/1704.03165, 2017. URL
http://arxiv wttpxx//...////////100.0.00.
Akshay Gadde, Aamir Anis, and Antonio Ortega. Active semi-supervised learning using sampling theory for graph signals. CoRR, abs/ Abs//405,4m 4324, 2014. URL http:// http:://xxxvvv.g//aa..
1405. 4324
Brian Gallagher, Hanghang Tong, Tina Eliassi-Rad, and Christos Faloutsos. Using ghost edges for classification in sparsely labeled networks. In Proceedings of the 14th ACM SIGKDD interna- tional conference Knowledge discovery and data mining, pp. 256 264. ACM, 2008
Andrew Guillory and Jeff A Bilmes. Label selection on graphs. Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (eds.), Advances in Neural Information Processing cc/
Systems 22, pp. 691-699. Curran Associates, Inc., 2009, URL http://papers. paper/3752-2 -ow.-aaaee--eeeeeee.eooooo------ p
Ming Ji and Jiawei Han. variance minimization criterion to active learning on graphs. In Artificial Intelligence and Statistics, pp. 556-55664 2012.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1xXiv:660000200000 2016.
F. Lin and W. W. Cohen. Semi-supervised classification of network data using very few labels. In 2010 International Conference on Advances Social Networks Analysis and Mining, pp. 192- 199, Aug 2010. doi: 10. R..1009AAOONAM.200.....
Ming Liu, Wray Buntine, and Gholamreza Haffari. Learning how to actively learn: deep im- itation learning approach. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1874-1883, Melbourne, Australia, July 2018a. Association for Computational Linguistics. doi: 10. (0.18653/1//118-117 URL
https: www http://wwwww..eeeeee.ooooocttaaa
Ming Liu, Wray Buntine, and Gholamreza Haffari. Learning actively lear neural machine trans- lation. In Proceedings of the 22nd Conference on Computational Natural Language Learning, pp. 334-344, 2018b.
Galilco Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. 2012.

---

Under review as a conference paper at ICLR 2020
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft qr learning. arXiv preprint arXiv:170..06440, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann, Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018.
Yee Tch, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In Advances in Neural Information Processing Systems, pp. 14966-4506 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003 2017.
Ronald J Williams. Simple statistical gradient-followigg algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25) 1992.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. arXiv preprint arXiv:1603.0886/ 2016.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1190-1198, 2017.
10

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1 CASE STUDY
To demonstrate the policy learned by algorithm is indeed reasonable, show the sequence of nodes selected by our algorithm. Taking the performance DAG-Distill policy Tu on Cora dataset example, for each step of node selection, draw the subgraph formed by the selected nodes and their 2-hop neighbors. The predicted classes are represented in different colors and the probabil- ities of the predictions are represented by the transparency of the color (the higher the transparency is, the lower the probability is). Further more, the nodes of the largest size are selected in the cor- responding step and the medium sized nodes were select previously. At the initial state of the node selection, the policy tends to choose the nodes in the center of region with less diversity of labels (e.g. step I, step 3, step 5). the middle stage, the policy prefers the nodes that serve as bridge of two densely connected components (e.g. step 23, step 25). In the latter stage, the policy tends to choose the node with great diversity of neighbor (e.g. step 26, step 28).
stop
stop
step
stop 11
step 13
8880
17
atop 19
21
aleo 23
step
step 28
step
sl5o 28
Figure 3: Case study carried out on Cora dataset
11

---

Under review as a conference paper at ICLR 2020
A.2
ABLATION STUDY
We conduct contrast experiments to study the importance of different features to the model. We take DAG-Single on Cora dataset an example. To study the importance of structure feature the model (denoted by -structure in Table we substitute the Struc2vec features with random vectors and report the performance of model trained with the absence of Struc2vec features. Similarly, other features are replace by zero or random vectors in order to demonstrate the their importance. From the table, we see that heuristic features and structure features both have significant benefits to the model. However, the historical features do not have positive influence on the model, possibly because the selected nodes are actually very small fraction of selection pool, thus may not providing much information. Future study will be carried out to better leverage the historical information.
Table 5: The importance of different features in our algorithm
historical
heuristic
structure
DAG-Single
Micro-fl
73.2 2.4
70.7 3.1
70.5 65.9 + 3.5
73.1 2,5
Macro-f1
66.8 + 5.0
62.9 + 5.4
65.9 + 5.0
12


Reviews:
[{"review_id": "SJev7G8sYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed a new method for active learning on node classification with GCN. RL based framework is used. The labeled graph is treated as state and the action is labeling the nodes. Validation accuracy on the hold out set is used as reward. Further transfer learning framework is also proposed, where graph-specific policy and master policy are jointly learned. Experiments on benchmark dataset show the effectiveness of proposed method compared to several baselines.\n\nThe idea of applying RL on active learning with GCN seems to be new and it sounds natural and technically. Also the idea of transferring the learned policy to new graphs make sense for similar graphs. However, the empirical results are a bit weak and not convincing enough for me. Please find the detailed comments below.\n\n1. Is the state defined on node level or graph level? Eq (1) is defined on node level, but I believe it should be a global policy on graph.\n2. All the results have a rather high variance. To compare such results, the authors should make a significant test. Otherwise, one cannot say that the performance from one method is better than the other. Especially, for Table 3 and 4, DAG-distill performs not better than DAG-Joint.\n3. What do \"0-4, 5-9,...\" mean in Table 3?\n4. Can the authors show curve as in figure 2 for table 2 and 3. It is important to see the progress for active learning.\n5. Why the results differ so much in Figure 2 for only 1 query? I believe the first one should be randomly picked. Thus all the methods should perform equally.\n6. \"Graphs encode the relations between different objects and are ubiquitous in real-world.\" Typo in first sentence.\n7. homologous or homogenous?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SJejFIWTFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Thank you for the author response.\nOriginal review:\n\nThis paper presents a method for active learning on graphs, including a novel setting of transferring an active learning policy to unseen graphs.  The problems tackled here are important and the method is shown to improve over previous work in some cases.  On the down side, the evaluation may be missing one important method of comparison, the reasons for the proposed approach winning over previous work are not made explicit, and the empirical advantage of the approach is inconsistent (by my count, in the majority of cases the F1 advantage over previous work is within the standard error).  This paper has strengths but I feel it needs further refinement before publication.\n\nThe introduction of the paper claims that existing approaches for active learning on graphs are domain-specific and may not apply well to new domains.  But later, in the experiments, different reasons for the proposed approach's wins are given (in particular, on large graphs the proposed approach does relatively better vs. AGE which the paper suggests is due to the more complex nonlinear models used in the proposed approach).  In general, this paper’s approach tends to win over the primary baseline (the AGE method from Cai et al. 2017), but the wins are relatively small and inconsistent (esp. taking into account the standard error) whether the methods are evaluated in the single-graph setting or the transfer learning setting (of the homologous or heterogeneous variety).  If the limitation of previous work was domain-specificity, I would expect to see much larger wins on the transfer learning setting.  In general, an analysis that explains more what is driving the gains of this approach over the AGE approach would help us know how to build on this paper’s method in future work.\n\nI was curious why the paper does not compare against the following work, which also presents an approach that wins over AGE:\n“Active Discriminative Network Representation Learning,” Gao et al., IJCAI 2018\n\nLastly, the distillation-based approach, which learns graph-specific policies that are trained to fit their target graphs and to minimize their KL divergence from a single global shared policy, was interesting.  The fact that it doesn’t work much better than the joint policy is somewhat disappointing, but it’s still interesting.\n\nMinor:\nSec 3.2: unclosed parenthesis in first paragraph\n“Moreover, we also average the struc2vec features of all previously annotated nodes to capture the historical information” -- since the model has only node-level features, I didn’t understand how this average across multiple nodes was fed in as a node feature.  Is it used in all nodes?  Only annotated nodes?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklvSUYRFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Positive\n1. The paper studies a universal policy for labeling nodes on graphs with multiple training graphs which can be transferred to new unseen graphs.\n2. The paper focuses on minimizing human efforts in obtaining labeled data. The model is based on active learning and transfer learning. \n\nNegative\n1. The proposed method combines existing models as the solution, which is heuristic and lacks persuasive theoretical proofs. \n2. In graphs, data (nodes) to be labeled are highly correlated. However, there is no method for solving this challenge.\n3. In Section 3.2, ACTIVEL EARNING ON A SINGLE GRAPH, the authors formalize the problem, i.e., learning a policy for selecting a set of nodes for annotation, as a sequential decision process, and the reinforce algorithm is applied to optimize the objective function. However, explanation about the active learning is confusing. More details are needed to explain their respective goals and to explain how to integrate active learning and reinforcement learning. \n4. The authors claim that the details of heuristic features are represented in Appendix, please add these information.\n5. The settings of active learning need more consideration. The total budget for active learning is set as $5\\times N_{class}$. How to choose these nodes? Is it to select all samples at once or in batches during iterative epoch? If the samples are selected in batches, what is the specific experimental setting?\n6. The experimental method about active learning. The paper focuses on minimizing human efforts in obtaining labeled data. Compared to the results of the model before selecting, how significant is the improvement after selecting all the node in the budget? More experiments are needed.\n7. Minor format issue: the fonts in Table 2 and Table 3 are different. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Paper proposes a method for active learning on graphs. Reviewers found the presentation of the method confusing and somewhat lacking novelty in light of existing works (some of which were not compared to). After the rebuttal and revisions, reviewers minds were not changed from rejection. 
Decision: Reject