基于非递减时序随机游走的动态异质网络嵌入

在当前信息时代，现实世界中的各类数据天然以网络图模型存在，蕴藏着各种丰富且复杂的信息.通过对网络数据进行分析和预测，人们可以挖掘数据中潜在的信息并加以利用，例如分析用户画像、进行定制化内容推荐等.但由于网络数据通常以邻接矩阵表示，规模大、维度高，难以直接作为机器学习模型的输入进行分析和预测.因此，网络表示学习或网络嵌入为研究者提供了一种方法，它将高维网络映射到低维向量空间，并尽可能地保留原有网络的结构和语义信息[1].

现有的网络嵌入研究大多集中在静态网络上，包括静态同质网络嵌入和异质信息网络嵌入.在静态网络嵌入研究中，主要考虑如何对网络的拓扑结构和异质网络中语义信息进行保留，而不考虑任何时间信息.然而，现实世界中的复杂网络会随着时间的推移而快速发展.如图1所示，一个动态异质信息网络(dynamic heterogeneous information network, DHIN)包含不同类型的节点和边，并随着时间实时变化.网络的演变趋势，我们称之为时间特征，节点和边的类型或标签所隐含的语义称之为异质特征，它们携带了大量包含丰富语义的信息.此外，我们希望动态异质网络嵌入算法的时间效率能够尽可能高，以便满足实时性需求.

现有研究已经证明，忽略网络的异质特性将由于信息损失造成嵌入质量的下降[2].由于动态异质网络是在异质信息网络的基础上同时具备时间戳信息，因此网络的边通常产生在语义紧密相关但分属不同类别的节点之间.并且，具有语义相关性的异质节点之间的边也经常具有相同的时间戳.例如图1所示，时刻t1用户U1在话题T1上发表了博文B1，则在动态异质网络中的局部结构为：在具有语义关联的节点U1，B1，T1之间建立时间戳为t1的边.和动态同质网络不同的是，受异质网络语义信息的影响，语义密切相关的节点之间更有可能出现完全相同的时间戳，而非发生时间具有先后顺序的、递增的时间戳，这将为动态同质网络嵌入中基于时间顺序的随机游走带来新的挑战.

与忽略异质特征类似，如果不考虑时间特征，同样会发生重大的信息损失.以图1的社交网络为例.在t<t4时，用户U2曾经收藏过作者U1发表的博文B1，并主要关注领域1中的话题.但当时间发展到t=t6时，U2可能由于年龄增长、职业变更、近期兴趣等原因，开始对不同领域的话题表现出兴趣，在话题T2中发表博文，在时刻t7与用户U3成为好友，逐渐对领域2更感兴趣.因此在t7后的一段时间，用户U2在领域2的T2，T3话题上发表博文的概率会比在领域1的T1话题上发表博文的概率大.如果忽略时间特征，就不会注意到网络演化的这一潜在倾向.

近年来，越来越多的学者开始关注动态网络嵌入的问题，已经有一些动态同质网络嵌入的方法，如连续时间动态网络嵌入(continuous-time dynamic network embeddings, CTDNE)[3]，但对动态异质网络嵌入的研究还较少.尽管网络通过退化，能够将丰富的异质网络嵌入方法和动态同质网络嵌入方法应用于DHIN嵌入，但仍存在3个问题：1)现有针对动态同质网络嵌入的方法大多是针对快照图设计的，而非针对实时变化的动态图，不能增量式地进行网络表示学习，难以满足动态网络推断实时性的要求；2)动态同质网络嵌入和静态网络嵌入方法会忽略网络的动态信息或异质特征，造成严重的信息损失；3)动态异质网络由于其同时具备动态和异质特性，引入了局部结构具有相同时间戳的新的复杂性.因此，本文提出一种针对实时演化的动态异质网络的增量式表示学习方法，综合考虑网络的动态和异质信息，通过时序非递减的随机游走规则解决局部相同时间戳带来的挑战.

动态异质网络嵌入的一大关键问题是如何捕捉网络实时演化信息.受CTDNE[3]的启发，一个直接的想法是，我们在图上进行由时序引导的随机游走，以模拟信息随时间在网络上传递的过程.通过这种方式，可以很容易地使模型以增量的方式进行游走，游走经过的边上的时间戳递增，并依据游走序列最后一步的时间戳进行游走序列的接续扩展.

但是，将时序引导的随机游走应用在动态异质网络嵌入上仍然存在一些挑战.

1) 如何组织游走规则，以保证我们在新到来的时间戳中捕捉到网络中新的变化，并不失去游走的随机性.如果直接应用CTDNE中的游走规则，保证始终走过新时间戳或时间段上新到来的所有边，可以很好地保留演变的趋势，但在某些情况下存在以下2个问题.一个是当图的规模较大时，由于不断到来的边的增长速度很快，且允许平行边(即同一对节点间的多条边)存在，算法所需要的内存大小可能难以接受.另一个是，由于动态网络变化速率通常较快，并且部分动态网络的时间信息粒度较粗，同一时间片内会有大量新边流入.由于在同一时间片内涌入的大量连接之间也具有较强的相关性和信息的流动，算法难以捕获相同时间片内部的信息，并且当处理某些具有特殊元结构的异质图时，某些类型的节点上可能存在大部分边缘处于相同时间戳的情况，例如数据集AMiner[4]和DBIS[5]，其论文类型节点P与会议节点C、作者节点A之间，以论文发表时间作为建立连接的时间戳，因此节点P上所连边一定处于相同时间戳.为了解决这一问题，我们采用和CTDNE中基于边的随机游走不同的方式：基于节点进行随机游走，由于网络中节点数通常远小于边数，因此算法所需要的内存大小始终为节点数的指定倍数；此外，采用非递减的时序约束随机游走，允许游走在满足一定条件下选择那些仍在当前时间片中的边.

2) 如何同时保留时间特征和异质特征.如果我们将时间约束和类型约束直接结合在随机游走上，序列的长度会因为更严格的限制而变短.因此我们必须在它们之间进行折中，允许在满足时间约束的前提下适当放宽对类型的约束.

3) 对于动态图的时间信息，我们利用的是图流中的时间戳，而不是具体时间下的网络快照，因此，节点、边和时间戳的数量都会随着时间增长.当我们训练模型时，事先并不知道下一个时间戳会发生什么，所以一些基于预知整个过程中所有节点和时间的深度学习方法不适合这样的问题.因此，我们提出了一种基于增量随机游走的新方法.

本文的主要贡献包括以下3个方面:

1) 提出了一种基于随机游走的增量算法框架TNDE(temporally non-decreasing dynamic hetero-geneous network embedding)来处理实时动态网络嵌入的表示学习.该算法能够随着时间的推移增量式学习，不需要预知图的结构、时间戳总数等额外信息，并且它基于节点视角来组织游走，使用有限的内存，其上界是可预测的.

2) 提出了时序非递减的方法来解决动态异质网络中随机游走的时间戳陷入问题.引入类型约束以同时捕捉网络的时间和异质特征，并设计折中策略以防止由于约束过于严格而导致的游走序列过短问题.

3) 在3个真实数据集上的实验表明，TNDE能够显著提升嵌入质量，在下游链路预测和节点分类任务上得到了2.4%～92.7%的性能提升，并在保证良好下游任务准确度的前提下，大幅缩短算法运行时间.通过比较3个特性不同的数据集的实验结果，证明TNDE在不同类型的网络中具有良好的通用性.

1 相关工作

1.1 静态网络嵌入

