GNN初印象

写在前面：GNN（Graph Neural Network）的理论非常数学，要彻底理解需要线性代数，微积分里面比较深的知识，目前hold不住，本文只是写写目前自己对GNN的感性认识，如有错误，欢迎指正！

从GCN（Graph convolutional network）说起

详细的GNN分类在这里就不赘述了，这篇文章主要关注GCN领域及其应用。GCN应用的代表作是《Semi-supervised classification with graph convolutional networks》。

Task

论文中针对的Task是给图（graph）中的节点（node）分类，semi-supervised classification是因为在这个graph中，只有少量的node有label，我们希望使用已有标签的node和图结构信息来推测graph中其他没有label的node的label。

原始方法

完成这个Task的原始方法是：

image.png

第一项是有label的node的loss，第二项是graph Laplacian正则项，在正则项中引入了graph的信息，论文里指出，这种方法太过依赖于有连接的node很可能有一样的label这种假设，这种假设造成了局限。

GCN

论文中提出了多层图卷积网络的方法来学习graph中隐含的信息：

image.png
公式本身很好理解，其中是表示图信息的normalized的拉普拉斯矩阵，其tensor的形状是[n * n]，表示node的数量大小，表示第个节点与第个节点之间的信息，表示第层图卷积网络所学到的node的embedding，其tensor形状是[n * m]， 表示embedding的维度，所以两个张量相乘的结果是[n * m]，其意义可以通过矩阵相乘仔细品一品。是我们最终需要得到的卷积核权重参数。
那么问题来了，为什么要这样定义公式呢？

谱图卷积

论文中提到公式定义的动机来源于对localized spectral filters on graph 的一阶逼近。
首先，图的谱卷积的定义是：

image.png
这里我理解为卷积核，就是非常重要的要学习的图卷积的卷积核参数，normailized 拉普拉斯矩阵在这里表示为，是的特征向量，是的特征值，是的图傅里叶变换。
虽然这个公式可以完成对图的卷积，但是非常耗费计算资源，尤其是对比较大的图来说。为了解决这个问题，Hammond等人提出可以被K阶的Chebyshev多项式很好的逼近：
image.png
因此，公式（3）可以演变为下面的形式：
image.png
要学习的卷积核参数变为了Chebyshev的多项式系数。
论文接下来叙述了基于图卷积的神经网络模型可以通过以公式（5）的形式叠加多层卷积层构建。通过对公式（5）中一些参数的限制，例如K=1等，公式（5）最终可演变为：
image.png
与公式（2）相比，是不是一样，。

GCN in NLP

2017年有一篇将GCN应用在NMT中的论文《Graph Convolutional Encoders for Syntax-aware Neural Machine Translation》，我们来看看。

• 这篇论文将sentence的依存信息作为graph，sentence中的每一个token作为graph的node。
• 这篇论文将GCN叠加在encoder的上方，对encoder的embedding进行图的学习，GCN与其他网络一起train。
• 这篇论文中有一个实验还挺有趣的，就是把sentence的token进行reorder，看加入了GCN的模型能不能找回正确的顺序，结果很好，正确率高达99.2%。（但是reorder真的能模仿自然语言的顺序吗？!）

这篇论文的核心公式为：

image.png
这个公式可以与上述介绍的公式（2）对比看，两个公式在形式上是一样的，多了一个bias值，与公式（2）中的意义一样。唯一不同的是本文中没有采用图的拉普拉斯矩阵，没有将图的结构信息放在拉普拉斯矩阵中，而是直接把与node有边关系的node的embedding拿出来利用。（这样的话预处理的工作就比较麻烦吧）。

ps：与Graph embedding的关系

graph embedding专门研究将node用低维向量表示，可以将graph embedding后的node vector应用到task中，而GCN可以产生直接与任务相关的embedding。