[[443041]]

又一年又接近尾聲，還有三天我們就要告別 2021 年了。

各個 AI 領域也迎來了年度總結和未來展望，今天來講一講 AI 圈始終大熱的圖機器學習（Graph ML）。

2021 年，圖機器學習領域涌現出了成千上萬篇論文，還舉辦了大量的學術會議和研討會，出現了一些重大的進展。2022 年，圖機器學習領域又會在哪些方面發力呢

Mila 和麥吉爾大學博士后研究員、專注于知識圖譜和圖神經網絡（GNN）研究的學者 Michael Galkin 在一篇博客中闡述了他的觀點。在文中，作者對圖機器學習展開了結構化分析，并重點介紹了該領域的主要進展和熱門趨勢。作者希望本文可以成為圖機器學習領域研究者的很好的參考。

本圖由 ruDALL-E 生成。

作者主要從以下 12 個部分進行了詳細的梳理：

1. 圖 Transformers + 位置特征
2. 等變 GNNs
3. 分子的生成模型
4. GNNs + 組合優化 & 算法
5. 子圖 GNN：超越 1-WL
6. 可擴展和深度 GNN：層數 100 及以上
7. 知識圖譜
8. 利用 GNN 做很酷的研究
9. 新的數據集、挑戰和任務
10. 課程和書籍
11. 庫和開源
12. 如何保持更新

圖 Transformers + 位置特征

GNN 在（通常是稀疏的）圖上運行，而 Graph Transformers (GT) 在全連接圖上運行，其中每個節點都連接到圖的其他節點。一方面，在節點數為 N 的圖中，圖的復雜度為 O(N^2) 。另一方面，GT 不會過度平滑，這是長程消息傳遞的常見問題。全連接圖意味著你有來自原始圖的真邊和從全連接變換添加的假邊，你需要進行區分。 更重要的是，你需要一種方法來為節點注入一些位置特征，否則 GT 不會超過 GNN。

今年最流行的兩個圖 transformer 模型為 SAN 和 Graphormer。Kreuzer、Beaini 等人提出的 SAN 采用拉普拉斯算子的 top-k 特征值和特征向量。 SAN 將光譜特征與輸入節點特征連接起來，在許多分子任務上優于稀疏 GNN。

Ying 等人提出的 Graphormer 采用空間特征。首先，節點特征豐富了中心編碼；然后，注意力機制有兩個偏置項：節點 i 和節點 j 之間的最短路徑距離；依賴于一條可用最短路徑的邊緣特征編碼。

Graphormer 實現了 2021 年 Graph ML 大滿貫：OGB large Challenge 和 Open Catalyst Challenge 奪得冠軍

等變 GNN

等方差有何獨特之處，讓 Geoffrey Hinton 如此贊美？

一般來說，等方差被定義在某些轉換組上，例如，3D 旋轉形成 SO(3) 組，特殊正交以 3D 的形式組合。等變模型在 2021 年掀起了 ML 的風暴，在圖機器學習中的許多分子任務中尤其具有突破性。應用于分子時，等變 GNN 需要一個額外的節點特征輸入，即分子物理坐標的一些表征，這些表征將在 n 維空間中旋轉 / 反射 / 平移。

在等變模型中，盡管變換的順序不同，但我們都能到達相同的最終狀態。圖源：Satorras, Hoogeboom, and Welling

Satorras、Hoogeboom 和 Welling 提出了 EGNN、E(n) 等變 GNN，其與普通 GNN 的重要區別在于向消息傳遞和更新步驟添加物理坐標。 等式 3 將相對平方距離與消息 m 相加，等式 4 更新位置特征。 EGNN 在建模 n 體（n-body 系統、作為自動編碼器和量子化學任務（QM9 數據集）方面顯示出令人印象深刻的結果。

與 vanilla GNN 的主要區別：等式 3 和 4 將物理坐標添加到消息傳遞和更新步驟中。圖源：Satorras, Hoogeboom, and Welling

另一種選擇是合并原子之間的角度，就像 Klicpera、Becker 和 Günnemann 在 GemNet 中所做的那樣。 這可能需要將輸入圖轉換為折線圖，例如邊圖，其中來自原始圖的邊變成折線圖中的節點。 這樣，我們就可以將角度作為新圖中的邊緣特征。

GemNet 在包括 COLL、MD17 和 Open Catalyst20 分子動力學任務上取得了不錯的成績， 顯然，等變 GNN 才剛剛起步，我們將在 2022 年看到更多進步！

