图卷积神经网络系列：6. | 谱域回顾 & 空域图卷积模型GNN
一 . 谱域图卷积回顾
虽然我知道上一节中已经回顾了一遍了，但是我就是还有再回顾一遍。
Point 1 ：在谱域卷积中，我们的基本思路是，先将空域输入信号和空域空域卷积核转换到谱域，然后在谱域中相乘，再通过傅里叶反变换转换回空域：
f_1(t) ★ f_2(t) = \mathcal{F}^{-1}[F_1(w) \cdot F_2(w)] \\
其中， \mathcal{F} 为傅里叶变换。
Point 2 ：图结构中信号的空域和谱域的转换是由图傅里叶变换实现的：其中，拉普拉斯特征向量作为经典傅里叶变换中的基函数，拉普拉斯矩阵的特征值作为经典傅里叶变量中的“频率”。
Point 3 ：介绍了三个经典的谱域图卷积模型。
★ SCNN：用可学习的对角矩阵来代替谱域的卷积核：
x ★ _Gg_\theta = UFU^\top x \\
★ChebNet：用切比雪夫多项式代替谱域的卷积核：
x ★_Gg_\theta =Ug_\theta U^\top x = \sum_{k=0}^K \beta_kT_k(\hat L)x \\
★ GCN：进一步对ChebNet进行简化，仅考虑一阶切比雪夫不等式，且每个卷积核只有一个参数。
x ★_Gg_\theta = \theta(\tilde{D}^{-1/2}\tilde{W}\tilde{D}^{-1/2})x \\
二 . 谱域图卷积的缺陷
1 . 谱域图卷积不适用于有向图。
- 首先，由于谱域图卷积是严格基于卷积定理和图傅里叶变换的，而图傅里叶变换的应用是有限制的，仅能够在无向图中应用。
- 其次，谱域图卷积的第一步是将空域信号转换到谱域，当图傅里叶变换无法使用时，谱域图卷积也就无法再进行计算了。
- 最后，在大量应用场景中，是有向图场景，也就是 W_{ij} \ne W_{ji} 。因此谱域图卷积此时无法使用。
2 . 谱域图卷积假定图结构是固定的。
x ★ _Gg = \mathcal{F}^{-1}(\mathcal{F}(x) \odot \mathcal{F}(g)) = U(U^\top x \odot U^\top g ) \\
也就是说，上式中的U必须是预先已知的且固定不变的。
在训练期间，图结构不能变化，也就是说不能改变节点之间的权重，不能增删节点。如果是图像识别领域则没有什么问题，但是某些领域，图结构可能会变化，如推荐系统，社交网络，交通数据等。例如在推荐系统中，新的用户和新的物品的加入，或是用户偏好发生短期改变，势必会造成节点的增删和权重的变化。
3 . 谱域图卷积模型的复杂度问题。
- SCNN需要进行拉普拉斯矩阵的谱分解，计算耗时，复杂度高， 为 O(n^3) 。
- 虽然ChebNet和GCN对SCNN进行了改进，不需要对拉普拉斯矩阵进行谱分解了，但是由于其可学习的参数过于简化（GCN中每一个卷积核只有一个可学习的参数），降低模型复杂度的同时，也一定程度上限制了模型性能。
基于谱域图卷积存在的问题，那么，能否绕过图谱理论，重新定义图上的卷积呢？
既然你诚心诚意的发问了，那我就大发慈悲的告诉你：是可以的！
现有的图卷积方法大致可以分为两类：谱域图卷积方法和空域图卷积方法：
- 谱域图卷积：根据图谱理论和卷积定理，将数据由空域转换到谱域做处理。理论基础扎实。
- 空域图卷积：不依靠图谱卷积理论，直接在空间上定义卷积操作。灵活性很强。
三 . 空域图卷积模型： GNN
PAPER：Hechtlinger Y, Chakravarti P, Qin J, et al. A Generalization of Convolutional Neural Networks to Graph-Structured Data.[J]. arXiv: Machine Learning, 2017
经典的卷积操作是如何定义的呢？
即固定数量邻域节点排序后，与相同数量的卷积核参数相乘求和。
传统卷积有着固定的邻域大小（如3x3卷积核为八邻域），同时有着固定的顺序，也就是从左上角到右下角。
因此，卷积的操作可以拆分为如下两步：
Step1：构建邻域。
- 找到固定数量的邻居节点。
- 对找到的邻居节点进行排序。
Step2：对邻域的点与卷积核参数做内积。
要想将经典卷积操作应用到图结构上，有如下两个问题：
- 对于图结构数据来说，不存在固定的邻域结构，每一个节点的邻域大小是不同的且变化的。
- 同一邻域内的节点不存在顺序性。
因此，GNN中所提出的解决思路为：
- 1 . 使用随机游走的方法，根据被选中的概率期望大小选择固定数量的邻居节点。
- 2 . 然后根据节点被选择的概率期望来对邻域进行排序。
符号定义
P 为图上的随机游走转移矩阵，其中， P_{ij} 表示节点 i 到节点 j 的转移概率。
S 为相似度矩阵。该矩阵的定义和作用与邻接矩阵类似。
D 为度矩阵， D_{ii} = \sum_{j}S_{ij} 。
具体的步骤如下：
第一步：GNN假设存在图结构是已知的，那么 相似度矩阵S 和度矩阵 D 也就是已知的。随机游走概率转移矩阵 P 定义如下： P= D^{-1}S \\
第二步：使用归一化的邻接矩阵来作为转移矩阵。
第三步：定义多步的转移期望：
Q^{(0)} = I \\ Q^{(1)} = I +P\\ ...\\ Q^{(k)} = \sum_{i=0}^{k} P^k
其中， Q_{ij} ^{(k)} 表示为 k 步内，由节点 i 出发到节点 j 的期望访问数。
第四步：根据期望大小来选择邻域：
\pi_i^{(k)}(c) 表示节点的序号。该节点为（k步内）由节点 i 出发的访问期望数第 c 大的节点。那么有： Q_{i \pi_i^{(k)}{(1)}}>Q_{i \pi_i^{(k)}{(2)}}>...>Q_{i \pi_i^{(k)}{(N)}} 。
第五步：做1D卷积：
在非欧空间中，数据有两个特点：序列无序性和维数可变性。而在欧式空间中的规则数据的特点为：序列有序性和维数一致性。
如果能够从非欧空间的图结构数据中找到固定数量的邻居节点，然后对找到的邻居节点进行排序，那么得到的数据就和欧式空间中的有序和规则数据类似了。
本质上，GNN的做法是强制将一个图结构数据变化为了一个类似规则的数据，从而可以被1D卷积所处理。
