網路結構中節點嵌入向量表達（network embedding）方法介紹

01-29

轉載請註明出處：8層會議室 - 知乎專欄
原文鏈接：網路結構中節點嵌入向量表達（network embedding）方法介紹

引言

在自然語言處理、文本挖掘中，常常使用詞向量作為單詞（Word）內在含義的表達，從傳統的向量表達到近幾年的詞嵌入（Word Embedding）表達，詞向量已經作為一種文本的常用特徵得到廣泛應用。類似的，一些研究者希望通過網路結構中的連接關係，得到網路中頂點（vertex）的向量表示，作為基本特徵應用到聚類、分類等任務上。

最近在研究圖片搜索中關於query和site的關係時，希望能通過它們的連接關係得到embedding向量作為特徵。

本文總結了5種近幾年常用的將網路結構中節點轉化為嵌入向量的方法，不同研究者對這一問題的命名有出入，如node2vector，graph representation，network embedding等，但實質上是同一個問題。接下來本文對deepwalk、line、DNGR、SDNE、node2vector五種方法分別做介紹。

nnnn

Deepwalk

Deepwalk模型源於論文《DeepWalk: Online Learning of SocialnRepresentations》，Deepwalk的思想非常簡單，主要借鑒了word2vec，將網路結構通過Random walk的方式，轉換為類似「sentence」的節點序列的形式。

Word2Vec是Mikolov帶領Google研發的用來產生詞嵌入表達的模型，其中又包括skip-grams 或continuous-bag-of-words（CBOW）兩種方式。Word2Vec相關介紹很多，本文不再贅述。

在deepwalk的這篇論文中，為了說明網路結構中的節點和文本中的詞具有可比性，作者根據對社交網路的圖和Wikipedia中的文本進行分別統計，發現都遵循zipfs定律，說明詞和經過Random walk後圖的節點，具有相似的特性。如下圖所示：

將網路結構轉化為「sentence」序列後，以通過word2vec中的Skip-gram模型或者CBOW模型，訓練得到每個節點的向量表示形式，進而可以用餘弦距離或者歐式距離來求得兩個節點之間的相似度。這篇論文採用了Skip-gram模型。

nn Deepwalk演算法描述，見下圖。對圖G，隨機採樣1個節點v，然後以此為起點連續採樣，直到達到最大路徑長度t，再通過Skip-gram來更新參數。

Deepwalk實現很簡單，在網路結構上主要考慮節點間是否存在連接的邊，但是效果穩定，在評測數據上取得了很不錯的效果，且代碼健壯。在應用上deepwalk支持directed/undirected網路，原始代碼不支持帶權重的網路結構。

nn Deepwalk工具包地址：phanein/deepwalk

LINE

LINE模型源於論文《LINE:nLarge-scale Information Network Embedding》，這篇文章提出了兩個規則（order），我們通過文中的示例來具體理解這兩種規則。如下圖所示網路：

在這個網路結構中，對5、6、7三個節點而言，根據first-order來說6、7節點更相似，因為它們有一條直接相連的邊；根據second-order來說5、6節點更相似，因為它們有四個公共鄰居節點。根據這兩種計算相似性的規則，論文作者相應的提出了兩種訓練節點向量的演算法。

nn First-order：這種方法主要考慮兩個節點間的沒有方向(undirected)的邊<i , j>，用 $mu$ 表示節點向量，那麼可以用下面的式子計算節點vi和vj的聯合概率：

根據經驗，在網路結構中vi和vj聯合分布的經驗概率可以表示為 $tilde{ p_1} (i,j)= w_{i,j} /W$ ，其中 $W= sum_{(i,j)in E}^{}{w_{i,j} }$ ，模型的目標函數就是希望優化兩種聯合概率的距離：

其中函數d表示兩種分布的「距離」，論文中選用了KL散度來衡量。此時，目標函數轉化為

Second-order：由於第二規則著重考慮鄰居節點對中心節點的表達，類似於文本中上下文對中心詞的表達，上下文一致時兩個中心詞就極有可能相似，因此在第二規則中對有向(directed)邊<i , j>，定義了節點間的生成概率：

根據經驗，我們可以知道節點i生成節點j的概率為 $tilde{ p_1} (x_{j} |v_{i})= w_{i,j} /d_{i}$ ，其中 $d_{i} = sum_{kin N_{i} }^{}{w_{i,k} }$ ，表示節點i指向所有邊的權重和。那麼模型的目標函數如下：

同樣適用KL散度定義距離，且使 $lambda _{i} =d_{i}$ ，消去常數項，可以使目標函數轉化為：

在Second-order的目標生成概率函數中可以發現，當需要計算節點i到節點j的轉移概率時，需要計算所有和節點i相鄰節點的內積，這樣明顯會極大增加求解過程中的計算量。論文作者採用負採樣（negative sampling）的方法對生成概率進行替換，如下面式子所示：

其中 $sigma$ 是sigmoid函數，K是負採樣的樣本個數。Pn是一個表示負樣本分布的參數，具體可參看論文。

發散思考：

