通过离线深度强化学习在社交网络中实现影响力最大化

《Neurocomputing》：Influence maximization in social networks via offline deep reinforcement learning

　　• 固定缓冲区离线强化学习（RL）支持重复的影响最大化部署。
• 相对悲观的高智能体-批评家（Actor-Critic）机制减轻了外来数据（OOD）值的估计偏差。
• 一次性顶级解码（One-shot Top-encoding）能够实现低延迟的种子集生成。
• 在降低部署延迟的同时，保持了竞争力的影响覆盖范围。
• 实验评估了不确定性、可扩展性和对离线数据的依赖性。

**引言**
随着互联网和移动通信技术的快速发展，在线社交平台已成为信息交流和社会互动的重要渠道，支持诸如定向信息传播[35]和谣言压制[15]等应用。在这些场景中，决策者希望用有限的初始用户群体在固定预算下覆盖广泛的受众。这一目标被形式化为影响最大化（IM）问题，即寻找一个预算受限的种子集，以在社交网络中最大化预期的信息传播[18]。
自从2003年Kempe等人首次将IM问题表述为组合优化（CO）问题以来，其目标就是选择一个种子集，在扩散模型（如独立级联（IC）模型[6]）下最大化信息的预期传播[18]。然而，Kempe等人也指出，由于信息传播的随机性和问题的复杂性，找到IM问题的最优解属于NP难问题，这限制了IM算法的应用范围。为了解决这一挑战，人们开发了多种基于非学习的方法，包括：（1）基于仿真的算法[18]、[24]、[51]，通过模拟信息传播过程来估计节点的影响力；（2）基于抽样的算法[3]、[7]、[10]、[45]，生成足够数量的传播样本以估计节点的影响范围；（3）基于启发式的算法[6]、[9]、[13]、[20]、[30]、[40]、[41]，利用启发式规则迭代选择具有高传播潜力的节点来优化种子节点集；以及（4）基于进化的方法[27]、[31]、[44]，通过种群更新、自适应搜索操作器和适应度评估来探索组合种子集。尽管这些方法在搜索策略上有所差异，但大多数方法都需要预定义的扩散模型或影响估计器来评估候选种子集。因此，方法的性能可能取决于所假设的传播机制对现实世界信息传播的忠实度。

随着人工智能和机器学习（ML），特别是深度强化学习（DRL）[36]的快速发展，它在多个领域取得了显著成就，例如网络安全[46]、推荐系统[50]、通信系统[48]等。作为基于模型的分析方法的重要补充，DRL利用深度神经网络（DNN）从大量数据中提取复杂信息，并构建用于序列决策的智能模型。通过根据当前状态选择行动并动态调整基于奖励的策略，DRL可以通过可学习的参数函数估计影响力的传播，使其成为解决IM问题的理想方法[5]、[19]、[26]、[28]、[29]、[34]。尽管在这一领域取得了显著进展，但基于学习的DRL方法在解决IM问题时仍面临一些关键挑战：
1) 从固定日志缓冲区中学习策略，而不需要额外的交互。典型的基于DRL的IM方法[5]、[19]、[26]、[28]、[29]、[34]通常通过与扩散模拟器的重复交互或操作环境的交互来收集训练轨迹。当历史日志或模拟器生成的轨迹已经可用时，在策略优化期间收集额外的交互数据可能成本高昂或在操作上不可取[16]。因此，挑战在于仅从固定缓冲区中学习有效的IM策略，同时限制日志数据支持不足的行动的价值估计偏差。
2) 低延迟生成预算可行的种子集。大多数基于DRL的IM方法通过顺序决策构建种子集，在每次选择后更新部分种子集并重新评分剩余的候选节点。虽然基于先前选定节点的条件可以明确表示候选节点值的变化，但重复的图编码和候选节点评估会增加部署延迟，特别是在大型网络和重复种子选择请求的情况下。因此，开发一种低延迟的部署机制至关重要，它可以在保持竞争力影响质量的同时减少部署时间的计算。

为了满足离线/日志数据约束下对低延迟影响最大化服务的实际需求，我们提出了一个名为ODRL-IM的离线深度强化学习框架。我们的目标是支持那些交互式在线探索成本高昂或风险较高的IM部署，同时系统必须返回一个预算可行的种子集，并且决策延迟低。首先，我们设计了一个统一的离线数据收集流程，该流程整合了来自多种异构行为策略（如S2 V-DQN[19]、PIANO[26]和ToupleGDD[5]）的轨迹和随机动作样本，形成一个固定的离线缓冲区用于训练。我们的离线设置使用固定缓冲区策略优化而不是无交互的数据采集；尽管如此，缓冲区的构建可能仍然需要与扩散模拟器的预先交互。然后，我们开发了一个具有相对悲观目标的对抗训练高智能体-批评家学习器，以减轻 offline 支持不足的行动的 OOD 值估计偏差，从而提高从离线数据中学习策略的可靠性。一个共享的基于 GNN 的图表示流程将所有日志状态重新嵌入，以实现节点和图之间的泛化。对于部署，学习到的高智能体不进行迭代的多步种子选择，而是执行一次性顶级决策：它输出一个连续的节点评分向量，并在一个步骤中确定性地将其映射到一个大小的种子集中，显著降低了在线推理延迟。然而，顶级解码是一种面向延迟的近似方法，而不是精确的组合优化器；选定的种子之间的交互仅通过图表示、终端奖励和批评家监督间接捕获。在六个真实世界社交网络上的实验表明，ODRL-IM在各种预算范围内实现了有竞争力的或最佳的影响传播，并且决策延迟比迭代深度 RL 基线降低了几个数量级。我们还观察到，ODRL-IM 对折扣因子的稳定性更强，而基线方法则表现出明显的参数敏感性，这进一步增强了所提出的一次性建模方法的有效性和鲁棒性。最后，我们讨论了在离线数据覆盖有限时的性能改进情况，特别是在极端大的图上；因此，ODRL-IM 最适合于在稳定或缓慢演变的网络上进行重复的、对延迟敏感的种子选择请求，特别是当有合适的日志轨迹可用时。

