Nature·机器智能：如何瓦解一个多层网络？MultiDismantler 算法给你答案！

原创杨宸，谷伟伟 2025-07-16 18:29 北京

集智社区科学家谷伟伟团队最新研究登上Nature子刊！

摘要

面对疫情防控、关键基础设施保护、交通电网安全乃至现代战争中的网络攻防转换等现实挑战，如何高效识别并拆除异质多层网络中的“关键节点”已成为网络科学领域的核心难题。传统方法大多依赖中心性等启发式指标，难以全面刻画异质节点之间复杂而多变的交互关系，导致拆解效率低、泛化能力差，难以满足现实复杂系统中大规模、多层次、多样化网络结构的实际需求。近日，集智社区科学家，北京化工大学谷伟伟副教授带领本科生杨宸和李磊创新性地提出MultiDismantler算法，相关成果发表在Nature Machine Intelligence。算法融合了图神经网络与深度强化学习优势，实现对多层异质网络关键节点的高效识别与动态瓦解，在复杂系统的智能拆解与安全防护领域填补了关键空白，推动网络干预智能化向前迈出重要一步。

关键词：网络瓦解，异质网神经网络，深度强化学习，级联失效

杨宸，谷伟伟丨作者

论文题目：Deep-learning-aided dismantling of interdependent networks
论文来源：Nature Machine Intelligence
论文链接：https://www.nature.com/articles/s42256-025-01070-2

一、研究背景：多层网络瓦解的挑战与突破

网络结构被广泛应用于描述自然与人造系统中的复杂交互关系，例如气候网络、蛋白质相互作用网络、社会网络以及基础设施网络等。这些复杂网络普遍呈现出高度异质的结构特性，系统的整体连通性往往依赖于少数关键节点。识别并移除这些关键节点，以最小代价将网络瓦解为多个小规模、互不连通的子图，被称为网络瓦解问题（network dismantling problem）。

网络瓦解问题在众多现实场景中具有重要意义。例如：在药物设计中，有选择性地抑制关键蛋白质以阻断病理过程；在基础设施网络中，识别并加固关键节点以提升系统稳健性；在传染病防控中，通过优先接种关键个体来高效阻断病毒传播路径。尽管网络瓦解是一个基础而关键的优化问题，但其本质属于 NP-hard 问题，精确求解仅适用于小规模网络。为此，研究者们提出了多种启发式算法，如基于中心性指标的 HDA（High Degree Adaptive）、CI（Collective Influence）、MinSum（Minimum Sum Influence）等方法。这类方法具备较高的计算效率，但通常难以获得全局最优解，且泛化能力有限。

近年来，机器学习方法逐渐被引入网络瓦解研究中。例如，GDM 和 NIRM 通过在小型合成网络上学习近似最优策略，尝试实现对更大规模网络的泛化；FINDER 则采用深度强化学习框架，通过与网络环境的交互过程自主学习瓦解策略，摆脱了对人工标签的依赖。这些方法在大规模网络上的初步应用展现出一定成效，但主要仍局限于单层网络的瓦解场景。

针对这一局限性，本文聚焦于多层异质网络中的关键节点识别难题，提出了一种融合异质图神经网络表示学习与深度强化学习优化策略的智能瓦解框架——MultiDismantler。该方法基于几何多层模型构建大规模训练数据集，并引入跨层注意力机制与 DQN 学习机制，实现对复杂网络结构及其层间依赖关系的高效建模与策略优化。实验结果表明，MultiDismantler 在单层及多层网络的瓦解任务中均显著优于现有主流算法，作为首个深度学习驱动的多层网络瓦解方法，具备重要的理论价值与现实应用前景。

2. 方法概述：MultiDismantler框架

现实中的许多复杂系统，如社会网络、电力交通系统或蛋白质调控网络，并非由单一层次的交互构成，而是呈现出多层相互依赖结构（multi-layer interdependent networks）。在这样的系统中，一个节点在一层中的故障可能通过跨层依赖关系引发连锁反应，最终导致整个系统的级联崩溃（cascading failure）。因此，简单地将单层瓦解算法应用于每一层并不能有效解决问题，甚至可能导致严重低估系统脆弱性。

在已有方法中，FINDER 是一项具有代表性的进展，它通过强化学习方式，不依赖精确标签，在单层网络中自动学习最优节点移除策略，显著提升了瓦解效果。FINDER 在策略学习能力方面表现优越，展现出超越传统启发式方法的潜力。

