论文链接：https://arxiv.org/abs/2004.01024

摘要：网络表示学习的目标在于学习网络的低维向量表示，同时捕捉网络的结构信息。目前在节点分类和链路预测等网络分析中获得了巨大的成功。大多数已有的网络嵌入算法关注于如何有效学习静态同质网络。然而现实世界中的网络要复杂得多。例如网络中通常包含了多种类型的节点和连边（被称作异质信息），而且节点和连边会随时间动态改变（称为演化模式）。由于同时学习演化信息和异构信息具有挑战性，因此对动态异构网络的网络嵌入所做的工作有限。本文我们提出了一种新的动态异质网络嵌入方法，称为DyHATR算法，该方法使用了分层注意力机制学习异质信息，并结合具有时序注意力的RNN来捕捉网络的演化模式。我们在四个真实世界的数据集上对我们的方法进行了基准测试，以完成链接预测任务。 实验结果表明，DyHATR 显着优于几个最先进的基线。

1、Introduction

网络嵌入就是将网络结构编码到非线性空间中，并使用低维特征来表示网络的节点[2,6]。它一直是一项流行且关键的机器学习任务，并在许多领域都有广泛的应用，例如推荐系统 [28,34]、自然语言处理 [32,9] 和计算生物学 [22,10,24]。

现有的网络嵌入方法在链路预测和节点分类等许多下游任务上取得了显著的性能，这些方法大多集中在静态同质网络 [25,13,30]、静态异质网络 [7,39,36,3] 或 动态同质网络 [12,11,41,40,27]。 然而，现实世界中的许多网络都是动态的且异质的。网络中通常包含多种类型的节点或边[7,3]，并且网络的结构可能会随着时间的推移而演变[8,31]。 例如，客户-产品网络通常是异构的，具有多种节点类型以区分客户和产品，并且具有动态的节点和边以捕获动态的用户活动。

对于异质网络，在网络嵌入时需要同时捕捉其异质性和演化模式是一个挑战。动态网络通常被描述为静态网络快照的有序列表 [29,23,4,19,20]。 由于节点和边在不同的快照中可能不同，动态异构网络上的网络嵌入不仅需要捕获静态异构快照的结构信息，还需要学习连续快照之间的演化模式。

目前，对动态异构网络的网络嵌入所做的工作有限。MetaDynaMix [21] 集成了基于元路径的拓扑特征和潜在表示来学习异质性和时序演化性。Change2vec [1] 专注于度量快照中的变化，而不是学习每个快照的整个结构信息，它还使用基于元路径的模型来捕获异质信息。上述两种方法都关注动态网络相邻快照之间的短期进化信息，因此不足以捕捉长期进化模式。最近，Sajadmanesh 等人 [26] 使用递归神经网络模型在基于元路径的模型之上学习动态网络的长期演化模式，并提出了一种非参数广义线性模型 NP-GLM 来预测连续时序关系。尹等人 [38] 提出了一种 DHNE 方法，该方法通过基于连续快照构建全面的历史-当前网络来学习历史和当前的异质信息并模拟演化模式。然后，DHNE 执行基于元路径的随机游走和动态异质skip-gram 模型来捕获节点的表示。孔等人 [17] 介绍了一种动态异质信息网络嵌入方法，称为 HA-LSTM。它使用图卷积网络来学习异质信息网络，并采用注意力模型和长短时记忆来捕获随时间步长变化的信息。有关现有网络嵌入方法的简要总结，请参阅表 1。

为了更好地捕捉静态快照的异质性和连续快照之间的模型演化模式。本文提出了一种新的动态异构网络嵌入方法，名为 DyHATR。 具体来说，DyHATR 使用分层注意模型来学习静态异质快照和时序注意 RNN 模型来捕捉演化模式。 本文的贡献总结为：

--我们提出了一种新的动态异质网络嵌入方法，名为DyHATR，该方法可以同时捕捉网络的异质信息和演化模式。

--我们使用分层注意力方法（其中包含节点层注意力和链路层注意力）来捕捉静态网络快照的异质性。

--我们强调动态网络的演化信息，并使用时序注意力 GRU/LSTM 来模拟连续快照之间的演化模式。

--我们通过链路预测任务来对我们的方法DyHATR进行了评估。结果表明，DyHATR 在四个真实世界数据集上的性能明显优于几个最先进的基线。

2、Method

