论文阅读_卷积图神经网GCN
介绍
英文题目：Semi-Supervised Classification with Graph Convolutional Networks
中文题目：使用卷积图神经网络实现半监督分类器
论文地址：https://arxiv.org/abs/1609.02907
领域：自然语言处理，知识图谱，图神经网络
上传时间：2016
出处：ICLR 2017
被引量：10671
代码和数据：
- https://github.com/tkipf/gcn
- https://github.com/kaize0409/pygcn/
阅读时间：22-03-11
泛读
- 针对问题：图节点多分类，半监督学习
- 结果：在知识图和引文图数据集中，有效提升了精度和效率
- 核心方法：基于频谱图，卷积神经网络，编码时考虑到图结构和节点的特征
- 难点：几乎全是公式推导，先验知识太多，单看公式看不懂
- 泛读后理解程度：30%
（看完题目、摘要、结论、图表及小标题）
精读
摘要
论文提出了基于图的，使用类似卷积神经网络的半监督学习方法。选择卷积结构让我们在建模时更注重邻近的节点。模型隐藏层编码同时考虑了局部结构和节点特征。相较于之前模型效果明显提升。
1. 介绍
论文主要解决图中节点的分类问题，且只对图中部分节点打了标签，使用半监督学习方法，通过显式的基于图的规则的方式打标签。在损失函数中使用了拉普拉斯正则化项：
\[ L=L_0+\lambda L_{reg}\qquad (1) \]
其中：
\[ L_{reg}=\sum_{i,j}A_{ij}||f(X_i)-f(X_j)||^2=f(X)^T\Delta f(X) \]
其中 L0 是有标签部分的误差（分类的类别），λ是正则化项的权重 Lreg 通过所有数据（含有标签和无标签）计算得出；把神经网络编码作为函数 f，X 是节点的原始的特征矩阵。\(\Delta=D-A\)，其中 A 是领域矩阵（其值可以是 0/1 值，也可以是权重），D 是度矩阵，∆ 是拉普拉斯矩阵，有时也用符号 L 表示。
预备知识
邻接矩阵
定义权重 Aij 为点 vi 和点 vj 之间的权重，所有点间线的权重 Aij 组成邻接矩阵 A，第 i 行第 j 值表示为 Aij。
度矩阵
定义 di 是与 i 点相连所有点的权重之和：
\[ di = \sum_{j=1}^n A_{ij} \]
度矩阵 D 是一个对角矩阵（主对角线上有值）：
\[ D=\left(\begin{matrix} d1 & ... & ...\\ ... & d2 & ...\\ ... & ... & ... \\ ... & ... & dn\end{matrix} \right) \] #### 拉普拉斯矩阵 \[ L=D-A \]
拉普拉斯算子
拉普拉斯矩阵就是图结构上的拉普拉斯算子，或者说是离散的拉普拉斯算子。
拉普拉斯算子对应的运算是：二阶导数，即散度。它用于衡量一个节点变化之后，对其他相邻结点（也可以说是整个图）的干扰总收益 (总变化)：将所有相邻的点相加再减去该中心点 x 的相邻个数。
\[ \Delta f= \sum \frac{\partial f}{\partial^2x} \]
离散函数的一阶导（含义是：一个节点与它邻近节点的差异）：
\[ \frac{\partial f}{\partial x}=f'(x)=f(x+1)-f(x) \]
离散函数的二阶导（一个节点与它前后两个点组成的关系，是平滑还是尖峰）
\[ \begin{aligned} \frac{\partial f^2}{\partial x^2}&=f''(x) \approx f'(x+1)-f'(x) \\ &=f(x+1)+f(x-1)-2f(x) \end{aligned} \]
对于某一个点 i，
\[ \Delta f_i=\sum_{j\in N_i}(f_i-f_j) \]
如果边具有权重 Aij，则有：
\[ \Delta f_i=\sum_{j\in N_i}A_{ij}(f_i-f_j) \]
当 i,j 无边相连时，Aij=0，所以 Ni 就可以变成 N。
\[ \begin{aligned} \Delta f_i & =\sum_{j\in N}A_{ij}(f_i-f_j) \\ & =\sum_{j\in N}A_{ij}f_i -\sum_{j\in N}A_{ij}f_j \\ & = d_if_i-A_{i:}f \end{aligned} \]
空间的二阶导：
\[ \Delta f= \sum \frac{\partial f}{\partial^2x}=(A-D)f=Lf \] ### 正文
正则化项 Lreg 的目标是让有连接的点在编码后差异足够小，整个图更平滑。该公式一依赖假设：图中连通的节点共享相同标签，这限制了模型的表述能力，因为边不只用于编码节点的相似性。
使用神经网络对图结构编码，用节点特征 X、邻接矩阵 A 和函数 f 编码：f(X,A)，利用有标签和无标签数据共同训练模型，使模型能够学习到对所有节点均适用的规则。
本文贡献：
- 介绍了一种简单而有效的神经网络模型分层规则，它使用图谱卷积的一阶近似。
- 示范了用半监督学习的，基于图的神经网络方法，解决图节点分类问题，模型的精度和效率方面相较于 SOTA 都有显著提升。
2. 图的快速近似卷积
对于图神经网络 f(X,A)，文中提出了多层图卷积网络（GCN），下图展示了基于层的递推，每个隐藏层计算如下：
\[ H^{(l+1)}=\sigma(\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}) \qquad(2) \]
其中 \(\widetilde{A}=A+I_N\)，A 是邻接矩阵，它表示了节点与其邻居的相关信息，\(I_N\) 是单位矩阵（对角线全 1 其它为 0），它补充了该节点自身的信息。计算度矩阵 \(\widetilde{D}_{ii}=\sum_j\widetilde{A}_{ij}\)，也考虑了节点自身的信息。\(W^{(l)}\) 是对不同层分别训练的权重参数。σ是激活函数。H 为隐藏层，H(0)=X。
2.1 谱图卷积
预备知识
卷积
- 卷积 (Convolution) 是通过两个函数 f 和 g 生成第三个函数的一种数学算子。
- CNN 中卷积是离散卷积，两个函数分别是卷积核和图片像素值，它实现了对图片的局部连接和参数共享。
- 图卷积：拓扑图中每个顶点的相邻顶点数目都可能不同，某个点可能与所有点都有连接，也可能部分连接，所以没办法用直接用卷积核过滤某一部分；因此，需要借助拉普拉斯矩阵实现卷积。
特征分解
机器学习_用PCA主成分分析给数据降维#1 特征值与特征向量
傅里叶变换
傅里叶变换是一种投影，比如将函数拆解成无数个不同频率正弦波之和。
空间傅里叶变换：一个 N 维空间，只要找到该空间的基，该空间的任意向量就都可以由正交基线性组合。
函数傅里叶变换：将一个函数展开成正交函数基的线性组合。
图的傅里叶变换：在图上找正交基，图上任意点可表示为正交基的线性组合。
因此，只要找到图的正交基，就可以完成图的傅里叶变换，再由卷积定理，就可以实现对图的卷积。
卷积定理
函数卷积的傅里叶变换是函数傅立叶变换的乘积。
\[ f\star g=F^{-1}\{F(f)\cdot F(g)\} \]
求卷积就变成了，两个函数分别做傅里叶变换，相乘后，再反向傅里叶变换即可。
图的频域变换步骤
- 创建图的表征矩阵
- 特征分解：计算矩阵的特征值和特征向量；通过特征向量将节点从空间映射到频域（拉普拉斯矩阵是对称的，所以可以进行对角化，也就是找到正交基）
- 进行下一步操作：基于新的表征，进行聚类或分类……
\[ L=U\Lambda U^T=(u_1,u_2,...,u_n)\left( \begin{matrix} λ1 & & \\ & ⋱ & \\ & & λn \end{matrix} \right) \left( \begin{matrix} u_1\\ u_2\\ ... \\ u_n \end{matrix} \right) \]
特征向量 U，特征值 \(\Lambda= \{\lambda_1,\lambda_1,\ldots,\lambda_n\}\)，\(u_l\) 是对应于 \(\lambda_l\) 的基。设特征值从大到小是 \(\lambda_1\) 到 \(\lambda n\)，其中 \(\lambda_1\) 影响最大，那么保留前 k 个 \(\lambda\) 就可以大致逼近原来 L。
图傅里叶变换是在将一个图信号分解到不同平滑程度的图信号上，就像传统傅里叶变换将函数分解到不同频率的函数上一样。
图傅里叶变换将图信号往拉普拉斯特征向量上投影，也是一种信号分解。如果将图看作信号的函数，把对图中节点的操作 f(i) 映射成了频域的 \(\hat{f}(\lambda_1)\)，其中 i 是节点，\(\lambda_1\) 是特征值，把对节点的变换变成了对特征值的变换。\(\hat{f}\) 是对整体的变换。
正文
由于无法直接在图上进行卷积操作，如果想实现卷积，需要借助拉普拉斯矩阵。经过变换，图中所有节点的特征都可以被图的拉普拉斯矩阵的特征向量的线性组合表示。
图卷积需要使用卷积核 gθ缩放每个节点（公式 3 左边），公式右边的 gθ是对特征值的卷积，θ为参数，其个数和图中节点个数相同：
\[ g_\theta \star x=Ug_\theta U^Tx \qquad (3) \]
这里 x 是图中节点的输入向量，左边的星指卷积，即对 x 的卷积，U 是拉普拉斯矩阵的特征向量（图的正交基），Λ是特征值组成的对角矩阵，\(U^Tx\) 是对 x 的傅里叶变换。可将右侧的 gθ看成对拉普拉斯矩阵特征值的函数，即 \(g\theta(\Lambda)\)。如果想使用式 3，需要对 L 做特征分解得到 U，计算量是 \(O(N^2)\)，对大图来说计算量太大。此时：
\(g_\theta(\Lambda)\) 是一阶的情况，它只考虑节点的一跳之内的近邻，如果需要支持多跳，则还需考虑 \(\Lambda^k\)：
\[ g_\theta(\Lambda) \approx \sum_{k=0}^K \theta_k \Lambda^k \]
然后，使用了切比雪夫多项式方法逼近 \(g\theta(\Lambda)\) 函数，它通过设置 k 值只关注 k 跳内的关系。
\[ g_{\theta'}(\Lambda) \approx \sum_{k=0}^K \theta_k'T_k(\widetilde{\Lambda}) \qquad (4) \]
这里的 \(\widetilde{\Lambda}=\frac{2}{\lambda_{max}}\Lambda-I_N\)，λmax 是 L 矩阵的最大特征值，计算后相当于做了正则化，将特征值映射到[-1,1] 之间；θ′ 是切比雪夫系数向量，由切比雪夫不等式的定义可知：
\[ T_k(x)=2xT_{k-1}(x)-T_{k-2}(x) \]
其中 T0(x)=1，T1(x)=x。Tk 可以迭代计算，从而降低了计算复杂度。
考虑到文中遇到的现实问题是对 x 的卷积，代入傅里叶变换，最后简化得到：
\[ g_{\theta'}\star x \approx \sum_{k=0}^{K}\theta_k'T_k(\widetilde{L})x\qquad(5) \]
同样的 \(\widetilde{L}=\frac{2}{\lambda_{max}}L-I_N\)，问题就变成求解 K 次多项式问题，它只依赖节点，及与节点最多在 K 跳内的邻居。其复杂度为 O(|E|)，E 为边数，与边的数据成线性关系。
切比雪夫多项式实现的目标是最佳逼近，它利用以递归方式定义的多项式序列，gθ(Λ) 可以用切比雪夫多项式 Tk(X) 的截断展开式来很好地逼近 K 阶。
2.2 基于层的线性模型
以下是此论文的优化重点。
对于公式 5，如果限制 K=1，也就是每个节点只考虑它的一阶邻居，上述函数就变成了拉普拉斯谱频的线性函数（从而不再受切比雪夫多项式的规则限制），将其看作一层，通过堆叠多层，来实现丰富的表达能力。我们希望模型对于较宽的度分布，可以平衡图中局部领域的过拟合；另外，多层机制也可以构建更深的网络，来提升模型在多领域的建模能力。
当 K=1 时，最大特征向量λmax≈2
\[ \begin{aligned} g_{\theta'}\star x & \approx \theta_0'x+\theta_1'(L-I_N)x\\ & =\theta_0'x-\theta_1'D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x \qquad (6) \end{aligned} \]
这是由于：
\[ L=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}=I_n-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \]
公式 5 被拆成了两部分，前一部分计算当前节点，后一部分计算领域节点，卷积核可被整个网络共享，连续应用卷积核有效地卷积节点的第 k 阶邻域，其中 k 可看作卷积层的数目。
实际应用时，通过限制参数数目，既可以避免过拟合，也可以减少运算量，进而得到以下公式：
\[ g_\theta\star x \approx \theta(I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x \qquad (7) \]
将参数定义为 \(\theta=\theta_0'=-\theta_1'\)，\(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\) 是[0,2] 范围内的特征值，在神经网络上连续使用同一操作可能引起梯度爆炸或梯度消失，使用 \(I_N\)，将 A 和 D 变成了 \(\widetilde{A}\) 和 \(\widetilde{D}\)。
根据以上定义，\(X\in R^{NxC}\)，N 是节点数，C 是输入的特征维度，计算新的节点表征：
\[ Z=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}X\theta \qquad(8) \]
其中 \(\theta\) 是参数矩阵，Z 输出的信号矩阵。计算复杂度是 O(|E|FC)，其中 F 是输出维度，C 是输入维度。
3. 半监督的节点分类问题
通过有监督学习，左图：将输入为 C 维的特征（节点 X 以及节点间的关系 A），编码成输出 F 维特征（向量表示 Z），最终实现分类 y。其中黑线表示图的边，它在多层之间共享。右图：用颜色标出结果。
3.1 示例
接下来，以两层的 GCN 为例，前向传播过程如下式所式：
\[ \begin{aligned} Z &=f(X,A) \\ & =softmax(\hat{A}ReLU(\hat{A}XW^{(0)})W^{(1)}) \qquad (9) \end{aligned} \]
w0 是一个 CxH 的矩阵用于将输入数据转换到隐藏层；W1 是 HxF 的矩阵，用于将隐藏层转换为输出；softmax 用于处理最后的多分类，最后用交叉熵作为误差函数：
\[ L=-\sum_{l\in y_L}\sum_{j=1}^F Y_{lf}\ lnZ_{lf} \qquad (10) \]
其中 yL 是有标签的节点集合。在学习过程中训练 W0 和 W1。
3.2 实现
代码由 TensorFlow 实现，训练基于 GPU 环境，计算复杂度是 O(|E|CHF)。
4. 相关工作
4.1 基于图的半监督学习
基于图的半监督学习有两大方向：图的拉普拉斯正则化；基于图嵌入的方法。
最近，图嵌入方法进一步被关注，它源于 skip-gram 模型，DeepWalk 通过随机游走学习邻近节点，LINE 和 node2vec 又优化了随机游走（深度/广度优先），还有其它一些图嵌入的优化方法。
4.2 图神经网络
将神经网络应用到图结构，可以追溯到 2005 年，2009 年提出了使用 RNN 框架，2015 年将 CNN 引入图结构，然后引入度矩阵，本文也进一步利用不同节点的度来规范化邻接矩阵。
2016 年提出的使用图神经网络解决节点分类问题，其复杂度较高，是 \(O(N^2)\)。本文中方法基于 2014 年提出的谱图卷积神经网络，文中方法提高了大规模网络中的模型的可扩展性和分类性能。
5 实验
5.1 数据集
实验数据包括引文网络和知识图，如表 -1 所示：
引文网络的输入是用词袋方法提取的每篇文章的词向量，以及文章间的引用关系，用 0/1 二值表，即无向图，因此邻接矩阵 A 为对称矩阵。对各篇文章打了类别标签进行训练。NELL 知识图是用一组边 (关系) 连接的实体，实体使用向量表示。
6 ## 结果
6.1 半监督的节点分类
与其它模型比较：
6.2 传播模型评价
使用不同传播模型的效果对比如下：
6.3 每次迭代的耗时
7. 讨论
7.1 半监督模型
文中提出的模型克服了之前模型的两种限制：边仅仅编码节点的相似性；多步 pipeline 难以被优化的问题。模型效率更高，且提升了分类性能。
实验证明，公式 8 提出的简化模型，不仅简化了复杂度和参数，还在很多数据集中表现更好。
7.2 局限性和未来的工作
内存
实验中，当图太大时，无法使用 GPU 计算，只能使用 CPU，其时间尚可接受。使用多 batch 的方法，会把某些领域切断，所以可能影响模型效果。
有向边和边的特征
文中模型目前无法支持边的特征，且只能支持无向图，在实验中处理知识图时，通过对边的处理可以部分解决此问题。
限制假设
论中假设自连接与相邻节点的边同等重要，但对于某些数据集，给其赋予不同权重效果可能更好
\[ \widetilde{A}=A+\lambda I_N \]
参考
《SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS》论文阅读（一）