郭佳雯 白淇介 林鑄天 宋春瑤 袁曉潔

1(南開大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 天津 300350) 2(天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點(diǎn)實(shí)驗(yàn)室(南開大學(xué)) 天津 300350)

在當(dāng)前信息時(shí)代，現(xiàn)實(shí)世界中的各類數(shù)據(jù)天然以網(wǎng)絡(luò)圖模型存在，蘊(yùn)藏著各種豐富且復(fù)雜的信息.通過對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析和預(yù)測(cè)，人們可以挖掘數(shù)據(jù)中潛在的信息并加以利用，例如分析用戶畫像、進(jìn)行定制化內(nèi)容推薦等.但由于網(wǎng)絡(luò)數(shù)據(jù)通常以鄰接矩陣表示，規(guī)模大、維度高，難以直接作為機(jī)器學(xué)習(xí)模型的輸入進(jìn)行分析和預(yù)測(cè).因此，網(wǎng)絡(luò)表示學(xué)習(xí)或網(wǎng)絡(luò)嵌入為研究者提供了一種方法，它將高維網(wǎng)絡(luò)映射到低維向量空間，并盡可能地保留原有網(wǎng)絡(luò)的結(jié)構(gòu)和語義信息[1].

Fig. 1 Sample of dynamic heterogeneous information network圖1 動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)示意圖

現(xiàn)有的網(wǎng)絡(luò)嵌入研究大多集中在靜態(tài)網(wǎng)絡(luò)上，包括靜態(tài)同質(zhì)網(wǎng)絡(luò)嵌入和異質(zhì)信息網(wǎng)絡(luò)嵌入.在靜態(tài)網(wǎng)絡(luò)嵌入研究中，主要考慮如何對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和異質(zhì)網(wǎng)絡(luò)中語義信息進(jìn)行保留，而不考慮任何時(shí)間信息.然而，現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)會(huì)隨著時(shí)間的推移而快速發(fā)展.如圖1所示，一個(gè)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)(dynamic heterogeneous information network, DHIN)包含不同類型的節(jié)點(diǎn)和邊，并隨著時(shí)間實(shí)時(shí)變化.網(wǎng)絡(luò)的演變趨勢(shì)，我們稱之為時(shí)間特征，節(jié)點(diǎn)和邊的類型或標(biāo)簽所隱含的語義稱之為異質(zhì)特征，它們攜帶了大量包含豐富語義的信息.此外，我們希望動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入算法的時(shí)間效率能夠盡可能高，以便滿足實(shí)時(shí)性需求.

現(xiàn)有研究已經(jīng)證明，忽略網(wǎng)絡(luò)的異質(zhì)特性將由于信息損失造成嵌入質(zhì)量的下降[2].由于動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)是在異質(zhì)信息網(wǎng)絡(luò)的基礎(chǔ)上同時(shí)具備時(shí)間戳信息，因此網(wǎng)絡(luò)的邊通常產(chǎn)生在語義緊密相關(guān)但分屬不同類別的節(jié)點(diǎn)之間.并且，具有語義相關(guān)性的異質(zhì)節(jié)點(diǎn)之間的邊也經(jīng)常具有相同的時(shí)間戳.例如圖1所示，時(shí)刻t1用戶U1在話題T1上發(fā)表了博文B1，則在動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中的局部結(jié)構(gòu)為：在具有語義關(guān)聯(lián)的節(jié)點(diǎn)U1，B1，T1之間建立時(shí)間戳為t1的邊.和動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)不同的是，受異質(zhì)網(wǎng)絡(luò)語義信息的影響，語義密切相關(guān)的節(jié)點(diǎn)之間更有可能出現(xiàn)完全相同的時(shí)間戳，而非發(fā)生時(shí)間具有先后順序的、遞增的時(shí)間戳，這將為動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入中基于時(shí)間順序的隨機(jī)游走帶來新的挑戰(zhàn).

與忽略異質(zhì)特征類似，如果不考慮時(shí)間特征，同樣會(huì)發(fā)生重大的信息損失.以圖1的社交網(wǎng)絡(luò)為例.在t

近年來，越來越多的學(xué)者開始關(guān)注動(dòng)態(tài)網(wǎng)絡(luò)嵌入的問題，已經(jīng)有一些動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入的方法，如連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)嵌入(continuous-time dynamic network embeddings, CTDNE)[3]，但對(duì)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入的研究還較少.盡管網(wǎng)絡(luò)通過退化，能夠?qū)⒇S富的異質(zhì)網(wǎng)絡(luò)嵌入方法和動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法應(yīng)用于DHIN嵌入，但仍存在3個(gè)問題：1)現(xiàn)有針對(duì)動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入的方法大多是針對(duì)快照?qǐng)D設(shè)計(jì)的，而非針對(duì)實(shí)時(shí)變化的動(dòng)態(tài)圖，不能增量式地進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)，難以滿足動(dòng)態(tài)網(wǎng)絡(luò)推斷實(shí)時(shí)性的要求；2)動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入和靜態(tài)網(wǎng)絡(luò)嵌入方法會(huì)忽略網(wǎng)絡(luò)的動(dòng)態(tài)信息或異質(zhì)特征，造成嚴(yán)重的信息損失；3)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)由于其同時(shí)具備動(dòng)態(tài)和異質(zhì)特性，引入了局部結(jié)構(gòu)具有相同時(shí)間戳的新的復(fù)雜性.因此，本文提出一種針對(duì)實(shí)時(shí)演化的動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)的增量式表示學(xué)習(xí)方法，綜合考慮網(wǎng)絡(luò)的動(dòng)態(tài)和異質(zhì)信息，通過時(shí)序非遞減的隨機(jī)游走規(guī)則解決局部相同時(shí)間戳帶來的挑戰(zhàn).

動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入的一大關(guān)鍵問題是如何捕捉網(wǎng)絡(luò)實(shí)時(shí)演化信息.受CTDNE[3]的啟發(fā)，一個(gè)直接的想法是，我們?cè)趫D上進(jìn)行由時(shí)序引導(dǎo)的隨機(jī)游走，以模擬信息隨時(shí)間在網(wǎng)絡(luò)上傳遞的過程.通過這種方式，可以很容易地使模型以增量的方式進(jìn)行游走，游走經(jīng)過的邊上的時(shí)間戳遞增，并依據(jù)游走序列最后一步的時(shí)間戳進(jìn)行游走序列的接續(xù)擴(kuò)展.

但是，將時(shí)序引導(dǎo)的隨機(jī)游走應(yīng)用在動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入上仍然存在一些挑戰(zhàn).

1) 如何組織游走規(guī)則，以保證我們?cè)谛碌絹淼臅r(shí)間戳中捕捉到網(wǎng)絡(luò)中新的變化，并不失去游走的隨機(jī)性.如果直接應(yīng)用CTDNE中的游走規(guī)則，保證始終走過新時(shí)間戳或時(shí)間段上新到來的所有邊，可以很好地保留演變的趨勢(shì)，但在某些情況下存在以下2個(gè)問題.一個(gè)是當(dāng)圖的規(guī)模較大時(shí)，由于不斷到來的邊的增長(zhǎng)速度很快，且允許平行邊(即同一對(duì)節(jié)點(diǎn)間的多條邊)存在，算法所需要的內(nèi)存大小可能難以接受.另一個(gè)是，由于動(dòng)態(tài)網(wǎng)絡(luò)變化速率通常較快，并且部分動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)間信息粒度較粗，同一時(shí)間片內(nèi)會(huì)有大量新邊流入.由于在同一時(shí)間片內(nèi)涌入的大量連接之間也具有較強(qiáng)的相關(guān)性和信息的流動(dòng)，算法難以捕獲相同時(shí)間片內(nèi)部的信息，并且當(dāng)處理某些具有特殊元結(jié)構(gòu)的異質(zhì)圖時(shí)，某些類型的節(jié)點(diǎn)上可能存在大部分邊緣處于相同時(shí)間戳的情況，例如數(shù)據(jù)集AMiner[4]和DBIS[5]，其論文類型節(jié)點(diǎn)P與會(huì)議節(jié)點(diǎn)C、作者節(jié)點(diǎn)A之間，以論文發(fā)表時(shí)間作為建立連接的時(shí)間戳，因此節(jié)點(diǎn)P上所連邊一定處于相同時(shí)間戳.為了解決這一問題，我們采用和CTDNE中基于邊的隨機(jī)游走不同的方式：基于節(jié)點(diǎn)進(jìn)行隨機(jī)游走，由于網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)通常遠(yuǎn)小于邊數(shù)，因此算法所需要的內(nèi)存大小始終為節(jié)點(diǎn)數(shù)的指定倍數(shù)；此外，采用非遞減的時(shí)序約束隨機(jī)游走，允許游走在滿足一定條件下選擇那些仍在當(dāng)前時(shí)間片中的邊.

2) 如何同時(shí)保留時(shí)間特征和異質(zhì)特征.如果我們將時(shí)間約束和類型約束直接結(jié)合在隨機(jī)游走上，序列的長(zhǎng)度會(huì)因?yàn)楦鼑?yán)格的限制而變短.因此我們必須在它們之間進(jìn)行折中，允許在滿足時(shí)間約束的前提下適當(dāng)放寬對(duì)類型的約束.

3) 對(duì)于動(dòng)態(tài)圖的時(shí)間信息，我們利用的是圖流中的時(shí)間戳，而不是具體時(shí)間下的網(wǎng)絡(luò)快照，因此，節(jié)點(diǎn)、邊和時(shí)間戳的數(shù)量都會(huì)隨著時(shí)間增長(zhǎng).當(dāng)我們訓(xùn)練模型時(shí)，事先并不知道下一個(gè)時(shí)間戳?xí)l(fā)生什么，所以一些基于預(yù)知整個(gè)過程中所有節(jié)點(diǎn)和時(shí)間的深度學(xué)習(xí)方法不適合這樣的問題.因此，我們提出了一種基于增量隨機(jī)游走的新方法.

本文的主要貢獻(xiàn)包括以下3個(gè)方面:

1) 提出了一種基于隨機(jī)游走的增量算法框架TNDE(temporally non-decreasing dynamic hetero-geneous network embedding)來處理實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)嵌入的表示學(xué)習(xí).該算法能夠隨著時(shí)間的推移增量式學(xué)習(xí)，不需要預(yù)知圖的結(jié)構(gòu)、時(shí)間戳總數(shù)等額外信息，并且它基于節(jié)點(diǎn)視角來組織游走，使用有限的內(nèi)存，其上界是可預(yù)測(cè)的.

