GNNExplainer: Generating Explanations for Graph Neural Networks

一、总览
原文由斯坦福大学的5位大佬带来，作为2019年NIPS的优质论文之一，原文的思想结构很清晰。顾名思义，原文核心提出一个通用的、模型无关的图神经网络（Graph Neural Networks，GNN）的解释器。

相较于比较经典的模型解释方法，如：LIME，SHAP。原文中的方法在思想上有异曲同工之妙，不深入探究模型内部的参数和结构，专注于信息本身，通过探索“改变”信息，对比模型结果，来监测被“改变”的信息是否足够重要。原文中对这一过程用高度抽象的一句话表示：We formulate GNNEXPLAINER as an optimization task that maximizes the mutual information between a GNN’s prediction and distribution of possible subgraph structures.

原文的整体结构如下：

介绍。
相关工作。
问题定义与GNN
GNNExplainer（最核心部分）
实验
结论
附录
原文可以在下面地址找到：https://arxiv.org/abs/1903.03894?context=cs

开源代码链接：https://github.com/RexYing/gnn-model-explainer

本文将尽量用人话阐述原文的基本内容与核心思想。

二、简介
图大家都很熟悉，不多吹牛逼。原文认为理解GNN的工作方式很重要：

可以提高人对GNN的信任程度。（事实上，我个人认为在绝大多数工作中，第一重要的不是精度，而是客户对我们模型的理解。客户不认可，模型结果100%正确也没用。）
在很多与公平、隐私与安全相关的领域应用中，这样能提高模型的透明度。
可以提高开发者对网络特征的理解、认知，并且减少模型出现系统性错误的风险。
常规解释其他神经网络的两个主流方式是：

对于模型本身进行解释。
通过对指标重要性的解释来解释模型。
但这两种解释方案，都没有把关系信息考虑进解释方案中。因此提出GNNExplainer，此方法将一个已经训练好的GNN和其预测结果作为输入，然后通过输出一个子图以及该子图上更少的特征，表示其输出最大程度的影响了该GNN的预测结果。这个子图可以最大化与GNN预测结果的互信息。在这个过程中，会有一个图掩码，用于挑选真正重要的子图；一个特征掩码，用于挑选真正重要的子特征集。用一个图解释一下这个过程，如下：

假设我们能看到图上红色中心[公式] 与绿色中心 [公式] 两个点，要预测红色中心点是Basketball，绿色中心是Sailing。GNNExplainer可以通过输出输入图结构子图与节点特征子集的方式，表示最能影响预测结果的子图结构与特征向量子集。在图中可以看出，预测红色中心为basketball的原因是周边都是进行球类运动的人，而预测绿色中心为sailling的原因是周边都是进行水上、沙滩运动的人。这里被高亮的除中心节点外的部分可以认为是找到的重要“结构”信息，而这些节点干的事情可以认为是重要的“特征”向量。

三、问题定义
图、边集合、节点集合分别是 [公式] ，并且有一个d维的节点特征集合 [公式] ，下面讨论一个节点分类的问题。假定 [公式] 表示一个函数 [公式] 将节点映射到 [公式] 个不同的类别中。已经训练好的GNN模型用 [公式] 表示。

通常，在模型的第 [公式] 层，我们认为一个GNN模型，由以下三个核心部分组成：

MSG，代表每对节点间的信息传递部分。在一对节点 [公式] 中的信息，可以通过两个节点在上一层的编码 [公式] 表示 [公式] 。
AGG，表示对于某个节点中心子图的信息汇集。假定节点 [公式] 的邻居节点集合为 [公式] ，那么其信息汇聚可以表示为 [公式] 。
UPDATE，表示根据上面内容，进行编码更新。可以表示为 [公式] 。
那么模型要做的事情，就是通过GNN给定的预测结果 [公式] ，找到其解释 [公式] ，其中前者是重要的子图结构，后者是重要的特征子集。PS: 这里的 [公式] 表示掩码，即是， [公式] 。

四、GNNExplainer
4.1 单节点解释
对于节点 [公式] ，我们的目标是找到对其预测结果 [公式] 重要的子图 [公式] 和重要的特征子集 [公式] 。这样利用互信息MI(mutual information)，可以将GNNExplainer表示为： [公式]

举个例子来说：当 [公式] 时，当把节点 [公式] 从 [公式] 中移除后，预测结果 [公式] 降低的很多，那么我们可以认为 [公式] 是对于 [公式] 很重要的节点。类似地，如果 [公式] ，当把关系 [公式] 从 [公式] 中移除后，预测结果 [公式] 降低的很多，那么我们认为这对关系对 [公式] 很重要。

回到上面的式子，当一个GNN训练完成后，那么 [公式] 就是确定的。这样上面的式子就变成了最小化条件熵 [公式] ，如下： [公式] 由优化，可以得出：[公式]原文提出，由Jesen's inequality可以得出： [公式] 由于Jesen's inequality的假设：要求函数需要是凸函数，才能得出上式推论。因此，原文中也给出了玄学的解释：别管那么多，可以用，信就行！

4.2 结合图结构与节点特征的信息
为了可以解释对于预测结果最重要的指标集，GNNExplainer会学习一个特征选择器 [公式] ，并认为 [公式] 是 [公式] 中的节点所带有特征的子集：[公式]那么解释问题就变为了最大化其MI：[公式]解这个方程可以用

L. Zintgraf, T. Cohen, T. Adel, and M. Welling. Visualizing deep neural network decisions: Prediction difference analysis. In ICLR, 2017.
中提到的Monte Carlo Estimate。

原文同时提出，上式的目标函数同样可以加入正则项（如：element-wise entropy），作为扩展限制。

4.3 单类别（Multi-instance or Single Class）解释
与4.1和4.2不同的是，有时候需要对模型判别一类或同一标签下所有样本的过程进行解释。原文提出两个步骤：

对于一个给定的类，先选定一个参考节点 [公式] ，然后解释 [公式] （也就是用4.1的方法），通过此来解释所有被分配到该类的节点。
将该类的邻接矩阵聚合后进行计算（也就是用4.2的方法），并认为这样的解释结果可以代表对整个类的解释。
这里继续引入原文中的玄学部分：

这里的参考节点可以先所有该类节点编码的平均值。然后取具有最接近该平均值编码的节点作为参考节点；或者，通过先验的知识挑选一个节点作为参考节点。这部分操作虽然在整个深度学习界很常见，但我个人对这样的操作表示不甚满意。但是既然大牛们说了可以！那就信就行啦！

4.4 GNNExplainer扩展
原文再次强调，GNNExplainer的好处是：

适用于任何在图上的机器学习任务。
适用于任何GNN模型。
复杂度低。
五、实验
实验部分的内容结构非常清晰，介绍了相关数据、baseline的选取等。结果如下：

这里的Explanation accuracy是通过已知的ground-truth explanation计算得出。

六、结论与延伸
引用原文中的一句话说明此方法的特点： GNNEXPLAINER, a novel method for explaining predictions of any GNN on any graphbased machine learning task without requiring modification of the underlying GNN architecture or re-training.