 最近，圖神經(jīng)網(wǎng)絡(luò) (GNN) 在各個領(lǐng)域越來越受到歡迎，包括社交網(wǎng)絡(luò)、知識圖譜、推薦系統(tǒng)，甚至生命科學(xué)。 GNN 在對圖形中節(jié)點間的依賴關(guān)系進行建模方面能力強大，使得圖分析相關(guān)的研究領(lǐng)域取得了突破性進展。本文旨在介紹圖神經(jīng)網(wǎng)絡(luò)的基本知識，以及兩種更高級的算法：DeepWalk 和 GraphSage。 在討論 GNN 之前，讓我們先了解一下什么是圖 (Graph)。在計算機科學(xué)中，圖是由兩個部件組成的一種數(shù)據(jù)結(jié)構(gòu)：頂點 (vertices) 和邊 (edges)。一個圖 G 可以用它包含的頂點 V 和邊 E 的集合來描述。 邊可以是有向的或無向的，這取決于頂點之間是否存在方向依賴關(guān)系。  一個有向的圖 (wiki) 頂點通常也被稱為節(jié)點 (nodes)。在本文中，這兩個術(shù)語是可以互換的。 圖神經(jīng)網(wǎng)絡(luò)是一種直接在圖結(jié)構(gòu)上運行的神經(jīng)網(wǎng)絡(luò)。GNN 的一個典型應(yīng)用是節(jié)點分類。本質(zhì)上，圖中的每個節(jié)點都與一個標簽相關(guān)聯(lián)，我們的目的是預(yù)測沒有 ground-truth 的節(jié)點的標簽。 本節(jié)將描述 The graph neural network model (Scarselli, F., et al., 2009) [1] 這篇論文中的算法，這是第一次提出 GNN 的論文，因此通常被認為是原始 GNN。 在節(jié)點分類問題設(shè)置中，每個節(jié)點 v 的特征 x_v 與一個 ground-truth 標簽 t_v 相關(guān)聯(lián)。給定一個部分標記的 graph G，目標是利用這些標記的節(jié)點來預(yù)測未標記的節(jié)點的標簽。它學(xué)習(xí)用包含鄰域信息的 d 維向量 h_v 表示每個節(jié)點。即： 其中 x_co[v] 表示與 v 相連的邊的特征，h_ne[v] 表示 v 相鄰節(jié)點的嵌入，x_ne[v] 表示v 相鄰節(jié)點的特征。函數(shù) f 是將這些輸入映射到 d 維空間上的過渡函數(shù)。由于我們要尋找 h_v 的唯一解，我們可以應(yīng)用 Banach 不動點定理，將上面的方程重寫為一個迭代更新過程。 H 和 X 分別表示所有 h 和 x 的串聯(lián)。 通過將狀態(tài) h_v 和特性 x_v 傳遞給輸出函數(shù) g，從而計算 GNN 的輸出。 這里的 f 和 g 都可以解釋為前饋全連接神經(jīng)網(wǎng)絡(luò)。L1 loss 可以直接表述為：  可以通過梯度下降進行優(yōu)化。 然而，原始 GNN 存在三個主要局限性：
