❶ 如何做出漂亮的復雜網路關系圖
想要繪制出復雜又漂亮的網路圖，選擇一款合適的軟體很重要，否則可能需要耗費大量時間和精力去畫了。目前用的比較多的兩款用來畫網路圖的工具：visio和edraw 億圖。這兩款軟體用於畫網路圖都很不錯，windows系統的可以兩個都試一下，mac和linux系統的可以用edraw。
❷ 第一代圖卷積網路：圖的頻域網路與深度局部連接網路
本文需要的前置知識：傅里葉變換與譜圖理論基礎
鏈接：
① 傅里葉級數與傅里葉變換
② 圖神經網路中的譜圖理論基礎
CNN在機器學習領域內的一些問題上取得了比較成功的效果，這主要得益於它處理的底層數據通常有一個坐標網格結構（在1，2，3維度上），因此這些數據就存在平移不變性（ translational equivariance/invariance）。圖像、語音、視頻就屬於這一類數據。由於網路不具備平移不變性（網路中的每個節點的鄰居數量是不固定的），因此在網路上直接應用CNN是比較困難的。
對於常規的網格數據，CNN能夠利用以下幾個很好地結合在一起的結構來大大減少系統中的參數數量：
①平移結構（translation structure），使用濾波器在數據的網格結構上平移處理數據，從而實現參數共享，並沒有使用線性映射；
②網格上的度量，使用緊湊支持濾波器（compactly supported filters），緊湊支持濾波器是指與輸入數據大小無關的濾波器，它的大小可能遠小於輸入數據的大小；
③網格的多尺度二元聚類（multiscale dyadic clustering），是指CNN應用了跨步卷積（stride convolution）和池化（pooling）來進行下采樣（subsampling）。
如果網格數據有 個坐標，數據的維度為 （舉例來說，圖片的坐標數就是像素點數，維度就是圖片的通道數，彩色圖為 ，灰度圖為 ），如果使用有 的輸出節點的全連接網路就需要 個參數，相當於 的參數復雜度。使用任意的濾波器（也就是①）而非全連接網路能將參數復雜度降低到 ，使用網格上的度量結構（也就是②）來構建局部連接網路也可以。而如果兩種一起使用能夠將復雜度降低到 ，這里的 代表數據feature map的數量， 代表卷積核的數量，此時復雜度與 無關。最後使用網格的多尺度二元聚類（也就是③）可以進一步降低復雜度。
然而某些數據並不具備上述幾何結構，比如表面張力或溫度、從一個氣象台網路中觀測到的數據、來自社交網路或協同過濾的數據，這些數據都不能直接應用CNN。雖然CNN可以應用於多層，但是在特徵維度上沒有假設任何幾何屬性，導致一個4-D tensor只能沿其空間坐標進行卷積，即對於一個4-D的tensor而言，其有 四個維度，典型的CNN只能對 三個維度（即空間維度）進行卷積操作（通過3D convolution 操作），而不能對 維度（特徵維度）進行操作。
網路提供了低維網格數據的一種泛化的框架，也就是GCN是CNN在domain上的推廣，推廣的方式是通過推廣卷積的概念。在本文中將會討論將深度卷積應用於網路數據的方法。本文一共提供兩種架構。第一種為空域架構（spatial construction），這種架構能夠對網路數據應用上述②和③，應用它們可以構建網路數據的局部連接網路，參數復雜度為 而非 。另一種架構稱為頻域架構（spectral construction），能夠在傅里葉域內應用卷積。頻域架構對於每一個feature map最多需要 的參數復雜度，也可以構建參數數量與 無關的架構。這兩種架構都可以應用高效的前向傳播並且能夠應用在有多個坐標的數據的數據集上。
網路數據將由一個加權圖 來表示， 是一個離散的節點集合，大小為 ， 是一個對稱半正定矩陣，也就是加權鄰接矩陣。將CNN泛化到網路數據的最直接想法是應用多尺度的、層級的局部感受野。
在網路上可以輕松的定義局部性（locality）的概念。邊的權重決定了節點的局部性，舉例來說，可以設置一個閾值 來決定一個節點的鄰居節點集合：
我們可以將注意力限制在稀疏的濾波器上，這些濾波器通過節點的鄰居節點集合來定義感受野，以此來構建局部連接網路，這樣可以將參數量降低為 ，這里的 代表平均鄰居節點數量。
CNN通過池化和下采樣來降低網格的大小，這一操作也就是網格的多尺度聚類（ multiscale clustering）：為每個cluster輸入多個特徵，輸出一個特徵。在圖上被證明更為有效的聚類方法仍然有待研究，在本文中選擇了一種比較樸素的聚類方法。如下圖所示，下圖中有兩層聚類，灰色的點為數據中的無向圖節點，然後進行聚類得到下一層帶顏色的節點，然後再對這些帶顏色的節點進行聚類，第一層為12個節點，第二層6個節點，第三層3個節點：
本文提出的空域架構也叫做深度局部連接網路（Deep Locally Connected Networks）。在這個架構中使用了網路的多尺度聚類，事實上這里的尺度可以認為是下采樣的層數，在這里我們考慮 個尺度，實際上也就是說這個架構由 個卷積層，每個卷積層後面都有一個池化層（也就是進行一次聚類），因此這個架構中總共有 層，每層包括一個個卷積層和一個池化層。
我們設置 ，也就是輸入層的節點集合，可以認為是第0層，每一層的節點集合記作 ，這里 ， 可以認為是將 聚成 個簇的一個劃分，因此 就表示第 層的節點個數，有 。另外定義 的節點的鄰居節點集合的表示：
注意這里 的下標雖然為 ，但它代表的是第 的節點集合 的每個節點的鄰域的表示，裡面的每個 都是一個集合。
有了上述定義現在我們可以定義網路的第 層。假設輸入信號是 上的實值信號，以 來代表第 層的卷積核的數量，也代表了第 層feature map的數量和信號的維度（類比CNN，卷積核的數量等於feature map的數量，也就是卷積後的信號特徵的維度）。每一層都會將 上的 維的信號轉換成 上的 維的信號，這一過程會權衡空間解析度和新創建的特徵坐標，也就是說，雖然經過每一層的節點數量降低了，但是卷積核的數量會逐層增加以保證特徵的維度會增加，也就是說每層有兩個結果：
①空間解析度降低（loses spatial resolution），即空間點數減少；
②濾波器數目增加（increases the number of filters），即每個點特徵數 增加。
第 層的輸入用 來表示，這里的 是一個 的矩陣， 可以認為是一個列向量， 也就相當於第 個feature map的信號。那麼第 層的輸出 就被定義為：
這里的 代表第 層的第 個卷積核對第 層的第 個feature map進行卷積的部分，注意由於圖的節點的鄰居分布情況不同，所以卷積核不像CNN那樣是共享的。這里的 是一個 的稀疏矩陣，矩陣的第 行的非零值都只會存在於 所指定的第 個節點的鄰居節點位置。 代表非線性激活函數。 代表對卷積的結果進行之前所述的池化操作來降低節點的數量， 相當於聚類的結果，是一個 的稀疏矩陣，每一行指示一個簇的分布，如果採用平均池化，那麼 的一個例子（ ）可以是：
整個過程可以用下圖來表示：
另外通過以下過程構建第 層的 和 ：
這里 的計算過程是指：由於 中的節點來自 中的節點的聚類，所以 之間的權重是 和 對應的聚類之前的 中節點之間所有權重的累加。 是對 的聚類，圖聚類的方法是多種多樣的，可以自行選取，這里的方法是採用 的 - covering，使用核函數 的 的 - covering是一個劃分 ，滿足：
以 代表平均節點數量，那麼第 層用來學習的參數量為：
實踐中通常有 ， 是下采樣因子，滿足 。
這種架構的優點在於不需要很強的前提假設，只需要圖具備鄰域結構即可，甚至不需要很好的embedding向量。但是缺點在於沒辦法進行參數共享，對於每一層的每一個節點都要有單獨的參數進行卷積而不能像CNN那樣使用同一個卷積核在數據網格上進行平移。
在這里，以 代表圖的度矩陣， 代表圖的加權鄰接矩陣，常用的圖的拉普拉斯矩陣有三種：
①Combinatorial Laplacian，也就是普通形式的拉普拉斯矩陣：
其中的元素為：
②Symmetric normalized Laplacian，也就是對稱歸一化的拉普拉斯矩陣：
其中的元素為：
③Random walk normalized Laplacian，也就是隨機遊走歸一化拉普拉斯矩陣：
其中的元素為：
為簡便起見，本文應用的是第①種。對於一個固定的加權鄰接矩陣 ，不同的節點信號列向量 （也就是說網路有 個節點）有不同的平滑性（smoothness）度量 ，在節點 處的平滑性度量為：
所有信號的平滑性度量為：
其實 也就是 ，關於拉普拉斯矩陣與信號平滑性的關系已經在本文開頭給出的文章鏈接里介紹過了，這里不再贅述。
有了上面的公式我們可以得出最平滑的信號 其實是一個歸一化的全 向量：
事實上 空間中最平滑的 個相互正交的單位向量其實就是 的特徵向量：
每個特徵向量 的平滑性度量的值其實也就是特徵值 ，這一點只需要代入計算一下就可以得出，拉普拉斯矩陣的譜分解為 ，這里的 為特徵值構成的對角矩陣， 為特徵向量構成的正交矩陣， 的每一列都是一個特徵向量，那麼 計算一下就可以得到等於特徵值 ，因此最平滑的信號向量就是特徵值最小的特徵向量，拉普拉斯矩陣的特徵值就代表了特徵向量的平滑度。
上面提到的一組特徵向量其實就是 空間的一組基，前面的文章里說過圖傅里葉變換其實就是將信號向量投影到拉普拉斯矩陣的各個特徵向量上：
特徵值的大小表示平滑程度，它對應傳統傅里葉變換中的頻率，頻率高表示短時間內變動多，和這里的相鄰節點變動大（變動越大越不平滑）能對應起來。因此圖傅里葉變換就是在將一個圖信號分解到不同平滑程度的圖信號上，就像傳統傅里葉變換將函數分解到不同頻率的函數上一樣。
一個任意信號向量 分解到所有的特徵向量上對應的每個系數用 （ ，這些系數也就是圖傅里葉變換後的系數）表示， 可以表示為 ，也就是 ，那麼 的平滑性度量的值可以用這些系數和特徵值表示：
兩個函數 和 進行卷積可以應用卷積定理，用公式表達卷積定理就是：
應用卷積定理可以在頻域上進行圖的卷積操作，具體的方法是將濾波器 和圖信號 都通過圖傅里葉變換轉換到頻域然後計算轉換後的結果的乘積（哈達瑪積，也就是向量對應元素相乘），然後將相乘的結果再通過圖傅里葉逆變換轉換回空域，整個過程如下：
這里將 組織成對角矩陣 ， 也就是神經網路要學習的參數。
在這里我們仍然使用 來代表網路的第 層， ， 仍然代表卷積核的數量。這種架構的卷積的過程主要依照卷積定理，首先來描述卷積的過程，之後再描述如何進行下采樣，因此現在假設第 層和第 層的節點數都是 ，那麼第 層的輸入 就是一個 的矩陣，輸出 就是一個 的矩陣。第 層的計算過程可以表示為：
這里的 仍然相當於第 個feature map的信號。 也就是第 個卷積核中對第 個feature map進行卷積的部分，每一個 都是一個對角矩陣，其實就是前面的 ，這里之所以有一個連加號是因為要將多個feature map的結果累加起來， 仍然表示非線性激活，另外這里的 的每一列的特徵向量是按照特徵值的大小依次排列的（降序）。
通常只有拉普拉斯矩陣的前 個特徵向量是有意義的，因為後面的特徵向量對應的特徵值比較小，特徵向量非常的平滑，因此在實際中可以取拉普拉斯矩陣的前 列構成的矩陣 代替 ，這個過程就相當於頻域架構的下采樣的過程，這里的 就相當於空域架構中的 ，每一層可以取不同的值。按照目前這種架構所需的參數復雜度為 。
本文中提出的兩種架構在兩個數據集上進行了實驗驗證效果。具體實驗設置參看原論文，這里不做贅述。
這個數據集是從MNIST數據集的每張圖片（ ）上采樣 個樣本點構建圖。實驗樣本如下圖：
實驗結果如下圖所示：
這個數據集將MNIST數據集中的樣本提升到3維空間中。實驗樣本如下圖：
實驗結果如下圖所示：
ref: 圖傅里葉變換
ref: paper reading：[第一代GCN] Spectral Networks and Deep Locally Connected Networks on Graphs