十一、metapath2vec

1. 目前为止绝大多数embedding 方法都集中在异质网络的表示学习representation learning 上，即网络的顶点类型是单一的，边的类型也是单一的。但是大量的社交网络以及其它信息网络本质上是异质heterogeneous的，网络包含多种顶点类型，也包含多种边的类型。因此异质网络表示学习的挑战在于：网络中存在多种类型的顶点和边。

   传统的 embedding 模型将不同类型的顶点和边采用相同的处理方式，这将导致为异质顶点生成没有类型区分的表示。因此这些异质网络是专门为同质homogeneous网络设计的 embedding 模型无法解决的。

   论文 《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》 首先形式化异质网络的表示学习问题，然后提出了 metapath2vec 框架，及其扩展的 metapath2vec ++ 框架来解决异质网络的表示学习问题。

2. 异质网络表示学习的目的是同时学习多种类型顶点的低维 embedding 。metapath2vec 框架基于meta-path 的随机游走从而构造顶点的异质邻域，然后利用异质 skip-gram 模型来执行顶点 embedding 。metapath2vec 的目标是最大化的保留给定异质网络的结构关系和语义关系。

   而 metapath2vec ++ 在 metapath2vec 的基础上使用了一种基于异质负采样的方法，称作 metapath2vec ++ ，该方法可以有效并且准确的预测顶点的异质邻域。

   大量实验表明，metapath2vec 和 metapath2vec ++ 不仅能够超越各种异质网络挖掘任务的 SOA 的 embedding 模型，还能够识别不同顶点之间的结构相关性和语义相关性。

3. metapath2vec 和 metapath2vec ++ 不同于传统的网络 embedding 模型，后者专注于同质网络。

   metapath2vec 和 metapath2vec++ 在某些方面也不同于 Predictive Text Embedding:PTE 模型。

   • 首先 PTE 是一种半监督学习模型，其中包含文本数据的标签信息。
   • 其次，PTE 中的异质性来自于文本网络，网络中存在了单词到单词的链接、单词到它所属文档的链接、单词及其 label 的链接。 因此本质上 PTE 的原始输入为单词，输出是每个单词的 embedding ，而不是多种类型的输入。

11.1 模型

11.1.1 问题定义

1. 论文对异质网络的表示学习进行了形式化。定义一个异质网络是一个图 ，其中每个顶点 和每条边 分别关联一个映射函数：

   

   其中 表示顶点类型， 表示边的类型，且满足 。

   例如可以用作者 author:A、论文 paper:P、会议 venue:V、组织 organization:O 作为顶点类型来表示下图中的学术网络。其中边可以表示coauthor 合作者关系 A-A、publish 发表关系 A-P,P-V、affiliation附属关系 O-A ，reference 引用关系 P-P 。黄色虚线表示 coauthor 关系，红色虚线表示引用关系。

   

2. 异质网络表示学习问题Heterogeneous Network Representation Learning：给定一个异质网络 ，任务的目标是学习一个 维的潜在表示 ，其中 ，使得该表示能够捕获网络的结构关系以及语义关系。任务的输出是一个低维矩阵 ，其第 列对应一个 维向量 ，即顶点 的 embedding 。

   • 尽管 中存在不同类型的顶点，但是各种类型顶点的 embedding 都被映射到相同的潜在空间中。
   • 学到的顶点 embedding 可以应用于各种异质网络挖掘任务，如顶点分类、聚类、相似性查找等。
   • 问题的挑战来自于网络异质性。网络embedding 模型的基本假设是：在embedding 空间保持顶点及其邻居（上下文）之间的邻近性。但是在异质网络中，如何定义和建模 “顶点 - 邻居” 的概念？另外模型如何优化，其中该模型有效维护多种类型顶点和边的结构关系和语义关系？

11.1.2 metapath2vec

