Relational deep learning treats a multi-table database as a graph. Rows become nodes, and foreign-key links (a column in one row that points to a row in another table) become edges. A graph neural network then learns predictions by passing messages along those links. This works well, but it slows down on the entities that matter most in practice. A customer with ten thousand reviews, or a product bought a million times, is a "hub." A hub either gets its neighbors randomly sampled, so its history is only partly seen, or it blows up the computation. Sampling also has to respect time: a prediction made at a given moment may only use rows that existed before that moment. So a separate neighborhood has to be drawn for every training example at every cutoff date.
We propose to precompute these joins once, in a form that answers every cutoff time exactly. For each foreign-key relation, we sort the linked rows by target entity and then by timestamp. We store running sums of their encoded features at that sorted position. Any aggregate over "all of this customer's reviews before time $t$", or "within the last 30 days before $t$", then costs two binary searches and one subtraction, however large the hub. Storing running sums at every edge would cost memory linear in the number of links times the feature width, which is the metadata wall. We therefore keep them only at sparse checkpoints and trade a tunable amount of scanning for memory. The result is an exact, leakage-free, sampling-free first stage for relational learning. It is a time-aware analogue of precomputed graph diffusion, and it needs no per-example feature tables.
Core Claim
Hub-heavy relational prediction tasks lose accuracy under neighbor sampling. Exact, time-correct aggregation over the full history of each relation recovers that accuracy. A checkpointed prefix-sum layout makes this exact aggregation cheaper in memory and preprocessing time than the two usual alternatives: materializing join-aggregate features per training example, or storing precomputed features per time snapshot. The new object is the temporal prefix-aggregate store and its composition across two schema hops. The claim is testable: on RelBench, it should match or beat sampled relational GNNs on the tasks where the target entities have high degree, while cutting training cost.
Where this sits
Three lines of work motivate the gap. Relational Deep Learning and RelBench cast databases as temporal heterogeneous graphs and treat message passing as a learnable JOIN plus GROUP BY. Their pilot relies on standard mini-batch neighbor sampling, and they leave scaling to large databases open. Relatron shows that join-and-aggregate feature synthesis (Deep Feature Synthesis, DFS) often competes with relational GNNs, especially on smaller or homophilous tasks. That suggests much of the useful signal is aggregate-shaped, which is exactly what we precompute. SIGN supplies the method template: precompute several fixed linear aggregation operators, then train a cheap model on the results. SIGN's operators are static, though. On a temporal database they would either leak future rows or require one precomputation per snapshot, and its storage grows with the number of operators times nodes.
Two systems papers supply the storage idea and its constraint. A-Store replaces join keys with positional array offsets, so joins become direct lookups. On the Star Schema Benchmark at scale factor 100 it reaches near flat-table scan speed while using 45.82 GB instead of 262.08 GB. We borrow its lesson that positional layout can stand in for physical denormalization.
We do not claim positional indexing itself as new. Compressed sparse row adjacency in graph libraries already does this. Our layout is instead positional over (entity, time), and it carries running aggregates. Hadoop Perfect File and Zhang motivate the checkpointing choice. Both show that per-item metadata, not payload, becomes the scaling limit, and that computing positions or offsets beats storing lookup tables.
Two papers constrain the design. RWDISK bounds hub cost by turning hubs into walk-terminating sinks, which is an approximation that discards hub information. We aim to keep hubs exact instead. Representation Independent Analytics Over Structured Data shows that flattening schemas distorts random-walk scores by more than 0.5 ranking discrepancy, while meta-path-based PathSim stays invariant. Our aggregates are defined along schema paths, much like meta-paths, so we predict and test the same invariance. Finally, REST and historical-embedding methods keep an $O(N)$ cache of node states that goes stale as the model trains. Our store holds only functions of raw features, so it never goes stale. The price is that it cannot hold learned states.
Research Program
Encoding and layout. Each table's columns are encoded once with RelBench's standard column encoders. For each relation from a fact table to a target entity (reviews to customer, reviews to product), we sort the fact rows by (target entity, timestamp). Two small arrays accompany this order. The first gives, for each target entity, the offset where its block starts. The second holds the sorted timestamps.
Checkpointed running sums. Every $b$ rows within each entity block, we store the cumulative sum, the count, and optionally the sum of squares of the encoded features. The aggregate for entity $v$ over the time window $(t-w, t]$ is the difference of two prefix values. Each prefix value is found by binary search on timestamps, then completed by scanning at most $b$ raw rows past the nearest checkpoint. Writing $E$ for the number of links in the relation and $d$ for the encoded width, memory and per-query work are
$$ M(b) \approx \frac{E}{b}\, d \quad\text{floats}, \qquad Q(b) = O\!\left(\log \deg(v) + b\, d\right). $$
The $b=1$ endpoint stores every running sum. The $b=\infty$ endpoint is plain on-the-fly scanning, which costs $O(\deg(v)\,d)$ and is where hubs hurt. We will also study degree-adaptive $b$, with checkpoints only inside blocks longer than some threshold, because the cost of hubs concentrates in a small number of long blocks.
Two-hop composition. For a path such as customer to reviews to product, we first attach to each review row the product's one-hop aggregate as of that review's timestamp. This is computed with the same store, costs one $O(E\,d)$ pass, and uses only data before the review. We then build a second prefix store over these augmented rows keyed by customer. Every quantity depends only on rows before the seed time, so leakage cannot occur by construction. We will verify this with a randomized audit against brute-force SQL.
Model. Per seed entity and cutoff time, we concatenate windowed aggregates over several windows and schema paths. These play the role of SIGN's multiple operators. Two heads read these features. One is an MLP, the SIGN analogue. The other is a hybrid, in which the precomputed aggregates replace sampling on hub relations while a sampled relational GNN still handles low-degree relations with learnable messages. The hybrid tests whether learnable first-hop message functions matter once exact aggregates are available.
Baselines
The naive reference point is RelBench's single-table LightGBM, which uses only the target entity's own columns. RelBench reports that relational deep learning beats it by an average of 20.4% on classification and 277% on recommendation tasks. Our method must land in the relational deep learning regime, not near this floor.
The strongest existing learned method is the RelBench relational GNN with temporal neighbor sampling (RelBench), which the paper reports matching or beating an expert data scientist on 11 of 15 tasks. The file gives no per-task scores: no reported result found on Lacuna for per-task RelBench RDL AUROC or MAE. We will therefore rerun it from the released configuration on the same splits, encoders, GPU and hyperparameter budget as our method. We will also sweep fanout, because a larger fanout is the obvious fix for hub truncation. Beating it means equal or better task metrics on average, with a clear gain on the high-degree-target tasks, at lower wall-clock time and peak memory.
The strongest aggregate-based competitor is DFS with LightGBM, as selected and tuned by Relatron using its released code. Relatron reports up to an 18.5% improvement over strong baselines and 87.5% accuracy in choosing between DFS and relational deep learning. We run it with the same aggregation primitives and windows as our store, so any difference in quality comes from the model and composition rather than the feature menu. The difference in cost comes from the layout. Beating it on cost means lower preprocessing time and memory at the same features. Beating it on quality requires the MLP or hybrid head to win.
The key ablations are two. The first is a snapshot-SIGN variant that precomputes static aggregates at $S$ fixed dates and uses the latest snapshot before each cutoff. It isolates the value of exact time correctness against its $O(S\,N\,d)$ memory. The second is a checkpoint sweep over $b$ from dense to $\infty$, which isolates the memory-latency trade-off.
Why not just…?
Why not just run DFS and train gradient-boosted trees? This is the real threat. On homophilous tasks, Relatron finds DFS already wins, and our features are DFS-like. The honest position is that on such tasks our contribution is the cost of computing the same features. DFS evaluates a join-aggregate per training example per cutoff, so its work scales with examples times entity degree. Our store answers the same query in near-constant time per example after one sort. If DFS with LightGBM equals our MLP head on quality, we report the result as a systems result and measure it on preprocessing time and memory on rel-amazon's 21.9M reviews. The modeling claim then rests only on the hybrid head and the heterophilous tasks where Relatron finds relational deep learning ahead.
Why not just raise the sampling fanout? Larger fanouts do reduce truncation on hubs, but cost grows multiplicatively per hop. SIGN reports up to an order of magnitude faster inference by avoiding sampling. The fanout sweep in the baseline directly measures where accuracy saturates and at what cost. If a moderate fanout already matches exact aggregation, our accuracy claim fails, and we will say so.
Why not just use SIGN or snapshot precomputation? Static diffusion on a temporal database either uses future rows or goes stale between snapshots. The snapshot ablation quantifies how much accuracy drift appears at practical snapshot counts, and how much memory $S$ snapshots cost compared with $E/b$ checkpoints.
Why not just use compressed sparse row adjacency with positional indices? We agree that this already provides A-Store-style virtual joins, and we build on it. What it lacks is time-sorted running aggregates, and those are what make hub aggregation cheap and exact at any cutoff.
Proposed Experiments
The main study covers the seven RelBench databases and their entity classification and regression tasks. For each task we stratify results by the degree of the target entity along its heaviest relation. The decisive check is whether our method's advantage over the sampled GNN grows with degree. If it does not, the hub hypothesis is wrong.
Scaling runs use rel-amazon and rel-avito, the largest databases in the benchmark. We report preprocessing time, peak host and GPU memory, epoch time, and inference latency, and we also measure the $M(b)$ and $Q(b)$ curves empirically against the formula above.
A correctness audit compares 10,000 random (entity, cutoff, window) queries against brute-force SQL, and should show zero mismatches in the leakage-relevant counts.
A representation-independence check follows the protocol of Representation Independent Analytics Over Structured Data. We build a flattened variant of one RelBench schema by collapsing an intermediate table into direct links, then compare how our path-defined aggregates and the sampled GNN shift in predictions and task metric. We expect our aggregates to shift little, as PathSim did, and the sampled GNN to shift more.
Recommendation tasks are left out of the main claim, since they need pairwise scoring beyond per-entity aggregates. We report them only for the hybrid head.
References
- Relational Deep Learning: Graph Representation Learning on Relational Databases
- RelBench: A Benchmark for Deep Learning on Relational Databases
- Relatron: Automating Relational Machine Learning over Relational Databases
- SIGN: Scalable Inception Graph Neural Networks
- Virtual Denormalization via Array Index Reference for Main Memory OLAP
- Hadoop Perfect File: A fast and memory-efficient metadata access archive file to face small files problem in HDFS
- Reducing the Overhead of Memory Space, Network Communication and Disk I/O for Analytic Frameworks in Big Data Ecosystem
- Fast nearest-neighbor search in disk-resident graphs
- Representation Independent Analytics Over Structured Data.
- Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks