詳解圖神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)原理1

圖深度學(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的輸入)。