电商时代，消费者对推荐系统已经不再陌生。“蓦然回首”，你发现喜欢的商品就在首页显眼处。
如今，不仅仅是电商网站首页会给你贴心推荐。你逛进一家淘宝商家的店铺，也很有可能享受到推荐算法的服务。
这是阿里商家事业部推出的智能店铺“千人千面”模块。
阿里商家事业部相关负责人介绍，单纯通过算法做出的商品推荐，未必符合商家利益。常有商家抱怨，自家想卖的商品得不到推荐，营销被算法牵着鼻子走。而“千人千面”，就是先让商家给出他们想要推送的商品集，算法再从指定候选集中为进入某家商铺的消费者做个性化推荐。如此一来，算法可以为商家的营销服务，为商家既定的 营销计划“锦上添花”。
不过要做到这一点并不简单。
业界推荐系统往往由Matching和Ranking两部分组成。Matching部分会根据全网用户的浏览、加购、收藏等行为数据，在一个庞大的商品池中找出较小的候选集。 Ranking则是利用综合用户Profile，偏好，以及商品特征等信息训练得出的一个打分排序模型。
但是，阿里电商目前拥有百万级别的活跃店铺，单个用户在单个特定店铺内的行为记录非常匮乏，很难按传统方法有效进行matching。
对此，阿里商家事业部提出一种高可扩展性的Graph Embedding（图嵌入）方法，并创新性地将它应用到商品的embedding中。它能够以非常小的存储空间来计算任意两个商品的相似度。就算你此前从未踏足这家店铺，算法也能根据你此前在别家的浏览记录，从店铺里挑出你可能喜欢的商品，摆在你面前。
模块投入使用后，商家的商品点击率提升了30%，成交量提升60%。
从学术层面来说，该Graph Embedding方法可学习到能够描述图中节点间高阶的、非对称相似度的低维Embedding向量，并且可以在理论上解释这种基于机器学习的方法和基于预定义的传统节点间相似度的关系，相关论文已被人工智能领域的顶级会议AAAI'2017接收。
以下是论文的中文描述：
工业界的推荐系统通常由Matching和Ranking两个部分组成，Matching部分会根据全网用户的浏览、加购、收藏等行为数据，利用协同过滤一类的算法（例如基于商品的ItemCF）在一个庞大的商品池中找出一个足够小的候选集，以缩小后续算法需要评估的范围。Ranking则是利用综合用户Profile，偏好，以及商品特征等额外信息训练得出的一个打分排序模型。
我们的推荐场景，即对于店铺私域内的千人千面推荐模块来说，其与公网推荐的重要区别在于，推荐的目标仅限于很小的一部分商家指定的商品集。
传统的Matching这部分所遇到的难题在于，阿里电商目前拥有百万级别的活跃店铺，这使得单个用户在单个店铺内的行为记录非常稀疏。而在很多情况下，用户在近期首次进入某商铺主页时，由于缺乏店内的行为信息（如足迹商品），很难有效利用店内ItemCF来进行推荐。
ItemCF的核心问题之一在于如何有效衡量与计算item与item之间的相似度parencite{recsurvey05}。对于全网推荐的应用场景，由于商品数量太大，通常我们会离线计算出每个item前k个相似的item listparencite{itemcftopk}，来用于在线打分的推荐方案。
然而，如果我们直接用全网topk item相似度的数据，对于每个商品来说，与他相似的商品数目其实可能很多，但由于topk的限制（通常小于200），只有极少数店铺的商品才能够被召回，即基于全网top-k的商品相似度在同店推荐中的召回能力比较有限。
当然，我们可以使用同样的方法，对于每个店铺，仅计算店铺内部的i2i数据，来完成推荐。这样做的缺陷在于，完全无法覆盖用户没有店内足迹的情况。
因此，为了提高相似商品的召回，以覆盖用户没有店内足迹的情况，我们使用了图嵌入算法APP来基于用户浏览记录来做商品嵌入——试图将商品嵌入到一个低维空间中，同时保存一些商品之间的结构特征，即商品相似度。这样就可以用稳定、较小的代价在线算出任意两个商品之间的相似度了。
“旺铺智能版智能模块“是一款面向中小商家的、商家可运营的个性化商品装修模块。在商家侧算法提供面向场景的选品，同时允许商家对算法商品池进行调整，或者完全手动建立商品池；在消费者端，个性化算法基于商家设置的商品池对访客进行实时投放。产品设计上一定程度上满足了商家确定性需求，在此基础上通过个性化算法提升成交转化。
我们研究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)
图 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的。
我们遵循这类游走方法，企图给图中的节点对创造一些正样本。对于每一个被标记为正例的样本（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质量。
5.参考文献
【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.
【5】 Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G. S.; and Dean, J. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, 3111–3119.
【6】 Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 701–710. ACM.
【7】 Tang, J.; Qu, M.;Wang, M.; Zhang, M.; Yan, J.; and Mei, Q. 2015. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, 1067–1077. ACM.
【8】 Liu, Q.; Li, Z.; Lui, J.; and Cheng, J. 2016. Powerwalk: Scalable personalized pagerank via random walks with vertex-centric decomposition. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 195–204. ACM.
