Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: -------------
Summary
-------------

This paper presents analysis how the batch size in GNNs would affect the tradeoff between accuracy and computation cost. The paper defines the gradient estimator for minibatches constructed by layer-wise random node sampling. Then the authors analyze the variance of such estimator in order to guide the hyperparameter tuning on batch size. I think it is an interesting idea to quantify the accuracy-computation tradeoff with the metric "pseudo precision rate", $\rho$ (as mentioned in the paper, $\rho$ is the normalized efficiency metric (Owens, 2013)). The authors calculate the bound for $\rho$ and then derive the optimal batch size based on full graph size and average degree. Experiments on three state-of-the-art GNN training methods verify that 1). the batch size for GNNs needs to be larger than that of other models on I.I.D. data; 2). there exists an optimal batch size to balance the accuracy and training cost. 

------
Pros
------

+ Training GNNs to achieve scalability and accuracy at the same time is a relatively underexplored problem. But it is indeed very important. The authors made a good attempt to unify both accuracy and scalability under the pseudo precision rate metric $\rho$. 
+ The paper is well-organized, and it is easy to grab the main idea. 
+ Extensive experiments have been conducted. These help the readers better understand the training behavior of existing state-of-the-art methods. 

-------
Cons
-------

Since the theme of the paper is to guide the tuning of existing methods rather than proposing new methods, it becomes more critical that the analysis is performed rigidly and under realistic assumptions. However, after reading the derivations carefully, I have the following concerns:
- Some fundamental assumptions on sampling are inconsistent with the setup of the state-of-the-art training methods. All of the analysis is based on the process of independent and uniform random sampling in each GNN layer (i.e., to construct the set $S_1$ and $S_2$). Unfortunately, none of the existing training methods follow such setup. For example, for GraphSAINT and Cluster-GCN, $S_1$ and $S_2$ are strongly dependent on each other as $S_1 = S_2$. For FastGCN, the sampling in each layer is not uniformly at random due to importance sampling. For other layer-sampling methods (e.g., GraphSAGE, VR-GCN, AS-GCN, LADIES), $S_1$ and $S_2$ are also not independent since the sampling of $S_2$ follows the inter-layer connections defined by $S_1$. 
    * If we remove such unrealistic assumptions on sampling, the derivations in the paper would fail. For example, if $S_1$ and $S_2$ are no longer independent, $\xi$ would have non-zero bias and then such definition of the estimator is questionable. The bias can be seen from the last equation of page 11 in the Appendix: without independence, $\mathbb{E}_{S_1, S_2}[...]$ is not equal to the product of $\mathbb{E}S_1$ and $\mathbb{E}S_2$. Assumption A.1 is also questionable since nodes in $S$ may have strong correlation depending on the subgraph sampler. Similarly, the derivation on the variance (page 12) would not hold without assuming independent $S_1$ and $S_2$. 
    * Following the setup of this paper, I think independent and uniform sampling of each $S$ may likely cause difficulty in GNN learning. Suppose the max sampling size is $O(1)$, due to the fixed GPU memory capacity. Now with the growth of the full graph size $n$ and under independent, uniform sampling, the probability that $S_1$ and $S_2$ have any connection will vanish. i.e., $1_{N\cap S_2\neq \emptyset}$  in the $\xi$ definition will almost always equal to 0 with a large enough $n$. The issue of unconnected minibatch will be much worse if we consider the sampling across multiple layers. 
    * Therefore, the analysis on variance gives limited practical insights due to those assumptions. 
