Press "Enter" to skip to content

【图神经网络】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.卷积并不具备局部连接性等缺点做了改进

 

本文的主要有以下贡献:

 

 

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

 

具有局部性的卷积。

 

计算复杂度低。

 

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

 

可复现代码

 

 

三、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

 

 

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

 

具有spatial localization

 

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

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注