GNN （其它）

一、Deeper Insights into GCN[2018]

1. 众所周知训练深度神经网络通常需要大量的标记数据。由于获得标记样本的成本较高，因此在很多情况下无法大量标记数据的需求无法满足。为了降低模型训练所需的标记数据量，最近很多研究集中在fewshot learning 上：学习一个分类模型，其中每个类别只有很少的标记数据。和 fewshot learning 密切相关的是半监督学习，其中大量未标记数据来辅助训练少量的标记数据。很多研究表明：如果使用得当，在训练中使用未标记数据可以显著提升模型的预测能力。

   关键问题是如何最大程度地有效利用未标记数据的结构信息和特征信息。目前已有一些基于神经网络的半监督学习模型取得成功，包括 ladder network, semi-supervised embedding, planetoid, graph convolutional network 。

   最近的图卷积神经网络 graph convolutional neural networks: GCNN 成功地推广了CNN 来处理图结构数据。《Semisupervised classification with graph convolutional networks》 提出了一种简化的 GCNN模型，称作图卷积网络 GCN ，并将其应用于半监督分类中。GCN 模型很自然地融合了图结构信息和节点特征信息，并在某些 benchmark 上明显优于许多 state-of-the-art 的方法。

   但是，GCN 模型面临很多其它神经网络模型类似的问题：

   • 用于半监督学习的 GCN 模型的工作机制尚不清楚。
   • 虽然 GCN 只需要少量的标记数据用于训练，但是GCN 仍然需要大量标记数据作为验证集从而用于超参数调优和模型选择。这违背了半监督学习的目的。

   论文 《Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning》 深入洞察 GCN 模型，并提出：GCN 模型的图卷积只是拉普拉斯平滑的一种特殊形式，这种平滑混合了节点及其周围邻域的特征。平滑操作使得同一个簇 cluster 中节点的特征相似，从而大大简化了分类任务，这是 GCN 表现出色的关键原因。

   但是，这也会带来过度平滑 over-smoothing 的潜在风险。如果 GCN 有很多层的卷积层，则最终输出的特征可能过于平滑，使得来自不同 cluster 之间的节点变得难以区分。如下图所示为 karate club 数据集分别使用 1、2、3、4、5 层 GCN 训练的节点 embedding 可视化的结果，不同颜色表示不同的类别。可以看到，随着卷积层数量的增加，过度平滑很快发生。除此之外，使用很多层的卷积层也使得训练变得更加困难。

   

   但是卷积层数量太少也会有问题。在半监督学习中标记数据太少，这使得浅层 GCN 无法将标签信息有效地传播到整个图。这就是卷积滤波器局部性带来的困扰。如下图所示（Cora 数据集），随着训练的标签数据的减少，GCN 性能迅速下降。即使采用了额外的 500 个标记样本作为验证集（图中的 GCN with validation 曲线），GCN 的性能也是迅速下降。

   

   为了克服 GCN 模型的缺陷并实现模型的全部潜力，论文提出了一种共同训练Co-Training 方法和一种自训练 Self-Training 方法来训练 GCN。

   • 通过将 GCN 和随机游走模型共同训练，从而利用随机游走模型补充 GCN 在探索全局图拓扑结构方面的不足。
   • 通过自训练，从而利用 GCN 的特征抽取能力来克服卷积滤波器的局部性。

   通过将 Co-Training 和 Self-Training 相结合，可以大大改善带少量标记数据的半监督学习的 GCN 模型，并使得它不需要额外的标记数据进行验证。如上图所示，论文提出的方法（红色曲线）在很大程度上超越了 GCN 的表现。

   论文贡献：

   • 对半监督 GCN 模型提供了新的洞察和分析。
   • 提出了改进半监督 GCN 模型的解决方案。

1.1 基本原理和相关工作

1. 给定图 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$$\mathcal G=(\mathcal V, \mathcal E,\mathbf X)$ ，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ 为节点集合， $\mathcal{E}$$\mathcal E$ 为边集合，$\mathbf{X}=[{\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_n{]}^{\mathrm{\top }}\in {\mathbb{R}}^{n\times d_f}$$\mathbf X = [\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_n]^\top\in \mathbb R^{n\times d_f}$ 为节点的特征矩阵，${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$\mathbf{\vec x}_i\in \mathbb R^{d_f}$ 为节点 $v_i$$v_i$ 的特征向量，$d_f$$d_f$ 为特征维度。注意，为简单起见，这里我们仅讨论无向图。

   定义非负的邻接矩阵 $\mathbf{A}=[a_{i,j}]\in {\mathbb{R}}^{n\times n}$$\mathbf A = [a_{i,j}]\in \mathbb R^{n\times n}$ ；定义度矩阵 $\mathbf{D}=\text{diag}(d_1,\cdots ,d_n),d_i=\sum _j{a}_{i,j}$$\mathbf D = \text{diag}(d_1,\cdots,d_n), d_i=\sum_{j} a_{i,j}$ ；定义图拉普拉斯矩阵 $\mathbf{L}=\mathbf{D}-\mathbf{A}$$\mathbf L = \mathbf D - \mathbf A$ 。定义归一化的图拉普拉斯矩阵为：对称版本为 ${\mathbf{L}}_{\text{sym}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$$\mathbf L_{\text{sym}} = \mathbf D^{-1/2}\mathbf L \mathbf D^{-1/2}$ 、非对称版本为 ${\mathbf{L}}_{\text{rw}}={\mathbf{D}}^{-1}\mathbf{L}$$\mathbf L_{\text{rw}} = \mathbf D^{-1}\mathbf L$ 。

   这里我们只考虑图上的半监督分类问题。假设标记节点集合为 ${\mathcal{V}}_l$$\mathcal V_l$，剩余的未标记节点集合为 ${\mathcal{V}}_u=\mathcal{V}-{\mathcal{V}}_l$$\mathcal V_u = \mathcal V - \mathcal V_l$ 。其中 ${\mathcal{V}}_u$$\mathcal V_u$ 就是我们需要预测标签的节点集合。

1.1.1 基于图的半监督学习

1. 基于图的半监督学习利用数据的拓扑结构从而可以通过很少的标签进行学习。很多基于图的半监督学习方法都采用聚类假设 cluster assumption：假设图上距离相近的节点倾向于共享相同的标签。采用这种假设的方法包括：最小割min-cuts 、随机最小割randomized min-cuts、spectral graph transducer、标签传播 label propagation 及其变体、modified adsorption、iterative classification algorithm 。

   但是图仅仅代表拓扑结构信息，在很多应用场景中，数据还带有属性信息。如引文网络中，文档可以表示为描述其内容的 bag-of-words 向量。许多半监督学习方法试图联合建模图结构和特征属性。一个常见的想法是用一些正则器对supervised learner 进行正则化。例如：

   • LapSVM 使用流形正则化manifold regularization 从而通过拉普拉斯正则化器来正则化支持向量机。
   • deep semi-supervised embedding 用基于embedding 的正则器对深度神经网络进行正则化。
   • Planetoid 也通过联合预测一个节点的类别标签和上下文来正则化神经网络。

1.1.2 GCN

1. Graph convolutional neural networks: GCNN 将传统的卷积神经网络推广到图数据。GCNN 主要有两种类型：空间 GCNN、谱域 GCNN 。

   • 空间 GCNN 将卷积视为 patch operator ，它基于节点邻域信息为每个节点构建一个新的 representation 向量。

   • 谱域 GCNN 通过谱域分解图信号 $\overrightarrow{\mathbf{s}}\in {\mathbb{R}}^n$$\mathbf{\vec s}\in \mathbb R^n$，然后在谱分量 spectral component上应用谱域滤波器 $g_{\theta }$$g_\theta$ ：

     $$\begin{array}{c}\overrightarrow{\mathbf{y}}=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{s}}\\ {\theta }_i=g_{\theta }({\lambda }_i),\mathbf{K}=\left[\begin{array}{cccc}{\theta }_1& 0& \cdots & 0\\ 0& {\theta }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\theta }_n\end{array}\right]\end{array}$$

     其中：图信号 $\overrightarrow{\mathbf{s}}$$\mathbf{\vec s}$ 每个原始对应于每个节点上的一个标量值；谱域滤波器 $g_{\theta }$$g_\theta$ 是 ${\mathbf{L}}_{\text{sym}}$$\mathbf L_{\text{sym}}$ 特征值的函数；$\mathbf{K}$$\mathbf K$ 为卷积核；$\mathbf{U}$$\mathbf U$ 为拉普拉斯矩阵特征向量 eigenvector 组成的矩阵。

2. 谱域GCNN 需要显式计算图的拉普拉斯特征向量 eigenvector ，这对于很多实际的大图来讲是难以实现的。解决该问题的一种方法是对谱域滤波器进 $g_{\theta }$$g_\theta$ 进行 $K$$K$ 阶切比雪夫多项式近似：

   $$\begin{array}{c}{\tilde{\mathbf{L}}}_{\text{sym}}=\frac{2}{{\lambda }_{max}}{\mathbf{L}}_{\text{sym}}-\mathbf{I}\\ \overrightarrow{\mathbf{y}}=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{s}}\simeq \sum _{k=0}^K{\beta }_k{T}_k({\tilde{\mathbf{L}}}_{\text{sym}})\overrightarrow{\mathbf{s}}\end{array}$$

   其中：${\beta }_k$$\beta_k$ 为 $k$$k$ 阶切比雪夫多项式的系数，$T_k(\cdot )$$T_k(\cdot)$ 为 $k$$k$ 阶切比雪夫多项式。

   《Semisupervised classification with graph convolutional networks》 通过限定 $K=1$$K=1$ 来简化该模型，从而得到：

   $${\mathbf{H}}^{(l+1)}=\sigma \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

   其中：$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$\tilde{\mathbf A} = \mathbf A + \mathbf I$， $\tilde{\mathbf{D}}$$\tilde{\mathbf D}$ 为 $\tilde{\mathbf{A}}$$\tilde{\mathbf A}$ 的度矩阵；${\mathbf{H}}^{(l)}$$\mathbf H^{(l)}$ 为第 $l$$l$ 层的 hidden representation， ${\mathbf{H}}^{(0)}=\mathbf{X}$$\mathbf H^{(0)} = \mathbf X$ ；${\mathbf{W}}^{(l)}$$\mathbf W^{(l)}$ 为第 $l$$l$ 层的参数矩阵；$\sigma (\cdot )$$\sigma(\cdot)$ 为激活函数。

   这个简化的模型被称作 GCN。

