基于動態網絡表示的鏈接預測*

韓忠明 李勝男 鄭晨燁 段大高 楊偉杰

1) (北京工商大學計算機與信息工程學院，北京 100048)

2) (北京工商大學食品安全大數據技術北京市重點實驗室，北京 100048)

1 引 言

在現實世界中, 很多復雜系統以復雜網絡的形式出現, 如社會網絡、引文網絡、生物網絡和web 網絡等. 網絡提供了一種組織現實世界中的多樣化信息的方式, 成為人們工作生活中不可或缺的一部分, 對這些網絡進行分析研究具有非常大的學術價值和潛在應用價值[1]. 在這些網絡中, 節點之間的交互行為通常以“鏈接”的形式表示, 即使用邊將兩個節點連接. 以社交網絡為例, 網絡節點用于描述用戶, 邊用于描述用戶之間的交互行為. 鏈接預測[2]通過分析網絡中的信息來預測未來網絡中任意兩個節點之間是否可能出現鏈接. 有效的鏈接預測對人們生活中各個方面都具有重要意義, 例如幫助人們控制信息在網絡上的傳播, 幫助社交平臺進行更準確的好友推薦等.

在真實世界中, 網絡會隨著時間的推移不斷進行演變, 即網絡中的節點和邊會隨時間發生變化.網絡演變會導致網絡信息發生變化, 進而對鏈接預測任務產生影響, 因此, 捕獲這些網絡演化信息是很有必要的. 以社交網絡為例, 網絡中隨時會有新用戶注冊, 用戶隨時會創建新的好友關系, 這些新信息的增加不僅改變了當前用戶的屬性信息, 其鄰域的拓撲結構和屬性信息也會隨之發生改變.

圖1 展示了一個動態網絡示意圖, 假設在對網絡進行鏈接預測任務時, 以節點共同鄰居個數度量節點相似性, 相似度越大的節點對在下一時刻發生鏈接的可能性越大. 在T1 時刻, 網絡中的節點2 和節點5 擁有一個共同鄰居(節點4), 在T2 時刻, 該網絡在節點3 和節點5 之間新增了一條邊,即節點3 變成了節點5 的鄰居. 此時節點2 和節點5 擁有兩個共同鄰居(節點4 和節點3), 它們在下一時刻產生鏈接的可能性變大. 由此可見, 雖然新增加的邊只涉及到節點3 和節點5, 但其鄰域中的節點2 的屬性也受到了影響. 因此, 網絡動態演化對節點及其鄰域的特征信息有著非常重要的影響, 在鏈接預測過程中加入動態信息將會提高鏈接預測的性能.

圖1 動態網絡示意圖Fig. 1. Schematic diagram of dynamic network.

現有的鏈接預測方法大多針對靜態網絡, 使用網絡拓撲結構特征分析的方法進行鏈接預測, 當網絡信息發生變化時, 其性能將會受到很大影響. 此外, 網絡中的節點并不是每時每刻都在產生新的交互信息, 其發生變化的時間是不規律的, 即變化發生的時間分布不均勻. 而兩次變化之間的時間間隔會影響節點的偏好信息. 例如, 如果某節點兩次變化之間的時間間隔較長, 則應該更關注新的交互信息, 因為新的信息更能體現該節點當前的偏好. 為了有效地捕獲網絡中的動態演化信息, 本文使用表示學習方法, 用低維稠密向量表示網絡節點的偏好信息, 通過度量網絡節點表示的相似度進行鏈接預測, 并提出了基于動態網絡表示的鏈接預測模型

DNRLP(dynamic network representation based link prediction). 針對網絡演化產生的動態信息,DNRLP 設計了基于不均勻時間間隔的信息更新機制. 同時, 考慮到動態信息對相關節點鄰域的影響, 設計了基于連接強度的隨機游走算法對鄰域信息進行更新. 該模型可以有效地捕獲網絡動態信息, 提高鏈接預測的質量和有效性.

2 相關研究

2.1 鏈接預測

現有的鏈接預測研究方法主要分為兩類, 基于網絡拓撲結構特征分析的方法和基于機器學習的方法. 傳統的鏈接預測方法主要是通過對網絡拓撲結構進行特征分析, 計算節點之間的相似度, 認為相似度高的節點在將來會發生鏈接. Newman 等[3]首先提出基于網絡共同鄰居的節點相似度計算方法, 即節點擁有的共同鄰居越多, 越可能在未來發生鏈接. Adamic 等[4]提出了一種新的網絡節點相似性度量方法, 該方法根據共同鄰居節點的鏈接情況為每個鄰居節點設置權重, 并使用其加權和作為節點對的相似度. Fouss 等[5]通過隨機游走算法對網絡中節點的鄰域信息進行采樣, 得到目標節點的隨機游走序列, 然后計算節點隨機游走序列的相似性進行鏈接預測.

