AAAI 2022 | ProtGNN：自解释图神经网络络

会员服务 ·

AAAI 2022 | ProtGNN：自解释图神经网络络

2022 年 8 月 22 日 PaperWeekly

作者 | 庄双双

单位 | 南京邮电大学

来源 | MIND Laboratory

论文标题：

ProtGNN: Towards Self-Explaining Graph Neural Networks

收录来源：

AAAI 2022

论文来源：

https://arxiv.org/abs/2112.00911

论文介绍

尽管最近在图神经网络 (GNNs) 方面取得了进展，但解释图神经网络的预测仍然具有挑战性。现有的解释方法主要集中在事后解释上，其中使用另一个解释模型为一个训练过的 GNN 提供解释。事后方法未能揭示 GNN 的原始推理过程，这一事实提出了构建具有内置可解释性的 GNN 的需要。

在这项工作中，作者提出了原型图神经网络 (ProtGNN)，它将原型学习与 GNN 结合起来，为 GNN 的解释提供了一个新的视角。在 ProtGNN 中，解释自然来源于基于案例的推理过程，实际上在分类过程中使用。ProtGNN 的预测是通过将输入与潜在空间中的一些学习原型进行比较而得到的。

此外，为了更好的可解释性和更高的效率，作者引入了一个新的条件子图采样模块来指示输入图的哪一部分与 ProtGNN+ 中的每个原型最相似。最后，作者在广泛的数据集上评估了模型，并进行了具体的案例研究。广泛的结果表明，ProtGNN 和 ProtGNN+ 可以提供内在的可解释性，同时实现与不可解释性的对等对象相当的性能。

论文方法

作者利用原型学习的概念来构建具有内置可解释性的 GNN（即自我解释的 GNN）。与事后解释方法相比，自我解释 GNN 所产生的解释实际上是在分类过程中使用的，而不是在分类后产生的。基于原型学习构建自我解释的 GNN 带来了独特的挑战。首先，边缘的离散性使得图形原型的投影和可视化变得困难。其次，图结构的组合性质使得很难建立高效和高精度的自解释模型。文中为解决上述挑战，并提出了原型图神经网络 (ProtGNN)，这为 GNN 的解释提供了一个新的视角。

ProtGNN/ProtGNN+ 的整体架构如下：

2.1 ProtGNN Architecture

模型主要由三个核心模块构成：GNN Encoder，Prototype Layer 和 Fully Connected Layer。

GNN Encoder：给定输入图，图编码层 f 将映射为固定长度的图嵌入 h。

Prototype Layer：在原型层中，模型为每个类分配一个预先确定的原型数 m。对于输入图的嵌入向量 h，计算 h 与原型之间的相似性分数：

其中，为某一类别的第 k 个原型嵌入，设置为一较小值 (e.g., 1e-4) 以保证结果始终大于 0。

Fully Connected Layer：基于原型层得到的相似性分数，全连接层过 Softmax 函数计算每个类的输出概率。

2.2 Learning Objective

模型的目标是学习一个具有准确性和内在可解释性的 ProtGNN。为了提高准确性，作者在训练数据集上采用交叉熵损失函数：

为了更好的可解释性，作者在构建可解释性的原型时考虑了 3 个约束条件：

1. 首先，集群成本 (Clst) 每个图的嵌入至少应该是 c 输给一个自己类的原型：

2. 其次，分离成本 (Sep) 每个图的嵌入都应该远离所属类的原型：

3. 最后，多样性损失 (Div) 来使学习原型的多样性，避免原型之间过于接近：

综上所述，最终的目标函数是：

其中，、和是控制损失权重的超参数。是属于类的原型。为设置的余弦相似度阈值。

2.3 Prototype Projection

学习到的原型是不能直接解释的嵌入向量。为了更好地解释和可视化，作者设计了一个在训练阶段执行的投影程序。具体来说，让每个原型转移到与的同一类的最近的潜在训练子图上，这样就可以在概念上将每个原型等同于一个子图。

在图形原型投影中，作者使用蒙特卡罗树搜索算法 (MCTS) (Silveretal.2017) 作为搜索算法来指导子图探索（见图 2）。

2.4 Conditional Subgraph Sampling module

作者进一步提出了一个新的条件子图采样模块的 ProtGNN+，以提供更好的解释在 ProtGNN+ 中，不仅显示了与原型的相似度分数，而且还确定了作为推理过程的一部分，输入图的哪一部分与每个原型最相似。

子图采样模块为每个原型输出不同的子图嵌入。随着图大小的时间复杂度呈指数增长,并行化和泛化的难度使 MCTS 算法成为一个不可取的选择。而是提出一种参数化方法进行子图搜索。

形式上，让是指示节点 i 和 j 之间的边是否被选择的二进制变量。的矩阵记为。为了提高效率和可推广性，作者假设解释图为随机图，采用深度神经网络来学习：

其中，为函数，MLP为参数的多层感知器，是连接操作。和是从 GNN 编码器中获得的节点嵌入，它编码的特征以及节点邻域的结构信息。然后子图搜索的目标函数为：

其中，是预算正则化的权重。在实验中作者采用随机梯度下降法对目标函数进行了优化。

2.5.2 Training Procedures

作者采用梯度下降法来优化等式中的目标函数，每隔几个训练 epoch 执行一次原型投影步骤。

实验结果

将 ProtGNN / ProtGNN+ 模型与三种不同的 GNN 评估。

结果显示，ProtGNN 和 ProtGNN+ 实现了与相应的原始 GNN 模型相当的分类性能。

对于 MUTAG 和 Graph-SST2 案例研究：

结果显示，ProtGNN 和 ProtGNN+ 能够准确可视化原型并识别出相似子图，具有较好的内在可解释性。

t-SNE 上的可视化：

图中可以观察到原型可以占据图嵌入的中心，这验证了原型学习的有效性。

总结

虽然人们已经做出了广泛的努力来从不同的角度解释 GNN，但现有的方法都不能为 GNN 提供内置的解释。在本文中，作者提出了 ProtGNN/ProtGNN+，它为 GNN 的解释提供了一个新的视角。ProtGNN 的预测是通过将输入与原型层中的一些学习原型进行比较来获得的。为了更好的可解释性和更高的效率，提出了一种新的条件子图采样模块来指示与原型最相似的子图。大量的实验结果表明，作者的方法可以提供人类可接受的分类精度、时间复杂度和人类可理解的推理过程。

更多阅读