1.1.3 采用 GCN 的半监督分类

1. 在 《Semisupervised classification with graph convolutional networks》 论文中，GCN 模型用于半监督分类。模型采用两层卷积层，并使用 softmax 分类器：

   $$\mathbf{Z}=\text{softmax}\left(\hat{\mathbf{A}}\text{ReLU}\left(\hat{\mathbf{A}}\mathbf{X}{\mathbf{W}}^{(0)}\right){\mathbf{W}}^{(1)}\right)$$

   其中： $\hat{\mathbf{A}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$\hat{\mathbf A} = \tilde{\mathbf D}^{-1/2}\tilde{\mathbf A} \tilde{\mathbf D}^{-1/2}$ ； ReLU(.) 为 ReLU 激活函数。

   损失函数为在所有标记数据上的交叉熵损失：

   $$\mathcal{L}=\sum _{v_i\in {\mathcal{V}}_l}\sum _{c=1}^C{y}_{i,c}\log z_{i,c}$$

   其中：

   • ${\mathcal{V}}_l$$\mathcal V_l$ 为标记的训练集，$C$$C$ 为类别数量。

   • ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 为节点 $v_i$$v_i$ 的类别标记的 one-hot 向量。 $y_{i,c}\in \{0,1\}$$y_{i,c}\in \{0,1\}$ 为${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 的第 $c$$c$ 个元素，表示节点 $v_i$$v_i$ 是否属于类别 $c$$c$ 。它满足：

     $$\begin{array}{c}\sum _{c=1}^C{y}_{i,c}=1\\ y_{i,c}\in \{0,1\}\end{array}$$

   • ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ 为节点 $v_i$$v_i$ 预测属于各类别的概率。 $z_{i,c}$$z_{i,c}$ 为 ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ 的第 $c$$c$ 个元素，表示节点 $v_i$$v_i$ 属于类别 $c$$c$ 的概率。它满足：

     $$\begin{array}{c}\sum _{c=1}^C{z}_{i,c}=1.0\\ 0.0\le z_{i,c}\le 1.0\end{array}$$

   GCN 模型很自然地在卷积中结合了图拓扑结构和节点属性，其中未标记节点的属性和附近的标记节点的属性混合，并通过多层 GCN 传播到图上。实验表明，在某些 benchmark 上（如引文网络），GCN 性能明显优于很多 state-of-the-art 方法。

   这里的半监督学习仅考虑监督损失，而并未考虑无监督损失。还有一些工作会同时考虑监督损失和无监督损失。

1.2 分析

1. 尽管 GCN 效果很好，但是我们还不清楚它的机制。这里我们仔细研究 GCN 模型，分析其原理并指出其局限性。

1.2.1 为什么 GCN 有效

1. 为分析 GCN 工作良好的原因，我们将其与最简单的全连接网络 fully-connected networks:FCN 进行比较，其中layer-wise 传播规则为：

   $${\mathbf{H}}^{(l+1)}=\sigma \left({\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

   可以看到 GCN 和 FCN 的区别在于：GCN 在 FCN 的左边乘以一个图卷积矩阵 graph convolution matrix $\hat{\mathbf{A}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$\hat{\mathbf A} = \tilde{\mathbf D}^{-1/2}\tilde{\mathbf A} \tilde{\mathbf D}^{-1/2}$ 。

   为分析图卷积矩阵的影响，我们在 Cora 引文网络上对比了 GCN 和 FCN 在半监督分类上的性能，其中每个类别有 20 个标记数据。对比结果如下表所示，可以看到：即使只有一层，GCN 也要比 FCN 效果好得多。

   

   首先我们考虑单层的 GCN 网络，它包含两步：

   • 通过对节点特征矩阵 $\mathbf{X}$$\mathbf X$ 应用图卷积，从而生成一个新的 representation 矩阵 $\mathbf{H}$$\mathbf H$ ：

     $$\mathbf{H}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}$$

   • 然后将新的 representation 矩阵 $\mathbf{H}$$\mathbf H$ 馈入一个全连接层。

   显然，图卷积是GCN 相对于 FCN 获得巨大性能提升的关键。

2. 拉普拉斯平滑：假设我们向图中每个节点添加一个自连接 self-connection ，则新的邻接矩阵为 $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$\tilde{\mathbf A} = \mathbf A + \mathbf I$ 。

   在输入特征每个维度上的拉普拉斯平滑 Laplacian Smoothing 定义为：

   $$h_i=(1-\gamma )x_i+\gamma \times \sum _{j=1}^n(\frac{{\tilde{a}}_{i,j}}{{\tilde{d}}_i}\times x_j),1\le i\le n$$

   其中：

   • $x_i$$x_i$ 为节点 $v_i$$v_i$ 在某个维度上的取值（标量）。
   • $h_i$$h_i$ 为节点 $v_i$$v_i$ 在该维度上拉普拉斯平滑结果（标量）。
   • $0<\gamma \le 1$$0\lt \gamma \le 1$ 为平滑参数，它控制当前节点 $v_i$$v_i$ 在该维度上取值及其邻域取值之间的权重。
   • ${\tilde{a}}_{i,j}$$\tilde a_{i,j}$ 为 $\tilde{\mathbf{A}}$$\tilde{\mathbf A}$ 的第 $i$$i$ 行、$j$$j$ 列元素； ${\tilde{d}}_i=\sum _j{\tilde{a}}_{i,j}$$\tilde d_i=\sum_{j}\tilde a_{i,j}$ 为节点 $v_i$$v_i$ 在新的邻接矩阵上的 degree 。

   我们以矩阵的形式重写拉普拉斯平滑：

   $$\mathbf{H}=\mathbf{X}-\gamma {\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{L}}\mathbf{X}=(\mathbf{I}-\gamma {\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{L}})\mathbf{X}$$

   其中 $\tilde{\mathbf{L}}=\tilde{\mathbf{D}}-\tilde{\mathbf{A}}$$\tilde{\mathbf L} =\tilde{\mathbf D} - \tilde{\mathbf A}$ 。

   令 $\gamma =1$$\gamma = 1$ 即仅使用邻域特征，则拉普拉斯平滑退化为：

   $$\mathbf{H}={\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{A}}\mathbf{X}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}$$

   这刚好就是图卷积公式。因此，我们将图卷积视为拉普拉斯平滑的一种特殊形式，称作对称拉普拉斯平滑 Symmetric Laplacian Smoothing 。注意：虽然 $\gamma =1$$\gamma=1$ 表示仅使用邻域特征，这里的平滑过程仍然包含当前节点的特征。因为每个节点都有一个自连接，所以每个节点都是自己的邻居。

   拉普拉斯平滑将节点的 representation 计算为自身以及邻域特征的加权平均。由于同一个 cluster 中的节点倾向于紧密连接 densely connected，因此平滑处理使得它们的 representation 彼此相似，这有助于后续的分类过程。从下图（ Cora 引文网络）可以看到，仅使用一次拉普拉斯平滑操作就能够带来巨大的性能提升。

   

3. 多层架构：从上图中我们也看到，虽然两层 FCN 相对于一层 FCN 有少许提升，但是两层 GCN 比一层 GCN 提升很大。这是因为在第一层 representation 上再次应用平滑会使得同一个 cluster 中节点的输出 representation 更为相似，进一步提升分类性能。

1.2.2 为什么失败

1. 我们已经表明：图卷积本质上是一种拉普拉斯平滑。一个自然的问题是，GCN 中应该包含多少卷积层？显然层数不是越多越好。一方面，深层 GCN 非常难以训练；另一方面，反复应用拉普拉斯平滑可能会混合来自不同 cluster 的节点的信息，使得它们无法区分。

   我们用 karate club 数据集为例。该数据集包含 34 个节点、78 条边、两种节点类型。我们将隐层维度设为 16，输出层维度为 2。每个节点的特征向量为节点的 one-hot 向量。可以观察到拉普拉斯平滑对该数据集的影响。

   • 在进行一次平滑之后，不同类型节点之间的区分不明显。
   • 在进行两次平滑之后，不同类型节点之间的区分相当明显。
   • 在进行更多次平滑之后，不同类型节点被混合 mixing。

   由于这是一个很小的数据集，而且两种类别节点之间存在很多连接，因此混合很快发生。

   

2. 我们即将证明：通过多次重复应用拉普拉斯平滑，图的每个连通分量 connected component 内的节点 representation 将收敛到相同的值。对于对称拉普拉斯平滑，它们将收敛到与节点的 degree 的平方根成正比。

   连通分量：任意两点之间都存在路径来访问。

   假设图 $\mathcal{G}$$\mathcal G$ 有 $k$$k$ 个连通分量 $\{{\mathcal{C}}_i{\}}_{i=1}^k$$\{\mathcal C_i\}_{i=1}^k$ ，对于第 $i$$i$ 个连通分量定义一个示性向量 ${\overrightarrow{\mathbf{q}}}^{(i)}\in {\mathbb{R}}^n$$\mathbf{\vec q}^{(i)}\in \mathbb R^n$ ，其定义为：

   $$\begin{array}{c}{q}_j^{(i)}=\{\begin{array}{ll}1,& v_j\in {\mathcal{C}}_i\\ 0,& \text{else }\end{array}\end{array}$$

   因此 ${\overrightarrow{\mathbf{q}}}^{(i)}$$\mathbf{\vec q}^{(i)}$ 向量中元素为 1 的项对应于属于第 $i$$i$ 个连通分量的节点。

   定理：如果一个图没有bipartite components，则对于任意信号 $\overrightarrow{\mathbf{s}}\in {\mathbb{R}}^n$$\mathbf{\vec s}\in \mathbb R^n$ 以及 $\alpha \in (0,1]$$\alpha \in (0,1]$ ，都有：

   $$\begin{array}{c}\underset{m\to +\mathrm{\infty }}{lim}{(\mathbf{I}-\alpha {\mathbf{L}}_{\text{rw}})}^m\overrightarrow{\mathbf{s}}=[{\overrightarrow{\mathbf{q}}}^{(1)},\cdots ,{\overrightarrow{\mathbf{q}}}^{(k)}]{\overrightarrow{\mathbf{w}}}_1\\ \underset{m\to +\mathrm{\infty }}{lim}{(\mathbf{I}-\alpha {\mathbf{L}}_{\text{sym}})}^m\overrightarrow{\mathbf{s}}={\mathbf{D}}^{-1/2}[{\overrightarrow{\mathbf{q}}}^{(1)},\cdots ,{\overrightarrow{\mathbf{q}}}^{(k)}]{\overrightarrow{\mathbf{w}}}_2\end{array}$$

   其中 ${\overrightarrow{\mathbf{w}}}_1\in {\mathbb{R}}^k,{\overrightarrow{\mathbf{w}}}_2\in {\mathbb{R}}^k$$\mathbf{\vec w}_1\in \mathbb R^k, \mathbf{\vec w}_2\in \mathbb R^k$ 。即它们分别收敛到 ${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 以及 ${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 的线性组合。

   证明：${\mathbf{L}}_{\text{rw}}$$\mathbf L_{\text{rw}}$ 和 ${\mathbf{L}}_{\text{sym}}$$\mathbf L_{\text{sym}}$ 有相同的 $n$$n$ 个特征值 eigenvalues，但是有不同的特征向量 eigenvectors 。如果图没有 bipartite components，则所有特征值都位于 [0,2) 之间。 则 ${\mathbf{L}}_{\text{rw}}$$\mathbf L_{\text{rw}}$ 和 ${\mathbf{L}}_{\text{sym}}$$\mathbf L_{\text{sym}}$ 对应于特征值 0 的特征空间 eigenspaces 分别由 ${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 以及 ${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 派生（即这些向量构成的线性空间）。

   对于 $\alpha \in (0,1]$$\alpha \in (0,1]$ ，则 $(\mathbf{I}-\alpha {\mathbf{L}}_{\text{rw}})$$\left(\mathbf I - \alpha \mathbf L_{\text{rw}}\right)$ 以及 $(\mathbf{I}-\alpha {\mathbf{L}}_{\text{sym}})$$\left(\mathbf I - \alpha \mathbf L_{\text{sym}}\right)$ 的特征值都落在区间 (-1,1] 。因此特征值 1 对应的特征空间分别由 ${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 以及 ${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 派生。

   由于 $(\mathbf{I}-\alpha {\mathbf{L}}_{\text{rw}})$$\left(\mathbf I - \alpha \mathbf L_{\text{rw}}\right)$ 以及 $(\mathbf{I}-\alpha {\mathbf{L}}_{\text{sym}})$$\left(\mathbf I - \alpha \mathbf L_{\text{sym}}\right)$ 的所有特征值的绝对值都小于等于 1，所以经过多次反复相乘之后，它们的结果收敛到特征值 1 对应的特征向量的线性组合，即 ${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 以及 ${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$\left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k$ 的线性组合。

3. 注意，由于每个节点都添加了额外的自连接，因此图中没有 bipartite component 。根据上述结论，过度平滑 over-smoothing 将使得节点之间特征难以区分从而有损于分类性能。

4. 上述分析总结了堆叠多层卷积层导致 GCN 过度平滑的问题，此外深层的 GCN 也难以训练。因此 《Semisupervised classification with graph convolutional networks》 使用的 GCN 采用两层卷积层。

   但是，由于图卷积是局部滤波器，即邻域节点的特征向量的线性组合，因此浅层 GCN 无法将标签信息充分传播到整个图上。如下图所示（Cora 数据集），随机训练标记数据的减少，GCN 算法的性能迅速下降。可以看到 GCN 准确率随着标记数据规模减少而下降的速度，要比 label propagation 下降速度快得多。由于标签传播label propagation 算法仅使用图结构，而 GCN 同时使用图结构和节点特征，因此这反应了 GCN 模型无法探索全局图结构。

   

5. GCN 的另一个问题是，它需要额外的验证集来实现早停，这本质上是需要额外的标记数据作为验证集来执行模型选择。如果我们不使用验证集来训练 GCN，则其性能会大大降低。如上图所示，不带验证集的 GCN 性能（GCN without validation）要比带验证集的 GCN 性能（GCN with validation）差得多。

   《Semisupervised classification with graph convolutional networks》 使用了额外 500 个标记数据作为验证集，这远多于训练标记数据。这是不可取的，因为这违反了半监督学习的目的。此外，这也使得 GCN 和其它方法的比较不公平，因为其它方法（如标签传播）可能根本不需要验证集。

1.3 解决方案

1. 我们总结了 GCN 模型的优缺点：

   • 优点：

     • 图卷积（拉普拉斯平滑）有助于分类问题。
     • 多层神经网络是功能强大的特征抽取器。

   • 缺点：

     • 图卷积是一个局部滤波器，在标记数据很少的情况下效果不理想。
     • 神经网络需要大量的标记数据作为验证集，从而进行模型选择。

     注：读者认为还有一个缺点是容易过度平滑。

   我们希望在克服缺点的同时充分利用 GCN 模型的优点。因此我们提出了 Co-Training、Self-Training 等思想。

1.3.1 Co-Training

1. 我们提出将 GCN 和随机游走模型一起共同训练，因为后者可以探索全局图结构，从而解决卷积局部性的问题。

   具体而言，我们首先使用随机游走模型找到最置信 confidence 的节点（即，每个标记节点的最近邻居），然后将它们添加到标记数据集合从而训练 GCN 。

   和 《Semisupervised classification with graph convolutional networks》 不同，我们直接在训练集上优化 GCN ，无需任何其它标记数据来作为验证集。

2. 我们使用 partially absorbing random walks:ParWalks 算法作为我们的随机游走模型。ParWalks 是一个二阶马尔科夫链，它在每个状态下都有部分吸收 partial absorption 。

   考虑下图的简单扩散过程：

   • 首先将单位能量（蓝色）注入到指定的节点。

   • 第一步，某些能量（红色）“存储” 在当前节点，剩余能量（蓝色）传播到邻居中。

   • 每当能量通过节点时，一部分能量就会保留在当前节点、剩余能量继续传播。

     随着该过程的持续，每个节点中存储的能量将累积，并且图中流动的能量越来越少。经过一定数量的step 后，几乎没有剩余能量流动，并且存储的能量总和几乎为 1 。

   

   正式地，考虑一个离散时间的随机过程 $X=\{X_t:t\ge 0\}$$X = \{X_t:t\ge 0\}$ ，状态空间为 $N=\{1,2,\cdots ,n\}$$N=\{1,2,\cdots,n\}$ ，其中初始状态 $X_0=i$$X_0 =i$ 是给定的。则下一个状态 $X_1$$X_1$ 是由转移概率 $P(X_1=j\mid X_0=i)=p_{i,j}$$P(X_1=j\mid X_0 = i) = p_{i,j}$ 来决定：

   $$\begin{array}{c}P(X_{t+2}=j\mid X_{t+1}=i,X_t=k)=\{\begin{array}{ll}1,& i=j,i=k\\ 0,& i\ne j,i=k,\\ P(X_{t+2}=j\mid X_{t+1}=i)=p_{i,j},& i\ne k\end{array}\end{array}$$

   即：如果前一个状态和当前状态是相同的，则下一个状态也永远保持不变；否则下一个状态和前一个状态无关、仅和当前状态有关（类似于普通的随机游走）。

   对于图 $\mathcal{G}$$\mathcal G$ ，定义图上的 ParWalks 转移概率为：

   $$\begin{array}{c}{p}_{i,j}=\{\begin{array}{ll}\frac{{\lambda }_i}{{\lambda }_i+d_i},& i=j\\ \frac{a_{i,j}}{{\lambda }_i+d_i},& i\ne j\end{array}\end{array}$$

   其中：

   • ${\lambda }_i\ge 0$$\lambda_i\ge 0$ 为任意参数。当 ${\lambda }_i>0$$\lambda_i\gt0$ 时我们说状态 $i$$i$ （或者说节点 $v_i$$v_i$ ）是一个吸收状态 absorbing state；当 ${\lambda }_i=0$$\lambda_i =0$ 时我们说状态 $i$$i$ （或者说节点 $v_i$$v_i$ ）是一个transient state 。
   • $a_{i,j}$$a_{i,j}$ 为节点 $v_i,v_j$$v_i,v_j$ 之间边的权重， $d_i$$d_i$ 为节点 $v_i$$v_i$ 的 degree 。

   定义 $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$\mathbf \Lambda = \text{diag}(\lambda_1,\cdots,\lambda_n)$ ，则 $\mathbf{\Lambda }$$\mathbf\Lambda$ 类似于一个正则化器，它控制每个节点的吸收状态， ${\lambda }_i$$\lambda_i$ 越大则 $p_{i,i}$$p_{i,i}$ 越大（意味着节点停留在原地的概率越大）。因此，我们称 $\mathbf{\Lambda }$$\mathbf\Lambda$ 为正则器矩阵 regularizer matrix。

   我们关心的是从节点 $v_i$$v_i$ 开始的随机游走被节点 $v_j$$v_j$ 吸收的概率 $r_{i,j}$$r_{i,j}$ 。令 $\mathbf{R}=[r_{i,j}]\in {\mathbb{R}}^{n\times n}$$\mathbf R = [r_{i,j}]\in \mathbb R^{n\times n}$ 为吸收概率矩阵，则可以证明：如果对于某个 $i$$i$ 有 ${\lambda }_i>0$$\lambda_i\gt 0$ ，则有 $\mathbf{R}=(\mathbf{\Lambda }+\mathbf{L}{)}^{-1}\mathbf{\Lambda }$$\mathbf R = (\mathbf\Lambda + \mathbf L)^{-1} \mathbf\Lambda$ 。

   我们可以求解 $\mathbf{R}$$\mathbf R$ 来得到每个标记数据的最近邻节点，但是涉及到矩阵的求逆。为降低计算复杂度，我们采用随机游走采样来快速逼近。

3. ParWalks 算法：

   • 输入：

     • 图拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$
     • 正则化器矩阵 $\mathbf{\Lambda }$$\mathbf\Lambda$

   • 输出：新的标记节点集合

   • 算法步骤：

     • 计算吸收概率矩阵 $\mathbf{R}=(\mathbf{\Lambda }+\mathbf{L}{)}^{-1}\mathbf{\Lambda }$$\mathbf R = (\mathbf\Lambda + \mathbf L)^{-1} \mathbf\Lambda$ 。

     • 对于每个类别 $k$$k$ ，假设 ${\mathcal{S}}_c$$\mathcal S_c$ 为类别 $c$$c$ 的标记节点集合，计算：

       $$p_i=\sum _{j\in {\mathcal{S}}_c}{r}_{i,j},\overrightarrow{\mathbf{p}}=(p_1,\cdots ,p_n{)}^{\mathrm{\top }}\in {\mathbb{R}}^n$$

       即计算每个节点 $v_i$$v_i$ 距离 ${\mathcal{S}}_c$$\mathcal S_c$ 中标记节点的吸收概率之和 $p_i$$p_i$ ，即每个节点隶属于类别 $c$$c$ 的置信度。 $\overrightarrow{\mathbf{p}}$$\mathbf{\vec p}$ 为置信度向量 confidence vector 。

       然后从 $\{p_1,\cdots ,p_n\}$$\{p_1,\cdots,p_n\}$ 中挑选 top - t 个节点，并将这些节点添加到标签 $c$$c$ 对应的训练标记数据。

       用随机游走来描述就是：观察哪些节点开始的随机游走序列最容易被类别为 $c$$c$ 的节点所吸收，那么就将这些节点视为类别 $c$$c$ 。

1.3.2 Self-Training

1. 让 GCN “看到” 更多标记数据的另一个方法是对 GCN 进行 self-train 。具体而言，我们首先通过给定的标记数据来训练 GCN，然后通过比较 softmax 得分为每个类别选择最置信的未标记数据，然后将这些未标记数据添加到对应的类别的标记数据集合中。然后，我们使用扩展的标记数据集合来训练 GCN，并使用预先训练好的 GCN 来作为初始化。

   GCN 发现的最置信的样本应该和标记数据共享相似（但不相同）的 representation，将它们添加到标记数据集合有助于训练更强大和准确的分类器。此外，它还在以下场景补充了 Co-Training 方法：当图具有很多孤立的、小的连通分量时，此时无法通过随机游走来传播标签。

   Co-Training 和 Self-Training 本质都是寻找最置信的未标记数据，从而将它们加入到标记数据中来扩充标记数据集。

   • Co-Training 是通过图结构来寻找最置信的节点，方法是基于随机游走寻找最近邻节点，无需模型参与。
   • Self-Training 是通过图结构和节点特征来寻找最置信的节点，方法是基于 GCN 模型寻找最相似节点。

2. Self-Training 算法：

   • 输入：训练好的 GCN 模型、图 $\mathcal{G}$$\mathcal G$

   • 输出：新的标记节点集合

   • 算法步骤：

     • 计算所有节点的预测输出：$\mathbf{Z}=\text{GCN}(\mathbf{X})\in {\mathbb{R}}^{n\times C}$$\mathbf Z = \text{GCN}(\mathbf X)\in \mathbb R^{n\times C}$
     • 对每个类别 $c$$c$ ，从 $\{z_{i,c}{\}}_{i=1}^n$$\{z_{i,c}\}_{i=1}^n$ 中找到 top - t 个节点，并将这些节点添加到标签 $c$$c$ 对应的训练标记数据。

3. 为提升标签多样性 diversity 并训练更鲁棒的分类器，我们提出联合 Co-Training 和 Self-Training 。具体而言：

   • 使用Co-Training 、Self-Training 分别挖掘出各自最置信的未标记节点。
   • 使用二者未标记节点的并集来扩充标记数据集合，并继续训练 GCN，这称为 Union。其中使用预先训练好的 GCN 来作为二次训练的初始化。
   • 使用二者未标记节点的交集来扩充标记数据集合，并继续训练 GCN，这称为 Intersection。其中使用预先训练好的 GCN 来作为二次训练的初始化。

   注意：我们在扩展的标记数据上训练 GCN，无需任何额外其它验证数据。只要扩展的标记数据包含足够多的正确的标记数据，则我们的方法就有希望训练出良好的 GCN 分类器。

4. 但是，训练一个 GCN 分类器需要多少标记数据？假设 GCN 层数为 $\tau$$\tau$，图的平均 degree 为 $\hat{d}$$\hat d$ ，则我们提出通过求解 ${\left(\hat{d}\right)}^{\tau }\times \eta \simeq n$$\left(\hat d\right)^\tau \times \eta \simeq n$ 来得到标记样本数量 $\eta$$\eta$ 的下界（根据定义有 $|{\mathcal{V}}_l|=\eta$$|\mathcal V_l| = \eta$）。背后的思想是：估计一个 $\tau$$\tau$ 层的 GCN 需要多少标记数据可以传播到整个图。

1.4 实验

1. 数据集：我们在三种常用的引文网络上进行实验：CiteSeer, Cora, PubMed。每个数据集上，文档采用 bag-of-word 特征向量，文档之间的引文链接通过 0/1 值的邻接矩阵来描述。

   这些数据集的统计信息如下表所示。

   

2. baseline 方法：

   我们和几种 state-of-the-art 方法比较，包括：带验证集的 GCN:GCN+V、不带验证集的 GCN:GCN-V、使用切比雪夫滤波器的 GCN(Cheby)、使用 ParWalks 的标记传播算法 label propagation:LP、 Planetoid 算法、DeepWalk 算法、流形正则化 manifold regularization:ManiReg、半监督嵌入semi-supervised embedding:SemiEmb 、iterative classification algorithm:ICA。

   我们对比了我们提出的 Co-Training、Self-Training、Union、Intersection 等方法。

3. 参数设置：

   • 对于 ParWalks，我们设置 $\mathbf{\Lambda }=\alpha \mathbf{I}$$\mathbf \Lambda = \alpha \mathbf I$ ，且 $\alpha ={10}^{-6}$$\alpha = 10^{-6}$ 。

   • 对于 GCN，我们使用和 《Semisupervised classification with graph convolutional networks》 相同的超参数，这些超参数是模型在 Cora 数据集上验证好的：学习率 0.01、最多 200 轮 epoch、$L_2$$L_2$ 正则化系数为 $5\times {10}^{-4}$$5\times 10^{-4}$ 、2层卷积层、隐层维度16 。

   • 对于 GCN(Cheby)，我们选择多项式的阶数为 $K=2$$K=2$ 。

   • 每次执行时，我们随机拆分标记数据，随机选择其中一小部分标记数据作为训练集，然后随机选择 1000 个标记数据作为测试集。

     • 对于 GCN +V ，我们还选择额外的 500个标记数据作为验证集。

     • 对于 GCN -V，我们仅简单地优化 GCN 的训练 accuracy 。

     • 对于所有方法，我们分别评估不同规模的训练标记数据的效果：

       • 在 Cora,CiteSeer 数据集上，训练标记数据规模分别为 0.5%, 1%, 2%, 3%, 4%, 5% 。
       • 在 PubMed 数据集上，训练标记数据规模为 0.03%, 0.05%, 0.1%, 0.3% 。

       我们选择这些比例是为了方便和 《Semisupervised classification with graph convolutional networks》 的实验结果进行比较。

     对于 Cora,CiteSeer 数据集，每种方法执行 50 轮并报告平均的 accuracy；对于 PubMed 数据集，每种方法执行 10 轮并报告平均的 accuracy 。

4. 不同方法在各数据集上的效果如下表所示，其中每列测试准确率最高的方法以粗体突出显示，top 3 方法以下划线显示。

   结论：

   • 在每个数据集上，我们的方法大多数情况下都要比其它方法好得多。

   • 如果数据具有很强的流形结构（如 PubMed），则 Co-Training 效果更好；否则 Self-Training 效果更好。Self-Training 在 PubMed 上表现较差，因为它未能充分利用图结构。

   • 当训练标记数据规模较大时，Intersection 效果更好，因为它会过滤很多扩展的、但是无效的标记数据；大多数情况下，Union 表现最佳，因为它为训练集添加了更多种多样的标签数据。

   • 当训练标记数据规模较小时，我们所有的方法都远远超越 GCN-V、并在大多数情况下超越了 GCN +V 。

     这验证了我们的分析，即 GCN 模型无法在标记数据较少时有效地将标签信息传播到整个图。

   • 随着训练标记数据规模的增加，大多数情况下我们的方法仍然优于 GCN +V ，这表明我们方法的有效性。

   • 当训练标记数据规模足够大时，我们方法和 GCN 表现差不多，这表明当标记数据充足时已经可以训练一个良好的 GCN 分类器。

   • Cheby 在大多数情况下表现不佳，这可能是由于过拟合造成的。

   

   

   

5. 我们将我们的方法和其它 state-of-the-art 方法比较，比较结果如下表所示。实验配置和前面的相同，除了对于每个数据集我们对每个类别采样 20 个训练标记数据，这对应于 CiteSeer 训练集大小 3.6%、Cora 的 5.1%、PubMed 的 0.3% 。

   其它 baseline 直接拷贝自 《Semisupervised classification with graph convolutional networks》。

   结论：我们方法的效果和 GCN 类似，并明显优于其它 baseline 方法。

   

6. 我们方法一个常用的超参数是新添加标记数据的数量：添加太多标记数据会引入噪声，添加太少标记数据则无法训练出良好的 GCN 分类器。

   如前文所述，我们估计训练 GCN 所需要的总的标记数据量 $\eta$$\eta$ 的下界为：

   $${\left(\hat{d}\right)}^{\tau }\times \eta \simeq n$$

   我们在实验中选择 $3\eta$$3\eta$ 。实际上我们发现选择 $2\eta ,3\eta ,4\eta$$2\eta, 3\eta,4\eta$ 的效果差不多。

7. 我们遵循 《Semisupervised classification with graph convolutional networks》 将卷积层数量设为 2 。我们观察到 2 层 GCN 表现最好。当卷积层数量增加时，分类准确率急剧下降，这可能是因为过度平滑。

8. 计算代价：

   • 对于 Co-Training，额外的计算开销是随机游走模型，这需要求解 $\mathbf{R}=(\mathbf{\Lambda }+\mathbf{L}{)}^{-1}\mathbf{\Lambda }$$\mathbf R = (\mathbf \Lambda + \mathbf L)^{-1} \mathbf \Lambda$ 。在我们的实验中，由于 Cora/CiteSeer 只有数千个节点，因此计算时间几乎可以忽略不记；而 PubMed 在 Matlab R2015b 上花的时间也不到 0.38 秒。

     我们可以使用基于节点的 graph engine 进一步加速计算速度，因此我们方法的可扩展性不是问题。

   • 对于 Self-Training，我们只需要训练 GCN 几个额外的 epoch，它建立在预先训练好的 GCN 之上，因此收敛速度很快。因此 Self-Training 训练时间和 GCN 相当。

二、GNNEXPLAINER[2019]

1. 图是强大的数据表示形式，而图神经网络Graph Neural Network: GNN 是处理图的最新技术。 GNN 能够递归地聚合图中邻域节点的信息，从而自然地捕获图结构和节点特征。

   尽管GNN 效果很好，但是其可解释性较差。由于以下几个原因，GNN 的可解释性非常重要：

   • 可以提高对 GNN 模型的信任程度。
   • 在越来越多有关公平fairness 、隐私privacy 、以及其它安全挑战safety challenge 的关键决策应用application 中，提高模型的透明度 transparency 。
   • 允许从业人员理解模型特点，从而在实际环境中部署之前就能识别并纠正模型的错误。

   尽管目前尚无用于解释 GNN 的方法。但是在更高层次，我们可以将包括 GNN 和 Non-GNN 的可解释性方法分为两个主要系列：

   • 使用简单的代理模型 surrogate model 局部逼近locally approximate 完整模型full model，然后探索这个代理模型以进行解释。

     这可能是以模型无关model-agnostic 的方式来完成的，通常是通过线性模型 linear model 或者规则集合 set of rules 来学习预测的局部近似，可以充分代表预测结果。

   • 仔细检查模型的相关特征relevant feature，并找到high-level 特征的良好定性解释good qualitative interpretation ，或者识别有影响力的输入样本influential input instance 。

     如通过特征梯度 feature gradients、神经元反向传播中输入特征的贡献、反事实推理counterfactual reasoning 等。

   上述两类方法专注于研究模型的固有解释，而后验post-hoc 的可解性方法将模型视为黑盒，然后对其进行探索从而获得相关信息。

   但是所有这些方法无法融合关系信息，即图的结构信息。由于关系信息对于图上机器学习任务的成功至关重要，因此对 GNN 预测的任何解释都应该利用图提供的丰富关系信息、以及节点特征。论文 《GNNExplainer: Generating Explanations for Graph Neural Networks》 提出了 一种解释 GNN 预测的方法，称作 GNNEXPLAINER 。GNNEXPLAINER 接受训练好的GNN 及其预测，返回对于预测最有影响力的、输入图的一个小的子图small subgraph ，以及节点特征的一个小的子集small subset 。

   如下图所示，这里展示了一个节点分类任务，其中在社交网络上训练了 GNN 模型 $\mathbf{\Phi }$$\mathbf\Phi$ 从而预测体育活动。给定训练好的GNN $\mathbf{\Phi }$$\mathbf\Phi$ 以及对节点 $v_i$$v_i$ 的预测 ${\hat{y}}_i=\text{basketball}$$\hat y_i= \text{basketball}$ ，GNNEXPLAINER 通过识别对预测 ${\hat{y}}_i$$\hat y_i$ 有影响力的输入图的一个小的子图、以及节点特征的一个小的子集来生成解释explanation ，如右图所示。

   • 通过检查 ${\hat{y}}_i$$\hat y_i$ 的解释 explanation，我们发现 $v_i$$v_i$ 社交圈中很多朋友都喜欢玩球类游戏，因此 GNN 预测 $v_i$$v_i$ 可能会喜欢篮球。
   • 同样地，通过检查 ${\hat{y}}_j$$\hat y_j$ 的解释 explanation我们发现 $v_j$$v_j$ 社交圈中很多朋友都喜欢水上运动和沙滩运动，因此 GNN 预测 ${\hat{y}}_j=\text{sailing}$$\hat y_j=\text{sailing}$ （帆船运动）。

   

   GNNEXPLAINER 方法和 GNN 模型无关，可以解释任何 GNN 在图的任何机器学习任务上的预测，包括节点分类、链接预测、图分类任务。它可以解释单个实例的预测 single-instance explanation ，也可以解释一组实例的预测 multi-instance explanation 。

   • 在单个实例预测的情况下，GNNEXPLAINER 解释了 GNN 对于特定样本的预测。
   • 在多个实例预测的情况下，GNNEXPLAINER 提供了对于一组样本（如类别为“篮球”的所有节点）的预测的一致性解释（即这些预测的共同的解释）。

   GNNEXPLAINER 将解释指定为训练 GNN 的整个输入图的某个子图，其中子图基于 GNN 的预测最大化互信息mutual information 。这是通过平均场变分近似 mean field variational approximation ，以及学习一个实值graph mask 来实现的。这个 graph mask 选择了 GNN 输入图的最重要子图。同时，GNNEXPLAINER 还学习了一个 feature mask，它可以掩盖不重要的节点特征。

   论文在人工合成图、以及真实的图上评估GNNEXPLAINER 的效果。实验表明：GNNEXPLAINER 为 GNN 的预测提供了一致而简洁的解释。

2. 虽然解释GNN 问题没有得到很好的研究，但相关的可解释性 interpretability 和神经调试neural debugging 的问题在机器学习中得到了大量的关注。在high-level 上，我们可以将那些 non-graph neural network 的可解释性方法分为两个主要方向：

   • 第一个方向的方法制定了完整神经网络full neural network 的简单代理模型。这可以通过模型无关model-agnostic 的方式完成，通常是通过学习 prediction 周围的局部良好近似（例如通过线性模型或规则集合），代表预测的充分条件sufficient condition 。
   • 第二个方向方法确定了计算的重要方面，例如，特征梯度feature gradient、神经元的反向传播对输入特征的贡献、以及反事实推理。然而，这些方法产生的显著性映射 saliency map 已被证明在某些情况下具有误导性，并且容易出现梯度饱和等问题。这些问题在离散输入（如图邻接矩阵）上更加严重，因为梯度值可能非常大而且位于一个非常小的区域interval 。正因为如此，这种方法不适合用来解释神经网络在图上的预测。

   事后可解释性post-hoc interpretability 方法不是创建新的、固有可解释的模型，而是将模型视为黑箱，然后探测模型的相关信息。然而，还没有利用关系型结构（如graph）方面的工作。解释图结构数据预测的方法的缺乏是有问题的，因为在很多情况下，图上的预测是由节点和它们之间的边的路径的复杂组合引起的。例如，在一些任务中，只有当图中存在另一条替代路径形成一个循环时，一条边才是重要的，而这两个特征，只有在一起考虑时，才能准确预测节点标签。因此，它们的联合贡献不能被建模为单个贡献的简单线性组合。

   最后，最近的GNN 模型通过注意力机制增强了可解释性。然而，尽管学到的edge attention 值可以表明重要的图结构，但这些值对所有节点的预测都是一样的。因此，这与许多应用相矛盾，在这些应用中，一条边对于预测一个节点的标签是至关重要的，但对于另一个节点的标签则不是。此外，这些方法要么仅限于特定的GNN架构，要么不能通过共同考虑图结构和节点特征信息来解释预测结果。

3. GNNEXPLAINER 提供了各种好处 ，包括可视化语义相关结构以进行解释的能力、以及提供洞察GNN 的错误的能力。

2.1 方法

1. 定义图 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$$\mathcal G=(\mathcal V, \mathcal E, \mathbf X)$ ，其中：

   • $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ 为节点集合，节点数量为 $n$$n$ 。
   • $\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 为边集合，$e_{i,j}=(v_i,v_j)$$e_{ i,j } = (v_i,v_j)$ ，边数量为 $m$$m$ 。
   • 每个节点 $v_i$$v_i$ 关联一个特征向量 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec x}_i\in \mathbb R^{d}$ ，所有节点的特征向量拼接为特征矩阵 $\mathbf{X}\in {\mathbb{R}}^{n\times d}$$\mathbf X\in \mathbb R^{n\times d}$ ， $d$$d$ 为特征向量维度。

   不失一般性，我们考虑节点分类问题的可解释性。定义 $f$$f$ 为一个节点到类别标签的映射函数：$f:\mathcal{V}\to \{1,\cdots ,C\}$$f:\mathcal V\rightarrow \{1,\cdots,C\}$ ，其中 $C$$C$ 为类别数量。GNN 模型 $\mathbf{\Phi }$$\mathbf\Phi$ 在训练集的所有节点上优化从而逼近 $f$$f$ ，然后用于预测未标记节点的label 。

2. 我们假设GNN 模型 $\mathbf{\Phi }$$\mathbf\Phi$ 采用消息传递机制。在第 $l$$l$ 层，GNN 模型 $\mathbf{\Phi }$$\mathbf \Phi$ 的更新涉及三个关键计算：

   • 首先，模型计算每对节点pair 对之间传递的消息。节点pair 对 $(v_i,v_j)$$(v_i,v_j)$ 之间的消息定义为：

     $${\overrightarrow{\mathbf{m}}}_{i,j}^{(l)}=\text{MSG}({\overrightarrow{\mathbf{h}}}_i^{(l-1)},{\overrightarrow{\mathbf{h}}}_j^{(l-1)},r_{i,j})$$

     其中：MSG(.) 为消息函数；${\overrightarrow{\mathbf{h}}}_i^{(l-1)}$$\mathbf{\vec h}_i^{(l-1)}$ 为节点 $v_i$$v_i$ 在第 $l-1$$l-1$ 层的 representation；$r_{i,j}$$r_{i,j}$ 为节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间的关系。

   • 然后，对于每个节点 $v_i$$v_i$，GNN 聚合来自其邻域的所有消息：

     $${\overrightarrow{\mathbf{a}}}_i^{(l)}=\text{AGG}\left(\{{\overrightarrow{\mathbf{m}}}_{i,j}^{(l)}\mid v_j\in {\mathcal{N}}_i\}\right)$$

     其中：AGG(.) 为一个邻域聚合函数；${\mathcal{N}}_i$$\mathcal N_i$ 为节点 $v_i$$v_i$ 的邻域集合。

   • 最后，对于每个节点 $v_i$$v_i$ ，GNN 根据 ${\overrightarrow{\mathbf{a}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_i^{(l-1)}$$\mathbf{\vec a}_i^{(l)} , \mathbf{\vec h}_i^{(l-1)}$ 来计算 $v_i$$v_i$ 在第 $l$$l$ 层的 representation：

     $${\overrightarrow{\mathbf{h}}}_i^{(l)}=\text{UPDATE}({\overrightarrow{\mathbf{a}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_i^{(l-1)})$$

     其中 UPDATE(.) 为节点状态更新函数。

   最终节点 $v_i$$v_i$ 的embedding 为 $v_i$$v_i$ 在第 $L$$L$ 层输出的 representation：

   $${\overrightarrow{\mathbf{z}}}_i={\overrightarrow{\mathbf{h}}}_i^{(L)}$$

   对于采用 MSG,AGG,UPDATE 计算组成的任何 GNN ，我们的 GNNEXPLAINER 可以提供解释。

3. 我们的洞察insight 是观察到：节点 $v$$v$ 的计算图computation graph 是由 GNN 的neighborhood-based 聚合来定义，如下图所示。这个计算图完全决定了用于生成节点 $v$$v$ 的预测 $\hat{y}$$\hat y$ 的所有信息。具体而言，节点 $v$$v$ 的计算图告诉 GNN 如何生成节点 $v$$v$ 的 embedding $\overrightarrow{\mathbf{z}}$$\mathbf{\vec z}$ 。

   定义节点 $v$$v$ 的计算图 computation graph 为 ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ ，它关联一个二元binary 邻接矩阵 ${\mathbf{A}}_c(v)\in {\mathbb{R}}^{n\times n}$$\mathbf A_c(v)\in \mathbb R^{n\times n}$ ，其中 $A_c(v)[i,j]\in \{0,1\}$$A_c(v)[i,j]\in \{0,1\}$ 取值为0 或1 ； 也关联一个特征矩阵 ${\mathbf{X}}_c(v)=\{{\overrightarrow{\mathbf{x}}}_j\mid v_j\in {\mathcal{G}}_c(v)\}$$\mathbf X_c(v) = \{\mathbf{\vec x}_j\mid v_j\in \mathcal G_c(v)\}$ 。

   GNN 模型 $\mathbf{\Phi }$$\mathbf\Phi$ 学习一个条件分布 $P_{\mathbf{\Phi }}(Y_v\mid {\mathcal{G}}_c(v),{\mathbf{X}}_c(v))$$P_{\mathbf \Phi}\left( Y_v\mid \mathcal G_c(v),\mathbf X_c(v)\right)$ ，表示给定节点计算图 ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$、节点特征矩阵 ${\mathbf{X}}_c(v)$$\mathbf X_c(v)$ 的条件下，节点 $v$$v$ 属于各类别的概率。其中 $Y_v\in \{1,\cdots ,C\}$$Y_v\in \{1,\cdots,C\}$ 为一个随机变量。

   一旦GNN 模型学到这样的分布之后，对于节点 $v$$v$ ，GNN 的类别预测结果为 $\hat{y}=\mathbf{\Phi }({\mathcal{G}}_c(v),{\mathbf{X}}_c(v))$$\hat y = \mathbf\Phi(\mathcal G_c(v),\mathbf X_c(v))$ ，意味着它完全由三个因素决定：模型 $\mathbf{\Phi }$$\mathbf\Phi$、图结构信息 ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ 、节点特征信息 ${\mathbf{X}}_c(v)$$\mathbf X_c(v)$ 。这个观察结果意味着我们只需要考虑图结构 ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ 和节点特征 ${\mathbf{X}}_c(v)$$\mathbf X_c(v)$ 来解释 $\hat{y}$$\hat y$ ，如下图 A 所示。

   正式地讲，GNNEXPLAINER 为预测 $\hat{y}$$\hat y$ 生成解释explanation，记作 $({\mathcal{G}}_S,{\mathbf{X}}_S^F)$$\left(\mathcal G_S,\mathbf X_S^F\right)$ 。其中：

   • ${\mathcal{G}}_S$$\mathcal G_S$ 为计算图的一个小的子图small subgraph ，如图 A 所示。

   • ${\mathbf{X}}_S$$\mathbf X_S$ 为 ${\mathcal{G}}_S$$\mathcal G_S$ 关联的特征，${\mathbf{X}}_S^F$$\mathbf X_S^F$ 为节点特征的一个小的特征子集 small subset 。F 表示通过 mask F 来遮盖，即：${\mathbf{X}}_S^F=\{{\overrightarrow{\mathbf{x}}}_j^F\mid v_j\in {\mathcal{G}}_S\}$$\mathbf X_S^F = \{\mathbf{\vec x}_j^F\mid v_j\in \mathcal G_S\}$ ，如图B 所示。

     假设原始的节点特征集合为 $\mathbb{A}=\{{\mathcal{A}}_1,\cdots ,{\mathcal{A}}_d\}$$\mathbb A=\{\mathcal A_1,\cdots,\mathcal A_d\}$ ，则经过 mask F 遮盖之后的特征集合为：

     $${\mathbb{A}}^F=\{{\mathcal{A}}_{t1},\cdots ,{\mathcal{A}}_{t_F}\},1\le t_1\le \cdots \le t_F\le d$$

     它是原始特征集合的一个小的特征子集，且有：${\overrightarrow{\mathbf{x}}}_j^F=(x_{j,t_1},x_{j,t_2},\cdots ,x_{j,t_F}{)}^{\mathrm{\top }}\in {\mathbb{R}}^F$$\mathbf{\vec x}_j^F=(x_{j,t_1},x_{j,t_2},\cdots,x_{j,t_F})^\top\in \mathbb R^F$ 为遮盖后的特征向量。

   下图中：

   • 图 A 给出了一个 GNN 在节点 $v$$v$ 处的计算图 ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ ，它用于得到节点 $v$$v$ 的类别预测 $\hat{y}$$\hat y$ 。

     ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ 中的某些边构成重要的消息传播路径（绿色），这些路径允许有用的节点消息跨 ${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ 传播并在节点 $v$$v$ 处聚合从而进行预测；相反，${\mathcal{G}}_c(v)$$\mathcal G_c(v)$ 中的另一些边不重要（橙色）。但是无论消息重不重要，在节点 $v$$v$ 处GNN 都会具有所有消息（包括不重要的消息）从而进行预测，这可能会稀释重要的消息。

     GNNEXPLAINER 的目标是识别少量对于预测至关重要的重要特征和路径（绿色）。

   • 图 B 表示 GNNEXPLAINER 通过学习节点特征mask 来确定 ${\mathcal{G}}_S$$\mathcal G_S$ 中节点的那些特征维度对于预测至关重要。

   

4. 接下来我们详细描述 GNNEXPLAINER。给定训练好的 GNN 模型 $\mathbf{\Phi }$$\mathbf\Phi$ 以及一个预测 prediction （即单实例解释single-instance explanation）、或者一组预测（即多实例解释multi-instance explanation ）， GNNEXPLAINER 将通过识别对模型 $\mathbf{\Phi }$$\mathbf\Phi$ 的预测影响最大的计算图的子图、节点特征的子集从而生成解释。

   在多实例解释中，GNNEXPLAINER 将每个实例的解释聚合在一起并自动抽取为一个原型proto。这个原型代表每个实例解释的公共部分，即proto 可以对所有这些实例进行解释。

2.1.1 单实例解释

1. 给定一个节点 $v$$v$ ，我们的目标是识别对于该节点的 GNN 预测 $\hat{y}$$\hat y$ 很重要的子图 ${\mathcal{G}}_S\subseteq {\mathcal{G}}_c$$\mathcal G_S\sube \mathcal G_c$ ，以及关联特征矩阵 ${\mathbf{X}}_S=\{{\overrightarrow{\mathbf{x}}}_j\mid v_j\in {\mathcal{G}}_S\}$$\mathbf X_S=\{ \mathbf{\vec x}_j \mid v_j\in \mathcal G_S\}$ 。现在我们不考虑特征 mask，这留待下一步讨论。

   我们使用互信息mutual information:MI 来刻画子图的重要性，并将 GNNEXPLAINER 形式化为以下最优化问题：

   $$\underset{{\mathcal{G}}_S}{max}\text{MI}(Y,({\mathcal{G}}_S,{\mathbf{X}}_S))=H(Y)-H(Y\mid \mathcal{G}={\mathcal{G}}_S,\mathbf{X}={\mathbf{X}}_S)$$

   其中：

   • $H(\cdot )$$H(\cdot)$ 为熵，它表示GNN 对于节点 $v$$v$ 类别预测结果的不确定性程度。 $Y\in \{1,\cdots ,C\}$$Y\in \{1,\cdots,C\}$ 为代表 GNN 预测节点 $v$$v$ 类别的随机变量。

     注意：这里没有任何关于节点 $v$$v$ 真实类别的信息。也就是我们不关心 GNN 预测得准不准，而是仅关心哪些因素和 GNN 预测结果相关。

     $H(Y)$$H(Y)$ 其实是 $H(Y\mid \mathcal{G}=\mathcal{G},\mathbf{X}=\mathbf{X})$$H(Y\mid \mathcal G=\mathcal G, \mathbf X=\mathbf X)$ ，即以原始图、原始特征矩阵来进行的预测所得到的熵。

   • $H(\cdot \mid \cdot )$$H(\cdot\mid \cdot)$ 为条件熵，它表当节点 $v$$v$ 的计算图被限制为子图 ${\mathcal{G}}_S$$\mathcal G_S$ 、节点特征被限制为 ${\mathbf{X}}_S$$\mathbf X_S$ 后，GNN 预测结果不确定性程度。

   MI 刻画了当节点 $v$$v$ 的计算图被限制为子图 ${\mathcal{G}}_S$$\mathcal G_S$ 、节点特征被限制为 ${\mathbf{X}}_S$$\mathbf X_S$ 后，预测结果为 $\hat{y}=\mathbf{\Phi }({\mathcal{G}}_c,{\mathbf{X}}_c)$$\hat y=\mathbf\Phi(\mathcal G_c, \mathbf X_c)$ 的概率的变化。例如：

   • 考虑 $v_j\in {\mathcal{G}}_c(v_i),v_j\ne v_i$$v_j\in \mathcal G_c(v_i),v_j\ne v_i$ 。如果从 ${\mathcal{G}}_c(v_i)$$\mathcal G_c(v_i)$ 中移除 $v_j$$v_j$ ，使得预测结果为 ${\hat{y}}_i$$\hat y_i$ 的概率急剧降低，则节点 $v_j$$v_j$ 是 $v_i$$v_i$ 预测的一个很好的解释。
   • 类似地，考虑 $v_j,v_k\in {\mathcal{G}}_v(v_i),v_j,v_k\ne v_i$$v_j,v_k \in \mathcal G_v(v_i),v_j,v_k\ne v_i$ 。如果移除 $v_j,v_k$$v_j,v_k$ 之间的边，使得预测结果为 ${\hat{y}}_i$$\hat y_i$ 的概率急剧降低，则 $(v_j,v_k)$$(v_j,v_k)$ 之间的边是 $v_i$$v_i$ 预测的一个很好的解释。

2. $\text{MI}(Y,({\mathcal{G}}_S,{\mathbf{X}}_S))$$\text{MI}( Y,(\mathcal G_S,\mathbf X_S))$ 的第一项 $H(Y)$$H(Y)$ 为常数项，因为对于给定的、训练好的 GNN，节点 $v$$v$ 的预测结果是 $\hat{y}$$\hat y$ 的概率是已知的，和 ${\mathcal{G}}_S$$\mathcal G_S$ 无关。则有：

   $$\begin{array}{c}\underset{{\mathcal{G}}_S}{max}\text{MI}(Y,({\mathcal{G}}_S,{\mathbf{X}}_S))=\underset{{\mathcal{G}}_S}{min}H(Y\mid \mathcal{G}={\mathcal{G}}_S,\mathbf{X}={\mathbf{X}}_S)\\ =\underset{{\mathcal{G}}_S}{max}{\mathbb{E}}_{Y\mid {\mathcal{G}}_S,{\mathbf{X}}_S}[\log P_{\mathbf{\Phi }}(Y\mid \mathcal{G}={\mathcal{G}}_S,\mathbf{X}={\mathbf{X}}_S)]\end{array}$$

   因此，对于预测 $\hat{y}$$\hat y$ 的解释是一个子图 ${\mathcal{G}}_S$$\mathcal G_S$ ，当 GNN 被限制在 ${\mathcal{G}}_S$$\mathcal G_S$ 时最小化 $\mathbf{\Phi }$$\mathbf\Phi$ 不确定性 uncertainty 。在效果上，${\mathcal{G}}_S$$\mathcal G_S$ 最大化预测为 $\hat{y}$$\hat y$ 的概率。

   理论上当 ${\mathcal{G}}_S={\mathcal{G}}_c$$\mathcal G_S = \mathcal G_c$ 时，上式最大化。为了获得更紧凑的解释，我们对 ${\mathcal{G}}_S$$\mathcal G_S$ 的大小施加约束，如 $|{\mathcal{G}}_S|\le K_M$$|\mathcal G_S|\le K_M$ ，使得 ${\mathcal{G}}_S$$\mathcal G_S$ 最多只有 $K_M$$K_M$ 个节点。实际上这意味着 GNNEXPLAINER 旨在通过采取对预测提供最高互信息的 $K_M$$K_M$ 个节点进行降噪。

3. 直接优化 GNNEXPLAINER 的目标函数很困难，因为 ${\mathcal{G}}_c$$\mathcal G_c$ 有指数级的子图 ${\mathcal{G}}_S$$\mathcal G_S$ 作为 $\hat{y}$$\hat y$ 的候选解释。因此，我们考虑子图 ${\mathcal{G}}_S$$\mathcal G_S$ 的分数邻接矩阵fractional adjacency matrix，即 ${\mathbf{A}}_S\in {\mathbb{R}}^{n\times n}$$\mathbf A_S\in \mathbb R^{n\times n}$， 其中 $A_S[i,j]\in [0.0,1.0]$$A_S[i,j] \in [0.0,1.0]$ 在 0~1.0 之间。此外我们施加约束 $A_S[j,k]\le A_c[j,k]$$A_S[j,k]\le A_c[j,k]$，使得没有边的节点之间 $A_S[j,k]$$A_S[j,k]$ 也为零。

   这种连续性松弛continuous relaxation 可以解释为 ${\mathcal{G}}_c$$\mathcal G_c$ 子图分布的变分近似variational approximation 。具体而言，我们将 ${\mathcal{G}}_S\in \mathcal{G}$$\mathcal G_S\in \mathcal G$ 视为一个随机图变量random graph variable，则目标函数变为：

   $$\underset{\mathcal{G}}{min}{\mathbb{E}}_{{\mathcal{G}}_S\in \mathcal{G}}H(Y\mid \mathcal{G}={\mathcal{G}}_S,\mathbf{X}={\mathbf{X}}_S)$$

   我们假设目标函数是凸函数，则 Jensen 不等式给出以下的上界：

   $$\underset{\mathcal{G}}{min}H(Y\mid \mathcal{G}={\mathbb{E}}_{\mathcal{G}}[{\mathcal{G}}_S],\mathbf{X}={\mathbf{X}}_S)$$

   实际上由于神经网络的复杂性，凸性假设不成立。但是通过实验我们发现：优化带正则化的上述目标函数通常求得一个局部极小值，该局部极小值具有高质量的解释性。

4. 为精确地估计 ${\mathbb{E}}_{\mathcal{G}}$$\mathbb E_\mathcal G$ ，我们使用平均场变分近似mean-field variational approximation ，并将 $\mathcal{G}$$\mathcal G$ 分解为多元伯努利分布multivariate Bernoulli distribution ：

   $$P_{\mathcal{G}}({\mathcal{G}}_S)=\prod _{(j,k)\in {\mathcal{G}}_c}{A}_S[j,k]$$

   这允许我们估计对于平均场近似的期望从而获得 ${\mathbf{A}}_S$$\mathbf A_S$ ，其中 ${\mathbf{A}}_S$$\mathbf A_S$ 的第 $(j,k)$$(j,k)$ 元素代表：节点 $(v_j,v_k)$$(v_j,v_k)$ 之间存在边的期望。

   • 我们从实验观察到：尽管 GNN 是非凸的，但是这种近似approximation 结合一个可以提升离散型discreteness 的正则化器一起，结果可以收敛到良好的局部极小值。

   • 可以通过使用邻接矩阵的计算图的掩码 ${\mathbf{A}}_c\odot \sigma (\mathbf{M})$$\mathbf A_c\odot \sigma(\mathbf M)$ 替换要优化的 ${\mathbb{E}}_{\mathcal{G}}[{\mathcal{G}}_S]$$\mathbb E_\mathcal G[\mathcal G_S]$ ，从而优化上式中的条件熵。即：

     $$\begin{array}{c}\underset{\mathcal{G}}{min}H(Y\mid \mathcal{G}={\mathbf{A}}_c\odot \sigma (\mathbf{M}),\mathbf{X}={\mathbf{X}}_S)\\ =\underset{\mathbf{M}}{min}-\sum _{c=1}^C{P}_{\mathbf{\Phi }}(Y=c\mid \mathcal{G}={\mathbf{A}}_c\odot \sigma (\mathbf{M}),\mathbf{X}={\mathbf{X}}_S)\log P_{\mathbf{\Phi }}(Y=c\mid \mathcal{G}={\mathbf{A}}_c\odot \sigma (\mathbf{M}),\mathbf{X}={\mathbf{X}}_S)\end{array}$$

     其中：

     • $\mathbf{M}\in {\mathbb{R}}^{n\times n}$$\mathbf M\in \mathbb R^{n\times n}$ 表示我们需要学习的mask 矩阵。
     • $\odot$$\odot$ 表示逐元素乘积。
     • $\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数，它将 mask 映射到 0.0~1.0 之间。

   GNNExplainer 的核心在于：用 0.0 ~ 1.0 之间的 mask 矩阵（待学习）来调整邻接矩阵，从而最小化预测的熵。但是，这种方法只关心哪个子图对预测结果最重要，并不关心哪个子图对 ground-truth 最有帮助。

   可以通过标签类别和模型预测之间的交叉熵来修改上式中的条件熵，从而得到哪个子图对 ground-truth 最有帮助。

   $\mathbf{M}$$\mathbf M$ 通过随机梯度下降来学习。

5. 在某些应用application中，我们不关心模型预测结果的 $\hat{y}$$\hat y$ 的解释性，而更关注如何使得模型能够预测所需要类别的标签。这里我们可以使用标签类别和模型预测之间的交叉熵来修改上式中的条件熵，即：

   $$\underset{\mathbf{M}}{min}-\sum _{c=1}^C\mathbb{I}[y=c]\log P_{\mathbf{\Phi }}(Y=c\mid \mathcal{G}={\mathbf{A}}_c\odot \sigma (\mathbf{M}),\mathbf{X}={\mathbf{X}}_c)$$

6. 尽管有不同的动机和目标，在 Neural Relational Inference 中也发现了masking 方法。

7. 最后，我们计算 $\sigma (\mathbf{M})$$\sigma(\mathbf M)$ 和 ${\mathbf{A}}_c$$\mathbf A_c$ 的逐元素乘积，并通过阈值移除 $\mathbf{M}$$\mathbf M$ 中的较小的值，从而得出节点 $v$$v$ 处模型预测 $\hat{y}$$\hat y$ 的解释 ${\mathcal{G}}_S$$\mathcal G_S$ 。

2.1.2 图结构 & 节点特征

1. 为确定哪些节点特征对于预测 $\hat{y}$$\hat y$ 最重要，GNNEXPLAINER 针对 ${\mathcal{G}}_S$$\mathcal G_S$ 中的节点学习一个特征选择器 $F$$F$ 。GNNEXPLAINER 考虑 ${\mathcal{G}}_S$$\mathcal G_S$ 中节点的特征子集 ${\mathbb{A}}^F=\{{\mathcal{A}}_{t1},\cdots ,{\mathcal{A}}_{t_F}\},1\le t_1\le \cdots \le t_F\le d$$\mathbb A^F = \{\mathcal A_{t1},\cdots,\mathcal A_{t_F}\},\quad 1\le t_1\le\cdots\le t_F\le d$ ，其中每个节点特征选择后的特征向量为 ${\overrightarrow{\mathbf{x}}}_j^F=(x_{j,t_1},x_{j,t_2},\cdots ,x_{j,t_F}{)}^{\mathrm{\top }}$$\mathbf{\vec x}_j^F=(x_{j,t_1},x_{j,t_2},\cdots,x_{j,t_F})^\top$。所有 ${\mathcal{G}}_S$$\mathcal G_S$ 中节点的选择后的特征矩阵为 ${\mathbf{X}}_S^F$$\mathbf X_S^F$ 。

   我们通过一个 mask 来定义特征选择器：

   $$\overrightarrow{\mathbf{f}}=(f_1,f_2,\cdots ,f_d{)}^{\mathrm{\top }}$$

   其中 $f_i\in \{0,1\}$$f_i\in\{0,1\}$ 取值为0 或 1 ，当它为1 时表示保留对应特征，否则遮盖对应特征。因此 ${\overrightarrow{\mathbf{x}}}_j^F$$\mathbf{\vec x}_j^F$ 包含未被 $F$$F$ 掩盖mask out 的节点特征。

   我们定义特征 mask 矩阵为：

   $$\begin{array}{c}\mathbf{F}=\left[\begin{array}{cccc}{f}_1& f_2& \cdots & f_d\\ f_1& f_2& \cdots & f_d\\ ⋮& ⋮& \ddots & ⋮\\ f_1& f_2& \cdots & f_d\end{array}\right]\in {\mathbb{R}}^{|{\mathcal{G}}_S|\times d}\end{array}$$

   则有：${\mathbf{X}}_S^F={\mathbf{X}}_S\odot \mathbf{F}$$\mathbf X_S^F = \mathbf X_S\odot \mathbf F$ 。其中 $\odot$$\odot$ 表示逐元素乘积。

2. 现在我们在互信息目标函数中考虑节点特征，从而得到解释explanation $({\mathcal{G}}_S,{\mathbf{X}}_S^F)$$(\mathcal G_S, \mathbf X_S^F)$ ：

   $$\underset{{\mathcal{G}}_S,F}{max}\text{MI}(Y,({\mathcal{G}}_S,F))=H(Y)-H(Y\mid \mathcal{G}={\mathcal{G}}_S,\mathbf{X}={\mathbf{X}}_S^F)$$

   该目标函数同时考虑了对预测 $\hat{y}$$\hat y$ 的子图结构解释、节点特征解释。

3. 从直觉上看：

   • 如果某个节点特征不重要，则 GNN 权重矩阵中的相应权重应该接近于零。mask 这类特征对于预测结果没有影响。
   • 如果某个节点特征很重要，则 GNN 权重矩阵中相应权重应该较大。mask 这类特征会降低预测为 $\hat{y}$$\hat y$ 的概率。

   但是在某些情况下，这种方法会忽略对于预测很重要、但是特征取值接近于零的特征。为解决该问题，我们对所有特征子集边际化marginalize，并在训练过程中使用蒙特卡洛估计从 ${\mathbf{X}}_S$$\mathbf X_S$ 中节点的经验边际分布中采样得到边际分布。

   此外，我们使用 reparametrization 技巧将目标函的梯度反向传播到 mask 矩阵 $\mathbf{F}$$\mathbf F$ 。

   具体而言，为了通过 $\mathbf{X}$$\mathbf X$ 反向传播，我们 reparametrize $\mathbf{X}$$\mathbf X$ 为：

   $$\mathbf{X}=\mathbf{Z}+({\mathbf{X}}_S-\mathbf{Z})\odot \mathbf{F},\text{ s.t. }\sum _j{f}_j\le K_F$$

   其中：

   • $\mathbf{Z}$$\mathbf Z$ 维从经验分布中采样到的随机变量。
   • $K_F$$K_F$ 为要保留的最大特征数量。

   上式等价于：$\mathbf{X}=(1-\mathbf{F})\odot \mathbf{Z}+\mathbf{F}\odot {\mathbf{X}}_S$$\mathbf X = (1-\mathbf F)\odot \mathbf Z + \mathbf F\odot\mathbf X_S$ 。因此 $\mathbf{X}$$\mathbf X$ 由两部分加权和得到：

   • $\mathbf{Z}$$\mathbf Z$ ：来自于每个维度边际分布采样得到的，权重为 $1-\mathbf{F}$$1-\mathbf F$ ，代表噪音部分。这是为了解决特征取值接近于零但是又对于预测很重要的特征的问题。
   • ${\mathbf{X}}_S$$\mathbf X_S$：来自于子图节点的特征向量，权重为 $\mathbf{F}$$\mathbf F$ ，代表真实信号部分。

   这种特征可解释方法可以用于普通的神经网络模型。

4. 为了在解释explanation中加入更多属性，可以使用正则化项扩展 GNNEXPLAINER 的目标函数。可以包含很多正则化项从而产生具有所需属性的解释。

   • 例如，我们使用逐元素的熵来鼓励结构mask 和节点特征mask 是离散的。
   • 例如，我们可以将 mask 参数的所有元素之和作为正则化项，从而惩罚规模太大的mask 。
   • 此外， GNNEXPLAINER 可以通过诸如拉格朗日乘子Lagrange multiplier 约束、或者额外的正则化项等技术来编码domain-specific 约束。

5. 最后需要重点注意的是：每个解释explanation 必须是一个有效的计算图。具体而言， $({\mathcal{G}}_S,{\mathbf{X}}_S)$$(\mathcal G_S, \mathbf X_S)$ 需要允许 GNN 的消息流向节点 $v$$v$ ，从而允许 GNN 做出预测 $\hat{y}$$\hat y$ 。

   重要的是，GNNEXPLAINER 的解释一定是有效的计算图，因为它在整个计算图上优化结构 mask。即使一条断开的边对于消息传递很重要，GNNEXPLAINER 也不会选择它作为解释，因为它不会影响 GNN 的预测结果。实际上，这意味着 ${\mathcal{G}}_S$$\mathcal G_S$ 倾向于是一个小的连通子图small connected subgraph。

   这是因为 GNNExplainer 会运行 GNN，如果计算图无效则运行 GNN 的结果失败或者预测效果很差，因此也就不会作为可解释结果。

2.1.3 多实例解释

1. 有时候我们需要回答诸如 “为什么 GNN 对于一组给定的节点预测都是类别 c ” 之类的问题。因此我们需要获得对于类别 c 的全局解释。

   这里我们提出一个基于 GNNEXPLAINER 的解决方案，从而在类别 c 中的一组不同节点的各自单实例解释中，找到针对类别c 的通用的解释。这个问题与寻找每个解释图中最大公共子图密切相关，这是一个 NP-hard 问题。这里我们采用了解决该问题的神经网络方案，案称作基于对齐alignment-based 的 multi-instance GNNEXPLAINER 。

2. 对于给定的类 c，我们首先选择一个参考节点 reference node $v_c$$v_c$。直观地看，该节点是能够代表该类别的原型节点 prototypical node。

   • 可以通过计算类别 c 中所有节点的 embedding 均值，然后选择类别 c 中节点 embedding 和这个均值最近的节点作为参考节点。
   • 也可以使用有关先验知识，选择和先验知识最匹配的节点作为类别 c 的参考节点。

   给定类别 c 的参考节点 $v_c$$v_c$ ，以及它关联的reference 解释图 ${\mathcal{G}}_S(v_c)$$\mathcal G_S(v_c)$ ，我们将类别 $c$$c$ 中所有节点的解释图都对齐到 ${\mathcal{G}}_S(v_c)$$\mathcal G_S(v_c)$ 。

   利用微分池化differentiable pooling 的思想，我们使用一个松弛relaxed 的对齐矩阵alignment matrix来找到解释图 ${\mathcal{G}}_S(v)$$\mathcal G_S(v)$ 中的节点和 reference解释图 ${\mathcal{G}}_S(v_c)$$\mathcal G_S(v_c)$ 中的节点之间的对应关系。设节点 $v$$v$ 待对齐的解释图的邻接矩阵和特征矩阵分别为 ${\mathbf{A}}_v,{\mathbf{X}}_v$$\mathbf A_v, \mathbf X_v$ ，设参考节点的解释图的邻接矩阵和特征矩阵分别为 ${\mathbf{A}}^{\ast },{\mathbf{X}}^{\ast }$$\mathbf A^*,\mathbf X^*$ 。我们定义松弛对齐矩阵 relaxed alignment matrix $\mathbf{P}\in {\mathbb{R}}^{n_v\times n^{\ast }}$$\mathbf P\in \mathbb R^{n_v\times n^*}$，则优化目标为：

   $$\underset{\mathbf{P}}{min}|{\mathbf{P}}^{\mathrm{\top }}{\mathbf{A}}_v\mathbf{P}-{\mathbf{A}}^{\ast }|+|{\mathbf{P}}^{\mathrm{\top }}{\mathbf{X}}_v-{\mathbf{X}}^{\ast }|$$

   其中：

   • $n_v$$n_v$ 为 ${\mathcal{G}}_S(v)$$\mathcal G_S(v)$ 中节点数量，$n^{\ast }$$n^*$ 为 ${\mathcal{G}}_S(v_c)$$\mathcal G_S(v_c)$ 中节点数量。
   • $\mathbf{P}$$\mathbf P$ 的元素大于零且每一行的和为 1.0 。

   上式第一项表示：经过对齐之后， ${\mathcal{G}}_S(v)$$\mathcal G_S(v)$ 对齐后的邻接关系应该尽可能接近 ${\mathbf{A}}^{\ast }$$\mathbf A^*$ ；第二项表示：经过对齐之后， ${\mathcal{G}}_S(v)$$\mathcal G_S(v)$ 对齐后的特征矩阵应该尽可能接近 ${\mathbf{X}}^{\ast }$$\mathbf X^*$ 。

   实际上对于两个大图 ${\mathcal{G}}_S(v)$$\mathcal G_S(v)$ 和 ${\mathcal{G}}_S(v_c)$$\mathcal G_S(v_c)$ ，上述最优化问题很难求解。但是由于单实例解释生成的 ${\mathcal{G}}_S(v)$$\mathcal G_S(v)$ 和 ${\mathcal{G}}_S(v_c)$$\mathcal G_S(v_c)$ 都是简洁的、很小的图，因此可以有效地计算几乎最优的对齐方式。

3. 一旦得到类别 c 中所有节点对齐后的邻接矩阵，我们就可以使用中位数来生成一个原型prototype 。之所以使用中位数，是因为中位数可以有效对抗异常值。即：

   $${\mathbf{A}}_{\text{proto}}=\text{median}({\tilde{\mathbf{A}}}_i)$$

   其中 ${\tilde{\mathbf{A}}}_i$$\tilde{\mathbf A}_i$ 为类别 c 中第 $i$$i$ 个节点的 explanation 的对齐后的邻接矩阵（即 ${\mathbf{P}}^{\mathrm{\top }}{\mathbf{A}}_i\mathbf{P}$$\mathbf P^\top \mathbf A_i\mathbf P$ ）。

   原型 ${\mathbf{A}}_{\text{proto}}$$\mathbf A_{\text{proto}}$ 允许我们深入了解属于某一类的节点之间共享的图结构模式。然后对于特定的节点，用户可以通过将节点 explanation 和类别原型进行比较，从而研究该特定节点。

4. 在多个解释图的邻接矩阵对齐过程中，也可以使用现在的图库 graph library 来寻找这些解释图的最大公共子图，从而替换掉神经网络部分。

5. 在多实例解释中，解释器explainer 不仅必须突出与单个预测的局部相关信息，还需要强调不同实例之间更高level 的相关性。

   这些实例之间可以通过任意方式产生关联，但是最常见的还是类成员class-membership关联。假设类的不同样本之间存在共同特征，那么解释器需要捕获这种共同的特征。例如，通常发现诱变化合物 mutagenic compounds 具有某些特定属性的功能团，如 NO2。

   如下图所示，经验丰富的专家可能已经注意到这些功能团的存在。当 GNNEXPLAINER 生成原型prototype 时，可以进一步加强这方面的证据。下图来自于 MUTAG 数据集的诱变化合物。