作者：Steeve Huang
編譯：ronghuaiyang

導讀

給大家介紹目前非常熱門的圖神經(jīng)網(wǎng)絡，包括基礎和兩個常用算法，DeepWalk和GraphSage。

近年來，圖神經(jīng)網(wǎng)絡(GNN)在社交網(wǎng)絡、知識圖譜、推薦系統(tǒng)甚至生命科學等各個領域得到了越來越廣泛的應用。GNN具有對圖中節(jié)點間依賴關系建模的強大功能，使得圖分析相關研究領域取得了突破。本文會介紹圖神經(jīng)網(wǎng)絡的基本原理，以及兩種更高級的算法，DeepWalk和GraphSage。

圖

在討論GNN之前，讓我們先了解什么是Graph。在計算機科學中，圖是由頂點和邊兩部分組成的數(shù)據(jù)結構。一個圖G可以由它所包含的頂點V和邊E的集合很好地描述。

根據(jù)頂點之間是否存在方向依賴關系，邊可以是有向的，也可以是無向的。

這些頂點通常稱為節(jié)點。在本文中，這兩個術語是可以互換的。

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

圖神經(jīng)網(wǎng)絡是一種直接作用于圖結構上的神經(jīng)網(wǎng)絡。GNN的一個典型應用是節(jié)點分類。本質上，圖中的每個節(jié)點都與一個標簽相關聯(lián)，我們希望在沒有ground-truth的情況下預測節(jié)點的標簽。本節(jié)將說明本文中描述的算法。第一個提出的GNN常常被稱為原始GNN。

在節(jié)點分類問題設置中，每個節(jié)點v的特征是x_v，并與一個ground-truth標簽t_v關聯(lián)。給定一個部分標記的圖G，目標是利用這些標記的節(jié)點來預測未標記的標簽。它學習用一個d維向量(狀態(tài))h_v表示每個節(jié)點，其中包含其鄰域的信息。具體地說,

其中x_co[v]表示與v相連的邊的特征，h_ne[v]表示與v相鄰節(jié)點的嵌入，x_ne[v]表示與v相鄰節(jié)點的特征。函數(shù)f是將這些輸入投射到d維空間的轉換函數(shù)。因為我們正在為h_v尋找一個惟一的解，所以我們可以應用Banach定點定理并將上面的等式重寫為迭代更新過程。這種操作通常稱為消息傳遞或鄰居聚合。

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

通過將狀態(tài)h_v和特征x_v傳遞給輸出函數(shù)g來計算GNN的輸出。

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

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

然而，有文章指出，GNN的這一原始方法存在三個主要限制：

1. 如果放松“不動點”的假設，就有可能利用多層感知器來學習更穩(wěn)定的表示，并消除迭代更新過程。這是因為，在原方案中，不同的迭代使用相同的轉換函數(shù)f的參數(shù)，而MLP不同層中不同的參數(shù)允許分層特征提取。
2. 它不能處理邊緣信息(例如，知識圖中不同的邊緣可能表示節(jié)點之間不同的關系)
3. 不動點會阻礙節(jié)點分布的多樣化，因此可能不適合學習表示節(jié)點。

已經(jīng)提出了幾個GNN的變體來解決上述問題。然而，它們沒有被涵蓋，因為它們不是本文的重點。

DeepWalk

DeepWalk是第一個提出以無監(jiān)督方式學習節(jié)點嵌入的算法。就訓練過程而言，它非常類似于單詞嵌入。其動機是圖中節(jié)點和語料庫中單詞的分布遵循冪律，如下圖所示:

算法包括兩個步驟:

1. 在圖中的節(jié)點上執(zhí)行隨機漫步以生成節(jié)點序列
2. 根據(jù)步驟1生成的節(jié)點序列，運行skip-gram，學習每個節(jié)點的嵌入

在隨機游走的每個時間步長上，下一個節(jié)點均勻地從前一個節(jié)點的鄰居中采樣。然后將每個序列截斷為長度2|w| + 1的子序列，其中w表示skip-gram的窗口大小。

本文采用層次softmax 算法，解決了節(jié)點數(shù)量大、計算量大的softmax問題。要計算每個單獨輸出元素的softmax值，我們必須計算所有元素k的所有e^xk。

因此，原始softmax的計算時間為O(|V|)，其中V表示圖中頂點的集合。

層次softmax利用二叉樹來處理該問題。在這個二叉樹中，所有的葉子(上圖中的v1 v2…v8)都是圖中的頂點。在每個內部節(jié)點中，都有一個二進制分類器來決定選擇哪條路徑。要計算給定頂點v_k的概率，只需計算從根節(jié)點到左節(jié)點的路徑上的每個子路徑的概率v_k。由于每個節(jié)點的子節(jié)點的概率之和為1，所以所有頂點的概率之和等于1的性質在層次softmax中仍然成立?，F(xiàn)在一個元素的計算時間減少到O(log|V|)，因為二叉樹的最長路徑以O(log(n))為界，其中n是葉子的數(shù)量。

經(jīng)過DeepWalk GNN的訓練，模型學習到每個節(jié)點的良好表示，如下圖所示。不同的顏色表示輸入圖中不同的標簽。我們可以看到，在輸出圖中(2維嵌入)，具有相同標簽的節(jié)點聚集在一起，而具有不同標簽的大多數(shù)節(jié)點被正確地分離。

然而，DeepWalk的主要問題是它缺乏泛化的能力。每當一個新節(jié)點出現(xiàn)時，它都必須對模型進行重新訓練，才可以表示這個節(jié)點。因此，這種GNN不適用于圖中節(jié)點不斷變化的動態(tài)圖。

GraphSage

GraphSage提供了一個解決上述問題的解決方案，以歸納的方式學習每個節(jié)點的嵌入。具體地說，每個節(jié)點由其鄰域的聚合表示。因此，即使在圖中出現(xiàn)了訓練過程中沒有出現(xiàn)過的新的節(jié)點，也可以用相鄰的節(jié)點來表示。下面是GraphSage的算法。

外循環(huán)表示更新迭代次數(shù)，h^k_v表示更新迭代時節(jié)點v的隱向量k。在每次更新迭代中，根據(jù)一個聚集函數(shù)、前一次迭代中v和v鄰域的隱向量以及權矩陣W^k對h^k_v進行更新。本文提出了三個聚合函數(shù):

1. Mean aggregator:

mean aggregator取一個節(jié)點及其所有鄰域的隱向量的平均值。

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

2. LSTM aggregator:

由于圖中的節(jié)點沒有任何順序，它們通過遍歷這些節(jié)點來隨機分配順序。

3. Pooling aggregator:

這個操作符在相鄰的集合上執(zhí)行一個元素池化函數(shù)。下面是最大池化的例子：

可以用均值池化或任何其他對稱池化函數(shù)替換。池化聚合器性能最好，而均值池化聚合器和最大池化聚合器性能相近。本文使用max-pooling作為默認的聚合函數(shù)。

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

其中u和v共出現(xiàn)在固定長度的隨機游動中，v_n是與u不共出現(xiàn)的負樣本。這種損失函數(shù)鼓勵距離較近的節(jié)點進行類似的嵌入，而距離較遠的節(jié)點則在投影空間中進行分離。通過這種方法，節(jié)點將獲得越來越多的關于其鄰域的信息。

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

總結

你學習了圖形神經(jīng)網(wǎng)絡、DeepWalk和GraphSage的基礎知識。GNN在復雜圖形結構建模方面的能力確實令人吃驚。鑒于其有效性，我相信在不久的將來，GNN將在人工智能的發(fā)展中發(fā)揮重要的作用。

英文原文：https:///a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3