基于时空注意力深度模型的动态链路预测

陈晋音,徐轩桁,吴洋洋,陈一贤,郑海斌

(浙江工业大学 信息工程学院,杭州 310023)

1 引 言

复杂网络的动态链路预测广泛应用于各个领域,包括社交网络[1]、经济学[2]、生物学[3],及工业系统[4]等.绝大多数实际网络的结构随时间推移而演变(节点或连边随着时间的推移而添加和删除),这类网络的链路预测称为动态网络链路预测[5-8].动态网络链路预测已经广泛应用于各种现实世界的网络[9,10],包括社交网络中预测朋友关系[11]、通信网络中预测未来通信关系[12]、科学合作网络中预测未来的同事关系[13]、社交安全网络中定位犯罪分子并预测犯罪时间[14]、疾病传染[15]、蛋白质相互作用[16],及其他许多领域的演化模式.

动态网络的链路随时间的增加而变化,连边使其预测比静态网络更具挑战[17],如何准确地预测动态网络中潜在的或未来的链路已经受到了广泛地关注.现有的许多动态网络链路预测方法[14-18]利用历史网络信息并将其压缩成一个网络来预测下一时刻的网络结构.最典型的方法是基于相似性的动态链路预测,最常见的比如共同邻居CN等.基于机器学习的方法也应用于计算链路预测的最佳相似性[19-23],但通常优化方法的计算复杂度较高,容易受到现有的相似性指标的限制.网络嵌入的方法也通常用于链路预测,比如DeepWalk[24],Node2vec[25],LINE[26]等.

然而,这些方法是从静态网络链路预测任务中演变而来,通常只是把先前时刻的网络拓扑信息看作一个整体,而不考虑先前时刻网络的动态演变过程.

除了只是利用动态网络空间特征的动态链路预测方法之外,也有许多方法提出通过学习动态网络的时间信息来提高动态链路预测性能.大部分方法通过将结构信息和时间信息集成在一起来模拟动态演化过程.由于在动态网络的演化过程中,最近的网络对于未来的链路预测更加可靠,Nahla Mohamed Ahmed[8,30,31]等提出了利用阻尼系数对T个时刻的网络的全局拓扑信息进行集合,从而得到更好的预测性能.也有不少研究者开始将时间信息集成到网络嵌入中[32-36],在不同的时间步骤中学习每个顶点的表示向量,使其能够捕获动态演化模式.但是这些方法通常只关注未来新添加连边,而忽略其他消失或者一直不变的连边.在动态链路预测任务中,新添加的链路以及消失或者不变的链路分别反应不同的网络演化模型,所以需要关注所有的链路(存在或不存在的)并学习相应的演化模式.

为了有效提高动态网络链路预测的性能,大部分方法尝试同时学习动态网络的时序以及网络特征,可是还存在着许多挑战.因此,本文提出了一种能够处理时空数据的基于时空注意力的深度模型(GLAT),分别在时间以及空间上关注更多与预测任务息息相关的输入特征,通过提取动态网络的时空特征,实现端到端(end-to-end)的动态网络的链路预测.GLAT模型的主要思想是充分利用GCN-attention模型学习隐藏状态和单元节点的网络结构,并通过LSTM-attention模型学习网络的时间特征,将注意力集中在所学习的时空特征中与任务最相关的部分,从而提高动态链路预测性能.GLAT可以有效地处理高维、时间依赖、稀疏结构的序列数据.在四个真实数据集上进行了大量实验.结果表明,GLAT模型明显优于当前其他先进方法.

本文的主要贡献如下:

1)提出基于端到端的动态网络链路预测模型(GLAT),有效的提取网络的时空特征.其中,通过注意力图卷积(GCN-attention)提取每个网络的空间特征,重点关注邻居节点的影响;通过注意力长短时记忆网络(LSTM-attention)提取动态网络的时序特征,关注每个节点在各个时刻的变化,从而提高预测模型的预测性能.

2)针对现有大部分方法只能预测部分网络的链路,无法准确预测整体网络的链路的缺陷,本文提出的GLAT通过计算整个网络所有链路(存在的和不存在的)的概率分数,实现整体网络的链路预测.