2) 提出了時(shí)序非遞減的方法來解決動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中隨機(jī)游走的時(shí)間戳陷入問題.引入類型約束以同時(shí)捕捉網(wǎng)絡(luò)的時(shí)間和異質(zhì)特征，并設(shè)計(jì)折中策略以防止由于約束過于嚴(yán)格而導(dǎo)致的游走序列過短問題.

3) 在3個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，TNDE能夠顯著提升嵌入質(zhì)量，在下游鏈路預(yù)測(cè)和節(jié)點(diǎn)分類任務(wù)上得到了2.4%～92.7%的性能提升，并在保證良好下游任務(wù)準(zhǔn)確度的前提下，大幅縮短算法運(yùn)行時(shí)間.通過比較3個(gè)特性不同的數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，證明TNDE在不同類型的網(wǎng)絡(luò)中具有良好的通用性.

1 相關(guān)工作

1.1 靜態(tài)網(wǎng)絡(luò)嵌入

靜態(tài)網(wǎng)絡(luò)包括靜態(tài)同質(zhì)網(wǎng)絡(luò)和靜態(tài)異質(zhì)網(wǎng)絡(luò).在靜態(tài)網(wǎng)絡(luò)嵌入問題上，學(xué)者們已經(jīng)做了大量的研究工作，代表性綜述包括文獻(xiàn)[1,6-8].文獻(xiàn)[9-10]是靜態(tài)異質(zhì)網(wǎng)絡(luò)嵌入上的代表性調(diào)研綜述，從背景和代表性方法到研究方向和挑戰(zhàn)進(jìn)行了全面的討論.

對(duì)于靜態(tài)同質(zhì)網(wǎng)絡(luò)嵌入，3類代表性方法包括：基于矩陣分解的方法HOPE[11]和M-NMF[12]；基于隨機(jī)游走的方法DeepWalk[13]，Node2Vec[14]和NRNR[15]；基于深度神經(jīng)網(wǎng)絡(luò)的方法SDNE[16]，SDAE[17]和SiNE[18].

對(duì)于靜態(tài)異質(zhì)網(wǎng)絡(luò)嵌入，有基于度量學(xué)習(xí)的模型PME[19]，可以同時(shí)保留一階和二階相似性；以及基于圖注意力網(wǎng)絡(luò)的方法HAN[20]和HetGNN[21].另外，部分靜態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法主要考慮單一下游任務(wù)的性能.例如，文獻(xiàn)[22]和[23]關(guān)注于節(jié)點(diǎn)分類，而文獻(xiàn)[24]則是為推薦任務(wù)設(shè)計(jì)的.

靜態(tài)異質(zhì)網(wǎng)絡(luò)嵌入中最經(jīng)典的是基于元路徑引導(dǎo)隨機(jī)游走的方法Metapath2Vec[2].它基于Deep-Walk的思想，利用word2vec[25]對(duì)圖中節(jié)點(diǎn)進(jìn)行表示學(xué)習(xí)，并通過預(yù)定義的元路徑引導(dǎo)隨機(jī)游走，以保留異質(zhì)網(wǎng)絡(luò)中的語義信息.此外，還有許多其他基于隨機(jī)游走的異質(zhì)網(wǎng)絡(luò)嵌入方法.例如，ESim[26]和HIN2Vec[27]均使用元路徑引導(dǎo)隨機(jī)游走.但是基于元路徑的方法需要依賴網(wǎng)絡(luò)的先驗(yàn)知識(shí)進(jìn)行元路徑的選取，并且元路徑選取的好壞將很大程度上影響嵌入質(zhì)量.JUST[28]方法不使用指定的元路徑，而是對(duì)不同類型的節(jié)點(diǎn)進(jìn)行有偏采樣，使得游走中下一跳的節(jié)點(diǎn)類型參照歷史類別進(jìn)行選擇，避免了基于元路徑的方法對(duì)先驗(yàn)知識(shí)和元路徑選擇依賴的問題.

1.2 動(dòng)態(tài)網(wǎng)絡(luò)嵌入

動(dòng)態(tài)網(wǎng)絡(luò)中，節(jié)點(diǎn)和邊隨時(shí)間變化，根據(jù)網(wǎng)絡(luò)動(dòng)態(tài)的呈現(xiàn)形式，通?？梢詣澐譃榭煺站W(wǎng)絡(luò)和實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)2種.快照是一種靜態(tài)圖，它存儲(chǔ)了網(wǎng)絡(luò)在某一時(shí)刻的結(jié)構(gòu).快照網(wǎng)絡(luò)指的是流式網(wǎng)絡(luò)中不同時(shí)間戳上得到的一系列快照，而實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)則是帶有時(shí)間戳的、不斷出現(xiàn)新邊和節(jié)點(diǎn)的圖流.

目前動(dòng)態(tài)網(wǎng)絡(luò)嵌入上的研究大部分集中在動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)上.Zhou等人[29]提出了一種基于三元閉合過程的模型DynamicTriad，以保留給定快照網(wǎng)絡(luò)的結(jié)構(gòu)信息和演化模式.Du等人[30]提出了一種啟發(fā)式算法DNE，將基于Skip-Gram的網(wǎng)絡(luò)嵌入方法擴(kuò)展到動(dòng)態(tài)環(huán)境中.Peng等人[31]提出了一種增量式Skip-Gram，結(jié)合現(xiàn)有的網(wǎng)絡(luò)嵌入模型Node2Vec[14]中的游走方式，能夠?qū)煺臻g的演變信息進(jìn)行良好的保留.但是上述方法主要針對(duì)快照網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)，不區(qū)分某一變化發(fā)生的具體時(shí)間戳，時(shí)間粒度粗.而對(duì)于具有時(shí)間戳、細(xì)粒度的實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)嵌入，Zuo等人[32]提出了一種基于Hawkes過程的方法HTNE來捕捉歷史信息的影響.Lee等人[3]提出了一種基于時(shí)序隨機(jī)游走的模型CTDNE，該模型采用時(shí)間戳嚴(yán)格遞增的順序進(jìn)行隨機(jī)游走.但上述針對(duì)動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)的方法，僅考慮了網(wǎng)絡(luò)的動(dòng)態(tài)特征，忽略動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)的異質(zhì)信息會(huì)造成嚴(yán)重的信息損失.

目前，越來越多的學(xué)者對(duì)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入產(chǎn)生了興趣，但其上的研究工作仍十分缺乏.例如，DANE[33]是一種用于動(dòng)態(tài)屬性網(wǎng)絡(luò)的譜方法，它能夠良好保留網(wǎng)絡(luò)的屬性標(biāo)簽和動(dòng)態(tài)特性，但它假設(shè)在訓(xùn)練過程中所有的節(jié)點(diǎn)都是事先已知的.DyHNE[34]通過元路徑增廣鄰接矩陣的擾動(dòng)來增量式捕捉變化，進(jìn)而利用特征值擾動(dòng)得到更新后的嵌入，但其對(duì)演化趨勢(shì)信息的建模能力有所欠缺，對(duì)近期頻繁發(fā)生的事件和過去頻繁發(fā)生的事件區(qū)分能力不足.受動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法DynamicTriad[29]的啟發(fā)，Bian等人提出了一種基于元路徑和三元組開/閉過程的表示學(xué)習(xí)方法Change2vec[35]，針對(duì)2個(gè)連續(xù)的靜態(tài)網(wǎng)絡(luò)快照之間的差異進(jìn)行處理，能夠兼顧網(wǎng)絡(luò)的動(dòng)態(tài)特性和異質(zhì)特性，有良好的時(shí)間效率.但其關(guān)注的是快照網(wǎng)絡(luò)而不是實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)，并且不是所有重要的變化都會(huì)導(dǎo)致三元開/閉過程.此外，動(dòng)態(tài)網(wǎng)絡(luò)上還有基于深度學(xué)習(xí)的嵌入方法，但由于其往往需要預(yù)知完整圖的節(jié)點(diǎn)集或時(shí)間戳集合而無法滿足動(dòng)態(tài)網(wǎng)絡(luò)實(shí)時(shí)增量具有不可預(yù)知性的要求.

綜上所述，現(xiàn)有網(wǎng)絡(luò)嵌入方法主要集中在靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)上，動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法仍較少；且現(xiàn)有動(dòng)態(tài)方法大多針對(duì)快照網(wǎng)絡(luò)，而非實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)，難以捕獲細(xì)粒度時(shí)間信息；基于譜方法或深度神經(jīng)網(wǎng)絡(luò)的方法由于其時(shí)間空間開銷大，且大多需要預(yù)知全圖信息，而難以適應(yīng)實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的需要.因此，除現(xiàn)有動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法外，能夠解決實(shí)時(shí)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入問題的最接近的路線包括：可在不同時(shí)間點(diǎn)上反復(fù)調(diào)用的靜態(tài)異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法，忽略動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)類型信息的動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法和基于隨機(jī)游走的動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法.因此我們分別從上述路線中各自選取了代表性的算法作為實(shí)驗(yàn)對(duì)比方法.

2 實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)中的基本概念

在詳細(xì)描述我們的算法之前，首先給出實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)嵌入問題的形式化定義和相關(guān)概念，并對(duì)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中由于局部結(jié)構(gòu)上時(shí)間戳相同帶來的時(shí)間戳陷入問題進(jìn)行描述.

2.1 問題定義

在本節(jié)中，我們首先利用文獻(xiàn)[3,6,9,36]中的異質(zhì)信息網(wǎng)絡(luò)和實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的形式化定義給出定義1和定義2，并給出實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)的定義.然后形式化說明實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)表示學(xué)習(xí)問題，并說明表示學(xué)習(xí)問題的輸入和輸出.

定義1.異質(zhì)信息網(wǎng)絡(luò).給定一個(gè)無向圖G=(V,E,L)，其中V={v1,v2,…,vn}代表節(jié)點(diǎn)集，E={e1,e2,…,em}代表邊集，L=Lv∪Le代表節(jié)點(diǎn)和邊的類型集合.當(dāng)類型數(shù)量|L|>2，且滿足節(jié)點(diǎn)類型數(shù)量|Lv|≥1，邊類型數(shù)量|Le|≥1時(shí)，該無向圖被稱為異質(zhì)信息網(wǎng)絡(luò).

