# L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data

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

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2018.

## Built on by (most cited first, 30 of 100)

- [Generic Attention-model Explainability for Interpreting Bi-Modal and Encoder-Decoder Transformers](https://mlsanity.com/paper/2103.15679/) (2021)
- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [A Consistent and Efficient Evaluation Strategy for Attribution Methods](https://mlsanity.com/paper/2202.00449/) (2022)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [TalkToModel: Explaining Machine Learning Models with Interactive Natural Language Conversations](https://mlsanity.com/paper/2207.04154/) (2022)
- [Rethinking Explainability as a Dialogue: A Practitioner's Perspective](https://mlsanity.com/paper/2202.01875/) (2022)
- [Rethinking Attention-Model Explainability through Faithfulness Violation Test](https://mlsanity.com/paper/2201.12114/) (2022)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [TokenSHAP: Interpreting Large Language Models with Monte Carlo Shapley Value Estimation](https://mlsanity.com/paper/2407.10114/) (2024)
- [Shapley Explanation Networks](https://mlsanity.com/paper/2104.02297/) (2021)
- [Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00285/) (2021)
- [On the Explainability of Natural Language Processing Deep Models](https://mlsanity.com/paper/2210.06929/) (2022)
- [Explaining a Series of Models by Propagating Shapley Values](https://mlsanity.com/paper/2105.00108/) (2021)
- [Understanding Interlocking Dynamics of Cooperative Rationalization](https://mlsanity.com/paper/2110.13880/) (2021)
- [Explaining Predictive Uncertainty with Information Theoretic Shapley Values](https://mlsanity.com/paper/2306.05724/) (2023)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Interpretable Geometric Deep Learning via Learnable Randomness Injection](https://mlsanity.com/paper/2210.16966/) (2022)
- [The Role of Explainability in Assuring Safety of Machine Learning in Healthcare](https://mlsanity.com/paper/2109.00520/) (2021)
- [Discovering Transferable Forensic Features for CNN-generated Images Detection](https://mlsanity.com/paper/2208.11342/) (2022)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Explainability is NOT a Game](https://mlsanity.com/paper/2307.07514/) (2023)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [groupShapley: Efficient prediction explanation with Shapley values for feature groups](https://mlsanity.com/paper/2106.12228/) (2021)
- [Self-Interpretable Model with TransformationEquivariant Interpretation](https://mlsanity.com/paper/2111.04927/) (2021)
- [Surrogate Model-Based Explainability Methods for Point Cloud NNs](https://mlsanity.com/paper/2107.13459/) (2021)
- [Logic Traps in Evaluating Attribution Scores](https://mlsanity.com/paper/2109.05463/) (2021)

## Abstract (arXiv)

We study instancewise feature importance scoring as a method for model interpretation. Any such method yields, for each predicted instance, a vector of importance scores associated with the feature vector. Methods based on the Shapley score have been proposed as a fair way of computing feature attributions of this kind, but incur an exponential complexity in the number of features. This combinatorial explosion arises from the definition of the Shapley value and prevents these methods from being scalable to large data sets and complex models. We focus on settings in which the data have a graph structure, and the contribution of features to the target variable is well-approximated by a graph-structured factorization. In such settings, we develop two algorithms with linear complexity for instancewise feature importance scoring. We establish the relationship of our methods to the Shapley value and another closely related concept known as the Myerson value from cooperative game theory. We demonstrate on both language and image data that our algorithms compare favorably with other methods for model interpretation.