Relaxing Graph Transformers for Adversarial Attacks

Philipp Foth 1 Lukas Gosch 1 2 Simon Geisler 1 Leo Schwinn 1 Stephan Günnemann 1

Abstract

They address inherent limitations of MPNNs such as oversmoothing, over-squashing, and limited receptive fields [5].
Despite their increasing popularity, the adversarial robustness of GTs is entirely unexplored. Consequently, the unknown stability of GTs poses a substantial risk in practicalapplications, where robustness is crucial. Yet evaluating,their robustness is non-trivial since they employ modified attention mechanisms and Positional Encodings (PEs) that areoften non-differentiable w.r.t. the graph structure. This renders the immediate application of standard gradient-based
adaptive attacks impossible. In prior work, similar issues
were addressed with adaptive attacks, tailored to specificarchitectures [6]–[8] including GNNs [9].

Existing studies have shown that Graph Neural Networks (GNNs) are vulnerable to adversarial attacks. Even though Graph Transformers (GTs) surpassed Message-Passing GNNs on
several benchmarks, their adversarial robustness
properties are unexplored. However, attacking
GTs is challenging due to their Positional Encodings (PEs) and special attention mechanisms
which can be difficult to differentiate. We overcome these challenges targeting three representative architectures based on (1) random-walk PEs,(2) pair-wise-shortest-path PEs, and (3) spectral
PEs – and propose the first adaptive attacks forGTs. We leverage our attacks to evaluate robustness to (a) structure perturbations on node classification; and (b) node injection attacks for (fakenews) graph classification. Our evaluation reveals
that they can be catastrophically fragile and underlines our work’s importance and the necessity
for adaptive attacks.

To provide the first analysis on the robustness of GTs, we
propose continuous relaxations and perturbation approximations that enable us to apply adaptive attacks to three
representative GT architectures. 1) Graph Inductive bias
Transformer (GRIT) [10], based on random walk PEs; 2)Graphormer [11], which uses pairwise shortest path PEs;
and 3) Spectral Attention Network (SAN) [12], with spectral PEs. We evaluate the adversarial robustness of the three
GT models for node and graph classification. To this end,
we propose a node injection attack (NIA) which we apply to attack fake news detection. Fig. 1 provides a directcomparison between the robustness of different GNNs andhighlights crucial robustness vulnerabilities of GTs.

1. Introduction
Graphs are versatile data structures that have applications
in a wide range of different domains and Graph Neural
Networks (GNNs) have become the tool of choice for many
learning tasks on graphs. Given the increasing popularityof GNNs, multiple studies in the past years have developed
adversarial attacks for GNNs and analyzed their robustness[1]–[3]. These studies mostly focus on Message-Passing
GNNs (MPNNs), such as the Graph Convolutional Network(GCN) [4] and show that GNNs are vulnerable to even slightgraph structure perturbations [1].

2. Background
Let G = (V, E) be an undirected attributed graph with n
nodes V = {v1 , ..., vn } and m edges. Let xi ∈ Rd be thefeature vector of node vi . Then the graph can be defined as
G = (A, X) with its symmetric binary adjacency matrix
A ∈ {0, 1}n×n and node feature matrix X ∈ Rn×d . The
diagonal degree matrix D with entries Dii = deg(vi ) =Pn
j=1 Aij and the normalized symmetric graph Laplacian11matrix Lsym = I − D − /2 AD − /2 can both be derived
from A. The GNNs considered in this work are functionsfθ (A, X) with model parameters θ, and H (l) denotes the
updated node representations in the model layers.

Recently, Graph Transformers (GTs) have started to increasingly outperform MPNNs in many common benchmarks [5].
1Department of Computer Science & Munich Data Science Institute, Technical University of Munich, Germany 2 Munich Center
for Machine Learning (MCML). Correspondence to: Philipp Foth<p.foth@tum.de>, Lukas Gosch <l.gosch@tum.de>.

Structure attacks. The attack objective is described by thefollowing optimization problem:nd

Published at the 2 Differentiable Almost Everything Workshop
at the 41 st International Conference on Machine Learning, Vienna, Austria. July 2024. Copyright 2024 by the author(s).

maxÃ s.t. ∥Ã−A∥0 <∆1

Latk (fθ (Ã, X))(1)

Relaxing Graph Transformers for Adversarial Attacks
80

80

60

Accuracy (%)

Accuracy (%)

Accuracy (%)

100
80
60
40

0
5
10
15
Edge modification budget (%)

0
5
10
15
Edge modification budget (%)(a) UPFD politifact.

(b) UPFD gossipcop.

Graphormer
GATv2
GAT
SAN
GCN
GRIT

60
40
20
0
2
4
Edge modification budget (%)(c) CLUSTER.

Figure 1. The classification accuracy for different GNNs with varying attack budget on the two UPFD Twitter fake news datasets (graphclassification, node injection attacks) and CLUSTER (node classification, structure attack). The strongest attack for each budget is shown.

where fθ is the GNN model with fixed parameters θ, Latk
is a suitable attack loss function, and Ã ∈ {0, 1}n×n is thediscrete perturbed adjacency matrix in relation to A with
the number of edge flips bounded by the budget ∆. It isconvenient to model the perturbation as a function of thebinary matrix indicating the edge flips B ∈ {0, 1}n×n :Ã = A + δA,

δA = (1n 1T
n − 2A) ⊙ B

For structure awareness, prior works commonly add Positional Encodings (PEs) to the node features: H (0) =X +ψ(A). We categorize the PEs roughly in three main categories: (1) random walk encodings, (2) distance encodings,
and (3) spectral encodings. In addition to PEs, many GTs
adapt the attention mechanism to capture relevant topological aspects of the graph explicitly in the attention operation.

(2)

with element-wise product ⊙. Applying a continuous relaxation B ∈ [0, 1]n×n to the combinatorial problem makes
optimization with gradient descent possible. In this setting,the entry Bij represents the probability that the edge (vi , vj )is flipped. Discrete perturbations can then be sampled fromthe continuous solution.
P The budget constraint becomes
E[Bernoulli(B)] =Bij ≤ ∆, which can be dealt withby using projected gradient descent [13]. For large graphs,
optimizing over all entries in B at once becomes infeasible.
Projected Randomized Block Coordinate Descent (PRBCD)
solves this with a strategy that optimizes over sampled random blocks of limited size [14].

