圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

本文作者： JocelynWang

編輯：幸麗娟

2020-01-06 10:09

導(dǎo)語：圖神經(jīng)網(wǎng)絡(luò)研究者看過來！

瑞利-貝納德對流（Rayleigh–Bénard Convection）。利用有限元方法將空間上連續(xù)的問題離散化，將復(fù)雜的關(guān)系歸納偏差顯示為實體集合。資料來源：原作者。

多智能體系統(tǒng)被廣泛應(yīng)用于各種不同的科學(xué)領(lǐng)域：從物理學(xué)到機器人學(xué)、博弈論、金融學(xué)和分子生物學(xué)等等。通常來說，預(yù)測或決策任務(wù)依賴于具有噪聲且無規(guī)則采樣的的觀測，因此封閉形式的分析公式對此是無效的。

這類系統(tǒng)對關(guān)系歸納偏差提供了生動形象的樣例。在樣本統(tǒng)計或機器學(xué)習(xí)過程中引入歸納誤差，是一種普遍用于提高樣本有效性和泛化性的方式。從目標(biāo)函數(shù)的選擇到適合某項具體問題的自組織深度學(xué)習(xí)的框架設(shè)計，設(shè)定偏差也是非常常見且有效的方式。

關(guān)系歸納偏差^[1]代表一類特殊的偏差，涉及實體之間的關(guān)系。無論是圖形模型、概率模型還是其他模型，都是一類專門對實體施加先驗結(jié)構(gòu)形式的關(guān)系偏差的傳統(tǒng)模型。這些圖形結(jié)構(gòu)能夠在不同領(lǐng)域中發(fā)揮作用，它可以通過引入條件獨立性假設(shè)來降低計算復(fù)雜度，也可以通過將先驗知識編碼為圖的形式來增強樣本的有效性。

圖神經(jīng)網(wǎng)絡(luò)（GNN）是圖模型對應(yīng)的深度學(xué)習(xí)網(wǎng)絡(luò)。GNN 通常會在這兩種情況中使用：一是當(dāng)目標(biāo)問題結(jié)構(gòu)可以編碼為圖的形式；二是輸入實體間關(guān)系的先驗知識本身可以被描述為一張圖。

GNN 在許多應(yīng)用領(lǐng)域都展示了顯著的效果，例如：節(jié)點分類^[2]、圖分類、預(yù)測^[3][4]以及生成任務(wù)^[5]。

一、深度學(xué)習(xí)中的常微分方程

一種類型不同但重要性相等的歸納偏差與收集到數(shù)據(jù)所使用系統(tǒng)的類別相關(guān)。盡管從傳統(tǒng)上看，深度學(xué)習(xí)一直由離散模型主導(dǎo)，但在最近的研究提出了一種將神經(jīng)網(wǎng)絡(luò)視為具有連續(xù)層的模型^[6]的處理方法。

這一觀點將前向傳播過程，重定義為常微分方程（ODE）中初值求解的問題。在這個假設(shè)下，可以直接對常微分方程進行建模，并可以提高神經(jīng)網(wǎng)絡(luò)在涉及連續(xù)時間序列任務(wù)上的性能。

《Graph Neural Ordinary Differential Equations》這項工作旨在縮小幾何深度學(xué)習(xí)和連續(xù)模型之間的差距。圖神經(jīng)常微分方程（Graph Neural Ordinary Differential Equations ，GDE）將圖結(jié)構(gòu)數(shù)據(jù)上的一般性任務(wù)映射到一個系統(tǒng)理論框架中。我們將常見的圖結(jié)構(gòu)數(shù)據(jù)放入系統(tǒng)理論框架中，比如將數(shù)據(jù)結(jié)構(gòu)化到系統(tǒng)中：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

無論 GDE 模型的結(jié)構(gòu)是固定還是隨時間變化的，它都可以通過為模型配備連續(xù)的 GNN 圖層來對定義在圖上的向量場建模。

GDE 模型由于結(jié)構(gòu)由連續(xù)的 GNN 層定義，具備良好的靈活性，可以適應(yīng)不規(guī)則序列樣本數(shù)據(jù)。

