TLP:一個動態網絡中的時序鏈路預測算法

符漢杰,熊 赟,朱揚勇

(1.復旦大學 計算機科學技術學院,上海 200433; 2.上海市數據科學重點實驗室,上海 200433;3.上海先進通信與數據科學研究院,上海 200433)

0 概述

在現實世界的網絡中,如社交網絡、基因網絡,用戶、基因等表示為網絡中的節點,而用戶間的朋友關系、基因間的相關性表示為節點間的連接關系。鏈路預測是網絡中的一個重要應用,即通過已知的網絡節點及其節點間的連接預測對未連邊的2個節點間存在連邊的可能性,其在用戶推薦[1]、基因序列分析[2]等場景中有著廣泛的應用和重要的價值。現有網絡上的主要研究是基于靜態網絡上的算法,如隨機游走優化的Node2vec[3]、矩陣分解的HOPE[4]和深度自編碼器的SDNE[5]。

而實際中的網絡具有豐富的動態特性,網絡中節點之間的連接隨著時間的推移[6-7],會產生新的聯系或者終止連接,從而導致網絡結構發生變化以及節點中內在的偏向發生偏移。網絡的演化原因是多方面的,如社交網絡中隨著用戶的偏好變化影響到社區聚合或分離,用戶購買商品隨著時間長短呈現周期性變化的規律。單純地考慮網絡的整體信息,忽略其歷史動態演變過程,難以預測有動態特性的數據及其時序上的規律。通過研究網絡結構隨時間變化的演變過程,預測節點間未來連接的可能性變化,以及分析未來社區演化的規律,更有利于提高鏈路的預測精度。

動態網絡中的鏈路預測需要結合網絡的空間結構和時序演變的信息,考慮節點間的動態鄰接信息,以提高鏈路預測的精確性,如TNE[8]和LIST[9]在動態圖中考慮了節點間的一階鄰近信息,但高階鄰近信息的缺失使得模型的精度有所降低。網絡中除了節點之間的直接連接關系,引入高階鄰近信息有助于表達網絡的空間拓撲結構,例如,DPHE[10]通過靜態網絡的算法捕捉到網絡中的高階鄰近信息,但其在不同時刻下獨立的節點表示難以預測未來時刻的網絡結構。

本文提出動態網絡時序鏈路預測算法TLP(Temporal Link Prediction),來預測動態網絡在空間上的高階鄰近信息以及時序上的演化規律。通過時序連接的方式將動態網絡中不同時刻的靜態網絡相連,并且在網絡上進行隨機游走優化,得到節點的高階鄰近鄰居以及魯棒的節點映射向量來表示動態網絡的空間結構信息。在此基礎上，使用自回歸的方式參數化節點向量,根據歷史的節點狀態推斷下一時刻的節點向量，從而預測節點的時序演變規律,以生成未來時刻的網絡結構。

1 相關工作

動態網絡由于其動態演變的特性,在近年來的研究中得到越來越多的關注。靜態網絡的算法往往只關注于網絡的歷史連接方式,而忽略了連接的時序關系,如基于隨機游走方式的DeepWalk[11]和Node2vec[3]、擬合高階鄰近的矩陣分解HOPE[4]、用深度自編碼器的SDNE[5]等。因此,和動態網絡的相關算法相比,靜態網絡算法不能很好地反映節點的偏好變化以及網絡的結構演變。

在動態網絡的相關研究中,有部分工作更關注歷史網絡的節點向量映射,而忽略了對未來網絡的表達能力。如TNE算法[8]考慮相鄰2個時刻的網絡中,節點向量是上一時刻的向量加一個偏移,并且在特征空間中具有時序平滑的特性,因此,節點向量不會變化很大。而在DynamicTraid[12]算法中,也僅考慮了相鄰2個時刻中3個節點之間的三角關系。在上述研究中,考慮相鄰時刻中的節點向量差異為一個偏移向量,不同時刻下的偏移量是獨立的,缺乏對動態網絡中的時序演變規律進行刻畫。和之前研究相比,LIST算法[9]使用多項式函數表達節點隨時間變化的規律,因此針對更遠時刻的網絡能夠刻畫網絡結構的時序性。但由于多項式的特性,節點向量往往取決于最高次項的系數,呈現單調性的變化，并且算法中只考慮了節點間的一階臨近信息,不能很好地捕捉網絡的拓撲結構。DynGEM算法[13]使用深度自編碼器的方式結合網絡的一階鄰近和二階鄰近信息,DHPE算法[10]通過GSVD靜態網絡模型捕捉高階鄰近信息,DynGraphGAN算法[14]通過生成對抗網絡的方式結合網絡的高階鄰近信息和時序演變信息。上述算法每個時刻的節點向量表示是獨立的。

