PaperlayerView exact revision on arXiv

Source-linked AI summary

RelGNN: Composite Message Passing for Relational Deep Learning

Tianlang Chen, Charilaos Kanatsoulis, Jure Leskovec

arXiv:2502.06784v2cs.LGcs.AIcs.DB

TL;DR

Relational database graphs have schema-driven structures that standard heterogeneous GNNs may not model effectively, despite their use for predictive tasks. RELGNN uses atomic routes with composite message passing and graph attention to model those structures. It outperforms baselines on most of 30 RelBench tasks, with improvements up to 25%.

  • Problem

    Standard heterogeneous GNNs treat primary-foreign key links as semantic relations, although they represent table connectivity, leaving relational database structure insufficiently modeled.

    Source: §3.1 · p. 4

  • Method

    RELGNN derives atomic routes from primary-foreign key relationships and uses composite message passing with attention to aggregate along them in a single step.

    Source: §1 · p. 2

  • Results

    RELGNN surpasses baselines on 27 of 30 RelBench tasks, performs comparably on the remaining three, and achieves up to a 25% improvement on site-success regression in rel-trial.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Across 30 tasks in seven databases, RELGNN outperforms state-of-the-art baselines on the vast majority of tasks.

    Source: §7 · p. 9

    Rel-stack gains are limited, and rel-trial results diverge across tasks; the authors suggest regression prediction-head limitations may contribute and identify improved regression heads as future work.

    Source: §5.2 · p. 8

Abstract

from arXiv · show

Predictive tasks on relational databases are critical in real-world applications spanning e-commerce, healthcare, and social media. To address these tasks effectively, Relational Deep Learning (RDL) encodes relational data as graphs, enabling Graph Neural Networks (GNNs) to exploit relational structures for improved predictions. However, existing RDL methods often overlook the intrinsic structural properties of the graphs built from relational databases, leading to modeling inefficiencies, particularly in handling many-to-many relationships. Here we introduce RelGNN, a novel GNN framework specifically designed to leverage the unique structural characteristics of the graphs built from relational databases. At the core of our approach is the introduction of atomic routes, which are simple paths that enable direct single-hop interactions between the source and destination nodes. Building upon these atomic routes, RelGNN designs new composite message passing and graph attention mechanisms that reduce redundancy, highlight key signals, and enhance predictive accuracy. RelGNN is evaluated on 30 diverse real-world tasks from Relbench (Fey et al., 2024), and achieves state-of-the-art performance on the vast majority of tasks, with improvements of up to 25%. Code is available at https://github.com/snap-stanford/RelGNN.

1. Introduction

Relational databases support important predictive tasks, but flattening them loses relational signal and standard heterogeneous GNNs can overlook their schema-driven structure. RELGNN uses atomic routes and composite message passing to model that structure, outperforming baselines on most RelBench tasks.

Motivation

  • Flattening relational data into one table requires manual feature engineering and loses predictive signal by oversimplifying its connections.RDL instead represents entities as graph nodes and primary-foreign key links as edges for GNN modeling.Source: §1 · p. 1
  • Standard heterogeneous GNNs treat primary-foreign key links as semantic edges, although they record table connectivity, overlooking relational database topology.This motivates architectures tailored to relational databases' structural regularities.Source: §1 · p. 1

Structural patterns

  • Many-to-many relationships are materialized through junction tables, creating bridge nodes with two foreign keys and hub nodes with three or more.These nodes primarily route information, while standard message passing can repeatedly aggregate through them and overlook latent clique-like dependencies around hubs.Source: §1 · p. 2

Our approach

  • RELGNN introduces atomic routes—simple paths enabling single-hop source-to-destination exchange—and builds composite message passing and graph attention on them.Routes through a shared intermediate node connect entities linked via multi-foreign-key tables.Source: §1 · p. 2
  • Composite message passing aggregates along atomic routes in one step, avoiding redundant hops and irrelevant information aggregation.Atomic routes are systematically derived from primary-foreign key relationships rather than manually designed meta-paths.Source: §1 · p. 2

Results

  • RELGNN surpasses baselines on 27 of 30 RelBench tasks and performs comparably on the other three, with up to a 25% improvement on rel-trial site-success regression.It improves over a standard heterogeneous GNN by more than 4% on 17 of 30 tasks.Source: §1 · p. 2

