本文為 AI 研習社編譯的技術部落格，原标題 ：
A Gentle Introduction to Graph Neural Networks (Basics, DeepWalk, and GraphSage)
作者 | 黃功詳 Steeve HuangFollow
翻譯 | GuardSkill、絲特芬妮•理
校對 | 醬番梨 稽核 | 約翰遜·李加薪 整理 | 立魚王
原文連結：
https://towardsdatascience.com/a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3
圖檔來源： Pexels
近來，圖神經網絡(GNN)在各個領域廣受關注，比如社交網絡，知識圖譜，推薦系統以及生命科學。GNN在對圖節點之間依賴關系進行模組化的強大功能使得與圖分析相關的研究領域取得了突破。 本文旨在介紹圖形神經網絡的基礎知識兩種較進階的算法，DeepWalk和GraphSage。
圖
在我們學習GAN之前，大家先了解一下什麼圖。在計算機科學中，圖是一種資料結構，由頂點和邊組成。圖G可以通過頂點集合V和它包含的邊E來進行描述。
根據頂點之間是否存在方向性，邊可以是有向或無向的。
頂點通常稱為節點。在本文中，這兩個術語是可以互換的。
圖神經網絡
圖神經網絡是一種直接在圖結構上運作的神經網絡。GNN的一個典型應用是節點分類。本質上，圖中的每個節點都與一個标簽相關聯，我們希望預測未标記節點的标簽。本節将介紹論文中描述的算法，GNN的第一個提法，是以通常被視為原始GNN。
在節點分類問題中，每個節點v都可以用其特征x_v表示并且與已标記的标簽t_v相關聯。給定部分标記的圖G，目标是利用這些标記的節點來預測未标記的節點标簽。 它通過學習得到每個節點的d維向量（狀态）表示h_v，同時包含其鄰居的資訊。
https://arxiv.org/pdf/1812.08434
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損失可以直接表述如下：
可以通過梯度下降優化。
但是，本文指出的原始GNN有三個主要局限：
如果放寬了“固定點”的假設，則可以利用多層感覺器來學習更穩定的表示，并删除疊代更新過程。 這是因為，在原始方法中，不同的疊代使用轉移函數f的相同參數，而不同MLP層中的不同參數允許分層特征提取。
它不能處理邊緣資訊（例如知識圖譜中的不同邊可能表示節點之間的不同關系）
固定點會限制節點分布的多樣化，是以可能不适合學習節點表示。
已經提出了幾種GNN變體來解決上述問題。 但是，他們不是這篇文章的重點。
DeepWalk
DeepWalk是第一個以無監督學習的節點嵌入算法。 它在訓練過程中類似于詞嵌入。 它的初衷是圖中的兩個節點分布和語料庫中的單詞分布都遵循幂律，如下圖所示：
http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
算法包括兩個步驟：
在圖中的節點上執行随機遊走生成節點序列
運作skip-gram，根據步驟1中生成的節點序列學習每個節點的嵌入
在随機遊走過程中，下一個節點是從前一節點的鄰居統一采樣。 然後将每個序列截短為長度為2 | w |+1的子序列，其中w表示skip-gram中的視窗大小。如果您不熟悉skip-gram，我之前的部落格文章已經向您介紹它的工作原理。
在論文中，分層softmax用于解決由于節點數量龐大而導緻的softmax計算成本過高的問題。為了計算每個單獨輸出元素的softmax值，我們必須為所有元素k計算ek。
softmax的定義
是以，原始softmax的計算時間是 O(|V|) ，其中其中V表示圖中的頂點集。
多層的softmax利用二叉樹來解決softmax計算成本問題。 在二叉樹中，所有葉子節點（上面所說的圖中的v1，v2，... v8）都是圖中的頂點。 在每個内部節點中（除了葉子節點以外的節點，也就是分枝結點），都通過一個二進制分類器來決定路徑的選取。 為了計算某個頂點v_k的機率，可以簡單地計算沿着從根節點到葉子節點v_k的路徑中的每個子路徑的機率。 由于每個節點的孩子節點的機率和為1，是以在多層softmax中，所有頂點的機率之和等于1的特性仍然能夠保持。如果n是葉子的數量，二叉樹的最長路徑由O（log（n））限定，是以，元素的計算時間複雜度将減少到O（log | V |）。
多層softmax
(http://www.perozzi.net/publications/14_kdd_deepwalk.pdf)
在訓練DeepWalk GNN之後，模型已經學習到了了每個節點的良好表示，如下圖所示。 不同的顔色在輸入圖中（圖a）表示不同标簽。 我們可以看到，在輸出圖（每個頂點被嵌入到2維平面）中，具有相同标簽的節點聚集在一起，而具有不同标簽的大多數節點被正确分開。
http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
然而，DeepWalk的主要問題是它缺乏泛化能力。 每當有新節點加入到圖中時，它必須重新訓練模型以正确表示該節點（ 直推式學習 ）。 是以，這種GNN不适用于圖中節點不斷變化的動态圖。
GraphSage
GraphSage提供了解決上述問題的解決方案，它以歸納方式學習每個節點的嵌入。 具體來講，它将每個節點用其鄰域的聚合重新表示。 是以，即使在訓練時間期間未出現在圖中新節點，也仍然可以由其相鄰節點正确地表示。 下圖展示了GraphSage的算法過程。
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
外層for循環表示更新疊代次數，而 h^k_v 表示節點v 在疊代第 k 次時的本征向量。 在每次疊代時，将通過聚合函數，前一次疊代中 v 和 v 領域的本征向量以及權重矩陣W^k 來更新h^k_v 。這篇論文提出了三種聚合函數：
1.均值聚合器：
均值聚合器取一個節點及其鄰域的本征向量的平均值。
與原始方程相比，它删除了上述僞代碼中第5行的連接配接操作。 這種操作可以被視為"skip-connection" ("跳連接配接")，這篇論文後面将證明其可以在很大程度上提高模型的性能。
2. LSTM聚合器：
由于圖中的節點沒有任何順序，是以他們通過互換這些節點來随機配置設定順序。
3.池聚合器：
此運算符在相鄰頂點集上執行逐元素池化函數。下面顯示了最大池的例子：
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
可以用平均池或任何其他對稱池函數替換這種最大池函數。盡管均值池和最大池聚合器性能相似，但是池聚合器（也就是說采用最大池函數）被實驗證明有最佳的性能。 這篇論文使用max-pooling作為預設聚合函數
損失函數定義如下：
https://www-cs-faculty.stanford.edu/people/jure/pubs/graphsage-nips17.pdf
其中u 和v 共同出現在一定長度的随機遊走中，而 v_n 是不與u共同出現的負樣本。這種損失函數鼓動節點在投影空間中更靠近嵌入距離更近的節點，而與那些相距很遠的節點分離。通過這種方法，節點将獲得越來越多其鄰域的資訊。
GraphSage通過聚合其附近的節點，可以為看不見的節點生成可表示的嵌入位置。它讓節點嵌入的方式可以被應用于涉及動态圖的研究領域，這類動态圖的圖的結構是可以不斷變化的。例如，Pinterest采用了GraphSage的擴充版本PinSage作為他們的内容探索系統的核心。
結束語
您已經學習了圖形神經網絡，DeepWalk和GraphSage的基礎知識。 GNN在複雜圖形結構模組化中的強大功能确實令人驚訝。鑒于其高效性，我相信GNN将在人工智能的發展中發揮重要作用。如果您覺得我的文章還不錯，請不要忘記在Medium和Twitter上關注我，我經常分享AI，ML和DL的進階發展動态。
想要繼續檢視該篇文章相關連結和參考文獻？
點選【神經網絡圖的簡介（基本概念，Deepwalk以及 GraphSage算法）】或長按下方位址：
https://ai.yanxishe.com/page/TextTranslation/1485
AI研習社今日推薦：雷鋒網雷鋒網雷鋒網(公衆号：雷鋒網)
卡耐基梅隆大學 2019 春季《神經網絡自然語言處理》是CMU語言技術學院和計算機學院聯合開課，主要内容是教學生如何用神經網絡做自然語言處理。神經網絡對于語言模組化任務而言，可以稱得上是提供了一種強大的新工具，與此同時，神經網絡能夠改進諸多任務中的最新技術，将過去不容易解決的問題變得輕松簡單。
加入小組免費觀看視訊：https://ai.yanxishe.com/page/groupDetail/33