TLP算法的主要目的是根據動態網絡的歷史結構生成基于時序特征的節點向量,不僅對已有的網絡進行向量映射,而且通過捕捉整個網絡的動態特性推斷未來時刻下的節點向量。

本文算法的主要貢獻如下:

1)TLP算法是一種有效的自回歸動態網絡節點向量表示,能夠保留動態網絡的時序演變特性。

2)TLP算法適用于大規模的網絡,能夠保留節點間的高階鄰近信息,維護動態網絡的空間結構。

3)在幾個真實數據集上與TNE、DHPE等算法對比,TLP算法性能具有明顯提升。

2 問題定義

本文中的主要符號含義如表1所示。一個網絡可以表達為G=(V,E),其中,V指網絡的節點集合,E?V×V包含節點間的連接。本文考慮的網絡是無權無向的,即對于每個連接的權重設定為1。

表1 符號及其含義

2.1 動態網絡

一個動態網絡可以看作是由T個靜態網絡{G1,G2,…,GT}組成,其中每個靜態網絡可表示為Gt=(V,Et),每個靜態網絡有著相同的節點集合,而邊集隨著時間變化發生演變。因此,對于動態網絡中的每個節點可表示為(v,t),指代t時刻下的網絡Gt中的節點v。相應的邊可以表示為(u,v,t),指代t時刻下節點u和節點v中有一連邊。

2.2 動態網絡的時序鏈路預測

3 時序鏈路預測算法

本節介紹在動態網絡上的鏈路預測算法TLP,算法的框架主要包括在動態網絡上捕捉節點間的高階鄰近信息，通過自回歸的向量表示和擬合網絡隨著時間演變的時序規律。

3.1 高階鄰近節點

與靜態網絡相比,在動態網絡中，由于節點存在于不同時刻的靜態網絡中,因此節點間的關系除了考慮當前網絡的連邊,還需要結合不同時刻下與其他節點的連邊信息,反映節點在不同時刻下的高階鄰近關系。

3.1.1 時序連接

定義不同時刻下節點的時序連接:假設t1≤t2,(v,t1)和(v,t2)中存在連邊,當且僅當存在(v,v1,t1)∈Et1和(v,v2,t2)∈Et2,且不存在(v,v3,t3)∈Et3，t3∈(t1,t2)。在定義中,一個節點只與時間上最近的時序連接,使得節點與不同時刻下的其他節點按照時間的距離有序地連接。將節點在不同時刻的時序連接起來,使得動態網絡中的各個子靜態網絡相互連接。

3.1.2 時序游走

一個可行的時序游走從節點(v1,t1)到節點(vk,tk),必定存在一個可行節點序列{(v1,t1),(v2,t2),…,(vk,tk)},所有的(vi,ti)與(vi+1,ti+1)之間有連邊。因此,由游走路徑上的連接信息可以得出,游走路徑中的各個節點間在動態網絡中是間接或直接鄰近的。給定一個游走路徑,可以采用Skip-Gram模型的形式,TLP算法的優化目標如式(1)所示。

(1)

(2)

其中,φ(t′,ti-k,ti)是與時間相關的權重因子,表示在時間區間外的連接概率,會隨著時間間隔增大權重因子變小。如社交網絡中的朋友關系,陌生人間的關系可能會隨時間變得更加親密而成為朋友,朋友間的關系可能會隨時間變得更加疏遠而成為陌生人。具體的權重因子定義如下:

(3)

其中,參數θ是控制權重的衰減速率,當θ=0時,源節點與目標節點在動態網絡中連接概率相等。

3.2 節點向量的時序表示

不同于靜態網絡的節點向量映射,設定動態網絡的節點在不同時刻下映射到不同的向量,并且節點的向量映射函數是與時間獨立的自回歸函數。節點(v,t)的節點向量表達式如式(4)所示。

(4)

(5)

3.3 TLP算法

在動態網絡中,由于網絡的稀疏性[16],算法中每個節點使用自回歸的向量映射方式容易產生過擬合的現象。因此,加入系數β的L2正則項提高模型的泛化能力。

在訓練過程中,算法的優化使用Adam優化器,其中每批訓練樣本量的大小設置為1 024,初始的學習率為0.000 1,輸出向量長度為50。本文的算法偽代碼如算法1所示。

