Transformer for Graphs: An Overview from Architecture Perspective

Abstract

Recently, Transformer model, which has achieved great success in many artificial intelligence fields, has demonstrated its great potential in modeling graph-structured data. Till now, a great variety of Transformers has been proposed to adapt to the graph-structured data. However, a comprehensive literature review and systematical evaluation of these Transformer variants for graphs are still unavailable. It’s imperative to sort out the existing Transformer models for graphs and systematically investigate their effectiveness on various graph tasks. In this survey, we provide a comprehensive review of various Graph Transformer models from the architectural design perspective. We first disassemble the existing models and conclude three typical ways to incorporate the graph information into the vanilla Transformer: 1) GNNs as Auxiliary Modules, 2) Improved Positional Embedding from Graphs, and 3) Improved Attention Matrix from Graphs. Furthermore, we implement the representative components in three groups and conduct a comprehensive comparison on various kinds of famous graph data benchmarks to investigate the real performance gain of each component. Our experiments confirm the benefits of current graph-specific modules on Transformer and reveal their advantages on different kinds of graph tasks.

1 Introduction

Graph is a kind of data structure that structurally depicts a set of objects (nodes) with their relationships (edges). As a unique non-Euclidean data structure, graph analysis focuses on tasks such as node classification Yang et al. (2016), link prediction Zhang and Chen (2018), and clustering Aggarwal (2010). Recent research on analyzing graphs using deep learning has attracted more and more attention due to the rich expressive power of deep learning models. Graph Neural Networks (GNNs) Kipf and Welling (2016), as a kind of deep learning-based method, are recently becoming a widely-used graph analysis tools due to their convincing performance. Most of the current GNNs are based on the Message Passing paradigm Gilmer et al. (2017), the expressive power of which is bounded by the Weisfeiler-Lehamn isomorphism hierarchy Maron et al. (2019); Xu et al. (2018a). Worse still, as pointed out by Kreuzer et al. (2021), GNNs suffer from the over-smoothing problem due to repeated local aggregation, and the over-squashing problem due to the exponential computation cost with the increase of model depth. Several studies Zhao and Akoglu (2019); Rong et al. (2019); Xu et al. (2018b) try to address such problems. Nevertheless, none of them seems to be able to eliminate these problems from the Message Passing paradigm.

On the other hand, Transformers and its variants, as a powerful class of models, are playing an important role in various areas including Natural Language Processing (NLP) Vaswani et al. (2017), Computer Vision (CV) Forsyth and Ponce (2011), Time-series Analysis Hamilton (2020), Audio Processing Purwins et al. (2019), etc. Moreover, recent years have witnessed many successful Transformer variants in modeling graphs. These models have achieved competitive or even superior performance against GNNs in many applications, such as Quantum Property Prediction Hu et al. (2021), Catalysts Discovery Chanussot* et al. (2021) and Recommendation Systems Min et al. (2022). The literature reviews and systematic evaluations for these Transformer variants are, however, lacking.

This survey gives an overview of the current research progress on incorporating Transformers in graph-structured data. Concretely, we provide a comprehensive review of over 20 Graph Transformer models from the architectural design perspective. We first dismantle the existing models and conclude three typical ways to incorporate the graph information into the vanilla Transformer: 1) GNNs as Auxiliary Modules, i.e., directly inject GNNs into Transformer architecture. Specifically, according to the relative position between GNN layers and Transformer layers, existing GNN-Transformer architectures can be categorized into three types: (a) build Transformer blocks on top of GNN blocks, (b) stack GNN blocks and Transformer blocks in each layer, (c) parallel GNN blocks and Transformer blocks in each layer. 2) Improved Positional Embedding from Graphs, i.e., compress the graph structure into positional embedding vectors and add them to the input before it is fed to the vanilla Transformer model. This graph positional embedding can be derived from the structural information of graphs, such as degree and centrality. 3) Improved Attention Matrices from Graphs, i.e., inject graph priors into the attention computation via graph bias terms, or restrict a node only attending to local neighbours in the graph, which can be computationally formulated as an attention masking mechanism.

Additionally, in order to investigate the effectiveness of existing models in various kinds of graph tasks, we implement the representative components in three groups and conduct comprehensive ablation studies on six popular graph-based benchmarks to uniformly test the real performance gain of each component. Our experiments indicate that: 1). Current models incorporating the graph information can improve the performance of Transformer on both graph-level and node-level tasks. 2). Utilizing GNN as auxiliary modules and improving attention matrix from graphs generally contributes more performance gains than encoding graphs into positional embeddings. 3). The performance gain on graph-level tasks is more significant than that on node-level tasks. 4) Different kinds of graph tasks enjoy different group of models.

