導讀

2020年才剛剛開始，但我們已經在最新的研究論文中看到了圖機器學習(GML)的趨勢。以下是我對2020年GML的重要內容的看法以及對這些論文的討論。

[[314620]]

介紹

本文的目標不是介紹GML的基本概念，如圖神經網絡(GNNs)，而是介紹我們在頂級科學會議上看到的前沿研究。

在GML領域有150篇論文提交，有三分之一的論文被接受。這大約相當于所有被接受論文的10%。

我讀了大部分GML的論文，以下是我列出的2020年的趨勢：

1. 對GNN有更扎實的理論認識;
2. 最新最酷的GNN應用;
3. 知識圖譜在變得越來越流行;
4. 圖嵌入的新框架

我們一個一個來看。

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

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

我將從我最喜歡的一篇文章開始：What graph neural networks cannot learn: depth vs width。這篇論文在技術的簡單性、很高的實際影響和深遠的理論見解之間取得了驚人的平衡。

它表明節點嵌入的維度(網絡的寬度，w)乘以層數(網絡的深度，d)應該與圖的大小n成比例，即dw = O(n)，如果我們希望GNN能夠計算出流行的圖問題的解決方案(如周期檢測、直徑估計、頂點覆蓋等)。

因此，由于層的數量(在許多實現中約為2-5層)和嵌入的維度(約為100-1000層)與圖的大小相比不夠大，許多當前的GNN實現無法實現這一條件。另一方面，在目前的環境下，太大的網絡計算存儲代價過高，這就提出了一個問題：我們應該如何設計“高效”的GNN，這是我們將來需要解決的問題。這篇論文還從80年代的分布式計算模型中得到了啟發，證明了GNNs本質上也做了同樣的事情。里面有更多的結果，所以我建議你去看看。

類似地，另外兩篇論文Oono & Suzuki和Barcelo等人也研究了GNNs的威力。第一個是Graph Neural Networks loss expression Power for Node Classification，表明：

在一定的權值條件下，當層數增加時，GCNs除了節點度和連通分量(由拉普拉斯頻譜確定)外，什么也學不到。

這個結果是一個眾所周知的性質的推廣，即馬爾科夫過程收斂于唯一的均衡，其中收斂率是由轉移矩陣的特征值決定的。

在第二篇論文The Logical Expressiveness of Graph Neural Networks中，作者展示了GNNs與它們所能捕獲的節點分類器類型之間的聯系。我們已經知道，一些GNN具有與WL同構檢驗同樣強大的能力，即當且僅當兩個節點被GNNs分類相同時，它們被WL著色相同。但是GNN可以捕獲其他分類函數嗎?例如，假設一個布爾函數，當且僅當一個圖有一個孤立的頂點時，才將true賦值給所有節點。GNNs能夠捕獲這種邏輯嗎?從直覺上說不是，因為GNN是一種消息傳遞機制，如果圖的一個部分與另一個部分(兩個連接的組件)之間沒有鏈接，那么這兩個部分之間就不會傳遞消息。因此，一個推薦的簡單修復方法是在鄰居聚合之后添加一個讀出操作，以便在更新所有特征時每個節點都擁有圖中所有其他節點的信息。

其他理論方面的工作包括Hou等人對GNN圖形信息的使用進行度量，以及Srinivasan & Ribeiro對基于角色和基于距離的節點嵌入的等價性進行度量。

2. GNN的新酷應用

還很高興看到如何將GNN應用于實際任務。今年的應用程序包括修復Javascript中的bug、玩游戲、回答類似IQ的測試、TensorFlow計算圖的優化、分子生成和對話系統中的問題生成。

