Graph Embedding之metapath2vec

摘要

Metapath2vec是Yuxiao Dong等于2017年提出的一种用于异构信息网络（Heterogeneous Information Network, HIN）的顶点嵌入方法。metapath2vec使用基于meta-path的random walks来构建每个顶点的异构邻域，然后用Skip-Gram模型来完成顶点的嵌入。在metapath2vec的基础上，作者还提出了metapath2vec++来同时实现异构网络中的结构和语义关联的建模。

简介

作者首先提到了基于神经网络的学习模型可以捕获不同类型数据的潜在信息和复杂关系，如图像，语音和语言等。同样地，基于神经网络的模型针对复杂网络的表示学习也有非常好的效果。作者提到了当前已经提出的采用了word2vec思想的网络表示算法，如Deepwalk，node2vec以及LINE等。但是作者也明确指出了，上述这些算法虽然可以用于网络表示学习，但仅适合那些只包含一类顶点类型和边类型的同构网络（Homogeneous Networks），并不能很好地用于包含多种顶点类型和边类型的复杂关系网络。于是作者在基于meta-path的基础上，提出了能很好应对指定scheme结构的异构复杂关系网络的表示学习方法——metapath2vec和metapath2vec++。 metapath2vec的目标是最大化保留一个异构网络的结构和语义信息的似然，首先使用基于meta-path的随机游走获取异构网络中每种不同类型顶点的异构领域，然后使用扩展的Skip-Gram处理前面获取的顶点领域，最终学习每个不同类型顶点的网络嵌入表示。跟之前的网络嵌入成果相比，作者认为metapath2vec具有以下贡献：

正式定义了Heterogeneous Network上的表示学习过程，并指明了网络异构带来的特殊挑战。
提出了有效且高效的能同时保留结构和语义相互关系的异构网络嵌入框架：metapath2vec和metapath2vec++。

问题定义

定义1：Heterogeneous Network

异构网络定义为： $\small G=(V,E,T)$ ，其中每个顶点和边对应的映射函数为： $\small \phi(v):V \to T_V$ 和 $\small \varphi (e):E \to T_E$ ，其中 $\small T_V$ 和 $\small T_E$ 分布表示顶点和边的类型，另外还满足 $\small |T_V|+|T_E| > 2$ 。

定义2：Heterogeneous Network Representation Learning

异构网络表征学习定义为：给定一个异构网络 $\small G$ ，学习一个 $\small d$ 维的潜在表征 $\small X \in \Bbb R^{|V| \times d}, d \ll|V|$ 可以表征网络中顶点之间的结构信息和语义场景关系。异构网络表征学习的输出是一个低维的矩阵 $\small X$ ，其中 $\small v^{th}$ 行是一个 $\small d$ 维的向量，表示顶点 $\small v$ 的表征。这里需要注意的是，虽然顶点的类型不同，但是不同类型的顶点的表征向量映射到同一个维度空间。由于网络异构性的存在，传统的基于同构网络的顶点嵌入表征方法很难有效地直接应用在异构网络上。

Metapath2vec框架

在正式介绍metapath2vec方法之前，作者首先介绍了同构网络上的基于random walk的graph embedding算法的基本思想，如：Deepwalk和node2vec等。该类方法采用了类似word2vec的思想，即：使用skip-gram模型对每个顶点的局部领域顶点信息进行预测，进而学习到每个顶点的特征表示。通常，对于一个同构网络 $\small G=(V,E)$ ，目标是从每个顶点的局部领域上最大化网络似然：
$\arg \max_\theta \prod_{v \in V} \prod_{c \in N(v)}p(c|v;\theta)$ 其中 $\small N(v)$ 表示顶点 $\small v$ 的领域，如1-hop以内的邻接顶点，2-hop以内的邻接顶点。 $\small p(c|v;\theta)$ 表示给定顶点 $\small v$ 后，顶点 $\small c$ 的条件概率。下面正式给出基于异构网络的metapath2vec嵌入算法。metapath2vec分为两个部分，分别是Meta-Path-Based Random Walks和Heterogeneous Skip-Gram。

