Dynamic Network Embedding by Modeling Triadic Closure Process 閱讀筆記

04-29

轉載請註明出處：

每周一篇機器學習論文筆記?

zhuanlan.zhihu.com

論文來源：AAAI 2018

論文鏈接：Dynamic Network Embedding by Modeling Triadic Closure Process

論文原作者：Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, Yueting Zhuang

論文模型源碼：Github code

（侵刪）

Abstract

Network embedding是最近網路挖掘領域很火的一塊，目的是希望能夠將網路中的節點用比較低維的向量去表達，同時在這個向量空間中，網路結構的一些性質仍能夠保持。然而，之前這個領域上比較經典的演算法比如Deepwalk，node2vec，LINE以及其他各種擴展的演算法都大多是對靜態網路進行研究。

在現實生活中，大多數網路是會隨著時間變化的。因此，這篇論文提出了一個新的網路表示學習方法－DynamicTriad，使得在保持網路結構性質的同時，也將網路的時間變化特性嵌合到向量中。論文通過引入triad(三合音)：三個頂點組成的一個網路基本單元，來作為網路動態變化的基本機制，從而使模型能夠捕捉網路的動態，並在不同的時間點學習每個頂點的向量表示。

Introduction

在網路動態的演變過程中，不同節點的結構演變可能也是不同的，而傳統的network embedding很難能夠獲取到這些結構的演變模式。以社交網路為例，用戶A可能更願意介紹他的朋友相互認識，因此可能在時間t時，與用戶A相連的兩個節點還未相連，而到了t+1時，用戶A已經介紹他們兩個認識了，則此時與用戶A相連的兩個節點也形成了邊。而用戶B可能傾向於讓他的朋友保持他們的圈子，所以不會介紹他的朋友互相認識。不同的用戶進化模式反映了他們自己的性格和社會策略之間的差異，這是用來滿足他們的社會需要，比如發展與他人的聯繫。因此，是否能夠很好地反映頂點的演化模式是動態網路嵌入方法的一個關鍵要求。

這篇文章主要是通過捕獲網路的演化結構屬性來學習頂點的嵌入向量。給出時間階段1-T上的網路 $G_1,...,G_T$ ，目標是希望能夠學習出節點i 在時間階段t 的向量表示 $extbf{u}_t^i$ 。之前的一些方法大多都是通過添加正則化項來表示平滑的動態變化，但這樣做的話就不能夠很好地表達一些急劇變化的節點，而且也不能體現出一些結構的演變。這篇文章通過triad來體現網路結構的動態變化，總的來說，存在兩種traid：closed triads(三個頂點中的任意兩點，都存在連接關係) 以及 open traids(三個頂點中有兩點是沒有互相連接的)。一個open traid發展到closed traid的過程叫做triad closure process，它是動態網路形成與演化的基本機制，而這篇文章就是通過量化open triad發展成closed triad的概率，從而在不同的時間點中學習每個頂點的嵌入向量。

Model

1.Definition.

網路由節點集 $V = {v_1,...,v_M}$ 和邊集 $E = {e_{ij} }$ 組成, 其中 $e_{ij}$ 指的是節點 $v_i$ 和 $v_j$ 的關係

動態網路: ${G^1,G^2,...,G^T}$ , 其中 $G^t = (V,E^t,W^t)(1leq tleq T)$ 指的是t時刻的網路表達，每一條邊 $e^t_{ij} in E^t$ 對應著權重 $w^t_{ij}$ 。

動態網路嵌入表達主要是學習映射函數使得： $f^t : v_i ightarrow R^d ext{ for each t}$ ，其中d是嵌入空間的維數。對於函數 $f^t$ ，希望它不僅能夠保持得了節點 $v_i$ 和 $v_j$ 在網路 $G^t$ 中的相似性，同時能夠保持這些節點在之後拓展關係（比如說，在t+1後，與其他點建立了新的連接）的趨勢。

用 $extbf{u}_i^t := f^t(v_i)$ 和 $extbf{u} = { extbf{u}_i^t}_{i={1,...,M},t={1,...,T}}$ 來表示學習到的網路向量。

2.Model Description

整個模型的目標函數從三個方面去考慮：

<1>.Triad closure process.