在HOPPITY: Learning Graph transform to Detect and Fix Bugs In Programs中。將代碼轉換為一個抽象語法樹，然后GNN對其進行預處理以獲得代碼嵌入。該思想給出一個處于初始狀態的圖形，通過多輪圖形編輯操作符(添加或刪除節點，替換節點值或類型)對其進行修改。為了了解應該修改圖的哪些節點，他們使用了一個指針網絡，該網絡接受圖的嵌入和到目前為止的編輯歷史，并選擇節點。然后，使用LSTM網絡執行修復，該網絡也獲取圖嵌入和編輯的上下文。作者在GitHub的提交上驗證了這個方法，顯示了對其他不太通用的基線的顯著提升。類似地，Wei等人的工作LambdaNet: Probabilistic Type Inference using Graph Neural Networks。作者提出了一個類型依賴超圖，其中包含作為節點的程序變量和它們之間的關系，如邏輯(如布爾類型)或上下文(如類似的變量名)約束。然后，首先訓練一個GNN模型來生成圖變量和可能的類型的嵌入，然后使用這些嵌入來預測最有可能的類型。在實驗中，LambdaNet在標準變量類型(例如布爾型)和用戶定義類型中都表現得更好。

Wang等人的一篇論文Abstract Diagrammatic Reasoning with Multiplex Graph Networks展示了如何使用GNNs在類IQ測試中進行推理(Raven Progressive Matrices (RPM)和Diagram Syllogism (DS))。在RPM任務中，為矩陣的每一行組成一個圖，其中的邊嵌入由一個前饋模型獲得，然后是一個圖形摘要。因為最后一行有8個可能的答案，所以創建了8個不同的圖，每個圖與前兩行連接起來，通過ResNet模型預測IQ分數。

DeepMind的一篇論文Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs提出了一種RL算法用來優化TensorFlow計算圖的計算代價。圖通過標準的消息傳遞GNN進行處理，該GNN產生的離散嵌入對應于圖中每個節點的調度優先級。這些嵌入被輸入到一個遺傳算法BRKGA中，BRKGA決定每個節點的設備放置和調度。通過對模型的訓練，優化得到的TensorFlow圖的實際計算代價。

GNN的其他有趣應用包括Shi等人的分子生成、Jiang等人的游戲和Chen等人 的對話系統。

3. 知識圖譜變得越來越流行

今年有不少關于知識圖譜推理的論文。本質上，知識圖譜是表示事實的結構化的方法。與一般的圖不同的是，在知識圖譜中節點和邊實際上具有一些含義，例如演員的名字或電影中的演員(見下圖)。知識圖譜上一個常見的問題是回答一些復雜的問題，比如“史蒂芬·斯皮爾伯格的哪些電影在2000年之前獲得了奧斯卡獎?”，這可以翻譯成一個邏輯查詢{Win(Oscar, V)∧Directed(Spielberg, V)∧ProducedBefore(2000, V)}}。

Ren等人的論文Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings。這種方法允許執行自然的相交操作，即∧連詞，因為它有一個新的矩形框結構。然而，建立一個聯合，即分離，并不是那么簡單，因為它可能導致不重疊的區域。而且，為了準確地使用嵌入建模任何查詢，用VC維度量的嵌入之間距離函數的復雜性應該與圖中實體的數量成比例。相反，有一個很好的技巧可以將析取查詢替換為DNF形式，其中union只發生在計算圖的末尾，這可以有效地簡化為每個子查詢的簡單距離計算。

在相同的主題上，王等人提出一種使用數值實體和規則的論文 “Differentiable Learning of Numerical Rules in Knowledge Graphs” *。*例如，知識圖譜的引用，你可以有一個規則，influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X)∧ hasCitation>(Y,Z) ，即學生X是通過同一個導師Z的同學 Y 影響到的，這個Z具有更多的引用。該規則右手邊的每個關系都可以表示為一個矩陣，而尋找缺失鏈接的過程可以表示為關系與實體向量的連續矩陣乘法，這個過程稱為規則學習。由于矩陣的構造方式，神經方法只能在諸如colleagueOf(Z,Y)這樣的分類規則下工作。作者的貢獻是一種新穎的方式來有效地工作與數字規則，如hasCitation>(Y,Z)和否定運算符，表明在現實中沒有必要顯式物化這樣的矩陣，這大大減少了運行時間。