隨著人工智能和機器學習技術的快速發展, 越來越多的研究人員嘗試使用機器學習方法去解決鏈接預測問題. 基于機器學習的鏈接預測方法首先需要從網絡中得到各個節點的特征向量, 然后將節點的特征向量作為機器學習算法的輸入. Hasan 等[6]將鏈接預測問題轉化為機器學習中的二分類問題,嘗試使用支持向量機[7], 多層感知機等機器學習方法進行鏈接預測, 若兩節點間未來可能產生鏈接則預測值為1, 否則為0. Freno 等[8]使用自然語言處理領域的詞袋模型對論文引用網絡中論文的摘要進行建模, 得到論文節點的特征表示, 然后使用神經網絡進行鏈接預測. Hosein 等[9]針對引文網絡使用論文作者和論文的互聚類方法進行鏈接預測.Xu 等[10]將信息熵應用于加權網絡中的鏈接預測,提出基于路徑貢獻的加權相似度指標, 實現了加權網絡的鏈接預測. Lai 等[11]針對復雜網絡, 用模塊化的置信度傳播算法來獲得網絡的底層塊結構, 并通過塊結構信息對節點間產生鏈接的可能性進行建模, 從而實現鏈接預測. Kovács 等[12]針對蛋白質相互作用網絡, 根據蛋白質之間的交互特性,使用長度為3 的網絡路徑(L3)進行鏈接預測.Pech 等[13]提出了一種新的鏈接方法, 由節點鄰居貢獻率的線性和來估計鏈接的可能性, 從而將鏈接預測問題轉化為似然矩陣的優化問題. Zhang 等[14]認為現有的相似性度量方法往往只適用于某幾種網絡, 為此提出了一種g-衰減理論來統一現有的相似性度量方法, 同時還提出了一種基于圖神經網絡(graph neural network, GNN)[15]的鏈接預測框架SEAL, 從網絡中的局部子圖來學習節點表示以進行鏈接預測. 以上方法大多是針對特定網絡提出了新的相似性度量方法. 除此之外, Ostapuk 等[16]首次將深度主動學習[17]應用于鏈接預測, 基于貝葉斯深度學習[18]提出了一種深度主動學習框架ActiveLink, 將不確定性采樣引入到聚類算法中,并且采用基于元學習[19]的無偏增量的方法進行訓練, 提高了模型的訓練速率. 相較于傳統的基于網絡結構相似度的鏈接預測方法而言, 有監督的機器學習模型使鏈接預測的結果有了明顯提升.

由于真實世界中的網絡是隨時間不斷演化的,因此雖然上述方法在大規模網絡的鏈接預測中取得了較好的成果, 但其大多僅考慮了網絡結構且大多只適用于靜態網絡, 而忽視了真實網絡中的動態信息以及節點間產生鏈接的時間信息, 因而在網絡發生變化時需要進行大量的重新計算.

2.2 動態網絡表示學習

由于復雜網絡通常包含數十億的節點和邊, 且數據具有稀疏性, 在網絡上很難直接進行復雜的推理過程, 為了有效地進行復雜網絡分析, 學者們提出了各種各樣的網絡表示學習[20]方法. 網絡表示學習作為網絡分析領域的一個重要基礎問題, 其核心思想是尋找一個映射函數將網絡中的節點轉化成低維稠密的實數向量, 即網絡節點表示. 這些網絡節點表示保存了網絡中所包含的信息, 為網絡分析任務提供了良好的特征基礎, 并可以直接用于各種網絡分析任務中, 如鏈接預測, 社團檢驗, 推薦系統等. 網絡表示學習的形式化定義如下:

對于給定網絡 G=(V,E) , 使用映射函數fv→τk為網絡中的每個節點 v∈V 學習到一個低維稠密的實數向量 Rv∈Rk作為節點的表示向量,該向量的維度 k 遠遠小于網絡節點的總個數 |V| .

由于網絡表示在常見的網絡分析任務中展現出了良好的能力, 因此越來越多的學者關注于網絡表示學習領域, 并提出了多種網絡表示學習方法,如DeepWalk[21], LINE[22], node2vec[23], SDNE[24],GCN[25], GraphSAGE[26]等.

近年來, 針對動態網絡的表示學習研究逐漸受到了研究人員的關注. 如Michael 等[27]基于復雜網絡動力學以及多元微分方程定義節點在不同時刻的表示, 提出了一種復雜網絡的多尺度動態嵌入技術. Kumar 等[28]基于遞歸神經網絡提出了JODIE模型, 對網絡中的用戶和項目分別進行動態表示學習, 并提出了一種并行批處理算法t-Batch. 李志宇等[29]通過對不同階層的網絡節點關系進行正負阻尼采樣, 構建針對新增節點的動態特征學習方法, 使得模型可以提取大規模社會網絡在動態變化過程中的結構特征. Palash 等[30]基于深度自編碼器提出DynGEM 模型, 該模型可以動態學習網絡中高度非線性的表示. 同時很多學者針對動態網絡表示學習中的鏈接預測任務進行了相關研究.Chen 等[31]將長短期記憶網絡[32](LSTM)與編碼器-解碼器體系結構相結合, 提出了一種新穎的encoder-LSTM-decoder(E-LSTM-D)深度學習模型來預測動態鏈接. Li 等[33]基于SDNE 算法提出了DDNE 模型, 使用門控循環單元[34](GRU)作為編碼器來捕獲動態網絡中的時間信息, 從而在動態網絡中進行鏈接預測. Lei 等[35]結合了圖卷積網絡(graph convolutional network, GCN)、長短期記憶網絡(long short-term memory, LSTM)以及生成對抗網絡[36](generative adversarial networks,GAN)的優勢, 用深度神經網絡(即GCN 和LSTM)來探索網絡中隱藏的拓撲結構和演化模式的非線性特征, 用GAN 來解決動態網絡中鏈接的稀疏性問題, 同時通過對抗的方式在動態網絡中進行鏈接預測. 這些研究方法大多只考慮了發生變化的節點本身的信息變化情況, 而沒有關注節點鄰域所受到的影響. 并且現有方法大多僅考慮了均勻間隔的時間間隔, 而忽視了不同時間間隔對節點偏好信息的影響. 由于網絡表示學習是網絡分析的基礎任務, 如何設計具有動態適應性的網絡表示學習模型, 學習網絡節點及其鄰域的信息變化并對它們的表示進行快速更新, 對現實世界中的網絡分析任務有著至關重要的作用.

