The Shapley value is a prominent tool for interpreting black-box machine
learning models thanks to its strong theoretical foundation. However, for
models with structured inputs, such as graph neural networks, existing
Shapley-based explainability approaches either focus solely on node-wise
importance or neglect the graph structure when perturbing the input instance.
This paper introduces the Myerson-Taylor interaction index that internalizes
the graph structure into attributing the node values and the interaction values
among nodes. Unlike the Shapley-based methods, the Myerson-Taylor index
decomposes coalitions into components satisfying a pre-chosen connectivity
criterion. We prove that the Myerson-Taylor index is the unique one that
satisfies a system of five natural axioms accounting for graph structure and
high-order interaction among nodes. Leveraging these properties, we propose
Myerson-Taylor Structure-Aware Graph Explainer (MAGE), a novel explainer that
uses the second-order Myerson-Taylor index to identify the most important
motifs influencing the model prediction, both positively and negatively.
Extensive experiments on various graph datasets and models demonstrate that our
method consistently provides superior subgraph explanations compared to
state-of-the-art methods.

本论文提出了 Myerson-Taylor 互动指数，将图结构内化到节点值和节点之间的互动值之中，并使用 Myerson-Taylor 结构感知图解释器（MAGE）基于二阶 Myerson-Taylor 指数识别影响模型预测的最重要模体。通过在各种图数据集和模型上进行广泛实验，我们证明了与现有方法相比，我们的方法始终提供更好的子图解释。