整合多關係圖神經網絡

一、統一觀點的GNN

#1、現有GNN 傳播範式

空域的GNN 是如何傳播的？如下圖所示，以節點A 為例:

首先其會將其鄰居節點N (A) 的資訊聚合成一個# h_N(A)^{(1 )}，再和A 其上一層的表示  h_N(A)⁽¹⁾ 進行組合，然後經過一個transformation 函數（即公式中的Trans(·)），就得到了A 的下一層表示 h_N(A)⁽²⁾。這個就是一個最基本的 GCN 的傳播典範。

#另外，還有一種解耦的傳播範式（decoupled propagation process）：

這兩種方式有什麼差別呢？ 解耦的傳播範式中會先用一個特徵提取器，也就是transformation 函數對初始的特徵進行提取，然後將提取後的特徵再放入聚合函數中進行聚合，可以看到這種方式將特徵的提取與聚合分開了，即做到了解耦。這樣做的好處在於：

• 可以自由的去設計前面的這個 transformation 函數，可以用任何的模型。
• 在聚合時可以增加很多層，來獲得更遠距離的連接信息，但是我們不會面臨過度參數化的風險，因為聚合函數中沒有需要優化的參數。

上面就是兩個主要的範式，而節點的embedding 輸出可以使用網路的最後一層，也可以使用中間層的殘差。

透過上面的回顧我們可以看到GNN 中有兩個基本的資訊來源：

• 網路的拓樸結構：一般可以捕捉圖結構的同配資訊屬性。
• 節點的特性：一般都會包含節點的低頻、高頻訊號。

2、一個統一的最佳化框架

#基於GNN 的傳播機制，我們可以發現，現有的GNN 有兩個共同的目標：

• 從節點的特徵去編碼有用的信息。
• 使用拓樸結構的平滑能力。

那麼能否用數學語言來描述這兩個目標呢？有人就提出了下面用公式表示的GNN 最佳化統一框架：

最佳化目標中的第一項：

 是特徵擬合項，它的目標是讓學習到的節點表示Z 盡可能與原始特徵H 接近，而 F_#1##, F2 是可以自由設計的圖卷積核。當卷積核為單位矩陣 I 時，就相當於一個全通濾波器；當卷積核為 0 矩陣時就是低通濾波器，當卷積核為拉普拉斯矩陣 L 時就是高通濾波器。

最佳化目標的第二項形式上看是一個矩陣的跡，其作用是圖上的正則項，跡與正則有什麼關係呢？其實第二項展開後就是下面這個形式：

其實是擷取圖上任兩個相鄰節點之間特徵的差異程度，代表了一個圖的平滑程度。最小化這個目標就等價於讓我和我的鄰居更相似。

3、用統一最佳化框架去理解現有GNN

GNN 大都是在優化這個目標，我們可以分不同的情況做下討論：

當參數：

 時最佳化目標就變成了：

求偏導就得到：

我們再來把上面得到的結果做進一步的展開就能得到：

它的意義就表示第K 層的所有節點表徵等於第K-1 層的節點表徵在鄰接矩陣上的傳播過程，一直推導到最後就會發現就等於初始的特徵X 做完特徵變換W* 之後在鄰接矩陣上傳播K 次。其實這就是去掉了非線性層的 GCN 或是 SGC 的模型。

當參數 F1_=F2_{=I，ζ=1，ξ=1/α-1， α∈（0,q] ，且選擇全通的濾波器時優化目標就變成了：}

這時我們同樣對Z 求偏導，並且令偏導等於0 就可以得到最佳化目標的閉式解：

#對結果稍作轉換就可以得到下面的式子：#​​

##我們可以發現上面的式子就代表了節點特徵在個人化PageRank 上傳播的過程，也就是PPNP 模型。

也同樣是這樣一個模型，如果用梯度下降的方式去求，並且設定步長為b，迭代項是k-1時刻目標函數對Z 的偏導值。

