最近圖相關(guān)的理論很火熱啊，耳邊一直聽(tīng)到各種graph embedding，什么GNN、GCN，結(jié)果發(fā)現(xiàn)自己對(duì)這方面完全不了解，趕緊找?guī)灼撐膩?lái)讀一讀。今天這一篇就是大家不管聽(tīng)沒(méi)聽(tīng)說(shuō)但總覺(jué)得眼熟的node2vec。不用想，這個(gè)node2vec一定跟word2vec有血緣關(guān)系，所以熟悉word2vec的同學(xué)應(yīng)該可以很快了解node2vec的思想。

不同于圖像、自然語(yǔ)言這種歐式空間的數(shù)據(jù)，網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)——圖，通常無(wú)法通過(guò)CNN或者RNN來(lái)處理，這就需要我們尋找其他的方法來(lái)處理圖數(shù)據(jù)。圖數(shù)據(jù)其實(shí)非常常見(jiàn)，例如社交網(wǎng)絡(luò)關(guān)系、分子結(jié)構(gòu)、論文互相引用的關(guān)系網(wǎng)絡(luò)等等，所以如何表達(dá)網(wǎng)絡(luò)節(jié)點(diǎn)的特征就十分重要，表達(dá)好了節(jié)點(diǎn)的特征，我們就可以用它做下游的分類(lèi)、預(yù)測(cè)、聚類(lèi)、可視化等等任務(wù)。

傳統(tǒng)的特征表示方法：

1. 特征工程

這個(gè)是機(jī)器學(xué)習(xí)最苦最累最關(guān)鍵的活兒，之前處理圖數(shù)據(jù)，需要請(qǐng)專家人工定義網(wǎng)絡(luò)節(jié)點(diǎn)的特征，這里面涉及很多圖論的知識(shí)和領(lǐng)域知識(shí)，所以特征工程十分麻煩。
雖然這種特征工程最后往往可以（在花費(fèi)巨大人力物力之后）取得比較好的效果，但一個(gè)明顯的問(wèn)題是——泛化性能差！因?yàn)樘卣鞴こ掏轻槍?duì)特定任務(wù)的，你換一個(gè)任務(wù)，也許之前的特征就不管用了。

2.在任務(wù)中學(xué)特征

前面不是嫌累嫌麻煩嘛，那咱們就不自己定義特征，定義一個(gè)下游任務(wù)，把這些特征作為參數(shù)，喂大量數(shù)據(jù)讓它自己去學(xué)！顯而易見(jiàn)，你是省事兒了，機(jī)器可不省事兒。成千上萬(wàn)個(gè)節(jié)點(diǎn)、隨便就上百的維度，輕輕松松讓你增加幾千萬(wàn)訓(xùn)練參數(shù)，這個(gè)計(jì)算開(kāi)銷(xiāo)可大了。而且，這還是有監(jiān)督的方法，意味著依然在不同任務(wù)間的泛化性能較差。

3.隱模型法/降維/矩陣分解法

這一類(lèi)方法不知道怎么叫才好，總的思想跟推薦系統(tǒng)中矩陣分解法十分類(lèi)似，屬于無(wú)監(jiān)督學(xué)習(xí)。試著把原來(lái)的網(wǎng)絡(luò)結(jié)構(gòu)表達(dá)成一個(gè)巨大的系數(shù)矩陣，然后通過(guò)Factorization來(lái)得到隱表示，作為各個(gè)節(jié)點(diǎn)的表示向量。這一類(lèi)方法主要的問(wèn)題在于計(jì)算開(kāi)銷(xiāo)大，尤其是對(duì)于真實(shí)世界中的大型網(wǎng)絡(luò)，搞一個(gè)矩陣分解也不是什么容易事兒。另外，實(shí)證表明這樣的表示在很多預(yù)測(cè)任務(wù)上效果較差。

新的思路 & 本文方法