定義2.無向?qū)崟r(shí)動(dòng)態(tài)網(wǎng)絡(luò).給定一個(gè)無向圖G=(V,E,Γ)，其中V和E分別代表節(jié)點(diǎn)和邊的集合，允許兩節(jié)點(diǎn)u,v之間建立多條直連邊，Γ代表映射函數(shù)Γ：E→+，即任意邊ei=(u,v,t)∈E，對(duì)應(yīng)正實(shí)數(shù)域上一個(gè)時(shí)間戳t，則該無向圖被稱為實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò).

值得注意的是，本文關(guān)注的是具有連續(xù)時(shí)間戳的實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)，而非將動(dòng)態(tài)網(wǎng)絡(luò)切割成一系列網(wǎng)絡(luò)靜態(tài)狀態(tài)的快照網(wǎng)絡(luò).換而言之，我們關(guān)注的是有連續(xù)邊輸入的圖流.定義3描述了本文的主要研究對(duì)象.

定義3.實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò).實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)是同屬于異質(zhì)信息網(wǎng)絡(luò)和實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的無向圖G=(V,E,L,Γ)，允許在同一對(duì)節(jié)點(diǎn)之間建立多條連接.其中，V代表節(jié)點(diǎn)集，E代表邊集，L代表節(jié)點(diǎn)和邊的類型集合，Γ：E→+表示將邊映射到相應(yīng)時(shí)間戳的函數(shù).

由于實(shí)時(shí)動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)是基于流的，并允許同一對(duì)節(jié)點(diǎn)之間存在平行邊，因此快照網(wǎng)絡(luò)和實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的嵌入方法有一些關(guān)鍵區(qū)別.首先，它們捕捉的是不同粒度的動(dòng)態(tài)特征.快照通常不包含時(shí)間戳，并且快照間的時(shí)間間隔較長(zhǎng)，因此把快照間的差異稱為粗粒度的變化；而在實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中，每條邊都攜帶時(shí)間戳，因此把某一時(shí)刻下網(wǎng)絡(luò)的變化稱為細(xì)粒度的變化.實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的嵌入方法通常利用具體的時(shí)間戳來捕捉細(xì)粒度的時(shí)間特征，而快照網(wǎng)絡(luò)的模型則是處理2個(gè)連續(xù)快照之間的粗粒度變化.其次，它們對(duì)平行邊問題的態(tài)度不同.快照網(wǎng)絡(luò)嵌入通常將快照處理成簡(jiǎn)單圖，不考慮平行邊；而在實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)嵌入中，同一對(duì)節(jié)點(diǎn)間在不同時(shí)刻可能產(chǎn)生多次連接，因此需考慮平行邊，以便捕獲到細(xì)粒度時(shí)間信息.

本文目標(biāo)是通過捕捉異質(zhì)特征和時(shí)間特征來學(xué)習(xí)實(shí)時(shí)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)的低維向量表示.該模型以一個(gè)無向的、具有平行邊的實(shí)時(shí)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)G=(V,E,L,Γ)作為輸入.若節(jié)點(diǎn)數(shù)|V|=n，則最終輸出一個(gè)n×d的矩陣，其中d?n，各行d維向量即為保留了拓?fù)涮卣?、異質(zhì)語義信息和時(shí)間特征的節(jié)點(diǎn)表示.

2.2 時(shí)間戳陷入問題

由于本文算法的主要挑戰(zhàn)之一是解決在動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)上進(jìn)行時(shí)序隨機(jī)游走時(shí)產(chǎn)生的時(shí)間戳陷入問題.因此，在介紹具體解決方式前，本節(jié)將對(duì)時(shí)間戳陷入問題產(chǎn)生的原因及過程進(jìn)行描述.

實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)在演化過程中，隨著事件的不斷發(fā)生而在節(jié)點(diǎn)之間生成新的邊連接，因此邊建立的先后順序?qū)㈦[含信息的傳遞方向.例如將圖2的動(dòng)態(tài)網(wǎng)絡(luò)看作郵件網(wǎng)絡(luò)的一個(gè)表示，節(jié)點(diǎn)v1分別于時(shí)刻t1,t2,t3向v2,v3,v5發(fā)送工作郵件，v5通過一段時(shí)間的整理，再于時(shí)刻t4向v4發(fā)送工作郵件，即完成一次從節(jié)點(diǎn)v1到v4的郵件信息傳遞.由于在實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中，網(wǎng)絡(luò)的動(dòng)態(tài)信息是通過邊上的時(shí)間戳來表示，因此針對(duì)實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的嵌入方法需要關(guān)注時(shí)間戳中動(dòng)態(tài)信息的建模方式，通過時(shí)序遞增引導(dǎo)隨機(jī)游走即可建模網(wǎng)絡(luò)中潛在的信息傳遞語義.

Fig. 2 Time trapped problem on dynamic network圖2 動(dòng)態(tài)網(wǎng)絡(luò)上的時(shí)間戳陷入問題

以圖2為例，t1≤t2≤t3≤t4，在動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)上應(yīng)用時(shí)序遞增引導(dǎo)隨機(jī)游走，從節(jié)點(diǎn)v1出發(fā)得到序列{v1,v5,v4}，能夠模擬信息從v1到v4的信息傳遞過程.但是游走到v4后，如果允許時(shí)間戳停留在游走當(dāng)前的時(shí)間戳，則下一跳將返回v5.由于v4和v5沒有時(shí)間戳大于t4的邊，則將從v5再次走到v4，在兩節(jié)點(diǎn)之間反復(fù)游走直到滿足序列長(zhǎng)度限制，從而造成在t4時(shí)間戳上的陷入問題.

時(shí)間戳陷入問題即可描述為：在無向?qū)崟r(shí)動(dòng)態(tài)網(wǎng)絡(luò)上，由于時(shí)序非減的隨機(jī)游走允許時(shí)間戳停留在當(dāng)前時(shí)刻，而造成的在某一時(shí)間戳上隨機(jī)游走陷入局部少數(shù)節(jié)點(diǎn)之間的反復(fù)游走、進(jìn)而降低模型準(zhǔn)確度的問題.

為解決這一問題，動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法CTDNE采用時(shí)間戳嚴(yán)格遞增的方式游走，即不允許游走停留在上一時(shí)刻，回避了時(shí)間戳陷入的前提條件.而在時(shí)間戳粒度較大的網(wǎng)絡(luò)中，例如以年為單位的引文網(wǎng)絡(luò)中，某年同一會(huì)議上發(fā)表的論文具有相同的時(shí)間戳.這意味著在某個(gè)階段，它們對(duì)同一個(gè)領(lǐng)域感興趣，這是重要的時(shí)間信息.規(guī)定時(shí)間戳嚴(yán)格遞增的約束，可能會(huì)造成游走序列過短、丟失重要語義信息、訓(xùn)練效果差的情況.

區(qū)別于動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)，動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)由于其同時(shí)具備異質(zhì)網(wǎng)絡(luò)特性和時(shí)間信息而存在更為復(fù)雜的結(jié)構(gòu).異質(zhì)網(wǎng)絡(luò)特性將使得不同類別的節(jié)點(diǎn)之間的不同類別的邊具有更豐富的語義信息.因此在動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入過程中，我們一方面需要利用網(wǎng)絡(luò)當(dāng)中的時(shí)間戳信息來建模網(wǎng)絡(luò)演化模式，另一方面還需要綜合考慮網(wǎng)絡(luò)中不同類別的節(jié)點(diǎn)和邊所代表的語義信息.

而值得注意的是，在異質(zhì)網(wǎng)絡(luò)中，由于每個(gè)具有語義信息的事件往往涉及到多類別的節(jié)點(diǎn)，事件發(fā)生這一動(dòng)作將引起多類節(jié)點(diǎn)之間同時(shí)產(chǎn)生多條邊連接，從而該邊上具有完全相同的時(shí)間戳，而不具有事件發(fā)生的先后順序.例如圖1中，節(jié)點(diǎn)B4上所連接的時(shí)間戳為t6的邊表示時(shí)刻t6用戶U2在話題T2上發(fā)表博文B4.如果不允許時(shí)間戳停留在上一跳的時(shí)刻，則當(dāng)游走從U2走到B4后，將在B4處終止或轉(zhuǎn)向時(shí)刻t8收藏了該文的用戶U3(t8>t6)，無法形成“某用戶某時(shí)刻在某話題上發(fā)表某博文”這一核心語義的游走序列(“用戶-博文-話題”).因此，在動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中，由于大量存在局部結(jié)構(gòu)上邊的時(shí)間戳相同的情況，不允許停留在當(dāng)前時(shí)間戳將使得在異質(zhì)網(wǎng)絡(luò)中無法產(chǎn)生具有緊密語義聯(lián)系的游走序列，因此需設(shè)計(jì)能夠解決時(shí)間戳陷入問題的時(shí)序非遞減的游走策略.

3 基于時(shí)序非遞減的增量嵌入模型TNDE

在本節(jié)中，我們提出了實(shí)時(shí)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)上的一種基于時(shí)序非遞減隨機(jī)游走的增量表示學(xué)習(xí)方法(temporally non-decreasing dynamic heterogeneous network embedding, TNDE).首先給出模型整體框架，然后分別對(duì)于模型中時(shí)序非遞減的算法和增量更新策略細(xì)節(jié)進(jìn)行描述.

3.1 模型框架

在介紹模型的細(xì)節(jié)之前，首先對(duì)TNDE算法進(jìn)行概述.第1步采用滑動(dòng)窗口模擬網(wǎng)絡(luò)動(dòng)態(tài)演化，第2步處理網(wǎng)絡(luò)中待更新的序列，第3步根據(jù)游走策略進(jìn)行增量游走，最后使用增量式Skip-Gram學(xué)習(xí)更新后的序列.圖3展示了TNDE的算法框架.

Fig. 3 Framework of TNDE圖3 TNDE模型框架

受CTDNE[3]中提出的時(shí)序游走的啟發(fā)，為了更好地保留動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中的時(shí)間特征，特別是在相同時(shí)間片上的具有強(qiáng)語義的時(shí)間信息，同時(shí)避免時(shí)間戳陷入問題，我們提出了一種基于非遞減時(shí)序的隨機(jī)游走方法.根據(jù)當(dāng)前游走的歷史情況，允許游走有一定概率在當(dāng)前時(shí)間戳下繼續(xù)延伸，并將時(shí)序約束與類型有偏引導(dǎo)隨機(jī)游走相結(jié)合，綜合考慮了網(wǎng)絡(luò)的時(shí)序和異質(zhì)信息.與CTDNE不同，本文中序列的游走方式從節(jié)點(diǎn)角度進(jìn)行組織，從而將算法的空間開銷從O(|E|)降至O(|V|)，并便于后續(xù)進(jìn)行序列的接續(xù)游走等增量更新.游走算法的具體細(xì)節(jié)在3.2節(jié)中描述.