為了解決上述問題，研究人員已經(jīng)提出了幾個 GNN 的變體。不過，它們不是本文的重點。 DeepWalk [2] 是第一個提出以無監(jiān)督的方式學(xué)習(xí)節(jié)點嵌入的算法。 它在訓(xùn)練過程中非常類似于詞匯嵌入。其動機是 graph 中節(jié)點和語料庫中單詞的分布都遵循冪律，如下圖所示：  該算法包含兩個步驟：
在 random walks 的每個時間步驟中，下一個節(jié)點從上一個節(jié)點的鄰節(jié)點均勻采樣。然后將每個序列截斷為長度為 2|w| + 1 的子序列，其中 w 表示 skip-gram 中的窗口大小。 本文采用 hierarchical softmax 來解決由于節(jié)點數(shù)量龐大而導(dǎo)致的 softmax 計算成本高昂的問題。為了計算每個單獨輸出元素的 softmax 值 , 我們必須計算元素 k 的所有 e ^ xk。  Softmax 的定義 因此，原始 softmax 的計算時間為 O(|V|)，其中 V 表示圖中頂點的集合。 分層 softmax 利用二叉樹來處理這個問題。在這個二叉樹中，所有的葉子 (下圖中的 v1, v2，…v8) 都表示 graph 中的頂點。在每個內(nèi)部節(jié)點中，都有一個二元分類器來決定選擇哪條路徑。要計算給定頂點 v_k 的概率，只需計算從根節(jié)點到葉節(jié)點 v_k 路徑上每一個子路徑的概率。由于每個節(jié)點的子節(jié)點的概率之和為 1，所以所有頂點的概率之和為 1的特性在分層 softmax 中仍然保持不變。由于二叉樹的最長路徑是 O(log(n))，其中 n表示葉節(jié)點的數(shù)量，因此一個元素的計算時間現(xiàn)在減少到 O(log|V|)。  Hierarchical Softmax 在訓(xùn)練完 DeepWalk GNN 之后，模型已經(jīng)學(xué)習(xí)了每個節(jié)點的良好表示，如下圖所示。不同的顏色表示輸入圖中的不同標簽。我們可以看到，在輸出圖 (2 維嵌入) 中，具有相同標簽的節(jié)點被聚集在一起，而具有不同標簽的大多數(shù)節(jié)點都被正確地分開了。  然而，DeepWalk 的主要問題是缺乏泛化能力。每當一個新節(jié)點出現(xiàn)時，它必須重新訓(xùn)練模型以表示這個節(jié)點。因此，這種 GNN 不適用于圖中節(jié)點不斷變化的動態(tài)圖。 GraphSage 提供了解決上述問題的辦法，以一種歸納的方式學(xué)習(xí)每個節(jié)點的嵌入。 具體地說，GraphSage 每個節(jié)點由其鄰域的聚合 (aggregation) 表示。因此，即使圖中出現(xiàn)了在訓(xùn)練過程中沒有看到的新節(jié)點，它仍然可以用它的鄰近節(jié)點來恰當?shù)乇硎尽?/p> 下面是 GraphSage算法：  外層循環(huán)表示更新迭代的數(shù)量，而 h ^ k_v 表示更新迭代 k 時節(jié)點 v 的潛在向量。在每次更新迭代時，h ^ k_v 的更新基于一個聚合函數(shù)、前一次迭代中 v 和 v 的鄰域的潛在向量，以及權(quán)重矩陣 W ^ k。 論文中提出了三種聚合函數(shù)： 1. Mean aggregator： mean aggregator 取一個節(jié)點及其所有鄰域的潛在向量的平均值。 與原始方程相比，它刪除了上面?zhèn)未a中第 5 行中的連接運算。這種運算可以看作是一種 “skip-connection”，在論文后面的部分中，證明了這在很大程度上可以提高模型的性能。 2. LSTM aggregator： 由于圖中的節(jié)點沒有任何順序，因此它們通過對這些節(jié)點進行排列來隨機分配順序。 3. Pooling aggregator： 這個運算符在相鄰集上執(zhí)行一個 element-wise 的 pooling 函數(shù)。下面是一個 max-pooling 的示例： 論文使用 max-pooling 作為默認的聚合函數(shù)。 損失函數(shù)定義如下： 其中 u 和 v 在固定長度的 random walk 中共存，而 v_n 是不與 u 共存的負樣本。這種損失函數(shù)鼓勵距離較近的節(jié)點具有相似的嵌入，而距離較遠的節(jié)點則在投影空間中被分離。通過這種方法，節(jié)點將獲得越來越多的關(guān)于其鄰域的信息。 GraphSage 通過聚合其附近的節(jié)點，可以為看不見的節(jié)點生成可表示的嵌入。它允許將節(jié)點嵌入應(yīng)用到涉及動態(tài)圖的域，其中圖的結(jié)構(gòu)是不斷變化的。例如，Pinterest 采用了GraphSage 的擴展版本 PinSage 作為其內(nèi)容發(fā)現(xiàn)系統(tǒng)的核心。 本文中，我們學(xué)習(xí)了圖神經(jīng)網(wǎng)絡(luò)、DeepWalk 和 GraphSage 的基礎(chǔ)知識。GNN 在復(fù)雜圖結(jié)構(gòu)建模方面的強大功能確實令人驚嘆。鑒于其有效性，我相信在不久的將來，GNN將在 AI 的發(fā)展中發(fā)揮重要作用。 [1] Scarselli, Franco, et al. 'The graph neural network model.” http://citeseerx.ist./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.” 點擊“閱讀原文”查看原文 【加入社群】 新智元AI技術(shù)+產(chǎn)業(yè)社群招募中，歡迎對AI技術(shù)+產(chǎn)業(yè)落地感興趣的同學(xué)，_2 入群;通過審核后我們將邀請進群，加入社群后務(wù)必修改群備注（姓名 - 公司 - 職位;專業(yè)群審核較嚴，敬請諒解）。 |
|
|