2. Preliminaries

The preliminaries define relational databases in terms of tables, entities, keys, and links, then describe how RDL turns them into temporal heterogeneous graphs. Temporal neighbor sampling restricts each prediction subgraph to information available by its seed entity's time.

2.1. Relational Database

  • A relational database comprises tables and links between them, with each table containing entities and each entity carrying a unique primary key and potentially foreign keys, attributes, and a timestamp.A table link exists when a foreign-key column references a primary-key column in another table.Source: §2.1 · pp. 2–3
  • The schema graph represents tables as node-types and primary-foreign key relationships as directed edges from foreign-key tables to primary-key tables.Figure 2 illustrates the progression from relational tables and their links to a relational entity graph.Source: §2.1 · p. 3, Figure 2 · p. 3

2.2. Relational Deep Learning (RDL)

  • RDL represents each table as a node-type, each row as a node, and each primary-foreign key relationship as an edge in a temporal heterogeneous graph.Table columns provide initial node features, and the transformation preserves the information in the tables.Source: §2.2 · p. 3
  • For a seed entity at time t, temporal neighbor sampling includes only nodes timestamped at or before t, excluding future information to avoid leakage.GNNs are trained end-to-end on these time-consistent subgraphs, without manual feature engineering.Source: §2.2 · p. 3

3. Bridge and Hub Topology in RDL (our work)

Relational entity graphs encode primary-foreign key connectivity rather than semantic relations, and junction tables represent many-to-many links. Bridge and hub structures therefore create message-passing inefficiencies and latent dependencies that standard approaches may miss.

3.1. Structural Patterns in Relational Databases

  • Unlike general heterogeneous graphs, relational entity graph edges encode primary-foreign key references rather than semantically meaningful relations.A junction table such as transaction becomes an intermediate node-type, so the usual semantic-edge message-passing assumptions do not hold.Source: §3.1 · p. 4
  • Junction tables decompose many-to-many relationships into two one-to-many links by connecting each entity pair through an intermediate node.The intermediate transaction node contains foreign keys to both the customer and the item.Source: §3.1 · p. 4

3.2.1. NODE-TYPE WITH TWO FOREIGN KEYS (BRIDGE)

  • A two-foreign-key node-type forms a tripartite bridge, where two-hop message passing duplicates destination information and can overemphasize the bridge over the source.In the race-outcome example, standings information reaches drivers in both hops, while race information arrives only in the second.Source: §3.2.1 · p. 4

3.2.2. NODE-TYPE WITH THREE OR MORE FOREIGN KEYS (HUB)

  • A node-type with three or more foreign keys forms a star-shaped hub connecting multiple node-types, with redundant paths and imbalanced signals under standard two-hop message passing.Hub stars also induce latent second-order clique structures at the schema level that standard approaches overlook and underuse.Source: §3.2.2 · pp. 4–5

4. Proposed Architecture: RELGNN

RELGNN derives atomic routes from primary–foreign key schemas for direct source–destination exchange, then builds composite message passing and graph attention over those routes.

4.1. Atomic Routes in RDL

  • An atomic route is a simple path between node-types that enables single-hop source–destination interaction, using an edge for one foreign key or a path through an intermediate node for multiple foreign keys.The multiple-foreign-key case connects the source and destination node-types through the intermediate primary-key node-type.Source: §4.1 · p. 5
  • Unlike manually designed, task-specific meta-paths, atomic routes are derived automatically from database primary–foreign key relationships and apply across relational schemas.The passage notes applicability even to complex or previously unseen schemas.Source: §4.1 · p. 5

4.2. Composite Message Passing for RDL

  • Standard heterogeneous GNNs need two steps and can aggregate unrelated neighbors or return destination information through the intermediate node; composite passing completes source-to-destination exchange in one step.This design targets redundant aggregation and extraneous information in the standard process.Source: §4.2 · pp. 5–6

