Adversarial Robustness of Graph Transformers
Authors: Philipp Foth
Lukas Gosch
Simon Geisler
Leo Schwinn
Stephan Günnemann
Venue: Accepted by TMLR ()

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. We close this gap and design the first adaptive attacks for GTs. In particular, 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 pairwise shortest paths, random walks, and the Laplacian spectrum. We evaluate our attacks on multiple tasks and perturbation models, including structure perturbations for node and graph classification, and node injection for graph classification. Our results reveal that GTs can be catastrophically fragile in many cases. Addressing this vulnerability, we show how our adaptive attacks can be effectively used for adversarial training, substantially improving robustness.

Published in Transactions on Machine Learning Research (09/2025)
Adversarial Robustness of Graph Transformers
Philipp Foth'
p.foth@lumm.e
School of Computation, Information and Technology Technicol University of Munich
Lukas Gosch
Lgosch@tum.de
School Computation, Information and Technology & Munich Data Science Institute Technical Universiby of Munich;; Munich Center for Machine Learning (MCML)
Simon Geisler
geiislen@tum.de
School of Computation, Information and Technology & Munich Data Science Institute Technical University of Munich
Leo Schwinn
Aschwivon@tamm.cm
School of Computation, Information and Technology & Munrch Data Science Institute Technicol University of Munich
Stephan Günnemann
School of Computation, Information and Technology & Munich Data Science Institute Technicol University of Munich; Munich Center for Machine Learning (MCML)
Reviewed on OpenReview: https: // openeevee.. net/ pet//orum? id 4aKOvjaTWL
Abstract
Existing studies have shown that Passage-Passing Graph Neural Networks (MPNNs) are highly susceptible to adversarial attacks. In contrast, despite the increasing importance of Graph Transformers (GTss, their robustness propertics are unexplored. We close this gap and design the first. adaptive attacks for GTs.. In particular, attacks GTss w.r.t. structure perturbations and instantiate attack framework for five representative and popular GT architectures. Specifically, we study GTs with specialized atlention mechanisms and Positional Encodings (PEs) based on pairwise shortest paths, random walks, and the Laplacian spectrum. We evaluate our attacks on multiple tasks and perturbation models, including structure perturbations for node and graph classification, and node injection for graph classification. Our results reveal that GTss can be catnstrophically fragile in many cases. Addressing this vulnerability, show how adaptive attacks can be effectively used for adversarial training, substantially improving robustness.
provide general design principles
for strong gradient-baat
1 Introduction
Graphs are fundamental data structures with broad applications across various domains. In recent years, Graph Neural Networks (GNNs) have become the go-to method for learning on graph-structured data. Given their growing adoption, numerous studies have explored adversarial attacks on GNNs, revcaling their susceptibility to even minor perturbations the graph structure (Zigner et al. 2018 Zügner & Günnemann] 2019 Zügner Günnemann, 2020). These studies mainly focus on Message- Message-Passing GNNs (MPNNs), such as Graph Convolutional Networks (GCNs) (Kipf & Welling (017). More recently, Graph Transformer (GT) models have emerged promising alternative, addressing key limitations of MPNNs,
"Equal contribution. Correspondeuce should be addressed Lgosch@tum.de..
Now with Google Research.

---

Published in Transactions on Machine Learning Research (09/2025)
Graphormer
GRIT
SAN
GPS
GPS-GON
Polynorme
GATv2
GAT
GON
Accuricy (%6)
60
400
20
0
20
10
15
20 15
Edge modification bodget (96)
Edige modifccaiion budget (56)
Edge modification budkgot (36)
Edge modification bodget (5))
(a) CLUSTER.
(b) Reddit Threads.
(c) UPFD politifact.
(d) UPFD gussipcop.
Figure 1: The adversarial classification accuracy for different GNNs with varying (ovasion) attack budgets on
four different datasets: CLUSTER- inductive node classification (global structure attack), Reddit Threads graph classification (structure attack), UPFD politifact and gossipcop graph classification (node injection attack). The strongest attack (out of 9, see Section 5 for more details) for each budget is shown.
such as over-smoothing, over-squashing, and limited receptive fields (Müller et al. 2024). Despite their growing popularity, the adversarial robustness of GTss is unexplored and hence, unknown. This gap highlights crucial limitation in our understanding of GTss and poses risk in practical applications where robustness is critical. However, to understand their robustness, it is not possible to directly apply state-of-the-art attacks for GNNs, such as PGD (Xu et al. 2019) and PRBCD (Geisler et al. 2021] as GTs employ modified attention mechanisms and Positional Encodings (PEs) that are not differentiable w.r.t. the input. Consequently, the lack of good tools to evaluate the robustness of GTs makes difficult to understand the robustness properties of different GT models, to determine which models or components are preferable in safety-critical settings, and to apply state-of-the-art. defense mechanisms such as adversarial training (Gosch et al. 2023al)
To address this challenge, we establish general guiding principles for designing differentiable relaxations to the discrete and non non-differentiable components in GTs. In doing so, we provide a general outline on how to design strong gradient-based adaptive attacks for GTTs that can adjust to all relevant architectural details. Such adaptive attacks are essential for realistic robustness estimates in the vision domain (Athalye et al.)
2018 Carlini& & Wagner 2017 Tramèr et al. 2020) as well as the GNN domain (Mujkanovic et al. 2022). We exemplify our guiding principles by developing specific relaxations for the most widely used GT components including (a) Shortest Path, (b) Random Walk, and (c) Spectral PEs. Using our relaxations, we provide the first analysis of the robustness of GTs by applying adaptive gradient-based attacks to five popular and representative GT architectures: 1) Graphormer (Ying et al.] 2021), 2) Spectral Attention Network
(SAN) (Kreuzer et al.) 2021b, 3) Graph Inductive bias Transformer (GRIT) [Ma et al.] 2023), 4) General, Powerful, Scalable (GPS) GT (Rampášck et al. 2022), and 5) Polynormer Deng et al. 2024
Our study reveals that GTs can be catastrophically fragile evaluated with our adaptive attacks (Fig. 1 For example, with our proposed node injection attacks (NIAs), perturbing 2% of the edges can halve the model's accuracy (Fig. Ic & Id.. Consequently, use our adaptive attacks to devise an effective adversarial training strategy and show its polential to alleviate the hypersenstiivity of GT architectures.
Our main contributions are:
(1) We formulate general guiding principles to relax non-differentiable GT (Graph Transformer) components. Based on this, we develop the first adaptive gradient- based structure attacks for five representative GT architectures. Our developed relaxations concern the most common building blocks found in GTss and thus, can find application across many different GT models.
(2) We conduct the first principled empirical study into the adversarial robustness of GTs and show that they can suffer from catastrophic vulnerabilities to even minor perturbations of the graph's 's structure, in some cases even worse than traditional message-passing GNNs.
(3) We show how to leverage our adaptive attacks for adversarial training strategics that can result in an effective defense counteracting GTs' vulnerabilities Thus, we establish that the ficxibility of GT models can lead to significantly better robust learning capabilities compared to classic message-passing GNNs.
2

---

Published in Transactions on Machine Learning Research (09/2025)
2 Preliminaries
Let G = (V) be an undirected attributed graph with n nodes V= {Ui, ..., Unf and m edges. Let H, E R be the feature vector of node v;. Then the graph can be defined as g = (A, X) with its symmetric binary adjacency matrix A E (0.1) 1 and node feature matrix X E R The diagonal degree matrix D with entries A; and the normalized symmetric graph Laplacian matrix Lyym = =I D- can both be derived from A. The GNNs considered in this work functions fo(A, X) with model parameters 0 e RP. We denote the updated hidden node representations after each GNN layer as H with initialization H = X. For node-level tasks, we assume that each node should be assigned a class c E (1..... K} and the output node representations are directly utilized for the prediction, while for graph-level tasks, a graph-pooling operation aggregates the node embeddings into a graph embedding before predicting one out of K classes for the whole graph.
D = [
2.1 Structure Attacks
In this work, we focus on untargeted white-box evasion attacks, i.e., an attacker with full knowledge of the model and data attempts to change the trained model's prodiction 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. The attack objective is described by the following optimization problem:
max s.t. AlosA Luck (fo(,foA,
(1)
where fo is the GNN model with fixed parameters 0, Á {0, is the discrete perturbed adjacency matrix in relation to A with the number of edge flips bounded by the budget A E No, and Lotk is a suitable attack loss function. For node classification, we use the tanh-margin attack loss proposed in Geisler et al. (2021). For graph classification, we optimize the unnormalized class logits: Latk -ly + Eezy les where te ER refers the unnormalized logit of class E (l,..., K). It is convenient to model the perturbation function of the binary matrix indicating the edge flips B {0,m)>>m
A= 5A,
8A = (1, 2A) O B
(2)
with element-wise product @. Often, the combinatorial problem in Eq. 1 can be optimized more efficiently using continuous relaxation B' E [0, 1jnx= replacing B in Eq. In this setting, the entry By represents the probability that the edge (u,, vy) is flipped. Then, the discrete perturbation matrix can be sampled from the continuous solution. In the continuous relaxation, the budget constraint bocomes [[Bernoulli( (B')] B' A, which can be dealt with by using projected gradient descent. (Xu et al. 2019). Note that a continuous B' gives risc to a continuous Á' E 1]*x,, whose clements A',, can be interpreted as the probability edge (i,j) being in A. For large graphs, updating all entries in B' at once becomes infeasible. Projected Randomized Block Coordinate Descent (PRBCD) solves this by optimizing over sampled random blocks of limited size Geisler et al. 2021
2.2 Graph Transformers
Graph transformers (GTs) apply the popular transformer architecture for sequences (Vaswani et al. 2017 to arbitrary graphs. A general GT architecture is depicted in Fig. 2 In this work, we focus on GTs that apply global self- atlf-attention, where each node can attend to all other nodes. A "vanilla" structure-uaaward self-attention head is defined as:
(HW,) (WW))HWW) (HW))
Attn(H) softmax
(3)
Vd
where WG WR, W, Rdddd are the weights for the query, key, and value projections. The individual attention scores can thus be defined as:
enyy
W h W h
Og = soyt
= Σn k euin?
wi
(4)
/d
3

---

Published in Transactions on Machine Learning Research (09/2025)
#''
Since this update is independent of the graph structure, many GTss apply modified attention mechanism that also depends on the adjacency matrix. Additionally, crucial and most common way to add structural information is by adding Positional Encodings (PEs) to the node features:
Modified Attention
IxLayes
v
H + (A)
(5)
where v represents the positional encoding of choice. Some architectures append wb to X instead of summing, or otherwise jointly process X and (b)). We categorize PEs roughly into three main categories: (1) distance encodings, (2) spectral encodings, and (3) random walk encodings. Some works distinguish between Structural Encodings (SEs) and PEs, where the term SE is used for encodings that make the GT aware of graph structure and the term PE for making node aware of its relative position. However, there is no formal distinction between SEs and PEs (Müller et al. 2024) and for the purpose of this work, we do not semantically distinguish belween SEs and PEs and use the term positional encoding to refer to any encoding based on A. Next, we describe the PÉs and attention mechanisms of the five representative GT models that we attack. For detailed overview and taxonomy of current GTss we refer Müller al. (2024).
Posttional Encoding
Figure 2:
A
generic graph transformer.
Graphormer (Ying et al., 2021). For the PEs, degree embedding vector za E IRd is learned for each discrete node degree value d. The embeddings are added to the node features according to the node degrees:
h (0) = a. + 2deg(us)
Similarly, a Icarnable scalar b, E R is assigned to each discrete Shortest Path Distance (SPD) s SE No. This value is added to the raw attention scores and results in a re-weighting of the attention weights between two nodes based on their distance in the graph:
Bij Wij + (ppd(n).))) Oiy = (1i))
(7)
where Way is set following Eq. For graph-level tasks, virtual node is added to the graph with its own distinct learnable bias Wirtual, which is used as graph representation in the pooling stage.
Spectral Attention Network (SAN) Kreuzer et al. 2021). SAN uses learned (spectral) Laplacian-based PEs that are based on the degoppecconooiiionn of the Laplacian Leym = UAUT, where the diagonal entries of A; = X; are the eigenvalues of Lym in ascending order Àι S X2 S ... I An, and the columns of U are the corresponding eigenvectors. The PL's are computed by a learned transformer encoder that takes the k smallest eigenvalues, which we denote by A₁ E R and their corresponding eigenvectors Uy Rax input. Concretely, for each node Us its PEs are initialized as the concatenation of the eigenvalues and the i-th row of Up:
P. = [diag(As) || (Ux).] E 2x2
Further processing by a transformer encoder results in p: f(P:) E Rd,, which is concatenated to the node features: h.()) = x; Pt- Regarding the main graph transformer attention mechanism, modified to have two separate key and query weights for connected and unconnected node-pairs. The attention scores to the connected nodes and to the unconnected nodes are computed independently, each with a softmax. A hyperparameter y R controls how the two scores are relatively scaled, varying the bias towards sparse full attention:
softmaxN, (W WT Wimnats,/a) if (w, uz) is real edge Oij softmaxy (.ath WTT (.
otherwise
where M; is the first-order neighbors of node v, (including vz).
Graph Inductive Bias Transformer (GRIT) Ma al. 2023 GRIT's PEs based random walk probability matrices for walks of lengths to k - 1. Concretely, the PEs are based on 3D tensor:
P [I, M, M
M Raxxxk with M = D-1A
(10)
4

---

Published in Transactions on Machine Learning Research (09/2025)
This yields embedding vector P.y E IR*t for each of the n² node-pairs (i, vy). The diagonal vector entries are transformed to dimension by a lincar layer and added to the node features as PEs: h; = 2; + 91 (Px). Additionally, all n² vectors are transformed by a separate linear layer and added as node-pair features: h (P.): The node representations h; and node-pair representations haj are updated in each transformer layer by modified altention mechanism, which includes an adaptive degree-scaler that is applied to the node representations:
hi,upaaee (h: 2 01) + log(1 + (e)((;)) (h, @ 02)
(11)
where 02 E Rd are learnable weights.
General, Powerful, Scalable (GPS) Graph Transformer (Rampásek et al. 2022 GPS is modular framework that first consists of a positional encoding of choice that is concatenated to the node features and again processed with an MLP before being passed through L GPS layers. Each GPS layer combines the local message passing of an MPNN with a global attention update as follows:
fcPs H, A) MLP (fMPNN (,, A) fGlobalArtn (H)
(12)
There several different choices of PEs, MPNNs, and global attention mechanisms tested by Rampášek et al. (2022). We consider the configuration with (spectral) Laplacian PEs that are encoded using DeepSet [Zaheer et al. 2017) (compared to a transformer encoder in SAN), local GatedGCN (Bresson & Laurent 2018) as an MPNN, and standard transformer global attention (see Eq. 3) as this configuration choice the most common one by Rampášek et al. (2022).
Polynormer (Deng et al., 2024). In the Polynormer model, the input is first processed by Liocal local message passing layers and then by Eyglball global attention layers. Notably, PFs are not used. For both type of layers, the node representation update is defined by second-degree polynomial equation of the form (omilting normalizat ions and activation functions):
Hupdate = (SHW,) @ (HW, - (131)), with attention matrix S = (A,,
(13)
where a is the sigmoid function and each layer has learnable weights W. W E Rddd and E Rd, To calculate S, for local layers, the local attention mechanism from GAT (Veličković al., 2018) used. For global layers, linearized global attention mechanism is used based the kernel trick. Instead of computing the softmax after the query-key multiplication (Eq, an element- sigmoid function is applied separately to the queries and keys. Then simple row-wise normalization ensures that rows sum to one:
Wi
Wyy = hW. hz
(14)
Σ
Wik
where Wg: We are the query and key projection matrices. Since the nonlinearity is applied before the multiplication, the order of operations can be changed to avoid computing the full attention matrix S, reducing complexity from O(n'd) to O(nd)). Thus, Polynormer is type of GT that achieves linear complerity in the number of nodes.
3 Attacking Graph Transformers
The main obstacles for gradient-based structure attacks GTss are PEs and attention mechanisms that are designed to operate on the discrete graph structure. As result, even if one wants to solve the associated optimization problem in Eq. 1 for a relaxed continuous adjacency matrix Á', the GT model fo is often discontinuous and cin-differenti w..tt. Á', making contimuous optimization through gradient- based attacks inapplicable. Thus, to enable obtaining useful gradients, we ncod to relax the structuro-aware components such as PEs and specialized attention mechanisms in fe, giving rise to a relaxed GT model fe. For designing effective continuous relaxations that lead to useful fo, we identify three main principles:
5

---

Published in Transactions on Machine Learning Research (09/2025)
Principle Relaxed and target models should coincide for discrete inputs. The prediction should equal (A( = (A) for any discrete adjacency matrix A (0,1)
Principle II: fo can interpolate between any different discrete graphs. In other words, (A') should be continuous w.r.t. A', and it should be differentiable almost everywhere w.r.t. A'.
Principle III: The relaxed model Sa must be efficient. It is a critical property that the relaxation does not excessively increase the memory and runtime complexity.
We do not require continuous differentiability in Principle II, as to obtain informative gradients w.r.t. the input data to effectively optimize the attack loss, we do not need to enforce stronger standards on fo than imposed by the perhaps most widely used activation function ReLU, which also continuous and differentiable almost everywhere except at O. We discuss Principle II and the differentiability requirement in more detail in G.. Now, below, we develop continuous relaxations for several common GT's that follow the above outlined principles and thereby, enable the effective application of statc-of-the-art gradient-based graph structure attacks as described in $ 5 Next to covering commonly used GT components, the following derivations should act as guiding examples on how to instantiate the above principles to develop effective continuous relaxations that enable strong adaptive attacks for a GT architecture or component of choice.
Graphormer. The degree PEs Edeg(e;) in Eq. 6 and SPD biases (spd(v..,,) in Eq- are indexed by the discrete values of the node degrees (# of neighbors) and shortest path distances (# of hops). To enable the use of continuous degrees, we define a linear interpolation between the PE vectors of the two closest integer degree values:
de)(( = 17 zdi+1 + (1 - 11) Ed.
(15)
with di = [deg(u))] and 17 deg(v;) di
Increasing the edge probabilities to a node also increases the expected discrete degree. However, the edge probabilities are more challenging to interpret for the SPDs. When very small edge probability lies on a (simple) shortest path, the path is less likely to exist in the discrete sampled adjacency matrix. Therefore, low edge probabilities should only marginally affect the original SPDs. To model this relationship, we use the reciprocal of the adjacency matrix R. = 1/,, to find continuous proxy shortest path distances rspd,y = spd(u;, uj] R). We interpolate between the closest discrete values again and obtain:
(s)d(e),e)) 11 ba.+1 + - 11) bs
(16)
with s [rspd,y], and 77 rspd.j st
Note that for discrete edge probability values 0 and 1, the reciprocal edge weights become -0o and 1, respectively, yielding the original SPDs. Hence, we do not alter the clean predictions if 8A = B = 0 (see Principle T).
SAN. We first discuss how to relax SAN's attention mechanism before discussing how to tackle relaxing the spectral PEs. To allow for smooth transition between SAN's two separate sparse attention mechanisms in Eq. g we formally convert both to full global attention. Then, the goal of the relaxed sparse attention mechanisms is to properly weigh the contribution an edge has the attention score calculation by the probability N'g that the corresponding edge is in the final perturbed adjacency matrix. This can be achieved by adding the log-probabill probabilitiees of the edges belonging to one of the attention mechanisms in Eq. 9 to the attention logits, where the corresponding probabilitics are P.j = Á' for the sparse attention originally defined over N,, and Pij = 1 Ai, for the sparse attention originally defined over V (N1, as one obtains
Dij = Wij + +lg((Ht))
Pij e
(17)
āig- = (aitmax(@i;)))) = Σn eiu
Ee Pik e
As a result, for discrete connected edge Kl = 1, the pogaaabbasiiiies become 0, or -oo respectively. Thus, such edge still fully contributes to the connected attention mechanism (over NG), while not affecting the

---

Published in Transactions on Machine Learning Research (09/2025)
disconnected one (over V WG) and vice versa for disconnected edges with A/, =0. Thus, the relaxation in essence still is sparse attention mechanism and the discrete output remains unchanged (see Principle I), while interpolating smoothly between any different discrete graphs (see Principle II). Some care has to be taken so that the gradient computation w.r.t. A' is numerically stable, which we discuss in $ G.2 Here we want to nole that the so-developed sparse attention relaxation can be generally applied to any sparse attention mechanism used in other GTs, which we demonstrate when deriving a relaxed Polynormer model at the end of this section.
Now, regarding the spectral PEs, note that the Laplacian matrix itself is continuous function of the entries in the adjacency matrix. However, its eigen-decomposition used for the PEs poses some challenges for gradient computation, especially w.r.t. the eigenvectors. The problems arise because: (a) the choice of direction (sign) for eigenvectors is arbitrary, (b) the choice of an eigenvector-basie of the eigenspace of a repeated eigenvalue arbitrary, thus the gradient not well defined, (c) for eigenvalues that are close together, the corresponding cigenvector gradients are mumerically unstable. To avoid direct gradient computation, we use results from mairix perturbation theory (Stewart Sun 1990 Bamieh 2022) to approximate the perturbed sigen-decomposition simpler function of the input perturbation. We define the perturbation the Laplacian as 8Lsym Lawn
L sum, where Eyym is the Laplacian of the perturbed contimuous adjacency 2022), the first-order approximations for the eigenvalues and eigenvectors are:
matrix A'. Following Bamich
À A + SA,
T SA ~ diag(U OL U)
(18)
Ú = U + SU,
UU -U (II
④ (UTLL. U))
(19)
if #
with II 1j
else
However, when repeated cigenvalues are present the unperturbed Laplacian, special care for the choice of the eigenvectors in U that span the eigenspaces of the repeated eigenvalues is required. This case is treated by [amiih (2022) and we show the application to our case in FF.1 A different strategy used by e.g. Lin et al. [2022] consists of adding bit of random noise to Laym in hopes of breaking apart any repeated cigenvalues, such that is possible to directly backpropagate through the eigen-decomposition. We claborate
on this strattey and propose our own alternative in $ F.2
GRIT. Relaxing the perturbed adjacency matrix Á to be used in Eq. 10 to be continuous and allowing for fractional node degrees in Eq. II one can see that the so relaxed GRIT model fulfills all three main principles for continuous relaxations outlined above. Thus, as only GT architecture, GRIT and its used random walk emboddings do not require special treatment beyond relaxing A to be continuous, to yield effective continuous relaxation.
GPS. As GPS' Laplacian PEs only differ to SAN's by using a DeepSet encoder instead of a transformer encoder, we can use the same relaxation as derived for SAN in Eqs. 1 & 19 Note that Rampášck et al. 2202 lists six different categories of PEs, which they group into local, global, and relative positional encodings and local, global, and relative structural encodings. Most of the example encodings provided for each category random walks. Thus, they are based on distances (shortest paths), node degrees, spectral decomposition, can be directly tackled by the relaxations developed for Graphormer (Eqs. G & 7 SAN (Eqs. 18 & 19 GRIT. This highlights the common and widespread usage of distance, spectral, or random-walk encodings and thus, the broad applicability of our developed PE relaxations to other GT models.
Now, we turn to the GPS layers defined by Eq. 12 The global attention fGiobalAtta requires no modification, as does not depend on the adjacency. However, we need take closer look at /MPNN for which GPS uses GatedGCN. The update of the local GatedGCN step for the embedding of node defined as:
(
h hupdote = h4 +
W Wmih
Σ ny @ Waehy BEEA
n. =
Σ nO M
(20)
with edge gates Mi = a (Weih; + Wo)h))
where WT1, Wn., Wea, We are the learnable parameters and p is the activation function. The edge gates Mi E Rdd can be interpreted per-dimension local attention weights and control the aggregation strength
7

---

Published in Transactions on Machine Learning Research (09/2025)
from each neighbor. Thus, to achieve continuous relaxation, we can define that node vj E if A', 0 and scale the edge gates by the probability that the neighbor node is connected:
iij = Pij Thjs
Pij = A'
(21)
This is in line with the way how other MPNNs such as traditional GCN are relaxed to allow for gradient-basod structure attacks (Geisler et al. 2021
Polynormer. The global attention mechanisms defined in Eq. 14 does not depend on the adjacency. Thus, relevant to deriving a relaxed model is how the attention matrix S in Eq. 13 is calculated for the local layers based on the local (sparse) attention mechanism from GAT. For this, recognize that the i-th row of the result. of the matrix product S that concerns the intermediate embedding updute for a node i after sparse aggregation and before the application of the dlmenntwwise multiplication in Eq. 13 can be written as:
hi,update =
aiy CaywWhhh Osjj = softmaxx, (wig), Wij p (a Wh, + af Wh;)
(22)
where p is an activation function and W, ag ag are the learnable parameters. Now, structure information enters the sparse attention computation for aij through attending only to the neighbors NG. To relax this sparse attention mechanism, attention in Eq. g by formally converting the sparse Oıj computation (and summation) in Eq. 22 to full attention and adding log Pij as bias to the attention logits Wij with Pij = A This highlights the general applicability of the relaxed spanse attention developed in Eq. 9 for SAN to other sparse attention mechanisms deployed in other GT models. Note that in contrast to relaxing an MPNNs aggregation through scaling each summation (aggregation) term by A'y,, the scaling for the relaxed sparse attention is already included in the oij computation. We close this section by noting that Polynormer does not use PEs and hence, we do not need to develop relaxation for them.
can use the same continuous relaxation derived for SAN's sparse
Pij
Computational Complexity. All our relaxations adhere to Principle III of efficiency and do not excessively increase runtime or memory complexity. In particular, the relaxations do not affect the asymptotic time complexities w.r.t. the number of nodes or edges of the models. We discuss the computational complexities of our relaxations in more detail in $ G.3
4 Node Injection Attack
We also considor the relevant case of insorting nodes into an existing graph structure. In contrast to the usual framing of Node Injection Attack (NIA), where the allacker also chooses the node features for the new vicious nodes WWang al., 2020), we connect existing nodes from other graphs of an inductive graph dataset. (excluding their own connections in the other graph). Therefore, the nodes" features are fixed but physically realizable even if, e.g., they represent embeddings of natural language. This alleviates us from somewhat subjective definition of imperceptibilitty required to craft the node features in the existing NTA. Hence, our attack solely focuses on "structure" perturbations and their influence on the PEs, which are of particular interest for attacking GTB.
We formulate our node injection attack as a structure attack on an augmented graph that includes both the original nodes and the set of potential injection nodes. This formulation enables the use of the same PRBCD atlack optimization, where the edge flip budget constraint also serves as an upper bound for the number of nodes that can be injected. We provide the details of extending PRBCD to node injection in
Node probability for smooth node insertion. The contimous optimization of structure attacks in 2.1 assigns probabilities to edges-flips, while nodes are assumed to be part of the graph. In contrast, during NIAs nodes also have certain probabilities of being included. To approximate these node probabilities from the odge weights in a general way, we propose a simple iterative computation. We can calculate the probability ps of i4 being connected to the graph, by using the probability of being connected its neighbors and the probabilities that these neighbors themselves are connected to the graph. We start with the assumption that.
8

---

Published in Transactions on Machine Learning Research (09/2025)
all nodes are connected to the graph and update using the edge probabilities:
(++1) Pi
=1
II (1 (1-Al, pf"), with p!0=1 = MyE
(23)
To ensure that the model output is continuous w.r.t. node injections, this node probability is used to compute weighted sum or mean in the graph-pooling for graph level tasks. Additionally for GTs, we use the node probability to bias the global pairwise attention scores which result in continuous weighting of the attention scores analogous to Eq. 17 where the bias probability is set to the node probability Pij = Pj. Notably, this node probability bias can be applied to any global attention mechanism even when it originally does not depend on the adjacency matrix (as is the case for e.g. GPS and Polynormer).
An ralustrative example shown in $
5 Evaluation
In what follows we describe the experimental details for our reported results. The code to reproduce our results can be found at
Datasets. We first evaluate our structure attacks CLUSTER (Dwivedi et al. 2023 which contains SBM-generated graphs with 6 clusters. A single node in each cluster is labeled and the task is to predict the cluster of all nodes (inductive node classification). We also consider the graph classification dataset Reddit Threads (Rozemberczki et al. 2020). It contains many small graphs (without node features) that represent users that are connected if they directly reply to each other in the thread. The task is to predict whether the thread is discussion-basse based or not. For our node injection attacks, we evaluate on the UPFD fake news detection datasets (Dou et al.] (022)). There are datasets: politifact, with political; and gossipcop with celebrity fake news. The graphs consist of "retweet" trees, where each node contains the user features and the edges represent retweets. Additionally, the root nodes contain features related to the news content and are consequently not considered for node injection. We do not perturb the original graph structure and if node ion does not result in a tree structure, we lake the maximum spanning tree to ensure that all perturbations are valid retweet trees. The task is binary classification of whether the graph contains fake news or not. Further details of the datasets and splits used are given in & B
Due to GT's (usually) quadratic scaling in the number of nodes, their application is limited to smaller graphs. While GTs are most widely applied to molecule data, adversarial attacks are of little practical relevance in that domain. Thus, we omit molecular datasets from our evaluations.
Models. We investigate the five representative GT models for which we developed continuous relaxations in $ $3 Graphormer, SAN, GRIT, GPS, and Polynormer. For their model training we do a hyperparameter search, choosing the model with the highest validation metric and we describe the hyperparamter search and the final hyperparaneters used for the models in $
Attacks. As explained in $ 2.1 study untaryeted global evasion attacks. Global applics to the task of node classification and means that our attacks try to decrease the overall accuracy of all (test) node predictions in the graph. This is more challenging than local attacks, which only attack a single victim node prediction such as Nettack (Zügner et al. 2018),, which cannot be effectively used for a global attack. Evasion means the graph structure of the test input is modified for a trained model with fixed weights. This is different from poisoning attacks such as Mettack (Zügner Günnemann 2019),, where the victim model is trained on the perturbed graph. Poisoning is much more relevant for transductive learning tasks (often on single graph), for which GTs are rarely used.
We show results for 5 different attack types. Adoptive PRBCD uses relaxations described in $ for a gradient-based PRBCD attack. Random perturbation is a simple bascline, where a single random perturbation of the adjacency mairix is used. In contrast, random allack is a brute-force random search that tests many random perturbations and selects the best. To match the computational budget of the adaptive attacks, it gets the same number of model evaluations. The GCN PRBCD transfer attack transfers the perturbation computed from attacking a GCN with an (adaptive) PRBCD attack, to the GT models. This relatively strong baseline attack that follows the same principle as many other established GNN attacks: it is a
9

---

Published in Transactions on Machine Learning Research (09/2025)
zazdom pertutbation
razdom attack
GCN PRBBCD crutader
adaptive PRECD (owss)
Accorti (16)
43
23
23
20
20
Edge budget
Edge mod. budget (56)
Edge mod. bradgct (36)
Bdge mod. brdgeet (16)
Bdge mod. brdggtt
Edge budget
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) GPS.
(e) Polynormer.
(I) GCN.
Figure 3: Global structure (evasion) attack results for CLUSTER (inductive node classification).
based attack (PRBCD) on a simpler surrogate (GCN) that gets transferred to the victim model. Moreover, it is the main (global evasion) attack for non-GCN models proposed and used by Geisler et al. 22021), where it has been shown to be very effective against other GNNs. Finally, we study how the adaptive attacks for the individual five considered GTss transfer one another. Fig. shows the best out of all applied attacks (including the individual GT transfers) for each investigated model and dataset.
For all datasets, evaluate our attacks the 50 first graphs in the test set and report average and standard deviation over 4 random seeds. For UPFD node injection, we use small block size of 1000, which is necessary due to the quadratic scaling of GTss We optimize all our adaptive attacks for 125 steps and sample 20 discrete perturbations from the result, of which we take the strongest. For all other attack hyperparameters, we use default values that performed well in preliminary evaluations. For all main results, we use all of our continuous relaxations proposed in 3 We report and discuss ablation results using different combinations of relaxation in $ C.5
6 Attack Results
In this section, we present the first principled analysis on the robustness of Giss on five representative architocture types (Graphormer, GRIT, SAN, GPS, Polynormer) enabled by our developed adaptive attacks based on our general principles for continuous relaxations outline in $ 3 We define different goals for our evaluation: (A) efficacy of the proposed adaptive attacks, (B) providing an accurate assessment of GT robustness for relevant real-world tasks. To this end, we perform our evaluation on datasets with varying complexity. Towards (A) we explore the robustness of GTss on CLUSTER and Reddit Threads, which comprise simple, interpretable structures. This exploration helps us evaluate the effectiveness of the proposed relaxations, idcally leading our attacks to target semantically meaningful structures within the dataset. We address (B) through evaluations on UPFD. Here, we constrain our allack to remain within the predefined tree structure of the dataset. As a result, the attack represents impersonating an existing user who retweeting the respective news article. This evaluation goes beyond previous robustness analysos of citation networks in GNNs Zugnner et al.] 2018 Geisler et al. 2021). offering a more practical use case and semantically meaningful attacks (Hu et a 2024 Wang et al. 2023b). We quantify and measure the semantic unnoticability of our
attacks on the UPFD datasets in $ C.6
CLUSTER. Across all models, our adaptive attacks result in the strongest perturbations except for the smallest budgets, as shown Fig. 3 The effectiveness of the random perturbation baseline indicates an inherent fragility of the data. Intuitively, since only single node in each cluster is labeled, attacking these labeled nodes requires little budget and leads to strong attacks. We manually inspected the adaptive attack perturbations and confirmed that most edge modifications of the transfer attacks also indicates that the straightforward nature of the task leads to the same type of semantically meaningful model-indepennden. perturbations. This outcome positively indicates the effectiveness of our adaptive attacks (A), as they consistently identify meaningful perturbations across all GTs. To avoid the natural fragility in the data, we also evaluate a constrained attack that prohibits modifying edges the labeled nodes, for which results are shown in $ C.1 In $ C.7 we evaluate and show the efficacy of our adaptive attacks in local attack setting. The worst-case perturbation results for all models, including GAT
connected to the labeled nodes. The strength
10

---

Published in Transactions on Machine Learning Research (09/2023)
sazdom perturbation * random attack
GCN PRBCD crunader
adaptive PRECD (ows)
Accuray (86)
13
05
70
Ddge mod. budget (38)
Edge brodget
Edge budgee
Edge mod. budget (%6
Edge mod. brdiget (%5
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) GPS.
(e) GCN.
Figure Structure (evasion) attack results for Reddit Threads (graph classification).
moneomm parturbation
candomm
CCNN PRECD trauradeer
silaption PRRCI (ours)
Aucunee 186
82
42-
83
100
Bige mod. Sudges (56)
Edee mod. brdggtt (55
Edge mnd. brdget (5)
Edge and budget (50)
Edge mod. budget (80
Bdge mod. budggs (25)
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) CPS.
(e)
Polynormer.
(I) GCN.
Figure 5: Node injection (evasion) attack results for UPFD gossipcop (graph classification).
and GATv2 (Brody et al. 2022), are shown in Fig. For these smaller budgets, the GTs are consistently more robust than the MPNNs, though their clean accuracies are also higher.
Reddit Threads. Fig. 4 shows that our adaptive attacks are significantly stronger than the baselines. SAN is the exception, where the adaptive attack is worse than transferring from GCN. This could be due to the perturbation approximation adding noise to the gradient updates, or because it results a harder optimization function. For most models, the adversarial accuracy drops close to zero when up to 80% of the edges can be modified. This likely because there are no node features and the prediction relies only on the graph structure. Interestingly, the random attacks never seem to work well, indicating that the gradient. information provided by relaxations is extremcly helpful for finding good perturbations. Fig. 1b shows comparison of the models' robustness for small budgets. While there are differences in robust all models follow a similar trend. Note that for this dataset we were unable to train comparable Polynormer model. We hypothesize that this is related to Reddit Threads having no node features. While the other GTs explicitly include graph structure information through positional encodings, these are missing in Polynormer, which only implicitly considers graph structure through the sparse atfention matrix obtained by employing a GAT. This may be insufficent graph inductive bias, node features have no discriminative information.
UPFD. As shown in Fig. 5 for the gossipcop dataset, our adaptive attacks significantly stronger than the baselines in most cases, providing the best estimates of the models' robustness. This highlights the efficacy and importance of our gradient-based adaptive attacks also for the node injection setting, In contrast to the results observed for the previous datasets, there are much more differences between models. Fig. [ provides direct model comparison of the worst-case perturbations for smaller budgets. Tt shows that the GCN model can exhibit considcrably higher robustness than some GTs. The SAN model the exception, as it is surprisingly robust for both UPFD datasets. These results reveal that GT's can showcase catastrophic vulnerabilities to adversarial modifications of the graph structure, even when these changes are constrained to meaningful perturbations. Results for the politifact dataset are shown in $
Transferability. For each of the five GT models, we collect the adversarial examples generated from our adaptive attack, and transfer them to the other GT models. In Fig. 6 we compare the strongest such transfer attack (best transfer) with the GCN transfer and adaptice attacks on UPFD gossipcop. The results show that our GT attack perturbations transfer better than from GCN. This may be because the GT models are more similar to each hthe than to GCN. In some cases, best transfer the overall strongest attack.
11

---

Published in Transactions on Machine Learning Research (09/2023)
GCN transéce
best transfr
adaptive
Accurary (50
60
130
23
Kdge mod. budge (5))
Kddge bodgre (%6
Eddg mod. bodget (76)
Edge modd basiget (56)
bdde mod. burigtt
Blge mod. budge (19
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d)
GPS.
(e) Polynormer.
(f) GCN.N.
Figure 6: Transfer allack results (node injection, evasion) for UPFD gossipcop (graph classification).
1o kod brunt, 2nd hol bad
Accunicy (56)
Aucruaacy (96)
60-
Accunacy
too 10%
buib9, knd
bu158, knd
100
Edge muoliieciio Iradages (14)
Edge modillcation budgett (16)
Edge modiliottion berlact (35)
Edae mudiification budger (%6)
(a) GCN, pol.
(b) Graphormer, pol.
(c) GCN, gos.
(d) Graphoomerr, gos.
Figure 7: Node injection attack results for normally (red lines) and adversarially trained (orange, green, &
yellow lines) GCN and Graphormer on UPFD politifact (pol) and gossipcop (gos) (graph classification).
However, note that choosing the best from up to eight (adaptively generated) attacks can be considered an ensemble with high computational cost. However, best transfer can be used as a "unit test" before laboriously designing adaptive atlacks for a new GT architecture. Results of best transfer for other dalasets and all individual tronsfer results across different GTss are available in $ C.3 & $ C.4 respectively,
7 Adversarial Training
We base our Adversarial Training (AT) implementation on the "Free" adversarial training of Shafahi et al. (2019). The main idea is to couple the attack and training optimizations by replaying the same mini-batch k times. In each replay, both the attack perturbation and the model weights are updated. This approach allows us to apply stronger perturbations through multi-step optimization, while avoiding the overhead of only performing a single training update for every & altack steps. In $ D we provide the pseulocode and details our modifications to free AT, make applicable to our setting.
We explore adversarial training for Graphormer, and compare it to adversarially training a GCN as baseline in a node injection attack scenario on the UPFD politifact dataset in Figs. 7a & ?b Fig. 7a shows that a GCN struggles to benefit from adversarial training, while Fig. 7b demonst that AT significantly improves Graphormer's robustness, surpassing the adversarially trained GCN by a large margin. We find that these results are consistent across datasets with similar results on gossipcop Figs. 7c & 7d These findings show that the increased flexibility and capacity of graph transformers can offer significant advantages in learning robust models via adversarial training, even when the standard (non-adversarially trained) versions of these models are highly vulnerable, we establish in $ G These results complement and support the findings of Gosch et al. (2023a), who attribute the limited success of AT for traditional message- message-passing GNNs to the lack of their fiexibility in adjusting their message- message-passing to adversarial examples. While Gosch el al. (2023a) establish that the capability of AT as a defense to structure perturbations can be significantly improved by making pressae--assingg GNNs more ficxible by making the graph filter a graph convolution learnable, we show that breaking the static message passing by being able to learn to attend to nodes has similar effect and is a key enabler for effective adversarial training.
of the least robust models in our attack evaluation,
12

---

Published in Transactions on Machine Learning Research (09/2025)
8 Related Work
Triggored by the seminal works of Zügner et al. (2018); Dai et al. (2018). , research arca emerged spanning
attacks, defenses, and certification of pressage-passsng GNNs (Jin et. al., 2021 Günnemann 2022 Guerranti
ct al. 2023: Gosch et al.] 2023b; Sabanayagam et al., 2025 However, GTss have been entirely neglected
despite being very active field of research with demonstrated success common benchmarks (uüller et al. 2024]. Zhu et al.) (2024) is the sole exception acknowledging this gap. However, they propose their own transformer-inspired defense component and evaluate it using transfer poisoning attacks. Thus, they do not shine light on the robustness of the diverse set of GTBs nor do they study adaptive attacks. MMjjaanovic et al. (2022) shows that adaplive attacks are crucial to correctly evaluate the robust of GNNs. This follows
similar results from the vision domain [Tramèr et al. 2020 Carlini & Wagner 2017 Athalye et al. 2018).
2019 proposes the first Projected Gradient Descent (PGD) attack for discrete Lo perturbations of the graph structure, with focus on massage-passng architectures. Geisler et al. (2021) extend this PGD with a randomization scheme Projected Randomized Block Coordinate Descent (PRBCD) attack. Gosch et al. (2023a) exlend PRBCD with local constraints to allow for semantically more meaningful attacks, which is conceptually related to our semantically meaningful node injection attack. Further important related works are Lin et al. (2022): Zhu et al. (2018); [Bocchvski & Günnemann (2019), where the authors study similar approximations for perturbations the rigen-decomposition of the graph Laplacian. Moreover, Wang et al. (2023a) attack message- wesssgg-passsng architectures on the UPFD fake news detection using reinforcement learning. As an entry to Node Insertion Attacks (NIA), we refer to Wang et al. (2020); Zou et al. 2021)
Next to adaptive-attack works, our attack is rooted in the GNN robustness literature. Xu ct al.
to obtain the efficient (gradient-basee
9 Conclusion
We provide the first principled study into the adversarial robustness of graph transformers. Concretely, we provide effective and general guiding principles for designing adaptive attacks for GTB. Consequently, we study five representative graph transformers which use three of the most commonly used positional encodings: random-walkk-assdd, distance-based, and spectral PEs; as well as common sparse-attention mechanisms. Thus, our developed contimuuus relaxations for these GT components can find broad application to other GT models. Furthermore, our study demonstrates that GTss can be rophically fragile in many settings and more robust in others. This diverse picture underlines the importance and need for adaptive attacks to reveal such muanced robustness properties. While the comparison of GT's and traditional GNN's robustness w.r.t. the studied attacks does not allow for conclusion about which architecture is superior in terms of robustness when applying normal training, our adaptive attacks allow to uncover a strong difference in their robust learning capabilities. Concretely, we show how to leverage our adaptive attacks for adversarial training with GTs and that doing so, due to the flexibility of GTTs, they have the potential to significantly outperform static posssge--assingg GNNs their robust learning performance, alleviating one of the key limitations of classic GNNs. One interesting direction for future work could be to study the optimality of relaxations, and how to define, measure, and prove this property.
Broader Impact Statement
While the threat model of attacking fake news detection could have a negative societal impact, our methods are applicable mostly white-box setting and, therefore, are much more useful to those who are developing fake news detection to probe and improve the robustness of their models. If model developer has access the right. tools, we are convinced that the information advantage outweighs the potential negative effects.
Acknowledgements
This paper has been supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the German Foderal Ministry of Education and Research and by the German Research Foundation, grant GU 1409/4-1. Leo Schwinn gratefully acknowledges funding by the Deutsche Forschungsgemeenschaaft (DFG, German Research Foundation) project number 544579844.
13

---

Published in Transactions on Machine Learning Research (09/2025)
References
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Bassam Bamich. A tutorial on matrix perturbation theory (using compact matrix notation). arXiv preprint XrXi:22202200001, 2022.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In Proceedings of the 36th International Conference on Machine Learning, pp. 695 704, 2019.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint xrx:::11111000 2018.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Proceedings IEEE Symposium Securily and Privacy, pp. 39 57, 2017.
Yonggiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In International Conference on Learning Representations, 2022. URL https://openrevieeu wttp://ommmm..d///aaaaaaaa
Thomas H. Cormen, Chalres E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack graph structured data. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-cxpresstre graph transformer in lincar time. In The Twelfth International Conference on Learning Representations, 2024.
Yingtong Dou, Kai Shu, Congying Xia, Philip S. Yu, and Lichao Sun. User preference-aware fake news detection. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2051 2055, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Simon Geisler, Tobias Schmidt,, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. In Thirty-seventh Conference on Newrul Information Processing Systems (NeurIPS), 2023a.
Lukas Gosch, Daniel Sturm, Simon Geisler, and Stephan Günnerann. Revisiting robustness in graph machine learning. In International Conference Learning Representations (ICLR), 2023b.
Filippo Guerranti, Zinuo Yi, Anna Starovoit, Rafiq Kamel, Simon Geisler, and Stephan Günnemann. On the adversarial robustness of graph contrastive learning methods. In NeurIPS Workshop on Graph Learning Frontiers, 12 2023.
Stephan Günnemann. Graph Neural Networks: Adversarial Robustness, pp. 149-176. Springer, Singapore, 2022. ISBN 978981 1660542.
Bo Hu, Zhendong Mao, and Yongdong Zhang. An overview of fake news detection: From a new perspective. Fundamental Research, 2024. ISSN 2667-3258.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adversarial attacks and defenses on graphs: A review, a tool and empirical studies. SIGKDD Explor. Newsl., 22:19 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourncau, and Prudencio Tossou. Rethinking graph transformers with spect attention. In Proceedings of the 35th Internalional Conference Neural Information Processing Systems, 2021.
Lu Lin, Ethan Blaser, and Hongning Wang. Graph structural attack by perturbing spectral distance. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp- 989 998, 8 2022.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In Proceedings of the 40th International Conference on Machine Learning, pp.
2023.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? In Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášck. Attending to graph transformers. Transactions on Machine Learning Research, 2 2024.
Ladislav Rampášck, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Proceedings of the 36th Internalional Conference on Neural Information Processing Systems, 2022.
Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20), pp. 3125 3132, ACM, 2020.
Mahalakshmi Sabanayagam, Lukas Gosch, Stephan Günnemann, and Debarghya Ghoshdastidar. Exact certification of (graph) neural networks against label poisoning. In The Thirteenth International Conference on Learning Representations, 2025.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Advances in Neurul Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
G. W. Stewart and Ji-guang Sun. Matrir Perturbation Theory. Academic Press, USA 1990. ISBN 9780126702309.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 6000-6010, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Haoran Wang, Yingtong Dou, Canyu Chen, Lichao Sun, Philip S. Yu, and Kai Shu. Attacking fake news detectors via manipulating news social engagement. In ACM Web Conference Proceedings of the World Wide Web Conference, WW WWW, pp. 3978 3978-3986, 2023a.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Haoran Wang, Yingtong Dou, Canyu Chen, Lichao Sun, Philip S. Yu, and Kai Shu. Attacking fake news detectors via manipulating news social engagement. In ACM Web Conference (WWW), 2023b.
Jihong Wang, Minnan Luo, Fnu Suya, Jundong Li, Zijiang Yang, and Qinghua Zheng. Scalable attack on graph data by injecting vicious nodes. Data Min. Knowl. Discon. 34(5):1363-1388 2020.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui- Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In IJCA(119 Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3961-3967, 6 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform bad for graph representation? In Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems, NewrIPS, 2017.
Dingyuan Zhu, Peng Cui, Ziwei Zhang, Jian Pei, and Wenwu Zhu. High-order proximity preserved embedding for dynamic networks. IEEE Transactions Knowledge and Data Engineering, 30:2134-2144 11 2018.
Yonghua Zhu, Jincheng Huang, Yang Chen, Robert Amor, and Michael Witbrock. graph transformer defence against graph perturbation by a flexible-pass filter. Information Fusion, 107, 2024.
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. TDGIA: Effective injection altacks on graph neural networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2461-2477 1661-471, 2021.
Daniel Zügner and Stephan Günneeann. Adversarial attacks graph neural networks via meta learning. In International Conference on Learning Representations, 2019.
Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1656-1665, 2020.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2847,2856, 2018.
16

---

Published in Transactions on Machine Learning Research (09/2025)
A Node Injection Attack Details
Let D = [91,.... .... 9N be the datasct of all graphs, where cach graph Gi = (Vi& has n, nodes V; {ur,1,.., vi, and a corresponding node feature matrix X; E Rnaxd The total number of nodes in the dataset is ny = Σ n4. Let Jack be the graph that is being attacked. We define the candidate set of injection nodes as the union of the nodes of all other graphs: Ves = UGLE V,, which contains nes = nD Natk nodes with the corresponding features Xes. It of course possible to restrict this candidate set if it is not sensible or feasible to include all nodes.
We can augment the original (connected) graph Gark = (Autk, Xatk) by adding the injection candidate set isolated nodes:
Pack = (Aatk, Xatk), Aatk = Aath
o 0
Xatk X
E (0,1)"Dx0D, Xatk =
E Reox x
(24)
Edge-flip perturbations to this augmented adjacency matrix, Á = A model both structure perturbations and node injections together. As in Eq. 2 the perturbation á' can be expressed in terms of a binary edge flip matrix: = A+ + (1,1, 2A) ② B, where:
B E
B
E
1 RRxDR
(25)
F
Note that the edge flip budget A is also an upper bound for the number of nodes that can be injected: 0 S nin S A. Since the attack budget is usually much smaller than the size of the candidate set, i.c. A < ness the perturbed augmented graph (A, 8) still mostly contains isolated nodes. Therefore, we prune away all disconnected components, which for the unperturbed graph simply reverts the augmentation: prune(ÿ) g. However, for perturbed augmented graph, this results in the perturbed graph that seeking:
ğ = prune Á, x) X), E 10,
X E
(26)
Here, Din is the number injected nodes, and ń = n + nin is the total number of nodes of the perturbed graph. The NIA objective can thus be written as:
max Cark (So()), with و -= prune + (1,,17 2A) o B, x)
(27)
B s.t. ||
where, fo is the trained GNN and Latk is suitable attack loss.
Edge block sampling. To optimize the objective, we can apply the relaxation B E [0, 1], as shown in 2.1 In this case, PRBCD |Geisler et al. 2021) not only enables more elficient optimization, but setting a smaller block size is crucial to limit the number of connected injection nodes during optimization, since GTs complexity scales with O(n²). Moreover, random block edge sampling allows us to control which parts of B results pure node injections without modifying odges the original graph. For NIAs with large candidate sets, we only sample from E, as sampling from the n entries of F results in using most of the budget on disconnected injection node pairs that are later pruned away.
in Eq. 25 can be changed, e.g. not sampling
A.1 Node Probability Example
We provide an illustrative example in Fig. of how the iterative node probability is applicd. Each iteration of Eq. can can be thought of as message passing step to update the node probability approximation based on the neighbors current approximations:
(++1) p
=1
II (1- My p39), with p = ():))((s))
The number of iterations should be set in the order of expected longest chain of added injection nodes. Therefore, very few iterations (2-5) should suffice for most NIAs.
17

---

Published in Transactions on Machine Learning Research (09/202))
1.0
1.
10
(a) Edge probabilities.
(b) Node probability initialization.
10
1.0
0,96
0.82
0.2
61
0.999
0.811
0.08
OL1
0.55
0.1
0.518
0.028
(c) After 1dd iteration.
(d) After 2nd
iteration.
Figure 8: Node probability example. Dashed lines indicate injection nodes.
B Dataset Details
The inductive node classification dataset CLUSTER @wiveedi al. 2023 has 12 000 graphs with an average
of 117.2 nodes. We used the standard PyG train/val/Len split of 83.3/8.3. 8.3/ 3/./8.3%% graphs. The binary graph
classification dataset Reddit Threads (Rozemberczki et al. 2020 contains 203 088 graphs with average of 23.9 nodes. We used stratified random split of 75/12.5 12.5%. The binary graph classification dataset UPFD gossipcop (Dou et al. 2021) contains 5464 graphs with an average of 58 nodes. We use the standard PyG split 20/10/70% The binary graph classification dataset UPFD politifact (Dou et al. 2021 contains 314 graphs with an average of 131 nodes. We use the standard PyG split of 20/10/ 20/10/70%
C Additional Attack Results
C.1 CLUSTER Constrained Attack
Fig. 9 shows the attack results for the CLUSTER dataset when constraining edge perturbations such that edges to the labeled nodes cannot be flipped. As expected, this significantly reduces the attack strength compared to the unconstrained setting shown in Fig. 3
zeslum iarturbation
zardomm stlack
GUN PRECD traunaferr
aiagytion PRRCID (surs)
Aecuncc (50
80
43
E0-
Edo
(85
Iradgrt
Insdast
Edo
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) GPS.
(e) Polynormer.
(f) GCN.
Figure 9: CLUSTER constrained attack results.
18

---

Published in Transactions on Machine Learning Research (09/2025)
C.2 UPFD Politifact Node Injection Attack
Fig.
10
shows the atlack results for the CPFD politifact dataset. The results are similar to the ones from the
UPFD
gossipcop dataset discussed in $ 6 and shown in Fig, 5
zuzdom perturbation
attack
adaptive (ours)
Accuncy (3g
23
20
23
Edge mnd. bodget (3)
Edge mod. bodget (16)
Edge mod. bodget (75)
Edge mod. budget
Edge mod. budges (56
Bdge mod. budget (5)
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) GPS.
(e) Polynormer.
(I) GCN.
Figure 10: Node injection (evasion) attack results for UPFD politifact (graph classification).
C.3 Best Transfer Attacks
Here provide the results for the bost transfer results, analogous to Fig. but for all additional datasets.
Results for CLUSTER are in Fig. 11 for CLUSTER (constrained) in Fig, 12 for Reddit Threads in Fig. 13
and for UPFD politifact in Fig. 14
adleptivee
50
AccIrON (35)
Edg mod. budge (3)
Edg med. budget (50
Edge med. brodget (80)
Rdge mod. Iradget (%)
Rdge mod. Indggt (9))
Edge mod. budge (5)
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) GPS.
(e) Polynormer.
(f) GCN.
Figure 11: Best transfer, CLUSTER (inductive node classification), structure attack (global, evasion).
GCN transfer
best transfer
adaptive
AonnEcc (56)
60
13
03
60
20
20
Edg mod.
budge
Fdge med.
budget (50)
Fdge mod. brodget (%)
Edge morl Insiget (36)
Reig mod. Insigtt
Rdge mod. budgge (5)
(a) Graphormer. Figure 12: Best transfer, CLUSTER (inductive node classification), constrained structure attack (global, evasion).
(b) GRIT
(c) SAN.
(d) GPS.
(e) Polynormer.
(f) GCN.
19

---

Published in Transactions on Machine Learning Research (09/2025)
GCN transéee
best transfer
adaptive
A0sun0 (10)
60
20
(3)
05
20
20
13
30
Edge bodget
budges
Edge
Edge
Ddge
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) GPS.
(e) GCN.
Figure 13: Best transfer, Reddit Threads (graph classification), structure attack (evasion).
adaptive
Accitoey (%)
Edgt bodget (50)
Edo mand. bodjet (55
brdggtt (75)
budget
Edge Sudgg
Edge budggt (9)
(a) Graphormer. GRIT.
(c) SAN.
(d) CPS.
(e) Polynormer.
(I) GCN.
Figure 14: Best transfer, UPFD politifact (graph classification), node injection attack (evasion).
C.4 All Transfer Results
Here we provide the detailed attack results including the individual transfer models. Results for Graphormer are in Fig. 15 for GRIT Fig. 16 for SAN in Fig. 17 for GPS in Fig. [8] for Polynormer in Fig. 19 and for
GCN in Fig. 20 The results highlight that depending the dataset, some GT models (e.g., Graphormer and GRIT) transfer well, while other don't (e.g., GPS to Graphormer).
(a) CLUSTER
(b) CLUSTER con.
(c) Reddit Threads
(d) UPFD pol.
UPFD gos.
Figure 15: Graphormer attack results with all transfer models shown.
20

---

Published in Transactions on Machine Learning Research (09/2025)
(a) CLUSTER
CLUSTER con.
(c) Reddit Threads
(d) UPFD pol.
UPFD gos.
Figure 16: GRIT attack results with all transfer models shown.
EST
(a) CLUSTER
(b) CLUSTER con.
(c) Reddit Threads
(d) UPFD pol.
(e) UPFD gos.
Figure 17: SAN atlakk results with all transfer models shown.
(a) CLUSTER
(b) CLUSTER con.
(c) Reddit Threads
(d) UPFD pol.
(e) UPFD gos.
Figure 18: GPS attack results with all transfer models shown.
(a) CLUSTER
(b) CLUSTER con.
(c) UPFD pol.
(d) UPFD gos.
Figure 19: Polynormer attack results with all transfer models shown.
(a) CLUSTER
(b) CLUSTER con.
(c) Reddit Threads
(d) UPFD pol.
(e) UPFD gos.
Figure 20: GCN attack results with all transfer models shown.
21

---

Published in Transactions on Machine Learning Research (09/2025)
C.5 Ablations
We enable each of the continuous relaxations individually and logether in different combinations. We report the results for Graphormer in Tab. ! The node probability relaxation only applies to the node injection attacks on UPFD. The main insights from the results arc: (a) All contimuous relaxations individually seem to give somewhat useful gradients and can be used to get better results than the gradient-free random baseline. (b) For node injection at tacks, using only the node probabilities the graph pooling and bias the attention scores is usually sufficient and leads to some of the strongest attack results. (c) Some relaxations are more effective than others, and using multiple does not seem to always work better than only one. However, is not consistently better than the her. A good approach might be to try the relaxations individually, to find which are most relevant. Similar effects have been reported by Trrmmrr et al. (0200) (Recurring Attack Theme T2). We also show ablations for GRIT and SAN components in Tab. and which we can draw the similar conclusions.
Tab. respectively, from
We also chock the attack strength for GRIT when cnabling or disabling gradient computation through certain parts of the model and show the results in Tab. 2 It is possible to get strong allacks even without computing gradients through RRWP, which could be much more efficient computationally, depending the model and graph size. For node injection attacks, as for the other models, using only the node probability bias in the attention scores already leads to the strongest attacks we report.
A Ablation on different attack components on SAN are presented in Tab. 8 The colomn 'Eig. backp.' refers to the alternative method of obtaining gradients through the eigen-decomposition discussed in The results indicate that both methods seem to work equally well.
Table 1: Ablations for the Graphormer relaxations for fixed budget of 1% for CLUSTER without and with perturbation constraints (c.), and 10% for UPFD politifact (pol.) and gossipcop (gos.). The mean and standard deviation over 4 runs with different scods are reported.
Acc. (%)
Node
Acc. (%)
Deg.
SPD
prob.
CLUSTER
CLUSTER
UPFD pol.
UPFD
52.61 0.57
60.00 + 0.42
67.0 2.0
38.0 0.0
/
46.78 1 0.46
68.45 0.37
67.0 1.00::20 2.0
38.0 1 0.0
50.81 + 0.41
60.66 + 0.21
/
66.5 = 1.9
39.5 = 1.9
66.5 =
38.5 =
/
80.5 3.4
53.5 + 1.0
random
66.52 1 0.61
70.29 0.32
85.0 1. 2.6
61.5 1 4.1
clean
77.89
77.89
92.0
98.0
Table 2: Ablations for the GRIT relaxations for fixed budget of 1% for CLUSTER without and with perturbation constraints (c.), and 10% for UPFD politifact (pol.) and gossipcop (gos.). The mean and standard deviation over 4 runs with different seeds reported.
PE
Deg. grad.
Acc. (%)
Node prob.
Acc. (%)
grad.
CLUSTER
CLUSTER
UPFD pol.
UPFD gos.
/
44.07 + 0.79
65.25 + 0.22
34.5 - 1.0
75.0 2.6
46.27 + 0.36
65.70 t 0.35
34.5 + 1.0
74.5 +: 2.5
49.51 0.90
66.49 0.49
34.5 +
73.5 1.0
34.5 + 1.0
73.5 + 1.0
/
54.5 1: 1.9
83.0 2.0
random
69.13 + 0.10
72.25 + 0.29
76.0 4.3
82.0 0.0
clean
78.98
78.98
98.0
$4.0
22

---

Published in Transactions on Machine Learning Research (09/2025)
Table 3: Ablations for the SAN relaxations for a fixed budget 1% for CLUSTER without and with perturbation constraints (c.), and 10% for UPFD politifact (pol.) and gossipcop (gos.). The mean and standard deviation over 4 runs with different seeds are reported.
Acc. (%)
Acc. (%)
Lap.
Eig. backp.
Attn.
pert.
CLUSTER
CLUSTER C.
prob.
UPFD pol.
UPFD gos.
54.0 + 0.6
63.3 3.3+000
83.5 + 1.0
91.5 4.1.
54.4 0.6
62.9
82.0 2.3
94.0 3.0
53.9
0.1
77.5
91.5 1 2.5
57.1 =
67.2 0.2
83.5 +
89.5 +
55.1 1 1.0
67.3 1
81.0 1 1.2
89.5 1 3.4
77.0
89.5 +
86.0 + 0.0
90.1 + 6.0
86.0 + 2.3
91.0 + 5.3
random clean
65.7 O.7 0.7 76.1
68.9 1: 0.3
86.0 1: 0.0
87.5 1.0
76.1
86.0
98.0
C.6
Unnoticability Results
Here we report the nodo-contric homophily results as mentioned by Chen al. (2022) as a semantic unnoticability criteria for node injection allacks. Following Chen et al. (2022), we the following node centric homophily measure hy for node u:
h2
Tu
Tu
Σ JEN(U)
Vdjvdo" X
(28)
where Xu the feature vector of node u. As we work with graph classification datasets, we compute hy for every node in every training graph and of the first 50 test graphs. Figure 21 and Figure 22 show the results for the UPFD gossipeop datasel with adversarial budget of 5% and 25%, respectively. They highlight. that there is significant homophily change towards lower homophily values w.r.t. the unperturbed test graphs or the original training graphs and thus, ostablishes that our attacks are unnoticable w.r.t. the metric proposed by Chen et al. (2022). This does not come as a big surprise, because in our node injection attack, we do not treat the node features as part of the optimization problem and only allow connections to nodes in other graphs (for our dataset these are other real users), which potentially more resembles a classic graph modification attack regarding homophily changes (Chen et al., (022).. For Polynormer, one can observe a slight reduction in the highest. homophily values for a stronger attack, interestingly, for the other models, find that higher attack budgets increase the overall measured homophily. We think that potential explanation lies in the already highly homophilic data. Adding more edges though higher attack budgets leads to even more averaging of already highly homophilic data. This also indicates that the actual predictive feature difference in the dataset as used by the GTs is not capturable by node-centric homophily.
Figure 21 and Figure 22 show similar results for the UPFD politifact dataset with an adversarial budget of 5% and 25%, respectively. Here, we observe the same patterns of no big changes the homophily. However, the highest homophilic measurements actually slightly decrease the attack strength increases, whereas close to highest homophilic measurements increase.
Lastly, we want to note that no perturbed test-graph has a lower homophily score than found in the training graphs and thus, the trivial defense against node injection attacks proposed by Chen et al. (2022) based on cutting away all nodes with lower homohpily scores than found in the training data won't be effective.
23

---

Published in Transactions on Machine Learning Research (09/2025)
Ereit
6.5 005
100
555 EM
530
631 5.
250 076
145
373 031 030
030 030
(a) Graphormer
(b) GRIT
(c) SAN
(d) GPS
(e) Polynormer
Figure 21: Node-cees centrcc homophilies in the training set, unperturbed test set and perturbed test set for 0.05 the UPFD gossipcop dataset.
Nulein Tapps
Surinn Euals
Taking Capls
Santin Sught
Drgil pada
100
579 076
Himarte'
23 120
03
00 020 130
16 120
(a) Graphormer
(b) GRIT
(c) SAN
(d) GPS
(e) Polynormer
Figure 22: Node-centris homophilies in the training set, unperturbed test set and perturbed test set for 0.25 in the UPFD gossipcop dataset.
Pakiing (aps
Nuiio Deats
Eaking Cagits
366 039 15 Uo
24 010 180 120
6.8 080
6.0 080
(a) Graphormer
(b) GRIT
(c) SAN
(d) GPS
(e) Polynormer
Figure 23: Node-centric homophilies in the training set, unperturbed test set and perturbed test set for 0.05 the UPFD politifact dataset.
Tuainn Supes
Stals
"aring Drals
Nea Ereite
GAT LA 12 200 120
Homochiv
000 0.0
0.0 100
(a) Graphormer
(b) GRIT
(c) SAN
(d) GPS
Polynormer
Figure 24: Node-centric homophilies in the training set, unperturbed test set and perturbed test set for 0.25 in the UPFD politifact datasct.
24

---

Published in Transactions on Machine Learning Research (09/2025)
C.7 Local Attack Results
Figures 25 and 26 show the results of applying our adaptive atlacks in local atlack setting for CLUSTER. In Figure 25 we use the constrained setting (see Section 6) that prohibits modifying edges to the labeled nodes, to increase the difficulty of the attack setting. The results highlight the efficacy of our adaptive attacks, significantly outperforming the random-attack baseline. Importantly, our adaptive attacks show similar strength w.r.t. the random baseline as PR-BCD does on GCN, which is known to be stronger then Nettack (Geisler et al. 2021 Zügner al. 2018 in the local attack setting.
To allow comparison with Nettack (Zigner et al. 2018
explore another attack setting, its threat model definition does not allow to model the above constrained setting. In particular, Nettack defines set of attack nodes A and allows the deletion or addition of an edge vu) if either u E A, or E A. Now, to compare Nettack with our adaptive attacks, we set A to the 1-hop neighborhood ((u) of the given target node u, and constrain our adaptive attacks to the same set of adversarial edge modifications. We say an attack budget [N(x) edges and is large if it can perturb between [N(u)] to 2
is small to moderate if it can perturb at most 2
[N) edges. Even stronger attacks have high risks of semantic violations (Gosch et al.) 2023b). On average on the CLUSTER dataset, the attack budgets we consider of 0.2% and 0.5% correspond to small to moderate budgets (4 and 10 perturbations), 0.9% and 1.4% strong budgets (18 and 28 perturbations) and 2% 40 perturbations. Figure 26 highlights that for small to moderate budgets, our adaptíve attacks oulperform Nettack by large margins. This highlights the effectiveness of the gradient signal derived from relaxations. For large budgets, our adaptive attacks outperform Nettack for GRIT and GPS, while Nettack gets strong results for SAN and Polynormer. Note here that the transferability between atlacks on CLUSTER is in general high (see Appendix C.4), which benefits transfer attacks like Nettack.
Edy and. kolyt (8)
Rig (9)
Rip Tadge (5)
Bky Iadari (5)
Fly real Lebyi (5)
Flyoedd Solge (3)
(a) Graphormer
(b) GRIT
(c) SAN
(d) GPS
(e) Polynormer
(f) GCN
Figure 25: Local adaptive attacks on CLUSTER (constrained setting, see Section budgets are shown from 0% 2%.
Edge modification
random porturbation
-h. random attakk
NECTACC
DCN FILICO trande
adaption PRICC (mnn))
00 6.5
69
60
30
10
08
Edac stadl Budkett
Edg Ieadact
Edee mnd Sudagt
Edas and Icoluct
Edg maol. badggt 190)
Edar bedget
(a) Graphormer.
(b) GRIT.
(c) SAN.
(d) CPS.
Polynormer.
(I) GCN.
Figure 26: Local adaptive allacks on CLUSTER (I-hop neighborhood). Edge modification budgets 0.2% and 0.5% average correspond to small medium attack budgets (i.e., the number of edges modifications is < than half of the victim node's s neighborhood size) with our adaptive attack consistently outperforming Nettack for these budgets. 0.9% and 1.4% usually correspond to strong attack budgets (between half of the nodes neighborhood size to the node's neighborhood size). 2% allows to perturb more edges than the size of the victim node's neighborhood.
25

---

Published in Transactions on Machine Learning Research (09/2025)
D Adversarial Training Algorithm
We based our implementation of the adversarial training on the 'Frec' adversarial training of Shaafhi et al. (2019). Pseudocode for our adversarial training is given in Alg. The main modifications are that we do two separate forward and backwards passes for the attack and model respectively. This is because: (1) the attack and model often have distinct loss functions that they optimize for, and (2) we sample a discrete structure perturbation for the model, such that the perturbed graph is included in the original valid sample space. Another difference is that need to iterate over the graphs in the minibatch separately. This is limitation caused by: (1) The attack optimization steps not trivial to parallelize, especially for node injection attacks, and (2) the PE computations (e.g. Laplacian digen-decomposstioon) are also not easily parallelizable and need to re-computed for each new perturbed graph.
Given these limitations, our adversarial training is much less efficient. requires at Ieast 2 [B] times more model evaluations than normal training. Furthermore, for many GTs the PE computation one of the most computationally expensive steps. Therefore, PEs are usually precomputed in a pre-processing step. During adversarial training, we need to compute PEs for new unseen perturbations at each step, which further increases the overhead. Nonetheless, following the main idea of Shafahi et al. (2019) alleviates some of the overhead and makes it somewhal practically leasible.
Algorithm Our k-step 'free" adversarial training
Require: Training dataset T, model fo, attack budget A, number of steps k, learning rate a Initialize 0
for epoch L....Nep/k do
for minibatch B T do Initialize perturbations P for i == 1...k do
Ge + for graph 9 = X, X, y) E B do
- PRBCD step(Ja So, X, A, P,A)
A' + sample discrete(A (A P)
Ja ga VoL(fo(A', X),y)
end for
<- 0 + a [ '0
end for
end for end for
E
Hyperparameters
To obtain trained models of comparable performance for each architecture type, we performed a hyperparameter search for each model and dataset. Because of the large number of experiments and pyperparameters we used random sampling of hyperparameter values predetermined ranges. These ranges are defined and available in the configuration files in our code repository under final hyperparamoters of the best models used for the robustness results shown for Graphormer in Tab. for SAN in Tab. 5 for GRIT in Tab. 6 for Polynormer in Tab. g for GPS in Tab. 7 for GCN in Tab. for
http://gggchuu..coos//////////// stteefoosggtrrouuseeeessss robustnesstt The
GPS-GCN in Tab. 10 for GAT in Tab. and for GATv2 in Tab. 12
26

---

Published in Transactions on Machine Learning Research (09/2025)
Table 4: Hyperparameters for Graphormer.
CLUSTER Reddit Threads
UPFD gos.
UPPD pol.
Optimizer
adam
adamW
adamW
adamW
Learning rate
8.04 x 10-4
10-4
3.75 x 10
1.29
Weight decay
10-6
1.37 x
6.7 x 10-3
max. degree
70
42
31
SPD max. distance
4
8
10
Attention dropout
0,107
0,138
0.382
0
Input dropout
0
8.65 x 10-3
0
MLP dropout
4.47 x 10-2
1.21
10-2
5.37 x 10-2
0
Hidden dimension
60
48
30
40
Layers
15
6
6
Attention heads
6
8
8
Graph pooling
virtual node
virtual node
virtual node
Table 5: Hyperparameters for SAN.
CLUSTER
Reddit Threads
UPFD gos.
CPFD pol.
Optimizer
adam
adamW
adlmm
adlam
Learning rate
5.0
10
5.66 10
5.41 10
1.29
10 10-4
Weight decay (num. cig.)
3.54 10
0
1.0
10-3
10
24
10
PE dimension
16
20
16
layers
2
2
PE heads
4
5
4
Y (global/ local)
0.1
5.46 x 10-5
4.28
10-3
1.43
10-2
Dropout
0
7.92 x 10-2
1.73
10-2
0
Hidden dimensions
48
48
80
96
Layers
16
3
3
Attention heads
8
8
4
Graph pooling
add
mean
add
Table 6: Hyperparameters for GRIT.
CLUSTER.
Reddit Threads
UPFD gos.
UPFD pol.
Optimizer
adamW
adamW
adamW
adamW
Learning rate
1.29 x 10-3
8.02
10-4
2.24 x 10-3
5.61 x 10-4
Weight decay
4.16 10-6
3.05 10-8
1.2 10-8
2.97 x 10-2
RRWP steps
4
6
Attention dropout
0.478
0.28
0.293
0.49
Dropout
1.0 10
10-2
5.55 10-2
Hidden dimensions
48
24
Layers
12
11
Attention heads
Graph pooling
mean
mean
Table 7: Hyperparameters for GPS.
CLUSTER
Reddit Threads
UPFD gos.
UPFD pol.
Optimizer
adamW
adamW
adamW
adamW
Learning rate
5.0 x 10-4
3.21 x 10-3
4.28
10-4
1.18
10-2
Weight decay
1.0 x 10-5
7.44 x 10-3
6.34 x 10
1.3 x 10
(num. cig.)
10
13
10
10
PE dimension
16
16
16
16
PE encoder
DeepSet
DeepSet 9.32 x 10-2
DeepSet 0.1
DeepSet
Attention dropout
0.1
0.1
Dropout
0.1
9.32 x 10
0.1
0.1
Hidden dimensions
48
24
40
32
Layers
16
5
6
Attention heads
8
8
8
Graph pooling
add
add
add
27

---

Published in Transactions on Machine Learning Research (09/2025)
Table 8: Hyperparameters for Polynormer.
CLUSTER
UPFD gos.
UPFD pol.
Optimizer
adamW
adamW
adamW
Learning rate
2.35 x 10-3
8.93 x 10-4
1.72 x 10-4
Weight decay
1.0 x 10-7
1.0 x 10-7
1.0 10-7
Attention dropout
5.0 10
5.0 10-2
5.0 10
Dropout local
0.137
0.149
0.121
Dropout global
5.0 10
5.0 x 10
5.0 x 10
Hidden dimensions
Layers local
Layers global
Attention heads local
Attention heads global
Graph pooling
Table 9: Hyperparameters for GCN.
CLUSTER
Reddit Threads
UPED gos.
UPFD pol.
Optimizer
adam
adamW
adamW
adamW
Learning
1.0 10
3.17 10-3
1,23 10-4
5.29 10-3
Weight decay
10-6
2.85 10-6
2.59 10-2
Dropout
10-3
Hidden dimension
30
Layers
Graph pooling
mean
add
meen
Table 10: Hyperparameters for GPS-GCN.
Table 11: Hyperparameters for GAT.
Table 12: Hyperparameters for GATv2.
CLUSTER adamW
Optimizer
CLUSTER
CLUSTER
Learning
9.74 10-4 1.0 10-8
Weight decay (num. eig.)
Optimizer
adam
Optimizer
adam
10
Learning rate
1.0
10-3
Learning
1.0
10-3
PE dimension
Weight decay
Weight decay
PE encoder
DeepSet
Dropout
Dropout
Attention dropout
5.0 x 10-2 5.0 x 10
Hidden dimension
176
Hidden dimension
120
Dropout
Layers
16
Layers
16
Hidden dimensions
40
Attention heads
Attention heads
Layers
13
Graph pooling
Graph pooling
Attention heads
8
Graph pooling
28

---

Published in Transactions on Machine Learning Research (09/2025)
F Laplacian Eigen-Decomposition Gradient
F.1 Perturbation Approximation: Repeated Eigenvalues
Unfortunately, Eq. 18 and 19 do not hold in general when repeated cigenvalues are present. This is due to the fact that a small perturbation can separale repeated eigenvalues inlo distinet eigenvalues. For the umperturbed graph, the choice of eigenvector basis of the repeated eigenvalue's eigenspace is arbitrary. In the perturbod graph, however, the cigenvectors corresponding (up to the sign). Thus, large discontinuous change in the eigenvectors can be caused by an arbitrarily small input perturbation. For instance, consider the matrix M with repeated eigenvalue and the following valid eigendecomposition:
the now distinct cigenvalues are uniquely defined
1 0 UAUT, A= 0 1
[ 0 [ 0 1
1 1 U
v2
M
-1
(29)
As soon as an arbitrarily small perturbation is added to one of the diagonal entries, the eigenvalues become distinct and the choice of cigenvectors becomes constrained, which results in discontinuous change:
M = [ -- = [10]-0A0
-UAOT A 0 1+E
Ú= 0 1
(30)
However, there always some valid choice of eigenvectors in the unperturbed graph that leads continuous change with respect to the given perturbation, e.g., in the above example U is also valid choice for the cigenvectors U of the unperturbed matrix. With the right choice of unperturbed cigenvectors, the approximation equations are, therefore, still valid. Here, provide procedure to transform arbitrary cigenvectors into the ones that lead to good perturbation approximations. For the theory showing why this leads to the correct result, we refer to Bamieh 2022).
Let (A, Ú) be the output of the eigendecompoosition algorithm for the unperturbed Laplacian Laym containing repeated cigenvalues. We can write the cigendecomposition it's block form:
A
L ÜAAU A
Ú
U
Ü
(31)
Ann'
For a simple eigenvalue A, the block has dimension one, i.e., A, = [M and Ú, = u, For repeated eigenvalue X, with multiplicity r, it's corresponding block is X,I, and U, E Raxxr Let = pT be an arbitrary symmetric perturbation to the original symmetric Laplacian. We can transform each eigenspace basis of repeated eigenvalue U, to the correct choice of eigenvectors follows:
U, Ü,Q Po,= = PŪ,
(32)
E E
First, we do basis transformation of the perturbation matrix onto the eigenbasis Ú. Then we find the eigendeccoposiiion of the corresponding diagonal block Pc., and use these perturbation eigenvectors to transform the original Laplacian eigenvectors. This results in choice of valid eigenvectors U, such that the approximations in Eq. 18 and 19 are valid for repeated cigenvalues and guarantees continuity of the eigenvalues and vectors with respect to a single perturbation, e.g,, when linearly interpolating from the unperturbed to the fully perturbed matrix.
F.2 Backpropagation: Breaking Up Repeated Eigenvalues
The only thing preventing the use of auto- dittoofiefnnntiiiionn to compute gradients through the digen-decompositionn is the presence of repeated eigenvalues. As a workaround, Lin et al. 2022) propose adding small amplitude random noise to the entire adjacency matrix. While this usually separates the repeated cigenvalues, is
29

---

Published in Transactions on Machine Learning Research (09/2025)
not guaranteed to. We propose different approach in which the smallest possible perturbation term is added to the Laplacian matrix, such that the repeated eigenvalues are guaranteed to be separated while the eigenvectors remain unchanged.
To achieve this, we must first define a minimum eigenvalue distance hyperparameter E, which we set to 10" in our experiments. Then we define eigenvalue separation such that for all perturbed Laplacian eigenvalues - 2 e must hold. Furthermore, we can define a vector o E I2 such that each entry represents the offsct of the perturbed cigenvalue in relation to the true value:
A1 + 01
A + diag(o)
(33)
An + Op
In order for the perturbed matrix to have the same eigenvectors as the unperturbed Laplacian, we can define it by its eigendecomposition:
L sym UÁUT
U(A + diag(o))U
(34)
UAU + Udiag(o)UT
= Lsym + Udiaglo)UT
Consequently, the additive perturbation has the form P Udiag(o)U", such that it shares the same eigenvectors the original Laplacian, and its eigenvalues are exactly the offsets.
Since the Frobenius norm can also be computed using the singular values, finding the perturbation with minimum norm is equivalent to minimizing the Euclidean norm of the offset vector P|] = V,, o, ||o||2- To ensure that the order of the eigenvalues is not changed we can define the separation constraints for the consecutive pairs of the perturbed eigenvalues d4+1 - dr = (Ai-1 +0++1) - (A, -a--0 o,) 2 e. The total constrained optimization problem can be written as:
min マ 1
(35)
subject to 0141 26 (A1+1 xx)
The (n - 1) inequality constraints linear and can be written in matrix-vector form. To further ensure that the total range of the eigenvalues is not changed, the equality constraints On o, = 0 can be added. As an initial guess, the offsets can be set to equally separate the eigenvalues in their range, which is guaranteed to satisfy all constraints. The optimal solution o* can be calculated efficiently using constrained optimization.
In conclusion, using the slightly perturbed Laplacian Laym Laym + ('dia(("")U as input to the eigen- decomposition in the forward pass results in usable gradient via back back- propagation. Note that to get the perturbation, the cigendecomposition of the original Laplacian has to be computed. Thus, it be checked for the presence of repeated eigenvalues, and second perturbed eigendecooppositonn is only computed when necessary. Tab. includes results using this approach, which seems to work about well as the perturbation approximation.
G Further Discussions
G.1 On Principle II
As discussed in Section 3 Principle II requires of Jo (i) continuily w.r.t. Á', and (ii) differentiability almost. everywhere w.r.t. Á'. This principle can be better understood by using the ReLU function as an analogy. The ReLU function satisfies both (i) and (it), but is not continuously differentiable still, neural networks employing ReLU can be effectively optimized (i.e., trained) using gradient descent. This is possible for any function satisfying (i) and (ii), the gradient can be computed for all inputs except on subset having
30

---

Published in Transactions on Machine Learning Research (09/2025)
measure zero, which for ReLU is {0}. In practice, the non-differentiable points are rarely reached, and if so, due to the continuity, an informative gradient can be defined at every non-differentiable point z0 in a principled manner, by choosing it to be cither the left-sided limit = =im f(z)-](zu) or the right-sided z-2g
[(x))f((m)) of the function. Thus, the non-dilfereniaabiiiy is not interfering with effective limit b = lim x z-2g
continuous optimization through methods like gradient descent. For ReLU, the left-sided limit is 0 and the right-sided limit is 1, and PyTorch 2.7.1 chooses to return the left-sided limit in case of an input O
Furthermore, we do require differentiability and not only contimuity, as otherwise, gradient- free (black-box) optimization methods have to be used to solve Equation ( which is complex and NP-hard combinatorial optimization problem. In fact, the literature adversarial attacks for GNNs has converged to showing that
the most effective attacks against GNNs are usually gradient-baser attacks (Xu et al. 2019 Geisler et. al.
2021
Gosch et al. 2023a). which is consistent with the image domain (Tramerr et al. 2020).
G.2
Numerical Considerations on Relaxed Sparse Attention
The computation of ō:j = softmax(wsy) with myy = wij + log(Ps)) itself is numerically stable, even if Psj 0 for some j,j E V. However, to ensure that the gradient-taking w.r.t. Aí defining the "soft attention mask' log is also numerically well-behaved, we set the minimum value of Piý to some small > 0, which is a hyperparameter that we choose to be 10-9 9 for our experiments. Hence, Pi = 0 implying W, = -0 is never reached. This follows the strategy employed by the attack framework PR-BCD, which we leverage to exccute our attacks (see Section 5) For scalability, PR-BCD iteratively samples a batch of edges and only computes the gradient w.r.t. these edges. It always sets the minimum value of a sampled edge to some small e, to ensure proper gradients can be calculated, even if the edge does not originally exist in the graph.
G.3 On the Computational Complexity of the Derived Relaxations
In this section, discuss the computations of the different GT models that dominate their runtime complexity and how our relaxations affect/change these.
Graphormer. Depending on the concrete implementation and graph characteristics (sparsity), the most dominant computational step w.r.t. the number n of nodes in the graph in Graphormer is the shortest path calculation that has to be done for each pair of nodes, or the full-altention calculation also done between each node. The full node attention calculation is untouched by our relaxation. As the relaxation introduces continuous edge weights and thereby, during the attack itcrations, reduces the sparsity in the graph, this can slightly increase the time spent for the shortest path calculation, if a shortest path implementation is chosen that particularly leverages the sparsity in the graph (Cormen et al., 2009). However, this does not change the asymptotic time complexity of the shortest path algorithm. As the relaxation otherwise just introduces a linear interpolation of the PE vectors and the learnable scalars associated to discrete shortest-pan path distances, which can be computed constant time, it does not change the asymptotic runtime of Graphormer. Thus we can conclude that our relaxation fulfills Principle III.
SAN. SAN has two computations that have the potential to dominate its runtime complexity. First, the Laplacian PEs require to calculate the eigendecomposition of the Laplacian which can have a cubic worst-case complexity in the number of nodes. However, only the lowest k cigenvalues and associated cigenvectors are used where k is a hyperparameter and is usually set to a small value between 10- - 20 (see Table 5 which allows for faster computation. Our relaxation performs a first-order approximation of the eigenvalues and eigenvectors of the perturbed Laplacian (see Equations (8) and (19).. Computing these only requires access to the original cigendecomposition and thus, does not increase the runtime complexity. In the special case of repeated eigenvalues (see Appendix F.1. hnother eigendecomposition has to be computed, but only of the subblock associated to the repeated eigenvalues. Thus, in the theoretic worst case of all eigenvalues being repeated, two cigendecompositions instead of one have to be computed. However, this does not change the asymptotic runtime complexity and in practice, repeated eigenvalues are rare event occurring seldom if at all in a graph and thus, has little practical relevance for the runtime. Lastly, SAN employs full node attention through two sparse attention schemes (see Equation ). one computed over the neighborhood node and
As the ReLU function is also convex, this corresponds subderivative of the ReL. function
31

---

Published in Transactions on Machine Learning Research (09/2025)
computed over all non-ncighbours and thus, has quadratic complexity w.r.t. the number of nodes. Our relaxation technically relaxes both sparse attention mechanisms to full attention (see Equation 17 However, this does not change the asymptotic complexity, but can have a slight effect on the speed of computing the attention in practice. Conceptually, is still a sparse attention mechanism, but due to the continuity of the adjacency matrix paired with gradient-laking using PR-BCD, more edges (but al most b, where the block-size Geisler al. (2021)) have non-zero values in practice. To conclude, as the asymptotic runtime of SAN doesn't 't changed and the relaxation introduces some but not significant additional computation, we can conclude that Principle III is satisfied.
GRIT. As for GRIT the relaxation only makes the adjacency matrix continuous without introducing any other changes and a continuous adjacency matrix does not change any of the involved computations for GRIT, its runtime complexity is not affected. Thus, Prinple III satisfied.
GPS. GPS again has two potential dominating computations. First, uses Laplacian PEs. However, as discussed for SAN, our relaxation does not alfect its runtime complexity. The second is its global attention module that is not affected by our relaxation and which dominates the relaxed local GatedGCN computation. Thus, the relaxed GPS also fulfills Principle I11.
Polynormer. The only change in computation our relaxation introduces is in the sparse attention computation of GAT, by adding log Pij Pij to the attention logit computation Wij- Theoretically, this does not change the asymptotic runtime complexity of the attention computation, because if Pij = 0, i.e,, there is no edge (i,j), there no contribution of Wa (i.e., node j). the attention score aty. I.e., the difference is that the neighbourhood of the attention is now defined A.j > 0 instead of A.j in the non-relaxed case. Due to the continuity of the adjacency matrix paired with gradient-taking using PR-BCD, more edges but at most b, where b is the block-size (Geisserr et al., 2021), have non-zero values in practice. Thus, this can have effect, though not excessive, on the practical runtime of computing the sparse attention. In our implementation, we choose to follow the presentation of SAN's relaxed spare attention and technically implemented the relaxation as full attention. This can potentially dominate Polynormer's global attention computation that is Ondd)) if d2 < n. However, we find that this is practically not significant. for the datasets we considered and hence, together with the above theoretic consideration, can conclude that Principle III is satisfied.
32


Reviews:
[{"review_id": "RWBeSGOUr2", "reviewer": "Reviewer_q7D1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n(+) This work provides and instantiates the first comprehensive empirical studies on the adversarial robustness of GTs;\n\n(+) The authors develop several principles and relaxations in order to perform the adversarial attacks on GTs;\n\n(+) Empirical results demonstrate the effectiveness of the proposed attack methods;\n\n## Weakness\n\n(-) It's unclear whether the generated perturbations are semantically unnoticeable or not;\n\n(-) The attack is limited to white-box setting, which may not be practical;\n\n(-) The evaluation with respect to the improvements in robustness of adversarial training may not be fair;", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the adversarial robustness of graph transformers (GT). The authors design general principles and differentiable relaxations for adaptive gradient-based structure attacks tailored to GTs, accounting for their unique attention mechanisms and positional encodings. They instantiate these attacks for five representative GT architectures and evaluate them on multiple node and graph-level tasks, including structure perturbations and node injection attacks. The results reveal that GTs can be catastrophically vulnerable to adversarial attacks—sometimes even more so than classic GNNs. However, the study also demonstrates that adversarial training, when done with these adaptive attacks, can significantly improve the robustness of GTs, often surpassing traditional GNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It's unclear whether the generated perturbations are semantically unnoticeable or not. It'd be great if certain proof-of-concept evidence could be provided, as it's been shown that the adversarial attack without constraint may destroy the original graph distribution by [1]\n\n[1] Understanding and Improving Graph Injection Attack by Promoting Unnoticeability, ICLR'22.\n\n2. The attack is limited to white-box setting, which may not be practical. It's intereseting to also study the transferability across different GTs, in addition to the comparison between GTs and message-passing based GNNs.\n\n3. The evaluation with respect to the improvements in robustness of adversarial training may not be fair. The authors claim that \"he flexibility of GT models can lead to significantly better robust learning capabilities compared to classic message-passing GNNs.\", while it seems message-passing GNNs are not trained with adversarial attacks.\n\n4. The proposed attack is also limited in terms of the sizes of the graphs, due to its limitations in efficiency and scalability.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WvDGdqVd9u", "reviewer": "Reviewer_SPiU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Proposes novel adaptive gradient-based attacks specifically tailored to Graph Transformers, effectively addressing gaps left by prior work primarily focused on MPNNs\n\n+ Provides insights into the continuous relaxations required for effective gradient-based robust attacks, with a focus on GT architectures.\n\n+ Demonstrates significant robustness improvements through adversarial training validated by extensive empirical evaluation against baseline approaches.\n\n- The focus is rather narrow - untargeted global evasion attacks, which makes the practical applicability of the work very narrow. It does reduce the need for comparison with other interesting baselines even though the core method presented could have had a broader attack relevance and ideally have a more extensive baseline comparison (e.g. Netattack - [6] D. Zügner, A. Akbarnejad, S. Günnemann, \"Adversarial Attacks on Neural Networks for Graph Data\", KDD 2018). \n\n- The theoretical part of the paper is not well-explained and some questions below would help improve the presentation. It is not essential for the paper to have a principled/theoretically justified approach if the empirical results are strong and the paper has practical relevance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the adversarial robustness of Graph Transformers (GTs), proposing a gradient-based adaptive attacks specifically tailored for GT architectures. It analyzes vulnerabilities across various GT architectures featuring different attention mechanisms and Positional Encodings (PEs), demonstrating significant fragility to adversarial perturbations. The authors introduce general principles to facilitate continuous relaxations, which are necessary for these gradient-based attacks. Furthermore, they leverage these adaptive attacks to improve GT robustness substantially. The empirical evaluation across diverse datasets confirms both the efficacy of adaptive attacks and the superiority of the adversarial training approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Principle II is not obvious. The observation below the principle states \"We argue that in Principle II, we do not require continuous differentiability, as to obtain informative gradients w.r.t. the input data, we do not need to enforce stronger standards on ˜fθ than perhaps the most widely used activation function.\" Can authors further elaborate on why the requirement is only for the function to be \"differentiable almost everywhere\" and not \"differentiable\" (or for that matter only continuous with no differentiability requirement at all). \n\nFor equation 17, \"Note that for a discrete connected edge A˜′ij = 1, the log-probabilities become 0, or −∞ respectively. Thus, such an edge still fully contributes to the connected attention mechanism (over Ni), while not affecting the disconnected one (over V \\ Ni)\" - doesn't this lead to numerical instability? Is the choice of log function appropriate in Eqn 17? Wouldn't a function that saturates be better?", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rAksuMzgsR", "reviewer": "Reviewer_RNcs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1] The writing is clear throughout and the work is well-explained. I particularly enjoyed the review of the different Graph Transformers. \n\n2] The continuous relaxations that are applied to the different Graph Transformers are well-motivated and sensible. They also show good empirical performance.\n\n3] I think your selection of datasets (even though you do not have a very large number of them) is sensible. \n\n\nWeaknesses\n\n1] I struggle to think of any real weakness in this work that needs to be addressed. Overall, the work seems to be clearly described, sensible and proven to work in practice. I suppose one could question whether the presented relaxations are optimal and/or unique. But I do not think this needs to be addressed in the submitted manuscript.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In the submitted manuscript, the authors provide a very nice overview of the functioning of five relevant Graph Transformer (GT) architectures. They illustrate how current adversarial attack schemes do not apply to these due to their discrete, non-differentiable nature. The authors then define continuous relaxations of the model equations of the different GTs, which allows them to define both structure perturbation and node injection attacks. The effectiveness of these attacks is proven on several real-world datasets, on which an adversarial attack is somewhat realistic.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since my overall impression of this paper is very positive, I only have minor improvement suggestions below. I don't insist on any of these and would be okey with the authors refuting some of them with sufficient arguments. \n\n1] In Figure 1, when you write \"The strongest attack for each budget is shown.\" it would be good to specify out of how many attacks you select the strongest. \n\n2] The following sentence is a bit ambiguous: \"Then, by adding the log-probabilities of the edges belonging to one of the attention mechanisms to the attention logits, we obtain: [...]\" I think here it would be nice to specify which attention mechanisms are concerned since it was not perfectly clear from the context to me. \n\n3] In Section 4, when you explain your node injection attacks, you write \"we connect existing nodes from other graphs of an inductive graph dataset.\" Here it was not perfectly clear to me whether these nodes are connected to the graphs in isolation (as I suspect) or whether you establish links between graphs in your dataset by maintaining the other connections that the injected node has in its original graph. It may be good to make this explicit. \n\n4] You lack GRIT in the following list: \"We investigate the five representative GT models for which we developed continuous relaxations in § 3: Graphormer, SAN, GPS, and Polynormer.\"\n\n5] I found the repeated word \"to\" in the following sentence \"[...] PRBCD attack to a GCN model to the GT models\" confusing.\n\n6] It may be nice to add some further detail here: \"Note that for this dataset we were unable to train a comparable Polynormer model.\" Why were you unable to train this model?\n\n7] Also the \"Transferability\" setting should be slightly more explicitly defined. The sentence \"We collected the adversarial examples generated for each of our adaptive GT attacks and applied them to the other models.\" was slightly too ambiguous for me to fully grasp which attacks, out of how many attacks, are transferred to what other models. It may be good to explicitly state that all five transformers are considered here. \n\n8] Some references lack detail, e.g., Bamieh (2022) does not have a venue.", "broader_impact_concerns": "I agree with the broader impact statement that was provided by the authors and have no further concerns to contribute myself.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)