基于元路径的动态异质网络表示学习

刘 群，谭洪胜，张优敏，王国胤

（重庆邮电大学计算机科学与技术学院，重庆 400065）

1 引言

网络表示学习在保留网络结构和语义信息的同时，将网络中的节点表示成低维向量，以提升图挖掘后续任务的性能，如节点分类［1］、聚类［2］等.现有大多数网络表示学习方法是为静态网络设计.文献［3～5］通过特定的游走策略得到节点的节点序列，然后将其输入到自然语言模型Skip-gram［6］中，学习到节点的向量表示.LINE［7］保留了节点的一阶和二阶相似性进行概率建模，通过负采样算法提升了在大规模网络上学习节点表示的效率.算法SDNE［8］采用深度学习的方法也取得了较好的效果.随着图神经网络［9］（Graph Neural Network，GNN）的广泛应用，很多网络表示学习方法［10～13］聚合邻居节点信息和节点本身的属性信息，以提升节点向量表示质量.但是上述方法忽略了网络空间信息（拓扑结构和属性）随时间变化的特点，而只是简单地将不同时间对应的空间压缩在一起.

由于网络是随时间不断变化的，前一秒没有关系的两个节点可能会在下一秒关联，而节点之间边的建立也改变了网络的拓扑结构.因此，只考虑静态的处理方式不符合网络实际的演化规律.早期的动态同质网络表示学习结合网络演化特点，通过快照的方式获得网络在不同时间上的动态演化信息［14，15］.不同于上述基于快照的模型，CTDNE［16］设计了能捕获网络时间信息的游走序列，可以更细粒度地捕捉网络中重要信息.M2DNE［17］从微观动力学和宏观动力学两个角度很好地模拟了网络演化过程.动态同质网络表示学习未考虑网络节点和边的差异，如果将其直接应用于动态异质网络中，将不可避免地丢失语义信息.目前，典型的动态异质网络表示学习方法［18～20］，使用快照对空间（结构）进行划分，前提是要确保空间子图之间的平滑演化（节点和边微小变化）.但是，在真实网络中（例如学术网络），子图之间的节点和边存在巨大差异，基于快照的划分方式会将交互的时间戳删除，不仅导致网络的形成过程变得未知，还将导致空间子图之间的相关性变低.

为了解决现有方法的不足，本文提出了一种基于元路径的动态异质网络表示学习方法DHNR，主要贡献有以下几点.（1）为捕获更精细的语义，提出了时间加权元路径对耦合的时空结构进行划分.通过对时间进行编码，把每一条元路径对应的时间信息编码到元路径序列里.（2）不同于大部分元路径处理方法，DHNR通过设计门控循环单元（Gated Recurrent Unit Network，GRU）将每条元路径序列中的所有邻居节点属性和信息都聚合到节点序列中，而不是仅仅保留两个末端节点的结构信息，从而保证尽量完整地捕获节点的上下文语义.（3）拓展了循环神经网络（Recurrent Neural Network，RNN），设计了带注意力机制的双向门控循环单元（Bi-directional Gated Recurrent Unit Network，Bi-GRU），对不同时间的元路径序列按照重要性进行权重分配，进而完成聚合.（4）三个真实网络数据集上的实验证明了本文模型优于其他基线模型.在节点分类任务中，Micro-F1 平均提高了1.09%～3.72%，节点聚类任务的ARI值提高了3.23%～14.49%.同时在对网络动态特性捕获和消融分析实验上，也证明了本文模型的有效性.

2 相关定义

定义1 动态异质网络动态异质网络可以形式化表示为G=(V，E，T)，其中V表示节点集合，E表示连边集合，T表示边上时间集合.网络中节点和节点类型间的映射函数为φ：V→A，边和边类型间的映射函数为ψ：E→R.其中A和R 表示节点类型和边类型，动态异质网络中|A|+|R| ≥2.每条边(i，j，t) ∈E表示t时刻节点i连接到节点j.

