ICML 2021 | 针对图神经网络的通用因果解释方法

论文标题｜ Generative Causal Explanations for Graph Neural Networks
论文来源｜ ICML 2021
论文链接｜ https://arxiv.org/abs/2104.06643
源码链接｜ https://github.com/wanyu-lin/ICML2021-Gem

TL;DR

论文中提出了一种通用的因果解释方法 Gem，可以为不同图学习任务中的 GNNs 提供通用的可解释性。主要想法是将 GNNs 模型的推理决策可解释性问题转为一个因果学习任务，然后基于格兰杰因果 (Granger causality) 的目标函数来训练一个因果解释模型。Gem 不依赖于 GNNs 的内部结构和图学习任务相关的先验知识，因此泛化性较强而且可以从图结构数据的因果角度来解释 GNNs ~ 保持好奇 🧐。实验部分在生成数据集和真实数据中验证了 Gem 相对其它解释模型而言，可以提升 30% 的解释准确性而且解释速度可达 110×。

Problem Definition

由于 GNNs 模型的可解释性研究是一个新兴的研究领域，当前主流的研究工作如下 Mark 🐶

GNNExplainer: [NeurIPS 2019] Generating Explanations for Graph Neural Networks
PGExplainer：[NeurIPS 2020] Parameterized Explainer for Graph Neural Network
PGM-Explainer: [NeurIPS 2020] Probabilistic Graphical Model Explanations for Graph Neural Networks
XGNN：[KDD 2020] Towards Model-Level Explanations of Graph Neural Networks

以上方法都是基于图结构或者加性特征归因 (addittive feature attribution) 的方法来解释 GNNs 的推理结果，泛化性较差而且没有从因果层面来考虑。

而这篇文章从因果模型来解释 GNNs，希望这一篇文章可以解决我多年前对 GNNs 因果推理的疑惑 🤔

首先好奇会以什么形式来解释 GNNs ⁉️

一般的图学习任务定义如下：

给定图集合 $\mathcal{G}=\{G_i\}^N_{i=1}, |\mathcal{G}|=N$ ，每个图表示为 $G_i=(V_i, E_i)$ ，其节点集合为 $V_i=\{v_1^i, v_2^i,\cdots, v_{|V_i|}^i\}$ ，对应的每个节点特征维度为 $X_i=\{x_1^i, x_2^i,\cdots, x_{|V_i|}^i\}, x_j^i\in \mathbb{R}^d$ 。论文中考虑在 Graph-level 和 Node-level 级别的分类任务来解释 GNNs。

对于 Graph-level 分类任务的数据集为 $\mathcal{D}=\{(G_i, y_i)\}_{i=1}^N$ ，每个图 $G_i$ 其对应的标签为 $y_{i} \in \mathcal{Y}=\left\{c_{1}, c_{2}, \cdots, c_{l}\right\}$ ，其中 $l$ 表示类别数量。
对于 Node-level 分类任务的数据集为 $\mathcal{D}=\{(v_j, y_j)\}_{j=1}^{|V|}$ ，每个图 $G$ 中的节点 $v_j\in V$ 对应的标签为 $y_i\in \mathcal{Y}$ 。

论文中使用示例 $I_i$ 表示一个实例，在 Graph-level 中对应 $G_i$ ，在 Node-level 中对应 $v_j$ 。所以下文谈到的实例可以为 Graph or Node。

GNNs 模型可以形式化化地表示如下：

Graph-level： $f(\cdot): \mathcal{G}\rightarrow \mathcal{Y}$
Node-level: $f(\cdot): \mathcal{V}\rightarrow \mathcal{Y}$

对应的目标函数如下， $\mathcal{L}: y \times \tilde{y} \rightarrow s$ ，其中 $y$ 表示真实分类， $\tilde{y}$ 表示预测输出，标量 $s\in \mathbb{R}$ 表示对应的损失。

模型解释的任务是给定一个预训练模型 $f(·)$ ，得到模型 $f(\cdot)_{exp}$ 对预训练模型进行快速精确的解释，预训练模型被称为 target GNN。

解释下 GNNs 模型的解释形式：

Intrinsically, an explanation is a subgraph that is the most relevant for a prediction —— the outcome of the target GNN.

个人理解：对于预测模型的预测输出，需要找到原图中的对应的子图来支持这一分类结果，找到子图这一过程由解释模型完成。这个子图作用在于？

Algorithm/Model

论文中提出的模型如下图所示

主要包括两个模块：

Distillation process：对于图中的边进行因果贡献分数计算。
Graph generator：根据 distillation 得到的子图监督训练图生成模型。

因果贡献

GNNs 对于一个实例的预测结果主要在于图结构 computation graph $G_{i}^{c}=\left(V_{i}^{c}, A_{i}^{c}, X_{i}^{c}\right)$ ，其中 $A_i^c\in \{0,1\}$ 表示邻接矩阵。

GNN 的目标是学习到一个分类条件分布 $\mathcal{P}(Y|G_i^c)$ 。

一个计算图示例如下，对于节点 $i$ 的 2-hop。

给定预训练的 GNNs 模型和对应的实例 $G^c$ ，其对应的分类结果为 $\tilde{y}=p(Y|G^c)$ ，所以解释模型的任务是找到预测结果 $\tilde{y}$ 对应的子图 $G^s$ 。

考虑到格兰杰因果的主要思想，可以量化图中边 $e_j\in G^c$ 对预训练 GNN 模型预测误差 $\delta_{G^c}$ 的因果贡献。

$\Delta_{\delta, e_{j}}=\delta_{G^{c} \backslash\left\{e_{j}\right\}}-\delta_{G^{c}}$

这样就可以计算删除边 $e_j$ 对模型的因果贡献，其预测误差即为损失函数计算得到的值。计算方式如下

$\begin{aligned} \tilde{y}_{G^{c}}&=f\left(G^{c}\right),\\ \tilde{y}_{G^{c} \backslash\left\{e_{j}\right\}}&=f\left(G^{c} \backslash\left\{e_{j}\right\}\right)\\ \delta_{G^{c}} &=\mathcal{L}\left(y, \tilde{y}_{G^{c}}\right) \\ \delta_{G^{c} \backslash\left\{e_{j}\right\}} &=\mathcal{L}\left(y, \tilde{y}_{G^{c} \backslash\left\{e_{j}\right\}}\right) \end{aligned}$

利用删除边的策略来计算因果贡献这种方法论文中将之称为ground-truth distillation process.

通过计算图中所有边的因果贡献，可以直接根据贡献分数排序来选择 top-K 最相关的边作为预测解释。但是图数据中的边贡献分布并不是独立的，因此作者使用 graph rules 来提高 distillation 过程。这一步就比较玄学了，完全取决于数据特征，但是大部分应该考虑了 top-K distillation edges 应该是连通的。

以上蒸馏过程中得到的子图表示为 $\tilde{G}^{s} = \left(\tilde{V}^{s}, \tilde{A}^{s}, \tilde{X}^{s}\right)$ ，~~可以根据其它模型的输出来进行有监督的，以此来解释其它模型~~