场景：帮助用户找到商品，达成某个满减门槛（比如满400减50），完成跨店凑单。
对场景的理解：认为凑单的重要场景是当用户已经加购了商品A，还想找一个能一起打包买的商品B，而不是想找跟A相似的商品C。
GraphEmbedding 思路：学习节点隐表示向量，在一个连续向量空间中对节点的关联关系进行编码，便于计算节点之间的关联关系，同时，graph具有传播能力，通过random walk可以挖掘多度关系，能有效的提升覆盖度，扩大召回。
比如deep walk，是语言模型和无监督学习从单词序列扩展到图结构上的一个典型方法，该方法将截断游走的序列当成句子进行学习，之后采用word2vec中Skip-Gram模型进行训练，得到每个节点的embedding向量。Line只针对边进行采样，Node2vec可以调节参数来进行BFS或者DFS的抽样。
所以Graph Embedding的基本思路是，对graph进行采样（Sampling），采出来的序构建模型（Embedding）。
主要技术：
我们主要有三方面的工作，一是，基于用户购买行为构建graph，节点：商品，边：商品间同时购买的行为，权重：同时购买的比重，可以是购买次数、购买时间、金额等feature；二是，基于权重Sampling（weighted walk）作为正样本的候选，负样本从用户非购买行为中随机抽样；三是，embedding部分将无监督模型升级成有监督模型，将基于weighted walk采出来的序，构造成item-item的pair对，送给有监督模型（DNN）训练。下图是算法框架图。
1） 构建图（带权图）
random walk等传统方法不适用商品网络，商品节点动辄上千万，其中大部分节点的关联性是很弱的，也就是冷门商品居多，只有少部分商品构建的graph是热点，如果采用random walk去采样，会采出很多冷门节点的序列，所以我们基于边的权重去采样（weighted walk），使采样尽量往热门节点方向游走，这样采样出来的样本置信度才更高。
因此，我们的输入是一个带weight的graph ，Graph定义：G = （V，E，W），V = vertex （顶点或者节点，在bundle的问题中，特指商品），E = edge（边，在bundle的问题中，特指共同购买） ，W = weight（边的权重，共同购买的次数、时间），如下图，接下来就要进行sampling。
2） 对图进行Sampling(构造序列)
传统的方法，比如deep walk，它的Sampling本质上是有两部分，首先，通过random walk的方式进行游走截断，其次，在仍给word2vec中Skip-Gram模型进行embedding之前，用negative sampling的方式去构造样本；这种随机采样的方法会大概率的将热门节点采集为负样本，这种方式适用于语言模型，因为在自然语言中，热门的单词均为无用单词（比如he、she、it、is、the）。
对于我们的商品网络，刚好相反，热门商品往往是最重要的样本，如果采用negative sampling的方式去构造样本，模型肯定是学不出来。因此，我们基于边的权重去采样（weighted walk），使采样尽量往热门节点方向游走。
算法解释：遍历每个节点Vi，以一定的概率对下一个节点进行选择。选择每个相邻节点的概率为 边权重/所有出度。
3） Embedding
将基于weighted walk采出来的序，构造成item-item的pair对，送给embedding模型，我们构造了一个有监督embedding模型（DNN），规避无监督模型无法离线评估模型效果的问题。
实现（线上不需要计算）
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和引擎
链接：https://yq.aliyun.com/articles/414733