静态网络包括静态同质网络和静态异质网络.在静态网络嵌入问题上，学者们已经做了大量的研究工作，代表性综述包括文献[1,6-8].文献[9-10]是静态异质网络嵌入上的代表性调研综述，从背景和代表性方法到研究方向和挑战进行了全面的讨论.

对于静态同质网络嵌入，3类代表性方法包括：基于矩阵分解的方法HOPE[11]和M-NMF[12]；基于随机游走的方法DeepWalk[13]，Node2Vec[14]和NRNR[15]；基于深度神经网络的方法SDNE[16]，SDAE[17]和SiNE[18].

对于静态异质网络嵌入，有基于度量学习的模型PME[19]，可以同时保留一阶和二阶相似性；以及基于图注意力网络的方法HAN[20]和HetGNN[21].另外，部分静态异质网络嵌入方法主要考虑单一下游任务的性能.例如，文献[22]和[23]关注于节点分类，而文献[24]则是为推荐任务设计的.

静态异质网络嵌入中最经典的是基于元路径引导随机游走的方法Metapath2Vec[2].它基于Deep-Walk的思想，利用word2vec[25]对图中节点进行表示学习，并通过预定义的元路径引导随机游走，以保留异质网络中的语义信息.此外，还有许多其他基于随机游走的异质网络嵌入方法.例如，ESim[26]和HIN2Vec[27]均使用元路径引导随机游走.但是基于元路径的方法需要依赖网络的先验知识进行元路径的选取，并且元路径选取的好坏将很大程度上影响嵌入质量.JUST[28]方法不使用指定的元路径，而是对不同类型的节点进行有偏采样，使得游走中下一跳的节点类型参照历史类别进行选择，避免了基于元路径的方法对先验知识和元路径选择依赖的问题.

1.2 动态网络嵌入

动态网络中，节点和边随时间变化，根据网络动态的呈现形式，通常可以划分为快照网络和实时动态网络2种.快照是一种静态图，它存储了网络在某一时刻的结构.快照网络指的是流式网络中不同时间戳上得到的一系列快照，而实时动态网络则是带有时间戳的、不断出现新边和节点的图流.

目前动态网络嵌入上的研究大部分集中在动态同质网络上.Zhou等人[29]提出了一种基于三元闭合过程的模型DynamicTriad，以保留给定快照网络的结构信息和演化模式.Du等人[30]提出了一种启发式算法DNE，将基于Skip-Gram的网络嵌入方法扩展到动态环境中.Peng等人[31]提出了一种增量式Skip-Gram，结合现有的网络嵌入模型Node2Vec[14]中的游走方式，能够对快照间的演变信息进行良好的保留.但是上述方法主要针对快照网络进行设计，不区分某一变化发生的具体时间戳，时间粒度粗.而对于具有时间戳、细粒度的实时动态网络嵌入，Zuo等人[32]提出了一种基于Hawkes过程的方法HTNE来捕捉历史信息的影响.Lee等人[3]提出了一种基于时序随机游走的模型CTDNE，该模型采用时间戳严格递增的顺序进行随机游走.但上述针对动态同质网络的方法，仅考虑了网络的动态特征，忽略动态异质网络的异质信息会造成严重的信息损失.

目前，越来越多的学者对动态异质网络嵌入产生了兴趣，但其上的研究工作仍十分缺乏.例如，DANE[33]是一种用于动态属性网络的谱方法，它能够良好保留网络的属性标签和动态特性，但它假设在训练过程中所有的节点都是事先已知的.DyHNE[34]通过元路径增广邻接矩阵的扰动来增量式捕捉变化，进而利用特征值扰动得到更新后的嵌入，但其对演化趋势信息的建模能力有所欠缺，对近期频繁发生的事件和过去频繁发生的事件区分能力不足.受动态同质网络嵌入方法DynamicTriad[29]的启发，Bian等人提出了一种基于元路径和三元组开/闭过程的表示学习方法Change2vec[35]，针对2个连续的静态网络快照之间的差异进行处理，能够兼顾网络的动态特性和异质特性，有良好的时间效率.但其关注的是快照网络而不是实时动态网络，并且不是所有重要的变化都会导致三元开/闭过程.此外，动态网络上还有基于深度学习的嵌入方法，但由于其往往需要预知完整图的节点集或时间戳集合而无法满足动态网络实时增量具有不可预知性的要求.

综上所述，现有网络嵌入方法主要集中在静态网络和动态同质网络上，动态异质网络嵌入方法仍较少；且现有动态方法大多针对快照网络，而非实时动态网络，难以捕获细粒度时间信息；基于谱方法或深度神经网络的方法由于其时间空间开销大，且大多需要预知全图信息，而难以适应实时动态网络的需要.因此，除现有动态异质网络嵌入方法外，能够解决实时动态异质网络嵌入问题的最接近的路线包括：可在不同时间点上反复调用的静态异质网络表示学习方法，忽略动态异质网络类型信息的动态同质网络嵌入方法和基于随机游走的动态异质网络嵌入方法.因此我们分别从上述路线中各自选取了代表性的算法作为实验对比方法.

2 实时动态异质信息网络中的基本概念

在详细描述我们的算法之前，首先给出实时动态异质信息网络嵌入问题的形式化定义和相关概念，并对动态异质网络中由于局部结构上时间戳相同带来的时间戳陷入问题进行描述.

2.1 问题定义

在本节中，我们首先利用文献[3,6,9,36]中的异质信息网络和实时动态网络的形式化定义给出定义1和定义2，并给出实时动态异质信息网络的定义.然后形式化说明实时动态异质信息网络表示学习问题，并说明表示学习问题的输入和输出.

定义1. 异质信息网络.给定一个无向图G=(V,E,L)，其中V={v1,v2,…,vn}代表节点集，E={e1,e2,…,em}代表边集，L=Lv∪Le代表节点和边的类型集合.当类型数量|L|>2，且满足节点类型数量|Lv|≥1，边类型数量|Le|≥1时，该无向图被称为异质信息网络.

定义2. 无向实时动态网络.给定一个无向图G=(V,E,Γ)，其中V和E分别代表节点和边的集合，允许两节点u,v之间建立多条直连边，Γ代表映射函数Γ：E→

+，即任意边ei=(u,v,t)∈E，对应正实数域上一个时间戳t，则该无向图被称为实时动态网络.

值得注意的是，本文关注的是具有连续时间戳的实时动态网络，而非将动态网络切割成一系列网络静态状态的快照网络.换而言之，我们关注的是有连续边输入的图流.定义3描述了本文的主要研究对象.

定义3. 实时动态异质信息网络.实时动态异质信息网络是同属于异质信息网络和实时动态网络的无向图G=(V,E,L,Γ)，允许在同一对节点之间建立多条连接.其中，V代表节点集，E代表边集，L代表节点和边的类型集合，Γ：E→

+表示将边映射到相应时间戳的函数.

由于实时动态异质信息网络是基于流的，并允许同一对节点之间存在平行边，因此快照网络和实时动态网络的嵌入方法有一些关键区别.首先，它们捕捉的是不同粒度的动态特征.快照通常不包含时间戳，并且快照间的时间间隔较长，因此把快照间的差异称为粗粒度的变化；而在实时动态网络中，每条边都携带时间戳，因此把某一时刻下网络的变化称为细粒度的变化.实时动态网络的嵌入方法通常利用具体的时间戳来捕捉细粒度的时间特征，而快照网络的模型则是处理2个连续快照之间的粗粒度变化.其次，它们对平行边问题的态度不同.快照网络嵌入通常将快照处理成简单图，不考虑平行边；而在实时动态网络嵌入中，同一对节点间在不同时刻可能产生多次连接，因此需考虑平行边，以便捕获到细粒度时间信息.

