千人千面模块上线，每一家淘宝店铺从此都可能有一个隐形智能导购，推荐算法再升级。
电商时代，消费者对推荐系统已经不再陌生。「蓦然回首」，你发现喜欢的商品就在首页显眼处。
如今，不仅仅是电商网站首页会给你贴心推荐。你逛进一家淘宝商家的店铺，也很有可能享受到推荐算法的服务。
这是阿里商家事业部推出的智能店铺「千人千面」模块。
阿里商家事业部相关负责人介绍，单纯通过算法做出的商品推荐，未必符合商家利益。常有商家抱怨，自家想卖的商品得不到推荐，营销被算法牵着鼻子走。而「千人千面」，就是先让商家给出他们想要推送的商品集，算法再从指定候选集中为进入某家商铺的消费者做个性化推荐。如此一来，算法可以为商家的营销服务，为商家既定的 营销计划「锦上添花」。
不过要做到这一点并不简单。
业界推荐系统往往由 Matching 和 Ranking 两部分组成。Matching 部分会根据全网用户的浏览、加购、收藏等行为数据，在一个庞大的商品池中找出较小的候选集。Ranking 则是利用综合用户 Profile，偏好，以及商品特征等信息训练得出的一个打分排序模型。
但是，阿里电商目前拥有百万级别的活跃店铺，单个用户在单个特定店铺内的行为记录非常匮乏，很难按传统方法有效进行 matching。
对此，阿里商家事业部提出一种高可扩展性的 Graph Embedding（图嵌入）方法，并创新性地将它应用到商品的 embedding 中。它能够以非常小的存储空间来计算任意两个商品的相似度。就算你此前从未踏足这家店铺，算法也能根据你此前在别家的浏览记录，从店铺里挑出你可能喜欢的商品，摆在你面前。
模块投入使用后，商家的商品点击率提升了 30%，成交量提升 60%。
从学术层面来说，该 Graph Embedding 方法可学习到能够描述图中节点间高阶的、非对称相似度的低维 Embedding 向量，并且可以在理论上解释这种基于机器学习的方法和基于预定义的传统节点间相似度的关系，相关论文已被人工智能领域的顶级会议 AAAI'2017 接收。
接下来是对该论文的中文讲解，完整论文PDF可点击阅读原文下载：
工业界的推荐系统通常由 Matching 和 Ranking 两个部分组成，Matching 部分会根据全网用户的浏览、加购、收藏等行为数据，利用协同过滤一类的算法（例如基于商品的 ItemCF）在一个庞大的商品池中找出一个足够小的候选集，以缩小后续算法需要评估的范围。Ranking 则是利用综合用户 Profile，偏好，以及商品特征等额外信息训练得出的一个打分排序模型。
我们的推荐场景，即对于店铺私域内的千人千面推荐模块来说，其与公网推荐的重要区别在于，推荐的目标仅限于很小的一部分商家指定的商品集。
传统的 Matching 这部分所遇到的难题在于，阿里电商目前拥有百万级别的活跃店铺，这使得单个用户在单个店铺内的行为记录非常稀疏。而在很多情况下，用户在近期首次进入某商铺主页时，由于缺乏店内的行为信息（如足迹商品），很难有效利用店内 ItemCF 来进行推荐。
ItemCF 的核心问题之一在于如何有效衡量与计算 item 与 item 之间的相似度\parencite{recsurvey05}。对于全网推荐的应用场景，由于商品数量太大，通常我们会离线计算出每个 item 前 k 个相似的 item list\parencite{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：
