鱼和熊掌如何兼得？基于强化学习的多尺度信息传播预测

「论文访谈间」是由 PaperWeekly 和中国中文信息学会社会媒体处理专委会（SMP）联合发起的论文报道栏目，旨在让国内优质论文得到更多关注和认可。

信息传播预测，也称为级联预测，主要研究信息如何在用户之间进行传播，已经在很多实际场景中得到了应用，例如产品推广，流行病学以及新闻和观点的传播。

近期传播预测的工作利用深度学习技术的优势，将信息传播过程建模为基于循环神经网络（RNN）的序列模型，并取得了很好的成果。

但是现有工作要么专注于预测下一个受影响的用户的微观尺度传播预测，要么致力于估算传播过程中受影响用户的总数的宏观尺度传播预测，没能将微观和宏观尺度的预测模型统一起来。

▲ 图1. 宏观尺度的传播预测（左）和微观尺度的传播预测（右）

针对已有研究的局限性，杨成等人提出了一种基于强化学习（RL）的多尺度信息传播预测模型同时进行微观尺度与宏观尺度的预测。具体地，论文通过使用强化学习框架将宏观尺度的监督信号引入微观级联模型，并采用了快速有效的结构上下文提取方法来利用社交网络结构信息。

他们的研究成果 Multi-scale Information Diffusion Prediction with Reinforced Recurrent Networks 发表在 2019 年的 IJCAI 会议上。为了方便大家了解该领域的工作，作者也 整理了一份近年来信息传播预测任务的相关论文列表：

https://github.com/albertyang33/DiffusionPapers

论文标题： Multi-scale Information Diffusion Prediction with Reinforced Recurrent Networks

论文来源： IJCAI 2019

论文链接： https://www.ijcai.org/Proceedings/2019/560

代码链接： https://github.com/albertyang33/FOREST

问题介绍

论文中使用的数据集有 Twitter、Douban 以及 Memetracker。以 Twitter 数据集为例，Twitter 数据集记录了 2010 年 10 月包含有 URL 的推特，其中每个 URL 都是在用户之间传播的信息项。

论文按照时间顺序对转发某个 URL 的用户进行排序，作为该 URL 的级联。数据集除包含有这些级联外还包含有这些用户的社交网络图信息。论文数据集的统计信息如下表所示：

▲ 表1. 数据集统计

下面给出微观与宏观尺度预测的形式化定义：

给定用户集合 V 和级联集合 C，每个级联是按受影响时间排序的用户序列，其中是级联的规模，即对应传播对象影响的用户总数。此外，当信息传播发生在社交网络服务上时，社交网络结构 G=(V,E) 也可以作为传播预测的额外输入。

微观尺度的传播预测旨在给定级联中已经被影响的用户的条件下，预测下一个被影响用户，其中。

宏观尺度的传播预测旨在给定前 k 个被影响用户的条件下，预测级联的最终规模。

模型框架

2.1 微观传播建模

这部分采用带门循环单元 GRU 作为微观尺度建模基础。给定级联序列，GRU 在每一步中，将用户作为输入并计算隐状态。通过采用 GRU 将级联中所有已经被影响的用户的历史信息编码到隐状态中。

如图2所示，除使用 GRU 编码历史信息之外，论文采用基于图神经网络的结构上下文提取方法提取用户的社交网络结构作为额外的用户特征表示。

▲ 图2. 结构上下文提取算法

直觉上讲，所有最近受影响的用户都可能影响下一个用户的预测。论文定义最近受影响的用户为最近 m 个用户，其中 m 是控制这个窗口大小的超参数。然后使用平均池化来聚合用户的结构上下文特征为，并将其与 GRU 隐状态表示拼接，预测下一个受影响用户的概率如下：

微观传播预测的训练目标为最大化所有级联的对数似然：

2.2 宏观传播建模

宏观传播建模的关键在于如何赋予微观级联模型预测宏观级联规模的能力，整个流程如下图所示：

▲ 图3. 宏观尺度信息传播预测框架

为了在步骤 (b) 中使得微观级联模型能够进行级联规模预测，首先在每个级联序列数据末尾添加虚拟用户 < STOP > 并让模型也将其看作普通用户进行预测。

给定前 K 个受影响用户，为了估算整个级联的规模，模型递归地根据预测的概率分布采样一个用户，将其作为下一步的输入并继续预测。一旦采样到 < STOP > 信号，认为该级联的传播停止并统计已经被预测的用户数作为级联的最终规模。

