2019年的時針開始轉動，在CNN、RNN、LSTM、GAN、GNN、CAP的潮起潮落中，帶來了這篇博客。放上一篇 參考引用 。 其實個人認為理解GNN的核心問題就是理解圖怎么做傅里葉變換。CNN的核心操作時卷積，GNN也是。CNN計算二維矩陣的卷積，GNN計算圖的卷積。那么我們定義好圖的傅里葉變換和圖的卷積就可以了，其媒介就是圖的拉普拉斯矩陣。

好了，這篇博客將簡要介紹圖神經網絡的原理，但是不會設計太多數學細節（因為博主數學很爛啦）。通過理解圖神經網絡的卷積操作，來理解其流程，再會配合代碼來做簡單解釋。

拉普拉斯矩陣

對于一個圖來說，其度為其與頂點鏈接的數量，Degree Matrix的對角線元素就是其每個頂點度的數量。鄰接矩陣表示了圖中各個頂點的鄰接關系。如下圖，一個圖的Laplace矩陣就是 L = D – A。

Laplace矩陣的計算

事實上，常用的Laplace矩陣有三種，上面介紹的只是其中一種。

Laplace矩陣有許多良好的性質：

1. Laplace矩陣是對稱矩陣，可以進行特征分解

2. Laplace矩陣只在中心頂點和一階相連頂點上有非0元素，其余處均為0

3. Laplace算子與Laplace矩陣進行類比

圖的傅里葉變換

推廣傅里葉變換

傳統的傅里葉變換針對連續的函數，然后對數列有了離散傅里葉變換，那么矩陣能否做傅里葉變換呢？這篇Paper告訴我們，可以，沒問題：https://arxiv.org/abs/1211.0053

L時拉普拉斯矩陣，V是其特征向量，滿足 LV=\lambda V

L的拉普拉斯譜分解為 L = U \sigma U^T

那么定義Graph上的傅里葉變換為Fourier（f） = U^T f

推廣卷積（f*h）_G = U（（U^Th）\odot（U^Tf））

那么時域上的卷積就是頻域點乘的傅里葉逆變換，這樣我們就可以實現卷積操作了。

理解拉普拉斯矩陣譜分解

傅里葉變換的本質，就是把任意一個函數表示成若干正交函數（由sin，cos構成）的線性組合。

傅里葉變換

拉普拉斯矩陣的特征值表示頻率。再graph空間上無法可視化頻率的概念，信息論告訴我們，特征值越大，對應的信息越多，小的特征值就是低頻分量，信息較少，是可以忽略的。

在壓縮圖像的過程中，也是把低頻成分變為0，高頻（邊緣）會被保留，它帶給我們更多的信息。

Deep Learning 中的 Graph Convolution

在卷積和中，需要手工設置K個參數，K具有很好的spatial localization，對應的有權重系數（這些具體的參數根據模型會有不同，這里大致介紹，重在理解）。更直觀的看，K=1就是對每個頂點上一階neighbor的feature進行加權求和，如下圖

K=1的情況

K=2的情況

GCN每次卷積對所有頂點都完成了圖示操作。

進一步在數學層面上理解Spectral Graph在GCN中的作用，這個就參考開頭給出鏈接中的paper吧。

OK，See You Next Time！