{"id":"534a2a47-620e-4532-a65f-2f99520b785f","arxiv_id":"2608.11431","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"AutoGrable selects table columns for graph construction using a training-free label-alignment score, and matches or beats task-aware constructors on real benchmarks.","lead":"A new method, AutoGrable, decides which columns of a table should become shared nodes in a graph before any neural network is trained, by scoring how well the induced row grouping matches the labels. It lets graph neural networks be applied to tables without hand-built graphs, and can even choose to build no graph when structure does not help.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"J-score proxy for downstream GNN performance is the weakest link; Lemma 1 applies only to row-feature-erased graphs, while the GNN uses full row features, and Table 2 shows weak/negative correlations.","rationale":"The paper's central claim is that AutoGrable finds good graphs. The theoretical backbone is: (i) a 1-WL-bounded GNN sees a construction as a colour-refinement partition; (ii) for incidence constructions with row features erased, that partition equals the projection partition π_S (Lemma 1); (iii) therefore construction reduces to column selection, and the score J over π_S should pick good columns. Step (iii) is where the argument is weakest. Lemma 1 holds for the erased reduct G°_S(T), but the GNN actually trains on G_S(T) with unexpanded row features. The paper acknowledges this ('may separate rows within a structural cell'), but then J is optimizing a partition that does not match the object the GNN sees. A GNN can exploit row-local features to solve labels that are not constant on π_S cells; J's block predictor cannot, so J can systematically reject useful constructions. The empirical correlation between J and downstream AUC is weak and even negative on test (tau_b = -0.08 on driver-top3, Table 2), and the paper retreats to 'one-sided screen,' which is not a justification for minimization. The greedy search minimizes J, so a biased proxy directly affects the returned graph. The unproven multi-table extension is secondary; even in the single-table regime the proxy gap exists. The controlled tasks (RQ1) do not include a case where the label depends on unselected row features interacting with the selected structure, so they do not exercise this failure mode. A targeted synthetic experiment would settle whether J can identify useful structure that only a GNN, not a block-constant predictor, can exploit.","tokens_in":25616,"tokens_out":8937,"duration_ms":80101,"concrete_test":"Construct a synthetic table where y depends jointly on a categorical column C and a row-local continuous feature f (e.g., y=1 iff C='a' and f>0.5). Run AutoGrable with all 8 configurations and record whether S* contains C. Then train the fixed GraphSAGE on γ(S*) and on γ_triv. If C is not selected because J's block-constant predictor cannot use f, yet the GNN on the C-incidence graph beats γ_triv by more than one standard error, J is not a reliable proxy for the construction's downstream value.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that AutoGrable selects good graphs rests on treating J(π_S) — validation risk of a block-constant predictor plus occupancy penalty — as a reliable proxy for downstream GNN performance. This is the least secure assumption. Lemma 1 equates the colour-refinement partition of the incidence grable with π_S only for the row-feature-erased reduct G°_S(T). The actual graph G_S(T) retains unexpanded row features, so its colour-refinement partition refines π_S; a GNN can use those features to separate rows within a cell. J penalizes exactly that within-cell label heterogeneity because the block predictor cannot use row features, so J can undervalue constructions whose value is in enabling message passing between rows with informative local features. The theoretical guarantees (Lemma 5, Proposition 1) apply to the block predictor, not the GNN. Table 2 shows Kendall tau_b as low as -0.08 on test; the paper only defends J as a 'one-sided screen,' which does not justify minimizing it. Since Algorithm 1 greedily minimizes J, a weak or biased proxy can drive selection to suboptimal graphs. The multi-table extension has no analogue of Lemma 1, so relational results lack the same anchor.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes AutoGrable, a training-free method for choosing which columns of a table (or foreign-key schema) to expand into an incidence graph before applying a GNN. The argument is that for a message-passing GNN bounded by 1-WL, the only information a construction conveys is the colour-refinement partition of the row nodes; under the row-feature-erased incidence grable this partition equals the projection partition onto the selected columns (Lemma 1). The paper defines an alignment score J(pi_S) equal to the validation risk of a block-constant predictor plus lambda times an occupancy penalty, proves a Rademacher-style estimation bound and a uniform validation guarantee for this score, and searches over column subsets by greedy forward/backward local search (Algorithm 1). The same score is applied to materialised joins over foreign-key paths. Experiments address column recovery on synthetic tasks, correlation of J with downstream GraphSAGE AUC on RDB2G-Bench candidate graphs, and comparison with trivial, full-incidence, random, REG, and auGraph constructors on transactional and RelBench tasks.","tokens_in":25913,"tokens_out":7689,"duration_ms":67578,"significance":"If the main claim were fully established, the paper would make a genuinely useful contribution: it offers a training-free, interpretable criterion for graph construction, with the attractive consequence that the constructor can decline to build a graph. The theoretical apparatus around the block predictor (Lemmas 3-5 and Proposition 1) is largely sound, and the experiments are extensive, with a fixed predictor and multiple baselines. However, the bridge from the block-predictor score to the actual downstream GNN is the weakest link: Lemma 1 concerns only the feature-erased reduct, the correlations in Table 2 are weak and only one-sided, and the multi-table extension has no theoretical anchor. The paper is best read as proposing a heuristic screening criterion with a partial theoretical justification; the current evidence does not support the stronger claim that minimizing J selects graphs that are optimal or near-optimal for GNN training.","major_comments":[{"comment":"Lemma 1 is stated without proof and applies only to the row-feature-erased reduct G°_S(T_tr). The graph actually trained on is G_S(T), whose row nodes carry the unexpanded attributes r|A\\S; as the paper notes in Section 4, pi_CR(G_S(T)) refines pi_S. Therefore the equivalence that reduces construction to column selection does not hold for the real object of learning. A GNN can separate rows within a cell of pi_S using row-local features, while the block predictor used by J cannot; the occupancy penalty in J charges for exactly this within-cell refinement. Consequently J can systematically undervalue constructions whose benefit is to enable message passing between rows with informative local features. The generalisation bound in Lemma 5 and the oracle inequality in Proposition 1 apply to the block predictor, not to a GNN trained on the constructed graph. Please prove Lemma 1, give the precise relation between pi_CR(G_S(T)) and pi_S, and either extend the theory to the full graph or explicitly restrict the claims to the feature-erased setting.","section":"Section 4, Lemma 1 and 'What the downstream GNN receives'"},{"comment":"The empirical support for J as a proxy for downstream performance is weak. On the test split, Spearman's rho between J and AUC is -0.118 and -0.251 for driver-top3 and -0.158 and -0.287 for study-outcome, with Kendall's tau_b between -0.082 and -0.219. These correlations are consistent with a one-sided screen only in the loose sense that no high-J graph performs well; the paper reports no threshold-selection procedure, no operating-characteristic analysis of the screen, and no comparison between graphs selected by minimizing J and graphs selected by other thresholds. Since Algorithm 1 greedily minimises J, a weak or biased proxy can drive selection to suboptimal graphs while still preserving a negative correlation. The RQ2 evidence should be supplemented by an explicit threshold analysis and by a direct evaluation of the downstream AUC of the graphs that Algorithm 1 actually returns.","section":"Section 5.2, Table 2"},{"comment":"No analogue of Lemma 1 is given for the multi-table setting. After left-joining along foreign-key paths of length < d and collapsing duplicate appearances with weight 1/k_i(S), the paper does not show that the colour-refinement partition of the resulting multi-table incidence graph equals the weighted projection partition on which J is evaluated. The relational results in Table 3 and Table 9 therefore rest on an unverified assertion. Either provide the corresponding equivalence, with the multiplicity weighting made explicit, or present the multi-table procedure as a heuristic and temper the claims accordingly.","section":"Section 3, 'Extension to relational databases'"},{"comment":"J is computed on T_val and used to select S*, and the same validation split is used for early stopping and checkpoint selection of the final GNN. Proposition 1 provides a uniform guarantee for the block-predictor score on the validation set, but not for the downstream GNN's test risk after selection. Because AutoGrable's construction choice is made by inspecting validation labels, its reported test performance is not obtained under the same selection protocol as the fixed baselines. Please report results with a three-way split, or nested validation, so that the construction-selection validation set is disjoint from the early-stopping validation set, or provide an argument that the validation reuse does not favour AutoGrable.","section":"Sections 2 and 5; Appendix D.6.1"},{"comment":"The method's behaviour is heavily controlled by the signature, direction, and lambda axes. Under frequency encoding, the row-local families Single-val, Conj, and XOR return the empty set in most configurations (Table 1), and the fixed setup reported in Table 3 (forward direction, lambda=1, frequency encoding) cannot recover these row-local tasks. The paper does not provide a principled rule for choosing signature, direction, and lambda, and the abstract's unqualified claim that AutoGrable recovers the generating columns is only true when the axes are matched to the task family. This is a practical gap for a method whose advertised advantage is being training-free; at minimum the claims should be restricted to the configuration actually recommended.","section":"Tables 1, 7, and 8"}],"minor_comments":[{"comment":"The paragraph introducing FREQENCODE uses both 'frequency-recoded copy' and 'frequency encoding'; please clarify that the encoding is applied only to candidate columns, while the label and the attributes outside F are unchanged.","section":"Equation (2)"},{"comment":"The x-axis label appears garbled ('J score of label versus color with = 1'); please fix the caption and the axis label.","section":"Figure 2"},{"comment":"There is an incomplete sentence: 'We therefore use the greedy local search in' followed by the heading 'Search strategy.' Please repair this typo.","section":"Appendix C.7"},{"comment":"The cell format '∅(0) †' is not explained in the caption; please clarify what the dagger denotes when the selected set is empty, since an objective-metric mismatch against the empty set needs a separate definition.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is creative and the conceptual framing is appealing, but the key theoretical bridge (Lemma 1 applied to the actual trained graph) is not established, and the empirical evidence connecting J to downstream GNN performance is thin. I do not think this warrants rejection: the method may be valuable as a cheap screening heuristic, and the authors are transparent about the one-sided nature of J. However, the abstract and conclusions overstate the strength of the result, and the multi-table claims need either a proof or a clear heuristic label. I would also encourage the authors to make the controlled-task axis dependence more prominent, since the fixed configuration chosen for Table 3 is not the one that succeeds on the row-local synthetic families."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe useful news: for the incidence grable construction, this paper reduces graph construction to column selection. Lemma 1 shows that colour refinement on the row-feature-erased graph induces exactly the projection partition onto the selected columns. For a 1-WL-bounded GNN, that partition is the expressive ceiling, so choosing columns is choosing structure. That is a clean, real idea, and it is the right frame for table-to-graph construction.\n\nThe J score is a sensible instantiation: validation risk of a block-constant predictor plus an occupancy penalty, with a standard generalisation bound. The NP-completeness reduction is standard. The experiments are unusually honest: Table 2 reports weak correlations instead of hiding them, and the negative control where AutoGrable declines to build a graph is a nice touch. Code is public.\n\nThe soft spots are in the link between J and the downstream GNN. The paper does not claim the GNN sees only π_S; Section 4 explicitly notes that row features refine the partition. But J is scored by a predictor that cannot see row features, so it can undervalue constructions whose payoff comes through message passing between rows with informative local features. The correlations in Table 2 are one-sided and weak, especially on test (Kendall tau_b down to -0.08). Calling J a one-sided screen is fair, but Algorithm 1 minimizes it, and a weak proxy can drive selection to suboptimal graphs. The theory applies to the block predictor, not to the GNN. That is the main gap to push on.\n\nA smaller issue: the reported real-task configuration (forward, λ=1, frequency) looks chosen after the fact, even though the appendix sweeps the axes. The multi-table extension has no analogue of Lemma 1; it is a heuristic. Also, J uses the validation split and early stopping uses the same validation split, so there is selection bias—not fatal, but worth a nested split.\n\nWho should read this: anyone building GNN pipelines for tables or relational data. It is a within-subfield contribution, not a paradigm shift, but a solid one. I would send it to review; a serious referee can ask for stronger proxy evidence or more restrained claims, but the core reduction is correct and worth engaging.","headline":"AutoGrable's reduction of table-to-graph construction to column selection is real and clean; the weak link between its J score and downstream GNN performance is the main thing to push on.","tokens_in":26383,"tokens_out":5223,"would_cite":true,"duration_ms":48584,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For a 1-WL-bounded GNN, a table-to-graph construction is seen only as a partition of the rows, so a good graph is one whose row groups align with the labels.","keywords":["table-to-graph construction","graph neural networks","1-WL colour refinement","column selection","label alignment","incidence grable","relational learning","training-free selection"],"falsifier":"Enumerate all $2^{|F|}$ column subsets for a fixed table and label, compute $J$ for each, and train a fixed 1-WL-bounded GNN on each incidence grable under a fixed hyperparameter budget. The criterion's claim is that low $J$ is necessary for strong downstream AUC; a single subset with low $J$ and poor test AUC, or a subset with high $J$ and top test AUC, would refute it. The paper's own test-split correlations are weak, so this direct enumeration is the decisive check.","tokens_in":25437,"feed_emoji":"📊","tokens_out":11466,"duration_ms":92747,"temperature":0.7,"pith_summary":"This paper asks what makes a graph a good one when the graph itself must be built from a table. Because a message-passing GNN bounded by the one-dimensional Weisfeiler–Leman test can see a construction only as the colour-refinement partition it induces on the rows, a graph is good when that partition places differently labelled rows in different classes and does not split rows that share a label. For the incidence construction, this partition is exactly the projection of the rows onto the selected columns, so choosing a graph reduces to choosing columns. The authors introduce a training-free score $J$, equal to the held-out risk of a cell-constant block predictor plus an occupancy penalty, search it greedily, and show that the resulting graph beats fixed, random, and task-aware constructors under a fixed predictor while being able to decline to build a graph entirely.","feed_headline":"Pick columns, not graphs, for table learning","feed_subtitle":"A training-free score selects columns whose row groups align with labels, and skips graphs that hurt.","key_machinery":"The load-bearing object is the incidence grable $G_S(T)$: a bipartite graph with one row node per table row, one value node per occurring value of each selected column, and a typed edge connecting a row node to each value it takes. Colour refinement (1-WL) on this graph stabilises to a partition of the row nodes, and Lemma 1 states that in the row-feature-erased reduct this stable partition is exactly $\\pi_S$, the partition of training rows by their projection onto $S$. That equality is what turns graph construction into column selection. The optimisation target is $J(\\pi_S) = \\widehat{\\mathrm{Risk}}_{\\mathrm{val}}(\\hat h_S) + \\lambda \\Omega(T^{tr},\\pi_S)$, with $\\hat h_S$ the empirical label distribution on each cell and $\\Omega(T^{tr},\\pi_S) = \\frac{1}{n_{tr}}\\sum_u \\sqrt{N_{S,u}}$ the occupancy penalty; $J$ is evaluated by a group-by and a validation pass, with no GNN trained.","core_discovery":"The central claim is that a table-to-graph construction is, for a 1-WL-bounded message-passing GNN, nothing more than a way of grouping rows, and the right grouping is one aligned with the label: separate different labels, do not split same labels without cause. The paper proves this for the incidence grable $G_S(T)$: with row features erased, its stable colour-refinement partition on row nodes equals the projection partition $\\pi_S = \\{r|_S\\}$ of the rows onto the selected columns. Consequently, searching over graphs is equivalent to searching over column subsets, and the quality of a subset can be judged in table space by the alignment score $J(\\pi_S) = \\widehat{\\mathrm{Risk}}_{\\mathrm{val}}(\\hat h_S) + \\lambda \\Omega(T^{tr},\\pi_S)$, where $\\hat h_S$ is the best cell-constant predictor and $\\Omega$ penalises sparsely populated cells. The selected columns are then expanded into value nodes to form the graph on which a GNN is trained; the block predictor is only the selection criterion, not the final model.","pith_inferences":["Any two constructions that induce the same 1-WL row partition should be interchangeable for a 1-WL-bounded learner; this equivalence is implicit and could be tested by rewiring edges within a cell and checking that attainable accuracy is unchanged.","Because $J$ is label-relative and training-free, it doubles as a regularised tabular feature-selection criterion: among all column subsets it picks those whose row groups can support a cell-constant predictor, independently of any graph.","Since $J$ is optimised for a block predictor, tasks whose labels depend on evidence a cell-constant predictor cannot see may be underserved; a score that also rewarded cross-cell interactions is a natural extension the paper does not explore.","The empty-selection behaviour suggests a deployment rule: run the score before deciding whether graph learning is worth it, and fall back to row-local models when it returns the empty set; the paper demonstrates this pattern but does not claim it as a universal law."],"forward_implications":["Graph construction can be taken out of the training loop: every candidate score is one group-by over the training rows plus one validation pass, so searching costs $O(|F|^2(n_{\\mathrm{tr}}+n_{\\mathrm{val}}))$ in the worst case.","For incidence constructions, the graph itself adds no row-distinguishing power beyond the selected columns' projection partition; it contributes cross-row evidence inside each cell, while unexpanded row features remain local to each row.","The same table has different good graphs for different tasks, and if the labels are row-local the good output may be no graph at all.","The trivial grable is an admissible and sometimes best output, and declining to build a graph avoids the validation-gain/test-loss overfitting observed when all columns are exposed on i.i.d. rows.","Even the weaker objective of separating all differently labelled rows with at most $k$ columns is NP-complete, so approximate greedy search is the practical route."],"supporting_citations":[{"why":"Establishes the 1-WL upper bound on what message-passing GNNs can distinguish, which fixes the partition view of constructions.","marker":"[7]"},{"why":"Provides the same colour-refinement bound for GNN architectures, supporting the claim that 1-WL is the expressive ceiling for the learner.","marker":"[8]"},{"why":"Defines the grable abstraction and the incidence grable, the object class that AutoGrable produces.","marker":"[9]"},{"why":"Supplies the relational entity graph baseline, a schema-skeleton constructor treated as a fixed construction in the comparisons.","marker":"[4]"},{"why":"Supplies the task-aware attribute-promotion constructor whose per-candidate GNN training motivates the need for a training-free score.","marker":"[6]"},{"why":"Provides the set of candidate graph constructions with trained-model performance used to test whether $J$ predicts downstream AUC.","marker":"[11]"},{"why":"Supplies the relational tasks on which AutoGrable and the baselines are compared.","marker":"[12]"},{"why":"Supplies the transactional fraud-detection tables whose shared values make cross-row structure potentially useful.","marker":"[14]"},{"why":"Supplies the i.i.d. single-table benchmark used as a negative control where constructing a graph should not help.","marker":"[15]"},{"why":"Provides the NP-completeness of test cover used to prove that selecting a separating column set is NP-complete.","marker":"[40]"}],"fun_headline_variants":["Training-free column selection picks good graphs for tables","For table GNNs, your graph is just the columns you keep","Score row groups by label alignment to pick graph columns","Skip graph search: choose columns that align labels with rows","A training-free score decides if a table graph will help"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the score $J$, the held-out risk of a cell-constant block predictor plus an occupancy penalty, is a reliable enough proxy for the downstream performance of a GNN trained on the selected graph; the paper's correlation evidence is weak and one-sided, and its generalisation bound applies to the block predictor, not the trained GNN.","fun_headline_variants_meta":{"raw":{"variants":["Training-free column selection picks good graphs for tables","For table GNNs, your graph is just the columns you keep","Score row groups by label alignment to pick graph columns","Skip graph search: choose columns that align labels with rows","A training-free score decides if a table graph will help"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000245,"raw_usage":{"total_tokens":1602,"prompt_tokens":1078,"completion_tokens":524,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":443}},"tokens_in":694,"tokens_out":524,"duration_ms":6595,"temperature":1.0,"reasoning_tokens":443,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:11:56.799811+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all $2^{|F|}$ column subsets for a fixed table and label, compute $J$ for each, and train a fixed 1-WL-bounded GNN on each incidence grable under a fixed hyperparameter budget. The criterion's claim is that low $J$ is necessary for strong downstream AUC; a single subset with low $J$ and poor test AUC, or a subset with high $J$ and top test AUC, would refute it. The paper's own test-split correlations are weak, so this direct enumeration is the decisive check.","supporting_citations":[{"cited_title":"Relbench: A benchmark for deep learning on relational databases.Advances in Neural Information Processing Systems, 37: 21330–21341, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the relational tasks on which AutoGrable and the baselines are compared."},{"cited_title":"How powerful are graph neural networks? InInternational Conference on Learning Representations, 2019","cited_arxiv_id":null,"evidence_quote":"Establishes the 1-WL upper bound on what message-passing GNNs can distinguish, which fixes the partition view of constructions."},{"cited_title":"Position: Relational deep learning - graph representation learning on relational databases","cited_arxiv_id":null,"evidence_quote":"Supplies the relational entity graph baseline, a schema-skeleton constructor treated as a fixed construction in the comparisons."},{"cited_title":"RDB2g-bench: A comprehensive benchmark for au- tomatic graph modeling of relational databases","cited_arxiv_id":null,"evidence_quote":"Provides the set of candidate graph constructions with trained-model performance used to test whether $J$ predicts downstream AUC."},{"cited_title":"Tabarena: A living benchmark for machine learning on tabular data","cited_arxiv_id":null,"evidence_quote":"Supplies the i.i.d. single-table benchmark used as a negative control where constructing a graph should not help."},{"cited_title":"Garey and David S","cited_arxiv_id":null,"evidence_quote":"Provides the NP-completeness of test cover used to prove that selecting a separating column set is NP-complete."}],"review_version":1}