[NeurIPS2020] 图神经网络的概率图模型解释器

今天解读的论文发表在 NeurIPS2020，它从全新的角度打开GNN黑箱模型。从贝叶斯学派的代表方法——概率图模型的角度对图神经网络加以解释。它的强大之处在于生成的解释具有丰富的统计信息，能够以条件概率的形式自然的表达出节点之间的依赖关系。

• 论文标题：PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks
• 论文地址：https://arxiv.org/pdf/2010.05788.pdf

0.摘要

在图神经网络（GNNs）中，图结构被纳入到节点表示学习过程中。这种复杂的结构使得解释 GNNs 的预测变得更具挑战性。在本文中，作者提出了PGM-Explainer，一个针对 GNNs 的概率图模型(PGM) 的模型无关解释器。给定一个要解释的预测，PGM-Explainer 能够识别关键的图组件，并以近似于该预测的概率图模型的形式生成一个解释。与现有的 GNNs 解释器不同(解释器是从一组解释特征的线性函数中得出的)，PGM-Explainer 能够以条件概率的形式证明被解释特征的依赖性。论文的理论分析表明，PGM-Explainer 生成的概率图模型包括了目标预测的马尔科夫毯，即包括了其所有的统计信息。此外，PGM- Explainer 返回的解释包含了完美 map 中相同的独立性声明。论文在合成数据集和真实数据集上的实验表明，PGM-Explainer 在许多基准任务中实现了比现有解释器更好的性能。

1. Introduction

本文的目标是解释 GNN 为什么会做出相应的预测，明确图结构数据中哪一部分导致了预测结果。整体流程是：1）通过多次扰动原始图数据生成新的数据，即采样数据；2）对采样数据进行变量选择，逐步简化问题，得到一组重要的变量；3）对过滤后的数据进行结构学习，获得GNN的概率图模型解释。

GNN 解释性问题的必要性

随着GNN领域的发展，理解GNN为什么做出这样的预测变得更加重要。原因如下：(i) 它能提高模型的透明度，增加对模型的信任。(ii)关于模型行为的知识有助于识别系统可能失败的场景。(iii)由于公平和隐私的原因，知道一个模型的决策是否有偏差是至关重要的，了解模型的决策有助于我们在部署模型之前发现这些偏差。

本文的贡献

• 本文提出了一个针对 GNNs 的概率图形模型的模型无关解释器，称为 PGM-Explainer。在 PGM-Explainer中，用一个近似于GNN预测的可解释贝叶斯网络对 GNN 预测加以解释。由于贝叶斯网络不依赖于被解释特征的线性独立假设，因此 PGM-Explainer 能够说明被解释特征之间的依赖性，并为 GNN 的预测提供比加性特征归因方法更深入的解释。
• 本文的理论分析表明，如果存在一个通过扰动 GNN 的输入而生成采样数据的完美映射，PGM-Explainer 生成的贝叶斯网络总是包括目标预测的马尔科夫毯。这意味着生成的概率图模型包含了完美映射中编码的被解释预测的所有统计信息。
• PGM-Explainer 在节点分类和图分类任务上都获得比较好的解释预测结果。在基于ground-truth评估模型的基础之上，还通过人类主观测试进行了评估。

2. 预备知识

符号表示

给定一个 GNN 模型

，

是一个需要解释的预测，此时

是模型的所有可能的输入图的集合，

是分类器的空间。在节点分类任务中，

是图

的所有节点预测的向量，其中

是目标预测(即本文中需要被解释的预测)；在图分类任务中，

是在图

上的预测，简单的将

写成

。

在 GNN 中，每一个输入图

，图的每一个节点上有

个特征，将维度为

的特征矩阵

和维度为

邻接矩阵

输入到模型

中 。具体来说，允许解释器通过对模型

进行多次查询来观察不同的预测；但不允许基于模型参数的反向传播和类似操作。当我们将一个图的组成部分，例如一个节点

与一个随机变量相关联时，使用粗体符号，如

，以强调它们之间的区别。

