Graph Transformers: A Survey

In plain words

Graphs are data made of things and the links between them, such as molecules, social networks and knowledge bases. Neural networks that read graphs usually pass messages between neighbours, so information from far-away nodes arrives slowly. Transformers, the models behind modern language systems, let every item look at every other item. Graph transformers try to combine the two ideas.

The catch is that a transformer has no built-in sense of order or of which nodes are connected. The designers of graph transformers therefore add extra information: where each node sits in the graph, which nodes are linked, and how much attention a pair of nodes should get based on how far apart they are. Looking at every pair of nodes also costs much more time and memory as the graph grows.

This survey sorts those design choices into categories. It also sorts the published models by depth (shallow or deep), by how they handle large graphs, and by whether they are pre-trained. It then lists the tasks where the models are used and the open problems the authors see. It runs no experiments of its own.

TL;DR

• A survey of graph transformers. It classifies how graph structure is added to self-attention, how attention is computed, and what kinds of models exist §3 §4.
• Its taxonomy has four types: shallow, deep, scalable and pre-trained graph transformers §4.
• It gives a short design guide, but the layer-count thresholds are not backed by experiments in the paper §6.
• Use it for orientation and as a map to the original papers. Check every model's category against that paper before relying on it, because the tables are the authors' own classification and contain conflicts (see Pitfalls).

Problem

Graphs appear in social networks, knowledge graphs, biology, chemistry and transportation §1. Standard transformers treat their input as a sequence, and graphs have no natural order §2. Message-passing graph neural networks (GNNs) capture local structure well but have trouble with long-range dependencies and global structure §1 §2. Graph transformers aim for both, and pay for it with higher computation and difficulty scaling to large graphs §1.

The authors say earlier surveys either focus mainly on vision (Chen et al.), skip the taxonomy (Müller et al.), or skip applications and open issues (Min et al.) §1. The paper's stated aim is a systematic review of design and application perspectives §1.

Method

This is a survey, so "method" here means the classification the paper proposes. The implementable pieces are the formulas it collects. Notation: a graph has N nodes and M edges, node features x_i, edge features e_ij, neighbours N(v) §2.

Message passing (background). A generic GNN layer updates a node from its own state and an aggregate of its neighbours' messages §2:

\mathbf{h}_v^{(l+1)} = \phi\left(\mathbf{h}_v^{(l)},\ \bigoplus_{u \in \mathcal{N}(v)} f(\mathbf{h}_u^{(l)}, \mathbf{h}_v^{(l)}, \mathbf{e}_{uv})\right) \quad [\S 2]

Step 1: how graph structure enters attention (§3.1). The paper names four kinds of graph inductive bias §3.1.

• Node positional bias (§3.1.1). Adds a vector per node. Local variants use hop distances (one-hot per distance), learned embeddings of edge types, or graph-kernel similarities between neighbourhoods. Global variants use Laplacian eigenvectors or eigenvalues, random-walk or diffusion probabilities (personalised PageRank, heat kernel), or a low-dimensional embedding that preserves graph distance §3.1.1.
• Edge structural bias (§3.1.2). Encodes distances, edge types, directions and substructures. Examples are a kernel on shortest-path distance (GraphiT), residual edge channels that adjust attention scores (EGT), edge features as extra input tokens (EdgeBERT), and global spectral or SVD encodings (Graphormer, GRPE) §3.1.2.
• Message-passing bias (§3.1.3). Combines a GNN step with attention in one of three placements, shown in fig. 3. The pseudocode below follows the equations in §3.1.3.
• Attention bias (§3.1.4). Changes the attention scores directly, as in the equations below. Local bias restricts or decays attention by distance; global bias adds a term computed from A, D, L or PageRank §3.1.4.

# Message-passing bias: three placements  [§3.1.3] [fig. 3]
# Input:  node_states (N, d); edges (M, 2); edge_feats (M, d_e)
# Output: node_states (N, d)

def preprocessing(node_states, edges, edge_feats, num_layers):
    # One message-passing step, then the attention layers  [§3.1.3]
    node_states = message_passing(node_states, edges, edge_feats)
    return attention_stack(node_states, num_layers)     # (N, d)

