GNNs + Combinatorial Optimization & Algorithms

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

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

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

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

Scalability and Deep GNNs: 100 Layers and More

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

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

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

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

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

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

知識圖譜

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

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

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

不需要節(jié)點特征

可以在歸納模式中以與直推模式相同的方式進行訓練

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

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

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

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

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

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

一些其他的GNN的研究

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

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

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

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