本文由Cristian Bodnar 和Fabrizio Frasca 合著，以 C. Bodnar 、F. Frasca 等人發(fā)表于2021 ICML《Weisfeiler and Lehman Go Topological: 信息傳遞簡單網(wǎng)絡(luò)》和2021 NeurIPS 《Weisfeiler and Lehman Go Cellular: CW 網(wǎng)絡(luò)》論文為參考。

本文僅是通過微分幾何學(xué)和代數(shù)拓撲學(xué)的視角討論圖神經(jīng)網(wǎng)絡(luò)系列的部分內(nèi)容。

從計算機網(wǎng)絡(luò)到大型強子對撞機中的粒子相互作用，圖可以用來模擬任何東西。圖之所以無處不在，是因為它們具有離散性和組合性，這使得它們能夠表達抽象關(guān)系，同時又易于計算。它們受歡迎的原因之一是圖抽象出幾何圖形，即節(jié)點在空間中的位置或邊緣是如何彎曲的，只留下節(jié)點如何連接的表示。

圖論起源于萊昂哈德 · 歐拉（Leonhard Euler）在1741年的著作《geometria situs》中的觀察，他指出著名的柯尼斯堡七橋問題問題沒有解決方案。

圖注：七橋問題要求在哥尼斯堡市內(nèi)找到一條循環(huán)行走的路線，不需要多次過橋。正如歐拉所說，哥尼斯堡市的確切形狀并不重要，重要的是不同的土地（圖的節(jié)點）是如何相互連接的（邊）。歐拉表明，當且僅當所有節(jié)點具有偶數(shù)度時，這樣的循環(huán)才存在。另外，最初的橋梁中只有五座存活到現(xiàn)代。圖源：維基百科

有趣的是，歐拉的發(fā)現(xiàn)不僅標志著圖論的開始，而且也常常被認為是拓撲學(xué)誕生的標志。與圖一樣，拓撲學(xué)家對空間的那些與其特定形狀或幾何形狀無關(guān)的屬性感興趣。

這些思想的現(xiàn)代表現(xiàn)形式出現(xiàn)在1895年的“分析地點” （Analysis situs），這是 Henri Poincaré 的一篇開創(chuàng)性的論文，他的工作點燃了對流形的組合描述的興趣，從這些流形中可以更容易地找到和計算拓撲不變量。

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

這些組合描述今天被稱為細胞復(fù)合體 ，可以被認為是圖的高維概括。

與由節(jié)點和邊形成的圖不同，細胞復(fù)合體也可以包含更高維的結(jié)構(gòu)或“細胞”：頂點是0-細胞，邊是1-細胞，2D 表面是2-細胞等。為了構(gòu)建一個細胞復(fù)合體，我們可以通過將一個細胞的邊界粘合到其他低維細胞上來進行分層。

在特殊情況下，當單元格由單形（如邊、三角形、四面體等）構(gòu)成時，這些空間也稱為單形復(fù)合體。

圖注：圖可以看作是我們附加邊（1-單元格）的一組頂點。類似地，單細胞復(fù)合體和細胞復(fù)合體可以看作是我們連接2-細胞（藍色顯示）、3-細胞（綠色顯示）等的圖形。

1 機器學(xué)習(xí)與數(shù)據(jù)科學(xué)中的拓撲

我們認為，人們不必等待 400 年才將把拓撲學(xué)變成一種實用的工具。

在拓撲數(shù)據(jù)分析（TDA）的保護傘下，諸如淺層復(fù)合物這樣的拓撲結(jié)構(gòu)已經(jīng)被用于機器學(xué)習(xí)和數(shù)據(jù)科學(xué)，這類方法出現(xiàn)在20世紀90年代，試圖以一種對度量不敏感和對噪聲穩(wěn)健的方式來分析“數(shù)據(jù)的形狀”。

TDA的根源可以追溯到20世紀20年代末最多產(chǎn)的拓撲學(xué)家之一 Leopold Vietnam oris 的工作。然而，這些技術(shù)必須等到現(xiàn)代計算的誕生才能大規(guī)模應(yīng)用。

圖注：給定一個點云，每個點周圍固定半徑的封閉球之間的交叉點產(chǎn)生一個簡單的復(fù)合體。通過逐步增加球的半徑，我們可以得到一個嵌套的簡單復(fù)合體序列。圖源：Bastian Rieck。

TDA 的主力是持久性同源性（PH），一種從點云中提取拓撲特征的方法。給定一個點的數(shù)據(jù)集，PH 創(chuàng)建一個簡單復(fù)數(shù)的嵌套序列，其中每個復(fù)數(shù)對應(yīng)于分析基礎(chǔ)點云的某個比例。然后，它跟蹤各種拓撲特征（例如，連接的組件、循環(huán)或空洞） ，這些特征隨著比例的逐漸增加而出現(xiàn)和消失，并且人們從序列中的一個復(fù)合物過渡到下一個復(fù)合物。

在深度學(xué)習(xí)時代，持久性同源性有了“第二次生命”，因為它表明人們可以通過它進行反向傳播，從而允許將已經(jīng)建立的 TDA 設(shè)備集成到深度學(xué)習(xí)框架中。

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

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

