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.

本研究探讨了实例级特征重要性评分作为模型解释方法，并提出两种线性复杂度的算法来评估图结构数据中的特征贡献，并与其他模型解释方法进行比较。