然而，FINDER主要针对单层网络结构设计，其表征学习架构无法识别或处理跨层信息传递所带来的系统性风险，限制了其在现实多层系统中的应用效果。为克服上述局限，MultiDismantler在其强化学习架构基础上，进一步融合多层网络建模和多层表示学习机制，面向多层网络瓦解问题提供全新的解决方案。

MultiDismantler整体架构由三大模块协同组成，实现端到端的多层网络瓦解方案：

核心术语释义

LMCC（largest mutually connected component，最大互连分量）
指在多层网络中，所有节点在所有层均保持可达性时形成的最大连通区域，其大小是衡量多层系统整体连通性的重要指标。

AUDC（Area Under the Dismantling Curve，瓦解曲线下的面积）
反映节点逐步移除过程中，最大互连分量的大小随移除代价变化的累积情况，值越小表示瓦解越高效。

C*（normalized dismantling cost，最小归一化瓦解成本）
表示将 LMCC 削减至非广延规模（通常小于原始网络平方根大小）所需的最小移除成本，并进行归一化处理，方便不同网络间横向比较。

图 1. MultiDismantler训练流程：首先，通过GMM生成大量多层网络；然后，利用MGNN对多层网络进行编码（对应图中fE过程）；接着，使用DQN进行解码（对应图中fD过程），并选择在网络拆解过程中最关键的节点(对应途中Greedy Selection)。该过程反复迭代，最终学习到多层网络瓦解的综合策略。

· 多层网络建模（GMM，Geometric Multiplex Model）

在训练数据准备阶段，MultiDismantler 引入 GMM 作为合成网络生成器。相比传统单层 BA 或 ER 网络，GMM 能更真实地复现现实网络中的层间几何相关性和耦合结构，从而在训练阶段提供具有代表性和结构多样性的语料，增强模型的泛化能力。这种对真实结构特性的模拟，使得算法在面对未见过的网络拓扑仍具备强鲁棒性和转移能力。

· 多层表示学习机制（MGNN，Multiplex Graph Neural Network）

在表征学习阶段，MultiDismantler 使用 MGNN 模型对多层网络进行编码，不仅在每一层内部通过图卷积提取局部结构特征，还通过节点级的跨层注意力机制实现层间信息融合。MGNN 能动态建模节点级别的注意力，量化不同层中的跨层节点相对重要性，生成具有全局语义、一体化的结构表示，精准捕捉跨层耦合对网络瓦解路径的影响。

· 强化学习策略优化（N-step Deep Q-Network）

在策略学习方面，MultiDismantler 基于 N-step Deep Q-Network设计了强化学习模块，以学习网络瓦解中的最优节点移除顺序。算法通过引入虚拟节点构建网络状态，结合LMCC大小的变化作为奖励信号，引导智能体学习长远且系统性强的拆解策略。N-step Q-learning 能够有效建模节点移除对未来状态的滞后影响，使得所学策略不仅关注当前瓦解效果，更能识别潜在的结构断裂点。考虑到多层网络中各层功能和结构的重要性不尽相同，MultiDismantler 为每一层分别计算节点的 Qvalue，再通过层级注意力机制自适应地融合这些值，形成综合的策略评估结果。

3. 网络瓦解过程可视化

为更直观地展示不同算法在多层网络瓦解过程中的表现，我们以一个包含 15 个节点的合成互依网络为例，对比分析了 HDA 算法与 MultiDismantler 的操作流程和瓦解效果。

· 图中每一层表示网络的一个子层，上下层节点一一对应，灰色竖线表示层间依赖关系。蓝色节点与连边表示当前网络中的LMCC，红色节点表示当前被移除的节点。

· 图 (a)–(c) 展示的是 HDA 算法的瓦解过程。HDA 首先移除节点 9，但其后选择了节点 8，未能显著破坏网络结构，最终留下了一个包含 13 个节点的 LMCC，瓦解效果有限。

图 (d)–(f) 展示的是 MultiDismantler 的瓦解过程。该方法同样以节点 9 作为首个移除目标，但在第二步选择了桥接节点 3。这一策略将原网络有效分割为两个较小的连通子图（分别为 5 节点与 6 节点），与HDA相比，LMCC所包含的节点减少了7个，加速了网络崩解的进程。