3)通过大量不同的实验,在多个动态网络数据集上验证了提出的方法的有效性,在AUC、GMAUC以及错误率等指标上,我们的模型明显优于目前的先进方法.

2 相关工作

近年来已提出许多动态网络链路预测方法,其中大多数方法利用历史网络信息并将其压缩成一个网络来预测下一时刻的网络结构.最典型的方法是基于相似性的动态链路预测[14],通过计算节点相似度判定是否存在连边关系,即节点相似性越大,存在连边的可能性越大.这类方法通常利用网络的拓扑信息来定义节点的相似性,称为结构相似性指标,一般分为局部和全局的相似性指数.局部相似性指数只需要节点的邻域信息,例如共同邻居(CN)[18],使用两个节点的共同邻居数量作为指标,简单有效.其他常见的局部相似度指标包括JA、AA、RA、Salton指标等[14].全局相似度指标需要利用网络的全局拓扑信息,常见的包括Katz、SimRank 、LHNI及MFI指标等[14].

方法[19-23]提出了基于机器学习进行动态链路预测,通过计算网络的最佳相似性来提高链路预测的性能.Catherine A等[19]提出协方差矩阵自适应演化策略(CMA-ES)进行优化权重,从而实现了16个邻域和节点相似性指标的线性组合,提高链路预测的精度.Chen等[20]提出了一种监督的动态网络链路预测方法,为每个属性训练一个分类器,并集成所有分类器的结果进行链路预测.通常优化方法的计算复杂度较高,易受到现有相似性指数的限制.

为了更深层次地考虑网络的结构相似性以及同质性,提出了许多用于动态网络链路预测的网络嵌入方法.受word2vec的启发而提出了DeepWalk[24]和node2vec[25],通过抽样节点生成游走序列并利用skip-gram模型获得节点和连边的向量.其他基于随机游走的方法,比如大规模信息网络嵌入(LINE)[26],以类似的方式学习节点表征,但具有不同的游走策略.这样的方法将网络映射到低维向量空间以获得每个连边的特征向量,训练分类器来预测连边(二分类:存在或不存在).

上述动态链路预测方法都基于网络,即根据给定时间内网络的结构信息来预测未来时刻的链路关系.然而,这些方法仅考虑先前时刻的网络拓扑信息作为一个整体,而忽略先前时刻网络的动态演变过程.

除了学习动态网络空间特征之外,也有方法通过学习动态网络的时间信息来提高动态链路预测性能.人们开始利用先前的网络序列来预测未来的链路,通过将结构信息和时间信息集成在一起以模拟动态演化过程[8,27-31].Sina Sajadmanesh等[27]引入了非参数广义线性模型(NP-GLM),根据链路出现时间的特征推断出时间的潜在概率分布.由于网络的动态特性,最近的对于未来的链路预测更可靠,Nahla Mohamed Ahmed等[8,30,31]提出了一种阻尼系数计算方式,对T(窗口尺寸)个时刻的网络的全局拓扑信息进行集合,从而得到更好的结果.Xiaoyi Li等[29]提出了一种基于条件时间受限玻尔兹曼机(ctRBM)的深度模型框架,根据个体过渡方差以及局部邻居的影响来预测链接.

由于现有的网络嵌入方法直接应用于动态图的每个网络,很大程度上忽略了网络的时间动态信息,因此不少研究[32-36]开始将时间信息集成到网络嵌入中,使其能够捕获动态演化的动态演变.Giang Hoang Nguyen等[34]提出了从连续时间动态网络学习时间约束的嵌入方法.Lekui Zhou等[35]提出了一种新的表征学习方法,即动态三元组学习法(DynamicTriad),保存给定网络的结构信息和演化模式,从而使模型能够捕捉网络动态,并学习每个节点在不同的时间步骤中的表征向量.这些方法通常只关注未来新添加的连边,而忽略其他消失或者不变的连边.