- Some important assumptions on the graph property are either unrealistic or not well-justified. The derivation of Propsition 4.1 relies on $m/n >\log n / d_{min}$. In other words, $d_{min} > (n/m)\log n$. Let's consider a median-scale graph in OGB with $10^6$ nodes. Suppose the batch size is $100$K (which is already much larger than the one tried in this paper). Then $d_{min}$ is already in the order of $10^2$ --- minimum degree is of similar scale to the avarage degree. Therefore, such assumption is unrealistic, especially considering the power-law. Assumption A.1 is not well-justified. A.1 requires weak correlation between sampled nodes. Such weak correlation probably does not hold for many well-performing graph sampling algorithms (e.g., random walk), where nodes in $S$ should be "close" to each other. 
- The conclusion from the main analysis (Proposition 4.1) is confusing. It is stated that $\delta$ is monotonically decreasing with batch size $m$. It seems to imply that the larger the batch size, the better the metric $\rho$ (such understanding is also verified by the case study of Corollary 4.2). So shouldn't we simply increase the batch size until we reach the GPU memory limit? Why concluding on $n/\overline{d}$ instead?
- The bound on $\rho$ is too loose to derive the practical batch size value of $n/\overline{d}$. The process to derive the suggest value $n/\overline{d}$ doesn't seem convincing. By looking at the bound $1/(\phi(1+\delta))$, the authors suggest that setting the coefficient $1/(1+\delta)$ may be good enough. However,
    * $\phi$ itself is not a constant. $\phi(1+\delta)$ jointly depend on $m$. Then we cannot simply treat $1/(1+\delta)$ as an independent coefficient. 
    * Even though we can set the coefficient $1/(1+\delta)$ to be $1/2$, and thus make $\delta=1$, it is still far away from concluding $m=n/\overline{d}$. Recall that in Corollary 4.2, $m=O(n/d\delta)$ is only describing the order. How can we simply ignore the constants hidden by the $O(..)$ notation? Especially, the derivation in Appendix seems to depend on multiple constants which could be of arbitrary scale. 

Minor concern:

The fact that larger batch size may help with GNN accuracy has already been observed (e.g., check the batch size configuration for the OGB results). The intuitive explanation from variance perspective has also been made in the literature. For example, GraphSAINT idenfieis the sparse connection issue within minibatches and performs additional experiments to study the effect of large batch sizes. Therefore, bringing up the issue of large batch training is not enough to be considered as a major contribution. The much more important contribution of this paper should lie in the analysis portion. 


---------------------------------------
Recommendation: Rejection
---------------------------------------

Considering the above, I feel that this paper makes limited contribution to deepen the understanding on the effect of batch size for GNNs. 

--------------
Questions
--------------

Detailed concerns are listed in the "Cons" section. Below is a short summary:
1. Please justify the assumptions on sampling.
2. Please justify the assumptions on the graph property.
3. Please clarify how to derive the $n/\overline{d}$ value. 
review_title: Good motivation for accuracy-computation tradeoff; analysis not convincing enough

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: The goal of the paper is to propose a principled strategy to select batch size for training graph neural networks with SGD. Training (using GNNs) real world graphs with a large number of nodes/ edges may not always fit in CPU /GPU memory, hence constructing mini-batches is important. Specifically, the authors propose a strategy for the task of node classification - where they aim to select batch size based on number of nodes and average degree in a graph and show that their proposed guidelines have benefits in terms of training time as well as accuracy. The authors propose a metric - pseudo precision rate which is dependent on the computation cost and the variance of the gradients and derive a lower bound for this metric which factors into account the batch size.

Pros:
1. The idea to study the effect on batch sizes for non -i.i.d data is interesting
2. Authors provide results on 3 large number of datasets  for 3 scalable GNNs

Concerns:
1. (Learning rate) - There have been lots of work which understand the connections between learning rates and batch sizes - their impacts on rate of convergence, local minima reached, variance in the gradients etc. In this work the authors use the same fixed learning rate for all batch sizes (which goes against many previous works without justification for the same).
2. (Confidence Intervals/ number of epochs) - The values presented in Tables 3-6 do not have any confidence intervals - with values which are so close of each other - it is crucial to have confidence interval. Also the authors use a fixed number of epochs for each of the batch sizes to compute training time - this is problematic  - the training time should only be considered up to the point it converges (for e.g. with early stopping).
3. (Clarity) - Section 3.2 What is $S_i^l$, $q^l$ - mathematically? - This is not clear from the text in the paras (vague) - Can you express S in terms of the k-hop neighborhood, is division by $q^l(i)$ well defined in equation (4), etc. Paragraph above - def 4.1 - " Proxy estimator does not adequately..." - what do you mean by this statement - the word 'layers' refers to what? Please see other concerns below as well
4. (Estimator and bounds) - From the text, it is unclear how the estimator in definition 4.1 is connected with the variance of the estimator and the computation costs used in definition in 4.2 . This flows into the proposition 4.1 and the corollary as well. Many of the computations in def 4.1 can be parallelized - so a clear definition of the variance of the estimator and computation costs are required.
5. Effect of distributed frameworks - another aspect to consider here - which is crucial to performance is the ability of GNN tools such as DGL an Pytorch-geometric to perform distributed training at scale (model parallel approaches) - this impacts the batch size as well.


