GNNExplainer

论文名称：GNNExplainer: Generating Explanations for Graph Neural Networks

论文地址：https://arxiv.org/abs/1903.03894

GNN使用节点的特征和图的结构作为信息沿着边传递。这种整合使得模型的可解释性更加困难。我们建议的模型GNNEXPLAINER，是一种与模型无关的，可以为任何的GNN模型提供解释。GNNEXPLAINER能够识别子图的结构和节点的特征，然后，对样本的实例作出解释。GNNEXPLAINER作为优化器，最大化GNN预测任务和子图结构之间的互信息，能够识别重要的图结构和特征。

GNNEXPLAINER将 trained GNN and its prediction(s)作为输入，返回输入图的子图和对预测结果产生影响的特征（Figure 1）。该方法是与模型无关的，可以解释基于GNN的机器学习任务，包括：节点分类、链路预测、图分类，它可以处理单条和多条样本。当处理单条样本时，GNNEXPLAINER针对该样本进行解释。（a node
label, a new link, a graph-level label）。当处理多条样本时，针对该样本集合进行解释。

GNNEXPLAINER用GNN训练时整个图的子图进行解释，该子图最大化与预测值之间互信息。

1. Formulating explanations for graph neural networks

设图为$G$, 边为$E$, 节点为$V$, 节点的特征为$d$ 维， X = { x 1 , … , x n } , x i ∈ R d \mathcal{X}=\left\{x_{1}, \ldots, x_{n}\right\}, x_{i} \in \mathbb{R}^{d} X={x1​,…,xn​},xi​∈Rd，其中， $n$是节点的数量。$f$是节点label的映射函数。 f : V ↦ { 1 , … , C } f: V \mapsto\{1, \ldots, C\} f:V↦{1,…,C}， 将$V$中的每个节点映射为$C$类， GNN模型$\Phi$在所有训练节点上进行优化，对新的节点进行预测。

1.1 Background on graph neural networks

在$l$层， GNN模型包括关键三步。（1）第一步，计算节点对$(v_i,v_j)$之间的message, ${\mathbf{h}}_i^{l-1}$和 ${\mathbf{h}}_j^{l-1}$分别是前一层节点$i$和节点$j$的表示， $r_{ij}$是两个节点之间的关系： $m_{ij}^l=\mathrm{MSG}\left({\mathbf{h}}_i^{l-1},{\mathbf{h}}_j^{l-1},r_{ij}\right)$（2），第二步，对于每个节点$v_i$, GNN汇总aggregates它的邻居${\mathcal{N}}_{v_i}$的信息, aggregated message $M_i$的计算方式：$M_i^l=\mathrm{AGG}\left(\left\{m_{ij}^l\mid v_j\in {\mathcal{N}}_{v_i}\right\}\right)$. 其中${\mathcal{N}}_{v_i}$是节点$v_i$的邻居的节点，它的定义不同会产生不同的GNN变种。（3）GNN 使用聚合函数$M_i^l$聚合节点$v_i$的representation ${\mathbf{h}}_i^{l-1}$, 然后进行非线性转换获得节点$v_i$的节点在$l$层表示${\mathbf{h}}_i^l$: ${\mathbf{h}}_i^l=\mathrm{UPDATE}\left(M_i^l,{\mathbf{h}}_i^{l-1}\right)$, 然后经过$L$层获得最后的输出: ${\mathbf{z}}_i={\mathbf{h}}_i^L$。

1.2 GNNEXPLAINER: Problem formulation

我们处理问题的关键是节点$v$的计算，将节点邻居的信息进行汇总，产生节点$v$的预测$\hat{y}$。节点$v$的最终输出为$\mathbf{z}$. 图$G_c(v)$的计算与临接矩阵 A c ( v ) ∈ { 0 , 1 } n × n A_{c}(v) \in\{0,1\}^{n \times n} Ac​(v)∈{0,1}n×n和节点特征 X c ( v ) = { x j ∣ v j ∈ G c ( v ) } X_{c}(v)=\left\{x_{j} \mid v_{j} \in G_{c}(v)\right\} Xc​(v)={xj​∣vj​∈Gc​(v)}有关。GNN模型$\Phi$学习$Y$的概率分布$P_{\Phi }\left(Y\mid G_c,X_c\right)$， 其中$Y$代表标签$1,\cdots ,C$随机变量，即每个节点属于$C$类中每个类别的概率。

GNN的预测$\hat{y}=\Phi \left(G_c(v),X_c(v)\right)$，模型$\Phi$主要是由图的结构信息$G_c(v)$和节点的特征$X_c(v)$决定的。一般地， GNNEXPLAINER将预测值 $\hat{y}$ 解释为$\left(G_S,X_S^F\right)$， 其中$G_S$是预测图的子图，$X_S$是$G_S$的节点特征，$X_S^F$是$G_S$中节点的子集（通过$F$进行mask， X S F = { x j F ∣ v j ∈ G S } X_{S}^{F}=\{x_{j}^{F} \mid v_{j} \in G_S\} XSF​={xjF​∣vj​∈GS​} )。

