影音先锋激情网站,色色网站在线观看观看,日韩无码成人一区黄色电影,男女日日夜夜,国产高清成人a片,2019中文字幕在线视频,免费又黄又爽又色的视频,人人摸人人操人人摸

來源：AI科技評論
本文約8500字，建議閱讀15+分鐘
本文叫你如何突破基于 WL 測試和消息傳遞機(jī)制的 GNN 的性能瓶頸。

圖可以方便地抽象關(guān)系和交互的復(fù)雜系統(tǒng)。社交網(wǎng)絡(luò)、高能物理、化學(xué)等研究領(lǐng)域都涉及相互作用的對象（無論是人、粒子還是原子）。在這些場景下，圖結(jié)構(gòu)數(shù)據(jù)的重要性日漸凸顯，相關(guān)方法取得了一系列初步成功，而一系列工業(yè)應(yīng)用使得圖深度學(xué)習(xí)成為機(jī)器學(xué)習(xí)方向的熱門研究話題之一。

圖注：通過圖對復(fù)雜系統(tǒng)的關(guān)系、交互進(jìn)行抽象。例如，「分子圖」中構(gòu)成分子的原子至今的化學(xué)鍵，「社交網(wǎng)絡(luò)」中用戶之間的關(guān)系和交互，「推薦系統(tǒng)」中用戶和商品之間的聯(lián)系。

受物理啟發(fā)的圖上的持續(xù)學(xué)習(xí)模型可以克服傳統(tǒng) GNN 的局限性。多年來，消息傳遞一直是圖深度學(xué)習(xí)領(lǐng)域的主流范式，使圖神經(jīng)網(wǎng)絡(luò)（GNN）在粒子物理到蛋白質(zhì)設(shè)計(jì)的廣泛應(yīng)用中取得了巨大成功。

從理論角度來看，它建立了與 Weisfeiler-Lehman（WL）層次結(jié)構(gòu)的聯(lián)系，我們可以以此分析 GNN 的表達(dá)能力。但是在 Michael Brostein 看來，當(dāng)前圖深度學(xué)習(xí)方案「以節(jié)點(diǎn)和邊為中心」的思維方式帶來了無法克服的局限性，阻礙了該領(lǐng)域未來的發(fā)展。

另一方面，在關(guān)于幾何深度學(xué)習(xí)的最新綜述中，Brostein 提出了受物理啟發(fā)的持續(xù)學(xué)習(xí)模型，從微分幾何、代數(shù)拓?fù)浜臀⒎址匠痰阮I(lǐng)域出發(fā)開啟了一系列新工具的研究。到目前為止，圖機(jī)器學(xué)習(xí)領(lǐng)域中還鮮有此類研究。

針對Bronstein的最新思考，我們做了不改原意的整理與編譯：

1、圖神經(jīng)網(wǎng)絡(luò)的工作原理

GNN 的輸入為具有節(jié)點(diǎn)和邊特征的圖，計(jì)算一個(gè)既依賴于特征又依賴于圖結(jié)構(gòu)的函數(shù)。消息傳遞類的 GNN（即 MPNN）通過交換相鄰節(jié)點(diǎn)之間的信息在圖上傳播特征。典型的 MPNN 架構(gòu)由幾個(gè)傳播層組成，基于鄰居特征的聚合函數(shù)對每個(gè)節(jié)點(diǎn)進(jìn)行更新。根據(jù)聚合函數(shù)的不同，我們可以將 MPNN分為：卷積（鄰居特征的線性組合，權(quán)值僅依賴于圖的結(jié)構(gòu)）、注意力（線性組合，權(quán)值依賴于圖結(jié)構(gòu)和特征）和消息傳遞（廣義的非線性函數(shù)）。消息傳遞 GNN 是最常見的，而前者可以視為消息傳遞 GNN 的特殊情況。

圖注：GNN 的三種風(fēng)格——卷積、注意力和廣義非線性信息傳遞風(fēng)格，它們都是消息傳遞的表現(xiàn)形式。

傳播層由基于下游任務(wù)學(xué)習(xí)的參數(shù)構(gòu)成，典型的用例包括：節(jié)點(diǎn)嵌入（每個(gè)節(jié)點(diǎn)表示為向量空間中的一個(gè)點(diǎn)，通過點(diǎn)之間的距離恢復(fù)出原始圖的連通性，此類任務(wù)被稱為「鏈接預(yù)測」），節(jié)點(diǎn)級的分類或回歸（如推斷社交網(wǎng)絡(luò)用戶的屬性），或者通過進(jìn)一步聚合節(jié)點(diǎn)的特征進(jìn)行圖級別的預(yù)測（例如，預(yù)測分子圖的化學(xué)性質(zhì)）。

