SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS ICLR2017

基于图卷积网络的半监督学习

论文：Semi-Supervised Classification with Graph Convolutional Networks 作者：Thomas N. Kipf, Max Welling 来源：ICLR 2017

概括

semi-GCN是一篇经典的GCN论文，作者提出了一种简单且有效GCN框架，使用切比雪夫一阶展开近似谱卷积，使每一个卷积层仅处理一阶邻域信息，然后通过分层传播规则叠加一个个卷积层达到多阶邻域信息传播。

基于图的半监督学习

图结构反映了节点之间的相似性，大量未标记的样本（节点）加入到模型训练中有助于提升分类效果，故基于图的半监督学习是一件很自然且重要的事情。

传统方法是假设“相连节点应该相似，具有相同标签”，将基于图的正则项Lreg显示加入到损失函数中进行学习：

\begin{aligned} \mathcal{L}&=\mathcal{L}_0+\lambda\mathcal{L}_{reg}\\ \text{with}\quad\mathcal{L}_{reg}&=\sum_{i,j}A_{ij}||f(X_i)-f(X_j)||^2=f(X)^T\Delta f(X) \end{aligned}

这个假设太严格了，极大限制模型能力，因为节点相连不一定都是相似，但会包含附加信息。

谱图卷积简介

GCN主流有两大类方法：

基于空间的方法(spatial domain):将图数据规则化，这样就可以直接用CNN来处理了
基于谱方法(spectral domain):利用谱图理论（spectral graph theory）直接处理图数据，本文是该类方法的代表作，简短介绍下相关的工作。

谱图卷积

谱方法的理论基础，直接对图结构数据及节点特征进行卷积操作

定义为信号(特征)x与卷积核gθ在傅立叶域上的乘积:

g_{\theta}x=Ug_{\theta}U^TX

但上述卷积计算复杂度比较大：特征向量矩阵U相乘计算复杂度为O(|N^2|) ，以及图的拉普拉斯矩阵分解开销。

切比雪夫近似谱卷积

g_{theta}*x\approx \sum_{k=0}^K\theta_k'T_k(\tilde{L})x

使用切比雪夫是因为是递归性质，计算复杂度低
上述多项式取前K项，即表示对k跳内邻居及特征进行卷积计算，即谱图卷积不再依赖于整个图，而只是依赖于距离中心节点K步之内的节点（即K阶邻居）

基于切比雪夫近似的GCN

本文工作

本文对Defferrard的工作进一步简化，每一个卷积层仅处理一阶邻居特征，通过分层传播规则叠加一个个卷积层达到多阶邻居特征传播。

Layer-wise线性模型

近似的谱图卷积虽然可以建立起K阶邻居的依赖，然而，却仍然需要在$\tilde{L}$上进行K阶运算。在实际过程中，这一运算的代价也是非常大的。为了降低运算代价，本文进一步简化了该运算，即限定K=1。此时，谱图卷积可以近似为$\tilde{L}$（或L）的线性函数。

当然，这样做的代价是，只能建立起一阶邻居的依赖。对于这一问题，可以通过堆积多层图卷积网络建立K阶邻居的依赖，而且，这样做的另一个优势是，在建立K>1阶邻居的依赖时，不需要受到切比雪夫多项式的限制。

为了进一步简化运算，在GCN的线性模型中，本文定义λmax≈2。此时，我们可以得到图谱卷积的一阶线性近似：

