通俗全面理解图卷积与GCN网络（一）：图与图卷积

下一篇：通俗全面理解图卷积与GCN网络（二）：从图卷积到GCN

前言

相信大家都了解普通卷积操作，在一般的论文里，习惯认为普通的卷积是操作在Euclidean Structure，即欧几里得空间上的。直观的来看，一般卷积操作的图片是非常整齐的矩阵，一个像素周围必定有上下左右以及斜对角八个像素包围，这样的卷积好操作，卷积核大小也固定，再加之权值共享，有效的提取空间特征同时减少参数，使得CNN成为深度学习图像处理界当之无愧的扛把子。 但人们逐渐认识到，并非所有的数据都是这样规则的。 反而可以说，自然界中大多数的数据都是不规则的。也就是数据之间相互影响，构成了数据结构里图的形状。即使普通我们规则的图像，我们在逐像素处理中可能计算了很多对我们任务来说无用的像素点。而如果我们提取关键点，这些点之间也会构成一幅图。这里的图指图论里的图，而非我们平常见的图片。 CNN理论已经非常完整，但是遇到这种不规则的图结构，我们又该如何提取它的空间特征呢？这就应该从CNN的本质说起，去模仿它，把它扩展到所谓的非欧几里得空间里，这就是我们所说的“图卷积”。

图

一般表示

度、邻接、拉普拉斯

我们先来介绍一下图论里面的相关概念（会的同学直接跳过） 相信大家在查资料时下面这幅图也见过不下十次了，我们这里也用这幅图来说明：  
  可见，最左面画出了一个拥有6个节点，7条边的无向图，右面分别是该图所对应的度矩阵、邻接矩阵和一种拉普拉斯矩阵。   节点的度： 节点的度定义为该节点上拥有的边数，上面的度矩阵也就是每个节点的度所构成的对角矩阵。 邻接矩阵： 邻接矩阵代表了图的几何结构，在节点联通的地方取值为1，不联通的地方取值为0.也即：A(i,j)=1 if 节点i和j联通 else 0。易知一个无向图的邻接矩阵一定是对称的。 拉普拉斯矩阵： 邻接矩阵只定义了与该节点联通的节点有哪些，而没有该节点自身的信息。反应在矩阵上可以看到邻接矩阵的对角线均为0。我们要在一个矩阵中同时表示该节点的信息和该节点的邻接信息，就出来了拉普拉斯矩阵。直观的想，拉普拉斯矩阵就是度矩阵减去邻接矩阵，即
  上面为什么要说这是一种拉普拉斯矩阵呢，因为拉普拉斯矩阵的定义有好多种，这只是其中的一种： 1、这种定义的拉普拉斯矩阵全称为Combinatorial Laplacian，也是最简单的一种。 2、全称为Symmetric normalized Laplacian，一般的图卷积神经网络中都采用这种方式。其目的就是将第一种拉普拉斯矩阵的特征值归一化，防止在训练时尺度不同导致的性能降低。 3、全称为Random walk normalized Laplacian，也是一种拉普拉斯矩阵的定义方式。  

为什么拉普拉斯

聪明的同学可能就会想，为什么叫做拉普拉斯矩阵。其实并不是拉普拉斯搞出来的，而是它和图上的拉普拉斯算子有很大的关系。 先放结论：拉普拉斯矩阵就是图上的拉普拉斯算子，或者说是离散的拉普拉斯算子。 推导警告，可直接跳过 众所周知，拉普拉斯算子如下：     这是n维的拉普拉斯算子，而对于图这种离散的结构，偏导当然不能用了，聪明的同学一定知道了，离散域的求导就是差分嘛： 对于一个图f，我们可以仿照上面直接定义其拉普拉斯算子：     其中为与节点i相邻的节点集合，计算出的为节点i的拉普拉斯。上面的公示很好理解，就是所有与节点i相邻的节点和节点i做差再求和。（这里操作的是每个节点的特征） 设A为该图的邻接矩阵，那么可以把求和条件扩展为整张图，因为不相邻的地方邻接矩阵值为0：     继续展开：     其中​即为节点i的度，由于对A按行求和。 这里计算出的是节点i的拉普拉斯，对于整张图，我们写成矩阵形式：  
  所以，可以清楚的看到，对图求拉欧拉斯就相当于对图左乘其拉普拉斯矩阵。

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

这一部分内容主要会与我们下一篇博客内容有关，在这里我们简单了解一下拉普拉斯矩阵的性质。 特征值分解，有的地方也叫谱分解，或者对角化，是一样的。 这里我们要记住拉普拉斯矩阵的一个性质：拉普拉斯矩阵一定是半正定对称矩阵。 依据这条性质，我们知道它一定有n个特征值，而且特征值非负。 故其特征分解为：  
  其中是列向量为单位特征向量的矩阵。 可以证明，U是正交矩阵，所以特征分解也可以写成：  
 

图卷积通式

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

总结

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