2021年Graph ML熱門趨勢和主要進展總結(jié)（2）

GNNs + Combinatorial Optimization & Algorithms

Xu 等人在他們 ICLR’21 論文中研究了神經(jīng)網(wǎng)絡(luò)的外推并得出了幾個驚人的結(jié)果。使用算法對齊的概念，作者表明 GNN 與動態(tài)規(guī)劃 (DP) 良好對齊（查看插圖 ）。與 ICLR’20 論文相比，作者在這里討論了更強的外推條件 - 與 DP 的線性對齊。事實上比較經(jīng)典 Bellman-Ford 算法的迭代以尋找最短路徑和通過 GNN 的消息的聚合組合步驟 - 你會發(fā)現(xiàn)很多共同點。作者還表明，在建模特定 DP 算法時，為 GNN 選擇合適的聚合函數(shù)至關(guān)重要，例如對于 Bellman-Ford，需要一個最小聚合器。

為了對該領(lǐng)域進行更全面的介紹，我想重點介紹 Cappart 等人在 IJCAI'21 上進行的一項全面調(diào)查，該調(diào)查涵蓋了優(yōu)化組合中的 GNN。這篇文章首次出現(xiàn)了神經(jīng)算法推理藍(lán)圖，后來在 Veli?kovi? 和 Blundell 的 Patterns 中的論文中進行了描述。

該藍(lán)圖解釋了神經(jīng)網(wǎng)絡(luò)如何模仿和授權(quán)嵌入空間中通常離散算法的執(zhí)行過程。在編碼-處理-解碼方式中，抽象輸入（從自然輸入獲得）由神經(jīng)網(wǎng)絡(luò)（處理器）處理，其輸出被解碼為抽象輸出，然后可以映射到更自然的任務(wù)特定輸出。例如如果抽象輸入和輸出可以表示為圖形，那么 GNN 可以是處理器網(wǎng)絡(luò)。離散算法的一個常見預(yù)處理步驟是將我們對問題的了解壓縮為“距離”或“邊容量”等標(biāo)量，并在這些標(biāo)量上運行算法。相反向量表示和神經(jīng)執(zhí)行可以輕松啟用高維輸入而不是簡單的標(biāo)量，并附加反向傳播以優(yōu)化處理器。有關(guān)更多信息，請參閱 Petar Veli?kovi? 的演講。

這個藍(lán)圖正在被越來越多的人使用——例如NeurIPS’21 有一些很酷的作品！Xhonneux 等人研究了遷移學(xué)習(xí)是否可用于將學(xué)習(xí)到的神經(jīng)執(zhí)行器泛化到新任務(wù)；Deac 等人發(fā)現(xiàn)了強化學(xué)習(xí)中算法推理和隱式規(guī)劃之間的聯(lián)系。2022 年還會有更多！

Scalability and Deep GNNs: 100 Layers and More

如果你在使用 2-4 層 GNN 時嫉妒深度 ResNets 或 100 層以上的巨大 Transformer，那么是時候歡呼了！2021 年為我們帶來了 2 篇隨意訓(xùn)練 100-1000 層 GNN 的論文，以及一篇關(guān)于幾乎恒定大小的鄰域采樣的工作。

Li 等人提出了兩種機制，在訓(xùn)練極深的過參數(shù)化網(wǎng)絡(luò)時，可以將GPU內(nèi)存消耗從L層的O(L)大幅降低到O(1)。作者展示了如何使用在 CV 或高效的 Transformer 架構(gòu)（如 Reformer）中使用了多年的可逆層；在層之間共享權(quán)重。然后可以訓(xùn)練多達(dá) 1000 層的 GNN 。下面的圖表展示了對 GPU 要求適中的層數(shù)的不斷擴展。

Godwin 等人介紹了一種利用遞歸學(xué)習(xí)深度 GNN 的方法——消息傳遞步驟被組織成塊，每個塊可以有 M 個消息傳遞層。然后循環(huán)應(yīng)用 N 個塊，這意味著塊之間共享權(quán)重。如果有 10 個消息傳遞層和 10 個塊將得到一個 100 層的 GNN。這里面其中一個重要的組成部分是噪聲節(jié)點正則化技術(shù)，它擾動節(jié)點和邊的特征并計算額外的去噪損失。

該架構(gòu)適合更好的分子任務(wù)，并在 QM9 和 OpenCatalyst20 數(shù)據(jù)集上進行了評估。

如果我們想要將任意GNN縮放到非常大的圖，我們沒有其他選擇只能對子圖進行采樣。如果采樣k-hop子圖會導(dǎo)致指數(shù)級的內(nèi)存開銷和計算圖的大小。

