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

论文题目：Learning to Understand Graph Structure: From Classification to Generation

作者：Martinkus, Karolis

类型：2023年博士论文

学校：ETH Zurich（瑞士苏黎世联邦理工学院）

下载链接：

链接: https://pan.baidu.com/s/1Ia6eIww7wsaP0weo7mFleQ?pwd=u5wc

硕博论文汇总：

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

图分类

图是一种特别吸引人的数据结构方式，因为这种表示形式的灵活性。实际上，任何类型的数据都可以以某种形式的图来表示。因此，近年来，图神经网络（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种是免疫球蛋白，这一研究方向是几何深度学习产生巨大现实世界影响的主要途径之一。

以 u 点周围的一个 2 跳邻域为例，图示了 4 种可能的 dropout 组合：一个 0 dropout、两个不同的 1 dropout 和一个 2 dropout。

几个示例图表明，DropGNN 在各种情况下比标准 GNN 更具表达力。不同的节点颜色对应不同的节点特征。

AgentNet 架构。我们有许多神经代理遍历图（a）。每个代理在每一步都会记录节点信息，调查其邻域，并进行概率性迁移到另一个邻居（b）。如果代理走过一个环（c）或一个团（d），它就能注意到。

AgentNet 子线性研究。首先，我们创建一个合成数据集，其中目标子图的密度可变 (a)。该数据集包含梯形图 (b) 和一些单元被十字线替换的梯形图 (c)。任务是区分这两个图。我们始终使用 k = 16 个代理，ℓ = 16 个步骤，并逐渐将梯形图的大小从 16 个节点增加到 1024 个节点。我们要么保持交叉单元密度为 0.5（蓝线），要么梯形图中始终只有两个交叉单元，与其大小无关（红线）。如果目标子图在图中很常见（蓝线），即使 k · ℓ

先生成光谱，SPECTRE 就能在局部连接之前控制全局图结构。SPECTRE 还能校正不完美的生成光谱。上图：调节光谱嵌入。下图：使用最终光谱嵌入绘制的生成图。

总体架构。生成过程按顺序进行，3 个 GAN 分别生成特征值（紫色）、特征向量（蓝色）以及最终的图（绿色）。每个生成步骤都以之前生成的变量为条件。每个子生成器的输入隐变量 w 由 MLP 获取。

特征向量生成器。初始特征向量 U(0) 取自已学习的 Stiefel 流形库。然后，它们经过 3 个旋转层（橙色框）进行变换，每个旋转层执行一次左旋转和一次右旋转。

由模型生成的一组样本图。每行都以相同数量的节点为条件。

我们的方法概述。给定一个目标形状，或者更一般地，给定一个目标函数，例如期望体积 (a)，我们将逆折纸问题公式化为棋盘上的标记放置游戏 (b)。代理可以迭代地与该游戏公式交互，并根据目标改进其策略。最佳展开方式可以转换为折痕图案 (c)，该图案可用于将平板刚性折叠成相应的形状，从而最大化目标 (d)。

一个4阶顶点，有一条入边和三条出边。图中标出了扇形角α、折叠角（二面角）ρ以及单位角U1、U2和U3。右图显示了刚体模态M ∈ {−1, 1} 对相同输入角ρ0的影响。

处于特定状态的折纸游戏（左：棋盘，中：折纸，右：折叠形状）。棋盘上的顶点颜色编码如下：蓝色/橄榄色顶点已延伸，颜色表示刚体模式M；粉色顶点可延伸，黄色顶点当前被选中进行延伸。绿色槽位表示第一个出边端点的允许位置，灰色槽位表示禁止位置——这些位置表示可用的操作。请注意，节点 44 被标记为粉色和绿色，因为它是一个可延伸顶点，可以被选为端点。

建议的内部通用侧链表示。全原子表示（顶部）中的二面体定义原子（橙色）用于构建通用四原子表示（底部）。如果侧链的夹角少于四个，则在通用侧链中放置额外的原子（灰色），以对应 180° 角。通过对合适的侧链模板应用匹配旋转，可以恢复全原子表示。

HER2 结构和生成的结合物的三维结构以不同颜色突出显示。AbDiffuser 已学会重新设计部分结合界面，同时保持亲和力。我们最紧密的结合物的 pKD 达到 9.5，考虑到实验差异，这与曲妥珠单抗（其平均测得的 pKD 为 9.21）相似。

四种目标形状的最佳近似值：（a）金字塔，（b）立方体，（c）碗，（d）面。