RIM: Reliable Influence-based Active Learning on Graphs
Year: 2021

Abstract:
Message passing is the core of most graph models such as Graph Convolutional Network (GCN) and Label Propagation (LP), which usually require a large number of clean labeled data to smooth out the neighborhood over the graph. However, the labeling process can be tedious, costly, and error-prone in practice. In this paper, we propose to unify active learning (AL) and message passing towards minimizing labeling costs, e.g., making use of few and unreliable labels that can be obtained cheaply. We make two contributions towards that end. First, we open up a perspective by drawing a connection between AL enforcing message passing and social influence maximization, ensuring that the selected samples effectively improve the model performance. Second, we propose an extension to the influence model that incorporates an explicit quality factor to model label noise. In this way, we derive a fundamentally new AL selection criterion for GCN and LP–reliable influence maximization (RIM)–by considering quantity and quality of influence simultaneously. Empirical studies on public datasets show that RIM significantly outperforms current AL methods in terms of accuracy and efficiency.

heading: 1 Introduction
text: Graphs are ubiquitous in the real world, such as social, academic, recommendation, and biological networks [38, 30, 31, 10, 28]. Unlike the independent and identically distributed (i.i.d) data, nodes are connected by edges in the graph. Due to the ability to capture the graph information, message passing is the core of many existing graph models assuming that labels and features vary smoothly over the edges of the graph. Particularly in Graph Convolutional Neural Network (GCN) [16], the feature of each node is propagated along edges and transformed through neural networks. In Label Propagation (LP) [25], node labels are propagated and aggregated along edges in the graph.
The message passing typically requires a large amount of labeled data to achieve satisfactory performance. However, labeling data, be it by specialists or crowd-sourcing, often consumes too much time and money. The process is also tedious and error-prone. As a result, it is desirable to achieve good classification results with labeled data that is both few and unreliable. Active Learning (AL) [1] is a promising strategy to tackle this challenge, which minimizes the labeling cost by prioritizing the selection of data in order to improve the model performance as much as possible. Unfortunately, conventional AL methods [3, 8, 20, 41, 21, 27] treat message passing and AL independently without explicitly considering their impact on each other. In this paper, we advocate that a better AL method should unify node selection and message passing towards minimizing labeling cost, and we make two contributions towards that end.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The first contribution is that we quantify node influence by how much the initial feature/label of label node v influences the output feature/label of node u in GCN/LP, and then connect AL with influence maximization, e.g., the problem of finding a small set of seed nodes in a network that maximizes the spread of influence. To demonstrate this idea, we randomly select different sets of |Vl| = 20 labeled nodes under the clean label and train a 2-layer GCN with a different labeled set on the Cora dataset [16]. For LP, we select two sets with the average node degree of 2 and 10. As shown in Figure 1, the model performance in both GCN/LP tends to increase along with the receptive field/node degree under the clean label, implying the potential gain of increasing the node influence.
Note that in real life, both humans and automated systems are prone to mistakes. To examine the impact of label noise, we set the label accuracy to 50%, and Figure 1(a) and Figure 1(b) show that the test accuracy could even drop with the increase of node influence under the noisy label. This is because the noise of labels will also be widely propagated with node influence increasing, thus diminishing the benefit of influence maximization. Therefore, our second contribution is that we further propose to maximize the reliable influence spread when label noise is taken into consideration. Specifically, each node is associated with a new parameter called the quality factor, indicating the probability that the label given by the oracle is correct. We recursively infer the quality of newly selected nodes based on the smoothing features/labels of previously selected nodes across the graph’s edges, i.e., nodes that share similar features or graph structure are likely to have the same label.
Based on the above insights, we propose a fundamentally new AL selection criterion for GCN and LP–reliable influence maximization (RIM)–by considering both quantity and quality of influence simultaneously. Under a high-quality factor, we enforce the influence of selected label nodes for large overall reaches, while under a low-quality factor, we make mistake penalization to limit the selected node influence. RIM also maintains some nice properties such as submodularity, which allows a greedy approximation algorithm for maximizing reliable influence to reach an approximation ratio of 1− 1e compared with the optimum. Empirical studies on public datasets demonstrate that RIM significantly outperforms the state-of-the-art methods GPA [13] by 2.2%-5.1% in terms of predictive accuracy when the labeling accuracy is 70%, even if it is enhanced with the anti-noise mechanism PTA [6]. Furthermore, in terms of efficiency, RIM achieves up to 4670× and 18652× end-to-end runtime speedups compared to GPA in GPU and CPU, respectively.
In summary, the core contributions of this paper are 1) We open up a novel perspective for efficient and effective AL for GCN and LP by enforcing the feature/label influence with a connection to social influence maximization [18, 9, 4]; 2) To the best of our knowledge, we are the first to consider the influence quality in graph-based AL, and we propose a new method to estimate the influence quantity based on the feature/label smoothing; 3) We combine the influence quality and quantity in a unified RIM framework. The empirical study on both GCNs and LP demonstrates that RIM significantly outperforms the compared baselines in performance and efficiency.

