# RelShap: Relationally Consistent Shapley Explanations

arXiv: https://arxiv.org/abs/2608.11508 · HTML: https://mlsanity.com/paper/2608.11508/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 46 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 22 of 22)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [When Do Neural Nets Outperform Boosted Trees on Tabular Data?](https://mlsanity.com/paper/2305.02997/) (2023)
- [On Embeddings for Numerical Features in Tabular Deep Learning](https://mlsanity.com/paper/2203.05556/) (2022)
- [OpenML Benchmarking Suites](https://mlsanity.com/paper/1708.03731/) (2017)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models](https://mlsanity.com/paper/2011.01625/) (2020)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [Computing the Shapley Value of Facts in Query Answering](https://mlsanity.com/paper/2112.08874/) (2021)
- [The Shapley Value in Database Management](https://mlsanity.com/paper/2401.06234/) (2024)
- [Fool SHAP with Stealthily Biased Sampling](https://mlsanity.com/paper/2205.15419/) (2022)
- [Explanation Multiplicity in SHAP: Characterization and Assessment](https://mlsanity.com/paper/2601.12654/) (2026)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [Relation-Stratified Sampling for Shapley Values Estimation in Relational Databases](https://mlsanity.com/paper/2511.22035/) (2025)

## Abstract (arXiv)

Machine learning pipelines commonly flatten relational data into single-table representations, discarding structural constraints. Widely used Shapley value-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations. We propose RelShap, 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. Our code is available at: https://github.com/duneag2/relshap.