图系列算法在转转推荐算法召回及粗排的实践

一、转转推荐算法介绍

1.1 什么是推荐系统？

随着信息技术与互联网的飞速发展，借由互联网所传递的信息也在飞速地膨胀，人类从信息匮乏时代走向了信息过载时代，推荐系统开始在互联网技术中扮演不可或缺的角色。推荐系统帮助人们更高效地建立与信息的连接，节约信息筛选的时间，为用户匹配、探索兴趣，也让平台的高效分发成为可能。对于转转来说，推荐系统承担了为用户推荐商品与内容的重要角色，一方面链接了用户与商品的关系，为用户节约筛选心仪产品的时间，帮助用户在平台琳琅满目的商品中发现感兴趣的商品；另一方面帮助商家让自己的商品从海量商品中脱颖而出，推荐给合适的用户。在推荐系统中，推荐算法扮演了发动机的作用。

推荐算法的作用

1.2 转转推荐主要场景及流程

转转推荐主要场景

在转转 APP 中，推荐算法涉及的主要场景包括首页推荐、商详页推荐以及收藏夹推荐等等。用户进入 APP 后，在主页面下滑即进入首页推荐场景，该场景由算法推荐用户可能感兴趣的商品流，帮助用户进行商品的筛选和探索；当用户点击一个商品后，即进入商详页推荐，为用户推荐与主商品相似的更多商品以挑选；当用户收藏商品后，也会根据用户的收藏行为和历史兴趣，为用户推荐更多的商品。

推荐算法流程

推荐算法的主要流程如图所示，整个流程呈漏斗形，对商品库进行层层筛选，最后将推荐结果呈现给用户。

召回是推荐算法的第一阶段，根据用户和商品信息从海量的商品库中，快速筛选出用户可能感兴趣的商品集，传递给接下来的粗排及精排部分。由于面对的商品集合非常大，因此召回阶段对于性能要求高，需要用相对简单的模型及特征；

粗排则承接召回筛选过的商品，为用户推荐的候选集打分，并筛选出精排候选，作为一个承上启下的阶段，模型及特征的复杂度相对折中；

精排则通常只对少量商品进行排序，可以使用较多特征及复杂模型，对于推荐的准确度要求更高；

最后会根据业务特点及其他目标进行重排，在此不再赘述。

本次分享主要介绍图算法的原理以及在转转召回及粗排阶段的实践。

二、图算法原理介绍及转转实践

图是一种基础且常用的数据结构，也广泛存在于真实世界的多种场景中，例如社交网络中人与人的联系、生物中蛋白质的作用以及电商中用户与商品之间的关系等等。

在转转的场景中，通过对用户与商品关系的建图以及在此基础上的图表示学习，我们能够得到低维、稠密、实值的向量，能够表达节点之间内在的关系。

利用得到的向量，既可以作为排序层的预训练特征，也可以直接计算向量相似度，寻找相似的商品，并直接推荐给用户。

图结构以及对应的节点向量(引自 DeepWalk 论文)

2.1 经典 Graph Embedding 方法：DeepWalk

首先介绍经典的 Graph Embedding 方法——DeepWalk。

DeepWalk 的基本流程(引自阿里 EGES 论文)

DeepWalk 在电商场景应用的大体流程可以分为以下四个步骤：

1. 获取用户原始行为序列，并根据一定规则进行切分（如点击间隔超过 1 小时）。

2. 基于这些切分的用户序列，构建商品图结构。例如用户 A 依次产生了 D、A、B 的行为，则构建 D->A 的有向边、A->B 的有向边。将所有用户序列产生的商品共现对如（D,A）都建立有向边后，即建立起全局的商品图。

3. 选取多个起始点（实际上可以以每个节点为起始点）进行随机游走，得到多条序列。

4. 将重新生成的物品序列利用 word2vec 模型里的 skip-gram 算法进行图向量的训练和获取。

其中关键是第三步的随机游走过程，即如何选择下一个游走的节点。DeepWalk 定义节点 vi 到 vj 的转移概率如下：

