wikillm

Paper · 2025-02-23 · cs.LG, cs.AI

A Survey of Graph Transformers: Architectures, Theories and Applications

Survey of Graph Transformers (GTs). It sorts GT architectures into four ways of bringing graph structure into attention: multi-level tokens, structural positional encodings, structure-aware attention, and GNN-Transformer ensembles. It also covers scalability, equivariance, Weisfeiler-Lehman expressivity and applications. No experiments are run; tables are qualitative.

Graph transformerPositional encodingGraph neural networkGraph structure learningsurveygraph-learningtransformers

arXivPDFMarkdown11 min read

AI-compiled by claude-haiku-5-5 on 2026-11-13, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Graph data is everywhere: molecules, proteins, social networks, road networks. The usual tool for it, a graph neural network, lets each node update its description by looking at its neighbours. That works locally, but information has to hop along the edges one step at a time, so distant parts of a graph barely talk to each other, and stacking many layers can make all node descriptions blur together.

Transformers solved a similar problem for text by letting every token look at every other token. Graph transformers try the same trick on graphs. The difficulty is that a plain transformer ignores the graph's wiring, so the graph has to be fed back in somehow: by turning small pieces of the graph into tokens, by giving each node a "where am I in the graph" label, by changing how much each pair of nodes attends to each other, or by running a graph network alongside the transformer.

This survey sorts the many published designs into those four ways, asks how much each design can actually tell apart in theory, and lists where graph transformers are used. Its main practical message is that the shape of the input graph (relational, geometric, dynamic or heterogeneous) predicts which design choices tend to help more than the application domain does. The survey itself runs no experiments, so its guidance is a map to test, not a ranking.

TL;DR

  • A survey of graph transformers (GTs) with no new experiments §1.
  • Four architecture families: multi-level tokenization, structural positional encoding, structure-aware attention and GNN-Transformer ensembles, plus notes on scalability and equivariance §3.
  • Expressivity is discussed through the Weisfeiler-Lehman (WL) hierarchy; the authors argue that a stronger theoretical PE does not reliably give better accuracy §4.1, §6.1.
  • Applications are organised by graph form, and a frequency table (Table 4) maps components to forms as qualitative tiers, not measured results §5.6.

Problem

The survey addresses the lack of a single organising view of GT designs. The authors note that earlier reviews focused mainly on architecture, and they add a theory section and an application section tied to graph form §1. Their starting observation is that vanilla attention is a message-passing network on a fully connected graph, so the design question becomes how to inject the real edges and other structure §3 opening.

Two limits motivate the review. Message passing suffers from over-smoothing and over-squashing, which make long-range dependencies hard to capture §1. Full attention costs quadratic time in the number of nodes, which blocks large graphs §3.5.

Method

This is a survey, so "method" here means the taxonomy and the shared formulations the survey uses. The notation is a graph with node features H (n by d) and adjacency A §2.

Background formulas. Message passing is written with a message function and an update function over neighbours §2, eq. 1. Scaled dot-product attention has queries, keys and values from linear maps, softmax over the scaled product, and the result multiplied by the values §2, eq. 2. Attention can be read as a message-passing layer on a complete graph §2, eq. 3. The feed-forward block is two linear layers with ReLU, with residual connections and layer normalisation §2, eq. 4. Multi-head attention splits the dimension into H heads of size d/H §2, eq. 5.