1. 论文提出了一个通用的异质网络embedding 学习框架 metapath2vec，其目标是：在考虑多种类型的顶点和边的情况下，最大化网络的概率。

2. 首先考虑 word2vec 模型。给定网络 ，模型的目标是根据局部结构来最大化网络概率：

   

   其中 为网络 中顶点 的邻域，它可以由不同的定义方式，如 的直接相连的顶点集合； 定义了给定顶点 的条件下，上下文 出现的条件概率。

   为了对顶点的异质邻域建模，metapath2vec 引入了异质 skip-gram 模型 Heterogeneous Skip-Gram。为了将异质网络结构融合到异质 skip-gram 模型中，metapath2vec 引入了基于 meta-path 的随机游走。

3. 异质 skip-gram 模型：在 metapath2vec 中，给定异质网络 ，其中 表示顶点类型， 表示边的类型，。我们通过最大化给定顶点 的条件下，异质上下文 的条件概率，使得 skip-gram 能够学习异质网络 的有效顶点表示：

   

   其中：

   • 表示顶点 的第 种类型的邻域顶点。考虑下图的学术网络，其中author 顶点 的邻域可以为：author 邻域 ；venue 邻域 ，organization 邻域 ；paper 邻域 。

     

   • 通常由一个 softmax 函数定义：

     

     其中 为 的第 列，是顶点 的 embedding 向量。

   为了有效优化目标函数，Milkolov 等人引入了负采样，它从网络种随机采样相对较小的一组顶点来代替 softmax 。metapath2vec 也采用了相同的负采样技术。给定一个负采样大小 ，则定义：

   

   其中：

   • 
   • 为预定义的顶点分布函数，根据该分布来采样 个负采样顶点 。metapath2vec 无视顶点类型来构建顶点的频率分布。

4. 基于 meta-path 的随机游走：如何有效的将网络结构转化为 skip-gram？在 DeepWalk 和 node2vec 中，这是通过将 random walker 在网络上遍历的顶点路径结合一个邻域函数来实现的。

   我们也可以将 random walker 放到异质网络中，从而生成多种类型顶点的路径。在随机游走的第 步，我们定义转移概率 为：在顶点 的邻域上的归一化概率分布，其中忽略顶点类型。然后将生成的游走序列作为 node2vec 和 DeepWalk 的输入。

   但是， Sun 等人证明了：异质随机游走偏向于高度可见的顶点类型（即那些在路径中频繁出现的顶点类型），以及中心顶点（即那些出现频繁出现在关键路径中的顶点）。有鉴于此，metapath2vec 设计了基于 meta-path 的随机游走，从而生成能够捕获不同类型顶点之间的语义相关性和结构相关性的游走序列，从而有助于我们将异质网络结构转化为异质 skip-gram 。

   形式化的，一个 meta-path 范式 定义为一个路径：

   

   其中 定义顶点类型 之间的一个组合关系。以下图为例：meta-path:APA 代表两个作者 A 在同一论文 P 上的 co-author 关系；meta-path:APVPA 代表两个作者 A 在同一个会议 V 的不同论文 P 上的 co-venue 关系。

   

   先前的工作表明：异质信息网络中的许多数据挖掘任务都可以通过 meta-path 建模受益。这里我们展示如何利用 meta-path 来指导异质 random walker 。

   给定一个异质网络 以及一个 meta-path 范式 ，在随机游走的第 步的转移概率定义为：

   

   其中： 表示第 步的顶点； 表示顶点 的、类型为 的邻居顶点。

   • 由于 ，这意味着 random walker 必须根据预定义的 meta-path 来游走。

   • 通常meta-path 都是对称的，如 ，因此有：

     

   • 基于 meta-path 的随机游走策略可以确保不同类型顶点之间的语义关系可以正确的合并到 skip-gram 中。

     如下图所示，假设上一个顶点为 CMU，当前顶点为 。在传统的随机游走过程中，下一个顶点可能是 周围的顶点 。但是在meta-path 的范式 OAPVPAO 下，下一个顶点倾向于论文类型的顶点 ，从而保持路径的语义。

     

