在這篇文章中，我們將仔細(xì)研究一個(gè)名為GCN的著名圖神經(jīng)網(wǎng)絡(luò)。首先，我們先直觀的了解一下它的工作原理，然后再深入了解它背后的數(shù)學(xué)原理。

為什么要用Graph?

許多問題的本質(zhì)上都是圖。在我們的世界里，我們看到很多數(shù)據(jù)都是圖，比如分子、社交網(wǎng)絡(luò)、論文引用網(wǎng)絡(luò)。

 

圖的例子。(圖片來自[1])

 

Graph上的任務(wù)

• 節(jié)點(diǎn)分類：預(yù)測特定節(jié)點(diǎn)的類型。
• 鏈接預(yù)測：預(yù)測兩個(gè)節(jié)點(diǎn)是否有聯(lián)系
• 社區(qū)檢測：識(shí)別密集聯(lián)系的節(jié)點(diǎn)群落。
• 網(wǎng)絡(luò)相似性：兩個(gè)(子)網(wǎng)絡(luò)的相似性有多大?

機(jī)器學(xué)習(xí)的生命周期

在圖中，我們有節(jié)點(diǎn)特征(代表節(jié)點(diǎn)的數(shù)據(jù))和圖的結(jié)構(gòu)(表示節(jié)點(diǎn)如何連接)。

對(duì)于節(jié)點(diǎn)來說，我們可以很容易地得到每個(gè)節(jié)點(diǎn)的數(shù)據(jù)。但是當(dāng)涉及到圖的結(jié)構(gòu)時(shí)，要從中提取有用的信息就不是一件容易的事情了。例如，如果2個(gè)節(jié)點(diǎn)彼此距離很近，我們是否應(yīng)該將它們與其他對(duì)節(jié)點(diǎn)區(qū)別對(duì)待呢?高低度節(jié)點(diǎn)又該如何處理呢?其實(shí)，對(duì)于每一項(xiàng)具體的工作，僅僅是特征工程，即把圖結(jié)構(gòu)轉(zhuǎn)換為我們的特征，就會(huì)消耗大量的時(shí)間和精力。

 

圖上的特征工程。(圖片來自[1])

 

如果能以某種方式同時(shí)得到圖的節(jié)點(diǎn)特征和結(jié)構(gòu)信息作為輸入，讓機(jī)器自己去判斷哪些信息是有用的，那就更好了。

這也是為什么我們需要圖表示學(xué)習(xí)的原因。

 

我們希望圖能夠自己學(xué)習(xí) "特征工程"。(圖片來自[1])

 

圖卷積神經(jīng)網(wǎng)絡(luò)(GCNs)

論文：基于圖神經(jīng)網(wǎng)絡(luò)的半監(jiān)督分類(2017)[3]

GCN是一種卷積神經(jīng)網(wǎng)絡(luò)，它可以直接在圖上工作，并利用圖的結(jié)構(gòu)信息。

它解決的是對(duì)圖(如引文網(wǎng)絡(luò))中的節(jié)點(diǎn)(如文檔)進(jìn)行分類的問題，其中僅有一小部分節(jié)點(diǎn)有標(biāo)簽(半監(jiān)督學(xué)習(xí))。

在Graphs上進(jìn)行半監(jiān)督學(xué)習(xí)的例子。有些節(jié)點(diǎn)沒有標(biāo)簽(未知節(jié)點(diǎn))。

主要思想

就像"卷積"這個(gè)名字所指代的那樣，這個(gè)想法來自于圖像，之后引進(jìn)到圖(Graphs)中。然而，當(dāng)圖像有固定的結(jié)構(gòu)時(shí)，圖(Graphs)就復(fù)雜得多。

 

從圖像到圖形的卷積思想。 (圖片來自[1])

 

GCN的基本思路：對(duì)于每個(gè)節(jié)點(diǎn)，我們從它的所有鄰居節(jié)點(diǎn)處獲取其特征信息，當(dāng)然也包括它自身的特征。假設(shè)我們使用average()函數(shù)。我們將對(duì)所有的節(jié)點(diǎn)進(jìn)行同樣的操作。最后，我們將這些計(jì)算得到的平均值輸入到神經(jīng)網(wǎng)絡(luò)中。

