【牛津大学博士论文】图机器学习的鲁棒性分析

来源：专知
本文约2300字，建议阅读5分钟
在这篇论文中，我们专注于基于图的机器学习模型的鲁棒性属性，特别是谱图滤波器和图神经网络。

基于图的机器学习是一种新兴的数据分析方法，适用于可以通过实体之间的成对关系很好地建模的数据。这包括社交网络、道路网络、蛋白质-蛋白质相互作用网络和分子等示例。尽管大量研究致力于设计新型机器学习模型，但对我们现有工具的理论属性的关注较少。在这篇论文中，我们专注于基于图的机器学习模型的鲁棒性属性，特别是谱图滤波器和图神经网络。鲁棒性是处理噪声数据、保护系统免受安全漏洞的侵害以及在某些情况下，对可迁移性等方面至关重要的属性。我们特别关注与基础图的拓扑结构相关的鲁棒性这一具有挑战性和组合性的问题。论文的第一部分提出了稳定性界限，以帮助理解基于图的模型对哪些拓扑变化具有鲁棒性。除了理论成果，我们还进行实验来验证这一理论提供的直觉。在第二部分中，我们提出了一种灵活且查询高效的方法，用于对图分类器进行黑盒对抗性攻击。对抗性攻击可以被视为对模型不稳定性的搜索，并为输入与决策边界之间提供了一个上限。在论文的第三部分和最后部分，我们提出了一种新的图分类器鲁棒性证书。使用一种可以在不同干扰级别对图的各个部分进行验证的技术，我们提供了对给定模型具有鲁棒性的干扰的精细理解。我们相信这篇论文中的发现提供了新的见解，并激励了进一步研究基于图的机器学习模型的稳定性和不稳定性。

图是一种通用的数据结构，它使用边来模拟实体之间的二元互动，这些实体在图中被建模为节点（也称为顶点）。现实世界中的许多类型的数据存在于图域上，或可以被建模为存在于图域上，例如在传感器、生物和社会网络中收集的数据。在过去的十年中，信号处理和机器学习社区开发了大量工具来分析和学习存在于图结构域上的数据。图信号处理（GSP）社区将图视为信号生存的不规则域，并通过概括和适应信号处理思想来分析这些数据，以开发工具如谱图滤波器和谱图神经网络[36, 111, 101, 50, 121, 43, 100]。另一方面，深度学习社区通过设计基于消息传递的神经网络来处理图上的学习，这些神经网络适用于图域，特别是考虑到所需的不变性和等变性属性[18, 57, 7, 62, 19]。

尽管不断增加的建模方法和旨在处理图结构数据的架构，但对它们的属性和特性的关注较少。很少有论文致力于这些模型的理论分析。即使从实证角度来看，大多数模型也仅仅是基于它们的预测准确性进行评估。

在这篇论文中，我们专注于基于图的机器学习模型的鲁棒性属性，包括来自图信号处理社区的主要工具——谱图滤波器，以及图机器学习社区中最常用的工具——图神经网络。

鲁棒性可以有多种含义，因此我们首先提供本论文中采用的高层定义。具体来说，我们旨在理解输入图在推理时的小干扰效应。如果这些干扰不会在模型的输出中造成大的变化，我们称模型对这些干扰具有鲁棒性。我们将考虑并讨论采用不同鲁棒性定义的其他工作，并在上下文中概述它们的含义。更广泛地说，鲁棒性覆盖我们的定义和其他上下文意味着机器学习流程中的小变化会在机器学习流程的其他部分引起小变化。

关于基础图的鲁棒性研究有许多动机。我们提供了一个非详尽的列表，为每个实例提供一个实际的现实世界例子：

从噪声数据推断的图。大脑活动可以通过功能性脑网络来建模，其中节点代表感兴趣的脑区，边缘是根据功能性磁共振成像（fMRI）生成的时间序列数据推断出来的。在这种情况下，我们期望时间序列数据包含随机不确定性，这反过来会导致推断出的图噪声大且可能不可靠。因为这种拓扑噪声是由原始数据中不希望的噪声引起的，因此希望图的噪声具有鲁棒性是可取的。
对抗鲁棒性。基于图的模型可能部署在存在不良行为者的环境中。例如，可以将在线社交网络建模为一个图，而不良行为者在这个领域的存在是公认的。不良行为者可能试图通过故意制造干扰来操纵模型，例如通过向其他账户发送连接请求来添加边，或通过创建假冒档案来添加节点。在这里，我们希望我们的模型即使在最坏的情况下（即不良行为者滥用模型时）也能表现良好。
可迁移性。考虑使用3D扫描仪数字化的物理对象，形成点云。这个点云可以使用三角化算法转换成图，生成网格图。在这种情况下，图方便地表示几何对象。然而，由于环境中的轻微变化，如照明或相机或对象的精确位置，对同一对象的两次扫描可以给出不同的网格图。在这些情况下，底层实体的图表示不是唯一的。然而，希望模型能为代表同一底层实体的图产生相同或相似的表示。这个属性更广泛地被称为可迁移性。鲁棒性对于可迁移性是必需的，因为模型未能适应输入中的即使是小变化，我们也不能期望它适应大变化。
进化图。时态图是拓扑结构随时间逐渐变化的图。例如，可以通过底层资产价格的相关性来建模金融网络。因为资产的相关性可能在很长一段时间内变得更加相关或不相关，图的拓扑结构会随时间演变。在这种情况下，通常希望模型给出的表示也能随时间逐渐变化。
部分可观测性。有时我们拥有的图数据只部分代表图中节点之间的底层关系。例如，一个在线社交网络为我们提供了现实世界友谊的近似。这是一个近似，因为现实生活中不是朋友的人可能会在社交网络上连接，而现实生活中的朋友可能还没有在在线平台上连接。在许多情况下，我们希望学到的表示能捕捉到人们的现实世界友谊，尽管只有通过在线友谊图的部分知识。

尽管有许多动机研究基础拓扑变化的鲁棒性，但很少有研究致力于理解基于图的机器学习和图信号处理模型的这些鲁棒性属性。在这篇论文中，我们提出了五个技术章节，解决了这种理解的局限性。我们将考虑通过各种视角对许多常用模型的拓扑扰动的鲁棒性。我们将解决尚未探索但重要的挑战，即将拓扑属性与稳定性联系起来，即图的特定特征的变化如何影响鲁棒性。