图神经网络的新计算结构

图神经网络 (GNN) 通常将其计算图与输入图的结构对齐。但是图是 GNN 的正确计算结构吗?最近的一系列论文通过用来自代数拓扑领域的更一般的对象替换图来挑战这一假设,这提供了多种理论和计算优势。 — 这篇文章是与 Cristian Bodnar 和 Fabrizio Frasca 合着的,基于 C. Bodnar、F. Frasca 等人、Weisfeiler 和 Lehman Go Topological: Message Passing Simplicial Networks (2021) ICML 和 C. Bodnar 等论文, F. Frasca 等人,Weisfeiler 和 Lehman Go Cellular:CW Networks (2021) NeurIPS。它…

学习拓扑空间

图神经网络的新计算结构

图神经网络 (GNN) 通常将其计算图与输入图的结构对齐。但是图是 GNN 的正确计算结构吗?最近的一系列论文通过用来自代数拓扑领域的更一般的对象替换图来挑战这一假设,这提供了多种理论和计算优势。

图神经网络的新计算结构

这篇文章是与 Cristian Bodnar 和 Fabrizio Frasca 合着,基于 C. Bodnar、F. Frasca 等人、Weisfeiler 和 Lehman Go Topological: Message Passing Simplicial Networks (2021) ICML 和 C. Bodnar, F . Frasca 等人,Weisfeiler 和 Lehman Go Cellular:CW Networks (2021) NeurIPS。它是通过微分几何和代数拓扑的镜头进行的图神经网络系列的一部分。另请参阅该系列中讨论神经扩散 PDE、使用 Ricci 流进行图形重新布线和蜂窝滑轮的其他帖子。[0][1][2][3][4][5]

“拓扑!人类思想的巅峰!在二十四世纪,它可能对某人有用。” ——亚历山大·索尔仁尼琴,在第一圈(1968)

图形用于模拟从计算机网络到大型强子对撞机中粒子相互作用的任何事物。图如此普遍的原因在于它们的离散和组合性质,允许它们表达抽象关系,同时保持对计算的服从。它们受欢迎的原因之一是图形抽象出几何图形,即节点在空间中的位置或边缘如何弯曲,只留下节点如何连接的表示。图论的起源源于莱昂哈德·欧拉 (Leonhard Euler) 于 1741 年在他关于几何位置(“位置的几何”)[1] 的工作中所做的这一观察,其中他表明著名的柯尼斯堡七桥问题没有解决方案。[0]

图神经网络的新计算结构

有趣的是,欧拉的发现不仅标志着图论的开始,而且也常常被视为拓扑学的诞生。与图一样,拓扑学家对独立于其特定形状或几何形状的空间属性感兴趣 [2]。这些思想的现代表现形式出现在 1895 年,即亨利·庞加莱 [3] 的一篇开创性论文“分析现场”。他的工作激发了人们对流形的组合描述的兴趣,从中可以更容易地找到和计算拓扑不变量。

图神经网络的新计算结构

这些组合描述今天被称为细胞复合体[8],可以被认为是图的更高维概括。与由节点和边组成的图不同,单元复合体还可以包含更高维的结构或“单元”:顶点是 0 单元,边是 1 单元,2D 表面是 2 单元,等等。要构建一个单元复合体,可以通过将一个单元的边界粘合到其他低维单元来分层进行。在单元由单纯形(例如边、三角形、四面体等)形成的特定情况下,这些空间也称为单纯形复形。

图神经网络的新计算结构

机器学习和数据科学中的拓扑

与我们选择打开这篇文章 [9] 的索尔仁尼琴角色的怀疑相反,人们不必等待四百年就可以将拓扑变成一种实用工具。诸如单纯复形之类的拓扑结构已在拓扑数据分析 (TDA) 的保护伞下用于机器学习和数据科学,这是 1990 年代出现的一类方法,试图分析“数据的形状”[4-7]以一种对度量不敏感且对噪声具有鲁棒性的方式。 TDA 的起源可以追溯到 1920 年代后期,可追溯到 20 世纪最多产的拓扑学家之一 Leopold Vietoris [43] 的工作。然而,这些技术必须等待现代计算的诞生才能大规模应用。[0]

图神经网络的新计算结构

