神經(jīng)網(wǎng)絡(luò)的基本知識(shí)，以及兩種更高級(jí)的算法：DeepWalk和GraphSage

圖神經(jīng)網(wǎng)絡(luò)(GNN)在各個(gè)領(lǐng)域越來越受歡迎，本文介紹了圖神經(jīng)網(wǎng)絡(luò)的基本知識(shí)，以及兩種更高級(jí)的算法：DeepWalk和GraphSage。

最近，圖神經(jīng)網(wǎng)絡(luò)(GNN)在各個(gè)領(lǐng)域越來越受到歡迎，包括社交網(wǎng)絡(luò)、知識(shí)圖譜、推薦系統(tǒng)，甚至生命科學(xué)。

GNN在對(duì)圖形中節(jié)點(diǎn)間的依賴關(guān)系進(jìn)行建模方面能力強(qiáng)大，使得圖分析相關(guān)的研究領(lǐng)域取得了突破性進(jìn)展。本文旨在介紹圖神經(jīng)網(wǎng)絡(luò)的基本知識(shí)，以及兩種更高級(jí)的算法：DeepWalk和GraphSage。

圖(Graph)

在討論GNN之前，讓我們先了解一下什么是圖(Graph)。在計(jì)算機(jī)科學(xué)中，圖是由兩個(gè)部件組成的一種數(shù)據(jù)結(jié)構(gòu)：頂點(diǎn)(vertices)和邊(edges)。一個(gè)圖G可以用它包含的頂點(diǎn)V和邊E的集合來描述。

邊可以是有向的或無向的，這取決于頂點(diǎn)之間是否存在方向依賴關(guān)系。

一個(gè)有向的圖(wiki)

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

圖神經(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è)沒有g(shù)round-truth的節(jié)點(diǎn)的標(biāo)簽。

本節(jié)將描述The graph neural network model(Scarselli, F., et al., 2009) [1]這篇論文中的算法，這是第一次提出GNN的論文，因此通常被認(rèn)為是原始GNN。

在節(jié)點(diǎn)分類問題設(shè)置中，每個(gè)節(jié)點(diǎn)v的特征x_v與一個(gè)ground-truth標(biāo)簽t_v相關(guān)聯(lián)。給定一個(gè)部分標(biāo)記的graph G，目標(biāo)是利用這些標(biāo)記的節(jié)點(diǎn)來預(yù)測(cè)未標(biāo)記的節(jié)點(diǎn)的標(biāo)簽。它學(xué)習(xí)用包含鄰域信息的d維向量h_v表示每個(gè)節(jié)點(diǎn)。即：

其中x_co[v]表示與v相連的邊的特征，h_ne[v]表示v相鄰節(jié)點(diǎn)的嵌入，x_ne[v]表示v相鄰節(jié)點(diǎn)的特征。函數(shù)f是將這些輸入映射到d維空間上的過渡函數(shù)。由于我們要尋找h_v的唯一解，我們可以應(yīng)用Banach不動(dòng)點(diǎn)定理，將上面的方程重寫為一個(gè)迭代更新過程。

H和X分別表示所有h和x的串聯(lián)。

通過將狀態(tài)h_v和特性x_v傳遞給輸出函數(shù)g，從而計(jì)算GNN的輸出。

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

可以通過梯度下降進(jìn)行優(yōu)化。

然而，原始GNN存在三個(gè)主要局限性：

如果放寬“不動(dòng)點(diǎn)” (fixed point)的假設(shè)，那么可以利用多層感知器學(xué)習(xí)更穩(wěn)定的表示，并刪除迭代更新過程。這是因?yàn)?，在原始論文中，不同的迭代使用轉(zhuǎn)換函數(shù)f的相同參數(shù)，而MLP的不同層中的不同參數(shù)允許分層特征提取。

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

不動(dòng)點(diǎn)會(huì)阻礙節(jié)點(diǎn)分布的多樣性，不適合學(xué)習(xí)表示節(jié)點(diǎn)。

為了解決上述問題，研究人員已經(jīng)提出了幾個(gè)GNN的變體。不過，它們不是本文的重點(diǎn)。

DeepWalk：第一個(gè)無監(jiān)督學(xué)習(xí)節(jié)點(diǎn)嵌入的算法

DeepWalk [2]是第一個(gè)提出以無監(jiān)督的方式學(xué)習(xí)節(jié)點(diǎn)嵌入的算法。

它在訓(xùn)練過程中非常類似于詞匯嵌入。其動(dòng)機(jī)是graph中節(jié)點(diǎn)和語料庫中單詞的分布都遵循冪律，如下圖所示：

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

在graph中的節(jié)點(diǎn)上執(zhí)行random walks，以生成節(jié)點(diǎn)序列

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

在random walks的每個(gè)時(shí)間步驟中，下一個(gè)節(jié)點(diǎn)從上一個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)均勻采樣。然后將每個(gè)序列截?cái)酁殚L(zhǎng)度為2|w| + 1的子序列，其中w表示skip-gram中的窗口大小。

