EvA: Evolutionary Attacks on Graphs

W1, W2, Q2, Q3. Compared to [1], we proposed three novel contributions: (i) Sparse and parallelized implementation (ii) Adaptive targeted mutation, and new fitness functions (Figure [2]) (iii) First ever attack on conformal prediction and GNN certificate.

As we show in the table below [and table 14 in appendix], (i) and (ii) lead to significant improvements. More importantly, since 2018, genetic-based algorithms have been ignored in favor of the gradient-based attacks. We argue this is a big oversight of the field.

Moreover, this perspective reveals the need to adjust new methods to balance exploration-exploitation for better performance. We believe this insight can suggest the design of new techniques that require fewer queries or hybrid approaches that combine the advantages of both strategies. For completeness we add further discussion in appendix.

W3, Q4. We draw the attention of the reviewer to Fig.5 (center and left) and Table 9, where we report the result of EvA and SOTA on the two most effective and commonly used defenses: (i) adversarial training and (ii) robust message passing (e.g., SoftMedian [1]). We refer the reviewer to Fig. 5 (right) and Table 9 (appendix) for adversarial training. SoftMedian - established to be the strongest defense [5] - is also studied in Fig 5.

W4, Q5. The reviewer is correct. We add the discussion on time complexity in the manuscript. The algorithm's runtime is O(population size/batch size * iterations * forward). The crossover and mutation do not have an effective overhead on the inference as they are linear to the size of the population. We added empirical results (fig 8 right) in appendix]on how EvA balances between time and memory constraints, i.e., with a limited memory budget, how much time is needed to attain the same performance. Furthermore, we showed the comparison with PRBCD with a limit, showing that for very small time limits (<20s), PRBCD is comparable to EvA. Increasing the computational capacity does not benefit PRBCD, but significantly benefits EvA.

Q1. Following [2], we consider the inductive setup since the transductive setup is shown to carry a flawed sense of robustness. The public split are only for transductive setup. While, we report our results mainly on the (more realistic) inductive setup; Table 1 reports the transductive setup for completeness. As shown by [4], even in a transductive setup, evaluation on one split (e.g., the default) is a major pitfall. Therefore, the evaluation should be applied to several random splits. Consequently, we introduced a split using the pipeline outlined in [2]. Another critical problem with the original split is that the size of the validation set is much larger than training set which is both unrealistic and can lead to flawed evaluation as discussed at length in [3] (section 3, P1). Similarly, [1] provide the drawbacks of having a large validation set for semi-supervised learning in general (see Page 7 of their paper). To summarize, a more extensive validation set could be more effectively utilized in real-world applications as part of the training set.

[1] Realistic Evaluation of Deep Semi-Supervised Learning Algorithms. Oliver et al., NeurIPS 2018.

[2] Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan

[3] Vijay Lingam, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Rethinking label poisoning for gnns: Pitfalls and attacks. In The Twelfth International Conference on Learning Representations, 2023.

[4] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868, 2018.

[5] Mujkanovic, F., Geisler, S., Günnemann, S., & Bojchevski, A. (2022). Are defenses for graph neural networks robust?. Advances in Neural Information Processing Systems, 35, 8954-8968.

Thank you for your insightful feedback and time. If you have further questions, we’re happy to clarify. If your concerns are addressed, we’d appreciate it if you could consider updating your score.

We thank the reviewer for reading our paper and for the constructive feedbacks. Below, we have provided a response addressing the comments and suggestions.

Larger graphs. We conducted additional experiments on the larger OGBN-ArXiv dataset. These experiments are conducted in two setups which are designed to be realistic.

No limitation. We apply the same experiment as for other datasets. We study the perturbation budget $\epsilon \in \{0.001, 0.005, 0.01\}$since even 1% equals approximately 10,000 edges on ArXiv. Higher perturbation budgets are unrealistic. As shown in the table, EvA performs better or comparable to PRBCD.