上面列舉了傳統(tǒng)的方法的各種問(wèn)題。那么可以怎么設(shè)計(jì)一種新的思路來(lái)得到節(jié)點(diǎn)的表示呢？
作者們想到了那大名鼎鼎的詞向量——word2vec。詞向量方法從大量的無(wú)標(biāo)注文本中學(xué)得詞語(yǔ)的分布式表示，不僅蘊(yùn)含了大量的信息，而且可以遷移到各種下游任務(wù)中。對(duì)于網(wǎng)絡(luò)數(shù)據(jù)能否使用同樣的方法呢？
網(wǎng)絡(luò)中存在很多很多通路，將各個(gè)節(jié)點(diǎn)連成一條線，這些連線蘊(yùn)含著節(jié)點(diǎn)之間的相互關(guān)系，就如同句子中各個(gè)詞語(yǔ)的關(guān)系一樣。因此，我們可以自然地想到——把這些節(jié)點(diǎn)序列當(dāng)做句子，用word2vec的方法進(jìn)行訓(xùn)練，就可以得到node的向量表示了！

這里的關(guān)鍵問(wèn)題在于——如何生成node序列。這也是本文的重點(diǎn)。

如何生成node sequence

這里給出一個(gè)論文中的圖來(lái)輔助說(shuō)明：

這個(gè)圖中，可以看到有兩個(gè)明顯的小團(tuán)體，分別以u(píng)和s6為中心。如果這就是一個(gè)簡(jiǎn)單的社交網(wǎng)絡(luò)關(guān)系的話，可以猜測(cè)u和s1,s2,s3,s4也許是同班同學(xué)這樣的關(guān)系，同樣s6和s5,s7,s8,s9也是類(lèi)似的關(guān)系，但二者不是同一個(gè)班。然后u和s6也許是兩個(gè)班的班長(zhǎng)。

那么這個(gè)里面就有些意思了，我們?cè)谏晒?jié)點(diǎn)序列的時(shí)候，要有什么規(guī)則？
首先，我們要知道，節(jié)點(diǎn)放到一個(gè)序列中了，就說(shuō)明你認(rèn)為它們?cè)谀撤N意義上是相似的。
你既可以認(rèn)為u跟s1,s2,s3,s4它們是相似的，它們是網(wǎng)絡(luò)中直接的鄰居，這時(shí)稱為homophily；
也可以認(rèn)為u應(yīng)該跟s6更相似，這種稱為結(jié)構(gòu)相似，structural equivalence。

要想從一個(gè)節(jié)點(diǎn)去尋找它的直接鄰居，就要通過(guò)BFS（廣度優(yōu)先搜索），而如果想找到那些結(jié)構(gòu)相似的，我們就不能在鄰居那里轉(zhuǎn)圈圈的，就需要“走出去”，因此就需要通過(guò)DFS（深度優(yōu)先搜索）。圖中給出了兩種方法的示意。

node2vec使用的方法——biased random walk

在網(wǎng)絡(luò)的表示中，homophily和structural equivalence都十分重要，我們希望可以在生成序列的時(shí)候同時(shí)考慮這兩種相似性。
并且，我們希望可以有參數(shù)讓我們控制二者的一個(gè)偏重，這樣在不同的任務(wù)我們可以靈活地調(diào)整。

看下圖：

假設(shè)我們從t節(jié)點(diǎn)開(kāi)始了一個(gè)random walk，現(xiàn)在到達(dá)了v節(jié)點(diǎn)。
現(xiàn)在的問(wèn)題是下一步怎么走？

如果采取BFS策略的話，應(yīng)該走到x1，因?yàn)関和x1都是t節(jié)點(diǎn)的直接鄰居；如果采取DFS策略的話，應(yīng)該走向x2或者x3，因?yàn)樗鼈兒蛅都中間隔了一步；當(dāng)然，也可能又返回到了t節(jié)點(diǎn)。

于是作者設(shè)計(jì)了一個(gè)二階轉(zhuǎn)移概率算法：
兩個(gè)節(jié)點(diǎn)之間的轉(zhuǎn)移概率為：

其中，w為兩節(jié)點(diǎn)的邊的weight，這個(gè)根據(jù)場(chǎng)景而設(shè)定。α為search bias，定義為：

一個(gè)節(jié)點(diǎn)的下一步怎么走，取決于它的上一步和下一步的關(guān)系。

有點(diǎn)拗口，我們逐一解釋一下：
v是當(dāng)前的節(jié)點(diǎn)，t是v的上一步所在節(jié)點(diǎn)，而x代表下一步的位置。
d(t,x)代表t和x之間的最短距離：

