【ETHZ博士论文】学习理解图结构:从分类到生成，273页pdf

在这项工作中，我们探讨了如何改进旨在处理图结构的机器学习算法。首先，我们利用分布式计算算法的思想来改善图神经网络在图分类任务上的表现，通过增强其表达能力和效率。在工作的第二部分，我们专注于生成性任务。生成性任务，如生成与一组提供的示例相似的新示例，可以被视为对给定领域理解的终极测试。为此，我们提出了多种改进通用生成方法的方式，使其更适应于图领域，而非采用先前的方法。例如，首先通过生成相应的图谱来生成大规模图结构。或者确保用于生成邻接矩阵的扩散过程保持离散。我们进一步展示了在两种不同的图生成领域适应中生成离散结构的现实世界应用性。具体来说，是为刚性折纸生成折痕图案，以及生成在体外已被证明能够良好执行其功能的新型抗体。

图分类

图是一种特别吸引人的数据结构方式，因为这种表示形式的灵活性。实际上，任何类型的数据都可以以某种形式的图来表示。因此，近年来，图神经网络（GNNs）在量子化学、物理学或社交网络等多个领域取得了最先进的性能。然而，GNNs 也显示出严重的限制，有时甚至无法识别简单的图结构。

众所周知，GNNs 的表现力受到 Weisfeiler-Lehman 测试（WL-test）的限制，WL-test 是一种启发式方法，用于检查两个图结构在节点排列上是否相同。这意味着 GNNs 无法区分许多种类型的图，至少包括那些 WL-test 无法区分的图。在第三章中，我们介绍了一种提高 GNNs 表现力的新方法，称为 Dropout 图神经网络（DropGNNs）。我们的主要思想是不执行一个而是多个不同的 GNN 运行。然后我们将这些不同运行的结果汇总成最终结果。正如您稍后将看到的，与随机分布式算法有些类似，引入的随机性允许打破平衡，从而区分一些高度规则的结构。

有效地，所有现有方法用于增加 GNN 的表现力，包括我们的 DropGNN，在增加计算负担方面都有所体现。这些表现力强的模型主要应用于图分类和回归任务，因为即使是简单模型在节点分类和边预测任务上通常也表现良好。在第四章中，我们展示了如果我们限制自己在这些图级任务上，可以设计出一种比标准消息传递 GNN 更高效的替代方法。我们的方法受到次线性分布式算法的启发，允许以与图大小无关的计算成本进行图级预测。我们将这种方法称为基于代理的图神经网络，或简称为 AgentNet。它基于一系列训练有素的神经代理，这些代理智能地在图中行走，然后集体对其进行分类。这些代理能够从它们所占据的节点、邻近节点以及占据同一节点的其他代理那里获取信息。这些信息用于更新代理的状态和所占节点的状态。最后，代理基于自身状态和邻近节点的状态选择一个邻近节点进行过渡。正如我们稍后将展示的，即使是非常简单的策略，一个代理也已经能够识别团块和循环，这是传统 GNNs 所无法做到的。

图生成

在这项工作的后半部分，我们专注于图生成问题。这个问题对我们来说特别有趣，因为能够从给定的数据分布中生成新的有效样本是模型精确捕捉数据所有方面的最终证明。此外，生成新颖的图对分子【142, 55, 182】、蛋白质【135】、网络和电路设计【199】等众多应用领域都具有相关性。然而，尽管近期有所努力，这个问题仍然在很大程度上未得到解决：之前的最先进方法局限于小型图，并且常常未能在捕捉训练分布的基本属性与展现高新颖性之间取得有利平衡。

近年来，表现最佳的生成模型被证明是生成对抗网络（GANs）【107, 9】和去噪扩散概率模型（DDPMs）【281, 124】。自然地，GANs【55, 162】和DDPMs【215, 147】已被应用于图领域。然而，它们仍然难以超越自回归图生成方法【321, 177, 52】，特别是在节点数超过几十个的图上。即使自回归模型，一次添加一个节点及其相应连接，对节点排列敏感且容易发生数据记忆化。这两个问题都可以通过一次性模型解决，这种模型一次生成节点间的所有边。

