在上一篇文章中[1]，我們介紹了Graph Convolution Network的推導(dǎo)以及背后的思路等，但是，其實我們會發(fā)現(xiàn)，在傅立葉域上定義出來的GCN操作，其實也可以在空間域上進行理解，其就是所謂的消息傳遞機制，我們在本篇文章將會接著[1]，繼續(xù)介紹Message Passing機制。本文轉(zhuǎn)載自徐飛翔的“《Geometric Deep Learning學(xué)習(xí)筆記》第三篇，GCN的空間域理解，Message Passing以及其含義”

版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接和本聲明。

Message Passing與GCN

消息傳遞(Message Passing) 正如其名，指的是目的節(jié)點的鄰居，如Fig 1所示，紅色節(jié)點的鄰居正是藍色節(jié)點，這些鄰居節(jié)點根據(jù)一定的規(guī)則將信息，也就是特征，匯總到紅色節(jié)點上，就是所謂的信息傳遞了。

讓我們舉個信息匯聚的最簡單的例子，那就是逐個元素相加。假設(shè)我們的每個節(jié)點的特征為，那么有：

其中，表示的是節(jié)點的鄰居節(jié)點。

通常來說，我們會加入一個線性變換矩陣，以作為匯聚節(jié)點特征的特征維度轉(zhuǎn)換（或者說是映射）。有：

加入激活函數(shù)后有：

其實式子(1.3)可以用更為緊致的矩陣形式表達，為：

其中為鄰接矩陣，接下來我們以Fig 2的拓?fù)浣Y(jié)構(gòu)舉個例子進行理解。

此時假設(shè)我們的輸入特征為10維，輸出特征為20維，那么我們有：

那么進行運算的過程如：

我們不難發(fā)現(xiàn)，其實的結(jié)果乘上鄰接矩陣的目的其實在于選在鄰居節(jié)點，其實本質(zhì)就是在于鄰居節(jié)點的信息傳遞。因此信息傳遞的公式可以用更為緊致的式子(1.4)進行描述。但是我們注意到，如Fig 5的綠色框所示的，每一行的節(jié)點總數(shù)不同，將會導(dǎo)致每個目的節(jié)點匯聚的信息尺度不同，容易造成數(shù)值尺度不統(tǒng)一的問題，因此實際計算中常常需要用標(biāo)準(zhǔn)化進行處理，這正是[1]中提到的對拉普拉斯矩陣進行標(biāo)準(zhǔn)化的原因。

除了標(biāo)準(zhǔn)化的問題之外，式子(1.4)還存在一些需要改進的地方，比如沒有引入節(jié)點自身的信息，一般來說，比如二維卷積，像素中心往往能提供一定的信息量，沒有理由不考慮中心節(jié)點自身的信息量，因此一般我們會用自連接將節(jié)點自身連接起來，如Fig 6所示。

因此，鄰接矩陣就應(yīng)該更新為：

而度數(shù)矩陣更新為：

為了標(biāo)準(zhǔn)化鄰接矩陣A AA使得每行之和為1，我們可以令：

也就是鄰居節(jié)點的特征取平均，這里對這個過程同樣制作了個詳細(xì)解釋的圖。

我們可以看到，通過式子(1.7)，我們對鄰接矩陣進行了標(biāo)準(zhǔn)化，這個標(biāo)準(zhǔn)化稱之為random walk normalization。然而，在實際中，動態(tài)特性更為重要，因此經(jīng)常使用的是symmetric normalization [2,3]，其不僅僅是對鄰居節(jié)點的特征進行平均了，公式如：

同樣，這里我制作了一個運算過程圖來解釋。

對拉普拉斯矩陣進行對稱標(biāo)準(zhǔn)化，有：

這就是為什么在[1]中提到的拉普拉斯矩陣要這樣標(biāo)準(zhǔn)化的原因了。

所以，經(jīng)過了對稱標(biāo)準(zhǔn)化之后，我們的式子(1.4)可以寫成：

其中熟悉吧，這個正是根據(jù)頻域上ChebNet一階近似得到的結(jié)果來的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