DyGNeX : Efficient Distributed Training of Dynamic Graph Neural Networks with Cross-Time-Window Scheduling

Thank you for your valuable review! Your insights have been instrumental in improving the quality of our paper, and we have uploaded a revised version based on your feedback. The revised sections have been highlighted in brickred for clarity.

W1&W2. Lacks challenge & new insights or contributions

Ensuring load balancing across all nodes while minimizing inter-node communication is a highly important issue in distributed DGNN training. We show that this scheduling problem is NP-hard. Efficiently (within seconds) obtaining approximate optimal solutions for this problem in various scenarios is challenging. DyGNeX-G and DyGNeX-L complement each other in addressing this issue under different scenarios.

Although there are existing solutions in this field, we believe DyGNeX offers unique insights&contributions:

1. Outstanding performance improvement: DyGNeX-G and DyGNeX-L achieve an average performance improvement of 24% and 28%, respectively, compared to the state-of-the-art work BLAD.
2. Complementary strategies: DyGNeX-G and DyGNeX-L complement each other for different scenarios, providing stable and efficient solutions.
3. Agnostic to DTDGs and DGNNs: It is agnostic to the characteristics of DTDGs and DGNNs, making it highly extensible to virtually all DTDGs and DGNNs.
4. Simplicity and extensibility: It is simple, efficient, and plug-and-play, with the group strategy decoupled from the training system, enabling seamless integration with other training frameworks.

---

W2. Load balancing has been studied extensively in many graph algorithm settings even for DGNN training.

Your point is correct. There are quite a number of studies on load balancing for GNNs and DGNNs. However, the load balancing methods for traditional distributed GNN training, such as graph partitioning, cannot be directly applied to DGNN scenarios. This is because the optimization objectives in DGNN scenarios are not consistent with those of GNNs. For example, data reuse between different snapshots needs to be taken into account. Currently, the research on load balance for distributed DGNN training is insufficient. In the not-open source work DGC (SIGMOD24), it is still impossible to completely eliminate the communication tasks among GPUs other than gradient synchronization. Therefore, we believe that the topic of load balance in distributed DGNN training is well worth exploring. Meanwhile, the solution we proposed, DyGNeX, is non-trivial.

---

W3. Focuses on system-level tradeoffs, not ML components

Thank you for your suggestion; we will take it into consideration. However, the Primary Area we chose for this paper is "infrastructure, software libraries, hardware, systems, etc." DyGNeX can be viewed both as a software library that provides the group strategy and as a complete training system, which aligns well with the requirements of this Primary Area.

Moreover, in ICLR 2024, there are similar works focusing on system-level contributions that have been accepted, such as:

• Qi et al. (2024). Zero Bubble (Almost) Pipeline Parallelism. Link
  • This study introduces a novel scheduling strategy that achieves zero pipeline bubbles in synchronous training by splitting the backward computation into two parts, thereby significantly enhancing the efficiency of large-scale distributed training systems.
• Mei et al. (2024). SRL: Scaling Distributed Reinforcement Learning to Over Ten Thousand Cores. Link
  • This paper presents SRL, a system designed to scale distributed reinforcement learning by splitting environment simulation, policy inference, and training into separate roles, making it easier to parallelize and balance resources across different cluster setups.

Therefore, we believe that DyGNeX fits well within the area of infrastructure, software libraries, hardware, systems, etc.

---

W4. Evaluation with larger graphs are needed

The goal of DyGNeX is to leverage data parallelism to accelerate training, rather than to handle larger graphs. Admittedly, we consider handling larger graphs an important issue and a direction for future research, but it is beyond the scope of DyGNeX.

Moreover, in most real-world scenarios, a snapshot group can easily fit into GPU memory, leaving plenty of memory to spare. DyGNeX already covers the vast majority of scenarios, and these scenarios are of significant importance.

We hope our answers will address your concerns.

Thank you for your valuable review! Your insights have been instrumental in improving the quality of our paper, and we have uploaded a revised version based on your feedback. The revised sections have been highlighted in brickred for clarity.

W1.1 Lack of clarity and visual aids in Section 2

Based on your suggestions, we have made the following revisions to the paper. In Section 2, we revised the description of the workflow of distributed training for DGNNs using equations and explained the communication types in Table 1 along with their underlying reasons. Additionally, we added Figure 6 in the appendix to illustrate the entire training pipeline. Regarding the dataset partition strategy, we included Figures 7, 8, and 9 in the appendix to visually highlight the differences between the three strategies. Furthermore, in the “Dilemma in Distributed Training of DGNNs” section, we emphasized the current challenge: ensuring load balancing across all nodes while minimizing inter-node communication. Lastly, our contributions are clearly detailed in the final paragraph of the introduction.

