基于级联时空特征的信息传播预测方法

引用本文

梁少斌, 陈志豪, 魏晶晶, 吴运兵, 廖祥文. 基于级联时空特征的信息传播预测方法. 模式识别与人工智能, 2021,34(11): 969-978
LIANG Shaobin, CHEN Zhihao, WEI Jingjing, WU Yunbing, LIAO Xiangwen. Information Diffusion Prediction Based on Cascade Spatial-Temporal Feature. PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2021,34(11): 969-978. 复制到剪切板

Doi: 10.16451/j.cnki.issn1003-6059.202111001
Permissions

《模式识别与人工智能》编辑部

基于级联时空特征的信息传播预测方法

梁少斌^1,^2,³, 陈志豪^1,^2,³, 魏晶晶⁴, 吴运兵^1,^2,³, 廖祥文^1,^2,^3,⁵

1.福州大学计算机与大数据学院福州 350108

2.福州大学福建省网络计算与智能信息处理重点实验室福州 350108

3.福州大学数字福建金融大数据研究所福州 350108

4.福建江夏学院电子信息科学学院福州 350108

5.鹏城实验室网络空间安全研究中心深圳 518000

通讯作者:

廖祥文,博士,教授,主要研究方向为观点挖掘、情感分析、自然语言处理.E-mail:liaoxw@fzu.edu.cn.

作者简介:

梁少斌,硕士研究生,主要研究方向为在线社交网络分析、自然语言处理.E-mail:n190320015@fzu.edu.cn.

陈志豪,博士研究生,主要研究方向为社交网络信息传播分析、情感分析.E-mail:n180320046@fzu.edu.cn.

魏晶晶,博士,讲师,主要研究方向为观点挖掘.E-mail:weijj@fjjxu.edu.cn.

吴运兵,硕士,副教授,主要研究方向为机器学习、数据挖掘、知识表示.E-mail:wyb5820@fzu.edu.cn.

收稿日期: 2021-05-31 接受日期: 2021-10-08

资助项目: 国家自然科学基金项目(No.61976054)资助

摘要

现有信息传播预测方法对级联序列和拓扑结构独立建模,难以学习级联时序特征和结构特征在嵌入空间的交互表达,造成对信息传播动态演化的刻画不足.因此,文中提出基于级联时空特征的信息传播预测方法.基于社交关系网络和传播路径构建异质图,使用图神经网络学习异质图和社交关系网络节点的结构上下文,引入门控循环单元提取级联时序特征,融合结构上下文和时序特征,构建级联时空特征,进行信息传播的微观预测.在Twitter、Memes数据集上的实验表明,文中方法性能得到一定提升.

关键词: 信息级联; 传播预测; 时空特征; 图神经网络; 循环神经网络

中图分类号:TP391

Information Diffusion Prediction Based on Cascade Spatial-Temporal Feature

LIANG Shaobin^1,^2,³, CHEN Zhihao^1,^2,³, WEI Jingjing⁴, WU Yunbing^1,^2,³, LIAO Xiangwen^1,^2,^3,⁵

1. College of Computer and Data Science, Fuzhou University, Fuzhou 350108

2. Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350108

3. Digital Fujian Institute of Financial Big Data, Fuzhou University, Fuzhou 350108

4. College of Electronics and Information Science, Fujian Jiangxa University, Fuzhou 350108

5. Research Center for Cyberspace Security, Peng Cheng Laboratory, Shenzhen 518000

Corresponding author:
LIAO Xiangwen, Ph. D., professor. His research interests include opinion mining, sentiment analysis and natural language processing.

About Author:
LIANG Shaobin, master student. His research interests include online social network analysis and natural language processing.
CHEN Zhihao, Ph.D. candidate. His research interests include social network information diffusion analysis and sentiment analysis.
WEI Jingjing, Ph.D., lecturer. Her research interests include opinion mining.
WU Yunbing, master, associate professor. His research interests include machine lear-ning, data mining and knowledge representation.

Fund:National Natural Science Foundation of China(No.61976054)

Abstract

The existing information diffusion prediction methods model the cascade sequences and topological structure independently. And thus it is difficult to learn the interactive expression of cascade temporal and structural features in the embedded space, and the portrayal of dynamic evolution of information diffusion is insufficient. Aiming at this problem, an information diffusion prediction method based on cascade spatial-temporal feature is proposed. Based on the social network and diffusion paths, the heterogeneous graphs are constructed. The structural context of nodes of heterogeneous graphs and social network is learned by graph neural network, while the cascade temporal feature is captured by gated recurrent unit. To make microscopic information prediction, the cascade spatial-temporal feature is constructed by fusing structure context and temporal feature. The experimental results on Twitter and Memes datasets demonstrate that the performance of the proposed method is improved to a certain extent.

Key words: Key Words Information Cascade; Diffusion Prediction; Spatial-Temporal Feature; Graph Neural Networks; Recurrent Neural Networks

文章图片

本文责任编委林鸿飞

Recommended by Associate Editor LIN Hongfei