TDA 的主力是 Persistent Homology (PH) [7],一种从点云中提取拓扑特征的方法。给定一个点数据集,PH 创建一个嵌套的单纯复形序列,其中每个复形对应于分析底层点云的特定比例。然后,它会跟踪随着规模逐渐增加以及一个从序列中的一个复合体过渡到下一个复合体而出现和消失的各种拓扑特征(例如,连接的组件、循环或空隙)。在深度学习时代,持久同源性在被证明可以通过它反向传播之后有了“第二生命”,从而允许将已经建立的 TDA 设备集成到深度学习框架中 [10-17]。[0]

最近的一系列作品提出了几何深度学习中单纯复形和细胞复形的不同用途,作为更丰富的底层拓扑空间来支持数据和在其上执行的计算。利用这一观点的前几项工作 [18-22] 提出了卷积模型以及在单纯复形上运行的随机游走方法 [42]。如我们的论文 [24,25] 所示,卷积模型可以理解为在单纯形和单元复合体 [23-25] 上传递消息的特定实例。因为计算是由这些空间的拓扑结构(即邻域结构)驱动的,所以我们将这组方法称为拓扑消息传递。在此框架中,可能具有不同维度的相邻单元正在交换消息,如下所示。

图神经网络的新计算结构

超越 GNN 中的图

尽管细胞复合体提供了丰富的结构,但我们不能忽视图是迄今为止机器学习中最常见的拓扑对象,并且很少有数据集可以超越它们。尽管如此,我们表明仍然可以通过转换输入图来利用这些有趣的拓扑空间。我们将图转换为高维拓扑空间称为“提升”,类似于范畴论中的同名概念。它是一种按照特定规则将高维单元格附加到输入图的转换。例如,可以通过将高维单元附加到图形的每个团或循环来将图形提升为单元复合体。通过这样做,图被替换为具有更多结构的不同空间,并且可以为 GNN 提供比原始图更好的计算结构。在下文中,我们将讨论这种方法的具体优势。

图神经网络的新计算结构

高阶特征和结构。 GNN 通常采用以节点为中心的视图,其中位于边缘的数据仅被视为增强顶点之间通信的辅助信息。在拓扑消息传递中,所有单元都是一等公民。无论它们的维度如何,它们都被分配了一个特定的表示,该表示是通过与相邻单元交换消息而演变的。这为显式建模某些高阶结构以及它们之间的相互作用提供了一个方法。特别是,它提供了一种有原则的方法来进化输入图的边缘(即 1 单元)特征,这是一大类 GNN 模型没有考虑的。

高阶交互。根据定义,图是二元的(“成对的”),不能表示涉及两个以上对象的关系和交互[26]。在对以高阶相互作用为特征的复杂系统进行建模时,这可能是一个问题:例如,化学反应中的三种反应物可能同时发生相互作用。在细胞复合体中,这种情况可以通过用 2 细胞(即“填充”三角形)连接反应物来编码。因此,模型的计算流程适应高阶交互的存在。

图神经网络的新计算结构

表现力。消息传递 GNN 的表达能力受到 Weisfeiler-Leman (WL) 图同构测试 [27-29] 的限制。众所周知,WL 无法检测某些图子结构,例如三角形或循环,即使是非常简单的非同构图也无法区分。在我们的论文 [24,25] 中,我们介绍了 WL 测试 (CWL) 的细胞版本,可用于测试细胞复合物的同构性。当这个新测试与上述的图提升程序配对时,我们证明它可以区分比 WL 测试更大的图类。在某些条件下,我们提出的拓扑消息传递程序继承了该测试的好处,与标准 GNN [24,25,30] 相比,表达能力有所提高。

不足、过度平滑和瓶颈。消息传递 GNN 需要 n 层来使 n 跳外的节点进行通信。因此,当仅使用几层时,相距较远的节点无法交换消息,这种现象称为未达到 [31,32]。相比之下,使用太多层可能会导致过度平滑 [33,34],并且消息可能会在图的结构瓶颈 [32] 中丢失。单元复合体可以缓解这些问题,因为由高维单元诱导的更丰富的邻域结构在可能相距很远的节点之间创建了捷径。因此,信息通过一定数量的计算步骤有效地传播。

图神经网络的新计算结构

