前言

在这里插入图片描述
题目： Semi-Supervised Classification with Graph Convolutional Networks
会议： International Conference on Learning Representations, 2017
论文地址：Semi-Supervised Classification with Graph Convolutional Networks

阅读前建议读一下前面几篇关于GNN的入门文章：

在TNNLS | GNN综述：A Comprehensive Survey on Graph Neural Networks一文中对GCN进行了大概的讲解，讲解如下：
在这里插入图片描述
RecGNN使用相同的图循环层(Grec)来更新节点的表示，而ConvGNN使用不同的图卷积层(Gconv)来更新节点表示。

ConvGNN分为两种：基于频域的和基于空间域的。其中基于频域的方法通过从图信号处理的角度引入过滤器（卷积核的集合）来定义图卷积，其中图卷积运算被解释为从图信号中去除噪声。 基于空间域的ConvGNN继承了RecGNN的思想，通过消息传递来定义图卷积运算。

A. Spectral-Based ConvGNN

基于频域的ConvGNN：假设图是无向的。无向图的归一化图拉普拉斯矩阵定义为：
$L=I_n-D^{-(1/2)}AD^{-(1/2)}$
其中 $D$ 是一个对角阵，对角上的元素表示对应节点的度。归一化图拉普拉斯矩阵具有实对称半正定的性质，因此可以被分解为：
$L=U\Lambda U^T$
其中 $U=[u_0, u_1,...,u_n] \in R^{n \times n}$ 是特征值排序的特征向量矩阵， $\Lambda$ 是特征值对角矩阵，线代基础知识了。归一化图拉普拉斯矩阵的特征向量形成正交空间，即 $U^TU=I$ 。

对图进行处理时， $\in R^n$ 表示为所有节点的特征向量， $x_i$ 为第 $i$ 个节点的特征向量。 $x$ 的图傅里叶变换为： $\Im(x)=U^Tx$ ，逆图傅里叶变换为： $\Im^{-1}(\hat{x})=U\hat{x}$ ，其中 $\hat{x}$ 表示傅里叶变换的结果信号。

由以上定义可知，图傅里叶变换将输入图信号投影到标准化空间，其中空间基由标准化图拉普拉斯算子的特征向量形成。原始输入信号可以被表示为： $\sum_{i}\hat{x}_iu_i$ （逆图傅里叶变换）。

有了以上定义后，输入信号与过滤器 $\in R^b$ 间的卷积运算被定义为：
在这里插入图片描述
如果将过滤器表示为： $g_{\theta}=diag(U^Tg)$ ，则图卷积可以简化为：

基于频域的ConvGNN都遵循以上定义，只是过滤器可能有所不同。

比如：Spectral CNN假设过滤器 $g_{\theta}=\Theta_{i, j}^{(k)}$ 是一组可学习的参数，Spectral CNN的图卷积层定义为：
在这里插入图片描述
其中 $k$ 是层索引， $H^{(k-1)} \in R^{n \times f_{k-1}}$ 是输入图信号， $H_0=X$ ， $f_{k-1}$ 为输入通道数， $f_k$ 为输出通道数。

B. Spatial-Based ConvGNN

基于空间域的ConvGNN：基于节点的空间关系来定义图卷积。

Image可以被视为Graph的特殊形式，每个像素代表一个节点，每个像素直接连接到其附近的像素：
在这里插入图片描述 对于3x3窗口，每个节点的邻域就是其周围8个像素点。 类似地，基于空间域的图卷积将中心节点的表示与相邻节点的表示进行卷积，得到中心节点的更新表示。

图的神经网络（NN4G）是基于空间域的ConvGNN的第一个工作，它通过直接汇总节点的邻域信息来执行图卷积，NN4G导出的下一层的节点状态公式为：
在这里插入图片描述
$f$ 是激活函数， $h_v^{(0)}$ 初始化为零向量。上式的矩阵形式为：

