📋 KEY INSIGHTS
- Graph Transformers combine the global self-attention mechanism of Transformers with the inductive bias of Graph Neural Networks, addressing a fundamental limitation of standard message-passing GNNs: the over-squashing problem. In deep GNNs, information from distant nodes must pass through many intermediate nodes, and each message-passing step aggregates over all neighbours — causing information from long-range dependencies to be compressed (squashed) into a fixed-size node representation. Transformers naturally avoid over-squashing by computing pairwise attention between all node pairs in a single layer, but they require positional encodings to inform the model about graph structure (since the attention mechanism is permutation-equivariant and treats all nodes symmetrically without structural context). The central design challenge for Graph Transformers is therefore: how to inject meaningful graph structural information into the attention mechanism without sacrificing the global receptive field that makes Transformers expressive.
- Graphormer (Ying et al., NeurIPS 2021) won the OGB-LSC molecular property prediction competition at NeurIPS 2021, establishing Graph Transformers as state-of-the-art for molecular ML. Graphormer encodes graph structure via three bias terms added to the standard attention logits: (1) centrality encoding — node degree (in-degree and out-degree) as additional node features, encoding graph centrality; (2) spatial encoding — a learnable scalar bias b_φ(d(v_i, v_j)) added to the attention logit between nodes i and j, where d(v_i, v_j) is the shortest-path distance, so nodes that are topologically close get higher attention; (3) edge encoding — a bias term computed from the edge features along the shortest path between nodes i and j, injecting bond-type information into attention. These three structural encodings together give Graphormer complete knowledge of graph topology within the attention mechanism.
- Positional encodings for graphs are more challenging than for sequences (where sinusoidal or learned position embeddings directly encode token position) because graphs have no canonical ordering — the same graph can be represented with any node permutation. The main approaches: (1) Laplacian eigenvector positional encodings (LapPE) — the k smallest eigenvectors of the graph Laplacian form a k-dimensional positional embedding for each node; they are unique up to sign (each eigenvector can be flipped), requiring sign-invariant handling; LapPE captures global graph structure and connectivity; (2) Random Walk positional encodings (RWPE) — the k-step random walk landing probabilities from each node to itself encode the local graph structure; they are deterministic and permutation-equivariant; RWPE captures local topology; (3) Structural encodings (SVD of adjacency, graph substructure counts) — encoding whether a node participates in triangles, 4-cycles, or other motifs provides subgraph structural information beyond pairwise distances.
- GPS (General, Powerful, Scalable, Rampášek et al., NeurIPS 2022) introduces a unifying framework for Graph Transformers as a combination of a local message-passing GNN layer and a global attention layer: h_v^{l+1} = MLP(MPNN(h^l)_v + Attn(h^l)_v). The MPNN layer aggregates local neighbourhood information (1-hop neighbours) while the Attention layer captures global graph structure via full self-attention with positional encodings. GPS supports plug-in choices of MPNN type (GIN, GatedGCN, GINE) and attention type (Transformer, Performer, Bigbird) and achieves state-of-the-art on 12 of 16 tasks in the Long Range Graph Benchmark (LRGB), which specifically tests models on tasks requiring long-range dependencies across the graph. GPS is the most adopted Graph Transformer architecture for practitioners due to its modularity and strong benchmark performance.
- Molecular property prediction is the killer application for Graph Transformers: molecules are naturally represented as graphs (atoms as nodes, bonds as edges), bond-type edge features are well-defined, and many molecular properties (bandgap, binding affinity, reaction yield) depend on long-range electronic effects that over-squash in standard MPNN models. The OGB-LSC PCQM4Mv2 benchmark (3.8 million molecules, predicting HOMO-LUMO gap from SMILES) is the standard large-scale molecular Graph Transformer benchmark: Graphormer, GEM, Uni-Mol, and GPS++ set state-of-the-art results here. The connection to our drug discovery guide is direct: Graph Transformers applied to molecular property prediction power virtual screening pipelines for lead optimisation — predicting binding affinity, ADMET properties, and toxicity from molecular graphs before expensive wet-lab synthesis.
- Scaling Graph Transformers to large graphs is the key computational challenge: full self-attention is O(n^2) in the number of nodes, making it infeasible for large social networks, knowledge graphs, or protein interaction networks with millions of nodes. The main approaches: (1) sparse attention — restrict attention to k-hop neighbours and a set of random global tokens (Bigbird graph, Exphormer); (2) linear attention approximations — Performer’s random feature kernel approximation reduces attention to O(n), enabling full-graph attention at scale; (3) graph clustering (Cluster-GCN partitioning) — partition the graph into subgraphs small enough for full attention and train on subgraphs with cross-subgraph edges sampled. The connection to our Graph Attention Networks guide is direct: standard GAT is the message-passing baseline that Graph Transformers extend, and understanding GAT’s neighbourhood-restricted attention is essential for appreciating why global attention (and its computational cost) is a meaningful upgrade for tasks with long-range graph dependencies.
Graph Neural Networks have achieved remarkable results on molecular property prediction, social network analysis, knowledge graph completion, and combinatorial optimisation problems — but their message-passing architecture imposes a fundamental constraint: each layer aggregates information only from immediate neighbours, requiring many layers to propagate information across distant parts of the graph, and causing the over-squashing problem at depth. Graph Transformers address this by applying self-attention across all node pairs simultaneously, giving every node global context in a single layer. This guide covers the full Graph Transformer landscape: positional encodings for graphs (Laplacian eigenvectors, random walk, structural encodings), Graphormer and its structural bias terms, the GPS unifying framework, Exphormer for scalable sparse attention, molecular property prediction benchmarks, and connections to downstream applications in drug discovery and materials science.
Positional Encodings, Structural Biases and Graphormer
The standard Transformer’s self-attention mechanism treats all input tokens symmetrically — without positional information it cannot distinguish node i from node j in a graph. For sequences, sinusoidal position embeddings break this symmetry by assigning a unique positional code to each sequence position. For graphs, defining positional encodings is fundamentally harder because graphs have no canonical ordering: the same molecular graph can be represented with any assignment of indices to atoms, and the positional encoding must be invariant (or equivariant) to this permutation. Laplacian eigenvector positional encodings (LapPE, Dwivedi & Bresson, 2021) use the k eigenvectors corresponding to the k smallest non-zero eigenvalues of the graph Laplacian L = D − A as positional embeddings. These eigenvectors capture global graph structure: on a path graph they recover sinusoidal functions analogous to Transformer positional embeddings, and on more complex graphs they encode connectivity and cluster structure. The sign ambiguity (each eigenvector can be multiplied by -1 without changing the eigenvalue) requires handling: SignNet (Lim et al., 2022) uses a sign-invariant neural network architecture to process LapPE robustly. Random Walk positional encodings (RWPE, Dwivedi et al., 2022) use the k-step random walk transition probabilities from each node back to itself as a structural fingerprint — the diagonal elements of P^1, P^2, …, P^k (where P is the random walk transition matrix). RWPE is deterministic and permutation-equivariant (unlike LapPE, which requires eigenvector sign handling) and strongly captures local topology: nodes in dense clusters have high k-step return probabilities, while bridge nodes between clusters have lower return probabilities. The connection to our GNN guide is direct: Laplacian eigenvectors are the spectral GNN perspective on graph structure, and RWPE connects to the random walk view of graph diffusion — both are structural encodings that complement the spatial (message-passing) view of graph neural networks. Graphormer (Ying et al., 2021) was the first Graph Transformer to demonstrate decisive state-of-the-art results at scale (OGB-LSC PCQM4Mv2: 1st place, NeurIPS 2021 competition). Its three structural bias terms inject topology into attention without modifying the Transformer architecture: the centrality encoding embeds node degree as a learnable bias per degree value (capturing graph centrality — hub nodes that connect many others get a distinct embedding); the spatial encoding adds a learnable scalar b_φ(SPD(i,j)) to the attention logit between nodes i and j based on their shortest-path distance (topologically close nodes attend more strongly); the edge encoding adds a bias term from edge features along the shortest path between i and j (injecting bond type, stereochemistry, and aromaticity information from molecular edges). The key insight is that these structural biases are differentiable and learned end-to-end: the model learns which structural patterns are important for each prediction task from data, rather than relying on hand-crafted structural features. The connection to our drug discovery guide is direct: Graphormer was trained on PCQM4Mv2 (quantum chemistry predictions from SMILES) and then fine-tuned for ADMET property prediction, 3D conformation generation, and binding affinity prediction — the core tasks in the drug discovery pipeline described there.
| Model | Structural Encoding | Attention Type | Key Task | Benchmark |
|---|---|---|---|---|
| Graphormer | Centrality, spatial, edge bias | Full O(n^2) | Molecular properties | PCQM4Mv2 SOTA 2021 |
| GT (Graph Transformer) | LapPE | Full O(n^2) | Graph classification | ZINC, CSL |
| SAN | Learnable LapPE | Full + k-hop mask | Multi-task | ZINC, LRGB |
| GPS | LapPE + RWPE | MPNN + global Attn | General SOTA | 12/16 LRGB tasks |
| Exphormer | RWPE | Sparse virtual nodes | Large graphs | LRGB scalable SOTA |
GPS Framework, Scalable Attention and Molecular Applications
The GPS (General, Powerful, Scalable) framework (Rampášek et al., NeurIPS 2022) makes the case that the best Graph Transformer is not pure global attention but a hybrid: combine a local MPNN layer (which efficiently encodes neighbourhood structure via message passing) with a global attention layer (which captures long-range dependencies across the entire graph) in each GPS layer. The GPS layer: z_v = Norm(h_v + Dropout(MPNN(h^l)_v)); h_v^{l+1} = Norm(z_v + Dropout(MHA(z)_v + FFN(MHA(z)_v))), where MPNN is a message-passing layer (GIN, GatedGCN) and MHA is multi-head attention over all graph nodes. This architecture achieves the best of both worlds: the MPNN captures local structure with O(n+m) complexity (n nodes, m edges), and the Transformer captures global context with O(n^2) complexity — but since most graph tasks have moderate n (hundreds of nodes per graph), the O(n^2) global attention is affordable. GPS achieves state-of-the-art on LRGB (Long Range Graph Benchmark) tasks including Peptides-func (protein function prediction), Peptides-struct (structural properties), PascalVOC-SP (superpixel graph node classification), and COCO-SP. The Long Range Graph Benchmark explicitly tests tasks where the relevant signal is non-locally distributed across the graph — exactly the setting where MPNN over-squashing is most damaging and global attention provides the largest benefit. Exphormer (Shirzad et al., ICML 2023) addresses the O(n^2) scalability bottleneck: instead of full attention, Exphormer uses sparse attention patterns combining local neighbourhood attention (k-hop), global virtual node attention (a set of learnable virtual nodes that attend to all graph nodes, compressing global context into O(n) tokens), and expander graph edges (a random regular graph overlay providing short-cut connections for long-range message passing at O(n) edge cost). Exphormer achieves GPS-quality performance on LRGB while scaling to large graphs (100K+ nodes) that full attention models cannot handle. The connection to our foundation models guide is direct: Uni-Mol (a Transformer trained on 209 million molecular conformations with 3D atom coordinates and pairwise distances as positional encodings) and MolBERT (BERT pre-training on SMILES strings) are molecular foundation models that use Graph Transformer-inspired architectures for pre-training on large unlabelled molecular databases, then fine-tuned for property prediction — mirroring the BERT pre-train/fine-tune paradigm for molecular graphs. The connection to our materials science guide is direct: Graphormer and GPS applied to crystal graphs achieve state-of-the-art on MatBench property prediction tasks, outperforming CGCNN and ALIGNN on tasks requiring long-range interatomic interactions (such as predicting phonon properties or elastic tensors that depend on lattice-scale collective behaviour).
✦ SUMMARIZE THIS ARTICLE WITH AI
Graph Neural Networks (message-passing framework; GIN; over-smoothing vs. over-squashing) are in our GNN guide. Graph Attention Networks (GAT, GraphSAGE, attention pooling) are in our Graph Attention Networks guide. ML for drug discovery (Graphormer for ADMET and binding affinity) is in our Drug Discovery guide. ML for materials science (Graph Transformers on crystal graphs) is in our Materials Science guide. Foundation models (Uni-Mol, MolBERT molecular pre-training) are in our Foundation Models guide. Transformers (self-attention, positional encoding, the architecture Graph Transformers adapt) are in our Transformers guide. Geometric deep learning (equivariant GNNs for 3D molecular geometry) is in our Geometric Deep Learning guide.