Taxonomy of structure injection §3, tab. 1:

  1. Multi-level graph tokenization (§3.1). Tokens are nodes (§3.1.1), edges (§3.1.2), induced subgraphs (§3.1.3) or hop shells around an anchor node (§3.1.4). Subgraph tokens keep the internal topology of a patch. Hop tokens keep the distance structure around an anchor and let self-attention run per node over its hop sequence, which allows mini-batch training §3.1.4.
  2. Structural positional encoding (§3.2). Absolute PEs are a function f of the adjacency, P = f(A), combined with node features through a function g [§3.2, eq. 6]. Laplacian PE uses the smallest eigenvectors of the normalised Laplacian §3.2, eq. 7. Two fixes are sign-invariant networks eq. 8 and a stable spectral form eq. 9. SVD PE uses the leading singular vectors and also works on directed and weighted graphs eq. 10. Random-walk PE stacks the diagonal return probabilities of the walk operator M = A D^-1 for k steps eq. 11. Degree encodings add learned vectors per degree at the input eq. 12, and GRIT adds degree information after the transformer block eq. 13. SAT adds a degree-scaled residual §3.2, text.
  3. Structure-aware attention (§3.3). Three ways: an additive attention bias §3.3.1, eq. 14; a multiplicative attention mask §3.3.2, eq. 17; or edge-level tokens inside attention §3.3.3. Table 2 lists the bias or mask of each named method. Graphormer uses a learned scalar per shortest-path distance plus an averaged edge encoding along the path §3.3.1, eq. 15. Graphormer-GD uses a resistance-distance-based bias and a multiplicative gate §3.3.1, eq. 16. GraphiT uses diffusion and random-walk kernels as masks §3.3.2. EGT combines a bias and a gate in one formula §3.3.2, eq. 18. Edge-token models update edges from attention eq. 19, eq. 20 or concatenate node and edge tokens with identifiers eq. 21.
  4. Model ensemble between GNNs and Transformers (§3.4). Four placements: GNN before Transformer, Transformer before GNN, interleaved blocks, and parallel branches fused at the output §3.4. GraphGPS uses parallel branches; SGFormer uses a single linear-attention layer with GCN blocks; CoBFormer adds an alignment loss between its GCN and Transformer branches §3.4.

Scalability §3.5. Linear attention variants replace softmax attention with cheaper forms, but structural bias does not fit them directly. NodeFormer handles this with an edge-level loss that pushes attention on connected pairs toward high values §3.5, eq. 22. Exphormer uses a union of adjacency, an expander graph and a virtual node §3.5. NAGphormer aggregates k-hop neighbourhoods into one token per hop before attention §3.5.

Geometric GTs §3.6. For 3D graphs, the distance between atoms enters as an edge feature, often through radial basis functions §3.6. TorchMD-Net uses distance-dependent filters, a SiLU score in place of softmax and a cutoff function §3.6, eqs. 23-25. Uni-Mol's coordinate head moves each node by a weighted sum of differences to other nodes, applied only in the last layer §3.6, eq. 26. High-order steerable models such as SE(3)-Transformer and Equiformer are named but left outside the survey's scope §3.6.

Expressivity §4.1. Structural tokenization and positional encoding are analysed separately. A transformer over k-tuple tokens can emulate k-order WL iterations layer by layer, so stronger-than-1-WL power comes from the token set and not from attention alone §4.1.1. Hop tokens and subgraph tokens are distinguished by their inductive bias §4.1.1. Absolute and relative PE can be equivalent on graphs without node features, but converting relative PE to absolute PE can lose information once node features exist §4.1.2. Section 4.1.3 extends the discussion to signed graphs, directed graphs and hypergraphs, which the authors argue fit the same framework §4.1.3.

Relations to other methods §4.2. Self-attention can speed convergence and PE can help generalisation, according to a cited study §4.2.1. MPNNs with a virtual node are strong baselines on the Long Range Graph Benchmark §4.2.1. Transformers, like graph attention networks, can over-smooth with depth, and a generalised PageRank attention is proposed against that §4.2.1. GTs can be seen as learning a soft, fully connected graph structure §4.2.2.

Applications §5. The survey writes all tasks with four shared templates: graph-level prediction, pair scoring, graph generation, and graph-to-text decoding §5.1, eqs. 27-30. It then groups applications into relational graphs (§5.2), geometric and periodic graphs (§5.3), dynamic graphs (§5.4) and heterogeneous or multimodal graphs (§5.5). Each subsection lists named models per task fig. 3.

Discussion §6. The authors argue that graph structure is treated as ground truth in message passing, while GTs treat it as a soft prior §6.1. They argue that feature dilution from aggregation is the real cause behind many deep-GNN failures §6.1. They argue that WL expressivity measures isomorphism rather than generalisation §6.1. Open directions are scaling, multimodal GTs, non-attention long-range models, theory beyond spectral PE, and graph foundation models §6.2.

Practical guidance §5.6, tab. 4. The authors tally how often each component appears in strong models per graph form, and sort them into three tiers. The table is in the Results section below.

Structure-aware attention as a single layer

The pseudocode below combines the bias and mask forms the survey describes. It is an abstraction for implementers, not code from any model. Relation functions are placeholders for SPD, resistance distance or random-walk kernels.

