GNNExplainer: Generating Explanations for Graph Neural Networks
TL;DR 精炼摘要
GNNExplainer是首个通用的图神经网络可解释性方法,通过优化任务实现对模型预测的解释。该方法识别关键子图和节点特征,平均优于基线17.1%。GNNExplainer为普遍的图机器学习任务提供一致且简洁的解释,增强用户的信任和模型透明性。
摘要
Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs.GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. However, incorporating both graph structure and feature information leads to complex models, and explaining predictions made by GNNs remains unsolved. Here we propose GNNExplainer, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task. Given an instance, GNNExplainer identifies a compact subgraph structure and a small subset of node features that have a crucial role in GNN's prediction. Further, GNNExplainer can generate consistent and concise explanations for an entire class of instances. We formulate GNNExplainer as an optimization task that maximizes the mutual information between a GNN's prediction and distribution of possible subgraph structures. Experiments on synthetic and real-world graphs show that our approach can identify important graph structures as well as node features, and outperforms baselines by 17.1% on average. GNNExplainer provides a variety of benefits, from the ability to visualize semantically relevant structures to interpretability, to giving insights into errors of faulty GNNs.
思维导图
论文精读
中文精读
1. 论文基本信息
1.1. 标题
GNNExplainer: Generating Explanations for Graph Neural Networks
1.2. 作者
Rex Ying† Dylan Bourgeois†,‡ Jiaxuan You† Marinka Zitnik† Jure Leskovec† †Department of Computer Science, Stanford University Robust.AI {rexying, dtsbourg, jiaxuan, marinka, jure}@cs.stanford.edu
作者团队主要来自斯坦福大学计算机科学系和Robust.AI,显示出该研究在图神经网络和可解释人工智能领域的深厚背景。
1.3. 发表期刊/会议
该论文作为预印本发表于 arXiv。 Published at (UTC):2019-03-10T00:56:26.000Z
1.4. 发表年份
2019年
1.5. 摘要
图神经网络 (Graph Neural Networks, GNNs) 是在图上进行机器学习的强大工具。GNNs 通过沿输入图的边递归传递神经网络消息来结合节点特征信息和图结构。然而,结合图结构和特征信息导致模型复杂,解释 GNNs 做出的预测仍然是一个未解决的问题。本文提出了 GNNExplainer,这是第一个通用的、模型无关的方法,用于为任何基于 GNNs 的模型在任何基于图的机器学习任务上提供可解释的解释。对于一个实例,GNNExplainer 识别一个紧凑的子图结构和一小部分在 GNN 预测中起关键作用的节点特征。此外,GNNExplainer 可以为一整类实例生成一致且简洁的解释。我们将 GNNExplainer 形式化为一个优化任务,该任务最大化 GNN 预测与可能子图结构分布之间的互信息 (mutual information)。在合成图和真实世界图上的实验表明,我们的方法可以识别重要的图结构和节点特征,并且平均优于基线方法 17.1%。GNNExplainer 提供了多种好处,从可视化语义相关结构的能力到可解释性,再到深入了解有缺陷 GNNs 的错误。
1.6. 原文链接
原文链接: https://arxiv.org/abs/1903.03894v4 PDF 链接: https://arxiv.org/pdf/1903.03894v4.pdf 发布状态:预印本 (arXiv)
2. 整体概括
2.1. 研究背景与动机
研究背景: 在许多现实世界的应用中,数据可以自然地建模为图,例如社交网络、信息网络、化学分子和生物网络。图作为数据表示工具虽然强大,但由于需要同时建模丰富的关系信息和节点特征信息,因此处理起来极具挑战性。图神经网络 (Graph Neural Networks, GNNs) 作为解决这一挑战的先进技术应运而生,它们能够通过递归地整合来自图中邻居节点的信息,自然地捕获图结构和节点特征。GNNs 在各种图机器学习任务中取得了最先进的性能。
动机与研究空白: 尽管 GNNs 功能强大,但它们普遍缺乏透明度,难以提供人类可理解的预测解释。这种“黑箱”特性带来了多重问题:
-
信任度不足: 在许多决策关键型应用中(如医疗、金融),用户和开发者需要信任模型的预测,而缺乏解释性会降低这种信任。
-
透明性需求: 随着对人工智能公平性、隐私和安全性挑战的日益关注,模型透明性变得至关重要。
-
模型调试与改进: 实践者需要理解 GNNs 的工作原理,以便识别和纠正模型在部署前可能出现的系统性错误模式。
现有针对其他类型神经网络(如卷积神经网络、循环神经网络)的解释方法,主要分为两类:一类是使用更简单的代理模型进行局部近似(如 LIME),另一类是识别输入中的相关特征(如梯度图)。然而,这些方法在应用于图数据时都存在根本性不足,因为它们无法有效地整合图的核心——关系信息。图上的预测往往是节点和它们之间边的复杂组合所诱导的,例如,一条边可能只有在与图中的另一条路径形成环时才重要。这种联合贡献无法通过简单的线性组合来建模,因此需要一种专门针对图结构数据设计的解释方法。
2.2. 核心贡献/主要发现
本文提出了 GNNExplainer,旨在填补 GNNs 可解释性方法的空白。其核心贡献和主要发现包括:
- 首个通用、模型无关的 GNN 解释方法: GNNExplainer 是第一个能够为任何基于 GNNs 的模型(例如 GCN、GAT 等)在任何图机器学习任务(包括节点分类、链接预测、图分类)上提供可解释解释的通用方法,且无需修改或重新训练底层 GNN 模型。
- 识别关键子图结构和节点特征: 对于给定预测,GNNExplainer 能够识别一个紧凑的子图结构和一小部分节点特征,这些结构和特征在 GNN 做出该预测时起到了决定性作用。它同时考虑了图结构和节点特征的重要性。
- 基于互信息 (Mutual Information) 的优化框架: 将解释问题形式化为一个优化任务,通过最大化 GNN 预测与可能的子图结构分布之间的互信息来找到最佳解释。这等价于最小化条件熵。
- 单实例和多实例解释能力: 能够为单个实例(如某个节点的预测标签)生成解释,也可以为一整类实例(如具有相同标签的所有节点)生成一致且简洁的原型解释,揭示该类实例共享的图模式。
- 优越的解释性能: 在合成图和真实世界图上的实验表明,GNNExplainer 在解释准确率方面平均优于现有基线方法 17.1%,在某些复杂数据集上甚至高达 43.0%。
- 提供领域洞察: GNNExplainer 能够识别语义相关的结构,例如在分子图中识别出致突变化学基团(如 NO₂),在社交网络中识别出具有特定互动模式的星形结构,从而为领域专家提供重要的洞察。
3. 预备知识与相关工作
3.1. 基础概念
为了更好地理解 GNNExplainer,我们首先需要了解一些核心概念。
3.1.1. 图 (Graph)
在计算机科学和数学中,一个图 由一组节点 (nodes) 或顶点 (vertices) 和一组边 (edges) 组成。每条边连接 中的两个节点。图可以用来表示各种关系数据,例如社交网络中的人际关系,分子结构中的原子连接,或知识图谱中的实体关系。每个节点还可以关联一个特征向量 (feature vector) ,表示该节点的属性。
3.1.2. 图神经网络 (Graph Neural Networks, GNNs)
GNNs 是一类专门设计用于处理图结构数据的神经网络。它们的核心思想是通过消息传递 (message passing) 机制来学习节点的表示。具体而言,每个节点会从其邻居节点接收信息(消息),然后将这些信息与自身的信息进行聚合 (aggregate),最后更新自己的节点表示 (node representation)。这个过程通常会迭代多层,使得每个节点的最终表示能够捕获其多跳邻域的结构和特征信息。
GNN 模型在第 层的更新通常涉及以下三个核心计算:
- 消息计算 (Message Computation, MSG): 对于每对节点 ,计算一个消息 ,它通常是节点 和 在前一层表示 和 的函数。 其中, 表示节点 和 之间的关系。
- 消息聚合 (Message Aggregation, AGG): 对于每个节点 ,聚合其邻居 发送来的所有消息,得到一个聚合消息 。
- 节点更新 (Node Update, UPDATE): 将聚合消息 与节点 在前一层的表示 结合,通过非线性变换更新得到 在当前层的表示 。 经过 层计算后,节点 的最终嵌入为 ,这个嵌入用于下游任务的预测。
3.1.3. 计算图 (Computation Graph)
对于 GNN 而言,一个节点的预测依赖于其多跳邻域内的节点和边。这个多跳邻域形成的子图就是该节点的计算图 (computation graph)。例如,一个 2 层 GNN 的预测会依赖于该节点 2 跳邻域内的所有节点和边。计算图完整包含了 GNN 做出某个预测所需的所有信息,包括结构和特征。
3.1.4. 可解释人工智能 (Explainable AI, XAI)
可解释人工智能 (Explainable AI, XAI) 旨在使人工智能模型的决策过程对人类而言更加透明和可理解。随着 AI 模型复杂性的增加,尤其是深度学习模型,它们往往被视为“黑箱”,难以理解其内部机制。XAI 的目标是提供模型如何做出预测的洞察,从而增强用户对 AI 的信任,帮助开发者调试模型,并确保模型满足公平性、隐私和安全等伦理要求。
3.1.5. 互信息 (Mutual Information, MI)
互信息 (Mutual Information, MI) 是信息论中的一个概念,用于衡量两个随机变量之间相互依赖的程度。它量化了一个变量中包含的关于另一个变量的信息量。如果两个变量相互独立,则它们的互信息为零。互信息越高,表示两个变量之间的关联性越强。
对于两个随机变量 和 ,其互信息 MI(X, Y) 定义为:
其中:
H(Y)是随机变量 的熵 (entropy),表示 的不确定性。- 是给定 时 的条件熵,表示在已知 的情况下 的剩余不确定性。 因此,互信息可以理解为:通过了解 能够减少 的不确定性量。在 GNNExplainer 中,GNNExplainer 通过最大化预测 与解释 之间的互信息,来寻找能够最大程度减少预测不确定性的子图和特征。
3.2. 前人工作
论文在 相关工作 (Section 2) 中讨论了现有解释性方法的局限性,特别是在图数据背景下。
3.2.1. 非图神经网络的解释方法
-
代理模型 (Proxy Models):
- 这类方法通过局部近似复杂模型来构建一个更简单的、可解释的代理模型。例如,LIME (Local Interpretable Model-agnostic Explanations) 会在单个预测周围用一个线性模型来近似“黑箱”模型,然后通过解释这个线性模型来获得局部解释。
- 论文中提到通过线性模型或规则集来表示预测的充分条件。这些方法通常是模型无关的,但其核心问题在于无法有效整合图的关系信息,这对于图数据的解释至关重要。
-
特征重要性 (Feature Importance) 方法:
- 这类方法通过检查模型来识别输入中对预测贡献最大的特征。
- 梯度方法 (Gradient-based methods): 例如
saliency maps(显著图),通过计算输出对输入特征的梯度来衡量特征重要性。梯度值越大,表示该特征对输出的影响越大。 - 反向传播贡献 (Backpropagation of contributions): 通过反向传播神经元的贡献到输入特征。
- 反事实推理 (Counterfactual reasoning): 改变输入以观察预测如何变化,从而推断哪些输入变化会导致预测改变。
- 局限性: 论文指出这些方法(特别是基于梯度的)可能在某些情况下产生误导,并且容易出现梯度饱和问题。对于离散输入(如图邻接矩阵),这些问题会加剧,因为梯度值可能在非常小的区间内非常大。更重要的是,它们通常难以捕获图结构中的复杂关系模式,例如环结构或路径的重要性。
3.2.2. GNNs中的注意力机制 (Attention Mechanisms)
一些 GNN 模型(如 Graph Attention Networks (GAT))通过引入注意力机制来增强可解释性。边上的注意力权重可以被解释为表示该边在消息传递中的重要性。
- 局限性: 论文指出,尽管注意力权重可以指示重要的图结构,但它们在不同节点的预测中往往是相同的。这意味着,一条边对于一个节点的预测可能很重要,但对于另一个节点的预测可能不重要,而注意力机制通常无法区分这一点。此外,这些方法通常要么局限于特定的 GNN 架构,要么无法同时解释图结构和节点特征信息。
3.3. 技术演进
图结构数据分析从传统的图特征工程(如节点度、中心性等)发展到复杂的图嵌入(如 DeepWalk, Node2vec),再到当前的图神经网络,性能上取得了显著飞跃。然而,在可解释性方面,GNNs 仍处于早期阶段。传统的可解释性方法主要针对图像、文本等欧几里得数据设计,难以直接应用于非欧几里得的图数据。GNNExplainer 正是在这一背景下,将可解释性研究从通用神经网络扩展到 GNNs,并首次提出一个能够同时考虑图结构和节点特征的模型无关解释框架。
3.4. 差异化分析
GNNExplainer 与相关工作的主要区别和创新点体现在以下几个方面:
- 图结构与节点特征的联合解释: 现有方法大多侧重于特征重要性或结构重要性之一,GNNExplainer 能够同时识别并解释对预测至关重要的子图结构和节点特征子集,这是其核心优势。
- 模型无关 (Model-Agnostic) 和任务无关 (Task-Agnostic): GNNExplainer 不依赖于特定的 GNN 架构,可以应用于任何基于消息传递的 GNN 模型,并且适用于多种图机器学习任务(节点分类、链接预测、图分类),而基线方法
ATT仅限于GAT模型。 - 基于互信息的形式化: 将解释问题严格形式化为最大化 GNN 预测与解释子图之间互信息的优化问题,提供了坚实的理论基础,而非启发式方法。
- 局部性与紧凑性: 通过优化框架识别出的解释是一个紧凑的子图,这使得解释更易于人类理解和可视化,避免了提供过于庞大或稀疏的信息。
- 处理关系信息的能力: 明确地利用了 GNN 的递归邻域聚合机制,确保所选的解释子图是有效的计算图,即其中包含的边和节点能够真正影响 GNN 的消息传递和最终预测。这避免了将图的复杂关系结构简单地线性化处理。
4. 方法论
4.1. 方法原理
GNNExplainer 的核心思想源于一个关键观察:GNN 对节点 的预测 完全由其计算图 (computation graph) 和其中涉及的节点特征 (node features) 所决定。GNNExplainer 的目标是为这个预测 找到一个紧凑的解释,即一个小的子图 和一个小的节点特征子集 ,它们对 的产生起着最关键的作用。
该方法将解释问题形式化为一个优化任务:最大化 GNN 预测与可能的子图结构分布之间的互信息 (mutual information)。通过这种方式,GNNExplainer 旨在找到一个解释 ,使得在仅考虑这个解释的情况下,GNN 预测的不确定性最小,从而使得预测 的概率最大化。为了使问题可处理,它引入了可学习的结构掩码和特征掩码,通过连续松弛和变分近似来优化目标函数。
4.2. 核心方法详解
4.2.1. GNN 模型背景
在介绍 GNNExplainer 的具体方法之前,我们首先回顾 GNN 的核心计算过程,因为 GNNExplainer 正是基于这些机制来生成解释的。一个 GNN 模型 在第 层的更新涉及三个关键计算:
-
消息计算 (Message Computation, MSG): 模型计算每对节点之间的神经网络消息。对于节点对 ,消息 是节点 和 在前一层表示 和 的函数,以及节点之间关系 的函数: 其中, 和 分别是节点 和 在第
l-1层的表示向量, 表示它们之间的关系(例如,通过邻接矩阵的元素)。 -
消息聚合 (Message Aggregation, AGG): 对于每个节点 ,GNN 从其邻域 聚合所有消息,并通过聚合方法 AGG 计算一个聚合消息 : 这里, 是节点 的邻域,其定义取决于特定的 GNN 变体。常见的聚合函数包括求和、求平均、最大值等。
-
节点更新 (Node Update, UPDATE): 最后,GNN 将聚合消息 与节点 在前一层的表示 结合,并通过非线性变换得到节点 在第 层的表示 : 经过 层计算后,节点 的最终嵌入是 。GNNExplainer 能够为任何可以通过 MSG、AGG 和 UPDATE 计算形式化的 GNN 提供解释。
4.2.2. GNNExplainer: 问题形式化
GNN 的预测 是由模型 、图结构信息 和节点特征信息 完全决定的。GNNExplainer 的目标是为预测 生成一个解释 ,其中 是计算图 的一个小型子图,而 是 中节点特征的一小部分子集,这些是解释 最重要的信息。
4.2.3. 单实例解释 (Single-instance explanations)
对于一个给定节点 ,我们的目标是识别一个子图 和其关联的特征 ,它们对于 GNN 的预测 至关重要。最初,我们假设 包含所有节点特征;稍后将讨论如何自动确定哪些特征维度需要包含在解释中。我们使用互信息 (Mutual Information, MI) 来形式化“重要性”的概念,并将 GNNExplainer 形式化为以下优化框架:
目标函数:
对于节点 ,互信息 MI 量化了当 的计算图限制为解释子图 且其节点特征限制为 时,预测概率分布 的变化。
由于训练好的 GNN 模型 是固定的,因此熵项 H(Y) 是常数。因此,最大化预测标签分布 与解释 之间的互信息等价于最小化条件熵 ,其表达式如下:
因此,预测 的解释是一个子图 ,它在 GNN 计算仅限于 时使 的不确定性最小。实际上, 最大化了 的概率。
为了获得一个紧凑的解释,我们对 的大小施加约束:,这样 最多有 个节点。这意味着 GNNExplainer 旨在通过选择与预测具有最高互信息的 条边来对 进行降噪。
GNNExplainer 的优化框架:
直接优化 GNNExplainer 的目标函数是不可行的,因为 具有指数级的子图 作为 的候选解释。因此,我们考虑子图 的分数邻接矩阵 ,并强制执行子图约束: 对于所有 j, k。这种连续松弛可以解释为 子图分布的变分近似。特别是,如果我们把 看作一个随机图变量,那么方程 (2) 中的目标就变为:
在凸性假设下,Jensen 不等式给出了以下上界:
实际上,由于神经网络的复杂性,凸性假设不成立。然而,实验发现,通过正则化最小化这个目标函数通常会导致高质量解释的局部最小值。
为了可处理地估计 ,我们使用均场变分近似 (mean-field variational approximation) 并将 分解为 。通过对均场近似的期望,我们得到 ,其中 (j,k)-th 条目表示边 是否存在的期望。经验上观察到,这种近似以及促进离散性的正则化器(如 [40])尽管 GNN 具有非凸性,但仍能收敛到良好的局部最小值。方程 (4) 中的条件熵可以通过替换 为计算图邻接矩阵 的掩码 来优化,其中 是我们需要学习的掩码, 表示逐元素乘法, 表示将掩码映射到 的 sigmoid 函数。
在某些应用中,用户更关心“为什么训练好的模型会预测某个类别标签”或“如何让训练好的模型预测一个期望的类别标签”。我们可以用交叉熵目标函数 (cross entropy objective) 替代方程 (4) 中的条件熵目标函数。为了回答这些查询,GNNExplainer 的目标函数的一个计算高效版本(我们使用梯度下降进行优化)如下:
优化目标 (交叉熵形式): 其中, 是一个指示函数,当真实标签为 时取 1,否则取 0。这个目标函数最小化了 GNN 在给定掩码图 和特征 下,对正确类别 的预测概率的负对数。
最后,我们计算 和 的逐元素乘积,并通过阈值处理去除 中的低值,从而得到 GNN 模型在节点 处预测 的解释子图 。
4.2.4. 联合学习图结构和节点特征信息 (Joint learning of graph structural and node feature information)
为了识别哪些节点特征对预测 最重要,GNNExplainer 为解释子图 中的节点学习一个特征选择器 。不是将 定义为包含所有节点特征,即 ,GNNExplainer 将 视为 中节点特征的子集,通过一个二值特征选择器 定义(如 Figure 2B 所示): 其中, 包含未被 掩码掉的节点特征。解释 随后通过以下目标函数联合优化,以最大化互信息:
联合优化目标函数: 这代表了方程 (1) 的修改版目标函数,它考虑了结构信息和节点特征信息来生成对预测 的解释。
学习二值特征选择器 : 我们将 指定为 ,其中 作为我们需要学习的特征掩码。直观地说,如果某个特定特征不重要,那么 GNN 权重矩阵中对应的权重值将接近零。这意味着掩盖该特征不会降低预测 的概率。反之,如果特征重要,掩盖它将降低预测概率。然而,在某些情况下,这种方法会忽略对预测重要但取值接近零的特征。为了解决这个问题,我们对所有特征子集进行边际化,并使用蒙特卡洛估计从训练期间 中节点的经验边际分布中采样。此外,我们使用重参数化技巧 (reparametrization trick) 来将方程 (7) 中的梯度反向传播到特征掩码 。具体来说,为了反向传播一个 维随机变量 ,我们将其重参数化为:,使得 ,其中 是从经验分布中采样的 维随机变量, 是表示解释中保留的最大特征数量的参数。
整合额外的约束到解释中: 为了对解释施加进一步的属性,我们可以用正则化项扩展 GNNExplainer 在方程 (7) 中的目标函数。例如,我们使用逐元素熵来鼓励结构掩码和节点特征掩码是离散的。此外,GNNExplainer 可以通过拉格朗日乘子约束或额外的正则化项来编码领域特定的约束。我们包含了一些正则化项来产生具有所需属性的解释。我们通过添加掩码参数所有元素的总和作为正则化项来惩罚解释的过大尺寸。
重要的是,每个解释都必须是一个有效的计算图。特别是,解释 需要允许 GNN 的神经网络消息流向节点 ,以便 GNN 能够做出预测 。GNNExplainer 自动提供代表有效计算图的解释,因为它优化了整个计算图上的结构掩码。即使一个不连通的边对神经网络消息传递很重要,它也不会被选作解释,因为它不能影响 GNN 的预测。实际上,这意味着解释 倾向于是一个小的连通子图。
4.2.5. 通过图原型进行多实例解释 (Multi-instance explanations through graph prototypes)
单实例解释的输出是输入图的一个小分子图和一小部分关联节点特征,它们对单个预测最具影响力。为了回答诸如“GNN 如何预测给定的一组节点都具有标签 ?”之类的问题,我们需要获得类别 的全局解释。我们的目标是深入了解特定节点的识别子图如何与解释整个类别的图结构相关联。GNNExplainer 可以根据图对齐和原型提供多实例解释。该方法分为两个阶段:
第一阶段:选择参考节点和对齐 对于给定的类别 (或任何我们想要解释的预测集),我们首先选择一个参考节点 (reference node) 。例如,可以通过计算所有分配给 的节点的平均嵌入,然后选择嵌入最接近平均值的节点。或者,如果对重要计算子图有先验知识,则可以选择最符合先验知识的节点。
给定类别 的参考节点 及其关联的重要计算子图 ,我们将类别 中所有节点的已识别计算子图与参考 对齐。利用可微池化 (differentiable pooling) 思想,我们使用松弛对齐矩阵来找到计算子图 中节点与参考计算子图 中节点之间的对应关系。令 和 分别是待对齐计算子图的邻接矩阵和关联特征矩阵。类似地,令 和 分别是参考计算子图的邻接矩阵和关联特征矩阵。然后我们优化松弛对齐矩阵 ,其中 是 中的节点数, 是 中的节点数,如下所示:
- 符号解释:
-
:松弛对齐矩阵,表示 中节点与 中节点之间的对应关系。
-
:待对齐子图 中的节点数量。
-
:参考子图 中的节点数量。
-
:待对齐计算子图 的邻接矩阵。
-
:待对齐计算子图 的特征矩阵。
-
:参考计算子图 的邻接矩阵。
-
:参考计算子图 的特征矩阵。
-
:可以是矩阵范数(如 Frobenius 范数),用于衡量矩阵之间的差异。
-
方程 (8) 的第一项 表明在对齐后, 的对齐邻接矩阵应该尽可能接近 。第二项 表明对齐节点的特征也应该接近。
在实践中,对于两个大型图,松弛图匹配找到良好最优解通常并不容易。然而,由于单实例解释器生成了简洁的子图,使得接近最佳对齐可以高效计算。
-
第二阶段:生成原型 我们对齐类别 中所有节点的邻接矩阵,使其与参考邻接矩阵定义的顺序对齐。然后,我们使用中位数来生成一个对异常值具有鲁棒性的原型 (prototype),,其中 是表示类别 中第 个节点解释的对齐邻接矩阵。原型 允许用户深入了解属于同一类别的节点之间共享的结构图模式。用户可以通过比较其解释与类别原型来研究特定节点。
4.2.6. GNNExplainer 模型扩展 (GNNExplainer model extensions)
-
任何图机器学习任务: 除了节点分类,GNNExplainer 无需修改优化算法即可为链接预测和图分类提供解释。
- 链接预测: 预测链接 时,GNNExplainer 会为链接的两个端点学习两个掩码 和 。
- 图分类: 分类图时,方程 (5) 中的邻接矩阵是图中所有我们希望解释其标签的节点的邻接矩阵的并集。值得注意的是,在图分类中,与节点分类不同,由于节点嵌入的聚合,解释子图 不一定是连通的。根据应用场景(例如在化学领域,解释应是功能组且应连通),可以提取最大的连通分量作为解释。
-
任何 GNN 模型: 现代 GNN 都基于输入图上的消息传递架构。消息传递计算图可以以多种不同方式组成,GNNExplainer 可以解释所有这些方式。因此,GNNExplainer 可以应用于:图卷积网络 (GCN)、门控图序列神经网络 (Gated Graph Sequence Neural Networks)、跳跃知识网络 (Jumping Knowledge Networks)、注意力网络 (Attention Networks)、图网络 (Graph Networks)、具有各种节点聚合方案的 GNN、线图神经网络 (Line-Graph NNs)、位置感知 GNN 等多种 GNN 架构。
-
计算复杂度 (Computational complexity): GNNExplainer 优化中的参数数量取决于我们旨在解释其预测的节点 的计算图 的大小。具体来说, 的邻接矩阵 等于需要由 GNNExplainer 学习的掩码 的大小。然而,由于计算图通常相对较小(例如,2-3 跳邻域、基于采样的邻域、带注意力的邻域),即使输入图很大,GNNExplainer 也能有效地生成解释。
该图像是示意图,展示了 GNNExplainer 方法的基本概念。图 A 显示了 GNN 消息传递中重要与不重要的节点及其功能,而图 B 则表示在解释中排除的特征向量。图中的重要性通过绿色和橙色节点表示,未包含的特征用红色标记。
Figure 2: A. GNN computation graph G _ { c } (green and orange) for making prediction at node Some edges in G _ { c } form important neural message-passing pathways (green), which allow useful node information to be propagated across G _ { c } and aggregated at for prediction, while other edges do not (orange). However, GNN needs to aggregate important as well as unimportant messages to form a prediction at node , which can dilute the signal accumulated from 's neighborhood. The goal of GNNExPLAINER is to identify a small set of important features and pathways (green) that are crucial for prediction. B. In addition to G _ { S } (green), GNNExPLAINER identifies what feature dimensions of G _ { S } 's nodes are important for prediction by learning a node feature mask.
上图(原文 Figure 2)A 部分展示了一个 GNN 的计算图 ,其中包含对预测有重要影响的消息传递路径(绿色)和不重要路径(橙色)。GNNExplainer 的目标是识别出对预测至关重要的少量特征和路径(绿色)。B 部分进一步说明,除了识别子图 (绿色),GNNExplainer 还通过学习节点特征掩码来识别 中哪些特征维度对预测很重要。
5. 实验设置
5.1. 数据集
实验使用了四种合成节点分类数据集和两种真实世界图分类数据集来验证 GNNExplainer 的性能。
5.1.1. 合成数据集 (Synthetic datasets)
这些数据集用于节点分类任务,具有已知的地面真值 (ground-truth) 解释,便于定量评估。
- BA-SHAPES: 从一个包含 300 个节点的 Barabási-Albert (BA) 基本图开始,并附加了 80 个五节点“房子”结构的网络基序 (network motifs) 到随机选择的基本图节点上。随后通过添加 0.1N 条随机边来扰动图。节点根据其在“房子”结构中的位置(顶部、中部、底部节点)或不属于“房子”结构而被分配到 4 个类别。
- 特点: 节点标签与特定的局部图结构(“房子”基序)紧密相关。
- BA-COMMUNITY: 是两个 BA-SHAPES 图的并集。节点具有正态分布的特征向量,并根据其结构角色和社区成员身份被分配到 8 个类别。
- 特点: 结合了结构角色和社区信息进行分类,同时引入了节点特征。
- TREE-CYCLES: 从一个 8 层平衡二叉树作为基本图开始,并附加了 80 个六节点循环基序到基本图的随机节点上。
- 特点: 节点标签与循环结构相关。
- TREE-GRID: 与 TREE-CYCLES 类似,但将 3x3 网格基序附加到基本树图上,而不是循环基序。
- 特点: 节点标签与网格结构相关,比循环基序更复杂。
5.1.2. 真实世界数据集 (Real-world datasets)
这些数据集用于图分类任务,用于展示 GNNExplainer 在复杂实际场景中的应用和提供领域洞察的能力。
- MUTAG: 一个包含 4,337 个分子图的数据集。这些图根据分子对革兰氏阴性细菌鼠伤寒沙门氏菌 (S. typhimurium) 的致突变性 (mutagenic effect) 进行标记。
- 特点: 分子结构(图结构)和原子类型(节点特征)共同决定致突变性。
- 样本示例: 分子图,节点代表原子,边代表化学键。例如,硝基 () 或胺基 () 等官能团是致突变性的关键结构。
- REDDIT-BINARY: 一个包含 2,000 个图的数据集,每个图代表 Reddit 上的一个在线讨论帖子。图中节点是参与讨论的用户,边表示一个用户回复了另一个用户的评论。图根据帖子中用户交互的类型进行标记:r/IAmA 和 r/AskReddit 包含问答 (Question-Answer) 互动,而 r/TrollXChromosomes 和 r/atheism 包含在线讨论 (Online-Discussion) 互动。
- 特点: 讨论模式(图结构)反映了不同的用户交互类型。
- 样本示例: 社交互动图,节点是用户,边是回复关系。
5.2. 评估指标
论文中主要使用了“解释准确率”作为定量评估指标。
5.2.1. 解释准确率 (Explanation Accuracy)
- 概念定义 (Conceptual Definition): 解释准确率旨在衡量解释方法识别与地面真值解释相符的关键结构和特征的能力。它将解释问题视为一个二分类任务:真实解释中包含的边被视为正类别标签,而解释方法提供的边的重要性权重被视为对这些标签的预测分数。一个更好的解释方法应该对真实重要的边赋予更高的分数,从而实现更高的解释准确率。在论文的上下文中,这可以理解为衡量模型是否能够精确地从大量可能的边中挑出那些在地面真值中被认为是重要的边。
- 数学公式 (Mathematical Formula): 论文中未直接提供解释准确率的数学公式。考虑到其描述为“预测高分数给真实解释中的边”且与二分类任务相关,一个常用的且能捕捉这种性能的指标是 AUC-ROC (Area Under the Receiver Operating Characteristic Curve)。
- 符号解释 (Symbol Explanation):
- (True Positive Rate,真阳性率):也称为召回率 (Recall) 或敏感度 (Sensitivity)。它表示所有实际为正(即在地面真值解释中存在的边)的样本中,被正确预测为正的比例。
- (False Positive Rate,假阳性率):表示所有实际为负(即不在地面真值解释中存在的边)的样本中,被错误预测为正的比例。
- :是指在所有可能的分类阈值下,以 FPR 为 x 轴,TPR 为 y 轴绘制的接收者操作特征 (ROC) 曲线下的面积。 的值范围从 0 到 1,其中 1 表示完美分类器,0.5 表示随机分类器。其值越大,表示解释方法在区分重要边和不重要边方面的性能越好,即它能更好地识别出“真实重要的边”。
5.3. 对比基线 (Baselines)
论文将 GNNExplainer 与两种可以提供图解释的替代方法进行了比较:
- GRAD (Gradient-based method):
- 原理: 这是一种基于梯度的方法,类似于神经网络中的显著图 (saliency map) 技术。它通过计算 GNN 损失函数关于邻接矩阵和关联节点特征的梯度来衡量它们的重要性。梯度值越大,表示对应的边或特征对模型预测的影响越大。
- 代表性: 梯度方法是评估神经网络特征重要性的标准方法之一,但论文指出它可能不适用于离散输入和存在梯度饱和问题。
- ATT (Graph Attention Networks, GAT) [33]:
- 原理: 这是一种基于图注意力网络的基线方法。它利用 GAT 模型学习到的边注意力权重 (attention weights) 作为边重要性的代理度量。注意力权重反映了在消息传递过程中,邻居节点对中心节点的重要性。
- 代表性: GAT 模型本身就具有一定的解释性,其注意力机制被认为可以揭示重要的结构。
- 局限性: 该方法仅限于解释 GAT 模型,且无法解释节点特征。此外,注意力权重在所有节点预测中往往是共享的,这限制了其提供高质量单实例解释的能力。在一个节点的一跳邻居同时也是二跳邻居的循环情况下,确定哪个注意力权重用于边缘重要性并不直观,论文通过取所有层上注意力权重的平均值来解决。
5.4. 设置和实现细节 (Setup and implementation details)
- GNN 模型训练: 每个数据集都首先训练一个单独的 GNN 模型。所有 GNN 模型都使用 Adam 优化器训练 1000 个 epoch,学习率为 0.001。在图分类数据集上,GNN 模型的准确率至少达到 85%,在节点分类数据集上达到 95%。
- 数据划分: 所有数据集的训练/验证/测试划分比例为 80%/10%/10%。
- GNNExplainer 训练: GNNExplainer 使用与 GNN 模型相同的 Adam 优化器和学习率,训练 100-300 个 epoch。由于 GNNExplainer 仅需在局部计算图(节点数通常少于 100)上进行训练,因此效率很高。
- 超参数:
- :控制解释子图的大小。对于合成数据集,设置为地面真值解释的大小。对于真实世界数据集,设置为 10。
- :控制特征解释中保留的特征数量。对于所有数据集,设置为 5。
- 正则化: 引入了若干正则化项以产生具有期望属性的解释。
- 子图大小约束的正则化超参数:0.005。
- 拉普拉斯约束的正则化超参数:0.5。
- 特征解释约束的正则化超参数:0.1。
- 所有实验中使用相同的超参数值。
- 子图提取:
- 首先计算边上的重要性权重(GRAD 使用梯度,ATT 使用注意力权重,GNNExplainer 使用掩码邻接矩阵)。
- 使用阈值去除低权重边,并识别解释子图 。
- 由于所有数据集的地面真值解释都是连通子图,对于节点分类,解释被识别为包含被解释节点的连通分量。
- 对于图分类,解释被识别为 的最大连通分量。
- 对于所有方法,执行搜索以找到最大阈值,使得解释的大小至少为 。当多个边的重要性权重相同时,它们都包含在解释中。
6. 实验结果与分析
论文通过定量和定性分析展示了 GNNExplainer 在各种图任务中的准确性和有效性,包括在图结构和节点特征方面的解释能力。
6.1. 核心结果分析
6.1.1. 定量分析 (Quantitative analyses)
论文在节点分类数据集上的实验结果表明,GNNExplainer 在解释准确率方面显著优于基线方法。
以下是原文 Table 1 的结果:
| Dataset | GNN Acc. | Explanation Accuracy (AUC) | |||
|---|---|---|---|---|---|
| ATT | GRAD | GNNExPLAINER | |||
| Node Class. | BA-SHAPES | 98.9% | 0.543 | 0.598 | 0.751 |
| BA-COMMUNITY | 95.1% | 0.569 | 0.589 | 0.701 | |
| TREE-CYCLES | 99.2% | 0.574 | 0.591 | 0.742 | |
| TREE-GRID | 98.8% | 0.561 | 0.573 | 0.819 | |
| Graph Class. | MUTAG | 89.6% | 0.612 | 0.687 | 0.781 |
| REDDIT-BINARY | 91.4% | 0.623 | 0.692 | 0.793 | |
上表(原文 Table 1)展示了 GNNExplainer 和两种基线方法在合成和真实世界数据集上的解释准确率(AUC)。GNN Acc. 列表示 GNN 模型自身的预测准确率。
- 结果分析:
- GNNExplainer 的显著优势: GNNExplainer 在所有节点分类和图分类数据集上都取得了最高的解释准确率。在节点分类数据集上,GNNExplainer 平均比替代方法高出 17.1%。
- 在 TREE-GRID 上的卓越表现: 在最难的
TREE-GRID数据集上,GNNExplainer 的准确率高达 0.819,比基线方法高出 43.0%。这表明 GNNExplainer 能够更好地识别复杂且对预测至关重要的图结构。 - 基线方法的局限性:
ATT和GRAD基线方法的解释准确率普遍较低,通常接近 0.5-0.6,这表明它们在识别真实重要结构方面的能力有限。特别是ATT,尽管使用了注意力机制,但由于其注意力权重通常在所有节点间共享,因此难以提供高质量的单实例解释。
6.1.2. 定性分析 (Qualitative analyses)

