Adversarial Robustness of Graph Transformers

Authors: Philipp Foth, Simon Geisler, Lukas Gosch, Leo Schwinn, Stephan Günnemann
Primary area: learning on graphs and other geometries & topologies
Keywords: Adversarial Robustness, Graph Transformer

Abstract:
Existing studies have shown that Message-Passing Graph Neural Networks (MPNNs) are highly susceptible to adversarial attacks. In contrast, despite the increasing importance of Graph Transformers (GTs), their robustness properties are unexplored. Thus, for the purpose of robustness evaluation, we design the first adaptive attacks for GTs. We provide general design principles for strong gradient-based attacks on GTs w.r.t. structure perturbations and instantiate our attack framework for five representative and popular GT architectures. Specifically, we study GTs with specialized attention mechanisms and Positional Encodings (PEs) based on random walks, pair-wise shortest paths, and the Laplacian spectrum. We evaluate our attacks on multiple tasks and threat models, including structure perturbations on node and graph classification and node injection for graph classification. Our results reveal that GTs can be catastrophically fragile in many cases. 
Consequently, we show how to leverage our adaptive attacks for adversarial training, substantially improving robustness.

Decision: reject
Reviewer scores: 6, 6, 5, 5

Reviews and discussion:
<thread>
creation date:
1729893884308

thread_type:
official_review

<thread_object>
creator: reviewer_bec6

<content>
summary:
This abstract discusses the vulnerability of Graph Transformers (GTs) to adversarial attacks, contrasting them with Message-Passing Graph Neural Networks (MPNNs), which are known to be susceptible. Despite GTs' growing importance, their robustness is underexplored. The authors design adaptive attacks specifically targeting GTs by creating gradient-based attacks focused on structural perturbations. They evaluate these attacks across five popular GT architectures, examining how GTs handle attention mechanisms and positional encodings (PEs). Results indicate that GTs are extremely fragile in many scenarios. To address this, the study also explores how adaptive attacks can inform adversarial training to enhance robustness.

strengths:
1. This work provides an adaptive gradient-based structure attacks for GTs.
2. This work is the first to study the adversarial robustness of graph transformers
3. The presentation and writing are very clear and convincing

weaknesses:
1. The main weakness of this paper is the limited contribution. The adaptive attack is specifically designed for a particular defense, which limits its generalizability. It would be a significant improvement if the adaptive attacks could share a generalizable principle across all GTs.

2. As shown in the experiments, the relaxation technique is ineffective, and the adaptive attack is not strong enough. In Figures 3, 4, 5, and 6, there are many cases where the adaptive attack is weaker than the transfer attacks. In the ablation study (Tables 1,2 and 3), relaxing the non-differentiable operator does not achieve a better attack in some cases and only provides minimal improvement in others. Additionally, the experiments do not compare results with non-adaptive gradient-based attacks. As noted in the paper, "A good approach might be to
try all individually as an ensemble and choose the strongest. " This work, however, appears highly incremental and lacks universality. All of these findings raise concerns regarding the effectiveness of the proposed method.

3. The attack baselines are limited; the experiments only compare transfer attacks and random attacks, which is insufficient. Furthermore, the adaptive attacks do not seem stronger than the transfer attacks. Additional baselines, including metattack and nettack, should be incorporated.

questions:
See the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729898623634

thread_type:
official_review

<thread_object>
creator: reviewer_fpkq

<content>
summary:
This paper presents the first analysis of the adversarial robustness of Graph Transformers (GTs). The authors design adaptive gradient-based attacks for five representative GT architectures, including those with specialized attention mechanisms and Positional Encodings (PEs) based on random walks, pair-wise shortest paths, and the Laplacian spectrum. The results reveal that GTs can be catastrophically fragile to adversarial attacks, with even slight perturbations to the graph structure leading to significant performance degradation. Consequently, the authors show how to leverage their adaptive attacks for adversarial training, substantially improving the robustness of GT models.