以社交網路為例，在某個時刻t， $(v_i,v_j,v_k)$ 構成了一個open traid，其中節點 $v_i$ 和 $v_j$ 互相不認識但他們都是用戶 $v_k$ 的朋友，即： $e_{ik},e_{jk} in E^t ext{ and } e_{ij} otin E^t$ . 在下一時刻t+1時，用戶 $v_k$ 會決定是否介紹 $v_i$ 和 $v_j$ 相互認識，而這個決定通常取決於 $v_k$ 和他們兩個有多熟悉，因為一般來說，我們都願意把自己的好朋友介紹給另一個好朋友。所以，可以先用一個向量去量化用戶k和他們兩者的親密程度：

$extbf{x}^t_{ijk} = w^t_{ik} * ( extbf{u}_k^t - extbf{u}_i^t ) + w^t_{jk} * ( extbf{u}_k^t - extbf{u}_j^t)$ , 其中 $extbf{u}_i^t$ 指的是t時刻下的節點i的嵌入向量。

除此之外，還要定義一個社會策略參數 $oldsymbol{ heta} in R^d$ ,從而將社會策略的一些信息也嵌入到對應的隱式空間中。

這樣一來，可以將open traid演變成closed traid，即在t+1時刻時，節點 $v_i$ 和 $v_j$ 會在節點 $v_k$ 的介紹下建立連接的概率，定義為：

$P^t_{tr}(i,j,k) = frac{1}{1+exp(-langle oldsymbol{ heta}, extbf{x}^t_{ijk} angle)}$

由於節點 $v_i$ 和 $v_j$ 可能會被其他共同好友介紹，所以要將這些可能聯合起來。用集合 $B^t(i,j)$ 來表示 $v_i$ 和 $v_j$ 在時刻t的共同鄰居，並定義一個向量 $oldsymbol{alpha}^{t,i,j} = (alpha^{t,i,j}_k)_{k in B^t(i,j)}$ , 表示如果在t+1時刻時open triad $(v_i,v_j,v_k)$ 演變成closed traid（即 $v_i$ 和 $v_j$ 有連接），則 $alpha^{t,i,j}_k ＝ 1$ 。可以想到，如果 $(v_i,v_j,v_k)$ 演變成closed traid的話，那麼其他與 $v_i$ 和 $v_j$ 相關的open traid 也會變成closed，所以在t+1時，一個新的連接 $e_{ij}$ 會被產生的概率為：

