Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a distributed extension of GNNAutoScale (DIGEST) and proposes an asynchronous representation update mechanism (DIGEST-A) to reduce communication overhead for node embedding updates. Theoretical analyses such as forward error bound and convergence analysis are provided. Experiments show promising speedup in training time. 
strength_and_weaknesses: # Strength 

1. The paper proposes a distributed GNN training framework that synergies the benefits of partition-based and propagation-based methods. The motivation is clearly demonstrated and the approach is valid.

2. Theoretical analyses demonstrate the impact of embedding error and staleness bound on prediction error and convergence behavior. This helps justify the impact of the staleness (but concerns are discussed below).

3. The experiments validate the effectiveness of the proposed algorithm, and the improvement over baselines is significant.

# Weakness

1. The major idea of the paper follows GNNAutoScale, and the asynchronous update is inspired by extensive research on asynchronous distributed optimization. The theoretical analyses and assumptions closely follow PipeGNN [1]. Overall, the originality is a bit weak.

2. The theoretical statements of the paper need further clarification. Assumptions being made need to be clearly clarified in the main theorem. For instance, there are lots of assumptions being made in the proof but they are never mentioned in Theorem 2 and Theorem 3. Furthermore, the constants in the Theorem need to be explained, such as $E, M, P(\eta)$ in Theorem 2 and 3.

3. There are multiple concerns with the theoretical analysis. 

(1) First, the error presented in Theorem 1 can be potentially very large, which grows exponentially with the number of layers and has a bad dependency on the maximum node degree. A detailed empirical study of this approximation error will be helpful to clarify the impact of the error.

(2) Second, the backward propagation process for gradient computation neglects the gradient computation through the out-subgraph stale representations. In other words, each local model considers the node representation from other machines to be constant. The paper and the corresponding theorem do not take this into account. In fact, this will invalidate one important step in the theoretical proof Eq. (34): $\nabla L(W^t) = 1/M \sum_1^M \nabla L_m(W_m^t)$. This might cause major flaws in the proof and need to be addressed.

4. The algorithm is only compared with 2 baselines that do not represent the state-of-art algorithms. It is suggested to also compare with algorithms such as PipeGNN and sampling-based methods such as GNNAutoScale.

[1] PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication
clarity,_quality,_novelty_and_reproducibility: # Clarity

The theoretical results of the paper need further revisions. Assumptions being made need to be clearly clarified in the main theorem. For instance, there are lots of assumptions being made in the proof but never mentioned in Theorem 2 and Theorem 3. Furthermore, the constants in the Theorem need to be explained, such as $E, M, P(\eta)$ in Theorem 2 and 3.

# Originality

The major idea of the paper follows GNNAutoScale, and the asynchronous update is inspired by extensive research on asynchronous distributed optimization. The theoretical analyses and assumptions closely follow PipeGNN [1]. Overall, the originality is not strong.





summary_of_the_review: The paper introduces a simple and practical distributed GNN framework. Theoretical analyses are presented but concerns need to be addressed. Experiments demonstrate significant speedup but more baselines will be beneficial.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the problem of distributed training of Graph Neural Networks (GNNs) over large-scale graphs. The authors proposed a framework called Distributed Graph Representation Synchronization (DIGEST), which leverages the stale representation of neighbors from other subgraphs to eliminate the information loss caused by dropped edges in partition-based methods and avoid communication overhead as in propagation-based methods. Specifically, the stale representations are stored in the central server and each subgraph communicate with the server to pull / push the stale representations during training. From system design perspective, the authors proposed both synchronous and asynchronous versions of DIGEST to further handle the straggler issue. Also, a key-value storage (KVS) design is introduced to implement the shared memory for the stale representations for better efficiency. Extensive theoretical analyses are provided, including convergence guarantee and the error bound of approximated gradients. Experimental results on several large-scale real-world graph datasets showed great performance and speedup of the proposed method compared with other distributed GNN methods.	
strength_and_weaknesses: Strengths:

1.	As far as I know, the originality of this paper is good. Considering stale representation under distributed training of GNNs is interesting and important.

2.	The proposed method is both theoretically and technically sound to me.

3.	This paper makes non-trivial contribution on system design and implementation, including both synchronous and asynchronous variants of the proposed method, and the key-value storage (KVS) for stale representations.

4.	The authors provided very extensive and novel theoretical analyses over the proposed methods. Convergence guarantees for both versions of DIGEST and the error bound of the approximated gradients due to the staleness are given with rigorous proof.

5.	The empirical results show a significant speedup of the proposed methods compared with other state-of-the-art distributed GNN methods on large real-world graph datasets.

Weaknesses:

1.	The authors are encouraged to better discuss the motivations and technical details of the asynchronous version of DIGEST. Also, how is the algorithm of asynchronous DIGEST different from that of synchronous one as shown in Algorithm 1 in appendix?

2.	Since graph partition algorithms can play an important role in distributed partition-based training of GNNs, I am curious how does different partition affect the performance of DIGEST? 

