【導(dǎo)讀】GNN是目前機(jī)器學(xué)習(xí)領(lǐng)域的熱門網(wǎng)絡(luò)之一，肯多研究與技術(shù)分享相比不可知的深度學(xué)習(xí)網(wǎng)絡(luò)模型，GNN 有哪些吸引我們的優(yōu)勢(shì)及硬核實(shí)力。然而，GNN 是完美的嗎？有什么缺點(diǎn)？在何種情況下，GNN 是無(wú)法發(fā)揮其能力的？近日，在 arXiv 上發(fā)布了一篇論文，專門研究探討了 GNN 在普適性與學(xué)習(xí)局限性等問(wèn)題。

本文主要從計(jì)算能力有限的角度，來(lái)研究GNN在消息傳遞分布式系統(tǒng)中的圖靈普適性和局限性，并得到了兩個(gè)與圖論問(wèn)題能否解決（impossibility statements）有關(guān)的結(jié)論：

（1）在一定的充足條件下，GNN是具有圖靈普適性的；

（2）而在深度和廣度被限制的條件下，GNN的性能會(huì)有一定的局限性。

應(yīng)用第一個(gè)結(jié)論，可以對(duì)一些圖論優(yōu)化問(wèn)題設(shè)置更低的計(jì)算復(fù)雜度下界，第二個(gè)結(jié)論則說(shuō)明在深度和廣度的乘積不超過(guò)圖的大小時(shí)，GNN是無(wú)法解決其他的一些問(wèn)題的。

專業(yè)術(shù)語(yǔ)

為了方便大家后續(xù)閱讀理解文章，我們先把文中涉及的幾個(gè)專業(yè)問(wèn)題做簡(jiǎn)單闡述：

1、圖靈普適性（Turing universal）

一個(gè)具有圖靈普適性的圖靈機(jī)（Universal Turing machine）能夠模擬任何圖靈機(jī)在任何輸入下的情況。

2、一致性問(wèn)題（Consensus）

即在分布式計(jì)算或者多代理（multi-agent）系統(tǒng)中，如何在發(fā)生進(jìn)程故障的情況下保持系統(tǒng)的可靠性（reliability）。這通常需要進(jìn)程就計(jì)算過(guò)程中的一些數(shù)值或數(shù)值操作達(dá)成一致，包括如何將提交到數(shù)據(jù)庫(kù)，如何識(shí)別leader進(jìn)程，狀態(tài)機(jī)復(fù)制（一種故障容忍機(jī)制），原子廣播等操作。

3、不可能結(jié)果（Impossibility result）

這是分布式領(lǐng)域的專業(yè)術(shù)語(yǔ)，在一個(gè)完全異步的消息傳遞分布式系統(tǒng)中，如果一個(gè)進(jìn)程有故障，那么一致性問(wèn)題是無(wú)法得到解決的，在此基礎(chǔ)上，有兩個(gè)比較著名的 impossibility result：FLP和CAP，詳見(jiàn)[1][2]。本文中提出了關(guān)于GNN的兩個(gè)結(jié)論都是屬于GNN的 impossibility results。簡(jiǎn)單來(lái)說(shuō)，就是在一定的限制條件下問(wèn)題能否被解決，那么任務(wù)的impossibility result就只有兩種情況：能和不能。

4、GNN的深度和廣度（depth and width）

深度就是網(wǎng)絡(luò)層數(shù)，廣度就是每層的感知域，也就是每個(gè)節(jié)點(diǎn)的能獲取到信息的鄰接節(jié)點(diǎn)的范圍。

模型普適性的研究

機(jī)器學(xué)習(xí)中的一個(gè)基本任務(wù)是研究哪些內(nèi)容是一個(gè)模型（網(wǎng)絡(luò)）能學(xué)習(xí)到，而哪些是不能學(xué)習(xí)到的，也就是研究模型的普適性，研究其能否解決大部分任務(wù)。過(guò)去的一些研究通過(guò)不變函數(shù)或者等效函數(shù)來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行等效近似，從而在函數(shù)層面研究什么是一個(gè)模型能學(xué)習(xí)到的內(nèi)容。

通常理論認(rèn)為，在有充足的訓(xùn)練數(shù)據(jù)和合適的學(xué)習(xí)優(yōu)化算法的情況下，普適性網(wǎng)絡(luò)能夠解決大部分給定的任務(wù)，然而這種理解是不全面的，因?yàn)樵趯?shí)際應(yīng)用時(shí)要滿足充足訓(xùn)練數(shù)據(jù)和合適優(yōu)化算法是比較困難的，這種無(wú)限制的普適性網(wǎng)絡(luò)是不能作為實(shí)際部署時(shí)的網(wǎng)絡(luò)設(shè)計(jì)參考的。

因此，可以從問(wèn)題的對(duì)立面，即研究模型的局限性，來(lái)間接地研究其普適性，也就是在特定的任務(wù)中，特定的限制條件下網(wǎng)絡(luò)不能學(xué)習(xí)到的內(nèi)容。這有助于了解模型和特定任務(wù)之間的關(guān)系，從而知曉任務(wù)能否被解決（impossibility results），進(jìn)而幫助我們調(diào)整模型的參數(shù)。例如，在圖分類任務(wù)中，我們希望模型能學(xué)習(xí)到同一類圖的共同特征，不同類圖的區(qū)別特征，然而如果GNN模型本身的深度和廣度不足以學(xué)習(xí)到足夠的特征，那么這個(gè)問(wèn)題就是impossible的，因此就需要進(jìn)一步的調(diào)整深度和廣度。

