注：本文略過了大部分數學推導，防止掉頭髮，感興趣的可自行推導
GCN背景知識
傳統CNN只能處理比較簡單的序列或網格結構的資料。但是現實世界中很多都是非結構化的，通俗理解就是在拓撲圖中每個頂點的相鄰頂點數目都可能不同，那麼也無法用一個同樣尺寸的卷積核來進行卷積運算。
由於CNN無法處理Non Euclidean Structure的資料，但又希望在這樣的資料結構（拓撲圖）上有效地提取空間特徵來進行機器學習，所以GCN成為了研究的重點。
Spectral domain
是GCN的理論基礎，藉助圖譜的理論實現拓撲圖上的卷積操作，藉助拉普拉斯矩陣的特徵值和特徵向量研究圖的性質
Graph上的卷積計算用到了傅立葉變換，而Graph Fourier Transformation及Graph Convolution的定義都用到圖的拉普拉斯矩陣，首先介紹一下拉普拉斯矩陣。
拉普拉斯矩陣
對於圖G=（V， E） ，其Laplacian 矩陣的定義為$$L=D-A$$ ，其中 L 是Laplacian 矩陣，D是頂點的度矩陣（對角矩陣），對角線上元素依次為各個頂點的度， A是圖的鄰接矩陣。
$$L=D-A$$定義的Laplacian 矩陣更專業的名稱叫
Combinatorial Laplacian，上面的圖用的是這種計算方法
$$L^{sys}=D^{-1/2}LD^{-1/2}$$定義的叫
Symmetric normalized Laplacian
，很多GCN的論文中應用的是這種拉普拉斯矩陣
$$L^{rw}=D^{-1}L$$定義的叫
Random walk normalized Laplacian
為什麼GCN要用拉普拉斯矩陣？ 拉普拉斯矩陣矩陣有很多良好的性質，
拉普拉斯矩陣是對稱矩陣，可以進行特徵分解（譜分解），這就和GCN的spectral domain對應上了
拉普拉斯矩陣只在中心頂點和一階相連的頂點上（1-hop neighbor）有非0元素，其餘之處均為0
GCN的核心是基於拉普拉斯矩陣的譜分解，
其中L是拉普拉斯矩陣，U是正交矩陣，中間是n個特徵值
傅立葉變換和graph上的傅立葉變換
傳統的傅立葉變換定義為：
Graph上的傅立葉變換：
其中$$f（i）$$是Graph上的頂點$$i$$的向量，$$u_l（i）$$表示拉普拉斯矩陣的第$$l$$個特徵向量的第$$i$$個分量，$$u_l^{*}（i）$$是$$u_l（i）$$的共軛，$$\lambda_l$$就是第$$l$$個特徵值（
相當於傅立葉變換的頻率
）。
$$\hat{f}（\lambda_l）$$的意思就是求f在Graph上做傅立葉變換後，第$$l$$個特徵向量（
基底
）的分量
所以f在Graph上的傅立葉變換的矩陣形式為：$$\hat{f} = U^Tf$$，其中$$U$$是拉普拉斯矩陣的單位特徵向量的矩陣。
同理，f在Graph上的傅立葉逆變換的矩陣形式為$$f = U\hat{f}$$
Graph上的卷積計算
卷積定理：
函式卷積的傅立葉變換是函式傅立葉變換的乘積
Graph上的卷積核$$h$$是一個矩陣，下面就是f和h在圖上的卷積計算
其中，$$\hat{h}（\lambda_l） = \sum_{i=1}^Nh（i）u_l^*（i）$$是卷積核h在Graph上的傅立葉變換，$$U^Tf$$是f在graph上的傅立葉變換，左乘U是求逆變換
第一代GCN
paper連結
簡單粗暴地把$$diag（\hat{h}（\lambda_l））$$作為卷積核$$diag（\theta_l）$$
其中$$g_{\theta}（\Lambda）$$是卷積核，n是頂點個數，$$Ug_{\theta}（\Lambda）U^Tx$$就是卷積運算的結果，x是每個頂點的輸入向量，y是每一層的輸出
反向傳播擬合$$\theta_i$$。
缺點：
每次卷積計算需要計算三個矩陣相乘，複雜度為$$O（n^3）$$
幾乎所有卷積核都是稠密的，失去了cnn卷積核的空間區域性性。下圖是卷積核的例子，圖有6個節點
需要n個引數，容易過擬合
第二代GCN
paper連結
計算公式不變，把卷積核設計為
其中，$$\lambda_l^j$$為Graph的第$$l$$個特徵值的j次冪，L是Graph的拉普拉斯矩陣，即$$g_\theta（\Lambda） = \sum_{j=0}^K\alpha_j\Lambda^j$$
為什麼這麼設計？
卷積核從n個引數降低成K個引數，K是自定義的引數，K< 公式中的特徵矩陣U不需要計算了，不需要做特徵分解了。矩陣計算複雜度是$$O（K|E|）$$，其中|E|是邊數 卷積核有很好的空間區域性性，K代表了卷積核的感受域（回憶下拉普拉斯矩陣的定義），即每次卷積運算會將每個頂點距離為j的特徵進行加權求和，權值為$$\alpha_j$$。下面是單個頂點的卷積計算，其中f（i）表示第i個頂點的輸入向量 用這個矩陣左乘每個頂點的輸入向量即為卷積的運算結果。 缺點： 引數太少，並且不能對不同鄰居分配不同權重 第三代GCN 第二代卷積核： $$g_\theta（\Lambda） = \sum_{j=0}^K\alpha_j\Lambda^j$$ 用chebyshev多項式擬合卷積核中的$$\Lambda^j$$計算複雜度 第三代卷積積核： $$g_\theta（\Lambda） = \sum_{j=0}^K\alpha_jT_k（\hat{\Lambda}）$$ 其中$$T_k$$是Chebyshev多項式，$$\hat{\Lambda}=2*\Lambda/\lambda_{max}-I$$，$$\lambda_{max}$$是拉普拉斯矩陣特徵值的最大值 第四代GCN paper連結 第三代卷積計算（$$\theta_k$$是擬合的卷積核引數，L是拉普拉斯矩陣，$$\hat{L}=2*L/\lambda_{max}-I$$，x是頂點的輸入向量）： 取$$\lambda_{max}$$= 2，K = 2，有 為了避免過擬合，令$$\theta=\theta_0=-\theta_1$$ 模型訓練 每一層輸入輸出都是圖結構 以一個半監督文字分類任務為例子，下面這個GCN包括一個隱藏層 資料集是一個論文圖，共2708個節點，每個節點都是一篇論文，所有樣本點被分為7類別： Case_Based， Genetic_Algorithms， Neural_Networks， Probabilistic_Methods， Reinforcement_Learning， Rule_Learning， Theory 每篇論文都由一個1433維的詞向量表示，即節點特徵維度為1433。詞向量的每個特徵都對應一個詞，取0表示該特徵對應的詞不在論文中，取1則表示在論文中。每篇論文都至少引用了一篇其他論文，或者被其他論文引用，這是一個連通圖，不存在孤立點。 GCN在訓練的時候需要輸入整個圖，包括測試和驗證集樣本的結構。 GCN應用 半監督人群分類 空手道俱樂部是一個包含34個成員的社交網路，有成對的文件交互發生在成員之間。俱樂部後來分裂成兩個群體，分別以指導員（節點0）和俱樂部主席（節點33）為首，整個網路視覺化如下圖： 任務是預測每個節點會加入哪一邊。 文字分類 靜態結構圖的分類任務 預測使用者行為是否正常 GCN（128）->GCN（64）->GCN（64）->Linear（2） 人體動作識別 人體骨架作為節點 paper連結，連結2 多標籤影象識別 paper連結 影象檢索 。。。 GCN的侷限性： GCN在訓練的時候需要輸入整個圖，（如果一個節點代表一個樣本，要包括測試和驗證集的樣本），訓練的時候用到所有鄰居節點的資訊。 無法處理新來的節點（處理起來比較tricky），在現實某些任務中也不能實現(比如用今天訓練的圖模型預測明天的資料，但明天的節點是拿不到的） 無法處理動態圖問題 需要將整個圖放到記憶體和視訊記憶體裡，耗費資源 處理有向圖比較困難，無法分配不同權重給不同的鄰居 其他GNN： GAT，GraphSAGE，VGAE 附錄 上文講的只是GNN中的一小部分，感興趣的同學可以看看論文
