张凤荔，王雪婷，王瑞锦，汤启友，韩英军
(电子科技大学信息与软件工程学院 成都 610054)
如今，Twitter、微博、Facebook、YouTube 和微信等在线社交平台已成为热点事件传播的主要途径。某一事件很快就能在社交网络中通过新闻报道、论坛帖子[1]和视频动态等各种形式被广泛传播。在事件传播过程中，信息级联是很重要的组成部分。信息级联是指博客、电子邮件以及社交网站中识别到的用户级联转发序列与网络关系图[2]。通过对信息级联模型的研究，可以了解信息的传播规律和特性，为事件演化下一步研究提供技术支持。
现今，在信息级联预测领域中，基于特征工程方法的模型只适用于特定场景[3-4]；依赖于假设的点过程 (如泊松过程和霍克斯过程) 的生成式方法的模型无法同时捕获级联图的基础结构和扩散的不确定性[4]；基于深度学习技术的模型，可以对时间序列和静态级联图结构进行建模。但现实生活中，信息级联图的结构是随着时间动态变化的。在建模过程中，考虑级联图的动态变化性，捕获级联图时序及结构特征，对于刻画信息传播过程有重要作用。
本文提出一个基于级联图的动态演化过程的模型。该模型考虑信息传播过程中的不确定性，将图的动态演化过程和自注意力机制相结合，实现对级联图的时序及结构特征的同时捕获；且仅依赖级联图的结构和时序信息，利用深度学习技术以端到端的方式，实现级联的潜在语义捕获。实验在新浪微博和APS 实际数据集上进行，相比传统的级联预测模型，提升了预测的准确性。
信息级联预测方法主要有以下3 类：
1) 基于特征建模的预测方法。特征建模方法基于特征工程，利用经典机器学习技术建模进行级联预测。如文献[5]发现加入与用户相关的特征可以有效地预测用户是否会参与级联；文献[6]验证了在微博数据集中结构特征和时序特征的重要性。这些方法都需要某一特定领域的大量相关特征，具有特殊性，不能够迁移至其他应用场景；且用户个人信息和私有社交平台特征信息具有私密性，难以得到。
2) 基于生成式的预测方法。生成式方法主要从转发到达速率方面入手，对每条消息的到达强度函数独立建模。如文献[7]通过借鉴生存分析的思想来预测在线内容的流行程度；文献[8]提出了一个生成概率模型，用增强泊松过程来预测科学论文的流行程度。文献[9]将级联转换成一组扩散路径，用自激励霍克斯点过程对级联进行建模。此类方法所观测的数据是观测时间窗口内的每个事件的发生，而不是未来要预测的增量流行度。
3) 基于深度学习的预测方法[10]。在深度学习级联预测模型中，节点的嵌入方法对节点表示有着关键性的作用。节点表示的准确性，将直接影响模型预测结果。DeepCas[11]是基于图表示学习的信息级联预测方法，它在借鉴了DeepWalk[12]的基础上，采用随机游走对级联图采样，然后将采样后的级联序列结合注意力机制传入双向门控递归单元 (Bi-GRU) ，最终得到节点的嵌入。基于注意力机制的预测模型，采用GloVe[13]对消息内容进行嵌入，并使用node2vec 对用户图进行编码。基于深度学习的级联预测方法，不需要在级联图上人工标记特征，预测准确性高。
现有的级联模型都是针对拥有固定节点集和边集的静态图。在现实生活中，级联图的本质是动态的，它的结构会随着时间的变化而呈现一个动态演化的过程。这就要求在学习级联图节点表示时，不仅要保留结构上的临近性，还要同时捕获其时序演变特征[1]。文献[14]将自注意力机制应用于动态图表示；文献[15]同时考虑到图的异构性和动态性的特点，通过循环神经网络结合自注意力机制实现节点动态嵌入；文献[16]提出了一种能够捕捉动态图演化的动力学特征方法。上述方法针对的是广泛的动态图，在信息级联领域还没有相关应用。
因此本文提出DySatCas 模型，主要将级联图的动态性定义为一系列的快照子图，融合自注意力机制捕获级联图的结构和时序特征，从而学习到节点的动态表示。
现有M条消息，每条消息转发记录对应一张级联图，如图1 所示，深灰色节点为消息发送者，白色节点为表示观测时间内转发该消息的用户，浅灰色节点为将会新增的转发用户，带箭头实线表示用户间的转发关系，虚线表示将会出现的转发关系。
图1 消息C i的级联图
图2 消息Ci 的级联演化图
融合动态图表示和自注意力机制的级联预测模型DySatCas 如图3 所示。整个模型分为4 个部分，分别是节点嵌入层、结构自注意力层、时序自注意力层、级联增量预测层。以某一级联图Gi及其演变子图为例：
图3 融合动态图表示和自注意力机制的级联预测模型
1) 节点嵌入层：输入级联图Gi和演变子图，本层将采样得到的演变子图分别进行编码，得到节点的向量表示矩阵xv。
2) 结构自注意力层：将节点嵌入层得到的向量矩阵xv输入该层，计算节点以及其邻居节点的注意力权重，并将该节点的邻居节点的特征聚合到该节点，得到该节点新的向量表示。
3) 时序自注意力层：将结构自注意力层输出的节点向量表示和该节点的位置嵌入pj求和后，传入时序自注意力层。该层对每个节点在其历史子图上的状态进行学习，得到每个节点的表示。
2.2.1 节点嵌入层
在级联图Gi的基础上，以相同时间间隔T/N作为标准得到演变级联子图ζi(tN)}。然后将 ζi(tj)(1 ≤j≤N)中的节点嵌入到向量空间{∈RD,∀v∈V},D是节点嵌入的维度，可调整。
2.2.2 结构自注意力层
结构自注意力层的主要作用是通过多层堆叠的自注意力机制对节点及其邻居节点的特征进行学习，将学习到的特征聚合到该节点上，得到对该节点的空间结构特征表示。该层的输入是演变级联子图ζi(tj)中 每个节点的D维向量表示{∈RD,∀v∈V}。通过该层可捕获到节点在级联子图的局部属性，输出为新的可调整的F维向量表示{∈RF,∀v∈V,j∈[1,N]}。
式中，Nv={u∈V:(u,v)∈ε}为 节点v在 图 ζi(tj)中直接邻居的集合；WS∈RF×D是应用于图中每个节点变换的共享权重；a∈R2D是注意力函数的加权向量参数化；‖表示拼接操作；σ(·)是非线性激活函数；是当前图中边 (u,v) 的 权重；αuv是通过softmax函数对在V中每个节点的邻居节点进行归一化操作后的学习参数，表示在当前图中节点u对 于节点v的影响力；同时使用LeakyRELU 非线性激活函数来计算注意力权重，然后用指数线性单元(exponential linear unit, ELU)来激活，并将激活结果作为输出表示。当 αuv为 0 时，节点u和v在图ζi(tj)中是没有连接的，使用稀疏矩阵可以有效的实现其邻居节点所隐藏的自我注意力。
2.2.3 时序自注意力层
时序自注意力层同结构自注意力层类似，采用多个堆叠的时序自注意力模块，充分考虑级联图的动态演化过程，捕捉多个时间段的节点的时序变化。该层的输入是特定节点v在不同时间步长的一系列表示。采用文献[18]所提出的位置嵌入方法，得到节点各子图中绝对时序位置的嵌入序列然后结合结构注意力层的节点v在不同的时间步长下的向量表示得到该层的输入，N是总时间步长。该层输出是。节点的输入及输出分别结合时间步长合并表示为Xv∈RN×F和。节点v在 时间步长j的输入表示为，且用作为该节点时间步长小于j的历史状态的查询。和结构自注意力机制在其邻居节点进行特征学习表示不同，时序自注意力机制更关注每个节点的历史状态。
通过对注意力按比例缩放的点积的形式来计算节点v在时间步长j的输出表示，其中查询、键和值的集合是节点的输入表示。查询、键和值首先分别通过线性投影矩阵Wq∈RF×F′,Wk∈RF×F′和Wv∈RF×F′转换到不同空间。在计算时考虑所有小于j的时间步长，直到时间步长到达j，来保持其自回归性。时序自注意力函数定义为：
式中，βv∈RN×N是通过乘法注意力函数得到的注意力权重矩阵；S∈RN×N是其每个子项Sij∈{−∞,0}拥有强自回归属性的掩码矩阵。为了对时序进行编码，将S定义为：
2.2.4 级联增量预测层
2.3.1 模型训练
该模型的最终目标是对级联增量大小进行预测，采用式(10)作为损失函数来对模型进行优化，在迭代中损失连续10 次不再减小时结束训练：
式中，P是所有消息的总量；Pi是消息Ci的预测级联增量；是实际增量。
2.3.2 算法描述
给定信息级联图Gi，经基于不同时间步的子图算法采样后，得到原始信息级联的子图快照集合ζi(tj)并 得到其对应的序列表示。将得到的序列表示输入到结构自注意力机制层，对每个节点及其邻居结构进行学习，得到。然后将与pj相加输入到时序自注意力机制层得到。最后将各节点融合了动态演化的结构特征和时序特征的向量表示依次通过多层感知机，并输出最终流行度增量预测值Pi。
整个算法流程与图3 模型架构图一致，主要分为节点嵌入、结构自注意力、时序自注意力和级联增量预测4 部分。
算法： DySatCas
输出：级联增量预测值Pi的集合
模型初始化，参数设置
本文主要基于两个实际场景的公开数据集来对所提出模型的有效性进行评估，分别是预测新浪微博的转发量和在数据集APS 上预测论文的引用量，如表1 所示。
表1 实验数据集的详细统计
APS(American physical society)：该数据集包含了美国物理学会的期刊从1893−2009 年所发表的论文及其引用，每一篇论文及其引文都形成了一个引用级联。
和文献[17]相同，使用均方对数误差MSLE 和平均绝对百分比误差MAPE 来对所提出的模型进行评估，具体评估公式为：
3.4.1 基线模型
1) Feature-Linear：基于特征的信息级联预测模型是应用最广泛的。本文基线模型提取如消息发送者/转发者的特征、结构和时间特征，将此类特征输入到线性回归模型和MLP 模型中对信息级联增长量进行预测。
2) DeepCas[11]：将深度学习应用于信息级联预测的模型，级联图采样方式为随机游走，并采用双向GRU 和注意力机制来预测端到端的信息级联增量。
3) Topo-LSTM[19]：使用LSTM 来对图中节点间关系进行建模。根据上一个节点状态，得到下一个节点的预测结果。
4) DeepHawkes[9]：结合了深度学习和自激励过程来进行信息级联预测。
3.4.2 模型评价指标对比
为了检验DySatCas 模型的效果，分别从现在流行的3 类级联预测方法中，选择其中具有代表性的模型来进行比较，具体结果如表2 所示。通过对比有以下发现:
表2 两种数据集下使用MSLE 和MAPE 两种评价指标对不同模型及变体的评估表现
1) DySatCas 的预测效果优于基线。在微博数据集上，观测时间为0.5 h ，MSLE 和MAPE 的结果分别比第一最佳基线 (DeepHawkes) 高出2.5%和3.4%；观测时间为1 h，MSLE 和MAPE 均比其他基线效果好。在数据集APS 上，观测时间为5 年，MSLE 和MAPE 的结果比第一最佳基线分别高出10%和4%，除观测时间3 年，MAPE 略低于DeepHawkes 外，其他数据均优于基线，且随着观测时间增加，预测误差逐渐减少，这表明了DySatCas模型的对级联图的动态演化过程学习的有效性。
2) 从实验结果不难看出，在两个数据集中，基于特征的基线模型的预测效果并不比基于深度学习的基线模型差。在微博数据集中，基于特征的基线模型预测准确性甚至高于传统的基于深度学习的基线模型(DeepCas、Topo-LSTM) 。但该方法极大地依赖于人工提取特征，存在很大的不稳定性和不确定性。并且通过人工的方法，很难提取到较复杂信息中所隐含的特征，适用场景相对固定，推广性差。
3) DeepCas 是基于图表示学习的级联预测模型。其主要使用随机游走的方法对级联图进行采样，但没有考虑信息的实际传播顺序，同时忽略了传播过程中的时序依赖性，使得预测效果较其他深度学习方法较差。这说明了在信息级联预测中，级联图的结构特征和时序特征的重要性。
5) DeepHawkes 模型是一种结合了生成式方法和深度学习的模型。在级联预测过程中，不考虑级联的拓扑信息，依赖于时间序列进行建模，主要关注点在于自我激励机制对级联增量的影响。虽然相比DeepCas 和Topo-LSTM 预测准确性更高，但因为没有考虑级联的结构特征，且忽略了级联的动态性，使得预测效果与DySatCas 相比不够理想。从而说明了在级联预测中，级联图的结构特征、时序特征及其传播过程中的动态过程都是影响预测效果的关键因素。
3.5.1 模型变体
为了更好地了解DySatCas 模型各组成部分对于模型整体预测效果的影响，引入两种变体进行对比。
1) DySatCas-Temporal：在该变体中，忽略时序注意力层，直接将通过结构自注意力层的向量表示输入到多层感知器进行预测。
2) DySatCas-Structural：在该变体中，忽略结构注意力层，直接将通过子图采样后的向量编码输入到时序自注意力层，然后将时序自注意力机层的表示输入到多层感知器中。
从表2 中可以看出：与DySatCas 相比，在观测时间为0.5 h 时，移除结构自注意力层的DySatCas-Structural 和移除时序自注意力层的DySatCas-Temporal 预测误差分别增加了10%和17%，其中移除了时序自注意力层的变体误差更大，说明了级联预测过程中，时序特征对预测效果有更大的影响力，同时也证明了本文模型各组成部分的有效性。
为了验证时间步长在动态图演化过程中的影响，在微博数据集上，分别将时间步长设置为2、3、4、5、6、7、8、9、10、11、12，得到预测结果如图4 所示。由图可知，随着时间步数越长级联预测效果越好，后期误差出现变化不大的原因主要是时间步划分过细，导致后期级联图变化不大，所学习到的节点表示相近。
图4 不同步长性能预测比较
3.5.3 观测窗口
观测时间窗口也是DySatCas 模型中最重要的参数，如图5 所示，在微博数据集和APS 数据集上，分别把观测时间窗口设置为0.5、1、2、3、4 h和3、4、5、6、7、8 年，由实验结果可知观察时间窗口越长，DySatCas 的训练数据越多，从而就能做出更准确的预测。
图5 不同观测窗口在不同数据集上的表现
本文融合动态图学习和自注意力机制，提出了级联预测模型DySatCas。该模型不严重依赖人工标记特征，充分考虑级联传播过程中的动态性和不确定性，根据级联图的结构特征和时序特征来进行级联预测。更好地帮助人们了解信息传播机制和规律，也为后续事件演化研究提供有力的技术支撑。未来考虑结合多任务、多视图等概念，进一步对信息传播特点进行研究。