Heterogeneous Skip-Gram

在metapath2vec中，作者使用Skip-Gram模型通过在顶点 $\small v$ 的领域 $\small N_t(v), t \in T_V$ 上最大化条件概率来学习异构网络 $\small G=(V,E,T)$ 上的顶点表征。
$\arg \max_\theta \sum_{v \in V} \sum_{t \in T_V} \sum_{c_t \in N_t(v)} \log p(c_t|v;\theta)$ 其中 $\small N_t(v)$ 表示顶点 $\small v$ 的类型为 $\small t$ 的领域顶点集合。 $\small p(c_t|v;\theta)$ 通常定义为一个softmax函数，即：
$p(c_t|v;\theta)=\frac{e^{X_{c_t} \cdot X_v}}{\sum _{u \in V}e^{X_u \cdot X_v}}$ 其中 $\small X_v$ 是矩阵 $\small X$ 的第 $\small v$ 行矩阵，表示顶点 $\small v$ 的嵌入向量。为了提升参数更新效率，metapath2vec采用了Negative Sampling进行参数迭代更新，给定一个Negative Sampling的大小 $\small M$ ，参数更新过程如下：
$\log \sigma(X_{c_t} \cdot X_v) + \sum _{m=1}^M \Bbb E_{u^m \sim P(u)}[\log \sigma(-X_{u^m} \cdot X_v)]$ 其中 $\small \sigma(x) = \frac{1}{1+e^{-x}}$ ， $\small P(u)$ 是一个negative node $\small u^m$ 在M次采样中的预定义分布。
metapath2vec通过不考虑顶点的类型进行节点抽取来确定当前顶点的频率。

Meta-Pathe-Based Random Walks

在同构网络中，DeepWalk和node2vec等算法通过随机游走的方式来构建Skip-Gram模型的上下文语料库，受此启发，作者提出了一种异构网络上的随机游走方式。在不考虑顶点类型和边类型的情况下， $\small p(v^{i+1}|v^i)$ 表示从顶点 $\small v^i$ 向其邻居顶点 $\small v^{i+1}$ 的转移概率。然而Sun等已证明异构网络上的随机游走会偏向于某些高度可见的类型的顶点，这些顶点的路径在网络中具有一定的统治地位，而这些有一定比例的路径指向一小部分节点的集合。鉴于此，作者提出了一种基于meta-path的随机游走方式来生成Skip-Gram模型的邻域上下文。该随机游走方式可以同时捕获不同类型顶点之间语义关系和结构关系，促进了异构网络结构向metapath2vec的Skip-Gram模型的转换。
一个meta-path的scheme可以定义成如下形式：
$V_1 \stackrel{R_1} \longrightarrow V_2 \stackrel{R_2} \longrightarrow \dots V_t \stackrel{R_t} \longrightarrow V_{t+1} \dots V_{l-1}\stackrel{R_{l-1}} \longrightarrow V_l$ 其中
$R=R_1\circ R_2 \circ \dots \circ R_{l-1}$ 表示顶点 $\small V_1$ 和顶点 $\small V_l$ 之间的路径组合。例如图（a）中，“APA”表示一种固定语义的meta-path，“APVPA”表示另外一种固定语义的meta-path。并且很多之前的研究成果都表明，meta-path在很多异构网络数据挖掘中很很大作用。因此，在本文中，作者给出了基于meta-path的随机游走方式。给定一个异构网络 $\small G=(V,E,T)$ 和一个meta-path的scheme $\small \cal P$ :
$V_1 \stackrel{R_1} \longrightarrow V_2 \stackrel{R_2} \longrightarrow \dots V_t \stackrel{R_t} \longrightarrow V_{t+1} \dots V_{l-1}\stackrel{R_{l-1}} \longrightarrow V_l$ 那么在第 $\small i$ 步的转移概率定义如下：
$p(v^{i+1}|v^i_t, \cal P)=\begin{cases} \frac{1}{|N_{t+1}(v_t^i)|} & (v^{i+1},v^i) \in E, \phi(v^{i+1})=t+1 \\ 0 & (v^{i+1},v^i) \in E, \phi(v^{i+1}) \neq t+1 \\ 0 & (v^{i+1},v^i) \notin E, \end{cases}$ 其中 $\small v_t^i \in V_t$ ， $\small N_{t+1}(v_t^i)$ 表示顶点 $\small v_t^i$ 的 $\small V_{t+1}$ 类型的领域顶点集合。换言之， $\small v^{i+1} \in V_{t+1}$ ，也就是说随机游走是在预定义的meta-path scheme $\small \cal P$ 条件下的有偏游走。初次之外，meta-path通常是以一种对称的方式来使用，也就是说在上述路径组合中，顶点 $\small V_1$ 的类型和 $\small V_l$ 的类型相同。即：
$p(v^{i+1}|v_t^i) = p(v^{i+1}|v_l^i), \text{if t=l}$ 基于meta-path的随机游走保证不同类型顶点之间的语义关系可以适当的融入Skip-Gram模型中。

