Deepmind最新研究:從圖表示學(xué)習(xí)看算法推理

??新智元報(bào)道??

來源：deepmind等

編輯：雅新

【新智元導(dǎo)讀】在上周三ICLR 2020大會中，來自Deepmind的研究人員Petar Veli?kovi?介紹了用算法推理的圖表示學(xué)習(xí)最新研究。該研究提出了主要鄰域聚合（PNA），并通過實(shí)踐證明了使用多個(gè)聚合策略同時(shí)提高了GNN的表現(xiàn)力。「新智元急聘主筆、高級主任編輯，添加HR微信（Dr-wly）或掃描文末二維碼了解詳情?！?/span>

?

由于圖的不規(guī)則性，傳統(tǒng)的深度學(xué)習(xí)算法在處理復(fù)雜的圖時(shí)面臨著巨大的挑戰(zhàn)。

?

近年來，人們對深度學(xué)習(xí)方法在圖上的擴(kuò)展有著濃厚的興趣，由此一個(gè)新的研究熱點(diǎn)——圖神經(jīng)網(wǎng)絡(luò)（GNN）應(yīng)運(yùn)而生。圖神經(jīng)網(wǎng)絡(luò)在算法推理能力上有著不可估量的潛力，甚至有望成為下個(gè)AI拐點(diǎn)。

?

上周的ICLR 2020大會中，來自Deepmind的研究人員Petar Veli?kovi?主要介紹了用于算法推理的圖表示學(xué)習(xí)最新研究。?

? ? ? ?? ? ? ?

圖表示學(xué)習(xí)

GNN 的出現(xiàn)，給圖表示學(xué)習(xí)帶來了新的建模方法。圖表示學(xué)習(xí)是深度學(xué)習(xí)的一個(gè)方向，是一種無監(jiān)督學(xué)習(xí)，其核心是研究圖數(shù)據(jù)的表示。以 DeepWalk、LINE 和 node2vec 為代表的圖表示學(xué)習(xí)技術(shù)得到廣泛地應(yīng)用。

?

為什么我們要通過圖來表示學(xué)習(xí)？是因?yàn)楹芏鄶?shù)據(jù)都是圖結(jié)構(gòu)，例如社交網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)、生物醫(yī)學(xué)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、互聯(lián)網(wǎng)、神經(jīng)網(wǎng)絡(luò)等。

圖數(shù)據(jù)中蘊(yùn)含著豐富的結(jié)構(gòu)信息，然而因其內(nèi)在關(guān)聯(lián)而產(chǎn)生的一種非線性結(jié)構(gòu)，在補(bǔ)充刻畫數(shù)據(jù)時(shí)，給數(shù)據(jù)學(xué)習(xí)帶來了巨大挑戰(zhàn)。因此，圖表示學(xué)習(xí)在此就會發(fā)揮巨大的作用。

它具有兩個(gè)重要作用，一是將圖數(shù)據(jù)表示成線性空間中的向量；二是為之后的學(xué)習(xí)任務(wù)奠定基礎(chǔ)。? ? ? ? ??

?

GNN表現(xiàn)力不夠強(qiáng)

?

圖神經(jīng)網(wǎng)絡(luò)（GNN）在過去十年中一直是活躍的研究領(lǐng)域，同時(shí)圖表示學(xué)習(xí)取得了巨大的突破。但是，由于缺乏標(biāo)準(zhǔn)化的基準(zhǔn)和表現(xiàn)力的理論框架，新型圖神經(jīng)網(wǎng)絡(luò)的有效性很難讓人理解。

實(shí)際上，該領(lǐng)域的大多數(shù)工作都集中在改進(jìn)一組圖形基準(zhǔn)上的GNN架構(gòu)，而沒有評估其網(wǎng)絡(luò)能否正確表示圖的結(jié)構(gòu)特性。

直到最近，才有關(guān)于各種GNN模型表現(xiàn)力的重大研究，主要集中在同構(gòu)任務(wù)和可數(shù)特征空間上。但是，這些主要側(cè)重于區(qū)分不同的圖形拓?fù)淠芰ι?，而在了解它們能否捕獲并利用圖結(jié)構(gòu)的基礎(chǔ)特征上所做的工作很少。

?

或者一些工作側(cè)重于使用光譜域?qū)⒕矸e神經(jīng)網(wǎng)絡(luò)（CNN）推廣到圖形，這是Bruna等人首先提出的。為了提高光譜分析效率和改善模型的性能，Chebyshev多項(xiàng)式誕生，后來推廣到Cayley濾波器。

?

