node2vec: Scalable Feature Learning for Networks文章閱讀

08-22

來自專欄我的ai之路5 人贊了文章

Theme:

提出了一種node2vec的演算法，用於學習網路結點的連續特徵表達，在這個演算法中，學習了一種結點映射到低維特徵空間，同時最大限度的保留網路里結點的鄰域(neighborhoods)。定義網路的結點鄰域並涉及了一種(biased)偏置的隨機遊走過程。
許多網路分析的工作主要涉及結點(nodes)和邊(edges)的預測。典型的結點分類的任務，一般預測結點在網路中最可能的標籤。
同樣的，在連接(link)預測中，我們希望預測在一個網路中的一對結點，是否需要有一個邊來連接它們。
在網路預測的問題當中，需要建立結點和邊的特徵向量的表示。一個典型的方法就是專家知識，但是這種方式的泛化能力不強；另一種方法就是通過解決優化問題來學(learn)特徵表示：而問題就在特徵學習的問題是定義一個目標函數，(1) 如果採用特徵圖譜的方式(spectrum)的方式，是一種監督學習的方式，可以直接找到特徵表達的方式，但是計算量隨參數的增加而增大；(2) 如果定義的目標函數與後面的預測任務獨立開，特徵表達就是一種無監督方式構建。(文章就是採用(2))。
4(2)中典型的降維的方法是通過優化目標函數，將一個網路表達式進行轉換。但是真實世界網路中數據矩陣的特徵分解特別費時，同時也會產生潛在表達。
我們設計了一個目標函數，用來保留結點的局部鄰域。通過隨機梯度下降來優化目標函數，相當於反向傳播只有一層隱藏層的神經網路。
最近朝著6方法的研究中，提出了一種有效的演算法，但是這個演算法依賴於嚴格的網路鄰域的定義，所以使這些方法對網路特有的連接性模式不敏感。用下圖闡釋：

網路中的結點可以根據結點屬於的社區來構建；另一種情況，構建也可以基於結點在網路中的結構角色。

例如，Figure 1中，結點 $u$ 和 $s_1$ 屬於一個緊密社區，而結點 $u$ 和 $s_6$ 屬於兩個不同社區里的結點，同時在社區處於同樣的結構角色（它們都是各個社區的中心結點）。

當前工作：

提出了node2vec的半監督演算法用於網路中的特徵學習，損失函數是一個自定義基於圖(custom graph-based)的目標損失函數，通過SGD來優化。d維的特徵空間，最大化的保留特徵空間中網路結點的鄰居結點，使用2階隨機遊走方式來產生（或稱為取樣）網路結點的鄰居結點。
主要的貢獻：定義了結點在網路中鄰居結點。（1）給定一個結點，通過node2vec的隨機遊走，構建結點在網路中的角色(roles)以及結點所屬的community，同時，尋找該結點的鄰居結點。（2）根據單個結點的表示(representation)，擴展至成對結點的表示，也就是邊的表示。通過二值運算將已知的單個結點的表示組合起來形成邊的表示形式。

實驗部分：

兩個預測任務：

多標記的分類任務：每個結點有一個或多個標籤；
連接的預測(link prediction)任務：給定一組結點，預測是否有邊存在。

文章解析

3. Feature learning framework

$G=(V,E)$ 表示一個給定的網路，該網路適用於所有有向或無向，有權值或無權值的情況。用 $f:V o R^d$ 表示結點到特徵表達的映射， $d$ 是特徵空間的維度。對於每一個結點 $uin V$ 定義 $N_S(u)subset V$ 是結點 $u$ 的網路鄰居， $S$ 是鄰居採樣策略。 $f(u)$ 是結點 $u$ 的特徵。提出目標函數：

$max_fsum_{uin V}logPr(N_S(u)|f(u))quad (1)$

在存在特徵表達 $f$ 的條件下，最大化發現網路鄰居 $N_S(u)$ 的 $log$ 概率。為了讓優化問題易於求解，給出了兩個標準的假設：

