metapath2vec异构图表征算法

type

status

date

slug

summary

解决了异构图上的节点嵌入（Embedding）问题，论文中指出了两个关键问题：

Contribution 1：定义了异构网络表示学习的问题，总结了异构网络嵌入所带来的挑战。

Contribution 2：提出两个快速且有效的框架，metapath2vec和metapath2vec++，能够保留异构网络中的结构和语义联系。

Contribution 3：证明了所提的两个模型能够挖掘到异构网络中不同类型节点的语义联系（现有方法无法识别的）。

Skip-gram是Word2Vec的一种常用网络，它根据中心词预测上下窗口内的共现词，如下窗口为2的MLP，采用Sampled Softmax的损失函数进行训练，最终获得Word的向量矩阵用来表示每个Word，Word向量之间的内积越大表示两个Word的关联性越高，更容易在一起出现。

其中为了减少权重更新的运算量，在Softmax处进行了负采样，只选取个负样本进行更新。

DeepWalk的思想类似Word2vec，针对同构图，使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk给出的方法是使用RandomWalk（随机游走）的方式在图中进行节点采样。

RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。

DeepWalk算法主要包括两个步骤，第一步为随机游走采样节点序列，第二步为使用skip-gram模型学习表达向量。

针对异构图采用基于meta path的Random Walk：

首先，定义了元路径（meta path）的概念，是在图中选取的由节点类型构成的组合路径如APA、APCPA等：

它们表示不同类型节点之间一种逻辑关系，相当于人为的引入一些先验知识。

然后，根据元路径在节点上Random Walk生成节点序列。其中，元路径最好实对称的（即首尾节点类型相同），方便扩展游走。

把游走序列作为样本训练skip-gram模型：

可以看出，metapath2vec在随机游走的时候考虑了节点类型，但是在负采样的时候没有考虑节点类型。这样的负样本采集方式并不利于模型训练，我们应当采集同样的样本类型，因此提出了metapath2vec++算法，在负采样的时候，考虑了节点类型。