作者：superbrother
来源：https://www.zhihu.com/question/54504471/answer/332657604

1 什么是离散卷积？CNN中卷积发挥什么作用？

了解GCN之前必须对离散卷积（或者说CNN中的卷积）有一个明确的认识：
如何通俗易懂地解释卷积？这个链接的内容已经讲得很清楚了，离散卷积本质就是一种加权求和。

如图1所示，CNN中的卷积本质上就是利用一个共享参数的过滤器（kernel），通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取，当然加权系数就是卷积核的权重系数。

那么卷积核的系数如何确定的呢？是随机化初值，然后根据误差函数通过反向传播梯度下降进行迭代优化。这是一个关键点，卷积核的参数通过优化求出才能实现特征提取的作用，GCN的理论很大一部分工作就是为了引入可以优化的卷积参数。

图1 CNN中卷积提取feature map示意图

注：这里的卷积是指深度学习（CNN）中的卷积，与数学中定义的卷积运算严格意义上是有区别的。两者的区别与联系可以见我的另一个回答：哪位高手能解释一下卷积神经网络的卷积核？

2 GCN中的Graph指什么？为什么要研究GCN？

CNN是Computer Vision里的大法宝，效果为什么好呢？原因在上面已经分析过了，可以很有效地提取空间特征。但是有一点需要注意：CNN处理的图像或者视频数据中像素点（pixel）是排列成成很整齐的矩阵（如图2所示，也就是很多论文中所提到的Euclidean Structure）。

图2 图像矩阵示意图（Euclidean Structure）

与之相对应，科学研究中还有很多Non Euclidean Structure的数据，如图3所示。社交网络、信息网络中有很多类似的结构。

图3 社交网络拓扑示意（Non Euclidean Structure）

实际上，这样的网络结构（Non Euclidean Structure）就是图论中抽象意义上的拓扑图。
所以，Graph Convolutional Network中的Graph是指数学（图论）中的用顶点和边建立相应关系的拓扑图。


那么为什么要研究GCN？原因有三：
(1)CNN无法处理Non Euclidean Structure的数据，学术上的表达是传统的离散卷积（如问题1中所述）在Non Euclidean Structure的数据上无法保持平移不变性。通俗理解就是在拓扑图中每个顶点的相邻顶点数目都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。
(2)由于CNN无法处理Non Euclidean Structure的数据，又希望在这样的数据结构（拓扑图）上有效地提取空间特征来进行机器学习，所以GCN成为了研究的重点。
(3)读到这里大家可能会想，自己的研究问题中没有拓扑结构的网络，那是不是根本就不会用到GCN呢？其实不然，广义上来讲任何数据在赋范空间内都可以建立拓扑关联，谱聚类就是应用了这样的思想（谱聚类（spectral clustering）原理总结）。所以说拓扑连接是一种广义的数据结构，GCN有很大的应用空间。

综上所述，GCN是要为除CV、NLP之外的任务提供一种处理、研究的模型。

3 提取拓扑图空间特征的两种方式

GCN的本质目的就是用来提取拓扑图的空间特征，那么实现这个目标只有graph convolution这一种途径吗？当然不是，在vertex domain(spatial domain)和spectral domain实现目标是两种最主流的方式。

(1)vertex domain

vertex domain(spatial domain)是非常直观的一种方式。顾名思义：提取拓扑图上的空间特征，那么就把每个顶点相邻的neighbors找出来。这里面蕴含的科学问题有二：

a.按照什么条件去找中心vertex的neighbors，也就是如何确定receptive field？
b.确定receptive field，按照什么方式处理包含不同数目neighbors的特征？

根据a,b两个问题设计算法，就可以实现目标了。推荐阅读这篇文章Learning Convolutional Neural Networks for Graphs（图4是其中一张图片，可以看出大致的思路）。

图4 vertex domain提取空间特征示意

这种方法主要的缺点如下：

c.每个顶点提取出来的neighbors不同，使得计算处理必须针对每个顶点
d.提取特征的效果可能没有卷积好

当然，对这个思路喜欢的读者可以继续搜索相关文献，学术的魅力在于百家争鸣嘛！

(2)spectral domain