在下圖中，我們有一個(gè)引文網(wǎng)絡(luò)的簡單實(shí)例。其中每個(gè)節(jié)點(diǎn)代表一篇研究論文，同時(shí)邊代表的是引文。我們?cè)谶@里有一個(gè)預(yù)處理步驟。在這里我們不使用原始論文作為特征，而是將論文轉(zhuǎn)換成向量(通過使用NLP嵌入，例如tf-idf)。NLP嵌入，例如TF-IDF)。

讓我們考慮下綠色節(jié)點(diǎn)。首先，我們得到它的所有鄰居的特征值，包括自身節(jié)點(diǎn)，接著取平均值。最后通過神經(jīng)網(wǎng)絡(luò)返回一個(gè)結(jié)果向量并將此作為最終結(jié)果。

GCN的主要思想。我們以綠色節(jié)點(diǎn)為例。首先，我們?nèi)∑渌朽従庸?jié)點(diǎn)的平均值，包括自身節(jié)點(diǎn)。然后，將平均值通過神經(jīng)網(wǎng)絡(luò)。請(qǐng)注意，在GCN中，我們僅僅使用一個(gè)全連接層。在這個(gè)例子中，我們得到2維向量作為輸出(全連接層的2個(gè)節(jié)點(diǎn))。

在實(shí)際操作中，我們可以使用比average函數(shù)更復(fù)雜的聚合函數(shù)。我們還可以將更多的層疊加在一起，以獲得更深的GCN。其中每一層的輸出會(huì)被視為下一層的輸入。

2層GCN的例子：第一層的輸出是第二層的輸入。同樣，注意GCN中的神經(jīng)網(wǎng)絡(luò)僅僅是一個(gè)全連接層(圖片來自[2])。

讓我們認(rèn)真從數(shù)學(xué)角度看看它到底是如何起作用的。

直觀感受和背后的數(shù)學(xué)原理

首先，我們需要一些注解

我們考慮圖G，如下圖所示。

從圖G中，我們有一個(gè)鄰接矩陣A和一個(gè)度矩陣D。同時(shí)我們也有特征矩陣X。

那么我們?cè)鯓硬拍軓泥従庸?jié)點(diǎn)處得到每一個(gè)節(jié)點(diǎn)的特征值呢?解決方法就在于A和X的相乘。

看看鄰接矩陣的第一行，我們看到節(jié)點(diǎn)A與節(jié)點(diǎn)E之間有連接，得到的矩陣第一行就是與A相連接的E節(jié)點(diǎn)的特征向量(如下圖)。同理，得到的矩陣的第二行是D和E的特征向量之和，通過這個(gè)方法，我們可以得到所有鄰居節(jié)點(diǎn)的向量之和。

計(jì)算 "和向量矩陣 "AX的第一行。

這里還有一些需要改進(jìn)的地方。

• 我們忽略了節(jié)點(diǎn)本身的特征。例如，計(jì)算得到的矩陣的第一行也應(yīng)該包含節(jié)點(diǎn)A的特征。
• 我們不需要使用sum()函數(shù)，而是需要取平均值，甚至更好的鄰居節(jié)點(diǎn)特征向量的加權(quán)平均值。那我們?yōu)槭裁床皇褂胹um()函數(shù)呢?原因是在使用sum()函數(shù)時(shí)，度大的節(jié)點(diǎn)很可能會(huì)生成的大的v向量，而度低的節(jié)點(diǎn)往往會(huì)得到小的聚集向量，這可能會(huì)在以后造成梯度爆炸或梯度消失(例如，使用sigmoid時(shí))。此外，神經(jīng)網(wǎng)絡(luò)似乎對(duì)輸入數(shù)據(jù)的規(guī)模很敏感。因此，我們需要對(duì)這些向量進(jìn)行歸一化，以擺脫可能出現(xiàn)的問題。

