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

Abstract

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