定义2 元路径［21］一条元路径Φ 可以表示为（缩写为A1A2…Am+1）.r=r1◦r2◦… ◦rm定义了Ai和Am+1之间的复合关系，◦表示Ai和Aj之间关系的复合操作符.

图1 给出了学术网络的示意图.该网络包含t1，t2两个时间点对应的空间.在t1时，A1、A2、A3、A4四位作者在C1，C2两个会议上发表了三篇论文P1、P3、P4；在t2时，A1、A2和A3三位作者在会议C1上再次合作发表了论文P2.传统的基于元路径的方法由于忽略网络中的时间因素，容易导致一条元路径序列上的节点间存在空间（结构）耦合.例如，在元路径APCPA 引导下，捕获到这样跨时间的节点序列.该序列耦合了两个时间点下不同的结构空间，无法学习到序列里面的时间信息，同时也无法保证语义的准确性.根据网络平滑演变假设［7］可知，间隔越近，其对应的空间信息也会越相似，其中的微妙变化只有对元路径考虑时间才能精细捕获.为了解决此问题，本文提出了时间加权元路径.

图1 动态异质网络示例

3 基于元路径的动态异质网络表示

本文提出的基于元路径的动态异质网络表示学习模型框架如图2所示，该模型由三部分构成：空间划分，邻域信息聚合，时序信息集成.空间划分模块根据时间将每个节点的结构邻域划分为不同时间下的时间加权元路径序列.通过GRU 模型和相对时间编码，邻域信息融合模块能够尽量保留网络的完整语义和时间信息.最后时序信息集成模块使用带注意力机制的Bi-GRU模型进行过滤筛选.

图2 模型框架示意图

3.1 空间划分

DHNR 采用时间加权元路径为节点采样邻居序列.图3 说明了将网络通过时间加权元路径划分后，获得不同时间值下多条时间加权元路径序列的过程.例如，给定一个节点类型为A1=φ(n0)的节点，在时间加权元路径的引导下，首先采样在t1时与节点n0建立r1类型边的邻居节点n1，然后采样在t1时与节点n1建立r2类型边的邻居节点n2，如此重复，直至采样与nm在时间t1建立rm类型边的邻居节点nm+1.最后获得节点n0在时间属性值为t1的一条时间加权元路径序列.通过设置不同的时间加权元路径的时间值，可以将网络耦合的空间进行有效划分.

图3 空间划分过程

3.2 邻域信息聚合

为了捕获节点的语义信息，DHNR将每个节点的不同时间加权元路径信息分别进行聚合，如图4 所示.以节点n0为例，给定一条由时间加权元路径提取的n0的时间加权元路径序列，以及该序列上每个节点的初始特征向量xi∈Rd（d表示初始特征向量维数）.将n0的时间加权元路径序列中所有邻居信息及其自身信息聚合起来，形成一个初始的向量表示.

图4 邻域信息聚合

传播过程中的邻居信息可以视为序列输入，而GNN 不能处理序列数据，所以DHNR 模型引入了GRU构造的传播模块，将节点n0本身特征x0及其邻域信息编码成特定时间特定语义下的向量，st表示序列语义为s，时间值为t的序列.

由于节点的异质性，不同类型的节点具有不同的特征空间.对每种类型的节点设计特定类型的变换矩阵（例如节点类型为φi的变换矩阵为），以此将不同类型节点的特征投影到相同的特征空间中.转换过程如下：

其中xi和分别是节点ni的原始特征和投影特征.通过式（1）的投影操作，GRU 传播模块可以处理序列中任意类型的节点.传播模块在时间加权元路径序列上的基本递归过程如下：

3.3 时序信息集成

为了捕获更多的语义信息，同时学习的网络演化规律，DHNR 将所有序列的特征向量进行融合，形成节点的最终表示.DHNR 拓展了已有的RNN 模型，运用带注意力机制的Bi-GRU 进行深层次信息交互，为不同时间元路径序列下的节点表示向量分配不同权重，再聚合得到节点的最终表示向量.

