萬字長文帶你入門 GCN

來源 | 阿澤的學習筆記（ID: aze_learning）

Convolutional Neural Network

CNN 在圖像識别等任務中具有重要作用，主要是因為 CNN 利用了圖檔在其域中的平移不變性。由于圖結構不存在平移不變性，是以 CNN 無法直接在圖上進行卷積。

1.1 Translational Invariance

剛剛提到 CNN 之是以可以應用到圖像而無法應用到圖網絡中主要是因為圖像具有「平移不變形（translational invariance）」，而圖網絡不具備這一屬性。那麼問題來了，什麼是平移不變形呢？

我們知道對于 CNN 來說，其核心在于使用了基于卷積核的卷積操作來提取圖像的特征，這裡的卷積操作類似于對「計算區域内的中心節點和相鄰節點進行權重求和」：

CNN 之是以能成為圖像領域的明珠卻很少應用于其他領域原因是：「圖檔是一個規整的二維矩陣」，無論卷積核平移到圖檔中的哪個位置都可以保證其運算結果的一緻性，這就是我們所說的「平移不變性」。CNN 的卷積本質就是利用這種平移不變性來對掃描的區域進行卷積操作，進而實作了圖像特征的提取。

而網絡是不規整的關系型資料，是以其不存在平移不變形（每個節點的周圍鄰居數不固定），這就使得傳統的 CNN 方法無法直接應用于網絡中。

1.2 Convolution Kernels

既然是因為卷積核的原因，那麼可不可以不使用卷積核？

答案肯定是不可以，因為卷積神經網絡的一大核心就是利用卷積核實作「參數共享（Parameter Sharing）」。下圖為有卷積核的卷積操作：

此時的參數大小隻與卷積核大小有關，而如果不進行參數共享的話，參數的大小則與圖像的像素矩陣保持一緻：

除此之外，卷積神經網絡還有另一大核心：「局部連接配接性（Locally Connection）」。局部連接配接是指卷積計算每次隻在與卷積核大小對應的區域進行，也就是說輸入和輸出是局部連接配接的。如果不進行局部連接配接的話，相當于将圖檔的矩陣展開成向量進行輸入，類似于全連接配接神經網絡，此時的參數量會變得非常巨大：

也就是說，通過參數共享和局部連接配接性我們可以将參數從 降低到 。其中，W H 和 K 分别為圖像的寬、高和通道，N 為隐藏層節點個數，m 為卷積核寬，k 為卷積核個數。

PS：CNN 有三大特點，除了上面說的局部連接配接和參數共享之外，還有「階層化表達（Hierarchical Expression）」。CNN 的階層化表達可以通過卷積層疊加得到，每一個卷積層都是在前一層的基礎上進行的，這樣的意義在于，網絡越往後，其提取到的特征越進階。比如說：第一層可能是一些線條，第二層可能會是一些紋理，第三層可能是一些抽象圖案：

可能會有同學問：那我們還有其他辦法在圖上進行卷積嗎？答案是一定有的 = =。

目前的一大思路就是借助譜圖理論（Spectral Graph Theory）來實作在拓撲圖上的卷積操作，大緻步驟為将空域中的拓撲圖結構通過傅立葉變換映射到頻域中并進行卷積，然後利用逆變換傳回空域，進而完成了圖卷積操作。

看到這裡，估計大家會有一堆疑問，包括：什麼是譜圖理論？什麼是傅立葉變換？什麼是頻域空域？逆變換是什麼？

想要清楚的回答這個問題，要從圖信号處理說起。

Graph Signal Processing

圖信号處理（Graph Signal Processing，以下簡稱 GSP）用來處理那些定義在圖上的非規則域的信号，這句話有點拗口，拆開說就是處理圖上定義的信号，但信号所在域是規則的。

2.1 Simple Example

這裡我們舉一個圖信号處理的簡單例子：

假設我們在一個地方測量溫度，并根據人口密度安排了溫度感應點（如上圖 a 所示），地區 n 的測量溫度可以表示為 （如上圖 b 所示），并且 ， 為真實溫度， 為随機噪聲帶來的誤差。

現在我們想通過對測量地及周圍的溫度求平均來減少這些随機噪聲，當然為了防止失去局部溫度（這個也叫 Over Smooth），我們會對每個點取其周圍區域進行平均：

