前言

深度學(xué)習(xí)中大家熟知的幾種框架DNN、CNN蜗侈、RNN(LSTM和GRU)等等是為了處理歐式空間中的數(shù)據(jù)篷牌，如圖片、語音踏幻、文本枷颊。而圖神經(jīng)網(wǎng)絡(luò)可以應(yīng)用于更為豐富的拓撲結(jié)構(gòu)數(shù)據(jù)，如社交網(wǎng)絡(luò)该面、推薦系統(tǒng)夭苗、交通網(wǎng)絡(luò)等，這些數(shù)據(jù)的特點是具有無序的連接關(guān)系吆倦。
圖神經(jīng)網(wǎng)絡(luò)是受CNN的啟發(fā)听诸，并假設(shè)距離越近的兩個節(jié)點，它們的關(guān)系也更為親密蚕泽，試圖通過將節(jié)點的特征信息和節(jié)點之間的拓撲信息相結(jié)合的方式來進行節(jié)點預(yù)測、圖預(yù)測等任務(wù)桥嗤。

信號處理和傅里葉變換（基礎(chǔ)）

以波的形式傳遞的信號常常會通過傅里葉變換將其從時域空間轉(zhuǎn)到頻域空間進行處理须妻，下面以一個簡單的例子進行說明：對聲音進行變聲處理，可以分為以下幾步,

1.用傅里葉變換將聲波從時域轉(zhuǎn)換到頻域,
$F(w)=\int_{- \infty}^{+\infty} f(t)e^{-itw}dt$

左圖為聲波的時域圖泛领，右圖為頻域圖

2.對頻域圖進行濾波處理：即用某個函數(shù) $h(w)$ 與 $F(w)$ 相乘,

濾波后的頻域圖.png

3.將頻域進行逆傅里葉變換荒吏，重新變?yōu)槁暡?

F(t) = \int_{-\infty}^{+\infty}f(w)e^{itw}dw

變換后的時域圖

圖片轉(zhuǎn)自python基于傅里葉變換的頻率濾波－音頻降噪

注：傅里葉變換就是以 $e^{-iwt}$ 為基底， $f(t)$ 為系數(shù)的線性組合渊鞋。

圖基本定義

