[Graph Embedding] node2vec

在前面兩篇文章中，我們分別介紹了DeepWalk 和 LINE，其中DeepWalk使用隨機遊走來擴展節點的領域。本文的node2vec的中心思想和DeepWalk很相似，作者對隨機遊走進行改寫，使得通過改寫的隨機遊走進行節點領域的遍歷時，可以同時反應dfs（深度優先採樣）和bfs（廣度優先採樣）的特性。
 

Introduction

關於DeepWalk之前的算法（應該已經是慢慢無人問津了）我們就暫且不討論了。作者對於DeepWalk和LINE這兩個算法的評價是：它們都提出了有效的圖表示學習算法，但是它們對網絡鄰域的概念的理解都比較僵硬死板，導致這些方法對網絡特有的連接模式不敏感。具體來說，網絡中的節點可以基於community的概念進行組織，也可以基於structural role的概念進行組織。而現實世界中的網絡通常都是表示出這2種等價關係的混合，作者提出的node2vec算法就可以靈活的兼顧這2種對於網絡節點之間進行組織的想法。

如上圖所示，節點u和節點s1屬於同一個緊密相連的community（社區），同時節點u和節點s6在2個不同的社區中扮演着相同的中心節點的角色（structural role）。

因此，node2vec算法學習到的特徵表示向量想要做到：

• 同一個community中的節點更加的相似
• 擁有類似的結構特徵（structural role）的節點更加的相似

node2vec算法原理

1. 目標函數

圖的定義爲 G = ( V , E ) G = (V,E) G=(V,E)，其中V爲節點集合，E爲邊集合。定義 f : V → R d f : V\rightarrow R^d f:V→Rd 爲從節點到特徵表示向量的映射函數， f f f 相當於一個大小爲 ∣ V ∣ × d |V| \times d ∣V∣×d 的矩陣，這就是算法所求。對任何一個源節點 u ∈ V u \in V u∈V，我們定義 N S ( u ) ⊂ V N_S(u) \subset V NS​(u)⊂V作爲節點 u 通過改寫的隨機遊走策略S生成的網絡領域。

優化目標爲：
m a x f   ∑ u   ∈   V l o g   P r ( N S ( u ) ∣ f ( u ) ) (1) \underset{f}{max} \ \displaystyle \sum_{u \ \in\ V}{log\ P_r(N_S(u)| f(u))} \tag1 fmax​ u ∈ V∑​log Pr​(NS​(u)∣f(u))(1)
爲了讓這個目標函數更加易於處理，引入了2個假設：

1. 條件獨立性（Conditionalindependence）：對一個節點u進行改寫的隨機遊走策略S獲得節點的網絡領域 N S ( u ) N_S(u) NS​(u)，定義其中每一個節點被採樣到的概率與其他節點被採樣到的概率是相互獨立的。即節點u採樣到 N S ( u ) N_S(u) NS​(u)的概率是節點u分別採樣到 N S ( u ) N_S(u) NS​(u)中每一個節點的概率的乘積，表示如下：
   P r ( N s ( u ) ∣ f ( u ) ) = ∏ n i ∈ N S ( u ) P r ( n i ∣ f ( u ) ) P_r(N_s(u)| f(u)) = \prod_{n_i \in N_S(u)}{P_r(n_i|f(u))} Pr​(Ns​(u)∣f(u))=ni​∈NS​(u)∏​Pr​(ni​∣f(u))

2. 特徵空間中的對稱性（Symmetry in feature space）：在特徵空間中，源節點和領域中的節點相互的影響是對稱的。就是說節點u作爲源節點和作爲領域中的節點時，它的feature represensation（ f ( u ) f(u) f(u)）是一樣的；這裏可以對比LINE算法中，節點作爲源節點和領域中的節點時，表示向量是不一樣的。上述條件概率就可以改寫爲：
   P r ( n i ∣ f ( u ) ) = e x p ( f ( n i ) ⋅ f ( u ) ) ∑ v   ∈   V e x p ( f ( v ) ⋅ f ( u ) ) P_r(n_i|f(u)) = {exp(f(n_i)\cdot f(u))\over \displaystyle \sum_{v \ \in\ V}{exp(f(v) \cdot f(u))}} Pr​(ni​∣f(u))=v ∈ V∑​exp(f(v)⋅f(u))exp(f(ni​)⋅f(u))​

