RelShap: Relationally Consistent Shapley Explanations

RelShap is a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations. The framework is estimator-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties. Functional dependencies further induce equivalence classes over feature coalitions, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not.

Most machine learning pipelines flatten relational data into single-table representations for model training. Once a predictive model is trained on such a flattened table, practitioners routinely seek to understand its predictions at the level of individual instances. Shapley value-based attributions have become a dominant approach for this purpose, assigning each input feature a score based on its contribution to the prediction. Notably, relational ML is a well-established setting, yet approaches that train directly on multi-table data must ultimately attribute predictions to individual features and thus face the same explanation-time flattening.

In practice, this computation requires two conceptual choices: background data selection, which determines how feature absence is simulated using reference data, and coalition selection, which specifies which feature subsets are evaluated. Existing methods instantiate different sides of the tension between being true to the model and true to the data. SHAP, the most widely used implementation, stays true to the model by assuming feature independence but potentially considers feature combinations that never arise in the data. Aas et al. instead remain true to the data by estimating conditional distribution, but only as true as the estimate itself, and the estimator's errors propagate directly into the attributions.

Both premises are problematic on data drawn from a relational database. The flattening step can discard database-level information, such as functional dependencies (FDs) that imply that some features are fully determined by others, and domain constraints that restrict admissible values. Feature independence is violated by these very constraints, and conditional distribution estimation, while potentially avoiding that violation, introduces its own modeling assumptions. When attribution methods ignore relational constraints, they may evaluate the model on inputs that could never arise from the underlying relational data, thereby fundamentally altering the resulting feature attributions.

Core contribution: We present RelShap—Relationally Consistent Shapley Explanations—the first framework to integrate relational database constraints into Shapley value-based feature attributions. RelShap changes the admissible space of the Shapley explanation itself: instead of relying on feature independence assumptions or additional distributional modeling, it restricts both background data and coalitions to relationally valid configurations through constraints derived from the database schema, query, and data. Importantly, in controlled settings with known ground truth, RelShap correctly identifies the dominant feature where Kernel SHAP, Conditional SHAP, and ManifoldShap do not. For instance, in a loan approval scenario, the explanation changes substantially depending on whether relational constraints are respected. The divergence is not a sampling artifact but a consequence of which feature combinations the explanation method permits.

Example 1. Consider two tables, Applicants(a id, age, life stage, empl) and Transactions(t id, a id, amount), linked by applicant identifier a id. Six representative applicants and their transactions are shown in Tables 1a and 1b. A data analyst issues the query:

SELECT a.a id, a.age, a.life stage, a.empl, SUM(t.amount) AS total amt FROM Applicants a, Transactions t WHERE a.a id = t.a id GROUP BY a.a id, a.age, a.life stage, a.empl;

to obtain an applicant-level view, then drops the identifier a id and adds a target loan approved to yield the ML-ready dataset in Table 1c.

ML practitioners computing explanations typically receive only this final flattened representation, with no visibility into the upstream structure. Applicant a27 applied for a loan, was rejected, and sought an explanation. Kernel SHAP, a widely used method, reports life stage as the top driver of the prediction with a positive score. This attribution, however, is an artifact of relationally invalid completions from Kernel SHAP. For instance, fixing age = 35 and filling in the rest from applicant a29 yields the combination (age = 35, life stage = older), which is impossible under the FD age → life stage.

RelShap instead operates over a space of relationally valid completions, automatically extracting constraints from the data's relational structure. In this example, the data reveals a functional dependency (FD) age → life stage: each age value maps to exactly one life stage. Similarly, because the query aggregates all of an applicant's transactions into a single row, each applicant identifier determines exactly one total amt. RelShap enforces these constraints during Shapley computation: fixing age = 35 forces life stage = middle; the remaining attributes are unconstrained and filled from a chosen background data point (a29). Additionally, RelShap supports a provenance-aware mode that traces each row of the flattened table back to its source tuples in the original tables. Fixing age = 35 narrows the provenance to a27, the sole applicant with that age, at which point the schema determines empl = self emp and total amt = 119. Provenance-based recovery is not always available when it does not resolve to a single tuple: age = 63, for instance, is shared by a12 and a29.

