Abstract
本文的贡献是在传统的word2vec基础上，为了减轻数据系数和冷启动问题，将辅助信息和合并到图embedding框架中。为了将辅助信息合并到图embedding中，本文提出了两种方法，离线的实验结果表明包含了辅助信息的方法要由于不包含辅助信息的方法。在淘宝的A/B测试中也验证的模型的有效性和可行性。
Introduction
本文抽取的关键问题是：淘宝上有10亿用户和20亿件商品，如何帮助用户快速找到所需有趣的商品。尽管当前在学术界和工业界各种推荐方法已经取得了成功。淘宝面临的三大技术挑战：大规模、数据稀疏、冷启动问题。为了解决这些问题，淘宝设计了一个两阶段的推荐框架，召回和排序。在召回阶段，为用户生成一组候选的商品集合；在排序阶段，训练一个深度神经网络模型， 根据用户的偏好对候选商品集合排序。每个阶段有不同独特的问题，每个阶段的目标也不同，这也导致了不同的技术解决方案。在进行pairwise计算商品的相似性之后（Pairwise被用来在排序阶段）,可以观测到候选商品在排序阶段进一步个性化。基于此，本文提出了一种方法从用户交易历史数据中抽取商品图结构并应用到现有的embedding方法中，这种方法被称为Base Graph Embedding.基于此，我们能够计算embedding向量的作为候选商品的项目集（这是前人的工作）。基于协同过滤的方法也能够计算相似性，但是协同过滤方法仅能够考虑用户历史行为中的共现信息。在本文的工作中，在商品图中进行Random walk是捕捉商品之间的高阶相似性，因而优于协同过滤类的方法。然而，对于有很少交互的商品，很难学习到用户的embedding。为了缓解这个问题，本文提出使用复制信息来增强学习embedding过程（带辅助信息的图embedding），例如：属于同一类别或品牌的商品在嵌入空间中应该更近。通过这种方式，对于有很少交互的商品也能够准确学习到商品的embedding，但是淘宝网友数百种类型的辅助信息如商品类别、品牌、价格等，从直观的角度说不同的辅助信息应该对学习embedding有着不同的贡献。因此，本文进一步提出了一种加权机制，称为带辅助信息的增强图Embedding(EGES).
本文值得学习的地方有三点：1. 设计一种有效的启发式算法，从10亿用户历史行为中构建商品图。2. 提出三种embedding方法：BGE、GES、EGES，以学习淘宝上20亿个商品embedding。进行离线实验证明实验的有效性。3.项目部署满足双十一的响应需求。
FRAMEWORK
首先介绍图embedding的常用方法DeepWalk，给带一个图\mathcal{G}=(\mathcal{V}, \mathcal{E}), 图Embedding的任务是对每一个节点\mathcal{v} \in \mathbb{V},在\mathbb{R}^d中学习到一个低维的嵌入表示，其中d \gg |V|.DeepWalk首先在图中运行随即便利生成节点序列，然后使用Skip-Gram来学习每个节点的表示。为了保留图的拓扑结构还需要解决以下优化问题：
\min_{\Theta} \sum_{\mathcal{v} \in \mathbb{V}} \sum_{c \in N(v)} -\log Pr(c|\Theta(v))
其中N(v)是节点v的邻居，其可以被定义为距离节点v内一个或两个跳跃点内的节点。Pr(c|\Theta(v))定义了给定节点v的前提下上下文节点c的概率。
Construction of Item Graph from Users Behaviors
在这一部分，本文根据用户的行为详细阐释商品图的构造。实际上，用户在淘宝网中的行为往往是有顺序的。基于协同过滤的方法也能够计算相似性，但是协同过滤方法仅能够考虑用户历史行为中的共现信息。忽略了用户的序列信息，而用户的序列信息更能准确地反映出用户的偏好。
但是，不能使用全部用户的历史信息：原因一是计算成本过于昂贵。原因二是用户的兴趣往往随着时间而发生变化。因而在实践中，我们设置一个时间窗口，只选择在时间窗口内的用户行为。这称为基于会话的用户行为.根据经验，时间窗口的持续时间是一小时。在获得了用户的短期会话行为后，如果两个商品先后被点击，那么两个节点之间会有一条边。根据所有用户行为中先后连接的两个商品出现的总次数，为每一条边赋予一个权重e_{ij},这个权重的值等于在用户历史数据中商品i转移到商品j中的频率。,此外本文提出三点方法来消除系统中的噪音：
- 如果点击后停留的持续时间少于1秒，这说明用户行为很可能是不小心点击的。
- 淘宝中有一些“过度活跃”的用户，他们其实是垃圾用户。根据淘宝内部的调查，如果一个用户在不到三个月的时间内购买了1000件商品或ta的总惦记次数大于3500，则该用户很可能是垃圾用户，我们需要过滤掉此类用户。
- 淘宝的零售商持续不断更新商品的细节，在某些极端的情况下，经过长时间的更新后，尽管商品的id都是相同的，但是两者的内容却可能截然不同，因而我们需要删除这类商品。
Base Graph Embedding
在获得加权有向商品图之后，即\mathcal{G}=(\mathcal{V}, \mathcal{E})，我们使用DeepWalk学习\mathcal{G}中的embedding，设M为图\mathcal{G}中的邻接矩阵，M_{ij}表示从节点i指向节点j边的权重。首先基于随机游走生成节点序列，然后在序列上运行Skip-Gram，随机游走的转义概率为
P(v_j|v_i)=
\begin{cases}
\frac{M_{ij}}{\sum_{j\in N_{+}(v_i)}}&v_j \in N_{+} (v_i) \
0& e_{ij} \notin \mathcal{E}
\end{cases}
其中N_+{v_i}表示为向外指向的邻居,运行随机游走，产生一系列序列如图1(c)所示。之后使用Skip-Gram算法学习embeddings，最大化两个节点出现的概率
\min_{\Theta} - \log Pr({ v_{i-w},...,v_{i+w} \backslash v_i | \Theta(v_i) })
其中w是序列中上下文节点的窗口大小。
根据独立性假设，我们有：
Pr({ v_{i-w},...,v_{i+w} \backslash v_i | \Theta(v_i) }) = \prod_{j=i-2, j \neq i} ^{i+w} Pr(v_j|\Theta(v_i))
使用负采样上述公式被改写为：
\min_{\Theta} \log \sigma( \Theta(v_j)^T \Theta(v_i)) + \sum_{t \in N(v_i)^'} \log \sigma(-\Theta(v_t)^T \Theta(v_i))
其中N(v_i)^'是对于v_i的负采样样本，\sigma()是sigmoid函数。从经验上说，|N(v_i)^'|越大，实验效果越好。
利用辅助信息的图神经网络
通过使用Deepwalk我们可以学习到商品的embedding，捕捉用户行为序列中的高阶相似性。但是学习低频商品的embedding仍然具有挑战性（冷启动问题）。为了解决冷启动问题，本文建议使用附加到低频商品的复制信息来增强低频商品的嵌入表示。辅助信息指的是商品的类别，商店，价格等。这些信息广泛用作排序阶段，较少用在召回阶段。，在图Embedding中加入辅助信息来缓解冷启动问题。例如：优衣库（同一商店）的两个连帽衫（相同类别）可能看起来很像，Embedding因而也比较相似。这意味具有相似辅助信息的商品在嵌入空间中应该更近。提出了如图二的GES方法
本文使用W为商品的Embedding或辅助信息，具体地说，W_v^0是商品v的Embedding，W_v^s是商品v的第s类辅助信息的嵌入，对于有n种类型辅助信息的商品v，我们有n+1个向量，W_v^0,...,W_v^n \in \mathbb{R}^d,根据经验商品和辅助信息的Embedding尺寸要设置相同的维度。如图二所示，为了合并辅助信息，对于商品v本文拼接n+1个Embedding向量，在此基础上添加了Avg池化层，以聚合池化层商品t的所有Embedding，即：
H_v = \frac{1}{n+1} \sum_{s=0}^n W_v^s,
H_v是商品v的聚合嵌入，通过这样方式，我们以这样的方式合并辅助信息，使得具有相似辅助信息的商品在嵌入空间中更加接近。
增强辅助信息的图神经网络
尽管GES性能提升，但是在嵌入聚合的过程中集成不同类型的辅助信息仍然存在问题。在上面的聚合公式中，我们假设不同类型的辅助信息对最终贡献都是相同的，但是这不能反映现实。例如：购买IPhone用户的由于品牌Apple而倾向于查看MacBook或Ipad，而用户可以在淘宝的同一商店购买不同品牌的服装以抵扣价格。
为了解决这个问题，本文提出EGES聚合不同类型的辅助信息该框架与GES相同，这个想法是当聚合Embedding是不同类型的辅助信息会有不同的贡献，因而提出加权平均层以聚合商品相关的辅助信息的嵌入，给定商品v，设A \in \mathbb{R}^{|V| \times (n+1)}, 元素A_{ij}的权重为第i个商品。A_{*0}矩阵A的第一列表示商品v本身的第一个权重。使用a_v^s表示商品v的第s类辅助信息的权重，其中a_v^0表示商品本身的权重。以下定义组合不同辅助信息的加权平均层:
H_v = \frac{\sum_{j=0}^n e^{a_v^j}W_v^j}{\sum_{j=0}^n e^{a_v^j}}
使用e^{a_v^j}而不是a_v^j的原因是因为确保每一个辅助信息的权重都大于0， 分母部分的作用是用于正规化每个相关的权重。对于训练数据中的节点v和Context节点u，我们使用Z_u \in \mathbb{R}^d来表示Embedding，使用y表示标签。然后EGES目标函数变化为：
\mathcal{L}(v,u,y) = -[ y \log(\sigma(H_v^TZ_u)) + (1-y)\log(1- \sigma(H_v^TZ_u))]
EXPERIMENTS
Offline Evaluation
链接预测：给定删除了一些边缘的网络，链接预测任务是预测链接的发生。随机移除1/3的边作为测试集，剩下的作为训练集。在测试数据中抽样相同数量的没有连接的样本作为负样本，使用AUC作为模型的评价指标。数据集Amazon Electronics，第二个数据集是淘宝数据集。对于亚马逊数据集，商品图的关系是根据“共同购买”关系构建的(在提供的数据中表示为also_bought)，使用三类辅助信息：“Category, sub-category, brand”对于淘宝数据集，在淘宝中使用了：零售商、品牌、购买水平、年龄、性别、风格等，这些是淘宝多年的实践经验，数据信息如下：
对比方法：实验使用了四种比较方法，BGE，LINE,GES, EGES。运行LINE使用一阶和二阶近似。同时自行实现其他三种方法，Embedding维度都设置为160维，对于BGE,GES和EGES.随机游走的长度被设置为10， 每个节点的部署设置为20，滑动窗口数设置为5
结果分析：
从实验结果中可看到GES和EGES要由于BGE，LINE（1st）和LINE（2st），这证明了所提出方法的有效性。 换句话说，通过结合辅助信息来减轻稀疏性问题。在比较亚马逊和淘宝上的改进时，淘宝上的性能提升更为显着。推测是因为淘宝数据集中使用了大量有效的辅助信息，在比较GES和EGES时，能够看到亚马逊数据集提升由于淘宝网，这可能是由于淘宝网的表现已经非常好了，所以EGES的改善不够突出。除此之外可以发现，在辅助信息的利用上面是大有文章可做的。
Online A/B Test
淘宝主页的推荐排序模型是基于深度神经网络模型实现，在A/B测试中，我们使用相同的方法对候选项进行排名。召回的效果将直接影响推荐的精度。在A/B测试，使用CTR来代表召回模型的有效性。
本文在测试框架中部署了这四种方法（注意要同时部署Baseline模型），2017年11月的七天结果如图4所示。注意“Base”表示基于item的CF方法。从图4中我们可以看出，EGES和GES在点击率方面始终优于BGE和Base，这证明了在本方法中模型的有效性。此外，Base的CTR大于BGE的CTR。 这意味着经过良好调整的基于CF的方法可以击败简单的嵌入方法，因为在实践中已经开发了大量手工制作的启发式策略。 另一方面，EGES始终优于GES，这与第3.1节中离线实验结果的结果一致。
Case Study
Visualization:
该工具使用tensorflow下的Projector来进行可视化展示，可以看到不同类别的鞋子是分开的。一种颜色代表一类鞋子，如羽毛球，乒乓球或足球鞋。它结合了辅助信息证明了学习Embedding的有效性：具备相似辅助信息的item应该在嵌入空间中更接近。
Cold Start Items
可以看到，尽管用户对两个冷启动项目的行为缺失，但可以利用不同的辅助信息来有效地学习它们的嵌入.根据最相似商品的质量，能够为每个相似项目注释连接到冷启动项目的辅助信息的类型。
Weights in EGES
在这部分中，我们可视化各种项目的不同类型的辅助信息的权重.
选择不同类别中的八个项目，并且从学习的权重矩阵A中提取与这些项目相关的所有辅助信息的权重.1）不同商品的权重分布是不同的，这与我们的假设不一致，即不同的边信息对最终表示的贡献不同。 2）在所有项目中，表示项目本身的嵌入的“项目”的权重始终大于所有其他辅助信息的权重。 它证实了直觉，即商品本身的嵌入仍然是用户行为的主要来源，而辅助信息则提供了用于推断用户行为的额外提示。 3）除商品外，零售商的权重始终大于其他方信息的权重。 它与淘宝网中用户的行为一致，即用户倾向于在同一商店购买物品，以方便和降低价格。