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

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

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

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

https://arxiv.org/abs/1704.01212

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

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

讀取階段是更新步驟:

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

2、圖卷積

https://arxiv.org/abs/1609.02907

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

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

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

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

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

https://arxiv.org/abs/1710.10903

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

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

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

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

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

4、GraphSAGE

https://arxiv.org/abs/1706.02216

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

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

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

對于某一層l

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

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

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

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

https://arxiv.org/abs/2006.10637

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

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

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

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

每當(dāng)一個節(jié)點參與一個活動(節(jié)點更新或節(jié)點間交互)時，記憶就會更新。

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

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

總結(jié)

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