基于元图卷积的异质网络嵌入学习算法

任嘉睿 张海燕 朱梦涵 马 波

1(宁夏大学信息工程学院 银川 750021)2(宁夏财经职业技术学院 银川 750021)

随着各种社交媒体的广泛流行，在虚拟社交网络上产生了大量的交互数据，虚拟社会网络是现实社会的一种映射，从而分析和研究社会网络为解决现实社会问题提供了有效的方法.社会网络呈现出图网络的结构形式，图网络中的节点通常代表现实社会的诸多实体，边代表节点之间的各种有意义的现实关系.图神经网络[1]可将图数据转换为低维向量表示的方法，在处理高维图数据方面具有优势，且由于其在各种应用领域处理图数据显示出的高效率，引起了广泛的研究兴趣，使其在推荐系统[2-3]、实体识别[4-5]、相似搜索[6-7]等领域发挥了重要作用.

已有许多的图神经网络模型被提出，基于图谱的图神经网络模型，例如图卷积网络(graph con-volutional network, GCN)[8]、自适应的图卷积网络(adaptive graph convolutional network, AGCN)[9]，这类模型是从图信号处理的角度引入滤波器来定义图卷积，对图的傅里叶域进行卷积运算，以学习图的嵌入表示.另一种基于图上空间的图神经网络模型，如GraphSAGE(graph sample and aggregate)[10]、图注意力网络(graph attention network, GAT)[11]，通过聚集邻居节点的信息来构建图卷积，得到目标节点的聚合表示.但以上模型主要是针对同质网络，即同种类型的节点及边类型，对于包含多类型节点及多维关系的异质信息网络将不再适用.

然而真实世界中的网络数据大多都为异质网络，例如引文网络、交通网络、蛋白质网络等.由于之前的图神经网络模型无法挖掘出异质网络蕴含的丰富语义信息和结构信息，因此为了能够处理异质网络，许多工作都基于元路径对异质网络进行建模.元路径是一种实体类型和关系交替而成的序列，可以描述异质图中特有的语义信息.虽然现有的研究在处理异质网络以及社会计算的基本应用任务上取得了一定的进展，例如节点分类和聚类任务，但仍存在一些局限：

1) 大多数模型的图卷积层没有充分利用异质网络中高阶邻居的信息.相比于同质网络，在异质网络中对于要分类或聚类的同类型节点不会直接相连，因此它们之间存在更高阶的间接关系，而现有的模型很多只利用到了二阶邻居的信息，即“邻居的邻居”，如何挖掘节点之间的高阶关系来学习更有效的网络节点嵌入是非常重要的.

2) 单条元路径无法准确地反映出节点间的复杂语义.比如在引文网络中，如果想要捕获2个作者(Author)在同一会议(Conference)发表论文(Paper)的语义，同时又要满足这2篇论文中出现了相同的关键术语(Term)，即2篇论文研究的是相似的主题，这时仅靠一条元路径Author→Paper→Conference→Paper→Author显然无法满足.虽然之前的很多工作使用元路径来建模异质网络，但如何融合多条元路径上所包含的语义信息，仍是一个值得研究的问题.

对于以上的局限以及挑战，本文提出了一种基于元图卷积的异质网络嵌入学习算法MGCN(meta-graph convolutional network).元图在文献[12]和[13]中被用来计算异质网络中同类型实体之间的相似度,是一种比元路径能够包含更多语义信息的异质网络表示模式.本文提出的算法利用元图融合不同元路径上的信息，挖掘异质网络中同类型节点之间的高阶间接关系.本文工作的主要贡献有3个方面：

1) 引入元图的概念，提出基于元图的异构邻接矩阵计算方法，用以融合多条元路径上的不同语义信息，挖掘节点间的高阶间接关系，保留异质网络中的复杂语义信息.

2) 提出基于元图卷积的异质网络嵌入学习算法MGCN，在不影响模型性能的情况下，相比于基于空间卷积的图神经网络基线模型显著缩短了训练时间.

