图神经网络综述（二）

点击关注"AI知识工厂"

更多干货，敬请期待...

关注公众号：AI知识工厂，回复GNN，下载李宏毅老师GNNs课程PPT。

       在讲GNN之前，我们先来回顾下一般的CNN过程，比如，我有一张256*256的image，我们在做卷积的时候，通常会固定一个大小的filter，比如3*3，然后对整张图做local convolution。然而在图网络中，由于网络的不规则性，我们无法使用一个固定的kernel做convolution。由此引出我们今天要讲的主题：如何将图网络中的节点信息采用卷积的方式进行嵌入，也就是本章内容要讲的ConvGNNs。这一章内容主要参考《A Comprehensive Survey on Graph Neural Networks》以及李宏毅老师的GNNs课程，文末附有链接。

方案一：参考CNN的思想，对每个节点的邻居进行某种方式的加权求和，即Spatial-based convolution

方案二：参考传统的信号处理的方法，对原始信号进行处理，引入滤波器来定义图卷积，图卷积运算被解释为从图信号中去除噪声，即Spectral-based convolution

接下来我们着重看下这两种方法。

Spatial-based convolution（基于空间的卷积）

定义：Spatial-based convolution与传统CNN在图像上的卷积运算类似，基于空间的方法根据节点的空间关系定义图的卷积。图像可以看作是图形的一种特殊形式，每个像素代表一个节点，如下图(a)所示，每个像素直接与其附近的像素相连。一个过滤器被应用到一个3×3的patch，通过对中心节点的像素值和它的邻居在每个通道的加权平均值。类似地，基于空间的图卷积将中心节点的表示与它的邻居的表示进行卷积，以得到中心节点的更新表示，如图(b)所示。从另一个角度来看，基于空间的convgnn与recgnn在信息传播/消息传递方面有着相同的思想。空间图卷积运算本质上是沿着边传播节点信息。

方法步骤：对于下图，假设我们现在要做graph classification，我们如何将Layer i的图网络convolution到Layer i+1的那一层去，并且如何将整张图抽象成一个high-level representation，我们采用以下两个步骤：

第一步Aggregate（聚合）：用neighbor feature update下一层的hidden state。比如下图，我们想要将  通过convolution的方式转变成  ，我们可以通过某种加权求和的方式将 Layer i 层的 以及  的邻居节点的feature整合起来，从而得到  的feature，其它节点一样的道理，最后得到Layer i+1层的hidden state。

第二步Readout（读取）：如果是graph-classification，需要把所有的nodes的feature集合起来代表整个图的feature。即采用某种sum或者average的方式将所有nodes的feature抽象成一个hidden state，并以此代表整张图的feature。

代表的网络如下

图神经网络(Neural Network for Graphs, NN4G)：

      如下图所示，对于NN4G网络，通过直接将节点的邻域信息相加来进行图卷积，应用residual connections和skip connections来记忆每一层的节点信息，表达式如下： 

其中  是激活函数，比如Relu，  和  是待学习的模型参数，即下图中的  ，下图中Hidden Layer 1中的  的获得是将  以及其邻居的信息进行相加，并通过加权的方式整合input layer在该节点的信息（  ），转成矩阵形式就是： 

 其中矩阵  就是图网络的邻接矩阵。

而readout层则通过对每一层的所有节点信息的取平均，即下图中所有紫色节点  ，从而获得每一层图的representation，并对每一层的信息通过求和平均的方式进行整个图的representation更新，即：

扩散卷积神经网络(Diffusion Convolutional Neural Network,  DCNN)：

DCNN在Aggregate阶段给出了不一样的方法，DCNN将图卷积视为扩散过程，它假设信息以一定的转移概率从一个节点转移到邻近的节点，使信息分布在几轮后达到均衡。如下图所示，第一层的  的结果是与  距离为1的节点的featue的求和平均，同理第二层的  则是与  距离为2的节点的featue的求和平均，这样我们对每一层的卷积操作可以用以下公式表示：

 其中K表示层数，  代表转移矩阵，  是节点度矩阵，  是邻接矩阵，  就代表了卷积所能观测到的节点邻居范围，  时表示对距离为1的邻居节点的卷积，  时表示对距离为2的邻居节点的卷积。

当我们计算出了每一层的节点的feature的时候，我们需要对每一层的节点feature进行concatenation成一个矩阵  ，然后通过一些线性变换对每个节点在不同层的feature做特征变换，如下图所示，最终得到整张图或者每个节点的特征矩阵  。