def interleaving(node_states, edges, edge_feats, num_layers):
    # Each layer: attention over all nodes plus a neighbourhood update  [§3.1.3]
    for layer in range(num_layers):
        local = message_passing(node_states, edges, edge_feats)  # (N, d)
        node_states = local + self_attention(node_states)        # (N, d)
    return node_states

def postprocessing(node_states, edges, edge_feats, num_layers):
    # Attention layers first, one message-passing step last  [§3.1.3]
    node_states = attention_stack(node_states, num_layers)       # (N, d)
    return message_passing(node_states, edges, edge_feats)       # (N, d)

# Attention bias  [§3.1.4]
# Input:  features (N, d); bias (N, N) from hop distance or graph matrices
# Output: attention weights (N, N)

def local_attention(features, bias, neighbours):
    # Multiplicative bias b_ij; softmax over N(v_i) only  [§3.1.4]
    scores = dot_product(features, features)                   # (N, N)
    weights = exp(scores * bias)                               # (N, N)
    return normalise_over(weights, neighbours)                 # (N, N)

def global_attention(features, graph_term):
    # Additive term c(A, D, L, P) on every pair of nodes  [§3.1.4]
    scores = dot_product(features, features)                   # (N, N)
    return softmax(scores + graph_term)                        # (N, N)

The paper's local formula is written as \alpha_{ij} = \exp(g(x_i,x_j)\, b_{ij}) / \sum_{k \in N(v_i)} \exp(g(x_i,x_k)\, b_{ik}), with g a dot product or a linear map §3.1.4. Its global formula is the same softmax with an additive term c(\mathbf{A},\mathbf{D},\mathbf{L},\mathbf{P})_{ij} §3.1.4.

Step 2: how attention is computed (§3.2). The paper groups mechanisms as global (every node attends to every node) or local (only to a subset) §3.2.

• Graph attention (§3.2, opening). Each node attends to neighbours with a learned score, a softmax over the neighbours, and a weighted sum with a residual term. The score is a LeakyReLU of a learned linear map of the two node features §3.2. Attention can also be applied to edges §3.2.
• Global, quadratic (§3.2.1). Standard softmax attention over all pairs, with cost O(N²) §3.2.1. Examples cited are GAT-style multi-head attention, GKAT, and GTN §3.2.1.
• Global, linear (§3.2.1). Approximations that aim for O(N), either kernel feature maps or locality-sensitive hashing (Reformer). The paper's formulas for both are reproduced in §3.2.1. See Pitfalls for the linear-attention formula.
• Local, message-passing attention (§3.2.2). Attention inside an MPNN-style update, cost O(E). Examples are GraphSAGE, L-CAT and PointTransformer-style layers §3.2.2.
• Local, spectral attention (§3.2.2). Self-attention computes spectral coefficients from Laplacian eigenvectors, cost O(N) §3.2.2. Examples are Specformer and UGformer §3.2.2.

Step 3: the taxonomy (§4). Models are grouped into four types, each with a table that lists the bias, attention type, application and datasets, and whether code is available §4.1 §4.2 §4.3 §4.4.

• Shallow (§4.1): few layers, aimed at efficiency. Examples: GAT, GATv2, GTN, GATE, Tree Transformer, GAT-POS, EDTER, PMPNet, GAMLP §4.1 table.
• Deep (§4.2): many stacked layers with skip, residual or dense connections, aimed at higher performance. Examples: DeepGraph, Graphormer, GRPE, GraphiT, SAT, SAN, UGformer, Edge Transformer §4.2 table.
• Scalable (§4.3): sparse, local or low-rank attention, or sampling, for large graphs. Examples: GPS, NodeFormer, DIFFormer, DyFormer, EXPHORMER, EGT, GRIT, HSGT §4.3 table.
• Pre-trained (§4.4): self-supervised pretraining on unlabelled graphs, then fine-tuning. Examples: GROVER, G-BERT, ChemBERTa, KPGT, GPT-GNN §4.4 table.

