PaperlayerView exact revision on arXiv

Source-linked AI summary

Relational Graph Transformer

Vijay Prakash Dwivedi, Sri Jaladi, Yangyi Shen, Federico López, Charilaos I. Kanatsoulis, Rishi Puri, Matthias Fey, Jure Leskovec

arXiv:2505.10960v2cs.LGcs.AIcs.DB

TL;DR

Relational entity graphs pose challenges for existing GNNs and Graph Transformers because they combine structural and long-range dependencies with heterogeneity, time, and schema constraints. RELGT uses enriched node tokens and local and global attention to model this setting. Across 21 RelBench tasks, it matches or outperforms GNN baselines, with gains up to 18%.

  • Problem

    Existing GNNs have limited structural expressiveness and long-range modeling, while Graph Transformers often do not handle relational graphs’ heterogeneity, temporality, and scale.

    Source: §1 · pp. 1–2

  • Method

    RELGT represents sampled relational-graph nodes with feature, type, hop-distance, time, and local-structure encodings, combining local attention with attention to learnable global tokens.

    Source: §1 · p. 2, §3.1.1 · p. 5

  • Results

    Across 21 RelBench tasks, RELGT improves on the RDL GNN baseline by more than 1% on 10 tasks, is within ±1% on 9, and is lower by more than 1% on 2; its largest reported gain is 18.43% on rel-trial site-success.

    Source: §4.2 · p. 8

  • Takeaways & Limitations

    The results support Graph Transformers as an effective architecture for relational deep learning across the evaluated RelBench tasks.

    Source: §1 · p. 2, §5 · p. 10

Abstract

from arXiv · show

Relational Deep Learning (RDL) is a promising approach for building state-of-the-art predictive models on multi-table relational data by representing it as a heterogeneous temporal graph. However, commonly used Graph Neural Network models suffer from fundamental limitations in capturing complex structural patterns and long-range dependencies that are inherent in relational data. While Graph Transformers have emerged as powerful alternatives to GNNs on general graphs, applying them to relational entity graphs presents unique challenges: (i) Traditional positional encodings fail to generalize to massive, heterogeneous graphs; (ii) existing architectures cannot model the temporal dynamics and schema constraints of relational data; (iii) existing tokenization schemes lose critical structural information. Here we introduce the Relational Graph Transformer (RelGT), the first graph transformer architecture designed specifically for relational tables. RelGT employs a novel multi-element tokenization strategy that decomposes each node into five components (features, type, hop distance, time, and local structure), enabling efficient encoding of heterogeneity, temporality, and topology without expensive precomputation. Our architecture combines local attention over sampled subgraphs with global attention to learnable centroids, incorporating both local and database-wide representations. Across 21 tasks from the RelBench benchmark, RelGT consistently matches or outperforms GNN baselines by up to 18%, establishing Graph Transformers as a powerful architecture for Relational Deep Learning.

1 INTRODUCTION

Relational databases hold complex multi-table data, but conventional pipelines flatten records for prediction and GNNs have limits in structural expressiveness and long-range modeling. RELGT is designed for relational entity graphs, combining enriched node tokens with local and global attention; across 21 RelBench tasks, it matches or outperforms GNN baselines by up to 18%.

1 INTRODUCTION

  • Relational databases commonly require manual feature engineering and flattening, while Relational Deep Learning represents them as entity graphs for end-to-end learning.RDL uses GNNs to learn features from entities and their primary-foreign-key relationships.Source: §1 · p. 1
  • Message-passing GNNs have limited structural expressiveness and long-range reach, constraining how they capture relationships among entities such as transactions and products.In the e-commerce example, products do not directly interact in a two-layer GNN because messages must pass through transactions and customers.Source: §1 · pp. 1–2
  • Existing Graph Transformers often assume non-temporal, homogeneous, small-scale graphs, whereas relational entity graphs are heterogeneous, temporal, and potentially massive.Common positional encodings can require costly precomputation and scale poorly to large, heterogeneous, or dynamic graphs.Source: §1 · p. 2
  • Across 21 RelBench tasks, RELGT matches or outperforms GNN baselines, with gains of up to 18%.The authors also report better results than HGT without added computational cost.Source: §1 · p. 2
  • RELGT encodes each node’s features, type, hop distance, time, and local structure, then combines local subgraph attention with attention to learnable global tokens.The tokenization avoids expensive subgraph- or graph-level precomputation.Source: §1 · p. 2

