基于时空注意力的社交网络信息级联预测模型

刘 超,韩 锐,刘小洋,黄贤英

(重庆理工大学 计算机科学与工程学院，重庆 400054)

0 引言

微博、微信、Facebook等在线社交平台的出现，为信息的传递与共享提供了巨大的便利，从而促进了信息的快速传播，并因此产生了信息级联现象。这种现象普遍存在于: 论文与博客引用[1-2]，电子邮件转发[3]，以及各种社交平台推文的转发(如新浪微博[4]和Twitter[5])中。信息级联预测能够预测信息级联的大小和广度，并可以控制(或加速)各种场景中的信息传播，可应用于企业的病毒式营销[6]、社交网络影响力最大化[7]、媒体定点投放广告[8]和虚假新闻检测[9-10]等领域。因此，信息级联预测已成为社交网络分析领域的研究热点。

目前信息级联预测方法可归纳为四类: 基于扩散的方法[11-12]，基于特征的方法[13]，基于生成建模的方法[4]和基于深度学习的方法[5,14]。基于深度学习的方法是目前预测最高效的方法，该方法通常将数据通过嵌入表示学习提取节点的特征，再利用神经网络自动学习节点的特征，最后进行预测输出。DeepCas[5]是第一个基于深度学习的信息级联模型，通过随机游走将级联图转换为节点序列，并自动学习各个图的表示，然后使用循环神经网络学习级联的时序信息。DeepHawkes[4]将级联图转换为扩散路径，然后使用Hawkes过程学习级联特征，使模型具有高度可解释性。Topo-LSTM[15]利用动态有向无环图DAG以及每个节点生成拓扑感知的嵌入来进行预测。CasCN[14]模型利用图卷积[16]网络嵌入级联子图的空间结构信息，再使用循环神经网络提取时序信息，再进行输出预测。

虽然上述模型能够预测信息级联，但是这些模型对级联数据时序特征和空间拓扑结构利用不全面。文献[4-5]利用了信息级联的时序特征，忽略了空间特征;文献[15]考虑了信息级联的空间拓扑结构，但却忽略了时序信息。文献[14]因考虑了信息级联的时序信息和空间拓扑结构，故实验效果优于文献[4-5,15]，但在捕获时序信息时会丢失部分空间拓扑结构，因而对最终的预测精度产生影响。由此可见，现有预测模型没有实现时序信息与空间拓扑结构的有效耦合，制约了模型的预测效果。

针对以上不足，本文提出一个端到端的深度学习模型，为了有效地捕获级联信息的时序和空间拓扑结构特征，先捕获信息级联的空间拓扑结构，然后在时序信息的传播过程中同时演变空间拓扑结构，最后利用注意力机制将时序信息和空间结构信息输出的特征进行耦合。因为级联图的大小不同，容易忽略一些边缘信息，而且各个边缘的权重不一致，导致对全局结构的嵌入不全面，采用注意力机制实现特征耦合，有偏重地提取边缘特征信息。

本文主要贡献如下:

(1) 引入了时空注意力机制，实现了级联图的时序信息与空间结构信息捕获后的耦合，使模型适用于不同的图结构、时序信息。

(2) 在利用双向循环神经网络捕获时序信息的同时，采用图卷积网络捕获级联信息的空间结构信息，能更好地捕获时序特征和空间结构特征。

(3) 提出一种新的面向社交网络的信息级联预测模型，与传统基于循环网络的信息级联预测模型相比，ICP模型的级联预测精度更高。

1 相关工作

1.1 图卷积网络

图卷积网络(GCN[16])通过计算图的拉普拉斯特征分解，从节点间的信息传递或等效的某些邻域聚合功能中提取高级特征再进行傅立叶域中的卷积运算，提升各种图任务的执行效果。随着图卷积网络的发展，先前的一些工作将图卷积网络应用于信息级联，利用其特性挖掘级联信息的空间拓扑结构信息。在文献[14,17]中，利用图卷积网络提取级联信息的空间拓扑信息，用于预测信息级联。

1.2 注意力机制