P(vj∣vi)={Mij∑j∈N+(vi)Mij,vj∈N+(vi)0,eid∈ε

其中 N+(vi)是 vi 的所有出边集合，Mij 是节点 vi 到 vj 的边权重。

2.2 结构性与同质性：node2vec

图的 BFS 和 DFS 遍历(引自 node2vec 论文)

在 DeepWalk 的基础上，node2vec 改进了随机游走过程的游走概率，引入了两个超参数来平衡图的两类游走方式——广度优先 BFS 和深度优先 DFS。

node2vec 的节点转移概率

通过引入超参数 p 和 q，算法能够控制节点的游走倾向性。将节点的游走概率定义为πvx=αpq(t,x)·wvx，其中 wvx 是边 vx 的权重，αpq(t,x)定义如下：

αpq(t,x)={1p,dtx=01,dtx=11q,dtx=2

其中，dtx 指节点 t 到节点 x 的距离，超参数 p 被称为返回参数，p 越小，返回原节点的概率越大，游走偏向 BFS，更关注结构性相似；q 被称为进出参数，q 越小，则随机游走向更远节点的概率越大，游走偏向 DFS，更关注同质性相似。

同质性与结构性(引自 node2vec 论文)

在推荐系统中，同质性相似的物品体现在同品类、同属性或者经常被一同点击、购买的商品；而结构性相似的物品则体现在各品类的爆款、各品类的最佳凑单商品等趋势类似的商品。node2vec 相比 DeepWalk 拥有更强的灵活性，能够帮助我们根据应用场景的不同选择不同的游走策略，得到合理的向量表示。

2.3 融合辅助信息：EGES

回顾下 DeepWalk 一节中介绍的算法流程，能够发现一个问题：对于新商品或者用户交互较少的商品，很可能是孤立的节点或者节点权重很小，导致不能游走到该节点或游走到该节点的概率很低。如何解决这类冷启动问题？

阿里 2018 年提出的 EGES(Enhanced Graph Embedding with Side Information)在 skip-gram 的向量嵌入过程中，除了采用序列的 ID 类 embedding 之外，还引入了带权的辅助信息(side information)来缓解该问题。

EGES 到生成商品序列前的流程与 DeepWalk 介绍的一致，但是在最后的嵌入过程中，引入了如类别、品牌、所在城市等辅助信息的多个 embedding 共同训练。对于多个 embedding，最简单的融合方法即 average pooling，形式化定义如下：

Hv=1n+1∑s=0nWvs

利用以上公式即平均操作，将不同的辅助信息向量与原物品向量融合，其中 W0 代表原始物品的 embedding，W1...Wn 代表每种 side information 对应的 embedding。

但是在实际问题中，不同的辅助信息对于物品的贡献应有所不同，如一个购买了 iPhone 的用户，倾向于查看 MacBook 和 iPad，是因为品牌。引入加权形式的辅助信息利用，能够得到更准确的 embedding。

Hv=∑j=0neavjWvj∑j=0neavj

在 GES 模型的基础上，引入权重 a1...an，通过 Hidden Representation 层执行加权平均操作，并输入 softmax 层，通过反向传播求得权重。

通过 eaj 代替 aj，保持权重大于 0，分母则起到 normalize weights 的作用。

最后进行 skip-gram 的方式训练得到每个商品的 embedding 和 side infomation 及对应的权重。

阿里 EGES 的向量训练模型结构

2.4 辅助信息融入建图：转转召回实践

在转转的实际实践中，采用 EGES 的加强辅助信息融合方式遇到了一些困难，特别是辅助信息融合训练的性能问题。

融入辅助信息的有向带权商品图

因此，我们采取了影响图权重的方式来引入辅助信息。主要有以下步骤：

1. 获取用户序列切分生成共现对，并同步获取相应商品的辅助信息

2. 将全局共现对聚合，根据用户交互行为数目确定初始权重

3. 根据节点间边的预先定义的几类辅助信息调整权重，例如同类或同价格区间即上调权重

4. 进行 node2vec 随机游走过程并进行向量嵌入训练

通过辅助信息融入建图过程的方法，大大提高了训练速度，并减少了 embedding 参数量，在实际应用中向量的质量也能够满足需要。在 node2vec 参数上，可以通过调整同质性相似与结构性相似，来应用于详情页推荐场景与首页推荐场景。

得到商品向量即可进行向量相似度计算，从而进行商品的 item2item 推荐，或者利用用户交互过的商品进行 user2item2item 的推荐。

2.5 异构图表示：转转粗排实践

对于粗排来说，需要得到同空间内的用户向量及商品向量，利用内积操作，能够对于用户的召回候选集进行快速的打分和筛选。通常的粗排模型往往采用双塔模型，通过拆分用户塔和商品塔，可以使得向量产出由离线计算完成，线上则采用内积。可见，粗排的关键问题即是用户和商品的向量生成。那么能不能通过图算法来得到用户和商品的向量呢？答案是肯定的。

前几节介绍了 Graph Embedding 的原理以及一些改进的思路，和转转的召回实践，这些介绍中的图都为同构图，图中的节点都为商品。要同时得到用户和商品的向量，则需要将用户节点也加入到图中，构成异构图。

用户商品二部图生成无向带权图

具体的实现步骤如下：

1. 获取用户行为序列，并切分为用户-商品二部图

2. 根据二部图中的（用户,商品）共现对，建立无向带权图

3. 在图中进行随机游走过程，得到形如 u1-i1-u2-i2...的序列

4. 进行向量嵌入训练，得到用户及商品的向量

离线训练得到向量后，线上分别取得用户及商品向量，进行简单内积后即得商品打分。

三、总结

本次分享介绍了转转的主要场景及算法流程，并介绍了三种常见的图算法：

• 经典的 Graph Embedding 方法 DeepWalk，是各类随机游走算法的基础

• node2vec 在 DeepWalk 的基础上引入超参数控制游走倾向，学习结构性及同质性相似

• EGES 则提出融合加权辅助信息，缓解节点冷启动的问题

介绍了上述图算法在转转推荐算法召回及粗排的实践。

图算法目前仍是工程和学术领域研究和实践的热点，除了本次分享介绍的方法，还有如随机游走类的 LINE、SDNE 以及图卷积类的 GAT、GraphSAGE 的方法，感兴趣的读者可以深入了解。图卷积算法也在转转有相应的落地和实践，有机会再向大家分享。谢谢！

参考资料

[1]Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014: 701-710.

[2]Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 855-864.

[3]Wang J, Huang P, Zhao H, et al. Billion-scale commodity embedding for e-commerce recommendation in alibaba[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 839-848.

[4]王喆：深度学习中不得不学习的 Graph Embedding 方法 https://zhuanlan.zhihu.com/p/64200072

> 转转研发中心及业界小伙伴们的技术学习交流平台，定期分享一线的实战经验及业界前沿的技术话题。> 关注公众号「转转技术」（综合性）、「大转转FE」（专注于FE）、「转转QA」（专注于QA），更多干货实践，欢迎交流分享~