3. Graph transformer relaxations
The main obstacles for gradient-based structure attacks on
GTs fθ are PEs and attention mechanisms that are designed
for a discrete graph structure. As a result, the model output
is often a discontinuous function of the continuous input
adjacency matrix Ã ∈ [0, 1]n×n , rendering continuous optimization ineffective. We identify such components in the GTmodels and continuously relax them: f˜θ . For designing thecontinuous relaxations, we identify three main principles:
Principle I: Relaxed and target models coincide for discrete inputs. The prediction should equal f˜θ (A) = fθ (A)for any discrete adjacency A ∈ {0, 1}n×n .

Graph transformers. GTs apply
the popular transformer architecture for sequences [15] to arbitrary
graphs. In this work, we focus on
GTs that apply global self-attention,
where each node can attend to allother nodes. A ‘vanilla’ structureunaware self-attention head is defined as:


QK T
V (3)
Attn(H) = σ √dkPrinciple II: f˜θ can interpolate “smoothly” between any
different discrete graphs. In other words, f˜θ (Ã) should
be continuous w.r.t. Ã but does not need to be continuously
differentiable.
Principle III: The relaxed model f˜θ must be efficient. It
is a critical property that the relaxation does not excessively
increase memory and runtime complexity.

Next, we introduce a representative GT for each of the PE
categories and propose continuous relaxations for problematic components based on these principles.

where Q = HWq , K = HWk ∈Figure 2. GenericRn×dk are the query and key projecGT architecture.
n×d
tions, V = XWv ∈ R
is thevalue projection, and σ is the softmax function. A generic
GT is depicted in Fig. 2. The individual attention scores are:Random-walk-based GRIT. The components of the GRIT
model [10] are already continuous and do not require additional relaxations for gradient-based attacks. Details on thearchitecture are given in Appendix B.

√

