Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors proposed a novel subgraph-wise sampling method, Local Message Compensation(LMC), to accelerate the training of GNNs on large-scale graphs. They mainly focus on solving the neighbor explosion problem. Their main concern is finding a solution to the neighbor explosion issue. I think their research has a significant impact on the advancement of GNNs.
strength_and_weaknesses: Strength:
(1) Their approach helps to avoid the neighbor explosion problem to a certain extent.
(2) The convergence of their method is provable.

Weaknesses:
1. one typo is that in table 1 GraphSAINT's 97.0 reaches the best.
2. It seems to me that the authors claim that their method is more efficient than other methods, which means the "proportion of reserved messages (%) in forward and backward passes" based on their response, but in terms of memory in Table 2, for example, 1892 for LMC is about 2 times more than 1193 for CLUSTER and 557 is about 1.3 times more than 424, which may confuse others in terms of memory efficiency. It would be clearer to modify Table 2 and add "proportion of reserved messages (%) in forward and backward passes" to it.
clarity,_quality,_novelty_and_reproducibility: This manuscript is excellently written. Their method is clearly explained in the notations, equations, and descriptions. Their novelties include a new backward SGD technique and theoretical guarantees.
summary_of_the_review: Even though their work aids in the development of GNNs, these are insufficient for being strongly accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new subgraph sampling method: Local Message Compensation (LMC) for speeding up GNNs training. The general subgraph sampling method will dscard information outside the mini-batches, and thus brings in performance degradation and slow convergence. LMC deals with this issue by retrieving the discarded information in backward passes based on a message passing formulation of backward passes. This paper also provides convergence analysis. The experiment is promising and achieves good convergence speed and accuracy.  
strength_and_weaknesses: Strength:

1: A reasonable method for retrieval information outside the mini-batches. 
2: Providing convergence analysis. 
2: Comprehensive experiments show fast convergence.

Weakness:

1) One thing I am confused is that do you need to maintain the all the node embeddings for all the layers? If that is the case, what if the number of layer is too large, would it be OOM issue? Traditional subgraph sampling methods such as ClusterGCN does not need to main such embeddings for all the layers, as it is computed on-the-fly, and thus more memory efficient.

2) how is the subgraph sampling method playing a role during the convergence? For example, what if using random partition vs metis?

3) how is the per epoch time comparing with different methods? The result presented in the paper is mostly on total training time  (or total epochs ) vs accuracy or loss. It would interesting to see per epoch time as well. As I feel seems there are more variables needing to be updated from traditional subgraph sampling method, LMC will need more time per epoch.

4) how the proposed method compared with GraphFM, which seems quite similar to the proposed method.

5) also some ablation over the combination coefficients beta_i.


clarity,_quality,_novelty_and_reproducibility: The paper is easy to understand and seems novel.
summary_of_the_review: The paper is in easy to understand and the proposed method is making sense and achieves good convergence. I am mostly concerning about the memory usage and space to maintain all the layers historical information.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this work, the authors proposed a subgraph sampling training technique to solve the neighbor-exploding issues commonly seen in GNN training. The proposed methods named Local Message Compensation is claimed to debias the mini-batch gradient in a one-shot sampling setting hence accelerate convergence of training. Both theoretical and experimental results shows the efficacy of the proposed method. 

strength_and_weaknesses: Pros: 
- The paper is well-written with wide coverage of related works. 
- The deviate of backward SGD is intuitive and make it easy to follow the further approximation and compensation. 
- The claimed theorems and illustration in Figure 1 make the difference between LMC and other methods straightforward. 
- Space and time complexity analysis in Appendix adds more concrete supports to the efficiency of LMC
- The uniform sampling and variance reduction technique using neighbors’ historic inform resemble some of the accelerated SGD method, and the authors provided theoretical rate of convergence in a similar way which is good to compare the ideal performance. 
- Complete and detailed experiments showing the convergence and efficiency of proposed method.  

Cons: 
- In equation (7), on the left hand side shouldn’t the gradient for \theta^l depends on V_j^{l + 1} instead of V_j^l  (same for u_{\theta}) ? 
- Does the classification performance of GAS and LMC always stay at the same level? What if you change a different base GNN (maybe less expressive and prone to error by gradient variance)? 
 - Please add indicator (such as different font, color, etc) in the tables so that its easier to find the winner. 
- Is the method universally adapted? What is the performance when applying to small/medium size graph?
clarity,_quality,_novelty_and_reproducibility: The paper is easy to understand with clear definition and intuitive illustrations. The novelty comes mostly from the historic compensation part but the authors shows the necessity in ablation studies. Results should be easily reproduced once they publish the code. 
summary_of_the_review: This work is a step forward from FAS. Though the two shares some similarity, the authors shown the improvements with both theoretical guarantee and detailed experiments. Overall I would recommend the paper to be accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This research proposes a subgraph sampling method(LMC) with provable convergence for graph neural networks. Training Graph neural networks suffer from neighbor explosion problems. Subgraph sampling methods apply to a wide range of GNN architectures by directly running GNNs on the subgraphs constructed by the sampled mini-batches and showed great empirical success in prior works, while inaccurate mini-batch gradients hurt the accuracy and performance of GNNs. The key idea of LMC is effective compensation in backward and forward passes, which computes accurate mini-batch gradients and thus accelerate convergence.
strength_and_weaknesses: Strength:
1. Key idea of effective compensation is great, and they explain their idea clearly.
2. First subgraph sampling method with provable convergence for graph neural networks. Their theoretical analysis shows that mini-batch gradients are unbiased and their algorithm can converge to the stationary point of GNNs.
3. Numeric experiments are sufficient, it's worth mentioning that the experiments on compensation terms are great.

Weaknesses:
1. Some typo, denote the j-th columns of A by $A_j$ not $A_i$, forward not froward.
2. More explanations are needed for the difference of GAS and LMC, why more information keeping can get the algorithm more robust the the graph size. On some datasets, GAS performs better, why?   
clarity,_quality,_novelty_and_reproducibility: The quality of the whole research is good especially since they explain some details for their numeric experiment.  
summary_of_the_review: This research proposes a subgraph sampling method(LMC) with provable convergence for graph neural networks.  The key idea of LMC is effective compensation in backward and forward passes, which computes accurate mini-batch gradients and thus accelerate convergence. Numeric experiments and theoretical analysis are great, while more explanations are needed for the difference and key development with the prior works.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors introduce a new subgraph sampling method, Local Message Compensation (LMC), to efficiently train GNN. Interestingly this model directly address one of the main challenges in training GNN the well-known neighbor explosion problem.

The paper is well-written and the main idea behind the result are very well-explained. The main idea behind the proposed technique is to debias the mini-batch gradient in a one-shot sampling setting to accelerate convergence of training. The authors show that their method works well both theoretically than experimentally.

Overall, the paper is a nice contribution to ICLR and I suggest to accept it.
justification_for_why_not_higher_score: I think that the paper is interesting but it is not solving a problem that is central enough to be an oral
justification_for_why_not_lower_score: The paper contains both interesting experimental and theoretical insights and it is well-written.
Decision: Accept: notable-top-25%