长短时记忆网络(LSTM)[37]最初由Sepp Hochreiter和Jrgen Schmidhuber于1997年提出,是RNN的一种特殊变种,可以处理长期依赖的时序数据.LSTM已成功应用于各个领域,比如图像领域[38]、视频处理领域[39]、语言模型[40]、语音识别[41]和机器翻译等[42].最近,在动态网络中,LSTM模块用于自适应地捕获每个时间下表征的多维交互之间的依赖性[43].

大多数现实世界的网络数据不具有规则的空间结构,导致在图像领域中广泛使用的卷积神经网络不能处理这些网络数据.因此,Joan Bruna[44]最早于2014年提出了图形卷积网络(GCN)来处理网络数据.最近,一些工作采用GCN来学习网络数据的结构特征,从而实现各种任务,比如网络表示学习和节点分类[45].

在许多基于序列的任务中,注意力机制(attention)已经得到了广泛的研究.注意机制的优势是帮助深度模型集中关注输入中与任务最相关的部分,做出更好的决策.Mnih等[46]使用注意力更加关注输入图像对应于图像分类任务的相关部分.Xu等[47]使用注意力集中于图像描述任务的关键图像信息.Bahdanau D等[48]通过在输出句子中生成相应单词时分配权重来反映机器翻译任务的注意力,该权重反映了输入句子中不同单词的重要性.Ma等[49]提出了单个注意力模型在医疗诊断预测中的应用,并提出了多种通用的注意力分数的计算公式.Wang等[50]把注意力模型应用于新闻推荐/筛选领域,根据新闻的文本和种类信息,同时考虑新闻的时效性和时间特征来完成新闻筛选.此外,注意力模型还广泛应用于问答系统[51-53],根据问题发现哪一部分输入和这个问题相关,从而能生成更加相关的答案.总之,基于注意力机制的深度模型已在计算机视觉和自然语言处理领域中实现重要应用.

注意力机制的深度模型在网络领域也有成功应用[54-56].Choi等[54]提出了基于注意力模型的医学本体图分析,他们的模型仅针对有向无环图(DAG),而不是有向(无向)有权(无权)网络.Velickovic等[55]提出了一种新的图注意网络(GAT)来执行图结构数据的节点分类任务,其思想是计算图中每个节点的隐藏表示,通过遵循自我注意力策略来关注邻居节点.Lee[56]研究了基于注意力的图分类问题,提出了一种新的RNN模型,即图注意模型(GAM),通过自适应地选择信息节点序列处理子图.使用注意力机制帮助模型专注于图中较小但信息丰富的部分,提高了模型的处理效率.

3 GLAT模型

本节介绍用于动态网络链路预测的GLAT模型.它能够根据时空注意力机制关注与任务相关的关键特征,为未来添加或删除的连边学习动态网络的空间和时间特征.

3.1 总体框架

GLAT模型的核心思想是将注意力图卷积(GCN-attention)和注意力长短时记忆网络(LSTM-attention)的组合作为一个编码器,放置在模型的输入端用于学习结构序列网络的时空特征,利用注意力长短时记忆网络(LSTM-attention)关注每个节点的多个时刻的隐藏表征并学习每个节点的连边状态的时序特征,同时利用(GCN-attention)通过更加关注每个节点的邻居信息来学习每个时刻网络的结构特征.最后利用全连接层网络作为解码器来将提取的特征转换回原始空间,输出预测的网络数据,并以统一的方式实现动态网络链路预测.模型系统框架如图1所示.

3.2 模型设计

GLAT模型分成三个模块:LSTM-attention模块、GCN-attention模块和解码模块.

图1 GLAT模型的系统框图Fig.1 Overall framework of GLAT

3.2.1 LSTM-attention模块

首先将动态网络里每一个时刻的网络对应的邻接矩阵A作为输入,利用所提出的LSTM-attention模型从结构序列数据{At-T,…,At-1}中提取相应的时间特征{ht-T,…,ht-1},并通过时间注意力机制关注T个时刻的隐藏层向量h来计算上下文向量at.