The rest of this survey is organized as follows. We first review the general vanilla Transformer Architecture in Section 2. Section 3 summarizes existing works about the Transformer variant on Graphs and systematically categorizes these methods into three groups. In Section 4, comprehensive ablation studies are conducted to verify the effectiveness and compatibility of these proposed models. In Section 5, we conclude this survey and discuss several future research directions.

2 Transformer Architecture

Transformer Vaswani et al. (2017) architecture was first applied to machine translation. In the paper, Transformer is introduced as a novel encoder-decoder architecture built with multiple blocks of self-attention. Let $𝐗\in {ℝ}^{n\times d}$ to be the input of each Transformer layer, where $n$ is number of tokens, $d$ is the dimension of each token, then one block layer can be a function $f_{\theta }:{ℝ}^{n\times d}\to {ℝ}^{n\times d}$ with $f_{\theta }(𝐗)=:𝐙$ defined by:

$𝐀$ $={\displaystyle \frac{1}{\sqrt{d}}}\mathrm{𝐗𝐐}{(\mathrm{𝐗𝐊})}^{\top },$ (1)

$\widetilde{𝐗}$ $=\mathrm{SoftMax}(𝐀)(\mathrm{𝐗𝐕}),$ (2)

$𝐌$ $={\mathrm{LayerNorm}}_1(\widetilde{𝐗}𝐎+𝐗),$ (3)

$𝐅$ $=\sigma ({\mathrm{𝐌𝐖}}_1+{𝐛}_1){𝐖}_2+{𝐛}_2,$ (4)

$𝐙$ $={\mathrm{LayerNorm}}_2(𝐌+𝐅),$ (5)

where Equation 1, Equation 2, and Equation 3 are the attention computation; while Equation 4 and Equation 5 are the position-wise feed-forward network (FFN) layers. Here, $\text{Softmax}(\cdot )$ refers to the row-wise softmax function, $\text{LayerNorm}(\cdot )$ refers to layer normalization function Ba et al. (2016), and $\sigma$ refers to the activation function. $𝐐,𝐊,𝐕,𝐎\in {ℝ}^{d\times d},{𝐖}_1\in {ℝ}^{d\times d_f},{𝐛}_1\in {ℝ}^{d_f},{𝐖}_2\in {ℝ}^{d_f\times d},{𝐛}_2\in {ℝ}^d$ are trainable parameters in the layer. Furthermore, it is common to consider multiple attention heads to extend the self-attention to Multi-head Self-attention (MHSA). Specifically, $𝐐,𝐊,𝐕$ are decomposed into $H$ heads with ${𝐐}^{(h)},{𝐊}^{(h)},{𝐕}^{(h)}\in {ℝ}^{d\times d_h}$ with $d={\sum }_{h=1}^H{d}_h$, and the matrices ${\widetilde{𝐗}}^{(h)}\in {ℝ}^{n\times d_h}$ from attention heads are concatenated to obtain $\widetilde{𝐗}$. In this case, Equation 1 and Equation 2 respectively become:

${𝐀}^{(h)}={\displaystyle \frac{1}{\sqrt{d}}}{\mathrm{𝐗𝐐}}^{(h)}{({\mathrm{𝐗𝐊}}^{(h)})}^{\top },$ (6)

$\widetilde{𝐗}={\parallel }_{h=1}^H(\mathrm{SoftMax}({𝐀}^{(h)}){\mathrm{𝐗𝐕}}^{(h)}).$ (7)

The multi-head mechanism enables the model to implicitly learn representation from different aspects. Apart from the attention mechanism, the paper uses $\mathrm{sine}$ and $\mathrm{cosine}$ functions with different frequencies as positional embedding to distinguish the position of each token in the sequence.

Table 1: A summary of papers that applied Transformers on graph-structured data. GA: GNNs as Auxiliary Modules; PE: Improved Positional Embedding from Graphs; AT: Improved Attention Matrix from Graphs.

Method	GA	PE	AT	Code
Zhu et al. (2019)			✓	✓
Shiv and Quirk (2019)		✓
Wang et al. (2019)		✓	✓
U2GNN Nguyen et al. (2019)			✓	✓
HeGT Yao et al. (2020)			✓	✓
Graformer Schmitt et al. (2020)			✓	✓
PLAN Khoo et al. (2020)			✓	✓
UniMP Shi et al. (2020)			✓
GTOS Cai and Lam (2020)		✓	✓	✓
Graph Trans Dwivedi and Bresson (2020)		✓	✓	✓
Grover Rong et al. (2020)	✓			✓
Graph-BERT Zhang et al. (2020)	✓	✓		✓
SE(3)-Transformer Fuchs et al. (2020)			✓	✓
Mesh Graphormer Lin et al. (2021)	✓	✓		✓
Gophormer Zhao et al. (2021)			✓
EGT Hussain et al. (2021)		✓	✓	✓
SAN Kreuzer et al. (2021)		✓	✓	✓
GraphiT Mialon et al. (2021)	✓	✓	✓	✓
Graphormer Ying et al. (2021)	✓	✓	✓	✓
Mask-transformer Min et al. (2022)			✓	✓
TorchMD-NET Thölke and de Fabritiis (2022)			✓	✓

