第31.1节 算法简介

前面介绍过Word2Vec算法，训练集为若干句子，计算出各单词的向量。如图所示。

Graph Embedding的计算也借鉴了这种做法，只不过多了一步从图到游走路径集的变换。若将每个图节点看作一个单词，则每条游走路径就相当于一个句子；对游走路径集使用Word2Vec计算，就可得到每个图节点的向量。如图所示：

每个游走方法就对应了一个GraphEmbedding算法，Random Walk（随机游走）对应着DeepWalk算法；Node2Vec Walk对应着Node2Vec算法；Meta Path Walk对应着MetaPath2Vec算法。即

• DeepWalk = Random Walk + Word2Vec
• Node2Vec = Node2Vec Walk + Word2Vec
• MetaPath2Vec = Meta Path Walk + Word2Vec

50.1.1 Random Walk（随机游走）

DeepWalk使用的Random Walk（随机游走），每一步都是当前节点的一个邻居。假设当前随机行走到节点，下一个访问的节点将是的邻居之一。选择哪个邻居是随机的，下一个节点的选择概率如下：

这里，为节点的所有邻居的集合。

进一步，对于加权图，下一个访问节点的选择是通过当前节点加权随机抽取的，计算概率公式如下：

其中为节点与之间边的权重。

50.1.2 Node2Vec Walk

节点选择上有两种“极端”策略：广度优先（BFS）和深度优先（DFS）。前者仅限于源节点的近邻，而后者则由距离不断增加的连续节点组成。Node2Vec Walk通过引入两个参数和，将广度优先搜索和深度优先搜索引入随机游走序列的生成过程。

先定义函数如下：

其中是节点与节点之间最短路径的距离，即节点与节点之间经过最少几条边可以到达。如果节点与节点重合，则其距离为0；如果节点与节点之间有一条边，则其距离为1。

通过对权重进行修正，得

进而得到节点的选择概率：

这里，为节点的所有邻居的集合。

由公式可以清晰看到Node2Vec Walk需要考虑当前节点及上一个节点，由函数的定义可知，参数控制着下一个节点会选择的概率，值越大越不会走回头路；参数控制着下一个节点会选择相邻节点的概率，值越贴近0，则越趋向于深度优先搜索，值比1越大，则越趋向于广度优先搜索。特殊地，当参数和都为1的时候，Node2Vec Walk就等同于Random Walk。

50.1.3 Meta Path Walk

对于Meta Path Walk，主要是在节点上引入了类型信息，在构造游走路径时，节点的类型要满足一定模式。譬如，如下所示，图有两种类型的节点，分别用黑色和白色表示。

我们定义游走路径的模式为黑白相间，路径模版定义为

则根据此模版，产生的一条路径如下，路径选中节点用方框标识。