【深度学习】图卷积网络 GCN

参考：https://www.zhihu.com/question/54504471?sort=created

---

GCN是什么？

  GCN 全称是 graph convolution network，中文翻译为图卷积网络。这里的“图”指的不是我们常说的2D图像，而是由一系列顶点和连着这些顶点的边构成的拓扑图，例如，有向图，无向图等等。接下来就以无向图介绍一下 GCN 的工作原理。

拓扑图的信息如何被提取并加以利用？

  这里使用的是图的拉普拉斯矩阵，具体计算方法如下。利用拉普拉斯矩阵可以画出原拓扑图。

$L=D-A$，$L$是拉普拉斯矩阵，$D$是度矩阵，$A$是邻接矩阵

  拓扑图已经表示用矩阵出来了，如何让它参与卷积呢？首先，需要进行傅里叶变换；然后，卷积。

傅里叶变换

  学《信号与系统》我们了解到时域上的卷积等于频域上的乘积，使用(e^{-jomega t})作为基函数。其中(e^{-jomega t})是拉普拉斯算子的特征函数,即式(Delta e^{-jomega t}= frac{{partial}^2 }{partial t^2} e^{-jomega t}=-{omega}^2 e^{-jomega t})成立。而广义的特征方程定义为(AV=lambda V)，其中，(A)是一种变换，(V)是特征向量或者特征函数（无穷维的特征向量）。
  根据以上理论，结合拉普拉斯矩阵就是离散的拉普拉斯算子，我们求出拉普拉斯矩阵(L)的特征向量，就可以做类似于傅里叶变换的工作。并且拉普拉斯矩阵为对称半正定矩阵，特征值均大于等于0，可对角化(L=ULambda U^T)（这里假设了特征值互不相等，因此(U)矩阵各向量正交，(U)为正交矩阵，满足(UU^T=E))。
  定义拓扑图的傅里叶变换为：

$F(lambda_l)=sum_{i=1}^Nf(i)u_l(i) ag {1}$   其中，$f$是图上的N维向量，$f(i)$与顶点一一对应，$u_l(i)$表示第$l$个特征向量的第$i$个分量。那么特征值（频率）$lambda_l$下的，$f$的graph傅里叶变换就是$lambda_l$对应的特征向量和$f$的内积。（1）式的矩阵形式：$F=U^Tf$。显然，对应的傅里叶逆变换：$f=UF$。

卷积

  直接给出卷积公式：

$(f*h)_G=U((U^Th)odot (U^Tf)) ag {2}$   （2）式右边的$U$用来将谱域（spectral domain）结果通过逆傅里叶变换到空域（spatial domain）。$U^Th$，$U^Tf$分别是卷积核$h$，图向量$f$的傅里叶变换。$odot$表示哈达马积，对于两个维度相同的向量、矩阵、张量进行对应位置的逐元素乘积运算。

DeepLearing中的GCN

  GCN 在不断的发展。

第一代GCN

  该方法直接将(U^Th)变为可学习的参数，即

$y_{output}=sigma (U(g_ heta odot (U^Tf))) ag {3}$   其中，$sigma ()$是激活函数，其中$g_ heta = ( heta_1, heta_2, cdots, heta_N)^T$。

第二代GCN

  与第一代GCN不同的是，该方法中的(g_ heta = (sum_{j=0}^Kalpha_j {lambda_1}^j, sum_{j=0}^Kalpha_j {lambda_2}^j, cdots, sum_{j=0}^Kalpha_j {lambda_N}^j)^T)，其中(lambda_i)为(L)的特征值。