论文链接：https://www.ijcai.org/proceedings/2021/0203.pdf

摘要：异质信息网络嵌入，学习多类型节点的低维表示，已经被广泛应用并取得了优异的性能表现。然而，大多数已有工作关注于静态异质信息网络或学习特定快照网络中的节点嵌入，很少关注整个网络的演化过程以及捕捉相关的演化动态特性。为了通过考虑演化过程中的所有时序动态来填补获得多类型节点低维嵌入的空白，我们提出了一种新的时序HIN嵌入方法（THINE）。该方法不仅使用注意力机制和元路径来保留HIN中的结构和语义信息，而且还结合Hawkes过程来模拟时序网络演化。我们对各种真实时间中的时序HIN进行了广泛评估，实验结果表明THINE在静态和动态任务（包括节点分类、链路预测和时序链路推荐）中都实现了SOTA的性能表现。

1、Introduction

近年来，网络嵌入因其优异的性能表现已经受到了越来越多的人的关注。它将网络节点映射到一个低维向量空间，并同时保留了网络的属性特征和结构特征。许多优秀的算法，如Deepwalk、LINE等被提出，并被成功应用到各种网络相关的任务中，如节点分类、节点聚类以及链路预测等。

然而，这些方法都关注于同质网络，而现实世界中的绝大多数网络数据是异质的，其中包含了多种类型的节点和连边关系。例如一个学术网络通常由三类节点：作者（A）、论文（P）以及会议（C）；与多种类型的连边关系构成：作者与论文之间有合著、引用及撰写等关系；论文与会议之间有出版关系等。在HIN中，不同类型的节点与连边关系可以生成各种类型的嵌入表示，包含更为复杂的结构及相互关系。也就是说，越来越多的研究人员开始关注于HIN的表示学习领域，如PTE、Metapath2Vec以及MAGNN等。

尽管如此，目前大多数工作都是针对静态HIN提出的，而现实中的HIN是随时间演化的。如学术网络中作者可能在不同年份发表不同的论文，业务等级根据用户在Yelp中的评论随时间变化而变化。因此简单地将时序HIN视为静态不变的，将会无法准确捕捉HIN变化时的结构和语义特征。

因此对于时序HIN的了解与日俱增。然而它却面临两个严峻的挑战：首先，如何有效的保留时序HIN中的结构和语义动态特征？动力学描述了HIN在其演化过程中节点和边的所有变化情况，包括节点的添加、边的删除等。因此准确捕捉动态特性对于研究时序HIN至关重要。而像DHNE等之前的大多数工作，通过简单的将时间划分为几个时期来使用快照对时序HIN进行建模，这会失去快照内的动态特性。

另一个挑战是如何捕捉异质节点之间的时序影响？不同于同质网络，HIN包含了多种类型的节点和边，因此它包含了更复杂的网络结构和更丰富的语义信息。例如在学术网络中，我们通常会考虑来自相同类型节点的时序影响（如作者-作者，或论文-论文）。此外，在HIN中，我们还应考虑来自不同类型节点的时序效应（如作者-论文）。但由于难以模拟异质节点之间的影响，以前的大多数工作如HDGAN、DyHNE仅考虑来自相同类型节点的时序影响。

为此我们提出了THINE，一种新颖的时序异质网络嵌入模型，用于捕捉所有类型节点之间的动态特征。我们首先定义各种元路径来捕捉HIN的语义和结构，再对于特定的下游任务，生成与任务相关的候选元路径集。通过使用Hawkes过程对节点之间的时序影响进行建模，我们获得了每个节点的低维嵌入。此外，还应用了两个级别的注意力机制来区分各个方面的权重。一种针对不同类型的元路径，一种针对邻居节点的距离。在各种真实世界数据集上的实验结果表明，与几种SOTA方法相比，我们的THINE在静态和动态任务中表现更好。

本文中我们的主要工作总结如下：

1、我们在时序异质信息网络嵌入问题中考虑了网络的演化动态特性；

2、我们提出了新的时序异质信息网络嵌入模型，该模型使用元路径来捕捉HIN中的结构信息和语义信息，并通过Hawkes过程来建模了网络的演化动态特性，同时应用了两个注意力层来分别捕捉不同的结构特征和语义特征。

3、进行了实验，结果表明在三个真实数据集上，THINE表现更好。

2、Preliminaries

一个HIN的演化可以视为在不同时间步上，节点或边的添加或删除。我们通常对时序HIN的定义如下：

定义1（时序HIN）：一个时序HIN被定义为，其中V为节点集，E为边集，T表示时间戳。此外有两个映射函数，，其中A和R分别表示节点类型集合和边类型集合。对于任意HIN，满足。

特别的，边表示节点与节点在时间步 t 建立连边关系。值得注意的是，两个节点可能在不同时间建立多个关系。例如会议（C）可能会发表同一作者（A）的多篇论文，因此学术网络中A和C之间可能存在大量关系。

定义2（节点对的影响）：节点对的影响表示两个节点对建立它们之间连边关系的贡献。给定一个节点对，其中，V为节点集，两节点的影响为，则：

        (1)

其中分别表示节点的嵌入表示。

定义3（元路径）：给定一个时序HIN，，元路径M是一个定义如下的路径：

其中，A和R分别表示节点的类型和边的类型。显然，一个元路径被描述为一个类型为的复杂关系。特别的，满足元路径M的节点序列是元路径M的一个路径实例m。

