从17年5月份开始接触Graph Embedding，学术论文读了很多，但是一直不清楚这技术是否真的能应用于工业界？
最近导师转发给我一篇文章，名为《阿里凑单算法首次公开！基于Graph Embedding的打包购商品挖掘系统解析》，眼界大开！
今天就阅读这篇推文，做一些摘录和笔记...侵删！
传送门：http://mp.weixin.qq.com/s/diIzbc0tpCW4xhbIQu8mCw

一、背景

凑单作为购物券导购链路的一个重要环节，旨在帮助用户找到商品，达成某个满减门槛（比如满400减50），完成跨店凑单，完善购物券整个链路的体验。满减购物券作为大促中使用最广泛的一种营销手段，优势远大于红包、商品打折等优惠活动，它不仅能给用户带来切实的优惠，而且能让用户买的更多，提升客单价。凑单作为用券的重要链路，旨在帮助消费者找到能使用同门槛优惠券的商品。

近期，阿里的凑单设计相比往年，有两个重大突破，首先是产品形态上的改变，往年，凑单只是一个商品推荐页，今年，凑单能够支持搜索、价格筛选、类目筛选、销量排序、价格排序等搜索功能。其次，算法上做了重大突破，基于Graph Embedding的bundle mining，bundle是打包购的意思，他们认为凑单的重要场景是当用户已经加购了商品A，还想找一个能一起打包买的商品B，而不是想找跟A相似的商品C，传统的u2i、相似i2i并不能满足凑单场景的需求，为了突破找相似等经常被人诟病的体验，我们甚至不能有u2i、相似i2i等逻辑，所以bundle mining变成凑单算法优化的重点，不仅能提升丰富性的体验，还能提升转化效率。

示例

二、核心算法

1. 基本思路

图是一种抽象程度高，表达能力强的数据结构：节点可用于表示现实世界的实体，而实体之间的关系则通过节点之间的边来体现。常用的图有社交网络、商品网络、知识图谱、用户-商品网络等等。

用户行为是一个天然的网络图，边和节点往往有着各种丰富的信息，graph embedding是学习节点的一种连续、稠密、低维的向量表示，以便通过向量的关系来衡量节点之间的关系。

Graph embedding是学术界一个重要的研究方法，传统的方法是对用于描述网络的affinity matrix进行矩阵分解，得到节点的低维表示。但是这种方法计算量大，不适合大型网络。随着 word embedding技术成功，涌现出一批借鉴语言模型完成graph embedding的方法：DeepWalk、node2vec、metapath2vec等等。这些方法大都包含两个步骤：（1）基于random walk挖掘节点之间的关系（由节点组成的sequence）；（2）将节点序列当做语料库中的句子，从而采用skip-gram模型学习节点的向量表示。

2. 主要技术
Graph embedding技术相比较于传统的协同过滤最大的优势是：基于random walk采样序列，能够挖掘出图中一阶，二阶甚至更高阶的关系，如朋友的朋友也是朋友。random walk能够充分利用图的传播能力，解决用户行为数据稀疏的问题，大大提高覆盖率和转化率。

阿里的工作主要分为三个部分：
（1）基于用户购买行为构建graph，节点：商品，边：商品间同时购买的行为，权重：同时购买的比重，可以是购买次数、购买时间、金额等feature；
（2）基于权重Sampling（weighted walk）作为正样本的候选，负样本从用户非购买行为中随机抽样；
（3）embedding部分将无监督模型升级成有监督模型，将基于weighted walk采出来的序，构造成item-item的pair对，送给有监督模型（DNN）训练。下图是算法框架图。
idea：能否基于网络关系挖掘高阶相似度或其他的信息、人为制定的规则，找出更为准确的负例？

算法框架

step 1 构建带权网络
节点——商品，边——商品间共同购买的关系，权重——共同购买的次数、购买时间。

为什么需要带权重的Graph？因为random walk等传统方法不适用商品网络，商品节点动辄上千万，其中大部分节点的关联性是很弱的，也就是冷门商品居多，只有少部分商品构建的graph是热点，如果采用random walk去采样，会采出很多冷门节点的序列，所以我们基于边的权重去采样（weighted walk），使采样尽量往热门节点方向游走，这样采样出来的样本置信度才更高。
idea：基于节点重要性采样呢？

因此，输入是一个带weight的graph ，Graph定义：G = （V，E，W），V = vertex （顶点或者节点，在bundle的问题中，特指商品），E = edge（边，在bundle的问题中，特指共同购买） ，W = weight（边的权重，共同购买的次数、时间），如下图，接下来就要进行sampling。

