【論文筆記】struc2vec

名稱：struc2vec： Learning Node Representations from Structural Identity

作者：Leonardo F。 R。 Ribeiro， Pedro H。 P。 Saverese， Daniel R。 Figueiredo

原始碼：

https：//

github。com/leoribeiro/s

truc2vec

這篇文章與很多現有的做網路表示的工作不同，它關注的是

不同的節點在網路中的所處的角色

。節點的

結構特性身份

（structural identity）跟其所處的網路位置和與其他節點的關係有關，這篇文章提出了一種新的框架用於在表示網路中節點的同時保持節點的結構特性。而現有的很多sota（state-of-the-art）演算法都僅僅只是將節點根據在網路中的距離關係表示成向量，並沒有考慮節點的結構特性。

這個結構身份（structural identity）因為翻譯找不到合適的詞，很容易跟網路的結構特性這種詞混淆，暫時可以將其理解為某個節點與周圍鄰居的連線關係所構成的特徵，或者說他們的空間結構相似，具體我們看文中是怎麼解釋的。

Introduction

在現實的網路中，構成網路的每個節點可能在網路中擔任著某種角色。比如社交網路中，經常可以看見一些關注量很高的大V。兩個大V在網路中的角色可能相同，因為他們都有很高的關注量；而大V與普通人（僅有幾個關注）在網路中的角色則是不同的，這就是所謂的某個節點的結構身份（structural identity）。

常見的一些可以決定某個節點的結構身份的方法有兩種。一種是

基於距離的方式

，透過鄰居資訊計算每個節點對之間的距離，然後透過聚類、匹配的方式來將結構相似的節點放到一起。另一種是

基於遞迴的方式

，就是透過遞迴的方式將所有鄰居的資訊聚合得到一個值，根據這個值決定是否是結構相似的。

之前的很多網路表示的工作的思路是利用鄰居作為上下文。

如果兩個節點的共同鄰居越多，那麼表示這兩個節點越相似

，自然就要減小他們在嵌入空間中的距離。但是這種方法無法鑑別結構相似但是距離非常遠的節點對，換句話說某些節點有著類似的拓撲結構，但是它們離得太遠，不可能有共同鄰居（就比如下圖的u和v）。這種情況是之前很多工作沒有考慮到的點。

DeepWalk或node2vec這一類的方法在判斷節

點的結構是否等價

的分類任務上往往並不能取得好的效果。其根本原因在於網路中的節點具有

同質性

（homohily），即兩個節點有邊相連是因為它們有著某種十分相似的特徵。因此在網路中相距比較近的節點在嵌入空間也比較近，因為他們有著共同的特徵；而在網路中相距比較遠的節點，則認為它們沒有共同特徵，因此在嵌入空間的距離也會比較遠，儘管兩個節點可能在區域性的拓撲結構上是相似的。

如果分類任務更看重同質性的特徵，那麼DeepWalk類的方法自然可以滿足要求；但是術業有專攻，如果分類任務是想找出哪些節點的區域性拓撲結構是相似的，那麼DeepWalk自然就不能勝任了。

盤點一下本文的貢獻：

本文的演算法並沒有按照節點和邊的屬性或者在網路中的位置關係來評估節點之間的結構相似性。如果兩個節點在區域性有著類似的拓撲結構，那麼這兩個節點就是類似的。本文的演算法即使在圖是非連通的情況下，仍然能在兩個子圖中找出結構相似的節點。

建立了一個分層的結構來衡量節點的結構相似性。在底層，兩個節點相似性的判定只依賴十分簡單的資訊，比如度；而在頂層，兩個節點的相似性的判定則要依賴於整個網路的資訊。

使用隨機遊走的取樣方式獲取上下文。如果兩個節點經常出現在相同的上下文中，表明它們有著相似的結構特性。

Related Work

首先肯定了一波網路表示學習的作用。

然後說到了DeepWalk的思想來源word2vec，它學習到的語言模型所最佳化的目標實際上是讓語義相近的節點在嵌入空間中也相近。

接著簡要說明了DeepWalk、node2vec的方法，最後回到本文的目標上來就是，按照這些最佳化方法，結構相似但是距離很遠的節點根本不會共享共同的上下文節點。

後面介紹了考慮了結構相似的同類型文章subgraph2vec、RolX等方法以及侷限性，因為沒看過原論文，就不詳細介紹了。

Methods

根據以上的分析，一個好的可以反映節點結構特性的方法必須滿足以下兩個特徵：

