Node2Vec

論文名稱：node2vec: Scalable Feature Learning for Networks

論文地址：https://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf

Node2Vec是用于學習網絡節點的連續特征表示。node2vec將節點映射為低維特征表示，最大化網絡鄰居節點的似然表示。定義一組彈性的鄰居節點的概念，設計有偏的隨機游走策略，學習探索各種各樣的鄰居表示。

1.FEATURE LEARNING FRAMEWORK

$G=(V,E)$表示網絡， 我們分析方法適用于有向（無向），有權（無權）的網絡模型。$f:V\to {\mathbb{R}}^d$將節點映射為 特征表示，用于下游的預測任務。$d$表示特征表示的維度。$f$是大小為$|V|\times d$的參數矩陣。對于每個source node $u\in V$, 我們定義$N_S(u)?V$ 為通過采樣策略$S$獲得$u$節點的鄰居節點。

我們采用擴展的Skip-gram結構。給定節點$u$的特征表示，最大化鄰居節點的log-probability。 $f$表示如下：
$$\underset{f}{\max }\sum _{u\in V}\log \mathrm{Pr}\left(N_S(u)\mid f(u)\right)\text{\hspace{1em}(1)}$$
為了使得優化過程易于處理，我們作出兩個假設：

• 條件獨立假設. 在給定source node的節點，他們的鄰居節點是是獨立的。
  $$\mathrm{Pr}\left(N_S(u)\mid f(u)\right)=\prod _{n_i\in N_S(u)}\mathrm{Pr}\left(n_i\mid f(u)\right)$$

• Symmertry in feature space。 source node和neighborhood在feature space之間的影響是對稱。

對source-neighborhood node pair的特征進行softmax dot product操作：
$$\mathrm{Pr}\left(n_i\mid f(u)\right)=\frac{\exp \left(f\left(n_i\right)?f(u)\right)}{{\sum }_{v\in V}\exp (f(v)?f(u))}$$
根據以上假設Eq.1 簡化為：
$$\underset{f}{\max }\sum _{u\in V}??\log Z_u+\sum _{n_i\in N_S(u)}f\left(n_i\right)?f(u)?\text{\hspace{1em}(2)}$$
對于每個節點的partition function， $Z_u={\sum }_{v\in V}\exp (f(u)?f(v))$對于大型網絡的計算代價是非常大的，因此，我們采用負采樣。采用隨機梯度法優化Eq.2中的模型參數。

在文本中，基于連續的文字序列，通過window size定義它們的鄰居。在網絡中，采用隨機策略生成source節點的不同的鄰居，他們的鄰居節點依賴于抽樣策略$S$。

2.node2vec

基于BFS和DFS， 我們設計兩者之間平滑的抽樣策略。

2.1 Random Walks