上圖 c 展示了 y(1) 的計算方式。我們也可以用矩陣來表示：

其中，矩陣 A 為鄰接矩陣（測量點的連接配接情況如上圖 d 所示），測量位置及每個位置的測量溫度如上圖 e 所示。

我們還可以對其進行優化，根據距離來為不同測量點添加不同的權重：

當然，我們也需要對權重進行歸一化，以便産生無偏估計：

其中，對角矩陣 D 用于歸一化，其值為 ，這個矩陣還有另外一個名字，叫「度矩陣（Degree Matrix）」。

以上便是一個簡單的是圖信号處理過程，其架構大緻為：

1. 測量點構成節點（圖 a），節點間的連通性和相關性構成邊；
2. 節點和邊構成圖（圖 b），該圖是信号域，表示測量信号的點以及它們之間的關系，并使用該圖進行分析和處理；
3. 測量溫度是圖的信号（圖 e），這裡的信号由真實溫度和測量噪聲所組成；
4. 考慮測量位置，我們提出了局部平均和權重平均，這是最簡單的圖信号處理方式（Linear fist-order）。

同樣的，我們也可以将其應用在多個領域，如民意調查、政治分析等。

2.2 Fourier Transformer

我相信如果我一上來就扔出傅立葉變換，很多人都會崩潰不想看，不信我們試試：

如果沒有崩潰的話就直接看下一節吧；如果崩潰了就接着看，但是筆掉了千萬别撿，否則可能就看不懂了。

2.2.1 Transformer

為了讓大家無痛入門，我們先從最簡單變換的說起。

我們知道笛卡爾坐标系中，每個點都會有一個坐标，如下圖所示 A(-3,1) B(2,3)：

那麼為什麼可以這麼表示呢？為什麼 A 的坐标為 (-3,1) 而 B 的坐标為 (2,3) ？

這是因為在笛卡爾坐标系中，我們定義了一組标準正交基 ，基是向量有方向有大小。（正交是指不同基之間的内積為 0，即兩個基線性無關，而标準基是指基的模為 1）

A 的坐标其實就表示在 x 軸坐标上有 3 個 的長度且方向與 相反，在 y 軸坐标上有 1 個 的長度，且方向相同。

這樣做的好處是什麼呢？主要是為了友善計算和表示，試想下，如果隻給你一點點而沒有坐标系，你怎麼表示兩個點之間的距離呢？而放在坐标系中，這些問題就迎刃而解。

有同學可能疑問，不是說變換嗎？怎麼扯到笛卡爾坐标系了？其實我們剛剛說的就是一種變換：「将圖上的節點變換到坐标系中」。

2.2.2 Fourier Series

傅立葉變換分為傅立葉級數和連續傅立葉變換，我們先說傅立葉級數。

傅立葉級數适用于周期性函數，它能夠将任何周期性函數分解成簡單震蕩函數的集合（正弦函數和餘弦函數），舉個例子，比如說下圖：

左邊是一個周期函數，右邊是将周期函數分解成多個簡單震蕩函數，是以這個周期函數用數學公式可以表達為：

我們看到上圖中的信号是随着時間變換的，是以我稱之為「時域（Time domain）」。

我們觀察到，不同的振蕩函數具有不同的振幅和頻率，以上圖為例 的振幅為 1/3 而頻率為 ，考慮以頻率為橫坐标，振幅為縱坐标，我們有：

這個就是我們所說的頻域（Frequency Domain），其和時域是等價的，不過是從另外一個角度去描述信号。我們把它放在一起看一下：

我們可以放一張動圖感受一下：

給出傅立葉級數的公式：

還可以将其稍作變換：

這樣我們便能看出來，此時的标準正交基為

，而對應的系數 其實就是傅立葉級數在這組标準正交基下的向量。這便是傅立葉變換，将信号從時域變換到頻域中。

這裡介紹下傅立葉變換後的基為正交基，因為有個知識點後面還會用到。

我們知道判斷兩個向量是否正交可以用向量點乘求和等于 0 來判斷，這種方法我們稱為點積（内積）：

與向量點積不同的是，函數是連續的，假設現在有兩個函數 f 和 g，f 的周期為 2n，我們也想用上述連續累加的方式來使得函數内積和向量内積的概念一緻，而積分正是函數累加的概念，是以我們有：