2、消息傳遞 GNN 的不足之處

GNN 在多個(gè)方面都取得了令人印象深刻的成功，最近的相關(guān)研究也具有相當(dāng)?shù)膹V度和深度。但是，當(dāng)下的圖深度學(xué)習(xí)范式的主流模型是：對于構(gòu)建好的圖，通過消息傳遞的方式沿著圖的邊傳播節(jié)點(diǎn)信息。Michael Brostein 認(rèn)為，正是這種以節(jié)點(diǎn)和邊為中心的思維方式，為該領(lǐng)域進(jìn)一步發(fā)展帶來了主要的障礙。

WL 的類比能力有限。適當(dāng)選擇像「求和」這樣的局部聚合函數(shù)，可以使消息傳遞等價(jià)于 WL 圖同構(gòu)測試，使圖神經(jīng)網(wǎng)絡(luò)能夠根據(jù)信息在圖上的傳播方式發(fā)現(xiàn)某些圖結(jié)構(gòu)。通過這種與圖論的重要聯(lián)系，研究人員提出了多種分析 GNN 表達(dá)能力的理論結(jié)果，決定了圖上的某些函數(shù)是否可以通過消息傳遞來計(jì)算。然而，這種類型的分析結(jié)果通常不能說明表征的效率（即需要多少層來計(jì)算某個(gè)函數(shù)），也不能說明 GNN 的泛化能力。

圖注：WL 測試就好比在沒有地圖的情況下走進(jìn)迷宮，并試圖理解迷宮的結(jié)構(gòu)。位置編碼提供了迷宮的地圖，而重連則提供了一個(gè)越過「墻壁」的梯子。

即使是對于三角形這種簡單的圖結(jié)構(gòu)，有時(shí) WL 算法也無法將它們檢測出來，這讓試圖將信息傳遞神經(jīng)網(wǎng)絡(luò)用于分子圖的從業(yè)者非常失望。例如，在有機(jī)化學(xué)中，像環(huán)這樣的結(jié)構(gòu)非常普遍，并且對分子的性質(zhì)十分重要（例如，萘等芳香環(huán)之所以被稱為芳香環(huán)，是因?yàn)樗鼈冎饕嬖谟诰哂袕?qiáng)烈氣味的化合物中）。

圖注：十氫化萘（左）和二環(huán)戊基（右）有不同的結(jié)構(gòu)，但我們無法通過 WL 測試區(qū)分它們。

近年來，研究者們已經(jīng)提出了一些構(gòu)建表達(dá)能力更強(qiáng)的 GNN 模型的方法。例如，WL 層次結(jié)構(gòu)中的高維同構(gòu)測試（以更高的計(jì)算和內(nèi)存復(fù)雜度以及缺乏局域性為代價(jià)），將 WL 測試應(yīng)用于子圖集合；位置或結(jié)構(gòu)編碼，為圖中的節(jié)點(diǎn)著色，以這種方式幫助打破迷惑 WL 算法的規(guī)律。位置編碼目前在 Transformer 模型中是最常見的技術(shù)，在 GNN 中也廣為使用。雖然存在多種位置編碼方法，但具體的選擇還取決于目標(biāo)應(yīng)用，要求使用者有一定經(jīng)驗(yàn)。

圖注：位置編碼示例：隨機(jī)特征、拉普拉斯特征向量（類似于 Transformer 中的正弦曲線）、結(jié)構(gòu)特征（三角形和矩形的個(gè)數(shù)）。

「圖重連」突破了 GNN 的理論基礎(chǔ)。GNN 和卷積神經(jīng)網(wǎng)絡(luò)（CNN）之間的一個(gè)重要且微妙的區(qū)別是：圖既是輸入的一部分，也是計(jì)算結(jié)構(gòu)的一部分。傳統(tǒng)的 GNN 使用輸入的圖結(jié)構(gòu)來傳播信息，通過這種方式獲得既反映圖結(jié)構(gòu)又反映圖上特征的表示。然而，由于某些結(jié)構(gòu)特征（「瓶頸」），一些圖在信息傳播方面的性能較差，導(dǎo)致來自太多節(jié)點(diǎn)的信息被壓縮到一個(gè)節(jié)點(diǎn)彪悍尊能中，即「過壓縮」。

現(xiàn)代 GNN 實(shí)現(xiàn)通過將輸入圖與計(jì)算圖解耦（或?yàn)橛?jì)算目的優(yōu)化輸入圖）來處理這種現(xiàn)象，這種技術(shù)稱為「圖重連」。重連可以采取以下形式：鄰域采樣、虛擬節(jié)點(diǎn)、連通性擴(kuò)散或演化，或節(jié)點(diǎn)和邊的 Dropout 機(jī)制。Transformer 和像 GAT 這類基于注意力的 GNN 通過為每條邊分配不同的權(quán)重來有效地學(xué)習(xí)新的圖，這也可以理解為一種「軟性」的重接。最后，潛圖學(xué)習(xí)方法也可以歸入這一類，它可以構(gòu)建針對特定任務(wù)的圖，并在每一層中更新它（初始狀態(tài)下有位置編碼、初始圖，或有時(shí)根本沒有圖）。很少有現(xiàn)代 GNN 模型在原始輸入圖上傳播信息。