3) 分别在DBLP,IMDB数据集上进行了大量的实验，结果说明本文提出的MGCN在多个指标上优于基线模型.

1 相关工作

目前已有许多研究工作致力于借用元路径对异质网络进行建模.Sun等人[14]在2011年提出元路径的概念用以处理异质网络，他们提出的PathSim算法，通过计算2个节点间的元路径实例的数量关系来衡量节点之间的相似性，可以捕获对象间的相似性的细微之处.之后在2012年提出的PathSelClus算法[15]，基于用户的引导对元路径进行选择，进而对网络中的对象进行聚类，具体实现方法是首先为每个聚类提供一个种子节点，算法学习元路径的权值，根据权值进一步产生社区.

针对PathSim没有探索异质网络结构中的相似性以及没有生成顶点的嵌入向量这2个问题, Shang等人[16]提出了ESim算法，结合给定的元路径和网络结构来学习顶点嵌入向量，以更好地捕捉节点间的相似度.

Wang等人[17]借助注意力机制，提出了一种基于层次注意的异质图注意力网络(heterogeneous graph attention network, HAN)，包括节点级和语义级的注意力机制.节点级的注意力目的是为了挖掘基于元路径的邻居对该目标节点的重要性，而语义级的注意力则能够挖掘不同元路径对目标节点的重要性.然后，该模型通过分层聚合基于元路径的邻居的特征来生成节点嵌入，用于下游任务.

但HAN在聚合基于元路径的邻居信息过程中，只考虑了由元路径连接的头尾2个节点，抛弃了元路径上中间节点的信息.针对这个限制，Fu等人[18]提出了一种基于元路径的聚合图神经网络(meta-graph aggregated graph neural network, MAGNN).具体来说，MAGNN使用了3个主要组件，其中节点内容转换用以封装输入节点的属性，元路径内聚合用来合并元路径上的中间语义节点，最后元路径间聚合组件合并来自多条元路径的信息.但由于需要为每个目标节点计算多头注意力，以及在模型训练过程中需要计算大量的元路径，因此HAN以及MAGNN这2个模型需要很大的训练时间以及资源.为了避免选择大量的元路径，Zhao等人[19]提出了一种基于元路径的高阶异质图卷积网络(higher-order heterogeneous graph convolutional network, HOHGCN),他们设计了一种基于高阶元路径的邻接矩阵计算方法,在消息传递的每一步，线性地聚合来自高阶元路径邻居的信息.但该模型对于具有多种节点和边类型的异质图，必须使用较大的嵌入维数来编码来自各种高阶元路径的信息，会导致大量的矩阵运算，从而影响计算效率.

这些基于图神经网络的方法已经在学习异质网络嵌入表示方面取得了一定的进展，但对于挖掘节点间高阶的间接关系以及对多条元路径的融合方案上，仍有改进的空间.

2 概念定义

本节介绍相关概念及定义，本文使用的符号如表1所示：

Table 1 Notation Explanation Table表1 符号对照表

定义1.异质网络[20].异质网络被定义为有向图G=(V,E,φ,φ,A,R)，其中V代表节点集，E代表边集.对于每个节点v∈V和边e∈E，都有其到各自对象类型的映射函数φ(v)：V→A和φ(e)：E→R，其中A和R分别表示节点类型和关系类型，且|A|+|R|>2.

图1(a)是一个在DBLP引文网络中异质网络的例子，该异质网络拥有4个节点类型，即作者(Author)、论文(Paper)、会议(Conference)和论文中出现的关键术语(Term)，以及3个关系类型，即作者撰写论文(Author→Paper)、论文发表在会议(Paper→Conference)和论文中包含某个关键术语(Paper→Term).由此可见，异质网络不仅包括多种类型的对象，还提供了丰富的高级语义.

Fig. 1 An example of related concepts in a heterogeneous network图1 异质网络中相关概念的示例

定义3.元图[13].一个元图S被定义为一个有向无环图，只有一个源节点(入度为0)和一个目标节点(出度为0).具体地，S=(Vs,Es)，其中Vs为节点的集合，Es为边的集合.对于每个节点v∈Vs，都有φ(v)∈A.同理，对于每条边e∈Es，都有φ(e)∈R.

