DyHNE-Dynamic Heterogeneous Information Network Embedding with Meta-path based Proximity

摘要

异构信息网络(HIN)嵌入的目的是学习节点的低维表示，同时保持HIN中的结构和语义。现有的方法主要集中在静态网络上，而一个真正的HIN通常会随着时间的推移而增加(删除)多种类型的节点和边。由于一个微小的变化都会影响到整个结构和语义，传统的HIN嵌入方法需要重新训练才能得到更新的嵌入，这既耗时又不现实。本文研究了动态HIN嵌入问题，提出了一种基于元路径邻近性的动态HIN嵌入模型(DyHNE)。具体来说，我们引入了基于元路径的一阶和二阶近似来保持HINs的结构和语义。随着HIN随时间的发展，我们自然地捕捉随着元路径增广邻接矩阵的扰动而发生的变化。然后，我们通过求解广义特征值问题来有效地学习节点嵌入，并利用特征值扰动在无需重新训练的情况下高效地推导出更新的嵌入。实验表明，DyHNE在有效性和效率方面超越了最先进的技术。
关键词：动态异构信息网络，网络嵌入，社会网络分析

1 引言

(HIN)揭示了网络(图)数据的分析，网络(图)数据由各种类型的边[1]连接的多种类型的节点组成。例如，DBLP网络有四种类型的节点:Author (A)， Paper §， Conference ©和Term (T);以及多种类型的关系:作者与论文的写作关系、论文与会议的出版/出版关系等。此外，在HINs[2]中，描述节点之间复合关系的元路径被广泛用于利用丰富的语义。在DBLP中，meta-path APA表示合著关系，APCPA表示两位作者在同一个会议上发表论文。因此，HIN包含着复杂的结构和语义，研究HIN对于实际应用具有重要意义。
近年来，HIN嵌入作为一种很有前景的HIN分析方法引起了人们的广泛关注。它的目的是在保持HIN结构和语义信息的同时学习节点的低维表示，从而使各种下游应用，如节点分类[5]和链路预测[6]，[7]，都能受益于HIN的嵌入。提出了几种HIN嵌入方法。例如，基于随机漫步的方法[8]、[9]，基于分解的方法[10]、[11]、[12]，基于深度神经网络的方法[7]、[13]、[14]以及一些特定任务的方法[15]、[16]。然而，所有这些方法都是为静态HINs设计的，也就是说，结构和语义不会随着时间而改变。在现实中，HIN通常随着各种类型的节点和边的演化，例如新添加(删除)的节点或边，表现出高度的动态性。此外，动态HIN中节点和边的变化可能因类型而异。仍然以DBLP为例，一个导师与不同的学生就不同的论文进行合作，从而导致合著者关系和论文的不断发展。此外，大量的新论文被添加到网络中，而每年的会议数量几乎没有变化。
实际上，现有的HIN嵌入方法很难有效地处理动态HIN中如此复杂的演化。即使HIN发生微小的变化，这些方法也必须在每一个时间步骤中重复训练，非常耗时，不能满足实时处理的需求。虽然提出了一些处理动态网络[17]，[18]，[19]的方法，但它们没有考虑网络的异质性，在很大程度上忽略了HINs中的各种语义关系。直接使用这些方法进行动态HINs将不可避免地失去一些结构和语义，降低下游任务的性能。因此，在真实的HIN分析场景中，需要一种有效、高效的动态HIN嵌入方法。
基本上，动态HIN嵌入需要仔细考虑两个基本问题。一个是如何有效地保留动态HIN中的结构和语义。由于网络结构和语义关系是HINs中最重要和最直接的两个信息，它们在本质上保证了学习嵌入的有效性。随着HIN的演进，新增加一个节点，以该节点为中心的局部结构会发生变化，这种变化会通过不同的元路径逐渐传播到所有节点，从而导致全局结构的变化。此外，新节点不仅会与邻域建立直接联系，还会通过各种元路径与其他节点建立复杂关系，这必然会影响HINs中的语义关系。因此，结构和语义都会随动态HIN的演变而改变。对于有效的动态HIN嵌入方法来说，对学习嵌入中的变化进行建模和编码(高阶)结构和语义是非常关键的，同时也是一个挑战。

另一个问题是，当HIN随着时间的推移而发展时，如何在不对整个HIN进行再训练的情况下有效地更新节点嵌入。对于每个时间步骤，重新训练HIN嵌入方法是得到最优嵌入的最直接的方法。但显然，这种策略非常耗时，特别是在网络结构变化很小的情况下。在大数据时代，再训练方式变得不现实。这些问题促使我们寻求一种有效的方法来保持动态HIN嵌入的结构和语义。

