We thank the reviewer for their feedback and acknowledgment of the good presentation!

W1: Limited contribution because attacks are not general

Adaptive attacks are necessarily model-specific. Nonetheless, our adaptive attacks are applicable to any model that uses one of the components that we relaxed. Furthermore, we provide general guidelines for designing such adaptive attacks for graph transformers. Note that our attack perturbations can be universally applied to any model as transfer attacks (in the same way, established attacks such as Nettack and Mettack are universally applicable). Due to the strength of our "best transfer", one can use the perturbations of our work for a first test on other GT's robustness. We provide the detailed discussion and reasoning in the general comment, "Universal adaptive attacks do not exist."

Since universal adaptive attacks are not attainable, we believe this should not be considered a weakness of our work. However, if the reviewer is not fully convinced by our arguments, we would kindly ask for more clarification so that we can effectively address the reviewer's concern.

W2: Attacks too weak

If comparing to the state of the art, our adaptive attacks are usually the strongest (in 88% of the cases for budgets of 10% or higher) and often by a large margin (e.g. in Figure 6, our adaptive achieves 1% adversarial accuracy vs. 60% of second-best attack). Our results clearly demonstrate that prior adversarial attacks are grossly insufficient for the evaluation of adversarial robustness of graph transformers. We refer to our 'Effectiveness of our attacks' global comment for more details, also contrasting the previous with the updated presentation in the paper.

Regarding the ablations, note that for Graphormer and SAN at least one relaxation is necessary to compute the gradients. The fact that the attack sometimes works better when only relaxing a single component is not entirely unexpected. As suggested in the Recurring Attack Theme T2 of $2$ :

only one or two $components$ would be sufficient for the defense to fail. Targeting only these components can lead to attacks that are simpler, stronger, and easier to optimize.

$2$ F. Tramèr, N. Carlini, W. Brendel, "On Adaptive Attacks to Adversarial Example Defenses", NeurIPS 2020.

W3: Attack baselines

We thank the reviewer for the suggestion on further attack baselines. In the revision, we have now added two new baseline attacks including the "GCN PRBCD transfer" attack as a (state-of-the-art) baseline. Note that the "GCN PRBCD transfer" has been shown to be more effective than SGA and Nettack $5$ . To the best of our knowledge, there has been no applicable attack that is significantly/consistently stronger in the meantime.

As we explain in our 'Requested baselines' global comment, many suggested baseline attacks (including Mettack and Nettack) are not suitable for the (GT "preferred") datasets and attack settings we evaluate on.

If our rebuttal did not fully address the points brought up by the reviewer, we kindly ask for clarification so we can effectively address the reviewer's concerns.

$5$ S. Geisler, T. Schmidt, H. Şirin, D. Zügner, A. Bojchevski, S. Günnemann, "Robustness of Graph Neural Networks at Scale", NeurIPS 2021.

We thank the reviewer for the review and, particularly, feedback on improving out work!

W1: Formulas not explained

We have updated and moved the corresponding section to more clearly explain the reasoning behind the log-term bias in the local attention relaxation. The revised section (shown in blue) now includes equations 6 and 7.

We hope that the improved explanation for this case helps in understanding the other equations as well. More details on the GT architectures, as provided in the appendix C, would most likely also be helpful to fully understand the relaxations.

W2: Robustness difference between datasets

It is very challenging to say a priori why and in which setting a model is robust. This is one of the reasons why adaptive attacks like ours are vital for anyone who seriously wants to deploy a GT and, thus, needs to understand the limitations in their respective setting.

W3: Confusing writing

We want to point out that we do define the node degree $\mathcal{deg}(v_i)$ in the first paragraph of section 2 (originally line 78). If there are other parts of the paper where the confusing writing could be improved, we would appreciate suggestions.

W4: Attack baselines

We thank the reviewer for pointing out the matter of attack baselines. In the revision, we have now added two new baseline attacks including the state-of-the-art "GCN PRBCD transfer" attack. To the best of our knowledge, there has been no applicable attack that is significantly/consistently stronger in the meantime.

