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

2018/08/07 by Jianbo Chen, Chen, Jianbo, Le Song +5 · 10 citations
Computer Science · Mathematics · #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1808.02610

arxiv created 2018/08/08 · openalex publication_date 2018/08/08 · arxiv updated 2018/08/09 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• MASE: Interpretable NLP Models via Model-Agnostic Saliency Estimation
• MACIE: Multi-Agent Causal Intelligence Explainer for Collective Behavior Understanding
• Adaptive Node Feature Selection For Graph Neural Networks
• Rigorous Feature Importance Scores based on Shapley Value and Banzhaf Index
• Attri-Net: A Globally and Locally Inherently Interpretable Model for Multi-Label Classification Using Class-Specific Counterfactuals
• A case for data valuation transparency via DValCards
• A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
• Prediction via Shapley Value Regression
• Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning
• A Meaningful Perturbation Metric for Evaluating Explainability Methods

Related

• Explaining the Model and Feature Dependencies by Decomposition of the Shapley Value
• Shapley Flow: A Graph-based Approach to Interpreting Model Predictions
• Problems with Shapley-value-based explanations as feature importance measures
• Explaining individual predictions when features are dependent: More accurate approximations to Shapley values
• Shapley Sets: Feature Attribution via Recursive Function Decomposition