Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################

Summary: 
This paper presents a novel variance reduction method which can adapt to any sampling-based GCN methods (inductive GCNs). The paper draws the idea from VRGCN that integrates the historical latent representations of nodes computed with full Laplacian to approximate the that computed with sampled sparse Laplacian. The variance reduction is implemented on both node embedding approximation, as well as layer-wise gradient computation in back-propagation. The resulting algorithms lead to faster convergence rate.

##########################################################################

Reasons for score:
Overall, I vote for accepting. The proposed variance reduction techniques can successfully accelerate convergence of any sampling method, according to the experiments, while also enjoys theoretical guarantee. Yet the novelty of the proposed SGCN+/SGCN++ algorithms themselves is a little limited to some extent. 

##########################################################################

Pros:
1. The authors introduced a doubly variance reduction which can effectively reduce the node approximation variance the layer-wise gradient variance of the existing sampling based GCN methods and accelerate convergence.
2. This paper also provides thorough theoretical analysis and convergence guarantee of the proposed algorithms.
3. The  authors have conducted comprehensive experiments using a variety of sampling-based GCN methods as building blocks. The quantitative results clearly demonstrate the effectiveness of the proposed algorithms. The authors also provide detailed empirical analysis on the training time / GPU memory usage of the proposed method.

##########################################################################

Cons:
1. To better illustrate the idea the variance reduction, the authors could compare the proposed algorithms with a vanilla full-batch GCN (instead of the mini-batch training version Exact used in this paper, and it could be evaluated on smaller datasets like Cora). This baseline may serve as a theoretical upper bound of SGCN+/SGCN++.
2. The proposed SGCN+ and SGCN++ requires a full-batch forward/backward computation every k step. As the authors suggest, this might hinder the scalability of SGCN++ on extremely large graphs. The authors hence propose a variant of SGCN++ which applies a large-batch approximation. The authors could also provide  an alternative version of SGCN+ without full-batch that only reduces the zeroth-order variance, and evaluate how SGCN+ without full-batch snapshot computation would impact on the zeroth-order and first-order variance.
3. Since the snapshot gap K serve as a budge hyper parameter balances between training speed and quality of variance reduction. As the model converges w.r.t. increasing number of epochs, I would like to know whether we can dynamically increase K during the training process to obtain some speed boost.
4. The paper is well-written in general. However, there is still some typos. For example, in Eq. (1) and Eq. (2), in the computation of gradient G_t^(l), the superscript in D_t should be (l+1) instead of (l), since we require the gradient of the loss w.r.t. the upper layer.

#########################################################################

Questions during rebuttal period: 
Please address and clarify the cons above

#########################################################################


review_title: a novel method to reduce variance with theoretical guarantee, but the algorithmic novelty is somewhat weak

final_score: rating: 7: Good paper, accept
review_content: Node sampling is a crucial point in making GCNs efficient. While several sampling methods have been proposed previously, the theorectical convergence analysis is still lacking. This paper finds that the convergence speed is related to not only the function approximation error but also the layer-gradient error. Based on this finding, the authors suggest to take historical hidden features and historical gradients to do doubly variance reduction. Experiments are done on 5 datasets for 7 baseline sampling-based GCNs.

Pros:

1. The core contribution of this paper lies in Theorem 1, which reveals the relationship between convergence speed and the function approximation error and the layer-gradient error. 

2. The idea of doubly variance reduction is reasonable.

Cons:

The biggest weakness of the proposed method is that it requires to compute snapshot features and gradients over all nodes (Line 5, Alg. 1 & Line 5 Alg. 2) before the sampling process. As this paper aims at enhancing sampling based GCNs, we should assumes no computation access/memory of performing full GCN. The authors have provided the related analyses in the appendix. It will be better if the experiments without full-batch shapshot are added in Table 1, as such we can check how it influences the final performance and if certain approximation will work well. 


