雖然我們才剛剛進入 2020 年，但已經可以在最新的研究論文中看到圖機器學習（Graph Machine Learning，GML）的趨勢了。本文是我對 2020 年圖機器學習的重要内容以及對有關這些論文的讨論的看法。
引言
本文寫作目的并非介紹圖機器學習的基本概念，如圖神經網絡（Graph Neural Network，GNN），而是揭示我們可以在頂級學術會議上看到的前沿研究。
在閱讀了大部分關于圖機器學習的論文之後，我整理出了 2020 年圖機器學習的趨勢，如下所列：
**對圖神經網絡将有更為紮實的理論認識；
圖神經網絡将會出現新奇炫酷的應用；
知識圖譜将會變得更加流行；
将出現用于圖嵌入的新架構。
讓我們來看看這些趨勢。**
1. 對圖神經網絡将有更為紮實的理論認識
對于這一趨勢，我感到特别興奮，因為它意味着圖機器學習領域已經成熟，以前的啟發式方法正被新的理論解決方案所取代。關于圖神經網絡的研究還有很多工作要做，但關于圖神經網絡的工作原理，已經有了一些重要的研究結果。
我将從我最喜歡的論文開始：《圖神經網絡無法學習的内容：深度與寬度》（What graph neural networks cannot learn: depth vs width）（作者：Andreas Loukas）。這篇論文在技術簡單性、高實用性和深遠的理論見解之間取得了驚人的平衡。
論文位址：
https://openreview.net/forum?id=B1l2bp4YwS- 論文表明，如果我們希望圖神經網絡能夠計算一個流行的圖問題（如循環檢測、直徑估計、頂點覆寫等等），那麼節點嵌入的維數（網絡寬度 w）乘以層數（網絡深度 d) 應與圖 n 的大小成正比，即 dw=O(n)。
結果，目前許多圖神經網絡的實作都無法滿足這一條件，因為層數（在許多實作中為 ~2-5）和嵌入次元（~100-1000）與圖的大小相比，還不夠大。另一方面，較大的網絡在目前的環境下是過于禁止的，這就引出了一個問題，即，我們應該如何設計高效的圖神經網絡？這是我們未來需要解決的問題。相當有說服力的是，這篇論文還從 20 世紀 80 年代的分布式計算模型中獲得了靈感，證明了圖神經網絡本質上也是如此。論文中還有更多的研究結果，我建議你去閱讀這篇論文。
與此類似，Oono 與 Suzuki、Barcelo 等人的另外兩篇論文也研究了圖神經網絡的威力。在第一篇論文《圖神經網絡在節點分類的表達能力呈指數級下降》（Graph Neual Networks Exponentially Lose Expressive Power for Node Classification）中，論文指出：
https://openreview.net/forum?id=S1ldO2EFPr- 在一定的權重條件下，當層數增加時，GCN 隻能學習節點度和連通分量（由拉普拉斯譜（the spectra of the Laplacian）确定），除此之外什麼也學不到。
這個結果推廣了馬爾科夫過程（Markov Processes）收斂到唯一平衡點的著名性質，其中收斂速度由轉移矩陣的特征值決定。
在第二篇論文《圖神經網絡的邏輯表達》（The Logical Expressiveness of Graph Neural Network）中，作者展示了圖神經網絡和它們可以捕獲的節點分類器類型之間的聯系。我們已經知道，一些圖神經網絡和圖同構的威斯費勒 - 萊曼（Weisfeiler-Leman，WL）算法一樣強大，也就是說，當且僅當兩個節點被圖神經網絡分類為相同時，威斯費勒 - 萊曼算法才會将它們着色為相同的顔色。但是，圖神經網絡可以捕獲其他分類函數嗎？例如，假設一個布爾函數，當且僅當一個圖有一個孤立的頂點時，該函數才會将 ture 指派給所有的節點。圖神經網絡能捕捉到這一邏輯嗎？從直覺上來看是不能，因為圖神經網絡是一種消息傳遞機制，如果圖的一部分和另一部分（兩個連接配接的元件）之間沒有連結，那麼這兩者之間将不會傳遞消息。是以，一個建議的簡單解決方案是在鄰域聚合之後添加一個讀出操作，這樣當每個節點更新所有特性時，它就擁有了關于圖中所有其他節點的資訊。
https://openreview.net/forum?id=r1lZ7AEKvB- 理論方面的其他工作包括 Hou 等人的圖神經網絡測量圖資訊的使用，以及 Srinivasan 與 Ribeiro 提出的基于角色和基于距離的節點嵌入的等價性。
2. 圖神經網絡将會出現新奇炫酷的應用
我們還可以看到圖神經網絡将如何應用于實際任務，這也是一件很棒的事情。今年的應用程式包括修複 JavaScript 中的 Bug、玩遊戲、回答類似 IQ 的測試、優化 TensorFlow 計算圖、分子生成以及對話系統中的問題生成等。
在 Dinella 等人的論文《HOPPITY：學習圖轉換來檢測和修複程式中的 Bug（HOPPITY: Learning Graph Transformations to Detect and Fix Bugs in Programs）中，提供了一種同時檢測并修複 JavaScript 代碼中 Bug 的方法。代碼被轉換為抽象文法樹，然後由圖神經網絡進行預處理以獲得代碼嵌入。這一想法是給出一個處于初始狀态的圖，通過多輪圖編輯操作符（如添加或删除節點、替換節點值或類型等）來對其進行修改。為了了解圖中的哪些節點應該被修改，他們使用了一個指針網絡，該網絡采用圖嵌入和迄今為止的編輯曆史，并選擇節點。然後，使用長短期記憶網絡（Long Short-Term Memory，LSTM）進行修複，該網絡還采用圖嵌入和編輯的上下文。作者在 GitHub 的送出上驗證了這個方法，顯示了對其他不太通用的基線的顯著提升。在精神上與 Wei 等人所做的理論工作相似：《LambdaNet：使用圖神經網絡的機率類型推斷》（LambdaNet: Probabilistic Type Inference using Graph Neural Networks）論文研究了 如何推斷 Python 或 TypeScript 等語言的變量類型。作者提出了一個類型依賴超圖，其中包含了作為節點的程式變量以及它們之間的關系，如邏輯（例如布爾類型）或上下文（例如類似的變量名）限制。然後，首先訓練圖神經網絡模型來産生圖變量和可能類型的嵌入，然後将其用于預測最有可能的類型。在實驗中，LambdaNet 在标準變量類型（如布爾類型）和用于定義類型方面表現更好。
在 Wang 等人的論文《基于多重圖網絡的抽象圖解推理》（Abstract Diagrammatic Reasoning with Multiplex Graph Networks）示範了 如何使用圖神經網絡在類似 IQ 的測試（瑞文推理測驗（Raven Progressive Matrices，RPM））和圖解三段論（Diagram Syllogism，DS）。在瑞文推理測驗任務中，為矩陣的每一行組成一個圖，其中的邊嵌入由一個前饋模型獲得，然後進行圖摘要（Graph summarization）。因為最後一行有 8 個可能的答案，是以建立了 8 個不同的圖，每個圖與前兩行連接配接起來，通過 ResNet 模型得到 IQ 得分的預測。
《基于多重圖網絡的抽象圖解推理》，Wang 等人
DeepMind 的一篇論文《用于優化計算圖的增強遺傳算法學習》（Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs）提出了 一種強化學習算法，可以優化 TensorFlow 計算圖的成本。這些圖是通過标準的消息傳遞圖神經網絡來處理的，圖神經網絡生成與圖中每個節點的排程優先級相對應的離散化嵌入。這些嵌入被輸入到一個遺傳算法 BRKGA 中，該算法決定每個節點的裝置放置和排程。通過對該模型進行訓練，優化得到的 TensorFlow 圖的實際計算成本。
《用于優化計算圖的增強遺傳算法學習》，作者：Paliwal 等人
圖神經網絡的其他有趣的應用還包括分子生成（作者：Shi 等人）、打遊戲（作者：Jiang 等人）、對話系統（作者：Chen 等人）等。
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 維（Vapnik-Chervonenkis Dimension）度量的嵌入之間的距離函數的複雜度應與圖中實體的數量成正比。取而代之的一個很好的技巧是，将一個析取式查詢替換為 DNF 形式，其中隻有在計算圖的末尾才會出現聯合，這可以有效地減少對每個子查詢的簡單舉例計算。
《Query2box：基于框嵌入的向量空間中知識圖譜的推理》，作者：Ren 等人
在類似的主題中，Wang 等人在題為《知識圖譜中數字規則的可微學習》（Differentiable Learning of Numerical Rules in Knowledge Graphs）中，提出了一種使用處理數值實體和規則的方法。例如，對于引用知識圖譜，可以有一個規則 influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X) ∧ hasCitation>(Y,Z)，它指出，學生 X 通常會受到他們的導師 Z 的同僚 Y 的影響，後者被引用的次數更多。這個規則右邊的每個關系都可以表示為一個矩陣，尋找缺失連結的過程可以通過實體向量的連續矩陣乘法，這一過程稱為規則學習（Rule Learning）。由于矩陣的構造方式，神經方法隻能在諸如 colleagueOf(z,y) 這樣的分類規則下工作。該論文作者的貢獻在于，他們提出了一種新穎的方法，通過顯示實際上無需顯式地物化這樣的矩陣，顯著地減少了運作時間，進而有效地利用 hasCitation(y,z) 和否定運算符等數值規則。
總體而言，在機器學習中以及今年在圖機器學習中出現的另一個主題，是對現有模型的重新評估，以及它們在公平環境中的表現。像這樣的論文，你可以檢視 Ruffinelli 等人的論文《你可以教會老狗新把戲！關于知識圖譜嵌入的訓練》（You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings），論文表明，新模型的性能往往取決于試驗訓練的“次要”細節，如損失函數的形式、正則化函數和采樣方案的形式。在一項大規模的消融研究中，作者觀察到，RESCAL 模型等舊方法隻要适當調整超參數，就可以實作 SOTA 性能。
在這個領域還有許多其他有趣的研究結果。Allen 等人基于對詞嵌入的最新見解，進一步了解了更多關于關系和實體的學習表征的潛在空間。Asai 等人展示了模型如何在 Wikipedia 圖譜上檢索回答給定查詢的推理路徑。Tabacof 與 Costaello 論述了圖嵌入模型的機率校準這一重要課題。他們指出，目前流行的嵌入模型 TransE 和 ComplEx，都是通過 logit 與 sigmoid 函數進行變換來獲得機率的，但這些模型的标定能力很差，即對事實的存在預測不足或預測過度。他們的方法依賴于生成被破壞的三元組作為負數，這些負數被普拉特縮放（Platt scaling）和保序回歸（Isotonic regression）等已知方法來校準機率。
4. 将出現用于圖嵌入的新架構
圖嵌入一直是圖機器學習的一個長期主題，今年我們對該如何學習圖表示有了新的觀點。
針對任何無監督嵌入方法，Deng 等人提出了一種改進節點分類問題的運作時間和正确率的方法：《GraphZoom：一種用于正确且可擴充的圖嵌入的多級譜方法》（GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding）。該論文的總體思路是：首先将原始圖縮小為更小的圖，這樣可以快速計算節點嵌入，然後恢複原始圖的嵌入。首先，根據屬性相似度，對原始圖進行擴充，增加對應于節點 K 最近鄰之間連結的附加邊。然後，對圖進行粗化：每個節點通過局部譜方法投影到低維空間，并聚內建集合。任何無監督的圖嵌入方法，如 DeepWalk 或 Deep Graph Infomax，都可以用來獲得小圖上的節點嵌入。在最後一步中，通過平滑算子疊代地廣播所獲得的節點嵌入（本質上代表集合的嵌入），以防止不同的節點具有相同的嵌入。在實驗中，GraphZoom 架構在 node2vec 和 DeepWalk 方法的基礎上實作了 40 倍加速，正确率提高了 10%。
關于圖分類問題，已有多篇論文對前人的研究成果進行了詳細的研究。Errica 等人的論文《圖神經網絡用于圖分類的公平比較》（A Fair Comparison of Graph Neural Networks for Graph Classification），在這一問題上對圖神經網絡模型的公平重新評估上做出了貢獻，表明了不利用圖的拓撲結構的簡單基線（即它在聚合節點特征上工作）的性能與 SOTA 圖神經網絡相當。這一令人驚訝的現象顯然是 Orlova 等人在 2015 年發表的，但當時并沒有吸引到大量的讀者。這項工作帶來的一個很好的結果是，在流行的資料集上公平的 SOTA 結果和友善的 PyTorch-Geometric 代碼庫，以便在将來的論文中運作模型的比較。在我們的研究論文《了解圖資料集中的同構偏差》（Understanding Isomorphism Bias in Graph Data Sets）中，我們還發現，在常用資料集（如 MUTAG 或 IMDB）中，即使考慮節點屬性，許多圖也具有同構副本。而且，在這些同構圖中，很多都具有不同的目标标簽，這自然會給分類器引入了标簽噪聲。這表明了利用網絡中所有可用的元資訊（如節點或邊屬性）對于提高模型性能的重要性。另一項研究成果——Chen 等人的論文《強大的圖神經網絡是必要的嗎？圖分類的剖析》（Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification），論文指出，如果将非線性鄰域聚合函數替換為線性鄰域聚合函數，包括鄰域的度數和傳播的圖屬性，則模型的性能并不會降低——這與之前的陳述一緻，即許多圖資料集對于分類來說都是微不足道的，并提出了一個問題，即是否有合适的驗證架構來完成這項任務。
結 語
随着頂會的論文送出率的增長，我們可以預計，2020 年圖機器學習領域将會湧現許多有趣的結果。我們已經目睹這一領域的轉變，從圖的深度學習的啟發式應用，到更合理的方法和關于圖波形範圍的基本問題。圖神經網絡找到了它的位置，作為一個有效的解決許多實際問題的方法，這些問題可以用圖來表達，但我認為，總體而言，圖機器學習隻不過是觸及了我們可以實作的圖論和機器學習的交叉點上所能取得的成果的皮毛，我們應該繼續關注即将到來的結果。
原文連結：
https://www.infoq.cn/article/YaapLQEtEHQR0og9WBFv https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3