博士论文 | CMU 2024 | 迈向更强大的图表示学习 127页

图(Graphs)在现实世界中广泛应用于表示关系，许多数据自然可以通过图来表示，如社交网络、蛋白质结构、分子和交易等。与具有特定自然顺序的图像和文本不同，图是无序的，并且具有排列不变性，这为学习良好的表示带来了显著的困难。图神经网络（GNNs）被提出并不断改进，用于图表示学习。本文在节点级别和图级别表示学习方面进行了研究，并提出了朝着更强大的表示学习迈进的解决方案，目标是实现图的基础模型。

在第一部分，我专注于节点级别的图表示学习，并解决一个关键问题——“表示过度平滑”。为了进一步理解图卷积网络（GCNs）的优势，我们探讨了神经网络与主成分分析（PCA）之间的关系。我们的研究表明，图正则化PCA的解与单个图卷积层的公式是相一致的。

在第二部分，我深入研究了图级别的表示学习。与多层感知机（MLPs）不同，MLPs是表格数据的通用函数近似器，而图神经网络（GNNs）具有有限的表达能力。我探讨了两种方法来增强GNN的表达能力：使用有根子图来提高局部结构意识；以及探索无序的高阶交互，以实现与有序交互相当的表达能力，同时在实际应用中获得更好的可扩展性。

在第三部分，我专注于图的生成模型。与需要标签来学习任务依赖表示的判别模型不同，生成模型在无监督表示学习方面表现出色。然而，图生成由于其无序性而面临独特的挑战，这要求一种与任何特定顺序无关的方法。为了解决这个问题，我首先研究了应用于类别数据的扩散模型，并提出简化并统一现有的离散时间和连续时间离散扩散。基于统一的离散扩散，我提出了一种基于部分顺序的扩散模型，将自回归方法与扩散模型相结合，用于图生成。该方法为图上的生成预训练奠定了基础。

在最后一部分，我探索了图表示学习的应用。具体而言，我研究了图级别异常检测（GLAD），该方法具有许多重要应用。由于GLAD研究较少，我建立了一个基于图神经网络的强基准模型“OCGIN”，一个包含数据集和许多非图神经网络基准的评估平台。我还发现并研究了一个名为“性能反转”的问题。随后，我设计了一个特定模型，用于检测普华永道的可疑会计交易，该任务需要处理带属性的图数据。

论文题目：Towards More Powerful Graph Representation Learning

作者：Lingxiao Zhao

类型：2024年博士论文

学校：Carnegie Mellon University（美国卡内基梅隆大学）

下载链接：

链接: https://pan.baidu.com/s/1ssrdX97wRGZ8EIpKg2yYIA?pwd=wn6s

硕博论文汇总：

链接: https://pan.baidu.com/s/1Gv3R58pgUfHPu4PYFhCSJw?pwd=svp5

本论文探讨了 GNN 领域走向成熟过程中面临的几个基本挑战和进步，涵盖了理论、各种应用和领域。图是用于对各种领域和问题之间的关系或结构进行建模的抽象元素。例如，社交网络以图的形式表示，以捕捉个人之间的关系或活动，主要关注的是节点级问题，例如个人行为。在推荐系统中，图将用户和产品抽象为节点，将用户与产品的互动抽象为边，主要关注预测互动（边级问题）。此外，图可以表示分子，以原子为节点，化学键为边，主要关注的是理解分子特性（图级任务）。由于任务、领域、复杂性和抽象级别的多样性，充分发展该领域就像盲人摸象一样；它需要许多成长和理解阶段。

该领域始于节点级问题，这也是论文第一部分的重点。在早期阶段，像 GCN [KW17] 这样的图网络方法已经开始超越传统的传播算法，如标签传播 [ZGL03] 和神经图嵌入方法，如 DeepWalk [PARS14]。与此同时，随着备受推崇的 ResNet [He+16] 消除了训练深度网络的难度，并证明了使网络更深可以扩大模型容量并优于加宽网络，研究人员探索深化 GNN 以进一步提高处理复杂图结构的性能。然而，人们普遍观察到违反直觉的现象：增加 GNN 中的层数通常会导致性能不提高甚至下降。为了解决和解释这一观察结果，[LHW18] 提出了一种称为“过度平滑”的假设。这一假设表明，重复的消息传递或图卷积层会导致节点的表示变得难以区分，从而在堆叠过多层时降低性能。

第 1 章深入探讨了过度平滑假设，提出了假设、指标和受控实验，旨在量化过度平滑及其对半监督节点分类任务中性能的影响。我们的全面研究和评估表明，两种形式的过度平滑，即所有特征都相同的列式过度平滑和所有节点收敛到统一表示的行式过度平滑，都是通过增加更多层来实现的。作为后续，我们提出了 GNN 中的第一个规范化层 PairNorm，它规范了表示之间的总成对距离，以消除深化图网络的缺点。另一个有趣的问题是找出图卷积对节点级问题的有效性的根源，之后我们可以进一步改进模型设计以实现性能提升。有趣的是，我们发现虽然过度平滑对节点嵌入有害，但适当的平滑有助于图卷积在节点级任务中的成功。

