【图神经网络】GCN-2（ChebyNet）

一、Address

发表于NIPS 2016的一篇论文：

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

地址：https://arxiv.org/pdf/1606.09375.pdf

二、Introduction

本文对第一代GCN（《Spectral Networks and Deep Locally Connected Networks on Graphs》）存在的1.计算复杂度高，2.卷积并不具备局部连接性等缺点做了改进

本文的主要有以下贡献：

1. 谱公式。基于图信号处理的谱图理论公式

2. 具有局部性的卷积。

3. 计算复杂度低。

4. 高效的共享。提出了一种有效的图上的池策略。

5. 可复现代码

三、Model

以下内容对入门者需要一些前置知识，可以去阅读一下本号图神经网络前面的内容。

将CNNs推广到图需要三个基本步骤：

（i）设计图的局部卷积滤波器；

（ii）将相似的顶点和顶点组合在一起的图粗化过程

（iii）一种图形池操作，用空间分辨率换取更高的滤波器分辨率（filter resolution）

3.1 ChbeyNet

图信号的谱滤波：

的learning复杂度为，并且不具备局部性，于是可以改用多项式滤波器来解决这个问题：

其中参数是切比雪夫多项式系数的向量。以上公式是怎样表示K阶局部性呢？

但是有了局部性后，将时间复杂度降低到了后，的复杂度还是，然后就到切比雪夫上场了：

• ，这是对特征向量矩阵进行缩放，缩放后范围为[-1，1]，目的是为了满足切比雪夫多项式的定义域为[-1,1]
• 为L的最大特征值
• 的复杂度为

关于K阶局部性的解释

下图可直观理解～

感谢来自知乎用户 superbrother 回答分享的图 （https://www.zhihu.com/question/54504471/answer/332657604）

3.2 推导过程

切比雪夫多项式

谱图卷积

本身提出的卷积核

从谱图卷积开始：

其中第二行到第三行的证明如下：

需要使用数学归纳法来证明，首先证明n=1时有

3.3 图粗化

本文是用了 Dhillon I S , Guan Y , Kulis B . Weighted Graph Cuts without Eigenvectors A Multilevel Approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(11):1944-1957.

的方法，此处不展开讲了，有兴趣的朋友可以去详看。

3.4 图池化

图粗化后，将该粗化图添加fake节点使得粗化图中每个顶点都有2个children，构成一个二叉树，将二叉树摊平构成一维信号（上图右部分下），然后对该信号采样即可表示为一次图pooling。

整体架构

四、Experiments

4.1 数值实验

标记着K个hidden units的全连接层，标记一个stride k的 pooling layer of size，和标记着带k特征map的graph卷积layer，所有的FCk，Ck，GCk后面都跟着一个ReLU激活函数max(x,0)，最后一个layer是softmax regression，损失能量E是带L2正则化的FCk layers之间的cross-entropy。Mini-batches设置成S=100。

MNIST数据集实验

为了验证我们的模型，我们将其应用于基准MNIST数据集中，该问题是一个由70000位数字组成的数据集，表示在一个28×28的二维网格上。对于我们的图模型，我们构造了一个二维网格的8-NN图，该图产生了一个个节点（个像素和192个伪节点）和| E |=3198个边的图。k-NN相似图（特征之间）的权重计算如下：

其中 是pixel i的2D坐标。

Table 1展示了我们在MNIST上与CNN有类似的效果。

表现差了一点，可以用spectral filters的各向同性来解释，一般图中的边不具有方向（如2D网格上的像素的上、下、右和左）

Text Categorization on 20NEWS

为了证明在非结构化数据上模型的能力，我们在包含18846个text document【11314训练，7532测试】，20个类别的20NEWS数据集上，我们在93953个不同的words中抽出了10000个最常用的词汇，每个document x使用 bag-of-words 模型来表示，在词汇之间正交化，为了测试模型，构造了16-NN 的graph，有10000个nodes，132834个edges，使用Adam优化器训练20epochs，学习率初始化为0.001，K=5的GC32

图片质量的影响

五、Conclusion

1. 卷积核的参数量为K，K远小于N，相比第一代GCN减少了复杂度

2. 具有spatial localization

3. 证明了图的质量对性能的影响