What Makes a Desired Graph for Relational Deep Learning?

Yao Cheng, Siqiang Luo

Introduction

Relational deep learning (RDL) promises to unlock the predictive power of relational databases (RDBs) by applying Graph Neural Networks (GNNs) directly to tabular data. However, the standard practice of mechanically converting tables to node types and foreign keys to edges often yields suboptimal results. This paper investigates why schema-derived graphs fail and introduces an end-to-end structural optimizer to construct "desired graphs" tailored specifically for relational reasoning.

The Core Challenges: Overload and Fragmentation

The fundamental issue in applying GNNs to databases stems from a mismatch in design objectives. RDB schemas are normalized for storage integrity and query efficiency, not for message passing in neural networks. This normalization introduces two systematic failures:

  1. Information Overload: Databases are filled with attributes (e.g., logging fields, internal IDs) that are statistically active but causally irrelevant to specific prediction tasks. This creates "semantic noise" that distracts the learning model.
  2. Semantic Fragmentation: Normalization fractures single, meaningful interactions into long, convoluted chains of tables (e.g., User $\rightarrow$ Order $\rightarrow$ OrderItem $\rightarrow$ Item). GNNs notoriously struggle to propagate signals across these extended paths without suffering from oversmoothing or vanishing gradients.

Methodology: The Structural Optimizer

To address these failures, the authors propose a unified Structural Optimizer that treats graph construction as a task-dependent, learnable transformation rather than a fixed mapping. The optimizer employs two primary operations:

1. Information Filtering

To combat overload, the model utilizes a hierarchical gating mechanism at both the column and table levels. By applying a Hard-Concrete relaxation, the model learns to differentiably "drop" or "keep" features during training. A Variational Information Bottleneck (VIB) is also used to further compress representations and eliminate noise.

2. Structural Injection

To resolve fragmentation, the model "repairs" the graph by injecting new edges based on four interpretable semantic templates:

  • Homophily Repair (KNN): Connects similar entities within the same table.
  • Topological Repair (Two-hop Shortcuts): Creates direct links across long relational chains, bypassing intermediate tables.
  • Collaboration Repair (Behavioral Similarity): Connects entities interacting with similar sets of neighbors.
  • Causal Repair (Temporal Continuity): Links records of the same entity across time to capture state transitions.

The entire pipeline is end-to-end trainable, allowing the model to learn the optimal graph structure and the GNN parameters simultaneously.

Key Insights and Empirical Findings

The framework was evaluated on RELBench, a comprehensive benchmark comprising 26 diverse tasks across seven real-world domains (including e-commerce, sports, and clinical trials). The empirical analysis revealed several critical insights into graph design:

  • The Inverted-U of Filtering: Graph performance follows a non-monotonic trend regarding compression. Too little filtering leaves noise that degrades learning, while excessive filtering destroys vital evidence. The optimal "desired graph" exists at a task-specific sweet spot.
  • Injection is Not a "Free Lunch": Indiscriminately adding edges can actually harm performance. Effective structural injection is highly task-dependent. For instance, KNN injection excels in classification by reinforcing clusters, whereas Temporal Continuity is the "killer app" for time-series regression tasks.
  • Semantic vs. Statistical Pruning: Standard feature selection methods (like retaining high-variance features) fail in RDBs because operational artifacts often exhibit high variance. The model’s learned semantic gates consistently outperform naive statistical filtering.

Results and Impact

The structural optimizer consistently outperformed raw schema-derived graphs and strong baselines, including LightGBM, HAN, and Relational Graph Transformers, across almost all 26 tasks.

Furthermore, by aggressively pruning irrelevant tables and columns, the optimized graphs frequently reduced inference latency. In some cases, "FullFilter" variants achieved the lowest latency while maintaining high accuracy. Crucially, these gains are backbone-agnostic, improving performance across various GNN architectures (GraphSAGE, REL-GNN, HGT) and proving that the bottleneck lies in the graph topology itself, not just the model layers.

Limitations and Future Directions

The optimizer is deliberately constrained to interpretable templates (like KNN or two-hop shortcuts) to maintain scientific readability. While effective, an unconstrained structure learner might discover more complex, higher-performing topologies at the cost of becoming a "black box."

Future work will focus on scaling these structural optimizations to multi-billion-node graphs and developing automated methods to discover novel injection templates beyond the four proposed in this study.

Summary updated

Abstract

Relational deep learning (RDL) converts relational databases (RDBs) into heterogeneous graphs, but graphs derived directly from database schemas are often not well suited for how graph neural networks (GNNs) perform relational reasoning. We study what makes a relational graph suitable for deep learning and show that schema-derived graphs suffer from two systematic failures: information overload and semantic fragmentation. Through an empirical analysis on real-world databases, we find that effective graphs arise from a task-dependent balance between removing task-irrelevant structure and injecting task-aligned relational connectivity. Filtering exhibits a non-monotonic effect on performance, while structural injection is beneficial only when it reflects the logic of the downstream task. Based on these findings, we develop an end-to-end structural optimizer that applies both operations to adapt relational graphs automatically. Across 23 tasks spanning classification, regression, and recommendation, the optimized graphs consistently improve accuracy while often reducing inference cost.
BibTeX
@inproceedings{cheng2026what,
  author = {Yao Cheng and Siqiang Luo},
  title = {{What Makes a Desired Graph for Relational Deep Learning?}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=GDHVAs2XDQ},
}
Figure