由于動(dòng)態(tài)網(wǎng)絡(luò)在不斷演進(jìn)的過程中，節(jié)點(diǎn)表示除受當(dāng)前新增信息影響外，還受歷史信息的影響，因此通過對(duì)節(jié)點(diǎn)的游走序列進(jìn)行增量更新，再利用更新后的節(jié)點(diǎn)序列進(jìn)行向量表示的增量式學(xué)習(xí)，能夠綜合當(dāng)前和歷史信息，并減少計(jì)算開銷，加速算法運(yùn)行.每當(dāng)滑動(dòng)窗口移動(dòng)，有新的邊到來時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)相關(guān)的游走序列將會(huì)出現(xiàn)序列段失效刪除或能夠進(jìn)行接續(xù)游走的情況.此外，為保證最新時(shí)間上的信息得到保留，模型依據(jù)指定比例p選取一定數(shù)量的序列進(jìn)行逆向的非遞減時(shí)序隨機(jī)游走，通過反轉(zhuǎn)序列使其等價(jià)于正向游走.在得到新時(shí)刻的游走序列后，為了縮短運(yùn)行時(shí)間，并保持所學(xué)到的向量表示在下游任務(wù)中的推斷能力，采用增量式Skip-Gram模型[31]學(xué)習(xí)，得到最終的節(jié)點(diǎn)向量表示.增量更新算法細(xì)節(jié)在3.3節(jié)中進(jìn)行描述.

TNDE的整體框架如算法1所示.通過滑動(dòng)窗口模擬圖流，在每個(gè)滑動(dòng)窗口中，對(duì)當(dāng)前有效節(jié)點(diǎn)采用incrementalUpdateW(3.3節(jié))增量式更新相關(guān)的游走序列，并選定后續(xù)需要接續(xù)游走和逆序游走的序列位置，之后對(duì)上述序列調(diào)用temporalRW函數(shù)(3.2節(jié))進(jìn)行時(shí)序非遞減的隨機(jī)游走，將各有效節(jié)點(diǎn)增量更新后的游走序列作為增量式Skip-Gram函數(shù)incrementalSkipGram(3.3節(jié))的輸入，增量學(xué)習(xí)給定的動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)G在當(dāng)前時(shí)刻的向量表示X.

算法1.TNDE算法框架.

輸入：動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)G、類別停留概率衰減因子α、時(shí)間停留概率衰減因子β、逆序更新比例p、最終向量表示維度d；

輸出：動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)節(jié)點(diǎn)表示X.

①T←getSortedTime(G)；/*將圖G中所有時(shí)間戳排序放入集合T中供滑動(dòng)窗口運(yùn)行*/

② 初始化walks為空；

③ for 第i次滑動(dòng)窗口在T上滑動(dòng)

④Gi←getValidGraph(T,i)；

⑤ 初始化Wvalid為空；

⑥ forGi中每個(gè)節(jié)點(diǎn)vj

⑦walksj←incrementalUpdateW(Gi,

vj,walk,p)；

⑧walksj←temporalRW(Gi,vj,walksj)；

⑨ 把walksj加入Wvalid；

⑩ end for

3.2 融合類型約束的非遞減時(shí)序隨機(jī)游走

本節(jié)描述算法中核心的融合類型約束的非遞減時(shí)序隨機(jī)游走策略，即算法1中的temporalRW函數(shù).

在第2節(jié)介紹時(shí)間戳陷入問題時(shí)已經(jīng)提到，在現(xiàn)實(shí)生活或?qū)嶋H應(yīng)用中，由于數(shù)據(jù)標(biāo)記的時(shí)間戳粒度不同，仍然會(huì)有在同一時(shí)間戳上新增的邊；并且在動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中，由異質(zhì)節(jié)點(diǎn)形成的強(qiáng)語義局部結(jié)構(gòu)上的邊往往具有相同的時(shí)間戳.因此，為了更好地保留時(shí)間信息，基于時(shí)間戳約束的隨機(jī)游走算法應(yīng)允許游走過程中停留在當(dāng)前時(shí)間片，同時(shí)需要解決允許時(shí)間停留引起的時(shí)間戳陷入問題.因此，我們提出了一種基于歷史游走信息的非遞減時(shí)序隨機(jī)游走的策略.

非遞減時(shí)序隨機(jī)游走是指在給定無向?qū)崟r(shí)動(dòng)態(tài)網(wǎng)絡(luò)G=(V,E,Γ)上，沿著時(shí)間戳非遞減有序的方向選取邊進(jìn)行隨機(jī)游走.所形成的節(jié)點(diǎn)序列{v1,v2,…,vl}滿足3個(gè)條件：

1) 對(duì)于任意1≤i

2) 對(duì)于任意1≤i

3) 選擇Γ(vi,vi+1)=Γ(vi+1,vi+2)的概率隨著在同一時(shí)間戳上連續(xù)停留次數(shù)的增加而降低.

上述時(shí)序游走策略中的第3點(diǎn)要求即是為了解決時(shí)間戳陷入問題而設(shè)計(jì)的.當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)沒有足夠多的滿足時(shí)間條件的鄰居，或者同一時(shí)間戳的邊數(shù)遠(yuǎn)遠(yuǎn)多于更遠(yuǎn)時(shí)間戳的邊數(shù)時(shí)，如果不限制時(shí)間停留概率，就很容易造成時(shí)間戳陷入問題，在局部節(jié)點(diǎn)之間徘徊，從而損害模型性能.

式(1)描述了節(jié)點(diǎn)v在時(shí)間戳ti中停留的概率，

(1)

如圖4所示，不同形狀分別表示不同類別的節(jié)點(diǎn).當(dāng)前節(jié)點(diǎn)v的上一跳節(jié)點(diǎn)為節(jié)點(diǎn)u，當(dāng)前游走時(shí)間戳為t1，且已n次停留在時(shí)間戳t1，則v的下一跳仍選擇時(shí)間戳t1邊的概率為βn，選擇大于t1的時(shí)間戳的概率為1-βn.由于當(dāng)前節(jié)點(diǎn)上的邊具有多個(gè)時(shí)間戳，令Tv表示v上大于t1的所有時(shí)間戳集合，Tv={t2,t3}.下一跳選擇Tv中任一時(shí)間戳的概率為(1-βn)/|Tv|.

Fig. 4 Sample of non-decreasing temporal random walk圖4 非遞減時(shí)序隨機(jī)游走示意圖

隨機(jī)游走的引導(dǎo)策略基于以下2個(gè)原則：一是隨機(jī)游走中采樣的邊要滿足邊上時(shí)間戳非遞減的條件，以保留網(wǎng)絡(luò)的時(shí)序信息；二是要滿足異質(zhì)網(wǎng)絡(luò)類型選擇的要求.

在采用不同的時(shí)間和異質(zhì)信息約束的情況下，二者共同作用的方式有所區(qū)別.受文獻(xiàn)[28]啟發(fā)，這里我們采用基于歷史游走類型進(jìn)行有偏類型選擇的策略，以避免元路徑約束過于嚴(yán)格，和時(shí)間約束相疊加后，滿足條件的序列長(zhǎng)度短的問題.并且我們還采取折中方案，優(yōu)先考慮時(shí)間約束，在滿足時(shí)間約束的前提下盡可能在類別約束引導(dǎo)下前進(jìn).

式(2)描述了在下一跳選定時(shí)間戳ti的前提下，節(jié)點(diǎn)v下一跳仍在類別l中停留的概率：

(2)

其中，l為節(jié)點(diǎn)v的類別，Nv(ti,l)為時(shí)間戳ti節(jié)點(diǎn)v的類別為l的鄰居，Nv(ti)為在時(shí)間戳ti與v相連的所有鄰居，m為序列在當(dāng)前類別下已游走的長(zhǎng)度，α為控制停留在當(dāng)前節(jié)點(diǎn)相同域的概率衰減速度參數(shù).α越大則游走越傾向于停留在相同的節(jié)點(diǎn)類別中，α越小則游走越傾向于探索其他類別的節(jié)點(diǎn).本文中，為良好保留動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)的類別信息，參考JUST[28]中參數(shù)設(shè)置，α=0.2.

以圖4為例，當(dāng)節(jié)點(diǎn)v已選定下一跳時(shí)間戳t2后，將在該時(shí)間戳下的鄰居中進(jìn)行節(jié)點(diǎn)類別的選擇.令Lv表示該時(shí)間戳下v的鄰居類別集合，且不包含v自身的類別l1.若節(jié)點(diǎn)v不具有類別為l1的鄰居時(shí)，從Lv中任選一個(gè)類別；若v只有類別為l1的鄰居時(shí)，選擇類別l1；若v既有類別為l1的鄰居，還有其他類型的鄰居，且已停留在l1類別m次，如圖4所示，則仍選取類型l1的概率為αm，選擇其他類型的概率為1-αm.由于可能存在多種其他類別，因此選擇其中某類別的概率為(1-αm)/|Lv|.

本節(jié)描述的時(shí)序非遞減的方法，能夠解決動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)中隨機(jī)游走的時(shí)間戳陷入問題，引入類型約束以同時(shí)捕捉網(wǎng)絡(luò)的時(shí)間和異質(zhì)特征，并設(shè)計(jì)折中策略以平衡時(shí)間和類型信息的重要性，防止由于約束過于嚴(yán)格而導(dǎo)致的游走序列過短問題.

3.3 增量游走更新與增量表示學(xué)習(xí)策略

在本節(jié)中，我們將討論模型中使用的增量策略.正如在算法框架中所述，TNDE選定需要以增量的方式更新的游走序列，即函數(shù)incrementalUpdateW，包括需要接續(xù)游走和逆序游走的序列位置，對(duì)其應(yīng)用上述時(shí)序隨機(jī)游走策略進(jìn)行增量游走；最后將更新后的相關(guān)游走序列作為增量Skip-Gram的輸入，即函數(shù)incrementalSkipGram.

3.3.1 增量游走更新incrementalUpdateW

