一、為什麼要研究圖卷積（GCN）？
CNN隻能處理 Euclidean Structure 的資料，如CV、NLP這些領域的資料，但無法處理 Non Euclidean Structure 的資料。真實世界中，大多數資料以圖或者網絡的形式存在，比如社交網絡，知識圖譜等。
Euclidean Structure 資料 與 Non Euclidean Structure 資料
二、CNN可以直接遷移到GCN嗎？
不能。因為 Non Euclidean Structure 的資料無法保持平移不變性。具體來說，由于在拓撲圖中每個頂點的相鄰頂點數目都可能不同，是以無法用一個同樣尺寸的卷積核來進行卷積運算。需要在圖上重新設計卷積的方法，而目前圖卷積方法主要分為兩大類：譜方法（Spectral Methods）和 空間方法（Spatial Methods）。
譜方法 ：大概思路是通過傅裡葉變換等将圖資料從空間域映射到譜域，然後在譜域實作卷積，最後再将處理後的信号映射回空間域。
空間方法 ：在空間域直接定義卷積， 這裡的卷積被定義為所有鄰居結點的權重平均函數。但主要問題是由于每個結點的鄰居大小不一樣，很難實作參數共享。
三、傳統傅裡葉變換與圖傅裡葉變換
3.1 圖拉普拉斯矩陣引入“譜” 這個概念的時候比較抽象，确實不好了解。可以簡單的認為
譜實際上就是對一個信号（視訊，音頻，圖像，圖）分解為一些簡單元素的線性組合（小波基，圖基）。如果這些分解的元素之間是線性無關的的（正交的），便可以作為信号的基。在信号進行中最常用的譜是傅裡葉變換，它提供了不同頻率下的正弦和餘弦波作為基，進而我們可以将信号在這些基進行分解。
為了滿足傅裡葉變換要求， 需要找到連續的正交基對應于傅裡葉變換的基。而圖上的拉普拉斯矩陣恰好滿足這些條件，它的特征值分解過程就是我們尋找構造圖所需的正交基的過程。
- 拉普拉斯是半正定實對稱矩陣, 對稱矩陣一定n個線性無關的特征向量
- 實對稱矩陣具有n個特征值,所對應的n個特征向量互相正交
- 半正定矩陣特征值非負
- n 階實對稱矩陣L必可對角化， 且可用正交矩陣對角化
拉普拉斯矩陣譜分解為：
, 其中
,
其中，
為
個特征值構成的對角矩陣，
是機關特征向量組成的矩陣且為正交矩陣，即
。
3.2 傳統傅裡葉變換傳統傅裡葉變換定義為：
逆變換為：
設
為節點的特征矩陣，
表示圖上第
個節點的特征。
為拉普拉斯矩陣
的特征向量矩陣，則特征值
(頻率) 所對應的特征向量
可作為傅裡葉變換中的一個正交基。是以，
Graph上的傅裡葉變換可以表示為：
逆變換為：
四、傳統傅裡葉卷積與圖卷積
傳統傅裡葉卷積：卷積定理：函數卷積的傅裡葉變換是函數傅立葉變換的乘積，即對于函數
與
兩者的卷積是其函數傅立葉變換乘積的逆變換:
證明如下：
設兩時域信号
,
，根據卷積的定義有：
傅裡葉變換為：
卷積定理在圖上也是成立的，設
為卷積核函數，
為結點的特征。則圖卷積可以表示為：
其中，
和
分别表示
和
傅裡葉變換的結果，
是 hadamard product（哈達馬積), 即這兩個向量進行内積運算(對應元素的乘積)。
由于卷積核可以通過學習或者設計得到，我們可将
的傅裡葉變換
寫成對角形式：
其中，
。
是以，圖卷積最終的結果可表示為：
五、圖卷積變換完整過程舉栗
給定一個圖
，其中
是節點集，
是邊集，
是權重鄰接矩陣。另外，每個結點有
維特征，
表示結點的特征矩陣。計算具體步驟如下：
- 計算得到圖拉普拉斯矩陣
, 其中
表示度矩陣。
2. 歸一化圖拉普拉斯矩陣
3. 求圖
的 Fourier basis
對
進行特征分解得到正交的特征向量集合（按照對應的特征值從大到小排序）作為圖的 Fourier basis。
4. 然後将圖的拉普拉斯矩陣對角化
, 其中
,
5. 得到圖的傅裡葉變換
對信号進行傅裡葉變換即
, 其中
6. 最後計算圖卷積
, 這裡的
表示譜域的卷積濾波器
參考資料：
Nango 明楠：圖卷積網絡GCN的了解與介紹zhuanlan.zhihu.com
劉浪：圖卷積神經網絡(GCN)詳解:包括了數學基礎(傅裡葉，拉普拉斯)zhuanlan.zhihu.com
圖圖：譜聚類方法推導和對拉普拉斯矩陣的了解zhuanlan.zhihu.com
如何了解 Graph Convolutional Network（GCN）？www.zhihu.com