Notably, RelShap computes different Shapley values even without approximation. Under both RelShap variants, life stage receives exactly zero attribution (which does not necessarily generalize), down from +0.2299 under Kernel SHAP, because the discovered FD age → life stage makes life stage redundant when age is present in a coalition, once coalitions are projected to relationally valid completions. Kernel SHAP ignores this redundancy and distributes substantial attribution to life stage. The top-ranked feature consequently changes from life stage to age. In all three cases, feature attribution values are computed exactly, over all background points and all coalitions; the divergence is not a sampling artifact but a consequence of which feature combinations the explanation method permits.

Our contributions are as follows:

1. RelShap alters both background data and coalition selection under relational constraints, producing attributions that correctly reflect the data-generating structure.

2. RelShap is agnostic to the choice of background data and coalition estimator: it enforces relational validity as a plug-in restriction layer while preserving the chosen background modeling approach and the base estimator's sampling and weighting scheme.

3. Computational effects: RelShap achieves orthogonal acceleration by avoiding redundant coalition evaluations while preserving Shapley values. We combinatorially characterize the resulting speedup factor as a function of the coalition estimator and FD structure.

4. We evaluate RelShap on 9 datasets across 4 models and 3 coalition estimators, empirically validating both the semantic effects and the runtime predictions.

Let F be the set of input features, f: RF → R a predictive model trained on Dtrain, and x ∈ Dtest an instance to be explained. To explain the prediction f (x), for any coalition S ⊆ F, xS denotes the projection of x onto S. The Shapley value of feature i ∈ F is defined as ϕi (f) = Σ S⊆F i S!(F − S − 1)! / F ! (f (xS∪ i) − f (xS)).

As discussed in Section 1, computing Eq. (1) in practice requires two design choices: background data selection, which determines how features in F S are filled in when evaluating f, and coalition selection, which subsets S ⊆ F i are evaluated. Since exhaustive enumeration over reference points and over the 2F −1 coalitions is infeasible in practice, both are typically operationalized via sampling. The two dimensions admit a multiplicity of instantiations and are typically treated as orthogonal. RelShap operates at the level of selection rather than sampling: it restricts the admissible background and coalition spaces to relationally valid configurations, so it applies whether the values are then computed exactly or approximated by any estimators.

Let Pbg (zF) denote a background distribution over the absent features indexed by F S, and B be the number of background samples (possibly all reference data points). With a completed input x̃(S, zF) ∈ RF, we define f (xS) = EzF ∼Pbg [f (x̃(S, zF))]. Methods differ in their choice of Pbg. Interventional methods, including default Kernel SHAP, treat feature absence as an intervention and fill absent features from the empirical marginal distribution, which is assumption-light but can break feature dependencies. Conditional SHAP instead estimates the distribution of absent features given the observed ones, aiming to preserve dependencies but potentially introducing estimator error. Causal methods intervene through a causal graph among the features, and ManifoldShap restricts completions to an estimated data manifold. These methods span the true to the model vs. true to the data axis discussed in Section 1. Importantly, RelShap is orthogonal to this axis: rather than choosing what distribution to put on the absent features, it constrains which configurations the chosen distribution is allowed to place mass on under relational constraints. The two design dimensions therefore compose rather than conflict: RelShap can be layered on top of any background data selection method. By default we use marginal (feature independence) as the base when no relational constraints are available, to comply with the no-distributional-assumptions property while removing the structurally infeasible inputs that Frye et al. and Taufiq et al. warn about.

We draw M coalitions from a coalition distribution Pcoal over S ⊆ F i and approximate ϕi (f) ≈ 1/M Σ M m=1 w(S (m))(f (xS (m) ∪ i) − f (xS (m))). Different Shapley value estimators choose different Pcoal and importance weight w. Kernel SHAP fits a weighted linear surrogate using the Shapley kernel, which concentrates weight on extreme (very small or large) coalition sizes. Monte Carlo (MC) estimator samples coalitions from the Shapley-weighted distribution, with coalition sizes sampled approximately uniformly. Leverage SHAP uses leverage score-based sampling, sampling the coalition size nearly uniformly and then sampling a coalition uniformly within that size. Recent variants further improve estimation through residual estimation or Fourier basis reduction. RelShap is estimator-agnostic and provides orthogonal acceleration: it preserves any base estimator's sampling distribution, weights, and accuracy guarantees, canonicalizing sampled coalitions under relational validity. Witter et al. also uses equivalence classes, but derives them from structural causal models. Maafa et al. studies lattice-structured coalition spaces to reduce computations, but not for ML predictions.