该例子清晰地说明：相比于基于度数的启发式方法，MultiDismantler 能够捕捉关键结构特征（如桥接节点），并制定更具全局破坏性与连锁瓦解潜力的节点移除序列，从而展现出更优的瓦解策略。

4. MultiDismantler网络瓦解性能评估

为全面验证 MultiDismantler 的有效性，作者在大量合成网络和真实世界网络数据上对比评估其瓦解性能。合成数据由GMM生成，具有可控的层间相关性和节点度分布，可模拟现实中的多种结构属性；真实数据则涵盖生物网络、交通网络、社交网络等多类复杂系统。

结果表明：

· 在合成网络上，MultiDismantler 在不同结构参数设定下均显著优于基线算法，AUDC在单位代价和度数代价下分别优于次优算法 EMD 约 5.9% 和 8.3%。

· 在真实多层网络中，MultiDismantler 同样表现优越。在单位代价下，C* 相较 FINDER 降低了 3%；在度数代价下，AUDC 相较 EMD 下降了 8.4%。

此外，实验还验证了 MultiDismantler 在未知代价分布（如正态分布、泊松分布）下的稳健性与泛化能力，即便仅在统一分布下训练，仍能在新分布下取得最优结果，展示出良好的实用性与鲁棒性。

5. MultiDismantler
在疾病传播防控与网络鲁棒性增强中的应用

MultiDismantler 不仅在理论层面具备最优瓦解能力，其输出的节点序列也在实际应用中展现出显著效用。本文聚焦两个典型应用场景：

（1）疾病传播防控：
在多层社交网络中，作者利用 MultiDismantler 提供的节点序列，设计疫苗接种策略。通过移除前 50% 的关键节点（即模拟接种），并在残余网络上进行 SIR 传播模拟，MultiDismantler减少了最终感染人数。与其他方法相比，其策略更有效地阻断了疫情的传播路径，达到了较低的感染率，展示出其在公共健康管理中的潜在应用价值。

（2）网络鲁棒性提升：
在抗攻击实验中，作者考察了在已知关键节点序列的前提下，若对其中前 1% 节点进行保护，网络在遭遇随机失效或定向攻击时的稳健性变化。结果表明，无论是随机扰动还是定向攻击，基于 MultiDismantler 策略保护的网络都保持了更大的主连通组件，证明其具备良好的“先识别、后保护”能力，适用于关键基础设施系统的抗毁设计。

总的来看，MultiDismantler 不仅是一种强有力的瓦解优化工具，其在疾病控制、网络设计与风险防范等领域的落地潜力也得到了初步验证。

6. 未来展望

尽管 MultiDismantler 在多层网络瓦解任务中展现出显著优势，仍有若干值得进一步探索的方向。比如当前模型主要面向一对一节点映射的互依网络结构，未来可以扩展至多对多依赖关系或部分冗余互联结构，以更贴近现实中复杂系统（如电网-通信、社交-交通耦合网络）中存在的异构依赖模式。

作者介绍

谷伟伟，北京化工大学信息科学与技术学院计算机系副教授，集智科学家，主要研究方向包括多层网络表征学习、图组合优化与AI For Science；近五年以第一作者在《Nature Machine Intelligence》《Nature Communications》等高水平期刊发表多项研究成果。

个人主页：https://lanyu617.github.io/weiweigu/

杨宸，北京化工大学信息科学与技术学院2020级本科生，香港理工大学研究助理。研究兴趣为AI for Science，图神经网络。邮箱：chenyangmiles@gmail.com。

推荐读书会

关于Finder的详细解读，请看视频👇🏿

「重整化群分析在非线性物理中的应用」系列课程

你知道吗？费根保姆常数可以由重整化群计算，相变临界点可以由重整化方法得出，深度神经网络的多层计算就是在对图像做重整化。重整化群是考察不同尺度下物理规律变化的数学工具，帮助我们理解系统在大范围内或临界点附近的行为。集智学园联合北京邮电大学兰岳恒教授开设「重整化群分析在非线性物理中的应用」系列课程，系统讲述重整化群这一理论框架，怎样用来分析高维非线性系统的性质，实现方程的求解与约化。

本系列课程将回答如下问题：

从有限的观测提取一般性规律建模的原则和常见框架是什么？

怎样写出系统重要结构和运动模式的近似解析表达式？

怎样将对称性、不变性、基本范式等先验知识放到系统解析描述中？

怎样建立系统不同层级动力学间联系的方程？

欢迎感兴趣的研究者加入课程。