# What Makes a Desired Graph for Relational Deep Learning?

arXiv: https://arxiv.org/abs/2606.08491 · HTML: https://mlsanity.com/paper/2606.08491/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 7 Jun 2026.

## Builds on (most cited first, 16 of 16)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [RelBench: A Benchmark for Deep Learning on Relational Databases](https://mlsanity.com/paper/2407.20060/) (2024)
- [Supervised Learning on Relational Databases with Graph Neural Networks](https://mlsanity.com/paper/2002.02046/) (2020)
- [RelGNN: Composite Message Passing for Relational Deep Learning](https://mlsanity.com/paper/2502.06784/) (2025)
- [Relational Graph Transformer](https://mlsanity.com/paper/2505.10960/) (2025)
- [PyTorch Frame: A Modular Framework for Multi-Modal Tabular Learning](https://mlsanity.com/paper/2404.00776/) (2024)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Efficient Algorithms for Computing Random Walk Centrality](https://mlsanity.com/paper/2510.20604/) (2025)
- [Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness](https://mlsanity.com/paper/2602.02512/) (2026)

## Abstract (arXiv)

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. Our empirical analysis reveals that the desired graph is not the raw schema, but a result of controlled structural adaptation. Performance depends on balancing two operations: mitigating information overload via filtering, and repairing semantic fragmentation via injection. Specifically, filtering serves as a bias-variance knob with non-monotonic effects, while injection improves performance only when it explicitly restores the relational dependencies missing from the original schema. Based on these findings, we develop an end-to-end structural optimizer that applies both operations to adapt relational graphs automatically. Across 26 tasks spanning classification, regression, and recommendation, the optimized graphs consistently improve accuracy while often reducing inference cost.