3 Transformer Architecture for Graphs

The self-attention mechanism in the standard Transformer actually considers the input tokens as a fully-connected graph, which is agnostic to the intrinsic graph structure among the data. Existing methods that enable Transformer to be aware of topological structures are generally categorized into three groups: 1) GNNs as auxiliary modules in Transformer (GA), 2) Improved positional embedding from graphs (PE), 3) Improved attention matrices from graphs (AT). We summarize relevant literature in terms of these three dimensions in Table 1.

(a) Before Trans

(b) Alternatively

(c) Parallel

Figure 1: Three types of GNN-as-Auxiliary-Modules architecture.

3.1 GNNs as Auxiliary Modules in Transformer

The most direct solution of involving structural knowledge to benefit from global relation modeling of self-attention is to combine graph neural networks with Transformer architecture. Generally, according to the relative postion between GNN layers and Transformer layers, existing Transformer architectures with GNNs are categorized into three types as illustrated in Figure 1: (1) building Transformer blocks on top of GNN blocks, (2) alternately stacking GNN blocks and Transformer blocks, (3) parallelizing GNN blocks and Transformer blocks.

The first architecture is most-frequently adopted among the three options. For example, GraphTrans Jain et al. (2021) adds a Transformer subnetwork on top of a standard GNN layer. The GNN layer performs as a specialized architecture to learn local representations of the structure of a node’s immediate neighbourhood, while the Transformer subnetwork computes all pairwise node interactions in a position-agnostic fashion, empowering the model global reasoning capability. GraphTrans is evaluated on graph classification task from biology, computer programming and chemistry, and achieves consistent improvement over benchmarks.

Grover Rong et al. (2020) consists of two GTransformer modules to represent node-level features and edge-level features respectively. In each GTransformer, the inputs are first fed into a tailored GNNs named dyMPN to extract vectors as queries, keys and values from nodes of the graph, followed by standard multi-head attention blocks. This bi-level information extraction framework enables the model to capture the structural information in molecular data and make it possible to extract global relations between nodes, enhancing the representational power of Grover.

GraphiT Mialon et al. (2021) also falls in the first architecture, which adopts one Graph Convolutional Kernel Network (GCKN) Chen et al. (2020) layer to produce a structure-aware representation from original features, and concatenate them as the input of Transformer architecture. Here, GCKNs is a multi-layer model that produces a sequence of graph feature maps similar to a GNN. Different from GNNs, each layer of GCKNs enumerates local sub-structures at each node, encodes them using a kernel embedding, and aggregates the sub-structure representations as outputs. These representations in a feature map carry more structural information than traditional GNNs based on neighborhood aggregation.

Mesh Graphormer Lin et al. (2021) follows the second architecture by stacking a Graph Residual Block (GRB) on a multi-head self-attention layer as a Transformer block to model both local and global interactions among 3D mesh vertices and body joints. Specifically, given the contextualized features $𝐌$ generated by multi-head self-attentions (MHSA) in Equation 3, Mesh Graphormer improves the local interactions using a graph convolution in each Transformer block as:

$${𝐌}^{\prime }=\text{GraphConv}({𝐀}^G,𝐌;{𝐖}^G)=\sigma ({𝐀}^G{\mathrm{𝐗𝐖}}^G).$$ (8)

where ${𝐀}^G\in {ℝ}^{n\times n}$ denotes the adjacency matrix of a graph and ${𝐖}_G$ denotes the trainable parameters. $\sigma (\cdot )$ implies the non-linear activation function. Mesh Graphormer also implements another two variants: building GRB before MHSA and building those two blocks in parallel, but they perform worse than the proposed one.

Graph-BERT Zhang et al. (2020) adopts the third architecture by utilizing a graph residual term in each attention layer as follows:

$${𝐌}^{\prime }=𝐌+\text{G-Res}(𝐗,{𝐗}_r,{𝐀}^G),$$ (9)