對于上面我們說的傅立葉變換後的正交基，我們容易得到：

容易證明上述标準基為正交基。

在數學裡，希爾伯特空間（Hilbert Space）是有限維歐幾裡得空間的一個推廣，是一個完備的内積空間，其定義了一個帶有内積的完備向量空間。在希爾伯空間中，一個抽象元素通常被稱為向量，它可以是一個複數或者函數。傅立葉分析的一個重要目的是将一個給定的函數表示成一族給定的基底函數的和，而希爾伯特空間為傅立葉分析提供了一種有效的表述方式。

可能大家看到這裡要爆炸了，不過不用擔心，我們隻需要記住上面「兩個函數的内積形式」即可。

2.2.3 Fourier Transformer

我們剛剛說的都是周期性函數，但現實中大部分函數都是非周期的，那如果涉及到非周期性函數該怎麼辦呢？

在介紹非周期性函數之前，我們先簡單介紹下歐拉公式。

考慮橫軸為 1，縱軸為虛機關 i 的坐标系，圖上任意一點都可以表示為 。

根據歐拉公式，我們可以寫成：

其中，e 為自然對數的底數。

是以坐标軸上的點現在有了兩種表示方式：

考慮 ， 會随着 t 的增大而逆時針旋轉。是以 可以表示為坐标點 A 随着時間 t 逆時針旋轉。我們以時間 t 為橫坐标，則可以記錄到坐标點 A 映射在虛軸的運動軌迹：

左邊圖是我們看到的旋轉頻率，稱為頻域，而右邊圖看到是時間流逝，稱為時域，是不是和我們剛剛介紹的（從時域變換到頻域）正好相反？也就是說，時域和頻域其實是可以互相轉換的。

回到正題，考慮非周期函數的傅立葉變換。

事實上，我們可以将非周期函數考慮為周期無窮大的函數，考慮頻域中的橫坐标：，當周期 T 無窮大大時，頻域圖就從離散點變為連續的曲線，如下圖：

那麼，我們該如何從這個非周期函數中分解出各種信号呢？答案就是利用正交！比如說，假設這函數中有一個 的信号，那麼我們用 就可以把它乘出來，而其他分量如

都會因為正交而消失。是以我們需要對函數做一個内積：

其中， 剛剛介紹過，就是一組正交基的組合。我們用正交基去與函數求内積，如果原函數中包含頻率為 的三角函數，則 便為 0，反之為 0，這樣自然分離能分離出相應的信号，其圖示如上圖 c 中右部分所示。

細心的同學可能還會注意到上式的計算的結果中還有複數 i。其實是樣子的：「實數部分表示振幅」，「虛數部分表示相位」。相關資料同學們可以自己查閱，不再進行過多介紹。

以上就是我們所說的傅立葉變換（Fourier Transform，FT）。同樣的我們也存在逆變換：

于是，我們便實作了将信号拆成多個正弦信号，再把正弦信号逆變換為原來信号的過程。

簡單介紹下傅立葉變換的應用吧， 省得看了那麼多不知道他能幹什麼。

一個很經典的例子就是：分離、降噪。如果男生和女生一起說話，該如何分離出兩者的聲音呢？答案就是對這一段聲音（時域）做傅立葉變換轉換到頻率，而男女生的聲音頻率不同，在頻域中，低頻為男生，中頻為女生，高頻可能為噪音，我們可以根據需要去除中頻和高頻的信号，并将其進行逆變換，這樣便分離出了男生的聲音。

PS：這裡再說一個好玩的，頻域中是不是不存在時間的概念？不存在時間卻可以表示時間，這有沒有一點像我們的人生，看似無規律，但是從上帝視角來看，一切皆命中注定。

2.3 Graph Laplacian

圖拉普拉斯矩陣可以定義為：

其中，D 為度矩陣，W 為考慮權值的鄰接矩陣。

考慮歸一化後的拉普拉斯矩陣：

以上為正常操作，不過介紹到這裡不知道大家會不會有一點疑問。

至少我是有疑問的：圖拉普拉斯矩陣為什麼要這樣定義的？

要想回答這個問題，首先我們得了解什麼是拉普拉斯算子。

2.3.1 Laplacian

