【Embedding】EGES：阿里在图嵌入领域中的探索

出品：贪心科技

作者：阿泽

今天学习的是阿里巴巴 2018 年的论文《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》。

这是一篇比较实用的工业论文，提出了 Enhanced Graph Embedding with Side Information（以下简称 EGES）算法，旨在利用 Graph Embedding 的方法解决推荐系统在工业界中的三大问题：扩展性、稀疏性和冷启动问题。

我们一起来看下论文，可以重点关注下如何利用 Side Information 来增强 Graph Embedding 的。

1.Introduction

推荐在电商领域是不可或缺的一部分，并且已经成为阿里巴巴收入的重要引擎。尽管各种推荐系统方法在学界和业界都取得了不错的效果，如协同过滤、基于内容的推荐、基于深度学习的推荐等，但是碰到阿里这样拥有数十亿用户和物品的场景时，还是会遇到很多挑战，比如说：

可扩展性：很多现有推荐方法只适用于小规模的数据集，无法应用大规模数据集；
稀疏性：用户能交互的商品只是很少的一部分，因此很难训练出一个准确的模型；
冷启动问题：在淘宝，每小时都会有数百万新商品上架，对于这些没有用户行为的新商品，我们称之为冷启动问题。

为了解决这些问题，推荐系统一般会分成两个阶段——召回和排序。召回阶段会为每个用户生成一个候选集，而排序阶段会训练一个模型给用户的候选集进行排序。两个阶段的目标不同，所以也会有不同的解决方案。

这篇论文中，我们重点关注召回阶段的问题，核心任务在于基于用户行为计算所有项目之间的成对相似性。大致步骤为基于用户历史行为构造一个图，然后利用 Node2Vec 的方法来学习 Item 的 Embedding 向量。这样便可以根据向量的内积计算节点间的相似度来生成候选集。

这和基于 CF 的推荐方法很相似，但是基于 CF 的方法只考虑到 User 和 Item 的历史共现，而现在的方法不仅考虑共现，还捕捉到了 Item 间的高阶相似性。

但目前的工作还是会存在问题，对于那些没有交互的新物品该如何进行冷启动呢？

为了解决这一问题，阿里的同学提出利用 Side Information 来增强 Embedding 过程，称之为 Graph Embedding with Side information（以下简称 GES）。具体做法为：属于同一类别或品牌的 Item 应该具有更相近的 Embedding 向量。通过这种方式，我们可以在较少甚至没有交互的情况下获得精确的 Item Embedding 。

然而，淘宝上有上百种类型的 Side Information，如品类、品牌、价格等，不同的 Side Information 对学习商品的 Embedding 有不同的贡献。因此，我们在学习 Embedding 时考虑了加权机制，称为 Enhanced Graph Embedding with Side information（以下简称 EGES）。

综上所叙，阿里的召回阶段的 Graph Embedding 迭代了三次方式，即 BGE、GES 和 EGES。

接下来，我们看一下每次迭代的不同之处。

2.EGES

2.1 Construction of Item Graph

先来介绍下如何利用用户行为构造 Item 图。

先前基于协同过滤的方法考虑了 User 和 Item 的共现关系，这样可以很好的反映用户的偏好。但是一般来说不会使用用户的全部历史记录，原因有两个：

用户的历史记录太多，计算代价和存储代价昂贵；
用户的兴趣往往会随时间改变。

因此，在实践过程中，我们会设置一个滑动窗口，只考虑滑动窗口内的用户行为，我们称之为 session-based 用户行为，如下图 a 部分。据经验所得，我们的滑动窗口大小为一小时。

在得到 session-based 的用户行为后，我们将和两个连续的 Item 用一个有向边连接，如下图 b 部分。我们利用用户的行为，考虑连续物品出现的频率，并将设置为相应的边权值。

在实际过程中，还会进行一些降噪处理：

点击少于一秒的视为无意点击，需移除；
去除过渡活跃用户，如三个月内购买超 1000 件商品，或者点击总数超过 3500 次；
有些商家会不断更新商品的细节。极端情况下，一件商品可能经过长时间更新后变成完全不同的商品。所以我们需要移除类似的 Item。

2.2 Base Graph Embedding

得到加权有向图后，我们采用 DeepWalk 来学习图中节点的 Embedding 向量。所以随机游走的概率为：

p(v_j|v_i) = left{ begin{aligned} frac{M_{ij}}{sum_{jin N_{ }(v_i)} M_{ij}} ,quad & v_j in N_{ }(v_i), \ 0 quadquadquad ,quad &e_{ij} notin E end{aligned} right.

其中，为边的权重，为节点的外链邻居集合（从节点出发的边）。

我们会通过随机游走得到一个序列，如下图 c 所示。

然后利用 Skip-Gram 算法来学习节点的 Embedding 向量，如上图 d 所示，优化问题为：

min_{Theta} quad -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)) = Pi_{j=i-w,jneq i}^{i w} Pr(v_j|Theta(v_i)) \

