本文寫作目的并非介紹圖機器學習的基本概念，如圖神經網絡（Graph Neural Network，GNN），而是揭示我們可以在頂級學術會議上看到的前沿研究。首先，我把在圖機器學習的研究成果的論文提交到 ICLR 2020闡述了GNN的論文情況。

有 150 篇論文涉及圖機器學習，其中三分之一的論文已被接受。這大約相當于所有被接受論文的 10%。

在閱讀了大部分關于圖機器學習的論文之后，我整理出了 2020 年圖機器學習的趨勢，如下所列：

對圖神經網絡將有更深入的理論理解；

圖神經網絡將會有更酷的應用；

知識圖譜將會變得更為流行；

新的圖嵌入框架將出現。

讓我們來看看這些趨勢。

1. 圖神經網絡的理論理解

從目前發展趨勢看，圖機器學習的領域在進展迅速，但是圖神經網絡還有很多工作要做。但關于圖神經網絡的工作原理，已經有了一些重要的研究結果！

洛桑聯邦理工學院 Andreas Loukas 的這篇論文《What graph neural networks cannot learn： depth vs width》，無論在影響力、簡潔性還是對理論理解的深度上，無疑是論文中的代表作。

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

但現實是當前的GNN的許多實現都無法達到此條件，因為層數和嵌入的尺寸與圖的大小相比還不夠大。另一方面，較大的網絡在實際操作中不合適的，這會引發有關如何設計有效的GNN的問題，當然這個問題也是研究人員未來工作的重點。需要說明的是，這篇論文還從80年代的分布式計算模型中汲取了靈感，證明了GNN本質上是在做同樣的事情。

與此類似，Oono 與 Suzuki、Barcelo 等人的另外兩篇論文也研究了圖神經網絡的威力。在第一篇論文《圖神經網絡在節點分類的表達能力呈指數級下降》（Graph Neual Networks Exponentially Lose Expressive Power for Node Classification）中，論文指出：

在一定的權重條件下，當層數增加時，GCN 只能學習節點度和連通分量（由拉普拉斯譜（the spectra of the Laplacian）確定），除此之外什么也學不到。

這個結果推廣了馬爾科夫過程（Markov Processes）收斂到唯一平衡點的著名性質，其中收斂速度由轉移矩陣的特征值決定。

在第二篇論文《圖神經網絡的邏輯表達》（The Logical Expressiveness of Graph Neural Network）中，作者展示了**圖神經網絡和它們可以捕獲的節點分類器類型之間的聯系。**我們已經知道，一些圖神經網絡和圖同構的威斯費勒 - 萊曼（Weisfeiler-Leman，WL）算法一樣強大，也就是說，當且僅當兩個節點被圖神經網絡分類為相同時，威斯費勒 - 萊曼算法才會將它們著色為相同的顏色。但是，圖神經網絡可以捕獲其他分類函數嗎？例如，假設一個布爾函數，當且僅當一個圖有一個孤立的頂點時，該函數才會將 ture 賦值給所有的節點。圖神經網絡能捕捉到這一邏輯嗎？從直觀上來看是不能，因為圖神經網絡是一種消息傳遞機制，如果圖的一部分和另一部分（兩個連接的組件）之間沒有鏈接，那么這兩者之間將不會傳遞消息。因此，一個建議的簡單解決方案是在鄰域聚合之后添加一個讀出操作，這樣當每個節點更新所有特性時，它就擁有了關于圖中所有其他節點的信息。

理論方面的其他工作包括 Hou 等人的圖神經網絡測量圖信息的使用，以及 Srinivasan 與 Ribeiro 提出的基于角色和基于距離的節點嵌入的等價性。

2. 圖神經網絡的更多應用

在過去的一年中，GNN已經在一些實際任務中進行了應用。包括修復 JavaScript 中的 Bug、玩游戲、回答類似 IQ 的測試、優化 TensorFlow 計算圖、分子生成以及對話系統中的問題生成。

