《圖表示學習入門1》中，討論了為什么要進行圖(graph)表示，以及兩種解決圖表示問題的思路。這篇把Node2Vec來作為線性化思路的一個典型來討論。

如果你了解Word2Vec的話，這個就太簡單了。

代碼實現：(https://github.com/leichaocn/graph_representation_learning)

目錄

核心想法

準備節點序列

用節點序列來訓練Node2Vec

指標評價

總結

參考文獻

核心想法

回想文本中Word2Vec中抽取單詞Embedding的方式，是怎么做的？

準備句子語料，用一個詞預測周圍詞來組成無監督訓練的樣本對。

用這些樣本來訓練一個2層的Word2Vec網絡，抽出隱層權重作為Embedding。

那我們只要準備好節點序列，是否也可以用Word2Vec的思路來抽取節點Embedding？

但是我們需要首先給節點創造一些序列，或者說語料“句子”。

如果清楚了這一點，我們的想法就大致如下：

準備節點序列

圖(graph)結構中，按照節點的連接關系生成節點序列，很容易。然而如果任意生成序列，也會導致序列的意義壞掉。正如一個隨機生成的文本肯定是糟糕的語料，一個隨意生成的節點序列也必然糟糕。

所以，我們需要針對每個節點，適度地有中心的產生語料。

用節點序列來訓練Node2Vec

以skip-gram(中心詞預測周圍詞)的方式，生成樣本對，來訓練Node2Vec網絡，最終從隱層權重中抽取出Embedding，自帶一定的相似度信息。

顯然，這是一種無監督的特征學習，只需要利用現成的圖(graph)結構準備好節點序列就可以了。

準備節點序列

如我們剛才討論的，我們的節點序列必須圍繞一些節點，稍微帶點”中心思想“，而不能瞎走。

BFS與DFS

這是兩種耳熟能詳的常見做法：

廣度優先搜索(BFS)

覆蓋度較好，但是太局部(local)。

深度優先搜索(DFS)

搜索深度較好，但是太全局(global)，過于遠的鄰居對表征幫助不大。

2im1.png

圖1.廣度優先搜索與深度優先搜索的對比(source)

然而，這兩種做法都有點極端，本著中庸之道的精神，綜合BFS和DFS，請出我們的主角：帶偏隨機游走(Biased random walk)。

Biased Random Walk

它相當于"插值"BFS和DFS，用兩個參數

，

來調節兩者的比例，命名為Biased，意在強調人為引入的這兩個參數。

2im2.png

圖2.帶偏隨機游走的核心思想(source)

帶偏隨機游走做法是：

對一個圖遍歷num_walks輪；每輪都用圖中全部節點，生成一段話；每句話是一個節點開頭，為預定長度walk_length。

對每個節點，讀入概率數據，進行以下1/2步的循環，直到達到預定長度。

1.用Alias Method采樣下一個節點。

2.采到的那個節點加入到節點序列里。該節點切換為當前節點。

在原始代碼(含鏈接)里，最核心就是下面這兩個方法：

def node2vec_walk(self, walk_length, start_node):

'''

Simulate a random walk starting from start node.

'''

G = self.G

alias_nodes = self.alias_nodes

alias_edges = self.alias_edges

walk = [start_node]

while len(walk) < walk_length:

cur = walk[-1]

cur_nbrs = sorted(G.neighbors(cur))

if len(cur_nbrs) > 0:

if len(walk) == 1:

walk.append(cur_nbrs[alias_draw(alias_nodes[cur][0], alias_nodes[cur][1])])

else:

prev = walk[-2]

next = cur_nbrs[alias_draw(alias_edges[(prev, cur)][0],

alias_edges[(prev, cur)][1])]

walk.append(next)

else:

break

return walk

def simulate_walks(self, num_walks, walk_length):

'''

Repeatedly simulate random walks from each node.

'''

G = self.G

walks = []

nodes = list(G.nodes())

print 'Walk iteration:'

for walk_iter in range(num_walks):

print str(walk_iter+1), '/', str(num_walks)

random.shuffle(nodes)

for node in nodes:

walks.append(self.node2vec_walk(walk_length=walk_length, start_node=node))

return walks

simulate_walks()用來生成“一篇文章”，對一個圖遍歷多輪(可以想成生成了多個自然段)，每輪隨機一下(每輪生成一個自然段)，遍歷所有節點(每個節點對應一句話)。最終獲得walks，格式為數組的數組，可以理解成一篇文章，每個自然段是對圖的一種隨機解讀，每個元素都是一句子的開頭。多個自然段可以理解為對圖結構的一種反復解讀：)。