论文采用 Mean Square Log-transformed Error (MSLE) 作为级联规模预测的评价标准。虽然修改后的微观级联模型能够通过模拟预测级联的规模，但是模型缺乏监督信号来引导模型更新获得更好的效果。

因为计算级联规模时的采样操作是不可导的，模型无法后向传播更新参数。为了解决这个问题，模型将模拟过程放入强化学习的框架中并使用 policy gradient 算法更新参数。

GRU 及其隐状态（包括结构上下文）对应强化学习中的 agent 和 state 概念。每一步的 action 是选取下个受影响用户。当 <STOP> 这个特殊的 action 被选中时，将 MSLE 的相反数作为 reward。模型目标是最大化级联的 reward 的期望:

其中 Pr 是选取action序列 seq 的概率，可以被分解为每个 action 的概率的乘积，模型采用 REINFORCE 算法来计算的梯度，最后，参数通过最大化 reward 的期望的梯度上升来更新。

模型实验效果

他们将模型命名为 reinFOrced REcurrent networks with STructural context (FOREST) 。 FOREST 在微观传播预测任务上一致地超过所有基线方法，并在 HITS 和 MAP 指标上取得了超过 10% 的相对提升。

FOREST 在宏观传播预测任务上一致地超过包含最先进的级联规模预测算法 DeepCas 在内的所有基线方法，并在 MSLE 评价指标上取得了 12% 的相对提升。

论文总结

论文提出了一种新颖的多尺度传播预测模型 FOREST ，能够同时进行微观和宏观尺度的传播预测。统一模型在实现微观与宏观尺度联合预测的同时，能够利用训练数据中的更多信息，本质上是一种多任务学习的解决方案。

模型通过强化学习框架赋予了微观传播模型预测宏观性质（即级联规模）的能力，相比于将级联规模预测视为回归问题的现有宏观预测工作，可以额外利用具体受影响的用户序列及其受影响顺序的信息。

此外，论文考虑到当信息通过社交网络服务进行传播时，可以进一步利用社交网络的结构信息帮助预测，因为信息很可能是通过用户间的社交链接传播的。

文中提出了一种结构上下文提取方法来提取用户的社交网络结构信息辅助信息传播预测。下个受影响用户预测和级联规模预测任务上的实验结果证明了方法的有效性。

关于作者

杨成，北京邮电大学计算机系助理教授。 于2014年、2019年获得清华大学学士、博士学位，清华大学计算机科学与技术系优秀博士毕业生。主要研究方向包括图数据挖掘与自然语言处理。在国际顶级学术期刊及会议上发表论文十余篇，Google Scholar 引用超1000次，并担任 ACL、EMNLP、AAAI、IEEE TKDE 等国际会议期刊程序委员会委员和审稿人。

唐建，加拿大蒙特利尔高等商学院&蒙特利尔学习算法研究所（MILA）助理教授。 2014年获北京大学博士学位。曾在密歇根大学和卡内基梅隆大学任博士后和访问学者。主要研究深度图表示学习及其应用。曾获 ICML’14 最佳论文、WWW’16 最佳论文提名。

孙茂松，博士，清华大学计算机科学与技术系教授，博士生导师，清华大学人工智能研究院常务副院长。 2007-2018年任计算机科学与技术系主任、党委书记。主要研究领域为自然语言处理、互联网智能、机器学习、社会计算和计算教育学。国家重点基础研究发展计划（973计划）项目首席科学家，国家社会科学基金重大项目首席专家。在重要国际刊物、国际会议、国内核心刊物上发表论文200余篇，Google Scholar 论文引用数1万余次。

崔淦渠，清华大学计算机科学与技术专业硕士研究生。 2019年获清华大学学士学位。研究方向为网络表示学习和图神经网络。

刘知远，清华大学计算机系副教授、博士生导师。 主要研究方向为表示学习、知识图谱和社会计算。2011年获得清华大学博士学位，已在人工智能领域的著名国际期刊和会议发表相关论文80余篇，Google Scholar统计引用超过7000次。曾获清华大学优秀博士学位论文、中国人工智能学会优秀博士学位论文、清华大学优秀博士后、中文信息学会青年创新奖，入选中国科协青年人才托举工程、中国计算机学会青年学者提升计划，担任 ACL、EMNLP、COLING、IJCNLP 领域主席。