圖注：GNN 中使用的各種圖重連技術(shù)——原始圖、鄰域采樣（例如，GraphSAGE）、注意力機(jī)制（例如，GAT）、連通性演化（例如，DIGL）。

WL 測試根據(jù)信息在圖上的傳播方式來描述圖。重連突破了這種理論上的聯(lián)系，但又讓我們陷入機(jī)器學(xué)習(xí)領(lǐng)域常見的問題中：學(xué)術(shù)界從理論上分析的模型與實(shí)踐中使用的模型并不相同。

有時(shí)，圖的「幾何特性」不足。GNN 是幾何深度學(xué)習(xí)宏偉藍(lán)圖中的一個(gè)實(shí)例。幾何深度學(xué)習(xí)是一個(gè)「群論框架」，使我們可以根據(jù)數(shù)據(jù)底層的域的對稱性設(shè)計(jì)深度學(xué)習(xí)架構(gòu)。由于圖沒有規(guī)范的節(jié)點(diǎn)順序，在圖的場景下，這種對稱性指的是節(jié)點(diǎn)排列。由于這種結(jié)構(gòu)特性，局部作用圖上的 MPNN 必須依賴于滿足排列不變性的特征聚合函數(shù)，這意味著圖上沒有「方向」的概念，信息的傳播是各向同性的。這種情況與在連續(xù)域、網(wǎng)格上的學(xué)習(xí)有著顯著的不同，并且是 GNN 的缺點(diǎn)之一，人們認(rèn)為各向同性濾波器的作用有限。

圖注：網(wǎng)格是具有局部歐氏結(jié)構(gòu)的離散流形。我們根據(jù)旋轉(zhuǎn)來定義鄰居節(jié)點(diǎn)，從而形成了「方向」的概念。圖的結(jié)構(gòu)較少，它根據(jù)排列來定義鄰居節(jié)點(diǎn)。

有時(shí)，圖的「幾何特性」又過多。距離與方向的差異在某種程度上也與構(gòu)建節(jié)點(diǎn)嵌入時(shí)遇到的問題有關(guān)。在某些空間中節(jié)點(diǎn)表征之間的距離被用來捕獲圖的聯(lián)通性。我們大致可以將嵌入空間中接近的節(jié)點(diǎn)通過圖中的一條邊連接起來。在推薦系統(tǒng)中，圖嵌入被用來在節(jié)點(diǎn)所代表的實(shí)體之間創(chuàng)建關(guān)聯(lián)（邊）。

圖嵌入的質(zhì)量及其表達(dá)圖結(jié)構(gòu)的能力，在很大程度上取決于嵌入空間的幾何性質(zhì)及其與圖的幾何性質(zhì)的兼容性。歐氏空間在表示學(xué)習(xí)中有重要的地位，也是目前最簡單、最方便的表征空間，但對于許多自然中的圖來說，歐氏空間并不理想，原因之一是：歐幾里德度規(guī)球的體積隨半徑以多項(xiàng)式形式增長，而隨維數(shù)指數(shù)增長，而現(xiàn)實(shí)世界中許多圖的體積增長是指數(shù)的。因此，嵌入變得「過于擁擠」，我們被迫使用高維空間，從而導(dǎo)致較高的計(jì)算復(fù)雜度和空間復(fù)雜度。

最近流行的一種替代方法是使用負(fù)曲率（雙曲）空間，它具有與圖更兼容的指數(shù)體積增長。雙曲幾何的使用通常會(huì)使嵌入維數(shù)更低，使節(jié)點(diǎn)表示更加緊湊。然而，圖往往是異質(zhì)的（例如，有些部分看起來像樹，其它部分看起來像團(tuán)，具有非常不同的體積增長特性），而雙曲嵌入空間是同質(zhì)的（每個(gè)點(diǎn)都有相同的幾何性質(zhì)）。

此外，即使嵌入空間具有非歐幾何性質(zhì)，但通常不可能在該空間中準(zhǔn)確地表示通用的圖的度量結(jié)構(gòu)。因此，圖的嵌入不可避免地是近似的。然而，更糟糕的是，由于嵌入是在考慮鏈接預(yù)測標(biāo)準(zhǔn)的情況下構(gòu)建的，高階結(jié)構(gòu)（三角形、矩形等）的畸變可能會(huì)大到無法控制的。在社會(huì)和生物網(wǎng)絡(luò)等應(yīng)用場景下，這樣的結(jié)構(gòu)扮演著重要的角色，因?yàn)樗鼈兛梢圆东@更復(fù)雜的非成對的相互作用和模體。