嵌入空間的距離得能反映出節點之間的結構相似性，兩個區域性拓撲結構相似的節點在嵌入空間的距離應該相近。

節點的結構相似性不依賴於節點或邊的屬性甚至是節點的標籤資訊。

總的來說，本文的演算法可以分成四步：

根據不同距離的鄰居資訊分別算出每個節點對的結構相似度，這涉及到了不同層次的結構相似度的計算。

構建一個多層次的帶權重網路M，每個層次中的節點皆由原網路中的節點構成。

在M中生成隨機遊走，為每個節點取樣出上下文。

使用word2vec的方法對取樣出的隨機遊走序列學習出每個節點的節點表示。

接下來我們逐個來看每個步驟分別做了什麼事。

Measuring structural similarity

前面說過兩個節點結構相似性的度量應該獨立於節點和邊的屬性，因此這一步就是找出這樣的一種度量節點之間相似性的方法。

一個核心觀點是：

如果兩個節點的度相同，那麼這兩個節點結構相似；如果這兩個節點的鄰居度也相同，那麼這兩個節點的結構相似性比前者更高。

接下來是一些符號：

：無向帶權網路，V表示節點集合，E表示邊集合。

：網路中的節點數。

：網路的直徑，即網路中任意兩點距離的最大值。

：與節點u距離為k的節點集合，等同與以u為根的BFS樹上第k層的節點集合。例如，

就是u的直接鄰居。

：對某個節點集合V中的節點按照度的從小到大順序排序後形成的序列。

：考慮兩個節點的k跳鄰域（k-hop neighborhoods）時（小於等於k跳的所有鄰居均要考慮），兩個節點的在結構距離（structural distance）。表示式如下：

$\begin{aligned} f_{k}(u, v)=& f_{k-1}(u, v)+g\left(s\left(R_{k}(u)\right), s\left(R_{k}(v)\right)\right) \\ & k \geq 0 \text { and }\left|R_{k}(u)\right|,\left|R_{k}(v)\right|>0 \\ \end{aligned} \\$

就是距離u，v相距為k的那些節點之間的結構距離。這是一個遞迴定義，

$f_{k-1}(u,v)$

表示考慮k-1跳鄰域時的距離，再加上只考慮k跳鄰居的距離，就形成了k跳鄰域的距離了，初始值

$f_{-1}=0$

。

表示兩個有序的序列

的距離。

$s(R_{k}(u)), s(R_{k}(v)))$

分別表示與u，v距離為k的節點按照度大小排序後的度序列。

注意到

的計算是在

$f_{k-1}(u,v)$

上加上一個非負的值，因此

該函式關於k是一個單調不降的函式

。並且這個函式只有在兩個節點同時存在k跳鄰域的時候才有定義。

下面給出一個具體的例子：

到這裡我們的一個最大的疑問可能是這個

到底是什麼？怎麼衡量兩個序列的距離呢？本文使用的是DTW（dynamic time warping）的方法，這是語音識別中的一種方法（詳細資料見文末Reference）。

對於兩個序列A、B，對任意的

$a \in A,b\in B$

定義一個距離函式

表示a與b的距離，DTW想利用這樣定義的距離函式找到序列A、B的最小距離。舉個例子：

設A=（1，1，3，5，8），B=（1，2，2，6）是兩個已經排序過的度序列，給出距離函式的定義為

$d(a,b)=\frac{max(a,b)}{min(a.b)}-1$

，那麼對A、B中所有元素兩兩之間計算距離d，得到左圖中紅色的距離。接下來我們利用這個矩陣來計算序列A、B的距離。

計算用到的演算法是動態規劃，遞推式為：