分层建模。拓扑消息传递执行的计算自然是分层的,信息从低维单元流向高维单元并返回。这可以看作是“垂直”(和可微)池的一种形式,而不是标准图神经网络中的“水平”池。这保持了“压缩”图区域的归纳偏差,而不会忽略输入图的细粒度信息,这通常会损害基于池的 GNN 的性能。

图神经网络的新计算结构

域对齐。某些应用自然与细胞复合物的结构一致。例如,分子的原子、键和化学环可以表示为 0-cell、1-cell 和 2-cell。分子的物理结构和细胞复合体表示之间的直接对应自然允许拓扑消息传递利用上述特性。使用这些表示,我们展示了拓扑消息传递在分子特性预测任务中实现了最先进的结果 [25]。其他良好对齐的应用程序可能包括计算机图形应用程序中的离散流形(网格)、社交网络(其中派系特别重要)或空间图,如谷歌地图(街道之间的街区可以自然地表示为“立方”细胞) .

图神经网络的新计算结构

拓扑和微分几何相遇的地方

拓扑消息传递保留了与代数拓扑和微分几何的许多有趣联系,从而允许利用迄今为止在图形和几何深度学习中未被充分探索的数学工具。

孔代数和方向等变。在代数拓扑中,通常使用有向单纯复形,其中每个单纯形中存在任意“定向”。例如,对于每条边,我们选择一个源节点和一个目标节点,对于每个三角形,我们选择一个遍历其节点的顺序。一旦选择了方向,我们就可以对复形执行有趣的代数运算,例如通过“边界算子”计算某些单纯形的边界。这些代数运算也可以用来在单纯复形中找到“洞”——没有边界但不在其他事物边界上的区域。在幕后,持久同源依赖于这些计算来检测拓扑特征。

图神经网络的新计算结构

拓扑消息传递可以看作是代数算子(例如边界算子)的(非线性)推广。因此,拓扑消息传递有必要表现得类似:我们希望我们层的输出“一致地”响应输入复合体方向的变化。换句话说,我们希望我们的层是方向等变的。在我们的工作 [24] 中,我们研究了拓扑消息传递如何通过选择正确的非线性和消息传递函数来满足此属性。同时,这也在纯卷积设置中得到了检验[20]。

区分拓扑空间。最早已知的拓扑不变量之一,欧拉特征 [8,41],最初用于柏拉图固体的分类。我们可以将其定义为每个维度中单元格数量的交替总和。令人惊讶的是,如果两个细胞复合体是同胚的,那么这些和将是相同的,即使它们是同一空间的非常不同的离散化。

一个有趣的事实是,拓扑消息传递模型的读出操作可以很容易地计算出这个拓扑不变量,因为它对每个维度的单元格应用了置换不变约简。因此,这种类型的模型通过构造来区分某些非同胚的空间(即具有不同的欧拉特征)。从计算的角度来看,这可以看作是 WL 测试的推广,我们不仅对确定两个细胞复合体是否严格相同感兴趣,而且对它们是否彼此同胚感兴趣。

离散霍奇理论为细胞复合物的拓扑性质提供了更几何的解释。当与 k 单元相关的特征的符号取决于 k 单元的方向时,这些特征在数学上可以看作是微分几何中微分 k 形式的离散版本(即 k 维体积元素,可以综合)[45]。一个拉普拉斯算子推广图拉普拉斯算子,称为霍奇拉普拉斯算子 [21,44],可以作用于这些微分形式。可以证明,基于此拉普拉斯算子的扩散 PDE 在极限内收敛到与复合物的空穴有关的信号 [44]。[0]

图神经网络的新计算结构

第一个简单的神经网络模型 [18-20] 实际上是基于 Hodge Laplacian 的卷积模型,反过来又受到拓扑信号处理的启发 [21,22]。最近,基于该算子的一个版本的卷积模型被用于解决计算代数拓扑中的 NP-hard 问题 [35]。

Final thoughts

这些只是变相的图表吗?最近的论文 [36,37] 认为,除其他外,拓扑消息传递方法只不过是在编码细胞复合体结构的修改图上运行的消息传递 GNN。这对于卷积模型来说当然是正确的,其消息传递计算涉及成对的单元格。然而,在其最一般的形式中,消息函数允许高维单元格调制在其边界上的低维单元格之间传递的消息。这(通常)不再可能通过图上的常规消息传递来实现,因为一条边恰好连接两个节点,而一个 2-cell 可以连接任意数量的边。