首先介紹增量游走的工作原理.一方面由于實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中歷史信息對(duì)節(jié)點(diǎn)嵌入的影響需要得到保留，增量式更新游走序列能夠減少歷史信息的計(jì)算開銷;另一方面事件的影響具有時(shí)間衰減效應(yīng)，近期頻繁發(fā)生的事對(duì)當(dāng)前狀態(tài)的影響更大，因此需要處理3個(gè)問題：如何沿著現(xiàn)有的路徑繼續(xù)游走，如何剔除現(xiàn)有路徑中的失效數(shù)據(jù)，如何保持最新的數(shù)據(jù)始終被學(xué)到.

為了滿足增量游走的要求，首先對(duì)于每個(gè)節(jié)點(diǎn)，算法維護(hù)了一組由節(jié)點(diǎn)ID標(biāo)識(shí)的游走序列.在隨時(shí)間增量式更新游走序列的過程中，每條由節(jié)點(diǎn)ID標(biāo)識(shí)的序列反映了與該節(jié)點(diǎn)相關(guān)的變化，這些序列對(duì)影響其對(duì)應(yīng)節(jié)點(diǎn)的網(wǎng)絡(luò)變化敏感.

每條序列可以看作是一個(gè)隨著游走不斷進(jìn)行而不斷滑動(dòng)的滑動(dòng)窗口.為了在處理接續(xù)游走和無效數(shù)據(jù)丟棄時(shí)節(jié)省時(shí)間和空間，我們將一個(gè)序列劃分為多個(gè)子窗口，子窗口的長(zhǎng)度為L(zhǎng)W.對(duì)于每個(gè)子窗口，只需要記錄其中最新的邊時(shí)間戳和節(jié)點(diǎn)類型.當(dāng)子窗口中最新的時(shí)間戳無效時(shí)，整個(gè)子窗口內(nèi)的序列將被丟棄.由于我們將一個(gè)子窗口作為一個(gè)操作單元，忽略了子窗口中各個(gè)具體的時(shí)間戳和節(jié)點(diǎn)類型等細(xì)節(jié)，因此LW越大，算法的成本越低.在本文實(shí)驗(yàn)中，我們使用LW=2作為默認(rèn)值.

網(wǎng)絡(luò)中發(fā)生的變化包括節(jié)點(diǎn)或邊的產(chǎn)生和消失.變化影響的區(qū)域是變化部分的直接連接節(jié)點(diǎn).當(dāng)網(wǎng)絡(luò)中的滑動(dòng)窗口移動(dòng)，新的時(shí)間片到達(dá)時(shí)，對(duì)于未受變化影響的節(jié)點(diǎn)，由節(jié)點(diǎn)ID標(biāo)識(shí)的現(xiàn)有游走序列剔除失效數(shù)據(jù)，其他保持不變.而對(duì)于受變化影響的節(jié)點(diǎn)，更新相應(yīng)的、以其節(jié)點(diǎn)ID標(biāo)識(shí)的游走序列.序列的增量式更新策略主要包括以下4種，分別對(duì)應(yīng)圖3中標(biāo)號(hào)：Ⅰ.無變化序列保留，Ⅱ.剔除現(xiàn)有序列中的無效節(jié)點(diǎn)和邊，Ⅲ.延續(xù)現(xiàn)有游走序列，Ⅳ.在新的時(shí)間片上逆向游走生成序列.

Ⅰ. 無變化序列保留，即對(duì)于不涉及變化的序列保持不變.

Ⅱ. 剔除現(xiàn)有序列中的無效數(shù)據(jù)是針對(duì)網(wǎng)絡(luò)當(dāng)前所有有效節(jié)點(diǎn)的對(duì)應(yīng)序列，以序列子窗口為單位，檢查子窗口時(shí)間戳是否已過期失效.若失效，則整個(gè)子窗口丟棄.

Ⅲ. 延續(xù)游走序列同理，在需要進(jìn)行延續(xù)的序列上，檢查最新子窗口的時(shí)間戳和類別信息，應(yīng)用3.2節(jié)中介紹的時(shí)序游走策略，在現(xiàn)有序列基礎(chǔ)上進(jìn)行游走.

Ⅳ. 在新的時(shí)間片上逆向游走則是為了保證能夠?qū)W到更新的數(shù)據(jù).這里提到的逆向游走就是非遞減時(shí)序游走的反向過程.正向游走是從歷史信息沿著時(shí)間戳非遞減的方向往近期游走，而逆向游走則是從當(dāng)前時(shí)刻沿著時(shí)間戳非遞增的方向往歷史數(shù)據(jù)游走.為了捕捉最新的演化信息，保持歷史信息的效果，并且不增加過多的計(jì)算成本，我們?cè)O(shè)置參數(shù)p來控制新變化節(jié)點(diǎn)開始的反向游走的比例.本文根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)設(shè)置p=0.2，以保證運(yùn)行時(shí)間與準(zhǔn)確度的平衡.

由于動(dòng)態(tài)場(chǎng)景下，網(wǎng)絡(luò)連接變化靈活，因此在不同情況下逆向游走序列的更新數(shù)目也不同.令每個(gè)節(jié)點(diǎn)標(biāo)識(shí)的游走序列數(shù)為r，則r×p為反向游走的標(biāo)準(zhǔn)比例.式(3)所示為節(jié)點(diǎn)v標(biāo)識(shí)的r條游走序列中需要逆序游走更新的序列數(shù)：

(3)

其中，newC為當(dāng)前節(jié)點(diǎn)v上有效邊數(shù)，oldC為節(jié)點(diǎn)v標(biāo)識(shí)的序列中尚未完全失效的歷史游走序列數(shù).即當(dāng)有效邊數(shù)較少，與歷史序列之和未達(dá)到序列總數(shù)上限或有效邊數(shù)未達(dá)到標(biāo)準(zhǔn)比例r×p時(shí)，逆向游走生成newC條序列；當(dāng)有效邊數(shù)和歷史序列數(shù)都較多，均能超過其對(duì)應(yīng)標(biāo)準(zhǔn)比例r×p和r-r×p時(shí)，生成標(biāo)準(zhǔn)比例數(shù)目的逆向游走序列r×p條(取整)；其他情況即為有效邊數(shù)較多而歷史序列數(shù)較少，但其二者之和超過序列總數(shù)上限，則生成r-oldC條逆向游走，使序列總數(shù)達(dá)到上限，盡可能利用空閑空間.

3.3.2 增量表示學(xué)習(xí)incrementalSkipGram

在增量式更新游走序列后，我們將更新后的節(jié)點(diǎn)涉及的序列輸入增量式Skip-Gram模型進(jìn)行節(jié)點(diǎn)增量表示學(xué)習(xí)，即函數(shù)incrementalSkipGram.該模型建模網(wǎng)絡(luò)中的變化節(jié)點(diǎn)帶來的影響，沿用前次Skip-Gram訓(xùn)練后的模型參數(shù)，對(duì)變化的節(jié)點(diǎn)序列增量式進(jìn)行表示學(xué)習(xí)，模型Loss函數(shù)為

(4)

4 實(shí) 驗(yàn)

為了評(píng)估TNDE嵌入算法的性能，驗(yàn)證模型效用，在本節(jié)中，我們選取了4個(gè)代表性對(duì)比算法和TNDE進(jìn)行比較，在3個(gè)真實(shí)數(shù)據(jù)集中評(píng)估它們?cè)阪溌奉A(yù)測(cè)和節(jié)點(diǎn)分類這2個(gè)下游任務(wù)中的性能.所有算法均使用Python實(shí)現(xiàn)，運(yùn)行在一臺(tái)配備Intel Core i7 3.40 GHz處理器和64 GB內(nèi)存的機(jī)器上.本文已公開TNDE的源代碼(1)https://github.com/guaw/TNDE.

4.1 數(shù)據(jù)集

實(shí)驗(yàn)選取3個(gè)不同領(lǐng)域、不同大小且具有不同結(jié)構(gòu)的數(shù)據(jù)集，表1為它們的統(tǒng)計(jì)信息.

Table 1 Information of Datasets表1 數(shù)據(jù)集信息

DBLP.文獻(xiàn)[37]提供了DBLP數(shù)據(jù)集的許多版本.我們選擇了2014年5月的DBLP集合，使用了其提供的10個(gè)領(lǐng)域子集數(shù)據(jù).該網(wǎng)絡(luò)由“發(fā)表”和“合著”信息組成，其中節(jié)點(diǎn)類型包括作者(A)和會(huì)議(C)，A-C和A-A形式的邊分別表示發(fā)表和合著關(guān)系，其局部結(jié)構(gòu)上具有強(qiáng)語義信息.邊上的時(shí)間戳代表建立關(guān)系的年份，時(shí)間戳數(shù)量較少且粒度粗，每一時(shí)間片內(nèi)的平均邊速率高.

Enron.該數(shù)據(jù)集由文獻(xiàn)[38]提供，是從安然公司收集的電子郵件通信網(wǎng)絡(luò).該網(wǎng)絡(luò)包含了公司內(nèi)部115名員工之間發(fā)送的43 160封郵件，具有豐富的類型信息.節(jié)點(diǎn)類型是員工的職位，每條邊上的時(shí)間戳表示郵件的發(fā)送時(shí)間.為便于后續(xù)描述，我們用1～9的數(shù)字代替具體文本來表示每個(gè)不同的節(jié)點(diǎn)類型.

TKY.該數(shù)據(jù)集文獻(xiàn)[39]是由FourSquare提供的用戶在東京的簽到數(shù)據(jù).節(jié)點(diǎn)類別包括用戶(U)和地點(diǎn)(P)兩類，每條邊上的時(shí)間表示用戶在某地簽到的時(shí)間.該網(wǎng)絡(luò)為二部圖，具有豐富的細(xì)粒度時(shí)間戳信息，并具有一定數(shù)量的相同時(shí)間片上的邊.

4.2 對(duì)比方法與實(shí)驗(yàn)設(shè)置

由于當(dāng)前流行的基于圖神經(jīng)網(wǎng)絡(luò)的算法時(shí)間復(fù)雜度較高，難以適應(yīng)實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)的嵌入要求，例如目前最先進(jìn)的針對(duì)動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入的DySAT[40]和針對(duì)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入的LIME[41]，其時(shí)間復(fù)雜度遠(yuǎn)高于其他基于隨機(jī)游走的模型方法.因此我們選擇以下4種不同的基于隨機(jī)游走的對(duì)比方法進(jìn)行比較，靜態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法JUST、分別針對(duì)實(shí)時(shí)動(dòng)態(tài)和快照的動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法CTDNE和ISGNS、針對(duì)快照的動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法Change2vec.上述方法的時(shí)間復(fù)雜度如表2所示，其中采樣和嵌入分別表示模型在對(duì)應(yīng)階段的時(shí)間復(fù)雜度.