ps：随机变量是指变量的值无法预先确定仅以一定的可能性(概率)取值的量， 因此这里粗体

表示节点状态的随机性。

解释模型

对某一个预测

的解释

通常从一组可能的解释中抽取，称为可解释域

。对于解释域

的选取，可以选择图

的边子集、特征矩阵

的实例子集。本文采用了[17]中提出的神经网络的解释模型框架，并认为

是一个可解释模型家族。在这个解释模型中，给定一个目标函数

，为每个解释分配一个分数，生成的解释是以下优化问题的解：

为了促进得到一个简洁的解

，解释器可能会对式子(1)引入一些约束条件。作者使用一个一般性条件

，其中

来表示这些约束条件。例如，可以通过将

设置为具有有限个数自由参数的模型集来鼓励解释器模型

更加简洁。

小结：解释的获取过程就是在解释域中选择一个最优解释使得目标函数得分最大化。

2.3 概率图模型作为 GNN 的解释域

这一部分主要介绍概率图模型的特点，以及为什么将其用于作为GNN的解释器。

选择一个合适的解释域

对于解释器的质量至关重要。需要对解释域

的复杂性的权衡，一方面，

必须足够复杂，并且能够解释目标预测。另一方面，解释也需要是简洁的，以便用户可以理解得到的解释。为了使每个解释器

都能够解释预测

，解释器

的行为必须与预测函数

的行为相似。因此为了解释 GNNs，必须选择一个解释域

，使其包含的解释模型与 GNN 预测过程的行为相似。

概率图形模型

概率图模型（Probabilistic Graphical Models，PGMs）是利用基于图的表示方法对多维空间上的复杂分布进行编码的统计模型[28]。一般来说，一个分布的概率图能够以因子化的形式紧凑地表示其分布状态。得到分布的 PGM 不仅可以将分布简洁地写下来，还可以对那些底层随机变量的依赖关系进行简单的解释。

由于我们的解释目标是一个复杂的函数

，在输入特征之间具有很高的依赖性，用线性函数来逼近预测过程

可能会导致糟糕的结果。相比之下，PGM 编码了丰富的图组件信息集合，可以潜在地支持我们分析每个组件对被检变量的贡献。例如，PGM能够告诉我们，某些被解释的特征只有在一些其它特征存在的情况下才能决定目标预测。这类信息显然不能从线性模型中获得。

贝叶斯网络

贝叶斯网络[29]是一种通过有向无环图表示变量间条件依赖关系的概率图模型。给定采样数据搜索贝叶斯网络的高效算法(即结构学习)被广泛研究[28，30]。因此，给定需要解释的目标预测函数

，本文提出的 PGM-Explainer 是以下优化过程的最优贝叶斯网络

：

其中

是所有贝叶斯网络的集合。

是贝叶斯网络

中随机变量的集合，

是目标预测

所对应的随机变量，在优化(2)中，第一个约束条件保证

中的变量数受给定常数

的约束，以促进解更加简洁，第二个约束条件保证目标预测包含在解释中。

no-child 约束

是贝叶斯网络

中节点

(随机变量) 的子节点，引入这个约束是因为目标变量

在概率图模型解释中更可能是一个叶子节点。该约束的作用：1）更高效地回答目标变量的条件概率查询。2）得到的概率图模型更加直观。例如，在贝叶斯网络中，同一个子节点的父母节点会直接影响彼此的分布，即使它的之间可能没有边连接。这种额外的约束使得我们在解释目标变量时可以避免歧义性。

3. PGM-Explainer

GNN 对一个节点进行角色预测时，目标节点周围的不同节点(特征)会贡献不同的力量，本文用概率图模型的形式直观的表达出不同特征的贡献程度，以及它们之间的交互关系，即特征之间的依赖关系。概率图模型的直观优点是能够以条件概率的值量化节点之间的交互关系。

