GNNs + Combinatorial Optimization & Algorithms

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

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

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

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

Scalability and Deep GNNs: 100 Layers and More

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

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

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

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

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

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

知識(shí)圖譜

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

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

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

不需要節(jié)點(diǎn)特征

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

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

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

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

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

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

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

一些其他的GNN的研究

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

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

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

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