Introduction to Graph Transformers
Graph transformers combine the flexibility of transformer attention with the structure of graphs. This guide explains why that combination matters, the graph-specific mechanisms it requires, and how it leads to relational graph transformers.
Originally published: April 2025
Authors: Federico Lopez, Matthias Fey, and Jure Leskovec
Graphs are everywhere
Graphs are one of the most general and expressive data structures in computer science. A graph consists of nodes (entities) and edges (relationships between entities). This simple abstraction captures an enormous range of real-world systems.
Social networks model people as nodes and friendships as edges. Molecular graphs represent atoms as nodes and chemical bonds as edges. Financial transaction networks connect accounts through payment flows. Knowledge graphs link concepts through typed relationships. Relational databases, when viewed through their foreign-key structure, form heterogeneous graphs connecting rows across tables.
What makes graphs powerful is that the structure of connections carries information. In a social network, a person’s position within a community can be as predictive as their profile attributes. In a molecular graph, the arrangement of bonds determines a compound’s properties. In a fraud network, tightly connected clusters of accounts can reveal suspicious patterns that no individual transaction would expose.
Analogy: Consider a city’s road network. Each intersection is a node and each road is an edge. The topology shows which neighborhoods are connected, where bottlenecks exist, and how traffic flows. A spreadsheet of intersections alone cannot capture this information.
Unlike images, which are regular pixel grids, or text, which is an ordered sequence of tokens, graphs have no fixed node ordering, have variable neighborhood sizes, and have complex topological structure. Standard deep-learning architectures need significant adaptation to learn effectively from them.
Graph learning must account for both entity attributes and relationship structure. Node features alone are insufficient because topology itself carries signal.
How transformers work: the attention mechanism
Transformers were originally designed for sequential data. Their core innovation is self-attention, which lets each input element dynamically weigh the importance of every other element.
Self-attention in four steps
The Query represents what each token is looking for, the Key represents what it offers, and the Value is the information passed along.
The attention operation is softmax(QKᵀ / √dₖ)V, where softmax makes the weights a probability distribution.
Multiple attention heads run in parallel so different heads can learn different relationship patterns. One can focus on syntax, another on semantic similarity, and another on positional proximity.
Analogy: Multi-head attention is a panel of analysts reviewing a document. Each uses a different lens, and the combined analysis is richer than any single view.
Why transformers excel on sequences
Attention lets token 1 directly attend to token 500 in one step instead of propagating information through 499 intermediate states. This supports parallel computation and direct long-range dependencies. For sequences, learned or sinusoidal positional encodings tell the model where each token occurs in the natural linear order.
Self-attention assumes a fully connected input with a natural ordering. Graphs have neither property by default.
Why standard transformers struggle with graphs
Standard transformers treat their input as a fully connected set of tokens: every token can attend to every other token. Applied directly to graph data, this creates three fundamental problems.
No notion of graph connectivity
Attention does not know which nodes are connected by edges. For sparse graphs, this forces the model to spend capacity learning that most node pairs should receive little attention instead of receiving that structural bias from the architecture.
No meaningful positional encoding
Sequential positions assume a linear order. Graphs have no canonical ordering: arbitrarily assigning node numbers does not tell the model whether two nodes are adjacent or disconnected.
No edge feature incorporation
Standard transformers have no native place for edge features. Bond types in molecules, relationship types in knowledge graphs, and foreign-key types in relational databases often carry essential semantics.
Full self-attention is also expensive. It is manageable for a molecule with tens of atoms but prohibitive for social networks with millions of nodes or relational databases with billions of rows.
Graph transformers address graph connectivity, graph-aware position, and edge features while retaining attention’s ability to model long-range relationships.
What are graph transformers?
Graph transformers adapt the transformer architecture to graph-structured data. They integrate self-attention with topology, allowing nodes to attend across the graph while respecting or being informed by structural properties.
How attention becomes graph-aware
The simplest approach restricts a node’s attention to directly connected neighbors. This supplies a locality bias and reduces computation from O(N²) to O(E), where E is the number of edges.
A more flexible approach computes attention broadly but adds a bias based on graph distance. Connected nodes can receive a positive bias and distant nodes a negative one, enabling a balance of local detail and global context. Some architectures combine local neighborhood attention with global attention through selected anchor nodes.
Edge features in attention
Graph transformers can condition attention weights on the features of the edge connecting a query node and key node.
This matters in heterogeneous graphs.
A single versus double molecular bond changes how information should flow, just as a purchased relationship means something different from a reviewed relationship in a relational database.
The three central innovations are topology-aware attention, graph-aware positional encodings, and explicit edge-feature integration.
Positional and structural encodings
Graphs do not have an inherent ordering, so graph transformers need an explicit way to represent position and structure. Positional encodings answer “Where am I in the graph?” Structural encodings answer “What does my neighborhood look like?”
Positional encodings: where am I?
Positional encodings describe a node’s location relative to others, such as whether it is central, peripheral, in a dense cluster, or bridges communities.
- Local, node-level: Distance to a cluster centroid or reachability through m-step random walks.
- Global, node-level: Laplacian or adjacency-matrix eigenvectors, distance to the graph centroid, and connected-component identifiers.
- Relative, edge-level: Pairwise distances from heat kernels, random-walk metrics, or eigenvector gradients.
Analogy: Positional encodings are GPS coordinates for nodes. Sequence positions are simple indices, but graph coordinates must describe how a node sits in the topology. Laplacian eigenvectors are a spectral form of GPS for a graph’s geometry.
Structural encodings: what role do I play?
Structural encodings describe local topology independently of global position. Nodes in different parts of a graph can share a role, such as hub, leaf, or the center of triangles.
- Local, node-level: Node degree, random-walk self-return probabilities, and counts of triangles, rings, or cliques.
- Global, graph-level: Eigenvalue spectra, graph diameter, connected-component count, and average degree.
- Relative, edge-level: Shared substructures and neighborhood overlap.
Graph position is not unique: Laplacian eigenvectors have sign ambiguity, and graphs have no canonical symmetry-breaking order. Current methods address this with sign-invariant networks or learned alignment across graphs.
Combining positional and structural encoding gives a graph transformer both a sense of location and a sense of role.
Graph transformers vs. GNNs
GNNs and graph transformers both learn from graph-structured data, but information flows differently. GNNs aggregate information from direct neighbors at each layer, so information from k hops away needs k rounds of message passing.
This creates two common GNN limitations:
- Over-smoothing: Repeated aggregation can make node representations converge, which is why many GNNs stay shallow.
- Over-squashing: Distant information is compressed through fixed-size intermediate representations and can be lost.
Graph transformers use self-attention so a node can directly attend to another node within its attention scope, without a chain of intermediate propagation.
In practice, the approaches are complementary. Many strong architectures pair local GNN message passing with transformer-style global attention: local layers capture detailed structure efficiently and attention layers capture long-range context.
Analogy: A GNN is a game of telephone, where information moves neighbor by neighbor. A graph transformer is a conference call, where participants can communicate directly but the call becomes unwieldy at scale. Hybrid architectures use both modes.
Real-world graphs are often heterogeneous. Both GNNs and graph transformers have type-aware variants that learn different attention and aggregation behavior for different node and edge types.
Applications: from molecules to relational databases
Molecular property prediction and drug discovery
Molecules are graphs of atoms and bonds. Graph transformers can capture long-range atomic interactions beyond the few layers that message-passing GNNs commonly use. The same benefit applies to protein folding, where distant amino acids can interact in the final 3D structure.
Fraud detection in financial networks
Transaction graphs link accounts, merchants, and payment events. Attention across structurally relevant distant nodes can expose fraud rings, rapid transfer sequences, and bridges between suspicious clusters without the information bottlenecks of multi-hop message passing.
Social networks, recommendations, and knowledge graphs
For social recommendations, models need both local interactions and a user’s broader community position. For knowledge-graph completion and question answering, attention can support multi-hop reasoning across entity-relation-entity triples.
Relational deep learning
Enterprise databases form large, heterogeneous, temporal graphs when rows are nodes and foreign keys are edges. Learning directly from this structure preserves cross-table relationships, temporal patterns, and multi-hop context that are discarded when data is flattened into feature vectors. The Relational Deep Learning framework formalizes this approach, and RelBench evaluates it on enterprise prediction tasks.
Scaling challenges and the road ahead
Full graph attention requires O(N²) computation, which makes it impractical for large graphs. Several strategies reduce this cost:
- Local attention: Restrict attention to a k-hop neighborhood for O(E)-like behavior.
- Global anchor nodes: Let all nodes attend to a small, representative set.
- Low-rank approximation: Use methods such as Linformer or Performer to approximate the attention matrix.
- Routing transformers: Learn a sparse, relevant attention pattern dynamically.
- Subgraph sampling: Train on manageable node, neighborhood, partition, or cluster subgraphs.
The road to relational graph transformers
Enterprise databases combine multiple node types, typed foreign-key relationships, rich features, and temporal dynamics. Effective graph transformers for this setting need heterogeneous graph-aware attention, relational positional and structural encodings, edge-feature integration, and scalable attention.
This progression leads to relational graph transformers, the architectural foundation for foundation models that learn directly from interconnected enterprise data. For the next step, see KumoRFM: A Relational Foundation Model.
Graph transformers bridge powerful attention and graph structure. Sparse attention, positional encoding, and subgraph sampling make the approach practical for relational data at scale.