GCN入门

为什么需要GCN

CNN之所以可以在图像识别领域具有重要作用，主要是因为CNN利用了图片在其域中的平移不变性。如下图所示。而且图片也是一个规整的二维矩阵

但是许多非结构化数据并不具备规整的二维矩阵，如下图所示

GCN的演进

第一代GCN

• 首先考虑到卷积定理

在适当条件下，两个信号的卷积的傅里叶变化是他们傅里叶变化的点积。

• 基于上述定理，既然我们无法对graph数据直接进行卷积操作，那么我们就可以先对其转化进行傅里叶变化，然后再做点积，然后再做反向的傅里叶变化。

• 傅里叶变化的定义： $\hat{f}=U^Tf$，其中U为我们拉普拉斯分解的正交矩阵，里面每个向量都为一个基向量。

• 对应的逆变化为 $f=U\hat{f}$

• 具体来说公式如下所示，其中 $\mathscr{F}$代表的是傅里叶变化。f代表的是我们原有的graph数据，h代表的是我们的卷积核。

  • f的维度可以是[N, D]，其中N为节点的个数，D为特征的维度
  • 之所以不把h也写成傅里叶变化的形式是因为h是learnable的参数，学习傅里叶变化后的参数和直接学习本身是一致的。
  • 整个graph的邻接矩阵是蕴含在U里面的。
  • U的定义为 $U=D-A$,其中D为度矩阵，A为带权邻接矩阵。其具体的推到见下一章所示。
    

• 直观来讲，h就是我们需要学习的参数。通过卷积定理，我们把卷积操作转化成了点乘的操作。

第二代GCN

• 上面我们介绍了第一代的GCN，但是它主要有以下几个缺点
  • 计算复杂度太高，我们需要对拉普拉斯矩阵分解得到特征矩阵向量U，其时间复杂度为 $O(n^3)$
• 为了解决上述问题，作者提出了第二代的GCN，ChebNet。
• 作者引入了 $k$阶多项式来表示拉普拉斯的特征矩阵向量U

第三代GCN

• 第二代卷积解决了U的特征向量分解的问题，但是在计算图卷积的过程中，我们仍然需要计算矩阵乘法，每次的时间复杂度都会O(n^2),n代表的是图中节点的个数。对于我们一个庞大的图来时，时间复杂度较高。
• 为了解决上述问题，作者提出了下述的多层图卷积网络传播规则，其中 $\tilde{A}=A+I_N$, $A$代表的是邻接矩阵， $I_N$代表的是单位矩阵，所以 $\tilde{A}$可以理解为添加自连接的邻接矩阵。 $\tilde{D}$代表的是节点的度矩阵。 $W$代表的是参数。 $\sigma$代表的是激活函数。 $H^{(l)} \in \mathbb{R}^{N \times D}$, $H^0 = X$
  

公式推导

拉普拉斯矩阵

• 为什么拉普拉斯矩阵的定义为 $D-A$,我们首先需要了解什么是拉普拉斯算子

拉普拉斯算子（Laplacian）是由欧几里得空间中的一个函数的梯度的散度给出的微分算子

• 这里引入了一个新的概念——散度，这里简单介绍下：散度（Divergence）是向量分析的一个向量算子，将向量空间上的向量场（矢量场）对应到一个标量场。散度描述的是向量场里一个点是汇聚点还是发源点。值为正时表示该点为发源点，值为负时表示该点为汇聚点。当拉普拉斯算子为整的正的时候，代表原函数的变化会越来越快，所以是发散的。当算子未负的时候，代表变化会越来越慢，所以是汇聚的。

• 拉普拉斯算子在笛卡尔坐标系中的定义为，数学表示为各个维度的二阶导数之和。
  

• 我们将其推广到图中，则有
  
  

参考文献

1. 万字长文带你入门 GCN