英文题目：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%
  (阅读主题、摘要、结论、图表和标题)

论文提出了基于图的，使用类似于卷积神经网络的半监督学习方法。卷积结构的选择使我们在建模时更加关注相邻的节点。同时考虑了模型隐藏层的编码局部结构和节点特征。与之前的模型相比，效果明显提高。

定义权重Aij为点vi和点vj之间的权重，所有点间线的权重Aij组成邻接矩阵A，第i行第j值表示为Aij。

定义di是与i点相连所有点的权重之和：
$$di=\sum _{j=1}^n{A}_{ij}$$
度矩阵D是一个对角矩阵（主对角线上有值）：
$$D=\left(\begin{array}{ccc}d1& ...& ...\\ ...& d2& ...\\ ...& ...& ...\\ ...& ...& dn\end{array}\right)$$

$$L=D-A$$

拉普拉斯矩阵就是图结构上的拉普拉斯算子，或者说是离散的拉普拉斯算子。

拉普拉斯算子对应的运算是：二阶导数，即散度。它用于衡量一个节点变化之后，对其他相邻结点（也可以说是整个图）的干扰总收益(总变化)：将所有相邻的点相加再减去该中心点x的相邻个数。
$$\Delta f=\sum \frac{\partial f}{{\partial }^{2}x}$$
离散函数的一阶导（含义是：一个节点与它邻近节点的差异）：
$$\frac{\partial f}{\partial x}=f^{\prime }(x)=f(x+1)-f(x)$$
离散函数的二阶导（一个节点与它前后两个点组成的关系，是平滑还是尖峰）
$$\begin{array}{rl}\frac{\partial f^2}{\partial x^2}& =f^{\prime \prime }(x)\approx f^{\prime }(x+1)-f^{\prime }(x)\\ & =f(x+1)+f(x-1)-2f(x)\end{array}$$
对于某一个点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{array}{rl}\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_i{f}_i-A_{i:}f\end{array}$$
空间的二阶导：
$$\Delta f=\sum \frac{\partial f}{{\partial }^{2}x}=(A-D)f=Lf$$

正则化项Lreg的目标是让有连接的点在编码后差异足够小，整个图更平滑。该公式一依赖假设：图中连通的节点共享相同标签，这限制了模型的表述能力，因为边不只用于编码节点的相似性。

使用神经网络对图结构编码，用节点特征X、邻接矩阵A和函数f编码：f(X,A)，利用有标签和无标签数据共同训练模型，使模型能够学习到对所有节点均适用的规则。

本文贡献：

• 介绍了一种简单而有效的神经网络模型分层规则，它使用图谱卷积的一阶近似。
• 示范了用半监督学习的，基于图的神经网络方法，解决图节点分类问题，模型的精度和效率方面相较于SOTA都有显著提升。