where the notation $\text{G-Res}(𝐗,{𝐗}_r,{𝐀}^G)$ represents the graph residual term introduced in Zhang and Meng (2019) and ${𝐗}_r$ is the raw features of all nodes in the graph.

3.2 Improved Positional Embeddings from Graphs

Although combining graph neural networks and Transformer has shown effectiveness in modeling graph-structured data, the best architecture to incorporate them remains an issue and requires heavy hype-parameter searching. Therefore, it is meaningful to explore a graph-encoding strategy without adjustment of the Transformer architecture. Similar to the positional encoding in Transformer for sequential data such as sentences, it is also possible to compress the graph structure into positional embedding (PE) vectors and add them to the input before it is fed to the actual Transformer model:

$$\widetilde{𝐗}=𝐗+f_{\text{map}}(𝐏),$$ (10)

where $𝐗\in {\mathrm{R}}^{n\times d}$ is the matrix of input embeddings, $𝐏\in {\mathrm{R}}^{n\times d_p}$ represents the graph embedding vectors, and $f_{\text{map}}:{\mathrm{R}}^{d_p}\to {\mathrm{R}}^d$ is a transformation network to align the dimension of both vectors. The graph positional embedding $𝐏$ is normally generated from the adjacent matrix ${𝐀}^G\in {\mathrm{R}}^{n\times n}$.

Dwivedi and Bresson (2020) adopt Laplacian eigenvectors as $𝐏$ in Graph Transformer. For each graph in the dataset, they pre-compute the Laplacian eigenvectors , which are defined by the factorization of the graph Laplacian matrix:

$${𝐔}^T\mathrm{\Lambda }𝐔=𝐈-{𝐃}^{-1/2}{𝐀}^G{𝐃}^{-1/2},$$ (11)

where $𝐃$ is the degree matrix, and $\mathrm{\Lambda },𝐔$ correspond to the eigenvalues and eigenvectors respectively. They use eigenvectors of the $k$ smallest non-trivial eigenvalues as the positional embedding, with $𝐏\in {ℝ}^{n\times k}$ in this case. Since these eigenvectors have multiplicity occurring due to the arbitrary sign of eigenvectors, they randomly flip the sign of the eigenvectors during training.

Hussain et al. (2021) employs pre-computed SVD vectors of the adjacent matrix as the positional embeddings $𝐏$. They use the largest $r$ singular values and corresponding left and right singular vectors to represent the positional encoding.

${𝐀}^G\stackrel{\mathrm{SVD}}{\approx }𝐔𝚺{𝐕}^T=(𝐔\sqrt{𝚺})\cdot {(𝐕\sqrt{𝚺})}^T=\widehat{𝐔}{\widehat{𝐕}}^T,$ (12)

$𝐏=\widehat{𝐔}\parallel \widehat{𝐕},$ (13)

where $𝐔,𝐕\in {\mathrm{R}}^{n\times r}$ contain the $r$ left and right singular vectors corresponding to the top $r$ singular values in the diagonal matrix $\mathrm{\Sigma }\in {ℝ}^{r\times r}$, $\parallel$ denotes concatenation operator along columns. They also randomly flip the signs during training as a form of data augmentation to avoid over-fitting, since similar to Laplacian eigenvectors, the signs of corresponding pairs of left and right singular vectors can be arbitrarily flipped.

Different from Eigen PE and SVD PE, which attempt to compress the adjacent matrix into dense positional embeddings, there exist some heuristic methods that encode specific structural information from the extraction of the adjacent matrix. For example, Graphormer Ying et al. (2021) uses the degree centrality as an additional signal to the neural network. To be specific, Graphformer assigns each node two real-valued embedding vectors according to its indegree and outdegree. For the $i$-th node, the degree-aware representation is denoted as:

$$\widetilde{𝐱}=𝐱+{𝐳}_{{\mathrm{deg}}^{-}(v_i)}^{-}+{𝐳}_{{\mathrm{deg}}^{+}(v_i)}^{+},$$ (14)

where ${𝐳}^{-},{𝐳}^{+}\in {ℝ}^d$ are learnable embedding vectors specified by the indegree ${\mathrm{deg}}^{-}(v_i)$ and outdegree ${\mathrm{deg}}^{+}(v_i)$ respectively. For undirected graphs, ${\mathrm{deg}}^{-}(v_i)$ and ${\mathrm{deg}}^{+}(v_i)$ could be unified to be $\mathrm{deg}(v_i)$. By using the centrality encoding in the input, the softmax attention will catch the node importance signal in queries and keys of the Transformer.

