图卷积神经网络理论基础

Graph Convolutional Networks图卷积网络涉及到两个重要的概念，Graph和Convolution。传统的卷积主要应用于Euclidean Structure的数据上（排列很整齐、Grid形式的），如图像、语句等，主要是因为欧式结构数据能够保证卷积的性质，即平移不变性，而Non-Euclidean无法保证平移不变性，通俗理解就是在拓扑图中每个顶点的相邻顶点数目都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。为了能够将卷积推广到Graph等Non-Euclidean数据上，GCN应运而生。那么GCN是如何将卷积推广到Graph上的呢？

 

卷积和傅里叶变换有着密不可分的关系。在数学上，两个函数的卷积等于各自求傅里叶变换转成频域后乘积的逆傅里叶变换。即：Convolution —— Fourier

 

傅里叶变换又可以通过谱图理论推广到Graph上进行变换。Fourier —— Spectral Graph

 

因此自然而然，Convolution —— Fourier —— Spectral Graph，Convolution通过傅里叶变换和Graph发生了联系。

 

从整个的研究进程来看，首先是研究GSP（Graph Signal Processing）的学者提出了Graph上的Fourier Transformation，进而定义了Graph的Convolution，最后与结合起来，发展出来GCN。

 

下文主要先介绍数学中的傅里叶变换，再介绍Graph上的傅里叶变换。最后介绍卷积如何应用在Graph上。

 

傅里叶变换

傅里叶变换可以从多种角度进行表述。

 

从数学角度，傅立叶变换就是将「周期函数」转化为一组「正交基」下的「坐标表示」，这个「坐标表示」就是傅立叶变换的结果。换句话说，周期函数是这些正交基的「线性组合」(向量的叠加), 线性组合「系数构成的向量」就是傅立叶变换的结果。

 

从信号处理领域角度，傅里叶变换将一个周期函数从「时域」（时间与振幅的关系）转化为「频域」（频率与振幅的关系）。做个类比，正交基选择的是正弦函数，每个正弦函数有个「频率」参数值，而每个正弦函数的「振幅」参数就是该基下对应的坐标值。所有正弦函数的「振幅构成的向量」就是傅立叶变换的结果。

 

下面以信号处理领域为例，来进一步理解傅里叶变换。

 

时域和频域

理解傅里叶变换，需要理解两个核心概念：

时域：时间和振幅的关系图，横坐标是时间，纵坐标是振幅。

频域：频率和振幅的关系图，横坐标是频率，纵坐标是振幅。

 

傅里叶级数

任何「周期(T)「函数，都可以使用」傅立叶级数展开法」将它们分解为有限或无限个不同「频率」不同「振幅」的正弦函数的叠加。傅里叶级数展开公式如下：

 

 

举例

举例：分解动图如下：

 

 

 

故，周期函数可以通过「傅立叶级数」画出频域图。

 

进一步欣赏下列图：

 

 

傅里叶级数是向量

首先，我们一般描述向量的时候，都有对应的基，即在某组基下的坐标表示构成了向量。默认是单位基时，则不显示提到。

 

 

 

也就是说，频域下，「某个曲线」是表示成了关于「正弦函数正交基下」的傅里叶级数向量。而在时域下，某个曲线是表示成了关于「时间」的周期函数。不管时域还是频域，其实反映的都是同一个曲线，只是一个是用函数的观点，一个是用向量的观点。

 

欧拉公式

 

 

 

可以用下图来形象化刻画：

 

 

 

 

 

傅里叶级数展开公式中有正弦波，也有余弦波，画频域图也不方便，通过欧拉公式，可以修改为复数形式：

 

 

 

Graph傅里叶变换

图上的傅里叶变换是通过下述联系实施的：

图拉普拉斯算子， Laplacian  Operator—— Graph Laplacian Matrix。

图拉普拉斯的谱分解，Graph Laplacian Matrix —— Spectral Decomposition。

Graph上Dirichlet Energy最小的基， Dirichlet Energy—— Orthonormal Basis —— Spectral Decomposition —— Eigenvectors

