Semi-Supervised Classification with Graph Convolutional Networks

1、四个问题

1. 要解决什么问题？
   • 半监督任务。给定一个图，其中一部节点已知标签，剩下的未知，要对整个图上的节点进行分类。
2. 用了什么方法解决？
   • 提出了一种卷积神经网络的变种，即提出了一种新的图卷积方法。
   • 使用谱图卷积（spectral graph convolution）的局部一阶近似，来确定卷积结构。
   • 所提出的的网络可以学习图上局部结构的特征，并进行编码。
3. 效果如何？
   • 在引文网络（citation network）和知识图谱（knowledge graph）等的数据集上比其之前的方法效果更好。
4. 还存在什么问题？
   • 最大的问题就是对GPU显存的占用较大，要使用较大规模的图来训练网络只能用CPU替代。
   • 文中的模型只是为无向图设计的，并不支持对边特征的提取。尽管能够将一个有向图看做一个无向加权联合图，但这个模型对于有向图的支持能力还是有限。

2、论文概述

1、简介

• 使用神经网络$f(X, A)$f(X,A)对图的结构进行编码，对所有带标签的节点进行有监督训练。
• $X$X是输入数据，$A$A是图邻接矩阵。
• 在图的邻接矩阵上调整$f(\cdot)$f(⋅)能让模型从监督损失$L_0$L0​。

2、图上的快速近似卷积

• 图卷积的前向传播公式：

$H^{(l+1)} = \sigma( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)} ) \tag{1}$H(l+1)=σ(D~−21​A~D~−21​H(l)W(l))(1)

• $ \tilde{A} = A + I_N $ 是无向图$G$G的自环邻接矩阵。
• $I_N$IN​是单位矩阵。
• $ \tilde{D}{ii} = \sum_j \tilde{A}{ij} $ 是$\tilde{A}$A~的度矩阵。
• $W^{(l)}$W(l)是可训练的权重矩阵，即网络的参数。
• $\sigma(\cdot)$σ(⋅)是**函数，比如ReLU。
• $H^{(l)} \in \mathbb{R}^{N \times D}$H(l)∈RN×D是第$l$l层的**矩阵，即网络的输出。$H^{(0)}=X$H(0)=X，第一层为输入。

2、谱图卷积

2.1、原始GCN

• 将图卷积通过傅里叶变换拓展到图的频域中。
• 对于一个输入信号$x \in \mathbb{R}^N$x∈RN，在傅里叶域中取一个$\theta \in \mathbb{R}^N$θ∈RN为参数的滤波器$g_{\theta} = diag(\theta)$gθ​=diag(θ)：
• $g_{\theta} \star x=U g_{\theta} U^{\top} x \tag{2}$gθ​⋆x=Ugθ​U⊤x(2)
  • $U$U是图的拉普拉斯矩阵$L$L的特征向量矩阵。
  • 拉普拉斯矩阵：$L=I_N - D^{-\frac{1}{2}} A D^{-\frac{1}{2}} = U \Lambda U^T$L=IN​−D−21​AD−21​=UΛUT。
    • $\Lambda$Λ是拉普拉斯矩阵$L$L的特征值组成的对角矩阵。
    • $U^T x$UTx就是图上的傅里叶变换。
  • 也可以将$g_{\theta}$gθ​看成是拉普拉斯矩阵$L$L的一系列特征值组成的对角矩阵$g_{\theta}(\Lambda)$gθ​(Λ)。
  • 公式(2)中做的事就是，借助傅里叶变换，将原始信号$x$x变换到频域，在频域乘上一个信号，再做傅里叶逆变换还原到空域。由傅里叶变换的特性有，在频域相乘相当于空域卷积，这样就回避了空域上对不确定结构的图进行卷积的问题。
• 这是最原始的GCN，但是这套方法的缺点就是计算非常复杂，每次需要对矩阵进行分解，如果图的规模非常大，这会带来巨大的计算开销。

2.2、加速版本的GCN

• 为了减少计算量，有人提出一个特殊的卷积核设计方法，即：将$g_{\theta}(\Lambda)$gθ​(Λ)用切比雪夫多项式进行$K$K阶逼近。
• 切比雪夫多项式：
  • $T_0 (x) = 1$T0​(x)=1
  • $T_1(x) = x$T1​(x)=x
  • $T_k(x) = 2x T_{k-1}(x) - T_{k-1}(x)$Tk​(x)=2xTk−1​(x)−Tk−1​(x)
• 改进的卷积核：
  • $g_{\theta^{\prime}}(\Lambda) \approx \sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{\Lambda}) \tag{3}$gθ′​(Λ)≈k=0∑K​θk′​Tk​(Λ~)(3)
    • $\tilde{\Lambda}=\frac{2}{\lambda_{\max }} \Lambda-I_{N}$Λ~=λmax​2​Λ−IN​。$\lambda_{max}$λmax​是拉普拉斯矩阵$L$L中最大的特征值。
    • $\theta^{\prime} \in \mathbb{R}^{K}$θ′∈RK是切比雪夫多项式的系数。