圖注：圖的模體是一種高階的結(jié)構(gòu)。在對許多生物現(xiàn)象建模的圖中可以觀察到這種結(jié)構(gòu)。

當(dāng)數(shù)據(jù)的結(jié)構(gòu)與底層圖的結(jié)構(gòu)不兼容時(shí)，GNN 的性能就會(huì)受到挑戰(zhàn)。許多圖學(xué)習(xí)數(shù)據(jù)集和對比基準(zhǔn)都默認(rèn)假設(shè)數(shù)據(jù)是同質(zhì)性的（即相鄰節(jié)點(diǎn)的特征或標(biāo)簽是相似的，或者說是平滑的）。在這種情況下，即使是對圖進(jìn)行簡單的低通濾波（例如，取鄰接平均值）也能起到很好的效果。早期的對比基準(zhǔn)測試（例如，Cora），都是在具有高度同質(zhì)性的圖上進(jìn)行的，這使得 GNN 的評估過于容易。

圖注：同構(gòu)和異構(gòu)數(shù)據(jù)集。在同構(gòu)圖中，節(jié)點(diǎn)特征或標(biāo)簽的結(jié)構(gòu)與圖是兼容的（即節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)相似）。

然而，在處理親異（heterophilic）數(shù)據(jù)時(shí)，許多模型顯示出令人失望的結(jié)果，在這種情況下，必須使用更精細(xì)的聚合方式。我們不妨考慮兩種典型的情況：（1）模型完全避免使用鄰居信息（GNN 退化為節(jié)點(diǎn)級的多層感知機(jī)）（2）出現(xiàn)「過平滑」現(xiàn)象，即節(jié)點(diǎn)的表征在經(jīng)過 GNN 的各層后變得更加平滑，最終「坍塌」為一個(gè)點(diǎn)。親同數(shù)據(jù)集中也存在「過平滑」現(xiàn)象，對于某些 MPNN 來說是一個(gè)更為本質(zhì)的缺陷，使深度圖學(xué)習(xí)模型難以實(shí)現(xiàn)。

我們通常很難理解 GNN 學(xué)到了什么，GNN 往往是難以解釋的黑盒模型。雖然可解釋性的定義在很大程度上還較為模糊，但在大多數(shù)情況下，我們確實(shí)并不真正理解 GNN 學(xué)習(xí)了什么。最近的一些工作試圖通過以緊湊的子圖結(jié)構(gòu)和在 GNN 預(yù)測中起關(guān)鍵作用的節(jié)點(diǎn)特征子集的形式來解釋基于 GNN 的模型，從而緩解可解釋性的缺陷。通過潛圖學(xué)習(xí)架構(gòu)學(xué)習(xí)的圖也可以看作提供「解釋」的一種形式。

約束通用的消息傳遞函數(shù)有助于排除不合理的輸出，確保 GNN 學(xué)到的東西有意義，并且在特定領(lǐng)域的應(yīng)用程序中可以更好地理解 GNN。具體而言，這樣做可以為消息傳遞賦予額外的「內(nèi)部」數(shù)據(jù)對稱性，從而更好地理解底層的問題。例如，E(3)-等變消息傳遞能夠正確地處理分子圖中的原子坐標(biāo)，最近對 AlphaFold 和 RosettaFold 等蛋白質(zhì)結(jié)構(gòu)預(yù)測架構(gòu)的成功作出了貢獻(xiàn)。

在 Miles Cranmer 和 Kyle Cranmer 合著的論文“Discovering symbolic models from deep learning with inductive biases”中，作者用符號公式取代了多體動(dòng)力系統(tǒng)上學(xué)習(xí)的消息傳遞函數(shù)，從而可以「學(xué)習(xí)物理方程」。還有的研究者試圖將 GNN 與因果推理聯(lián)系起來，試圖構(gòu)建一個(gè)圖來解釋不同變量之間的因果關(guān)系?？偟膩碚f，這仍然是一個(gè)處于起步階段的研究方向。

圖注：不同的「可解釋」GNN 模型——圖解釋器、潛圖學(xué)習(xí)、等變消息傳遞。

