GCN
参考链接：
如何理解 Graph Convolutional Network（GCN）？ - 知乎 (zhihu.com)
1.什么是离散卷积？CNN中卷积发挥什么作用？
f,g的卷积$f*g(n)$：
- 连续形式：$(f*g)(n)=\int_{-\infty}^{\infty}f(\tau)g(n-\tau)d\tau$
- 离散形式：$(f*g)(n)=\sum_{\tau=-\infty}^{\infty}f(\tau)g(n-\tau)$
“卷”：先对g函数进行翻转，相当于在坐标系中把g函数从右边折到左边去。
“积”：把g函数平移n个单位长度，在该位置将两个函数的对应点相乘然后相加。
所谓两个函数的卷积，本质上就是先将一个函数翻转，然后进行滑动叠加。
考虑以下案例：
例1：信号分析
如下图所示，输入信号是 f(t) ，是随时间变化的。系统响应函数是 g(t) ，图中的响应函数是随时间指数下降的，它的物理意义是说：如果在 t=0 的时刻有一个输入，那么随着时间的流逝，这个输入将不断衰减。换言之，到了 t=T时刻，原来在 t=0 时刻的输入f(0)的值将衰减为f(0)g(T)。
考虑到信号是连续输入的，也就是说，每个时刻都有新的信号进来，所以，最终输出的是所有之前输入信号的累积效果。如下图所示，在T=10时刻，输出结果跟图中带标记的区域整体有关。其中，f(10)因为是刚输入的，所以其输出结果应该是f(10)g(0)，而时刻t=9的输入f(9)，只经过了1个时间单位的衰减，所以产生的输出应该是 f(9)g(1)，如此类推，即图中虚线所描述的关系。这些对应点相乘然后累加，就是T=10时刻的输出信号值，这个结果也是f和g两个函数在T=10时刻的卷积值。
显然，上面的对应关系看上去比较难看，是拧着的，所以，我们把g函数对折一下，变成了g(-t)，这样就好看一些了。看到了吗？这就是为什么卷积要“卷”，要翻转的原因，这是从它的物理意义中给出的。
上图虽然没有拧着，已经顺过来了，但看上去还有点错位，所以再进一步平移T个单位，就是下图。它就是本文开始给出的卷积定义的一种图形的表述：
例2：丢骰子
要解决的问题是：有两枚骰子，把它们都抛出去，两枚骰子点数加起来为4的概率是多少?
分析一下，两枚骰子点数加起来为4的情况有三种情况：1+3=4， 2+2=4, 3+1=4
因此，两枚骰子点数加起来为4的概率为：
写成卷积的方式就是：
$$
(f*g)(4)=\sum_{m=1}^{3}f(4-m)g(m)
$$
在此进一步使用翻转滑动叠加的逻辑进行解释。
首先，因为两个骰子的点数和是4，为了满足这个约束条件，我们还是把函数 g 翻转一下，然后阴影区域上下对应的数相乘，然后累加，相当于求自变量为4的卷积值，如下图所示：
进一步，如此翻转以后，可以方便地进行推广去求两个骰子点数和为 n 时的概率，为f 和 g的卷积 f\g(n)*，如下图所示：
由上图可以看到，函数 g 的滑动，带来的是点数和的增大。这个例子中对f和g的约束条件就是点数和，它也是卷积函数的自变量。
例3：图像处理
图像可以表示为矩阵形式。
对图像的处理函数（如平滑，或者边缘提取），也可以用一个g矩阵来表示，如：
$$
\begin{bmatrix}
b_{-1,-1} & b_{-1,0} & b_{-1,1}\\
b_{0,-1} & b_{0,0} & b_{0,1} \\
b_{1,-1} & b_{1,0} & b_{1,1}
\end{bmatrix}
$$
注意，我们在处理平面空间的问题，已经是二维函数了，相当于：
$f(x,y)=a_{x,y}$
$g(x,y)=b_{x,y}$
那么函数f和g在（u,v）处的卷积$f*g(u,v)$该如何计算呢？
按卷积的定义，二维离散形式的卷积公式应该是：
$$
(f*g)(u,v)=\sum_{i}\sum_{j}f(i,j)g(u-i,v-j)=\sum_i\sum_ja_{i,j}b_{u-i,v-j}
$$
从卷积定义来看，应该是在x和y两个方向去累加（对应上面离散公式中的i和j两个下标），而且是无界的，从负无穷到正无穷。可是，真实世界都是有界的。例如，上面列举的图像处理函数g实际上是个3x3的矩阵，意味着，在除了原点附近以外，其它所有点的取值都为0。考虑到这个因素，上面的公式其实退化了，它只把坐标（u,v）附近的点（满足u-i和v-j在[-1,1]之间）选择出来做计算了。所以，真正的计算如下所示：
首先我们在原始图像矩阵中取出（u,v）处的矩阵：
$$
f=
\begin{bmatrix}
a_{u-1,v-1} & a_{u-1,v} & a_{u-1,v+1}\\
a_{u,v-1} & a_{u,v} & a_{u,v+1}\\
a_{u+1,v-1} & a{u+1,v} & a{u+1,v+1}
\end{bmatrix}
$$
然后将图像处理矩阵翻转（先x后y或先y后x），如下：
原始矩阵：
翻转后矩阵：
$$
g’=
\begin{bmatrix}
b_{1,1} & b_{1,0} & b_{1,-1}\\
b_{0,1} & b_{0,0} & b_{0,-1}\\
b_{-1,1} & b_{-1,0} & b_{-1,-1}
\end{bmatrix}
$$
计算卷积时，就可以用f和g’的内积：
以上公式有一个特点，做乘法的两个对应变量a,b的下标之和都是（u,v），其目的是对这种加权求和进行一种约束。这也是为什么要将矩阵g进行翻转的原因。
以上计算的是（u,v）处的卷积，沿x轴或者y轴滑动，就可以求出图像中各个位置的卷积，其输出结果是处理以后的图像（即经过平滑、边缘提取等各种处理的图像）。
再深入思考一下，在算图像卷积的时候，我们是直接在原始图像矩阵中取了（u,v）处的矩阵，为什么要取这个位置的矩阵，本质上其实是为了满足以上的约束。因为我们要算（u,v）处的卷积，而g矩阵是3x3的矩阵，要满足下标跟这个3x3矩阵的和是（u,v），只能是取原始图像中以（u,v）为中心的这个3x3矩阵，即图中的阴影区域的矩阵。
推而广之，如果如果g矩阵不是3x3，而是7x7，那我们就要在原始图像中取以（u,v）为中心的7x7矩阵进行计算。由此可见，这种卷积就是把原始图像中的相邻像素都考虑进来，进行混合。相邻的区域范围取决于g矩阵的维度，维度越大，涉及的周边像素越多。而矩阵的设计，则决定了这种混合输出的图像跟原始图像比，究竟是模糊了，还是更锐利了。
比如说，如下图像处理矩阵将使得图像变得更为平滑，显得更模糊，因为它联合周边像素进行了平均处理：
$$
g=
\begin{bmatrix}
1/9 & 1/9 &1/9\\
1/9&1/9&1/9\\
1/9&1/9&1/9
\end{bmatrix}
$$
而如下图像处理矩阵将使得像素值变化明显的地方更为明显，强化边缘，而变化平缓的地方没有影响，达到提取边缘的目的：
$$
g=
\begin{bmatrix}
-1&-1&-1\\
-1&9&-1\\
-1&-1&-1
\end{bmatrix}
$$
以上内容解释了离散卷积的本质，即一种加权求和。
如图1所示，CNN中的卷积本质上就是利用一个共享参数的过滤器，通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取，加权系数就是卷积核的权重系数。
卷积核系数的确定方法是随机化初值，然后根据误差函数通过反向传播梯度下降进行迭代优化。卷积核的参数通过优化求出才能实现特征提取的作用，GCN的理论很大一部分工作就是为了引入可以优化的卷积参数。
注意：此处的卷积是指深度学习中的卷积，与数学中卷积的概念有所不同。（深度学习中的卷积不需要翻转，只是“加权求和”）
2.GCN中的Graph指什么？为什么要研究GCN？
CNN处理的图像或者视频中像素点（pixel）是排列很整齐的矩阵（如下图，一般称作Euclidean Structure）。
与之相对应，科学研究中还有很多Non Euclidean Structure的数据，如下图。这类数据在社交网络、信息网络中非常常见。
这样的网络结构也就是GNN中的Graph，即数学（图论）中用顶点和边建立相应关系的拓扑图。
研究GCN的原因有三：
- CNN无法直接处理Non Euclidean Structure的数据。因为拓扑图中每个顶点的相邻顶点数目都可能不同，固然不能用一个同样尺寸的卷积核来进行卷积运算。
- 对于Non Euclidean这样的数据结构也有有效提取空间特征以进行机器学习的要求。
- GCN的研究并不仅仅局限于拓扑图。广义上来讲任何数据在赋范空间内都可以建立拓扑关联，谱聚类就是应用了这样的思想。所以说拓扑连接是一种广义的数据结构，GCN有很大的应用空间。
综上，GCN是要为CV、NLP之外的任务提供一种处理、研究的模型。
3.提取拓扑图空间特征的两种方式
GCN本质是提取拓扑图的空间特征，实现这个目标有基于vertex domain（spatial dimain）和基于spectral domain两种方式。
3.1空间维度
Vertex domain是一种非常直观的方式。即需要提取图谱图上的空间特征，那就把每个顶点的邻居找出来即可。
这里需要考虑两个问题：
- 按照什么条件去找中心顶点的邻居，即如何确定可接受域？
- 确定可接受域后，按照什么方式处理包含不同数目邻居的特征？
围绕着以上两个问题设计算法，就可以实现目标，一种实现思路可以参考Learning Convolutional Neural Networks for Graphs (mlr.press)，下图是其大致思路：
该方法主要有以下两个缺点：
- 每个顶点提取出来的邻居不同，计算必须针对每个顶点特质化
- 提取特征的效果可能没有卷积好
3.2图谱维度
Spectral domain就是GCN的理论基础。大致思路是借助图谱的理论来实现拓扑图上的卷积操作。
由于从空间维度分析问题，需要逐节点地处理，而图结构是非欧式的连接关系，这在很多场景下会有明显的局限性。图谱维度则是将问题转换在“频域”里分析，不再需要逐节点处理，对于很多场景能带来意想不到的便利，也称为了GSP（Graph Signal Processing）的基础。
至于分析的具体方法，简单来说就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质。
4.什么是拉普拉斯矩阵？为什么GCN要用拉普拉斯矩阵？
拉普拉斯矩阵定义：对于图$G=(V,E)$，其拉普拉斯矩阵定义为$L=D-A$，其中L是拉普拉斯矩阵，D是顶点的度矩阵（对角矩阵），对角线上元素依次为各个顶点的度，A是图的邻接矩阵。下图展示的是一个拉普拉斯矩阵计算的实例：
常用的拉普拉斯矩阵实际有三种：
- $L=D-A$，定义的是Combinatorial Laplacian（组合拉普拉斯矩阵）
- $L^{sys}=D^{-1/2}LD^{-1/2}$定义的叫Symmetric normalized Laplacian（对称归一化拉普拉斯矩阵），很多GCN论文中应用的是这种拉普拉斯矩阵）
- $L^{rw}=D^{-1}L$定义的叫Random walk normalized Laplacian（随机游走归一化拉普拉斯矩阵）。该定义可以体现出Graph Convolution和Diffusion的相似之处，其实两者只差一个相似矩阵的变换）。
为什么GCN要用拉普拉斯矩阵？以下是三点原因：
- 拉普拉斯矩阵是对称矩阵，可以进行特征分解，和GCN的spectral domain相对应
- 拉普拉斯矩阵只在中心顶点和一阶相连的顶点上有非0元素，其余之处均为0
- 通过拉普拉斯算子与拉普拉斯矩阵进行类比
5.拉普拉斯矩阵的谱分解（特征分解）
矩阵的谱分解、特征分解、对角化是同一个概念。
不是所有矩阵都可以特征分解，充要条件为：n阶方阵存在n个线性无关的特征向量。
但拉普拉斯矩阵是半正定对称矩阵，有如下性质：
- 实对称矩阵一定有n个线性无关的特征向量
- 半正定矩阵的特征值一定非负
- 实对称矩阵的特征向量总是可以化成两两相互正交的正交矩阵
由以上性质可知，拉普拉斯矩阵一定可以谱分解，且分解后有特殊形式。
对于拉普拉斯矩阵，其谱分解为：
$$
L=U
\begin{pmatrix}
\lambda_1 & \\
& \ddots \\
&&\lambda_n
\end{pmatrix}
U^{-1}
$$
其中$U=(\vec{u_1},\vec{u_2},\cdots,\vec{u_n})$，是列向量为单位特征向量的矩阵，即**$\vec{u_l}$是列向量**。中间的矩阵是n个特征值构成的对角阵。
由于U是正交矩阵，即$UU^T=E$，E是单位矩阵。所以特征分解又可写成：
$$
L=U\begin{pmatrix}\lambda_1 & \\& \ddots \\&&\lambda_n\end{pmatrix}U^T
$$
6.如何从传统的傅里叶变换、卷积类比到图上的傅里叶变换和卷积？
把传统的傅里叶变换以及卷积迁移到图上来，核心工作 其实就是把拉普拉斯算子的特征函数$e^{-iwt}$变为图对应的拉普拉斯矩阵的特征向量。
具体推广方式不做过多阐述，详情请见本文的参考链接。
7.GCN
7.1主要思想
对于每个节点，考虑其所有邻居以及其自身所包含的特征信息。假设我们使用average函数，那对每个节点进行上述操作后，就可以得到能够输入到神经网络的平均值表示。
上图是一个简单的引用网络。每个节点代表一篇文章，边代表引用情况。首先进行预处理，将论文的原始文本通过NLP嵌入的方法转化为向量。接下来考虑绿色节点，首先得到包括自身在内的所有节点的特征值，然后取平均，将该平均值向量输入到一个神经网络中，再得到一个向量。
上面的例子使用平均值函数，但在实际应用中我们可以采用更复杂的聚合函数，GCN神经网络的结构也可以比上面图中的网络结构更复杂。如下图就是一个两层全连接GCN的例子，每一层作为下一层的输入。
7.2网络层数
网络层数代表着节点特征所能到达的最远距离。比如一层GCN，每个节点只能得到其一阶邻居身上的信息。对于所有节点来说，信息的获取过程是独立、同时展开的。当增加网络的层数时，就可以使节点的信息传递下去，但是我们通常不会需要节点的信息传播地太远，经过6~7个hops基本就可以使节点信息传播到整个网络。
一般我们使用2~3层GCN效果较好，到第7层时效果已经变得较差，但是加上residual connections between hidden layers可以使效果变好。