在本文中，我们提出了基于元路径邻近性的动态异构信息网络嵌入模型(DyHNE)，以有效地学习节点嵌入。受摄动理论[20]的启发，我们通过求解广义特征值问题来学习节点嵌入，并利用特征值摄动对HIN的演化进行建模。沿着这条路线，我们首先采用元路径增广邻接矩阵对HIN的类型进行建模，并建立一个基本的静态HIN嵌入模型(即StHNE)，以保留基于元路径的一阶和二阶邻近性。这样我们可以更好地捕捉动态HINs中的结构和语义。为了捕捉HIN的演化，我们利用多个元路径增广邻接矩阵的扰动，以自然的方式模拟HIN的结构和语义的变化。最后，我们利用特征值摄动理论来考虑这些变化，并有效地推导出节点嵌入。这样，就不需要再训练HNE来获得最佳嵌入。
我们工作的贡献总结如下:

• 本文首次研究了动态HIN的增量学习节点嵌入问题，使HIN嵌入在现实场景中更加实用。
• 我们提出了一种静态HIN嵌入模型(StHNE)，以保持HIN的结构和语义。在此基础上，提出了一种基于元路径相似性的动态HIN嵌入模型(DyHNE)，可以有效地推导出更新后的嵌入结果，该模型可应用于节点数相对于时间复杂度为线性的大规模HIN嵌入。
• 我们进行了全面的评价，以表明我们的模式在效力和效率方面大大超过了几个先进水平。

2 相关工作

在本节中，我们首先介绍了一般网络嵌入的相关方法，然后讨论了HIN嵌入的最新研究成果。最后，简要介绍了动态网络嵌入方面的最新研究成果。

2.1 网络嵌入

网络嵌入的目的是在保持网络[3]，[4]，[21]原始结构信息和性质的同时，将网络投射到一个低维潜空间中。在文献中，网络嵌入可以追溯到降维技术，该技术通常通过对网络[22]，[23]进行分解来学习节点或边的潜在低维向量。Ahmed等人[24]提出将图表示为一个矩阵，其中矩阵元素对应于节点之间的边，然后进行矩阵分解学习图的低维表示。Isomap[22]的目标是通过近似保留数据对之间的测地线距离来寻找数据集的低维表示。这些基于分解的图嵌入方法在某些情况下取得了良好的性能。但是，由于大规模矩阵分解的计算量大，使得该算法对于大规模网络中的数据挖掘任务既不实用也不有效。

除了word2vec25外，对这个新兴的网络分析范式[17]、[18]、[26]、[27]、[28]、[29]、[30]、[31]、[32]、[33]、[34]、[35]、[36]、[37]、[38]也做了许多改进。例如[26]，[30]结合random walk和skip-gram[39]学习节点表示。这些方法通过在网络上随机行走构造节点序列，然后利用基于跳图的模型学习节点嵌入。为了保持节点之间的一阶和二阶邻近性，Tang等人提出了一种大规模信息网络嵌入模型。GraRep[28]和HOPE[40]都被设计用来模拟网络中节点之间的高阶邻近性。[32]，[36]进行矩阵分解，找到一个低秩空间来表示一个网络。提出了一些基于深度神经网络的网络嵌入模型，如基于自动编码器的[31]、[37]等。除了网络拓扑外，也有一些研究侧重于利用边信息，如[29]、[35]网络中的节点内容。近年来，图神经网络(GNN)得到了广泛的关注，一些基于GNN的模型被提出来解决各种数据挖掘任务(如分类)[41]、[42]、[43]、[44]。虽然这些方法取得了很好的性能，但它们都只能处理同构网络，不能直接应用于包含多类型节点和边的HINs嵌入。

2.2 HIN嵌入