大多數(shù) GNN 的實(shí)現(xiàn)是與硬件無關(guān)的。目前大多數(shù) GNN 依賴于 GPU 實(shí)現(xiàn)，并默認(rèn)數(shù)據(jù)可以裝入內(nèi)存。然而，在處理大規(guī)模圖（如生物網(wǎng)絡(luò)和社交網(wǎng)絡(luò)）時(shí)，這往往是一種一廂情愿的想法。在這種情況下，理解底層硬件的局限性（如不同的帶寬和內(nèi)存層次結(jié)構(gòu)的延遲），并方便地使用硬件是至關(guān)重要的。大體來說，在相同物理內(nèi)存中的兩個(gè)節(jié)點(diǎn)和不同芯片上的兩個(gè)節(jié)點(diǎn)之間，消息傳遞的成本可能存在一個(gè)數(shù)量級的差異?！甘?GNN 對現(xiàn)有硬件友好」是一個(gè)重要而又經(jīng)常被忽視的問題?？紤]到設(shè)計(jì)新芯片所需的時(shí)間和精力，以及機(jī)器學(xué)習(xí)的發(fā)展速度，開發(fā)以圖為中心的新型硬件是一個(gè)更大的挑戰(zhàn)。

3、圖學(xué)習(xí)新藍(lán)圖——「持續(xù)」模型

「持續(xù)」學(xué)習(xí)模型是一個(gè)取代離散 GNN 的新興的、希望的方案?！甘艿轿锢硐到y(tǒng)啟發(fā)的持續(xù)學(xué)習(xí)」從微分幾何、代數(shù)拓?fù)浜臀⒎址匠痰阮I(lǐng)域出發(fā)開辟了一系列新的工具，迄今為止在圖機(jī)器學(xué)習(xí)中還尚未被探索。

將 GNN 重新想象為連續(xù)的物理過程。與在圖上傳遞多層消息不同，我們可以考慮在連續(xù)的時(shí)間維度上發(fā)生在某個(gè)域（可以是流形等連續(xù)的域，并將其轉(zhuǎn)化為離散圖）上的物理過程。該過程在空間和時(shí)間上的某個(gè)點(diǎn)的狀態(tài)取代了一層 GNN 生成的圖中某個(gè)節(jié)點(diǎn)的潛在特征。該過程由一組參數(shù)（表示底層物理系統(tǒng)的屬性）控制，這些參數(shù)取代了消息傳遞層的可學(xué)習(xí)權(quán)值。

我們可以根據(jù)經(jīng)典系統(tǒng)和量子系統(tǒng)構(gòu)造出大量不同的物理過程。研究者們在一系列論文中證明，許多現(xiàn)有的 GNN 可能與擴(kuò)散過程有關(guān)，這可能最自然的傳播信息方式。也可能存在一些更奇特的方式（如耦合振蕩系統(tǒng)），它們可能具備某些優(yōu)勢。

圖注：圖耦合振蕩系統(tǒng)的動(dòng)力學(xué)。

連續(xù)系統(tǒng)在時(shí)間和空間上可以是離散的。空間離散化指的是：以圖的形式在連續(xù)域上連接附近的點(diǎn)，它可以隨時(shí)間和空間變化。這種學(xué)習(xí)范式與傳統(tǒng)的 WL 測試截然不同，后者嚴(yán)格地受底層輸入圖假設(shè)的約束。更重要的是，空間離散化思想啟發(fā)了一系列新的工具的誕生。至少從原則上說，它讓我們可以解決一些重要的問題，這些問題是現(xiàn)有的圖論技術(shù)所無法解決的。

圖注：2D 拉普拉斯算子的不同離散化結(jié)果。

學(xué)習(xí)是一個(gè)最優(yōu)控制問題。在給定的時(shí)間內(nèi)，過程的所有可能狀態(tài)的空間可以被看作是一個(gè)可以表示的函數(shù)的「假設(shè)類」。這種學(xué)習(xí)方式可以看作一個(gè)最優(yōu)控制問題，即是否可以控制過程（通過在參數(shù)空間中選擇一條軌跡）使其達(dá)到某種理想狀態(tài)。我們可以將表示能力定義為：是否可以通過在參數(shù)空間中選擇適當(dāng)?shù)能壽E來控制過程，從而實(shí)現(xiàn)某種給定的功能（可達(dá)性）；效率與達(dá)到某一狀態(tài)所需的時(shí)間有關(guān)；而泛化性則與該過程的穩(wěn)定性有關(guān)。

圖注：將學(xué)習(xí)作為控制問題。通過飛機(jī)來比喻物理系統(tǒng)，其 xyz 坐標(biāo)（系統(tǒng)狀態(tài)）是通過操縱推理、副翼、和方向舵（參數(shù)空間）來控制的。