---

W1.2 The difference between other components and previous work BLAD

Our system comprises three main components: the profiler, group scheduler, and trainer. The profiler in DyGNeX aligns closely with BLAD, as the profiling methodologies are largely consistent across most works. The group scheduler is the core component enabling DyGNeX to achieve load balancing by computing an optimized group strategy. This component sets DyGNeX apart from other DGNN training systems. The trainer in DyGNeX also diverges from BLAD. In BLAD, each GPU is assigned two processes, which collaboratively train different snapshots within the same snapshot group. One process handles computations for the first half of the snapshot group, while the other processes the second half, forming a two-stage pipeline. By contrast, DyGNeX executes two snapshot groups sequentially within the same process, streamlining execution as detailed in line 196.

---

W1.3 Section 4.3 is hard to understand where a lot of symbols are not defined or explained in advance

We added Table 2 in Section 4 to explain the frequently used notations for better reader understanding. Additionally, we modified some variable names to enhance readability.

---

W2. How the scheduling algorithm affects training on other datasets

We present the test accuracy on the Products and Reddit datasets in Figure 3, along with the training accuracy and loss in Figures 11 and 12.It can be observed that in the vast majority of scenarios, there is no difference in accuracy between DyGNeX and PSG. This indicates that DyGNeX’s approach does not have a significant impact on training quality.

---

W3. The need for a clearer definition of PSG and a more detailed comparison of the differences between PSG, DyGNeX, and BLAD

Based on your suggestion, we have provided a more detailed explanation of the differences between PSG, BLAD, and DyGNeX in the baseline part of Section 5.

In PSG, each GPU training a single snapshot group. BLAD utilizes a two-stage pipeline to collaboratively train two consecutive snapshot groups. In contrast, DyGNeX-G and DyGNeX-L execute two scheduled groups sequentially.

We hope our answers will address your concerns.

Thank you for your valuable review! Your insights have been instrumental in improving the quality of our paper, and we have uploaded a revised version based on your feedback. The revised sections have been highlighted in brickred for clarity.

W1&Q2. Profiling cost

In actual training, the first few epochs can be used for profiling. We only need to adjust the group strategy after the profiling epochs. The training results from the profiling epochs are not wasted, so we consider this to be a negligible overhead.

We also present the solving times of DyGNeX-L under different numbers of snapshots and gap constraints in Table 1. Based on the result and our experience, we believe that when the number of snapshots is less than 100, DyGNeX-L can solve most cases within 10 seconds under a 3% constraint, which we consider acceptable. In DTDG training, the dataset is represented as $G = (G_1, G_2, \dots, G_T)$, where the dynamic connectivity of the graph remains unchanged between epochs. Each epoch trains on the full sequence of graph changes, $G = (G_1, G_2, \dots, G_T)$. Therefore, profiling and solving need to be done only once, regardless of the number of epochs, and the resulting strategy can be applied to the entire training process.

Table 1. Time cost of DyGNeX-L solving under different snapshot numbers and gap constraints

---

W2. Handling situations where solving the ILP at runtime takes too long or fails

We can either relax DyGNeX-L’s constraint or switch to using DyGNeX-G.

---

Q1. What is $n$ in the time complexity?

$n$ represents the number of snapshots in the dataset. In Table 2, we show the solving time of DyGNeX-G as $n$ varies. We believe that when $n$ is less than 10,000, the solving time of DyGNeX-G is guaranteed to be acceptable.

Table 2. Time cost of DyGNeX-G solving under different snapshot numbers

---

Q3. Alternative metrics or features to estimate runtime without profiling

We fully agree with your perspective, and this is indeed a direction for our future work. However, in DyGNeX, since profiling and algorithm solving only need to be performed once, the overhead is minimal, accounting for less than 3% of the end-to-end time, which we consider acceptable.

---

Q4. Why DyGNeX achieves more than 2x reduction in training time per epoch while the imbalance ratio improvement is less than 2x

DyGNeX’s performance gains stem from multiple factors, with load balancing being one of them. Compared to ESDG, DyGNeX achieves gains by both eliminating hidden state communication and enhancing load balancing. Against BLAD, DyGNeX benefits not only from superior load balancing but also from avoiding performance issues inherent to BLAD’s two-process-per-GPU setup, which introduces inter-process synchronization overhead and competition for compute resources. Relative to PSG, DyGNeX’s primary advantage lies in improved load balancing, with additional gains from reducing gradient communication frequency.