條件獨立性：假設給定了一個源結點的特徵表達後，發現一個該源結點的鄰居結點與發現該鄰居結點的其他結點的概率相互獨立。於是，我們可以將概率進行因式分解：其中 $N_S(u)$ 是源結點 $u$ 的鄰居結點。

$P_r(N_S(u)|f(u))=prod_{n_iin N_S(u)}Pr(n_i|f(u))$

2. 特徵空間的對稱性：一個源結點與它的鄰居結點在特徵空間內有對稱性。定義每一對源結點與其鄰居結點的條件概率作為一個softmax單元，且用它們的特徵做點乘進行參數化(構造softmax層)：

$P_r(n_i|f(u))=frac{exp(f(n_i)cdot f(u))}{sum_{vin V}exp(f(v)cdot f(u))}$

3. (1)式變形成：

$max_fsum_{uin V}[-logZ_u+sum_{n_iin N_S(u)}f(n_i)cdot f(u)]quad (2)$

每個結點分配的函數：

$Z_u=sum_{vin V}exp(f(u)cdot f(v))$ 使用Distributed representations of words and phrases

and their compositionality. In NIPS, 2013.的文章提出的方法來近似（還沒看），使用隨機梯度下降SGD，來優化（2）式。

3.1 Classic search strategies

我們將該已知結點進行鄰居的採樣問題視為一種局部搜索。如圖1所示，已知一個源結點 $u$ ，來採樣這個源結點的鄰居結點集合 $N_S(u)$ 。將鄰居結點集合 $N_S$ 採樣的結點個數固定為 $k$ 個，對一個源結點 $u$ 採樣獲取多個鄰居結點集合。一般有兩種採樣策略用來產生 $k$ 個鄰居結點集合 $N_S$ ：

廣度優先取樣(BFS)：直接與源結點相連接的結點作為源結點的鄰居結點 $N_S$ 。例如Fig 1中，如果 $k=3$ ，BFS取樣 $u$ 的鄰居結點是 $s_1,s_2,s_3$ 。

深度優先取樣(DFS)：採樣的鄰居結點與源結點的距離不斷的增加，例如用DFS取樣後的結點是 $s_4,s_5,s_6$ 。

一般網路結點的預測任務會有兩種狀態：1. 同質性（homophily）；2. 結構等價性（structural equivalence）。

對於第一種homophily而言的結點，處於高度連通狀態，屬於相似的網路聚類或緊密嵌入(embedded)的社區，例如Fig 1中的結點 $s_1$ 和 $u$ 屬於同一個網路社區；與之相反的第二種情況，在結構等價性下的結點，有相似結構角色(role)的結點應該緊密的嵌入在一起，例如Fig 1中的結點 $u$ 和 $s_6$ 視為它們所應的社區的中心(hub)。重要的是，與homophily不同的是，結構等價性不強調連通性。結點可以與網路離得很遠，但仍然有相同的結構角色。

3.2 node2vec

3.2.1 隨機遊走(random walks)

給定一個源結點 $u$ ，隨機遊走固定長度 $l$ ， $c_i$ 表示遊走過程當中的第 $i$ 個結點，遊走的起點是 $c_0=u$ 。結點 $c_i$ 通過下面的分布產生：

$P(c_i=x|c_{i-1}=v)=egin{cases} frac{pi_{vx}}{Z}, & ext{if $(v,x)in E$ } \ 0 , & ext{otherwise} end{cases}$

$pi_{vx}$ 是結點 $v$ 和 $x$ 之間的轉移概率。

3.2.2 尋找偏置 $alpha$

定義二階隨機遊走：

假定一個隨機遊走，剛剛遍歷了邊 $(t,v)$ ，並且現在停留在結點 $v$ （Fig 2所示）。該遊走現在需要決定下一步，這樣可以估計從 $v$ 出發的邊到下一結點 $x$ 的邊，也就是 $(v,x)$ 上的轉移概率，設為 $pi_{vx}=alpha_{pq}(t,x)cdot omega_{vx}$ 。其中， $omega_{vx}$ 是邊的權重。同時， $alpha_{pq}(t,x)$ 滿足：