• 當(dāng)d=0時(shí)，就是從v又回到t節(jié)點(diǎn)的意思，這個(gè)時(shí)候search bias為1/p，可以理解為以1/p的概率返回上一步；
• 當(dāng)d=1時(shí)，則x為t的直接鄰居，相當(dāng)于BFS，這時(shí)的bias為1；
  -當(dāng)d=2時(shí)，則x是t鄰居的鄰居，相當(dāng)于DFS，這時(shí)的bias為1/q；

作者稱p為Return parameter，因?yàn)閜控制著回到原節(jié)點(diǎn)的概率；成q為In-out parameter，因?yàn)樗刂浦鳥(niǎo)FS和DFS的關(guān)系。

這樣，我們?cè)O(shè)置不同的p和q，就可以得到不一樣偏重的node sequence。在訓(xùn)練模型的時(shí)候，可以使用grid search來(lái)尋找最優(yōu)的p和q。也可以根據(jù)場(chǎng)景的需要來(lái)選擇p和q。

如何學(xué)習(xí)節(jié)點(diǎn)特征

這里就是完全借用word2vec的方法。
總的目標(biāo)函數(shù)是：

這里的f就是把節(jié)點(diǎn)u映射到特征空間的函數(shù)，N(u)是通過(guò)前面node sequence得到的u的近鄰節(jié)點(diǎn)，相當(dāng)于詞向量訓(xùn)練中的上下文。
下面是具體如何計(jì)算：

這一部分不想多講，了解詞向量的話這里十分好理解。
關(guān)于詞向量，可以在我的專欄中找到相關(guān)的文章。

這樣，我們就可以總結(jié)一個(gè)node2vec完整的算法框架了：

如何表示邊的特征

上面已經(jīng)學(xué)習(xí)到了各個(gè)節(jié)點(diǎn)（node）的特征，但是很多任務(wù)中我們是針對(duì)邊（edge）的，因此我們也需要邊的特征。
實(shí)際上，一條邊不就是由兩個(gè)節(jié)點(diǎn)決定的嗎，因此可以用兩個(gè)節(jié)點(diǎn)的特征來(lái)表示，作者給出了一些選項(xiàng)：

案例和實(shí)驗(yàn)：

1. 可視化

作者首先在一個(gè)人物關(guān)系網(wǎng)絡(luò)上試了試node2vec，通過(guò)kmeans聚類(lèi)，并做了一個(gè)可視化，看看node2vec得到的節(jié)點(diǎn)向量可以反映出網(wǎng)絡(luò)的什么特點(diǎn)：
當(dāng)作者設(shè)置p=1,q=0.5的時(shí)候，聚類(lèi)的效果是這樣的：

可見(jiàn)這個(gè)時(shí)候各個(gè)小社區(qū)、小團(tuán)體被聚為一類(lèi)。

當(dāng)作者設(shè)置p=1,q=2的時(shí)候，聚類(lèi)效果是這樣的：

這個(gè)時(shí)候，可以發(fā)現(xiàn)各個(gè)社區(qū)之間的橋梁——藍(lán)色節(jié)點(diǎn)，被聚成一類(lèi)，因?yàn)樗鼈冇蓄?lèi)似的結(jié)構(gòu)特點(diǎn)，而那些淡黃色的點(diǎn)，是那些人物關(guān)系中比較邊緣化的那些人。

所以可以看到，不同的p和q確實(shí)使node2vec刻畫(huà)一個(gè)網(wǎng)絡(luò)在不同方面的特點(diǎn)。

2. 節(jié)點(diǎn)分類(lèi)（node classification）

這里先把使用的測(cè)試數(shù)據(jù)集和用于對(duì)比的模型列一下，由于比較好理解，我就不翻譯了：

數(shù)據(jù)集：

對(duì)比模型：

實(shí)驗(yàn)結(jié)果：

3.連接預(yù)測(cè)（link prediction）

對(duì)于link，我們就需要構(gòu)造邊的特征的，具體構(gòu)造方法上面也給出了。這里也是直接貼實(shí)驗(yàn)結(jié)果了：

a，b，c，d分別代表四種edge feature生成的方法。

這些就大致是node2vec的內(nèi)容，更多細(xì)節(jié)還是參見(jiàn)論文吧。
另外，斯坦福提供了現(xiàn)成的代碼和訓(xùn)練方法，可以參見(jiàn)他們的官網(wǎng)：
http://snap.stanford.edu/node2vec/