图神经网络 GNN GAT & GCN（一）

作者: 龚俊民(昵称:  除 夕 )

学校: 新南威尔士大学

方向: 自然语言处理和可解释学习

知乎:  https://www.zhihu.com/people/gong-jun-min-74

前言：神经网络要如何聚合图结构中的信息呢？之前有说到有两种主流方法：(1) 把CNN的方法泛化，考虑节点周边的邻居关系进行空间上的卷积，比如 GAT。(2) 利用卷积本质是频域上的滤波这一特性，在频域上操作，比如 GCN。这一期我们来说下这两种方法具体怎么做（来自李宏毅《机器学习》助教姜成翰资料）

Spatial-based GNN

这部分内容会包括 NN4G，DCNN，DGC，GraphSAGE，MoNET，GAT，GIN。它们主要的区分在聚合方式上的操作不同。

我们先来看下卷积是如何聚合信息的。一个 3×3 的权重矩阵作为滑动窗口，Element-wise 乘上图像对应位置的值后相加求和。它相当于对 (x, y) 这个位置的周边8个方向的邻居，做了加权求和。在图结构中我们没法固定窗口，不过也可以用把邻居信息加权求和的思想来聚合信息。这里的邻居都是在空间上的概念，所以这种方法也叫作 Spatial-based Convolution。

一个图的节点通常是用一个嵌入向量来表征的。信息聚合意思是，让包含一个节点信息的嵌入向量，也表征了它周围节点的信息。在 Spatial-based Convolution 中，我们需要有两个信息聚合的操作：一个是用邻居特征更新下一层的隐层，叫 Aggregate，另一个是把所有的节点的特征聚合成一个代表整个图的向量表征，叫Readout。

在图神经网络中，对于输入的节点，会先经过一个嵌入层来得到节点的嵌入表征 h。在 Aggregate 上，一个直觉的做法是，把某个节点的邻居的嵌入表征都乘上下一层的可训练权重   ，再加上原本的输入嵌入。这个权重就类如 CNN 中 feature map 上把窗口内的值求和的加权。这样，下一层的节点嵌入表征，就会因为加权求和操作，聚合到它周边邻居的信息。

在 Readout 上，我们把每一层节点的特征都加起来取一个平均，再通过一个全连接层作为输出层，做任务上的分类或回归。这个 Aggregate 和 Readout 方法叫作 NN4G。它是 2009 年出的，最早的做 GNN 的想法之一。为什么我们要做相加呢？因为每个图上邻居数量不一样，相加比较好处理。

NN4G 只能聚合到它周边最近邻居的信息，而邻居的邻居信息，比如距离为2的邻居信息，就照顾不到。类比于卷积，我们把能聚合多远邻居的距离称之为感受野。2015 年提出的 DCNN 提出了一种渐进式的聚合方法来扩大 GNN 的感受视野。

对第一层的 Aggregate，它考虑的邻居依赖与 NN4G 一样。在如图所示，v3 节点距离为 1 的邻居是 {v0, v2, v4}。在聚合操作上，NN4G 是把与当前节点距离是 1 的邻居嵌入向量做加权求和。但 DCNN 是先把邻居嵌入加起来求平均后，再乘上权重，得到下一层该节点位置的嵌入向量。图中 h_{0,3} 表示的是在第一层，节点 3 的嵌入向量。

到了第二层，它会比 NN4G 多往外拓展一层感受野，计算距离为 2 的邻居。也就是{v0, v2, v4} 的除了 v3 的邻居 {v1}。

以此类推，我们依次计算距离为3,4……k的邻居。H^K 为在第 K 层所有的叠加向量。

readout的时候，DCNN 是把每一层图的隐层向量拼接起来再接上一个 FC 层进行分类。

DGC 与 DCNN 唯一不同在，它在 Readout 这里是把每个隐层加起来做信息聚合。

DCNN 在扩大感受野的过程忽略了一点在，它把每个邻居之间的距离都默认为了1。但事实上，邻居与邻居之间应该有不同的距离权重。MoNET 则考虑了这一点，它使用的是距离的加权求和。MoNET 通过定义某个权重的方式来决定节点与节点之间的距离。我们用 u(x, y) 来表示节点 x 到节点 y 的权重。它是一个二维的向量，维度取值为   。对于每一条边，我们都可以定义这样一个距离。到下一层聚合的时候，我们会用一个全连接层将u(x,y)转换再乘上当前节点隐层做加权求和。这个 u(x, y) 我们也可以定义成别的，让模型能自动学到的权重。