Table 2 Time Complexity表2 時(shí)間復(fù)雜度

為保證公平性，實(shí)驗(yàn)過程中各方法涉及到的所有通用參數(shù)均保持一致，節(jié)點(diǎn)向量的維度d=128，從每個(gè)節(jié)點(diǎn)或(在CTDNE中)從每條邊出發(fā)的游走輪數(shù)r=10，游走序列最大長(zhǎng)度l=80.考慮到不同數(shù)據(jù)集的時(shí)間戳數(shù)量和粒度，在各方法實(shí)驗(yàn)過程中，對(duì)于不同數(shù)據(jù)集滑動(dòng)窗口的設(shè)置為：在Enron上滑動(dòng)步長(zhǎng)為5，共滑動(dòng)4次；在DBLP上滑動(dòng)步長(zhǎng)為10，共滑動(dòng)5次；在TKY上滑動(dòng)步長(zhǎng)為10 000，共滑動(dòng)56次.對(duì)于靜態(tài)網(wǎng)絡(luò)嵌入方法，則在滑動(dòng)窗口每次移動(dòng)后的位置對(duì)當(dāng)前網(wǎng)絡(luò)快照進(jìn)行表示學(xué)習(xí)；對(duì)于針對(duì)快照網(wǎng)絡(luò)的方法，則學(xué)習(xí)各相鄰快照之間的差異信息.

JUST[28]是一種靜態(tài)異質(zhì)信息網(wǎng)絡(luò)嵌入方法，基于類別信息能夠動(dòng)態(tài)調(diào)整游走偏好的類別.為了更好地捕捉節(jié)點(diǎn)的類別信息，游走類別初始停留概率參數(shù)α=0.2，使得游走過程中算法傾向于經(jīng)過異質(zhì)邊探索新類型的節(jié)點(diǎn)，而少有比率選擇同質(zhì)邊進(jìn)而停留在當(dāng)前節(jié)點(diǎn)類別.其余參數(shù)均選取原作默認(rèn)設(shè)置.為保證實(shí)驗(yàn)公平性，TNDE中對(duì)應(yīng)的類別停留參數(shù)α也設(shè)置為0.2.

CTDNE[3]是一種實(shí)時(shí)動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法，其中隨機(jī)游走以邊為角度進(jìn)行組織，按照時(shí)間戳嚴(yán)格遞增順序選取下一條邊.每條游走序列最小長(zhǎng)度w=5，算法中批量更新的大小與滑動(dòng)窗口滑動(dòng)步長(zhǎng)保持一致，以保證CTDNE能夠在有限時(shí)間戳數(shù)量的網(wǎng)絡(luò)中生成符合要求的游走序列，且序列不過短.

ISGNS[31]是一種針對(duì)快照的動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法，該算法游走階段采用node2vec中的策略.超參數(shù)按照node2vec默認(rèn)設(shè)置為p=1，q=1.

Change2vec[35]是一種針對(duì)快照的動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法，使用元路徑引導(dǎo)隨機(jī)游走.為保證元路徑選取的質(zhì)量，各數(shù)據(jù)集上使用的元路徑均基于該數(shù)據(jù)集語義進(jìn)行選取，并且考慮到選取不同元路徑對(duì)于模型方法效果的影響，在實(shí)驗(yàn)中綜合考慮了多條元路徑進(jìn)行隨機(jī)游走.具體來說，對(duì)于DBLP，我們使用元路徑ACA和CAC來引導(dǎo)從每個(gè)節(jié)點(diǎn)開始的隨機(jī)游走.對(duì)于TKY，使用UPU和PUP來引導(dǎo).對(duì)于Enron，由于其節(jié)點(diǎn)類型多，尋找具有良好語義信息的長(zhǎng)元路徑比較困難，我們針對(duì)不同類型選擇了一系列短元路徑：1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9,9-1.這些元路徑表示的是2個(gè)職位的員工之間頻繁的溝通關(guān)系，并且這樣選取元路徑能夠保留圖中類別之間的整體關(guān)聯(lián)性，沒有將網(wǎng)絡(luò)根據(jù)不同類別完全分割成互不相連的域.

4.3 運(yùn)行時(shí)間

在實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中，對(duì)網(wǎng)絡(luò)嵌入的需求會(huì)隨時(shí)、頻繁地發(fā)生，因此，為了滿足動(dòng)態(tài)網(wǎng)絡(luò)嵌入的需求，算法的運(yùn)行時(shí)間非常重要.在保證下游推斷任務(wù)具有良好準(zhǔn)確度的前提下，算法的時(shí)間成本越低越好.因此在本節(jié)中，我們首先對(duì)TNDE和其他4種對(duì)比方法所需的運(yùn)行時(shí)間進(jìn)行了評(píng)估.表3為各方法分別在3個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的運(yùn)行總時(shí)間.

Table 3 Runtime表3 運(yùn)行時(shí)間 s

從表3中可以看出，靜態(tài)模型JUST和基于邊視角組織游走的動(dòng)態(tài)方法CTDNE在表示學(xué)習(xí)上花費(fèi)的時(shí)間較多.每當(dāng)需要獲得嵌入的時(shí)候，靜態(tài)模型都要在當(dāng)前全圖上運(yùn)行，完全重新訓(xùn)練模型.因此，從實(shí)驗(yàn)結(jié)果也能夠看出，靜態(tài)方法JUST在各數(shù)據(jù)集上的時(shí)間開銷均為最大，和其他動(dòng)態(tài)方法的運(yùn)行時(shí)間相差1～2個(gè)數(shù)量級(jí).靜態(tài)方法應(yīng)用在動(dòng)態(tài)網(wǎng)絡(luò)嵌入問題上，由于其運(yùn)行時(shí)間過長(zhǎng)而難以適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)嵌入在時(shí)間實(shí)時(shí)性方面的需要，因此后續(xù)推斷任務(wù)準(zhǔn)確度不再與靜態(tài)方法進(jìn)行對(duì)比.

而對(duì)于CTDNE，每當(dāng)一定量新邊到來時(shí)都會(huì)嘗試多次隨機(jī)游走，保留滿足長(zhǎng)度要求的序列，即嘗試生成的序列數(shù)為網(wǎng)絡(luò)中邊的倍數(shù).但實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中允許相同節(jié)點(diǎn)對(duì)之間具有平行邊，這意味著邊數(shù)可以遠(yuǎn)大于節(jié)點(diǎn)數(shù).因此，CTDNE比我們基于節(jié)點(diǎn)視角的游走花費(fèi)的時(shí)間有數(shù)量級(jí)的增長(zhǎng)，尤其是在邊密集的網(wǎng)絡(luò)上，例如平均節(jié)點(diǎn)度為750.61的Enron.在該網(wǎng)絡(luò)上CTDNE的運(yùn)行時(shí)間高達(dá)靜態(tài)方法JUST的19倍、動(dòng)態(tài)方法的數(shù)百上千倍.

根據(jù)表3運(yùn)行時(shí)間結(jié)果和下游任務(wù)準(zhǔn)確度(4.4節(jié))可知，與對(duì)比方法相比，Enron數(shù)據(jù)集上，TNDE方法取β<0.9的情況下所需時(shí)間均為最短，且鏈路預(yù)測(cè)指標(biāo)AUC達(dá)到0.77～0.91，與對(duì)比方法相當(dāng)，甚至有所提升；鏈路預(yù)測(cè)指標(biāo)Micro為0.24～0.32不等，弱于Change2vec但與另2種動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法相當(dāng).在DBLP和TKY上，TNDE取β=0用時(shí)僅次于Change2vec方法，相比另2種動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)嵌入方法運(yùn)算時(shí)間降低了39.06%～97.46%.雖然在DBLP和TKY上，應(yīng)用Change2vec所需要的時(shí)間比TNDE短，但從4.4節(jié)展示的實(shí)驗(yàn)結(jié)果可以看出，它在下游任務(wù)中幾乎沒有表現(xiàn)出歸納能力，而TNDE方法在下游任務(wù)中具有出色的歸納結(jié)果.因此，綜合考慮算法運(yùn)行時(shí)間與下游任務(wù)準(zhǔn)確度，TNDE在不同數(shù)據(jù)集上具有良好的通用性，綜合表現(xiàn)最優(yōu)，可以在保持歸納性能的前提下，大大縮短學(xué)習(xí)嵌入的運(yùn)行時(shí)間.

4.4 下游任務(wù)準(zhǔn)確度對(duì)比分析

在本節(jié)中，我們針對(duì)實(shí)時(shí)動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入方法保留時(shí)間信息和異質(zhì)信息的能力，分別通過鏈路預(yù)測(cè)和節(jié)點(diǎn)分類2個(gè)下游任務(wù)來進(jìn)行評(píng)估.在分析具體實(shí)驗(yàn)數(shù)據(jù)之前，我們注意到2個(gè)下游任務(wù)在一定程度上具有相反的趨勢(shì)，即鏈路預(yù)測(cè)效果出眾的方法，在節(jié)點(diǎn)分類上的實(shí)驗(yàn)效果往往欠佳.其原因在于鏈路預(yù)測(cè)任務(wù)是通過邊的2個(gè)端點(diǎn)向量的相似度來判斷未來是否會(huì)出現(xiàn)這條邊，兩端點(diǎn)向量的余弦相似度越大，未來節(jié)點(diǎn)間產(chǎn)生連接的可能性就越大；節(jié)點(diǎn)分類任務(wù)則恰恰相反，是通過節(jié)點(diǎn)向量之間的距離來劃分不同的類別，節(jié)點(diǎn)相似度越高，被歸入同一類別的可能性就越大.

而值得注意的是，在異質(zhì)網(wǎng)絡(luò)中，無論是動(dòng)態(tài)還是靜態(tài)，經(jīng)常發(fā)生關(guān)聯(lián)的節(jié)點(diǎn)通常分別屬于不同的類別.因此，當(dāng)嵌入模型在鏈路預(yù)測(cè)任務(wù)中表現(xiàn)良好時(shí)，意味著2個(gè)屬于不同類別的端點(diǎn)在嵌入空間中很接近，使得分類器很難準(zhǔn)確地分辨它們，從而導(dǎo)致在節(jié)點(diǎn)分類任務(wù)中表現(xiàn)不佳，反之同理.

4.4.1 鏈路預(yù)測(cè)

