2020 年才剛剛開始，但我們已經(jīng)可以通過最新的研究論文看到圖形機(jī)器學(xué)習(xí)（GML）的趨勢。以下是我對(duì) 2020 年 GML 的重要性的看法以及對(duì)這些論文的討論。

前言

本文的目的不是介紹 GML 的基本概念，如圖神經(jīng)網(wǎng)絡(luò)（GNNs），而是揭示我們可以在頂級(jí)科學(xué)會(huì)議上看到的前沿研究。首先，我將資料提交給 ICLR2020，這是一個(gè)在 GML 領(lǐng)域最負(fù)盛名的會(huì)議。在前面的文章（https://medium.com/@sergei.ivanov_24894/iclr-2020-graph-papers-9bc2e90e56b0 ）中，我已經(jīng)描述了關(guān)于這個(gè)域的一些簡單的信息，但是這里有一個(gè)簡短的版本： 

在 GML 領(lǐng)域有 150 份論文被提交，其中三分之一被接收。大約占了所有被接收論文的 10% 。

我閱讀了大部分 GML 論文，以下是我對(duì) 2020 年趨勢的認(rèn)知： 

• 對(duì) GNN 更扎實(shí)的理論理解

• GNN 的最新應(yīng)用

• 知識(shí)圖譜越來越流行 

• 圖嵌入的新框架

讓我們看看這些趨勢。

1.對(duì) GNN 更扎實(shí)的理論理解

我特別高興地看到這一趨勢，因?yàn)樗砻?GML 領(lǐng)域已經(jīng)成熟，以前的啟發(fā)式方法正在被新的理論解決方案所取代。關(guān)于圖神經(jīng)網(wǎng)絡(luò)還有很多需要了解的地方，但是關(guān)于 GNNs 是如何工作的已經(jīng)有很多重要的結(jié)果。

我將從我的最愛開始：Andreas Loukas 的「什么圖形神經(jīng)網(wǎng)絡(luò)無法學(xué)習(xí)：深度 VS 寬度」。這篇論文在技術(shù)的簡單性、實(shí)踐影響力和理論見解的深遠(yuǎn)性之間取得了顯著的平衡。

它表明，如果我們希望 GNN 能夠計(jì)算出流行圖問題（如循環(huán)檢測、直徑估計(jì)、頂點(diǎn)覆蓋等）的解，那么節(jié)點(diǎn)嵌入的維數(shù)（網(wǎng)絡(luò)寬度，w）乘以層數(shù)（網(wǎng)絡(luò)深度，d）應(yīng)該與圖 n 的大小成正比，即 dw=O（n）。

因此，許多 GNN 的當(dāng)前實(shí)現(xiàn)未能達(dá)到此條件，這是由于與圖的大小相比，層的數(shù)量（在許多實(shí)現(xiàn)中約為 2-5 層）和嵌入的維度（約為 100-1000 層）不夠大。另一方面，在目前的環(huán)境下，更大的網(wǎng)絡(luò)令人望而卻步，這就提出了一個(gè)問題：我們應(yīng)該如何設(shè)計(jì)高效的 GNN，這是我們未來需要解決的問題。讓人信服的是，本文還從 80 年代的分布式計(jì)算模型中得到啟示，說明 GNN 在本質(zhì)上做了同樣的事情。里面有更多的結(jié)果，所以我建議你看看。

類似地，其他兩篇論文，Oono&Suzuki 和 Barcelóet al. 也研究了 GNN。第一篇文章「Graph Neural Networks Exponentially Lose Expressive Power for Node Classification」中寫道：： 

在一定的權(quán)值條件下，當(dāng)層數(shù)增加時(shí)，GCN 除了節(jié)點(diǎn)度和連接分量（由 Laplacian 譜確定）外，不能學(xué)習(xí)任何東西。

這個(gè)結(jié)果推廣了 Markov 過程收斂到唯一平衡點(diǎn)這一眾所周知的性質(zhì)，其中收斂速度由轉(zhuǎn)移矩陣的特征值決定。

