作者：Steeve Huang 導(dǎo)讀給大家介紹目前非常熱門的圖神經(jīng)網(wǎng)絡(luò)，包括基礎(chǔ)和兩個常用算法，DeepWalk和GraphSage。 近年來，圖神經(jīng)網(wǎng)絡(luò)(GNN)在社交網(wǎng)絡(luò)、知識圖譜、推薦系統(tǒng)甚至生命科學(xué)等各個領(lǐng)域得到了越來越廣泛的應(yīng)用。GNN具有對圖中節(jié)點(diǎn)間依賴關(guān)系建模的強(qiáng)大功能，使得圖分析相關(guān)研究領(lǐng)域取得了突破。本文會介紹圖神經(jīng)網(wǎng)絡(luò)的基本原理，以及兩種更高級的算法，DeepWalk和GraphSage。 圖 在討論GNN之前，讓我們先了解什么是Graph。在計(jì)算機(jī)科學(xué)中，圖是由頂點(diǎn)和邊兩部分組成的數(shù)據(jù)結(jié)構(gòu)。一個圖G可以由它所包含的頂點(diǎn)V和邊E的集合很好地描述。 根據(jù)頂點(diǎn)之間是否存在方向依賴關(guān)系，邊可以是有向的，也可以是無向的。 有向圖 這些頂點(diǎn)通常稱為節(jié)點(diǎn)。在本文中，這兩個術(shù)語是可以互換的。 圖神經(jīng)網(wǎng)絡(luò) 圖神經(jīng)網(wǎng)絡(luò)是一種直接作用于圖結(jié)構(gòu)上的神經(jīng)網(wǎng)絡(luò)。GNN的一個典型應(yīng)用是節(jié)點(diǎn)分類。本質(zhì)上，圖中的每個節(jié)點(diǎn)都與一個標(biāo)簽相關(guān)聯(lián)，我們希望在沒有g(shù)round-truth的情況下預(yù)測節(jié)點(diǎn)的標(biāo)簽。本節(jié)將說明本文中描述的算法。第一個提出的GNN常常被稱為原始GNN。 在節(jié)點(diǎn)分類問題設(shè)置中，每個節(jié)點(diǎn)v的特征是x_v，并與一個ground-truth標(biāo)簽t_v關(guān)聯(lián)。給定一個部分標(biāo)記的圖G，目標(biāo)是利用這些標(biāo)記的節(jié)點(diǎn)來預(yù)測未標(biāo)記的標(biāo)簽。它學(xué)習(xí)用一個d維向量(狀態(tài))h_v表示每個節(jié)點(diǎn)，其中包含其鄰域的信息。具體地說, 其中x_co[v]表示與v相連的邊的特征，h_ne[v]表示與v相鄰節(jié)點(diǎn)的嵌入，x_ne[v]表示與v相鄰節(jié)點(diǎn)的特征。函數(shù)f是將這些輸入投射到d維空間的轉(zhuǎn)換函數(shù)。因?yàn)槲覀冋跒閔_v尋找一個惟一的解，所以我們可以應(yīng)用Banach定點(diǎn)定理并將上面的等式重寫為迭代更新過程。這種操作通常稱為消息傳遞或鄰居聚合。 H和X分別表示所有H和X的級聯(lián)。 H和X分別表示所有H和X的級聯(lián)。 通過將狀態(tài)h_v和特征x_v傳遞給輸出函數(shù)g來計(jì)算GNN的輸出。 這里的f和g都可以解釋為前饋全連接神經(jīng)網(wǎng)絡(luò)。L1損失可以直接表述為: 可以通過梯度下降來優(yōu)化。 然而，有文章指出，GNN的這一原始方法存在三個主要限制：
已經(jīng)提出了幾個GNN的變體來解決上述問題。然而，它們沒有被涵蓋，因?yàn)樗鼈儾皇潜疚牡闹攸c(diǎn)。 DeepWalk DeepWalk是第一個提出以無監(jiān)督方式學(xué)習(xí)節(jié)點(diǎn)嵌入的算法。就訓(xùn)練過程而言，它非常類似于單詞嵌入。其動機(jī)是圖中節(jié)點(diǎn)和語料庫中單詞的分布遵循冪律，如下圖所示: 算法包括兩個步驟:
在隨機(jī)游走的每個時間步長上，下一個節(jié)點(diǎn)均勻地從前一個節(jié)點(diǎn)的鄰居中采樣。然后將每個序列截?cái)酁殚L度2|w| + 1的子序列，其中w表示skip-gram的窗口大小。 本文采用層次softmax 算法，解決了節(jié)點(diǎn)數(shù)量大、計(jì)算量大的softmax問題。要計(jì)算每個單獨(dú)輸出元素的softmax值，我們必須計(jì)算所有元素k的所有e^xk。 因此，原始softmax的計(jì)算時間為O(|V|)，其中V表示圖中頂點(diǎn)的集合。 層次softmax利用二叉樹來處理該問題。在這個二叉樹中，所有的葉子(上圖中的v1 v2…v8)都是圖中的頂點(diǎn)。在每個內(nèi)部節(jié)點(diǎn)中，都有一個二進(jìn)制分類器來決定選擇哪條路徑。要計(jì)算給定頂點(diǎn)v_k的概率，只需計(jì)算從根節(jié)點(diǎn)到左節(jié)點(diǎn)的路徑上的每個子路徑的概率v_k。由于每個節(jié)點(diǎn)的子節(jié)點(diǎn)的概率之和為1，所以所有頂點(diǎn)的概率之和等于1的性質(zhì)在層次softmax中仍然成立。現(xiàn)在一個元素的計(jì)算時間減少到O(log|V|)，因?yàn)槎鏄涞淖铋L路徑以O(log(n))為界，其中n是葉子的數(shù)量。 經(jīng)過DeepWalk GNN的訓(xùn)練，模型學(xué)習(xí)到每個節(jié)點(diǎn)的良好表示，如下圖所示。不同的顏色表示輸入圖中不同的標(biāo)簽。我們可以看到，在輸出圖中(2維嵌入)，具有相同標(biāo)簽的節(jié)點(diǎn)聚集在一起，而具有不同標(biāo)簽的大多數(shù)節(jié)點(diǎn)被正確地分離。
然而，DeepWalk的主要問題是它缺乏泛化的能力。每當(dāng)一個新節(jié)點(diǎn)出現(xiàn)時，它都必須對模型進(jìn)行重新訓(xùn)練，才可以表示這個節(jié)點(diǎn)。因此，這種GNN不適用于圖中節(jié)點(diǎn)不斷變化的動態(tài)圖。 GraphSage GraphSage提供了一個解決上述問題的解決方案，以歸納的方式學(xué)習(xí)每個節(jié)點(diǎn)的嵌入。具體地說，每個節(jié)點(diǎn)由其鄰域的聚合表示。因此，即使在圖中出現(xiàn)了訓(xùn)練過程中沒有出現(xiàn)過的新的節(jié)點(diǎn)，也可以用相鄰的節(jié)點(diǎn)來表示。下面是GraphSage的算法。
外循環(huán)表示更新迭代次數(shù)，h^k_v表示更新迭代時節(jié)點(diǎn)v的隱向量k。在每次更新迭代中，根據(jù)一個聚集函數(shù)、前一次迭代中v和v鄰域的隱向量以及權(quán)矩陣W^k對h^k_v進(jìn)行更新。本文提出了三個聚合函數(shù): 1. Mean aggregator: mean aggregator取一個節(jié)點(diǎn)及其所有鄰域的隱向量的平均值。
與原始方程相比，它刪除了上面?zhèn)未a第5行中的連接操作。這種操作可以看作是一種“跳躍連接”，本文稍后的部分證明了這種連接在很大程度上提高了模型的性能。 2. LSTM aggregator: 由于圖中的節(jié)點(diǎn)沒有任何順序，它們通過遍歷這些節(jié)點(diǎn)來隨機(jī)分配順序。 3. Pooling aggregator: 這個操作符在相鄰的集合上執(zhí)行一個元素池化函數(shù)。下面是最大池化的例子：
可以用均值池化或任何其他對稱池化函數(shù)替換。池化聚合器性能最好，而均值池化聚合器和最大池化聚合器性能相近。本文使用max-pooling作為默認(rèn)的聚合函數(shù)。 損失函數(shù)定義如下:
其中u和v共出現(xiàn)在固定長度的隨機(jī)游動中，v_n是與u不共出現(xiàn)的負(fù)樣本。這種損失函數(shù)鼓勵距離較近的節(jié)點(diǎn)進(jìn)行類似的嵌入，而距離較遠(yuǎn)的節(jié)點(diǎn)則在投影空間中進(jìn)行分離。通過這種方法，節(jié)點(diǎn)將獲得越來越多的關(guān)于其鄰域的信息。 GraphSage通過聚合其附近的節(jié)點(diǎn)，為不可見的節(jié)點(diǎn)生成可表示的嵌入。它允許將節(jié)點(diǎn)嵌入應(yīng)用于涉及動態(tài)圖的領(lǐng)域，其中圖的結(jié)構(gòu)是不斷變化的。例如，Pinterest采用GraphSage的擴(kuò)展版本PinSage作為內(nèi)容發(fā)現(xiàn)系統(tǒng)的核心。 總結(jié) 你學(xué)習(xí)了圖形神經(jīng)網(wǎng)絡(luò)、DeepWalk和GraphSage的基礎(chǔ)知識。GNN在復(fù)雜圖形結(jié)構(gòu)建模方面的能力確實(shí)令人吃驚。鑒于其有效性，我相信在不久的將來，GNN將在人工智能的發(fā)展中發(fā)揮重要的作用。 英文原文：https:///a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3 |
|
|