本文采用hierarchical softmax來解決由于節(jié)點(diǎn)數(shù)量龐大而導(dǎo)致的softmax計(jì)算成本高昂的問題。為了計(jì)算每個(gè)單獨(dú)輸出元素的softmax值,我們必須計(jì)算元素k的所有e ^ xk。

Softmax的定義

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

分層softmax利用二叉樹來處理這個(gè)問題。在這個(gè)二叉樹中，所有的葉子(下圖中的v1, v2，…v8)都表示graph中的頂點(diǎn)。在每個(gè)內(nèi)部節(jié)點(diǎn)中，都有一個(gè)二元分類器來決定選擇哪條路徑。要計(jì)算給定頂點(diǎn)v_k的概率，只需計(jì)算從根節(jié)點(diǎn)到葉節(jié)點(diǎn)v_k路徑上每一個(gè)子路徑的概率。由于每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的概率之和為1，所以所有頂點(diǎn)的概率之和為1的特性在分層softmax中仍然保持不變。由于二叉樹的最長(zhǎng)路徑是O(log(n))，其中n表示葉節(jié)點(diǎn)的數(shù)量，因此一個(gè)元素的計(jì)算時(shí)間現(xiàn)在減少到O(log|V|)。

Hierarchical Softmax

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

然而，DeepWalk的主要問題是缺乏泛化能力。每當(dāng)一個(gè)新節(jié)點(diǎn)出現(xiàn)時(shí)，它必須重新訓(xùn)練模型以表示這個(gè)節(jié)點(diǎn)。因此，這種GNN不適用于圖中節(jié)點(diǎn)不斷變化的動(dòng)態(tài)圖。

GraphSage：學(xué)習(xí)每個(gè)節(jié)點(diǎn)的嵌入

GraphSage提供了解決上述問題的辦法，以一種歸納的方式學(xué)習(xí)每個(gè)節(jié)點(diǎn)的嵌入。

具體地說，GraphSage每個(gè)節(jié)點(diǎn)由其鄰域的聚合(aggregation)表示。因此，即使圖中出現(xiàn)了在訓(xùn)練過程中沒有看到的新節(jié)點(diǎn)，它仍然可以用它的鄰近節(jié)點(diǎn)來恰當(dāng)?shù)乇硎尽?/p>

下面是GraphSage算法：

外層循環(huán)表示更新迭代的數(shù)量，而h ^ k_v表示更新迭代k時(shí)節(jié)點(diǎn)v的潛在向量。在每次更新迭代時(shí)，h ^ k_v的更新基于一個(gè)聚合函數(shù)、前一次迭代中v和v的鄰域的潛在向量，以及權(quán)重矩陣W ^ k。

論文中提出了三種聚合函數(shù)：

1. Mean aggregator：

mean aggregator取一個(gè)節(jié)點(diǎn)及其所有鄰域的潛在向量的平均值。

與原始方程相比，它刪除了上面?zhèn)未a中第5行中的連接運(yùn)算。這種運(yùn)算可以看作是一種“skip-connection”，在論文后面的部分中，證明了這在很大程度上可以提高模型的性能。

2. LSTM aggregator：

由于圖中的節(jié)點(diǎn)沒有任何順序，因此它們通過對(duì)這些節(jié)點(diǎn)進(jìn)行排列來隨機(jī)分配順序。

3. Pooling aggregator：

這個(gè)運(yùn)算符在相鄰集上執(zhí)行一個(gè)element-wise的pooling函數(shù)。下面是一個(gè)max-pooling的示例：

論文使用max-pooling作為默認(rèn)的聚合函數(shù)。

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

其中u和v在固定長(zhǎng)度的random walk中共存，而v_n是不與u共存的負(fù)樣本。這種損失函數(shù)鼓勵(lì)距離較近的節(jié)點(diǎn)具有相似的嵌入，而距離較遠(yuǎn)的節(jié)點(diǎn)則在投影空間中被分離。通過這種方法，節(jié)點(diǎn)將獲得越來越多的關(guān)于其鄰域的信息。

GraphSage通過聚合其附近的節(jié)點(diǎn)，可以為看不見的節(jié)點(diǎn)生成可表示的嵌入。它允許將節(jié)點(diǎn)嵌入應(yīng)用到涉及動(dòng)態(tài)圖的域，其中圖的結(jié)構(gòu)是不斷變化的。例如，Pinterest采用了GraphSage的擴(kuò)展版本PinSage作為其內(nèi)容發(fā)現(xiàn)系統(tǒng)的核心。

總結(jié)

本文中，我們學(xué)習(xí)了圖神經(jīng)網(wǎng)絡(luò)、DeepWalk和GraphSage的基礎(chǔ)知識(shí)。GNN在復(fù)雜圖結(jié)構(gòu)建模方面的強(qiáng)大功能確實(shí)令人驚嘆。鑒于其有效性，我相信在不久的將來，GNN將在AI的發(fā)展中發(fā)揮重要作用。

[1] Scarselli, Franco, et al. "The graph neural network model.”

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1015.7227&rep=rep1&type=pdf

[2] Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations.”

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

[3] Hamilton, Will, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs.”

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