2 GNNEXPLAINER

接下来，我们介绍一下 GNNEXPLAINER 如何在单条（2.1， 2.2）和多条（2.3）上的预测进行模型解释。最后介绍GNNEXPLAINER在机器学习任务上的应用（2.4），如链路预测和图分类。

2.1 Single-instance explanations

给定一个节点$v$， 我们的目标是识别子图$G_S\subseteq G_c$和相关特征 X S = { x j ∣ v j ∈ G S } X_S=\left\{x_{j} \mid v_{j} \in G_{S}\right\} XS​={xj​∣vj​∈GS​}, 这些对于GNN预测$\hat{y}$ 是非常重要的。现在，我们假设$X_S$是子集节点的特征, $d$维。在2.2将要讨论哪一维特征能够对模型进行解释。使用互信息$MI$衡量重要性， GNNEXPLAINER优化框架如下：
$$\underset{G_S}{\max }MI\left(Y,\left(G_S,X_S\right)\right)=H(Y)-H\left(Y\mid G=G_S,X=X_S\right)\text{\hspace{1em}(1)}$$
对于节点$v$, $MI$是衡量是当计算图被限制在子图$G_S$，节点特征被限制在$X_S$时，预测概率$\hat{y}=\Phi \left(G_c,X_c\right)$的变化。

举例来说，$v_j\in G_c\left(v_i\right),v_j\ne v_i$，如果移除$v_j$, ${\hat{y}}_i$的概率显著下降， 则节点$v_j$就是很好反事实解释。类似地，$\left(v_j,v_k\right)\in G_c\left(v_i\right),v_j,v_k\ne v_i$，如果移除$v_j$和$v_k$之间的边，${\hat{y}}_i$ 的预测概率值显著下降，则$v_j$和$v_k$之间的边是很好的反事实解释。

在Eq.(1)中， 交叉项$H(Y)$是常数，因为模型$\Phi$已经训练好，因此，最大化$Y$和$(G_S,X_S)$之间的互信息等于最小化条件熵$H\left(Y\mid G=G_S,X=X_S\right)$，如下：
$$H\left(Y\mid G=G_S,X=X_S\right)=-{\mathbb{E}}_{Y\mid G_S,X_S}\left[\log P_{\Phi }\left(Y\mid G=G_S,X=X_S\right)\right]\text{\hspace{1em}(2)}$$
以子图$G_S$对$\hat{y}$ 进行解释, 实际上最小化 $\Phi$的不确定性。实际上，最大化概率$\hat{y}$。为了给出简介的解释，我们给$G_S$增加限制：$\left|G_S\right|\le K_M$， 其中$G_S$最多有$K_M$个节点。这意味着， GNNEXPLAINER通过$K_M$边消除$G_C$的噪声，给出预测的最大互信息。

GNNEXPLAINER’s optimization framework. 对于$G_c$来说，用于解释$\hat{y}$ 的子图$G_S$非常多，直接处理是非常困难的。我们考虑部分邻接矩阵的方式：$A_S[j,k]\le A_c[j,k]$，其中，$A_S\in [0,1{]}^{n\times n}$， 对于所有$j,k$增加以上限制。这个近似可以理解为子图是$G_c$的近似。我们将$G_S\sim \mathcal{G}$看做图的随机变量，目标函数Eq.(2)可以变换为：
$$\underset{\mathcal{G}}{\min }{\mathbb{E}}_{G_S\sim \mathcal{G}}H\left(Y\mid G=G_S,X=X_S\right)\text{\hspace{1em}(3)}$$
由于凸的假设，使用Jensen不等式给出上限：
$$\underset{\mathcal{G}}{\min }H\left(Y\mid G={\mathbb{E}}_{\mathcal{G}}\left[G_S\right],X=X_S\right)\text{\hspace{1em}(4)}$$
在实际中，由于神经网络的复杂性，凸的假设是不成立的，但是，最小化这个目标函数和正则项通常会带来比较的解释。

为了估计${\mathbb{E}}_{\mathcal{G}}$, 我们将其分解为multivariate Bernoulli distribution：$P_{\mathcal{G}}\left(G_S\right)={\prod }_{(j,k)\in G_c}{A}_S[j,k]$，其中$A_S$的$(j,k)\text{-th}$条目代表边$(v_j,v_k)$之间是否有边存在。我们经验发现，使用正则项可以使得分解值收敛局部最小，即使GNN是非凸的。将Equation 4中${\mathbb{E}}_G[G_S]$替换为masking 邻接矩阵$A_c\odot \sigma (M)$进行优化 ，$M\in {\mathbb{R}}^{n\times n}$指的是Mask，$\odot$指element-wise乘积，$\sigma$ 指的是将mask映射为$[0,1{]}^{n\times n}$.

