This paper studies faithful explanations for Graph Neural Networks (GNNs).
First, we provide a new and general method for formally characterizing the
faithfulness of explanations for GNNs. It applies to existing explanation
methods, including feature attributions and subgraph explanations. Second, our
analytical and empirical results demonstrate that feature attribution methods
cannot capture the nonlinear effect of edge features, while existing subgraph
explanation methods are not faithful. Third, we introduce \emph{k-hop
Explanation with a Convolutional Core} (KEC), a new explanation method that
provably maximizes faithfulness to the original GNN by leveraging information
about the graph structure in its adjacency matrix and its \emph{k-th} power.
Lastly, our empirical results over both synthetic and real-world datasets for
classification and anomaly detection tasks with GNNs demonstrate the
effectiveness of our approach.

本文研究了图神经网络（GNNs）的可信解释，并提供一种全新的通用方法来形式化描述 GNNs 的可信解释，包括特征归因和子图解释。作者提出的 KEC 方法从图的结构和其 k 次幂得到信息，可以最大程度地提高生成解释的准确性以及说明原始 GNN 的预测结果，同时弥补了子图解释和特征归因方法的缺陷。经过作者使用多种合成和真实数据集的分类和异常检测任务的实验证明，该方法是有效的。