本文作者在這兩種方法的基礎上，提出了一些具體問題上進行討論。第一個問題是網路節點中低維度節點應該怎樣訓練？

低維度節點指的是某些節點的「鄰居節點」太少，這樣可供其採集的樣本就很少。在這些節點上學習到的特徵就很弱。為了增加其信息的豐富性，作者嘗試使用構建鄰接邊的方式豐富網路結構，主要思想是假如存在臨邊<i, k> 、<k, j>，那麼就可以確定出<I, j>的權重。公式如下：

第二個問題是針對一個網路結構訓練完畢後，如何添加入新的節點？

nn 這是一個應用性很強的問題，其本質是要考慮如何不重新整合全局信息而得到新加入節點在這個空間維度的向量表達。在Word2Vec中就可以實現在訓練結果的基礎上，加入新的預料繼續優化。在這裡，作者提出了一個簡單的優化目標，在不改變原始網路中節點向量的基礎上，根據新節點的連接關係對新節點進行優化。兩種規則的優化目標函數如下：

兩個目標函數較易理解，不再贅述。

除了以上兩個問題，作者還對這兩種向量的結合問題做了思考。畢竟這兩種方法都挺不錯，如果能結合起來學出來一套綜合的向量按理說效果應該更好啊。不過很遺憾的是由於這兩個方法的出發點不一樣，很難把兩種演算法結合起來學習。但是卻有一種簡單粗暴的方法，就是使用兩種規則分別訓練，最後直接把兩個向量拼接起來。效果在具體任務上見仁見智吧，我在自己的任務上試驗過，反而比單獨的效果還差一點，也是很不解。有興趣的童鞋可以再研究研究，沒準就能搞一篇不錯的論文出來。

LINE工具包：tangjianpku/LINE

Node2Vector

Node2Vector演算法源於論文《node2vec:nScalable Feature Learning for Networks》，這篇論文可以看作是deepwalk的升級版。

整體上來看，Node2Vector在deepwalk的基礎上改變了節點遊走的方式，考慮了更多的信息，deepwalk在下一個節點的選擇上只是對當前節點的所有鄰居節點中random選擇一個，而本文方法就更複雜些，在一些評測上也取得了更好的效果。下面就具體看一下Node2Vec的實現方法。

nnnn 論文作者首先提出了網路節點間遊走（採樣）的兩種方式：Breadth-first Sampling（BFS）和Depth-first Sampling（DFS），其實有點類似常說的廣搜和深搜。我們用論文中的一張圖來說明這兩種採樣方式：

相信上面這張圖已經直觀的解釋了BFS和DFS，不再細說。這兩種採樣方式風格不同，但各有千秋，都挺符合我們的認知，論文作者覺得應該把兩種採樣方式結合起來啊，這樣豈不是很牛逼？但是怎樣結合是一個大問題。

不著急，我們先來看下面這個圖，這是作者論文中的一張圖：

這種圖充分說明論文作者如何將兩種遊走方式結合起來的。在deepwalk中，一條walk序列從t節點走到v節點，接下來往哪裡走呢？就是從{t, x1, x2, x3}隨機選一個，然後依次類推的往下走。但在Node2Vector中作者將四個節點共分為3類{t}、{x1}、{x2, x3}，對當前節點（cur_node）來說，節點t的上一個節點（pre_node），x1是cur_node和pre_node同時連接的節點，{x2, x3}是其他鄰居節點。我們還可以將這三類節點按照DFS和BFS的理論去分析，比如再往想x1/ x2/ x3走就是DFS，往x1/ t走就是BFS，總而言之這些都可以算是物理意義上的解釋吧。

nn 為了實現這種結合的遊走方式，作者定義了p、q兩個參數，將這三類節點的概率值分別定義為1/p、1、1/q，參數p、q是作為參數傳入的。根據網路結構的不同特點，可以調整p、q來實現對不同採樣方式的偏愛。如下圖所示：

到這裡，針對節點t來說，我們得到了t能轉移到不同類別節點的概率，常規做法是歸一化之後按照概率隨機選取，但這篇論文並沒有直接這樣做，而是選用了Alias演算法進行抽樣。Alias演算法相比較於直接抽樣方法效率上要高一些，效果上見仁見智，這裡不再具體介紹。

此時，我們就可以得到節點序列，已經完成了整個演算法的核心部分，因為接下來就是直接用word2vec對節點序列進行訓練（對，就是這麼任性）就好了。

另外，值得一提的是，由於在next_node的選擇上需要<pre_node,ncur_node>兩個節點的信息，因此在初始的轉移概率空間複雜度上就是deepwalk的平方。當節點個數較多的時候可能出現out of memory。

當然，也由於這種遊走方式的複雜性，在網路節點的個數較少時，node2vec的效果整體上要優於deepwalk，但在節點多到可能影響空間限制時，deepwalk效果更優。

Node2vec源碼：aditya-grover/node2vec

SDNE

SNDE方法源於論文《StructuralnDeep Network Embedding》，這篇論文從Auto-encoder方法上進行改進，從而實現對網路節點的embedding。