在任何一种情况下,计算都是由数据附加到的底层空间的拓扑驱动的。我们相信,在消息传递中采用这种拓扑观点具有超越纯粹计算考虑的好处。除了有价值的数学联系外,它还为其他数学和计算学科打开了研究话语权,并有利于我们通常过于单一的社区之间的积极交叉授粉。

拓扑消息传递的下一步是什么?我们预计拓扑消息传递方法的两个主要未来方向。首先,多年来在 GNN 中开发的许多架构(例如注意力机制 [38,39])可能会在这些新的拓扑空间中采用,同时利用它们的特定特征。其次,图形和几何深度学习社区将采用来自代数拓扑领域的其他数学对象和工具(包括诸如蜂窝滑轮 [40] 之类的结构,即使对于最精通数学的 ML 研究人员来说也可能听起来很陌生)。这些方法既可以为旧问题提供答案,也可以帮助解决新问题,或者,正如 Robert Ghrist 所说:“新的挑战需要新的数学”。[0]

[1] L. Euler, Solutio problematis ad geometriam situs pertinentis (1741), Eneström 53, Euler 档案。[0]

[2] 粗略地说,拓扑使用邻域的概念而不是距离或角度,这是几何构造。

[3] H. Poincaré,Analysis situs (1895),Journal de l’École Polytechnique。

[4] P. Frosini, A distance for Similar classes of submanifolds of a Euclidean space (1990), Bulletin of the Australian Mathematical Society 42(3):407–415。

[5] H. Edelsbrunner 等人,拓扑持久性和简化 (2002),离散和计算几何 28(4):511-533。

[6] G. Carlsson,拓扑和数据(2009 年),美国数学会公报 46:255-308。

[7] H. Edelsbrunner 和 J. Harer。计算拓扑:介绍(2010 年),美国数学会。

[8] A. Hatcher,代数拓扑(2002 年),剑桥大学出版社。

[9] 俄语原文:“Топология! Стратосфера человеческой мысли! В двадцать четвёртом столетии она, может быть, и понадобится кому-нибудь。”在小说中,这个判断是由半自传人物格列布·内尔任(Gleb Nerzhin)做出的,他是一位数学家,他在浮士德式的问题上苦苦挣扎,即是否从事有助于斯大林政权的应用研究。作者 Aleksandr Solzhenitsyn 本人是一名受过训练的数学家,请参阅 Robert Ghrist 讲座上的注释,我们从中窃取了这句话。[0]

[10] M. Horn、E. De Brouwer 等人。拓扑图神经网络 (2022),ICLR。[0]

[11] R. Gabrielsson 等人,机器学习的拓扑层 (2020),AISTATS。[0]

[12] M. Moor 等人,拓扑自动编码器 (2020),ICML。[0]

[13] C. Hofer 等人,具有拓扑特征的深度学习 (2017),NIPS。[0]

[14] C. Hofer 等人,通过持久同源进行连接优化表示学习 (2019),ICML。[0]

[15] C. Hofer 等人,持久性条形码的学习表示 (2019),JMLR 20(126):1-45, 2019。[0]

[16] C. Hofer 等人,图过滤学习 (2020),ICML[0]

[17] C. Hofer 等人,拓扑致密分布 (2020),ICML[0]

[18] E. Bunch 等人。简单 2 复卷积神经网络 (2020),NeurIPS 拓扑数据分析及其他研讨会。[0]

[19] S. Ebli 等人。简单神经网络 (2020),NeurIPS 拓扑数据分析及其他研讨会。[0]

[20] M. T. Roddenberry、N. Glaze 和 S. Segarra,用于轨迹预测的原理简单神经网络 (2021),ICML。[0]

[21] S.巴巴罗萨等人。单纯复形上的拓扑信号处理 (2020),IEEE Transactions on Signal Processing 68:2992–3007。[0]

[22] S. Sardellitti 等人。细胞复合物的拓扑信号处理(2021 年),信号、系统和计算机的 Asilomar 会议。[0]