在第五章中，我们认为当前GAN模型【55, 162】中使用的一次性生成器存在表达性问题，这阻碍了它们捕捉全局图属性。因为它们需要控制从大量局部节点互动中产生的全局图结构，使用有限数量的层。随着图的大小增加，这项任务变得越来越困难。为了缓解这个问题，我们提出了一种新的GAN架构，能够生成图拉普拉斯算子的前k个特征值和特征向量，然后用于条件化一个更传统的图GAN。前k个特征值和特征向量捕捉全局图结构，因此这种设置中的最终图GAN只需要修正局部连接。结果表明，这有助于大幅提高生成模型性能。 图去噪扩散模型【215, 147】，由于其迭代细化图的过程，对错误的敏感性略低。尽管扩散过程已被提出用于连续【283】和离散【11】状态空间，但其在图生成中的应用仅集中在连续状态空间中的高斯扩散过程【215, 147】。在第六章中，我们展示了通过使用离散去噪过程【11, 127】和伯努利噪声，我们可以提高样本质量并减少去噪步骤的数量。这可以解释为离散噪声过程迫使链的每个中间步骤都是一个“有效”的图，从而大大降低了搜索空间的维度。

像大多数深度生成模型一样，深度图生成模型不可解释。这与各种统计图生成模型，如 Erdős-Rényi 模型【81, 125, 76】形成鲜明对比。它们是可解释的，与深度生成模型不同，能够外推到以前未见过的图大小。不幸的是，这些模型难以紧密拟合现实世界的图分布。在第七章中，我们旨在弥合可解释性和分布拟合质量之间的差距。为此，我们提出了一种方法，用以发现能够从给定图分布生成新样本的算法，这些算法由Python函数表示。我们展示了这种方法可以产生可解释的图生成器，它们生成的图质量与现有深度生成模型相似，并且在某些情况下可以发现真正的图生成过程。

应用

在第8章和第9章中，我们专注于图生成模型的应用。首先，我们研究了刚性折纸。折纸在机器人学、建筑学、生物医学工程、可展开结构、变形材料、航空航天应用等多个领域都有应用。作为刚性折纸的可折叠图案，在实际应用中特别受关注，因为在折叠这些图案时材料不会变形。更重要的是，原则上，刚性图案的折叠运动可以通过单一的折叠激活引发，也被称为图案的自由度（DOF）。这允许创造出不仅美观而且功能性的形状。

在第8章中，我们展示了如何将这种刚性可折叠图案的构造描述为一种游戏，其中图在2D平面上逐步建立。我们的公式非常灵活，允许用户定义任意目标。我们展示了如何找到折纸图案，这些图案在折叠时可以近似已知的3D形状，以及指定基于功能的目标，例如从给定大小的纸张中折叠最大体积形状（可能的最大桶）。由于这个游戏是NP-Hard，我们在这项任务上测试了各种基于机器学习的优化方法，如强化学习和进化搜索。 考虑到本工作第一部分中突出的GNN限制，在第9章中，我们强调了即使在到目前为止基于图的模型主导的领域中，构建特定领域模型架构的潜在好处。我们介绍了AbDiffuser，一种等变和物理信息化的扩散模型，用于联合生成抗体的3D结构和序列。它基于蛋白质结构的新表征，依赖于一种新的对齐蛋白质普遍有效的架构，并利用强大的扩散先验来改善去噪过程。体外和体内实验表明，我们引入的架构和其他变化，与参考集的各种序列和结构属性相比，可以更紧密地拟合分布。实验室实验表明，我们的方法生成的16种HER2抗体都有高水平的表达，且57.1%的选定设计是紧密结合体。能够在体外生成具有预定义生化特性的新抗体，承诺加速药物设计过程，同时消除了对动物实验的需求。由于抗体是最受欢迎的药物模式之一，2022年FDA新批准的37种药物中有10种是免疫球蛋白，这一研究方向是几何深度学习产生巨大现实世界影响的主要途径之一。