Graph transformers

Graph transformers let every node attend to every other and put the graph back in through Laplacian or random-walk encodings and shortest-path attention biases (Graphormer); GPS runs this in parallel with message passing.

8 min read713 wordsadvanced0 viewsupdated 2026-10-21

Definition

Graph transformer A graph neural network whose layers use Self-attention between nodes, over all node pairs or over the edges only, with the graph structure supplied by positional or structural encodings added to node features or by attention biases indexed by pairwise structure. Key papers: Dwivedi and Bresson, "A Generalization of Transformer Networks to Graphs" (AAAI 2021 workshop on Deep Learning on Graphs); Ying et al., "Do Transformers Really Perform Bad for Graph Representation?" (Graphormer, NeurIPS 2021); Rampášek et al., "Recipe for a General, Powerful, Scalable Graph Transformer" (GPS, NeurIPS 2022).

The inputs are graphs, often small molecules, and the outputs are usually graph-level (a property of the whole molecule) or node-level labels. Message-passing layers such as Graph Convolutional Network (GCN) or Graph Isomorphism Network (GIN) only mix information along edges. Two limits follow. Their power to tell graphs apart is bounded by the 1-WL test. And information from rr hops away needs rr layers and must squeeze through the few nodes in between (over-squashing), so long-range interactions are hard.

A Transformer encoder applied to the node set fixes the reach: every node sees every other in one layer. But attention is permutation-equivariant and ignores edges, so on its own it treats the graph as a set. With identical node features, every attention row is uniform. The whole design problem is how to put the structure back without breaking permutation equivariance.

Encodings: where is a node, and what is around it

Δ=I−D−1/2AD−1/2=UΛU⊤,PEi=(Ui,1,…,Ui,k),RWSEi=((AD−1)ii, (AD−1)ii2, …, (AD−1)iiK)\Delta=I-D^{-1/2}AD^{-1/2}=U\Lambda U^{\top},\qquad \mathrm{PE}_i=\big(U_{i,1},\dots,U_{i,k}\big),\qquad \mathrm{RWSE}_i=\big((AD^{-1})_{ii},\,(AD^{-1})^2_{ii},\,\dots,\,(AD^{-1})^K_{ii}\big)
Δ\Delta
symmetric normalised Laplacian; eigenvalues 0=λ0≤λ1≤⋯≤20=\lambda_0\le\lambda_1\le\dots\le 2
PEi\mathrm{PE}_i
Laplacian positional encoding: row ii of the kk eigenvectors with the smallest non-trivial eigenvalues, the graph analogue of sinusoidal Positional encoding
RWSEi\mathrm{RWSE}_i
random-walk structural encoding: probability that a tt-step random walk from ii returns to ii, for t=1..Kt=1..K (Dwivedi et al., ICLR 2022)

Low-frequency eigenvectors vary smoothly over the graph, so nodes close together get similar PE vectors. Eigenvectors are only defined up to sign, and up to any rotation when an eigenvalue repeats. Dwivedi and Bresson flip signs at random during training; SignNet and BasisNet (Lim et al., ICLR 2023) build the invariance into the network. RWSE has no such ambiguity, and its entries count short cycles: a 3-step return is impossible without a triangle.

Graphormer: structure as an attention bias

Aij=(hiWQ)(hjWK)⊤d+bϕ(vi,vj)+cij,hi(0)=xi+zdeg⁡−(vi)−+zdeg⁡+(vi)+A_{ij}=\frac{(h_iW_Q)(h_jW_K)^{\top}}{\sqrt d}+b_{\phi(v_i,v_j)}+c_{ij},\qquad h_i^{(0)}=x_i+z^{-}_{\deg^{-}(v_i)}+z^{+}_{\deg^{+}(v_i)}
ϕ(vi,vj)\phi(v_i,v_j)
shortest-path distance (SPD); b is one learnable scalar per distance value, shared across all layers
cijc_{ij}
edge encoding: average over the edges on a shortest path of (edge feature · learned weight)
z±z^{\pm}
centrality encoding: learned embeddings of in- and out-degree added to the input features

The bias sits inside the softmax of Scaled dot-product attention, so a large negative bdb_d for d≥2d\ge2 makes Graphormer attend only to neighbours. Ying et al. show this lets it express GIN-, GCN- and GraphSAGE-style aggregation as special cases, while SPD lets it separate graphs that 1-WL cannot. Graphormer also adds a virtual node connected to all others, used as the graph readout.

GPS: local and global in parallel

