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

165
0
2020年12月6日 09时10分

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

目录

    • 前言
      • 一般表示
      • 度、邻接、拉普拉斯
      • 为什么拉普拉斯
      • 拉普拉斯矩阵的特征值分解
    • 图卷积通式
    • 总结

前言

相信大家都了解普通卷积操作,在一般的论文里,习惯认为普通的卷积是操作在Euclidean Structure,即欧几里得空间上的。直观的来看,一般卷积操作的图片是非常整齐的矩阵,一个像素周围必定有上下左右以及斜对角八个像素包围,这样的卷积好操作,卷积核大小也固定,再加之权值共享,有效的提取空间特征同时减少参数,使得CNN成为深度学习图像处理界当之无愧的扛把子。

但人们逐渐认识到,并非所有的数据都是这样规则的。 反而可以说,自然界中大多数的数据都是不规则的。也就是数据之间相互影响,构成了数据结构里图的形状。即使普通我们规则的图像,我们在逐像素处理中可能计算了很多对我们任务来说无用的像素点。而如果我们提取关键点,这些点之间也会构成一幅图。这里的图指图论里的图,而非我们平常见的图片。

CNN理论已经非常完整,但是遇到这种不规则的图结构,我们又该如何提取它的空间特征呢?这就应该从CNN的本质说起,去模仿它,把它扩展到所谓的非欧几里得空间里,这就是我们所说的“图卷积”。

一般表示

 

1

 

度、邻接、拉普拉斯

我们先来介绍一下图论里面的相关概念(会的同学直接跳过)
相信大家在查资料时下面这幅图也见过不下十次了,我们这里也用这幅图来说明:

 

2

 

可见,最左面画出了一个拥有6个节点,7条边的无向图,右面分别是该图所对应的度矩阵、邻接矩阵和一种拉普拉斯矩阵。

 

节点的度: 节点的度定义为该节点上拥有的边数,上面的度矩阵也就是每个节点的度所构成的对角矩阵。
邻接矩阵: 邻接矩阵代表了图的几何结构,在节点联通的地方取值为1,不联通的地方取值为0.也即:A(i,j)=1 if 节点i和j联通 else 0。易知一个无向图的邻接矩阵一定是对称的。
拉普拉斯矩阵: 邻接矩阵只定义了与该节点联通的节点有哪些,而没有该节点自身的信息。反应在矩阵上可以看到邻接矩阵的对角线均为0。我们要在一个矩阵中同时表示该节点的信息和该节点的邻接信息,就出来了拉普拉斯矩阵。直观的想,拉普拉斯矩阵就是度矩阵减去邻接矩阵,即3

 

上面为什么要说这是一种拉普拉斯矩阵呢,因为拉普拉斯矩阵的定义有好多种,这只是其中的一种:

1、通俗全面理解图卷积与GCN网络(一):图与图卷积插图(3)这种定义的拉普拉斯矩阵全称为Combinatorial Laplacian,也是最简单的一种。

2、通俗全面理解图卷积与GCN网络(一):图与图卷积插图(4)全称为Symmetric normalized Laplacian,一般的图卷积神经网络中都采用这种方式。其目的就是将第一种拉普拉斯矩阵的特征值归一化,防止在训练时尺度不同导致的性能降低。

3、通俗全面理解图卷积与GCN网络(一):图与图卷积插图(5)全称为Random walk normalized Laplacian,也是一种拉普拉斯矩阵的定义方式。

 

为什么拉普拉斯

聪明的同学可能就会想,为什么叫做拉普拉斯矩阵。其实并不是拉普拉斯搞出来的,而是它和图上的拉普拉斯算子有很大的关系。
先放结论:拉普拉斯矩阵就是图上的拉普拉斯算子,或者说是离散的拉普拉斯算子。
推导警告,可直接跳过

众所周知,拉普拉斯算子如下:

 

通俗全面理解图卷积与GCN网络(一):图与图卷积插图(6)

 

这是n维的拉普拉斯算子,而对于图这种离散的结构,偏导当然不能用了,聪明的同学一定知道了,离散域的求导就是差分嘛:
对于一个图f,我们可以仿照上面直接定义其拉普拉斯算子:

 

通俗全面理解图卷积与GCN网络(一):图与图卷积插图(7)

 

其中通俗全面理解图卷积与GCN网络(一):图与图卷积插图(8)为与节点i相邻的节点集合,计算出的通俗全面理解图卷积与GCN网络(一):图与图卷积插图(9)为节点i的拉普拉斯。上面的公示很好理解,就是所有与节点i相邻的节点和节点i做差再求和。(这里操作的是每个节点的特征)
设A为该图的邻接矩阵,那么可以把求和条件扩展为整张图,因为不相邻的地方邻接矩阵值为0:

 

通俗全面理解图卷积与GCN网络(一):图与图卷积插图(10)

 

继续展开:

 

通俗全面理解图卷积与GCN网络(一):图与图卷积插图(11)

 

其中通俗全面理解图卷积与GCN网络(一):图与图卷积插图(12)即为节点i的度,由于对A按行求和。
这里计算出的是节点i的拉普拉斯,对于整张图,我们写成矩阵形式:

 

7

 

所以,可以清楚的看到,对图求拉欧拉斯就相当于对图左乘其拉普拉斯矩阵。

拉普拉斯矩阵的特征值分解

这一部分内容主要会与我们下一篇博客内容有关,在这里我们简单了解一下拉普拉斯矩阵的性质。
特征值分解,有的地方也叫谱分解,或者对角化,是一样的。

这里我们要记住拉普拉斯矩阵的一个性质:拉普拉斯矩阵一定是半正定对称矩阵
依据这条性质,我们知道它一定有n个特征值,而且特征值非负。
故其特征分解为:

 

8

 

其中通俗全面理解图卷积与GCN网络(一):图与图卷积插图(15)是列向量为单位特征向量的矩阵。
可以证明,U是正交矩阵,所以特征分解也可以写成:

 

11

 

图卷积通式

下面我们直接给出类比得出的图卷积通式,在下一篇文章中,我们再详细介绍图卷积的由来:
与卷积类似任何图卷积层都可以看做是非线性函数:

 

12

 

总结

这篇文章我们介绍了图与图卷积的基本概念,但这里的图卷积在实现起来还存在着一些问题,在下一篇文章中,我们将从卷积的本质来导出图上的卷积,并介绍GCN网络。

发表评论

后才能评论