Graph Neural Networks (GNNs) for prediction tasks like node classification or edge prediction have received increasing attention in recent machine learning from graphically structured data. However, a large quantity of labeled graphs is difficult to obtain, which significantly limit the true success of GNNs. Although active learning has been widely studied for addressing label-sparse issues with other data types like text, images, etc., how to make it effective over graphs is an open question for research.   In this paper, we present the investigation on active learning with GNNs for node classification tasks.   Specifically, we propose a new method, which uses node feature propagation followed by K-Medoids clustering of the nodes for instance selection in active learning. With a theoretical bound analysis we justify the design choice of our approach. In our experiments on four benchmark dataset, the proposed method outperforms other representative baseline methods consistently and significantly. Graph Neural Networks (GNN) (Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017; Wu et al., 2019) have been widely applied in many supervised and semi-supervised learning scenarios such as node classifications, edge predictions and graph classifications over the past few years. Though GNN frameworks are effective at fusing both the feature representations of nodes and the connectivity information, people are longing for enhancing the learning efficiency of such frameworks using limited annotated nodes. This property is in constant need as the budget for labeling is usually far less than the total number of nodes. For example, in biological problems where a graph represents the chemical structure (Gilmer et al., 2017; Jin et al., 2018 ) of a certain drug assembled through atoms, it is not easy to obtain a detailed analysis of the function for each atom since getting expert labeling advice is very expensive. On the other hand, people can carefully design a small "seeding pool" so that by selecting "representative" nodes or atoms as the training set, a GNN can be trained to get an automatic estimation of the functions for all the remaining unlabeled ones. Active Learning (AL) (Settles, 2009; Bodó et al., 2011) , following this lead, provides solutions that select "informative" examples as the initial training set. While people have proposed various methods for active learning on graphs (Bilgic et al., 2010; Kuwadekar & Neville, 2011; Moore et al., 2011; Rattigan et al., 2007) , active learning for GNN has received relatively few attention in this area. Cai et al. (2017) and Gao et al. (2018) are two major works that study active learning for GNN. The two papers both use three kinds of metrics to evaluate the training samples, namely uncertainty, information density, and graph centrality. The first two metrics make use of the GNN representations learnt using both node features and the graph; while they might be reasonable with a good (well-trained) GNN model, the metrics are not informative when the label budget is limited and/or the network weights are under-trained so that the learned representation is not good. On the other hand, graph centrality ignores the node features and might not get the real informative nodes. Further, methods proposed in Cai et al. (2017) ; Gao et al. (2018) only combine the scores using simple linear weighted-sum, which do not solve these problems principally. We propose a method specifically designed for GNN that naturally avoids the problems of methods above 1 . Our method select the nodes based on node features propagated through the graph structure, 1 Our code will be released upon acceptance. making it less sensitive to inaccuracies of representation learnt by under-trained models. Then we cluster the nodes using K-Medoids clustering; K-Medoids is similar to the conventional K-Means, but constrains the centers to be real nodes in the graph. Theoretical results and practical experiments prove the strength of our algorithm. • We perform a theoretical analysis for our method and study the relation between its classification loss and the geometry of the propagated node features. • We show the advantage of our method over Coreset (Sener & Savarese, 2017) by comparing the bounds. We also conjecture that similar bounds are not achievable if we use raw unpropagated node features. • We compare our method with several AL methods and obtain the best performance over all benchmark datasets. We study the active learning problem in the node classification task for Graph Convolution Networks (GCNs). We propose a propagated node feature selection approach (FeatProp) to comply with the specific structure of GCNs and give a theoretical result characterizing the relation between its classification loss and the geometry of the propagated node features. Our empirical experiments also show that FeatProp outperforms the state-of-the-art AL methods consistently on most benchmark datasets. Note that FeatProp only focuses on sampling representative points in a meaningful (graph) representation, while uncertainty-based methods select the active nodes from a different criterion guided by labels, how to combine that category of methods with FeatProp in a principled way remains an open and yet interesting problem for us to explore.
This paper introduces a clustering-based active learning algorithm on graphs.
{"src": "scitldr-AIC_train", "paper_id": "HylwpREtDr"}