設隨機游走的長度$l$, $c_i$是游走的第$i$個節點， 起始節點$c_0=u$。節點$c_i$通過以下方式產生：
$$P\left(c_i=x\mid c_{i?1}=v\right)=\{\begin{array}{ll}\frac{{\pi }_{vx}}{Z}& \text{?if?}(v,x)\in E\\ 0& \text{?otherwise?}\end{array}$$
${\pi }_{vx}$是 節點v和節點x之間非標準化的轉移概率， $Z$是用于標準化的常數。

2.2 Search bias $\alpha$

最簡單直接的隨機游走方式是基于邊的權重$w_{vx}$進行下一個節點的抽樣。例如：${\pi }_{vx}=w_{vx}$。（對于無權圖$w_{vx}=1$）。但是，這種情況沒有考慮到網絡的結構，不能進行不同形式鄰居節點的探查。BFS和DFS分別適合結構等價和同質的網絡的極端采樣范式?，F實多是兩種情況的融合，我們的隨機游走對兩者作出平衡。

根據$p$和$q$我們定義$2^{nd}$階的隨機游走，$p$和$q$引導游走的方式：假設剛游走過一條邊$(t,v)$, 現在處于節點$v$，（Figure 2）。現在基于邊$(v,x)$, 決定下一步游走的轉移概率${\pi }_{vx}$。我們設未標準化的轉移概率${\pi }_{vx}={\alpha }_{pq}(t,x)?w_{vx}$，其中：
$${\alpha }_{pq}(t,x)=?\begin{array}{ll}\frac{1}{p}& \text{?if?}{d}_{tx}=0\\ 1& \text{?if?}{d}_{tx}=1\\ \frac{1}{q}& \text{?if?}{d}_{tx}=2\end{array}$$
$d_{tx}$是節點$t$和節點$x$之間的最短路徑。$d_{tx}$是集合$\{0,1,2\}$中的一個。兩個參數對于引導游走的方式是非常必要的。

直觀上，參數$p$和參數$q$是用來控制離開起始節點$u$鄰域的速度。特別的，這些參數允許我們的搜索過程在BFS和DFS之間進行插值，從而反映對不同節點的親和力。

Return parameter $p$

參數$p$控制在游走的過程中，折返（ revisiting）訪問節點可能性。如果將其設置一個較高的值$(>\max (q,1))$，采樣到已經訪問過節點的概率是非常小的（除非下一個節點沒有鄰居節點）。這個策略鼓勵新的探索，避免重復過去無效2-hop。另一方面，如果$p$比較小$(<\min (q,1))$，它將會導致游走的回溯(Figure 2), 將會導致在節點$u$附近進行local walk。

In-out parameter $q$

參數$q$控制“inward”和“outward”的參數。如Figure 2，如果$q>1$, 隨機游走偏向節點$t$。這個游走獲得起始節點的局部視圖，類似BFS，獲取都是局部樣本點。

如果$q<1$, 游走會遠離節點$t$, 進行更深層次訪問。這種行為類似DFS探索。與DFS不同的是，我們基于隨機游走的框架實現類似DFS探索。給定樣本點$u$, 抽樣的樣本不是嚴格遵循DFS的distance 遞增過程，但是采樣的效率是非常高的且易于處理。設${\pi }_{v,x}$是在$t$時刻， 當前進行節點的函數，它們的隨機游走符合馬爾科夫性。

Benefits of random walks

在時間和空間復雜度方面，相對于 BFS和DFS, 隨機游走的計算非常高效的。在空間復雜度方面， 存儲節點鄰居$O|E|$. 在$2^{nd}$隨機游走過程中，存儲鄰居間的交互，它們的空間復雜度是$O(a^2|V|)$, 其中$a$是圖平均度。在時間復雜度方面，通過在樣本生成過程施加圖連接，隨機游走一種方便的機制，通過跨不同源節點重用樣本來提高采樣的效率。假設模擬$l>k$隨機游走， 由于馬爾可夫性， 我們可以為$l?k$個節點一次產生$k$個樣本。因此，每個樣本的復雜度為$O(\frac{l}{k(l?k)})$。舉例來說，我們隨機游走$l=6$, 序列為$\{u,s_4,s_5,s_6,s_8,s_9\}$, 會產生如下: $N_S(u)=\left\{s_4,s_5,s_6\right\}$，$N_S\left(s_4\right)=\left\{s_5,s_6,s_8\right\}$和$N_S(s_5)=\{s_6,s_8,s_9\}$。需要注意的是：重用樣本在整個過程中會引入偏差，但效率大大提高。

2.3 The node2vec algorithm

Algorithm 1是node2vec的偽代碼，由于起始節點$u$的選擇, 在隨機游走過程中，會存在隱含的偏差。因為我們要學習所有節點的表示，我們將每個節點作為起始節點，隨機游走固定的長度$l$, 游走$r$次。每一步的游走基于轉移概率${\pi }_{vx}$。對于二階馬爾科夫轉移概率${\pi }_{vx}$可以事先計算。因此，對于節點的采樣可以在$O(1)$時間內完成。node2vec可以分為3個階段：轉移概率預計算、隨機游走序列生成、SGD優化，三個過程串聯進行。每個階段可以并行、異步執行，對全局進行優化。

3 Learning edge features

node2vec提供半監督的方式學習節點特征表示。然而，相對個體節點，我們通常對節點對的預測任務更加感興趣。例如，在鏈路預測任務中，判斷兩個節點是否存在邊。因為隨機游走自然地學習到網絡節點之間的連接性。我們基于個體節點的特征表示，使用bootstrapping的方法，可以學習節點對之間的關系。

考慮兩個節點$u$和$v$， 我們基于特征向量$f(u)$和$f(v)$定義二值算子$°$，用于計算表征向量$g(u,v)$, $g:V\times V\to {\mathbb{R}}^{d^{\prime }}$, 其中，$d^{\prime }$是節點對$(u,v)$表征大小。我們想讓我們的算子對任何算子定義有效，即使節點之間的邊不存在。這樣做是方便鏈路預測。我們的測試數據包含真假邊。我們考慮幾種算子$°$, 使得$d^{\prime }=d$, 總結在Table 1中。

總結

以上是生活随笔為你收集整理的Node2Vec的全部內容，希望文章能夠幫你解決所遇到的問題。

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