CP=CA1A2⊗CA2A3⊗…⊗CAl-1Al，

(1)

3 基于元图卷积的异质网络嵌入学习算法

由于GCN具有很强的聚合图中邻居节点信息的能力，本文基于GCN设计了元图卷积算法模型MGCN.本节对提出的MGCN算法框架进行介绍，并详细描述基于元图的异构邻接矩阵的计算方法，以及MGCN的图卷积网络层的学习节点嵌入表示的过程.

3.1 算法框架描述

为了对异质网络中多条元路径上的语义信息进行有效融合，本文提出的基于元图卷积的异质网络嵌入学习算法MGCN，能够保存比单条元路径更复杂的语义信息.

在以往学习异质网络中的语义信息和结构信息时，通常先将异质网络转化为同质网络，即将对称元路径的头尾节点直接进行连接，忽略元路径上的中间节点，将异质网络简化为一个新的只有同类型节点的同质网络，然后利用图神经网络模型学习节点嵌入.然而，仅使用孤立的单条元路径无法对一些特定复杂语义进行有效的描述，即割裂了多条元路径之间的潜在联系，因此，需要对多条元路径上包含的不同的语义信息进行融合，本文利用元图对多条元路径上的语义信息进行融合，该过程将整条元路径上的所有节点信息都计算在内.

该算法主要包括2个阶段：1)异构邻接矩阵的计算；2)节点嵌入表示学习.整体框架如图2所示.首先计算基于元图的异构邻接矩阵，该矩阵含有目标节点间基于元路径的高阶语义信息，并融合了不同元路径上的复杂语义，之后将归一化后的异构邻接矩阵与目标节点的属性特征矩阵输入MGCN的卷积层，MGCN使用了2层的图卷积网络，学习节点的嵌入表示，并将该嵌入表示应用于社会计算的下游任务中.

Fig. 2 The overall architecture of MGCN图2 MGCN总体框架

3.2 基于元图的异构邻接矩阵

为了更清楚地解释元图的概念，本文选取DBLP数据集中的部分数据来说明，如图3所示，S1,S2,S3表示DBLP中的3条元路径，它们都可以看作是一种特殊的元图.S4和S5表示元图，可以看到它们都是有向无环图，具体地，以元图S5来说明基于元图的异构邻接矩阵的计算问题.

Fig. 3 Meta-graph used for DBLP datasets图3 DBLP数据集元图示例

为了计算基于该元图的异构邻接矩阵，并融合这2条元路径上不同的语义信息，本文对这2条元路径未重合的子结构部分的异构邻接矩阵进行Hadamard乘积来融合不同的语义信息，之后再通过矩阵乘法得到包含元图复杂语义的异构邻接矩阵.基于元图S5的异构邻接矩阵具体计算过程如算法1所示，⊙表示矩阵的Hadamard积.此基于元图的异构邻接矩阵，不仅包含了节点间基于元路径的高阶语义信息，还融合了不同元路径之间的语义信息，在挖掘异质网络节点间的高阶关系和多条元路径语义的融合方案上提供了新的思路.

算法1.基于元图S5的异构邻接矩阵计算.

输入：不同类型节点间的邻接矩阵CAP,CPC,CPT；

输出：基于元图S5的异构邻接矩阵CS5.

① https://dblp.uni-trier.de/

② https://www.imdb.com/

③CP1P2=CP1⊙CP2;/*计算CP1P2*/

⑤ returnCS5./*返回结果*/

3.3 MGCN节点嵌入学习过程

在异质网络中，节点彼此之间的连接分布不均匀，导致部分节点拥有大量的邻居节点，部分节点的邻居节点非常稀少，进而导致邻接矩阵内部元素的差值非常巨大.所以在计算得到基于元图的异构邻接矩阵C之后，和传统的GCN类似，本文对异构邻接矩阵C进行度归一化，降低异质网络中节点邻居数量不一致的影响，具体计算方法：