nn Auto-encoder方法，簡單來說可以算是一種降維的方法，在圖片應用上比較多，將原始的高維向量在儘可能避免信息丟失的情況下降維得到目標維度的向量。Auto-encoder的網路結構大致如下：

Auto-encoder演算法主要達到的是一個「降維」的目的，並不能學習出表示節點關係的embedding表達。在這篇論文中，作者通過在訓練過程中加入節點信息使得學習出的向量能過表示出節點的內在關係。

nn 接下來我們來詳細介紹下SDNE，先給出下面這幅圖，描述了整個SDNE的網路結構：

第一步，我們來了解下Auto-encoder，就是上圖中的左邊部分，給定一個原始的出入向量xi，可以得到：

通過decoder的過程，我們可以得到最終輸出 $tilde{x}$ ，目標函數是最小化輸入和輸出的誤差：

第二步，對Auto-encoder演算法加入懲罰因子。在圖片的自編碼中，由於原始輸入的每一維度都不為0，但是在網路結構中，我們將節點i和其他節點的關係（0、1關係/權重關係）作為該節點的原始輸入。對一些節點多、連接少的網路結構而言，原始輸入十分稀疏，這會導致encode/decode後的向量更趨向零向量。因此將目標函數改為如下：

其中 $odot$ 表示Hadamard乘法， $b_i={left{ b_{i,j} right} x_{j=1}^{n}}$ ，如果 $x_{i,j} =0$ ，則 $b_{i,j} =1$ ，否則 $b_{i,j} =beta >1$ 。

第三步，學習節點間的關係信息。這是這篇論文在Auto-encoder較大的改進應用。作者認為兩個節點直接相連的時候，那麼最終的短處向量y就應該更相似。基於這個目標，能夠得到如下圖所示的loss函數；

其中y就是我們需要的固定維度的最終向量。

最終，基於以上這些，作者給出了最終的目標函數：

前兩項在在上面已經解釋過，最後一項是個正則化項防止過擬合，定義如下：

關於求解過程不再具體闡述。以上就是SDNE的模型框架。

DNGR：

NDGR演算法來源於論文《DeepnNeural Networks for Learning Graph Representations》，這篇論文和SDNE演算法有異曲同工之妙，都應用了auto-encoder，但在如何學習節點間連接信息的方法上卻另闢蹊徑。

SDNE為了學習到鄰接節點的相似信息，在目標函數中加入中間結果的loss函數（具體見上文），而本文則根據鄰接信息改變每個節點的原始表達，作為自編碼模型的輸入。由於輸入向量本身就含有網路連接信息，因此經過「壓縮」後的向量也能表達節點關係。具體我們一步步來介紹。

第一步，通過random surfing模型得到概率共現矩陣。作者認為將網路節點轉化為序列可能存在一些問題，比如序列長度，採樣次數，這些都不好確定。根據PageRank演算法的啟發，作者希望通過概率轉移矩陣/鄰接矩陣A學習到網路結構信息。由於步驟較為簡單且便於理解，此處直接通過matlab代碼來說明:

其中A是原始鄰接/概率轉移矩陣，alpha是平滑參數，決定節點是否需要轉移。P0和M矩陣初始分別是單位矩陣和全0矩陣，M是最終產出結果。ScaleSimMat是對矩陣進行主對角線置0後，對每列進行歸一化。

第二步是得到PPMI矩陣，對上步得到的矩陣進行處理。其中PMI(pointwise mutual information)定義如下：

在PMI的基礎上，對值為負的元素，全部置為0，得到PPMI矩陣。

第三步是進行自編碼，論文作者使用了SDAE(stacked denoising autoencoders)編碼。SDAE和AE的差距不大，主要區別是在訓練之前對input向量進行了容錯處理，具體做法是按照一定的方式對input向量中的少部分元素置0，這樣可以在某種程度上對輸入向量的依賴程度，提高整體的學習效果。具體encode/decode的過程和AE基本一致，可以在SDNE方法中看到。

DNGR方法在編碼之前，通過轉移矩陣學習到節點間的連接信息，和SDNE有共通之處。但在實際應用過程中卻會遇到很多問題，可以在上列步驟中看到需要進行矩陣運算，當網路節點很多時，就要面臨大型矩陣的運算問題，需要單獨將矩陣運算部分拿出來，利用Hadoop等方式運算（主要是大型矩陣的存儲）。筆者嘗試一般超過5W節點後基本單機是難以直接實現的，因此在工業實現上還需要具體改進演算法。

DNGR工具包：https://github.com/ShelsonCao/DNGRn（matlab）

MdAsifKhan/DNGR-Keras（python）

小結：

以上五種方法中，整體來說deepwalk和node2vector一脈相承，DNGR和SDNE異曲同工，LINE沒有直接藉助現成的工具，但思想上和前面兩種方法更接近一些。

從效果上來說，deepwalk在大型網路上比小網路上效果要好，源於其完全隨機的遊走方式需要大數據作為基礎，在小型網路上node2vector比deepwalk效果整體好一些。在具體應用上，deepwalk和LINE對大數據的適應性更好，其餘三種方法所附的代碼工具包對大型網路（節點>5W）難以實現，需要通過其他方式改進。