11.1.3 metapath2vec ++

1. metapath2vec 在创建顶点 的邻域 时，根据上下文顶点的类型来区分顶点 的上下文顶点。但是它忽略了 softmax 函数中的顶点类型信息。即：在给定顶点 的条件下，为了推断来自邻域 中的上下文 的顶点类型，metapath2vec 实际上采用了所有类型的负样本，包括相同类型 的负样本，以及其它类型的负样本。

   论文提出的 metapath2vec ++ 框架采用异质负采样策略 heterogeneous negative sampling 。该框架中，softmax 根据上下文顶点 的类型进行归一化，即 根据指定的顶点类型 来调整：

   

   其中 为类型为 的顶点集合。

2. metapath2vec ++ 会为 skip-gram 模型输出层中的每种邻域类型定义一组 softmax 分布。

   在 metapath2vec、node2vec、DeepWalk 中，输出softmax 分布的维度等于网络的顶点数量 。但是在 metapath2vec ++ 中，输出 softmax 分布的维度由类型为 的顶点数量 决定。

   如下图所示给定顶点 ，metapath2vec ++ 输出四组softmax 分布，每一组分布对应于不同的邻域顶点类型：会议V、作者 A、组织 O、论文 P 。 给出了类型为 的顶点集合， 。 给出了顶点邻域中类型为 的邻居顶点数量， 。

   

3. 受到 PTE 的启发，metapath2vec 在负采样过程中同样可以根据邻居顶点 的类型进行调整，因此有目标函数：

   

   其中 为类型为 的顶点的分布函数。

   目标函数的梯度为：

   

   其中 为一个示性函数，用于指示 是否为邻域上下文顶点 ，并且当 时 。

   最终可以通过随机梯度下降算法来对模型进行优化求解。

4. metapath2vec++ 算法：

   • 输入：

     • 异构网络
     • 一个 meta-path 范式
     • 每个顶点开始的游走序列的数量
     • 每条游走序列的长度
     • embedding 维度
     • 邻域大小 （即窗口大小）

   • 输出：顶点的 embedding 矩阵

   • 算法步骤：

     • 初始化

     • 迭代 ，迭代步骤为：

       遍历图 中的每个顶点 ，执行：

       

     • 返回

5. MetaPathRandomWalk 算法：

   • 输入：

     • 异构网络
     • 一个 meta-path 范式
     • 当前顶点
     • 每条游走序列的长度

   • 输出：一条 meta-path 随机游走序列

   • 算法步骤：

     • 初始化：

     • 迭代 ，迭代过程为：

       根据 采样顶点 ，并记录

     • 返回

6. HeterogeneousSkipGram 算法：

   • 输入：

     • 当前的
     • 邻域大小
     • 随机游走序列 ，以及它的长度

   • 输出：更新后的

   • 算法步骤：

     • 迭代 ，迭代步骤为：

       取出当前顶点 , 对左侧的 个顶点、右侧的 个顶点共计 个顶点进行更新：

       

       其中 为学习率。

7. 下图给出了异质学术网络heterogeneous academic network ，以及学习该网络embedding 的 metapath2vec/metapath2vec ++ 的 skip-gram 架构。

   • 图 a 的黄色虚线表示 co-author 关系，红色虚线表示论文引用关系。
   • 图 b 表示 metapath2vec 在预测 的上下文时，使用的 skip-gram 架构。其中 为顶点数量， 的邻居顶点包括 ，窗口大小 。
   • 图 c 表示 metapath2vec ++ 在预测 的上下文时，使用的 skip-gram 架构。

   

11.2 实验

