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

阿泽 Crz

发布于 2021-04-29 16:47:19

8590

发布于 2021-04-29 16:47:19

文章被收录于专栏：阿泽的学习笔记

一、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.卷积并不具备局部连接性等缺点做了改进

本文的主要有以下贡献：

谱公式。基于图信号处理的谱图理论公式
具有局部性的卷积。
计算复杂度低。
高效的共享。提出了一种有效的图上的池策略。
可复现代码

三、Model

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

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

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

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

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

3.1 ChbeyNet

图信号的谱滤波：

g_\theta(\Lambda)

的learning复杂度为

O(n)

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

g_{\theta}(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} \Lambda^{k}

其中参数

θ∈R^K

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

但是有了局部性后，将时间复杂度降低到了

O(K)

后，

Ug_\theta (\Lambda)U^Tx

的复杂度还是

O(n^2)

，然后就到切比雪夫上场了：

g_{\theta}(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} T_{k}(\tilde{\Lambda})

\tilde{\Lambda}=2\Lambda / \lambda_{max}-I_N

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

\lambda_{max}

为L的最大特征值

T_{k}(\tilde{\Lambda})x

的复杂度为

O(|E|)

关于K阶局部性的解释

下图可直观理解～

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

3.2 推导过程

切比雪夫多项式

\begin{array}{l} T_{0}(x)=1 \\ T_{1}(x)=x \\ T_{n+1}(x)=2 x T_{n}(x)-T_{n-1}(x) \end{array}

谱图卷积

y=g_{\theta}(L) x=g_{\theta}\left(U \Lambda U^{T}\right) x=U g_{\theta}(\Lambda) U^{T} x

本身提出的卷积核

g_{\theta}(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} T_{k}(\tilde{\Lambda})

从谱图卷积开始：

\begin{aligned} g_{\theta} * x &=U g_{\theta} U^{T} x \\ &=U g_{\theta}(\Lambda) U^{T} x \\ &=U\left(\sum_{k=0}^{K} \theta_{k} T_{K}(\tilde{\Lambda})\right) U^{T} x \\ &=\left(\sum_{k=0}^{K} \theta_{k} T_{K}\left(U \tilde{\Lambda} U^{T}\right)\right) x \\ &=\sum_{k=0}^{K} \theta_{k} T_{K}(\tilde{L}) x \end{aligned}

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

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

\begin{array}{l} U T_{0}(\bar{\Lambda}) U^{T}=U U^{T}=1=T_{0}\left(U \bar{\Lambda} U^{T}\right) \\ U T_{1}(\tilde{\Lambda}) U^{T}=U \tilde{\Lambda} U^{T}=T_{1}\left(U \tilde{\Lambda} U^{T}\right) \end{array}

\begin{aligned} U T_{k}(\bar{\Lambda}) U^{T} &=2 U \bar{\Lambda} T_{k-1}(\bar{\Lambda}) U^{T}-U T_{k-2}(\bar{\Lambda}) U^{T} \\ &=2\left(U \tilde{\Lambda} U^{T}\right)\left[U T_{k-1}(\tilde{\Lambda}) U^{T}\right]-U T_{k-2}(\tilde{\Lambda}) U^{T} \\ &=2\left(U \tilde{\Lambda} U^{T}\right) T_{k-1}\left(U \tilde{\Lambda} U^{T}\right)-T_{k-2}\left(U \tilde{\Lambda} U^{T}\right) \\ &=T_{k}\left(U \tilde{\Lambda} U^{T}\right) \end{aligned}

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 数值实验

FCk

标记着K个hidden units的全连接层，

标记一个stride k的 pooling layer of size，

GCk

和

标记着带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图，该图产生了一个

n=| V |=976

个节点（

28^2=784

个像素和192个伪节点）和| E |=3198个边的图。k-NN相似图（特征之间）的权重计算如下：

W_{i j}=\exp \left(-\frac{\left\|z_{i}-z_{j}\right\|_{2}^{2}}{\sigma^{2}}\right)

其中

是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