\begin{aligned} &g_{\theta'}*x\approx\theta_0'x+\theta_1'\left(L-I_N\right)x=\theta_0'x-\theta_1'D^{\text{—}\frac{1}{2}}AD^{\text{—}\frac{1}{2}}x\\ \Rightarrow&\theta\left(I_N-D^{\text{—}\frac{1}{2}}AD^{\text{—}\frac{1}{2}}\right)x \end{aligned}

可以看到，该式中仅有两个参数θ'_0与θ'_1。若需建立k阶邻居上的依赖，可以通过设置k层这样的滤波器来实现。

在实际的过程中，可以通过对参数进行约束来避免过拟合，并进一步简化运算复杂度。例如，可以令

\theta=\theta_0'=-\theta_1'

，从而得到

g_{\theta}*x\approx\theta\left(I_N+D^{\text{—}\frac{1}{2}}AD^{\text{—}\frac{1}{2}}\right)x

需要注意的是，

I_N+D^{\text{—}\frac{1}{2}}AD^{\text{—}\frac{1}{2}}

的特征值范围为[0,2]，这意味着，当不停地重复该操作时（网络非常深时），可能会引起梯度爆炸或梯度消失。为了减弱这一问题，本文提出了一种 renormalization trick：

I_N+D^{\text{—}\frac{1}{2}}AD^{\text{—}\frac{1}{2}}\Rightarrow\tilde{D}^{\text{—}\frac{1}{2}}\tilde{A}\tilde{D}^{\text{—}\frac{1}{2}}

其中，

\tilde{A}=A+I_N,\quad \tilde{D}_{ii}=\sum_j\tilde{A}_{ij}

当图中每个节点的表示不是单独的标量而是一个大小为C的向量时，可以使用其变体进行处理：

Z=\tilde{D}^{\text{—}\frac{1}{2}}\tilde{A}\tilde{D}^{\text{—}\frac{1}{2}}X\Theta

其中，

\Theta\in\mathbb{R}^{C\times F}

表示参数矩阵，

Z\in\mathbb{R}^{N\times F}

为相应的卷积结果。此时，每个节点的节点表示被更新成了一个新的F维向量，该F维向量包含了相应的一阶邻居上的信息。

卷积层

使用切比雪夫一阶展开（K=1，线性）的卷积核，外套一个非线性单元。

H^{(l+1)}=\sigma\left(\tilde{D}^{\text{—}\frac{1}{2}}\tilde{A}\tilde{D}^{\text{—}\frac{1}{2}}H^{(l)}W^{(l)}\right)

$H^{(l)}$为上一个卷积层的输出，表示为节点该层的embedding，作为第l+1个卷积层的输入，

H^{(0)}=X

，X为节点自身特征。

\tilde{D}^{\text{—}\frac{1}{2}}\tilde{A}\tilde{D}^{\text{—}\frac{1}{2}}H^{(l)}

为一阶近似卷积核，可以简单理解成加权平均邻接特征。

增加self-loops，使在卷积计算时也会考虑当前节点自身特征：
$\tilde{A}=A+I$
，A为邻接矩阵
对$\tilde{A}$进行对称归一化：
$\hat{A}=\tilde{D}^{\text{—}\frac{1}{2}}\tilde{A}\tilde{D}^{\text{—}\frac{1}{2}}$
。避免邻居数量越多，卷积后结果越大的情况以及考虑了邻居的度大小对卷积的影响。

σ为非线性激活单元，如RELU，$W^{(l)}$为卷积层参数，每个节点共享该参数。

分层传播

每个卷积层仅处理一阶邻居特征，堆叠起来可以达到处理K阶内邻居特征。

这种作法一方面缓解当节点度分布非常广时的过拟合情况，另外也可以以更少的代价建立更深层的模型。

半监督GCN框架

输入：节点X1, X2, X3, X4，每个节点包含C维特征。

输出：经过卷积层的处理，最终输出F个分类对应的预测概率Z1, Z2, Z3, Z4

训练：其中X1, X4为带标签节点，X2, X3不带标签，共同训练，并计算带标签的节点损失，进行后向传播。

两层GCN例子

Z=f(X,A)=\text{softmax}\left(\tilde{A}\text{ReLU}\left(\tilde{A}XW^{(0)}\right)W^{(1)}\right)

输入:节点特征矩阵
$X\in R^{N\times C}$
及邻接矩阵
$A\in R^{N\times N}$
预处理邻接矩阵A：
$\hat{A}=\tilde{D}^{\text{—}\frac{1}{2}}\tilde{A}\tilde{D}^{\text{—}\frac{1}{2}}$
第一层卷积+ReLU非线性转换：
$H^{(0)}=\text{ReLU}\left(\hat{A}XW^{(0)}\right)$
第二层卷积+softmax转换后输出：
$\begin{aligned} &Z=f(X,A)=\text{softmax}\left(\tilde{A}H^{(0)}W^{(1)}\right)=\text{softmax}\left(\tilde{A}\text{ReLU}\left(\tilde{A}XW^{(0)}\right)W^{(1)}\right)\\ \Rightarrow &Z=H^{(1)} \end{aligned}$