# Graph Transformers: A Survey

Ahsan Shehzad, Feng Xia, , Shagufta Abid, Ciyuan Peng, , Shuo Yu, , Dongyu
Zhang, and Karin Verspoor  A. Shehzad, S. Abid, and D. Zhang are with School
of Software, Dalian University of Technology, Dalian 116620, China (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>F. Xia and
K. Verspoor are with School of Computing Technologies, RMIT University,
Melbourne, VIC 3000, Australia (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>C. Peng is with the Institute of Innovation,
Science and Sustainability, Federation University Australia, Ballarat 3353,
Australia (e-mail<EMAIL_ADDRESS>S. Yu is with School of Computer Science
and Technology, Dalian University of Technology, Dalian 116024, China (e-mail:
<EMAIL_ADDRESS>Corresponding author: Feng Xia 0000-0003-2116-2183
0000-0002-8324-1859 0000-0002-8661-1544

###### Abstract

Graph transformers are a recent advancement in machine learning, offering a
new class of neural network models for graph-structured data. The synergy
between transformers and graph learning demonstrates strong performance and
versatility across various graph-related tasks. This survey provides an in-
depth review of recent progress and challenges in graph transformer research.
We begin with foundational concepts of graphs and transformers. We then
explore design perspectives of graph transformers, focusing on how they
integrate graph inductive biases and graph attention mechanisms into the
transformer architecture. Furthermore, we propose a taxonomy classifying graph
transformers based on depth, scalability, and pre-training strategies,
summarizing key principles for effective development of graph transformer
models. Beyond technical analysis, we discuss the applications of graph
transformer models for node-level, edge-level, and graph-level tasks,
exploring their potential in other application scenarios as well. Finally, we
identify remaining challenges in the field, such as scalability and
efficiency, generalization and robustness, interpretability and
explainability, dynamic and complex graphs, as well as data quality and
diversity, charting future directions for graph transformer research.

###### Index Terms:

Graph transformer, attention, graph neural network, representation learning,
graph learning, network embedding

##  I Introduction

Graphs, as data structures with high expressiveness, are widely used to
present complex data in diverse domains, such as social media, knowledge
graphs, biology, chemistry, and transportation networks [1]. They capture both
structural and semantic information from data, facilitating various tasks,
such as recommendation [2], question answering [3], anomaly detection [4],
sentiment analysis [5], text generation [6], and information retrieval [7]. To
effectively deal with graph-structured data, researchers have developed
various graph learning models, such as graph neural networks (GNNs), learning
meaningful representations of nodes, edges and graphs [8]. Particularly, GNNs
following the message-passing framework iteratively aggregate neighboring
information and update node representations, leading to impressive performance
on various graph-based tasks [9]. Applications ranging from information
extraction to recommender systems have benefited from GNN modelling of
knowledge graphs [10].

More recently, the graph transformer, as a newly arisen and potent graph
learning method, has attracted great attention in both academic and industrial
communities [11, 12]. Graph transformer research is inspired by the success of
transformers in natural language processing (NLP) [13] and computer vision
(CV) [14], coupled with the demonstrated value of GNNs. Graph transformers
incorporate graph inductive bias (e.g., prior knowledge or assumptions about
graph properties) to effectively process graph data [15]. Furthermore, they
can adapt to dynamic and heterogeneous graphs, leveraging both node and edge
features and attributes. [16]. Various adaptations and expansions of graph
transformers have shown their superiority in tackling diverse challenges of
graph learning, such as large-scale graph processing [17]. Furthermore, graph
transformers have been successfully employed in various domains and
applications, demonstrating their effectiveness and versatility.

Existing surveys do not adequately cover the latest advancements and
comprehensive applications of graph transformers. In addition, most do not
provide a systematic taxonomy of graph transformer models. For instance, Chen
et al. [18] focused primarily on the utilization of GNNs and graph
transformers in CV, but they failed to summarize the taxonomy of graph
transformer models and ignored other domains, such as NLP. Similarly, Müller
et al. [12] offered an overview of graph transformers and their theoretical
properties, but they did not provide a comprehensive review of existing
methods or evaluate their performance on various tasks. Lastly, Min et al.
[19] concentrated on the architectural design aspect of graph transformers,
offering a systematic evaluation of different components on different graph
benchmarks, but they did not include significant applications of graph
transformers or discuss open issues in this field.

To fill these gaps, this survey aims to present a comprehensive and systematic
review of recent advancements and challenges in graph transformer research
from both design and application perspectives. In comparison to existing
surveys, our main contributions are as follows:

  1. 1.

We provide a comprehensive review of the design perspectives of graph
transformers, including graph inductive bias and graph attention mechanisms.
We classify these techniques into different types and discuss their advantages
and limitations.

  2. 2.

We present a novel taxonomy of graph transformers based on their depth,
scalability, and pre-training strategy. We also provide a guide to choosing
effective graph transformer architectures for different tasks and scenarios.

  3. 3.

We review the application perspectives of graph transformers in various graph
learning tasks, as well as the application scenarios in other domains, such as
NLP and CV tasks.

  4. 4.

We identify the crucial open issues and future directions of graph transformer
research, such as the scalability, generalization, interpretability, and
explainability of models, efficient temporal graph learning, and data-related
issues.

An overview of this paper is depicted in Figure 1. The subsequent survey is
structured as follows: Section II introduces notations and preliminaries
pertaining to graphs and transformers. Section III delves into the design
perspectives of graph transformers that encompass graph inductive bias and
graph attention mechanisms. Section IV presents a taxonomy of graph
transformers categorizing them based on their depth, scalability and pre-
training strategy. Additionally, a guide is provided for selecting appropriate
graph transformer models for diverse tasks and domains. Section V explores the
application perspectives of graph transformers on various node-level, edge-
level, and graph-level tasks, along with other application scenarios. Section
VI identifies open issues and future directions for research on graph
transformers. Lastly, Section VII concludes the paper and highlights its main
contributions.

Figure 1: Organization of this paper

##  II Notations and Preliminaries

In this section, we present fundamental notations and concepts utilized
throughout this survey paper. Additionally, we provide a concise summary of
current methods for graph learning and self-attention mechanisms which serve
as the basis for graph transformers. Table I includes mathematical notations
used in this paper.

TABLE I: Notations in this paper

Notation | Definition
---|---
$G=(V,E)$ | A graph with node set $V$ and edge set $E$
$N$ | Number of nodes
$M$ | Number of edges
$\textbf{A}\in\mathbb{R}^{N\times N}$ | Adjacency matrix of graph $G$
$\textbf{X}\in\mathbb{R}^{N\times d_{n}}$ | Node feature matrix, $\textbf{x}_{i}\in\textbf{X}$
$\textbf{F}\in\mathbb{R}^{M\times d_{e}}$ | Edge feature matrix
$\textbf{h}_{v}^{(l)}$ | Hidden state of node $v$ at layer $l$
$\phi$ | An update function for node states
$\oplus$ | An aggregation function for neighbor states
$N(v)$ | Neighbor set of node $v$
$f$ | A message function for the node and edge states
$\textbf{Q},\textbf{K},\textbf{V}$ | Query, key and value matrices for self-attention
$d_{k}$ | Dimension of query and key matrices
$\textbf{p}_{i}$ | Positional encoding of node $v_{i}$
$d(i,j)$ | The shortest path distance between node $v_{i}$ and node $v_{j}$
$\textbf{e}_{ij}$ | Edge feature between node $v_{i}$ and node $v_{j}$
$a_{ij}$ | Attention score between node $v_{i}$ and node $v_{j}$
$W,b$ | Learnable parameters for the self-attention layer
$\textbf{L}=\textbf{I}_{N}-\textbf{D}^{-1/2}\textbf{AD}^{-1/2}$ | Normalized graph Laplacian matrix
U | Eigenvectors matrix of L

###  II-A Graphs and Graph Neural Networks

A graph is a data structure consisting of a set of nodes (or vertices) $V$ and
a set of edges (or links) $E$ that connect pairs of nodes. Formally, a graph
can be defined as $G=(V,E)$, where $V=\\{v_{1},v_{2},\dots,v_{N}\\}$ is node
set with $N$ nodes and $E=\\{e_{1},e_{2},\dots,e_{M}\\}$ is edge set with $M$
edges. Edge $e_{k}=(v_{i},v_{j})$ indicates the connection between node
$v_{i}$ and node $v_{j}$, where $i,j\in\\{1,2,\dots,N\\}$ and
$k\in\\{1,2,\dots,M\\}$. A graph can be represented by an adjacency matrix
$\textbf{A}\in\mathbb{R}^{N\times N}$, where $A_{ij}$ indicates the presence
or absence of an edge between node $v_{i}$ and node $v_{j}$. Alternatively, a
graph can be represented by the edge list $E\in\mathbb{R}^{M\times 2}$, where
each row of $E$ contains the indices of two nodes connected by an edge. A
graph can also have node features and edge features that describe the
attributes or properties of nodes and edges, respectively. The features of the
nodes can be represented by a feature matrix $\textbf{X}\in\mathbb{R}^{N\times
d_{n}}$, where $d_{n}$ is the dimension of the node features. The edge
features can be represented by a feature tensor
$\textbf{F}\in\mathbb{R}^{M\times d_{e}}$, where $d_{e}$ is the dimension of
the edge features [20].

Graph learning refers to the task of acquiring low-dimensional vector
representations, also known as embeddings for nodes, edges, or the entire
graph. These embeddings are designed to capture both structural and semantic
information of the graph. GNNs are a type of neural network model that excels
at learning from graph-structured data. They achieve this by propagating
information along edges and aggregating information from neighboring nodes
[21]. GNNs can be categorized into two main groups: spectral methods and
spatial methods.

Spectral methods are based on graph signal processing and graph Fourier
transform, implementing convolution operations on graphs in the spectral
domain [22]. The Fourier graph transform is defined as
$\mathbf{\hat{X}}=\textbf{U}^{T}\textbf{X}\textbf{U}$, where
$\mathbf{\hat{X}}$ is the spectral representation of node feature matrix X and
U is the eigenvector matrix of the normalized graph Laplacian matrix
$\textbf{L}=\textbf{I}_{N}-\textbf{D}^{-1/2}\textbf{A}\textbf{D}^{-1/2}$,
where $\textbf{I}_{N}$ is the identity matrix and D is diagonal degree matrix
with $D_{ii}=\sum_{j=1}^{N}A_{ij}$. Spectral methods can capture global
information about the graph, but they suffer from high computational
complexity, poor scalability, and the lack of generalization to unseen graphs
[23].

Spatial methods are based on message-passing and neighborhood aggregation,
implementing convolution operations on graphs in the spatial domain [24]. The
message-passing framework is defined as:

$\begin{aligned}
\textbf{h}_{v}^{(l+1)}=\phi\left(\textbf{h}_{v}^{(l)},\bigoplus_{u\in\mathcal{N}(v)}f(\textbf{h}_{u}^{(l)},\textbf{h}_{v}^{(l)},\textbf{e}_{uv})\right)\end{aligned},$
(1)

where $\textbf{h}_{v}^{(l)}$ is the hidden state of node $v$ at layer $l$,
$\phi$ is an update function and $\oplus$ is an aggregation function.
$\mathcal{N}(v)$ is the set of neighbors of node $v$ and $f$ is a message
function that depends on node states and edge features. $\textbf{e}_{uv}$ is
the feature vector of the edge between nodes $u$ and $v$. Spatial methods can
capture local information of the graph, but they have limitations in modeling
long-range dependencies, complex interactions and heterogeneous structures
[25].

###  II-B Self-attention and transformers

Self-attention is a mechanism that enables a model to learn to focus on
pertinent sections of input or output sequences [26]. It calculates a weighted
sum of all elements in a sequence with weights determined by the similarity
between each element and a query vector. Formally, self-attention is defined
as:

$\begin{aligned}
\text{Attention}(\textbf{Q},\textbf{K},\textbf{V})=\text{softmax}\left(\frac{\textbf{QK}^{T}}{\sqrt{d_{k}}}\right)\textbf{V}\end{aligned},$
(2)

where Q, K and V are query, key and value matrices,respectively. $d_{k}$ is
the dimension of the query and key matrices. Self-attention can capture long-
range dependencies, global context and variable-length sequences without using
recurrence or convolution.

Figure 2:  An illustration of transformer architecture [13].

Transformers are neural network models that use self-attention as the main
building block [13]. Transformers consist of two main components: an encoder
and a decoder. The encoder takes an input sequence
$\textbf{X}=\\{\textbf{x}_{1},\textbf{x}_{2},\dots,\textbf{x}_{N}\\}$ and
generates a sequence of hidden states
$\textbf{Z}=\\{\textbf{z}_{1},\textbf{z}_{2},\dots,\textbf{z}_{N}\\}$. The
decoder takes an output sequence
$\textbf{Y}=\\{\textbf{y}_{1},\textbf{y}_{2},\dots,\textbf{y}_{N}\\}$ and
generates a sequence of hidden states
$\textbf{S}=\\{\textbf{s}_{1},\textbf{s}_{2},\dots,\textbf{s}_{N}\\}$. The
decoder also uses an attention mechanism to attend to the encoder's hidden
states. Formally, the encoder and decoder are defined as:

$\displaystyle\textbf{z}_{i}$
$\displaystyle=\text{EncoderLayer}(\textbf{x}_{i},\textbf{Z}_{<i}),$ (3)
$\displaystyle\textbf{s}_{j}$
$\displaystyle=\text{DecoderLayer}(\textbf{y}_{j},\textbf{S}_{<j},\textbf{Z}).$

Here, EncoderLayer and DecoderLayer are composed of multiple self-attention
and feed-forward sublayers. Transformers can achieve state-of-the-art results
on various tasks, such as machine translation [27], text mining [28, 29],
document comprehending [30, 31], image retrieval [32], visual question
answering [3], image generation [33], and recommendation systems [34, 35]. An
overview of vanilla transformer is shown in Figure 2.

Graph transformers integrate graph inductive bias into transformer to acquire
knowledge from graph-structured data [36]. By employing self-attention
mechanisms on nodes and edges, graph transformers can effectively capture both
local and global information of the graph. In particular, graph transformers
exhibit the ability to handle heterogeneous graphs containing diverse types of
nodes and edges, as well as complex graphs featuring higher-order structures
[12, 37].

##  III Design Perspectives of graph transformers

In this section, we discuss the primary architectures of graph transformers,
aiming to explore their design perspectives in depth. Particularly, we will
focus on two key components: graph inductive biases and graph attention
mechanisms, to understand how these elements shape graph transformer models’
capabilities.

###  III-A Graph Inductive Bias

Unlike Euclidean data, such as texts and images, graph data is non-Euclidean
data, which has intricate structures and lacks a fixed order and
dimensionality, posing difficulties in directly applying standard transformers
on graph data [16]. To address this issue, graph transformers incorporate
graph inductive bias to encode the structural information of graphs and
achieve effective generalization of transformers across new tasks and domains.
In this section, we explore the design perspectives of graph transformers
through the lens of graph inductive bias. We classify graph inductive bias
into four categories: node positional bias, edge structural bias, message-
passing bias, and attention bias (see Figure. 3).

Figure 3: Graph Inductive bias: (A) and (B) are local and global node
positional biases, respectively. (C) and (D) are local and global edge
structural biases, respectively. (E) and (F) are local and global attention
biases, respectively. Notably, message-passing bias is a kind of local
attention bias.

####  III-A1 Node Positional Bias

Node positional bias is a crucial inductive bias for graph transformers
because it provides information about the relative or absolute positions of
nodes in a graph [38]. Formally, given a graph $G=(V,E)$ with $N$ nodes and
$M$ edges, each node $v_{i}\in V$ has a feature vector
$\textbf{x}_{i}\in\mathbb{R}^{d}_{n}$. A graph transformer aims to learn a new
feature vector $\textbf{h}_{i}\in\mathbb{R}^{d}_{k}$ for each node by applying
a series of self-attention layers. A self-attention layer can be defined as:

$\displaystyle\textbf{h}_{i}=\sum_{j=1}^{n}a_{ij}W\textbf{x}_{j}+b,$ (4)

where $a_{ij}$ is the attention score between nodes $v_{i}$ and $v_{j}$,
measureing the relevance or similarity of their features. $W$ and $b$ are
learnable parameters. However this self-attention mechanism does not consider
the structural and positional information of nodes, which is crucial for
capturing graph semantics and inductive biases [39]. Node positional encoding
is a way to address this challenge by providing additional positional features
to nodes, reflecting their relative or absolute positions in the graph.

_Local Node Positional Encodings._ Building on the success of relative
positional encodings in NLP, graph transformers leverage a similar concept for
local node positional encodings. In NLP, each token receives a feature vector
that captures its relative position and relationship to other words in the
sequence [40]. Likewise, graph transformers assign feature vectors to nodes
based on their distance and relationships with other nodes in the graph [41].
This encoding technique aims to preserve the local connectivity and
neighborhood information of nodes, which is critical for tasks like node
classification, link prediction, and graph generation.

A proficient approach for integrating local node positional information
involves the utilization of one-hot vectors. These vectors represent the hop
distance between a node and its neighboring nodes [11]:

$\textbf{p}_{i}=[I(d(i,j)=1),I(d(i,j)=2),...,I(d(i,j)=max)].$ (5)

In this equation, $d(i,j)$ represents the shortest path distance between node
$v_{i}$ and node $v_{j}$ and $I$ is an indicator function that returns 1 if
its argument is true and 0 otherwise. The maximum hop distance is denoted by
$max$. This encoding technique was utilized by Velickovic et al. [42] to
enhance their Graph Attention Networks (GATs) with relative position-aware
self-attention. Another way to incorporate local node positional encodings in
a graph is by using learnable embeddings that capture the relationship between
two nodes [43, 44]. This approach is particularly useful when a node has
multiple neighbors with different edge types or labels. In this case, the
local node positional encoding can be learned based on these edge features:

$\displaystyle\textbf{p}_{i}=[f(\textbf{e}_{ij_{1}}),f(\textbf{e}_{ij_{2}}),...,f(\textbf{e}_{ij_{l}})],$
(6)

where $\textbf{e}_{ij}$ is edge feature between node $v_{i}$ and node $v_{j}$,
$f$ is a learnable function that maps edge features to embeddings and $l$ is
the number of neighbors considered.

To enhance the implementation of local node positional encodings in a broader
context, a viable strategy is leveraging graph kernels or similarity functions
to evaluate the structural similarity between two nodes within the graph [45,
37]. For instance, when a node exhibits three neighbors with unique subgraph
patterns or motifs in their vicinity, its local node positional encoding can
be computed as a vector of kernel values between the node and its neighboring
nodes:

$\textbf{p}_{i}=[K(G_{i},G_{j_{1}}),K(G_{i},G_{j_{2}}),...,K(G_{i},G_{j_{l}})].$
(7)

In this equation, $G_{i}$ refers to the subgraph formed by node $v_{i}$ and
its neighbors. The function $K$ is a graph kernel function that measures the
similarity between two subgraphs. Mialon et al. [46] utilized this approach in
their GraphiT model, which incorporates positive definite kernels on graphs as
relative positional encodings for graph transformers.

Local node positional encodings enhance the self-attention mechanism of graph
transformers by integrating structural and topological information of nodes.
This encoding approach offers the advantage of preserving the sparsity and
locality of graph structure, resulting in enhanced efficiency and
interpretability. However, a limitation of this method is its restricted
ability to capture long-range dependencies or global properties of graphs,
which are essential for tasks such as graph matching or alignment.

_Global Node Positional Encodings._ The concept of global node positional
encodings is inspired by the use of absolute positional encodings in NLP [47].
In NLP, as mentioned previously, every token receives a feature vector
indicating its position within a sequence. Extending this idea to graph
transformers, each node can be assigned a feature vector representing its
position within the embedding space of the graph [48]. The objective of this
encoding technique is to encapsulate the overall geometry and spectrum of
graphs, thereby unveiling its intrinsic properties and characteristics.

One method for obtaining global node positional encodings is to leverage
eigenvectors or eigenvalues of a matrix representation, such as adjacency
matrix or Laplacian matrix [39]. For instance, if a node’s coordinates lie
within the first k eigenvectors of graph Laplacian, its global node positional
encoding can be represented by the coordinate vector:

$\textbf{p}_{i}=[u_{i1},u_{i2},...,u_{ik}],$ (8)

where $u_{ij}$ is $j$-th component of $i$-th eigenvector of the graph
Laplacian matrix. One alternative approach to incorporating global node
positional encodings is by utilizing diffusion or random walk techniques, such
as personalized PageRank or heat kernel [49]. For example, if a node possesses
a probability distribution over all other nodes in the graph, following a
random walk [50], its global node positional encoding can be represented by
this probability vector:

$\textbf{p}_{i}=[\pi_{i1},\pi_{i2},...,\pi_{iN}],$ (9)

where $\pi_{ij}$ is the probability of reaching node $v_{j}$ from node $v_{i}$
after performing a random walk on the graph.

A more prevalent approach to implementing global node positional encodings is
to utilize graph embedding or dimensionality reduction techniques that map
nodes to a lower-dimensional space while maintaining a sense of similarity or
distance [51]. For instance, if a node possesses coordinates in a space
derived from applying multi-dimensional scaling or graph neural networks to
the graph, its global node positional encoding can be represented by that
coordinate vector:

$\textbf{p}_{i}=[y_{i1},y_{i2},...,y_{ik}],$ (10)

where $y_{ij}$ is $j$-th component of $i$-th node embedding in a
$k$-dimensional space, which can be obtained by minimizing the objective
function that preserves graph structure:

$\min_{\textbf{Y}}\sum_{i,j=1}^{N}\textbf{w}_{ij}\|\textbf{y}_{i}-\textbf{y}_{j}\|^{2}.$
(11)

Here, $\textbf{w}_{ij}$ is a weight matrix that reflects the similarity or
distance between node $v_{i}$ and node $v_{j}$, $Y$ is the matrix of node
embeddings.

The primary aim of global node positional encodings is to improve the
representation of node attributes in graph transformers by incorporating
geometric and spectral information from graphs. This encoding method offers
the advantage of capturing long-range dependencies and overall graph
characteristics, benefiting tasks like graph matching and alignment. However,
a drawback of this encoding approach is that it could undermine the sparsity
and locality of graph structures, potentially impacting efficiency and
interpretability.

####  III-A2 Edge Structural Bias

In the realm of graph transformers, edge structural bias is crucial for
extracting and understanding complex information within graph structure [52].
Edge structural bias is versatile and can represent various aspects of graph
structure, including node distances, edge types, edge directions and local
sub-structures. Empirical evidence has shown that edge structural encodings
can improve the effectiveness of graph transformers [53, 54, 55].

_Local Edge Structural Encodings._ Local edge structural encodings capture the
local structure of a graph by encoding relative position or distance between
two nodes [52]. These encodings borrow ideas from relative positional
encodings used in NLP and CV, where they are used for modeling sequential or
spatial order of tokens or pixels [56]. However, in the context of graphs, the
concept of relative position or distance between nodes becomes ambiguous due
to the presence of multiple connecting paths with varying lengths or weights.
Consequently, the scientific community has proposed various methods to define
and encode this information specifically for graph structures.

GraphiT [46] introduces local edge structural encodings to graph transformers.
It promotes the use of positive definite kernels on graphs to measure node
similarity considering the shortest path distance between them. The kernel
function is defined as:

$k(u,v)=\exp(-\alpha d(u,v)),$ (12)

where $u$ and $v$ are two nodes in a graph, $d(u,v)$ is their shortest path
distance and $\alpha$ is a hyperparameter that controls decay rate. The kernel
function is then used to modify the self-attention score between two nodes as:

$\text{Attention}(\textbf{Q},\textbf{K},\textbf{V})=\text{softmax}(\frac{\textbf{QK}^{T}}{\sqrt{d_{k}}}+k(\textbf{Q},\textbf{K}))\textbf{V},$
(13)

where $k(\textbf{Q},\textbf{K})$ is the matrix of kernel values computed for
each pair of nodes. EdgeBERT [57] proposes using edge features as additional
input tokens for graph transformers. These edge features are obtained by
applying a learnable function to the source and target node features of each
edge. The resulting edge features are then concatenated with node features and
fed into a standard transformer encoder.

More recently, the Edge-augmented Graph Transformer (EGT) [58] introduces
residual edge channels as a mechanism to directly process and output both
structural and node information. The residual edge channels are matrices that
store edge information for each pair of nodes. They are initialized with
either an adjacency matrix or the shortest path matrix and updated at each
transformer layer by applying residual connections. These channels are then
used to adjust the self-attention score between two nodes

$\text{Attention}(\textbf{Q},\textbf{K},\textbf{V},\textbf{R}_{e})=\text{softmax}(\frac{\textbf{QK}^{T}}{\sqrt{d_{k}}}+\textbf{R}_{e})\textbf{V},$
(14)

where $\textbf{R}_{e}$ is the residual edge channel matrix.

Although local edge structural encodings can capture detailed structural
information, they may have limitations in capturing overall structural
information. This can lead to increased computational complexity or memory
usage as pairwise information needs to be computed and stored. Additionally,
the effectiveness of these encodings may vary depending on the selection and
optimization of encoding or kernel function for different graphs and tasks.

_Global Edge Structural Encodings._ Global edge structural encodings aim to
capture the overall structure of a graph. Unlike NLP and CV domains, the exact
position of a node in graphs is not well-defined because there is no natural
order or coordinate system [59]. Several approaches have been suggested to
tackle this issue.

GPT-GNN [60] is an early work that utilizes graph pooling and unpooling
operations to encode the hierarchical structure of a graph. It reduces graph
size by grouping similar nodes and then restoring the original size by
assigning cluster features to individual nodes. This approach results in a
multiscale representation of graphs and has demonstrated enhanced performance
on diverse tasks. Graphormer [11] uses spectral graph theory to encode global
structure. It uses eigenvectors of normalized Laplacian matrix as global
positional encodings for nodes. This method can capture global spectral
features (e.g., connectivity, centrality and community structure). Park et al.
[41] extended Graphormer by using singular value decomposition (SVD) to encode
global structure. They utilized the left singular matrix of the adjacency
matrix as global positional encodings for nodes. This approach can handle both
symmetric and asymmetric matrices.

Global edge structural encodings excel at capturing coarse-grained structural
information at the graph level, benefiting tasks that require global
understanding. However, they may struggle with capturing fine-grained node-
level information and can lose data or introduce noise during encoding. In
addition, their effectiveness may depend on the choice of encoding technique
and matrix representations.

####  III-A3 Message-passing Bias

Message-passing bias is a crucial inductive bias for graph transformers to
facilitate learning from the local structure of graphs [61]. This bias enables
graph transformers to exchange information between nodes and edges, thereby
capturing dependencies and interactions among graph elements. Moreover,
message-passing bias helps graph transformers in overcoming certain
limitations of standard transformer architecture, such as the quadratic
complexity of self-attention, the absence of positional information and
challenges associated with handling sparse graphs [39]. Formally, message-
passing bias can be expressed as follows:

$\textbf{h}_{v}^{(t+1)}=f(\textbf{h}_{v}^{(t)},\\{\textbf{h}_{u}^{(t)}:u\in\mathcal{N}(v)\\},\\{\textbf{e}_{uv}:u\in\mathcal{N}(v)\\}).$
(15)

Here, $\textbf{h}_{v}^{(t)}$ is the representation of node $v$ at layer $t$,
$u$ is a neighboring node of node $v$, $\textbf{e}_{uv}$ is the feature of the
edge between nodes $v$ and $u$, and $f$ is the function that aggregates
information from neighbors and edges. Incorporation of message-passing bias in
graph transformers can be achieved through three primary approaches:
preprocessing, interleaving and post-processing (as illustrated in Figure 4 ).
These approaches vary in how they combine message-passing operations with
self-attention layers within transformer architecture.

Figure 4: Incorporation of message-passing bias in transformer model.

_Preprocessing._ Preprocessing involves applying message-passing operations to
node features before feeding them to self-attention layers [36]. This
technique aims to augment node features with local structural information,
making them more compatible with global self-attention. Preprocessing can
maintain the integrity of the original transformer architecture without making
any modifications and utilize message-passing modules from existing GNNs. It
can be mathematically defined as follows:

$\displaystyle\textbf{h}_{v}^{(t)}$
$\displaystyle=f(\textbf{h}_{v}^{(t-1)},\\{\textbf{h}_{u}^{(t-1)}:u\in\mathcal{N}(v)\\},\\{\textbf{e}_{uv}:u\in\mathcal{N}(v)\\}),$
(16) $\displaystyle\textbf{h}_{v}^{(t+1)}$
$\displaystyle=\text{SelfAttention}(\textbf{h}_{v}^{(t)},\\{\textbf{h}_{u}^{(t)}:u\in
V\\}).$

Here, $\textbf{h}_{v}^{(0)}=\textbf{x}_{v}$, $\textbf{x}_{v}$ is input feature
of node $v$, SelfAttention is a function that performs self-attention over all
nodes.

The limitation of preprocessing is that it applies message-passing only once
before self-attention layers. This approach may not fully capture intricate
interactions between nodes and edges on various scales. Additionally, the
preprocessing step may introduce redundancy and inconsistency between the
message-passing module and the self-attention layer as they both serve similar
functions of aggregating information from neighboring elements.

_Interleaving._ Interleaving refers to the technique employed in graph
transformer architecture that involves alternating message-passing operations
and self-attention layers [62, 16, 63]. The objective of this technique is to
achieve a balance between local and global information processing, thereby
enabling multi-hop reasoning over graphs. By integrating message-passing
modules into core components of graph transformers, interleaving enhances
their expressive power and flexibility. It can be mathematically defined as
follows:

$\displaystyle\textbf{h}_{v}^{(t+1)}$
$\displaystyle=\theta+\text{SelfAttention}(\textbf{h}_{v}^{(t)},\\{\textbf{h}_{u}^{(t)}:u\in
V\\}),$ (17) $\displaystyle\theta$
$\displaystyle=f(\textbf{h}_{v}^{(t)},\\{\textbf{h}_{u}^{(t)}:u\in\mathcal{N}(v)\\},\\{\textbf{e}_{uv}:u\in\mathcal{N}(v)\\}).$

One drawback of the interleaving technique is its impact on the complexity and
computational requirements of graph transformers. This is due to the need for
additional parameters and operations compared to pre-processing or post-
processing. Furthermore, interleaving can potentially lead to interference and
conflict between the message-passing module and the self-attention layer as
they each update node representations in distinct manners.

_Post-processing._ Post-processing refers to the technique of applying
message-passing operations to node representations obtained from self-
attention layers [64, 58]. The purpose of this approach is to refine and
adjust node representations based on underlying graph structure, thereby
enhancing their interpretability and robustness. By doing so, this method aims
to improve the quality and utility of node representations for downstream
tasks and applications. It can be mathematically defined as follows:

$\displaystyle\textbf{h}_{v}^{(t+1)}$
$\displaystyle=\text{SelfAttention}(\textbf{h}_{v}^{(t)},\\{\textbf{h}_{u}^{(t)}:u\in
V\\}),$ (18) $\displaystyle\textbf{h}_{v}^{(T+1)}$
$\displaystyle=f(\textbf{h}_{v}^{(T)},\\{\textbf{h}_{u}^{(T)}:u\in\mathcal{N}(v)\\},\\{\textbf{e}_{uv}:u\in\mathcal{N}(v)\\}).$

Here, $T$ is the final layer of the graph transformer.

The drawback of post-processing is its limited application of message-passing
after self-attention layers, potentially failing to capture intricate
semantics and dynamics of graph data. Additionally, post-processing runs the
risk of introducing noise and distortion to node representations as it has the
potential to overwrite or override information acquired by self-attention
layers.

####  III-A4 Attention Bias

Attention bias enables graph transformers to effectively incorporate graph
structure information into the attention mechanism without message-passing or
positional encodings [39, 65]. Attention bias modifies attention scores
between nodes based on their relative positions or distances in the graph. It
can be categorized as either local or global depending on whether it focuses
on the local neighborhood or global topology of the graph.

_Local Attention Bias._ Local attention bias limits the attention to a local
neighborhood surrounding each node. This concept is analogous to the message-
passing mechanism observed in GNNs [66]. It can be mathematically defined as
follows:

$\begin{aligned} \alpha_{ij}=\frac{\exp(g(\mathbf{x}_{i},\mathbf{x}_{j})\cdot
b_{ij})}{\sum_{k\in\mathcal{N}(v_{i})}\exp(g(\mathbf{x}_{i},\mathbf{x}_{k})\cdot
b_{ik})}\end{aligned},$ (19)

where $\alpha_{ij}$ is the attention score between node $v_{i}$ and node
$v_{j}$, $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are their node features, $g$ is
a function that computes the similarity between two nodes, such as dot-product
and linear transformation. $b_{ij}$ is a local attention bias term that
modifies attention score based on the distance between node $v_{i}$ and node
$v_{j}$. The local attention bias term can be either a binary mask that only
allows attention within a certain hop distance [67, 42, 36] or a decay
function that decreases attention score with increasing distance [68, 64].

_Global Attention Bias._ Global attention bias integrates global topology
information into the attention mechanism independent of message-passing and
positional encodings [69]. It can be mathematically defined as follows:

$\displaystyle\alpha_{ij}=\frac{\exp(g(\mathbf{x}_{i},\mathbf{x}_{j})+c(\mathbf{A},\mathbf{D},\mathbf{L},\mathbf{P})_{ij})}{\sum_{k=1}^{N}\exp(g(\mathbf{x}_{i},\mathbf{x}_{k})+c(\mathbf{A},\mathbf{D},\mathbf{L},\mathbf{P})_{ik})}.$
(20)

Here, $c$ is the function that computes the global attention bias term,
modifying attention score based on some graph-specific matrices or vectors,
such as adjacency matrix $\mathbf{A}$, degree matrix $\mathbf{D}$, Laplacian
matrix $\mathbf{L}$, and PageRank vector $\mathbf{P}$. The global attention
bias term can be additive or multiplicative to the similarity function [46,
70]. Generally, global attention bias can enhance the global structure
awareness and expressive power of graph transformers [70].

###  III-B Graph Attention Mechanisms

Graph attention mechanisms play an important role in the construction of graph
transformers [71]. By dynamically assigning varying weights to nodes and edges
in the graph, these mechanisms enable transformers to prioritize and emphasize
the most relevant and important elements for a given task [72]. Specifically,
a graph attention mechanism is a function that maps each node $v_{i}\in V$ to
a vector $\textbf{h}_{i}\in\mathbb{R}^{d_{k}}$:

$\textbf{h}_{i}=f_{n}(\textbf{x}_{i},\\{\textbf{x}_{j}\\}_{v_{j}\in\mathcal{N}(v_{i})},\\{A_{ij}\\}_{v_{j}\in\mathcal{N}(v_{i})}),$
(21)

where $f_{n}$ is a nonlinear transformation, $\textbf{x}_{i}$ is the input
feature vector of node $v_{i}$, $\textbf{x}_{j}$ is the input feature vector
of node $v_{j}$. The function $f_{n}$ can be decomposed into two parts: an
attention function and an aggregation function.

The attention function computes a scalar weight for each neighbor of node
$v_{i}$, denoted by $\alpha_{ij}$, which reflects the importance or relevance
of node $v_{j}$ for node $v_{i}$:

$\alpha_{ij}=\text{softmax}_{i}(\text{LeakyReLU}(\textbf{W}_{a}[\textbf{x}_{i}||\textbf{x}_{j}])),$
(22)

where $\textbf{W}_{a}\in\mathbb{R}^{1\times 2d_{n}}$ is a learnable weight
matrix, $||$ is the concatenation operation, and
$\text{softmax}_{i}$normalizes weights over all neighbors of node $v_{i}$. The
aggregation function combines the weighted features of the neighbors to obtain
the output representation of node $v_{i}$:

$\textbf{h}_{i}=\textbf{W}_{h}\left(\textbf{x}_{i}+\sum_{v_{j}\in\mathcal{N}(v_{i})}\alpha_{ij}\textbf{x}_{j}\right),$
(23)

where $\textbf{W}_{h}$ is another learnable weight matrix. Graph attention
mechanisms have the potential to extend their application beyond nodes to
edges. This can be achieved by substituting nodes with edges and utilizing
edge features instead of node features [73]. Furthermore, stacking of graph
attention mechanisms in multiple layers allows for the utilization of output
representations from one layer as input features for the subsequent layer
[74].

####  III-B1 Global Attention Mechanisms

Global attention mechanisms can determine how each node calculates its
attention weights across all other nodes in the graph [75]. Global attention
mechanisms can be broadly categorized into two types: quadratic attention
mechanisms and linear attention mechanisms.

_Quadratic Attention Mechanisms._ Quadratic attention mechanisms are derived
from the conventional self-attention formula. This formula calculates
attention weights by applying a softmax function to scale the dot product
between the query and key vectors of each node:

$\displaystyle\alpha_{ij}=\frac{\exp(\frac{\mathbf{q}_{i}^{\top}\mathbf{k}_{j}}{\sqrt{d_{k}}})}{\sum_{n=1}^{N}\exp(\frac{\mathbf{q}_{i}^{\top}\mathbf{k}_{n}}{\sqrt{d_{k}}})}.$
(24)

The computational complexity of this method is $O(N^{2})$.

One of the pioneering studies that has introduced quadratic attention
mechanisms for graph transformers is the work by Velickovic et al.[42]. The
authors proposed the use of multiple attention heads to capture different
types of relations between nodes. Choromanski et al.[76] introduced the Graph
Kernel Attention Transformer (GKAT), an approach that integrates graph
kernels, structural priors, and efficient transformer architectures. GKAT
leverages graph kernels as positional encodings to capture the structural
characteristics of the graph while employing low-rank decomposition techniques
to minimize the memory requirements of quadratic attention:

$\displaystyle\alpha_{ij}$
$\displaystyle=\frac{\exp(\frac{\mathbf{q}_{i}^{\top}\mathbf{k}_{j}}{\sqrt{d_{k}}}+\mathbf{p}_{i}^{\top}\mathbf{p}_{j})}{\sum_{n=1}^{N}\exp(\frac{\mathbf{q}_{i}^{\top}\mathbf{k}_{n}}{\sqrt{d_{k}}}+\mathbf{p}_{i}^{\top}\mathbf{p}_{n})},$
(25) $\displaystyle\mathbf{z}_{i}$
$\displaystyle=\sum_{j=1}^{N}\alpha_{ij}(\mathbf{U}\mathbf{V}^{\top})_{ij}$

where $\textbf{z}_{i}$ is the output vector of node $v_{i}$, $\mathbf{p}_{i}$
is the positional encoding vector of node $v_{i}$, which is computed by
applying a graph kernel function to node features. $\mathbf{U}$ and
$\mathbf{V}$ are low-rank matrices that approximate value matrix in the GKAT
model. GKAT also introduced a novel kernel-based masking scheme to control the
sparsity of the attention matrix. Yun et al. [36] introduced Graph Transformer
Networks (GTN), an approach that uses multiple layers of quadratic attention
to acquire hierarchical representations of graphs. GTN further enhances
attention computation by incorporating edge features through the use of
bilinear transformations instead of concatenation. This innovative technique
demonstrates the potential for improved graph representation learning in the
field of graph analysis.

Quadratic attention mechanisms possess a significant advantage in capturing
extensive dependencies and global information within graphs, thereby offering
potential benefits for various graph learning tasks. Nonetheless, these
mechanisms have some limitations, including their computationally expensive
nature, high memory consumption, and susceptibility to noise and outliers.
Additionally, quadratic attention mechanisms may not effectively preserve and
leverage local information within graphs which holds significance in certain
domains and tasks.

_Linear Attention Mechanisms._ Linear attention mechanisms employ different
approximations and hashing techniques to decrease the computational complexity
of self-attention from $O(N^{2})$ to $O(N)$ [77]. These mechanisms can be
categorized into two subtypes: kernel-based linear attention mechanisms and
locality-sensitive linear attention mechanisms.

Kernel-based linear attention mechanisms leverage the concept of employing
kernel functions to map query and key vectors into a feature space that allows
efficient computation of their inner products [78, 79]. In the work by
Katharopoulos et al. [80], Linear Transformer Networks (LTN) were introduced.
LTN utilizes random Fourier features as kernel functions to approximate self-
attention:

$\displaystyle\alpha_{ij}$
$\displaystyle=\frac{\exp(\frac{\phi(\mathbf{q}_{i})^{\top}\phi(\mathbf{k}_{j})}{\sqrt{d_{k}}})}{\sum_{n=1}^{N}\exp(\frac{\phi(\mathbf{q}_{i})^{\top}\phi(\mathbf{k}_{n})}{\sqrt{d_{k}}})},$
(26) $\displaystyle\phi(\mathbf{x})$
$\displaystyle=\sqrt{\frac{2}{m}}[\cos(\omega_{1}^{\top}\mathbf{x}+b_{1}),...,\cos(\omega_{m}^{\top}\mathbf{x}+b_{m})]^{\top}.$

Here, $\phi$ is a random Fourier feature function that maps input vector into
a $m$-dimensional feature space. $\omega_{i}$ and $b_{i}$ are randomly sampled
from a Gaussian distribution and a uniform distribution, respectively.

Locality-sensitive linear attention mechanisms are based on the concept of
employing hashing functions to partition the query and key vectors into
discrete buckets that facilitate local computation of their inner products
[81, 82, 83]. Kitaev et al. [84] introduced the Reformer model which uses
locality-sensitive hashing (LSH) as a hashing function to approximate self-
attention:

$\displaystyle\alpha_{ij}$
$\displaystyle=\frac{\exp(\frac{\mathbf{q}_{i}^{\top}\mathbf{k}_{j}}{\sqrt{d_{k}}})}{\sum_{n\in
B_{i}}\exp(\frac{\mathbf{q}_{i}^{\top}\mathbf{k}_{n}}{\sqrt{d_{k}}})},$ (27)
$\displaystyle B_{i}$
$\displaystyle=\\{j|h(\mathbf{q}_{i})=h(\mathbf{k}_{j})\\},$

where $h$ is an LSH function that maps the input vector into a bucket index
and $B_{i}$ is a set of nodes that share the same bucket index with node
$v_{i}$. RGN also incorporated edge features into the attention computation
using a shared query-key projection matrix.

Linear attention mechanisms offer a significant advantage in terms of reducing
computational cost and memory usage in self-attention, thereby enabling graph
transformers to efficiently process large-scale graphs. However, they do come
with certain limitations, including approximation error, hashing collision and
loss of global information. Additionally, linear attention mechanisms may not
be capable of capturing intricate or nonlinear relationships between nodes.

####  III-B2 Local Attention Mechanisms

Local attention mechanisms determine how each node computes its attention
weights over a subset of nodes in the graph [85]. Local attention mechanisms
can be broadly categorized into two types: message-passing attention
mechanisms and spectral attention mechanisms.

_Message-passing Attention Mechanisms._ Message-passing attention mechanisms
are built on the foundational framework of message-passing neural networks
(MPNNs) [86], which iteratively aggregate messages from neighboring nodes to
compute node representations. To enhance MPNNs, message-passing attention
mechanisms employ self-attention to compute messages or aggregation weights
[61, 87, 88, 39]. The computational complexity of this method is $O(E)$, where
$E$ represents the number of edges in the graph.

One of the pioneering works in introducing message-passing attention
mechanisms for graph transformers is GraphSAGE [89]. GraphSAGE proposes the
use of mean pooling as an aggregation function and self-attention as a
combination function. Additionally, GraphSAGE incorporates node sampling
techniques to efficiently handle large-scale graphs. The function can be
mathematically defined as:

$\displaystyle\mathbf{h}_{i}^{(l+1)}$
$\displaystyle=\text{ReLU}(\mathbf{W}^{(l)}[\mathbf{h}_{i}^{(l)}\|\text{MEAN}(\\{\mathbf{h}_{j}^{(l)},\forall
v_{j}\in\mathcal{N}(v_{i})\\})])$ (28) $\displaystyle\mathbf{z}_{i}$
$\displaystyle=\sum_{l=0}^{L}\alpha_{il}\mathbf{h}_{i}^{(l)}.$

Here, $\mathbf{h}_{i}^{(l)}$ is hidden vector of node $v_{i}$ at layer $l$,
$\mathbf{W}^{(l)}$ is a linear transformation matrix, $\|$ is the
concatenation operator, MEAN indicates a mean pooling function. $\alpha_{il}$
means an attention weight between node $v_{i}$ and layer $l$. More recently,
Javaloy et al. [90] proposed L-CAT which uses self-attention as both an
aggregation function and a combination function. L-CAT also incorporates edge
features into the attention computation by using bilinear transformations.
Message-passing attention mechanisms, while adept at preserving and leveraging
local graph information, are constrained by scalability issues, such as
limited expressiveness and graph connectivity dependence. Their capacity to
capture long-range dependencies and global graph information is also
questionable.

_Spectral Attention Mechanisms._ Spectral attention mechanisms are founded on
the concept of transforming node features into a spectral domain, where the
graph structure is encoded by eigenvalues and eigenvectors of the graph
Laplacian matrix [91]. Spectral attention mechanisms employ self-attention to
calculate spectral coefficients and spectral filters [92]. The computational
complexity of this approach is $O(N)$.

Wang et al. [22] proposed graph isomorphism networks (GIN) as a spectral
attention mechanism for graph transformers, employing an expressive
aggregation function of sum pooling and self-attention. GIN also integrates a
unique graph readout scheme via set functions to encapsulate global graph
characteristics. The equations of GIN are as follows:

$\displaystyle\mathbf{h}_{i}^{(l+1)}$
$\displaystyle=\text{MLP}^{(l)}((1+\epsilon^{(l)})\mathbf{h}_{i}^{(l)}+\sum_{j\in\mathcal{N}(v_{i})}\mathbf{h}_{j}^{(l)}),$
(29) $\displaystyle\mathbf{z}_{i}$
$\displaystyle=\sum_{l=0}^{L}\alpha_{il}\mathbf{h}_{i}^{(l)},$
$\displaystyle\mathbf{z}_{G}$
$\displaystyle=\text{READOUT}(\\{\mathbf{z}_{i},\forall v_{i}\in V\\}).$

Here, $\text{MLP}^{(l)}$ is a multi-layer perceptron, $\epsilon^{(l)}$ is a
learnable parameter, READOUT indicates a set function that aggregates node
output vectors into a graph output vector. $\mathbf{z}_{G}$ is the output
vector of graph $G$. In addition, Nguyen et al. [93] introduced UGformer, a
self-attention-based method for the spectral coefficient computation of each
node using eigenvalues and eigenvectors of the Laplacian graph matrix.
UGformer further integrates edge features into spectral computation via
bilinear transformations.

Spectral attention mechanisms possess the ability to incorporate the
structural information of a graph into the spectral domain, thereby offering
potential benefits for certain tasks or domains. However, they are also
accompanied by certain limitations, including high computational cost, memory
consumption and sensitivity to graph size and density.

##  IV Taxonomy of Graph Transformers

The past few years have witnessed a surge of interest in graph transformers.
This section dives into four key categories dominating the current literature:
shallow, deep, scalable, and pre-trained graph transformers. By analyzing
representative models within each category, we aim to establish valuable
guidelines for designing effective graph transformers.

###  IV-A Shallow Graph Transformers

Shallow graph transformers represent a class of GNNs that leverage the power
of self-attention to acquire node representations from data structured in
graphs. Inspired by transformer models, which effectively capture long-range
dependencies in sequential data through self-attention, shallow graph
transformers extend this concept to graph data by computing self-attention
weights based on both node features and graph topology [94]. The primary
objective of shallow graph transformers is to achieve exceptional performance
while minimizing computational complexity and memory usage.

Shallow graph transformers can be seen as a generalization of graph attention
networks (GAT) [42]. GAT use a multi-head attention mechanism to calculate
node embeddings. However, GAT has some limitations, such as the inability to
model edge features and lack of diversity among attention heads [95]. Several
GAT extensions have been proposed in the literature to address these issues.
For example, GTN by Yun et al. [36] introduces edge-wise self-attention to
incorporate edge information into node embeddings. Ahmad et al.[63] proposed
the graph attention transformer encoder (GATE), which applies a masked self-
attention mechanism to learn different attention patterns for different nodes.
GATE also uses a position-wise feed-forward network and dropout to enhance
model capacity and generalization. The summary of shallow graph transformer
methods is given in Table II.

Shallow graph transformers are efficient and adaptable capable of handling
various graph learning tasks and different types of graphs, but their lack of
depth and recurrence may limit their ability to capture complex dependencies.
Their performance can also be influenced by the choice of mask matrix and the
number of attention heads, indicating a need for further research on their
optimal design and regularization.

TABLE II: Shallow graph transformers

Model |  Graph inductive bias |  Graph attention mechanisms |  Application |  Dataset |  Code availability
---|---|---|---|---|---
|  Node Positional encoding |  Edge Structural Encoding |  Message-Passing Bias |  Global attention |  Local Attention |  |
Graph Transformer [16] |  Yes (local) |  Yes (local) |  Yes (pre-processing) |  No |  Yes (message passing) |  Graph representation learning |  ZINC, PATTERN, CLUSTER |  Yes
GAT [42] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Node classification of graph-structured data |  Cora, Citeseer, Pubmed, PPI |  Yes
GATv2 [95] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Graph representation learning |  OGB, QM9, VARMISUSE |  Yes
GTN [36] |  No |  No |  No |  No |  Yes (message passing) |  Node classification on heterogeneous graphs |  DBLP, ACM, IMDB |  Yes
GATE [63] |  No |  No |  No |  Yes (linear) |  No |  Cross-lingual relation and event extraction |  ACE 2005 corpus |  Yes
PiT [96] |  No |  No |  No |  Yes (quadratic) |  No |  Image classification, object detection |  ImageNet, COCO, ImageNet-A |  Yes
WDPruning [97] |  No |  No |  No |  Yes (quadratic) |  No |  Image classification and image retrieval |  CIFAR-10 and ILSVRC-12 |  No
SVT [98] |  No |  No |  No |  Yes (quadratic) |  No |  Image classification |  Synthetic data and CIFAR-10 |  No
Gubelmann et al. [99] |  No |  No |  No |  Yes |  No |  Natural language inference (NLI) |  SNLI and MNLI |  No
TADDY [100] |  Yes (global and local) |  No |  No |  Yes (linear) |  No |  Anomaly detection in dynamic graphs |  UCI Messages, Enron, DBLP, Facebook, Twitter and Reddit. |  No
Tree Transformer [38] |  Yes (local) |  No |  No |  Yes (quadratic) |  No |  Program translation and semantic parsing |  For2Lam, CoffeeScript-JavaScript, JOBS, GEO, ATIS |  Yes
GAT-POS [43] |  Yes (local) |  No |  No |  Yes (linear) |  Yes (message passing) |  Node classification |  Chameleon, Squirrel, Actor, Cora, Citeseer, Pubmed |  No
DGT [45] |  Yes |  No |  No |  Yes (linear) |  No |  Node classification on graphs |  Actor, Squirrel, Chameleon, Cora, Citeseer, twitch-gamers, ogbn-arxiv, Reddit |  No
EDTER [54] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Edge detection |  BSDS500, NYUDv2, Multicue |  Yes
BGT-Net [55] |  No |  No |  No |  Yes |  No |  Scene Graph Generation for Images |  Visual Genome (VG), OpenImages (OI), Visual Relationship Detection (VRD) |  No
PMPNet [61] |  No |  No |  Yes (pre-processing) |  No |  Yes (message passing) |  3D object detection |  nuScenes |  Yes
GAMLP [74] |  No |  No |  No |  Yes (linear) |  Yes (spectral) |  Node classification |  14 real-world graph datasets |  Yes
SA-GAT [101] |  No |  No |  No |  Yes (linear) |  Yes (spectral) |  Graph classification |  MUTAG, PTC, NCI1, NCI109, PROTEINS, ENZYMES, DD and COLLAB |  No
GKAT [76] |  No |  No |  No |  Yes (linear) |  No |  Graph classification and graph pattern detection |  Bioinformatics and social networks datasets, ImageNet dataset |  No
EcoFormer [78] |  No |  No |  No |  Yes (linear) |  No |  Image classification and long-range tasks |  CIFAR-100, ImageNet-1K, Long Range Arena |  Yes
Reformer [84] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  NLP and generative tasks |  Synthetic task, enwik8, imagenet64, WMT 2014 English-German |  Yes
LISA [85] |  No |  No |  No |  Yes (linear) |  No |  Sequential recommendation |  Alibaba, Amazon Video Games, MovieLens 1M, MovieLens 25M |  Yes

###  IV-B Deep Graph Transformers

Deep graph transformers consist of multiple self-attention layers stacked on
top of each other, with optional skip connections, residual connections or
dense connections between layers [102]. They are designed to achieve higher
performance with increased model depth and complexity [103]. Deep graph
transformers extend shallow graph transformers by applying self-attention
layers to node features and graph topology hierarchically.

However, deep graph transformers also face several challenges that need to be
addressed. One challenge is the difficulty of training deeper models, which
can be mitigated by employing techniques, such as PairNorm introduced in
DeeperGCN [104]. Another challenge is the over-smoothing problem, which can be
addressed by using a gated residual connection and a generalized convolution
operator as proposed in DeeperGCN. Additionally, the disappearance of global
attention capacity and the lack of diversity among attention heads are
challenges that can be tackled by approaches like DeepGraph [94]. DeepGraph
incorporates substructure tokens and local attention to improve the focus and
diversity of global attention.

Deep graph transformers, while complex, can achieve top-tier results on
various graph learning tasks and adapt to different types of graphs and
domains. However, their high computational cost, difficulty in optimization,
and sensitivity to hyperparameters necessitate further research for optimal
design and training. Table III summarizes the methods of deep graph
transformers.

TABLE III: Deep graph transformers

Model |  Graph inductive bias |  Graph attention mechanisms |  Application |  Datasets |  Code availability
---|---|---|---|---|---
|  Node Positional encoding |  Edge Structural Encoding |  Message-Passing Bias |  Global attention |  Local Attention |  |
HG-Transformer [102] |  No |  No |  No |  Yes (linear) |  No |  Multi-label text classification |  RCV1, RCV1-2K, AmazonCat-13K |  No
Unfolded Transformer [103] |  No |  No |  No |  Yes (quadratic) |  No |  Graph neural networks and NLP |  IMDB and SST2 |  Yes
DeepGraph [94] |  Yes (relative) |  No |  No |  Yes (linear) |  Yes (message passing) |  Graph representation learning |  PCQM4M-LSC, ZINC, CLUSTER, PATTERN |  Yes
GraphWriter [105] |  No |  Yes |  No |  Yes (linear) |  No |  Text generation from knowledge graphs |  AGENDA dataset |  Yes
GraphLoG [106] |  No |  No |  Yes (pre-processing) |  No |  Yes (message passing) |  Graph representation learning |  ZINC15, MoleculeNet, Protein ego-networks |  Yes
DIET [40] |  Yes |  No |  No |  Yes (quadratic) |  No |  cross-lingual generalization, machine translation |  GLUE, XTREME, WMT 2018 |  No
GRPE [41] |  Yes (local and global) |  Yes (local and global) |  No |  Yes (linear) |  No |  Graph representation learning |  ZINC, MolPCBA, MolHIV, PATTERN, CLUSTER, PCQM4M, PCQM4Mv2 |  No
Graphormer [11] |  No |  Yes |  No |  Yes (quadratic) |  No |  Graph representation learning |  PCQM4M-LSC, OGB, ZINC |  Yes
Relation-aware Self-Attention [26] |  No |  Yes (local) |  No |  Yes (quadratic) |  No |  Machine translation |  WMT 2014 English-German and English-French |  Yes
GraphiT [46] |  Yes (local and global) |  No |  No |  Yes (quadratic) |  Yes (message passing) |  Graph representation learning for classification and regression tasks |  MUTAG, PROTEINS, PTC, NCI1, ZINC |  Yes
Tree Transformer [48] |  Yes (global and local) |  No |  No |  Yes (quadratic) |  Yes (message passing) |  Code representation learning |  Python150k and JavaScript150k |  Yes
MagLapNet [49] |  Yes (local and global) |  No |  No |  Yes (quadratic) |  Yes (spectral) |  Graph learning tasks such as correctness testing of sorting networks and source code understanding |  Synthetic graphs, OGB Code2 |  Yes
SAT [52] |  Yes (local and global) |  No |  No |  Yes (quadratic) |  Yes (message passing) |  Graph representation learning for graph and node property prediction |  ZINC, CLUSTER, PATTERN, OGBG-PPA, OGBG-CODE2 |  Yes
Edge Transformer [107] |  Yes |  Yes |  No |  Yes (quadratic) |  No |  Improve systematic generalization in natural language understanding and relational reasoning tasks |  CLUTRR, CFQ and COGS |  Yes
Cai et al. [62] |  Yes |  Yes |  No |  Yes (quadratic) |  No |  Graph-to-sequence learning |  LDC2015E86, LDC2017T10, WMT16 English-German, WMT16 English-Czech |  Yes
SAN [66] |  Yes (local and global) |  No |  No |  Yes (quadratic) |  Yes (spectral) |  Graph representation learning |  ZINC, PATTERN, CLUSTER, MolHIV, MolPCBA |  Yes
KMCA [79] |  No |  No |  No |  Yes (quadratic) |  Yes (message passing) |  Time series analysis |  Synthetic, FordA, uWave, IMDB, ECG |  No
ABT-MPNN [87] |  No |  No |  Yes (pre-processing) |  Yes (quadratic and linear) |  No |  Molecular property prediction and biological activity prediction |  Johnson et al. [108], Tox21, ClinTox, ToxCast, HIV, QM8, ESOL, FreeSolv, Lipophilicity and QM8. |  Yes
UGformer [93] |  No |  No |  No |  Yes (quadratic) |  No |  Graph classification and text classification |  COLLAB, IMDB-B, IMDB-M, DD, PROTEINS, MUTAG, PTC, MR, R8, R52, Ohsumed |  Yes
DTI-GTN [109] |  No |  Yes |  Yes (interleaving) |  Yes (quadratic) |  No |  Drug-target interaction prediction |  Peng et al. [110] dataset |  No
Dual-GCN+Transformer [111] |  No |  No |  No |  Yes (linear) |  No |  Image Captioning |  MS COCO and Visual Genome |  Yes
SGTransformer [112] |  Yes |  Yes |  No |  Yes (quadratic) |  Yes (message passing) |  Scene graph to image generation |  Visual Genome, COCO-Stuff and CLEVR-Dialog |  Yes,
TPT [113] |  Yes |  No |  No |  Yes |  No |  Video scene graph generation |  VidHOI and Action Genome |  No

###  IV-C Scalable Graph Transformers

Scalable graph transformers are a category of graph transformers that tackle
the challenges of scalability and efficiency when applying self-attention to
large-scale graphs [114, 39, 53, 115]. These transformers are specifically
designed to reduce computational cost and memory usage while maintaining or
improving performance. To achieve this, various techniques are employed to
reduce the complexity of self-attention, such as sparse attention, local
attention, and low-rank approximation [12, 115]. Scalable graph transformers
can be regarded as an enhancement of deep graph transformers addressing
challenges, such as over-smoothing and limited capacity of global attention.

Several scalable graph transformer models have been proposed to enhance the
scalability and efficiency of graph transformers. For instance, Rampášek et
al. [39] introduced GPS, use low-rank matrix approximations to reduce
computational complexity, and achieve state-of-the-art results on diverse
benchmarks. GPS decouples local real-edge aggregation from a fully-connected
transformer and incorporates different positional and structural encodings to
capture graph topology. It also offers a modular framework that supports
multiple encoding types and mechanisms for local and global attention. Cong et
al. [116] developed DyFormer, a dynamic graph transformer that utilizes
substructure tokens and local attention to enhance the focus and diversity of
global attention. DyFormer employs a temporal union graph structure and a
subgraph-based node sampling strategy for efficient and scalable training.

Scalable graph transformers are an innovative and efficient category of graph
transformers that excel in handling large-scale graphs while minimizing
computational cost and memory usage. However, scalable graph transformers face
certain limitations, including the trade-off between scalability and
expressiveness, the challenge of selecting optimal hyperparameters and
encodings, and the absence of theoretical analysis regarding their convergence
and stability. Consequently, further investigation is required to explore
optimal designs and evaluations of scalable graph transformers for various
applications. For a comprehensive overview of scalable graph transformer
methods, please refer to Table IV.

TABLE IV: Scalable graph transformers

Model |  Graph inductive bias |  Graph attention mechanisms |  Application |  Datasets |  Code availability
---|---|---|---|---|---
Node Positional encoding |  Edge Structural Encoding |  Message-Passing Bias |  Global attention |  Local Attention |  |
GPS [39] |  Yes (local and global) |  Yes (local and relative) |  Yes (interleaving) |  Yes (quadratic and linear) |  Yes (message passing) |  Graph representation learning |  ZINC, PCQM4Mv2, CIFAR10, MalNet-Tiny, OGB benchmarks |  Yes
NodeFormer [53] |  No |  No |  Yes (relational bias) |  Yes (linear) |  No |  Node classification |  Citation networks, OGB-Proteins, Amazon2M, Mini-ImageNet, 20News-Groups |  Yes
DIFFORMER [115] |  No |  No |  No |  Yes (linear) |  Yes (spectral) |  Node classification, image/text classification, spatial-temporal dynamics prediction |  Cora, Citeseer, Pubmed, ogbn-Proteins, Pokec, CIFAR, STL, 20News |  Yes
DyFormer [116] |  Yes (global) |  Yes (global) |  Yes (pre-processing) |  Yes (quadratic) |  No |  Dynamic graph representation learning |  RDS, UCI, Yelp, ML-10M, SNAP-Wikipedia, SNAP-Reddit |  No
Graph ViT/MLP-Mixer [117] |  Yes |  No |  No |  No |  Yes (message passing) |  Graph representation learning |  ZINC, MNIST, CIFAR10, MolTOX21, MolHIV, Peptide-func, Peptide-struct, CSL, EXP, SR25, LRGB, TreeNeighbourMatch |  Yes
DiGress [118] |  No |  Yes |  No |  Yes |  Yes |  Graph generation |  QM9, MOSES, GuacaMol, SBM, planar graphs |  Yes
EXPHORMER [119] |  Yes (local and global) |  Yes (local and global) |  Yes (interleaving) |  Yes (linear) |  Yes (spectral) |  Graph learning and representation tasks |  CIFAR10, MalNet-Tiny, MNIST, CLUSTER, PATTERN, PascalVOC-SP, COCO-SP, PCQM-Contact, ogbn-arxiv, |  Yes
EGT [120] |  Yes (global) |  Yes (global) |  No |  Yes (quadratic) |  No |  Node and edge classification, graph classification and regression, transfer learning. |  PATTERN, CLUSTER, TSP, MNIST, CIFAR10, ZINC, PCQM4M, PCQM4Mv2, MolPCBA and MolHIV. |  Yes
GRIT [121] |  Yes |  No |  No |  Yes (quadratic) |  No |  Graph regression and classification |  ZINC, MNIST, CIFAR10, PATTERN, CLUSTER, Peptides-func, Peptides-struct, ZINC-full, PCQM4Mv2 |  Yes
HSGT [122] |  No |  Yes (local, based on shortest path distance) |  No |  Yes (quadratic) |  Yes (message passing, based on neighborhood sampling) |  Node classification |  Cora, CiteSeer, PubMed, Amazon-Photo, ogbn-arxiv, ogbn-proteins, ogbn-products, Reddit, Flickr, Yelp |  No
Higher-Order Transformers [123] |  No |  No |  No |  Yes (quadratic and linear) |  Yes (message passing) |  Graph and hypergraph modeling |  Synthetic chains, PCQM4M-LSC, Jets, Delaunay, Hyperedge prediction |  Yes
EGAT [73] |  No |  No |  Yes (interleaving) |  Yes (linear) |  No |  Graph representation learning and molecular property prediction |  AMLSim, Cora, Citeseer, PubMed |  No
L-CAT [90] |  No |  No |  No |  Yes (linear) |  No |  Node classification |  CSBM, Amazon, Facebook, GitHub, TwitchEN, Coauthor Physics, OGB (arxiv, products, mag, proteins) |  Yes
Point Transformer [88] |  Yes (relative) |  No |  No |  No |  Yes (message passing) |  3D point cloud processing |  S3DIS, ModelNet40, ShapeNetPart |  Yes
Specformer [92] |  No |  No |  No |  Yes (linear) |  Yes (spectral) |  Graph representation learning |  Synthetic, node-level and graph-level datasets |  Yes
HierGAT [124] |  Yes (local) |  No |  No |  Yes (linear) |  No |  Entity Resolution |  Magellan and WDC product matching datasets |  Yes
Geo-ER [125] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Geospatial Entity Resolution |  OSM, FSQ, Yelp |  Yes
GTA [126] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Multivariate time series anomaly detection in IoT |  SWaT, WADI, SMAP, MSL |  Yes
GraTransDRP [127] |  Yes |  No |  No |  Yes (linear) |  No |  Drug response prediction |  GDSC |  Yes
LGT [128] |  Yes (local and global) |  No |  No |  Yes (linear) |  Yes (message passing) |  Molecular properties prediction |  ZINC, QM9, ESOL, FreeSolv |  No,
GTAGC [129] |  Yes (global) |  No |  No |  Yes (linear) |  Yes (spectral) |  Graph clustering |  Citeseer, Cora, Pubmed |  No
ANS-GT [130] |  Yes (local and global) |  No |  No |  Yes (linear) |  Yes (message passing) |  Node classification |  Cora, Citeseer, Pubmed, Chameleon, Actor, Squirrel, Cornell, Texas, Wisconsin |  No
RelTR [131] |  No |  No |  No |  Yes (linear) |  No |  Scene graph generation |  Visual Genome, Open Images V6, VRD |  Yes
BSTG-Trans [132] |  Yes (local and global) |  Yes (local and global) |  No |  Yes (linear) |  Yes (message Passing) |  Long-term Pose Forecasting |  Human3.6M, HumanEva-I, Human360K |  Yes
GraphSum [133] |  Yes (local and global) |  No |  No |  Yes (linear) |  Yes (message passing) |  Abstractive MDS |  WikiSum and MultiNews |  Yes
KG-Transformer [134] |  No |  No |  Yes (pre-processing) |  Yes (linear) |  No |  Text generation from knowledge graphs |  UMLS, PubMed, 2010 i2b2/VA, JNLPBA, BC5CDR, GAD, EU-ADR |  No

###  IV-D Pre-trained Graph Transformers

Pre-trained graph transformers utilize large-scale unlabeled graphs to acquire
transferable node embeddings [135]. These embeddings can be fine-tuned for
downstream tasks with scarce labeled data that address the challenges of data
scarcity and domain adaptation in graph learning tasks [136, 137]. These
transformers are similar to pre-trained large language models (LLMs) and are
trained on graph datasets using self-supervised learning objectives, such as
masked node prediction [138], edge reconstruction [139], and graph contrastive
learning [140]. These objectives aim to encapsulate the inherent properties of
graph data independently of external labels or supervision [141]. The pre-
trained model can be fine-tuned on a specific downstream task with a smaller
or domain-specific graph dataset by incorporating a task-specific layer or
loss function and optimizing it on labeled data [142]. This allows the pre-
trained model to transfer the knowledge acquired from the large-scale graph
dataset to the subsequent task, giving better performance compared to the
training from scratch [142].

Pre-trained graph transformers face some challenges, such as the selection of
appropriate pre-training tasks, domain knowledge incorporation, heterogeneous
information integration, and pre-training quality evaluation [143]. To address
these issues, KPGT [144] and KGTransformer [145] have been proposed. KPGT
leverages additional domain knowledge for pre-training, while KGTransformer
serves as a uniform Knowledge Representation and Fusion (KRF) module in
diverse tasks. Despite their power and flexibility, pre-trained graph
transformers encounter issues related to graph data heterogeneity and
sparsity, domain adaptation, model generalization and performance
interpretation. A summary of pre-trained graph transformer methods is provided
in Table V.

TABLE V: Pre-trained graph transformers

Model |  Graph inductive bias |  Graph attention mechanisms |  Application |  Datasets |  Code availability
---|---|---|---|---|---
Node Positional encoding |  Edge Structural Encoding |  Message-Passing Bias |  Global attention |  Local Attention |  |
GRAPHIX-T5 [136] |  No |  Yes |  Yes (pre-processing) |  Yes (linear) |  No |  Text-to-SQL |  SPIDER, SYN, DK, REALISTIC, SPIDER-SSP |  Yes
GROVER [137] |  No |  No |  Yes (interleaving) |  Yes (linear) |  Yes (message passing) |  Molecular representation learning |  MoleculeNet |  No
G-BERT [135] |  No |  No |  No |  Yes (linear) |  No |  Medication recommendation |  MIMIC-III |  Yes
ChemBERTa [138] |  No |  No |  No |  Yes (quadratic) |  No |  Molecular property prediction |  PubChem 77M, MoleculeNet |  Yes
HEAT [139] |  Yes (local) |  No |  No |  Yes (linear) |  Yes (message passing) |  Structured reconstruction |  SpaceNet Challenge and Structured3D |  Yes
FormNetV2 [140] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Form document information extraction |  FUNSD, CORD, SROIE |  No
MPG [143] |  No |  No |  No |  Yes (linear) |  Yes (spectral) |  Drug discovery |  MoleculeNet, DDI, DTI |  Yes
LiGhT [144] |  No |  Yes (path encoding and distance encoding) |  No |  Yes (linear) |  No |  Molecular property prediction |  ChEMBL29, BACE, BBBP, ClinTox, SIDER, Estrogen, MetStab, Tox21, ToxCast, FreeSolv, Lipophilicity |  Yes
LightGT [146] |  Yes (global) |  No |  No |  Yes (linear) |  No |  Multimedia recommendation |  Movielens, Tiktok, Kwai |  Yes
KGTransformer [145] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Knowledge graph transfer |  WFC, WN18RR, AwA-KG, CommonsenQA |  Yes
CoVGT [147] |  No |  No |  No |  Yes (linear) |  Yes (message-passing) |  Video Question Answering |  NExT-QA, TGIF-QA, TGIF-QA-R, STAR-QA, Causal-VidQA, MSRVTT-QA |  Yes
G-Adapter [148] |  No |  Yes (local) |  No |  Yes (quadratic) |  No |  Molecular graph tasks |  MolHIV, MolPCBA, FreeSolv, ESOL, BBBP, Estrogen-$\alpha$, Estrogen-$\beta$, MetStablow, MetStabhigh |  Yes
kgTransformer [149] |  No |  No |  Yes (interleaving) |  Yes (quadratic) |  No |  Knowledge graph reasoning for complex logical queries |  FB15k-237, NELL995 |  Yes
Li et al. [149] |  Yes (local and global) |  No |  No |  Yes (linear) |  Yes (message passing) |  Movement synchrony estimation in autism therapy interventions |  PT13 and Human3.6MS |  No
Pellegrini et al. [150] |  No |  Yes |  No |  Yes (linear) |  No |  Disease prediction using graph convolutional networks |  TADPOLE and MIMIC-III |  Yes
Video Graph Transformer (VGT) [151] |  No |  No |  No |  Yes (linear) |  Yes (message passing) |  Video Question Answering (VideoQA) |  NExT-QA, TGIF-QA, MSRVTT-QA |  Yes
Tan et al. [152] |  No |  No |  No |  Yes (linear) |  No |  Few-shot node classification |  CoraFull, ogbn-arxiv, CiteSeer, Cora |  No
GPT-GNN [60] |  No |  Yes |  Yes |  No |  Yes |  Graph representation learning and graph mining |  OAG, Amazon, Reddit, OAG (citation) |  Yes

###  IV-E Design Guide for Effective Graph Transformers

Developing effective graph transformers requires meticulous attention to
detail and careful consideration. This guide provides general principles and
tips for designing graph transformers for various scenarios and tasks.

  * •

Choose the appropriate type of graph transformers based on the nature and
complexity of your graph data and tasks. For simple and small graph data, a
shallow graph transformer with a few layers may suffice. For complex and large
graph data, a deep graph transformer with many layers can learn more
expressive representations. For dynamic or streaming graph data, a scalable
graph transformer is more efficient. Pre-trained graph transformers are more
suitable for sparse or noisy graph data.

  * •

Design suitable structural and positional encodings for your graph data. These
encodings capture the structure of graphs and are added to input node or edge
features before feeding them to transformer layers. The choice of encodings
depends on the characteristics of the graph data, such as directionality,
weight, and homogeneity. The careful design of these encodings ensures their
informativeness.

  * •

Optimize the self-attention mechanism for your graph data. Self-attention
mechanisms compute attention scores among all pairs of nodes or edges in the
graph, capturing long-range dependencies and interactions. However, it
introduces challenges like computational complexity, memory consumption,
overfitting, over-smoothing, and over-squashing. Techniques like sampling,
sparsification, partitioning, hashing, masking, regularization, and
normalization can be employed to address these challenges and improve the
quality and efficiency of the self-attention mechanism.

  * •

Utilize pre-training techniques to enhance the performance of graph
transformers. Pre-training techniques leverage pre-trained models or data from
other domains or tasks transferring knowledge or parameters to a specific
graph learning task. Methods like fine-tuning, distillation, and adaptation
can be used to adapt pre-trained models or data. Utilizing pre-training
techniques is particularly beneficial when a large amount of pre-training data
or resources are available.

##  V Application Perspectives of Graph Transformers

Graph transformers are finding applications in various domains that involve
interconnected data. This section delves into their applications for graph-
related tasks, categorized by the level of analysis: node-level, edge-level
and graph-level. Beyond these core tasks, graph transformers are also making
strides in applications that handle text, images, and videos, where data can
be effectively represented as graphs for analysis.

###  V-A Node-level Tasks

Node-level tasks involve the acquisition of node representations or the
prediction of node attributes using the graph structure and node features
[153].

####  V-A1 Protein Structure Prediction

In the field of bioinformatics, graph transformers have demonstrated
substantial potential in Protein Structure Prediction (PSP) [154]. Gu et al.
[155] introduced HEAL, which employs hierarchical graph transformers on super-
nodes that imitate functional motifs to interact with nodes in the protein
graph, effectively capturing structural semantics. Pepe et al. [156] used
Geometric Algebra (GA) modelling to introduce a new metric based on the
relative orientations of amino acid residues, serving as an additional input
feature to a graph transformer, assisting in the prediction of the 3D
coordinates of a protein. Chen et al. [157] proposed gated-graph transformers
integrating node and edge gates within a graph transformer framework to
regulate information flow during graph message passing, proving beneficial in
predicting the quality of 3D protein complex structures. Despite the
encouraging outcomes, various challenges persist, such as the complexity of
protein structures, scarcity of high-quality training data, and substantial
computational resource [158]. Further investigation is necessary to address
these challenges and enhance the precision of these models.

####  V-A2 Entity Resolution

Entity Resolution (ER) is a crucial task in data management that aims to
identify and link disparate representations of real-world entities from
diverse sources [159]. Recent research has highlighted the efficacy of graph
transformers in ER. For example, Yao et al. [160] proposed Hierarchical Graph
Attention Networks (HierGAT) integrating the self-attention mechanism and
graph attention network mechanism to capture and leverage the relationships
between different ER decisions, leading to substantial enhancements over
conventional approaches. Ying et al. [161] extended the standard transformer
architecture and introduced several straightforward yet powerful structural
encoding techniques to enhance the modeling of graph-structured data. Despite
facing challenges related to data complexity and structural information
encoding, these techniques have exhibited promising outcomes in terms of
enhanced performance, scalability, and accuracy. Furthermore, Dou et al.[162]
proposed the Hybrid Matching Knowledge for Entity Matching (GTA) method
improves the transformer for representing relational data by integrating
additional hybrid matching knowledge acquired through graph contrastive
learning on a specially designed hybrid matching graph. This approach has also
demonstrated promising results by effectively boosting the transformer for
representing relational data and surpassing existing entity matching
frameworks.

####  V-A3 Anomaly Detection

Graph transformers are valuable tools for anomaly detection, especially in
dynamic graphs and time series data [65, 163]. They tackle key challenges like
encoding information for unattributed nodes and extracting discriminative
knowledge from spatial-temporal dynamic graphs. Liu et al [164] proposed
TADDY, a transformer-based Anomaly Detection framework, enhancing node
encoding to represent each node’s structural and temporal roles in evolving
graph streams. Similarly, Xu et al. [165] proposed the Anomaly Transformer
which uses an Anomaly-Attention mechanism to measure association discrepancy
and employs a minimax strategy to enhance normal-abnormal differentiation.
Chen et al. [166] proposed the GTA framework for multivariate time series
anomaly detection incorporates graph structure learning, graph convolution,
and temporal dependency modeling with a transformer-based architecture. Tuli
et al. [167] developed TranAD, a deep transformer network for anomaly
detection in multivariate time series data, showing efficient anomaly
detection and diagnosis in modern industrial applications. Despite their
effectiveness, further research is needed to enhance their performance and
applicability across different domains.

###  V-B Edge-level Tasks

Edge-level tasks aim to learn edge representations or predict edge attributes
based on graph structure and node features [168, 169].

####  V-B1 Drug-Drug Interaction Prediction

Graph transformers have been increasingly employed in the prediction of Drug-
Drug Interactions (DDIs) owing to their capability to adeptly model the
intricate relationships between drugs and targets [170]. Wang et al. [109]
proposed a method which uses a line graph with drug-protein pairs as vertices
and a graph transformer network (DTI-GTN) for the purpose of forecasting drug-
target interactions. Djeddi et al. [171] proposed a novel approach named DTIOG
for the prediction of DTIs, leveraging a Knowledge Graph Embedding (KGE)
strategy and integrating contextual information derived from protein
sequences. Despite the encouraging outcomes, these approaches encounter
challenges such as overlooking certain facets of the intermolecular
information and identifying potential interactions for newly discovered drugs
[172]. Nevertheless, findings from multiple studies indicate that graph
transformers can proficiently anticipate DDIs and surpass the performance of
existing algorithms [173].

####  V-B2 Knowledge Graph Completion

In the domain of Knowledge Graph (KG) completion, the utilization of graph
transformers has been extensively investigated [174]. Chen et al. [175]
proposed a novel inductive KG representation model, known as iHT, for KG
completion through large-scale pre-training. This model comprises an entity
encoder and a neighbor-aware relational scoring function, both parameterized
by transformers. The application of this approach has led to remarkable
advancements in performance, with a relative enhancement of more than 25% in
mean reciprocal rank compared to previous models. Liu et al. [176] introduced
a generative transformer with knowledge-guided decoding for academic KG
completion, which incorporates pertinent knowledge from the training corpus to
provide guidance. Chen et al. [177] developed a hybrid transformer with multi-
level fusion to tackle challenges in multimodal KG completion tasks. This
model integrates visual and textual representations through coarse-grained
prefix-guided interaction and fine-grained correlation-aware fusion modules.

####  V-B3 Recommender Systems

Graph transformers have been effectively utilized in recommender systems by
combining generative self-supervised learning with a graph transformer
architecture [178]. Xia et al. [179] used the generative self-supervised
learning method to extract representations from the data in an unsupervised
manner and utilized graph transformer architecture to capture intricate
relationships between users and items in the recommendation system. Li et al.
[180] introduced a new method for recommender systems that leverages graph
transformers (GFormer). Their approach automates the self-supervision
augmentation process through a technique called rationale-aware generative
self-supervised learning. This technique identifies informative patterns in
user-item interactions. The proposed recommender system utilizes a special
type of collaborative rationale discovery to selectively augment the self-
supervision while preserving the overall relationships between users and
items. The rationale-aware self-supervised learning in the graph transformer
enables graph collaborative filtering. While challenges remain in areas like
graph construction, network design, model optimization, computation
efficiency, and handling diverse user behaviors, experiments show that the
approach consistently outperforms baseline models on various datasets.

###  V-C Graph-level Tasks

Graph-level tasks aim to learn graph representations or predict graph
attributes based on graph structure and node features.

####  V-C1 Molecular Property Prediction

Graph transformers are powerful tools for molecular property prediction,
utilizing the graph structure of molecules to capture essential structural and
semantic information [181]. Chen et al. [182] proposed Algebraic Graph-
Assisted Bidirectional Transformer (AGBT) framework which integrates
complementary 3D molecular information into graph invariants, rectifying the
oversight of three-dimensional stereochemical information in certain machine
learning models. Li et al [144] utilized Knowledge-Guided Pre-training of
Graph Transformer (KPGT) in a self-supervised learning framework which
emphasizes the importance of chemical bonds and models the structural
information of molecular graphs. Buterez et al. [183] proposed transfer
learning with graph transformer to enhance molecular property prediction on
sparse and costly high-fidelity data.

####  V-C2 Graph Clustering

Graph transformers have been increasingly utilized in the field of Graph
Clustering, offering innovative methodologies and overcoming significant
challenges [184]. Yun et al. [185] proposed a graph transformer network to
generate new graph structures for identifying useful connections between
unconnected nodes on the original graph while learning effective node
representation on the new graphs in an end-to-end fashion. Gao et al. [186]
proposed a patch graph transformer (PatchGT) that segments a graph into
patches based on spectral clustering without any trainable parameters and
allows the model to first use GNN layers to learn patch-level representations
and then use transformer to obtain graph-level representations. These
methodologies have addressed issues such as the limitations of the local
attention mechanism and difficulties in learning high-level information,
leading to enhanced graph representation, improved model performance, and
effective node representation.

####  V-C3 Graph Synthesis

Graph transformers have been applied in the field of graph synthesis to
improve graph data mining and representation learning. Existing graph
transformers with Positional Encodings have limitations in node classification
tasks on complex graphs, as they do not fully capture the local node
properties [16]. To address this, Ma et al. [187] introduced the Adaptive
Graph Transformer (AGT). This model tackles the challenge of extracting
structural patterns from graphs in a way that is both effective and efficient.
AGT achieves this by learning from two different graph perspectives:
centrality and subgraph views. This approach has been shown to achieve state-
of-the-art performance on real-world web graphs and synthetic graphs
characterized by heterophily and noise. Jiang et al. [188] proposed an Anchor
Graph Transformer (AGFormer) that leverages an anchor graph model to perform
more efficient and robust node-to-node message passing for overcoming the
computational cost and sensitivity to graph noises of regular graph
transformers. Zhu et al. [122] developed a Hierarchical Scalable Graph
Transformer (HSGT) which scales the transformer architecture to node
representation learning tasks on large-scale graphs by utilizing graph
hierarchies and sampling-based training methods.

###  V-D Other Application Scenarios

Graph transformers have a wide range of applications beyond graph-structured
data. They can also be utilized in scenarios involving text, images, or
videos. [189].

####  V-D1 Text Summarization

Text summarization is a crucial aspect of NLP which has been significantly
advanced with the introduction of Graph transformers [190]. These models
utilize extractive, abstractive, and hybrid methods for summarization.
Extractive summarization selects and extracts key sentences or phrases from
the original text to create a summary [191]. In contrast, abstractive
summarization interprets the core concepts in the text and produces a concise
summary. Hybrid summarization combines the advantages of both approaches
[192]. Despite the progress, challenges remain in text comprehension, main
idea identification, and coherent summary generation. Nevertheless, the
application of graph transformers in text summarization has demonstrated
promising outcomes in terms of summary quality and efficiency [193].

####  V-D2 Image Captioning

Graph transformers have emerged as a potent tool within the domain of image
captioning, offering a structured representation of images and efficiently
processing them to produce descriptive captions [194]. Techniques such as
Transforming Scene Graphs (TSG) leverage multi-head attention to architect
graph neural networks for embedding scene graphs, which encapsulate a myriad
of specific knowledge to facilitate the generation of words across various
parts of speech [195]. Despite encountering challenges, such as training
complexity, absence of contextual information, and lack of fine-grained
details in the extracted features, graph transformers have exhibited promising
outcomes. They have enhanced the quality of generated sentences and attained
state-of-the-art performance in image captioning endeavors [196].

####  V-D3 Image Generation

Graph transformers have been effectively utilized in image generation, as
demonstrated by various research studies [197]. Sortino et al. [33] proposed a
transformer-based method conditioned by scene graphs for image generation,
employing a decoder to sequentially compose images. Zhang et al. [198]
proposed StyleSwin which uses transformers in constructing a generative
adversarial network for high-resolution image creation. Despite challenges
like redundant interactions and the requirement for intricate architectures,
these studies have exhibited promising outcomes in terms of image quality and
variety [199, 200].

####  V-D4 Video Generation

Graph transformers have been extensively applied in the field of Video
Generation. Xiao et al. [201] proposed a Video Graph Transformer (VGT) model,
which utilizes a dynamic graph transformer module to encode videos, capturing
visual objects, their relationships, and dynamics. It incorporates
disentangled video and text transformers for comparing relevance between the
video and text. Wu et al. [202] proposed The Object-Centric Video Transformer
(OCVT) which adopts an object-centric strategy to break down scenes into
tokens suitable for a generative video transformer and understanding the
intricate spatiotemporal dynamics of multiple interacting objects within a
scene. Yan et al. [203] developed VideoGPT, which learns downsampled discrete
latent representations of a raw video through 3D convolutions and axial self-
attention. A GPT-like architecture is then used to model the discrete latent
in a spatiotemporal manner using position encodings. Tulyakov et al. [204]
proposed the MoCoGAN model which creates a video by mapping a series of random
vectors to a sequence of video frames. Despite the challenges in capturing
complex spatio-temporal dynamics in videos, these methodologies have exhibited
promising outcomes across various facets of video generation, ranging from
question answering to video summarization and beyond.

##  VI Open Issues and Future Directions

Despite their immense potential for learning from graph-structured data, graph
transformers still face open issues and challenges that require further
exploration. Here we highlight some of these open challenges.

###  VI-A Scalability and Efficiency

The scalability and efficiency of graph transformers pose considerable
challenges due to their substantial memory and computational requirements
especially when employing global attention mechanisms to deal with large-scale
graphs [205, 114]. These challenges are further amplified in deep
architectures which are susceptible to overfitting and over-smoothing. To
address these issues, several potential strategies can be proposed:

  1. 1.

Developing efficient attention mechanisms, such as linear, sparse and low-rank
attention, to reduce the complexity and memory usage of graph transformers.

  2. 2.

Applying graph sparsification or coarsening techniques to decrease the size
and density of graphs while maintaining their crucial structural and semantic
information.

  3. 3.

Using graph partitioning or sampling methods to divide large graphs into
smaller subgraphs or batches for parallel or sequential processing.

  4. 4.

Exploring graph distillation or compression methods to create compact and
effective graph transformer models, which are suitable for deployment on
resource-limited devices.

  5. 5.

Investigating regularization or normalization techniques, such as dropout,
graph diffusion, convolution, and graph spectral normalization, to prevent
overfitting and over-smoothing in graph transformer models.

###  VI-B Generalization and Robustness

Graph transformers often face challenges when it comes to generalizing to
graphs that they have not encountered before or that fall outside of their
usual distribution. This is especially true for graphs that have different
sizes, structures, features, and domains. Additionally, graph transformers can
be vulnerable to adversarial attacks and noisy inputs, which can result in a
decline in performance and the production of misleading results. In order to
improve the generalization and robustness of graph transformers, the following
strategies could be taken into account:

  1. 1.

Developing adaptive and flexible attention mechanisms, such as dynamic
attention, span-adaptive attention, and multi-head attention with different
scales, to accommodate varying graphs and tasks.

  2. 2.

Applying domain adaptation or transfer learning techniques to facilitate
learning from multiple source domains and transfer the knowledge from source
domains to target domains.

  3. 3.

Exploring meta-learning or few-shot learning techniques to enable learning
from limited data and rapid adaptation to new tasks.

  4. 4.

Designing robust and secure attention mechanisms, such as adversarial
attention regularization, attention masking, and attention perturbation, to
resist adversarial attacks and noisy inputs.

  5. 5.

Evaluating the uncertainty and reliability of graph transformer models using
probabilistic or Bayesian methods, such as variational inference, Monte Carlo
dropout, and deep ensembles.

###  VI-C Interpretability and Explainability

Graph transformers commonly regarded as black box models present significant
challenges in terms of interpretability and explainability. The lack of
sufficient justification and evidence for their decisions can undermine their
credibility and transparency. To address this issue, several approaches can be
considered:

  1. 1.

Developing transparent and interpretable attention mechanisms, such as
attention visualization, attention attribution, and attention pruning, to
highlight the importance and relevance of different nodes and edges in graphs.

  2. 2.

Applying explainable artificial intelligence (XAI) techniques, such as
saliency maps, influence functions, and counterfactual explanations, to
analyze and understand the behaviour and logic of graph transformer models.

  3. 3.

Exploring natural language generation techniques, such as template-based
generation, neural text generation, and question-answering generation, to
produce natural language explanations for outputs or actions of graph
transformer models.

  4. 4.

Investigating human-in-the-loop methods, such as active learning, interactive
learning, and user studies, to incorporate human guidance in the learning or
evaluation process of graph transformer models [31].

###  VI-D Learning on Dynamic Graphs

Graphs, which are frequently characterized by their dynamic and intricate
nature, possess the ability to transform over time as a result of the addition
or removal of nodes and edges, as well as the modification of node and edge
attributes [206]. Moreover, these graphs may exhibit diverse types and
modalities of nodes and edges. In order to empower graph transformers to
effectively manage such dynamic graphs, it is advisable to explore the
following strategies:

  1. 1.

Developing temporal and causal attention mechanisms, such as recurrent,
temporal, and causal attention, to capture the temporal and causal evolution
of graphs.

  2. 2.

Applying continual learning techniques on dynamic graphs to void forgetting
previous knowledge and retraining.

  3. 3.

Exploring multimodal attention mechanisms, such as image-text, audio-visual,
and heterogeneous attention, to integrate multimodal nodes and edges.

  4. 4.

Leveraging multi-level and multi-layer attention mechanisms, such as node-
edge, graph-graph, and hypergraph attention, to aggregate information from
different levels and layers of graphs.

###  VI-E Data Quality and Diversity

Graph transformers require a significant quantity of diverse and high-quality
data to achieve effective learning. Nevertheless, in the real world, data is
frequently limited, noisy, incomplete, imbalanced, and biased. This has a
detrimental effect on the performance and fairness of graph transformer
models. To mitigate these challenges related to data quality and diversity,
several potential strategies can be considered:

  1. 1.

Developing noise-tolerant attention mechanisms, such as denoising attention,
error correction attention, and self-supervised attention, to filter out data
noise and errors.

  2. 2.

Applying data augmentation or generation techniques, such as graph
augmentation [207], graph completion, and graph generation, to enhance the
quantity and variety of data.

  3. 3.

Exploring data imbalance and bias mitigation techniques, such as data re-
sampling, data re-weighting, and data debiasing, to improve data fairness and
equity.

  4. 4.

Evaluating data quality and diversity using data quality assessment or data
diversity analysis methods, such as data quality metrics, data diversity
measures, and data quality visualization.

##  VII Conclusion

Graph transformers are a novel and powerful class of neural network models,
which can effectively encode and process graph-structured data. This survey
provides a comprehensive overview of graph transformers in terms of design
perspectives, taxonomy, applications, and open issues. We first discuss how
graph transformers incorporate graph inductive bias, including node positional
encodings, edge structural encodings, message-passing bias and attention bias,
to encode the structural information of graphs. Then, we introduce the design
of graph attention mechanisms, including global and local attention
mechanisms. Afterwards, a taxonomy of graph transformers is presented. This
survey also includes a design guide for effective graph transformers,
including the best practices and recommendations for selecting appropriate
components and hyperparameters. Moreover, the application scenarios of graph
transformers are reviewed based on various graph-related tasks (e.g., node-
level, edge-level, and graph-level tasks), as well as tasks in other domains.
Lastly, current challenges and future directions of graph transformers are
identified. This survey aims to serve as a valuable reference for researchers
and practitioners interested in graph transformers and their applications.

## Acknowledgment

The authors would like to thank Estrid He (RMIT University) for her helpful
comments.

## References

  * [1] P. Veličković, “Everything is connected: Graph neural networks,” _Current Opinion in Structural Biology_ , vol. 79, p. 102538, 2023.
  * [2] S. Wu, F. Sun, W. Zhang, X. Xie, and B. Cui, “Graph Neural Networks in Recommender Systems: A Survey,” _ACM Computing Surveys_ , vol. 55, no. 5, pp. 1–37, May 2023.
  * [3] A. A. Yusuf, C. Feng, X. Mao, R. Ally Duma, M. S. Abood, and A. H. A. Chukkol, “Graph neural networks for visual question answering: A systematic review,” _Multimedia Tools and Applications_ , Nov. 2023.
  * [4] X. Ma, J. Wu, S. Xue, J. Yang, C. Zhou, Q. Z. Sheng, H. Xiong, and L. Akoglu, “A comprehensive survey on graph anomaly detection with deep learning,” _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * [5] N. Das, B. Sadhukhan, R. Chatterjee, and S. Chakrabarti, “Integrating sentiment analysis with graph neural networks for enhanced stock prediction: A comprehensive survey,” _Decision Analytics Journal_ , p. 100417, 2024\.
  * [6] Y. Lin, T. Ruan, J. Liu, and H. Wang, “A survey on neural data-to-text generation,” _IEEE Transactions on Knowledge and Data Engineering_ , 2023\.
  * [7] K. S. Yow, N. Liao, S. Luo, and R. Cheng, “Machine Learning for Subgraph Extraction: Methods, Applications and Challenges,” _Proceedings of the VLDB Endowment_ , vol. 16, no. 12, pp. 3864–3867, Aug. 2023.
  * [8] F. Liu, S. Xue, J. Wu, C. Zhou, W. Hu, C. Paris, S. Nepal, J. Yang, and P. S. Yu, “Deep learning for community detection: Progress, challenges and opportunities,” in _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , C. Bessiere, Ed. ijcai.org, 2020, pp. 4981–4987.
  * [9] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [10] Z. Ye, Y. J. Kumar, G. O. Sing, F. Song, and J. Wang, “A comprehensive survey of graph neural networks for knowledge graphs,” _IEEE Access_ , vol. 10, pp. 75 729–75 741, 2022.
  * [11] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Liu, “Do transformers really perform badly for graph representation?” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 877–28 888, 2021\.
  * [12] L. Müller, M. Galkin, C. Morris, and L. Rampášek, “Attending to graph transformers,” _Transactions on Machine Learning Research_ , 2024.
  * [13] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [14] T. Lin, Y. Wang, X. Liu, and X. Qiu, “A survey of transformers,” _AI Open_ , 2022.
  * [15] J. Kim, D. Nguyen, S. Min, S. Cho, M. Lee, H. Lee, and S. Hong, “Pure transformers are powerful graph learners,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 14 582–14 595, 2022.
  * [16] V. P. Dwivedi and X. Bresson, “A generalization of transformer networks to graphs,” _AAAI Workshop on Deep Learning on Graphs: Methods and Applications_ , 2021.
  * [17] F. Xia, K. Sun, S. Yu, A. Aziz, L. Wan, S. Pan, and H. Liu, “Graph learning: A survey,” _IEEE Transactions on Artificial Intelligence_ , vol. 2, no. 2, pp. 109–127, 2021.
  * [18] C. Chen, Y. Wu, Q. Dai, H.-Y. Zhou, M. Xu, S. Yang, X. Han, and Y. Yu, “A survey on graph neural networks and graph transformers in computer vision: A task-oriented perspective,” _arXiv preprint arXiv:2209.13232_ , 2022.
  * [19] E. Min, R. Chen, Y. Bian, T. Xu, K. Zhao, W. Huang, P. Zhao, J. Huang, S. Ananiadou, and Y. Rong, “Transformer for graphs: An overview from architecture perspective,” _arXiv preprint arXiv:2202.08455_ , 2022.
  * [20] F. Chen, Y.-C. Wang, B. Wang, and C.-C. J. Kuo, “Graph representation learning: A survey,” _APSIPA Transactions on Signal and Information Processing_ , vol. 9, p. e15, 2020.
  * [21] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * [22] X. Wang and M. Zhang, “How powerful are spectral graph neural networks,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 23 341–23 362.
  * [23] D. Bo, X. Wang, Y. Liu, Y. Fang, Y. Li, and C. Shi, “A Survey on Spectral Graph Neural Networks,” _arXiv preprint arXiv:2302.05631_ , 2023\.
  * [24] Z. Zhang, P. Cui, and W. Zhu, “Deep learning on graphs: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 34, no. 1, pp. 249–270, 2020.
  * [25] D. Bacciu, F. Errica, A. Micheli, and M. Podda, “A gentle introduction to deep learning for graphs,” _Neural Networks_ , vol. 129, pp. 203–221, 2020.
  * [26] P. Shaw, J. Uszkoreit, and A. Vaswani, “Self-attention with relative position representations,” in _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), New Orleans, Louisiana, USA, June 1-6_ , 2018, pp. 464–468.
  * [27] W. Nam and B. Jang, “A survey on multimodal bidirectional machine learning translation of image and natural language processing,” _Expert Systems with Applications_ , p. 121168, 2023.
  * [28] A. Elangovan, J. He, and K. Verspoor, “Memorization vs. generalization: quantifying data leakage in nlp performance evaluation,” in _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics (ECL)_ , 2021, pp. 1325–1335.
  * [29] J. He, Y. Li, Z. Zhai, B. Fang, C. Thorne, C. Druckenbrodt, S. Akhondi, and K. Verspoor, “Focused contrastive loss for classification with pre-trained language models,” _IEEE Transactions on Knowledge and Data Engineering (TKDE)_ , 2023.
  * [30] J. He, B. Fang, H. Yoshikawa, Y. Li, S. A. Akhondi, C. Druckenbrodt, C. Thorne, Z. Afzal, Z. Zhai, L. Cavedon _et al._ , “Chemu 2021: reaction reference resolution and anaphora resolution in chemical patents,” in _Advances in Information Retrieval: Proceedings of the 43rd European Conference on IR Research (ECIR)_. Springer International Publishing, 2021, pp. 608–615.
  * [31] A. Elangovan, E. He, Y. Li, and K. Verspoor, “Effects of human adversarial and affable samples on bert generalization,” in _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 2023\.
  * [32] N. Parmar, A. Vaswani, J. Uszkoreit, L. Kaiser, N. Shazeer, A. Ku, and D. Tran, “Image transformer,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 4055–4064.
  * [33] R. Sortino, S. Palazzo, and C. Spampinato, “Transforming Image Generation from Scene Graphs,” in _2022 26th International Conference on Pattern Recognition (ICPR)_. IEEE, 2022, pp. 4118–4124.
  * [34] J. He, J. Qi, and K. Ramamohanarao, “Timesan: A time-modulated self-attentive network for next point-of-interest recommendation,” in _Proceedings of the 2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2020, pp. 1–8.
  * [35] S. Deldari, H. Xue, A. Saeed, J. He, D. V. Smith, and F. D. Salim, “Beyond just vision: A review on self-supervised representation learning on multimodal and temporal data,” _arXiv preprint arXiv:2206.02353_ , 2022.
  * [36] S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim, “Graph transformer networks,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [37] F. Xia, S. Yu, C. Liu, J. Li, and I. Lee, “Chief: Clustering with higher-order motifs in big networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 9, no. 3, pp. 990–1005, 2021.
  * [38] V. Shiv and C. Quirk, “Novel positional encodings to enable tree-based transformers,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [39] L. Rampášek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini, “Recipe for a general, powerful, scalable graph transformer,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 14 501–14 515, 2022.
  * [40] P. Chen, H. Tsai, S. Bhojanapalli, H. W. Chung, Y. Chang, and C. Ferng, “A simple and effective positional encoding for transformers,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP), Virtual Event / Punta Cana, Dominican Republic, 7-11 November_ , 2021, pp. 2974–2988.
  * [41] W. Park, W.-G. Chang, D. Lee, J. Kim, and seung-won hwang, “GRPE: Relative positional encoding for graph transformer,” in _ICLR2022 Machine Learning for Drug Discovery_ , 2022.
  * [42] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” in _International Conference on Learning Representations_ , 2018.
  * [43] L. Ma, R. Rabbany, and A. Romero-Soriano, “Graph attention networks with positional embeddings,” in _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 2021, pp. 514–527.
  * [44] J. Liu, F. Xia, L. Wang, B. Xu, X. Kong, H. Tong, and I. King, “Shifu2: A network representation learning based model for advisor-advisee relationship mining,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 33, no. 4, pp. 1763–1777, 2019.
  * [45] J. Park, S. Yun, H. Park, J. Kang, J. Jeong, K.-M. Kim, J.-w. Ha, and H. J. Kim, “Deformable Graph Transformer,” _arXiv preprint arXiv:2206.14337_ , 2022.
  * [46] G. Mialon, D. Chen, M. Selosse, and J. Mairal, “Graphit: Encoding graph structure in transformers,” _arXiv preprint arXiv:2106.05667_ , 2021.
  * [47] A. Haviv, O. Ram, O. Press, P. Izsak, and O. Levy, “Transformer language models without positional encodings still learn positional information,” in _Findings of the Association for Computational Linguistics: EMNLP 2022_ , 2022, pp. 1382–1390.
  * [48] H. Peng, G. Li, Y. Zhao, and Z. Jin, “Rethinking Positional Encoding in Tree Transformer for Code Representation,” in _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , 2022, pp. 3204–3214.
  * [49] S. Geisler, Y. Li, D. J. Mankowitz, A. T. Cemgil, S. Günnemann, and C. Paduraru, “Transformers meet directed graphs,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 11 144–11 172.
  * [50] F. Xia, J. Liu, H. Nie, Y. Fu, L. Wan, and X. Kong, “Random walks: A review of algorithms and applications,” _IEEE Transactions on Emerging Topics in Computational Intelligence_ , vol. 4, no. 2, pp. 95–107, 2019.
  * [51] Á. Huertas-García, A. Martín, J. Huertas-Tato, and D. Camacho, “Exploring Dimensionality Reduction Techniques in Multilingual Transformers,” _Cognitive Computation_ , vol. 15, no. 2, pp. 590–612, 2023\.
  * [52] D. Chen, L. O’Bray, and K. Borgwardt, “Structure-aware transformer for graph representation learning,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 3469–3489.
  * [53] Q. Wu, W. Zhao, Z. Li, D. P. Wipf, and J. Yan, “Nodeformer: A scalable graph structure learning transformer for node classification,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 27 387–27 401, 2022.
  * [54] M. Pu, Y. Huang, Y. Liu, Q. Guan, and H. Ling, “Edter: Edge detection with transformer,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 1402–1412.
  * [55] N. Dhingra, F. Ritter, and A. Kunz, “Bgt-net: Bidirectional gru transformer network for scene graph generation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 2150–2159.
  * [56] K. Han, A. Xiao, E. Wu, J. Guo, C. Xu, and Y. Wang, “Transformer in transformer,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 15 908–15 919, 2021.
  * [57] T. Tambe, C. Hooper, L. Pentecost, T. Jia, E.-Y. Yang, M. Donato, V. Sanh, P. Whatmough, A. M. Rush, and D. Brooks, “Edgebert: Sentence-level energy optimizations for latency-aware multi-task nlp inference,” in _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2021, pp. 830–844.
  * [58] M. S. Hussain, M. J. Zaki, and D. Subramanian, “Global self-attention as a replacement for graph convolution,” in _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2022, pp. 655–665.
  * [59] P. Zhang, X. Dai, J. Yang, B. Xiao, L. Yuan, L. Zhang, and J. Gao, “Multi-scale vision longformer: A new vision transformer for high-resolution image encoding,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 2998–3008.
  * [60] Z. Hu, Y. Dong, K. Wang, K.-W. Chang, and Y. Sun, “Gpt-gnn: Generative pre-training of graph neural networks,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 1857–1867.
  * [61] J. Yin, J. Shen, C. Guan, D. Zhou, and R. Yang, “Lidar-based online 3d video object detection with graph-based message passing and spatiotemporal transformer attention,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 11 495–11 504.
  * [62] D. Cai and W. Lam, “Graph transformer for graph-to-sequence learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, 2020, pp. 7464–7471.
  * [63] W. U. Ahmad, N. Peng, and K.-W. Chang, “GATE: Graph attention transformer encoder for cross-lingual relation and event extraction,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, 2021, pp. 12 462–12 470.
  * [64] L. Ma, C. Lin, D. Lim, A. Romero-Soriano, P. K. Dokania, M. Coates, P. Torr, and S.-N. Lim, “Graph Inductive Biases in Transformers without Message Passing,” _arXiv preprint arXiv:2305.17589_ , 2023.
  * [65] F. Xia, X. Chen, S. Yu, M. Hou, M. Liu, and L. You, “Coupled attention networks for multivariate time series anomaly detection,” _IEEE Transactions on Emerging Topics in Computing_ , 2023.
  * [66] D. Kreuzer, D. Beaini, W. Hamilton, V. Létourneau, and P. Tossou, “Rethinking graph transformers with spectral attention,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 21 618–21 629, 2021.
  * [67] T. Nguyen, X. Nguyen, S. R. Joty, and X. Li, “Differentiable window for dynamic local attention,” in _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , D. Jurafsky, J. Chai, N. Schluter, and J. R. Tetreault, Eds. Association for Computational Linguistics, 2020, pp. 6589–6599.
  * [68] X. Chu, Z. Tian, Y. Wang, B. Zhang, H. Ren, X. Wei, H. Xia, and C. Shen, “Twins: Revisiting the design of spatial attention in vision transformers,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 9355–9366, 2021.
  * [69] M. S. Hussain, M. J. Zaki, and D. Subramanian, “Global self-attention as a replacement for graph convolution,” in _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2022, pp. 655–665.
  * [70] J. Lee, I. Lee, and J. Kang, “Self-attention graph pooling,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 3734–3743.
  * [71] D. Soydaner, “Attention mechanism in neural networks: Where it comes and where it goes,” _Neural Computing and Applications_ , vol. 34, no. 16, pp. 13 371–13 385, 2022.
  * [72] I. Schwartz, S. Yu, T. Hazan, and A. G. Schwing, “Factor graph attention,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 2039–2048.
  * [73] Z. Wang, J. Chen, and H. Chen, “EGAT: Edge-featured graph attention network,” in _Artificial Neural Networks and Machine Learning–ICANN 2021: 30th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 14–17, 2021, Proceedings, Part I 30_. Springer, 2021, pp. 253–264.
  * [74] W. Zhang, Z. Yin, Z. Sheng, Y. Li, W. Ouyang, X. Li, Y. Tao, Z. Yang, and B. Cui, “Graph attention multi-layer perceptron,” in _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2022, pp. 4560–4570.
  * [75] Z. Niu, G. Zhong, and H. Yu, “A review on the attention mechanism of deep learning,” _Neurocomputing_ , vol. 452, pp. 48–62, 2021.
  * [76] K. Choromanski, H. Lin, H. Chen, T. Zhang, A. Sehanobish, V. Likhosherstov, J. Parker-Holder, T. Sarlos, A. Weller, and T. Weingarten, “From block-toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked transformers,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 3962–3983.
  * [77] Y. Tay, M. Dehghani, D. Bahri, and D. Metzler, “Efficient transformers: A survey,” _ACM Computing Surveys_ , vol. 55, no. 6, pp. 1–28, 2022.
  * [78] J. Liu, Z. Pan, H. He, J. Cai, and B. Zhuang, “Ecoformer: Energy-saving attention with linear complexity,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 10 295–10 308, 2022.
  * [79] A. Moreno, Z. Wu, S. Nagesh, W. Dempsey, and J. M. Rehg, “Kernel Multimodal Continuous Attention,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 18 046–18 059, 2022.
  * [80] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, “Transformers are rnns: Fast autoregressive transformers with linear attention,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5156–5165.
  * [81] H. Lee, H. Choi, K. Sohn, and D. Min, “KNN local attention for image restoration,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 2139–2149.
  * [82] Y. Mei, Y. Fan, and Y. Zhou, “Image super-resolution with non-local sparse attention,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 3517–3526.
  * [83] G. Daras, N. Kitaev, A. Odena, and A. G. Dimakis, “Smyrf-efficient attention using asymmetric clustering,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 6476–6489, 2020.
  * [84] N. Kitaev, L. Kaiser, and A. Levskaya, “Reformer: The efficient transformer,” in _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.
  * [85] D. Soydaner, “Attention mechanism in neural networks: Where it comes and where it goes,” _Neural Computing and Applications_ , vol. 34, no. 16, pp. 13 371–13 385, 2022.
  * [86] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Message passing neural networks,” _Machine learning meets quantum physics_ , pp. 199–214, 2020.
  * [87] C. Liu, Y. Sun, R. Davis, S. T. Cardona, and P. Hu, “ABT-MPNN: An atom-bond transformer-based message-passing neural network for molecular property prediction,” _Journal of Cheminformatics_ , vol. 15, no. 1, p. 29, 2023.
  * [88] H. Zhao, L. Jiang, J. Jia, P. H. Torr, and V. Koltun, “Point transformer,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 16 259–16 268.
  * [89] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [90] A. Javaloy, P. Sánchez-Martín, A. Levi, and I. Valera, “Learnable graph convolutional attention networks,” in _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.
  * [91] L. Mou and X. X. Zhu, “Learning to pay attention on spectral domain: A spectral attention module-based convolutional network for hyperspectral image classification,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 58, no. 1, pp. 110–122, 2019.
  * [92] D. Bo, C. Shi, L. Wang, and R. Liao, “Specformer: Spectral graph neural networks meet transformers,” in _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.
  * [93] D. Q. Nguyen, T. D. Nguyen, and D. Phung, “Universal graph transformer self-attention networks,” in _Companion Proceedings of the Web Conference 2022_ , 2022, pp. 193–196.
  * [94] H. Zhao, S. Ma, D. Zhang, Z. Deng, and F. Wei, “Are more layers beneficial to graph transformers?” in _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.
  * [95] S. Brody, U. Alon, and E. Yahav, “How attentive are graph attention networks?” in _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net, 2022.
  * [96] B. Heo, S. Yun, D. Han, S. Chun, J. Choe, and S. J. Oh, “Rethinking spatial dimensions of vision transformers,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 11 936–11 945.
  * [97] F. Yu, K. Huang, M. Wang, Y. Cheng, W. Chu, and L. Cui, “Width & depth pruning for vision transformers,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, 2022, pp. 3143–3151.
  * [98] H. Li, M. Wang, S. Liu, and P. Chen, “A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity,” in _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.
  * [99] R. Gubelmann and S. Handschuh, “Uncovering More Shallow Heuristics: Probing the Natural Language Inference Capacities of Transformer-Based Pre-Trained Language Models Using Syllogistic Patterns,” _arXiv preprint arXiv:2201.07614_ , 2022.
  * [100] Y. Liu, S. Pan, Y. G. Wang, F. Xiong, L. Wang, Q. Chen, and V. C. Lee, “Anomaly Detection in Dynamic Graphs via Transformer,” _IEEE Transactions on Knowledge and Data Engineering_ , pp. 1–1, 2021.
  * [101] J. Gao, J. Gao, X. Ying, M. Lu, and J. Wang, “Higher-order interaction goes neural: A substructure assembling graph attention network for graph classification,” _IEEE Transactions on Knowledge and Data Engineering_ , 2021\.
  * [102] J. Gong, Z. Teng, Q. Teng, H. Zhang, L. Du, S. Chen, M. Z. A. Bhuiyan, J. Li, M. Liu, and H. Ma, “Hierarchical graph transformer-based deep learning model for large-scale multi-label text classification,” _IEEE Access_ , vol. 8, pp. 30 885–30 896, 2020.
  * [103] Y. Yang and D. P. Wipf, “Transformers from an optimization perspective,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 36 958–36 971, 2022.
  * [104] G. Li, C. Xiong, A. Thabet, and B. Ghanem, “Deepergcn: All you need to train deeper gcns,” _arXiv preprint arXiv:2006.07739_ , 2020.
  * [105] R. Koncel-Kedziorski, D. Bekal, Y. Luan, M. Lapata, and H. Hajishirzi, “Text generation from knowledge graphs with graph transformers,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , J. Burstein, C. Doran, and T. Solorio, Eds. Association for Computational Linguistics, 2019, pp. 2284–2293.
  * [106] M. Xu, H. Wang, B. Ni, H. Guo, and J. Tang, “Self-supervised graph-level representation learning with local and global structure,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 11 548–11 558.
  * [107] L. Bergen, T. O’Donnell, and D. Bahdanau, “Systematic generalization with edge transformers,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 1390–1402, 2021.
  * [108] E. O. Johnson, E. LaVerriere, E. Office, M. Stanley, E. Meyer, T. Kawate, J. E. Gomez, R. E. Audette, N. Bandyopadhyay, N. Betancourt _et al._ , “Large-scale chemical–genetics yields new m. tuberculosis inhibitor classes,” _Nature_ , vol. 571, no. 7763, pp. 72–78, 2019.
  * [109] H. Wang, F. Guo, M. Du, G. Wang, and C. Cao, “A novel method for drug-target interaction prediction based on graph transformers model,” _BMC Bioinformatics_ , vol. 23, no. 1, p. 459, Nov. 2022.
  * [110] J. Peng, J. Li, and X. Shang, “A learning-based method for drug-target interaction prediction based on feature representation learning and deep neural network,” _BMC Bioinformatics_ , vol. 21, no. Suppl 13, p. 394, 2020\.
  * [111] X. Dong, C. Long, W. Xu, and C. Xiao, “Dual Graph Convolutional Networks with Transformer and Curriculum Learning for Image Captioning,” in _Proceedings of the 29th ACM International Conference on Multimedia_ , ser. MM ’21. New York, NY, USA: Association for Computing Machinery, Oct. 2021, pp. 2615–2624.
  * [112] R. Sortino, S. Palazzo, F. Rundo, and C. Spampinato, “Transformer-based image generation from scene graphs,” _Computer Vision and Image Understanding_ , vol. 233, p. 103721, 2023.
  * [113] Y. Zhang, Y. Pan, T. Yao, R. Huang, T. Mei, and C.-W. Chen, “End-to-End Video Scene Graph Generation with Temporal Propagation Transformer,” _IEEE Transactions on Multimedia_ , pp. 1–13, 2023.
  * [114] F. Xia, L. Wang, T. Tang, X. Chen, X. Kong, G. Oatley, and I. King, “Cengcn: Centralized convolutional networks with vertex imbalance for scale-free graphs,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 35, no. 5, pp. 4555–4569, 2022.
  * [115] Q. Wu, C. Yang, W. Zhao, Y. He, D. Wipf, and J. Yan, “Difformer: Scalable (graph) transformers induced by energy constrained diffusion,” in _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.
  * [116] W. Cong, Y. Wu, Y. Tian, M. Gu, Y. Xia, C.-c. J. Chen, and M. Mahdavi, “DyFormer: A Scalable Dynamic Graph Transformer with Provable Benefits on Generalization Ability,” in _Proceedings of the 2023 SIAM International Conference on Data Mining (SDM)_. SIAM, 2023, pp. 442–450.
  * [117] X. He, B. Hooi, T. Laurent, A. Perold, Y. LeCun, and X. Bresson, “A generalization of vit/mlp-mixer to graphs,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 12 724–12 745.
  * [118] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard, “Digress: Discrete denoising diffusion for graph generation,” in _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_ , 2023.
  * [119] H. Shirzad, A. Velingker, B. Venkatachalam, D. J. Sutherland, and A. K. Sinop, “Exphormer: Sparse transformers for graphs,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 31 613–31 632.
  * [120] M. S. Hussain, M. J. Zaki, and D. Subramanian, “Global self-attention as a replacement for graph convolution,” in _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2022, pp. 655–665.
  * [121] L. Ma, C. Lin, D. Lim, A. Romero-Soriano, P. K. Dokania, M. Coates, P. Torr, and S.-N. Lim, “Graph inductive biases in transformers without message passing,” in _International Conference on Machine Learning_ , 2023, pp. 23 321–23 337.
  * [122] W. Zhu, T. Wen, G. Song, X. Ma, and L. Wang, “Hierarchical transformer for scalable graph learning,” in _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China_ , 2023, pp. 4702–4710.
  * [123] J. Kim, S. Oh, and S. Hong, “Transformers generalize deepsets and can be extended to graphs & hypergraphs,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 016–28 028, 2021.
  * [124] D. Yao, Y. Gu, G. Cong, H. Jin, and X. Lv, “Entity resolution with hierarchical graph attention networks,” in _Proceedings of the 2022 International Conference on Management of Data_ , 2022, pp. 429–442.
  * [125] P. Balsebre, D. Yao, G. Cong, and Z. Hai, “Geospatial entity resolution,” in _Proceedings of the ACM Web Conference 2022_ , 2022, pp. 3061–3070.