小叽导读：在双11的购物环节中，平台与商家为了激发用户的购买欲望，在不同品类或卖家店铺下存在各种满减优惠活动。在已加购一些目标商品的情况下，一部分用户会选择加购一件额外的商品，在符合购物计划的同时满足特定的满减条件，收获一件物美价廉的商品；还有一部分用户在选择额外商品的时候，会无意间发现一个惊喜的商品，甚至更改之前的购物计划；凑单作为购物环节重要的环节，具有帮助用户提高优惠购物效率与购物探索性两大重要角色。
背景
今年凑单相比往年，在产品形态上我们在第二页推荐中增加了锦囊，增加产品的丰富度，为用户推荐个性化的品类标签，增强用户对产品的黏性。在业务上额外支持了天猫万券齐发会场的个性化推荐与品类津贴的混合凑单。在今年的凑单场景中，继续注重用户在凑单场景的探索发现性与逛的体验，提升推荐的丰富度与多样性，增强跨类目推荐的体验，而本文主要介绍其中在Graph Embedding方面的工作，包括并行化算法的尝试与应用。
算法
问题的抽象与描述
在互联网平台上用户与商品的基本购买关系可以用基于用户/商品两种二部图所描述如下所示：
其中蓝色实线表示用户与商品的直接点击、购买等行为关系，黑色虚线表示表示商品之间基于用户的共同行为关系（点击、加购、购买等），若考虑节点自身的相关属性，则该二部图会变成更加复杂的属性图。
当目标为计算商品之间的I2I关系的时候，传统的一种较为常用的方法是，将用户/商品的二部图通过用户共同行为关系转化为商品之间的同构网络，而同构图中的权重则会基于Memory Based协同过滤的方法计算（如：Adamic-Adar等权衡节点与邻居直接关系与信息热度的1阶计算方法、集团的Swing等综合考虑节点邻居之间相似性的2阶算法）；
另外一种较为常用的方法是在二部图上采样（带权重的随机游走）或基于用户在一个Session中的日志数据，捕获用户的连续行为，得到商品之间的“共现”样本，采用Skip Gram的模型（DeepWalk、Node2Vec、LINE等）训练得到商品Embedding，然后基于TOPK的相似度得到商品I2I。
基于共同行为关系的I2I算法能从大量用户行为数据中精准的捕获商品之间的相关性，在集团内各种推荐场景中都发挥着非常重要的作用。
在凑单场景中，当用户在已加购一定商品的基础上，若再推荐与购买或已经浏览过的商品，则可能会适得其反，因此在凑单的推荐上更侧重于跨类目与丰富度的提升。去年的凑单首次将Graph Embedding算法应用在业务中，而今年我们在去年的基础上强化跨类目的训练，并基于BSP框架在基于BSP的Graph Embedding算法实现上做了一次尝试与算法应用，并设计了一个跨类目属性的概率图模型。本文主要介绍了Graph Embedding算法的实现与应用部分，这只是凑单业务场景的一个部分。
基于BSP的分布式LINE算法实现
SGNS(Skip-Grams with Negative Sampling)是Word2Vec的一个经典模型，自DeepWalk问世以来，类似SGNS的模型在Graph Embedding领域中得到了非常广泛的应用，近些年也陆续有很多改进版本的算法问世，而LINE是其中一个比较经典且效果显著的结合网络局部1阶、2阶关系训练节点向量的算法，也是Graph Embedding算法系列中经常用来作为State of the Art对比的算法，算法基于网络图的边权分布对相邻连接节点之间进行建模与训练：
其中，表示节点的向量，p1通过图中两节点Embedding內积的Sigmoid函数σ定义的两点之间的连接概率，O1是1阶目标函数Loss，描述边的实际连接分布与通过p1表达整个图的概率分布之间的KL距离，O2是2阶目标函数Loss，在2阶模型中每个节点除了自身节点的向量之外，在更新过程中维护一个作为邻居节点context信息的向量，在Glove中也有用到类似context变量的方法。考虑到O2目标函数中分母存在归一化项带来的计算量问题，与Word2Vec的SGNS模型类似，LINE采用如下负采样的方法训练模型：
其中，采用O1与O2作为目标函数分别训练得到1-order与2-order的embedding向量，算法最终经常会采用归一化后的向量作为LinkPrediction以及分类问题的特征。
从分布式的角度观察目标函数，任意节点的更新依赖如下两个部分：1.的邻居节点，2.从全局按照的概率负采样得到的节点。在BSP计算框架下，第1部分的特性非常适合并行化（类似SVD等算法的分布式实现），而第2部分的特性使得BSP框架下的并行化遇到一定的麻烦，因为需要从全局进行采样与更新，因此之前的主流并行化实现模式是Parameter Server的编程模式，而BSP则更多的用于其中的采样环节，作为后续PS上训练Word2Vec算法的样本准备环节，(类似算法那有DeepWalk/Node2Vec等)。
2017年AAAI上发表了一篇关于分布式负采样的Paper，文中提出了一种Target Negative Sampling的方法，其通过在Target节点所在Partition中进行采样的方式实现了负采样在Partition间的并行化，简单理解可以认为其将负采样所需要的计算与存储分摊在了不同的Partition上，通过不同Partition上的AliasMethod采样分摊负采样的计算与存储。
基于集团的Odps-Graph（BSP编程框架）我们实现了LINE的分布式算法，在Odps-Graph框架下，不同的vertex会分摊在不同worker内进行存储，反之一个worker会承担多个vertex的计算与存储，将负采样约束在worker范围内，通过消息的发送实现跨worker的负采样，从而得到近似全局负采样并分摊存储的效果。在梯度更新方面，基于正、负样本的节点向量更新分别采用2个独立超步通过vertex之间的消息发送实现。其余采用类似SGNS模型训练的Graph Embedding算法均可以采用类似的思路实现，伪代码如下：
回到凑单的业务场景中，基于用户历史的共同点点击、购买等行为样本数据，其中对于跨类目的行为进行加权，增强跨类目的训练，基于分布式的Graph Embedding算法，训练的到商品的embedding表达，离线计算得到商品的I2I数据，用于I2I召回的索引Build与在线TopK的推荐商品召回，这种跨类目的做法我们可以归类为样本跨类目的范畴。
举几个实际的Case，如下所示：
通过第一幅现代装饰画，召回后面的油画、开关贴、餐具瓷器、冷水壶、墙贴等多个跨类目下的商品：
通过第一件风衣，召回后面的面霜、睫毛膏、BB霜、耳饰、连衣裙等多个跨类目下的商品：
跨类目概率图模型
传统的Graph Embedding基于Graph中任意两节点与之间的相似度进行edge表达的建模，在凑单等注重丰富度的业务场景中则相对偏重于跨类目的学习。2018年WWW有一篇介绍了考虑人气属性差异的RARE算法，其通过人气差异去削弱人气差异较大节点之间的embedding相似度，虽然他们可能之间存在一条边。
在凑单场景中，我们基于RARE模型进行扩展，尝试基于类目相似度差去削弱在相同类目下不同共同用户行为作用商品之间的embedding相似度。并重点将类目考虑到edge的建模中，而由于类目是一个离散变量，类目的差异我们采用将其做embedding的方法计算，并在模型中结合类目做了一些修正，构建如下所示概率图模型：
总结
Graph Embedding是图学习表达领域一个重要的分支，通过Graph节点的向量表达，描述复杂稀疏的网络结构，能够学习到不同节点之间1、2阶之外的高阶关系，在提升丰富度，新颖性方面有其独特的优势。目前集团内也有算法以及系统团队对其有更加深入的研究与实现，期待广泛的合作与交流学习。
展望
算法上，目前凑单的Graph模型中暂时只有考虑类目与边关系，随着近些年属性图算法、基于Meta Path的Graph Embedding以及深度学习的快速发展，后续会融入更多的商品、用户维度的属性特征，提高模型的精度与表达能力，此外将基于embeddingI2I的召回与排序之间综合考虑建模也是未来研究的重点。
业务上，目前凑单中很多场景入口信息还不完善，比方说用户购物车真实点击入口商品等，因此在实现用户真正意义的“更好的凑”还有比较大的提升空间，此外在用户体验上，今年增强了动态性，削弱了相似商品的重复曝光体验，因此如何更好的挖掘用户的体验也是值得深入研究的方向。
项目总结
本文介绍了凑单项目Graph Embedding方面的一些工作，只覆盖了凑单项目的一小部分，今年我们在系统以及算法上都做了一次较为全面的升级，在算法模型上部署了深度学习模型，分组背包优化模型，跨类目Graph模型，在权重的学习方面引入了实时的LTR，整体上同比去年直接引导进店支付金额+XX%，转化率+XX%，线上A/B对比基准通曝光价值+XX%，转化率+XX%。
参考文献：
【1】Adamic, Lada A., and Eytan Adar. "Friends and neighbors on the web." Social networks 25.3 (2003): 211-230.
【2】J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. LINE: Large-scale Information Network Embedding. In WWW, 2015.
【3】Yupeng Gu, Yizhou Sun, Yanen Li, Yang Yang, "RaRE: Social Rank Regulated Large-scale Network Embedding," Proc. of the 27th Int. Conf. on World Wide Web (WWW’18), Lyon, France, Apr. 2018.
【4】Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.
【5】Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.
【6】Stergios Stergiou, Zygimantas Straznickas, Rolina Wu, and Kostas Tsioutsiouliklis.2017. Distributed Negative Sampling for Word Embeddings. In Proc. AAAI Conf. on Arti$cial Intelligence (AAAI).
