{"id":"3ba543f6-787e-499f-af07-f2399200f44f","arxiv_id":"2608.11508","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"RelShap restricts Shapley value explanations to relationally valid data configurations, using functional dependencies, domain constraints, and provenance, and provides a quotient-mode speedup that preserves exact Shapley values.","lead":"Machine learning explanations that ignore the structure of relational databases can score features using input combinations that could never exist in the data. This paper presents RelShap, which restricts Shapley explanations to relationally valid configurations, with a runtime optimization claimed to preserve the values.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 1's quotient-mode invariance is proven only for exact summation; Algorithm 1's deduplication without reweighting changes sampling estimators' empirical distribution, so the 'all estimators' claim is unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: Prop. 1 proves invariance only for exact summation over equivalence classes, while Algorithm 1's deduplication without reweighting changes the empirical distribution of sampling-based estimators. This is not a minor technicality; it undercuts the paper's third contribution and the abstract's promise that RelShap composes with Kernel SHAP, Monte Carlo, and Leverage SHAP 'without altering their sampling or weighting properties.' The paper's own Appendix C.1 shows that Kernel SHAP accumulates duplicate weights, directly contradicting Algorithm 1's skip behavior. A corrected argument would need to define class-level weights (e.g., sum of Shapley weights over each class) and have the estimator use those weights, or restrict Prop. 1's invariance claim to exact computation and adjust the runtime claims accordingly. The semantic core of RelShap—restricting background and coalition spaces to relationally valid configurations—is well motivated, clearly formalized (Def. 1, Def. 3), and empirically supported by the controlled ground-truth experiment, where RelShap is the only method with zero violation prevalence. The runtime experiments and the correlation with Theorem 1 are useful but do not settle the correctness of deduplicated sampling estimators. Therefore the verdict should remain CONDITIONAL: the central relational-consistency contribution is sound, but the orthogonal-acceleration claim needs a proof or a revised statement before the paper's full claims can be accepted.","tokens_in":45204,"tokens_out":7854,"duration_ms":74330,"concrete_test":"On a controlled setup with features {a,b,c}, FD a->b, a small synthetic model f, and a fixed background dataset, compute exact Shapley values by full enumeration (with relational background restriction only). Then for the Monte Carlo estimator with budget M=1000, compute (1) the standard MC estimate that counts every draw (duplicates included), and (2) the RelShap quotient-mode estimate exactly as in Algorithm 1: sample M coalitions, canonicalize via FD closure, skip coalitions already seen, and average over the distinct canonical classes. Repeat over 100 seeds. If the mean of (2) differs from the exact Shapley value by more than the standard error of (1), or if the distribution of (2) is shifted relative to (1), then quotient deduplication changes the estimator and Prop. 1's 'all coalition estimators' claim fails for MC.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's third contribution is that quotient mode reduces runtime without changing Shapley values for any coalition estimator (Prop. 1, abstract, Section 3.2). The proof in Appendix F.1 groups coalitions by Sigma-equivalence classes and factors the exact Shapley sum: sum_{S in C_k} w(S) times the class evaluation. This is valid only for exact enumeration. Algorithm 1, however, is a post-sampling procedure (Def. 2): it draws M raw coalitions, maps each to a canonical representative, and then skips any canonical coalition already in Seen (lines 15-18). Skipping a duplicate removes a sample that the base estimator would have counted. For Monte Carlo, the estimator averages over all M draws; dropping duplicates without reweighting replaces the Shapley-weighted average with an average over unique equivalence classes, which is generally biased. For Kernel SHAP, Appendix C.1 explicitly states that duplicate coalitions are handled by increasing the regression weight of the existing row; Algorithm 1 instead discards the duplicate, so the weighted regression design matrix differs from the base estimator's. For Leverage SHAP, stratified sampling without replacement within each size stratum is altered because canonicalization can change the coalition size (e.g., FD a->b maps {a} to {a,b}), so the effective size distribution and stratum counts no longer match the intended design. The paper asserts (Section 3.2) that the base estimator's distribution, weights, and accuracy guarantees are preserved because constraints are applied before deduplication, but applying constraints that expand or repair coalitions itself changes the sampled object's size and value. No theorem or proof addresses the expectation, variance, or regression solution of the deduplicated estimator; Prop. 1 only covers the exact sum. Thus the central claim that quotient mode is a pure speedup with identical Shapley values for all estimators is unsupported as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces RelShap, a framework for computing Shapley-value explanations on machine-learning predictions made from flattened relational data. RelShap derives constraints (functional dependencies, domain constraints, denial constraints, and provenance) from the relational schema, the flattening query, and the data, and uses them to restrict both the background data used for completion and the coalition space evaluated. The authors further propose a quotient mode in which coalitions equivalent under the discovered functional dependencies are canonicalized and deduplicated, claiming that this preserves Shapley values exactly while reducing runtime; the expected speedup is characterized combinatorially (Theorem 1). The experimental section evaluates RelShap on nine datasets and multiple models/estimators, including controlled settings with synthetic ground truth, and reports substantial changes in explanations and runtime reductions.","tokens_in":45516,"tokens_out":5226,"duration_ms":49251,"significance":"If the technical claims are established, RelShap addresses a real and under-explored problem: standard Shapley estimators freely evaluate feature combinations that violate relational integrity, and this can change attributions in ways that are hard to detect. The framework's separation of background selection from coalition restriction is conceptually clean, and the combinatorial analysis of FD-induced equivalence classes is a useful contribution. The paper also ships reproducible code, provides a broad empirical evaluation, and is honest about several limitations. However, the central claim that quotient mode preserves Shapley values for all estimators is not proven for sampling-based estimators, and the controlled ground-truth validation is partly circular. These issues affect the paper's main advertised contributions and should be resolved before publication.","major_comments":[{"comment":"Prop. 1 states that quotient-space coalition projection leaves Shapley values unchanged for all coalition estimators, but the proof in Appendix F.1 only reasons about exact summation over equivalence classes. Algorithm 1, however, is a post-sampling procedure: it draws M raw coalitions, canonicalizes each, and then skips any canonical representative already in Seen (lines 15–18). For the Monte Carlo estimator, which averages over all M Shapley-weighted draws, dropping duplicates without reweighting changes the empirical average and generally introduces bias. For Kernel SHAP, Appendix C.1 explicitly states that duplicate coalitions are handled by increasing the regression weight of the existing row; Algorithm 1 instead discards the duplicate, so the weighted regression design matrix differs from the base estimator's. For Leverage SHAP, canonicalization can change the coalition size (e.g., the FD a→b maps {a} to {a,b}), altering the stratified-without-replacement sample design and the effective stratum counts. Thus the statement in Section 3.2 that the base estimator's sampling distribution, weighting scheme, and accuracy guarantees are preserved is unsupported for sampling-based estimators. Please either prove an appropriate reweighting that preserves each estimator's target quantity, restrict Prop. 1 to exact enumeration and to estimators that are provably invariant under deduplication, or modify Algorithm 1 to accumulate duplicate weights rather than skip them.","section":null},{"comment":"The controlled experiment defines ground truth as the model's behavior on the relationally valid domain, which is exactly the space to which RelShap restricts. Since g(x)=1{age>50}+δ r(life_stage)1{x does not satisfy Σ} only deviates from the label-generating rule on relationally invalid inputs, and since all training and test instances satisfy Σ, any method that never evaluates invalid completions will trivially attribute the prediction to age. RelShap is the only method in the comparison that enforces Σ exactly, so the result that RelShap ranks age first is partly by construction. The experiment still usefully demonstrates that invalid completions can distort standard estimators, but it should be framed as a sanity check of the proposed semantics rather than as independent evidence of correctness. Please add a validation setting where the ground truth is not defined by the same constraint set passed to RelShap (for example, a known generative mechanism whose relational constraints are hidden from the explainer), or explicitly discuss this circularity in the limitations section.","section":null}],"minor_comments":[{"comment":"The phrase \"post-sampling procedure\" is ambiguous about whether duplicate draws are removed, reweighted, or both; given that Prop. 1 and Algorithm 1 hinge on this, the definition should state explicitly what happens to the sampling distribution and to the estimator's weights.","section":null},{"comment":"The y-axis label \"Top attribution frequency\" is not defined precisely; please clarify whether it is the fraction of instances in which each feature has the largest absolute Shapley value and how ties are handled.","section":null},{"comment":"The columns \"Top-3 Jaccard\", \"1−RBO\", \"Δ Jaccard\", and \"Δ RBO\" are introduced without definitions in the table caption; please define them there or provide an explicit pointer to Appendix J where the null-baseline construction is described.","section":null},{"comment":"The default thresholds (left-hand-side size bound of 2, domain cardinality bound of 20, provenance candidate threshold τ) are presented without sensitivity analysis; since the framework's behavior depends on these choices, a brief robustness study or at least a discussion of their influence would improve reproducibility.","section":null},{"comment":"Several references list only partial author information (e.g., \"GitHub. 2023\" and multiple entries with \"et al.\" without author names); please complete the bibliographic details before the final version.","section":null}],"recommendation":"major_revision","confidential_remarks":"The technical gap between the exact-sum proof and the sampling-based claim is the key issue; it is fixable within the scope of the paper, but the current wording overstates the result. The controlled experiment's circularity should also be acknowledged or supplemented. The paper's positioning relative to the database-Shapley literature is clear and fair."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Seun,\n\nYou can skip the first read and go straight to Section 3.2 if you want to find the paper's main stress point. The core contribution is solid: RelShap is the first framework to make Shapley explanations respect relational constraints—FDs, domain and denial constraints, and provenance—by restricting both background data and coalition evaluation to relationally valid configurations. That's a real gap. Flattened tables lose exactly this structure, and standard SHAP will happily evaluate impossible worlds. The controlled experiment in Section 4.1 shows the problem clearly: kernel SHAP, conditional SHAP, and ManifoldShap all drift as the invalid perturbation strengthens, while RelShap stays fixed and correctly ranks the dominant feature. The paper is honest about the limits of that validation, and the code release makes replication easy.\n\nThe soft spot is the quotient-mode acceleration claim. The stress-test note is correct: Proposition 1's proof in Appendix F.1 works by grouping coalitions into equivalence classes and factoring the exact Shapley sum. That is fine for exact enumeration. But Algorithm 1 is a sampling procedure that draws raw coalitions, maps them to canonical representatives, and then skips any canonical coalition already seen. That changes the estimator. For Monte Carlo, dropping duplicates without reweighting replaces a Shapley-weighted average over draws with an average over unique classes—generally biased. Kernel SHAP's own duplicate handling increases the regression weight of the existing row; Algorithm 1 discards the duplicate instead, so the design matrix differs. Leverage SHAP's stratified without-replacement sampling is also broken because canonicalization can change coalition size. The paper's assertion that constraints applied before deduplication preserve the base estimator's distribution is not an argument; the pushforward of the sampling distribution under canonicalization is different. This is a load-bearing overclaim, because the abstract and contribution list explicitly say quotient mode leaves Shapley values unchanged for all estimators. It needs to be fixed—either by defining class-level weights or by restricting the invariance claim to exact computation.\n\nThe other weakness is that the controlled validation is partly by construction: ground truth is defined as the model's behavior on the valid domain, exactly the space RelShap restricts to. That's a fine way to demonstrate the mechanism, but it doesn't by itself establish superiority on real data. The paper acknowledges this in the limitations, so I don't hold it against them.\n\nWho is this for? People working at the intersection of XAI and data management, and anyone who cares about explanations that respect what the data allows. The paper deserves a serious referee: the main idea is novel, the experiments are extensive, and the fixes are tractable. Send it to review, but the reviewers should insist on a corrected or qualified quotient-mode claim.","headline":"RelShap's core idea is good and the controlled experiments are clean, but the paper overclaims that quotient mode accelerates sampling estimators without changing Shapley values; Prop. 1 only covers exact enumeration.","tokens_in":46146,"tokens_out":3267,"would_cite":true,"duration_ms":32067,"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":"RelShap restricts Shapley explanations to relationally valid feature combinations, and in controlled settings it is the only tested method that correctly identifies the dominant feature.","keywords":["RelShap","Shapley values","feature attribution","relational databases","functional dependencies","data provenance","explainable AI","model explanations"],"falsifier":"Run Kernel SHAP (or Monte Carlo) on a small dataset with a known functional dependency at a fixed sampling budget, once with quotient-mode deduplication and once without, and compare the estimated Shapley values. If the two estimates differ beyond sampling noise for any estimator, Proposition 1 fails as stated for that estimator; if they agree, the invariance claim holds.","tokens_in":44975,"feed_emoji":"🗄️","tokens_out":12267,"duration_ms":96428,"temperature":0.7,"pith_summary":"RelShap makes Shapley feature attributions respect the relational structure of the data they were computed from. Standard Shapley implementations treat feature coalitions as arbitrary subsets and fill absent features independently, so they routinely evaluate the model on combinations a relational database could never produce — in the paper's experiments, 64–93% of sampled coalitions violate at least one discovered constraint. The paper claims that excluding these relationally invalid configurations changes which features look important: in a controlled setting with known ground truth, RelShap is the only method among Kernel SHAP, Conditional SHAP, and ManifoldShap that always ranks the genuinely dominant feature first, while the others shift attribution toward a redundant feature as invalid perturbations strengthen. Because the restriction is a plug-in layer, it composes with any coalition estimator without changing its sampling or weighting scheme, and the same constraints that fix the semantics can be exploited to cut runtime by collapsing equivalent coalitions.","feed_headline":"Schema-aware Shapley finds the right feature; rivals miss it","feed_subtitle":"RelShap rules out impossible feature combinations, keeping explanations tied to the database that produced the data.","key_machinery":"Three objects carry the argument. The relationally consistent background distribution (Def. 1) places probability mass only on completions that satisfy the extracted constraint set $\\Sigma$; the $\\Sigma$-equivalence relation (Def. 3) declares two coalitions equivalent when they induce the same set of relationally valid completions; and quotient-space coalition projection (Def. 2) maps every sampled coalition to its canonical representative, so equivalent coalitions share one cached evaluation. Functional dependencies do the heavy lifting: discovered from the data, declared by the schema, or induced by the query (a GROUP BY makes the grouping key determine the aggregates), they force certain features to be included in a coalition once others are, and their closure under Armstrong's axioms defines the lattice of equivalence classes. Counting those classes (Prop. 2, building on known closed-set counts) feeds the expected-speedup formula (Thm. 1), $E[K_M]=\\sum_{C\\in\\mathcal{C}_\\Sigma}\\left(1-(1-q(C))^M\\right)$, which predicts runtime reduction from the interaction of the estimator's coalition-size distribution with the FD-induced collapse counts.","core_discovery":"The paper's central claim is that Shapley-value explanations of models trained on flattened relational data are calculated wrong: the standard computation evaluates the model on feature combinations that violate the database structure that generated the data. RelShap changes the admissible space of the explanation itself, extracting constraints — functional dependencies, domain and denial constraints, and identifier-induced dependencies recovered through provenance — from the database schema, the query, and the data, and restricting both background data and coalition evaluation to configurations that satisfy them. In the running loan-approval example, the functional dependency $\\mathrm{age}\\to\\mathrm{life\\_stage}$ makes the latter feature redundant once age is observed: under RelShap, life_stage receives exactly zero attribution, down from +0.2299 under Kernel SHAP, and age becomes the top-ranked feature. In a controlled two-feature experiment with the predictor $g(x)=\\mathbf{1}\\{\\mathrm{age}>50\\}+\\delta\\, r(\\mathrm{life\\_stage})\\,\\mathbf{1}\\{x\\nvDash\\Sigma\\}$, where the perturbation term activates only on relationally invalid combinations, RelShap is the only method among Kernel SHAP, Conditional SHAP, and ManifoldShap that consistently assigns the larger attribution to age as $\\delta$ grows. The paper further claims that functional dependencies induce equivalence classes over coalitions, and that projecting sampled coalitions onto these classes (quotient mode) leaves Shapley values unchanged while provably reducing runtime.","pith_inferences":["A direct corollary of the paper's violation-prevalence numbers is a new diagnostic: practitioners could report the fraction of relationally invalid coalitions an explanation method queries as a data-quality signal for the explanation itself.","The framework's own machinery supports approximate functional dependencies, so the natural stability test is whether a small violation tolerance preserves the correct top-feature identification on noisy or incomplete real-world schemas.","The expected-speedup analysis is a coupon-collector formula over whatever relation induces coalition equivalence; the same formula should transfer to equivalence classes derived from causal structure, so the runtime argument is not specific to functional dependencies.","Because the paper validates correctness only against synthetic ground truth (it explicitly defers a user study), the decisive open question is whether humans make better decisions with relationally consistent attributions."],"forward_implications":["When a feature is functionally determined by others, RelShap transfers its attribution to the determining features, so the top-ranked feature can change even when Shapley values are computed exactly rather than sampled.","Quotient mode reduces the number of model evaluations with Shapley values unchanged; the speedup is largest for Kernel SHAP when the data has many low-arity functional dependencies, because Kernel SHAP concentrates its sampling on the small coalitions that most often collapse together.","Relational consistency composes with any coalition estimator and any model type, making the choice of background semantics and the choice of estimator independent design decisions rather than competing ones.","In the controlled ground-truth setting, RelShap's explanations are insensitive to relationally invalid perturbations as their strength δ grows from 0 to 10, while Kernel SHAP, Conditional SHAP, and ManifoldShap increasingly misattribute importance to the redundant feature."],"supporting_citations":[{"why":"Supplies the default estimator and its marginal background distribution, whose relationally invalid completions (e.g., age=35 paired with life_stage=older) RelShap rules out.","marker":"Lundberg and Lee 2017"},{"why":"The conditional-distribution baseline that still permits residual FD violations (4.8% in the controlled experiment) and serves as a comparison method.","marker":"Aas et al. 2021"},{"why":"ManifoldShap baseline (5.1% residual violations) whose controlled evaluation design Section 4.1 follows for ground-truth validation.","marker":"Taufiq et al. 2023"},{"why":"Provides Armstrong's axioms, the closure rules used to canonicalize coalitions and to derive multi-attribute right-hand sides of discovered FDs.","marker":"Armstrong 1974"},{"why":"Gives the closed-set/lattice characterization and counting formulas for FD-induced classes (Prop. 2) that Theorem 1's expected-speedup analysis builds on.","marker":"Demetrovics et al. 1992"},{"why":"Defines Leverage SHAP, one of the three coalition estimators RelShap composes with while preserving its sampling scheme.","marker":"Musco and Witter 2025"},{"why":"Coupon-collector style arguments used in the proof of Theorem 1 for the expected number of distinct equivalence classes sampled.","marker":"Flajolet et al. 1992; Motwani et al. 1995"},{"why":"Background for discovering exact functional dependencies from data, the mechanism RelShap uses when schema and query constraints are unavailable.","marker":"Huhtala et al. 1999; Papenbrock et al. 2015"}],"fun_headline_variants":["RelShap ties Shapley to database rules, not random combos","Schema-aware Shapley: RelShap finds the true driver","Shapley's relational blind spot: RelShap sees it","Data-valid Shapley: RelShap beats rivals on faithfulness","RelShap rejects impossible feature combos, others don't"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that skipping coalitions already evaluated in canonical form leaves Shapley values unchanged for every estimator, a claim the paper proves only for exact full enumeration, not for the sampling-based estimators it is used with in practice.","fun_headline_variants_meta":{"raw":{"variants":["RelShap ties Shapley to database rules, not random combos","Schema-aware Shapley: RelShap finds the true driver","Shapley's relational blind spot: RelShap sees it","Data-valid Shapley: RelShap beats rivals on faithfulness","RelShap rejects impossible feature combos, others don't"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000337,"raw_usage":{"total_tokens":1911,"prompt_tokens":1040,"completion_tokens":871,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":778}},"tokens_in":656,"tokens_out":871,"duration_ms":8591,"temperature":1.0,"reasoning_tokens":778,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T13:57:39.839316+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Kernel SHAP (or Monte Carlo) on a small dataset with a known functional dependency at a fixed sampling budget, once with quotient-mode deduplication and once without, and compare the estimated Shapley values. If the two estimates differ beyond sampling noise for any estimator, Proposition 1 fails as stated for that estimator; if they agree, the invariance claim holds.","supporting_citations":[],"review_version":1}