AutoGrable Automates Optimal Graph Construction from Tables

Applying Graph Neural Networks (GNNs) to tabular data or relational databases presents a significant challenge: these data sources do not inherently come with a predefined graph structure. Traditionally, the decision of which entities become nodes and how they connect has been made manually, through schema heuristics, or by exhaustively training models on various candidate graphs. This paper introduces AutoGrable, a new method that automates this graph construction process without requiring a trained GNN model. AutoGrable proposes a criterion based on how well a graph's structure, when viewed through the lens of a 1-Weisfeiler-Leman (1-WL) test, partitions rows into color-refinement classes. A "good" graph for a given task is one where this partition effectively separates rows with different labels while keeping rows with shared labels together. For incidence constructions, where the partition is determined by selected columns, AutoGrable scores candidate column subsets using a label-alignment risk, penalized by an occupancy term that measures block population density. Crucially, this scoring mechanism does not materialize a graph or train a GNN, allowing AutoGrable to greedily and efficiently search the space of subsets. Experiments demonstrate that AutoGrable effectively discards a large fraction of suboptimal candidate graphs while retaining the best ones. It successfully recovers label-generating columns in controlled tasks and outperforms fixed, random, and task-aware constructors on real-world tasks. Uniquely, AutoGrable can also determine when no graph construction would be beneficial, offering a robust and efficient solution for graph learning from tables.