wij = Wq hi · Wk hj/ d,ewij
αij = σ(wij ) = P w
ikkeDistance-based Graphormer. The Graphormer model [11]learns a PE embedding vector z ∈ Rd for each integer degree value (# of neighbors) which are added to the node(4)2

Relaxing Graph Transformers for Adversarial Attacks(0)

features according to their degrees: hi = xi + zdeg(vi ) .
To allow for continuous degrees, we linearly interpolate between the PE embeddings of the two closest integer values:

For the approximation to hold with repeated eigenvalues,
special care for the choice of arbitrary eigenvectors that spanthe eigenspace is required, as described by Bamieh [17].

z̃deg(vi ) = η · zdl +1 + (1 − η) · zdl
with dl = ⌊deg(vi )⌋, η = deg(vi ) − dl

The SAN attention mechanism computes separate attention
scores between connected and unconnected nodes, using
different key and query weights. A hyperparameter γ ∈ R+
controls how the two scores are relatively scaled, varying
the bias towards sparse or full attention. To relax the binary
decision of whether an edge is real or fake, we add edges
with probability between 0 and 1 to both attention mechanisms. The contribution of the uncertain edges is weighted
relative to the probabilities of being real or fake using acorresponding bias:γα̃ij =
σ wfake,ij + log(1 − Ãij )
1+γ
(9)


1
+
σ wreal,ij + log(Ãij )
1+γ

(5)

Similarly, a learnable scalar b ∈ R is assigned to each discrete Shortest Path Distance (SPD). This value is added asa bias to the raw attention scores: wˆij = wij + bspd(vi ,vj ) ,.
When a very small edge probability lies on a (simple) shortest path, the path is less likely to exist in the discrete sampledadjacency matrix. Therefore, low edge probabilities should
only marginally affect the original SPDs. To model this relationship, we use the reciprocal of the continuous adjacency
matrix Rij = 1/Ãij for the SPDs. We interpolate again tohandle the continuous distance values and compute:b̃spd(vi ,vj ) = η · bsl +1 + (1 − η) · bsl

withsl = ⌊rspdij ⌋,η = rspdij − sl

(6)

For a discrete real edge, i.e., Ãij = 1, the logarithm terms
become −∞ and 0 respectively. The equation then simpli1
fies to αij = 1+γ
softmax (wreal,ij ), thus only contributing
to the ‘real’ attention scores, as in the original SAN. The
same can be shown for fake edges.

where rspdij = spd(vi , vj |R) is the sum of edge weightsthat lie on the shortest path from vi to vj for the graphdefined by R. Similar to ReLU activations, the distances
are not differentiable everywhere. However, we use the sum
over one possible shortest path as a proxy. Backpropagation
through this sum yields the gradients w.r.t the continuous
adjacency matrix. Note that for discrete edge probability
values 0 and 1, the reciprocal edge weights become −∞and 1, respectively, yielding the original distances. Hence,
we do not alter the clean predictions if δA = B = 0 (seePrinciple I).

4. Node injection attack
We also consider the relevant case of inserting nodes into
an existing graph structure. In contrast to the usual framingof Node Injection Attack (NIA), where the attacker alsochooses the node features for the new vicious nodes [18],we connect existing nodes from other graphs of an inductive
graph dataset. Therefore, the nodes’ features are fixed but
physically realizable even if, e.g., they represent embeddingsof natural language. Details are shown in Appendix C.

Spectral SAN. The SAN architecture [12] uses learned
Laplacian-based PEs (LPEs), starting with the eigendecomposition of the Laplacian Lsym = U ΛU T , where
diagonal entries of Λii = λi are the eigenvalues of Lsym
in ascending order, and the columns of U are the corresponding eigenvectors. While the Laplacian matrix itself
is a continuous functions of the entries in the adjacency
matrix, its eigen-decomposition poses challenges for gradient computation, especially w.r.t the eigenvectors. To avoid
direct gradient computation, we use results from matrix perturbation theory [16], [17] to approximate the perturbed
eigen-decomposition as a simpler function of the input perturbation. The perturbation is δLsym = L̃sym − Lsym ,where L̃sym is the Laplacian of the continuous adjacency
matrix Ã. The first-order approximations for the eigenvalues
and vectors are [17]:δΛ ≈ diag(U T δL U )Ũ = U + δU , δU ≈ −U Π ⊙ U T δL U ,(1
if λi ̸= λjwhere Πij = λi −λj0elseΛ̃ = Λ + δΛ,During the structure attack optimization, probabilities are
assigned to edges, yet for NIAs, node probabilities are also
relevant to allow for a smooth node insertion. To obtainthese from the edges, we propose a simple iterative computation. For a continuous connected graph, let N (vi ) be the
1-hop neighborhood of node vi . We can approximate theprobability pi of vi being connected to the graph, by using
the probability that it is connected to its neighbors and theprobability that these neighbors are connected to the graph.
We start with the assumption that all nodes are connected to(0)
the graph: pi = 1, and update using the edge probabilities:
Y
(t+1)
(t)
pi
=1−
(1 − Aij · pj )(10)
vj ∈N (vi )(7)

To to ensure that the model output is continuous w.r.t. node
injections, for graph level tasks we weigh the nodes’ contributions in the sum or mean graph-pooling by their probabilities. For GTs, we additionally use them to bias the attention
scores: ŵij = wij + log(pj ).

(8)

3

60
40
20

80

adaptive
randomtransfer

60

Accuracy (%)

adaptive
randomtransfer

Accuracy (%)

Accuracy (%)

80

40
20

0

5
10
15
Edge mod. budget (%)(a) GRIT.

0

5
10
15
Edge mod. budget (%)

adaptive
randomtransfer

60
40
20
0

Accuracy (%)

Relaxing Graph Transformers for Adversarial Attacks

40
20

5
10
15
Edge mod. budget (%)(b) Graphormer.

adaptive
randomtransfer

60(c) SAN.

0

5
10
15
Edge mod. budget (%)(d) GCN.

Figure 3. CLUSTER attack results.

5. Results

Table 1. Graphormer attacks using relaxations for a fixed budget
of 1% for CLUSTER unconstrained (u.) and constrained (c.).
Acc. (%)
Deg.
SPD
CLUSTER, u.
CLUSTER, c.

Fig. 1 shows the strongest attacks on the different GNNs
for CLUSTER and the UPFD fake news detection datasets.
It shows that some GTs can be surprisingly fragile. Moredetailed results are reported in Appendix E.

✓✓

Results for three attack types are shown: adaptive, transfer,and random. Adaptive is the gradient-based PRBCD attack
with our relaxations described in § 3. Random is a baseline
attack that randomly flips as many edges as the budget
allows. The random attack gets the same number of model
evaluations as the adaptive attack during optimization. Of
those, the strongest random perturbation is chosen. For atransfer attack, the perturbed graph generated by an adaptive
attack on one model is used as an adversarial input for adifferent GNN model. We report results for the strongest
transfer perturbation at each budget.

✓✓

randomclean

52.61 ± 0.57
46.78 ± 0.46
50.81 ± 0.41

60.00 ± 0.42
68.45 ± 0.37
60.66 ± 0.21

66.52 ± 0.61
77.89

70.29 ± 0.32
77.89

Table 2. SAN attacks using relaxations for a fixed budget of 1%
for CLUSTER unconstrained (u.) and constrained (c.).
Lap.
Acc. (%)
Atten.
pert.
CLUSTER, u.
CLUSTER, c.
✓✓

We evaluate our structure attacks on the inductive nodeclassification dataset CLUSTER [19]. It contains SBMgenerated graphs with 6 clusters, where each cluster has
one labeled node. The task is to predict which node belongs
to which cluster. The node classification accuracy for the
CLUSTER dataset for different attack budgets is shown in
Fig. 3. We hypothesize that the straightforward nature of
the task and dataset lead to the same type of perturbations,
independent of the model. This would explain the strongtransferability and little variation in robustness across models. This outcome positively indicates the effectiveness of
our adaptive attacks, as they consistently identify meaningful perturbations across all GTs. They may sometimes be
weaker than the transfer attacks simply due to a more difficult optimization function. To avoid the natural fragility inthe data, we also evaluate a constrained attack that prohibits
modifying edges to the labeled nodes.

✓✓

randomclean

53.95 ± 0.59
53.87 ± 0.26
57.12 ± 0.62

63.27 ± 0.27
63.20 ± 0.12
67.22 ± 0.17

65.70 ± 0.65
76.12

68.86 ± 0.32
76.12

Since there is not one that is consistently better than theothers, a good approach might be to try all combinations as
an ensemble and choose the strongest. A similar evaluation
for NIAs on the UPFD datasets is shown in Appendix E. It
indicates that only adding the node probability bias to theattention scores seems to be sufficient and leads to some ofour strongest attacks.
In conclusion, we empirically demonstrate that GTs canbe catastrophically fragile in some settings and remarkably
robust w.r.t. the studied attack in other settings. This diverse
picture underlines the importance and need for adaptive
attacks to reveal nuanced robustness properties. Similarly,
also the comparison of GT’s and MPNN’s robustness w.r.t.
the studied attacks does not allow for a conclusion about
which approach is superior in terms of robustness. Nevertheless, our work sets the important cornerstone for empiricalresearch in answering this very question.

Additionally, we attack the CLUSTER graphs with different
combinations of our relaxations. The results for Graphormer
and SAN are shown in Tab. 1 and 2 respectively. All continuous relaxations individually seem to provide somewhat
useful gradients and can be used to get better than random
results. Yet some lead to stronger attacks than others, andusing multiple does not seem to work better than just one.
4

Relaxing Graph Transformers for Adversarial Attacks

Acknowledgement[14]

This paper has been supported by the DAAD programme
Konrad Zuse Schools of Excellence in Artificial Intelligence,sponsored by the Federal Ministry of Education and Research.

[15]

References

[16]

[1]

[17]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

D. Zügner, A. Akbarnejad, and S. Günnemann, “Adversarial attacks on neural networks for graph data,” in Proceedings of the ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining, Jul. 2018,
pp. 2847–2856.
D. Zügner and S. Günnemann, “Adversarial attacks ongraph neural networks via meta learning,” in International
Conference on Learning Representations, 2019.
D. Zügner and S. Günnemann, “Certifiable robustness ofgraph convolutional networks under structure perturbations,” in Proceedings of the ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining,
Aug. 2020, pp. 1656–1665.
T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in International
Conference on Learning Representations, 2017.
L. Müller, M. Galkin, C. Morris, and L. Rampášek, “Attending to graph transformers,” Transactions on Machine
Learning Research, Feb. 2024.
A. Athalye, N. Carlini, and D. Wagner, “Obfuscated gradients give a false sense of security: Circumventing defenses
to adversarial examples,” in Proceedings of the 35th International Conference on Machine Learning, Jul. 2018,
pp. 274–283.
N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in Proceedings - IEEE Symposium on Security and Privacy, 2017, pp. 39–57.
F. Tramèr, N. Carlini, W. Brendel, and A. Madry, “Onadaptive attacks to adversarial example defenses,” in Proceedings of the 34th International Conference on Neural
Information Processing Systems, 2020.
F. Mujkanovic, S. Geisler, S. Günnemann, and A. Bojchevski, “Are defenses for graph neural networks robust?”
In Proceedings of the 36th International Conference on
Neural Information Processing Systems, 2022.
L. Ma, C. Lin, D. Lim, et al., “Graph inductive biases intransformers without message passing,” in Proceedings ofthe 40th International Conference on Machine Learning,
2023, pp. 23 321–23 337.
C. Ying, T. Cai, S. Luo, et al., “Do transformers really
perform bad for graph representation?” In Proceedings ofthe 35th International Conference on Neural Information
Processing Systems, 2021.
D. Kreuzer, D. Beaini, W. L. Hamilton, V. Létourneau, andP. Tossou, “Rethinking graph transformers with spectral
attention,” in Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
K. Xu, H. Chen, S. Liu, et al., “Topology attack and defense
for graph neural networks: An optimization perspective,”in IJCAI’19: Proceedings of the 28th International Joint
Conference on Artificial Intelligence, Jun. 2019, pp. 3961–
3967.

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

5

S. Geisler, T. Schmidt, H. Şirin, D. Zügner, A. Bojchevski,
and S. Günnemann, “Robustness of graph neural networks
at scale,” in Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
A. Vaswani, N. Shazeer, N. Parmar, et al., “Attention is
all you need,” in Proceedings of the 31st International
Conference on Neural Information Processing Systems,
2017, pp. 6000–6010.
G. W. Stewart and J. Sun, Matrix Perturbation Theory.
1990, ISBN: 9780126702309.
B. Bamieh, A tutorial on matrix perturbation theory (using
compact matrix notation), 2022. arXiv: 2002 . 05001[math.SP].
J. Wang, M. Luo, F. Suya, J. Li, Z. Yang, and Q. Zheng,“Scalable attack on graph data by injecting vicious nodes,”Data Min. Knowl. Discov., vol. 34, no. 5, pp. 1363–1389,
Sep. 2020.
V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio,
and X. Bresson, “Benchmarking graph neural networks,”
Journal of Machine Learning Research, vol. 24, no. 43,
pp. 1–48, 2023.
H. Dai, H. Li, T. Tian, et al., “Adversarial attack on graphstructured data,” in Proceedings of the 35th International
Conference on Machine Learning, 2018.
W. Jin, Y. Li, H. Xu, et al., “Adversarial attacks and defenses on graphs: A review, a tool and empirical studies,”
SIGKDD Explor. Newsl., vol. 22, pp. 19–34, 2 2021.
S. Günnemann, “Graph neural networks: Adversarial robustness,” in Graph Neural Networks: Foundations, Frontiers, and Applications, L. Wu, P. Cui, J. Pei, and L. Zhao,
Eds. 2022, pp. 149–176, ISBN: 9789811660542.
Y. Zhu, J. Huang, Y. Chen, R. Amor, and M. Witbrock,“A graph transformer defence against graph perturbation
by a flexible-pass filter,” Information Fusion, vol. 107, Jul.
2024.
L. Gosch, D. Sturm, S. Geisler, and S. Günnemann, “Revisiting robustness in graph machine learning,” in The
Eleventh International Conference on Learning Representations, 2023.
L. Lin, E. Blaser, and H. Wang, “Graph structural attack by
perturbing spectral distance,” in Proceedings of the ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2022, pp. 989–998.
D. Zhu, P. Cui, Z. Zhang, J. Pei, and W. Zhu, “High-orderproximity preserved embedding for dynamic networks,”
IEEE Transactions on Knowledge and Data Engineering,
vol. 30, pp. 2134–2144, 11 Nov. 2018.
A. Bojchevski and S. Günnemann, “Adversarial attacks on
node embeddings via graph poisoning,” in Proceedings ofthe 36th International Conference on Machine Learning,
2019, pp. 695–704.
H. Wang, Y. Dou, C. Chen, L. Sun, P. S. Yu, and K. Shu,
“Attacking fake news detectors via manipulating news social
engagement,” in ACM Web Conference 2023 - Proceedingsof the World Wide Web Conference, WWW 2023, 2023,
pp. 3978–3986.
X. Zou, Q. Zheng, Y. Dong, et al., “TDGIA: Effective injection attacks on graph neural networks,” in Proceedings of
the ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, 2021, pp. 2461–2471.

Relaxing Graph Transformers for Adversarial Attacks
[30]

[31]

[32]

[33]

[34]

[35]

L. Rampášek, M. Galkin, V. P. Dwivedi, A. T. Luu, G.
Wolf, and D. Beaini, “Recipe for a general, powerful, scalable graph transformer,” in Proceedings of the 36th International Conference on Neural Information Processing
Systems, 2022.
J. You, R. Ying, and J. Leskovec, “Design space for graphneural networks,” in Proceedings of the 34th International
Conference on Neural Information Processing Systems,
2020.
M. Fey and J. E. Lenssen, Fast graph representation learning with PyTorch Geometric, 2019. arXiv: 1903.02428[cs.LG].
Y. Dou, K. Shu, C. Xia, P. S. Yu, and L. Sun, “Userpreference-aware fake news detection,” in Proceedings ofthe 44th International ACM SIGIR Conference on Researchand Development in Information Retrieval, 2021, pp. 2051–
2055.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò,and Y. Bengio, “Graph attention networks,” in International
Conference on Learning Representations, 2018.
S. Brody, U. Alon, and E. Yahav, “How attentive are graphattention networks?” In International Conference on Learning Representations, 2022.

6

Relaxing Graph Transformers for Adversarial Attacks

A. Related work
Triggered by the seminal works of Zügner, Akbarnejad, and Günnemann [1] and Dai, Li, Tian, et al. [20], a research area
emerged spanning attacks, defenses, and certification of GNNs [21], [22]. However, GTs have been entirely neglected
despite their recent success on common benchmarks. Zhu, Huang, Chen, et al. [23] is the sole exception acknowledging thisresearch gap. However, they solely propose a robust and sparse transformer and evaluate it with non-adaptive poisoning
attacks. Thus, they do not shine light on the robustness of the diverse set of graph transformers nor do they study adaptive
attacks.
Our attack is rooted in the GNN robustness literature. Xu, Chen, Liu, et al. [13] proposes the first Projected Gradient
Descent attack for discrete L0 perturbations of the graph structure, with a focus on message-passing architectures. Geisler,
Schmidt, Şirin, et al. [14] extend this PGD with a randomization scheme to obtain the efficient Projected Randomized Block
Coordinate (PRBCD) attack. Gosch, Sturm, Geisler, et al. [24] extend PRBCD with local constraints, which is comparablewith our relaxed GTs. While highlighting the general nature of our framework, we leave the empirical evaluation for future
work. Further important related works are Lin, Blaser, and Wang [25], Zhu, Cui, Zhang, et al. [26], and Bojchevski andGünnemann [27], where the authors study similar approximations for perturbations on the eigen-decomposition of the graphLaplacian. Moreover, Wang, Dou, Chen, et al. [28] attack message-passing architectures on the UPFD fake news detection
using reinforcement learning. As an entry to Node Insertion Attacks (NIA), we refer to Wang, Luo, Suya, et al. [18] andZou, Zheng, Dong, et al. [29]B. Graph transformers
Graph transformers (GTs) apply the popular transformer architecture for sequences [15] to arbitrary graphs. A general GT
architecture is depicted in Fig. 2. In this work, we focus on GTs that apply global self-attention, where each node can attend
to all other nodes. A ‘vanilla’ structure-unaware self-attention head is defined as:(XWq )(XWk )T√(XWv )(11)
Attn(X) = softmax
dk
where Wq , Wk ∈ Rd×dk are the weights for the query and key projections, and Wv ∈ Rd×d is the value weight matrix. For
structure awareness, prior works commonly add Positional Encodings (PEs) to the node features:X̂ = X + ψ(A)(12)

GT categorization. We categorize the PEs roughly in three main categories: (1) random walk encodings, (2) distanceencodings, and (3) spectral encodings. In addition to PEs, many GTs adapt the attention mechanism to capture relevant
topological aspects of the graph explicitly in the attention operation. Some GT architectures can optionally leverage available
edge features, which we omit here since our evaluation data does not include any. Furthermore, edge features are typicallynot considered for pure structure perturbation attacks, as adding new edges would also require adding features for them.
Next, we introduce a representative GT for each of the PE categories.
(1) Random-walk-based GRIT. The GRIT model architecture [10] terms their PE Relative Random Walk Probabilities(RRWP). The random walk encodings are collected from a fixed-length walk of length k, which is a hyperparameter (usuallyk > 10). The PEs are based on the tensor:
P = [I, M , M 2 , ..., M k−1 ] ∈ Rn×n×k ,with

M = D −1 A

(13)This yields an embedding vector Pij ∈ Rk for each of the n2 node-pairs (vi , vj ). The diagonal vector entries are transformed(0)
to dimension d by a linear layer and added to the node features as PEs: hi = xi + g1 (Pii ). Additionally, all n2 vectors are(0)transformed by a separate linear layer and added as node-pair features: hi,j = g2 (Pij ). The node representations hi andnode-pair representations hi,j are updated in each transformer layer by a modified attention mechanism, which includes anadaptive degree-scaler that is applied to the node representations:hi = (hi ⊙ θ1 ) + log(1 + deg(vi )) · (hi ⊙ θ2 )where θ1 , θ2 ∈ Rd are learnable weights.
7(14)

Relaxing Graph Transformers for Adversarial Attacks(2) Distance-based Graphormer. The Graphormer model [11] uses degree PEs. For each discrete degree value there is alearnable embedding vector z ∈ Rd . The embeddings are added to the node features according to the node degrees:(0)hi= xi + zdeg(vi )(15)

Similarly, a learnable scalar b ∈ R is assigned to each discrete Shortest Path Distance (SPD). This value is added to the raw
attention scores and results in a re-weighting of the attention weights after applying the softmax function:wˆij = wij + bspd(vi ,vj ) ,αij = softmax(ŵij )

(16)

√

where wij = Wq hi · Wk hj/ d. For graph-level tasks, a virtual node is added to the graph with its own distinct learnable bias
bvirtual , which is used as graph representation in the pooling stage.
(3) Spectral SAN The SAN architecture [12] uses learned Laplacian-based PEs (LPEs), starting with the eigendecomposition of the Laplacian Lsym = U ΛU T , where diagonal entries of Λii = λi are the eigenvalues of Lsym
in ascending order λ1 ≤ λ2 ≤ ... ≤ λn , and the columns of U are the corresponding eigenvectors. Determined by a
hyperparameter, only the k-th smallest eigenvalues and their eigenvectors are used, which we write as Λk ∈ Rk×k andUk ∈ Rn×k . For each node vi , its PEs are initialized as the concatenation of the eigenvalues and the i-th row of Uk :Pi = [diag(Λk ) ∥ (Uk )i ] ∈ Rk×2

(17)

Further processing by a transformer encoder results in pi = f (Pi ) ∈ Rdp , which is concatenated to the node features:(0)hi = xi ∥pi . Additionally, the main graph transformer attention mechanism is 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 γ ∈ R+ controls how the two scores are
relatively scaled, varying the bias towards sparse or full attention:(√
1
Wq,real hi · Wk,real hj / d)if (vi , vj ) is a real edge
1+γ softmax (
αij =
(18)
√
γ
W
h
·
W
h
i
j
q,fakek,fake/ d) otherwise
1+γ softmax (Some graph transformer architectures (including all three chosen in this work) can optionally leverage available edge
features, which we omit here since our evaluation data does not include any. Furthermore, edge features are typically notconsidered for pure structure perturbation attacks, as adding new edges would also require adding features for them.

C. Node injection attack
We also consider the relevant case of inserting nodes into an existing graph structure. In contrast to the usual framing ofNode Injection Attack (NIA), where the attacker also chooses the node features for the new vicious nodes [18], we connect
existing nodes from other graphs of an inductive graph dataset. Therefore, the nodes’ features are fixed but physicallyrealizable even if, e.g., they represent embeddings of natural language. NIA in this inductive setting is also interesting for
attacking GTs since they allow to increase the graph size successively. This growth implies that the attention mechanism
must allow for a smooth insertion of nodes.
Let D = {G1 , ..., GN } be the dataset including all graphs, where each graph Gi = (Vi , Ei ) has nPi nodes Vi = {vi,1 , ..., vi,ni }with node feature matrix Xi ∈ Rni ×d . The total number of nodes in the dataset is nD =ni . Let Gatk be the graphthat is S
being attacked. We define the candidate set of injection nodes as the union of the nodes of all other graphs:
Vcs = Gi ∈D\Gatk Vi , which includes ncs = nD − natk nodes with corresponding features Xcs . It is of course possible torestrict this candidate set if is is not sensible or not feasible to include all nodes.

′
We can augment the original (connected) graph by adding the injection candidate set as isolated nodes. Then Gatk=′′
(Aatk , Xatk ) is the augmented graph with:
Aatk 0
Xatk′
nD ×nD′
Aatk =∈ {0, 1},
Xatk =∈ RnD ×d
(19)
Xcs
0
0

Edge-flip perturbations to this augmented adjacency matrix, Ã′ = A′ + δA′ , model both structure perturbations and node
injections together. As in Eq. 2, the perturbation δA′ can be expressed in terms of a binary edge flip matrix:


B E
′
′
′
∈ {0, 1}nD ×nD(20)Ã′ = A′ + (1n 1T
−
2A
)
⊙
B
,
with
B
=
n
ET F
8

Relaxing Graph Transformers for Adversarial Attacks

Since the number of edge flips is bounded by a budget usually much smaller than the candidate set size i.e., ∆ ≪ ncs , theperturbed augmented graph G̃ = (Ã′ , X ′ ) still mostly contains isolated nodes. Therefore, we prune away all disconnectedcomponents, which for the unperturbed graph simply reverts the augmentation: prune(G ′ ) = G. However, for a perturbed
augmented graph, this results in the perturbed graph that we are seeking:G̃ = (Ã, X̃) = prune(Ã′ , X ′ )(21)where, Ã ∈ {0, 1}ñ×ñ , X̃ ∈ Rñ×d , ñ = n + nin is the total number of nodes and nin is the number of new injected nodes.
The node injection attack objective can thus be written as:max

B ′ s.t. ∥B ′ ∥0 <∆Latk (fθ (G̃))(22)

where, fθ is the trained GNN and Latk is a suitable attack loss. Note that the edge flip budget ∆ is also an upper bound forthe number nodes that can be injected: 0 ≤ nin ≤ ∆.
Edge block sampling. To optimize the objective, we can apply the relaxation Bij ∈ [0, 1], as shown in § 2. In this case,
PRBCD [14] not only enables more efficient optimization, but setting a smaller block size is crucial to limit the numberof connected injection nodes during optimization, since GTs complexity scales with O(ñ2 ). Moreover, the edge samplingallows us to control which parts of B ′ in Eq. 20 to sample from, e.g. not sampling in B results in ‘pure’ node injections
without modifying edges in the original graph. For large candidate sets, we recommend only sampling from E, as samplingfrom the n2cs entries of F results in many disconnected injection node pairs that get pruned away.
Node probability attention bias. The continuous optimization of structure attacks in § 2 assigns probabilities to edges-flips,
while nodes are assumed to all be part of the graph. In contrast, during NIAs the nodes also have have certain probabilities
of being included. To obtain node probabilities from the edge weights in a general way, we propose a simple iterative
computation. For a continuous connected graph, let N (vi ) be the 1-hop neighborhood of node vi . We can approximate
the probability pi of vi being connected to the graph, by using the probability that it is connected to its neighbors and theprobability that these neighbors are connected to the graph. We start with the assumption that all nodes are connected to thegraph and update using the edge probabilities:
Y
(t+1)
(t)
(0)
pi
=1 −
(1 − Aij · pj ), with pi = 1(23)
vj ∈N (vi )The number of iterations should be set to match the expected longest chain of added injection nodes. Therefore very few
iterations (2-3) should suffice for most NIAs.
We use the node probability to compute a weighted sum or mean in the graph-pooling for graph level tasks, to ensure thatthe model output is continuous w.r.t. node injections. Additionally for GTs, we use the node probability to bias the global
pairwise attention scores which result a continuous weighting of the attention scores:ŵij = wij + log(pj ),D. Evaluation details

pj · ewij
eŵij
α̂ij = softmax(ŵij ) = P ŵ = P
wik
ik
ke
k pk · e(24)

Setup. We build our implementation on top of GPS [30], which uses the flexible GraphGym [31] framework of the PyG[32] library. All our experiments ran on an internal GPU cluster. Experiments that require less than 10GB of GPU memory
were conducted on a Nvidia GTX1080Ti (10GB), the others on V100 and A100 GPUs (32/40GB). Attacking a single graphin our experiments takes anywhere from a few seconds to a few minutes, depending on the graph and model sizes.
Datasets. We evaluate our structure attacks on the inductive node classification dataset CLUSTER [19]. It contains SBMgenerated graphs with 6 clusters, where each cluster has one labeled node. The average number of nodes is 117. The task isto predict which node belongs to which cluster. For training, we use the standard PyG train/val/test split of 10000/1000/1000
graphs, respectively. We use the UPFD Twitter fake news detection datasets from [33] to evaluate our node injection attacks.
There are 2 datasets: politifact, with political; and gossipcop with celebrity fake news. The average number of nodes is 131
and 58, respectively. The graphs consist of retweet trees, where the root node has features concerning both the news content
and the user who posted the news. All other nodes’ features are related to the users that retweeted the news. The task is9Relaxing Graph Transformers for Adversarial Attacks

40

60

40

0

5
10
15
Edge mod. budget (%)(a) GRIT.

60

40

0

5
10
15
Edge mod. budget (%)0(b) Graphormer.

adaptive
randomtransfer

60

40

20

20

20

20

adaptive
randomtransfer

Accuracy (%)

60

adaptive
randomtransfer

Accuracy (%)

Accuracy (%)

adaptive
randomtransfer

Accuracy (%)

80

80

5
10
15
Edge mod. budget (%)(c) SAN.

0

5
10
15
Edge mod. budget (%)(d) GCN.

Figure 4. CLUSTER constrained attack results.

binary classification whether the graph contains fake news or not. We use the standard PyG train/val/test split of 20/10/70%
of the 314/5464 graphs for politifact and gossipcop, respectively.
Due to the quadratic scaling in the number of nodes of the three chosen GTs, their application is limited to smaller graphs.
This renders evaluation on larger graph datasets commonly used in robustness studies impractical. While GTs are mostwidely applied to molecule data, adversarial attacks are of little practical relevance in that domain. Thus, we omit molecule
data from our evaluations.
Attacks. In this work we focus on untargeted white-box evasion attacks, i.e., an attacker with full knowledge of model anddata attempts to change the trained model’s prediction to any incorrect class at test time by slightly perturbing the input
graph structure. For node-level tasks we focus on global attacks that minimize the overall performance metric across all
nodes. For model training we do a random hyperparameter search, choosing the model with the highest validation metric.
This approach is consistent with common practice. As described in § 5, we show results for three attack types: adaptive,
transfer, and random for a range of different budgets.
For both CLUSTER and the UPFD datasets, we evaluate our attacks on the 50 first graphs in the test set and report averageand standard deviation over 4 random seeds. For node classification, we use tanh-margin attack loss, shown to be effectivein [14]. For the binary graph classification, we simply minimize/maximize the raw prediction score (before sigmoid) forlabels 1/0 as our attack loss. For CLUSTER attacks, we use a PRBCD block size of 20000. For UPFD, we use a small block
size of 1000, which is necessary due to the n2 scaling of GTs. For GCN it is possible to increase the block size, but we keep
it the same for comparability. We optimize all our adaptive attacks for 125 steps and sample 20 discrete perturbations fromthe result, of which we take the strongest. For all other attack hyperparameters, we use default values that performed well in
preliminary evaluations. For all results except the ablations, we use all of our continuous relaxations proposed in § 3.

E. Additional results
We present the first principled analysis on the robustness of GTs on three representative architecture types (GRIT, Graphormer,
SAN). 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 GTs on CLUSTER, which comprises simple, interpretable structures.
This exploration helps us evaluate the effectiveness of the proposed relaxations, ideally leading our attacks to target
semantically meaningful structures within the dataset. We address (B) through evaluations on UPFD. Here, we constrain
our attack to remain within the predefined tree structure of the dataset. As a result, the attack represents impersonating an
existing user who is retweeting the respective news article. This evaluation goes beyond previous robustness analyses ofcitation networks in GNNs [1], [14], offering a more practical use case and semantically meaningful attacks.
CLUSTER. The node classification accuracy for the CLUSTER dataset for different attack budgets is shown in Fig. 3.
Since only a single node in each cluster is labeled, attacking these labeled nodes requires little budget and leads to strong
attacks. We manually inspected the perturbations and confirmed that most edge modifications are connected to the labelednodes, which shows the efficacy of the attacks. The difference in attack strength between the adaptive and transfer attacks is
insignificant. This confirms our hypothesis that the straightforward nature of the task leads to the same type of semanticallymeaningful perturbations, independent of the model (modifying the edges to labeled nodes). This would explain the strongtransferability and little variation in robustness across models. This outcome positively indicates the effectiveness of ouradaptive attacks (A), as they consistently identify meaningful perturbations across all GTs. They may sometimes be weaker
10Relaxing Graph Transformers for Adversarial Attacks
80(a) GRIT pol.

(b) Graphormer pol.
adaptive
randomtransfer

60
40

100

20
40
Edge mod. budget (%)

0

0

20
40
Edge mod. budget (%)6040(e) GRIT, gos.

0

20
40
Edge mod. budget (%)

90
80
70

adaptive
randomtransfer

0(f) Graphormer, gos.

20
40
Edge mod. budget (%)(d) GCN, pol.
100

60
0

adaptive
randomtransfer40

20
40Edge mod. budget (%)

100

20

20

60

(c) SAN, pol.

adaptive
randomtransfer80

adaptive
randomtransfer

60

0

80

70

Accuracy (%)

adaptive
randomtransfer40

20
40Edge mod. budget (%)

100
Accuracy (%)

60

80

20
40
Edge mod. budget (%)(g) SAN, gos.

Accuracy (%)

0

Accuracy (%)

adaptive
randomtransfer

40

80

Accuracy (%)

Accuracy (%)

60

Accuracy (%)

Accuracy (%)

80

80
60
adaptive
randomtransfer

40
0

20
40
Edge mod. budget (%)(h) GCN, gos.

Figure 5. Attack results for the UPFD twitter datasets politifact (pol.) and gossipcop (gos.).

than the transfer attacks simply due to a more difficult optimization function (GCN has fewer non-differentiable components).
To avoid the natural fragility in the data, we also evaluate a constrained attack that prohibits modifying edges to the labelednodes, for which results are shown in Fig. 4. For CLUSTER, we additionally attack the GAT [34] and GATv2 [35] GNN
models and include the adversarial perturbations for these in the transfer attack. Results for these are also shown in Fig 1.
UPFD. For our node injection attack, we add all dataset nodes except for the graph roots into the candidate set since they
have unique properties and include user and news features. We do not allow for perturbations of the original tree structure.
If the discretely sampled perturbations do not have a tree structure, we take the maximum spanning tree (using the edge
probabilities) to ensure all perturbations are valid retweet trees.
The graph classification accuracy for different attack budgets is shown in Fig. 5. In contrast to the results observed for the
CLUSTER dataset, we note big robustness differences across models for UPFD. In general, Graphormer seems to be theleast robust and for which our adaptive attacks work best in comparison the baselines. For Graphormer on gossipcop therandom baseline creates significantly stronger attacks than the transfer attacks, highlighting the importance of adaptive
attacks. The adaptive attacks for GRIT are also significantly stronger than the baselines. The SAN attacks are the outlier, andfor gossipcop the random baseline generates significantly stronger attacks than both adaptive and transfer. The reason may
be that the Laplacian eigen-decomposition perturbation approximation does not hold well in the case of node injection. The
ablation in Tab. 4 also indicates that by disabling this relaxation much stronger attacks than reported in Fig. 5 are possible.
Our results reveal that GTs showcase catastrophic vulnerabilities to adversarial modifications of the graph structure, evenwhen these changes are constrained to meaningful perturbations. In comparison, the GCN model exhibits considerably higher
robustness. Furthermore, we cannot derive a consistent pattern concerning the robustness of the different GT architecturesand results differ depending on the dataset and attack. Both findings underscore the need for research into robust design
choices of architecture components, such as PEs, and modifications to the attention mechanism.
Ablations. We enable each of the continuous relaxations individually and in different combinations together. We report
the results for Graphormer and SAN in Tab. 3 and 4 respectively. The node probability relaxation only applies to the node
injection attacks on UPFD. The main insights from the results are: (a) all continuous relaxations individually seem to givesomewhat useful gradients and can be used to get better than random results. (b) some work better than others, and using
multiple does not seem to always work better than only one. We argue that they lead the optimization towards different
adversarial perturbations, targeting features relevant for different components. However, one is not consistently better thanthe other. (c) adding the node probability bias to the attention scores for node injection results is usually sufficient andleads to some of the strongest attacks. (d) A good approach might be to try all individually as an ensemble and choose thestrongest. Additionally, we check the attack strength for GRIT when enabling or disabling gradient computation through11Relaxing Graph Transformers for Adversarial Attacks

Table 3. Ablations for the Graphormer relaxations for a fixed budget of 1% for CLUSTER unconstrained (u.) and constrained (c.), and
10% for UPFD politifact (pol.) and gossipcop (gos.). Mean and standard deviation over 4 runs with different seeds.
Deg.
✓
✓

✓
✓

✓

Acc. (%)

SPD
CLUSTER, u.

CLUSTER, c.

52.61 ± 0.57
46.78 ± 0.46
50.81 ± 0.41

60.00 ± 0.42
68.45 ± 0.37
60.66 ± 0.21

Node
prob.

UPFD pol.

UPFD gos.

✓✓✓

67.0 ± 2.0
67.0 ± 2.0
66.5 ± 1.9

38.0 ± 0.0
38.0 ± 0.0
39.5 ± 1.9✓

66.5 ± 1.980.5 ± 3.4

38.5 ± 1.0
53.5 ± 1.0

85.0 ± 2.6
92.0

61.5 ± 4.1
98.0✓

randomclean

66.52 ± 0.61
77.89

Acc. (%)

70.29 ± 0.32
77.89

Table 4. Ablations for the SAN relaxations for a fixed budget of 1% for CLUSTER unconstrained (u.) and constrained (c.), and 10% for
UPFD politifact (pol.) and gossipcop (gos.). Mean and standard deviation over 4 runs with different seeds.
Atten.
✓
✓

Lap.
pert.
✓
✓

✓

Acc. (%)
CLUSTER, u.

CLUSTER, c.

53.95 ± 0.59
53.87 ± 0.26
57.12 ± 0.62

63.27 ± 0.27
63.20 ± 0.12
67.22 ± 0.17

Node
prob.

UPFD gos.

✓✓✓

83.5 ± 1.0
77.5 ± 1.0
83.5 ± 1.0

91.5 ± 4.1
91.5 ± 2.5
89.5 ± 1.9✓77.0 ± 1.2
86.0 ± 0.0

89.5 ± 3.4
90.1 ± 6.0

86.0 ± 0.0
86.0

87.5 ± 1.0
98.0✓

randomclean

65.70 ± 0.65
76.12

Acc. (%)
UPFD pol.

68.86 ± 0.32
76.12

certain parts of the model and show the results in Tab. 5. It is possible to get strong attacks even without computing gradients
through RRWP, which could be much more efficient computationally, depending on 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 thestrongest attacks we report.

F. Limitations
All our adversarial attacks do neither provide a guarantee nor insights about how close they are to the optimal adversarial
example. We note that this is common practice in the adversarial learning community. Nevertheless, if we are able to findan adversarial example, this proves the non-robustness of the studied model. Furthermore, we only look at three specificgraph transformer architectures. While the continuous relaxations described here may not always be directly applicableto other GTs, our approach for designing adaptive attacks should provide a useful guide for further relaxations of similar
components.

Table 5. Ablations for the GRIT relaxations for a fixed budget of 1% for CLUSTER unconstrained (u.) and constrained (c.), and 10% for
UPFD politifact (pol.) and gossipcop (gos.). Mean and standard deviation over 4 runs with different seeds.
RRWP
grad.

Deg.
grad.

✓
✓

✓
✓

✓
randomclean

Acc. (%)
CLUSTER, u.

CLUSTER, c.

44.07 ± 0.79
46.27 ± 0.36
49.51 ± 0.90

65.25 ± 0.22
65.70 ± 0.35
66.49 ± 0.49✓
69.13 ± 0.10
78.98

72.25 ± 0.29
78.98

12

Node
prob.

Acc. (%)
UPFD pol.

UPFD gos.

✓✓✓

34.5 ± 1.0
34.5 ± 1.0
34.5 ± 1.0

75.0 ± 2.6
74.5 ± 2.5
73.5 ± 1.0✓

34.5 ± 1.0
54.5 ± 1.9

73.5 ± 1.0
83.0 ± 2.0

76.0 ± 4.3
98.0

82.0 ± 0.084.0