在一些应用中，用户更关注如何将训练的模型用于预测想要的label。我们需要修改Equation4：
$$\underset{M}{\min }-\sum _{c=1}^{C}1[y=c]\log P_{\Phi }\left(Y=y\mid G=A_c\odot \sigma (M),X=X_c\right)\text{\hspace{1em}(5)}$$
该公式 使用Mask机制，将$\sigma (M)$和$A_c$进行乘积，移除$M$中小的值，以达到用子图$G_S$解释GNN对节点$v$的预测值$\hat{y}$进行解释的作用。

2.2 Joint learning of graph structural and node feature information

为了识别节点特征对预测值$\hat{y}$的重要性， GNNEXPLAINER学习$G_S$节点特征$F$选择器。与节点所有特征不同， X S = { x j ∣ v j ∈ G S } X_{S}=\left\{x_{j} \mid v_{j} \in G_{S}\right\} XS​={xj​∣vj​∈GS​}， GNNEXPLAINER考虑$G_S$的子集特征$X_S^F$， 特征的选择通过二值特征选择器 F ∈ { 0 , 1 } d F \in\{0,1\}^{d} F∈{0,1}d（Figure 2B）：
$$X_S^F=\left\{x_j^F\mid v_j\in G_S\right\},x_j^F=\left[x_{j,t_1},\dots ,x_{j,t_k}\right]\text{ for }{F}_{t_i}=1\text{\hspace{1em}(6)}$$
其中，$x_j^F$是没有被$F$ mask out的节点特征。$(G_S,X_S)$进行联合优化以最大化互信息：
$$\underset{G_S,F}{\max }MI\left(Y,\left(G_S,F\right)\right)=H(Y)-H\left(Y\mid G=G_S,X=X_S^F\right)\text{\hspace{1em}(7)}$$
该方程对Eq.(1)目标函数进行调整，同时考虑结构和节点特征两个方面，对预测$\hat{y}$进行解释。

Learning binary feature selector $F$. 我们设$X_S=X_S\odot F$, 其中$F$是需要学习的参数。如果某个特征不重要，GNN会使得它的权重为0. 实际上，若果这个特征不重要，移除这个特征预测值不会有太大的变化，如果这个特征重要，预测值会显著下降。但是这种方法会忽略一些特征很重要，但是取值接近0。为了解决这个问题，在训练的过程中，我们使用蒙特卡洛从节点$X_S$的边缘经验分布抽样。然后，我们使用参数化技巧进行反向传播，学习feature mask $F$。特别地，随机变量$X$计算如下：$X=Z+\left(X_S-Z\right)\odot F$ s.t. ${\sum }_j{F}_j\le K_F$，其中$Z$是从经验分布抽样的$d$维随机变量，$K_F$是保留的最大特征的数量，是可学习的参数。

Integrating additional constraints into explanations. 为了强化可解释性，我们可以对Eq.(7)增加正则项。例如，为了使得structural and node feature masks to be discrete， 我们使用element-wise entropy，或者增加特定领域限制，如，拉格朗日正则项。我们也可以将mask的元素求和，作为正则项。

最后，需要注意的是对GNN进行解释必须是一个有效的计算图。因为解释$\left(G_S,X_S\right)$必须允许GNN的message能够流向节点$v$, 以此来预测$\hat{y}$. 重要的是， GNNEXPLAINER 自动可以提供有效计算图，因为它会在整个图上优化structural mask。如果边是没有连接的，它不会被选择，不会影响最终GNN预测。

2.3 Multi-instance explanations through graph prototypes

我们的目标是分析子图如何对一类标签进行解释， GNNEXPLAINER能够基于 graph alignments and prototypes对多实例进行解释。

首先，我们先选择一个类别$c$的参考样本样本点，例如，将其他节点embedding的均值赋值$c$。我们利用$G_S(v_c)$对$v_c$进行解释，然后将解释赋值给这个类别$c$的其他节点。如果在大图中，进行匹配是非常具有挑战性的。但是单条样本产生是一个小图，而且near-optimal pairwise graph matchings是非常高效的。

其次，我们将邻接矩阵进行汇总给a graph prototype $A_{\text{proto}}$, 例如计算中位数. $A_{\text{proto}}$用于识别graph patterns，它在同类别中是共享的。可以用于预测和模型解释。

2.4 GNNEXPLAINER model extensions

Any machine learning task on graphs. 除了能够解释节点分类，在不需要修改优化算法的情况下，GNNEXPLAINER可以用于链路预测和图分类。当对$(v_j,v_k)$进行链路预测时，GNNEXPLAINER会学习$X_S(v_j)$和$X_S(v_k)$两个mask。当进行图分类时，会将我们想解释图的所有邻接矩阵进行union.

Any GNN model. 现在GNN主要基于 message passing构建各种结构， GNNEXPLAINER能够对它们进行解释。

Computational complexity. GNNEXPLAINER的优化取决于计算图$G_c$的大小, $G_c(v)$的邻接矩阵$A_c(v)$等于mask $M$的大小，需要GNNEXPLAINER学习。但是，通常来说，计算图相对较小， 即使输入大图 ，GNNEXPLAINER也能对其进行有效的解释。