可以由離散微分方程推導(dǎo)出 GNN。物理系統(tǒng)的行為通常可由微分方程控制，其解產(chǎn)生系統(tǒng)的狀態(tài)。在某些情況下，這樣的解可以是閉式解。但在更普遍的情況下，必須依靠基于適當(dāng)離散化的數(shù)值解。經(jīng)過一個(gè)多世紀(jì)的研究，數(shù)值分析領(lǐng)域出現(xiàn)了各種各樣的迭代求解器，為圖上的深度學(xué)習(xí)提供了可能的全新架構(gòu)。

GNN 中的注意力機(jī)制可以解釋為具有可學(xué)習(xí)擴(kuò)散系數(shù)的離散擴(kuò)散偏微分方程，使用顯式數(shù)值方法求解。此時(shí)，求解器的每一步迭代對應(yīng)于 GNN 的一個(gè)層。目前還沒有 GNN 架構(gòu)能夠直接類比于更復(fù)雜的求解器（例如，使用自適應(yīng)步長或多步方案），該方向的研究可能催生出新的架構(gòu)。另一方面，隱式的方案則需要在每次迭代時(shí)求解一個(gè)線性系統(tǒng)，可以將其解釋為「多跳」濾波器。此外，數(shù)值方法具有穩(wěn)定性和收斂性的保證，為它們能夠工作提供了條件，也為失效情況提供了解釋。

數(shù)值求解器應(yīng)該對硬件友好。迭代求解器比數(shù)字計(jì)算機(jī)更古老，從數(shù)字計(jì)算機(jī)誕生之日起，它就必須知道自己擁有底層硬件，并有效地利用它們。科學(xué)計(jì)算中的大規(guī)模問題通常必須在計(jì)算機(jī)集群上解決，而這些問題是至關(guān)重要的。

在圖上進(jìn)行「持續(xù)」深度學(xué)習(xí)的方式，使我們以與模擬它們的硬件兼容的方式對底層微分方程進(jìn)行離散化。這里可能用到超級計(jì)算研究社區(qū)的大量成果（如域分解技術(shù)）。具體而言，圖重連和自適應(yīng)迭代求解器考慮了內(nèi)存的層次結(jié)構(gòu)，例如：在不同物理位置的節(jié)點(diǎn)上執(zhí)行很少的信息傳遞步驟，而在相同物理內(nèi)存中的節(jié)點(diǎn)上執(zhí)行更頻繁的步驟。

將演化方程解釋為與物理系統(tǒng)相關(guān)的能量函數(shù)的梯度流，有助于理解學(xué)習(xí)模型。許多物理系統(tǒng)都有一個(gè)相關(guān)的能量泛函（有時(shí)也包含某些對稱或守恒定律），其中控制系統(tǒng)動(dòng)力學(xué)的微分方程是一個(gè)最小化的梯度流。例如，擴(kuò)散方程使狄利克雷能量最小化，而它的非歐版本（Beltrami 流）使 Polyakov 泛函最小化，從而直觀地理解了學(xué)習(xí)模型。利用最小作用原理，某些能量泛函可以導(dǎo)出雙曲方程（如波動(dòng)方程）。這些方程的解是波動(dòng)的（振蕩的），與典型的 GNN 動(dòng)力學(xué)有很大的不同。

分析這種流的極限情況提供了對模型表現(xiàn)的深刻理解，而這是很難通過其它方法獲得的。例如，在論文“Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs”中，Michael 等人證明了傳統(tǒng)的 GNN 必然會(huì)導(dǎo)致過平滑，并且只有在同質(zhì)性假設(shè)下才具有分離的能力；在使用圖上的額外結(jié)構(gòu)可以獲得更好的分離能力。在論文“Graph-Coupled Oscillator Networks”中，Michael 等人證明了振動(dòng)系統(tǒng)在極限下可避免過平滑。這些結(jié)果可以解釋為什么在某些 GNN 架構(gòu)中會(huì)產(chǎn)生某些不良現(xiàn)象，以及如何設(shè)計(jì)架構(gòu)來避免它們。此外，將流的極限情況與分離聯(lián)系起來，揭示了模型表達(dá)能力的界限。

可以在圖中使用更豐富的結(jié)構(gòu)。如前文所述，有時(shí)圖的幾何性質(zhì)可能「不足」（無法捕獲更復(fù)雜的現(xiàn)象，如非成對關(guān)系），也可能「過剩」（即難以在同質(zhì)空間中表示）。我們可以通過使用額外的結(jié)構(gòu)使圖更豐富，從而處理圖幾何性質(zhì)不足的問題。例如，分子包含環(huán)，化學(xué)家認(rèn)為環(huán)是單一的實(shí)體，而不是原子和鍵（節(jié)點(diǎn)和邊）的集合。

