RelGNN: Composite Message Passing for Relational Deep Learning
Authors: Tianlang Chen
Charilaos Kanatsoulis
Jure Leskovec
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Networks
Relational Deep Learning
Primary area: deep_learning->graph_neural_networks
TL;DR: RelGNN is a novel GNN framework that introduces composite message passing and graph attention mechanisms based on automatically derived "atomic routes" to efficiently model relational data, achieving state-of-the-art performance on Relbench.

Abstract: 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%.

RELGNN: Composite Message Passing for Relational Deep Learning
Tianlang Chen Charilaos Kanatsoulis Jure Leskovee'
Abstract
& Guestrin, 2016) that often require flattening relational data into single table through manual feature engineering (Kag- gle, 2022). This approach is not only labor-intensive but also leads to substantial loss of predictive signal, as it oversimplifies the interconnected structure relational data during the flattening process.
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 REIGNNN, 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 evaluated on 30 diverse real-world tasks from RELBENCH (Fey al., 2024), and achieves state-of-the-art performance on the vast majority of tasks, with improvements of up to 25%.
To overcome the limitations of tabular approaches, Fey et al. (2024) introduced Relational Deep Learning (RDL.), new machine learning paradigm that enables end-to-end trainable neural networks to perform predictive modeling directly on relational databases. In RDL, relational data is represented as a graph, where each entity represented as a node, and the primary-foreign key links between entities define the edges. This graph-baset representation allows Graph Neural Networks (GNNs) (Gilmer et al., 2017: Hamilton al., 2017) to serve as predictive models, capturing complex relational dependencies that traditional approaches overlook. Complementing this advancement, REL BENCH (Robinson et al., 2024) provides the first comprehensive benchmark for evaluating and developing RDL models.
Building effective RDL models is essential for tackling predictive tasks, yet remains quite challenging: Relational entity graphs are large-scale, heterogeneous, and temporally dynamic. The models introduced by Robinson et al. (2024) apply standard heterogeneous GNNs (Schlichtkrull et al., 2018; Hu et al., 2020) to relational entity graphs. This design choice can be suboptimal, since standard hetero- geneous GNNs are developed for generic multi-relational graphs, where each edge-type denotes direct semantic interaction between nodes. In relational databases, however, edges are defined by primary-foreign key links that merely record table connectivity, rather than native semantic relation. Treating these schema-driven links as ordinary semantic edges overlooks the database's characteristic topology (e.g., many-to-many motifs, as discussed later), misrepresents how information should propagate, and ultimately limits model fidelity. These differences motivate the design of architectures tailored to the structural regularities of relational databases.
1. Introduction
Predictive modeling over relational data (multiple tables connected via primary-foreign key relations) is central to numerous real-world applications: e-commerce platforms forecast product demand, music streaming services personal- ize recommendations, financial institutions assess credit risk, etc. The common strategy tackle these predictive tasks re- lies on classical tabular machine learning approaches (Chen
'Computer Science Department, Stanford University. Corre- spondence to: Tianlang Chen <tlchen srcchen@cssstanfor..coo edu.>
Our contribution. We analyze the distinctive structural patterns of relational entity graphs. Our work builds upon a central insight: Relational databases abound with many-to- many relationships; because each foreign key can reference
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

RELGNN: Composite Message Passing for Relational Deep Learning
standings
standings
roces
standings
drivers
constructors
races
drivers
standings
results
FROM
resuls
dhivers
rooes
drivers
constructors
deivers
crouts
roces
results
dircuit
qualifying
(u) Primary-foreign Key Relation rel--lfl Dataset
(b) Bridge Stracture
(c) Hub Structure
(d) Example of Atomic Routes
Figure 1:
An illustration of the key concepts in our method. (a) The formany- key relation of the rel-f1 dataset. Arrows point from node with foreign key to the node with the corresponding primary key. Nodes with zero or one foreign key are marked in pink, and the corresponding foreign key is illustrated by a solid line. Nodes with two or more foreign keys are marked in purple, and the corresponding foreign keys are illustrated by dotted lines. (b) An example of the bridge structure, where standings node is a bridge node. (c) An example of the hub structure, where results node is a hub node. (d) Examples of three atomic routes, where the nodes within each box constitute a distinct atomic route.
only one primary key, these associations cannot be encoded by single primary-foreigg key edge. Instead, they are materialized through junction tables that sit between the two entity tables, decomposing each many-to-man mo-many association into a pair of one-to-many links. In the resulting graph, these tables give rise to two common substructures: (i) bridge nodes (cf. Figure 1(b)), which contain exactly two for- eign keys and connect pairs of entities via tripartite pattern (node-type 3 node-type - node-type 2) and (ii) hub nodes (cf. Figure I(c)). which possess three more foreign keys, forming star-shaped subgraphs. Bridge and hub nodes function mostly as 'routers', i.e., they contribute little se- mantic content, but channel information among their neigh- bors. Standard message passing GNNs repeatedly aggregate signals through the same bridge or hub nodes, generating over-smoothed representations. Moreover, the star-shaped motifs around hub nodes encode latent clique-like depen- dencies that conventional message passing cannot exploit.
2011) used in conventional heterogeneous graphs, atomic routes differ fundamentally in how they are constructed. While meta-paths typically rely on manual design guided by domain expertise, atomic routes are automatically and sys- tematically derived from primary-foreign key relationships in relational databases, making them both broadly applica- ble and highly scalable across diverse datasets. Building on these routes, RELGNN designs composite message passing with attention mechanism that directly aggregates messages along atomic routes in single step, avoiding redundant hops and preventing irrelevant information aggregation. This en- ables more efficient and accurate extraction of predictive signals compared to conventional heterogeneous GNNs.
We assess the performance of the proposed RELGNN across all tasks in RELBENCH (Fey et al., 2024), a benchmark which spans seven diverse relational databases covering e- commerce, social networks, sports, and medical platforms. RELBENCH features 30 real-world predictive tasks cast as entity classification, entity regression, and recommendation. RELGNN surpasses all basclines on 27 of the 30 tasks while performing comparably on the remaining three. Notably, RELGNN achieves more than a 4% improvement over a standard heterogeneous GNN in 17 out of 30 tasks, and provides up a 25% improvement on the site success regression task in the rel-trial database.
To address these challenges, we propose RELGNN, a novel GNN framework that introduces the composite message passing and graph attention mechanism to fully exploit the unique structural properties of graphs built from relational database. RELGGN introduces the concept of atomic roufes, which are simple paths that support complete, single-hop information exchange between the source and destination nodes, grounded in primary-foreige key relationships (cf. Figure I(d). When a table has a single foreign key, an atomic route consists of a pair of node-types and the edge connecting them. When a table has multiple foreign keys, it induces set of atomic routes in the form of (source + inter- mediate ++ destination) paths, each of which connects two entities through a shared intermediate node (i.e., a bridge or hub node). Although reminiscent of meta-paths (Sun et al.,
2. Preliminaries
2.1. Relational Database
A relational database (T, L) consists of a set of tables T (Ti...., T and set of links between them L C T. Each table is set T (U1,... ber), where the elements
2

---

RELGNN: Composite Message Passing for Relational Deep Learning
Products
Transactions
Tranactions
Products
Prodact
Transaction_p
Description
ProductiJ
dh
1
6747
Image
Timestemp
08
Size
Customer_p _DD
4017
Customers
Cusioneer__
Kame
(a) Relational Database
(b) Relational Tables
(c) Relational Entity Graph
(d) Sampled Subgraph
Figure 2: Illustration of key concepts of RDL. (a) An example relational database. (b) Relational tables connected by primary-foreign key relations. (c) Relational entity graph built from relational tables. (d) Subgraph sampled with termporal neighbor sampling. Figures from Fey et al. (2024).
E T are called rows or entities. Each entity E T has a unique primary key Pe that distinguishes it from other entities within the table. An entity can possess one or more foreign keys. Formally, each foreign key Kr,, C (Pe : v' E T" and (T,T") E L} links an entity e e T to entity v' E T where Py is the primary key of o' in table TV. An entity may have several attributes Ze, which represent the informational content, and may optionally include timestamp E., indicating when the corresponding event occurred. Primary keys, foreign keys, attributes, and the timestamp are all realized as table columns. link = (Tey.. Tpkyy) between tables exists if foreign key column in T Roy references primary key column of T Tkkyy.
2.2. Relational Deep Learning (RDL)
Fey et al. (2024) introduced RDL, an end-to-end framework for predictive modeling on relational databases with neural networks. RDL represents the database as a relational entity graph, which a temporal, heterogeneous graph, where each table becomes node-type, each row (entity) an individual node, and every primary-foreign key relationship edge (Figure 2 (b)-(c).. The columns of each table provide the initial feature vector for their corresponding nodes. The transformation from the relational database to its relational entity graph form is lossless, preserving all information contained the original tables.
Time is a first-class citizen in RDL. Each entity v may carry timestamp fo that records when the corresponding event occurred- for example, every row in the TRANSACTIONS table logs the moment of purchase. Many tasks are inher- ently temporal (c.g., predicting next-week product sales), so the model must respect causality. RDL therefore employs temporal neighbor sampling (Hamilton et al., 2017: Fey et al., 2024): for a seed entity at time f, builds a subgraph that contains only nodes with timestamps S t,, excluding all future information to avoid leakage. A GNN is then trained end-to-end on these time-consistent subgraphs, eliminating the need for manual feature engineering (Figure 2 (d)).
In Figure 2 (a). the TRANSACTIONS table contains one primary key column (TRANSACTIONID), two foreign key columns (PRODUCTID and CUSTOMERID), a numeri- cal attribute column (PRICE), and a timestamp column (TIMESTAMP). The PRODUCTS table, by contrast, has a single primary key column (PRoDUcTID), no foreign keys, and three attribute columns (DESCRIPTION, IMAGE, SIZF); it does not record timestamps. The black lines illustrate the peregn--ey--piimary--e links between the tables.
To capture the structural relationships between tables, we introduce the schema graph, which encodes the table- relational database. Given a relational database (T, (), the schema graph is defined as (T, L), node,
level topology
3. Bridge and Hub Topology in RDL (our work)
where each table (i.e., node-type) corresponds and each primary-foreign key relationship defines directed edge from the foreign key table to the primary key table. Fig- ure 1 (a) illustrates the schema graph of rel-fe wel-fl fl dataset and Figure 4 shows the schema graphs of all the other datasets in RELBENCH This definition corresponds to the directed variant of the schema graph described in Fey et al. (2024). Note that node in the schema graph corresponds to a node- type in the relational entity graph, which introduce in the next subsection.
3.1. Structural Patterns in Relational Databases
Heterogeneous graph topology. General heterogeneous graphs encode information between nodes and edges of different types. The basic structural unit of the heteroge- neous graph schema a relation, written as a triplet (source node-type, edge-type, destination node-type). For example, retail purchase is captured by the triplet (customer, transaction, item), which represents customer purchasing an item. Heterogeneous GNNs (Schlichtkrull et al., 2018;
3

---

RELGNN: Composite Message Passing for Relational Deep Learning
Hu et al., 2020), are designed process these relations through edge-semantic message passing, e.g., message originating at a customer node traverses a transaction edge and is aggregated at the corresponding item node in a single hop. This message passing mechanism learns representations of both nodes and edge-types, and preserves the distinct semantics of each relation.
Constructor constructor and standings each have two foreign keys, and results and qualifying each have three. Node-types with zero or one foreign key, high- lighted in pink, do not require intermediate nodes to support message exchange and they exhibit a standard topology. In contrast, node-types with two or more foreign keys, high- lighted in purple, serve as structural intermediaries in the schema. Given the ubiquity of many-to-many relationships in real-world interactions, cases involving (ii) are common in relational entity graphs and play central role in shaping information flow. Next, we analyze the limitations of stan- dard message passing over these structures and motivate a more specialized approach.
Relational entity graph topology. Unlike general het- erogeneous graphs, where an edge denotes a semantically meaningful relation, the edges of relational entity graphs are formed by references to primary foreign keys in the database schema. Hence, each edge-type carries no intrinsic semantics beyond "table A points table B," and the basic structural unit collapses a pair (node-type I, node-type 2), rather than a semantic triplet. Consider the retail example: instead of a single relation (customer, transaction, item), the database materializes a junction table transaction. In the relational entity graph, this becomes an explicit intermediate node-type, producing two edges (transaction, customer) and (Iransaction, item). Because these edges encode only primary-foreign key relationships-non the semantic of purchasing- usual message passing assumptions for heterogeneous graphs no longer hold. This shift from semantic triplets to purely structural links therefore calls for further investigation.
3.2. Challenges in Message Passing for RDL
3.2.1. NODE-TYPE WITH TWO FOREIGN KEYS (BRIDGE)
When a node-type has two foreign keys, it forms subgraph of the form (node-type 3 t- node-type / -> node-type 2), creating a local tripartite structure among these three node- types. In this configuration, node-rype simply acts as an aggregating bridge between node-type 2 and node-type 3. Under standard heterogeneous GNNs, message passing over this structure involves two hops: from the source to the bridge, and then from the bridge to the destination. However, this two-hop communication introduces two inefficiencies. First, redundancy: information from the destination node is passed the bridge in the first hop and then routed back to itself in the second, duplicating self-information. Second, imbalance: since the bridge node is an one-hop neighbor of the destination node while the source node is two hops away, the destination aggregates information from the bridge in both hops but receives information from the source only in the second. This leads to an overemphasis on the bridge node and under-utilization of the source node, which often carries more informative and predictive signals.
Many-to-mant relationships. The transition from seman- tic triplets to hrimary-foreige key edges significantly im- pacts how many-to-many relationships are represented in relational databases. A many-to toyy-ttomma -o--mnny relationship describes a scenario where multiple instances of one entity type are as- sociated with multiple instances of another. Although many- to-many relationships are ubiquitous, they cannot be directly encoded using single frimary-foreigee key connection, by definition, foreign key can reference only one unique primary key. To address this, databases introduce junction ta- bles that decompose many-to-many relationships into pairs of one-to-many links. In the retail example, customers and items form a many-to-many relationship each customer can purchase multiple items, and each item can be purchased by multiple customers. This association is mediated by transaction node, which serves as an intermediate connector in the relational entity graph. Each transaction node contains a pair of foreign keys, one referencing a customer node and the other referencing an item node, thereby decomposing the many-to-many association into two one-to-many links.
For example, consider the task of predicting race outcomes, where information flows from races node (source) to a drivers node (destination) via a standings node (bridge) (cf. Figure 1 (b)). In standard two-hop message passing, infor- mation from standings reaches the drivers node in both hops, while information from races arrives only in the second. Since the races node typically contains more contextual information relevant to driver performance, this imbalance may degrade performance. As we show in the next section, modeling such structure as an atomic route enables direct one-hop message passing between the relevant node-types without any loss of information.
The previous observations lead the following categoriza- tion of node-types in relational entity graphs: (i) node-types with zero or one foreign key, and (ii) node-types with two or more foreign keys. To illustrate them, consider the rel 1llfl fl schema, which tracks all-time Formula racing data since 1950 (cf. Figure 1 (a)). In this schema, constructors, races, and drivers each have zero foreign keys, and circuits has one.
3.2.2. NODE-TYPE WITH THREE OR MORE FOREIGN KEYS (HUB)
When a node-type has three or more foreign keys, it forms star-shaped subgraph that acts as a communication hub,
4

---

RELGNN: Composite Message Passing for Relational Deep Learning
connecting multiple other node-types. For example, as shown in Figure (c), the results node links constructors, races, and drivers, thereby mediating interactions among constructors-races, races-drivers, and constructors-drivern These hub node-types inherit the same inefficiencies observed in the two-foreign key case (bridge structures): Standard two-hop message passing leads to redundant communication paths and imbalanced predictive signals since information from hub nodes is aggregated multiple times, while more informative signals from source nodes may be underrepresented. Furthermore, the star-shaped connectivity patterns around hub node-types induce latent second-order clique structures at the schema strec-ssrus that are typically overlooked and under- utilized by standard modeling approaches. Our proposed approach, detailed next, is designed exploit these latent clique structures, which constitute critical subgraphs in many real-world domains. This shift from star-shaped to clique-like connectivity substantially increases graph density and transforms the geometry of information flow.
standings - drivers). These routes capture the necessary interactions among multiple entities within single step.
Comparison to Meta-paths. We compare atomic routes to meta-paths, a widely utilized concept in heterogeneous graph learning (cf. Section 6 for an extended discus- sion of meta-paths). Although both structures facilitate message propagation, they differ fundamentally in their construction and purpose. Meta-paths typically neces- sitate manual design guided by domain knowledge and task-specific intuition. This manual design process makes them labor-intensive, sensitive to dataset-specific charac- teristics, and susceptible to introducing selection bias. In contrast, atomic routes are derived automatically from the primary-foreign key relationships defined in the database schema. This enables their extraction without human su- pervision, ensuring applicability across wide range of relational
those with complex or pre- viously unseen schemas. While meta-paths are often con- structed to emphasize particular semantic patterns relevant to a task, atomic routes serve fundamentally different func- tion: they systematically capture the minimal pathways to avoid structural inefficiencies due to the primary-foreign key constraints.
4. Proposed Architecture: RELGNN
4.1. Atomic Routes in RDL
To address the limitations of standard message passing in relational entity graphs outlined above, we introduce the concept of atomic routes.
4.2. Composite Message Passing for RDL
In this subsection, we build upon the concept of atomic routes and design composite message passing mechanisms for RDL. We begin this discussion by applying a standard heterogeneous GNN on a subgraph that encodes tables with multiple foreign keys. We assign sre, dst, and mid to represent nodes corresponding to source, destination, and intermediate node-types, respectively. In standard heteroge- neous GNNs, takes two steps to complete the full informa- tion exchange. In the first step, each mic node aggregates information from all its neighbor nodes:
Definition 4.1 (Atomic Route). An atomic route is a simple path between node-types that enables single-hop inter- action between the source and destination node-type. We distinguish two cases:
1. Single foreign key. a table has exactly one foreign key referencing to another table, the atomic route is an edge between the foreign key node-type (source) and the primary key node-type (destination), forming simple path (source - destination).
h mid
(1+1) UPD(((m (1+1) (+RR// (I, <(mid)) RJ)..
2. Multiple foreign keys. If table has multiple for- eign keys referencing to different tables, the atomic routes are hyperedges that connect pairs of foreign key node-types (source and destination) via the intermedi- ate primary key node-type, forming simple paths of type (source > intermediate -> destination).
where
((+1) mR R
= AG (1 (d(()))) = TB),
he denotes the embedding of node v at the 1-th layer, UPD and AGGR are arbitrary differentiable functions with opti- mizable parameters, {(-) denotes a permutation invariant set aggregator (e.g. mean, sum), R denotes the edge set consisting of pairs of node-types connected through primary- foreign key relationships and d(.) denotes a function map- ping node to its corresponding node-type. Then in the second step, the message passed from mid to dst is
Figure 1 and 3 illustrate the primary-foreige key relation- ships in the rel-fi f1 dataset and the atomic routes derived from these relationships. For instance, the circuits table has only one foreign key, which points to the races table, form- ing atomic routes (circuits + races) and (races + circuits). In contrast, the standings table has two foreign keys con- necting it to both the drivers and races tables. This results in atomic routes (drivers - standings -> races) and (races >>
(2) Note that in Equation (1), T represents all node-types con- nected to the intermediate node-type. Therefore, in addition
(I+2) m (mid, dst) = AGGR(h (1+1) ((b)-)))
"ind
5

---

RELGNN: Composite Message Passing for Relational Deep Learning
the information from the source node-type, information from other node-types connected the intermediate node-
type is also aggregated during this step. Furthermore, the information from dst is passed to mid in this step, and subsequently passed back to dst again in Equation (2), leading to redundancy, as discussed in Section 3.2.
dst
STC
dst
races
circuits
circuits
races
To avoid these modeling inefficiencies we propose novel composite message passing scheme based on atomic routes.
(L+1) (dat.mid,src)
AGGR(h (9 dat. ((FUSE() (1) mid: hee )
m
(3)
src
mid
dst
Equation (3) describes composite information exchange from src via mi d to dst that is completed within a single step. As result, there is no extrancous information entan- gled in the process. In summary, our approach effectively tackles the challenges that standard heterogencous GNNs may encounter, such as multiple steps needed for complete information exchange and redundant aggregation during message passing.
STC
mid
dst
raccs
cestructoo.standdng constructors races
constructors
constructor siteructtorstanding
races
constructor
constructors
constructors
mustructor_resule
races
drivers
standings
races
races
standings
drivers
drivers
results
races
4.3. RNLGNN: Composite Message Passing with Atomic Routes
races
results
drivers
constructors
results
races
races
results
constructors
The introduction of atomic routes and composite message passing enables the design of new architectures specifically tailored to relational entity graphs. Equation (3) admits multiple instantiations, offering a flexible framework for message passing using atomic routes. Here, we propose REIGGNN, graph attention instantiation of Equation (3). When multiple foreign keys are involved, RELGNN in- stantiates Equation (3) follows: for each mid node, it fuses information from each src node connected via pri- fary-foreign key relationship. Specifically, FUSE(.) is implemented as linear combination:
drivers
results
constructors
constructors
results
drivers
drivers
qualifying
races
qualifying
drivers
constructors
qualifying
racos
races
qualifying
constructors
drivers
qualifying
constructors
constructors
qualifying
drivers
All the atomic routes derived from rel-fl dataset. The cemmary-foreigee key relations rel-fl is illustrated in Figure (a).
Figure 3:
FUSE(b
(1) mid' SYC = W h mid
W2h!! src:
(4)
for brevity):
Note that, due to the nature of foreign keys, each mid node connected to only one sre node. Then, RELGNN in- stantiates AGGR(-) with the standard multi-head attention mechanism (Vaswani et al., 2017; Shi et al., 2021), where embeddings from destination nodes serve as queries, and em- beddings derived from the fusion operation in Equation (4) serve keys and values. Let h (!) juse = FUSE(h") (4) mins h defined in Equation (4). AGGR(-) is realized as:
(Woh (( g " cuse
Qdat, = softmax
Vd
In cases where tables with multiple foreign keys are not present, there is only a source and destination node-type, so the fusion operation is not needed. We directly substitute h with hare in Equation (5):
(+1) (dst,sce) = AGGR(h ((h0) are
aser
(6)
AGGR(b ( dat ((120 H1)
W proj proj a
We use different weight matrices in Equation (4) and Equa- tion (5) for each atomic route, enabling REL CEL.GNN to capture different types of information across routes.
Σ
Oldst,fuse Wyho
(5)
Euse (ssneEA((cst))
where the attention coefficients fuse are computed via multi-head attention (with the multi-head notation omitted
Finally, the destination node aggregates information from atomic routes related using simple summation and
6

---

RELGNN: Composite Message Passing for Relational Deep Learning
updates its embedding:
For baselines, we compare with the heterogeneous Graph- SAGE (Hamilton al., 2017; Fey & Lenssen, 2019; Robin- son et al., 2024) used in the original RELBENCHI paper. To ensure fair comparison, we maintain identical settings, including the data processing pipeline and training table, the temporal neighbor sampling algorithm, the initial node em- beddings extraction model, the prediction head, and the loss function. We also incorporate Light Gradient Boosting Machine (LightGBM) (Ke et al., 2017) as an additional non- RDL baseline, which is applied directly to the raw entity ta- ble features, following the setting in Robinson et al. (2024).
h (1+1)
(++1) m
dst
(dT()st)
where T(dst) denotes the set of atomic routes with dst as the destination node, and m (1+1) denotes the message from atomic route f, as defined in Equation (3) or Equation (6). Note that this final update operation will not lead to in- formation entanglement, as the model learns distinct weight matrices for each atomic route, therefore learning to assign an appropriate weights to message from each atomic route during the summation.
5.1. Entity Classification
5. Experiments
Experimental Setup. The entity classification task in- volves predicting binary labels for a given entity at specific seed time. The performance is evaluated with the ROC-AUC (Hanley & McNeil, 1983) metric, where higher values indi- cate better performance. The prediction head for this task consists of multi-layer perceptron (MLP) applied to the GNN-generated node embeddings. The model is trained using binary cross-entropy loss. All results are averaged over five different seeds.
We evaluate RELGNN on RELBENCH (Robinson et al., 2024), a public benchmark designed for predictive tasks over relational databases using GNNs. RELBENCH offers diverse collection of real-world relational databases and realistic predictive tasks. The benchmark covers 7 datasets, each carefully processed from real-world sources across diverse domains such as e-commerce, social networks, medical records, Q&A platforms, and sports. These datasets vary significantly in size, with differences in the number of rows, columns, and tables, serving as a challenging and comprehensive benchmark for RDL model evaluation. Appendix A.1 provides description and detailed statistics for each dataset.
Results. Table 1 presents the results, along with the rel- ative improvement of RELGNN over the standard hetero- geneous GNN. RELGNNN outperforms the baselines on 10 out of 12 tasks and achieves comparable performance on the remaining two. Notably, the relative gain is more sig- nificant on datasets with more complex primary-foreige key structure (e.g., rel-f1; see Appendix B for visualiza- tions). In contrast, performance improvements are smaller on datasets with simpler primary-foreign key structures, like rel amazon and rel-hm. This trend aligns with the core design principle of RELGNN, demonstrating that its performance gains arise from effectively highlighting key predictive signals and eliminating redundant message ag- gregation-key challenges faced by standard heterogeneous GNNs when applied directly to relational entity graphs
RELBENCH introduces 30 predictive tasks covering a wide range of real-world use cases, grouped into three representative types: entity classification (Section 5.1). entity regression (Section 5.2), and recommendation (Section 5.3). These tasks are designed to reflect practical applications, such as predicting event attendance, estimating sales of an item, and recommending posts to users. The data is split temporally, with models trained on data from earlier time periods and tested on data from future time periods. To attach target labels, each task defines a training table that links entities of interest to their target labels and timestamps via foreign keys, enabling automatic supervision from historical data while ensuring temporal consistency during training. The tasks vary significantly in the number of entities in the maain/valiattiontees split and the proportion of test entities encountered during training. Detailed description of each task can be found in Appendix A.2.
Discussion and Limitations. On the rel-stack dataset, RELGNN does not achieve significant improve- ments. A potential cause might be the unique self-loop structure, where primary-foreign key links connect nodes of the same type (posts). This pattern does not present in other datasets in BELBENCH and introduces an orthogonal modeling challenge. We provide a potential solution in Ap- pendix D. Since robust handling of self-loops is orthogonal to our core contribution, we leave it for future work.
We follow the data processing pipeline introduced in Robin- son et al. (2024). Relational data is transformed into hetero- geneous temporal graphs, and temporal neighbor sampling is used to construct subgraphs centered around each entity and timestamp. Initial node embeddings are extracted from raw table attributes using Py Torch Frame (Hu et al., 2024). Final node embeddings are passed to prediction heads specific to the type of task to generate final predictions.
5.2. Entity Regression
Experimental Setup. Entity regression task requires predicting numerical labels for an entity at a specific seed time. The evaluation metric Mean Absolute Error
7

---

RELGNN: Composite Message Passing for Relational Deep Learning
Table I: Entity classification results (ROC- (OC()),(%) higher is better) on RELBENCH test set. Best values are in bold.
Table 2: Entity regression results (MAE, lower is better) on RELBENCH test set. Best values are in bold.
Dataset
Tack
LightGBM
Hetern- GNN
RELGNN
(ours)
Rriathe Gain
Datnse
Task
LightGBM
Hetero- GNN
RELGNN
(ouP)))
Relative Gain
rel-anaron
62.54
52.22
70.42
62.81
201 col-enazon
uscr-1cV
item-1cc
16.783
60.569
50.000 30.053
14.313
45.767
14.230
3%
1%
zel-avito
sesernp..oo Lock
$3.05
$3.60
66.20
65.90
66.25
66.
0%
4%
rel-avito
ad-otz
0.041
0.037
10%
xel-ovant
use2 Aquosa
user-cepeat
79.93
69.00
81.62
76.
79.61
4%
201-f1
rel leveent
deiver-ocaition
aser-attendee
4.170
0:264
0.258
4.022
0,238
3.798
6%
6%
xel-c1
driver-dof drivee-top3
73:92
08.56
75.54
72:
75.29
85.69
13%
4%
(h) hr
iten Mallx
0.076
0.056
0.054
4%
(wl at
powt votex
0.068
0.088
0.065
0%
rel-to
user-churn
$5.21
69. 88
70.93
2%
rol-stack
Lsor-engsgaront
usor-tadge
63.43
63.39
90.72 75
85,98
rel-triel
study-adverse
aite
44.011
0.425
44.473
0.400
44.461
0.301
0%
xel-teial
ctady-cuttoree
70.09
68.00 00
71.24
47%
GNN (Wang et al., 2019a) and an identity-aware GNN (ID-
(MAE), where lower values indicate better performance. The prediction head is an MIPP applied to GNN-generated node embeddings, identical to the setup used for entity classification. The model is trained using LI loss. Results averaged over five random seeds.
GNN) (You et al., 2021). The two-tower GNN calculates pairwise scores through the inner product of source and target node embeddings and is trained using the Bayesian Personalized Ranking loss (Rendle et al., 2012). ID-GNN computes scores by applying an MLP to the embedding of the target entity within the subgraph sampled around each source entity and is trained using binary cross-entropy loss. Consistent with the original implementation, we use two- tower GNN for tasks in rel-eellaee -amazon dataset and ID-GNN for tasks in the remaining datasets. The evaluation metric is Mcan Average Precision (MAP) @ K, where higher values indicate better performance. All results are averaged over five seeds.
Results. Table 2 presents the results and the relative gain of our model over the standard heterogeneous GNN. REL- GNN outperforms the baselines on 8 out of 9 tasks and achieves comparable performance on the remaining one. As in the classification task, improvements are most pro- nounced datasets with complex primary-foreign key structures, highlighting that RELGNNN' effectiveness in modeling relational structure translates to consistent gains in both classification and regression settings.
Results. Results are presented in Table 3. REL- GNN achieves better same performance compared to baselines on all 9 tasks. These consistent improvements across diverse datasets and tasks underscore the versatil- ity of our approach and demonstrate its effectiveness in modeling complex relational information and extracting key predictive signals crucial for recommendation.
Discussion and Limitations. The performance gain on rel-stack is limited, as discussed in Section 5.1. We also observe divergent results across tasks in the rel-trial dataset. potential cause might be the inher- ent limitation of the prediction head for the entity regression task rather than the GNN model itself, noted in the origi- nal RELBBENCH paper (Robinson et al., 2024). In particular, advveed involves estimating an unbounded target (the number of patients with severe outcomes), while s sitcesss predicts a bounded success rate. One possible explanation is that unbounded predictions may be more challenging given the inherently constrained design of the regression head. Enhancing prediction heads for regression tasks is an important direction for future work.
Discussion and Limitations. One limitation comes from the ID-GNN prediction head, which restricts recommenda- tion candidates to nodes sampled within the source entity's s subgraph for efficiency. This limitation is quantified by the locality score (Yuan et al., 2024), which measures the fraction of ground-truth targets present in the sampled subgraph. A high locality score suggests users tend to re-engage with previously interacted entities, while a low score indicates a preference for novel items. ID-GNN struggles on low-locality tasks where ground-truth targets often fall outside the sampled subgraph. Accordingly,
5.3. Recommendation
Experimental Setup. Recommendation tasks involve pre- dicting ranked list of top K target entities for a given source entity at specific seed time, where K is predefined per task. This requires computing pairwise scores between source and target entities. We follow REL BENCH implemen- tation and use two types of prediction heads: a two-tower
REL.GNI shows greater gains on high-locality tasks (e.g.. rel rel-stack) than on low-locality ones (e.g., rel-hm, rel-trial). Designing improved prediction heads for recommendation tasks is orthogonal to our core contribution and remains a valuable direction for future work.
8

---

RELGNN: Composite Message Passing for Relational Deep Learning
Table 3: Recommendation results (MAP()), higher is bet- ter) on RELBENCH test set. Best values are in bold.
Distinction between RDL and Knowledge Graphs. The literature of knowledge graphs (Bordes et al., 2013; Wang et al., 2014; 2017) differs from RDL in terms of the tasks being tackled. Knowledge graph models mainly focus on completion tasks like predicting missing entities (e.g., Q: Who is the author of Harry Potter? A: J.K. Rowling) or missing relationships (e.g. Q: Did Yoshua Bengio win a Tur- in Award? A: Yes). In contrast, RDL focuses on making predictions about entities groups of entities in the future timestamp (e.g.. Will a customer churn in the next month?
Dutase
Task
LightBM
Hetern-
REUGNN
(surs)
Relathee Gain
usse- Loa puzchhsse
0.18
0.74
0.77
4%
user-It res-raae
0.17
0.87
0.82
uaee Liam peoiay
0.09
0.47
0.52
1155
rel-avito
user-ad-vtele
0.06
3.05
3.84
6%
ra2-be
UsBE Ltwa puzchese
0.38
2.91
2.81
0%
woRr-poot-coo -comert
0.04
12.72
14.00
10%
post pest-reeateee related
2,00
10.83
11.06
8%
rel-evin3
condi: Modil:oone spensopooo--
aite- aponsor-pur.
5.40
4.52
11:36
19.00
19.14
11.55
2%
1%
How much will customer spend in the upcoming week?)
6. Related Work
7. Conclusion
Deep Learning on Relational Data. Several works have explored the use of GNNs for learning on relational data (Schlichtkrull et al., 2018; Cvitkovic, 2019; Sir, 2021; Zahradník et al., 2023; Kanatsoulis et al.. 2025). These works investigated different GNN architectures that utilize the relational structure. More recently, Fey et al. (2024) introduced Relational Deep Learning (RDL) (cf. Sec. 2.2), establishing a new subfield of machine learning. RDL has enabled various research opportunities, such as advancements in relational graph construction algorithms, GNN architectures, and task-specific prediction heads. Yuan et al. (2024) focused on improving recommendation tasks by addressing limitations of the currently employed two-tower and pair-wise wise prediction heads. In contrast, our work focuses on improving GNN architectures applied to all task types, offering an orthogonal contribution. Recently, series of works have explored the use of large language models (LLMs) for heterogeneous graphs. HiGPT (Tang et al., 2024) introduced a language-enhanced heterogeneous graph tokenizer combined with LLMs. Wydmuch et al. (2024) proposed leveraging L.LMs for predictive tasks in RDL, showing improvements on certain node-level tasks.
In this paper, we introduced RELGNN,, novel graph neu- ral network framework specifically designed to address the structural inefficiencies of existing heterogeneous GNNs for relational databases. By leveraging atomic routes, we designed a composite message passing mechanism that en- ables direct single-hop interactions between the source and destination nodes. This avoids redundant aggregation and highlights key predictive signals, leading to more efficient and accurate predictive modeling. Through extensive eval- uation on RELBENCH, a diverse benchmark covering 30 predictive tasks across 7 relational databases, RELGNN outperforms state-of -aate-of-tie wat---ffthhheee the-art baselines on the vast majority of tasks, achieving up to a 25% improvement in predictive accuracy. Our findings emphasize the limitations of conven- tional heterogeneous GNNs when applied to relational data and highlight the necessity of models that explicitly account for primary-foreign key relationships.
A Acknowledgments
We thank Rishabh Ranjan and Vijay Prakash Dwivedi for discussions and for providing feedback on our manuscript. We also gratefully acknowledge the support of NSF under Nos. OAC-1835598 (CINES), CCF--118944 (Expeditions). DMS- 23277237709 (IHBEM), IIS-2403318 (III;; Stanford Data Applications Initiative, Wu Tsai Neurosciences Institute, Stanford Institute for Human-Centered AI, Chan Zuckerberg Initiative, Amazon, Genentech, GSK, Hitachi, SAP, and UCB.
Meta-paths in Heterogeneous Graphs. Meta-paths (Sun et al., 2011) are widely used in heterogeneous graph Iearn- ing to capture semantic relationships between different types of entities (Shang al., 2016; Dong et al., 2017: Hu al., 2018; Shi et al., 2018; Wang al., 2019b; Fu al., 2020). A meta-path is a manually designed sequence of node and edge-types in a heterogeneous graph intended to capture spe- cific relational patterns. For example, in an academic graph, a meta-path Author-Paper-Author models co-authorship, and a meta-path Wwwphhor-PPpe--oofeeeeeee PatprrencceePpe--uuuhr captures co-conference patterns. While effective in many settings, meta-paths have some known limitations (Shi et al., 2016; Hu et al., 2020; Shi, 2022). They typically rely on manual specification, which requires domain expertise and may introduce bias or overlook important patterns. Designing an effective set of meta-paths for complex graphs can be consuming and may fail to comprehensively capture all relevant interactions.
The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding entities.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
9

---

RELGNN: Composite Message Passing for Relational Deep Learning
References
Hu, B., Shi, C., Zhao, W. X., and Yu, S. Leveraging mrea--ptth based context for top-n recommendation with neural co-attention model. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 1531-1540, 2018.
Bordes, A., Usunier, N., Garcia-Duran A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems (NeurlPS), 2013.
Hu, W., Yuan, Y., Zhang, Z., Nitta, A., Cao, K., Kocijan, V., Leskovec, J., and Fey, M. Pytorch frame: A modu- lar framework for multi-modal tabular learning, arXiv preprint XXi:24404.00776 2024.
Chen, T. and Guestrin, C. Xghoost: A scalable tree boosting system. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp. 785-794, 2016.
Cong. W., Zhang. S., Kang, J., Yuan, B., Wu, H., Zhou, X., Tong, H., and Mahdavi, M. Do we really need compli- cated model architectures for temporal networks? In The Eleventh International Conference on Learning Repre- sentations.
Hu, Z., Dong, Y., Wang, K. and Sun, Y. Heterogeneous graph transformer. In Proceedings of the web conference 2020, pp. 2704-2710, 2020.
Huang, Y., Lu, W., Robinson, J., Yang. Y. Zhang, M., Jegelka, S., and Li, P. On the stability of expressive posi- tional encodings for graphs. In The Twelfth International Conference on Learning Representations.
Corso, G., Cavalleri, L.,, Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. Advances in neural information processing systems, 33: 13260-13271, 2020.
Kaggle. Kaggle Data Science & Machine Learn- ing Survey, 2022. Available: https://wwwt taggle.com, www.////////ccceee//oooeoeeeeeee http://dd/pplllaaee
//wp:://www.
Cvitkovic, M. Supervised learning on relational databases with graph neural networks. ICLR Workshop on Repre- sentation Learning on Graphs and Manifolds, 2019.
soogle-ssrrey. 2022-2222222000 aall-ll--- hall-results/ notebook.
Dong, Y., Chawla, N. V., and Swami, A. metapath2vec: Scalable representation learning for heterogeneous net- works. In Proceedings of the 23rd ACM SIGKDD inter- national conference knowledge discovery and data mining, pp. 135-144, 2017.
Kanatsoulis, C. I., Choi, E., Jegelka, S., Leskovec, J., and Ribeiro, A. Learning efficient positional encodings with graph neural networks. arXiv preprint arXiv:2502.01 122, 2025.
Kazemi, S. M., Goel, R., Eghbali, S., Ramanan, J., Sa- hota, J., Thakur, S., Wu, S., Smyth, C., Poupart, P., and Brubaker, M. Time2vee: Learning a vector representation of time. arXiv preprint 1907.05927532 2019..
Fey, M. and Lenssen, Fast graph representation learning with pytorch geometric. ICLR 2019 (RLGM Workshop), 2019.
Fey, M., Hu, W., Huang, K., Lenssen, J. E., Ranjan, R., Robinson, J., Ying, R., You, J., and Leskovec, J. Rela- tional deep learning: Graph representation learning on relational databases. ICML Position Paper, 2024.
Ke, G., Meng, Q., Finley, T., Wang. T., Chen, W., Ma, W., Ye, Q., and Liu, T.-Y. Lightghm: highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Fu, X., Zhang, J., Meng, Z., and King, I. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of the web conference 2020, pp. 2331-23310 233112341,200 2020.
Rendle, S., Freudenthaler. C., Gantner, Z., and Schmidt- Thieme, L. Bpr: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv: 1205.2618. 2012.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International Conference on Machine Learning (ICML), pp. 1263-1272, 2017.
Robinson, J., Ranjan, R., Hu, W., Huang, K., Han, J., Dobles, A., Fey, M., Lenssen, J. E., Yuan, Y., Zhang, Z., He, X., and Leskovec, J. Relbench: A benchmark for deep learning on relational databases. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL https: //oenrevieww net/ / forummormm///m WWI
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Hanley, J. A. and McNeil, B. J. A method of comparing the areas under receiver operating characteristic curves derived from the same cases. Radiology, 148(3):839-88) 843, 1983.
Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In Gangemi, A., Nav- igli, R., Vidal, M.-F., Hitzler, P., Troncy, R., Hollink, L..,
10

---

RELGNN: Composite Message Passing for Relational Deep Learning
Tordai, A., and Alam, M. (eds.), The Semantic Web, pp. 593-607, Cham, 2018. Springer International Publishing-
Wang, Q.. Mao, Z.,, Wang, B., and Guo, L. Knowledge graph embedding: survey of approaches and applications. IEEE Transactions Knowledge and Data Engineering, 29(12):2724 2743, 2017.
Shang, J., Qu, M., Liu, J., Kaplan, L.. M., Han, J., and Peng. Meta-path guided embedding for similarity search in large-scale heterogeneous information networks. arXiv 2016.
Wang. X., He, X., Wang, M., Feng, F., and Chua, T.-S. Neural graph collaborative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pp. 165-174, 2019a.
preprint
Shi, C. Heterogeneous graph neural networks. In Wu, L.., Cui, P., Pei, J., and Zhao, L.. (eds.), Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 351-369, Springer Singapore, Singapore, 2022.
Wang, X., Ji, H., Shi, C., Wang, B., Ye, Y., Cui, P., and Yu, P. S. Heterogeneous graph attention network. In The world wide web conference, pp. 2022-2032, 2019b.
Shi, C., Li. Y., Zhang, J.. Sun, Y., and Philip. S. Y. A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering, 29 (1):17-37, 2016.
Wang. Z., Zhang, J., Feng. J., and Chen, Z. Knowledge graph embedding by translating on hyperplanes. In Pro- ceedings of the AAAI conference artificial intelligence, volume 28, 2014.
Shi, Y., Zhu, Q.. Guo, F., Zhang, C., and Han, J. Easing embedding learning by comprehensive transcription of heterogeneous information networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2190-21999 2018.
Wydmuch, M., Borchmann, L., and Graliñski. F. Tackling prediction tasks in relational databases with Ilms. arXiv preprint arXiv:2411.11880 2024.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In International confer- ence on machine learning, pp.
Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified mes- sage passing model for sumi-super classification. In Zhou, Z. (ed.), Proceedings of the Thirtieth In- ternational Joint Conference on Artificial Intelligence, IJCAI-21, pp. 1548-1554. International Joint Confer- ences on Artificial Intelligence Organization, 8 2021. doi: 00.24966/ijccai.22212222 1021/14 10.24963. 11199//ijcai... 2222/2244 Main Track.
PMLR, 2018.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
URL https::////.. /tw.oooooooooooooo
You, J., Gomes-Selman, J. M., Ying, R., and Leskovec, J. Identity- aware graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, pp. 10737- 10745, 2021.
Šír, G. Deep Learning with Relational Logic Representa- tions. Czech Technical University, 2021.
Sun, Y., Han, J., Yan, X., Yu, P. S., and Wu, T. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endow- ment, 4(1 ((11):92221000000 1003, 2011.
Yuan, Y., Zhang, Z., He, X., Nitta, A., Hu, W., Wang, D., Shah, M., Huang, S., Stojanovič, B., Krumholz, A., et al. Contextgnn: Beyond two-tower recommendation systems. arXiv preprint arXiv:2411.19511 2024.
Tang, J., Yang. Y., Wei, W., Shi, L., Xia, L., Yin, D., and Huang, C. Higpt: Heterogeneous graph language model. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2842-2853, 2024.
Zahradník, L., Neumann, J., and Šír, G. A deep learning blueprint for relational databases. In NewrlPS 2023 Sec- ond Table Representation Learning Workshop, 2023.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.

---

RELGNN: Composite Message Passing for Relational Deep Learning
Table 4: Statistics of RELBENCI.
#Rows training table
#Unique
fétrainkest
Lype
Validation
Text
Farny Overlap
uscr-churn
clasaification
4.732,555
351,885
1,385,983
Iten-churn
chuselfication
2,559.264
177,689
166.842
416.352
93.1
zel-anazon
iton-ity
user-ity
regression
regression
2.707,679
4.732.555
409,792
166,978
351,855
1763334
427,537
1.585,922
93.5
$3.0
oser-iten-pune
seer-iten-purrcheee
5,112,803
351,876
uscr-item--rate
recommendiiion
3,067.157
257,939
292,609
1,481,3600
$1.0
user-iten-revi.e
recommendsion
2
116,970
127.001
894,136
74.1
usez-clicka
clussiication
99,454
21,185
47,99%
66,489
45.3
rel-avito
adroLi usez-ad-viait
cloccilication
regression
S6619
29,979
1,766
36,120
1,816
63,405
64.6
recommandzzion
96,616
29,979
36,129
UScI-xc70a
classification
rel-event
user-ignore user-sttendance
chaseliicttion
19.239
4,185
4,010
9,799
21.1
regression
19.261
2,014
2,006
9.694
14.6
driver dnf doiver-Lop3 driver-position
chsciiiiction
11.411
366
702
821
50.0
se1-F1
clscsification
1,353
588
726
134
50.0
regression
7.453
499
826
user-churn iten-sales
classifiction
3,871,10
76,556
74,575
1,02,9844
89.7
re1-hm
regression
user-iten-purchh
recommedssron
3,878.451
74,575
67,144
1004,066
user engegement
clessilication
1,300,80
85,838
88,137
58,137
uses badoe
classiliation
3,386,276
247.395
250
255,360
96.9
rel-stack
post-votes
regression
2,453,921
156,216
160903
100,903
97.1
post
recommcadztion
825
post post-poat post- reattrelated
recommaadzzion
226
8.5
study-cutcom stady-advcrse cite-sucoese
clasiffcation
11, 1..944
960
13,779
0.0
regression
43.335
3,596
3,098
50,029
0.0
rel-tzial
regression
151,407
19,740
22,617
129,542
42.0
condition-sppasere cite-sponsos-ruh
36,934
2,081
3,956
recommendaion
37,003
A. RELBENCH Details
In this section, we provide detailed description and related statistics of RELBENCH. Table 4 provides detailed statistics for each dataset and task.
A.1. Datasets
RELBENCH consists of datasets, covering a diverse range of domains and scales. Below is a detailed description for each dataset.
rel-amazon. The Amazon E-commerce dataset contains product, user, and review interactions on Amazon's 's platform. It includes product metadata (e.g., price, category), review details (e.g., rating, text), and user engagement.
rel-avito. Avito, major online marketplace, facilitates buying and selling across categories such real estate, vehicles, and consumer goods. This dataset contains user search queries, ad characteristics, and additional contextual data for developing predictive models.
rel-event. The Event Recommendation dataset derived from Hangtime, mobile app that tracks users' social plans. contains user interactions, event metadata, demographic information, and social network connections, offering insights into how social relationships influence user behavior.
rel-f1. The Fl dataset records comprehensive Formula 1 racing data since 1950, covering drivers, constructors, engine and tire manufacturers, and race circuits). includes historical race results, season standings, and granular data on practice sessions, qualifying rounds, sprints, and pit stops.
rel-hm. The H&M dataset captures customer and product interactions from the retailer's e-commerce platform. includes metadata on customers and products (e.g., demographic attributes, product descriptions), and purchase histories.
12

---

RELGNN: Composite Message Passing for Relational Deep Learning
rel-stack. Stack Exchange is network of Q&A websites where earn reputation based contributions. The dataset contains detailed activity logs, including user biographies, posts, comments, edit histories, votes, and linked questions.
The clinical trial dataset, sourced from the AACT initiative, aggregates study protocols and results. It includes trial design details, participant demographics, intervention specifics, and outcome measures, serving valuable resource for medical research and policy analysis.
rel-trial.
A.2. Tasks
The following list outlines the description predictive tasks included in RELBENCH.
1. rellamazon
(a) user-churn: Predict whether user will stop reviewing products within the next three months.
(b) item-churn: Predict whether a product will receive no reviews in the next three months.
(c) user-ltv: Estimate the total dollar value of products
will purchase and review the next three months.
(d) item-ltv: Estimate the total dollar value of purchases and reviews a product will receive in the next three months
(e) user-item paasmpppcchsee Predict the of items a user will purchase in the next three months.
(1) user-item- rate: Predict the set of items a user will purchase and rate five stars in the next three months.
g user-item-reviers Predict the set of distinct items a user will purchase and write a detailed review for in the next three months.
2. rel- rel-avito
(a) user-visits: Predict a user will interact with multiple ads within next four days.
(b) user-clicks: Predict if a user will engage with more than one ad by clicking within next four days.
(c) ad-ctr: Estimate the through rate for an ad, assuming it receives a click within four days.
(d) user-ad-vil Predict the list of ads a user will visit within next four days.
3. rel-event
(a) user-attendance: Predict the number of events user will RSVP "yes" or "maybe" to in the next seven days.
(b) user-repeat: Predict whether a user will attend an event (by responding "yes" or "maybe") in the next seven days, given they attended an event in the last 14 days.
(c) user-ignore: Predict whether user will ignore more than two event invitations in the next seven days.
4. rel-fi fl
Node-level tasks:
(a) driver-dnf: Predict whether driver will fail finish race within the next month.
(b) driver-top3: Predict a driver will secure a top-three qualifying position in race within the next month.
(c) triver-positinn Predict driver's average finishing placement across all races in the next months.
5. rel-hn
Node-level tasks:
(a) churnchurn: Predict a customer will become inactive (no transactions) in the next week.
(b) item-sales: Predict total revenue generated by article in the upcoming week.
(c) user-item-pe purchassee Predict the list of articles a customer will over the next seven days.
6. rel-stack
13

---

RELGNN: Composite Message Passing for Relational Deep Learning
(a) user-engagement:: Predict whether user will participate by voting, posting, commenting within the next three months.
(b) user-badge: Predict if a user will earn a new badge within the next three months.
(c) post Predict the number of votes user's post will receive over the next three months.
(d)
Predict which existing posts a user will comment on in the next two years.
(c) post-post-relatee Identify a list of existing posts that will be linked to given post within the next two years.
7. rel-triat
(a) study-outeome: Predict if clinical trial will meet its primary outcome within the next year.
(b) study-adverse: Estimate the number of patients who will experience severe adverse events or death in a clinical trial over the next year.
(c) site-success: Predict the success rate of a trial site in the next year.
(d) condition condition-sponsor--- sponsor- run: Predict which sponsors will be associated with a particular condition.
(e) site-sponsor--aee Predict whether a specific sponsor will conduct trial at given facility.
B. Visualization of Primary-Foreign Key Relationships
We visualize the primary-foreign key relationships of all datasets in RELBEnCH in Figure 4 (rel-f1 visualized in Figure (a)).
C. Ablation Study
To isolate the contribution of atomic routes, we conduct an ablation study comparing variants of RELGNN with and without the attention mechanism. In our instantiation and main experiments, the FUSE operation of RELGNN is instantiated using the same design as GraphSAGE (cf. Equation (4)). For this ablation, we additionally configure the AGGR operation to use GraphSAGE-style aggregation instead of attention. This ensures that the only architectural difference between the baseline and RELGNN is the inclusion of atomic routes.
As shown in Tables 6, and 7, RELGNN achieves consistent gains over the baselines, even when using the same aggregation mechanism. Notably, the performance improvement is not attributable to attention alone: the gap between RELGNN with and without attention is modest. These results indicate that the performance gains stem primarily from the use of atomic routes, which enable more efficient and targeted message passing across relational structures.
We also include additional baselines using GAT (Veličković et al., 2018) and GIN (Xu et al., 2019) as backbone architectures. As shown in Tables 6, and 7, Nooupprruss all baselines regardless of the backbone GNN.
D. Aditionaal Discussion
Scalability and Efficiency in Large Relational Databases. A common concern is whether the complexity of computing atomic routes increases with database size. In our framework, atomic routes are computed at the schema graph level, where nodes represent table types rather than individual entities. Even large databases with millions of rows, the number of table types typically remains in the tens. This schema-level design makes RELGNN agnostic to the number of entities and allows scale efficiently as the database grows.
Another related concern is the complexity introduced by tables with many foreign keys. In practice, follow the standard RDL sampling strategy, which samples fixed-size local neighborhood around each seed node. As result, only subset of the foreign key links is activated at training or inference time. The number of active connections remains bounded by the sampling configuration, ensuring that the message passing remains efficient even when some tables connect to many others.
A Potential Approach for Handling Self-Loop Tables. Although self-loop tables are rare in relational databases (only 1 out of 7 datasets in RELBENCH) it is worthwhile to improve the model handling of such cases. The key to addressing this challenge is enhancing the model's ability to distinguish messages coming from the same table type (for self- tables) versus those from different types (for non-self-loop tables). To address this, we propose incorporating relative positional
14

---

RELGNN: Composite Message Passing for Relational Deep Learning
rel-amazon
rel-hm
(a) rel-amazon
(b) rel-hm
rel-avite
rel-event
Vildtraan
EXET,
Usetnto
Locatin
Adinnto
Hance
(c) rel-avito
(d) re rel-evert
rel-trial
rel-stack
deiggs
withdrasd
reporeed Jara
pertinia
ostore enabses
badge
Intenertions
conditore
(e) rel-stack
(f rel-trial
Figure 4: Primary-foreee key relationships of datasets in RELBENCH.
15

---

RELGNN: Composite Message Passing for Relational Deep Learning
Table Ablation results for entity classification (ROC-AUC((S), higher is better) on RELBENCH test set. The best values are bold, and the second-best values are underlined.
RELGGNN w/o attn
Dataset
Task
GraphSAGE.
GAT
GIN
RELGNN
user-churn
70.42
63.21
70.50
70.99 82.64
70.90
rel-amazon
item-churn
82.81
69.99
82.74
82.94
user-visits user-clicks
66.20
64.82
65.96
66.18
66.80
rel-avico
65.90
65.85
66.04
68.23
66.72
xel-event
user-rt
76.89
68.24
74.35
79.61
78.82
ignore
81.62
82.04
79.54
86.18
85.58
driver-dn
72.62
75.29
rel-fl
driver-top3
75.54
73.64
85.69
rel-hm
user-churn
69.88
64.72
69.91
70.93
usgg-engagement
90.59
89.59
90.53
90.75
90.70
rel-stack
user-badge
88.86
84.51
88.72
88.99
rel-trial
study-out.com
68.60
66.19
68.44
71.24
69.34
Table 6: Ablation results for entity regression results (MAE, lower is better) on RELBENCH test set. The best values are in bold, and the second-best values are underlined.
RELGNN w/o attn
Dataset
Task
GraphSAGE
GAT
GIN
RELGNN
uaer-itv item-ltv
14.313
16,626
14.318
14.230
14.240
rel-amazon
50.053
58.902
50.087
76.
48.282
rel-avito
ad-ctr
0.041
0.041
0.037
rel-event
uaer-attendance
0.258
0,263
0.264
0.238
0.238
rel-fl
driver-positien
4.022
4.268
4.072
3.798
3.792
re1-hm
item-sales
0.056
0.079
0.055
0.054
0.053
rel-stack
poat-votea
0.065
0.068
0.065
0.065
0.065
rel-trial
study-adverse
44.473
46.026
44.400
44.461
45.531
si.e-succeas
0.400
0.393
0.398
0.301
0.354
Table 7: Ablation results for recommendation results (MAP(%), higher is better) RELBENCH test set. The best values in bold, and the second-best values are underlined.
RELGNN w/o atin
Dataset
Task
GraphSAGE
GAT
GIN
RELGNN
user-it ieer-itee-purcchaan
0.69
0.77
rel-amazon
user-iten-rate
0.87
0.78
0.78
0.92
0.89
ascr-iton-revicw
0.47
0.29
0.42
0.52
0.59
rel-avito
user-ad user-ad-vies
3.66
1.99
3.66
3.94
3.96
rel-hm
nser-item-purchasee
2.81
1.88
2.80
2.81
2.83
user-past-corment
12.72
11.97
12.81
14.00
13.66
rel-stack
post post related
10.83
10.71
10.78
11.66
11.38
condi:i onndinoooos
11.36
10.43
11.32
11.55
11.44
rel-trial
site-sponsor-run
19.00
17.90
18.91
19.14
19.08
16

---

RELGNN: Composite Message Passing for Relational Deep Learning
encoding (RPE) over the schema graph (where nodes table types and edges are primary-foreign key relations). RPE helps the model identify whether two tables of the type and also offers additional benefits. Since the schema graph defines the database structure at macro level, it can provide global relational context that complements the local structural information captured by GNNs on the relational entity graph. Moreover, schema graphs are typically small (with only tens of nodes even in large databases) and static, so the RPE can be precomputed once with negligible overhead and reused throughout training and inference.
To evaluate, we implemented an RPE method based on Huang et al.: eigen-decompose the Laplacian of the schema graph Vdiag(AVV apply m element-wise MLPs dx(-) to obtain Q Q[i,i. ;, V
for k E [m], resulting in tensor E I NxxN and project via MLP p to obtain RPE = p(Q) NxNxd where N is the number of node-types of d is the dimension of node embeddings. For a message from node-type i to j. we update the original message m as m = m + a RiE j] with learnable a. This resulted in a 2% improvement on both classification tasks in rel-stack, which contains self-loops.
Integration with Advanced Components. We focus on improving the core design of message passing, but the REL- GNN framework is flexible and accommodates more advanced components.
Advanced GNN Aggregators. RELGNN allows easy integration of different GNN aggregators by re-instantiating the AGGR operation in Equation (5). For example, PNA (Corso et al., 2020) improves expressiveness by combin- ing multiple aggregators and degree-scalers. It can be integrated into RELGNN by instatiating Equation (5) with
AGGR(h (1) {1h faee }}) W hroj
(1)
(t) + E, EfaseNN(dst) A (!)
( where M-) the PNA operator. Model-agnostic
aggregators can also be integrated on top of RELGNN. For instance, Jumping Knowledge Network (Xu al., 2018 8) improves performance by adaptively combining representations from multiple layers. This can be implemented by collecting outputs from each RELGNN layer and passing them to PyG's JumpingKnowledge module, with the result used as input to the final prediction layer.
Effective Time Encodings. Many RDL. tasks involve temporal prediction, and various temporal encodings can be incorporated as additional node features for REL GNN. For example, Teme2Vec (Kazemi et al., 2019) maps timestamps = sin + 6:) with learnable parameters Wi and Φ;. GraphMixer (Cong et al.) introduces a fixed time encoding - cos(tw), where s {a- - } and the choice of a; 3 depends on the dataset's time range. These techniques are compatible with RELGNNam introduce minimal overhead.
to Rd via Time2Ved
17


Reviews:
[{"review_id": "tcJGTmZkxE", "reviewer": "Reviewer_pL7w", "summary": "The manuscript proposes RelGNN, a graph neural network framework tailored for relational deep learning (RDL), enabling predictive modeling on relational databases. RelGNN introduces atomic routes, which capture high-order tripartite structures to facilitate direct single-hop interactions between heterogeneous nodes. By designing a composite message passing mechanism based on atomic routes, RelGNN completes the two-step information exchange in a single step with an attention mechanism. RelGNN is empirically evaluated on 30 tasks from RelBench [1] which consists of entity classification, entity regression, and recommendation.\n\n[1] Fey et al., “Relational Deep Learning - Graph Representation Learning on Relational Databases”, ICML Position Paper, 2024.\n \n \n\n## Update after rebuttal\nThe paper could benefit from including additional evidence to support the main claim and existing heterogeneous GNNs with relevant adjustments in the experiments.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and address each concern as follows:\n\n> Regarding Justification of Claims\n\nThe message passing process through an intermediate node introduces an imbalance: the source node’s signal is aggregated twice, while signals from intermediate nodes are only aggregated once. In RDL, the source nodes typically contain the most critical information for prediction, so preserving a clean, undiluted source signal is essential. Standard heterogeneous architectures attempt to address this issue by employing skip connections and additional components such as MLPs, which must implicitly learn to disentangle the clean source signal from the noise introduced during multiple aggregations. In contrast, our approach explicitly leverages atomic routes and composite message passing to maintain a direct, efficient exchange of information between source, intermediate, and destination nodes. This targeted mechanism minimizes the dilution of the source signal without introducing additional parameters, ensuring that the most critical information propagates effectively through the network.\n\n> Regarding Additional Baselines\n\nThe reviewer asks for additional baselines. Our original choice of baselines was intended to maintain consistency with prior work [1]. In response to the reviewer’s suggestion, we conducted experiments using GAT [2] and GIN [3] as backbone architectures. As presented in Table 1, the performance remains largely unchanged across different backbone GNN architectures.\n\nRegarding meta-path-based GNNs, these methods require substantial manual effort and domain expertise to select appropriate meta-paths, making them less directly applicable to RelBench. In contrast, our method is fully automated and eliminates the need for such human intervention. We have already discussed meta-path approaches and cited [4,5] in the original manuscript, and we will add the citation [6] in the revised version.\n\n> Regarding Limitations\n\nThe reviewer notes that some limitations are left as future work. We clarify that addressing most of these limitations is orthogonal to our main contribution. RDL is an emerging field, and the pipeline described in [1] opens up research opportunities across multiple dimensions. Our work focuses on the foundational aspect of improving message passing design, while complementary aspects—such as refined prediction heads and improved recommendation frameworks, noted as limitations of the current pipeline—are recognized as independent. By keeping these components constant, we isolate the effect of our proposed message passing method, ensuring a fair comparison. We highlight these limitations to encourage further advancements in the field.\n\n> Regarding Ablation on Model Components\n\nWe appreciate the reviewer’s suggestion for the ablation study.  The FUSE operation of RelGNN is instantiated in the same way as GraphSAGE in our original manuscript. For the ablation study, we further instantiate the AGGR operation with GraphSAGE instead of attention so that the only difference from the baseline is the inclusion of atomic routes. As shown in Table 1-3, the performance gap clearly demonstrates the effectiveness of atomic routes. The attention mechanism itself does not contribute significantly to performance gains (RelGNN w/ attn vs RelGNN wo/ attn; GraphSAGE baseline vs GAT baseline). We will include further details of this ablation study in the revised version.\n\nTable 1. Classification (ROC-AUC, ↑)\n\nTable 2. Regression (MAE, ↓)\n\nTable 3. Recommendation (MAP, ↑)\n\n> Regarding Code and Other Details\n\nWe've now made our source code and model checkpoints available at https://anonymous.4open.science/r/RelGNN for reproducibility. The training setup and experimental details are maintained consistent with [1] to ensure a fair comparison. In the revised manuscript, we will add a section detailing these setup. \n\nThe gray nodes in Figure 2(c) denote training tables, derived in the same manner as in [1]. “Relational Entity Graph” specifically refers to the graph built from relational tables that encompasses all entities, while “Relational Data Graph” is used more generally to refer to any graph constructed from a relational database (e.g., a subgraph sampled from the Relational Entity Graph). We will clarify these points in the revised manuscript.\n\n\nWe hope these clarifications address the reviewer’s concerns and will update the manuscript when permitted.", "claims_and_evidence": "In Section 3.1, the authors claim that standard heterogeneous GNNs entangle irrelevant information when propagating messages through intermediate nodes with two or more foreign keys. However, there is insufficient evidence to support the claim that messages propagated from one-hop or two-hop neighboring nodes of an intermediate node contribute as irrelevant noise. For instance, the authors argue that the “constructors” node introduces noise during the message-passing process to the “standings” node. However, even in a two-hop scheme, the “constructors” node does not contribute to the message-passing process to the “standings” node. Furthermore, in relational databases, the assumption that the information from tables connected via primary-foreign key relationships to a table corresponding to an intermediate node cannot be deemed irrelevant contradicts the rationale for using GNN-based models. Therefore, a clear theoretical justification for this claim is necessary.", "methods_and_evaluation_criteria": "RelGNN is evaluated on the recently proposed RelBench [1]. There is no new benchmark dataset or evaluation criteria.", "theoretical_claims": "There is no formal proof or theoretical justification for the claims made in this manuscript.", "experimental_designs_or_analyses": "The baseline models for evaluating the proposed RelGNN are highly limited. The authors primarily use only the heterogeneous GraphSAGE from the original RelBench [1] as the baseline. However, it is necessary to compare RelGNN with other heterogeneous GNNs that employ different backbone GNN architectures, such as GAT [2] and GIN [3], rather than relying solely on GraphSAGE. Additionally, other heterogeneous GNNs including models that use meta-paths should be included as baselines [4,5,6]. Furthermore, despite the use of only a limited baseline, the performance improvement of RelGNN is not significant.\n\n[2] Veličković et al., “Graph Attention Networks”, ICLR, 2018.\\\n[3] Xu et al., “How Powerful are Graph Neural Networks?”, ICLR, 2019.\\\n[4] Fu et al., “MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding”, WWW, 2020.\\\n[5] Hu et al., “Leveraging Meta-path based Context for Top-N Recommendation with A Neural Co-Attention Model”, KDD, 2018.\\\n[6] Tang et al., “HiGPT: Heterogeneous Graph Language Model”, KDD, 2024.", "relation_to_broader_scientific_literature": "In this manuscript, RelGNN is proposed for predictive tasks on relational databases. However, the rationale behind introducing its main idea, the atomic route, is not clearly justified. Additionally, the limited number and variety of baseline models make it difficult to properly assess the significance of RelGNN.", "essential_references_not_discussed": "References and discussions of the various baseline models mentioned in the “Experimental Designs or Analyses*” section are necessary [2,3,4,5,6].", "other_strengths_and_weaknesses": "- The authors provide reasonable explanations for the experimental results of the proposed model, particularly when its performance is comparable to or worse than the baseline models. However, most limitations have been left as future work without being addressed. Additionally, further discussion is needed after incorporating other baseline models.\n- There is a lack of justification for key model components, such as the attention mechanism and FUSE operation. In particular, without an ablation study on the attention mechanism, it is unclear whether the model’s performance improvements are due to the introduction of atomic routes or the attention mechanism itself.\n- The manuscript lacks a clear explanation of the model’s training methodology. While it can be inferred that the training table was used following previous work [1], this is not explicitly stated, leaving the details of the training and inference process ambiguous. Additionally, the meaning of the gray nodes in Figure 2(c) is not clearly explained, making it difficult to interpret their role.\n- The code/data for the experiments is not provided, and the detailed descriptions of the experimental setup (e.g., number of layers) are insufficient, making it difficult to ensure reproducibility.", "other_comments_or_suggestions": "- In line 373 of the main text, the phrase starting with “tianlangNote to self” in the right column may compromise anonymity.\n- The terms “Relational Entity Graph” and “Relational Data Graph” appear to refer to the same concept, yet they are used inconsistently throughout the manuscript.", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FSHiFHXY30", "reviewer": "Reviewer_935g", "summary": "The paper introduces RelGNN, a graph neural network (GNN) framework specifically designed for Relational Deep Learning (RDL), the task of doing end-to-end predictive modeling directly on relational databases (multiple tables linked by primary/foreign keys). RelGNN leverages  “atomic routes,” which reflect short tripartite or star-shaped connectivity among tables that have multiple foreign keys. These are sequences (or hyperedges) of node-types that facilitate more direct single-hop message passing between relational tables that are semantically connected.\n\n## update after rebuttal\nMy concerns are addressed. Considering that I gave a relatively high score in the review, I will just maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments. We appreciate the recognition of our method’s novelty, strong results, and the clarity of our experimental setup. We address each point below:\n\n> **Regarding Handling Self-Loop Tables (W1, C2, Q1)**\n\nThe reviewer suggests discussing solutions for self-loop tables, which we previously identified as a potential limitation. Although self-loop tables are rare in relational databases—only 1 out of 7 datasets in Relbench—we agree that discussing potential solutions is important. We experimented with adding positional encoding to help the model distinguish messages from different types of tables, which resulted in a 2% improvement on both entity classification tasks in the rel‑stack dataset. We will include a discussion in the revised version.\n\n> **Regarding Discussion of Integrating Other Components (W2)**\n\nThe reviewer suggests discussing advanced GNN aggregators and time encodings. We find this an interesting point and will include a discussion on how our framework can be flexibly integrated with these components. We note that incorporating such elements is complementary and orthogonal to our primary focus on enhancing the message passing design for RDL. To ensure a fair comparison, we kept other components the same as prior work.\n\n> **Regarding Ablation Study (C1)**\n\nWe appreciate the suggestion and incorporate an ablation study to further examine the impact of atomic routes. We instantiated Eq5 of RelGNN with GraphSAGE, which is equivalent to GraphSAGE + atomic routes. Additionally, we removed atomic routes from RelGNN, reducing it to a heterogeneous GAT. As shown in Table 1-3, the performance gap in both cases (GraphSAGE vs RelGNN w/ GraphSAGE; GAT vs RelGNN) highlights the effectiveness of atomic routes. We will include this ablation study in the revised version.\n\n**Table 1. Classification (ROC-AUC, ↑)**\n|Task|GraphSAGE|RelGNN w/ GraphSAGE|GAT|RelGNN|\n|-|-|-|-|-|\n|user-churn|70.42|70.90|63.21|70.99|\n|item-churn|82.81|82.94|69.99|82.64|\n|user-visits|66.20|66.80|64.82|66.18|\n|user-clicks|65.90|66.72|65.85|68.23|\n|user-repeat|76.89|78.82|68.24|79.61|\n|user-ignore|81.62|85.58|82.04|86.18|\n|driver-dnf|72.62|74.77|70.26|75.29|\n|driver-top3|75.54|84.86|60.03|85.69|\n|user-churn|69.88|70.29|64.72|70.93|\n|user-engagement|90.59|90.70|89.59|90.75|\n|user-badge|88.86|88.99|84.51|88.98|\n|study-outcome|68.60|69.34|66.19|71.24|\n\n**Table 2. Regression (MAE, ↓)**\n|Task|GraphSAGE|RelGNN w/ GraphSAGE|GAT|RelGNN|\n|-|-|-|-|-|\n|User-ltv|14.313|14.240|16.626|14.230|\n|Item-ltv|50.053|48.282|58.902|48.767|\n|Ad-ctr|0.041|0.037|0.043|0.037|\n|User-attendance|0.258|0.238|0.263|0.238|\n|Driver-position|4.022|3.792|4.268|3.798|\n|Item-sales|0.056|0.053|0.079|0.054|\n|Post-votes|0.065|0.065|0.068|0.065|\n|Study-adverse|44.473|45.531|46.026|44.461|\n|Site-success|0.400|0.354|0.393|0.301|\n\n**Table 3. Recommendation (MAP, ↑)**\n|Task|GraphSAGE|RelGNN w/ GraphSAGE|GAT|RelGNN|\n|-|-|-|-|-|\n|user-item-purchase|0.74|0.79|0.44|0.77|\n|user-item-rate|0.87|0.91|0.78|0.92|\n|user-item-review|0.47|0.57|0.29|0.52|\n|user-ad-visit|3.66|3.95|1.99|3.94|\n|user-item-purchase|2.81|2.82|1.88|2.81|\n|user-post-comment|12.72|13.9|11.97|14|\n|post-post-related|10.83|11.79|10.71|11.66|\n|condition-sponsor-run|11.36|11.62|10.43|11.55|\n|site-sponsor-run|19.00|19.17|17.90|19.14|\n\n> **Regarding Format (C3)**\n\nWe thank the reviewer for pointing this out and will revise the paper.\n\n> **Regarding Complexity in Large DBs (Q2)**\n\nThe reviewer asks if the complexity of computing atomic routes increases with larger DBs. The answer is no. Atomic routes are computed at the schema graph level—where nodes represent table types, which typically number in the tens—even for very large databases. This design choice makes our method agnostic to the number of individual entities (which can be in the millions), allowing RelGNN to scale efficiently as databases grow while the number of table types remains relatively stable. We will clarify this in the revised version.\n\n> **Regarding Handling Tables with Many Foreign Keys (Q3)**\n\nThe reviewer is concerned about complexity when handling tables with many foreign keys. We employ a sampling method (following the standard RDL implementation), so only a subset of nodes around the seed node is sampled. Consequently, we only process foreign keys within the sampled subset. The sample size can be controlled to ensure that the number of connections remains manageable. We will explain this in the revised version.\n\nIn summary, we provide potential solution for self-loop tables, discuss integration with advanced techniques, provide the ablation study that confirms the effectiveness of atomic routes and clarify how RelGNN is capable of handling large and complex DBs efficiently. We hope these clarifications address the reviewer’s concerns and will update the manuscript when permitted.", "claims_and_evidence": "Claim 1: RelGNN better models relational DB structure through “atomic routes” than standard heterogeneous GNNs.\n\nEvidence of Claim 1: The authors highlight the difference between typical “meta-path” approaches in heterogeneous graphs and the new approach of extracting routes directly from primary–foreign key constraints. The authors then show strong empirical improvements (≥15/30 tasks with >4% relative gain) on the RELBENCH benchmark.\n\nClaim 2: Gains are larger on DBs with more complicated foreign-key structures (“bridge” or “hub” shapes).\n\nEvidence of Claim 2: They measure the improvements by listing results across all tasks and highlight bigger improvements in “complex” schemas (e.g. rel-f1).", "methods_and_evaluation_criteria": "Overall, the proposed methods and metrics make sense for the targeted RDL tasks.", "theoretical_claims": "The paper does not heavily focus on new theoretical proofs. The main conceptual claim is that “atomic routes” in relational data can be grouped for single-step message passing. The authors do not provide formal theorems, but they do discuss the correctness of capturing needed information in one pass.", "experimental_designs_or_analyses": "They follow the standard approach from RELBENCH. Each of the 30 tasks is tested with a consistent data split (temporal). Baselines are run with the same node embedding initialization and the same sampling method. Besides, the authors highlight that improvements are especially large when the relational schema is complicated. That matches the paper’s central premise. The experiments appear valid for the stated goal. There do not appear to be unusual or confounding design choices in their methodology.", "relation_to_broader_scientific_literature": "The authors situate their approach relative to Relational Deep Learning (Fey et al., 2024) and the concept of knowledge graphs in heterogeneous GNNs. The difference is that knowledge graphs revolve around semantic relation types (like “author-of,” “works-in,” etc.), whereas relational DB edges come strictly from primary–foreign key constraints.\nThey also place it in context with meta-path approaches for heterogeneous GNNs (like HAN, R-GCN). However, they argue that meta-paths require domain knowledge, whereas they systematically build “atomic routes” from DB schema keys.\nTo conclude, they do address the main relevant lines of prior work on heterogeneous graph modeling and knowledge graph completions.", "essential_references_not_discussed": "Given the scope, they mostly reference the standard GNN and relational DB learning papers. Possibly referencing more about “multi-hop GNN minimization / skipping aggregator nodes” from other design patterns might help, but not necessarily “essential.” No glaring missing references stand out.", "other_strengths_and_weaknesses": "Stengths:\n- Novel approach to dealing with multi-foreign-key bridging nodes, which is common in real relational DBs.\n- Relatively strong results on a large set of real tasks from RELBENCH.\n- Minimal overhead or domain knowledge needed: the “atomic route” concept is systematically derived from foreign key constraints.\n\nWeaknesses:\n- May not handle self-joins or self-loop tables elegantly (they mention rel-stack’s performance is not improved as much).\n- The proposed method focuses on composite message passing but does not discuss integration with more advanced GNN aggregator designs or advanced time encodings.", "other_comments_or_suggestions": "1. A small ablation might be helpful: e.g. how does the removal of the composite step or the removal of atomic routes degrade performance?\n2. The authors could incorporate or discuss how “atomic routes” would handle self-referencing foreign keys or cyclical references.\n3. Please check the formating of the tables and the margins on the last page of the paper, as they are poorly presented.", "questions_for_authors": "1. For tasks like rel-stack with self-joins (post to post), do you see a better representation approach than treating them like normal foreign-key edges?\n2. For extremely large DBs, do atomic routes lead to any complexities in memory usage or graph construction time?\n3. For tables with many foreign keys, do you risk a large blow-up in “composite messages” to handle all pairwise or triple connections?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N.A."}}, {"review_id": "2yQk8yKFvg", "reviewer": "Reviewer_xbNa", "summary": "The paper proposes a graph neural network with attention mechanism, called RelGNN, for predictive tasks on relational tables. The paper introduces atomic routes based on primary-foreign key connections and design a composite message passing using atomic Routes. RelGNN achieves good results on RELBENCH that is a widely accepted benchmark for deep learning on relational data.\n\n## update after rebuttal\nMy questions are answered. I maintain my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging RelGNN’s efficiency, strong performance, and the clarity of our writing. We also appreciate the constructive feedback and address each point below:\n\n> **Regarding Discussion on the Limitations (W1)**\n\nThe reviewer mentions that the limitations of RelGNN are not discussed. In fact, we did discuss specific limitations within the experiment sections (e.g., discussing limitations on recommendation tasks due to the constraints of the inherited framework and prediction head from RDL; analyzing potential reasons for performance variations across tasks). We recognize these discussions and insights could be more accessible. In the revised version, we will add a consolidated limitations section. This reorganization will improve clarity without requiring substantial new content, as the critical analysis is already present in our original manuscript.\n\n> **Regarding Open-Sourcing Implementations (W2)**\n\nThis is a good point and we acknowledge the importance of reproducibility and transparency. We've now made our source code available at  https://anonymous.4open.science/r/RelGNN.\n\n> **Regarding Handling Many-to-Many Relationships (Q1)**\n\nThe reviewer inquires about RelGNN’s ability to handle many-to-many relationships. The answer is an unambiguous yes. Many-to-many relationships are common in relational databases and are routinely modeled using bridge tables. For instance, in the rel-hm dataset, a customer may purchase multiple articles, and an article may be purchased by many customers; similarly, in the rel-f1 dataset, a driver participates in multiple races while each race includes multiple drivers. Such relationships are handled through bridge tables (e.g., transaction tables in rel-hm dataset) which is standard practice in relational databases. Incorporating these bridge tables are necessary by definition of database - as primary keys must uniquely identify rows, many-to-many relationships require intermediate tables with foreign keys pointing to both related entities. In the reviewer's movie-actor example, a valid relational database design requires more than just \"actors\" and \"movies\" tables. To represent this many-to-many relationship correctly, a bridge table (commonly called \"appearances\" or \"cast\") must be introduced. This bridge table would contain foreign keys referencing the primary keys of both the \"actors\" and \"movies\" tables, thereby preserving referential integrity while enabling the many-to-many relationship.\n\nIn fact, this prevalence of bridge-node-modeled many-to-many relationships distinguishes relational data graphs from general heterogeneous graphs, which motivated RelGNN's design to specifically leverage this unique structure, leading to improved performance compared to general heterogeneous GNNs. We thank the reviewer for this great question and will clarify this point in the revised manuscript.\n\n> **Regarding Clarification on “Broad Applicability and Scalability”**\n\n\"Broad applicability and scalability\" refers to two key advantages:\n\n- Broad Applicability: RelGNN's atomic routes can be automatically extracted without domain-specific knowledge (unlike traditional meta-path approaches), making it applicable to diverse relational datasets beyond Relbench.\n- Scalability: Atomic routes are computed at the schema graph level—a graph where nodes represent table types (which typically number in the tens even for large databases) rather than the data graph level, where nodes represent individual entities (which can number in the millions). This design makes our method agnostic to the number of entities, allowing RelGNN to scale efficiently to very large databases where the number of entities grow rapidly while table types remain relatively stable.\n\nWe thank the reviewer for bringing this up and will clarify this explanation in the revised manuscript.\n\nIn summary, we\n\n- Note that limitations were discussed in our experiment section and commit to a more explicit discussion in the revised version.\n- Make our source code available.\n- Clarify that many-to-many relationships are handled via bridge nodes, a necessity in relational database design.\n- Explain \"broad applicability and scalability\" by highlighting RelGNN’s independence from human knowledge and its efficiency as the database scales.\n\nWe hope these clarifications address the reviewer’s concerns and will update the manuscript when permitted.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes, the proposed methods is evaluated on RELBENCH that is a widely accepted benchmark for deep learning on relational data.", "theoretical_claims": "Yes. I did read and understand the equations in the paper.", "experimental_designs_or_analyses": "Yes, I did. Experimental evaluations in the paper are conducted on a state-of-the-art benchmark.", "relation_to_broader_scientific_literature": "The key contributions of the paper are atomic routes and a composite message passing with atomic routes, which are simple but efficient. In general, simple but efficient approaches are easier to be deployed into systems.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths \nS1: Authors propose a simple but efficient solution for learning over relational tables.\nS2: RelGNN have good performances on all tasks.\nS3: The paper reads well.\n\nWeakness\nW1: Limitations of RelGNN are not discussed \nW2: Implementations are not open-sourced.", "other_comments_or_suggestions": "Personal comment: I can not learn some implementation details as I did not find the source codes.", "questions_for_authors": "Q1: Will RelGNN degenerate on relational tables with many-to-many relationships? For example,  for movie and actor tables, one actors can appear in multiple movies and one movie can feature many actors. \n\nQ2: The claim made in line 233 - 234 \"This ensures both broad applicability and scalability across diverse datasets\". Can authors explain what \"broad applicability and scalability\" means?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The papers presents RELGNN, a novel graph neural network framework that improves predictive modeling of relational databases by utilizing atomic routes and composite message passing to capture relational structures effectively. Doing so achieves up to 25% improvement in accuracy over existing models across various real-world tasks. One reviewer points out some downsides such as a potentially unproven claim that standard heterogeneous GNNs entangle irrelevant information,  weak selection of baselines, as the paper mainly uses heterogeneous GraphSAGE as a comparison and a missing ablation study. These downsides have been largely addressed in the rebuttal. While indeed more existing heterogenuous GNNs could be included, the updated results (including ablation studies) as well as the overall idea underlying RELGNN, seem to be interesting, as pointed out by the other reviewers. The other reviewers also stress the novelty of the approach as well as relatively strong results on a large set of real tasks from RELBENCH. Therefore, I overall recommend to accept the paper, overruling one of the reviewers. I agree with them.
Decision: Accept (poster)