[[314165]]

本文轉自雷鋒網，如需轉載請至雷鋒網官網申請授權。

2019年絕對是圖機器學習（GML）大火的一年，凡是學術會議，圖神經網絡的會場總會爆滿。 

圖機器學習的研究之所以在2019年突然變得火熱，原因在于，在前幾年盡管深度學習在歐氏空間中的數據方面取得了巨大的成功，但在許多實際的應用場景中的數據往往是從非歐式空間生成的。 

正如阿里達摩院曾在2019年所提：“單純的深度學習已經成熟，而結合了深度學習的圖研究將端到端學習與歸納推理相結合，有望解決深度學習無法處理的關系推理、可解釋性等一系列問題。” 

在過去的一年里，圖機器學習經過了蓬勃的發展，這從各大頂會中圖機器學習的火爆場面也可以看出。 

而新的一年已經過去了一個月，那么2020年圖機器學習的火熱還能持續嗎？又將有哪些新的研究趨勢呢？ 即將于4月份在埃塞俄比亞舉辦的ICLR 2020是一個能夠很好反映這些問題的會議。

這個會議是由深度學習三巨頭之二的 Yoshua Bengio 和 Yann LeCun 牽頭創辦，旨在關注有關深度學習各個方面的前沿研究。

在ICLR 2020中共有150篇投稿與圖機器學習有關，而其中有近1/3的論文都被錄用了，這也說明圖機器學習火熱依舊。

我們不妨將這些論文按照理論、應用、知識圖譜、圖嵌入來劃分，從而一窺圖機器學習在2020年的研究趨勢。

注：文中涉及論文，可關注雷鋒網「AI科技評論」微信公眾號，并后臺回復「2020年GML趨勢」下載。

1、GNN理論知識會更加扎實

從目前的形式看，圖機器學習的領域在成熟的康莊大道上越走越遠，但是圖神經網絡還有很多進步空間。過去的一年圖神經網絡不斷改進，因此誕生了許多理論研究，在我們對2020年預測之前，先來簡單梳理一下圖神經網絡的重要理論成果吧！

What graph neural networks cannot learn: depth vs width

https://openreview.net/forum?id=B1l2bp4YwS

洛桑聯邦理工學院 Andreas Loukas 的這篇論文，無論在影響力、簡潔性還是對理論理解的深度上，無疑是論文中的典范。 

它表明，當我們用GNN計算通常的圖問題時，節點嵌入的維數（網絡的寬度，w）乘以層數（網絡的深度，d）應該與圖n的大小成正比，即dW=O(n)。 

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

這篇文章還包含有大量有價值的結論，強烈建議去閱讀原文。可關注雷鋒網(公眾號：雷鋒網)「AI科技評論」微信公眾號，后臺回復「2020年GML趨勢」下載論文。 

同樣，在另外兩篇論文中，Oono等人研究了GNN的能力。第一篇文章是《圖神經網絡在節點分類中失去了表達能力》，第二篇文章是《圖神經網絡的邏輯表達》。

Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

https://openreview.net/forum?id=S1ldO2EFPr

這篇論文表明：“在已知某些條件下的權重，當層數增加時，GCN除了節點度和連通分量以外，將無法學習其他任何內容。”這一結果擴展了“馬爾可夫過程收斂到唯一平衡點”的性質，并表明其中收斂速度由轉移矩陣的特征值決定。

The Logical Expressiveness of Graph Neural Networks 

https://openreview.net/pdf?id=r1lZ7AEKvB

這篇論文展示了GNN與節點分類器類型之間的聯系。在這之前，我們已經了解GNN與WL同構檢驗一樣強大。但是GNN可以獲得其他分類功能么？直觀上不行，因為GNN是一種消息傳遞機制，如果圖的一個部分和另一個部分之間沒有鏈接，那么兩者之間就不會傳遞消息。

因此論文提出一個簡單解決方案：在鄰域聚合之后添加一個讀出操作，以便每個節點在更新所有要素時與圖中所有其他節點都有聯系。 

其他在理論上的工作還有很多，包括Hou等人測量GNN的圖形信息的使用。以及 Srinivasan 和 Ribeiro提出的基于角色的節點嵌入和基于距離的節點嵌入的等價性討論。

論文鏈接如下：

Measuring and Improving the Use of Graph Information in Graph Neural Networks

https://openreview.net/forum?id=rkeIIkHKvS

On the Equivalence between Positional Node Embeddings and Structural Graph Representationshttps://openreview.net/forum?id=SJxzFySKwH

2、新酷應用不斷涌現

在過去的一年中，GNN已經在一些實際任務中進行了應用。例如已經有一些程序應用于玩游戲、回答智商測試、優化TensorFlow計算圖形、分子生成以及對話系統中的問題生成。

HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS

https://openreview.net/pdf?id=SJeqs6EFvB

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

LambdaNet: Probabilistic Type Inference using Graph Neural Networks

https://openreview.net/pdf?id=Hkx6hANtwH 

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

Abstract Diagrammatic Reasoning with Multiplex Graph Networks

https://openreview.net/pdf?id=ByxQB1BKwH

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

來自：https://openreview.net/pdf?id=ByxQB1BKwH 

Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs

https://openreview.net/pdf?id=rkxDoJBYPBDeepMind

在上面的論文中提出了一種RL算法來優化TensorFlow計算圖的開銷。先通過標準GNN對圖形進行處理，然后產生與圖中每個節點的調度優先級相對應的離散化嵌入，最后將嵌入被饋送到遺傳算法BRKGA中進行模型訓練，從而優化得到的TensorFlow圖的實際計算開銷。值得注意的是該遺傳算法決定每個節點的布局和調度。