Realistic larger scale attacks. The freedom to choose any node and perturb its edges is unrealistic, especially in large networks. For instance, in a social network, an adversary might have a limited number of accounts that they control. Here, the adversary is allowed to perturb the edges with one endpoint landing in a predefined subset of “control” nodes. Moreover, often the attacker wants to target a subset of nodes, rather than all test nodes. To study we randomly pick 1000 control nodes, and 1500 target nodes. The table below shows the average result of over five random samplings. In this more realistic setting, our gap to PRBCD is even larger. Note, here the percentage is w.r.t. the edges of the control nodes.

Readability. In light of the reviewer’s comment we improved the readability of the paper.

Time analysis. We conducted a new experiment showing the performance of both EvA and PRBCD under various time and memory constraints. Both PRBCD and EvA offer adaptability through their hyper-parameters. In PRBCD, the block size can be adapted to accommodate memory limitations, and computations can be terminated within a specified time limit. Similarly, EvA can adjust by decreasing the population size and capping the number of iterations to meet time and memory restrictions. To explore these adaptations, we conducted an experiment (Fig. 8, left) that evaluates the wall-clock time and effectiveness of both approaches. The results indicate that PRBCD performs better under very tight time constraints (<20s), maintaining similar effectiveness even with increased computational power, which means that the method does not exhibit any improvement given more computational power. Furthermore, as shown in Fig. 3, similar accuracy can be achieved for various memory constraints by varying running time. For the PubMed graph, EvA surpasses PRBCD in under 1 minute, highlighting its superior scaling capabilities. The key takeaway from Fig. 3 is the distinct scalability of EvA, which is absent in PRBCD.

We thank the reviewer for the comments. Here we address concerns:

W1. Yes, indeed, EvA has more forward propagation compare to PRBCD. Through batched inference (highly parallelized), we reduce the time to even one forward pass per iteration for small graphs. Here, the batching process itself (definition of the large graph and extracting the evaluation for each tiny graph after inference) has no significant overhead while allowing hardware utilization. Despite the computational efficiency of PRBCD, it can only partially utilize the provided compute. Increasing the computation power also does not benefit PRBCD, while EvA benefits from it. Here, we conducted an experiment to precisely study this. In figure 8 in appendix, we show a 3D scatter plot where the 3 axes are time, memory and difference with clean accuracy. Under 20 sec and 5GB memory, PRBCD performs comparably with EvA. Increasing the runtime (from 1 to 4 minutes) and memory budget (1 to 30GB), EvA significantly improves while PRBCD’s performance remains the same. This result is on the relatively larger pubmed graph and is easily runnable in modern GPUs. The most important insight from Fig. 3 is precisely EvA's scaling property, which is absent in PRBCD.

Besides, to address the time-space trade-off, Fig. 8 (right) shows the time-memory constraint runs, which all result in the same accuracy. This shows that EvA can adapt its runtime depending on the memory constraint.

W2. We conducted additional experiments on the larger OGBN-ArXiv dataset. These experiments are conducted in two setups which are designed to be realistic.

No limitation. We apply the same experiment as for other datasets. We study the perturbation budget $\epsilon \in \{0.001, 0.005, 0.01\}$since even 1% equals approximately 10,000 edges on ArXiv. Higher perturbation budgets are unrealistic. As shown in the table, EvA performs better or comparable to PRBCD.

Realistic larger scale attacks. The freedom to choose any node and perturb its edges is unrealistic, especially in large networks. For instance, in a social network, an adversary might have a limited number of accounts that they control. Here, the adversary is allowed to perturb the edges with one endpoint landing in a predefined subset of “control” nodes. Moreover, often the attacker wants to target a subset of nodes, rather than all test nodes. To study we randomly pick 1000 control nodes, and 1500 target nodes. The table below shows the average result of over five random samplings. In this more realistic setting, our gap to PRBCD is even larger. Note, here the percentage is w.r.t. the edges of the control nodes.

