最近，深度學習領(lǐng)域關(guān)于圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks，GNN）的研究熱情日益高漲，圖神經(jīng)網(wǎng)絡(luò)已經(jīng)成為各大深度學習頂會的研究熱點，包括社交網(wǎng)絡(luò)，知識圖，推薦系統(tǒng)，甚至生命科學。GNN在對圖中節(jié)點之間的依賴關(guān)系建模方面的強大功能使得與圖分析相關(guān)的研究領(lǐng)域取得了突破。GNN處理非結(jié)構(gòu)化數(shù)據(jù)時的出色能力使其在網(wǎng)絡(luò)數(shù)據(jù)分析、推薦系統(tǒng)、物理建模、自然語言處理和圖上的組合優(yōu)化問題方面都取得了新的突破。

本文旨在介紹圖形神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)知識和兩種更高級的算法，DeepWalk和GraphSage。

一 圖

在我們學習GNN之前，讓我們先了解一下圖是什么。在計算機科學中，圖是由兩個組成部分組成的數(shù)據(jù)結(jié)構(gòu)，即頂點和邊緣。圖G可以通過頂點集V和它包含的邊E來進行描述。

圖表示學習的主要目標是：將結(jié)點映射為向量表示的時候盡可能多地保留圖的拓撲信息。圖表示學習主要分為基于圖結(jié)構(gòu)的表示學習和基于圖特征的表示學習

?

圖由頂點（Vertex）和連接頂點的邊（Edge）構(gòu)成，邊可以是有向的或無向的，這取決于頂點之間是否存在方向依賴關(guān)系。

頂點和邊之間的關(guān)系可以用鄰接矩陣（A）表示，兩個頂點間有邊標識為1，否則為0。