GDE 模型的主要目的是，提供一種數(shù)據(jù)驅(qū)動的方法為結(jié)構(gòu)化系統(tǒng)建模，特別是當(dāng)這個動態(tài)過程是非線性時，更是難以用經(jīng)典的分析方法進行建模。

下面是對GDE的介紹。關(guān)于更多細節(jié)和推導(dǎo)，請參閱原論文，論文相關(guān)鏈接如下：

https://arxiv.org/abs/1911.07532

目前我們正在開發(fā)一個用于介紹GDE模型的 Github Repository（倉庫），其中包含使用 Jupyter notebook 且?guī)в凶⑨尩南嚓P(guān)示例，Github 相關(guān)地址如下：

https://github.com/Zymrael/gde

據(jù)悉，我們正計劃將它最終部署成具有不同功能的設(shè)置（包括預(yù)測、控制…），其中包括所有主要圖形神經(jīng)網(wǎng)絡(luò)（GNN）架構(gòu)下不同 GDE 變體的工作示例。

二、序言和背景

GDE 和 GNN 一樣，都是在圖上進行操作。關(guān)于符號和基本定義更詳細的介紹，我們參閱了關(guān)于 GNN 的優(yōu)秀的相關(guān)綜合研究（相關(guān)研究鏈接為：https://arxiv.org/abs/1901.00596）以及原論文中的背景部分。

下面，我們將對 GDE 進行簡要的介紹，不夠?qū)嶋H上，只有下面兩點關(guān)于圖的基本知識是我們即將需要了解到的：

1、圖是由邊連接的互連節(jié)點（實體）的集合。深度學(xué)習(xí)模型通常處理用一組特征（通常以一組向量或張量）描述節(jié)點的屬性圖。對于 n 個節(jié)點的圖，每個節(jié)點都可以用 d 個特征描述，最后我們將這 n x d 個節(jié)點嵌入矩陣表示為 H。
2、圖的結(jié)構(gòu)由其鄰接矩陣 A 捕獲。節(jié)點之間的連通結(jié)構(gòu)表現(xiàn)出標(biāo)準深度學(xué)習(xí)模型和GNN模型之間的主要區(qū)別^[1]，因為GNN直接以各種方式利用它對節(jié)點嵌入進行操作。

三、圖神經(jīng)常微分方程

圖神經(jīng)常微分方程（GDE）定義如下：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

GDE的一般公式

其中，H是節(jié)點特征矩陣。上式中定義了函數(shù) F 參數(shù)化的 H 的向量場，其中函數(shù) F 可以是任意已知的圖神經(jīng)網(wǎng)絡(luò)（GNN）層。

換句話說，F(xiàn) 利用圖 G 節(jié)點的連接信息及其節(jié)點特征來描述 H 在 S 中的變化過程。其中，S 是模型的深度域；不同于 GNN 由自然數(shù)的子集來指定的深度域，S 是連續(xù)的，它表示由函數(shù) F 定義的常微分方程的積分域。

GDE 可以通過多種方式進行訓(xùn)練，這一點很像標(biāo)準的神經(jīng)常微分方程^[6]。原論文中也對系統(tǒng)的適定性進行了詳細闡釋和討論。

一般的 GDE 公式帶有幾種含義。在一般神經(jīng)常微分方程中，觀察到選擇離散化方案可以對 ResNets（殘差網(wǎng)絡(luò)）已知的先前離散多步驟變量進行描述^[7]。因此，深度學(xué)習(xí)中連續(xù)動態(tài)系統(tǒng)的觀點不僅局限于微分方程的建模，而且可以利用豐富的數(shù)值方法相關(guān)文獻來指導(dǎo)發(fā)現(xiàn)新的通用模型。

與 ResNets 相比，GNN 作為一個模型類別來說算是相對年輕的。因此，關(guān)于多步驟的復(fù)雜變體以及類似分形殘差連接的相關(guān)文獻發(fā)展得并沒有那么完善；而我們可以發(fā)現(xiàn)一些新的 GNN 變體是通過應(yīng)用GDE的各種離散化方案來指導(dǎo)的，而不是完全從頭開始。

