- Rating
- 2(+1)
- Confidence
- 3(+2)
- Informativeness
- 2
- Presentation
- 2(+1)
- Soundness
- 2(+1)
Read review
Paper summary
This paper proposes RelCraft, a framework for automated feature engineering in relational learning. The method uses a typed, point-in-time-checked program representation to generate and verify SQL features. It introduces coalition-based credit assignment to guide LLM-driven program search and employs a protected selection mechanism with a statistical risk bound to select the final program and predictor. The authors evaluate RelCraft on several relational learning benchmarks, comparing predictive performance and efficiency against existing methods. They also conduct ablation studies to examine the contributions of the proposed components.
Critical strengths
-
The paper addresses a practical problem in relational learning by integrating program verification, point-in-time constraints, and feature search into a unified framework.
-
The experimental evaluation covers multiple relational learning benchmarks and includes ablation studies and efficiency analyses, providing useful evidence of the effectiveness of the proposed framework.
Critical weaknesses
-
Presentation: The mathematical notation is not consistently presented, and several important definitions are scattered across the paper. For example, Eqs. (2), (8), and (10) use optimality notation for solutions obtained under different objectives.
-
Theoretical Assumptions: The theoretical guarantee relies on the independence of entity-group losses. However, relational databases naturally contain dependencies through shared entities, relationships, and temporal effects. The paper does not establish whether this assumption holds in the evaluated settings, raising concerns about the applicability of the theoretical guarantee.
-
Experimental Evaluation: The experiments do not sufficiently compare the proposed coalition-guided search with alternative program search strategies under the same constraints and computational budget. This makes it difficult to assess the necessity of the proposed search mechanism.
-
Methodological Validation: The paper does not clearly establish the assumptions and conditions under which coalition-based credit assignment can effectively guide program search, particularly when features exhibit strong interactions. These conditions should be explicitly formulated and empirically verified to support the central methodological claim.
Questions for authors
Questions For Authors:
-
Theorem 1 assumes independent entity-group losses. Given the dependencies naturally present in relational databases, how is this assumption justified in the evaluated datasets? Are the resulting risk bounds sufficiently tight to be meaningful in practice?
-
Under what conditions does coalition-based credit assignment effectively guide program search? In particular, how does the method discover strongly interacting features that have little predictive value individually?
-
How does coalition-guided search compare with alternative search strategies, such as greedy search or MCTS, under the same program constraints and computational budget? What evidence establishes that the observed improvements specifically arise from the proposed credit assignment mechanism?
7 comments
Response to reviewer
Thank you for the detailed response and additional experiments. I appreciate the improvements, but I still have several concerns.
-
Some notation inconsistencies remain. Equation (6) uses and , while Appendix D.2 describes normalized quantities. I also do not understand how hat in Eq. (7) is estimated or why a prediction is needed when execution time can be directly measured. In addition, why does Figure 2(c) use , while Eq. (7) uses ? Which notation is correct?
-
I appreciate the new comparisons. However, the improvements over MCTS and beam search in predictive accuracy are not significant. While the smaller programs and reduced selection–test gap are positive, I am still not fully convinced of the advantage of coalition credit over these stronger search strategies.
-
The new grouping analysis partially addresses my concern about independence. However, I am not sure whether the grouping is recursive, and even disjoint clusters do not necessarily imply independence. I understand that perfect independence is difficult to establish, but some discussion of residual dependence or its effect on the bound would be helpful. More importantly, the bound still seems extremely loose. For example, Table 19 allows a margin of 10.4 percentage points when the observed protected–test difference is only 0.2 points. I find it difficult to see the practical significance of such a loose bound.
Overall, the current evidence and responses have not changed my original concerns regarding the notation, theoretical, and experimental support for the proposed method. Therefore, I maintain my original rating.
We thank the reviewer for the follow-up and for confirming that coalition credit yields smaller programs and a smaller selection–test gap. Below we show that the scales are fixed in the paper, that coalition credit leads every alternative search rule on every outcome of Table 3b, and that the 10.4-point margin comes from the grammar-wide prior: on the frozen shortlist the same argument gives 2.0 points.
Q1. Notation in Eq. (6), Eq. (7), and Figure 2(c).
R: The scales are fixed in the submitted PDF; we collect them here.
(1) Eq. (6) writes the penalties in natural units. Appendix D.2 (Page 22) gives the scale used in code: enters as , and as . D.2 states that the main-text is implemented by ; both terms lie in . The unnormalized is used only in the prior .
(2) in Eq. (7). The measured time of already enters through Eq. (6). Eq. (7) chooses which path family to expand next. The blocks created by that expansion have not run yet, so D.2 and Table 9 (Page 22) specify a prediction on the scale. is the mean measured of the evaluated blocks in 's path family.
(3) Figure 2(c) shows the same score in schematic form. Its caption (Page 3) states that denotes of §4.2, so and .
Q2. Advantage over beam and MCTS.
R: With grammar, candidate pool, verifier, selector, and the 211-job budget held fixed, coalition credit is ahead of every alternative on every outcome of Table 3b. The differences in the deployed program are significant against all three.
| vs. | ΔAUROC [95% CI] | Fewer blocks | Latency (s/10K) | Sel/Test gap |
|---|---|---|---|---|
| LOO greedy | +0.41 [0.07, 0.75] | 7.2 (32/32) | −8.1% (29/32) | −0.23 |
| Beam (4) | +0.29 [0.05, 0.52] | 4.8 (31/32) | −5.9% (26/32) | −0.17 |
| MCTS | +0.24 [0.01, 0.48] | 4.4 (30/32) | −5.9% (30/32) | −0.15 |
(1) Accuracy. All three unadjusted 95% AUROC intervals exclude zero. With Holm correction over all search-rule contrasts, = 0.235–0.291, so §5.4 claims accuracy parity. AUTC$_N$ is significantly higher than for LOO and beam (Holm = 0.013).
(2) Deployed program. Block, latency, and gap differences all have . Latency uses the Table 15 runs. At the same budget and accuracy, MCTS and beam deploy 14–15% larger programs whose protected estimates track test less closely.
(3) Mechanism. When block value depends on partners, the accuracy gap is large. On XOR, coalition credit gains +0.45 AUROC over LOO, and it has higher Sign-F1 in all 12 interacting settings (Table 5, Page 9; Table 18, Page 30).
Q3. Grouping, residual dependence, and tightness.
R: (1) Grouping. Yes: clusters are connected components (the transitive closure) of the graph linking protected targets that share a row through a declared PK–FK edge. Point (2) covers what remains, such as time trends.
(2) Residual dependence. Suppose group losses have a dependency graph with fractional chromatic number . Then Hoeffding's inequality holds with in place of (Janson, RSA 2004). grows by a factor of , and the union argument is unchanged.
(3) Tightness. The 10.4-point margin reflects – nats, the union over the whole grammar that Eq. (8) uses to penalize long programs. Theorem 1 conditions on the frozen , so a uniform union over – is valid under the same assumptions, and every input is in Table 19 (Page 30):
- At the entity level, has median 1.9 points (range 1.6–9.1). On 4DB cla-01 it is 2.0 instead of 10.4. At the cluster level, the median is 2.9 points.
- The observed is 0.33 points on average. Its cluster-bootstrap 95% upper limit (at most 0.95) lies below the cluster-level on all 32 tasks.
- equals the Table 19 value at –. A certificate no larger than the reported bound therefore holds even if each protected group depends on up to 19 others.
In practice the selector keeps the gap small: without it, Sel/Test rises from 0.56 to 1.41 points (Table 4, Page 9).
The final version would add the shortlist certificate and result after Theorem 1 and the latency to Table 15. With the ethics concern resolved by the completed AI-use statement, we would be grateful if the reviewer would reconsider the score.
We sincerely thank the reviewer for the careful reading and constructive suggestions, and for recognizing that RelCraft addresses a practical problem by integrating program verification, point-in-time constraints, and feature search, with evaluation across multiple benchmarks, ablations, and efficiency analyses. Below, Q denotes each question and R our response.
Q1. AI-use statement.
R: The previous version is replaced by the completed statement on Page 11: generative AI was used only for grammar, spelling, and typographical checks and for reference verification, and the authors reviewed all edits and take full responsibility for the content. We apologize for the oversight and hope this resolves the flag.
Q2. Eqs. (2), (8), and (10) use optimality notation for different objectives.
R: The revision separates the three objects explicitly (§3, Notation, Page 3). Eq. (2) defines the population target (Q∘,ϕ∘). Search visits measured states hr=(Qr,ϕr) and freezes a shortlist H. The protected selector returns h⋆∈H (Eq. 8), and the deployed artifact is ϕ⋆ fitted on Ttr∪Tdev (Eq. 10).
Q3. Is the independence assumption justified, and is the bound tight enough to be meaningful?
R: The bound is non-vacuous and contains the test loss on all 32 tasks, and the observed gap stays within it under dependence-aware grouping. Theorem 1 is stated for independent protected entity groups (§4.4, Page 6). The new bound audit (Appendix E.6, Table 19, Page 30) measures it per task:
(1) At the entity level, the complexity term has median 0.095 and the bound median 0.272; the bound contains the test bounded loss on every task, exceeding it by 0.122 on average; the complexity term is at most 0.15 on 27 of 32 tasks.
(2) To probe dependence, we merge targets that share relational neighbors into clusters (155–5,726 per task) and treat each cluster as one group. This raises the complexity term by 1.59× on average and moves the Sel/Test gap only from 0.56 to 0.587 points. On every task, the upper 95% cluster-bootstrap limit of the protected–test gap (at most 0.95 points) stays below the cluster-level bound.
Q4. How does coalition-guided search compare with greedy search or MCTS under the same constraints and budget?
R: Coalition credit has the highest AUROC of six search rules, the smallest programs, and the best-calibrated selection. In the new search-rule control (§5.4, Table 3b, Page 8; Appendix E.2, Table 15, Page 28), all rules share the typed grammar, frozen candidate pool, verifier, protected selector, seeds, and 211 jobs; only the search rule changes. Coalition credit versus each alternative:
All block and gap differences have Holm p<0.001. Because every other component is held fixed, these differences arise from the credit assignment itself.
Q5. When does coalition credit guide search, and how does it find strongly interacting features with little individual value?
R: Coalition credit helps when a block's value depends on partners in the program universe. It scores each block in sampled contexts of every size (Eq. 5, Page 4), so a block is evaluated both with and without its partner. Leave-one-out credit scores a block in one context; an XOR block whose partner is absent gets zero gain and is pruned before the pair forms. This is why typed LOO search stays at 0.500 AUROC on XOR, while RelCraft reaches 1.000 (Table 5a, Page 9).
The new interaction sweep (Table 5b, Page 9; Appendix E.5, Table 18, Page 30) adds 1% label flips and six distractor features:
(1) With additive labels both rules agree (AUROC 0.988 vs. 0.984), so coalition credit costs nothing without interaction.
(2) The advantage grows with interaction strength: for XOR at M=8, the AUROC gain over LOO rises from 0.11 at strength 0.25 to 0.45 at full strength.
(3) Higher-order interactions need more contexts: for fourth-order parity, Sign-F1 exceeds LOO from M=8 (0.787 vs. 0.722; 0.836 at M=16).
With the default M=8, coalition credit beats LOO on both AUROC and Sign-F1 in all 12 interacting settings.
We hope the completed disclosure, the clarified notation, and the new controls address the reviewer's concerns, and we would be grateful if the reviewer would consider raising the score.