图卷积神经网络理论基础
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)「函数，都可以使用」傅立叶级数展开法」将它们分解为有限或无限个不同「频率」不同「振幅」的正弦函数的叠加。傅里叶级数展开公式如下：
振幅 有具体的计算公式。 是频率。求和叠加就是线性组合。如果把函数 看成离散点构成的向量，那么就是这些正弦函数「基向量」的线性组合。
举例
举例：分解动图如下：
某个周期函数
, 可以分解为一系列正弦函数的和：
其中各个分量的「振幅」 （有正有负）的确定有专门的公式，此处不详述。而各个分量的「频率」 （ 是角频率， ）恰好是原来函数频率的整数倍(公式中 为整数)，是确定的。
经过分解后的公式完全可以用另一幅图来表示，横坐标为各个分量的「频率」（不断递增的整数），纵坐标为对应「振幅」。即图中，侧面观看到的 。也就是说，频域图中每个点**(频率，振幅)** 对应的就是一个正弦函数中的「频率和振幅」参数。所有正弦函数的频率和振幅参数点组成整幅频域图。
故，周期函数可以通过「傅立叶级数」画出频域图。
进一步欣赏下列图：
傅里叶级数是向量
首先，我们一般描述向量的时候，都有对应的基，即在某组基下的坐标表示构成了向量。默认是单位基时，则不显示提到。
我们发现，给定周期函数 , 频域图中的横坐标频率值实际上可以确定了，即 。进一步，横坐标频率代表的正弦函数实际上就是傅里叶级数的基，即：，可以证明这些基相互正交。而系数 构成的「向量就是傅里叶级数」。因此，傅里叶级数是向量。
也就是说，频域下，「某个曲线」是表示成了关于「正弦函数正交基下」的傅里叶级数向量。而在时域下，某个曲线是表示成了关于「时间」的周期函数。不管时域还是频域，其实反映的都是同一个曲线，只是一个是用函数的观点，一个是用向量的观点。
欧拉公式
首先介绍欧拉公式。我们知道，根据欧拉公式有：(参考如何通俗地解释欧拉公式 )
欧拉公式可以根据泰勒展开推出。通常的理解，我们可以把 看做是「单位圆的圆周运动」来「描述单位圆上的点，」 通过「复平面的坐标」来「描述单位圆上的点」，是同一个点不同的描述方式，所以有 .
接着，根据欧拉公式，重新表示
在我们的例子中， , 。有：
随着时间流逝，t从0开始增长， 这个向量就会旋转起来， 会转1周，也就是 。随着圆周的运动，我们把 向量的「虚部」记录下来（也就是纵坐标），得到的就是 ；在时间轴 上，把 的虚部记录下来就是 。以此类推。
同理，在时间轴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最小的基。
因此，可以通过这一系列类比/桥接，实现在图上的傅里叶变换。
图拉普拉斯算子
首先是标准的拉普拉斯算子定义：
即，非混合二阶偏导数的和。 是拉普拉斯算子作用的「函数」，求函数各向二阶导数再求和，定义为 上的拉普拉斯算子。注意这个是其严谨的数学定义，所有的xxx拉普拉斯算子都是其一个特例，或是某种情况下(比如离散情况下)的一种近似。由于拉普拉斯算子和二阶偏导数密切相关，而二阶偏导数能够衡量函数的smoothness（不变化或缓慢变化时二阶导为0；突变或噪声，则数值不为0。因此容易检测出突变点）。
接着看图像上的处理。图像是一种离散数据（看做是函数的一种特殊形式），那么其拉普拉斯算子必然要进行离散化。
从一阶导数定义说起：(一阶差分近似)
则二阶导数近似等于其二阶差分。
**某个二阶导数等于其在所有自由度上微扰之后获得的增益。**一维函数其自由度可以理解为2，分别是+1方向和-1方向，增益分别为： 和 。总增益为所有方向增益的和。
同理对于图像而言，
上下左右共4个自由度 （当然还可以任意的定义自由度，比如对角线也算的话，就是8个自由度。在卷积时，使用的拉普拉斯模板就对应着1种方式的自由度定义）。在图像上某一点 ，其拉普拉斯算子的值 ，「即为对其进行扰动，使其变化到相邻像素后得到的增益。」
这给我们一种形象的结论：「拉普拉斯算子就是在所有自由度上进行微小变化后获得的增益 (另一种说明，Informally, the Laplacian measures how different the value of f at p is from the average value of the neighbors)。」
那么推广到Graph, 对于有 个节点的Graph, 其邻接矩阵为 。这个Graph的自由度为 。「因为如果该图是一个完全图，即任意两个节点之间都有一条边，那么对一个节点进行微扰，它可能变成任意一个节点。」
那么上面的函数 就理所当然是一个 维的向量，即：
其中， 表示函数在节点 的值（「跟节点相关的信息，如节点属性等，可以是标量或向量，最基本的向量信息就是节点编号one-hot向量，这里先用标量」），类比 在 的值。 可以表示Graph (权重还没考虑)。
对于任意节点 ，对 节点进行微扰，它可能变为任意一个与他相邻的节点 。
前面提到，拉普拉斯算子就是在所有自由度上进行微小变化后获得的增益。对于图而言，从节点 变化到节点 增益是 。不过通常这里头写作取负数的形式（无非就是L=D-W还是W-D的问题），即 。「再考虑边的权重」，可以认为增益是： 。那么对于节点 ，总的增益即为拉普拉斯算子在节点 的值：
上述 去掉是因为非邻接点 。粗体代表矩阵或向量。
对于任意的 , 都有上述的结论。故：
这个公式全称：图拉普拉斯算子作用在由图节点信息构成的向量上 得到的结果等于图拉普拉斯矩阵和向量 的点积。
左式 要看成一个整体(而不是乘法)，即，图拉普拉斯算子作用在由图节点信息构成的向量上 得到的结果。右边是矩阵乘法，即 拉普拉斯矩阵和向量 乘法（当节点的信息为向量时， 为矩阵）。通常， 图拉普拉斯矩阵也直接称作图拉普拉斯算子，即 ，此时就可以认为， 是乘法，只不过实际上「这种写法是等式右边的式子」，而不是左边的式子。
我们可以发现，图拉普拉斯算子作用在「节点信息」 上，并不会改变 的形状。当 , 则 。只不过上述讨论都是基于 为标量展开的。
拉普拉斯矩阵的谱分解
拉普拉斯矩阵的谱分解就是特征分解。由于拉普拉斯矩阵时「半正定对称矩阵」的，因此拥有诸多优秀性质：
-
「对称矩阵一定n个线性无关的特征向量」（n是Graph节点数） -
「半正定矩阵的特征值一定非负」 -
「对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。」
谱分解：
由于半正定对称矩阵，故有：
是「列向量」为单位特征向量构成的正交矩阵。 是由对应特征值构成对角阵。
Dirichlet Energy
Dirichlet Energy衡量了函数的平滑性Smoothness。Dirichlet Energy定义为：
是函数， 是拉普拉斯算子。
我们的目标是寻找「Graph」上Dirichlet Energy最小一组「单位正交基」（每个基都可以看出函数）。
巧合的是，这样的正交基正好就是对拉普拉斯矩阵 进行谱分解得到的特征向量 。
因此，这也是下文从传统傅里叶变换推广到Graph上傅里叶变换时，进行类比和替换的「理论解释」。
Graph傅里叶变换
回顾下传统的傅里叶变换，
是傅里叶系数（即频率为 时的振幅值）。约等号去掉了常数系数，同时 为离散变量时，离散积分等于内积。
为Fourier Basis。可以证明 是「拉普拉斯算子的特征函数」（满足特征方程 ），证明：
在Graph上作类比， 是图拉普拉斯算子 的「特征向量」（满足 ）。即，在Graph中， ，而 和特征值 有关。
因此，为了在Graph上进行傅里叶变换，可以把传统傅里叶变换中的 换成 。（换了种「基」）
| 传统傅里叶变换 | 图傅里叶变换 |
|---|---|
| 频率（ ） | 特征值（ ） |
| 正弦函数（ ） | 特征向量（ ） |
| 振幅（ ） | 振幅（ ） |
则，图上的傅里叶变换写作：
是由节点信息构成的n维向量。做个类似的解释，即特征值 (频率)下， 的Graph傅里叶变换（振幅）等于 与 对应的特征向量 的内积。
推广到矩阵形式，「图傅里叶变换」：
其中， ，即图傅里叶变换，即不同特征值(频率)下对应的振幅构成的向量。 是由节点信息构成的n维向量。
类似的，传统「逆傅里叶变换」：（n个正弦波的叠加）
「迁移到Graph上的逆傅里叶变换」： ，两个基正交，类比于 。
推广到矩阵形式，
个人理解，「Graph傅里叶变换是为了将Graph从Spatial Domain转换到Spectural Domain，使得Graph在Spectural Domain有向量化表示，卷积更方便。这就类比于，传统傅里叶变换为了将Function从Time Domain转换到Frequency Domain，使得Function在Frequency Domain有向量化表示。」
Graph Convolution
「卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积，即对于函数 与 两者的卷积是其函数傅立叶变换乘积的逆变换。」
「类比到Graph上并把傅里叶变换的定义带入」，
为Graph节点信息向量的集合，
-
的Graph傅里叶变换：
-
卷积核 的Graph傅里叶变换为： ，其中， 。实际上， .
-
求图傅里叶变换向量 和 的element-wise乘积，等价于将 组织成对角矩阵的形式，即 ，再求 和 矩阵乘法（稍微想一下就可以知道）。
-
求上述结果的逆傅里叶变换，即左乘 。
则：图上的卷积定义为：
Deep Learning中的Graph Convolution
Deep Learning中的「Convolution就是要设计含有trainable」共享参数的kernel。「从公式1看很直观：graph convolution」的参数就是 ，也就是说，简单粗暴的将其变成了卷积核 。这也是为什么我们前面不把卷积核 的Graph傅里叶变换表示为 的原因，我们要把 变换后的结果 直接作为参数向量 进行学习。
可以得到第一代的GCN，(Spectral Networks and Locally Connected Networks on Graphs)：
「 就是graph上对应于每个顶点的feature构成的向量 ，目前仍然是每个节点信息是标量（即单通道），后续推广到向量很方便（多通道）。」 是该节点卷积后的输出。所有的节点都要经过该操作，得到各自的输出。再 激活后，传入下一层。 。相当于拿这个卷积核每个节点卷一遍。
这个问题在于，
-
复杂度太高，需要对拉普拉斯矩阵进行谱分解求 ，Graph很大时复杂度较高。每次前向传播都要计算矩阵乘积，复杂度 ， 为Graph节点数。
-
卷积核的参数为 ，当Graph很大时， 非常大。
-
卷积核的spatial localization不好。（相对于下一代GCN而言）
第二代的GCN，Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
为了解决上述问题，首先回顾一下，「图傅里叶变换」是关于特征值(频率)的函数 , 即， ，因此可以将上述卷积核 写作 。接着，将 定义成如下「k阶多项式」形式：
代入可以得到：
上述推导第三步应用了特征分解的性质。
上式为第二代的GCN。不需要做特征分解了，直接对拉普拉斯矩阵进行变换。可以事先把 计算出来，这样前向传播的时候，就只需要计算矩阵和相邻的乘法。复杂度为 。如果使用稀疏矩阵（ 比较稀疏）算法，复杂度为 .
那么上式是如何体现localization呢？我们知道，矩阵的 次方可以用于求连通性，即1个节点经过 步能否到达另一个顶点，矩阵 次方结果中对应元素非0的话可达，为0不可达。因此 矩阵的 次方的含义就是代表 之内的节点。进一步，根据拉普拉斯算子的性质。可以证明，如果两个节点的最短路径大于 的话，那么 在相应位置的元素值为0。因此，实际上只利用到了节点的K-Localized信息。
另外，作者提到，可以引入切比雪夫展开式来近似 ，因为「任何k次多项式都可以使用切比雪夫展开式来近似」。(类比泰勒展开式对函数进行近似）。
引入切比雪夫多项式（Chebyshev polynomial) 的 阶截断获得对 的近似，进而获得对 的近似，来降低时间复杂度。
其中， 为经图拉普拉斯矩阵 的最大特征值（即谱半径）缩放后的特征向量矩阵（防止连乘爆炸）。 表示一个「切比雪夫向量」， 是第 维分量。切比雪夫多项式 使用递归的方式进行定义：，其中 。
此时，可以使用近似的 替换原来的 ，可以得到：
其中， 。
因此有，
参数向量 ，需要通过反向传播学习。时间复杂度也是 。
第三代的GCN对上式进一步简化，Semi-Supervised Classification with Graph Convolutional Networks
-
取 ，此时模型是1阶的first-order proximity。即每层卷积层只考虑了直接邻域，类似CNN中3*3的卷积核。
-
深度加深，宽度减小。即，若要建立多阶 proximity，只需要使用多个卷积层。
-
并加了参数的一些约束，如: ，引入renormalization trick，大大简化了模型。
具体推导，首先 代入，
上述推导利用了归一化拉普拉斯矩阵。此时只有两个参数，即每个卷积核只有2个参数， 是邻接矩阵。
进一步简化，假设 ，则此时单个通道的单个卷积核参数只有1个 ：
谱半径 太大，使用renormalization trick（关于这个trick，参考从 Graph Convolution Networks (GCN) 谈起，讲的非常好！），
其中， (相当于加了「self-connection」，本来 对角元素为0) , 。
则：
推广到「多通道」(单个节点的信息是向量，对比图像上3个通道RGB的值构成3维向量)和「多卷积核」(每个卷积核只有1个参数)，即，
其中， 是节点的「数量」， 是通道数，或者称作表示节点的「信息维度数。」 是节点的feature矩阵。
相应的卷积核参数变化：
其中， 为卷积核数量。
则卷积结果写作矩阵形式如下：
最终得到的卷积结果 。即，每个节点的卷积结果的维数等于卷积核数量。
上述操作可以叠加多层，对 激活一下，然后将激活后的 作为下一层的节点的feature矩阵。
第三代GCN特点总结：
-
复杂度为 (稀疏矩阵优化的话) -
只考虑1-hop，若要建模多hop，通过叠加层数，获得更大的感受野。（联想NLP中使用卷积操作语句序列时，也是通过叠加多层来达到获取长依赖的目的）。
参考
[马同学: 从傅立叶级数到傅立叶变换](https://www.matongxue.com/madocs/712/)
[信号频域和时域的关系？- 言东的回答 - 知乎](https://www.zhihu.com/question/21040374/answer/37911622)
[如何理解 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)
由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：
（1）点击页面最上方"AINLP"，进入公众号主页。
（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。
感谢支持，比心
推荐阅读
征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）
完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）
模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法
文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化
斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用
关于AINLP
AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。
阅读至此了，分享、点赞、在看三选一吧🙏
相关内容
微信扫码咨询专知VIP会员