在第 2 章中，我们研究了图卷积和图正则化 PCA 之间的联系。具体来说，我们在图卷积的形式和图正则化 PCA 的闭式解之间建立了数学联系。这种联系强调了有效的平滑或图卷积能力源自基于图的拉普拉斯正则化项。此外，增加 GCN 的深度类似于提高拉普拉斯正则化项的系数。基于这些联系，我们可以通过拉普拉斯正则化的视角来分析 GCN 的局限性。例如，我的合作者深入研究了节点级任务的 GNN 中的同质性和异质性问题 [Zhu+20]。 GNN 的异质性问题可以用拉普拉斯正则化的局限性来解释，因为其有效性取决于图结构与任务标签的匹配程度。虽然节点级问题是 GNN 中研究最广泛的问题，但仍有一些理论问题尚未完全解决。例如，节点级任务的学习本质上是一种非独立同分布的学习，因为图中的所有节点都相互影响，其中许多来自独立同分布设置的理论不能直接应用。

随着该领域的发展，诸如图属性预测任务之类的图级问题已越来越受欢迎。在这些场景中，会呈现一组图，这些图具有或不具有相关属性，并且假定所有图都是独立且相同分布的 (i.i.d.)。第二部分重点介绍图级任务。假设每个输入都是一个图，我们的目标是开发能够对图上的任何函数进行建模的强大 GNN。多层感知器 (MLP) 简单而又众所周知，只要有足够的深度和宽度，它就可以作为高维向量上函数的通用函数逼近器。早在 2019 年初，Chen 等人 [Che+19a] 就证明了成为图上函数的通用函数逼近器相当于能够解决图同构测试问题。因此，GNN 的表达能力从那时起就通过其解决图同构测试问题的能力来衡量。然而，由于图同构测试在多项式时间内不可解 [For96]，GNN 也不能成为图函数的通用函数逼近器，这与向量函数上的 MLP 有显著区别。事实上，[Xu+19] 证明了流行的基于消息传递的 GNN 的表达能力上限受一阶 Weisfeiler-Leman 算法 (1-WL) 的限制。这意味着 GNN 无法区分 1-WL 算法无法区分的图。因此，GNN 无法计算三角形和循环的数量，而这对于许多实际问题来说很重要。提高 GNN 向图上函数通用函数逼近器的表达能力成为该领域前进的重要瓶颈。在第 3 章中，我探讨了子图的明确使用，以提高模型的表达能力。观察到典型的 GNN 仅聚合局部首跳信息，在区分非同构图方面受到限制，因此我首次提出将星型聚合推广到子图聚合。这一洞察产生了 GNNAsKernel [Zha+22c]，这是一个具有理论保证的通用框架，它通过将子图与基 GNN 卷积为核来增强任何 GNN。该框架结合了子图内和子图间的交互，在各种图形任务基准上显著提高了性能，错误率降低了 60%。

使用子图来增强 GNN 表达力的方向一直是一个重要的研究方向，该领域许多人都在关注。例如，Zhang 等人 [Zha+23a] 已经证明，所有具有消息传递基 GNN 的子图 GNN 的表达力上限都为 3-WL。子图 GNN 大大增强了现有 GNN 模型的表达能力，但它们仍然受到 3-WL 测试上限的限制。此外，追求更高的表达能力可能并不总是合理的，因为它可能导致相当大的计算成本和可能较弱的泛化能力。社区对结合无限高表达能力和可调节表达能力的 GNN 的需求日益增长。这种方法将允许系统地评估表达能力对现实世界问题的影响。在第 4 章中，我致力于开发既实用又具有渐进表达能力的 GNN，并以理论保证为后盾。认识到高阶交互的高表达能力，我的重点是克服它们的主要限制：考虑所有 k 阶元组所带来的指数级计算成本。在 [Zha+22b] 中，我研究了通过关注集合而不是元组来最小化高阶实体数量的方法。从元组到集合的转变意味着忽略元素顺序和重复中嵌入的信息。虽然这种策略显著减少了所涉及的实体数量，但评估其对表达能力的理论影响具有挑战性。通过应用一阶逻辑和博弈论的理论，我证明了，虽然表达能力有所降低，但基于 k 阶集合的 GNN 仍然保持了不低于基于 (k-1) 阶元组的 GNN 的表达能力。基于高阶 WL 的集合版本开发了一种新的高阶模型 (k, c)-SetGNN。这项工作在许多基准测试中取得了新的最先进性能，以前无法实现 k=10 阶，大大扩展了高阶 GNN 的可能性。

除了设计更具表现力的模型架构外，开发适用于图的无监督学习范式对于解锁大量未标记数据中的丰富信息也越来越重要。生成模型是最有前途的无监督学习方法之一，它已经彻底改变了语言建模和计算机视觉等许多领域 [Ope23]，GPT-4 和 Claude 3 等突破性模型被数亿人广泛使用并被各种应用所采用。生成模型本质上捕获了训练数据集的全部信息，因为使用完美训练的生成模型，您可以通过从模型中采样来恢复训练数据集。然而，考虑到图的独特特征（例如置换不变性和丰富的高阶结构信息），为图数据开发有效的生成模型仍然具有挑战性。