混合模型(Mixture Model Networks, MoNET)：

MoNET同样是定义了一种新的Aggregate的方式，在Aggregate阶段不是简单的对邻居节点feature的平均求和，而是通过加权的方式，权重的计算则是通过衡量节点之间的度的距离方式，即： 

 其中  表示几节点 的度，图中的  则是特征变换（比如NN），经过NN对节点feature进行编码，最后对某一节点的邻居节点特征加权求和。

图采样聚合模型(Graph Sample and aggregate, GraphSAGE)：

GraphSAGE主要是通过对邻居节点采样的方法对节点信息进行更新，即图中的Step 1，然后再对这些采样的节点信息进行某种方式的聚合，主要有Mean\Pooling\LSTM三种aggregator的方法，即图中的Step 2，Step 3则是利用聚合信息进行当前节点label或者邻居节点的预测，预测的方式有两种，一种是无监督学习方式。无监督学习基于图的损失函数希望临近的顶点具有相似的向量表示（公式的前半部分），同时让分离的顶点的表示尽可能区分（公式的后半部分），损失函数如下： 

 其中  是  的临近节点，  是负采样样本的分布，即对远离节点  的节点的采样，  是负采样的个数，   是待学习的节点特征。第二种是有监督学习方式，监督学习形式根据任务的不同直接设置目标函数即可，如最常用的节点分类任务使用交叉熵损失函数等。

图注意神经网络(Graph Attention Networks, GAT):

图注意神经网络采取了Attention的方式来计算节点间的权重大小，最后通过加权求和的方式更新节点的feature，节点间权重的计算公式如下：  

 其中  是模型更新之后的权重表达式，  是节点  相对于节点  的attention值，  是模型学习的参数。

下图就是GAT模型的图卷积层的更新过程，其中  就是attention的权重。

 Spectral-based convolution（基于光谱的卷积）

定义：通常情况下，卷积的操作是在时域上完成，Layer i 经过filter得到Layer i+1层信息，如果我们将图信号在频域中实现上述过程，则需要先对Layer i图信号进行Fourier Transform，然后根据时域上的卷积等于频域上的乘积，将傅里叶变换后的Filter与傅里叶变换后的图信号相乘，最后将得到的信号经过反傅里叶变换得到Layer i+1层的信息。

       在Spectral-based的模型中，图通常被假定为无向图。对无向图比较鲁棒的表示方法是归一化的拉普拉斯矩阵（Normalized graph Laplacian matrix），拉普拉斯矩阵  ，归一化的拉普拉斯矩阵  被定义为：  其中  是图的对角度数矩阵，  是图的邻接矩阵， 

归一化的图的拉普拉斯矩阵  是一个实对称的半正定矩阵。根据这个性质，可以将拉普拉斯矩阵  分解为： 

上述的表达式中，  是奇异值向量的矩阵。  是奇异值的对角矩阵，  对角线上的每一个元素是一个奇异值  ，  中的奇异值向量构成了一个正交的空间，因而有性质  ，在图信号处理的过程当中。一个图信号  是一个特征向量，其中每一个元素  是图中第  个结点的值，  。

      有了上述了定义之后，我们来看一个具体的例子加以说明，（例子来源：李宏毅GNNs课程），如下图所示，给定  和  以及图网络节点信息  ，我们对  做拉普拉斯变换，最后得到图中的  ，通过计算，我们发现，  中的每个元素都是每个节点自己的信息与相邻节点信息的差的和。如果把  看成是能量的话，就需要对  进行平方，能量总和就是  ，  可以看成是节点间信号能量的变化。自然而然，如果节点间的信号变化量比较大（频率比较大），能量总和就比较大，如果节点间信号变化量比较小（频率比较小，极端情况下直流信号），能量总和就比较小，如图3所示。 

 图 1

图 2

图 3

简单地讲就是，  代表频率分量，每个  对应的  即是该频率下的信号能量变化。下图中的  可以看成是频率，频率越高说明节点间能量变化越大，频率越低，节点间能量变化就越小。

      所以图的傅里叶变换就是  ，可以看成是基函数和原函数的内积，向量内积可以表示向量之间的相似程度，也代表了下图中的值  （可以理解为对应  频率下，该成分分量的大小，即基函数下的坐标），图中的  就对应于下图的  ，有点类似时域转频域。对于Filter，我们同样采取相同的傅里叶变换操作。