#當 

當 

## 

時可以得到：

這就是APPNP 模型。 APPNP 模型的出現背景是 PPNP 模型中求矩陣的逆運算太過複雜，而 APPNP 使用迭代近似的手段去解。也可以理解 APPNP 能收斂到 PPNP 是因為兩者來源自同一個框架。

4、新的GNN 框架只要我們設計一個新的適配項 O#fit

設計一個對應的圖正規項目 O

reg

#，再加上一個新的求解過程就可以得到一個新的GNN 模型。 ###############① 範例1：從全通濾波到低通濾波###############前面講過，全通濾波器下卷積核 #########F#########1#############=#########F################################### #####2############=#########I #########，當卷積核為拉普拉斯矩陣L時就是高通濾波器。如果將這兩種情況加權所得到的GNN 能encode 低通的資訊：################################################################## ###當 ###################

 可以精確解：

同樣，我們可以迭代求解：

#5、Elastic GNN

##前面的統一框架中提到的正規項相當於L2 正規則，相當於計算圖上任兩點之間的差異資訊。有研究者覺得 L2 正規過於全局化，會導致整個圖上的平滑程度趨於相同，這與實際上並不完全一致。於是就提出加入 L1 正規項，L1 正規項會對圖上變化比較大的地方懲罰比較小。

• #其中的L1 正規項部分為：
總之，上面的這個統一框架告訴我們：

我們可以用一個更宏觀的視角去理解GNN

#我們可以從這個統一框架出發去設計新的GNN

但是，這個統一框架還只能適合同質圖結構，接下來我們來看看更普遍的多重關係圖的結構。

二、關係GNN模型

#1、RGCN

所謂的多關係圖指的就是邊的種類大於1 的圖，如下圖所示。

#這種多關係圖在現實世界中非常廣泛，例如化學分子中的多類型的分子鍵，又如社交關係圖中人與人的不同關係。對於這樣的圖我們可以使用 Relational Graph Neural Networks 來建模。其主要想法是將具有 N 種關係的圖形單獨聚合，從而得到 N 個聚合結果，再將 N 個結果聚合。

# 用公式表示就是： ^{可以看到聚合分兩步驟進行，先從所有的關係R 中選擇一種關係r，再找到包含這種關係的所有節點} Nr 

###聚合，其中 ###W## #######r ######是用來加權各種關係的權重。因此可以看到隨著圖中關係數目的增加，權重矩陣 ###W#########r ######也會跟著增加，這樣就會導致過度參數化的問題（ Over-parameterization）。另外，將拓樸關係圖根據關係分割的做法也會導致過平滑（Over-smoothing）。 ##########

2、CompGCN

為了解決過度參數化的問題，CompGCN 用了一個向量化的關係編碼器來取代N 個關係矩陣：

 #編碼器包含正向、反向、自環三種方向的關係：

#每一次迭代也會更新relation 的embedding。

但這種啟發式的設計，以及這樣的參數化編碼器同樣也會造成過度的參數化。那麼，基於上述的考量就得到了我們工作的出發點：能否從優化目標的角度設計一個更可靠的 GNN，同時能夠解決現有 GNN 存在的問題。

三、整合多關係圖神經網路

#我們的EMR GNN 在今年發表，接下來主要從三個面向展開討論我們如何設計一個適用於多重關係圖的GCN：

• 如何設計一個合適的整合最佳化演算法
• #訊息的傳遞機制
• #GNN 模型是怎麼設計的

#1、整合最佳化演算法

這個最佳化演算法需要滿足兩個面向要求：

• 能夠同時捕捉圖上的多種關係
• #能夠建模出圖上不同關係的重要性

我們在多重關係圖上提出的整合的多重關係圖正規項目如下：

這個正規項也是要去捕捉圖訊號的平滑能力，只不過這個鄰接矩陣是在關係r 下去捕獲的，而受歸一化約束的參數 μ_#r##r

