Graph convolutional networks (GCNs) are powerful deep neural networks for graph-structured data. However, GCN computes nodes' representation recursively from their neighbors, making the receptive field size grow exponentially with the number of layers. Previous attempts on reducing the receptive field size by subsampling neighbors do not have any convergence guarantee, and their receptive field size per node is still in the order of hundreds. In this paper, we develop a preprocessing strategy and two control variate based algorithms to further reduce the receptive field size. Our algorithms are guaranteed to converge to GCN's local optimum regardless of the neighbor sampling size. Empirical results show that our algorithms have a similar convergence speed per epoch with the exact algorithm even using only two neighbors per node. The time consumption of our algorithm on the Reddit dataset is only one fifth of previous neighbor sampling algorithms.
The paper proposes a method to speed up the training of graph convolutional networks, which are quite slow for large graphs. The key insight is to improve the estimates of the average neighbor activations (via neighbor sampling) so that we can either sample less neighbors or have higher accuracy for the same number of sampled neighbors. The idea is quite simple: estimate the current average neighbor activations as a delta over the minibatch running average. I was hoping the method would also include importance sampling, but it doesn’t. The assumption that activations in a graph convolution are independent Gaussians is quite odd (and unproven). 
Quality: Statistically, the paper seems sound. There are some odd assumptions (independent Gaussian activations in a graph convolution embedding?!?) but otherwise the proposed methodology is rather straightforward. 
Clarity: It is well written and the reader is able to follow most of the details. I wish the authors had spent more time discussing the independent Gaussian assumption, rather than just arguing that a graph convolution (where units are not interacting through a simple grid like in a CNN) is equivalent to the setting of Wang and Manning (I don’t see the equivalence). Wang and Manning are looking at MLPs, not even CNNs, which clearly have more independent activations than a CNN or a graph convolution. 
Significance: Not very significant. The problem of computing better averages for a specific problem (neighbor embedding average) seems a bit too narrow. The solution is straightforward, while some of the approximations make some odd simplifying assumptions (independent activations in a convolution, infinitesimal learning rates). 
Theorem 2 is not too useful, unfortunately: Showing that the estimated gradient is asymptotically unbiased with learning rates approaching zero over Lipchitz functions does not seem like an useful statement. Learning rates will never be close enough to zero (specially for large batch sizes). And if the running activation average converges to the true value, the training is probably over. The method should show it helps when the values are oscillating in the early stages of the training, not when the training is done near the local optimum.