流行圖神經(jīng)網(wǎng)絡(luò)總結(jié)

上面我們介紹完了古神經(jīng)網(wǎng)絡(luò)的基本流程，下面我們總結(jié)一下流行圖神經(jīng)網(wǎng)絡(luò)，并將它們的方程和數(shù)學(xué)分為上面提到的3個(gè)GNN步驟。許多體系結(jié)構(gòu)將消息傳遞和聚合步驟合并到一起執(zhí)行的一個(gè)函數(shù)中，而不是顯式地一個(gè)接一個(gè)執(zhí)行，但為了數(shù)學(xué)上的方便，我們將嘗試分解它們并將它們視為一個(gè)單一的操作!

1、消息傳遞神經(jīng)網(wǎng)絡(luò)

https://arxiv.org/abs/1704.01212

消息傳遞神經(jīng)網(wǎng)絡(luò)(MPNN)將正向傳播分解為具有消息函數(shù)Ml的消息傳遞階段和具有頂點(diǎn)更新函數(shù)Ul的讀出階段

MPNN將消息傳遞和聚合步驟合并到單個(gè)消息傳遞階段:

讀取階段是更新步驟:

其中ml+1v是聚合的消息，hl+1v是更新的節(jié)點(diǎn)嵌入。這與我上面提到的過(guò)程非常相似。消息函數(shù)Ml是F和G的混合，函數(shù)Ul是k，其中eij表示可能的邊緣特征，也可以省略。

2、圖卷積

https://arxiv.org/abs/1609.02907

圖卷積網(wǎng)絡(luò)(GCN)論文以鄰接矩陣的形式研究整個(gè)圖。在鄰接矩陣中加入自連接，確保所有節(jié)點(diǎn)都與自己連接以得到~A。這確保在消息聚合期間考慮源節(jié)點(diǎn)的嵌入。合并的消息聚合和更新步驟如下所示:

其中Wl是一個(gè)可學(xué)習(xí)參數(shù)矩陣。這里將X改為H，以泛化任意層l上的節(jié)點(diǎn)特征，其中H0=X。

由于矩陣乘法的結(jié)合律(A(BC)=(AB)C)，我們?cè)谀膫€(gè)序列中乘矩陣并不重要(要么是AHl先乘，然后是Wl后乘，要么是HlWl先乘，然后是A)。作者Kipf和Welling進(jìn)一步引入了度矩陣~D作為"renormalisation"的一種形式，以避免數(shù)值不穩(wěn)定和爆炸/消失的梯度:

“renormalisation”是在增廣鄰接矩陣^A=D?12A~D?12上進(jìn)行的。新的合并消息傳遞和更新步驟如下所示:

3、圖注意力網(wǎng)絡(luò)

https://arxiv.org/abs/1710.10903

聚合通常涉及在和、均值、最大值和最小值設(shè)置中平等對(duì)待所有鄰居。但是在大多數(shù)情況下，一些鄰居比其他鄰居更重要。圖注意力網(wǎng)絡(luò)(GAT)通過(guò)使用Vaswani等人(2017)的Self-Attention對(duì)源節(jié)點(diǎn)及其鄰居之間的邊緣進(jìn)行加權(quán)來(lái)確保這一點(diǎn)。

邊權(quán)值αij如下。

這里的Wa∈R2d '和W?Rd ' ×d為學(xué)習(xí)參數(shù)，d '為嵌入維數(shù)，⊕是向量拼接運(yùn)算。

雖然最初的消息傳遞步驟與MPNN/GCN相同，但合并的消息聚合和更新步驟是所有鄰居和節(jié)點(diǎn)本身的加權(quán)和:

邊緣重要性加權(quán)有助于了解鄰居對(duì)源節(jié)點(diǎn)的影響程度。與GCN一樣，添加了自循環(huán)，因此源節(jié)點(diǎn)可以將自己的表示形式考慮到未來(lái)的表示形式中。

4、GraphSAGE

https://arxiv.org/abs/1706.02216

GraphSAGE：Graph SAmple and AggreGatE。這是一個(gè)為大型、非常密集的圖形生成節(jié)點(diǎn)嵌入的模型。

這項(xiàng)工作在節(jié)點(diǎn)的鄰域上引入了學(xué)習(xí)聚合器。不像傳統(tǒng)的gat或GCNs考慮鄰居中的所有節(jié)點(diǎn)，GraphSAGE統(tǒng)一地對(duì)鄰居進(jìn)行采樣，并對(duì)它們使用學(xué)習(xí)的聚合器。

假設(shè)我們?cè)诰W(wǎng)絡(luò)(深度)中有L層，每一層L∈{1，…，L}查看一個(gè)更大的L跳鄰域w.r.t.源節(jié)點(diǎn)。然后在通過(guò)MLP的F和非線性σ傳遞之前，通過(guò)將節(jié)點(diǎn)嵌入與采樣消息連接來(lái)更新每個(gè)源節(jié)點(diǎn)。

對(duì)于某一層l

其中⊕是向量拼接運(yùn)算，N(i)是返回所有鄰居的子集的統(tǒng)一抽樣函數(shù)。如果一個(gè)節(jié)點(diǎn)有5個(gè)鄰居{1,2,3,4,5}，N(i)可能的輸出將是{1,4,5}或{2,5}。