Graph-BERT Zhang et al. (2020) introduces three types of PE to embed the node position information, i.e., an absolute WL-PE which represents different codes labeled by the Weisfeiler-Lehman algorithm, an intimacy based PE and a hop based PE which are both variant to the sampled subgraphs. Cai and Lam (2020) applies graph transformer to tree-structured abstract meaning representation (AMR) graph. It adopts a distance embedding for each node by encoding the minimum distance from the root node as a flag of the importance of the corresponding concept in the whole-sentence semantics. Kreuzer et al. (2021) proposes a learned positional encoding that can utilize the full Laplacian spectrum to learn the position of each node in a given graph.

3.3 Improved Attention Matrices from Graphs

Although node positional embedding is a convenient practice to inject graph priors into Transformer architectures, the progress of compressing graph structure into fixed-sized vectors suffers from information loss, which might limit their effectiveness. For this sake, another group of works attempts to improve the attention matrix computation based on graph information:

(15)

where $𝐗$ is the input features, ${𝐀}^G$ is the adjacent matrix of the graph, $𝐄\in {ℝ}^{n\times n\times d_e}$ is the edge features if available, $𝐐,𝐊,𝐕$ are the attention parameters, ${𝐖}_1,{𝐖}_2$ are extra graph encoding parameters.

One line of models adapts self-attention mechanism to GNN-like architectures by restricting a node only attending to local node neighbours in the graph, which can be computationally formulated as an attention masking mechanism:

$$𝐀=(\frac{1}{\sqrt{d}}\mathrm{𝐗𝐐}{(\mathrm{𝐗𝐊})}^{\top })\odot {𝐀}^G,$$ (16)

where ${𝐀}^G\in {ℝ}^{n\times n}$ is the adjacent matrix of the graph. In Dwivedi and Bresson (2020), ${𝐀}_{ij}^G=1$ if there is an edge between $i$-th node and $j$-th node. Given the simple and generic nature of this architecture, they obtain competitive performance against standard GNNs on graph datasets. In order to encode edge features, they also extend Equation 16 as:

$$𝐀=(\frac{1}{\sqrt{d}}\mathrm{𝐗𝐐}{(\mathrm{𝐗𝐊})}^{\top })\odot {𝐀}^G\odot {𝐄}^{\prime }{𝐖}_E,$$ (17)

where ${𝐖}_E\in {ℝ}^{d_e\times d}$ is the parameter matrix, ${𝐄}^{\prime }$ is the edge embedding matrix from the previous layer which is updated based on $𝐀$, we do not elaborate these details for simplicity.

One possible extension of this practice is masking the attention matrices of different heads with different graph priors. In the original multi-head self-attention blocks, different attention heads implicitly attend to information from different representation subspaces of different nodes. While in this case, using the graph-masking mechanism to enforce the heads explicitly attend to different subspaces with graph priors further improves the model representative capability for graph data. For example, Yao et al. (2020) computes the attention based on the extended Levi graph. Since Levi graph is a heterogeneous graph that contains different types of edges. They first group all edge types into a single one to get a homogeneous subgraph referred to as connected subgraph. The connected subgraph is actually an undirected graph that contains the complete connected information in the original graph. Then they split the input graph into multiple subgraphs according to the edge types. Besides learning the directly connected relations, they introduce a fully-connected subgraph to learn the implicit relationships between indirectly connected nodes. Multiple adjacent matrices are assigned to different attention heads to learn a better representation for AMR task. Min et al. (2022) adopts a similar practice, which carefully designs four types of interaction graphs for modeling neighbourhood relations in CTR prediction task: induced subgraph, similarity graph, cross-neighbourhood graph, and complete graph. And they use the masking mechanism to encode these graph priors to improve neighbourhood representation.

GraphiT Mialon et al. (2021) extends the adjacent matrix to a kernel matrix, which is more flexible to encode various graph kernels. Besides, they use the same matrix for keys and queries following the recommendation of Tsai et al. (2019) to reduce parameters without hurting the performance in practice, and adopt a degree matrix to reduce the overwhelming influence of highly connected graph components. The update equation can be formulated as:

$𝐀$ $=({\displaystyle \frac{1}{\sqrt{d}}}\mathrm{𝐗𝐐}{(\mathrm{𝐗𝐐})}^{\top })\odot {𝐊}_r,$ (18)

$\widetilde{𝐗}$ $=\text{SoftMax}(𝐀)(\mathrm{𝐗𝐕}),$

$𝐌$ $=\text{LayerNorm}({𝐃}^{-\frac{1}{2}}\widetilde{𝐗}+𝐗),$

where $𝐃\in {ℝ}^{n\times n}$ is the diagonal matrix of node degrees, ${𝐊}_r\in {ℝ}^{n\times n}$ is the kernel matrix on the graph, which is used as diffusion kernel and p-step random walk kernel.