傅里叶变换，Fourier —— Fourier Basis —— Laplacian eigenfunctions

根据4，可以证明，Fourier basis = Laplacian eigenfunctions，即Fourier的基(和频率一一对应)是拉普拉斯算子的特征函数 (满足特征方程)。根据1，在Graph上，拉普拉斯算子为拉普拉斯矩阵。根据2，拉普拉斯矩阵的谱分解得到的特征向量(和特征值一一对应)类比特征函数。因此，传统傅里叶变换在Graph的拓展就是将「正弦函数」基替换换成Graph拉普拉斯矩阵的「特征向量」，正弦函数与频率一一对应，特征向量与特征值一一对应。而根据3，这一的替换的根源意义在于，Graph拉普拉斯矩阵的「特征向量」作为一组基的话，这组基是Graph上Dirichlet Energy最小的基。

 

因此，可以通过这一系列类比/桥接，实现在图上的傅里叶变换。

 

图拉普拉斯算子

首先是标准的拉普拉斯算子定义：

 

 

 

 

同理对于图像而言，

 

 

 

 

 

 

 

 

拉普拉斯矩阵的谱分解

拉普拉斯矩阵的谱分解就是特征分解。由于拉普拉斯矩阵时「半正定对称矩阵」的，因此拥有诸多优秀性质：

 

「对称矩阵一定n个线性无关的特征向量」（n是Graph节点数）

「半正定矩阵的特征值一定非负」

「对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。」

 

谱分解：

 

 

因此，这也是下文从传统傅里叶变换推广到Graph上傅里叶变换时，进行类比和替换的「理论解释」。

 

Graph傅里叶变换

 

 

 

 

个人理解，「Graph傅里叶变换是为了将Graph从Spatial Domain转换到Spectural Domain，使得Graph在Spectural Domain有向量化表示，卷积更方便。这就类比于，传统傅里叶变换为了将Function从Time Domain转换到Frequency Domain，使得Function在Frequency Domain有向量化表示。」

 

Graph Convolution

「卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积，即对于函数与两者的卷积是其函数傅立叶变换乘积的逆变换。」

 

Deep Learning中的Graph Convolution

 

 

卷积核的spatial localization不好。（相对于下一代GCN而言）

 

第二代的GCN，Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

 

 

 

 

 

 

第三代的GCN对上式进一步简化，Semi-Supervised Classification with Graph Convolutional Networks

 

 

 

 

参考

[马同学: 从傅立叶级数到傅立叶变换](https://www.matongxue.com/madocs/712/)

 

[信号频域和时域的关系？- 言东的回答 - 知乎](https://www.zhihu.com/question/21040374/answer/37911622)

 

图拉普拉斯算子为何定义为D-W

 

[如何理解 Graph Convolutional Network(GCN)- Becca的回答-知乎](https://www.zhihu.com/question/54504471/answer/360026284)

 

[The Emerging Field of Signal Processing on Graphs](https://arxiv.org/pdf/1211.0053.pdf)

 

[Spectral Networks and Locally Connected Networks on Graphs](https://link.zhihu.com/?target=https%3A//arxiv.org/abs/1312.6203)

 

[Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](http://papers.nips.cc/paper/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering)

 

[Semi-Supervised Classification with Graph Convolutional Networks](https://arxiv.org/abs/1609.02907)

 

[如何理解 Graph Convolutional Network（GCN）？- superbrother的回答 - 知乎](https://www.zhihu.com/question/54504471/answer/332657604)

 

[Semi-Supervised Classification with Graph Convolutional Networks阅读笔记](https://zhuanlan.zhihu.com/p/31067515)

 

[Graph Neural Network Review](https://zhuanlan.zhihu.com/p/43972372)

 

[从 Graph Convolution Networks (GCN) 谈起](https://zhuanlan.zhihu.com/p/60014316)

 

声明：文章收集于网络，版权归原作者所有，为传播信息而发，如有侵权，请联系小编删除，谢谢！