導(dǎo)讀

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

[[314620]]

介紹

本文的目標(biāo)不是介紹GML的基本概念，如圖神經(jīng)網(wǎng)絡(luò)(GNNs)，而是介紹我們在頂級科學(xué)會議上看到的前沿研究。

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

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

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

我們一個一個來看。

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

我特別興奮地看到這一趨勢，因為它表明，GML領(lǐng)域的成熟和以前的啟發(fā)式方法正在被新的理論解決方案所取代。關(guān)于圖神經(jīng)網(wǎng)絡(luò)還有很多需要理解的地方，但是關(guān)于GNNs如何工作有相當(dāng)多的重要結(jié)果。

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

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

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

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

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

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

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

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

2. GNN的新酷應(yīng)用

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

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

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

DeepMind的一篇論文Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs提出了一種RL算法用來優(yōu)化TensorFlow計算圖的計算代價。圖通過標(biāo)準(zhǔn)的消息傳遞GNN進行處理，該GNN產(chǎn)生的離散嵌入對應(yīng)于圖中每個節(jié)點的調(diào)度優(yōu)先級。這些嵌入被輸入到一個遺傳算法BRKGA中，BRKGA決定每個節(jié)點的設(shè)備放置和調(diào)度。通過對模型的訓(xùn)練，優(yōu)化得到的TensorFlow圖的實際計算代價。

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

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

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

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

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

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

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

4. 圖嵌入的新框架

圖嵌入是圖機器學(xué)習(xí)的一個長期主題，今年有一些關(guān)于我們應(yīng)該如何學(xué)習(xí)圖表示的新觀點。

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

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

總結(jié)

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