Adaptive Sampling Towards Fast Graph Representation Learning
Graph Convolutional Networks (GCNs) have become a crucial tool on learning representations of graph vertices. The main challenge of adapting GCNs on largescale graphs is the scalability issue that it incurs heavy cost both in computation and memory due to the uncontrollable neighborhood expansion across layers. In this paper, we accelerate the training of GCNs through developing an adaptive layer-wise sampling method. By constructing the network layer by layer in a top-down passway, we sample the lower layer conditioned on the top one, where the sampled neighborhoods are shared by different parent nodes and the over expansion is avoided owing to the fixed-size sampling. More importantly, the proposed sampler is adaptive and applicable for explicit variance reduction, which in turn enhances the training of our method. Furthermore, we propose a novel and economical approach to promote the message passing over distant nodes by applying skip connections. Intensive experiments on several benchmarks verify the effectiveness of our method regarding the classification accuracy while enjoying faster convergence speed.
In this paper, the authors solve the scalability issue of GCNs by developing a layer-by-layer sampling method for network construction. There are two benefits for this: first, it enables the neighborhood sharing in upper layers; second, the parameters of the sampler and the network can be finetuned to reduce the variance explicitly.  Moreover, to enable message passing across distant nodes, this paper proposes to apply skip connections to reuse to nodes in the (l-1)-th layer as the 2-hop neighborhoods of the (l+1)-th layer. Finally, remarkable improvements in accuracy and speedups are demonstrated for the proposed methods on four benchmarks.    1) Clarity: This is a Well-written paper. It is well organized and easy to understand.  2) Novelty: Compared to GraphSage and FastGCN that have been developed previously, the layer-wise sampling scheme by this paper is novel and efficient. Also, the idea of applying skip-connections to preserve second-order proximity is interesting.   3) Significance: Experimental evaluations verify the fast convergence speed of the proposed method compared to other sampling counter-parts. The importance of the variance reduction is also justified by Table 1.    4) Minor things: - Line 252 in the paper says the window-size of early stopping is 10, while in the supplementary the number becomes 30 in line 22. Which is correct?  - To justify the importance of the variance reduction, the authors set \lambda=0. However, without the variance term, how can we train the parameters of the self-dependent function, since the gradient of the classification loss is always zero? - In Line 120, the computational complexity for Eq.(1) should be O(|E|D^lD^{l-1}), not O(N^2 D^lD^{l-1}).    In all, a rather thorough paper that derives an efficient way to perform convolutions on graphs using layer-wise sampling and skip-connections. At one hand, this leads to improvements over other competing methods in terms of accuracy and convergence speed. Hence, I recommend accepting this paper. ###################After Rebuttal########################### I think the authors have addressed my previous concerns, which make me not to change my mind and recommend the acceptance.