图神经网络：GCN

GCN 基本原理

在机器学习中，我们常用 MLP、CNN、RNN 等网络来对数据进行特征学习，这些网络对数据都有一个要求，那就是维度是确定的、是规则的，否则就无法进行学习。也就是说，这些网络的数据是在欧氏空间中的，它是一种向量空间，存在距离、角度等几何意义。

但是图结构是一种非欧结构，在图结构中，距离、角度等几何意义都不复存在，取而代之的是节点和边。如何在图结构中进行特征学习，一直是一个比较难的问题。

我们可以从二维卷积出发，想象一个二维卷积是怎么在图像上抽取信息的，它在第一层只对周围几个像素进行卷积，将卷积结果作为自身的值，那么在下一层卷积时，由于周围也同样进行了卷积操作，此时就可以获取到周围的周围的信息。也就是说感受野在不断扩大，以此来加强卷积的特征抽取能力。

在 GCN 中我们也可以沿用相同的思路，我们先对一个节点的邻居进行卷积，那么在下一层中，由于邻居也进行了卷积，此时我们就可以卷积到邻居的邻居的信息。那么关键问题就变成怎么卷积。

我们可以先考虑最简单的情况，为了描述一个图结构，我们会有一个邻接矩阵 $A$，同时还有一个特征矩阵 $X$ 来描述每个节点的信息。假设节点个数为 $n$，那么邻接矩阵 $A$ 的形状就是 $n\times n$，假设每个节点用一个 $d$ 维的向量来表示，那么特征矩阵 $X$ 的形状就是 $n \times d$。于是我们可以得到以下公式来表示卷积操作，其中 $W$ 表示可学习的参数，$\sigma$ 表示激活函数。

$$f(X,A) = \sigma(AXW)$$

此时就是最简单的卷积操作了，就是邻接矩阵和特征矩阵相乘，就可以描述整个图结构，然后再与可学习的权重矩阵相乘，最终就是一个进行特征抽取的过程。进一步，为了表示多层卷积，我们使用上标 $(l)$ 来表示第 $l$ 层。可得公式：

$$H^{(l+1)}=f(H^{(l)}, A) = \sigma(AH^{(l)}W^{(l)})$$

特别的，有 $H^{(1)} = X$

但这样简单的处理有两个问题：

1. 节点无法考虑自身信息，因为邻接矩阵是存储边信息的，连到自身的边大部分图结构中都没有，所以在此处邻接矩阵中的元素为 0，所以在计算节点信息时不会考虑自身。
2. 邻接矩阵没有经过归一化，会改变原始特征的分布。

为了解决以上问题，我们首先对邻接矩阵进行调整，即加上一个单位矩阵，就可以让计算过程考虑到自身。

$$\hat{A} = A + I$$

我们可以使用度矩阵 $D$ 来实现归一化，其中 $\hat{D}$ 为 $\hat{A}$ 的度矩阵

$$\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$$

在经过以上两步操作之后，就可以解决这两个问题，于是有最后的公式：

$$H^{(l+1)}=f(H^{(l)}, A) = \sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$$

我们再来看下矩阵运算的形状变化，其中 $D,A$ 都是形状为 $n\times n$ 的矩阵，$H$ 为 $n \times d$，计算过后会得到考虑了图结构之后的图信息计算矩阵，其形状为 $n\times d$，随后与可学习的权重矩阵相乘，来对图信息进行抽取和学习。

权重矩阵的形状为 $d\times k$，其中 $k$ 是人为设定的特征向量的维度，所以权重矩阵的形状实际上和图结构没有任何关系，只和图信息维度和特征向量维度有关，于是我们可以很简单地得到结论，GCN 的训练和推理可以是不同的图结构，但也说明每一层是共享一个权重矩阵的。

如何处理有向图？

在有向图中，邻接矩阵不是对称的，且每个节点的度将分为出度和入度，在原始 GCN 的卷积计算过程中存在问题。所以 GCN 无法直接处理有向图，通常需要将有向图转化为无向图（这会带来一定的信息损失），或者使用 GCN 的变种 DGCN，通过修改卷积传播信息的方式来实现有向图的卷积。

训练和推理

在 Semi-Supervised Classification with Graph Convolutional Networks 这篇文章中，其训练时输入的是完整的邻接矩阵和节点信息，使用训练集进行损失函数的计算和反向传播。

具体来说，在所给代码中，输入是整个图的信息，输出也是整个图的标签，根据所选的训练集计算其损失，然后基于该损失进行反向传播。所以在推理环节，输入的是整个图，得到的输出也是整个图所有节点的标签。

由于输入输出都是完整图的信息，这也导致了其无法处理大规模的图结构。

GraphSAGE

由于 GCN 的种种问题，导致其难以落地，GraphSAGE 提出的核心就是从图全局的计算转移到图局部的计算，也就是基于节点及其邻居计算，而不是直接计算整张图。试图解决处理不完整的图及复杂度过大的问题。

其主要思想为以节点为中心，从内向外选取邻居，再从外向内计算聚合。

首先基于我们要计算的节点，我们对邻居进行抽样选取，再对邻居的邻居进行抽样选取，当满足我们想要的层数之后，就形成了一个以我们选取节点为中心的树状结构，向外扩张的样子。

我们首先聚合最外层节点的信息，生成最外层 - 1 层的聚合信息，随后再基于该聚合信息，再往内聚合。最终的效果就是中心节点会聚合到整个树状结构的信息，和卷积有些类似，感受野随着层数加深而变大。通过这样迭代计算的过程将节点周围的图信息聚集到节点本身上。

具体来说，首先要进行采样，采样是一个自定义的过程，最简单的是定长采样，例如第一层每个节点采样 3 个邻居，第二层每个节点采样 5 个邻居。如果邻居数不够，则可以重采样，如果邻居数过多，则抽样采样。

在完成采样之后会形成一个树状图结构，首先初始化所有节点的 embedding，然后从最外层开始向内计算聚合 embedding。计算聚合是通过聚合器函数实现的，聚合器函数类似于卷积核，最简单的可以是平均聚合，即聚合 embedding 计算是对所有邻居取平均，或者池化聚合，更复杂还可以使用 GCN 或 LSTM 当作聚合器函数。

当从最外层一层一层聚合到中心节点时，中心节点就完成了聚合。

需要注意的是聚合器函数一层只有一个，所以在一层中，所有节点都是共享一个参数的，这样可以使训练出来的模型可以适应不同的图结构。

---