AutoGrable: What Is a Good Graph for a Table?

# AutoGrable: What Is a Good Graph for a Table?
Source: [https://arxiv.org/html/2608.11431](https://arxiv.org/html/2608.11431)
###### Abstract

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\.AutoGrableturns 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, soAutoGrablecan 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; thatAutoGrablerecovers 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\.

## 1Introduction

Graph learning presupposes the existence of a single or multiple graphs\. The graph is where the inductive bias lives: Message\-passing can only relate two entities if an edge, or a path of edges, connects them\. Recent work has applied graph learning techniques to the data formats that dominate applied machine learning– single tables and relational databases linked by foreign keys– but these do not come with a graph representation\. In order to bring a graph model to such data we must first decide what the nodes are, which entities to connect, and through which relations\. This decision is usually made by hand, schema heuristics, or not at all, and it is made*before*any learning happens\.

The question this paper takes up is the one that precedes architecture and optimization entirely:when the graph is not given, what is a good graph to learn on, and how do we build it?

Two responses to this question exist, yet neither answers it fully\. One*learns*a graph: taking the data points as nodes, it infers a soft adjacency from their features jointly with the model\[franceschi,kazi2022dgm,zhou2023opengsl\]\. 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\[RDL\-fey,autog,augraph\]\. The first assumes structure means geometric proximity over given nodes, which a table does not provide: its relation is shared categorical values, and its node set is itself a construction choice\. 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*\. We seek a notion of a good graph that can be stated before training and that explains why a construction helps\.

In this work, we judge the quality of a graph representation by the distinctions the model running on it can make\. Message\-passing GNNs are bounded by the one\-dimensional Weisfeiler–Leman \(1\-WL\) test, or colour refinement\[xu2018how,morris\-WL\-go\-neural\]: a GNN cannot tell two nodes apart when 1\-WL assigns them the same colour, that is, when their neighborhoods are indistinguishable under iterated aggregation, however near or far apart the two nodes sit\. For such a model, then, 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\. 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\. This gives a criterion for constructing a graph that can be stated, and checked, before any model is trained\.

We turn this target into an algorithm\. Scoring a candidate graph is cheap: because the target only concerns which rows are grouped together, it can be measured directly from that grouping, with no model training\. Yet, searching for the best graph is not cheap, the closely related separation problem is NP\-hard, so we build the graph greedily rather than by enumeration\. The result isAutoGrable, which selects a construction by this training\-free target and then trains a graph model on it\. The algorithm naturally extends from a single table to several tables linked by foreign keys\.

Contributions\.We propose a criterion for what makes a graph good for a task, and apply it to tabular learning, where the graph is not given but has to be constructed\. Our 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\)AutoGrable, 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\.

## 2Attribute selection as label alignment

Our approach rests on one observation: selecting a subset of attributes and expanding its values into shared nodes of an incidence graph induces, on the rows of the table, exactly the colour\-refinement \(1\-WL\) partition of that graph – and colour refinement is precisely what limits the power of message\-passing GNNs \(Section[4](https://arxiv.org/html/2608.11431#S4)\)\. Choosing attributes therefore fixes the expressive ceiling of every GNN run on the constructed graph, and the choice can be made entirely in table space, even though what the choice produces, cross\-row communication, is not available in table space at all\.

We thus focus first on how to select the attribute subset\. The guiding notion is that its induced partition should be*aligned*with the labels: fine enough that cells are label\-homogeneous, yet coarse enough that each cell retains the support needed to estimate anything on it\. This section makes alignment precise\. We attach to every candidate attribute set a partition of the training rows and a training\-free predictor, and score the pair by an objective that trades held\-out predictive gain against fragmentation, with a generalisation bound as justification\.

Tables and candidate attributes\.Let𝒞\\mathcal\{C\}be a universe of attribute names andval\\mathrm\{val\}a value domain\. A*schema*is a finite setC⊆𝒞C\\subseteq\\mathcal\{C\}, a*CC\-row*is a mapr:C→valr\\colon C\\to\\mathrm\{val\}, and a*CC\-table*is a finite indexed collection of rows\. We writer⁡\[c\]r\[c\]for the value ofccinrr, andr\|Sr\|\_\{S\}for the restriction ofrrtoS⊆CS\\subseteq C\. One attributeY∈CY\\in Cis the label,A:=C∖\{Y\}A:=C\\setminus\\\{Y\\\}are the input attributes, andF⊆AF\\subseteq A, fixed before the validation sample is inspected, contains the attributes eligible for structural selection\. The labelled rows are split into disjoint training and validation samplesTtrT\_\{\\mathrm\{tr\}\}andTvalT\_\{\\mathrm\{val\}\}of sizesntrn\_\{\\mathrm\{tr\}\}andnvaln\_\{\\mathrm\{val\}\}\. Every candidate setS⊆FS\\subseteq Fpartitions the training rows by projection:

r∼Sr′⟺r\|S=r′\|S,πS:=Ttr/∼S\.r\\sim\_\{S\}r^\{\\prime\}\\quad\\Longleftrightarrow\\quad r\|\_\{S\}=r^\{\\prime\}\|\_\{S\},\\qquad\\pi\_\{S\}:=T\_\{\\mathrm\{tr\}\}/\{\\sim\_\{S\}\}\.Equivalently,πS\\pi\_\{S\}consists of the nonempty cellsBS,u:=\{r∈Ttr:r\|S=u\}B\_\{S,u\}:=\\\{r\\in T\_\{\\mathrm\{tr\}\}:r\|\_\{S\}=u\\\}foru∈valSu\\in\\mathrm\{val\}^\{S\}, withNS,u:=\|BS,u\|N\_\{S,u\}:=\|B\_\{S,u\}\|\. We writeπ′⪯π\\pi^\{\\prime\}\\preceq\\piwhenπ′\\pi^\{\\prime\}refinesπ\\pi; in particularS⊆S′S\\subseteq S^\{\\prime\}impliesπS′⪯πS\\pi\_\{S^\{\\prime\}\}\\preceq\\pi\_\{S\}\.

A training\-free block predictor\.Each candidate set is scored with the simplest predictor compatible with its partition\. Writingp^S​\(y∣u\):=NS,u−1​∑r∈Ttr𝟏​\{r\|S=u,r⁡\[Y\]=y\}\\widehat\{p\}\_\{S\}\(y\\mid u\):=N\_\{S,u\}^\{\-1\}\\sum\_\{r\\in T\_\{\\mathrm\{tr\}\}\}\\mathbf\{1\}\\\{r\|\_\{S\}=u,\\ r\[Y\]=y\\\}andp^0\(y\):=ntr−1∑r∈Ttr𝟏\{r\[Y\]=y\}\\widehat\{p\}\_\{0\}\(y\):=n\_\{\\mathrm\{tr\}\}^\{\-1\}\\sum\_\{r\\in T\_\{\\mathrm\{tr\}\}\}\\mathbf\{1\}\\\{r\[Y\]=y\\\}, we seth^S\(r\):=p^S\(⋅∣r\|S\)\\widehat\{h\}\_\{S\}\(r\):=\\widehat\{p\}\_\{S\}\(\\,\\cdot\\mid r\|\_\{S\}\)ifNS,r\|S\>0N\_\{S,r\|\_\{S\}\}\>0andh^S​\(r\):=p^0\\widehat\{h\}\_\{S\}\(r\):=\\widehat\{p\}\_\{0\}otherwise: the empirical label distribution on occupied cells, the training marginal on unseen projections\. This predictor serves only to select a structure; the final predictor is a graph\-learning model \(Section[4](https://arxiv.org/html/2608.11431#S4)\)\.

The alignment score𝒥\\mathcal\{J\}\.Alignment must balance two failure modes\. An under\-refined partition mixes differently labelled rows in one cell, which no cell\-constant predictor can resolve; an over\-refined one captures more label variation but produces small, poorly supported cells\. For a subsetS⊂FS\\subset Fof attributes, we measure fragmentation by

Ω\(Ttr,πS\):=1ntr∑u:NS,u\>0NS,u,\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\):=\\frac\{1\}\{n\_\{\\mathrm\{tr\}\}\}\\sum\_\{u:N\_\{S,u\}\>0\}\\sqrt\{N\_\{S,u\}\},
Figure 1:A candidate setSSpartitions the training rows by their projectionr\|Sr\|\_\{S\}\. Under\-refinement leaves differently labelled rows in the same cell; over\-refinement produces sparsely supported cells\. After selectingS⋆S^\{\\star\}, the chosen values become shared value nodes\.which is monotone under refinement and ranges fromntr−1/2n\_\{\\mathrm\{tr\}\}^\{\-1/2\}\(a single cell\) to11\(all singletons\)\. LetRisk^val​\(h^S\)\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\widehat\{h\}\_\{S\}\)be the average validation loss ofh^S\\widehat\{h\}\_\{S\}for some bounded loss functionℓ\\ell\. We scoreSSby

𝒥⁡\(πS\):=Risk^val​\(h^S\)\+λ​Ω​\(Ttr,πS\),λ≥0\.\\mathcal\{J\}\(\\pi\_\{S\}\):=\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\widehat\{h\}\_\{S\}\)\+\\lambda\\,\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\),\\qquad\\lambda\\geq 0\.\(1\)The first term rewards distinctions that track the labels on held\-out rows; the second charges for distinctions supported by too few training rows\. Minimising𝒥\\mathcal\{J\}therefore selects the partition best aligned with the labels: an attribute enters only when its held\-out gain outweighs the fragmentation it introduces\. The penalty is principled rather than heuristic\. For binary classification, letg^S\\widehat\{g\}\_\{S\}be the empirical majority classifier on the cells ofπS\\pi\_\{S\},Risk⋆\\mathrm\{Risk\}^\{\\star\}the unrestricted optimal population risk, andRiskS⋆\\mathrm\{Risk\}^\{\\star\}\_\{S\}the best population risk among classifiers constant on those cells\. ForSSfixed independently ofTtrT\_\{\\mathrm\{tr\}\}, with probability at least1−δ1\-\\delta,