An illustrative example of a heterogeneous academic network and skip-gram architectures of metapath2vec and metapath2vec++ for embedding this network.

metapath2vec++

metapath2vec在为每个顶点构建领域时，通过meta-path来指导随机游走过程向指定类型的顶点进行有偏游走。但是在softmax环节中，并没有顶点的类型，而是将所有的顶点认为是同一种类型的顶点。换言之，metapath2vec在Negative Sampling环节采样的negative 样本并没有考虑顶点的类型，也就是说metapath2vec支持任意类型顶点的Negative Sampling。于是作者在metapath2vec的基础上又提出了改进方案metapath2vec++。

Heterogeneous Negative Sampling

在metapath2vec++中，softmax函数根据不同类型的顶点的上下文 $\small c_t$ 进行归一化。也就是说 $\small p(c_t | v; \theta)$ 根据固定类型的顶点进行调整。即：
$p(c_t|v; \theta) = \frac{e^{X_{c_t} \cdot X_v}}{\sum _{u_t \in V_t} e^{X_{u_t}\cdot X_v}}$ 其中 $\small V_t$ 是网络中 $\small t$ 类型顶点集合。在这种情况下，metapath2vec++为Skip-Gram模型的输出层中的每种类型的领域指定了一个多项式分布的集合。而在metapath2vec，DeepWalk和node2vec中，Skip-Gram输出多项式分布的维度等于整个网络中顶点的数目，然而对于metapath2vec++的Skip-Gram，其针对特定类型的输出多项式的维度取决于网络中当前类型顶点的数目。如图（c）所示。最终我们可以得到如下的目标函数：
$O(X) = \log \sigma(X_{c_t} \cdot X_v) + \sum _{m=1}^M \Bbb E_{u_t^m \sim P_t(u_t)}[\log \sigma(-X_{u_t^m} \cdot X_v)]$ 可以得出其梯度如下：
$\frac{\partial O(X)}{ \partial X_{u_t^m}} = (\sigma (X_{u_t^m} \cdot X_v - \Bbb I_{c_t}[u_t^m]))X_v \\ \frac{\partial O(X)}{\partial X_v} = \sum_{m=0}^M(\sigma(X_{u_t^m} \cdot X_v - \Bbb I_{c_t}[u_t^m]))X_{u_t^m}$ 其中 $\small \Bbb I_{c_t}[u_t^m]$ 是一个指示函数，用来指示 $\small u_t^m$ 在 $\small m=0,u_t^0=c_t$ 时是否是顶点 $\small c_t$ 的上下文。该算法使用随机梯度下降进行参数优化。整个metapath2vec++算法如下。

the metapath2vec++ Algorithm

以上就是metapath的全部内容，该算法沿用了之前同构网络上基于随机游走的Embedding算法的思想，作者通过在异构网络上，引入预置meta-paths来指导随机游走的过程，另外通过meta-path的领域来改进传统的Skip-Gram模型，使得该嵌入方法不仅能保留网络中的异构信息和语义关系信息，同时针对大规模网络，性能也有了本质上的提升。具体细节可以参考原论文，链接如下。

参考：
metapath2vec: Scalable Representation Learning for Heterogeneous Networks