深度学习中不得不学的 Graph Embedding 方法

之前已经有无数同学让我介绍一下 Graph Embedding，我想主要有两个原因：

一是因为Graph Embedding 是推荐系统、计算广告领域最近非常流行的做法，是从 word2vec 等一路发展而来的 Embedding 技术的最新延伸；
二是因为已经有很多大厂将 Graph Embedding 应用于实践后取得了非常不错的线上效果。

那我们今天就一起讨论一下 Graph Embedding 的主要做法和前沿应用。

word2vec 和由其衍生出的 item2vec 是 embedding 技术的基础性方法（我在之前的文章中也详细介绍了二者的技术原理，王喆：万物皆 Embedding，从经典的 word2vec 到深度学习基本操作 item2vec），但二者都是建立在“序列”样本（比如句子、推荐列表）的基础上的。而在互联网场景下，数据对象之间更多呈现的是图结构。典型的场景是由用户行为数据生成的和物品全局关系图（图 1），以及加入更多属性的物品组成的知识图谱（图 2）。

图 1 由用户行为序列生成的物品全局关系图 (引自阿里论文)

图 2 由属性、实体、各类知识组成的知识图谱

在面对图结构的时候，传统的序列 embedding 方法就显得力不从心了。在这样的背景下，对图结构中间的节点进行表达的 graph embedding 成为了新的研究方向，并逐渐在深度学习推荐系统领域流行起来。

经典的 Graph Embedding 方法——DeepWalk

早期影响力较大的 graph embedding 方法是 2014 年提出的 DeepWalk，它的主要思想是在由物品组成的图结构上进行随机游走，产生大量物品序列，然后将这些物品序列作为训练样本输入 word2vec 进行训练，得到物品的 embedding。图 3 用图示的方法展现了 DeepWalk 的过程。

图 3 DeepWalk 的算法流程（引自阿里论文）

如图 3，整个 DeepWalk 的算法流程可以分为四步：

图 a 展示了原始的用户行为序列
图 b 基于这些用户行为序列构建了物品相关图，可以看出，物品 A，B 之间的边产生的原因就是因为用户 U1 先后购买了物品 A 和物品 B，所以产生了一条由 A 到 B 的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
图 c 采用随机游走的方式随机选择起始点，重新产生物品序列。
图 d 最终将这些物品序列输入 word2vec 模型，生成最终的物品 Embedding 向量。

在上述 DeepWalk 的算法流程中，核心是第三步，其中唯一需要形式化定义的是随机游走的跳转概率，也就是到达节点 vi 后，下一步遍历 vi 的临接点 vj 的概率。如果物品的相关图是有向有权图，那么从节点 vi 跳转到节点 vj 的概率定义如下：

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

如果物品相关图是无相无权重图，那么跳转概率将是上面公式的一个特例，即权重 Mij 将为常数 1，且 N+(vi) 应是节点 vi 所有“边”的集合，而不是所有“出边”的集合。

DeepWalk 的进一步改进——Node2vec

2016 年，斯坦福大学在 DeepWalk 的基础上更进一步，通过调整随机游走权重的方法使 graph embedding 的结果在网络的 ** 同质性（homophily）和结构性（structural equivalence）** 中进行权衡权衡。

具体来讲，网络的“同质性”指的是距离相近节点的 embedding 应该尽量近似，如图 4，节点 u 与其相连的节点 s1、s2、s3、s4 的 embedding 表达应该是接近的，这就是“同质性“的体现。

“结构性”指的是结构上相似的节点的 embedding 应该尽量接近，图 4 中节点 u 和节点 s6 都是各自局域网络的中心节点，结构上相似，其 embedding 的表达也应该近似，这是“结构性”的体现。

图 4 宽度优先搜索（BFS）和深度优先搜索（DFS）示意图

为了使 Graph Embedding 的结果能够表达网络的同质性，在随机游走的过程中，需要让游走的过程更倾向于宽度优先搜索（BFS），因为 BFS 更喜欢游走到跟当前节点有直接连接的节点上，因此就会有更多同质性信息包含到生成的样本序列中，从而被 embedding 表达；另一方面，为了抓住网络的结构性，就需要随机游走更倾向于深度优先搜索（DFS），因为 DFS 会更倾向于通过多次跳转，游走到远方的节点上，使得生成的样本序列包含更多网络的整体结构信息。**（通过 **