注意力机制在许多机器学习任务中都展示了显著的效果，如图像字幕[18]、视频字幕[19]和机器翻译[20]。注意力机制对重点关注邻域分配更多的注意力资源以获取更多所需要的特征信息，抑制其他的无用信息，从而取得更好的效果。文献[5]中，采用注意力机制计算级联序列的权重，更准确地预测级联信息。文献[21]采用注意力机制探索用户与用户间隐式的级联扩散，从而实现预测级联信息。注意力的关键思想是学习一组分配注意权重(将总和求归一化): 较高(较低)的权重表示相应的功能对于最终任务提供较多(较少)的信息。

2 模型介绍

本文提出一个端到端的深度学习面向社交网络的ICP模型，采用级联子图Ci(t)作为输入，预测推文pi在Δt时间内传播的增量ΔSi。ICP模型由4个组件组成，首先，从级联图中对子图节点进行采样并生成邻接矩阵序列；然后，将观察时间窗口内的邻接矩阵序列和级联图的结构信息输入到Bi-LSTM网络；再将Bi-LSTM得到的表示输入到注意力机制，耦合时间序列和空间结构特征，再输入衰减函数，得到符合时间衰减效应的特征表示；最后，使用全连接层输出进行预测。

2.1 问题定义

图1 级联图

表1 符号定义表

2.2 节点嵌入层

推文pi观察到的级联图Ci(t)，将其表示为邻接矩阵形式，并为每个节点加入自环，如图2所示。然后根据级联图Ci(t)中每个节点的到达时刻进行独热编码(One-Hot Code)表示节点特征。将观察窗口[0,T)划分为l个不相交的细粒度时间间隔{[t0=0,t1),[t1,t2),…,[tl-1,tl=T)}，然后再对每个时间间隔进行编码。

图2 级联子图序列的采样表示

(1)

为了捕获级联信息在传播过程中的空间结构信息，采用图卷积网络来学习嵌入[22]。信息扩散过程类似于马尔科夫过程，即经扩散一段时间后会收敛于一个稳定的分布，类似于分布[23]。因此，设级联的拉普拉斯矩阵Δc，符合级联图的随机游走特征，设马尔科夫状态转移概率矩阵P=D-1A，且存在φi={φ1,φ2,…,φn}满足φTP=φT。根据图卷积网络[16]公式:

(2)

可得拉普拉斯矩阵Δc:

(3)

其中，D表示级联图的度矩阵，K表示捕获的邻域层数，

2.3 图卷积与双向循环神经网络层

图3 模型框架图

(6)

(7)

(8)

2.4 注意力机制

(11)

2.5 输出预测层

先前研究发现，信息级联存在着时间衰减效应，即一个节点对其他节点的影响会随着时间的推移而减小[24]。本文采用非参数化时间衰减函数λf(T-ti)，根据文献[4]得:

(12)

ICP模型最后一部分是由全连接层(MLP)组成。根据前面计算得到的h′t，可计算出ΔSi，如式(13)所示。

ΔSi=MLP(h′t)

(13)

最终任务是预测指定时间间隔内信息传播的增量，引入均方对数误差(Mean Square Log-Transformed Error, MSLE)，即:

(14)

作为损失函数loss，使用Adam优化器优化loss值，使其达到最优(最小)。

算法1 ICP算法

2: repeat3: for邻接矩阵序列ATi和对应的拉普拉斯矩阵Δci do4: 根据式(6) ～ 式(8)得ht←Bi-LSTM(*G(ATi,Δci))5: 根据式(9) ～ 式(11)得hat←Attention(ht)6: 根据式(12)得h't←Aggregate(λf(T-tji)hat)7: 根据式(13)得ΔSi←MLP(h't)8: 根据式(14)得使用Adam优化器对参数进行优化9: end for10: until convergence;

3 实验

3.1 数据集

为了评估ICP模型在信息级联预测中的有效性和扩展性，本文使用公开数据集进行实验并与先前的研究进行比较。数据集的数据信息统计见表2。

表2 数据集信息统计表

Weibo[4]: 此数据集是选取新浪微博在2016年6月1日生成的所有原始帖子，并跟踪接下来24小时内每个帖子的所有转发，总共包括119 313条贴文。图4(a)显示了级联大小的分布情况；图5(a)展示了级联的流行情况，显示24h后，流行达到饱和。本文遵循与CasCN[14]相似的设置，即观察时间窗口T=1, 2, 3h。最后，根据预处理后的层叠时间对层叠进行排序，并为层叠选择前70%的层叠为训练集，剩下的平均分为验证集和测试集。