heading: 2 Preliminary

heading: 2.1 Active Learning
text: Problem Formulation. Let c be the number of label classes and the ground-truth label for a node vi be a one-hot vector yi ∈ Rc. Suppose that the entire node set V is partitioned into training set Vtrain
(including both the labeled set Vl and unlabeled set Vu), validation set Vval and test set Vtest. Given a graph G = (V ,E) with |V| = N nodes and |E| = M edges, feature matrix X = {x1,x2...,xN} in which xi ∈ Rd, a labeling budget B, and a loss function `, the goal of an AL algorithm is to select a subset of nodes Vl ⊂ Vtrain to label from a noisy oracle with the labeling accuracy α, so that it can produce a model f with the lowest loss on the test set:
arg min Vl:|Vl|=B
Evi∈Vtest [` (yi, P (ŷi|f))] , (1)
where P (ŷi|f) is the predictive label distribution of node vi. To measure the influence of feature or label propagation, we focus on f being GCN or LP.
AL on graphs. Both GCN and LP are representative semi-supervised graph models which can utilize additional unlabeled data to enhance the model learning [40], and lots of AL methods are specially designed for these two models. For example, both AGE [3] and ANRMAB [8] adopt uncertainty, density, and node degree when composing query strategies. LP-ME chooses the node that maximizes entropy for itself, while LP-MRE chooses the node such that the acquisition of its label reduces entropy most for the total graph [20].

heading: 2.2 Graph Models
text: LP. Based on the intuitive assumption that locally connected nodes are likely to have the same label, LP iteratively propagates the label influence to distant nodes along the edges as follows:
Y(k+1) = D̃−1ÃY(k), Y(k+1)u = Y (k+1), Y (k+1) l = Y (0), (2)
where Y(0) = {y1,y2...,yl} is the initial label matrix consisting of one-hot label indicator vectors, Y (k) u and Y (k) l denote the soft label matrix of the labeled nodes set Vl and unlabeled nodes set Vu in iteration k respectively. According to [39], we iteratively set the nodes in Vl back to their initial label Y(0) since their labels are correct and should not be influenced by the unlabeled nodes.
GCN. Each node in GCN iteratively propagates its feature influence to the adjacent nodes when predicting a label. Especially, each layer updates the node feature embedding in the graph by aggregating the features of neighboring nodes:
X(k+1) = δ ( D̃−1ÃX(k)W(k) ) , (3)
where X(k) and X(k+1) are the embeddings of layer k and k + 1 respectively. Specifically, X (and X(0)) is the original node feature. Ã = A + IN is used to aggregate feature vectors of adjacent nodes, where A is the adjacent matrix of the graph and IN is the identity matrix. D̃ is the diagonal node degree matrix used to normalize Ã, W(k) is a layer-specific trainable weight matrix and δ(·) is the activation function.

heading: 2.3 Influence Maximization
text: The influence maximization (IM) problem in social networks aims to select B nodes so that the number of nodes activated (or influenced) in the social networks is maximized [15]. That being said, given a graph G = (V, E), the formulation is as follows:
max S |σ(S)|, s.t. S ⊆ V, |S| = B, (4)
where σ(S) is the set of nodes activated by the seed set S under certain influence propagation models, such as Linear Threshold (LT) and Independent Cascade (IC) models [15]. The maximization of σ(S) is NP-hard. However, if σ(S) is nondecreasing and submodular with respect to S, a greedy algorithm can provide an approximation guarantee of (1− 1e ) [23]. RIM is the first to connect social influence maximization with graph-based AL under a noisy oracle by defining reliable influence.