類似的炫酷應用還有Chence Shi的分子結構生成和Jiechuan Jiang玩游戲以及Yu Chen的玩游戲等等。

論文鏈接如下：Graph Convolutional Reinforcement Learning

https://openreview.net/forum?id=HkxdQkSYDB

Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation

https://openreview.net/forum?id=HygnDhEtvr

3、知識圖譜將更加流行

在今年的ICLR會議上，有很多關于知識圖譜推理的論文。  

知識圖譜例子（來源：https://arxiv.org/abs/1503.00759） 

從本質上講，知識圖譜是一種結構化的表示事實的方式。與一般的圖不同，知識圖譜的節點和邊實際上具有一定的含義，例如演員的名字、電影名等。知識圖譜中一個常見的問題是，如何回答一些復雜問題，例如“斯皮爾伯格哪些電影在2000年之前贏得了奧斯卡獎？”，這個問題翻譯成邏輯查詢語言則是：
∨ {Win(Oscar, V) ∧ Directed(Spielberg, V) ∧ProducedBefore(2000, V) }  Query2box: 

Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings 

https://openreview.net/forum?id=BJgr4kSFDS

Query2Box 推理框架 在斯坦福大學Hongyu Ren等人的工作中，他們建議將query嵌入到隱空間當中，而不是作為單個的點（作為矩形框）。 

QUERY2BOX的兩種操作及距離函數的幾何示例 這種方法使得可以自然地執行 交 操作（即合取 ∧），得到一個新的矩形框。但是對于 并 操作（即析取 ∨）卻并不那么簡單，因為它可能會產生非重疊區域。

此外，要使用嵌入來對所有query進行精確建模，嵌入之間的距離函數（通過VC維度進行度量）的復雜性會與圖譜中實體的數量成正比。

不過有一個不錯的技巧可以將析取（ ∨）query轉換為DNF形式，這時候只有在圖計算的最后才會進行 并 操作，這能夠有效減少每個子查詢的距離計算。

Differentiable Learning of Numerical Rules in Knowledge Graphs

https://openreview.net/forum?id=rJleKgrKwSCMU的Po-Wei 

Wang等人在類似主題的一篇文章提出了一種處理數字實體和規則的方法。

引用知識圖譜（Citation KG）示例 舉例來說，以引用知識圖譜（Citation KG），可以有一條規則： influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X)∧ hasCitation>(Y,Z)  這是一個典型的情況，即學生X受到其導師Z的同事Y（Y有較高的引用率）的影響。 

這個規則右邊的每個關系都可以表示為一個矩陣，而尋找缺失連接（missing links）的過程可以表示為關系與實體向量的連續矩陣乘積，這個過程稱為規則學習。由于矩陣的構造方式，神經網絡的方法只能在分類規則colleagueOf(Z,Y)下工作。 

作者的貢獻在于，他們通過一種新穎的方法證明了，在實際中并不需要顯式地表示這些矩陣，從而有效地處理了類似hasCitation>(Y,Z)、求反運算這樣的數字規則，這大大降低了運行時間。

You CAN Teach an Old Dog New Tricks! 

On Training Knowledge Graph Embeddingshttps://openreview.net/forum?id=BkxSmlBFvr 

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

上面這篇文章即是其中一個，他們的研究表明，新模型的性能往往取決于試驗訓練中的“次要”細節，例如損失函數的形式、正則器、采樣的方案等。

在他們進行的大型消融研究中，作者觀察到將舊的方法（例如RESCAL模型）的超參數進行適當調整就可以獲得SOTA性能。 當然在這個領域還有許多其他有趣的工作，Allen et al. 基于對詞嵌入的最新研究，進一步探究了關系與實體的學習表示的隱空間。Asai et al. 則展示了模型如何在回答給定query的Wikipedia圖譜上檢索推理路徑。

Tabacof 和 Costabello 討論了圖嵌入模型的概率標定中的一個重要問題，他們指出，目前流行的嵌入模型TransE 和ComplEx（通過將logit函數轉換成sigmoid函數來獲得概率）均存在誤校，即對事實的存在預測不足或預測過度。

論文鏈接如下：On Understanding Knowledge Graph Representation

https://openreview.net/forum?id=SygcSlHFvS

Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering

https://openreview.net/forum?id=SJgVHkrYDH

Probability Calibration for Knowledge Graph Embedding Models

https://openreview.net/forum?id=S1g8K1BFwS

4、圖嵌入的新框架

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

GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding

https://openreview.net/forum?id=r1lGO0EKDH

康奈爾的Chenhui Deng等人提出了一種改善運行時間和準確率的方法，可以應用到任何無監督嵌入方法的節點分類問題。 這篇文章的總體思路是，首先將原始圖簡化為更小的圖，這樣可以快速計算節點嵌入，然后再回復原始圖的嵌入。

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

A Fair Comparison of Graph Neural Networks for Graph Classification 

https://openreview.net/forum?id=HygDF6NFPB

已有多篇論文對圖分類問題的研究成果進行了詳細的分析。比薩大學的Federico Errica 等人在圖分類問題上，對GNN模型進行了重新評估。

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

Understanding Isomorphism Bias in Graph Data Sets

https://openreview.net/forum?id=rJlUhhVYvSSkolkovo 

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

Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification 

https://openreview.net/forum?id=BJxQxeBYwH

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