HIC-DRL：基于独立级联模型的超图影响最大化深度强化学习方法

《Knowledge-Based Systems》：HIC-DRL: A deep reinforcement learning approach for hypergraph influence maximization with independent cascade model

　　

• •
  HIC-DRL是首个用于超图IC扩散的端到端DRL框架。
• •
  在HIC模型下，影响力最大化被证明是单调且次模的。
• •
  HIC-DRL在九个数据集上以极低的运行时间实现了接近贪心的传播效果。
• •
  直接的超图建模优于团扩展图方法。

引言

随着在线社交网络、知识社区和协作平台的日益普及，信息[1]、意见[2]和行为的扩散动态[3]已成为网络科学、社会学和数据挖掘领域的核心研究课题。在此背景下，计算社会学中的经典影响力最大化（IM）问题旨在识别一组最优的初始用户（种子节点），以最大化信息通过网络传播的最终范围。由于其在病毒式营销、舆论引导和公共卫生倡议等领域的显著应用，IM问题长期受到广泛的学术关注[4]。

传统的IM研究主要依赖于描述两两交互的普通图模型。然而，许多现实世界的交互本质上是基于群体的，例如群聊讨论、团队协作和社区活动。为了准确捕捉这种高阶关联，超图作为普通图的一般化被引入。在超图中，一条超边可以同时连接任意数量的节点，为建模复杂社会系统提供了更自然和更具表达力的框架。尽管如此，大多数现有的基于超图的IM研究仍然采用或改编LT模型及其变体[5]、[6]、[7]、[8]、[9]。LT模型的核心机制是"累积影响"，其中节点的激活取决于其邻居影响的加权总和是否超过某个阈值。这种机制特别适用于涉及高决策成本和由社会强化驱动的场景，例如决策制定和意见形成。然而，在快速信息扩散、病毒式营销和突发新闻传播等场景中，个体决策往往由单次暴露触发，传播动态更接近于"独立传染"机制。IC模型[10]是描述这种"简单扩散"过程的理想工具。它假设每次激活尝试都是独立的，从而更好地捕捉群体内信息传播的随机性和并发特性。

不幸的是，尽管IC模型在普通图上已被广泛研究[11]、[12]、[13]、[14]，且少数工作将其扩展到超图或群体结构[15]、[16]、[17]，但这些尝试主要依赖于启发式或基于排名的策略，既未能充分利用超图结构信息，也未能捕捉种子节点之间的组合协同效应；同时，经典的精确方法如贪心算法受NP难性和蒙特卡洛（MC）模拟高昂成本的制约，因此难以扩展到大规模超图。因此，针对超图独立级联机制且集成超图表示学习与深度强化学习的种子选择方法仍尚待探索。与此同时，尽管深度强化学习（DRL）在普通图IM问题上展现了强大的序列决策能力，但将其应用于超图独立级联模型仍面临若干挑战：传播通过超边在节点群组之间扩散，因此需要在节点-超边二部结构上学习表示，而这难以被传统的成对GNN刻画；种子集的影响力传播仅能通过序列选择末端的MC模拟获得，使得单步边际贡献存在噪声且信用分配困难；动作空间包含所有节点，而每一步评估都依赖昂贵的随机模拟，对可扩展性提出了严格要求。为了应对这些挑战，本文对超图独立级联模型下的影响力最大化进行了系统研究。本文的主要贡献总结如下：

（1）我们研究了超图独立级联机制下的影响力最大化，使用HIC实例化来刻画超边介导的独立扩散，并证明了单调性、次模性和贪心近似保证。

（2）我们提出了HIC-DRL，一个用于超图独立级联模型的端到端深度强化学习框架，集成了高阶结构表示学习与序列种子选择。

（3）在九个真实数据集上的实验表明，HIC-DRL实现了接近贪心的扩散性能，同时具有显著更高的效率。消融实验和结构比较研究进一步验证了预训练和直接超图建模的有效性。

本文其余部分组织如下。第2节回顾相关工作。第3节给出超图传播模型的形式定义和问题定义。第4节详细介绍HIC-DRL框架设计。第5节呈现实验结果和讨论。第6节总结本文并概述未来研究方向。

章节片段

影响力最大化

影响力最大化旨在选择社交网络中的一组种子节点以最大化信息传播。Domingos等人[18]是最早从数据挖掘角度研究此问题的工作之一。Kempe等人[19]随后将其表述为离散优化问题，并证明了在IC和LT等经典扩散模型下的NP难性。通过利用影响力函数的次模性，他们提出了一种具有$1?1/e??$近似保证的贪心算法，

超图和扩展图的定义

定义1 超图

超图定义为有序对$H=(V,E)$，其中$V=\{v_1,v_2,\dots ,v_n\}$是节点的有限集合，$E=\{e_1,e_2,\dots ,e_m\}?2^V?\{?\}$是$m$条非空超边的集合。当所有超边都是二元子集时（即$?e_i\in E,\left|e_i\right|=2$），该结构退化为普通图。

超图的主要优势在于其能够直接表示多节点间的高阶交互。为了利用成熟的图算法，超图结构通常被转换为普通

提出的框架：HIC-DRL

图3展示了HIC-DRL框架的整体架构，包含三个核心阶段：预训练、强化学习训练和模型推断。如图3(a)所示，预训练阶段采用HGNN来学习节点的低维嵌入，为策略学习建立特征基础。图3(b)描绘了核心强化学习训练阶段，其中智能体通过与...的交互学习序列种子节点选择策略

实验

在本节中，我们通过一系列对比实验评估了所提出的HIC-DRL算法在IM问题上的表现。实验平台由Ubuntu 20.04.6 LTS系统下的Intel Xeon Gold 6346 CPU和NVIDIA A100 GPU组成。详细的设计和分析如下。

结论

本文提出了HIC-DRL，一个专为超图IM设计的基于深度强化学习的框架。首先，我们研究了HIC模型下的IM，并证明了影响力函数的单调性和次模性，这建立了贪心算法的$(1?1/e)$近似保证，并提供了理论上有依据的近似最优参考。基于该模型，IM问题被表述为马尔可夫决策过程并通过深度Q学习进行优化。其次，

CRediT作者贡献声明

Peng-Yue Li：撰写——审阅与编辑，撰写——初稿，软件，方法论，调查研究，形式分析，概念化。Feng Hu：撰写——审阅与编辑，验证，监督，资源，概念化。Zhao-Yang Bao：撰写——初稿，验证，资源。You-Feng Zhao：撰写——审阅与编辑，验证。Yu-Rong Song：验证，监督。Dong Li：撰写——审阅与编辑，验证，监督，资源，概念化。

资金支持

本工作得到了国家自然科学基金委员会（资助编号62566052、62376136和62076149）、西藏智能重点实验室建设项目（资助编号2025-ZJ-J08）和广东省基础与应用基础研究基金（资助编号2024A1515011935）的支持。

利益冲突声明

作者声明他们没有已知的财务利益冲突或个人关系，这些关系可能会影响本文所述的工作。

Peng-Yue Li|Feng Hu|Zhao-Yang Bao|You-Feng Zhao|Yu-Rong Song|Dong Li