《Neurocomputing》：Dismantling strategies for cost networks based on multi-view deep learning
编辑推荐：
针对传统网络拆卸未考虑攻击转移成本的问题，本文提出成本网络拆卸模型，结合节点攻击成本和转移成本构建多视图图神经网络，设计Epi_CND和Ins_CND两种强化学习算法，在合成与真实网络实验中验证其有效性。
Xuetong Li|Xiao-Dong Zhang
数学科学学院，教育部资助的科学与工程计算重点实验室，上海应用数学中心，上海交通大学，上海200240，中国
摘要
研究网络破坏策略对于攻击恶意网络和确保自身网络的安全至关重要，因为系统（如社会群体、供应链）的实体关系可以通过网络来描述。现有研究主要集中在两种策略上：网络破坏（ND）强调快速摧毁网络结构，而广义网络破坏（GND）还考虑了攻击成本。然而，这两种策略都没有考虑到攻击传递的异质性。为了解决这一限制，我们引入了成本网络，通过结合节点和边的异质性来更全面地表示攻击成本。为了实现快速的网络连接中断和成本效率，我们提出了两种新的模型Epi_CND和Ins_CND用于成本网络破坏。强化学习作为核心解决方案框架，并辅以一种新颖的多视图图神经网络用于信息提取。在合成和真实成本网络上的实验验证表明，所提出的算法表现出显著的有效性和优越性。
引言
如今，网络模型被广泛应用于金融[1]、[2]、军事[3]、[4]、生物医学科学[5]、[6]和交通[7]、[8]等领域。它们的复杂性和互连性逐渐增加，这促使研究人员专注于使用网络模型对现实世界问题进行建模和解决。在商业、军事、政治、网络安全和毒品控制等对抗性场景中，制定攻击对手网络中关键实体的最佳策略以导致其系统崩溃是一个重要的研究课题[9]、[10]、[11]、[12]，这对攻击者和防御者都有重要意义。对于攻击者来说，有策略的攻击比随机攻击更有效地节省资源和确保优势。对于防御者来说，研究网络攻击有助于识别和预防潜在威胁，同时为系统安全设计提供指导，从而确保整个网络生态系统的稳定性。
网络攻击的一个主要目标是快速瓦解网络，从而损害其协作功能和效率。这是通过移除少量节点来显著减小最大连通分量大小来实现的，这通常被称为网络破坏（ND）问题[13]、[14]、[15]。确定节点移除的最佳顺序是理想的优化策略。大多数现有的网络破坏工作假设所有节点和边都是同质的。一些研究进一步考虑了攻击成本，即节点异质性，从而提出了广义网络破坏（GND）问题[16]、[17]、[18]。然而，在这些方法中，边被视为同质的，主要用作评估网络性能的连通性指标。在许多现实世界场景中，边直接限制了攻击序列。例如，攻击者可能需要在连续的攻击步骤之间承担转移成本，或者面临某些攻击转换是否可能的限制。前者适用于由物理实体组成的网络，其中转移成本可以基于攻击目标之间的物理距离进行建模。后者以C. elegans的神经网络为例[19]，其中连接可以分为化学突触、电突触和神经肌肉接头。如果信号只能通过神经递质传输，那么攻击必须遵循化学突触连接，从而将攻击限制在网络中的特定边上。这些例子突显了转移成本在网络破坏中的实际意义，这在军事战争、网络通信和其他领域也可以观察到。在考虑攻击成本和转移成本的同时，我们将网络破坏问题称为成本网络破坏（CND）。为了解决具有两种类型转移成本的CND问题，我们提出了两种新算法：表观成本网络破坏（Epi_CND）和即时成本网络破坏（Ins_CND）。在接下来的讨论中，Epi_CND和Ins_CND将交替使用，以指代相应的问题及其各自的解决算法。
图1展示了一个简单的例子，比较了四种网络破坏模型：ND、GND、Epi_CND和Ins_CND。在ND问题中，除了节点属性外，只需要节点连通性信息，优化目标仅关注破坏节点连接。相比之下，GND问题同时考虑了连通性和个别攻击成本，旨在平衡网络中断和攻击成本节省。需要注意的是，在ND和GND中，每次攻击步骤都可以从剩余网络中自由选择下一个攻击目标。CND模型呈现出更复杂的多视图结构，可以分为破坏目标层（上部）和攻击成本层（下部）。优化过程必须同时考虑破坏目标层中的网络结构中断和攻击成本层中的成本节省。具体来说，在Epi_CND问题中，攻击成本层被建模为一个完全连接的加权网络，其中节点权重代表攻击成本，边权重代表节点之间的转移成本。攻击者可以从剩余网络中自由选择下一个攻击目标。相比之下，Ins_CND问题增加了额外的限制：攻击者只能选择当前攻击节点的相邻节点作为下一次攻击的目标。这种限制增强了Ins_CND问题的实际意义和计算复杂性。第5.1节将提供这四种网络模型的破坏策略的详细比较。
强化学习已成为解决基本网络破坏（ND）及其广义形式（GND）的有效工具。对于具有离散动作空间的破坏，基于价值的动作选择更为常见。DQN的离策略回放和n步回报使得在渐进式节点移除的高度非平稳过程中学习更加稳定和高效。Finder[20]首次将深度强化学习引入破坏领域，此后开发了许多改进的变体。最近的研究进一步将其他领域的概念融入基于RL的破坏过程中：QDRL[21]利用量子增强编码-解码，DRLRA[22]引入资源分配引导策略，GTRP[23]采用流行度感知图Transformer，为传统破坏流程带来了新的视角和优化重点。尽管它们的问题表述相对基本，并没有充分利用现代模型的表达能力。其他变体，如基于线图的边破坏[24]和带符号的网络破坏[25]，能够适应不同类型的网络，但主要关注自适应处理。此外，对比性RL方法[26]最近被证明在结构变化下可以提高鲁棒性。然而，现有研究尚未充分建模攻击传递的结构属性，尽管实际场景中的步骤间约束强烈影响节点移除的顺序，不能被忽视。此外，除了转移成本之外，当前破坏研究很少考虑异质多视图融合。这些限制构成了本工作旨在解决的关键挑战。
本研究对成本网络进行了建模，并探索了高效的破坏策略。我们处理转移成本和节点攻击的方法使我们的工作与以往的研究有所不同。本研究的主要贡献如下：
•引入了一些新概念和指标，并通过考虑个别攻击成本和转移成本来研究成本网络破坏，为现实世界网络场景中的攻击者和防御者提供了宝贵的见解。
•提出了两种基于强化学习的顺序攻击算法用于成本网络破坏：Epi_CND在自由选择攻击目标时考虑转移成本，而Ins_CND引入了空间约束，要求对相邻节点进行顺序攻击。
•开发了一种新的图神经网络（GNN）架构，用于从破坏目标层和攻击成本层提取结构信息，该架构使用多视图学习来融合相应的节点嵌入并降低算法复杂性。
•在合成和真实世界网络上验证了训练有素的策略算法，并证明了它们在成本网络破坏方面优于七种基线方法。
在第2节中，我们回顾了常见的网络破坏方法和图表示学习方法。第3节介绍了与成本网络破坏相关的几个新概念和指标，正式化了成本网络破坏问题的建模，并根据转移成本的类型将其分为两个优化问题。第4节详细介绍了使用DQN作为框架并结合新颖的基于图神经网络的信息提取架构来解决情节成本优化和即时成本优化的方法。第5节将训练有素的模型应用于生成的数据集和真实数据集，将其与其他算法进行比较，并进行了消融实验和超参数分析。第6节以一些评论结束了本文。
部分摘录
网络破坏
在解决网络破坏问题时，一种常见的方法是根据节点的重要性排名（如度中心性[27]或介数中心性[28]）贪婪地移除节点。然而，这些方法对于大规模网络来说计算成本较高。一些研究采用了启发式的循环移除方法[13]、[29]、[30]，这些方法对于树状结构有效，但往往具有较差的可转移性。最近，多模态大型语言模型（MLLMs）已被用于
问题形式化
相互依赖的网络是常见的网络破坏模型，其中每个网络层中的相应节点代表相互依赖的不同实体。如果一个失败，另一个也会失败[46]。例如，在电力通信网络中，如果电力网络中的一个节点失败，由于缺乏电力支持，通信网络中的相应节点也无法正常工作。大多数先前的工作将每个网络层中的所有节点视为网络的对象
模型
本章的前三个小节介绍了用于无约束优化问题（6）的算法模型Epi_CND，而用于受限优化问题（7）的算法Ins_CND将在第4.4节提供。
实验
在本节中，我们使用Python在运行Ubuntu 20.04的环境中评估了所提出的算法Epi_CND和Ins_CND在合成和真实世界数据集上的性能。实验是在配备了第13代Intel Core i7-13700 CPU、Intel UHD Graphics 770、32 GB RAM和1.5 TB（1 TB + 512 GB）组合存储的设备上进行的。
结论
本研究在网络破坏领域取得了显著进展，具体贡献如下：首先，通过细化攻击成本的概念，提供了一个新的网络破坏策略理论框架。其次，创新性地建模了两种类型的成本，并提出了两种基于强化学习的攻击算法，有效解决了传统方法的局限性。第三，设计的图神经网络信息提取架构
CRediT作者贡献声明
Xuetong Li：撰写——原始草稿、软件、方法论、概念化。Xiao-Dong Zhang：撰写——审阅与编辑、监督、项目管理、方法论。
利益冲突声明
作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。
致谢
我们感谢编辑和审稿人对手稿提出的建设性建议和有用评论，这些评论显著提高了我们研究的严谨性和清晰度。这项工作部分得到了中国国家自然科学基金（编号12371354和12161141003）、中国上海市科学技术委员会（编号22JC1403600）以及中国-黑山科学技术合作项目（编号4–3）的支持。
Xiao-Dong Zhang于1998年获得中国科学技术大学的博士学位。自2005年起，他一直在上海交通大学担任教授。他是200多篇科学出版物的作者，指导了20多篇博士和博士论文，并且是10多个由国家自然科学基金等支持的项目的主要研究者。他的研究兴趣包括图论、复杂网络、数据挖掘、人工神经网络和数字信号处理。