$P_{tr_+}^t = sum_{oldsymbol{alpha}^{t,i,j} e f{0}}prod_{k in B^t(i,j)} (P^t_{tr}(i,j,k))^{alpha^{t,i,j}_k} imes (1-(P^t_{tr}(i,j,k))^{1-alpha^{t,i,j}_k}$

當然，如果 $v_i$ 和 $v_j$ 都沒有被它們的共同好友所影響到，那麼新的連接 $e_{ij}$ 就不會被產生，這個概率為：

$P_{tr_－}^t = prod_{k in B^t(i,j)} (1-(P^t_{tr}(i,j,k))$

為了更清晰地表達，定義兩個集合： $S^t_+ = { (i,j) | e_{ij} otin E^t wedge e_{ij} in E^{t+1}}$ 表示的是t+1時刻能夠建立連接，以及 $S^t_－ = { (i,j) | e_{ij} otin E^t wedge e_{ij} otin E^{t+1}}$ 指的是不能建立連接。所以triad closure

process的損失函數表達為：

$L_{tr}^t = -sum_{(i,j) in S^t_+}{logP^t_{tr_+}(i,j)} -sum_{(i,j) in S^t_-}{logP^t_{tr_-}(i,j)}$

<2>. Social homophily

第二個方面考慮的是網路內部的性質。

首先定義在嵌入向量空間下節點 $v_j$ 和 $v_k$ 的距離： $g^t(j,k) = | extbf{u}_j^t - extbf{u}_k^t|^2_2$ . 另外，在定義兩個集合，分別是邊集 $E^t_+ = E^t$ 和非邊集 $E^t_- = {e_{jk} | j e k, e_{jk} otin E^t}$ .

在向量學習中，我們希望原本網路中相連的節點在嵌入空間中仍然接近，而不相連的節點可以稍遠些。因此，損失函數可以表達為：

$L_{sh}^t = sum_{(j,k) in E^t_+ \ (j,k) in E^t_-} h(w_{jk},[g^t(j,k)-g^t(j,k)+xi)]_{+} )$ ，其中 $[x]_+ = max(0,x)$ ， $xi in R^+$ 是邊際值，函數 $h(w,x) = w * x$ .

<3>.Temporal smoothness

第三個是時序上變化的考慮。一般來說，網路的變化是平緩的，也就是說，連續時間戳下，網路的向量表達的變化相差不能太大。因此，對應的損失函數可以表達為：

$L^t_{smooth} = egin{cases} sum_{i=1}^{N}{| extbf{u}_i^t - extbf{u}_i^{t-1}|^2_2} & t>1 \ 0 & t=1 end{cases}$

綜上，考慮了動態網路中traid的演變，網路內部的性質，以及平緩的變化趨勢，最後整個模型的求解是最小化損失函數：

$mathop{argmin}_{ extbf{u}_i^t,oldsymbol{ heta}} sum_{t=1}^{T}{L^t_{sh} + eta_0L^t_{tr} + eta_1L^t_{smooth}}$

3.Model optimization

由於損失函數比較複雜，因此要對它進行優化。論文中對優化步驟都提及到了，但有些細節因為文章篇幅的限制所以省略了，在這裡我們也稍微提及下。

對於損失函數 $L^t_{tr}$ ,它由兩項組成。對於 $(i,j) in S^t_-$ 來說，損失函數可以很簡單地求解，只需要將 $P^t_{tr_-}(i,j,k)$ 代入即可。然而對於 $(i,j) in S^t_＋$ 來說，由於隱式變數 $oldsymbol{alpha}^{t,i,j}$ 的存在，因此無法直接代入求解，因此論文使用了EM演算法去計算出上界，從而方便去求導。

對於損失函數 $L^t_{sh}$ ，在大型網路中，遍歷每一對節點的代價是昂貴的，因此這裡使用了採樣的方法。

最後求導是使用自適應的隨機梯度下降進行的，整個訓練過程偽代碼如下圖所示，如果想更加具體了解優化過程的，可以到論文原文看看。

Experiment

（論文模型源碼：Github code）

數據集：

Mobile：它包含340751個用戶15天內200萬多個通話記錄。在每一天中，如果一個用戶撥打過給另一個用戶，則說明有邊的存在，這個邊的權重由通話數量決定。此外，每個頂點有一個標籤來標記這個用戶是否是電話詐騙犯。
Loan：與Mobile數據集有著相似的結構，它包含PPDai的200000個註冊用戶在13個月內1603712個通話記錄，每一個月看做是一個時間階段t。此外，每個頂點在時間t上都有一個時間敏感的標籤來指示用戶是否在那段時間內未能償還貸款。
Academic：51060個研究人員作為頂點，794552次合著關係作為邊。每一個時間階段是4年周期，在連續時間步長之間有2年的間隔。權重由時間段內合著次數決定。如果一個研究員發表在特定的會議的論文數量超過一半，則說明她屬於那個對應的社區，作為她的標籤。

任務：

對每一個數據集，首先學習出不同時間階段的動態網路 ${G_1,...,G_T}$ 的嵌入向量 $f{u}^t$ ,之後完成下列任務：

節點分類。通過分類器對學習到的嵌入向量訓練，然後得出節點的類標；
節點預測：通過t時段的嵌入向量去預測t+1時刻的的類標；
連接重構：通過 $|f{u}^t_i - f{u}_j^t|$ 來決定 $v_i$ 和 $v_j$ 之間是否存在連接；
連接預測：通過t時段的嵌入向量去預測t+1時刻的連接是否存在；
重構和預測變化的邊：與前兩個任務一樣，但只考慮被移除或者被添加的邊；

對比演算法：

DeepWalk，node2vec 以及 Temporal Network Embedding (TNE)

Conclusion

這篇論文主要通過triad這個結構作為載體，從一個新穎的角度，來研究動態網路之間的變化，從而實現動態網路的向量學習。個人看完覺得還是挺有啟發的，這篇論文挺值得一讀。