• 将该卷积核代入图卷积的公式：
  • $g_{\theta^{\prime}} \star x \approx \sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{L}) x \tag{4}$gθ′​⋆x≈k=0∑K​θk′​Tk​(L~)x(4)
    • $\tilde{L}=\frac{2}{\lambda_{\max }} L-I_{N}$L~=λmax​2​L−IN​。
    • 这个公式为拉普拉斯算子的$K$K阶切比雪夫多项式形式，即它受到距离*节点$K$K步以内的节点影响。
• 这里的加速版本的GCN，将参数减少到了$K$K个，并且不再需要对拉普拉斯矩阵做特征分解，直接使用即可。

2.3、线性模型

• $K=1$K=1时，模型有两个参数，GCN公式：
• $g_{\theta^{\prime}} \star x \approx \sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{L}) x \tag{4}$gθ′​⋆x≈k=0∑K​θk′​Tk​(L~)x(4)
• 这里的公式(4)就对应一个GCN层。
• 作者在论文中提到，通过使用这种形式的GCN，我们可以缓解模型在图的局部结构上的过拟合。此外，很大程度上减小了计算开销，使得我们可以堆叠多个GCN来获得一个更深的模型，提取特征。
• 近似地认为$\lambda_{max} \approx 2$λmax​≈2，公式(5)可以简化为下式：
• $g_{\theta^{\prime}} \star x \approx \theta_{0}^{\prime} x+\theta_{1}^{\prime}\left(L-I_{N}\right) x=\theta_{0}^{\prime} x-\theta_{1}^{\prime} D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x \tag{5}$gθ′​⋆x≈θ0′​x+θ1′​(L−IN​)x=θ0′​x−θ1′​D−21​AD−21​x(5)
  • 这里有两个*参数：$\theta_0^{\prime}$θ0′​和$\theta_1^{\prime}$θ1′​。滤波器的参数在整个图上共享。
  • 通过连续堆叠这种形式的滤波器，可以作用到卷积节点的$K$K阶领域上，其中$K$K是卷积层的个数。
• 进一步简化公式(5)中的模型，公式如下：
• $g_{\theta} \star x \approx \theta\left(I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right) x \tag{6}$gθ​⋆x≈θ(IN​+D−21​AD−21​)x(6)
  • 这里令$\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$θ=θ0′​=−θ1′​，将公式(5)中的两个参数都替换成了$\theta$θ。
  • 但是，这里的$I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$IN​+D−21​AD−21​的特征值范围为$[0, 2]$[0,2]，这可能会导致数值不稳定和梯度消失/爆炸。所以还需要增加一步归一化操作。
  • 归一化：
    • $I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$IN​+D−21​AD−21​→D~−21​A~D~−21​
    • $\tilde{A}=A+I_{N}$A~=A+IN​
    • $\tilde{D}_{i i}=\sum_{j} \tilde{A}_{i j}$D~ii​=j∑​A~ij​
• 现在可以将卷积操作推广到信号$X \in \mathbb{R}^{C \times F}$X∈RC×F，输入通道数为$C$C，有$F$F个滤波器。推广的图卷积形式如下：
• $Z=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X \Theta \tag{7}$Z=D~−21​A~D~−21​XΘ(7)
  • $\Theta \in \mathbb{R}^{C \times F}$Θ∈RC×F是滤波器的参数矩阵。
  • $Z \in \mathbb{R}^{N \times F}$Z∈RN×F是卷积后输出的信号矩阵。

3、半监督节点分类

• 回到半监督任务上，前面介绍了优化后的图卷积结构。在现在的半监督任务中，作者希望通过已知的数据$X$X和邻接矩阵$A$A来训练图卷积网络$f(X, A)$f(X,A)。 作者认为，在邻接矩阵中包含了一些$X$X中没有的隐含的图的结构信息，而我们可以利用这些信息进行推理。
• 下图中，左图是一个GCN网络示意图，输入有$C$C维特征，输出有$F$F维特征，中间有若干隐藏层，$X$X是训练数据，$Y$Y是标签。右图是使用一个两层GCN在Cora数据集上（只是用了5%的标签）得到的可视化结果。
• 

3.1、实例

• 在预处理中，首先计算好：$\hat{A}=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$A^=D~−21​A~D~−21​。
• 然后，前向传播的模型可以写成下式：
• $Z=f(X, A)=\operatorname{softmax}\left(\hat{A} \operatorname{ReLU}\left(\hat{A} X W^{(0)}\right) W^{(1)}\right) \tag{8}$Z=f(X,A)=softmax(A^ReLU(A^XW(0))W(1))(8)
  • 这是一个很简单的两层GCN。
  • $W^{(0)} \in \mathbb{R}^{C \times H}$W(0)∈RC×H是输入到隐藏层的权重矩阵，隐藏层上的特征维度是$H$H。
  • $W^{(1)} \in \mathbb{R}^{H \times F}$W(1)∈RH×F是隐藏层到输出的权重矩阵。
  • $softmax$softmax就不多说了。
• 损失函数采用交叉熵，评估所有有标签的数据：
• $\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f} \tag{9}$L=−l∈YL​∑​f=1∑F​Ylf​lnZlf​(9)
• $\mathcal{Y}_{L}$YL​为带标签节点组成的集合。
• 训练：SGD，引入了BN和Dropout。

4、实验

• 数据集描述：
• 
• 半监督分类准确率：
• 

3、参考资料

• Semi-Supervised Classification with Graph Convolutional Networks