该图像是示意图,展示了GNNExplainer在不同图结构(如BA-Shapes和BA-Community、Tree-Cycles和Tree-Grid)上的表现,比较了计算图、GNNExplainer、Grad、Att和Ground Truth的结果,体现了GNNExplainer在解释GNN预测中的有效性。
Figure 3: Evaluation of single-instance explanations. A-B. Shown are exemplar explanation subgraphs for node classication task on four synthetdatasets.Each method provides explanation or the red node's predicion. 上图(原文 Figure 3)展示了单实例解释的评估结果,为四个合成数据集上的节点分类任务提供了示例解释子图。每个方法都为红色节点的预测提供了解释。
-
合成数据集上的表现: 在没有节点特征的拓扑预测任务中,如
BA-SHAPES和TREE-CYCLES,GNNExplainer 成功识别了用于解释节点标签(即结构标签)的网络基序。如图所示,house、cycle和tree基序被 GNNExplainer 识别出来,而基线方法未能做到。这表明 GNNExplainer 能够捕获到 GNN 预测所依赖的特定局部结构模式。
该图像是一个图表,展示了论文中GNNExplainer方法与Grad和Att方法在两个数据集(Mutag和Reddit-Binary)上的解释效果对比。图中分A和B两部分,分别对应不同任务的计算图、方法结果及真实标签,突出了GNNExplainer在捕捉重要子结构和节点特征上的优势。
图表(原文 Figure 4)展示了 GNNExplainer 方法与 Grad 和 Att 方法在两个数据集(Mutag 和 Reddit-Binary)上的解释效果对比。图中分 A 和 B 两部分,分别对应不同任务的计算图、方法结果及真实标签,突出了 GNNExplainer 在捕捉重要子结构和节点特征上的优势。
-
图分类任务的解释:
- MUTAG 数据集: 在
MUTAG分子图的例子中,颜色表示节点特征(如氢 H、碳 C 等原子)。GNNExplainer 准确地识别出了碳环以及NH2和NO2等化学基团,这些基团已知具有致突变性。这证明了 GNNExplainer 能够提供重要的领域洞察,识别出对分子性质有关键影响的化学结构。 - REDDIT-BINARY 数据集:
- 问答图 (Question-Answer graphs): 如图 4B 中第二行所示,问答图通常具有 2-3 个高连接度节点,同时连接到许多低连接度节点。这符合 Reddit 问答帖子的特点,即通常有 2-3 位专家回答许多不同的问题。
- 讨论模式 (Discussion patterns): 如图 4A 中第二行所示,讨论模式通常呈现树状结构,这反映了 Reddit 帖子通常是对单一主题的反应。
- MUTAG 数据集: 在
-
基线方法的局限性: 相比之下,
GRAD和ATT方法给出了不正确或不完整的解释。例如,这两种基线方法都未能识别MUTAG数据集中的循环基序以及TREE-GRID数据集中更复杂的网格基序。此外,尽管ATT中的边注意力权重可以被解释为消息传递的重要性分数,但这些权重在输入图的所有节点中是共享的,因此ATT无法提供高质量的单实例解释。
该图像是一个示意图,展示了 GNNExplainer 在图分类(A)和节点分类(B)任务中的应用。上部分展示了输入图、GNN 的预测以及特征重要性比较,底部分则列出了 Ground Truth、GNNExplainer 和 Grad 的结果,突出 GNNExplainer 在提取特征上的有效性。
Figure 5: Visualization of features that are important for a GNN's prediction. A. Shown is a representative molecular graph from MuTAG dataset (top). Importance of the associated graph features is visualized with a heatmap (bottom). In contrast with baselines, GNNExPLAINER correctly identifies features that are important for predicting the molecule's mutagenicity, i.e. C, O, H, and N atoms. B. Shown is a computation graph of a red node from BA-CoMMUNITY dataset (top). Again, GNNExPLAINER successfully identifies the node feature that is important for predicting the structural role of the node but baseline methods fail. 上图(原文 Figure 5)展示了对 GNN 预测重要的特征可视化。
- 特征可视化和联合解释: 可解释性的一个重要标准是它必须是可解释的,即提供输入节点与预测之间关系的定性理解。这要求解释既易于理解又详尽。这意味着 GNN 解释器应在可用时同时考虑底层图的结构及其关联的特征。Figure 5 展示了一个 GNNExplainer 联合考虑结构信息和少量特征维度信息的实验结果。
-
MUTAG 数据集: GNNExplainer 正确地识别了对预测分子致突变性重要的特征,例如 C、O、H 和 N 原子,并通过热图清晰地展示了其重要性。
-
BA-COMMUNITY 数据集: GNNExplainer 成功识别出对预测节点结构角色重要的节点特征,而基于梯度的基线方法在加入噪声后难以应对,对不相关的特征维度也给出了高重要性分数。
这进一步证明了 GNNExplainer 在联合解释图结构和节点特征方面的优越性,以及其在处理噪声和提供语义相关解释方面的鲁棒性。
-
6.1.3. 多实例解释 (Multi-instance explanations)
论文在附录中进一步探讨了使用图原型进行多实例解释的能力。GNNExplainer 能够为给定节点类别提供原型,例如在 MUTAG 数据集中识别出致突变化合物的功能子图。

