异质图分析——概念与基本方法

近年来，网络型数据受到广泛关注。典型的网络比如社交网络，构建了人与人之间的关系。以微博为例，每一个用户可以看做网络中的一个节点，如果一个用户关注了另一个用户，那么两者之间就存在一条连边。这就是一个典型的网络型数据。

随着技术的发展，仅仅关注于一类节点（如微博网络中，节点都是用户）与一类边（如微博网络中，边都代表关注关系）构成的网络只能分析现实生活中一部分的网络型数据。在更多情况下，我们可能需要考虑更复杂的网络。例如，在一个典型的学术网络中，我们要考虑的节点就有三类：作者、文章与杂志，由此产生的关系也就多种多样。例如作者与文章之间会有“写作/被写作”关系，文章与杂志间会有“发表/被发表”关系，文章之间也会有“引用/被引用”的关系。像这样由多种节点与多种边构成的网络，我们常常称为异质信息网络（Heterogeneous Information Network）或者异质图（Heterogeneous Graph）。今天我们将基于以下两篇综述性文章，介绍异质图建模的相关概念与经典方法：

1. Shi, Chuan, et al. “A Survey of Heterogeneous Information Network Analysis.” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 1, 2017, pp. 17–37.
2. Wang, Xiao, et al. “A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources.” ArXiv Preprint ArXiv:2011.14867, 2020.

基本定义

在这一部分，我们参照两篇文章，给出异质图相关概念的规范定义。

1.Heterogeneous Graph

一个图由一群节点与边构成，即。其中，代表节点集合，其中每一个元素都是一个节点；代表边集合，其中每一个元素都是一条边。在异质图中，我们有多种类型的节点，因此我们还需要一个节点类型映射，它将每一个节点对应到其属于的节点类型，这里就是所有节点类型的集合。同理，也有一个边类型映射，其中是所有边类型的集合。在传统的同质图中，我们仅有一类节点与一类边，此时。而在异质图中，我们要求或者。下图1（a）展示了一个学术网络的例子，图中不同颜色的连接就代表不同类型的边。

图 1 异质图示例(a)及其网络范式(b)

2.Network schema

网络范式定义为，是针对图的节点类型集与边类型集而言的，是对图结构的抽象。用具体例子更好理解，图1(b)展示了学术网络对应的网络范式，图中包含学术网络节点类型及其可能的相互关系。经过这种抽象，学术网络的基础结构就更为清晰了。

3.Meta-path

元路径是连接两个节点的路径，其基本形式是。其中，，分别表示节点类型与边类型。不同的元路径描述了不同的语义关系（semantic relationship）例如，在学术网络中，作者到作者有两种路径：

a. (作者-文章-作者)。这表示两个学者有合作论文（Co-author）

b. (作者-文章-会议-文章-作者)。这反映两个学者在同一会议发表了文章。

4.Heterogeneous graph embedding

异质图嵌入的目标是学习一个函数，将图中的每一个节点映射到低维欧式空间，且。在对图进行建模时，我们需要将其转化为计算机可以识别的数字。面对个节点，最简单的办法就是用元素非0即1的维向量（即one-hot法）。例如，第一个节点是，第二个节点。这样我们就可以将每一个节点区分开来，但这就会导致维数过大，且难以描述两者间的关系。通过embedding方法，我们仅需要使用一个远小于的维向量来表示各个节点。一个好的embedding，是下游任务的基础。

常见的异质图

事实上，很多网络数据都可以归类为异质图的一种。在这一部分我们给出一些统计或计算机学科中常研究的一些异质图。

图 2 常见的异质图类型

1.Multi-Relational Network with Single-Typed Object

图2(a)展示了一个一类节点间存在多重关系的网络。这种网络结构在社交网络（例如微博）中十分常见，我们研究的对象都是用户，但用户间可能有多种关系（如聊天、关注、浏览等等）

2.Bipartite Network

二部图（也称双模网络）也是异质图的一种。在这种网络中，我们有两类节点，且边只存在于两类节点间，没有同类相连的边。图2(b)展示了用二部图来表示文本的例子，节点有文章与词两类，如果文章中包含相应的词，则有边相连。这类网络在以往的文献中已有丰富的研究。

3.Star-Schema Network

