# 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.

Source: https://www.mlfoundry.in/learn/graph-transformers  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: advanced · 8 min read · updated 2026-10-21

**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 $r$ hops away needs $r$ 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

$$
\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=\lambda_0\le\lambda_1\le\dots\le 2$
- $\mathrm{PE}_i$: Laplacian positional encoding: row $i$ of the $k$ eigenvectors with the smallest non-trivial eigenvalues, the graph analogue of sinusoidal **Positional encoding**
- $\mathrm{RWSE}_i$: random-walk structural encoding: probability that a $t$-step random walk from $i$ returns to $i$, for $t=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

$$
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)}
$$

- $\phi(v_i,v_j)$: shortest-path distance (SPD); b is one learnable scalar per distance value, shared across all layers
- $c_{ij}$: edge encoding: average over the edges on a shortest path of (edge feature · learned weight)
- $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 $b_d$ for $d\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

$$
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)
$$

- $\mathrm{MPNN}$: any edge-aware message-passing layer (GINE, GatedGCN, …); handles edge features and local structure
- $\mathrm{GlobalAttn}$: full multi-head attention ($O(N^2)$) or a linear one such as Performer or BigBird ($O(N)$)
- $X^{0}$: node features with PE/SE (LapPE, RWSE, …) concatenated or added

> Figure: 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|)

> Figure: 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:

Computed in Python for node v0 of each graph

| 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 $t=3$ return probability is the triangle detector: $2$ closed 3-walks out of $2^3=8$ gives $0.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
import torch, torch.nn as nn
import torch_geometric.transforms as T
from torch_geometric.datasets import ZINC
from torch_geometric.loader import DataLoader
from torch_geometric.nn import GINEConv, GPSConv, global_add_pool

pe = T.AddRandomWalkPE(walk_length=20, attr_name="pe")       # RWSE: (RW^t)_ii, t = 1..20
train = ZINC("data/ZINC", subset=True, split="train", pre_transform=pe)

class GPS(nn.Module):
    def __init__(self, d=64, pe_dim=8, layers=10):
        super().__init__()
        self.atom = nn.Embedding(28, d - pe_dim)               # 28 atom types
        self.pe_lin = nn.Linear(20, pe_dim)
        self.bond = nn.Embedding(4, d)
        mlp = lambda: nn.Sequential(nn.Linear(d, d), nn.ReLU(), nn.Linear(d, d))
        self.layers = nn.ModuleList(GPSConv(d, GINEConv(mlp()), heads=4) for _ in range(layers))
        self.head = nn.Linear(d, 1)

    def forward(self, b):
        x = torch.cat([self.atom(b.x.squeeze(-1)), self.pe_lin(b.pe)], dim=-1)
        e = self.bond(b.edge_attr)
        for layer in self.layers:                              # MPNN branch + global attention
            x = layer(x, b.edge_index, b.batch, edge_attr=e)
        return self.head(global_add_pool(x, b.batch)).squeeze(-1)

model, batch = GPS(), next(iter(DataLoader(train, batch_size=32, shuffle=True)))
loss = (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)

> **Laplacian PE is not a fixed coordinate system:** Two runs of an eigensolver can return $-u$ instead of $u$, or a rotated basis when eigenvalues repeat (the hexagon above). A model that memorises raw PE values will not transfer between graphs or even between runs. Use random sign flips in training, a sign-invariant encoder, or RWSE. Also budget the preprocessing: a dense eigendecomposition is $O(N^3)$ per graph, fine for molecules, not for a million-node graph.

> **Attention without structure is a set model:** Drop the encodings and a graph transformer is permutation-equivariant over a **set** of nodes: it cannot tell a hexagon from two triangles, or even from 6 isolated nodes. Every structural signal enters through PE, SE, the attention bias, or the MPNN branch. Which one you choose sets the expressive power, not the attention itself.

**Strengths**

- 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

**Limitations**

- 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

**Question:** 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?

- A. Attention concentrated on graph neighbours
- B. Uniform attention 1/N over all nodes, so every node gets the same output
- C. Attention proportional to node degree
- D. It cannot run, because graphs have no token order

**Answer:** B. Uniform attention 1/N over all nodes, so every node gets the same output — All queries and keys are equal, so every logit in a row is the same and the softmax is uniform. The edges never enter the computation. That is the default "no structure" setting in the figure: every α is 1/12.

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

- A. The node degrees
- B. 1-WL colours after 3 rounds
- C. The probability that a 3-step random walk returns to its start
- D. The number of edges

**Answer:** C. The probability that a 3-step random walk returns to its start — Both graphs are 2-regular with 6 edges, so degrees and 1-WL colours agree. A 3-step return needs a triangle: (RW³)₀₀ = 0.25 for the triangles and 0 for the hexagon. That is the RWSE entry for t = 3.

**Key points**

- Graph transformers attend over nodes; structure enters only via encodings (LapPE, RWSE), attention biases (SPD, edges) or a parallel MPNN.
- LapPE: rows of the $k$ lowest non-trivial eigenvectors of $I-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: $A_{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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