Many ML datasets originate from relational databases, where data is organized into multiple tables linked by keys. Flattening this structure into a single table for model training discards integrity constraints that govern valid data combinations. A functional dependency (FD) A → B states that the value of attributes in A uniquely determines the value of B; for instance, in Example 1, age → life stage means each age value maps to exactly one life stage. Domain constraints restrict attributes to valid ranges conditioned on other attributes (e.g., if region = 'North America' then currency ∈ 'USD', 'CAD', 'MXN'). Denial constraints capture structural prohibitions such as mutual exclusivity in one-hot encoded features. Standard Shapley estimators are free to violate all of these, evaluating the model on feature combinations that could never arise in the data-generating process. RelShap systematically prevents this.

RelShap incorporates two types of relational constraints: global, applied to all test instances, and local, instantiated per test instance. ΣFD is global; provenance-aware constraints, Σdom, and Σden are applied locally. RelShap first prepares relational constraints for downstream modules, either directly from relational inputs or from flattened-only inputs through normalization. We denote a relational schema as S, a query as Q, and the resulting flattened dataset as D. The schema, query, and resulting data together induce a collection of relational constraints, which we denote by Σ S,Q,D = ΣFD ∪Σdom ∪Σden, where ΣFD, Σdom, and Σden are the sets of FDs, domain constraints, and denial constraints, respectively. After extracting all relational constraints, users inspect them and specify which types of constraints to include and to what extent; we denote the resulting set by Σ.

Relational schema. ΣS contains schema-declared integrity constraints: FDs from primary and unique keys, dependencies induced by foreign keys (applied when the corresponding relations are joined in the query), and conditional domain constraints (e.g., CHECK clauses), ignoring unary type constraints already satisfied by the data. Query. We parse Q using SQLGlot to extract query-induced FDs and conditional domain rules. ΣQ FD identifies GROUP BY clauses, window aggregation, top-1 selection patterns, and self-joins. Σdom captures WHERE and JOIN predicates. Flattened data. RelShap discovers exact minimal FDs with bounded left-hand-side size (default 2) and single-attribute right-hand sides; multi-attribute right-hand sides can be derived via Armstrong's axioms. For any L ⊆ F and attribute a ∈/ L, let D/L denote the partition of D induced by equality on L; an FD L → a holds if, for all equivalence classes C ∈ D/L, DISTINCTa (C) ≤ 1. For each discovered FD A → B with dom(B) ≤ 20 (default), we derive conditional domain rules (B = s) ⇒ φ(A): for categorical A, φ(A) is the set of observed values; for continuous A, an interval [ls, us] estimated from the data. We also extract denial constraints by identifying cycles in the FD set (e.g., A → B, B → C, C → A) and testing for structural patterns common in ML data, such as scaled one-hot encodings and exclusive-or among binary attributes. By default, we use D for constraint discovery and Dtrain as the reference distribution.