While there are many other existing works, not all apply to the same settings and are thus not comparable to each other. For instance:

• The first suggested attack (InfMax) only perturbs the node features while the graph structure remains the same. We are interested in the opposite case, where only the graph structure is modified, which affects the positional encodings used in graph transformer models.
• The second suggested attack (graph backdoor) corresponds to a different threat model, where the attack already occurs at training time. In the evasion setting that we consider, the models have already been trained on clean data (fixed weights), and the test input is perturbed.

Thus, these two attacks would not be meaningful baseline comparisons. For further details, we kindly refer to our 'Requested baselines' global comment. However, we are happy about specific suggestions that are applicable to our setting (and ideally go beyond transferring perturbations from a GCN).

W5: Defense baselines

The main contributions of our paper are the adaptive attacks for graph transformers and robustness evaluations. However, we also demonstrate that our attacks can be used for Adversarial Training (AT) to improve the robustness. We believe these results are not trivial and may be of interest to further research. Due to the many aspects like inductive vs. transductive, node-level vs. graph-level, etc. a thorough/meaningful comparison on when GNNs (+ defenses) are superior to GTs requires multiple works on its own.

As a consequence of not comparing to baselines, we do not claim SOTA results or improvements over alternative defenses. However, it has been shown by $4$ that most existing GNN defenses can be effectively be broken by adaptive attacks such as ours. In contrast, our AT Graphormer models are impressively robust against our adaptive attacks.

$4$ F. Mujkanovic, S. Geisler, S. Günnemann, A. Bojchevski, "Are Defenses for Graph Neural Networks Robust?", NeurIPS 2022.

W6: Experiment setting

In the revision, we have updated the figures and captions to explain the attack settings more explicitly and highlight better our main attack. For more details on the baselines and which results are from our attacks, we kindly refer to our 'Effectiveness of our attacks' global comment.

We thank the reviewer for their feedback and for acknowledging that our work is a good basis for adversarial attacks on GTs.

W1: Notation and clarity

We thank the reviewer for pointing out these improvements, we have addressed them in the revision (modifications are shown in blue). For GTs, the adjacency matrix is not self-looped (and adding a self-connection is not considered a valid attack perturbation, such that the diagonal always stays zero).

W2: Clarity on attack setting

We thank the reviewer for the feedback and have added a reminder of the attack setting to the evaluation section and all figures to improve clarity. However, we would like to point out that we did specify the attack setting in sub-section 2.1 (originally line 86):

untargeted white-box evasion attacks, i.e., an attacker with full knowledge of model and data attempts to change the trained model’s prediction to any incorrect class at test time by slightly perturbing the input graph structure. For node-level tasks we focus on global attacks that minimize the overall performance metric across all nodes.

We previously described the attack losses in section 5 (originally line 317). In the revision, we have modified and moved this to section 2.1 for increased clarity.

Q1: Real-world scenarios

One scenario is that of fake news detection $A$ as we explore with the fake news detection datasets (UPFD). A model could be deployed to automatically detect if a social media post contains fake news. An adversary, similar to our attack, then might access different accounts under their control to retweet the post with the goal of deceiving the fake news detection. This is similarly explored for other GNN-based fake news detectors in $B$ . Another important application of graph learning methods is spam detection $C$ , where structure perturbations can model spammers adapting their posting strategy to avoid detection $D$ .

Nevertheless, due to the white-box attack setting, we are mostly concerned with understanding the limitations of a model and less with IT security. Understanding the limitations of a model is critical for all wide-spread applications. To what extent GTs are the better choice for applications is not up to us. However, as GTs are showing strong performance in benchmarks, it is not unreasonable to assume that they could be deployed. The question we tackle relates to the simple and important question: are the predictions of graph transformers more or less fragile than those of MPNNs? To answer such a question, the field requires the tools we study.

$A$ Hu et al. "An overview of fake news detection: From a new perspective", Fundamental Research 2024

