流行圖神經網絡總結

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

1、消息傳遞神經網絡

https://arxiv.org/abs/1704.01212

消息傳遞神經網絡(MPNN)將正向傳播分解為具有消息函數Ml的消息傳遞階段和具有頂點更新函數Ul的讀出階段

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

讀取階段是更新步驟:

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

2、圖卷積

https://arxiv.org/abs/1609.02907

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

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

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

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

3、圖注意力網絡

https://arxiv.org/abs/1710.10903

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

邊權值αij如下。

這里的Wa∈R2d '和W?Rd ' ×d為學習參數，d '為嵌入維數，⊕是向量拼接運算。

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

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

4、GraphSAGE

https://arxiv.org/abs/1706.02216

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

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

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

對于某一層l

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

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

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

5、時間圖網絡

https://arxiv.org/abs/2006.10637

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

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

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

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

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

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

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

總結

上面就是我們對圖神經網絡的數學總結，圖深度學習在處理具有類似網絡結構的問題時是一個很好的工具集。它們很容易理解，我們可以使用PyTorch Geometric、spectral、Deep Graph Library、Jraph(jax)以及TensorFlow-gnn來實現。GDL已經顯示出前景，并將繼續作為一個領域發展。