关于人工智能:图嵌入中节点如何映射到向量

所有的机器学习算法都须要输出数值型的向量数据，图嵌入通过学习从图的结构化数据到矢量示意的映射来取得节点的嵌入向量。它的最根本优化办法是将具备类似上下文的映射节点凑近嵌入空间。咱们能够应用两种正交办法（同质性和构造等效性）之一或它们的组合来定义图中节点的上下文。

图数据库和机器学习

图数据库能够反对来自各种起源的互相关联数据的大数据利用。它们容许应用一种简洁的查询语言来剖析数据中的简单关系模式，例如 PageRank、核心性检测、链接预测、模式识别等算法能够用简略直观的形式来表述。

大多数成熟的传统机器学习算法，如线性和逻辑回归、神经网络等，都是在数值向量示意上工作的。为了将图数据库和和机器学习联合就须要一种办法来以向量模式示意咱们的数据网络。图嵌入就是从图中的数据中精确学习这种映射的一种模式。

图嵌入的目标

图嵌入的指标是找到图中每个节点的向量示意，该向量的映射代表节点的网络结构，而不是思考节点的相干特色。换句话说，一个节点的嵌入向量应该基于它的关系和相邻节点。图构造中类似的节点应在向量空间中严密映射。咱们将节点映射到的向量空间称为嵌入空间。

下面的形容中有两个问题须要额定思考：

• 图中的两个节点类似怎么判断？
• 嵌入空间中的“严密”是什么意思？

网络中的类似节点

为了具体阐明图中的相似性，临时思考一个句子：

句子能够被了解为是一个单词的序列，每个单词都有一个确定的地位。因而，一个句子中的一个词恰好有一个先人和一个后继。要定义句子中单词的上下文，能够应用围绕它的单词。例如，单词“capital”的间隔一上下文是单词“the”和“of”。间隔二的上下文是“is”、“the”、“of”、“Germany”。这被称为 n-gram 模型，也就是 word2vec 嵌入应用的办法。

与 n -gram 相似咱们能够在图中定义节点的上下文，并且在图构造中比在单词序列中有更多的抉择。因为在个别的图中每个节点可能连贯到两个以上的其余节点——而在一个句子中，一个单词只有一个间接先人和后续节点。

一个句子是一个向量，能够通过沿着索引轴挪动来摸索单词的上下文。图被形容为一个二维邻接矩阵，节点的间接先人是一个向量。在每个间隔级别上摸索节点的上下文有多个抉择，必须决定如何遍历这些抉择。

一般来说，摸索网络上下文有两种正交办法：

宽度优先: 在 (可能) 挪动到间隔为 2 的节点之前，咱们首先具体阐明源节点的间接街坊。这也被称为同质性，源于一个社会学概念，即人们通常偏向于与类似的人亲密互动。因而它是基于图中类似节点关系密切的假如。

深度优先: 首先通过从源节点开始到其深度的门路来摸索一个连贯链，而后再持续下一个。与同质性相同，这个度量从更宽泛的角度捕获网络中节点的角色。不是着眼于亲密的关系，而是寻找节点的构造角色: 例如，它是如何嵌入到更大的社区环境中。这个度量称为构造等价。

能够应用这两种办法来查找节点的上下文——也能够将它们组合在一起。领有一组形容每个节点上下文的节点，能够应用这些节点来比拟每对节点的上下文相似性。例如，能够利用 Jaccard 相似性来度量两个上下文重叠的水平。这将为咱们提供一种在图中找到具备类似网络结构的节点的办法。

上下文的抽样

然而有可能不能采样给定节点的整个上下文，因为这最终会导致捕捉整个图。因而采纳了一种近似的抽样策略。其思维是在源顶点中开始固定数量的随机游走，并摸索其上下文生成一个随机样本。node2vec 定义的抽样策略联合了同质性和构造等价性。它蕴含了决定在游走的每一步中，是应该放弃在源节点左近 (同质性)，还是应该摸索另一个间隔程度(构造等效) 的参数。