文章主要貢獻(xiàn)

本文所研究的特定任務(wù)是圖論中的一些優(yōu)化任務(wù)，特定限制條件是 GNN 的深度和廣度，將深度和廣度與理論計(jì)算機(jī)科學(xué)中的復(fù)雜度等度量聯(lián)系起來(lái)，再將計(jì)算復(fù)雜度作為這些優(yōu)化任務(wù)的完成下界（從 impossible 變?yōu)?possible 的最低復(fù)雜度要求），從而得到GNN的深度和廣度對(duì)具體任務(wù)的影響，以及對(duì)GNN普適性的影響。具體地，關(guān)于普適性的研究有以下兩個(gè)結(jié)論。

1、GNN 的圖靈普適性

在足夠的條件下，GNN 能以圖靈機(jī)的形式對(duì)任意輸入函數(shù)進(jìn)行運(yùn)算，且不限于網(wǎng)絡(luò)結(jié)構(gòu)。通過(guò)建立 GNN 和經(jīng)典分布式計(jì)算模型 LOCAL 之間的圖靈等效，來(lái)間接的研究其普適性。這里的足夠條件是：

（1）有足夠的層數(shù)

（2）每一層都有足夠的廣度

（3）節(jié)點(diǎn)之間可以相互獨(dú)立（ids）

（4）每一層計(jì)算的函數(shù)有足夠的表現(xiàn)力

2、GNN 的學(xué)習(xí)能力局限性

正如前面提到的，在深度和廣度都被限制的情況下，GNN是無(wú)法表現(xiàn)出其圖靈普適性，即應(yīng)用在具體任務(wù)上時(shí)，無(wú)法解決這個(gè)任務(wù)。那么如何確定能否完成任務(wù)的下界呢？還是通過(guò) LOCAL。任務(wù)或問(wèn)題的 impossiblility result 可以在GNN和LOCAL之間以一定的形式相互轉(zhuǎn)換，因此研究任務(wù)在 GNN下能否完成和在LOCAL下能否完成是等效的，進(jìn)而可以在LOCAL模型下為完成任務(wù)的計(jì)算復(fù)雜度要求設(shè)置下界。具體的，文章中提到了四種類型的任務(wù)（問(wèn)題定義詳見(jiàn)原論文）：

（1）檢測(cè)（detecting）圖G中是否含有特定長(zhǎng)度的環(huán)（cycle of specific length）

（2）驗(yàn)證（verifying）圖G的給定子圖是否連通（connected），是否具有環(huán)（cycle），是否為生成樹(shù)（spanning tree，具備樹(shù)結(jié)構(gòu)，沒(méi)有環(huán)），是否為二分圖（bipartite，頂點(diǎn)集合可以分為兩個(gè)子集，所有邊的兩個(gè)頂點(diǎn)分屬于這兩個(gè)子集），是否為簡(jiǎn)單路徑（simple path，與圖的哈密頓循環(huán)有關(guān)）

（3）計(jì)算（computing）兩個(gè)頂點(diǎn)間的最短路徑（shortest path between two vertices），圖的最小割（minimum cut），以及最小生成樹(shù)（the minimum spanning tree）

（4）求圖的最大獨(dú)立集（maximum independent），最小頂點(diǎn)覆蓋（minimum vertex cover），或圖的頂點(diǎn)著色問(wèn)題（chromatic coloring）

以上問(wèn)題都是屬于圖論中的傳統(tǒng)優(yōu)化問(wèn)題，雖然不是現(xiàn)在主流研究的頂點(diǎn)分類，圖分類問(wèn)題，但二者之間有密不可分的聯(lián)系。這些問(wèn)題的具體計(jì)算復(fù)雜度下界為：

總結(jié)

本文首次對(duì)GNN模型提出了 impossible 問(wèn)題，并通過(guò)等效計(jì)算的方法，以計(jì)算復(fù)雜度的形式，給出了 GNN 在部分圖論任務(wù)中impossible results下界與網(wǎng)絡(luò)寬度和廣度的關(guān)系，在一定程度上說(shuō)明了 GNN 的性能會(huì)受到網(wǎng)絡(luò)本身的寬度和廣度的限制。

由于原文中的數(shù)學(xué)推導(dǎo)過(guò)于復(fù)雜，因此這里我只介紹文章的基本思想。GNN作為目前機(jī)器學(xué)習(xí)領(lǐng)域的熱門研究之一，已經(jīng)被應(yīng)用于各種各樣的任務(wù)，通常在應(yīng)用一個(gè)網(wǎng)絡(luò)的同時(shí)，也要同步地去研究這個(gè)網(wǎng)絡(luò)的內(nèi)在本質(zhì)，從而更好的理解，改進(jìn)它，進(jìn)而幫助我們?cè)趯?shí)際應(yīng)用網(wǎng)絡(luò)時(shí)更好的設(shè)置網(wǎng)絡(luò)的參數(shù)，這篇文章就是一個(gè)很好的例子。