如何以最小代价破坏系统结构？一套基于机器学习的方法

导语

复杂系统的结构连通性会极大影响其功能，对于规模巨大的系统，如何确定一组最小规模的节点，使得其被移除后系统几乎崩溃？这一问题也被称为网络拆解问题，备受研究者的关注。近日，发表在 Nature Communications 上的一篇论文“复杂系统的机器学习拆解和瓦解预警信号”，提出了一种基于机器学习的框架，能够有效评估节点属于拆解最小节点组的概率，该框架同时提供了一种量化系统风险和实现系统崩溃预警的方法。

「网络科学·集智课堂」迎来全新升级，我们邀请陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华等网络科学专家作为导师，以「复杂系统的数学建模与应用」为主题展开课程。课程自10月16日持续至12月25日，学员可加入400人+的集智网络科学交流社区，详情见文末。

研究领域：网络拆解问题，深度学习，可解释性，系统崩溃预警

江水 | 作者

梁金 | 审校

邓一雪 | 编辑

论文题目：

Machine learning dismantling and early-warning signals of disintegration in complex systems

论文地址：

https://www.nature.com/articles/s41467-021-25485-8

1. 如何以最小代价

最大程度地破坏系统结构？

现实生活中的复杂系统的结构和动力学可以通过由点边构成的复杂网络而有效表征，例如常见的基础设施网络、社交网络、蛋白交互网络等。网络的结构拓扑会极大地影响系统的运行，找到对网络结构影响最大的节点加以破坏，能够以最小的代价最大程度地破坏系统的结构与功能。

例如，图1展示了巴西贪腐网络的拆解过程，网络中的节点表示贪腐案件涉及到的人，连边表示两个人至少一次出现在同一案件中，通过制定有效的网络拆解方案，只需突破少量个体，即可快速破坏整个贪腐体系。而另一方面，若该网络表征的是社会正常运行赖以生存的电网、水网等基础设施系统，则拆解方案中的节点将成为维持系统功能的重点保护对象。

此类拆解方案的制定问题通常被称为网络拆解问题（或网络瓦解问题）。在众多网络结构特性的评价中，研究者最常利用网络最大规模连通集团中的节点数作为网络结构连通性的评价标准。因此，网络拆解问题受到广泛认可的严格定义是：如何确定一个最小规模的节点集合，使得这些节点被移除后网络破碎化为众多很小的连通集团。图1中的 (b)(c) 相同颜色的节点位于同一连通集团，而白色节点群表示最大连通集团。该问题本质上是一个NP-hard问题，问题的难度随着网络规模的增加而急剧增长，在之前的研究中，研究者通常尝试运用渗流理论和图论等知识，通过设计启发式规则来获取问题的近似最优解。

图1：巴西贪腐网络的拆解过程

2. 训练一个机器，

学习拓扑机制以拆解网络

与传统基于结构启发式的方法不同，在本文中作者创新地提出了一个有效的机器学习框架GDM（Graph Dismantling with Machine learning）来解决上述问题，该框架的主体是一个由图卷积层和回归子组成的几何深度学习模型，能够通过在大量小型人工网络中的训练，学习到属于最小拆解集合中节点的特征聚合方式，进而快速判断出大规模网络中节点属于最小拆解集合的概率。该框架以网络中节点的中心性等特征为输入，以节点位于网络最小拆解集的概率为输出，按照概率从大到小依次移除网络中的节点，即可有效地拆解网络。

该框架采用有监督学习的方式进行训练，首先要获取大量有标签的训练样本。本文中作者生成了一些小规模的模型网络，例如无标度网络、随机网络等，计算节点的不同中心性和拓扑特征，例如节点度值、聚类系数等，通过穷举法获得其所有的最小拆解集合，进而计算每个节点位于拆解集合的概率，由此就得到了大量的训练样本。运用这些样本，可以对深度学习模型进行有效训练，以获得合适的节点特征聚合方式，而框架中采用的图注意力网络通过注意力机制来对邻居节点做聚合操作，实现了不同邻居权重的自适应分配。

为了评估算法的有效性，文章运用节点移除过程中最大连通集团规模曲线（如图1a所示）下的面积（AUC, Area Under the Curve）作为评估算法有效性的指标，通过在大量的节点规模达到十万、百万量级的真实网络和模型网络的实验，发现本算法的平均表现要优于当前已有的结构启发式算法，且具有较低的时间复杂度。同时，文章通过网络的连边重写扰动实验和单一特征的增强实验，进一步证明了本框架的有效性。