(2)

(3)

其中，H(l)∈N×D表示第l层的输出，H(0)=X为节点的原始属性特征矩阵，W(l)表示特定层的可训练权重矩阵，σ(·)表示一个激活函数，本文使用函数ReLU(·)=max(0,· ).

整个正向传播过程如算法2所示.行①②表示基于输入的元图利用算法1中的计算方法，计算相应的异构邻接矩阵，行③表示选择输入到图卷积层的异构邻接矩阵Cs，行④～⑦表示计算每个节点v∈V的低维嵌入表示zv的过程.

算法2.异质网络嵌入学习算法MGCN.

输入：异质网络G=(V,E,φ,φ,A,R)，元图集合S，层数L，节点原始属性特征矩阵X；

输出：节点的低维嵌入表示{zv,∀v∈V}.

① forsinSdo/*处理元图*/

使用算法1计算基于元图s的异构邻接矩阵Cs；

② end for/*终止循环*/

③ 选择异构邻接矩阵Cs;

④ forl=1…Ldo

/*多层图卷积层计算节点嵌入向量*/

⑥ end for/*终止循环*/

⑦ returnzv←H(L),∀v∈V.

/*返回输出结果*/

4 实 验

本节详细介绍实验过程中使用的数据集、对比的基准方法与实验度量标准，同时展示实验结果并对该结果进行分析.

4.1 实验数据集

为了评估提出的MGCN的有效性，本文采用来自不同领域的2种广泛使用的异质网络数据集，即DBLP和IMDB数据集，之后针对这2个数据集本文进行节点分类与节点聚类实验，表2总结了2个数据集的相关统计信息.

Table 2 Statistics of Datasets表2 数据集统计信息

1) DBLP数据集①.DBLP是计算机领域内一个英文文献的集成网站.本文采用与文献[18]相同的DBLP数据集，该数据集是文献[21]提取的DBLP子集，整个数据集包括4个计算机研究领域(数据库、数据挖掘、人工智能和信息检索)的文献、作者以及学术会议信息.包括4 057个作者节点、14 328个论文节点、7 723个关键字节点，以及20个学术会议节点(其中每个研究领域选择5个学术会议).作者节点的属性特征为他们所发表论文关键词组成的词袋，其中在对作者节点的分类和聚类任务中，训练集、验证集以及测试集的大小分别为400(9.86%)，400(9.86%)，3257(80.28%).

2) IMDB数据集②.IMDB是一个关于电影、电影演员和电影导演的在线数据库，包括影片的演员、内容介绍、分级、评论等众多信息.本文同样使用与文献[18]相同的IMDB数据集，包括3个类型(动作电影、喜剧电影和戏剧电影)的电影、导演以及演员信息.其中包括4 278个电影节点、2 081个导演节点、5 257个演员节点.电影节点的属性特征是描述电影情节的词袋特征向量，对电影节点的分类和聚类任务中，训练集、验证集以及测试集的大小分别为400(9.86%)，400(9.86%)，3478(80.28%).

4.2 实验对比方法

为了更好地说明本文提出的算法MGCN，选择6种不同类型的图嵌入模型在节点分类和节点聚类任务比较各自的性能，包括传统的经典算法、基于图神经网络的同质网络嵌入模型和异质网络嵌入模型：

1) Node2vec[22].一个基于传统机器学习方法的同质网络嵌入模型，Node2vec是对DeepWalk[23]的拓展，引入有偏的随机游走，使所选择的随机游走序列更有指向性.本文将其应用在异质网络上，需要忽略图结构的异质性，并清除所有节点上的属性特征.

2) Metapath2vec[24].一个基于传统机器学习方法的异质网络嵌入模型，该算法基于元路径进行随机游走，使用skip-gram将节点映射为低维的嵌入向量,但元路径的选择需要用户指定.

3) GCN[8].一个同质图神经网络模型，通过谱图卷积学习节点的嵌入表示.本文中，在基于元路径的同质网络上对GCN进行实验.

