全面入门：图卷积网络（GCN）的谱分析

2020 年 4 月 12 日 极市平台

加入极市专业CV交流群，与 10000+来自港科大、北大、清华、中科院、CMU、腾讯、百度等名校名企视觉开发者互动交流！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。关注极市平台公众号，回复加群，立刻申请入群~

本文授权转自大家都叫我0号，https://zhuanlan.zhihu.com/p/124727955，未经允许，不得二次转载。

本文简要介绍了信号处理的一些概念，介绍了图卷积的定义和各种谱方法下的GNN，最后分析了GCN过平滑的原因。大约5千余字，里面有一些公式比较复杂，可能需要手推一下~~。

1 Introduction

某的上一篇文章图表示学习极简教程 ^[1]介绍了图嵌入(Graph Embedding)、图神经网络(GNNs)的一些发展。图表示学习极简教程 ^[2]对GCN、GraphSAGE、GAT等模型进行了介绍，这些介绍都是从空域的角度对图卷积进行分析，也就是说GNNs每层的网络就是对邻居结点的聚合操作。这样的idea似乎很好理解，也很好想到。其实，这些方法的背后蕴含着许多信号分析的重要背景。近日听了 ICT沈老师相关知识 ^[3]的讲授后，某自认为对图卷积网络的谱分析有了更进一步的理解。下面就开始进入正题吧。【注】：如果读者已经了解过卷积、傅里叶变换的相关概念，可以对部分章节选择性跳过。

2 卷积

【注意】：下列公式中的积分、求和上下限在遇到具体问题是会退化为具体的数字。积分上下限为无穷只是它的一般定义。

一维连续卷积

卷积的名字似乎听上去让人感觉有些晦涩，其实它的计算难度并不大。我们给定两个函数和，这两个函数的卷积的计算公式如下(这个公式应该小伙伴们都在概率论中见过)：

二维连续卷积(这里不太重要，理解是怎么算的就行)

和一维卷积类似，对于多元函数，二维的连续函数卷积可以表示为：

一维离散卷积

将连续卷积的积分号变为求和号，就可以得到两个离散函数和一维离散卷积的公式：在此，引用一张很形象的图(结合公式)来帮助小伙伴们理解什么是一维离散卷积：

二维离散卷积

这是卷积神经网络(CNN)的基础，和上述的卷积类似，对两个信号、，我们定义他的二维离散卷积公式为：

这里还是借助一个动图来看看二维的卷积是如何卷的：

不难发现二维离散的卷积是将卷积核进行一个中心对称的翻转后，在进行对应位置相乘求和得到的。然而，实际上大家在CNN的计算中可以省去旋转的步骤，因为卷积核的参数是学来的。

3 傅里叶变换与卷积的另一种求法

由于一些信号在时域内部难以分析，我们将信号先变换到频域，再变换回时域，以便于我们的分析。我们对一个时域信号函数做傅里叶变换：

有时候，我们在时域很难求卷积，我们就要利用下面的卷积公式求解：

这个公式告诉我们，时域卷积的傅里叶变换等于傅里叶变换的乘积。因此，我们可以这样求卷积：

其中，代表傅里叶变换的逆变换。

4 拉普拉斯算子

我们知道，一个二元函数的Nabla算子，可以表示为：那么梯度就可以表示为：下面定义拉普拉斯算子：

显然，我们可以把拉普拉斯算子视为二阶导数。

上述的拉普拉斯算子表示的是连续函数的拉普拉斯算子。那么离散情况下的拉普拉斯算子是什么呢？我们可以用差分来近似我们的“导数”概念。对于一个离散的二元函数，它的拉普拉斯算子可表示为：

我们可以观察一下上面这个式子，它可以写成：

从直观上看，拉普拉斯算子体现的离散值之间的关系为：

根据拉普拉斯算子的定义和图4相关可视化表示，我们可以看出离散拉普拉斯算子描述的是 二维空间上与上、下、右邻居局部差异的和。下一步我们就可以将这个概念迁移到图上去定义图的拉普拉斯矩阵。

5 拉普拉斯矩阵