GAT 是在 MoNET 上的延续。它邻居之间边的权重 u(x, y) 是模型自动学出来的。

GAT 具体的做法是，对于某个节点，它的下一层嵌入是该节点对其邻居做自注意力的结果。这个自注意力得分就是边的距离权重。

GraphSAGE 比较了 Aggregate 用 mean, max-pooling 和 LSTM 等各种情况。它尝试把邻居的信息喂给一个 LSTM 取最后的隐层作为输出，来作为聚合后的信息更新每层。它会随机地采样出一个邻居顺序，每次更新都会用不同的顺序。以此来去忽略不同顺序的影响，来学到比较好的聚合信息。

但用 LSTM 的表现不一定非常好。

GIN这篇论文从理论上说明了为什么有些方法会Work，但有些方法不会Work。它证明了最佳的聚合更新方式。对于某个节点 v，它在第 k 层的隐层应该要把它全部的邻居都加起来后，再加上某一个常量乘上节点自身的隐层，再通过一个线性映射。我们要用sum，而不是mean或max，是因为对于有两个邻居的节点和有三个邻居的节点，mean和max都无法区分它们是不同的图。

Spectral-based GNN

另一种给图做卷积的思路是，我们尝试把一个图上的信号（把特征看作是信号），通过傅里叶变换到频域空间，乘上频域空间上的卷积核，再傅里叶逆变换回来。

在讲频域卷积之前，我们需要补充一些《信号与系统》的知识。

信号可以看作是一种 N-维空间的向量。这个向量是由一组基向量通过线性组合合成的。当我们想知道它里面每个不同的部分的权重   ，我们就需要分析。分析方式是我们用这个向量 A 与 A 中的某个特定成分做内积，得到   。

以上是在空间域上的，基向量一般是空间坐标轴 x, y, z。在频域上的基向量一般为 cos 和 sin。

该图比较了二者的对应关系。对于这一部分，非 EE 专业的我，学得很局限。关于傅里叶变换的更多内容可以参照 3Blue1Brown 的  这个视频 。

图结构为节点信号在空间上的关系。我们可以把这个空间上的图转换为频域上的图。对这个图的频谱进行滤波操作后，再转换回空间上的图，就可以实现卷积过程。我们要如何把空间上的图变成频域上的图呢？这里需要了解一下谱图理论。

一个图我们会用邻接矩阵   来表示。   的值为节点 i 和节点 j 的距离权重。我们只考虑无向图。我们再用   来表示度矩阵。度为一个节点与它的邻居的权重边之和。   用来表示节点 x 上的信号。

如何理解这个   ？假设我们的节点代表的是一座城市，而它的信号代表的是这座城市的气温，人口增长数等。这个   便是城市到城市的气温、人口增长数的映射函数。

图拉普拉斯矩阵被定义为   。L 的定义保证了它是半正定的。无向图保证了 L 是对称的。这样我们就可以对矩阵 L 做特征值分解。L 可以分解成   。Λ 是一个全为   的对角矩阵，U 为有向量   组成的正交矩阵。   为频率，   为该频域对应的基。

该图是一个获得 L，Λ 和 U的例子。

我们把上图中的 U 可视化出来，这样我们就得到一个从低频到高频的频谱。频率越低，则   元素间方差越小。相反，频率越高，   元素间方差越大。

当频率很小的时候，所有信号都朝向一致的方向，且值的方差很小。当频率很大的时候，相邻两点之间的信号变化就会很大，比如图e中，它们的方向完全相反，差为两倍的信号大小。

我们可以把 L 当作是一个用来对图操作的矩阵。给定一个图的信号f，用 L 与它相乘，Lf = (D-A)f = Df - Af。它所做的操作刚好等价于当前节点与它周边邻居的能量差异之和。频率越大，相邻节点的能量变化也就越大。

如果我们让 Lf 再乘上当前节点vi，推导化简下来，会得到该节点与周边节点的信号能量差的加权求和。我们就可以用这个计算的结果来量化某个图信号的频域大小是多少。这就是图傅里叶变换.它做的是让图映射到频域上。当我们的图信号越平滑，相邻两个节点信号的差异会越小。反之图信号越不平滑，相邻两个节点信号的差异就会越大。