Michael 等人的研究指出，圖可以被「提升」為「簡單元胞復(fù)合體」（simplicial- and cellular complexes）的高維拓?fù)浣Y(jié)構(gòu)。我們可以設(shè)計(jì)一個(gè)更復(fù)雜的消息傳遞機(jī)制，使信息不僅可以像在 GNN 中那樣在節(jié)點(diǎn)之間傳播，還可以在環(huán)這樣的結(jié)構(gòu)之間傳播。恰當(dāng)?shù)貥?gòu)造這類「提升」操作使這些模型比傳統(tǒng)的 WL 測試具有更強(qiáng)的表達(dá)能力。

圖注：將圖「提升」為元胞復(fù)合體，元胞消息傳遞。

在論文“Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs”中，Michael 等人證明了，通過給節(jié)點(diǎn)和邊分配向量空間和線性映射，可以給圖配備一種額外的幾何結(jié)構(gòu)，即「元胞束」。傳統(tǒng)的 GNN 隱式地假設(shè)圖具有簡單的底層束結(jié)構(gòu)，這反映在相關(guān)擴(kuò)散方程的性質(zhì)和圖拉普拉斯算子的結(jié)構(gòu)上。與傳統(tǒng)的 GNN 相比，使用復(fù)雜的「束」可以產(chǎn)生更豐富的擴(kuò)散過程，有利于對其漸近行為。例如，在選擇出的恰當(dāng)?shù)氖Y(jié)構(gòu)上的擴(kuò)散方程可以在極限的多個(gè)類中分離，即使在親異環(huán)境中也是如此。

從幾何的觀點(diǎn)來看，束結(jié)構(gòu)類似于連接，這是微分幾何中描述流形上向量的平行傳輸?shù)母拍睢倪@個(gè)意義上說，我們可以把束的學(xué)習(xí)看作是一種取決于下游任務(wù)演化圖的幾何結(jié)構(gòu)的方法。Michaedl 等人證明，通過限制束的結(jié)構(gòu)群（例如，限制為特殊的正交群），可以使節(jié)點(diǎn)特征向量只旋轉(zhuǎn)，這樣可以獲得一些有趣的發(fā)現(xiàn)。

圖注：建立在圖上的元胞束由附加在每個(gè)節(jié)點(diǎn)上的向量空間和連接它們的線性約束映射組成。這可以被認(rèn)為是賦予圖幾何性質(zhì)，約束映射與連接類似。

「離散曲率類比」是另一種圖幾何結(jié)構(gòu)的例子，這是微分幾何領(lǐng)域用來描述流形局部性質(zhì)的標(biāo)準(zhǔn)方法。在論文“Understanding over-squashing and bottlenecks on graphs via curvature”中，Michael 等人證明了負(fù)圖 Ricci 曲率會(huì)對圖上的信息流產(chǎn)生瓶頸，從而導(dǎo)致 GNN 中的過壓縮現(xiàn)象。離散 Ricci 曲率可以被應(yīng)用于高階結(jié)構(gòu)（三角形和矩形），這在許多應(yīng)用中都很重要。這種結(jié)構(gòu)對于傳統(tǒng)的圖嵌入來說有些「過?！梗?yàn)閳D是異構(gòu)的（非常曲率）。對于通常用于嵌入的空間，即使是非歐空間，也是同構(gòu)的（常曲率）。

在論文“Heterogeneous manifolds for curvature-aware graph embedding”中，Michael 等人展示了一種具有可控 Ricci 曲率的異構(gòu)嵌入空間的構(gòu)造，可以選擇與圖的曲率匹配的 Ricci 曲率，不僅可以更好地表示鄰域（距離）結(jié)構(gòu)，而且可以更好地表示三角形和矩形等高階結(jié)構(gòu)。這些空間被構(gòu)造成同構(gòu)、對旋轉(zhuǎn)對稱的流形的乘積，可以使用標(biāo)準(zhǔn)黎曼梯度下降方法進(jìn)行有效優(yōu)化。

圖注：（左）空間形式（球體、平面和雙曲面）具有常的正的、零的和負(fù)的Ricci曲率，下方為它們與相應(yīng)的離散的 Forman 曲率的圖的類比（團(tuán)、網(wǎng)格和樹）。（中）積流形（圓柱可以被認(rèn)為是圓和線的乘積）。（右）具有變曲率的異質(zhì)流形及其圖的類比。

位置編碼可以看作是域的一部分。將圖看作連續(xù)流形的離散化，可以將節(jié)點(diǎn)位置坐標(biāo)和特征坐標(biāo)視為同一空間的不同維度。在這種情況下，圖可以用來表示由這種嵌入引出的黎曼度規(guī)的離散類比，與嵌入相關(guān)的諧波能量是狄利克雷能量的非歐擴(kuò)展，在弦論中稱為 Polyakov 泛函。這種能量的梯度流是一個(gè)擴(kuò)散型方程，它演化了位置坐標(biāo)和特征坐標(biāo)。在節(jié)點(diǎn)的位置上構(gòu)建圖是一種針對特定任務(wù)的圖重連的形式，它也會(huì)在擴(kuò)散的迭代層中發(fā)生變化。

