密歇根大学

Towards Trustworthy Machine Learning on Graph Data

https://deepblue.lib.umich.edu/handle/2027.42/174201

摘要

机器学习已经被应用于越来越多影响我们日常生活的与社会相关的场景，从社交媒体和电子商务到自动驾驶汽车和刑事司法。因此，为了避免对个人和社会的负面影响，开发可靠的机器学习方法至关重要。在本文中，我们关注理解和提高图机学习的可信度，这由于图数据的复杂关系结构提出了独特的挑战。

特别地，我们认为机器学习模型的可信性在异常情况下是可靠的。例如，机器学习模型在对抗攻击下或在子种群上的性能不应严重退化，分别对应对抗鲁棒性或公平性问题。值得信任的图机器学习的独特挑战是，在图数据的上下文中有许多更复杂的，有时是隐式的异常条件。本文识别了未充分挖掘的异常情况，理解了识别出的异常情况下的预期模型行为，并改进了现有模型在此类异常情况下的行为。

重点关注图神经网络(GNN)，这是一类流行的图机器学习模型，利用了深度学习的最新进展。本文确定了图神经网络的三种异常情况。首先，受社交网络应用场景启发，通过一个新的实际威胁模型研究了GNN的对抗鲁棒性，并研究了GNN何时以及为什么会遭受对抗攻击。发现现有的GNN对许多现实世界的图数据可能会被错误指定，并开发了一个新的框架来改进现有的模型。发现了一种与节点结构位置相关的测试节点子种群之间的GNN预测的不公平性。本文还提出了一种主动学习框架来缓解不公平问题。

第一章 引言

人工智能(AI)，特别是机器学习(ML)，已经作为一种通用技术融入人类社会，有望在许多方面重塑我们的日常生活，从社交媒体和电子商务，到自动驾驶汽车和刑事司法。然而，尽管AI和ML带来了巨大的经验成功和商业价值，但要更广泛地部署这些技术，需要更好地理解ML模型对社会的影响。因此，可信的ML成为了一个越来越受欢迎的研究方向。Trustworthy ML是一个概括性的概念，包括关于ML可靠性和透明度的各种主题，如公平性、鲁棒性、可解释性等。

例如，机器学习模型可能在特定子种群上的系统表现较差，这导致了公平性问题。因此，对机器学习公平性的研究兴趣迅速增加。也有现实世界的ML应用程序证明了偏见和不公平:亚马逊的人工智能招聘工具被发现具有性别偏见[37];一种曾经广泛使用的犯罪预测工具，矫正罪犯管理分析替代制裁(COMPAS)，被发现具有种族偏见[4]。另一个例子是，ML模型已被证明对添加到数据中的小的对抗性扰动很敏感，因此容易受到对抗性攻击[136]。例如，最先进的计算机视觉模型可能通过停车标志[45]上看似随机的涂鸦，将停车标志识别为限速标志。

由于相关主题的多样性和我们对可信机器学习的科学理解的文献历史，社区自然发展出了一套相对被广泛接受的可信性问题的概念类别，包括但不限于公平性、鲁棒性、安全性、隐私、可问责性、可解释性和因果性。虽然这种概念分类，像任何分类系统一样，有助于简化对该领域的理解，但有时也会产生误导。

首先，这种分类可以使可信机器学习的不同问题被视为孤立的主题。然而，这些不同的可信性问题可能相互冲突或相关。例如，在某些隐私和公平概念之间存在固有的冲突[32,24]。另一方面，公平性也可以与域外泛化相关[99]。此外，可解释的ML[41]和因果推理[113]可以成为一些公平性或鲁棒性问题的候选解决方案。一个扁平的概念类别分类方法无法捕捉不同主题之间丰富的相互关系。