算法1TLP算法

輸入動態網絡{G1,G2,…,GT},時刻t

1.根據時序連接的定義,把動態網絡轉為靜態網絡G。

2.用Node2vec算法中的隨機游走方式,得到游走路徑集合walk。

3.LOOP

4.從游走路徑walk中采樣作為訓練樣本,路徑上每個節點vi取窗口內的節點為正樣本,通過負采樣得到的節點vn～Pn(vi)作為負樣本。

5.通過式(2)計算算法的損失函數。

7.重復步驟1～步驟3,直至算法收斂為止。

4 實驗結果與分析

本節在公開的數據集上進行實驗,通過幾個基準的算法進行比較來評估算法的性能。

4.1 數據集

本文采用4個數據集進行實驗,包括社交網絡和共同作者關系網絡。所有的網絡都是無向無權重的動態網絡,具體描述如下:

1)Facebook[17]、Epinions[18]、Digg[19]數據集:社交網絡數據是從Facebook、Epinions和Digg中收集的，其中,網絡中的節點表示用戶,節點的連接在Facebook、Epinions數據集中表示用戶的朋友關系,在Digg數據集中表示用戶間的信任關系。用戶間的關系有建立的時間,對此按照一個月的時間間隔劃分數據集得到動態網絡。對于時間缺失的連邊,把它看作是第1個動態網絡的初始邊。

2)Dblp[20]數據集:共同作者關系網絡反映的是在dblp computer science bibliography上的共同作者關系。網絡中的節點表示論文作者,而節點間的連接表示作者共同發表論文，論文的發表時間作為連接的時間,以一年的時間間隔劃分數據,保留不小于1970年的關系,從而得到最終的動態網絡。

在4個真實數據上構造動態網絡,節點數的范圍為60 000～1 400 000,節點間連邊數范圍為700 000～8 500 000,動態網絡的時間長度最大為48。具體的數據描述如表2所示。

表2 具體數據說明

4.2 動態網絡算法

為評估算法的性能,對目前有代表性的動態網絡算法進行對比,具體如下:

TNE算法[8]:使用矩陣分解的方法將動態網絡的節點映射到向量中,并且基于節點時序平滑的性質,考慮相鄰時刻的同一節點向量的差異。由于算法只對每個歷史時刻生成節點向量,因此采用T-5時刻下的節點向量作為未來時刻的結果。

DynamicTriad算法[12]:考慮相鄰時刻下3個節點的三角閉合關系來捕捉網絡中的結構信息和演化模式。與TNE算法類似,采用T-5時刻下的節點向量作為未來時刻的結果。

DHPE算法[10]:采用靜態網絡算法得到節點向量,然后根據網絡的變化更新向量,實驗中采用T-5時刻下的節點向量作為未來時刻的結果。

4.3 鏈路預測

在鏈路預測的任務中,使用動態網絡中最后5個時刻的靜態網絡作為測試集,而其余的靜態網絡作為訓練集。其中,測試集中的連邊作為正樣本,通過隨機采樣的方式得到與正樣本同樣數量的邊集作為負樣本。評估的指標采用AUC，所有實驗運行的機器設備為220 GHz CPU,128 GB RAM和16 GB Tesla-P100 GPU,實驗結果如圖1～圖4所示。

圖1 Facebook數據集上AUC變化曲線比較結果

Fig.1Comparison results of AUC changing curve on Facebook dataset

圖2 Digg數據集上AUC變化曲線比較結果

Fig.2Comparison results of AUC changing curve on Digg dataset

圖3 Epinions數據集上AUC變化曲線比較結果

Fig.3Comparison results of AUC changing curve on Epinions dataset

圖4 Dblp數據集上AUC變化曲線比較結果

Fig.4Comparison results of AUC changing curve on Dblp dataset

根據上述實驗結果可以得到以下結論:

1)TLP算法和TNE、LIST、DynamicTriad、DHpe算法相比,在各個數據集中的AUC指標都有提升,在Facebook、Digg、Epinions、Dblp數據集上的提升分別為1.72%、4.17%、0.13%和7.92%。因此,TLP算法在對未來時刻的鏈路預測任務中擁有更好的性能提升。

