在上一篇文章中[1]，我們介紹了Graph Convolution Network的推導以及背后的思路等，但是，其實我們會發現，在傅立葉域上定義出來的GCN操作，其實也可以在空間域上進行理解，其就是所謂的消息傳遞機制，我們在本篇文章將會接著[1]，繼續介紹Message Passing機制。本文轉載自徐飛翔的“《Geometric Deep Learning學習筆記》第三篇，GCN的空間域理解，Message Passing以及其含義”
版權聲明：本文為博主原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
Message Passing與GCN
消息傳遞(Message Passing) 正如其名，指的是目的節點的鄰居
，如Fig 1所示，紅色節點
的鄰居正是藍色節點
，這些鄰居節點根據一定的規則將信息，也就是特征，匯總到紅色節點上，就是所謂的信息傳遞了。
讓我們舉個信息匯聚的最簡單的例子，那就是逐個元素相加。假設我們的每個節點的特征為，那么有：
其中，表示的是節點
的鄰居節點。
通常來說，我們會加入一個線性變換矩陣，以作為匯聚節點特征的特征維度轉換（或者說是映射）。有：
加入激活函數后有：
其實式子(1.3)可以用更為緊致的矩陣形式表達，為：
其中為鄰接矩陣，接下來我們以Fig 2的拓撲結構舉個例子進行理解。
此時假設我們的輸入特征為10維，輸出特征為20維，那么我們有：
那么進行運算的過程如：
我們不難發現，其實的結果乘上鄰接矩陣
的目的其實在于選在鄰居節點，其實本質就是在于鄰居節點的信息傳遞。因此信息傳遞的公式可以用更為緊致的式子(1.4)進行描述。但是我們注意到，如Fig 5的綠色框所示的，每一行的節點總數不同，將會導致每個目的節點匯聚的信息尺度不同，容易造成數值尺度不統一的問題，因此實際計算中常常需要用標準化進行處理，這正是[1]中提到的對拉普拉斯矩陣
進行標準化的原因。
除了標準化的問題之外，式子(1.4)還存在一些需要改進的地方，比如沒有引入節點自身的信息，一般來說，比如二維卷積，像素中心往往能提供一定的信息量，沒有理由不考慮中心節點自身的信息量，因此一般我們會用自連接將節點自身連接起來，如Fig 6所示。
因此，鄰接矩陣就應該更新為：
而度數矩陣更新為：
為了標準化鄰接矩陣A AA使得每行之和為1，我們可以令：
也就是鄰居節點的特征取平均，這里對這個過程同樣制作了個詳細解釋的圖。
我們可以看到，通過式子(1.7)，我們對鄰接矩陣進行了標準化，這個標準化稱之為random walk normalization。然而，在實際中，動態特性更為重要，因此經常使用的是symmetric normalization [2,3]，其不僅僅是對鄰居節點的特征進行平均了，公式如：
同樣，這里我制作了一個運算過程圖來解釋。
對拉普拉斯矩陣進行對稱標準化，有：
這就是為什么在[1]中提到的拉普拉斯矩陣要這樣標準化的原因了。
所以，經過了對稱標準化之后，我們的式子(1.4)可以寫成：
其中熟悉吧，這個正是根據頻域上ChebNet一階近似得到的結果來的GCN表達式，因此GCN在空間域上的解釋就是Message Passing。
Reference
[1].https://blog.csdn.net/LoseInVain/article/details/90171863
[2].https://people.orie.cornell.edu/dpw/orie6334/lecture7.pdf
[3].https://math.stackexchange.com/questions/1113467/why-laplacian-matrix-need-normalization-and-how-come-the-sqrt-of-degree-matrix