基于关系强度理论与反馈机制的信息传播动态网络表示

潘乐，李弼程，万旺，曾荣燊

（华侨大学 计算机科学与技术学院，福建 厦门 361021）

0 概述

互联网的迅速发展及移动设备的快速更新换代助推了在线社交网络的发展，极大拓宽了人们获取消息、传播信息的渠道，传播主体的下沉使每个人都能成为信息传播的主体。然而个体意见通过社交网络汇聚成集体意见，民意的自由表达若被有心人利用，将引发社会舆论。因此，社交网络信息传播的研究是必要的。

近年来，深度学习技术在众多领域的不同任务中均展现了较为优异的性能。在信息传播领域，利用深度学习技术处理信息传播预测任务有一套较为通用的流程：首先，将社交网络用户节点与连边进行网络表示学习（Network Representation Learning，NRL）［1］，将网络结构数据表示为低维稠密向量；然后，将低维稠密向量的网络节点作为输入进行各类信息传播预测任务。BOURIGAULT等［2］利用现有扩散级联进行信息传播的表示学习；LI等［3］利用表示学习进行信息扩散概率预测。要提升信息传播预测的性能，合适、高效的NRL 方法显得尤为重要。

随着微博、知乎等开放型即时信息交流平台的发展，信息传播不再局限于好友关系之间，更多的是陌生人间出于对某个言论的赞同而进行的转发操作。在信息传播网络中，关联可以表示为一个人与另一个人存在好友或关注关系，而信息传播可以发生在两个好友之间的消息交流（存在关联边）或陌生人之间的信息转发（不存在关联边）。区分并同时考虑这两种传播情形才能更好、更完整地描述节点之间的信息传播。

为增强信息传播网络动态表示的有效性和效率，本文基于社交网络关系强度理论和信息反馈机制，提出动态网络表示（Dynamic Network Representation，DNRep）模型。将信息传播动态网络划分为传播网络（弱关系网络）和关系网络（强关系网络），使用强关系变化辅助影响弱关系交互，以动态变化驱动网络，并用归纳式的方法从两个子网络的相互驱动中得到网络表示。此外，引入反馈机制，在节点聚合更新信息之后将信息反馈到邻域，提高动态网络表示的效率。

1 相关工作

1.1 静态网络表示

静态网络表示方法早期大多基于谱聚类［4-5］，但这类方法的时间和空间复杂度较高，无法满足日益增长的网络规模的需求。随着网络表示学习的发展，许多新的表示学习模型被提出。DeepWalk［1］将网络嵌入问题描述为一个序列建模问题，通过随机游走的方式生成节点序列，并使用Skip-Gram 学习节点表示。基于DeepWalk 模型，Node2vec［6］集成了深度优先搜索和广度优先搜索策略，能更灵活地挖掘网络结构信息。结合外部信息的方法有TADW［7］、CANE［8］、MMDW［9］。以上静态网络表示学习方法尝试解决目前网络空间大规模性、高维性难题，然而真实世界的互动系统是动态的，其连边、节点都随时间不断变化。这些时间特性是动态网络的重要体现，也反映了网络演化的机制。因此，在信息传播领域的研究中静态网络表示学习并不适用。

1.2 动态网络表示

关于动态网络的研究相对较少，且大多数研究局限于表示为图的快照序列的离散时间动态图［9-11］，通过忽略时间演化特性将静态网络深度学习模型应用于动态网络中，但这并非最优方案，且这些方法对于每一个时间片都需要进行重新训练，时间成本巨大。此外，这些方法虽然能够展现网络在不同时刻的变化特征，但缺乏对网络动态变化本质属性的挖掘，对现实网络的高度动态性建模不够［12］。

近期，有学者提出几种支持连续时间的动态网络表示学习方法。XIONG等［13］提出DynGraphGAN模型，利用生成对抗网络（Generative Adversarial Networks，GAN）捕获因节点或边的变化而导致的网络局部结构的变化。Dyngraph2vec［14］使用长短期记忆（Long Short-Term Memory，LSTM）网络模型捕获节点的变化特征，包括每个时刻节点间的非线性交互结构特征和节点多个时刻间的变化特征。DyRep［15］模型将网络中的演变划分为关联演变和社交演变，运用注意力机制聚合节点变化，从而对网络结构产生影响。