分子的生成模型

由于幾何深度學習，整個藥物發現 領域在 2021 年實現了大幅的躍進。藥物發現的眾多關鍵挑戰之一是生成具有所需屬性的分子（圖）。這個領域很廣闊，這里只提到模型的三個分支。

歸一化流

Satorras、Hoogeboom 等人應用上述等變框架創建了 E(n) 等變歸一化流，能夠生成具有位置和特征的 3D 分子。

Shi、Luo 等人研究了在給定 2D 圖形的情況下生成 3D 構象異構體（即 3D 結構）的問題。模型 ConfGF 估計了原子坐標對數密度的梯度場。這些字段是旋轉平移等變的，作者想出了一種方法將這種等變屬性合并到估計器中。Conformer 采樣本身是通過退火朗之萬動力學采樣完成的。

RL 方法

該方法是以一種非常非科學的方式描述的，這些方法通過逐步附加「構建模塊」來生成分子。可以根據這些方法對構建過程的調節方式對其進行廣義分類。

例如，Gao、Mercado 、 Coley 以可合成性為構建過程的條件，即是否可以在實驗室中實際創建這種分子。為此，他們首先學習了如何創建構建塊的合成樹（一種模板）。

Yoshua Bengio 領導的 Mila 和斯坦福團隊提出了一個更通用的框架，他們引入了生成流網絡（GFlowNets）。這很難用幾句話來概括：首先，當我們想要對不同的候選者進行采樣時，GFlowNets 可以用于主動學習案例，并且采樣概率與獎勵函數成正比。此外，團隊最近的 NeurIPS'21 論文展示了 GFlowNets 應用于分子生成任務的用處。Emmanuel Bengio 的博客文章更詳細地描述了該框架并提供了更多的實驗證據：http://folinoid.com/w/gflownet/

GNNs + 組合優化 & 算法

2021 年，對于這個新興的子領域來說是重要的一年。

Xu et al 在 ICLR’21 的論文中研究了神經網絡的外推，并得出了一些亮眼的結論。基于算法對齊的概念，作者表示，GNN 與動態規劃（DP）可以很好地對齊（如下圖所示）。事實上，將經典 Bellman-Ford 算法尋找最短路徑的迭代和通過 GNN 的信息的聚合組合步驟做比較，會發現很多共同點。

此外，作者表明，在建模特定 DP 算法時，為 GNN 選擇合適的聚合函數至關重要，例如，對于 Bellman-Ford，需要一個最小聚合器（min-aggregator）。作者 Stefanie Jegelka 在 2021 年深度學習和組合優化研討會上細致講述了這項工作的主要成果：https://www.youtube.com/watch?v=N67CAjI3Axw

為了更全面的介紹這個領域，還需要重點介紹 Cappart et al 在 IJCAI’21 上的一項研究，該調查涵蓋了 GNN 中的組合優化。這篇文章首次出現了神經算法推理藍圖，后來 Veličković 和 Blundell 的 Patterns 中的立場文件也對此進行了描述。

這個藍圖解釋了神經網絡如何在嵌入空間中模仿和授權一般離散算法的執行過程。在編碼 - 處理 - 解碼方式中，抽象輸入（從自然輸入獲得）由神經網絡（處理器）進行處理，其輸出被解碼為抽象輸出，然后可以映射到更自然的任務特定輸出。

例如，如果抽象輸入和輸出可以表示為圖形，那么 GNN 可以即可成為處理器網絡。離散算法的一個常見的預處理步驟是將我們對這個問題的任何所知內容轉化為像「距離」或「邊緣容量」這樣的標量，并在這些標量上運行算法。相反，向量表征和神經執行可以輕松啟用高維輸入而不是簡單的標量，并附加反向傳播以優化處理器。

目前，該藍圖已經得到越來越多的采用，NeurIPS'21 上出現了一些很酷的作品。Xhonneux et al 研究了遷移學習是否可用于將學習到的神經執行器泛化到新任務；Deac et al 發現了強化學習中算法推理和隱式規劃之間的聯系。相信在 2022 年還會出現更多有關研究。

子圖 GNN：超越 1-WL

如果 2020 年是首次嘗試離開 GNN 表現力的 1-WL-landia 的一年，那么 2021 年則是超越 1WL-landia 的一年。這些聯系已被證明很有用，我們現在擁有一些強大且更具表現力的 GNN 架構，這些架構將消息傳遞擴展到更高階的結構，如單純復形（例如 Bodnar、Frasca、Wang 等人的 MPSN 網絡、胞腔復形（Bodnar、Frasca 等人的 CW Networks ））或子圖。