在 node2vec 中，没有应用后面形容的 Jaccard 相似性，而是尝试为每个节点找到一个数值向量。利用图中节点的采样上下文优化映射函数将具备类似上下文的节点映射到一起。

node2vec 的数学原理

通过上面的例子来具体理解 node2vec 是如何工作的:

V: 图中所有节点
N_S(u): 由样本策略 S 确定的 u 的邻域
F (u): 节点 u 到向量的映射函数

指标是找到 V 中所有节点 u 的嵌入，使具备类似上下文的节点的向量示意在嵌入空间中靠近。尽管曾经晓得图中的类似上下文意味着什么，但依然须要定义嵌入空间中的“靠近”是如何示意的。

当初只思考图中的两个节点:

u: 源节点
V: u 上下文中的节点

为了开始数学原理的介绍，简略地抉择两个随机向量 f(u)，f(v)作为两个节点。度量嵌入空间中的相似性，须要应用两个向量的点积，也就是它们之间的夹角。

因为节点 v 在 u 的左近，所以能够逐渐优化映射函数 f，以使它们的相似性最大化。

为了将相似性转化为概率，须要对其利用 softmax。softmax 将类似度得分 dot(f(u), f(v)) 归一化为 u 与 V 中所有其余向量 v 的所有类似度之和。因而点积被转换为 [0,1] 之间的数字 并且所有相似性加起来就是 1，后果就是从向量示意中在节点 u 的上下文中看到节点 v 的概率。当初，能够通过应用随机梯度降落更新咱们的向量 f(u) 来逐渐优化这个概率。

下一步是推广这个概念，不仅对 N_S(u) 中的一个节点 v 进行优化，而且对 u 上下文中的所有节点进行优化。如果给定节点 u，心愿能够优化看到的整个采样上下文的概率。如果假如样本是独立的，能够将这个公式简化为简略概率的乘积。

要学习图中每个源节点 u 的映射，须要将公式同时利用于图的所有节点。应用 SGD 通过调整映射 f 来优化总和，从而减少概率。通过屡次迭代直到达到最大迭代次数或在优化问题中找到一个固定点。

补充阐明

该解决方案在大型数据集上运行时存在一个次要挑战是：当计算 softmax 以确定概率 P(f(v) | f(u)) 时，分母中的归一化项很难计算。这个归一化项是 u 和图中所有其余节点的所有相似性的总和。它在优化的整个迭代中放弃固定，因而对于源节点 u 的总和的所有迭代也是固定的。

另外一个挑战是：在所有向量上计算这样一个因子十分低廉。在每次迭代中，咱们必须确定每个源节点 u 与图中所有其余向量的点积，才可能找到归一化因子。为了克服这个问题，一种称为负采样的技术被用来近似这个因素。

边嵌入

上述办法也能够利用于不同的根本假如：咱们还能够设置不同的指标，将边缘映射到嵌入空间，通过使这些边缘靠近共享雷同的节点，而不是找到具备类似上下文的节点的映射。联合 node2vec 中的节点和边嵌入，能够推导出更通用图嵌入，它可能将互相关联的数据映射到向量示意。

总结

本文介绍了如何找到映射 f(u) 以将图的节点映射到向量空间，从而使类似的节点靠近。有多种办法能够定义图上下文中节点的相似性：同质性和构造等效性，两者都具备正交办法并且 node2vec 定义了将两者组合成参数化采样策略的。

采样策略是一种查找节点上下文的办法，嵌入空间中的相似性顺次定义为两个映射向量之间的点积。嵌入自身是应用随机梯度降落的迭代优化。它在每次迭代中调整所有节点的向量，以最大化从同一上下文中看到节点的概率。十分大的数据集的实现和利用须要一些统计近似来减速计算。

node2vec: Scalable Feature Learning for Networks. A. Grover, J. Leskovec. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016.

https://www.overfit.cn/post/4012a7b482bf477283c84fd0ec61c388

作者：Philipp Brunenberg