RIM: Reliable Influence-based Active Learning on Graphs
Authors: Wentao Zhang
Yexin Wang
Zhenbang You
Meng Cao
Ping Huang
Jiulong Shan
Zhi Yang
Bin CUI
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Active Learning
Graph
Label Noise
Social Influence Maximization

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. 

RIM: Reliable Influence-based Active Learning on Graphs
Wentao Zhang 1.2 Yexin Wang', Zhenbang You', Meng Cao², Ping Huang? Jiulong Shan", Zhi Yang".; ,3, Bin Cui School of CS, Peking University AAppee
National Engineering Laboratory for Big Data Analysis and Applications
'Institute of Computational Social Science, Peking University (Qingdao), China wentao.zhang, yexinwang, zhenbangyou, flyang.cs, yangzhi, bin.cui | @ pku.edu.cn 2 mmengcao, Banang_ping jlshan) @apple.com
Abstract
Message passing is the core of most graph models such as Graph Convolutional Network (GCN) and Label Propagation (LP), which usually require large number 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 of few and unreliable labels that be obtained cheaply. We make two contributions towards that end. First, we open up a perspective by drawing 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 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 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.
Introduction
Graphs are ubiquitous in the real world, such as social, academic, recommendation, and biological networks [38] 30 31 10 (2). 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 node labels are propagated and aggregated along edges in the graph.
Propagation (LP) 25
The message passing typically requires large amount of labeled data to achieve satisfactory per- formance. However, labeling data, be by specialists crowd-sourcing, often consumes too much time and money. The process is also tedious and error-prone. As result, it is desirable to achieve good classification results with labeled data that is both few and unreliable. Active Learning (AL) is 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 g 20 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 (NcurIPS 2021).

---