2)在Dblp數據集中,節點數量達到140萬,在該大規模的網絡中對算法的性能有比較高的要求。其中LIST算法受限于內存的限制,不適用于Dblp大大規模的數據集。而DynamicTriad算法受限于Tensorflow框架中張量的大小不能大于2 GB,也不能在Dblp數據集上運行。因此,圖4中沒有LIST和DynamicTriad算法的相關結果。而TLP算法采用隨機游走的方式不需要輸入整個網絡進行優化,并且節點向量采用函數表達的方式需要的張量比DynamicTriad算法需求低,因此,能夠適用于大規模的網絡。

3)TNE算法的目的是把歷史不同時刻的網絡節點映射到低維的空間,但在數據集上的效果相比其他算法效果略低。由于TNE算法在T時刻的節點向量基于T-1時刻進行更新,容易陷入局部收斂的狀態。并且算法中只考慮歷史時刻的節點向量映射,并不能很好地反映未來時刻的節點向量變化。由于在實際網絡中節點間的連邊具有稀疏的性質,但算法中沒有平衡正負樣本的比例。使得結果稍差。

4)LIST算法使用多項式函數表達節點向量,向量隨著時刻的增加呈指數式變化,與時序平滑的性質相違背。如在Facebook和Epinions數據集中,LIST算法在T時刻下的AUC指標較T-4時刻相比分別降低了0.13和0.20。而TLP算法在Facebook和Epinions數據集上的Auc指標分別降低0.05和0.01,比LIST算法中的多項式函數效果更優。并且LIST算法只考慮節點間的一階鄰近信息,不能很好地捕捉動態網絡的拓撲結構。

5)DynamicTriad算法由于只考慮由歷史時刻網絡結構得到的節點向量,缺乏對時序演變規律的挖掘。而TLP算法能夠考慮更高階的鄰近信息。因此，該算法在Facebook、Digg和Epinions數據集上的精度要低于TLP算法。

6)DHPE算法能夠通過靜態網絡算法考慮高階鄰近信息,但由于其不能結合網絡結構和時序信息,因此實驗結果中該算法的精度有所降低。

4.4 參數分析

為證明TLP算法中參數的重要性,本文在Facebook數據集上根據不同的參數驗證算法的效果。

在TLP算法中,參數δ可以平衡自回歸節點向量表示中全局信息和時序信息的權重比,參數δ越大時序信息的權重比也越大。通過枚舉參數δ來得到算法的結果,觀測時序信息對節點向量的影響。本文枚舉參數δ從0到1,固定參數d=50、s=2、β=0、θ=0。具體結果如圖5示,可以看出，當δ=0.25時，TLP算法能得到最好的效果,而當δ=1時最差；當δ=0時,即TLP算法只考慮動態網絡的全局信息而忽略了時序信息,在未來時刻的鏈路預測問題上依然能得到一個較好的效果,這反映出全局信息在動態網絡中的重要性。而當δ=1時,加入了與全局信息等權重的時序信息,由于反映時序的參數個數與參數s成線性相關,優化過程中容易使時序信息權重比例過大導致效果降低。當δ=0.25時,由于能夠平衡節點向量中的全局信息以及時序信息的權重比例,因此使得算法能夠得到更好的效果。

圖5 δ參數在Facebook數據集中的驗證效果

由于節點間關系會隨時間發生衰減或增強,為了觀測關系變化強度對算法的影響,通過枚舉參數θ來得到算法的結果。參數θ越大,節點間關系變化越快。枚舉參數θ從0到1,固定參數d=50、s=2、β=0、δ=0.25。具體結果如圖6所示,可以看出，當θ=0.75時效果最好，當θ=0時,忽略了節點間的聯系在時間上平滑過渡的性質，當θ=1時,節點之間連邊的權重隨時間變化衰減或者增長較快,使得算法效果較差。因此,選取適當的θ,控制節點間連邊的權重變化,能夠提升算法在動態網絡上的效果。

圖6 θ參數在Facebook數據集中的驗證效果

5 結束語

本文提出一個動態網絡上的鏈路預測算法。該算法在時序連接的動態網絡上尋找節點間的高階鄰近信息,可適用于大規模網絡,同時節點運用自回歸向量表示的方法捕捉節點向量與歷史狀態的關系，使用歷史狀態推導下一時刻的節點向量方式,解決了與時間相關的多項式向量表達中隨時間增加向量表達性能降低的問題。在真實數據集上的實驗結果表明,與現有動態網絡相關算法相比,TLP算法在更遠時刻網絡上的鏈路預測任務中具有更高的精度。由于模型缺乏對內容屬性的考慮,下一步將通過加入節點和連邊的屬性挖掘來提高模型的預測精確度。