AutoGrable: What Is a Good Graph for a Table?

The paper addresses the fundamental question of graph construction for tabular and relational data: when the graph is not given, what is a good graph to learn on, and how do we build it? The authors note that Graph learning presupposes the existence of a single or multiple graphs but tables and relational databases do not come with one. Applying a GNN to such data 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.

The paper critiques existing approaches: "One learns a graph: taking the data points as nodes, it infers a soft adjacency from their features jointly with the model. The other constructs one from a table or schema, fixing the foreign-key skeleton, searching schema edits, or scoring attributes, and judges it by the accuracy of a model trained on it. The first assumes structure means geometric proximity over given nodes, which a table does not provide, while the second defines a good graph only operationally, good if a trained model likes it, which is circular, costs a training run per candidate, and says nothing about which distinctions a graph exposes to the learner."

The central observation is that Message-passing GNNs are bounded by the one-dimensional Weisfeiler–Leman (1-WL) test, or colour refinement: a GNN cannot tell two nodes apart when 1-WL assigns them the same colour. Therefore, a graph constructed from a table does just one thing: it sorts the table rows (row nodes in the graph) into 1-WL colour classes, and only distinctions between colour classes are visible to the learner.

This leads to the criterion: "A graph is good for a task when this sorting lines up with the labels, rows of different labels fall in different classes, and rows of the same label are not split further than necessary. Too coarse a sorting hides the labels; too fine a one lets the model memorize individual rows instead of generalizing."

The paper formalizes this through an alignment score. For a candidate attribute set S, rows are partitioned by projection: r ∼S r′ ⇐⇒ rS = r′S. Each cell gets a training-free block predictor: the empirical label distribution on occupied cells, the training marginal on unseen projections.

The score combines two terms:

• Validation risk of the block predictor: The first term rewards distinctions that track the labels on held-out rows

• Occupancy penalty: the second charges for distinctions supported by too few training rows

The fragmentation measure is defined as:

(T tr, pi S):= 1 over n tr sum u: N S,u > 0 sqrt N S,u

The score is:

J(pi S):= val(S) + lambda (T tr, pi S), lambda at least 0

The paper proves a generalization bound showing Ω bounds the estimation term in a generalisation bound: refinement can lower approximation error, but raises the observable quantity controlling estimation. Specifically, for binary classification, with probability at least 1−δ:

Risk(S) - Risk* at most Risk* S - Risk* + (T tr, pi S) + 4 sqrt(4/delta) over 2n tr

A uniform validation guarantee is also provided: an exact minimiser S⋆ of (1) satisfies, with probability at least 1 − δ, Risk(ĥS⋆) + λΩ(Ttr, πS⋆) ≤ min S⊆F Risk(ĥS) + λΩ(Ttr, πS) + 2εL.

Exact minimization is infeasible: even a requirement much weaker than alignment is already NP-complete. The paper proves:

Theorem 1 (Separation is NP-complete): Given Ttr, F, and k, deciding whether some S ⊆ F with S ≤ k separates the labels is NP-complete.

The paper also notes that "Separation is necessary for a cell-constant predictor to fit the training labels, but it is not the objective, and it is attained by two degenerate choices: taking all attributes separates whenever any subset does, at the price of the finest and least supported partition, while a key-like attribute separates all rows, permitting memorisation while exposing no repeated structure to generalise from."

Algorithm 1 (SCS) performs greedy local search with:

• Direction: forward (from S=∅, adding columns) or backward (from S=F, removing columns)

• Signature: value encoding (σ=val) or frequency encoding (σ=freq), where frequency encoding replaces each value with the number of times its value occurs in that column

• Tolerance τ: sets the minimum improvement in J the search will act on, so it does not chase differences attributable to validation noise

The cost is O(F2(ntr + nval)) in the worst case since each evaluation is one group-by over Ttr and one pass over Tval.

The paper defines the incidence grable GS(T) with:

1. one row node vr per r ∈ T, carrying the unexpanded attributes rA

2. one value node uc,a per occurring typed value (c, a) with c ∈ S

3. An edge of type c joins vr and uc,a exactly when r[c] = a

Lemma 1: For all r, r′ ∈ Ttr, πCR(G◦S(Ttr)) = πS. This shows SCS computes πS by a group-by, yet πS is precisely the stable row partition that the selected incidence structure induces once row features are suppressed.

The paper emphasizes: "Selecting S is a table-space operation, but the object it selects is not. By Lemma 1 the graph adds no distinguishing power over πS; what it adds is access, within a cell, to evidence held by other rows—how many share a value, and what those rows carry."

For relational databases: "We materialise Te:= T ⋈d D by left joins along all foreign-key paths of length < d and evaluate candidates on Te. The paper handles join multiplicity: duplicate appearances of a primary row are collapsed within each cell, and if row i then occurs in ki(S) distinct cells, each appearance receives weight 1/ki(S), so every primary row contributes one total unit."

