網路嵌入(4)GraRep

10-13

網路嵌入(4)GraRep

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

論文名稱：GraRep: Learning Graph Representations with Global Structural Information

這篇論文的思想與之前幾篇不同，並沒有用隨機遊走+skip-gram模型，而是用矩陣分解（matrix factorization）的方法來解決網路嵌入問題。GraRep可以處理帶權的網路，並且在學習網路表示的過程中會整合網路的全局結構信息。但是由於計算量大，該方法也會特別耗時，因此不能在大型網路中使用。

Introduction

同樣還是先引入網路嵌入的概念，然後介紹了一下DeepWalk，但是作者拋出了一個問題，雖然DeepWalk確實有效果，但是為什麼這麼定義損失函數就可以得出效果呢？損失函數的可解釋性並沒有在DeepWalk論文中被談及。

文中提到skip-gram模型其實就是用來量化兩個節點的k階關係（k-step relationship），所謂k階關係就是兩個頂點可以通過k步相連的關係。skip-gram實際上是將節點之間的這種關係投影到一個平凡子空間（common subspace）中。而本文則是將k階關係投影到獨立的子空間（distict subspace）中。簡單來說就是，skip-gram模型將網路節點表示成向量後，節點的1到k階關係全都綜合反映到這個向量中。而GraRep則選擇將1到k總共k種關係分開，分別形成k個向量，每個向量表示一種關係。

而另一種方法LINE，則是根本無法獲取到k>2的節點關係。作者認為節點之間的k階關係對把握網路的全局特徵非常重要，越高階的關係（也就是k越大）被考慮進來，得到的網路表示結果會越好。

本文的大致思路是通過矩陣分解的（matrix factorization）方法分別學習網路節點的k階關係表示，然後將k個表示結合起來作為最終的表示結果。

日常總結一下貢獻：

可以提取網路全局信息
與DeepWalk、Line等經典的基於Skip-Gram和Negative Sampling的方法不同，GraRep使用矩陣分解來學習節點表示。

Related Work

相關工作中提到了兩類概念：線性序列表示和圖表示

線性序列方法中提到了NLP處理詞向量的兩種方式：一種是nerual embedding一種是matrix fatorization。前者就是DeepWalk借鑒的方法，選擇一個窗口大小，然後對每個單詞和窗口內單詞建模，但是這種方法無法獲取到全局特徵，因為它只考慮了窗口內兩個單詞共同出現的次數。後者就是本文要使用的方法，就是將全局中單詞共同出現的次數形成一個矩陣，然後分解這個矩陣得到每個單詞的表示。

圖表示方法中提到了一些目前將NLP中方法應用到網路表示學習的例子。

GraRep Model

前面說了那麼多廢話終於要看本文做的工作了，首先還是一些圖的概念等等就不說了。鄰接矩陣S也不說了；度矩陣D是一個對角矩陣，分別表示圖中每個頂點的度；那麼可以定義一階轉移概率矩陣（1-step probability transition matrix）A，A中每個元素 $A_{i,j}$ 就是頂點 $v_i$ 在一步之內轉移到 $v_j$ 的概率。A可由D和S計算得到：

$A = D^{-1}S$

A可以看成是一個被放縮的鄰接矩陣，A中每行都被標準化了，每行的加和都等於1。

所謂網路的全局特徵，不過是兩方面：一個是即使兩個節點相聚很遠，他們的關係也要被考慮到。另一個是不同step的關係也要被考慮到，要綜合考慮節點的1階關係到k階關係。

為了證明這一點，用下面幾個圖來做例子：

圖中標為藍色的頂點都是相似的頂點，藍色加粗的邊代表強連接，8張圖分別代表了k=1，2，3，4的情況。為什麼要分別考慮不同的k而不能綜合起來考慮呢？下面這個例子解釋了原因：

如果對於（a）中的A節點，同時考慮k=1，2，那麼等同於將A同時與B、C1、C2、C3、C4連接起來，所形成的就是（b）圖，改變了原來圖的拓撲結構。因此本文的方法是：對k=1學習一個網路表示，這樣能反映節點A與B的關係；再對k=2學習一個網路表示，這樣就能反映節點A和C1、C2、C3、C4的關係，綜合兩者才能反映（a）圖的全局信息。

再回到節點的關係上來，在考慮兩個節點的關係時，如何判斷兩個節點的關聯程度？或者我們再將問題簡化，如果存在一條從節點w到節點c的路徑，那麼這條路徑的概率是多少？將這個概率表示為 $p_k(c|w)$ ，意思是從節點w走k步到達節點c的概率（k步包括節點w和c）。為每 $(w,c)$ 節點對都計算這樣的概率，得到了一個矩陣，稱之為k階轉移概率矩陣。計算公式如下：

$A^k = underbrace{A···A}_{k}$

即 $p_k(c|w) = A^k_{w,c}$ ，其中 $A^k_{w,c}$ 表示矩陣 $A^k$ 中第w行第c列的元素。

