汇编：

介绍

我将向您介绍最受欢迎的图形神经网络，包括基础知识和两种常用算法，以及。

近年来，图形神经网络（GNN）越来越广泛地用于社交网络，知识图，推荐系统甚至生命科学等各个领域。 GNN具有建模图中的节点依赖性的强大功能，该图在与图分析有关的研究字段中取得了突破。本文将介绍图形神经网络的基本原理，以及两个更高级的算法。

图片

在讨论GNN之前，让我们了解是什么。在计算机科学中，图是由两个部分组成的数据结构：顶点和边缘。图G可以通过它包含的顶点V和边缘E进行很好的描述。

取决于顶点之间是否存在方向依赖性，边缘可以定向或无方向性。

定向图

这些顶点通常称为节点。在本文中，这两个术语是可以互换的。

图神经网络

图神经网络是直接作用于图形结构的神经网络。 GNN的典型应用是节点分类。本质上，图中的每个节点都与标签关联，我们希望预测没有 - 的节点的标签。本节将说明本文所述的算法。第一个提议的GNN通常称为原始GNN。

在节点分类问题设置中，每个节点V均以X_V为特征，并与A -TAG T_V相关联。给定部分标记的图G，目标是使用这些标记的节点来预测未标记的标签。它学会了用D维矢量（状态）H_V表示每个节点，其中包含有关其邻域的信息。具体来说，

其中x_co [v]表示连接到v的边缘的特征，h_ne [v]表示与v相邻的节点的嵌入，而x_ne [v]表示与v。相邻的节点的特征是v。函数f是一个转换函数这些输入到D维空间中。因为我们正在寻找H_V的唯一解决方案，所以我们可以应用定理定理并重写上述方程式作为迭代更新过程。这种操作通常称为消息传递或邻居聚合。

H和X分别代表所有H和X的级联反应。

GNN的输出是通过将状态H_V传递和功能X_V到输出函数g来计算的。

F和G这里都可以解释为完全连接的神经网络。 L1损失可以直接表示为：

它可以通过梯度下降来优化。

但是，一些文章指出，这种原始方法的GNN有三个主要局限性：

如果放松“解开点”的假设，则可以使用多层感知器来学习更稳定的表示并消除迭代更新过程。这是因为，在原始方案中，不同的迭代使用转换函数f的相同参数，而MLP不同层中的不同参数允许层次特征提取。

它无法处理边缘信息（例如，知识图中的不同边缘可能代表节点之间的不同关系）

一个固定点阻碍了节点分布的多元化，可能不适合学习代表节点。

已经提出了几种GNN的变体来解决上述问题。但是，它们没有被覆盖，因为它们不是本文的重点。

这是第一种提出无监督的学习节点嵌入的算法。就培训过程而言，它与单词嵌入非常相似。动机是，图中的节点和语料库中单词的分布遵循了幂律，如下图所示：

该算法由两个步骤组成：

在图中的节点上进行随机步行以生成一系列节点

根据步骤1中生成的节点序列，运行跳过以学习每个节点的嵌入

在随机步行的每个时间步骤中，下一个节点均匀地从上一个节点的邻居中进行示例。然后将每个序列截断为长2 | w | +1的子序列，其中w表示跳过的窗口大小。

本文使用分层算法来解决大量节点和大量计算的问题。要计算每个单独的输出元素的值，我们必须计算所有元素k的所有e xk。

因此，原始计算时间为o（| v |），其中v表示图中的一组顶点。

层次结构使用二进制树来解决此问题。在这个二进制树中，所有叶子（上图中的V1 V2…V8）都是图中的顶点。在每个内部节点中，都有一个二进制分类器来决定选择哪种路径。要计算给定顶点V_K的概率，只需计算从根节点到左节点的路径上每个子路径的概率V_K即可。由于每个节点的子女的概率之和是1，因此所有顶点的概率之和等于1在层次结构中仍然是真实的。现在，元素的计算时间缩短为O（log | v |），因为二进制树的最长路径由O（log（log（n））界定，其中n是叶子的数量。

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

但是，主要问题是它缺乏泛化能力。每当出现新节点时，它都必须重新训练模型以表示该节点。因此，该GNN不适合在图中不断变化的节点变化的动态图。

提供了上述问题的解决方案，以以归纳方式学习每个节点的嵌入。具体而言，每个节点都由其社区的聚合表示。因此，即使在训练过程中未出现的新节点出现在图中，它们也可以由相邻节点表示。以下是算法。

外循环表示更新的次数，而H^k_v表示更新迭代期间节点V的隐藏向量k。在每次更新迭代中，H^k_v根据聚合功能，上一个迭代中V和V社区的隐藏向量以及权重矩阵W^k进行更新。本文提出了三个汇总功能：

1。平均：

含义取得了节点及其所有邻居的隐藏向量的平均值。

与原始方程相比，它在上面的伪代码的第5行中删除了连接操作。该操作可以看作是“跳跃连接”，本文稍后将证明该连接大大提高了模型的性能。

2。LSTM：

由于图中的节点没有顺序，因此它们通过遍历这些节点来随机分配顺序。

3。：

该操作员在相邻集合上执行元素池函数。这是最大池的示例：

它可以用平均池或任何其他对称池功能替换。合并的聚合器具有最佳性能，而平均合并的聚合器和最大汇总聚合器的性能相似。本文使用max-作为默认聚合函数。

损失函数定义如下：

其中u和v以固定长度的随机摆动出现，而v_n是一个负面样本，与u并不出现在u中。此损耗函数鼓励对更紧密的节点进行类似的嵌入，而远处节点在投影空间中分开。这样，节点将获得有关其邻居的越来越多的信息。

通过汇总其附近的节点，为隐形节点生成了代表性的嵌入。它允许将节点嵌入应用于涉及动态图的字段，其中图的结构在不断变化。例如，所采用的扩展版本是内容发现系统的核心。

总结

您已经学习了图形神经网络的基础知识，并且。 GNN对复杂图结构进行建模的能力确实令人惊讶。鉴于其有效性，我相信在不久的将来，GNN将在人工智能的发展中发挥重要作用。

- 结尾-

原始英语：