1.5　Graph Embedding

前面几节我们介绍了由Word Embedding延伸出的Item Embedding等，这些延伸都建立在它们有序列特性的基础上。其实，可延伸的领域还有很多，有些初看起来与序列无关的领域，通过适当变化后，也同样适用。如图1-24所示，左边是人们在电商网站浏览物品的轨迹，这些轨迹呈图结构，通过一些算法（具体有哪些算法，后文会详细介绍）计算后，可以把左图转换为右图这样具有序列样本特征的格式。

Graph Embedding与Word Embedding一样，目的是用低维、稠密、实值的向量表示网络中的节点。目前Graph Embedding在推荐系统、搜索排序、广告等领域非常流行，并且也取得了非常不错的实践效果。那么，应该如何实现Graph Embedding呢？

图（Graph）表示一种“二维”的关系，而序列（Sequence）表示一种“一维”的关系。因此，要将Graph转换为Graph Embedding，一般需要先通过一些算法把Graph变为Sequence；然后通过一些模型或算法把这些Sequence转换为Embedding。

1.5.1　DeepWalk方法

DeepWalk方法首先以随机游走（RandomWalk）的方式在网络中进行节点采样，生成序列，然后使用Skip-Gram模型将序列转换为Embedding。那么，如何从网络中生成序列呢？首先使用RandomWalk的方式进行节点采样。RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。然后给定当前访问起始节点，从其邻居中随机选择一个节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。

获取足够数量的节点访问序列后，使用Skip-Gram模型进行向量学习，最终获得每个节点的Embedding，如图1-25所示。

DeepWalk方法的优点首先是它可以按需生成，随机游走。由于Skip-Gram模型也针对每个样本进行了优化，因此随机游走和Skip-Gram的组合使DeepWalk成为在线算法。其次，DeepWalk是可扩展的，生成随机游走和优化Skip-Gram模型的过程都是高效且平凡的并行化。最重要的是，DeepWalk引入了深度学习图形的范例。

用Skip-Gram方法对网络中节点进行训练。那么，根据Skip-Gram的实现原理，最重要的就是定义Context，也就是Neighborhood。在自然语言处理中，Neighborhood是当前Word周围的字，本文用随机游走得到Graph或者Network中节点的Neighborhood。

1.5.2　LINE方法

DeepWalk只适用无向、无权重的图。在2015年，微软亚洲研究院发布了LINE（Large-scale Information Network Embedding，大型信息网络嵌入）。LINE使用边采样方法克服了传统的随机梯度法容易出现的Node Embedding聚集问题，同时提高了最后结果的效率和效果，如图1-26所示。

用学习到的Embedding作为输入，使用t-SNE包，将作者映射到二维空间。节点的颜色表示作者所属的技术领域：红色为“数据挖掘”，蓝色为“机器学习”，绿色为“计算机视觉”。

从图1-26可以看出：

1）使用图分解（Graph F，GF）得到的可视化意义并不大，属于同一领域的作者并不聚集在一起。

2）DeepWalk的效果较好，但是许多属于不同领域的作者紧紧聚集在中心区域，其中大部分是高度顶点。这是因为DeepWalk使用随机游走的方法来扩展顶点的邻居，由于其具有随机性，会给度数比较高的顶点带来很多噪音。

3）LINE（2nd）执行得相当好，并生成了有意义的网络布局（内容相似的节点分布得更近）。

LINE方法可以应用于有向图、无向图以及边有权重的网络，并能够通过将一阶、二阶的邻近关系引入目标函数，使最终学习得到的Node Embedding的分布更为均衡、平滑。

1阶相似度（first-order proximity）：用于描述图中成对顶点之间的局部相似度，可形象化描述为，若节点之间存在直连边，则边的权重即为两个顶点的相似度；若不存在直连边，则1阶相似度为0。如图1-27所示，节点6和7之间存在直连边，且边权较大，则认为两者相似且1阶相似度较高，而5和6之间不存在直连边，则两者间1阶相似度为0。

2阶相似度（second-order proximity）：如图1-27所示，虽然节点5和6之间不存在直连边，但是它们有很多相同的相邻节点（1, 2, 3, 4），表明节点5和6也是相似的，而1阶相似度显然并不能描述这种关系，所以会用到2阶相似度来描述。

1.5.3　node2vec方法

在DeepWalk和LINE的基础之上，斯坦福大学在2016年发布了node2vec。该算法不但关注了同质性和结构性，更可以在两者之间进行权衡。

图1-28展示了node2vec方法的两种搜索策略，其中，BFS表示广度优先，DFS表示深度优先。node2vec所体现的网络的同质性和结构性在推荐系统中也是可以被直观地解释的。同质性相同的物品很可能是同品类、同属性或者经常被一同购买的物品，而结构性相同的物品则是各品类的爆款、最佳凑单商品等拥有类似趋势或者结构性属性的物品。毫无疑问，同质性和结构性在推荐系统中都是非常重要的特征表达。由于node2vec的这种灵活性，以及发掘不同特征的能力，甚至可以把不同node2vec生成的Embedding融合输入后续深度学习网络，以保留物品的不同特征信息。

