Relational Graph Transformers

From GNNs to graph transformers

Graph Neural Networks (GNNs) learn from relational data by treating rows as nodes, foreign keys as edges, and propagating messages along those connections. An enterprise database with customers, transactions, and products becomes a heterogeneous graph where every row is a node and every foreign-key relationship is an edge.

This captures relational structure without manual feature engineering, but deeper multi-hop dependencies expose structural constraints in message passing.

The progression resembles the shift from recurrent neural networks to transformers in natural-language processing. Where recurrent models process text sequentially, transformers let every token attend directly to every other token. Relational Graph Transformers apply that principle to relational data: nodes can interact directly regardless of graph distance.

Why message-passing GNNs hit a wall

Three related issues constrain message-passing GNNs on relational data: the multi-hop bottleneck, over-squashing, and limited expressiveness.

The multi-hop bottleneck

Related entities in a database can be several hops apart. Two transactions from the same customer communicate through the customer node: transaction A -> customer -> transaction B. Each GNN layer extends the receptive field by one hop, so practical 2-to-4-layer GNNs have a limited effective range. Adding layers also increases computation and parameters and can make training less stable.

Over-squashing

Even when a GNN reaches distant nodes, it must compress their information through intermediate nodes into fixed-size vectors. A customer connected to transactions, products, categories, and reviews can become a bottleneck where subtle predictive combinations are lost.

Limited expressiveness

Standard message-passing GNNs are bounded by the 1-Weisfeiler-Leman graph-isomorphism test. Some non-isomorphic graph structures therefore receive the same representation, making particular relational patterns invisible to the model.

From database to graph

Before a Relational Graph Transformer operates on enterprise data, the database is converted into a schema-preserving graph representation.

1. Entity representation

Each row becomes an entity with a primary key, foreign keys, descriptive attributes, and optional timestamps. A transaction row, for example, has its own ID, a foreign key to its customer, attributes such as amount and payment method, and an event timestamp.

2. Schema graph

Each table becomes a node type, while each foreign-key relationship becomes an edge type. The schema graph is the blueprint for the full entity graph.

3. Relational entity graph

Every row becomes a concrete node of its table type, and every foreign-key value creates an edge to the referenced row. The result is a heterogeneous graph that preserves the distinction between node types and relationship types.

Handling multi-modal attributes

The architecture uses specialized encoders before fusing modalities into unified node features.

• Numerical features pass through normalized MLPs.
• Categorical variables use learnable embedding tables.
• Text fields use pre-trained language models such as Sentence-BERT.
• Images use pre-trained CNNs or vision transformers.
• Timestamps can be categorical, continuous, or cyclic features.

PyTorch Frame fuses these modality embeddings into row vectors that serve as initial transformer node features.

The Relational Graph Transformer architecture

A naive transformer over every node in a database graph ignores topology and requires O(n²) attention over millions of nodes. Relational Graph Transformers instead combine graph-aware attention, relation-aware edge encoding, and scalable subgraph sampling.

Graph-aware attention

Attention incorporates relational topology directly. Nodes prioritize local neighbors while retaining the ability to capture long-range dependencies. Graph structure biases attention toward nearby nodes, but the model can learn to prioritize distant signals when useful.

Relation-aware edge encoding

Different relationships carry different semantics. A purchased relationship differs from a reports-to relationship, so the model uses relation-aware attention with specialized weights for edge types.

Scalable subgraph sampling

Enterprise graphs can contain millions of nodes and billions of edges. The source experimental setup samples two hops of 15 neighbors before applying full attention within each local subgraph.

Positional encodings for relational structure

Graphs have no natural linear order, so Relational Graph Transformers use four composable local encodings computed within each sampled subgraph.

Hop encoding identifies distance from the target node. Tree encoding represents parent-child hierarchy. Message-passing encoding refines random embeddings with a lightweight GNN to approximate node2vec-style structural features. Time encoding limits information to earlier events, preventing data leakage while capturing recency.

Benchmark results on RelBench

The source evaluates models on RelBench, a public benchmark for predictive tasks over relational databases. Both GNN and transformer models use two-hop sampling with 15 neighbors, a node dimension of 128, and the same local neighborhoods. The transformer uses four layers, eight attention heads, and a 512-dimensional feed-forward network. LightGBM is an additional baseline using raw entity-table features without graph feature engineering.

The source reports that Graph Transformers outperform the GNN baseline by around 10% and LightGBM by more than 40% across RelBench datasets.

From benchmark to production

Production systems must handle graphs with millions of nodes and billions of edges, low-latency predictions, cold-start entities, and sparse data. Schema-guided sampling focuses on the tables and relationships relevant to a task.

With two-hop sampling at 15 neighbors per hop, the source estimates a bounded subgraph of at most about 240 nodes per prediction. The forward pass scales with the sampling budget rather than the full database size. Cold-start entities can still contribute their own multi-modal attributes before interaction history accumulates.

The source reports these production benefits for Kumo.ai deployments:

• 20x faster time-to-value than traditional feature-engineering and model-training pipelines.
• 30-50% accuracy improvements from deeper relational context.
• 95% less data-preparation effort by operating directly on relational structure.

Implications for foundation models

Relational Graph Transformers provide an architectural basis for foundation models over relational data. The source highlights schema-agnostic attention, multi-modal feature encoding, and composable positional encodings as properties that support transfer across databases and tasks.

The work builds on Relational Deep Learning, PyTorch Frame, and RelBench. The source positions KumoRFM as a model built on this direction, with remaining research questions focused on larger and more diverse pretraining datasets, schemas, and models.