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

文章图片
图形神经网络（GNNs）通常将其计算图与输入图的结构相一致。但是，图是GNN的正确计算结构吗？最近的一系列论文挑战了这一假设，用来自代数拓扑学领域的更普遍的对象取代了图，这提供了多种理论和计算优势。作者|MichaelBronstein等人
编译|黄楠、bingo
编辑|陈彩娴本文由CristianBodnar和FabrizioFrasca合著，以C.Bodnar、F.Frasca等人发表于2021ICML《WeisfeilerandLehmanGoTopological:信息传递简单网络》和2021NeurIPS《WeisfeilerandLehmanGoCellular:CW网络》论文为参考。
本文仅是通过微分几何学和代数拓扑学的视角讨论图神经网络系列的部分内容。
从计算机网络到大型强子对撞机中的粒子相互作用，图可以用来模拟任何东西。图之所以无处不在，是因为它们具有离散性和组合性，这使得它们能够表达抽象关系，同时又易于计算。它们受欢迎的原因之一是图抽象出几何图形，即节点在空间中的位置或边缘是如何弯曲的，只留下节点如何连接的表示。
【Michael Bronstein从代数拓扑学取经，提出了一种新的图神经网络计算结构！】图论起源于莱昂哈德·欧拉（LeonhardEuler）在1741年的著作《geometriasitus》中的观察，他指出著名的柯尼斯堡七桥问题问题没有解决方案。

文章图片
图注：七桥问题要求在哥尼斯堡市内找到一条循环行走的路线，不需要多次过桥。正如欧拉所说，哥尼斯堡市的确切形状并不重要，重要的是不同的土地（图的节点）是如何相互连接的（边）。欧拉表明，当且仅当所有节点具有偶数度时，这样的循环才存在。另外，最初的桥梁中只有五座存活到现代。图源：维基百科
有趣的是，欧拉的发现不仅标志着图论的开始，而且也常常被认为是拓扑学诞生的标志。与图一样，拓扑学家对空间的那些与其特定形状或几何形状无关的属性感兴趣。
这些思想的现代表现形式出现在1895年的“分析地点”（Analysissitus），这是HenriPoincaré的一篇开创性的论文，他的工作点燃了对流形的组合描述的兴趣，从这些流形中可以更容易地找到和计算拓扑不变量。

文章图片
图注：LeonhardEuler（1707-1783）和HenriPoincaré（1854-1912）
这些组合描述今天被称为细胞复合体，可以被认为是图的高维概括。
与由节点和边形成的图不同，细胞复合体也可以包含更高维的结构或“细胞”：顶点是0-细胞，边是1-细胞， 2D表面是2-细胞等。为了构建一个细胞复合体，我们可以通过将一个细胞的边界粘合到其他低维细胞上来进行分层。
在特殊情况下，当单元格由单形（如边、三角形、四面体等）构成时，这些空间也称为单形复合体。

文章图片
图注：图可以看作是我们附加边（1-单元格）的一组顶点。类似地，单细胞复合体和细胞复合体可以看作是我们连接2-细胞（蓝色显示）、3-细胞（绿色显示）等的图形。
1机器学习与数据科学中的拓扑我们认为，人们不必等待400年才将把拓扑学变成一种实用的工具。
在拓扑数据分析（TDA）的保护伞下，诸如浅层复合物这样的拓扑结构已经被用于机器学习和数据科学，这类方法出现在20世纪90年代，试图以一种对度量不敏感和对噪声稳健的方式来分析“数据的形状” 。