beyondWLandoriginalmessagepassingGraphs可以很容易地抽象出关系和交互的复杂系统。社交网络、高能物理和化学等研究领域都涉及相互作用的对象（无论是人、粒子还是原子）。在这些场景中，图结构数据的重要性日益凸显，相关方法取得了一系列的初步成功，一系列的工业应用使得图深度学习成为机器学习方向的研究热点之一。图注：复杂系统的关系和相互作用是通过图形来抽象的。比如“分子图谱”中构成分子的原子之间的化学键，“社交网络”中用户之间的关系和交互，“推荐系统”中用户与产品的联系等。受物理学启发的图形连续学习模型可以克服传统GNN的局限性。多年来，消息传递一直是图深度学习领域的主流范式，使图神经网络(GNN)在从粒子物理学到蛋白质设计的广泛应用中取得了巨大成功。从理论的角度来看，它与Weisfeiler-Lehman(WL)层次结构建立了联系，我们可以从中分析GNN的表达能力。但在MichaelBronstein看来，当前图深度学习方案“以节点和边为中心”的思维方式带来了不可逾越的局限性，阻碍了该领域未来的发展。另一方面，在最新的几何深度学习综述中，Bronstein提出了一种受物理学启发的连续学习模型，开启了微分几何、代数拓扑和微分方程等领域一系列新工具的研究。到目前为止，图机器学习领域的此类研究还很少。针对Bronstein的最新思考，AI科技评论在不改初衷的情况下进行了整理整理：1.图神经网络的工作原理。功能。GNN的消息传递类（即MPNN）通过在相邻节点之间交换信息来传播图上的特征。典型的MPNN架构由多个传播层组成，每个节点的更新基于邻居特征的聚合函数。根据聚合函数的不同，我们可以将MPNN分为：卷积（邻居特征的线性组合，权重只取决于图的结构）、注意力（线性组合，权重取决于图的结构和特征）和消息传递（广义非-线性函数）。消息传递GNN是最常见的，而前者可以看作是消息传递GNN的特例。图注：GNN的三种风格——卷积、注意力和广义非线性信息传递风格，它们都是消息传递的表现形式。传播层由基于下游任务学习的参数组成。典型的用例包括：节点嵌入（每个节点表示为向量空间中的一个点，通过点与点之间的距离恢复原始图的连通性。这类任务称为“链接预测”），节点-级分类或回归（例如，推断社交网络用户的属性），或通过进一步聚合节点特征进行图级预测（例如，预测分子图的化学性质）。2.GNNs在MessagePassing方面的弱点GNNs在很多方面都取得了令人瞩目的成功，近期的相关研究具有相当的广度和深度。然而，当前图深度学习范式的主流模型是：对于构造好的图，节点信息通过消息传递沿图的边传播。MichaelBronstein认为，正是这种以节点和边缘为中心的思维方式对该领域的进一步发展构成了重大障碍。WL的类比有限。Appropriatechoiceoflocalaggregationfunctionslike"sum"canmakemessagepassingequivalenttoWLgraphisomorphismtests,enablinggraphneuralnetworkstodiscovercertaingraphstructuresbasedonhowinformationpropagatesacrossthegraph.通过与图论的这种重要联系，研究人员提出了各种理论结果来分析GNN的表达能力，确定图上的某些函数是否可以通过消息传递来计算。然而，此类分析的结果通常无法说明表示的效率（即计算某个函数需要多少层），也无法说明GNN的泛化能力。图注：WL测试就像是没有地图就走进了迷宫，试图理解迷宫的结构。位置编码提供了迷宫的地图，而重新布线则提供了爬过“墙”的梯子。即使对于三角形等简单的图结构，WL算法有时也无法检测到它们，这让试图将信息传递神经网络应用于分子图的从业者大失所望。例如，在有机化学中，像环这样的结构非常普遍，对分子的性质也很重要（例如，萘等芳香环主要存在于具有强烈气味的化合物中，因此被称为芳香环）。图片说明：萘烷（左）和双环戊基（右）具有不同的结构，但我们无法通过WL测试区分它们。近年来，研究人员提出了一些构建具有更强表达力的GNN模型的方法。例如，WL层次结构中的高维同构测试（以更高的计算和内存复杂度以及缺乏局部性为代价），将WL测试应用于子图的集合；locationorstructureencoding，为图中的节点着色，这样有助于打破混淆WL算法的规律。位置编码是目前Transformer模型中最常用的技术，在GNN中也被广泛使用。虽然存在多种位置编码方法，但具体选择取决于目标应用，需要用户有一定经验。图例：位置编码示例：随机特征、拉普拉斯特征向量（类似于Transformer中的正弦曲线）、结构特征（三角形和矩形的数量）。“图重联”突破了GNN的理论基础。GNN和卷积神经网络(CNN)之间一个重要但微妙的区别：图形是输入的一部分，也是计算结构的一部分。传统的GNN使用输入的图结构来传播信息，并通过这种方式获得同时反映图结构和图上特征的表示。然而，由于某些结构特征（“瓶颈”），一些图在信息传播方面表现不佳，导致来自太多节点的信息被压缩到一个节点中，即“过度压缩”。现代GNN实现通过将输入图与计算图解耦（或为计算目的优化输入图）来处理这种现象，这种技术称为“图重新布线”。重新布线可以采用以下形式：邻域采样、虚拟节点、连通性扩散或进化，或节点和边缘的丢失机制。Transformer和GAT等基于注意力的GNN通过为每条边分配不同的权重来有效地学习新图，这也可以理解为“软”重新连接。最后，潜在图学习方法也属于这一类，它构建一个任务特定的图并在每一层更新它（带有位置编码的初始状态、初始图，或者有时根本没有图）。很少有现代GNN模型通过原始输入图传播信息。图例：GNN中使用的各种图重新连接技术——原始图、邻域采样（例如GraphSAGE）、注意机制（例如GAT）、连通性演化（例如DIGL）。WL测试根据信息如何在图中传播来描述图。Rewiring打破了这种理论联系，却让我们陷入了机器学习中的一个普遍问题：学术界理论分析的模型与实践中使用的模型并不相同。有时图形的“几何特性”是不够的。GNN是几何深度学习宏伟计划中的一个实例。几何深度学习是一个“群论框架”，它允许我们根据数据底层域的对称性来设计深度学习架构。由于图没有规范的节点顺序，因此在图的上下文中，这种对称性指的是节点的排列。由于这种结构特性，局部动作图上的MPNN必须依赖于满足排列不变性的特征聚合函数，这意味着图上没有“方向”的概念，信息的传播是各向同性的。这种情况与在连续域、网格上学习有很大不同，并且是GNN的缺点之一，其中各向同性滤波器被认为用途有限。图例：网格是具有局部欧氏结构的离散流形。我们根据旋转来定义邻居，从而产生“方向”的概念。该图的结构较少，它根据排列定义相邻节点。有时，图形的“几何属性”太多了。距离与方向的差异也部分与构建节点嵌入时遇到的问题有关。某些空间中节点表示之间的距离用于捕获图的连通性。我们可以通过图中的边粗略地连接嵌入空间中的紧密节点。在推荐系统中，图形嵌入用于在节点表示的实体之间创建关联（边）。图嵌入的质量及其表达图结构的能力在很大程度上取决于嵌入空间的几何特性及其与图的几何特性的兼容性。欧氏空间在表示学习中起着重要作用，是目前最简单、最方便的表示空间。然而，对于自然界中的许多图，欧氏空间并不理想。原因之一是：欧几里德度球体的体积随半径呈多项式增长，随维数呈指数增长，而许多现实世界的图形在体积上呈指数增长。结果，嵌入变得“太拥挤”，我们被迫使用高维空间，导致高计算和空间复杂度。最近流行的一种替代方法是使用负曲率（双曲）空间，它具有与图形更兼容的指数体积增长。双曲线几何的使用通常会导致较低的嵌入维数和更紧凑的节点表示。然而，图往往是异构的（例如，一些部分看起来像树，另一些看起来像团，具有非常不同的体积增长特性），而双曲线嵌入空间是均匀的（每个点都具有相同的几何特性）。此外，即使嵌入空间具有非欧几里德几何特性，也往往无法准确表示该空间中的一般图度量结构。因此，图嵌入不可避免地是近似的。然而，更糟糕的是，由于嵌入是在考虑链接预测标准的情况下构建的，因此高阶结构（三角形、矩形等）的失真可能会变得无法控制地大。在社交和生物网络等应用场景中，此类结构发挥着重要作用，因为它们可以捕获更复杂的未配对交互和主题。图例：图的主题是高阶结构。这种结构可以在模拟许多生物现象的图表中观察到。当数据结构与底层图的结构不兼容时，GNN的性能就会受到挑战。许多图学习数据集和基准测试默认假设数据是同质的（即相邻节点的特征或标签相似或平滑）。在这种情况下，即使是简单的图形低通滤波（例如，采用邻接平均）也能很好地工作。早期的比较基准（例如Cora）是在同质性高的图上进行的，这使得GNN的评估过于容易。图例：同构和异构数据集。在同构图中，节点特征或标签的结构与图兼容（即，节点与其邻居相似）。然而，许多模型在处理异嗜性数据时显示出令人失望的结果，在这种情况下必须使用更精细的聚合。我们不妨考虑两种典型情况：（1）模型完全避免使用邻居信息（GNN退化为节点级多层感知器）（2）出现“过度平滑”现象，即节点的表示经过GNN的每一层，然后变得更平滑，最终“坍缩”成一个点。“过度平滑”也存在于类似的数据集中，这是一些MPNN更根本的缺陷，使得深度图学习模型难以实现。我们往往很难理解GNN学到了什么，GNN往往是一个难以解释的黑盒模型。虽然可解释性的定义在很大程度上仍然很模糊，但在大多数情况下，我们真的并不真正理解GNN学到了什么。最近的一些工作试图通过以紧凑??的子图结构和在GNN预测中起关键作用的节点特征子集的形式解释基于GNN的模型来减轻可解释性缺陷。通过潜在图学习架构学习的图也可以被视为提供一种“解释”形式。约束通用消息传递函数有助于排除不合理的输出，确保GNN学习的内容有意义，并能够更好地理解特定领域应用程序中的GNN。具体来说，这样做为消息传递提供了额外的“内部”数据对称性，从而可以更好地理解潜在问题。例如，E(3)-等变消息传递正确处理分子图中的原子坐标，并且最近为AlphaFold和RosettaFold等蛋白质结构预测架构的成功做出了贡献。在Miles和KyleCranmer合着的论文“Discoveringsymbolicmodelsfromdeeplearningwithinductivebiases”中，作者用符号公式替换了多体动力系统上学习的消息传递函数，这允许“学习物理方程”。其他研究人员试图将GNN与因果推理联系起来，试图构建一个图来解释不同变量之间的因果关系。总的来说，这仍然是一个处于起步阶段的研究方向。图例：不同的“可解释”GNN模型-图解释器、潜在图学习、等变消息传递。大多数GNN实现都是独立于硬件的。大多数GNN目前依赖GPU实现，默认情况下数据可以放入内存。然而，在处理生物和社交网络等大规模图时，这往往是一厢情愿的想法。在这种情况下，了解底层硬件的局限性（例如不同带宽和内存层次结构的延迟）并方便地使用硬件至关重要。粗略地说，同一物理内存中的两个节点与不同芯片上的两个节点之间的消息传递成本可能存在一个数量级的差异。“让GNNs对现有硬件友好”是一个重要且经常被忽视的问题。考虑到设计新芯片所需的时间和精力，以及机器学习的发展速度，开发新型以图形为中心的硬件是一个更大的挑战。3图学习的新蓝图——“连续”模型“连续”学习模型是一种新兴且有前途的离散GNN替代方案。“受物理系统启发的持续学习”开辟了一组新的工具，来自微分几何、代数拓扑和微分方程等领域，这些领域迄今为止在图机器学习中尚未探索。将GNN重新想象为连续的物理过程。与在图上传递多层消息不同，我们可以考虑在一个连续的时间维度上发生在域（可以是流形等连续域，将其转化为离散图）上的物理过程。过程在空间和时间上某一点的状态取代了一层GNN生成的图中节点的潜在特征。该过程由一组参数（代表底层物理系统的属性）控制，这些参数取代了消息传递层的可学习权重。我们可以从经典系统和量子系统中构造出大量不同的物理过程。在一系列论文中，研究人员证明许多现有的GNN可能与扩散过程有关，这可能是传播信息最自然的方式。可能还有一些更奇特的方法（例如耦合振荡系统），它们可能具有某些优势。图例：耦合振荡系统的动力学图。连续系统在时间和空间上可以是离散的。空间离散化是指将连续域上的邻近点以图形的形式连接起来，可以随时间和空间变化。这种学习范式不同于传统的WL测试，后者受到基本输入图假设的严格约束。更重要的是，空间离散化的思想激发了一系列新工具的诞生。至少在原则上，它使我们能够解决现有图论技术无法解决的重要问题。图例：二维拉普拉斯算子的不同离散化结果。学习是一个最优控制问题。在给定的时间，一个过程的所有可能状态的空间可以被视为可表示函数的“假设类”。这种学习可以看作是一个最优控制问题，即是否可以控制过程（通过在参数空间中选择一条轨迹）使其达到某种理想状态。我们可以将表征能力定义为：是否可以通过在参数空间中选择合适的轨迹来控制过程，从而实现给定的功能（可达性）；效率与达到某种状态所需的时间有关；而泛化与过程的稳定性有关。图例：学习作为一个控制问题。使用飞机与物理系统的类比，其xyz坐标（系统状态）由操纵推理、副翼和方向舵（参数空间）控制。GNN可以从离散微分方程导出。物理系统的行为通常可以由微分方程控制，微分方程的解产生系统的状态。在某些情况下，这样的解决方案可能是封闭形式的解决方案。但在更一般的情况下，必须依赖基于适当离散化的数值解。经过一个多世纪的研究，数值分析领域出现了各种迭代求解器，为图深度学习提供了可能的新架构。GNN中的注意力机制可以解释为具有可学习扩散系数的离散扩散偏微分方程，使用显式数值方法求解。此时，求解器的每一步迭代都对应了GNN的一层。目前还没有直接类似于更复杂求解器的GNN架构（例如，使用自适应步长或多步方案），朝这个方向的研究可能会产生新的架构。另一方面，隐式方案需要在每次迭代时求解线性系统，这可以解释为“多跳”滤波器。此外，数值方法具有稳定性和收敛性保证，这些保证提供了它们可以工作的条件和对失败情况的解释。数值求解器应该是硬件友好的。迭代求解器比数字计算机更古老，从数字计算机诞生之日起，它就必须知道它拥有底层硬件并有效地使用它。科学计算中的大规模问题通常必须在计算机集群上解决，而且它们至关重要。我们在图上进行“连续”深度学习的方式使我们能够以与模拟它们的硬件兼容的方式离散化底层微分方程。超级计算研究社区的大量工作（例如域分解技术）可用于此处。具体来说，图重新连接和自适应迭代求解器考虑了内存的层次结构，例如，在不同物理位置的节点上执行不频繁的消息传递步骤，而在同一物理内存中的节点上执行更频繁的步骤。步。将演化方程解释为与物理系统相关的能量函数的梯度流有助于理解学习模型。许多物理系统都有相关的能量泛函（有时还包含某些对称性或守恒定律），其中控制系统动力学的微分方程是最小梯度流。例如，扩散方程最小化了Dirichlet能量，而其非欧几里得版本（Beltrami流）最小化了Polyakov函数，给出了对学习模型的直观理解。使用最小作用原理，某些能量泛函可以导出双曲线方程（例如波动方程）。这些方程的解是波动的（振荡的），与典型的GNN动力学非常不同。分析此类流的极限情况可以深入了解难以通过其他方式获得的模型行为。例如，在论文“NeuralSheafDiffusion:ATopologicalPerspectiveonHeterophilyandOversmoothinginGNNs”中，Michael等人。证明了传统的GNNs必然会导致oversmoothing，只有在同质性假设下才有分离的能力；在图上使用额外的结构可以获得更好的分离能力。在论文“Graph-CoupledOscillatorNetworks”中，Michael等人。表明振荡系统可以避免极限过度平滑。这些结果可以解释为什么某些GNN架构中会出现某些不良行为，以及如何设计架构来避免这些行为。此外，将流动的极限情况与分离联系起来揭示了模型表达能力的界限。图中可以使用更丰富的结构。如前所述，有时图的几何属性可能“不足”（未能捕捉到更复杂的现象，例如非成对关系）或“过多”（即难以在齐次空间中表示）。我们可以通过使用附加结构使图形更丰富来处理图形几何图形不足的问题。例如，分子包含环，化学家将其视为单个实体，而不是原子和键（节点和边）的集合。迈克尔等人。表明图形可以“提升”到“简单和元胞复合体”的高维拓扑。我们可以设计一个更复杂的消息传递机制，让信息不仅可以像GNN那样在节点之间传递，也可以像环一样在结构之间传递。正确构建此类“提升”操作可使这些模型比传统的WL测试更具表现力。图例：“促进”图形进入细胞复合体，细胞信息传输。在论文“NeuralSheafDiffusion:ATopologicalPerspectiveonHeterophilyandOversmoothinginGNNs”中，Michael等人。表明通过将向量空间和线性映射分配给节点和边，可以为图形配备额外的几何结构，即“单元束”。传统的GNN隐含地假设图具有简单的底层束结构，这反映在相关扩散方程的属性和图拉普拉斯算子的结构中。与传统的GNN相比，使用复杂的“束”可以产生更丰富的扩散过程，有利于其渐近行为。例如，即使在异嗜环境中，正确选择的梁结构上的扩散方程也可以在多个极限类别中分离。从几何的角度来看，束结构类似于连接，连接是微分几何中的一个概念，描述流形上矢量的平行传输。从这个意义上说，我们可以将波束学习视为一种依赖于下游任务进化图几何形状的方法。迈克尔等人。证明了通过限制束的结构群（例如，到特殊的正交群），可以使节点特征向量仅旋转，从而导致一些有趣的发现。图例：建立在图上的元胞束由附加到每个节点的向量空间和连接它们的线性约束映射组成。这可以认为是赋予图几何属性，约束图类似于连接。“离散曲率类比”是图几何的另一个例子，是微分几何领域描述流形局部性质的标准方法。在论文“Understandingover-squashingandbottlenecksongraphsviacurvature”中，Michael等人。证明负图Ricci曲率对图上的信息流造成了瓶颈，导致GNN中的过度压缩。离散里奇曲率可应用于高阶结构（三角形和矩形），这在许多应用中都很重要。这种结构对于传统的图形嵌入来说有点“矫枉过正”，因为图形是异构的（非常弯曲）。对于通常用于嵌入的空间，即使是非欧几里得空间也是同构的（恒定曲率）。在论文“Heterogeneousmanifoldsforcurvature-awaregraphembedding”中，Michael等人。展示了一个Ricci曲率可控的异构嵌入空间的构造，可以选择它来匹配图的曲率，不仅可以更好地表示邻域（距离）结构，而且可以更好地表示三角形、矩形等高阶结构。这些空间被构造为同构、旋转对称流形的乘积，可以使用标准黎曼梯度下降法对其进行有效优化。图例：（左）空间形式（球体、平面和双曲面）具有恒定的正、零和负Ricci曲率，以及它们与下面相应的离散Forman曲率图（簇、网格和树）的类比。（中等）乘积流形（圆柱体可以被认为是圆和线的乘积）。（右）具有不同曲率的异构流形及其图形的类比。位置代码可以看作是域的一部分。将图看作是连续流形的离散化，节点位置坐标和特征坐标可以看作是同一空间的不同维度。在这种情况下，该图可用于表示由此类嵌入引起的黎曼度量的离散类比，与嵌入相关的谐波能量是Dirichlet能量的非欧几里德扩展，在弦理论中称为Polyakovpan信。这种梯度能量流是一种扩散型方程，可以演化出位置和特征坐标。在节点位置构建图形是一种特定于任务的图形重新布线形式，它也会在迭代扩散层中发生变化。图例：Cora图的位置和特征分量通过重新连接的Beltrami流演化的结果。域演化是图重新连接的替代方法。扩散方程也可以作为预处理步骤应用于图形连通性，旨在改善信息流并避免过度压缩。Klicpera等人。提出了一种基于个性化PageRank的算法，即图扩散嵌入。在论文“Understandingover-squashingandbottlenecksongraphsviacurvature”中，我们分析了这个过程，指出了它在异构设置中的缺点，并提出了一种替代图重新布线的方法，用于受Ricci流计划启发的过程。这种重新布线减少了由负曲率引起的图形瓶颈的影响。里奇流是流形的几何演化方程，与黎曼度量的扩散方程非常相似，是微分几何中流行且强大的技术（包括著名的庞加莱猜想的证明）。更广泛地说，我们不是将图重新连接视为预处理步骤，而是考虑进化过程的耦合系统：一个进化特征，另一个进化域。图例：（上图）具有负曲率瓶颈的哑铃形黎曼流形，经过基于曲率的度量演化后，变得更圆，瓶颈不那么明显。（底部）类似的基于曲率的图形重新连接过程减少了瓶颈并使图形对消息传递更加友好。4结论新的理论框架能带我们走多远，它们是否能解决该领域目前未解决的问题，仍然是一个悬而未决的问题。这些方法真的会在实践中使用吗？从业者的一个关键问题是，这些方法是否会带来新的更好的架构，或者仍然是脱离实际应用的理论工具。MichaelBronstein认为，这方面的研究将具有实用性，通过拓扑和几何工具获得的理论结果将使我们能够对现有的GNN架构做出更好的选择。例如，如何限制消息功能，以及何时使用这些特定的选择。我们是否超越了消息传递？从广义上讲，数字计算机上的任何计算都是一种消息传递形式。然而，在GNN的严格意义上，消息传递是一种通过将信息从一个节点发送到另一个节点来实现的计算概念，这是一个本质上离散的过程。另一方面，所描述的物理模型以连续的方式在节点之间共享信息（例如，在图耦合振荡系统中，节点的动态取决于其邻居在每个时间点的动态）。在对描述系统的微分方程进行离散化和数值求解时，相应的迭代确实是通过消息传递来实现的。然而，可以假设使用这些物理系统或其他计算范例（例如，模拟电子学或光子学）的实际实现。在数学上，基础微分方程的解有时可能以封闭形式给出：例如，各向同性扩散方程的解是高斯核卷积。在这种情况下，邻居的影响被吸收到核心结构中，不会发生实际的消息传递。图注：基于反向传播的深度学习在真实物理系统中的应用。
