mlsanityData to 14 Oct 2026

AutoGrable: What Is a Good Graph for a Table?

arXiv 2608.11431 ↗First posted 11 Aug 2026cs.LGcited by 0

Not on the map. Why?

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.

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

32 of 38 references.

References · 32

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  3. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  4. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  5. 2025TabICL: A Tabular Foundation Model for In-Context Learning on Large Datacited by 289
  6. 2019Learning Discrete Structures for Graph Neural Networkscited by 231
  7. 2020Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddingscited by 214
  8. 2025TabArena: A Living Benchmark for Machine Learning on Tabular Datacited by 176
  9. 2021SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networkscited by 110
  10. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  11. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 97
  12. 2024RelBench: A Benchmark for Deep Learning on Relational Databasescited by 96
20 more
  1. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  2. 2021A Survey on Graph Structure Learning: Progress and Opportunitiescited by 71
  3. 2025RelGNN: Composite Message Passing for Relational Deep Learningcited by 48
  4. 2020word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Datacited by 38
  5. 2025Relational Graph Transformercited by 34
  6. 2023WL meet VCcited by 31
  7. 2023OpenGSL: A Comprehensive Benchmark for Graph Structure Learningcited by 30
  8. 2024GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Datacited by 20
  9. 2026RelBench v2: A Large-Scale Benchmark and Repository for Relational Datacited by 20
  10. 2024Graph Neural Networks for Tabular Data Learning: A Survey with Taxonomy and Directionscited by 13
  11. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  12. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  13. 2025RDB2G-Bench: A Comprehensive Benchmark for Automatic Graph Modeling of Relational Databasescited by 8
  14. 2025AutoG: Towards automatic graph construction from tabular datacited by 7
  15. 2025From Features to Structure: Task-Aware Graph Construction for Relational and Tabular Learning with GNNscited by 6
  16. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  17. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 2
  18. 2026Grables: When Graph Structure Helps Tabular Predictioncited by 2
  19. 2026Relatron: Automating Relational Machine Learning over Relational Databasescited by 2
  20. 2025Database Views as Explanations for Relational Deep Learningcited by 1

Built on by

Not cited yet.