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

「论文访谈间」是由 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 是选取下个受影响用户。 当 这个特殊的  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 ，能够同时进行微观和宏观 尺度的传播预测。 统一模型在实现微观与宏观尺度联合预测的同时，能够利用训练数据中的更多信息，本质上是一种多任务学习的解决方案。

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

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

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

点击以下标题查看更多往期内容：

• 变分推断（Variational Inference）最新进展简述

• 变分自编码器VAE：原来是这么一回事

• 图神经网络三剑客：GCN、GAT与GraphSAGE

• 如何快速理解马尔科夫链蒙特卡洛法？

• 深度学习预训练模型可解释性概览

• ICLR 2020：从去噪自编码器到生成模型

:mag:

现在，在 「知乎」 也能找到我们了

进入知乎首页搜索 「PaperWeekly」

点击 「关注」 订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击 「交流群」 ，小助手将把你带入 PaperWeekly 的交流群里。