“?本文的內(nèi)容包括圖卷積的基礎(chǔ)知識以及相關(guān)輔助理解的知識點，相信同學(xué)們看完后一定能平滑上手理解GCN！”

作者：苘郁蓁

來源：知乎專欄 郁蓁的機器學(xué)習(xí)筆記。

編輯：happyGirl

具體來說，本文包括什么：

• 圖網(wǎng)絡(luò)的有哪些種類，它們之間的區(qū)別和聯(lián)系是什么？

• 圖卷積的地位，圖卷積怎么理解？

• 有沒有一個圖卷積的通式，各種不同的公式怎么統(tǒng)一？

• 有沒有一個最簡單的例子說明網(wǎng)絡(luò)的訓(xùn)練過程？

• 想快速上手有哪些代碼實現(xiàn)和庫？

本文不包括

• 傅立葉算子到拉普拉斯算子到拉普拉斯矩陣的數(shù)學(xué)推倒，感興趣可以看參考文獻。

一文讀懂系列文章：

《一文讀懂Transformer和Attention》(https://zhuanlan.zhihu.com/p/90033981) 《一文讀懂殘差網(wǎng)絡(luò)ResNet》(https://zhuanlan.zhihu.com/p/91385516)

圖神經(jīng)網(wǎng)絡(luò)GNN相關(guān)系列文章：

《什么是Weisfeiler-Lehman(WL)算法和WL Test？》 (https://zhuanlan.zhihu.com/p/90645716)

《圖神經(jīng)網(wǎng)絡(luò)庫PyTorch geometric（PYG）零基礎(chǔ)上手教程》 (https://zhuanlan.zhihu.com/p/91229616)

---

圖網(wǎng)絡(luò)的分類

在最開始，我們先梳理一下經(jīng)常被提到的幾個術(shù)語的區(qū)別和聯(lián)系，也就是Graph Embedding，Graph Neural Network和Graph Convolutional Network的區(qū)別和聯(lián)系是什么。

Graph Embedding

圖嵌入（Graph Embedding/Network Embedding，GE），屬于表示學(xué)習(xí)的范疇，也可以叫做網(wǎng)絡(luò)嵌入，圖表示學(xué)習(xí)，網(wǎng)絡(luò)表示學(xué)習(xí)等等。通常有兩個層次的含義：

• 將圖中的節(jié)點表示成低維、實值、稠密的向量形式 ，使得得到的向量形式可以在向量空間中具有表示以及推理的能力，這樣的向量可以用于下游的具體任務(wù)中。例如用戶社交網(wǎng)絡(luò)得到節(jié)點表示就是每個用戶的表示向量，再用于節(jié)點分類等；

• 將整個圖表示成低維、實值、稠密的向量形式 ，用來對整個圖結(jié)構(gòu)進行分類；

圖嵌入的方式主要有三種：

• 矩陣分解： 基于矩陣分解的方法是將節(jié)點間的關(guān)系用矩陣的形式加以表達，然后分解該矩陣以得到嵌入向量。通常用于表示節(jié)點關(guān)系的矩陣包括鄰接矩陣，拉普拉斯矩陣，節(jié)點轉(zhuǎn)移概率矩陣，節(jié)點屬性矩陣等。根據(jù)矩陣性質(zhì)的不同適用于不同的分解策略。

• DeepWalk： DeepWalk 是基于 word2vec 詞向量提出來的。word2vec 在訓(xùn)練詞向量時，將語料作為輸入數(shù)據(jù)，而圖嵌入輸入的是整張圖，兩者看似沒有任何關(guān)聯(lián)。但是 DeepWalk 的作者發(fā)現(xiàn)，預(yù)料中詞語出現(xiàn)的次數(shù)與在圖上隨機游走節(jié)點被訪問到底的次數(shù)都服從冪律分布。因此 DeepWalk 把節(jié)點當(dāng)做單詞，把隨機游走得到的節(jié)點序列當(dāng)做句子，然后將其直接作為 word2vec 的輸入可以節(jié)點的嵌入表示，同時利用節(jié)點的嵌入表示作為下游任務(wù)的初始化參數(shù)可以很好的優(yōu)化下游任務(wù)的效果，也催生了很多相關(guān)的工作；

• Graph Neural Network： 圖結(jié)合deep learning方法搭建的網(wǎng)絡(luò)統(tǒng)稱為圖神經(jīng)網(wǎng)絡(luò)GNN，也就是下一小節(jié)的主要內(nèi)容，因此圖神經(jīng)網(wǎng)絡(luò)GNN可以應(yīng)用于圖嵌入來得到圖或圖節(jié)點的向量表示；

Graph Neural Network

圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network, GNN)是指神經(jīng)網(wǎng)絡(luò)在圖上應(yīng)用的模型的統(tǒng)稱，根據(jù)采用的技術(shù)不同和分類方法的不同，又可以分為下圖中的不同種類，例如從傳播的方式來看，圖神經(jīng)網(wǎng)絡(luò)可以分為圖卷積神經(jīng)網(wǎng)絡(luò)（GCN），圖注意力網(wǎng)絡(luò)（GAT，縮寫為了跟GAN區(qū)分），Graph LSTM等等，本質(zhì)上還是把文本圖像的那一套網(wǎng)絡(luò)結(jié)構(gòu)技巧借鑒過來做了新的嘗試。但在這篇文章中并不會細細介紹下面的每一種，作為入門篇，我們著重理解最經(jīng)典和最有意義的基礎(chǔ)模型GCN，這也是理解其他模型的基礎(chǔ)。

圖神經(jīng)網(wǎng)絡(luò)GNN的分類：分別從圖的類型，訓(xùn)練的方式，傳播的方式三個方面來對現(xiàn)有的圖模型工作進行劃分

Graph Convolutional Network

圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional Network, GCN)正如上面被分類的一樣，是一類采用圖卷積的神經(jīng)網(wǎng)絡(luò)，發(fā)展到現(xiàn)在已經(jīng)有基于最簡單的圖卷積改進的無數(shù)版本，在圖網(wǎng)絡(luò)領(lǐng)域的地位正如同卷積操作在圖像處理里的地位。

GCN的區(qū)別和聯(lián)系

如圖2所示，這三個比較繞的概念可以用一句話來概括：圖卷積神經(jīng)網(wǎng)絡(luò)GCN屬于圖神經(jīng)網(wǎng)絡(luò)GNN的一類，是采用卷積操作的圖神經(jīng)網(wǎng)絡(luò)，可以應(yīng)用于圖嵌入GE。

卷積VS圖卷積

要理解圖卷積網(wǎng)絡(luò)的核心操作圖卷積，可以類比卷積在CNN的地位。

如下圖所示，數(shù)字圖像是一個二維的離散信號，對數(shù)字圖像做卷積操作其實就是利用卷積核（卷積模板）在圖像上滑動，將圖像點上的像素灰度值與對應(yīng)的卷積核上的數(shù)值相乘，然后將所有相乘后的值相加作為卷積核中間像素對應(yīng)的圖像上像素的灰度值，并最終滑動完所有圖像的過程。

用隨機的共享的卷積核得到像素點的加權(quán)和從而提取到某種特定的特征，然后用反向傳播來優(yōu)化卷積核參數(shù)就可以自動的提取特征，是CNN特征提取的基石 。

圖像卷積

然而，現(xiàn)實中 更多重要的數(shù)據(jù)集都是用圖的形式存儲的，例如社交網(wǎng)絡(luò)信息，知識圖譜，蛋白質(zhì)網(wǎng)絡(luò)，萬維網(wǎng)等等。這些圖網(wǎng)絡(luò)的形式并不像圖像，是排列整齊的矩陣形式，而是非結(jié)構(gòu)化的信息，那有沒有類似圖像領(lǐng)域的卷積一樣，有一個通用的范式來進行圖特征的抽取呢 ？這就是圖卷積在圖卷積網(wǎng)絡(luò)中的意義。

對于大多數(shù)圖模型，有一種類似通式的存在，這些模型統(tǒng)稱GCNs。因此可以說，圖卷積是處理非結(jié)構(gòu)化數(shù)據(jù)的大利器，隨著這方面研究的逐步深入，人類對知識領(lǐng)域的處理必將不再局限于結(jié)構(gòu)化數(shù)據(jù)（ CV，NLP），會有更多的目光轉(zhuǎn)向這一存在范圍更加廣泛，涵蓋意義更為豐富的知識領(lǐng)域。

接下來我們就來逐步拆解這個范式。

圖卷積

圖結(jié)構(gòu)實例

圖的定義

對于圖，我們有以下特征定義：

對于圖 ?? ， ?? 為節(jié)點的集合， ??為邊的集合，對于每個節(jié)點 ?? ， 均有其特征 ?? ，可以用矩陣?? 表示。其中 ?? 表示節(jié)點數(shù)， ??表示每個節(jié)點的特征數(shù)，也可以說是特征向量的維度。

圖卷積的形象化理解

在一頭扎進圖卷積公式之前，我們先從其他的角度理解一下這個操作的物理含義，有一個形象化的理解，我們在試圖得到節(jié)點表示的時候，容易想到的最方便有效的手段就是利用它周圍的節(jié)點，也就是它的鄰居節(jié)點或者鄰居的鄰居等等，這種思想可以歸結(jié)為一句話：

圖中的每個結(jié)點無時無刻不因為鄰居和更遠的點的影響而在改變著自己的狀態(tài)直到最終的平衡，關(guān)系越親近的鄰居影響越大。

實際上從鄰居節(jié)點獲取信息的思想在很多領(lǐng)域都有應(yīng)用，例如word2vec，例如pagerank。關(guān)于這個點展開的內(nèi)容文章[2]有非常詳細的解釋。

更加細節(jié)的如何從傅立葉變換到拉普拉斯算子到拉普拉斯矩陣的數(shù)學(xué)推倒可以轉(zhuǎn)向博客[7]，為了避免數(shù)學(xué)功底沒有那么強的初學(xué)者（比如我）被繞暈，我們先建立大綱，不要太發(fā)散。

圖相關(guān)矩陣的定義

那么有什么東西來度量節(jié)點的鄰居節(jié)點這個關(guān)系呢，學(xué)過圖論的就會自然而然的想到鄰接矩陣和拉普拉斯矩陣。舉個簡單的例子，對于下圖中的左圖（為了簡單起見，舉了無向圖且邊沒有權(quán)重的例子）而言，它的度矩陣?? ，鄰接矩陣 ?? 和拉普拉斯矩陣 ??分別如下圖所示，度矩陣 ?? 只有對角線上有值，為對應(yīng)節(jié)點的度，其余為0；鄰接矩陣 ??只有在有邊連接的兩個節(jié)點之間為1，其余地方為0；拉普拉斯矩陣 ?? 為 ??。但需要注意的是，這是最簡單的一種拉普拉斯矩陣，除了這種定義，還有接下來介紹的幾種拉普拉斯矩陣。

一個圖的度矩陣，鄰接矩陣和拉普拉斯矩陣

圖卷積的通式

任何一個圖卷積層都可以寫成這樣一個非線性函數(shù)：

? 為第一層的輸入， ?? ，?? 為圖的節(jié)點個數(shù)， ?? 為每個節(jié)點特征向量的維度， ?? 為鄰接矩陣，不同模型的差異點在于函數(shù) ?? 的實現(xiàn)不同。

下面介紹幾種具體的實現(xiàn)，但是每一種實現(xiàn)的參數(shù)大家都統(tǒng)稱拉普拉斯矩陣。

實現(xiàn)一

其中 ?? 為第 ?? 層的權(quán)重參數(shù)矩陣， ?? 為非線性激活函數(shù)，例如ReLU。

這種思路是基于節(jié)點特征與其所有鄰居節(jié)點有關(guān)的思想。鄰接矩陣 ?? 與特征 ??相乘，等價于，某節(jié)點的鄰居節(jié)點的特征相加。這樣多層隱含層疊加，能利用多層鄰居的信息。

但這樣存在兩個問題：

• 沒有考慮節(jié)點自身對自己的影響；

• 鄰接矩陣?? 沒有被規(guī)范化，這在提取圖特征時可能存在問題，比如鄰居節(jié)點多的節(jié)點傾向于有更大的影響力。

因此實現(xiàn)二和實現(xiàn)三針對這兩點進行了優(yōu)化。

實現(xiàn)二

拉普拉斯矩陣 ?? ，學(xué)名Combinatorial Laplacian，是針對實現(xiàn)一的問題1的改進：

• 引入了度矩陣，從而解決了沒有考慮自身節(jié)點信息自傳遞的問題

實現(xiàn)三

對于這里的拉普拉斯矩陣 ?? ，學(xué)名Symmetric normalized Laplacian，也有論文或者博客寫?? ， 就是一個符號的差別，但本質(zhì)上還是實現(xiàn)一的兩個問題進行的改進：

• 引入自身度矩陣，解決自傳遞問題；

• 對鄰接矩陣的歸一化操作，通過對鄰接矩陣兩邊乘以節(jié)點的度開方然后取逆得到。 具體到每一個節(jié)點對 ?，? ，矩陣中的元素由下面的式子給出（對于無向無權(quán)圖）：

其中 ?? 分別為節(jié)點 ??的度，也就是度矩陣在節(jié)點 ?? 處的值。

可能有一點比較疑惑的是怎么兩邊乘以一個矩陣的逆就歸一化了？ 這里需要復(fù)習(xí)到矩陣取逆的本質(zhì)是做什么。

我們回顧下矩陣的逆的定義，對于式子 ?? ，假如我們希望求矩陣X，那么當(dāng)然是令等式兩邊都乘以?? ，然后式子就變成了 ?? 。

舉個例子對于，單個節(jié)點運算來說，做歸一化就是除以它節(jié)點的度，這樣每一條鄰接邊信息傳遞的值就被規(guī)范化了，不會因為某一個節(jié)點有10條邊而另一個只有1條邊導(dǎo)致前者的影響力比后者大，因為做完歸一化后者的權(quán)重只有0.1了，從單個節(jié)點上升到二維矩陣的運算，就是對矩陣求逆了，乘以矩陣的逆的本質(zhì)，就是做矩陣除法完成歸一化。但左右分別乘以節(jié)點i,j度的開方，就是考慮一條邊的兩邊的點的度。

常見的拉普拉斯矩陣除了以上舉的兩種，還有 ??等等[3][4]，歸一化的方式有差別，根據(jù)論文[5]的實驗，這些卷積核的形式并沒有一種能夠在任何場景下比其他的形式效果好，因此在具體使用的時候可以進行多種嘗試，但主流的還是實現(xiàn)三，也就是大多數(shù)博客提到的。

另一種表述

上面是以矩陣的形式計算，可能會看起來非常讓人疑惑，下面從單個節(jié)點的角度來重新看下這些個公式（本質(zhì)是一樣的，上文解釋過，對于單個節(jié)點就是除法，對于矩陣就是乘以度矩陣的逆），對于第?? 層的節(jié)點的特征 ?? ，對于它的鄰接節(jié)點?? ， ?? 是節(jié)點 ??的所有鄰居節(jié)點的集合，可以通過以下公式計算得到：

其中， ?? ， ?? ，?? 為 ?? 的鄰居節(jié)點， ?? 為?? 的度，這跟上面的公式其實是等價的，所以有些地方的公式是這個，有些的上面那個。

碼字不易，覺得有收獲記得點贊哦～

更多內(nèi)容，歡迎點擊文末閱讀原文關(guān)注作者的專欄和作者交流！

參考文獻

[1] ?https:// ?zhuanlan.zhihu.com/p/77729049 圖嵌入的分類

[2] ?https://www.zhihu.com/question/54504471/answer/630639025 關(guān)于圖卷積的物理學(xué)解釋

[3] https://www.zhihu.com/question/54504471/answer/332657604拉普拉斯公式推倒細節(jié)，包括譜分解和傅立葉變換

[4] http://tkipf.github.io/graph-convolutional-networks 兩篇論文細講

[5] https://github.com/conferencesub/ICLR_2020各種圖卷積核比較

[6] https://persagen.com/files/misc/scarselli2009graph.pdfGNN首次被提出的paper

[7] https://zhuanlan.zhihu.com/p/85287578 拉普拉斯矩陣和拉普拉斯算子的關(guān)系

備注：公眾號菜單包含了整理了一本AI小抄，非常適合在通勤路上用學(xué)習(xí)。

往期精彩回顧 那些年做的學(xué)術(shù)公益-你不是一個人在戰(zhàn)斗適合初學(xué)者入門人工智能的路線及資料下載機器學(xué)習(xí)在線手冊深度學(xué)習(xí)在線手冊備注：加入本站微信群或者qq群，請回復(fù)“加群”加入知識星球（4500+用戶，ID：92416895），請回復(fù)“知識星球”

喜歡文章，點個在看

總結(jié)

以上是生活随笔為你收集整理的一文读懂图卷积GCN的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。