EGALA: Efficient Gradient Approximation for Large-scale Graph Adversarial Attack

We appreciate the concern you have raised regarding the gradient derivation of our EGALA model and its applicability to more advanced GNN models such as GAT and GPRGNN. We fully recognize the importance of this issue. We have made some further studies.

[W1] Regarding the gradient derivation: Although our proposed method only use SGC as the surrogate model, SGC is very useful for its simplicity, scalability and effectiveness. SGC is commonly used as surrogate model in graph adversarial attacks [1][2]. Also, the simplicity of SGC makes it even more applicable to large graphs. We have expanded our empirical evaluation, incorporating additional experiments to benchmark our EGALA model against adaptive PRBCD and GRBCD attacks. These new comparisons are detailed in the revised Appendix B.1. Using more advanced GNNs as surrogate models for attack does not necessarily improve the attack performance. Additionally, we examined the computational resources required conducting attacks on more advanced GNNs. Both time and memory costs rise significantly with the complexity of GNN models, constraining the scalability of adaptive attacks.

In the future, we will try to find ways to apply our model to white-box setting, comparing the approximated gradients with actual ones, and evaluating on other defense methods.

[Q1] Mini-batch training on large graphs: We adopt full-batch training on large graphs, which is the same as the baselines. Specifically, they chunk some operations (e.g. matrix multiplication) within the message passing step to successfully scale to larger graphs.

[Q2] Hyperparameter tuning: To further explore parameter sensitivity and complexity, we have conducted additional ablation studies, presented in Appendix C, to analyze the influence of clustering parameters on our model's performance, both the accuracy and computational cost. For GNN models, we follow the training settings of the original paper of PRBCD and GRBCD.

We appreciate the opportunity to address these critical aspects of our research and believe that the revisions have significantly strengthened the contribution of our work.

[1] Li, Jintang, et al. "Adversarial attack on large scale graph." IEEE Transactions on Knowledge and Data Engineering, 2021.

[2] Zügner, Daniel, et al. "Adversarial attacks on neural networks for graph data." Proceedings of the 24th ACM SIGKDD, 2018.

Thank you for your detailed and valuable feedback. Your input has led to substantive revisions and enhancements in our paper, and we are grateful for the opportunity to improve our work.

[W1] Regarding the extension to other surrogate models and the surrogate model of baselines: Firstly, although our proposed method cannot be extended to other surrogate models, we demonstrate the importance of using SGC as our surrogate model for its simplicity, scalability and effectiveness. SGC is commonly used as surrogate model in graph adversarial attacks [1][2]. Also, the simplicity of SGC makes it even more applicable to large graphs. We have expanded our empirical evaluation, incorporating additional experiments to benchmark our EGALA model against adaptive PRBCD and GRBCD attacks. These new comparisons are detailed in the revised Appendix B.1. Using more advanced GNNs as surrogate models for attack does not necessarily improve the attack performance. Additionally, we examined the computational resources required conducting attacks on more advanced GNNs. Both time and memory costs rise significantly with the complexity of GNN models, constraining the scalability of adaptive attacks.

Secondly, we carried out additional experiments to consider PRBCD and GRBCD utilizing their originally suggested surrogate model, Vanilla GCN. We present the results of this analysis in Appendix B.2.

[W2] Regarding the distribution of budgets: In our experiemnt, the $\Delta_t$ we use is the same as that of GRBCD, where the budget is evenly distributed. This was done to ensure an equitable comparison of results. Furthermore, we acknowledge the potential for future work to explore more sophisticated budget distributions, as also suggested in the GRBCD original paper. Our current choice of $\Delta_t$ serves as a starting point, and we are open to investigating more complex allocation strategies as part of our continued research efforts.

[W2] Regarding the comparison with PDG: We would like to clarify the rationale behind our baseline selection process. The PDG model has already been comprehensively compared with both PRBCD and GRBCD in their respective original publications. Consequently, we focused our comparative evaluation on the two more recent and advanced models: PRBCD and GRBCD. Nonetheless, we appreciate the importance of thorough baseline validation and are prepared to include PDG in our future evaluations to corroborate and extend the findings of the original papers.

[1] Li, Jintang, et al. "Adversarial attack on large scale graph." IEEE Transactions on Knowledge and Data Engineering, 2021.

[2] Zügner, Daniel, et al. "Adversarial attacks on neural networks for graph data." Proceedings of the 24th ACM SIGKDD, 2018.

Thank you for your thorough and constructive feedback. Your insights have been invaluable in refining our paper. Based on your suggestions, we have implemented several modifications and enhancements to our work.