图2. GDM框架流程示意图

3. 打开深度学习的黑箱，

揭秘方法有效背后的原因

在验证了算法的初步性能后，为探究模型具体是怎样学习和做出长期预测的，作者引入这一类图卷积网络模型的解释器 GNNExplainer，提取由节点和连边子图组成的解释子图，来揭示模型对每个节点的预测值。

如图3所示，通过测试几种网络的解释子图发现，得分排名前四的节点均为连接多个簇的桥节点，且是通过结合输入特征和查找K阶邻居中的其他桥节点发现的，在算法中通过聚合局部和二阶特征来实现。这一思路实际上和一种已有的基于组合影响（Collective Influence，CI）的启发式方法的机理类似，区别在于CI仅对节点及其k阶邻居的度值特征进行聚合，而本方法通过深度学习方法聚合了更多节点及其邻居的特征。

图3. 巴西贪腐网络中排名前四节点的解释子图

在理解了模型学习的内容后，进一步运用 GNNExplainer 分析特征在输出值计算中的作用，并了解模型如何选择节点。通过图4的分析可以看出，并没有一个在所有网络中都处于支配地位的特征，而且不同特征的权重比例还会随着节点的得分而变化。这些结果也说明，基于这些 GDM 框架的结果来定义一种启发式方法是极其困难的，因为每个特征的权重是由模型根据拓扑和网络中的模式进行调整的。

图4. 节点不同特征的重要性趋势

网络中如果移除会产生新的连通片的节点被称为“关节点”，对于维持网络连通性有重要作用，随着网络中节点的移除，也会产生新的关节点。作者通过分析节点移除过程中，网络中的关节点数量，移除节点中关节点数量和新产生的关节点数量的变化，来分析框架识别出的节点的特点。值得注意的是，单纯关节点的移除并不会对网络连通性造成很大的损伤，因为有些关节点可能只会影响网络中的少量节点。本文通过如图4所示的分析说明，GDM 方法能够通过学习找到那些更有效瓦解网络的关节点。

图5. 节点移除过程中关节点的移除与产生

4. 系统崩溃发生前夕的早期预警信号

在文章的研究中使用最大连通片的规模作为系统连通性的评价，事实上，仅关注这一指标并不能完全把握系统的状态。我们所担心的系统的崩溃风险并不仅仅来源于系统连通规模的下降，更多来源于节点失效累积而造成的系统性能的骤降。

如图6所示的例子，深红色节点的依次移除在开始并不会造成明显的连通片下降，然而当移除数目累积到一定程度时，整个网络就会完全被分为两个部分，发生系统崩溃。本文框架对节点移除概率的特殊表达提供了一种有效的系统风险量化方式，通过累积计算被移除节点的概率之和，相对于 GDM 框架给出的排名前n节点的概率之和的比例（其中n为最小拆解集合中的节点数目），能够提前感知系统状态，实现系统崩溃的早期预警。

图6. 为什么需要一个早期预警信号？

作者通过不同的真实基础设施网络中的实验来说明，通过文章中的框架可以实现系统崩溃的有效预测。如图7所示，对于欧洲电网、北美电网和伦敦公共交通网这三种不同的基础设施网络，通过本框架的预警信号给出的首次响应时间，能够有效地在系统崩溃来临之前做出提前预警。

图7. 真实基础设施网络崩溃的早期预警

上述发现使得本问题提出的GDM框架不仅可以提供一种有效的网络拆解方案，更能估计由于持续损害而可能导致的系统崩溃，为决策者提供定量的预警信号，以触发对系统紧急情况的及时响应，在例如水网、电网、通信和公共交通网络等基础设施网络的管理中有重要应用意义。

网络科学第三期火热报名中

为什么新冠病毒容易在大城市间快速传播？为什么个别电站故障可以引起大范围停电？为什么手机芯片会带来国家之间的经济博弈？怎样识别社交媒体上的关键信息节点？怎样辨别社群组织内部隐藏的关键人物？怎样判定企业在上下游经济体系中的位置？……一系列真实世界问题的挑战，催生了复杂网络研究的快速兴起。网络科学正在成为21世纪的新通识。

集智学园特邀陈关荣、樊瑛、周进、李翔、张江、闫小勇、刘宗华、石川、虞文武、赵海兴、史定华等网络科学专家作为导师，自10月16日起开展系列在线课程，介绍复杂网络的建模与应用以及相关课题。欢迎希望进入网络科学领域、提高网络分析能力、与一线专家探讨问题的朋友报名参加！