$alpha_{pq}(t,x)=egin{cases} frac{1}{p}, & ext{if $d_{tx}=0$ } \ 1, & ext{if $d_{tx}=1$}\ frac{1}{q}, & ext{if $d_{tx}=2$} end{cases}$

$d_{tx}$ 表示結點 $t$ 和結點 $x$ 之間的最短路徑，注意 $d_{tx}$ 必須是 ${0,1,2}$ 中的其中一個。參數 $p$ 和 $q$ 用來控制遊走的速度和距離初始結點 $u$ 的距離。

Return parameter： $p$

參數 $p$ 用來控制在遊走過程中立即重新走到已訪問過的結點的可能性。從Fig 2中分析：

將 $p$ 值設置為 $pgt max(q,1)$ ，那麼 $p>q$ 一定成立，所以結點之間邊的權值關係變成 $(alpha_{tv}=1/p)lt (alpha_{vx}=1/q)$ ，用來保證減少採樣已經訪問過的結點，也就是當結點從 $t o v$ 後，不會再重新返回結點 $t$ ，而是訪問結點 $x$ 。
將 $p$ 值設置為 $plt min(q,1)$ ，那麼 $plt q$ 一定成立，所以結點之間邊的權值關係變為 $(alpha_{tv}=1/p)gt(alpha_{vx}=1/q)$ ，也就是當結點從 $t o v$ 後，將重新回到 $t$ 結點，將會使遊走陷入局部循環。

In-out parameter： $q$

Fig 2中：

如果 $qgt1$ ，隨機遊走時的結點與結點 $t$ 緊鄰。從圖中，下一步應該會選擇結點 $x_1$ ，相當於是廣度優先搜索，尋找與源結點近鄰的結點。如圖3的bottom圖顯示的是設置 $p=1,q=2$ 的情況。通過node2vec演算法獲取結點的特徵，並且用這些特徵對結點進行聚類。例如圖3的bottom圖中，通過node2vec演算法後的藍色結點距離較小，因為它們作為子圖的橋存在。而黃色結點由於交互次數有限，所以具有相同的結構特徵，同樣距離較近。通過這種方式實現了結構等價性(structural equivalence)。
如果 $qlt 1$ ，隨機遊走傾向選擇訪問距離結點 $t$ 較遠的點，在圖2中，下一步會選擇 $x_2,x_3$ 結點，類似於深度優先搜索策略。如圖3的top圖顯示的是設置 $p=1,q=0.5$ 的情況。在進行vec2node演算法時，頻繁訪問到的結點作為同屬於一個社區的結點。通過這種來發現前面提到的同質性(homophily)。

對於Fig 1而言，我們採樣一個隨機遊走，設隨機遊走的長度為 $l$ ， $k$ 是 $(l-k)$ 個結點的鄰居結點的個數，( $lgt k$ )。於是，我們採樣了一個 $l=6$ 的隨機遊走， ${u,s_4,s_5,s_6,s_8,s_9}$ ，所以結點的鄰居結點分別是， $u$ 的鄰居結點： $N_S(u)={s_4,s_5,s_6}$ ， $s_4$ 的鄰居結點： $N_S(s_4)={s_5,s_6,s_8}$ ， $s_5$ 的鄰居結點： $N_S(s_5)={s_6,s_8,s_9}$

node2vec 演算法解析：

演算法思想：定義一個圖 $G=(V,E,W)$ ，維度是 $d$ （特徵空間的維度），進行隨機遊走，遊走的長度是 $l$ ，選取的鄰居結點個數是 $k$ ，參數 $p, q$ 。優化 $k,d, walks$ 。

