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

前言

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

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

我閱讀了大部分 GML 論文，以下是我對 2020 年趨勢的認知： 

• 對 GNN 更扎實的理論理解

• GNN 的最新應用

• 知識圖譜越來越流行 

• 圖嵌入的新框架

讓我們看看這些趨勢。

1.對 GNN 更扎實的理論理解

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

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

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

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

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

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

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

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

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

2.GNN 的最新應用

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

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

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

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

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

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

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

3.知識圖譜越來越流行 

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

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

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

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

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

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

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

4.圖嵌入的新框架 

圖的嵌入一直是圖機器學習的一個長期課題，今年對于如何學習圖的表示有了新的觀點。

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

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

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

結(jié)論 

隨著頂級會議提交量的增長，我們可以預見到 2020 年 GML 領(lǐng)域?qū)性S多有趣的成果。我們已經(jīng)可以看到這個領(lǐng)域從圖深度學習的啟發(fā)式應用到更合理的方法，以及關(guān)于圖模型范圍的基本問題的轉(zhuǎn)變。GNN 找到了它的位置，作為一個有效的解決許多實際問題的方法，它可以用圖表來表達，但是我希望 GML 大體上已經(jī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)載須知。