導(dǎo)讀

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

[[314620]]

介紹

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

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

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

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

我們一個(gè)一個(gè)來(lái)看。

1. 對(duì)GNN有更扎實(shí)的理論理解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. 知識(shí)圖譜變得越來(lái)越流行

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

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

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

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

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

4. 圖嵌入的新框架

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

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

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

總結(jié)

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