其次，这种分类倾向于为每个主题寻找过度通用的解决方案，这可能不是解决可信机器学习问题的最佳方法。由于主题的概念性质，通常有各种直观合理的方法来将可信性概念(例如，公平性或鲁棒性)形式化为定量概念，而同时实现所有概念的可信性是不现实的。例如，Kleinberg等人[78]证明，通常不可能有一种算法同时满足三个常见的公平标准。因此，没有一个通用的解决方案是所有应用的万能药。此外，不同的可信性问题的重要性和恰当表述是高度特定于应用程序的。就可信性不同方面的重要性而言，例如，自动驾驶汽车可能会遭受对抗性攻击，因为它在野生[45]中接受数据输入;相比之下，对电子健康记录(EHR)数据进行对抗性攻击实际上要困难得多，因为这些数据由授权的医疗专家生成，并且在封闭的系统中循环。另一方面，EHR数据的隐私标准远高于驾驶数据。在可信性的正确制定方面，研究表明，制定的选择应该利用利益相关者在具体应用[28]中的感知。总的来说，应该将可信性作为位于特定类型的应用程序场景中的ML技术的属性来研究，而不是作为通用ML技术的属性。

许多现有的可信性概念可以按照这个程序重新制定。例如，机器学习模型的不公平性问题往往是由于它们在特定少数子种群上的性能下降，而与它们在多数子种群上的性能相比。机器学习的对抗漏洞是指与在干净数据上的性能相比，它们在对抗攻击下的性能下降。另一方面，其他一些可信性概念，如可解释性或因果关系，不能通过上述过程直接表述。在某种程度上，不公平或不鲁棒的模型将产生直接后果，而可解释性或因果关系可以被视为缓解问题的候选解决方案(例如，不公平或不鲁棒)。上述过程关注的是作为问题而不是解决方案的可信性概念。这个过程还强调应用场景的可信性问题。

为约束特定应用场景下的可信范围，本文对图机器学习(GML)的可信性进行了研究。现实世界的数据中存在大量的关系结构，通常以图的形式表示。例如，社交媒体上的用户或物联网系统中的传感器通过图结构进行连接。如果在预测任务中使用得当，这种关系图结构可以提供显著的预测能力。GML是一个流行的机器学习技术家族，它将图结构用于预测模型。近年来，GML在许多影响人们日常生活的应用中表现出了优异的性能。举个常见的例子，GML在Uber Eats[65]、亚马逊[162]和Pinterest[157]的工业推荐系统中发挥着重要作用;GML还被广泛用于在谷歌Map[38]中的ETA预测或房地产价格估计等任务中对地理数据进行建模[114]。此外，由于关系结构的普遍性，GML方法已经应用于或准备应用于高利害攸关的决策问题，如社会正义。例如犯罪预测和数据驱动的起诉[68,156]，警察不当行为预测[22]，假释决定的风险评估[132]，公共安全监视[95]，以及许多其他社会公正和安全问题[111]。

鉴于GML的众多社会相关应用场景，这类ML系统的可信性问题变得至关重要。此外，与传统的ML相比，由于GML复杂的关系结构，在理解和改进GML的可信性问题方面存在独特的挑战。特别是，在GML的上下文中，有许多更复杂，有时甚至是隐式的异常条件。以对抗性攻击为例，在传统的机器学习设置中，攻击者大多通过向输入特征添加对抗性扰动来进行攻击。对于GML，在实际应用中存在着更复杂的威胁:攻击者不仅可以扰动GML节点属性，还可以扰动图结构;攻击者还可以通过扰动邻居节点来间接影响节点的预测结果。在子种群之间的机器学习公平性方面，大多数传统文献研究的是有关某些敏感属性的子种群，如性别或种族。在图数据中，人们可以根据图结构来调查子群体，例如节点中心性[12,13]或社区结构[51,47]。社会科学理论认为，社会网络中人们的结构特征往往与其社会经济地位相关[53,16]。图数据中独特的对抗性威胁和基于结构的子群呈现出在传统ML文献中没有充分探索的例外情况，使可信的GML更具挑战性。

本文旨在解决这些对理解和提高GML可信性的独特挑战。具体而言，本文旨在回答以下3类研究问题，并在3种应用场景下展示研究方法。

1. GML模型在实际应用场景中可能遇到的潜在异常情况是什么?

2. 在确定的异常条件下，GML模型的预期行为是什么?

3.在识别出的异常情况下，如何缓解GML模型的性能差异?