离散拉普拉斯算子描述的是 二维空间上与上、下、右邻居局部差异的和。迁移到图上，我们将拉普拉斯算子定义为与邻居结点特征信息差异的和，即：其中表示结点的邻居结点，这里的表示第个结点的特征(信号)，简便起见，只有一维(看做数字、标量)。我们用表示结点之间的邻接关系：下面我们将扩充到所有结点集合进行表示：

其中表示结点的度数。

我们将每个结点的扩充到整个图上，得到：

这样我们就定义了图的拉普拉斯矩阵。的对角线元素对应着各个结点的度数，非对角线元素对应着图的邻接矩阵。我们给出一个拉普拉斯矩阵的范例 ^[4]：

性质1：拉普拉斯矩阵有 个线性无关的特征向量

原因：拉普拉斯矩阵是实对称矩阵。

性质2：特征值非负

首先，我们定义图的总变差为矩阵的二次型：

所以是 半正定的矩阵(证明手推一下难度不大)。所以它的特征值均为非负。

注意一下，这里存在一个特殊的特征值0，它对应的特征向量为，这个代入验证即可。

性质3：特征向量相互正交

是实对称矩阵，它的特征向量相互正交，构成一个特征空间。

6 图傅里叶变换与图卷积

普通的傅里叶变化公式为：其中为傅里叶基。我们有：根据广义的特征方程，我们可以看出就是拉普拉斯算子的特征向量，相当于特征值，就相当于拉普拉斯矩阵。

把傅里叶变换的定义扩充到图上。传统傅里叶变换是求信号在上的投影，图傅里叶变换求的是一个信号在正交基上的投影(这里信号是一个维的列向量，表示每一个结点仅为一个数 )。我们定义 图信号的傅里叶变换为：其中，是矩阵特征分解矩阵的转置( )。这里我们注意一下，的每一个列向量为的一个特征向量，的每一个行向量为的一个特征向量。这样与的乘积就实现了一个信号在正交基上的投影，图傅里叶变换完成。

接下来我们就可以很容易地实现傅里叶逆变换：这里用到了矩阵分解的性质：。

在信号处理中我们有如下的卷积公式：

应用到图上，我们定义卷积公式：

其中表示 哈达玛积，就是向量的对应元素相乘(不是矩阵相乘)。我们把其中的向量写成对角阵的形式，这样我们就可以把哈达玛积写成是 矩阵相乘的形式了，即：

我们将对角阵用来表示：其实这里的对角阵就是可供学习的卷积核了。

终于！！！把图信号的卷积定义完了！

7 基于谱方法的各种Net

7.1 Spectral Graph CNN

根据上述的定义，我们知道了如何定义图上的卷积操作。那么网络的前传也就可以定义了：

其中：

在此之前我们讨论的都只有一个特征信息(通道)。这里增加了通道数， , 分别表示第层和第层的通道数。
表示第层的可供学习的卷积核，是一个对角阵。
表示具有个通道(信号)的个结点

该模型存在的问题主要有三：

模型不是spatial localization(局部连接)的；
依赖矩阵分解，前传的时候多次用到矩阵乘法，计算代价大；
卷积核的规模参数收到图规模的控制，特别是对大图而言。

7.2 ChebNet

对于上述的卷积核，我们可以使用阶多项式进行拟合：

那么图卷积就变成了：

这样的操作就将参数个数减少到个，同时也不需要进行矩阵的分解了。同时就算复杂度大大下降。注意，这里的的次方就体现了局部相关特性，这和邻接矩阵次幂的含义类似，代表着阶可达。 ChebNet引入了切比雪夫多项式对进行拟合。切比雪夫多项式的递归定义为：

的阶近似为: 其中，是最大的特征值，这个操作的意义是将特征值调整到的范围中，因为我们知道拉普拉斯矩阵的特征值非负，且有最小值为0(稍加推导就可以得到范围了)。这个操作可以防止梯度爆炸。

现在我们的图卷积公式就可以被进一步写成是：

下面介绍公式之间是如何进行转换的。

的证明：

只要证明：对上述式子应用数学归纳法：

或时，根据切比雪夫多项式的定义，。

假设小于的时候都成立。

证毕。

的转换：

由此我们就得到了新的卷积公式：可以看出，ChebNet解决了7.1中Spectral Graph CNN存在的3个问题。