在线社交媒体已成为互联网用户自由发布信息、表达观点及进行网络社交的重要媒介.信息受用户社交行为的影响, 在社交网络上传播并留下一系列轨迹, 这些轨迹被称为信息级联^[1].信息传播预测^[2]旨在利用观测的级联学习信息传播的潜在机制和原理, 预测下一个受影响的用户或级联的最终规模, 被广泛应用在舆情分析、营销推广等领域.本文后文不加区别地使用“ 受影响” 、“ 激活” 等术语表明级联中用户的状态.

近年来, 研究者们围绕信息的传播展开多方面、多维度的系统研究.早期的工作主要是利用传染病模型^{[3, 4]}、时序点过程^{[5, 6]}等方法对信息级联进行建模.这类方法基于对信息传播的先验知识构建符合传播规律的数学模型, 虽然取得一定成果, 但过分依赖对先验知识的假设, 导致复杂网络环境下性能不佳^[7].之后基于深度学习的信息传播模型成为研究热点.例如循环神经网络(Recurrent Neural Networks, RNN)、卷积神经网络(Convolutional Neural Net-works, CNN)等传统图像、文本领域的深度学习方法, 都用于信息级联的建模和预测.图卷积网络(Graph Convolutional Networks, GCN)、图注意力网络(Graph Attention Networks, GAT)及一系列变体专门针对图数据提供建模方法.这类方法以端到端的方式^[8]自动提取级联的内容和结构特征并进行预测, 避免特征设计和传播模型假设强加的先验知识.

目前的信息级联预测主要从宏观和微观两个尺度展开研究.宏观级联预测旨在预测级联的最终规模, 而微观传播预测关注预测下一个激活用户.根据对级联特征刻画的不同侧重点, 可将其划分为基于级联时序特征的预测方法和基于级联拓扑特征的预测方法.

基于级联时序特征的预测方法利用RNN框架重点学习级联的序列特征.Li等^[8]将级联序列类比为文档中的句子, 基于双向门循环单元(Gated Recurrent Unit, GRU)对级联进行编码, 提取级联的时序特征.Cao等^[9]使用深度学习的方法模拟霍克斯(Hawkes)过程, 同时引入非参数化的时间衰减函数, 模拟时间衰减效应.Wang等^[10]提出分层传播注意力网络(Hierarchical Diffusion Attention Network, HiDAN), 在RNN的基础上引入两级注意力, 在用户层级和级联层级分别考虑节点间的依赖关系.由于级联序列的依赖关系并非总是顺序的, Wang等^[7]提出级联序列中的跨越依赖现象, 即级联中的节点激活可能依赖于非直接前任, 引入覆盖机制, 解决注意力分配错误的问题.RNN适合处理序列信息, 可有效学习级联在时间维度的依赖关系, 但难以学习信息传播过程中的拓扑特征.

基于级联拓扑特征的预测方法通过扩展RNN或引入注意力的方法, 兼顾级联的空间结构信息.考虑到级联在传播过程中的拓扑结构, Chen等^[11]引入GCN, 捕获级联的空间结构信息, 并输入RNN进行编码, 预测级联大小.Cao等^[12]将2个图神经网络(Graph Neural Network, GNN)进行堆叠, 分别用于建模激活节点间的交互和影响力在网络中的传播, 更好地学习信息传播过程中的级联效应(Cascading Effect).Wang等^[13]提出拓扑长短期记忆网络(Topology Long Short-Term Memory, Topo-LSTM), 拓展标准的LSTM, 用于学习级联的拓扑特征.Wang等 ^[14]设计结构注意力, 用于提取网络的拓扑特征.Yuan等^[15]提出动态异质图卷积网络(Dynamic Heterogeneous GCN, Dy-HGCN), 采用更擅长学习图数据的图卷积学习结构特征, 构建动态异质图学习信息的传播动态, 然而图卷积对级联的时序性并不敏感, 导致无法有效学习级联的时序特征.

级联预测和传播预测分别从宏观和微观的角度学习信息级联的传播模式并进行预测.近期学者尝试同时从宏观层级和微观层级对级联进行建模, 充分利用彼此的表示信息.Yang等^[16]提出具有结构上下文的强化循环网络(Reinforced Recurrent Net-works with Structural Context, FOREST), 利用级联序列和社交关系图进行传播预测, 并利用强化学习赋予模型预测级联大小的能力.Chen等^[17]提出联合学习的框架, 分别利用GAT和双向LSTM学习级联图及传播序列的表示, 生成共享表示, 分别用于级联预测和传播预测任务.

在真实的社交网络环境中, 信息的传播受用户的社交联系和社交行为共同影响, 在时间和空间上表现特定的时空特征^[18].现有方法大都独立地对级联的时间特征和空间特征进行建模, 造成学习的特征表示缺乏在时间域和空间域中的交互.

针对上述问题, 本文提出基于级联时空特征的信息传播预测方法, 使用RNN和GNN对级联的时空特征进行联合建模.基于异质图卷积学习用户节点在不同网络空间中的上下文依赖关系, 基于GRU捕获级联的序列特征.对社交网络和传播路径构造的异质图进行图卷积, 在学习信息传播拓扑结构的同时也关注用户间社交关系带来的影响, 基于RNN的序列建模进一步使方法捕获级联在时间维度的低维特征表示.

