图神经网络基础篇(2)：原始图神经网络

图神经网络基础篇(1)是一些基本知识，我会根据当前篇的内容对之进行更新，有需要的小伙伴请自行翻阅哦。

Vanilla GNN的数学表示

原始图神经网络，英文翻译是Vanilla Graph Neural Network，简称Vanilla GNN，在Scarselli et al. (2009)中首次提出。我们来一起研究一下，图神经网络的基本思想。

在图神经网络基础篇(1)中，我们介绍了图的两个最基本要素，节点和边，这里我们引申一下，每个节点都是有特征的，比方我们的人际关系网络中，每个人都有自己的年龄、身高、兴趣爱好等等多维特征。

图中的节点因此就有两个基本要素了：特征、与其他节点的关系。此时，一个图可以由两个矩阵来表示，一个是节点特征，假定有 $n$ 个节点，每个节点有 $m$ 维特征，则我们构建一个矩阵：

$X = \begin{bmatrix} \mathbf{x}_1\\ \mathbf{x}_2\\ \vdots\\ \mathbf{x}_n \end{bmatrix}$

来表示节点特征，称为特征矩阵，其中 $x_i, (i = 1,2,\cdots,n)$ 表示第 $i$ 个节点的特征（此时 $\mathbf{x}_i$ 是 $m$ 维向量）。而节点之间的关系由邻接矩阵 $A$ 表征。

有了特征矩阵 $X$ 和邻接矩阵 $A$ ，我们可以使用数学语言描述GNN是如何工作的了。

就像普通的神经网络除最后输出层之外的隐藏层输出一样，GNN试图去学习每一个节点 $i$ 的 $s$ 维嵌入(embedding) $\mathbf{h}_i \in \mathbb{R}^s$ ，使得 $\mathbf{h}_i$ 编码了每一个节点的邻居节点的信息，记 $\mathbf{o}_i$ 为 $\mathbf{h}_i$ 的输出。

我们仿照Scarselli et al. (2009)绘制了下图，来示意GNN是如何工作的。

在照Scarselli et al. (2009)中，Vanilla GNN用于处理无向同质图，每一个节点由特征 $x_i$ 表征，同时每一条边也有自己的特征。

定义一个含参函数 $f$ ，称作local transition function，用于表示节点和它邻居节点的依赖关系。原文中使用 $v$ 代表节点， $co[v]$ 表示与节点 $v$ 相连的边， $ne[v]$ 表示节点 $v$ 的邻居节点。 $\mathbf{x}_v$ 表示节点 $v$ 的特征， $\mathbf{x}_{co[v]}$ 表示与节点 $v$ 相连边的特征， $\mathbf{x}_{ne[v]}$ 表示节点 $v$ 的邻居节点的特征， $\mathbf{h}_{ne[v]}$ 节点 $v$ 的邻居节点的嵌入。则节点 $v$ 的嵌入为：

$\mathbf{h}_v = f(\mathbf{x}_v, \mathbf{x}_{co[v]}, \mathbf{h}_{ne[v]}, \mathbf{x}_{ne[v]})$

有了嵌入之后，再定义一个含参的函数 $g$ ，称作local output function，用于根据节点特征以及节点嵌入来产生输出 $\mathbf{o}_v$ ，即：

$\mathbf{o}_v = g(\mathbf{h}_v, \mathbf{x}_v)$

为简便起见，我们对原文所使用的符号做一些改动，在不致引起混淆的情况下，我们使用 $x_i$ 来表示节点 $i$
以及节点 $i$ 的特征，也就是我们说，节点 $x_i$ 的特征为 $x_i$ ，将两个节点 $x_i, x_j$ 的连边使用 $e_{(i,j)}$ 来表示。

我们以节点 $x_1$ 作为示例，看看与之相关的节点和连边，也就是上图蓝色虚线框住的部分。

$co[x_1]$ 包含 $e_{(1,2)},e_{(3,1)},e_{(1,4)},e_{(1,5)}$ ， $ne[x_1]$ 包括 $x_2, x_3, x_4, x_5$ 。

