Graph Transformers
Why use transformers on graphs instead of MPNN?
MPNN has local receptive field per layer - distant nodes need many layers, causing oversmoothing and over-squashing. Transformers attend globally in one layer. Cost: $O(n^2)$ vs $O(|E|)$.
What positional encodings do graph transformers need?
Graphs have no canonical order. Inject structure via Laplacian eigenvectors, random-walk structural encoding (RWSE), shortest-path distance biases, or centrality encodings (Graphormer).
What is Graphormer?
Transformer with three structural biases: centrality encoding (degree), spatial encoding (shortest-path distance), edge encoding (edge features in attention). Showed transformers can beat MPNNs on molecules with right encodings.
What is the GPS architecture?
General Powerful Scalable Graph Transformer = parallel MPNN branch (local) + Transformer branch (global), combined with MLP. Best of both. State-of-the-art on many OGB benchmarks.
When choose MPNN over graph transformer?
Sparse million-node graphs (cost), latency-sensitive production, strong local structure (molecules with few layers). Transformers win when over-squashing limits MPNN and graph is small/medium.