1. 这里我们展示了 metapath2vec/metapath2vec ++ 用于异质网络表示学习的效果和效率。我们评估了经典的三种异质网络挖掘任务，包括：顶点分类问题、顶点聚类问题、顶点相似性查找问题。

   另外，我们还通过 tensorflow 的 embedding 可视化来观察异质学术网络中学到的顶点 embedding 。

2. 数据集：我们使用以下两个异质网络，它们都是公开的：

   • AMiner Computer Science(CS) dataset：包含 2016 年之前j举行的 3883 个计算机科学venue（包含会议 conference 和期刊 journal ）的 9323739 名计算机科学家，以及 3194405 篇论文。

     我们构建了一个异质网络，该网络包含三种类型的顶点：作者 A、论文 P、venue:V 。

   • Database and Information Systems(DBIS) dataset：包含 464 个会议，以及其中 top-5000 个作者，以及对应的 72902 篇论文。

     我们也构建了一个异质网络，该网络包含四种类型的顶点：作者 A、论文 P、venue:V 。

3. 基准模型：我们将 metapath2vec/metapath2vec ++ 和以下几种 embedding 方法比较：

   • DeepWalk/node2vec ：在相同的随机游走序列输入下，我们发现 DeepWalk 的hierarchical softmax 和 的 node2vec 的负采样之间并未产生显著差异，因此我们这里采用 的 node2vec 。
   • LINE：我们使用同时采用了1 阶邻近度和 2 阶邻近度的 LINE 模型。
   • PTE：我们构建了三个异质二部图 A-A, A-V, V-V ，并将其作为无监督 embedding 学习方法的约束。
   • 谱聚类Spectral Clustering/图的因子分解 Graph Factorization：因为早前的研究表明 DeepWalk 和 LINE 的性能超越了它们，因此这里并不考虑这两种方法。

4. 参数配置：对于所有模型，我们使用以下相同的参数：

   • 每个顶点开始的随机游走序列数量

   • 每个随机游走序列长度

   • 隐向量维度 。注意：对于 LINE 模型，其一阶embedding 和 二阶 embedding 的维度都是 128 。

   • 邻域尺度

   • 负采样大小

   • 对于 metapath2vec/metapath2vec ++ ，我们还需要指定 meta-path 范式来指导随机游走的生成。我们调查了大多数基于 meta-path 的工作，发现异质学术网络中最常用和有效的meta-path 范式是 APA 和 APVPA 。

     我们的实验表明：meta-path 范式 APVPA 产生的顶点 embedding 可以泛化到各种异质学术网络的挖掘任务中。

   最后，在参数敏感性实验中，我们对参数中的一个进行变化，同时固定其它参数来观察 metapath2vec/metapath2vec ++ 的效果。

11.2.1 顶点分类

1. 我们使用第三方的 label 来确定每个顶点的类别。

   • 首先将 Google Scholar 中的八个会议的研究类别与 AMiner 数据中的会议进行匹配：

     1
     Computational Linguistics, Computer Graphics, Computer Networks & Wireless Communication, Computer Vision & Pattern Recognition, Computing Systems, Databases & Information Systems, Human Computer Interaction, Theoretical Computer Science
     

     每种类别20 个会议。在这 160 个会议中，有 133 个已经成功匹配并进行相应的标记。

   • 然后，对于这 133 个会议的论文的每位作者，将他/她分配给他/她大部分论文的类别，如果论文类别分布均匀则随机选择一个类别。最终有 246678 位作者标记了研究类别。

2. 我们从完整的 AMiner 数据集中学到顶点的 embedding ，然后将上述顶点标记以及对应的顶点 embedding 一起作为逻辑回归分类器的输入。

   我们将训练集规模从标记样本的 5% 逐渐增加到 90% ，并使用剩下顶点进行测试。我们将每个实验重复十轮，并报告平均的 macro-F1 和 micro-F1 。

   下表给出了 Venue 类型顶点的分类结果。

   

   下表给出了 Author 类型顶点的分类结果：

   

   结论：

   • metapath2ve/metapath2vec ++ 模型始终一致且明显的优于所有其它基准方法。
   • 在预测 venue 类别顶点时，由于训练数据量比 author 类别顶点少得多，因此 metapath2vec/metapath2vec ++ 的优势特别明显。