本文目标是通过捕捉异质特征和时间特征来学习实时动态异质网络中节点的低维向量表示.该模型以一个无向的、具有平行边的实时动态异质网络G=(V,E,L,Γ)作为输入.若节点数|V|=n，则最终输出一个n×d的矩阵，其中d≪n，各行d维向量即为保留了拓扑特征、异质语义信息和时间特征的节点表示.

2.2 时间戳陷入问题

由于本文算法的主要挑战之一是解决在动态异质网络上进行时序随机游走时产生的时间戳陷入问题.因此，在介绍具体解决方式前，本节将对时间戳陷入问题产生的原因及过程进行描述.

实时动态网络在演化过程中，随着事件的不断发生而在节点之间生成新的边连接，因此边建立的先后顺序将隐含信息的传递方向.例如将图2的动态网络看作邮件网络的一个表示，节点v1分别于时刻t1,t2,t3向v2,v3,v5发送工作邮件，v5通过一段时间的整理，再于时刻t4向v4发送工作邮件，即完成一次从节点v1到v4的邮件信息传递.由于在实时动态网络中，网络的动态信息是通过边上的时间戳来表示，因此针对实时动态网络的嵌入方法需要关注时间戳中动态信息的建模方式，通过时序递增引导随机游走即可建模网络中潜在的信息传递语义.

以图2为例，t1≤t2≤t3≤t4，在动态异质信息网络上应用时序递增引导随机游走，从节点v1出发得到序列{v1,v5,v4}，能够模拟信息从v1到v4的信息传递过程.但是游走到v4后，如果允许时间戳停留在游走当前的时间戳，则下一跳将返回v5.由于v4和v5没有时间戳大于t4的边，则将从v5再次走到v4，在两节点之间反复游走直到满足序列长度限制，从而造成在t4时间戳上的陷入问题.

时间戳陷入问题即可描述为：在无向实时动态网络上，由于时序非减的随机游走允许时间戳停留在当前时刻，而造成的在某一时间戳上随机游走陷入局部少数节点之间的反复游走、进而降低模型准确度的问题.

为解决这一问题，动态同质网络嵌入方法CTDNE采用时间戳严格递增的方式游走，即不允许游走停留在上一时刻，回避了时间戳陷入的前提条件.而在时间戳粒度较大的网络中，例如以年为单位的引文网络中，某年同一会议上发表的论文具有相同的时间戳.这意味着在某个阶段，它们对同一个领域感兴趣，这是重要的时间信息.规定时间戳严格递增的约束，可能会造成游走序列过短、丢失重要语义信息、训练效果差的情况.

区别于动态同质网络，动态异质信息网络由于其同时具备异质网络特性和时间信息而存在更为复杂的结构.异质网络特性将使得不同类别的节点之间的不同类别的边具有更丰富的语义信息.因此在动态异质网络嵌入过程中，我们一方面需要利用网络当中的时间戳信息来建模网络演化模式，另一方面还需要综合考虑网络中不同类别的节点和边所代表的语义信息.

而值得注意的是，在异质网络中，由于每个具有语义信息的事件往往涉及到多类别的节点，事件发生这一动作将引起多类节点之间同时产生多条边连接，从而该边上具有完全相同的时间戳，而不具有事件发生的先后顺序.例如图1中，节点B4上所连接的时间戳为t6的边表示时刻t6用户U2在话题T2上发表博文B4.如果不允许时间戳停留在上一跳的时刻，则当游走从U2走到B4后，将在B4处终止或转向时刻t8收藏了该文的用户U3(t8>t6)，无法形成“某用户某时刻在某话题上发表某博文”这一核心语义的游走序列(“用户-博文-话题”).因此，在动态异质网络中，由于大量存在局部结构上边的时间戳相同的情况，不允许停留在当前时间戳将使得在异质网络中无法产生具有紧密语义联系的游走序列，因此需设计能够解决时间戳陷入问题的时序非递减的游走策略.

3 基于时序非递减的增量嵌入模型TNDE

在本节中，我们提出了实时动态异质网络上的一种基于时序非递减随机游走的增量表示学习方法(temporally non-decreasing dynamic heterogeneous network embedding, TNDE).首先给出模型整体框架，然后分别对于模型中时序非递减的算法和增量更新策略细节进行描述.

3.1 模型框架

在介绍模型的细节之前，首先对TNDE算法进行概述.第1步采用滑动窗口模拟网络动态演化，第2步处理网络中待更新的序列，第3步根据游走策略进行增量游走，最后使用增量式Skip-Gram学习更新后的序列.图3展示了TNDE的算法框架.

受CTDNE[3]中提出的时序游走的启发，为了更好地保留动态异质网络中的时间特征，特别是在相同时间片上的具有强语义的时间信息，同时避免时间戳陷入问题，我们提出了一种基于非递减时序的随机游走方法.根据当前游走的历史情况，允许游走有一定概率在当前时间戳下继续延伸，并将时序约束与类型有偏引导随机游走相结合，综合考虑了网络的时序和异质信息.与CTDNE不同，本文中序列的游走方式从节点角度进行组织，从而将算法的空间开销从O(|E|)降至O(|V|)，并便于后续进行序列的接续游走等增量更新.游走算法的具体细节在3.2节中描述.

由于动态网络在不断演进的过程中，节点表示除受当前新增信息影响外，还受历史信息的影响，因此通过对节点的游走序列进行增量更新，再利用更新后的节点序列进行向量表示的增量式学习，能够综合当前和历史信息，并减少计算开销，加速算法运行.每当滑动窗口移动，有新的边到来时，网络中节点相关的游走序列将会出现序列段失效删除或能够进行接续游走的情况.此外，为保证最新时间上的信息得到保留，模型依据指定比例p选取一定数量的序列进行逆向的非递减时序随机游走，通过反转序列使其等价于正向游走.在得到新时刻的游走序列后，为了缩短运行时间，并保持所学到的向量表示在下游任务中的推断能力，采用增量式Skip-Gram模型[31]学习，得到最终的节点向量表示.增量更新算法细节在3.3节中进行描述.

TNDE的整体框架如算法1所示.通过滑动窗口模拟图流，在每个滑动窗口中，对当前有效节点采用incrementalUpdateW(3.3节)增量式更新相关的游走序列，并选定后续需要接续游走和逆序游走的序列位置，之后对上述序列调用temporalRW函数(3.2节)进行时序非递减的随机游走，将各有效节点增量更新后的游走序列作为增量式Skip-Gram函数incrementalSkipGram(3.3节)的输入，增量学习给定的动态异质信息网络G在当前时刻的向量表示X.

算法1. TNDE算法框架.

输入：动态异质信息网络G、类别停留概率衰减因子α、时间停留概率衰减因子β、逆序更新比例p、最终向量表示维度d；

输出：动态异质信息网络节点表示X.

① T←getSortedTime(G)； /*将图G中所有时间戳排序放入集合T中供滑动窗口运行*/

② 初始化walks为空；

③ for 第i次滑动窗口在T上滑动

④ Gi←getValidGraph(T,i)；

⑤ 初始化Wvalid为空；

⑥ for Gi中每个节点vj