strengths:
- This is the first study on the adversarial robustness of Graph Transformers (GTs), which have become popular alternatives to Message-Passing Graph Neural Networks (MPNNs).
- The authors design adaptive gradient-based attacks for five representative GT architectures, including those with specialized attention mechanisms and Positional Encodings (PEs).
- The results show that GTs can be vulnerable to adversarial attacks, with even small perturbations to the graph structure leading to significant performance drops.
- The authors use their adaptive attacks to develop an effective adversarial training strategy that substantially improves the robustness of GT models.

weaknesses:
- The mathematical formulas in the paper seem to appear out of nowhere, lacking sufficient explanation and intuition. For instance, in Eq. (6) ($\hat{w} = w + \log{A}$), the paper does not explain why the log function is necessary. Does the log function have special properties here? Providing a theoretical analysis to explain why such a design could help adversarial attacks would be very beneficial. The same issue arises in Eq. (7) (8) (9) (10).
- In Figure (1b), the attack effect for Graph Transformer （Graphormer, GRIT, SAN）seems not to be very well. Under small budget (for example, 5%), the accuracy drops are not very much compared with Figure (1a) and (1d). Could the author provide a further explanation?
- The writing is so confusing and needs to be improved. For example, the author directly use $deg(v_i)$ in Eq. (7) without any definition.
- The experiment setting has some problems. First, this paper lacks adversarial attack baselines. They should include both typical adversarial attacks and adversarial attacks for graphs. There should be many existing works, like [1, 2].
- If the authors want to validate the effectiveness of adversarial training, they should also compare it with typical graph adversarial defense methods, like [3]. In total, the experiments of this paper are obviously insufficient.
- The clarification of the experiment setting is also confusing. The authors list three different attack methods, but I cannot tell which one is proposed by this paper.

[1] Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem

[2] Graph Backdoor

[3] GNNGuard: Defending Graph Neural Networks against Adversarial Attacks

questions:
The same as the weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730490845395

thread_type:
official_review

<thread_object>
creator: reviewer_yz1c

<content>
summary:
This work explores the adversarial robustness of five graph transformer (GT) models. The author designs adaptive gradient-based attacks on five GT models to poison the model’s node and graph classification performance. This work is the first to show that GTs are commonly vulnerable to adversarial attacks and proposes leveraging adversarial training to improve GTs’ adversarial robustness.

strengths:
1. This paper establishes a good baseline for gradient-based adversarial attacks on graph transformers.

2. The work solves the problem of gradient-based structure attacks on GTs by introducing relaxation to attention scores.

3. The author has done explicit experiments on five graph transformers and types of attacks to validate the attack's effectiveness.

weaknesses:
1. There are some typos and explanations which are not clear. For example, the last adjacency matrix symbol in Equation (6) should be \tilde{A} not A. The author may explain what ‘H’ means in equation (3) as it was not shown or explained before. Also, the author may clarify that the adjacency matrix ‘A’ in equation (2) is already self-looped. 

2. The author explains different types of GTs in detail in the background section. However, the author may also need to clarify whether the attack is aimed at degrading performance on training data, test data, or both, and to provide a formal definition of the attack loss function used in their experiments.

questions:
1. Can the author provide concrete examples of potential real-world scenarios where these attacks might be relevant or impactful for each type of graph transformer discussed in the paper?

2. The author mentioned that the model output is discontinuous because positional encoding and attention mechanisms in GTs are designed for a discrete graph structure at the beginning of Section 3. Does this mean PEs and ATs are discontinuous because the adjacency matrix is discrete? Normally, the adjacency matrix becomes continuous values when you do the attack. Does this naturally solve the problem that PEs and ATs are discontinuous, so you do not need the relaxation on attention scores?

3. The author claimed in Principle II that the relaxed model function f shoule be continuous w.r.t continuous version of A. Can the gradient-based attack be conducted if it is continuous but not differentiated?

4. Can the author explain why introducing relaxation by adding the log of continuous edge probability to the attention score in equation (6) can solve the gradient problem? What’s the reason for this specific relaxation?

5. Is the method only adapted to PGD and PRBCD attacks? Has the author considered adapting it to other attacks like meta-attacks [1]? Can the author show some results?

[1] https://openreview.net/pdf?id=Bylnx209YX
</content>
</thread_object>

