2020年圖機(jī)器學(xué)習(xí)的發(fā)展趨勢

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

有 150 篇論文涉及圖機(jī)器學(xué)習(xí)，其中三分之一的論文已被接受。這大約相當(dāng)于所有被接受論文的 10%。

在閱讀了大部分關(guān)于圖機(jī)器學(xué)習(xí)的論文之后，我整理出了 2020 年圖機(jī)器學(xué)習(xí)的趨勢，如下所列：

對圖神經(jīng)網(wǎng)絡(luò)將有更深入的理論理解；

圖神經(jīng)網(wǎng)絡(luò)將會有更酷的應(yīng)用；

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

新的圖嵌入框架將出現(xiàn)。

讓我們來看看這些趨勢。

1. 圖神經(jīng)網(wǎng)絡(luò)的理論理解

從目前發(fā)展趨勢看，圖機(jī)器學(xué)習(xí)的領(lǐng)域在進(jìn)展迅速，但是圖神經(jīng)網(wǎng)絡(luò)還有很多工作要做。但關(guān)于圖神經(jīng)網(wǎng)絡(luò)的工作原理，已經(jīng)有了一些重要的研究結(jié)果！

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

論文表明，如果我們希望圖神經(jīng)網(wǎng)絡(luò)能夠計(jì)算一個(gè)流行的圖問題（如循環(huán)檢測、直徑估計(jì)、頂點(diǎn)覆蓋等等），那么節(jié)點(diǎn)嵌入的維數(shù)（網(wǎng)絡(luò)寬度 w）乘以層數(shù)（網(wǎng)絡(luò)深度 d） 應(yīng)與圖 n 的大小成正比，即 dw=O（n）。

但現(xiàn)實(shí)是當(dāng)前的GNN的許多實(shí)現(xiàn)都無法達(dá)到此條件，因?yàn)閷訑?shù)和嵌入的尺寸與圖的大小相比還不夠大。另一方面，較大的網(wǎng)絡(luò)在實(shí)際操作中不合適的，這會引發(fā)有關(guān)如何設(shè)計(jì)有效的GNN的問題，當(dāng)然這個(gè)問題也是研究人員未來工作的重點(diǎn)。需要說明的是，這篇論文還從80年代的分布式計(jì)算模型中汲取了靈感，證明了GNN本質(zhì)上是在做同樣的事情。

與此類似，Oono 與 Suzuki、Barcelo 等人的另外兩篇論文也研究了圖神經(jīng)網(wǎng)絡(luò)的威力。在第一篇論文《圖神經(jīng)網(wǎng)絡(luò)在節(jié)點(diǎn)分類的表達(dá)能力呈指數(shù)級下降》（Graph Neual Networks Exponentially Lose Expressive Power for Node Classification）中，論文指出：

在一定的權(quán)重條件下，當(dāng)層數(shù)增加時(shí)，GCN 只能學(xué)習(xí)節(jié)點(diǎn)度和連通分量（由拉普拉斯譜（the spectra of the Laplacian）確定），除此之外什么也學(xué)不到。

這個(gè)結(jié)果推廣了馬爾科夫過程（Markov Processes）收斂到唯一平衡點(diǎn)的著名性質(zhì)，其中收斂速度由轉(zhuǎn)移矩陣的特征值決定。

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

理論方面的其他工作包括 Hou 等人的圖神經(jīng)網(wǎng)絡(luò)測量圖信息的使用，以及 Srinivasan 與 Ribeiro 提出的基于角色和基于距離的節(jié)點(diǎn)嵌入的等價(jià)性。

2. 圖神經(jīng)網(wǎng)絡(luò)的更多應(yīng)用

在過去的一年中，GNN已經(jīng)在一些實(shí)際任務(wù)中進(jìn)行了應(yīng)用。包括修復(fù) JavaScript 中的 Bug、玩游戲、回答類似 IQ 的測試、優(yōu)化 TensorFlow 計(jì)算圖、分子生成以及對話系統(tǒng)中的問題生成。

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

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

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

DeepMind 的一篇論文《用于優(yōu)化計(jì)算圖的增強(qiáng)遺傳算法學(xué)習(xí)》（Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs）提出了**一種強(qiáng)化學(xué)習(xí)算法，可以優(yōu)化 TensorFlow 計(jì)算圖的成本。**這些圖是通過標(biāo)準(zhǔn)的消息傳遞圖神經(jīng)網(wǎng)絡(luò)來處理的，圖神經(jīng)網(wǎng)絡(luò)生成與圖中每個(gè)節(jié)點(diǎn)的調(diào)度優(yōu)先級相對應(yīng)的離散化嵌入。這些嵌入被輸入到一個(gè)遺傳算法 BRKGA 中，該算法決定每個(gè)節(jié)點(diǎn)的設(shè)備放置和調(diào)度。通過對該模型進(jìn)行訓(xùn)練，優(yōu)化得到的 TensorFlow 圖的實(shí)際計(jì)算成本。

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

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

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

