圖神經(jīng)網(wǎng)絡(luò)的困境，用微分幾何和代數(shù)拓?fù)浣鉀Q

選自towardsdatascience

作者：Michael Bronstein

機器之心編譯

編輯：Juniper

微分幾何和代數(shù)拓?fù)湓谥髁鳈C器學(xué)習(xí)中并不常見。在本系列文章中，作者展示了如何使用這些領(lǐng)域的工具重新解釋圖神經(jīng)網(wǎng)絡(luò)并解決一些常見困境。

本文的作者是 Twitter 首席科學(xué)家、DeepMind 人工智能教授 Michael Bronstein。以下是博客原文。

對稱，無論從廣義還是狹義的角度講，都是人類一直以來試圖理解和創(chuàng)造秩序與美的一種觀念。

——Hermann Weyl

Hermann Weyl 這種詩意的描述強調(diào)了對稱性在科學(xué)中的基石作用。Felix Klein 在 1872 年的「Erlangen Programme」中用對稱群表征幾何。這不僅是數(shù)學(xué)上的一個突破，即統(tǒng)一了「幾何大家庭」，還推進了現(xiàn)代物理理論的發(fā)展，這些理論可以完全從對稱性的第一原理推導(dǎo)出來。幾何深度學(xué)習(xí)領(lǐng)域也出現(xiàn)了類似的原則，通過群不變性和等變性能夠推導(dǎo)出大多數(shù)流行神經(jīng)網(wǎng)絡(luò)架構(gòu)的通用藍圖。

圖神經(jīng)網(wǎng)絡(luò)可以被認(rèn)為是幾何深度學(xué)習(xí)藍圖的一個特例，其構(gòu)建模塊是具有對稱群的域（在這種情況下是具有置換群的圖）、域上的信號（節(jié)點特征）和此類信號的群等變函數(shù)（消息傳遞）。

幾何深度學(xué)習(xí)藍圖可以應(yīng)用于不同的領(lǐng)域，例如 grid、mesh 或圖 (graph)。然而，前兩者具有明確的連續(xù)形式的類比對象，grid 可以被認(rèn)為是歐幾里得空間或更一般的均勻空間（如球體）的離散化，mesh 則是二維流形的常見離散化），圖卻沒有直接的連續(xù)形式的類比。這種不可類比有點令人不安，因此我們決定仔細研究用于圖學(xué)習(xí)的連續(xù)模型。

圖神經(jīng)網(wǎng)絡(luò)擴散。圖神經(jīng)網(wǎng)絡(luò) (GNN) 通過在圖上執(zhí)行某種形式的消息傳遞來學(xué)習(xí)。其中，特征通過邊從一個節(jié)點傳遞到另一個節(jié)點。這種機制與圖上的擴散過程有關(guān)，可以用稱為「擴散方程」的偏微分方程 (PDE) 形式表示。我們最近在一篇論文中展示了這種具有非線性可學(xué)習(xí)擴散函數(shù)的 PDE 的離散化（稱為 GRAND），泛化了一大類 GNN 架構(gòu)，例如圖注意力網(wǎng)絡(luò)（GAT。

PDE 的思維方式提供了多種優(yōu)勢，例如可以利用兼具穩(wěn)定性和收斂性的高效數(shù)值求解器（例如隱式、多步、自適應(yīng)和 multigrid 方案）。其中一些求解器在流行的 GNN 架構(gòu)中沒有直接的類比，可能會促成一些新型圖神經(jīng)網(wǎng)絡(luò)設(shè)計。由于我們考慮的擴散 PDE 可以看作是一些相關(guān)能量的梯度流 ，因此這種架構(gòu)可能比典型架構(gòu)更易于解釋。

同時，雖然 GRAND 模型提供連續(xù)時間來代替?zhèn)鹘y(tǒng) GNN 中的層，但方程的空間部分仍然是離散的，并且依賴于輸入圖。重要的是，在這個擴散模型中，域（圖）是固定的，其上定義的某些屬性會演化。