spectral domain就是GCN的理论基础了。这种思路就是希望借助图谱的理论来实现拓扑图上的卷积操作。从整个研究的时间进程来看：首先研究GSP（graph signal processing）的学者定义了graph上的Fourier Transformation，进而定义了graph上的convolution，最后与深度学习结合提出了Graph Convolutional Network。


认真读到这里，脑海中应该会浮现出一系列问题：

Q1 什么是Spectral graph theory？
Spectral graph theory请参考这个，简单的概括就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质
Q2 GCN为什么要利用Spectral graph theory？
这应该是看论文过程中读不懂的核心问题了，要理解这个问题需要大量的数学定义及推导，没有一定的数学功底难以驾驭（我也才疏学浅，很难回答好这个问题）。所以，先绕过这个问题，来看Spectral graph实现了什么，再进行探究为什么？

4 什么是拉普拉斯矩阵？为什么GCN要用拉普拉斯矩阵？

Graph Fourier Transformation及Graph Convolution的定义都用到图的拉普拉斯矩阵，那么首先来介绍一下拉普拉斯矩阵。

图5 Laplacian 矩阵的计算方法
这里要说明的是：常用的拉普拉斯矩阵实际有三种：
No.1 定义的Laplacian 矩阵更专业的名称叫Combinatorial Laplacian
No.2 定义的叫Symmetric normalized Laplacian，很多GCN的论文中应用的是这种拉普拉斯矩阵
No.3 定义的叫Random walk normalized Laplacian,有读者的留言说看到了Graph Convolution与Diffusion相似之处，当然从Random walk normalized Laplacian就能看出了两者确有相似之处（其实两者只差一个相似矩阵的变换，可以参考Diffusion-Convolutional Neural Networks，以及下图）不需要相关内容的读者可以略过此部分

Diffusion Graph Convolution与Spectral Graph Convolution相似性证明

其实维基本科对Laplacian matrix的定义上写得很清楚，国内的一些介绍中只有第一种定义。这让我在最初看文献的过程中感到一些的困惑，特意写下来，帮助大家避免再遇到类似的问题。

为什么GCN要用拉普拉斯矩阵？
拉普拉斯矩阵矩阵有很多良好的性质，这里写三点我感触到的和GCN有关之处
(1)拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解），这就和GCN的spectral domain对应上了
(2)拉普拉斯矩阵只在中心顶点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处均为0
(3)通过拉普拉斯算子与拉普拉斯矩阵进行类比（详见第6节）
以上三点是我的一些理解，当然严格意义上，拉普拉斯矩阵应用于GCN有严谨的数学推导与证明。

5 拉普拉斯矩阵的谱分解（特征分解）

GCN的核心基于拉普拉斯矩阵的谱分解，文献中对于这部分内容没有讲解太多，初学者可能会遇到不少误区，所以先了解一下特征分解。
矩阵的谱分解，特征分解，对角化都是同一个概念（特征分解_百度百科）。

不是所有的矩阵都可以特征分解，其充要条件为n阶方阵存在n个线性无关的特征向量。

但是拉普拉斯矩阵是半正定对称矩阵（半正定矩阵本身就是对称矩阵，半正定矩阵—百度百科，此处这样写为了和下面的性质对应，避免混淆），有如下三个性质：

• 对称矩阵一定n个线性无关的特征向量
• 半正定矩阵的特征值一定非负
• 对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。

由上可以知道拉普拉斯矩阵一定可以谱分解，且分解后有特殊的形式。

对于拉普拉斯矩阵其谱分解为：

文献中都是最后导出的这个公式，但大家不要误解，特征分解最右边的是特征矩阵的逆，只是拉普拉斯矩阵的性质才可以写成特征矩阵的转置。
其实从上可以看出：整个推导用到了很多数学的性质，在这里写得详细一些，避免大家形成错误的理解。

6 如何从传统的傅里叶变换、卷积类比到Graph上的傅里叶变换及卷积？

把传统的傅里叶变换以及卷积迁移到Graph上来，核心工作其实就是把拉普拉斯算子的特征函数变为Graph对应的拉普拉斯矩阵的特征向量。

(1)推广傅里叶变换

想亲自躬行的读者可以阅读The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains这篇论文，下面是我的理解与提炼：

(a)Graph上的傅里叶变换
传统的傅里叶变换定义为：

