GNN survey

convolution

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

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

spectral Network

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

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

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

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

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

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

当给了一张图：

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

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

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

  $\Lambda =diag({\lambda }_0,...,{\lambda }_{n-1}),U=[{\mu }_0,..,{\mu }_{n-1}],正交的$。

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

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

• 那么就有下式的成立：

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

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

• Vertex domain 转换成 spectral domain

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

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

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

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

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

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

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

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

• 现在我们明确了我们想找的filter $g_{\theta }(\Lambda )$,使得：
  $$\hat{y}=g_{\theta }(\Lambda )\hat{x}$$

  $$\Rightarrow g_{\theta }(\Lambda )U^{T}x$$

  两边同时成一个 U
  $$U\hat{y}=U{g}_{\theta }(\Lambda )U^{T}X$$
  合并一下：
  $$y=U\hat{y}=U{g}_{\theta }(\Lambda )U^{T}X=g_{\theta }(U\Lambda U^T)X=g_{\theta }(L)x$$

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

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

还有另外一个问题2：

当$g_{\theta }=L^2$的时候：

$L^2$代表着与结点距离为2的邻居结点的信息，$L^n$则代表着距离为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