review_title: Experiments on discussing the version without full-batch computation are needed.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper studies the convergence of stochastic training methods for graph neural networks. Here, this paper views GNN as a compositional optimization problem. Then, to reduce the variance incurred by the neighbor sampling, this paper uses SPIDER to reduce the variance to accelerate the convergence speed. It provides theoretical convergence analysis for SPIDER used on GNNs, showing that the proposed method has a better convergence rate compared with the traditional gradient descent method. At last, this paper conducts experiments to verify the proposed algorithm. 

1. Overall, this is a new application of SPIDER on GNNs. It shows how to bound the variance under the setting of GNNs, which is then used for the convergence proof. However, some assumptions are too strong, such as assumption 3. With these strong assumptions, the theoretical analysis is simplified too much.

2. Some parts are not very clear. In eq.(3), this paper claims that the bias term is mainly caused by node embedding approximation in the forward pass while the variance term is caused by gradient varinace in the backward pass. It is very confusing. The node embedding approximation affects both the forward and backward pass. Why does it only affect the forward pass?

3. For figure 3, the exact sampling method uses all neighbors. Therefore, it is actually the full gradient desenct method. Why does there exist variance? 

4. The most weak point of this paper is that the theory is NOT consistent with experiments. In detail, the theorems study the convergence rate of (variance-reduced) SGD. However, in experiments, this paper uses Adam. Thus, the experimental results cannot support the claim of theories. 



review_title: The theory is not consistent with experiments

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper provides a convergence analysis for GCN training and proposes two variance reduction algorithms to ensure convergence. 

The authors first draw a connection between sampling-based GCN training and compositional optimization, and they divide the error of gradient into a bias term and a variance term. This is actually first established in [Cong et al. Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks]. Although there is some inaccuracy in their formulation, the authors should clarify that this observation is first made by previous work. 

Based on the variance and bias decoupling, the authors then establish a convergence result for biased SGD (Theorem 1). The analysis itself is trivial and is not new. The authors should consider adding some references. 

The authors then propose an algorithm to reduce the bias term (Algorithm 1). Again, this is not new. It is exactly the nested SPIDER method for solving multi-level stochastic compositional optimization [Zhang et al. Multi-Level Composite Stochastic Optimization via Nested Variance Reduction]. Although the paper is the first to apply the algorithm to GCN training (as far as I know), it is important to have correct references to clarify the contribution. Also, it is worth noting that the algorithm is based on the assumption that the full neighbor aggregation result is available and the storage of Z and H is possible. I doubt the practicality of the algorithm for training on large graphs. 

The experimental results validate that the algorithm works for GCN training. However, I notice that some values in Table 1 for the baseline (SGCN) are not the best results reported in other papers. For example, GraphSAINT achieves 96% on Reddit graph, but the authors report 93.68% as the baseline. This makes me suspect that the good results reported in the paper may be due to some parameter tuning instead of the algorithm itself. 


A minor point: 
The paper says “the data points in these works are sampled independently, but the data points (nodes) in SGCN are sampled node- or layer-dependent according to the graph structure.”
The data samples in compositional optimization do not need to be independent. The only requirement is that the stochastic function with the data samples is unbiased. 

review_title: need to clarify contribution

Meta-review: The paper provides variance reduction techniques for GCN training. When training a GCN it is common to sample nodes as in SGD, but also subsample the nodes’ neighbors, due to computational reasons. The entire mechanism introduces both bias and variance to the gradient estimation. The authors decompose the gradient estimate into its variance and bias error, allowing them to apply more targeted variance (and bias) reduction techniques.

The results and improvement over existing GCN methods seem to be solid. The main weakness of the paper is its novelty. As pointed out in the reviews the techniques seem to be quite close to papers [5],[11] (referring to the authors posted list).
It therefore boils down to the question of whether the authors simply applied existing techniques, achieving a better implementation than previous art, or did they develop a truly new algorithm that will encourage further research and deepen the understanding of GCNs. Given the decisive opinions of reviewers 1 and 4, that remained after taking the response into account, I tend to believe that the improvement provided here is either too incremental or not stated in a crisp enough manner in order to be published in its current form

Decision: Reject