We thank the reviewer for acknowledging the clarity of our proposed method, the delivery of ideas as well as the comprehensive experiments. We address the question for the reviewer below.

Response to “Adding experiment DropNode as a baseline”

We thank the reviewer for raising this comment for enriching the evaluation and comparison. We further conduct the experiment of DropNode across all different architectures with the same experimental setting. For fair comparison, we set the ratio of edge dropped to the same across different baselines in all experiments. We present the experiment of DropNode in the appendix of the paper. As shown in the results, DropNode experiment results share similar features with DropEdge, where StructDrop achieves a comparable accuracy with DropNode. Same as DropEdge, StructDrop achieves higher efficiency because of hardware efficiency as discussed in section 4.2.2, StructDrop drops the entire columns and rows, leading to reduced adjacency matrix and node embeddings and finally translates into performance gain during training.

Response to “accuracy type in Table 1”

The number reported in Table 1 is test accuracy during the experiment. We will add the clarification in paper to avoid ambiguity.

We thank the reviewer for recognizing our contributions and writing. We address the questions raised below.

Response to “the large variance potentially caused by in-convergence for experiment without instance normalization in GCN”

We thank the reviewer for the careful review! We add more experiments specifically to check the convergence level with respect to the training epoch. We added them to the appendix of our paper. As shown in the figure, the training of Reddit and ogbn-Arxiv without instance normalization has converged as the highest validation point is achieved far before the training ends. For ogbn-Product dataset, we plot a training curve with 1200 epochs (far more than commonly used configuration) and we see it converge very slowly during training without instance normalization. Note that the number we report in the paper is following the configuration of experiments with instance normalization for ablation study. In ogbn-Product experiment, even with 1200 epochs, the accuracy finally achieves 76.73 ± 2.30, which is far less than with instance normalization. The results show that instance normalization does help with convergence speed as it contributes to the stabilized training under the randomized sampling training mechanism. Meanwhile, the smooth training process contributes to the final accuracy. Nonetheless, The variance of accuracy could be due to the instability of the training process, that because of the randomness the model converges to different points. With instance normalization, the smoother internal shifts (as shown in figure 5) lead to more robust training.

Response to “different algorithms for fully utilizing the features of datasets”

We thank the reviewer for the careful thoughts on designing the algorithm! We agree different datasets do have different features which could be utilized, for example, the information redundancy, the connectivity, etc, which could be considered in future work. For our proposed method, we used a general and uniformed sampling scheme, and we only have one hyper-parameter in configuration which is the sampling ratio. This method works well across different datasets.

Response to “incremental contribution”

We claim our contribution as the first to employ random sampling during the whole training pipeline which largely accelerate the GNN training. We study and implement different sampling algorithms and effectively accelerate the graph training. We report and find that sound theory for top-k sampling might not be the most robust algorithm for sampling in forwarding. Instead, a pure random sampling algorithm could work the best. We proposed to apply instance normalization in this scheme for stabilizing the training. We also conduct comprehensive analysis and experiments to verify our results that we accelerate the large graph training far more than previous SOTA GNN acceleration[1] while preserving the accuracy.

Response to “Lack of elaboration for efficiency of random sampling based mechanism”:

We would like to point out that our method has largely increased the efficiency of GNN training. Our evaluation in Table 2 shows that our proposed method achieved at most 3.87x than the vanilla scheme while maintaining the accuracy. Moreover, we accelerated much more in large graph training then previous work. We are the first to study and apply sampling algorithms during the whole training process, and exceed the previous SOTA solution by more than 2x [1].

Response to “adding the original formula as part of our baseline”:

We would like to point our in section 2.2 we wrote “(Adelman et al., 2021) introduced the top-k sampling method: deterministically selecting the k column-row pairs that have the highest values according to Equation 4”. In another word, top-k sampling is based on the equation 4 and is a better mechanism for forming up the sampling. We have thoroughly studied the behavior of top-k sampling and compare our results with it in section 4 as a baseline. Our conclusion is that top-k sampling cannot maintain the accuracy due to underflow, and applying StructDrop will achieve efficiency while preserving the accuracy.

[1] Liu, Zirui, Chen Shengyuan, Kaixiong Zhou, Daochen Zha, Xiao Huang, and Xia Hu. "RSC: accelerate graph neural networks training via randomized sparse computations." In International Conference on Machine Learning, pp. 21951-21968. PMLR, 2023.

Response to “theoretical guarantee to StructDrop”

We thank the reviewer for considering the overall soundness of our proposed scheme. Here we would like to argue that our work takes an initial step towards exploring random algorithms applying to the forward path. We report and find that sound theory for top-k sampling, which is an unbiased estimation, might not be the most robust algorithm for sampling in forwarding, which is inconsistent with intuition. We then experimented and proposed this effective random sampling algorithm, which works well for the training pipeline. We have done comprehensive analysis and experiments for verifying our observations. We hope this first step could benefit the community and innovate more work alongside this direction.

Response to “sampling efficiency comparing to top-k sampling in Table 2”

We thank the reviewer for the careful reviewing our evaluation results. We would like to point out that for all the baseline listed in Table 2, they are conducted and compared in a fair way, that top-K sampling is also applied both in forward and backward pass. Among different mechanisms, Our conclusion is that StructDrop is the robustest in acceleration while preserving the accuracy.

Response to “adding more architecture for graph training”

We thank the reviewer for the careful consideration. We would like to point out that GCN and GraphSAGE are still the robustest and most widely used GNN architectures in graph training. We add another GNN architecture that is widely used — GCN2 for validating our results. We add experiments of comparing different baselines on this architecture and we add the results in the appendix of the paper. The results show a consistent conclusion with all other architectures, that StructDrop accelerates the sparse operations, largely reducing the computation complexity while preserving the accuracy. Please refer to the appendix for more details. We believe the architecture presented in our paper are used in mainstream GNN training and our results are representative and convincing in GNN accelerations.

Response to “adding more graph training mechanisms”

We thank the reviewer again for the careful consideration. As suggested, we add Graphsaint experiment to validate whether we can accelerate the subgraph training mechanism effectively using StructDrop. We add experiments of comparing different baselines on this mechanism and we add the results in the appendix of the paper. Comparing through different baseline, StructDrop is the most Robust mechanism that it accelerate the training while maintaining the accuracy, which is consistent with other experiments. Please refer to the appendix for more details.

Response to “Why does training accuracy decreased with the increased sample ratio for ogbn-Product dataset”

We thank the reviewer for the detailed review of this experimental results. We found that ogbn-Product’s performance decreased with the increased sample ratio. We further conduct experiments to change the dropout ratio (a training configuration) in ogbn-Product dataset training. We found consistent results with the results presented in the paper, that with larger dropout ratio, the accuracy decreases more. We explain the phenomenon as follows: the augmentation and generalization performance varies across different datasets. For ogbn-Product, it has much more edges/nodes compared to other datasets, leading to much more information redundancy. The augmentation scale, which can be defined by the ratio of dropped information, i.e. the dropping number of columns row pairs in our settings, will contribute more to the generalization ability, and improve the model’s performance as a result.