在线客服
企业微信
Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！
图注：七桥问题要求在哥尼斯堡市内找到一条循环行走的路线，不需要多次过桥。正如欧拉所说，哥尼斯堡市的确切形状并不重要，重要的是不同的土地（图的节点）是如何相互连接的（边）。欧拉表明，当且仅当所有节点具有偶数度时，这样的循环才存在。另外，最初的桥梁中只有五座存活到现代。
有趣的是，欧拉的发现不仅标志着图论的开始，而且也常常被认为是拓扑学诞生的标志。与图一样，拓扑学家对空间的那些与其特定形状或几何形状无关的属性感兴趣。
这些思想的现代表现形式出现在1895年的“分析地点” （Analysis situs），这是 Henri Poincaré 的一篇开创性的论文，他的工作点燃了对流形的组合描述的兴趣，从这些流形中可以更容易地找到和计算拓扑不变量。
Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！
这些组合描述今天被称为细胞复合体 ，可以被认为是图的高维概括。
与由节点和边形成的图不同，细胞复合体也可以包含更高维的结构或“细胞”：顶点是0-细胞，边是1-细胞，2D 表面是2-细胞等。为了构建一个细胞复合体，我们可以通过将一个细胞的边界粘合到其他低维细胞上来进行分层。
在特殊情况下，当单元格由单形（如边、三角形、四面体等）构成时，这些空间也称为单形复合体。
Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！
1
机器学习与数据科学中的拓扑
我们认为，人们不必等待 400 年才将把拓扑学变成一种实用的工具。
在拓扑数据分析（TDA）的保护伞下，诸如浅层复合物这样的拓扑结构已经被用于机器学习和数据科学，这类方法出现在20世纪90年代，试图以一种对度量不敏感和对噪声稳健的方式来分析“数据的形状”。
TDA的根源可以追溯到20世纪20年代末最多产的拓扑学家之一 Leopold Vietnam oris 的工作。然而，这些技术必须等到现代计算的诞生才能大规模应用。
Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！
给定一个点云，每个点周围固定半径的封闭球之间的交叉点产生一个简单的复合体。通过逐步增加球的半径，我们可以得到一个嵌套的简单复合体序列。图源：Bastian Rieck。
TDA 的主力是持久性同源性（PH），一种从点云中提取拓扑特征的方法。给定一个点的数据集，PH 创建一个简单复数的嵌套序列，其中每个复数对应于分析基础点云的某个比例。然后，它跟踪各种拓扑特征（例如，连接的组件、循环或空洞） ，这些特征随着比例的逐渐增加而出现和消失，并且人们从序列中的一个复合物过渡到下一个复合物。
在深度学习时代，持久性同源性有了“第二次生命”，因为它表明人们可以通过它进行反向传播，从而允许将已经建立的 TDA 设备集成到深度学习框架中。
最近的一系列工作提出了在几何深度学习中简化和细胞复合体的不同用途，作为一个更丰富的底层拓扑空间来支持数据和对其进行的计算。
最早利用这一观点的几项工作提出了卷积模型以及在简化复合体上操作的随机行走方法。如在本文中，卷积模型可以被理解为简单和细胞复合体上信息传递的具体实例。
由于计算是由这些空间的拓扑结构（即邻域结构）驱动的，我们把这套方法称为拓扑信息传递。在这个框架中，相邻的单元，可能是不同维度的，正在交换信息，如下图所示。
Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！
拓扑信息传递示意图。蓝色箭头描述了上层相邻细胞之间的“水平”信息传播，即同一高维细胞的边界上的细胞。红色箭头描述了“垂直”信息传播，即细胞从其边界的低维细胞中接收信息。将来自边界细胞的信息汇总到一个更粗的表示中，这种计算可以被解释为一种（可微分的）集合形式。
在 GNN 中超越图
尽管细胞复合体提供了丰富的结构，但我们不能忽视图是迄今为止机器学习中最常见的拓扑对象，而且很少有数据集能超越它们。尽管如此，人们仍然可以通过转换输入图来利用这些有趣的拓扑空间。
我们把将图转换为高维拓扑空间称为“提升”，以类似于范畴理论中的同名概念。它是一种转换，通过遵循某些规则将高维单元附加到输入图上。例如，一个图可以通过在图的每个悬崖或周期上附加一个高维单元而被提升为一个单元复合体。通过这样做，图被替换成一个不同的空间，它有更多的结构，可以为GNN提供一个比原始图更好的计算结构。在下文中，我们将讨论这种方法的具体优势。
Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！
通过将二维封闭圆盘的边界粘合到图中的诱导循环上，可以从图中构造出高维的细胞复合体。
高阶特征和结构
GNN通常采用以节点为中心的观点，驻留在边上的数据仅被视为增加顶点间通信的辅助信息。在拓扑信息传递中，所有单元都是一等公民。无论它们的维度如何，它们都被分配了一个特定的表示，这个表示是通过与相邻的单元交换信息而发展起来的。这为明确地模拟某些高阶结构和它们之间的相互作用提供了一个秘诀。特别是，它提供了一种原则性的方法来演化输入图的边缘（即1个单元）特征，这是一大类 GNN 模型没有考虑到的问题。
高阶交互
图表根据定义是二元的（“成对的”），不能表示涉及两个以上对象的关系和交互。在对以高阶相互作用为特征的复杂系统进行建模时，这可能是一个问题：例如，化学反应中的三种反应物可能同时发生相互作用。在细胞复合体中，这种情况可以通过两个细胞（即“填充”三角形）连接反应物来编码。因此，模型的计算流程适应高阶交互的存在。
