【導(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ù),這篇文章就是一個很好的例子。
-
深度學(xué)習(xí)
+關(guān)注
關(guān)注
73文章
5442瀏覽量
120800 -
GNN
+關(guān)注
關(guān)注
1文章
31瀏覽量
6322
原文標(biāo)題:什么限制了GNN的能力?首篇探究GNN普適性與局限性的論文出爐!
文章出處:【微信號:rgznai100,微信公眾號:rgznai100】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論