heading: 3 Reliable Influence Maximization
text: This section presents RIM, the first graph-based AL framework that considers both the influence quality and influence quantity. At each batch of node selection, RIM first measures the proposed reliable influence quantity and selects a batch of nodes that can maximize the number of activated nodes, and then it updates the influence quality for the next iteration. The above process is repeated until the labeling budget B runs out. We will introduce each component of RIM in detail below.

heading: 3.1 Influence Propagation
text: We measure the feature/label influence of a node vi on vj by how much change in the input feature/label of vi affects the aggregated feature/label of vj after k iterations propagation [26, 33]. Definition 3.1 (Feature Influence). The feature influence 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 . The normalized influence score is defined as
If (vj , vi, k) = Îf (vj , vi, k)∑
vw∈V I(vj , vw, k) . (5)
Definition 3.2 (Label Influence). The label influence score of node vi on node vj after k-step propagation is the gradient of y(k)j with respect to yi:
Il(vj , vi, k) = ∥∥∥E[∂y(k)j /∂yi]∥∥∥
1 . (6)
Given the k-step feature/label propagation mechanism, the feature/label influence score captures the sum over probabilities of all possible paths of length k from vi to vj , which is the probability that a random walk (or variants) starting at vj ends at vi after taking k steps [33]. Thus, we could take them as the probability that vi propagates its feature/label to vj via random walks from the influence propagation perspective.

heading: 3.2 Influence Quality Estimation
text: Most AL works end up fully trusting the few available labels. However, both humans and automated systems are prone to mistakes (i.e., noisy oracles). Thus, we further estimate the label reliability and associate it with influence quality. The intuition behind our method is to exploit the assumption that labels and features vary smoothly over the edges of the graph; in other words, nodes that are close in feature space and graph structure are likely to have the same label. So we can recursively infer the newly selected node’s quality based on the features/labels of previously selected nodes.
Specifically, after k iterations of propagation, we calculate the node similarity s of node vi and vj in LP by measuring the cosine similarity in Y(k) according to E.q. (2). Like SGC [29], we remove the activate function δ(·) and the trainable weight W(k) and get the new feature matrix as: X̂(k+1) = D̃−1ÃX̂(k). For better efficiency in measuring the node similarity, we replace X(k) in E.q. (3) with the simplified X̂(k) since its calculation is model-free. Similar to LP, we get the node similarity s in GCN by measuring the cosine similarity in X̂(k). Larger s means vi and vj are more similar after k iterations of feature/label propagation and thus are more likely to have the same label. Theorem 3.1 (Label Reliability). Denote the number of classes as c. And assume that the label is wrong with the probability of 1 − α, and the wrong label is picked uniformly at random from the remaining c− 1 classes. Given the labeled node vi ∈ Vl and unlabeled node vj ∈ Vu, supposing the oracle labels vj as ỹj and ỹj = yi (the ground truth label for vi, the same notation also applies to vj), the reliability of node vj according to vi is
rvi→vj = αs
αs+ (1− α) 1−sc−1 (7)
where α is the labeling accuracy, and s measures the similarity between vi and vj .
Proof of Theorem 3.1 is in Appendix A.1. Intuitively, Theorem 3.1 shows that the label of node vj is more reliable if (1) The oracle is more proficient and thus has higher labeling accuracy α. (2) The labeled node vi is more similar to vj and thus leads to larger s. Definition 3.3 (Influence Quality). The influence quality of vj is recursively defined as
rvj = ∑
vi∈Vl,ỹj=ỹi
r̂virvi→vj , (8)
where rvi→vj is the label reliability of node vj with respect to node vi, and r̂vi = rvi∑
vq∈Vl,ỹj=yq rvq
is the normalized label reliability score of node vi.
For each unlabeled node vj , we firstly find all labeled nodes which have the same label with ỹj and then get the final influence quality with weighted voting [17]. The source node vi should contribute more in measuring its influence on another node vj if its label is reliable, i.e., with higher r̂vi .

