Metapath2vec: Scalable Representation Learning forHeterogeneous Networks

2021-06-04

论文笔记 / 图学习 / 异构网络

字数统计: 2.1k | 阅读时长≈ 9 分钟

https://dl.acm.org/doi/pdf/10.1145/3097983.3098036

https://github.com/apple2373/metapath2vec

Metapath2vec: Scalable Representation Learning forHeterogeneous Networks ，KDD，2017

总结：未完待续… …

1. 简介

1.1 摘要

We study the problem of representation learning in heterogeneousnetworks. Its unique challenges come from the existence of mul-tiple types of nodes and links, which limit the feasibility of theconventional network embedding techniques. We develop twoscalable representation learning models, namelymetapath2vecandmetapath2vec++. The metapath2vec model formalizes meta-path-based random walks to construct the heterogeneous neighborhoodof a node and then leverages a heterogeneous skip-gram modelto perform node embeddings. The metapath2vec++ model furtherenables the simultaneous modeling of structural and semantic correlations in heterogeneous networks. Extensive experiments show that metapath2vec and metapath2vec++ are able to not only outperform state-of-the-art embedding models in various heterogeneous network mining tasks, such as node classification, clustering, and similarity search, but also discern the structural and semantic correlations between diverse network objects.

本文主要研究异构网络表示学习。异构网络中存在多种类型的边和节点，这限制了很多传统表示学习方法的可行性，因此异构网络表示学习存在很多挑战。作者设计了两种scalable表示学习模型，metapath2vec和metapath2vec++。metapath2vec对基于元路径的随机游走进行格式化来构建每个节点的异构邻居，再用一个异构skip-gram模型来学习节点embedding。metapath2vec++模型则进一步对网络中的结构和语义相关性同时进行建模。大量实验表明作者提出的这两个模型不仅在各种异构网络挖掘任务中表现优秀，还能识别不同网络对象之间结构和语义上的相关性。

1.2 本文工作

受NLP领域一些模型启发，DeepWalk、LINE和node2vec等被提出用于网络表示学习，但是这些工作都是针对于同构网络表示学习的，将其直接用于异构网络存在诸多问题。比如在异构学术网络中，如何获取多种类型节点之间的上下文关系？可以直接将DeepWalk中的随机游走应用于有多种类型节点的网络中吗？能直接将同构网络中的嵌入架构（比如skip-gram）直接应用到异构网络中吗？

本文作者针对上述challenges，提出了metapath2vec模型，学习潜在的异构网络嵌入，用于各种网络挖掘任务。和传统的基于meta-path的方法相比，潜在空间表示学习的优势在于可以对没有元路径相连接的两个节点的相似性进行建模。

作者在metapath2vec中首先基于meta-path的随机游走，针对各种类型节点生成具有网络语义的异构领域。然后在利用skip-gram模型对位置上和语义上相近的节点进行建模。最后作者设计了一种基于异构负采样的方法，称为metapath2vec++，可以准确有效地预测节点的异构邻居。

1.3 问题定义

2. MetaPath2Vec

metapath2vec主要参考DeepWalk和node2vec方法，利用基于metapath的随机游走，将这两个算法拓展到异构网络中。DeepWalk和node2vec这两个方法大概思想是：给定一个图 $G=(V,E)$ ，进行随机游走，将节点看做单词，游走路径看做NLP中的句子，再利用skip-gram模型进行训练，目标是最大化邻居共现概率，即：

\arg \max _{\theta} \prod_{v \in V} \prod_{c \in N(v)} p(c \mid v ; \theta)\tag 1

其中 $N(v)$ 表示节点v的邻居，邻居定义方式有很多种可以是一阶邻居、二阶邻居、语义上的邻居等等。 $p(c|v;\theta)$ 表示给定节点v，上下文节点c出现的概率。

skip-gram

基于meta-path的随机游走

普通随机游走

将随机游走器放在网络中，第i步，以 $p(v^{i+1}|v^i)$ 概率从节点 $v^i$ 前进到节点 $v^{i+1}$ ，以此类推。当游走路径长度达到要求后，将得到的游走路径作为node2vec和DeepWalk的输入。

sun等人证明了直接将随机游走应用在异构网络中存在问题。因此作者设计了一种基于元路径的游走策略。

定义一种元路径模式 $\mathcal P$ ，表示 $V_{1} \stackrel{R_{1}}{\longrightarrow} V_{2} \stackrel{R_{2}}{\longrightarrow} \cdots V_{t} \stackrel{R_{t}}{\longrightarrow} V_{t+1} \cdots \stackrel{R_{l-1}}{\longrightarrow} V_{l}$ ， $R=R_1\circ R_2\circ···\circ R_{l-1}$ 表示从 $V_1$ 类型节点到 $V_l$ 类型节点路径上的所有边的关系集合。

QQ截图20210408155753.png

比如上图中，元路径“APA”表示合作者关系，元路径“APVPA”表示两个作者在同一个会议/期刊上发表了文章。之前很多工作都表明meta-path对于异构信息网络上的数据挖掘很有用。

本文作者提出的基于meta-path的随机游走具体细节如下：

给定一个异构网络 $G=(V,E,T)$ ，一种元路径模式 $\mathcal P:V_{1} \stackrel{R_{1}}{\longrightarrow} V_{2} \stackrel{R_{2}}{\longrightarrow} \cdots V_{t} \stackrel{R_{t}}{\longrightarrow} V_{t+1} \cdots \stackrel{R_{l-1}}{\longrightarrow} V_{l}$ ，第i步的转换概率定义如下：

p\left(v^{i+1} \mid v_{t}^{i}, \mathcal{P}\right)=\left\{\begin{array}{cl} \frac{1}{\left|N_{t+1}\left(v_{t}^{i}\right)\right|} & \left(v^{i+1}, v_{t}^{i}\right) \in E, \phi\left(v^{i+1}\right)=t+1 \\ 0 & \left(v^{i+1}, v_{t}^{i}\right) \in E, \phi\left(v^{i+1}\right) \neq t+1 \\ 0 & \left(v^{i+1}, v_{t}^{i}\right) \notin E \end{array}\right.\tag 3

其中 $v_t^i\in V_t$ 表示类型为t的节点， $N_{t+1}(v_t^i)$ 表示 $v_t^i$ 邻居中类型为 $V_{t+1}$ 的节点。

注：元路径通常都定义成对称的

基于元路径的随机游走策略可以保证不同类型节点之间的语义关系可以被整合到skip-gram模型中。还以下图为例，如果采用普通的随机游走，从CMU节点转移到 $a_4$ （A）节点后，下一步可能转移到 $a_2,a_3,a_5,p_2,p_3,CMU$ 中任意一个节点（这包括了三种类型）。但是如果定义“OAPVPAO”形式元路径对其进行约束，鉴于前一个节点类型是‘O’，那么下一步模型会遵循元路径的语义信息，更倾向于像Paper类型节点转移。