在第二篇關(guān)于圖神經(jīng)網(wǎng)絡(luò)邏輯表達(dá)的論文中，作者展示了 GNN 與它們能夠捕獲的節(jié)點(diǎn)分類器的類型之間的聯(lián)系。我們已經(jīng)知道，有些 GNN 和 WL 同構(gòu)檢驗(yàn)一樣強(qiáng)大，即當(dāng)且僅當(dāng)兩個(gè)節(jié)點(diǎn)被 GNN 分為同一類時(shí)，WL 才對(duì)它們著色。但是，GNN 可以捕獲其他分類函數(shù)嗎？例如，假設(shè)有一個(gè)布爾函數(shù)，當(dāng)且僅當(dāng)一個(gè)圖有一個(gè)孤立的頂點(diǎn)時(shí)，該函數(shù)才將 true 賦給所有節(jié)點(diǎn)。GNN 能捕獲這個(gè)邏輯嗎？直覺上不能，因?yàn)?GNN 是一種消息傳遞機(jī)制，如果圖的一部分和另一部分（兩個(gè)連接的組件）之間沒有鏈接，那么這兩個(gè)部分之間就不會(huì)有消息傳遞。因此，一個(gè)簡單的解決方案是在鄰域聚集之后添加一個(gè)讀出操作，這樣，現(xiàn)在每個(gè)節(jié)點(diǎn)在更新所有特征時(shí)都有關(guān)于圖中所有其他節(jié)點(diǎn)的信息。

其他理論方面的工作包括 Hou 等人測量 GNN 中圖形信息的使用（https://openreview.net/forum?id=rkeIIkHKvS），以及 Srinivasan 和 Ribeiro 提出的基于角色和距離的節(jié)點(diǎn)嵌入的等價(jià)性（https://openreview.net/forum?id=SJxzFySKwH）。

2.GNN 的最新應(yīng)用

看看 GNN 如何應(yīng)用于實(shí)際任務(wù)也很棒。今年，它在 JavaScript bug 修復(fù)、玩游戲、IQ 類測試回答、優(yōu)化張量流計(jì)算圖、分子生成和對(duì)話系統(tǒng)中的問題生成都有應(yīng)用。

在 Dinella 等人的文章「HOPPITY: Learning Graph Transformations to Detect and Fix Bugs in Programs」中提出了一種在 Javascript 代碼中同時(shí)檢測和修復(fù)錯(cuò)誤的方法。代碼被轉(zhuǎn)換為抽象語法樹，然后由 GNN 對(duì)其進(jìn)行預(yù)處理，得到代碼嵌入。

該方法給出了一個(gè)處于初始狀態(tài)的圖，通過多輪圖編輯操作（添加或刪除節(jié)點(diǎn)、替換節(jié)點(diǎn)值或類型）對(duì)其進(jìn)行修改。為了理解應(yīng)該修改圖中的哪些節(jié)點(diǎn)，它們使用指針網(wǎng)絡(luò)，該網(wǎng)絡(luò)接受圖嵌入和編輯歷史并選擇節(jié)點(diǎn)。然后，使用 LSTM 網(wǎng)絡(luò)執(zhí)行修復(fù)，該網(wǎng)絡(luò)還接受圖嵌入和編輯的上下文。作者對(duì) GitHub 提交的方法進(jìn)行了驗(yàn)證，發(fā)現(xiàn)它顯示出對(duì)其他不太通用基線的顯著提升。這和 Wei 等人的文章「LambdaNet: Probabilistic Type Inference using Graph Neural Networks」類似。在這片文章中，作者提出了一種依賴超圖，它包含程序變量作為節(jié)點(diǎn)，還包含它們之間的關(guān)系，如邏輯（如布爾類型）或上下文（如相似變量名）約束。然后，首先訓(xùn)練 GNN 模型來產(chǎn)生圖的變量和可能的類型的嵌入，然后用它來預(yù)測具有最高似然的類型。在實(shí)驗(yàn)中，LambdaNet 在標(biāo)準(zhǔn)變量類型（例如 boolean）和用戶定義類型中的性能都更高。

在 Wang 等人的論文「Abstract Diagrammatic Reasoning with Multiplex Graph Networks」中，用多重圖網(wǎng)絡(luò)推理演示了如何在類智商測試中用 GNN 進(jìn)行推理。在 RPM 任務(wù)中，為矩陣的每一行組成一個(gè)圖，其中的邊嵌入是通過一個(gè)前饋模型獲得的，隨后是圖摘要。因?yàn)樽詈笠恍杏?8 個(gè)可能的答案，所以創(chuàng)建了 8 個(gè)不同的圖，每個(gè)圖都與前兩行連接起來，通過 ResNet 模型得到 IQ 分?jǐn)?shù)的預(yù)測。

圖片來源于 Wang 等人的「Abstract Diagrammatic Reasoning with Multiplex Graph Networks」