heading: 3.3 Reliable Influence
text: Different from the original social influence method which only considers the influence magnitude [14, 34], we measure the influence quantity and get the reliable influence quantity by introducing the influence quality since it is common to have noisy oracles in the labeling process of Active Learning. Definition 3.4 (Reliable Influence Quantity Score). Given the influence quality rvi , the reliable influence quantity score of node vi on node vj after k-step feature/label propagation is
Q(vj , vi, k) = rviI(vj , vi, k), (9)
where I(vj , vi, k) is If (vj , vi, k) for GCN and Il(vj , vi, k) for LP.
The reliable influence quantity score Q(vj , vi, k) is determined by: (1) The influence quality of the labeled influence source node vi. (2) The feature/label influence score of vi on vj after k-step propagation. From the perspective of random walk, it is harder to get a path from vi to vj with larger steps k, and the influence score will gradually decay along with the propagation steps. As a result, node vj can get a highly reliable influence quality score from the labeled node vi if they are close neighbors and vi has high influence quality.
In a node classification problem, the node label is dominated by the maximum class in its predicted label distribution. Motivated by this, we assume an unlabeled node vj can be activated if and only if the maximum influence magnitude satisfies:
Q(vj ,Vl, k) > θ, (10) where Q(vj ,Vl, k) = maxvi∈Vl Q(vj , vi, k) is the maximum influence of Vl on the node vj , and the threshold θ is a parameter which should be specially tuned for a given dataset. Definition 3.5 (Activated Nodes). Given a set of labeled seeds Vl , the activated node set σ(Vl) is a subset of nodes in V that can be activated by Vl:
σ(Vl) = ⋃
v∈V,Q(v,Vl,k)>θ
{v}. (11)
The threshold θ = 0 means we consider an unlabeled node v is influenced as long as there is a k-step path from any labeled node, which is equal to measuring whether this unlabeled node can be involved in the entire training process of GCN or LP. In practice, we could choose this threshold value in the case of a tiny budget so that our goal is to involve unlabeled nodes as more as possible. However, if the budget is relatively large, we could choose a positive threshold θ > 0, which enables the selection process to pay more attention to those weakly influenced nodes.

heading: 3.4 Node Selection and Model Training
text: In order to increase the feature/label influence (smoothness) effect on the graph, we should select nodes that can influence more unlabeled nodes. Due to the impact of the graph structure, the speed
Algorithm 1: Batch Node Selection. Input: Initial labeled set V0, query batch size b, and labeling accuracy α. Output: Labeled set Vl
1 Vl = V0; 2 for t = 1, 2, . . . , b do 3 Select the most valuable node v∗ = arg maxv∈Vtrain\Vl F (Vl ∪ {v}); 4 Set the influence quality of v∗ to the labeling accuracy α; 5 Update the labeled set Vl = Vl ∪ {v∗}; 6 Update the influence quality of nodes in Vl \ V0 according to E.q. 8; 7 return Vl
of expansion or, equivalently, growth of the influence can change dramatically given different sets of label nodes. This observation motivates us to address the graph data selection problem in the viewpoint of influence maximization defined below.
RIM Objective. Specifically, RIM adopts a reliable influence maximization objective:
max Vl F (Vl) = |σ(Vl)|, s.t. Vl ⊆ V, |Vl| = B. (12) By considering both the influence quality and quantity, RIM aims to find a subset of B to label so that the number of activated nodes can be maximized.
Reliable Node Selection. Without losing generality, we consider a batch setting where b nodes are selected in each iteration. For the first batch, when the initial labeled set V0 = ∅, we ignore the influence quality term rvi in E.q. 9 since there are no reference nodes for measuring the label quality from the oracle. For better efficiency in finding selected nodes in each batch, we set the influence quality of each node to the labeling accuracy α during the node selection process and then simultaneously update these values according to E.q. 8 after the node selection process of this batch. For the node selection after the first batch, Algorithm 1 provides a sketch of our greedy selection method for the graph models, including both GCN and LP. Given the initial labeled set V0, query batch size b, and labeling accuracy α, we first select the node v∗ generating the maximum marginal gain (line 3), set its influence quality to the labeling accuracy α (line 4), and then update the labeled set Vl (line 5). After getting a batch of labeled nodes, we require the label from a noisy oracle (line 5) and then update their influence quality according to E.q. 8 (line 6). Theorem 3.2. The greedily selected batch node set is within a factor of (1− 1e ) of the optimal set for the objective of reliable influence maximization.
Proof of Theorem 3.2 is in Appendix A.2. The node selection strategy in both AGE and ANRMAB relies on the model prediction, while this process in RIM is model-free. Such a characteristic is helpful in practice since the oracle does not need to wait for the end of model training in each batch node selection of RIM. For example, if the model training dominates the end-to-end runtime, the main efficiency overhead of both AGE and ANRMAB is the model training.
Reliable Model Training. Nodes with larger influence quality in Vl should contribute more to the training process, so we introduce the influence quality in the model training. For GCN, we use the weighted cross entropy loss as: L = −∑vi∈Vl rviyi log ŷi, where rvi is the influence quality of node vi. For each labeled node vi in LP, we just change its label yi to rviyi.