$g(i, j)=\min \left\{\begin{array}{l}{g(i-1, j)+d(i, j)} \\ {g(i-1, j-1)+2 d(i, j)} \\ {g(i, j-1)+d(i, j)}\end{array}\right. \\$

比如要計算

，那麼首先找到

，

$g(2,1)+2d(3,2)=0+2\times 0.5=1$

因此

，然後我們用一個箭頭標註

是從

計算出來的。

透過這樣逐個計算，直到下標到達A、B的最大長度，則

就是A、B這兩個序列的距離。

觀察到這樣一個現象，當A=（1，1，3，5）時，其實與B的度序列非常相似，此時計算出來兩個序列的距離為1。9（上圖的

），而給A加了一項很大的值後，兩個度序列的距離一下子就變成了3。9。

最後，為什麼這麼定義距離函式？看個例子，如果a=1，b=2，兩者差值為1，

；而若a=100，b=101，兩者差值仍然為1，此時

。這說明後者比前者距離更小，更相似。

Constructing the context graph

上一步得到了每個節點對在不同的k上的結構相距離，這一步我們根據這些資訊構建一個多層帶權重的網路M。

先看其中的一層，每一層是一個帶權重的完全圖（任意兩個節點都有邊相連，如下圖），因此有

$\frac{n(n-1)}{2}$

條邊，每條邊的權值定義為：

$w_{k}(u, v)=e^{-f_{k}(u, v)}, \quad k=0, \ldots, k^{*} \\$

直觀上理解一下這個式子，如果u，v越相似，那麼它們的結構距離

就越小，或者越趨向於0，那麼（u，v）在圖中的權重越大，當

時權重達到最大值1。也就是說，在每層的圖中，邊表示任意兩個節點的結構相似性，相似性越大的權重越大。

層與層之間是透過有向邊相連的，具體的，對於第k層的任意節點

，都有有向邊

$(u_k,u_{k-1})$

和

$(u_k,u_{k+1})$

，權重為別為：

$\begin{aligned} w\left(u_{k}, u_{k+1}\right) &=\log \left(\Gamma_{k}(u)+e\right), \quad k=0, \ldots, k^{}-1 \\ w\left(u_{k}, u_{k-1}\right) &=1, \quad k=1, \ldots, k^{} \\ \end{aligned} \\$

其中

$\Gamma_k(u)$

表示第k層中，所有指向u的邊中權重大於該層平均權重的數量。具體的式子：

$\Gamma_{k}(u)=\sum_{v \in V} \mathbb{1}\left(w_{k}(u, v)>\overline{w_{k}}\right) \\$

$\bar w_k$

第k層所有邊權的平均值。

$\Gamma_k(u)$

實際上表示了第k層中，有多少節點是與節點u相似的，如果u與很多節點都相似，說明此時一定處於低層次，考慮的資訊太少，那麼

$\Gamma_k(u)$

將會很大，即

$w(u_k,u_{k+1})>w(u_k,u_{k-1})$

，對於這種情況，就不太適合將本層中的節點作為上下文了，應該考慮跳到更高層去找合適的上下文，所以去喜高層的權重更大。

Generating context for nodes

上一步多層網路M的構建就是為了尋找合適的上下文，而尋找上下文的方法與DeepWalk一樣是取樣隨機遊走的方式。

具體的，假設隨機遊走走到了

，那麼它下一步可能的走向是

$u_{k+1},u_{k-1},v_k,w_k$

（見上圖左半邊）。留在本層繼續遊走的機率為q，自然跳層的機率就是1-q。

在本層中，向其他節點遊走的機率跟邊的權重有關，也就是對權重做一次歸一化得到機率：

$p_{k}(u, v)=\frac{e^{-f_{k}(u, v)}}{Z_{k}(u)} \\$

分母是歸一化因子：

$Z_{k}(u)=\sum_{v \in V \atop v \neq u} e^{-f_{k}(u, v)} \\$

如果跳層，同樣分兩個方向，機率也跟邊的權重有關：

$\begin{aligned} p_{k}\left(u_{k}, u_{k+1}\right) &=\frac{w\left(u_{k}, u_{k+1}\right)}{w\left(u_{k}, u_{k+1}\right)+w\left(u_{k}, u_{k-1}\right)} \\ p_{k}\left(u_{k}, u_{k-1}\right) &=1-p_{k}\left(u_{k}, u_{k+1}\right) \end{aligned} \\$

注意到當層數越高，因為考慮的鄰域更廣，節點間的結構相似性計算越苛刻，因此

在底層計算出兩個節點結構相似的，在高層則不一定相似

，並且高層很多節點之間的

可能根本沒有定義。這就導致如果隨機遊走在某個節點u跳到了更高的層，那麼在隨機遊走的序列中，其左邊的節點是k層，而右邊的節點是k+1層的。而左右兩邊的取值範圍是不同的。換言之，某個節點可能會出現在左邊，但不會出現在右邊，因為雖然它跟中間那個節點u在k層是相似的，但在k+1層可能無定義或者

$f_{k+1}(u,v)$

太大導致隨機遊走在k=1層走到這個節點的機率幾乎可以忽略。

另外從原始碼可以發現，當在節點u處跳層時，只會新增一次節點

，而不會將

$u_k,u_{k+1}$

都新增到隨機遊走中。

Learning a language model

有了上一步取樣出來的隨機遊走。這一步就很簡單了。直接套用word2vec中SGNS（skip-gram with negative sampling）就可以了。

complexity and optimization

瞭解了演算法的流程後，逐步分析演算法的複雜性

DTW計算序列距離：

，透過一定的最佳化可以降到

，l是序列的最大長度。

度序列的長度：

$|s(R_k(u))|<min(d^k_{max},n)<n$

第k層一共要計算

$\frac{n(n-1)}{2}$

個節點對，第k層的複雜度：

$O(n^2min(d^k_{max},n))$

總共k層：

這個複雜度太高了，為此作者提供了3種最佳化演算法：

壓縮度序列，降低度序列長度。比如{1，1，1，1，2，2，5，5，5，8}壓縮成{（1，4），（2，2），（5，3），（8，1）}，每一項分別表示度數與度出現的次數。

略去很多初始值就很大的點對。在計算點對結構相似性時，很多點對在k=0的情況下結構距離

就非常大了，對於k更大的值根本就不用算了，肯定比

還要大（單調不降函式）。解決措施是根據二分查詢與當前節點度數相近的節點，二分查詢路徑上的節點與當前節點構成節點對，直接將n個節點對降低到logn個節點對。

演算法總共要計算

層，很多情況下，網路直徑比平均距離要大得多，可以使用一個更小的k，比如平均距離等等來代替這個值。

Experiment

Barbel graph

為了說明實驗效果，作者先在一個小的資料集上進行實驗，構造了一個Barbel graph，這個圖由兩個完全圖和連線兩個完全圖的橋構成。這個圖是對稱的，理論上兩個完全圖中的所有節點，除了與橋相連的兩個節點，都是結構相似的。另外由於橋也是對稱的，所有橋兩邊的對稱的節點也是結構相似的。這是理論分析的結果，現在看看各個baseline在這個資料上的效果。

DeepWalk和node2vec顯然是根據節點在網路中的距離對映到嵌入空間的，有著與原圖十分相似的慢慢過渡的結構。因為skip-gram的機制導致兩個完全圖中的節點不可能同時出現在一個隨機遊走序列的某個視窗中，因而兩個完全圖中的節點被對映到了完全不同的位置。

struc2vec的結果則完全如理論分析的那樣，OPT1的演算法甚至更好。

RolX是一個可以分辨角色的框架，然而它的效果仍然沒有struc2vec效果好。

Karate network

空手道俱樂部是另一個被廣泛使用的資料集，本文為了更好地說明結構相似性，將原網路複製了一份，使得每個節點都有一個與之結構相同的映象節點。前面說過strcu2vec是可以處理不連通的網路的，但是其他的baseline不可以，因此為了公平，在兩個網路之間添加了一條連線映象節點的邊。整個網路的效果如下：

下面看看對其嵌入後的結果：

由於其他的方法效果太差，這裡就只放strcu2vec的效果了，透過上圖可以發現：

映象節點（顏色相同）的嵌入距離大都比較相近。

節點1、37、42、34這兩組映象節點與其他節點的嵌入距離較遠，觀察原網路可以發現，這兩組節點實際上是兩個社群的中心節點，度數均非常大。

同樣另外一幅圖也很能說明問題：

藍色標記表示strcu2vec中映象節點之間的距離分佈，紅色節點表示struc2vec中所有節點之間的距離分佈，橙色節點表示node2vec中映象節點之間的距離分佈，紅色節點表示node2vec中所有節點之間的距離分佈。虛線分別表示距離的平均值。

對比藍色與綠色發現，strcu2vec更能區分出映象節點。

對比綠色和橙色發現，node2vec不能區分出映象節點，因為這兩個分佈的形狀是類似的，仔細想想其實也能明白因為映象節點之間相距太遠，node2vec直接把他們當成不同的節點了。

對比紅色和橙色發現，strcu2vec對不相似的節點區分地更開，顯示在影象中就是紅色分佈的尾部更長且分佈的距離範圍更廣。

其他的資料集上的效果就不一一分析了，具體的可以參考文章原文。

Reference

【Graph Embedding】Struc2Vec：演算法原理，實現和應用

Network Embedding—Struc2Vec

Strcu2vec 的簡讀

HMM學習筆記_1（從一個例項中學習DTW演算法

語音訊號處理之（一）動態時間規整（DTW）

小蜜蜂問答

小蜜蜂問答

【論文筆記】struc2vec

推薦文章

小蜜蜂問答

小蜜蜂問答

【論文筆記】struc2vec

相關文章

夢幻西遊五開為什麼一個號掉線？

璧山到機場距離？

貌似神合，其實不然什麼意思？

今年賺了兩個億下一句怎麼回？

推薦文章