Aggregator k=1從1-hop鄰域聚集采樣節(jié)點(diǎn)(彩色)，而Aggregator k=2從2 -hop鄰域聚集采樣節(jié)點(diǎn)(彩色)

論文中用K和K表示層指數(shù)。但在本文中分別使用L和L來(lái)表示，這是為了和前面的內(nèi)容保持一致性。此外，論文用v表示源節(jié)點(diǎn)i，用u表示鄰居節(jié)點(diǎn)j。

5、時(shí)間圖網(wǎng)絡(luò)

https://arxiv.org/abs/2006.10637

到目前為止所描述的網(wǎng)絡(luò)工作在靜態(tài)圖上。大多數(shù)實(shí)際情況都在動(dòng)態(tài)圖上工作，其中節(jié)點(diǎn)和邊在一段時(shí)間內(nèi)被添加、刪除或更新。時(shí)間圖網(wǎng)絡(luò)(TGN)致力于連續(xù)時(shí)間動(dòng)態(tài)圖(CTDG)，它可以表示為按時(shí)間順序排列的事件列表。

論文將事件分為兩種類(lèi)型:節(jié)點(diǎn)級(jí)事件和交互事件。節(jié)點(diǎn)級(jí)事件涉及一個(gè)孤立的節(jié)點(diǎn)(例如:用戶更新他們的個(gè)人簡(jiǎn)介)，而交互事件涉及兩個(gè)可能連接也可能不連接的節(jié)點(diǎn)(例如:用戶a轉(zhuǎn)發(fā)/關(guān)注用戶B)。

TGN提供了一種模塊化的CTDG處理方法，包括以下組件:

• 消息傳遞函數(shù)→孤立節(jié)點(diǎn)或交互節(jié)點(diǎn)之間的消息傳遞(對(duì)于任何類(lèi)型的事件)。
• 消息聚合函數(shù)→通過(guò)查看多個(gè)時(shí)間步長(zhǎng)的時(shí)間鄰域，而不是在給定時(shí)間步長(zhǎng)的局部鄰域，來(lái)使用GAT的聚合。
• 記憶更新→記憶（Memory）允許節(jié)點(diǎn)具有長(zhǎng)期依賴關(guān)系，并表示節(jié)點(diǎn)在潛在(“壓縮”)空間中的歷史。這個(gè)模塊根據(jù)一段時(shí)間內(nèi)發(fā)生的交互來(lái)更新節(jié)點(diǎn)的內(nèi)存。
• 時(shí)間嵌入→一種表示節(jié)點(diǎn)的方法，也能捕捉到時(shí)間的本質(zhì)。
• 鏈接預(yù)測(cè)→將事件中涉及的節(jié)點(diǎn)的時(shí)間嵌入通過(guò)一些神經(jīng)網(wǎng)絡(luò)來(lái)計(jì)算邊緣概率(即，邊緣會(huì)在未來(lái)發(fā)生嗎?)。在訓(xùn)練過(guò)程中，我們知道邊的存在，所以邊的標(biāo)簽是1，所以需要訓(xùn)練基于sigmoid的網(wǎng)絡(luò)來(lái)像往常一樣預(yù)測(cè)這個(gè)。

每當(dāng)一個(gè)節(jié)點(diǎn)參與一個(gè)活動(dòng)(節(jié)點(diǎn)更新或節(jié)點(diǎn)間交互)時(shí)，記憶就會(huì)更新。

對(duì)于批處理中的每個(gè)事件1和2,TGN為涉及該事件的所有節(jié)點(diǎn)生成消息。TGN聚合所有時(shí)間步長(zhǎng)t的每個(gè)節(jié)點(diǎn)mi的消息;這被稱為節(jié)點(diǎn)i的時(shí)間鄰域。然后TGN使用聚合消息mi(t)來(lái)更新每個(gè)節(jié)點(diǎn)si(t)的記憶。

一旦所有節(jié)點(diǎn)的內(nèi)存si(t)是最新的，它就用于計(jì)算批處理中特定交互中使用的所有節(jié)點(diǎn)的“臨時(shí)節(jié)點(diǎn)嵌入”zi(t)。然后將這些節(jié)點(diǎn)嵌入到MLP或神經(jīng)網(wǎng)絡(luò)中，獲得每個(gè)事件發(fā)生的概率(使用Sigmoid激活)。這樣可以像往常一樣使用二進(jìn)制交叉熵(BCE)計(jì)算損失。

總結(jié)

上面就是我們對(duì)圖神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)總結(jié)，圖深度學(xué)習(xí)在處理具有類(lèi)似網(wǎng)絡(luò)結(jié)構(gòu)的問(wèn)題時(shí)是一個(gè)很好的工具集。它們很容易理解，我們可以使用PyTorch Geometric、spectral、Deep Graph Library、Jraph(jax)以及TensorFlow-gnn來(lái)實(shí)現(xiàn)。GDL已經(jīng)顯示出前景，并將繼續(xù)作為一個(gè)領(lǐng)域發(fā)展。