Thank you for your valuable review! Your insights have been instrumental in improving the quality of our paper, and we have uploaded a revised version based on your feedback. The revised sections have been highlighted in brickred for clarity.

W1. Effects of snapshot configuration on performance and how these configurations are managed

DyGNeX only needs to ensure that a single group can fit into the memory of one GPU. For the artificially created Arxiv, Products, and Reddit datasets, we followed the same approach as BLAD, sampling 30 snapshots from a static graph dataset, with the window size during training uniformly set to 4. For the Stackoverflow dataset, which spans 2774 days, we grouped the data from every 55 days into a single snapshot, with the training window size also set to 4.

Snapshot configuration can impact the performance of DyGNeX. Our experiments on four datasets demonstrate the impact of snapshot size. We observed that DyGNeX achieves significant improvements across datasets with varying snapshot sizes. Notably, DyGNeX exhibits a greater advantage on datasets with larger snapshot sizes, such as Reddit. In such scenarios, the time imbalance effect caused by the differences among graphs is more pronounced. Time intervals affect the number of snapshot groups in a dataset, while the number of GPUs influences the number of snapshot groups trained per iteration. We can discuss the impact of these factors using the ratio $\frac{\text{group count}}{\text{GPU count}}$. The results are presented in Section 5.4. When the $\frac{\text{group count}}{\text{GPU count}}$ ratio is high—corresponding to scenarios with fewer GPUs in Figure 5—DyGNeX has sufficient flexibility in group scheduling, achieving nearly linear scalability. As the $\frac{\text{group count}}{\text{GPU count}}$ ratio decreases, DyGNeX's scheduling flexibility becomes constrained, limiting the optimization potential. In this case, throughput experiences a certain degree of decline but still shows significant improvement compared to PSG.

---

W2. How sparsity affect performance & Addressing synchronization overhead & Scalability across GNN architectures and dynamic graph types

Admittedly, sparsity can affect the training time of snapshot groups; however, there are many factors influencing the training time of snapshot groups, and DyGNeX does not schedule groups based on these factors. During the profiling phase, DyGNeX obtains the training time for each snapshot group and schedules tasks based on this training time, rather than the properties of the graph itself (e.g., edges, nodes, sparsity).

Meanwhile, synchronization occurs only during the gradient AllReduce phase, introducing no additional overhead. Could you kindly confirm if this is the synchronization you are referring to?

Similarly, DyGNeX does not impose any specific requirements on DGNN models or DTDGs; it simply needs to determine the training time for each snapshot group under the given DGNN model. As a result, DyGNeX is capable of extending to all DTDG datasets and DGNN models.

---

W3. Accuracy

We the test accuracy on the Products and Reddit datasets in Figure 3. This indicates that DyGNeX’s approach does not have a significant impact on accuracy.

---

W4. Misleading in scalability experiment