3 基于動態網絡表示的鏈接預測模型

本文針對動態網絡的鏈接預測問題提出了基于動態網絡表示的鏈接預測模型DNRLP. 該模型對LSTM 進行了改進, 考慮了網絡演化過程中產生新信息的非平均時間間隔問題以及新信息的擴散問題, 有效地捕獲和學習了網絡中的動態信息,并得到了含有節點偏好信息的節點表示. 然后通過計算習得節點表示之間的相似度, 最終得到鏈接預測的結果.

圖2 基于動態網絡表示的鏈接預測模型結構Fig. 2. The architecture of link prediction model based on dynamic network representation.

圖2 給出DNRLP 模型的結構示意圖, DNRLP模型主要分為兩個模塊: 動態網絡表示學習模塊和鏈接預測模塊, 其中動態網絡表示學習模塊由節點信息動態更新單元和節點鄰域更新單元組成.DNRLP 模型根據 Ti時刻網絡中出現的新增信息,得到與其直接關聯的節點集合, 使用節點信息動態更新單元對該集合內的節點進行節點表示更新. 然后對該集合內的節點進行鄰域采樣, 得到與新增信息間接關聯的節點集合, 使用節點鄰域更新單元對鄰域節點進行更新, 最終得到當前時刻更新后的網絡節點表示. 基于這些節點表示使用鏈接預測模塊計算節點間的相似度并進行排序, 最終得到鏈接預測的結果.

3.1 節點信息動態更新

隨時間動態演化的網絡可以看作不同時刻下的靜態網絡, 使用 G(Vt,Et,t)表示 t 時刻的網絡,其中 Vt為該時刻的節點集合, Et為該時刻的邊集合, t 為對應的時間戳. 隨著時間的推移, 網絡中的節點會不斷地與網絡中的其他節點建立新鏈接, 這些新鏈接會改變當前節點的屬性信息. 例如在社交網絡中, 如果兩個用戶有聯系, 他們會逐漸分享共同的興趣愛好. 新鏈接的建立順序以及它們建立的時間間隔對節點屬性特征的變化也有著非常重要的影響. 按照時間戳對節點 v 新產生的鏈接進行排序得到鏈接序列 Sv={(v,vi,t0),(v,vi,t1),...,(v,vi,tn)}, 其中 (v,vi,t)表示 t時刻節點 v與節點 vi之間新建立的鏈接, vi∈Nv表示節點 v 的一階鄰域節點, Nv表示節點 v的一階鄰域節點集合; t 表示鏈接建立的時間戳, t0

綜上所述, 針對網絡中的任一節點, 當產生新鏈接時, 應該根據鏈接產生的時間間隔決定需要更新哪些新信息, 以及需要遺忘哪些歷史信息.DNRLP 模型基于LSTM 模型對網絡中的節點進行動態表示學習. LSTM 模型通過遺忘門、輸入門和輸出門解決了對歷史信息的長期依賴問題. 但是現有的LSTM 中沒有考慮不同的時間間隔對歷史信息丟棄策略所產生的影響, 因此我們根據動態網絡信息傳播規律, 在LSTM 的計算過程中增加了一個基于時間間隔的信息過濾單元(time interval based filter unit, TIFU), 從而達到了根據時間間隔的大小決定下一時刻節點對歷史信息的丟棄程度的目的, 使模型更關注節點的新增信息, 其計算單元如圖3 所示.

圖3 基于時間間隔的LSTM 單元Fig. 3. Time interval based LSTM unit.

圖3 左半部分描述了TIFU 的示意圖. TIFU的工作原理是根據時間間隔 ?t的大小, 決定當前細胞狀態信息Ct?1傳遞到下一時刻t的信息的具體計算過程如下所示:上述公式中, TIFU 將上一時刻t ?1 標準LSTM計算單元輸出的細胞狀態Ct?1分成了兩個部分:短期記憶和長期記憶. 我們認為細胞狀態Ct?1是由長期記憶和短期記憶兩個部分構成的,短期記憶對信息的存儲時間較短, 容易被遺忘, 而長期記憶對信息的存儲時間較長, 不容易被遺忘.同時短期記憶與長期記憶并不是完全割裂的, 通過重復、鞏固短期記憶可以轉化為長期記憶, 即隨著時間的流逝, 部分短期記憶可以演變為長期記憶.(1)式使用神經網絡和tanh 激活函數自動選擇歷史信息中較為短暫的歷史信息, 即單元的短期記憶, 其中為根據t ?1 時刻的細胞狀態生成的短期記憶. (2)式中為相應的需要傳遞給下一時刻t的長期記憶. TIFU 根據時間間隔 ?t對單元短期記憶的部分信息進行丟棄, 如(3)式所示, 其中為保留下來的短期記憶信息, ?t越大丟棄的短期記憶信息越多. 經過上述計算, 完成對節點歷史信息保留的決策, 并得到需要傳遞給下一時刻t的歷史信息, 如(4)式所示,將和進行組合, 并作為下一時刻t標準LSTM 單元的輸入, 即最終傳遞給下一時刻t的節點歷史信息是由節點的部分短期記憶與全部長期記憶所組成的.