1 问题的形式化描述

如图1所示, 给定一幅社交关系图G=(U, E)及级联集C, 其中U表示用户的集合, 若u_j关注u_i, 则存在一条有向边e_ij∈ E.

	Figure Option View Download New Window
	图1 微观信息传播预测的形式化描述Fig.1 Formal description of microscopic information diffusion prediction

某一消息的级联

c_i={(u_i_k, t_i_k)|u_i_k∈ U, t_i_k∈ [0, +∞ ), k=1, 2, …, L}∈ C,

其中, L表示级联大小, 二元组 ${(u}_{k}^{i}$ , $t_{k}^{i)}$ 表示用户 $u_{k}^{i}$ 在时刻 $t_{k}^{i}$ 分享消息.

微观信息传播预测旨在利用级联集C及社交关系图G训练模型M, 给定级联c, 输出下一时刻产生社交行为的用户u_k₊₁.

2 基于级联时空特征的信息传播预测方法

信息级联的时序性和传播的拓扑结构是目前级联建模方法的研究重点.现有工作利用社交网络和传播路径构造动态异质图, 并基于图卷积的方法更新用户节点表示, 学习级联在不同网络空间中的结构特征和传播依赖.然而图卷积对级联的时序性并不敏感, 故本文提出基于级联时空特征的信息传播预测方法.引入GRU提取级联序列的时序特征.考虑到异质图卷积在提取网络结构特征时可能受到来自不同属性边的噪声影响, 引入GAT提取社交网络的结构特征.融合不同属性网络的结构特征构造级联时空特征, 学习级联不同属性特征在嵌入空间的交互表达.

本文设计的微观信息传播预测方法框架如图2所示.

	Figure Option View Download New Window
	图2 本文方法框图Fig.2 Framework of the proposed method

本文方法主要包含如下几部分.1)基于图注意力的结构特征提取, 利用GAT学习社交节点网络结构感知的向量表示, 并作为级联的初始向量表示.2)基于RNN的时序特征提取, 通过GRU学习级联的时序特征, 捕获信息传播过程在时间维度的上下文依赖关系.3)基于异质图卷积的传播拓扑特征提取, 利用关系图卷积网络(Relational GCN, RGCN)学习信息在网络空间中的传播依赖, 可学习具有多类型边的异质图, 捕获信息传播过程在不同网络空间中的依赖关系.4)基于时间衰减和注意力的依赖关系再分配, 对级联的历史时空特征赋予不同权重, 调整节点间的依赖关系.5)基于级联时空特征的信息传播预测, 将级联时空特征解码为整个用户空间上的激活概率分布, 预测下一个激活用户.

2.1 基于图注意力的社交关系网络特征提取

以关系网络为核心的用户社交是许多在线社交平台的基本形式.具有相同兴趣偏好的用户群体形成一个社交网络, 并通过社交行为促进信息传播.学习社交网络的结构特征有助于解释信息传播和社交网络的潜在联系, 同时为用户节点的向量表示提供更丰富的上下文信息.考虑到用户的邻居节点可能具有不同的社交活跃度, 更合适的做法是赋予不同的注意力权重, 因此本文采用GAT提取社交关系网络的结构特征.

设G为数据集上的一幅社交关系图, 表示为邻接矩阵的形式并输入GAT进行结构特征提取.对于节点i, 首先利用随机初始化的方式得到节点的原始表示向量x_i, 逐个计算i与其邻居j∈ N_i间的注意力得分:

e_ij=a([Wx_i=Wx_j]), (1)

其中, a为单层前馈神经网络, W∈ R^d^×^d为权重矩阵, d为嵌入的维度, =为拼接操作.

再使用softmax函数对节点i在其邻居节点上的注意力得分进行规范化:

α _ij=softmax(e_ij)= $\frac{\exp (LeakyReLU (e_{ij}))}{\sum_{k \in N_{i}} \exp (LeakyReLU (e_{ik}))}$ . (2)

于是, 节点i使用注意力系数加权后的新特征:

x'_i=σ 〔 $\sum_{j \in N_{i}}$ α _ijWx_j〕. (3)

上式为单头注意力的节点特征表达式, 使用多头注意力的节点特征表达式为

x'_i= $\overset{K}{\underset{k = 1}{=}}$ σ 〔 $\sum_{j \in N_{i}} α_{ij}^{k}$ W^kx_j〕, (4)

其中, σ 为激活函数, x'_i∈ R^d为节点i社交网络结构感知的特征向量, d为嵌入维度.该特征向量将作为RNN的输入进一步提取级联的序列特征, 为了便于区分, 记为 $x_{i}^{s}$ .本文通过实验表明, 相比以随机初始化的用户向量作为RNN的输入, 采用网络结构感知的x^s作为RNN的输入具有更好的预测性能.

2.2 基于循环神经网络的级联时序特征提取