HEP-PH[25]: HEP-PH数据集(高能物理现象学数据集)来自电子版arXiv论文引用网络，数据涵盖了1993年1月至2003年4月(124个月)期间的论文，其中有34 546篇论文的所有引文。如果论文i引用论文j，则论文引用图包含从i到j的有向边。如果论文引用了数据集之外的论文或被其引用，则该图将不包含有关此信息。图4(b)显示了级联大小的分布情况,图5(b)展示了级联的流行情况。对于观察窗口，选择T=3, 5, 7a，分别对应流行度达到最终规模的50%，60%和70%，如图5(b)所示。然后，收集70%的级联用于训练，其余平均拆分为验证集和测试集。

图4 级联尺寸分布图X轴为级联大小，Y轴表示不同级联大小对应的数量

图5 时间和级联数之间的百分比分布

3.2 实验环境和参数设置

本文所有实验在Ubuntu 16操作系统，Intel Core I9-9980XE CPU，128GB内存和NVIDIA TiTan RTX(24GB)显卡上进行。

对于DeepCas、DeepHawkes、Topo-LSTM和CasCN，参照DeepCas[5]设置用户的嵌入维度是50，循环神经网络每层的隐藏单元数是32，全连接层的隐藏单元数分别是32和16，用户学习率为5×10-4，其他学习率为5×10-3。每次迭代的批处理大小为32，当连续50次迭代，验证集的loss没有下降，模型训练过程将停止。Weibo数据集的时间间隔设置为10min，HEP-PH的时间间隔设置为2个月。

本文采用Tensorflow来实现ICP模型，并使用Adam优化器通过梯度下降来优化参数。除图表示学习的嵌入邻域层采用K=2外，其余模型参数设置与上述模型保持一致。

3.3 评估指标

根据现有的工作，在实验中选择标准评估指标——MSLE[见式(14)]来评估链接准确性。请注意，MSLE越小，其预测性能越好。

3.4 模型对比

3.4.1 基准版性能对比

将用本文所提出ICP模型的基准版，在真实的数据集上与先前级联预测模型进行实验对比。

DeepCas[5]是第一个用于信息级联预测的深度学习体系结构，其表示级联图为一组随机行走路径，并通过双向GRU神经网络通过管道传输，并带有注意力机制来预测级联的大小。它主要利用结构和节点身份的信息进行预测。

DeepHawkes[4]模型将端到端深度学习的预测能力集成到Hawkes过程的可解释因素中，以进行流行度预测。深度学习方法与级联动力学建模过程之间的结合弥合了信息级联预测和理解之间的鸿沟。该方法既属于生成方法又属于基于深度学习的方法。

Topo-LSTM[15]是有向无环图结构(DAG结构)RNN，将动态DAG作为输入，并为DAG中的每个节点生成拓扑感知的嵌入作为输出，从而预测下一个节点。

CasCN[14]模型结合了结构和时间的深度学习框架，利用图卷积网络捕获网络空间结构信息，通过循环神经网络合并了时间衰减函数实现时间信息的更有效利用。该模型是一种深度学习的方法。

表3总结了Weibo和HEP-PH数据集上ICP模型和其他模型基准版之间的性能比较。ICP模型与DeepCas对比，证明仅嵌入节点作为图表示是不够的，不能将图表示为一组随机路径。因DeepCas未能考虑时序信息和级联图的拓扑结构，导致其性能比其他基于深度学习方法要差。Topo-LSTM也缺乏对时序信息的处理，导致其性能也较差。DeepHawkes虽然以生成方式对级联进行建模，但由于其学习结构信息的能力较弱，因此无法发挥最佳性能。CasCN考虑了时序信息与空间拓扑结构，但忽略了二者特征之间的融合。最后，本文提出的ICP模型在两个数据集上的信息级联预测(推文转发和论文引用)，效果明显优于其他模型。如在Weibo数据集中观察1、2、3h，MSLE值分别为2.123,2.012,1.776；在HEP-PH数据集中观察3、5、7a，MSLE值分别为0.939, 0.843, 0.812，取得了较好的预测效果。与CasCN相比，本文提出的ICP模型预测误差分别降低了5.31%,1.18%,7.31%和6.47%,8.07%,8.46%，从而证实了模型的有效性。

表3 性能对比表(MSLE)

3.4.2 时空注意力对信息级联的影响