LSTM-attention模块主要依赖于两个状态值,即用于提取输入信息的隐藏层状态h,以及用于保存长期信息的细胞层状态c.GLAT的关键在于它的细胞层状态c贯穿整个前向过程中,导致信息在细胞层上传递可以保持长时间不变.在动态连边预测任务中,由于细胞层状态和隐藏层状态分别反映不同的信息,我们建议使用两个GCN模型分别对细胞层状态和隐藏层状态执行卷积运算.

在LSTM-attention模型中,第一步是确定先前细胞层状态的信息丢失量.这个决定通过遗忘门ft∈[0,1]d来完成,其中0表示完全遗忘,1表示完全保留,定义如下:

ft=σ(WfAt+Ufht-1+bf)

(1)

其中At∈RN×N定义为t时刻的输入数据,ht-1∈RN×d定义为t-1时刻的隐藏层状态,Wf∈RN×d、Uf∈Rd×d和bf∈Rd分别对应遗忘门的权重和偏置矩阵,σ(·)表示sigmoid函数,N表示输入维度,d表示模型隐藏层维度.

(2)

其中Wi,c∈RN×d、Ui,c∈Rd×d和bi,c∈Rd分别对应输入门的权重和偏置矩阵.

这样更新后的细胞层不仅可以保存长时间的信息,而且可以选择性的过滤掉一些无用的信息.最后,我们需要决定把哪些更新后的细胞层信息输出,次任务由输出门来完成:

ot=σ(WoAt+Uoht-1+bo),ht=ot⊙tanh(ct)

(3)

其中,Wo∈RN×d、Uo∈Rd×d以及bo∈Rd分别对应输出门的权重和偏置矩阵.

在动态网络链路预测任务中,最终目标是根据T个时刻的连边矩阵的信息来预测下个时刻可能出现的链路状态.而{ht-T,…,ht-1}∈RN×d是经过模型提取的每个时刻的网络所有节点的特征矩阵,对于每个时刻的特征矩阵来说,它都可能包含预测需要的部分信息.因此,本文利用一个时间注意力机制来计算一个上下文向量ct,来捕获时间下的相关信息,关注各个时间的特征向量来帮助实施预测任务.时间注意机制仅根据每个时刻的隐藏层状态来计算各个时刻对应的注意力系数,计算如下:

eti=Wtahi+bta

(4)

其中Wta∈RN×d和bta∈RN分别表示时间注意机制的权重和偏置矩阵.eti∈RN表示i时刻每个节点隐藏层向量对应的注意力系数.为了使注意力系数在不同时间之间易于比较,使用softmax函数对所有时刻对应的eti进行标准化:

(5)

根据获得的归一化后的权重向量和T个时刻的隐藏层向量计算上下文向量:

(6)

最后获得的上下文向量at∈RN×d作为LSTM-attention模块最后输出的时间特征向量.

3.2.2 GCN-attention模块

在LSTM-attention模型中,每个时刻提取的时间特征h可以看成当前时刻所有节点向量的集合h={h1,h2,…,hN},hi∈Rd.本文把当前时刻所有节点向量的集合作为GCN-attention模型,通过空间注意力机制关注邻居节点来更新每个节点的隐藏层向量.

首先,隐藏层向量与一个滤波器相乘,输出新的隐藏层向量:

(7)

值得注意的是,本文采用K阶的切比雪夫多项式来近似滤波器gθ,可以利用距离中心节点最大K阶的节点信息,因此K是一个非常重要的超参数.如图2所示,当K=1,只考虑节点6本身的信息;当K=2,会考虑到1阶节点(1,5,7)信息对节点6的影响;当K=3,会额外考虑到1阶节点(1,5,7)以及2阶节点(2,4,8,12)的信息.当K越大,可以考虑更大更广的领域节点与中心节点的关系,但是会大大增加计算量.一般情况下,选择K=3.

图2 GCN的阶数K的说明Fig.2 An illustration of K of GCN

当更新了隐藏层向量后,本文利用一个简单的图注意层作为空间注意力机制应用于每个时刻的网络,如图3所示.

本文在节点上执行自我注意,即一个共享的注意力机制a:Rd×Rd→R来计算注意力系数:

eij=a(hi,hj)

(8)

在实验中,注意力机制a是一个简单的单层前馈神经网络:

eij=LeakyReLU(Wga1hi+Wga2hj)

(9)

其中,Wga1,Wga2∈Rd是相应的权重矩阵,然后利用LeakyReLU(负值非零斜率=0.2)作为最后的非线性激活函数.在图注意层里,eij表明节点j的特征对于节点i的相似度.在最通用的表述中,注意力模型允许每个节点与其他所有节点之间计算注意力系数,而丢弃所有结构信息.通过执行邻域注意将网络结构加入到注意力机制中-我们只计算节点i与节点j∈Ni之间的注意力系数eij,其中Ni表示图中节点i的邻居节点集合.在所有的实验中,这些将是i的1阶邻居节点集合(包括节点i本身).为了使注意力系数在不同节点之间易于比较,使用softmax函数在节点j的所有选项中对对应的eij进行标准化:

(10)

归一化后的注意力系数将用于计算与它们对应的特征的线性组合,以用作每个节点的最终输出特征:

(11)

更新后的隐藏层向量作为下一个时刻LSTM-attention模型的输入.这样LSTM-attention模型与GCN-attention模型构成了GLAT的整个时间序列下的前向过程.最后获得的上下文向量作为编码器的最后输出的时空特征向量.

图3 图注意层的整个框架Fig.3 Overall framework of graph attention layer

3.2.3 解码器

为了输出最终的预测网络,使用全连接层网络作为解码器,将编码器最后输出的特征向量转换为最终的概率矩阵:

(12)

其中Wd∈Rd×N和bd∈RN分别表示解码器的权重和偏置矩阵,L表示全连接层的层数,并且每个隐藏层中的单元数量可以根据输入数据的变化而变化,以获得更好的性能.Pt∈RN×N表示最后的输出链路概率矩阵,每一个Pt(i,j)=[0,1]表示节点i到节点j存在链路的概率,Pt(i,j)的值越大,链路存在的概率越大.

3.3 模型训练

训练整个GLAT模型的目的是为了让动态网络链路预测的准确率提高,使得预测输出的概率矩阵Pt与t时刻的连边矩阵At越相似越好,采用L2距离来衡量预测值与真实值之间的相似程度.

(13)

但是,由于网络的稀疏性,导致连边矩阵中零元素的数量要远远大于非零元素的数量,如果仅仅将L2范数作为所提出的级联模型的Loss函数,容易导致Loss函数更偏向于保证零元素的预测准确率,从而导致过拟合.为了保证模型能在一定程度上避免过拟合,添加正则化损失函数Lreg.本文通过计算GLAT模型中所有权重的F范数的平方和,来计算正则化损失:

(14)

训练过程中总的Loss定义为:

L=L2+βLreg

(15)

其中,β用于调整L2与Lreg的权重比例.在训练过程中,采用Adam优化器来训练GLAT模型的参数.

4 实验与分析

4.1 实验设计

本文在四个动态网络数据集:CONTACT[57]、HYPERTEXT09[58]、ENRON和RADOSLAW[59]上实验,并与CN[18]、node2vec[25]、LINE[26]和TNE[36]方法做结果对比.

表1 动态网络数据和统计
Table 1 Dynamic network data and statistics

Dataset|V||ET| ddmaxTimespan(days)CONTACT27428.2K206.220923.97HYPERTEXT0911320.8K368.514832.46ENRON15150.5K669.851771137.55RADOSLAW16782.9K993.19053271.19

本文选择AUC、GMAUC[17]以及错误率ErrorRate作为基准评价指标.

AUC:如果在n个独立的比较中,如果存在n′次存在的连边比不存在的连边具有更高的分数,以及n″次存在的连边与不存在的连边具有相同的分数,则AUC定义为:

(16)

GMAUC:用于测量动态链接预测性能的度量标准.它通过几何平均来结合PRAUC和AUC这两个指标,因此GMAUC被定义为:

(17)