在GML方法中，我们关注图神经网络(GNN)[52,124,77]，这是一个大的趋势GML模型家族，将深度学习[83]的最新进展利用到GML中，并在许多真实世界的应用程序中显示出卓越的性能。

第二章 前期工作

第三章 对图神经网络的实际对抗攻击

图神经网络（GNNs）[151]，图上的深度学习模型家族，在机器学习对图数据的各种应用中显示出了良好的经验性能，如推荐系统[157]、社会网络分析[85]和药物发现[131]。与其他深度学习模型一样，gnn也被证明在对抗性攻击[169]下是脆弱的，这最近吸引了越来越多的研究兴趣[70]。事实上，对抗性攻击已经成为分析图神经网络的理论性质和实际责任的有效工具。由于图形数据比图像或文本数据具有更复杂的结构，研究人员提出了不同的对抗性攻击设置。例如，有不同的任务（节点分类和图分类）、攻击者的知识假设（白盒、灰盒和黑盒）、策略（节点特征修改和图结构修改），以及相应的预算或其他约束（特征变化的规范或边缘变化的数量）。尽管进行了这些研究，但在攻击性的设置和现实之间仍然有相当大的差距。假设攻击者可以改变大量节点的输入是不合理的，即使存在预算限制，假设他们可以按照自己的意愿攻击任何节点也是不合理的。例如，在现实世界的社交网络中，攻击者通常只能访问几个机器人账户，而且他们不太可能是网络中的顶级节点之一；攻击者很难入侵和改变名人账户的属性。此外，攻击者通常对平台所使用的底层机器学习模型的知识有限（例如，他们可能大致知道使用了什么类型的模型，但无法访问模型参数或训练标签）。基于真实的攻击场景，本章研究了一种新型的黑盒对抗性攻击，该攻击更有限、更现实，假设攻击者无法访问模型参数或预测。我们的设置不同于现有的工作，在节点访问方面有一个新的约束，即攻击者只能访问图中的一个节点子集，并且他们只能操作少量的

提出的黑盒对抗攻击需要两步步骤： 1)在节点访问的限制下选择小子节点进行攻击；2)在每个节点预算下改变节点属性或边。在本章中，我们将重点关注第一步，并研究节点选择策略。该策略的关键观点在于，在没有访问GNN参数或预测的情况下，GNN模型的强结构诱导偏差可以作为一种有效的攻击信息源。由各种神经结构（如卷积神经网络中的卷积核）编码的结构归纳偏差在深度学习模型的成功中发挥着重要作用。由于图结构和重权重共享设计，gnn具有更明确的结构归纳偏差。理论分析表明，对结构归纳偏差的理解可以导致更好地设计GNN模型[153,79].从一个新的角度来看，我们的工作表明，这种结构性归纳偏差可以在黑盒攻击中变成安全问题，因为图的结构通常暴露给攻击者。

据此，我们推导了一个节点选择策略，并对所提出的黑箱攻击设置进行了正式分析。通过利用gnn的反向传播和随机游动之间的联系，我们首先将白盒攻击中的梯度范数推广到一个类似于PageRank的模型无关的重要性得分。在实际应用中，攻击重要性得分较高的节点会显著增加分类损失，但对误分类率不会产生相同的影响。我们的理论和实证分析表明，这种差异是由于错误分类率的收益递减效应。我们进一步提出了一种计算重要性分数的贪婪修正程序。在三个真实世界的基准数据集和流行的GNN模型上的实验表明，所提出的攻击策略明显优于基线方法。我们总结了我们的主要贡献如下：

1.我们提出了一种新的黑盒攻击的设置，与现有的工作相比，这是迄今为止最受限制和现实的。

2.我们证明了gnn的结构诱导偏差可以作为黑盒对抗性攻击的有效信息源。

3.我们分析了分类损失和错误分类率之间的差异，并提出了一种实用的节点分类任务的贪婪对抗攻击方法。

4.我们在使用流行的GNN模型的三个基准数据集上验证了该方法的有效性。

第四章 图在图神经网络中的表征和相关作用