clarity,_quality,_novelty_and_reproducibility: Quality: The proposed method is both theoretically and empirically sound to me. Extensive theoretical analyses are shown for convergence guarantee and stale gradients error bound.  Empirical studies are comprehensive and shows great speedup and performance of the proposed method. 

Clarity: In general, this paper is well-written with great presentation. Also, I found this paper quite easy to follow.

Originality: As far as I know, this paper makes non-trivial contributions for distributed partition-parallel training of GNNs with stale representation, which could handle information loss and communication overhead simultaneously. Novel system design and extensive theoretical analyses further round up the good work.

summary_of_the_review: In summary, this paper delivered a non-trivial and meaningful exploration of distributed partition-parallel training of GNNs. Both system design and theoretical analyses are novel and interesting. Empirical results are provided with great performance. Also, the paper presentation is good to me. Hence, I would recommend accept of this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper explores the trade-off between partition-based and propagation-based distributed training methods, taking advantage of both low communication overhead and no information loss. To do this, it saves a subgraph on each device and allows each device utilizes the stale representation of the neighbors of the subgraph saved on other devices. The results show more than 20 times speedup compared with the state-of-the-art distributed GNN training frameworks. This paper also proves the convergence of the proposed method. 
strength_and_weaknesses: ## Strength:
1. The GNN training framework proposed in this paper drops no edges while avoiding communication overhead, showing both good performances of accuracy and speedup.

2. The periodic stale representation synchronization technique using periodically synchronous pull/push operations for the representations is novel and able to approximate the representations of nodes.

3. The authors provide detailed proof of performance and convergence for both synchronous and asynchronous versions.

## Weakness:
1. Does KVS stores the representations of all the nodes on a graph? It would be better if the authors could provide the memory consumption of different methods. If the memory consumption of DIGEST is large, it may be hard for it to handle as large graphs as both partition-based and propagation-based methods.

2. The experiments should use larger datasets, such as ogbn-papers100M and mag-240. The datasets used in this paper can be easily saved on a single machine. (The data size of the largest dataset ogbn-products is only 2.8G.) 
clarity,_quality,_novelty_and_reproducibility: The paper is well written. The idea is new to me. 
summary_of_the_review: The paper is well written. The proposed technique is intuitive, but not very impressive.  The experiments are insufficient.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a method to achieve a trade-off between information loss(partition-based) and communication cost(propagation-based) distributed GNN training. The key design is to synchronize representation to an in-memory KV store periodically with pipelined IO, so that the GNN training is aware of the full graph and without frequent communication overhead.
strength_and_weaknesses: Strengths:
1. The distributed training of GNNs is an important problem. The motivation of this paper is clear and the proposed method is simple yet effective.
2. The experiments show the speedup and scalability are good.
3. This paper gives theoretical bound and convergence analysis of the proposed training method.

Concerns:
1. A question is, if the I/O is pipelined and hidden as in Figure 2, why is it still needed to sync **periodically**(as we should be able to sync in each epoch without much addition time cost)? And as shown in Figure 6, is there any way to determine or suggest the best synchronization frequency?
2. This method proposed in this paper shows nice scalability in a single-machine multi-GPU environment. It could be more interesting if it could be extended to a multi-machines environment with nice scalability.
clarity,_quality,_novelty_and_reproducibility: This paper presents a distributed GNN training framework very clearly. Both the theoretical analysis and the experiments are convincing. Though there are some works, e.g., [1], that share similar ideas to train GNNs with stale representation, this paper has its contribution as a system implementation with stale representation synchronization and pipelined I/O.

[1] Stochastic Training of Graph Convolutional Networks with Variance Reduction, Jianfei Chen, Jun Zhu, Le Song, ICML 2018

summary_of_the_review: This paper proposes a distributed GNN training framework by balancing partition-based and propagation-based distributed GNN training. The key designs are periodic stale representation synchronization with pipelined I/O. The results are convincing and I think the merits outweigh the flaws.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper introduces a new technique for distributed training for GNN. The main idea behind the paper is to combine the "partition-based" and the "propagation-based" approach to obtain a system that is scalable and accurate at the same time.

The paper presents some interesting ideas and some nice experimental results but it has few fundamental drawbacks that should be addressed before publication.

First, the experimental analysis is nice but not fully convincing. After rebuttal, the paper presents a single experiment on a large size dataset. This is not sufficient for a paper that introduces new scalable systems. Multiple large datasets should be analyzed and an in depth scalability analysis on different architecture and on graph of different size should be presented.

Second, the paper should better clarify the novelty in comparison with previous work and should improve the clarity of the theoretical results.

Overall, the paper contains some interesting ideas but in the current state it does not meet the ICLR acceptance bar.
justification_for_why_not_higher_score: The paper is present a new system for scaling GNN and it run a single experiment(in rebuttal phase) on a large graph. A more in depth experimental analysis of scalability is needed before acceptance.
Decision: Reject