Cleas Noay
Closdinguee Neto&Dgaer 2
Tex accumccy1))
Test aocumoy())
-0
Chundlapee
10
10
Receptive field
Btration
(a) Influence of GCN
(b) Influence of LP
Figure 1: The influence between feature/label propagation and test accuracy with clean/noisy label.
The first contribution is that quantify node influence by how much the initial feature/label of label node v influences the output feature/label of node u 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 [V] 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 ! 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 [[a] and Figure [(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 '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 fundamentally new AL selection criterion for GCN and LP-reliable inffuence maximization (RIM)-by considering both quantity and quality of influence simultaneouslyy Under 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 greedy approximation algorithm for maximizing reliable influence to reach an approximation ratio of 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 is enhanced with the anti-noise mechanism PTA 66. Furthermore, in terms of efficiency, RIM achieves up to 4670x and 18652x 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 novel perspective for efficient and effective AL for GCN and LP by enforcing the feature/label influence with connection to social influence maximization I8 4; 2) To the best of our knowledge, we are the first to consider the influence quality in graph-based AL, and we propose 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 IP demonstrates that RIM significantly outperforms the compared baselines in performance and efficiency.
2 Preliminary
2.1 Active Learning
Problem Formulation. Let be the number of label classes and the ground-truth label for node us be a one-hot vector y; R Suppose that the entire node set V is partitioned into training set Vtrain

---

(including both the labeled set 1/2 and unlabeled set Vu), validation set Veal and test set Viest- Given a graph 9 (V,E) with V = N nodes and |8] M edges, feature matrix X { T2... NN in which æ; 1dd labeling budget B, and loss function L, the goal an AL algorithm to select subset of nodes Vi C Verain to label from noisy oracle with the labeling accuracy a, so that it can produce model f with the lowest loss on the test set:
arg min EeyeVient (e,, P(rlf))) V= =8
where P(ü:lf) is the predictive label distribution of node 04. To measure the influence of feature or label propagation, focus on f being GCN 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 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]
2.2
Graph Models
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:
( D AY y
(k+1),
Y (++1) (0)
where (0) (y1, y 3r is the initial label matrix consisting of one-hot label indicator vectors, y*()) and ( denote the soft label matrix of the labeled nodes set V and unlabeled nodes set Vu in iteration & respectively. According to [39]. we iteratively set the nodes in Vi back to their initial label Y since their labels are correct and should not be influenced by the unlabeled nodes.
GCN. Each node in GCN iteratively propagates its feature influence 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++)) = O (D-
where (4) and (k++) are the embeddings of layer & and & + respectively. Specifically, X (and X (()) is the original node feature. A = + nodes, where A is the adjacent matrix of the graph and I is the identity matrix. D is the diagonal node degree matrix used normalize A, ((k) is layer-specific trainable weight matrix and 6(-) is the activation function.
+ IN is used to aggregate feature vectors of adjacent
2.3 Influence Maximization
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 = EV,E), the formulation is as follows:
(o()) s.t. S SCV. 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 (SS) is NP-hard. However, if (SS) is nondecreasing and submodular with respect to S, a greedy algorithm can provide an approximation guarantee of (1 ! 23 RIM is the first to connect social influence maximization with graph-basee based AL under noisy oracle by defining reliable influence.

---

3 Reliable Influence Maximization
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 batch of nodes that can maximize the number of activated nodes, and then updates the influence quality for the next iteration. The above process repeated until the labeling budget B runs out. We will introduce each component of RIM in detail below.
3.1 Influence Propagation
We measure the feature/label influence of a node vú on U/ by how much change in the input feature/la- bel of o affects the aggregated feature/label of U after & iterations propagation [26 33
Definition 3.1 (Feature Influence). The feature influence score of node v; on node v after k-step
propagation is the Ll-norm of the expected Jacobian matrix [ vs k)) = Blx (8) /8x (0)
The normalized influence score is defined as
I5(0,, k)
Ty(U,, vi, Emeey (V,, kw:k)
(5)
Definition 3.2 (Label Influence). The label influence score of node vs on node vj after k-step propagation is the gradient of yj
(k) with respect y::
I( U2 k) = | (K) /0yill,-
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 v; to ey. which is the probability that a random walk (or variants) starting at u ends at U; after taking steps [33. Thus, we could take them as the probability that propagates its feature/label to ey via random walks from the influence propagation perspective.
3.2 Influence Quality Estimation
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 's quality based on the features/labels of previously selected nodes.
Specifically, after l iterations of propagation, we calculate the node similarity s of node vi and ey in LP by measuring the cosine similarity in (k) according to E.q. (2). Like SGC 29
remove the activate function 8(-) and the trainable weight (kk) and get the new feature matrix as: (k+1) D (A) For better efficiency in measuring the node similarity, we replace ((k) in E.q. B with the simplified (*) since its calculation is model-free. Similar to LP, we get the node similarity in GCN by measuring the cosine similarity in X (k), Larger means u; and vj are more similar after i 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 And assume that the label is wrong with the probability of 1 a, and the wrong label is picked uniformly at random from the remaining e classes. Given the labeled node v, Vi and unlabeled node Uy V.., supposing the oracle labels Vj as J and Ú; y, (the ground truth label Us the same notation also applies to Uz), the reliability of node y according to Ug is
Tog-byy as +
where a is the labeling accuracy, and measures the similarity between ia and by.

---

Proof of Theorem 3.1 in Appendix A.1. Intuitively, Theorem 3.1 shows that the label of node v is more reliable if (h) oracle is more proficient and thus has higher labeling accuracy a. (2) The labeled node ti is more similar to Vi and thus leads to larger 8.
Definition 3.3 (Influence Quality). The influence quality of uy is recursively defined as
E
Tos
Te,Tn h051
where Tor-vu is the label reliability of node uj with respect to node vs, and fe. " 2ngeV You is the normalized label reliability score of node v.-
Twy
For each unlabeled node vj. we firstly find all labeled nodes which have the same label with y, and then get the final influence quality with weighted voting [1]. The source node is should contribute more in measuring its influence another node by if its label is reliable, i.e., with higher Pey.
3.3 Reliable Influence
Different from the original social influence method which only considers the influence magnitude [14] 34J. measure the influence quantity and get the reliable influence quantity by introducing the influence quality since it common to have noisy oracles in the labeling process Active Learning.
Definition 3.4 (Reliable Influence Quantity Score). Given the influence quality Two the reliable influence quantity score of node on node Vi after k-step feature/label propagation is
(Uú, U1 k) T (U3, Us. k),
where [[yj, Uz; k) is Ty(Ug, Us k) for GCN and Ti(U,, Vs. k) for LP.
The reliable influence quantity score QU vt, k) is determined by: (1) The influence quality of the labeled influence source node v. (2) The fcature/label influence score of i; on ej after k-step propagation. From the perspective of random walk, is harder to get path from v; to By with larger steps k and the influence score will gradually decay along with the propagation steps. As a result, node vy can get highly reliable influence quality score from the labeled node v; they are close neighbors and has high influence quality.
In 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 v can be activated if and only the maximum influence magnitude satisfies:
Qu k),
(10)
where Q(vy, Vi, k) max (Uy; vi, k) is the maximum influence of V the node üj. and the threshold 0 is a parameter which should be specially tuned for a given dataset.
Definition 3.5 (Activated Nodes). Given set of labeled seeds Vi, the activated node set a (Vi) is subset of nodes in V that can be activated by Vi:
o(V)
U
{n).
(11)
VEV (EV
The threshold means we consider an unlabeled node is influenced as long as there a k-step path from any labeled node, which is equal to measuring whether this unlabeled node can be involved the entire training process of GCN 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 relatively large, we could choose a positive threshold O, which enables the selection process to pay more attention to those weakly influenced nodes.
3.4 Node Selection and Model Training
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
5

---

Algorithm 1: Batch Node Selection.
Input:
Initial labeled set Vo. query batch size b, and labeling accuracy a. Output: Labeled set V/
Vi
Vo:
2 for f = 1,,...,,b do
Select the most valuable node 8* arg ma Verain
F(V U {n}):
Set the influence quality of v" to the labeling accuracy o;;
Update the labeled set 1/2 = Vi U {v*}:
Update the influence quality of nodes in Vi \ Vo according to E.q.
return
of expansion or, equivalentl, growth of the influence can change dramatically given different sets of label nodes. This observation motivates 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 F()) lo(V)),, s.t. Vi V. M = B.
(12)
Vi
By considering both the influence quality and quantity, RIM aims to find subset of B to label that the number of activated nodes can be maximized.
Reliable Node Selection. Without losing generality, we consider batch setting where b nodes are selected in each iteration. For the first batch, when the initial labeled set Vo- = 0, we ignore the influence quality term rı; in E.q. 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 a during the node selection process and then simuitancously update these values according to E.q. E.q. aater the node selection process of this batch. For the node selection after the first batch, Algorithm provides a sketch our greedy selection method for the graph models, including both GCN and LP. Given the initial labeled set Vo. query batch size b, and labeling accuracy a, we first select the node v" generating the maximum marginal gain (line 3), set its influence quality the labeling accuracy (line 4), and then update the labeled set Vi (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 E.q. 8 (line 6).
Theorem 3.2. The greedily selected batch node set is within factor of (1 - 2)) of the optimal set for the objective of reliable influence maximization.
Proof of Theorem 3.2 is 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 practice since the oracle does not need to wait for the end of model training 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 Vi 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 Enyer, Te; Vi log D.. where Tv, the influence quality of node Us. For each labeled node in LP, we just change its label yı to ro
3.5 Comparison with Prior Works
regarding label noise mainly focus on two phases: noise detection and noise handling. Both the data-drives 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
Existing AL works 35
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 substantial. To sum up, current AI. 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.
4 Experiments
We now verify the effectiveness of RIM 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 basclines, what should be the reason?
4.1 Experiment Setup
Datasets and Baselines, We use node classification tasks to evaluate RIM in both inductive and transductive settings [ three citation networks (i.e., Citeseer, Cora, and PubMed) [[6] 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 B]: Combine different query strategies linearly with time-sensitive parameters for GCN; (3)ANRMB 88 Adopt multi-arme armeed bandit mechanism for adaptive decision making to
select nodes for GCNs; GP) [3: Jointly train on several source graphs and learn a transferable active learning policy which can directly generalize unlabeled target graphs; (5)PP-MRE (20) Select a node that can reduce the entropy most in LP; (6)LP-ME [0]: Select a node with maximum uncertainty score in LP.
None of these baselines has considered the label noise in AL. For fair comparison, have tried several anti-noise mechanisms [2] 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 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 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 OpenBox [19 for hyper-parameter tuning 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.
4.2 Experimental Results
Performance on GCN. To answer Q1, We choose the labeling size as 20 nodes per class labeling error rate ranging from 0 0.5, and then we report the corresponding test accuracy of GCN in Figure 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 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 [ 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 I... Following the same settings in GCN, the result of I.P is shown in Figure 3 Even if combined with the anti-noise method PTA, RIM consistently outperforms LP-MRE and
7

---

Table 1: The test accuracy (%) on different
Table 2: The influence of different compo- nents in RIM.
datasets when labeling accuracy is 0.7.
Model
Mothods
Cora
Ciesseer
PubMed
Reddit
Method
Cora
A
Clteseer
PuhMed
Random
65.6
56.3
63.3
75.2
AGE+
RT
25.1
-28
63.9
-3.6
71.4
-18
GCN
ANRMAB+
GPA+
72.8
72.4
63.8
63.4
68.9
69.7
71.9
77.2
No RTS
No RS
73.4
74.8
-3.1
43
61.9
63.4
4.1
5.6
68.9
70.5
-27
4.3
RIM
77.9
67.5
73.2
80.1
RIM
77.9
67.5
73.2
Rundom
51.7
31,4
50.4
51.3
LP
LP-MRE+
1 +
58.5
53.4
RIM
62.4
46.7
65.5
58.5
Cura
Ciresees
PubMed
Toa scseacy
Toa accuaaett
Thet accerngsNN)
RIM
CLPA
AGE
60
ANDRAL
BAUNDOO
ACE:
ANTOAB
Lahelling uncr mio
Labilling crror mit
sahelling cmdr 1912
Figure 2: The test accuracy with different labeling error rate of labeled nodes for GCN.
Cura
Citeseer
PM
You SocUINo
30
Labelling crcor mit
Lahiling croor mi
shhlling cmor 1912
Figure 3: The test accuracy with different labeling error rate of labeled nodes for LP.
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. T that both LP-ME+ and LP-MRE+ outperform Random, but RIM further boosts the performance 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, evaluate RIM GCN while disabling one component at a time when the labeling accuracy 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)")((ii) without both reliable component(called "No Reliable Training and Selection (RTS)"). Table 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 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 model performance than reliable training since removing the former will lead to a more substantial performance gap. For example, the gap 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.
all datasets, and it is more important
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 I 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 2 to 20k with labeling error rates being and 0.3, respectively, and report the test accuracy of GCN, Figure 4 shows

---

Labelling mite 0.3
Labelling
GPU
accumoet))
70
199
3oureee 8
The mibbrr 3t Rode
11 The mimber of laboled modes
Cur PihMred Reoemt
CoFn PIDMed Redam
Figure 4: The test accuracy of each method along with different labeling budget when labeling error rate is 0.3 and O, respectively.
Figure 5: The end-to-end runtime (at log scale) on different datasets. The speedup on each bar is relative to GPA.
RIMINO
102
30
Incoreecll aetwoned Inaziivatall
100
75
30
30
75
30
30
Figure 6: The node distribution of different methods on the Cora dataset. Note that a node is correctly activated only if it is firstly activated by a correctly labelled node.
that with the budget size growing, RIM constantly outperforms other baselines, especially when there 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 each method in Figure 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 speedup of 2, 30x, and 172x over ANRMAB on Cora, PubMed, and Reddit and a speedup of 4670x, 950x, and 177x over GPA on Cora, PubMed, and Reddit, respectively on GPUs. It is worth mentioning that, since GPA is 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 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 shows that AGE has the fewest activated nodes, and nearly half of them 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 activated by correctly labeled nodes (i.e., restrain the noisy propagation), which is why RIM performs better in node classification.
5 Conclusion
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, novel AL method that connects node selection with social influence maximization. RIM represents 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 new objective that maximizes the reliable influence quantity.

---

Empirical studies on real-world graphs show that RIM outperforms competitive baselines by 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 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 avoid traffic overload and saving people's time. RIM has significant technical-cconomic 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, 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/MI 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.
References
[T] C. C. Aggarwal, X. Kong, Q. Gu, J. Han, and S. Y. Philip. Active learning: A survey, In Data Classification: Algorithms and Applications, pages 571-605. CRC Press, 2014.
[2] M.-R. Bouguelia, S. Nowaczyk, K. Santosh, and A. Verikas. Agreeing to disagree: active learning with noisy labels without crowdsourcing. International Journal of Machine Learning and Cyhernetics, 307):1307-1319, 2018
[3] H. Cai, W. Zheng, and C.-C. Chang, Active learning for graph embedding. arXiv preprint 2017.
[4] Y. Chen and A. Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In Proceedings the 30th International Conference Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pages 160-168, 2013.
[5] G. Dasarathy, R. D. Nowak, and X. Zhu. S2: an efficient graph based active learning algorithm with application to nonparametric classification. In Proceedings The 28th Conference Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 522, 2015.
[6] H. Dong, J. Chen, Feng, X. He, S. Bi, 7. Ding, and P. Cui. On the equivalence of decoupled graph convolution network and label propagation. In WWW '21: The Web Conference 2021, Virtual Event Ljubljana, Slovenia, April 19-23, 2021, pages 3651-3662, 2021.
[7] Du and X. Ling. Active learning with human- noisy oracle. In 2010 IEEE International Conference on Data Mining, pages 802. IEEE, 2010.
[8] L. Gao, H. Yang, C. Zhou, J. Wu, S. Pan, and Y. Hu. Active discriminative network representa- tion learning. In IJCAI International Joint Conference on Artificial Intelligence, 2018.
[9] D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res., 42:427-488 2011.
[10] Q. Guo, X. Qiu, X. Xue, and Z. Zhang. Syntax-guided text generation via graph neural network. Sci. China Inf. Sci., 64(5). 2021.
10

---

[11] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017.
[12] B. Han, Q Yao, T. Liu, G. Niu, I. W. Tsang, J. T. Kwok, and M. Sugiyama. A survey of label-noise representation learning: Past, present and future. arXiv preprini arXiv:201 1.04406, 2020.
[13] S. Hu, Z. Xiong, M. Qu X. Yuan. M. Côté, Z. Liu, and J. Tang. Graph policy network for transferable active learning on graphs. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[14] K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In 2012 IEEE 12th International Conference on Data Mining, pages 918-923. IEEE, 2012.
[15] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[16] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[17] L. I. Kuncheva and J. R. Diez. A weighted voting framework for classifiers ensembles. Knowl. Inf. Syst.. 38(2):559-275 2014.
[18] Y. Li, J. Fan, Y. Wang, and K.-L. Tan. Influence maximization on social graphs: A survey. IEEE 2018.
Transactions on Knowledge and Data Engineering, 30(
[19] Y. Li, Shen, W. Zhang, Y. Chen, H. Jiang, M. Liu, J. Jiang. J. Gao, W. Wu, Z. Yang, C. Zhang, and B. Cui. Openbox: A generalized black-box optimization service. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 3209-320 2019,219222220000 2021.
[20] Long, J. Yin, W. Zhao, and E. Zhu. Graph-based based active learning based on label propagation. In International Conference on Modeling Decisions for Artificial Intelligence, pages 199-190. Springer, 2008
[21] Y. Ma, R. Garnett, and J. G. Schneider. E-optimality for active learning on gaussian random fields. In Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2751-2759, 2013.
[22] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology. (7())4455444, 2001.
[23] G. Nemhauser, A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I. Math. Program., 14(1):265-24,, 1978.
[24] S. Paul, S. Chandrasekaran, B. Manjunath, and A. K. Roy-Chowdhury, Exploiting context for robustness to label noise in active learning. arxiv preprint arXhv:2010.09066 2020.
[25] F. Wang and C. Zhang. Label propagation through linear neighborhoods. IEEE Transactions on Knowledge and Data Engineering. 20(1):55 67, 2007.
[26] H. Wang and J. Leskovec. Unifying graph convolutional neural networks and label propagation. arXiv preprint arXiv:2002.06755, 2020.
[27] X. Wang, Liu, S. Cao, I. Jing, and J. Yu. Important sampling based active learning for imbalance classification. Sci. China Inf. Sci, 63(8):1-14, 2020.
11

---

[28] Y. Wang. Y. Yuan, Y. Ma, and G. Wang. Time- deneedeenddn graphs: Definitions, applications, and algorithms. Data Sci. Eng., 4(4) -66, 2019.
[29] Wu, A. H. S. Jr., T. Zhang, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 6861-6871, 2019. 2019.
[30] S. Wu, F. Sun, W. Zhang, and B. Cui. Graph neural networks in recommender systems: survey. arXiv preprint arXiv: 20122011000 1.02260, 2020.
[3]] S. Wu, Y. Zhang, C. Gao, K. Bian, and B. Cui. Garg: Anonymous recommendation of point- of-interest in mobile networks by graph convolution network. Data Science and Engineering, 5(4):433-447, 2020.
[32] B. Xu, X. Zhao, and Q. Kong. Using active learning to improve distantly supervised entity typing in multi-source knowledge bases. In CCF International Conference on Natural Language Processing and Chinese Computing, pages 219 191..3. Springer, 2020.
[33] K. Xu, C. Li, Y. Tian, Sonobe, K. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, JCML 2018, Stockholmssässsan, Stockholm, Sweden, July 10-15, 2018, pages 5449-5458, 2018.
[34] Y. Yang, E. Chen, Q. Liu, B. Xiang, T. Xu, and S. A. Shad. On approximation of real-world influence spread. In Joint European conference on machine learning and knowledge discovery in databases, pages 548-564. Springer, 2012.
[35] C. Zhang and K. Chaudhuri. Active learning from weak and strong labelers. arXiv preprint arXiv:1510.0284 2015.
[36] W. Zhang, Y. Shen, Y. Li, L. Chen, Z. Yang. and B. Cui, ALG: fast and accurate active learning framework for graph convolutional networks, In SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021, pages 2366-2374, 2021.
[37] W. Zhang, Z. Yang, Y. Wang, Y. Shen, Y. Li, L. Wang, and B. Cui. Grain: Improving data efficiency of graph neural networks via diversified influence maximization. Proc. VLDB Endow. 14(11):2473-2482 2021.
[38] Z. Zhang, P. Cui, and W. Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 2020.
[39] X. Zhu, superviuer learning with graphs. Carnegic Mellon University, 2005.
[40] X. Zhu and A. B. Goldberg. Introduction to semi-supervised learning. Synthesis lectures on artificial intelligence and machine learning. 3(1):1-130. 2009.
[41] X. Zhu, J. Lafferty, and Ghahramani. Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. In ICML 2003 workshop on the continuum from labeled to unlabeled data in machine learning and data mining, volume 3, 2003.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have carefully read the guidelines.
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix A.I.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL.?? [Yes] We provide it
in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We have a detailed implementation instruction.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See the implementation part in Section 4.1.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the implementation details in the Appendix A.4.
4. If you using existing assets (c.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See section 4.1.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] We have include them in both the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] We use the widely used and public data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] Our experiment just simulates the human labeling process.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "jEsLt9BDry_", "reviewer": "Reviewer_nYPR", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The problem consider in this paper is of practical impact. The motivation of the paper is clearly presented. The paper seem to be well written overall, but part of the problem setup is not 100% clear (see next). The method proposed in this paper is both inspiring and gives good empirical gains. I think this paper should be accepted after some moderated concerns being addressed. I will be more confident in my judgement after my questions (see next) are addressed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitation:\n1. The setup of the paper is not 100% clear to me. In particular, there are three type of labels: 1) the ground truth, 2) labels given by an oracle, 3) the predicted labels given by the algorithm. In the problem statement in section 2.1, it seems that the ground truth labels are not available, and we only have access to the labeling oracle. However, in equation 8, the ground truth labels are used for computation. From the content, it seems that there are at least a small set of nodes where the ground truth label are given, I hope the authors can further clarify the setup in their writing.\n2. In appendix line 14, s is defined as the probability that the two node i,j have the same ground truth label. In practice, s is computed as the cosine similarity between the two node features / or label vectors. This seems to be a huge leap since: 1) cosine similarity has range [-1,1] while probability has range [0,1]; 2) even if those two have the same range, simply using cosine similar as probability without further justification is still not sound enough.\n3. It is not clear to me how equation 6 in appendix is derived. In particular, where does k come from?\n\nSocietal Impact:\nThere is no significant negative societal impact associated with this research.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "KRnTE5jO7hG", "reviewer": "Reviewer_RKEJ", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "- This paper is well structured, clearly written and easy-to-follow. The idea of the method seems to me to be highly convincing and reasonable. In particular, the method that takes into account the noise of the labels seems to have a high practical value.\n- It has been shown to be effective in terms of accuracy and computational complexity for node classification tasks in cases where there is noise in the labels. It has also been validated using several real data sets, and comparison results with many baselines are provided.\n- The authors used PTA as the anti-noise mechanisms. What other algorithms have you tried, and why did you choose just PTA? It is better to show that the proposed method is superior without relying on the selection of anti-noise mechanisms.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the applicability of the proposed technology is not low, but there is little description of its social value and impact. It would be better to add descriptions of specific applications that would inspire readers (users of the technology).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "KL-NNCBRZXZ", "reviewer": "Reviewer_e5Eo", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes an interesting active learning method on graph models from a social influence maximization perspective. It exploits the message passing property of graph models, quantifying the influence quantity of labeled nodes to unlabeled nodes, so as to incorporate active learning into the message passing process. In addition, label noise is considered, and label reliability is achieved by estimating influence quality. The overall method is theoretically sound, theorem 3.1 obtains label reliability, and theorem 3.2 guarantees the feasibility of Algorithm 1. \n\nIn general, this paper is well-organized, clearly written, and easy to follow. The experiments are relatively sufficient and demonstrate the effectiveness of RIM. Ablation study supports the necessity of influence quality. The interpretability illustration is impressive. However, I have the following questions and concerns: \n(1) The experiments do not demonstrate the advantage of influence quantity; the claim/motivation of “A better AL method should unify node selection and message passing” is not well supported. Table 2 shows “No RTS” does not always outperform the baselines, e.g., GPA+ on Citeseer and PubMed. It will be nice to conduct an additional verification by removing the effects from label noise, e.g., to compare “No RTS” with AL baselines(no anti-noise mechanism), such as GPA, in a setting without label noise. \n\n(2) What’s the relationship between r_{v_j} in Equation 8 and Q(v_j,v_i,k) in Equation 9? It seems that both the two capture the reliability of v_j. But Q(v_j,v_i,k) is used to decide whether v_j is activated, and r_{v_j} is used during model training. Why? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "GiSyrOw2wRl", "reviewer": "Reviewer_qTkm", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Even though the general idea has much potential, there are serious issues with the writing (e.g., notation, language, clarity, references),  missing references, and many missing details in the theory and experimental section.\n\n*** If the authors properly address the following issues, I am more than willing to change my rating. ***\n\nThe theoretical derivations seem correct but miss many details and do not state all assumptions. Most importantly, the proof of the key theoretical contribution of this paper - that the (reliable influence maximization) RIM objective is submodular - is discussed very shortly in the appendix. A rigorous proof is necessary here.\n\nAdditionally, in the proof of Theorem 1, the last step in Eq. (6) is only possible by assuming that the label noise is happening in a particular way: with probability $1-\\alpha$, the label is wrong (this is what the authors state) and that the wrong label is picked uniformly at random from the remaining $k-1$ classes (this is not explicitly assumed or stated in the paper). Also, it is not completely clear whether the ground-truth labels (e.g., $y_i$) are fixed (deterministic) or rather random variables. In the main text, it seems like they are fixed (and only the $\\tilde{y}$ are random), but in the proof, they use the $y_i$ as random variables (e.g., state the probability $P(y_i = y_j)$). Clarification helps a lot here. It is also not the Bayes formula in line 11, but merely the definition of conditional probabilities.\n\nIt is also unclear how the authors actually use Theorem 1 because it assumes the true similarity/probability s to be known, while the authors use an estimate of the similarity given by LP (label propagation) or GCN (graph convolution networks) instead. I also would disagree, that the computation of RIM is \"model-free\" because it still relies on evaluating, e.g., LP some number of steps. Could the authors help disambiguate and clarify the issues here?\n\nIt is also not completely clear why there is an expectation in the definition of feature and label influence. In the paper [23], the expectation is only used in the feature influence and not in the label influence. The authors of [26] use the same definition without the expectation. I can only speculate that it is either the expectation over the randomly sampled features $X$ and/or labels $y$, or meant in a social influence maximization manner (with, e.g., probabilities that vertex v influences vertex w). How are these expectations computed?\n\nMore things are not clear and not well explained: The modification of the cross-entropy loss and the labels using the influence quality (\"reliable model training\") is not explained nor motivated well and might even bias in favour of the proposed method. The motivation with Figure 1 is not really clear (also: what exactly do you mean with \"receptive field\"). \n\nEmpirical evaluations:\nThe achieved results definitely are impressive, in particular, in noisy settings. The code seems to be reproducible and well documented.\nHowever, there are multiple issues.\n\n1. Even though the achieved mean accuracy of 10 runs is significantly higher than the baselines, error bars would make the plots more valuable. The authors claimed that they have error bars in the Checklist, which they do not; also not in the supplementary.\n\n2. The four used datasets (especially the three citation datasets) are generally known to be overused in the last years.\n    Other graphs should have been used instead or additionally.\n\n3. It is unclear why the authors selected these particular baselines. For example, they have chosen a (comparably unknown) variant of active LP [17], instead of the (first) classical active LP (and one of the most known graph active learning) approach [Zhu, 2003]. The other baselines are: AGE [3] (an unpublished preprint from 2017), [10] (2018) and a recent approach from last year. There exist many well-tested graph-based active learning approaches such as [Ma, 2013] and [Gu, 2012], including the baselines therein. In fact, [Ma, 2013] seem to achieve comparable accuracy on Cora and even better accuracy on Citeseer using LP without noise (comparing Figure 3 of [Ma, 2013] with the current paper's Figure 3). Can the authors explain their choice of methods?\n\n4. The authors say that they used grid-search to select hyperparameters. However, more details on how, for example, their activation threshold $\\theta$ was chosen are missing. Experiments on how $\\theta$ affects the results are not shown and would benefit the experimental evaluation.\n\n5. Looking at Figure 4: It is not mentioned on what dataset these plots were achieved. Why not present such plots for all datasets (e.g., in the supplementary)? Also, it looks like the proposed method has already a ~7% better test accuracy than all baselines after only (roughly) 5 queries, which seems to be too good to be true. \n\n6. Looking at Figure 5: Why did the author's exclude the baselines LP-ME and LP MRE here? In line 304, they say that Figure 5 contains the \"runtime of each method\". The reason to exclude the labeling time in these measurements is not clear to me (line 306/307). They also mention in line 196 that to increase the efficiency, they set the influence of each new vertex first to $\\alpha$. Plots showing how this affects the efficiency (but also the accuracy) are interesting.\n\n7. It seems like RIM is the only algorithm with direct access to the label accuracy $\\alpha$, while the baselines do not explicitly use this information. A discussion about this discrepancy is necessary.\n\n8. How do the approaches select the first vertex (or batch $V_0$) to query?\n\nMissing / not discussed important previous work:\n\n* In line 66/67 the authors claim that they are the first to consider label noise in graph-based active learning (AL). However, there are previous graph AL approaches that also include label noise. For example, [Dasarathy, 2015] explicitly models the label noise as a parameter and derives bounds based on it. Also, multiple approaches model graph-based AL in a probabilistic setting (e.g., Gaussian random fields) with probability distributions for each vertex to have a particular label, e.g, the original active LP [Zhu, 2003] and [Ma, 2013]. This also models label noise but just not with an explicit parameter $\\alpha$ as the authors of this submission did.\n\n* The use of submodularity in AL and connections between influence maximization and AL: The use of submodularity is quite common in AL, see, e.g., [Chen 2013], [Ma, 2013]. In fact, the whole subject of \"adaptive submodularity\" [Golovin 2013] deals with the connection between submodularity and AL (and also social influence maximization).\n\n(Easily fixable) notation issues:\n\n* $k$ is the number of classes (/labels) (e.g., line 74, proof of Theorem 1 and the Theorem itself), but also the number of iterations (e.g., eq. 2, 3. def 3.1, 3.2, 3.4, 3.5).\n\n* no difference between $s$ the estimated (by LP or GCN) similarity of two vertices and $s$ the probability that two vertices have the same ground truth label.\n\n* The \"global\" budget B and the batch size b should be related, but this is not discussed. In general, I think the additional abstraction of using a batch of size b instead of just querying B vertices iteratively, is unnecessary and does not contribute much. It instead makes the understanding of Algorithm 1 more difficult.\n\n* The authors sometimes call the influence function $F$ and sometimes $\\sigma$. This is especially troubling in Def. 1 (nondecreasing submodular) in the appendix, where they switch the notation in the middle of the equation. In eq. (12) \"RIM objective\" it is also unnecessary to write max $F(.) = |\\sigma(.)|$\n\n* Why is there an underline in line 205 and also in line 33 of the appendix.\n\n* Looking at the most left equation in Eq. 2, it seems like Y^k and Y^(k+1) is the full |V|*k vertex label matrix. In the other two equation however, the same matrix is assigned to Y_l and Y_u of different size.\n\nSome smaller language issues:\nLine 219 \"The former .. construct\" -> \"constructs\". In the input of Alg.1, the authors say \"labelling\" while on other occasions, they say \"labeling\" (e.g., line 202). Please, be consistent.\n\nSome issues in the references:\n\nWhy do the authors cite [13] and [14] the preprint and published versions of GCN? Reference [21] contains no authors and no title but only the editors and the conference; is the intention to cite the conference as a whole? Citation [15] seems to be wrong. The authors cite it under the keyword \"social influence maximization\" in line 66 (btw. I do not understand what \"[15]; 2)\" there means), but [15] is about a different topic. They might confuse it with [Chen 2013]. Sometimes the authors spell out the same conference name, e.g., [24] sometimes not, e.g., [26]. Please, be consistent.\n\nReferences:\n\n[Zhu, 2003]: Zhu, Xiaojin, John Lafferty, and Zoubin Ghahramani. \"Combining active learning and semi-supervised learning using gaussian fields and harmonic functions.\" ICML 2003 workshop on the continuum from labeled to unlabeled data in machine learning and data mining 2003.\n\n[Ma, 2013] Ma, Yifei, Roman Garnett, and Jeff G. Schneider. \"Σ-Optimality for Active Learning on Gaussian Random Fields.\" NIPS. 2013.\n\n[Gu, 2012] Gu, Quanquan, and Jiawei Han. \"Towards active learning on graphs: An error bound minimization approach.\" ICDM 2012.\n\n[Dasarathy, 2015] Dasarathy, G., Nowak, R., & Zhu, X. (2015, June). S2: An efficient graph based active learning algorithm with application to nonparametric classification. In Conference on Learning Theory\n\n[Chen 2013] Chen, Yuxin, and Andreas Krause. \"Near-optimal batch mode active learning and adaptive submodular optimization.\" ICML 2013.\n\n[Golovin 2013] Golovin, Daniel, and Andreas Krause. \"Adaptive submodularity: Theory and applications in active learning and stochastic optimization.\" Journal of Artificial Intelligence Research 42 (2011): 427-486.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss limitations of their work, but that their approach is not directly applicable to heterogeneous networks (line 334,335). \n\n In real-world applications, the labeling accuracy $\\alpha$ is usually unknown. The authors could add a discussion on what to do in such situations.\n\nThe authors motivate their approach in Eq. (1) with the minimization of the generalization risk. However, they later in the paper do not refer to it again. Is is possible to relate the author's RIM optimization to the actual goal of minimizing the risk. Are there reasonable conditions/conditions to achieve that?\n\nThey also do not discuss any societal impact, but this is fine, as their work is an early conceptual / methodological work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After some concerns of the reviewers could be resolved by the author feedback, the reviewers unanimously suggest to accept the submission. They generally found the submission interesting, theoretically sound, and well-presented. The authors should carefully incorporate the reviewer comments including their clarifications into the final version. 

Decision: Accept (Spotlight)