</thread>
<thread>
creation date:
1730666228346

thread_type:
official_review

<thread_object>
creator: reviewer_t2zt

<content>
summary:
This paper investigates the robustness of Graph Transformers (GTs) against adversarial attacks, a relatively unexplored area compared to the vulnerabilities of Message-Passing Graph Neural Networks (MPNNs). The authors propose adaptive, gradient-based structure attacks targeting GT architectures and evaluate these attacks across different attention mechanisms and positional encoding methods. Their findings reveal that GTs can be highly vulnerable to adversarial attacks, similar to MPNNs. They further demonstrate that adversarial training effectively enhances the robustness of GTs, providing a defense mechanism against these vulnerabilities.

strengths:
1.	The paper is the first to propose adaptive gradient-based attack strategies specifically for Graph Transformers (GTs), establishing a foundation for studying the adversarial robustness of GTs.
2.	The authors conduct multiple experiments across multiple tasks and threat models, demonstrating GTs’ performance under different attack budgets and highlighting their vulnerabilities to adversarial attacks.
3.	The authors propose an adversarial training strategy that reduces the hypersensitivity of some GT architectures, effectively enhancing their adversarial robustness and showing the potential of adversarial training in GTs.
4.	The paper is organized well, and the logic is smooth and convincing.

weaknesses:
1.	The attack approach lacks generalizability and is overly empirical, requiring specific design adjustments for each model rather than presenting a systematic method or architecture, making it more of an empirical study than a universal solution.
2.	The effectiveness of the "adaptive attack" is questionable, as it does not significantly outperform grey-box attacks. Non-adaptive attacks without relaxation should have been included for comparison, and the baseline comparisons are limited to weak black-box attacks (random and transfer), which diminishes the impact of the results.
3.	The selection of baselines for both attacks and defenses is insufficient. The study lacks comparisons with established attack methods like Metattack and Nettack, as well as with more diverse defense strategies, such as other robust training techniques, graph cleaning methods, detection techniques, etc.

questions:
1.	Could the authors include more attack and defense baselines?
2.	What is the performance of gradient-based attacks without relaxation?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732717431419

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank the reviewers for their helpful feedback to improve our work! Based on it, we now include interesting **new results and discussions**. However, we believe that the scores/feedback of some reviewers are guided strongly by some misunderstandings:
1) It is an impossible desiderata to request universal adaptive adversarial attack (that are efficient), as we argue in detail in the **'Universal adaptive attacks do not exist'** comment below. Thus, that our attacks do not capture all possible models/graph transformers should not be regarded as a weakness of our work, it is rather a general characteristic of adversarial attacks.
1) As we detailed previously in ll. 311-314, our transfer attacks are much stronger than the usual definition of transfer attacks, leading to doubts regarding the effectiveness of our adaptive attacks. In the revision, we moved the transferability analysis to a separate paragraph and figure (Fig. 7) with an improved explanation of the (relabeled) "best transfer" results. Furthermore, we added two new baselines to the main result figures (Fig. 3-6) that provide better context.  In the **'Effectiveness of our attacks'** comment, we explain in detail why our transfer attacks are already much stronger than commonly reported transfer attacks and that in comparison to a single transfer attack, our adaptive attacks are almost consistently stronger and often by a large margin.
5) Most attack baselines are incompatible with our setting, that is tailored to graph transformers. Nevertheless, we added two new baselines ("GCN PRBCD transfer" and "Random perturbation"). In the **'Requested baselines'** comment below, we explain in detail why certain baselines are not applicable in our evaluation setting.

To support these main points, we now provide a **revision** of our paper (uploaded). Notable modifications are shown in blue and include:
- **Two new attack baselines** (updated Fig. 3-6).
- Additional specification of the attack settings and threat models.
- Improved explanations for equations and notation.
- A separate analysis of the (best) transfer attacks (Fig. 7, and 11-14). 

Given these major clarifications, we would **appreciate a reevaluation of our work**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733162316877

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Discussion Period Closing Soon