对于社交网络中的信息传播而言，动态网络表示学习依旧存在如下2 个挑战：

1）结合传播学理论建立更贴合真实世界的有效网络表示。本文在进一步分析社交网络中的信息传播时发现，在信息传播网络中普遍存在着区别于社交强关系的弱关系（即存在非好友关系的用户形成了信息传播关联）。强弱关系假设是社会学与传播学中一个很重要的理论，FRIEDKIN等［16］认为弱关系在信息流传播过程中起推动和“桥梁”的作用，连接了不同的关系群体。而在现今开放社交网络蓬勃发展的情景下，弱关系的存在可使信息传播得更快、更广，因此弱关系的存在是不可忽视的。

如图1 所示为信息传播动态网络示意图，可以看到在社交网络中存在用户之间单向或双向的关注形成的强关系，同时，更普遍存在着关系疏远、互动频率较低，但在信息的传播中发挥一定作用的弱关系。此外，在信息传播过程中，也会有新节点的加入以及新关系的形成。

2）及时捕获网络动态演化信息。自然观察到的关联以及之间的交互行为存在动力学关系，但目前没有方法能够对它们进行联合建模，进而通过动态图进行表示学习。此外，当前大部分算法都是直推式的，即针对特定领域或特定网络结构生成固定节点嵌入，而当网络结构或信息发生改变时，直推式表示学习模型就需要进行重新训练，相较之下归纳式学习的方法更适用于网络变化。然而大多数归纳式学习的方法仅采用聚合的方式生成节点表示，对于信息传播网络容易造成延迟，导致下游机器学习任务的性能受到影响。

为解决以上2 个问题，本文受DyRep［15］模型的启发，结合社会传播学中的关系强度等相关理论，加入信息反馈机制，建立更适用于社交网络信息传播扩散分析的动态网络表示模型DNRep，用以对信息传播网络进行动态网络表示，解决现有方法不能很好地反映真实传播网络、忽略信息传播中的动力学特征等问题。

2 DNRep 模型

2.1 相关定义

人与人之间的关系有强弱之分，美国的社会学家KEUCHENIUS［17］认为划分人际关系的主要标准是双方互动和情感维系的强弱，其中互动较多且双方关系比较紧密的是强关系，而互动较少且没有较强情感维系的就是弱关系。文献［18］将此种关系强度理论引入到社交网络的划分中，可以认为用户间已建立的关系网络就是一种强关系，信息能够轻易地在强关系网络中传播。而由用户间的信息交流构成的传播网络则可以认定为弱关系，只在某一时刻针对特定事件或特定信息产生互动，是一种临时性的短期关系。

基于以上理论，本文定义t时刻的传播动态网络：

其中：Vt为节点集合；et表示边的集合。在时间窗口[0，t]中网络变化的集合定义如式（2）所示：

其中：u，v表示发生变化的2 个节点；t表示时刻；k作为一个标记，k=0 代表网络拓扑结构演变（即关系网络的变化），k=1 代表“固定”网络拓扑结构上的交互活动（即传播网络的变化）。在信息传播网络中t时刻发生的变化也可简化描述为ti，k，k∈{0，1}。

本文定义Ei∈Rd为节点i的d维表示，而节点表示随时间的推移而变化，因此本文将其定义为关于时间的函数Ev(t)。

2.2 模型框架

在建立DNRep 模型时，本文结合了传播学中的关系强度理论，将信息传播动态网络划分为关系网络（强关系）和传播网络（弱关系）。考虑到在信息传播过程中，关系网络和传播网络都在不断变化，而两者是共存的，且变化相互影响，形成传播动力学演化机制，因此将表示学习过程作为2 个网络的中介过程，将2 个网络的变化过程联系起来，从而驱动2 个网络演变，并使节点表示随时间动态演化。DNRep模型的整体框架如图2 所示。

图2 DNRep 模型的整体框架Fig.2 Overall frame of DNRep model