Star-schema是目前异质图研究中的重点。在这种网络中，我们关注一类核心节点（即Star），其余的对象都围绕它展开。图2(c)中的学术网络就是一个典型的Star-Schema式网络，学术网络中的核心是文章，其他类型的节点都通过与它相连加入到网络中。

4.Multiple-Hub Network

除了一类对象为网络核心，一些网络可能由多个中枢(Hub)组成，这就构成了所谓的Multiple-hub Network。图2(d)展示了生物信息学中的一个例子。在这一网络中存在两个中枢：基因与化合物。

除了上述类型的网络，现实生活中可以构建出更多复杂的异质图，这些网络甚至难以用一个简单的范式进行描述。例如，广为研究的知识图谱也可以被认为是异质图的一种，但其成千上万种节点与边几乎不可能用异质图的研究框架来分析。

网络数据挖掘已经在多种任务中应用，例如排序、聚类、链路预测、影响力分析等。然而，异质图仍存在其特殊性，如果直接应用同质图的方法将带来信息损失。Shi, et al.(2017)从以下三个方面总结了进行异质图分析的意义。

异质图分析的意义

网络数据挖掘已经在多种任务中应用，例如排序、聚类、链路预测、影响力分析等。然而，异质图仍存在其特殊性，如果直接应用同质图的方法将带来信息损失。Shi, et al.(2017)从以下三个方面总结了进行异质图分析的意义。

1.A New Development of Data Mining

早期的数据挖掘关注于研究对象的各种特征，也就形成了典型的表格型数据。20世纪以来，随着互联网的普及，各式各样的数据激增，研究者也更关注对象间的关联（links），从而产生了网络。但在如今，不同类型的对象也互相关联，这就超出了同质图的表示范围。因此，异质图分析是从解决现实问题的角度提出的。

2.An Effective Tool to Fuse More Information

在异质图中，我们可以通过引入各种不同类型的节点，来丰富网络中蕴涵的信息。例如，同质图往往是从单一数据源构建，但现在我们可以轻松获得各种来源的数据，它们从不同角度提供了研究对象的信息。通过异质图，我们可以有效地将这些信息融合在一起，统一分析。

3.Rich Semantics

丰富的语义信息也是异质图的一大特点。各种类型的节点，通过各种类型的边联通，反映出不同的含义。正如我们前文提到的学术网络，其元路径APA或APCPA就代表了两个作者间不同的关系。例如，通过APA路径，你可能会发现与某一作者最相似的作者是其学生，因为他们经常合作论文。但通过APCPA路径，可能最相似的就是同一领域的其他知名学者。不同语义蕴涵的信息将在不同的研究兴趣中发挥作用。

异质图嵌入

为了分析异质图数据，首先要面对的问题就是embedding。在这一部分，我们基于Wang, et al.(2020)的分类介绍几种构建embedding的主要思想及其中的代表性方法。

1.Structure-preserved HG Embedding

这一类方法的核心思想是使学习得到的embedding尽可能保留异质图的结构信息，例如link、meta-path信息。一个代表性的工作就是PME（Chen, et al. 2018），对于通过关系相连的两个节点与，作者希望其embedding尽可能的相似。即我们要最小化距离：

式中，指的是两个节点的embedding。需要注意的是，由于异质图中存在不同种类的关系，因此在考虑两个节点的距离时，也应当基于不同关系进行计算。作者为每一种关系定义了一个映射矩阵，通过这一变换，将原始embedding转化到关系对应的空间中，再计算两节点间的距离。代表的是两个节点间边的权重。定义了两个节点间的距离，作者使用triple-loss进行训练：

式中，是网络中存在关系的节点对（即正样本），则是不存在关系的节点对（即负样本）。我们的目标是要让存在的关系的节点对距离相比于负样本尽可能小。这里设定了一个阈值及，只有当两者差距大于这一阈值，才会产生损失。通过这种无监督的方式，我们就可以从数据中学习到相应节点、边的embedding。

然而，基于link的方式仅仅保留了节点间的一阶关系（first-order relation），节点的高阶信息同样重要。例如，我们在学术网络中，不仅仅保留A（作者）和P（文章）的连接，更需要保留路径APA进行连接的A（作者1）与A（作者2）之间的关系。因此，就有学者提出了基于meta-path的embedding。

