图形神经网络(GNN )主要用于分子应用。 因为分子结构可以用图形结构表示。 GNN的有趣之处在于可以有效地对系统中对象之间的关系和交互进行建模。
近年来，图形神经网络(GNN )越来越广泛地应用于社交网络、知识地图、推荐系统甚至生命科学等各个领域。 GNN是对图表节点之间的依赖关系进行模型化的强大功能，突破了与图表分析相关的研究领域。 本文介绍了图形神经网络的基本原理和DeepWalk和GraphSage两种高级算法。
图(Graph)
在讨论GNN之前，让我们先了解一下什么是图。 在计算机科学中，图是由顶点和边两部分组成的数据结构。 图g可以用顶点集合v和其中包含的边e来记述。
根据顶点之间是否存在方向依赖关系，边可以是有向的也可以是无向的。
图1有向图
顶点也称为节点，本文中这两个术语可以互换。
图神经网络图神经网络是直接作用于图结构的神经网络。 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是第一个在没有监视的情况下学习的节点嵌入算法。 在训练过程中类似于词语的嵌入。 这样做的目的是使图的节点分布和语料库的单词分布都遵循幂律，如下图所示。
算法包括两个步骤。
1 .在图中节点上随机行走生成节点序列；
运行skip-gram，根据步骤1中生成的节点序列学习各节点的嵌入；
在随机行走过程中，从前一个节点的邻居统一采样下一个节点。 然后将每个序列截断为长度为2 | w | 1的子序列。 其中w表示skip-gram的窗口大小。 不熟悉skip-gram的人，在以前的博客文章中介绍了其结构。
在论文中，分层softmax用于解决因节点数量庞大而引起的softmax计算成本过高的问题。 要为每个单独的输出元素计算softmax值，必须为所有元素k计算ek。
图2 softmax的定义
因此，原始softmax的计算时间为O(|V|)。 其中v表示图表的顶点集。
多层softmax利用二叉树解决softmax计算成本问题。 在二叉树中，所有的叶节点〔上文所述的图的v1、v2、 v8〕是图的顶点。 在各内部节点(叶节点以外的节点，也就是分支节点)中，路径的选择由二元分类器决定。 为了计算给定顶点v_k的概率，可以简单地计算沿着从根节点到叶节点v_k的路径的每个子路径的概率。 由于每个节点的子节点的概率和为1，多层softmax保持了所有顶点的概率和为1的特性。 如果n是叶子的数量，二叉树的最长路径由o(log ) (n ) )规定，所以要素的计算时间的复杂度减少为o ) log|v|。
图3多层softmax
训练DeepWalk GNN后，模型学习了每个节点的表示，如下图所示。 不同的颜色在输入图(图a )中表示不同的标签。 在输出图表中，可以看到具有相同标签的节点聚集在一起，而具有不同标签的大多数节点都已正确隔离。
但是，DeepWalk的主要问题是泛化能力不足。 每次向图中添加新节点时，都必须重新训练模型以正确表示节点。 因此，这样的GNN不适用于图表中的节点不断变化的动态图表。
GraphSage GraphSage提供并总结了解决上述问题的解决方案
式学习每个节点的嵌入。具体来讲，它将每个节点用其邻域的聚合重新表示。因此，即使在训练期间未出现的新节点，也仍然可以由其相邻节点正确地表示。下图展示了GraphSage的算法过程：外层for循环表示更新迭代次数，而 h^k_v 表示节点v在迭代第 k次时的本征向量。在每次迭代时，将通过聚合函数，前一次迭代中v和v领域的本征向量以及权重矩阵W^k来更新h^k_v。这篇论文提出了三种聚合函数：
1.均值聚合器：
均值聚合器取一个节点及其邻域的本征向量的平均值。
与原始方程相比，它删除了上述伪代码中第5行的连接操作。这种操作可以被视为"skip-connection" ("跳连接")，这篇论文后面将证明其可以在很大程度上提高模型的性能。
2. LSTM聚合器：
由于图中的节点没有任何顺序，因此他们通过互换这些节点来随机分配顺序。
3.池聚合器：
此运算符在相邻顶点集上执行逐元素池化函数。下面显示了最大池的例子：
可以用平均池或任何其他对称池函数替换这种最大池函数。尽管均值池和最大池聚合器性能相似，但是池聚合器（也就是说采用最大池函数）被实验证明有最佳的性能。 论文使用max-pooling作为默认聚合函数。损失函数定义如下：
其中u 和v 共同出现在一定长度的随机游走中，而 v_n 是不与u共同出现的负样本。这种损失函数鼓动节点在投影空间中更靠近嵌入距离更近的节点，而与那些相距很远的节点分离。通过这种方法，节点将获得越来越多其邻域的信息。
GraphSage通过聚合其附近的节点，可以为看不见的节点生成可表示的嵌入位置。它让节点嵌入的方式可以被应用于涉及动态图的研究领域，这类动态图的图的结构是可以不断变化的。例如，Pinterest采用了GraphSage的扩展版本PinSage作为他们的内容探索系统的核心。