comment:
We want to thank all reviewers again for their work and feedback that allowed us to improve the quality of our work. As the deadline to answer to our rebuttal very soon comes to an end, we would greatly appreciate a response if we could resolve the questions and concerns. Otherwise, we are happy to provide further clarifications.

Best regards,   
The Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733224809311

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of rebuttal phase

comment:
Dear AC, dear reviewers,

We thank again for the feedback on our work and believe that the revision of our manuscript improved as well as addressed the weaknesses. Since graph transformers are gaining importance, we believe that their robustness should not remain unexplored, and we show that graph transformers indeed can be critically vulnerable (sometimes more than message-passing models). However, with the attacks prior to our work, such findings were hardly possible. The changes in our manuscript triggered by the feedback further help us to convey this message!

While we are still awaiting the response of one of the reviewers, none of the other reviewers articulated any remaining weaknesses after our rebuttal, although one reviewer seems not fully convinced for unspecified reasons. As we elaborate in our rebuttal, the main points are:
1. We clarified that adaptive attacks are necessarily model-specific. Both reviewers who criticized this point thereafter increased their scores.
1. We altered the presentation to show the inadequacy of prior work for assessing the robustness of graph transformers and the efficacy of our attacks. Our adaptive attacks are almost consistently more effective (e.g., in 88% of the cases for budgets of 10% or higher) and often by a large margin (e.g. in Figure 6, our adaptive attack achieves 1% adversarial accuracy vs. 60% of second-best attack).
1. Most studies on adversarial robustness/attacks in the graph domain focus on settings where graph transformers do not excel. While the inapplicability of most prior methods prevented us from comparing to some of the requested baselines, it further shines light on how unexplored the studied setting is.

We believe that the matter of the adversarial robustness of graph transformers is a serious one and that our work will be a seminal work for further studies to come. We would appreciate it if the reviewers and area chair would carefully discuss our work once more and, importantly, provide guidance on how to improve if deemed insufficient – particularly important to the field due to the previously unknown fragility of graph transformers in some settings and for the study of strategies to remedy this fragility (like our adversarial training).
</content>
</thread_object>

</thread>
<thread>
creation date:
1772613026276

thread_type:
public_comment

<thread_object>
creator: ~lukas_gosch1

<content>
title:
Revised & Published Paper Version

comment:
The authors want to refer interested readers to [a revised paper version](https://openreview.net/pdf?id=4xK0vjxTWL) accepted at TMLR, awarded with a J2C-Certification, and selected for presentation at ICLR 2026.

Revised Paper Link: https://openreview.net/pdf?id=4xK0vjxTWL
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper explores the robustness of Graph transformers under adversarial attacks, proposes adaptive, gradient-based structure attacks for GT architectures, and evaluates these attacks against different Graph Transformers. Their findings reveal that Graph Transformers are also vulnerable to adversarial attacks, and leveraging adversarial training can improve GT's adversarial robustness.

Strength:
1. Explore the adversarial robustness of Graph Transformers.

2. Explore the adaptive attacks on different attention methods and position encoding methods in Graph Transformers.

Weaknesses:

1. Lack of baseline for attacks and defenses. Although the authors argue that many other attacks are not in the same setting (like perturbing features), I think it doesn't make sense as the attacker's goal is to fool the GT no matter which method is used. Unless the authors can convince the readers that the other attacks or defenses are not practical.

2. The authors further comment “Most studies on adversarial robustness/attacks in the graph domain focus on settings where graph transformers do not excel”. That also made me concerned about this work's importance, as GT's impact is also not strong enough as it has many problems as the authors mentioned. Furthermore, GT's efficiency is not good on large graphs. Therefore, I think it may not be a good time to evaluate robustness. Maybe the authors can manage to do attacks on Graph LLMs in their revision, its influence will be larger.


Although it's the first work evaluating the adversarial robustness of Graph Transformers, I don't think its findings on GT being vulnerable to attacks is a surprising result. Transformers are not robust on the image, sequential signal, and many other modalities. Therefore, I don't think anyone will believe GT will be robust even if no paper does such experiments. Then I would like to treat this paper as a paper for better attacks. Due to this reason, I think this paper needs comprehensive evaluations.

In summary, I suggest to reject this paper.