Michael Bronstein從代數拓樸學取經，提出了一種新的圖神經網路運算結構！

本文由Cristian Bodnar 和Fabrizio Frasca 合著，以 C. Bodnar 、F. Frasca 等人发表于2021 ICML《Weisfeiler and Lehman Go Topological: 信息传递简单网络》和2021 NeurIPS 《Weisfeiler and Lehman Go Cellular: CW 网络》论文为参考。

本文仅是通过微分几何学和代数拓扑学的视角讨论图神经网络系列的部分内容。

从计算机网络到大型强子对撞机中的粒子相互作用，图可以用来模拟任何东西。图之所以无处不在，是因为它们具有离散性和组合性，这使得它们能够表达抽象关系，同时又易于计算。它们受欢迎的原因之一是图抽象出几何图形，即节点在空间中的位置或边缘是如何弯曲的，只留下节点如何连接的表示。

图论起源于莱昂哈德 · 欧拉（Leonhard Euler）在1741年的著作《geometria situs》中的观察，他指出著名的柯尼斯堡七桥问题问题没有解决方案。

图注：七桥问题要求在哥尼斯堡市内找到一条循环行走的路线，不需要多次过桥。正如欧拉所说，哥尼斯堡市的确切形状并不重要，重要的是不同的土地（图的节点）是如何相互连接的（边）。欧拉表明，当且仅当所有节点具有偶数度时，这样的循环才存在。另外，最初的桥梁中只有五座存活到现代。图源：维基百科

有趣的是，欧拉的发现不仅标志着图论的开始，而且也常常被认为是拓扑学诞生的标志。与图一样，拓扑学家对空间的那些与其特定形状或几何形状无关的属性感兴趣。

这些思想的现代表现形式出现在1895年的“分析地点” （Analysis situs），这是 Henri Poincaré 的一篇开创性的论文，他的工作点燃了对流形的组合描述的兴趣，从这些流形中可以更容易地找到和计算拓扑不变量。

图注：Leonhard Euler（1707-1783）和 Henri Poincaré（1854-1912）

这些组合描述今天被称为细胞复合体 ，可以被认为是图的高维概括。

与由节点和边形成的图不同，细胞复合体也可以包含更高维的结构或“细胞”：顶点是0-细胞，边是1-细胞，2D 表面是2-细胞等。为了构建一个细胞复合体，我们可以通过将一个细胞的边界粘合到其他低维细胞上来进行分层。

在特殊情况下，当单元格由单形（如边、三角形、四面体等）构成时，这些空间也称为单形复合体。

图注：图可以看作是我们附加边（1-单元格）的一组顶点。类似地，单细胞复合体和细胞复合体可以看作是我们连接2-细胞（蓝色显示）、3-细胞（绿色显示）等的图形。

1 机器学习与数据科学中的拓扑

我们认为，人们不必等待 400 年才将把拓扑学变成一种实用的工具。

在拓扑数据分析（TDA）的保护伞下，诸如浅层复合物这样的拓扑结构已经被用于机器学习和数据科学，这类方法出现在20世纪90年代，试图以一种对度量不敏感和对噪声稳健的方式来分析“数据的形状”。

TDA的根源可以追溯到20世紀20年代末最多產的拓撲學家之一 Leopold Vietnam oris 的工作。然而，這些技術必須等到現代計算的誕生才能大規模應用。

圖註：給定一個點雲，每個點周圍固定半徑的封閉球之間的交叉點產生一個簡單的複合體。透過逐步增加球的半徑，我們可以得到一個嵌套的簡單複合體序列。圖源：Bastian Rieck。

TDA 的主力是持久性同源性（PH），一種從點雲中提取拓樸特徵的方法。給定一個點的資料集，PH 建立一個簡單複數的巢狀序列，其中每個複數對應於分析基礎點雲的某個比例。然後，它追蹤各種拓撲特徵（例如，連接的組件、循環或空洞） ，這些特徵隨著比例的逐漸增加而出現和消失，並且人們從序列中的一個複合物過渡到下一個複合物。

在深度學習時代，持久性同源性有了“第二次生命”，因為它表明人們可以通過它進行反向傳播，從而允許將已經建立的TDA 設備整合到深度學習框架中。

最近的一系列工作提出了在幾何深度學習中簡化和細胞複合體的不同用途，作為一個更豐富的底層拓撲空間來支持數據和對其進行的計算。

最早利用這一觀點的幾項工作提出了卷積模型以及在簡化複合體上操作的隨機行走方法。如在本文中，卷積模型可以被理解為簡單和細胞複合體上訊息傳遞的具體實例。

由於計算是由這些空間的拓樸（即鄰域結構）所驅動的，我們把這套方法稱為拓樸資訊傳遞。在這個框架中，相鄰的單元，可能是不同維度的，正在交換訊息，如下圖所示。

