我们遵循这类游走方法，企图给图中的节点对创造一些正样本。对于每一个被标记为正例的样本（A, B）我们会根据目标函数更新 A 的 source 向量和 B 的 target 向量。并且随机采样其他的节点作为负样本。

我们定义给定节点 u，可以预测到节点 v 的概率

利用 Skip-Gram with Negative-Sampling【5】，近似等价于优化

K 是负采样数，P_D（n）在图中可用均匀分布替代。则总的目标函数如下：

下面我们来解释一个有趣的现象，我们非对称的点积最终会是以学习出两点之间的 PPR 的对数为目标。

这里，类似于 Levy【4】的证明，当维数充分大时，可看作互相独立的变量。于是另下式为 0：

得到：

由于|V|, k 均为常数，我们可以看出 x 只跟 Rooted PageRank 的模拟值 Sim_u(v) 呈对数关系。通过以上证明，论证了该方法可以保持非对称的、高阶相似度的说法，因为 Rooted PageRank 就是一种非对称的、高阶的相似度度量。

3.小数据集上的实验

Link Prediction Task（AUC）：Embedding 方法相对于传统 Pre-defined i2i 指标来说，在 AUC 上很占便宜。因为传统指标大多基于 2 跳以内的关系，包括阿里内部使用的 Swing。这样就有很多正例的结果是 0——完全无法和负例分开，AUC 不高。可以看出我们的方法（APP）在比现有的方法要好一些。

下表是为了体现非对称性的优势，而在负样本中加大了单向边的比例，即 A->B 有边，B->A 无边。可以看出我们与之前的方法在 LinkPrediction 任务上有显著提升。

Node Recommendation：

值得注意的是，在寻找 topk 的这个问题当中，我们发现之前的 Embedding 方法似乎并没有传统指标靠谱。但我们的方法可以比较好的反应 Topk 的相似关系。

4.在模块千人千面中的实践

为了缓解用户在店铺内部行为的稀疏性，我们将用户 Session 中的全网点商品击序列转化成一个全网商品点击转换图。之后应用我们的 Graph Embedding 方法得到商品向量。该向量可以用来计算用户点击行为所产生的商品之间的相似度。下图是我们与传统 topk i2i 方法在真实场景中的点击率比较。

我们的这项工作目前还只是作为 Match 打分的基础算法，我们正在尝试进一步融合一些外部信息，如商品文本属性、类目信息等，提高长尾商品的结构化 Embedding 质量。

参考文献：

1.Fogaras, D.; R´acz, B.; Csalog´any, K.; and Sarl´os, T. 2005. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics 2(3):333–358.

2.Grover, A., and Leskovec, J. 2016. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining. ACM.

3.Haveliwala, T. H. 2002. Topic-sensitive pagerank. In Proceedings of the 11th international conference on World Wide Web, 517–526. ACM.

4.Levy, O., and Goldberg, Y. 2014. Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems, 2177–2185.