節(jié)點(diǎn)嵌入算法—Node2vec原理與優(yōu)化

來(lái)源：https://zhuanlan.zhihu.com/p/267371107

本文從基礎(chǔ)知識(shí)開始，一步一步引出Node2vec算法并給出了優(yōu)化策略，保證閱讀0門檻，如果覺(jué)得篇幅太長(zhǎng)讀不完建議先收藏起來(lái)哦~

背景知識(shí)-圖結(jié)構(gòu)

在介紹Node2vec之前，我們先從圖開始。
圖是由節(jié)點(diǎn)和邊組成的結(jié)構(gòu)，如下圖所示。它在我們生活中是很常見(jiàn)的，比如社交網(wǎng)絡(luò)，蛋白質(zhì)分子之間的相互作用網(wǎng)絡(luò)等。

網(wǎng)絡(luò)分析中的許多重要任務(wù)涉及對(duì)節(jié)點(diǎn)和邊的預(yù)測(cè)，但是想要利用圖中的信息是比較困難的，因?yàn)閳D本身是離散的。

因此，我們需要使用一種方式將圖結(jié)構(gòu)轉(zhuǎn)化為便于計(jì)算的表達(dá)方式。

背景知識(shí)-嵌入算法

嵌入可以將實(shí)體映射到連續(xù)的向量空間中，使得實(shí)體可以用向量來(lái)表示。

嵌入也有很多分類，這里Node2vec主要討論點(diǎn)嵌入。

我們希望嵌入能夠保留圖中的信息，比如通過(guò)某個(gè)點(diǎn)的嵌入向量能夠找到它在圖中的鄰居。同時(shí)，我們希望可以將某個(gè)點(diǎn)的嵌入向量直接用作下游任務(wù)的輸入。

那么我們應(yīng)該使用什么方法對(duì)某個(gè)點(diǎn)進(jìn)行嵌入呢？

背景知識(shí)-SkipGram模型

在自然語(yǔ)言處理領(lǐng)域中也曾經(jīng)遇到了類似的詞嵌入問(wèn)題，而其中一個(gè)有名的模型叫做SkipGram。

該模型使用一個(gè)滑窗對(duì)句子進(jìn)行采樣，使得中心詞和滑窗內(nèi)的單詞同時(shí)出現(xiàn)的概率大，而中心詞和滑窗外的單詞同時(shí)出現(xiàn)的概率小, 來(lái)保證模型能夠?qū)W習(xí)到某個(gè)單詞的周圍詞信息。

采樣的結(jié)果是一系列的由中心詞和相鄰詞組成的單詞對(duì)，正如圖片中所展示的那樣。

在對(duì)文本進(jìn)行采樣以后，Skipgram模型的第二步是將采樣獲取到的中心詞轉(zhuǎn)化為one-hot編碼，并作為神經(jīng)網(wǎng)絡(luò)的輸入，而神經(jīng)網(wǎng)絡(luò)的輸出則是相鄰詞的向量。

在經(jīng)過(guò)一系列訓(xùn)練后，將某個(gè)中心詞的one-hot向量與隱藏層的矩陣相乘獲得的就是附近詞的信息，即該詞的詞嵌入向量。

依照這個(gè)思路我們也可以將圖中某個(gè)節(jié)點(diǎn)和它附近的節(jié)點(diǎn)嵌入到向量中，那么我們應(yīng)該如何借鑒Skipgram模型對(duì)圖中的節(jié)點(diǎn)進(jìn)行嵌入呢？

背景知識(shí)-隨機(jī)游走模型

Skipgram模型的輸入是序列化的數(shù)據(jù)，這與圖的結(jié)構(gòu)化數(shù)據(jù)是不符合的，因此在應(yīng)用Skipgram模型之前，我們需要獲取節(jié)點(diǎn)的序列。

在此前的工作DeepWalk中提出了Random Walk的概念，具體來(lái)說(shuō)就是從圖中任意一個(gè)點(diǎn)出發(fā)，在節(jié)點(diǎn)之間等概率地轉(zhuǎn)移，將上述步驟重復(fù)有限次，最終采集出一系列節(jié)點(diǎn)序列。

當(dāng)收集到足夠多的序列后，我們就可以用類似處理文本的方式，將這些序列輸入Skipgram模型，并最終得到嵌入向量。

Node2vec算法-對(duì)隨機(jī)游走模型提出質(zhì)疑