step2 sampling
传统的方法，比如Deepwalk，它的Sampling本质上是有两部分，首先，通过random walk的方式进行游走截断，其次，在仍给word2vec中Skip-Gram模型进行embedding之前，用negative sampling的方式去构造样本；这种随机采样的方法会大概率的将热门节点采集为负样本，这种方式适用于语言模型，因为在自然语言中，热门的单词均为无用单词（比如he、she、it、is、the）。对于我们的商品网络，刚好相反，热门商品往往是最重要的样本，如果采用negative sampling的方式去构造样本，模型肯定是学不出来。因此，我们基于边的权重去采样（weighted walk），使采样尽量往热门节点方向游走，以下图为例：

带权重的商品

举个例子来说，假设游走2步，从节点A出发，随机取下一个邻居节点时，如果是random walk算法，它会等概率的游走到B或C节点，但是我们的算法会以7/8的概率取节点C，再会以8/12的概率游走到节点D，最终很大概率上会采出来一条序walk=（A，C，D），对于原始graph，A和D是没有关联的，但是通过weighted walk，能够有效的挖掘出A和D的关系，算法详见：

算法实现是在odps graph平台实现的，一个分布式的图计算平台，离线graph有2亿条边，3千万节点，10分钟跑完所有的数据，实时部分，阿里实现了每分钟最高可更新10w的Graph边的结构，后期阿里会公布如何在分布式odps graph平台实现这套算法的。

step3 Embedding
上一部分介绍了如何构建了带权重的概率图，基于带权重的采样（weighted walk）作为正样本的候选，负样本从用户非购买行为中随机抽样；这一部分主要介绍embedding的部分，将基于weighted walk采出来的序，构造成item-item的pair对，送给embedding模型，构造了一个有监督embedding模型（DNN），规避无监督模型无法离线评估模型效果的问题。模型结构如下图。

有监督的embedding模型（DNN）

模型是在SDNE模型上家里几层全连接层和一层softmax层，但是推文中没有交代ground truth是什么，即物品和物品之间的相似度如何衡量？

三、实现

1. 离线
   a）训练：离线模型在PAI平台上用tensorflow框架实现，抽取了历史50天的全网成交数据，大概抽取3000万节点，构建的graph，在odps graph平台做完weighted walk，产出2亿条样本，也就是item-item的pair对，训练至收敛需要2小时的时间；
   b）预测：从全网所有行为中，随机抽取几十亿条pair对，去做预测，给每对item pair预测一个score；
   c）上线：对每个种子商品取topN的bundle商品，打到搜索引擎的倒排和正排字段，从qp中取出每个用户的种子商品，基于倒排字段召回bundle商品，基于正排字段做bundle排序
   注：在搜索引擎中，倒排是指一个关键词对应很多文章，正排是一篇文章，对应很多关键词。

2. 实时
   用户购买行为，日常和大促差异很大，为了能够实时的捕获用户实时行为，我们在porsche上建了一套实时计算bundle mining的流程：
   a）数据预处理：在porsche上对用户实时日志进行收集，按离线的数据格式处理成实时的数据流  
   b）Sampling：发送给odps graph实时计算平台，构建graph，做weighted walk，生成序，再通过swift消息发出  
   c）Embedding：在porsche上做DNN模型训练和实时预测 
   d）数据后处理：计算item的topN的bundle item list，实时写到dump和引擎
   实时部分用很多东西没有接触过，有待进一步探究

四、实验和结果

双十一预热期间，阿里将bundle算法上线对比基准桶，提升很明显
1、点击：离线版bundle算法对比基准桶，ipv提升13%，实时版bundle算法在此基础上又提升4%，如下图：

五、总结

利用网络结构的传递想，弥补了购买行为稀疏的问题，有效的提升了覆盖率。

六、未来展望

凑单在未来还要继续努力，我们还有不完善的地方，在产品形态上，第一，价格preview没有做出来，用户不知道自己已经加购了多少，还差多少，能用多少优惠券，我们希望下次能在凑单页帮用户实时的算出凑单进度，第二，我们这次没有实时捕捉到入口种子商品，下次我们期望能做到，不同入口点进去，凑单的商品能和入口种子商品强相关；在算法优化上，把新颖性做强，尝试用graph bandit的方法，给用户投放一些没看过的但又相关的品类，根据投放的收益，设计一个合理的机制去explore。

七、启发

1. 在评论中看到“这种算法还是有点不切合实际，就如评论说的，买个转接头，推荐手机。个人觉得，是否考虑弱关联是向下推荐，而不是这种向上推荐，稍微不够智能。”
   作者回复“这个想法很好，我们也尝试过很多，比如lstm，通过graph embedding构造出来的bundle i2i只是我们线上系统中的一维特征，线上的排序系统中还有相似i2i，人群偏好等特征，都是精心加工过的，最终会用一个ltr模型，自动学习各个维度的特征权重，做最终排序~~”

2.将用户信息考虑进去