Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！( 二 )

TDA的根源可以追溯到20世纪20年代末最多产的拓扑学家之一LeopoldVietnamoris的工作。然而，这些技术必须等到现代计算的诞生才能大规模应用。

文章图片
图注：给定一个点云，每个点周围固定半径的封闭球之间的交叉点产生一个简单的复合体。通过逐步增加球的半径，我们可以得到一个嵌套的简单复合体序列。图源：BastianRieck 。
TDA的主力是持久性同源性（PH），一种从点云中提取拓扑特征的方法。给定一个点的数据集， PH创建一个简单复数的嵌套序列，其中每个复数对应于分析基础点云的某个比例。然后，它跟踪各种拓扑特征（例如，连接的组件、循环或空洞），这些特征随着比例的逐渐增加而出现和消失，并且人们从序列中的一个复合物过渡到下一个复合物。
在深度学习时代，持久性同源性有了“第二次生命” ，因为它表明人们可以通过它进行反向传播，从而允许将已经建立的TDA设备集成到深度学习框架中。
最近的一系列工作提出了在几何深度学习中简化和细胞复合体的不同用途，作为一个更丰富的底层拓扑空间来支持数据和对其进行的计算。
最早利用这一观点的几项工作提出了卷积模型以及在简化复合体上操作的随机行走方法。如在本文中，卷积模型可以被理解为简单和细胞复合体上信息传递的具体实例。
由于计算是由这些空间的拓扑结构（即邻域结构）驱动的，我们把这套方法称为拓扑信息传递。在这个框架中，相邻的单元，可能是不同维度的，正在交换信息，如下图所示。

文章图片
图注：拓扑信息传递示意图。蓝色箭头描述了上层相邻细胞之间的“水平”信息传播，即同一高维细胞的边界上的细胞。红色箭头描述了“垂直”信息传播，即细胞从其边界的低维细胞中接收信息。将来自边界细胞的信息汇总到一个更粗的表示中，这种计算可以被解释为一种（可微分的）集合形式。
在GNN中超越图尽管细胞复合体提供了丰富的结构，但我们不能忽视图是迄今为止机器学习中最常见的拓扑对象，而且很少有数据集能超越它们。尽管如此，人们仍然可以通过转换输入图来利用这些有趣的拓扑空间。
我们把将图转换为高维拓扑空间称为“提升” ，以类似于范畴理论中的同名概念。它是一种转换，通过遵循某些规则将高维单元附加到输入图上。例如，一个图可以通过在图的每个悬崖或周期上附加一个高维单元而被提升为一个单元复合体。通过这样做，图被替换成一个不同的空间，它有更多的结构，可以为GNN提供一个比原始图更好的计算结构。在下文中，我们将讨论这种方法的具体优势。

文章图片
图注：通过将二维封闭圆盘的边界粘合到图中的诱导循环上，可以从图中构造出高维的细胞复合体。
高阶特征和结构GNN通常采用以节点为中心的观点，驻留在边上的数据仅被视为增加顶点间通信的辅助信息。在拓扑信息传递中，所有单元都是一等公民。无论它们的维度如何，它们都被分配了一个特定的表示，这个表示是通过与相邻的单元交换信息而发展起来的。这为明确地模拟某些高阶结构和它们之间的相互作用提供了一个秘诀。特别是，它提供了一种原则性的方法来演化输入图的边缘（即1个单元）特征，这是一大类GNN模型没有考虑到的问题。