由于网络的异构性，HIN嵌入侧重于保存网络[1]，[3]中的结构和语义信息，为异构数据分析提供了新的视角，使网络嵌入在现实世界中更加实用。与前面提到的同构网络嵌入类似，HIN嵌入方法大致可以分为四种类型。第一个是基于元路径的随机遍历[8]，[9]，[45]。Dong等人提出基于元路径在HIN上随机行走，然后将不同类型的节点嵌入到相应的潜在空间中。HIN2Vec[8]通过联合进行多个预测训练任务，进行随机游动并学习节点的潜向量。其次，一些方法将HIN分解成简单的网络，然后分别建模[10]，[11]，[16];例如，EOE[11]将复杂的学术异构网络分解为词共现网络和作者协作网络，并同时对子网络中的节点对进行表示学习。第三，还设计了一些基于神经网络的方法来嵌入HINs[7]，[13]，[14]，[46]。Wang等人使用自动编码器对异构信息进行建模，然后通过聚合多个特征表示获得最终的节点嵌入。最后，提出了一些HIN嵌入方法，用于探索HIN的独特性质(如异构结构)[47]、[48]或执行特定任务(如推荐和链接预测)[15]、[49]。在PME[15]中，Chen等人提出将不同类型的节点映射到相同的关系空间中，进行异构链路预测。以上所有方法都只关注嵌入静态HIN网络，而忽略了网络本身是随时间动态变化的

2.3 动态网络嵌入

近年来，一些研究人员开始关注动态网络嵌入，并做了一些尝试[17]，[33]，[38]，[50]，[51]，[52]。提出了在动态属性网络中学习节点嵌入的DANE[33]算法，该算法采用离线方法学习节点嵌入，并随着网络和属性的变化更新嵌入。DANE基于广义特征值问题，利用邻接矩阵捕捉结构的变化，利用属性矩阵建模属性的变化，仅考虑一阶邻近性。为了在动态网络中保持节点间的高阶邻近性，Zhu等人[17]设计了一种基于GSVD的方法DHPE，随着网络的演化来学习和更新节点嵌入。DHPE将GSVD问题转化为广义特征值问题，将动态网络的变化与基于Katz指数的矩阵相结合，以保持同质网络的高阶邻近性。在DynamicTriad[38]中，Zhou等人将网络的演化建模为一个三元闭合过程，并在不同的时间步长学习每个网络快照的节点嵌入。DynamicTriad利用三元组(即一组三个顶点)来模拟网络结构的动态变化，并模拟一个封闭三元组如何从一个开放三元组发展而来。Song等人对基于跳跃图的模型进行了扩展，提出了一个动态网络嵌入框架。最近，DHNE[53]被提出用于学习动态异构网络中的节点嵌入。DHNE基于快照子图构建全面的历史当前网络，在子图上执行随机游动，并使用动态异构跳跃图模型学习嵌入。DHNE专注于用动态异构skip-gram模式保持节点的动态特征，这种模式不能在不重新训练模型的情况下增量更新节点嵌入。

综上所述，上述方法要么是针对结构相对简单的同构网络设计的，要么是无法处理动态HIN，随着结构的变化，需要对整个HIN进行重新训练以获得新的嵌入。

4 DyHNE模型

在本节中，我们首先提出静态HIN嵌入模型(StHNE)作为保持一阶和二阶近似元路径的基本模型，该模型通过求解广义特征值问题来学习节点嵌入。然后引入特征值摄动理论推导更新的节点嵌入，使基于元路径邻近性的动态模型(DyHNE)能够有效地学习节点嵌入，同时有效地捕获节点的结构和语义。我们在图2中展示了StHNE和DyHNE的总体示意图。

4.1 基本思想

DyHNE的核心思想是构建一个有效、高效的体系结构，能够捕获动态HIN中结构和语义的变化，并高效地推导出节点嵌入。为了实现这一点，我们首先引入了基于元路径的一阶和二阶近似来保持HINs的结构和语义。

简而言之，所提出的StHNE能够在基于元路径的一阶和二阶近似的HIN中捕获结构和语义，而DyHNE能够在元路径增广邻接矩阵的扰动下实现网络嵌入的高效更新。

4.2 静态HIN嵌入

当HIN随着时间的推移而发展时，为了实现有效的更新节点嵌入，一个合适的静态HIN嵌入来捕获结构和语义信息是必须的。因此，我们提出了一个静态HIN嵌入模型(StHNE)，该模型保留了基于元路径的一阶和二阶近似。

5 结论

本文研究了动态HIN的嵌入问题，提出了一种新的动态HIN表示学习模型(DyHNE)。DyHNE基于设计的静态HIN嵌入模型(StHNE)，通过保留基于一阶和二阶近似的元路径来捕获结构和语义。随着动态HIN的发展，DyHNE结合元路径增广邻接矩阵的结构和语义变化，基于摄动理论高效地学习节点的嵌入。实验评估表明，DyHNE不仅显著优于先进技术，而且效率更高。