原文链接：https://arxiv.org/abs/1609.02907
代码链接： https://github.com/tkipf/gcn.
出处： ICLR
关键词：semi-supervised, graph convolutional networks
一、motivation
通过在图上做卷积学习节点特征，做分类任务。
二、核心思想
1. 图卷积
首先，我们先明确所谓的卷积是什么意思，是计算中心节点和邻居节点的加权求和，本质上就是在汇聚邻居信息。在如图像这种的结构化数据中，卷积核具有平移不变性，而在图这种非结构化数据，CNN卷积核的平移不变形不再适用，我们需要在图拓扑中寻找邻居，然后定义图上的“卷积”操作来汇聚邻居节点的信息
传统的卷积有两种，一种是CNN那种，直接在数据空域中进行计算；还有一种是将数据通过傅里叶变换变到频域中进行计算。在图上，如果使用空域卷积，由于每个节点的邻居都不同，那么没有办法使用共享卷积核进行卷积操作；如果使用频域卷积，就需要先把图上的数据变换到频域，再计算。
作者选择了第二种，在图上使用频域卷积。
传统的频域卷积是这样的：函数和
二者的卷积是其函数傅里叶变换乘积的逆变换，即：
其中，和
是傅里叶变换后的值，
是傅里叶变换的基函数。
那么仿照传统频域卷积，图卷积可以定义为：，也是把
和
分别进行图傅里叶变换到频域相乘再逆变换回来。
对比可以发现，作者把图上的傅里叶变换定义为：，
，其中，
是图拉普拉斯矩阵的特征向量矩阵。所以，定义图卷积的关键在于定义图傅里叶变换，作者是怎么得到图上傅里叶变换公式的呢？
2. 图傅里叶变换
传统傅里叶变换：，
其中，是空域表示，
是频域表示，
是基函数。
作者发现以为基的拉普拉斯算子是：
对照，可以发现，傅里叶变换中的基其实对照过来是矩阵的特征向量，那么将矩阵替换成图拉普拉斯矩阵，就是：
，那么这个
应该也可以做为图傅里叶变换的基。
于是，作者定义图拉普拉斯矩阵的特征向量可以做图傅里叶变换的基，得到：
，
是第
个点的信号，
是特征值。
3. 图卷积核
前面定义图卷积的计算是，把
表示成对角矩阵形式，则有
表示成函数形式为，输入是
，输出是
，
是要学习的卷积核。
作者使用切比雪夫多项式近似做卷积核：，其中，
，则图卷积表示成：
，化简完就不用计算拉普拉斯矩阵的特征向量了。
这里的表示考虑到几阶邻居。
当时，
；
当时，
;
当时，
.
其中，，
是单位矩阵。
将拉普拉斯矩阵变换成
是因为
中，
的取值范围是[-1,1]，而
的范围是[0,1]，需要变换到[-1,1]的范围。
在GCN文章中，作者只考虑了一阶邻居，即的情况，且
，则
，
那么：
因为之间没有约束，那么参数计算量会上升，所以作者把两个参数合并：
其中，.
又因为这个矩阵的特征值
，在神经网络的训练中会导致梯度消失或爆炸，所以：
其中，，
.
所以，最后输入信号，
其中，，
作者使用了两层GCN，表达式为：
其中，
三、直观理解GCN计算公式
隐含层之间的传递
是节点在第
层的隐含表示，左边部分
是图的拉普拉斯矩阵，
是考虑了自连接的邻接矩阵，
是由
计算得到的度矩阵，右边
表示
层神经网络要学习的参数。
直观理解这个公式就是先汇聚自身及邻居节点的信息，然后放入神经网络中学习。
我觉得最重要的就是这些了，剩下的是一些实验相关的内容，不难理解。另外就是作者使用的是半监督学习，只用很少的标签。
四、小结
1. GCN的突出贡献是将空域和频域的卷积操作联系起来，使得图卷积有了理论支撑；
2. 相比早期的图神经网络如node2vec只使用了拓扑结构，GCN使用了图的拓扑结构和节点特征；
3. GCN只考虑了一阶邻居，线性计算比较高效；
4. GCN虽然是学习节点embedding并分类，但它启发了后来很多研究，包括异构图，边分类等等。
网友评论