如上圖所示，圖G=（V，E）其中 V={v1，v2，v3，v4，v5}，E={（v1，v2),（v1，v3),(v2，v4),(v3，v4）,(v4，v5）}

?

二 GNN 圖神經(jīng)網(wǎng)絡(luò)

圖神經(jīng)網(wǎng)絡(luò)是一種直接作用于圖結(jié)構(gòu)上的神經(jīng)網(wǎng)絡(luò)。GNN比較經(jīng)典的是這篇《The Graph Neural Network Model》

GNN的一個典型應(yīng)用是節(jié)點分類。本質(zhì)上，圖中的每個節(jié)點都與一個標簽相關(guān)聯(lián)，我們希望在沒有g(shù)round-truth的情況下預(yù)測節(jié)點的標簽。本節(jié)將說明本文中描述的算法。第一個提出的GNN常常被稱為原始GNN。

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

其中x_co[v]表示與v相連的邊的特征，h_ne[v]表示與v相鄰節(jié)點的嵌入，x_ne[v]表示與v相鄰節(jié)點的特征。函數(shù)f是將這些輸入投射到d維空間的轉(zhuǎn)換函數(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損失可以直接表述為:

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

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

如果放松“不動點”的假設(shè)，就有可能利用多層感知器來學習更穩(wěn)定的表示，并消除迭代更新過程。這是因為，在原方案中，不同的迭代使用相同的轉(zhuǎn)換函數(shù)f的參數(shù)，而MLP不同層中不同的參數(shù)允許分層特征提取。

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

不動點會阻礙節(jié)點分布的多樣化，因此可能不適合學習表示節(jié)點。

三 DeepWalk

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

DeepWalk采用了Random walk的思想進行結(jié)點采樣。首先根據(jù)用戶的行為構(gòu)建出一個圖網(wǎng)絡(luò)；隨后通過Random walk隨機采樣的方式構(gòu)建出結(jié)點序列(例如：一開始在A結(jié)點，A->B，B又跳到了它的鄰居結(jié)點E，最后到F，得到"A->B->E->F"序列)；對于序列的問題就是NLP中的語言模型，因為我們的句子就是單詞構(gòu)成的序列。接下來我們的問題就變成Word2vec(詞用向量表示)的問題，采用Skip-gram的模型來得到最終的結(jié)點向量。可以說這種想法確實是十分精妙，將圖結(jié)構(gòu)轉(zhuǎn)化為序列問題確實是非常創(chuàng)新的出發(fā)點。在這里，結(jié)點走向其鄰居結(jié)點的概率是均等的。當然，在有向圖和無向圖中，游走的方式也不一樣。無向圖中的游走方式為相連即可走；而有向圖中則是只沿著“出邊”的方向走。

上圖出自阿里Embedding實踐paper：Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

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

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

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

層次softmax利用二叉樹來處理該問題。在這個二叉樹中，所有的葉子(上圖中的v1 v2…v8)都是圖中的頂點。在每個內(nèi)部節(jié)點中，都有一個二進制分類器來決定選擇哪條路徑。要計算給定頂點v_k的概率，只需計算從根節(jié)點到左節(jié)點的路徑上的每個子路徑的概率v_k。由于每個節(jié)點的子節(jié)點的概率之和為1，所以所有頂點的概率之和等于1的性質(zhì)在層次softmax中仍然成立。現(xiàn)在一個元素的計算時間減少到O(log|V|)，因為二叉樹的最長路徑以O(shè)(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é)點由其鄰域的聚合表示。因此，即使在訓練時間期間看不到的新節(jié)點出現(xiàn)在圖中，它仍然可以由其相鄰節(jié)點正確地表示。

具體實現(xiàn)中，訓練時它僅僅保留訓練樣本到訓練樣本的邊，然后包含Sample和Aggregate兩大步驟，Sample是指如何對鄰居的個數(shù)進行采樣，Aggregate是指拿到鄰居節(jié)點的embedding之后如何匯聚這些embedding以更新自己的embedding信息。下圖展示了GraphSAGE學習的一個過程，

第一步，對鄰居采樣

第二步，采樣后的鄰居embedding傳到節(jié)點上來，并使用一個聚合函數(shù)聚合這些鄰居信息以更新節(jié)點的embedding

第三步，根據(jù)更新后的embedding預(yù)測節(jié)點的標簽

網(wǎng)絡(luò)的層數(shù)可以理解為需要最大訪問的鄰居的跳數(shù)(hops)，比如在上圖中，紅色節(jié)點的更新拿到了它一、二跳鄰居的信息，那么網(wǎng)絡(luò)層數(shù)就是2。為了更新紅色節(jié)點，首先在第一層(k=1)，我們會將藍色節(jié)點的信息聚合到紅色解節(jié)點上，將綠色節(jié)點的信息聚合到藍色節(jié)點上。在第二層(k=2)紅色節(jié)點的embedding被再次更新，不過這次用到的是更新后的藍色節(jié)點embedding，這樣就保證了紅色節(jié)點更新后的embedding包括藍色和綠色節(jié)點的信息，也就是兩跳信息。

?

五 為何基于mean、max aggregate的GNN不夠強大

mean和max 無法區(qū)分哪些結(jié)構(gòu)

節(jié)點v和v'為中心節(jié)點，通過聚合鄰居特征生成embeddind，分析不同aggregate設(shè)置下是否能區(qū)分不同的結(jié)構(gòu)（如果能捕獲不同結(jié)構(gòu)，二者的embedding應(yīng)該不一樣）

設(shè)紅綠藍色節(jié)點特征值分別為r,g,b，不考慮combine

結(jié)論：由于mean和max-pooling 函數(shù) 不滿足單射性，無法區(qū)分某些結(jié)構(gòu)的圖，故性能會比sum差一點。

sum, mean, max 分別可以捕獲什么信息？

三種不同的aggregate

• sum：學習全部的標簽以及數(shù)量，可以學習精確的結(jié)構(gòu)信息
• mean：學習標簽的比例（比如兩個圖標簽比例相同，但是節(jié)點有倍數(shù)關(guān)系），偏向?qū)W習分布信息
• max：學習最大標簽，忽略多樣，偏向?qū)W習有代表性的元素信息

基于對 graph分類，證明了 sum 比 mean 、max 效果好，但是不能說明在node 分類上也是這樣的效果，另外可能優(yōu)先場景會更關(guān)注鄰域特征分布，或者代表性， 故需要都加入進來實驗。

?

參考：

https://towardsdatascience.com/a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3

https://zhuanlan.zhihu.com/p/136521625

How Powerful are Graph Neural Networks？ GIN 圖同構(gòu)網(wǎng)絡(luò) ICLR 2019 論文詳解

?

?

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的[图神经网络] 图神经网络GNN基础入门的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。