標籤：

網路嵌入(3)node2vec

10-14
網路嵌入(3)node2vec

來自專欄網路嵌入3 人贊了文章

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

node2vec的思想同DeepWalk一樣：生成隨機遊走，對隨機遊走採樣得到（節點，上下文）的組合，然後用處理詞向量的方法對這樣的組合建模得到網路節點的表示。不過在生成隨機遊走過程中做了一些創新。

Introduction

首先介紹了複雜網路面對的幾種任務，一種是網路節點的分類，通俗點說就是將網路中的節點進行聚類，我們關心的是哪些節點具有類似的屬性，就將其分到同一個類別中。另一種是鏈接預測，就是預測網路中哪些頂點有潛在的關聯。

要完成這些任務首先要解決的問題就是網路嵌入，以前的手工提取特徵的方式有著諸多不足。一種替代的提取網路特徵的方法是通過解優化函數的方式學習網路的表示特徵。但是這樣的方法面臨一個計算效率和準確度的平衡問題，無法兼顧兩者。通過將一些傳統的降維方法如PCA應用到網路表示中也確實有一定的效果，缺點是會涉及矩陣分解，運算量大，同時準確率也不高，而且有些方法只是針對特定的任務才有效果。

能否設計出又能保持節點鄰居信息而且又容易訓練的模型呢？這就是本文嘗試解決的工作。我們發現很多節點在網路中往往有一些類似的結構特徵。一種結構特徵是很多節點會聚集在一起，內部的連接遠比外部的連接多，我們稱之為社區。另一種結構特徵是網路中兩個可能相聚很遠的點，在邊的連接上有著類似的特徵。比如下圖， {u,s_1,s_2,s_3,s_4} 就屬於一個社區，而 u,s_6 在結構上有著相似的特徵。

那麼要設計的網路表示學習演算法的目標必須滿足這兩點：

  1. 同一個社區內的節點表示相似。
  2. 擁有類似結構特徵的節點表示相似。

然後就是日常吹一下本文的工作了，總之本文的貢獻就是：提出了一個有效的、可擴展的表示學習演算法，可以體現網路特徵和節點鄰居特徵。

Related Works

之前的工作存在著一些問題：

  • 特徵需要依賴人手工定義，不是某個領域內專業人士無法從事工作，而且依靠人手工定義特徵這件事本身就很懸，就算是領域專家也不能肯定某個提取出來的特徵就一定管用，所以這種方法就很玄學了。
  • 一些非監督學習中的降維方法被拿來使用，但是這些方法計算效率低，準確度也不夠，而且還不能反應出網路的結構特徵。

最近（當時是最近）在NLP中的方法為本文的作者提供了思路，其實跟DeepWalk的想法是一樣的。用skip-gram模型來解決網路表示學習的問題。

Algorithm

一些基本圖的定義，網路映射到向量的形式化定義就不提了，基本上一眼就能看懂的。直接上損失函數，其實跟DeepWalk也是一樣的，只不過換了種表達而已。

max limits_{f} sum_{u∈V}logPr(N_s(u)|f(u))

其中 f(u) 就是當前節點， N_s(u) 就是鄰居節點（以s的方法採樣得到的），為了讓這個結果更容易計算，引入了兩個假設，其實這都是skip-gram模型中的。

第一個假設是條件獨立（Conditional independence），即採樣每個鄰居是相互獨立的，所以如果要計算採樣所有鄰居的概率只需要將採樣每個鄰居的概率相乘就行了，公式化表達就是：

Pr(N_s(u)|f(u))=prod_{n_i∈N_s(u)}Pr(n_i|f(u))

第二個假設是特徵空間的對稱性（Symmetry in feature space），其實也很好理解，比如一條邊連接了a和b，那麼映射到特徵空間時，a對b的影響和b對a的影響應該是一樣的。用一個模型來表示一個（節點，鄰居）對：

Pr(n_i|f(u)) = frac{exp(f(n_i)·f(u))}{sum_{v∈V}exp(f(v)·f(u))}

將上面三個公式結合起來得到最終要優化的結果：

max limits_{f} sum_{u∈V}[-logZ_u + sum_{n_i∈N_s(u)}f(n_i)·f(u)]

推導過程如下：