則是為了建模某種關係的重要性。而第二項是係數向量的二範式正則，是為了讓係數向量更均勻。

而為了解決過平滑的問題我們又加了一個擬合項，來保證原始的特徵資訊不會被遺失。擬合項與正規項目加起來就是：

#####################與上一章提到的統一框架相比，我們這裡設計的目標函數包含節點矯正Z 和關係矩陣參數 μ 兩個變數。那麼基於這樣一個優化目標去推導得到一個訊息傳播機制也是一個挑戰。 ##########

2、推導訊息傳遞機制

在這裡我們採用的是迭代優化的策略：

• 先固定節點表徵Z，再去最佳化參數μ
• #依照上一個步驟迭代的結果μ 再去最佳化節點表徵Z

當固定節點表徵Z 時，整個最佳化目標就會退化成只跟μ 相關的一個目標函數，但是這是一個帶約束的目標函數：

#這其實是單純形約束（constraint in a standard simplex）上的一個μ 的convex函數，對於這類問題我們可以使用鏡像熵梯度下降演算法（Mirror Entropic Descent Algorithm）去解決。我們會先求出一個常數，然後再對每一種關係下的權重係數進行更新，整個更新的過程類似指數的梯度下降演算法。

#固定關係係數μ 去更新Z，這時的最佳化目標就退化成下面這種形式：

#這樣我們求目標函數對Z 的偏導數，並且令偏導數等於0 就可以得到：

#那麼Z 的閉式解就是：

#同樣我們可以用迭代的方式去得到近似解，這個過程可以表示如下：

#從推導出的訊息傳遞機制我們可以證明該設計可以避免過度平滑，避免過度參數化，下面我們可以看下證明的過程。

原始的多重關係PageRank 矩陣是這樣定義的：

個人化的多重關係PageRank 矩陣在此基礎上加了一個返回自身節點的機率：

透過解上面的迴圈等式就可以得到多重關係個性化PageRank 矩陣：

我們讓:

#

 就可以得到：

##這個也就是我們提出方案所得到的閉式解。也就是說我們的傳播機制可以等價於特徵 H 在節點的個人化 PageRank 矩陣上進行傳播。因為這個傳播機制中一個節點可以有一定的機率返回自身節點，也就是說在訊息傳遞過程中不會失去自身訊息，從而防止過度平滑的問題。

另外，我們這個模型也緩解了過度參數化這個現象，因為從公式中可以看到，對於每一種關係我們的模型只有一個可學習的係數 μ_#r ##，相較於之前的encoder，或是權重矩陣 wr _{的參數量來比，我們這個參數量級幾乎是可以忽略的。下圖即為我們設計的模型架構：}

#其中RCL 即為參數學習的步驟，而Pro 步驟為特徵傳播的步驟。這兩個步驟放在一起就構成了我們的訊息傳遞層。那麼如何把我們的訊息傳遞層整合到 DNN 中，且不引入額外的更多參數呢？我們也沿用了解耦的設計思路：先用一個 MLP 對輸入特徵進行提取，之後經過多層我們所設計的消息傳遞層，疊加多層同樣不會導致過平滑。最終的傳遞結果經過 MLP 完成節點分類即可做下游的任務。用公式將上述過程表示如下：

f(X;W) 就表示將輸入特徵經過MLP 做特徵提取，後面的EnMP(K) 則表示將提取結果經過K 層的消息傳遞，gθ #則表示經過一個分類的MLP。

反向傳播中我們只用更新兩個MLP 中的參數即可，而我們的EnMP 中的參數是在前向傳播過程中學習的，後向傳播過程中不用更新EnMP 任何的參數。

我們可以比較看下不同機制的參數量，可以看到我們的EMR-GNN 的參數量主要來自於前後兩個MLP，以及relation的係數。當層數大於 3 時我們就可以知道 EMR-GNN 的參數量比 GCN 的參數量還要少，更是比其他異質圖還要的少了。

