0
作者 | Michael Bronstein等人
编译 | 黄楠 、bingo
本文由Cristian Bodnar 和Fabrizio Frasca 合著，以 C. Bodnar 、F. Frasca 等人发表于2021 ICML《Weisfeiler and Lehman Go Topological: 信息传递简单网络》和2021 NeurIPS 《Weisfeiler and Lehman Go Cellular: CW 网络》论文为参考。
本文仅是通过微分几何学和代数拓扑学的视角讨论图神经网络系列的部分内容。
从计算机网络到大型强子对撞机中的粒子相互作用，图可以用来模拟任何东西。图之所以无处不在，是因为它们具有离散性和组合性，这使得它们能够表达抽象关系，同时又易于计算。它们受欢迎的原因之一是图抽象出几何图形，即节点在空间中的位置或边缘是如何弯曲的，只留下节点如何连接的表示。
图论起源于莱昂哈德 · 欧拉（Leonhard Euler）在1741年的著作《geometria situs》中的观察，他指出著名的柯尼斯堡七桥问题问题没有解决方案。
图注：七桥问题要求在哥尼斯堡市内找到一条循环行走的路线，不需要多次过桥。正如欧拉所说，哥尼斯堡市的确切形状并不重要，重要的是不同的土地（图的节点）是如何相互连接的（边）。欧拉表明，当且仅当所有节点具有偶数度时，这样的循环才存在。另外，最初的桥梁中只有五座存活到现代。图源：维基百科
有趣的是，欧拉的发现不仅标志着图论的开始，而且也常常被认为是拓扑学诞生的标志。与图一样，拓扑学家对空间的那些与其特定形状或几何形状无关的属性感兴趣。
这些思想的现代表现形式出现在1895年的“分析地点” （Analysis situs），这是 Henri Poincaré 的一篇开创性的论文，他的工作点燃了对流形的组合描述的兴趣，从这些流形中可以更容易地找到和计算拓扑不变量。
图注：Leonhard Euler（1707-1783）和 Henri Poincaré（1854-1912）
这些组合描述今天被称为细胞复合体 ，可以被认为是图的高维概括。
与由节点和边形成的图不同，细胞复合体也可以包含更高维的结构或“细胞”：顶点是0-细胞，边是1-细胞，2D 表面是2-细胞等。为了构建一个细胞复合体，我们可以通过将一个细胞的边界粘合到其他低维细胞上来进行分层。
在特殊情况下，当单元格由单形（如边、三角形、四面体等）构成时，这些空间也称为单形复合体。
图注：图可以看作是我们附加边（1-单元格）的一组顶点。类似地，单细胞复合体和细胞复合体可以看作是我们连接2-细胞（蓝色显示）、3-细胞（绿色显示）等的图形。
我们认为，人们不必等待 400 年才将把拓扑学变成一种实用的工具。
在拓扑数据分析（TDA）的保护伞下，诸如浅层复合物这样的拓扑结构已经被用于机器学习和数据科学，这类方法出现在20世纪90年代，试图以一种对度量不敏感和对噪声稳健的方式来分析“数据的形状”。
TDA的根源可以追溯到20世纪20年代末最多产的拓扑学家之一 Leopold Vietnam oris 的工作。然而，这些技术必须等到现代计算的诞生才能大规模应用。
图注：给定一个点云，每个点周围固定半径的封闭球之间的交叉点产生一个简单的复合体。通过逐步增加球的半径，我们可以得到一个嵌套的简单复合体序列。图源：Bastian Rieck。
TDA 的主力是持久性同源性（PH），一种从点云中提取拓扑特征的方法。给定一个点的数据集，PH 创建一个简单复数的嵌套序列，其中每个复数对应于分析基础点云的某个比例。然后，它跟踪各种拓扑特征（例如，连接的组件、循环或空洞） ，这些特征随着比例的逐渐增加而出现和消失，并且人们从序列中的一个复合物过渡到下一个复合物。
在深度学习时代，持久性同源性有了“第二次生命”，因为它表明人们可以通过它进行反向传播，从而允许将已经建立的 TDA 设备集成到深度学习框架中。
最近的一系列工作提出了在几何深度学习中简化和细胞复合体的不同用途，作为一个更丰富的底层拓扑空间来支持数据和对其进行的计算。
最早利用这一观点的几项工作提出了卷积模型以及在简化复合体上操作的随机行走方法。如在本文中，卷积模型可以被理解为简单和细胞复合体上信息传递的具体实例。
由于计算是由这些空间的拓扑结构（即邻域结构）驱动的，我们把这套方法称为拓扑信息传递。在这个框架中，相邻的单元，可能是不同维度的，正在交换信息，如下图所示。
图注：拓扑信息传递示意图。蓝色箭头描述了上层相邻细胞之间的“水平”信息传播，即同一高维细胞的边界上的细胞。红色箭头描述了“垂直”信息传播，即细胞从其边界的低维细胞中接收信息。将来自边界细胞的信息汇总到一个更粗的表示中，这种计算可以被解释为一种（可微分的）集合形式。
尽管细胞复合体提供了丰富的结构，但我们不能忽视图是迄今为止机器学习中最常见的拓扑对象，而且很少有数据集能超越它们。尽管如此，人们仍然可以通过转换输入图来利用这些有趣的拓扑空间。
我们把将图转换为高维拓扑空间称为“提升”，以类似于范畴理论中的同名概念。它是一种转换，通过遵循某些规则将高维单元附加到输入图上。例如，一个图可以通过在图的每个悬崖或周期上附加一个高维单元而被提升为一个单元复合体。通过这样做，图被替换成一个不同的空间，它有更多的结构，可以为GNN提供一个比原始图更好的计算结构。在下文中，我们将讨论这种方法的具体优势。
图注：通过将二维封闭圆盘的边界粘合到图中的诱导循环上，可以从图中构造出高维的细胞复合体。
GNN通常采用以节点为中心的观点，驻留在边上的数据仅被视为增加顶点间通信的辅助信息。在拓扑信息传递中，所有单元都是一等公民。无论它们的维度如何，它们都被分配了一个特定的表示，这个表示是通过与相邻的单元交换信息而发展起来的。这为明确地模拟某些高阶结构和它们之间的相互作用提供了一个秘诀。特别是，它提供了一种原则性的方法来演化输入图的边缘（即1个单元）特征，这是一大类 GNN 模型没有考虑到的问题。
图表根据定义是二元的（“成对的”），不能表示涉及两个以上对象的关系和交互。在对以高阶相互作用为特征的复杂系统进行建模时，这可能是一个问题：例如，化学反应中的三种反应物可能同时发生相互作用。在细胞复合体中，这种情况可以通过两个细胞（即“填充”三角形）连接反应物来编码。因此，模型的计算流程适应高阶交互的存在。
图注：细胞 Weisfeiler-Lehman（CWL）测试，将经典的WL测试扩展到细胞群，算法的每一步都完美地散列了相邻单元的颜色（可能有不同的维度）。
信息传递 GNN 的表达能力受 Weisfeiler-Leman (WL) 图同构测试限制，众所周知，WL 无法检测某些图子结构，例如三角形或循环，即使是非常简单的非同构图也无法区分。
据此前的论文显示（论文地址：https://arxiv.org/abs/2103.03212；https://arxiv.org/abs/2106.12575），WL 测试 (CWL) 的细胞版本可用于测试细胞复合物的同构性。当这个新测试与上面描述的图提升过程相配时，可以发现，它能比 WL 测试区分更大的图类。因此，在一定条件下，拓扑信息传递过程继承了该测试的优点，相比标准 GNN 提高了表达能力。
信息传递的 GNN 需要n个层来使相距n个跳数的节点进行通信。当仅使用几层，以至于相距较远的节点无法交换信息时，这种现象称为未达到。
相比之下，使用太多层可能会导致过度平滑，且信息可能会在图的结构瓶颈中丢失。
单元复合体可以缓解这些问题，因为由高维单元诱导的更丰富的邻域结构，在可能相距很远的节点之间创建了捷径。因此，信息只需包含一些计算步骤来传播，就是有效的。
图注：GNN 需要很多层才能使相距很远的节点进行通信（左）。高维单元通过创建捷径来改变空间的底层拓扑结构（右）。这允许远程节点在几个信息传递步骤中交换信息。
拓扑信息传递执行的计算是分层的，信息从低维单元流向高维单元并返回，可看作是“垂直”（和可区分）池的一种形式，而非标准图神经网络中的“水平”池。这保持了“压缩”图区域的归纳偏差，而不会忽略输入图的会损害基于 GNN 池性能的细粒度信息。
图注：拓扑信息传递允许信息存在于不同维度的单元之间分层
某些应用自然与细胞复合物的结构一致，例如，分子的原子、键和化学环可以表示为 0-cell、1-cell 和 2-cell，分子的物理结构和细胞的复杂表示之间的直接对应，允许了拓扑信息传递利用上述特性，这些表示也展示了拓扑信息传递在分子特性预测任务中所实现的最先进结果 。
其他表现良好对齐的应用程序，可能包括计算机图形应用程序中的离散流形（网格）、社交网络（派系特别重要）或空间图，例如谷歌地图（街道间的街区可被自然地表示为“立方”细胞） 。
图注：咖啡因子被建模为二维细胞复合物
拓扑信息传递中，保留了许多与代数拓扑学、微分几何学的有趣联系，允许使用迄今为止仍在图和几何深度学习中没有得到充分开发的数学工具。
在代数拓扑中，通常使用有向单纯复形，其中每个单纯形存在任意“定向”，例如，我们选择每条边中的一个源节点和一个目标节点，并对每个三角形选一个遍历其节点的顺序。一旦选定方向后，就可对复形执行有趣的代数算子，例如通过“边界算子”计算某些单纯形的边界。这些代数运算也可以用来在单纯复形中找到“洞”——没有边界但不在其他事物边界上的区域。其背后，持久同源依靠这些计算来检测拓扑特征。
图注：应用于 2-单纯形的边界算子产生一个三角形。再次将算子应用于三角形，结果为零，由于三角形是一个循环，因此它没有边界。
拓扑信息传递可以看作是代数算子（例如边界算子）的（非线性）推广。因此，拓扑信息传递表现类似是有必要的：我们希望各层的输出能够“一致”地响应输入复合物方向的变化。换句话说，我们希望我们的层是方向等值的。在工作中，我们研究了拓扑信息传递是如何通过选择合适的非线性和信息传递函数来满足这一特性，同时，纯卷积设置中也对这一点进行了研究。
最早已知的拓扑不变量之一、欧拉特征，最初用于柏拉图固体的分类，我们可以将其定义为每个维度中单元格数量的交替总和。令人惊讶的是，如果两个细胞复合体是同胚的，即便它们是同一空间的不同离散，这些和也将是一致的。
有趣的是，拓扑信息传递模型的读出操作，使其能很容易计算出该拓扑的不变性，因为它对每个维度单元应用了一个可包容不变量的还原。
因此，这类模型在构造上可以区分某些非同构的空间（即具有不同的欧拉特征）。从计算的角度来看，这可以被看作是 WL 测试的一种推广，在 WL 测试中，我们不仅仅对确定两个细胞复合物是否相同感兴趣，也对它们是否彼此同构感兴趣。
离散霍奇理论为细胞复合物的拓扑性质提供了一个更几何的解释。当与k-细胞相关的特征符号取决于k-细胞的方向时，这些特征在数学上可被看作是微分几何中的微分k-形的离散版本（即可以被整合的k维体积元素）。一个被称为霍奇拉普拉斯的算子概括了图形拉普拉斯，它可作用于这些微分形式。可以证明，基于此拉普拉斯算子的扩散 PDE ，会在极限内收敛与复合物的洞的有关信号 。
图注：基于霍奇拉普拉斯算子的扩散偏微分方程，收敛于初始微分形式在拉普拉斯算子核上投影的极限。该图像显示了霍奇拉普拉斯算子的零特征向量是如何在复合体中的洞周围取高值。
第一个简单的神经网络模型实际上是基于霍奇拉普拉斯的卷积模型，反之，又受到拓扑信号处理的启发。就在最近，基于该算子的一个版卷积模型被用于解决计算代数拓扑学中的NP-hard问题。
最近有论文认为，除其他外，拓扑信息传递方法不过是在编码细胞复合体结构的修正图上操作信息传递的 GNN 。这对卷积模型来说是正确的，其信息传递计算涉及到成对的单元格。
然而，在其最一般的形式中，信息函数允许高维单元格调制其边界上的低维单元格之间传递的信息。一般情况下，能通过图上的常规信息传递，因为一条边正好连接两个节点，而一个2-单元格可以任意连接多的边。
在这两种情况下，计算都是由数据所依附的底层空间的拓扑结构所驱动的。我们相信，在信息传递上采用这种拓扑视角所带来的好处，要超出纯粹的计算考虑。除了有价值的数学联系外，它还为其他数学和计算学科打开了研究话语，有利于我们经常过于单调的社区之间的积极交叉融合。
我们预计拓扑信息传递方法的两个主要未来方向：
第一，多年来在GNN中开发的许多架构（如注意力机制）可能会在这些新的拓扑空间中被采用，同时可利用它们的特定特征。
其次，来自代数拓扑领域的更多数学对象和工具（包括诸如蜂窝滑轮之类的结构，即使是最精通数学的 ML 研究人员，对他们来说可能听起来也很陌生）将被图和几何深度学习社区采用。
这些方法既可以为老问题提供答案，也可以帮助解决新问题，正如Robert Ghrist 所说：「novel challenges necessitate novel math」（新的挑战需要新的数学）。
https://towardsdatascience.com/a-new-computational-fabric-for-graph-neural-networks-280ea7e3ed1a
雷峰网(公众号：雷峰网)
雷峰网版权文章，未经授权禁止转载。详情见转载须知。
