论文笔记：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

前言

初代频域GCN简单粗暴的将$diag(\hat{g}{(\lambda_l)})$diag(g^​(λl​))变成了卷积核$diag(\theta_l)$diag(θl​)
由此最终形式为$y_{output}=\sigma(U{g_\theta}(\Lambda)U^Tx)$youtput​=σ(Ugθ​(Λ)UTx)其中

第一代的参数方法存在着一些弊端，主要在于：

1. 每一次的前向传播，存在高维数矩阵的运算，计算代价相对较高
2. 卷积核的定义方式意味着不具有spatial localization
3. 卷积核需要n个参数导致效率降低

为解决这些问题，提出了在卷积核表达形式上进行优化的第二代频域GCN方法：利用Chebyshev多项式作为卷积核
同时此篇文章中所定义的卷积公式严格局部定位，计算复杂度低，滤波器复杂度线性，图池化

1.利用Chebyshev多项式作为卷积核

推导过程
通过上述推导过程我们可以推导出几个结论：

1. 通过切比雪夫多项式的近似拟合卷积核，实现了卷积核维度的下降，降低计算复杂度
2. 通过卷积核的表达形式同时结合图的邻接关系，明显可以看出卷积核的localize特性。因为它是拉普拉斯算子中的$K_{th}$Kth​阶多项式，即它仅取决于离中央节点($K_{th}$Kth​阶邻域)最大$K$K步的节点
3. $T _K(L)x$TK​(L)x的复杂度是$O(|E|)$O(∣E∣)，即与边数E呈线性关系，整个运算的复杂度是$O(K|E|)$O(K∣E∣)。当graph是稀疏图的时候，计算加速尤为明显，这个时候复杂度远低于$O(n^2)$O(n2)

2.图池化

每级粗化我们可以得到一个粗化图$（g0,g1,g2,g3,g4）$（g0,g1,g2,g3,g4），将该粗化图添加上一些辅助节点（蓝色圆），使粗化图中每个顶点都有2个孩子，从而构成一个二叉树，将二叉树摊平构成一维信号，然后对该信号采样即可表示为一次图pooling。这部分作者借助的是之前的工作，这个构建二叉树于与摊平操作是依靠METIS时的粗话图之间的关系。

3.整个GCN过程

4.总结

• 此篇文章最重要的地方就是利用切比雪夫多项式近似拟合卷积核来解决初代频域GCN的一些缺点
• 同时作者原码中利用MNIST数据集作为实验，如何将图片数据转换为图非常重要
• 代码实现流程参考
• 相关数学基础：正定矩阵和半正定矩阵，矩阵特征值和特征向量的意义，实对称矩阵，拉普拉斯矩阵和拉普拉斯算子以及在图上的推广，梯度和散度，拉普拉斯矩阵的特征向量和傅里叶变换的基的关系，傅里叶变换，正交向量组等等。有些列举的非常简单，但这是了解频域GCN原理不可缺少的相关知识