3. 我们接下来对 metapath2vec ++ 的几个通用参数进行超参数敏感性分析。我们变化其中的一个超参数，然后固定其它的超参数。

   结论：

   • 从图 a 和 b 可以看到，参数 和 对于 author 顶点的分类性能是正相关的，其中 、 左右，author 顶点分类性能提到到峰值附近。

     但是令人惊讶的是， 对于 venue 顶点的分类性能无关。

   • 从图 c 和 d 可以看到，embedding 尺寸 和邻域大小 与 venue 顶点分类性能无关。而 对于 author 顶点分类性能至关重要，下降的曲线表明较小的邻域大小对于 author 顶点能够产生更好的 embedding 表示。

     这和同质图完全不同。在同质图中，邻域大小 通常对顶点分类显示出积极影响，而这里是消极影响。

   • 这些通用的超参数在异质网络中表示出和同质网络中不同的效果，这表明对于异质网络表示学习需要采用不同的思路和解决方案。

   

11.2.2 顶点聚类

1. 我们采用与上述分类任务中使用的相同的八个类别的 author 顶点和 venue 顶点，我们针对这些顶点的 embedding 进行聚类。这里我们使用 k-means 聚类算法，并通过归一化的互信息 NMI 来评估聚类效果。

   所有聚类实验均进行十次，并报告平均性能，结果如下表所示。结论：

   • 总体而言，metapath2vec 和 metapath2vec ++ 优于其它所有方法。
   • 从 venue 顶点聚合结果可以看到，大多数方法的NMI 都较高，因此该任务相对容易。而 author 顶点聚类指标都偏低，因此任务更难。

   

2. NMI 指标：给定随机变量 ，则归一化的互信息定义为：

   

3. 和分类实验的步骤相同，我们研究了聚类任务中 metapath2vec ++ 的参数敏感性，衡量指标为 NMI 。

   • 从图 a 和 b 可以看到，author 顶点和 venue 顶点在 时可以在效果和计算效率之间取得平衡。

   • 从图 c 和 d 可以看到，对于 author 顶点， 和 与聚类性能呈负相关；而对于venue 顶点， 也与聚类性能负相关，但是 增加时聚类 NMI 先增加后减小。

     对于 author 顶点和 venue 顶点，当 时，生成的 embedding 可以得到较好的聚类结果。

   

11.2.3 相似度查找

1. 我们从 AMiner 数据集选择 16 个不同领域的顶级 CS 会议，然后通过余弦相似度选择这些会议顶点的 top 10 相似度结果。

   结论：

   • 对于query 顶点 ACL，metapath2vec++ 返回的venue 具有相同的主题 NLP ，如 EMNLP(1st)、NAACL(2nd)、Computational Linguistics(3rd)、CoNLL(4th)、COLING(5th) 等等。

     其它领域的会议的 query 也有类似的结果。

   • 大多数情况下，top3 结果涵盖了和 query 会议声望类似的venue。例如theory理论领域的 STOC 和 FOCS、system系统领域的 OSDI 和 SOSP、architecture 架构领域的HPCA 和 ISCA、security 安全领域的 CCS 和 S&P、human-computer interaction 人机交互领域的 CSCW 和 CHI、NLP 领域的 EMNLP 和 ACL、machine learning 机器学习领域的 ICML 和 NIPS、web 领域的 WSDM 和 WWW、artificial intelligence 人工智能领域的 AAAI 和 UCAI、database 数据库领域的 PVLDB 和 SIGMOD 等等。

   