先初始化圖和圖中的參數 $p,q$ ，把 $(G,p,q)$ 構成的權值賦值給 $pi$ ，也就是 $pi=PreprocessModifiedWeights(G,p,q)$ ，也就是用 $pi$ 初始化圖 $G=(V,E,W)$ 中的權重 $W$ ，構成了圖 $G=(V,E,pi)$ 。

初始化遊走，在演算法 $node2vecWalk$ 中，初始化遊走起點是結點 $u$ ，遊走的長度是 $l$ ，所以一次遊走要遍歷包括起始結點在內的 $l$ 個結點。 $curr=walk[-1]$ 指向當前遍歷的結點也就是從起始結點 $u$ 開始，通過 $GetNeighbors(curr,G)$ 尋找當前結點在圖 $G$ 中的鄰居結點，將鄰居結點記為 $V_{curr}$ ，同時通過 $AliasSample(V_{curr},pi)$ 根據權值 $pi$ （每一步是 $pi_{vx}$ ，也就是結點 $v,x$ 之間的權值）進行路徑的選擇，選擇的下一步路徑記為 $s$ ，將選擇的下一個結點路徑 $s$ 添加到 $walk$ 里。遍歷完總路徑長度 $l$ 後返回一條總的路徑 $walk$ 。對圖 $G$ 中的所有結點，都作為初始結點進行一次隨機遊走，作為一次迭代過程，這樣重複迭代 $r$ 次。通過隨機梯度下降優化函數 $f$ 中的鄰居結點個數 $k$ ，特徵空間 $d$ ，隨機遊走路徑 $walks$ ，最後返回函數 $f$ 。

總結演算法的三階段：

預處理時，轉移概率的計算，也就是 $pi$ 的獲取；
隨機遊走的執行；
通過隨機梯度下降（SGD）優化目標函數。

該演算法的每個階段是非同步並行執行的。

3.3 Learning edge features

將單個結點的特徵表達擴展為一對結點的特徵表達。

給定兩個結點 $u$ 和 $v$ ，這兩個結點相對應的特徵向量分別是 $f(u),f(v)$ ，定義結點之間邊的表達式為 $g(u,v)$ ，並且 $g: V imes V o R^{d}$ ，這裡的 $d$ 是點對 $(u,v)$ 表達式的大小。下表table 1就是幾種邊特徵的表達。

4.2 Experimental setup

實驗中通過監督學習的方法來評估通過node2vec演算法學到的特徵表達的性能：結點的多標記分類，邊的預測。

通過與下列演算法進行比較：

譜聚類（Spectral clustering）：這是一種矩陣分解方法，我們選擇top $d$ 個圖的標準Laplacian 矩陣作為結點的特徵向量。
深度遊走（DeepWalk）：可視為當node2vec演算法選擇 $p=1,q=1$ 時的情況，也就是一種均勻隨機遊走的情況。
LINE：分為兩個階段學習一個 $d$ 維的特徵表達。第一階段：通過BFS獲得直接相連的鄰居結點，學到 $d/2$ 維；第二階段：獲取與源結點2跳距離的結點（2-hop），學到接下來的 $d/2$ 維。

這裡paper排除了其他的矩陣分解方法，是因為這裡提到的DeepWalk比其他的矩陣分解方法都要好；同樣也排除了GraRep方法，該方法時LINE方法的泛化，獲取了與源結點距離超過2跳（2-hop）的結點信息，但是這種方法不能擴展到大型的網路。

關於node2vec的參數設定：

設置 $d=128,r=10,l=80,k=10$ ，通過十重交叉驗證優化超參數， $p,qin {0.25,0.50,1,2,4 }$ 。

4.3 Multi-label classification

在多標記的分類中，每個結點由一個或多個標籤，標籤集合 $L$ 。在訓練階段，可以發現一個特定的結點和它對應的所有標籤。該任務時為了預測剩餘結點的標籤。

在如下數據集上進行了實驗：

BlogCatelog：該網路有10,312個結點，333,983條邊，以及39個不同的標籤；

Protein-Protein Interactions(PPI)：

。