一、統一視角的 GNN

1、現有 GNN 傳播范式

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

首先其會將其鄰居節點 N (A) 的信息聚合成一個 h_N(A)⁽¹⁾，再和 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₁, F₂ 是可以自由設計的圖卷積核。當卷積核為單位矩陣 I 時，就相當于一個全通濾波器；當卷積核為 0 矩陣時就是低通濾波器，當卷積核為拉普拉斯矩陣 L 時就是高通濾波器。

優化目標的第二項形式上看是一個矩陣的跡，其作用是圖上的正則項，跡與正則有什么關系呢？其實第二項展開后是下面這個形式：

其含義是捕獲圖上任意兩個相鄰節點之間特征的差異程度，代表了一個圖的平滑程度。最小化這個目標就等價于讓我和我的鄰居更加相似。

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

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

當參數 ：

 時優化目標就變成了：

求偏導就得到：

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

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

當參數 F₁=F₂=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₁=F₂=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，再找到包含這種關系的所有節點 N^r 進行聚合，其中 W^r 是用來加權各種關系的權重。因此可以看到隨著圖中關系數目的增加，權重矩陣 W^r 也會跟著增加，這樣就會導致過度參數化的問題（Over-parameterization）。另外，將拓撲關系圖根據關系拆分的做法也會導致過平滑（Over-smoothing）。

2、CompGCN

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

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

每一次迭代也都會對 relation 的 embedding 進行更新。

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

三、集成多關系圖神經網絡

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

• 如何設計一個合適的集成優化算法
• 消息的傳遞機制
• GNN 模型是怎么設計的

1、集成優化算法

這個優化算法需要滿足兩方面要求：

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

我們在多關系圖上提出的集成的多關系圖正則項如下：

這個正則項也是要去捕捉圖信號的平滑能力，只不過這個鄰接矩陣是在關系 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，或者是權重矩陣 w_r 的參數量來比，我們這種參數量級幾乎是可以忽略不計的。下圖即為我們設計的模型架構：

其中 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：我們自己覺得嚴格的可解釋的數學推導是一種可靠的設計方法。