# Efficient SAGE Estimation via Causal Structure Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 66 references that are in the map.
- First posted on arXiv 6 Apr 2023.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Explainable Machine Learning in Deployment](https://mlsanity.com/paper/1909.06342/) (2019)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices](https://mlsanity.com/paper/1906.09208/) (2019)
- [Learning Likelihoods with Conditional Normalizing Flows](https://mlsanity.com/paper/1912.00042/) (2019)
- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Foundations of Structural Causal Models with Cycles and Latent Variables](https://mlsanity.com/paper/1611.06221/) (2016)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Asymmetric Shapley values: incorporating causal knowledge into model-agnostic explainability](https://mlsanity.com/paper/1910.06358/) (2019)
- [Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models](https://mlsanity.com/paper/2011.01625/) (2020)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [General Pitfalls of Model-Agnostic Interpretation Methods for Machine Learning Models](https://mlsanity.com/paper/2007.04131/) (2020)
- [Conditional Density Estimation with Bayesian Normalising Flows](https://mlsanity.com/paper/1802.04908/) (2018)
- [Shapley Flow: A Graph-based Approach to Interpreting Model Predictions](https://mlsanity.com/paper/2010.14592/) (2020)
- [Interpretable Classification Models for Recidivism Prediction](https://mlsanity.com/paper/1503.07810/) (2015)
- [Large-scale empirical validation of Bayesian Network structure learning algorithms with noisy data](https://mlsanity.com/paper/2005.09020/) (2020)
- [SHAFF: Fast and consistent SHApley eFfect estimates via random Forests](https://mlsanity.com/paper/2105.11724/) (2021)
- [Scientific Inference With Interpretable Machine Learning: Analyzing Models to Learn About Real-World Phenomena](https://mlsanity.com/paper/2206.05487/) (2022)
- [Conditional Feature Importance for Mixed Data](https://mlsanity.com/paper/2210.03047/) (2022)

## Built on by (most cited first, 4 of 4)

- [Explaining Predictive Uncertainty with Information Theoretic Shapley Values](https://mlsanity.com/paper/2306.05724/) (2023)
- [Explaining Bayesian Optimization by Shapley Values Facilitates Human-AI Collaboration](https://mlsanity.com/paper/2403.04629/) (2024)
- [A Guide to Feature Importance Methods for Scientific Inference](https://mlsanity.com/paper/2404.12862/) (2024)
- [Practical do-Shapley Explanations with Estimand-Agnostic Causal Inference](https://mlsanity.com/paper/2509.20211/) (2025)

## Abstract (arXiv)

The Shapley Additive Global Importance (SAGE) value is a theoretically appealing interpretability method that fairly attributes global importance to a model's features. However, its exact calculation requires the computation of the feature's surplus performance contributions over an exponential number of feature sets. This is computationally expensive, particularly because estimating the surplus contributions requires sampling from conditional distributions. Thus, SAGE approximation algorithms only take a fraction of the feature sets into account. We propose d-SAGE, a method that accelerates SAGE approximation. d-SAGE is motivated by the observation that conditional independencies (CIs) between a feature and the model target imply zero surplus contributions, such that their computation can be skipped. To identify CIs, we leverage causal structure learning (CSL) to infer a graph that encodes (conditional) independencies in the data as d-separations. This is computationally more efficient because the expense of the one-time graph inference and the d-separation queries is negligible compared to the expense of surplus contribution evaluations. Empirically we demonstrate that d-SAGE enables the efficient and accurate estimation of SAGE values.