基于meta-path的异质网络Embedding-metapath2vec

metapath2vec: Scalable Representation Learning for Heterogeneous Networks

metapath2vec https://dl.acm.org/citation.cfm?id=3098036是17年发表的，使用基于meta－path的随机游走重构节点的异质邻居，并用异质的skip－gram模型求解节点的网络表示。DeepWalk 是同质网络中的表示学习方法，并不能直接应用到异质网络。比如：并不能解决多种类型节点的“word-context”对的问题，异质网络中的random walk问题。

本文提出了两种模型，metapath2vec 和 metapath2vec++。模型框架如下图所示：

Heterogeneous Skip-Gram
对于一个|TV|>1的异质网络G=(V,E,T)(ϕ:V→TV,ψ:E→TE)，metapath2vec通过skip-gram模型学习网络表示。给定一个节点v，它最大化节点的异质上下文(context) Nt(v),(t∈TV)
$a r g m a x θ \sum v \in V \sum t \in T V \sum c t \in N t (v) p (c t | v; θ) (1)$

条件概率p(ct|v;θ)定义为soft-max函数p(ct|v;θ)=exp(XctXv)∑u∈Vexp(XuXv)。
这个公式，每计算一次，就会遍历所有的节点，计算起来并不高效，根据Word2vector中的负采样优化，上式可以写为

l o g σ (X c t \cdot X v) + \sum m = 1 M E u m \sim P (u) l o g σ (- X u m \cdot X v)

metapath2vec在构建P(u)分布的时候，忽略了节点的类别信息。

Meta-path-based Random Walks
跟deep walk是类似的，本文也是通过随机游走的方式保留网络结构。但是在异质网络中，决定游走下一步的条件概率 p(vi+1|vi)不能像deep walk那样，直接在节点vi的所有邻居上做标准化（Normalized Probability）。如果这样做忽略了节点的type信息。yizhou su etc.在论文PathSim http://web.engr.illinois.edu/~hanj/pdf/vldb11_ysun.pdf中指出：异质网络上的随机游走生成的路径，偏向（biased）于高度可见的节点类型（具有优势/主导数量的路径的节点）和集中(concentrated)的节点（即：具有指向一小组节点路径的大部分百分比）。因而，本文提出了基于元路径的随机游走，捕获不同类型节点之间的语义和结构相关性。

给定一个异质网络 G=(V,E,T) 和meta-path P:V1⟶R1V2⟶R2⋯Vt⟶RtVt+1⋯⟶Rl−1Vl那么第i步的转移概率可定义为：

p (v i + 1 | v i t; P) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 1 N t + 1 (v i t) (v i + 1, v i t) \in E, ϕ (v i + 1) = t + 1 0 (v i + 1, v i t) \in E, ϕ (v i + 1) \neq t + 1 0 (v i + 1, v i t) \notin E

其中vit∈Vt, 并且Nt+1(vit)代表的是节点vit的邻居中属于t+1type的节点集合。换句话说，游走是在预先设定的meta-path P的条件上。而且，meta-path一般都是用在对称的路径上：

p (v i + 1 | v i t) = p (v i + 1 | v i 1), i f t = l

部分源代码
meta-path-based Random Walk的源代码连接https://www.dropbox.com/s/0ss9p4dh91i3zcq/py4genMetaPaths.py?dl=0
基于meta-path的异质网络Embedding-metapath2vec

作者在论文中用的meta-path是”APVPA”。

metapath2vec++
metapath2vec在计算softmax时，忽略了节点类型。换句话说，在采集负样本时，没有考虑样本是否与正样本属于同一个节点类型。因而本文提出，异质的负采样 (Heterogeneous negative sampling)。也就说条件概率p(ct|v;θ)在特定的节点类型上做标准化。
$p (c t | v; θ) = e x p (X c t \cdot X v) \sum u t \in V t e x p (X u t \cdot X v)$
这就为skip-gram最后一层输出层中的每个类型都指定了一个多项分布。负采样的目标函数：
$O (X) = l o g σ (X c t \cdot X v) + \sum m = 1 M E u m t \sim P t (u) [l o g σ (- X u m t \cdot X v)]$
实验
在实验方面，本文主要做了multi-class分类，节点聚类，相似性搜索，可视化。
本文将AMiner数据集按照论文发表的会议分为八大类，对于每个作者节点的标签，则是选择作者曾经发表的论文中，占比例较大的标签；如果是相等的，那么从中随机选择一个标签。
在聚类任务上，作者使用的是K-Means的方法，NMI指标。
从代码实现来看，本文主要研究的是作者-会议之间的一种关系，这种关系并不能直接观察到，而是通过作者-论文-会议这样一种路径构建的。因而，最终学到的只是作者、会议节点的embedding向量表示。在分类等任务上也是针对的作者，会议节点。

基于meta-path的异质网络Embedding-metapath2vec

metapath2vec: Scalable Representation Learning for Heterogeneous Networks

相关推荐