动态异质网络嵌入的主要任务是如何同时捕捉动态网络的异质信息和时序演化模式。我们提出了一种新的动态异质网络嵌入方法，该方法使用分层注意力模型来捕捉网络快照中的异质信息，并且使用时序注意力RNN模型来学习网络随时间的演化特性，我们所提出模型DyHATR的整体框架如图1所示：

动态异质网络通常被描述为所观察到的有序网络快照列表，其中表示第t个网络快照，为节点集，其类型为，为边集，其类型为。分别为节点的类型集合和边的类型集合，且。为网络快照的数量。动态网络嵌入的目标在于学习一个非线性映射函数，该函数可以将任意节点编码到一个隐层特征空间：，其中，。对于任意网络快照，所学习到的嵌入矩阵可以表示为。请注意，每个快照都被视为静态异质网络，我们将在下一节中首先解释 DyHATR 如何使用分层注意力模型来捕获快照的异质性。 然后是用于跨快照建模演化模式的时序注意 RNN。

2.1 Hierarchical Attention for Heterogeneous Information

我们引入分层注意模型，通过根据不同的边类型将异质网络快照分成几个特定类型的子网络来捕获静态快照的异质信息。分层注意模型包含两个组件：节点层注意和连边层级注意。分层注意力机制的图示如图1（a）所示。

节点层注意力：节点层注意力模型的目标在于学习各节点邻居的重要性权重，并通过聚合这些重要邻域的特征来生成新的潜在表示。对于每个静态异质网络快照，我们为每个具有相同边类型的子图采用注意力模型。对于具有连边类型为的节点对，它们在第个网络快照上的权重系数可以通过如下计算得到：

其中为节点的初始特征向量，为类型为的边的转换矩阵。为网络快照 t 中具有 r 类型连边的节点 i 的采样邻居节点。为连边类型为 r 的注意力函数的参数化权重向量；为激活函数，||为拼接操作符。然后，用计算的权重系数聚合邻居的潜在嵌入，我们可以将快照 t 中连边类型为 r 的节点 i 的最终表示为:

其中为快照 t 中连边类型为 r 的节点 i 的聚合后的嵌入向量。我们在节点层注意力模型中使用多头注意力机制来确保获得的特征稳定且有效。即，我们同时并行运行个独立的节点层注意力模型，并将这些模型所学到的特征进行拼接后作为输出的嵌入表示。因此快照 t 中具有连边类型 r 的节点 i 的多头注意力表示为：

其中为的简写形式，是第 k 个节点层注意力模型的输出，同时 k 为注意力头数。在节点层注意力模型之后，我们获得了快照网络中具有不同连边类型的节点表示集合：{}，其中为节点层注意力模型中的嵌入特征维度。

连边层注意力：节点层注意模型可以捕获单个边类型特定的信息。然而，异质网络通常包含多种类型的边。为了整合每个节点的多个特定于连边的信息，我们采用连边层注意力模型来学习不同类型连边的重要性权重，并聚合这些不同类型的特定信息以生成新的嵌入。

首先我们将特定于边的嵌入输入到非线性变换函数中，以映射到相同的特征空间，其中为激活函数，例如tanh 函数。W 和 b 分别为可学习的权重矩阵和偏置向量。这些参数在不同的边类型和不同的快照网络中共享。然后，我们通过计算映射特定边的嵌入和连边层注意力模型参数化向量 之间的相似性来度量输入的特定边的嵌入的重要性系数。将快照 t 上具有连边类型 r 的节点 i 的归一化权重系数表示为。则我们可以聚合这些特定边的嵌入，来生成第 t 个快照网络中的节点 i 的最终表示特征。

聚合了所有特定边的嵌入之后，我们可以获得不同快照网络中的节点的最终嵌入：{}，其中为连边层注意力模型的输出嵌入向量的维度。

2.2 Temporal Attentive RNN for Evolutionary Patterns

时序演化模式展示了节点和边随时间推移而出现或消失的情况。DyHATR中的分层注意力模型可以有效捕捉到静态快照网络中的异质信息。但是无法建模随时间的演化模式。最近，用于动态网络嵌入方法的循环神经网络 (RNN) 的引入取得了可喜的性能 [11,29,35,27]。在我们的论文中，我们扩展了现有的 RNN 模型，并提出了一个时序注意力 RNN 模型来捕捉连续时间戳之间更深层次的演化模式。所提出的时序注意力RNN模型主要包含两部分：循环神经网络和时序自注意力模型。时序注意力RNN模型的图示如图1（b）所示。