由于計算是由這些空間的拓撲結(jié)構(gòu)（即鄰域結(jié)構(gòu)）驅(qū)動的，我們把這套方法稱為拓撲信息傳遞。在這個框架中，相鄰的單元，可能是不同維度的，正在交換信息，如下圖所示。

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

在 GNN 中超越圖?

盡管細胞復(fù)合體提供了豐富的結(jié)構(gòu)，但我們不能忽視圖是迄今為止機器學(xué)習(xí)中最常見的拓撲對象，而且很少有數(shù)據(jù)集能超越它們。盡管如此，人們?nèi)匀豢梢酝ㄟ^轉(zhuǎn)換輸入圖來利用這些有趣的拓撲空間。

我們把將圖轉(zhuǎn)換為高維拓撲空間稱為“提升”，以類似于范疇理論中的同名概念。它是一種轉(zhuǎn)換，通過遵循某些規(guī)則將高維單元附加到輸入圖上。例如，一個圖可以通過在圖的每個懸崖或周期上附加一個高維單元而被提升為一個單元復(fù)合體。通過這樣做，圖被替換成一個不同的空間，它有更多的結(jié)構(gòu)，可以為GNN提供一個比原始圖更好的計算結(jié)構(gòu)。在下文中，我們將討論這種方法的具體優(yōu)勢。

圖注：通過將二維封閉圓盤的邊界粘合到圖中的誘導(dǎo)循環(huán)上，可以從圖中構(gòu)造出高維的細胞復(fù)合體。

高階特征和結(jié)構(gòu)

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

高階交互

圖表根據(jù)定義是二元的（“成對的”），不能表示涉及兩個以上對象的關(guān)系和交互。在對以高階相互作用為特征的復(fù)雜系統(tǒng)進行建模時，這可能是一個問題：例如，化學(xué)反應(yīng)中的三種反應(yīng)物可能同時發(fā)生相互作用。在細胞復(fù)合體中，這種情況可以通過兩個細胞（即“填充”三角形）連接反應(yīng)物來編碼。因此，模型的計算流程適應(yīng)高階交互的存在。

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

表現(xiàn)力

信息傳遞 GNN 的表達能力受 Weisfeiler-Leman (WL) 圖同構(gòu)測試限制，眾所周知，WL 無法檢測某些圖子結(jié)構(gòu)，例如三角形或循環(huán)，即使是非常簡單的非同構(gòu)圖也無法區(qū)分。

據(jù)此前的論文顯示（論文地址：https://arxiv.org/abs/2103.03212；https://arxiv.org/abs/2106.12575），WL 測試 (CWL) 的細胞版本可用于測試細胞復(fù)合物的同構(gòu)性。當這個新測試與上面描述的圖提升過程相配時，可以發(fā)現(xiàn)，它能比 WL 測試區(qū)分更大的圖類。因此，在一定條件下，拓撲信息傳遞過程繼承了該測試的優(yōu)點，相比標準 GNN 提高了表達能力。

不足、過度平滑和瓶頸

信息傳遞的 GNN 需要n個層來使相距n個跳數(shù)的節(jié)點進行通信。當僅使用幾層，以至于相距較遠的節(jié)點無法交換信息時，這種現(xiàn)象稱為未達到。

相比之下，使用太多層可能會導(dǎo)致過度平滑，且信息可能會在圖的結(jié)構(gòu)瓶頸中丟失。

單元復(fù)合體可以緩解這些問題，因為由高維單元誘導(dǎo)的更豐富的鄰域結(jié)構(gòu)，在可能相距很遠的節(jié)點之間創(chuàng)建了捷徑。因此，信息只需包含一些計算步驟來傳播，就是有效的。

圖注：GNN 需要很多層才能使相距很遠的節(jié)點進行通信（左）。高維單元通過創(chuàng)建捷徑來改變空間的底層拓撲結(jié)構(gòu)（右）。這允許遠程節(jié)點在幾個信息傳遞步驟中交換信息。

分層建模

拓撲信息傳遞執(zhí)行的計算是分層的，信息從低維單元流向高維單元并返回，可看作是“垂直”（和可區(qū)分）池的一種形式，而非標準圖神經(jīng)網(wǎng)絡(luò)中的“水平”池。這保持了“壓縮”圖區(qū)域的歸納偏差，而不會忽略輸入圖的會損害基于 GNN 池性能的細粒度信息。

圖注：拓撲信息傳遞允許信息存在于不同維度的單元之間分層

域?qū)R

某些應(yīng)用自然與細胞復(fù)合物的結(jié)構(gòu)一致，例如，分子的原子、鍵和化學(xué)環(huán)可以表示為 0-cell、1-cell 和 2-cell，分子的物理結(jié)構(gòu)和細胞的復(fù)雜表示之間的直接對應(yīng)，允許了拓撲信息傳遞利用上述特性，這些表示也展示了拓撲信息傳遞在分子特性預(yù)測任務(wù)中所實現(xiàn)的最先進結(jié)果 。