基於上面的假設，公式（1）可以簡化爲：
m a x f   ∑ u   ∈   V [ − l o g Z u + ∑ n i ∈ N S ( u ) f ( n i ) ⋅ f ( u ) ] (2) \underset{f}{max} \ \displaystyle \sum_{u \ \in\ V} {[-logZ_u + \displaystyle \sum_{n_i\in N_S(u)}{f(n_i) \cdot f(u)}]} \tag2 fmax​ u ∈ V∑​[−logZu​+ni​∈NS​(u)∑​f(ni​)⋅f(u)](2)
其中 Z u = ∑ u ∈ V e x p ( f ( u ) ⋅ f ( v ) ) Z_u = \displaystyle \sum_{u \in V}{exp(f(u) \cdot f(v))} Zu​=u∈V∑​exp(f(u)⋅f(v))， Z u Z_u Zu​的計算非常費時，所以作者採用負採樣的方法來優化該部分。

對公式（2）採用SGD（隨機梯度下降）進行優化，所求得 f f f 就是我們將節點映射爲表示向量的函數。然後就可以將節點或邊的表示向量餵給下游的分類器，進行節點預測、邊預測等任務。

2. 節點序列採樣策略

在普通的Random Walk中， 令 c i c_i ci​ 表示一個節點序列中的第i個節點，則節點 c i c_i ci​ 服從下面的分佈：

其中 π v x \pi_{vx} πvx​是從節點v到節點x的非歸一化前的轉移概率，Z是歸一化常數。

作者基於深度優先採樣和廣度優先採樣的思想，對上面的傳統的Random Walk進行了改進，node2vec引入了2個參數p和q。如上圖所示，我們假設當前節點剛從節點t 經過邊(t, v) 到達節點v。

我們令上面傳統Random Walk式中的未歸一化前的轉移概率 π v x = α p q ( t , x ) ⋅ w v x \pi_{vx} = \alpha_{pq}(t,x)\cdot w_{vx} πvx​=αpq​(t,x)⋅wvx​ ,其中

上式中的 d t x d_{tx} dtx​ 表示從節點t到節點x的最短路徑長度。我們將上面的 α p q ( t , x ) \alpha_{pq}(t,x) αpq​(t,x) 帶入回傳統的Random Walk式中，就得到了頂點到他的鄰居節點的轉移概率。

3. 參數解析

上面 α p q ( t , x ) \alpha_{pq}(t,x) αpq​(t,x) 中的參數p和q的意義如下：

• Return parameter（p），參數p控制在一個採樣序列中，對於已經訪問到的節點進行重採樣的概率，如果我們參數p的值很大的時候，則一個節點不太會重新採樣一個剛剛採樣到的節點；如果參數p的值比較小的時候，則相反。

• In-out parameter（q），參數q控制着採樣序列是採樣到多爲community內的節點還是community以外的節點。

  我們令 q > 1 q > 1 q>1，則採樣節點會傾向跑到與節點t在同一個community中的節點，類似於BFS（廣度優先搜索）。

  我們令 q < 1 q < 1 q<1，則採樣節點會傾向於跑出t所在的community，類似於DFS（深度優先搜索）。

4. 僞代碼

上面是作者提供的node2vec的僞代碼，這裏不多加贅述。值得一提的是，節點到它的鄰居節點的轉移概率 π v x \pi_{vx} πvx​已經被提前算好了。因此與LINE中一樣，作者採用alias table method，採樣一個節點的時間複雜度僅爲O(1)。

論文原文：node2vec: Scalable Feature Learning for Networks