1.5.4　Graph Embedding在阿里的应用

以淘宝为例，每天用户浏览商品时都会留下轨迹，如图1-29所示。

这些轨迹或图形中隐含着丰富的信息，如用户对物品（Item）的偏好、用户相似关系、各物品的优劣、物品广告的宣传效果、物品之间的依赖关系、物品与用户的关系等，如何通过这些信息对用户进行个性化推荐或优先排序就显得非常重要。

阿里工程师把他们的经验汇集成论文—Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba，在业界引起了很大反响。

阿里为此把整个过程分成如图1-29所示的四个步骤。

1）根据用户的行为数据，构建每个用户在每次会话中的浏览序列。例如，用户U2两次访问淘宝，第一次查看了两个物品B和E，第二次查看了三个物品D、E和F。

2）通过用户的行为数据，建立一个商品图（Item Graph），可以看出，因为用户U1先后购买了物品A和物品B，所以物品A与B之间会产生一条由A到B的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。

3）通过随机游走方式对图进行采样，重新获得物品序列。

4）使用Skip-Gram模型进行嵌入。

在具体实施过程中，主要可能遇到如下几个技术问题。

• 可扩展性（Scalability）问题。尽管已经存在很多可以在小规模数据集上很好地工作的推荐方法（例如数百万的用户和物品），但它们通常会在淘宝的海量数据集上试验失败。
• 数据稀疏性（Sparsity）问题。由于用户趋向于只与小部分的物品交互，特别是当用户或物品只有少量交互时，很难训练一个精准的推荐模型，这通常被称为“稀疏性”问题。
• 冷启动（Cold Start）问题。在淘宝，每小时均会有数百万的新物品持续上传。这些物品没有用户行为，所以，处理这些物品或者预测用户对这些物品的偏好是个很大的挑战，这被称为“冷启动”问题。

针对这些问题，阿里淘宝团队提出了基于Graph Embedding的算法来解决。具体方法如下。

1. Base Graph Embedding（BGE）

使用DeepWalk算法来学习在图1-29b中每个节点的Embedding。假设M表示图1-29b的邻近矩阵，M ij表示从节点i指向节点j的加权边。先通过随机游走的方式生成节点序列，然后在这些序列上运行Skip-Gram算法。

2. Graph Embedding with Side Information（GES）

该方案增加物品的额外信息（例如category、brand、price等）以丰富物品表征力度。针对每件物品（Item），将得到item_embedding、category_embedding、brand_embedding、price_embedding等Embedding信息，然后对这些信息求均值，用于表示该物品。

3. Enhanced Graph Embedding with Side Information（EGES）

该组合模型在表示各item_embedding时，会对物品和额外信息的Embedding施加不同的权重。权重值通过模型训练得到。EGES的流程图见图1-30。

关于图1-30，有几点需要说明。

1）SI表示额外信息（Side Information），其中“SI 0”表示item自身。

2）稀疏特征（Sparse Feature）代表物品和额外信息的ID信息，类似于独热向量。

3）稠密嵌入（Dense Embedding）是物品和相应的额外信息的Embedding信息。

4）α 1，α 2，…，α n分别代表物品和额外信息的Embedding权重。

5）隐藏层是物品和它相应的额外信息的聚合Embedding。

6）Softmax采样分类器中的N代表采样的负样本，P代表正样本。

目前能进行嵌入的“工具”只有Skip-Gram，只能处理类似序列这样一维的关系输入。因此，当我们需要在二维关系上进行“采样”时，可以使用随机游走算法实现。

1.5.5　知识图谱助力推荐系统实例

将知识图谱作为辅助信息引入推荐系统中，可以有效解决传统推荐系统存在的稀疏性和冷启动问题，近几年有很多研究人员在做相关的工作。目前，将知识图谱特征学习应用到推荐系统中的方式主要有三种：依次学习（One-by-One Learning）、联合学习（Joint Learning）以及交替学习（Alternate Learning）。

1. 依次学习

依次学习的具体学习方法是首先使用知识图谱特征学习得到实体向量和关系向量，然后将这些低维向量引入推荐系统，学习得到用户向量和物品向量，如图1-31所示。

2. 联合学习

联合学习是指将知识图谱特征学习与推荐算法的目标函数结合，使用端到端（end-to-end）的方法进行联合学习，如图1-32所示。

3. 交替学习

交替学习是指将知识图谱特征学习和推荐算法视为两个分离但又相关的任务，使用多任务学习（Multi-Task Learning）的框架进行交替学习，如图1-33所示。