其他表現(xiàn)良好對齊的應(yīng)用程序，可能包括計算機圖形應(yīng)用程序中的離散流形（網(wǎng)格）、社交網(wǎng)絡(luò)（派系特別重要）或空間圖，例如谷歌地圖（街道間的街區(qū)可被自然地表示為“立方”細胞） 。

圖注：咖啡因子被建模為二維細胞復(fù)合物

2 拓撲學(xué)和微分幾何學(xué)的結(jié)合

拓撲信息傳遞中，保留了許多與代數(shù)拓撲學(xué)、微分幾何學(xué)的有趣聯(lián)系，允許使用迄今為止仍在圖和幾何深度學(xué)習(xí)中沒有得到充分開發(fā)的數(shù)學(xué)工具。

洞代數(shù)和方向等值

在代數(shù)拓撲中，通常使用有向單純復(fù)形，其中每個單純形存在任意“定向”，例如，我們選擇每條邊中的一個源節(jié)點和一個目標節(jié)點，并對每個三角形選一個遍歷其節(jié)點的順序。一旦選定方向后，就可對復(fù)形執(zhí)行有趣的代數(shù)算子，例如通過“邊界算子”計算某些單純形的邊界。這些代數(shù)運算也可以用來在單純復(fù)形中找到“洞”——沒有邊界但不在其他事物邊界上的區(qū)域。其背后，持久同源依靠這些計算來檢測拓撲特征。

圖注：應(yīng)用于 2-單純形的邊界算子產(chǎn)生一個三角形。再次將算子應(yīng)用于三角形，結(jié)果為零，由于三角形是一個循環(huán)，因此它沒有邊界。

拓撲信息傳遞可以看作是代數(shù)算子（例如邊界算子）的（非線性）推廣。因此，拓撲信息傳遞表現(xiàn)類似是有必要的：我們希望各層的輸出能夠“一致”地響應(yīng)輸入復(fù)合物方向的變化。換句話說，我們希望我們的層是方向等值的。在工作中，我們研究了拓撲信息傳遞是如何通過選擇合適的非線性和信息傳遞函數(shù)來滿足這一特性，同時，純卷積設(shè)置中也對這一點進行了研究。

區(qū)分拓撲空間

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

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

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

離散霍奇理論

離散霍奇理論為細胞復(fù)合物的拓撲性質(zhì)提供了一個更幾何的解釋。當與k-細胞相關(guān)的特征符號取決于k-細胞的方向時，這些特征在數(shù)學(xué)上可被看作是微分幾何中的微分k-形的離散版本（即可以被整合的k維體積元素）。一個被稱為霍奇拉普拉斯的算子概括了圖形拉普拉斯，它可作用于這些微分形式?？梢宰C明，基于此拉普拉斯算子的擴散 PDE ，會在極限內(nèi)收斂與復(fù)合物的洞的有關(guān)信號 。

圖注：基于霍奇拉普拉斯算子的擴散偏微分方程，收斂于初始微分形式在拉普拉斯算子核上投影的極限。該圖像顯示了霍奇拉普拉斯算子的零特征向量是如何在復(fù)合體中的洞周圍取高值。

第一個簡單的神經(jīng)網(wǎng)絡(luò)模型實際上是基于霍奇拉普拉斯的卷積模型，反之，又受到拓撲信號處理的啟發(fā)。就在最近，基于該算子的一個版卷積模型被用于解決計算代數(shù)拓撲學(xué)中的NP-hard問題。

3 最后的思考

這些只是變相的圖表嗎？

最近有論文認為，除其他外，拓撲信息傳遞方法不過是在編碼細胞復(fù)合體結(jié)構(gòu)的修正圖上操作信息傳遞的 GNN 。這對卷積模型來說是正確的，其信息傳遞計算涉及到成對的單元格。

然而，在其最一般的形式中，信息函數(shù)允許高維單元格調(diào)制其邊界上的低維單元格之間傳遞的信息。一般情況下，能通過圖上的常規(guī)信息傳遞，因為一條邊正好連接兩個節(jié)點，而一個2-單元格可以任意連接多的邊。

在這兩種情況下，計算都是由數(shù)據(jù)所依附的底層空間的拓撲結(jié)構(gòu)所驅(qū)動的。我們相信，在信息傳遞上采用這種拓撲視角所帶來的好處，要超出純粹的計算考慮。除了有價值的數(shù)學(xué)聯(lián)系外，它還為其他數(shù)學(xué)和計算學(xué)科打開了研究話語，有利于我們經(jīng)常過于單調(diào)的社區(qū)之間的積極交叉融合。

拓撲信息傳遞的下一步是什么？

我們預(yù)計拓撲信息傳遞方法的兩個主要未來方向：

第一，多年來在GNN中開發(fā)的許多架構(gòu)（如注意力機制）可能會在這些新的拓撲空間中被采用，同時可利用它們的特定特征。

其次，來自代數(shù)拓撲領(lǐng)域的更多數(shù)學(xué)對象和工具（包括諸如蜂窩滑輪之類的結(jié)構(gòu)，即使是最精通數(shù)學(xué)的 ML 研究人員，對他們來說可能聽起來也很陌生）將被圖和幾何深度學(xué)習(xí)社區(qū)采用。

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