在這麼少的參數量下我們的EMR-GNN 如下不同的節點分類任務下還是可以達到最好的水準。

#

此外，我們也比較了不同的網路結構在層數增加後分類精度的變化，如下圖所示，當層數增加到64 層後我們的模型依然能夠保持較高的精度，而原始的RGCN 當層數增加到16 層以上時就會遇到內存不夠的情況，想要迭加更多層更是不可能的，這就是由於其參數過多導致的。而 GAT 模型則因過平滑而表現性能降低。

#此外我們也發現，我們的EMR-GNN 在較小的資料規模下即可達到全樣本的分類精度，而RGCN 則下降很多。

我們也分析了 EMR-GNN 所學到的關係係數μr是否真的有意義，那麼什麼算有意義呢？我們希望關係係數 μ_#r ##關係係數給重要的關係更大的權重，給予不重要的關係更小的權重。我們分析的結果如下圖所示：

#其中綠色的長條圖表示在一種關係下分類時的效果，如果在某種關係下其分類精度更高，我們就可以認為該關係時重要的。而藍色柱子則表示我們的 EMR-GNN 所學習到的關係係數。藍綠對比可以看到我們的關係係數能夠反映出關係的重要性。

最後我們也做了一個視覺化展示如下圖：

可以看到EMR-GNN 訓練出來的節點embedding 能夠帶有節點的結構化訊息，它能夠讓同一類別的節點更加內聚，不同類別的盡可能分開，分割邊界相對其他網路更清晰。

四、總結

1. 我們用統一的觀點去理解GNN

    ① 在這個視角下我們可以很容易看出現有GNN 有什麼問題

    ②這個統一觀點可以給我們一個重新設計GNN 的基礎

2. 我們從目標函數的角度嘗試設計一個新的多重關係的GNN

    ① 我們首先設計了一個整合的最佳化框架

    ② 基於這樣一個最佳化框架我們推導出來了一個訊息傳遞機制

####    ③ 這個帶有少量參數的訊息傳遞機制簡單地與MLP 結合即可得到EMR-GNN###############3. EMR-GNN 有什麼好處？ ###############    ① 它依賴一個可靠的最佳化目標，因此得到的結果可信，從數學上也能解釋其底層的原理########## #########    ② 它可以解決現有的Relation GNN 的過平滑問題#################    ③ 解決參數化問題##### #####

    ④ 容易訓練、在較小的參數量下可得到較好的效果

五、Q&A環節

Q1：關係係數的學習與attention 機制有什麼不同嗎？

A1：這裡的關係係數學習是透過最佳化框架推導出來的更新過程，而attention 是需要基於反向傳播才能學習到的過程，所以說在優化上兩者就有本質不同。

Q2：在大規模資料集上模型的適用性如何？

A2：我們在附錄中分析了模型的複雜度，從複雜度上說我們和RGCN 是一個量級的，但是參數量會比RGCN 更少，因此我們的模型更適用於大規模資料集。

Q3：這個框架能融入邊的訊息嗎？

A3：可以在擬合項或正規項中融入。

Q4：這些數學基礎該從哪裡學？

A4：一部分是基於前人的工作，另外一部分優化相關的數學理論我們用的也是一些比較經典的最佳化方面論文。

Q5：關係圖和異構圖的差異在什麼地方？

A5：關係圖是一種異構圖，只不過異構圖我們都通常認為是哪些節點的型別或邊的型別大於 1 的。而關係圖我們特別關注的是關係的類別大於 1，可以理解後者包括前者。

Q6：能否支援 mini-batch 的訓練？

A6：支援。

Q7：未來 GNN 的研究方向是否更傾向於嚴格的、可解釋的數學推導，而非啟發式的設計。

A7：我們自己覺得嚴格的可解釋的數學推導是一種可靠的設計方法。

#

以上是整合多關係圖神經網絡的詳細內容。更多資訊請關注PHP中文網其他相關文章！