Explaining Graph Neural Networks with Structure-Aware Cooperative Games
  Explaining predictions made by machine learning models is important and has
attracted increased interest. The Shapley value from cooperative game theory
has been proposed as a prime approach for computing feature importance towards
predictions, especially for images, text, tabular data, and recently graph
neural networks (GNNs) on graphs. In this work, we revisit the appropriateness
of the Shapley value for graph explanation, where the task is to identify the
most important subgraph and constituent nodes for graph-level predictions. We
purport that the Shapley value is a non-ideal choice for graph data because it
is by definition not structure-aware. We propose a Graph Structure-aware
eXplanation (GStarX) method to leverage the critical graph structure
information to improve the explanation. Specifically, we propose a scoring
function based on a new structure-aware value from the cooperative game theory
called the HN value. When used to score node importance, the HN value utilizes
graph structures to attribute cooperation surplus between neighbor nodes,
resembling message passing in GNNs, so that node importance scores reflect not
only the node feature importance but also the structural roles. We demonstrate
that GStarX produces qualitatively more intuitive explanations, and
quantitatively improves over strong baselines on chemical graph property
prediction, text graph sentiment classification, and synthetic subgraph
detection tasks.