Using Census/Adult data with planted tasks (Single-value, Conjunction, XOR, Count, Duplicate), the paper finds:

• Recovery is decided by the signature, rejection by λ and the search direction

• With value encoding, AUTO G RABLE recovers all tasks for row-local tasks

• Frequency encoding recovers extension-sensitive tasks (Count, Duplicate)

• λ closes the Rec–Exact gap where the search starts too large, and costs Rec where it does not

Using RDB2G-Bench candidate graphs: J acts as a one-sided screen rather than a ranking: low J is necessary for strong downstream AUC on these candidates, not sufficient. On driver-top3, retaining the two lowest J levels discards 80% of the candidate graphs and all ten of the best-performing graphs survive. Correlations are negative throughout, but attenuated by ties.

Under a fixed GraphSAGE predictor, AUTO G RABLE outperforms baselines:

• On transactional tasks (FDB): vehicleloan 0.662 vs. trivial 0.647, twitterbot 0.908 vs. auGraph 0.887

• On relational tasks (RelBench): driver-top3 0.803 vs. auGraph 0.791, driver-dnf 0.761 vs. auGraph 0.742

• On study-outcome: AUTO G RABLE returns ∅ and matches trivial (0.677), being the only method compared that can decline to build a graph when none helps

The paper notes: "Fixed constructions do not select: exposing every eligible column (γinc) loses to building no graph on three of five tasks, and the schema skeleton (REG) loses to γtriv on study-outcome. Structure is not free, and a column that fragments the rows costs more than the signal it carries."

The paper's contributions are: "(1) alignment as a criterion of graph goodness: a construction reaches a 1-WL-bounded learner only as a grouping of the rows, and is good for a task when that grouping matches the labels; (2) a score for this criterion, computed from the grouping alone with no model trained, weighing the error of the best predictor the grouping admits against how thinly it spreads the rows; and (3) AUTO G RABLE, a table-to-graph constructor that builds the graph the score selects, applies to single- and multi-table datasets, and outperforms alternative constructions on transactional and relational benchmarks."

The paper concludes: "For a learner bounded by 1-WL, a construction is visible only as a partition of the rows, so the design question is not how much a construction distinguishes but how it groups. On a fixed table the maximum distinguishing power is already available without any construction, and under the incidence construction the induced partition is the projection onto the selected columns (Lemma 1). Construction therefore reduces to column selection, and the criterion that matters is alignment with the label rather than refinement."

Based on the paper, here are specific improvements for AI systems:

1. Training-free graph construction evaluator

• Improvement: Replace model-training-based graph selection with the alignment score J, computed directly from row partitions and label distributions.

• What the improved system can do: Evaluate candidate graph constructions in O(F2(n tr + n val)) without training a model per candidate, enabling rapid graph search across large relational schemas where training runs were previously the bottleneck.

2. Label-aligned feature grouping for tabular GNNs

• Improvement: Use the 1-WL partition criterion to select column subsets that group rows by label alignment, rather than relying on geometric proximity or schema heuristics.

• What the improved system can do: Build graphs where message passing exposes label-relevant distinctions while suppressing over-fragmentation, reducing memorization and improving generalization on tabular tasks with sparse labels.

3. Automatic graph abstention

• Improvement: Incorporate the occupancy penalty Ω to detect when no column subset improves over a trivial (no-graph) baseline.

• What the improved system can do: Decline to build a graph when structure doesn't help (e.g., returning ∅ on study-outcome tasks), avoiding performance degradation from unnecessary fragmentation—a capability no fixed constructor currently has.

4. Frequency-encoding for extension-sensitive tasks

• Improvement: Use frequency encoding (σ=freq) in the SCS search to capture count-based and duplicate-detection patterns that value encoding misses.

• What the improved system can do: Recover tasks like Count and Duplicate where the label depends on how many rows share a value, not just which values exist—enabling GNNs to learn aggregation-dependent relations.

5. Multi-table join-aware graph construction

• Improvement: Materialize joined tables via left joins along foreign-key paths, with duplicate-row collapse and inverse-frequency weighting per cell.

• What the improved system can do: Handle relational databases with multiple tables, ensuring each primary row contributes equal weight even when joins create multiplicities, enabling consistent graph learning across heterogeneous schemas.

6. One-sided screening for graph candidates

• Improvement: Use J as a necessary-condition filter before expensive downstream training, retaining only low-J candidates.

• What the improved system can do: Discard 80% of candidate graphs while preserving all top-performing ones (as shown on driver-top3), reducing downstream evaluation cost by an order of magnitude in graph search pipelines.

7. NP-completeness-aware search with bounded cost

• Improvement: Apply greedy local search (SCS) with direction, signature, and tolerance parameters, given that exact separation is NP-complete.

• What the improved system can do: Find near-optimal column subsets in polynomial time with worst-case O(F2(n tr + n val)) cost, with tolerance τ preventing overfitting to validation noise during search.

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.