扩散CNN (DCNN)认为图的卷积是一个扩散过程。它假设信息以一定的转移概率从一个节点转移到它的一个相邻节点，使信息分布在几轮后达到均衡。DCNN将扩散图卷积定义为：
在这里插入图片描述
其中 $f$ 是激活函数，概率转移矩阵 $P=D^{-1}A$ 。由于扩散的平稳分布是概率转移矩阵幂级数的总和，因此DGC可以定义如下：

这里 $W^{(k)} \in R^{D \times F}$ 。需要注意的是，这里使用了概率转移矩阵的幂，这意味着远处的邻居对中心节点更新的贡献很少。

PGC-DGCNN基于最短路径增加了远处邻居的贡献。PGC-DGCNN定义了最短路径邻接矩阵 $S^{(j)}$ ：如果节点 $v$ 到结节点 $u$ 的最短路径长度为 $j$ ，则 $S_{v,u}^{(j)}=1$ ，否则为0。PGC-DGCNN中的图卷积运算定义如下：
在这里插入图片描述
式中 $\tilde{D}_{ii}^{(j)}=\sum_{l}S_{i,l}^{(j)}$ ， $H_{(0)}=X$ ， $∣ ∣$ 表示向量的连接。

本篇文章提出的GCN是基于空间域的ConvGNN。

1. 引言

考虑在图中对节点进行分类的问题，图中只有少数节点被标记，然后我们的任务是预测未标记节点的标签，这种问题就是图的半监督分类。

解决上述问题比较经典的方法：
在这里插入图片描述
其中 $L_0$ 表示标记数据上的误差， $f$ 可以是神经网络， $X$ 是节点特征向量矩阵， $\Delta=D-A$ 是未归一化的图拉普拉斯矩阵（ $D$ 为度矩阵， $A$ 为邻接矩阵）， $f(X_i)$ 表示节点的编码表示。

上式中加上正则化项后，如果两个节点邻接（ $A_{ij} \neq 0$ ），那么我们会认为它们可能共享同一标签。这种假设会限制模型的表达能力，因为图中的边不一定需要编码节点相似性，也可能是其它信息。

2. 图的快速近似卷积

传统的图卷积：
$H^{(l+1)}=\sigma(AH^{(l)}W^{(l)})$
可以发现，节点的状态向量在通过每一层图卷积进行传播时，都乘上了邻接矩阵 $A$ ，也就是说节点在更新自己状态向量的同时考虑了邻接节点的信息，但并没有考虑到自身的信息，这是因为 $A$ 的对角线为0（除非节点存在自环）。

本文提出的图卷积传播规则：
在这里插入图片描述
其中 $\tilde{A}=A+I_N$ ，即邻接矩阵在原有基础上加上一个单位矩阵，也即每一个节点都增加一条指向自己的边； $\tilde{D}$ 为加上自环后的度矩阵； $W^{(l)}$ 为层权重矩阵； $\sigma(\cdot)$ 为激活函数，比如ReLU； $H^{(0)}=X$ ，也就是节点特征矩阵；经过多层卷积后，我们得到了最终的 $H^{k}$ ， $H^{k}$ 即GCN学到的节点的状态向量表示。

可以发现，本文在传统图卷积的基础上做了两点创新：

$\tilde{A}=A+I_N$ 。每个节点强行加上自环，这样节点的状态向量在向前传播过程中就能考虑到自身的特征信息。
对加上自环后的邻接矩阵 $\tilde{A}$ 进行了归一化： $\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ 。归一化后的邻接矩阵每一行的和都为1。

3. 半监督节点分类

有了上述图卷积的传播规则后，半监督节点分类就变得很简单了。比如说我们要分为两类，那么只需要在GCN后加上一个输出为2的全连接层，然后再经过一个Softmax即可。得到输出后再算出交叉熵损失，然后反向传播更新每一层GCN的参数 $W$ 。

比如考虑只有一个隐藏层的简单模型：
在这里插入图片描述
其中 $\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ ，即加上自环然后进行归一化的邻接矩阵； $W^{(0)}$ 为从输入到隐藏层的权重矩阵； $W^{(1)}$ 为隐藏层到输出层的权重矩阵。