图卷积对级联的时序性并不敏感, 而DyHGC-N^[15]摒弃序列模型框架, 提高模型的并行性, 却减弱序列模型对级联时序特征的学习能力.针对上述问题, 本文引入GRU对级联序列进行建模, 纠正图卷积对级联时序性不敏感造成的依赖分配错误, 提高模型对级联时序特征的学习能力.

设模型的输入为级联

c={(u_k, t_k)|u_k∈ U, t_k∈ [0, +∞ ), k=1, 2, …, L}.

利用GAT的输出作为级联的表示向量[ $x_{1}^{s}$ , $x_{2}^{s}$ , …, $x_{L}^{s}$ ], 输入GRU提取级联的序列特征.GRU将每个时刻的用户表示 $x_{k}^{s}$ 作为输入, 计算隐藏状态h_k并输出, 该隐藏状态将作为GRU下一时刻的输入:

h_k=GRU(h_k_-1, $x_{k}^{s}$ ). (5)

GRU利用两个门控制结合当前输入信息与历史信息, 并给出当前时刻的输出, 能在记忆较长级联信息的情况下避免梯度消失的问题.h_k刻画级联当前时刻的时序信息, 可认为是已激活用户{u₁, u₂, …, u_k_-1}在时刻t_k叠加的影响力.

2.3 基于异质图卷积的级联拓扑特征提取

用户的社交关系网络是信息传播的主要载体, 信息在网络中传播的同时表现出一定的结构特征.Yuan等^[15]基于社交网络和传播路径构造的异质图包含不同属性的边, 对异质图进行卷积, 捕获用户节点在不同属性网络中的结构特征, 更好地学习用户的动态选择偏好.

本文遵循DyHGCN的做法, 构造不同时刻的异质图.首先将整个数据集的时间窗口划分为N个等长的时间间隔, 在第i个时间间隔T_i, i=1, 2, …, N, 利用社交关系图和传播图构造异质图邻接矩阵:

$A_{T_{i}}$ =[G, $R_{T_{i}}$ ],

其中, G∈ $R^{|U| \times |U|}$ 为社交关系网络的邻接矩阵, $R_{T_{i}}$ ∈ $R^{|U| \times |U|}$ 为时刻T_i传播图的邻接矩阵, 若用户u_j接收到u_i的消息, 存在一条从u_i指向u_j的边.本文采用RGCN对上述的异质图执行图卷积操作.RGCN将GCN框架应用于具有多边关系的数据建模, 节点的更新方式如下:

$x_{i}^{(l + 1)}$ =σ $\sum_{r \in R} \sum_{j \in N_{i}^{r}}$ 〔 $\frac{1}{c_{i, r}} W_{r}^{(l)} x_{j}^{(l)}$ + $W_{0}^{(l)} x_{i}^{(l)}$ 〕, (6)

其中, $x_{i}^{(l)}$ 为节点i在第l层的特征表示, $N_{i}^{r}$ 为与节点i关系类型为r∈ R的邻居节点, c_i_,_r为可学习或提前设定(如 $|N_{i}^{r}|$ )的正则化常量, W_r、W₀为待学习的权重矩阵, σ 为一个激活函数.

本文方法产生N个用户嵌入矩阵{ $X_{T_{1}}^{r}$ , $X_{T_{2}}^{r}$ , …, $X_{T_{N}}^{r}$ }, $X_{T_{i}}^{r}$ ∈ $R^{|U| \times d}$ , i=1, 2, …, N.相应地, 在时刻t_k用户u_k有N个候选的表示向量{ $u_{T_{1}}^{r}$ , $u_{T_{2}}^{r}$ , …, $u_{T_{N}}^{r}$ }.若t_k∈ [T_i, T_i₊₁), 选择 $u_{T_{i}}^{r}$ 作为用户u_k在级联中的表示 $u_{k}^{r}$ .

考虑到RGCN在提取社交网络结构特征时可能受到不同属性边的噪声干扰, 本文借鉴残差网络的连接形式, 将GAT输出的结构特征x^s与h、u^r进行拼接, 得到级联在时刻t_k的时空特征:

f_k=concat(h_k, $x_{k}^{s}$ , $u_{k}^{r}$ ). (7)

2.4 基于时间衰减效应与注意力的依赖权值再分配

时间衰减描述用户影响力随时间推移而衰减的现象, 文献[12]和文献[15]设计不同的计算方法模拟这种社交现象.对于时刻t_k的用户u_k来说, 同一级联中时刻t_k附近的用户对u_k的影响力应远大于较早时刻的用户.因此, 本文根据时间上的相对位置赋予它们不同的重要性.

对于级联

c={(u_k, t_k)|u_k∈ U, t_k∈ [0, +∞ ), k=1, 2, …, L},

其在各时刻的时空特征为 f_k.不妨认为 f_k为用户{u₁, u₂, …, u_k_-1}在时刻t_k的影响力叠加.为了充分利用历史信息, 根据级联在时间上的相对位置对这些时空特征进行融合.设数据集上的观测时间窗口为[0, T], 划分为l个连续的时间间隔:

{[t₀=0, t₁), [t₁, t₂), …, [t_l_-1, t_l=T)},

并计算每个时刻的相对位置p.当前时刻t_k在时间维度上的相对位置为p_k, 计算过程如下:

p_k=⌊ $\frac{(t_{k} - t_{0})}{「 T / l ⌉}$ 」.

再根据p_k赋予历史时空特征不同的权重并对其加权求和:

f'_k= $\overset{k - 1}{\sum_{i = 1}}$ α _i f_i, k=2, 3, …, L,

其中α _i为对相对位置p进行softmax后的得分.f'_k赋予历史时空特征不同的重要性, 符合用户影响力衰减的规律.

最后, 对得到的级联时空特征F=[f'₁, f'₂, …, f'_k]施加一个带掩码的多头自注意力, 重新调整级联中各个节点的依赖关系:

z_i=Attention( $F W_{i}^{Q}$ , $F W_{i}^{K}$ , $F W_{i}^{V}$ ),

Z=[z_1,z_2,…, z_H]W^O,

其中, $W_{i}^{Q}$ ∈ $R^{3 d \times d_{k}}$ , $W_{i}^{K}$ ∈ $R^{3 d \times d_{k}}$ , $W_{i}^{V}$ ∈ $R^{3 d \times d_{k}}$ , W^O∈ $R^{3 d \times d_{k}}$ 为待学习的权重矩阵, d_k=3d/H, H为注意力的头数, Z∈ R^L^{× 3}^d为最终的级联表示.

2.5 信息传播预测

本文方法最后的部分是一个解码器, 输出为整个用户空间上的激活概率分布, 选择激活概率最大的节点作为下一时刻的激活节点:

$\hat{y}$ =decoder(Z),

其中, $\hat{y}$ ∈ $R^{L \times |U|}$ .模型的优化目标是最小化下面的损失函数:

J(θ )=- $\overset{L}{\sum_{i = 1}} \overset{|U|}{\sum_{j = 1}}$ y_ijlog₂( ${\hat{y}}_{ij}$ )+ $\frac{λ}{2} θ_{2}^{2}$ ,

其中, θ 为模型参数集合, λ 为L₂正则化项的系数, y_ij为用户u_j在时刻t_i的激活状态.若y_ij=1, 表示用户激活, 否则, 表示未激活, ${\hat{y}}_{ij}$ 为预测的激活状态.

2.6 算法步骤

基于级联时空特征的信息传播预测方法的伪代码如算法1所示.首先, 利用GAT从社交关系图提取网络结构感知的用户节点表示X^s.再利用输入级联和社交关系图构造不同时刻的异质图, 使用RGCN学习传播依赖感知的用户节点表示 $X_{T_{i}}^{r}$ .为了弥补图卷积操作对级联时序的不敏感性, 使用GRU提取级联在不同时间步的时序特征h_k, 其中, 级联的初始表示由GAT所得的用户表示[ $x_{1}^{s}$ , $x_{2}^{s}$ , …, $x_{L}^{s}$ ]构成.最后, 利用式(7)融合上述特征, 构造级联的特征表示F=[f₁, …, f_k, …, f_L], 其中, f_k表示级联在时刻t_k的时空特征, 并通过模型训练不断学习级联不同属性特征在嵌入空间的交互表达.

算法 1 基于级联时空特征的信息传播预测算法

输入级联集C={c₁, c₂, …, c_n}, 社交关系图G,

c={(u₁, t₁), (u₂, t₂), …, (u_L, t_L)}

输出每条级联的时空特征F

对于每位用户u_i∈ U, 初始化嵌入表示x_i;

根据式(1)~式(4)更新用户嵌入表示, 得到嵌入矩阵X^s∈ $R^{d \times |U|}$ ;

fori=1∶ N do

构建异质图 $A_{T_{i}}$ ;

根据式(6)更新用户嵌入表示, 得到嵌入矩阵

X $_{T_{i}}^{r}$ ∈ $R^{d \times |U|}$ ;

end for

初始化隐藏状态h₀ , 使用[ $x_{1}^{s}$ , $x_{2}^{s}$ , …, $x_{L}^{s}$ ]作为级联初始表示;

fork=1∶ L do

根据式(5)计算隐藏状态h_k;

根据用户时间戳从{ $X_{T_{1}}^{r}$ , $X_{T_{2}}^{r}$ , …, $X_{T_{N}}^{r}$ }选择用户嵌入表示 $u_{k}^{r}$ ;

根据式(7)生成级联在t_k的时空特征f_k;

end for

return 级联时空特征 F=[f₁, f₂, …, f_L].

3 实验及结果分析

3.1 实验环境

为了验证本文方法的有效性, 在Twitter^[19]、Memes^[20]这2个公开的真实数据集上开展实验.按照8∶ 1∶ 1的比例将级联集C={c₁, c₂, …, c_n}随机划分为训练集、验证集和测试集.

Twitter数据集收集包含特定URL的推文在twitter上的传播事件.每个URL指向一个外部的站点内容, 可认为是一个信息项, 用户通过转发上一个用户的推文传播特定信息.数据集还包含用户节点间的社交关系网络, 用户通过关注形成有向的社交联系.数据集包含12 627个用户节点, 3 442条级联记录, 连接数为30 9637, 平均级联长度为32.60.

Memes数据集记录“ meme” 在新闻网站上的传播情况.“ meme” 意指互联网上的流行文化, 可以是一张表情包, 或是一个网络段子等.每个网站视为一个节点, 若节点出现在级联中的相邻位置, 认为它们存在社交联系.数据集包含4 403个用户节点, 11 987条级联记录, 连接数为2 716 864, 平均级联长度为15.36.本文将级联长度限制在5~500之间, 减小无效级联的影响.

本文选取如下微观级联预测方法进行对比.

1)TopoLSTM^[13].将级联序列建模为不同时刻的传播拓扑图, 并将LSTM扩展为拓扑LSTM, 从而学习拓扑感知的级联特征.