Risk⁡\(g^S\)−Risk⋆≤\(RiskS⋆−Risk⋆\)\+Ω⁡\(Ttr,πS\)\+4​ln⁡\(4/δ\)2​ntr\.\\mathrm\{Risk\}\(\\widehat\{g\}\_\{S\}\)\-\\mathrm\{Risk\}^\{\\star\}\\leq\\bigl\(\\mathrm\{Risk\}^\{\\star\}\_\{S\}\-\\mathrm\{Risk\}^\{\\star\}\\bigr\)\+\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\+4\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\_\{\\mathrm\{tr\}\}\}\}\.ThusΩ\\Omegabounds the estimation term in a generalisation bound: refinement can lower approximation error, but raises the observable quantity controlling estimation\. Moreover, conditioning onTtrT\_\{\\mathrm\{tr\}\}, concentration on the validation sample is uniform over all2\|F\|2^\{\|F\|\}candidates: withεL:=L​\|F\|​ln⁡2\+ln⁡\(2/δ\)2​nval\\varepsilon\_\{L\}:=L\\sqrt\{\\frac\{\|F\|\\ln 2\+\\ln\(2/\\delta\)\}\{2n\_\{\\mathrm\{val\}\}\}\}, an exact minimiserS⋆S^\{\\star\}of \([1](https://arxiv.org/html/2608.11431#S2.E1)\) satisfies, with probability at least1−δ1\-\\delta,

Risk⁡\(h^S⋆\)\+λ​Ω​\(Ttr,πS⋆\)≤minS⊆F⁡\{Risk⁡\(h^S\)\+λ​Ω​\(Ttr,πS\)\}\+2​εL\.\\mathrm\{Risk\}\(\\widehat\{h\}\_\{S^\{\\star\}\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S^\{\\star\}\}\)\\leq\\min\_\{S\\subseteq F\}\\bigl\\\{\\mathrm\{Risk\}\(\\widehat\{h\}\_\{S\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\\bigr\\\}\+2\\varepsilon\_\{L\}\.Because the concentration event is uniform over all2\|F\|2^\{\|F\|\}candidates, it also covers candidates inspected adaptively during search; if the search returns anη\\eta\-suboptimal empirical minimiser, the oracle inequality holds with an additional additive termη\\eta\. Full statements and proofs are in[AppendixC](https://arxiv.org/html/2608.11431#A3)\.

## 3Finding an aligned attribute set

The score𝒥\\mathcal\{J\}specifies which attribute sets are desirable; this section addresses how to find one\. Exact minimisation over all2\|F\|2^\{\|F\|\}subsets is provably out of reach: even a requirement much weaker than alignment is already NP\-complete\.

Alignment rather than maximal separation\.An attribute setSS*separates the labels*whenr​\[Y\]≠r′​\[Y\]r\[Y\]\\neq r^\{\\prime\}\[Y\]impliesr\|S≠r′\|Sr\|\_\{S\}\\neq r^\{\\prime\}\|\_\{S\}for allr,r′∈Ttrr,r^\{\\prime\}\\in T\_\{\\mathrm\{tr\}\}\. 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\.

The desired partition is*aligned*with the task—fine enough to distinguish label\-relevant row types, coarse enough to preserve support among rows that should share information\. Even so, under a budget\|S\|≤k\|S\|\\leq k, the separation floor is computationally hard\.

###### Theorem 1\(Separation is NP\-complete\)\.

GivenTtrT\_\{\\mathrm\{tr\}\},FF, andkk, deciding whether someS⊆FS\\subseteq Fwith\|S\|≤k\|S\|\\leq kseparates the labels is NP\-complete\.

UnlessP=NP\\mathrm\{P\}=\\mathrm\{NP\}, no polynomial\-time exact method solves even this restricted selection problem, let alone the alignment objective\. We therefore use greedy local search\.

Algorithm 1SCS: structural column selection1:

T=Ttr∪TvalT=T\_\{\\mathrm\{tr\}\}\\cup T\_\{\\mathrm\{val\}\}, label

YY, candidates

F⊆AF\\subseteq A, direction

∈\{fwd,bwd\}\\in\\\{\\mathrm\{fwd\},\\mathrm\{bwd\}\\\}, signature

σ∈\{val,freq\}\\sigma\\in\\\{\\mathrm\{val\},\\mathrm\{freq\}\\\},

λ≥0\\lambda\\geq 0, tolerance

τ≥0\\tau\\geq 0
2:selected columns

S⋆S^\{\\star\}
3:if

σ=freq\\sigma=\\mathrm\{freq\}then

4:

T←FreqEncode​\(T,F\)T\\leftarrow\\textsc\{FreqEncode\}\(T,F\)// via \([2](https://arxiv.org/html/2608.11431#S3.E2)\)

5:endif

6:ifdirection

=fwd=\\mathrm\{fwd\}then

7:

S←∅S\\leftarrow\\emptyset;

moves⁡\(S\):=\{S∪\{c\}:c∈F∖S\}\\mathrm\{moves\}\(S\):=\\\{\\,S\\cup\\\{c\\\}:c\\in F\\setminus S\\,\\\}
8:else

9:

S←FS\\leftarrow F;

moves⁡\(S\):=\{S∖\{c\}:c∈S\}\\mathrm\{moves\}\(S\):=\\\{\\,S\\setminus\\\{c\\\}:c\\in S\\,\\\}
10:endif

11:repeat

12:

S′←arg⁡minS′′∈moves⁡\(S\)⁡𝒥⁡\(πS′′\)S^\{\\prime\}\\leftarrow\\arg\\min\_\{S^\{\\prime\\prime\}\\in\\mathrm\{moves\}\(S\)\}\\ \\mathcal\{J\}\(\\pi\_\{S^\{\\prime\\prime\}\}\)// via \([1](https://arxiv.org/html/2608.11431#S2.E1)\)

13:if

𝒥⁡\(πS\)−𝒥⁡\(πS′\)\>τ\\mathcal\{J\}\(\\pi\_\{S\}\)\-\\mathcal\{J\}\(\\pi\_\{S^\{\\prime\}\}\)\>\\tauthen

14:

S←S′S\\leftarrow S^\{\\prime\}
15:elsebreak

16:endif

17:until

moves⁡\(S\)=∅\\mathrm\{moves\}\(S\)=\\emptyset
18:return

S⋆←SS^\{\\star\}\\leftarrow S

Greedy search\.[Algorithm1](https://arxiv.org/html/2608.11431#alg1)\(Structural column selection, SCS\) performs local search on the refinement lattice of column subsets: at each step it evaluates every one\-column neighbour of the current set—one addition or removal, controlled by chosen direction—and moves to the neighbour with the lowest𝒥\\mathcal\{J\}\. Forward search starts from the coarsest partition \(S=∅S=\\emptyset\) and is cheap, terminating as soon as no single addition clears the tolerance; it is the right choice when few columns are expected to matter, but it can reject a column that becomes informative only jointly with another\. Backward search starts from the finest available partition \(S=FS=F\) and is more robust to such interactions, since an informative pair is present from the start rather than added one column at a time, at the cost of evaluating more candidates and relying onλ\\lambdato prune the extra columns it keeps\. The toleranceτ\\tausets the minimum improvement in𝒥\\mathcal\{J\}the search will act on, so it does not chase differences attributable to validation noise;τ=0\\tau=0recovers standard greedy descent\. The signatureσ\\sigmacontrols the initial table encoding \(values or frequency\), which is explained below\. Because𝒥\\mathcal\{J\}requires no model fit—each evaluation is one group\-by overTtrT\_\{\\mathrm\{tr\}\}and one pass overTvalT\_\{\\mathrm\{val\}\}—a full run costsO⁡\(\|F\|2​\(ntr\+nval\)\)O\\bigl\(\|F\|^\{2\}\(n\_\{\\mathrm\{tr\}\}\+n\_\{\\mathrm\{val\}\}\)\\bigr\)in the worst case\. The uniform validation event covers the adaptively returned subset, and the empirical optimisation gapη\\etaof greedy search enters the oracle inequality only additively\.

##### What the search scores\.

SCSmay be run on the tableTTdirectly \(σ\\sigma=val\) or on the frequency\-recoded copyFreqEncode​\(T,F\)\\textsc\{FreqEncode\}\(T,F\)\(σ\\sigma=freq\), which has the same rows and columns asTTand entries

FreqEncode​\(T,F\)​\[r,c\]:=\|\{r′∈T:r′​\[c\]=r⁡\[c\]\}\|,c∈F\.\\textsc\{FreqEncode\}\(T,F\)\[r,c\]:=\\bigl\|\\\{\\,r^\{\\prime\}\\in T:r^\{\\prime\}\[c\]=r\[c\]\\,\\\}\\bigr\|,\\qquad c\\in F\.\(2\)leaving the label and the attributes outsideFFunchanged, so each cell in a candidate column is replaced by the number of times its value occurs in that column\. This changes what a column is scored on: under value encoding, a column scores well when particular values track the label; under frequency encoding, when the multiplicity pattern it induces does—whether a value is rare or shared, not which value it is\. The second is the weaker signal, and deliberately so: it selects columns for the structure they expose rather than for the labels their values happen to carry\. This affects the score alone, since the constructor expands the selected columns by their original values in either case\.

Extension to relational databases\.In the multi\-table setting the subset search is unchanged; only the table changes\. We materialiseT~:=T⋈d𝒟\\widetilde\{T\}:=T\\bowtie\_\{d\}\\mathcal\{D\}by left joins along all foreign\-key paths of length<d<dand evaluate candidates onT~\\widetilde\{T\}\. Each expanded row retains the identifier of its originating primary row\. To deal with join multiplicity, duplicate appearances of a primary row are collapsed within each cell, and if rowiithen occurs inki​\(S\)k\_\{i\}\(S\)distinct cells, each appearance receives weight1/ki​\(S\)1/k\_\{i\}\(S\), so every primary row contributes one total unit\. The selected attributes are then added to the graph: each becomes value nodes attached to the rows of the table it belongs to, and the foreign\-key path fromTTto that table is materialised\. The skeleton is carried in by selection rather than fixed in advance, so selecting nothing returns the trivial grable \(γtriv\\gamma\_\{\\mathrm\{triv\}\}\)\.

## 4AutoGrable

AutoGrableis our table\-to\-graph constructor\. Given a labelled tableTTand candidate attributesFF, it runsSCS\([Section3](https://arxiv.org/html/2608.11431#S3)\) to obtainS⋆S^\{\\star\}, then expands the selected columns into a graph, the*incidence grable*GS⋆​\(T\)G\_\{S^\{\\star\}\}\(T\)\(see Figure[1](https://arxiv.org/html/2608.11431#S2.F1)\), on which any row\-level graph\-learning method can be trained\. This section supplies the graph\-side vocabulary, grables and colour refinement, and proves the correspondence announced in[Section2](https://arxiv.org/html/2608.11431#S2): the partitionπS⋆\\pi\_\{S^\{\\star\}\}thatSCSoptimises through group\-bys is exactly the structural row partition ofGS⋆​\(T\)G\_\{S^\{\\star\}\}\(T\), the partition that bounds message\-passing GNNs\.

Grables\.A*constructor*γ\\gammamaps a table to a typed, attributed graphGC,TγG^\{\\gamma\}\_\{C,T\}with one distinguished*row node*vrv\_\{r\}per rowrr; the result is a*grable*\[grables\]\.111The trivial grableγtriv\\gamma\_\{\\textsl\{triv\}\}is the simplest grable, only consisting of row nodes and no edges\.A row\-level GNN predicts at the row nodes, so it can exploit information from other rows only through the edges the constructor supplies\. In this way a grable turns a*row\-local*predictor, one whose output for a row is unchanged when all other rows are removed, into an*extension\-sensitive*one\[grables\]\.

Colour refinement\.What a message\-passing GNN can distinguish is governed by colour refinement \(or 1\-WL\)\. For a typed, attributed graphGG, letχG\(0\)​\(v\)\\chi\_\{G\}^\{\(0\)\}\(v\)encode the initial node type and attributes exposed to the GNN, and iterateχG\(t\+1\)​\(v\)=HASH⁡\(χG\(t\)​\(v\),\{\{\(type⁡\(v,w\),χG\(t\)​\(w\)\):w∈NG​\(v\)\}\}\)\\chi\_\{G\}^\{\(t\+1\)\}\(v\)=\\operatorname\{HASH\}\\\!\\left\(\\chi\_\{G\}^\{\(t\)\}\(v\),\\\{\\\!\\\!\\\{\(\\operatorname\{type\}\(v,w\),\\chi\_\{G\}^\{\(t\)\}\(w\)\):w\\in N\_\{G\}\(v\)\\\}\\\!\\\!\\\}\\right\)withHASH\\operatorname\{HASH\}injective\. On a finite graph the induced partition stabilises;πCR​\(G\)\\pi\_\{\\mathrm\{CR\}\}\(G\)denotes its restriction to the row nodes\. Two row nodes with the same stable colour cannot receive different outputs from any message\-passing GNN, and sufficiently expressive injective architectures attain this bound\[xu2018how,morris\-WL\-go\-neural\]\. The partitionπCR​\(G\)\\pi\_\{\\mathrm\{CR\}\}\(G\)is thus the expressive ceiling of graph learning onGG\.

The incidence grable\.ForS⊆AS\\subseteq A, the incidence grableGS​\(T\):=GC,TγincSG\_\{S\}\(T\):=G^\{\\gamma\_\{\\mathrm\{inc\}\}^\{S\}\}\_\{C,T\}contains

1. 1\.one row nodevrv\_\{r\}perr∈Tr\\in T, carrying the unexpanded attributesr\|A∖Sr\|\_\{A\\setminus S\}; and
2. 2\.one value nodeuc,au\_\{c,a\}per occurring typed value\(c,a\)\(c,a\)withc∈Sc\\in S, whose initial feature identifies\(c,a\)\(c,a\)\.

An edge of typeccjoinsvrv\_\{r\}anduc,au\_\{c,a\}exactly whenr⁡\[c\]=ar\[c\]=a; the labelYYis never exposed\. Rows that agree on a selected value are thus wired to a common value node, while the remaining attributes stay local to their row\. The typed\-value encoding matters: were literal values hidden, distinct values with identical structural profiles could remain colour\-equivalent\. To isolate the structure contributed bySSfrom the features that happen to sit on the rows, letGS∘​\(T\)G\_\{S\}^\{\\circ\}\(T\)be the*row\-feature\-erased reduct*ofGS​\(T\)G\_\{S\}\(T\): all row nodes receive the same initial colour, while value\-node features and edge types are retained\. The reduct is an analysis device only\.

###### Lemma 1\.

For allr,r′∈Ttrr,r^\{\\prime\}\\in T\_\{\\mathrm\{tr\}\},πCR​\(GS∘​\(Ttr\)\)=πS\\pi\_\{\\mathrm\{CR\}\}\\bigl\(G\_\{S\}^\{\\circ\}\(T\_\{\\mathrm\{tr\}\}\)\\bigr\)=\\pi\_\{S\}\.

The lemma closes the loop\.SCScomputesπS\\pi\_\{S\}by a group\-by, yetπS\\pi\_\{S\}is precisely the stable row partition that the selected incidence structure induces once row features are suppressed\. In minimising𝒥\\mathcal\{J\}over column subsets,SCSis therefore searching over the expressive ceilings of the corresponding grables—without ever building a graph\. Note that the cells are structural row types, not connected components: rows in different cells may share value nodes and exchange messages through them\.

SelectingSSis a table\-space operation, but the object it selects is not\. By[Lemma1](https://arxiv.org/html/2608.11431#Thmlemma1)the graph adds no distinguishing power overπS\\pi\_\{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\. Such statistics can be materialised as columns one at a time, but which grouping to count over, and which row\-local attribute it should interact with, are task\-dependent\. ExpandingS⋆S^\{\\star\}into structure leaves that choice to the downstream learner rather than fixing it in advance\.

What the downstream GNN receives\.The downstream learner receives the full graphGS⋆​\(T\)G\_\{S^\{\\star\}\}\(T\), not the reduct\. Its row nodes retainr\|A∖S⋆r\|\_\{A\\setminus S^\{\\star\}\}, which may separate rows within a structural cell, soπCR​\(GS⋆​\(T\)\)⪯πS⋆\\pi\_\{\\mathrm\{CR\}\}\\bigl\(G\_\{S^\{\\star\}\}\(T\)\\bigr\)\\preceq\\pi\_\{S^\{\\star\}\}\. The selected columns fix the cross\-row communication channels; the unexpanded attributes supply row\-local evidence\. The GNN combines both, and is in no way restricted to the block predictorSCSused for scoring\.

## 5Experiments

We ask three questions:\(RQ1\)DoesAutoGrablerecover the columns that generate a task and reject the rest?\(RQ2\)Is𝒥\\mathcal\{J\}an indicator of downstream performance for 1\-WL\-bounded learners?\(RQ3\)Under a fixed predictor, doesAutoGrablebuild graphs that outperform other table\-to\-graph constructors? RQ1 requires known ground\-truth structure and is answered on controlled tasks; RQ2 and RQ3 are answered on real tabular, transactional, and relational tasks\.

### 5\.1Controlled tasks: does alignment select relevant structure?

Setup\.RQ1 is about selection, not prediction, so no model is trained in this section: we runAutoGrableto its selected subsetS⋆S^\{\\star\}and compare that subset against the columns the task was built from\. This requires ground truth, which is why the tasks are constructed\.

*Data and tasks\.*The base table is Census/Adult\[adult\-dataset\], whose categorical columns form the column universeCC\. A task is a choice ofS⋆⊆CS^\{\\star\}\\subseteq Ctogether with a label generated fromS⋆S^\{\\star\}alone\. We include row\-local tasks:*single\-value*,*conjunction*, and*interaction*\(XOR\) and extension\-sensitive ones:*count*, and*duplicate*\. Full generating processes are in Appendix[D\.2](https://arxiv.org/html/2608.11431#A4.SS2)\.

*Configurations\.*We sweep the axes ofAutoGrable: signature \(*value*,*frequency*\), search direction \(*forward*,*backward*\), andλ\\lambda\. Table[1](https://arxiv.org/html/2608.11431#S5.T1)reports the noise\-free tasks atλ∈\{0,1\}\\lambda\\in\\\{0,1\\\}; the full sweep and the behaviour under label noise are in Appendix[D\.5](https://arxiv.org/html/2608.11431#A4.SS5)\. Task instances are drawn once per \(family, seed\)\. Each cell isN=10N=10seeds, resampling the rows and the planted columns\.

*Metrics\.*LetS⋆S^\{\\star\}be the selected columns andS∘S^\{\\circ\}the set the task was built from\. RecoveryRec=\|S⋆∩S∘\|/\|S∘\|\\mathrm\{Rec\}=\|S^\{\\star\}\\cap S^\{\\circ\}\|/\|S^\{\\circ\}\|measures how much of the generating set is kept;Exact=𝟙\[S⋆=S∘\]\\mathrm\{Exact\}=\\mathbbm\{1\}\[S^\{\\star\}=S^\{\\circ\}\]additionally requires that nothing else is selected\. We separate failure of the objective from failure of the search: an*objective\-metric mismatch*is a run in which𝒥⁡\(πS∘\)≥𝒥⁡\(πS⋆\)\\mathcal\{J\}\(\\pi\_\{S^\{\\circ\}\}\)\\geq\\mathcal\{J\}\(\\pi\_\{S^\{\\star\}\}\)—the search stopped somewhere the score prefers to the generating set, so the score, not the search, is what rankedS∘S^\{\\circ\}below—and a*procedure failure*is a stopping point that is not optimal for𝒥\\mathcal\{J\}\. Only the second is a shortcoming of the algorithm rather than of the objective\.

Table 1:Column recovery on synthetic tasks,N=10N=10seeds\. Rows showλ∈\{0,1\}\\lambda\\in\\\{0,1\\\}\(more values in App\.[D\.5](https://arxiv.org/html/2608.11431#A4.SS5)\)\. Cell format: %exact \(%recovery\);∅\\emptysetmarks a cell where the selected column set was empty\. A†\\daggermarks an objective\-metric mismatch against ground truth \(𝒥⁡\(true\)≥𝒥⁡\(reached\)\\mathcal\{J\}\(\\text\{true\}\)\\geq\\mathcal\{J\}\(\\text\{reached\}\)\)\.Results\.RQ1 asks whetherAutoGrablerecovers the columns that generate a task and rejects the rest\. Table[1](https://arxiv.org/html/2608.11431#S5.T1)answers yes on both counts, but the two halves are controlled by different axes: recovery is decided by the signature, rejection byλ\\lambdaand the search direction\.

*Recovery\.*With the value signatureAutoGrablerecovers all tasks\. Recovering Count is consistent with it being extension\-sensitive: selection only has to find the column, and on a fixed table the partition by that column’s values already fixes each row’s multiplicity: the graph is needed to compute the target, not to identify the column\. Duplicate with forward direction fails for the opposite reason: its column is near\-unique, so its value partition is almost all singletons\. The frequency signature is more suited to recover it\. Symmetrically, frequency encoding returns the empty set on the row\-local families \(except at backward withλ=0\\lambda=0\), and the†\\daggermarks confirm𝒥⁡\(∅\)≤𝒥⁡\(S∘\)\\mathcal\{J\}\(\\emptyset\)\\leq\\mathcal\{J\}\(S^\{\\circ\}\)there: frequencies discard value identity, which is what a row\-local label depends on, so the score reports that no structure is worth building\. Recovery is therefore complete when the signature matches the family, and the failures are informative rather than silent\.

*Exact recovery\.*A gap between Rec and Exact means the selected set contains the true columns and more, and this is whereλ\\lambdaacts\. It acts mainly on backward search, which keeps more columns than forward\. Atλ=0\\lambda=0backward search reaches Rec=100=100with Exact between00and9090: the true columns are kept, but so are others\. Atλ=1\\lambda=1the gap closes, with Exact=100=100on four of five families\. This isΩ\\Omegadoing its job\. The effect is not uniform: forward search also leaves a gap on Conjunction atλ=0\\lambda=0and there raisingλ\\lambdastops the search earlier rather than dropping the extra column, so Rec falls to8080and Exact does not move; under frequency encoding with backward search, raisingλ\\lambdacollapses the row\-local families from Rec=100=100to the empty set\. Soλ\\lambdacloses the Rec–Exact gap where the search starts too large, and costs Rec where it does not\.

### 5\.2Real tasks: does alignment relate to downstream performance?

Setup\.RQ2 and RQ3 need different apparatus\. RQ2 compares𝒥\\mathcal\{J\}against downstream performance across many graphs for a single task; we take these from RDB2G\-Bench\[rdb2g\], which enumerates schema\-level constructions for RelBench\[relbench\-v1,relbench\-v2\]tasks and reports trained\-model performance for each\. RQ3 compares construction methods, one graph per method, on the same task and split\.

*Fixed predictor\.*We use GraphSAGE throughout, with fixed architecture, budget and hyperparameters within regime \(see Appendix[D\.6\.1](https://arxiv.org/html/2608.11431#A4.SS6.SSS1)\) for every construction and every dataset, and no per\-constructor tuning\. Underγtriv\\gamma\_\{\\mathrm\{triv\}\}there are no edges, so GraphSAGE reduces to an MLP on the row features\. Differences in performance across constructors are attributable to the construction alone\.

*Constructors\.*γtriv\\gamma\_\{\\mathrm\{triv\}\}is the no\-structure floor\. The fixed constructions are the full incidence grableγinc\\gamma\_\{\\mathrm\{inc\}\}\[grables\], which exposes every eligible column and so performs no selection, and, for foreign\-key schemas, the relational entity graph \(REG\)\[RDL\-fey\], which takes the schema itself as the graph \(defined only in the relational case\)\. The random constructor draws a column subset uniformly at random in both size and membership, redrawn independently for each seed, and separates the contribution of*which*columns are selected from that of selecting any columns at all\. The task\-aware comparison is auGraph\[augraph\], which scores attributes individually and has multiple metrics\. The one reported corresponds to the one with the best performance in the validation set \(gnn\-gainon all tasks studied\)\.

*Datasets\.*Three regimes\. Transactional: FDB\[fraud\-benchmark\]single tables that are not i\.i\.d\. at the table level—rows share device, merchant and account values\. Relational: RelBench\[relbench\-v1,relbench\-v2\]\. Negative control: the i\.i\.d\. single\-table benchmark TabArena\[tabarena\], where each label should depend only on its own row\.

*Protocol\.*Learning is transductive: one graph per dataset carrying train, validation and test row masks, so a node may aggregate from rows in other splits while labels are read only within its own\. On the timestamped datasets splits are contiguous blocks in time\. The neighbour sampler restricts each row to aggregate from rows at or before its own timestamp\. For the RDB2G graph constructions, we compute𝒥\\mathcal\{J\}from the partition induced by colour refinement\.

Results\.𝒥\\mathcal\{J\}acts as a one\-sided screen rather than a ranking: low𝒥\\mathcal\{J\}is necessary for strong downstream AUC on these candidates, not sufficient\. Ondriver\-top3, retaining the two lowest𝒥\\mathcal\{J\}levels discards80%80\\%of the candidate graphs and all ten of the best\-performing graphs survive\. The correlations in Table[2](https://arxiv.org/html/2608.11431#S5.T2)are consistent with this: they are negative throughout, but attenuated by ties, since𝒥\\mathcal\{J\}takes limited distinct values over the constructions \(Figure[5\.2](https://arxiv.org/html/2608.11431#S5.SS2)\) and the AUC values are themselves tightly clustered\. This is a property of the candidate set—RDB2G\-Bench enumerates schema\-level edits over a fixed key–foreign\-key skeleton, so the induced row partitions differ in few ways\. The association is weaker on test than on validation, as expected since𝒥\\mathcal\{J\}is also computed on the validation split\.

Table 2:Correlation \(Spearman’sr​h​orhoand Kendall’s\-tauτb\\tau\_\{b\}\) between𝒥⁡\(⋅\)\\mathcal\{J\}\(\\cdot\)and downstream performance \(AUC on validation and test splits\)\. Graph constructions and performance obtained from RDB2G\-Bench, using GraphSAGE as model and all seeds available \(5 per graph forstudy\-outcomeand 15 fordriver\-top3\)\.
\.

Figure 2:𝒥⁡\(color,task\)\\mathcal\{J\}\(\\text\{color\},\\text\{task\}\)vs\. AUC on val set, taskdriver\-top3,7474graphs,1515seeds per graphTable 3:Downstream test AUROC \(↑\\uparrow\) under a*fixed*predictor\. Mean±\\pmstd overN=15N\{=\}15seeds\. Best inbold, secondunderlined\.AutoGrablereported results are for fixed setup \(forward direction,λ=1\\lambda=1,σ=\\sigma=frequencies\)\. An∗\*marks equivalent constructions\. More results in Tables[7](https://arxiv.org/html/2608.11431#A4.T7)and[9](https://arxiv.org/html/2608.11431#A4.T9)AutoGrableuses𝒥\\mathcal\{J\}as a filter: it searches for a column subset𝒥\\mathcal\{J\}does not discard, and RQ3 asks whether the resulting graph beats the graphs the alternatives return, under the same predictor\. Table[3](https://arxiv.org/html/2608.11431#S5.T3)shows that it does, in both the single\-table and the multi\-table setting\. More results for other datasets and tasks can be found in Appendix[D\.6](https://arxiv.org/html/2608.11431#A4.SS6)\.

The baselines fail in three ways\. Fixed constructions do not select: exposing every eligible column \(γinc\\gamma\_\{\\mathrm\{inc\}\}\) loses to building no graph on three of five tasks, and the schema skeleton \(REG\) loses toγtriv\\gamma\_\{\\mathrm\{triv\}\}onstudy\-outcome\. Structure is not free, and a column that fragments the rows costs more than the signal it carries\. Random selection separates how many columns from which ones: it beats full incidence on some tasks, so part of the gain comes from selecting fewer columns, but it stays behind task\-aware selection\.AutoGrableimproves on auGraph everywhere, and at a lower cost: auGraph’s best\-performing metric,*gnn\-gain*, uses a GNN to score an attribute by materialising the augmented graph and running it over the validation nodes, which is done for every promotion\.

The taskstudy\-outcomeis special: the row\-local predictor is the strongest baseline and every constructor that builds structure loses to it\.AutoGrablereturns∅\\emptysetand soγtriv\\gamma\_\{\\mathrm\{triv\}\}itself: no subset lowers validation risk enough to pay for the fragmentation it introduces\. It is the only method compared here that can decline to build a graph\. The same behaviour appears on the i\.i\.d\. benchmark TabArena\[tabarena\], where each label depends on its own row and structure should not help \(App\.[D\.6\.3](https://arxiv.org/html/2608.11431#A4.SS6.SSS3)\)\.

## 6Related work

Expressive power as a design target\.Message\-passing networks separate two nodes only when colour refinement does\[xu2018how,morris\-WL\-go\-neural\]; for relational data the canonical route to a graph is the incidence encoding, whose power under11\-WL is characterised byGro\+2020\. This literature is read almost always in one direction: given a graph, how much can a model distinguish, and how can an architecture distinguish more\. Read the other way, the same bound is a statement about capacity\.morris2023wlvcbound MPNNs’ VC dimension by the number of colours11\-WL produces, and what rules generalisation is whether the induced classes align with the labels rather than how many there are\[li2025towards,maskey2026graph\]\. We apply this reading to the construction rather than the architecture\. With the model class fixed at the11\-WL bound, a construction reaches the learner only as a partition of the rows, so construction is partition design and finer is not necessarily better\.

Learning or modifying a graph\.When no graph is given, one can learn one by fixing the data points as nodes and inferring connectivity jointly with the predictor\[franceschi,kazi2022dgm,fatemi2021slaps\]; seezhou2023opengslfor a survey\. Two assumptions divide this setting from ours\. The node set is given—a table offers no such points, and what the row set becomes as a graph, including its value nodes and their typing, is itself the construction we study\. And edge quality is read from the downstream objective, knowable only by training the predictor; our criterion is a property of the induced row partition, evaluated before any model is trained\. A parallel line modifies a graph that already exists, adding or deleting edges to improve information flow via curvature\[topping2022\], spectral gap\[karhadkar2023\], or effective resistance\[black2023\]\. Those objectives are label\-independent flow proxies over a given topology; ours is a label\-dependent property of a graph that does not yet exist\.

Graphs from tables and databases\.Table\-to\-graph constructions includekk\-nearest\-neighbour graphs over rows, row–value bipartite graphs, and hypergraph variants\[li2025gnn4tdl\]; RDL instead fixes the entity graph induced by the key–foreign\-key skeleton\[RDL\-fey\]and develops architectures over it\[chen2025relgnn,dwivedi2026relgt\]\. An empirical finding is that this skeleton is not the right graph and that not all of it helps: the extraction strategy materially changes performance\[wang2024dbinfer\], the best schema\-level graph model beats the standard heuristic by up to10%10\\%while being hard to identify without training\[rdb2g\], and validation performance is an unreliable selector across relational architectures\[chen2026relatron\]\. Our position is stronger than*select carefully*: the graph adds no distinguishing power, so its value lies in enabling cross\-row interactions only when*it pays off*, which is why declining to build one is an admissible output\.

Automatic construction from tables\.The closest methods propose a construction and judge it by a trained model\. auGraph\[augraph\]promotes attributes to nodes by relevance scores, one of which trains a GNN per candidate; AutoG\[autog\]has an LLM propose schema transformations and selects among them with an oracle that trains a basket of GNNs\.AutoGrablereturns an object of the same class over the same input regime, and its search calls no trained graph model—a candidate costs one group\-by and one pass over the validation split\.

See Appendix[A](https://arxiv.org/html/2608.11431#A1)for an extended discussion on related work\.

## 7Conclusions

We asked what makes a graph good for a table, and answered it before any model is trained\. 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](https://arxiv.org/html/2608.11431#Thmlemma1)\)\. Construction therefore reduces to column selection, and the criterion that matters is alignment with the label rather than refinement\.

We introduced a score that selects columns exposing label\-relevant structure, and turned it intoAutoGrable, which optimises it greedily since the weaker selection problem is NP\-complete\. Empirically,AutoGrable\(i\) recovers the relevant columns on controlled tasks, and \(ii\) produces graphs that match or improve on canonical and task\-aware baselines under a fixed predictor, in both the single\-table and the multi\-table setting\. It can also decline to build a graph when no construction pays for the fragmentation it introduces\.

## References

## GenAI Usage Statement

In this work, we used generative AI tools for language editing and basic coding assistance\. Specifically, we used Claude \(Anthropic\) for grammar correction, copy\-editing, and phrasing of the manuscript, and Claude Code \(Anthropic\) as a coding assistant during implementation and debugging of theAutoGrablecodebase and the experimental pipeline\. We have reviewed all AI\-assisted work and take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI\.

## Appendix AExtended related work

This appendix expands Section[6](https://arxiv.org/html/2608.11431#S6)along three axes that the main text compresses: the expressivity–capacity literature underlyingΩ\\Omega, the range of table\-to\-graph constructions, and a per\-invariant comparison against automatic constructors\.

### A\.1Expressivity, capacity, and the partition

Beyond the11\-WL bound\[xu2018how,morris\-WL\-go\-neural\],barcelo2020give the logical characterisation of what MPNNs express, andGro\+2020the analysis of incidence encodings of relational structures that ourγincS\\gamma^\{S\}\_\{\\mathrm\{inc\}\}instantiates\. This literature is read in one direction: given a graph, how much can a model distinguish, and how can an architecture distinguish more\.

The capacity side of the same bound appears less in construction work\.morris2023wlvcbound the VC dimension of MPNNs by the number of colours11\-WL produces, andcarrasco2026rademachercomplexitygraphneurallink the empirical Rademacher complexity of a class constant on the colour classes by the number of those classes and how the sample distributes across them\. The colouring a construction induces is simultaneously what the learner can separate and what it can overfit\. It follows that expressive power alone does not determine generalisation\[franks2024margin,maskey2026graph\]: what rules it is whether the induced classes align with the labels, a trade\-off between intra\-class concentration and inter\-class separation\[li2025towards\]\.

This is precisely the spirit of𝒥\\mathcal\{J\}: the first term is what refinement buys, the second is what it costs, and the sum is minimised to balance the trade\-off\. Lemma[5](https://arxiv.org/html/2608.11431#Thmlemma5)supplies the corresponding statement in our setting, withΩ\\Omegaas the occupancy\-resolved form of the complexity term\.

Two differences are worth stating\. The results from previous literature diagnose a fixed architecture on a given input, while we use it as the objective for choosing the input\. They are also stated at the graph level, over a sample of graphs; our partition is on the row nodes of a single graph\.

### A\.2Learning a graph, and modifying one

Latent graph inference learns a soft adjacency over given nodes, either by a bi\-level program over a distribution on edges\[franceschi\], by similarity in a learned embedding\[kazi2022dgm\], by alternating between structure and representation\[chen2020idgl\], or with an auxiliary denoising objective\[fatemi2021slaps\];zhu2021gslsurveyandzhou2023opengslsurvey the area and its benchmarks\. The presupposition throughout is geometric: an edge means proximity in some feature space\. A table’s native relation is exact agreement on a categorical value, which is combinatorial, and its node set is not given\. Rewiring addresses a different failure mode—information flow over an existing topology\[alon2021\], corrected by curvature\-guided edge surgery\[topping2022\], spectral\-gap maximisation\[karhadkar2023\], or effective\-resistance criteria\[black2023\]\. These criteria are computed from topology alone and are label\-independent, and could be applied downstream of any constructor, including ours\.

### A\.3Table\-to\-graph constructions

li2025gnn4tdlorganise single\-table constructions by which tabular elements become nodes \(instances, features, values, cells\) and by how edges are created \(intrinsic, rule\-based, learned, retrieval\-based\); our incidence grable is the row–value intrinsic case\. In the multi\-table setting the relational entity graph\[RDL\-fey\]fixes rows as nodes and foreign keys as edges, and the RelBench line\[relbench\-v1,relbench\-v2\]standardises tasks over it, with architectures exploiting its specific structure\[chen2025relgnn,dwivedi2026relgt\]\. Structure can also be induced implicitly through cross\-row attention in tabular foundation models\[tabpfn\_nature,qu2025tabicl\]; there the induced structure depends on tokenisation and architectural detail and is not available as an object one can inspect, compare, or hold fixed, which is what the grable abstraction\[grables\]isolates\. In the reverse direction, benchmarks with tabular features on given graphs\[bazhenov2025GraphLand\]probe whether structure is used at all; our negative control on TabArena\[tabarena\]plays the analogous role from the tabular side\.

### A\.4Which structure is worth having

Three recent results converge on the same finding from different directions\.

wang2024dbinfermake the relational\-to\-graph extraction strategy an explicit benchmark axis \(Row2Node, Row2N/E, dummy tables\) and report that the choice materially changes performance\.rdb2genumerate schema\-level graph models over55databases and1212tasks, producing roughly5050k graph–performance pairs, and find the best model improves on the common heuristic by up to10%10\\%while remaining hard to identify without repeated GNN training;chen2026relatronfind that relational deep learning does not consistently beat deep feature synthesis, that no single architecture dominates, and that validation performance is an unreliable selector, and respond with training\-free task signals for routing\. Their object of selection is the architecture given a graph; ours is the graph given an architecture \(or a family of them\)\.

### A\.5Automatic table to graph constructors

Table[4](https://arxiv.org/html/2608.11431#A1.T4)compares the methods that produce a graph automatically\. We separate them by what they return, what they require as input, and what a single candidate evaluation costs\.

Table 4:Automatic table\-to\-graph constructors by invariant\.*Candidate cost*is the work required to score one candidate construction during search\.AutoG’s oracle uses early\-stage validation performance averaged over a basket of GNNs, which is cheaper than full training per candidate but is still a trained graph model in the loop\.

### A\.6Relation to feature selection and to explanation

Selecting columns whose induced partition refines the label partition, viewed as a covering problem over pairs with different labels, is Test Cover, which is Theorem[1](https://arxiv.org/html/2608.11431#Thmtheorem1)\. However, two things separate our objective from standard filter feature selection\.

1. 1\.In our setting, the selected columns are not features but structure: they become value nodes, and what they contribute is cross\-row communication rather than row\-local signal\.
2. 2\.The partition scored by𝒥\\mathcal\{J\}is not a convenient proxy: it is exactly the structural row partition the selected construction induces, and hence the component of the downstream learner’s expressive ceiling that the construction controls\. The downstream GNN also receives the unexpanded row features, so it can separate rows within a cell;𝒥\\mathcal\{J\}scores what the construction contributes, not the full model\.

Selection cannot substitute construction—on extension\-sensitive targets no row\-local predictor over the selected columns can compute the label at any capacity\[grables\]\.

rissaki2025viewsare formally the closest work we are aware of: they select database views minimising deviation\-from\-determinacy plusλ⋅cost\\lambda\\cdot\\mathrm\{cost\}, and observe that even the projection\-only fragment reduces to hitting set\. The objective has the same shape as𝒥\\mathcal\{J\}—fidelity plus a regularised complexity term—and the same combinatorial core\. The difference is directional: their views explain a model that has already been trained, ours chooses a construction before one exists\.

## Appendix BConnection to Test Cover and Min Features Problem

Selecting columns so that the induced row partition separates the labels is theMin\-Features\(orkk\-Feature\-Set\) problem, shown NP\-complete bydavies1994np\. We record here an alternative derivation as an instance of the classicalTest Coverproblem\. We restate the result on the incidence constructions graph side\.

### B\.1Setup

A tableTThas a finite set of rows, a label columnYY, and feature columnsAA\. Entries are real numbers; categorical columns are assumed one\-hot encoded, so this is without loss of generality\. ForS⊆AS\\subseteq Aand a rowrr, writer\|Sr\|\_\{S\}for the restriction ofrrtoSS, and letπS\\pi\_\{S\}be the partition of rows defined byr∼r′⇔r\|S=r′\|Sr\\sim r^\{\\prime\}\\iff r\|\_\{S\}=r^\{\\prime\}\|\_\{S\}\. LetπY\\pi\_\{Y\}be the partition induced by the label column\. A columncc*separates*a pair\{r,r′\}\\\{r,r^\{\\prime\}\\\}ifr​\[c\]≠r′​\[c\]r\[c\]\\neq r^\{\\prime\}\[c\], and a setSSseparates the pair if somec∈Sc\\in Sdoes, i\.e\.r\|S≠r′\|Sr\|\_\{S\}\\neq r^\{\\prime\}\|\_\{S\}\.

###### Definition 1\(Label\-separating set\)\.

S⊆AS\\subseteq Ais*label\-separating*ifπS\\pi\_\{S\}refinesπY\\pi\_\{Y\}: equivalently, every pair of rows with distinct labels is separated by somec∈Sc\\in S\.

###### Definition 2\(WL\-Separate\)\.

*Given*a tableTTwith label columnYY, feature columnsAA, andk∈ℕk\\in\\mathbb\{N\};*decide*whether there exists a label\-separatingS⊆AS\\subseteq Awith\|S\|≤k\|S\|\\leq k\. The optimization version,Min\-Separate, asks for a label\-separatingSSof minimum size\.

### B\.2The test cover problem

###### Definition 3\(Test cover\)\.

Given a set of itemsIIand a collection of tests𝒯⊆2I\\mathcal\{T\}\\subseteq 2^\{I\}, where a testtt*separates*\{i,i′\}\\\{i,i^\{\\prime\}\\\}iff\|t∩\{i,i′\}\|=1\|t\\cap\\\{i,i^\{\\prime\}\\\}\|=1;*find*a smallest𝒯′⊆𝒯\\mathcal\{T\}^\{\\prime\}\\subseteq\\mathcal\{T\}such that every pair of items is separated by somet∈𝒯′t\\in\\mathcal\{T\}^\{\\prime\}\.

Test cover is set cover over the universe of item pairs\(I2\)\\binom\{I\}\{2\}: a test covers exactly the pairs it separates\. It is NP\-complete\[garey1979computers\]\.

### B\.3Reduction and hardness

###### Lemma 2\(Test Cover≤p\\leq\_\{p\}WL\-Separate\)\.

Given an instance\(I,𝒯\)\(I,\\mathcal\{T\}\)withI=\{1,…,m\}I=\\\{1,\\dots,m\\\}and𝒯=\{t1,…,tp\}\\mathcal\{T\}=\\\{t\_\{1\},\\dots,t\_\{p\}\\\}, construct a tableTTwith

- •one rowrir\_\{i\}per itemi∈Ii\\in I;
- •one feature columncjc\_\{j\}per testtjt\_\{j\}, withri​\[cj\]=1r\_\{i\}\[c\_\{j\}\]=1ifi∈tji\\in t\_\{j\}andri​\[cj\]=0r\_\{i\}\[c\_\{j\}\]=0otherwise;
- •a label column with a distinct label per row,ri​\[Y\]=ir\_\{i\}\[Y\]=i\.

Then for everyS⊆\{c1,…,cp\}S\\subseteq\\\{c\_\{1\},\\dots,c\_\{p\}\\\},SSis label\-separating iff\{tj:cj∈S\}\\\{t\_\{j\}:c\_\{j\}\\in S\\\}is a test cover of\(I,𝒯\)\(I,\\mathcal\{T\}\)\.

###### Proof\.

Since labels are distinct, every pair of rows must be separated, so label\-separation means every pair\{ri,ri′\}\\\{r\_\{i\},r\_\{i^\{\\prime\}\}\\\}is separated by somecj∈Sc\_\{j\}\\in S\. By constructioncjc\_\{j\}separates\{ri,ri′\}\\\{r\_\{i\},r\_\{i^\{\\prime\}\}\\\}iffri​\[cj\]≠ri′​\[cj\]r\_\{i\}\[c\_\{j\}\]\\neq r\_\{i^\{\\prime\}\}\[c\_\{j\}\]iff exactly one ofi,i′i,i^\{\\prime\}lies intjt\_\{j\}ifftjt\_\{j\}separates\{i,i′\}\\\{i,i^\{\\prime\}\\\}\. HenceSSseparates all pairs iff\{tj:cj∈S\}\\\{t\_\{j\}:c\_\{j\}\\in S\\\}covers all pairs\. ∎

###### Theorem 2\.

WL\-Separateis NP\-complete\.

###### Proof\.

Membership: givenSS, checking that every pair of differently\-labelled rows is separated takes polynomial time\. Hardness follows from Lemma[2](https://arxiv.org/html/2608.11431#Thmlemma2), which is size\-preserving and therefore transfers both the decision hardness and the optimal value of test cover\. ∎

## Appendix CDetails of the training\-free alignment score

##### Roadmap\.

The purpose of the alignment score is to select a subset of columns that exposes label\-relevant structure without fragmenting the data into cells that are too small to support reliable estimation or useful message passing\. The construction has four steps\. Given a column subsetSS, we

1. 1\.partition the training rows according to their values onSS;
2. 2\.attach to each resulting cell the simplest possible predictor, namely its empirical label distribution;
3. 3\.measure how strongly the partition fragments the training sample through an occupancy penalty; and
4. 4\.combine this penalty with the predictor’s loss on a held\-out validation set\.

Thus, adding columns creates a more expressive predictor, but also produces finer and potentially less well\-supported cells\. The score makes this trade\-off explicit\. We first define the cells, predictor, and occupancy penalty\. We then establish the statistical meaning of the penalty and the validation guarantee for the resulting score\. Finally, we describe the greedy search used to optimise it in practice\.

### C\.1From column subsets to cells

Let𝒳=valA\\mathcal\{X\}=\\mathrm\{val\}^\{A\}be the ambient row space over the non\-label attributesA=C∖\{Y\}A=C\\setminus\\\{Y\\\}, and let𝒴\\mathcal\{Y\}be the finite label alphabet\. We treat the data as an indexed sample

T=\(\(Xi,Yi\)\)i=1n\.T=\\bigl\(\(X\_\{i\},Y\_\{i\}\)\\bigr\)\_\{i=1\}^\{n\}\.Fix a split of the indices into disjoint training and validation setsItrI\_\{\\mathrm\{tr\}\}andIvalI\_\{\\mathrm\{val\}\}, with

ntr=\|Itr\|≥1,nval=\|Ival\|≥1\.n\_\{\\mathrm\{tr\}\}=\|I\_\{\\mathrm\{tr\}\}\|\\geq 1,\\qquad n\_\{\\mathrm\{val\}\}=\|I\_\{\\mathrm\{val\}\}\|\\geq 1\.The corresponding subsamples are denoted byTtrT\_\{\\mathrm\{tr\}\}andTvalT\_\{\\mathrm\{val\}\}\.

LetF⊆AF\\subseteq Abe the fixed set of columns eligible for selection\. Throughout this section,S⊆FS\\subseteq Fdenotes a candidate subset\.

The information exposed bySSabout a rowx∈𝒳x\\in\\mathcal\{X\}is its projectionx\|Sx\|\_\{S\}\. Rows that agree on this projection belong to the same*cell*\. More precisely, for every value tupleu∈valSu\\in\\mathrm\{val\}^\{S\}, define

BS,u=\{i∈Itr:Xi\|S=u\},NS,u=\|BS,u\|\.B\_\{S,u\}=\\bigl\\\{i\\in I\_\{\\mathrm\{tr\}\}:X\_\{i\}\|\_\{S\}=u\\bigr\\\},\\qquad N\_\{S,u\}=\|B\_\{S,u\}\|\.We index cells by value tuples rather than only by observed training rows\. Consequently, the countNS,uN\_\{S,u\}is defined even when no training row has projectionuu\. This will allow the predictor introduced below to be defined on all of𝒳\\mathcal\{X\}, including previously unseen rows\.

The nonempty setsBS,uB\_\{S,u\}form a partitionπS∈Π⁡\(Itr\)\\pi\_\{S\}\\in\\Pi\(I\_\{\\mathrm\{tr\}\}\)of the training indices:

i∼πSj⟺Xi\|S=Xj\|S\.i\\sim\_\{\\pi\_\{S\}\}j\\quad\\Longleftrightarrow\\quad X\_\{i\}\|\_\{S\}=X\_\{j\}\|\_\{S\}\.We writeπ′⪯π\\pi^\{\\prime\}\\preceq\\piwhenπ′\\pi^\{\\prime\}refinesπ\\pi, meaning that every block ofπ′\\pi^\{\\prime\}is contained in a block ofπ\\pi\.

### C\.2The block predictor

A column subsetSSinduces a predictor without fitting a parametric model\. On each occupied cell, the predictor simply returns the empirical label distribution of the training rows in that cell\. ForNS,u\>0N\_\{S,u\}\>0, define

p^S​\(y∣u\)=1NS,u​∑i∈Itr𝟏​\{Xi\|S=u,Yi=y\}\.\\hat\{p\}\_\{S\}\(y\\mid u\)=\\frac\{1\}\{N\_\{S,u\}\}\\sum\_\{i\\in I\_\{\\mathrm\{tr\}\}\}\\mathbf\{1\}\\\{X\_\{i\}\|\_\{S\}=u,\\ Y\_\{i\}=y\\\}\.For a cell that does not occur in the training data, these conditional frequencies are not identifiable\. We therefore use the training\-set marginal

p^0\(y\)=1ntr∑i∈Itr𝟏\{Yi=y\}\\hat\{p\}\_\{0\}\(y\)=\\frac\{1\}\{n\_\{\\mathrm\{tr\}\}\}\\sum\_\{i\\in I\_\{\\mathrm\{tr\}\}\}\\mathbf\{1\}\\\{Y\_\{i\}=y\\\}as a fixed fallback\.

The resulting*block predictor*is the function

h^S​\(x\)=\{p^S\(⋅∣x\|S\),NS,x\|S\>0,p^0,NS,x\|S=0\.\\hat\{h\}\_\{S\}\(x\)=\\begin\{cases\}\\hat\{p\}\_\{S\}\(\\,\\cdot\\mid x\|\_\{S\}\),&N\_\{S,x\|\_\{S\}\}\>0,\\\\\[2\.0pt\] \\hat\{p\}\_\{0\},&N\_\{S,x\|\_\{S\}\}=0\.\\end\{cases\}The predictor is therefore defined on the entire row space𝒳\\mathcal\{X\}, not only on the rows observed during training\. Moreover, conditional onTtrT\_\{\\mathrm\{tr\}\}, it is a fixed function: all its cell counts, label frequencies, and fallback probabilities are determined by the training sample\.

On occupied cells,p^S\(⋅∣u\)\\hat\{p\}\_\{S\}\(\\cdot\\mid u\)is the categorical maximum\-likelihood estimate\. When a hard prediction is required, we use

g^S​\(x\)=arg⁡maxy∈𝒴​h^S​\(x\)​\(y\),\\hat\{g\}\_\{S\}\(x\)=\\arg\\max\_\{y\\in\\mathcal\{Y\}\}\\hat\{h\}\_\{S\}\(x\)\(y\),with a fixed tie\-breaking rule\. Thus,h^S\\hat\{h\}\_\{S\}estimates a label distribution, whereasg^S\\hat\{g\}\_\{S\}is the00–11empirical risk minimiser among classifiers that are constant on the cells induced bySS\.

### C\.3The occupancy penalty

The block predictor becomes more expressive as cells are refined\. In particular, a sufficiently fine partition can place every training row in its own cell, at which point the predictor merely memorises the training labels\.

What matters, however, is not the number of cells that could exist, but how the observed training rows are distributed over the cells that actually occur\. We quantify this through the occupancy functional

Ω⁡\(Ttr,π\)=1ntr​∑B∈π\|B\|\.\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\)=\\frac\{1\}\{n\_\{\\mathrm\{tr\}\}\}\\sum\_\{B\\in\\pi\}\\sqrt\{\|B\|\}\.For the partition induced bySS, this becomes

Ω\(Ttr,πS\)=1ntr∑u:NS,u\>0NS,u=1ntr∑i∈Itr1NS,Xi\|S\.\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)=\\frac\{1\}\{n\_\{\\mathrm\{tr\}\}\}\\sum\_\{u:N\_\{S,u\}\>0\}\\sqrt\{N\_\{S,u\}\}=\\frac\{1\}\{n\_\{\\mathrm\{tr\}\}\}\\sum\_\{i\\in I\_\{\\mathrm\{tr\}\}\}\\frac\{1\}\{\\sqrt\{N\_\{S,X\_\{i\}\|\_\{S\}\}\}\}\.\(3\)The final expression gives a useful row\-wise interpretation: each training row is charged the inverse square root of the number of rows supporting its prediction\.

Accordingly,Ω\\Omegais best read as an*occupancy penalty*\. It is small when many rows share a few well\-populated cells, and large when the data is spread over many sparsely populated cells\. Since the block sizes always sum tontrn\_\{\\mathrm\{tr\}\}, we have

1ntr≤Ω⁡\(Ttr,πS\)≤1\.\\frac\{1\}\{\\sqrt\{n\_\{\\mathrm\{tr\}\}\}\}\\leq\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\\leq 1\.The two extremes illustrate the scale:

- •If all rows belong to one cell, thenΩ=1/ntr\\Omega=1/\\sqrt\{n\_\{\\mathrm\{tr\}\}\}\. Every prediction is supported by the entire training sample\.
- •If every cell is a singleton, thenΩ=1\\Omega=1\. This is the pure memorisation regime\.

#### C\.3\.1Adding columns increases fragmentation

The first important property ofΩ\\Omegais structural: exposing more columns can only refine the partition and therefore can only increase the penalty\.

###### Lemma 3\.

IfS⊆S′⊆FS\\subseteq S^\{\\prime\}\\subseteq F, then

πS′⪯πS\.\\pi\_\{S^\{\\prime\}\}\\preceq\\pi\_\{S\}\.

###### Proof\.

IfXi\|S′=Xj\|S′X\_\{i\}\|\_\{S^\{\\prime\}\}=X\_\{j\}\|\_\{S^\{\\prime\}\}, thenXi\|S=Xj\|SX\_\{i\}\|\_\{S\}=X\_\{j\}\|\_\{S\}becauseS⊆S′S\\subseteq S^\{\\prime\}\. Hence every block ofπS′\\pi\_\{S^\{\\prime\}\}is contained in a block ofπS\\pi\_\{S\}\. ∎

###### Lemma 4\.

Ifπ′⪯π\\pi^\{\\prime\}\\preceq\\pi, then

Ω⁡\(Ttr,π\)≤Ω⁡\(Ttr,π′\)\.\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\)\\leq\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi^\{\\prime\}\)\.

###### Proof\.

Every blockB∈πB\\in\\piis the disjoint union of the blocksB′∈π′B^\{\\prime\}\\in\\pi^\{\\prime\}that it contains\. Therefore,

\|B\|=∑B′∈π′B′⊆B\|B′\|\.\|B\|=\\sum\_\{\\begin\{subarray\}\{c\}B^\{\\prime\}\\in\\pi^\{\\prime\}\\\\ B^\{\\prime\}\\subseteq B\\end\{subarray\}\}\|B^\{\\prime\}\|\.By subadditivity of the square root,

\|B\|≤∑B′∈π′B′⊆B\|B′\|\.\\sqrt\{\|B\|\}\\leq\\sum\_\{\\begin\{subarray\}\{c\}B^\{\\prime\}\\in\\pi^\{\\prime\}\\\\ B^\{\\prime\}\\subseteq B\\end\{subarray\}\}\\sqrt\{\|B^\{\\prime\}\|\}\.Summing overB∈πB\\in\\piand dividing byntrn\_\{\\mathrm\{tr\}\}proves the claim\. ∎

###### Corollary 1\.

IfS⊆S′⊆FS\\subseteq S^\{\\prime\}\\subseteq F, then

Ω⁡\(Ttr,πS\)≤Ω⁡\(Ttr,πS′\)\.\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\\leq\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S^\{\\prime\}\}\)\.

Thus, an additional column may improve predictive fidelity, but it can never reduce the occupancy penalty\. This is precisely the tension that the alignment score will balance\.

#### C\.3\.2Why occupancy is statistically meaningful

The occupancy penalty is not merely a heuristic measure of fragmentation\. It also controls the estimation error of the corresponding class of cell\-constant classifiers\.

Let

𝒢S=\{g:𝒳→𝒴\|x\|S=x′\|S⇒g\(x\)=g\(x′\)\}\\mathcal\{G\}\_\{S\}=\\left\\\{g:\\mathcal\{X\}\\to\\mathcal\{Y\}\\;\\middle\|\\;x\|\_\{S\}=x^\{\\prime\}\|\_\{S\}\\Rightarrow g\(x\)=g\(x^\{\\prime\}\)\\right\\\}be the class of classifiers that are constant on the cells induced bySS\. Letg^S\\hat\{g\}\_\{S\}be an empirical risk minimiser over𝒢S\\mathcal\{G\}\_\{S\}onTtrT\_\{\\mathrm\{tr\}\}under00–11loss\. On every occupied cell, this is the majority\-label classifier\. The convention above fixes its value on unoccupied cells\.

Write

Risk\(g\)=Pr𝒟\[g\(X\)≠Y\],Risk∗=infgRisk\(g\),\\mathrm\{Risk\}\(g\)=\\Pr\_\{\\mathcal\{D\}\}\[g\(X\)\\neq Y\],\\qquad\\mathrm\{Risk\}^\{\*\}=\\inf\_\{g\}\\mathrm\{Risk\}\(g\),and

RiskS∗=infg∈𝒢SRisk⁡\(g\)\.\\mathrm\{Risk\}^\{\*\}\_\{S\}=\\inf\_\{g\\in\\mathcal\{G\}\_\{S\}\}\\mathrm\{Risk\}\(g\)\.
###### Lemma 5\.

FixS⊆FS\\subseteq Findependently ofTtrT\_\{\\mathrm\{tr\}\}\. Suppose that𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}and thatTtrT\_\{\\mathrm\{tr\}\}consists ofntrn\_\{\\mathrm\{tr\}\}independent draws from𝒟\\mathcal\{D\}\. For everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\deltaoverTtrT\_\{\\mathrm\{tr\}\},

Risk⁡\(g^S\)−Risk∗≤\(RiskS∗−Risk∗\)⏟approximation error\+Ω⁡\(Ttr,πS\)⏟estimation error\+4​ln⁡\(4/δ\)2​ntr\.\\mathrm\{Risk\}\(\\hat\{g\}\_\{S\}\)\-\\mathrm\{Risk\}^\{\*\}\\leq\\underbrace\{\\bigl\(\\mathrm\{Risk\}^\{\*\}\_\{S\}\-\\mathrm\{Risk\}^\{\*\}\\bigr\)\}\_\{\\text\{approximation error\}\}\+\\underbrace\{\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\}\_\{\\text\{estimation error\}\}\+4\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\_\{\\mathrm\{tr\}\}\}\}\.\(∗\\ast\)

###### Proof\.

Writen=ntrn=n\_\{\\mathrm\{tr\}\}\. Encode classifiers and labels by signs:

g~=2​g−1∈\{−1,\+1\},Y~i=2​Yi−1\.\\tilde\{g\}=2g\-1\\in\\\{\-1,\+1\\\},\\qquad\\tilde\{Y\}\_\{i\}=2Y\_\{i\}\-1\.Then

𝟏\{g\(Xi\)≠Yi\}=12\(1−Y~ig~\(Xi\)\)\.\\mathbf\{1\}\\\{g\(X\_\{i\}\)\\neq Y\_\{i\}\\\}=\\frac\{1\}\{2\}\\bigl\(1\-\\tilde\{Y\}\_\{i\}\\tilde\{g\}\(X\_\{i\}\)\\bigr\)\.\(4\)Letσ1,…,σn\\sigma\_\{1\},\\ldots,\\sigma\_\{n\}be independent Rademacher signs and let

𝒢~S=\{g~:g∈𝒢S\}\.\\widetilde\{\\mathcal\{G\}\}\_\{S\}=\\\{\\tilde\{g\}:g\\in\\mathcal\{G\}\_\{S\}\\\}\.
Every function in𝒢~S\\widetilde\{\\mathcal\{G\}\}\_\{S\}is constant on each block ofπS\\pi\_\{S\}\. Its values on the training sample are therefore determined by one freely chosen sign per block\. Hence

ℜ^​\(𝒢~S\)\\displaystyle\\widehat\{\\mathfrak\{R\}\}\(\\widetilde\{\\mathcal\{G\}\}\_\{S\}\)=1n​𝔼σ​\[supg~∈𝒢~S∑i=1nσi​g~​\(Xi\)\]\\displaystyle=\\frac\{1\}\{n\}\\mathbb\{E\}\_\{\\sigma\}\\left\[\\sup\_\{\\tilde\{g\}\\in\\widetilde\{\\mathcal\{G\}\}\_\{S\}\}\\sum\_\{i=1\}^\{n\}\\sigma\_\{i\}\\tilde\{g\}\(X\_\{i\}\)\\right\]=1n​∑B∈πS𝔼σ​\|∑i∈Bσi\|\.\\displaystyle=\\frac\{1\}\{n\}\\sum\_\{B\\in\\pi\_\{S\}\}\\mathbb\{E\}\_\{\\sigma\}\\left\|\\sum\_\{i\\in B\}\\sigma\_\{i\}\\right\|\.By Cauchy–Schwarz applied to the random variables\|∑i∈Bσi\|\\lvert\\sum\_\{i\\in B\}\\sigma\_\{i\}\\rvertand11, together with

𝔼σ​\(∑i∈Bσi\)2=\|B\|,\\mathbb\{E\}\_\{\\sigma\}\\left\(\\sum\_\{i\\in B\}\\sigma\_\{i\}\\right\)^\{2\}=\|B\|,we obtain

𝔼σ​\|∑i∈Bσi\|≤\|B\|\.\\mathbb\{E\}\_\{\\sigma\}\\left\|\\sum\_\{i\\in B\}\\sigma\_\{i\}\\right\|\\leq\\sqrt\{\|B\|\}\.Consequently,

ℜ^​\(𝒢~S\)≤1n​∑B∈πS\|B\|=Ω⁡\(Ttr,πS\)\.\\widehat\{\\mathfrak\{R\}\}\(\\widetilde\{\\mathcal\{G\}\}\_\{S\}\)\\leq\\frac\{1\}\{n\}\\sum\_\{B\\in\\pi\_\{S\}\}\\sqrt\{\|B\|\}=\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\.
Let

ℒS=\{\(x,y\)↦𝟏\{g\(x\)≠y\}:g∈𝒢S\}\.\\mathcal\{L\}\_\{S\}=\\left\\\{\(x,y\)\\mapsto\\mathbf\{1\}\\\{g\(x\)\\neq y\\\}:g\\in\\mathcal\{G\}\_\{S\}\\right\\\}\.By \([4](https://arxiv.org/html/2608.11431#A3.E4)\), the additive constant contributes12​n​𝔼σ​∑iσi=0\\frac\{1\}\{2n\}\\mathbb\{E\}\_\{\\sigma\}\\sum\_\{i\}\\sigma\_\{i\}=0, while the multiplicative factor1/21/2remains\. Moreover, the productsσi​Y~i\\sigma\_\{i\}\\tilde\{Y\}\_\{i\}are again independent Rademacher signs conditional on the sample\. Therefore,

ℜ^​\(ℒS\)=12​ℜ^​\(𝒢~S\)≤12​Ω​\(Ttr,πS\)\.\\widehat\{\\mathfrak\{R\}\}\(\\mathcal\{L\}\_\{S\}\)=\\frac\{1\}\{2\}\\widehat\{\\mathfrak\{R\}\}\(\\widetilde\{\\mathcal\{G\}\}\_\{S\}\)\\leq\\frac\{1\}\{2\}\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\.
Apply the standard one\-sided empirical Rademacher bound for\[0,1\]\[0,1\]\-valued loss classes with failure probabilityδ/2\\delta/2\. With probability at least1−δ/21\-\\delta/2, simultaneously for everyg∈𝒢Sg\\in\\mathcal\{G\}\_\{S\},

Risk⁡\(g\)\\displaystyle\\mathrm\{Risk\}\(g\)≤Risk^tr​\(g\)\+2​ℜ^​\(ℒS\)\+3​ln⁡\(4/δ\)2​n\\displaystyle\\leq\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{tr\}\}\(g\)\+2\\widehat\{\\mathfrak\{R\}\}\(\\mathcal\{L\}\_\{S\}\)\+3\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\}\}≤Risk^tr​\(g\)\+Ω⁡\(Ttr,πS\)\+3​ln⁡\(4/δ\)2​n\.\\displaystyle\\leq\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{tr\}\}\(g\)\+\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\+3\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\}\}\.Forε\>0\\varepsilon\>0, choose a fixedε\\varepsilon\-minimisergS,ε∗∈𝒢Sg^\{\*\}\_\{S,\\varepsilon\}\\in\\mathcal\{G\}\_\{S\}satisfying

Risk⁡\(gS,ε∗\)≤RiskS∗\+ε\.\\mathrm\{Risk\}\(g^\{\*\}\_\{S,\\varepsilon\}\)\\leq\\mathrm\{Risk\}^\{\*\}\_\{S\}\+\\varepsilon\.Since this comparator is fixed independently ofTtrT\_\{\\mathrm\{tr\}\}, the one\-sided Hoeffding inequality, also with failure probabilityδ/2\\delta/2, gives

Risk^tr​\(gS,ε∗\)≤Risk⁡\(gS,ε∗\)\+ln⁡\(2/δ\)2​n\.\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{tr\}\}\(g^\{\*\}\_\{S,\\varepsilon\}\)\\leq\\mathrm\{Risk\}\(g^\{\*\}\_\{S,\\varepsilon\}\)\+\\sqrt\{\\frac\{\\ln\(2/\\delta\)\}\{2n\}\}\.By a union bound, both displayed inequalities hold with probability at least1−δ1\-\\delta\. Put

c=3​ln⁡\(4/δ\)2​n,b=ln⁡\(2/δ\)2​n,Ω=Ω⁡\(Ttr,πS\)\.c=3\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\}\},\\qquad b=\\sqrt\{\\frac\{\\ln\(2/\\delta\)\}\{2n\}\},\\qquad\\Omega=\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\.On the event above,

Risk⁡\(g^S\)\\displaystyle\\mathrm\{Risk\}\(\\hat\{g\}\_\{S\}\)≤Risk^tr​\(g^S\)\+Ω\+c\\displaystyle\\leq\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{tr\}\}\(\\hat\{g\}\_\{S\}\)\+\\Omega\+c≤Risk^tr​\(gS,ε∗\)\+Ω\+c\\displaystyle\\leq\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{tr\}\}\(g^\{\*\}\_\{S,\\varepsilon\}\)\+\\Omega\+c≤RiskS∗\+ε\+Ω\+c\+b\\displaystyle\\leq\\mathrm\{Risk\}^\{\*\}\_\{S\}\+\\varepsilon\+\\Omega\+c\+b≤RiskS∗\+ε\+Ω\+4​ln⁡\(4/δ\)2​n\.\\displaystyle\\leq\\mathrm\{Risk\}^\{\*\}\_\{S\}\+\\varepsilon\+\\Omega\+4\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\}\}\.The second inequality uses the empirical optimality ofg^S\\hat\{g\}\_\{S\}\. SubtractingRisk∗\\mathrm\{Risk\}^\{\*\}and lettingε↓0\\varepsilon\\downarrow 0gives \([∗‣5](https://arxiv.org/html/2608.11431#A3.Ex23)\)\. ∎

The bound separates two effects\. The approximation term measures what is lost by forcing rows in the same cell to receive the same label\. The occupancy term measures the estimation cost of learning one prediction per occupied cell\. Thus, finer partitions can reduce approximation error, but they necessarily increase the quantity controlling estimation error\. BecauseΩ\\Omegacan be as large as11, the bound may be vacuous in the singleton\-cell memorisation regime\. This is precisely the regime that the occupancy penalty is designed to detect\.

The randomness in[Lemma5](https://arxiv.org/html/2608.11431#Thmlemma5)is overTtrT\_\{\\mathrm\{tr\}\}: the lemma explains why the occupancy of the training sample is worth penalising\. The validation result below instead conditions onTtrT\_\{\\mathrm\{tr\}\}and randomises overTvalT\_\{\\mathrm\{val\}\}: it certifies the selection made using that penalty\.

### C\.4The alignment score

The occupancy penalty alone would always favour the coarsest possible partition\. We therefore balance it against predictive fidelity on the validation split\.

Letℓ\\ellbe a loss taking values in\[0,L\]\[0,L\]\. Define

Risk^val​\(h^S\)=1nval​∑i∈Ivalℓ⁡\(h^S​\(Xi\),Yi\)\.\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{S\}\)=\\frac\{1\}\{n\_\{\\mathrm\{val\}\}\}\\sum\_\{i\\in I\_\{\\mathrm\{val\}\}\}\\ell\\bigl\(\\hat\{h\}\_\{S\}\(X\_\{i\}\),Y\_\{i\}\\bigr\)\.The training\-free alignment score is

𝒥⁡\(πS\)=Risk^val​\(h^S\)\+λ​Ω​\(Ttr,πS\),λ≥0\.\\mathcal\{J\}\(\\pi\_\{S\}\)=\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{S\}\)\+\\lambda\\,\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\),\\qquad\\lambda\\geq 0\.\(5\)
The two terms have deliberately different roles:

- •TtrT\_\{\\mathrm\{tr\}\}determines the cells, the block predictor, and the occupancy penalty;
- •TvalT\_\{\\mathrm\{val\}\}measures how well the resulting predictor generalises beyond those training cells\.

The parameterλ\\lambdastates how much validation loss we are willing to trade for a coarser and better\-supported structure\.

### C\.5Validation guarantee

Because every predictorh^S\\hat\{h\}\_\{S\}is fixed after conditioning onTtrT\_\{\\mathrm\{tr\}\}, standard concentration on the independent validation set gives a uniform guarantee over all candidate subsets\.

###### Proposition 1\(Uniform validation guarantee\)\.

Fixδ∈\(0,1\)\\delta\\in\(0,1\)and condition onTtrT\_\{\\mathrm\{tr\}\}\. Assume that

1. \(A1\)the validation rows are independent draws from a distribution𝒟val\\mathcal\{D\}\_\{\\mathrm\{val\}\}, independent ofTtrT\_\{\\mathrm\{tr\}\}, and Risk⁡\(h\)=𝔼𝒟val​\[ℓ⁡\(h⁡\(X\),Y\)\];\\mathrm\{Risk\}\(h\)=\\mathbb\{E\}\_\{\\mathcal\{D\}\_\{\\mathrm\{val\}\}\}\[\\ell\(h\(X\),Y\)\];
2. \(A2\)the lossℓ\\elltakes values in\[0,L\]\[0,L\]; and
3. \(A3\)the candidate setF⊆AF\\subseteq Ais fixed independently ofTvalT\_\{\\mathrm\{val\}\}\.

Define

εL=L​\|F\|​ln⁡2\+ln⁡\(2/δ\)2​nval\.\\varepsilon\_\{L\}=L\\sqrt\{\\frac\{\|F\|\\ln 2\+\\ln\(2/\\delta\)\}\{2n\_\{\\mathrm\{val\}\}\}\}\.Then, with probability at least1−δ1\-\\deltaoverTvalT\_\{\\mathrm\{val\}\}, every minimiser

S⋆∈arg⁡minS⊆F⁡𝒥⁡\(πS\)S^\{\\star\}\\in\\arg\\min\_\{S\\subseteq F\}\\mathcal\{J\}\(\\pi\_\{S\}\)satisfies

Risk⁡\(h^S⋆\)\+λ​Ω​\(Ttr,πS⋆\)≤minS⊆F⁡\{Risk⁡\(h^S\)\+λ​Ω​\(Ttr,πS\)\}\+2​εL\.\\displaystyle\\mathrm\{Risk\}\(\\hat\{h\}\_\{S^\{\\star\}\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S^\{\\star\}\}\)\\leq\\min\_\{S\\subseteq F\}\\Bigl\\\{\\mathrm\{Risk\}\(\\hat\{h\}\_\{S\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\\Bigr\\\}\+2\\varepsilon\_\{L\}\.\(6\)In particular,

Risk⁡\(h^S⋆\)≤minS⊆F⁡\{Risk⁡\(h^S\)\+λ​Ω​\(Ttr,πS\)\}\+2​εL\.\\mathrm\{Risk\}\(\\hat\{h\}\_\{S^\{\\star\}\}\)\\leq\\min\_\{S\\subseteq F\}\\Bigl\\\{\\mathrm\{Risk\}\(\\hat\{h\}\_\{S\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\\Bigr\\\}\+2\\varepsilon\_\{L\}\.

###### Proof\.

Condition onTtrT\_\{\\mathrm\{tr\}\}\. For everyS⊆FS\\subseteq F, the functionh^S\\hat\{h\}\_\{S\}is then fixed on all of𝒳\\mathcal\{X\}: its counts, empirical label distributions, and fallback distribution are determined entirely by the training sample\.

BecauseTvalT\_\{\\mathrm\{val\}\}is independent ofTtrT\_\{\\mathrm\{tr\}\}, the random variables

ℓ⁡\(h^S​\(Xi\),Yi\),i∈Ival,\\ell\(\\hat\{h\}\_\{S\}\(X\_\{i\}\),Y\_\{i\}\),\\qquad i\\in I\_\{\\mathrm\{val\}\},are independent, take values in\[0,L\]\[0,L\], and have meanRisk⁡\(h^S\)\\mathrm\{Risk\}\(\\hat\{h\}\_\{S\}\)\. Hoeffding’s inequality therefore gives

Pr\[\|Risk^val\(h^S\)−Risk\(h^S\)\|\>t\]≤2exp\(−2​nval​t2L2\)\.\\Pr\\left\[\\left\|\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{S\}\)\-\\mathrm\{Risk\}\(\\hat\{h\}\_\{S\}\)\\right\|\>t\\right\]\\leq 2\\exp\\left\(\-\\frac\{2n\_\{\\mathrm\{val\}\}t^\{2\}\}\{L^\{2\}\}\\right\)\.
By assumption \(A3\), the family

\{h^S:S⊆F\}\\\{\\hat\{h\}\_\{S\}:S\\subseteq F\\\}is fixed before the validation set is observed and contains at most2\|F\|2^\{\|F\|\}predictors\. A union bound with total failure probabilityδ\\deltatherefore yieldst=εLt=\\varepsilon\_\{L\}\. Hence, with probability at least1−δ1\-\\delta, simultaneously for allS⊆FS\\subseteq F,

\|Risk^val​\(h^S\)−Risk⁡\(h^S\)\|≤εL\.\\left\|\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{S\}\)\-\\mathrm\{Risk\}\(\\hat\{h\}\_\{S\}\)\\right\|\\leq\\varepsilon\_\{L\}\.\(7\)
On this event, for everyS⊆FS\\subseteq F, the optimality ofS⋆S^\{\\star\}for𝒥\\mathcal\{J\}and two applications of \([7](https://arxiv.org/html/2608.11431#A3.E7)\) give

Risk⁡\(h^S⋆\)\+λ​Ω​\(Ttr,πS⋆\)\\displaystyle\\mathrm\{Risk\}\(\\hat\{h\}\_\{S^\{\\star\}\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S^\{\\star\}\}\)≤Risk^val​\(h^S⋆\)\+λ​Ω​\(Ttr,πS⋆\)\+εL\\displaystyle\\leq\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{S^\{\\star\}\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S^\{\\star\}\}\)\+\\varepsilon\_\{L\}≤Risk^val​\(h^S\)\+λ​Ω​\(Ttr,πS\)\+εL\\displaystyle\\leq\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{S\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\+\\varepsilon\_\{L\}≤Risk⁡\(h^S\)\+λ​Ω​\(Ttr,πS\)\+2​εL\.\\displaystyle\\leq\\mathrm\{Risk\}\(\\hat\{h\}\_\{S\}\)\+\\lambda\\Omega\(T\_\{\\mathrm\{tr\}\},\\pi\_\{S\}\)\+2\\varepsilon\_\{L\}\.Minimising the right\-hand side overS⊆FS\\subseteq Fproves \([6](https://arxiv.org/html/2608.11431#A3.E6)\)\. Dropping the nonnegative penalty on the left gives the final statement\. ∎

Assumption \(A1\) holds for a uniformly random train–validation split\. For a time\-based or grouped split, the guarantee should instead be read relative to the validation distribution that is actually sampled\. If rows within a validation group are dependent, Hoeffding’s inequality must be replaced by an appropriate block\-wise concentration inequality\.

### C\.6How to read the guarantee

##### The comparator is penalised risk\.

Forλ\>0\\lambda\>0,[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)does not claim thatS⋆S^\{\\star\}is near\-optimal for prediction risk alone\. It says thatS⋆S^\{\\star\}is near\-optimal for the trade\-off declared by𝒥\\mathcal\{J\}\. A subset with slightly larger prediction risk may therefore be preferred when it induces substantially better\-supported cells\. Whenλ=0\\lambda=0, the penalty disappears and the result reduces to the classical held\-out model\-selection bound\.

##### Why use a positive penalty?

There are two reasons to chooseλ\>0\\lambda\>0\.

First, the validation guarantee conditions on one realised training sample\. A partition consisting largely of singleton cells can behave well for that particular draw while changing sharply when the training sample changes\.[Lemma5](https://arxiv.org/html/2608.11431#Thmlemma5)shows that occupancy is precisely the quantity controlling this sensitivity\.

Second,S⋆S^\{\\star\}is not selected only to make predictions\. It is used to constructγincS⋆\\gamma\_\{\\mathrm\{inc\}\}^\{S^\{\\star\}\}, in which the cells determine shared neighbourhoods\. WhenΩ\\Omegais close to11, most row nodes have essentially unique neighbourhoods, leaving message passing with little shared structure to aggregate\. The score is therefore a*structural selector*, not merely a risk estimator\.

##### Why is occupancy measured on the training set?

The block predictor is fitted fromTtrT\_\{\\mathrm\{tr\}\}, so its estimation error is governed by the occupancy of the cells inTtrT\_\{\\mathrm\{tr\}\}\. MeasuringΩ\\OmegaonTvalT\_\{\\mathrm\{val\}\}would charge the score for rows that were never used to estimatep^S\(⋅∣u\)\\hat\{p\}\_\{S\}\(\\cdot\\mid u\), while failing to penalise training\-time memorisation directly\.

UsingTtrT\_\{\\mathrm\{tr\}\}also makes both the predictor and the penalty fixed after conditioning on the training sample\. This conditional viewpoint is what the proof of[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)requires\. It does not require the predictor and penalty to be unconditionally independent; indeed, both are functions ofTtrT\_\{\\mathrm\{tr\}\}\.

##### What does the guarantee say about greedy search?

The union bound in[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)ranges over the complete lattice\{S:S⊆F\}\\\{S:S\\subseteq F\\\}\. Consequently, the uniform deviation event also covers a subset chosen adaptively by inspecting validation scores\.

In particular, ifS~\\tilde\{S\}is the subset returned by[Algorithm1](https://arxiv.org/html/2608.11431#alg1), then

\|Risk^val​\(h^S~\)−Risk⁡\(h^S~\)\|≤εL\.\\left\|\\widehat\{\\mathrm\{Risk\}\}\_\{\\mathrm\{val\}\}\(\\hat\{h\}\_\{\\tilde\{S\}\}\)\-\\mathrm\{Risk\}\(\\hat\{h\}\_\{\\tilde\{S\}\}\)\\right\|\\leq\\varepsilon\_\{L\}\.The deviation for one returned candidate isεL\\varepsilon\_\{L\}; the factor2​εL2\\varepsilon\_\{L\}in[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)arises only when two candidates are compared\.

More generally, suppose thatS~\\tilde\{S\}isη\\eta\-suboptimal for the empirical score:

𝒥⁡\(πS~\)≤minS⊆F⁡𝒥⁡\(πS\)\+η\.\\mathcal\{J\}\(\\pi\_\{\\tilde\{S\}\}\)\\leq\\min\_\{S\\subseteq F\}\\mathcal\{J\}\(\\pi\_\{S\}\)\+\\eta\.Then the conclusion of[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)holds withη\+2​εL\\eta\+2\\varepsilon\_\{L\}in place of2​εL2\\varepsilon\_\{L\}\. The validation guarantee therefore survives approximate optimisation\. What it does not provide is a bound onη\\eta: although the occupancy term is monotone, the validation\-risk term is not, and greedy search may stop at a local minimum\.

### C\.7Greedy optimisation

We provide a bit more background on[Algorithm1](https://arxiv.org/html/2608.11431#alg1)\. As mentioned, exact minimisation of \([1](https://arxiv.org/html/2608.11431#S2.E1)\) is generally infeasible\. The search space contains2\|F\|2^\{\|F\|\}column subsets, and the underlying separation problem is NP\-complete\. We therefore use the greedy local search in

##### Search strategy\.

The algorithm maintains a current subsetSSand considers all subsets that differ fromSSby one column\.

Forward selection starts fromS=∅S=\\emptysetand considers additionsS∪\{c\}S\\cup\\\{c\\\}\. Backward elimination starts fromS=FS=Fand considers deletionsS∖\{c\}S\\setminus\\\{c\\\}\. At every iteration, the algorithm evaluates𝒥\\mathcal\{J\}on all one\-column neighbours and selects the best one\. The move is accepted only when it improves the current score by more than a toleranceτ\\tau\. Otherwise, the search terminates\.

The algorithm returns the surviving subsetS⋆S^\{\\star\}, together with the block model already computed for it\. This block model is then passed to the constructor asγincS⋆\\gamma\_\{\\mathrm\{inc\}\}^\{S^\{\\star\}\}\.

##### Choosing the search direction\.

The two directions traverse the refinement lattice in opposite ways\. Forward selection starts from the coarsest partition: it has the smallest possible occupancy penalty but is also the least expressive\. Backward elimination starts from the finest available partition: it is the most expressive but pays the largest occupancy penalty\. The validation\-risk term is not monotone, so the two directions may reach different local minima\.

Forward selection is typically cheaper\. It often terminates after only a few accepted additions and never needs to construct the finest partition\. It is therefore preferable when only a small number of columns are expected to matter\.

Backward elimination is more robust to interactions between attributes\. A column that is uninformative in isolation but useful together with another column is present at the start and is not rejected before that interaction can be evaluated\. Backward search also tends to remove high\-cardinality columns early, since such columns strongly increaseΩ\\Omegaand often fragment the cells on which the block predictor relies\.

##### Choosing the tolerance\.

The toleranceτ\\tauprevents the search from accepting improvements that are indistinguishable from validation noise\.[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)supplies the natural scale:

εL=O⁡\(L​\|F\|\+log⁡\(1/δ\)nval\)\.\\varepsilon\_\{L\}=O\\left\(L\\sqrt\{\\frac\{\|F\|\+\\log\(1/\\delta\)\}\{n\_\{\\mathrm\{val\}\}\}\}\\right\)\.A single candidate’s validation risk is accurate toεL\\varepsilon\_\{L\}, while the uncertainty in a pairwise comparison can be as large as2​εL2\\varepsilon\_\{L\}\. Choosingτ\\tauon this order prevents the search from pursuing sampling fluctuations\. Settingτ=0\\tau=0recovers ordinary greedy descent\.

##### Computational cost\.

For the𝒥\\mathcal\{J\}score, evaluation one candidate requires no model fitting\. It consists of two passes through the data:

1. 1\.one hash group\-by overTtrT\_\{\\mathrm\{tr\}\}to constructπS\\pi\_\{S\}, accumulate per\-cell label counts, and computep^S\\hat\{p\}\_\{S\},p^0\\hat\{p\}\_\{0\}, andΩ\\Omega;
2. 2\.one pass overTvalT\_\{\\mathrm\{val\}\}to accumulate the validation loss\.

Each score evaluation therefore requires

O⁡\(ntr\+nval\)O\(n\_\{\\mathrm\{tr\}\}\+n\_\{\\mathrm\{val\}\}\)hash operations\. At a subset of sizekk, backward elimination evaluateskkneighbours, whereas forward selection evaluates\|F\|−k\|F\|\-k\. A complete run uses at mostO⁡\(\|F\|2\)O\(\|F\|^\{2\}\)score evaluations and hence

O⁡\(\|F\|2​\(ntr\+nval\)\)O\\bigl\(\|F\|^\{2\}\(n\_\{\\mathrm\{tr\}\}\+n\_\{\\mathrm\{val\}\}\)\\bigr\)work in the worst case\. In practice, the cost is usually lower because the search terminates as soon as no one\-column move improves the score by more thanτ\\tau\.

##### Summary\.

The complete procedure implements a transparent structural trade\-off\. Adding columns may improve validation fidelity by distinguishing more row types, but it also creates smaller and less\-supported cells\. The validation loss measures the first effect, the occupancy penalty measures the second, and𝒥\\mathcal\{J\}selects the balance between them\. The two guarantees justify these roles separately:[Lemma5](https://arxiv.org/html/2608.11431#Thmlemma5)explains why occupancy controls estimation, while[Proposition1](https://arxiv.org/html/2608.11431#Thmproposition1)shows that held\-out selection is uniformly reliable over the candidate subsets\.

## Appendix DExtended experimental results

### D\.1Controlled tasks

#### D\.1\.1Column recovery under the alignment objective \(RQ1\)

RQ1 asks whether minimizing𝒥\\mathcal\{J\}selects the columns that generate the task and rejects irrelevant ones\. We answer it at two levels: whether the*global minimizer*of𝒥\\mathcal\{J\}is the true relevant set, and whether the*greedy procedure*we run reaches that minimizer\. The second matters only because it shows that, despite being greedy, the algorithm performs\.

### D\.2Data\-generating process

As base data we use the Census/Adult dataset\[adult\-dataset\], whose88categorical columns form the core of the column universeCC\. A task is defined by a ground\-truth relevant setS∘⊆CS^\{\\circ\}\\subseteq C, and a labelyygenerated fromS∘S^\{\\circ\}\. We constrain the base rate toP⁡\(y=1\)∈\[0\.3,0\.7\]P\(y\{=\}1\)\\in\[0\.3,0\.7\]at generation time to avoid degenerate targets\.

The five mechanism families vary in howyydepends onS∘S^\{\\circ\}, from row\-local to genuinely relational:

- •Single\-value\.yyis set by one value of one column:yi=𝟙\[Ti\[ca\]=v\]y\_\{i\}=\\mathbbm\{1\}\[T\_\{i\}\[c\_\{a\}\]\{=\}v\], withS∘=\{ca\}S^\{\\circ\}=\\\{c\_\{a\}\\\}\.
- •Conjunction\.yyrequires two column values jointly:yi=𝟙\[Ti\[ca\]=va∧Ti\[cb\]=vb\]y\_\{i\}=\\mathbbm\{1\}\[T\_\{i\}\[c\_\{a\}\]\{=\}v\_\{a\}\\wedge T\_\{i\}\[c\_\{b\}\]\{=\}v\_\{b\}\],S∘=\{ca,cb\}S^\{\\circ\}=\\\{c\_\{a\},c\_\{b\}\\\}, with each column individually informative but neither sufficient\.
- •Interaction \(XOR\)\.yyis the exclusive\-or of two binarized columns, chosen so that neither column is informative aboutyyon its own while the pair determines it\.S∘=\{ca,cb\}S^\{\\circ\}=\\\{c\_\{a\},c\_\{b\}\\\}\. We include this family to stress\-test greedy selection\.
- •Count\.yydepends on how often a row’s key value recurs:yi=𝟙\[multiplicity ofTi\[k\]≥τ\]y\_\{i\}=\\mathbb\{1\}\[\\,\\text\{multiplicity of \}T\_\{i\}\[k\]\\geq\\tau\\,\],S∘=\{k\}S^\{\\circ\}=\\\{k\\\}\. No row\-local feature onkkexpressesyy\.
- •Duplicate\.yymarks rows whose value in a particular column appears more than once:yi=𝟙​\[value​Ti​\[d\]​is not unique\]y\_\{i\}=\\mathbbm\{1\}\[\\,\\text\{value \}T\_\{i\}\[d\]\\text\{ is not unique\}\\,\],S∘=\{d\}S^\{\\circ\}=\\\{d\\\}\.

##### Noise\.

We flip each label independently with probabilityη∈\{0\.0,0\.1,0\.2\}\\eta\\in\\\{0\.0,0\.1,0\.2\\\}to test the robustness and performance of the model against noisy targets\.

### D\.3Metrics

LetS^\\hat\{S\}be the selected subset\.*Recall*Rec=\|S^∩S∘\|/\|S∘\|\\mathrm\{Rec\}=\|\\hat\{S\}\\cap S^\{\\circ\}\|/\|S^\{\\circ\}\|measure how much of the true set is kept;*Exact*=𝟙\[S^=S∘\]=\\mathbbm\{1\}\[\\hat\{S\}=S^\{\\circ\}\]is their all\-or\-nothing combination\. We also separate objective failure from procedure failure: objective failure is when the minimum of𝒥\\mathcal\{J\}does not correspond to the partition induced by the ground\-truth relevant columns, and procedure failure is when the point reached by the greedy procedure is non\-optimal\.

### D\.4Protocol

For each \(family,η\\eta\) we drawN=10N=10seeds, resampling the rows, planted columns, and label noise each time, and score the selected subset against the knownS∘S^\{\\circ\}\.

### D\.5Extended results

Beyond the results in Table[1](https://arxiv.org/html/2608.11431#S5.T1), we report the full experimental results for the differentAutoGrablemechanisms and for the inclusion of progressive noise in the tasks\. We analyse each axis separately\.

##### Effect of the regularisation strengthλ\\lambda\.

Figure[3](https://arxiv.org/html/2608.11431#A4.F3)reports performance as a function ofλ\\lambdafor every combination of the twoAutoGrableaxes—encoding \(*values*,*frequencies*\) and direction \(*forward*,*backward*\)—on the clean tasks \(noise=0=0\)\. Solid curves show the mean over the tasks in each category \(*row\-local*,*extension\-sensitive*\); faint curves show the individual tasks\. The location of the optimalλ\\lambdashifts across panels and differs between the two task categories, showing that the effect ofλ\\lambdais not independent of the chosen mechanism\.

Figure 3:Performance \(Exact recovery\) versus regularisation strengthλ\\lambdafor each encoding×\\,\\times\\,direction setting, on the clean tasks \(noise=0\{\}=0\)\. Solid lines are per\-category means over tasks; faint lines are individual tasks\. Axes are shared across panels\. Best viewed in color\.
##### Robustness to progressive noise\.

Figure[4](https://arxiv.org/html/2608.11431#A4.F4)reports performance as the amount of added noise increases, shown separately for each task category \(Figures[4\(a\)](https://arxiv.org/html/2608.11431#A4.F4.sf1)and[4\(b\)](https://arxiv.org/html/2608.11431#A4.F4.sf2)\)\. Within each panel—again one per encoding×\\,\\times\\,direction setting—each curve corresponds to a value ofλ\\lambda\. This lets us read off both the overall degradation under noise and whether the bestλ\\lambdadepends on the noise level: crossing curves indicate that the ranking ofλ\\lambdachanges as noise grows\.

\(a\)*Row\-local*tasks\.\(b\)*Extension\-sensitive*tasks\.
Figure 4:Performance \(Exact recovery\) under progressively stronger added noise, per task category\. Each panel corresponds to an encoding×\\,\\times\\,direction setting; each curve corresponds to a value ofλ\\lambda\(light to dark\)\. Best viewed in color\.

### D\.6Real transactional, relational and i\.i\.d tasks

#### D\.6\.1Training details

##### GraphSAGE architecture and hyperparameters

Throughout the transactional, relational and i\.i\.d\. tabular tasks, the predictor is kept fixed: for each dataset, a single configuration is instantiated once and reused unchanged across every task family and every graph construction evaluated on that dataset\. Table[5](https://arxiv.org/html/2608.11431#A4.T5)reports the architecture and configuration used for the transactional \(fraud\) and tabular i\.i\.d\. \(TabArena\) setups, which share the sameHeteroSAGEimplementation\. For RelBench tasks we use RelBench’s own referenceHeteroGraphSAGEimplementation and hyperparameters, reported separately in Table[6](https://arxiv.org/html/2608.11431#A4.T6), since its encoder and message\-passing modules differ from ours and are not directly comparable field\-by\-field\.

Hyperparameters are not selected per construction: the validation set is used only for early stopping, checkpointing on the epoch with the best validation score, under a fixed architecture and fixed hyperparameters, not for a hyperparameter search re\-run per construction\. No construction receives more tuning than another\.

Table 5:GraphSAGE \(HeteroSAGE\) hyperparameters, Transactional \(fraud\) vs\. Tabular IID \(TabArena\) setups\. Both use the same architecture \(NodeEncoder\+HeteroSAGE\+MLPHead\)\.Table 6:GraphSAGE hyperparameters, Relational \(RelBench\) setup\. Uses RelBench’sHeteroEncoder\+HeteroTemporalEncoder\+HeteroGraphSAGE\+ single\-layerMLPhead

#### D\.6\.2Transactional fraud detection

From the*FDB: Fraud Dataset Benchmark*we use all available real datasets with at least 3 categorical attributes\. This rules out 5 of the 9 available datasets, from which 4 have two or less categorical variables \(and hence the graph\-construction\-via\-selection effect is limited\) or are simulated \(particularly “Simulated Credit Card Transactions generated using Sparkov” \(sparknov\)\)\. Table[7](https://arxiv.org/html/2608.11431#A4.T7)show the validation and test results of the fixed graph constructions and the differentAutoGrableconfigurations\.

Table 7:AutoGrableperformance \(AUC\) comparison across encoding/direction/λ\\lambdaconfigurations on transactional \(FDB\) datasets\. Results averaged overN=15N\{=\}15seeds\. We note thatfraudecomis a particularly challenging task, where no configuration \(nor other methods reported in the official benchmark leader board\) beats near\-random performance\.
#### D\.6\.3Tabular datasets results

Table[8](https://arxiv.org/html/2608.11431#A4.T8)reports the performance ofγtriv\\gamma\_\{\\mathrm\{triv\}\},γinc\\gamma\_\{\\mathrm\{inc\}\}, and the different configurations ofAutoGrableon a selected subset of the i\.i\.d\. tabular benchmark TabArena\[tabarena\]\. The datasets are selected for having more than 8 categorical features and a binary classification target\.

Table 8:TabArena \(i\.i\.d\. single\-table\) results\. AUC averaged overN=15N\{=\}15seeds\. Baselines above the rule;AutoGrableconfigurations below, with bold marking the best validation score among them\. A∗marks a configuration that selects no columns and therefore returnsγtriv\\gamma\_\{\\mathrm\{triv\}\}; a∘marks one that selects all of them and therefore returnsγinc\\gamma\_\{\\mathrm\{inc\}\}\. Since each label depends on its own row, no constructor is expected to improve onγtriv\\gamma\_\{\\mathrm\{triv\}\}\.Here the labels are allegedly i\.i\.d\. at the row level, so the informative outcome should be that no structure is selected\. In every task at least oneAutoGrableconfiguration returns the empty column set and so reduces toγtriv\\gamma\_\{\\mathrm\{triv\}\}, and in four of five at least two do\. All ten such cases are forward search, and eight of them are frequency\-encoded forward search: starting from the empty set, no column offers a validation gain that covers the fragmentation it adds\. Building structure anyway is not neutral\. Full incidence gains on validation and loses on test relative toγtriv\\gamma\_\{\\mathrm\{triv\}\}\(→0\.7200\.800\\\!\\to\\\!0\.720oncredit\-g,→0\.7760\.839\\\!\\to\\\!0\.776onmkt\_campaign, against drops of0\.0050\.005and0\.0220\.022\), which is the fragmentation\-driven overfitting thatΩ\\Omegais meant to detect\.

#### D\.6\.4Relational databases results

Table[9](https://arxiv.org/html/2608.11431#A4.T9)shows results ofAutoGrableand the other baselines in both validation and test set of Relbench tasks\.

Table 9:Validation and test AUROC \(↑\\uparrow\) under a*fixed*predictor; only the constructor varies\. Mean±\\pmstd overN=15N\{=\}15seeds\. Best inbold, secondunderlined\.