在數學中，拉普拉斯算子（Laplacian）是由歐幾裡得空間中的一個函數的梯度的散度給出的微分算子，通常有以下幾種寫法：。是以對于任意函數 來說，其拉普拉斯算子的定義為：

這裡引入了一個新的概念——散度，這裡簡單介紹下：

散度（Divergence）是向量分析的一個向量算子，将向量空間上的向量場（矢量場）對應到一個标量場。散度描述的是向量場裡一個點是彙聚點還是發源點。值為正時表示該點為發源點，值為負時表示該點為彙聚點，值為零時表示該點無源。散度在實體上的含義可以了解為磁場、熱源等。

回到正文，我們看下拉普拉斯算子在 n 維空間中的笛卡爾坐标系的數學定義：

數學表示為各個次元的二階偏導數之和。

以一維空間為例：

也就是說二階導數近似于其二階差分，可以了解為目前點對其在所有自由度上微擾之後獲得的增益。這裡自由度為 2，分别是 +1 和 -1 方向。

再以二維空間為例子：

看到上面可能大家會很可能很陌生，但是這個就是圖像中的拉普拉斯卷積核：

此時共有 4 個自由度 (1,0),(-1,0),(0,1),(0,-1)，當然如果對角線後其自由度可以為 8。

對此我們可以進行歸納：「拉普拉斯算子是所有自由度上進行微小變化後所獲得的增益」。

我們将其推廣到網絡圖中，考慮有 N 個節點的網絡圖，其自由度最大為 N，那麼函數 可以是 N 維的向量，即：

其中， 表示函數 在網絡圖中節點 i 處的函數值，類比 為函數 在 (x,y) 的函數值。

在網絡圖中，兩個節點的之間的增益為 ，考慮權重圖則有 ，那麼對于節點 i 來說，總增益即為拉普拉斯算子在節點 i 的值：

其中， 為節點 i 的度；上式第二行去掉了 是因為 可以控制節點 i 的鄰接矩陣。

對于任意 都成立，是以我們有：

自此，我們便給出了圖拉普拉斯矩陣的推導過程，這個公式的全稱為：圖拉普拉斯算子作用在由圖節點資訊構成的向量 上得到的結果等于圖拉普拉斯矩陣和向量 的點積。拉普拉斯矩陣反映了目前節點對周圍節點産生擾動時所産生的累積增益，直覺上也可以了解為某一節點的權值變為其相鄰節點權值的期望影響，形象一點就是拉普拉斯矩陣可以刻畫局部的平滑度。

2.3.2 Laplace Spectral decomposition

拉普拉斯矩陣的譜分解就是矩陣的特征分解：

對于無向圖來說，拉普拉斯矩陣是實對稱矩陣，而實對稱矩陣一定可以用正交矩陣進行正交相似對角化：

其中， 為特征值構成「對角矩陣」， 為特征向量構成的「正交矩陣」。

又因為正交矩陣的逆等于正交矩陣的轉置： ，是以我們有：

因為 L 是半正定矩陣，我們還可以有：

其中， 為節點 i 的信号。我們稱 為圖信号的總變差（Total Variation），可以刻畫圖信号整體的平滑度。

拉普拉斯的譜分解具有以下幾點性質：

• 由于拉普拉斯矩陣以每行（列）元素之和為零，是以拉普拉斯矩陣的至少有一個特征值為 0，對應的特征向量
• 拉普拉斯矩陣的特征值都大于零，歸一化的拉普拉斯矩陣的特征值區間為 [0, 2]；
• 如果有 n 個特征值為 0，則表示圖有 n 個子圖互相無連接配接；
• 特征值的總和為矩陣的迹，對于歸一化的拉普拉斯矩陣，如果沒有孤立節點或子圖，其特征值為 N。

2.4 Graph Fourier Transformer

有同學看到這可能會感到疑問了：「我們剛介紹傅立葉變換，現在又介紹拉普拉斯譜分解的，到底想幹嘛」。

這是因為：「傅立葉分析是拉普拉斯譜分析的一個特例」！想不到吧，是不是很震驚？

我們來證明下，首先考慮亥姆霍茲方程（Helmholtz Equation）：

其中， 為拉普拉斯算子， 為特征函數， 為特征值。

看不懂不要緊，把它當成廣義特征方程就行：，狹隘的特征方程隻能用于處理向量和矩陣，而這個可以用于處理函數，最經典的應用是處理波動方程和擴散方程，是以我們可以用它處理信号。