图2 中关系网络的连边表示用户之间的关注、好友等强关系的建立，一旦连接会造成长期性的路径变化，导致当前网络拓扑结构的改变。网络中节和边的增加是关系网络演变的过程，在舆论事件发生时，往往伴随着大量节点的增加，网络拓扑结构会不断改变，而在关系网络中两节点间如果存在关注或好友关系，事件信息就会沿着这条路径传播，且这种传播路径是长期存在的。

传播网络只表示了当前网络中已有节点之间的传播行为，没有考虑引入新的节点和新的关系连边情况，并且这种传播行为是临时性的短期关系，属于弱关系，这更贴合真实世界舆情事件发生时的传播情况。

关系网络与传播网络相互演化，两者的变化更新了网络表示，同时网络表示的更新通过反馈机制将当前时刻的变化信息实时反馈至两个网络，保证了网络表示的及时性。

2.3 网络节点表示

在信息传播网络中影响节点表示变化的因素主要有3 个：

1）用户节点间建立新的关系（强关系或弱关系），信息从一个邻域传播到另一个邻域；

2）节点自身过去变化带来的影响（如时间衰减）；

3）外部因素影响。因此节点更新的表示可以描述为式（3）所示：

其中：Ev(t)为节点v在t时刻的节点表示；Ms(t-1)表示t-1 时刻用户节点邻域间的影响，即提取、聚合了网络结构信息并反馈了变化信息；(t-1)是关于节点v的邻居节点u的信息表示向量，其中包含注意力机制；Mr Ev(t-1)表示自身历史变化带来的影响；Ev(t-1)是节点v过去表示的周期性状态；Mt(τ-τt-1)表示外部环境的影响，如与该节点相关的两次网络拓扑结构的变化之间会产生外部影响；τ表示时间点；Ms、Mr、Mt为可学习参数。

对于式（3），(t-1)为输出的表示向量，包含节点注意力的更新、节点信息的聚合和变化信息的反馈，且邻域带来的变化对节点更新的表示影响最大，是本文重点研究和改进的部分。

2.4 节点邻域信息更新

信息传播网络中用户节点的变化大致可以分为3 类：

1）该时刻节点间只形成弱关系；

2）节点间已存在关注、好友等强关系，该时刻发生了如转发等的弱关系交互行为；

3）该时刻节点间既形成了强关系也形成了弱关系。

以第3类，即关联网络与传播网络同时发生变化为例，DNRep模型更新节点表示的流程图如图3所示。

图3 DNRep 模型更新节点表示的流程Fig.3 Procedure of update node representation of DNRep model

图3 展示了在t时刻，节点2 与节点4 之间发生关联（强关系）与传播（弱关系）行为，由于关系网络与传播网络同时发生变化，因此需要更新相关节点的邻接矩阵与注意力权重，同时聚合节点信息并反馈节点变化信息，最后结合自相关项与时间项更新节点表示。

由于节点间的变化可能有3 类不同的情况发生，因此对于节点邻域信息的更新，本文对3 类情况分别进行讨论。

1）节点i与节点j在t-1 时刻无关联，t时刻发生i到j的传播行为。

此时由于仅形成弱关系，因此节点的注意力关系强度矩阵S不变，即：

2）节点i与节点j在t-1 时刻已存在关联，t时刻发生i到j的传播行为。

为了度量节点对的关系强度，引入概率密度λ。考虑λ需要满足计算结果为正值的条件下还需要区分关联网络与传播网络，本文利用Softplus 函数作为外部函数，概率密度λ的计算式如式（5）所示：

其中：ψk是可学习的标量时间尺度参数，表示对应网络发生变化的速率；mk∈R2d为学习时间尺度特定兼容性的模型参数；[·∥·]为聚合过程，表示2 个节点上一时刻节点表示的聚合。

所以λ时刻节点的注意力关系强度矩阵S的计算式如式（6）所示：

其中：Ni(t)表示节点i的邻居节点个数。

3）节点与节点j无关联，t时刻同时发生关联以及从i到j的传播行为。

由于在t时刻产生关联，所以节点i与节点j的邻接矩阵更新为Ai，j(t)=1。关联行为产生的网络拓扑结构的改变也使得节点i邻域注意力权重发生改变，同时在t时刻传播网络也发生了变化，因此节点i与邻居节点的注意力关系强度矩阵S的计算式为式（7）所示：