Q1. There are two general approaches to making a GNN robust: (i) adversarial training and (ii) robust message passing (e.g., SoftMedian [1]). Both setups have already been studied in the paper. For adversarial training, we refer the reviewer to Fig. 4 (right) and Table 9 (appendix). SoftMedian - established to be the strongest defense [2] - is also studied in Fig 4.

In light of the reviewer's comments, we have revised and updated the paper in OpenReview. In case any concerns are not fully addressed or are missing, we would be happy to discuss them further.

[1] Geisler, S., Li, Y., Chen, J., Smola, A., & Loukas, A. (2021). Robustness of Graph Neural Networks at Scale. arXiv preprint arXiv:2110.14038.

[2] Mujkanovic, F., Geisler, S., Günnemann, S., & Bojchevski, A. (2022). Are defenses for graph neural networks robust?. Advances in Neural Information Processing Systems, 35, 8954-8968.

Thank you for your insightful feedback and time. If you have further questions, we’re happy to clarify. If your concerns are addressed, we’d appreciate it if you could consider updating your score.

We are thankful for the reviewer comment. Here we address the mentioned concerns.

W1, 3. We conducted additional experiments on the larger OGBN-ArXiv dataset. These experiments are conducted in two setups which are designed to be realistic.

No limitation. We apply the same experiment as for other datasets. We study the perturbation budget $\epsilon \in \{0.001, 0.005, 0.01\}$since even 1% equals approximately 10,000 edges on ArXiv. Higher perturbation budgets are unrealistic. As shown in the table, EvA performs better or comparable to PRBCD.

Realistic larger scale attacks. The freedom to choose any node and perturb its edges is unrealistic, especially in large networks. For instance, in a social network, an adversary might have a limited number of accounts that they control. Here, the adversary is allowed to perturb the edges with one endpoint landing in a predefined subset of “control” nodes. Moreover, often the attacker wants to target a subset of nodes, rather than all test nodes. To study we randomly pick 1000 control nodes, and 1500 target nodes. The table below shows the average result of over five random samplings. In this more realistic setting, our gap to PRBCD is even larger. Note, here the percentage is w.r.t. the edges of the control nodes.

Additionally, we compared EvA and SOTA (PRBCD) in both memory and time in the modified version (Fig. 8), showing that (i) in the time-memory trade for various memory constraints, there is an instance of EvA with the same effectiveness. However, less available memory requires more time to achieve the same results. Furthermore, Fig. 8 (left) indicates that while PRBCD performs slightly better with very limited computation time (<20s), it fails to improve with increased computational resources. In contrast, EvA demonstrates scalable performance with additional computing. A similar experiment concerning memory constraint is shown in Fig. 3. Again, EvA scales with additional memory.

W2. Compared to [1], we proposed three novel contributions: (i) Sparse and parallelized implementation (ii) Adaptive targeted mutation, and new fitness functions (Figure [2]) (iii) First ever attack on conformal prediction and GNN certificate.

As we show in the table below [and table 14 in appendix], (i) and (ii) lead to significant improvements. More importantly, since 2018, genetic-based algorithms have been ignored in favour of the gradient-based attacks. We argue this is a big oversight of the field. Moreover, this perspective reveals the need to adjust new methods to balance exploration-exploitation for better performance. We believe this insight can suggest the design of new techniques that require fewer queries or hybrid approaches that combine the advantages of both strategies. For completeness we add further discussion in appendix.

[1] Adversarial Attack on Graph Structured Data. Dai & Al. - ICML 2018.

Thank you for your insightful feedback and time. If you have further questions, we’re happy to clarify. If your concerns are addressed, we’d appreciate it if you could consider updating your score.

Clarification on Related Work in Graph and Non-Graph Domains

GANI [1] uses genetic algorithm for node-injection attack, Lapa [2] explores label poisoning attacks and Unsupervised Euclidean Distance Attack [3] studies poisoning of unsupervised (random walk) embeddings. Since we focus on evasion under edge perturbation which is a different goal (in a few ways) from the above methods, they are all out-of scope as baselines, nonetheless, in the camera ready version we would surely discuss them in the related work section. We thank the reviewer for brining them to our attention.

