??由于課題研究需要，這星期看了幾篇GCN相關的文章和書籍，并對其進行了代碼復現，現將最近學習的內容做一個梳理與總結，用于日后復習鞏固，由于能力有限，文章中有錯誤或者不當之處，還望各位讀者多多指出，之后對GCN應用方面相關的論文閱讀筆記，也會及時文末跟新，（最近更新:2020年11月1日）

引言

?? 相信大多數讀者在了解GCN（Graph Convolutional Networks）之前，對CNN（Convolutional Neural Network）都是非常熟悉的，我們知道，在連續信號中的卷積是表征函式f與g經過翻轉和平移的重疊部分函式值乘積對重疊長度的積分,如下公式（1），
∫ ? ∞ + ∞ f ( τ ) g ( x ? τ ) d τ ( 1 ) \quad\qquad\int_{-\infty}^{+\infty} f(\tau)g(x-\tau)d\tau \qquad\qquad\qquad (1) ∫?∞+∞?f(τ)g(x?τ)dτ(1)

對于離散信號而言，離散卷積的本質也是平移疊加之后的加權和，所以在CNN中影像上的卷積，本質上是利用引數共享的過濾器（kernel），通過計算中心像素點以及相鄰像素點的加權和來構建成Feature Map,實作空間特征的提取，而加權的系數就是卷積核的權重，這其實在很多傳統影像的演算法中也有體現，就比如高斯平滑算子，拉普拉斯算子，邊緣檢測算子（提取邊緣特征），包括SIFI（Scale-invariant feature transform）特征點提取，也是一系列的卷積和后處理操作，這些在影像上通過卷積核特征提取的操作，之所以有效很大一部分原因是因為影像本身是結構化資料，它是多個像素點排列整齊的矩陣，而CNN具有平移不變性（即影像如果經過平移，得到的特征圖也會相應平移），然而在真實世界中，還含有很多非歐幾里得距離的資料，比如社交網路關系、交通連通圖、腦網路連接等等，對于這類具有抽象意義的拓撲圖關系的資料，它們是無法保證平移不變性的，這就需要我們有類似cnn的方法，來提取和挖掘有效的空間關系進行建模學習，廣義來說，對于任何資料，都可以建立一定的拓撲關聯，來進一步挖掘資料內部之間的關聯性，所以GCN有很大的應用空間，

GCN發展

??GCN真正開始運用和發展是從這篇于2016年提出，2017年發表的文章開始：SEMI-SUPERVISED CLASSIFICATION WITHGRAPH CONVOLUTIONAL NETWORKS ，詳細文章內容，讀者可以自行閱讀原文，

1、基于損失函式的考慮