接下来就是逆傅里叶过程，信号在频域下转成时域下的模式，假如我们需要求  在  时刻的信号大小，则需要先求出各个频域分量在  时刻的成分大小乘以对应频域下的振幅大小  ，然后加起来就是时域下的信息大小， 即： 

同理，对于图的逆傅里叶变换就是  ，我们想要求出  处的大小(对应上面的  )，就需要求出信号各个频域分量在  处成分的大小(  )乘以在对应频率下的振幅大小  (对应上面的  ，基下的坐标)，然后加起来就是时域下的信息大小。

注：下面这张图中最右边部分对应于上面这张图最左边部分，上图中各个分量的  对应下图中L矩阵的特征值分量  。

综上所述，从图的傅里叶变换的定义中我们可以理解：

1、图的傅里叶变换是将输入的图信号x映射到由U中的奇异值向量所构成为的正交空间中去。

2、傅里叶变换的结果是图信号在新的空间（由奇异值向量所构成的空间）对应的坐标。

3、我们可以写出输入的图信号  在新的空间中的表示： 根据图的傅里叶变换，可以定义图卷积，假设图的输入信号为  ，滤波器为  ，图卷积可以被定义为： 其中  表示element-wise product，如果换一种表示方法，把表示  为滤波器。为模型要学习的参数，图卷积可以被简化为： 以上就是spectral-based的图卷积网络的定义，不同的网络结构在于对滤波器  的选择。

总结：时域下的卷积等于频域下的乘积，所以我们可以通过设定一个关于  的Filter，然后让这个频域下的Filter和频域下的shu'r信号进行相乘，得到Filter后的响应，最后我们通过逆傅里叶变换将频域下的信号变成时域。

接下来，我们深入讨论下不同Filter的特点以及Filter的选择，请先看下面两个问题：

两个问题：

1、  复杂度较高

请先看下面两张图

第一张图表示信号在频域中的卷积过程，即傅里叶变换过程  。

第二张图表示spectral-based的图卷积过程，即时域下的变换  。

讲道理，  可以取任意的关于  函数，假如我们取  (泰勒展开)，看到这里我们会发现第一个问题，就是泰勒展开后的  的复杂度会比较高，其复杂度和input graph的大小有关。而我们在做CNN的时候，不管input graph有多大，都可以用一个一样大的model去训练，而对于Spectral-based Graph来说，只要我们遇到一个不一样的input都要重新学一个model，而且复杂度不一样。

2、不是localize convolution的模型

如下第一张图所示，假设  ，  ，这个时候  的第一行的最后一个数是0，也就是说  这个节点（  中-3）影响不到  （  中的2）的更新，但如果  取  的话，就是会影响到（如下第二张图所示），所以该卷积过程并不是localize的。假设我们取  ，那它在经过一次filter的时候就能看遍整张图，并没有考虑neighbor的信息，即不是localize convolution。

举例：ChebNet

ChebNet解决的问题就是运算速度快，并且能实现localize，通过选定  是多项式函数，限定  的次数，可以最大实现K-localize，并且拉式变换复杂度在  ，即  ，但是当在做inverse fourier transform的时候，复杂度会变成  ，即  。

为了解决时间复杂度的问题，ChebNet采用chebyshev polynomial，本质的目的就是把  转变成一种容易计算的  ，递归的方程式如下： 

下面这波转换的目的只是为了方便计算，（多项式展开），  好比下图的3，7，-2等，  好比a,b,c,

下面是对多项式的展开，其中红色部分可以用递归的方式进行计算得到，这样的话，复杂度就降低了，变成  。

下面是ChebNet的模型图，假设我们有  个channel，我们就需要有  个filter做卷积。

下面是GCN的计算方式，其中  就是上一层的节点特征  ，  就是下一层的节点特征  ，GCN就是采用了ChebNet算法模型中  的情况，最终模型更新的公式为：  ，这也是最常用的一种GNN的模型。

将上述式子转变成通俗理解的意思，就是下面的形式，第  个节点的hidden feature的等于它所有邻居节点的transform的和的平均加上一个biase，并激活。

推荐阅读

扫描下方二维码，及时关注最新内容

参考文献：

[1] Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on Graph Neural Networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019.

[2] 李宏毅GNN课程. https://www.youtube.com/watch?v=eybCCtNKwzA&t=1s.