图作为存储丰富关系信息的灵活数据表示，在数据科学任务中常用。在图[23]上的机器学习方法，特别是图神经网络（GNNs），已经引起了研究界越来越多的兴趣。它们被广泛应用于推荐系统[157]、社交网络分析[85]、交通预测[158]等现实问题。在异构类型的图结构数据中，值得注意的是，图通常在不同的上下文、不同的数据集和不同的任务中发挥不同的角色。有些角色是关系的，因为图可能表示连接观察的某些统计关系；有些是表征的，因为图的拓扑结构可能编码数据的重要特征/模式；有些甚至是因果关系，因为图可能反映了领域专家指定的因果关系。

为了正确地利用图结构数据中的信号，识别图的不同作用是至关重要的。在本章中，我们将在节点级的环境中区分图的表征作用和相关作用（半）监督学习，我们研究如何设计更好的gnn，利用这两种角色。

在节点级预测任务中，数据中观察到的图可能以多种方式与感兴趣的结果（例如，节点标签）相关联。从概念上讲，如果可以利用图来构造更好的特征表示，我们就认为图具有表征作用。例如，在社交网络分析中，从朋友那里聚集用户特征通常是有用的（多亏了众所周知的同质性现象[104]）。此外，用户的本地网络的结构属性，例如结构多样性[140]和结构孔[17,93]，通常为预测该用户的某些结果提供了有用的信息。另一方面，有时一个图直接编码了连接节点的结果之间的相关性，我们称之为扮演相关性的作用。例如，超链接的网页很可能被一起访问，即使它们有不同的内容。在时空预测中，基于所有特征，附近位置的结果可能仍然是相关的。

虽然在图形结构数据中，表征和相关角色都很常见，但我们发现，通过模拟研究，许多现有的GNN模型无法利用图中编码的相关信息。具体来说，我们设计了一个用于节点级回归的合成数据集。节点级的结果来自于多元正态分布，以均值和协方差作为图的函数，分别反映表征和相关的作用。我们发现，当图只提供节点结果的相关信息时，许多流行的GNN模型都不如一个根本不考虑图的多层感知器运行。

为了缓解gnn的这一缺陷，我们提出了一个有原则的解决方案——连接图神经网络（CopulaGNN），它可以以广泛的gnn作为基础模型，提高其建模相关图信息的能力。

该方法的关键观点是，通过将节点结果的联合分布分解为边缘密度和连接密度的乘积，可以将表征信息和相关信息分别建模。前者通过基GNN的边缘密度建模，后者通过高斯连接建模。该方法还易于扩展到各种类型的节点结果变量，包括连续变量、离散计数变量，甚至是混合类型的变量。我们分别用正态边际分布实例化正态边际分布和泊松边际分布的CopulaGNN用于连续和计数回归任务。我们还实现了两种类型的两种类型的连接参数化。

我们评估所提出的方法在连续和计数回归的合成和真实数据任务。实验结果表明，当数据中的图同时表现出相关和表征作用时，连接的GNN显著优于其对应的基本GNN。我们总结了我们的主要贡献如下：

1.我们提出了区分图所扮演的两个角色的问题，并证明了当许多现有的gnn扮演纯粹的相关角色时，它不能利用图信息。

2.我们提出了一个有原则的解决方案，CopulaGNN，来整合图的表征和相关作用。

3.我们证明了基本gnn在半监督回归任务上的有效性。

第五章 图神经网络的推广与公平性

图神经网络（GNNs）[52,124,77]是一组机器学习模型，可以用于以一种灵活的方式建模非欧几里得数据以及相互相关的样本。近年来，gnn在药物发现[69]、计算机视觉[106]、交通预测[158]、推荐系统[157]等各个领域都取得了巨大的成功应用。根据预测目标的类型，应用程序任务可以大致分为为节点级、边缘级、子图级和图级任务[151]与显著的经验成功相比，对gnn泛化能力的理论理解一直相当有限。在现有的文献中，一些研究[42,49,89]集中在图级任务的分析上，其中每个样本都是一个完整的图，而图的样本都是IID。[125,142]探索节点级GNN任务的GNN泛化的研究非常有限，但他们假设节点（及其相关的邻域）是IID样本，这与常见的基于图的半监督学习设置不一致。Baranwal等人[6]研究了没有IID假设但在特定数据下的GNN泛化