@张备

** 同学的提醒，这里其实是写反了，BFS 应该反映了结构性，DFS 反而反应了同质性，大家可以深度思考一下这是为什么，欢迎在评论区讨论）**

那么在 node2vec 算法中，是怎样控制 BFS 和 DFS 的倾向性的呢？主要是通过节点间的跳转概率。图 5 显示了 node2vec 算法从节点 t 跳转到节点 v 后，下一步从节点 v跳转到周围各点的跳转概率。

图 5 node2vec 的跳转概率

形式化来讲，从节点 v 跳转到下一个节点 x 的概率为

其中是边 vx 的权重，的定义如下：

其中，dtx 指的是节点 t 到节点 x 的距离，参数 p 和 q 共同控制着随机游走的倾向性。参数 p 被称为返回参数（return parameter），p 越小，随机游走回节点 t 的可能性越大，node2vec 就更注重表达网络的同质性，参数 q 被称为进出参数（in-out parameter），q 越小，则随机游走到远方节点的可能性越大，node2vec 更注重表达网络的结构性，反之，当前节点更可能在附近节点游走。

node2vec 这种灵活表达同质性和结构性的特点也得到了实验的证实。图 6 的上图就是 node2vec 更注重同质性的体现，可以看到距离相近的节点颜色更为接近，而图 6 下图则是结构特点相近的节点的颜色更为接近。

图 6 node2vec 实验结果

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

阿里的 Graph Embedding 方法 EGES

2018 年阿里公布了其在淘宝应用的 Embedding 方法 EGES（Enhanced Graph Embedding with Side Information），其基本思想是在 DeepWalk 生成的 graph embedding 基础上引入补充信息。

如果单纯使用用户行为生成的物品相关图，固然可以生成物品的 embedding，但是如果遇到新加入的物品，或者没有过多互动信息的长尾物品，推荐系统将出现严重的冷启动问题。为了使“冷启动”的商品获得“合理”的初始 Embedding，阿里团队通过引入了更多补充信息来丰富 Embedding 信息的来源，从而使没有历史行为记录的商品获得 Embedding。

生成 Graph embedding 的第一步是生成物品关系图，通过用户行为序列可以生成物品相关图，利用相同属性、相同类别等信息，也可以通过这些相似性建立物品之间的边，从而生成基于内容的 knowledge graph。而基于 knowledge graph 生成的物品向量可以被称为补充信息（side information）embedding 向量，当然，根据补充信息类别的不同，可以有多个 side information embedding 向量。

那么如何融合一个物品的多个 embedding 向量，使之形成物品最后的 embedding 呢？最简单的方法是在深度神经网络中加入 average pooling 层将不同 embedding 平均起来，阿里在此基础上进行了加强，对每个 embedding 加上了权重，如图 7 所示，对每类特征对应的 Embedding 向量，分别赋予了权重 a0，a1…an。图中的 Hidden Representation 层就是对不同 Embedding 进行加权平均操作的层，得到加权平均后的 Embedding 向量后，再直接输入 softmax 层，这样通过梯度反向传播，就可以求的每个 embedding 的权重 ai(i=0…n)。

图 7 阿里的 EGES Graph Embedding 模型

在实际的模型中，阿里采用了而不是 aj 作为相应 embedding 的权重，一是避免权重为 0，二是因为在梯度下降过程中有良好的数学性质。

阿里的 EGES 并没有过于复杂的理论创新，但给出一个工程性的结合多种 Embedding 的方法，降低了某类 Embedding 缺失造成的冷启动问题，是实用性极强的 Embedding 方法。

时至今日，Graph Embedding 仍然是工程和学术领域研究和实践的热点，除了本节介绍的 DeepWalk，Node2vec，EGES 等主流的方法，还有 LINE，SDNE 等方法也很流行，感兴趣的同学可以参考我之前的综述性文章王喆：Embedding 从入门到专家必读的十篇论文或者直接阅读论文。

按照惯例留一个讨论题，希望大家踊跃发表意见，让我们所有人都从讨论中受益：

在使用 Graph Embedding 生成物品的 Embedding 之后，应该如何生成用户的 Embedding？除了 Average Pooling 有更好的方法吗？