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