Another line of models attempts to add soft graph bias to attention scores. Graphormer Ying et al. (2021) proposes a novel Spatial Encoding mechanism. Concretely, they consider a distance function $\varphi (v_i,v_j)$, which measures the spatial relation between nodes $v_i$ and $v_j$ in the graph. They select $\varphi (v_i,v_j)$ as the shortest path distance (SPD) between $v_i$ and $v_j$. If they are not connected, the output of $\varphi$ is set as a special value, i.e., $-1$. They assign each feasible value of $\varphi$ a learnable scale parameter as a graph bias term. So the update rule is:

$$𝐀=(\frac{1}{\sqrt{d}}\mathrm{𝐗𝐐}{(\mathrm{𝐗𝐊})}^{\top })+{𝐁}^s.$$ (19)

${𝐁}^s$ is the bias matrix, where ${𝐁}_{ij}^s=b_{\varphi (v_i,v_k)}$ is the learnable scalar indexed by $\varphi (v_i,v_k)$, and shared across all layers. In order to handle graph structure with edge features, they also design an edge feature bias term. Specifically, for each ordered node pair $(v_i,v_j)$, they search (one of) the shortest path ${\text{SP}}_{ij}=(e_1,e_2,\mathrm{\dots },e_N)$ from $v_i$ to $v_j$, and then compute an average of dot-products of the edge features and a learnable embedding along the path. Combined with the above spatial bias, the unnormalized attention score can be modified as:

$$𝐀=(\frac{1}{\sqrt{d}}\mathrm{𝐗𝐐}{(\mathrm{𝐗𝐊})}^{\top })+{𝐁}^s+{𝐁}^c$$ (20)

where ${𝐁}^c$ is the edge feature bias matrix. ${𝐁}_{ij}^c=\frac{1}{N}{\sum }_{n=1}^N{x}_{e_n}{(w_n^E)}^{\top }$, where $x_{e_n}$ is the feature of the $n$-th edge $e_n$ in ${\mathrm{SP}}_{ij},w_n^E\in {ℝ}^{d_e}$ is the $n$-th weight embedding, and $d_e$ is the dimensionality of edge feature.

Gophormer Zhao et al. (2021) proposes proximity-enhanced multi-head attention (PE-MHA) to encode multi-hop graph information. Specifically, for a node pair $⟨v_i,v_j⟩$, $M$ views of structural information is encoded as a proximity encoding vector, denoted as ${\varphi }_{ij}\in {ℝ}^M$, to enhance the attention mechanism. The proximity-enhanced attention score ${𝐀}_{ij}$ is defined as:

$${𝐀}_{ij}=(\frac{1}{\sqrt{d}}{𝐱}_i𝐐{({𝐱}_j𝐊)}^{\top })+{\mathit{\varphi }}^{ij}{𝐛}^{\top },$$ (21)

where $𝐛\in {ℝ}^M$ is the learnable parameters that compute the bias of structural information. The proximity encoding is calculated by $M$ structural encoding functions defined as:

$${\mathit{\varphi }}_{ij}=\mathrm{Concat}({\mathrm{\Phi }}_m(v_i,v_j)|m\in 0,1,\mathrm{\dots },M-1),$$ (22)

where each structural encoding function ${\mathrm{\Phi }}_m(\cdot )$ encodes a view of structural information.

PLAN Khoo et al. (2020) also proposes a structure aware self-attention to model the tree structure of rumour propagation in social media. The modified attention calculation can be defined as:

${𝐀}_{ij}$ $={\displaystyle \frac{1}{\sqrt{d}}}({𝐱}_i𝐐{({𝐱}_j𝐊)}^{\top })+a_{ij}^K$ (23)

${𝐌}_i$ $={\displaystyle \sum _{j=1}^n}\text{SoftMax}({𝐀}_{ij})({𝐱}_j𝐕+a_{ij}^V)$ (24)

Both $a_{ij}^V$ and $a_{ij}^K$ are learnable parameter vectors that represent one of the five possible structural relationships between the pair of the tweets (i.e. parent, child, before, after and self).

Table 2: Details of the datasets.

Dataset Type	Name	#Graph	#Nodes(Avg.)	#Edges(Avg.)	Task type	Metric
Graph-level	ZINC	12,000	23.2	49.8	Regression	MAE
	ogbg-molhiv	41,127	25.5	27.5	Binary cla.	ROC-AUC
	ogbg-molpcba	437,929	26.0	28.1	Binary cla.	AP
