圖形神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)知識(shí)兩種較高級(jí)的算法

近來(lái)，圖神經(jīng)網(wǎng)絡(luò)（GNN）在各個(gè)領(lǐng)域廣受關(guān)注，比如社交網(wǎng)絡(luò)，知識(shí)圖譜，推薦系統(tǒng)以及生命科學(xué)。GNN在對(duì)圖節(jié)點(diǎn)之間依賴關(guān)系進(jìn)行建模的強(qiáng)大功能使得與圖分析相關(guān)的研究領(lǐng)域取得了突破。 本文旨在介紹圖形神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)知識(shí)兩種較高級(jí)的算法，DeepWalk和GraphSage。

圖

在我們學(xué)習(xí)GAN之前，大家先了解一下什么圖。在計(jì)算機(jī)科學(xué)中，圖是一種數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)和邊組成。圖G可以通過(guò)頂點(diǎn)集合V和它包含的邊E來(lái)進(jìn)行描述。

根據(jù)頂點(diǎn)之間是否存在方向性，邊可以是有向或無(wú)向的。

頂點(diǎn)通常稱為節(jié)點(diǎn)。在本文中，這兩個(gè)術(shù)語(yǔ)是可以互換的。

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

圖神經(jīng)網(wǎng)絡(luò)是一種直接在圖結(jié)構(gòu)上運(yùn)行的神經(jīng)網(wǎng)絡(luò)。GNN的一個(gè)典型應(yīng)用是節(jié)點(diǎn)分類。本質(zhì)上，圖中的每個(gè)節(jié)點(diǎn)都與一個(gè)標(biāo)簽相關(guān)聯(lián)，我們希望預(yù)測(cè)未標(biāo)記節(jié)點(diǎn)的標(biāo)簽。本節(jié)將介紹論文中描述的算法，GNN的第一個(gè)提法，因此通常被視為原始GNN。

在節(jié)點(diǎn)分類問(wèn)題中，每個(gè)節(jié)點(diǎn)v都可以用其特征x_v表示并且與已標(biāo)記的標(biāo)簽t_v相關(guān)聯(lián)。給定部分標(biāo)記的圖G，目標(biāo)是利用這些標(biāo)記的節(jié)點(diǎn)來(lái)預(yù)測(cè)未標(biāo)記的節(jié)點(diǎn)標(biāo)簽。 它通過(guò)學(xué)習(xí)得到每個(gè)節(jié)點(diǎn)的d維向量（狀態(tài)）表示h_v，同時(shí)包含其鄰居的信息。

https://arxiv.org/pdf/1812.08434

x_co［v］ 代表連接頂點(diǎn)v的邊的特征，h_ne［v］代表頂點(diǎn)v的鄰居節(jié)點(diǎn)的嵌入表示，x_ne［v］代表頂點(diǎn)v的鄰居節(jié)點(diǎn)特征。f是將輸入投影到d維空間的轉(zhuǎn)移函數(shù)。由于要求出h_v的唯一解，我們應(yīng)用Banach不動(dòng)點(diǎn)理論重寫上述方程進(jìn)行迭代更新。

https://arxiv.org/pdf/1812.08434

H和X分別表示所有h和x的連接。

通過(guò)將狀態(tài)h_v以及特征x_v傳遞給輸出函數(shù)g來(lái)計(jì)算GNN的輸出。

https://arxiv.org/pdf/1812.08434

這里的f和g都可以解釋為全連接前饋神經(jīng)網(wǎng)絡(luò)。 L1損失可以直接表述如下：

https://arxiv.org/pdf/1812.08434

可以通過(guò)梯度下降優(yōu)化。

但是，本文指出的原始GNN有三個(gè)主要局限：

如果放寬了“固定點(diǎn)”的假設(shè)，則可以利用多層感知器來(lái)學(xué)習(xí)更穩(wěn)定的表示，并刪除迭代更新過(guò)程。 這是因?yàn)?，在原始方法中，不同的迭代使用轉(zhuǎn)移函數(shù)f的相同參數(shù)，而不同MLP層中的不同參數(shù)允許分層特征提取。

