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

转载 2019-11-23 22:31  阅读 12 次 评论 0 条

metapath2vec是2017年KDD上的一个工作,提出了对异质网络的表示学习算法metapath2vec和metapath2vec++。异构网络的最大挑战来源于不同种类的节点与连接,因此限制了传统network embedding的可行性。论文提出了两种特征学习模型:metapath2vec以及metapath2vec++,它们的具体做法是基于元路径的随机游走来指定一个节点的邻居,之后利用异构skip-gram模型来实现embedding。

传统的网络挖掘方法,一般都是先将网络转化成邻接矩阵,然后再用机器学习的模型从而完成网络挖掘任务,比如社区检测,连接预测,离群点检测等等。然而这样的话,邻接矩阵通常都很稀疏,且维数很大。network embedding是近来比较火的领域,近几年也是发展迅猛。它主要是从网络中学到隐式的表达矩阵,使得网络重要的信息能够被包含在一个新的相对低维的空间向量中,之后再对这个隐式表达矩阵采样机器学习的算法,从而能够更好地完成网络挖掘任务。

近年来各种顶会上也出现了很多network embedding的文章,公认不错的一些算法有deepwalk, node2vec, line等等,然而它们大多数都是针对同构网络的,也就是忽略了网络的异质性,只考虑一种节点对象中的一种关系。然而,现实生活中更多存在的网络是包含不多种类的节点以及连接。比如在DBLP网络,节点种类有会议,论文,作者等,而不同种类节点之间的连接也代表着不同语义,比如说论文和论文之间存在着引用和被引用关系,作者和作者存在合著关系,论文和会议存在发表/被发表关系。因此相比于同构网络,异构网络融合了更多信息,以及包含更丰富的语义信息。所以作者提出了两个在异构网络做network embedding的算法模型,metapath2vec以及metapath2vec++。

1 Problem Definition

1.1 Heterogeneous Network

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

给定图G=(V,E,T),存在映射:\(ϕ(v):V→T_V\)和\(φ(e):E→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(|TV|>1)的异质网络,给定节点v的上下文节点Nt(v),最大化如下的概率:

\(\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)}}}\)

其中,Nt(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函数,Xv表示节点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}\)

跳转概率定义为:

\(p(v^{i+1}|v^i_t,\mathcal{P}) =
\begin{cases}
\frac{1}{|N_{t+1}(v_t^i)|}& (v^{i+1},v_t^i)\in{E},\phi(v^{i+1})=t+1 \\
0& (v^{i+1},v_t^i)\in{E},\phi(v^{i+1})\neq{t+1}\\
0& (v^{i+1},v_t^i)\notin{E}
\end{cases}\)

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

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

3 metapath2vec++

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

\(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}}}}\)

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

4 Summary

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

metapath其实和deepwalk node2vec的基本思想是一致的,最大化log概率(公式1),softmax函数归一化项不考虑节点的类型。

metapath++ 则考虑到softmax函数中对不同类型节点的归一化(公式3),这样就把异质网络转成了不同节点类型的同质网络。

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

论文下载:

metapath2vec Scalable Representation Learning for Heterogeneous Networks

本文地址:http://51blog.com/?p=6270
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 ROOTLu ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情