知識圖譜例子

在 斯坦福大學(xué)Ren 等人的論文《Query2box：基于框嵌入的向量空間中知識圖譜的推理》（Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings）中，作者建議 將查詢嵌入到潛在空間中作為矩形框形式，而不是作為單點(diǎn)形式。這種方法允許執(zhí)行自然的相交操作，即合取 ∧，因?yàn)樗鼤a(chǎn)生新的矩形框。但是，對聯(lián)合（即析取 ∨）進(jìn)行建模并不是那么簡單，因?yàn)樗赡軙?dǎo)致不重疊的區(qū)域。此外，為了精確建模任何帶有嵌入的查詢，用 VC 維（Vapnik-Chervonenkis Dimension）度量的嵌入之間的距離函數(shù)的復(fù)雜度應(yīng)與圖中實(shí)體的數(shù)量成正比。取而代之的一個(gè)很好的技巧是，將一個(gè)析取式查詢替換為 DNF 形式，其中只有在計(jì)算圖的末尾才會出現(xiàn)聯(lián)合，這可以有效地減少對每個(gè)子查詢的簡單舉例計(jì)算。

Query2Box 推理框架

在類似的主題中，Wang 等人在題為《知識圖譜中數(shù)字規(guī)則的可微學(xué)習(xí)》（Differentiable Learning of Numerical Rules in Knowledge Graphs）中，**提出了一種使用處理數(shù)值實(shí)體和規(guī)則的方法。**例如，對于引用知識圖譜，可以有一個(gè)規(guī)則 influences（Y，X） ←colleagueOf（Z，Y） ∧ supervisorOf（Z，X） ∧ hasCitation》（Y，Z），它指出，學(xué)生 X 通常會受到他們的導(dǎo)師 Z 的同事 Y 的影響，后者被引用的次數(shù)更多。這個(gè)規(guī)則右邊的每個(gè)關(guān)系都可以表示為一個(gè)矩陣，尋找缺失鏈接的過程可以通過實(shí)體向量的連續(xù)矩陣乘法，這一過程稱為規(guī)則學(xué)習(xí)（Rule Learning）。由于矩陣的構(gòu)造方式，神經(jīng)方法只能在諸如 colleagueOf（z，y）這樣的分類規(guī)則下工作。該論文作者的貢獻(xiàn)在于，他們提出了一種新穎的方法，通過顯示實(shí)際上無需顯式地物化這樣的矩陣，顯著地減少了運(yùn)行時(shí)間，從而有效地利用hasCitation（y，z） 和否定運(yùn)算符等數(shù)值規(guī)則。

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

在今年的圖神經(jīng)網(wǎng)絡(luò)（或者說機(jī)器學(xué)習(xí)）中經(jīng)常出現(xiàn)的一個(gè)研究方向是：對現(xiàn)有模型的重新評估，以及在一個(gè)公平環(huán)境中進(jìn)行測評。

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

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

4. 新的圖嵌入框架將出現(xiàn)

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

康奈爾的Chenhui Deng等人的《GraphZoom： A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》提出了一種改善運(yùn)行時(shí)間和準(zhǔn)確率的方法，可以應(yīng)用到任何無監(jiān)督嵌入方法的節(jié)點(diǎn)分類問題。

這篇文章的總體思路是，首先將原始圖簡化為更小的圖，這樣可以快速計(jì)算節(jié)點(diǎn)嵌入，然后再回復(fù)原始圖的嵌入。

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

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

他們的研究表明，一個(gè)不利用圖的拓?fù)浣Y(jié)構(gòu)（僅適用聚合節(jié)點(diǎn)特征）的簡單基線能獲得與SOTA GNN差不多的性能。事實(shí)上，這個(gè)讓人驚訝的發(fā)現(xiàn)，Orlova等人在2015年就已經(jīng)發(fā)表了，但沒有引起大家的廣泛關(guān)注。

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

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

結(jié)論

隨著頂會的論文提交量的增長，我們可以預(yù)計(jì)，2020 年圖機(jī)器學(xué)習(xí)領(lǐng)域?qū)楷F(xiàn)許多有趣的成果。我們已經(jīng)目睹這一領(lǐng)域的轉(zhuǎn)變，從圖的深度學(xué)習(xí)的啟發(fā)式應(yīng)用，到更合理的方法和關(guān)于圖波形范圍的基本問題。圖神經(jīng)網(wǎng)絡(luò)找到了它的位置，作為一個(gè)有效的解決許多實(shí)際問題的方法，這些問題可以用圖來表達(dá)，但我認(rèn)為，總體而言，圖機(jī)器學(xué)習(xí)只不過是觸及了我們可以實(shí)現(xiàn)的圖論和機(jī)器學(xué)習(xí)的交叉點(diǎn)上所能取得的成果的皮毛，我們應(yīng)該繼續(xù)關(guān)注即將到來的結(jié)果。