Pseudocode
# Structure-aware self-attention layer  [§3.3] [eq. 14] [eq. 17]
# Input:  nodes (n, d); adjacency (n, n); pair features (n, n, e)
# Output: updated nodes (n, d)

def structure_aware_attention(nodes, adjacency, pair_feats):
    # 1. Project nodes to queries, keys and values  [§2] [eq. 2]
    queries = nodes @ W_Q                       # (n, d)
    keys = nodes @ W_K                          # (n, d)
    values = nodes @ W_V                        # (n, d)
    # 2. Scaled dot-product scores  [§2] [eq. 2]
    scores = queries @ keys.T / sqrt(d)         # (n, n)
    # 3. Additive structural bias  [§3.3.1] [eq. 14]
    bias = relation_bias(adjacency, pair_feats) # (n, n)
    scores = scores + bias
    # 4. Multiplicative structural mask, as written in eq. 17  [§3.3.2]
    mask = relation_mask(adjacency, pair_feats) # (n, n)
    attn = softmax(scores * mask, dim=-1)       # (n, n)
    # 5. Aggregate values  [§2] [eq. 2]
    return attn @ values                        # (n, d)

Sign-invariant Laplacian PE

Laplacian eigenvectors are only defined up to sign, so the survey describes a network that gives the same output for v and -v §3.2, eq. 8.

Pseudocode
# Sign-invariant Laplacian positional encoding  [§3.2] [eq. 8]
# Input:  eigvecs (n, k), the k smallest non-trivial eigenvectors
# Output: pe (n, out_dim)

def sign_invariant_pe(eigvecs):
    # 1. Encode each eigenvector and its negation, then add  [§3.2] [eq. 8]
    parts = []
    for i in range(k):
        vec = eigvecs[:, i]                  # (n,)
        parts.append(phi(vec) + phi(-vec))   # (n, h)
    # 2. Concatenate over eigenvectors and map to the PE  [§3.2] [eq. 8]
    pe = rho(concat(parts, dim=-1))          # (n, out_dim)
    return pe

Hyperparameters

The survey runs no experiments, so it reports no training settings. It names some method hyperparameters without giving values:

NameValueWhereNotes
Laplacian PE: number of smallest eigenvectors knot stated§3.2Dwivedi et al. style PE
SAN: number of eigenvectors mnot stated§3.2called "a hyperparameter"
random-walk PE length knot statedeq. 11 §3.2k-step return probabilities
GRIT: random-walk length Knot stated§3.3.1initialises P as powers of M
GraphiT: diffusion β and walk length pnot stated§3.3.2both called hyperparameters
GraphiT: walk weight γnot stated§3.3.2used in the p-step kernel
Graphormer: shortest-path bias and degree vectorslearned, not valuedeq. 12 eq. 15learnable scalars and vectors
NodeFormer: number of layers L in the edge lossnot statedeq. 22no loss weight stated

Results

No experiments are run and no new benchmark numbers are reported. The survey reports qualitative tables only. Author-reported numbers from cited papers are not reproduced here.

Table 4, frequency of components by graph form §5.6, tab. 4. Tiers are the authors' own judgement: ●●● high, ●●○ medium, ●○○ low or emerging, ○○○ not applicable. Row labels are reworded from the paper.

ComponentRelationalGeometricDynamicHeterogeneous
Node tokens●●●●●●●●●●●●
Edge tokens●●○●○○●○○●●○
Subgraph tokens●●○●○○●○○●○○
Hop tokens●●○○○○●○○●○○
Shortest-path PE●●●●●○●○○●○○
Walk-return encoding●●●●○○●○○●○○
Node-degree encoding●●○●○○●○○●○○
Spectral encoding●○○●●○●○○○○○
Time-based encoding○○○○○○●●●○○○
Attention bias or mask●●●●●○●●○●●○
Distance-based attention○○○●●●●○○○○○
Cross-attention●○○●●○●○○●●●
GNN plus Transformer blocks●●○●○○●●○●●●
Type-specific projections●●○●○○●○○●●●
Sparse or linear attention●○○●○○●●○●○○
Sampling or pooling●●○●○○●○○●●○
Equivariant updates○○○●●●○○○○○○
Pairwise geometric features○○○●●●●○○○○○
Angle encoding○○○●●○○○○○○○