2 BACKGROUND

Relational Deep Learning represents database entities and their key relationships as heterogeneous temporal graphs, but relational data also impose schema, time, and type constraints. Prior RDL methods and Graph Transformers address parts of the problem; RELGT decomposes relational information into learnable components to jointly handle these constraints without expensive global precomputation.

2.1 RELATIONAL DEEP LEARNING

  • A relational entity graph represents table rows as typed nodes, primary-foreign-key links as edges, and entity timestamps as temporal information.The graph structure is shaped by database schema, and time-aware sampling can prevent future information from leaking into past predictions.Source: §2.1 · p. 3

2.2 RDL METHODS

  • RDL methods include heterogeneous GraphSAGE with temporal-aware neighbor sampling, specialized relational GNNs, and hybrid or retrieval-augmented approaches.These methods address particular challenges or tasks, while the cited approaches do not incorporate broader Graph Transformer advances into RDL.Source: §2.2 · p. 3

2.3 GRAPH TRANSFORMERS

  • Graph Transformers use positional or structural encodings and scalable designs such as sparse attention and neighborhood sampling, but many lack temporal and multi-type mechanisms for relational data.Existing heterogeneous and subgraph-based Transformers do not jointly address relational data’s multimodal attributes, schema constraints, and temporal dynamics.Source: §2.3 · pp. 3–4, §2.4 · p. 4

2.4 ADDRESSING CHALLENGES

  • RELGT decomposes relational-graph information into specialized components that can be learned and composed, addressing heterogeneity, temporality, and schema-defined structure without expensive global precomputation.Source: §2.4 · p. 4

3 RELGT: RELATIONAL GRAPH TRANSFORMER

RELGT replaces a single positional encoding with five token elements for relational data, then processes sampled local context alongside global representations. Its Transformer combines local structural detail with database-wide context for downstream prediction.

3.1 TOKENIZATION

  • A single positional encoding is computationally inefficient for relational graphs and risks losing heterogeneity, temporal dynamics, and schema-defined structure.Standard encodings would need modification for multiple node types and time; global precomputation is prohibitively expensive at database scale.Source: §3.1 · pp. 4–5

3.1.1 PROPOSED APPROACH

  • For each seed, RELGT samples K neighboring nodes within two hops, excluding nodes timestamped later than the seed to prevent temporal leakage.When fewer than K neighbors are available, randomly selected fallback tokens maintain fixed size K.Source: §3.1.1 · p. 5
  • Each token combines node features, type, relative hop distance, relative time, and a lightweight-GNN structural encoding.The encodings are concatenated and mixed into a unified representation; random GNN features are resampled each training step to approximately preserve permutation equivariance while retaining expressivity gains.Source: §3.1.1 · pp. 5–6

3.2 TRANSFORMER NETWORK

  • The local module applies all-pair self-attention among the seed and its K tokens, capturing fine-grained relationships defined by the database schema.Its broader structural coverage contrasts with baseline GNN message passing.Source: §3.2 · pp. 6–7
  • The global module attends from each seed to B graph-wide centroids, updated during training with EMA K-Means on mini-batch seed features.The final node representation combines local and global embeddings.Source: §3.2 · p. 7
  • A task-specific prediction head consumes the combined seed representation, and end-to-end training uses task-specific loss functions.The architecture pairs sampled local tokens with global context.Source: §3.2 · pp. 6–7

4 EXPERIMENTS

Across RelBench entity classification and regression tasks, RELGT mostly matches or exceeds the RDL GNN baseline, while ablations show that subgraph positional encoding is consistently important and the value of global attention and other encodings varies by task. The experiments also compare HGT variants and local-context sizes, with runtime costs and tuning choices shaping those comparisons.

4 EXPERIMENTS

  • Evaluation covers 21 entity classification and regression tasks from RelBench, excluding recommendation tasks.RelBench has 7 datasets and 30 total tasks; recommendation tasks are excluded because they require specific considerations such as target-node identification or pair-wise learning architectures.Source: §4 · pp. 7–8, §4.2 · p. 8

4.1 SETUP AND BASELINES

  • RELGT is implemented in the RDL pipeline with 10–20M parameters, and the authors do not conduct exhaustive hyperparameter tuning.They use K = 300 local neighbors and B = 4096 global-centroid tokens; tasks with more than 1M training nodes use four layers due to compute budgets.Source: §4.1 · p. 8