[23] M. Hajij 等人。 Cell Complex Neural Networks (2020),NeurIPS 拓扑数据分析及其他研讨会。[0]

[24] C. Bodnar、F. Frasca、Y. G. Wang、G. Montúfar 等人。 Weisfeiler 和 Lehman 进入拓扑:消息传递简单网络 (2021),ICML。[0]

[25] C. Bodnar、F. Frasca 等人。 Weisfeiler 和 Lehman 使用蜂窝网络:CW Networks (2021),NeurIPS。[0]

[26] F. Battiston 等人,复杂系统中高阶相互作用的物理学(2021 年),自然物理学 17:1093–1098。[0]

[27] B. Weisfeiler 和 A. Leman,将图简化为规范形式和其中出现的代数(1968 年),Nauchno-Technicheskaya Informatsia 2(9):12-16。请参阅有关 WL 测试和 GNN 关系的帖子。如需深入回顾(和历史记录),请参阅 C. Morris 等人,Weisfeiler 和 Leman 的机器学习:迄今为止的故事 (2021) arXiv:2112.09992。[0][1][2]

[28] K. Xu 等人,图神经网络有多强大? (2019 年),ICLR。[0]

[29] C. Morris 等人,Weisfeiler 和 Leman Go Neural:高阶图神经网络 (2019),AAAI。[0]

[30] 我们注意到,与我们的方法正交,WL 测试的持久版本是由 B. Rieck 等人提出的,A Persistent Weisfeiler-Lehman Procedure for Graph Classification (2019),ICML。同时,持久同源性也被用来使 GNN 比 WL 测试更具表现力 [10]。[0]

[31] P. Barceló 等人,图神经网络的逻辑表达能力 (2020),ICLR。

[32] U. Alon 和 E. Yahav,关于图神经网络的瓶颈及其实际意义(2021 年),ICLR。[0]

[33] K. Oono 和 T. Suzuki,图神经网络以指数方式失去节点分类的表达能力(2020 年),ICLR。[0]

[34] C. Cai 和 Y. Wang, A note on over-smoothing for Graph Neural Networks (2020), arXiv:2006.13318。[0]

[35] A. D. Keros 等人,Dist2Cycle:用于同源定位的简单神经网络 (2021),AAAI。[0]

[36] P. Veličković,消息一直向上传递(2022 年),ICLR 几何和拓扑表示学习研讨会。[0][1]

[37] F. Jogl 等人。将细胞复合体的学习减少为图形(2022 年),ICLR 几何和拓扑表示学习研讨会。[0]

[38] C. W. J. Goh 等人。简单注意网络 (2022),ICLR 几何和拓扑表示学习研讨会。[0]

[39] L. Giusti 等人,Simplicial Attention Neural Networks (2022),arXiv:2203.07485。[0]

[40] C. Bodnar、F. Di Giovanni 等人,Neural Sheaf Diffusion:A Topological Perspective on Heterophily and Oversmoothing in GNN (2022) arXiv:2202.04579。另请参阅随附的帖子。[0][1]

[41] L. Euler, Elementa doctrinae solidorum (1758), Novi Commentarii Academiae Scientiarum Petropolitanae:109-140。

[42] C. Hacker,k-simplex2vec:node2vec (2020) 的简单扩展,NeurIPS 拓扑数据分析及其他研讨会。

[43] L. Vietoris, Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen (1927), 数学年鉴 97:454–472。[0]

[44] A. Muhammad 和 M. Egerstedt,在网络拓扑中使用高阶拉普拉斯算子进行控制(2006 年),网络和系统数学理论国际研讨会。

[45] 当限制在边缘时,这些信号可以很好地解释为流过网络的流。例如,参见 T. Gebhart 等人,顺其自然?使用霍奇理论 (2021) 对美国医疗保健提供网络进行大规模分析,IEEE 大数据 2021 作为拓扑数据分析在大数据中的应用研讨会的一部分。[0]

我们感谢 Ben Chamberlain 和 Bastian Rieck 校对了这篇文章。有关图表深度学习的更多文章,请参阅我在 Towards Data Science 中的其他帖子、订阅我的帖子、获得 Medium 会员资格或在 Twitter 上关注我。[0][1][2][3]

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
上一篇 2022年6月13日 下午12:47
下一篇 2022年6月14日 上午10:54