它不能處理邊緣信息（例如知識(shí)圖譜中的不同邊可能表示節(jié)點(diǎn)之間的不同關(guān)系）

固定點(diǎn)會(huì)限制節(jié)點(diǎn)分布的多樣化，因此可能不適合學(xué)習(xí)節(jié)點(diǎn)表示。

已經(jīng)提出了幾種GNN變體來(lái)解決上述問(wèn)題。 但是，他們不是這篇文章的重點(diǎn)。

DeepWalk

DeepWalk是第一個(gè)以無(wú)監(jiān)督學(xué)習(xí)的節(jié)點(diǎn)嵌入算法。 它在訓(xùn)練過(guò)程中類似于詞嵌入。 它的初衷是圖中的兩個(gè)節(jié)點(diǎn)分布和語(yǔ)料庫(kù)中的單詞分布都遵循冪律，如下圖所示：

http://www.perozzi.net/publications/14_kdd_deepwalk.pdf

算法包括兩個(gè)步驟：

在圖中的節(jié)點(diǎn)上執(zhí)行隨機(jī)游走生成節(jié)點(diǎn)序列

運(yùn)行skip-gram，根據(jù)步驟1中生成的節(jié)點(diǎn)序列學(xué)習(xí)每個(gè)節(jié)點(diǎn)的嵌入

在隨機(jī)游走過(guò)程中，下一個(gè)節(jié)點(diǎn)是從前一節(jié)點(diǎn)的鄰居統(tǒng)一采樣。 然后將每個(gè)序列截短為長(zhǎng)度為2 | w |+1的子序列，其中w表示skip-gram中的窗口大小。如果您不熟悉skip-gram，我之前的博客文章已經(jīng)向您介紹它的工作原理。

在論文中，分層softmax用于解決由于節(jié)點(diǎn)數(shù)量龐大而導(dǎo)致的softmax計(jì)算成本過(guò)高的問(wèn)題。為了計(jì)算每個(gè)單獨(dú)輸出元素的softmax值，我們必須為所有元素k計(jì)算ek。

softmax的定義

因此，原始softmax的計(jì)算時(shí)間是 O（|V|） ，其中其中V表示圖中的頂點(diǎn)集。

多層的softmax利用二叉樹來(lái)解決softmax計(jì)算成本問(wèn)題。 在二叉樹中，所有葉子節(jié)點(diǎn)（上面所說(shuō)的圖中的v1，v2，。.. v8）都是圖中的頂點(diǎn)。 在每個(gè)內(nèi)部節(jié)點(diǎn)中（除了葉子節(jié)點(diǎn)以外的節(jié)點(diǎn)，也就是分枝結(jié)點(diǎn)），都通過(guò)一個(gè)二元分類器來(lái)決定路徑的選取。 為了計(jì)算某個(gè)頂點(diǎn)v_k的概率，可以簡(jiǎn)單地計(jì)算沿著從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)v_k的路徑中的每個(gè)子路徑的概率。 由于每個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)的概率和為1，因此在多層softmax中，所有頂點(diǎn)的概率之和等于1的特性仍然能夠保持。如果n是葉子的數(shù)量，二叉樹的最長(zhǎng)路徑由O（log（n））限定，因此，元素的計(jì)算時(shí)間復(fù)雜度將減少到O（log | V |）。

多層softmax

（http://www.perozzi.net/publications/14_kdd_deepwalk.pdf）

在訓(xùn)練DeepWalk GNN之后，模型已經(jīng)學(xué)習(xí)到了了每個(gè)節(jié)點(diǎn)的良好表示，如下圖所示。 不同的顏色在輸入圖中（圖a）表示不同標(biāo)簽。 我們可以看到，在輸出圖（每個(gè)頂點(diǎn)被嵌入到2維平面）中，具有相同標(biāo)簽的節(jié)點(diǎn)聚集在一起，而具有不同標(biāo)簽的大多數(shù)節(jié)點(diǎn)被正確分開。

http://www.perozzi.net/publications/14_kdd_deepwalk.pdf

