“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。
地址：https://zhuanlan.zhihu.com/p/355043976
01
CNN是针对规则结构的数据，例如图片（点阵）进行卷积运算，来提取特征的局部相关性，但是CNN无法对拓扑图结构的数据进行类似的卷积操作。因此，研究者以图论为基础提出了图卷积。02
采用了离散卷积的形式，即输入X为一个矩阵，卷积核为另一个矩阵，在进行卷积时，结果矩阵的每个点就是当n取不同下标【i，j】时，两个矩阵重合部分的对应乘积再累加。当【i，j】变化时，就相当于上述公式中的n在变化。因此，卷积结果相当于关于【i，j】或n的一个函数的输出值。给定一个[i,j]或n，就得到一个输出矩阵[i,j]位置的值。唯一区别就在于，卷积核可以视为已经180°翻转过的矩阵，所以在实际CNN网络反向传播求卷积核参数时，不会再强调和考虑翻转的事了。03
由上面CNN中卷积的定义可知，都是矩阵在不断平移，每次平移对应位置乘积累加得到输出矩阵的某个位置的值。而拓扑图结构中，每个节点的1跳,2跳。。。邻居都是个数不定的，因此无法做到与CNN卷积核（例如3*3）这种规则尺寸，从而进行卷积。在这种情况下，早期有人用下面的公式进行局部特征的信息提取：在l层的输出结果中，节点v的值（类比于CNN卷积后输出的feature map中的一个点的值）由l层的输入图数据中与节点v相邻的其他节点（也可以包括v自己）的取值进行加权累加。当然这里就没有明确的卷积核的概念了。缺点：非常明显，没有卷积核作为共享参数，只是简单进行了特征的汇聚；另外，当图的规模很大时，计算量也是非常大的。因此，重点来了！当时域很难做的时，人们往往会考虑从频域进行处理。感谢傅里叶，建立起了时域与频域的连接。04
这里不会讲解傅里叶变换的细节，只需要有个直观的认识即可。
从上图（转载自如何理解傅里叶变换公式？）可以看到，任何复杂形状的时域波形，都可以用频域的一组正交基来表示，可以理解为时域的向量被投影到这些正交基构成的新的频域空间中。一个函数可以被理解为一个广义的向量，所以f(t)可以被看做是t=1,t=2......时f(1),f(2).....这些值构成的向量。而向量是可以投影（或变换）到不同向量空间中的。而向量空间又是由一组基向量支撑的。例如因此，要将一个时域的函数（广义的向量）转到频域空间，就要找到合适的频域空间的基向量。这件事被傅里叶搞定了，就是傅里叶级数（针对周期性的函数）。为了可以处理非周期函数，就是傅立叶变换。在图卷积中使用的都是傅里叶变换。频域的信号是F(w)，时域的信号是f(t)。从上面提到的向量投影角度，可以将这个积分理解为f(t)向量与e-iwt向量的内积（投影）。而e-iwt就是撑起频域空间的一组基向量，而且是正交基，证明过程略。那么F(w)就是频域空间中这个信号的坐标了。所以同一个信号，就从时域空间投影到了频域空间。05
预备知识3 拉普拉斯算子的特征向量是傅里叶变换的基向量e-iwt了解了傅里叶变换后，就能够将任意一个函数从时域转换到（投影到）频域，其关键是向e-iwt基向量进行投影。但是如何找到这组基向量呢？GCN中利用拉普拉斯算子和傅里叶变换的基向量建立联系。理解了拉普拉斯算子的定义和物理含义，那么它和傅里叶变换有什么关系呢？那就是拉普拉斯算子的特征向量就是傅里叶变换的频域基向量。见下图。因此，进行傅里叶变换的基向量就可以利用拉普拉斯算子来得到。然而特别要注意的是，拉普拉斯算子是针对一个函数中的各个自变量取值而言，与拓扑图还没有产生联系，也无法用于卷积。06
若我们认为拓扑图中关于每个节点的取值有一个函数，记为f。节点1的取值为f(1)，节点2的取值为f(2)........节点N的取值记为f(N)，那么可以重新在拓扑图上类比地定义一个新的拉普拉斯算子（这里是类比，缺少严格的推导，这也是目前GCN的问题）。下面推导一下这个新的拉普拉斯算子与拉普拉斯矩阵的关系（两者是等效的）。由上面的推导可知， ，而拉普拉斯矩阵的定义，恰恰就是L=D-A，D为度矩阵，A为邻接矩阵。而W可以看作是带权重的邻接矩阵。因此， ，即图中的新定义的拉普拉斯算子与图的拉普拉斯矩阵等价。综上，GCN中对拉普拉斯矩阵的使用，就是对拉普拉斯算子的使用，而且拉普拉斯算子的特征值可以看作是频域空间的基向量。下面再看下拉普拉斯算子或矩阵的使用是否相当于时域到频域的转换。07
首先，对拉普拉斯矩阵L进行特征分解，得到特征向量，并由特征向量构成矩阵U，即 。U的每一列都是L的特征向量，就是频域的基向量e-iwt。那么，根据前述对傅里叶变换的理解，那个积分表达式可以理解为时域的函数f(t)向量与e-iwt向量的内积（投影）。因此，傅里叶变换可以写为又因为在时域空间中的卷积，可以基于傅里叶变换写为如下频域计算的形式（用卷积定理）：卷积定理的证明如下（直接用傅里叶变换的定义和卷积定义代入即可证明）：而图的卷积可以类比地写为如下形式（采用上述图的傅里叶变换）：这种将图的时域卷积转化为频域计算的方法，解决了时域卷积不能处理过大数据的问题，而且在频域上的计算可以更便于设计卷积核。08
在此基础上，就可以通过卷积核+激活函数构成一个图卷积层了，多个图卷积层可以进一步构成图卷积网络，这就是第一代GCN。其缺点十分明显：需要从拉普拉斯矩阵的特征分解来获得U，当N很大时，拉普拉斯矩阵L的维度N*N，特征分解的计算量就很大。同时，矩阵相乘的复杂度也很高O（n^2），最后，没有使用归一化的拉普拉斯矩阵，也就会存在度很大的节点影响过大。后面的二代GCN和三代GCN就是对上述缺点的解决。09
图卷积3 第二代GCN 解决了计算量过大的问题，不用对L特征分解求U了
核心贡献是对待学习的参数 进行了规模的缩减变为了一个关于L的特征值的函数 （其中 即L矩阵的特征值构成的对角阵），且推导出的卷积表达式不再含有U。推导如下：缺点：虽然不用特征分解了，但是矩阵相乘仍然计算量很大，计算L的k次方，复杂度O(kn^2)，且没有使用归一化的拉普拉斯矩阵。要注意的是，超参数K为卷积核的receptive field感受野，也就是节点i周围的K-跳的节点的h会影响到节点i。（暂时没想通）10
图卷积4 第三代GCN 进一步降低计算量，且对拉普拉斯矩阵进行了归一化第三代GCN进一步对待学习的参数 进行了近似，采用的是切比雪夫展开式，具体如下：上述切比雪夫展开式在计算时，要计算K阶的展开。为了进一步简化，第三代GCN又进行了如下的近似简化。上面就推出了第三代GCN的最终卷积表达式。下面再分析一下X的输入维度和期望卷积后输出的维度。
本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。“强基固本”历史文章
更多强基固本专栏文章，
请点击文章底部“阅读原文”查看
分享、点赞、在看，给个三连击呗！