图网络如何对抗防御？佐治亚理工最新《图脆弱性与鲁棒性》TKDE综述论文，概述图鲁棒性度量、攻击与防御

2022 年 4 月 7 日 专知

【导读】图机器学习是当下的研究热点。围绕图网络的鲁棒性研究是一个关键的问题。来自佐治亚理工最新《图脆弱性与鲁棒性》综述论文，提炼了许多领域的关键发现，包括图鲁棒性度量、网络攻击策略和防御技术。

Graph Vulnerability and Robustness: A Survey

网络鲁棒性研究是表征和理解复杂互联系统(如基础设施、通信和社交网络)的重要工具。虽然在这些领域进行了大量的研究，但综述文献仍然存在空白。目前，关键问题的答案分散在多个科学领域和众多论文中。在这项综述中，我们提炼了许多领域的关键发现，并通过以下方法为研究人员提供了获取重要信息的关键途径: (1) 总结和比较最新和经典的图鲁棒性度量; (2) 探索哪些鲁棒性措施最适用于不同类别的网络(如社会、基础设施); (3) 回顾常见的网络攻击策略，总结在不同的网络拓扑中哪种攻击最有效; (4) 广泛讨论了如何选择防御技术来减轻跨各种网络的攻击。本综述指导研究人员和实践者在网络鲁棒性领域导航，同时总结了关键问题的答案。最后，我们强调了当前的研究方向和有待解决的问题。

https://www.zhuanzhi.ai/paper/52b2ce832531fb453c9345b2d2386b8b

引言

在网络鲁棒性研究中有三个基本任务:(i)开发量化网络鲁棒性的措施，(ii)识别网络攻击机制，(iii)构建抵御网络故障和从攻击中恢复的防御技术。早在20世纪70年代[1]就被提到，网络鲁棒性有着丰富而传奇的历史，跨越了工程和科学的众多领域[2]，[3]，[4]，[5]。这种研究的多样性产生了各种独特的视角，为具有挑战性的问题提供了新的见解，同时为研究人员的调查提供了基础知识。虽然研究领域可能不同，但它们通过网络鲁棒性的共同定义[3]，[6]，[7]联系在一起:

鲁棒性是衡量网络在部分网络遭到自然破坏或成为攻击目标时继续运行的能力。

为了直观地理解这个定义，我们考虑一个电网网络的例子，该电网既容易受到自然故障，也容易受到有针对性的攻击。自然故障是指由于局部腐蚀或自然灾害导致单个变电站发生故障。然而，当一个变电站故障时，额外的负载会被转移到其他变电站，这可能会导致级联故障。并非所有的故障都源于自然原因，有些来自有针对性的攻击，比如敌国入侵电网，破坏关键设备，最大限度地破坏电网的运行。通过分析和理解这些网络的鲁棒性，我们可以减轻自然故障和目标攻击造成的损害，在某些情况下，甚至可以完全预防。

不幸的是，跨学科研究的性质也带来了重大的挑战。一个领域的重要发现往往不能迅速传播，从而导致错失创新机会。在这项综述中，我们的目标是提炼出在先前的相关研究中提出的关键研究问题，如果得到有效的解决，将有助于读者理解这个主题的复杂的相互联系，并加速思想的传播。具体来说，我们分析和比较了许多经典和现代的鲁棒性技术——解决了本综述中的一个关键空白，并帮助为未来的工作奠定了基础。

本文贡献

通过C1-C5的贡献，我们提炼和总结了在网络鲁棒性文献中发现的关键主题。

C1-我们总结了17个现代和经典的网络鲁棒性措施 ，以及每个措施是如何与图脆弱性和鲁棒性评估联系在一起的。我们的目标是为研究人员提供一个信息存储库，以便在他们自己的应用中客观地比较鲁棒性度量。

C2-并不是所有的鲁棒性度量都同样适用于每一类网络数据 。例如，图的聚类系数对于社会网络的研究是很重要的，因为它提供了群体“紧密性”的指示。然而，供水网络需要能够考虑瓶颈和替代途径的措施。我们深入研究了文献，并总结了为什么有些措施更适用于特定领域。特别是，我们研究了两种高影响的用例情景(i)交通网络和(ii)供水网络。