由于邻域信息聚合的是每个时间加权元路径上的邻域节点信息，考虑到节点的演化规律需要结合节点在不同时空结构下的语义特征信息，DHNR 使用Bi-GRU 来交互不同时间下的特征信息，以此来模拟网络的演化.其公式为：

其中{o1，o2，…，og}是Bi-GRU 的状态向量序列集合，g为节点采样的序列数.传统方法直接拼接这些状态向量作为节点的最终向量表示，这种处理方式无法关注到重要特征.本文模型引用注意力机制对特征向量进行权重设计，注意力权重αi的计算公式如下：

αi越高，oi则越重要.LeakyReLU为激活函数，为注意力参数，则节点n0的所有状态特征聚合得到的节点最终向量表示为：

u0∈Rd'是节点n0的最终向量表示.在节点最终表示向量的生成过程中，采用了最小化所有标记节点的真实值和预测值的交叉熵作为损失函数：

其中Yl是节点真实标签集合.yl和表示节点标签真实值和节点标签预测值.DHNR算法如下.

3.4 复杂度分析

DHNR 模型为三个模块构成.若网络中有N个节点，则三个模块分别对应的时间复杂度分析如下：空间划分模块的时间为Nl，其中每个节点采样时间为l=w1f1+w2f2+……+wk fk，每条时间加权元路径序列节点数为fi(i=1，…，k)，k为元路径类型数，wi(i=1，…，k)表示每种类型元路径的数量，则每个节点采样的序列数为g=w1+w2+……+wk；邻域信息聚合模块的时间为N(7ld2+3ld+3gd2)，其中d为向量维度；时序信息集成模块的时间为Ng(12d2+10d+1).由于d、g、l都为很小的常数，最终DHNR的时间复杂度为O(N).

4 实验分析

为了验证DHNR 模型的性能，针对三种典型的网络挖掘任务，与不同基线模型进行了对比，同时也对DHNR模型捕获网络动态性的能力做了验证测试.

4.1 数据集

AMiner①https://www.aminer.cn/data和DBLP②https://dblp.uni-trier.de是广泛用于异质网络研究的两个数据集.DBLP-4 是从DBLP 中抽取生成的一个公开数据集.为了更充分地进行对比，本文对DBLP 数据集抽取生成了数据子集DBLP-10.表1归纳了三个数据集的统计特征.

表1 数据集描述

（1）AMiner：是一个学术网络数据集，实验抽取了从1990 年到2005 年且作者在其中五个领域研究方向有变化的子集.对于每位在这五个领域发表文章的作者，其标签与其主要研究领域相符.

（2）DBLP-4：是一个计算机科学的学术网络，包含四类节点，根据作者的研究方向将其分为四个领域.

（3）DBLP-10：该数据集包含从2008年到2013年10个研究领域发表的文章，标签是根据文章被发表的会议或者期刊所属领域进行标记.

4.2 对比算法

将DHNR算法与以下基线算法进行对比：

（1）DeepWalk［4］和GCN［13］：这是两种静态同质网络表示学习模型.前者基于随机游走生成序列，再学习节点表示，简写为DeW.后者为图卷积神经网络，在实验对比中，测试了本文使用的所有元路径，记录其中的最佳结果.

（2）Metapath2vec［3］和HAN［10］：这是两种静态异质网络的表示学习方法，前者通过元路径约束生成的序列来学习节点表示，简写为M2v.后者考虑了节点和语义级两种注意力.本文实验中，HAN 元路径的选择和本文相同.

（3）M2DNE［17］：一种动态同质网络表示学习方法，用微观动力学和宏观动力学模拟网络的演化.

