最近，圖神經(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。
在討論 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ò)是一種直接在圖結(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ù)測沒有 ground-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ù)測未標(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 [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度為 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 中仍然保持不變。由于二叉樹的最長路徑是 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 每個(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 在固定長度的 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)的核心。
本文中，我們學(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.”
[3] Hamilton, Will, Zhitao Ying, and Jure Leskovec. 'Inductive representation learning on large graphs.”
點(diǎn)擊“閱讀原文”查看原文
【加入社群】
新智元AI技術(shù)+產(chǎn)業(yè)社群招募中，歡迎對(duì)AI技術(shù)+產(chǎn)業(yè)落地感興趣的同學(xué)，_2 入群;通過審核后我們將邀請(qǐng)進(jìn)群，加入社群后務(wù)必修改群備注（姓名 - 公司 - 職位;專業(yè)群審核較嚴(yán)，敬請(qǐng)諒解）。
聯(lián)系客服