那么，可以联想了，处理Graph问题的时候，用到拉普拉斯矩阵（拉普拉斯矩阵就是离散拉普拉斯算子，想了解更多可以参考Discrete Laplace operator），自然就去找拉普拉斯矩阵的特征向量了。

是拉普拉斯矩阵， 是其特征向量，自然满足下式

离散积分就是一种内积形式，仿上定义Graph上的傅里叶变换：

注：上述的内积运算是在复数空间中定义的，所以采用了 ，也就是特征向量 的共轭。Inner product更多可以参考Inner product space。 (b)Graph上的傅里叶逆变换 即在Graph上傅里叶逆变换的矩阵形式为：
式中：的定义与第五节中的相同

(2)推广卷积

在上面的基础上，利用卷积定理类比来将卷积运算，推广到Graph上。

注：很多论文中的Graph卷积公式为：其实式(2)与式(1)是完全相同的。这里主要推(1)式是为了和后面的deep learning相结合。
这部分理论也是我看了很久才想明白的，在此记录下来，如果是想继续探究理论的朋友，可以作为“入门小引”，毕竟理论还很深！对于喜欢实践的朋友，也能初步了解理论基础，也是“开卷有益”。

7 为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基？特征值表示频率？

(1)为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基？

傅里叶变换一个本质理解就是：把任意一个函数表示成了若干个正交函数（由sin,cos 构成）的线性组合。

图6 傅里叶逆变换图示

(2)怎么理解拉普拉斯矩阵的特征值表示频率？

在graph空间上无法可视化展示“频率”这个概念，那么从特征方程上来抽象理解。

其实图像压缩就是这个原理，把像素矩阵特征分解后，把小的特征值（低频部分）全部变成0，PCA降维也是同样的，把协方差矩阵特征分解后，按从大到小取出前K个特征值对应的特征向量作为新的“坐标轴”。
Graph Convolution的理论告一段落了，下面开始Graph Convolution Network

8 Deep Learning中的Graph Convolution

Deep learning 中的Graph Convolution直接看上去会和第6节推导出的图卷积公式有很大的不同，但是万变不离其宗，(1)式是推导的本源。
第1节的内容已经解释得很清楚：Deep learning 中的Convolution就是要设计含有trainable共享参数的kernel，从(1)式看很直观：graph convolution中的卷积参数就是 。
第一代的GCN(Spectral Networks and Locally Connected Networks on Graphs)，简单粗暴地把变成了卷积核 ,也就是：

式（3）就是标准的第一代GCN中的layer了，其中是激活函数，就跟三层神经网络中的weight一样是任意的参数，通过初始化赋值然后利用误差反向传播进行调整, 就是graph上对应于每个顶点的特征向量。第一代的参数方法存在着一些弊端：主要在于： 由于以上的缺点第二代的卷积核设计应运而生。


第二代的GCN(Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering)，把 巧妙地设计成了 ，也就是： 各符号的定义都同第五节。
(4)式就变成了：其中是任意的参数，通过初始化赋值然后利用误差反向传播进行调整。
式(5)所设计的卷积核其优点在于：
（1）卷积核只有K个参数，一般 K远小于n
（2）矩阵变换后，神奇地发现不需要做特征分解了，直接用拉普拉斯矩阵 L 进行变换，计算复杂度变成了
（3）卷积核具有很好的spatial localization，特别地，K就是卷积核的receptive field，也就是说每次卷积会将中心顶点K-hop neighbor上的feature进行加权求和，权系数就是
更直观地看， K=1就是对每个顶点上一阶neighbor的feature进行加权求和，如下图所示：图7 k=1 的graph convolution示意

同理，K=2的情形如下图所示：

图8 k=2 的graph convolution示意
注：上图只是以一个顶点作为实例，GCN每一次卷积对所有的顶点都完成了图示的操作。

9 从数学的角度看Spectral Graph在GCN中的作用

待完善
上面的内容算是“师傅领进门”了，下面就“修行看个人”，推荐两本少林72绝技
深度学习时代的图模型，清华发文综述图网络
清华大学孙茂松组：图神经网络必读论文列表

推荐阅读
CNN 的平移不变性详解
ECCV2018|ShuffleNetV2：轻量级 CNN 网络中的桂冠

微信公众号: 极市平台（ID: extrememart ）
每天推送最新CV干货