7.3 平时看到的GCN——ChebNet的一阶近似

我们对ChebNet进行一阶近似，即。我们可以得到下面的公式：

对进行正则化，得到正则化后的表示：正则化后的拉普拉斯矩阵特征值不超过2，所以将的最大特征值近似为为2，。将带入 , , 可以转换成：

其中，值得注意的是，这里的是一个标量。我们将：，分别表示输入输出的通道数。网络层与层时间的传递公式可以表示为：在这个公式中，结合上一篇文章图表示学习极简教程 ^[5]，我们可以看出这个模型是对邻居结点的聚合(1-hop)，当网络加深到K层的时候就会将聚合关系扩充到K跳。

8 GCN——一个低通滤波器

8.1 为什么叫它低通滤波器？

我们有 (这里其实有一点不太严谨的地方，不影响阅读，详细可参考一下从 Graph Convolution Networks \(GCN\) 谈起 ^[6])。我们知道， 特征值的范围是0~2。所以有：可以看出，它的 特征值范围为。在信号与系统中，我们可以将信号转换到频域，通过频率响应函数滤波，再将信号转换到时域完成滤波的操作。这里的频率响应函数为。不难看出，它对信号进行了低通滤波。

8.2 GCN的大问题——Over Smoothing

根据实验，我们的GCN一直无法像CNN那样将网络做深，很大的一个原因就是 过平滑(Over smoothing)。那么这种现象为什么会产生？

在GCN堆叠层的过程中，矩阵被乘了次。我们看看它展开会是什么样子：

其中的只有在当时，有。其余情况下绝对值都不超过1。所以有：

这时：

这里有： ( 表示全1向量)。如果在往下乘，会出现一项:

信号在往下乘的时候就会出现处处相等的情况，所有的结点特征就会趋于一致，过平滑由此产生。

另外，有一种更为容易理解的方法。一层的GCN是对一阶邻居信息的聚合，k层对应的就是k-hop。相信大家听过 六度空间理论，几乎每一个结点的聚合都可以做到很快就把几乎全图进行覆盖。

联系我：Data_LH_ChenAToutlook.com.(AT改为@) 炼丹时间半年多，初涉该领域，如有理解不当或错误的地方欢迎指正。

一些很优秀的参考资料（可下滑）

[1]图表示学习极简教程: https://zhuanlan.zhihu.com/p/112295277

[2]图表示学习极简教程: https://zhuanlan.zhihu.com/p/112295277

[3]ICT沈老师相关知识: https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1zp4y117bB

[4]拉普拉斯矩阵的范例: https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/Laplacian_matrix

[5]图表示学习极简教程: https://zhuanlan.zhihu.com/p/112295277

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

[7]图神经网络在线研讨会2020丨图表示学习和图神经网络的最新理论进展和应用探索: https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1zp4y117bB

[8]Graph Convolutional Network图卷积网络基础理论: https://zhuanlan.zhihu.com/p/100250297

[9]深入浅出图神经网络: https://link.zhihu.com/?target=https%3A//detail.tmall.com/item.htm%3Fspm%3Da230r.1.14.1.21e24bf49k0WwP%26id%3D610178053512%26cm_id%3D140105335569ed55e27b%26abbucket%3D9

[10]图卷积网络 GCN Graph Convolutional Network（谱域GCN）的理解和详细推导: https://link.zhihu.com/?target=https%3A//blog.csdn.net/yyl424525/article/details/100058264

[11]拉普拉斯矩阵: https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/Laplacian_matrix%23Incidence_matrix

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

[13]Convolutional Neural Networks on Graphswith Fast Localized Spectral Filtering: https://link.zhihu.com/?target=https%3A//arxiv.org/abs/1606.09375

[14]Wavelets on Graphs via Spectral Graph Theory: https://link.zhihu.com/?target=https%3A//arxiv.org/abs/0912.3848

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

[16]SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS: https://link.zhihu.com/?target=https%3A//arxiv.org/pdf/1609.02907.pdf

[17]Graph Convolutional Networks: https://link.zhihu.com/?target=https%3A//tkipf.github.io/graph-convolutional-networks/