在本文研究工作中，研究人員著眼于不同GNN模型理解光譜分解某些方面的能力，即拉普拉斯圖和光譜半徑，因?yàn)樗鼈儤?gòu)成了圖的光譜特性的基本方面。雖然光譜特性和濾光片沒有在此次的架構(gòu)中明確編碼，但功能強(qiáng)大的GNN仍然能夠有效地學(xué)習(xí)。

?

研究發(fā)現(xiàn)：主要鄰域聚合（PNA）

?

先前經(jīng)典圖論工作著重于評估GNN模型在單個(gè)任務(wù)上應(yīng)用的性能，如最短路徑，圖矩或旅行商問題。

?

而本文研究者們采用了不同的方法開發(fā)多任務(wù)基準(zhǔn)，同時(shí)包含節(jié)點(diǎn)級和圖形級的問題。他們還特別觀測了每個(gè)GNN預(yù)測單源最短路徑，離心率，拉普拉斯特征的能力，連通性，直徑和光譜半徑。其中許多任務(wù)基于使用動(dòng)態(tài)算法編程，因此非常適合于GNN的研究。

?

Petar表示，「我們相信這項(xiàng)多任務(wù)方法可確保GNN能夠同時(shí)理解多種特性，這是解決復(fù)雜圖形問題的基礎(chǔ)。而且，任務(wù)間有效地共享參數(shù)，表明了其對圖形的結(jié)構(gòu)特征有更深入的了解。此外，我們通過在更大尺寸的圖形上進(jìn)行測試來探索網(wǎng)絡(luò)的泛化能力存在于訓(xùn)練集中?！?/span>

?

? ? ? ??使用單個(gè)GNN層和連續(xù)輸入要素空間，一些聚合器無法區(qū)分鄰域消息。同時(shí)研究還發(fā)現(xiàn)聚合器是互補(bǔ)的，至少有一個(gè)聚合器始終可以區(qū)分不同的鄰域消息。

通過假設(shè)當(dāng)前的GNN的聚合層從節(jié)點(diǎn)鄰域進(jìn)入單層無法提取足夠的信息，這限制了它們的表現(xiàn)力和學(xué)習(xí)能力。實(shí)際上，最近的工作表明不同的聚合器在不同的任務(wù)上表現(xiàn)更好。由于不能正確識別鄰域，同時(shí)也無法可靠地找到子結(jié)構(gòu)，GNN并不能很好地學(xué)習(xí)節(jié)點(diǎn)集群。

?

研究者們首先對引入不可數(shù)多集注入性問題提出解決方案，從數(shù)學(xué)上證明對多種聚合的需求。然后，他們提出了標(biāo)度的概念，作為總聚合概括，它允許網(wǎng)絡(luò)基于每個(gè)節(jié)點(diǎn)的程度放大或衰減信號。結(jié)合以上內(nèi)容，研究者又設(shè)計(jì)了主鄰域聚合（PNA）網(wǎng)絡(luò)，并通過實(shí)踐證明了使用多個(gè)聚合策略同時(shí)提高了GNN在圖論問題上的性能。

?

Petar把目前現(xiàn)有研究中的CNN算法分為了三個(gè)級別 Unit-level, Step-level, Algo-level

?

? ? ? ?? ? ?

作者同時(shí)分析了GNN的理論框架擴(kuò)展到了連續(xù)的特征，并證明了在這種情況下需要多個(gè)聚合器。通過呈現(xiàn)標(biāo)度來聚合，并建議使用對數(shù)標(biāo)度。

針對以上所有因素，作者提出了一種由多個(gè)聚合器和標(biāo)度組成的「主要鄰域聚合」。為了理解GNN捕獲圖結(jié)構(gòu)的能力，并提出了一種新穎的多任務(wù)基準(zhǔn)以及用于解決它的編碼過程解碼結(jié)構(gòu)。

?? ? ? ?使用相同架構(gòu)和各種接近最佳的超參數(shù)的不同GNN模型的多任務(wù)基準(zhǔn)。圖a中PNA模型始終優(yōu)于最新模型，圖b顯示PNA的在所有任務(wù)表現(xiàn)的更好

?

Petar表示「我們認(rèn)為，我們的發(fā)現(xiàn)構(gòu)成了建立GNN具有表現(xiàn)力模型層次結(jié)構(gòu)的一步，從這個(gè)意義上講，PNA模型似乎優(yōu)于GNN層設(shè)計(jì)中的現(xiàn)有技術(shù)?！?/span>

?

「算法推理是圖形表示學(xué)習(xí)一個(gè)令人興奮的新領(lǐng)域。」

?