基于线图转换与深度强化学习的复杂网络关键边攻击序列高效挖掘

为解决复杂网络拆解(ND)中关键边攻击序列的识别难题，研究人员创新性地提出FIGHTER框架，通过线图转换将边攻击转化为节点攻击问题，结合图神经网络(GNN)与深度强化学习(DRL)，在合成与真实网络中平均性能提升19.28%-20.45%，为网络防御与流行病控制等场景提供高效解决方案。

　　

在当今高度互联的世界中，复杂网络已成为建模从社交关系到交通系统等各种复杂体系的核心工具。然而，如何有效拆解有害网络——无论是阻止计算机病毒的传播还是遏制社会谣言的扩散——始终是学术界和工业界面临的重大挑战。传统方法多聚焦于攻击网络中的关键节点，却忽视了边攻击往往更具现实可行性，因为节点通常数量较少且防护严密。这一研究空白，加上网络拆解(Network Dismantling, ND)任务固有的NP难特性，促使研究人员寻求更智能的解决方案。

针对这一挑战，研究人员开发了名为FIGHTER的创新框架。该工作首次将线图转换技术与深度强化学习(Deep Reinforcement Learning, DRL)相结合，巧妙地将原始图中的边攻击问题转化为线图中的节点攻击问题。通过将ND过程建模为马尔可夫决策过程(Markov Decision Process, MDP)，并利用图神经网络(Graph Neural Network, GNN)进行表征学习，FIGHTER能够从海量数据中自动挖掘高效的网络拆解策略。

研究团队采用了三项关键技术：(1)基于GraphSAGE的线图节点嵌入生成算法，直接提取边特征向量；(2)可适配不同ND目标(攻击最大节点或边连通子图)的弹性奖励函数设计；(3)考虑异质攻击成本的边移除策略，将成本定义为线图中的边度数。实验数据来源于20000余张训练网络图，在NVIDIA GeForce RTX 4060 GPU上完成72小时模型训练。

【模型设计】
FIGHTER的核心创新在于其端到端架构。通过线图转换，原始图中的每条边对应线图中的一个节点，使得成熟的节点攻击方法可直接应用于边攻击场景。编码器模块采用GNN提取线图拓扑特征，解码器则通过DRL学习边移除的最优序列。特别值得注意的是，研究定义了两种巨连通分量(Giant Connected Component, GCC)指标：GCC_node(含最多节点的子图)和GCC_edge(含最多边的子图)，后者在交通网络等边密集型场景中更具实际意义。

【实验结果】
在四类实验场景(均匀/异质成本×GCC_node/GCC_edge目标)中，FIGHTER均展现出显著优势。与五种基准方法相比，在合成网络和真实网络中的平均性能提升分别达到20.45%和19.28%。异质成本场景下的设计尤为亮眼——将边移除成本定义为该边在线图中的度数(即邻边数量)，这一创新使FIGHTER能够智能识别高影响力低成本的"性价比"边攻击序列。

【结论与展望】
该研究通过FIGHTER框架成功实现了三个突破：(1)首次将线图转换与DRL结合解决边攻击序列问题；(2)提出可适应不同网络类型和规模的弹性ND框架；(3)验证了异质成本策略在实际应用中的优越性。这些成果不仅为网络防御提供了新工具，其方法论更可拓展至药物设计中的靶点组合筛选、流行病控制中的传播路径阻断等生命健康领域。论文发表于《Expert Systems with Applications》，作者团队特别声明无利益冲突。未来工作将聚焦于超大规模网络的实时拆解算法优化，以及多目标ND任务的协同求解。