H好菇凉666用万字长文聊一聊 Embedding 技术( 七 )

本文插图
DeepWalk得本质可以认为是：random walk + skip-gram 。在DeepWalk算法中，需要形式化定义的是random walk的跳转概率，即到达节点后，下一步遍历其邻居节点的概率：
其中，表示及节点的所有出边连接的节点集合，表示由节点连接至节点的边的权重。由此可见，原始DeepWalk算法的跳转概率是跳转边的权重占所有相关出边权重之和的比例。算法具体步骤如下图所示：

本文插图
DeepWalk算法原理简单，在网络标注顶点很少的情况也能得到比较好的效果，且具有较好的可扩展性，能够适应网络的变化。但由于DeepWalk采用的游走策略过于简单（BFS），无法有效表征图的节点的结构信息。
B) Node2vec 为了克服DeepWalk模型的random walk策略相对简单的问题，斯坦福大学的研究人员在2016年提出了Node2vec模型。该模型通过调整random walk权重的方法使得节点的embedding向量更倾向于体现网络的同质性或结构性。

同质性：指得是距离相近的节点的embedding向量应近似，如下图中，与节点相连的节点、、和的embedding向量应相似。为了使embedding向量能够表达网络的同质性，需要让随机游走更倾向于DFS ，因为DFS更有可能通过多次跳转，到达远方的节点上，使游走序列集中在一个较大的集合内部，使得在一个集合内部的节点具有更高的相似性，从而表达图的同质性。
结构性：结构相似的节点的embedding向量应近似，如下图中，与节点结构相似的节点的embedding向量应相似。为了表达结构性，需要随机游走更倾向于BFS ，因为BFS会更多的在当前节点的邻域中游走，相当于对当前节点的网络结构进行扫描，从而使得embedding向量能刻画节点邻域的结构信息。

本文插图
在Node2vec中，同样是通过控制节点间的跳转概率来控制BFS和DFS倾向性的。如下图所示，当算法先由节点跳转到节点，准备从节点跳转至下一个节点时（即），各节点概率定义如下：
其中，是节点和边的权重，定义如下：
这里表示节点与的最短路径，如与的最短路径为1（即），则。作者引入了两个参数和来控制游走算法的BFS和DFS倾向性：

return parameter p：值越小，随机游走回到节点的概率越大，最终算法更注重表达网络的结构性
In-out parameter q：值越小，随机游走到远方节点的概率越大，算法更注重表达网络的同质性

当时， Node2vec退化成了DeepWalk算法。

本文插图
下图是作者通过调整p和q ，使embedding向量更倾向于表达同质性和结构性的可视化结果：
从图中可以看出，同质性倾向使相邻的节点相似性更高，而结构性相似使得结构相似的节点具有更高的相似性。 Node2vec的算法步骤如下：

本文插图
相较于DeepWalk ， Node2vec通过设计biased-random walk策略，能对图中节点的结构相似性和同质性进行权衡，使模型更加灵活。但与DeepWalk一样， Node2vec无法指定游走路径，且仅适用于解决只包含一种类型节点的同构网络，无法有效表示包含多种类型节点和边类型的复杂网络。
为了解决Node2vec和DeepWalk无法指定游走路径、处理异构网络的问题， Yuxiao Dong等人在2017年提出了Metapath2vec方法，用于对异构信息网络（Heterogeneous Information Network, HIN）的节点进行embedding 。