我们研究 Graph Embedding 的初衷是为旺铺模块千人千面场景提供覆盖率高的 Match 支持。因为用户在店铺内部的行为稀疏，传统的基于 I2I 的 match 覆盖率较低。而通过 Embedding 可以计算出任意两个商品之间的 Match 分数，极大改善覆盖率问题。

我们提出一种高可扩展性的 Graph Embedding 方法，该方法可学习到能够可描述图中节点间高阶的、非对称相似度的低维 Embedding 向量。同时我们提供理论上的解释，来阐述这种基于机器学习的方法和基于预定义的传统节点 I2I 相似度的关系。

1.背景介绍 & 相关工作

图是一种抽象程度高、表达能力强的数据结构，它通过对节点和边的定义来描述实体和实体之间的关联关系。常用的图有社交关系网络，通信网络，商品网络，知识图谱等等。

而如何衡量图中节点之间的相似度，对于朋友推荐、商品推荐、以及常见的分类聚类问题来说都是一个很重要的前置步骤。Graph Embedding 可以理解成是一种降维技术，它可以将图中的节点映射到一个低维空间里，我们只需要通过计算低维向量之间的关系，就可以得到原来节点之间的关联关系。

尽管传统 Embedding 技术被研究了很久，但他们的复杂度往往都在 N^2 级别以上，难以适应大规模数据。最近的一系列可扩展性较强的 Graph Embedding 工作主要是从 DeepWalk【6】开始，后面有 Line【7】，Node2vec【2】等等。DeepWalk 在原图中做了一些路径采样，然后将路径当作一个句子，路径中的点当作单词，之后就采用 word2vec 中提出的 Skip-Gram with Negative-Sampling【5】方式进行训练，得到每一个节点的 embedding 向量。Line 只针对边进行采样。Node2vec 可以调节参数来进行 BFS 或者 DFS 的抽样。

然而图中的路径采样在概率上有着非常严重的非对称性，之前的这些方法并没有注意到这件事，也没有从理论上来思考为什么这么干不太科学。

例如在有向图（图 1）中，对于 A 来说，可能并不关心 C，而对于 C 来说，A 很可能是他的兴趣点。即使在无向图中（图 2），也有同样的现象。这样的节点非对称性关系是由于节点周围的图结构不同造成的。而从 C 出发的路径 C->B->A 和从 A 出发的路径 A->B->C 有着完全不相同的概率（0.5，0.08）。因此我们不能认为 C->B->A 这条路径的产生会带来一个（A->C）的正样本。

图 1 有向图中的非对称性

图 2 无向图中的非对称性

2.我们的工作

我们的工作所做的改进其实非常简单，首先为了有能力表达非对称性相似度，我们为每个节点引入了两种 Embedding 向量，分别是 Source 向量和 Target 向量，如图一所示。我们将对于 A 来说 B 的相似度记为 sim(A，B)，并使用 Source(A) 与 Target(B) 的点积来表示，图一中我们可以从 Embedding 中算出 sim(A，C)<sim(C, A)。

图 3 节点的两种 Embedding 身份

其次我们遵循了一种标准的、用来估计 Rooted PageRank【3】的蒙特卡洛随机游走的方法【1】【8】来进行正例的采样。

节点 u 对于节点 v 的 Rooted PageRank（PPR）值代表了从 v 出发落在 u 点的概率。我们认为以这种方式生成图中节点对的正样例是更加自然、合理、有说法的。

这类游走方法都是基于常见的 Random Ｗalk with Restart，即从一个点出发以（1-alpha）的概率选择邻居进行跳转，另外 alpha 的概率跳转回自己。那么现有的几种方法稍有一些区别：

例如 Monte Carlo End Point 只保留首次跳转之前的节点，Monte Carlo Full Path 保留路径上的所有节点，将路径的后缀也当作有效的采样【1】。因为这两条路径对于起始点来说可以看作是相互独立的。在最新的工作中也有对前缀路径进行重用的【8】，就不再此展开。值得注意的是，后两种的采样效率相对于 1 来说要更高，尽管这三种方法都在各自的文章中被证明是正确且有 Bound 的。