圖注：通過帶有重連的 Beltrami 流對 Cora 圖的位置和特征分量進(jìn)行演化的結(jié)果。

域的演化可替代圖重連。作為一個(gè)預(yù)處理步驟，擴(kuò)散方程也可以應(yīng)用于圖的連通性，旨在改善信息流和避免過壓縮。Klicpera 等人提出了一種基于個(gè)性化 Page Rank 的算法，這是一種圖擴(kuò)散嵌入。在論文“Understanding over-squashing and bottlenecks on graphs via curvature”中，我們分析了這個(gè)過程，指出了它在異構(gòu)設(shè)定下的缺陷，并提出了一個(gè)受 Ricci 流啟發(fā)的過程的圖重接的替代方案。這樣的重連減少了負(fù)曲率造成的圖瓶頸的影響。Ricci 流是流形的幾何演化方程，非常類似于用于黎曼度規(guī)的擴(kuò)散方程，是微分幾何中類流行且強(qiáng)大的技術(shù)（包括著名的 Poincaré 猜想的證明）。更廣義地說，與其將圖重連作為預(yù)處理步驟，還不如考慮一個(gè)演化過程的耦合系統(tǒng)：一個(gè)演化特征，另一個(gè)演領(lǐng)域。

圖注：（上）具有負(fù)曲率的瓶頸的啞鈴形黎曼流形，經(jīng)過基于曲率的度規(guī)演化，變得更圓，瓶頸更不明顯。（下）一個(gè)類似的基于曲率的圖重連過程，減少了瓶頸，使圖對消息傳遞更友好。

4、結(jié)語

新的理論框架能讓我們走多遠(yuǎn)，是否能夠解決該領(lǐng)域目前尚未解決的問題，仍然是一個(gè)懸而未決的問題。

這些方法真的會(huì)在實(shí)踐中被使用嗎？對于實(shí)踐者來說，一個(gè)關(guān)鍵的問題是，這些方法是否會(huì)催生新的更好的架構(gòu)，或者仍然是一個(gè)脫離實(shí)際應(yīng)用的理論工具。Michael Brostein 相信，這個(gè)領(lǐng)域的研究將是實(shí)用的，通過拓?fù)浜蛶缀喂ぞ攉@得的理論成果將使我們對現(xiàn)有 GNN 架構(gòu)做出更好的選擇。例如，如何約束消息傳遞函數(shù)，以及何時(shí)使用這些特定的選擇。

我們是否已經(jīng)超越了消息傳遞的范疇？從廣義上講，數(shù)字計(jì)算機(jī)上的任何計(jì)算都是一種消息傳遞形式。然而，在嚴(yán)格意義上的 GNN 中，消息傳遞是一個(gè)計(jì)算概念，它通過將信息從一個(gè)節(jié)點(diǎn)發(fā)送到另一個(gè)節(jié)點(diǎn)來實(shí)現(xiàn)，這是一個(gè)內(nèi)在的離散過程。另一方面，所描述的物理模型以連續(xù)的方式在節(jié)點(diǎn)之間共享信息（例如，在一個(gè)圖耦合振蕩系統(tǒng)中，一個(gè)節(jié)點(diǎn)的動(dòng)力學(xué)依賴于它的鄰居在每個(gè)時(shí)間點(diǎn)上的動(dòng)力學(xué)）。在對描述該系統(tǒng)的微分方程進(jìn)行離散化和數(shù)值求解時(shí)，所對應(yīng)的迭代確實(shí)是通過消息傳遞實(shí)現(xiàn)的。

然而，人們可以假設(shè)使用這些物理系統(tǒng)的實(shí)際實(shí)現(xiàn)或其他計(jì)算范式（例如，模擬電子學(xué)或光子學(xué)）。在數(shù)學(xué)上，底層的微分方程的解有時(shí)可能以封閉形式給出：例如，各向同性擴(kuò)散方程的解是一個(gè)高斯核卷積。在這種情況下，鄰居的影響被吸收到核的結(jié)構(gòu)中，沒有發(fā)生實(shí)際的消息傳遞。

圖注：基于反向傳播的深度學(xué)習(xí)在真實(shí)物理系統(tǒng)中的應(yīng)用。

原文鏈接：

https://towardsdatascience.com/graph-neural-networks-beyond-weisfeiler-lehman-and-vanilla-message-passing-bc8605fa59a

編輯：于騰凱

校對：林亦霖

Michael Brostein 最新幾何深度學(xué)習(xí)綜述：超越 WL 和原始消息傳遞的 GNN