Node-level	Flickr	1	89,250	899,756	Multi-class cla.	Accuracy
	ogbg-arxiv	1	169,343	1,166,243	Multi-class cla.	Accuracy
	ogbg-product	1	2,449,029	61,859,140	Multi-class cla.	Accuracy

Table 3: Hyper-parameters of various Transformer sizes.

	Transformer Size
	Small	Middle	Large
#Layers	6	12	12
Hidden Dimension	80	80	512
FFN Inner Hidden Dimension	80	80	512
#Attention Heads	8	8	32
Hidden Dimension of Each Head	10	10	16

Table 4: Performance comparison on graph-level tasks. For each column, the values with underline are the best results in each group. The values in bold are the best results across the groups.

		graph-level tasks									node-level tasks
		ZINC(MAE$\downarrow$)			molhiv(ROC-AUC$\uparrow$)			molpcba(AP$\uparrow$)			Flickr(Acc$\uparrow$)			arixv(Acc$\uparrow$)			product(Acc$\uparrow$)
		Small	Middle	Large	Small	Middle	Large	Small	Middle	Large	Small	Middle	Large	Small	Middle	Large	Small	Middle	Large
TF	vanilla	0.6689	0.6700	0.6699	0.7466	0.7230	0.7269	0.1624	0.1673	0.1676	0.5270	0.5279	0.5214	0.5539	0.5571	0.5598	0.7887	0.7887	0.7956
GA	before	0.4700	0.4809	0.5169	0.6758	0.7339	0.7182	0.2105	0.1989	0.2269	0.5352	0.5369	0.5272	0.5608	0.5590	0.5614	0.7953	0.7888	0.8012
	alter	0.3771	0.3412	0.2956	0.7200	0.7086	0.7433	0.2474	0.2417	0.2244	0.5374	0.5357	0.5162	0.5599	0.5555	0.5592	0.7905	0.7915	0.8057
	parallel	0.3803	0.2749	0.2984	0.7138	0.7750	0.7603	0.2345	0.2444	0.2205	0.5370	0.5379	0.5209	0.5647	0.5600	0.5529	0.7878	0.7896	0.7999
PE	degree	0.5364	0.5364	0.5435	0.7506	0.6818	0.7357	0.1672	0.1646	0.1650	0.5291	0.5250	0.5133	0.5551	0.5618	0.5502	0.7920	0.7913	0.7947
	eig	0.6031	0.6074	0.6166	0.7407	0.7279	0.7351	0.2194	0.2087	0.2131	0.5253	0.5278	0.5257	0.5575	0.5637	0.5658	0.7893	0.7887	0.8017
	svd	0.5811	0.5462	0.5400	0.7350	0.7155	0.7275	0.1648	0.1663	0.1767	0.5281	0.5317	0.5203	0.5614	0.5663	0.5706	0.7856	0.7893	0.8007
AT	SPB	0.5122	0.4878	0.6100	0.7065	0.7589	0.7255	0.2409	0.2524	0.2621	0.5368	0.5364	0.5234	0.5503	0.5605	0.5576	0.7921	0.7918	0.7984
	PMA	0.6194	0.6057	0.5963	0.6902	0.7054	0.7314	0.2115	0.1956	0.2518	0.5240	0.5288	0.5204	0.5567	0.5571	0.5492	0.7877	0.7853	0.7945
	Mask-1	0.2861	0.2772	0.2894	0.7610	0.7753	0.7960	0.2573	0.2662	0.1594	0.5295	0.5300	0.5236	0.5598	0.5559	0.5583	0.7923	0.7917	0.7963
	Mask-n	0.3906	0.3596	0.4765	0.7286	0.7423	0.7128	0.2619	0.2577	0.2380	0.5359	0.5349	0.5348	0.5593	0.5603	0.5576	0.7935	0.7917	0.8016

Table 5: The training hyper-parameters.

attention dropout	0.1	FFN dropout	0.1
maximum steps	1e+6	warm-up steps	4e+4
peak learning rate	2e-4	batch size	256
weight decay value	1e-3	lr decay	Linear
gradient clip norm	5.0	Adam $ϵ,{\beta }_1,{\beta }_2$	1e-8, 0.9, 0.99

4 Experimental Evaluations

