Semi-Supervised Classification with Graph Convolutional Networks（基于圖卷積神經網絡的半監督分類）
這篇文章是阿姆斯特丹大學的教授Max Welling和博士Thomas N.Kipf于2017年在深度學習頂會ICLR上發表的，至寫此篇部落格時，在谷歌學術上顯示論文被引用數已經到達2136次。
論文：Semi-Supervised Classification with Graph Convolutional Networks
摘要部分：
作者提出了一種基于圖（圖論意義上的圖）的可擴充的半監督學習方法。通過譜圖卷積的局部一階近似來确定卷積網絡結構選擇，并在引文網絡，知識譜圖等許多資料集中展現了較明顯的優勢。
tips：
（1）半監督分類
半監督學習(Semi-Supervised Learning）是監督學習與無監督學習相結合的一種學習方法。半監督學習使用大量的未标記資料，以及同時使用标記資料，來進行相關工作。在無類标簽的樣例的幫助下訓練有類标簽的樣本。
（2）為什麼要引入圖結構模型
本來印象中的深度學習都是廣泛地用CNN，RNN這類模型，但是CV，NLP處理的問題都是可以由矩陣結構表示的資料，但是對于非矩陣結構的Graph（如現實生活中常見的社交網絡，引文網絡等），CNN則束手無策了，其平移不變性不再适用，為了在Graph結構上提取特征進行學習并引入可優化卷積參數，作者在本文提出了GCN模型。
本篇部落格的結構：
一. INTRODUCTION
二.Graph上的快速近似卷積思路
三. 半監督方式的節點聚類
四.模型局限及作者展望
五.總結
(以下Graph均指圖論意義上的圖)
一. INTRODUCTION
對于Graph中的節點半監督學習分類問題，前人在處理該問題時借助基于圖的正則化形式将标簽資訊與圖結構資料平滑的結合，在代價函數中加入Graph-based的拉普拉斯正則項
f(*)是神經網絡的可微分梯度函數，λ是某權值系數，A是鄰接矩陣，▲=D-A是未正則化的圖上拉普拉斯算子（拉普拉斯矩陣），D是其度矩陣，A是其鄰接矩陣。但是上述存在一個限制性的假設：相連節點存在相似的特征标簽。 這些假設可能會影響到模型的性能。
拉普拉斯算子簡述：
機器學習–拉普拉斯算子（Laplace Operator）學習整理
二. Graph上的快速近似卷積思路
作者提出頻譜圖上的一階近似卷積。
其中：
（1）A~（帶自環的鄰接矩陣）=A+IN（A為鄰接階矩陣，IN為自環）；
（2）σ(*)為激活函數；
（3）H(l)為第l層的激活矩陣；H(0)=X；
（4）W(l)為可訓練權重
作者的方法是在頻譜圖卷積下進行改進的：
在譜域下進行傅裡葉變換及卷積。
通俗了解，圖譜是将信号 / 音頻 / 圖像 / 圖分解成簡單元素 (微波、圖) 的組合。
輸入x與經過傅裡葉域參數化的filter：gθ=diag（θ）進行相乘：
U是歸一化Graph拉普拉斯算子L的特征向量的矩陣，Λ是它的特征值對角矩陣，UTx是x的圖形傅裡葉變換。
但是這種方式運算量很大O（n^2)，然後又有大牛提出用切比雪夫多項式的k階截斷展開式來逼近：
其中：Λ~=2Λ/λmax−IN，λmax是L的最大特征值，θ’是切比雪夫系數的向量。
經過切比雪夫多項式的遞歸定義代入式子後，式子變為：
這個表達式變成了K的範圍内。gθ約等于拉普拉斯算子中的一個K階多項式，運算便隻和卷積位置的節點的K steps範圍内的點有關了，計算複雜度大大降低，變成了O(|ε|)。
上述部分都是前人的研究結果。
作者基于上述部分提出層級線性模型，分層卷積操作限制為K=1，然後主要的改進為設定λmax≈2，這樣對于中心節點進行一次卷積時，僅利用中心節點最近的節點，對上一層的卷積可擴充至下一層。
然後模型就變成：
然後，由于限制參數數量可以進一步解決過拟合問題并将各層的運算量最小化，作者進一步将θ’0和-θ’1都等價于θ，式子化簡為：
計算的特征值都處于[0,2]之間，但是，當在深度神經網絡模型中使用該運算時，不斷地進行網絡層疊加操作，反複使用該運算方法可能會導緻數值不穩定性以及爆炸或消失梯度問題。這樣，作者又适用了一個技巧性的歸一化操作：
将該定義使用到具有C個輸入通道（每個節點的C維特征向量）的X和F個filter，得到特征映射式子：
Z是卷積操作後得到的輸出矩陣，卷積操作時間複雜度為
三. 半監督方式的節點聚類
整體的模型是用于半監督學習的多層GCN網絡。
（1）預處理及模型
作者首先計算了：
這使得模型式子更加簡潔：
（2）交叉熵損失
其中YL是有标簽的節點的集合。
（3）訓練：
Tensorflow GPU環境：
作者使用每次訓練疊代的完整資料集執行批量梯度下降，這是可行的選擇，隻要資料集适合記憶體即可。使用了A的稀疏矩陣表示，記憶體需求為O（| E |），即邊數，為線性需求。同時，作者還借鑒了resnet中的經典dropout方法（随機舍棄網絡中的神經元）引入到自己的模型中。
（4）資料集：
三個引文網絡，一個知識譜圖。
（5）模型參數：
兩層的GCN網絡，dropout率，L2正則化因子等
對不同的資料集參數有些差别：
（6）實驗結果：
總體上，本文的模型均優于前人（僅兩層GCN！)，同時注意到NELL資料集的accuracy遠低于其他。
每個epoch的訓練時間：
可以看出時間性能優良，但是當10M時CPU訓練已經記憶體超限。
四.模型局限及作者展望
模型還存在的局限：
（1）存儲空間的需求
如上述epoch的10M時的邊資料CPU已經無法訓練，作者的實作是基于全批次梯度下降，記憶體需求随着資料集大小線性增長。若要使用小批量的随機梯度下降的話，需要考慮GCN的層數，及節點的K鄰域必須存儲進去。
（2）不能處理有向圖特征
本文GCN模型隻适用于無向圖。同時作者提出對于NELL資料集的一個有趣的現象，對于知識譜圖，可以将有向圖轉化為無向二分圖進行操作。
（3）前提假設同樣存在局限
作者假設子環和邊連的鄰接結點的重要性同等，同時，作者認為對于某些資料集中引入一個權衡參數可能較有利。
五.總結
作者在本篇論文中介紹了一種基于graph結構的頻譜卷積，采用一階近似卷積（WL-1算法的一階近似改進）的方式提出GCN模型，同時從結果可以看出僅兩層的GCN就已經比深度訓練的模型在Graph上有着更優的accuracy了。
最後，推薦幾篇好部落格：
首先，肯定是作者自己的部落格啦，作者在自己的部落格中也清楚的介紹了模型的思路，同時，通過空手道俱樂部的例子，能更直覺的感受到GCN的強大。
https://tkipf.github.io/graph-convolutional-networks/
然後是學習的時候看到的幾篇寫得很好的部落格：
（1）https://blog.csdn.net/yuzhijiedingzhe/article/details/78895464
（2）https://blog.csdn.net/u013263329/article/details/77587078
（3）https://blog.csdn.net/qq_41727666/article/details/84640549
部落格有什麼錯誤歡迎各位大佬指正！