靜態(tài)圖結(jié)果：節(jié)點分類

通過在 Cora、Pubmed 和 Citeseer 上進行一系列半監(jiān)督節(jié)點分類實驗，證明 GDE 可以作為高性能的通用模型。這些數(shù)據(jù)集包含靜態(tài)圖，其中鄰接矩陣 A 保持不變，從而使其遠離運用GDE的動態(tài)系統(tǒng)設(shè)置。我們評估圖卷積常微分方程（GCDE）的性能，定義為：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

GCDE模型。在我們的論文中包含了一個更加詳細的版本，以及一些GNN流行的GDE變體版本。

它們的完全離散的形式對應(yīng)圖卷積網(wǎng)絡(luò)（GCN）^[8]。我們參考了包括著名的圖注意力網(wǎng)絡(luò)（GAT）^[9]在內(nèi)的文獻作為參考：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

節(jié)點分類任務(wù)的準確性。上表取值為100次運行的平均值和標(biāo)準偏差。

GCDE 被證明可以媲美最先進的模型，并且優(yōu)于它們的離散模型。我們評估了如下兩種 GCDE的版本：

一種是離散的固定步長的方案，采用 Runge-Kutta4（GCDE-rk4）；
另一種是自適應(yīng)步長方案，采用 Dormand-Prince（GDDE-dpr5）。

固定步長的離散方案并不能保證 ODE 近似仍然接近解析解；在這種情況下，求解一個適當(dāng)?shù)?ODE 是不必要的，GCDE—rk4能夠提供一個計算效率高的類子結(jié)構(gòu)的FractalNet（比如GCN模型的結(jié)構(gòu)）來提高準確率。

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

如圖為Cora的訓(xùn)練損失和準確率，其中陰影區(qū)域是95%置信區(qū)間

另一方面，使用自適應(yīng)步長解算器訓(xùn)練 GCDE 自然會比使用 vanilla GCN 模型的深度更深，后者網(wǎng)絡(luò)層的深度使該網(wǎng)絡(luò)性能大大降低。

實驗中我們成功地訓(xùn)練了GCDE-dpr5，它有多達200個ODE函數(shù)評估（NFE），這使得它對圖中的計算量明顯高于vanilla GCN（由于層數(shù)太深使得性能大幅度降低）。應(yīng)該注意的是，由于GDE在求解函數(shù)中會對參數(shù)重利用，它比對應(yīng)的離散項需要更少的參數(shù)。

有趣的是，自適應(yīng)步長GDE似乎不受節(jié)點特征過度平滑的影響。過度平滑問題^[10]阻礙了深層GNN在各個領(lǐng)域的有效使用，特別是在多智能體強化學(xué)習(xí)（MARL）中，我們目前正在積極探索GDE這一特性，并能夠很快進行更為詳細的分析。

四、時空 GDE

GDE 中一項關(guān)鍵的設(shè)定涉及到時空圖數(shù)據(jù)信息。在處理圖的序列信息時，需要用到 GNN 的遞歸版本^[11][12]。
然而，與常規(guī)的遞歸神經(jīng)網(wǎng)絡(luò)（RNN）及其變體一樣，在固定的離散度的情況下不允許其對不規(guī)則的樣本數(shù)據(jù)進行操作。這一事實進一步推動了基于到達次數(shù)之間的變動的先驗假設(shè)下 RNN 形式的發(fā)展，比如 RNN 的 ODE 版本^[14] 。

在涉及時間分量的場景中，GDE 中 S 的深度域與時間域一致，并且可以根據(jù)需求進行調(diào)整。例如，給定時間窗口 Δt，使用 GDE 進行預(yù)測的公式形式如下：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

盡管擁有特殊的結(jié)構(gòu)，GDE 代表了一類圖序列的自回歸模型，以混合動態(tài)系統(tǒng)的形式自然地通往擴展的經(jīng)典時空結(jié)構(gòu)，比如：以時間連續(xù)和時間離散的動力學(xué)相互作用為特征的系統(tǒng)。