在論文中，作者其提出了一種在Javascript代碼中同時檢測和修復錯誤的方法（HOPPITY： LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS）。具體操作是將代碼轉換為抽象語法樹，然后讓GNN進行預處理以便獲得代碼嵌入，再通過多輪圖形編輯運算符（添加或刪除節點，替換節點值或類型）對其進行修改。為了理解圖形的哪些節點應該修改，論文作者使用了一個指針網絡（Pointer network），該網絡采用了圖形嵌入來選擇節點，以便使用LSTM網絡進行修復。當然，LSTM網絡也接受圖形嵌入和上下文編輯。

類似的應用還體現在上面這篇論文中《LambdaNet： Probabilistic Type Inference using Graph Neural Networks》。來自得克薩斯大學奧斯汀分校的作者研究了如何推斷像Python或TypeScript此類語言的變量類型。更為具體的，作者給出了一個類型依賴超圖（type dependency hypergraph），包含了程序作為節點的變量以及它們之間的關系，如邏輯關系、上下文約束等；然后訓練一個GNN模型來為圖和可能的類型變量產生嵌入，并結合似然率進行預測。

在智商測試類的應用中，上面這篇論文《Abstract Diagrammatic Reasoning with Multiplex Graph Networks》展示了GNN如何進行IQ類測試，例如瑞文測驗（RPM）和圖三段論（DS）。具體的在RPM任務中，矩陣的每一行組成一個圖形，通過前饋模型為其獲取邊緣嵌入，然后進行圖形匯總。由于最后一行有8個可能的答案，因此將創建8個不同的圖，并將每個圖與前兩行連接起來，以通過ResNet模型預測IQ得分。如下圖所示：

DeepMind 的一篇論文《用于優化計算圖的增強遺傳算法學習》（Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs）提出了**一種強化學習算法，可以優化 TensorFlow 計算圖的成本。**這些圖是通過標準的消息傳遞圖神經網絡來處理的，圖神經網絡生成與圖中每個節點的調度優先級相對應的離散化嵌入。這些嵌入被輸入到一個遺傳算法 BRKGA 中，該算法決定每個節點的設備放置和調度。通過對該模型進行訓練，優化得到的 TensorFlow 圖的實際計算成本。

類似的炫酷應用還有Chence Shi的分子結構生成《Graph Convolutional Reinforcement Learning》和Jiechuan Jiang玩游戲以及Yu Chen的玩游戲等等《Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation》。

3. 知識圖譜將會變得更為流行

在ICLR2020會議上，有很多關于知識圖譜推理的論文。從本質上講，知識圖譜是一種表示事實的結構化方法。與一般的圖不同，知識圖譜中的節點和邊實際上具有某種意義，例如，演員的名字或在電影中的表演（見下圖）。知識圖譜的一個常見問題是回答一些復雜的查詢，例如“在 2000 年前，Steven Spielberg 的哪些電影獲得了奧斯卡獎？”可以將其轉換成邏輯查詢 ∨ {Win（Oscar， V） ∧ Directed（Spielberg， V） ∧ ProducedBefore（2000， V） }。

知識圖譜例子

在 斯坦福大學Ren 等人的論文《Query2box：基于框嵌入的向量空間中知識圖譜的推理》（Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings）中，作者建議 將查詢嵌入到潛在空間中作為矩形框形式，而不是作為單點形式。這種方法允許執行自然的相交操作，即合取 ∧，因為它會產生新的矩形框。但是，對聯合（即析取 ∨）進行建模并不是那么簡單，因為它可能會導致不重疊的區域。此外，為了精確建模任何帶有嵌入的查詢，用 VC 維（Vapnik-Chervonenkis Dimension）度量的嵌入之間的距離函數的復雜度應與圖中實體的數量成正比。取而代之的一個很好的技巧是，將一個析取式查詢替換為 DNF 形式，其中只有在計算圖的末尾才會出現聯合，這可以有效地減少對每個子查詢的簡單舉例計算。

Query2Box 推理框架

在類似的主題中，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） 和否定運算符等數值規則。

引用知識圖譜（Citation KG）示例

在今年的圖神經網絡（或者說機器學習）中經常出現的一個研究方向是：對現有模型的重新評估，以及在一個公平環境中進行測評。