[W2, W3, W4] Regarding the adaptive attack: We have expanded our empirical evaluation, incorporating additional experiments to benchmark our EGALA model against adaptive PRBCD and GRBCD attacks. These new comparisons are detailed in the revised Appendix B.1. Our results indicate that while adaptive attacks on the Vanilla GCN indeed demonstrate effectiveness, adaptive GRBCD does not consistently outperform its transfer attack, particularly within more complex GNN models like Vanilla GDC. The adaptive GRBCD fails to surpass its transfer counterpart in these contexts, suggesting that the advantage of adaptivity in greedy methods is non-universal and may not be decisive in all scenarios. Additionally, we examined the computational resources required for these adaptive attacks. We found that both time and memory costs rise significantly with the complexity of GNN models, constraining the scalability of adaptive attacks. This finding is important as it underscores the trade-offs between the intensity of attack methodologies and their practical deployability, especially with more elaborate GNN architectures.

[Q2] Computational cost affected by hyperparameters: To further explore parameter sensitivity and complexity, we have conducted additional ablation studies, presented in Appendix C, to analyze the influence of clustering parameters on our model's performance, both the accuracy and computational cost. Also, it is noteworthy that the primary contributor to computational load in EGALA on small datasets is the Approximate Nearest Neighbor Search (ANNS). As such, pursuing more advanced ANNS methods is likely to reduce computational costs substantially.

[Q3] The approximation of $\frac{\partial a_{ij}}{\partial e_{ij}}$: The approximation of the derivative $\frac{\partial a_{ij}}{\partial e_{ij}}$ is necessary and indispensable. Empirically, the attack performance degrades if we ignore this part. Moreover, according to Equation (14) of our paper, $\frac{\partial a_{ij}}{\partial e_{ij}}$ is inversely proportional to the squared root of node degrees. By attacking edges connected to lower-degree nodes, the model incurs a higher misclassification rate, which is consistent with recent findings in [1]. The attack performance without the approximation of $\frac{\partial a_{ij}}{\partial e_{ij}}$ is shown in the following table.

In the future, we will conduct more experiments to evaluate on local attacks, visualizing the approximated gradients, finding ways to apply our model to white-box setting, and evaluating on other defense methods. Your comments have been instrumental in improving our study and the clarity of our findings. We appreciate the opportunity to address these critical aspects of our research and believe that the revisions have significantly strengthened the contribution of our work.

[1] Li, Kuan, et al. "Revisiting graph adversarial attack and defense from a data distribution perspective." The Eleventh International Conference on Learning Representations, 2022.

Thank you for your thorough and insightful comments. Your constructive feedback has played a crucial role in the enhancement of our manuscript. We have undertaken a series of thoughtful modifications and additions in our work to address your points. Moreover, there are certain clarifications we would like to present regarding aspects of our research.

[W1 & W2] Regarding the adaptive attack: We expanded our empirical evaluation, incorporating additional experiments to benchmark our EGALA model against adaptive PRBCD and GRBCD attacks. These new comparisons are detailed in the revised Appendix B.1. Our results indicate that while adaptive attacks on the Vanilla GCN indeed demonstrate effectiveness, adaptive GRBCD does not consistently outperform its transfer attack, particularly within more complex GNN models like Vanilla GDC. The adaptive GRBCD fails to surpass its transfer counterpart in these contexts, suggesting that the advantage of adaptivity in greedy methods is non-universal and may not be decisive in all scenarios. Additionally, we examined the computational resources required for these adaptive attacks. We found that both time and memory costs rise significantly with the complexity of GNN models, constraining the scalability of adaptive attacks. This finding is important as it underscores the trade-offs between the intensity of attack methodologies and their practical deployability, especially with more elaborate GNN architectures.

[W2 & W3] Regarding the computational cost: We would like to apologize for any confusion caused by our initial presentation of the computational cost comparison. We have revised Table 3 in Section 4.2 to seperate the computational analysis of both EGALA and EGALA-N. The the increment of computational cost of EGALA on small datasets can be attributed to the ANNS methodology employed in EGALA. Exploring more efficient ANNS implementations holds the potential to notably diminish the overall computation cost. More importantly, for smaller datasets like Cora and Citeseer, the direct computation of matrix multiplication proves to be both rapid and incurs minimal memory cost. Conversely, for larger datasets like Arxiv and Products, the incorporation of the ANNS mechanism significantly mitigates computational costs, justifies its application.

When comparing the computational cost of PRBCD and GRBCD, we used the recommended hyperparameter settings in the original papers to ensure fidelity in our comparative analysis. We also studied the influence of block size on the performance of the baseline. The results are shown in the following table.

[W4] Ablation studies: We conducted ablation studies, presented in Appendix C, to analyze the influence of clustering parameters on our model's performance, comparing both the accuracy and computational cost simultaneously.

Your feedback has been instrumental in propelling our research forward. We appreciate the opportunity to address these critical aspects of our research and believe that the revisions have significantly strengthened the contribution of our work.