新智元报道
来源：towardsdatascience
作者：黃功詳SteeveHuang编辑：肖琴
图神经网络(GNN)在各个领域越来越受欢迎，本文介绍了图神经网络的基本知识，以及两种更高级的算法：DeepWalk和GraphSage。
最近，图神经网络(GNN)在各个领域越来越受到欢迎，包括社交网络、知识图谱、推荐系统，甚至生命科学。
GNN在对图形中节点间的依赖关系进行建模方面能力强大，使得图分析相关的研究领域取得了突破性进展。本文旨在介绍图神经网络的基本知识，以及两种更高级的算法：DeepWalk和GraphSage。
图(Graph)
在讨论GNN之前，让我们先了解一下什么是图(Graph)。在计算机科学中，图是由两个部件组成的一种数据结构：顶点(vertices)和边(edges)。一个图G可以用它包含的顶点V和边E的集合来描述。
边可以是有向的或无向的，这取决于顶点之间是否存在方向依赖关系。
一个有向的图(wiki)
顶点通常也被称为节点(nodes)。在本文中，这两个术语是可以互换的。
图神经网络
图神经网络是一种直接在图结构上运行的神经网络。GNN的一个典型应用是节点分类。本质上，图中的每个节点都与一个标签相关联，我们的目的是预测没有ground-truth的节点的标签。
本节将描述Thegraphneuralnetworkmodel(Scarselli,F.,etal.,)[1]这篇论文中的算法，这是第一次提出GNN的论文，因此通常被认为是原始GNN。
在节点分类问题设置中，每个节点v的特征x_v与一个ground-truth标签t_v相关联。给定一个部分标记的graphG，目标是利用这些标记的节点来预测未标记的节点的标签。它学习用包含邻域信息的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都可以解释为前馈全连接神经网络。L1loss可以直接表述为：
可以通过梯度下降进行优化。
然而，原始GNN存在三个主要局限性：
如果放宽“不动点”(fixedpoint)的假设，那么可以利用多层感知器学习更稳定的表示，并删除迭代更新过程。这是因为，在原始论文中，不同的迭代使用转换函数f的相同参数，而MLP的不同层中的不同参数允许分层特征提取。它不能处理边缘信息(例如，知识图中的不同边缘可能表示节点之间的不同关系)不动点会阻碍节点分布的多样性，不适合学习表示节点。
为了解决上述问题，研究人员已经提出了几个GNN的变体。不过，它们不是本文的重点。
DeepWalk：第一个无监督学习节点嵌入的算法
DeepWalk[2]是第一个提出以无监督的方式学习节点嵌入的算法。
它在训练过程中非常类似于词汇嵌入。其动机是graph中节点和语料库中单词的分布都遵循幂律，如下图所示：
该算法包含两个步骤：
在graph中的节点上执行randomwalks，以生成节点序列运行skip-gram，根据步骤1中生成的节点序列，学习每个节点的嵌入
在randomwalks的每个时间步骤中，下一个节点从上一个节点的邻节点均匀采样。然后将每个序列截断为长度为2
w
+1的子序列，其中w表示skip-gram中的窗口大小。
本文采用hierarchicalsoftmax来解决由于节点数量庞大而导致的softmax计算成本高昂的问题。为了计算每个单独输出元素的softmax值,我们必须计算元素k的所有e^xk。
Softmax的定义
因此，原始softmax的计算时间为O(
V
)，其中V表示图中顶点的集合。
分层softmax利用二叉树来处理这个问题。在这个二叉树中，所有的叶子(下图中的v1,v2，…v8)都表示graph中的顶点。在每个内部节点中，都有一个二元分类器来决定选择哪条路径。要计算给定顶点v_k的概率，只需计算从根节点到叶节点v_k路径上每一个子路径的概率。由于每个节点的子节点的概率之和为1，所以所有顶点的概率之和为1的特性在分层softmax中仍然保持不变。由于二叉树的最长路径是O(log(n))，其中n表示叶节点的数量，因此一个元素的计算时间现在减少到O(log
V
)。
HierarchicalSoftmax
在训练完DeepWalkGNN之后，模型已经学习了每个节点的良好表示，如下图所示。不同的颜色表示输入图中的不同标签。我们可以看到，在输出图(2维嵌入)中，具有相同标签的节点被聚集在一起，而具有不同标签的大多数节点都被正确地分开了。
然而，DeepWalk的主要问题是缺乏泛化能力。每当一个新节点出现时，它必须重新训练模型以表示这个节点。因此，这种GNN不适用于图中节点不断变化的动态图。
GraphSage：学习每个节点的嵌入
GraphSage提供了解决上述问题的办法，以一种归纳的方式学习每个节点的嵌入。
具体地说，GraphSage每个节点由其邻域的聚合(aggregation)表示。因此，即使图中出现了在训练过程中没有看到的新节点，它仍然可以用它的邻近节点来恰当地表示。
下面是GraphSage算法：
外层循环表示更新迭代的数量，而h^k_v表示更新迭代k时节点v的潜在向量。在每次更新迭代时，h^k_v的更新基于一个聚合函数、前一次迭代中v和v的邻域的潜在向量，以及权重矩阵W^k。
论文中提出了三种聚合函数：
1.Meanaggregator：
meanaggregator取一个节点及其所有邻域的潜在向量的平均值。
与原始方程相比，它删除了上面伪代码中第5行中的连接运算。这种运算可以看作是一种“skip-connection”，在论文后面的部分中，证明了这在很大程度上可以提高模型的性能。
2.LSTMaggregator：
由于图中的节点没有任何顺序，因此它们通过对这些节点进行排列来随机分配顺序。
3.Poolingaggregator：
这个运算符在相邻集上执行一个element-wise的pooling函数。下面是一个max-pooling的示例：
论文使用max-pooling作为默认的聚合函数。
损失函数定义如下：
其中u和v在固定长度的randomwalk中共存，而v_n是不与u共存的负样本。这种损失函数鼓励距离较近的节点具有相似的嵌入，而距离较远的节点则在投影空间中被分离。通过这种方法，节点将获得越来越多的关于其邻域的信息。
GraphSage通过聚合其附近的节点，可以为看不见的节点生成可表示的嵌入。它允许将节点嵌入应用到涉及动态图的域，其中图的结构是不断变化的。例如，Pinterest采用了GraphSage的扩展版本PinSage作为其内容发现系统的核心。
总结
本文中，我们学习了图神经网络、DeepWalk和GraphSage的基础知识。GNN在复杂图结构建模方面的强大功能确实令人惊叹。鉴于其有效性，我相信在不久的将来，GNN将在AI的发展中发挥重要作用。
[1]Scarselli,Franco,etal.Thegraphneuralnetworkmodel.”