其中LA和LR分别表示增加连边和移除连边的数量,PRAUCnew表示在新出现连边里计算的PRAUC分数,AUCprev表示已经存在的链路计算的AUC分数.

ErrorRate:错误率被定义为错误预测链接的数量(由Nfalse表示)与真实存在的链接的总数(由Ntrue表示)的比值,具体表示为:

(18)

与仅计算两个网络中链接的绝对差的SumD不同,错误率考虑了真正存在的链接总数量来避免被欺骗.

特别的,本文将ErrorRate分为两部分作为有效补充:ErrorRate+和ErrorRate-.ErrorRate+表示真实存在链接中错误预测链接数与所有链接总数之比.ErrorRate-表示真正不存在的链接中错误预测链接的数量与所有链接总数的比率.

4.2 实验结果

在模型的训练过程中,把10个连续的网络{Gt-10,…,Gt-1}作为一个样本输入到GLAT中来预测Gt.对于TNE模型,和我们的GLAT模型具有相同的输入.对于那些传统的无法处理时间依赖性的方法CN、node2vec以及LINE来说,一般有以下两种典型的处理方法:(1)只利用Gt-1的信息来预测Gt[60];(2)把先前10个网络整合成一个静态网络来预测Gt[61].由于单单只利用上一个时刻网络的信息来进行链路预测可能会出现信息量不足的情况,而且GLAT模型把10个连续的网络作为输入,为了保证输入数据信息的相似性,本文选择了第二种方法.

由于网络的演化模式可能随着时间而改变,选择前20个测试样本和全部80个样本的三个性能指标的平均值来反应预测模型的短期和长期预测性能.结果如表2所示,无论是密集还是稀疏的网络,GLAT模型的短期和长期预测能力几乎在所有情况下都优于其他方法.由于CN、node2vec和LINE方法的效果一般,表明这些为静态网络设计的方法并不适用于动态链路预测.相反,TNE和GLAT由于其捕捉动态特性的能力,在动态链路预测中获得更好的性能.相比之下,GLAT模型在大多数情况下比TNE表现更好,特别是在能体现添加和删除连边的动态链路预测性能的GMAUC指标上.

此外,针对每个时刻的测试样本,将预测的网络与真实的网络的链路差与真实存在的连边进行比较来计算错误率.预测网络和真实网络之间的错误率的显著差异表明该度量是对AUC的良好补充,以全面地测量动态链路预测的性能.如表2所示,大部分对比方法可能预测出比真正存在的链路数更多的无效连边,从而导致了相对较大的错误率.传统的网络嵌入的方法node2vec以及LINE在错误率方面效果较差,错误地预测出大量无效链路,是真正存在链路数的10倍甚至70倍.这是因为动态网络的链路随时间演化,而网络嵌入的方法利用的预训练的线性回归模型无法捕捉链路的动态变化,从而对链路进行错误分类.TNE在错误率上效果也理想,这可能是因为TNE采用的矩阵分解方法在稀疏邻接矩阵上无法平衡正负样本,导致无法很好的处理我们给出的稀疏动态网络.而GLAT在错误率上明显优于其他所有对比算法,结果再次证明了GLAT模型在动态链路预测准确性方面具有更好性能.这是因为其他对比算法直接基于前10个网络来预测下一个网络,GLAT需要根据前240个样本中来预训练模型,可以更加有效地学习动态网络的演化模式.同时,GLAT模型不仅使用LSTM来学习序列网络的时序特性,还使用GCN来了解每个时刻的网络特征,而且提出了一个时空注意力机制,可以有效的关注与任务息息相关的信息.因此,在测试过程中,我们的模型可以更准确地预测未来的连边,具有较低的预测误差.在这四个数据集中,ENRON数据集在时间序列上的演化过程中发生了较大的变化,导致所有方法在该数据集上的表现都有所下降.因此我们预先训练好的GLAT模型在测试集上的评估结果相对较差.从表2还可以得出,我们的模型在错误率方面的优势要远远大于AUC和GMAUC指标.这也从侧面反应,与传统的性能指标AUC和GMAUC相比,我们新定义的错误率度量在评估动态链路预测时更具可辨性.