（4）DHNE［18］和DyHATR［20］：都是基于快照的动态异质网络表示模型.DHNE 在历史快照和当前快照进行元路径约束游走，通过改进的Skip-gram 模型学习动态异质网络的节点表示.DyHATR 利用层次注意力来学习网络的异质性，并利用带注意力机制的RNN 学习网络演化过程.

（5）DHNRstu：本文模型DHNR 的变体，通过消除每条序列上的时间编码，进行消融实验对比.

实验过程中使用Par2vec［24］对节点的文本内容进行预训练，设置初始特征维数为128.在DHNR 模型中，节点隐藏层维度和最终表示维度都设置为128 维.使用Adam优化器对参数进行优化，学习率设置为0.000 1.为了对比公平，其他基线模型的节点表示维度均设置为128 维，Deepwalk和Metapath2vec 设置其窗口大小参数5，其他超参数设置为各自论文中指定值.所有实验都重复10 次，取平均值作为最终实验结果.对比的静态网络表示学习模型，实验中忽略了网络中的时间属性值.对比的动态同质表示学习模型，将所有节点和边视为同一类.对比的动态异质网络表示学习算法，依据其思想，构造了不同的时间快照进行学习.

4.3 节点分类

实验中，在AMiner和DBLP-4 数据集上是对作者节点类型进行分类.在DBLP-10 数据集上，是对论文节点进行分类.采用的分类算法是逻辑回归分类模型.将DHNR 学习到的节点向量表示作为逻辑回归分类器的输入.实验过程中训练集的比例设置为20%，50%，80%.

表2 给出了以Micro-F1和Macro-F1 作为评价指标的分类结果.从实验结果可以看出，DHNR 在三个数据集上的表现优于所有的对比算法，证明了DHNR 学习的节点向量表示的有效性.在DBLP-4 数据集上，由于该数据集包含了关键词等类型节点，使网络中节点类型更加丰富，节点相互之间产生的边也更多，语义信息也更丰富.因此要想获得更多更准确的语义信息，需要设计更多的元路径.实验对比中，发现M2DNE 表现性能好于本文模型，分析原因其核心思想是计算邻居节点间的相似性，较好地适用于边丰富的网络.但是当训练比例稍大一点，本文模型DHNR 表现更优.这说明了DHNR不仅能获得较丰富语义信息，还能获得高阶邻居结构信息.对比不同的动态异质网络表示学习，DHNR也展现最佳性能，说明DHNR 通过元路径保留网络语义和结构信息同时，拓展的RNN 很好地归纳聚合了网络演化信息，提升了网络表示质量.同时为了验证本文模型DHNR 不同模块的有效性，与不考虑时间编码的DHNRstu进行了对比，可以看到，考虑了每个序列时间信息的DHNR，其分类性能有一定的提升.

表2 节点多分类结果

4.4 节点聚类

实验中利用KMeans 进行节点聚类，簇数K 设置为数据集本身的标签数目.采用标准化互信息（NMI）和调整兰德系数（ARI）作为聚类评价指标.由于KMeans的性能受到初始质心的影响，进行了10次重复实验，最后实验结果取均值，表3给出了聚类的实验结果.

从表3可以看出，本文模型DHNR 在聚类任务上具有较优的性能，比其他基线算法的兰德系数（ARI）高出3.23%～14.49%.DHNR 区分了网络中的时间和空间，结合了节点在不同时间的轨迹，并在信息融合过程中考虑了路径上的中继节点，使得节点表示质量提升.

表3 节点聚类结果

4.5 可视化

本节进一步将学习到的节点特征向量投影到二维空间中，进行可视化比较.采用t-SNE 可视化了AMiner中的作者节点表示向量，根据作者节点的类型，进行不同着色.从图5可以看出，相比于其他基线模型，DHNR可以将不同类型的作者更好地映射到不同的社区，并且同一社区中节点聚集紧密，不同社区节点相距较远，只有极少数节点被嵌入到其他颜色区域，具有较高的聚类质量.