微分幾何中常用的一個不同概念是幾何流（geometric flow），域本身的屬性不斷演化。我的博士生導(dǎo)師 Ron Kimmel 等研究者 20 世紀(jì) 90 年代在圖像處理領(lǐng)域就采用了這個想法。他們將圖像建模為嵌入在聯(lián)合位置和顏色空間中的流形，并通過 PDE 對它們進行推導(dǎo)演化，以最小化嵌入的諧波能量。這樣的偏微分方程稱為貝爾特拉米流（Beltrami flow），具有各向同性非歐幾里得擴散的形式，并產(chǎn)生保邊圖像去噪。

我們將這種范式應(yīng)用于「Beltrami 神經(jīng)擴散（BLEND）」框架中的圖。圖的節(jié)點現(xiàn)在由位置坐標(biāo)和特征坐標(biāo)來表征，這兩個坐標(biāo)都是經(jīng)過演化的，并且都決定了擴散性。在這種思維模式下，圖本身就變成了一個輔助角色：它可以從位置坐標(biāo)生成（例如作為 k - 最近鄰圖）并在整個演化過程中重新連接。下圖說明了這種同時演化的過程。

圖的表達能力

在最近的工作中，人們對圖神經(jīng)網(wǎng)絡(luò)（GNN）的表達能力給予了極大的關(guān)注。消息傳遞的 GNN 等價于 Weisfeiler-Lehman 圖同構(gòu)測試（一種通過迭代顏色細化來確定兩個圖是否在結(jié)構(gòu)上等價 (同構(gòu)) 的經(jīng)典方法）。這個檢驗是一個必要但不充分條件：事實上，一些非同構(gòu)圖可能會通過 Weisfeler-Lehman 測試。下圖說明了 GNN 傳遞消息過程中該測試「看到」了什么：兩個高亮顯示的節(jié)點看起來沒有什么區(qū)別，然而這兩個圖顯然具有不同的結(jié)構(gòu)：

位置編碼。解決這個問題的一個常見方法是通過為節(jié)點分配一些額外的特征來給節(jié)點「著色」，這些特征保證了圖中節(jié)點的角色或「位置」。由于位置編碼在 Transformer 中已得到普及，因此位置編碼成為增加圖神經(jīng)網(wǎng)絡(luò)表達能力的常用方法。

位置編碼為圖的節(jié)點分配了額外的特征，允許消息傳遞獲得比 Weisfeiler-Lehman 測試更高的表達能力。然而，對于位置編碼，并沒有一個「規(guī)范」的選擇。

也許最直接的方法是賦予每個節(jié)點一個隨機特征；然而，這種方法雖然可以更具表達性，但泛化能力較差（因為不可能在兩個圖中重現(xiàn)隨機特征）。圖拉普拉斯算子的特征向量提供了圖的領(lǐng)域保持嵌入，并已成功用作位置編碼。最后，我們（與 Giorgos Bouritsas 和 Fabrizio Frasca 合著）在一篇論文中表明，圖的子結(jié)構(gòu)計數(shù)可以用作位置或「結(jié)構(gòu)」編碼的一種形式，這說明它比基本的 Weisfeiler-Lehman 測試更強大。

然而，位置編碼有多種選擇，如何選擇以及哪種方法在哪種情況下效果更好，都沒有明確的答案。我相信像 BLEND 這樣的幾何流可以根據(jù)這個問題來解釋：通過非歐幾里得擴散來演化圖的位置坐標(biāo)，位置編碼可以適用于下游任務(wù)。因此，答案是「視情況而定」：最佳位置編碼是手頭數(shù)據(jù)和任務(wù)的函數(shù)。

高階消息傳遞。表達性的另一種選擇是放棄根據(jù)節(jié)點和邊來考慮圖，而是把圖看作單元復(fù)合體（cell complex）對象的示例，單元復(fù)合體是代數(shù)拓?fù)漕I(lǐng)域的主要研究對象之一。在這種方法中，節(jié)點是 0-cell，邊是 1-cell。不必止步于此：我們可以構(gòu)造如下圖所示的 2-cells（面），這使得上述示例中的兩個圖可以完美區(qū)分：