Fig 1中演示了一个 PGM 解释的例子。作者采用了[24]的测试方法，其中输入图是 Barabási-Albert(BA) 图组合而成(一组 motifs 和一些随机边)。如Fig 1(a) 中不同颜色所示，根据节点的角色将它们分成四类。一个 motif 中的某一节点预测的解释的 ground-truth 是该motif 中的所有节点。在本例中，解释的目标是Fig 1(b) 中节点E的角色 "紫色"。PGM-Explainer 能够识别 motif 中的所有节点，并构建一个近似于目标预测的概率图模型（Fig 1(c)）。与现有的解释器不同的是，PGM-Explainer 提供了关于图中各个组成成分在条件概率方面的贡献的统计信息。例如，在不知道E的任何邻域信息的情况下，PGM 解释近似预测E为 "紫色 "的概率为47.2%。如果 PGM 知道对节点A的预测及其实现，预测E为 "紫色 "的概率就会增加到65.8%。这些信息不仅可以帮助用户评估每个解释特征对目标预测的贡献，还可以直观地了解它们在构成该预测时的交互作用。

PGM-Explainer 的重要组件

fig2

给定一个输入图数据和一个待解释的预测。在数据生成步骤，PGM-Explainer 扰动原始图，记录 GNN 在这些图上的预测，称为采样数据(即生成、预处理和记录一组待解释的预测的输入输出对)。变量选择步骤从采样的数据中剔除不重要的变量作为过滤后的数据，以改善运行时间，促进解释更加简洁。最后将上一步过滤后的数据作为输入，经过结构学习生成 PGM 解释。

3.1 Data Generation

PGM-Explainer 中数据生成步骤的目标是从目标函数

中生成一组采样数据

。在后续步骤中，PGM 将从这些采样数据

中学习。由于解释器的目的是捕捉预测函数

的行为，特别是在输入图

的邻域，PGM-Explainer 首先对输入图

的一些特征进行扰动，得到一组扰动样本。具体方法是：固定一个参数

，代表每个节点中特征被扰动的概率。对于

中的每个节点

，引入一个随机变量

，表示节点

上的特征是否受到扰动。由于我们希望被扰动的图接近于原始图

，所以扰动方案可能会根据应用的不同而变化，作者实现了不同的扰动算法；但本文使用的方案是简单地将节点特征设置为所有节点中的平均值。对于

的每一个实现(即每一次不同的扰动)，都会得到一个induced 图

，然后通过将

喂入GNN，得到 induced 图上的预测

。

在节点分类任务中，对于每一次扰动，节点变量

的实现都会被记录到采样数据

中，其中

是表示扰动后的预测

是否与原始预测

有显著差异的函数。直观地说，节点变量

既编码了节点

的特征对图的预测的影响，也编码了图的整体变化对节点

预测的影响，在 PGM-Explainer 的实现中，

和

以 二进制值存储，因此节点变量

的域仅仅用2 bits来实现。如果 GNN 有

层，那么对

的预测只能受到

的

跳邻居的影响，解释器只需要检查

的

跳邻居。因此，对于每一个实现(扰动)

，PGM-Explainer 只记录

的

，其中

是节点

在

中的

跳邻居，在对

进行

次采样(扰动)后，PGM-Explainer 将得到一个尺寸为

的数据表

，其中每个条目

是节点随机变量

的第

次采样。

即扰动n次，获得n条采样数据，每一条数据由其

跳邻居的状态决定。

对于图分类任务，设置节点变量

，并在随机变量集中引入一个额外的目标变量

，即记录扰动后的预测是否与原始预测具有显著差异。此外，我们设置邻域集

为

(即图中所有的节点)，因为输入图上的所有节点都可以影响图的预测。因此，在这种情况下，得到的数据表

的尺寸为

。

3.2 Variables Selections

从数据表

中学习概率图模型

的任务称为结构学习。然而从采样数据中寻找一个最优的概率图模型是很难的。对于一个典型的 GNN 来说，节点

的

跳邻居集合

可能包含数千个节点，搜索一个最优的贝叶斯网络花销非常大。因此需要进一步修剪结构学习算法所要考察的变量集。为了减少数据表

中的变量数量，需要确定哪些变量是重要的，并避免消除它们。那么选择重要变量的原则是什么呢？

