介绍

英文题目：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点相连所有点的权重之和：
$\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是输入维度。