heading: 3.5 Comparison with Prior Works
text: Existing AL works [35, 7, 2, 5] regarding label noise mainly focus on two phases: noise detection and noise handling. Both the data-driven and model-based methods are designed for noise detection. The former firstly constructs a graph from the dataset and then utilizes graph properties, e.g., the homophily assumption [22] without corrupting graph structure [24], while the latter [35] measures the likelihood of noise by the predicted soft labels [32]. For noise handling, existing works primarily concentrate on three aspects: data correction, objective function modification, and optimization policy modification [12]. However, none of these AL methods is specially designed for graphs and fails to consider the influence quantity imposed by the graph structure, leading to sub-optimal performance.
Meanwhile, there are also works [37, 8, 36] concerning graph-based AL, and they are designed for GCN or LP. Nonetheless, they fail to take into account the noise brought by oracles. That being said, the quality of influence is overlooked. Thus these methods suffer from a lack of robustness, especially when the quantity of noise is substantial. To sum up, current AL methods are unable to consider the quantity and quality of influence simultaneously. To bridge this gap, RIM introduces the influence quality to tackle the noise from the oracle. Besides, the influence quantity has been deliberated to get more nodes involved in semi-supervised learning.

heading: 4 Experiments
text: We now verify the effectiveness of RIM on four real-world graphs. We aim to answer four questions. Q1: Compared with other state-of-the-art baselines, can RIM achieve better predictive accuracy? Q2: How does the influence quality and quantity influence RIM? Q3: Is RIM faster than the compared baselines in the end-to-end AL process? Q4: If RIM is more effective than the baselines, what should be the reason?

heading: 4.1 Experiment Setup
text: Datasets and Baselines. We use node classification tasks to evaluate RIM in both inductive and transductive settings [11] on three citation networks (i.e., Citeseer, Cora, and PubMed) [16] and one large social network (Reddit). The properties of these datasets are summarized in Appendix A.3. We compare RIM with the following baselines: (1) Random: Randomly select the nodes to query; (2) AGE [3]: Combine different query strategies linearly with time-sensitive parameters for GCN; (3)ANRMAB [8]: Adopt a multi-armed bandit mechanism for adaptive decision making to select nodes for GCNs; (4)GPA [13]: Jointly train on several source graphs and learn a transferable active learning policy which can directly generalize to unlabeled target graphs; (5)LP-MRE [20]: Select a node that can reduce the entropy most in LP; (6)LP-ME [20]: Select a node with maximum uncertainty score in LP.
None of these baselines has considered the label noise in AL. For a fair comparison, we have tried several anti-noise mechanisms [12, 24, 32] to fight against noise in GCN and LP, and finally choose PTA [6] to our baselines since it can get the best performance in most datasets. We name AGE enhanced with PTA as AGE+, so do other baselines. Similar to RIM, PTA assigns each labeled node a dynamic label reliability score for model training. PTA computes the label reliability based on the graph proximity and the similarity of the predicted label, while RIM does not consider the model prediction because it may be unreliable in the AL setting that only a few labeled nodes can be used in the initial node selection phases. Unlike PTA, RIM considers the labeling accuracy and combines it with the graph proximity in its influence quality estimation.
Implementations. We use OpenBox [19] for hyper-parameter tuning or follow the original papers to find the optimal hyperparameters for each method. To eliminate randomness, we repeat each method ten times and report the mean test accuracy. The implementation details are shown in Appendix A.4, and our code is available in the supplementary material.