XMℓ+1=MPNNℓ(Xℓ,Eℓ,A),XTℓ+1=GlobalAttnℓ(Xℓ),Xℓ+1=MLPℓ(XMℓ+1+XTℓ+1)X_M^{\ell+1}=\mathrm{MPNN}^{\ell}(X^{\ell},E^{\ell},A),\qquad X_T^{\ell+1}=\mathrm{GlobalAttn}^{\ell}(X^{\ell}),\qquad X^{\ell+1}=\mathrm{MLP}^{\ell}\big(X_M^{\ell+1}+X_T^{\ell+1}\big)
MPNN\mathrm{MPNN}
any edge-aware message-passing layer (GINE, GatedGCN, …); handles edge features and local structure
GlobalAttn\mathrm{GlobalAttn}
full multi-head attention (O(N2)O(N^2)) or a linear one such as Performer or BigBird (O(N)O(N))
X0X^{0}
node features with PE/SE (LapPE, RWSE, …) concatenated or added
graph transformer: attention over nodes, structure injected as encodings or biases1 graph + encodingsv1v2v3v4v5v6h⁰ᵢ = xᵢ ‖ PEᵢ (or SEᵢ)LapPE or RWSE (RWᵗ)ᵢᵢ2 GPS layer ℓ (× L)Xˡ (N × d)local MPNNedges onlyO(|E|)global attnall N² pairsor linear O(N)+MLP → Xˡ⁺¹each branch: residual + norm3 SPD(vᵢ, vⱼ) → biasa learned scalar per hop012213101222210121221012122103321230Aᵢⱼ = qᵢ·kⱼ/√d + b[SPDᵢⱼ]degree in: 2 2 3 2 2 1→ hᵢ += z[deg(vᵢ)]GT (Dwivedi & Bresson)attention over neighbours only+ Laplacian eigenvector PEGraphormer (Ying et al.)full attention + SPD bias,degree (centrality) embeddingsGPS (Rampášek et al.)MPNN ∥ global attention,PE/SE added to node featuresreadout for graph tasks: mean/sum pool over nodes (or a virtual node / [CLS] token) → MLP
fig.The pieces on a 6-node graph (a 5-ring with a pendant v6). 1: PE or SE vectors are attached to the node features. 2: a GPS layer runs a message-passing branch over the 6 edges and an attention branch over all 36 pairs, sums them and applies an MLP; L layers are stacked. 3: Graphormer's alternative, a learned bias for each shortest-path distance (0 to 3 here) added to the attention logits, plus degree embeddings. Bottom: which model uses which ingredient.

Each branch has its own residual connection and normalisation; the GPS paper uses Batch normalization, as Dwivedi and Bresson had found it works better than Layer normalization on graphs. Dwivedi and Bresson's original GT restricted attention to neighbours and found it beat full attention on their benchmarks. GPS keeps the edge-local branch for that inductive bias and adds the global branch for reach.

Datasets and results

ZINC (12k subset)
10,000 / 1,000 / 1,000 molecular graphs; regress constrained solubility; metric MAE, lower is better
Graphormer on ZINC
Graphormer-slim, MAE 0.122 ± 0.006 (Ying et al., 2021)
GPS on ZINC
MAE 0.070 ± 0.004 with RWSE (Rampášek et al., 2022)
PCQM4M-LSC
about 3.8M molecules, HOMO–LUMO gap regression; Graphormer won this quantum-chemistry track of the OGB Large-Scale Challenge at KDD Cup 2021
Cost
full attention is O(N²) per layer, fine for molecules (tens of atoms); for large graphs GPS swaps in linear attention, and the MPNN branch stays O(|E|)
full self-attention over 12 nodes with identical input featuresscore = τ·⟨PEᵢ, PEⱼ⟩/√k, k = 2 eigenvectorsv0.216v1.064v2.034v3.165v4.236v5.257v6.003v7.004v8.005v9.004v10.006v11.005click a node to make it the query · labels = α(v0, j)attention matrix (rows: queries)shade ∝ √α · v0–v5 | v6–v11query v0: mass on self + 1-hop 0.702 · own community 0.972 · E[SPD] 1.152all 12 queries: self + 1-hop 0.785 · own community 0.901 · E[SPD] 0.974uniform reference: own community 0.500, a GCN layer puts 1.000 on self + 1-hopnormalised-Laplacian eigenvalues used: 0.068, 0.439SPD row of v0: 0 1 2 1 2 1 5 4 3 4 5 6
structure
query node
fig.Full attention over two 6-node communities joined by the bridge v2–v8, all with the same input features, so the scores come only from structure (W_Q = W_K = I). Default, Laplacian PE with k = 2 and τ = 2, query v0: α = 0.216 to itself, 0.257 to v5 and 0.236 to v4, which is 2 hops away, against 0.064 to the neighbour v1. PE measures smooth position, not adjacency. v0 puts 0.972 on its own community; over all 12 queries the figure is 0.901. Click "no structure": every α is 1/12 = 0.083 and own-community mass is 0.500. Push k to 11: the full eigenbasis is orthonormal, so each node attends almost only to itself (0.992). "SPD bias" with β = 1: v0 gives 0.404 to itself and 0.149 to each of its 3 neighbours (own community 0.959). The bridge node v2 gives 0.131 to v1, v3 and v8 alike, so only 0.731 stays in its community.