神经网络的权重也可以用相同的方法转到频域上。二者相乘就完成了滤波操作。

我们要如何把频域的图转换回来呢？直接把某个节点上的频率U 和其能量大小相乘，再加权求和。

整个计算流程如图所示。模型要学习的参数在Λ之中。假如我们让g(L) = log(1 + L)，但 Λ 的大小要与输入的图一致。当图很大时，Λ也会变得巨大。这显然不合适。g(L) = cos(L) = 无穷级数。其中   这里会导致所有节点的信号都互相影响。这不合适，因为它不够像卷积那样只考虑一个固定窗口，聚合的信息是局部化的。

为解决这两个问题，出现了 ChebNet。它让 g(L) 是一个多项式函数，来近似计算图卷积。最高次数 K 是定义好的。所以它能够因K的固定而变得局部化。而且它要学的参数空间复杂度为 O(K)。但我们在用它计算y的时候，它需要乘上傅里叶基U，让时间复杂度变成了   。这带来了第三个问题，计算复杂度过大。

为解决第三个问题，ChebNet用了一个 Chebyshev polynomial 把复杂度降低至O(K|E)。E 为边的数量。这个多项式函数是用一个递归方式定义的。

我们将卷积运算化简可以发现，切比雪夫多项式矩阵的运算是固定的，可以在预处理阶段完成。而且拉普拉斯矩阵一般是稀疏的，可以使用稀疏张量乘法加速，让整个图卷积的计算复杂度大大降低。

受到 ChebNet 的启发，一种更加简单的图卷积变种 GCN 被提出来了。它相当于对一阶切比雪夫图卷积的再近似。我们在切比雪夫卷积核定义基础上，令多项式的阶数为 1，再让拉普拉斯矩阵 L 的最大特征值为2。这样图卷积运算过程可以被进一步简化。GCN 的卷积核变得更小，参数量也更少，计算复杂度也随之减少。它等价于最简的一阶切比雪夫图卷积。在化简中，它使用了一个重归一化技巧。它能将特征值范围进一步缩小使得滤波器变得更加低通。解决的问题是[0,2]范围内的特征值在神经网络中使用多次后，会导致梯度消失和梯度爆炸的问题。ChebNet 虽然比 GCN 复杂度更高，但它的表征能力更强。但我们可以通过堆叠多个 GCN 来扩大图卷积的感受野，所以灵活性比 ChebNet 更高。重要的是复杂度更低的 GCN 会更容易训练，速度快且效果好，实用性强。所以它成为了被提到最多的典型方法。

GCN 在半监督分类任务上的效果表现

我们再回过头来看 GCN 在 TSP 任务上的 Benchmark。TSP 是一个边分类任务。GCN 在没有加残差连接的情况下，随着层数增加表现是显著下降的。

ICLR 2020 有一篇论文探索了图神经网络无法做深的两个原因 (过拟合和过平滑) 并提出了一种简单有效的方法，随机地删除边 DropEDGE。过拟合指的是使用复杂模型去拟合少量数据的时候造成的泛化能力变差的情况。它在深度学习模型中是广泛存在的。过平滑则是指在图神经网络消息传递过程中，所有节点的输入特征会收敛到一个和输入无关的子空间的过程。这一过程会导致输入 GCN 的特征失效并造成梯度消失。过平滑是 GCN 模型特有的问题，它造成了深层图神经网络的训练困难。

实验结果显示，在使用了 DropEDGE 之后，结果会显著好于没有用 DropEDGE。

总结： 在 ChebNet 那边涉及到的理论基础比较深，没有详细讲。日后有机会再填坑。GAT 和 GCN 为两个比较主流的图神经网络。我们通常不会去考虑太多 GCN 的数学基础，而是在实际中拿来用。GNN 也存在随着层数变深，信息损失严重的问题。最新的学习模型通常都会为了适应数据而做些略微的修改，比如 Deep Graph InfoMatrix， Graph Transformer， GraphBert等等。最后推荐使用 DeepGraphLibrary，一个图神经网络的库，以上模型它都已经写好了。此外，与之类似的库还有 PyTorch 的 PyG。