對於一個確定的k，現在我們採樣得到了一堆k-step的路徑，這些路徑有起始點（current vertex）和終止點（context vertex），我們將其中從起始點w到終止點c的k-step路徑記作 $(w,c)$ 。那麼要優化的目標就是：對於任意的一個 $(w,c)$ 的組合，最大化這個組合所代表的路徑在圖中的概率，最小化除了這個組合外在圖中的概率。換句話說，對於所有的 $(w,c)$ 組合對，如果 $(w,c)$ 所代表的路徑在圖中，那麼增大它的概率；如果 $(w,c)$ 所代表的路徑不在圖中，那麼減小它的概率。

前方一大波公式預警！！！為了方便我這裡直接放手寫公式了。

本文使用了NCE損失函數來反應這種特性，損失函數的定義是：

對於每個V中的節點w，都計算一次損失函數，最後加在一起。其中每一項是：

這裡雖然叫損失函數，但是結合Negative Sampling中的公式來看，優化的目標應該是最大化這個損失函數。

我們之前說過有兩個優化目標。橙色部分體現了第一個目標，可以將 $sigma (vec w cdot vec c)$ 理解為 $(w,c)$ 出現的概率，那麼對於路徑屬於圖中的節點對 $(w,c)$ ，要最大化其出現的概率，也就是最大化橙色部分。藍色部分體現了第二個目標，對於任取的一個節點c形成的 $(w,c)$ ，要最小化其出現的概率，最小化其出現概率就是最大化 $sigma (- vec w cdot vec c)$ ，λ是負採樣的個數，總共採樣λ個c。然後我們把負採樣的部分單獨拿出來看：

$p_k(V)$ 是網路中節點的概率分布。負採樣部分實際上就是c服從 $p_k(V)$ 分布時 $(w,c)$ 不出現的期望（回顧一下期望怎麼求）。對於隨機採樣的一個節點c，如果正好選到了正確的節點c，那麼對應的就是前一項（紅色）；如果沒有選到c，那麼對應的就是後一項（藍色）。因此對於一個特定的 $(w,c)$ 組合對來說（這裡就要取上個式子的前一項了），損失函數表達如下：

文中提到一個現象：隨著k的增長，w經過k步到達c的概率會逐漸收斂到一個固定值。下面來看看 $p_k(c)$ 怎麼算，意思是任一節點經過k步到達節點c的概率，因此等於所有k步可以到達c的路徑的概率加和。

將 $p_k(c|w)$ 、 $p_k(c)$ 代入之前的式子得到：

既然要最大化損失函數，一種很常規的方法就是對損失函數求導，找出導數為0的點。令 $e=vec w cdot vec c$ ，對 $L_k(w)$ 求偏導並令偏導數為0，即令 $frac{partial L_k}{partial e}=0$ ，推導過程如下：

最終得到：

到這一步就可以解釋我們之前的工作了，所有之前的工作不過是找到這樣一個矩陣Y，它編碼了網路中所有節點相互之間的關係，但是這個矩陣維數很高（|V|×|V|），不能直接用來作為網路的表示。因此要用矩陣分解的方法對Y進行分解，分解後形成的W、C矩陣維數要遠遠小於Y的維度，而這個W矩陣就是網路節點的表示，C矩陣就是上下文節點的表示（我們不關心這個矩陣）：

下面的目標就變成了找到矩陣Y的一個合適分解。為了降低誤差，將矩陣Y中負值全被替換為0，形成一個新的矩陣X：

$X^k_{i,j} = max(Y^k_{i,j},0)$

接下來用SVD方法將矩陣X分解成：

$X^k = U^k Sigma ^k(V^k)^T$

因為最終的網路表示要求是d維的，那麼進一步將X分解為：

$X^k approx X^k_d = U^k_d Sigma ^k_d(V^k_d)^T$

這一步牽涉到矩陣的SVD分解相關知識，相關資料可參考李宏毅線性代數課中SVD分解那節視頻（b站視頻傳送門）。

觀察到最後要將矩陣分解成這種形式： $X^k approx X^k_d = W^kC^k$

那自然想到這麼分解就好了 $W^k=U^k_d (Sigma ^k_d)^{frac{1}{2}}$ 、 $C^k=(Sigma ^k_d)^{frac{1}{2}}{V^k_d}^T$

到這整個演算法部分就介紹完了_(:з」∠)_，下面來對照著文中給出的演算法步驟複習一遍。

演算法分為三步：

計算k階轉移概率矩陣。
對每一個k計算一個網路表示$W^k$，具體計算步驟為：先計算$X^k$，然後將矩陣中負值替換為0，接著用SVD分解的方法分解矩陣得到網路節點表示矩陣$W^k$。
將不同的$W^k$結合起來作為最終的網路表示。

總結

這篇論文其實還是挺需要花時間的，我也是參閱了好幾篇論文中的參考文獻才基本摸清楚思路，而且還需要理解NLP中詞向量的幾種模型。總之，從矩陣分解的角度也是解決網路嵌入問題的一種新方式。後面還會遇到不少使用這種方法的論文。文中還提到了一種E-SGNS的方法來解決帶權圖的表示，但是我並沒有搞懂為啥這種方法就能解決帶權圖呢？