圖神經網絡(GNN)在各個領域越來越受歡迎，本文介紹了圖神經網絡的基本知識，以及兩種更高級的算法：DeepWalk和GraphSage。

最近，圖神經網絡(GNN)在各個領域越來越受到歡迎，包括社交網絡、知識圖譜、推薦系統，甚至生命科學。

GNN在對圖形中節點間的依賴關系進行建模方面能力強大，使得圖分析相關的研究領域取得了突破性進展。本文旨在介紹圖神經網絡的基本知識，以及兩種更高級的算法：DeepWalk和GraphSage。

圖(Graph)

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

邊可以是有向的或無向的，這取決于頂點之間是否存在方向依賴關系。

一個有向的圖(wiki)

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

圖神經網絡

圖神經網絡是一種直接在圖結構上運行的神經網絡。GNN的一個典型應用是節點分類。本質上，圖中的每個節點都與一個標簽相關聯，我們的目的是預測沒有ground-truth的節點的標簽。

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

在節點分類問題設置中，每個節點v的特征x_v與一個ground-truth標簽t_v相關聯。給定一個部分標記的graph G，目標是利用這些標記的節點來預測未標記的節點的標簽。它學習用包含鄰域信息的d維向量h_v表示每個節點。即：

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

H和X分別表示所有h和x的串聯。

通過將狀態h_v和特性x_v傳遞給輸出函數g，從而計算GNN的輸出。

這里的f和g都可以解釋為前饋全連接神經網絡。L1 loss可以直接表述為：

可以通過梯度下降進行優化。

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

如果放寬“不動點” (fixed point)的假設，那么可以利用多層感知器學習更穩定的表示，并刪除迭代更新過程。這是因為，在原始論文中，不同的迭代使用轉換函數f的相同參數，而MLP的不同層中的不同參數允許分層特征提取。

它不能處理邊緣信息(例如，知識圖中的不同邊緣可能表示節點之間的不同關系)

不動點會阻礙節點分布的多樣性，不適合學習表示節點。

為了解決上述問題，研究人員已經提出了幾個GNN的變體。不過，它們不是本文的重點。

DeepWalk：第一個無監督學習節點嵌入的算法

DeepWalk [2]是第一個提出以無監督的方式學習節點嵌入的算法。

它在訓練過程中非常類似于詞匯嵌入。其動機是graph中節點和語料庫中單詞的分布都遵循冪律，如下圖所示：

該算法包含兩個步驟：

在graph中的節點上執行random walks，以生成節點序列

運行skip-gram，根據步驟1中生成的節點序列，學習每個節點的嵌入

在random walks的每個時間步驟中，下一個節點從上一個節點的鄰節點均勻采樣。然后將每個序列截斷為長度為2|w| + 1的子序列，其中w表示skip-gram中的窗口大小。

本文采用hierarchical softmax來解決由于節點數量龐大而導致的softmax計算成本高昂的問題。為了計算每個單獨輸出元素的softmax值,我們必須計算元素k的所有e ^ xk。

Softmax的定義

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

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

Hierarchical Softmax

在訓練完DeepWalk GNN之后，模型已經學習了每個節點的良好表示，如下圖所示。不同的顏色表示輸入圖中的不同標簽。我們可以看到，在輸出圖(2維嵌入)中，具有相同標簽的節點被聚集在一起，而具有不同標簽的大多數節點都被正確地分開了。

然而，DeepWalk的主要問題是缺乏泛化能力。每當一個新節點出現時，它必須重新訓練模型以表示這個節點。因此，這種GNN不適用于圖中節點不斷變化的動態圖。

GraphSage：學習每個節點的嵌入

GraphSage提供了解決上述問題的辦法，以一種歸納的方式學習每個節點的嵌入。

具體地說，GraphSage每個節點由其鄰域的聚合(aggregation)表示。因此，即使圖中出現了在訓練過程中沒有看到的新節點，它仍然可以用它的鄰近節點來恰當地表示。

下面是GraphSage算法：

外層循環表示更新迭代的數量，而h ^ k_v表示更新迭代k時節點v的潛在向量。在每次更新迭代時，h ^ k_v的更新基于一個聚合函數、前一次迭代中v和v的鄰域的潛在向量，以及權重矩陣W ^ k。

論文中提出了三種聚合函數：

1. Mean aggregator：

mean aggregator取一個節點及其所有鄰域的潛在向量的平均值。

與原始方程相比，它刪除了上面偽代碼中第5行中的連接運算。這種運算可以看作是一種“skip-connection”，在論文后面的部分中，證明了這在很大程度上可以提高模型的性能。

2. LSTM aggregator：

由于圖中的節點沒有任何順序，因此它們通過對這些節點進行排列來隨機分配順序。

3. Pooling aggregator：

這個運算符在相鄰集上執行一個element-wise的pooling函數。下面是一個max-pooling的示例：

論文使用max-pooling作為默認的聚合函數。

損失函數定義如下：

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

GraphSage通過聚合其附近的節點，可以為看不見的節點生成可表示的嵌入。它允許將節點嵌入應用到涉及動態圖的域，其中圖的結構是不斷變化的。例如，Pinterest采用了GraphSage的擴展版本PinSage作為其內容發現系統的核心。

總結

本文中，我們學習了圖神經網絡、DeepWalk和GraphSage的基礎知識。GNN在復雜圖結構建模方面的強大功能確實令人驚嘆。鑒于其有效性，我相信在不久的將來，GNN將在AI的發展中發揮重要作用。

[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