表2 动态链路预测性能AUC、GMAUC以及误差率
Table 2 Dynamic link prediction performances on AUC,GMAUC,Error Rate

评价指标方法CONTACTHYPERTEXT09ENRONRADOSLAW2080208020802080AUCCN0.85410.84570.66960.72660.72470.81020.83420.8408node2vec0.52120.51260.63480.65910.76590.68060.61030.7676LINE0.60640.42390.54160.53570.52940.50420.52920.5231TNE0.94420.93710.90760.85170.80960.83140.90530.8801GLAT0.99000.98730.95850.97370.88790.87110.98750.9862GMAUCCN0.84450.83300.60100.67490.68180.79290.82790.8343node2vec0.18050.13980.48910.51630.40690.54170.72410.7203LINE0.45020.38750.46860.37240.26420.23580.33410.3105TNE0.90830.89580.88560.83920.82330.79740.82820.8251GLAT0.99270.98840.98870.92170.91070.88310.99740.9978ErrorRateCN0.85960.78363.77635.26742.11113.30254.88805.6093node2vec29.34325.20724.39812.82668.80831.97120.71317.113LINE11.32711.42516.6906.78823.25712.1581.54883.0576TNE1.81691.66561.64531.96752.04682.93354.76354.3204GLAT0.21080.31150.21420.24340.37470.44310.17400.1882ER+CN0.28850.30510.56100.34190.53510.33880.25280.2201node2vec0.30010.29890.40870.35950.17430.34930.22250.2867LINE0.21190.22910.27300.34830.21170.19580.37600.2655TNE0.94360.94370.75980.58000.67020.45180.17950.1829GLAT0.15950.18580.18990.18840.15670.17780.10350.1175ER-CN0.57110.47853.21534.92551.57602.96374.63515.3892node2vec29.04324.90823.99012.46668.63331.62220.49016.826LINE11.11511.19616.4176.43923.04611.9621.17292.7921TNE0.87330.72190.88551.38741.37662.48174.58414.1375GLAT0.05130.12570.02440.05500.09710.10400.07050.0707

有趣的是,在大多数情况下,对比方法的ErrorRate-要远远大于ErrorRate+,尤其是node2vec和LINE.他们更有可能将不存在的链路预测为存在的链路.由于我们实验的动态网络数据基本上都是稀疏网络,因此嵌入式方法中的预训练分类器无法有效地对稀疏网络进行分类.对于我们的GLAT方法,虽然ErrorRate+略大于ErrorRate-,但我们的方法的ErrorRate+仍然是所有比较实验中最小的.进一步表明,我们的方法不仅在不存在的链路上具有很高的预测精度,而且在现有链路上具有更好的预测性能,可以更好地预测网络的动态链路.

从表2可以看出,ErrorRate+的预测效果非常显著,并且ErrorRate+可以很好地应用于基因调控网络中的联合预测.在基因调控网络中,节点代表基因,有向连边表示基因之间的调节关系.我们的模型可以应用于基因调控网络的连边预测,一方面可以进一步探索已知调控网络的潜在调控关系,另一方面,它可以为未知基因调控提供研究方向.另外,在研究合作网络中,一般会预测哪些研究人员会一起工作,但是不能错误地预测.因此,ErrorRate-在研究合作网络中非常重要,误差率越小,预测模型的性能越好.

表3 前10%重要链路的预测错误率
Table 3 Prediction error rate of the top 10% important links

评价指标方法CONTACTHYPERTEXT09ENRONRADOSLAW2080208020802080DCCN0.37800.44940.52880.58060.41300.41480.49100.5466node2vec0.59740.59760.43970.48370.62960.49910.49310.5037LINE0.73820.75200.42970.42300.39830.37890.51860.4691TNE0.82350.78430.28690.33600.24110.21380.23420.2450GLAT0.05100.07950.05780.08070.12530.13650.03570.0491EBCCN0.48680.53740.68650.41980.44330.40880.53470.5076node2vec0.63750.62950.56020.50640.51740.49630.50320.5361LINE0.81650.79520.71950.78740.72370.80490.90790.8541TNE0.97460.98460.66550.47050.64020.46690.36580.3543GLAT0.29290.41180.22660.27410.27900.30450.15490.1737

