GNN在普適性與學(xué)習(xí)局限性等問題

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

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

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

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

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

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

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

1、圖靈普適性（Turing universal）

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

2、一致性問題（Consensus）

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

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

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

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

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

模型普適性的研究

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

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

因此，可以從問題的對立面，即研究模型的局限性，來間接地研究其普適性，也就是在特定的任務(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í)到足夠的特征，那么這個問題就是impossible的，因此就需要進(jìn)一步的調(diào)整深度和廣度。

文章主要貢獻(xiàn)

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

1、GNN 的圖靈普適性

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

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