其中：Ui表示节点i所有邻居节点的集合。新产生关联的节点i与节点j的注意力关系强度矩阵S的计算方式见式（6）。

2.5 节点信息聚合与反馈

如图4 所示，在局部传播部分，模型捕获了节点丰富的邻域结构信息，下一步需要进行节点信息的聚合。目前信息聚合常用的方法有均值聚合、pooling 或者使用LSTM 框架等，但这些方法普遍存在忽略节点重要性或复杂度过高的缺点。

本文将注意力机制应用到动态模型中来度量各个节点的权重，考虑了网络动态变化对注意力的影响，并利用Softmax 函数将聚合信息以向量形式输出，因此节点i邻域信息聚合的输出向量(t) 的计算式如式（8）所示：

其中：Si，r(t)表示节点i与邻域的注意力关系强度矩阵；Er(t-1)表示节点i的邻居节点t-1 时刻的节点表示；Mh与bh为可学习的、控制信息传播的参数；Ui(t)表示节点i的邻居节点集合。

在式（3）中，由于Ej(t-1)为自相关项，(τ-τt-1)为时间相关项，两者均可通过直接计算得到，因此可以根据式（3）计算得到i时刻的节点表示Ei(t-1)。

为提高网络更新的速度，本文引入反馈机制，将节点i的信息反馈到其邻居节点。在发生动态变化的节点i更新了节点表示后，节点i向邻域反馈了自身变化信息，邻居节点的表示Er(t)的更新公式如式（9）所示：

其中：Er(t-1)为t-1 时刻节点i的邻居节点表示；Md为可学习向量；(Ei(t)-Ei(t-1))表示节点i的变化信息；Ui(t-1)表示t-1 时刻节点i的邻居节点的集合。

2.6 模型训练

模型采用无监督的学习方式，整个模型待学习的参数空间Ω表达式如式（10）所示：

模型的训练过程通过最小化负对数似然实现，对于一个在时间窗口[0，T]上产生了n次变化的集合O，损失函数L的定义如式（11）所示：

其中：n≠0；λ为节点对关系强度的概率密度函数；等式右边最后一项表示总的残存概率。

3 实验结果与分析

为评估DNRep 模型学习到的节点表示，将其应用于动态网络的链接预测任务。

3.1 实验数据集

为更好地评估模型的性能，提高模型的可比性，本文选用前人工作所使用的数据集，包括Social Evolution 数据集和Github 数据集。

Social Evolution 数据集［19］是麻省理工学院人类动力学实验室利用手机应用程序，收集了参与实验的83 名师生在2008 年10 月—2009 年5 月期间的社会关系、政治观点、通信等记录。该数据集包含了超过200 万个事件（包括信息传播事件与关系建立事件）。本文将观点交换等信息传播事件作为模型的传播网络，将师生间的亲密朋友关系作为模型的关系网络。由于相邻间隔记录的数量太大并且包含大量噪声，因此本文采用与DyRep 模型［15］相同的方式对该数据集进行预处理，根据相邻间隔记录发生的概率进行过滤。

Github 数据集［20］根据时间轴记录了开发人员编写代码、提交文档、访问、收藏等内容，数据集每小时更新一次。本文选取了自2012年12月28日—2013年12 月31 日的数据。本文将开发人员间的关注、收藏等行为构成的网络作为模型的关系网络，将文档的访问、提交等行为构成的网络作为模型的传播网络。采用与LDG 模型［21］相似的预处理方法后，得到的数据集统计如表 1 所示。

表1 数据集信息 Table 1 Dataset information

3.2 评价指标与参数设置

链接预测就是预测下一时刻可能产生交互关联的用户。由于存在大量潜在的目标用户，因此精确地预测下一个用户通常是不现实的，但是可以预测一个用户候选集。预测下一个可能转发信息的用户可以被视为一个检索问题，将所有下一时刻可能产生链接的用户进行排序，采用排名指标作为评价标准。参照现有的信息传播扩散研究［15，21-22］，选择前10 命中率（HITS@10）和平均排名（MAR）作为评价指标。