C3-网络攻击策略概述通过了解网络的拓扑结构，可以分析自然故障和针对性攻击的影响 。我们讨论了流行的网络攻击策略，并对哪些攻击策略最适合于不同的网络拓扑结构提供了一个高层次的总结。这种攻击策略的比较，作为同类的第一个，为研究者和实践者提供了一个有效的攻击选择的快速指南。

C4-通过了解C3中常见的网络拓扑和攻击策略，我们可以研究网络防御机制的有效性 。在这三种主要的网络防御机制中，我们总结了与各种网络拓扑结构、自然失效机制和针对性攻击相关的众多防御机制:每一种机制都有相关的利益和成本，其中有些机制比其他机制贵得离谱。我们探讨这些权衡，目的是为读者提供各种真实世界场景中可用的防御选项的全面概述，以帮助网络防御的决策制定。据我们所知，这是第一次跨攻击矢量和网络拓扑对网络防御技术进行全面的比较。

C5-通过仔细分析现有的网络鲁棒性文献，我们识别并提炼出具有强大潜力作为未来研究方向的开放问题 。未来网络鲁棒性研究的有前途的方向和开放的问题包括:(1)对鲁棒性测度的期望性质进行公论化研究，有助于指导新测度的选择和开发;(2)鲁棒性测量的可解释性，帮助用户理解测量分数的影响;(3)将网络鲁棒性研究应用到其他高影响的领域，如物理安全和网络安全;(4)将图脆弱性和鲁棒性的研究与最近在图结构数据上的对抗机器学习的发展联系起来。

本文结构

本文对所做的工作进行了视觉概述。§2总结并比较了17种图鲁棒性度量。§3概述了网络故障和攻击的方法。§4总结了跨越各种图拓扑和攻击向量的网络防御技术。

图1显示了本次综述论文结构的概述，

表2总结了代表性工作。本文的剩余部分分为七个部分。每个主要组件(度量、攻击和防御)都有一个或多个部分，以促使每个组件如何在其他组件的基础上构建。

§2总结和比较鲁棒性测度

我们总结了最近和经典的鲁棒性测度，以及每个测度是如何与图脆弱性和鲁棒性评价相联系的。然后，我们创建一个表，总结每个鲁棒度量，允许用户以简单的方式比较每个度量

§3讨论网络故障和目标攻击

我们讨论了与常见图拓扑相关的自然故障和目标攻击策略。

§4分析网络防御机制

我们总结了常用的网络防御机制，用于减轻各种网络拓扑结构和攻击造成的损害。

鲁棒性测度

我们首先总结了18个最近的和经典的鲁棒性度量，根据它是否使用图(第2.1节)、邻接矩阵(第2.2节)或拉普拉斯矩阵(第2.3节)，将每个度量分为三类之一。在描述了每个度量之后，我们描述了它与网络鲁棒性研究的联系。我们注意到一些额外的鲁棒性度量，如散射数[93]、韧性[94]、完整性[95]、断层直径[5]、韧性[1]和等周数[96]。但是，由于它们是一般图[28]的组合度量，所以我们不考虑它们来求值。

图攻击

为了理解网络故障和攻击的潜在机制，我们需要研究促成这些问题的图属性。为了做到这一点，我们首先简要概述3.1节中的四个经典图模型。图模型的背景知识有助于分别在第3.2节和第3.3节中分析网络故障和攻击。

网络防御

要理解特定网络的最佳防御机制，重要的是要理解图的属性以及我们希望防范的攻击或失败的类型。在4.1节中，我们概述了如何度量用于提高网络防御的独立启发式，将每种技术分为三类之一，这取决于它是否通过(i)添加边缘，(ii)重新连接边缘，或(iii)识别网络中的重要节点和边缘来监控可疑活动。然后，在4.2节中，我们根据上述相同的分类过程分析基于优化的网络防御技术。最后，在4.3节中，我们讨论了何时应用不同的防御技术。

开放问题

提出了从综述工作中提炼出来的研究方向和有待解决的问题。三个有前景的方向包括: (1) 对鲁棒性测度的期望性质进行公理化研究，帮助指导新测度的选择和开发;

(2) 鲁棒性测量的可解释性，帮助用户理解测量分数的影响;

(3) 将网络鲁棒性研究应用到其他高影响的领域，如物理安全和网络安全。

专知便捷查看