该图像是示意图,展示了三种不同的子图结构:参考子图(Ref Subgraph)、噪声子图(Noisy Subgraph)和原型(Prototype)。这些子图在GNNExplainer方法中用于解释GNN的预测,突显了子图特征的重要性。
Figure 6: GnnExpLAINER is able to provide a prototype for a given node class, which can help identify functional subgraphs, e.g. a mutagenic compound from the MuTAG dataset. 上图(原文 Figure 6)展示了 GNNExplainer 能够为给定节点类别提供原型,这有助于识别功能子图,例如来自 Mutag 数据集的致突变化合物。
- 原型生成: GNNExplainer 通过对齐同一类别中多个实例的解释子图,并聚合它们(例如使用中位数),生成一个能够代表该类别共同特征的图原型。这使得用户可以获得对整个类别预测背后模式的高级理解,例如识别出致突变化合物中常见的 官能团。这种原型化能力为深入理解 GNN 在类别层面上的行为提供了强大的工具。
6.2. 消融实验/参数分析
论文中没有明确提及独立的消融实验章节,但其方法设计中包含了对解释大小 () 和特征数量 () 的超参数控制,以及多项正则化项(结构掩码离散性、特征掩码离散性、图大小惩罚、拉普拉斯约束),这些都隐含了对模型不同组件和约束有效性的考虑。通过调整这些超参数,可以在解释的紧凑性、连通性和准确性之间进行权衡。例如,正则化项的引入旨在确保解释的离散性、连通性及避免过大。
7. 总结与思考
7.1. 结论总结
本文提出了 GNNExplainer,这是一种新颖且开创性的方法,用于解释图神经网络 (GNNs) 在任何图基机器学习任务中的预测。它的核心创新在于能够通用地、模型无关地提供可解释的解释,而无需修改或重新训练底层的 GNN 架构。GNNExplainer 通过将解释问题形式化为最大化 GNN 预测与解释子图之间互信息的优化任务,有效地识别出对特定预测至关重要的紧凑子图结构和少量节点特征。
实验结果在合成和真实世界图上都强有力地验证了 GNNExplainer 的有效性。它在解释准确率方面显著优于梯度 (GRAD) 和注意力 (ATT) 等基线方法,并且能够识别出语义上相关且对领域专家有价值的结构(如分子图中的致突变基团、社交网络中的互动模式)。此外,GNNExplainer 还具备通过图原型生成多实例解释的能力,从而提供对整个类别预测背后共享模式的高级洞察。GNNExplainer 为理解 GNN 预测、调试模型和识别系统性错误模式提供了一个直观而强大的接口。
7.2. 局限性与未来工作
论文在附录中讨论了多实例解释面临的挑战,并将其作为未来研究的方向:
- 多实例解释的计算复杂性: 论文指出,为一组解释找到共同组件(例如,最大公共子图)是一个具有挑战性的问题,尤其是当节点邻域结构存在噪声和变异时。图对齐(graph alignment)本身就是一个计算密集型问题,找到两个大型图之间的最佳匹配在实践中很困难,尤其是在存在噪声和结构变异的情况下。
- 图对齐方法的局限性: 尽管 GNNExplainer 通过生成小图来缓解了对齐的难度,但论文也承认,神经方法在寻找两个大型图的良好最优匹配方面通常并非易事。未来的工作可能需要设计更高效、更鲁棒的图对齐算法或启发式方法。
7.3. 个人启发与批判
7.3.1. 个人启发
- 将解释性问题形式化为优化问题: GNNExplainer 将解释性问题巧妙地转化为一个可优化的数学问题(最大化互信息或最小化交叉熵),这提供了一个坚实且可量化的框架,而不是仅仅依赖启发式方法。这种从信息论角度出发的设计非常优雅和强大。
- 结构和特征的联合学习: 图数据本身就包含结构和节点特征两方面信息,GNN 的强大之处也正在于能同时利用二者。GNNExplainer 能够同时识别结构掩码和特征掩码,这是对图数据本质的深刻理解和有效利用,也是其优于只关注单一方面的基线方法的关键。
- 模型无关性 (Model-Agnostic): GNNExplainer 的模型无关特性使其具有广泛的适用性,可以应用于各种 GNN 架构而无需进行特定修改,极大地降低了其应用门槛和成本。这对于快速发展的 GNN 领域尤为重要。
- 图原型的潜力: 多实例解释,特别是通过图原型来总结一个类别共有的结构模式,为理解 GNN 在更高抽象层次上的行为提供了强大工具。这对于科学发现(如分子生物学中发现新的功能基团)或社交网络分析(如识别特定社区的互动模式)具有巨大潜力。
- 对 GNN 调试的价值: 能够识别出 GNN 预测所依赖的关键结构和特征,对于 GNN 的调试和错误分析至关重要。当模型做出错误预测时,解释可以帮助开发者理解错误的根源,从而指导模型改进或数据清洗。
7.3.2. 批判
- 连续松弛和变分近似的理论局限性: 尽管论文指出实验效果良好,但将离散的子图选择问题松弛为连续的邻接矩阵,并使用均场变分近似来优化目标,理论上可能无法保证找到全局最优解,甚至可能收敛到次优的局部最小值。对于某些复杂的图结构,这种近似可能引入偏差。
- 超参数敏感性: 解释子图的最大大小 和最大特征数量 需要预先设定。这些参数的选择往往依赖于先验知识或经验,其设定可能会显著影响解释的紧凑性和完整性。例如,如果 太小,可能无法捕获到所有重要的上下文;如果太大,解释又会变得冗余。缺乏一种自适应或数据驱动的方法来确定这些参数可能是一个潜在的局限。
- 解释准确率评估的挑战: 对于合成数据集,存在明确的地面真值,因此 AUC 可以作为有效的评估指标。然而,在真实世界场景中,获取“真正的”解释(即 GNN 实际关注的结构和特征)本身就是一个难题。如果没有可靠的地面真值,解释的“准确性”将难以客观评估。这使得在实际应用中验证解释质量仍是一个开放且具有挑战性的问题。
- 多实例解释中图对齐的效率和鲁棒性: 论文在附录中承认了图对齐的挑战,特别是对于大型图或结构差异较大的图。尽管其生成的单实例解释是小图,缓解了部分难度,但对齐过程本身的计算成本和在噪声环境下的鲁棒性仍值得进一步探究。如果对齐不准确,生成的原型可能无法真实反映类别的共同模式。
- 对 GNN 模型性能的依赖: GNNExplainer 的目标是解释 GNN 的预测,而非改进 GNN 本身。如果 GNN 模型本身的性能很差或学习到了错误的模式,GNNExplainer 可能会准确地解释这些“错误”的决策,但其提供的洞察可能并无益处,甚至会强化对错误模型的信任。因此,一个“好的”解释器需要与一个“好的”预测模型协同工作。
相似论文推荐
基于向量语义检索推荐的相关论文。