本文的作者是 Twitter 首席科学家、DeepMind 人工智能教授 Michael Bronstein。以下是博客原文。
对称，无论从广义还是狭义的角度讲，都是人类一直以来试图理解和创造秩序与美的一种观念。
——Hermann Weyl
Hermann Weyl 这类诗意的描述强调了对称性在科学中的基石作用。Felix Klein 在 1872 年的「Erlangen Programme」中用对称群表征多少。这不仅是数学上的一个突破，即统一了「多少大家庭」，还推进了现代物理理论的发展，这些理论可以完全从对称性的第一原理推导出来。多少深度进修畛域也出现了类似的原则，通过群不变性和等变性能够推导出大多数流行神经网络架构的通用蓝图。
图神经网络可以被认为是多少深度进修蓝图的一个特例，其构建模块是具有对称群的域（在这类情况下是具有置换群的图）、域上的信号（节点特点）和此类信号的群等变函数（消息传递）。
多少深度进修蓝图可以应用于不同的畛域，例如 grid、mesh 或图 (graph)。然而，前两者具有明确的连续方式的类比对象，grid 可以被认为是欧几里得空间或更一般的均匀空间（如球体）的失散化，mesh 则是二维流形的常见失散化），图却没有直接的连续方式的类比。这类不可类比有点令人不安，因此我们决定仔细研究用于图进修的连续模型。
图神经网络聚集。图神经网络 (GNN) 通过在图上执行某种方式的消息传递来进修。其中，特点通过边从一个节点传递到另一个节点。这类机制与图上的聚集过程有关，可以用称为「聚集方程」的偏微分方程 (PDE) 方式表示。我们最近在一篇论文中展示了这类具有非线性可进修聚集函数的 PDE 的失散化（称为 GRAND），泛化了一大类 GNN 架构，例如图注意力网络（GAT。
PDE 的思维方式提供了多种优势，例如可以利用兼具稳定性和收敛性的高效数值求解器（例如隐式、多步、自适应和 multigrid 方案）。其中一些求解器在流行的 GNN 架构中没有直接的类比，可能会促成一些新型图神经网络设计。由于我们考虑的聚集 PDE 可以看作是一些相关能量的梯度流 ，因此这类架构可能比典型架构更易于解释。
同时，虽然 GRAND 模型提供连续时间来代替传统 GNN 中的层，但方程的空间部分仍然是失散的，并且依赖于输出图。重要的是，在这个聚集模型中，域（图）是固定的，其上定义的某些属性会蜕变。
微分多少中常用的一个不同概念是多少流（geometric flow），域本身的属性不断蜕变。我的博士生导师 Ron Kimmel 等研究者 20 世纪 90 年代在图像处理畛域就采用了这个想法。他们将图像建模为嵌入在联合地位和颜色空间中的流形，并通过 PDE 对它们进行推导蜕变，以最小化嵌入的谐波能量。这样的偏微分方程称为贝尔特拉米流（Beltrami flow），具有各向同性非欧几里得聚集的方式，并产生保边图像去噪。
我们将这类范式应用于「Beltrami 神经聚集（BLEND）」框架中的图。图的节点现在由地位坐标和特点坐标来表征，这两个坐标都是经过蜕变的，并且都决定了聚集性。在这类思维模式下，图本身就变成了一个辅助角色：它可以从地位坐标生成（例如作为 k – 最近邻图）并在整个蜕变过程中从头连接。下图说明了这类同时蜕变的过程。
图的表达能力
在最近的工作中，人们对图神经网络（GNN）的表达能力给予了极大的关注。消息传递的 GNN 等价于 Weisfeiler-Lehman 图同构尝试（一种通过迭代颜色细化来确定两个图是否在结构上等价 (同构) 的经典办法）。这个检验是一个必要但不充分条件：事实上，一些非同构图可能会通过 Weisfeler-Lehman 尝试。下图说明了 GNN 传递消息过程中该尝试「看到」了什么：两个高亮显示的节点看起来没有什么区别，然而这两个图显然具有不同的结构：
地位编码。解决这个课题的一个常见办法是通过为节点分配一些额外的特点来给节点「着色」，这些特点保证了图中节点的角色或「地位」。由于地位编码在 Transformer 中已得到普及，因此地位编码成为增加图神经网络表达能力的常用办法。
地位编码为图的节点分配了额外的特点，允许消息传递获得比 Weisfeiler-Lehman 尝试更高的表达能力。然而，对于地位编码，并没有一个「规范」的选择。
也许最直接的办法是赋予每个节点一个随机特点；然而，这类办法虽然可以更具表达性，但泛化能力较差（因为不可能在两个图中重现随机特点）。图拉普拉斯算子的特点向量提供了图的畛域保持嵌入，并已成功用作地位编码。最后，我们（与 Giorgos Bouritsas 和 Fabrizio Frasca 合著）在一篇论文中表明，图的子结构计数可以用作地位或「结构」编码的一种方式，这说明它比基本的 Weisfeiler-Lehman 尝试更强大。
然而，地位编码有多种选择，如何选择以及哪种办法在哪种情况下效果更好，都没有明确的答案。我相信像 BLEND 这样的多少流可以根据这个课题来解释：通过非欧几里得聚集来蜕变图的地位坐标，地位编码可以适用于下游任务。因此，答案是「视情况而定」：最佳地位编码是手头数据和任务的函数。
高阶消息传递。表达性的另一种选择是放弃根据节点和边来考虑图，而是把图看作单位复合体（cell complex）对象的示例，单位复合体是代数拓扑畛域的主要研究对象之一。在这类办法中，节点是 0-cell，边是 1-cell。不必止步于此：我们可以构造如下图所示的 2-cells（面），这使得上述示例中的两个图可以完美区分：
在我最近与 Cristian Bodnar 和 Fabrizio Frasca 合作的两篇论文中，我们表明可以构建一个「提升变换」，用高阶单位来增强图，从而在这些单位上可以执行更复杂的分层消息传递方式。该方案可被证明比 Weisfeiler-Lehman 尝试的表达能力更强，并且在计算化学畛域给出了有望的结果：比建模为图，建模为单位复合体表现更好。
「over-squashing」现象
GNN 的另一个常见课题是「over-squashing」现象，或者由于输出图的某些结构特点，消息传递无法有效地传播信息。oversquashing 通常发生在体积呈指数增长的图中，例如小世界网络以及依赖于远程信息的课题。换句话说，GNN 作用的输出图并不总是对消息传递友好。
「小世界」图中快速增长的邻居数量通常是 GNN 中观察到的过度挤压现象的根源。
从实验可以观察到，将输出图与计算图解耦并允许在不同的图上传递消息有助于缓解这一课题。这类技术通常被称为「图从头布线（graph rewiring）」。
事实上，许多流行的 GNN 架构都实现了某种方式的图重构，可以采用邻域采样（最初在 GraphSAGE 中提出以应对可扩展性）或多跳滤波器的方式。上面讨论的拓扑消息传递也可以看作是从头布线的一种方式，远距离节点之间的信息流可以认为是通过高阶单位的「捷径」。Alon 和 Yahav [23] 表明，即使像使用全连接图这样简单的办法也可能有助于改善图 ML 课题中的 over-squashing。
Klicpera 等研究者宣称「聚集改进了图进修」，提出了一个通用的 GNN 预处理步骤（DIGL），包括通过聚集过程来去噪图的连通性。总体而言，尽管进行了重要的实验研究，但 over-squashing 现象一直令人难以捉摸。我们最近在一篇论文中表明：导致 over-squashing 的瓶颈可归因于图的局部多少特性。具体来说，通过定义 Ricci 曲率的图类比，我们可以证明罪魁祸首是 negatively-curved 边。因此出现了一种类似于「反向 Ricci 流」的图从头布线过程，该过程去除有课题的边并生成一个更易于消息传递的图，同时在结构上与输出图相似。
使用基于聚集的办法（DIGL，中）和基于曲率的办法（Ricci，右）从头连接康奈尔图（左）的示例。基于曲率的办法显著减少了瓶颈，同时更接近于原始图结构。
总结
这些例子表明，微分多少和代数拓扑为图机器进修中重要且具有挑战性的课题带来了新的视角。在本系列的后续文章中，我将更详细地展示如何使用这些畛域的工具来解决上述图神经网络课题。第二部分将讨论代数拓扑如何提高 GNN 的表达能力。第三部分将讲解多少聚集偏微分方程。第四部分将展示 over-squashing 现象与图曲率有何相关，并提供一种受 Ricci 流启发的图从头布线的新型多少办法。