2)DeepDiffuse^[21].基于LSTM和注意力机制对级联序列进行建模, 同时将时间戳信息纳入嵌入表示中, 预测下一时刻受影响的用户及受影响的时刻.

3)FOREST^[16].使用RNN提取级联特征, 同时基于邻居采样提取社交网络的结构上下文, 使用强化学习框架将宏观尺度的监督信号引入微观级联预测, 同时进行级联微观和宏观预测任务.

4)DyHGCN^[15].通过用户间的社交关系网络和不同时刻的传播图构建动态异质图, 再使用GCN进行动态异质图编码, 最后基于注意力的方法并行地学习上下文信息.

本文将信息传播的预测视为一项信息检索任务.因此, 选择hits@k和map@k这2个在微观级联预测中广泛使用的评价指标评价方法.设输入的级联为

c={u_i|u_i∈ U, i=1, 2, …, L},

预测的输出为

{ ${\hat{u}}_{i}$ | ${\hat{u}}_{i}$ ∈ U, i=2, 3, …, L},

则hits@k计算多次检索任务中预测的前k个节点包含实际激活节点的比率:

hits@k= $\frac{1}{L - 1} \overset{L}{\sum_{i = 2}}$ y_i.

其中:若u_i∈ { ${\hat{u}}_{j}$ |j=1, 2, …, k}, y_i=1, 否则y_i=0; ${\hat{u}}_{j}$ 为预测的第i个激活节点.map@k表示计算平均精度均值, 模型预测的相关节点越靠前, 评分越高:

ap@k= $\frac{1}{\min (k, L - 1)}$ ·

$\overset{k}{\sum_{i = 1}} \frac{1}{i}$ c∩ { ${\hat{u}}_{j}$ j=1, 2, …, i}|· idx( ${\hat{u}}_{i}$ ), map@k= $\frac{1}{L - 1} \overset{L - 1}{\sum_{i = 1}}$ @ki,

其中, 若 ${\hat{u}}_{i}$ ∈ c, idx( ${\hat{u}}_{i}$ )=1, 否则idx( ${\hat{u}}_{i}$ )=0.上述指标数值越大, 性能越佳.

为了得到不同时刻的传播图, 将数据集上的整个时间窗口划分为N=8个时间间隔.使用自适应矩估计(Adaptive Moment Estimation, Adam)优化算法更新神经网络参数, 嵌入维度设为64, 初始学习率设为0.001, 批大小设为16.在数据集上进行50轮的训练.

实验中分别使用两层RGCN和具有2个注意力头的GAT学习传播图和社交关系图的特征.在时间衰减模块中, 时间间隔数l=1 000, 最后的多头注意力头数设为12.对于Twitter数据集, 将失活系数设为0.5, L₂正则项权重系数设为0.000 1, 对于Memes数据集, 失活系数设为0.25, L₂正则项权重系数设为0.005.

3.2 实验结果对比

分别在Twitter、Memes数据集上进行实验, 各方法在Twitter、Memes数据集上的实验结果如表2所示.所有评价指标的结果取5次实验的平均值, 并取基准方法中最优结果与本文方法进行标准配对t检验, 以p< 0.001认为方法具有显著性优势, 使用黑体数字标注.

由表1可看出, 相比基准方法, 本文方法在所有评价指标上均取得最优表现.在Twitter数据集上, hits@k指标取得较明显的提升.相比基准方法中最好结果, hits@10提升2.59%, map@100提升0.8%.在Memes数据集上, 相比基准方法中最好结果的FOREST, 本文方法在hits@10, hits@50, hits@100上分别提升1.36%、1.52%和1.56%.上述结果表明, 本文方法不仅能有效预测下一个激活的用户, 同时能将实际激活用户排在相对靠前的位置, 给出更可靠的预测结果.

表1 各方法在2个数据集上的实验结果 Table 1 Experimental results of different methods on 2 datasets %