圖3 中右半部分為標準LSTM 計算單元示意圖, 其具體計算過程如下所示:

其中xt為當前時刻t的輸入向量, 表示網絡的新增信息. 由于新增信息由節點vi,vj之間的新增鏈接產生, 因此可以通過計算兩節點當前表示的加權和來得到xt, 計算方式如(5)式所示. 接下來分別對標準LSTM 單元的輸入門、遺忘門及輸出門進行計算, 其中σ表示sigmoid 激活函數,⊙表示矩陣乘積運算,it,ft,ot分別代表t時刻LSTM 單元輸入門、遺忘門以及輸出門的系數.{Wi,Ui,bi},{Wf,Uf,bf}和{Wo,Uo,bo}分為上述三種門的網絡參數.表示用于更新細胞狀態ct的候選狀態.{Wc,Uc,bc}是網絡產生候選記憶的參數.ht是在時刻t時經過上述三種門的過濾后的隱藏狀態, 該狀態記錄了t時刻之前習得的所有有用信息.ct經過輸出門舍棄掉部分信息后形成當前時刻t的輸出向量ht. 根據上述TIFU 和標準LSTM 計算單元的計算過程, 可將上述過程進行如下表示:

當網絡中有新信息產生時, 使用f對關系兩端的節點信息(節點表示)進行更新, 其中Ct?1,ht?1為上一時刻f計算得到的細胞狀態和隱藏狀態,xt=W1uvi+W2uvj+b是網絡新增關系為涉及到的兩個節點vi和vj帶來的新信息,W1,W2,b是生成新信息的表示向量的模型參數.ht即為目標節點更新后的表示向量.

針對模型冷啟動問題, 在初始時刻, DNRLP模型使用網絡的鄰接矩陣作為網絡節點的表示向量, 并對網絡中每個節點進行固定大小的鄰域采樣, 然后使用聚合函數對節點鄰域內的節點表示進行聚合, 最終得到節點初始化表示向量, 并使用上述表示向量作為f的初始化的節點表示.

3.2 節點信息擴散算法和更新

網絡中兩節點vi,vj之間的新增鏈接不僅會對鏈接兩端的節點產生影響, 同時也會影響與vi,vj距離較近的節點. 因此當網絡產生新鏈接時, 涉及到的兩個節點vi,vj的鄰域節點也應該進行信息更新. 為此, DNRLP 模型通過對產生新鏈接的節點進行鄰域采樣來模擬新信息在網絡中的擴散過程,然后對采樣到的鄰域節點進行信息更新. 這么做的原因主要有三個方面: 第一, 文獻[37]表明新鏈接對整個網絡的影響往往是局部的. 第二, 由于網絡的復雜性, 與新鏈接直接關聯的節點不一定會將收集到的新信息傳播給其所有的鄰居, 同時新信息很有可能會被傳播到與其較近但不直接相鄰的節點.第三, 通過實驗發現, 當對目標節點的局部鄰域進行信息更新時, 模型的性能會更好.

在節點鄰域采樣的過程中, DNRLP 模型采用基于連接強度的隨機游走算法. 把節點間的連接強度作為隨機游走中的邊權重, 對目標節點進行加權隨機游走采樣從而得到節點vi,vj的局部鄰域. 其中邊權重的計算過程如下:

其中,uv為節點v的表示向量,Nv表示節點v的一階鄰居節點集合,fs(uvi,uv)表示節點v和其鄰域節點vi間的連接強度, 可以將該連接強度看作一個歸一化后的概率值, 根據該概率值來選擇目標節點信息在下一時刻要擴散到的節點. 圖4 給出一個簡單網絡實例, 圖中實線代表歷史鏈接, 虛線代表當前時刻新產生的鏈接. 分別對網絡中新鏈接兩端的節點v4,v5進行隨機游走. 以節點v5的隨機游走鄰域采樣為例, 其具體的隨機游走采樣策略如下:

圖4 節點鄰域采樣示意圖Fig. 4. Schematic diagram of node neighborhood sampling.

(1)建立隨機游走結果集合Rv5={}.

(2)根據邊權重概率分布隨機選擇下一節點v1,并將該節點加入Rv5中.

(3)判斷所選節點v1是否有一階鄰居, 或者其一階鄰居是否全部在Rv5中, 是則退回到上一時刻的節點重復此步驟, 否則進入下一步.

(4)重復步驟(2)和(3)直到隨機游走的結果集合達到期望的長度.

(5)若隨機游走過程中選擇的節點與結果集合中的節點重復, 則退回到上一時刻的節點重新進行選擇. 如圖中節點v2下一刻游走選擇節點v5, 則退回到節點v2重新進行決策.

