Parameter Sharing對於卷積

運算來講也是至關重要，因為如何sharing直接決定了參數的數量。在GCN可能更尤為重要了，因為graph上每個頂點的度都不一樣，所以不能按照CNN的方式來進行sharing。

這裡介紹三種目前較為流行的GCN模型。

1 Defferrard, M., Bresson, X., & Vandergheynst, P. (2016)

這裡的GCN運算可以寫成如下公式：

y=sigma left(U g_ heta(Lambda) U^T x ight) qquad(1)

g_ heta(Lambda)=sum_{j=1}^K alpha_j Lambda^j qquad(2)

公式中符號的定義與我之前的回答（如何理解 Graph Convolutional Network（GCN）？）保持一致，並且我推導了以上的運算等價於：

y=sigma left( sum_{j=1}^K alpha_j L^j x ight) qquad(3)

很明顯 alpha_j 是可學習的參數，可以看到 alpha_j 與 L^j 保持一致，我們知道 L^j 對應著 j 階neighbor，這意味著在同階的鄰居上參數共享（可以學習的參數相同），不同階的鄰居上參數不共享（可以學習的參數不同）。

舉個例子，具體信息還是同（如何理解 Graph Convolutional Network（GCN）？）

在下圖的graph上我們取 K=1,2 的卷積核，結果如下所示：

graph示意圖
卷積核（K=1）
卷積核（K=2）

我們可以看到，當 K=1 ，只有一個參數，即所有一階neighbor上學習的卷積係數都由共享的 alpha_1 控制，更高階的neighbor也沒有參與運算。

當 K=2 ，可以注意到所有一階neighbor上學習的卷積係數都由 alpha_1 和 alpha_2 控制，所有二階neighbor上學習的卷積係數都僅由 alpha_2 控制。

上述的例子與我們前面的分析完全相同。

總結一下優缺點：

優點：

  • 這樣的共享方式是有「物理意義」的，因為我們知道graph通常本身是有local stationary性質的。也就是說隨著neighbor階數的增加，頂點間的相關性遞減（相當於距離近的鄰域內相關性強）。這種共享方式，本質上可以很容易實現上述性質。
  • 參數很少，如果是超大規模的圖，可以利用這種方式。

缺點：

  • 參數太少了，只有 K 個，使得模型無法很好地實現在同階的鄰域上分配不同的權重給不同的鄰居（也就是GAT論文裏說的 enable specifying different weights to different nodes in a neighborhood）

2 Kipf, T. N., & Welling, M. (2016)

作者的blog可謂讓GCN一鳴驚人，其運算公式如下：

H^{l+1}=sigma left(hat D^{-frac{1}{2}} hat A hat D^{-frac{1}{2}} H^{l} W^l ight ) qquad(4)

H^{0}=x qquad(5)

其中 A 是graph的鄰接矩陣， hat A=A+I 是為了實現self-accessible， hat D 是 hat A 中每個頂點的度矩陣。

運算 hat D^{-frac{1}{2}} hat A hat D^{-frac{1}{2}} 是為了對 hat A 進行歸一化，防止在運算中出現數值不穩定的情況。

這個版本中，記 Y^l=hat D^{-frac{1}{2}} hat A hat D^{-frac{1}{2}} H^{l} ，這個運算可以理解為實現了空間信息的聚合，類似於下圖。其中第0層的輸入，是原始的特徵，以後每增加一層，就會多聚合一階neighbor上的信息（ l 層就對每個頂點融合了 l 階鄰域的信息）。

空間信息的聚合示意

很顯然模型可學習的參數是W^l ，Y^lW^l 進行了線性變換，我個人認為是實現了feature augment。也就是說模型在每一層共享了用於特徵增強的參數變化矩陣。矩陣W^l的兩個維度分別是 （ H^l 的第二個維度，根據特徵增強需要設計的維度（是超參數））。很顯然，這個矩陣維度與頂點數目或者每個頂點的度無關，於是說這是一個在同層內頂點上共享的參數矩陣。

總結一下優缺點：

優點：

  • 這樣的共享方式， W^l 的維度是可以進行調節的，與頂點的數目無關，使得模型可以用於大規模的graph數據集。另一方面這個模型可以完成圖結構train在test上不一樣的任務。

缺點：

  • 這個模型對於同階的鄰域上分配給不同的鄰居的權重是完全相同的（也就是GAT論文裏說的無法 enable specifying different weights to different nodes in a neighborhood）。這一點限制了模型對於空間信息的相關性的捕捉能力，這也是在很多任務上不如GAT的根本原因。

3 Zhang, Z., Li, M., Lin, X., Wang, Y., & He, F. (2019)

（這是我自己的一篇論文，Multistep speed prediction on traffic networks: A deep learning approach considering spatio-temporal dependencies，在19年7月31號前免費下載，感興趣的朋友可以看看。當然，這種運算模型也不是我提出的，在之前的論文中已有相似的內容）

我使用的GCN其實是一種不共享參數的形式，其計算具體如下：

A_{GC}^K=Ci left{ (A+I)^K ight} qquad(6)

y=(A_{GC}^Kodot W_{GC})cdot x qquad(7)

(A+I)^K 是為了構建一個 K 階可達的類鄰接矩陣， Ci(cdot) 是歸一化的運算元，防止出現數值不穩定的情況。 W_{GC} 是一個和graph鄰接矩陣維度相同的參數矩陣。

A_{GC}^Kodot W_{GC} 是一個逐位乘法，其作用相當於添加了一個mask矩陣，使得參數矩陣只在 K 階neighbor的位置上有參數，其餘位置均為0。

如果想直接感受一下，這是一種什麼樣的運算，可以在CNN上這樣類比：

CNN卷積核共享

CNN參數不共享示意

這裡的實現就相當於後者。

（更詳細的對比可以參考我的另一個回答如何理解卷積神經網路中的權值共享？）

總結一下優缺點：

優點：

  • 這樣的共享方式，在規模較小的graph數據集上極大地提高了對於空間相關性的刻畫能力，可以實現對於任意的鄰居分配任意的權重係數，也就是和GAT一樣可以 enable specifying different weights to different nodes in a neighborhood。
  • 學習完的參數矩陣具有可解釋性，這一點和GAT的相關係數 e_{i,j} 類似，通過分析 W_{GC}[i,j] 對於模型刻畫的空間相關性進行分析，然後再與真實的物理條件進行對比。我在論文中對於交通場景中的理解進行了較為細緻的分析，大家感興趣可以參考。

缺點：

  • 參數量與圖的規模有關，也就是說對於對於頂點數目為 N 的圖，其參數量為 N*N ，可以想像在大規模的數據集上，內存很可能會溢出。當然也無法在train和test階段graph結構不一樣的任務上應用。

最後總結一句：如果要在小規模圖數據上，實現具有可解釋性的圖卷積，那麼這種方式值得一試！

參考文獻：

Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. InAdvances in neural information processing systems(pp. 3844-3852).

Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks.arXiv preprint arXiv:1609.02907.

如果這個回答對於大家的科研有幫助，希望可以引用我們的論文

Zhang, Z., Li, M., Lin, X., Wang, Y., & He, F. (2019). Multistep speed prediction on traffic networks: A deep learning approach considering spatio-temporal dependencies.Transportation Research Part C: Emerging Technologies,105, 297-322.


推薦閱讀：
相關文章