$B$ Wang et al. "Attacking fake news detectors via manipulating news social engagement", WWW 2023

$C$ Li et al. "Spam Review Detection with Graph Convolutional Networks", CIKM 2019

$D$ Soliman et al. "AdaGraph: Adaptive Graph-Based Algorithms for Spam Detection in Social Networks", 2017

Q2: Discontinuity

For some models, such as GRIT, a continuous change of the values of the adjacency matrix does indeed result in a continuous change of the output. However, other models are "designed for a discrete graph structure" to such an extent that the architecture and implementation rely on the certainty that the values in the adjacency matrix are discrete (e.g., for Graphormer). When inputting continuous values in the adjacency matrix, the computation becomes undefined and trying to execute the original implementation of the model results in an error.

Q3: Relaxation differentiability

For the relaxations we only require continuity and not differentiability everywhere. While it would be nice if $\tilde{f}\_{\theta}$ was continuously differentiable, it would be challenging to design it in such a way. Nonetheless, for optimization, it should suffice for the function to be continuous. As we stated directly after the principles:

While Principle II might appear surprising at first glance, we argue that we do not need to enforce stronger standards on $\tilde{f}\_{\theta}$ than perhaps the most widely used activation function ReLU

(Since NNs using ReLU can evidently be optimized as well).

Q4: Local attention relaxation

We have updated and moved the corresponding section to more clearly explain the reasoning behind the log-term bias in the local attention relaxation. The revised section (shown in blue) now includes equations 6 and 7.

Q5: Other attacks

Since our relaxations enable the computation of gradients w.r.t. the adjacency matrix in general, we are not limited to using PDG/PRBCD. Other options for gradient-based attacks are e.g. FGSM/FGA, and GRBCD $4,5$ . Moreover, $5$ (and $4$ ) show that for adaptive global evasion attacks PRBCD (and PGD) tend to perform the best. Therefore, we would not expect the results and insights to change much by adding a new gradient-based attack such as GRBCD. For this reason, we did not pursue this further.

We also want to note that we apply evasion attacks (test-time); using a poisoning attack (training time) such as Mettack is not directly applicable.

$4$ F. Mujkanovic, S. Geisler, S. Günnemann, A. Bojchevski, "Are Defenses for Graph Neural Networks Robust?", NeurIPS 2022.

$5$ S. Geisler, T. Schmidt, H. Şirin, D. Zügner, A. Bojchevski, S. Günnemann, "Robustness of Graph Neural Networks at Scale", NeurIPS 2021.

We thank the reviewer for their critical thoughts on improving our paper!

W1: Universal adaptive attacks

Adaptive attacks are necessarily model-specific, and their development contains empirical parts. Nonetheless, our adaptive attacks are applicable to any model that uses one of the components that we relaxed. Furthermore, we provide general guidelines for designing such adaptive attacks for graph transformers. Note that our attack perturbations can be universally applied to any model as transfer attacks (in the same way, established attacks such as Nettack and Mettack are universally applicable). Due to the strength of our "best transfer," one can use the perturbations of our work for a first test on other GT's robustness. We provide the detailed discussion and reasoning in the general comment, "Universal adaptive attacks do not exist."

Since universal adaptive attacks are not attainable, we believe this should not be considered a weakness of our work. However, if the reviewer is not fully convinced by our arguments, we would kindly ask for more clarification so that we can effectively address the reviewer's concern.

W2 (and Q1): Attack effectiveness and baselines

If comparing to the state of the art, our adaptive attacks are usually the strongest (in 88% of the cases for budgets of 10% or higher) and often by a large margin (e.g. in Figure 6, our adaptive achieves 1% adversarial accuracy vs. 60% of second-best attack). Furthermore, we want to point out that we do include "non-adaptive attacks without relaxation": the (brute force) random attack and the GCN transfer attack. These attacks are the applicable state of the art in the GNN attack domain. We refer to the general comment for an in-depth discussion, and we have changed our presentation to convey this better.

