简单的图神经网络介绍

最近，Graph Neural Network（GNN）在很多领域日益普及，包括社交网络、知识图谱、推荐系统甚至于生命科学。GNN在对节点关系建模方面表现十分突出，使得相关的研究领域取得了一定突破。本文旨在对GNN做一个简单的介绍，并介绍两种前沿算法，DeepWalk和GraphSage。

Graph

在学习GNN之前，先让我们了解一下什么是Graph。在计算机科学中，graph是一种数据结构，由两部分组成，顶点和边。图G可以通过顶点集V和边集E来描述：

根据顶点之间是否有方向，边可以分为无向和有向。

有向图

顶点又称节点，本文中两者可以互换。

Graph Neural Network

GNN是直接在图数据结构上运行的神经网络。GNN的典型应用便是节点分类。图中的每个节点都有一个标签，我们希望不需要标注数据，可以预测新的节点标签。本节将讲解论文《The graph neural network model》中的GNN算法，算得上第一个GNN。

在节点分类问题中，每个节点 v 的特征用 x v 表示，并且和标签 t v 相关联。给定部分标记的图 G ，目标是利用这些标记的节点来预测未标记节点的标签。网络学会用 d 维向量（状态） h v 表示每个节点，其中包含其邻域信息。

其中， x co[v] 表示与 v 连接的边的特征， h ne[v] 表示 v 的相邻节点嵌入特征， x ne[v] 表示 v 的相邻节点的特征。函数 f 是将这些输入投影到 d 维空间的传递函数。由于我们正在寻找 h v 的唯一解，可以应用Banach不动点定理并将上述等式重写为迭代更新过程。

H 和 X 分别表示所有 h 和 x 的连接。通过将状态 h v 以及特征 x v 传递给输出函数 g 来计算GNN的输出。

f 和这里的 g 都可以解释为前馈全连接神经网络。 L1损失可以直接表述如下：

再通过梯度下降优化。上述的GNN算法有三个限制：

1、如果放宽“固定点”的假设，可以利用多层感知机来学习更稳定的表示，并删除迭代更新过程。这是因为，在该提议中，不同的迭代使用传递函数f的相同参数，而不同MLP层中的不同参数允许分层特征提取。

2、它不能处理边信息（例如知识图中的不同边可能表示节点之间的不同关系）。

3、固定点可以阻止节点分布的多样化，因此可能不适合学习表示节点。

当然，已经有几种GNN的变体来解决上述问题，我在这里不展开讲解了。

DeepWalk

DeepWalk是以无监督的方式学习node embedding的算法。它的训练过程非常类似word embedding。动机是图表中的节点和语料库中的单词的分布遵循幂定律，如下图所示:

算法包括两个步骤：

1、在图中的节点上进行随机游走以生成节点序列；

2、使用skip-gram，根据步骤1中生成的节点序列学习每个节点的嵌入。

在随机游走的每个时间步骤，从前一节点的邻居统一采样下一个节点。然后将每个序列截短为长度为 2| w |+1 的子序列，其中 w 表示skip-gram中的窗口大小。

在提出DeepWalk的论文中，分层softmax用于解决由于节点数量庞大而导致的softmax计算成本高昂的问题。为了计算每个单独输出元素的softmax值，我们必须计算所有元素 k 的所有 e x k 。

因此，原始softmax的计算时间为O(|V|)，其中 V 表示图中的顶点集。

分层softmax利用二叉树来处理问题。在这个二叉树中，所有叶子（上图中的 v 1 ， v 2 ，...， v 8 ）都是图中的顶点。在每个内部节点中，有一个二元分类器来决定选择哪条路径。为了计算给定顶点 v k 的概率，可以简单地计算沿着从根节点到离开 v k 的路径中的每个子路径的概率。由于每个节点的子概率为1，因此所有顶点的概率之和等于1的特性仍然保持在分层softmax中。现在，元素的计算时间减少到O( log | V |)，因为二叉树的最长路径由O( log | n |)限定，其中是 n 叶子的数量。

分层Softmax

在训练DeepWalk GNN之后，模型已经学习了每个节点的良好表示，如下图所示。不同的颜色表示输入图中的不同标签。我们可以看到，在输出图形（嵌入2维）中，具有相同标签的节点聚集在一起，而具有不同标签的大多数节点被正确分开。

然而，DeepWalk的主要问题是缺乏泛化能力。每当有新节点加入时，它必须重新训练模型以表示该节点。因此，这种GNN不适用于图中节点不断变化的动态图。

GraphSage

GraphSage提供解决上述问题的方案，以归纳方式学习每个节点的嵌入。具体而言，每个节点由其邻域的聚合表示。因此，即使在训练时间内看不到的新节点出现在图中，它仍然可以由其相邻节点正确地表示。下面显示了GraphSage的算法。

可以用mean-pooling或任何其他对称池化函数替换。文章指出pooling aggregator执行最佳，而mean-pooling和max-pooling具有相似的性能。本文使用max-pooling作为默认聚合函数。

损失函数定义如下：

其中 u 和 v 共同出现在固定长度的随机游走中，而 v n 是不与 u 共同出现的负样本。这种损失函数鼓励具有类似嵌入的节点更接近，而那些相距很远的节点在投影空间中分离。通过这种方法，节点将获得越来越多关于其邻域的信息。

GraphSage通过聚合其附近的节点，可以为看不见的节点生成可表示的嵌入。它允许将节点嵌入应用于涉及动态图的域，其中图的结构不断变化。例如，Pinterest采用了GraphSage的扩展版本PinSage作为其内容发现系统的核心。

总结