简单理解图神经网络 GNN

前言

图神经网络（Graph Neural Networks，GNN）最早由The Graph Neural Network Model(Gori et al., 2005)提出。近年来，深度学习领域关于图神经网络的研究热情日益高涨，图神经网络已经成为各大深度学习顶会的研究热点。

本文主要介绍图神经网络的基本原理，通过简单的方式理解 GNN, GCN 是如何工作的，尽量把原理说清楚。

Overview

总的来说，GNN 就是做了这么一件事情：利用图的节点信息去生成节点（图）的 Embedding 表示。

Graph Neural Network(GNN)

既然是 Graph，那么我们的数据就是一张图：

其中 $h_A, h_B, h_C, h_D, h_E$ 分别是节点 $A, B, C, D, E$ 的所包含的信息，你也可以简单理解为是这个节点的特征。

GNN 可分为三步：1. 聚合；2. 更新；3. 循环。

首先是聚合。通过观察上面的图我们可以发现，节点 $A$ 有三个邻居节点 $B,C,D$ ，显然这是一个非常重要的信息，节点 $A$ 与这三个节点有密切的联系。举个例子，如果我们不知道节点 $A$ 是否有钱，但是我们发现节点 $B,C,D$ 都非常有钱，那么很大程度上节点 $A$ 也非常有钱，也就是通过节点的邻居信息判断这个节点的信息。那么要如何利用这个特征呢？

就像在一开始说的，GNN 就是利用图的节点信息去生成节点（图）的 Embedding 表示，这也就是聚合。我们可以通过简单的方式获取邻居的信息：

$\begin{aligned}N_A &= a \cdot h_B + b \cdot h_C + c \cdot h_D \\ &= a \cdot (2,2) + b \cdot (3,3) + c \cdot (4,4) \end{aligned}$

其中 $a,b,c$ 为常数，也可以通过训练得到或者是手动设定，我们这里简单理解为常数。

好了，通过上面的简单的方式，我们得到了节点 $A$ 的邻居的信息，我们将这个信息作为节点 $A$ 信息的补充。

再来是更新。当我们获取了邻居的信息后，自然也不能忘了节点 $A$ 本身的信息：

$(h_A + \alpha \cdot N_A)$

其中 $\alpha$ 为常数（同样也可以通过训练得到或者是手动设定，这里简单理解为常数）。当然了，肯定不能直接简单加起来就作为节点 $A$ 的新的信息，而是需要进行一些处理，其实也就是常规的线性变换，再过个激活函数：

$\begin{aligned}h_A = \sigma (W (h_A + \alpha \cdot N_A)) \end{aligned}$

其中 $\sigma$ 为激活函数， $W$ 为权重矩阵， $h_A$ 为节点 $A$ 的信息， $N_A$ 为节点 $A$ 的邻居信息。

简而言之，聚合更新就是把节点的邻居的信息添加到这个节点中。

现在，一次聚合操作就完成了，经过一次聚合之后：

节点 $A$ 中有 $B,C,D$ 的信息；
节点 $B$ 中有 $A,C$ 的信息；
节点 $C$ 中有 $A,B,D,E$ 的信息；
节点 $D$ 中有 $A,C$ 的信息；
节点 $E$ 中有 $C$ 的信息；

第二次聚合也是类似的，仍然以节点 $A$ 为例，计算节点 $A$ 的邻居信息。但此时当节点 $A$ 聚合节点 $C$ 的时候，由于节点 $C$ 中包含了节点 $E$ 的信息，所以这时节点 $A$ 获得了二阶邻居 $E$ 的信息。

归根结底，GNN 就是一个提取特征的方法。

Graph Convolutional Network(GCN)

好了，讲完了 GNN 的总体思路，让我们具体来看看 GCN 是怎么做的。还是以下面这幅图为例:

同样的，我们需要获取节点 $A$ 的邻居信息:

$\begin{aligned}N_A &= a \cdot h_B + b \cdot h_C + c \cdot h_D \\ &= a \cdot (2,2) + b \cdot (3,3) + c \cdot (4,4) \end{aligned}$

这里我们使用矩阵的方式来表示图，邻接矩阵 $A$ ，以及隐藏层矩阵 $H$ 。