PyG的作者Matthias Fey等人創(chuàng)建了GNNAutoScale，它利用歷史嵌入(緩存以前消息傳遞步驟)和圖聚類(著名的METIS算法)在恒定時間內(nèi)縮放gnn的框架。在預(yù)處理時將圖劃分為B個簇(小批量)，使簇之間的連通性最小化。然后通過這些簇運行消息，在緩存中跟蹤更新的節(jié)點特性。經(jīng)過實驗證明深度網(wǎng)絡(luò)(最多64層)的GNNAutoScale性能與完整批量一樣好，但內(nèi)存需求顯著降低(大約是普通GPU的50倍)，因此可以將深度gnn和大型圖放置消費級GPU上。

知識圖譜

基于kg的表征學(xué)習(xí)終于突破了轉(zhuǎn)換的極限。在2021年之前，模型被明確地分為直推式型和歸納型并且具有不同的歸納偏差、架構(gòu)和訓(xùn)練方式。直推式模型沒有機會適應(yīng)看不見的實體，而歸納模型對于訓(xùn)練中大型圖來說太昂貴了。

2021年出現(xiàn)了很多方法對這兩種架構(gòu)的改進：

在直推和歸納環(huán)境中工作

不需要節(jié)點特征

可以在歸納模式中以與直推模式相同的方式進行訓(xùn)練

可擴展到現(xiàn)實世界的 KG 大小

Zhu 等人的 Neural Bellman-Ford 找到了一種非常優(yōu)雅的方法將經(jīng)典的 Bellman-Ford 推廣到更高級別的框架，并展示了如何通過使用特定運算符實例化框架來獲得其他知名方法，如 Katz 指數(shù)、PPR 或最寬路徑。更重要的是，他們的論文表明廣義 Bellman-Ford 本質(zhì)上是一個關(guān)系 GNN 架構(gòu)（GNN 和動態(tài)規(guī)劃之間算法對齊的另一個確認(rèn)）。

NBFNet 不學(xué)習(xí)實體嵌入（僅關(guān)系和 GNN 權(quán)重），這使模型可以通過設(shè)計和泛化到看不見的圖并具有歸納性。該模型在關(guān)系圖和非關(guān)系圖上的鏈接預(yù)測任務(wù)上都表現(xiàn)出色。

在 KG的應(yīng)用中，NBFNet 從 2019 年開始為 FB15k-237 和 WN18RR 帶來最大的性能提升，同時參數(shù)減少了 100 倍。

Galkin 等人（本文的作者是論文的作者之一）的另一種方法的靈感來自 NLP 中的標(biāo)記化算法，該算法包含了固定的能夠標(biāo)記任何單詞的詞匯表，那些在訓(xùn)練時看不見的單詞也包括在里面。將這種方法應(yīng)用于 KG，NodePiece 將每個節(jié)點表示為一組前 k 個最近的錨節(jié)點（在預(yù)處理步驟中采樣）和節(jié)點周圍的 m 個唯一關(guān)系類型。錨點和關(guān)系類型被編碼為可用于任何下游任務(wù)（分類、鏈接預(yù)測、關(guān)系預(yù)測等）和任何歸納/直推設(shè)置的節(jié)點表示。

NodePiece的特征可以被像RotatE這樣的非參數(shù)****直接使用也可以發(fā)送到gnn進行消息傳遞。該模型在歸納鏈接預(yù)測數(shù)據(jù)集上具有與NBFNet相當(dāng)?shù)男阅?，在大型圖上具有較高的參數(shù)效率——OGB WikiKG 2上的NodePiece模型需要的參數(shù)比淺層的直推模型少約100倍。

一些其他的GNN的研究

本節(jié)提到了幾個特別有意思的作品，它們使用了 GNN但不屬于某個特定類別。

Huang、He 等人在 ICLR’21 上展示了 Correct & Smooth - 一個通過標(biāo)簽傳播改進模型預(yù)測的簡單程序。該方法在沒有使用任何gnn和更少的參數(shù)的情況下，僅與一個MLP配對并以最高分?jǐn)?shù)橫掃OGB排行榜!目前幾乎所有OGB的節(jié)點分類上的頂級模型都使用了Correct & Smooth來獲得更多一點的分?jǐn)?shù)。

11月，Knyazev等人在通過一次前向傳遞預(yù)測各種神經(jīng)網(wǎng)絡(luò)架構(gòu)參數(shù)的工作震動了ML社區(qū)。與其隨機初始化模型還不如直接使用預(yù)測好的參數(shù)，而且這樣的模型已經(jīng)大大優(yōu)于隨機模型

*博客內(nèi)容為網(wǎng)友個人發(fā)布，僅代表博主個人觀點，如有侵權(quán)請聯(lián)系工作人員刪除。