斷斷續(xù)續(xù)寫了一個(gè)多星期，期間找了很多同學(xué)討論學(xué)習(xí)，感謝指導(dǎo)過點(diǎn)撥過我的同學(xué)們，為了精益求精本著不糊弄?jiǎng)e人也不糊弄自己的原則在本文中探討了很多細(xì)節(jié)。
當(dāng)然，還有很多細(xì)節(jié)沒提到，包括總變差（Total Variation）、空域和頻域視角下的圖信號(hào)等，有興趣的同學(xué)可以深入了解下圖信號(hào)處理，本人才疏學(xué)淺還希望拋磚引玉引出更多的 GCN 的文章。
非常感謝知乎 @superbrother 同學(xué)和蘑菇先生的精彩筆記才使得我能夠入門 GCN，當(dāng)然我也將公開我的筆記希望能幫助更多的同學(xué)。
CNN 在圖像識(shí)別等任務(wù)中具有重要作用，主要是因?yàn)?CNN 利用了圖片在其域中的平移不變性。由于圖結(jié)構(gòu)不存在平移不變性，所以 CNN 無法直接在圖上進(jìn)行卷積。
剛剛提到 CNN 之所以可以應(yīng)用到圖像而無法應(yīng)用到圖網(wǎng)絡(luò)中主要是因?yàn)閳D像具有「平移不變形（translational invariance）」，而圖網(wǎng)絡(luò)不具備這一屬性。那么問題來了，什么是平移不變形呢？
我們知道對(duì)于 CNN 來說，其核心在于使用了基于卷積核的卷積操作來提取圖像的特征，這里的卷積操作類似于對(duì)「計(jì)算區(qū)域內(nèi)的中心節(jié)點(diǎn)和相鄰節(jié)點(diǎn)進(jìn)行加權(quán)求和」：
CNN 之所以能成為圖像領(lǐng)域的明珠卻很少應(yīng)用于其他領(lǐng)域原因是：「圖片是一個(gè)規(guī)整的二維矩陣」，無論卷積核平移到圖片中的哪個(gè)位置都可以保證其運(yùn)算結(jié)果的一致性，這就是我們所說的「平移不變性」。CNN 的卷積本質(zhì)就是利用這種平移不變性來對(duì)掃描的區(qū)域進(jìn)行卷積操作，從而實(shí)現(xiàn)了圖像特征的提取。
而網(wǎng)絡(luò)是不規(guī)整的關(guān)系型數(shù)據(jù)，所以其不存在平移不變形（每個(gè)節(jié)點(diǎn)的周圍鄰居數(shù)不固定），這就使得傳統(tǒng)的 CNN 方法無法直接應(yīng)用于網(wǎng)絡(luò)中。
既然是因?yàn)榫矸e核的原因，那么可不可以不使用卷積核？
答案肯定是不可以，因?yàn)榫矸e神經(jīng)網(wǎng)絡(luò)的一大核心就是利用卷積核實(shí)現(xiàn)「參數(shù)共享（Parameter Sharing）」。下圖為有卷積核的卷積操作：
此時(shí)的參數(shù)大小只與卷積核大小有關(guān)，而如果不進(jìn)行參數(shù)共享的話，參數(shù)的大小則與圖像的像素矩陣保持一致：
除此之外，卷積神經(jīng)網(wǎng)絡(luò)還有另一大核心：「局部連接性（Locally Connection）」。局部連接是指卷積計(jì)算每次只在與卷積核大小對(duì)應(yīng)的區(qū)域進(jìn)行，也就是說輸入和輸出是局部連接的。如果不進(jìn)行局部連接的話，相當(dāng)于將圖片的矩陣展開成向量進(jìn)行輸入，類似于全連接神經(jīng)網(wǎng)絡(luò)，此時(shí)的參數(shù)量會(huì)變得非常巨大：
也就是說，通過參數(shù)共享和局部連接性我們可以將參數(shù)從 降低到 。其中，W H 和 K 分別為圖像的寬、高和通道，N 為隱藏層節(jié)點(diǎn)個(gè)數(shù)，m 為卷積核寬，k 為卷積核個(gè)數(shù)。
PS：CNN 有三大特點(diǎn)，除了上面說的局部連接和參數(shù)共享之外，還有「層次化表達(dá)（Hierarchical Expression）」。CNN 的層次化表達(dá)可以通過卷積層疊加得到，每一個(gè)卷積層都是在前一層的基礎(chǔ)上進(jìn)行的，這樣的意義在于，網(wǎng)絡(luò)越往后，其提取到的特征越高級(jí)。比如說：第一層可能是一些線條，第二層可能會(huì)是一些紋理，第三層可能是一些抽象圖案：
可能會(huì)有同學(xué)問：那我們還有其他辦法在圖上進(jìn)行卷積嗎？答案是一定有的 = =。
目前的一大思路就是借助譜圖理論（Spectral Graph Theory）來實(shí)現(xiàn)在拓?fù)鋱D上的卷積操作，大致步驟為將空域中的拓?fù)鋱D結(jié)構(gòu)通過傅立葉變換映射到頻域中并進(jìn)行卷積，然后利用逆變換返回空域，從而完成了圖卷積操作。
看到這里，估計(jì)大家會(huì)有一堆疑問，包括：什么是譜圖理論？什么是傅立葉變換？什么是頻域空域？逆變換是什么？
想要清楚的回答這個(gè)問題，要從圖信號(hào)處理說起。
圖信號(hào)處理（Graph Signal Processing，以下簡(jiǎn)稱 GSP）用來處理那些定義在圖上的非規(guī)則域的信號(hào)，這句話有點(diǎn)拗口，拆開說就是處理圖上定義的信號(hào)，但信號(hào)所在域是規(guī)則的。
這里我們舉一個(gè)圖信號(hào)處理的簡(jiǎn)單例子：
假設(shè)我們?cè)谝粋€(gè)地方測(cè)量溫度，并根據(jù)人口密度安排了溫度感應(yīng)點(diǎn)（如上圖 a 所示），地區(qū) n 的測(cè)量溫度可以表示為 （如上圖 b 所示），并且 ， 為真實(shí)溫度， 為隨機(jī)噪聲帶來的誤差。
現(xiàn)在我們想通過對(duì)測(cè)量地及周圍的溫度求平均來減少這些隨機(jī)噪聲，當(dāng)然為了防止失去局部溫度（這個(gè)也叫 Over Smooth），我們會(huì)對(duì)每個(gè)點(diǎn)取其周圍區(qū)域進(jìn)行平均：
上圖 c 展示了 y(1) 的計(jì)算方式。我們也可以用矩陣來表示：
其中，矩陣 A 為鄰接矩陣（測(cè)量點(diǎn)的連接情況如上圖 d 所示），測(cè)量位置及每個(gè)位置的測(cè)量溫度如上圖 e 所示。
我們還可以對(duì)其進(jìn)行優(yōu)化，根據(jù)距離來為不同測(cè)量點(diǎn)添加不同的權(quán)重：
當(dāng)然，我們也需要對(duì)權(quán)重進(jìn)行歸一化，以便產(chǎn)生無偏估計(jì)：
其中，對(duì)角矩陣 D 用于歸一化，其值為 ，這個(gè)矩陣還有另外一個(gè)名字，叫「度矩陣（Degree Matrix）」。
以上便是一個(gè)簡(jiǎn)單的是圖信號(hào)處理過程，其框架大致為：
同樣的，我們也可以將其應(yīng)用在多個(gè)領(lǐng)域，如民意調(diào)查、政治分析等。
我相信如果我一上來就扔出傅立葉變換，很多人都會(huì)崩潰不想看，不信我們?cè)囋嚕?/p>
如果沒有崩潰的話就直接看下一節(jié)吧；如果崩潰了就接著看，但是筆掉了千萬別撿，否則可能就看不懂了。
為了讓大家無痛入門，我們先從最簡(jiǎn)單變換的說起。
我們知道笛卡爾坐標(biāo)系中，每個(gè)點(diǎn)都會(huì)有一個(gè)坐標(biāo)，如下圖所示 A(-3,1) B(2,3)：
那么為什么可以這么表示呢？為什么 A 的坐標(biāo)為 (-3,1) 而 B 的坐標(biāo)為 (2,3) ？
這是因?yàn)樵诘芽栕鴺?biāo)系中，我們定義了一組標(biāo)準(zhǔn)正交基 ，基是向量有方向有大小。（正交是指不同基之間的內(nèi)積為 0，即兩個(gè)基線性無關(guān)，而標(biāo)準(zhǔn)基是指基的模為 1）
A 的坐標(biāo)其實(shí)就表示在 x 軸坐標(biāo)上有 3 個(gè) 的長(zhǎng)度且方向與 相反，在 y 軸坐標(biāo)上有 1 個(gè) 的長(zhǎng)度，且方向相同。
這樣做的好處是什么呢？主要是為了方便計(jì)算和表示，試想下，如果只給你一點(diǎn)點(diǎn)而沒有坐標(biāo)系，你怎么表示兩個(gè)點(diǎn)之間的距離呢？而放在坐標(biāo)系中，這些問題就迎刃而解。
有同學(xué)可能疑問，不是說變換嗎？怎么扯到笛卡爾坐標(biāo)系了？其實(shí)我們剛剛說的就是一種變換：「將圖上的節(jié)點(diǎn)變換到坐標(biāo)系中」。
傅立葉變換分為傅立葉級(jí)數(shù)和連續(xù)傅立葉變換，我們先說傅立葉級(jí)數(shù)。
傅立葉級(jí)數(shù)適用于周期性函數(shù)，它能夠?qū)⑷魏沃芷谛院瘮?shù)分解成簡(jiǎn)單震蕩函數(shù)的集合（正弦函數(shù)和余弦函數(shù)），舉個(gè)例子，比如說下圖：
左邊是一個(gè)周期函數(shù)，右邊是將周期函數(shù)分解成多個(gè)簡(jiǎn)單震蕩函數(shù)，所以這個(gè)周期函數(shù)用數(shù)學(xué)公式可以表達(dá)為：
我們看到上圖中的信號(hào)是隨著時(shí)間變換的，所以我稱之為「時(shí)域（Time domain）」。
我們觀察到，不同的振蕩函數(shù)具有不同的振幅和頻率，以上圖為例 的振幅為 1/3 而頻率為 ，考慮以頻率為橫坐標(biāo)，振幅為縱坐標(biāo)，我們有：
這個(gè)就是我們所說的頻域（Frequency Domain），其和時(shí)域是等價(jià)的，不過是從另外一個(gè)角度去描述信號(hào)。我們把它放在一起看一下：
我們可以放一張動(dòng)圖感受一下：
給出傅立葉級(jí)數(shù)的公式：
還可以將其稍作變換：
這樣我們便能看出來，此時(shí)的標(biāo)準(zhǔn)正交基為
這里介紹下傅立葉變換后的基為正交基，因?yàn)橛袀€(gè)知識(shí)點(diǎn)后面還會(huì)用到。
我們知道判斷兩個(gè)向量是否正交可以用向量點(diǎn)乘求和等于 0 來判斷，這種方法我們稱為點(diǎn)積（內(nèi)積）：
與向量點(diǎn)積不同的是，函數(shù)是連續(xù)的，假設(shè)現(xiàn)在有兩個(gè)函數(shù) f 和 g，f 的周期為 2n，我們也想用上述連續(xù)累加的方式來使得函數(shù)內(nèi)積和向量?jī)?nèi)積的概念一致，而積分正是函數(shù)累加的概念，所以我們有：
對(duì)于上面我們說的傅立葉變換后的正交基，我們?nèi)菀椎玫剑?/p>
容易證明上述標(biāo)準(zhǔn)基為正交基。
在數(shù)學(xué)里，希爾伯特空間（Hilbert Space）是有限維歐幾里得空間的一個(gè)推廣，是一個(gè)完備的內(nèi)積空間，其定義了一個(gè)帶有內(nèi)積的完備向量空間。在希爾伯空間中，一個(gè)抽象元素通常被稱為向量，它可以是一個(gè)復(fù)數(shù)或者函數(shù)。傅立葉分析的一個(gè)重要目的是將一個(gè)給定的函數(shù)表示成一族給定的基底函數(shù)的和，而希爾伯特空間為傅立葉分析提供了一種有效的表述方式。
可能大家看到這里要爆炸了，不過不用擔(dān)心，我們只需要記住上面「兩個(gè)函數(shù)的內(nèi)積形式」即可。
我們剛剛說的都是周期性函數(shù)，但現(xiàn)實(shí)中大部分函數(shù)都是非周期的，那如果涉及到非周期性函數(shù)該怎么辦呢？
在介紹非周期性函數(shù)之前，我們先簡(jiǎn)單介紹下歐拉公式。
考慮橫軸為 1，縱軸為虛單位 i 的坐標(biāo)系，圖上任意一點(diǎn)都可以表示為 。
根據(jù)歐拉公式，我們可以寫成：
其中，e 為自然對(duì)數(shù)的底數(shù)。
所以坐標(biāo)軸上的點(diǎn)現(xiàn)在有了兩種表示方式：
考慮 ， 會(huì)隨著 t 的增大而逆時(shí)針旋轉(zhuǎn)。所以 可以表示為坐標(biāo)點(diǎn) A 隨著時(shí)間 t 逆時(shí)針旋轉(zhuǎn)。我們以時(shí)間 t 為橫坐標(biāo)，則可以記錄到坐標(biāo)點(diǎn) A 映射在虛軸的運(yùn)動(dòng)軌跡：
左邊圖是我們看到的旋轉(zhuǎn)頻率，稱為頻域，而右邊圖看到是時(shí)間流逝，稱為時(shí)域，是不是和我們剛剛介紹的（從時(shí)域變換到頻域）正好相反？也就是說，時(shí)域和頻域其實(shí)是可以相互轉(zhuǎn)換的。
回到正題，考慮非周期函數(shù)的傅立葉變換。
事實(shí)上，我們可以將非周期函數(shù)考慮為周期無窮大的函數(shù)，考慮頻域中的橫坐標(biāo)：，當(dāng)周期 T 無窮大大時(shí)，頻域圖就從離散點(diǎn)變?yōu)檫B續(xù)的曲線，如下圖：
那么，我們?cè)撊绾螐倪@個(gè)非周期函數(shù)中分解出各種信號(hào)呢？答案就是利用正交！比如說，假設(shè)這函數(shù)中有一個(gè) 的信號(hào)，那么我們用 就可以把它乘出來，而其他分量如
其中， 剛剛介紹過，就是一組正交基的組合。我們用正交基去與函數(shù)求內(nèi)積，如果原函數(shù)中包含頻率為 的三角函數(shù)，則 便為 0，反之為 0，這樣自然分離能分離出相應(yīng)的信號(hào)，其圖示如上圖 c 中右部分所示。
細(xì)心的同學(xué)可能還會(huì)注意到上式的計(jì)算的結(jié)果中還有復(fù)數(shù) i。其實(shí)是樣子的：「實(shí)數(shù)部分表示振幅」，「虛數(shù)部分表示相位」。相關(guān)資料同學(xué)們可以自己查閱，不再進(jìn)行過多介紹。
以上就是我們所說的傅立葉變換（Fourier Transform，F(xiàn)T）。同樣的我們也存在逆變換：
于是，我們便實(shí)現(xiàn)了將信號(hào)拆成多個(gè)正弦信號(hào)，再把正弦信號(hào)逆變換為原來信號(hào)的過程。
簡(jiǎn)單介紹下傅立葉變換的應(yīng)用吧， 省得看了那么多不知道他能干什么。
一個(gè)很經(jīng)典的例子就是：分離、降噪。如果男生和女生一起說話，該如何分離出兩者的聲音呢？答案就是對(duì)這一段聲音（時(shí)域）做傅立葉變換轉(zhuǎn)換到頻率，而男女生的聲音頻率不同，在頻域中，低頻為男生，中頻為女生，高頻可能為噪音，我們可以根據(jù)需要去除中頻和高頻的信號(hào)，并將其進(jìn)行逆變換，這樣便分離出了男生的聲音。
PS：這里再說一個(gè)好玩的，頻域中是不是不存在時(shí)間的概念？不存在時(shí)間卻可以表示時(shí)間，這有沒有一點(diǎn)像我們的人生，看似無規(guī)律，但是從上帝視角來看，一切皆命中注定。
圖拉普拉斯矩陣可以定義為：
其中，D 為度矩陣，W 為考慮權(quán)值的鄰接矩陣。
考慮歸一化后的拉普拉斯矩陣：
以上為常規(guī)操作，不過介紹到這里不知道大家會(huì)不會(huì)有一點(diǎn)疑問。
至少我是有疑問的：圖拉普拉斯矩陣為什么要這樣定義的？
要想回答這個(gè)問題，首先我們得了解什么是拉普拉斯算子。
在數(shù)學(xué)中，拉普拉斯算子（Laplacian）是由歐幾里得空間中的一個(gè)函數(shù)的梯度的散度給出的微分算子，通常有以下幾種寫法：。所以對(duì)于任意函數(shù) 來說，其拉普拉斯算子的定義為：
這里引入了一個(gè)新的概念——散度，這里簡(jiǎn)單介紹下：
散度（Divergence）是向量分析的一個(gè)向量算子，將向量空間上的向量場(chǎng)（矢量場(chǎng)）對(duì)應(yīng)到一個(gè)標(biāo)量場(chǎng)。散度描述的是向量場(chǎng)里一個(gè)點(diǎn)是匯聚點(diǎn)還是發(fā)源點(diǎn)。值為正時(shí)表示該點(diǎn)為發(fā)源點(diǎn)，值為負(fù)時(shí)表示該點(diǎn)為匯聚點(diǎn)，值為零時(shí)表示該點(diǎn)無源。散度在物理上的含義可以理解為磁場(chǎng)、熱源等。
回到正文，我們看下拉普拉斯算子在 n 維空間中的笛卡爾坐標(biāo)系的數(shù)學(xué)定義：
數(shù)學(xué)表示為各個(gè)維度的二階偏導(dǎo)數(shù)之和。
以一維空間為例：
也就是說二階導(dǎo)數(shù)近似于其二階差分，可以理解為當(dāng)前點(diǎn)對(duì)其在所有自由度上微擾之后獲得的增益。這里自由度為 2，分別是 +1 和 -1 方向。
再以二維空間為例子：
看到上面可能大家會(huì)很可能很陌生，但是這個(gè)就是圖像中的拉普拉斯卷積核：
此時(shí)共有 4 個(gè)自由度 (1,0),(-1,0),(0,1),(0,-1)，當(dāng)然如果對(duì)角線后其自由度可以為 8。
對(duì)此我們可以進(jìn)行歸納：「拉普拉斯算子是所有自由度上進(jìn)行微小變化后所獲得的增益」。
我們將其推廣到網(wǎng)絡(luò)圖中，考慮有 N 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)圖，其自由度最大為 N，那么函數(shù) 可以是 N 維的向量，即：
其中， 表示函數(shù) 在網(wǎng)絡(luò)圖中節(jié)點(diǎn) i 處的函數(shù)值，類比 為函數(shù) 在 (x,y) 的函數(shù)值。
在網(wǎng)絡(luò)圖中，兩個(gè)節(jié)點(diǎn)的之間的增益為 ，考慮加權(quán)圖則有 ，那么對(duì)于節(jié)點(diǎn) i 來說，總增益即為拉普拉斯算子在節(jié)點(diǎn) i 的值：
其中， 為節(jié)點(diǎn) i 的度；上式第二行去掉了 是因?yàn)?可以控制節(jié)點(diǎn) i 的鄰接矩陣。
對(duì)于任意 都成立，所以我們有：
自此，我們便給出了圖拉普拉斯矩陣的推導(dǎo)過程，這個(gè)公式的全稱為：圖拉普拉斯算子作用在由圖節(jié)點(diǎn)信息構(gòu)成的向量 上得到的結(jié)果等于圖拉普拉斯矩陣和向量 的點(diǎn)積。拉普拉斯矩陣反映了當(dāng)前節(jié)點(diǎn)對(duì)周圍節(jié)點(diǎn)產(chǎn)生擾動(dòng)時(shí)所產(chǎn)生的累積增益，直觀上也可以理解為某一節(jié)點(diǎn)的權(quán)值變?yōu)槠湎噜徆?jié)點(diǎn)權(quán)值的期望影響，形象一點(diǎn)就是拉普拉斯矩陣可以刻畫局部的平滑度。
拉普拉斯矩陣的譜分解就是矩陣的特征分解：
對(duì)于無向圖來說，拉普拉斯矩陣是實(shí)對(duì)稱矩陣，而實(shí)對(duì)稱矩陣一定可以用正交矩陣進(jìn)行正交相似對(duì)角化：
其中， 為特征值構(gòu)成「對(duì)角矩陣」， 為特征向量構(gòu)成的「正交矩陣」。
又因?yàn)檎痪仃嚨哪娴扔谡痪仃嚨霓D(zhuǎn)置： ，所以我們有：
因?yàn)?L 是半正定矩陣，我們還可以有：
其中， 為節(jié)點(diǎn) i 的信號(hào)。我們稱 為圖信號(hào)的總變差（Total Variation），可以刻畫圖信號(hào)整體的平滑度。
拉普拉斯的譜分解具有以下幾點(diǎn)性質(zhì)：
有同學(xué)看到這可能會(huì)感到疑問了：「我們剛介紹傅立葉變換，現(xiàn)在又介紹拉普拉斯譜分解的，到底想干嘛」。
這是因?yàn)椋?strong>「傅立葉分析是拉普拉斯譜分析的一個(gè)特例」！想不到吧，是不是很震驚？
我們來證明下，首先考慮亥姆霍茲方程（Helmholtz Equation）：
其中， 為拉普拉斯算子， 為特征函數(shù)， 為特征值。
看不懂不要緊，把它當(dāng)成廣義特征方程就行：，狹隘的特征方程只能用于處理向量和矩陣，而這個(gè)可以用于處理函數(shù)，最經(jīng)典的應(yīng)用是處理波動(dòng)方程和擴(kuò)散方程，所以我們可以用它處理信號(hào)。
回顧一下傅立葉變換：
其實(shí)就是信號(hào)函數(shù) 與基函數(shù) 的內(nèi)積（剛剛介紹過函數(shù)內(nèi)積）。
對(duì)于基函數(shù) ，我們讓其與拉普拉斯算子求內(nèi)積：
以上便證明 是「拉普拉斯算子的特征函數(shù)」，同時(shí)也證明了「離散傅立葉變換是拉普拉斯譜分析的一個(gè)特例」。
寫到這我們有以下線索：首先拉普拉斯矩陣（離散拉普拉斯算子）可以應(yīng)用在圖像上，理論上也可以應(yīng)用到網(wǎng)絡(luò)上，而傅立葉變換是拉普拉斯的一個(gè)小弟，所以小弟也可以應(yīng)用到圖上。
回顧下拉普拉斯譜分析：
我們類比一下：
| 信號(hào)中的傅立葉變換 | 網(wǎng)絡(luò)圖中的傅立葉變換 |
|---|---|
| 頻率 | 特征值 |
| 正交基中某個(gè)向量 | 正交矩陣中的某個(gè)向量 |
是不是長(zhǎng)得非常像，所以我們也有了網(wǎng)絡(luò)圖上的傅立葉變換：
其中， 為網(wǎng)絡(luò)圖上的 n 維向量， 表示網(wǎng)絡(luò)中的節(jié)點(diǎn) i 的第 k 個(gè)分量， 表示特征向量 k 的第 i 個(gè)分量。做個(gè)類比解釋：特征值（頻率） 下， 的圖傅立葉變換（振幅）等于 與 對(duì)應(yīng)的特征向量 的內(nèi)積。
考慮矩陣乘法：
所以我們得到了「圖傅立葉變換的矩陣形式」，這里的 為拉普拉斯譜分解的正交矩陣。
我們也可以得到傅立葉逆變換：
前面的鋪墊很多，終于要迎來 GCN 了。
我們先來看一下卷積的定義，卷積是指通過兩個(gè)函數(shù) 和 生成第三個(gè)函數(shù)的一種數(shù)學(xué)算子，表征函數(shù) 與經(jīng)過翻轉(zhuǎn)和平移的 的乘積函數(shù)所圍成的曲邊梯形的面積：
對(duì)于離散卷積來說，我們可以定義為：
計(jì)算卷積有很多種方法，除了直接計(jì)算外，我們還可以考慮「卷積定理」：在適當(dāng)條件下，兩個(gè)信號(hào)的卷積的傅立葉變換是他們的傅立葉變換的點(diǎn)積。換句話說，一個(gè)域（如時(shí)域）的卷積等于另一個(gè)域（如頻域）的點(diǎn)乘：
其中 表示 的傅立葉變換。
借助傅立葉逆變換 可以寫成：
這樣做有什么好處呢？或者說，我們?yōu)槭裁匆儞Q一個(gè)域后再去做卷積操作？
因?yàn)槔镁矸e定理可以簡(jiǎn)化卷積的運(yùn)算量。對(duì)于一個(gè)長(zhǎng)度為 n 的序列，按照卷積的定義來計(jì)算則需要做 2n-1 組對(duì)位乘法，即時(shí)間復(fù)雜度為 ；而利用傅立葉變換后，只需要計(jì)算一組對(duì)位乘法，而且離散傅立葉變換有快速的算法（快速傅立葉變換），所以總的計(jì)算復(fù)雜度為 。
現(xiàn)在有了圖傅立葉變換，又有了離散卷積操作，那么我們想：既然無法直接在空域進(jìn)行卷積，可否將圖信號(hào)映射到頻域后再做卷積操作。
所以我們有：
其中，向量 與向量 的元素點(diǎn)積，等價(jià)于將 組織成對(duì)角矩陣的形式進(jìn)行矩陣乘法，所以我們有：
最后我們?cè)僮蟪?nbsp; 進(jìn)行逆變換：
這里，我們不寫成 的主要原因在于，我們可以將其與深度學(xué)習(xí)相結(jié)合，在 GCN 中我們的卷積核是可訓(xùn)練并且參數(shù)共享的，所以在此我們可以直接將 寫成 ，這個(gè)便是深度學(xué)習(xí)中的可學(xué)習(xí)參數(shù)。
第一代的卷積神經(jīng)網(wǎng)絡(luò)也就是剛剛我們給出的公式：
這和論文中給出的公式是一樣的：
這邊補(bǔ)充一點(diǎn)，在這篇論文中，作者還給出了一個(gè)基于空域的「深度局部連接網(wǎng)絡(luò)」（Deep Locally Connected Networks），我們可以簡(jiǎn)單看一下：
每一層變換定義為：
其中， 表示第 k 第 i 個(gè)節(jié)點(diǎn)； 表示第 k 層節(jié)點(diǎn) i 和節(jié)點(diǎn) j 的權(quán)值，考慮局部鄰居； 表示卷積運(yùn)算； 表示第 k 層的池化操作。也就是說每個(gè)節(jié)點(diǎn)都是由其鄰居和自身卷積池化得到。
雖然看起來很簡(jiǎn)單，但是優(yōu)點(diǎn)在于它不需要很強(qiáng)的前提假設(shè)，其只需要網(wǎng)絡(luò)具有局部鄰域結(jié)構(gòu)，甚至不需要很好的 Embedding 向量。
但這種結(jié)構(gòu)下有一個(gè)很大的缺點(diǎn)：「沒有辦法實(shí)現(xiàn)共享參數(shù)」。
作者針對(duì)這種問題提出了我們所看到第一代圖卷積神經(jīng)網(wǎng)絡(luò)。
第一代的圖卷積神經(jīng)網(wǎng)絡(luò)很巧妙的利用圖譜理論來實(shí)現(xiàn)拓?fù)鋱D的卷積操作，但其有很多缺點(diǎn)，比如說：計(jì)算復(fù)雜度太高，我們需要對(duì)拉普拉斯矩陣進(jìn)行譜分解得到特征向量矩陣 ，時(shí)間復(fù)雜度為 ；
針對(duì)這個(gè)問題，學(xué)者提出了第二代 GCN。
首先我們回顧下圖傅立葉變換：
可以看到這是一個(gè)和特征值密切相關(guān)的函數(shù)，我們不妨將 寫成拉普拉斯矩陣 L 的特征值函數(shù) ：
然后這個(gè)卷積核有兩個(gè)局限性：
為了克服這個(gè)缺點(diǎn)，我們引入 K 階多項(xiàng)式：
其中，參數(shù) 是多項(xiàng)式系數(shù)，這樣濾波器就具有了 K 階局部性了，復(fù)雜度也降低到 。
我們將這個(gè)公式帶入卷積運(yùn)算中：
此時(shí)，我們計(jì)算圖卷積運(yùn)算就不需要再乘上特征向量矩陣 ，而是直接使用拉普拉斯矩陣 L 的 k 次方，這樣就避免了進(jìn)行特征分解。而我們可以事先計(jì)算好 ，這樣就只需要計(jì)算矩陣相乘。同時(shí)由于 L 為稀疏矩陣，所以時(shí)間復(fù)雜度為 ， 為節(jié)點(diǎn)邊數(shù)。
此外，作者還引入了切比雪夫展開式來近似 。
設(shè) 為切比雪夫多項(xiàng)式的第 k 階式子，切比雪夫多項(xiàng)式的遞歸式為：
其中， ； 是指拉普拉斯矩陣 L 的最大值。
?這是因?yàn)榍斜妊┓蚨囗?xiàng)式的輸入要在 之間，由于拉普拉斯矩陣的半正定性，所以所有的特征值都是大于等于 0 的，將其除以最大特征值可以將特征壓縮到 區(qū)間內(nèi)，現(xiàn)在需要將其壓縮到 ，所以我們有：
?
我們將切比雪夫多項(xiàng)式引入到我們的卷積變換中：
其中， 。這個(gè)表達(dá)式為拉普拉斯多項(xiàng)式中的一個(gè) k 階近似函數(shù)，依賴于節(jié)點(diǎn)的 「k 階鄰域」（走 k 步能到的鄰居），時(shí)間復(fù)雜度與邊呈線形相關(guān)。
第二代 GCN 解決了圖卷機(jī)要求特征分解的問題，但是在計(jì)算圖卷積操作時(shí)，依然每次都要進(jìn)行矩陣乘法，時(shí)間復(fù)雜度為 ，于是學(xué)者繼續(xù)優(yōu)化。
我們把上式拿下來：
GCN 通過上式的多層卷積層進(jìn)行疊加，而每層都會(huì)逐點(diǎn)進(jìn)行非線性疊加，考慮到時(shí)間復(fù)雜度問題，學(xué)者直接取 K=2，也就是說得到了一個(gè)拉普拉斯算子的二階近似函數(shù)。這樣我們既可以對(duì)網(wǎng)絡(luò)進(jìn)行卷積操作，又不會(huì)引入太多的切比雪夫系數(shù)。而且這樣的線形運(yùn)算允許我們構(gòu)建更深的網(wǎng)路，提高模型的建模能力。
我們知道歸一化的拉普拉斯矩陣的特征值區(qū)間為 [0, 2]，進(jìn)一步近似 ，所以我們有新的表達(dá)式：
其中， 為切比雪夫系數(shù)的向量，是僅有的兩個(gè)參數(shù)。
在實(shí)際訓(xùn)練過程中，我們需要規(guī)范化參數(shù)來避免過擬合，所以我們令 ，從而有：
需要注意的是， 的特征值范圍在 [0, 2] 之間，所以如果在很深的網(wǎng)絡(luò)中會(huì)引起梯度爆炸的問題，所以我們需要再次對(duì)他進(jìn)行一次歸一化（原文也稱 「renormalization trick」）：
我們把這個(gè)公式從標(biāo)量推廣到矩陣，對(duì)于輸入節(jié)點(diǎn)的向量 ，其中 N 為節(jié)點(diǎn)數(shù)，C 為節(jié)點(diǎn)的特征向量維度，我們有：
其中， 是濾波器的參數(shù)矩陣， 是卷積后的信號(hào)矩陣，時(shí)間復(fù)雜度為 。節(jié)點(diǎn)的向量可以通過卷積操作從 C 維度 轉(zhuǎn)變?yōu)?F 維度。
依據(jù)上面的單層運(yùn)算，我們給出了多層圖卷積網(wǎng)絡(luò)的傳播規(guī)則：
其中， ，A 為鄰接矩陣， 為單位矩陣，所以 為添加自連接的鄰接矩陣； ， 可以理解為對(duì)角線為節(jié)點(diǎn) i 的度數(shù)矩陣； 為神經(jīng)網(wǎng)絡(luò)第 層的權(quán)重矩陣； 是激活函數(shù)； 是第 層的激活矩陣，并且 ， 是由節(jié)點(diǎn) 的特征向量組成矩陣。
到此，便完成了 GCN 卷積操作的公式推導(dǎo)。
再來關(guān)注一下模型。
圖卷積神經(jīng)網(wǎng)絡(luò)是指在圖結(jié)構(gòu)中做卷積操作的神經(jīng)網(wǎng)絡(luò)，所以其輸入輸出的都是圖結(jié)構(gòu)，區(qū)別于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，其隱藏層是直接在圖結(jié)構(gòu)中進(jìn)行激活：
為了方便理解，我們舉個(gè)分類任務(wù)例子，以包含一個(gè)隱藏層的 GCN 為例：
由于知道了 GCN 的傳播規(guī)則，所以我們有最終的結(jié)果：
其中， 是輸入層到隱藏層的權(quán)重， 是隱藏層到輸出層的權(quán)重；用 Softmax 是因?yàn)檫@是一個(gè)節(jié)點(diǎn)分類任務(wù)，需要預(yù)測(cè)標(biāo)簽。
然后，我們用交叉熵作為代價(jià)函數(shù)：
其中， 為有標(biāo)簽的節(jié)點(diǎn)集合。
有了代價(jià)函數(shù)后，我們可以通過梯度下降來更新網(wǎng)絡(luò)的參數(shù)。
簡(jiǎn)單看下第三代 GCN 的試驗(yàn)。
由于 GCN 比較復(fù)雜，所以這里我將給出兩種實(shí)驗(yàn)，一種是 GCN 的效果實(shí)驗(yàn)，另一種是模擬 GCN 運(yùn)行的實(shí)驗(yàn)。
我們來看一下實(shí)驗(yàn)部分，GCN 與其他模型的對(duì)比：
可以看到 GCN 的結(jié)果在不同數(shù)據(jù)集上都取得了非常好的效果，遠(yuǎn)超其他模型。
我們?cè)倏匆幌?，?duì)于 GCN 而言不同程度的近似會(huì)有什么樣的效果：
可以看到并不是模型越復(fù)雜效果越好。
GCN 還有除了訓(xùn)練后模型精度高外，還有兩個(gè)非常硬核的地方，即使不訓(xùn)練，直接隨機(jī)參數(shù)也可以獲得不錯(cuò)的效果，下圖展示了在某一數(shù)據(jù)集下隨機(jī)賦權(quán)值的結(jié)果：
另外，作為半監(jiān)督學(xué)習(xí)，GCN 可以在只標(biāo)注少量樣本的情況下學(xué)得出色的效果，下圖為每個(gè)類別只標(biāo)注一個(gè)樣本的分類結(jié)果：
為了更加形象的理解 GCN，我們來對(duì) GCN 進(jìn)行模擬。
首先，以一個(gè)簡(jiǎn)單有向圖模型為例：
鄰接矩陣 A 和 節(jié)點(diǎn)的特征向量 X 為：
我們有一個(gè)簡(jiǎn)單的傳播規(guī)則（不考慮參數(shù)矩陣和激活函數(shù)）：
「可以看到節(jié)點(diǎn)的特征變成了其鄰居的特征之和！」
但這邊也就一些小問題：
為了解決這個(gè)問題，我們需要：
我們先看下加上單位矩陣的效果：
可以看到，加上單位矩陣的計(jì)算考慮了節(jié)點(diǎn)的特征。
再看下鄰接矩陣歸一化的效果：
鄰接矩陣被歸一化到 0 到 1 之間。
我們將兩個(gè)放在一起，并考慮參數(shù)矩陣 W：
所以我們有：
以上便完成了 GCN 的簡(jiǎn)單仿真。
我們回過頭來再來看一下網(wǎng)絡(luò)的傳播規(guī)則：
現(xiàn)在是不是更能明白為什么這么傳播了？
這里解釋一下歸一化為什么是兩邊乘上矩陣的 -1/2 次方。
這是因?yàn)閷?duì)稱歸一化的拉普拉斯矩陣其元素定義為：
我們仿真模擬的是用加權(quán)求和取平均的方式來聚合，而作者采用的是拉普拉斯變換。我這邊做一個(gè)化簡(jiǎn)大家可能個(gè)就會(huì)明白了：
區(qū)別于加權(quán)求和取平均的方式，拉普拉斯變換不但考慮當(dāng)前節(jié)點(diǎn)的 i 的度，還考慮其他節(jié)點(diǎn) j 的度。
GCN 的入門文章就介紹完了，大致思路為：CNN 中的卷積無法直接應(yīng)用于網(wǎng)絡(luò)圖中，所以引出了圖信號(hào)處理（Graph Signal Processing）中的 Graph Fourier Transformation，進(jìn)而定義 Graph Convolution，最后結(jié)合深度學(xué)習(xí)發(fā)展出來 GCN。
聯(lián)系客服