首先验证注意力机制的有效性，设计消融实验。构建一个ICP的删减版ICP-LSTM，即将基准版中的Bi-LSTM替换为LSTM，然后与CasCN进行比较，等价于ICP-LSTM是在CasCN模型的基础上添加了注意力机制。在实验过程中，二者参数一致，验证采样的邻域层数K=1,2时的实验效果如表4所示。

表4 注意力机制影响级联预测性能对比表(MSLE)

表4中给出了嵌入层K=1,2与CasCN模型K=2的性能对比。根据表4可以看出，当K=2时，本文提出的ICP模型优于CasCN模型，这是因为添加了注意力机制，能够耦合时序信息与空间结构信息。当K=1时，在Weibo中观察2h，ICP-LSTM的MSLE大于CasCN，是由于K=1，采取的空间结构信息不足，导致结果略低。

然后，验证时序信息对级联预测的影响，将ICP的变体ICP-BiLSTM与CasCN进行对比分析(ICP-BiLSTM为本文提出的ICP模型去掉注意力机制，也等价于将CasCN模型中LSTM网络替换为BiLSTM网络所产生的模型)。通过表5数据可以看出，当K=2时，Weibo观察3h的MSLE=1.783和HEP-PH观察7a的MSLE=0.84，优于CasCN的MSLE，从而证实时序信息在信息级联中的重要性。

表5 时序网络影响级联预测性能对比表(MSLE)

最后，验证时序信息和空间信息对级联预测的影响，在CasCN的基础上使用Bi-LSTM并添加注意力机制，再调整嵌入的邻域层数K分别与CasCN进行比较。通过表6的数据可以看出，在Weibo和HEP-PH数据集上K=1,2时，MSLE值均小于CasCN的MSLE值，表明本文提出的模型优于CasCN，对时序信息和空间拓扑信息的捕获更全面，从而提升了模型的效率，降低了损失率。

表6 时序空间影响级联预测性能对比表(MSLE)

上述实验表明，时序信息和空间结构信息对信息级联预测效果有重要影响。二者结合，能更好地保证预测的准确率。使用注意力机制耦合二者数据，使模型对时序信息和空间结构信息的捕获更加全面，也使模型更具有泛化力。

3.5 模型优化

本文注意力机制的主要思想源自于自注意力机制，可采用比自注意力机制耦合效果更优的方法。例如，可以采用多头注意力机制来替换文中的注意力机制，提出了ICP的变体ICP-Mhead。表7给出了在相同参数下CasCN、ICP与ICP-Mhead实验对比结果。可以得出，ICP-MHead模型的MSLE值均小于CasCN模型和ICP模型的MSLE值，表明使用多头注意力的效果明显优于CasCN模型。因为多头注意力机制采用多个头部去捕获特征信息，从而可以捕获更多的边缘信息(被忽略的时序信息和空间拓扑结构)，使得提取的特征更加全面，故ICP-MHead模型优于ICP模型。

表7 多头注意力机制影响级联预测性能对比表(MSLE)

3.6 模型收敛性

本节对ICP-LSTM，ICP-BiLSTM，ICP-MHead与ICP的收敛性进行分析，实验结果如图6所示。

图6中，可以看出，ICP-LSTM经过100轮迭代之后基本拟合，平均用时约7h；ICP-BiLSTM经过80次迭代之后基本拟合，平均用时约8h；ICP-MHead经过120轮迭代之后基本拟合，平均用时约12h。ICP经过50轮迭代之后基本拟合，平均用时约9h。ICP-MHead与ICP所采用Bi-LSTM和注意力机制导致训练时间较长，但模型的预测指标更高且训练时间在可接受范围内。

图6 ICP模型验证集Loss

图6 (续)

4 总结

本文提出端到端的深度学习ICP模型实现信息级联预测。在深度学习框架下，首先利用图卷积网络提取级联信息的空间结构特征，再利用双向循环神经网络提取时序特征，然后使用注意力机制耦合空间结构特征和时序特征，最后，在结合级联的时间衰减效应进一步提高模型的预测准确性。本文在两个公开数据集上进行实验，结果表明，本文提出的基于时空注意力的社交网络ICP模型预测精度高于先前的方法。

下一步在空间结构与时序信息相结合的基础上，引入点过程建模，使得模型更具有可解释性，提高模型的预测能力。