⑦ walksj←incrementalUpdateW(Gi,

⑧ walksj←temporalRW(Gi,vj,walksj)；

⑨ 把walksj加入Wvalid；

X′←incrementalSkipGram(Wvalid,d)；

保存X作为输出；

3.2 融合类型约束的非递减时序随机游走

本节描述算法中核心的融合类型约束的非递减时序随机游走策略，即算法1中的temporalRW函数.

在第2节介绍时间戳陷入问题时已经提到，在现实生活或实际应用中，由于数据标记的时间戳粒度不同，仍然会有在同一时间戳上新增的边；并且在动态异质网络中，由异质节点形成的强语义局部结构上的边往往具有相同的时间戳.因此，为了更好地保留时间信息，基于时间戳约束的随机游走算法应允许游走过程中停留在当前时间片，同时需要解决允许时间停留引起的时间戳陷入问题.因此，我们提出了一种基于历史游走信息的非递减时序随机游走的策略.

非递减时序随机游走是指在给定无向实时动态网络G=(V,E,Γ)上，沿着时间戳非递减有序的方向选取边进行随机游走.所形成的节点序列{v1,v2,…,vl}满足3个条件：

1) 对于任意1≤i<l，边(vi,vi+1)∈E；

2) 对于任意1≤i<l-1，相邻边上的时间戳满足Γ(vi,vi+1)≤Γ(vi+1,vi+2)；

3) 选择Γ(vi,vi+1)=Γ(vi+1,vi+2)的概率随着在同一时间戳上连续停留次数的增加而降低.

上述时序游走策略中的第3点要求即是为了解决时间戳陷入问题而设计的.当网络中的节点没有足够多的满足时间条件的邻居，或者同一时间戳的边数远远多于更远时间戳的边数时，如果不限制时间停留概率，就很容易造成时间戳陷入问题，在局部节点之间徘徊，从而损害模型性能.

式(1)描述了节点v在时间戳ti中停留的概率，

其中，Nv为v的所有邻居集合，

为在ti时以及比ti更远的时刻上与v相连的邻居，T(Nv)代表节点v与其所有邻居相连的时间戳集合，n为序列在当前时间戳下已游走的长度，β是控制时间停留概率衰减速度的参数.β越大则游走越倾向于停留在相同的时间戳.若节点v在时间戳ti及该时刻往后没有相邻节点，则当前游走序列终止；若节点v当前所有的邻居中没有时间ti下的邻居，则停留在当前时间戳ti的概率为0，在ti后的时间戳中随机选取下一跳时间戳；若节点v具有ti下的邻居，则停留在当前时间戳的概率由衰减参数β和当前时间戳上游走长度n共同决定.若概率命中停留在当前时间，则下一跳从v在时间戳ti下的邻居中选取；若未命中，且节点v不具有时间戳ti后的邻居，则游走停止.

如图4所示，不同形状分别表示不同类别的节点.当前节点v的上一跳节点为节点u，当前游走时间戳为t1，且已n次停留在时间戳t1，则v的下一跳仍选择时间戳t1边的概率为βn，选择大于t1的时间戳的概率为1-βn.由于当前节点上的边具有多个时间戳，令Tv表示v上大于t1的所有时间戳集合，Tv={t2,t3}.下一跳选择Tv中任一时间戳的概率为(1-βn)/|Tv|.

随机游走的引导策略基于以下2个原则：一是随机游走中采样的边要满足边上时间戳非递减的条件，以保留网络的时序信息；二是要满足异质网络类型选择的要求.

在采用不同的时间和异质信息约束的情况下，二者共同作用的方式有所区别.受文献[28]启发，这里我们采用基于历史游走类型进行有偏类型选择的策略，以避免元路径约束过于严格，和时间约束相叠加后，满足条件的序列长度短的问题.并且我们还采取折中方案，优先考虑时间约束，在满足时间约束的前提下尽可能在类别约束引导下前进.

式(2)描述了在下一跳选定时间戳ti的前提下，节点v下一跳仍在类别l中停留的概率：

其中，l为节点v的类别，Nv(ti,l)为时间戳ti节点v的类别为l的邻居，Nv(ti)为在时间戳ti与v相连的所有邻居，m为序列在当前类别下已游走的长度，α为控制停留在当前节点相同域的概率衰减速度参数.α越大则游走越倾向于停留在相同的节点类别中，α越小则游走越倾向于探索其他类别的节点.本文中，为良好保留动态异质网络的类别信息，参考JUST[28]中参数设置，α=0.2.

以图4为例，当节点v已选定下一跳时间戳t2后，将在该时间戳下的邻居中进行节点类别的选择.令Lv表示该时间戳下v的邻居类别集合，且不包含v自身的类别l1.若节点v不具有类别为l1的邻居时，从Lv中任选一个类别；若v只有类别为l1的邻居时，选择类别l1；若v既有类别为l1的邻居，还有其他类型的邻居，且已停留在l1类别m次，如图4所示，则仍选取类型l1的概率为αm，选择其他类型的概率为1-αm.由于可能存在多种其他类别，因此选择其中某类别的概率为(1-αm)/|Lv|.

本节描述的时序非递减的方法，能够解决动态异质网络中随机游走的时间戳陷入问题，引入类型约束以同时捕捉网络的时间和异质特征，并设计折中策略以平衡时间和类型信息的重要性，防止由于约束过于严格而导致的游走序列过短问题.

3.3 增量游走更新与增量表示学习策略

在本节中，我们将讨论模型中使用的增量策略.正如在算法框架中所述，TNDE选定需要以增量的方式更新的游走序列，即函数incrementalUpdateW，包括需要接续游走和逆序游走的序列位置，对其应用上述时序随机游走策略进行增量游走；最后将更新后的相关游走序列作为增量Skip-Gram的输入，即函数incrementalSkipGram.

3.3.1 增量游走更新incrementalUpdateW

首先介绍增量游走的工作原理.一方面由于实时动态网络中历史信息对节点嵌入的影响需要得到保留，增量式更新游走序列能够减少历史信息的计算开销;另一方面事件的影响具有时间衰减效应，近期频繁发生的事对当前状态的影响更大，因此需要处理3个问题：如何沿着现有的路径继续游走，如何剔除现有路径中的失效数据，如何保持最新的数据始终被学到.

为了满足增量游走的要求，首先对于每个节点，算法维护了一组由节点ID标识的游走序列.在随时间增量式更新游走序列的过程中，每条由节点ID标识的序列反映了与该节点相关的变化，这些序列对影响其对应节点的网络变化敏感.

每条序列可以看作是一个随着游走不断进行而不断滑动的滑动窗口.为了在处理接续游走和无效数据丢弃时节省时间和空间，我们将一个序列划分为多个子窗口，子窗口的长度为LW.对于每个子窗口，只需要记录其中最新的边时间戳和节点类型.当子窗口中最新的时间戳无效时，整个子窗口内的序列将被丢弃.由于我们将一个子窗口作为一个操作单元，忽略了子窗口中各个具体的时间戳和节点类型等细节，因此LW越大，算法的成本越低.在本文实验中，我们使用LW=2作为默认值.

网络中发生的变化包括节点或边的产生和消失.变化影响的区域是变化部分的直接连接节点.当网络中的滑动窗口移动，新的时间片到达时，对于未受变化影响的节点，由节点ID标识的现有游走序列剔除失效数据，其他保持不变.而对于受变化影响的节点，更新相应的、以其节点ID标识的游走序列.序列的增量式更新策略主要包括以下4种，分别对应图3中标号：Ⅰ.无变化序列保留，Ⅱ.剔除现有序列中的无效节点和边，Ⅲ.延续现有游走序列，Ⅳ.在新的时间片上逆向游走生成序列.

Ⅰ. 无变化序列保留，即对于不涉及变化的序列保持不变.