DeepMind 的一篇論文「Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs」提出了一種 RL 算法來優(yōu)化張量流計(jì)算圖的花銷。這些圖通過標(biāo)準(zhǔn)消息傳遞 GNN 進(jìn)行處理，GNN 生成與圖中每個(gè)節(jié)點(diǎn)的調(diào)度優(yōu)先級(jí)相對(duì)應(yīng)的離散化嵌入。這些嵌入被輸入到遺傳算法 BRKGA 中，BRKGA 決定每個(gè)節(jié)點(diǎn)的設(shè)備布局和調(diào)度。訓(xùn)練該模型以優(yōu)化所得到的張量流圖的實(shí)際計(jì)算成本。

圖片來自 Paliwal 等人的「Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs」

3.知識(shí)圖譜越來越流行 

今年有不少關(guān)于知識(shí)圖譜推理的論文。從本質(zhì)上講，知識(shí)圖譜是表示事實(shí)的結(jié)構(gòu)化方法。與一般圖不同，在知識(shí)圖譜中，節(jié)點(diǎn)和邊實(shí)際上具有一些含義，如演員的名字或電影中的表演（見下圖）。知識(shí)圖譜上的一個(gè)常見問題是回答復(fù)雜的問題，例如「2000 年前 Steven Spielberg 的哪部電影獲得了奧斯卡獎(jiǎng)？」可以轉(zhuǎn)換為邏輯查詢「{Win（Oscar，V）∧Directed（Spielberg，V）∧ProducedBefore（2000，V）}」。

知識(shí)圖譜示例（來源：Nickel 等人的論文）

在 Ren 等人的論文「Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings」中，建議將查詢作為矩形。此方法允許執(zhí)行自然交叉操作，因?yàn)樗鼤?huì)生成新的矩形框。但是，對(duì)并集進(jìn)行建模并不是那么簡單，因?yàn)樗赡軐?dǎo)致不重疊的區(qū)域。此外，為了精確地模擬任何嵌入的查詢，由 VC 維度測量的嵌入之間的距離函數(shù)的復(fù)雜性應(yīng)該與圖中實(shí)體的數(shù)量成正比。相反，有一個(gè)很好的技巧可以將析取查詢替換為 DNF 形式，其中聯(lián)合只發(fā)生在計(jì)算圖的末尾，這有效地減少了到每個(gè)子查詢的簡單距離計(jì)算。

圖片來源于 Ren 等人的論文「Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings」

在類似的話題中，Wang 等人在論文「Differentiable Learning of Numerical Rules in Knowledge Graphs」中，提出了一種處理數(shù)字實(shí)體和規(guī)則的方法。例如，對(duì)于引用知識(shí)圖，可以有一個(gè)規(guī)則 influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X)∧ hasCitation>(Y,Z)，它表示通常學(xué)生 X 受其主管 Z 的同事 Y 的影響，Z 有更多的引用。這個(gè)規(guī)則右邊的每一個(gè)關(guān)系都可以表示為一個(gè)矩陣，尋找缺失鏈接的過程可以表示為一個(gè)連續(xù)的矩陣乘以實(shí)體向量的關(guān)系，這個(gè)過程稱為規(guī)則學(xué)習(xí)。由于矩陣的構(gòu)造方式，神經(jīng)方法只能處理分類規(guī)則，如 collagueof（Z，Y）。作者的貢獻(xiàn)是在一種新的方法上在數(shù)值規(guī)則上有效地工作，表明在現(xiàn)實(shí)中沒有必要顯式具體化類似 hasCitation>(Y,Z) 這樣的矩陣，這大大減少了運(yùn)行時(shí)間。

