通俗全面理解图卷积与GCN网络(二):从图卷积到GCN

165
0
2020年12月7日 09时30分

目录

 

  • 前言
  • 卷积
  • 傅里叶变换
    • 信号的傅里叶变换
    • 图的傅里叶变换
  • 图卷积
  • GCN(图卷积神经网络)
    • 第一代GCN
    • 第二代GCN
  • 总结

 

前言

 

在上一篇文章中我们介绍了图的部分概念以及最简单的图卷积方式,但这里的图卷积在实现起来还存在着一些问题,在这一篇文章中我们从卷积的定义角度导出图上的卷积,再将它用到GCN里。

 

卷积

 

学过信号处理相关理论的同学一定知道,卷积就是对信号进行如下操作:

 

1607155903(1)

 

当然,这是对连续信号,如果信号是离散的,那么就是这样:

 

1607155942(1)

 

而在图像处理领域,卷积说白了就是把这个公式拓展到了二维嘛:

 

1607155971(1)

 

其中f就是我们说的卷积核,我们假设卷积核大小为M*N,那么可以认为f函数在除了这个范围后的值为0,那么从负无穷到正无穷的求和就可以变成0到M,0到N的求和,这样,上述式子就变成了我们平常看到的通俗理解卷积,如下图:

 

微信图片_20201205161313

 

从信号处理的角度来看,卷积计算这么麻烦,有什么用呢?

 

众所周知,它和傅里叶变换或者拉普拉斯变换有着密切的关系。可以用下面两句绕口令表述:
卷积的傅里叶变换等于傅里叶变换的乘积
乘积的傅里叶变换等于傅里叶变换的卷积

 

写成公式:

 

1607156014(1)

 

正是由于这样的性质,而卷积可以用于还原信号,所以我们用信号傅里叶变换的乘积再做逆变换来计算卷积,从而能做信号处理里的好多事情。

 

按照这样的思路,如果我们能够导出图的傅里叶变换,我们就能导出图卷积的公式。

 

傅里叶变换

 

信号的傅里叶变换

 

上面说了这么多,那什么是傅里叶变换呢,这里简要带大家回忆一下,如果不懂的同学就自行百度了。

 

傅里叶变换与逆变换定义如下:

 

1607156052(1)

 

傅里叶变换为傅里叶级数的拓展,傅里叶级数为求和的形式,只是对于周期信号适用,而当对于任意信号时,可以认为周期趋于无穷,频谱谱线也就无限靠近形成连续谱,求和也变成了积分的形式。

 

同样,离散的傅里叶变换变成求和号即可。

 

从另一个角度看,傅里叶变换可以看做是函数与基函数e-jwt的积分,我们研究一下这个基函数。

 

对其求拉普拉斯,我们可以得到:

 

1607156134(1)

 

按照特征值的定义:

 

对于一种变换A,按照线性代数相关知识,其广义特征方程定义为:

 

1607156224(1)

 

其中V是特征向量,λ是特征值

 

可以看出,e-jwt是拉普拉斯算子的特征函数,而ω与特征值有关。

 

图的傅里叶变换

 

按照上一篇博客里证明过的,图的拉普拉斯矩阵其实就是图的拉普拉斯算子,然后套用上面的关系,我们可以得到:

 

1607156257(1)

 

仿照上面的傅里叶变换的公式,我们可以导出图上傅里叶变换公式:

 

1607156281(1)

 

按照上一篇博客里拉普拉斯矩阵的特征值分解,可以得到矩阵U,其列向量即为特征向量,这里记做ul

 

注意,这里是向量点乘形式,这里的u我们看做复数形式,所以在点乘时,要对u取共轭。

 

上式求得的是节点i的傅里叶变换值。然后我们可以把这个写成矩阵形式:

 

1607156308(1)

 

这样我们就得出了图上的傅里叶变换:

 

1607156340(1)

 

同理,逆变换为:

 

1607156370(1)

 

其他不变,改为对l求和即可。

 

其矩阵形式为:

 

1607156399(1)

 

即:

 

1607156438(1)

 

注:这里我们的定义是类比下来的,将原傅里叶变换的基函数e-jwt类比为特征向量u,因为他们都和特征值有关。实际上,根据线性代数的知识,可以证明这n个特征向量u是线性空间的一组基,而且是正交基。

 

在傅里叶变换中,变换后的函数自变量变为特征值ω,故在这里,变换后的自变量变为特征值λ,如下图:

 

1607156469(1)

 

图卷积

 

根据上面定义,图上的傅里叶变换与逆变换为:

 

1607156502(1)

 

根据傅里叶变换与卷积的关系,为了导出图卷积公式,我们计算图与卷积核的傅里叶变换,将其想乘,再求其逆变换:

 

1607156537(1)

 

带入可得:

 

1607156572(1)

 

其中为哈达马积,即两向量对应元素相乘。

 

这里对于卷积核的傅里叶变换我们可以写为:

 

1607156602(1)

 

故可将别扭的哈达马积去掉,写成:

 

1607156694(1)

 

 

GCN(图卷积神经网络)

 

将图卷积相关理论构成神经网络即图卷积神经网络(Graph Convolutional Network)。
在上一篇博客里我们定义了图卷积层的三种形式,这里我们具体地将我们导出的图卷积公式带入。

 

第一代GCN

 

在第一代GCN中,作者直接将卷积核的傅里叶变换1607156769(1)设定为可学习的卷积核1607156858(1),卷积层就变成了下面这个样子:

 

1607156903(1)

 

其中1607156949(1)即为卷积核

 

其实,同时对于大型图,可能有上亿个节点,这样卷积核就需要学习上亿个参数。

 

第二代GCN

 

为了避免上述的问题,第二代GCN将1607157008(1)设定成1607157072(1),即把傅里叶变换1607157122(1)设置为一个自变量为1607157206(1)的幂级数,最高次为k。那么参数量就变成了k个,即α。

 

而按照之前的推导对于拉普拉斯矩阵有性质:

 

1607157318(1)

 

 

这样就可以有以下化简:

 

1607157370(1)

 

那么图卷积层就表示为:

 

1607157412(1)

 

这个方法太巧妙了,其实就是通过权值共享把要学习的参数量变成幂级数的系数。原来我有几个节点,就得有几个参数,现在我们只需要k个系数就能进行学习。

 

总结

 

这篇文章介绍了图卷积的推导以及GCN网络的构建。在最后,把需要学习的参数降为为k个幂级数的系数。

 

在后来的研究中,研究人员也提出很多种不同的GCN,仅目前pytorch集成的就不下20种了:
pytorch geometric的github:https://github.com/rusty1s/pytorch_geometric

其中改进方法大多为对上述幂级数的改进,可以换成其他函数生成方式,或插值方式。如:贝塞尔曲线、B-样条曲线等。

 

目前,通过B-样条曲线的方法构建的GCN效果很好,该方法来自CVPR2018的论文SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels

 

但也不能说其他的方法效果一定不好,目前这方面还在研究中,这些图卷积的方法效果也基本都差不多,在实际应用中通常要经过多次的尝试找到效果最好的一种。

发表评论

后才能评论