4) GAT[11].一个同质图神经网络模型，使用注意力机制为不同邻居节点指定不同的权重，聚合邻居节点上的信息.类似地，本文在基于元路径的同质网络上对GAT进行实验.

5) HAN[17].一个异质图神经网络模型，同样使用注意力机制为多条元路径分配不同的权重，融合多条元路径上的信息，学习生成基于元路径的节点嵌入表示.

6) MAGNN[18].一个异质图神经网络模型，可以看作是HAN的拓展，其将元路径上的中间节点也计算在内，利用注意力机制学习得到最终的节点嵌入表示.

与文献[18]相同，对于传统的图嵌入模型，包括Node2vec和Metapath2vec，本文将窗口大小设置为5，随机游走的长度设置为100，每个节点的随机游走序列个数为40.对于基于图神经网络的模型，包括GCN,GAT,HAN,MAGNN以及本文提出的MGCN，使用相同的训练集、验证集和测试集划分方式，使用dropout率为0.5，权重衰减为0.001的Adam优化器.对于节点分类和节点聚类任务，使用一小部分有标签的节点以一种半监督的方式训练.对于GAT,HAN和MAGNN，将多头注意力的数量设置为8个.特别地，对于HAN和MAGNN，将元路径间聚合的注意力向量维数设置为128.为了便于实验的比较，本文将上述所有模型的嵌入维数都设置为64，训练轮次为100轮，并使用容忍度为30 轮的提前终止策略.

4.3 实验结果及分析

4.3.1 节点分类

本文在DBLP和IMDB数据集上进行了节点分类任务，比较不同的图嵌入模型在不同数据集上的性能.对于2个数据集，本文分别对作者节点和电影节点进行分类.具体方法是，将模型学习生成的节点嵌入表示输入到一个可以应用不同比例的数据进行训练的SVM分类器中.为了公平比较，本文只将测试集中的节点提供给SVM分类器，即DBLP为3 257个作者节点，IMDB为3 478个电影节点，因为在半监督模型的训练过程中，对训练集和验证集中的数据标签已经知晓.

每个图嵌入模型运行10次的平均Macro-F1值和Micro-F1值如表3和表4所示，在不同比例的训练数据以及不同的数据集上，MGCN的分类性能始终优于其他基线模型.与最好的基线模型相比，对于DBLP数据集，在Macro-F1值和Micro-F1值上分别提高了0.7%和0.67%，同时对于IMDB数据集，分别提高了0.32%和1.01%.说明本文所提出的算法能够对不同元路径上的复杂语义信息有效融合，且能够有效利用节点间的高阶间接关系.

Table 3 Experimental Results of Different Methods on Macro -F1 for Node Classification表3 节点分类任务中不同方法在Macro -F1值上的实验结果对比 %

Table 4 Experimental Results of Different Methods on Micro -F1 for Node Classification表4 节点分类任务中不同方法在Micro -F1值上的实验结果对比 %

其次，可以看到基于图神经网络的深度图嵌入模型要比传统的图嵌入模型Node2vec和Metapath2vec具有更好的分类效果，说明深层的模型具有更强的学习表达能力，能够生成更有效的节点嵌入.以及异质图嵌入模型HAN,MAGNN和MGCN的性能要比同质图嵌入模型GCN和GAT更好，说明异质图神经网络对图中的复杂语义信息具有更强的捕获及表达能力.

4.3.2 节点聚类

本文在DBLP和IMDB数据集上进行了节点聚类任务，比较不同的图嵌入模型在不同数据集上的性能.与分类任务中的策略类似，将测试集中的节点提供给HC层次聚类器,对每个图嵌入模型学习生成的节点嵌入表示进行聚类(DBLP中的作者节点和IMDB中的电影节点).本文采用NMI和ARI指数作为评价指标，将每个模型的节点嵌入在聚类器运行10次的平均结果记录在表5内.

Table 5 Experimental Results of Different Methods for Node Clustering表5 节点聚类任务中不同方法的实验结果对比 %