表1 給出了擴散算法的偽代碼. 在表1 中,Enew代表新增鏈接的集合;v代表與新增鏈接相關聯的一個節點;m代表隨機游走了的長度;L是給定的隨機游走序列的最大長度;P表示邊權重概率分布;u代表節點v的一階鄰居;Rv代表節點v的隨機游走結果集合;R代表所有節點的隨機游走結果集合. 步驟6—8 實現節點間邊權重的計算. 步驟9 實現相關節點的鄰域采樣. 步驟4—12 實現基于連接強度的隨機游走算法, 找到了相關節點的局部鄰域Rv, 其中Rv是一個有序的隨機游走序列,越靠前的節點越容易從相關節點到達, 即相關節點的信息更容易擴散到序列中排位靠前的節點上去,刻畫出了相關節點信息的擴散過程. 整個算法得到了與新增信息直接相關的節點的隨機游走序列Rv的集合R, 描繪出了整個網絡中新增信息的擴散過程.

表1 信息擴散算法Table 1. Information diffusion algorithm.

由于新增鏈接并沒有對隨機游走序列中的節點產生直接影響, 因此新增鏈接的信息并沒有影響這些節點的歷史信息, 只帶來了新信息, 并且對于相關節點局部鄰域中較老、較遠的節點(較老的節點: 相關節點與其的交互發生在比較早先的時候或者其與隨機游走序列中的上一個節點之間的交互發生在比較早先的時候; 較遠的節點: 相關節點與其的距離比較遠)而言, 新信息對其影響較小. 綜上, DNRLP 模型根據相關節點與其隨機游走序列中的節點之間的鏈接存在的時間長短, 或者根據隨機游走序列中相鄰兩節點之間鏈接存在的時間長短, 對新信息進行處理. 建立鏈接的時間越長, 需要丟棄的新增信息越多. 同時還使用相關節點與其隨機游走序列中節點之間的距離對新信息進行進一步的處理.

DNRLP 模型設計了節點鄰域更新單元對新信息涉及到的相關節點vi的隨機游走序列進行信息更新, 更新過程如下:

式 中,v ∈Rv,indv為 節 點v在Rv中 的 索 引 號,為節點v上一時刻的細胞狀態,xt=W1uvi+W2uvj+b為節點vi和vj之間新增關系產生的新信息. 更新后節點v的表示向量為. 上述相關節點鄰域信息更新單元的結構如圖5 所示.

3.3 參數訓練

圖5 節點鄰域更新單元Fig. 5. Node neighborhood update unit.

為了在無監督方式下進行參數學習, DNRLP模型將輸出的節點表示向量hv,v ∈V應用于基于圖的損失函數, 并使用梯度下降法對模型參數進行更新. 基于圖的損失函數假設相互連接的節點有著相似的網絡表示向量, 損失函數如下:

3.4 基于動態網絡表示的鏈接預測

在網絡中相似節點在未來發生鏈接的可能性更大, 因此, 本文通過度量網絡節點之間的相似度來進行網絡鏈接預測. 通過上述動態網絡表示學習過程, 我們可以得到每次網絡演化后的新節點偏好表示, 這些節點表示保存了節點的偏好信息, 可以直接進行節點間的相似度計算, 計算過程如下:

其中,hv和hu表示兩個節點在當前時刻的表示向量,i和j表示節點偏好表示向量的分量. 相似度越大, 則節點間發生鏈接的可能性越大, 因此對網絡目標節點進行鏈接預測時, DNRLP 模型首先會計算該節點與網絡中的其余節點之間的相似度并對其進行排序, 選擇top-k 的節點作為最終鏈接預測的結果.

4 實驗分析

4.1 實驗設計

為了驗證DNRLP 模型在網絡鏈接預測任務下的性能和有效性, 本文在具有代表性的四個公開動態網絡數據集上進行了對比實驗. 這四個數據集的數據統計信息如表2 所示.

表2 動態網絡數據詳細信息Table 2. Dynamic network data details.

其中, UCI[38]是由加利福尼亞大學歐文分校的在線學生社區的用戶之間的消息通信而組成的網絡. 網絡中的節點表示社區用戶, 如果用戶之間有消息通信, 那么用戶之間就會有邊連接, 與每條邊相關聯的時間表示用戶之間的通信時間. DNC 是2016 年民主黨全國委員會電子郵件泄漏的電子郵件通信網絡. 網絡中的節點代表人員, 邊代表人員之間的郵件交互. Wikipedia talk, Chinese(Wikipedia)[39]是中文維基百科的通訊網絡, 節點表示中文維基百科的用戶, 邊表示在某一時刻某一用戶在另一用戶的對話頁上發送了一條消息.Enron[40]是由Enron 員工之間發送的電子郵件所組成的電子郵件網絡. 和DNC 一樣, 網絡中的節點代表員工, 邊代表電子郵件. 這些數據集涵蓋了多種情況, 例如: UCI 和DNC 的節點數和邊數較少, 而聚類程度較高, 形成較為密集的小網絡. 但是它們在持續時間上又有所不同, UCI 的持續時間短, 而DNC 的持續時間較長. Enron 是節點數和邊數較多, 聚類程度也較高的數據集, 形成較為密集的大網絡. 而Wikipedia 是節點數和邊數很多,持續時間很長, 但聚類程度卻極低的數據集, 形成稀疏的大網絡. 使用這些數據集, 我們可以對模型的魯棒性進行測試.