Table 1, architecture summary §3, tab. 1. The survey lists about 28 named models, each marked for token type, PE, attention structure and whether it has an MPNN ensemble. Notable entries: Graphormer, GRIT and Equiformer use node tokens; TokenGT and TGT use edge tokens; NAGphormer uses hop tokens; SAT and GraphiT use subgraph tokens; GraphGPS and SGFormer are ensembles tab. 1. The table is a summary; check the source row before you implement anything from it.

Table 3, PE trade-offs §4.1.2, tab. 3. Expressivity, complexity, stability and constraints for degree, Laplacian, SVD, random-walk and shortest-path PE. Laplacian PE is above 1-WL in expressivity but has low stability and sign ambiguity; shortest-path PE is hard to adapt to linear attention; degree PE fails on regular graphs.

Paper vs code

No official code.

The LaTeX source (raw/src/2502.16533), the arXiv metadata and the abstract contain no repository or project-page link. A GitHub repository search for "graph transformers survey" found no repository owned by an author or a lab of an author. Two survey-named repositories exist under unrelated owners and were not used. Nothing in this survey is an implementation, so there is nothing to compare against code.

Pitfalls

  • No experiments. Table 4 and the tiers in §5.6 are the authors' summary of the literature. The authors present them as a map to test, not a fixed rule §5.6. Do not treat them as measured effects.
  • Equation 17 and the text disagree on masks. Eq. 17 multiplies the scores element-wise by the mask inside the softmax §3.3.2, eq. 17. The text then defines masks as edge weights, and as -∞ for non-adjacent pairs §3.3.2. A -∞ value only works when added to the scores, not multiplied. Implementations usually add a bias or set masked logits to -∞ before the softmax.
  • Graphormer-GD's distance matrix is defined inconsistently. The text defines R_ij as a set of shortest-path length and path, which is a shortest-path object §3.3.1, yet calls R the resistance distance and Table 2 names it resistance distance. Compute resistance distance as the name says, and check the original paper.
  • Laplacian PE is not stable. Eigenvectors are sign-ambiguous and ambiguous within repeated eigenvalues, and small perturbations of the graph change them §3.2. The sign-invariant network eq. 8 addresses sign only. Repeated eigenvalues need a separate basis-invariant method, which the survey points to but does not define in full §3.2.
  • SVD PE is not sign-invariant. The survey flags this as a future direction §3.2, so any SVD PE needs sign handling added by the implementer.
  • Structural bias does not fit linear attention. Attention bias and mask need an explicit N by N matrix, and linear attention never builds one §3.5. NodeFormer's loss eq. 22 is one workaround, and it only constrains edges.
  • Hop tokens are not subgraph tokens with a different k §3.1.4, §4.1.1. Implement them as separate tokenisers.
  • Expressivity gains may not show in accuracy. The authors say a theoretically stronger PE does not uniformly improve benchmark results, and that many datasets are dominated by node attributes or local targets §4.1.2, §6.1.
  • Figures. Figure 1 credits its application illustrations to earlier studies fig. 1. Figures are not reproduced in this card, and the survey's own illustrations are not ours to republish.
  • Graph size. The survey's "scalable" methods trade exactness for speed (sparse, hop, pooled tokens) and do not all keep the same inductive bias §3.5. Check which bias you need before choosing one.

Lineage

  • Builds on: the Transformer self-attention formulation the survey cites as its base §2; the message-passing framework §2, eq. 1. The survey gives no arXiv id for these in its text.
  • Works it reviews that have cards here: Graphormer (shortest-path bias and degree encodings, §3.2 and §3.3.1) and TokenGT (edge and node tokens, §3.3.3 and §4.1.1).
  • Compared against: message-passing GNNs (§4.2.1), graph attention networks §4.2.1 and graph structure learning §4.2.2.
  • Superseded by: not stated in the paper.

Source and license

Adapted from “A Survey of Graph Transformers: Architectures, Theories and Applications” by Chaohao Yuan, Kangfei Zhao, Ercan Engin Kuruoglu, Liang Wang, Tingyang Xu, Wenbing Huang, Deli Zhao, Hong Cheng, Yu Rong (arXiv:2502.16533), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.