《metapath2vec:Scalable Representation Learning for Heterogeneous Networks》—论文笔记

metapath2vec是2017年KDD上的一个工作,提出了对异质网络的表示学习算法metapath2vec和metapath2vec++。论文的主要亮点在于:通过元路径来指导随机游走,从而构造出节点的邻居节点集合,然后基于异质的skip-gram模型进行节点embedding。

1、 Problem Definition

1.1、Heterogeneous Network

异质网络中的节点和边的类型的数量之和至少为3。

给定图$G=(V,E,T)$,存在映射:$\phi(v): V \to {T_V}$和$\varphi(e): E \to {T_E}$,$T_V$和$T_E$分别表示节点和边的类型集合,其中$|T_V|+|T_E|>2$。

1.2、Heterogeneous Network Representation Learning

异质网络的表示学习就是学习不同类型的节点的特征表示,这个特征表示能够保留网络的结构特征和语义关系。

虽然异质网络中节点类型不同,但是特征表示空间是相同的。

1.3、Meta Path

元路径是一种通过一组关系连接多个节点类型的路径,可以用来描述异质网络中不同类型对象之间各种连接的不同语义关系。

2、metapath2vec

论文同样是基于随机游走和Skip-gram模型进行改进,将其用于异质网络的表示学习,提出了异质的Skip-gram基于元路径的随机游走

异质的Skip-gram其实就是在原始Skip-gram模型的基础上,添加了对不同节点类型的叠加。对于节点类型数量大于1($|T_V|>1$)的异质网络,给定节点$v$的上下文节点$N_t(v)$,最大化如下的概率:

其中,$N_t(v)$表示节点$v$的邻居节点集合,类型为$t$,$p(c_t|v;\theta)=\frac{e^{X_{c_t}\cdot{X_v}}}{\sum_{u\in{V}}{e^{X_u\cdot{X_v}}}}$定义为softmax函数,$X_v$表示节点$v$的表示特征。论文同样采用负采样的方法更新公式(1),定义为:$\log \sigma(X_{c_t},X_v)+\sum_{m=1}^M{E_{u^m\sim{P(u)}}[\log \sigma{-X_{u^m}\cdot{X_v}}]}$。

从上面的公式定义可以看出,其实metapath和DeepWalk、node2vec基本类似,softmax归一化时同样没有考虑节点的类型,分母也是对图中的所有节点的特征表示求和。唯一的区别在于:metapath通过元路径来指导随机游走的节点跳转,在给定元路径模式$\mathcal{P}: V_1\to^{R_1}{V_2}\to^{R_2}{…}\to{V_t}\to^{R_t}{V_{t+1}}\to{…}\to^{R_{l-1}}{V_l}$,跳转概率定义为:

公式中$i​$表示第i步,$v_t^i\in{V_t}​$表示在第i 步的类型为t的节点,$N_{t+1}(v_t^i)​$表示节点$v_t^i​$的类型为$t+1​$的邻居节点。

如果下一节点$v^{i+1}$和当前节点$v_t^i$之间有边连接($(v^{i+1},v_t^i)\in{E}$),而且$v^{i+1}$的类型符合元路径模式所定义的下一节点类型($\phi(v^{i+1})=t+1$),那么随机游走到节点$v^{i+1}$的概率就是节点$v_t^i$的邻居节点且类型为$t+1$的节点的个数的倒数(均匀分布)。

3、metapath2vec++

在metapath2vec中,softmax归一化没有考虑节点的类型,分母是对图中的所有节点的特征表示求和,其实本质上和DeepWalk、node2vec差不多,因此论文又在此基础上提出了metapath2vec++,不同于metapath2vec的softmax函数,metapath2vec++用不同类型节点的特征表示进行归一化,softmax函数定义如下:

metapath2vec++对每种类型节点指定不同的一组多项式分布,相当于在输出层根据节点类型,把异质网络分解成不同的同质网络,同样采用负采用的方法简化计算.

具体算法如下伪代码:

4、Summary

论文比较有亮点的地方在于用元路径指导随机游走的的邻居节点的选择,本质上也是一种带偏置的随机游走,由元路径来指导随机游走的跳转,如果下一节点的类型满足元路径中的类型,那么跳转的概率就是该类型节点数分之一(等概率跳转),否则,全部为0。

metapath其实和deepwalk、node2vec的基本思想是一致的,最大化log概率(公式1),softmax函数归一化项不考虑节点的类型。
metapath++ 则考虑到softmax函数中对不同类型节点的归一化(公式3),这样就把异质网络转成了不同节点类型的同质网络。

综合看一下deepwalk、node2vec和这篇论文的metapath2vec,虽然处理的网络不同,分别对应同质网络和异质网络,但是其本质似乎都是通过随机游走选择邻居节点,然后用skip-garm模型学习节点的表示,不同的是随机游走的过程中,邻居节点(上下文节点)的跳转选择策略是不同的

写的还不错?那就来个红包吧!
0%