前言
在上一篇文章中我们介绍了图的部分概念以及最简单的图卷积方式，但这里的图卷积在实现起来还存在着一些问题，在这一篇文章中我们从卷积的定义角度导出图上的卷积，再将它用到GCN里。
卷积
学过信号处理相关理论的同学一定知道，卷积就是对信号进行如下操作： 
当然，这是对连续信号，如果信号是离散的，那么就是这样： 
而在图像处理领域，卷积说白了就是把这个公式拓展到了二维嘛： 
其中f就是我们说的卷积核，我们假设卷积核大小为M*N，那么可以认为f函数在除了这个范围后的值为0，那么从负无穷到正无穷的求和就可以变成0到M，0到N的求和，这样，上述式子就变成了我们平常看到的通俗理解卷积，如下图： 
从信号处理的角度来看，卷积计算这么麻烦，有什么用呢？ 众所周知，它和傅里叶变换或者拉普拉斯变换有着密切的关系。可以用下面两句绕口令表述： 卷积的傅里叶变换等于傅里叶变换的乘积 乘积的傅里叶变换等于傅里叶变换的卷积 写成公式： 
正是由于这样的性质，而卷积可以用于还原信号，所以我们用信号傅里叶变换的乘积再做逆变换来计算卷积，从而能做信号处理里的好多事情。 按照这样的思路，如果我们能够导出图的傅里叶变换，我们就能导出图卷积的公式。
傅里叶变换
信号的傅里叶变换
上面说了这么多，那什么是傅里叶变换呢，这里简要带大家回忆一下，如果不懂的同学就自行百度了。 傅里叶变换与逆变换定义如下： 
傅里叶变换为傅里叶级数的拓展，傅里叶级数为求和的形式，只是对于周期信号适用，而当对于任意信号时，可以认为周期趋于无穷，频谱谱线也就无限靠近形成连续谱，求和也变成了积分的形式。 同样，离散的傅里叶变换变成求和号即可。 从另一个角度看，傅里叶变换可以看做是函数与基函数e-jwt的积分，我们研究一下这个基函数。 对其求拉普拉斯，我们可以得到： 
按照特征值的定义：
对于一种变换A，按照线性代数相关知识，其广义特征方程定义为：
其中V是特征向量，λ是特征值
可以看出，e-jwt是拉普拉斯算子的特征函数，而ω与特征值有关。
图的傅里叶变换
按照上一篇博客里证明过的，图的拉普拉斯矩阵其实就是图的拉普拉斯算子，然后套用上面的关系，我们可以得到： 
仿照上面的傅里叶变换的公式，我们可以导出图上傅里叶变换公式： 
按照上一篇博客里拉普拉斯矩阵的特征值分解，可以得到矩阵U,其列向量即为特征向量，这里记做ul。 注意，这里是向量点乘形式，这里的u我们看做复数形式，所以在点乘时，要对u取共轭。 上式求得的是节点i的傅里叶变换值。然后我们可以把这个写成矩阵形式： 
这样我们就得出了图上的傅里叶变换： 
同理，逆变换为： 
其他不变，改为对l求和即可。 其矩阵形式为： 
即： 
注：这里我们的定义是类比下来的，将原傅里叶变换的基函数e-jwt类比为特征向量u，因为他们都和特征值有关。实际上，根据线性代数的知识，可以证明这n个特征向量u是线性空间的一组基，而且是正交基。 在傅里叶变换中，变换后的函数自变量变为特征值ω，故在这里，变换后的自变量变为特征值λ，如下图： 
图卷积
根据上面定义，图上的傅里叶变换与逆变换为： 
根据傅里叶变换与卷积的关系，为了导出图卷积公式，我们计算图与卷积核的傅里叶变换，将其想乘，再求其逆变换： 
带入可得： 
其中⊙ 为哈达马积，即两向量对应元素相乘。 这里对于卷积核的傅里叶变换我们可以写为： 
故可将别扭的哈达马积去掉，写成： 
GCN（图卷积神经网络）
将图卷积相关理论构成神经网络即图卷积神经网络（Graph Convolutional Network）。 在上一篇博客里我们定义了图卷积层的三种形式，这里我们具体地将我们导出的图卷积公式带入。
第一代GCN
在第一代GCN中，作者直接将卷积核的傅里叶变换
设定为可学习的卷积核
，卷积层就变成了下面这个样子： 
其中
即为卷积核 其实，同时对于大型图，可能有上亿个节点，这样卷积核就需要学习上亿个参数。
第二代GCN
为了避免上述的问题，第二代GCN将
设定成
，即把傅里叶变换
设置为一个自变量为
的幂级数，最高次为k。那么参数量就变成了k个，即α。 而按照之前的推导对于拉普拉斯矩阵有性质： 
这样就可以有以下化简： 
那么图卷积层就表示为： 
这个方法太巧妙了，其实就是通过权值共享把要学习的参数量变成幂级数的系数。原来我有几个节点，就得有几个参数，现在我们只需要k个系数就能进行学习。
总结
这篇文章介绍了图卷积的推导以及GCN网络的构建。在最后，把需要学习的参数降为为k个幂级数的系数。 在后来的研究中，研究人员也提出很多种不同的GCN，仅目前pytorch集成的就不下20种了： pytorch geometric的github：https://github.com/rusty1s/pytorch_geometric 其中改进方法大多为对上述幂级数的改进，可以换成其他函数生成方式，或插值方式。如：贝塞尔曲线、B-样条曲线等。 目前，通过B-样条曲线的方法构建的GCN效果很好，该方法来自CVPR2018的论文SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels。 但也不能说其他的方法效果一定不好，目前这方面还在研究中，这些图卷积的方法效果也基本都差不多，在实际应用中通常要经过多次的尝试找到效果最好的一种。
