Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

*** If the authors properly address the following issues, I am more than willing to change my rating. ***

The 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.

Additionally, 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.

It 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?

It 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?

More 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"). 

Empirical evaluations:
The achieved results definitely are impressive, in particular, in noisy settings. The code seems to be reproducible and well documented.
However, there are multiple issues.

1. 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.

2. The four used datasets (especially the three citation datasets) are generally known to be overused in the last years.
    Other graphs should have been used instead or additionally.

3. 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?

4. 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.

5. 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. 

6. 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.

7. 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.

8. How do the approaches select the first vertex (or batch $V_0$) to query?

Missing / not discussed important previous work:

* 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.

* 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).

(Easily fixable) notation issues:

* $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).

* 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.

* 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.

* 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(.)|$

* Why is there an underline in line 205 and also in line 33 of the appendix.

* 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.

Some smaller language issues:
Line 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.

Some issues in the references:

Why 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.

References:

[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.

[Ma, 2013] Ma, Yifei, Roman Garnett, and Jeff G. Schneider. "Σ-Optimality for Active Learning on Gaussian Random Fields." NIPS. 2013.

[Gu, 2012] Gu, Quanquan, and Jiawei Han. "Towards active learning on graphs: An error bound minimization approach." ICDM 2012.

[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

[Chen 2013] Chen, Yuxin, and Andreas Krause. "Near-optimal batch mode active learning and adaptive submodular optimization." ICML 2013.

[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.
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). 

 In real-world applications, the labeling accuracy $\alpha$ is usually unknown. The authors could add a discussion on what to do in such situations.

The 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?

They also do not discuss any societal impact, but this is fine, as their work is an early conceptual / methodological work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

In 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: 
(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. 

(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? 
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.
- 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.
- 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.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.
limitations_and_societal_impact: Limitation:
1. 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.
2. 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.
3. It is not clear to me how equation 6 in appendix is derived. In particular, where does k come from?

Societal Impact:
There is no significant negative societal impact associated with this research.
review_title: null

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)