此外,在大多数情况下,GLAT模型在短期的预测性能上要优于长期的预测性能,这是因为在测试集中,后半段的演化模式发生了变化,而我们的模型更倾向于拟合前半段的演化模式.

接着,针对80个测试样本,其中Gt从1变化到80,绘制GLAT模型在四个数据集上获得的AUC、GMAUC以及错误率这三个度量随着时间变化而变化的曲线,作为时间t的函数来反应动态链路预测性能.

图4 在AUC、GMAUC以及错误率随着时间变化而变化的曲线Fig.4 Curves of AUC,GMUUC,and Error rate as a function of time t

从图4所示可以得到:随着时间的增加,AUC和GMAUC在逐渐减小,而错误率在逐渐增加,这表明由于长时间下动态网络演化的不确定性,针对动态网络链路长时间预测相对困难.有趣的是,对于RADOSLAW数据集,预测性能相对稳定,这可能是因为它的网络结构的演化模式呈现周期性,拥有很好的长时预测性能.为了进一步解释这一现象,本文研究了四个网络中两个最常见的结构特性(即平均度和平均聚类系数)随着时间增加的变化趋势.结果如图5所示,我们可以看到CONTACT、HYPERTEXT09和ENRON数据集里平均度和平均聚类系数随着时间变化而发生了显著变化,而RADOSLAW则相对稳定.这些结果反映了本文提出的GLAT可以在动态网络上可以实现较好的长期预测性能.

综上所述,尽管一些方法在AUC这个统计指标上具有较优的性能,但是它们在错误率上却不尽人意,还是错误地预测了许多无效链路.但是在大多数现实场景中,我们可能只关心那些最重要的连边是否预测正确.因此,进一步评价了所有模型在特别重要的部分链路上得预测性能.本文使用两个度量来衡量每个连边的重要性:度中心性(DC)和链路介数中心性(EBC).度中心性DC起初是根据邻居的数量来衡量节点的重要性,本文利用源节点和目标节点的度中心性之和来衡量该条链路的重要性.当根据DC和EBC选出前10%重要链路后,计算这些重要链路的预测错误率,结果如表3所示.在大部分情况下,GLAT在四个数据集上具有最低的错误率,不管是短期还是长期预测.这进一步证明了GLAT在预测重要链路的方面仍然表现十分出色.此外,比较表2和表3的结果,发现前10%重要链路上的错误率要远小于所有链路上的错误率率.这表明,GLAT在那些重要的链路上比不重要的链路的预测性能更加优异.

图5 网络结构属性(平均度值和平均聚类系数)随着时间增加的变化趋势Fig.5 Trends curves over time of network structure attributes(average value and average cluster coefficient)

5 结 论

本文提出了一种能够处理时空数据的基于时空注意力的深度模型GLAT,用于动态链路预测.整个GLAT模型主要利用GCN-attention模型学习隐藏状态和单元节点的网络结构,并通过LSTM-attention模型学习网络的时间特征,将注意力集中在所学习的时空特征中与任务最相关的部分,从而提高动态链路预测性能.最后利用全连接层网络作为解码器来将提取的时空特征转换回原始空间,输出预测的网络数据,从而实现动态网络链路预测.GLAT不仅能捕捉连续网络间的时间依赖性,还考虑到了网络结构的影响.因此,它可以更好地捕获网络演化的模式.最后,进行了大量实验,与其他链路预测方法在各种动态网络数据集上进行比较.结果表明,GLAT不仅在AUC、GMAUC以及错误率这几个整体指标上明显优于其他模型,而且在重要链路预测任务上体现了优异的性能.

未来的研究将侧重于大规模的动态网络的链路预测,尽可能降低所提出的GLAT模型的计算复杂度,使其能适应其他各种应用.此外,还需要研究并改进新的时空注意力机制来提高模型的性能.