本文方法性能的提升主要得益于如下两方面.1)GRU的引入在一定程度上改善图卷积对级联时序的不敏感性.图卷积基于目标节点与邻居节点的邻接关系聚合节点特征, 这种更新策略难以学习用户在级联中的先后依赖关系, 导致对级联时序特征的不敏感.本文融合图卷积提取的级联结构特征与GRU学习的时序特征, 进一步基于时间衰减特性调整依赖权重, 增强方法对级联时序的敏感性.2)GAT增强方法对社交网络结构信息的学习能力.将GAT获得的社交网络结构感知的用户嵌入作为级联初始向量表示, 采用残差连接的形式融合社交网络结构特征与级联不同属性特征, 增强方法对网络结构的感知能力.

在基于级联序列特征的模型中, 本文方法在hits@k指标上的提升较明显.由于DeepDiffuse仅对级联序列进行建模, 未考虑信息传播过程中表现的空间结构特征, 总体性能不佳.本文方法采用对级联序列和传播拓扑联合建模的方式, 解决特征单一性的问题.FOREST对用户的网络结构进行邻居采样, 基于强化学习对预测性能进行优化, 性能优于仅考虑序列特征的方法.

在考虑级联结构特征的方法中, 本文方法在map@10和hits@10指标上提升较明显.虽然TopoLSTM也同时考虑级联的时序和拓扑特征, 但仅对单个级联样本的拓扑结构进行建模, 未能充分利用不同级联序列间的动态交互信息, 性能的提升有限, 训练时间较长.本文方法利用传播路径(级联序列)构建全局的动态传播图, 纳入社交网络的结构信息, 更好地学习信息传播的动态演化过程.DyHGCN同样采用基于动态异质图的学习方法, 能学习用户的动态偏好, 但欠缺对级联序列特征的考虑, 导致信息传播在时间域的动态刻画不足.相对而言, 本文方法考虑级联特征在时间域和空间域的交互表达, 更好地对信息的传播过程进行动态建模, 提升总体预测性能.

3.3 消融实验结果

为了探究方法各部件对实验结果的影响, 单独移除方法中的部件进行实验.实验包括去除多头自注意力模块(图中简记为-attention)、去除时间衰减效应(简记为-time decay)、去除社交关系网络(简记为-social network)、去除异质图(简记为-RGCN)、去除门控循环单元(简记为-GRU).实验结果如图3所示.

	Figure Option View Download New Window
	图3 本文方法各部件的消融实验结果Fig.3 Ablation experiment results of components of the proposed

消融实验结果验证本文RNN和GNN提取的级联时空特征的有效性.由图3可知:当移除社交关系网络后, 方法在2个数据集上的评价指标均有所下降, 表明用户间的社交联系对信息的传播存在影响; 时间衰减效应和GRU模块在Twitter数据集上具有更明显的作用, 这是因为信息在twitter这样的即时社交媒体上的传播过程表现出更显著的时序特征.引入RGCN网络后, 本文方法能学习信息在空间上的传播拓扑结构, 为节点的表示向量带来更丰富的上下文依赖信息.多头自注意力模块重新调整级联各个节点的依赖关系, 为方法带来更优的预测性能.综合来看, 本文方法的各部件都对实验结果具有重要作用.

3.4 参数分析

为了探究注意力头数对实验结果的影响, 本文尝试使用不同的注意力头数进行实验.级联的自注意力可理解为对级联中的各个节点计算其与前序节点的注意力权重, 从而捕获节点间的依赖关系.为了探究注意力头数对预测性能的影响, 选择不同的注意力头数进行实验, 实验结果如图4所示.

	Figure Option View Download New Window
	图4 注意力头数对map@k和hits@k指标值的影响.Fig.4 Influence of the number of attention heads on the metrics of map@k and hits@k

由图4可看到, 随着注意力头数的增加, map@k指标呈现先降低后上升的趋势, 在注意力头数为12时取得最优效果, 在注意力头数超过12时, map@k指标开始下降.hits@k指标随着注意力头数的增加而缓慢提升, 在注意力头数为12时趋于稳定.这是由于多头自注意力可在不同的表示子空间上考虑节点间的依赖信息, 重新调整节点间的依赖关系.随着注意力头数的增加, 将耗费更多的计算资源, 故选择注意力头数为12.

4 结束语

本文提出基于级联时空特征的信息传播预测方法.利用社交关系图和信息传播路径构建不同时刻的异质图, 并使用异质图卷积学习网络节点结构感知的依赖上下文, 能捕获级联传播过程中的拓扑特征.为了让方法在表征信息传播结构特征的同时也能刻画级联的序列特性, 引入GRU学习级联的时序特征, 融合级联时序特征和空间结构特征, 构建级联时空特征, 让方法具备刻画信息传播动态演化过程的能力.本文方法在两个公开数据集上均取得较优综合表现, 具有统计学上的显著性优势.今后将考虑引入多任务学习框架, 通过多任务训练共享表示空间, 增强节点向量表达能力.

参考文献

文献选项