早期的一些方法借鉴了文本embedding的思路，在网络中进行随机游走（Random Walk），从而产生meta-path的实例。例如，我们从一个作者出发，随机选择其邻居，得到文章，再继续随机选，从而得到一条路径。每一条meta-path就可以看作一句话，其中的每一个节点就是一个词，然后我们就可以借鉴Word2Vec的方法进行学习。一个典型的例子就是Metapath2Vec（Dong, et al. 2017）。当然，在具体的操作上，我们需要对随机游走的方式进行一定的限制，从而对应到异质图中的各种元路径。

上述基于结构保留的embedding的方法都较为简单，使用的主要是浅层模型，可以很好的并行实现。但也存在一定的问题。例如，如果有一个新的节点加入网络中，我们必须重新训练整个网络才可以获得其embedding。

2.Attribute-assisted HG Embedding

在异质图中，不仅仅有着复杂的节点与边类型，每一个节点对应的属性（Attributes or Features）也是多种多样的。例如，在豆瓣影评网络中，一部电影P可能有数值属性（如评分）、文本属性（如电影简介）和图片属性（如电影封面）等。而同一个网络中的其他节点可能由不同的属性构成，如一个用户可能只有数值属性（如年龄）和文本属性（如个人签名）等。每个节点蕴涵的丰富信息可以进一步提升网络效果，但也对建模提出了新挑战。Attribute-assisted embedding就是为了更好地融合节点属性而提出的。

图 3 HetGNN模型结构

一个典型的方法是HetGNN(Zhang, et al. 2019)。其通过三个层次来融合各种信息，图3(a)展示了整体结构。考虑一个目标节点a，我们想建模其embedding。首先，我们需要对每个节点的内部属性进行一个建模（Encoding Heterogeneous Contents）。对于每一个节点的各种属性，我们分别使用合适的神经网络模型进行建模。例如，数值属性使用MLP，图像使用CNN。然后通过一个双向LSTM融合一个节点的各种属性信息，得到每个节点的一个embedding，对应图3(b)。然后，我们再来融合节点的邻居信息（Aggregating Heterogeneous Neighbors）。这又分为两步。一是同一类型邻居节点聚合，文章中也是采用了一个双向LSTM进行建模，这样我们就得到了a节点各个类型邻居节点的embedding，即图3(c)。二是不同类型邻居聚合，使用一个self-attention机制将不同类型的节点进行一个聚合，最终得到融合了邻居信息的节点a的embedding，即图3(d)。通过这样的层次模型，HetGNN同时建模了节点属性与图结构。

3.Application-oriented HG Embedding

异质图embedding往往与特定的实际应用结合在一起，例如推荐系统等。在这种情况下，研究者更需要定义好适用的异质图结构以及需要包含的信息。这样才能对目标任务的效果提升有帮助。以推荐系统为例，其至少需要考虑商品与用户两类节点，这是一个天然的异质图。在这种任务导向的情境下，常常会构建端到端的模型（End-to-End），即原始数据输入-Embedding-推荐系统模型，整体一起建模。此时就不再采用无监督的训练方式，而是根据最终目标构造损失进行有监督训练（如用户是否购买商品）。更具体的模型将依据相关领域知识进行设计，本文不再介绍。

总结

本文介绍了异质图分析的基本概念与embedding方法研究现状。近年来，相关的研究十分火热，有不少典型的应用场景与常用数据集。例如本文多次提到的学术网络、电影评论网络、社交网络等等。Wang, et al.(2020)也总结了目前研究中常用的异质图数据集及其应用任务（图4）。同时也应注意到，目前的异质图分析仍然比较简单，处理的节点类型与边类型并不太多，因此仍有很多研究空间可以被探索。

图 4 常用异质图数据集

参考文献

[1] Shi, Chuan, et al. “A Survey of Heterogeneous Information Network Analysis.” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 1, 2017, pp. 17–37.

[2] Wang, Xiao, et al. “A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources.” ArXiv Preprint ArXiv:2011.14867, 2020.

[3] Chen, Hongxu, et al. “PME: Projected Metric Embedding on Heterogeneous Networks for Link Prediction.” Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 1177–1186.

[4] Dong, Yuxiao, et al. “Metapath2vec: Scalable Representation Learning for Heterogeneous Networks.” Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017, pp. 135–144.

[5] Zhang, Chuxu, et al. “Heterogeneous Graph Neural Network.” Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 793–803.

- END -