Worked example: a hexagon versus two triangles

Both graphs have 6 nodes, 6 edges and every degree equal to 2. With identical node features, 1-WL colour refinement never splits the nodes, so every message-passing GNN maps both graphs to the same output. Encodings tell them apart:

EncodingHexagon C₆Two triangles 2×C₃
degrees / 1-WL coloursall 2 / one colourall 2 / one colour
SPD from v00, 1, 2, 3, 2, 10, 1, 1, ∞, ∞, ∞
normalised Laplacian eigenvalues0, 0.5, 0.5, 1.5, 1.5, 20, 0, 1.5, 1.5, 1.5, 1.5
RWSE (RWᵗ)₀₀ for t = 2, 3, 40.5, 0, 0.3750.5, 0.25, 0.375
Computed in Python for node v0 of each graph

The t=3t=3 return probability is the triangle detector: 22 closed 3-walks out of 23=82^3=8 gives 0.250.25. The repeated eigenvalue 0.5 of the hexagon also shows the basis problem: any rotation of its two eigenvectors is equally valid, so a raw LapPE of C₆ is not uniquely defined.

python
1import torch, torch.nn as nn
2import torch_geometric.transforms as T
3from torch_geometric.datasets import ZINC
4from torch_geometric.loader import DataLoader
5from torch_geometric.nn import GINEConv, GPSConv, global_add_pool
6
7pe = T.AddRandomWalkPE(walk_length=20, attr_name="pe") # RWSE: (RW^t)_ii, t = 1..20
8train = ZINC("data/ZINC", subset=True, split="train", pre_transform=pe)
9
10class GPS(nn.Module):
11 def __init__(self, d=64, pe_dim=8, layers=10):
12 super().__init__()
13 self.atom = nn.Embedding(28, d - pe_dim) # 28 atom types
14 self.pe_lin = nn.Linear(20, pe_dim)
15 self.bond = nn.Embedding(4, d)
16 mlp = lambda: nn.Sequential(nn.Linear(d, d), nn.ReLU(), nn.Linear(d, d))
17 self.layers = nn.ModuleList(GPSConv(d, GINEConv(mlp()), heads=4) for _ in range(layers))
18 self.head = nn.Linear(d, 1)
19
20 def forward(self, b):
21 x = torch.cat([self.atom(b.x.squeeze(-1)), self.pe_lin(b.pe)], dim=-1)
22 e = self.bond(b.edge_attr)
23 for layer in self.layers: # MPNN branch + global attention
24 x = layer(x, b.edge_index, b.batch, edge_attr=e)
25 return self.head(global_add_pool(x, b.batch)).squeeze(-1)
26
27model, batch = GPS(), next(iter(DataLoader(train, batch_size=32, shuffle=True)))
28loss = (model(batch) - batch.y).abs().mean() # ZINC is scored by MAE
A GPS model on ZINC with RWSE in PyTorch Geometric (not run here: no PyG in this sandbox)

Use when

  • +One layer reaches every node: no over-squashing through bottleneck nodes
  • +SPD bias and RWSE/LapPE separate graphs that 1-WL and plain message passing cannot
  • +Strong on molecules: GPS ZINC MAE 0.070; Graphormer won PCQM4M-LSC at KDD Cup 2021
  • +GPS is modular: choose the MPNN, the attention and the encodings separately

Avoid when

  • −Full attention is O(N²) in time and memory per layer
  • −Eigenvector PEs need sign/basis handling and O(N³) preprocessing
  • −Weak locality prior: pure global attention can lose to a GNN on small or homophilous graphs
  • −More hyperparameters (PE type and size, attention type) than a GCN or GIN

Check yourself

A plain Transformer encoder (no encodings, no bias) runs on a graph whose nodes all have the same feature vector. What does its first attention layer compute?

Check yourself

Which quantity distinguishes a 6-cycle from two disjoint triangles?

Remember

  • ✓Graph transformers attend over nodes; structure enters only via encodings (LapPE, RWSE), attention biases (SPD, edges) or a parallel MPNN.
  • ✓LapPE: rows of the kk lowest non-trivial eigenvectors of I−D−1/2AD−1/2I-D^{-1/2}AD^{-1/2}; mind sign flips and repeated eigenvalues.
  • ✓RWSE: return probabilities (RWᵗ)ᵢᵢ for t = 1..K; sign-free and it counts short cycles.
  • ✓Graphormer: Aij=qi⋅kj/d+bSPD(i,j)+cijA_{ij}=q_i\cdot k_j/\sqrt d+b_{\mathrm{SPD}(i,j)}+c_{ij} plus degree embeddings; won PCQM4M-LSC at KDD Cup 2021.
  • ✓GPS: X = MLP(MPNN(X) + GlobalAttn(X)) per layer, full or linear attention; ZINC MAE 0.070.
← back to Deep Learning roadmap