Definition 1 (Relationally Consistent Background Distribution). Given a feature set F, a coalition S ⊆ F, an instance x, and a set of relational constraints Σ, we define Pbg Rel = (Pbg Marginal, if Σ = ∅, P ZF x̃(S, ZF) = Σ otherwise.

Under Def. 1, any coalitions S and S ′ are Σ-equivalent, i.e., S ∼Σ S ′, if they induce the same set of relationally valid completions under Σ. Accordingly, [S]Σ denotes the equivalence class of S under ∼Σ, and the Σ-coalition space CΣ is the quotient of the original coalition space by ∼Σ, collapsing coalitions indistinguishable under Σ.

Definition 2 (Quotient space coalition projection). Given CΣ, quotient space coalition projection is a post-sampling procedure that maps a coalition S ⊆ F i drawn by any sampler to its Σ-equivalence class [S]Σ (i.e., each coalition value is replaced by its canonical representative under Σ). For example, if Σ contains an FD a → b over a, b, c, then a ∼Σ a, b and a, c ∼Σ a, b, c, and hence each pair belongs to the same Σ-equivalence class. Under Def. 2, once a coalition is evaluated, subsequent samples mapping to the same Σ-equivalence class reuse cached results without additional model calls. Two properties hold, for distinct reaso…

Based on the paper, here are the specific improvements you can make to AI systems and what the improved system can do:

• Improvement: Integrate relational database constraints (functional dependencies, domain constraints, denial constraints) into Shapley value computation.

• What the improved system can do: Generate feature attributions that never evaluate the model on impossible feature combinations (e.g., age=35 with life stage=older when an FD says age→life stage). This prevents spurious attributions to redundant features and correctly identifies the true dominant feature in controlled settings where Kernel SHAP, Conditional SHAP, and ManifoldShap fail.

• Improvement: Trace each flattened data row back to its source tuples in the original relational tables, using identifier-induced dependencies.

• What the improved system can do: When a coalition fixes certain features (e.g., age=35), the system narrows provenance to a single source tuple (e.g., applicant a27), then infers all other feature values (empl, total amt) from that tuple, producing fully consistent completions. In relaxed mode, it handles ambiguous provenance by using features constant across candidate tuples.

• Improvement: Exploit functional dependencies to collapse equivalent coalitions into equivalence classes, reusing cached evaluations.

• What the improved system can do: Reduce runtime by up to the theoretically characterized speedup factor (Theorem 1) without changing Shapley values. For example, with FD a→b, coalitions a and a,b are equivalent, so only one model evaluation is needed. The system preserves the base estimator's sampling distribution and accuracy guarantees while deduplicating evaluations.

• Improvement: Apply relational constraints as a plug-in restriction layer on top of any coalition estimator (Kernel SHAP, Monte Carlo, Leverage SHAP).

• What the improved system can do: Enforce relational validity without altering the estimator's sampling or weighting properties. This means users can keep their preferred estimator while gaining correctness, and the system works across linear, tree-based, and neural models.

• Improvement: Automatically extract functional dependencies, domain constraints, and denial constraints from either relational schemas/queries or from flattened data alone.

• What the improved system can do: When given only a flattened table (common in practice), the system discovers exact minimal FDs (e.g., age→life stage) and conditional domain rules, then applies them during explanation. This removes the need for manual constraint specification and works even when the original database structure is unavailable.

• Improvement: Eliminate all relationally invalid perturbations during Shapley computation (violation prevalence = 0%).

• What the improved system can do: In synthetic scenarios with known ground truth (e.g., loan approval where only age matters), the system consistently assigns higher attribution to the true dominant feature (age) across all perturbation strengths δ, while baselines increasingly misattribute to life stage as invalid perturbations grow. This demonstrates robustness to adversarial or accidental invalid feature combinations.

• Improvement: Restrict background data and coalitions to configurations that could actually arise from the underlying relational data.

• What the improved system can do: Produce explanations that reflect the true data-generating structure, leading to large and systematic ranking changes (e.g., Top-3 Jaccard distance up to 0.96 on TPC-H) compared to unconstrained methods. This is particularly important for high-stakes domains like credit approval, where explanations must align with actual data constraints.

• Improvement: Provide a theoretical characterization (Theorem 1) of expected runtime reduction based on FD structure and coalition estimator.

• What the improved system can do: Predict before execution how much speedup to expect (empirically validated with Pearson correlation 0.806 and Kendall τ 0.741), enabling users to decide whether to enable quotient mode based on their data's FD structure and estimator choice.

• Improvement: Extract constraints efficiently as a one-time preprocessing step (under 12 seconds for most datasets, 98.9s for MovieLens 20M, 482.7s for SpeedDating).

• What the improved system can do: Handle large relational datasets without significant overhead, reusing extracted constraints across all explanation queries for multiple instances and models.

• Improvement: Validate across logistic regression, XGBoost, Random Forest, and MLP-PLR models.

• What the improved system can do: Consistently produce relationally valid explanations regardless of the underlying predictive model, making it suitable for diverse ML pipelines in production.