Ⅱ. 剔除现有序列中的无效数据是针对网络当前所有有效节点的对应序列，以序列子窗口为单位，检查子窗口时间戳是否已过期失效.若失效，则整个子窗口丢弃.

Ⅲ. 延续游走序列同理，在需要进行延续的序列上，检查最新子窗口的时间戳和类别信息，应用3.2节中介绍的时序游走策略，在现有序列基础上进行游走.

Ⅳ. 在新的时间片上逆向游走则是为了保证能够学到更新的数据.这里提到的逆向游走就是非递减时序游走的反向过程.正向游走是从历史信息沿着时间戳非递减的方向往近期游走，而逆向游走则是从当前时刻沿着时间戳非递增的方向往历史数据游走.为了捕捉最新的演化信息，保持历史信息的效果，并且不增加过多的计算成本，我们设置参数p来控制新变化节点开始的反向游走的比例.本文根据实验经验设置p=0.2，以保证运行时间与准确度的平衡.

由于动态场景下，网络连接变化灵活，因此在不同情况下逆向游走序列的更新数目也不同.令每个节点标识的游走序列数为r，则r×p为反向游走的标准比例.式(3)所示为节点v标识的r条游走序列中需要逆序游走更新的序列数：

其中，newC为当前节点v上有效边数，oldC为节点v标识的序列中尚未完全失效的历史游走序列数.即当有效边数较少，与历史序列之和未达到序列总数上限或有效边数未达到标准比例r×p时，逆向游走生成newC条序列；当有效边数和历史序列数都较多，均能超过其对应标准比例r×p和r-r×p时，生成标准比例数目的逆向游走序列r×p条(取整)；其他情况即为有效边数较多而历史序列数较少，但其二者之和超过序列总数上限，则生成r-oldC条逆向游走，使序列总数达到上限，尽可能利用空闲空间.

3.3.2 增量表示学习incrementalSkipGram

在增量式更新游走序列后，我们将更新后的节点涉及的序列输入增量式Skip-Gram模型进行节点增量表示学习，即函数incrementalSkipGram.该模型建模网络中的变化节点带来的影响，沿用前次Skip-Gram训练后的模型参数，对变化的节点序列增量式进行表示学习，模型Loss函数为

4 实验

为了评估TNDE嵌入算法的性能，验证模型效用，在本节中，我们选取了4个代表性对比算法和TNDE进行比较，在3个真实数据集中评估它们在链路预测和节点分类这2个下游任务中的性能.所有算法均使用Python实现，运行在一台配备Intel Core i7 3.40 GHz处理器和64 GB内存的机器上.本文已公开TNDE的源代码(1)https://github.com/guaw/TNDE.

4.1 数据集

实验选取3个不同领域、不同大小且具有不同结构的数据集，表1为它们的统计信息.

DBLP.文献[37]提供了DBLP数据集的许多版本.我们选择了2014年5月的DBLP集合，使用了其提供的10个领域子集数据.该网络由“发表”和“合著”信息组成，其中节点类型包括作者(A)和会议(C)，A-C和A-A形式的边分别表示发表和合著关系，其局部结构上具有强语义信息.边上的时间戳代表建立关系的年份，时间戳数量较少且粒度粗，每一时间片内的平均边速率高.

Enron.该数据集由文献[38]提供，是从安然公司收集的电子邮件通信网络.该网络包含了公司内部115名员工之间发送的43 160封邮件，具有丰富的类型信息.节点类型是员工的职位，每条边上的时间戳表示邮件的发送时间.为便于后续描述，我们用1～9的数字代替具体文本来表示每个不同的节点类型.

TKY.该数据集文献[39]是由FourSquare提供的用户在东京的签到数据.节点类别包括用户(U)和地点(P)两类，每条边上的时间表示用户在某地签到的时间.该网络为二部图，具有丰富的细粒度时间戳信息，并具有一定数量的相同时间片上的边.

4.2 对比方法与实验设置

由于当前流行的基于图神经网络的算法时间复杂度较高，难以适应实时动态网络的嵌入要求，例如目前最先进的针对动态同质网络嵌入的DySAT[40]和针对动态异质网络嵌入的LIME[41]，其时间复杂度远高于其他基于随机游走的模型方法.因此我们选择以下4种不同的基于随机游走的对比方法进行比较，静态异质网络嵌入方法JUST、分别针对实时动态和快照的动态同质网络嵌入方法CTDNE和ISGNS、针对快照的动态异质网络嵌入方法Change2vec.上述方法的时间复杂度如表2所示，其中采样和嵌入分别表示模型在对应阶段的时间复杂度.

为保证公平性，实验过程中各方法涉及到的所有通用参数均保持一致，节点向量的维度d=128，从每个节点或(在CTDNE中)从每条边出发的游走轮数r=10，游走序列最大长度l=80.考虑到不同数据集的时间戳数量和粒度，在各方法实验过程中，对于不同数据集滑动窗口的设置为：在Enron上滑动步长为5，共滑动4次；在DBLP上滑动步长为10，共滑动5次；在TKY上滑动步长为10 000，共滑动56次.对于静态网络嵌入方法，则在滑动窗口每次移动后的位置对当前网络快照进行表示学习；对于针对快照网络的方法，则学习各相邻快照之间的差异信息.

JUST[28]是一种静态异质信息网络嵌入方法，基于类别信息能够动态调整游走偏好的类别.为了更好地捕捉节点的类别信息，游走类别初始停留概率参数α=0.2，使得游走过程中算法倾向于经过异质边探索新类型的节点，而少有比率选择同质边进而停留在当前节点类别.其余参数均选取原作默认设置.为保证实验公平性，TNDE中对应的类别停留参数α也设置为0.2.

CTDNE[3]是一种实时动态同质网络嵌入方法，其中随机游走以边为角度进行组织，按照时间戳严格递增顺序选取下一条边.每条游走序列最小长度w=5，算法中批量更新的大小与滑动窗口滑动步长保持一致，以保证CTDNE能够在有限时间戳数量的网络中生成符合要求的游走序列，且序列不过短.

ISGNS[31]是一种针对快照的动态同质网络嵌入方法，该算法游走阶段采用node2vec中的策略.超参数按照node2vec默认设置为p=1，q=1.

Change2vec[35]是一种针对快照的动态异质网络嵌入方法，使用元路径引导随机游走.为保证元路径选取的质量，各数据集上使用的元路径均基于该数据集语义进行选取，并且考虑到选取不同元路径对于模型方法效果的影响，在实验中综合考虑了多条元路径进行随机游走.具体来说，对于DBLP，我们使用元路径ACA和CAC来引导从每个节点开始的随机游走.对于TKY，使用UPU和PUP来引导.对于Enron，由于其节点类型多，寻找具有良好语义信息的长元路径比较困难，我们针对不同类型选择了一系列短元路径：1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9,9-1.这些元路径表示的是2个职位的员工之间频繁的沟通关系，并且这样选取元路径能够保留图中类别之间的整体关联性，没有将网络根据不同类别完全分割成互不相连的域.

4.3 运行时间

在实时动态网络中，对网络嵌入的需求会随时、频繁地发生，因此，为了满足动态网络嵌入的需求，算法的运行时间非常重要.在保证下游推断任务具有良好准确度的前提下，算法的时间成本越低越好.因此在本节中，我们首先对TNDE和其他4种对比方法所需的运行时间进行了评估.表3为各方法分别在3个实验数据集上的运行总时间.