4.2 RESULTS AND DISCUSSION

  • RELGT improves on the RDL baseline in 10 tasks, matches it within ±1% in 9, and trails by more than 1% in 2.The largest reported gains are 18.43% on rel-trial site-success, 15.85% on rel-avito ad-ctr, and 10.56% on rel-f1 driver-top3; rel-stack user-badge is 3.94% lower.Source: §4.2 · p. 8, Table 1 · p. 8
  • Removing subgraph GNN positional encoding degrades performance across all tasks, indicating its role in encoding local structure and disambiguating parent-child relationships.The authors illustrate that products belonging to specific transactions are not effectively captured without this component, even when other encodings remain.Source: §4.2 · p. 9, Table 2 · p. 9
  • Removing global attention to learnable centroids yields task-dependent outcomes, including a 19.08% drop on rel-trial site-success and a 7.79% gain on rel-avito user-clicks.The authors interpret these mixed outcomes as showing that global context can add information beyond local neighborhoods for some tasks, but may add noise for others.Source: §4.2 · p. 9, Table 2 · p. 9
  • Removing node-type, hop-distance, or relative-time encodings has mixed effects, while the full model performs best when averaged across tasks.The authors note that current temporal encodings may add noise for some tasks and suggest task-specific tuning or more effective temporal encodings.Source: §4.2 · p. 9, Table 2 · p. 9
  • HGT underperforms the RDL HeteroGNN on most tasks, while adding Laplacian positional encodings improves HGT on 8 of 21 tasks and increases epoch runtime.The reported precomputation slowdowns range from 1.8× to 8.62×; Figure 4’s left panel separates base HGT runtime from the additional precomputation time.Source: §4.2 · p. 9, Figure 4 · p. 10
  • K = 300 generally performs best, but the preferred local context size varies by task, with rel-avito ad-ctr benefiting from a larger window and rel-trial study-outcome from a smaller one.The Figure 4 ablation compares K = 100 and K = 500 performance relative to K = 300.Source: §4.2 · pp. 9–10, Figure 4 · p. 10

5 CONCLUSION

The conclusion presents RELGT as a transformer designed for relational entity graphs, combining fine-grained node tokens with local and global attention. Its RelBench experiments support the role of subgraph positional encodings and the broader use of Graph Transformers for relational deep learning.

5 CONCLUSION

  • RELGT combines multi-element tokens enriched with graph context, local attention over sampled subgraphs, and global attention to learnable centroids.The token elements represent node features, type, hop distance, time, and local structure.Source: §5 · p. 10
  • Experiments on RelBench show that RELGT consistently outperforms GNN and Graph Transformer baselines across multiple tasks.Source: §5 · p. 10
  • The analysis highlights subgraph-based positional encodings as a lightweight and effective alternative to traditional graph positional encodings.The authors state that the work opens avenues for advancing and scaling relational architectures toward foundation models.Source: §5 · p. 10

A.1 BENCHMARK DETAILS

The benchmark evaluation draws on seven diverse RelBench datasets and focuses on entity classification and regression. The appendix describes dataset scale and explains why recommendation tasks are outside this evaluation.

A.1 BENCHMARK DETAILS

  • RelBench comprises 7 datasets spanning domains including e-commerce, clinical records, social networks, and sports, with 47M training records in total.Individual prediction-task training sets range from 1.3K to 5.4M records.Source: §A.1 · p. 15
  • The benchmark contains 30 tasks across entity classification, entity regression, and recommendation, while this evaluation uses 21 classification and regression tasks.Source: §A.1 · p. 15
  • Recommendation tasks are excluded because they require considerations such as target-node identification or pair-wise learning, and using RELGT trivially in RDL is sub-optimal.Source: §A.1 · p. 15

A.1.1 DATASETS

The appendix describes seven relational datasets drawn from commerce, social platforms, motorsport, and clinical research. Their records combine entity attributes and interactions relevant to each domain.

A.1.1 DATASETS

  • The rel-amazon, rel-avito, and rel-hm datasets cover e-commerce products, users, reviews, searches, advertisements, customer demographics, and purchase histories.Source: §A.1.1 · pp. 15–16
  • The rel-event, rel-f1, rel-stack, and rel-trial datasets describe social planning, Formula 1 records, Stack Exchange activity, and clinical trial protocols and outcomes.Source: §A.1.1 · pp. 15–16