回顧一下傅立葉變換：

其實就是信号函數 與基函數 的内積（剛剛介紹過函數内積）。

對于基函數 ，我們讓其與拉普拉斯算子求内積：

以上便證明 是「拉普拉斯算子的特征函數」，同時也證明了「離散傅立葉變換是拉普拉斯譜分析的一個特例」。

寫到這我們有以下線索：首先拉普拉斯矩陣（離散拉普拉斯算子）可以應用在圖像上，理論上也可以應用到網絡上，而傅立葉變換是拉普拉斯的一個小弟，是以小弟也可以應用到圖上。

回顧下拉普拉斯譜分析：

我們類比一下：

信号中的傅立葉變換	網絡圖中的傅立葉變換
頻率	特征值
正交基中某個向量	正交矩陣中的某個向量

是不是長得非常像，是以我們也有了網絡圖上的傅立葉變換：

其中， 為網絡圖上的 n 維向量， 表示網絡中的節點 i 的第 k 個分量， 表示特征向量 k 的第 i 個分量。做個類比解釋：特征值（頻率） 下， 的圖傅立葉變換（振幅）等于 與 對應的特征向量 的内積。

考慮矩陣乘法：

是以我們得到了「圖傅立葉變換的矩陣形式」，這裡的 為拉普拉斯譜分解的正交矩陣。

我們也可以得到傅立葉逆變換：

Graph Convolutional Network

前面的鋪墊很多，終于要迎來 GCN 了。

3.1 Convolution

我們先來看一下卷積的定義，卷積是指通過兩個函數 和 生成第三個函數的一種數學算子，表征函數 與經過翻轉和平移的 的乘積函數所圍成的曲邊梯形的面積：

對于離散卷積來說，我們可以定義為：

計算卷積有很多種方法，除了直接計算外，我們還可以考慮「卷積定理」：在适當條件下，兩個信号的卷積的傅立葉變換是他們的傅立葉變換的點積。換句話說，一個域（如時域）的卷積等于另一個域（如頻域）的點乘：

其中 表示 的傅立葉變換。

借助傅立葉逆變換 可以寫成：

這樣做有什麼好處呢？或者說，我們為什麼要變換一個域後再去做卷積操作？

因為利用卷積定理可以簡化卷積的運算量。對于一個長度為 n 的序列，按照卷積的定義來計算則需要做 2n-1 組對位乘法，即時間複雜度為 ；而利用傅立葉變換後，隻需要計算一組對位乘法，而且離散傅立葉變換有快速的算法（快速傅立葉變換），是以總的計算複雜度為 。

3.2 Graph Convolution

現在有了圖傅立葉變換，又有了離散卷積操作，那麼我們想：既然無法直接在空域進行卷積，可否将圖信号映射到頻域後再做卷積操作。

是以我們有：

其中，向量 與向量 的元素點積，等價于将 組織成對角矩陣的形式進行矩陣乘法，是以我們有：

最後我們再左乘 進行逆變換：

這裡，我們不寫成 的主要原因在于，我們可以将其與深度學習相結合，在 GCN 中我們的卷積核是可訓練并且參數共享的，是以在此我們可以直接将 寫成 ，這個便是深度學習中的可學習參數。

3.3 GCN-1

第一代的卷積神經網絡也就是剛剛我們給出的公式：

這和論文中給出的公式是一樣的：

這邊補充一點，在這篇論文中，作者還給出了一個基于空域的「深度局部連接配接網絡」（Deep Locally Connected Networks），我們可以簡單看一下：

每一層變換定義為：

其中， 表示第 k 第 i 個節點； 表示第 k 層節點 i 和節點 j 的權值，考慮局部鄰居； 表示卷積運算； 表示第 k 層的池化操作。也就是說每個節點都是由其鄰居和自身卷積池化得到。

雖然看起來很簡單，但是優點在于它不需要很強的前提假設，其隻需要網絡具有局部鄰域結構，甚至不需要很好的 Embedding 向量。

但這種結構下有一個很大的缺點：「沒有辦法實作共享參數」。

作者針對這種問題提出了我們所看到第一代圖卷積神經網絡。

3.4 GCN-2