根據表1 中所述的時序網絡數據得到t時刻的網絡拓撲圖以及時間信息, 使用平均交互排序(mean reciprocal rank, MRR)指標評估鏈接預測任務的質量. MRR 計算了測試集中真實節點的排名倒數的平均值, 其計算過程如下所示:

其中,H為測試集中的節點個數, 將目標節點與和其有真實連接的節點之間的余弦相似度進行降序排序,ranki則表示了它們的余弦相似度在降序序列中所處的位置. 當測試集中的節點與目標節點間有真實連接時, 其相似度排名應盡可能靠前, 因此MRR值越大, 說明鏈接預測的質量越高, 即網絡表示越精準有效. 實驗按照時間順序選取前80%的數據作為模型的訓練數據, 后10%的數據作為驗證數據, 其余10%的數據作為測試數據. 實驗不但與現有的鏈接預測模型進行了對比, 還與使用了不同信息擴散策略的DNRLP 模型的變體進行了比較. 并且, 為了驗證DNRLP 模型的準確性,我們還選取了不同數量的訓練數據來與對比模型進行對比. 對于測試集中的每個鏈接節點對, 我們固定鏈接一端的節點, 將其看作目標節點, 計算網絡中其余節點與該目標節點的余弦相似度, 并進行降序排列.

本文還使用Recall@k指標來計算在測試數據集中真實鏈接占預測結果集中Top-k 的百分比,其計算過程如下所示:

其中σ{ranki?k}=1 表示在預測結果集中真實鏈接節點的排名ranki小于設定閾值k.Recall@k的值越大, 說明鏈接預測任務的效果越好.

此外, 本文還使用Precision@k指標來計算在測試數據集中預測結果占真實鏈接集中Top-k 的百分比, 其計算過程如下所示:

其中,σ{ranki?k}=1 表示在預測結果集中真實鏈接節點的排名ranki小于設定閾值k.Precision@k的值越大, 說明鏈接預測任務的效果越好.

鑒于機器學習模型在鏈接預測任務中的優異表現, 以及網絡表示在常見的網絡分析任務中展現出的優異能力, 本文分別使用基于機器學習的鏈接預測方法和基于網絡表示的鏈接預測方法作為對比方法. 在基于機器學習的方法中, 我們選擇兩個經典的機器學習模型, 支持向量機(SVM)模型和邏輯回歸(LR)模型. 在鏈接預測任務中, 將節點的特征向量作為SVM 和LR 模型的輸入, 通過節點的特征向量得到節點對的特征向量, 將節點對的特征向量分為有鏈接和無鏈接兩類, 從而將鏈接預測問題轉變為機器學習中的二分類問題. 在基于網絡表示的方法中, 主要通過計算節點表示之間的相似性來進行鏈接預測, 因此得到更為合適的節點表示是該類方法的主要目的. 為此我們分別選取了具有代表性的三個靜態網絡表示學習方法和三個動態網絡表示學習方法來進行對比, 靜態網絡表示學習方法包括node2vec、GCN 和GraphSAGE, 動態網絡表示學習方法包括DynGEM、GCN-GAN和DDNE. Node2vec 是一種優異的圖表示學習方法, 它利用隨機游走來捕獲網絡中的鄰近性, 并將所有節點映射到一個保持鄰近性的低維表示空間中. GCN 構建了一個半監督的節點嵌入模型, 通過對網絡拓撲結構和網絡節點特征進行編碼, 從而得到了含有豐富信息的節點表示. GraphSAGE 通過訓練聚合函數將GCN 擴展到歸納學習任務中,使其可以直接泛化到未知節點上去. DynGEM 是一種針對時間間隔固定的動態網絡的表示學習模型, 它學習到了含有時間信息的節點表示. GCNGAN 將GCN、LSTM 和GAN 相結合, 用GCN和來捕獲空間結構信息, 用LSTM 來挖掘時間信息, 最后通過對抗的方式在動態網絡中進行鏈接預測. DDNE 用GRU 作為編碼器來捕獲動態網絡中的時間信息, 從而在動態網絡中進行鏈接預測. 在上 述 模 型 中, SVM、 LR、 node2vec、 GCN 和GraphSAGE 是適用于靜態網絡的模型, 因此需要將動態網絡轉化為靜態網絡進行實驗, 即將所有時刻的網絡信息拼接到一個網絡中. 而DynGEM、GCN-GAN、DDNE 以及我們提出的DNRLP 都是適用于動態網絡的模型, 但DynGEM、GCNGAN 和DDNE 中的新鏈接建立的時間間隔是固定的, 因此在實驗中我們忽略動態網絡中不同大小的時間間隔. 實驗使用網絡的鄰接矩陣作為模型的輸入特征, 將鄰接矩陣的行向量作為節點的特征向量. 本文中所有模型的統一實驗環境如表3 所示.

實驗中各模型的參數設置如下:

SVM, LR: 根據節點的特征向量得到節點對的特征向量, 將節點對的特征向量分為兩類: 有鏈接的標為0, 無鏈接的標為1. SVM 模型的核函數選用sigmoid 函數, LR 模型則使用sag 優化算法來進行求解, 迭代次數設定為100.

