会员服务 ·

NeurIPS 2019 开源论文 | 万能的GNN解释器

2020 年 5 月 17 日 图与推荐

作者丨纪厚业

学校丨北京邮电大学博士生

研究方向丨异质图神经网络及其应用

本文由斯坦福 Jure 组发表在 NeurIPS 2019 上，一作 Rex Ying 也是著名的 GraphSAGE 的作者。代码和数据：

https://github.com/RexYing/gnn-model-explainer

引言

图神经网络（Graph Neural Network），作为深度学习领域最热门的方向之一，相关论文在各大顶会层出不穷。但是，图神经网络的解释性问题没有得到较多的关注。图神经网络的解释性是非常有必要的：1）提升了 GNN 的可信程度；2）在一些注重公平性，隐私性和安全性的决策应用，可以提升决策的透明度；3）可以更好的理解图本身的特性。

虽然一些基于 Attention 机制的模型（如 Graph Attention Network）可以一定程度上对 GNN 进行解释。但是，作者认为它们有两个问题：1）GAT 可以学习节点之间关系的权重，但是其只能实现对结构的进行解释而无法通过特征的角度进行解释；2）节点的 1-hop 邻居和 2-hop 邻居可能有重叠，GAT 会学习到同一对节点之间的不同权重。这时候到底该用那个无法抉择。

因此，本文提出了 GNNExplainer，可以从网络结构和节点属性的角度来对任意图神经网络和任意图挖掘任务生成解释。GNNExplainer 旨在探寻与预测结果最相关的子图结构来实现对结果的解释，其中 Graph Mask 和 Feature Mask 可以分别对实现对结构和特征的筛选。

上图给了一个如何对 GNN 预测的节点分类（Basketball 和 Sailing）的结果进行解释。针对节点及其 label 篮球，其邻居中很多人都喜欢球类也有一些喜欢非球类, GNNExplainer 可以自动的找到邻居中都喜欢球类的这些人。同样的，针对节点，GNNExplainer 也可以发现其好友中同样喜欢水上/沙滩类运动的好友。

模型

作者首先归纳了 GNN 的三个步骤：1）MSG，构建节点之间需要传递的消息；2）AGG，收集节点相关的消息；3）UPDATE，更新节点表示。下图解释了 GNNExplainer 要做的事情：自动发现重要的消息和特征。

Explanation via Structural Information

假定被选择的与模型预测结果 Y 最相关的的结构和特征分别为

和

，那么其重要性可以用互信息 MI 来衡量：

上式中的，H(Y) 是常数，因为 GNNExplainer 是在训练好的 GNN 上模型上进行解释。上式等价于最小化条件熵：

这样新的优化目标就是

，利用 Jensen 不等式和凸性假设，我们可以得到

。注意，这里的神经网络实际是不满足凸假设的。但是，作者通过实验发现上述目标函数 + 一定的正则可以实现高质量的解释。

为了实现对

的估计，这里用了平均场变分近似对 G 进行分解

。这里

代表边

存在的期望。上式中的

可以用

来代替，这里 M 是就是我们要学习的 Graph Mask。

很多任务只关心部分类的节点及其模型如何对该类进行预测。因此上式可以修正为：

在实际解释的时候，只需要设定阈值将 M 中的部分低于阈值的边移除就好。这样就从结构的角度实现了对模型的解释。

Explanation via Feature Information

与结构方面的解释类似，这里通过选择与预测结果最相关的部分特征来实现对模型的解释。

这里的特征选择器

可以将部分无关特征移除。联合考虑结构和特征的选，本文最终的优化目标为：

其中，

。这里作者利用了重采样技术

来优化模型。

Multi-instance explanations through graph prototypes

上面都是对单个节点进行解释，但是很多时候我们更关注：如何对一类节点的预测进行解释？本文把这个叫做 multi-instance explanations，其主要包含两步：

1. 给定节点类别 c，作者通过对该类的所有节点的 Embedding 进行平均得到了参考节点

。然后将之前针对单节点解释的优化目标换成

。

2. 聚集邻居矩阵得到 Graph Prototype

，即：同类节点之间共享的图模式。

实验

作者在合成/真实数据集上验证了 GNNExplainer 在多种任务上的解释能力。

下图是在合成数据集上的结果。可以看出相对于 Grad 和 Att，GNNExplainer 可以更好的抽取出与 Ground Truth 相似的结构。

作者随后在真实数据集上，从结构和特征两个方面对图分类和节点分类任务进行了解释。与合成数据集上类似，GNNExplainer 可以更好抽取出于 Ground Truth 相似的的结构。即使 Ground Truth 存在多个复杂结构的时候，GNNExplainer 依然可以抽取出最具有解释性的结构。

除了从结构的角度对 GNN 进行解释之外，GNNExplainer 也可以抽取出最重要的特征来实现更好的解释。从下图可以看出，在 molecule 中含有多种原子中，有部分原子对预测 mutagenicity 有重要作用，而 GNNExplainer 可以非常好的识别出来。Grad 的方法一定程度上可以识别特征的重要性，但是不够明确。