1. 简化问题：减少随机变量的数目，从节点的L跳邻居，缩减为节点的马尔科夫毯，认为马尔可夫毯中能够包含目标变量的全部统计信息。

PGM-Explainer 认为对目标变量

重要的其它变量存在于

的 Markov-blanket 中。根据定义，在概率图模型

中，

的Markov-blanket 表示为

，是最小的变量集合，这样给定 Markov-blanket 中所有变量的实现，

条件地独立于

中所有其他变量。因此，在假设 中节点

的

跳邻居集合

存在随机变量分布的完美映射概率图模型

的前提下，分析

可以得到与全部邻居节点

中相同的

统计信息。因此不需要在节点

的

跳邻居集合

中寻找最优概率图模型

，计算过程可以反过来：

1）确定目标变量的马尔科夫毯

；

2）计算

上的概率图模型

，作为对

的解释。

由于Markov-blanket 的特性，

和

中

的统计信息是相同的。

2. 问题再次被简化：不需要准确的得到目标变量的马尔可夫毯，只需获得的集合包含目标变量马尔可夫毯。

马尔科夫毯

可以通过Grow-Shrink(GS)算法获得[32]。但是GS中条件独立检验的数量将达到随机变量数量的指数级。为了生成 GNN 预测的解释，解释器不需要准确知道

。事实上，知道任何包含

的集合，就足以使生成的概率图模型包含目标预测的所有统计信息。在 PGM-Explainer中，可以找到

的一个小的子集

，确保其包含目标变量的马尔科夫毯

。

定理1给出：子集

的定义和计算方式、以及如何保证

：

基于 Theorem 1，从原始数据表

中构建包含变量

的马尔科夫毯的子集

是非常容易的，PGM-Explainer 首先计算

独立性检验来构建

之后通过组合

中所有的元素构建

，基于约束(3)的 no-child 约束，我们可以通过处理比

更小的集合，并且令其包含

。

定理2给出：获得比

更小的随机变量集合的方式：

基于定理2，我们可以使用

次依赖性检验，学习到

。

给定

，解释器可以在

的基础上学习PGM，而不是在原始的

个随机变量上学习 PGM。要强调的是，PGM-Explainer的定理1和定理2中的

的构造都只使用了pairwise 依赖性检验，而不是像传统算法求解Markov-blankets那样的条件依赖性检验。因为条件依赖性检验对

个二元变量的就需要

次依赖性检验。如果其中任何一个依赖性检验断言两个变量的分布是不同的，则宣布两个变量具有相互依赖关系。当数据样本数量有限时，随着条件集合大小的增加，将错误变量纳入Markov-blanket 的概率也迅速增加[32]。此外，仅使用依赖性检验，可以计算 PGM 中所有节点

的

。因此，对于节点分类任务，PGM-Explainer 能够同时为许多目标预测生成批量解释。

3.3 Structure Learning

PGM-Explainer 的最后一步是从数据表

中学习解释贝叶斯网络

。首先介绍无约束(3)的学习过程，本文使用

分数如下：

是变量

上的数据，

是贝叶斯网络

的维度，

是贝叶斯网络的参数，函数

是

和

之间的 log- likelihood，即

，(4) 中的

是最大化 log- likelihood 时的参数值，它被称为极大似然估计量。基于这个目标函数，PGM-Explainer 可以使用 exhaustive-search 来求解最优 PGM。hill-climbing 算法[33]也能返回良好的局部最优解，且运行时间显著降低。

在PGM-Explainer中，我们选择了

得分作为目标函数，因为这个目标被证明与数据是一致的[28]。如果随着样本数

，以下两个条件成立，则评分函数是一致的。(i)

使得分最大化；(ii) 所有与

不包含相同独立性集合的结构都具有较低得分。第二个条件也被称为

-equivalent 条件。这两个特性意味着，

得分渐进地优先选择与数据中的依赖性完全匹配的结构。因此，在采样量足够大的情况下，通过最大化

得分得到的贝叶斯网络

能够反映

中变量的依赖性，从而为我们提供模型决策背后的原因。