定义4（候选元路径集）：一个时序边的候选元路径集S(t)是一个包含了所有涉及源节点，并且在时间 t 之前生成的元路径实例的集合。请注意，在时间 t 之前形成的路径实例，意味着它包含的所有时序边都在时间 t 之前生成。

在本文中，我们的目标是在考虑时间动态的情况下获得多类型节点嵌入。 形式上，我们将问题定义如下：

问题：时序HIN嵌入：给定一个时序HIN，目标是学习一个映射函数，其中 d<<|V|，且 d 表示嵌入维度。函数 f 不仅要捕捉到网络的演化时序动态特征，还需要考虑所有类型的节点间的相互影响。

3、The Propsed Model

3.1 Model Overview

在本节中，我们将解释我们提出的模型 THINE 的细节，它可以结合时间动态的影响来捕捉 HIN 的结构和语义。如图 1 所示，THINE 通过基于元路径的随机游走获得不同类型节点之间的结构交互。然后，我们获得每个边的候选元路径集，以使用 Hawkes 过程对时序 HIN 的动态结构和语义进行建模。此外，通过区分不同关系影响的结构级和语义级注意机制进行优化，我们聚合每个节点的效果以获得多类型节点嵌入。

3.2 THINE Model

使用元路径捕获语义。THINE 首先使用基于元路径的随机游走来提取 HIN 的信息。元路径的构建决定了我们可以捕捉到哪些语义和结构。因此，元路径的选择对于研究 HIN 至关重要。定义元路径的关键是包含尽可能多的语义。例如，对于学术网络，除了之前模型考虑的作者-论文关系的配对路径外，我们还考虑了论文-论文关系的元路径，写为APPA。总的来说，我们定义的元路径列在表 1 中。使用这些元路径，我们可以很好地保留 HIN 中的语义。此外，网络中的节点和边受节点本身和相关候选元路径集的影响。因此，基于节点对的影响，我们对候选集的影响进行建模以理解时序 HIN。

候选元路径集的建模动力学。此外，我们模拟候选元路径集的影响，以使用Hawkes过程捕获时序 HIN 的语义和结构。通常，Hawkes过程用于模拟过去事件对现在的影响。显然，事件越久，它们对当前的影响就越小。具体来说，对于THINE，我们对每一个影响都应用了Hawkes过程的关注。因此，候选元路径集的影响，以及所有相关元路径实例的影响，正式定义为：

其中 m 是一个元路径实例，表示在时间 t 之前生成的元路径实例 m。为方便起见，我们使用来表示候选元路径集、一个元路径和一个时序边的影响。因此，表示时间 t 之前的相应影响。因此我们需要对一个元路径实例 的影响进行初步建模，这可以被认为是它包含的所有边的影响。 因此，它被定义为:

其中表示节点 和之间的一条边。一条边可以由它连接的两个节点表示。因此，我们通过使用节点对和霍克斯过程的影响来模拟一个时间边缘的影响，这意味着

其中表示边缘的时间戳，描述了时间衰减效应，我们定义 。 δ 是与节点相关的可训练参数，用于调整时间衰减效果的比例。

请注意，由于计算复杂性，我们选择候选元路径集的子集进行训练。具体来说，我们选择从时间 t 最近生成的 n 个元路径实例，n 是一个超参数。很可能，对于一个元路径实例，我们选择最接近源节点的 z 个候选边进行训练，z 也是一个超参数。

使用注意力机制优化。我们展示了THINE如何计算候选元路径集的详细过程。如图1（c）所示，边的候选元路径集包含等。因此。显然和是由不同元路径APCPA和APA生成，它们将影响不同的任务。为了捕捉这种微妙的区别，我们应用了语义级注意机制。形式上，我们定义不同类型元路径的权重如下：

其中 c 是任务中定义的所有元路径的集合， 表示第 b 个元路径的权重。考虑到不同元路径的语义，我们将候选元路径集的影响重新表述为:

其中为元路径M的权重，而元路径实例m属于M。根据上述定义，。显然，由于训练边的跳数，每条边的影响应该是不同的。因此，使用结构级别的注意力机制来捕捉这种差异，我们将与跳数相关的权重表示为：

其中表示边到源节点的跳数，第跳的权重表示为。正相关于候选边 z 的数量。即一个元路径实例的影响可重新定义为：

通过元路径、两级注意力机制和霍克斯过程，我们对每个时序边的演化进行建模。通过这种方式，THINE 能够在静态和动态网络中获得具有保留语义和结构的多类型节点嵌入。基于以上公式，我们定义条件强度函数来表示在时间 t 处节点和之间生成时序边的强度：

    (9)

因为条件强度函数应该返回一个正实数，因此使用指数函数来转换，即有。取值为0到1，表示节点与之间建立连边的概率。

损失函数：因此，我们可以表示在时间 t 节点和之间建立连接的概率。特别是，考虑到时间 t 之前的条件强度函数和候选元路径集 S(t)，我们将这个概率定义为

其中表示时序 HIN 中除 之外的所有节点，所有节点对的对数似然可以表示为:

显然，的计算需要汇总全网节点的信息。我们应用负采样技术使我们的模型降低计算开销。所以损失函数可以重新表述为：

其中K为根据采样到负样本个数，正相关于，且表示节点 v 的度。为sigmoid函数，表示为。最后，我们通过Adam方法优化模型。

4、Experiments and Discussions