為模擬實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)嵌入在鏈路預(yù)測(cè)任務(wù)中的動(dòng)態(tài)變化情況，每組數(shù)據(jù)集上的實(shí)驗(yàn)隨著滑動(dòng)窗口的每次滑動(dòng)進(jìn)行評(píng)估.由于TKY數(shù)據(jù)集時(shí)間片數(shù)量多，窗口滑動(dòng)次數(shù)多，因此我們將每滑動(dòng)10次的位置作為一個(gè)時(shí)間點(diǎn)，從中選取了5個(gè)重要的時(shí)間點(diǎn)，報(bào)告該時(shí)刻網(wǎng)絡(luò)的鏈路預(yù)測(cè)指標(biāo).實(shí)驗(yàn)使用當(dāng)前時(shí)刻下網(wǎng)絡(luò)的嵌入表示，計(jì)算節(jié)點(diǎn)之間的余弦相似度，使用從當(dāng)前時(shí)間點(diǎn)到下一次評(píng)估的時(shí)間點(diǎn)之間的數(shù)據(jù)作為測(cè)試集正例，從網(wǎng)絡(luò)中抽取與正例等量的負(fù)例共同組成測(cè)試集，并使用AUC來評(píng)估當(dāng)前時(shí)刻鏈路預(yù)測(cè)結(jié)果的性能.AUC值越高，說明鏈路預(yù)測(cè)結(jié)果越好；AUC越接近0.5，表示鏈路預(yù)測(cè)效果越差，接近隨機(jī)預(yù)測(cè).實(shí)驗(yàn)報(bào)告了各評(píng)估時(shí)間點(diǎn)上的AUC，以及AUC的平均得分，結(jié)果如表4所示，報(bào)告了TNDE在β控制下的最優(yōu)結(jié)果，其中在DBLP和Enron上取β=1，在TKY上取β=0.5.

Table 4 AUC of DBLP Link Prediction表4 DBLP鏈路預(yù)測(cè)指標(biāo)AUC

根據(jù)表4數(shù)據(jù)并綜合考慮算法的運(yùn)行時(shí)間可以看出，在時(shí)間明顯縮短的條件下，TNDE仍然可以取得良好的鏈路預(yù)測(cè)效果；并且，通過調(diào)節(jié)時(shí)間停留概率參數(shù)β，能夠在犧牲一定時(shí)間效率的情況下取得較大的性能提升.同為處理動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入的Change2vec表現(xiàn)最差，盡管其運(yùn)行時(shí)間短，但在DBLP和TKY上幾乎沒有推斷能力.

在TKY數(shù)據(jù)集下，TNDE方法選取β=0.5時(shí)的實(shí)驗(yàn)結(jié)果，其時(shí)間開銷與CTDNE相當(dāng)，AUC提升了2.4%，與ISGNS和Change2vec相比提升了15.2%～47.5%.并且在算法取β=0，即時(shí)間開銷遠(yuǎn)低于CTDNE和ISGNS的情況下，TNDE的AUC仍能達(dá)到0.700，比ISGNS和Change2vec高3.1%～32.0%.

在DBLP數(shù)據(jù)集下，實(shí)驗(yàn)報(bào)告了TNDE模型取β=1時(shí)的結(jié)果.相比ISGNS，AUC降低了9.5%，但其時(shí)間效率提升了12.5%；相比CTDNE，AUC提升了30.5%，運(yùn)行時(shí)間效率提升了49.7%.

在Enron數(shù)據(jù)集下，表4中報(bào)告了TNDE取β=1的情況，運(yùn)行時(shí)間略有升高但能取得3.5%～18.5%的鏈路預(yù)測(cè)性能提升，β=0.9的情況下，運(yùn)行時(shí)間略有下降，AUC仍能達(dá)到0.915，有2.5%～17.4%的提升.

4.4.2 節(jié)點(diǎn)分類

本節(jié)中使用邏輯回歸分類器進(jìn)行節(jié)點(diǎn)多標(biāo)簽分類任務(wù).數(shù)據(jù)集按時(shí)間戳順序被分成2部分，前75%作為訓(xùn)練集，后25%作為測(cè)試集.每組實(shí)驗(yàn)重復(fù)5次，并分別報(bào)告Macro-F1和Micro-F1的平均分?jǐn)?shù)以評(píng)估分類效果[42].分?jǐn)?shù)越高，說明嵌入在節(jié)點(diǎn)分類任務(wù)中的性能越好.實(shí)驗(yàn)結(jié)果如表5所示，其中報(bào)告了TNDE在β控制下的最優(yōu)結(jié)果，在DBLP，Enron和TKY上β分別取0.5，0.8和0.9.

從表5中可以看出,Change2vec方法在DBLP和TKY數(shù)據(jù)集中分類表現(xiàn)欠佳，但其在Enron數(shù)據(jù)集上明顯高于其他算法.這是因?yàn)镃hange2vec算法在抽取快照間差異后，在其上進(jìn)行了基于元路徑引導(dǎo)的隨機(jī)游走.由于指定元路徑能夠人為地干預(yù)隨機(jī)游走中游走路徑的選擇，使得所生成的序列將指定元路徑中相關(guān)聯(lián)的節(jié)點(diǎn)聚集得比較近，而沒有通過元路徑關(guān)聯(lián)起來的節(jié)點(diǎn)類型離得很遠(yuǎn).因此，在DBLP和TKY兩個(gè)具有明顯局部結(jié)構(gòu)、節(jié)點(diǎn)類別較少的網(wǎng)絡(luò)中，元路徑帶來的積極影響不突出.而在Enron數(shù)據(jù)集中，節(jié)點(diǎn)類別較多，且節(jié)點(diǎn)類別與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間是弱耦合的關(guān)系，則指定元路徑的游走方式能更好地協(xié)助模型生成具有良好分類能力的節(jié)點(diǎn)嵌入.TNDE在Enron數(shù)據(jù)集上僅次于Change2vec算法，且在另外2個(gè)數(shù)據(jù)集上都能取得最好的節(jié)點(diǎn)分類結(jié)果.

Table 5 Macro-F1 and Micro-F1 of Node Classification表5 節(jié)點(diǎn)分類指標(biāo)Macro-F1和Micro-F1

由于不同類別的節(jié)點(diǎn)數(shù)量存在差距，Macro-F1指標(biāo)的差異更為明顯.在DBLP數(shù)據(jù)集上，表5報(bào)告了TNDE取β=0.5下的實(shí)驗(yàn)結(jié)果，與各對(duì)比方法相比，Macro-F1能夠提高7.9%～60.6%，且從表3可以看出，與ISGNS和CTDNE相比，算法運(yùn)行時(shí)間降低92%～95.4%.在Enron中，TNDE取β=0.8，雖然Macro-F1低于Change2vec，但相比CTDNE和ISGNS兩種動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)方法有27.5%～50.2%的提升，且算法運(yùn)行時(shí)間為3.22 s，比3種對(duì)比方法用時(shí)下降了28.4%～99.91%.在TKY數(shù)據(jù)集上，TNDE取β=0.9，Macro-F1能夠提高11.4%～92.7%；考慮到算法運(yùn)行時(shí)間，β=0時(shí)算法運(yùn)行時(shí)間效率相比ISGNS提升了39.1%，盡管Macro-F1相比ISGNS下降了14.95%，但仍能達(dá)到0.723，且比CTDNE和Change2vec仍有38.3%～47.1%的提升.

從異質(zhì)性信息的角度考慮，CTDNE和ISGNS方法均針對(duì)動(dòng)態(tài)同質(zhì)網(wǎng)絡(luò)，忽略網(wǎng)絡(luò)的異質(zhì)信息，從表5的實(shí)驗(yàn)結(jié)果來看，這2種方法在節(jié)點(diǎn)分類任務(wù)上低于本文方法TNDE，本文方法能夠在Macro-F1上取得7.9%～92.7%的提升，在異質(zhì)性更強(qiáng)的Enron數(shù)據(jù)集上表現(xiàn)提升尤其明顯，能夠體現(xiàn)不考慮異質(zhì)性的信息丟失問題.

綜上所述，與其他對(duì)比方法相比，TNDE方法在大多數(shù)情況下能夠取得最好的節(jié)點(diǎn)分類結(jié)果，能夠?qū)?dòng)態(tài)異質(zhì)網(wǎng)絡(luò)的異質(zhì)信息進(jìn)行良好保留，在不同類型的網(wǎng)絡(luò)中具有很好的通用性；并且通過調(diào)節(jié)時(shí)間停留概率參數(shù)β，能在保證良好分類效果的情況下大大減少算法的運(yùn)行時(shí)間.

4.4.3 小 結(jié)

理論分析與實(shí)驗(yàn)結(jié)果均顯示，這2個(gè)不同的推斷任務(wù)由于任務(wù)本身特性而難以同時(shí)達(dá)到最優(yōu)結(jié)果，即在鏈接預(yù)測(cè)中表現(xiàn)較好的方法在節(jié)點(diǎn)分類中往往表現(xiàn)較差，反之同理.實(shí)驗(yàn)還表明，TNDE可以顯著提升鏈路預(yù)測(cè)和節(jié)點(diǎn)分類的準(zhǔn)確度，良好保留動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)的時(shí)間和異質(zhì)信息，并在保證良好鏈路預(yù)測(cè)和分類效果的前提下，獲得運(yùn)行時(shí)間效率的大幅提升.

4.5 參數(shù)分析

4.5.1 參數(shù)β影響分析

本節(jié)中，我們從算法運(yùn)行時(shí)間、下游任務(wù)準(zhǔn)確度方面評(píng)估了算法中的參數(shù)β對(duì)嵌入質(zhì)量的影響.選定α=0.2，將β從0到1分別取{0，0.1，0.3，0.5，0.7，0.8，0.9，1}.圖5～8分別展示了算法運(yùn)行時(shí)間、鏈路預(yù)測(cè)AUC、節(jié)點(diǎn)分類Macro-F1和Micro-F1指標(biāo)的變化情況.由于不同數(shù)據(jù)集所用時(shí)間差異較大，為了在同一張圖中更清晰地表示算法運(yùn)行時(shí)間在3個(gè)不同數(shù)據(jù)集中的變化趨勢(shì)，圖5分別設(shè)置了2個(gè)時(shí)間刻度，左軸為TKY，DBLP所用時(shí)間刻度，右軸為Enron所用刻度.

Fig. 5 The variation of runtime with β圖5 運(yùn)行時(shí)間隨β變化情況

Fig. 6 The variation of AUC with β圖6 AUC隨β變化情況

