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