Step 4: applications (§5). The paper covers node-level (protein structure prediction, entity resolution, anomaly detection), edge-level (drug-drug and drug-target interaction, knowledge-graph completion, recommendation), graph-level (molecular property, clustering, synthesis), and non-graph uses (summarisation, captioning, image and video generation) §5.1 §5.2 §5.3 §5.4.

Step 5: design guide (§6). Four principles: choose the type by graph size, density and dynamics; add structural and positional encodings; optimise attention by sampling, sparsification, partitioning or hashing; and use pretraining for low-resource settings §6.

Hyperparameters

The paper trains nothing and reports no model hyperparameters. The only numeric guidance is in the design guide §6:

Results

Not applicable. The paper is a survey and reports no experiments of its own. The tables in §4 record each model's categories, applications and datasets as the authors read them from the original papers §4.1 §4.2 §4.3 §4.4. They do not give numbers. For performance, read the original paper.

Paper vs code

No official code. The paper is a survey and has no implementation. The LaTeX source contains no code link. The taxonomy tables have a "Code availability" column, which records whether each original model has code, not whether this paper does §4.1 table. Paper-collection repositories (awesome lists) that readers link to surveys are not code. I did not run a repository search for this survey.

Pitfalls

• GAT is classed inconsistently. §3.2.1 places the multi-head attention of Veličković et al. (GAT) under quadratic global attention §3.2.1. The shallow table lists GAT's global attention as "Yes (linear)" §4.1 table. Check which one matches the GAT paper before using the table to pick an attention type.
• The "linear" formula is not linear as written. The LTN formula in §3.2.1 still sums over all N keys in the denominator for every query, which is the O(N²) pattern. The text says linear attention reduces cost to O(N) §3.2.1. Check the feature-map formula against the cited paper before implementing it. The card does not use this formula as a recipe.
• Local attention bias is multiplicative. In §3.1.4 the bias b_ij multiplies the score inside exp(·). A binary b_ij of 0 then gives exp(0) = 1, not an excluded entry. Exclusion comes only from the softmax being summed over N(v_i). An implementation that masks with b_ij alone will not match the formula. The paper does not say which it intends.
• One technique under two headings. Laplacian eigenvector positional encoding is attributed to Rampášek et al. in §3.1.1. The global edge-structural section (§3.1.2) attributes spectral global encoding to Graphormer. The paper does not explain why it is in both places. Treat the two sections as one idea with two sources.
• Two "attention" formulas are about depth, not neighbours. The GraphSAGE and GIN equations in §3.2.2 weight layers with α_il, not neighbours. The text calls GIN a spectral attention mechanism §3.2.2, but the equation shown is a sum-aggregation message-passing update. Read the original model before implementing either.
• Spectral transform notation. §2 writes the graph Fourier transform as X̂ = UᵀXU, which applies U to a matrix of features. The notation for a single signal is not given. Check the cited source before implementing.
• Degree matrix is undefined. The Laplacian L = I − D^(−1/2) A D^(−1/2) and the bias term in §3.1.4 use the degree matrix D, but its row in the notation table is commented out in the source §2.
• Abstract lists a challenge with no section. The abstract and the contribution list name data quality and diversity as open issues. §7 has subsections only for scalability, generalisation and robustness, interpretability and dynamic graphs §7.
• Design guide has a gap. The thresholds in §6 cover graphs under 10³ and over 10⁵ nodes. The range between is not covered. The thresholds and layer counts have no citation or experiment in the text.
• Tables are the authors' classification. Each model's bias, attention type, application and datasets are the authors' reading of the original papers. The paper does not say how they were checked. Several rows also conflict with the text (see the GAT item).
• Some applications are grouped oddly. Recommendation and knowledge-graph completion sit under edge-level tasks §5.2. The text does not explain this grouping.
• Source version. The card follows arXiv v2 (the version fetched). The source carries reviewer-response markers, so the text may differ from v1.

Lineage

• Builds on: the transformer §2 (Vaswani et al.), GNN message passing §2, and GAT §3.2.1. None has a card in this wiki.
• Compared against: the surveys of Chen et al., Müller et al. and Min et al. §1.
• Superseded by: not stated in the paper.