In Appendix H, we describe how the test data was obtained. Using Dygraph (GRADES-NDA'22), we generated 10,000 snapshots and profiled a subset of these snapshots on A100 GPUs. Through profiling, we observed that training time can be fitted using the equation below. Using another set of data for extrapolation, we found that the prediction error was less than 5%, as shown in Figure 14. We consider this prediction error to be within an acceptable range. Using this linear regression model, we predicted the training times for all 10,000 snapshots, which provided the test data used in our experiments.

$t_{\text{snapshot}} = \alpha_1 \cdot N_{\text{node}} + \alpha_2 \cdot N_{\text{edge}} + \alpha_3$

---

W5. Limitations

We have added a section titled “Limitations” in the main text to discuss the limitations of DyGNeX and potential optimization directions.

Large Snapshot Group In DyGNeX, each snapshot group must fit on a single GPU for training. While current GPU memory (e.g., 80GB, 40GB) suffices for most datasets, larger datasets may exceed this limit, making DyGNeX infeasible. A potential solution is to partition the graph and use full-neighbor sampling on target nodes, enabling training until all nodes are processed. The trade-offs between the overhead of partitioning and sampling and the advantages of DyGNeX over vertex-based methods (e.g., DGC) merit further exploration.

Limited Number of Snapshot Groups The benefits of DyGNeX depend on the flexible combination of snapshot groups for load balancing. With very few groups, the limited combination space reduces potential gains.

We hope our answers will address your concerns.

Dear Reviewers,

We would like to extend our heartfelt gratitude for the time and effort you have dedicated to reviewing our manuscript and providing us with such valuable suggestions. As the author-reviewer discussion phase is approaching its conclusion, we deem it necessary to confirm whether our responses have successfully tackled your concerns.

A few days ago, we furnished detailed responses to address your concerns. We earnestly hope that these responses have satisfactorily resolved the issues you raised. In the event that you need further clarification or happen to have any additional concerns, please feel free to reach out to us at any time. We are wholeheartedly prepared to continue our communication with you and are committed to ensuring that all your queries are properly addressed.

Thank you for your valuable review! Your insights have been instrumental in improving the quality of our paper, and we have uploaded a revised version based on your feedback. The revised sections have been highlighted in brickred for clarity.

W1. Improvement compared with PSG

PSG is a baseline proposed in DyGNeX, and comparing it with PSG directly highlights the benefits brought by improved load balance. DyGNeX-G achieves an average improvement of 12.51% compared to PSG, while DyGNeX-L achieves an average improvement of 17.45%. We believe these improvement rates are considerable.

W2. Cost analysis of the ILP solver vs the greedy variation

We find your proposed viewpoint very meaningful. We present the solving times of DyGNeX-G and DyGNeX-L under different numbers of snapshots and gap constraints in the main text Table 5 and Table 6 (Word limit in comments). Based on the results in the tables, we observe that even with a relaxed 10% constraint, DyGNeX-L cannot match the speed of DyGNeX-G. From our experience, the performance difference between DyGNeX-G and DyGNeX-L (with a 2% constraint) is generally around 5%. Therefore, we believe that setting DyGNeX-L’s constraint to 2% or 3% compared to DyGNeX-G provides stable performance improvements. However, considering the computational cost of the ILP solver, we use DyGNeX-L for solving when the number of snapshots is less than 100 and DyGNeX-G when the number exceeds 100.

W3. The use of a simulator instead of the actual runs is not ideal

Except for Section 5.4, all of our experiments were actually run on A100 GPUs. In Section 5.4, due to hardware limitations, we used a simulator to conduct throughput simulations. Meanwhile, we explained the rationality of the simulation in Appendix H. In this section, we used the greedy algorithm for scheduling instead of the ILP method, because ILP was difficult to solve in this scenario, while the greedy algorithm could be quickly solved within 10 seconds, which we considered acceptable.

Q1. How does varying the number of snapshots impact the training time per epoch and the task scheduling overhead?

The number of snapshots affects the number of snapshot groups. Since DyGNeX leverages the lack of temporal dependency between snapshot groups to enable data parallel training, the impact of the number of snapshots on training time per epoch is consistent with the effect of increasing the number of training batches in data parallel training. The impact on task scheduling overhead is shown in Table 5 and Table 6. When the number of snapshots exceeds 100, DyGNeX-L experiences significant task scheduling overhead, and when the number of snapshots exceeds 10,000, DyGNeX-G faces noticeable task scheduling overhead.

Q2. How quickly does the dynamic connectivity of the graph change between epochs?

In DTDG training, the dataset is represented as $G = (G_1, G_2, \dots, G_T)$, where the dynamic connectivity of the graph can change between iterations within an epoch but remains unchanged between epochs. Each epoch trains on the full sequence of graph changes, $G = (G_1, G_2, \dots, G_T)$. Therefore, profiling and solving need to be done only once, regardless of the number of epochs, and the resulting strategy can be applied to the entire training process.

We hope our answers will address your concerns.

Thank you for your valuable review! Your insights have been instrumental in improving the quality of our paper, and we have uploaded a revised version based on your feedback. The revised sections have been highlighted in brickred for clarity.

Q1. Test accuracy

We present the test accuracy on the Products and Reddit datasets in Figure 3.It can be observed that in the vast majority of scenarios, there is no difference in accuracy between DyGNeX and PSG. This indicates that DyGNeX’s approach does not have a significant impact on training quality.

Q2. Memory consumption

We use torch.cuda.max_memory_allocated() to analyze the memory consumption during training. As shown in the table below, we observed that DyGNeX consistently requires less GPU memory compared to BLAD across all datasets and models. The results demonstrate that DyGNeX has lower memory requirements compared to BLAD. In DyGNeX, all experiments can be conducted on consumer-grade GPUs, such as the NVIDIA RTX 2080 Ti or RTX 3090. Due to the single-GPU dual-process pipeline handling groups, BLAD has introduced additional memory consumption caused by model replicas and so on.

Memory Consumption Comparison between DyGNeX and BLAD (in GB)

We hope our answers will address your concerns.