Published as a conference paper at ICLR 2020 REGIONAL BASED QUERY IN GRAPH ACTIVE LEARN- ING
Graph convolution networks (GCN) have emerged as a leading method to classify nodes and graphs. These GCN have been combined with active learning (AL) methods when a small chosen set of tagged examples can be used. Most AL-GCN use the sample class uncertainty as selection criteria, and not the graph. In contrast, representative sampling uses the graph, but not the prediction. We propose to combine the two and query nodes based on the uncertainty of the graph around them. We here propose two novel methods to select optimal nodes in AL-GCN that explicitly use the graph information to query for optimal nodes. The first method named regional uncertainty is an extension of the classical entropy measure, but instead of sampling nodes with high entropy, we propose to sample nodes surrounded by nodes of different classes, or nodes with high ambiguity. The second method called Adaptive Page-Rank is an extension of the page-rank algorithm, where nodes that have a low probability of being reached by random walks from tagged nodes are selected. We show that the latter is optimal when the fraction of tagged nodes is low, and when this fraction grows to one over the average degree, the regional uncertainty performs better than all existing methods. While we have tested these methods on graphs, such methods can be extended to any classification problem, where a distance can be defined between the input samples.
The paper studies active learning in graph representations. To decide which nodes in a graph to label during the active labeling, the paper proposes two approaches. First it argues that one should consider region-based measures rather than single nodes. Second, it proposes to adapt the page rank algorithm (APR) to determine which nodes are far away from labeled nodes.
Overall it remains unclear *how* to select the right strategy (before seeing the results for a dataset) i.e. which of the proposed approaches or variants should one select for a new dataset.
Strength:
-	One of the ideas of the paper, using region entropy over single node entropy makes sense to me.
-	The paper evaluates on 6 datasets and compares different variants as well to related work on 2 datasets.
Weaknesses:
1.	The paper contains several confusing and contradicting statements or claims which are not supported by the experimental results:
For example:
1.1.	“APR outperforms all other methods at low sampling fractions”.  This is supported neither in Table 1 nor Table 2, where APR is frequently not highest performing
1.2.	 “We have here shown that the accuracy of AL when uncertainty is computed regionally is much higher than when either local uncertainty or representative nodes are used”, this is not the case on CiteSeer in Table 1
1.2.1.	Also e.g. “Region Margin” is worse than random on 5% Email-EU; or “Region Margin AE” on 3% SubeljCora (Table 2) [It is unclear how to select with or without AE]
1.3.	“We outperform all existing methods in the Cora dataset, and get very similar results to the best accuracy obtained by Chang et al methods:”
1.3.1.	The difference to Cai et al. on Cora is very small (improvement by only 0.002), while on Citeseer the performance is comparatively bigger (Cai et al. is by 0.016 better)
1.3.2.	It should be “Cai et al”
2.	Clarity: I found the paper rather difficult to understand and follow:
Some specifics:
2.1.	The introduction could be more concisely discussing the motivation, the main idea of the paper, as well as contributions.
2.2.	Figure 1: according to the caption, APR should point to node 15, but in the figure it points to node 14. From the example it makes much more sense to label node 14 to me.
2.3.	Page 6 mentions twice the “ratio between APR and PR”, is this is this used/evaluated in the results?
2.4.	The decision what is bold and what is not is not consistent throughout the table 2.
2.5.	“Thus, hybrid techniques, combining several approaches, outperform using only one approach have been proposed.” It is not clear what this refers to and where the hybrid techniques have been evaluated.
Minor:
The paper contains many minor writing issues, e.g.
-	missing spaces, e.g. “distribution,and” (page 2)
-	Table 1: incomplete sentence: “∗∗ scores for smaller budget, since it was the”
-	Table 2: unclear: “accuracy without content”
The paper’s incorrect claims (weakness 1) are highly concerning and strongly suggest rejecting the paper. Furthermore, the clarity of the paper should be improved to follow the author arguments and make the paper easier to read.