網路嵌入(1) DeepWalk

10-11

網路嵌入(1) DeepWalk

來自專欄每周一篇機器學習論文筆記6 人贊了文章

論文名稱：DeepWalk: Online Learning of Social Representations

本文是第一個將NLP中的思想用在網路嵌入(Network Embedding,NE)上的。

Introduction

文章簡介部分介紹了網路嵌入是什麼，以社交網路為例，網路嵌入就是將網路中的點用一個低維的向量表示，並且這些向量要能反應原先網路的某些特性，比如如果在原網路中兩個點的結構類似，那麼這兩個點表示成的向量也應該類似。

本文提出了一種網路嵌入的方法叫DeepWalk，它的輸入是一張圖或者網路，輸出為網路中頂點的向量表示。DeepWalk通過截斷隨機遊走(truncated random walk)學習出一個網路的社會表示(social representation)，在網路標註頂點很少的情況也能得到比較好的效果。並且該方法還具有可擴展的優點，能夠適應網路的變化。

Problem Definition

圖G定義如下，由頂點集V和邊集E組成：

如果在圖G的基礎上再加上頂點的向量表示和頂點所屬的標註（網路節點分類問題中，網路中的每個頂點都有一個類別，所屬的類別即為該頂點的標註）就構成了一個標註圖(labeled graph)。頂點的表示X是一個|V|×s維的矩陣，|V|表示頂點的數量，s是代表每個頂點的向量的維數（一般比較小），所以X即為將每個頂點的向量結合在一起形成的矩陣。Y則是每個頂點的標註構成的矩陣。

Learning social representations

文中提到，在學習一個網路表示的時候需要注意的幾個性質：

適應性，網路表示必須能適應網路的變化。網路是一個動態的圖，不斷地會有新的節點和邊添加進來，網路表示需要適應網路的正常演化。
屬於同一個社區的節點有著類似的表示。網路中往往會出現一些特徵相似的點構成的團狀結構，這些節點表示成向量後必須相似。
低維。代表每個頂點的向量維數不能過高，過高會有過擬合的風險，對網路中有缺失數據的情況處理能力較差。
連續性。低維的向量應該是連續的。

提到網路嵌入，可能會讓人聯想到NLP中的word2vec，也就是詞嵌入(word embedding)。前者是將網路中的節點用向量表示，後者是將單詞用向量表示。因為大多數機器學習的方法的輸入往往都是一個向量，演算法也都基於對向量的處理，從而將不能直接處理的東西轉化成向量表示，這樣就能利用機器學習的方法對其分析，這是一種很自然的思想。

本文處理網路節點的表示(node representation)就是利用了詞嵌入（詞向量）的的思想。詞嵌入的基本處理元素是單詞，對應網路網路節點的表示的處理元素是網路節點；詞嵌入是對構成一個句子中單詞序列進行分析，那麼網路節點的表示中節點構成的序列就是隨機遊走。

所謂隨機遊走(random walk)，就是在網路上不斷重複地隨機選擇遊走路徑，最終形成一條貫穿網路的路徑。從某個特定的端點開始，遊走的每一步都從與當前節點相連的邊中隨機選擇一條，沿著選定的邊移動到下一個頂點，不斷重複這個過程。下圖所示綠色部分即為一條隨機遊走。

關於隨機遊走的符號解釋：以 $v_i$ 為根節點生成的一條隨機遊走路徑（綠色）為 $W_{v_i}$ ，其中路徑上的點（藍色）分別標記為 $W^1_{v_i},W^2_{v_i},W^3_{v_i}$ …，截斷隨機遊走(truncated random walk)實際上就是長度固定的隨機遊走。

使用隨機遊走有兩個好處：

並行化，隨機遊走是局部的，對於一個大的網路來說，可以同時在不同的頂點開始進行一定長度的隨機遊走，多個隨機遊走同時進行，可以減少採樣的時間。
適應性，可以適應網路局部的變化。網路的演化通常是局部的點和邊的變化，這樣的變化只會對部分隨機遊走路徑產生影響，因此在網路的演化過程中不需要每一次都重新計算整個網路的隨機遊走。

文中提到網路中隨機遊走的分布規律與NLP中句子序列在語料庫中出現的規律有著類似的冪律分布特徵。那麼既然網路的特性與自然語言處理中的特性十分類似，那麼就可以將NLP中詞向量的模型用在網路表示中，這正是本文所做的工作。

首先來看詞向量模型：

$w^u_i = (w_0,w_1,w_2,…,w_n)$ 是一個由若干單片語成的序列，其中 $w_i∈V(Vocabulary)，V$ 是辭彙表，也就是所有單片語成的集合。

在整個訓練集上需要優化的目標是：

$Pr(w_n|w_0,w_1,…,w_n-1)$

比如下面的單片語成的序列：

優化目標就是 $Pr(w_3|w_0,w_1,w_2)$ ，意思就是當知道I like studying後，下一個詞是English的概率為多少？

如果將單詞對應成網路中的節點 $v_i$ ，句子序列對應成網路的隨機遊走，那麼對於一個隨機遊走 $(v_0,v_1,…,v_i)$ 要優化的目標就是：

$Pr(v_i|(v_0,v_1,…,v_{i-1}))$

按照上面的理解就是，當知道 $(v_0,v_1,…,v_{i-1})$ 遊走路徑後，遊走的下一個節點是 $v_i$ 的概率是多少？可是這裡的 $v_i$ 是頂點本身沒法計算，於是引入一個映射函數??，它的功能是將頂點映射成向量（這其實就是我們要求的），轉化成向量後就可以對頂點 $v_i$ 進行計算了。

映射函數??對網路中每一個節點映射成d維向量，??實際上是一個矩陣，總共有|V|×d個參數，這些參數就是需要學習的。

有了??之後， $??(v_i)$ 就是一個可以計算的向量了，這時原先的優化目標可以寫成：

$Pr(v_i|(??(v_0),??(v_1),…,??({v_i-1})))$

但是怎麼計算這個概率呢？同樣借用詞向量中使用的skip-gram模型

skip-gram模型有這樣3個特點：

不使用上下文（context）預測缺失詞（missing word），而使用缺失詞預測上下文。因為 $(??(v_0),??(v_1),…,??({v_i-1}))$ 這部分太難算了，但是如果只計算一個 $??(v_k)$ ，其中 $v_k$ 是缺失詞，這就很好算。
同時考慮左邊窗口和右邊窗口。下圖中橘黃色部分，對於 $v_4$ 同時考慮左邊的2個窗口內的節點和右邊2個窗口內的節點。
不考慮順序，只要是窗口中出現的詞都算進來，而不管它具體出現在窗口的哪個位置。