可擴展性和深度 GNN

如果你在使用 2-4 層 GNN 時羨慕深度 ResNet 或 100 多層的大型 Transformer，那么 2021 年有兩篇論文為我們帶來了福音，一篇是關于隨意訓練 100-1000 層 GNN 的論文，另一篇是關于幾乎恒定大小的鄰域采樣。

Li 等人提出了兩種新機制，可以在訓練極深的超參數化網絡時減少 GPU 內存消耗：將 L 層網絡的 O(L) 降低到 O(1)。作者展示了如何在 CV 或高效 Transformer 架構（例如 Reformer）中使用可逆層，并在層之間共享權重（權重綁定），以訓練多達 1000 層的 GNN。下圖展示了根據 GPU 需求進行的層數擴展。

圖源：Li 等人的論文《 Training Graph Neural Networks with 1000 Layers 》

Godwin 等人提出了一種利用循環學習深度 GNN 的方法——在塊（Block）中組織消息傳遞步驟，每個塊可有 M 個消息傳遞層。然后循環應用 N 個塊，這意味著有多個塊共享權重。如果有 10 個消息傳遞層和 10 個塊，你將得到一個 100 層的 GNN。其中一個重要的組成部分是 Noisy Nodes 正則化技術，它會干擾節點和邊的特征并計算額外的去噪損失。該架構能更好地適用于分子任務，研究團隊還在 QM9 和 OpenCatalyst20 數據集上進行了評估。

最后，如果想將任意 GNN 擴展成非常大的圖，那么只有一個選擇——采樣子圖。通常，對 k-hop 子圖進行采樣會導致指數級內存成本和計算圖大小

PyG 的作者 Matthias Fey 等人創建了一個在恒定時間內利用歷史嵌入和圖聚類擴展 GNN 的框架 GNNAutoScale。該方法在預處理期間將圖劃分為 B 個集群（小批量），以便最小化集群之間的連通性；然后在這些集群上運行消息傳遞與全批量設置一樣好，并顯著降低了內存要求（小了約 50 倍），這使得在商品級 GPU 上安裝深度 GNN 和大型圖成為可能。

知識圖譜（KG）

在 2021 年之前，模型根據歸納偏置、架構和訓練機制被明確分為轉導和歸納兩類。換句話說，轉導模型沒有機會適應未見過的實體，而歸納模型在中大型圖上訓練成本太高。 2021 年有兩種新架構在轉導和歸納環境中均可使用。這兩種架構不需要節點特征，可以在歸納模式中以與轉導模式相同的方式進行訓練，并可擴展到現實世界的 KG 大小。

一種是 Zhu 等人的神經 Bellman-Ford 網絡，其中將經典的 Bellman-Ford 推廣到了更高級別的框架，并展示了如何通過使用特定運算符實例化框架來獲得其他經典方法（如 Katz 指標、PPR 、最寬路徑等）。更重要的是，該研究表明泛化的 Bellman-Ford 本質上是一種關系 GNN 架構。 NBFNet 不學習實體嵌入，這使得模型通過泛化到未見過的圖而獲得了歸納性。該模型在關系圖和非關系圖上的鏈接預測任務上都表現出色。在 KG 的應用上，NBFNet 給 FB15k-237 和 WN18RR 兩個數據集帶來了自 2019 年以來最大的性能提升，同時參數減少了 100 倍。

另一種是 Galkin 等人受 NLP 中標記化算法啟發的新方法。在 KG 上應用時，NodePiece 將每個節點表征為一組 top-k 個最近的錨節點和節點周圍的 m 個唯一關系類型。錨點和關系類型被編碼為可用于任何下游任務（分類、鏈接預測、關系預測等）和任何歸納 / 轉導設置的節點表征。 NodePiece 特征可以直接被 RotatE 等非參數解碼器使用，也可以發送到 GNN 進行消息傳遞。該模型在歸納鏈接預測數據集上的性能可與 NBFNet 媲美，并在大型圖上表現出較高的參數效率——OGB WikiKG 2 上的 NodePiece 模型所需參數僅為淺的僅轉導模型的一百分之一。

利用 GNN 做很酷的研究

