Relational Deep Learning: Databases as Graphs

Chapter 1: Database as Graph

The translation from relational database to graph is mechanical — no choices, no ambiguity. Every table becomes a node type. Every row in a table becomes a node instance. Every foreign key relationship between tables becomes an edge type. Every row-to-row FK reference becomes an edge instance.

A heterogeneous graph where node types correspond to tables and edge types correspond to foreign key relations. This is precisely the input format that heterogeneous GNNs (like HGT, or the RelBench GNN) operate on. The table columns become node features.

Feature Encoding for Tables

Table columns come in several types, each needing a different encoding strategy:

• Numeric: Use the value directly (possibly normalized). Order total → scalar feature.
• Categorical: Embed with a learned embedding table. Product category → 16-dim vector.
• Text: Use a pre-trained text encoder (sentence transformers). Product name → 384-dim sentence embedding, then linearly projected.
• Datetime: Encode as [year, month, day, hour, day-of-week] cyclically. Order timestamp → 5-dim feature.

These features are concatenated into a per-node feature vector. Different node types may have different feature dimensions — the GNN handles this by projecting all types into a common latent dimension at the first layer.

Chapter 2: GNN on Relations — Interactive

Once the database is a graph, the GNN processes it with standard heterogeneous message passing. For each prediction task (e.g., "will this user churn in the next 30 days?"), the GNN computes an embedding for the target node (user) by aggregating information from its neighborhood — orders, products, reviews — up to K hops away.

python (PyG HeteroConv)
import torch
from torch_geometric.nn import HeteroConv, SAGEConv

# Define one conv per edge type
conv = HeteroConv({
    ('user', 'placed', 'order'): SAGEConv((-1, -1), 64),
    ('order', 'contains', 'product'): SAGEConv((-1, -1), 64),
    ('user', 'wrote', 'review'): SAGEConv((-1, -1), 64),
    # ... reverse edges for bidirectional flow
}, aggr='sum')

# Forward pass: x_dict = {node_type: feature_tensor}
x_dict = conv(x_dict, edge_index_dict)
# After K layers, x_dict['user'] = churn prediction embeddings
user_logits = mlp_head(x_dict['user'])  # [N_users, 1]

Chapter 3: Temporal Data

Real relational databases are not static snapshots — they grow over time. Orders accumulate. User behavior evolves. Product reviews arrive daily. A churn prediction model trained naively on historical data will suffer from temporal leakage: using future information to predict the past.

RDL enforces a temporal cutoff for each prediction task. For a target entity at time t*, only nodes and edges with timestamps ≤ t* are included in the graph. This requires:

• Every row in every table must have a timestamp column (or be associated with one through FK chains).
• The graph construction must filter edges based on the cutoff time for each training example.
• Different training examples may have different cutoff times — the graph is resampled for each.

python
def build_temporal_graph(db, target_entity, cutoff_time):
    # Only include events before the prediction cutoff
    filtered_orders = db.orders[db.orders.timestamp <= cutoff_time]
    filtered_reviews = db.reviews[db.reviews.timestamp <= cutoff_time]

    # Encode relative time delta as a node feature
    filtered_orders['days_ago'] = (cutoff_time - filtered_orders.timestamp).dt.days
    filtered_reviews['days_ago'] = (cutoff_time - filtered_reviews.timestamp).dt.days

    # Build heterogeneous graph from filtered tables
    graph = schema_to_graph(db.users, filtered_orders, filtered_reviews, db.products)
    return graph

# Training: each example gets its own temporally-consistent graph
for user, label, cutoff in training_examples:
    g = build_temporal_graph(db, user, cutoff)
    pred = gnn(g)[user]
    loss = bce_loss(pred, label)

Chapter 4: RelBench

RelBench is the benchmark suite introduced alongside the RDL paper. 11 tasks across 5 real-world relational databases, each with standardized train/validation/test splits that respect temporal ordering. No data leakage. No cherry-picked tasks.

The Databases

• rel-amazon — Amazon product reviews. Predict review rating. Nodes: Users, Reviews, Products (10M+ rows).
• rel-stack — Stack Overflow. Predict upvotes, user badges. Nodes: Users, Posts, Tags, Comments (millions of rows).
• rel-hm — H&M fashion retail. Predict article purchases. Nodes: Customers, Articles, Transactions.
• rel-trial — Clinical trials. Predict trial outcome. Nodes: Trials, Sponsors, Conditions, Interventions.
• rel-avito — Russian classifieds. Predict ad click probability. Nodes: Ads, Users, Locations, Categories.

The 11 Tasks

Tasks span classification, regression, and ranking — all evaluated as binary classification (top-k precision) or regression (MAE/RMSE) with temporal validation to prevent leakage:

Chapter 5: vs XGBoost

XGBoost on manually engineered features is the standard baseline for relational prediction tasks. It's fast, interpretable, and often competitive. The RDL paper's key claim: the GNN on the raw graph beats XGBoost on a significant fraction of tasks — and the gap grows with the complexity of the relational structure.

GNN wins in most tasks. XGBoost wins occasionally — specifically on tasks where the relational structure is shallow (entities don't chain deeply) and where the target is mainly predictable from the entity's own historical features.

Chapter 6: Scale

Real production databases have millions of rows per table. A naively constructed graph would have millions of nodes and hundreds of millions of edges — far too large for a full-graph GNN forward pass. How does RDL handle this?

Mini-batch Subgraph Sampling

The same strategy used by GraphSAGE and neighbor sampling GNNs: for each training example (target node), extract a K-hop subgraph by sampling a fixed number of neighbors at each hop. This subgraph is small regardless of global graph size.

For a K=2 GNN with fanout [25, 25]: at hop 1, sample at most 25 neighbors of the target node. At hop 2, sample at most 25 neighbors of each hop-1 node. Maximum subgraph size: 1 + 25 + 625 = 651 nodes — tiny, regardless of whether the graph has 1 million or 100 million total nodes.

Node-Level Partitioning for Very Large Graphs

For graphs too large even for sampling (billion-node graphs), graph partitioning distributes nodes across machines. Each machine owns a partition of nodes and their local edges. During training, cross-partition edges require communication. Libraries like PyG's DistNeighborSampler and dist module implement this for relational settings.

Chapter 7: Connections

Relational Deep Learning connects decades of relational database research to the modern GNN literature. Understanding these connections situates RDL as not a niche contribution but a bridge between two large research communities.