Other concerns:
1. Please don't include very generic statements which don't any much value to the reader - like "SGD performs well when mini-batch size is small" (abstract and second para of intro) - this is dependent on the task, whether the data is i.i.d etc and also too small minibatches is bad as well. Early graph neural networks clearly showed that larger batch sizes for SGD training was always better (with full batch gradient descent achieving fast convergence as well as convergence to local minima which achieved highest test accuracy).
2. Typo - para 1 -  intro  - minibatch
3.  3rd para - (i) reduced instead of reduce (ii) training may take instead of training take
4. Section 3.1 - classify the labels of nodes
5. Proposition 4.1 - what is d?? you have defined d_min, but nothing about 

If made more clear and the concerns are addressed, I will be happy to improve my score.
review_title: Review of On Batch-size Selection for Stochastic Training for Graph Neural Networks

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors study an important problem on how the choice of batch size (i.e., the number of sampled nodes) affects the training efficiency and accuracy of graph neural networks (GNN). Focusing on the layer-wise and graph-wise sampling for training, the authors theoretically characterize the impact of batch sizes on the efficiency (measured by a product of computation time and variance) of the algorithms. Especially, in order to better capture the randomness of two-consecutive layers, the authors investigate a different estimator rather than the one truly used in the training of GNN. The resulting theory suggests a choice of the batch size to be n/\hat d, where n is the total number of nodes and \hat d is the average degree of the graph. The authors empirically show that compared to the training of NN, the training of GNN requires a much larger batch size to achieve an efficient training. In addition, the experiments show that the best batch size is much smaller than the full batch that is widely adopted in the training of GNN.

Strength: 

   (1) This paper studies an interesting and important problem on the selection of batch size for GNN training. The results may be useful for practitioners to accelerate the training for GNN depending on different settings. 

Weakness:

  (1) This paper is not well written and some parts can be clearer. For example, from my reading, the layer-wise sampling plays an important role in the analysis. However, It is not directly clear to me about the derivation of equation (4). As a result, I do not get the point of your estimator design in Definition 4.1. Specifically, more intuitions and explanations on the design of your theoretical estimator in Definition 4.1 should be given, and clarify whether this estimator can truly capture the training of GNN, e.g., whether it will change the convergence of SGD during the training. 

  (2) The theoretical results seem not to well support the empirical results. For example, the theoretical results suggest some optimal batch sizes given by theory, e.g., 4K for Pubmed, 2k for Reddit, 12k for Ogbn-arxiv, 48k for Ogbn-products. However, from the experiments in Tables 3,4,5,6 suggest that the best choices are 512-1k for Pubmed, 4k-8k for Reddit, 8k for Ogbn-arxiv, 8k-32k for Ogbn-products. There seem to be some big gaps between the theory and the experiments. 

  (3)	It seems to me that the analysis only studies the two-consecutive layers. However, in practice, GNN often contains far more than two layers. The authors should discuss whether such analysis is still applicable to larger GNN or provide a corollary to present such results. 

  (4)	Assumption  A.1 is restrictive. It requires that the intersection of the neighborhoods of any two points has nearly no correlation. In practice, this assumption is hard to satisfy because the neighborhoods of points always contain big overlaps. I think this assumption is made in order to derive or simplify the analysis. The authors may try another more reasonable and practical assumption or show why this assumption is necessary and practical in some settings. 