We conduct an extensive evaluation to study the effectiveness of different methods. On the basis of standard Transformer, methods in the three groups, auxiliary GNN modules (GA), positional embeddings (PE), and improved attention (AT) are compared. Since most methods are composed of more than one graph-specific module and are trained with various tricks, it is difficult to evaluate the effectiveness of each module in a fair and independent way. In our experiments, we extract the representative modules of existing models and evaluate their performance individually. For GA methods, we compare the three architectures described in Section 3.1. In both alternately and parallel settings, the GNNs and Transformer layers are combined before the FFN layers. PE methods include degree embedding Ying et al. (2021), Laplacian Eigenvectors Dwivedi and Bresson (2020) and SVD vectors Hussain et al. (2021). AT methods contain spatial bias (SPB) Ying et al. (2021), proximity-enhanced multi-head attention (PMA) Zhao et al. (2021), attention masked with 1-hop adjacent matrix (Mask-1) Dwivedi and Bresson (2020). We also mask attention with different hops of the adjacent matrix, denoted as (Mask-n), inspired by the multi-head masking mechanisms in Yao et al. (2020); Min et al. (2022). We evaluate the methods on both graph-level tasks on small graphs and node-level tasks on a single large graph. The details of the tasks and datasets are listed in Table 2.

4.1 Settings and Implementation Details

To ensure a consistent and fair evaluation, we fix the scale of the Transformer architecture in three levels: small, middle, and large, whose configurations are listed in Table 3. The remaining hyper-parameters are fixed to their empirical value as shown in Table 5. For node-level tasks in large-scale graphs, we adopt the shadow $k$-hop sampling Zeng et al. (2020) to generate a subgraph for a target node, to which the graph-aware modules are applied. We calculate the required inputs of all modules based on the subgraph instead of the original graph because most of them are not computationally scalable to large graphs. We set the maximum sampling hop to be $2$ and the maximum neighbourhood per node to be $10$. For PE methods, we select the embedding size from $\{3,4,5\}$. For GA methods, we select the GNN type from GCN Kipf and Welling (2016), GAT Velivckovic et al. (2017) and GIN Xu et al. (2018a). Our learning framework is built on PyTorch 1.8, and PyTorch Geometric 2.0, and the code is public at https://github.com/qwerfdsaplking/Graph-Trans.

4.2 Experimental Results

Table 4 reports the performance of ten graph-specific modules from three categories on six datasets of graph-level and node-level tasks, respectively. We summarize the main observations as follows:

• Not surprisingly, in most cases, the evaluated graph-specific modules of Transformer lead to to better performance. For example, on molpcba, we observe at most a 56% performance improvement compared with the vanilla Transformer. This observation confirms the effectiveness of graph-specific modules on the various kinds of graph tasks.

• The improvement on graph-level tasks is more significant than that on node-level tasks. This may be due to the graph sampling process when dealing with a single large graph. The sampled induced subgraphs fail to keep the original graph intact, incurring variance and information loss in the learning process.

• GA and AT methods bring more benefits than PE methods. In conclusion, PE’s weaknesses are twofold. First, as introduced in Section 3.2, PE does not contain intact graph information. Second, since PE is only fed into the input layer of the network, the graph-structural information would decay layer by layer across the model, leading to a degeneration of the performance.

• It seems that different kinds of graph tasks enjoy different group of models. GA methods achieve the best performance in more than half of the cases (5 out of 9 cases) of node-level tasks. More significantly, AT methods achieve the best performance in almost all the cases (8 out of 9 cases) of graph-level tasks. We conjecture that GA methods are able to better encode the local information of the sampled induced subgraphs in node-level tasks, while AT methods are suitable for modeling the global information of the single graphs in graph-level tasks.

In summary, our experiments confirm the value of the existing graph-specific module on Transformer and reveal their advantages for a variety of graph tasks.

5 Conclusion and Future Directions

In this survey, we present a comprehensive review of the current progress of applying Transformer model on graphs. Based on the injection part of graph data and graph model in Transformer, we classify the existing graph-specific modules into three typical groups: GNNs as auxiliary modules, improved positional embeddings from graphs, and improved attention matrices from graphs. To investigate the real performance gains under a fair setup, we implement the representative modules from three groups and compare them on six benchmarks with different tasks. We hope our systematic review and comparison will foster understanding and stimulate new ideas in this area.

In spite of the current successes, we believe several directions would be promising to investigate further and to start from in the future, including:

• New paradigm of incorporating the graph and the Transformer. Most studies treat the graphs as strong prior to modifying the Transformer model. There is a great interest to develop the new paradigm that not just takes graphs as a prior, but also better reflects the properties of graphs.

• Extending to other kinds of graphs. Existing Graph Transformer models mostly focus on homogeneous graphs, which consider the node type and edge type as the same. It is also important to explore their potential on other forms of graphs, such as heterogeneous graphs and hypergraphs.

• Extending to large-scale graphs. Most existing methods are designed for small graphs, which might be computationally infeasible for large graphs. As illustrated in our experiments, directly applying them to the sampled subgraphs would impair performance. Therefore, designing salable Graph-Transformer architecture is essential.