# AutoGrable: What Is a Good Graph for a Table?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 38 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 30 of 32)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [TabICL: A Tabular Foundation Model for In-Context Learning on Large Data](https://mlsanity.com/paper/2502.05564/) (2025)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [TabArena: A Living Benchmark for Machine Learning on Tabular Data](https://mlsanity.com/paper/2506.16791/) (2025)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [RelBench: A Benchmark for Deep Learning on Relational Databases](https://mlsanity.com/paper/2407.20060/) (2024)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [A Survey on Graph Structure Learning: Progress and Opportunities](https://mlsanity.com/paper/2103.03036/) (2021)
- [RelGNN: Composite Message Passing for Relational Deep Learning](https://mlsanity.com/paper/2502.06784/) (2025)
- [word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data](https://mlsanity.com/paper/2003.12590/) (2020)
- [Relational Graph Transformer](https://mlsanity.com/paper/2505.10960/) (2025)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [OpenGSL: A Comprehensive Benchmark for Graph Structure Learning](https://mlsanity.com/paper/2306.10280/) (2023)
- [GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data](https://mlsanity.com/paper/2409.14500/) (2024)
- [RelBench v2: A Large-Scale Benchmark and Repository for Relational Data](https://mlsanity.com/paper/2602.12606/) (2026)
- [Graph Neural Networks for Tabular Data Learning: A Survey with Taxonomy and Directions](https://mlsanity.com/paper/2401.02143/) (2024)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [RDB2G-Bench: A Comprehensive Benchmark for Automatic Graph Modeling of Relational Databases](https://mlsanity.com/paper/2506.01360/) (2025)
- [AutoG: Towards automatic graph construction from tabular data](https://mlsanity.com/paper/2501.15282/) (2025)
- [From Features to Structure: Task-Aware Graph Construction for Relational and Tabular Learning with GNNs](https://mlsanity.com/paper/2506.02243/) (2025)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Grables: When Graph Structure Helps Tabular Prediction](https://mlsanity.com/paper/2602.03945/) (2026)

## Abstract (arXiv)

Graph learning presupposes a graph, and tables and relational databases do not come with one. Applying a GNN to them requires deciding which entities become nodes, which of them to connect, and through which relations---a decision made by hand, by schema heuristics, or by training a model on every candidate graph and keeping the best. We give a criterion that requires no trained graph model. In the minimal table-to-graph abstraction each row is a node, so a message-passing GNN, bounded by 1-WL, sees a construction only as a partition of the rows into colour-refinement classes: a construction is good for a task when that partition separates rows with different labels and does not split rows that share one. AutoGrable turns this criterion into a construction procedure. For incidence constructions the partition is fixed by the selected columns, so building a graph reduces to choosing them, and we score a candidate subset by a label-alignment risk: the held-out risk of the best predictor constant on its blocks, penalised by an occupancy term measuring how thinly the blocks are populated. The score materialises no graph and trains no GNN, so AutoGrable can search the space of subsets greedily and cheaply, and returns the resulting grable for single tables and for foreign-key schemas alike. Our experiments show that over a space of candidate graphs the score discards a large fraction while retaining the best; that AutoGrable recovers the columns that generate the label on controlled tasks and outperforms fixed, random, and task-aware constructors on real tasks under a fixed predictor; and that it is the only method compared that can decline to build a graph when none helps.