node2vec原理介紹及實踐

Node2vec是用來產生網路中節點向量的模型，輸入是網路結構（可以無權重），輸出是每個節點的向量

主要思想：直接導word2vec的包，透過特定的遊走方式進行取樣，對於每個點都會生成對應的序列。再將這些序列視為文字匯入word2vec中的cbow或者skip-gram模型，即可得到每個節點的向量（對應word2vec中每個詞的向量）

原理介紹

對於每個節點，我們希望把該節點表示為向量的情況下出現該節點鄰近的點的機率最大，為了配合後面softmax所以取對數形式如下：

對於每個節點向量出現起鄰近點的機率顯然等於鄰近點中每個點出現機率相乘：

該節點向量下對應其他每個節點的機率可以用softmax表示：

再把上面三個公式整合，得到下面的目標函式：

其中

這個目標函式換句話說就是，再給定u和對應的臨近點N（u）下，透過求這個目標函式最大值的情況下得到f（n）的函式形式，從而得到每個節點的向量。

所以這裡有兩個要解決的問題，

①怎麼找每個節點對應的鄰近集

②用什麼方法求解這個目標函式

第一個問題用作者特殊的二階random walk進行取樣（這個方法後面會講到）

第二個問題是用word2vec，將一個節點加上其鄰近節點視為一篇文章，每個節點視為一個單詞，這樣就可以得到每個節點的向量了。

下面重點講講這個二階random walk方法，word2vec具體怎麼運作可以看我之前的一篇文章：

對於一個節點到另一個節點的轉移機率，可以視為

其中 π 是標準化前的轉移機率，Z是用來標準化的常數

而這個轉移機率還要乘以兩個節點之間的權重（如果是無權重則視為1）

而另外一部分就是node2vec的創新點了，這個轉移機率到底是怎樣的

我們結合下圖來看

當下一個節點X與前一個節點t和當前節點v等距時，α=1； 當下一個節點x是上一個節點時，α=1/p；在其他情況下，α=1/q

透過這個取樣方式，我們就可以得到一系列樣本，再倒入word2vec得到每個節點的向量了。

( ╯-_-)╯┴—┴ (ノ—_—)ノ~┴—┴ 分割線（╯－＿－）╯╧╧ （ノ*-_-*)ノ┴—┴

原始碼賞析

preprocess_transition_probs（初始生成節點到節點的機率）

def

preprocess_transition_probs

（

self

）：

‘’‘

Preprocessing of transition probabilities for guiding the random walks。

’‘’

####get_alias_edge這個函式是對每條邊設定為二階randomwalk的機率形式

###這個函式的作用是生成每個邊界的機率，同時會有alias_setup這個函式將機率進行轉換，方便後面抽樣

G

=

self

。

G

is_directed

=

self

。

is_directed

alias_nodes

=

{}

for

node

in

G

。

nodes

（）：

unnormalized_probs

=

［

G

［

node

］［

nbr

］［

‘weight’

］

for

nbr

in

sorted

（

G

。

neighbors

（

node

））］

#讀取每個鄰點權重

norm_const

=

sum

（

unnormalized_probs

）

###權重求和，作為公式中正則項常數的那個分母

normalized_probs

=

［

float

（

u_prob

）

/

norm_const

for

u_prob

in

unnormalized_probs

］

###除以分母

alias_nodes

［

node

］

=

alias_setup

（

normalized_probs

）

alias_edges

=

{}

triads

=

{}

if

is_directed

：

for

edge

in

G

。

edges

（）：

alias_edges

［

edge

］

=

self

。

get_alias_edge

（

edge

［

0

］，

edge

［

1

］）

else

：

for

edge

in

G

。

edges

（）：

alias_edges

［

edge

］

=

self

。

get_alias_edge

（

edge

［

0

］，

edge

［

1

］）

alias_edges

［（

edge

［

1

］，

edge

［

0

］）］

=

self

。

get_alias_edge

（

edge

［

1

］，

edge

［

0

］）

self

。

alias_nodes

=

alias_nodes

self

。

alias_edges

=

alias_edges

return

get_alias_edge是得到節點到節點的機率

def get_alias_edge（self， src， dst）：####二階ramdom walk

#src是隨機遊走序列中的上一個節點，dst是當前節點

‘’‘

Get the alias edge setup lists for a given edge。

’‘’

G = self。G

p = self。p

q = self。q

unnormalized_probs = ［］

for dst_nbr in sorted（G。neighbors（dst））：

if dst_nbr == src：

unnormalized_probs。append（G［dst］［dst_nbr］［‘weight’］/p）

elif G。has_edge（dst_nbr， src）：

unnormalized_probs。append（G［dst］［dst_nbr］［‘weight’］）

else：

unnormalized_probs。append（G［dst］［dst_nbr］［‘weight’］/q）

norm_const = sum（unnormalized_probs）

normalized_probs = ［float（u_prob）/norm_const for u_prob in unnormalized_probs］

return alias_setup（normalized_probs）

alias_setup ：輸入機率，得到對應的兩組數，方便後面的抽樣呼叫

def alias_setup（probs）：

‘’‘

alias_setup的作用是根據二階random walk輸出的機率變成每個節點對應兩個數，被後面的alias_draw函式所進行抽樣

’‘’

K = len（probs）

q = np。zeros（K）

J = np。zeros（K， dtype=np。int）

smaller = ［］

larger = ［］

for kk， prob in enumerate（probs）：

q［kk］ = K*prob

if q［kk］ < 1。0：

smaller。append（kk）

else：

larger。append（kk）##kk是下標，表示哪些下標小

while len（smaller） > 0 and len（larger） > 0：

small = smaller。pop（）##smaller自己也會減少最右邊的值

large = larger。pop（）

J［small］ = large

q［large］ = q［large］ + q［small］ - 1。0

if q［large］ < 1。0：

smaller。append（large）

else：

larger。append（large）

return J， q

alias_draw 抽樣函式

def alias_draw（J， q）：

‘’‘

Draw sample from a non-uniform discrete distribution using alias sampling。

’‘’

K = len（J）

kk = int（np。floor（np。random。rand（）*K））

if np。random。rand（） < q［kk］：

return kk

else：

return J［kk］

node2vec_walk就是對於給定的長度，對於開始節點開始模擬這個節點的路徑，涉及的函式都在上面提及

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］

######alias_draw這個函式是等於是根據二階random walk機率選擇下一個點

while len（walk） < walk_length：

cur = walk［-1］

cur_nbrs = sorted（G。neighbors（cur））###G。neighbors（cur）得到cur一級關聯的節點

if len（cur_nbrs） > 0：

if len（walk） == 1：

####cur［0］

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

最後總結一下node2vec的模型框架：透過二階random walk計算每個節點到其他節點的機率，然後將這個機率輸出為兩組數，方便後面抽樣呼叫。（具體原理可以看

The Alias Method： Efficient Sampling with Many Discrete Outcomes）

然後對於每個節點，設定每個節點被呼叫作為開始的次數，每次random walk的長度就可以得到一系列節點數排列。

最後將這些節點數排列視為文字，每個節點作為單詞，匯入word2vec中的Skipgram模型並用SGD進行最佳化，就得到每個節點的向量。

（ ╯-_-）╯┴—┴ （ノ—_—）ノ~┴—┴

分割線

（╯－＿－）╯╧╧ （ノ*-_-*）ノ┴—┴

實踐呼叫

具體過程原始碼可以看作者的github

snap-stanford/snap

這裡列出輸入輸出作展示

輸入形如下圖： 是34個節點的連線展示

輸出：每個節點的向量

好啦，終於說完了，小弟才疏學淺，請多多指教~