点击下方 “ PaperEveryday ”，每天获得顶刊论文解读
PAGE: Prototype-Based Model-Level Explanations fo- Graph Neural Networks 题目：PAGE：图神经网络的基于原型的模型级解释 作者：Yong-Min Shin; Sun-Woo Kim; Won-Yong Shin
摘要 图神经网络（GNNs）作为一种强大的框架，正在改变图表示学习，吸引了显著的关注。对GNN模型的解释需求也在不断增加。尽管已经开发了各种GNN解释方法，但大多数研究都集中在实例级解释上，这些解释是为给定的图实例量身定制的。在我们的研究中，我们提出了一种新颖的模型级GNN解释方法，即基于原型的GNN解释器（PAGE），它通过发现人类可解释的原型图来解释图分类中底层GNN模型学到了什么。我们的方法为给定的类别产生解释，因此能够提供比实例级解释更简洁、更全面的解释。首先，PAGE在图级embedding空间上对类区分输入图的embedding进行聚类后选择它们。然后，PAGE通过迭代搜索高匹配节点对来发现共同子图模式，使用节点级embedding通过原型评分函数，从而产生我们的解释原型图。使用六个图分类数据集，我们证明了PAGE在定性和定量上都优于最先进的模型级解释方法。我们通过展示PAGE与实例级解释方法之间的关系、PAGE对输入数据稀缺环境的鲁棒性，以及PAGE中提出的原型评分函数的计算效率，进行了系统的实验研究。
关键词 embedding
模型级解释
图分类
图神经网络（GNN）
原型图
I. 引言 A. 背景和动机 图是一种普遍的方式来组织复杂现实世界数据的多样化集合，如社交网络和分子结构。图神经网络（GNNs）已被广泛研究，作为从底层图中提取有用特征的强大手段，同时执行各种与图相关的下游任务。GNNs通过消息传递来有效学习节点和图的表示，同时采用神经网络作为基本构建块来学习图结构和节点特征（属性）。
尽管GNN模型具有强大的表达能力，但它们缺乏透明度，因为它们不为各种下游任务的GNN预测提供任何人类可解释的解释。因此，提高GNN模型的可解释性已成为近期的研究兴趣，因为它能够彻底理解模型的行为以及信任和透明度。最近尝试解释GNN模型的尝试大多强调了在给定输入图中突出显示对底层GNN模型预测贡献最大的子图结构。这些所谓的GNN的实例级解释方法为给定的图实例提供了深入分析。
然而，实例级GNN解释并没有揭示底层模型在训练过程中已经训练过的整个数据集的一般行为，该数据集由许多图组成。在某些现实世界场景中，展示GNN模型决策过程的解释确实有益。例如，当在现实世界环境中使用黑盒GNN模型时，模型可能会遇到在训练期间未观察到的各种实例。在这种情况下，理解GNN模型的一般决策过程将有助于预测GNN在新环境中的行为。这激发了我们研究模型级解释，旨在解释GNN在模型级别。
图1展示了实例级解释方法与模型级解释方法如何不同，以便理解预训练GNN模型的一般行为。
对于实例级解释，为每个图实例提供解释。因此，要理解整个数据集上的模型，我们需要进一步的步骤，例如提取实例级解释中的共同模式，并对提取的模式进行聚合。然而，模型级解释方法直接通过呈现它从整个数据集中学到的内容来捕捉预训练GNN模型的行为，这被总结为人类可解释的子图的形式。
作为一个代表性的GNN模型级解释方法，XGNN通过强化学习训练了一个图生成器。由于XGNN需要领域特定的知识来手动设计奖励函数，除非根据不同类型的数据集提供精确的奖励，否则它通常无法产生可靠的解释。尽管存在许多实际挑战，但为GNN设计模型级解释方法仍然是一个未被充分探索的领域。
B. 主要贡献 在本文中，我们介绍了基于原型的GNN解释器（PAGE），这是一种新颖的事后模型级解释方法，它通过发现人类可解释的原型图来解释图分类中底层GNN模型学到了什么。GNN模型的行为通过识别模型为给定目标类别学习到的图模式来表示。我们根据以下洞察指导我们的问题制定：我们应该寻找的共同图模式实际上就在训练集中。因此，我们使用训练集以及预训练GNN模型生成的表示作为PAGE的输入，以便准确地捕捉模型学到了什么。图1展示了一个示例，其中PAGE正确地从分子集合中识别出苯结构作为结果模型级解释，同时使用预训练GNN模型的节点级和图级embedding作为输入。
我们的目标是根据以下设计原则设计我们的PAGE方法：解释模块本身应该是（a）可解释的，并且（b）不伴随高级学习模型（即，黑盒学习模型）。为此，我们设计了一个两阶段方法，包括1）在图级embedding空间上对embedding进行聚类和选择，以及2）发现原型图。在第一阶段，我们通过对图级embedding空间进行聚类，然后选择每个群集中中心附近的k个embedding，从训练集中选择类别有区别的图。这个阶段的动机是1）表现出共同子图模式的图级embedding倾向于在图级embedding空间上共定位（这将在第IV节A2中经验验证），以及2）选择的k个图（或等效地，图级embedding）靠近它们所属群的中心可以是群的很好的代表。在第二阶段，作为我们的解释，我们从选定的k个图中发现原型图。然而，将GNN的行为表示为从选定的k个图中精确的子图模式是具有挑战性的，因为这需要在所有可能的k个节点中进行组合搜索，这些节点应该共同体现模型学到了什么。为了指导这个搜索，我们新定义了一个原型评分函数，用于使用节点级embedding向量在k个选定图中的k个节点之间有效计算匹配分数。通过对所有可能的k个节点组合应用该函数，我们迭代地搜索高匹配节点元组，直到我们发现一个子图。值得注意的是，利用两种embedding空间（即，节点级和图级embedding空间）在原型发现中的影响和好处是双重的：1）预训练GNN模型的行为被编码到低维embedding空间的向量表示中，这可以方便地处理，以及2）丰富的属性和拓扑信息可以有效地融合到向量表示中。
为了验证我们PAGE方法的质量和有效性，我们使用各种合成和真实世界数据集进行了全面的实证评估。然而，模型级解释的评估提出了另一个挑战，因为它在文献中尚未被广泛探索。作为我们研究的一个主要贡献，我们为模型级GNN解释设计了系统的评估，总结如下。首先，我们通过可视化解释进行定性评估，这表明PAGE产生了与地面真实解释相似的原型图。其次，我们采用四种性能指标，准确度、密度、一致性和忠实度[15]，并进行修改，进行定量分析，这（a）显示了PAGE优于XGNN[14]，代表性的模型级GNN解释方法，以及（b）与定性评估一致。第三，我们研究了我们的PAGE方法与实例级解释方法之间的关系。为此，我们提出了两个量，包括集中度分数和相对训练增益，并定量评估实例级解释与PAGE发现的原型图的一致程度。第四，我们通过在更困难的设置中可视化结果原型图来分析PAGE的鲁棒性，其中每个训练集由PAGE的输入组成的只有少数可用图；我们证明了合理的地面真实解释仍然可以产生。最后，我们实证验证了我们的原型评分函数的有效性，它成功地近似了计算成本高昂的替代方案。
此外，我们解决了PAGE和XGNN[14]之间的主要区别：1）使用可解释组件而不使用黑盒学习模块，以及2）在应用我们的方法到不同领域时的泛化能力，而不需要领域特定的先验知识。本文的主要技术贡献可以总结为三个方面：- 我们提出了PAGE，一种新颖的图分类模型级GNN解释方法，包括两个阶段，1）聚类和选择图级embedding，以及2）原型发现；- 在PAGE中，我们从理论和实证上证明了图级embedding聚类的使用，并设计了一个新的原型图发现算法来捕捉GNN模型的一般行为；- 通过使用五个图分类数据集进行系统评估，我们全面展示了PAGE的有效性，对不完整数据集的鲁棒性，以及计算效率。
C. 组织和符号 本文的其余部分组织如下。在第二节中，我们介绍了与我们工作相关的先前研究。在第三节中，我们解释了我们研究的方法论，包括基本设置、GNN模型的描述、我们的问题表述，以及我们PAGE方法的概述。第四节描述了所提出方法的技术细节。第五节展示了全面的实验结果。最后，我们在第六节中提供了总结和结论性评论。
III. 方法论 在本节中，我们首先描述我们的问题设置和目标。然后，我们提出了PAGE方法作为GNN的模型级解释的概述。
A. 设置和基本假设 假设我们有一组图 我们将每个图 B. 图分类的GNN模型 在这一部分，我们简要回顾了用于图分类的GNN模型。 首先，我们展示了GNN中消息传递的一般形式[26]，其中我们通过两个函数迭代地更新节点的表示，通过聚合其邻居的表示。具体来说，给定一个图 其中 其次，我们描述如何产生 C. 问题表述 我们研究的目标是提供事后模型级解释，通过发现底层GNN模型在图分类训练期间学到的最具区分性的图模式。为此，我们提出了PAGE，一种新的模型级解释方法，以及人类可解释的原型图。对于给定的类别 注意，模型级解释与实例级解释不同，后者提供有关给定图实例 D. 我们的PAGE方法概述 在这一小部分中，我们解释了我们的方法论以及提出的PAGE方法的概述，该方法包括以下两个阶段：1）通过聚类和选择图级embedding来选择代表给定类别 在我们描述上述每个阶段之前，让我们简要说明与XGNN[14]的主要区别，这是最先进的模型级GNN解释方法。虽然XGNN旨在生成原型图，但PAGE尝试使用底层图 首先，我们通过在图级embedding空间上进行聚类来选择代表给定类别 在这里插入图片描述 其次，我们转向发现原型图（见图2(a)的右半部分）。为了便于解释，我们只关注发现第 IV. PAGE: 提出的方法 在本节中，我们详细阐述PAGE，即我们提出的事后模型级GNN解释方法，用于图分类。 我们首先描述如何对图级embedding进行聚类和选择，以详细选择输入图的子集。我们还提供我们聚类的理论和实证验证。然后，我们介绍如何发现原型图。 A. 图级embedding的聚类和选择（第一阶段） 1) 方法细节 我们假设GNN模型 EM迭代在执行E步骤和M步骤之间交替进行。在E步骤中，我们计算 其中上标 其中 接下来，我们选择每个群集中心的 然后，对于每个群集，我们选择 2) 理论和实证验证 在第IV节A2中，我们旨在通过我们的理论和实证验证来证明PAGE中图级embedding聚类的使用。我们的研究基本上假设包含不同原型的图很可能被映射到图级embedding空间的不同向量表示中，即使它们属于同一类别。为了验证这一主张，我们首先提供了一个理论基础，将GNN与Weisfeiler-Lehman (WL) 核[32]联系起来。然后我们通过可视化基准数据集上的图级embedding来实证验证上述主张。 我们首先描述WL核[32]。它最初通过节点属性为给定图的每个节点着色，并在每一轮迭代中通过考虑每个节点的邻居的颜色来细化节点着色，直到稳定。我们正式通过假设给定图 定理1（Morris等人，2019）：设 从定理1，节点级embedding向量 推论2：假设通过颜色细化为两个图 证明：从定理1，存在一个双射函数 从而得到 从推论2，我们可以期望GNN在区分图（即区分非同构图）方面将表现得像WL核。 接下来，我们通过可视化基准数据集上的图级embedding来实证验证我们的主张，即GNN能够区分包含不同原型的图。 示例1：图3通过可视化BA-house数据集上的图级embedding向量，通过t-SNE[33]展示了这种趋势，该数据集中有多个包含和不包含房屋形状子图的图（参见第V-A节，了解有关BA-house的更多描述）。在这里，我们训练了一个GNN模型来执行图分类任务，该任务对输入图是否包含房屋形状子图（类别1）或不包含（类别0）进行分类。然而，由于类别1中的每个图可能有一个或两个房屋形状子图，我们对进一步研究属于类别1且包含不同数量房屋形状子图的图是否被单独embedding到图级embedding空间感兴趣。尽管GNN模型在训练时并不知道这些原型的存在，我们观察到GNN模型将具有不同原型的输入图embedding到图级embedding空间的远距离簇中（见图3中的红色和蓝色点）。
通过这种实证验证，我们得出结论，GNN确实能够像WL核一样区分具有不同原型的图。 B. 原型发现（第二阶段） 在本节中，我们转向描述我们的原型发现算法
备注1：可以使用替代方法（例如，使用图匹配）来实现我们发现原型图的目标。然而，当我们采用[24]，[25]中的图匹配方法来发现原型图候选时，我们实证发现结果候选者不太可能包含地面真实解释，如果不是完全不认识的。这意味着基于替代方法的原型发现可能需要进行重大修改以获得满意的性能。 1) 初始化（步骤1） 初始化步骤涉及创建 定义1（原型评分函数）：给定一组 我们接下来创建 2) 核心原型搜索模块 对于剩余部分的原型发现阶段，我们希望实现原型发现函数 更具体地说，我们引入了一个搜索预算，表示为变量budget，它决定了我们运行的搜索会话的数量。每个搜索会话由迭代子图搜索（步骤2）和原型检索（步骤3）组成。换句话说，对于给定的budget，我们最多运行budget个会话进行原型搜索。当所有会话的原型搜索结束后，我们选择具有最高输出概率 3) 迭代子图搜索（步骤2） 现在我们描述每个搜索会话中的迭代子图搜索步骤。在这一步中，我们迭代地找到 示例2.如图4所示，在我们的示例中，假设 每个选定的 4) 原型检索（步骤3） 作为下一步，我们能够从每个搜索会话中发现 由于我们运行了budget个搜索会话，我们获得了budget个原型候选。我们通过选择budget个候选中具有最高输出概率 V. 实验评估 在本节中，我们首先描述用于评估的合成和真实世界数据集。我们还介绍了用于比较的基准GNN解释方法。在描述我们的实验设置之后，我们全面评估了PAGE和基准方法的性能。PAGE的源代码已公开提供在线。 A. 数据集 在我们的研究中，使用了两个合成数据集，包括BA-house和BA-grid数据集，以及四个真实世界数据集，包括Solubility, MUTAG, Benzene和MNIST-sp数据集。所有数据集都提供了每个数据集的图分类的地面真实解释（即地面真实原型）以及地面真实标签。每个数据集的主要统计数据总结在表I中。我们描述了数据集的重要特征。
BA-house和BA-grid。受到[5]的启发，我们为图分类生成了新的合成数据集。在这两个数据集中，我们使用Barabási-Albert (BA) 模型作为主干图，并通过附加某些子图模式（或图案）来完成每个图，这些子图模式作为地面真实解释。这两个数据集包含两个类别，其中一个类别包括底层图中的地面真实解释，而另一个类别具有不完整的子图模式。在生成数据集时，我们首先为要生成的图分配类别标签0或1。然后，我们使用BA模型生成一个由5到10个节点组成的主干图。如果分配的类别标签是0，则我们将附加子图模式连接到主干图。否则，我们连接一个不完整的子图模式到主干图。对于BA-house，子图模式是房屋形状的子图，而对于BA-grid，使用网格状子图。在BA-house的情况下，类别0中随机添加了一个或两个房屋形状的子图。每个节点都有一个独热编码的特征向量，指示节点是否属于主干图、图案的头部（即地面真实解释）或图案的身体，这取决于给定图中节点的位置。 Benzene [15]：Benzene数据集包含分子，其中节点和边分别表示原子和化学键。这些图根据分子中是否存在苯结构（即具有六碳环的结构，数据集忽略了氢原子）被划分（标记）为两个不同的类别。每个节点都有相应的独热编码特征向量，代表可能的原子类型，可以是碳、氮、氧、氟、碘、氯和溴中的一种。 MUTAG [34]：MUTAG数据集包含代表分子的图，其中节点代表不同的原子，与Benzene数据集类似。这些图根据它们对细菌的突变效应被划分为两个不同的类别[5]。节点特征是独热编码的向量，代表原子类型，包括碳、氮、氧、氟、碘、氯、溴和氢。在我们的实验中，为了简单起见，忽略了边缘标签。 Solubility [4]：Solubility数据集由具有不同溶解度的真实世界分子组成，其中节点和边分别表示原子及其化学键。在我们的实验中，我们忽略了边缘连接类型。尽管这个数据集最初是作为回归任务设计的，但它被划分为两个类别用于图分类任务。我们将对数溶解度值低于-4的分子标记为0，而将值高于-2的标记为1。刚性碳结构被认为是不溶性地面真实解释，而R-OH化学基团被视为溶解性地面真实解释。每个节点的独热编码特征向量代表原子类型，可以是碳、氮、氧、氟、碘、氯、磷、硫、氢和溴中的一种。 MNIST-sp [35]：MNIST-sp是源自用于图像分类的MNIST数据集的图分类数据集。由于局部像素被处理成每个图像的节点（超像素），图像分类被转换为图分类问题。每个图包含75个节点，边缘根据超像素是否在原始图像中相邻而连接。节点特征包括超像素的中心位置和像素的连续值。因此，我们将连续值归类以离散化它们。像素值根据其原始值被归类为三组：0（完全黑色）、(0, 0.5]（暗）和(0.5, 1]（亮）。位置值通过它们与图像的关联被归类为14×14的均匀网格。 注意，模型级解释方法旨在识别基于每个数据集类别的解释。因此，在所有实验中，模型级解释方法使用包含精确子图模式的类别作为输入，然后尝试检索类别有区别的子图作为原型图。 B. 基准方法 在这一小节中，我们介绍一个用于比较的最先进方法。作为代表性的模型级解释，我们使用XGNN [14]作为我们的基准方法，它通过强化学习训练了一个图生成器，以生成子图模式（即原型图），在最大化底层GNN模型的某种预测的意义上。更具体地说，图生成器被训练为以迭代方式添加边缘。在生成步骤t，生成的图Gt+1被输入到底层GNN以计算奖励函数Rt：Rt = Rt,fGNN(Gt+1) + λ1 ∑m i=1 Rollout(Gt+1) / m + λ2Rt,r,
（5）
其中λ1和λ2是超参数；Rt,fGNN(Gt+1)是底层GNN fGNN的预测类别概率；Rollout(·)是rollout操作[36]；m是执行rollout的次数，Rt,r是基于各种图规则提供领域特定奖励的额外项。 C. 实验设置 我们首先描述GNN模型的设置。我们采用GCN [27]作为广泛使用的GNN架构之一。求和函数被用作读出函数。我们为BA-house和BA-grid数据集使用2个GNN层，对于其他三个数据集使用3个GNN层，除非另有说明。我们将每个隐藏潜在空间的维度设置为32对于所有数据集。我们使用Adam优化器[37]训练GNN模型，学习率为0.001，批量大小为16。对于除MNIST-sp之外的所有五个数据集，我们将每个数据集分割为训练/验证/测试集，比例为90/5/5%。对于MNIST-sp数据集，我们遵循给定的训练/测试拆分，并进一步将训练集拆分为训练/验证集，比例为5:1。训练集用于通过交叉熵损失学习模型参数；验证集用于早期停止，耐心为5个周期。除非另有规定，我们使用G中所有图运行PAGE。我们在表I中报告了测试集上的图分类性能以及数据集。 接下来，我们描述解释方法PAGE和XGNN的设置。在PAGE中，GMM的实现来自scikit-learn Python包[38]。我们将L = 2和k = 3，因为我们发现这样的设置在不同数据集上产生稳定的结果。我们还设置预算，表示搜索会话的数量，为5。此外，我们将衰减率和迭代子图搜索（第二阶段步骤2）中允许的最大迭代次数设置为10和1,000。对于XGNN的实现，我们基本上遵循原始论文[14]中的相同设置来调整超参数。 我们实验中使用的GNN模型和解释方法使用Python 3.8.12、PyTorch 1.11.0、PyTorch Geometric 2.0.4 [39]和Captum 0.5.0 [40]实现，并在配备有Intel Core i7-9700 K 3.60 GHz CPU、32 GB RAM和单个NVIDIA GeForce RTX 3080 GPU的机器上运行。 D. 实验结果 我们的实验旨在回答以下八个关键研究问题（RQs）。 RQ1: PAGE的模型级解释与基准方法在定性上如何评估？ RQ2: PAGE的模型级解释与基准方法在定量上如何评估？ RQ3: 在多次搜索会话中，PAGE何时返回最终原型图？ RQ4: PAGE的解释与实例级解释方法有何关系？ RQ5: PAGE需要多少输入图来进行模型级解释？ RQ6: PAGE中的原型评分函数与简单替代方案相比效果如何？ RQ7: PAGE与基准方法相比在计算复杂度上有多昂贵？ RQ8: 在没有明确地面真实解释的数据集上，PAGE的表现如何？ 模型级解释方法的定性分析（RQ1）：我们通过可视化每个数据集的PAGE和XGNN的解释（即原型图）以及地面真实解释来进行定性评估。如图5所示，我们观察到PAGE发现的解释与地面真实解释在图结构和节点特征（即节点类型）方面具有很高的相似性，而XGNN大多未能产生包含整个地面真实解释的原型。从图5和6中，我们对每个数据集的发现如下：
对于BA-house数据集，PAGE成功返回了我们添加到主干图上的类别区分子图，即房屋形状的子图。然而，XGNN生成的原型只包含部分房屋形状子图。例如，XGNN的结果只包含房屋形状子图的五个节点中的三个，因此解释是不完整的。另一方面，PAGE能够通过返回包含单个或双房屋形状子图的两种类型的原型图来产生更精确的解释。这种精确性主要是因为使用了图级embedding的聚类。 BA-grid数据集的结果与BA-house类似。PAGE返回了大部分网格状子图，而XGNN只恢复了较小部分。 在Benzene数据集的情况下，PAGE正确识别了作为原型图一部分的6个碳原子组成的环状结构，而XGNN没有生成任何碳环。尽管XGNN产生了六个碳原子，但它未能将原子连接成封闭的环状结构。 对于MUTAG数据集，PAGE识别了两种类型的原型图，即碳环和NO2化学基团。然而，XGNN只恢复了NO2，同时生成了较小的分子。 我们分析了Solubility数据集的两个类别的模型级解释。对于类别0（即被分类为不溶性分子的情况），PAGE倾向于返回碳原子，并偶尔添加氢原子；XGNN也产生了大部分由碳原子组成的原型，但包含了大部分非碳原子。与PAGE不同，XGNN未能产生碳环结构。对于类别1（即可溶性分子的情况），PAGE正确识别了所有原型的R-OH化学基团；相比之下，XGNN未能包含R-OH。 最后，我们分析了MNIST-sp数据集类别0的模型级解释。如图6所示，PAGE的解释中可以看到对应于感兴趣类别的数字0，而XGNN在生成充分解释类别0方面存在困难。这表明了PAGE在数据集中发现原型图的好处，而不是像其对应生成它的那样。 模型级解释方法的定量分析（RQ2）：对于定量分析，我们采用了四种性能指标：准确性、密度、一致性和忠实度。 准确性比较原型图g与地面真实解释gT。为此，我们假设我们可以获取连接gT和g的节点/边对应关系（即两个图之间的节点匹配），同时计算g中属于gT一部分的边的数量，这将导致最佳的解释性能。在我们的评估中，我们定义模型级解释的准确性（Acc.）如下： 其中TP(g, gT), FP(g, gT)和FN(g, gT)分别表示在计算g和gT之间相关节点和边的数量时的真实阳性、假阳性和假阴性。 一致性[15]测量解释对不同GNN模型设置的鲁棒性。直观地说，可靠的解释方法应该在相同的任务的不同模型配置下产生稳定的解释。在我们的实验中，我们计算了不同GNN超参数设置下解释（例如，由PAGE检索的原型图）的输出概率的标准差。为此，我们为BA-house和BA-grid数据集生成了25个模型，这些模型具有{4, 8, 16, 32, 64}×{4, 8, 16, 32, 64}隐藏维度配置。对于Benzene、Solubility、MUTAG和MNIST-sp数据集，我们生成了64个模型，具有{4, 8, 16, 32}×{4, 8, 16, 32}×{4, 8, 16, 32}隐藏维度配置。一致性越低，性能越好。 忠实度[15]测量解释方法反映GNN模型行为的程度。按照[15]，我们将模型的测试准确性视为感兴趣的行为，并观察解释的输出概率与GNN的测试准确性之间的关系。在我们的实验中，忠实度通过解释的输出概率pGNN与GNN的测试准确性之间的Kendall's tau系数[41]来测量，这代表了解释反映GNN测试准确性的程度。为此，我们通过从0%到50%以5%的增量破坏训练集中的部分标签，获得了一组导致不同准确性的GNN模型。忠实度越高，性能越好。 表II总结了在六个数据集上对PAGE和XGNN进行的准确性、密度、一致性和忠实度的定量评估。表II(a)显示，无论数据集如何，PAGE始终提供比地面真实解释更准确的解释。表II(b)显示，PAGE产生的解释在大多数情况下倾向于展示较低的密度，这意味着解释相对不那么复杂。在表II(c)中，我们观察到PAGE在所有数据集上（除了MNIST-sp）在不同的隐藏维度配置下提供比XGNN更稳定的解释。从表II(d)中，我们观察到PAGE显然在GNN的测试准确性和输出概率之间展示了正相关，而XGNN则相反，这意味着PAGE能够成功地解释GNN模型对其解释结果的了解。
为了进一步分析PAGE和XGNN的忠实度，我们在图7中可视化了解释的输出概率与GNN的测试准确性之间的散点图，用于测量忠实度。从表II(d)和图7中的有趣观察如下：
在BA-house、BA-grid、Benzene和MNIST-sp之间的PAGE和XGNN之间的不同趋势是明显的。对于Solubility和MUTAG，当标签被破坏时，GNN的测试准确性往往很低，这并不展示输出概率和测试准确性之间的清晰关系。这意味着这两个数据集在这种嘈杂的设置中更难学习。- 总的来说，PAGE和XGNN在忠实度方面的性能差异在合成数据集上变得更加突出。这是因为地面真实解释可以更清晰地与相应类别建立关系，因为合成数据集的噪声较少。- XGNN在某些数据集上显示负Kendall's tau系数。- 这是因为，当GNN模型用高标签破坏率训练时，它基本上作为随机分类器传递，因此无法决定从XGNN生成的解释是否有效。当GNN模型用较少破坏的数据训练时，它现在学习了给定数据集的特征，并将产生低输出概率，如果XGNN的结果不包含完整的地面真实原型。最终，这导致输出概率与GNN的测试准确性之间的负相关。 PAGE中多次搜索会话的影响（RQ3）：除了PAGE的最终原型图外，我们还对分析每个搜索会话计算的输出概率pGNN感兴趣，以了解何时选择了具有最高pGNN的原型候选。图8为所有数据集，当给定预算为5时，可视化了每个会话中发现的子图（即原型候选）的输出概率pGNN的热图。每个案例中被选为最终原型图g(c)l的原型候选突出显示在红色框中。我们希望提出以下观察： 在这里插入图片描述 在大多数情况下，每个搜索会话倾向于返回具有各种pGNN值的原型候选。例如，在MUTAG的Cluster1中，发现的原型候选的pGNN值范围从接近0.4到接近0.8，这忠实地反映了我们设计核心原型搜索模块（见第IV-B2节）的意图。- 第一次搜索会话为7个中的10个案例产生了最终解释（即最终原型图g(c)l）。这种趋势是预期的，因为第一次搜索会话从Yl中的最高匹配分数开始迭代子图搜索（第二阶段步骤2）。- 有些情况下，除了第一次之外的其他搜索会话返回的原型候选被选为最终原型图，从而证明了多次搜索会话的必要性。- 从这些观察中，我们可以看到，会话数量，即预算，不会是决定PAGE性能的关键问题。 PAGE与实例级解释方法的关系（RQ4）：由于大多数关于GNN解释的研究都集中在实例级解释上，我们通过研究PAGE方法与实例级解释方法之间的关系进行了额外分析。具体来说，我们对评估原型图的归因图感兴趣，这表明了它对做出模型决策的重要性。为此，在通过PAGE发现原型图g(c)l之后，我们使用g(c)l作为输入到一个实例级解释方法来获取归因图（也称为显著性图）。这种评估可以被解释为衡量PAGE与实例级解释方法之间的一致性。 对于图Gi = (Vi, Ei, Xi)，一个实例级解释方法以图中的节点v作为输入，并返回其归因分数，表示为Λ(v)，该分数在图中所有节点中归一化。我们在实验中提出了以下两个量。 定义2（集中度分数）：给定原型图g(c)l和地面真实解释g(c)T，我们定义集中度分数α如下： 其中Vg(c)T和Vg(c)l分别是子图g(c)T和g(c)l中节点的集合。集中度分数衡量实例级解释集中在属于地面真实解释g(c)T的节点上的程度。如果没有原型g(c)l中的节点属于g(c)T，则α变为零。α的值越高（介于0和1之间），性能越好。 定义3（相对训练增益）：给定原型图g(c)l的集中度分数α和地面真实解释g(c)T，相对训练增益β定义为 其中α0表示在训练前对相同的原型图g(c)l进行训练的GNN模型计算的集中度分数。 相对训练增益衡量在GNN模型训练后集中度分数的相对增益。β值越高，性能越好。注意，β与忠实度不同，它专注于模型级和实例级解释方法之间的关系。 在我们的实验中，我们采用了以下两个实例级解释方法： 输入×梯度[42]：该方法采用输出相对于输入的梯度，并将其与输入相乘以产生归因图。 GNNExplainer[5]：给定一个输入实例，该方法识别对GNN的预测最有影响力的子图结构和节点特征的小子集。GNNExplainer执行优化任务，以最大化预测和可能子图结构的分布之间的互信息。 表III总结了在BA-house和Benzene数据集上对PAGE和两种实例级解释方法进行的一致性评估，分别针对集中度分数α和相对训练增益β，以及通过测量AUROC来衡量每种实例级解释方法的性能。
为了进一步分析PAGE和两种实例级解释方法之间的关系，我们在图9中可视化了归因分数的热图，其中输入×梯度和GNNExplainer被应用于PAGE输出的原型图。
我们首先分析表III和图9中关于α的定量评估结果。 对于BA-house数据集，输入×梯度和GNNExplainer实现的α值都足够高，这表明绝大多数归因分数被分配给了属于房屋形状子图的节点。换句话说，PAGE和两种实例级解释方法的表现彼此之间非常一致。 对于Benzene数据集，尽管对于GNNExplainer也观察到类似的趋势，但对于输入×梯度，α的值趋于减小。众所周知，基于梯度的归因方法可能经常无法捕捉GNN模型的行为，因为激活函数（如ReLU）在GNN的前馈过程中未被激活时梯度为零[42]。 可以预期看到正值的β，如果PAGE和实例级解释方法的表现彼此之间非常一致。然而，对于Benzene案例，输入×梯度观察到β的负值，这与GNNExplainer在两个数据集上产生正值的β形成对比。 PAGE和GNNExplainer在Benzene上更高的一致性是由于GNNExplainer旨在为图形和GNN模型生成解释，因此可靠地产生结果归因。 上述趋势也反映在表III中的AUROC中，其中输入×梯度的AUROC为零，而GNNExplainer的AUROC为0.8889。请注意，其他三个数据集的结果也显示了与第V-D4节中报告的相似的趋势。 PAGE对可用输入图数量的鲁棒性（RQ5）：我们现在通过可视化结果原型图在更具挑战性的情况下进行定性评估，其中每个数据集由来自训练集的少量可用图组成作为PAGE的输入。这在真实环境中经常发生，因为旨在设计解释方法的用户和组织可能对输入数据的访问受到限制。为了模拟这种情况，我们通过从训练集中随机抽样创建了基数为10的子集（即 |˜G| = 10）。换句话说，子集˜G用于运行PAGE，而GNN模型已经使用G中的整个训练集进行了训练。由于在PAGE的第一阶段中，对少量图˜G进行图级embedding聚类是不可能的，我们简化了PAGE，并在选择了˜G中的k个图而不是kNN之后仅执行了第二阶段。 图10可视化了在BA-house和Benzene数据集的˜G子集上使用k = 3时，简化的PAGE进行五次独立试验时发现的原型图。在BA-house的情况下，如图10(a)所示，我们观察到在五次试验中有四次原型包含完整的单个房屋形状子图，表明核心原型搜索模块即使在不完整的数据集设置中也能够产生地面真实解释。然而，由于缺乏聚类，不包含双房屋形状子图的原型图没有被检索到。因此，简化的PAGE不会产生精确的解释，而是会退回到更简单的解释。在Benzene的情况下，如图10(b)所示，我们观察到在所有五次试验中都包含了碳环结构；由于随机选择的图子集˜G，试验中除了地面真实解释之外的原子数量各不相同。请注意，其他三个数据集的结果也遵循了虽然未在手稿中显示的相似趋势。
PAGE中原型评分函数的有效性（RQ6）：我们验证了我们原型评分函数s在计算效率方面与简单替代方案相比的有效性。我们不是通过某个GNN模型获取一组节点级embedding向量，而是合成地生成并输入它们到函数s中，这足以分析s的有效性。具体来说，我们首先生成每个高斯随机向量wi，均值为零，协方差矩阵为Ib，即wi ∼ N(0b, Ib)，其中0b和Ib分别表示大小为b的零向量和单位矩阵。 在我们的实验中，我们生成了10^3个3元组向量，它们被用作s(v1, v2, v3)的输入。我们将s与以下替代原型评分函数进行比较：sAM(v1, v2, v3) = (vT1 v2 + vT2 v3 + vT3 v1) / 3和sGM(v1, v2, v3) = (vT1 v2 × vT2 v3 × vT3 v1)^1/3，它们分别返回所有可能的embedding向量对之间内积的算术平均值和几何平均值。 我们在表IV中经验性地显示了s、sAM和sGM的平均运行时复杂度。这个实验揭示了sAM和sGM比s更昂贵的计算成本，这与我们在备注2中的分析一致。此外，图11可视化了所提出的s与每个简单替代方案（即sAM或sGM）的结果，我们观察到两者之间的高相关性，其中皮尔逊相关系数ρ在两种情况下都超过0.75。这表明我们的原型评分函数s是计算所有可能的embedding对之间内积的良好近似。
PAGE的效率（RQ7）：我们验证了PAGE在效率方面的优越性。为此，我们首先从理论上分析了它的计算复杂度。在第一阶段，GMM的复杂度为O(nkb^3)[43]，kNN选择涉及对每个群集的排序，导致O(nk(b^3 + log n))，其中b是节点级embedding向量的维度。在第二阶段，由于计算Yl和运行每个搜索会话高度可并行化，计算基本上取决于预定义的最大允许迭代次数Nmax和Yl中非零元素的数量Nnnz。因此，PAGE的第二阶段产生的复杂度为O(NmaxNnnz log Nnnz)。 因此，PAGE的总计算复杂度由O(nk(b^3 + log n) + NmaxNnnz log Nnnz)给出。 此外，我们使用两个数据集，BA-house和Benzene，来测量PAGE和XGNN的运行时复杂度。表V显示了每种模型级GNN解释方法在10次独立试验中的运行时复杂度（均值±标准差）。结果证明了PAGE在不同数据集上的效率优于XGNN。
PAGE在Graph-SST2数据集上的表现（RQ8）：我们评估了PAGE在没有明确地面真实解释的Graph-SST2数据集上的性能。Graph-SST2是从SST2数据集处理而来的二元图分类数据集。由于Graph-SST2是一个情感分类数据集，它没有明确的地面真实解释，这通常在实例间表达，这对运行PAGE构成了重大挑战。换句话说，技术上很难发现代表整个类别的地面真实解释（原型）。由于边缘表示词汇搭配，使得任务更加困难，因为词汇组合与类别没有明确的联系。 尽管存在这样的严重限制，我们还是在Graph-SST2上运行了PAGE的一部分，看看哪些输入图被选为最具代表性的图。更具体地说，我们执行了PAGE的第一阶段作为一个简化版本的PAGE。图12可视化了PAGE的结果，为每个类别/群集选择了三个图。从图中，我们希望提出以下观察： 在这里插入图片描述 如前所述，提取公共子图模式是不可能的。这是因为1）存在节点边缘，以及2）需要额外的标准来确定一个节点是否与另一个节点匹配以形成元组。 被选为输入的句子往往非常短。这可以自然地解释为PAGE的第一阶段试图在群集中发现共同模式的结果。当句子变得更长时，它将更有可能在其所属的群集中独特定位，因为它可能包含很少使用的单词，从而产生独特的图结构。尽管与化学/分子数据集分类的其他数据集相比，PAGE无法提供明确的原型图，但它仍然可以提供代表短语情感的每个类别的低分辨率概念，这是PAGE背后的另一个优点。 VI. 结论和展望 我们研究了一个在很大程度上未被探索但非常重要的问题，即在模型级别解释GNN的决策。为了应对这一实际挑战，我们引入了一种新颖的解释方法，通过发现来自节点级和图级embedding的原型，为图分类任务提供了GNN的模型级解释。具体来说，我们设计了一种有效的两阶段模型级GNN解释方法PAGE；在第一阶段进行图级embedding的聚类和选择之后，我们在第二阶段执行原型发现，该阶段分为初始化、迭代子图搜索和原型检索步骤。此外，我们从理论上验证了在PAGE中使用图级embedding聚类的使用。使用两个合成和三个真实世界数据集，我们全面证明了PAGE在定性和定量上都优于最先进的模型级GNN解释方法。此外，通过系统的评估，我们证明了PAGE在以下方面的有效性：1）核心原型搜索模块中多次搜索会话的影响，2）通过定量评估与实例级解释方法的关系，3）在只有少数图可用作为PAGE输入的困难和具有挑战性的情况下的鲁棒性，以及4）所提出的原型评分函数的计算效率。 我们工作的主要限制主要在于假设每个类别的地面真实解释的数量是可用的，我们在PAGE的第一阶段运行以发现图级embedding空间中的多个群集。在第一阶段，可以使用定量分析中使用的各种性能指标来找到最佳群集数量。作为未来研究的展望，估计每个类别的地面真实解释的数量是未来研究的一个有趣且重要的研究课题，因为PAGE的第一阶段需要在聚类之前知道每个类别的地面真实解释的数量，而这通常是事先不知道的。未来的其他研究途径包括为节点级或边缘级分类任务设计模型级GNN解释方法。 声明 本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。 你是否有这样的苦恼：自己辛苦的论文工作，几乎没有任何的引用。为什么会这样？主要是自己的工作没有被更多的人了解。
计算机书童 为各位推广自己的论文搭建一个平台，让更多的人了解自己的工作，同时促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 计算机书童 鼓励高校实验室或个人，在我们的平台上分享自己 论文 的介绍、解读 等。
稿件基本要求：
• 文章确系个人 论文的解读 ，未曾在公众号平台标记原创发表，
• 稿件建议以 markdown 格式撰写，文中配图要求图片清晰，无版权问题
投稿通道：
• 添加小编微信协商投稿事宜，备注：姓名-投稿
△长按添加 PaperEveryday 小编