$A = \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} \quad H = \begin{bmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \end{bmatrix}$

这里假设 $a=b=c=1$ ，那么，节点 $A$ 的邻居信息就可以表示为：

$\begin{aligned} N_A &= \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \end{bmatrix} = \begin{bmatrix}9 & 9\end{bmatrix} \\ &= A_{0,*}H \end{aligned}$

其中 $A_{0,*}$ 表示矩阵 $A$ 的第一行，即节点 $A$ 的邻居关系。另外别忘了加上节点 $A$ 自身的信息，具体来说，可以通通过加上单位矩阵 $I$ 的方式实现：

$\begin{aligned} N_A &= \left( \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \end{bmatrix} + \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \end{bmatrix}\right) \begin{bmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \end{bmatrix} = \begin{bmatrix}10 & 10\end{bmatrix} \\ &= (A_{0,*} + I_{0,*})H \end{aligned}$

同理，我们可以得到所有节点的邻居信息 $N$ :

$\begin{aligned}N &= (A + I)H \\ &:= \tilde{A}H \end{aligned}$

记 $\tilde{A} = A + I$

现在，就可以写出隐藏层的更新方程了，与之前的思路类似，常规的线性变换，再过个激活函数：

$H^{(l+1)} = \sigma (\tilde{A}H^{(l)}W^{(l)})$

其中 $l$ 为循环层数， $\sigma$ 为激活函数， $W$ 为隐藏层的权重矩阵。

现在还有最后一个问题，你会发现，现在我们的矩阵 $\tilde{A}$ 中，非零元素均为 $1$ ，即简单的将当前节点的邻居信息相加，可以想象的是它会越来越「膨胀」。

$\tilde{A} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}$

实际上，解决这个问题并不麻烦，归一化就行了。在图 Graph 中，我们可以借助「度」来进行归一化。具体为什么这么做、为什么要进行归一化我们放在后面讲：关于归一化的一些问题。

具体什么是度这里就不赘述了，给出度矩阵：

$D = \begin{bmatrix} 3 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \quad \tilde{D} = \begin{bmatrix} 4 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{bmatrix}$

其中， $D,\tilde{D}$ 分别是 $A,\tilde{A}$ 的度矩阵。

这里直接给出 GCN 论文 Semi-Supervised Classification with Graph Convolutional Networks 中的归一化方法，它的本质是对称归一化的拉普拉斯矩阵：

$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$

关于上面的归一化方法，我们同样在后面具体讨论：关于归一化的一些问题，如果你不想了解细节也没关系，你只需要知道它的作用即可。

至此为止，我们可以得到完整的隐藏层的更新方程：

$H^{(l+1)} = \sigma (\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$

其中 $l$ 为循环层数， $\sigma$ 为激活函数， $W$ 为隐藏层的权重矩阵， $\tilde{A} = (A + I)$ ， $\tilde{D}$ 是 $\tilde{A}$ 的度矩阵。虽然式子长得难看了点，但我想如果你了解了上面讲的内容，也就不难理解了。

关于归一化的一些问题

现在，让我们回到上面没解决的问题：

为什么要进行归一化？
论文中为什么使用 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 进行归一化？

问题一

首先，为什么要进行归一化？这个问题其实在上面也有简单的解释。矩阵 $\tilde{A}$ 中，非零元素均为 $1$ ，那么这就意味着，在计算 $\tilde{A}H$ 时，就是简单的将当前节点的邻居信息相加，各个邻居一视同仁。

问题二

归一化

一个直观的归一化方法是：平均化聚合每个节点的信息。

$\tilde{A} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \quad \rightarrow \quad \begin{bmatrix} 1/4 & 1/4 & 1/4 & 1/4 & 0 \\ 1/3 & 1/3 & 1/3 & 0 & 0 \\ 1/5 & 1/5 & 1/5 & 1/5 & 1/5 \\ 1/3 & 0 & 1/3 & 1/3 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \end{bmatrix} =\tilde{D}^{-1}\tilde{A}$

其中， $\tilde{D}^{-1}$ 是 $\tilde{A}$ 的度矩阵的逆。从数学的角度，上面的平均化也就是 $\tilde{D}^{-1}\tilde{A}$ 的过程。现在我们已经将求和变成了加权平均，权值之后归一化为 $1$ 了。

对称归一化

那么为什么不直接使用简单的平均化方法呢？第一个缺点就是 $\tilde{D}^{-1}\tilde{A}$ 不再是对称矩阵了，这不是我们想要看到的。

第二个缺点我们来看一个比较特殊的例子，在下面这幅图中，我们发现节点 $A$ 只有一个邻居节点 $C$ ，另一方面节点 $C$ 有着包括 $A$ 在内的 6 个邻居节点。

按照上面的平均化思路，当节点 $A$ 聚合节点 $C$ 时，节点 $C$ 所有的特征会完全加到节点 $A$ 上，但实际上，节点 $A$ 和节点 $C$ 的差距是很明显的。举个例子，节点 $A$ 是我，节点 $C$ 是老板，老板管着一票人，我只是一个苦命的打工人，不可能说把老板的工资完全加到我身上，然后我拿着一半我的工资，一半老板的工资，美滋滋。

那么一个科学的方法就是同时考虑节点 $A$ 和 $C$ 的邻居数量，即「度」，具体来说，可以考虑几何平均数 $\sqrt{\tilde{D}_{ii} \tilde{D}_{jj}}$ ，回到 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ ：

$\begin{aligned} (\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H)_i &= (\tilde{D}^{-1/2}\tilde{A})_i \tilde{D}^{-1/2}H \\ &= \left( \sum_k \tilde{D}_{ik}^{-1/2}\tilde{A}_i \right) \tilde{D}^{-1/2}H \\ &= \tilde{D}_{ii}^{-1/2} \sum_j \tilde{A}_{ij} \sum_k \tilde{D}_{jk}^{-1/2} H_j \\ &= \tilde{D}_{ii}^{-1/2} \sum_j \tilde{A}_{ij} \tilde{D}_{jj}^{-1/2} H_j \\ &= \sum_j \frac{1}{\sqrt{\tilde{D}_{ii} \tilde{D}_{jj}}} \tilde{A}_{ij} H_j \end{aligned}$

不考虑复杂的推导过程，只看结论，论文中的对称归一化方法就是使用了上面说的结论，同时考虑两个节点的邻居数量。那么，前面的例子就变成了：

$\begin{aligned} \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} &= \begin{bmatrix} \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{5}} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{3}} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{5}} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{3}} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} \end{bmatrix}\\ &= \begin{bmatrix} \frac{1}{4} & \frac{1}{2\sqrt{3}} & \frac{1}{2\sqrt{5}} & \frac{1}{2\sqrt{3}} & 0 \\ \frac{1}{2\sqrt{3}} & \frac{1}{3} & \frac{1}{\sqrt{15}} & 0 & 0 \\ \frac{1}{2\sqrt{5}} & \frac{1}{\sqrt{15}} & \frac{1}{5} & \frac{1}{\sqrt{15}} & \frac{1}{\sqrt{10}} \\ \frac{1}{2\sqrt{3}} & 0 & \frac{1}{\sqrt{15}} & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{\sqrt{10}} & 0 & \frac{1}{2} \end{bmatrix} \end{aligned}$