上面這篇文章即是其中一個，他們的研究表明，新模型的性能往往取決于試驗訓練中的“次要”細節，例如損失函數的形式、正則器、采樣的方案等。在他們進行的大型消融研究中，作者觀察到將舊的方法（例如RESCAL模型）的超參數進行適當調整就可以獲得SOTA性能。

當然在這個領域還有許多其他有趣的工作，Allen et al. 基于對詞嵌入的最新研究，進一步探究了關系與實體的學習表示的隱空間。Asai et al. 則展示了模型如何在回答給定query的Wikipedia圖譜上檢索推理路徑。Tabacof 和 Costabello 討論了圖嵌入模型的概率標定中的一個重要問題，他們指出，目前流行的嵌入模型TransE 和ComplEx（通過將logit函數轉換成sigmoid函數來獲得概率）均存在誤校，即對事實的存在預測不足或預測過度。

4. 新的圖嵌入框架將出現

圖嵌入是圖機器學習的一個長期的研究主題，今年有一些關于我們應該如何學習圖表示的新觀點出現。

康奈爾的Chenhui Deng等人的《GraphZoom： A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》提出了一種改善運行時間和準確率的方法，可以應用到任何無監督嵌入方法的節點分類問題。

這篇文章的總體思路是，首先將原始圖簡化為更小的圖，這樣可以快速計算節點嵌入，然后再回復原始圖的嵌入。

最初，根據屬性相似度，對原始圖進行額外的邊擴充，這些便對應于節點的k近鄰之間的鏈接。隨后對圖進行粗化：通過局部譜方法將每個節點投影到低維空間中，并聚合成簇。任何無監督的圖嵌入方法（例如DeepWalk、Deep Graph Infomax）都可以在小圖上獲得節點嵌入。在最后一步，得到的節點嵌入（本質上表示簇的嵌入）用平滑操作符迭代地進行廣播，從而防止不同節點具有相同的嵌入。在實驗中，GraphZoom框架相比node2vec和DeepWalk，實現了驚人的 40 倍的加速，準確率也提高了 10%。

已有多篇論文對圖分類問題的研究成果進行了詳細的分析。比薩大學的Federico Errica 等人提出《**A Fair Comparison of Graph Neural Networks for Graph Classification **》在圖分類問題上，對GNN模型進行了重新評估。

他們的研究表明，一個不利用圖的拓撲結構（僅適用聚合節點特征）的簡單基線能獲得與SOTA GNN差不多的性能。事實上，這個讓人驚訝的發現，Orlova等人在2015年就已經發表了，但沒有引起大家的廣泛關注。

Skolkovo 科學技術研究院的Ivanov Sergey等人在《Understanding Isomorphism Bias in Graph Data Sets》研究中發現，在MUTAG和IMDB等常用數據集中，即使考慮節點屬性，很多圖也都會具有同構副本。而且，在這些同構圖中，很多都有不同的target標簽，這自然會給分類器引入標簽噪聲。這表明，利用網絡中所有可用的元信息（如節點或邊屬性）來提高模型性能是非常重要的。

另外還有一項工作是UCLA孫怡舟團隊的工作《**Are Powerful Graph Neural Nets Necessary？ A Dissection on Graph Classification **》。這項工作顯示如果用一個線性近鄰聚合函數取代原有的非線性近鄰聚合函數，模型的性能并不會下降。這與之前大家普遍認為“圖數據集對分類的影響并不大”的觀點是相反的。同時這項工作也引發一個問題，即如何為此類任務找到一個合適的驗證框架。

結論

隨著頂會的論文提交量的增長，我們可以預計，2020 年圖機器學習領域將會涌現許多有趣的成果。我們已經目睹這一領域的轉變，從圖的深度學習的啟發式應用，到更合理的方法和關于圖波形范圍的基本問題。圖神經網絡找到了它的位置，作為一個有效的解決許多實際問題的方法，這些問題可以用圖來表達，但我認為，總體而言，圖機器學習只不過是觸及了我們可以實現的圖論和機器學習的交叉點上所能取得的成果的皮毛，我們應該繼續關注即將到來的結果。