Active Learning Graph Neural Networks via Node Feature Propagation
Authors: Yuexin Wu
Yichong Xu
Aarti Singh
Artur Dubrawski
Yiming Yang
Venue:  (2020)
Keywords: Graph Learning
Active Learning

Abstract: Graph Neural Networks (GNNs) for prediction tasks like node classification or edge prediction have received increasing attention in recent machine learning from graphically structured data. However, a large quantity of labeled graphs is difficult to obtain, which significantly limit the true success of GNNs. Although active learning has been widely studied for addressing label-sparse issues with other data types like text, images, etc., how to make it effective over graphs is an open question for research.  In this paper, we present the investigation on active learning with GNNs for node classification tasks.  Specifically, we propose a new method, which uses node feature propagation followed by K-Medoids clustering of the nodes for instance selection in active learning. With a theoretical bound analysis we justify the design choice of our approach. In our experiments on four benchmark dataset, the proposed method outperforms other representative baseline methods consistently and significantly.

Under review as a conference paper at ICLR 2020
ACTIVE LEARNING FOR GRAPH NEURAL NETWORKS VIA NODE FEATURE PROPAGATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) for prediction tasks like node classification edge prediction have received increasing attention recent machine learning from graphically structured data. However, large quantity of labeled graphs is difficult to obtain, which significantly limits the true success of GNNs. Although active learning has been widely studied for addressing label-sparse issues with other data types like text, images, etc., how to make it effective over graphs is an open question for research. In this paper, we present investigation active learning with GNNs for node classification tasks. Specifically, we propose a new method, which uses node feature propagation followed by K-Medoids clustering of the nodes for instance selection in active learning. With a theoretical bound analysis we justify the design choice of our approach. In our experiments on four benchmark datasets, the proposed method outperforms other representative baseline methods consistently and significantly.
INTRODUCTION
Graph Neural Networks (GNN) (Kipf & Welling 2016 Veličković et al.] 2017 Hamilton et al. 2017 /W et al., 2019) have been widely applied many supervised and semi-supervised learning scenarios such as node classifications, edge predictions and graph classifications over the past few years. Though GNN frameworks are effective at fusing both the feature representations of nodes and the connectivity information, people are longing for enhancing the learning efficiency of such frameworks using limited annotated nodes. This property is in constant need as the budget for labeling is usually far less than the total number of nodes. For example, in biological problems where graph represents the chemical structure (Gilmer et al., |017: [in al. 2018) of a certain drug assembled through atoms, it is not easy to obtain detailed analysis of the function for each atom since getting expert labeling advice is very expensive. On the other hand, people can carefully design a small "seeding pool" so that by selecting "representative" nodes or atoms the training set, a GNN can be trained to get an automatic estimation of the functions for all the remaining unlabeled ones.
Active Learning (AL) (Settles 2009
Bodó et al. 2011 following this lead, provides solutions
that select "informative" examples as the initial training set. While people have proposed various methods for active learning on graphs (Bilgic et al., 2010 Kuwadekar & Neville 2011 Moore
et al.) 2011: Rattigan et al. 2007), active learning for GNN has received relatively few attention in this area. Cai al. (2017) Gao et al. (2018) two major works that study active learning for GNN. The two papers both use three kinds of metrics to evaluate the training samples, namely uncertainty, information density, and graph centrality. The first two metrics make use of the GNN representations learnt using both node features and the graph; while they might be reasonable with a good (well-trained) GNN model, the metrics are not informative when the label budget is limited and/or the network weights are under-trained so that the learned representation is not good. On the other hand, graph centrality ignores the node features and might not get the real informative nodes. Further, methods proposed in Cai et al. (2017); Gao et al. (2018) only combine the scores using simple linear weighted-sum, which do not solve these problems principally.
We propose a method specifically designed for GNN that naturally avoids the problems of methods above Our method select the nodes based on node features propagated through the graph structure,
Our code will be released upon acceptance.

---

Under review as a conference paper at ICLR 2020
making it less sensitive to inaccuracies of representation learnt by under-trained models. Then cluster the nodes using K-Medoids clustering; K-Medoids is similar to the conventional K- K-Means, but constrains the centers to be real nodes in the graph. Theoretical results and practical experiments prove the strength of our algorithm.
We perform theoretical analysis for our method and study the relation between its classifi- cation loss and the geometry of the propagated node features.
We show the advantage of our method over Coreset (Sener & Savarese 2017) by comparing the bounds. We also conjecture that similar bounds are not achievable if we use raw unpropagated node features.
We compare our method with several AL methods and obtain the best performance over all benchmark datasets.
RELATED WORKS
Active Learning (AL) aims interactively choosing data points from the training pool to maximize model performances. and has been widely studied both in theory (Beygelzimer et al. [0008] Hanneke 2014) and practice (Settles) 2009; Shen al., 2017). Recently, [Sener& Savarese (2017) proposes to compute a Coreset over the last-layer activation of a convolutional neural network. The method is designed for general-pune purppse neural networks, and does not take the graph structure into account.
Early works on AL with graph-strum sreph-structured data (Dasarathy et al. 2015 Mac Aodha et al., 2014)) study non- conaamametriic classification models with graph regularization. More recent works analyze active sampling under the graph signal processing framework (Ortega et al. 2018 Chen et al. 2016). However, most of these works have focused on the denoising setting where the signal is smooth over the graphs and labels are noisy versions of node features. Similarly, optimal experimental design (Pukelsheim 2006; Allen-Zhu et al. 2017) can also apply to graph data but primarily deals with linear regression problems, instead of nonlinear classification with discrete labels.
Graph Neural Networks (GNNs) (Hamilton et al., 2017: Veličković et al, 2017: Kipf & Welling
2016) are the emerging frameworks in the recent years when people try to model graph-structured data. Most of the GNN variants follow a multi-layer paradigm. In each layer, the network performs a message passing scheme, so that the feature representation of a node in the next layer could be some neighborhood aggregation from its previous layer. The final feature of a single node thus comprises of the information from multi-hop neighborhood, and usually universal and "informative" to be used for multiple tasks. Recent works show the effectiveness of using GNNs in the AL setting. Cai al. (017)), for instance, proposes to linearly combine uncertainty, graph centrality and information density scores and obtains the optimal performance. Gao et al. (018)) further improves the result by using learnable combination of weights with multi-armed bandit techniques. Instead of combining different metrics, in this paper, we approach the problem by clustering propagated node features. We show that our one-step active design outperforms existing methods based on learnt network represenations, in the small label setting, while not degrading in performance for larger amounts of labeled data.
PRELIMINARIES
In this section, we describe a formal definition for the problem of graph- based active learning under the node classification setting and introduce a uniform set of notations for the rest of the paper.
We are given a large graph G =VV, E), where each node E V is associated with a feature vector Te E X C Rd and a label ye y = 21, C}. Let V = {1, 2..,,..,, n), we denote the input features as matrix X E Rnxd, where each row represents node, and the labels as vector
Y (V):-. ..., Vn). We also consider loss function 1(M G, X, Y) that computes the loss over the inputs (G, X, Y) for model M that maps G, X prediction vector Y E e
Following previous works on GNN(CCa et al. 2017 Hamilton et al. 2017). we consider the inductive learning setting; i.e., small part of Y is revealed to the algorithm, and wish to minimize the loss on the whole graph [(MG, X, Y). Specifically, an active learning algorithm A is initially given
the graph G and feature matrix X. In step / of operation, it selects subset s' C [m] {1, (1.2...,.)) n).
2

---

Under review as a conference paper at ICLR 2020
and obtains ys for every i s². We assume ys is drawn randomly according to distribution Pa ylzz supported on }/; we use (v) = Pr(y c|uj to denote the probability that y C given node v, and ((()) = (v) (v),..., (c()) " Then uses G, X and yi for i E S U... Us as the training set to train model, using training algorithm .M. The trained model is denoted as M. If . is the same for all active learning strategies, we can slightly abuse the notation A, = ,MA. to emphasize the focus of active learning algorithms. A general goal of active learning is then to minimize the loss under a given budget b:
min
where the randomness is over the random choices of Y and A. We focus on M being the Graph Neural Networks and their variants elaborated in detail in the following part.
3.1 GRAPH NEURAL NETWORK FRAMEWORK
Graph Neural Networks define multi-layer feature propagation process similar to Multi-Layer Perceptrons (MLPs). Denote the k-th layer representation matrix of all nodes as (*),, and X( e Raxd are the input node features. Graph Neural Networks (GNNs) differ in their ways of defining the recursive function f for the next-layer representation:
((++1) f(x(), G, Ox),
(2)
where O₂ is the parameter for the le-th layer. Naturally, the input X satisfies X = X by definition. Graph Convolution Network (GCN). A GCN (Kipf & Welling 2016) has a specific form of the function f as:
x (k+1) + ReLU(SX(
(3)
where ReLU is the element-wise rectified-lineal unit activation function (Nair & Hinton 2010). θ₂ is the parameter matrix used for transforming the size of feature representations different dimension and S is the normalized adjacency matrix. Specifically, $ is defined as:
S (I D)+ *(A [[T+
where A is the original adjacency matrix associated with graph G and D is the diagonal degree matrix of A. Intuitively, this operation updates node embeddings by the aggregation of their neighbors. The added identity matrix I (equivalent to adding self-loops to G) acts in a similar spirit to the residual links (He et al. 2016) in MLPs that bypasses shallow-layer representations to deep layers. By applying this operation in mulli--aaye fashion, GCN encourages nodes that are locally related to share similar deep-layer embeddings and prediction results thereafter.
For the classification task, it is normal to stack linear transformation along with softmax function to the representation in the final layer, so that each class could have prediction score. That is,
Y softmax (x (x))
(5)
where softmax(x:) (z) = exp(x)/XX E
c= exp(xz) which makes the prediction scores have unit sum of 1 for all classes, and K is the total number of layers. We use the GCN structure as the fixed unified model M for all the following discussed AL strategies A.
4 ACTIVE LEARNING STRATEGY & THEORETICAL ANALYSIS
Traditionally, active learning algorithms choose one instance at a time for labeling, i.c., with |s'| 1. However, for modern datasets where the numbers of training instances are very large, it would be extremely costly if we re-train the entire system each time when a new label is obtained. Hence we focus on the "batched" one-step active learning setting (Contardo et al. (017). and select the informative nodes once and for all when the algorithm starts. This is also called the optimal experimental design in the literature (Pukelsheim) 2006 Allen-Zhu et al. 2017). Aiming to select the b most representative nodes as the batch, our target becomes:
min *S1Sh
The node selection algorithm is described in Section 4.1 followed by the loss bound analysis in Section 4.2 and the comparison with a closely related algorithm (K-Center in Coreset (Sener & (Savarese 2017)) in Section 4.3
3

---

Under review as a conference paper at ICLR 2020
4.1 NODE SELECTION VIA FEATURE PROPAGATION AND K-MEDOIDS CLUSTERING
Algorithm Active Learning with Distance-based Clustering
Input: Node representation matrix X, graph structure matrix G and budget b
1: Compute distance function (x:) V x V + R
# for FeatProp: use Eqn. # for FeatProp: use K-Medoids
2: Perform clustering using dx,G with centers
3: Select to be the centers
4: Obtain labels for v E s and train model M
Output: Model M
We describe a generic active learning framework using distance-based clustering in Algorithm T acts in major steps: 1) computing distance matrix or function dx G using the node feature representations X and the graph structure G; 2) applying clustering with b centers over this distance matrix, and from each cluster select the node closest to the center of the cluster. After receiving the labels (given by matrix Y) of the selected nodes, we train graph neural network, specifically GCN, based on X, G and Y for the node classification task. Generally speaking, different options for the two steps above would yield different performance in the down-stream prediction tasks; we detail and justify our choices below and in subsequent sections.
Distance Function. Previous methods (Sener & Savarese, 2017 Cai et al. 2017, Gao et al. 2018
commonly use network representations compute the distance, i.e., ( v1) = [(X ()))
(x(*)) for some specific While this can be helpful in a well-trained network, the representations quite inaceurate in initial stages of training and such distance function might not select the
representatitive nodes. Differently, we define the pairwise node distance using the L2 norm of the difference between the corresponding propagated node features:
dx Uz) |I(S* X); - (S* X)gl12,
where (M); denotes the i-th row of matrix M, and recall that K is the total number of layers. Intuitively, this removes the effect of untrained parameters on the distance, while still taking the graph structure into account.
Clustering Method.
Two commonly used methods are K-Means (Cai et al. 2017 Gao et al. 2018)
and K-Center (Sener Savarese 2017 We propose to apply the K-Medoids clustering. K-Medoids problem is similar to K-Means, but the center it selects must be real sample nodes from the dataset. This is critical for active learning, since we cannot try to label the unreal cluster centers produced by K-Means. Also, show in Section 4.3 that K-Medoids can obtain a more favorable loss bound than K-Center.
We call our method FeatProp, emphasize the active learning strategy via node feature propagation over the input graph, which is the major difference from other node selection methods.
4.2 THEORETICAL ANALYSIS OF CLASSIFICATION LOss BOUND
Recall that we use [|(S*)) - (S* X);l12 to approximate the pairwise distances between the hidden representations of nodes GCN. Intuitively, representation 5 X resembles the output of simplified GCN (Wu et al. 2019) by dropping all activation functions and layer-related parameters in the original structure, which introduces a strong inductive bias. In other words, the selected nodes could possibly contribute to the stabilization of model parameters during the training phase of GCN. The following theorem formally shows that using K-Medoids with propagated features can lead to a low classification loss:
Theorem 1 (informal), Suppose that the label vector Y is sampled independently from the distribution Yi ~ (i)), and the loss function is bounded by [-L, L). Then under mild assumptions, there exists a constant on such that with probability 1 8 the expected classification loss of A, satisfies
1 [[(AolG, X,
L log(1/8)
min [| x), (S* X)xl12 + jeso
(8)
2n.
For group of nodes, K-Center problem aims find a 5-cover with most nodes for smallest possible 8.
4

---

Under review as a conference paper at ICLR 2020
To understand Theorem notice that the first term Σx=1 minjeso lI(S* X); (S* X)i is exactly
the target loss of K- K-Medoids (sum of point-center distances), and the second term / l quickly decays with where is the total number of nodes in graph G. Therefore the classification loss of Ao on the entire graph G is mostly dependent the K-Medoids loss. In practice, we can utilize existing robust initialization algorithms such as Partitioning Around Medoids (PAM) to approximate optimal solution for K-Medoids clustering.
2n
The assumptions we made in Theorem are pretty standard in the literature, and we illustrate the details in the appendix. While our results share some common characteristics with Sener et al. (l..eneer & Savarese 2017). our proof is more involved in the sense that it relates to the translated features [[5*X); (S x)ilia instead the raw features (I(); (X) )
fact, we conjecture that using
raw feature clustering selection for GCN will not result in similar bound in (8): this is because
GCN uses the matrix S to diffuse the raw features across all nodes in V. and the final predictions
of node will also depend on its neighbors well the feature (X);- We could a clearer comparison practice in Section 5.2
de
duo
d
dg
de
Figure I: Visualization of Theorem 1 Consider the set of selected points s and the remaining points in the dataset [n]]ss. K-Medoids corresponds to the mean of all red segments in the figure, whereas K-Center corresponds to the max all segments the figure.
4.3
WHY NOT K-CENTER
In this subsection provide justifications using the K-Medoids clustering method opposed to Coreset (Sener & Savarese 2017). The Coreset approach aims to find a 8-cover of the training set. In the context of using propagated features, this means solving
min max min dx.a("; Uy) min max min [s
[[ X); - (S X)xl1a
(9)
jEs
jes
We can show a similar theorem as Theorem | for the Coreset approach:
Theorem 2. Under the same assumptions as in Theorem with probability 8 the expected classification loss of Ag satisfies
I log(1/8)
1(A,G & co max max ||( X); KS* X)sl12 + 72
(10)
jeso
2n
Let d; = minjes" ||S X); ( X) 1l2. It is easy to see that RHS of Eqn. is smaller than RHS of Eqn. (9) since 1 Σn= dç < max; d, In other words, K-Medoids can obtain better bound than
the K-Center method (see Figure f a graphical illustration). We observe superior performance of
K-Medoid clustering over K- K-Center clustering in our experiments as well (see Section 5.2).
5 EXPERIMENT
We evaluate the node classification performance of our selection method on the Cora, Citeseer, and PubMed network datasets (Yang al. 2016). We further supplement experiment with an
5

---

Under review as a conference paper at ICLR 2020
denser network dataset CoraFull (Bojchevski & Günnemann, 2017) to illustrate the performance
differences of the comparing approaches on a large-scale setting. Table I summarizes the dataset statistics.
Data
Nodes
Edges
Classes
Feature size
Cora
2,708
5,429
3,703
Citeseer
3,327
4,732
6
1,433
PubMed
19,717
44,338
3
500
CoraFull
19,793
126,842
70
8.710
Table 1: Dataset statistics of different networks.
Cora
Citeseer
PubMed
CoraFull
FeatProp 239
622
1,506
13,059
CoresetMIP 12,260
13,257
OOT
OOT
Coreset-greedy 44
46
509
636
Table 2: Comparison of running time of 5 different runs in seconds between our algorithm (FeatProp) and Coreset. OOT denotes out-of-time. Note in order to get more accurate solution, CoresetMIP costs much more time than Coreset-greedy.
Cora
Citeseer
PubMed
CoraFull
Random
59.83 + 5.77
48.79 + 4.03
71.66 4.50
10.75 + 0.92
Degree
63.30 + 0.55
35.50 + 0.82
60.54 0.38
10.85 + 0.30
Uncertainty
39.14 4.52
6.76 = 0.72
Coreset-greedy
59.99 + 4.59
48.21 + 3.78
68.41 4.50
10.83 + 1.28
CoresetMIP
55.86 6.89
46.76 3.99
AGE
65.01 2.43
49.65 5.19
67.96 + 2.73
13.52 + 0.81
ANRMAB
63.71 4.34
47.29
+ 3.33
71.06 4.82
11.40 + 0.98
FeatProp
74.89 + 2.63
51.03 + 2.80
73.20 + 1.81
14.86 + 0.70
Table 3: Comparison of Aicro-Fl-istaddard deviation averaged over different number of labeled nodes for training. Bold fonts represent the best methods. CorsetMIP does not scale up for PubMed and CoraFull datasets.
We evaluate the Macro-F1 of the methods over the full set of nodes. The sizes of the budgets are fixed for all benchmark datasets. Specifically, we choose to select 10, 20, 40, 80 and 160 nodes as the budget sizes. After selecting the nodes, two-layer GCN with 16 hidden neurons, is trained as the prediction model. We use the Adam (Kingma Ba 2014) optimizer with a learning rate of 0.01 and weight decay of 3 10-4, All the other hyperparameters kept in the default setting (81 = 0.9, 32 = 0.999). To guarantee the convergence of the GCN, the model trained after 200 epochs is used to evaluate the metric the whole set.
5.1 BASELINES
We compared the following methods:
Random:
Choosing the nodes uniformly from the whole vertex set.
Degree: Choosing the nodes with the largest degrees. Note that this method does not
consider the information of node features.
Uncertainty: Similar to the methods Joshi al. (2009), we put the nodes with max- entropy into the pool of instances.
In the semi-supervised setting of citation networks, two-layer GCN is the optimal structure for the node classification task (Kipf & Welling, 2016).

---

Under review as a conference paper at ICLR 2020
This method performs a K-Center clustering over the last hidden representations in the network. If time allows (on Cora and Citeseer), a robust mixture integer programming method in Sennrr & Savarese (2017) (dubbed CoresetMIP) is adopted. We also apply a time-efficient approximation version (Coreset-greedy) for all of the datasets. The center nodes then selected into the pool.
Coreset (Sener & Savarese, 2017):
AGE (Cai et al., 2017): This method linearly combines three metrics graph centrality, information density, and uncertainty and select nodes with the highest scores.
ANRMAB (Gao et al., 2018): This method enhances AGE by learning the combination weights of metries through exponential multi-arm- bandit updating rule.
FeatProp: This is method. We perform K-Medoids clustering to the propogated features (Eqn. (7), where is the input node features. the experiment, we adopts an efficient approximated K-Medoids algorithm which performs K-Means until convergence and select nodes cloesest to centers into the pool.
Citeseer
0.6
Macro-F1
0.6
Macro-F7
0.5
0.4
0.3
0.2
0.2
160
Labeled data
# Labeled data
PubMed
CoraFull
0.8
0.25
Macro-F1
0.7
Macro-F1
0.20
0.15
0.6
0.10
0.5
0.05
0.00
10
20
40
80
160
10
20
40
80
160
Labeled data
# Labeled data
Random Degree
Uncertainty Coresat-greedy
CoresetMIP AGE
ANRMAB FeatProp
Figure 2: Results of different approaches over benchmark datasets averaged from different runs.
5.2 EXPERIMENT RESULTS
In our experiments, start with small set of nodes nodes) sampled uniformly random from the dataset the initial pool. We run all experiments with 5 different random seeds and report the averaged classification accuracy the metric. We plot the accuracy the number of labeled points. For approaches (U (Uncertainty, Coreset, AGE and ANRMAB) that require the current status/hidden representations from the classification model, fully-trained model built from the previous budget pool is returned. For example, if the current budget is 40, the model trained from 20 examples selected by the same AL method is used.
Main results. As is shown in Figure 2 our method outperforms all the other baseline methods in most of the compared settings. is noticeable that AGE and ANRMAB which use uncertainty score their sub-cor sub-component methods most of the cases. We also show an averaged Macro-Fl with standard deviation across different number of labeled nodes in Table It is interesting find that method has the second
achieve better performances than Uncertainty and the second best
7

---

Under review as a conference paper at ICLR 2020
smallest standard deviation (Degree is deterministic in terms of node selection and the variance only comes from the training process) among all methods. We conjecture that this is due to the fact that other methods building upon uncertainty may suffer from highly variant model parameters at the beginning phase with very limited labeled nodes.
Efficiency. We also compare the time expenses between method and Coreset, which also involves It is noticeable that in order to make Coreset more
a clustering sub-routine (K-Center), in Table 2 stable, CoresetMIP uses extreme excess time comparing to Coreset-greedy in the same setting. An interesting fact we could observe in Figure is that CoresetMIP and Coreset-greedy do not have too much performance difference on Citeseer, and poreset-greedy is even better than CoresetMIP on Cora. This is quite different from the result in image classification tasks with CNNs (Sener & Savarese 2017). This phenomenon distinguishes the difference between graph node classification with traditional classification problems. We conjecture that this is partially due to the fact that the nodes no longer preserve independent embeddings after the GCN structure, which makes the original analysis of Coreset not applicable.
Cora
Citeseer
0.6
Macro-F1
Macro-F1
0.6
0.4
0.4
10
20
40
160
20
40
80
160
Labeled data
Labeledd data
FeatProp
FeatProp w/ network reprenseriatiionn
FeatProp w/ kcenter
Figure 3: Results of different approaches over benchmark datasets averaged from 5 different runs. Similar to Coreset, the orange line denotes replacing the original distance function in Eqn. (7) with L2 distance from the final GCN layer. The blue line denotes the algorithm replacing the K-Medoids module with K-Center clustering.
Ablation study. It is crucial to select the proper distance function and clustering subroutine for FeatProp (Line [ and Line Algorithm [ As is discussed in Section 4.3 we test the differences with the variant of using the L2 distance from the final layer of GCN as the distance function and the one by setting K-Medoids choice with K-Center replacement. We compare these algorithms in Figure 3 As is demonstrated in the figure, the K-Center version (blue line) has lower accuracy than the original FeatProp approach. This observation compatible with our analysis in Section (4.3 K-Medoids comes with tighter bound than K-Center in terms of the classification loss. Furthermore, as final layer representations are very sensitive to the small budget case, we observe that the network representation version (orange line) also generally shows much deteriorated performance at the beginning stage.
Though FeatProp is tailored for GCNs, we could also test the effectiveness of our algorithm over other GNN frameworks. Specifically, we compare the methods over a Simplified Graph Convolution (SGC) (Wu et al. 2019) and obtain similar observations. Due the space limit, we put the detailed results in the appendix.
CONCLUSION
We study the active learning problem in the node classification task for Graph Convolution Networks (GCNs). We propose a propagated node feature selection approach (FeatProp) to comply with the specific structure of GCNs and give theoretical result characterizing the relation between its classification loss and the geometry of the propagated node features. Our empirical experiments also show that FeatProp outperforms the state-of-the-an AL methods consistently on most benchmark datasets. Note that FeatProp only focuses on sampling representative points a meaningful (graph) representation, while uncertainty-basee methods select the active nodes from different criterion
8

---

Under review as a conference paper at ICLR 2020
guided by labels, how to combine that category of methods with FeatProp in principled way remains an open and yet interesting problem for us to explore.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimization for experimental design: A regret minimization approach. CoRR, abs/1711.05174, 2017. URL
http://arxiv.org///. /t11//0001111111144
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.03962. 2018.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. arXiv preprint arXiv:08/2.4995,, 2008.
Mustafa Bilgic, Lilyana Mihalkova, and Lise Getoor. Active learning for networked data. In Proceedings of the 27th international conference on machine learning (ICML-I0), pp. 79-86, 2010.
Zalán Bodó, Zsolt Minier, and Lehel Csató. Active learning with clustering. In Active Learning and Experimental Design workshop In conjunction with AISTATS 2010, pp. 127-139, 2011.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv:1707.038/15 2017.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint arXiv: 7705 050855 2017.
S. Chen, R. Varma, A. Singh, and J. Kovacevic. Signal recovery on graphs: Random versus experimentally designed sampling. IEEE Transactions on Signal and Information Processing over Networks, special issue on Inference and Learning over Networks, 2(4):539-554, 2016.
Anna Choromanska, Yann LeCun, and Gérard Ben Arous. Open problem: The landscape of the loss
surfaces of multilayer networks. In Conference Learning Theory, pp. 1760, 2015.
Gabriella Contardo, Ludovic Denoyer, and Thierry Artières. A meta-learning approach to one-step active learning. arXiv preprint 1706::7706.08.... 08334, 2017.
Gautam Dasarathy, Robert D. Nowak, and Xiaojin Zhu. S2: an efficient graph based active learning algorithm with application to nonparametric classification. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pp. 503-522. org 2015, URL http: wwwmm..orgg/poooooo wttp:///prr..eeen.n////apsss///e Dasarathy15 html
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint 18/1 003804, 2018.
Li Gao, Hong Yang, Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network representation learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 1142-2148, AAAI Press, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Volume 70, pp. 1263-1272. JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1034-1034,10 2017.
Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learning, 7(2-3), 2014.

---

Under review as a conference paper at ICLR 2020
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Wassily Hoeffding. Probability inequalities for sums bounded random variables. The Collected Works of Wassily Hoeffdding, pp- 409-426 Springer, 1994.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. arXiv preprint arXiv: /80::046224444 2018.
Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2372- 2379. IEFE, 2009.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pp. 586-594, 2016.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprini arXiv: 1412,6980 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arviv: 1609 029000 2016.
Ankit Kuwadekar and Jennifer Neville. Relational active learning for joint collective classification models. In Proceedings of the 28th international conference on machine learning (icml-1 / 1), pp. 385-392. Citeseer, 2011.
Oisin Mac Aodha, Neill D. Campbell, Jan Kautz, and Gabriel J. Brostow. Hierarchical subquery evaluation for active learning on graph. In 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014, pp. 564-571. IEEE Computer Society, 2014. ISBN 978- 11881-9-99-51188- doi: 10. 1111009/CVP.2211...77. URL https
1109 11/099/CPPP.. 2014.79
Cristopher Moore, Xiaoran Yan, Yaojia Zhu, Jean- Bean-Baptiste Rouquier, and Terran Lane. Active learning for node classification in assortative and disassortative networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 841-849. ACM, 2011.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference machine learning (ICML-10), pp. 807-814, 2010.
A. Ortega, P. Frossard, J. Kovaevi, J. M. F. Moura, and P. Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-88)) -288, May 2018. ISSN 0018-9219. doi: 10. 10.1100//.....11.... 28200266.
Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
Matthew J Rattigan, Marc Maier, and David Jensen. Exploiting network structure for active inference in collective classification. In Seventh IEEE International Conference on Data Mining Workshops (ICDMW 2007). pp. 229-434, IEEE, 2007.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint wrXXiv1708.0044 2017.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin- Madisson Department of Computer Sciences, 2009.
Yanyao Shen, Hyokun Yun, Zachary Lipton, Yakov Kronrod, and Animashree Anandkumar. Deep
active learning for named entity recognition. Proceedings of the 2nd Workshop Representation Learning for NLP, 2017. doi: 10.18653/\1/w11-226600 URL http: // dww.oor//1
38653vv//11-26666
10

---

Under review as a conference paper at ICLR 2020
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:/710.10903, 2017.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint urXiv:1902.077 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. arXiv preprint 10Xvv:/806.03366, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. arXiv preprint
2016.

---

Under review as a conference paper at ICLR 2020
A
ADDENDUM TO EXPERIMENTS
We also evaluate the methods using the metric of Micro-Fl in Table 4
Cora
Citeseer
PubMed
CoraFull
Random
65.19 + 4.39
57.04 + 3.39
73.11 + 2.61
21.78 + 1.97
Degree
68.61 0.50
46.13 0.77
68.44 0.32
25.12 + 0.53
Uncertainty
58.88 +: 6.07
46.08 + 4.44
68.49 + 5.55
14.66 + 1.80
Coreset-greedy
66.94 2.87
55.00 3.09
70.74
24.61 2.35
CoresetMIP
63.98 5.40
55.68 3.43
AGE
70.07 1.36
57.27 4.68
73.80 - 1.91
28.35 = 1.16
ANRMAB
68.62 + 3.66
54.90 + 3.61
73.98 + 3.37
23.14 + 1.79
FeatProp 77.68 + 1.81
59.36 + 1.98
74.64 1.49
28.86 + 1.22
Table 4: Comparison of
averaged different number of labeled nodes for training. Bold fonts represent the best methods. CorsetMIP does not scale for PubMed and CoraFull datasets.
We evaluate the performances different active learning methods on 2-layer SGC (Simplified Graph Convolution) framework. The results can be seen in Figure
Cora
Citeseer
0.7
0.8
0.7
Macro-F1
Macro.F1
0.4
0.4
0.3
0.3
0.2
10
20
40
80
160
10
20
40
80
160
Labeled
Labeled data
PubMed
CoraFull
0.30
0.8
0.25
Macro-F]
0.7
Macro-F1
0.20
0.15
0.6
0.10
0.5
0.05
10
20
40
80
160
10
20
40
80
160
Labeled data
Labeled data
Uncertainty Coreset-greedy
Degroe
ANRMAB
Figure 4: Results different approaches over benchmark datasets averaged from different runs on an SGC framework.
Figure 5 shows the results of FeatProp different GNN frameworks. We that SGC has slightly inferior performance to GCN since drops all the activation functions and in-layer parameters, but not too much.
12

---

Under review as a conference paper at ICLR 2020
Cora
Citeseer
0.80
Macro-F1
0.75
Macro-F1
0.70
0.4
0.65
0.60
0.2
10
20
40
160
10
40
80
160
Labeled data
# Labeledd data
SGC
GCN
Figure 5: Results of SGC vs GCN over benchmark datasets averaged from different runs by using FeatProp.
B PROOF OF THEOREM 1
For simplicity, for any model M let - E RC be the prediction for node i under input G, X, and (M),.e be the e-th element of (M); (i.e., the prediction for class c). In order to show Theorem M we make the following assumptions:
(M),,
Assumption 1. We assume Ao overfits to the training data. Specifically, we assume the following two conditions: i) Ao has
training loss on s"; ii) for any unlabeled data (I2; with g s" and j E s", have (AAo).., S (Ao)j..; and (Ap)).c 2 (Ao)j.c for all * yj- The second condition states that Ao achieves a high confidence on trained samples and low confidence on unseen samples. We also assume that the class probabilities are given by ground truth GCN; i.e., there exists GCN M that predicts Pr(Y, c] on the entire training set. This is a common assumption in the literature, and (Du et al.) 2018) shows that gradient descent provably achieves zero training loss and precise prediction in polynomial time.
Assumption 2. We assume is Lipschitz with constant and bounded in [-L, L). The loss function is naturally Lipschitz for many common loss functions such as hinge loss, mean squared error, and cross-entropy if the model output bounded. This assumption widely used DI. theory (e.g..
Allen-Zhu et al. (2088) 8); Du et al. (018)).
Assumption 3. We assume that there exists a constant a such that the sum of input weights of every neuron is less than Namely, we assume E; (O < a. This assumption is also present in (Sener& & Savarese 2017). We note that one can make Σ, [(Ok),,) arbitrarily small without changing the network prediction; this is because dividing all input weights by constant t will also divide the output by a constant l.
Assumption 4. We assume that ReLU function activates with probability 1/2. This common assumption in analyzing the loss surface of neural networks, and also used in (Choromanska et al.) 2015 Kawaguchi 2016 Xu et al. 2018). This assumption also aligns with observations in practice that usually half' of all the ReLU neurons can activate.
With these assumptions in place, we are able to prove Theorem
Theorem ] (restated). Suppose Assumptions 1-4 hold, and the label vector Y is sampled indepen- dently from the distribution yo ny()) for every u e V. Then with probability 1 the expected classification loss of A, satisfies
(A (A+ 1(A,G.
L)a22))
L log((1/))
Σ
min |(S x); - - (3))yll2 + jezo
n
2n
i=1
13

---

Under review as a conference paper at ICLR 2020
Proof. Fix Vj for j E s and therefore the resulting model Au. Let i V s be any node and j jES. We have
By) [1((A));, y)
Σ
Pr[y, = cl(((Ao)i,..c))
o=l
c
Pr(Y; c](((AA)i.cc +
Σ (Pr(Y, = c) Pr(V, = c)) ((Aoiic)) c).
(11)
For the first term we have
C
C
Σ
Pr|y, = c](((A))i,,s
Σ
Pr(y, -)) 1((Ao) c)]
Pr(y, = =c(((AA))scr)))
Pr(y, [[(((A)) -
[((Ao)s.: -((A))))))))(()))333))) c)
Σ Pr(y, - =c]((Ao).c - (An)i.c
(12)
The last inequality holds from the Lipschitz continuity of 1. Now from Assumption 1, we have (Ao),,e 2 (Ao)j,e for c o Yj and (Ao)i.c S (Ao)i.c otherwise. Now taking the expection w.r.t the randomness in ReLU we have
E, [AAoii. (Ao)jec = E, (((Sx(K-1));00) - )
E, (SX(K-1)) - 1)
5 Es [(SX(K-))) - -(X((-11)) S
a K ||(S X): - (s*x)) x)
(13)
Here E, represents taking the expectation w.r.t ReLU. Now for 12 we have
E, Σ Pr|y, = c) ((An),, - -(oolial
EE,
Pr(y, = cl ((Ao)c - (Ab)ii)) +
E,
Pr[Y, = yıl ((Ao)s - (Ao))a)
C
Pr[Y, = c) ( K
||(5 X); - (5 X)sll
x
G=0
a
K ||( x): - -5* x),ll-
The inequality follows from 133
Now for the second loss in II we use the property that M computes the ground truth: (Pr(Y: c| Pr(Y, c)) ((Ao))..e)) ((M").. )tc- (MM"),.e) ((Ao))..)))
We now use the fact that ReLU activates with probability 1/2, and compute the expectation:
E, [((M)),, (MM*),.)(((AA).... c)]
E. [((M((((cc )cc - (MM (TE, [(M' )c,cl - F, [(M)(())))))))) ((An))
1
2x ((S* X); -(S -(s*x),) 0,02- ... -Rll(Aooi
K ||(* x); -(S* X)xll
< L
14

---

Under review as a conference paper at ICLR 2020
Here Eg means that compute the expectation w.r.t randomness in (ReLU) in Mr. The last inequality follows from definition of a, and that E [--LL].
Combining the two parts to 11 and let j argmin |1S X): (S X)sll. obtain
E By-n()) [1((A)), 4)1 = (A ()(222) min ||(s*( X); - (s* x)sll
(14)
3
Now notice that
(AAo,,XX,y)
E (((Ao)s: + Σ {(((Ao))BB))== = Σ (((A))s,b)) JES
(15)
iEV
SEV
Consider the following process: we first get G. X (fixed data) as input, which induces 17(1) for i E [ Note that MM gives the ground truth 77)) for every so distributions 17(1) = 7 are fixed once we obtain G, X Then the algorithm A choose the set s" to label. After that, we randomly sample 3/ (i] for j E s" and use the labels to train model Ag. At last, we randomly sample yi ~ 77(2) and obtain loss I(AAu) G, X. Y)). Note that the sampling of all for i V s is after we fix the model Ao. and knowing exact values of Yj for j E x does not give any information of y/ (since s7(i) is only determined by G, X). Now we use Hoeffding's ' inequality (Theorem) 3) with Z; (((AA) 9a); we have L < Z; < L by our assumption, and recall that V s we have that with probability 1 8.
b. Let be the RHS of (17)
Σ
1 (((Ao)()1) - nu - Ev-nto) [(((A))s, vi)l S
Llog(1/8)
2(n 6)
SEV'S'
Now plug in (14), multiply both sides by (n b) and rearrange. We obtain that
L Llog(1/0)
b)
Σ u((Ao)i):: < i
Σ (A+ ()a/2)) min |(s* X); -SS x),l + *EV
(16)
Now note that since the random draws of is completely irrelevant with training of Ag. we can also
sample together with y; for j E s after receiving G, X and before the training of An (AA does not have access to the labels anyway). So (16) holds for the random drawings of all y Now divide both sides of 16) by n and use 15
we have
1 -(AA)), +A+ (a/2))
L Llog(1/8)) b)
min (IS X); (8* X)al12 +
n
2n²
(A + 2)
Llog(1/8)
min [|(s X); 13sx))ll2++ + V jes
2n
C PROOF OF THEOREM 2
The same proof as Theorem applies for Theorem 2 using the max of distances instead of averaging. We therefore omit the details here.
D HOEFFDING'S INEQUALITY
We attach the Hoeffding's inequality here for the completeness our paper.
'To make a rigorous argument, we get the activation of M in this step, meaning that we pass through the randomness of in M
15

---

Under review as a conference paper at ICLR 2020
Theorem 3 (Hoeffding's s Inequality, Hoeffding (1994)) ) Suppose Zi,..., Zn are independent random
variables such that a; S Zi S b, almost surely for S S n. Then we have
1
n
22
Pr
74
>
S exp
(17)
71
> (b. a.
1=1
16


Reviews:
[{"review_id": "ryxdKsggir", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces active learning for graphs using graph neural networks\n\nThe bound is not very meaningful as it requires unrealistic assumptions and is loose. \n\nFigure 2 shows that even random selection performs quite well compared to this elaborate method. \n\nThis Area if research and the data sets don’t seem to have many actual real applications in the world with much impact. \n\n.................................................................\\.\\\\........................................,,..", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgnPPN0FB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose an interesting method to actively select samples using the embeddings learned from GNNs. The proposed method combines graph embeddings and clustering to intelligently select new node samples. Theoretical analysis is provided to support the effectiveness and experimental results shows that this method can outperform many other active learning methods.  \nThis paper can be improved on the following aspects:\n1.\tThe proposed method conducts clustering using node embeddings. Although these embeddings have encoded graph structure to some extent, I would suggest explicitly incorporating the graph structure in clustering or at least comparing to a baseline on that. The proposed method conducts embedding learning and clustering in two consecutive but separate steps. It would be interesting to see that the clustering can also leverage the graph information.\n2.\tIt would be better to provide more details about network settings (some hyperparams have already been given in the paper), and more analysis would be helpful. For example, how the number of clusters affects the performance? \n3.\tIs it possible to create a scenario where there are more labeled data from one cluster but less data from another cluster? In this case, should we still take equal amount of samples from different clusters?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkxt7UNTYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to incorporate active learning into the graph neural network training and claim some guarantee on the proposed method. \n\nI have some concerns about the correctness of the proof. For theorem 1, how is the Hoeffding applied so that the \\sqrt{n} term appears? My worry is naively applying Hoeffding as is done in the proof only gives a bound on a fixed model, but in the theorem A_t is not fixed. You may need to apply a union bound or more sophisticated set cover theory to claim the result. Or if I missed something could the authors add more details on the step using Hoeffding bound to the proof?\n\nOther than that I also feel the assumptions on theorem 1 are way too strong. Especially assumption 2 and 3. They are simply not true in application. The assumptions are so strong that the theorem, even if the proof can be fixed, is not interesting any more.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a method of selecting nodes to label in a graph neural network setting to reduce the loss as efficiently as possible. Building atop Sener & Savarese 2017 the authors propose an alternative distance metric and clustering algorithm. In comparison to the just mentioned work, they show that their upper bound is smaller than the previous art's upper bound. While one cannot conclude from this that their algorithm is better, at least empirically the method appears to have a advantage over state of the art.

However, reviewers were concerned about the assumptions necessary to prove the theorem, despite the modifications made by the authors after the initial round. 

The work proposes a simple estimator and shows promising results but reviewers felt improvements like reducing the number of assumptions and potentially a lower bound may greatly strengthen the paper.
Decision: Reject