W3 (and Q1): Not enough attack/ defense comparisons

We appreciate the suggestions on incorporating further baselines. We now include two additional baseline attacks. However, it is not trivial to find other suitable baseline attacks for the datasets and attack settings we study (e.g., this is why Mettack and Nettack are not suitable). We are happy about specific suggestions that are applicable to our setting (and ideally go beyond transferring perturbations from a GCN). For more details on this point, please see 'Requested baselines' in our general comment.

The main contributions of our paper are the adaptive attacks for graph transformers and robustness evaluations. However, we also demonstrate that our attacks can be used for Adversarial Training (AT) to improve their robustness. We believe these results are not trivial and may be of interest to further research. Due to the many aspects like inductive vs. transductive, node-level vs. graph-level, etc., a thorough/meaningful comparison of when GNNs (+ defenses) are superior to GTs requires multiple works on its own.

As a consequence of not comparing to baselines, we do not claim SOTA results or improvements over alternative defenses. However, it has been shown by $4$ that most existing GNN defenses, such as GNNGuard $9$ , can be effectively broken by adaptive attacks such as ours. In contrast, our AT Graphormer models are impressively robust against our adaptive attacks.

Q2: Gradient-based without relaxations

The results for all transfer attacks can be considered as results for gradient-based attacks that do not use the relaxations of the victim model. Regarding adaptive attacks, for models that only include the adjacency matrix in a non-differentiable manner (e.g., Graphormer), at least one relaxation is required to compute the gradient. Without any relaxation, the gradient is undefined and, e.g., PyTorch will throw an error. Thus, no adaptive gradient-based attack is possible. However, in the ablations, we show how using different relaxations individually impacts the performance.

We are confident that this addresses all the concerns of the reviewer and are looking forward to their feedback!

We now additionally include "GCN PRBCD transfer" and "random perturbation" as baseline attacks. The GCN PRBCD transfer attack follows the same principle as many other popular (and requested) baselines: a gradient-based attack (PRBCD) on a "simpler" surrogate (GCN) that gets transferred to the victim model. Moreover, it has been show to be just as effective (or more) than other baselines $5$ .

We want to note that it is not easy to find suitable baseline attacks for our learning task and attack settings. Admittedly, we only mentioned these settings in the background section, which presumably led to some misunderstanding. In the revision, we have made the setting much clearer in all relevant sections and figures (shown in blue). Below, we explain in detail why it is not possible to employ most of the baselines requested by the reviewers.

Specifically, we evaluate on datasets that contain many graphs (of smaller size) where the task is inductive graph (or node) classification because, in such settings, GTs perform best. Existing GNN robustness literature often studies the transductive node classification task on a single (larger) graph. However, most GTs are not applied to these tasks as they do not perform well in this setting. For the inductive setting, evasion (test-time) attacks are of most interest; while for the transductive learning setting, poisoning attacks are often more appropriate $4$ . Thus, for our setting we focus on evasion attacks.

Incompatible attack baselines: Due to our specific tasks and settings, the following types of attacks are not suited as baselines for our evaluations:

• Feature attacks: Our attacks only perturb the graph structure, not the node features. Adding feature attacks as baselines would not be very meaningful, as they are not directly comparable (e.g. InfMax $10$ ).
• Different threat models: Since we only evaluate evasion attacks (on inductive datasets), requested baselines that correspond to fundamentally different threat models, such as training-time poisoning (e.g. Mettack $7$ ) or backdoor (e.g. Graph Backdoor $11$ ) attacks are not meaningfully comparable.
• Local attacks (for node classification): Some popular attacks, such as Nettack $6$ and SGA $8$ , are specifically for local attacks, i.e., the prediction of a single node in a node classification task is attacked. The only node classification dataset we evaluate on is CLUSTER. However, we evaluate global attacks where the overall classification accuracy over all nodes is degraded. While we could add a local attack evaluation to compare to the above-mentioned baselines, the global attack is already extremely effective in assessing this "fragile" data. For CLUSTER, local attacks are even more straightforward (disconnect the target node from its cluster and attach to a different one). Thus, hardly any difference between (all successful) attack methods can be perceived. We welcome suggestions for other (inductive) node classification datasets on which we could evaluate local attacks.