??在2016年以前，就有前人嘗試利用正則化約束的方法，通過在損失函式中引入圖的拉普拉斯正則項，來對節點分類任務進行半監督學習，如下公式（2）.
L = L 0 + λ L r e g w i t h L r e g = ∑ i , j A i j ∣ ∣ f ( X i ) ? f ( X j ) ∣ ∣ 2 = f ( X ) T △ f ( X ) . ( 2 ) \mathcal{L}=\mathcal{L}_0+\lambda\mathcal{L_{reg}}\qquad with\quad \mathcal{L_{reg}}=\sum_{i,j}A_{ij}||f(X_i)-f(X_j)||^{2}=f(X)^T\vartriangle f(X). \qquad(2) L=L0?+λLreg?withLreg?=i,j∑?Aij?∣∣f(Xi?)?f(Xj?)∣∣2=f(X)T△f(X).(2)
其中 L 0 \mathcal{L}_0 L0?為監督損失（與label定義的損失）， L r e g \mathcal{L}_{reg} Lreg?為約束項， f ( . ) f(.) f(.)可以是神經網路可微函式， X X X是節點特征向量 X i X_i Xi?的矩陣， △ = D ? A \vartriangle=D-A △=D?A是無向圖 G = ( V , E ) G=(V,E) G=(V,E)的非標準化拉普拉斯矩陣，這里說明下，拉普拉斯矩陣是用來研究圖結構性質的核心物件，其定義為 L = D ? A L=D-A L=D?A，其中D是一個對角矩陣, A A A是鄰接矩陣， D i i = ∑ j A i j D_{ii}=\sum_jA_{ij} Dii?=∑j?Aij? 表示 i i i節點的度，拉普拉斯矩陣還有一種正則化的形式(symmetric normalized laplacian) L s y m = D ? 1 2 L D ? 1 2 = I N ? D ? 1 2 A D ? 1 2 ( 3 ) \qquad L_{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I_N-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \qquad\qquad\qquad(3) Lsym?=D?21?LD?21?=IN??D?21?AD?21?(3),其元素級別的定義如下：
L s y m [ j , j ] { 1 i f i = j ? 1 d e g ( v i ) d e g ( v j ) i f e i j ∈ E 0 o t h e r w i s e ( 4 ) \qquad L_{sym}[j,j]\left\{ \begin{aligned} 1\qquad\quad& &{ if\ i=j\quad}\\ \frac{-1}{\sqrt{deg(v_i)deg(v_j)}} & &{if\ e_{ij} \in E} \\ 0 \qquad\quad& & {otherwise } \end{aligned} \right.{\quad \qquad \qquad \qquad (4)} Lsym?[j,j]??????????1deg(vi?)deg(vj?) ??1?0??if i=jif eij?∈Eotherwise?(4)
拉普拉斯矩陣的定義源自于拉普拉斯算子，拉普拉斯算子它是 n n n維歐式空間種的二階微分算子，在二維空間的影像中表示就是我們熟悉的邊緣檢測算子（兩者之間的關系這里不多展開，感興趣的讀者可以看看這篇文章 拉普拉斯算子與拉普拉斯矩陣的關系

回到公式（2），從運算式上我們可以清晰的看到，正則部分相當于衡量相鄰節點之間的差異性，因為 A i , j A_{i,j} Ai,j?是鄰接矩陣上的元素，兩個節點處于鄰接關系時為1，其他為0.這樣的正則項，使得拓撲圖上相鄰節點盡可能相似，物以類聚，這是很自然的想法，從信號的角度上來看，減少該正則項，就是期望經過模型之后的圖信號更加平滑，從頻域上來看，是對圖信號做了低通濾波的處理，但是這樣的假設可能會限制模型的表達能力，因為圖上邊不只包含相似度的資訊，還可能包含其他相關資訊，

2、從譜圖卷積開始

??最初標準的第一代GCN出自Spectral Networks and Locally Connected Networks on Graphs，其對于圖上的卷積有如下定義：
g θ ? x = U g θ U T x ( 5 ) \qquad \qquad g_{\theta}*x=Ug_{\theta}U^Tx \qquad\qquad\qquad\quad(5) gθ??x=Ugθ?UTx(5)
這里 U U U是圖的標準化拉普拉斯（Laplacian）矩陣 L s y m L_{sym} Lsym?(公式3)的特征向量矩陣,因此有 L s y m = U Λ U T L_{sym}=U\Lambda U^T Lsym?=UΛUT, x x x是資料中提取出來的特征，也就是輸入，定義 g θ = d i a g ( h ^ ( λ l ) ) g_{\theta}=diag(\hat{h}(\lambda_l)) gθ?=diag(h^(λl?))是特征值的回應函式，進一步為了類比CNN中的共享卷積核的設計，在神經網路中將其設定為可訓練引數的卷積核，如 d i a g ( θ l ) diag(\theta_l) diag(θl?)，而 U T x U^Tx UTx的本質是將 x x x映射到傅里葉空間, U U U是傅里葉空間的一組正交基，對于如何將傅里葉分解推廣到圖卷積，可以參考這篇The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains ，太過復雜的推導和證明這里不過多解釋，
對于第一代版本的GCN主要有以下幾點弊端：

1. 每一層的計算涉及 U d i a g ( h ^ ( θ l ) ) U T Udiag(\hat{h}(\theta_l))U^T Udiag(h^(θl?))UT三個矩陣乘法，復雜度為 O ( N 2 ) O(N^2) O(N2)，代價較高
2. 卷積核具有n個引數，n是L的特征值個數，
3. 計算Hermitian Matrix特征值的代價非常昂貴

過高的計算復雜度和過大的計算引數，在實際運用中都是不允許的,于是基于以上兩點的考慮，就產生了第二代版本的GCN，詳細內容和公式推導可參考論文：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
，文中作者將卷積核巧妙地設計成了如下公式：
g θ ( Λ ) = ∑ k = 0 K ? 1 θ k Λ k = ( ∑ j = 0 k ? 1 θ j λ 1 j ? ∑ j = 0 k ? 1 θ j λ n j ) ( 6 ) g_{\theta}(\Lambda)=\sum_{k=0}^{K-1}\theta_k\Lambda^k= \begin{pmatrix} \sum_{j=0}^{k-1}\theta_j\lambda_1^j &&\\ &\ddots&\\ &&\sum_{j=0}^{k-1}\theta_j\lambda_n^j \end{pmatrix}\qquad\qquad(6) gθ?(Λ)=k=0∑K?1?θk?Λk=????∑j=0k?1?θj?λ1j????∑j=0k?1?θj?λnj??????(6)
經過這樣的設計，原本需要訓練n個引數，縮小到了K個，同時將公式（6）帶入公式（5）得到公式（7），從公式（7）中不難發現，此時我們不在需要在求矩陣的特征向量了，可直接使用拉普拉斯矩陣進行運算，第二代版本的GCN解決了第一代的2、3兩個問題的弊端，但是矩陣乘法的復雜度依舊是 O ( N 2 ) O(N^2) O(N2)，
g θ ? x = ∑ j = 0 k ? 1 θ j L j x ( 7 ) \qquad\qquad g_{\theta}*x=\sum_{j=0}^{k-1}\theta_jL^jx \qquad \qquad \qquad\quad(7) gθ??x=j=0∑k?1?θj?Ljx(7)

3、切比雪夫卷積核

??計算多個大型稠密矩陣的乘法復雜度是很高的，這運用中在實際場景是不被允許的，尤其是計算像社交關系網路這種超大拓撲圖的資料，顯然是無法實作的，為解決這個問題，我們采用切比雪夫多項式（Chebyshev polynomials）來近似 g θ ( Λ ) g_{\theta}(\Lambda) gθ?(Λ)，具體內容的討論讀者可閱讀知乎：chevyshev多項式作為卷積核 或Hammond等人對這一問題深入的討論Wavelets on graphs via spectral graph theory，我們直接給出近似公式：
g θ ’ ( Λ ) ≈ ∑ k = 0 K θ k ′ T k ( Λ ~ ) ( 8 ) \qquad \qquad g_{\theta^’}(\Lambda)\approx\sum_{k=0}^{K}\theta_k^{'}T_k(\tilde{\Lambda})\qquad\qquad\qquad(8) gθ’?(Λ)≈k=0∑K?θk′?Tk?(Λ~)(8)
這里 Λ ~ = 2 λ m a x Λ ? I N \tilde{\Lambda}=\frac{2}{\lambda_{max}}\Lambda-I_N Λ~=λmax?2?Λ?IN?是對 Λ \Lambda Λ的一種縮放， λ m a x \lambda_{max} λmax?是 L L L的最大特征值， θ ′ ∈ R k \theta^{'}\in\mathbb{R}^k θ′∈Rk是切比雪夫系數向量，切比雪夫的遞回式定義為 T k ( x ) = 2 x T k ? 1 ( x ) ? T k ? 2 ( x ) T_k(x)=2xT_{k-1}(x)-T_{k-2}(x) Tk?(x)=2xTk?1?(x)?Tk?2?(x)，設 T 0 ( x ) = 1 T_0(x)=1 T0?(x)=1, T 1 ( x ) = x T_1(x)=x T1?(x)=x,由此就可以的得到一個計算近似特征值的方法，將公式(8)帶入之前的卷積定義公式(5)，我們有： g θ ? x = ∑ k = 0 K θ k ′ T k ( L ~ ) x ( 9 ) \qquad\qquad g_{\theta}*x=\sum_{k=0}^{K}\theta_k^{'}T_k(\tilde{L})x \qquad\qquad\qquad(9) gθ??x=k=0∑K?θk′?Tk?(L~)x(9)這里 L ~ = 2 λ m a x L ? I N \tilde{L}=\frac{2}{\lambda_{max}}L-I_N L~=λmax?2?L?IN?,這個運算式是區域化的，它是拉普拉斯式的一個K階多項式，也就是說，它只依賴于距離中心節點(K階鄰域)，公式（9）的復雜度是 O ( ∣ ε ∣ ) O(|\varepsilon|) O(∣ε∣),即計算復雜度取決于圖的邊的數量，

4、GCN圖卷積網路

??為了簡化問題，同時減輕由于區域節點度過大而導致過擬合的問題，我們設定K=1,即只考慮中心節點的一階鄰近,將 T 0 ( x ) = 1 T_0(x)=1 T0?(x)=1, T 1 ( L ~ ) = L ~ T_1(\tilde{L})=\tilde{L} T1?(L~)=L~帶入公式(9)，進一步，我們將尺度變換的 λ m a x \lambda_{max} λmax?固定為2，于是我們就得到卷積新的近似表達:

g θ ? x ≈ θ 0 ′ x + θ 1 ′ ( L ? I N ) x = θ ( I N + D ? 1 2 A D ? 1 2 ) x . ( 10 ) g_{\theta}*x\approx\theta_0^{'}x+\theta_1^{'}(L-I_N)x=\theta(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x.\qquad\qquad(10) gθ??x≈θ0′?x+θ1′?(L?IN?)x=θ(IN?+D?21?AD?21?)x.(10)
由蓋爾圓盤定理我們知道，公式（10）中 I N + D ? 1 / 2 A D ? 1 / 2 I_N+D^{-1/2}AD^{-1/2} IN?+D?1/2AD?1/2的特征值范圍為[0,2]，重復的進行卷積操作，可能會導致數值不穩定，在神經網路中多層的圖卷積之后，容易導致梯度消失或者梯度爆炸，為了解決這個問題，我們將其進一步標準化:
I N + D ? 1 2 A D ? 1 2 → D ~ ? 1 2 A ~ D ~ ? 1 2 ( 11 ) \qquad \qquad \quad I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\to \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}\qquad\qquad\qquad\qquad(11) IN?+D?21?AD?21?→D~?21?A~D~?21?(11)
其中 A ~ = A + I N \tilde{A}=A+I_N A~=A+IN?, D ~ = ∑ j A ~ i j \tilde{D}=\sum_j\tilde{A}_{ij} D~=∑j?A~ij?，此時我們就將其特征值規范到了[0,1]之間，可以看到， A ~ \tilde{A} A~相當于每個節點增加了自連接關系，直觀上來看，就是每個節點的跟新與鄰近節點的表征以及節點上一層的表征有關，
將公式（11）帶入公式（10）我們的圖卷積運算式最終可寫成如下形式：
Z = D ~ ? 1 2 A ~ D ~ ? 1 2 X Θ ( 12 ) \qquad\qquad\quad\qquad Z=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta \qquad \qquad\qquad\qquad\qquad\quad(12) Z=D~?21?A~D~?21?XΘ(12)
這里 X ∈ R N × C X\in\mathbb{R}^{N\times C} X∈RN×C,N表示節點數，C表示節點的特征向量維度如C-dimensional, Θ ∈ R C × F \Theta\in\mathbb{R}^{C\times F} Θ∈RC×F表示可訓練的引數矩陣,F表示輸出維度， Z ∈ R N × F Z\in \mathbb{R}^{N\times F} Z∈RN×F就是卷積后的信號，這個公式的計算復雜度為 O ( ∣ ε ∣ F C ) O(|\varepsilon|FC) O(∣ε∣FC),由于 A ~ X \tilde{A}X A~X可以執行稀疏矩陣乘法運算，所以實際計算速度會很快，

代碼設計與實作

在GCN中，將公式（12）寫成如下多層傳播的形式:
H ( l + 1 ) = σ ( D ~ ? 1 2 A ~ D ~ ? 1 2 H ( l ) W ( l ) ) ( 13 ) \qquad\qquad \qquad H^{(l+1)}=\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})\qquad\qquad\qquad \quad(13) H(l+1)=σ(D~?21?A~D~?21?H(l)W(l))(13)
代碼實作方面非常簡單，主要是前期對鄰接矩陣的處理，以及圖卷積層的構建，這里是一個pytorch實作的代碼：

import torch
import torch.nn as nn
import torch.nn.init as init
import torch.nn.functional as F
# 圖卷積層
class GraphConvolution(nn.Module):
    def __init__(self, input_dim, output_dim, use_bias=True):
        """圖卷積：L*X*\theta

        Args:
        ----------
            input_dim: int
                節點輸入特征的維度
            output_dim: int
                輸出特征維度
            use_bias : bool, optional
                是否使用偏置
        """
        super(GraphConvolution, self).__init__()
        self.input_dim = input_dim
        self.output_dim = output_dim
        self.use_bias = use_bias
        self.weight = nn.Parameter(torch.Tensor(input_dim, output_dim))#權重
        if self.use_bias:
            self.bias = nn.Parameter(torch.Tensor(output_dim))
        else:
            self.register_parameter('bias', None)
        self.reset_parameters()

    def reset_parameters(self):
        init.kaiming_uniform_(self.weight)
        if self.use_bias:
            init.zeros_(self.bias)

    def forward(self, adjacency, input_feature):
        """鄰接矩陣是稀疏矩陣，因此在計算時使用稀疏矩陣乘法"""
        support = torch.mm(input_feature, self.weight)
        output = torch.sparse.mm(adjacency, support)
        if self.use_bias: 
            output += self.bias
        return output

    def __repr__(self):
        return self.__class__.__name__ + ' (' \
            + str(self.input_dim) + ' -> ' \
            + str(self.output_dim) + ')'
# 將鄰接矩陣標準化
def normalization(adjacency):
    """計算 L=D^-0.5 * (A+I) * D^-0.5,

    Args:
        adjacency: sp.csr_matrix.

    Returns:
        歸一化后的鄰接矩陣，型別為 torch.sparse.FloatTensor
    """
    adjacency += sp.eye(adjacency.shape[0])    # 增加自連接
    degree = np.array(adjacency.sum(1))
    d_hat = sp.diags(np.power(degree, -0.5).flatten())
    L = d_hat.dot(adjacency).dot(d_hat).tocoo()
    # 轉換為 torch.sparse.FloatTensor
    indices = torch.from_numpy(np.asarray([L.row, L.col])).long()
    values = torch.from_numpy(L.data.astype(np.float32))
    tensor_adjacency = torch.sparse.FloatTensor(indices, values, L.shape)
    return tensor_adjacency

更多相關代碼，可以從GitHub上下載：
《深入淺出圖神經網路：GNN原理決議》配套代碼

圖神經網路相關演算法詳述及實作

關于GCN的論文集合：GCN相關論文匯總

總結

??從第一個版本到最終圖卷積網路，每一次都在前一次的基礎上大大減少了計算復雜度，最終才使得GCN的端到端訓練成為可能，然而科學是不斷進步和發展的，GCN還存在很多問題，

1、譜域卷積

在譜域圖卷積中，我們對圖的拉普拉斯矩陣進行譜分解，并通過在傅里葉空間特征分解幫助我們理解潛在的子圖結構，GCN和ChebNet就是典型的應用，但是對于有向圖的鄰接矩陣是非對稱矩陣，此時不能對拉普拉斯矩陣進行譜分解，需要我們重新定義鄰接關系，或者通過其他形式的GCN來挖掘拓撲圖上的關系，

2、空域卷積

空域卷積作用在節點的鄰域上，我們通過聚合距離中心節點k-hop鄰居來得到節點的特征表示，空域卷積相比譜域卷積更加簡單和高效，GraphSAGE(Graph SAmple and aggreGatE)和GAT(Graph Attention Network) 是空域卷積的典型代表（GCN變體），

未來圍繞GCN的作業可以從以下幾點圍繞展開：
1、過度平滑問題
2、下游任務的處理應用
3、可解釋性
4、處理有向圖
5、inductive任務
…

參考文獻

[1] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” 5th Int. Conf. Learn. Represent. ICLR 2017 - Conf. Tra

[2] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” Adv. Neural Inf. Process. Syst., no. 59, pp. 3844–3852, 2016.

[3] Y. Jin, N. Duffield, P. Haffner, S. Sen, and Z. L. Zhang, “Learning Convolutional Neural Networks for Graphs Mathias,” 2010 22nd Int. Teletraffic Congr. - Proceedings, ITC 22, vol. 1, 2010.

[4] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and deep locally connected networks on graphs,” 2nd Int. Conf. Learn. Represent. ICLR 2014 - Conf. Track Proc., pp. 1–14, 2014.

[5] 《深入淺出圖神經網路：GNN原理決議》劉忠雨，李彥霖，周洋

[6] 知乎：如何理解 Graph Convolutional Network（GCN）