第一代的圖卷積神經網絡很巧妙的利用圖譜理論來實作拓撲圖的卷積操作，但其有很多缺點，比如說：計算複雜度太高，我們需要對拉普拉斯矩陣進行譜分解得到特征向量矩陣 ，時間複雜度為 ；

針對這個問題，學者提出了第二代 GCN。

首先我們回顧下圖傅立葉變換：

可以看到這是一個和特征值密切相關的函數，我們不妨将 寫成拉普拉斯矩陣 L 的特征值函數 ：

然後這個卷積核有兩個局限性：

1. 不具備局部連接配接性；
2. 時間複雜度為 。

為了克服這個缺點，我們引入 K 階多項式：

其中，參數 是多項式系數，這樣濾波器就具有了 K 階局部性了，複雜度也降低到 。

我們将這個公式帶入卷積運算中：

此時，我們計算圖卷積運算就不需要再乘上特征向量矩陣 ，而是直接使用拉普拉斯矩陣 L 的 k 次方，這樣就避免了進行特征分解。而我們可以事先計算好 ，這樣就隻需要計算矩陣相乘。同時由于 L 為稀疏矩陣，是以時間複雜度為 ， 為節點邊數。

此外，作者還引入了切比雪夫展開式來近似 。

設 為切比雪夫多項式的第 k 階式子，切比雪夫多項式的遞歸式為：。是以我們有：

其中， ； 是指拉普拉斯矩陣 L 的最大值。

這是因為切比雪夫多項式的輸入要在 之間，由于拉普拉斯矩陣的半正定性，是以所有的特征值都是大于等于 0 的，将其除以最大特征值可以将特征壓縮到 區間内，現在需要将其壓縮到 ，是以我們有：

我們将切比雪夫多項式引入到我們的卷積變換中：

其中， 。這個表達式為拉普拉斯多項式中的一個 k 階近似函數，依賴于節點的 「k 階鄰域」（走 k 步能到的鄰居），時間複雜度與邊呈線形相關。

3.5 GCN-3

第二代 GCN 解決了圖卷機要求特征分解的問題，但是在計算圖卷積操作時，依然每次都要進行矩陣乘法，時間複雜度為 ，于是學者繼續優化。

我們把上式拿下來：

GCN 通過上式的多層卷積層進行疊加，而每層都會逐點進行非線性疊加，考慮到時間複雜度問題，學者直接取 K=2，也就是說得到了一個拉普拉斯算子的二階近似函數。這樣我們既可以對網絡進行卷積操作，又不會引入太多的切比雪夫系數。而且這樣的線形運算允許我們建構更深的網路，提高模型的模組化能力。

我們知道歸一化的拉普拉斯矩陣的特征值區間為 [0, 2]，進一步近似 ，是以我們有新的表達式：

其中，

在實際訓練過程中，我們需要規範化參數來避免過拟合，是以我們令 ，進而有：

需要注意的是， 的特征值範圍在 [0, 2] 之間，是以如果在很深的網絡中會引起梯度爆炸的問題，是以我們需要再次對他進行一次歸一化（原文也稱 「renormalization trick」）：

我們把這個公式從标量推廣到矩陣，對于輸入節點的向量 ，其中 N 為節點數，C 為節點的特征向量次元，我們有：

其中， 是濾波器的參數矩陣， 是卷積後的信号矩陣，時間複雜度為 。節點的向量可以通過卷積操作從 C 次元 轉變為 F 次元。

依據上面的單層運算，我們給出了多層圖卷積網絡的傳播規則：

其中， ，A 為鄰接矩陣， 為機關矩陣，是以 為添加自連接配接的鄰接矩陣； ， 可以了解為對角線為節點 i 的度數矩陣； 為神經網絡第 層的權重矩陣； 是激活函數； 是第 層的激活矩陣，并且 ， 是由節點 的特征向量組成矩陣。

到此，便完成了 GCN 卷積操作的公式推導。

3.6 Model

再來關注一下模型。

圖卷積神經網絡是指在圖結構中做卷積操作的神經網絡，是以其輸入輸出的都是圖結構，差別于傳統的神經網絡結構，其隐藏層是直接在圖結構中進行激活：

為了友善了解，我們舉個分類任務例子，以包含一個隐藏層的 GCN 為例：

由于知道了 GCN 的傳播規則，是以我們有最終的結果：