HITS@10：在预测任务时对于给定元组，计算其与其他节点的条件密度，并对它们进行排名，再与下一时刻进行对比，测试节点出现在前10 名的次数比例。HITS@10 值越高表示实验评价结果越好。

MAR：测试元组的平均排名。MAR 越小则实验评价结果越好。

实验的超参数设置：训练的batch_size=200，dropout=0，隐藏层的神经元个数d=32。本文使用Adam 优化器［23］来训练模型，学习率为0.000 2，每个模型运行10 次取平均结果。

3.3 性能比较

为更好地对比模型性能，本文选择7 种具有代表性的模型作为对比模型，具体如下：

1）Node2vec 模型［6］，指利用网络中存在类似结构特征（即社区结构）的特点而设计的一种既保持节点邻居信息又能体现网络信息的易训练网络嵌入模型，其基本思想和DeepWalk 类似，也是生成随机游走，对随机游走进行采样得到网络节点表示。

2）DynGEM 模型［10］，一种动态网络表示学习模型，使用深度自编码器对动态图的快照进行编码，将时间线划分为离散的时间点，并保留结构，学习在这些时间点上的图形快照嵌入。

3）GraphSage 模型［24］，一种归纳式表示学习模型，采样图中每个节点的邻居结构信息，再通过聚合函数聚合采样信息，从而得到图中各个顶点的向量表示。

4）GAT模型［25］，在GraphSage 模型的基础上对邻域采用多头非均匀注意力机制。

5）Know-Evolve 模型［26］，是将时间点过程引入动态图表示学习的先驱，模型结合动态时间点过程和深度神经网络框架，考虑了知识随时间的进化以及实体在多元关系中复杂的交互过程，通过参数化条件强度函数和关系得分将知识图中事件的发生建模为多维点过程。

6）DyRep 模型［15］，将图结构的变化分为2 种过程，引入聚合机制并结合注意力机制，通过训练对应的参数得到相关节点表示，且这种表示是可以动态变化的。本文所设计模型是基于DyRep 模型进行改进的。

7）LDG 模型［21］，使用神经关系推理模型推理图中的事件类型，可以同时考虑2 种以上类型的边，将DyRep 模型拓展为研究多关系图，同时还加入双线性编码层，用以捕获不同节点间更深层次的交互。

对于Social Evolution数据集，本文对2008年1月—2008 年9 月10 日间的数据进行初始化，将2008 年9 月11 日—2009 年4 月的数据作为训练集，将2009 年5 月及之后的数据用作测试集。对于Github 数据集，本文使用2013 年之前的数据初始化网络，将2013 年1 月1 日—2013 年9 月30 日的事件作为训练集，将2013 年10 月1 日—2013 年12 月31 日的数据作为测试集。将本文模型与Node2vec、DyGem、GraphSage、GAT 这4 种基于时间快照离散网络的动态网络表示模型在两个数据集下分别进行链接预测任务，实验结果如图4、图5 及表2 所示，其中图4 表示Hits@10指标的对比结果，图5 表示MAR 指标的对比结果。在表2中，性能最优的实验结果用粗体标注，次优的用下划线标注。

图4 不同模型的Hits@10 指标结果对比Fig.4 Comparison of Hits@10 indicator results of different models

图5 不同模型的MAR 指标对比结果Fig.5 Comparison of MAR indicator results of different models

表2 不同模型的实验结果对比 Table 2 Comparison of experimental results of different models

Node2vec、DynGEM、GraphSage、GAT 这4 种表示模型在处理动态图时的主要思路都是将动态图切分成离散的快照图，然后对当前时刻的快照图进行静态网络表示。然而真实世界的信息传播网络是动态的，且变化发生的时间分布不均匀，在连续的时间序列中静态网络表示性能受到极大影响。由图4、图5 及表2 可知，这4 种模型在真实世界动态网络数据集上的预测任务中效果并不好。