Huang, He 等人在 ICLR’21 上展示了 Correct & Smooth — 一個通過標簽傳播改進模型預測的簡單程序。 僅與 MLP 配對，該方法在不使用任何 GNN 且參數少得多的情況下以最高分沖擊 OGB 排行榜！ 今天，幾乎所有 OGB 節點分類賽道中的頂級模型都使用 Correct & Smooth 來壓縮更多的點。

圖源： Huang, He 等人

Knyazev 等人在前向傳遞中預測各種神經網絡架構參數的工作震驚了 ML 社區。 他們沒有采用隨機初始化模型，而是采用預測好的參數，這樣會優于隨機模型。

參數預測實際上是一個圖學習任務——任何神經網絡架構（ResNet、ViT、Transformers）都可以表示為一個計算圖，其中節點是具有可學習參數的模塊，節點特征是那些參數，網絡有 一堆節點類型（比如，線性層、卷積層等，作者使用了大約 15 種節點類型）。 參數預測則是一個節點回歸任務。 計算圖使用 GatedGNN 進行編碼，并將其新表示發送到解碼器模塊。 為了訓練，作者收集了一個包含 1M 個架構（圖）的新數據集。 該方法適用于任何神經網絡架構，甚至適用于其他 GNN。

預測未知模型的參數的 pipeline。圖源：Knyazev 等人

DeepMind 和谷歌通過將道路網絡建模為超分段圖并在其上應用 GNN，極大地提高了谷歌地圖中 ETA 的質量。 在 Pinion 等人的論文中，該任務被定義為節點級和圖級回歸。 除此之外，作者還描述了許多需要解決的工程挑戰，以便在谷歌地圖規模上部署系統。 應用 GNN 解決數百萬用戶面臨的實際問題。

論文地址：https://arxiv.org/pdf/2108.11482.pdf

圖源: Pinion 等人

一些資料總結

文章最后，作者介紹了一些相關資料，包括數據集、課程和書籍、一些實用的庫等內容。

如果你不習慣使用 Cora、Citeseer、Pubmed 數據集，可以考慮以下：

• OGB 數據集包含 3 個非常大的圖，可分別用于節點分類（240M 節點）、鏈接預測（整個 Wikidata，90M 節點）和圖回歸（4M 分子）任務。 在 KDD Cup 中，大多數獲勝團隊使用了 10-20 個模型組合；
• 由 Meta AI 發起的公開催化劑挑戰賽（ Open Catalyst NeurIPS’21 Challenge ），提供了一項大型分子任務——給出具有原子位置的初始結構，預測其松弛狀態能。這個數據集非常龐大，需要大量的計算，但組織者暗示將發布一個更小的版本，這將對 GPU 預算有限的小型實驗室更友好。事實上，Graphormer 在 OGB LSC 和 OpenCatalyst ' 21 中都獲得了第一名，并在 2021 年獲得了 Graph ML 的大滿貫；
• GLB 2021 帶來了一組新的數據集，包括 Lim 等人提出的 non-homophilous graphs ，Tsitsulin 等人提出的 graph simulations，以及 Rozemberczki 等人提出的 spatiotemporal graphs 等；
• NeurIPS’21 數據和基準賽道帶來了新數據集，MalNet 可用于圖分類，該數據集的平均圖大小是 15k 節點以及 35k 邊；ATOM3D 可用于 3D 分子任務；RadGraph 可用于從放射學報告中提取信息。

由 Michael Bronstein、Joan Bruna、Taco Cohen 和 Petar Veličković 編寫的幾何深度學習原型書和課程，包含 12 個講座和實踐教程和研討會。

• 書籍地址：https://arxiv.org/pdf/2104.13478.pdf
• 課程地址：https://geometricdeeplearning.com/lectures/

此外，比較有價值的書籍和課程還包括

• 由 18 位學者參與撰寫的知識圖譜新書：https://kgbook.org/
• William Hamilton 的圖表示學習手冊：https://www.cs.mcgill.ca/~wlh/grl_book/

2021 年發布的庫包含 TensorFlow GNN 、TorchDrug。

• TensorFlow GNN 地址：https://github.com/tensorflow/gnn
• TorchDrug 地址：https://torchdrug.ai/

在 2021 年持續更新的庫包括：

• PyG 2.0 — 現在支持異構圖、GraphGym 以及一系列改進和新模型；
• DGL 0.7 — 在 GPU 上進行圖采樣，更快的內核，更多的模型；
• PyKEEN 1.6 — 更多的模型、數據集、指標和 NodePiece 支持；