图5 AMiner网络中的节点向量表示的可视化

4.6 动态分析

为了更好地验证DHNR 模型是否能够捕获时间信息，实验中采用了节点聚类进行测试.考虑到网络演化是一个漫长的过程，所以选择有较长时间的AMiner 数据集进行实验.因为DHNR 可以通过节点的所有时间轨迹来学习向量表示，时间步长越长，网络中包含的时间信息越多，节点的交互轨迹越丰富，学习到的节点向量表示越准确.本节通过分析不同的时间步长来验证本文模型在捕获网络演化方面的有效性.

实验结果如图6 所示，当时间步长小于10 时，节点聚类性能提升较快.这说明当时间步长较短时，网络中节点的交互轨迹不足以反应节点的特征信息.随着时间步长增加，包含的时间信息更加丰富，节点聚类精度提升较快.但是当时间步长达到一定值后，网络演化趋于稳定，模型已经能够从节点的交互轨迹中学习到较完整的节点向量表示，所以聚类结果趋于稳定.说明本文模型能够真实地反映网络的动态演化特性.

图6 不同时间步的影响

4.7 不同类型元路径性能分析

由于本文模型DHNR 利用了多条不同类型的元路径来提取网络中的丰富语义信息，为验证单个不同元路径以及不同类型元路径的效果，以DBLP 数据集为例，进行了节点聚类的实验验证.

如图7所示，仅仅使用单条元路径提取的语义信息和结构信息有限，导致性能较差.而且从实验中可以发现，不同元路径提取的语义信息对节点表示向量的影响也不相同.APCPA 较APA和APTPA 具有更好的性能，分析原因是APCPA 较好地反映了作者的研究领域与他们提交的会议之间的相关性.由此可见，对不同类型的元路径进行注意力权重设置能够提升节点表示向量的质量.

图7 不同元路径影响合

4.8 元路径数量分析

为判断不同元路径数量对模型的影响，对AMiner和DBLP-10 数据集进行了节点分类的实验.图8 中Ma-F1表示Macro-F1，Mi-F1表示Micro-F1.由图8（a）可知，在Aminer 数据集上，APA 元路径数量取为4 的时候达到峰值，而APCPA元路径取值为8的时候达到峰值.其中上下两组分别代表上述两条路径在不同数量情况下的Macro-F1和Micro-F1 的取值情况.由于在Aminer 数据集中，很多作者发表论文数量是有限的，所以当路径数量为4 的时候，就能够将APA 的邻域空间准确划分，超过4 则容易导致APA 节点序列出现重复，再增加路径数量对模型几乎不产生影响.对于APCPA，尽管一定数量序列可以将A 的邻域空间准确划分，但是中继节点C的存在能够形成更多不同节点序列，因此更多的元路径数量能获取更多结构信息.如图8（b）所示，在DBLP-10 数据集上，当选取4 条PAP 路径和4 条PCP 元路径，实验效果达到峰值.其中上下两组分别代表上述两条路径在不同数量情况下的Macro-F1和Micro-F1 的取值情况.随着路径数量增多，分类效果会逐渐提升.但是到达一定值后，结果趋于稳定.同样，在DBLP-4数据集上选取了4 条APA，4 条APCPA，4 条APTPA 进行对比实验.

图8 不同元路径数量实验结果

5 结论

本文提出了一种动态异质网络表示学习方法DHNR.模型利用时间加权元路径和GRU 模型来获取网络结构和语义信息，再通过带注意力机制的双向门控循环单元来归纳网络演化规律，有效地提高了节点向量表示的质量，并在分类、聚类等下游任务中均表现出优异的性能.但是本文利用元路径提取语义信息可能导致部分信息丢失，并且忽视了网络演化的驱动力.未来将从上述两个方面开展进一步的工作.首先是考虑采用能够更好地捕捉语义的方法，其次是从网络动力学角度更好地描述网络的动态演化过程.