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 hops away needs 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
- symmetric normalised Laplacian; eigenvalues
- Laplacian positional encoding: row of the eigenvectors with the smallest non-trivial eigenvalues, the graph analogue of sinusoidal Positional encoding
- random-walk structural encoding: probability that a -step random walk from returns to , for (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
- shortest-path distance (SPD); b is one learnable scalar per distance value, shared across all layers
- edge encoding: average over the edges on a shortest path of (edge feature · learned weight)
- 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 for 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
- any edge-aware message-passing layer (GINE, GatedGCN, …); handles edge features and local structure
- full multi-head attention () or a linear one such as Performer or BigBird ()
- node features with PE/SE (LapPE, RWSE, …) concatenated or added
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|)
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:
| Encoding | Hexagon C₆ | Two triangles 2×C₃ |
|---|---|---|
| degrees / 1-WL colours | all 2 / one colour | all 2 / one colour |
| SPD from v0 | 0, 1, 2, 3, 2, 1 | 0, 1, 1, ∞, ∞, ∞ |
| normalised Laplacian eigenvalues | 0, 0.5, 0.5, 1.5, 1.5, 2 | 0, 0, 1.5, 1.5, 1.5, 1.5 |
| RWSE (RWᵗ)₀₀ for t = 2, 3, 4 | 0.5, 0, 0.375 | 0.5, 0.25, 0.375 |
The return probability is the triangle detector: closed 3-walks out of gives . 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.
1import torch, torch.nn as nn2import torch_geometric.transforms as T3from torch_geometric.datasets import ZINC4from torch_geometric.loader import DataLoader5from torch_geometric.nn import GINEConv, GPSConv, global_add_pool67pe = T.AddRandomWalkPE(walk_length=20, attr_name="pe") # RWSE: (RW^t)_ii, t = 1..208train = ZINC("data/ZINC", subset=True, split="train", pre_transform=pe)910class 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 types14 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)1920 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 attention24 x = layer(x, b.edge_index, b.batch, edge_attr=e)25 return self.head(global_add_pool(x, b.batch)).squeeze(-1)2627model, batch = GPS(), next(iter(DataLoader(train, batch_size=32, shuffle=True)))28loss = (model(batch) - batch.y).abs().mean() # ZINC is scored by MAEUse 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 lowest non-trivial eigenvectors of ; mind sign flips and repeated eigenvalues.
- ✓RWSE: return probabilities (RWᵗ)ᵢᵢ for t = 1..K; sign-free and it counts short cycles.
- ✓Graphormer: 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.