Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

时间:2022-08-30 21:16:03

Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in Neural Information Processing Systems. 2016.

摘要:

作者提出了一种把传统CNN扩展到非欧空间上的一种卷积网络

1.介绍

作者的主要贡献有:

(1)谱方法的形式化。一种基于谱方法的CNN的形式化表述,基于GSP(Shuman, David I., et al. "The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains." IEEE Signal Processing Magazine 30.3 (2013): 83-98.)

(2)严格的局部化的filters。作者扩展了(Bruna, Joan, et al. "Spectral networks and locally connected networks on graphs." arXiv preprint arXiv:1312.6203 (2013).d)的工作。局部化就是定义了一个参数K,K代表以一个节点为中心的K次跳跃(也就是距离为K)。

(3)小的计算复杂度。复杂度是和K以及边数成正比。因为大部分现实生活中的图是高度稀疏的,那么就是边数远远低于点数的平方,即 边 = k*点数。k可以看做是一个点的k最近邻。这也就是说复杂度是和输入数据的大小。另外,这个方法避免计算傅里叶因子(需要计算和储存傅里叶因子)。这个方法只用储存一个拉普拉斯矩阵,这是一个稀疏矩阵,只有边数个非零值。

(4)高效的pooling。通过构建一个二叉树进行pooling。

(5)实验结果。作者在MNIST上做了实验,取得了和传统CNN相当的实验结果。tensorflow code:https://github.com/mdeff/cnn_graph

2.技术细节

实现图上的CNN需要满足一下一点要求:(1)设计卷积核(2)相似点聚集(3)pooling操作

2.1 学习局部化谱filters

图的傅里叶变换:首先定义拉普拉斯矩阵:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

其中D是度矩阵,W是邻接矩阵,Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

如果对拉欧拉斯矩阵做归一化,则表示为:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

然后对L做特征值分解,得到:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

U是特征向量组成的矩阵,A是特征值组成的对角矩阵。

那么图上的傅里叶变换为:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

其中x是整个图组成的特征,n为图上的节点数。

图上的卷积操作定义为:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

那么对x做卷积操作即为:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

其中Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

多项式近似实现局部化:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

快速过滤的递归推导:主要是利用了切比雪夫多项式的递推关系

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

学习过滤器:通过梯度下降即可完成:

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

2.2 图粗化

主要是用了(Dhillon, Inderjit S., Yuqiang Guan, and Brian Kulis. "Weighted graph cuts without eigenvectors a multilevel approach." IEEE transactions on pattern analysis and machine intelligence 29.11 (2007).)的方法

2.3 快速pooling

作者通过上述方法得到更粗糙的图,然后对节点重排序,然后构建一个二叉树。

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

相关论文:

Semi-Supervised Classification with Graph Convolutional Networks

Geometric deep learning on graphs and manifolds using mixture model CNNs

GRAPH ATTENTION NETWORKS