详解GCN原理-公式推导

GNN survey

convolution

如何graph domain 上做convolution 是最近最热门的研究方向。

总的来说有两种卷积的方法： Spectral and non-spectral (spatial)

spectral Network

通过对图的拉普拉斯矩阵做特征分解，将它定义在 傅里叶 domain上。

在深入解释之前，先看一些有关图的定义，以下都是针对无向图所做的说明

对于图$G$G,可以用它其中的节点$V$V 和 边$E$E来对他进行定义。

矩阵$A$A是图的邻接矩阵，反应了节点之间有无连接。

$D$D代表了图的度矩阵，表示了每个节点有多少个度，即有多少条边和它相连接，$D$D为对角矩阵

$f$f代表了一中映射，可以节点转换为信号。

当给了一张图：

• 我们有了它的邻接矩阵$A$A和度矩阵$D$D

• 计算拉普拉斯矩阵，其实很简单就是$D-A$D−A:

• 然后对$L$L做spectral decomposition ，又称特征分解。因为$L$L是对称矩阵，所以可以得到以下的分解形式：
  $L=U\Lambda\ U^T$L=UΛ UT
  其中$\Lambda$Λ是特征值的对角矩阵，$U$U是一个由特征向量组成的向量。

  $\Lambda=diag(\lambda_0,...,\lambda_{n-1}), U=[\mu_0,..,\mu_{n-1}],正交的$Λ=diag(λ0​,...,λn−1​),U=[μ0​,..,μn−1​],正交的。

• 假设$f=[4,2,4,-3]^T$f=[4,2,4,−3]T,我们来研究$Lf$Lf代表了什么意思：
  $Lf=(D-A)f=Df-Af$Lf=(D−A)f=Df−Af
  

我们只关注于第一个结点$v_0$v0​，根据上图我们可以看到，结果 $a$a就是结点$v_0$v0​和它的两个邻居结点$v_1,v_2$v1​,v2​信号的差值。

• 那么就有下式的成立：

如果$f^TLf$fTLf表示相邻结点之间能量的话，那么如果信号的频率越高，则相邻的两个信号之间的差值就越大，能量也就会越大。

• 而特征值$\lambda$λ,就是一种频率的反映

• Vertex domain 转换成 spectral domain

  给定一个图的结点的signal $x$x,则经过傅里叶转换到频域上的 $\hat x=U^Tx$x^=UTx

其实就是乘上不同频率 $\lambda$λ上的特征值，得到这个信号在不同频率上的大小是多少：

• 怎么转换回去呢？spectral domain 转换成 Vertex domain

  就是将每一个频率下对应的信号，和对应特征向量中的值相乘：

右边一列是在不同特征值下的特征向量的分布情况，下面的那一行不同频率下的值。

现在我们知道了 vertex和spectral domain 互相转换的方法

**如果我们在spectral 转换成 vertex的时候，改变转换时乘上的参数，改成一个$g_\theta(\Lambda)$gθ​(Λ) 一个关于$\theta 的函数$θ的函数 ** 。

然后我们希望通过这个$g_\theta$gθ​转换成我们想要的label，那么这个过程就是可以通过神经网络进行训练的。

• 现在我们明确了我们想找的filter $g_\theta(\Lambda)$gθ​(Λ),使得：
  $\hat y=g_\theta(\Lambda) \hat x$y^​=gθ​(Λ)x^

  $\Rightarrow g_\theta(\Lambda) U^Tx$⇒gθ​(Λ)UTx

  两边同时成一个 U
  $U\hat y=U g_\theta(\Lambda)U^TX$Uy^​=Ugθ​(Λ)UTX
  合并一下：
  $y=U\hat y=U g_\theta(\Lambda)U^TX=g_\theta(U\Lambda U^T)X=g_\theta(L)x$y=Uy^​=Ugθ​(Λ)UTX=gθ​(UΛUT)X=gθ​(L)x

• 上述的$g_\theta(.)$gθ​(.)可以是任意的一个函数，比如:

根据泰勒展开式会有上述的形式，但是这样会出现一个问题1，就是学习的复杂度太高了：$O(n)$O(n)

还有另外一个问题2：

当$g_\theta=L^2$gθ​=L2的时候：

$L^2$L2代表着与结点距离为2的邻居结点的信息，$L^n$Ln则代表着距离为n。如果当n越来越大，那么图中的每一个结点会和其他的所有结点相关，这个就违反了局部性 localized。

使用ChebNet去解决上述的两种问题

我们使用 一个可以被循环计算的多项式函数来拟合L

综上，GCN的最终形态会被写成：

参考
视频:https://www.youtube.com/watch?v=M9ht8vsVEw8&t=1913s
PPT:http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML2020/GNN.pdf