GCN详解

什么是Convolution

Convolution的数学定义是 
GCN详解

一般称g为作用在f上的filter或kernel

一维的卷积示意图如下

GCN详解

大家常见的CNN二维卷积示意图如下

GCN详解

在图像里面卷积的概念很直接,因为像素点的排列顺序有明确的上下左右的位置关系。

GCN详解

比如这个社交网络抽象出来的graph里面,有的社交vip会关联上万的节点,这些节点没有空间上的位置关系,也就没办法通过上面给出的传统卷积公式进行计算。


Fourier变换

为了解决graph上卷积计算的问题,我们给出第二个装备--Fourier变换。

先上结论,根据卷积定理,卷积公式还可以写成

GCN详解

这样我们只需要定义graph上的fourier变换,就可以定义出graph上的convolution变换。

 

GCN详解

好的,先来看下Fourier变换的定义

GCN详解

Inverse Fourier变换则是

GCN详解

 

根据Fourier变换及其逆变换的定义,下面我们来证明一下卷积定理

我们定义 GCN详解 是 GCN详解 和 GCN详解 的卷积,那么

GCN详解

GCN详解

带入 GCN详解 ; GCN详解

GCN详解

最后对等式的两边同时作用 GCN详解 ,得到

GCN详解


Laplacian算子

GCN详解

一波未平,又来一个陌生的概念。。。

不要担心,这是出新手村之前的最后一件装备了。

一阶导数定义为

GCN详解

laplacian算子简单的来说就是二阶导数

GCN详解

 

那在graph上,我们可以定义一阶导数为

GCN详解

其中y是x的邻居节点

那么对应的Laplacian算子可以定义为
GCN详解

定义 GCN详解 是GCN详解 的度数矩阵(degree matrix)

GCN详解

定义 GCN详解 为GCN详解 邻接矩阵(adjacency matrix)

GCN详解

那么图上的Laplacian算子可以写成

GCN详解

标准化之后得到 GCN详解

GCN详解

定义Laplacian算子的目的是为了找到Fourier变换的基

比如传统Fourier变换的基 GCN详解 就是Laplacian算法的一组特征向量

GCN详解 , GCN详解 是一个常数

那么图上的Fourier基就是 GCN详解 矩阵的n个特征向量 GCN详解 , GCN详解 可以分解为

GCN详解

其中 GCN详解 是特征值组成的对角矩阵

 

GCN详解

 

那么Graph Fourier变换可以定义为

GCN详解

其中 GCN详解 可以看做是作用在第 GCN详解 个点上的signal,用向量 GCN详解 来表示

GCN详解 是 GCN详解 的的对偶向量, GCN详解 是矩阵 GCN详解 的第 GCN详解 行,GCN详解 是矩阵 GCN详解 的第 GCN详解 行。

那么我们可以用矩阵形式来表示Graph Fourier变换

GCN详解

类似的Inverse Graph Fourier变换定义为

GCN详解

它的矩阵形式表达为

GCN详解


推导Graph Convolution

走到这里,我们已经获得了新手村的所有装备,下面就开始推导GCN的公式。

还记得我们之前提到的先上卷积定理吗

GCN详解

那么图的卷积公式可以表示为

GCN详解

作为图卷积的filter函数 GCN详解 ,我们希望具有很好的局部性。就像CNN模型里的filter一样,只影响到一个像素附近的像素。那么我们可以把 GCN详解 定义成一个laplacian矩阵的函数 GCN详解

GCN详解

作用一次laplacian矩阵相当于在图上传播了一次邻居节点。进一步我们可以把 GCN详解 看做是 GCN详解 一个laplacian特征值的函数,参数为 GCN详解

改写上面的图卷积公式,我们就可以得到论文SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

https://arxiv.org/pdf/1609.02907.pdf​arxiv.org

的公式(3)

GCN详解

可以看到这个卷积计算的复杂度是非常高的,涉及到求laplacian矩阵的特征向量,和大量的矩阵计算。下面我们考虑对filter函数做近似,目标是省去特征向量的求解

GCN详解

其中 GCN详解 是Chebyshev多项式。这里可以把简单 GCN详解 简单看成是 GCN详解 的多项式。

因为 GCN详解

所以上面filter函数可以写成 GCN详解 的函数 GCN详解

设定 GCN详解那卷积公式可以简化为

GCN详解

令 GCN详解 , GCN详解

GCN详解

那么再加上激活层,我们就可以得到最终的GCN公式

GCN详解

 

 

源自知乎:https://zhuanlan.zhihu.com/p/54505069

上一篇:Fourier serie


下一篇:【转载】别怕,"卷积"其实很简单