圖註：拓樸資訊傳遞示意圖。藍色箭頭描述了上層相鄰細胞之間的「水平」訊息傳播，即同一高維細胞的邊界上的細胞。紅色箭頭描述了「垂直」訊息傳播，即細胞從其邊界的低維細胞中接收訊息。將來自邊界細胞的資訊匯總到一個更粗的表示中，這種計算可以被解釋為一種（可微分的）集合形式。

在GNN 中超越圖

儘管細胞複合體提供了豐富的結構，但我們不能忽視圖是迄今為止機器學習中最常見的拓樸對象，而且很少有資料集能超越它們。儘管如此，人們仍然可以透過轉換輸入圖來利用這些有趣的拓樸空間。

我們把圖轉換為高維拓撲空間稱為“提升”，以類似於範疇理論中的同名概念。它是一種轉換，透過遵循某些規則將高維單元附加到輸入圖上。例如，一個圖可以透過在圖的每個懸崖或週期上附加一個高維單元而被提升為一個單元複合體。透過這樣做，圖被替換成一個不同的空間，它有更多的結構，可以為GNN提供一個比原始圖更好的計算結構。在下文中，我們將討論這種方法的具體優勢。

圖註：透過將二維封閉圓盤的邊界黏合到圖中的誘導循環上，可以從圖中構造出高維度的細胞複合體。

#

高階特徵和結構

GNN通常採用以節點為中心的觀點，駐留在邊上的資料僅被視為增加頂點間通訊的輔助資訊。在拓樸訊息傳遞中，所有單元都是一等公民。無論它們的維度如何，它們都被分配了一個特定的表示，這個表示是透過與相鄰的單元交換資訊而發展起來的。這為明確地模擬某些高階結構和它們之間的相互作用提供了一個秘訣。特別是，它提供了一種原則性的方法來演化輸入圖的邊緣（即1個單元）特徵，這是一大類 GNN 模型沒有考慮到的問題。

高階交互

圖表根據定義是二元的（「成對的」），不能表示涉及兩個以上物件的關係和交互。在對以高階相互作用為特徵的複雜系統進行建模時，這可能是一個問題：例如，化學反應中的三種反應物可能同時發生相互作用。在細胞複合體中，這種情況可以透過兩個細胞（即「填充」三角形）連接反應物來編碼。因此，模型的計算流程適應高階交互作用的存在。

圖註：細胞Weisfeiler-Lehman（CWL）測試，將經典的WL測試擴展到細胞群，演算法的每一步都完美地散列了相鄰單元的顏色（可能有不同的維度）。

表現力

訊息傳遞GNN 的表達能力受Weisfeiler-Leman (WL) 圖同構測試限制，眾所周知，WL 無法偵測某些圖子結構，例如三角形或循環，即使是非常簡單的非同構圖也無法區分。

根據先前的論文顯示（論文地址：https://arxiv.org/abs/2103.03212；https://arxiv.org/ abs/2106.12575），WL 測試(CWL) 的細胞版本可用來測試細胞複合物的同構性。當這個新測試與上面描述的圖提升過程相符時，可以發現，它能比 WL 測試區分更大的圖類。因此，在一定條件下，拓樸信息傳遞過程繼承了此測試的優點，相較於標準 GNN 提高了表達能力。

不足、過度平滑和瓶頸

訊息傳遞的 GNN 需要n個層來使相距n個跳數的節點進行通訊。當只使用幾層，以至於相距較遠的節點無法交換信息時，這種現象稱為未達到。

相較之下，使用太多層可能會導致過度平滑，且資訊可能會在圖的結構瓶頸中遺失。

單元複合體可以緩解這些問題，因為由高維單元誘導的更豐富的鄰域結構，在可能相距很遠的節點之間創建了捷徑。因此，資訊只需包含一些計算步驟來傳播，就是有效的。

圖註：GNN 需要很多層才能讓相距很遠的節點進行通訊（左）。高維單元透過創造捷徑來改變空間的底層拓樸（右）。這允許遠端節點在幾個資訊傳遞步驟中交換資訊。

分層建模

拓撲信#利息傳遞執行的計算是分層的，訊息從低維單元流向高維單元並返回，可看作是「垂直」（和可區分）池的一種形式，而非標準圖神經網路中的「水平」池。這保持了「壓縮」圖區域的歸納偏差，而不會忽略輸入圖的會損害基於 GNN 池性能的細粒度資訊。

#

圖註：拓撲訊息傳遞允許資訊存在於不同維度的單元之間分層

域對齊

##某些應用自然與細胞複合物的結構一致，例如，分子的原子、鍵結和化學環可以表示為0-cell、1-cell 和2-cell，分子的物理結構和細胞的複雜表示之間的直接對應，允許了拓樸資訊傳遞利用上述特性，這些表示也展示了拓樸信息傳遞在分子特性預測任務中所實現的最先進結果。

其他表現良好對齊的應用程序，可能包括電腦圖形應用程式中的離散流形（網格）、社交網路（派系特別重要）或空間圖，例如Google地圖（街道間的街區可自然表示為「立方」細胞） 。

圖註：咖啡因子被建模為二維細胞複合物

2 拓樸學和微分幾何學的結合