然而，DeepWalk的主要問(wèn)題是它缺乏泛化能力。 每當(dāng)有新節(jié)點(diǎn)加入到圖中時(shí)，它必須重新訓(xùn)練模型以正確表示該節(jié)點(diǎn)（ 直推式學(xué)習(xí) ）。 因此，這種GNN不適用于圖中節(jié)點(diǎn)不斷變化的動(dòng)態(tài)圖。

GraphSage

GraphSage提供了解決上述問(wèn)題的解決方案，它以歸納方式學(xué)習(xí)每個(gè)節(jié)點(diǎn)的嵌入。 具體來(lái)講，它將每個(gè)節(jié)點(diǎn)用其鄰域的聚合重新表示。 因此，即使在訓(xùn)練時(shí)間期間未出現(xiàn)在圖中新節(jié)點(diǎn)，也仍然可以由其相鄰節(jié)點(diǎn)正確地表示。 下圖展示了GraphSage的算法過(guò)程。

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

外層for循環(huán)表示更新迭代次數(shù)，而 h^k_v 表示節(jié)點(diǎn)v 在迭代第 k 次時(shí)的本征向量。 在每次迭代時(shí)，將通過(guò)聚合函數(shù)，前一次迭代中 v 和 v 領(lǐng)域的本征向量以及權(quán)重矩陣W^k 來(lái)更新h^k_v 。這篇論文提出了三種聚合函數(shù)：

1.均值聚合器：

均值聚合器取一個(gè)節(jié)點(diǎn)及其鄰域的本征向量的平均值。

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

與原始方程相比，它刪除了上述偽代碼中第5行的連接操作。 這種操作可以被視為“skip-connection” （“跳連接”），這篇論文后面將證明其可以在很大程度上提高模型的性能。

2. LSTM聚合器：

由于圖中的節(jié)點(diǎn)沒有任何順序，因此他們通過(guò)互換這些節(jié)點(diǎn)來(lái)隨機(jī)分配順序。

3.池聚合器：

此運(yùn)算符在相鄰頂點(diǎn)集上執(zhí)行逐元素池化函數(shù)。下面顯示了最大池的例子：

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

可以用平均池或任何其他對(duì)稱池函數(shù)替換這種最大池函數(shù)。盡管均值池和最大池聚合器性能相似，但是池聚合器（也就是說(shuō)采用最大池函數(shù)）被實(shí)驗(yàn)證明有最佳的性能。 這篇論文使用max-pooling作為默認(rèn)聚合函數(shù)

損失函數(shù)定義如下：

https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

其中u 和v 共同出現(xiàn)在一定長(zhǎng)度的隨機(jī)游走中，而 v_n 是不與u共同出現(xiàn)的負(fù)樣本。這種損失函數(shù)鼓動(dòng)節(jié)點(diǎn)在投影空間中更靠近嵌入距離更近的節(jié)點(diǎn)，而與那些相距很遠(yuǎn)的節(jié)點(diǎn)分離。通過(guò)這種方法，節(jié)點(diǎn)將獲得越來(lái)越多其鄰域的信息。

GraphSage通過(guò)聚合其附近的節(jié)點(diǎn)，可以為看不見的節(jié)點(diǎn)生成可表示的嵌入位置。它讓節(jié)點(diǎn)嵌入的方式可以被應(yīng)用于涉及動(dòng)態(tài)圖的研究領(lǐng)域，這類動(dòng)態(tài)圖的圖的結(jié)構(gòu)是可以不斷變化的。例如，Pinterest采用了GraphSage的擴(kuò)展版本PinSage作為他們的內(nèi)容探索系統(tǒng)的核心。

結(jié)束語(yǔ)

您已經(jīng)學(xué)習(xí)了圖形神經(jīng)網(wǎng)絡(luò)，DeepWalk和GraphSage的基礎(chǔ)知識(shí)。 GNN在復(fù)雜圖形結(jié)構(gòu)建模中的強(qiáng)大功能確實(shí)令人驚訝。鑒于其高效性，我相信GNN將在人工智能的發(fā)展中發(fā)揮重要作用。如果您覺得我的文章還不錯(cuò)，請(qǐng)不要忘記在Medium和Twitter上關(guān)注我，我經(jīng)常分享AI，ML和DL的高級(jí)發(fā)展動(dòng)態(tài)。