在本章中，我们的第一个贡献是提供一种新的pac-贝叶斯分析，用于在非IID假设的节点级任务上的泛化能力。特别地，我们假设节点特征是固定的，并且节点标签是根据节点特征的分布中独立采样的。我们还假设训练集和测试集可以被选择为图上节点的任意子集。在此非IID设置下，我们首先证明了两个一般的pac-贝叶斯推广界（定理5.4.2和定理5.4.3）。随后，我们根据GNN模型的特征和节点特征，推导出了GNN的一个推广界（定理5.4.10）。

值得注意的是，GNN的泛化边界受到测试节点和训练节点之间的聚合节点特征的距离的影响。这表明，给定一个固定的训练集，“远离”所有训练节点的测试节点可能会遭受更大的泛化错误。基于这一分析，我们的第二个贡献是发现了一种不公平，这种不公平来自于理论上在测试节点的某些子组之间可预测的精度差异。我们进一步进行了实证研究，调查了四种流行的GNN模型对不同的测试节点子组的预测精度。在多个基准数据集上的结果表明，这些子组之间的测试准确性确实存在显著差异。我们总结了本章的贡献如下：

(1)我们建立了一种新的-贝叶斯分析基于图的半监督学习非IID假设。

(2)在这种情况下，我们推导了gnn的一个推广界，它可以应用于测试节点的任意子组。

(3)作为泛化界的一个暗示，我们预测将存在GNN预测的不公平，这来自于测试节点的子组之间的准确性差异。

(4)我们通过实证验证了流行的GNN模型在多个基准数据集上的精度差异的存在性，正如我们的理论分析所预测的那样。

第六章 基于分区的图神经网络的主动学习

在前一章中，我们已经看到，训练节点的选择对gnn的泛化和公平性起着至关重要的作用。在本章中，我们研究了主动学习设置[128]中基于gnn的半监督学习（GSSL）问题，在有限的注释预算下，允许主动查询图上的节点标签。我们的目标是设计有效的主动学习策略，可以提高gnn的泛化和公平性。

在GSSL中，主动学习设置也特别有趣，因为我们通常在学习之前访问大量的未标记样本，在许多情况下（例如，在社交网络上），我们可以灵活地查询一小部分样本的标签。此外，由于GNN的一个关键优势是能够利用相互连接的样本之间的关系信息，正确地选择节点进行注释可能会进一步提高GNN的性能。

然而，由于问题和GNN模型的特殊结构，直接使传统的主动学习方法适应于GSSL可能是次优的。实际上，利用数据的适当的平滑性特性一直是对许多主动学习方法的成功。例如，一个常用的假设（我们称之为特征平滑性）是，具有相似特征的样本有更高的机会落入同一类。除了特征平滑性之外，现实世界的GSSL任务经常利用图上的多种类型的平滑性属性，跨越局部平滑性和全局平滑性[163]之间的频谱。虽然已经有一些基于图的主动学习方法利用这些平滑特性[36,19,150]，但在适当的水平上充分利用特征和结构平滑的方法是很少的

在本章中，我们提出了一种基于图分区的gnn主动学习方法。该方法在很大程度上是由在现实世界的图形中通常存在的社区结构所驱动的。节点和结构属性在群落内往往表现出同质性和群落间的异质性。我们用社区级别的图形结构数据的适当平滑性假设（由图的分区表示）将这一观察结果形式化，并在这些假设下对GNN分类错误进行了新的分析。该分析进一步推动了该方法中的图划分步骤。特别是，图部分首先根据模块化[29]将图分割为几个分区，然后在每个分区中选择最具代表性的节点进行查询。该方法的一个重要优点是，它没有引入额外的超参数，而这对主动学习设置是至关重要的，因为标记的验证数据经常缺失。通过大量的实验，我们证明了该方法在多基准上优于现有的主动学习方法