拓樸訊息傳遞中，保留了許多與代數拓樸學、微分幾何學的有趣聯繫，允許使用迄今為止仍在圖和幾何深度學習中沒有充分開發的數學工具。

洞代數和方向等值

在代數拓撲中，通常使用有向單純複形，其中每個單純形存在任意“定向”，例如，我們選擇每條邊中的一個來源節點和一個目標節點，並對每個三角形選擇一個遍歷其節點的順序。一旦選定方向後，就可對複形執行有趣的代數算子，例如透過「邊界算子」計算某些單純形的邊界。這些代數運算也可以用來在單純複形中找到「洞」——沒有邊界但不在其他事物邊界上的區域。背後，持久同源依靠這些計算來偵測拓樸特徵。

圖註：應用於 2-單純形的邊界算子產生一個三角形。再次將算子應用於三角形，結果為零，由於三角形是一個循環，因此它沒有邊界。 拓樸訊息傳遞可以看作是代數算符（例如邊界算子）的（非線性）推廣。因此，拓樸信息傳遞表現類似是有必要的：我們希望各層的輸出能夠「一致」地響應輸入複合物方向的變化。換句話說，我們希望我們的層是方向等值的。在工作中，我們研究了拓樸

信

息傳遞是如何透過選擇合適的非線性和

信

息傳遞函數來滿足這一特性，同時，純卷積設定中也對這一點進行了研究。

區分拓樸空間

最早已知的拓樸不變量之一、歐拉特徵，最初用於柏拉圖固體的分類，我們可以將其定義為每個維度中單元格數量的交替總和。令人驚訝的是，如果兩個細胞複合體是同胚的，即便它們是同一空間的不同離散，這些和也將是一致的。

有趣的是，拓樸資訊傳遞模型的讀出操作，使其能很容易計算出該拓撲的不變性，因為它對每個維度單元應用了一個可包容不變量的還原。

#########因此，這類模型在建構上可以區分某些非同構的空間（即具有不同的歐拉特徵）。從計算的角度來看，這可以被看作是 WL 測試的一種推廣，在 WL 測試中，我們不僅對確定兩個細胞複合物是否相同感興趣，也對它們是否彼此同構感興趣。 ######

離散霍奇理論

離散霍奇理論為細胞複合物的拓樸性質提供了一個更幾何的解釋。當與k-細胞相關的特徵符號取決於k-細胞的方向時，這些特徵在數學上可被看作是微分幾何中的微分k-形的離散版本（即可以被整合的k維體積元素） 。一個被稱為霍奇拉普拉斯的算子概括了圖形拉普拉斯，它可作用於這些微分形式。可以證明，基於此拉普拉斯算子的擴散 PDE ，會在極限內收斂與複合物的洞的有關訊號 。

圖註：基於霍奇拉普拉斯算子的擴散偏微分方程，收斂於初始微分形式在拉普拉斯算子核上投影的極限。此影像顯示了霍奇拉普拉斯算子的零特徵向量是如何在複合體中的洞周圍取高值。

第一個簡單的神經網路模型其實是基於何杰拉普拉斯的捲積模型，反之，又受到拓樸訊號處理的啟發。就在最近，基於該算子的一個版卷積模型被用來解決計算代數拓樸學中的NP-hard問題。

3 最後的思考

這些只是變相的圖表嗎？

最近有論文認為，除此之外，拓樸訊息傳遞方法不過是在編碼細胞複合體結構的修正圖上操作訊息傳遞的 GNN 。這對卷積模型來說是正確的，其資訊傳遞計算涉及成對的單元格。

然而，在其最一般的形式中，信息函數允許高維單元格調製其邊界上的低維單元格之間傳遞的資訊.一般情況下，能透過圖上的常規信息傳遞，因為一邊剛好連接兩個節點，而一個2-單元格可以任意連接多的邊。

在這兩種情況下，計算都是由資料所依附的底層空間的拓樸結構所驅動的。我們相信，在訊息傳遞上採用這種拓樸視角所帶來的好處，要超越純粹的計算考量。除了有價值的數學聯繫外，它還為其他數學和計算學科打開了研究話語，有利於我們經常過於單調的社區之間的積極交叉融合。

拓樸訊息傳遞的下一步是什麼？

我們預期拓樸訊息傳遞方法的兩個主要未來方向：

#第一，多年來在GNN中開發的許多架構（如注意力機制）可能會在這些新的拓樸空間中被採用，同時可利用它們的特定特徵。

其次，來自代數拓撲領域的更多數學物件和工具（包括諸如蜂窩滑輪之類的結構，即使是最精通數學的ML 研究人員，對他們來說可能聽起來也很陌生）將被圖和幾何深度學習社群採用。

這些方法既可以為舊問題提供答案，也可以幫助解決新問題，正如Robert Ghrist 所說：「novel challenges necessitate novel math」（新的挑戰需要新的數學）。

以上是Michael Bronstein從代數拓樸學取經，提出了一種新的圖神經網路運算結構！的詳細內容。更多資訊請關注PHP中文網其他相關文章！