从表3中可以看出，静态模型JUST和基于边视角组织游走的动态方法CTDNE在表示学习上花费的时间较多.每当需要获得嵌入的时候，静态模型都要在当前全图上运行，完全重新训练模型.因此，从实验结果也能够看出，静态方法JUST在各数据集上的时间开销均为最大，和其他动态方法的运行时间相差1～2个数量级.静态方法应用在动态网络嵌入问题上，由于其运行时间过长而难以适应动态网络嵌入在时间实时性方面的需要，因此后续推断任务准确度不再与静态方法进行对比.

而对于CTDNE，每当一定量新边到来时都会尝试多次随机游走，保留满足长度要求的序列，即尝试生成的序列数为网络中边的倍数.但实时动态网络中允许相同节点对之间具有平行边，这意味着边数可以远大于节点数.因此，CTDNE比我们基于节点视角的游走花费的时间有数量级的增长，尤其是在边密集的网络上，例如平均节点度为750.61的Enron.在该网络上CTDNE的运行时间高达静态方法JUST的19倍、动态方法的数百上千倍.

根据表3运行时间结果和下游任务准确度(4.4节)可知，与对比方法相比，Enron数据集上，TNDE方法取β<0.9的情况下所需时间均为最短，且链路预测指标AUC达到0.77～0.91，与对比方法相当，甚至有所提升；链路预测指标Micro为0.24～0.32不等，弱于Change2vec但与另2种动态同质网络嵌入方法相当.在DBLP和TKY上，TNDE取β=0用时仅次于Change2vec方法，相比另2种动态同质网络嵌入方法运算时间降低了39.06%～97.46%.虽然在DBLP和TKY上，应用Change2vec所需要的时间比TNDE短，但从4.4节展示的实验结果可以看出，它在下游任务中几乎没有表现出归纳能力，而TNDE方法在下游任务中具有出色的归纳结果.因此，综合考虑算法运行时间与下游任务准确度，TNDE在不同数据集上具有良好的通用性，综合表现最优，可以在保持归纳性能的前提下，大大缩短学习嵌入的运行时间.

4.4 下游任务准确度对比分析

在本节中，我们针对实时动态异质网络嵌入方法保留时间信息和异质信息的能力，分别通过链路预测和节点分类2个下游任务来进行评估.在分析具体实验数据之前，我们注意到2个下游任务在一定程度上具有相反的趋势，即链路预测效果出众的方法，在节点分类上的实验效果往往欠佳.其原因在于链路预测任务是通过边的2个端点向量的相似度来判断未来是否会出现这条边，两端点向量的余弦相似度越大，未来节点间产生连接的可能性就越大；节点分类任务则恰恰相反，是通过节点向量之间的距离来划分不同的类别，节点相似度越高，被归入同一类别的可能性就越大.

而值得注意的是，在异质网络中，无论是动态还是静态，经常发生关联的节点通常分别属于不同的类别.因此，当嵌入模型在链路预测任务中表现良好时，意味着2个属于不同类别的端点在嵌入空间中很接近，使得分类器很难准确地分辨它们，从而导致在节点分类任务中表现不佳，反之同理.

为模拟实时动态网络嵌入在链路预测任务中的动态变化情况，每组数据集上的实验随着滑动窗口的每次滑动进行评估.由于TKY数据集时间片数量多，窗口滑动次数多，因此我们将每滑动10次的位置作为一个时间点，从中选取了5个重要的时间点，报告该时刻网络的链路预测指标.实验使用当前时刻下网络的嵌入表示，计算节点之间的余弦相似度，使用从当前时间点到下一次评估的时间点之间的数据作为测试集正例，从网络中抽取与正例等量的负例共同组成测试集，并使用AUC来评估当前时刻链路预测结果的性能.AUC值越高，说明链路预测结果越好；AUC越接近0.5，表示链路预测效果越差，接近随机预测.实验报告了各评估时间点上的AUC，以及AUC的平均得分，结果如表4所示，报告了TNDE在β控制下的最优结果，其中在DBLP和Enron上取β=1，在TKY上取β=0.5.

根据表4数据并综合考虑算法的运行时间可以看出，在时间明显缩短的条件下，TNDE仍然可以取得良好的链路预测效果；并且，通过调节时间停留概率参数β，能够在牺牲一定时间效率的情况下取得较大的性能提升.同为处理动态异质网络嵌入的Change2vec表现最差，尽管其运行时间短，但在DBLP和TKY上几乎没有推断能力.

在TKY数据集下，TNDE方法选取β=0.5时的实验结果，其时间开销与CTDNE相当，AUC提升了2.4%，与ISGNS和Change2vec相比提升了15.2%～47.5%.并且在算法取β=0，即时间开销远低于CTDNE和ISGNS的情况下，TNDE的AUC仍能达到0.700，比ISGNS和Change2vec高3.1%～32.0%.

在DBLP数据集下，实验报告了TNDE模型取β=1时的结果.相比ISGNS，AUC降低了9.5%，但其时间效率提升了12.5%；相比CTDNE，AUC提升了30.5%，运行时间效率提升了49.7%.

在Enron数据集下，表4中报告了TNDE取β=1的情况，运行时间略有升高但能取得3.5%～18.5%的链路预测性能提升，β=0.9的情况下，运行时间略有下降，AUC仍能达到0.915，有2.5%～17.4%的提升.

本节中使用逻辑回归分类器进行节点多标签分类任务.数据集按时间戳顺序被分成2部分，前75%作为训练集，后25%作为测试集.每组实验重复5次，并分别报告Macro-F1和Micro-F1的平均分数以评估分类效果[42].分数越高，说明嵌入在节点分类任务中的性能越好.实验结果如表5所示，其中报告了TNDE在β控制下的最优结果，在DBLP，Enron和TKY上β分别取0.5，0.8和0.9.

从表5中可以看出,Change2vec方法在DBLP和TKY数据集中分类表现欠佳，但其在Enron数据集上明显高于其他算法.这是因为Change2vec算法在抽取快照间差异后，在其上进行了基于元路径引导的随机游走.由于指定元路径能够人为地干预随机游走中游走路径的选择，使得所生成的序列将指定元路径中相关联的节点聚集得比较近，而没有通过元路径关联起来的节点类型离得很远.因此，在DBLP和TKY两个具有明显局部结构、节点类别较少的网络中，元路径带来的积极影响不突出.而在Enron数据集中，节点类别较多，且节点类别与网络拓扑结构之间是弱耦合的关系，则指定元路径的游走方式能更好地协助模型生成具有良好分类能力的节点嵌入.TNDE在Enron数据集上仅次于Change2vec算法，且在另外2个数据集上都能取得最好的节点分类结果.

由于不同类别的节点数量存在差距，Macro-F1指标的差异更为明显.在DBLP数据集上，表5报告了TNDE取β=0.5下的实验结果，与各对比方法相比，Macro-F1能够提高7.9%～60.6%，且从表3可以看出，与ISGNS和CTDNE相比，算法运行时间降低92%～95.4%.在Enron中，TNDE取β=0.8，虽然Macro-F1低于Change2vec，但相比CTDNE和ISGNS两种动态同质网络方法有27.5%～50.2%的提升，且算法运行时间为3.22 s，比3种对比方法用时下降了28.4%～99.91%.在TKY数据集上，TNDE取β=0.9，Macro-F1能够提高11.4%～92.7%；考虑到算法运行时间，β=0时算法运行时间效率相比ISGNS提升了39.1%，尽管Macro-F1相比ISGNS下降了14.95%，但仍能达到0.723，且比CTDNE和Change2vec仍有38.3%～47.1%的提升.