另一個(gè)在機(jī)器學(xué)習(xí) GML 中更頻繁出現(xiàn)的主題是對(duì)現(xiàn)有模型的重新評(píng)估，以及它們?nèi)绾卧诠降沫h(huán)境中執(zhí)行。例如 Ruffinelli 等人的論文「You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings」表明，新模型的性能通常取決于實(shí)驗(yàn)訓(xùn)練的「次要」細(xì)節(jié)，如損失函數(shù)、正則化器和采樣方案的形式。在一項(xiàng)大型研究中，作者觀察到，像 RESCAL 模型這樣的舊方法只要適當(dāng)?shù)卣{(diào)整超參數(shù)就可以達(dá)到 SOTA 的性能。

在這個(gè)領(lǐng)域還有許多其他有趣的作品。例如  Allen 等人的文章在詞嵌入的最新見解的基礎(chǔ)上，了解更多關(guān)于關(guān)系和實(shí)體學(xué)習(xí)表示的潛在空間。Asai 等人演示了模型如何通過回答給定查詢的 Wikipedia 圖檢索推理路徑等等。

4.圖嵌入的新框架 

圖的嵌入一直是圖機(jī)器學(xué)習(xí)的一個(gè)長期課題，今年對(duì)于如何學(xué)習(xí)圖的表示有了新的觀點(diǎn)。

Deng 等人在文章「GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding」中，針對(duì)工作圖縮放中的任意無監(jiān)督嵌入方法，提出了一種提高節(jié)點(diǎn)分類問題運(yùn)行時(shí)間和分類精度的方法。其總體思路是先將原始圖縮小為一個(gè)更小的圖，這樣可以快速計(jì)算節(jié)點(diǎn)嵌入，然后恢復(fù)原始圖的嵌入。首先，基于屬性相似度，在原圖中增加與節(jié)點(diǎn) k 近鄰之間的鏈接相對(duì)應(yīng)的附加邊。然后，對(duì)圖進(jìn)行粗化：通過局部譜方法將每個(gè)節(jié)點(diǎn)投影到一個(gè)低維空間，并聚集成簇。任何無監(jiān)督的圖嵌入方法，如 DeepWalk 或 Deep graph Infomax，都可以用來獲取小圖上的節(jié)點(diǎn)嵌入。最后，使用平滑算子將得到的節(jié)點(diǎn)嵌入（本質(zhì)上表示集群的嵌入）迭代回來，以防止不同節(jié)點(diǎn)具有相同的嵌入。在實(shí)驗(yàn)中，GraphZoom 框架相比 node2vec 和 DeepWalk 方法實(shí)現(xiàn)了驚人的 40 倍加速，精度提高了 10%。

 圖片來源于 Deng 等人的論文「GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding」

有幾篇論文仔細(xì)研究了先前圖分類問題的結(jié)果。Errica 等人的論文「A Fair Comparison of Graph Neural Networks for Graph Classification」討論了 GNN 模型上的公平重新評(píng)估問題，表明不使用圖的拓?fù)浣Y(jié)構(gòu)的簡單基線（即它在聚合的節(jié)點(diǎn)特征上工作）的性能與 SOTA GNNs 相同。這一令人驚訝的現(xiàn)象顯然是由 Orlova 等人在之前發(fā)表的。它被發(fā)表于 2015 年，但沒有吸引到大量關(guān)注。這項(xiàng)工作的一個(gè)很好的結(jié)果是在流行的數(shù)據(jù)集上的公平的 SOTA 結(jié)果和 PyTorch Geometric 中方便的代碼庫，以便為將來的論文運(yùn)行模型的比較。在理解圖數(shù)據(jù)集的同構(gòu)偏差的工作中，我們還發(fā)現(xiàn)在 MUTAG 或 IMDB 等常用的數(shù)據(jù)集中，即使考慮節(jié)點(diǎn)屬性，也有許多圖具有同構(gòu)副本。此外，在這些同構(gòu)圖中，許多圖都有不同的目標(biāo)標(biāo)記，這自然會(huì)給分類器引入標(biāo)記噪聲。這表明使用網(wǎng)絡(luò)的所有可用元信息（如節(jié)點(diǎn)或邊緣屬性）對(duì)于提高模型性能的重要性。Chen 等人的另一篇文章「Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification」表明，如果用包含鄰域度和傳播圖屬性的線性鄰域聚合函數(shù)代替非線性鄰域聚合函數(shù)，則模型的性能不會(huì)降低，這與之前的說法一致，即許多圖形數(shù)據(jù)集對(duì)于分類來說都是微不足道的。文章還提出了一個(gè)關(guān)于此任務(wù)的正確驗(yàn)證框架的問題。

結(jié)論 

隨著頂級(jí)會(huì)議提交量的增長，我們可以預(yù)見到 2020 年 GML 領(lǐng)域?qū)?huì)有許多有趣的成果。我們已經(jīng)可以看到這個(gè)領(lǐng)域從圖深度學(xué)習(xí)的啟發(fā)式應(yīng)用到更合理的方法，以及關(guān)于圖模型范圍的基本問題的轉(zhuǎn)變。GNN 找到了它的位置，作為一個(gè)有效的解決許多實(shí)際問題的方法，它可以用圖表來表達(dá)，但是我希望 GML 大體上已經(jīng)觸及了我們?cè)趫D論和機(jī)器學(xué)習(xí)交叉點(diǎn)，我們應(yīng)該繼續(xù)關(guān)注即將到來的結(jié)果。

via：https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3

雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)     

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。