在問題(1)中，我們可以通過在A中增加一個(gè)單位矩陣I來解決，得到一個(gè)新的鄰接矩陣Ã。

取lambda=1(使得節(jié)點(diǎn)本身的特征和鄰居一樣重要)，我們就有Ã=A+I，注意，我們可以把lambda當(dāng)做一個(gè)可訓(xùn)練的參數(shù)，但現(xiàn)在只要把lambda賦值為1就可以了，即使在論文中，lambda也只是簡單的賦值為1。

 

通過給每個(gè)節(jié)點(diǎn)增加一個(gè)自循環(huán)，我們得到新的鄰接矩陣

 

對(duì)于問題(2): 對(duì)于矩陣縮放，我們通常將矩陣乘以對(duì)角線矩陣。在當(dāng)前的情況下，我們要取聚合特征的平均值，或者從數(shù)學(xué)角度上說，要根據(jù)節(jié)點(diǎn)度數(shù)對(duì)聚合向量矩陣ÃX進(jìn)行縮放。直覺告訴我們這里用來縮放的對(duì)角矩陣是和度矩陣D̃有關(guān)的東西(為什么是D̃，而不是D?因?yàn)槲覀兛紤]的是新鄰接矩陣Ã 的度矩陣D̃，而不再是A了)。

現(xiàn)在的問題變成了我們要如何對(duì)和向量進(jìn)行縮放/歸一化?換句話說：

我們?nèi)绾螌⑧従拥男畔鬟f給特定節(jié)點(diǎn)?我們從我們的老朋友a(bǔ)verage開始。在這種情況下，D̃的逆矩陣(即，D̃^{-1})就會(huì)用起作用?；旧?，D̃的逆矩陣中的每個(gè)元素都是對(duì)角矩陣D中相應(yīng)項(xiàng)的倒數(shù)。

例如，節(jié)點(diǎn)A的度數(shù)為2，所以我們將節(jié)點(diǎn)A的聚合向量乘以1/2，而節(jié)點(diǎn)E的度數(shù)為5，我們應(yīng)該將E的聚合向量乘以1/5，以此類推。

因此，通過D̃取反和X的乘法，我們可以取所有鄰居節(jié)點(diǎn)的特征向量(包括自身節(jié)點(diǎn))的平均值。

到目前為止一切都很好。但是你可能會(huì)問加權(quán)平均()怎么樣?直覺上，如果我們對(duì)高低度的節(jié)點(diǎn)區(qū)別對(duì)待，應(yīng)該會(huì)更好。

 

但我們只是按行縮放，但忽略了對(duì)應(yīng)的列(虛線框)。

 

 

 

為列增加一個(gè)新的縮放器。

 

新的縮放方法給我們提供了 "加權(quán) "的平均值。我們?cè)谶@里做的是給低度的節(jié)點(diǎn)加更多的權(quán)重，以減少高度節(jié)點(diǎn)的影響。這個(gè)加權(quán)平均的想法是，我們假設(shè)低度節(jié)點(diǎn)會(huì)對(duì)鄰居節(jié)點(diǎn)產(chǎn)生更大的影響，而高度節(jié)點(diǎn)則會(huì)產(chǎn)生較低的影響，因?yàn)樗鼈兊挠绊懥Ψ稚⒃谔嗟泥従庸?jié)點(diǎn)上。

在節(jié)點(diǎn)B處聚合鄰接節(jié)點(diǎn)特征時(shí)，我們?yōu)楣?jié)點(diǎn)B本身分配最大的權(quán)重(度數(shù)為3)，為節(jié)點(diǎn)E分配最小的權(quán)重(度數(shù)為5)。

因?yàn)槲覀儦w一化了兩次，所以將"-1 "改為"-1/2"

 

例如，我們有一個(gè)多分類問題，有10個(gè)類，F(xiàn) 被設(shè)置為10。在第2層有了10個(gè)維度的向量后，我們將這些向量通過一個(gè)softmax函數(shù)進(jìn)行預(yù)測。

