论文笔记：Semi-Supervised Classification with Graph Convolutional Networks

妖狐艹你老母 2022-02-12 16:23 241阅读 0赞

# 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) f(X,A)对图的结构进行编码，对所有带标签的节点进行有监督训练。
 *   X X X是输入数据， A A A是图邻接矩阵。
 *  在图的邻接矩阵上调整 f ( ⋅ ) f(\\cdot) f(⋅)能让模型从监督损失 L 0 L\_0 L0。

### 2、图上的快速近似卷积 ###

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

(1) H ( l + 1 ) = σ ( D ~ − 1 2 A ~ D ~ − 1 2 H ( l ) W ( l ) ) 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~−21A~D~−21H(l)W(l))(1)

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

### 2、谱图卷积 ###

#### 2.1、原始GCN ####

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

#### 2.2、加速版本的GCN ####

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

#### 2.3、线性模型 ####

*   K = 1 K=1 K=1时，模型有两个参数，GCN公式：
 *   (4) g θ ′ ⋆ x ≈ ∑ k = 0 K θ k ′ T k ( L ~ ) x 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来获得一个更深的模型，提取特征。
 *  近似地认为 λ m a x ≈ 2 \\lambda\_\{max\} \\approx 2 λmax≈2，公式(5)可以简化为下式：
 *   (5) g θ ′ ⋆ x ≈ θ 0 ′ x + θ 1 ′ ( L − I N ) x = θ 0 ′ x − θ 1 ′ D − 1 2 A D − 1 2 x 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−21AD−21x(5)
    
     *  这里有两个自由参数： θ 0 ′ \\theta\_0^\{\\prime\} θ0′和 θ 1 ′ \\theta\_1^\{\\prime\} θ1′。滤波器的参数在整个图上共享。
     *  通过连续堆叠这种形式的滤波器，可以作用到卷积节点的 K K K阶领域上，其中 K K K是卷积层的个数。
 *  进一步简化公式(5)中的模型，公式如下：
 *   (6) g θ ⋆ x ≈ θ ( I N + D − 1 2 A D − 1 2 ) x 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−21AD−21)x(6)
    
     *  这里令 θ = θ 0 ′ = − θ 1 ′ \\theta=\\theta\_\{0\}^\{\\prime\}=-\\theta\_\{1\}^\{\\prime\} θ=θ0′=−θ1′，将公式(5)中的两个参数都替换成了 θ \\theta θ。
     *  但是，这里的 I N + D − 1 2 A D − 1 2 I\_\{N\}+D^\{-\\frac\{1\}\{2\}\} A D^\{-\\frac\{1\}\{2\}\} IN\+D−21AD−21的特征值范围为 \[ 0 , 2 \] \[0, 2\] \[0,2\]，这可能会导致数值不稳定和梯度消失/爆炸。所以还需要增加一步归一化操作。
     *  归一化：
        
         *   I N + D − 1 2 A D − 1 2 → D ~ − 1 2 A ~ D ~ − 1 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−21AD−21→D~−21A~D~−21
         *   A ~ = A + I N \\tilde\{A\}=A+I\_\{N\} A~=A\+IN
         *   D ~ i i = ∑ j A ~ i j \\tilde\{D\}\_\{i i\}=\\sum\_\{j\} \\tilde\{A\}\_\{i j\} D~ii=j∑A~ij
 *  现在可以将卷积操作推广到信号 X ∈ R C × F X \\in \\mathbb\{R\}^\{C \\times F\} X∈RC×F，输入通道数为 C C C，有 F F F个滤波器。推广的图卷积形式如下：
 *   (7) Z = D ~ − 1 2 A ~ D ~ − 1 2 X Θ Z=\\tilde\{D\}^\{-\\frac\{1\}\{2\}\} \\tilde\{A\} \\tilde\{D\}^\{-\\frac\{1\}\{2\}\} X \\Theta \\tag\{7\} Z=D~−21A~D~−21XΘ(7)
    
     *   Θ ∈ R C × F \\Theta \\in \\mathbb\{R\}^\{C \\times F\} Θ∈RC×F是滤波器的参数矩阵。
     *   Z ∈ R N × F Z \\in \\mathbb\{R\}^\{N \\times F\} Z∈RN×F是卷积后输出的信号矩阵。

### 3、半监督节点分类 ###

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

#### 3.1、实例 ####

*  在预处理中，首先计算好： A ^ = D ~ − 1 2 A ~ D ~ − 1 2 \\hat\{A\}=\\tilde\{D\}^\{-\\frac\{1\}\{2\}\} \\tilde\{A\} \\tilde\{D\}^\{-\\frac\{1\}\{2\}\} A^=D~−21A~D~−21。
 *  然后，前向传播的模型可以写成下式：
 *   (8) Z = f ( X , A ) = softmax ⁡ ( A ^ ReLU ⁡ ( A ^ X W ( 0 ) ) W ( 1 ) ) 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 ) ∈ R C × H W^\{(0)\} \\in \\mathbb\{R\}^\{C \\times H\} W(0)∈RC×H是输入到隐藏层的权重矩阵，隐藏层上的特征维度是 H H H。
     *   W ( 1 ) ∈ R H × F W^\{(1)\} \\in \\mathbb\{R\}^\{H \\times F\} W(1)∈RH×F是隐藏层到输出的权重矩阵。
     *   s o f t m a x softmax softmax就不多说了。
 *  损失函数采用交叉熵，评估所有有标签的数据：
 *   (9) L = − ∑ l ∈ Y L ∑ f = 1 F Y l f ln ⁡ Z l f \\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∑FYlflnZlf(9)
 *   Y L \\mathcal\{Y\}\_\{L\} YL为带标签节点组成的集合。
 *  训练：SGD，引入了BN和Dropout。

### 4、实验 ###

*  数据集描述：
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 1]
 *  半监督分类准确率：
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 2]

## 3、参考资料 ##

*  [Semi-Supervised Classification with Graph Convolutional Networks][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70]: /images/20220212/e8c94e1ba6424225bf6b92e7206c5fe3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 1]: /images/20220212/66de763313ca4a9ea1cdb6bf4c58bc0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvbmdiaW5feHU_size_16_color_FFFFFF_t_70 2]: /images/20220212/8d53cb027da54c06a7467f939b376bdd.png
[Semi-Supervised Classification with Graph Convolutional Networks]: https://openreview.net/forum?id=SJU4ayYgl