heading: 4.2 Experimental Results
text: Performance on GCN. To answer Q1, We choose the labeling size as 20 nodes per class labeling error rate ranging from 0 to 0.5, and then we report the corresponding test accuracy of GCN in Figure 2. Compared to other baselines, RIM consistently outperforms the baselines as the labeling error rate grows. Moreover, even with the anti-noise method, i.e., PTA, the baselines still have a noticeable performance gap from RIM. To demonstrate the improvement of RIM in the noisy situation, we also provide the test accuracy with a labeling error rate set as 0.3. Table 1 shows that GPA+, AGE+, and ANRMAB+ outperform Random in most datasets, as they are specially designed for GCNs. However, RIM further boosts the performance by a significant margin. RIM improves the test accuracy of the best baseline, i.e., GPA+, by 3.5-5.1% on the three citation networks and 2.2% on the Reddit dataset.
Performance on LP. Following the same settings in GCN, the result of LP is shown in Figure 3. Even if combined with the anti-noise method PTA, RIM consistently outperforms LP-MRE and
Table 1: The test accuracy (%) on different datasets when labeling accuracy is 0.7.
Table 2: The influence of different components in RIM.
LP-ME by a large margin as the labeling error rate grows. To demonstrate the improvement of RIM with the existence of noise, we also provide the test accuracy with labeling accuracy set as 0.7. Table 1 shows that both LP-ME+ and LP-MRE+ outperform Random, but RIM further boosts the performance by a significant margin. Especially, RIM improves test accuracy of the best baseline LP-MRE+ by 3.3-7.0% on the three citation networks and 3.6% on Reddit.
Ablation Study. RIM combines both influence quality and influence quantity. To answer Q2 and verify the necessity of each component, we evaluate RIM on GCN while disabling one component at a time when the labeling accuracy is 0.7. We evaluate RIM: (i) without the label reliability score served as the loss weight (called “No Reliable Training (RT)”); (ii) without the label reliability when selecting the node (called “No Reliable Selection (RS)”);(iii) without both reliable component(called “No Reliable Training and Selection (RTS)”). Table 2 displays the results of these three settings.
The influence quality in RIM contributes to both the reliable node selection and reliable training. First, the test accuracy will decrease in all three datasets if reliable training is ignored. For example, the performance gap is as large as 3.6% if reliable training is unused on Citeseer. Adopting reliable training can avoid the bad influence from the nodes with low label reliability. Besides, reliable node selection has a significant impact on model performance on all datasets, and it is more important than reliable training since removing the former will lead to a more substantial performance gap. For example, the gap on PubMed is 2.7%, which is higher than the other gap (1.8%). The more reliable the label is, the more reliable activated nodes we can use to train a GCN.
With the removal of reliable training and selection, the objective of RIM is to maximize the influence quantity (the total number of activated nodes). As shown in Table 1 and 2, RIM still exceeds the AGE+ method by a margin of 0.9%, 0.8%, and 0.6% on Cora, Citeseer, and PubMed, respectively, which verifies the effectiveness of maximizing the influence quantity.
Influence of labeling budget We study the performance of different AL methods under different labeling budgets in order to answer Q1. More concretely, the budget size ranges from 2k to 20k with labeling error rates being 0 and 0.3, respectively, and report the test accuracy of GCN. Figure 4 shows
that with the budget size growing, RIM constantly outperforms other baselines, especially when there is more label noise, which shows the robustness of RIM.
Efficiency Comparison. Another key advantage of RIM is its high efficiency in node selection. To answer Q3, we report the end-to-end runtime of each method in Figure 5. In real-world AL settings, the end-to-end runtime of model-based methods (i.e., GPA, AGE, and ANRMAB) includes both labeling time and model training time. However, the labeling time is excluded from our measurement since the quality and proficiency of oracles dramatically influence it.
The left part in Figure 5 shows that RIM obtains a speedup of 22×, 30×, and 172× over ANRMAB on Cora, PubMed, and Reddit and a speedup of 4670×, 950×, and 177× over GPA on Cora, PubMed, and Reddit, respectively on GPUs. It is worth mentioning that, since GPA is a transfer learning method, the training time does not depend on the scale of the target dataset, and thus the runtime of GPA is very close on the three datasets (its details can be found in Appendix A.4). As RIM is model-free and does not rely on GPU, we also evaluate them on CPU environment, and the result is shown in the right part of Figure 5. The speedup grows on all these three datasets. For example, the speedup increases from 4670x to 18652x when the GPU device is unavailable on the Cora dataset.
Interpretability. To answer Q4, we evaluate the distribution of the correctly activated nodes, incorrectly activated nodes, and inactivated nodes for AGE, RIM (No RS), and RIM when labeling accuracy is 0.7 for Cora in GCN. The result in Figure 6 shows that AGE has the fewest activated nodes, and nearly half of them are incorrectly activated. RIM (No RS) has the most activated nodes but also gets many nodes activated by incorrectly labeled nodes. Compared to these two methods, RIM has enough activated nodes, and most of them are activated by correctly labeled nodes (i.e., restrain the noisy propagation), which is why RIM performs better in node classification.