从异质性信息的角度考虑，CTDNE和ISGNS方法均针对动态同质网络，忽略网络的异质信息，从表5的实验结果来看，这2种方法在节点分类任务上低于本文方法TNDE，本文方法能够在Macro-F1上取得7.9%～92.7%的提升，在异质性更强的Enron数据集上表现提升尤其明显，能够体现不考虑异质性的信息丢失问题.

综上所述，与其他对比方法相比，TNDE方法在大多数情况下能够取得最好的节点分类结果，能够对动态异质网络的异质信息进行良好保留，在不同类型的网络中具有很好的通用性；并且通过调节时间停留概率参数β，能在保证良好分类效果的情况下大大减少算法的运行时间.

理论分析与实验结果均显示，这2个不同的推断任务由于任务本身特性而难以同时达到最优结果，即在链接预测中表现较好的方法在节点分类中往往表现较差，反之同理.实验还表明，TNDE可以显著提升链路预测和节点分类的准确度，良好保留动态异质网络的时间和异质信息，并在保证良好链路预测和分类效果的前提下，获得运行时间效率的大幅提升.

4.5 参数分析

4.5.1 参数β影响分析

本节中，我们从算法运行时间、下游任务准确度方面评估了算法中的参数β对嵌入质量的影响.选定α=0.2，将β从0到1分别取{0，0.1，0.3，0.5，0.7，0.8，0.9，1}.图5～8分别展示了算法运行时间、链路预测AUC、节点分类Macro-F1和Micro-F1指标的变化情况.由于不同数据集所用时间差异较大，为了在同一张图中更清晰地表示算法运行时间在3个不同数据集中的变化趋势，图5分别设置了2个时间刻度，左轴为TKY，DBLP所用时间刻度，右轴为Enron所用刻度.

如图5所示，算法运行时间随着β的增大而增加.其主要原因在于，参数β决定了初始状态下，时序游走过程中选择仍在当前时刻的边的概率，以及概率的衰减速度.参数β较大则游走倾向于停留在当前时间片的边中，β较小则游走倾向于选择更远的时间点上的边.由于β的增大实际上是对严格增时序约束限制的放宽，允许游走的范围随着β而变大，进而生成的随机游走序列长度也会增长，引起算法运行时间的上升.

实验数据显示，在β<0.9时，网络表示学习时间随β的增大近似线性增长，而当β逼近1时，算法运行时间陡增.时间陡增的主要原因是，β逼近1意味着网络中每次进行随机游走时，有极大的概率选择当前时间片内的边，而难以向更远的时间游走，产生时间戳的陷入，导致游走序列长、算法运行时间长.结合图6～8的下游任务指标也能够看出，对于时间粒度细、局部结构具有较少相同时间片的数据集，例如TKY，当β=1时下游任务效果具有明显下降.

因此，对于时间粒度细、局部结构具有较少相同时间片的数据集则可将β调小，使得游走更倾向于向远方时间点探索.而对于时间片较少、相同时间戳下具有大量边的数据集，如Enron和DBLP，则可将β适当调大，以便在相同时间片内的边上进行较为充分的游走探索.同时注意，由于β逼近1时存在的运行时间陡增和算法性能下降的趋势，β可调至0.8左右，以保证算法在运行时间和嵌入质量上均具有良好表现.

4.5.2 参数α影响分析

在本节中，我们同样从算法运行时间、下游任务准确度方面评估了算法中的参数α对嵌入质量的影响.实验选定β=0.7，将α从0到1分别取{0，0.2，0.4，06，0.8，1}.图9～12分别展示了算法运行时间、链路预测AUC、节点分类Macro-F1和Micro-F1指标的变化情况.由于不同数据集所用时间差异较大，为了在同一张图中更清晰地表示算法运行时间在3个不同数据集中的变化趋势，图9分别设置了2个时间刻度，左轴为TKY,DBLP所用时间刻度，右轴为Enron所用刻度.

如图9所示，算法运行时间随着α的增大而基本持平，在节点类别较多的Enron数据集上，运行时间随α的增大而略有下降.其主要原因在于，参数α决定了初始状态下，时序游走过程中下一跳仍选择当前类别节点的概率，以及概率的衰减速度.参数α较大则游走倾向于选择仍为当前类别的节点，α较小则游走倾向于选择不同类别的节点.由于α的增大实际上是倾向于游走中选择相同类别的节点，在少类别的数据集中对游走过程允许范围的影响较小，进而对生成的随机游走序列长度影响较小，因此算法运行时间基本持平.而在Enron数据集中由于类别更多，当α增大时，倾向于在相同类别间游走，减少了跨越不同类别的游走，因此算法运行时间略有下降.

在实验设置中，链路预测任务是面向未来链接的预测，其主要考察模型嵌入对于网络动态演化模式、动态信息的建模和保留能力；而节点分类任务面向节点的类别进行划分，主要考察模型嵌入对于网络类别信息，即网络异质信息的建模和保留能力.

由图10能够看出，面向网络动态演化模式的链路预测任务对于调节类别的参数α不敏感.仅在α逼近1时，由于将游走约束在一类节点上，忽略了不同类别节点之间的关系，从而导致链路预测结果下降.

由图11，12的节点分类结果能够看出，对于类别较多、不同节点类别间关系松散的数据集Enron来说，随着α的增大，随机游走的范围将逐渐收缩到某一类别的节点，能够聚集该类别的节点信息，使得相同类别节点的向量表示彼此接近，而不同类别节点的向量表示相距较远，利于节点分类任务.对于节点类别和边类别较少的二部图TKY来说，α对于游走类别影响有限，因此算法时间和下游任务指标对α变化不敏感.对于同样节点类别较少但分布不均匀的DBLP来说，当α逼近1时，大量游走序列集中在数量较多的A类别节点上，引起分类结果的下降.

因此，对于节点类别较少的数据集，如DBLP和TKY，可将α调小，使得游走更倾向于向不同类别节点探索.而对于类别丰富的数据集，如Enron，可将α适当调大，以便捕获同类节点之间的关系.需要注意，由于α逼近1时算法性能有下降趋势，建议在0～0.8对α取值，以保证算法综合考虑类别信息，在运行时间和嵌入质量上均具有良好表现.

5 结论

在这项工作中，我们提出了一种基于时序随机游走的动态异质信息网络增量表示学习框架TNDE，该框架设计了允许时间停留在当前时间片的非递减时序随机游走策略，保留了动态异质网络嵌入强语义局部结构中的时间信息，并引入基于节点类型的有偏游走概率以保留网络异质信息.使用更新参数p来平衡最新信息和历史信息的比例，使用时间停留概率衰减因子β来平衡停留在当前时间和向更远时间探索的概率，并通过使用子窗口对游走序列进行增量式更新和使用增量Skip-Gram来进行增量式表示学习，降低算法运行成本.实验结果表明，与静态异质网络方法相比，TNDE能够显著降低算法运行时间；与其他动态嵌入方法相比，TNDE可以显著提升链路预测和节点分类的准确度，良好保留动态异质网络的时间和异质信息，并在保证良好链路预测和分类效果的前提下，获得运行时间效率的大幅提升.

作者贡献声明：郭佳雯负责论文方法构建、部分对比实验和论文写作；白淇介负责部分对比实验和部分论文修改工作；林铸天负责部分对比实验；宋春瑶和袁晓洁提供了论文方法思路指导和论文撰写指导.

[1]Cui Peng, Wang Xiao, Pei Jian, et al. A survey on network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(5): 833-852

[2]Dong Yuxiao, Chawla N V, Swami A. Metapath2Vec: Scalable representation learning for heterogeneous networks[C] //Proc of the 23rd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2017: 135-144