其中， 是輸入層到隐藏層的權重， 是隐藏層到輸出層的權重；用 Softmax 是因為這是一個節點分類任務，需要預測标簽。

然後，我們用交叉熵作為代價函數：

其中， 為有标簽的節點集合。

有了代價函數後，我們可以通過梯度下降來更新網絡的參數。

3.7 Experiment

簡單看下第三代 GCN 的試驗。

由于 GCN 比較複雜，是以這裡我将給出兩種實驗，一種是 GCN 的效果實驗，另一種是模拟 GCN 運作的實驗。

3.7.1 Effect

我們來看一下實驗部分，GCN 與其他模型的對比：

可以看到 GCN 的結果在不同資料集上都取得了非常好的效果，遠超其他模型。

我們再看一下，對于 GCN 而言不同程度的近似會有什麼樣的效果：

可以看到并不是模型越複雜效果越好。

GCN 還有除了訓練後模型精度高外，還有兩個非常硬核的地方，即使不訓練，直接随機參數也可以獲得不錯的效果，下圖展示了在某一資料集下随機賦權值的結果：

另外，作為半監督學習，GCN 可以在隻标注少量樣本的情況下學得出色的效果，下圖為每個類别隻标注一個樣本的分類結果：

3.7.2 Simulation

為了更加形象的了解 GCN，我們來對 GCN 進行模拟。

首先，以一個簡單有向圖模型為例：

鄰接矩陣 A 和 節點的特征向量 X 為：

我們有一個簡單的傳播規則（不考慮參數矩陣和激活函數）：

「可以看到節點的特征變成了其鄰居的特征之和！」

但這邊也就一些小問題：

1. 這種傳播過程沒有考慮節點自身的特征；
2. 度的大節點特征值會越來越大，度小的節點特征值會越來越小，傳播過程對特征的尺度敏感。

為了解決這個問題，我們需要：

1. 加一個機關矩陣，考慮自環路；
2. 将鄰接矩陣 A 與度矩陣 D 的逆相乘對特征進行歸一化。

我們先看下加上機關矩陣的效果：

可以看到，加上機關矩陣的計算考慮了節點的特征。

再看下鄰接矩陣歸一化的效果：

鄰接矩陣被歸一化到 0 到 1 之間。

我們将兩個放在一起，并考慮參數矩陣 W：

是以我們有：

以上便完成了 GCN 的簡單仿真。

我們回過頭來再來看一下網絡的傳播規則：

現在是不是更能明白為什麼這麼傳播了？

這裡解釋一下歸一化為什麼是兩邊乘上矩陣的 -1/2 次方。

這是因為對稱歸一化的拉普拉斯矩陣其元素定義為：

我們仿真模拟的是用權重求和取平均的方式來聚合，而作者采用的是拉普拉斯變換。我這邊做一個化簡大家可能個就會明白了：

差別于權重求和取平均的方式，拉普拉斯變換不但考慮目前節點的 i 的度，還考慮其他節點 j 的度。

Conclusion

GCN 的入門文章就介紹完了，大緻思路為：CNN 中的卷積無法直接應用于網絡圖中，是以引出了圖信号處理（Graph Signal Processing）中的 Graph Fourier Transformation，進而定義 Graph Convolution，最後結合深度學習發展出來 GCN。

Reference

1. 《Graph Convolutional Networks in 3 Minutes》
2. 《如何了解卷積神經網絡中的權值共享？》
3. 《HIERARCHICAL DEEP LEARNING ARCHITECTURE FOR 10K OBJECTS CLASSIFICATION》
4. 《Introduction to Graph Signal Processing》
5. 《Fourier series》
6. 《Fourier Series Graph Interactive》
7. 《Hilbert space》
8. 《Laplace operator》
9. 《如何了解 GCN？- Johnny Richards的回答》
10. 《圖拉普拉斯算子為何定義為D-W》
11. 《圖卷積神經網絡理論基礎》
12. 《如何了解 GCN？- superbrother的回答》
13. 《Fourier transform》
14. 《Convolution》
15. 《Convolution theorem》
16. 《Spectral Networks and Deep Locally Connected Networks on Graphs》
17. 《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》
18. 《Semi-supervised Classification with Graph Convolutional Networks》
19. 《How to do Deep Learning on Graphs with Graph Convolutional Networks》