如果我的推導沒錯的話，推導完後其實是有一個 |N_s(u)| 的係數的（圖中橙色部分），但是這部分沒有在最終的損失和函數中。可能是因為整個這一項 |N_s(u)|logZ_u 都是常數的原因。

注意兩點：

  1. Z_u 直接計算特別費時，本文用Negative Sampling方法解決的。
  2. N_s(u) 未必是u的直接鄰居，只是用s方法採樣得到的鄰居，跟具體的採樣方法有關。

到這裡之前這些公式基本都是NLP中處理詞向量那塊的，現在讓我們把目光放到node2vec中的創新內容。

說到隨機遊走的採樣，本文分析了兩種圖的遊走方式，深度優先遊走（Depth-first Sampling，DFS）和廣度優先遊走（Breadth-first Sampling，BFS），之前的圖中也畫出了兩種遊走的路徑，學過圖論或者數據結構的很好理解。遊走的路徑就是採樣後得到的隨機遊走。

複雜網路處理的任務其實離不開兩種特性，前面也提到過：一種是同質性，就是之前所說的社區。一種就是結構相似性，值得注意的是，結構相似的兩個點未必相連，可以是相距很遠的兩個節點。

BFS傾向於在初始節點的周圍遊走，可以反映出一個節點的鄰居的微觀特性；而DFS一般會跑的離初始節點越來越遠，可以反映出一個節點鄰居的宏觀特性。

鋪墊了這麼多終於到本文的工作了，能不能改進DeepWalk中隨機遊走的方式，使它綜合DFS和BFS的特性呢？所以本文引入了兩個參數用來控制隨機遊走產生的方式。

上圖中，對於一個隨機遊走，如果已經採樣了 (t,v) ，也就是說現在停留在節點v上，那麼下一個要採樣的節點x是哪個？作者定義了一個概率分布，也就是一個節點到它的不同鄰居的轉移概率：

直觀的解釋一下這個分布：

  • 如果t與x相等，那麼採樣x的概率為 frac{1}{p} ；
  • 如果t與x相連，那麼採樣x的概率1；
  • 如果t與x不相連，那麼採樣x概率為 frac{1}{q} 。

參數p、q的意義分別如下：

返回概率p：

  • 如果 p>max(q,1) ，那麼採樣會盡量不往回走，對應上圖的情況，就是下一個節點不太可能是上一個訪問的節點t。
  • 如果 p<min(q,1) ，那麼採樣會更傾向於返回上一個節點，這樣就會一直在起始點周圍某些節點來迴轉來轉去。

出入參數q：

  • 如果 q>1 ，那麼遊走會傾向於在起始點周圍的節點之間跑，可以反映出一個節點的BFS特性。
  • 如果 q<1 ，那麼遊走會傾向於往遠處跑，反映出DFS特性。

當p=1，q=1時，遊走方式就等同於DeepWalk中的隨機遊走。

下面來逐行看看論文中提供的演算法：

首先看一下演算法的參數，圖G、表示向量維度d、每個節點生成的遊走個數r，遊走長度l，上下文的窗口長度k，以及之前提到的p、q參數。

  1. 根據p、q和之前的公式計算一個節點到它的鄰居的轉移概率。
  2. 將這個轉移概率加到圖G中形成G。
  3. walks用來存儲隨機遊走，先初始化為空。
  4. 外循環r次表示每個節點作為初始節點要生成r個隨機遊走。
  5. 然後對圖中每個節點。
  6. 生成一條隨機遊走walk。
  7. 將walk添加到walks中保存。
  8. 然後用SGD的方法對walks進行訓練。

第6步中一條walk的生成方式如下：

  1. 將初始節點u添加進去。
  2. walk的長度為l，因此還要再循環添加l-1個節點。
  3. 當前節點設為walk最後添加的節點。
  4. 找出當前節點的所有鄰居節點。
  5. 根據轉移概率採樣選擇某個鄰居s。
  6. 將該鄰居添加到walk中。

Experiments

下圖是一些實驗結果和可視化效果：

總結

本文其實思想跟DeepWalk是一樣的，不過改進了DeepWalk中隨機遊走的生成方式，使得生成的隨機遊走可以反映深度優先和廣度優先兩種採樣的特性，從而提高網路嵌入的效果。

推薦閱讀：

TAG:計算機視覺 | 計算機網路 | 科技 |