圖深度學(xué)習(xí)(Graph Deep Learning) 多年來一直在加速發(fā)展。許多現(xiàn)實(shí)生活問題使GDL成為萬能工具:在社交媒體、藥物發(fā)現(xiàn)、芯片植入、預(yù)測(cè)、生物信息學(xué)等方面都顯示出了很大的前景。
本文將流行的圖神經(jīng)網(wǎng)絡(luò)及其數(shù)學(xué)細(xì)微差別的進(jìn)行詳細(xì)的梳理和解釋,圖深度學(xué)習(xí)背后的思想是學(xué)習(xí)具有節(jié)點(diǎn)和邊的圖的結(jié)構(gòu)和空間特征,這些節(jié)點(diǎn)和邊表示實(shí)體及其交互。
圖
在我們進(jìn)入圖神經(jīng)網(wǎng)絡(luò)之前,讓我們先來探索一下計(jì)算機(jī)科學(xué)中的圖是什么。
圖G(V,E)是包含一組頂點(diǎn)(節(jié)點(diǎn))i∈v和一組連接頂點(diǎn)i和j的邊eij∈E的數(shù)據(jù)結(jié)構(gòu),如果連接兩個(gè)節(jié)點(diǎn)i和j,則eij=1,否則eij=0??梢詫⑦B接信息存儲(chǔ)在鄰接矩陣A中:
我假設(shè)本文中的圖是無加權(quán)的(沒有邊權(quán)值或距離)和無向的(節(jié)點(diǎn)之間沒有方向關(guān)聯(lián)),并且假設(shè)這些圖是同質(zhì)的(單一類型的節(jié)點(diǎn)和邊;相反的是“異質(zhì)”)。
圖與常規(guī)數(shù)據(jù)的不同之處在于,它們具有神經(jīng)網(wǎng)絡(luò)必須尊重的結(jié)構(gòu);不利用它就太浪費(fèi)了。下面的圖是一個(gè)社交媒體圖的例子,節(jié)點(diǎn)是用戶,邊是他們的互動(dòng)(比如關(guān)注/點(diǎn)贊/轉(zhuǎn)發(fā))。
對(duì)于圖像來說,圖像本身就是一個(gè)圖!這是一種叫做“網(wǎng)格圖”的特殊變體,其中對(duì)于所有內(nèi)部節(jié)點(diǎn)和角節(jié)點(diǎn),來自節(jié)點(diǎn)的外向邊的數(shù)量是恒定的。在圖像網(wǎng)格圖中存在一些一致的結(jié)構(gòu),允許對(duì)其執(zhí)行簡單的類似卷積的操作。
圖像可以被認(rèn)為是一種特殊的圖,其中每個(gè)像素都是一個(gè)節(jié)點(diǎn),并通過虛線與周圍的其他像素連接。當(dāng)然,以這種方式查看圖像是不切實(shí)際的,因?yàn)檫@意味著需要一個(gè)非常大的圖。例如,32×32×3的一個(gè)簡單的CIFAR-10圖像會(huì)有3072個(gè)節(jié)點(diǎn)和1984條邊。對(duì)于224×224×3的較大ImageNet圖像,這些數(shù)字會(huì)更大。
與圖片相比,圖的不同的節(jié)點(diǎn)與其他節(jié)點(diǎn)的連接數(shù)量不同,并且沒有固定的結(jié)構(gòu),但是就是這種結(jié)構(gòu)為圖增加了價(jià)值。
圖神經(jīng)網(wǎng)絡(luò)
單個(gè)圖神經(jīng)網(wǎng)絡(luò)(GNN)層有一堆步驟,在圖中的每個(gè)節(jié)點(diǎn)上會(huì)執(zhí)行:
- 消息傳遞
- 聚合
- 更新
這些組成了對(duì)圖形進(jìn)行學(xué)習(xí)的構(gòu)建塊,GDL的創(chuàng)新都是在這3個(gè)步驟的進(jìn)行的改變。
節(jié)點(diǎn)
節(jié)點(diǎn)表示一個(gè)實(shí)體或?qū)ο?,如用戶或原子。因此?jié)點(diǎn)具有所表示實(shí)體的一系列屬性。這些節(jié)點(diǎn)屬性形成了節(jié)點(diǎn)的特征(即“節(jié)點(diǎn)特征”或“節(jié)點(diǎn)嵌入”)。
通常,這些特征可以用Rd中的向量表示. 這個(gè)向量要么是潛維嵌入,要么是以每個(gè)條目都是實(shí)體的不同屬性的方式構(gòu)造的。
例如,在社交媒體圖中,用戶節(jié)點(diǎn)具有可以用數(shù)字表示的年齡、性別、政治傾向、關(guān)系狀態(tài)等屬性。在分子圖中,原子節(jié)點(diǎn)可能具有化學(xué)性質(zhì),如對(duì)水的親和力、力、能量等,也可以用數(shù)字表示。
這些節(jié)點(diǎn)特征是GNN的輸入,每個(gè)節(jié)點(diǎn)i具有關(guān)聯(lián)的節(jié)點(diǎn)特征xi∈Rd和標(biāo)簽yi(可以是連續(xù)的,也可以是離散的,就像單獨(dú)編碼一樣)。
邊
邊也可以有特征aij∈Rd '例如,在邊緣有意義的情況下(如原子之間的化學(xué)鍵)。我們可以把下面的分子想象成一個(gè)圖,其中原子是節(jié)點(diǎn),鍵是邊。雖然原子節(jié)點(diǎn)本身有各自的特征向量,但邊可以有不同的邊特征,編碼不同類型的鍵(單鍵、雙鍵、三鍵)。不過為了簡單起見,在本文中我將省略邊的特性。
現(xiàn)在我們知道了如何在圖中表示節(jié)點(diǎn)和邊,讓我們從一個(gè)具有一堆節(jié)點(diǎn)(具有節(jié)點(diǎn)特征)和邊的簡單圖開始。
消息傳遞
gnn以其學(xué)習(xí)結(jié)構(gòu)信息的能力而聞名。通常,具有相似特征或?qū)傩缘墓?jié)點(diǎn)相互連接(比如在社交媒體中)。GNN利用學(xué)習(xí)特定節(jié)點(diǎn)如何以及為什么相互連接,GNN會(huì)查看節(jié)點(diǎn)的鄰域。
鄰居Ni,節(jié)點(diǎn)I的集合定義為通過邊與I相連的節(jié)點(diǎn)j的集合。形式為Ni={j: eij∈E}。
一個(gè)人被他所處的圈子所影響。類似地GNN可以通過查看其鄰居Ni中的節(jié)點(diǎn)i來了解很多關(guān)于節(jié)點(diǎn)i的信息。為了在源節(jié)點(diǎn)i和它的鄰居節(jié)點(diǎn)j之間實(shí)現(xiàn)這種信息共享,gnn進(jìn)行消息傳遞。
對(duì)于GNN層,消息傳遞被定義為獲取鄰居的節(jié)點(diǎn)特征,轉(zhuǎn)換它們并將它們“傳遞”給源節(jié)點(diǎn)的過程。對(duì)于圖中的所有節(jié)點(diǎn),并行地重復(fù)這個(gè)過程。這樣,在這一步結(jié)束時(shí),所有的鄰域都將被檢查。
讓我們放大節(jié)點(diǎn)6并檢查鄰域N6={1,3,4}。我們?nèi)∶總€(gè)節(jié)點(diǎn)特征x1、x3和x4,用函數(shù)F對(duì)它們進(jìn)行變換,函數(shù)F可以是一個(gè)簡單的神經(jīng)網(wǎng)絡(luò)(MLP或RNN),也可以是仿射變換F(xj)=Wj?xj+b。簡單地說,“消息”是來自源節(jié)點(diǎn)的轉(zhuǎn)換后的節(jié)點(diǎn)特征。
F 可以是簡單的仿射變換或神經(jīng)網(wǎng)絡(luò)?,F(xiàn)在我們?cè)O(shè)F(xj)=Wj?xj為了方便計(jì)算 ? 表示簡單的矩陣乘法。
聚合
現(xiàn)在我們有了轉(zhuǎn)換后的消息{F(x1),F(xiàn)(x3),F(xiàn)(x4)}傳遞給節(jié)點(diǎn)6,下面就必須以某種方式聚合(“組合”)它們。有很多方法可以將它們結(jié)合起來。常用的聚合函數(shù)包括:
假設(shè)我們使用函數(shù)G來聚合鄰居的消息(使用sum、mean、max或min)。最終聚合的消息可以表示為:
更新
使用這些聚合消息,GNN層就要更新源節(jié)點(diǎn)i的特性。在這個(gè)更新步驟的最后,節(jié)點(diǎn)不僅應(yīng)該知道自己,還應(yīng)該知道它的鄰居。這是通過獲取節(jié)點(diǎn)i的特征向量并將其與聚合的消息相結(jié)合來操作的,一個(gè)簡單的加法或連接操作就可以解決這個(gè)問題。
使用加法
其中σ是一個(gè)激活函數(shù)(ReLU, ELU, Tanh), H是一個(gè)簡單的神經(jīng)網(wǎng)絡(luò)(MLP)或仿射變換,K是另一個(gè)MLP,將加法的向量投影到另一個(gè)維度。
使用連接:
為了進(jìn)一步抽象這個(gè)更新步驟,我們可以將K看作某個(gè)投影函數(shù),它將消息和源節(jié)點(diǎn)嵌入一起轉(zhuǎn)換:
初始節(jié)點(diǎn)特征稱為xi,在經(jīng)過第一GNN層后,我們將節(jié)點(diǎn)特征變?yōu)閔i。假設(shè)我們有更多的GNN層,我們可以用hli表示節(jié)點(diǎn)特征,其中l(wèi)是當(dāng)前GNN層索引。同樣,顯然h0i=xi(即GNN的輸入)。
-
芯片
+關(guān)注
關(guān)注
452文章
50008瀏覽量
419734 -
神經(jīng)網(wǎng)絡(luò)
+關(guān)注
關(guān)注
42文章
4726瀏覽量
100319 -
數(shù)學(xué)
+關(guān)注
關(guān)注
0文章
99瀏覽量
19202
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論