Although I think studying the batch size selection for GNN is very important, I am not convinced or excited by the results in this paper. For me, it is more interesting to provide a better and  comprehensive theoretical result  beyond the simplified case in this paper, or develop a new batch size selection scheme (e.g., adaptation) to accelerate the training of GNN. However, I do not get such points from the current version. For these reasons, I tend to reject this paper. However, since I am not an expert in this area, i.e., GNN training, I am open to change my mind based on other reviews and the authors’ response. 

--------------------------------------------------------------------------------------------------------------------------
Post rebuttal:

I first want to thank the authors for their response to my concerns. My concerns have been partially addressed, but some concerns still exist. For example, I am not clear about whether the simplified theoretical estimator in Definition 4.1 really captures the training of GNN. To achieve this goal, some simulations or theoretical justifications should be provided. In addition, the analysis fails to motivate some useful and meaningful algorithmic designs for GNN acceleration, which I believe is much more interesting. For these reasons, I tend to keep my score unchanged. 

However, I  think the authors take a very good start in studying the impact of batch sizes for GNN training, and I encourage the authors to further enhance their papers from both the theoretical and practical perspectives. For example, it would be much better to explore some new designs for accelerating GNN training based on the developed analysis (e.g., batch size adaptation). Theoretically, the authors can study a more practical and general estimator (perhaps beyond two layers). With these improvements, I believe this can be a very good paper to be published in top venues. 
review_title: Official Blind Review #4

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:

In this paper, the authors studied the problem of batch size selection in graph neural networks. Since scaling up the batch size is the most efficient way to increase parallelism, this topic seems to be very important for making full use of modern computer architectures like GPUs or TPUs. The authors conduct a detailed analysis on the impact of batch size in graph neural networks. After a series of discussions, the authors conclude that an ideal batch size should be n/d where n is the total number of nodes and d is the average node degree. The authors suggested that this batch size should be able to give the best convergence/generalization performance for graph neural networks. Overall, the paper is properly written. In terms of presentation, the structure is clear and the idea is easy to understand.

Interesting point:

As suggested by many previous papers, large-batch training typically suffers a generalization problem found in [1]. However, the results in this paper (e.g. Tables 3-6) show that large-batch training generalizes very well for graph neural networks. For example, a batch size of 32K may make the training crash by using stochastic gradient descent for convolutional neural networks. That seems to be interesting, the authors may need to explain the reason behind that.

Main concern:

In this paper, the authors did not provide any algorithmic contributions. As mentioned in the paper, the only contribution of this paper is a theoretical analysis. The authors conduct some experiments to support their theoretical analysis. To be honest, I do not find enough interesting points in the theoretical analysis. Considering the experiments are fairly easy to be conducted, the contribution of this paper seems to be incremental.

Questions:

(1) In Tables 3-6, did the authors fix the number of epochs when they change the batch size?

(2) Can the authors provide more information on optimizers and hyper-parameters?

(3) The horizontal axis of Figure 1 is “training time”, can the authors add another figure with the horizontal axis as “epochs”.

Minor concerns:

(1) In the introduction section, the authors claimed “The maximum size of the minibatch is limited by the available memory”. That’s not true. If the authors have out-of-memory issues with limited hardware resources, please check [2]. If the hardware can run with a batch size of 1, it can run whatever batch size.

(2) The lines in Figure 1 are hard to tell from each other. The authors may consider adding different markers to different lines.

(3) The evaluated datasets/models seem to be small. Even though the authors only use one GPU, they managed to train almost all of them within one hour.

[1] Keskar, Nitish Shirish, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. "On large-batch training for deep learning: Generalization gap and sharp minima." arXiv preprint arXiv:1609.04836 (2016).

[2] https://discuss.pytorch.org/t/how-to-implement-accumulated-gradient/3822

review_title: the contribution of this paper seems to be minor

Meta-review: All the reviewers find the problem studied in the interesting. However all of them raise concerns about the assumptions made in the paper for the analysis. Reviewers find the assumptions very limiting and far from the practical training of GNNs. Improving the analysis by relaxing the assumptions further can significantly help the paper. 
Decision: Reject