在我最近與 Cristian Bodnar 和 Fabrizio Frasca 合作的兩篇論文中，我們表明可以構(gòu)建一個「提升變換」，用高階單元來增強圖，從而在這些單元上可以執(zhí)行更復(fù)雜的分層消息傳遞形式。該方案可被證明比 Weisfeiler-Lehman 測試的表達能力更強，并且在計算化學(xué)領(lǐng)域給出了有望的結(jié)果：比建模為圖，建模為單元復(fù)合體表現(xiàn)更好。

「over-squashing」現(xiàn)象

GNN 的另一個常見問題是「over-squashing」現(xiàn)象，或者由于輸入圖的某些結(jié)構(gòu)特征，消息傳遞無法有效地傳播信息。oversquashing 通常發(fā)生在體積呈指數(shù)增長的圖中，例如小世界網(wǎng)絡(luò)以及依賴于遠程信息的問題。換句話說，GNN 作用的輸入圖并不總是對消息傳遞友好。

「小世界」圖中快速增長的鄰居數(shù)量通常是 GNN 中觀察到的過度擠壓現(xiàn)象的根源。

從實驗可以觀察到，將輸入圖與計算圖解耦并允許在不同的圖上傳遞消息有助于緩解這一問題。這種技術(shù)通常被稱為「圖重新布線（graph rewiring）」。

事實上，許多流行的 GNN 架構(gòu)都實現(xiàn)了某種形式的圖重構(gòu)，可以采用鄰域采樣（最初在 GraphSAGE 中提出以應(yīng)對可擴展性）或多跳濾波器的形式。上面討論的拓?fù)湎鬟f也可以看作是重新布線的一種形式，遠距離節(jié)點之間的信息流可以認(rèn)為是通過高階單元的「捷徑」。Alon 和 Yahav [23] 表明，即使像使用全連接圖這樣簡單的方法也可能有助于改善圖 ML 問題中的 over-squashing。

Klicpera 等研究者宣稱「擴散改進了圖學(xué)習(xí)」，提出了一個通用的 GNN 預(yù)處理步驟（DIGL），包括通過擴散過程來去噪圖的連通性。總體而言，盡管進行了重要的實驗研究，但 over-squashing 現(xiàn)象一直令人難以捉摸。我們最近在一篇論文中表明：導(dǎo)致 over-squashing 的瓶頸可歸因于圖的局部幾何特性。具體來說，通過定義 Ricci 曲率的圖類比，我們可以證明罪魁禍?zhǔn)资?negatively-curved 邊。因此出現(xiàn)了一種類似于「反向 Ricci 流」的圖重新布線過程，該過程去除有問題的邊并生成一個更易于消息傳遞的圖，同時在結(jié)構(gòu)上與輸入圖相似。

使用基于擴散的方法（DIGL，中）和基于曲率的方法（Ricci，右）重新連接康奈爾圖（左）的示例?；谇实姆椒@著減少了瓶頸，同時更接近于原始圖結(jié)構(gòu)。

總結(jié)

這些例子表明，微分幾何和代數(shù)拓?fù)錇閳D機器學(xué)習(xí)中重要且具有挑戰(zhàn)性的問題帶來了新的視角。在本系列的后續(xù)文章中，我將更詳細地展示如何使用這些領(lǐng)域的工具來解決上述圖神經(jīng)網(wǎng)絡(luò)問題。第二部分將討論代數(shù)拓?fù)淙绾翁岣?GNN 的表達能力。第三部分將講解幾何擴散偏微分方程。第四部分將展示 over-squashing 現(xiàn)象與圖曲率有何相關(guān)，并提供一種受 Ricci 流啟發(fā)的圖重新布線的新型幾何方法。

關(guān)鍵詞： 圖神經(jīng)網(wǎng)絡(luò)的困境 用微分幾何和代數(shù)拓?fù)浣鉀Q