設(shè)G(V,E)绰更，V代表節(jié)點集合，共有N個節(jié)點锡宋；E代表邊集合儡湾，共有M條邊≈戳可以用連接矩陣A來表示一個圖的拓撲結(jié)構(gòu)信息,
$A = \left\{ \begin{aligned} &1 \ \ A_{ij} \in E\\ &0 \ \ A_{i,j} \notin E \end{aligned} \right.$
用D表示度矩陣徐钠，它是一個對角陣，對角線上的元素是節(jié)點的度數(shù),
$D_{ii} = \sum_j A_{ij}\$
拉普拉斯矩陣L的定義如下：
$L = D - A$

拉普拉斯矩陣

為了使大家能對GCN有更加直觀的理解役首，這里對拉普拉斯矩陣做幾點說明尝丐。

$(L x)_{i}=\sum_{j \in N(v_i)} (x_i - x_j)$ ，其中 $x \in R^N$ 衡奥， $N(v_i)$ 代表節(jié)點 $v_i$ 的一階鄰居節(jié)點集合爹袁≈狄溃可以看到 $L$ 矩陣是對圖中一階節(jié)點信息的簡單聚合操作晾剖。
$x^T L x = \sum_{e_{ij}\in E} (x_i - x_j)^2$ 顽腾，可以衡量一個圖中節(jié)點信息的差異性，該值越大缤弦，則信息差異也越大。且可以看出 $L$ 是對稱的半正定矩陣团赏。
常用的拉普拉斯矩陣是其規(guī)范化的形式： $L_{s} = D^{(- \frac{1}{2})} L D^{(- \frac{1}{2})}$ 胃珍，該矩陣通過特征分解得到的特征值，其范圍是[0,2)蛤迎。證明如下,
$Lemma$
$\lambda_{min} = min \frac{x^T B x}{x^T x},\\ \lambda_{max}=max \frac{x^T B x}{x^T x}$
其中 $\lambda_{min}$ 是矩陣 $B$ 的最小特征值确虱， $\lambda_{max}$ 是矩陣 $B$ 的最大特征值。
$Proof$
最小特征值為0可以從 $L_{s}$ 為半正定矩陣推出替裆，且其特征向量較易得出 $D^{\frac{1}{2}} I$ 校辩，下證其最大特征值<2,
$\begin{aligned} & \frac{x^TL_{s} x}{x^T x} \\ =& \frac{x^TD^{(- \frac{1}{2})} L D^{(- \frac{1}{2})}x}{x^T x} \\ =& \frac{y^TL y}{y^T D y} (令y=D^{- \frac{1}{2}}x) \\ =& \frac{\sum_{e_{ij} \in E} (y_i - y_j)^2}{\sum_{e_{ij} \in E}(y_i ^2 + y_j ^2)} \\ \leq & \frac{\sum_{e_{ij} \in E} 2(y_i ^2 + y_j ^2)}{\sum_{e_{ij} \in E}(y_i ^2 + y_j ^2)} = 2，得證 \end{aligned}$
特征分解：因為 $L$ 是一個對稱陣辆童，一定有一個正交陣 $V$ 宜咒，使得其對角化，對應(yīng)的對角矩陣為 $\Lambda$ ,
$VLV^T = \Lambda$
設(shè) $x \in R^N$ 把鉴，對其進行傅里葉變換,
$\tilde{x} = V^T x$
對其進行逆傅里葉變換：
$\begin{aligned} x =& V \tilde{x} \\ =& [v_1,...,v_N] \tilde{x} \\ =& \sum_{i=1}^{N} v_i \tilde{x}_i \end{aligned}$
其中特征向量 $v_i$ 為基底故黑，傅里葉系數(shù)為其線性組合的系數(shù)。

GCN

理論

GCN的計算過程與信號處理過程相同庭砍，先將卷積核和圖數(shù)據(jù)通過傅里葉變換轉(zhuǎn)換到頻域空間场晶，再對頻域空間的系數(shù)進行數(shù)值運算，最后進行逆傅里葉變換得到卷積后的結(jié)果怠缸。設(shè) $x \in R^N$ 是圖中節(jié)點的特征向量诗轻， $\theta$ 是待學(xué)習(xí)的參數(shù)，則一次圖卷積可以定義為,
$\begin{aligned} y=&F^{-1}(g(\theta) \circ F(x)) \\ =&F^{-1}(g(\theta)\circ V^Tx)\\ =&F^{-1}(diag(\theta)V^Tx) \\ =&Vdiag(\theta)V^Tx \end{aligned}$
其中 $F$ 代表傅里葉變換揭北， $F^{-1}$ 代表逆傅里葉變換扳炬， $g(\theta)=diag(\theta)$ ， $\circ$ 代表元素之間的點乘搔体。
從式子中可以看出待學(xué)習(xí)的參數(shù)是 $diag(\theta)恨樟，$ 共 $N$ 個，即和圖中節(jié)點的數(shù)目相關(guān)嫉柴，該方法難以適應(yīng)節(jié)點數(shù)量較多的圖（而這種情況在現(xiàn)實世界中更為常見）厌杜。那么可以使用多項式進行逼近，下面簡單介紹下切比雪夫多項式计螺。
$切比雪夫多項式遞推形式\left\{\begin{aligned} &T_0(x) = 1\\ &T_1(x) = x\\ &T_n(x) = 2x*T_{n-1}(x) - T_{n-2}(x) \end{aligned} \right. x\in[-1,1]$
則對應(yīng)的 $g(\theta)=\sum_{k=0}^{K}\theta_{k}'T_k(\tilde\Lambda)$ 夯尽，其遞推形式為,
$切比雪夫多項式遞推形式 \left\{\begin{aligned} &T_0(\tilde\Lambda) = 1\\ &T_1(\tilde\Lambda) = \tilde\Lambda\\ &T_n(\tilde\Lambda) = 2\tilde\Lambda*T_{n-1}(\tilde\Lambda) - T_{n-2}(\tilde\Lambda) \end{aligned} \right. \tilde\Lambda=\frac{2}{\lambda_{max}}\Lambda_s-I \in [-1, 1]$
對應(yīng)的 $y=\sum_{k=0}^{K}\theta_{k}'T_k(\tilde L)x$ ，其遞推形式為登馒，
$切比雪夫多項式遞推形式 \left\{\begin{aligned} &T_0(\tilde L) = 1\\ &T_1(\tilde L) = \tilde L\\ &T_n(\tilde L) = 2 \tilde L*T_{n-1}(\tilde L) - T_{n-2}(\tilde L) \end{aligned} \right. \tilde L=\frac{2}{\lambda_{max}}L_s-I \in [-1, 1]$
用一階切比雪夫多項式進行逼近匙握， $\lambda_{max} \approx2$ ，令 $\theta=\theta_0'=-\theta_1'$ 陈轿，
$\begin{aligned} y=&(\theta_0I+\theta_1\tilde L)x \\ =&(\theta_0I+\theta_1(L_s-I))x\\ =&(\theta_0I-\theta_1D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\\ =&\theta(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\\ \approx & \theta\tilde D^{-\frac{1}{2}}\tilde A \tilde D^{-\frac{1}{2}} x \end{aligned}$
其中 $\tilde D=D+I,\tilde A=A+I$ 圈纺。
進一步推廣秦忿，得到圖卷積的形式，設(shè) $X \in R^{n*m}$ 蛾娶， $m$ 是特征向量的維度灯谣， $W\in R^{m*d}$ ， $d$ 是輸出向量的維度蛔琅，
$Z=\tilde D^{-\frac{1}{2}}\tilde A \tilde D^{-\frac{1}{2}}XW$
paper：semi-supervised classification with graph convolutional networks

實踐(代碼)

使用cora數(shù)據(jù)進行實踐胎许，cora數(shù)據(jù)是一個論文引用關(guān)系網(wǎng)絡(luò)，節(jié)點代表一篇論文罗售，邊代表兩篇論文之間的引用關(guān)系辜窑；節(jié)點有7種分類，分屬于不同的學(xué)科寨躁。通過GCN對該數(shù)據(jù)進行節(jié)點分類任務(wù)穆碎。

訓(xùn)練誤差與測試誤差.png

最后對隱藏層的輸出進行t-sne可視化，得到

隱藏層的可視化.png

代碼：7nic7 GitHub

圖卷積神經(jīng)網(wǎng)絡(luò)(GCN)的理論與實踐

圖卷積神經(jīng)網(wǎng)絡(luò)(GCN)的理論與實踐

前言

信號處理和傅里葉變換（基礎(chǔ)）

圖基本定義

拉普拉斯矩陣

GCN

理論

實踐(代碼)