Additionally, our "random attack" is a stronger random attack than what is usually reported. Specifically, "random attack" is a brute-force random search attack with a computational budget that matches the adaptive attacks. This results in a much more effective attack than a single random perturbation (which is also often used as a baseline). Because of this, the name may be slightly misleading. To clarify this, we have added the simple single "random perturbation" as an additional baseline to make the difference explicit.

References

$1$ A. Athalye, N. Carlini, D. Wagner, "Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples", ICML 2018.

$2$ F. Tramèr, N. Carlini, W. Brendel, "On Adaptive Attacks to Adversarial Example Defenses", NeurIPS 2020.

$3$ N. Carlini, D. Wagner, "Towards Evaluating the Robustness of Neural Networks", SSP 2017.

$4$ F. Mujkanovic, S. Geisler, S. Günnemann, A. Bojchevski, "Are Defenses for Graph Neural Networks Robust?", NeurIPS 2022.

$5$ S. Geisler, T. Schmidt, H. Şirin, D. Zügner, A. Bojchevski, S. Günnemann, "Robustness of Graph Neural Networks at Scale", NeurIPS 2021.

$6$ D. Zügner, A. Akbarnejad, S. Günnemann, "Adversarial Attacks on Neural Networks for Graph Data", KDD 2018.

$7$ D. Zügner, S. Günnemann, "Adversarial Attacks on Graph Neural Networks via Meta Learning", ICLR 2019.

$8$ J. Li, T. Xie, L. Chen, F. Xie, X. He, Z. Zheng, "Adversarial Attack on Large Scale Graph", TKDE 2021.

$9$ X. Zhang, M. Zitnik, "GNNGuard: Defending Graph Neural Networks against Adversarial Attacks", NeurIPS 2020.

$10$ "Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem", WSDM 2022.

$11$ Z. Xi, R. Pang, S. Ji, T. Wang, "Graph Backdoor", USENIX Security 2021.

We use adaptive attacks to attack the victim models directly because this often results in stronger attacks and, therefore, better model robustness estimates. Indeed, if compared to the state of the art, our adaptive attacks are usually the strongest (in 88% of the cases for budgets of 10% or higher) and often by a large margin (e.g. in Figure 6, our adaptive achieves 1% adversarial accuracy vs. 60% of second-best attack).

However, we can (and do) also use the perturbations generated by our adaptive attacks as transfer attacks for other models (previously "transfer" and now "best transfer"). These transfer attacks are, of course, completely general and can be applied to any model of arbitrary type. Notably, the strength of our "best transfer" attacks seems to have led to some misinterpretation, suggesting that our adaptive attacks are weak in comparison. However, since the transfer attacks are generated by our own adaptive attacks for different graph transformers, the strength of these transfer attacks is, of course, intimately coupled to the strength of our adaptive attacks. Moreover, we transfer the results of the (up to) 8 adaptive attacks for different models, where we take the strongest perturbation for each instance. In other words, the "best transfer" attack can be considered an ensemble attack. We hypothesize that the variety of the transfer attacks substantially benefits the effectiveness. In contrast, we solely report the results for a single adaptive attack. We originally included "best transfer" mainly to show the transferrability of the attacks between GT models and to get the worst-case perturbations for the best robustness estimates.

To disentangle the presentation and first compare our adaptive attacks to the prior state of the art, we now report in Figure 3-6 our adaptive attacks in comparison to a "GCN PRBCD transfer" attack (new baseline/state of the art/common practice). This clearly demonstrates that prior adversarial attacks are grossly insufficient for evaluating the adversarial robustness of graph transformers. Also, note that the "GCN PRBCD transfer" is not a weak baseline as it has been shown to be more effective than GCA and Nettack $5$ . To the best of our knowledge, there has been no applicable attack that is significantly/consistently stronger in the meantime.