Fig. 7 The variation of Macro-F1 with β圖7 Macro-F1隨β變化情況

Fig. 8 The variation of Micro-F1 with β圖8 Micro-F1隨β變化情況

如圖5所示，算法運(yùn)行時(shí)間隨著β的增大而增加.其主要原因在于，參數(shù)β決定了初始狀態(tài)下，時(shí)序游走過程中選擇仍在當(dāng)前時(shí)刻的邊的概率，以及概率的衰減速度.參數(shù)β較大則游走傾向于停留在當(dāng)前時(shí)間片的邊中，β較小則游走傾向于選擇更遠(yuǎn)的時(shí)間點(diǎn)上的邊.由于β的增大實(shí)際上是對(duì)嚴(yán)格增時(shí)序約束限制的放寬，允許游走的范圍隨著β而變大，進(jìn)而生成的隨機(jī)游走序列長(zhǎng)度也會(huì)增長(zhǎng)，引起算法運(yùn)行時(shí)間的上升.

實(shí)驗(yàn)數(shù)據(jù)顯示，在β<0.9時(shí)，網(wǎng)絡(luò)表示學(xué)習(xí)時(shí)間隨β的增大近似線性增長(zhǎng)，而當(dāng)β逼近1時(shí)，算法運(yùn)行時(shí)間陡增.時(shí)間陡增的主要原因是，β逼近1意味著網(wǎng)絡(luò)中每次進(jìn)行隨機(jī)游走時(shí)，有極大的概率選擇當(dāng)前時(shí)間片內(nèi)的邊，而難以向更遠(yuǎn)的時(shí)間游走，產(chǎn)生時(shí)間戳的陷入，導(dǎo)致游走序列長(zhǎng)、算法運(yùn)行時(shí)間長(zhǎng).結(jié)合圖6～8的下游任務(wù)指標(biāo)也能夠看出，對(duì)于時(shí)間粒度細(xì)、局部結(jié)構(gòu)具有較少相同時(shí)間片的數(shù)據(jù)集，例如TKY，當(dāng)β=1時(shí)下游任務(wù)效果具有明顯下降.

因此，對(duì)于時(shí)間粒度細(xì)、局部結(jié)構(gòu)具有較少相同時(shí)間片的數(shù)據(jù)集則可將β調(diào)小，使得游走更傾向于向遠(yuǎn)方時(shí)間點(diǎn)探索.而對(duì)于時(shí)間片較少、相同時(shí)間戳下具有大量邊的數(shù)據(jù)集，如Enron和DBLP，則可將β適當(dāng)調(diào)大，以便在相同時(shí)間片內(nèi)的邊上進(jìn)行較為充分的游走探索.同時(shí)注意，由于β逼近1時(shí)存在的運(yùn)行時(shí)間陡增和算法性能下降的趨勢(shì)，β可調(diào)至0.8左右，以保證算法在運(yùn)行時(shí)間和嵌入質(zhì)量上均具有良好表現(xiàn).

4.5.2 參數(shù)α影響分析

在本節(jié)中，我們同樣從算法運(yùn)行時(shí)間、下游任務(wù)準(zhǔn)確度方面評(píng)估了算法中的參數(shù)α對(duì)嵌入質(zhì)量的影響.實(shí)驗(yàn)選定β=0.7，將α從0到1分別取{0，0.2，0.4，06，0.8，1}.圖9～12分別展示了算法運(yùn)行時(shí)間、鏈路預(yù)測(cè)AUC、節(jié)點(diǎn)分類Macro-F1和Micro-F1指標(biāo)的變化情況.由于不同數(shù)據(jù)集所用時(shí)間差異較大，為了在同一張圖中更清晰地表示算法運(yùn)行時(shí)間在3個(gè)不同數(shù)據(jù)集中的變化趨勢(shì)，圖9分別設(shè)置了2個(gè)時(shí)間刻度，左軸為TKY,DBLP所用時(shí)間刻度，右軸為Enron所用刻度.

Fig. 9 The variation of runtime with α圖9 運(yùn)行時(shí)間隨α變化情況

Fig. 10 The variation of AUC with α圖10 AUC隨α變化情況

Fig. 11 The variation of Macro-F1 with α圖11 Macro-F1隨α變化情況

Fig. 12 The variation of Micro-F1 with α圖12 Micro-F1隨α變化情況

如圖9所示，算法運(yùn)行時(shí)間隨著α的增大而基本持平，在節(jié)點(diǎn)類別較多的Enron數(shù)據(jù)集上，運(yùn)行時(shí)間隨α的增大而略有下降.其主要原因在于，參數(shù)α決定了初始狀態(tài)下，時(shí)序游走過程中下一跳仍選擇當(dāng)前類別節(jié)點(diǎn)的概率，以及概率的衰減速度.參數(shù)α較大則游走傾向于選擇仍為當(dāng)前類別的節(jié)點(diǎn)，α較小則游走傾向于選擇不同類別的節(jié)點(diǎn).由于α的增大實(shí)際上是傾向于游走中選擇相同類別的節(jié)點(diǎn)，在少類別的數(shù)據(jù)集中對(duì)游走過程允許范圍的影響較小，進(jìn)而對(duì)生成的隨機(jī)游走序列長(zhǎng)度影響較小，因此算法運(yùn)行時(shí)間基本持平.而在Enron數(shù)據(jù)集中由于類別更多，當(dāng)α增大時(shí)，傾向于在相同類別間游走，減少了跨越不同類別的游走，因此算法運(yùn)行時(shí)間略有下降.

在實(shí)驗(yàn)設(shè)置中，鏈路預(yù)測(cè)任務(wù)是面向未來鏈接的預(yù)測(cè)，其主要考察模型嵌入對(duì)于網(wǎng)絡(luò)動(dòng)態(tài)演化模式、動(dòng)態(tài)信息的建模和保留能力；而節(jié)點(diǎn)分類任務(wù)面向節(jié)點(diǎn)的類別進(jìn)行劃分，主要考察模型嵌入對(duì)于網(wǎng)絡(luò)類別信息，即網(wǎng)絡(luò)異質(zhì)信息的建模和保留能力.

由圖10能夠看出，面向網(wǎng)絡(luò)動(dòng)態(tài)演化模式的鏈路預(yù)測(cè)任務(wù)對(duì)于調(diào)節(jié)類別的參數(shù)α不敏感.僅在α逼近1時(shí)，由于將游走約束在一類節(jié)點(diǎn)上，忽略了不同類別節(jié)點(diǎn)之間的關(guān)系，從而導(dǎo)致鏈路預(yù)測(cè)結(jié)果下降.

由圖11，12的節(jié)點(diǎn)分類結(jié)果能夠看出，對(duì)于類別較多、不同節(jié)點(diǎn)類別間關(guān)系松散的數(shù)據(jù)集Enron來說，隨著α的增大，隨機(jī)游走的范圍將逐漸收縮到某一類別的節(jié)點(diǎn)，能夠聚集該類別的節(jié)點(diǎn)信息，使得相同類別節(jié)點(diǎn)的向量表示彼此接近，而不同類別節(jié)點(diǎn)的向量表示相距較遠(yuǎn)，利于節(jié)點(diǎn)分類任務(wù).對(duì)于節(jié)點(diǎn)類別和邊類別較少的二部圖TKY來說，α對(duì)于游走類別影響有限，因此算法時(shí)間和下游任務(wù)指標(biāo)對(duì)α變化不敏感.對(duì)于同樣節(jié)點(diǎn)類別較少但分布不均勻的DBLP來說，當(dāng)α逼近1時(shí)，大量游走序列集中在數(shù)量較多的A類別節(jié)點(diǎn)上，引起分類結(jié)果的下降.

因此，對(duì)于節(jié)點(diǎn)類別較少的數(shù)據(jù)集，如DBLP和TKY，可將α調(diào)小，使得游走更傾向于向不同類別節(jié)點(diǎn)探索.而對(duì)于類別豐富的數(shù)據(jù)集，如Enron，可將α適當(dāng)調(diào)大，以便捕獲同類節(jié)點(diǎn)之間的關(guān)系.需要注意，由于α逼近1時(shí)算法性能有下降趨勢(shì)，建議在0～0.8對(duì)α取值，以保證算法綜合考慮類別信息，在運(yùn)行時(shí)間和嵌入質(zhì)量上均具有良好表現(xiàn).

5 結(jié) 論

在這項(xiàng)工作中，我們提出了一種基于時(shí)序隨機(jī)游走的動(dòng)態(tài)異質(zhì)信息網(wǎng)絡(luò)增量表示學(xué)習(xí)框架TNDE，該框架設(shè)計(jì)了允許時(shí)間停留在當(dāng)前時(shí)間片的非遞減時(shí)序隨機(jī)游走策略，保留了動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)嵌入強(qiáng)語義局部結(jié)構(gòu)中的時(shí)間信息，并引入基于節(jié)點(diǎn)類型的有偏游走概率以保留網(wǎng)絡(luò)異質(zhì)信息.使用更新參數(shù)p來平衡最新信息和歷史信息的比例，使用時(shí)間停留概率衰減因子β來平衡停留在當(dāng)前時(shí)間和向更遠(yuǎn)時(shí)間探索的概率，并通過使用子窗口對(duì)游走序列進(jìn)行增量式更新和使用增量Skip-Gram來進(jìn)行增量式表示學(xué)習(xí)，降低算法運(yùn)行成本.實(shí)驗(yàn)結(jié)果表明，與靜態(tài)異質(zhì)網(wǎng)絡(luò)方法相比，TNDE能夠顯著降低算法運(yùn)行時(shí)間；與其他動(dòng)態(tài)嵌入方法相比，TNDE可以顯著提升鏈路預(yù)測(cè)和節(jié)點(diǎn)分類的準(zhǔn)確度，良好保留動(dòng)態(tài)異質(zhì)網(wǎng)絡(luò)的時(shí)間和異質(zhì)信息，并在保證良好鏈路預(yù)測(cè)和分類效果的前提下，獲得運(yùn)行時(shí)間效率的大幅提升.

作者貢獻(xiàn)聲明：郭佳雯負(fù)責(zé)論文方法構(gòu)建、部分對(duì)比實(shí)驗(yàn)和論文寫作；白淇介負(fù)責(zé)部分對(duì)比實(shí)驗(yàn)和部分論文修改工作；林鑄天負(fù)責(zé)部分對(duì)比實(shí)驗(yàn)；宋春瑤和袁曉潔提供了論文方法思路指導(dǎo)和論文撰寫指導(dǎo).