A.1.2 TASKS

The RelBench tasks cover entity classification and regression across relational datasets, with predictions spanning user, product, event, sports, and clinical outcomes.

A.1.2 TASKS

  • RelBench defines entity classification and regression tasks across its datasets.The listed tasks include forecasts of engagement, churn, sales, lifetime value, event participation, sports outcomes, and clinical trial outcomes.Source: §A.1.2 · p. 16
  • rel-amazon tasks predict user or product churn and user or item lifetime value over the next three months.Lifetime-value tasks estimate the monetary value of purchases and reviews.Source: §A.1.2 · p. 16
  • rel-avito tasks predict user ad visits, ad clicks, and ad interaction probability within four days.The ad click-through task assumes the ad receives an interaction within that period.Source: §A.1.2 · p. 16
  • Event tasks include attendance and repeat-RSVP predictions, alongside predictions that users will ignore more than two invitations.The listed RSVP and invitation outcomes are for the upcoming seven days.Source: §A.1.2 · p. 16
  • Other tasks cover driver race outcomes, customer churn and product sales, community participation, and clinical trial outcomes.These include driver finish and top-three outcomes, user churn and item sales, user badges and post votes, trial outcomes, adverse effects, and site success.Source: §A.1.2 · pp. 16–17

A.2 NODE INITIALIZATION FOR SUBGRAPH GNN PE IN RELGT

RELGT’s Subgraph GNN PE encodes local subgraph structure using a lightweight GNN, with randomly initialized node features; Laplacian initialization performs worse and adds computation.

A.2 NODE INITIALIZATION FOR SUBGRAPH GNN PE IN RELGT

  • The local-structure encoding targets parent-child relationships that other token elements do not represent.Source: §A.2 · p. 17
  • The Subgraph GNN PE applies a lightweight GNN to the sampled-subgraph adjacency matrix and random node features to produce each node’s encoding.RELGT sets the initial random-feature dimension to dinit = 1.Source: §A.2 · p. 17
  • ZLapPE consistently underperforms Zrandom and adds 1.02×–3.38× computational overhead across eight selected tasks.The study uses a positional-encoding dimension of 4 for the Laplacian alternative.Source: §A.2 · p. 17

A.3 LEARNABLE SPATIO-TEMPORAL PE

The learnable spatio-temporal PE repurposes the Subgraph GNN PE using relative time, then mixes its output with feature, type, and hop encodings; the tested replacement consistently lowers performance.

A.3 LEARNABLE SPATIO-TEMPORAL PE

  • The alternative uses relative time to initialize nodes in a repurposed Subgraph GNN PE, making it a learnable spatio-temporal encoding.Relative time is the temporal difference between neighbor node vj and seed node vi.Source: §A.3 · pp. 17–18
  • The token concatenates feature, type, hop-distance, and spatio-temporal encodings, then applies a learnable matrix to mix them.The matrix O has shape 4d × d.Source: §A.3 · p. 18
  • Replacing the temporal and Subgraph GNN PE encoders with Spatio-Temporal PE consistently lowers performance across three regression and five classification tasks.Table 5 reports the comparison with RELGT Full.Source: §A.3 · p. 18, Table 5 · p. 18

A.4 COMPARISON WITH GRIFFIN

The appendix compares RELGT with Griffin and HGT variants, details tuned configurations and component studies, and reports RELGT’s attention complexity and compute environment.

A.4 COMPARISON WITH GRIFFIN

  • RELGT outperforms Griffin on 8 of 10 RelBench entity-classification tasks, with relative gains of up to 8.41%.Griffin is finetuned per task using the same procedure as RELGT.Source: §A.4 · pp. 18–19

A.5 HGT BASELINE

  • HGT+PE adds Laplacian-encoding precomputation overhead and requires more epoch training time than HGT across datasets.The appendix reports the comparison in Figure 5 and Table 7.Source: §A.5 · p. 19, Figure 5 · p. 19, Table 7 · p. 20

A.6 DETAILED RESULTS

A.7 COMPUTATIONAL COMPLEXITY AND RESOURCE INFORMATION.

  • RELGT has per-node complexity O(K^2 · d) for local attention and O(K · B · d) for global attention, and experiments ran on an NVIDIA A100 server with eight GPU nodes.K is local context size, B the number of global centroids, and d the hidden dimension.Source: §A.7 · p. 20

Related papers

Loading 2505.10960v2…