[3]Lee J B, Nguyen G, Rossi R A, et al. Dynamic node embeddings from edge streams[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2020. DOI:10.1109/TETCI.2020.3011432

[4]Tang Jie, Zhang Jing, Yao Limin, et al. Arnetminer: Extraction and mining of academic social networks[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 990-998

[5]Sun Yizhou, Han Jiawei, Yan Xifeng, et al. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 992-1003

[6]Chen Haochen, Perozzi B, AI-Rfou R, et al. A tutorial on network embeddings[J]. arXiv preprint, arXiv:1808.02590v1, 2018

[7]Zhang Daokun, Yin Jie, Zhu Xingquan, et al. Network representation learning: A survey[J]. IEEE Transactions on Big Data, 2020, 6(1): 3-28

[8]Hamilton W L, Ying R, Leskovec J. Representation learning on graphs: Methods and applications[J]. arXiv preprint, arXiv: 1709.05584v3, 2018

[9]Shi Chuan, Li Yitong, Zhang Jiawei, et al. A survey of heterogeneous information network analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(1): 17-37

[10]Yang C, Xiao Yuxin, Zhang Yu, et al. Heterogeneous network representation learning: Survey, benchmark, evaluation, and beyond[J]. arXiv preprint, arXiv:2004.00216, 2020

[11]Ou Mingdong, Cui Peng, Pei Jian, et al. Asymmetric transitivity preserving graph embedding[C] //Proc of the 22nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1105-1114

[12]Wang Xiao, Cui Peng, Wang Jing, et al. Community preserving network embedding[C] //Proc of the 31st AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2017: 2040-2040

[13]Perozzi B, AI-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 701-710

[14]Grover A, Leskovec J.Node2vec: Scalable feature learning for networks[C] //Proc of the 22nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2016: 855-864

[15]Ye Zhonglin, Zhao Haixing, Zhang Ke, et al. Network representation learning using the optimizations of neighboring vertices and relation model[J]. Journal of Computer Research and Development, 2019, 56(12): 2562-2577 (in Chinese)(冶忠林, 赵海兴, 张科, 等. 基于邻节点和关系模型优化的网络表示学习[J]. 计算机研究与发展, 2019, 56(12): 2562-2577)

[16]Wang Daixin, Cui Peng, Zhu Wenwu. Structural deep network embedding[C] //Proc of the 22nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, New York: ACM, 2016: 1225-1234

[17]Cao Shaosheng, Lu Wei, Xu Qiongkai.Deep neural networks for learning graph representations[C] //Proc of the 30th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2016: 1145-1152

[18]Wang Suhang, Tang Jiliang. Aggarwal C, et al. Signed network embedding in social media[C] //Proc of the 17th SIAM Int Conf on Data Mining (SDM 2017). Philadelphia, PA: SIAM, 2017: 327-335

[19]Chen Hongxu, Yin Hongzhi, Wang Weiqing, et al. PME: Projected metric embedding on heterogeneous networks for link prediction[C] //Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 1177-1186

[20]Wang Xiao, Ji Houye, Shi Chuan, et al. Heterogeneous graph attention network[C] //Proc of the World Wide Web Conf. New York: ACM, 2019: 2022-2032

[21]Zhang Chuxu, Song Dongjin, Huang Chao, et al.Heterogeneous graph neural network[C] //Proc of the ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2019: 793-803

[22]Jacob Y, Denoyer L, Gallinari P. Learning latent representations of nodes for classifying in heterogeneous social networks[J]. Alternatives to the High Cost of Litigation, 2014, 13(12): 373-382

[23]Santos L D, Piwowarski B, Denoyer L.Representation learning for classification in heterogeneous graphs with application to social networks[J]. ACM Transactions on Knowledge Discovery from Data, 2018, 12(5): 1-33

[24]Shi Chuan, Hu Binbin, Zhao W X, et al. Heterogeneous information network embedding for recommendation[J]. IEEE Transactions on Knowledge and Data Engineering. 2019, 31: 357-370

[25]Mikolov T, Chen Kai, Corrado G, et al. Efficient estimation of word representations in vector space[J]. arXiv preprint, arXiv:1301.3781v3, 2013

[26]Shang Jingbo, Qu Meng, Liu Jianlu, et al. Meta-path guided embedding for similarity search in large-scale heterogeneous information networks[J]. arXiv preprint, arXiv:1610.09769v1, 2016

[27]Fu Taoyang, Lee W C, Lei Zhen. HIN2Vec: Explore meta-paths in heterogeneous information networks for representation learning[C] //Proc of the 2017 ACM Conf on Information and Knowledge Management. New York: ACM, 2017: 1797-1806

[28]Hussein R, Yang Dingqi, Cudre-Mauroux P. Are meta-paths necessary? Revisiting heterogeneous graph embeddings[C] //Proc of the 27th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2018: 437-446

[29]Zhou Lekui, Yang Yang, Ren Xiang, et al.Dynamic network embedding by modeling triadic closure process[C]. Proc of the 32nd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2018: 571-578

[30]Du Lun, Wang Yun, Song Guojie, et al.Dynamic network embedding: An extended approach for skip-gram based network embedding[C] //Proc of the 27th Int Joint Conf on Artificial Intelligence. San Mateo, CA: Morgan Kaufmann, 2018: 2086-2092

[31]Peng Hao, Li Jianxin, Yan Hao, et al. Dynamic network embedding via incremental skip-gram with negative sampling[J]. Science China Information Sciences, 2020, 63(10): 1-19

[32]Zuo Yuan, Liu Guannan, Lin Hao, et al.Embedding temporal network via neighborhood formation[C] //Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 2857-2866

[33]Li Jundong, Dani H, Hu Xia, et al. Attributed network embedding for learning in a dynamic environment[C] //Proc of the 2017 ACM Conf on Information and Knowledge Management. New York: ACM, 2017: 387-396

[34]Wang Xiao, Lu Yuanfu, Shi Chuan, et al. Dynamic heterogeneous information network embedding with meta-path based proximity[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, PP(99). DOI:10.1109/TKDE.2020.2993870

[35]Bian Ranran, Koh Y S, Dobbie G, et al. Network embedding and change modeling in dynamic heterogeneous networks[C] //Proc of the 42nd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2019: 861-864

[36]Cai Hongyun, Zheng V W, Chang K C C. A comprehensive survey of graph embedding: Problems, techniques and applications[J]. arXiv preprint, arXiv:1709.07604v3, 2018

[37]Tang Jie. Citation network dataset[EB/OL]. [2021-05-24]. https://www.aminer.cn/citation

[38]Arne H R. Enron data[EB/OL]. [2021-05-24]. http://www.ahschulz.de/enron-email-data/

[39]Yang Dingqi, Zhang Daqing, Zheng V W, et al.Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(1): 129-142

[40]Sankar A, Wu Yanhong, Gou Liang, et al. DySAT: Deep neural representation learning on dynamic graphs via self-attention networks[C] //Proc of the 13th Int Conf on Web Search and Data Mining. New York: ACM, 2020: 519-527

[41]Peng Hao, Yang Renyu, Wang Zheng, et al. LIME: Low-cost incremental learning for dynamic heterogeneous information networks[J]. IEEE Transactions on Computers, 2021, PP(99). DOI:10.1109/TC.2021.3057082

[42]Ghamrawi N, McCallum A. Collective multi-label classification[C] //Proc of the 2005 ACM CIKM Int Conf on Information and Knowledge Management. New York: ACM, 2005: 195-200