我们将上述过程以向量形式写出。之前定义的 $f,g$ 称作local function，也就是考虑局域节点的函数，当考虑向量形式，也就是将所有节点统一考虑，需要重新定义对应函数，以考虑全局节点的函数， $F ,G$ 分别称为global transition function和global output function，同时有：

$\mathbf{H} = F(\mathbf{H}, \mathbf{X})\\ \mathbf{O} = G(\mathbf{H}, \mathbf{X}_N)$

其中 $\mathbf{H}$ 表示节点嵌入， $\mathbf{X}$ 表示全部特征，包括节点特征和连边特征， $\mathbf{O}$ 表示所有输出， $\mathbf{X}_N$ 表示所有节点的特征。

Vanilla GNN的数学机制

根据巴拿赫不动点定理（请参照图神经网络基础篇(1)中相关介绍），我们可以把 $\mathbf{H}$ 写成迭代形式，来嵌入到GNN中进行迭代，即：

$\mathbf{H}^{t+1} = F(\mathbf{H}^t, \mathbf{X})$

只要 $F$ 是一个压缩映射，经过不断迭代后， $\mathbf{H}$ 会收敛到一个固定点，这个点就是不动点。那么我们怎么保证 $F$ 是一个压缩映射呢？

我们先从度量空间的压缩映射定义出发：

$d(T(x),T(y)) \le kd(x,y)$

其中 $k < 1$ ，我们使用范数 $||x-y||$ 表示在度量空间中 $x,y$ 的距离，则上式整理得：

$\Vert T(x)-T(y)\Vert \le k\Vert x-y\Vert\\ \frac{\Vert T(x)-T(y)\Vert}{\Vert x-y\Vert} \le k\\ \frac{\Vert T(x)-T(x-\Delta x)\Vert}{\Vert\Delta x\Vert} \le k\\ \Vert T'(x)\Vert = \Vert\frac{\partial T(x)}{\partial x}\Vert \le k$

因此，映射 $T$ 为压缩映射的条件等价于 $T$ 的导数 $T'<1$ 。有了导数的关系，我们可以对雅可比矩阵的惩罚来实现，也就是 $F$ 对 $\mathbf{H}$ 的偏导数矩阵。

有了上式的迭代关系，我们可以在定义需要的损失函数后，使用梯度下降方法来训练GNN了。在通过有监督或者自监督的方法后，我们就获得了训练好的网络模型，这里面有个非常有用的副产物—节点嵌入向量 $\mathbf{h}_v$ ，这对于做一些下游分析极其重要。

Vanilla GNN 在面对结构化数据建立模型的方面具有很强大的能力，Vanilla GNN巧妙地将具有图拓扑结构的数据嵌入到神经网络训练的范畴。

一点点讨论

话说到这儿，小伙伴们就要知道下面要说什么了。没错，Vanilla GNN也有它的局限性。主要有如下几个：

假设我们训练Vanilla GNN $N$ 步，模型就需要迭代 $N$ 次来更新嵌入向量 $\mathbf{H}$ ，这无疑需要大量的计算。
Vanilla GNN在迭代时，使用相同的参数，而其他较为通用的多层神经网络，每一层的参数都互不相同，这便可在特征提取时提取到不同层级的特征。
在考虑连边信息的时候，比方在知识图谱中，不同的边需要有不同的类型，Vanilla GNN没有为边设定独立的参数，无法将连边特征有效地提取出来。
此外，如果训练步数 $N$ 过大，在大量计算的问题之外，当研究图表示理论的时候，不动点理论将不再适用。这是因为基于不动点的收缩，必然会导致节点之间对隐藏信息之间存在较多的信息共享，从而导致表示分布的过平滑，因此很难区分不同节点的信息。

为了解决这些局限性，基于Vanilla GNN的变体相继出现，我们将在后续章节深入探讨。

图神经网络基础篇(2)：原始图神经网络