从聚类结果可以看出，本文提出的MGCN优于传统的图嵌入模型以及基于同质图神经网络的深度模型，原因是MGCN借助元图卷积融合了不同元路径上的高阶语义信息.但在DBLP数据集上略低于2种异质图神经网络模型HAN和MAGNN，是因为HAN和MAGNN利用多头注意力机制从元路径聚合邻居节点的语义信息，而本文的算法基于GCN直接对包含不同元路径语义信息的异构邻接矩阵做聚合.另外本文提出的MGCN利用GCN能够聚合邻居信息的优势，收集目标节点基于元图的高阶邻居的信息，在损失函数的收敛性能以及模型的训练时间上要明显优于其他所有的基线方法，减少了因多头注意力机制产生的计算开销，具体对比结果在4.3.3节做详细分析.

4.3.3 可视化

为了更直观地比较，本文在图4中展示了不同图嵌入模型节点嵌入的可视化结果.首先使用不同的图嵌入模型在DBLP数据集上学习作者节点的嵌入表示，之后本实验利用t-SNE方法对节点嵌入表示进行降维，将学习到的嵌入表示投影到一个二维空间中得到二维的可视化结果，为每个作者节点确定一个坐标，并根据不同的研究领域为节点确定不同的颜色.

从图4可以看出，传统的同质网络图嵌入模型Node2vec不能很好地学习节点嵌入表示，可视化结果较为分散，不能有效区分不同类别的节点.与传统模型相比，基于同质图神经网络的模型GCN和GAT，大致划分出了每个研究领域的节点，但4个区域的交界还是存在大量不同颜色节点相互混杂的情况.而与同质图神经网络模型相比，异质图神经网络模型HAN，MAGNN以及本文提出的MGCN，明显优于上述图嵌入模型，能够很好地将节点嵌入划分为4个区域，且区域彼此之间边界明显.以上的分析结果表明，MGCN能够学习到异质网络中有意义的节点嵌入表示，但与HAN和MAGNN不同，MGCN减少了因计算多头注意力而花费的训练时间.

Fig. 4 Embedding visualization of nodes on the DBLP dataset图4 DBLP数据集上的节点嵌入表示可视化

图5显示了MGCN与另外2种异质图神经网络模型HAN和MAGNN在训练过程中损失函数值收敛性能的具体对比，在100轮的训练中，可见MGCN的损失在第20轮之后就达到了一个稳定的值，MAGNN在第50轮左右下降到局部最低，在60轮左右出现一个明显的波动之后也逐渐达到稳定值，而HAN在第70轮之后才逐渐收敛.以上结果表明，本文提出的MGCN在损失函数值收敛的性能上要明显优于另外2种异质图神经网络模型HAN和MAGNN.

Fig. 5 Comparison of convergence performance of loss图5 不同方法的损失函数收敛性能对比

如图6所示，本文对比了MGCN,HAN以及MAGNN这3种异质图神经网络模型每轮次的平均训练时间.在100轮的训练中，可以看到MGCN每轮次的平均训练时间要明显少于其他2种基线模型，为3.39 s，其次是HAN，每轮次的平均训练时间为13.04 s，训练时间最长的是MAGNN，每轮次为23.64 s.在3个模型的训练过程中，采用了相同的提前终止策略，进而MGCN能够在损失函数收敛之后就可停止训练保存模型.以上结果表明在模型的训练时间上，本文提出的MGCN具有显著的优势.

Fig. 6 Comparison of average training time per epoch图6 不同方法每轮平均训练时间对比

5 总 结

本文提出了一种基于元图卷积的异质网络嵌入学习算法MGCN，设计了基于元图的异构邻接矩阵计算方法，用以融合多条元路径上的不同语义信息，挖掘节点间的高阶间接关系，以解决单条元路径无法对异质网络中的特定复杂语义进行描述的困难.在实验中，MGCN在2个公开的真实异质网络数据集的节点分类等任务上取得了更好的性能以及更少的模型训练时间.未来的研究工作计划将该模型应用到具体的社区发现任务中，设计以节点聚类为目标导向的社区发现算法.