表3 實驗環境設置信息Table 3. Experimental environment setup information.

node2vec: 將模型中隨機游走的數量定為20,隨機游走的步長定為40, 語言模型Skip-Gram 的窗口大小設定為10, 最終輸出的網絡表示維度為128.

GCN: 將模型中的圖卷積網絡層數設定為2,訓練過程迭代次數設定為500, 學習率設定為0.01,輸出網絡表示的維度設定為128.

GraphSAGE: 將模型中的搜索深度設定為2,鄰域采樣數量設定為20, 學習率設定為0.01, 輸出網絡表示的維度設定為128.

DynGEM: 將模型中深度編碼器的隱藏層層數設定為2, 隱藏層單元數分別設定為[256, 128],輸出的網絡表示維度設定為128.

GCN-GAN: 將模型中的圖卷積網絡層數設定為2, LSTM 隱藏層層數設定為2, 學習率設定為0.01, 輸出的網絡表示維度設定為128.

DDNE: 將模型中深度編碼器的隱藏層層數設定為2, 歷史窗口的大小設定為2, 學習率設定為0.01, 輸出的網絡表示維度設定為128.

DNRLP: 將模型中LSTM 中的隱藏單元數設定為128, 新信息擴散過程中的隨機游走步長設定為40, 輸出的網絡表示的維度設定為128.

4.2 結果分析

實驗結果如表4 所示. 通過觀察對比結果可以看出基于網絡表示學習的鏈接預測方法比基于機器學習的鏈接預測方法更加有效. 這是因為網絡表示學習方法可以對網絡節點間的關系進行深入挖掘, 從而得到更加豐富的特征信息. 在基于網絡表示學習的鏈接預測方法中, node2vec 在四個數據集上均表現一般, 主要因為node2vec 僅通過隨機游走來捕獲節點的鄰域結構, 沒有重視直接相連節點間的信息交互. 且其主要適用于靜態網絡, 忽略了網絡中的動態信息. DynGEM、GCN-GAN 和DDNE 模型是針對動態網絡的表示學習模型, 它們引入了網絡中的動態信息, 因而預測效果優于node2vec, 這說明了動態信息在網絡演化中的重要性. 但是DynGEM 和DDNE 模型的預測效果不如或者與GCN 和GraphSAGE 的效果相似, 這是因為它們僅對網絡拓撲圖的鄰接矩陣進行學習, 只得到了網絡的全局拓撲結構信息, 而忽略了網絡中的局部信息, 因而學習到的網絡特征并沒有GCN 和GraphSAGE 豐富. 而GCN 和GraphSAGE通過聚合鄰居節點的信息來模擬信息在節點間的擴散過程, 既學習到了網絡中全局信息也學習到了局部信息, 這表明了局部特征在網絡中的重要性,同時也體現出GCN 和GraphSAGE 模型適用于聚類系數較高的鄰域信息豐富的網絡. 但是GCN 和GraphSAGE 忽視了信息傳播隨時間的衰減, 沒有對信息進行遺忘, 而GCN-GAN 既考慮到了網絡中的全局特征和局部特征, 又考慮到了網絡演化過程中的動態信息, 因而效果優于GCN 和GraphSAGE. 但是GCN-GAN 模型忽視了時間間隔對信息更新的影響, 而DNRLP 模型通過信息動態更新模塊和信息擴散模塊不僅學習到了網絡的動態信息, 考慮到了節點鄰域所受的影響, 同時還考慮了時間間隔對信息更新的影響, 因此, 該模型在鏈接預測任務中較其他模型有明顯優勢. 此外,我們可以看到, 在Wikipedia 數據集上所有方法的表現均不佳, 這是因為它的聚類系數太低, 持續時間又太長, 給鏈接預測任務帶來了極大的挑戰. 同時對比于其他數據集我們可以看出在聚類系數稍高的情況下, 我們的模型效果要遠優于其他所有模型.

表4 鏈接預測MRR 結果對比Table 4. Link prediction MRR results comparison.

本文還在四個數據集上對基于表示學習的鏈接預測方法中效果較好的幾個模型計算了其在不同k值下的Recall@k指標, 實驗結果如圖6 所示.本文所提出的DNRLP 模型在不同k值下的鏈接預測效果均優于對比模型. 同時隨著k值的不斷增大,Recall@k的值也在不斷增大. 我們可以看出,DynGEM 的預測效果與GraphSAGE 的效果相似, 并且在DCN 數據集中它的表現較差, 表明了學習局部信息的重要性. 而GraphSAGE 在DCN數據集中的表現優異, 表明了GraphSAGE 強大的學習鄰域信息的能力, 也表明了GraphSAGE 適用于聚類系數較高的網絡. 在不同k值下, GCNGAN 模型的預測效果基本位列第二, 表明了同時考慮空間信息與時間信息的重要性, 而GCNGAN 的預測效果要次于DNRLP, 表明了時間間隔在網絡演化過程中的重要性. 上述實驗結果表明, DNRLP 模型可以更好的學習網絡中的節點信息, 得到含有全局信息、局部信息以及節點偏好信息的節點表示.