4.3. RELGNN: Composite Message Passing with Atomic Routes

  • For multiple-foreign-key routes, RELGNN fuses source-node information at each intermediate node, then uses destination embeddings as attention queries and fused embeddings as keys and values.The attention coefficients are computed with multi-head attention.Source: §4.3 · p. 6
  • When tables have no multiple-foreign-key structure, RELGNN skips fusion and uses the source embedding directly.Figure 3 depicts the atomic routes derived from the rel-f1 dataset.Source: §4.3 · p. 6, Figure 3 · p. 6
  • RELGNN uses distinct weight matrices for each atomic route and sums the resulting route messages at each destination node.The route-specific weights let the model learn how to weight each message during the summation.Source: §4.3 · pp. 6–7

5. Experiments

Experiments evaluate RELGNN across diverse, temporally split RELBENCH tasks using matched heterogeneous-GNN baselines. It performs better or comparably across classification, regression, and recommendation, with task-specific boundaries.

5. Experiments

  • RELBENCH spans 7 real-world databases and 30 tasks, with models trained on earlier periods and tested on future periods.The heterogeneous-GNN baseline uses the same data pipeline, training table, sampling algorithm, initial embeddings, prediction head, and loss function.Source: §5 · p. 7

5.1. Entity Classification

  • 10 of 12 classification tasks favor RELGNN over baselines, with comparable performance on the remaining two.Gains are more pronounced on datasets with complex primary-foreign-key structures than on rel-amazon and rel-hm.Source: §5.1 · p. 7, Table 1 · p. 8
  • On rel-stack, RELGNN does not achieve significant classification improvements; its same-type post links present a distinct self-loop challenge.The authors leave robust handling of self-loops for future work because it is orthogonal to their core contribution.Source: §5.1 · p. 7

5.2. Entity Regression

  • 8 of 9 regression tasks favor RELGNN over baselines, with comparable performance on the remaining task.Improvements are most pronounced on datasets with complex primary-foreign-key structures.Source: §5.2 · p. 8, Table 2 · p. 8
  • Regression results diverge across rel-trial tasks, and the authors suggest prediction-head limits may contribute, especially for unbounded targets.They identify improving regression prediction heads as future work.Source: §5.2 · p. 8

5.3. Recommendation

  • RELGNN achieves better or the same performance as baselines on all 9 recommendation tasks.The study uses two-tower GNNs for rel-amazon and ID-GNNs for the remaining datasets.Source: §5.3 · p. 8, Table 3 · p. 9
  • ID-GNN restricts recommendation candidates to nodes sampled around the source, and struggles when ground-truth targets are often outside that subgraph.Accordingly, RELGNN shows greater gains on high-locality tasks than on low-locality tasks.Source: §5.3 · p. 8

6. Related Work

Related work spans GNNs for relational data, manually designed meta-paths for heterogeneous graphs, and knowledge-graph completion. RELGNN focuses instead on GNN architecture for predictive tasks over relational databases.

Deep Learning on Relational Data

  • Prior relational-data GNN work explores architectures using relational structure, while RELGNN targets GNN architecture across RDL task types.Yuan et al. (2024) focus on recommendation prediction heads, an orthogonal contribution.Source: §6 · p. 9

Meta-paths in Heterogeneous Graphs

  • Meta-paths are manually specified node- and edge-type sequences, which can require expertise and overlook relevant patterns.The authors contrast this manual design with their systematically derived atomic routes.Source: §6 · p. 9

Distinction between RDL and Knowledge Graphs

  • Knowledge-graph models mainly predict missing entities or relations, whereas RDL predicts entities or groups at future timestamps.The passage gives customer churn and future spending as RDL examples.Source: §6 · p. 9

7. Conclusion

RELGNN addresses structural inefficiencies in heterogeneous GNNs on relational databases through atomic routes and composite message passing. On RELBENCH, it outperforms state-of-the-art baselines on most tasks, with improvements up to 25%.

7. Conclusion

  • Across 30 tasks and 7 relational databases, RELGNN outperforms state-of-the-art baselines on the vast majority of tasks, with up to 25% improvement in predictive accuracy.The conclusion argues that relational-data models should explicitly account for primary-foreign-key relationships.Source: §7 · p. 9
  • Atomic routes support direct single-hop interactions between source and destination nodes in composite message passing.The conclusion says this avoids redundant aggregation and highlights key predictive signals.Source: §7 · p. 9
  • RELGNN is designed to address structural inefficiencies of existing heterogeneous GNNs applied to relational databases.The conclusion describes the framework as specifically designed for this setting.Source: §7 · p. 9