它的核心思想是，讓一個 GDE 在兩種時間點之間平滑地控制潛在的節(jié)點特征，然后應(yīng)用一些離散算子，讓節(jié)點特征 H 快速移動，接著由輸出層來處理這些節(jié)點特征 H 。

給定一系列的時間常數(shù) 圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？以及一種數(shù)據(jù)的狀態(tài)——圖數(shù)據(jù)信息流，自回歸 GDE 的一般公式為：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

如圖為自回歸GDE。擁有已知連續(xù)變量的時空GNN模型可以通過從這個系統(tǒng)中通過選擇合適的F，G，K參數(shù)來獲得。

其中，參數(shù) F，G，K 是類似于 GNN 的操作或者一般的神經(jīng)網(wǎng)絡(luò)層，H+表示經(jīng)過離散變換后的 H 值。該系統(tǒng)的轉(zhuǎn)變過程可以通過混合自動機進行可視化處理：

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

自回歸 GDE的混合自動機原理圖

與只具有離散跳躍的標(biāo)準遞歸模型相比，自回歸 GDE 在跳躍間包含了一個潛在特征節(jié)點的連續(xù)流 H。自回歸 GDE 的這一特性使它們能夠從不規(guī)則的觀測結(jié)果中來跟蹤動態(tài)系統(tǒng)。

F，G，K 的不同組合可以產(chǎn)生最常見的時空 GNN 模型的連續(xù)變量。

為了評估自回歸 GDE 模型對預(yù)測任務(wù)的有效性，我們在建立的 PeMS 流量數(shù)據(jù)集上進行了一系列實驗。我們遵循文獻^[15]的實驗預(yù)設(shè)參數(shù)，并且附加了一個預(yù)處理步驟：對時間序列進行欠采樣，為了模擬在具有不規(guī)則時間戳或有缺失值等具有挑戰(zhàn)性的環(huán)境，這里將每個輸入以 0.7 的概率進行刪除。

為了在由連續(xù)時間系統(tǒng)生成的數(shù)據(jù)設(shè)置中測量 GDE 獲得的性能提升，我們使用 GCDE-GRU 及其對應(yīng)的離散 GCGRU^[12]，并將結(jié)果置于 vanilla GRU 度量標(biāo)準中進行測量。

對于所考慮的每個模型，我們收集了標(biāo)準化 RMSE（NRMSE）和平均絕對百分比誤差（MAPE）結(jié)果。關(guān)于所選指標(biāo)和數(shù)據(jù)的更多細節(jié)請參見原論文。

由于在訓(xùn)練和測試過程中平均的預(yù)測時間范圍會發(fā)生急劇變化，這種時間戳之間的非恒定差異導(dǎo)致單個模型的預(yù)測任務(wù)更加具有挑戰(zhàn)性。為更加公平的對模型進行比較，我們將增量時間戳信息作為 GCGN 和 GRU 的附加節(jié)點特征。

圖神經(jīng)常微分方程，如何讓 GNN 在連續(xù)深度域上大顯身手？

不規(guī)則數(shù)據(jù)預(yù)測任務(wù)的結(jié)果。此處取5次訓(xùn)練的平均值和標(biāo)準差。

由于 GCDE-GRU 和 GCGRU 的設(shè)計在結(jié)構(gòu)和參數(shù)數(shù)量上是匹配的，我們可以在 NRSME 中測量到 3% 的性能增長，在MAPE中測量到7%的性能增長。

對具有連續(xù)動態(tài)和不規(guī)則數(shù)據(jù)集的其他應(yīng)用領(lǐng)域采用 GDE 作為建模工具，也將同樣使其擁有優(yōu)勢，例如在醫(yī)學(xué)、金融或分布式控制系統(tǒng)等領(lǐng)域。我們正在這些領(lǐng)域進行另外的一些相關(guān)實驗，歡迎提出任何要求、想法或合作意見。