2020 年，圖機器學習的趨勢有哪些

• 2020 年 2 月 21 日
• 筆記

前 言

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

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

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

• 對 GNN 更紮實的理論理解
• GNN 的最新應用
• 知識圖譜越來越流行
• 圖嵌入的新框架

讓我們看看這些趨勢。

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

我特別高興地看到這一趨勢，因為它表明 GML 領域已經成熟，以前的啟發式方法正在被新的理論解決方案所取代。關於圖神經網路還有很多需要了解的地方，但是關於 GNNs 是如何工作的已經有很多重要的結果。

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

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

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

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

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

這個結果推廣了 Markov 過程收斂到唯一平衡點這一眾所周知的性質，其中收斂速度由轉移矩陣的特徵值決定。

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

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

2.GNN 的最新應用

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

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

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

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

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

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

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

3.知識圖譜越來越流行

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

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

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

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

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

另一個在機器學習 GML 中更頻繁出現的主題是對現有模型的重新評估，以及它們如何在公平的環境中執行。例如 Ruffinelli 等人的論文「You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings」表明，新模型的性能通常取決於實驗訓練的「次要」細節，如損失函數、正則化器和取樣方案的形式。在一項大型研究中，作者觀察到，像 RESCAL 模型這樣的舊方法只要適當地調整超參數就可以達到 SOTA 的性能。

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

4.圖嵌入的新框架

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

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

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

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

結 論

隨著頂級會議提交量的增長，我們可以預見到 2020 年 GML 領域將會有許多有趣的成果。我們已經可以看到這個領域從圖深度學習的啟發式應用到更合理的方法，以及關於圖模型範圍的基本問題的轉變。GNN 找到了它的位置，作為一個有效的解決許多實際問題的方法，它可以用圖表來表達，但是我希望 GML 大體上已經觸及了我們在圖論和機器學習交叉點，我們應該繼續關注即將到來的結果。

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