论文解读GCN论文阅读总结

本次要总结的论文是ConvolutionalNeuralNetworksonGraphswithFastLocalizedSpectralFiltering，论文链接GCN[1]，参考的代码实现GCN-code[2]。

不得不说，读懂这篇论文难度较大，因为里面有许多数学推导，要了解较多的数学知识。本人数学一般，因此在读本论文的同时参考了网上部分较优秀的讲解，这里会结合我对论文的理解，对本论文下总结，文末会详细列出我参考的讲解链接。

「建议在非深色主题下阅读本文，pc端阅读点击文末左下角“原文链接”，体验更佳」

回顾卷积定义与CNN

传统傅里叶变换与卷积

拉普拉斯算子与拉普拉斯矩阵

GCN模型

切比雪夫多项式及其捕捉局部特征

GraphCoarsening（图粗化）

文本分类实验(TextCategorizationon20NEWS)

数据预处理步骤

模型部分

实验结果

个人总结

参考文献

回顾卷积定义与CNN

我们知道卷积神经网络(cnn)在图像、视频、语音识别等领域取得了巨大的成功。cnn的一个核心内容就是卷积操作。

在这里插入图片描述

卷积核：上图中的featuremap参数共享机制：假设每个神经元连接数据窗口的权重是固定的

?

对于inputlayer中，不同的数据区域，卷积核参数是共享的，但是不同的输入通道卷积核参数可以不同

?

这种参数共享机制有如下两个优点

大大减少了模型需要学习的参数可以将卷积操作理解为平移不变的滤波器，这意味着它们能够独立于其空间位置识别相同的特征。

在维基百科里，可以得到卷积操作的定义：

为

的卷积

连续形式离散形式?

更深入的理解可参考知乎这个回答：如何通俗易懂地解释卷积？[3]

?

那么对于「不规则或非欧几里德域上」的结构数据，例如社交网络用户数据、生物调控网络上的基因数据、电信网络上的日志数据或单词嵌入的文本文档数据等，可以用图形（graph）来构造，cnn上的卷积操作想直接推广到graph上并不是简单可行的，「因为卷积核池化操作只能作用在规则的网格中。」

在这里插入图片描述

由上面一张社交网络图可以看出，每个顶点的邻居顶点数量可能都不一致，无法直接使用卷积核池化操作进行特征提取。

为此还需要了解傅里叶变换以及拉普拉斯算子。

传统傅里叶变换与卷积

傅里叶变换的核心是「从时域到频域的变换，而这种变换是通过一组特殊的正交基来实现的。即把任意一个函数表示成了若干个正交函数（由sin,cos构成）的线性组合。」

Fourier变换?

为傅里叶变换基函数，且为拉普拉斯算子的特征函数

?Fourier逆变换

定义

是

和

的卷积，则有代入

最后对等式的两边同时作用

，得到也即是：「即对于函数

与

两者的卷积是其函数傅立叶变换乘积的逆变换」

即可以通过傅里叶变换得到函数卷积结果。

那么问题来了，如何类比到graph上的傅里叶变换呢？

拉普拉斯算子与拉普拉斯矩阵

这里只说几点重要的结论

拉普拉斯算子计算了周围点与中心点的梯度差。当

受到扰动之后，其可能变为相邻的之一，「拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总增益」（或者说是总变化）。「拉普拉斯矩阵就是图上的拉普拉斯算子，或者说是离散的拉普拉斯算子」；拉普拉斯矩阵中的第

行实际上反应了第

个节点在对其他所有节点产生扰动时所产生的增益累积。直观上来讲，图拉普拉斯反映了当我们在节点

上施加一个势，这个势以哪个方向能够多顺畅的流向其他节点。「谱聚类中的拉普拉斯矩阵可以理解为是对图的一种矩阵表示形式。」?

拉普拉斯矩阵实际上是对图的一种矩阵表示形式，这句话太重要了更深入的证明请查看拉普拉斯矩阵与拉普拉斯算子的关系[4]

?

上面讲到传统的傅里叶变换：

其中

为拉普拉斯算子的特征函数：

类比到图上，拉普拉斯算子可以由拉普拉斯矩阵

代替。而由于

为半正定对称矩阵，有如下三个性质：

实对称矩阵一定n个线性无关的特征向量

，且

半正定矩阵的特征值一定非负实对阵矩阵的特征向量总是可以化成两两相互正交的正交矩阵

其中

为特征向量，

为特征值构成的对角矩阵。

那么

在图上的傅里叶变换可以表示如下：

其中

表示第

个特征，

表示graph上顶点个数。

?

可以看出等式左边是以特征值为自变量，等式右边以顶点为自变量，同样可以类别理解为从一个域转换到另外一个域

?

表示图

上的顶点数量，

可理解为输入

可理解为作用在顶点

上的函数，故

为长度为

的向量

其中

个特征向量组成的矩阵如下：

其中

为特征值为

对应的特征向量，

、

、

类似

则

「在图上的傅里叶变换」的矩阵形式如下：

即：

同理可以推导

在图上的逆傅里叶变换：

GCN模型

上面已经得出：类比得到图上卷积：

其中

:

其中

为

的参数。

则可得：

=

由此可得：

其中

为激活函数，

就是「卷积核」，注意

为特征值组成的对角矩阵，所以

也是对角的，可以将卷积核记为如下形式

?

这里面的

就是我们要定义的卷积核具体形式

?

这里面的参数

即为模型需要学习的卷积核参数。

论文中将

，也即

?

为

个shape相同的矩阵相加，结果还是矩阵形式注意上式中不同的特征值共享相同的参数

，做到了参数共享

?

继续推导可得：

?

注意得到的还是

个矩阵相加形式

?

可得：

好了，直观上看这样做有以下几个优点：

卷积核只有

个参数，一般

远小于

，参数的复杂度被大大降低了。矩阵变换后，直接用拉普拉斯矩阵

替换，计算

时间复杂度还是

切比雪夫多项式及其捕捉局部特征

可以利用切比雪夫多项式来逼近卷积核函数：

其中

表示切比雪夫多项式，

表示模型需要学习的参数，

表示re-scaled的特征值对角矩阵，进行这个shift变换的原因是Chebyshev多项式的输入要在

之间，因此

由

可得：

其中

在实际运算过程中，可以利用Chebyshev多项式的性质，进行「递推」：

那么这种切比雪夫展开式如何体现其"localize"呢？可以看看下面这个简单例子

在这里插入图片描述

可以由上面这个简单的graph得到图的拉普拉斯矩阵

当

时，卷积核为

：

?

显然K=0时，卷积核只能

转载请注明：http://www.shijichaoguyj.com/wxjq/6642.html