Leveraging the variety of our adaptive attacks on different representative graph transformers, we can use them as a diverse transfer attack to new architectures. In Figure 7, we now show that our diverse "best transfer" already constitutes a very effective attack in many but not all settings. Our "best transfer" could be used for future graph transformers as a "unit test." In other words, if a graph transformer is already non-robust w.r.t. "best transfer," then one might skip the considerable effort for designing adaptive attacks.

Based on the above reasoning, our transfer attacks could be considered more general than those of Nettack and Mettack (considering our relaxed GT models as surrogate models) since we allow the transfer of the results from multiple victim models. Admittedly, this is not the most computationally efficient approach, as attacking GTs is more expensive than attacking a GCN.

In summary, prior work is severely insufficient for the robustness evaluation of GTs. Moreover, the strength of "best transfer" is mostly a consequence of the strength of our adaptive GT attacks and should not be considered a weakness of our paper!

Why use adaptive attacks?: While the purpose of using non-differentiable components in GTs is not to defend against adversarial attacks, the resulting effect is the same as for defenses that rely on gradient obfuscation $1$ . Simply applying attacks that were designed for a different setting is likely to result in estimates that are too optimistic. For example, the evaluation with adaptive attacks sometimes even revealed that defenses might harm the robustness while the defenses helped with non-adaptive attacks $4$ . Therefore, adaptive attacks are needed to study the robustness of these GTs more accurately. Our continuous relaxations are analogous to the Backward Pass Differentiable Approximations proposed in $1$ , although we also use the relaxations in the forward pass.

Adaptive attacks are always specific and empirical: As stated in the abstract of $2$ :

no single strategy would have been sufficient for all defenses [...] adaptive attacks cannot be automated and always require careful and appropriate tuning to a given defense

Thus, studies employing adaptive attacks are necessarily model-specific and empirical by trying different attack strategies tailored to specific models or defenses in order to find the strongest adversarial examples $1,2,3,4$ (if an exhaustive search is infeasible as it is the case already for small graphs). However, we do provide general design principles to develop adaptive attacks for graph transformers (and non-differentiable components in general). Furthermore, our specific relaxations can provide useful examples for similar components.

Applicability to other GNNs: Many of our findings can be used to attack other GNNs and GTs. For example, PEs are popular choices for different GNNs. As suggested in the Recurring Attack Theme T2 of $2$ :

only one or two $components$ would be sufficient for the defense to fail. Targeting only these components can lead to attacks that are simpler, stronger, and easier to optimize.

Conversely, from a robustness perspective, every component requires its own study regarding its robustness properties as it might introduce another vulnerability. This is further supported by our ablation study, indicating that any GNN using just one of these components can be attacked using our proposed relaxations.

Established attacks are general because they are transfer attacks: In fact, most established GNN structure attacks, such as Nettack $6$ and Mettack $7$ , are general and universally applicable for this reason: They are non-adaptive transfer attacks computed for a surrogate model. This is also described in $4$ :

Such transfer attacks are so common in the graph domain that their usage is often not even explicitly stated, and we find that the perturbations are most commonly transferred from Nettack or Metattack (both use a linearized GCN). Other times, the authors of a defense only state that they use PGD (aka “topology attack”) without further explanations. In this case, the authors most certainly refer to a PGD transfer attack on a GCN proxy.

In summary, adaptive attacks always require model-specific modifications/considerations. Our adaptive evaluation of graph transformers is already much more general than impactful works like Nettack $6$ and Mettack $7$ as they solely study (linearized) GCNs. However, prior work usually appears generally applicable since they only transfer perturbations. Thus, it should not be considered a weakness that adaptive attacks are model-specific. That adaptive attacks are model-specific is a general property of adversarial attacks and cannot be attributed to our work specifically. Nevertheless, for widespread applicability, we study a representative sample of GTs, spanning many frequently used components.