循环神经网络模型（RNN Model）：循环神经网络的结构使得它能够建模序列信息并学习连续快照之间的演化模式。我们提出的模型中使用了两个突出且广泛使用的 RNN 变体，即长短期记忆 (LSTM) 和门控循环单元 (GRU)。

长短期记忆（LSTM）是一种经典的循环神经网络模型，它可以捕获序列数据的长距离信息，并在动态网络学习任务中取得预期表现[15]。通过上面的分层注意力模型，我们可以获得每个快照中的节点嵌入集：{}，其中 t 为 第 t 个快照网络，i 表示节点 i 。F 为每个节点的嵌入维度。每一个LSTM单元计算输入向量，遗忘门向量，输出门向量，记忆单元向量以及状态向量。单个LSTM单元的计算公式如下：

其中；分别为输入门、遗忘门、记忆单元；和均为可训练参数。为激活函数，||表示拼接操作，为逐元素乘法运算符。

GRU为LSTM的一个简单变体[5]，被引入来捕获许多动态网络嵌入模型中的长期关联[35,23]。GRU单元比LSTM单元具有更少的参数，并且每个GRU单元仅包含两个门单元：更新门和重置门。对于每一个输入的快照网络，状态向量可以通过以下公式计算得到：

其中分别为更新门和重置门。均为可训练参数。为激活函数，||表示拼接操作。为逐元素乘法运算符。在 GRU 的迭代方程中，我们使用对从先前状态通信的潜在特征进行建模。

RNN模型的输出表示为。传统方法可能将这些状态向量进行拼接：，或取其最后一个状态作为节点 i 的最终嵌入。然而，这些传统方法可能导致信息丢失，并且不能捕捉到最重要的嵌入特征。在我们的模型中，我们在 RNN 模型的输出上使用时序级注意力模型来捕获重要的特征向量。

时序自注意力模型：不同于将所有特征向量拼接到一起作为最终嵌入向量在最后一个快照网络中进行动态网络中的链路预测任务。我们使用了一个时序级自注意力模型来进一步捕捉动态网络的演化模式。从RNN模型的输出中我们可以获得节点 i 在不同快照网络中的嵌入表示：，其中 D 为输入嵌入的维度。假设时序级注意力模型的输出表示为，其中为输出的嵌入表示维度。

在我们的模型中使用了Scaled Dot-Product注意力机制来学习不同快照网络中的每个节点嵌入。我们将节点 i 在前一时间步上的表示打包：作为输入。对应的输出表示为。首先，输入被映射到不同的特征空间，作为Query；作为Key；作为Value，其中为可训练参数。时序级注意力模型定义如下：

其中为重要性矩阵，表示屏蔽矩阵。如果为负无穷，意味着从快照 u 到 v 的注意力关闭，并且重要性矩阵中的相应元素为零，例如：。当快照网络满足，我们设置,否则为负无穷。

使用多头注意力来提高模型的有效性和鲁棒性也是可行的。因此，具有个头的节点 i 的最终嵌入向量可表示为。此时我们得到所有快照网络中节点 i 的所有嵌入表示。但是我们将使用最后一个快照网络中的节点表示：进行优化以及下游任务。

2.3 Objective Function

DyHATR的目标是同时捕获动态异质网络中的异质信息和演化模式，我们定义了利用二元交叉熵函数的目标函数，以确保最后一个快照中的节点 u 与其附近节点具有相似的嵌入特征。其损失函数如下：

其中为激活函数，如sigmoid函数，<·>为内积符号；为节点 u 在最后一个快照网络中进行固定长度随机游走所得的邻居节点集合。表示负采样的概率分布，Q为负样本个数。为为了避免过拟合而添加的惩罚项，例如 L2 正则项。为惩罚项的调控超参数。DyHATR算法的伪代码如算法1：

3、实验

3.1 数据集

3.2 实验设置

随机抽取20%的边作为验证集调参，剩余80%用于链路预测。其中再随机选择25%作为训练集，75%作为测试集。同时我们随机抽取相等数量的无链接节点对，分别作为训练集和测试集的反例。我们使用两个节点的嵌入特征的内积作为链接的特征。

训练逻辑回归模型作为分类器，使用AUROC和AUPRC作为评价矩阵。各实验重复5次，报告平均值和标准偏差值。

3.3 Baselines

静态同质网络方法：DeepWalk，GraphSAGE，GAT

静态异质网络方法：metapath2Vec

动态同质网络方法：DynamicTriad、dyngraph2Vec，DySAT

动态异质网络方法：MetaDynaMix，change2vec，DHNE，NP-GLM

3.4 实验结果