由图4和图5可知，在Social Evolution 数据集下，4 种模型中性能最优的是GraphSage 模型，HITS@10 和MAR 值分别为0.12 和37.0。在数据量较大、节点分布较稀疏的Github 数据集下，GAT 模型由于引入了多头非均匀注意力机制，所以处理稀疏数据的性能在四者中较优，HITS@10 和MAR 值分别为0.21 和107.1。而较为经典的Node2vec 模型由于通过随机游走对结果进行采样，结合社区结构等特征生成节点表示，因此在处理数据规模大、节点稀疏的Github 数据集时的效果并不好，MAR 值为139.4（随机预测的MAR 值约为140）。本文模型是一种处理连续时间网络的动态网络表示模型，在连续变化的动态网络中有较优异的性能，实验证明本文模型明显优于以上4 种模型。

针对图4、图5 及表2 的实验结果，将本文模型与其他基线模型做对比，作出如下分析。

1）与Know-Evolve 模型对比

Know-Evolve 模型主要适用于知识图谱的表示学习，对于真实世界动态网络数据集的表示效果有限，在Social Evolution 数据集下的HITS@10 和MAR值分别为0.25 和30.0，在Github 数据集下的HITS@10 和MAR 值分别为0.17 和109.8。Know-Evolve 模型相较于前3 种切分成离散快照图形式的网络表示学习模型在性能上有一定优势，但明显不如本文模型。

2）与DyRep 模型对比

DyRep 模型由于缺少源代码、数据集的预处理以及模型的具体实现，导致实验结果产生较大误差。为提高可比性，表2 中DyRep 模型的实验结果参考自文献［23］。本文主要基于DyRep 模型框架进行改进，在该模型上考虑了传播学的关系强度理论以及在节点信息聚合后引入信息反馈机制。在Social Evolution 数据集的实验中，本文模型在HITS@10 和MAR 值上分别比DyRep 模型提高了0.09 和1.6；在Github 数据集中，本文模型在2 个评价指标上分别高出了0.03 和25.7，由此说明本文模型性能更好。

3）与LDG 模型对比

LDG 模型使用神经关系推理改进DyRep 模型，突破了DyRep 模型只能研究两种关系类型的限制。另外该模型加入了双线性编码层，使模型能捕获更多节点信息。在没有加入双线性编码层的条件下，本文模型在两个数据集上的各项评价指标均优于LDG 模型。

与加入双线性编码层的LDG 模型相比，本文模型在Social Evolution 数据集上的实验结果在HITS@10和MAR 两个指标上分别提高了0.19 和2.5。而由于Github 数据集数据量大且节点分布稀疏，因此双线性编码层在大型稀疏网络中捕获的潜在关系能有效提高下游预测任务的性能，所以本文模型在Github数据集上的实验结果是次优的。

本文在Intel®Xeon®W-2102 CPU，NVIDIA GeForce GTX 1080 GPU，32 GB 内存，Windows 10 Professional系统环境下，对本文模型与加入双线性编码层的LDG模型在两个数据集上进行链接预测任务的时间效率测试，测试进行10次，结果取平均值，测试结果如图6所示。

图6 不同模型的时间效率对比Fig.6 Time efficiency comparison of different models

由图6 可知，本文模型在Social Evolution 数据集、Github 数据集上的平均时间效率与加入双线性层的LDG 模型相比，分别提高了91.8%、87.2%。

综上，本文提出的DNRep 模型在真实网络数据集的实验中各项评价指标都是最优或次优的。加入双线性编码层后的LDG 模型在Github 数据集上表现出较优异的性能，然而在时间效率上本文模型显著优于LDG 模型。对于真实世界中只包含强弱两种关系的较为稠密的信息传播网络，本文提出的DNRep 模型更为适用，综合性能更佳。总体而言，本文做出的改进是有效的，所提出的DNRep 模型对于提高下游预测任务的性能有着显著成效。

4 结束语

传统的静态网络表示学习方法不能很好地反映网络结构的动态变化特性，与真实世界的信息传播网络不贴合，且存在延迟性问题。本文结合传播学理论，引入反馈机制，在改进DyRep 模型框架的基础上提出DNRep 模型。使用图神经网络学习得到交互结构的序列相关性，并利用用户辅助信息实现个性化推荐。实验结果表明，与Know-Evolve、DyRep、LDG 等模型相比，本文模型的命中率和平均排名提升显著。下一步将关注大规模动态网络上的网络表示学习，并利用表示学习改进下游机器学习任务，从而提高信息传播动态模型的效率。