小结

首先，数据

是通过对输入特征的随机扰动生成的。

然后，PGM-Explainer 使用 pairwise 独立性检验修剪变量的数量。

最后，利用

得分与 hill-climbing学习得到概率图模型。

具有 no-child 约束的结构学习

为了施加 no-child 约束(3)，我们需要修改结构学习步骤，以确保解与数据保持一致。PGM-Explainer不是在

上最大化

得分，而是在上计

算一个最优的概率图模型

，然后，通过迭代的去除变量

，得到

的父集。这可以用类似GS[32]中收缩步骤的方式来完成。之后，PGM-Explainer 将

重新纳入到

中，并从所有父节点添加到

的有向边，得到最终的解释。定理3表明，得到的no-child 约束下的概率图模型

与无约束时得到的概率图模型

是

-equivalence 的。

fig5

4 Experiments

小编提示：对于不同的数据集、不同的任务，GNN 解释任务的 ground-truth(即真实标签)定义的形式是不同的，目前的论文中有些 ground-truth 设计的相对主观，我们可以思考他的定义方式是否严谨和客观，加以改进。

1. 合成数据集上的结果

每个输入图都是一个基础图和一组 motifs 的组合。

ground-truth：与被预测节点处于同一 motif 中的节点。

fig7

2. 真实数据集上的结果

数据集：Bitcoin-Alpha 和 Bitcoin-OTC datasets，以上数据集由3783个账户和5881个账户组成的网络，分别在名为Bitcoin-Alpha和Bitcoin-OTC的平台上交易比特币。在每个网络中，成员对其他成员的评分为-10（总不信任）到+10（总信任）。根据这些评分给每个账户贴上值得信任或不值得信任的标签。

ground-truth：没有对目标节点进行评价或对目标进行负面评价的账户都被算作 "错误账户"。

3.人类主观测试结果

数据集：MNIST SuperPixel-Graph，其中每个样本都是对应于手写数字MNIST数据集中图像样本的图结构数据。在这个数据集中，原始 MNIST 图像使用super-pixels转换为图数据，super-pixels代表图像中强度均匀的小区域。在一个给定的图中，每个节点代表原始图像中的一个 super-pixels，而节点的特征是super-pixels的强度和位置。没有 ground-truth 的解释，采用人主观测试来评价解释器的结果。

fig9

图5(a)给出了两个解释的例子，红框内是每种解释方法生成的解释节点；可以看出 PGM 给出的解释节点和 superpixel 最匹配；

图5(b)是10个用户根据他们主观意识，评估红框内节点对 GNN 预测的重要程度，对每一解释给出0-10之间的分数，可以看出PGM方法的得分最高，即生成的解释节点比其他解释方法更直观。

5. Conclusion

本文提出了 PGM-Explainer，该方法能以可理解的方式解释任何 GNN 模型的预测。通过利用图模型近似于目标预测，PGM-Explainer 能捕获被解释特征对GNN预测的非线性贡献。虽然本文只采用贝叶斯网络作为可解释的模型，但 PGM-Explainer 公式也支持其他图模型的探索，如马尔科夫网络和依赖性网络。对于未来的研究，作者希望分析不同目标函数和结构学习方法对解释器质量和运行时间的影响。

参考文献

• [24] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec, “GNNexplainer: Generating explanations for graph neural networks,” in Advances in Neural Information Processing Systems 32, 2019, pp. 9244–9255.
• [28] D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning. The MIT Press, 2009.
• [29] J. Pearl, “Chapter 3 - markov and bayesian networks: Two graphical representations of proba- bilistic knowledge,” in Probabilistic Reasoning in Intelligent Systems, 1988, pp. 77 – 141.
• [30] M. Scanagatta, A. Salmerón, and F. Stella, “A survey on bayesian network structure learning from data,” in Progress in Artificial Intelligence 8, 2019, p. 425–439.
• [32] D. Margaritis and S. Thrun, “Bayesian network induction via local neighborhoods,” in Advances in Neural Information Processing Systems 12, 2000, pp. 505–511.