Loss函數(shù)的計(jì)算方法很簡單，就是通過對(duì)所有有標(biāo)簽的例子的交叉熵誤差來計(jì)算，其中Y_{l}是有標(biāo)簽的節(jié)點(diǎn)的集合。

層的數(shù)量

#layers的含義

層數(shù)是指節(jié)點(diǎn)特征能夠傳輸?shù)淖钸h(yuǎn)距離。例如，在1層的GCN中，每個(gè)節(jié)點(diǎn)只能從其鄰居那里獲得信息。每個(gè)節(jié)點(diǎn)收集信息的過程是獨(dú)立進(jìn)行的，對(duì)所有節(jié)點(diǎn)來說都是在同一時(shí)間進(jìn)行的。

當(dāng)在第一層的基礎(chǔ)上再疊加一層時(shí)，我們重復(fù)收集信息的過程，但這一次，鄰居節(jié)點(diǎn)已經(jīng)有了自己的鄰居的信息(來自上一步)。這使得層數(shù)成為每個(gè)節(jié)點(diǎn)可以走的最大跳步。所以，這取決于我們認(rèn)為一個(gè)節(jié)點(diǎn)應(yīng)該從網(wǎng)絡(luò)中獲取多遠(yuǎn)的信息，我們可以為#layers設(shè)置一個(gè)合適的數(shù)字。但同樣，在圖中，通常我們不希望走得太遠(yuǎn)。設(shè)置為6-7跳，我們就幾乎可以得到整個(gè)圖，但是這就使得聚合的意義不大。

 

例： 收集目標(biāo)節(jié)點(diǎn) i 的兩層信息的過程

 

GCN應(yīng)該疊加幾層?

在論文中，作者還分別對(duì)淺層和深層的GCN進(jìn)行了一些實(shí)驗(yàn)。在下圖中，我們可以看到，使用2層或3層的模型可以得到最好的結(jié)果。此外，對(duì)于深層的GCN(超過7層)，反而往往得到不好的性能(虛線藍(lán)色)。一種解決方案是借助隱藏層之間的殘余連接(紫色線)。

 

不同層數(shù)#的性能。圖片來自論文[3]

 

做好筆記

• GCNs用于圖上的半監(jiān)督學(xué)習(xí)。
• GCNs同時(shí)使用節(jié)點(diǎn)特征和結(jié)構(gòu)進(jìn)行訓(xùn)練
• GCN的主要思想是取所有鄰居節(jié)點(diǎn)特征(包括自身節(jié)點(diǎn))的加權(quán)平均值。度低的節(jié)點(diǎn)獲得更大的權(quán)重。之后，我們將得到的特征向量通過神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練。
• 我們可以堆疊更多的層數(shù)來使GCN更深?？紤]深度GCNs的殘差連接。通常，我們會(huì)選擇2層或3層的GCN。
• 數(shù)學(xué)筆記：當(dāng)看到對(duì)角線矩陣時(shí)，要想到矩陣縮放。
• 這里有一個(gè)使用StellarGraph庫的GCN演示[5]。該倉庫還提供了許多其他GNN的算法。

論文作者的說明

該框架目前僅限于無向圖(加權(quán)或不加權(quán))。但是，可以通過將原始有向圖表示為一個(gè)無向的兩端圖，并增加代表原始圖中邊的節(jié)點(diǎn)，來處理有向邊和邊特征。

下一步是什么呢?

對(duì)于GCN，我們似乎可以同時(shí)利用節(jié)點(diǎn)特征和圖的結(jié)構(gòu)。然而，如果圖中的邊有不同的類型呢?我們是否應(yīng)該對(duì)每種關(guān)系進(jìn)行不同的處理?在這種情況下如何聚合鄰居節(jié)點(diǎn)?最近有哪些先進(jìn)的方法?

在圖專題的下一篇文章中，我們將研究一些更復(fù)雜的方法。

如何處理邊的不同關(guān)系(兄弟、朋友、......)?