node2vec_walk()則是傳入一個節點，生成一句話(節點序列)。由于提前把概率設置并儲存在圖數據中，這里調用alias_draw()即可獲得。alias_draw實現的就是Alias Method采樣方法。對Alias Method采樣方法有興趣的小伙伴可以進一步了解。

生成的結果在圖3中進行了舉例，有助于理解。

可能需要注意：最終生成的序列很有可能有一個節點重復出現多次的情況。

無論走的方向是往前或往回或平行，都是隨機的，因此很可能會往前走了又走回來了。這沒關系，因為這都是由起始節點及圖(graph)結構造成的，我們給它多產生一些序列即可，即豐富的“語料”。

用節點序列來訓練Node2Vec

通過之前的操作，我們已經準備好了節點序列，按照skip-gram思想，即對于輸入的句子，我們用中心詞預測周邊詞們；對于準備好的節點序列串，我們也用某個中心節點預測周邊節點們。

注意：這里的周邊，指的是節點序列里某元素的周邊，而不是圖(graph)的某元素的周邊。用

表示基于策略

(本文指)生成的序列，節點

的周圍節點的集合，如圖3所示。

2im3.png

圖3.節點序列及周圍節點集合生成示意圖

優化目標

假設節點

的one-hot向量為

，在一串序列中，它周圍節點one-hot向量為

，這些

組成的集合為

。

對自己周圍的預測概率

，通過引入樸素貝葉斯假設，可以簡化為：

我們希望這個

盡可能地大，根據公式，現在的問題是如何求

。

這個好辦，我們只要學一個函數

，輸入

，輸出對節點

的預測概率

。

而這個函數

正是我們要訓練的神經網絡。

這下我們就清楚了，可以定義如圖3所示的這個優化目標：

2im4.png

圖4.node2vec的學習目標

神經網絡結構

下圖中的神經網絡即實現這個

，只要輸入一個樣本

，前向傳播一次，從向量

的元素中，即可獲得每一個標簽

對應的

。

2im5.png

圖5.Node2Vec神經網絡的結構

在訓練中，

將被納入我們的目標函數進行尋優。

具體的訓練涉及細節較多，我們將在Word2Vec中詳細討論。

Embedding的獲得

待網絡訓練結束，只要輸入節點

的one-hot向量

，前向傳播到隱層，生成

，即為節點

的Embedding。

更簡便的方式是，由于訓練時都是用one-hot向量訓練，其實，只需要把對應

里為1的那個元素，所對應的權重序列拿出來，即為節點

的Embedding。

這部分，將在Word2Vec中詳細討論。

指標評價

由于是無監督訓練，同時獲取的Embedding也只是節點的特征表示，因此需要結合具體項目表現來對Node2vec結果進行評價。

例如節點分類項目，訓出Embedding，再結合節點已標注的類別標簽，訓練一個分類器，根據分類結果的指標對Embedding進行間接評價。需要注意的是，節點序列生成策略、Node2Vec網絡的隱層維度、分類器的選型和參數，均影響分類結果的指標。

總結

通過合適的策略生成節點序列，當做訓練Node2Vec的“語料”。

訓練Node2Vec網絡，即以Word2Vec的思路訓練神經網絡，抽出隱層權重作為對應節點的Embedding。

參考文獻

[1] Jure Leskovec, 《Graph Representation Learning》

[2] Jure Leskovec, 《Representation Learning on Networks》

(如有錯誤及表述不清，請不吝反饋)

總結

以上是生活随笔為你收集整理的node2vec文献出处_图表示学习入门2——Node2Vec的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。