ICML  2022 | Efficient Higher-order Subgraph Attribution via Message Passing

文章信息

「来源」：Proceedings of the 39th International Conference on Machine Learning（ICML） 2022
「标题」：Efficient Higher-order Subgraph Attribution via Message Passing
「作者」：Ping Xiong, Thomas Schnake, Grégoire Montavon, Klaus-Robert Müller, Shinichi Nakajima
「链接」：https://proceedings.mlr.press/v162/xiong22a.html

内容简介

解释图神经网络 (GNN) 变得越来越重要。高阶解释方案，例如 GNN-LRP（GNN 的逐层相关性传播），成为揭示不同特征如何相互作用从而有助于解释 GNN 的强大工具。GNN-LRP 给出了每层节点之间游走的相关属性，子图属性表示为指数级许多此类行走的总和。本文证明了可以避免这种指数复杂性，能够在线性时间（网络深度）内使用 GNN-LRP 对子图进行属性的新算法。本文的算法是通过属性的消息传递技术派生的，直接计算数量以进行高阶解释。「作者进一步调整高效算法来计算子图属性的泛化，同时考虑相邻图的特征。实验结果表明所提出算法的显着加速，并证明了新颖的广义子图归因方法的高实用性和可扩展性。」

尽管 GNN-LRP 已被证明在解释 GNN 的特征交互方面非常有效，但由于网络深度的指数复杂性，其计算迄今为止仅限于相对较小的图和浅层网络。这种复杂性问题并不是 GNN-LRP 特有的，而是存在于除加性或线性解释之外的一般高阶特征归因方法（Lundberg & Lee, 2017; Samek et al., 2021）。这是因为 N 个输入特征的 L 阶解释方法需要考虑 NL 个不同的特征组合。在提取图特征集合的联合相关性的任务中，即输入数据点中子图的相关性（Schnake et al., 2021; Yuan et al., 2021），并入高阶特征归因是必不可少的，但是如果没有找到一种有效的计算方法来弥补指数复杂性，即使 L 中等大，对于一般情况也是不可行的。

「本文提出了一种新的传播规则，称为子图 GNN-LRP (sGNN-LRP)，它直接计算单个反向传播过程中子图的相关性」。与总结步行相关性的 GNN-LRP 的简单应用相比，计算复杂度相对于网络深度 L 从指数降低到线性（见图 2）。前钩技巧（Schnake et al.，2021 年；Samek et al,，2021 年）允许 sGNN-LRP 的简单、快速且内存密集度较低的实现。这项工作的一个新方面也存在于开发新传播规则的方式中：sGNN-LRP 是作为和积消息传递算法推导出来的，也称为信念传播（Bishop，2006；Pearl，1982），以显式计算定义的目标数量——在给定子图中的所游走的相关性总和。本文通过指出消息传递与马尔可夫链过程的边际概率计算的数学相似性来解释为什么消息传递适用于相关性计算，并通过推导现有的 LRP 规则作为消息传递算法讨论其普遍性。消息传递框架允许轻松地将传播规则调整到另一个目标数量。本文通过推导 sGNN-LRP 的变体来对子图相关性进行广义定义来证明这一好处，该定义考虑了子图外的步行，并根据步行步出子图的次数进行折扣。本文的实验表明，所提出的广义子图相关性在节点排序性能方面定量地改进了 GNN 的解释。

子图属性的高效计算

在解释图上的模型时，理解输入图中子图对模型预测的相关贡献是一个关键挑战。作为一种高阶解释方法，Schnake 等人提出了子图相关性的定义，即子图 内所有行走的相关性得分之和，即

在这里，稍微有点滥用符号，作者用 表示行走 停留在 内，即，对于所有 有。上式求和作者称其为 GNN-LRP 用于子图归因的简单应用 (Naive GNN-LRP)，在指数级多的 步数上仅限于最先进的 GNN 的小子图（节点或边），因为它们通常层次很深。

LRP 作为消息传递

作者将部分游走 的相关性定义为从第 层到第 层经过指定节点的所有游走的相关性之和，即:

及其神经元级对应项 条目 ,其 是部分游走的相关性，该部分游走限制为在第 层由 指定的特定神经元。作者用 表示部分游走在子图中，即，对于 , ，。并通过 计算任何节点的部分游走的相关性总和。

GNN 可以展开为前馈神经网络 (FFNN)，如下图（b）：基于展开的网络，考虑一个虚拟随机系统，其中一个粒子在时间 时存在于第 层，在时间 时停留在第 层，并在时间到达输入层。在每一层，粒子随机选择特定节点中的特定神经元。然后，它的轨迹可以表示为 ，其中 指定每一层神经元的选择。假设第 层节点-神经元对的选择概率仅取决于第 层的选择。那么联合概率可以写为:

上图(c)是一个简单的马尔可夫链。如果正式假设 并且 ，则联合分布与神经元级行走的相关性相吻合，行走不仅指定节点，还指定每一层节点内部的神经元：

重要的是，相关性与马尔可夫链的联合分布具有相同的可分解结构。因此可以使用 sum-product 算法——它允许对马尔可夫链的各种边际分布进行有效计算——来计算需要对不同游走集求和的相关性。

实验分析

计算效率评估

本文展示了 sGNN-LRP 相对于 Naive GNN-LRP (Schnake et al., 2021) 的计算优势，作为不同尺度模型和子图大小的基线。实验在具有 8GB 内存的 Xeon E5-2620 CPU 上进行。下图显示了 BA-2motif 上子图属性的计算时间，分别作为 (a) 网络深度 和 (b) 子图大小 的函数。作者观察到 Naive GNN-LRP 的 (a) 指数和 (b) 三次 () 复杂度 。本文提出的复杂度为 的 sGNNLRP 速度要快得多。下表总结了各种 GNN 和数据集的计算时间。报告的计算时间是每个数据集中随机选择的 50 个样本的三次试验的平均值。如果发生内存不足错误或计算未在 360 秒内完成将报告“失败”。再次从表中观察到 sGNN-LRP 的显著计算增益。

广义子图归因的节点排序性能

下图显示了 AUAC 和 AUPC 及其对折扣参数 α 的依赖性。由于 AUAC 和 AUPC 在正样本和负样本之间存在很大差异，因此作者将它们分别绘制。推测这是由于模型对正样本和负样本的预测能力不同。sGNN-LRP 的（红色）曲线暗示子图属性的原始定义，即 α = 0，并不总是最优的，调整 α 可以提高节点排序性能。这不仅适用于修剪任务，也适用于激活任务。

总结

图神经网络的逐层相关性传播 (GNN-LRP) 是 GNN 的一种高阶可解释性方法，它在游走级别提供 GNN 模型的属性。具体来说，它通过对给定子图中的游走求和来支持子图级别的归因，但是它存在指数复杂性，因此在应用中存在计算限制。在本文中，作者通过提出直接计算子图 GNN-LRP 属性的多项式时间算法 (sGNN-LRP) 克服了这个问题。值得注意的是，作者对 sGNN-LRP 的开发是通过一种新颖的程序进行的：与以前的工作不同，作者通过首先定义要计算的目标数量然后导出传播规则作为消息传递算法来开发 sGNN-LRP。这种新颖的程序是通用的，重新发现了许多现有的 LRP 规则，因此有望促进新的 LRP 方法的未来发展。作者通过推导另一个 LRP 规则来计算考虑部分外部游走的子图相关性的广义定义，证明了该过程的实用性。实验结果表明，本文提出的 sGNN-LRP 明显快于 GNNLRP 的应用，并且广义子图相关性定义可以在子图级别更稳健地归因 GNN。

未来的研究将解决新算法的广泛应用，因为现在新的“更深入”的见解（体现在更长的步行或更深的 GNN 中）对于具有大量高阶和长程非线性相互作用的学习问题已经成为可能。除了在科学领域的应用之外，作者认为新的高效 GNN-LRP 算法对 NLP 应用很有前景，其中评估更深层次的高阶交互可能有助于评估 SOTA 系统的可信度、公平性和无偏性。