Robust Conformal Prediction Approaches:

On robust conformal prediction [4] and [5] derive certified CP sets that apply for continuous data, but neither apply to graphs and binary data. [6] derives robust CP for graphs but their guarantees hold only in the transductive setting. Specifically, they assume that the defender trains, and computes the calibration scores on the clean graph. Perturbations on test nodes are then applied after calibration. However, as shown by [7] in this setup the defender can easily remember the clean graph and recover it after perturbation which results in full robustness for free.

Deriving provably robust CP sets for inductive node classification is a non-trivial open problem. First of all, even in a non-adversarial setup, the coverage guarantee is only valid in the inductive setting after re-computing calibration nodes [8]. This is because the calibration nodes are affected during message passing with test nodes. Now, if those test nodes are potentially perturbed, the calibration nodes and their scores are also perturbed as a result. Therefore, we would need a certificate that accounts for both changes in calibration and test scores at the same time, which currently does not exist.

Contribution:

We want to highlight the comparison of EvA to the previous known work in genetic-based attack in the same setting [9]. While the high-level idea to use genetic algorithms is the same, compared to [9], EvA has several improvements (fitness, encoding, mutation, scalability) that make it roughly 2.5x more effective (e.g. 78 vs 74 for a budget of 1%) as shown in Table 14.

Moreover, a similar argument on “novelty” can be made for gradient-based attacks. For example, both PGD and PRBCD have the same high-level idea of using project gradient descent. Yet, the details of how you instantiate a gradient-based attack are important for the final performance. This is why we have many different variants of gradient-based attacks accepted at top publishing venues (both for graphs and non-graph data).

In any case, we show that we can get a huge gap to the previous SOTA attack (~11%), which we argue is a contribution enough of its own. Put differently, so far the field has largely ignored genetic attacks (for which ever reason) and focused on gradient-based attacks. We argue that this is a mistake, and that the field should dedicate more effort to genetic-based or hybrid attacks. If this paper is not published, the field would likely continue on the same trend of gradient-based attacks which are far from optimal as we show.

[1] Fang, J., Wen, H., Wu, J., Xuan, Q., Zheng, Z., & Chi, K. T. (2024). Gani: Global attacks on graph neural networks via imperceptible node injections. IEEE Transactions on Computational Social Systems.

[2] Li, J., Li, H., He, J., & Dou, T. (2023, April). Lapa: Multi-label-flipping adversarial attacks on graph neural networks. In 2023 International Seminar on Computer Science and Engineering Technology (SCSET) (pp. 29-32). IEEE.

[3] Yu, S., Zheng, J., Chen, J., Xuan, Q., & Zhang, Q. (2020, July). Unsupervised euclidean distance attack on network embedding. In 2020 IEEE Fifth International Conference on Data Science in Cyberspace (DSC) (pp. 71-77). IEEE.

[4] Gendler, A., Weng, T. W., Daniel, L., & Romano, Y. (2021). Adversarially robust conformal prediction. In International Conference on Learning Representations.

[5] Yan, G., Romano, Y., & Weng, T. W. (2024). Provably robust conformal prediction with improved efficiency. arXiv preprint arXiv:2404.19651.

[6] Zargarbashi, S. H., Akhondzadeh, M. S., & Bojchevski, A. (2024). Robust yet efficient conformal prediction sets. arXiv preprint arXiv:2407.09165.

[7] Gosch, L., Geisler, S., Sturm, D., Charpentier, B., Zügner, D., & Günnemann, S. (2024). Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. Advances in Neural Information Processing Systems, 36.

[8] Zargarbashi, S. H., & Bojchevski, A. (2024). Conformal inductive graph neural networks. arXiv preprint arXiv:2407.09173

[9] Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., & Song, L. (2018, July). Adversarial attack on graph structured data. In International conference on machine learning (pp. 1115-1124). PMLR.