[1]	廖祥文, 郑候东, 刘盛华, 等. 基于用户行为的情感影响力和易感性学习. 计算机学报, 2017, 40(4): 955-969. (LIAO X W, ZHENG H D, LIU S H, et al. Learning Influences and Susceptibilities for Sentiments from Users' Behaviors. Chinese Journal of Computers, 2017, 40(4): 955-969. ) [本文引用:]
[2]	YANG Y, TANG J, LEUNG C W, et al. Rain: Social Role-Aware Information Diffusion // Proc of the 29th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2015: 367-373. [本文引用:]
[3]	WOO J, CHEN H. An Event-Driven Sir Model for Topic Diffusion in Web Forums // Proc of the IEEE International Conference on Intelligence and Security Informatics. Washington, USA: IEEE, 2012: 108-113. [本文引用:]
[4]	WOO J, SON J, CHEN H. An Sir Model for Violent Topic Diffusion in Social Media // Proc of the IEEE International Conference on Intelligence and Security Informatics. Washington, USA: IEEE, 2011: 15-19. [本文引用:]
[5]	MISHRA S, RIZOIU M A, XIE L X. Feature Driven and Point Process Approaches for Popularity Prediction // Proc of the 25th ACM International Conference on Information and Knowledge Ma-nagement. New York, USA: ACM, 2016: 1069-1078. [本文引用:]
[6]	ZHAO Q Y, ERDOGDU M A, HE H Y, et al. SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity // Proc of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2015: 1513-1522. [本文引用:]
[7]	WANG Y Q, SHEN H W, LIU S H, et al. Cascade Dynamics Mo-deling with Attention-Based Recurrent Neural Network // Proc of the 26th International Joint Conference on Artificial Intelligence. New York, USA: ACM, 2017: 2985-2991. [本文引用:]
[8]	LI C, MA J Q, GUO X X, et al. Deepcas: An End-to-End Predictor of Information Cascades // Proc of the 26th International Confe-rence on World Wide Web. New York, USA: ACM, 2017: 577-586. [本文引用:]
[9]	CAO Q, SHEN H W, CEN K T, et al. DeepHawkes: Bridging the Gap between Prediction and Understand ing of Information Cascades // Proc of the ACM Conference on Information and Knowledge Ma-nagement. New York, USA: ACM, 2017: 1149-1158. [本文引用:]
[10]	WANG Z T, LI W J. Hierarchical Diffusion Attention Network // Proc of the 28th International Joint Conference on Artificial Intelligence. New York, USA: ACM, 2019: 3828-3834. [本文引用:]
[11]	CHEN X Q, ZHOU F, ZHANG K P, et al. Information Diffusion Prediction via Recurrent Cascades Convolution // Proc of the 35th IEEE International Conference on Data Engineering. Washington, USA: IEEE, 2019: 770-781. [本文引用:]
[12]	CAO Q, SHEN H W, GAO J H, et al. Popularity Prediction on Social Platforms with Coupled Graph Neural Networks // Proc of the 13th International Conference on Web Search and Data Mining. New York, USA: ACM, 2020: 70-78. [本文引用:]
[13]	WANG J, ZHENG V W, LIU Z M, et al. Topological Recurrent Neural Network for Diffusion Prediction // Proc of the IEEE International Conference on Data Mining. Washington, USA: IEEE, 2017: 475-484. [本文引用:]
[14]	WANG Z T, CHEN C Y, LI W J. A Sequential Neural Information Diffusion Model with Structure Attention // Proc of the 27th ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2018: 1795-1798. [本文引用:]
[15]	YUAN C Y, LI J C, ZHOU W, et al. DyHGCN: A Dynamic He-terogeneous Graph Convolutional Network to Learn Users' Dynamic Preferences for Information Diffusion Prediction // Proc of the Joint European Conference on Machine Learning and Knowledge Disco-very in Databases. Berlin, Germany: Springer, 2020: 347-363. [本文引用:]
[16]	YANG C, TANG J, SUN M S, et al. Multi-scale Information Di-ffusion Prediction with Reinforced Recurrent Networks // Proc of the 28th International Joint Conference on Artificial Intelligence. New York, USA: ACM, 2019: 4033-4039. [本文引用:]
[17]	CHEN X, ZHANG K P, ZHOU F, et al. Information Cascades Modeling via Deep Multi-task Learning // Proc of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM, 2019: 885-888. [本文引用:]
[18]	CUI B R, YANG S J, HOMAN C. Non-independent Cascade Formation: Temporal and Spatial Effects // Proc of the 23rd ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2014: 1923-1926. [本文引用:]
[19]	HODAS N O, LERMAN K. The Simple Rules of Social Contagion. Scientific Reports, 2014, 4(1). DOI: DOI:10.1038/srep04343. [本文引用:]
[20]	LESKOVEC J, BACKSTROM L, KLEINBERG J. Meme-Tracking and the Dynamics of the News Cycle // Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2009: 497-506. [本文引用:]
[21]	ISLAM M R, MUTHIAH S, ADHIKARI B, et al. DeepDiffuse: Predicting the 'Who' and 'When' in Cascades // Proc of the IEEE International Conference on Data Mining. Washington, USA: IEEE, 2018: 1055-1060. [本文引用:]