在第三部分中，我们将探讨为图设计置换不变的生成模型。图和序列（例如语言和图像块）之间的主要区别在于，图缺乏元素（节点和边）的自然排序。节点和边的任何排列都不会改变图，这使得用于序列的自回归方法对图的效果较差，而不会损害其对任意排序的泛化。最近，扩散模型（例如 [HJA20] 提出的模型）在图领域引起了越来越多的关注。这些模型能够对可交换概率进行建模，确保学习到的概率在某些条件下不受元素排序变化的影响。然而，图本质上是离散对象，许多复杂的连续状态扩散模型无法应用。因此，在第 5 章中，我首先对当前的离散状态扩散模型进行了一些改进，使其对图更有效、更易于使用。具体来说，我为离散时间和连续时间离散扩散模型开发了一系列数学简化，实现了两者的精确和更快的采样。我还为变分下限创建了一个简单而精确的公式，大大提高了训练速度。我们的方法允许前向和后向概率适应任何噪声分布，即使对于复杂的多元素对象也是如此。最重要的是，设计的扩散模型提供了一组前向和后向程序，统一了离散和连续时间离散扩散。随着有效离散扩散模型的开发，我在第 6 章中探讨了将自回归方法和扩散模型结合起来的可能性，以利用两者的有效性和效率，同时消除它们的缺点。具体而言，虽然自回归方法难以推广到任意顺序，但扩散模型通常需要数千个去噪步骤。由于难以直接对所有边和节点的联合分布进行建模，因此这大大减慢了训练和生成的速度。认识到图中的节点与集合中的元素不同，它们具有基于其连接的偏序，我探索将联合分布分解为一系列更简单的条件分布。这种分解遵循逐块自回归模式，其中每个条件分布代表一个更简单的节点和边子集。至关重要的是，为了在概率建模中保持置换不变性，每个条件分布都采用扩散模型。这些模型提供了必要的对称性破坏，这对于准确预测结构等效节点块中的新连接至关重要。此外，我还开发了基于因果原理的并行训练，类似于因果转换器。这种方法可以同时训练所有块，大大提高了效率和使用率。

除了基础模型和方法改进外，我还致力于将这些模型应用于实际场景，如上一节第四部分所示。具体来说，我专注于将图神经网络应用于基于结构的异常检测。在第 7 章中，我开发了第一个基于 GNN 的图级异常检测 (GLAD) 方法，建立了一个具有广泛基线的综合测试平台，并分析了 GLAD 中的关键问题 [ZA23]。认识到 GLAD 无监督性质在超参数设置方面的挑战，我通过结合自动模型选择和更有效的损失函数（通过 MMD 池化）进一步增强了该方法 [Zha+22d]。此外，在第 8 章中，我们扩展了 GLAD 模型以处理金融系统中常见的有向多边图。作为一项现实世界的研究，我们将我们的方法应用于普华永道的会计数据集，目的是识别包含不准确交易记录的欺诈簿记日记帐。

总而言之，这篇论文涵盖了我对各种问题的研究探索，我认为这些问题对于该领域走向成熟非常重要，从过度平滑、表达能力等基本问题到模型、学习方法和应用。我很幸运能够不受任何限制地研究我最感兴趣的问题，并有机会与该领域一起成长。

图示：一个 GNN-AK+ 层。对于每一层，GNN-AK+ 首先提取 n (# 个节点) 个根子图，并将所有子图与基础 GNN 作为内核进行卷积，从而生成多个形式为 Emb(i | Sub[j]) 的丰富子图节点嵌入（在子图 j 上应用 GNN 内核时节点 i 的嵌入）。从这些中，我们提取并连接给定节点 j 的三个编码：(i) 质心 Emb(j | Sub[j])、(ii) 子图 Pi Emb(i | Sub[j]) 和 (iii) 上下文 Pi Emb(j | Sub[i])。GNN-AK+ 对 L 层重复该过程，然后对所有生成的节点嵌入求和以计算最终的图嵌入。作为较弱的版本，GNN-AK 仅包含编码 (i) 和 (ii)。

两个 4 正则图无法通过 1-WL 区分。彩色边是两个图之间的差异。两个 1 跳自网络被可视化，而所有其他根自网络都被忽略，因为它们在图 A 和图 B 中是相同的。

两个非同构的强正则图，无法通过 3-WL 区分。

GNN-AK(+)-S 在训练中使用 SubgraphDrop。GNN-AK(+)-S 首先提取子图，然后对 m⌧|V| 子图进行子采样，以使用多种策略覆盖每个节点至少 R 次。基础 GNN 用于计算选定子图中的所有中间节点嵌入。上下文编码按比例缩放以匹配评估。子图和质心编码最初仅存在于选定子图的根节点中，并传播以估计其他节点的编码。