前言

  在上一篇文章中我们介绍了图的部分概念以及最简单的图卷积方式，但这里的图卷积在实现起来还存在着一些问题，在这一篇文章中我们从卷积的定义角度导出图上的卷积，再将它用到GCN里。  

卷积

  学过信号处理相关理论的同学一定知道，卷积就是对信号进行如下操作：     当然，这是对连续信号，如果信号是离散的，那么就是这样：     而在图像处理领域，卷积说白了就是把这个公式拓展到了二维嘛：     其中f就是我们说的卷积核，我们假设卷积核大小为M*N，那么可以认为f函数在除了这个范围后的值为0，那么从负无穷到正无穷的求和就可以变成0到M，0到N的求和，这样，上述式子就变成了我们平常看到的通俗理解卷积，如下图：     从信号处理的角度来看，卷积计算这么麻烦，有什么用呢？   众所周知，它和傅里叶变换或者拉普拉斯变换有着密切的关系。可以用下面两句绕口令表述： 卷积的傅里叶变换等于傅里叶变换的乘积 乘积的傅里叶变换等于傅里叶变换的卷积   写成公式：     正是由于这样的性质，而卷积可以用于还原信号，所以我们用信号傅里叶变换的乘积再做逆变换来计算卷积，从而能做信号处理里的好多事情。   按照这样的思路，如果我们能够导出图的傅里叶变换，我们就能导出图卷积的公式。  

傅里叶变换

 

信号的傅里叶变换

  上面说了这么多，那什么是傅里叶变换呢，这里简要带大家回忆一下，如果不懂的同学就自行百度了。   傅里叶变换与逆变换定义如下：     傅里叶变换为傅里叶级数的拓展，傅里叶级数为求和的形式，只是对于周期信号适用，而当对于任意信号时，可以认为周期趋于无穷，频谱谱线也就无限靠近形成连续谱，求和也变成了积分的形式。   同样，离散的傅里叶变换变成求和号即可。   从另一个角度看，傅里叶变换可以看做是函数与基函数e^-jwt的积分，我们研究一下这个基函数。   对其求拉普拉斯，我们可以得到：     按照特征值的定义：  

对于一种变换A，按照线性代数相关知识，其广义特征方程定义为：     其中V是特征向量，λ是特征值  

可以看出，e^-jwt是拉普拉斯算子的特征函数，而ω与特征值有关。  

图的傅里叶变换

  按照上一篇博客里证明过的，图的拉普拉斯矩阵其实就是图的拉普拉斯算子，然后套用上面的关系，我们可以得到：     仿照上面的傅里叶变换的公式，我们可以导出图上傅里叶变换公式：     按照上一篇博客里拉普拉斯矩阵的特征值分解，可以得到矩阵U,其列向量即为特征向量，这里记做u_l。   注意，这里是向量点乘形式，这里的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。   但也不能说其他的方法效果一定不好，目前这方面还在研究中，这些图卷积的方法效果也基本都差不多，在实际应用中通常要经过多次的尝试找到效果最好的一种。