從圖(Graph)到圖卷積(Graph Convolution)：漫談圖神經網絡模型 (二)(https://www.cnblogs.com/SivilTaram/p/graph_neural_network_2.html)
該文詳細寫明了設涉及的參考材料，是一個很棒的綜述性材料。本文僅作為閱讀該系列文章的筆記，詳情請參考原文。
參考博文2:稍微簡略一些，建議看完《漫談圖神經網絡模型 (二）》再去看此文，最終講到不需要做特征值分解的GCN，有點神奇。
https://blog.csdn.net/qq_41727666/article/details/84622965

此前的圖神經網絡是基于循環結構，此篇主要介紹基于圖卷積神經網絡中的卷積操作。

1.卷積是什么

卷積本身是一種數學算子，對兩個函數f和g操作，生成第三個函數h。
$$h(t)={\int }_{?\infty }^{\infty }f(\tau )g(t?\tau )d\tau$$

即：新函數在t處的值=f 和g 關于t對稱處函數值成績的和。簡單(抽象)地說就是一個加權求和的過程。了解加權求和的核心之后，可以建模出圖像上的卷積操作。每一層的卷積核就是一個權重可學習的權值函數$g(?)$。

卷積核的權重可以依據任務確定：實現邊緣提取laplacian算子、可依據損失函數學習特定特征提取的權重。

卷積操作的作用：通過結點和周圍結點的信息，提取/聚合結點的特征。

小結：在機器學習領域，卷積的具體操作是加權求和，卷積的效果是特征聚合/提取。

2.圖卷積的源起

圖像卷積操作要求規整的數據結構，圖上結點的鄰居結點數量不固定。

衍生了兩種特征聚合圖結點的特征的操作：

1. 把圖轉換成規整的結構–少數
2. 處理變長鄰居結點的卷積核–主流，主要焦點

圖卷積又分為空域卷積和頻域卷積：

1. 空域卷積–卷積核直接在原圖上卷積操作
2. 頻域卷積–圖做了傅立葉變換之后再進行卷積操作

啟發：一種最簡單的無參卷積–將所有的鄰居結點的隱藏狀態加和，以更新當前結點的隱藏狀態。

3.空域卷積

3.1消息傳遞網絡MPNN

Massage Passing Neural Network–MPNN，空域卷積的形式化框架。他將空域卷積分解為兩個過程：消息傳遞$M_l(?)$和狀態更新$U_l(?)$
$$h_v^{l+1}=U_{l+1}(h_v,\sum _{u\in ne[v]}{M}_{l+1}(h_v^l,h_u^l,x_{uv}))$$
即本結點與鄰居結點的信息通過$M_l(?)$形成消息，將所有的消息類和后，然后通過狀態更新函數$U_l(?)$更新自己的隱狀態。

GCN：每一層包含所有結點，每層的MU參數并不共享，層數由設計確定
GNN：按更新時間序列展開成，各層的MU參數共享，每一次更新所有的結點，按不動點理論，時間序列的長度不定。

MPNN主要缺陷：卷積操作針對整張圖，所有結點都要進內存。大規模圖上的全圖卷積操作并不現實。

3.2 圖采樣與聚合GraphSage

采樣部分結點進行學習，

1. 每一層的消息傳遞和狀態更新不涉及所有結點，隨機采樣若干個結點。
2. 針對每個結點，隨機選取固定數目的鄰居結點，（1階/2階均可）
3. 定義aggregate函數聚合鄰居結點的信息
4. 計算采樣點處的損失

GraphSage狀態更新公式：
hvl+1=σ(Wl+1?aggregate(hvl,{hul}),?u∈ne[v])h_v^{l+1}=\sigma(W^{l+1}*aggregate(h_v^l,\{h_u^l\}),\forall u \in ne[v])hvl+1?=σ(Wl+1?aggregate(hvl?,{hul?}),?u∈ne[v])

GraphSage的設計重點在于aggregate函數的設計上。

4.頻域卷積

(理解起來稍微有一點抽象)–利用傅立葉變換在圖上的抽象來實現圖上卷積操作。
傅立葉變換：將一個在空域上定義的函數分解成頻域上的若干頻率成分。
$$\hat{f}(t)=\int f(x){\exp }^{?2\pi ixt}dx$$

傅立葉變換恒等式：兩個函數在空域上的卷積的效果，等于兩函數在頻域上的乘積。
$$(f?g)(t)=F^{?1}[F[f(t)]\odot F[g(t)]]$$

所以：可以利用傅立葉變換，得到頻域表示后，進行哈達瑪乘積，再傅立葉逆變換回去，即可得到空域卷積的結果。

傅立葉變換的作用：

1. 去規律的噪點
2. 加速卷積操作（卷積核比較小時沒啥加速效果）

利用傅立葉變換實現圖上卷積的核心點：如何找到變換算子${\exp }^{?2\pi ixt}$。

依據變換算子是拉普拉斯算子的特征函數這一重要特性，找到圖數據拉普拉斯變換算子–拉普拉斯矩陣對應的特征向量。

(頻域卷積的前提條件-圖是無向圖。)
圖拉普拉斯矩陣的特征值分解：
$$L=U\Lambda U^T$$
$$U=(u_1,u_2,...,u_n)$$
$$\Lambda =diag({\lambda }_1,{\lambda }_2,...,{\lambda }_n)$$

圖結點數據傅立葉變換:$\widehat{(}f)(t)={\sum }_{n=1}^{N}f(n)u_t(n)$ 這個疊加的n是個什么東西？N個結點的信息

整張圖的傅立葉變換:$$\hat{f}=?\begin{array}{c}\hat{f}(1)\\ ...\\ \hat{f}(N)\end{array}?=U^{T}f$$
用神經網絡建模卷積核傅立葉變化后的函數，用$g_{\theta }$表示，那么頻域卷積可以表示為：
$$g_{\theta }\odot U^{T}f$$

再通過傅立葉逆變換可以求得，最終圖上的卷積。(逆變換算子為${\exp }^{2\pi ixt}$，類比圖中的逆變換算子為U)：
$$o=(f?g{)}_{\theta }=U{g}_{\theta }{U}^{T}f$$

圖上頻域卷積的工作，都聚焦于$g_{\theta }$的設計。頻域卷積，隱狀態更新涉及:

1. $l$層隱狀態$h^l\in R^{N?d_l}$，每一行為該層一個結點的隱藏狀態：
   $$h^l=?\begin{array}{cccc}{h}_{11}^l& h_{12}^l& ...& h_{1d_l}^l\\ ...& & & \\ h_{N1}^l& h_{N2}^l& ...& h_{N{d}_l}^l\end{array}?$$
2. 傅立葉變換算子$U^T$,每一行是拉普拉斯矩陣的一個特征向量:
   $$U^T=?\begin{array}{cccc}{u}_{11}& u_{12}& ...& u_{1N}\\ ...& & & \\ u_{N1}& u_{N2}& ...& u_{NN}\end{array}?$$
3. 卷積核頻域形式$g_{\theta }:d_{l+1}?N$,參數化唄,還就是一個權重呀(沒說明白怎么作用的呀,后面再看看吧)：
   $$g_{\theta }=?\begin{array}{ccc}{\theta }_1& ...& 0\\ ...& ...& ...\\ 0& ...& {\theta }_N\end{array}?$$

頻域卷積，隱狀態更新公式,{:i}表示第i列,$(i=1,...,d_l),(j=1,...,d_{l+1})$：
$$h_{:,j}^{l+1}=\sigma (U\sum _{i=1}^{d_L})g_{\theta }{U}^T{h}_{:,i}^l$$

切比雪夫網絡用來加速特征矩陣的求解。

5.圖結構的序列化-Patch-SAN

Patch-SAN：將圖轉化成序列結構，然后利用卷積神經網絡在序列化結構上作卷積。
Patch-SAN原文中主要涉及圖分類任務。

圖結構的特點：

1. 同構
2. 鄰居結點的連接關系

圖結構-》序列化結構要求
3. 同構圖產生的序列應當是相似的
4. 保持鄰居結點和目標結點的距離關系

Patch-SAN 通過三個規則來將圖轉化成一個長度為$w?(k+1)$的序列，然后直接使用1D卷積對該序列進行操作。