heading: 5 Conclusion
text: Both GCN and LP are representative graph models which rely on feature/label propagation. Efficient and effective data selection for the model training is demanding due to its inherent complexity, especially in the real world when the oracle provides noisy labels. In this paper, we propose RIM, a novel AL method that connects node selection with social influence maximization. RIM represents a critical step in this direction by showing the feasibility and the potential of such a connection. To accomplish this, we firstly introduce the concept of feature/label influence and then define their influence quality/quantity. To deal with the oracle noise, we propose a novel criterion to measure the influence quality based on the graph isomorphism. Finally, we connect the influence quality with the influence quantity and propose a new objective that maximizes the reliable influence quantity.
Empirical studies on real-world graphs show that RIM outperforms competitive baselines by a large margin in terms of both model performance and efficiency. We are extending RIM to heterogeneous graphs for future work as the current measurement of influence quality cannot be directly used.
Broader Impact
Specifically, RIM can be employed in graph-related areas such as prediction on citation networks, social networks, chemical compounds, transaction graphs, road networks, etc. Each of the usage may bring a broad range of societal benefits. For example, predicting the malicious accounts on transaction networks can help identify criminal behaviors such as stealing money and money laundry. Prediction on road networks can help to avoid traffic overload and saving people’s time. RIM has significant technical-economic and social benefits because it can significantly shorten the labor time and labor intensity of oracles. However, as RIM requires oracles to label each selected node, it also faces the risk of information leakage. In this regard, we encourage researchers to understand the privacy concerns of RIM and investigate how to mitigate possible information leakage.
Acknowledgments and Disclosure of Funding
This work is supported by NSFC (No. 61832001, 61972004), Apple Scholars in AI/ML PhD fellowship, Beijing Academy of Artificial Intelligence (BAAI), PKU-Baidu Fund 2019BD006, and PKU-Tencent Joint Research Lab. Zhi Yang and Bin Cui are the corresponding authors.

Review summaries:
The authors propose a novel graph-based active learning approach, specifically with label propagation and graph convolutional networks in mind. They, in particular, tackle the problem of label noise in graph-based active learning, which is indeed very important and not well studied. They provide a conceptual and practical solution to this problem. For that, they introduce the notion of reliable influence maximization based on influence maximization in social networks, where they take not only the quantity of the influence into account but also a novel way of measuring the influence quality. On benchmark datasets, they achieve impressive performance in terms of predictive accuracy, runtime and label noise robustness compared to some baselines.

This proposes a novel graph-based active learning framework by reliable social influence maximization. The proposed model aims to select a subset of nodes to be labeled, so as to maximize the number of nodes influenced. Whether a node is influenced is determined by both the influence quantity and quality (assuming label noise). A greedy algorithm is adopted for optimization, whose approximation precision is guaranteed theoretically. SeveraleExperiments are conducted to validate the effectiveness and efficiency of RIM. 

This paper proposes the AL method which combines node selection and message passing of the graph models for minimizing labeling cost. The first technical contribution is to quantify the influence of labeling in GCN/LP and relate AL to the problem of finding seed nodes for maximizing the influence. In addition, this paper shows how to maximize the spread of influence by considering the noise and reliability of labels.

This paper studies graph active learning in the presence of labeling noise, which is an under-explored area with real-world impact. The key idea of this paper is to define Reliable-Influence-Quantity-Score Q as the product of label reliability and label influence. The active learning objective is then to maximize the number of activated node, whose Q score exceed a certain threshold. The authors proposed a greedy algorithm for selecting the nodes, and showed the greedy algorithm is close to optimal. Empirical results on real-world dataset shows this algorithm outperforms the baselines by large margins.