A. RELBENCH Details

The appendix section provides RELBENCH descriptions and statistics for its datasets and tasks.

A. RELBENCH Details

  • The section provides detailed descriptions and related statistics for RELBENCH.Table 4 presents statistics for each dataset and task.Source: A. RELBENCH Details · p. 12

A.1. Datasets

RELBENCH comprises seven datasets spanning diverse domains, from commerce and social activity to sports, Q&A, and clinical trials. The datasets contain varied entities, interactions, and domain-specific records.

  • Amazon’s dataset combines product metadata, reviews, and user engagement, while Avito includes search queries, ad characteristics, and contextual marketplace data.Source: §A.1 · p. 12
  • The Event dataset links user interactions and event details with demographics and social connections; F1 records racing participants, results, standings, and session data.Source: §A.1 · p. 12
  • H&M captures customer and product attributes alongside purchase histories, while Stack Exchange records user biographies and detailed posts, comments, edits, votes, and linked questions.Source: §A.1 · pp. 12–13
  • The clinical-trial dataset aggregates study protocols, participant demographics, interventions, and outcome measures.Source: §A.1 · p. 13

A.2. Tasks

RELBENCH tasks predict future outcomes across its datasets, including classification, regression, and recommendation targets. A separate visualization presents datasets’ primary–foreign key relationships.

A.2. Tasks

  • H&M tasks cover customer and product churn, customer and item lifetime value, and purchase or review recommendations.Source: §A.2 · p. 13
  • Avito tasks predict user ad visits and clicks, ad click-through rate, and ads visited by a user.Source: §A.2 · p. 13
  • Event and F1 tasks predict attendance, invitation responses, race completion, qualifying positions, and future finishing placement.Source: §A.2 · p. 13
  • Amazon tasks include predicting customer churn, article sales, and the items a customer will purchase.Source: §A.2 · p. 13
  • Stack Exchange tasks predict user participation and badges, post votes, and links or comments between posts.Source: §A.2 · p. 14
  • Clinical-trial tasks predict study outcomes, adverse events, site success, and sponsor associations with conditions or facilities.Source: §A.2 · p. 14

B. Visualization of Primary-Foreign Key Relationships

C. Ablation Study

The ablation study finds that RELGNN’s gains are primarily associated with atomic routes rather than attention alone. Its advantage also holds across different backbone GNNs.

  • The ablation configures FUSE as in GraphSAGE and replaces attention-based AGGR with GraphSAGE-style aggregation, isolating atomic routes as the architectural difference.Source: C. Ablation Study · p. 14
  • RELGNN’s gains stem primarily from atomic routes, with only a modest performance gap between versions with and without attention.The authors report consistent gains over baselines when the aggregation mechanism is held constant.Source: C. Ablation Study · p. 14
  • RELGNN outperforms all tested baselines with GAT and GIN backbones as well as the other backbone GNNs.Source: C. Ablation Study · p. 14

D. Additional Discussion

The discussion describes scalability choices and optional additions to RELGNN, including schema-graph encoding and alternative GNN components. It also reports an RPE evaluation on self-loop data.

  • Atomic routes are computed over schema-level table types, typically numbering in the tens, so their computation is agnostic to entity count and can scale as databases grow.Source: D. Additional Discussion · p. 14
  • Fixed-size neighborhood sampling bounds active foreign-key connections during training or inference, keeping message passing efficient for tables with many foreign keys.Source: D. Additional Discussion · p. 14
  • Relative positional encoding over the schema graph distinguishes same-type from different-type messages and adds global relational context; on rel-stack, it improved both classification tasks by 2%.The schema graph is small and static, allowing RPE to be precomputed and reused.Source: D. Additional Discussion · p. 17
  • RELGNN can incorporate advanced components, including PNA as an aggregator and Jumping Knowledge to combine representations from multiple layers.Source: D. Additional Discussion · p. 17
  • Time2Vec and GraphMixer time encodings can be added as node features, with minimal overhead.Source: D. Additional Discussion · p. 17

Related papers

Loading 2502.06784v2…