1. Why Transformers on Graphs?
Message passing only mixes local neighborhoods per layer. Distant nodes need many layers → oversmoothing and over-squashing.
Transformers let every node attend to every other node in one layer - global receptive field.
2. Graph Positional Encodings
Unlike sequences, graphs have no built-in order. Transformers need position info injected:
- Laplacian PE: first $k$ eigenvectors of $\mathbf{L}$ as node coordinates
- RWSE: random-walk structural encoding (landing probabilities)
- SignNet: handles eigenvector sign ambiguity
- Shortest-path distance: added to attention bias between $i$ and $j$
3. Graphormer
Paper: Ying et al. - Do Transformers Really Perform Bad for Graph Representation? (2021)
Three structural encodings added to attention:
- Centrality encoding - degree-based bias
- Spatial encoding - shortest-path distance between nodes
- Edge encoding - edge features in attention
4. GPS and Hybrid Models
Paper: Rampášek et al. - Recipe for a General, Powerful, Scalable Graph Transformer (GPS, 2022)
GPS = MPNN + Transformer:
$$\mathbf{h}_i' = \text{MLP}\left(\text{MPNN}(\mathbf{h})_i + \text{Transformer}(\mathbf{h})_i\right)$$Local message passing captures neighborhood structure; global attention fixes over-squashing. State-of-the-art on many OGB benchmarks.
Also see: GRIT, SAN, Exphormer (sparse expander attention).
5. Complexity and Scaling
- Full attention: $O(n^2)$ memory - OK for molecules (~30 atoms), not for million-node social graphs
- Sparse attention: only attend to $k$-hop neighbors + virtual nodes
- Linear attention: kernel tricks (NodeFormer, DIFFormer)
- Subgraph sampling: train on induced subgraphs
6. MPNN vs Transformer
| Choose MPNN | Choose Graph Transformer |
|---|---|
| Sparse, million-node graphs | Small/medium graphs needing long-range |
| Strong local structure (molecules) | Over-squashing in deep MPNN |
| Latency-sensitive production | Benchmark chasing on OGB |