考虑 Negative sampling，我们有：

min_{Theta} quad log; sigma(Theta(v_j)^TTheta(v_j)) sum_{tin N(v_i)^{'}} sigma(-Theta(v_j)^TTheta(v_j)) \

其中，为节点的负采样的样本集合，负采样个数越多，结果越好。

此致，我们便完成了最基本的 Graph Embedding。

2.3 Graph Embedding with Side Information

通过上一节的方法我们可以得到 Item 的 Embedding 向量，从而从用户行为中捕捉高阶相似性。然而现有方法只能针对已有的 Item 而无法应对新的 Item，即无法解决冷启动问题。

为了解决冷启动问题，作者提出了利用 Side Information 来增强 BGE。在电商中，Side Information 是指一个商品的类别、店铺、价格等，这些信息在排序阶段会被广泛使用，但是在召回阶段很少被使用。

我们将利用这些 Side Information 来缓解冷启动问题，例如：优衣库（同店）的两件卫衣（同品类）可能会非常相似，喜欢尼康镜头的人可能也会对佳能相机感兴趣。所以具有相似 Side Information 的 Item 应该离得更近。基于这个假设，我们提出了 GES 方法，如下图所示：

我们用 W 去表示 Item 或者 Side Information 的矩阵，例如：表示 Item v 的 Embedding 向量，表示 Item v 的第 s 个 Side Information。所以，对于具有 n 个 Side Information 的 Item v 来说，其具有 n 1 向量，其中 d 为 Embedding 的维度。这里要注意，Side Information 和 Iten 具有相同维度的 Embedding 向量。

如上图所示，为了合并 Side Information，我们将 Item v 的 n 1 个 Embedding 向量连接起来，并添加了 average-pooling 的操作：

H_v = frac{1}{n 1}sum_{s=0}^n W_v^s \

其中，是 Item v 的聚合后的 Embedding 向量。通过这种方法，我们便将 Side Information 合并到了一起。

2.4 Enhanced Graph Embedding with Side Information

尽管 GES 的性能有所提高，但在 Embedding 的过程中，不同种类的 Side Information 的整合依然存在问题。我们之前采用 average-pooling 是在假设不同种类的 Side Information 对 Embedding 的贡献是相等的。但是这显然有悖于常识，比如说，购买 Iphone 的用户更可能倾向于 Macbook 或者 Ipad；用户可能会为了方便或更低的价格而在淘宝的同一家商店购买不同品牌的衣服。因此，不同类型的 Side Information 是具有不同的贡献值的。

为了解决这个问题，作者提出了 EGES 方法来聚合不同类型的 Side Information。EGES 的框架与 GES 相同，区别在于不同类型的 Side Information 在被聚合时会具有不同的贡献，即权重不同。对于 item v 来说，令为权重矩阵，表示第 v 个 Item 的第 j 种类型的 Side Information，表示 item v 本身的权重。简单起见，我们分别用和代替。所以新的 Embedding 向量为：

H_v = frac{sum_{j=0}^ne^{a_v^j}W_v^j}{sum_{j=0}^ne^{a_v^j}} \

我们用代替来保证每个 Side Information 的贡献度都是大于 0 的，并利用进行归一化。

我们用来表示上下文节点 u，所以 EGES 的目标函数为：

L(v,u,y) = -[ylog(sigma(H_v^TZ_u) (1-y)log(1-sigma(H_v^TZ_u)))] \

反向梯度为：

frac{partial L}{partial Z_u} = (sigma(H_v^TZ_u)-y)H_v \

对于第 s 个 Side Information：

begin{aligned} frac{partial L}{partial a_v^s} &= frac{partial L}{partial H_v}frac{partial H_v}{partial a_v^s} \ &=(sigma(H_v^TZ_u)-y)Z_ufrac{(sum_{j=0}^ne^{a_v^j})e^{a_v^s}W_v^s-e^{a_v^s}sum_{j=0}^ne^{a_v^j}W_v^j}{sum_{j=0}^ne^{a_v^j}} \ frac{partial L}{partial W_v^s} &= frac{partial L}{partial H_v}frac{partial H_v}{partial W_v^s} \ &= frac{e^{a_v^s}}{sum_{j=0}^ne^{a_v^j}}(sigma(H_v^TZ_u)-y)Z_u \ end{aligned}

EGES 的伪代码如下：