另一個在機器學習中經常出現的主題是，在今年的GML中，重新評估現有的模型，以及它們在公平的環境中如何表現。就像這篇論文：Ruffinelli等人的You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings表明，新模型的性能往往取決于實驗訓練的“次要”細節，如損失函數的形式、正則化器和采樣方案。在一項大型的消融研究中，作者觀察到舊的方法，如RESCAL模型，僅通過適當調整超參數就可以獲得SOTA性能。

在這個領域還有許多其他有趣的文章。Allen等人展示了模型如何在回答給定查詢的Wikipedia圖上檢索推理路徑。Tabacof & Costabello涉及了圖嵌入模型的概率校準這一重要課題。他們指出，目前流行的利用s形函數轉換對數來獲得概率的嵌入模型TransE和ComplEx均校準不足，即對事實的存在預測不足或預測過度。他們的方法依賴于生成不好的三元組作為負樣本，而已知的方法如Platt縮放法和isotonic回歸法則使用這些負樣本來校準概率。

4. 圖嵌入的新框架

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

Deng等人在GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding的總體思路是首先將原始圖簡化為更小的圖，這樣可以快速計算節點嵌入，然后恢復原始圖的嵌入。首先，根據屬性相似度，對原始圖進行額外的邊擴充，這些邊對應于節點的k近鄰之間的鏈接。然后，對圖進行粗化：通過局部譜方法將每個節點投影到低維空間中，并聚合成簇。任何無監督的圖嵌入方法，如深度步或深度圖信息挖掘，都可以在小圖上獲得節點嵌入。在最后一步中，得到的節點嵌入(本質上表示集群的嵌入)用平滑操作符迭代地廣播回來，以防止不同節點具有相同的嵌入。在實驗中，GraphZoom框架在node2vec和DeepWalk方法的基礎上實現了驚人的40倍加速，準確率提高了10%。

已有多篇論文對圖分類問題的研究成果進行了詳細的分析。Errica等人的A Fair Comparison of Graph Neural Networks for Graph Classification 的貢獻在于GNN模型在這個問題上的公正的重新評估，文章給出了一個簡單的基線，不利用圖的拓撲結構(它用戶節點特征聚合)的表現可以與SOTA的GNNs相當。這一令人驚訝的現象很顯然由Orlova等人在在2015年之前發表，但并沒有獲得大量的讀者。這項工作的一個很好的結果是在流行數據集上和在PyTorch-Geometric上的代碼基準上的得到了公平的SOTA。在我們的工作 Understanding Isomorphism Bias in Graph Data Sets中，我們發現在常用的數據集如MUTAG和IMDB上，很多圖具有同構的副本，即便考慮到節點的屬性。此外，在這些同構圖中，有許多不同的目標標簽，這自然為分類器引入了標簽噪聲。這表明為了更好的模型性能，使用所有可用的網絡元信息(如節點或邊緣屬性)的重要性。另一個工作， Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification，Chen等人表明，如果用線性部分來取代非線性鄰域聚合函數，其中包括鄰居的度和圖屬性的傳播，那么模型的性能不會降低，— 這與前面的說法一致，即許多圖數據集對于分類來說都是不重要的，并且為這個任務提出了適當的驗證框架的問題。

總結

隨著在優秀會議上的提交率的增長，我們可以預期在2020年GML領域會有很多有趣的結果。我們已經看到了這個領域的轉變，從圖上深度學習的啟發式應用到更合理的方法和關于圖模型范圍的基本問題。GNNs在解決許多可以通過圖表示的實際問題上有它自己的地位，但我希望在一般來說，GML剛剛到達圖論和機器學習的交集的表面，我們應該請繼續關注即將到來的結果。