本文梳理了近几年主流的图嵌入（Graph Embedding）模型，并辅以相应的工业界应用，旨在通过算法原理+业务应用的方式更好地帮助大家了解这一领域的发展历史和现状，也希望能为准备入坑 Graph Embedding 的同学提供一些有价值的信息。笔者个人水平有限，欢迎大家批评指正。
1. 概述与基础
图结构(Graph)广泛存在于现实各种应用场景中。比如社交媒体，用户之间的关注关系可以构成一个庞大的社交图网络；又比如推荐系统，用户对商品的购买、浏览和评分等行为可以抽象成用户和商品的交互图。然而，现实中的图结构大多都很复杂。一个复杂的图网络中可能包含十亿个节点、千万条边和上十万个簇，且不同的边可能代表着节点之间不同的关系。因此，如何有效地对图结构信息进行建模是学术界和工业界持续关注的焦点。
近年兴起的图嵌入(Graph Embedding)方法，为图结构的建模提供了很好的解决思路，并在工业界被广泛的应用。嵌入(Embedding)的思想是：把图中的节点或者边嵌入到一个低维的向量空间中，且节点或边在该低维空间的关系能比较完整地保留原图的结构信息（图 1）。换而言之，图嵌入的过程等价于对图中节点或边进行降维表示学习的过程。
图1 图嵌入过程示例
本文介绍了常见的 Graph Embedding 算法及其基本原理，另外还会对 Graph Embedding 在工业界（尤其是我司）实际业务场景中的落地情况进行简单地介绍和总结。
1.1 Word2vec 介绍[1]
说到 Graph Embedding，就不得不从 Word2vec 算法进行切入。2013 年，Google 的 Mikilov 等大神们提出的 Word2vec 算法，正式为我们开启了“万物皆可 embedding”的时代。Word2vec 最早应用在自然语言处理领域（NLP）。大神们认为：同一语义上下文的单词之间存在天然的语义关系。例如：如果把“拜仁赢得欧冠冠军。”这句话看作是同一个语义上下文，“拜仁”这个词与“赢得”，“欧冠”和“冠军”等单词有比较强的语义关系。为了捕捉这一语义关系，Word2vec 利用同一上下文的单词来学习各自的词向量表示（Word Embedding）。
图2 Word2vec滑动窗口示例
具体地，Word2vec 利用语义窗口来捕捉每个句子中的语义上下文，并通过对语义窗口进行滑动，学习每一个句子序列中不同语义上下文窗口中的单词 embedding。还是以句子“拜仁赢得欧冠冠军。”为例，如图 2，假设滑动窗口的长度为 1，当“赢得”这个词位于滑动窗口的中心时，那么“拜仁”，和“欧冠”这两个词就是“赢得”的上下文。因此，我们可以把“赢得”定义为中心词(Center Word)，把“拜仁”和“欧冠”这两个上下文词语定义为背景词(Context Word)。在 Word2vec 中，每个词语都关联着两个词向量，分别为中心词向量和背景词向量，取决于当前时刻该词语的角色。为了学习每个单词的中心词向量和背景词向量，Word2vec 提出了两种模型，分别是以中心词预测背景词的 Skip-gram 模型，和以背景词去预测中心词的 C-bow 模型。由于它们的模型结构正好相反且前者是目前被使用更多的模型，本文将以 Skip-gram 为例提供关于 Word2vec 的进一步解释。
1.1.1 Skip-gram
在 Skip-gram 模型中，Word2vec 旨在通过中心词来最大化背景词出现的联合概率分布，并以此对中心词和背景词进行有效的嵌入表示（例如，当前以“赢得”为中心词进行上下文预测时，单词“拜仁”和“欧冠”出现的概率需要是最大的）：
图3 Skip-gram模型图
1.1.2 负采样机制
1.1.3 Word2vec 与矩阵分解
在面对大规模语料时，基于矩阵分解的操作是复杂且耗时的，尤其是当矩阵比较稠密的时候。相比之下，Word2vec 中基于负采样方法的训练过程要简单和高效许多。这也是基于负采样的 Skip-gram 模型被普遍采用的原因之一。希望对 Word2vec 有更深入理解的同学，可以去拜读 Levy 他们的文章。
1.1.4 工业界应用：Item2vec[5]
鉴于 Word2vec 在学习单词表示时所达到的优异表现，在 2016 年，微软尝试直接把它应用在推荐系统中基于商品协同过滤的场景下，旨在学到商品的向量表示，更好地建模商品和商品之间的关系。
图4 出现在同一session中的游戏订单
Item2vec 认为，和自然语言中，同一语义上下文的单词语义相近类似。在用户每个 Session 中下单的所有商品都存在一定的关联（如图 4 中的 Snowboard Party 和 Drag Racing 3D）。所以，它把同一个 session 中被下单的商品集（Item Set）看作同一个上下文，用该商品集中的商品去实现两两之间的预测，并采用基于负采样的 Skip-gram 模型学习每个商品的 embedding。
最终，通过实验对比，对 Word2vec 进行直接迁移的 Item2vec 模型所学习到的商品 embedding 的效果要优于推荐中传统的矩阵分解模型 SVD。
图5 Item2vec和SVD关于商品向量的t-SNE可视化结果
1.1.5 工业界应用：Airbnb Embedding[6]
个人认为，Airbnb 的这篇论文是 Word2vec 结合业务场景改进的一次成功实践，该工作也获得了 KDD’ 2018 Applied Data Science Track 的 best paper。它的模型简单不花哨，但工程性极强，在 Word2vec 的基础上很好地融入了 Airbnb 自身的业务特点，并取得了很好的落地效果。强烈推荐大家有时间可以针对论文进行仔细阅读和思考，毕竟是出自 Mihajlo 的工作。
Airbnb 是一个民宿租赁的两方平台（Two-side Platform），同时对房东和租客开放。房东可以在平台上发布房源（listing）信息，租客根据需求搜索、浏览并选取自己心仪的房源进行预定。同时，房东也可以根据租客的信息决定是否接受租客的预定。此外，一处房源同一时间只能服务一个订单。此类两方平台的业务特色目前也广泛存在于现实世界中，例如：Airbnb，滴滴和 Uber 等。它们的业务性质与传统的电商和社交网络业务并不一致。在 Airbnb 平台，它们希望利用平台上有效的房东和租客行为（例如：点击浏览(click)，预定(booking)和拒绝预定(reject)），为房源学习到有效的 embedding，从而在搜索或相似房源推荐中向用户推荐更符合他们偏好的房源信息。
1.1.5.1 房源（Listing）Embedding
为了将 Word2vec 应用在自己的业务场景，Mihajlo 等人结合 Airbnb 自身业务场景提出的调整策略可总结为以下 3 点：
- 同一个 Session 中的用户行为可以看做同一个序列，可类比成 NLP 中的一个句子。当一个用户的两次点击行为之间相距超过 30 分钟，则把新的点击行为当作另一个 Session 的开始；
- 把 Session 中的 booked listing 当作是一个全局上下文（Global Context）。如图 6 所示，每次用 central listing 预测 context listing 时，也需要预测 booked listing；
- 在负采样时，不仅需要做基于全局的负采样，也要基于当前 central listing 的地理位置进行局部的负采样。
图6 用于Listing Embedding学习的Skip-gram模型
其中，策略二和三非常好地结合了 Airbnb 的业务需求。作为一个租赁平台，其主要目的是希望用户最终成功下单。策略二把每个 Session 中最终的 booked listing 作为 global context，让它和同一 Session 中其他仅点击而未下单的 listing 尽可能的相似。在相似房源推荐的场景中，策略二希望为用户推荐他们可能下单的 listing，而不仅仅是相似的 listing。此外，Airbnb 的用户在考虑下单时，更多是建基于特定的地域环境进行决策，例如：当用户在浏览北京朝阳区的房源时，大概率不会跳跃考虑深圳南山的房源。然而，Word2vec 中提出的基于全局进行负采样的策略，无法保证同一地域中的 listing embedding 具有很好的区分性。所以，本文在全局负采样的基础上，提出了基于中心 listing 的地理位置进行局部地区的负采样策略。
图7 利用Listing Embedding召回的相似Listings结果
为了验证基于公式（6）学习到的 embedding 是否能成功捕捉 listing 之间的关联，论文中也提供了基于 listing embedding 做近邻召回的可视化结果。从图 7 我们可以看出，虽然 Airbnb 只利用了用户对 listing 的点击和订购的信息学习 embedding。但是，基于左边 listing 召回的三个最相似的 listing 无论从房子结构还是租赁价格等方面，都和目标 listing 比较相似。此外，在相似房源推荐的场景中，该版本的 listing embedding 也比前一个版本的模型对线上点击率指标提高了20% 。可以说，Airbnb embedding 的提出，在他们业务平台上还是收到了非常不错的效果。
1.1.5.2 冷启动 Listing
在 Airbnb，每天都有很多房主上传新的 listing 供租客挑选。新 listing 没有订购和浏览行为，无法学出它们的 embedding，这是很多业务场景中常见的冷启动现象。为了解决这类新 listing 的冷启动问题，本文作者提出以新 listing 地理位置 10 英里以内的空间作为圈定条件，挑选出属性（价格，房型等）与当前 listing 最接近的三个 listing。并通过对这三个 listing 的 embedding 取平均，得到新 listing 的 embedding 表示。通过这一操作，他们每天可以额外覆盖98%的新 listing。
1.1.5.3 长期兴趣建模
Listing embedding 仅仅是基于用户的 Session 行为进行学习。Mihajlo 等作者认为，用户在一个 Session 内的点击和订购行为仅能反映其短期兴趣，更多适用于相似房源推荐的应用场景。相比之下，对用户长期兴趣的建模可以更好地为用户提供个性化推荐。例如：同一个用户在伦敦和纽约的订单信息，可能有助于为他推荐洛杉矶的 listing。基于这一概念，论文也尝试通过用户长期的订购序列对用户的长期兴趣进行建模。
图8 User\_type（蓝色）和Listing\_type（橙色）Embedding学习的Skip-gram模型
此外，在 Airbnb，对于每一个订单，房东对租客也有选择的权利。比如，房东可能会认为没有详细用户信息的租客并不可靠，而拒绝此类租客的预定。为了防止给用户推荐他们可能被拒绝的 listing，在对 user\_type 和 listing\_type 的 embedding 进行学习时，如图 8 所示，在利用 central item 对 context user\_type 和 context listing\_type 进行预测时，作者们把房东拒绝预定（reject）的行为也加入考虑。在学习 user\_type embedding 时，reject 的 listing\_type embedding 将会作为负样本进行学习。同样地，在学习 listing\_type embedding 时，被 reject 的 user\_type embedding 将会被作为负样本。具体训练细节，敬请阅读 Airbnb 的论文。题外话：在搜推的场景下，Mihajlo 他们发表的 Airbnb 三部曲的工作都非常推荐大家研读一下。
2. 图嵌入（Graph Embedding）
上文花了大量的篇幅介绍 Word2vec 及其在工业界的一些应用，主要是因为 Word2vec 是近年 Graph Embedding 方法学习图节点嵌入表示的基础。但是，正如前文所述，无论是 Word2vec 还是 Airbnb embedding 等工业界应用，其使用场景均是利用滑动的上下文窗口在序列数据上捕捉节点之间的关系。图结构作为一种空间拓扑结构，应该如何把 Word2vec 这一高效的语言表示学习模型应用于图拓扑结构呢？
2.1 DeepWalk[7]
Perozzi 等人在 KDD 2014 提出的DeepWalk模型，是谈论 Graph Embedding 方法绕不过去的经典模型之一，它成功在 Word2vec 和 Graph Embedding 之间架起了连接的桥梁。为了学习图中每个节点的嵌入表示，DeepWalk 提出了一种二阶段的图嵌入学习框架:
- 阶段一：采用截断式随机游走（Truncated Random Walks）的方式把图中每个节点的局部拓扑结构转换成序列信息；
- 阶段二：把 Word2vec 模型应用于阶段一产生的序列数据，学习序列中每个节点的 embedding 表示。
图9 DeepWalk在电商推荐场景下的算法流程概览
图 9 是 DeepWalk 模型在推荐场景下的应用。图 9（a）显示的是不同用户在不同 Session 中的 item 点击序列。用 Item2vec 或 Airbnb embedding 的方法，Word2vec 模型可以直接在这些序列信息上对节点进行嵌入学习。但图中用户的 Session 行为都偏短，会导致序列中 item 学习出来的 embedding 质量并不理想。DeepWalk 会根据每个 Session 中 item 的共现信息和出现的次序，构建一个全局的 item 有向图（图 9（b））。然后以每个 item 节点为起始节点，进行截断式随机游走产生新的 item 序列。从图 9（c）中可以看出，因为随机游走对图结构的局部探索能力，我们可以得到一些原来并没有见过的 item 序列，例如：“ABE”序列。因此，后续的表示学习模型可以拥有更丰富的数据来学习每个节点的 embedding。最后，通过随机游走生成的 item 序列都会被送入 Skip-gram 模型中进行节点的 embedding 学习。
值得一提，随机游走不仅可以完成图结构到序列信息的转换，还可以并行地为每个节点生成序列信息，这为 DeepWalk 模型应用在大规模图结构上提供了可行性。腾讯 TEG 数平的 Angel 团队在公司太极平台提供了非常丰富的图算法组件供使用。DeepWalk 这种二阶段的图嵌入学习框架，也被后续很多 Graph Embedding 方法所采用。所以，DeepWalk 在学术界和工业界，都是一个很常见的 Graph Embedding baseline。
2.1.1 工业界应用: EGES[8]
EGES 是阿里巴巴和港科大发表在 KDD‘18 关于推荐召回的工作。细心的读者可能会发现，它和 Airbnb 的工作发表在同年同一个会议上，推荐领域几项经典的工作（MMoE 等）都在同一年 KDD 出现，这一盛况也不是那么的常见，哈哈。
EGES 的作者们认为，传统的协同过滤模型只能建模商品之间表面的共现关系，而基于图结构的 DeepWalk 模型通过随机游走的模式，可以捕捉到商品之间的高维（High-order）相似性（图 9）。所以，他们把 DeepWalk 应用在阿里的 item embedding 学习中，并把学习到的 item embedding 用在手淘推荐的召回阶段。但是，作为国内最大的电商平台，淘宝每天都有上千万新上架的商品，这些冷启动的商品并没有行为信息，从而导致原版的 DeepWalk 模型无法学到它们的 embedding 表示。为了解决冷启动的问题，他们尝试利用这些商品关联的类目、品牌等边信息（Side Information）。此外，他们也认为，在电商场景中，商品之间的关系和自然语言处理中单词之间的关系不完全相同。例如：同一个品牌的商品之间在向量空间中的位置应该接近。因此，他们在 DeepWalk 的基础上，提出了加入 Side Information 的 Graph Embedding 模型。这也是 EGES（Enhanced Graph Embedding with Side Information）名字的由来。
图10 item embedding和边信息embedding加权融合过程
图11 EGES在淘宝平台的实验结果
虽然 EGES 只是对 DeepWalk 模型做了简单的修改，但是从图 11 中我们可以看出，加入边信息学习后的 item embedding 在冷启商品的召回结果和线上七天 ab 测试的 CTR 结果中，都取得了不错的效果。
当然，发表于 18 年的 EGES 并不复杂，通过和 DeepWalk 的对比，可以发现它仅是结合业务对 DeepWalk 进行了有限的修改。那么，感兴趣的同学可以思考一下，EGES 后续还有什么可以改进的地方呢？这几年一直深耕深度学习的各位可能第一时间就想到了 Attention 机制，包括作者们也在文章的 future work 中提到了关于 Attention 的尝试。但笔者认为，EGES 可能早在 Attention 机制盛行之前就已经在阿里内部提出，所以文章中并没有做基于 attention 的尝试和对比。另外，虽然加入 attention 机制无疑可以减少模型需要训练的参数，同时为模型带来更多的灵活性，但是否也会使得模型计算变得更复杂反而降低了 embedding 的质量？另外，EGES 把用户的 Session 行为根据序列关系转换成了有向图，有向图和无线图在 item embedding 学习上是否差别很大？毕竟在电商的推荐场景中，同一个 Session 内，用户购买商品的序列可能并不一定这么明显。
最后，看点快报在 18 年也尝试在图文召回中利用 EGES 加入媒体、类别和 tag 等边信息来学习图文的 embedding 表示[9]。
2.1.2 工业界应用: 腾讯新闻[10]
DeepWalk 在腾讯新闻的个性化推荐场景中也有被使用到。
图12 腾讯新闻Graph Embedding建模过程
如图 12 所示，新闻的同事们提出的 Graph Embeddnig 的整体思路与 DeepWalk 类似，他们主要的改进工作体现在图构建阶段，希望在构建图阶段，通过改变节点之间边的权重来调整随机游走所得到的的序列结果，使得生成的训练节点序列更符合腾讯新闻的业务场景。在基于腾讯新闻的用户行为数据构建图的时候，新闻同事们提出了两点有意思的思考：
- Item 的曝光信息极有可能影响 item 之间的共现，比如曝光更多的 item 往往更容易共现。因此，item 曝光信息也应该反映在图中 item 节点之间的边权重上；
- Item 之间的推荐关系是有向的，新闻场景中可以在冷门内容后推荐相关的热门新闻，但是未必适合在热门新闻后推荐相关的冷门内容。
基于这两个前提，新闻的同事提出了一种叫做 ACF 的算法计算图中节点之间的边权重。最终学习到的 item embedding 在视频召回中上线，并在点击 vv 和总 vv 上都取得了明显的提升。
2.2 Node2vec[11]
Node2vec 是图领域的男神 Jure Leskovec 课题组的工作。Jure 在图表示领域做出了许多贡献，包括 PinSage，GraphRNN 和 19 年 ICLR 的“How Powerful Are Graph Neural Networks?”等经典工作。所以这篇 Node2vec 还是需要详细介绍一下。
Node2vec 的出发点在于，在现实世界的图结构中，节点间的相似性广泛地存在两种形态:
- 一种是和同一社区（Community）内近邻节点之间的同质性（Homophily）；
- 一种是和担任类似结构角色的节点之间的结构性（Structural Equivalence）。
图13 Node2vec节点关系示例
具有同质性相似的节点之间往往处在同一个小社区内，并且相互之间具有紧密的连接性。相比之下，具有结构性相似的节点之间并不一定是邻接节点，但他们处在图中类似的结构之中。如图 13 中，节点 和节点 之间的相似性属于同质性，而节点 和节点 之间的相似性则属于结构性。这两种相似性分别需要用基于广度优先搜索（BFS）和基于深度优先搜索（DFS）的策略对图的局部结构进行探索。而 DeepWalk 所采用的随机游走策略更多是一种 DFS 的探索策略。为了完整地建模图中这两种相似性，Node2vec 提出了一种有偏的随机游走（Biased Random Walk）策略。
2.2.1 有偏随机游走（Biased Random Walk）
图14 Node2vec的有偏随机游走策略示例
值得一提的是，到底是BFS 更适合捕捉图的结构信息而 DFS 更能捕捉图的同质信息？还是BFS 更适合捕捉图的同质信息而 DFS 更能捕捉图的结构信息？这个问题一直困扰了很多 Node2vec 的读者，包括广告界的知乎大 V 王喆大神，也曾混淆过这里的关系，并且专门写了一篇知乎博客对其进行解释[12]。所以这个问题笔者也想在这里和大家一起探讨一下。非常有趣的一点是，在文章的 Introduction 部分，作者们表达的信息倾向于 BFS 更适合捕捉图的同质信息而 DFS 则更适合结构信息，包括作者们提供的图解（图 13）也让读论文的同学们有这样的理解。但是，从论文的方法部分开始，作者明确提出，BFS 由于可以对微观视角（Microscopic View）的结构进行更清楚的探索，所以更能捕捉图的结构信息。相比之下，DFS 则更可以在局部图中探索宏观视角（Marco-view）的信息，所以更能捕捉图在一个大社区下的节点之间的同质性信息。
图15 基于DFS和BFS的聚类可视化结果
图 15 中的可视化结果是作者对同一个图结构分别采用倾向于 DFS 的游走策略和倾向于 BFS 的游走策略学到的节点 embedding 的聚类结果。可以看到，DFS 的结果使得在同一个社区内的节点都分在了相同颜色的簇。而 BFS 的聚类结果则让一些结构信息更类似的节点更容易被分在相同颜色的簇中，例如图 15（b）中的蓝色节点。有趣的是，作者在文中对于这一结果最终也说道:不同的人对于这个可视化的聚类结果可能有不同的理解，但他们需要强调的其实是 Node2vec 模型可以通过设置不同的参数来捕捉图中两种不同的相似性特质（微笑脸）。
笔者认为，可能一开始图 13 给了我们太深的印象，无形中也混淆了我们的理解。根据文章中的解释，无论是同质性还是结构性，更多都是站在同一个社区的角度进行捕捉。BFS 更能捕捉的是同一个局部结构内，具有相似微观结构的节点之间的相似性。而 DFS 由于可以游走得更远，所以更能捕捉整个社区的宏观信息，从而学习到大社区内不同节点之间的相似性。
腾讯看点的内容投放组也尝试利用看点的用户行为数据在公司内部平台上利用 Node2vec 的 BFS 和 DFS 这两种策略进行验证。我们发现：通过 BFS 所学到的 item embedding 更易召回热度相近的内容。例如：社会类的热点新闻会召回娱乐类的热点新闻，因为他们在图结构中的角色是相近的，都是一个簇的中心（结构性）。与之对应的，DFS 的召回结果基本都位于一个大类下面。例如，社会类的内容召回同为社会类或时事类、政治类的内容，因为他们在图结构中更可能同属一个大簇。
无论怎么说，Node2vec 提出的有偏随机游走策略确实让其在面对复杂图网络结构时，比起 DeepWalk 更能学习到节点的完整表示。毕竟出自大神组的工作，其在工业界也有不少应用。对 Node2vec 感兴趣的同学也可以去参考 Jure Leskovec 在 Youtube 的相关授课视频[13]。
2.2.2 工业界应用：微信朋友圈广告[14]
这项工作主要是应用在 2016 年微信朋友圈广告投放的场景中，当时微信团队需要基于广告主提供的种子用户做用户扩散，找到一批对目标广告可能感兴趣的潜在用户，并对它们进行朋友圈的曝光。在进行用户扩散的过程中，需要用到每个用户的 embedding，对用户 embedding 的学习，微信的同事们选择采用 Node2vec 模型在微信用户的社交关系图上进行 embedding 学习。
微信的同事们认为，在社交关系数据里面有两个核心的价值：
- 社交同质性：我和我的好友可能有相似的兴趣；
- 社交影响力：我可能被我的某些好友与朋友圈广告的互动行为所影响。
社交同质性和影响力分别对应了 Node2vec 里面的同质性和结构性角色这两种相似性，可以说 Node2vec 模型比较好地结合了当时微信朋友圈广告推送的业务场景。这一点也是笔者推荐这项工作的原因之一。在查找 Node2vec 在工业界应用的文献过程中，笔者发现很多工作对 Node2vec 的应用场景仅仅是因为它可以学到图节点的嵌入表示，并没有很好地把它的原理和自己的业务结合思考。换而言之，在同一个业务场景下，使用 DeepWalk 模型进行节点 embedding 学习也没有太大的区别。这类工作，可能并不具备 Node2vec 应用的代表性，所以在此处就不多加介绍了。另一点比较值得注意的是，貌似很多 Node2vec 的应用场景都在风控部门，例如斗鱼风控部门利用 Node2vec 来挖掘黑产团伙[15]等。这个现象也比较有意思，但因为公布的材料不多，就没做深入的研究。
2.3 LINE[16]
发表于 WWW’15 的 LINE 也是 Graph Embedding 算法中非常重要的模型之一。把它放在 Node2vec 之后介绍，主要是因为与 DeepWalk、Node2vec 和 EGES 等二阶段图算法模型不同，LINE 通过巧妙地构造目标函数，实现对大规模图网络的嵌入学习。LINE 的作者认为，在对图中节点关系进行嵌入学习的过程中，需要同时建模两种节点之间的关系：
- 一阶亲密度（First-order Proximity）：代表着图中存在边连接的节点之间的关系；
- 二阶亲密度（Second-order Proximity）：代表着共享大部分邻居的节点之间的关系。
图16 一阶亲密度和二阶亲密度示意图
2.3.1 一阶亲密度建模
2.3.2 二阶亲密度建模
2.3.3 新节点问题
2.3.4 实验对比
图17 Line在维基百科上关于网页分类结果的对比
笔者一直在说，LINE 本身的二阶亲密度的建模方式其实等价于 Word2vec 的建模方式。从作者的实验中（图 17）也可以看出，DeepWalk 在分类的性能上其实和 LINE(2nd)是差不多的。LINE 的提升更多来自于在 LINE(2nd)的基础上对 LINE(1st)的拼接。而且，笔者个人认为，如果随机游走的次数足够多，无论在无向图还是有向图，DeepWalk 都可以完整地建模到大于二阶邻居的关于每个节点的局部图结构，从而学到更有代表性的节点表示。也就是说，个人猜测通过足够的随机游走和精准的调参策略，大多数情况，DeepWalk 模型应该是要优于 LINE(2nd)的。我甚至非常好奇 LINE(1st)+DeepWalk 是否会达到比 LINE(1st+2nd)更好的性能？以上观点仅代表个人猜想。但无论如何，在当时的时间节点，LINE 提出在建模节点间的关系时，用边权重进行辅助指导还是非常直观和正确的思路。作者采用的一阶和二阶分开训练然后拼接的方式，也挺值得深思。
2.3.5 工业界应用：CDG 信贷场景[17]
在搜索 LINE 在工业界应用的过程中，有一个现象非常有意思。无论在腾讯内部知识平台亦或是在知乎等知识平台上搜索关键词“Graph Embedding”或“图嵌入”，只要是关于 Graph Embedding 相关技术的介绍或者综述的文章，5 篇有 4 篇都会提到图嵌入的三大杀器：DeepWalk、Node2vec 和 LINE。但是，所有的文章都会提到“DeepWalk”和“Node2vec”。这个现象挺有意思的，至于是为啥笔者也解释不清楚。在查询 LINE 在工业界的应用时，由于 LINE 的设计初衷是对大规模图网络中的节点进行嵌入学习，所以更多的应用倒是关于 LINE 在工业界的分布式实现，而不是它在业务场景中的应用。笔者搜到的唯二 LINE 的应用场景都是和金钱相关。
一个是 CDG 的信贷风控团队认为在计算用户间资金关系链时，用户的一阶关系和二阶关系同样重要。这个出发点与 LINE 非常贴合，但通过对申请信贷的用户进行分析后发现，在该应用场景下，用户们来自全国各地，往往共同好友非常少，无法很好地建模用户之间的二阶亲密度。因此，通过 LINE 学出来的用户 embedding 在作为特征输入预测模型后，并没有获得太多收益。
一个是微信支付团队在建模微信支付用户 embedding 时，尝试用 LINE 分别学习用户作为“收款方”和“付款方”时的 embedding[18]。这里不得不再感慨一下微信的同事们对图算法的探索做得还是非常全面的，提供了许多非常宝贵和实用的学习资料。
2.4 Metapath2vec[19]
前文所介绍的方法，无论是二阶段图嵌入的鼻祖 DeepWalk、结合 BFS 和 DFS 的 Node2vec 或者同时捕捉节点间一阶亲密度和二阶亲密度的 LINE，更多专注于对图的局部结构信息进行探索。但多数情况，在现实世界的图网络中，节点之间不仅具有空间结构（structure）上的联系而且还具有语义（semantic）上的联系。
图18 多语义学术图网络示例
2.4.1 metapath2vec
通过预定义异构图网络中的语义联系作为元路径（例如：co-author 关系“APA”或论文发表关系“APVPA”等），基于元路径的随机游走策略可以保证 metapath2vec 模型在生成节点序列信息时，可以同时建模节点之间的空间结构关系和语义关系。另外，在选定相关元路径后，例如“APA”，metapath2vec 可以通过循环选定元路径的方式游走出预定长度的异构节点序列。假设游走长度为5 ，则从作者（A）类节点开始游走的序列所遵循的模式为"APAPA"，这样的模式可以挖掘出论文作者之间的二阶甚至高阶的学术关系。例如，假设“Geoffrey Hinton”和“Yann LeCun”是 co-author，且“Geoffrey Hinton”和“Yoshua Bengio”也是 co-author，则“LeCun”和“Bengio”之间也可能存在某种学术联系。
对每个节点完成基于元路径的随机游走的序列采样后，与其他二阶段图嵌入方法一样，metapath2vec 也采用基于负采样的 Skip-gram 模型对序列信息进行节点嵌入的学习。
2.4.2 metapath2vec++
虽然 metapath2vec 通过元路径引导随机游走的方式，限定了在序列游走的过程中下一节点的可选范围需要遵循预定义的元路径语义。但是，在节点的嵌入学习阶段，metapath2vec 和其他二阶段图嵌入算法一样，采用了传统的基于负采样的 Skip-gram 模型。因此，在每次基于中心节点进行负采样时，负采样的节点范围是所有类型的节点而与中心节点的类型是无关的。Metapath2vec 的作者们认为，这样不利于区分异构节点的嵌入表示。所以，他们在 metapath 的基础上，提出了新的负采样方式对异构节点序列进行学习，叫做 metapath2vec++。
图19 metapath2vec和metapath2vec++关于学术图网络学习到的作者和会议embedding的可视化
从图 19 中可以看出，虽然 metapath2vec 和 metapath2vec++都学到了作者节点和会议节点之间的语义关系，例如：C.D. Manning 和 ACL。但是，我们可以看到，metapath2vec++不仅成功捕捉了不同类型节点之间的语义关系，同时可以比较清晰地区分会议节点和作者节点在嵌入空间中的关系。
2.4.3 工业界应用: 微视召回[20]
Metapath2vec 被微视的同事用于学习用户（User）和视频（Item）的 embedding 学习，并应用在推荐召回阶段。
图20 微视Metapath2vec应用流程
微视同事们认为，同一作者在同一类目下创作的视频之间具有较强的语义关联。同样地，消费了同一作者在同一类目下的视频的用户也应该有相似的兴趣。所以在推荐场景中的 user 节点和 item 节点的基础上，他们引入了由作者（Author）和二级类目（Cate2）拼接构成的 AC 节点，并设计了基于“User-Item-AC-Item-User”的元路径来引导随机游走策略在微视的用户行为异构图上进行序列生成。具体细节如图 20 所示，根据用户对视频的点击序列和视频与作者类目之间的关系，构建微视自己的“用户-视频-AC”异构图，并在构建好的异构图上基于“User-Item-AC-Item-User”的元路径进行随机游走。最终游走生成的序列采取 Skip-gram 进行训练。
根据[20]中的描述，Metapath2vec 使得微视关于视频召回业务在内容相关性指标上得到了一定的提升，不过 AC 节点的引入带来了过强的约束力也削弱了召回视频的多样性。为了解决这一问题，微视的同事们也做了相关的操作，感兴趣的鹅厂同学推荐阅读这篇文章。最终，Metapath2vec 模型在微视的召回业务中上线，且在人均时长和人均 VV 上都收获了不错的提升。
笔者认为，微视召回的这项工作是关于 Metapath2vec 非常好的一个应用实例。微视同事们首先考虑到用户节点和视频节点的异质性。然后，通过拼接作者节点和二级类目节点很自然地引入了同作者在同类目下创作内容之间天然的语义联系。作者节点和二阶类目节点拼接的方式也比较有意思。所以，还是再次推荐微视同事们写的这篇内部技术文章，质量非常不错。微视推荐召回篇系列的内容都非常扎实，推荐相关的同学非常值得阅读。
另外，看点投放团队近半年也一直在基于 Metapath2vec 对信息流中“用户”，“内容”和“作者”之间的关系进行探索，日后期待也能带来相关有深度的分析和业务结果分享给各位看官。
2.5 HIN2Vec[21]
HIN2Vec 和 Metapath2vec 同样发表于 2017 年，从它的标题“HIN2Vec: Explore Meta-paths in Heterogeneous InformationNetworks for Representation Learning”可以看出，HIN2Vec 的中心思想也是通过元路径来指导异构图网络中节点的表示学习，旨在同时建模节点间的空间结构关系和语义结构关系。与 Metapath2vec 类似，HIN2Vec 也采用二阶段学习的方式来学习节点表示和边表示：
- 训练数据准备阶段；
- 表示学习阶段。
2.5.1 表示学习阶段
与 DeepWalk，Metapath2vec 等基于 Skip-gram 的二阶段学习模型不同，HIN2Vec 在节点的表示学习阶段并没有采用基于负采样的 Skip-gram 模型，而是把节点和边的表示学习转换成了二分类任务。由于学习方式的不同，所以 HIN2Vec 在阶段一关于训练数据准备的方式也与之前介绍的二阶段图嵌入方法略有不同，所以这里先从阶段二切入介绍。
图21 HIN2Vec的二分类神经网络模型示意图
2.5.2 训练数据准备阶段
在数据准备阶段，HIN2Vec 采用了随机游走的方式生成节点的随机序列。但与 Metapath2vec 基于元路径进行随机游走的方式不同，HIN2Vec 采用的是原始的随机游走策略。然后根据随机游走所得到的序列内节点之间的关系，提取出对应的训练三元组 $$。
图22 作者-论文异构图
2.6 基于 Metagraph 的异构图建模[22]
这篇工作是腾讯 IEG 同事联合 SMU 和微众一起提出的。与之前基于元路径（Meta-path）建模异构图节点间的语义关系不同，本文的作者们提出了一种称为元图（Meta-graph）的概念。并基于元图建模节点之间在不同语义上下文中的相似度。
图23 Meta-graph示例图
该工作利用元图的方式来建模用户之间复杂的关系确实非常巧妙，但是不可避免地，在图结构中进行子图挖掘和匹配是十分耗时的过程。在原论文中，作者们也提出了基于元图的对称匹配和二阶段训练等加速方法。因为不是本文关注的重点，故在此不多加介绍。根据内部技术文章中 ieg 同事的描述，该方法被应用在多个异构图推荐问题中。文章的作者 Wenqing Lin 在图挖掘方面也多有建树，感兴趣的同学推荐阅读原文和持续 follow 作者的 publication。
2.7 动态图（Dynamic Graph）问题
虽然上述各类图嵌入方法的有效性和高效性无论在学术界或是工业界都得到大量的验证。但它们在对图节点进行表示学习时，更多是以单一图或者静态图（Static Graph）的方式进行学习。换而言之，图的结构信息是稳定且不会变化的。当图的结构发生变化时，比如加入了新的边或者新的节点，上述 Graph Embedding 的方法均需要对新图进行重新训练。但是在现实场景中，图的结构往往是在不断地变化，比如：新用户的加入，新商品的上架，新的好友关系的形成等。这种基于图变化的建模问题可以称为动态图（Dynamic Graph）问题。试想一下，如果微信支付团队每次在新加入用户节点或者用户节点之间的支付关系发生变化时，均需要对图进行重新训练，无论从模型的效果、稳定性或者计算资源的需求上，都是不现实的。根据笔者的调研，现阶段 Graph Embedding 领域处理动态图节点的方法，大致包括以下三种思路。
最简单且常见的方法类似于 Airbnb embedding 对于处理冷启动 listing 的方式或者 LINE 处理新节点的方式：在不改变老节点 embedding 的情况下，利用邻接节点的 embedding 来表示或学习新节点的 embedding。例如：对同一地理位置相似的房源 embedding 求平均来表示新加入的房源。这一方法因为简单高效，被很多业务团队采用。年初，我们看点内容投放策略团队在对冷启用户 embedding 进行建模时，也通过对其最近点击的内容 embedding 求平均的方式来表示冷启用户。但是，此方法无法精确学习新节点的 embedding。此外，每当有新节点或者新边加入图结构，部分旧节点的表示也需要做适当的调整，以完整捕捉旧节点在新图的局部结构信息。
相比之下，微信支付团队发文探讨过关于动态图增量更新的方法[23]更值得参考。他们仅对图中产生变化的局部区域采用随机游走生成新的序列，并利用上一版本的 Embedding 作为初始化来更新模型。这样的办法可以避免对整个图进行重新计算，且受影响节点都能获得动态更新。但这类方法存在的风险在于，虽然老版本的 embedding 被用作初始化，但是经过多次局部图更新后，该方法可能面临空间偏移（Space Drifting）的问题。此外，微信支付的同学也提到，当节点变化较大，全图更新还是无法避免，且 embedding 的稳定性无法得到保障。微信支付团队在腾讯内部技术平台上持续输出了多篇关于图算法的好文，现场打 call。
最后，关于动态图问题的思路来自于论文Dynamic Network Embedding: An Extended Approach for Skip-gram based Network Emebdding[24]。文章认为，动态图需要解决两个问题：
- 动态图不仅需要学习新节点的 embedding，也需要更新那些受影响的老节点 embedding；
- 在学习新节点 embedding 和更新老节点 embedding 时，需要避免向量空间偏移的问题。
为了解决上述两个问题，文章提出了一种动态图嵌入的方法，首先对基于负采样的 Skip-gram 模型的目标函数进行了分解，使得模型可以分开对每个节点进行单独更新且对利用正则项对节点 embedding 的版本作了约束：
笔者认为，第三种思路利用了交替更新的办法保证新节点和受影响的老节点的 embedding 学习能尽快收敛，且通过公式（20）约束了 embedding 的版本，缓解了向量空间偏移的问题。但是，交替更新的新节点向量是否能达到节点的最优解是存疑的，且空间偏移问题并不能通过公式（20）进行一个彻底的解决。所以对于动态图或者是工业界常见的增量更新问题，各位读者如果有好的解决思路不妨一起探讨，近期微信支付团队在腾讯内部技术平台输出的关于增量更新的文章也很值得阅读[25]。（PS：SAGE 等归纳式方法（Inductinve Method）并不在本文的讨论范围内，所以这里就略过不提了）
3. 结语
本文介绍了近年主流的图嵌入模型和它们在工业界的具体应用，算是看点内容投放策略团队近期在图算法领域的一次初探总结。文章从 Word2vec 模型入手，介绍了一些经典的图嵌入模型的原理和它们设计的动机，并提供了一些笔者总结的相关工业界的应用。希望本文能达到以下几点：
- 为对图嵌入方法感兴趣的同学提供一篇比较合适的科普文，让大家对主流图嵌入模型有一定地了解；
- 能作为一个简版的关于图嵌入的应用实战 cookbook，为想要在业务中使用 Graph Embedding 的童鞋提供一定的参考；
- 希望从模型的动机和具体的业务需求出发，引发大家对于不同图嵌入模型在不同需求和业务场景下如何使用的讨论和思考。
看点内容投放策略团队近期也一直在探索图算法在信息流内容投放场景中的应用，欢迎各位对图嵌入或是图算法有深入了解或者感兴趣的同学们多来一起交流。后续也将持续更新图算法系列，分享本团队在腾讯看点相关的业务场景中应用图嵌入模型的经验。也欢迎对图嵌入有深入理解的童鞋可以帮忙指正本文的不足之处，持续交流。
最后，顺便为我们在探索调研过程中，联系和交流过的微信支付团队、TEG 数平的 Angel 团队打 Call。特别鸣谢其中的 brian、gdp 和 joy 同学，他们充分表现了鹅厂内部乐于助人，乐于分享的精神，为笔者关于图算法方面提供了很多知识和帮助。感谢团队内部和笔者一起合力完成本文的 add 同学和 ross 大佬。
4. 相关文献
[1] Mikolov, Tomas, et al. "Efficient estimation of word representations in vector space." arXiv preprint arXiv:1301.3781 (2013).
[2] Rong, Xin. "word2vec parameter learning explained." arXiv preprint arXiv:1411.2738 (2014).
[3] https://www.youtube.com/watch...\_FSo&t=1371s
[4] Levy, Omer, and Yoav Goldberg. "Neural word embedding as implicit matrix factorization." Advances in neural information processing systems 27 (2014): 2177-2185.
[5] Barkan, Oren, and Noam Koenigstein. "Item2vec: neural item embedding for collaborative filtering." _2016 IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP)_. IEEE, 2016.
[6] Grbovic, Mihajlo, and Haibin Cheng. "Real-time personalization using embeddings for search ranking at airbnb." _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2018.
[7] 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. 2014.
[8] Wang, Jizhe, et al. "Billion-scale commodity embedding for e-commerce recommendation in alibaba." _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2018.
[9] 腾讯内部技术文章《Embedding 模型在快报图文相关推荐召回上的应用(二)》
[10] 腾讯内部技术文章《GraphEmbedding 在新闻推荐中的应用》
[11] 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_. 2016.
[12] https://zhuanlan.zhihu.com/p/...
[13] https://www.youtube.com/watch...
[14] https://mp.weixin.qq.com/s/EV...
[15] https://cloud.tencent.com/dev...
[16] Tang, Jian, et al. "Line: Large-scale information network embedding." _Proceedings of the 24th international conference on world wide web_. 2015.
[17] 腾讯内部技术文章《信用风险模型（三）：图算法在信贷风控领域的应用》
[18] 腾讯内部技术文章《大规模 Embedding 之双向图算法在微信支付反欺诈的应用》
[19] Dong, Yuxiao, Nitesh V. Chawla, and Ananthram Swami. "metapath2vec: Scalable representation learning for heterogeneous networks." _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_. 2017.
[20] 腾讯内部技术文章《微视推荐召回篇(一)-Graph Embedding》
[21] Fu, Tao-yang, Wang-Chien Lee, and Zhen Lei. "Hin2vec: Explore meta-paths in heterogeneous information networks for representation learning." _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_. 2017.
[22] Fang, Yuan, et al. "Metagraph-based learning on heterogeneous graphs." IEEE Transactions on Knowledge and Data Engineering 33.1 (2019): 154-168.
[23] 腾讯内部技术文章《微信支付 Graph Embedding 研究与实践》
[24] Du, Lun, et al. "Dynamic Network Embedding: An Extended Approach for Skip-gram based Network Embedding." _IJCAI_. Vol. 2018. 2018.
[25] 腾讯内部技术文章《微信支付大规模动态图增量表示学习实践》
原文：腾讯技术工程
作者： jamiiejiang
推荐阅读
更多腾讯AI相关技术干货，请关注专栏腾讯技术工程