**本文的主要贡献如下：**
• 面向部署的固定缓冲区 IM 公式化：我们定义了一个 IM 环境，其中策略仅使用固定日志缓冲区进行优化，并在策略优化和部署期间重复用于种子选择请求，而无需额外的环境交互。
• 统一的离线数据和保守的策略学习：我们将来自多种行为策略和随机动作采样的轨迹标准化为基于图的通用一次性表示。然后使用具有相对悲观目标的对抗训练高智能体-批评家来减轻 offline 支持不足的行动的价值估计偏差。
• 面向延迟的一次性顶级解码：我们通过确定性的顶级解码将连续的高智能体分数映射到一个预算可行的种子集中，一步完成。该过程避免了多轮顺序候选节点重新评分，尽管种子集交互仅通过图表示、终端奖励和批评家监督间接捕获。
• 统计评估和边界分析：我们在六个真实世界网络上使用独立的训练运行和蒙特卡洛扩散模拟来评估 ODRL-IM。额外的分析考察了准备和部署成本、离线缓冲区覆盖范围、OOD 值估计、解码权衡、编码器可扩展性和参数敏感性。结果显示，在大型图上具有竞争力的影响覆盖范围和显著的延迟降低，同时确定了性能对离线数据覆盖范围的依赖性。

**组织结构**
本文的其余部分组织如下：第2节回顾相关工作。第3节定义了 IM 问题，介绍了 RL 公式化，并描述了面向部署的问题设置。第4节介绍了 ODRL-IM，包括离线数据构建、离线训练阶段和在线部署阶段。第5节提供了对底层机制的理论分析。第6节报告了在真实世界社交网络上的实验结果。最后，第7节总结了本文。

**相关工作**
现有的 IM 方法可以大致分为非基于学习的方法和基于学习的方法。

**初步部分**
本节在 IC 模型下定义了 IM 问题，介绍了其有限视界 RL 公式化，并指出了本研究中考虑的固定缓冲区学习和部署设置。表1总结了主要符号。

**基于 ODRL 的影响最大化**
本节介绍了如图1所示的 ODRL-IM。该框架将多种行为策略生成的 -步轨迹转换为固定的单次训练缓冲区，并学习一个具有相对悲观目标的高智能体-批评家策略。在部署过程中，高智能体在单次向前传递中评分所有候选节点，确定性顶级解码返回一个预算可行的种子集，无需迭代选择或额外的环境交互。

**理论分析**
本节提供了对 ODRL-IM 在一次性公式化下的两个属性的机制级洞察。首先，我们分解了使用离线相对悲观目标训练的批评家的终端值估计误差（公式（19）。所得到的界限考虑了函数逼近、优化转移、统计泛化和策略引起的分布变化。其次，我们比较了迭代和一次性 IM 的误差传播机制。分析显示...

**实验**
本节从三个方面评估了 ODRL-IM：相对于近似和基于学习的基线的影响质量，一次性解码的部署效率和质量-延迟权衡，以及一次性解码、图编码器选择和保守的离线目标的作用。遵循共同的评估协议，我们报告了影响覆盖范围及其不确定性估计，并进行了成对显著性测试，区分了一次性准备成本和每次查询的延迟。

**结论**
本文提出了一种名为 ODRL-IM 的离线 DRL 框架，用于解决 IM 问题，该框架在收集所需轨迹后仅从固定缓冲区中进行学习。基于图的编码器用于表示网络拓扑并标准化来自异构行为策略的轨迹。ODRL-IM 使用相对悲观的高智能体-批评家目标来减少 offline 缓冲区中支持不足的行动的过度乐观的价值估计。在部署期间，高智能体...

**作者贡献声明**
刘洪福：撰写 – 审稿与编辑、撰写 – 原始草稿、可视化、验证、软件、方法论、调查、形式分析、概念化。
严豪瑞：撰写 – 审稿与编辑、撰写 – 原始草稿、可视化、验证、软件、方法论、调查、形式分析、概念化。
张博：撰写 – 审稿与编辑、方法论、形式分析、概念化。
李大成：可视化、验证、软件、调查。
陈丽星：...

**利益冲突声明**
作者声明他们没有已知的竞争性财务利益或个人关系可能会影响本文报告的工作。

**致谢**
本研究得到了中国国家重点研发计划（编号2023YFB3107100）、国家自然科学基金（编号62372297）和中国博士后科学基金（编号2025M771527）的支持。