此外, 本文還對上述幾個模型計算了其在不同k值下的Precision@k指標, 實驗結果如圖7 所示.我 們 可 以 看 出,Precision@k指 標 與 Recall@k指標的實驗結果相似. 在DCN 數據集中, 所有方法的表現都比較好, 且當k值較小時, DNRLP 與GraphSAGE、GCN-GAN 的差別不大, 這是因為DCN 數據的聚類系數較大, 網絡中的局部信息相對重要, 而這三個模型均可以通過聚合鄰居節點的信息來更新節點表示, 體現了學習網絡中局部信息的重要性. 相反在Wikipedia 數據集上所有方法的表現均不佳, 這是因為它的聚類系數太低, 持續時間又太長, 對進行準確的鏈接預測有很大的挑戰.在四個數據集上, 本文所提出的DNRLP 模型在不同k值下的Precision@k指標均優于對比模型, 并且隨著k值的不斷增大,Precision@k的值也在不斷增大, 當k值較大時, 所提DNRLP 模型的優勢更為明顯. 實驗結果表明, 在動態網絡中DNRLP模型可以更為準確地進行鏈接預測.

圖6 各數據集上的 Recall@k 對比圖 (a) UCI 數據集; (b) DNC 數據集; (b) Wikipedia 數據集; (d) Enron 數據集Fig. 6. Recall@k comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset.

圖7 各數據集上的 Precision@k 對比圖 (a) UCI 數據集; (b) DNC 數據集; (b) Wikipedia 數據集; (d) Enron 數據集Fig. 7. Precision@k comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset.

為了驗證DNRLP 模型中用基于連接強度的隨機游走算法模擬信息擴散過程的有效性, 我們對模型的三個變體進行了對比實驗. DNRLPprop 模型是加入了基于連接強度的隨機游走算法的鏈接預測模型. DNRLP-1 st 模型是使用節點在網絡中的一階鄰域模擬信息傳播過程的鏈接預測模型. DNRLP-org 模型為不考慮新信息在網絡中的傳播的鏈接預測模型. 對比實驗結果如圖8 所示, 可以看出在四個數據集上, DNRLP-prop 模型的預測效果均優于其他兩個變體模型, 且k值越大,Recall@k的值也越大, 而DNRLP-org 模型的預測效果最差. DNRLP-org 模型的低預測效果主要是因為它忽略了信息在網絡中的擴散過程, 沒有將新信息傳播到節點鄰域中去, 這表明了信息傳播在網絡中的重要性. DNRLP-prop 模型的預測效果優于DNRLP-1st 模型的預測效果, 這主要是因為新信息的擴散往往是局部性的, 不僅會對相關節點的一跳鄰居產生影響, 也會對與其距離較近的多跳鄰居產生影響. 實驗結果表明, 動態信息對動態網絡的表示學習有著至關重要的作用, 不僅對直接相關的節點有影響, 對其周圍一定范圍內的節點也有影響. 使用基于連接強度的隨機游走算法可以有效地將網絡中的動態信息更新到受影響的節點中去.

圖8 DNRLP 模型變體的Recall@k 對比圖 (a) UCI 數據集; (b) DNC 數據集; (c) Wikipedia 數據集; (d) Enron 數據集Fig. 8. Recall@k comparison diagram of the variants of DNRLP. (a) UCI dataset; (b) DNC dataset; (c) Wikipedia dataset;(d) Enron dataset.

圖9 不同訓練率的MRR 結果對比圖 (a) DNC 數據集; (b) Enron 數據集Fig. 9. MRR results of different training rates. (a) DNC dataset; (b) Enron dataset.

此外, 為了驗證DNRLP 模型的準確性, 本文還選取了三個表現較好的模型計算了其在不同比率的訓練樣本下的MRR 指標. 我們在兩個典型的數據集上, 按照時間順序分別選取前60%, 70%,80%, 90%的數據作為訓練數據, 其余的選擇10%作為測試數據. 實驗結果如圖9 所示, 可以看出在兩個數據集上, 隨著訓練數據比率的增大,MRR 的值也在增大. 并且在任意比率下, DNRLP的訓練效果均優于對比模型, 表現了我們所提模型在鏈接預測任務中優異的性能.

5 結 論

本文針對現實世界中動態演化的網絡提出了一種基于動態網絡表示的鏈接預測模型DNRLP.該模型根據動態網絡的特性, 在標準LSTM 單元的基礎上引入了基于時間間隔的信息過濾單元, 來決策節點新、舊信息的去留. 此外, DNRLP 模型還考慮了新信息在直接相關節點鄰域內的信息傳播問題. 本文在四個動態網絡公開數據集上對模型的有效性進行了驗證, 實驗結果表明網絡中的全局信息和局部信息對學習良好的網絡表示有非常重要的作用, 同時動態網絡中的時間信息以及動態信息在網絡中的傳播對網絡節點表示的更新有著極其重要的影響. DNRLP 模型可以學習到動態網絡中豐富的信息, 能夠有效地對新信息進行快速準確地學習, 在鏈接預測任務中表現出了明顯的優勢.

由于現實世界中的網絡通常含有多類異構信息, 如社交網絡中, 除了含有用戶交互產生的網絡結構信息以外, 每個用戶還具有不同的屬性信息,包括用戶的性別、年齡、愛好等. 如何將這些信息加入到鏈接預測中, 將是一個重要的研究方向.