RelGNN: Composite Message Passing for Relational Deep Learning

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:

Regarding Discussion on the Limitations (W1)

The 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.

Regarding Open-Sourcing Implementations (W2)

This 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.

Regarding Handling Many-to-Many Relationships (Q1)

The 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.

In 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.

Regarding Clarification on “Broad Applicability and Scalability”

"Broad applicability and scalability" refers to two key advantages:

• 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.
• 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.

We thank the reviewer for bringing this up and will clarify this explanation in the revised manuscript.

In summary, we

• Note that limitations were discussed in our experiment section and commit to a more explicit discussion in the revised version.
• Make our source code available.
• Clarify that many-to-many relationships are handled via bridge nodes, a necessity in relational database design.
• Explain "broad applicability and scalability" by highlighting RelGNN’s independence from human knowledge and its efficiency as the database scales.

We hope these clarifications address the reviewer’s concerns and will update the manuscript when permitted.

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:

Regarding Handling Self-Loop Tables (W1, C2, Q1)

The 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.

Regarding Discussion of Integrating Other Components (W2)

The 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.

Regarding Ablation Study (C1)

We 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.

Table 1. Classification (ROC-AUC, ↑)

Table 2. Regression (MAE, ↓)

Table 3. Recommendation (MAP, ↑)

Regarding Format (C3)

We thank the reviewer for pointing this out and will revise the paper.

Regarding Complexity in Large DBs (Q2)

The 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.

Regarding Handling Tables with Many Foreign Keys (Q3)

The 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.

In 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.

We thank the reviewer for the feedback and address each concern as follows:

Regarding Justification of Claims

The 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.

Regarding Additional Baselines

The 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.

Regarding 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.

Regarding Limitations

The 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.

Regarding Ablation on Model Components

We 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.

Table 1. Classification (ROC-AUC, ↑)

Table 2. Regression (MAE, ↓)

Table 3. Recommendation (MAP, ↑)

Regarding Code and Other Details

We'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.

The 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.

We hope these clarifications address the reviewer’s concerns and will update the manuscript when permitted.