node2vec: Scalable Feature Learning for Networks 閱讀筆記

轉載請註明出處：All Minable團隊的搬磚日常

論文來源：KDD 2016

論文鏈接：http://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf

Abstract

現有的特徵學習方法沒有能夠捕捉到網路連接的多樣性模式，所以作者提出了node2vec演算法,一個學習網路節點連續空間表示的框架。

Introduction

對於網路的表示學習可以有許多用途，例如節點分類（社區挖掘）和連接預測等。

要學習網路特徵，一種學習特徵表達的方法是通過定義目標函數然後解決優化問題。但是現有的技術要不就是需要大量訓練和運算花費，要不就是效果太差。

一個解決的方向是通過局部的鄰居關係來制定目標函數，同時這個目標函數可用隨機梯度下降(SGD)來解決。這樣就不用訓練同時運算快速。

一個靈活的節點表示學習演算法需要具備兩個條件：

1. 能夠將相同網路社區的節點映射到相近的位置

2. 對於扮演相似角色的節點有相似的映射方式

本篇文章的四個主要貢獻：

1. 提出node2vec演算法，基於鄰居留存的特徵學習優化演算法，使用SGD，計算高效，拓展性強

2. 展示了node2vec符合網路科學的原則

3. 基於鄰居留存目標，拓展了node2vec和其他的特徵學習方法，從節點到節點對

4. 在真實數據集上測試了node2vec進行多分類和連接預測的性能

Related work

之前的關於特徵工程的研究，總的來說存在以下問題：

1. 我們需要先人工定義一些特徵出來，然後再進行學習

2. 對於非監督特徵學習，之前大多使用的是譜特徵進行學習，這樣的學習存在計算複雜度高和效果不理想的缺點

3. 對於不同模型下的網路，這些方法往往魯棒性不夠

最近NLP領域的skip-gram演算法給了許多網路特徵表示研究一些相關的啟發：skip-gram大概就是用文本中的一個單詞來預測上下文單詞，並假設每一個單詞都跟它的上下文單詞是相似的。

Algorithm

這篇論文主要是以skip-gram的演算法為基礎的，skip-gram是nlp的一個演算法，大概是用某個單詞求解上下文概率。基於類似的出發點，本文也提出了一個類似的目標函數：

其中， 是節點到特徵表達的映射函數 , 為表達空間維度。 是節點 的網路鄰居，通過鄰居節點採樣方法 採到的。

為了簡化，作者又增加了條件獨立和空間對稱假設，所以有了以下公式：

將上面的公式進行簡化，可得到：

其中， ，至此，最後一個公式就是本次我們要求的目標函數，在實現中，我們使用隨機梯度下降法(SGD)來進行求解。

以下是個人的一些理解，不一定正確：

上述公式介紹了一個從制定目標函數到增加一些假設並簡化目標函數的過程，對於目標函數的理解，大概就是儘可能找到一個映射函數 ，使得映射後鄰居關係保持的概率越大越好。這個就像是NLP中對於一個詞的映射，使得映射後與上下文的關係保持的概率越大越好。

這時就涉及到網路分析與NLP的一個不同，那就是順序性，語料天然具有順序性，而網路沒有，那麼，該如何生成有順序的節點序列成了一個重要的問題。作者的方法是使用隨機遊走策略來生成節點序列，這樣既有順序性，又考慮了節點的鄰居關係。而本文作者所採用的隨機遊走是比較有創新的地方。

隨機遊走

對於隨機遊走，一般的做法是直接用邊的權重來轉化成概率，本文作者在權重之前乘上一個係數 ，從而在一定程度上調節隨機遊走的走向。假設已知遊走路徑已從 ，示意圖如下：

那麼，在本文的隨機遊走中，作者定義了 和 兩個參數變數來調節遊走，現在遊走到節點 ，首先計算其鄰居節點與上一節點 的距離 ，從而得到 :

通過調節參數 和 ，可以控制隨機遊走的方向，兩個極端的方向就是BFS和DFS，也就是一直在節點 旁邊繞或者一直往外面走，這樣就能做到一個比較靈活的調節。

最後貼一波偽代碼：

總結

network embedding是網路分析的一個方向，這幾年出的文章也比較多。作者能夠結合NLP領域的演算法，加以修改並引入到網路分析中，很值得學習，同時提出了自己的隨機遊走策略，值得一讀。

推薦閱讀：