2. 类似的，我们从 DBIS 数据中选择另外的 5 个 CS 会议，然后通过余弦相似度选择这些会议顶点的 top 10 相似度结果。结论也类似。

   

3. 我们从 DBIS 数据中选择一个会议顶点、一个作者顶点，然后比较不同 embedding 方法找出的 top-5 相似度的结果。结果如下表所示，其中 metapath2vec ++ 能够针对不同类型的 query 顶点获得最佳的 top-5 相似顶点。

   

11.2.4 可视化

1. 我们使用 tensorflow embedding 2 维 PCA 来进一步可视化模型学到的顶点 embedding 。我们从 AMiner 数据集选择 16 个不同领域的顶级 CS 会议，以及对应的顶级作者进行可视化。

   • 从图 d 可以看到，metapath2vec++ 能自动组织这两种类型的顶点，并隐式学习它们的内部关系。这种内部关系可以通过连接每对顶点的箭头的方向和距离表示，如 J.Dean --> OSDI，C.D.Manning --> ACL，R.E.Tarjan --> FOCS，M.I.Jordan --> NIPS 等等。

     这两类顶点位于两个独立的“列”中，很显然图 a 和 b 的 embedding 无法达到同样的效果。

   • 从图 c 可以看到，metapath2vec 能够将每对 “作者-会议” pair 对进行紧密的分组，而不是将两种类型的顶点分类两列。如 R.E.Tarjan + FOCS、H.Jensen + SIGGRAPH、H.Ishli + CHI、R.Agrawal + SIGMOD 等等。 常规的 embedding 方法也无法达到这种效果。

   • metapath2vec/metapath2vec++ 都可以将来自相似领域的顶点放在一起、不同领域的顶点相距较远。这种分组不仅可以通过会议顶点来反映，还可以通过作者顶点来反映。

   

2. 下图通过 t-SNE 可视化了metapath2vec++ 学到的AMiner 数据集不同领域的顶级 CS 会议，一共48 个会议、16个领域，每个领域 3 个会议。

   • 可以看到：来自同一个领域的会议彼此聚在一起，并且不同组之间的间隔比较明显。这进一步验证了 metapath2vec++ 的 embedding 能力。
   • 另外，异质 embedding 能够揭示不同领域的顶点之间的相似性。如，右下角的 Core CS 领域的几个簇、右上角的 Big AI 领域的几个簇。

   

11.2.5 可扩展性

1. metapath2vec/metapah2vec ++ 可以使用和 word2vec/node2vec 中相同的机制来并行化。我们对 AMiner 数据集进行实验，实验在 Quad 12(48) core 2.3 GHz Intel Xeon CPUs E7-4850 上进行。我们实现不同的线程数 {1,2,4,8,16,24,32,40} ，每个线程使用一个 CPU core 。

   下面给出了metapath2vec/metapath2vec++ 的加速比。最佳加速比由虚线 表示。我们的这两种方法都可以达到能够接受的亚线性加速比，它们都接近于虚线。

   具体而言，在使用 16 个 core 时，它们可以实现 11-12 倍的加速比；使用 40 个 core 时，它们可以实现 24-32 倍加速比。

   

2. 在使用 400 个 core 时，metapath2vec ++ 的学习过程只需要 9 分组即可训练整个 AMS CS 网络的 embedding ，该网络由 900 万以上的作者、3300 多个 venue、300 万篇论文组成。

   总体而言，对于具有数百万个顶点的大规模异质网络，metapath2vec/metapath2vec++ 是有效的且 scalable 的。

11.2.6 未来方向

1. metapath2vec/metapath2vec++ 模型和 DeepWalk/node2vec 一样，在对网络采样生成大量随机游走路径时，面临大量中间临时输出数据的挑战。因此识别和优化采样空间是一个重要方向。
2. 和所有基于 meta-path 异质网络挖掘方法一样，可以通过自动学习有意义的 meta-path 来进一步改善 metapath2vec/metapath2vec++ 。