兩種GraphEmbedding詳解(DeepWalk及node2vec)

本文為轉(zhuǎn)載，原文鏈接：https://wmathor.com/index.php/archives/1531/

Introduction

既然你點進(jìn)了這篇博客，我就默認(rèn)你了解圖的最基本概念，包括但不限于有向圖、無向圖的定義，這里我不再多做贅述，下面我只闡述一些比較重要的部分

圖神經(jīng)網(wǎng)絡(luò)是一種直接對圖結(jié)構(gòu)進(jìn)行操作的神經(jīng)網(wǎng)絡(luò)。GNN 的一個典型應(yīng)用是節(jié)點分類。本質(zhì)上，圖中的每一個節(jié)點都與一個標(biāo)簽相關(guān)聯(lián)。如下圖所示，a節(jié)點的向量表示為[0.3, 0.02, 7, 4, ...]，將該向量送入下游繼續(xù)做分類即可得到a節(jié)點的類別。

a 節(jié)點的向量表示究竟是如何得到的，等會兒我會詳細(xì)闡述，不過在這我們可以簡單的思考一下，a 節(jié)點的向量表示一定應(yīng)該與其相鄰節(jié)點和**相鄰邊有關(guān)系，假設(shè)每個節(jié)點v的one-hot向量表示為X_v，則
h_v=f(X_v, X_{co[v]}, h_{ne[v]},X_{ne[v]})

其中X_{co[v]}表示與v相連邊的one-hot表示，h_{ne[v]}表示與v相鄰節(jié)點的embedding，X_{ne[v]}表示與v相鄰節(jié)點的one-hot表示。最終再將h_v向量和真實標(biāo)簽計算loss，不過也有的地方是將h_v向量和X_v經(jīng)過一輪融合之后再計算loss，例如
\begin{aligned} O_v&=g(h_v,X_v)\\ loss &= \sum_{i=1}^p (t_i-o_i) \end{aligned}

上述公式以及符號可能不好理解，這里其實可以類比 Word2Vec。在 Word2Vec 中，輸入的是每個詞對應(yīng)的 one-hot，即 X_v。輸出的是這個詞對應(yīng)的 embedding，即 h_v

作為一個典型的非歐式數(shù)據(jù)，對于圖數(shù)據(jù)的分析主要集中在節(jié)點分類，鏈接預(yù)測和聚類等。對于圖數(shù)據(jù)而言，圖嵌入（Graph / Network Embedding）和圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks, GNN）是兩個類似的研究領(lǐng)域。圖嵌入旨在將圖的節(jié)點表示成一個低維向量空間，同時保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點信息，以便在后續(xù)的圖分析任務(wù)中可以直接使用現(xiàn)有的機器學(xué)習(xí)算法。一些基于深度學(xué)習(xí)的圖嵌入同時也屬于圖神經(jīng)網(wǎng)絡(luò)，例如一些基于圖自編碼器和利用無監(jiān)督學(xué)習(xí)的圖卷積神經(jīng)網(wǎng)絡(luò)等。下圖描述了圖嵌入和圖神經(jīng)網(wǎng)絡(luò)之間的差異：

DeepWalk：第一個無監(jiān)督學(xué)習(xí)節(jié)點嵌入的算法

DeepWalk 用一句話概述就是：隨機生成圖節(jié)點序列，然后對該序列進(jìn)行 Word2Vec

具體來說，給定一個圖，我們隨機選擇一個節(jié)點作為起始，然后隨機 "步行" 到鄰居節(jié)點，直到節(jié)點序列的長度達(dá)到給定的最大值。例如下圖，分別選擇 d,e,f 作為起點進(jìn)行游走，得到三條節(jié)點序列


在這種情況下，我們可以將節(jié)點和節(jié)點序列分別看作是“單詞”和“句子”，然后利用skip-gram或者cbow算法訓(xùn)練得到每個節(jié)點的embedding。

DeepWalk算法主要包含兩個部分：一個隨機游走序列生成器和一個更新過程。
隨機游走序列生成器首先在圖G中隨機抽樣一個隨機游走W_{v_i}的根節(jié)點v_i，接著從根節(jié)點的鄰居中均勻地隨機抽樣一個節(jié)點直到達(dá)到設(shè)定的最大長度t。對于一個生成的以v_i為中心左右窗口為w的隨機游走序列v_{i-w},...,v_{i-1},v_i,v_{i+1},...,v_{i+m}，DeepWalk利用SkipGram算法通過最大化以v_i為中心，左右w為窗口的同其他節(jié)點共現(xiàn)概率來優(yōu)化模型：
\text{Pr} \left(\left\{v_{i-w}, \dotsc, v_{i+w}\right\} \setminus v_i \mid \Phi \left(v_i\right)\right) = \prod_{j=i-w, j \neq i}^{i+w} \text{Pr} \left(v_j \mid \Phi \left(v_i\right)\right)

DeepWalk和Word2Vec的類比如下表所示：

node2vec: bias random walk

一般的隨機游走公式
{P}\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{cc} \frac{1}{|N(v)|}, & \text { if }(v, x) \in E \\ 0, & \text { otherwise } \end{array}\right.
其中，|N(v)|表示v節(jié)點的鄰居節(jié)點數(shù)量，c_{i-1}表示當(dāng)前節(jié)點，c_i表示下一個選擇的節(jié)點

一般的隨機游走存在以下幾個問題：

  1. 如果是帶權(quán)圖，沒考慮邊權(quán)值的影響
  2. 太過于隨機，不能由模型自行學(xué)習(xí)以何種方式游走更好

實際上圖的游走分為兩大類：DFS和BFS

為了引入邊的權(quán)重，以及依概率選擇DFS或BFS，我們首先要將一般的隨機游走公式進(jìn)行修改：
{P}\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{cc} \frac{\pi_{vx}}{Z}, & \text { if }(v, x) \in E \\ 0, & \text { otherwise } \end{array}\right.
其中，\frac{\pi_{vx}}{Z}在值上與\frac{1}{|N_{(v)}|}是相等的，Z可以理解為歸一化的縮放因子

假設(shè)當(dāng)前隨機游走經(jīng)過邊(t,v)到達(dá)頂點v，節(jié)點v和x之間的邊權(quán)為w_{vx}，則可以將\pi_{vx}改寫為\alpha(t,x) \cdot w_{vx}
\alpha_{{pq}}(t, x)=\left\{\begin{array}{l} \frac{1}{p}, &\quad{ \text { if } d_{t x}=0} \\ 1, &\quad{\text { if } d_{t x}=1} \\ \frac{1}{q}, &\quad{ \text { if } d_{t x}=2} \end{array}\right.

其中，d_{tx}表示當(dāng)前節(jié)點v的一節(jié)鄰居節(jié)點到節(jié)點t的最短距離

  • p: 控制隨機游走以多大的概率“回頭”
  • q: 控制隨機游走偏向DFS還是BFS
    • q較大時(q>1)，傾向于BFS
    • q較小時(q<1)，傾向于DFS
  • p=1=1時，\pi_{vx}=w_{vx}

到此為止，GNN 中節(jié)點 Embedding 算法我就不再多敘述，其實還有很多更好的算法，例如 LINE，Struct2vec 等，不過我個人感覺這些 embedding 算法并不重要，或者說它們并不是 GNN 的核心部分，只要當(dāng)作工具來用就行了，類比 Transformer 中 Word Embedding 的地位

References

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容