簡(jiǎn)單的隨機(jī)游走是存在問(wèn)題的。

在Node2vec論文中指出，通過(guò)隨機(jī)游走獲取的節(jié)點(diǎn)序列不能同時(shí)反應(yīng)圖的同質(zhì)性（homophily）和結(jié)構(gòu)對(duì)等性（structural equivalence ），而這兩種特性分別是由DFS和BFS體現(xiàn)的。

正如下圖所示，藍(lán)色箭頭的采樣序列反映了圖的同質(zhì)性而紅色箭頭的采樣序列反映了圖的結(jié)構(gòu)對(duì)等性。

因此Node2vec提出采用一些參數(shù)來(lái)控制這個(gè)采樣過(guò)程，使得這個(gè)采樣過(guò)程既有DFS的特征也有BFS的特征。

Node2vec算法-對(duì)隨機(jī)游走的改進(jìn)

在Node2vec中，作者提出了采用一個(gè)搜索參數(shù)α來(lái)控制隨機(jī)游走的傾向，該參數(shù)是由p、q兩個(gè)值來(lái)確定的，定義如下：

以下圖為例，假設(shè)我們已經(jīng)從t轉(zhuǎn)移到v，接下來(lái)我們要采集新的節(jié)點(diǎn)。

• 如果p值比較小，那么采樣將在t附近徘徊，表現(xiàn)出BFS的特征。

• 如果q值比較小，那么采樣將逐漸遠(yuǎn)離t，表現(xiàn)出DFS的特征。

通過(guò)這種方式，我們可以對(duì)不同的圖使用不同的采樣策略，以此來(lái)得到質(zhì)量更高的節(jié)點(diǎn)序列。這是Node2vec的一大貢獻(xiàn)。

Node2vec算法-實(shí)驗(yàn)表現(xiàn)

作者在Link prediction和Node classification這兩個(gè)任務(wù)上對(duì)Node2vec進(jìn)行了實(shí)驗(yàn)。

結(jié)果表明，在這兩項(xiàng)任務(wù)上Node2vec都取得了非常顯著的進(jìn)步。

在Node classification的部分?jǐn)?shù)據(jù)集上，Node2vec甚至能達(dá)到20%的提升，這是非常驚人的，截取論文中的實(shí)驗(yàn)結(jié)果如下：

Node2vec優(yōu)化-負(fù)采樣加快計(jì)算速度

Node2vec依然有很多值得改進(jìn)的地方。

我們?cè)賮?lái)看一眼這個(gè)Skipgram模型，隱藏層和輸出層之間采用全連接的方式，這意味反向傳播需要消耗大量計(jì)算資源。

因此作者提出采用負(fù)采樣的方式，在反向傳播時(shí)更新隱藏層的部分權(quán)值，以此來(lái)減少計(jì)算量。

而權(quán)重是否被更新取決于權(quán)重相關(guān)的節(jié)點(diǎn)出現(xiàn)概率，節(jié)點(diǎn)出現(xiàn)概率越大，與之相關(guān)的權(quán)值被更新的概率也越大，權(quán)重被更新的概率可以表示如下：

（注意：公式中的0.75是一個(gè)經(jīng)驗(yàn)結(jié)論，實(shí)際應(yīng)用可以根據(jù)情況修改）

Node2vec優(yōu)化-部分采樣加快采樣速度

對(duì)大規(guī)模的圖采樣極其消耗時(shí)間，因此我們可以對(duì)網(wǎng)絡(luò)中的部分節(jié)點(diǎn)采樣以節(jié)約采樣耗時(shí)。

在部分采樣中，我們需要控制節(jié)點(diǎn)被采樣的概率，節(jié)點(diǎn)出現(xiàn)的頻率Z(vi)越高，那么將它做為起點(diǎn)進(jìn)行采樣的概率就越小，可以理解為已經(jīng)被反復(fù)采樣的節(jié)點(diǎn)就不需要重新采樣了，如下圖所示：

（注意：公式中的0.001依然是一個(gè)經(jīng)驗(yàn)結(jié)論，實(shí)際應(yīng)用可以根據(jù)情況修改）

以上就是本文的所有內(nèi)容啦~都看到這里了，不妨點(diǎn)個(gè)贊再走唄

?···? END? ···

↓長(zhǎng)按關(guān)注本號(hào)、加我交流↓
? ??