吳安彪,袁 野,馬玉亮,王國仁

1(東北大學(xué) 計算機科學(xué)與工程學(xué)院,遼寧 沈陽 110169)

2(北京理工大學(xué) 計算機學(xué)院,北京 100081)

3(東北大學(xué) 工商管理學(xué)院,遼寧 沈陽 110169)

基于計算機超高速的運算能力,人們設(shè)計出了面向高維數(shù)據(jù)、多層次的神經(jīng)網(wǎng)絡(luò)的模型.在深度學(xué)習(xí)領(lǐng)域中的圖數(shù)據(jù)方向,由于圖數(shù)據(jù)結(jié)構(gòu)的非歐式屬性,在神經(jīng)網(wǎng)絡(luò)研究初期,人們并沒有找到一種針對圖數(shù)據(jù)行之有效的網(wǎng)絡(luò)模型.所以,如何將高維度的圖數(shù)據(jù)結(jié)構(gòu)抽象成低維度、結(jié)構(gòu)性的向量,然后通過神經(jīng)網(wǎng)絡(luò)對得出的節(jié)點向量進(jìn)行參數(shù)訓(xùn)練,是一件非常有挑戰(zhàn)性的工作.

2009 年,Scarselli 等人[1]首次提出了圖神經(jīng)網(wǎng)絡(luò)模型(graph neural network model,簡稱GNN)的概念,并且文中的基本也是通過整合鄰居節(jié)點的屬性來進(jìn)行對節(jié)點的向量化表達(dá),給出了一種圖表達(dá)學(xué)習(xí)的研究雛形,一定程度上指導(dǎo)了后來一些研究者們在基于屬性圖表達(dá)學(xué)習(xí)方向的研究思路,但是在當(dāng)時并未引起學(xué)者們的廣泛關(guān)注.直到2014 年,隨著DeepWalk[2]算法的提出,真正引爆了人們對圖(節(jié)點)嵌入的研究熱潮.受啟發(fā)于自然語言處理中的word2vec[3]算法,DeepWalk 算法設(shè)計出了一種非常簡單且有效的面向節(jié)點的向量表達(dá)方式,即通過skip-gram[3]模型訓(xùn)練各個節(jié)點隨機游走出的序列(節(jié)點ID 序列),進(jìn)行計算節(jié)點間的相似性和節(jié)點向量.而后在基于DeepWalk 算法的基礎(chǔ)上,研究者們陸續(xù)提出了LINE[4],PTE[5],node2vec[6]以及stru2vec[7]等節(jié)點嵌入算法,但是這些算法都沒有脫離DeepWalk 算法的原有框架,本質(zhì)上說,相比較于DeepWalk 算法,這些算法只是在節(jié)點游走策略上更傾向于節(jié)點游走的有偏性,即在關(guān)注節(jié)點拓?fù)浣Y(jié)構(gòu)的情況下定義出節(jié)點的游走概率.在2018年,Dong 等人[8]給出了DeepWalk,LINE,PTE 和node2vec 這4 種算法的矩陣表達(dá)形式,更進(jìn)一步說明了這些算法在思想上的統(tǒng)一性.

雖然這種基于游走策略的圖表達(dá)學(xué)習(xí)在一定程度上可以保留節(jié)點拓?fù)浣Y(jié)構(gòu)這一屬性,特別是基于有偏游走策略的方法如node2vec 等,并且在實驗中取得了令人滿意的結(jié)果,但是基于游走策略的算法同樣也有一個非常明顯的缺點,即完全忽略了節(jié)點間的屬性值對實驗結(jié)果的作用,這就使得在某些屬性圖的數(shù)據(jù)集上無法達(dá)到令人滿意的效果.在2017 年,Hamilton 等人[9]設(shè)計了一種名為GraphSAGE 的新型采樣策略,首先,節(jié)點v對鄰居節(jié)點vi(節(jié)點v的所采樣的第i個鄰居)進(jìn)行采樣;而后對采樣后的節(jié)點vi再次向下一層節(jié)點vij(節(jié)點vi所采樣的的第j個鄰居)進(jìn)行采樣;然后由外向內(nèi)對所采樣的節(jié)點特性信息進(jìn)行聚合,從而得到節(jié)點v的一個新的聚合后的特征向量.GraphSAGE 算法雖然考慮了節(jié)點特征向量這一因素,但在一定程度上弱化了對節(jié)點拓?fù)浣Y(jié)構(gòu)屬性的保留.同年,Kipf[10]提出了一種半監(jiān)督分類的圖卷積網(wǎng)絡(luò)(graph convolutional networks,簡稱GCN).與GraphSAGE 的策略有所不同,文獻(xiàn)[10]中通過共享權(quán)值對單一節(jié)點所有鄰居節(jié)點特征進(jìn)行卷積操作,本質(zhì)可以看成加權(quán)求和,并且由公式可以看出:作者通過由單位矩陣IN和鄰接矩陣A相加得到的矩陣、節(jié)點特征向量H以及矩陣,在進(jìn)行拉普拉斯變換后,借助于可訓(xùn)練權(quán)重參數(shù)W來得出新的節(jié)點向量.并且可以看出,作者進(jìn)行了一個多層卷積的操作.同時,從文獻(xiàn)[10]中所提供的實驗結(jié)果可以看出:隨著層數(shù)的增加,會得出精度更高的實驗結(jié)果;但是一旦超過一定的層數(shù),實驗結(jié)果會急劇下降.這是因為一旦單一節(jié)點所聚合的信息過多,就不能很好地保持各個節(jié)點間向量的差異性,從而導(dǎo)致模型泛化.文獻(xiàn)[10]中對鄰居節(jié)點的卷積操作是在共享權(quán)值的前提下統(tǒng)一進(jìn)行的,但在現(xiàn)實情況中,節(jié)點的屬性受某些特定鄰居節(jié)點的影響會大于其余節(jié)點,所以這些鄰居節(jié)點理所應(yīng)該享有更高的權(quán)重.基于此,Velickovic 等人[11]在2018 年提出了圖注意力機制網(wǎng)絡(luò)(graph attention networks,簡稱GAT),即在共享權(quán)重參數(shù)W和節(jié)點特征向量的基礎(chǔ)上,通過LeakyReLU 和softmax 函數(shù)來計算兩節(jié)點vi和vj間的權(quán)重系數(shù):

由于各個鄰居節(jié)點特征向量的不同,所以權(quán)重系數(shù)也會不同,且共享權(quán)重參數(shù)W在學(xué)習(xí)的過程中不斷變化,那么節(jié)點間的權(quán)重系數(shù)也會隨著訓(xùn)練的過程而改變.

時序圖(temporal graph,亦被稱為temporal network[12,13],time-varying graph[14,15])是一種節(jié)點邊上帶有時間標(biāo)簽的基于時間的動態(tài)圖,對時序圖數(shù)據(jù)的分析工作在生物信息網(wǎng)絡(luò)、在線社交網(wǎng)絡(luò)和道路交通網(wǎng)絡(luò)等有著重要的應(yīng)用價值.在生物信息網(wǎng)絡(luò)中,生物功能的連接并不是一直活躍的[16],如在蛋白質(zhì)互作用網(wǎng)絡(luò)[17]和基因調(diào)控網(wǎng)絡(luò)中[18],其中的生物結(jié)構(gòu)體的聯(lián)系是存在一定的先后順序的,而通過分析這些結(jié)構(gòu)體在不同時間段相互關(guān)系,可以更容易確定出它們在網(wǎng)絡(luò)中的功能.在道路交通網(wǎng)絡(luò)[19?21]中,可以結(jié)合交通網(wǎng)絡(luò)中的歷史數(shù)據(jù),向用戶進(jìn)行某一時刻的路徑推薦或可達(dá)性查詢等相關(guān)工作;在社交網(wǎng)絡(luò)中[22?24],可以通過記錄用戶間的具體互動,更精準(zhǔn)地刻畫用戶間的關(guān)系.

現(xiàn)有的關(guān)于節(jié)點嵌入的研究工作更多的是在關(guān)注如何更好地在節(jié)點表達(dá)向量中保存節(jié)點的結(jié)構(gòu)屬性,但是在時序圖中,節(jié)點間的拓?fù)浣Y(jié)構(gòu)是隨時間動態(tài)變化的,因為節(jié)點之間的聯(lián)系是時序性的,表明了某種特定信息在節(jié)點間傳播的先后順序,而這種情況尚未被研究者們充分地考慮在圖嵌入策略中.

在網(wǎng)絡(luò)圖里,時序性不僅僅只限于兩相連節(jié)點間的時序性,如圖1(a)中的頂點1 和頂點2 的連接關(guān)系只在時刻t1和t2是存在的,且當(dāng)不考慮邊靜態(tài)(1,3)時,只是單純地從拓?fù)浣Y(jié)構(gòu)上看,在頂點1 和2 之間是存在可達(dá)路徑1→2→3 的;但是一旦考慮時間因素,如果在靜態(tài)邊(2,3)上的時間戳為t3且t3>t2>t1,則頂點1 和頂點2 之間便不再存在可達(dá)路徑.除了連接時序性和路徑時序性以外,節(jié)點的屬性有時也會是時序性的,以圖1(b)中的頂點1 為例,節(jié)點在不同的時刻可能會有不同的屬性.這一現(xiàn)象在電商網(wǎng)絡(luò)中是非常明顯的,在推薦系統(tǒng)領(lǐng)域中是一個非常棘手且待解決的挑戰(zhàn).

Fig.1 Instance of temporal graph圖1 時序圖示例

基于時序圖相比較于靜態(tài)圖所特有的時間屬性,面向時序圖的圖神經(jīng)網(wǎng)絡(luò)模型可總結(jié)有如下挑戰(zhàn).

(1)節(jié)點可達(dá)性:如果兩個頂點vi,vj僅僅在拓?fù)浣Y(jié)構(gòu)上存在一條可達(dá)路徑,但是在實際情況下并沒有任何想連接的可能,則節(jié)點vi在采樣時去整合頂點vj的信息是不合適的;

(2)多邊性:兩頂點在一個時間跨度之下不同的時刻會存在多條時間相關(guān)的邊,如圖1(c)中的頂點a和頂點b分別在時刻3 和時刻5 存在兩條邊,那么在節(jié)點做游走或信息整合時,需要考慮選擇哪條邊更為合適?

(3)路徑選擇:選擇不同基于時間的路徑則會直接影響起始點游走長度或聚合節(jié)點信息的多少.如圖1(c)中的頂點b和頂點d,如果在頂點b到頂點c時選擇時刻6 的路徑,則頂點b無法到達(dá)頂點d;而選擇時刻2 的路徑時則可達(dá).所以,準(zhǔn)確地選擇一條盡可能正確的路徑,才可以整合到盡可能準(zhǔn)確的信息;

(4)路徑時間跨度:當(dāng)一個頂點沿著一條路徑進(jìn)行游走或者進(jìn)行信息聚合時,如果這條路徑的時間跨度過大,那么在靠近路徑頂端的頂點和靠近路徑起始位置的頂點應(yīng)該是不能夠享有相同的權(quán)重系數(shù)的.如圖1(c)中由頂點a到頂點f的一條路徑(〈a,b,c,e,f〉),可以看出:當(dāng)在路徑的a和e之間,時間跨度只有7;但是當(dāng)?shù)竭_(dá)頂點f時,時間跨度陡增為50,此時可能頂點f對頂點a的影響已經(jīng)微乎其微了,但是如果把頂點f的信息整合都頂點a中去,則不僅使頂點a整合后的信息顯得冗余甚至是錯誤的.所以,隨著時間的增長,應(yīng)該弱化聯(lián)系時間更長的頂點對起始點的影響.

雖然現(xiàn)如今在圖嵌入領(lǐng)域已經(jīng)出現(xiàn)眾多研究成果,但是當(dāng)對這些研究工作的實驗結(jié)果進(jìn)行分析時,發(fā)現(xiàn)了一個非常明顯且普遍的問題,即,基于不同策略的圖表達(dá)學(xué)習(xí)在不同類型圖數(shù)據(jù)上的實驗結(jié)果是存在差異性的.這是因為有些圖數(shù)據(jù)對其本身的拓?fù)浣Y(jié)構(gòu)具有很強的敏感性,而對其自身的屬性等因素并不敏感.對于這種類型的圖數(shù)據(jù),使用游走策略的節(jié)點嵌入方法往往可以得到更好的實驗結(jié)果;而對其自身屬性等因素較為敏感的圖數(shù)據(jù),顯然更適用于卷積策略的圖表達(dá)策略.基于此發(fā)現(xiàn),可以認(rèn)識到:在現(xiàn)有的理論框架和技術(shù)水平之下,想要通過一種統(tǒng)一的圖學(xué)習(xí)模型來進(jìn)行對所有類型圖數(shù)據(jù)進(jìn)行圖表達(dá)的嘗試是幾乎不可行的.所以,為了應(yīng)對面向時序圖表達(dá)學(xué)中的挑戰(zhàn),本文旨在設(shè)計出一種對自身時序性敏感的圖數(shù)據(jù)嵌入學(xué)習(xí)方法,以得到一種更符合時序圖特性的圖表達(dá)學(xué)習(xí)方式.

本文創(chuàng)新點如下:

(1)整合現(xiàn)有的圖嵌入思想和時序圖相關(guān)特性,設(shè)計出一種新型的、可以滿足對時序圖數(shù)據(jù)進(jìn)行分析的時序圖嵌入策略;

(2)為解決不同類型時序圖節(jié)點間活躍性差異巨大的問題,設(shè)計出一種自適應(yīng)、滿足時序可達(dá)性的節(jié)點游走模型,盡可能地保留在不同的時間段節(jié)點和其周圍節(jié)點聯(lián)系的時間性質(zhì);

(3)為了盡可能快速地得到節(jié)點在不同時間段所游走出的節(jié)點序列,通過將在游走過程中的節(jié)點存在雙向、時序多叉樹中.如此,在游走結(jié)束后,可以簡單且快速地得到節(jié)點的游走序列;

(4)在嵌入方法特性和圖拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上,嘗試通過提出重要節(jié)點采樣的方式來縮減面向單節(jié)點的神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練時間;

(5)在不同類型的真實時序圖數(shù)據(jù)集上進(jìn)行了面向時序圖不同任務(wù)的實驗,以此驗證了本文中所設(shè)計方法的通用性、準(zhǔn)確性以及高效性.

本文第1 節(jié)對時序圖相關(guān)的基本定義和時序圖嵌入問題定義進(jìn)行說明.第2 節(jié)給出一種基本的、時序性的游走方法.第3 節(jié)提出一種更有效的面向時序圖的游走策略.在第4 節(jié)中進(jìn)行重要節(jié)點采樣的工作.第5 節(jié)中對在時序圖上的各項實驗分析進(jìn)行說明.第6 節(jié)中對相關(guān)工作進(jìn)行說明.

1 問題定義

本節(jié)將對一些基本的問題進(jìn)行梳理,對所面向的研究對象時序圖的類型進(jìn)行介紹,對基本的概念做出定義.并在表1 中對本文所常用到的一些符號的意義進(jìn)行簡要說明.

Table 1 Labels and meanings表1 常用符號表示

一般情況下,時序圖邊都是離散型表達(dá),如圖2(a),節(jié)點u在時刻t指向節(jié)點v的邊表示為(u,v,t,λ),其中,λ表示到達(dá)時間,即節(jié)點u在t時刻出發(fā)經(jīng)λ時間達(dá)到節(jié)點v.在本文中,由于并沒有涉及到節(jié)點間基于時間的路徑查詢等問題[25],更注重的是節(jié)點u到達(dá)節(jié)點v的時刻,從而無需刻意考慮λ,所以在實際操作中,可以將t=λ+t來看待.如此,在本文中的時序圖便可以簡化為(u,v,t)的形式,其中,t=λ+t.以圖2(a)中頂點a和頂點b為例,假如在0 時刻由a向b發(fā)出信息,經(jīng)歷λ=1 個時間單位到達(dá),則其邊上權(quán)重為1.而在社交網(wǎng)絡(luò)數(shù)據(jù)集中,由于消息的即時性往往將λ=0 做處理.而對于另外一種情況,如果λ表示聯(lián)系持續(xù)時間,即在t時刻兩節(jié)點建立聯(lián)系,持續(xù)λ個時間單位,基于最早到達(dá)的原則,將λ忽略處理,兩節(jié)點邊上的權(quán)重賦值為t.需要注意的是:在真實地數(shù)據(jù)集上,數(shù)據(jù)表示形式中的兩節(jié)點的聯(lián)系往往都是即時性的,所以在λ這個層面上無需做過多考慮.在此種類型的離散型時序圖便是本文所研究的對象.

除此之外,還有種特殊的時序圖亦稱時變圖(time-dependent graph)[26,27],其邊上的權(quán)重是由時間相關(guān)的函數(shù)f(t)所決定,非離散的,如圖2(b)所示.此種類型的時序圖由于應(yīng)用范圍實在有限,所以并不在本文研究范圍之內(nèi).

Fig.2 Instance of different types of temporal graph圖2 不同類型時序圖示例

定義1(時序圖).給定時序網(wǎng)絡(luò)GT(V,E,TE,X)表示為節(jié)點間帶有時序關(guān)系的有向時序圖.V表示節(jié)點的集合,V={v1,…,vn},E表示邊的集合,且|V|=n,|E|=m.TE表示圖中所有節(jié)點之間存在聯(lián)系時刻的集合,T(u,v)表示在節(jié)點u和v之間存在聯(lián)系的時刻的集合,如圖2(a),T(a,c)={2,6},且T(u,v)∈TE.X表示節(jié)點特征向量集合,X={x1,…,xn},其中,xi表示節(jié)點vi的特征向量.

定義2(到達(dá)時間).給定時序圖GT(V,E,TE,X),在時序圖GT中,則由節(jié)點u到達(dá)節(jié)點v的時間表示為Arr(u,v),且Arr(u,v)=T(u,v)+λ.

由于在本文中將λ=0 處理,所以以圖2(a)為例,Arr(a,b)=T(a,b)={1},Arr(a,c)=T(a,c)={2,6}.

定義3(時序可達(dá)路徑).給定時序圖GT(V,E,TE,X),在時序圖GT中,路徑〈v1,v2,…,vk〉滿足時序可達(dá)當(dāng)且僅當(dāng),則表示節(jié)點vi+1和vi+2之間的所有聯(lián)系時間都在節(jié)點vi和vi+1存在聯(lián)系之前,即:在節(jié)點vi到達(dá)節(jié)點vi+1之后,兩節(jié)點vi+1和vi+2之間便不再有關(guān)聯(lián).

以圖2(a)為例,頂點a到頂點f存在3 條時序可達(dá)路徑:〈a,b,c,f〉,〈a,c,f〉和〈a,d,f〉,以路徑〈a,d,f〉為例,若頂點a到頂點d的到達(dá)時間由4 變?yōu)?,則路徑〈a,d,f〉為非時序可達(dá)路徑,因為在時刻9 之后,頂點d和f之間的聯(lián)系便中斷了.

定義4(時序圖表達(dá)學(xué)習(xí)).給定時序圖GT(V,E,TE,X),時序圖節(jié)點的表達(dá)學(xué)習(xí)可以形式化地表示為:通過學(xué)習(xí)函數(shù)f,在采樣節(jié)點滿足時序可達(dá)的條件下,將節(jié)點vi映射到一個維度為d的向量,且d<<|V|,即:

其中,向量zi對應(yīng)節(jié)點vi最終的向量表達(dá)形式.

2 游走策略在時序圖中的限制和不足

基于以上對時序圖的定義、特征以及應(yīng)用場景的介紹,下面對由于受時序圖本身特性所限的節(jié)點表達(dá)問題所面臨的限制或挑戰(zhàn)進(jìn)行分析.盡可能地分析出問題的癥結(jié)所在,是解決問題的第1 步,然后才能針對癥結(jié)做出對應(yīng)的解決策略.

? 限制1:游走序列不能有效地保留時間因素

在基于游走策略的節(jié)點表達(dá)學(xué)習(xí)時,首先需要得到一個節(jié)點的游走序列,以圖3 中頂點a和o為例,當(dāng)不考慮頂點間的時序關(guān)系時,頂點a可以通過〈a,f,n,o〉和〈a,e,l,f,n,o〉兩個路徑到達(dá)頂點o,并以此得到‘a(chǎn),f,n,o’和‘a(chǎn),e,l,f,n,o’兩個游走序列.頂點a和o的遠(yuǎn)近只能說明兩者在拓?fù)渚嚯x上是接近的.當(dāng)考慮時序關(guān)系時,由于路徑〈a,e,l,f,n,o〉不滿足時序可達(dá)性,所以頂點a只能通過路徑〈a,f,n,o〉達(dá)到頂點o.

這樣,便可在犧牲些許“拓?fù)洹睂傩缘那疤嵯?更好地保留節(jié)點間的時序?qū)傩?這在對節(jié)點間對時間敏感的實驗結(jié)果中無疑是更友好的.并且僅僅在拓?fù)浣Y(jié)構(gòu)上相近的點并不見得就是真的“親近”,當(dāng)他們不滿足時序可達(dá)時,可能表明在實際情況中兩頂點并沒有過多的聯(lián)系,僅僅受制于拓?fù)潢P(guān)系,而使得他們看起來很“親近”而已.

Fig.3 Random walk paths selection in temporal graph圖3 時序圖節(jié)點游走路徑選擇

? 限制2:局部拓?fù)浣Y(jié)構(gòu)的動蕩變化

有時在很小的時間跨度內(nèi),在一個圖的局部范圍內(nèi),節(jié)點間關(guān)系的動態(tài)變化有限,對單一節(jié)點vi在不同的時刻游走會得到很多的重復(fù)路徑.以圖3 中的頂點a和d為例,在2 和4 時刻,頂點a在路徑4 上走出的滿足時序可達(dá)路徑是相同的;而當(dāng)時間的跨度相對較大,到達(dá)8 時刻時,就可以得到一個不同的時序可達(dá)路徑.當(dāng)節(jié)點間的聯(lián)系時刻突然發(fā)生了較大的變化時,有可能在和其相關(guān)的局部拓?fù)浣Y(jié)構(gòu)會發(fā)生了一些“動蕩”,這個時候可以在動蕩之后的時刻進(jìn)行重新游走,以得出一個新的路徑,而在動蕩之前,可以盡可能少地采樣.

這種現(xiàn)象在實際的網(wǎng)絡(luò)圖中也是普遍存在的,以最典型的交通網(wǎng)絡(luò)圖為例,在不同的時刻(早高峰、晚高峰和平時),每個路段的通行時間是不同的,如此便導(dǎo)致了局部連通性的變化,等由始發(fā)地A行駛到目的地B時,在不同的時刻可能就需要選取不同的路徑.

? 限制3:不同類型的時序網(wǎng)絡(luò)中動態(tài)變化率差異極大

在不同類型的時序網(wǎng)絡(luò)中,各個節(jié)點間聯(lián)系頻率的差異是非常明顯的.有的可能是以毫秒級來計算的(通信服務(wù)網(wǎng)絡(luò)等),而有的可能是以分鐘、小時,甚至以天來計算(郵件網(wǎng)絡(luò)等).針對這種情況,對于如何設(shè)計一種自適應(yīng)的節(jié)點采樣策略,如此可以在不同類型的時序網(wǎng)絡(luò)數(shù)據(jù)中解決限制二所面臨的問題,便成了一個很大的挑戰(zhàn).

? 限制4:采樣路徑的時間跨度問題

考慮到時間的變化對時序圖中的拓?fù)浣Y(jié)構(gòu)和節(jié)點間的關(guān)系屬性影響很大,所以一個節(jié)點受其相近鄰居的影響也應(yīng)該是局限在一定的時間范圍之內(nèi)的.正如在真實的一個網(wǎng)絡(luò)中(腦網(wǎng)絡(luò)、交通網(wǎng)絡(luò)抑或郵件網(wǎng)絡(luò)),腦網(wǎng)絡(luò)中的一個神經(jīng)元a1在時刻t1發(fā)送到另一個神經(jīng)元的信息并不會永無休止地在這個網(wǎng)絡(luò)中一直傳遞下去,經(jīng)過若干個神經(jīng)元后,在時刻ti傳遞到神經(jīng)元ai,而在經(jīng)過若干個時刻后,有一個信息從神經(jīng)元中ai發(fā)出,而這個信息可能只是單純的由神經(jīng)元ai發(fā)出,已經(jīng)和初始神經(jīng)元a1無半點關(guān)系,所以在此時刻以后的時序路徑應(yīng)該歸屬于神經(jīng)元ai而不是a1.這種現(xiàn)象在時序網(wǎng)絡(luò)中應(yīng)該是一種很常見的現(xiàn)象,特別是在社交網(wǎng)絡(luò)中,信息往往都是即時性的,這種現(xiàn)象應(yīng)該更為常見.

所以當(dāng)對初始節(jié)點vi進(jìn)行滿足時序可達(dá)性的路徑上進(jìn)行采樣時,隨著采樣路徑中節(jié)點的增加,路徑的時間跨度也就越大,這個時候應(yīng)該檢測路徑尾部的節(jié)點和初始節(jié)點vi雖然滿足時序可達(dá)性,但是兩者相互間的關(guān)聯(lián)性是否是間接地借助中間節(jié)點完成的,且傳遞的性質(zhì)是否已經(jīng)發(fā)生了變化.

3 基本的時序節(jié)點嵌入策略

結(jié)合現(xiàn)有游走策略的嵌入方法和節(jié)點間的時序性,一種最簡單的時序圖嵌入策略就是在節(jié)點游走的過程中記錄游走序列中最新節(jié)點的到達(dá)時刻,進(jìn)而對下一個可以游走的節(jié)點的進(jìn)行選擇.

首先,需要將時序圖GT轉(zhuǎn)化為一種更方便操作的靜態(tài)圖,如圖4 所示.圖4(a)是原始的時序圖GT,圖4(b)是轉(zhuǎn)化后所對應(yīng)的靜態(tài)圖.在圖4(b)中,具有相同顏色的節(jié)點表示在不同時刻的同一個節(jié)點.以頂點a為例,在圖4(a)中,頂點a分別和頂點b～d在1,2,4 和6 這4 個時刻存在聯(lián)系,則在圖4(b)中,有4 個與之對應(yīng)顏色相同的頂點a1,a2,a4,a6,同時按時間順序由較早時刻的頂點依次指向較晚時刻的頂點,如圖4(b)中顏色和頂點相同的邊所示.圖4(b)中頂點的下標(biāo)表示頂點u到達(dá)鄰居頂點v的時刻,或從鄰居頂點v到達(dá)自身u的時刻,即頂點在不同時刻的出邊和入邊,如其中帶箭頭黑色邊所示.

Fig.4 Instance of temporal graph圖4 時序圖示例

在僅考慮節(jié)點間的時序可達(dá)的條件下,首先將時序圖轉(zhuǎn)化為靜態(tài)圖,圖4 所示;然后結(jié)合現(xiàn)有的節(jié)點隨機游走策略,借助于自然語言處理中的skip-gram模型,設(shè)計出一種最基本的基于時序圖的節(jié)點嵌入算法.

算法的基本思想:首先,在時序圖中,受時間因素所限,節(jié)點會喪失游走的“自由”度,當(dāng)初始節(jié)點v游走到節(jié)點u后,需要選擇所要游走u的鄰居節(jié)點{u1,u2,…,un}時,需要首先判斷節(jié)點u的訪問時刻Arr(v,u)是否小于等于和其鄰居節(jié)點ui的最大聯(lián)系時刻,只有滿足的條件的節(jié)點ui才可以被游走.而后可以從滿足條件節(jié)點中的一個或若干個進(jìn)行游走采樣,當(dāng)所有頂點都采樣完畢得到游走序列時,便可以通過skip-gram模型得出節(jié)點帶有時序關(guān)系的向量表達(dá).

算法1.Basic 時序嵌入.

輸入:時序圖GT(V,E,TE),Skip-Gram模型,游走步長L;

輸出:時序圖節(jié)點表達(dá)向量Z.

在第3 行,首先將節(jié)點u本身作為有序列的起始點;第5 行表示從現(xiàn)有的游走序列中的尾部取出節(jié)點作為下一次游走的起始點;第7 行～第11 行表示當(dāng)游走序列停留在節(jié)點u上時,從其鄰居節(jié)點集合Nu中隨機選擇一個滿足時序可達(dá)的節(jié)點v到u的游走序列ul中去,如果沒有滿足時序可達(dá)的鄰居節(jié)點,則游走停止;第14 行～第16 行表示首先記錄所有節(jié)點的游走序列(第14 行),然后通過skip-gram模型得到各個節(jié)點的向量表達(dá).

但是需要注意的是:這種基本的時序圖嵌入策略無法很好地解決在第2 節(jié)中所提到的各個限制,特別是無法自動識別出不同類型時序圖的動態(tài)變化率和采樣路徑的時間跨度問題.基于此,進(jìn)一步對基本算法進(jìn)行改進(jìn),以更好地應(yīng)對以上限制.

4 對基本時序節(jié)點嵌入策略的改進(jìn)

由于不同類型時序圖的動態(tài)變化率有很大的差異,相對的也就決定了在不同類型的時序圖中采樣路徑的時間跨度也會有很大的不同.由于前一節(jié)所提出的Basic 算法無法有效地解決這兩種問題,所以在Basic 算法的基礎(chǔ)上,本節(jié)提出了一種自適應(yīng)時序圖動態(tài)變化的新型嵌入策略.

4.1 自適應(yīng)時序節(jié)點嵌入

基于上一節(jié)中提出的基本嵌入策略所面臨問題的基礎(chǔ)上,本小節(jié)提出一種改進(jìn)的自適應(yīng)時序圖節(jié)點采樣策略ATGEB.策略思想:網(wǎng)絡(luò)的動態(tài)變化是因為信息在其中的流通,信息通過用戶間建立聯(lián)系進(jìn)行傳播.而信息同樣也在隨著時間的改變而發(fā)生變化,即信息在時序網(wǎng)絡(luò)中是有“傳播壽命”的.不同的信息Infi和Infj在網(wǎng)絡(luò)中傳播的時間跨度可能有完全重合、部分重合以及完全分離這3 種情況.在全局的角度下,很難通過時間來區(qū)分這些不同的信息;但是一旦具體到各個單一節(jié)點u中去分析信息的傳播時,便可能通過節(jié)點間的聯(lián)系間接地保存這些信息特征.假設(shè)信息Infi和Infj的傳播時間跨度都是[t1,t2],當(dāng)信息分別傳播到節(jié)點ui,uj時,便可以通過觀察在[t1,t2]間與兩節(jié)點抱有聯(lián)系的節(jié)點來間接地區(qū)分兩種信息,因為不同的信息所作用的節(jié)點也可能是不同的.

通過這種思想,可以對節(jié)點ui在不同的信息Infi下進(jìn)行游走,這樣盡可能保留節(jié)點ui在不同類型信息傳播下和其相鄰節(jié)點的時序關(guān)系.但是需要注意的是:正常情況下,出于對用戶隱私保護(hù)的需求,研究者是無法得到這些具體信息的傳播途徑的.結(jié)合信息自身傳播的特性,可以從節(jié)點活躍時刻集合入手來進(jìn)行問題的研究.

節(jié)點u與其鄰居節(jié)點Nu的聯(lián)系時刻,Tu同樣包含了節(jié)點u的活躍時間跨度(time span):TSu=max(Tu)?min(Tu)和活躍次數(shù)|Tu|及其活躍頻率(activity frequency):AFu=|Tu|/TSu.在[min(Tu),max(Tu)]時間段中,由于傳播信息的不同,集合Tu中的時刻分布是不均勻的,所以可以通過DBSCAN 這種無監(jiān)督方式對時刻ti進(jìn)行聚類這種間接的方式來區(qū)分節(jié)點u所傳遞的不同信息.將節(jié)點的平均活躍時間間隔設(shè)置為對象半徑E=TSu/(|Tu|?1).求解過程如下.

首先對Tu中的各個時刻進(jìn)行排序,得,則總的時間的間隔為,間隔個數(shù)為|Tu|?1.所以,E=TSu/(|Tu|)?1).

通過DBSCAN 將Tu聚類后會得到若干各集合類,其中,即間接地看為若干個信息的活動范圍,如Ci集合中的時間跨度為.然后,在每個已完成的聚類的時間段內(nèi)對節(jié)點u進(jìn)行游走,得出其各個時間段的游走序列,以此來保存在不同“信息”下的和其相鄰節(jié)點的時序關(guān)系.具體的操作步驟在算法2 和算法3 中做出詳細(xì)說明.

這種無監(jiān)督的聚類方式可以很好地解決不同類型時序圖中節(jié)點活動頻率有差異的問題,因為將對象半徑E設(shè)置好之后,便可以對各個時刻進(jìn)行自動聚類.如果某一節(jié)點u非常規(guī)律地向其鄰居節(jié)點發(fā)送信息,即AFu保持不變,如此便間接說明了所傳遞“信息”的相似性甚至大概率表明一直都是在傳遞同一種信息,而通過這種自適應(yīng)的聚類方式,便可以將Tu中的元素聚類到同一種類型中去,如此便可以在一定程度上減少了在不同時間段重復(fù)采樣的可能,避免造成采集數(shù)據(jù)過分冗余.

算法2.ATGEB.

輸入:時序圖GT(V,E,TE),Skip-Gram模型;

輸出:時序圖節(jié)點表達(dá)向量Z.

針對在不同時間段Ci中節(jié)點u如何向其相鄰節(jié)點進(jìn)行游走的問題(第9 行),在算法3 中做出詳細(xì)說明.其主要思路是:在節(jié)點u在其鄰居節(jié)點Nu選取一個節(jié)點v,節(jié)點v在時間段Ci內(nèi)和u存在聯(lián)系,且存在聯(lián)系時刻T∈Tu接近或等于時間段的起始值min(Ci).然后由選取的節(jié)點v向外發(fā)散游走,“追蹤”信息的傳播路徑.

算法3.PathTree.

輸入:時序圖GT(V,E,TE),節(jié)點u,時間段Ci;

輸出:節(jié)點u在時間段Ci內(nèi)的游走序列ul.

結(jié)合示例圖5 對算法3 進(jìn)行詳細(xì)說明.首先需要說明:圖5 中的樹是一個多叉時序可達(dá)樹,即有根節(jié)點到葉子結(jié)點是滿足時序可達(dá)的.在第1 行中,對根節(jié)點的名字、后續(xù)節(jié)點集合和前序節(jié)點做初始化.需要注意的是:由于是多叉樹,所以樹的非葉子節(jié)點保留其各個后續(xù)節(jié)點的地址集合,而前序節(jié)點保存一個單一的地址.第5 行～第8 行:表示節(jié)點的鄰居為空,則將此節(jié)點記錄為葉子結(jié)點,將其地址記錄到葉子結(jié)點集合TL中.第9 行～第13行:如果有滿足需求的鄰居節(jié)點v,即在時間段內(nèi)Ci滿足可達(dá)關(guān)系,則更新節(jié)點v的到達(dá)時間、前后序節(jié)點地址,記錄節(jié)點名字,并將其放入樹中.第14 行、第15 行表示節(jié)點u無滿足可達(dá)性的鄰居節(jié)點存在,則將u作為樹的葉子節(jié)點,并將其地址記錄到TL中去.

而后,第18 行～第24 行表示通過在TL所記錄的葉子結(jié)點地址進(jìn)行游走序列提取.如圖5(b)所示:首先,通過f以此向上直到root 頂點a,得到一個節(jié)點序列ul1=‘f,c,b,a’.需要注意的是:這個序列是和真實序列相反的,所以在算法實現(xiàn)時,需要將每次提出的節(jié)點名字放在序列最前面,這樣便可以得到真實的序列ul1=‘a(chǎn),b,c,f’.第24 行中的ul表示節(jié)點的在這個時間段內(nèi)的序列集合,以圖5(b)為例,即ul=[[a,b,c,f],[a,c,e],[a,c,f],[a,d,f]].這樣便可得到了一個節(jié)點u在時間段Ci內(nèi)和信息Infi相關(guān)的游走序列集合.

Fig.5 Random walk paths selection in temporal graph圖5 時序圖節(jié)點游走路徑選擇

4.2 嵌入準(zhǔn)確性的簡要分析

首先簡要介紹skip-gram模型在節(jié)點嵌入中的運行原理,從節(jié)點的表達(dá)向量是如何得出的角度進(jìn)行分析.如圖6 所示,節(jié)點的one-hot向量由隱藏層加權(quán)后到輸出層分類,通過計算在移動窗口w內(nèi)節(jié)點和其余各個節(jié)點的概率值和softmax層的輸出值的差異作為損失量,進(jìn)行向后傳遞更新各層的權(quán)重值,然后通過移動窗口進(jìn)行持續(xù)更新.最后,通過隱藏層H的權(quán)重值得到相應(yīng)節(jié)點的向量表達(dá)Z.

Fig.6 Instance for nodes embedding圖6 節(jié)點向量嵌入示意圖

假設(shè)時序網(wǎng)絡(luò)中存在用戶傳遞的信息I個:Inf1,Inf2,…,InfI,同時存在的節(jié)點標(biāo)簽(類)L個:Lab1,Lab2,…,LabL.而不同標(biāo)簽的用戶對不同信息的敏感度是不一樣的,這也就說明標(biāo)簽決定了用戶對不同信息的接收和傳播的概率是不同的,即通過不同的信息用戶“接觸”到不同的用戶.反之可以推斷,若干種信息Infi,Infj,…,Infk可以間接決定用戶的標(biāo)簽,f(Infi,Infj,…,Infk)=Labi,所以通過用戶所接收或傳播的信息類別,可以更準(zhǔn)確地判斷出其所屬的標(biāo)簽.

在節(jié)點分類的神經(jīng)網(wǎng)絡(luò)中,兩個節(jié)點的向量相似度越高,也就意味著同屬于一種類的可能性越高,即:

將在圖6 中的用戶列表示為U,softmax層表示為輸出層O,隱藏層表示為H,對于一個已經(jīng)訓(xùn)練好的skipgram模型,對于屬于同Lab的用戶節(jié)點u和v,假設(shè)其經(jīng)softmax層輸出后的前w個類對應(yīng)用戶分別為而兩者的嵌入向量zu,zv,且已知隱藏層神經(jīng)元的值H=WH×[0,0,0,…,1,0]T直接決定了節(jié)點的向量和節(jié)點的經(jīng)輸出層后的分類U,即Hu→zu,Hv→zv,已知兩節(jié)點u,v同Label,則說明兩者的嵌入向量相似:zu≈zv,由此可知Hu≈Hv,而隱藏層同樣決定了輸出層,所以

上述主要描述了在進(jìn)行節(jié)點嵌入網(wǎng)絡(luò)中的向前傳播機制,基于此,進(jìn)一步說明隱藏層的更新方式.假設(shè)節(jié)點u在一個游走序列ul中,以u為中心所構(gòu)成的一個大小為w的窗口Winu={u1,…,u,…,uw},則在此窗口內(nèi)的網(wǎng)絡(luò)訓(xùn)練誤差,其中,y′=Onehotu×WH×WO.由于Winu的規(guī)模有限,不可能將所有節(jié)點放入進(jìn)去,所以對除u以外的節(jié)點,其在窗口Winu的可能性越小,則P(u,v)的值也就越小,則隨著訓(xùn)練的增加,由輸出層softmax的特性可知,對u的One-hot向量Onehotu在skip-gram網(wǎng)絡(luò)中的分類,也就越傾向于在Winu出現(xiàn)頻率高的節(jié)點.由此可知,節(jié)點u的窗口Winu中的節(jié)點出現(xiàn)頻率也就影響了其在skip-gram中的分類,進(jìn)而由上段中的分析可知,也就影響了其隱藏層中神經(jīng)元的值Hu來影響zu.

所以,通過以上的分析可知:對于屬于同Label的節(jié)點u和v,要使得兩者的嵌入向量zu,zv相似,則需要使得在所有游走序列ul中的分別以u和v為中心的移動窗口Winu,Winv中出現(xiàn)的高頻率節(jié)點集合盡可能高地重合,且同屬相同的Label的節(jié)點應(yīng)該有著相似的重合度.因為如果不同的Label的節(jié)點有了相似的重合度,便也意味著可以得到相似的表達(dá)向量z,而這顯然與兩者的Label不同這一前提是矛盾的.

對于同Label兩節(jié)點u和v,設(shè)其可能的游走節(jié)點的集合分別為,在算法2 中可能的游走集合分別為,且易知,則對于游走窗口Winu={u1,…,u,…,uw}和Winv={v1,…,v,…,vw},若兩節(jié)點的Label與Infi,Infj相關(guān),設(shè)受兩信息影響而活躍的節(jié)點集合為,而SInf中的節(jié)點也就間接地表明他們是在Infi,Infj的影響下活動的.所以相較于隨機游走的策略,在本文的游走策略下,在含有兩節(jié)點u和v的游走路徑ul中,在節(jié)點u(v)之前和之后的1/2(w?1)個節(jié)點(即窗口Winu或Winv內(nèi)的節(jié)點)也都更傾向于都包含在SInf中,即窗口內(nèi)的節(jié)點和u(v)同Label的概率更大,所以表明以兩節(jié)點為中心的窗口內(nèi)出現(xiàn)共同節(jié)點的可能性也就越大(相較于隨機游走的方法).如前分析,共同高頻率節(jié)點越多,也就越可以得到更為相似的節(jié)點向量.

5 圖的重要節(jié)點采樣

在圖數(shù)據(jù)結(jié)構(gòu)中,由于其復(fù)雜的拓?fù)浣Y(jié)構(gòu),通常都會有大量的節(jié)點在很短的距離內(nèi)聚集在一個社區(qū)中.而通過節(jié)點嵌入算法的思想可以看出:在一個密集的社區(qū)內(nèi),其中大量的節(jié)點會游走出很相似的序列,進(jìn)而也會產(chǎn)生相似的向量表達(dá).而這些非常相似向量并屬于同一種類Ci的話,那么在進(jìn)行節(jié)點分類的任務(wù)工作中,如果應(yīng)用要在盡可能短的時間內(nèi),且可以承受模型有一定誤差的這種需求的話,是否可以通過采樣同一類型中具有相似向量節(jié)點中的若干個節(jié)點向量進(jìn)行神經(jīng)網(wǎng)絡(luò)中參數(shù)的訓(xùn)練呢?這樣便可以在盡可能短的時間內(nèi)訓(xùn)練出神經(jīng)網(wǎng)絡(luò)中的參數(shù)權(quán)重.

對于節(jié)點ui,uj和uk,其所對應(yīng)的游走序列分別為uil,ujl和ukl,如果ui和uj的距離說明節(jié)點ui相較于節(jié)點uk更接近于uj.則在一般情況下,兩節(jié)點的共同鄰居同樣也滿足如此,對于節(jié)點v,在經(jīng)過w(假設(shè)其大小和skip-gram模型窗口一致)長度游走的范圍內(nèi),當(dāng)其游走序列vl在經(jīng)過節(jié)點uj后,經(jīng)過節(jié)點ui的概率同樣大于經(jīng)過uk的概率,即P(vl→uj|vl→ui)>P(vl→uj|vl→uk);反之,序列由節(jié)點ui到節(jié)點uj的概率同樣也大于uk.由此可得:對于任意節(jié)點的游走序列wl∈WL,在一個窗口大小為w的范圍內(nèi),其同時包含ui,uj的概率大于同時包含的uj,uk概率,即P(uj,ui∈wl)>P(uj,uk∈wl),在全局的角度來看,所以ui,uj共同在窗口w范圍內(nèi)出現(xiàn)在WL中的次數(shù)要大于uj,uk.而在skip-gram模型中,節(jié)點u向量是通過在序列wl中和u共同在窗口w中的其余節(jié)點進(jìn)行更新的.由此可知,對于三節(jié)點所對應(yīng)的向量,則前兩者應(yīng)該具有更大的相似性,即

根據(jù)以上分析可知:可以選取圖中的若干個稠密子圖g1,g2,…,gm作為密集社區(qū)來選取重要節(jié)點,稠密子圖gi需要滿足對于任意兩節(jié)點vi,vj∈gi,兩節(jié)點的距離應(yīng)該盡可能地小.首先最容易想到的是通過k-core來進(jìn)行稠密社區(qū)的挖掘,雖然k-core可以通過提高k值的方式得到稠密的子圖gi,但是這種方式得到的子圖并不滿足使得盡可能地小.以圖7 為例,去掉節(jié)點e,f,g,剩余的節(jié)點便可以得到一個完整的2-core子圖,但是通過節(jié)點c和d可以發(fā)現(xiàn),d(c,d)=6,而通過小世界原理可知,這在圖數(shù)據(jù)網(wǎng)絡(luò)中已經(jīng)可以看成一個很長的距離.所以對社區(qū)的挖掘,僅僅通過稠密性是難以達(dá)到目標(biāo)需求的,還需要限制社區(qū)中節(jié)點的相互距離,而在文獻(xiàn)[28]中所提出的kr-Clique算法思想可以滿足這種需求,其中:k指的是節(jié)點度數(shù);r指的是節(jié)點跳數(shù),即在社區(qū)內(nèi)任意兩節(jié)點可以在r跳內(nèi)可達(dá).

Fig.7 k-core communities in graph圖7 圖的k-core 劃分

文獻(xiàn)[28]中的kr-Clique 算法旨在找出所有滿足需求的社區(qū),但是在本文中這是沒有必要的,重要節(jié)點的采樣旨在選取相對于節(jié)點類Ci更具有代表性的節(jié)點向量作為訓(xùn)練樣本集進(jìn)行訓(xùn)練,而無需選取所有的節(jié)點.在這種思想的指導(dǎo)下,可以在圖中選取若干個度數(shù)較大的節(jié)點作為中心節(jié)點,然后以這些中心節(jié)點選取其鄰居的度數(shù)大于k的節(jié)點,然后通過節(jié)點u向外進(jìn)行發(fā)散,選取節(jié)點u滿足條件的鄰居節(jié)點,循環(huán)r次,即可以得到一個關(guān)于中心節(jié)點2cv的粗略的kr-Clique,這已經(jīng)可以滿足需求.當(dāng)一個中心節(jié)點1cv的kr-Clique社區(qū)選取完畢后,對其中的節(jié)點按類進(jìn)行聚類,得到節(jié)點集合,然后可以按照一個很小的比例(如10%)從各個聚類中隨機選取節(jié)點向量作為訓(xùn)練集,而非直接將圖中的60%節(jié)點作為訓(xùn)練集,因為這60%中的節(jié)點很多都是屬于相同的類別,且向量具有較高的相似性.然后可以進(jìn)行關(guān)于下一個中心節(jié)點的重要節(jié)點選取.

對于中心節(jié)點和重要節(jié)點的選取工作,本小節(jié)通過一種類似于影響力最大問題中基于節(jié)點度的啟發(fā)式算法[29]進(jìn)行選取,詳見算法4 所示.

算法4.INS(important nodes sampling)算法.

輸入:時序圖GT(V,E,TE),節(jié)點類,C1,C2,…,Cc,中心節(jié)點個數(shù)N;

輸出:重要節(jié)點的向量集合ZIN.

第1 行的krC表示已經(jīng)選取的社區(qū)節(jié)點集合,i控制社區(qū)中心節(jié)點選取的數(shù)量.第3 行、第4 行表示在選取新的中心節(jié)點ui時,使得ui不在已經(jīng)選取的社區(qū)中,即與現(xiàn)存的所有的中心節(jié)點的距離都要至少大于等于2,且ui的度數(shù)在剩余節(jié)點中保持最大,這樣可以在圖中盡可能廣的范圍內(nèi)選取中心節(jié)點,而不是集中在圖的某一個局部地區(qū).以圖7 為例,首先選取a為中心節(jié)點選取一個(3,3)-Clique,然后在剩余節(jié)點中,將b作為中心節(jié)點.第5行～第12 行表示以節(jié)點ui為中心的社區(qū)的形成,首先通過BN1尋找滿足條件的鄰居節(jié)點,將社區(qū)進(jìn)行向外擴散,并將邊界點記錄到BN2中,第1 輪完畢后,將BN2中的邊界點賦值到BN1進(jìn)行新一輪的擴散.第14 行為重要節(jié)點選取,具體細(xì)節(jié)已在上段中說明.

而以上的重要節(jié)點的選取都是在稠密社區(qū)的基礎(chǔ)上完成的,但是在實際的圖數(shù)據(jù)中,有很多的節(jié)點或者新的連通結(jié)構(gòu)體都是游離在這些社區(qū)之外.為了使得選取的節(jié)點不僅僅具有代表性,還應(yīng)更具有統(tǒng)一性,所以最后還需要在這些“游離”的節(jié)點中按照同樣的比例隨機選取節(jié)點添加到訓(xùn)練樣本集合ZIN中去.

6 實驗和評估

在算法實驗的設(shè)計和驗證上,為了充分驗證算法在不同類型數(shù)據(jù)上的表現(xiàn),本文選取了4 種在節(jié)點(邊)規(guī)模上、時序邊分布、稠密度等圖結(jié)構(gòu)方向都有明顯不同的真實數(shù)據(jù)集作為輸入數(shù)據(jù),并在節(jié)點聚類、鏈接預(yù)測、節(jié)點分類和節(jié)點時序可達(dá)檢測這4 個方向?qū)λ惴ㄟM(jìn)行驗證.

6.1 實驗數(shù)據(jù)和參數(shù)設(shè)置

(1)實驗數(shù)據(jù)

數(shù)據(jù)集D0[30]和D1[31]分別取自兩個名為Bitcoin OTC 和Bitcoin Alpha 的比特幣交易平臺,主要注意的是:這兩個數(shù)據(jù)集為用戶的金融交易數(shù)據(jù),非普通的社交網(wǎng)絡(luò),用戶與其鄰居只存在一次聯(lián)系,從數(shù)據(jù)中的時序邊等于靜態(tài)邊可以看出.數(shù)據(jù)集D2[32]和D3[32]分別取自名為Math Overflow 和Super User 的堆交換網(wǎng)站中的時序網(wǎng)絡(luò)數(shù)據(jù).各個數(shù)據(jù)集節(jié)點規(guī)模、靜態(tài)邊、時序邊以及節(jié)點的活躍頻率的分布情況詳見表2.并且從表2 的數(shù)據(jù)可以看出:各個數(shù)據(jù)集在不同的指標(biāo)上有很大的差異,滿足了實驗需求.

Table 2 Info of data sets表2 實驗數(shù)據(jù)集信息

(2)對比算法

本文除了在數(shù)據(jù)集上完成了本文所提出的算法,同樣對以下3 種算法在數(shù)據(jù)集上進(jìn)行了復(fù)現(xiàn)作為對比.由于其中某些算法不支持時序性可達(dá)的游走策略,在數(shù)據(jù)集上進(jìn)行復(fù)現(xiàn)選擇將數(shù)據(jù)作為靜態(tài)圖看待,即忽略邊上的時間戳:

? DeepWalk.首先,將時序圖GT中的時間戳刪除,將其轉(zhuǎn)化為靜態(tài)有向圖;然后,在靜態(tài)圖的基礎(chǔ)上通過DeepWalk 算法對節(jié)點進(jìn)行向量化表達(dá);

? Node2vec.和DeepWalk 算法相比,node2vec 算法的不同之處在于:當(dāng)游走經(jīng)過節(jié)點t到達(dá)u后,向鄰居節(jié)點v進(jìn)行游走時,首先需要計算u的每個鄰居節(jié)點的游走概率αpq(t,v),然后借助于Alias 采樣方法選擇下一步游走的節(jié)點v.游走的概率計算公式見公式(1):

其中,dtv表示兩節(jié)點路徑長度.在本次實驗中,p設(shè)置為0.25,q的值設(shè)置為4,然后通過Alias 算法進(jìn)行游走采樣;

? CTDNE[33].這種算法的思想與本文的Basic 和DeepWalk 算法一致,只是節(jié)點在游走的過程中,作者設(shè)置一個節(jié)點對時間相關(guān)的概率,即有偏采樣,以此來左右節(jié)點對鄰居節(jié)點的選擇.

(3)實驗環(huán)境

64 位操作系統(tǒng):Windows10,CPU:i5-8400@2.80Hz,內(nèi)存為24G,硬盤500GB,編程環(huán)境為Python 3.7.

(4)參數(shù)設(shè)置:

在通過skip-gram生成節(jié)點向量時,窗口大小設(shè)置為5;節(jié)點的游走步長L分別設(shè)置為10,20,30,40 和50;節(jié)點u生成的向量zu的維度大小d=100;學(xué)習(xí)率r=0.01,在分類任務(wù)中的損失函數(shù)為交叉熵?fù)p失函數(shù).

6.2 節(jié)點聚類

在節(jié)點聚類的實驗中,通過兩種方式來對各個算法的聚類效果進(jìn)行評測:跨類的靜態(tài)邊EC(edges crossing clusters)和時序邊TC(temporal edges crossing clusters)的數(shù)量.假設(shè)通過節(jié)點的表達(dá)向量將節(jié)點聚類為N類:C1,C2,…,CN,用Cv表示節(jié)點v所屬的類.則即:當(dāng)節(jié)點v的鄰居u和v屬于不同的類時,邊(v,u)便可以看為跨越不同的聚類.,e表示在EC中的邊,Te表示邊e上的時刻集合.

為了盡可能公允地分析實驗的結(jié)果,在實際的實驗中,分別將節(jié)點聚類成4 類和5 類,然后在計算出各種算法在不同聚類的情況下的表現(xiàn).詳情如圖8 和圖9 所示,其中,TC(i)和EC(i)中的i表示的是節(jié)點的游走長度:由10～50.

Fig.8 Node clustering in temporal graph圖8 時序圖節(jié)點聚類

Fig.9 Analysis for important nodes sampling圖9 重要節(jié)點采樣分析

圖8 中的各個子圖的縱坐標(biāo)表示數(shù)量,橫坐標(biāo)表示在TC和EC下的節(jié)點游走的長度L:10～50.由圖8(a)和圖8(b)中的數(shù)據(jù)可以看出:本文的方法在起始階段會更快地收斂,但是隨著游走長度的增加逐漸趨于平穩(wěn).這是因為受采樣策略所限,因為一旦采樣策略受時間所限,則其游走長度到達(dá)一定的長度后便會自動終止.可以看出,本文的方法基本上會在30 步以后趨于平穩(wěn).由此可知,游走的序列長度大部分應(yīng)該在30 步以內(nèi).在圖8(a)和圖8(b)中可以看出:ATGEB 在前期有一定的優(yōu)勢,但是隨著游走長度的增加,便和DeepWalk 和node2vec 保持基本一致.但是在圖8(c)和圖8(d)中可以看出,后兩種方法在在數(shù)據(jù)集D2 和D3 中更有優(yōu)勢.通過此實驗,旨在表明對于傳統(tǒng)的節(jié)點聚類問題上,基于時序節(jié)點嵌入的策略對數(shù)據(jù)集的屬性較為敏感,即對某些特定類型的數(shù)據(jù)集有一定的優(yōu)勢,但不如傳統(tǒng)的DeepWalk 和node2vec 這類算法可以較好地應(yīng)用在各類型數(shù)據(jù)中.

6.3 連接預(yù)測和可達(dá)性檢測

在此次實驗中,首先在鏈接預(yù)測的任務(wù)中,分別對每個節(jié)點v選取樣本向量,選取節(jié)點v的1/2|Nv|個鄰居節(jié)點作為正樣本,z(u,v)=zu+zv,其中,‘+’表示拼接,相應(yīng)的類為1,表示兩節(jié)點有邊,然后在圖中隨機選取同樣數(shù)目節(jié)點,然后判斷節(jié)點v和ui是否存在邊:如有邊,則向量對應(yīng)的類為1;否則為0.而在時序可達(dá)性檢測的實驗中,通過計算兩節(jié)點是否滿足時序可達(dá),進(jìn)行分配向量的類別.在對所有節(jié)點完成樣本采集后,取其中的20%為訓(xùn)練集,其余的80%為測試集,測試結(jié)構(gòu)見表3,其中的數(shù)據(jù)值都是取自不同游走長度下所得到結(jié)果的最高值.

Table 3 Accuracy of link prediction and temporal achievability (%)表3 鏈接預(yù)測和時序可達(dá)性檢測準(zhǔn)確性 (%)

首先需要說明的是:時序圖節(jié)點的嵌入在鏈接預(yù)測的問題上受限于其游走策略的影響,其結(jié)果有很大的可能性弱于普通游走策略的,特別是在節(jié)點間聯(lián)系時刻很少的情況下.正如表3 所示:在數(shù)據(jù)集D0 和D1 中,基于時序采樣的方法在鏈接預(yù)測上有明顯的弱勢.因為從D0 和D1 中的數(shù)據(jù)信息可以看出,節(jié)點間的聯(lián)系是非常單一的.由于是貨幣交易網(wǎng)絡(luò),用戶間在全局范圍內(nèi)只有一次聯(lián)系,即時序邊和靜態(tài)邊相同,這也就導(dǎo)致任何基于時序游走策略的方法的游走長度都會更大程度地受時間因素所限制.但是當(dāng)隨著用戶聯(lián)系次數(shù)增加,本文所提出的算法和DeepWalk 和Node2vec 的差距也就越小,在數(shù)據(jù)集D2 中只有微小的差距,而在D3 數(shù)據(jù)中生成了更好的實驗結(jié)果.

在節(jié)點間的時序可達(dá)性檢測問題上,形勢則會發(fā)生改變.在此問題上,傳統(tǒng)游走策略的準(zhǔn)確度會有明顯的下降.因為傳統(tǒng)的游走策略是完全沒有考慮節(jié)點間的時序關(guān)系的,即節(jié)點的表達(dá)向量中并沒有充分保存節(jié)點間的時序特性,而基于時序圖游走的策略在采樣過程中遵循時序可達(dá)這一條件的.并且從中可以看出:ATGEB 在數(shù)據(jù)集D0 和D1 中有著明顯的優(yōu)勢,而在D2 和D3 中不如前者更明顯.這是因為在后兩種的數(shù)據(jù)集中,節(jié)點的活躍頻率更高,節(jié)點間的聯(lián)系更頻繁,節(jié)點的路徑所滿足時序可達(dá)性的幾率也就越大(相較于前兩種數(shù)據(jù)集).

6.4 節(jié)點分類和重要節(jié)點采樣

在本小節(jié)的實驗測試中,主要集中在節(jié)點的分類和重要節(jié)點的采樣.在重要節(jié)點的采樣中,對比了對于不同訓(xùn)練集且選取方式不同下的訓(xùn)練時間和結(jié)果.其中的訓(xùn)練集的選取方式有3 種:一是正常取20%的數(shù)據(jù)集S作為訓(xùn)練集;一種隨機取十分之一S規(guī)模的數(shù)據(jù)集作為訓(xùn)練集;最后一種是在第4 節(jié)中所介紹的重要節(jié)點采樣的方式,同樣選取和第2 種同等數(shù)量的數(shù)據(jù)集作為訓(xùn)練集.然后對比在完全相同的神經(jīng)網(wǎng)絡(luò)中的訓(xùn)練時間和測結(jié)果的變化情況,來判斷重要節(jié)點的采樣是否可以通過在盡可能少的誤差內(nèi)用更短的時間訓(xùn)練數(shù)據(jù).

在測試的時序圖數(shù)據(jù)集中并沒有對節(jié)點所屬的類進(jìn)行標(biāo)注,所以在此次實驗中,通過兩種方式對節(jié)點進(jìn)行標(biāo)注3 種類型來進(jìn)行模擬實驗驗證.因為在實際的數(shù)據(jù)集中,屬于相同類的節(jié)點相對而言都有更短的跳數(shù)距離,基于此,通過以下兩種方式對節(jié)點進(jìn)行模擬標(biāo)注分類.

? 第1 種方式是選取若干個距離盡可能遠(yuǎn)的節(jié)點u1,…,uk,分別標(biāo)注為C1,C2,C3,然后以這些節(jié)點為中心,取得這些節(jié)點相近鄰居的集合S1u,將這些集合中的節(jié)點60%的節(jié)點標(biāo)注和中心節(jié)點相同的類,然后剩余的節(jié)點進(jìn)行隨機標(biāo)注;

? 第2 種方式是中心節(jié)點在選取臨近節(jié)點時需要滿足時序可達(dá),得到集合,后續(xù)的標(biāo)注類的方法同第1 種.

通過這兩種方式的對比,來盡可能真實、客觀地評價本文方法的實驗結(jié)果.而之所以沒有使用對節(jié)點進(jìn)行隨機標(biāo)注3 種類型的方式,因為隨機標(biāo)注的策略會導(dǎo)致本來非常相似的兩個向量賦予了不同的類,導(dǎo)致最后只能識別出一種類型,經(jīng)過實驗而放棄了這種策略.盡管如此,這種模擬的方法還是難免出現(xiàn)上述問題,只能做到盡可能的準(zhǔn)確.

實驗的結(jié)果見表4,從中可以看出:在考慮節(jié)點間的時序性時,傳統(tǒng)的采樣方法在結(jié)果上都會呈現(xiàn)出不同程度的下降;基于時序游走策略的方法可以更好地保留節(jié)點間的時序關(guān)系,從而得出更好地實驗結(jié)果.在圖9 中,注意:由于有的數(shù)據(jù)集規(guī)模較小訓(xùn)練時間較短,為了更方便看清實驗的結(jié)果,左子圖的橫坐標(biāo)并不是按比例繪制的.同時,以第1 種方式(不考慮時序性)的采樣策略進(jìn)行重要節(jié)點采樣的結(jié)果對比.其中,在各個對應(yīng)數(shù)據(jù)下方,左邊的數(shù)據(jù)集為隨機選取的結(jié)果,相鄰右邊的數(shù)據(jù)集為通過重要節(jié)點策略選取的節(jié)點的實驗結(jié)果.結(jié)合左右兩個子圖可以看出,重要節(jié)點采樣的策略可以在一定的誤差損失范圍內(nèi)(本實驗中可以控制在2%以內(nèi))且在更短的時間完成神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練.

Table 4 Accuracy of nodes classification (%)表4 節(jié)點分類準(zhǔn)確性 (%)

7 相關(guān)工作

和靜態(tài)圖不同,時序圖中的邊會隨時間呈現(xiàn)出兩種相互轉(zhuǎn)化的狀態(tài):活躍和非活躍.時序圖中的頂點只有在邊處于活躍狀態(tài)下是存在聯(lián)系的.現(xiàn)實中有很多時序網(wǎng)絡(luò)的例子,如:

(1)通信網(wǎng)絡(luò):電郵和手機通訊、短信等都是非常典型的點對點時序網(wǎng)絡(luò);

(2)一對多的信息傳播網(wǎng)絡(luò):這種時序網(wǎng)絡(luò)特點是單一用戶向其余多個用戶傳播信息;

(3)生物信息網(wǎng)絡(luò):如腦神經(jīng)元網(wǎng)絡(luò)、代謝網(wǎng)絡(luò)和蛋白質(zhì)互作用網(wǎng)絡(luò)等.

如今,在數(shù)據(jù)庫領(lǐng)域,面向時序圖的研究工作主要集中在可達(dá)性查詢、最短時序路徑和到達(dá)時間預(yù)測[25?27]等方向.

圖節(jié)點嵌入的工作最早引起人們的注意始于DeepWalk[2]算法的提出,DeepWalk 算法開創(chuàng)性地將圖的隨機游走策略和自然語言處理中的skip-gram[3]文字向量化表達(dá)模型相結(jié)合,通過這種極具創(chuàng)新性的方法完成了圖節(jié)點的向量化表達(dá)工作.而后的研究者們[4?7]在DeepWalk 算法的基礎(chǔ)上,希望通過一種有偏采樣的方式對這種方法進(jìn)行改進(jìn),進(jìn)而設(shè)計出了不同的節(jié)點采樣策略,如node2vec,LINE,PTE 以及stru2vec 等節(jié)點嵌入方法.雖然這些算法在相應(yīng)的圖數(shù)據(jù)集上,在鏈接預(yù)測和節(jié)點分類等問題上都宣稱取得了更好的實驗效果,但是相較于DeepWalk 算法并沒有質(zhì)的提升,并且不同的采樣策略在不同的數(shù)據(jù)集上效果有時會出現(xiàn)明顯的差異.由此給后續(xù)研究者們在研究節(jié)點嵌入表達(dá)問題上提供了啟發(fā),即:在現(xiàn)有神經(jīng)網(wǎng)絡(luò)框架訓(xùn)練能力有限的今天,圖節(jié)點嵌入的向量化表達(dá)的研究需要著眼于研究者所想要解決的具體問題和圖數(shù)據(jù)所屬的拓?fù)浣Y(jié)構(gòu)特征.如在異質(zhì)圖上做節(jié)點嵌入和在知識圖譜上的研究方式是不同的,而當(dāng)所要解決的問題不同時,如做節(jié)點分類和商品推薦,也會因所研究問題的不同而做出符合問題實際需要的研究策略.

社區(qū)發(fā)現(xiàn)[28,34,35]是一個在圖數(shù)據(jù)挖掘中經(jīng)久不衰的研究方向.在問題的起始階段,研究者們主要致力于將拓?fù)渚嚯x相近的網(wǎng)絡(luò)用戶聚集在一起,形成一個社區(qū).而隨著問題的深入研究和現(xiàn)實一些實際的應(yīng)用需求,研究者們更傾向于將“興趣點”一致的用戶聚集在一起,形成一個基于共同“興趣點”的社區(qū).在這個社區(qū)中,各個用戶通常有著共同的興趣或類似的屬性,如此可以通過這些興趣點,更精準(zhǔn)地向用戶推薦他們感興趣的信息或者所需商品.

8 展 望

本文的研究工作主要集中在面向無屬性的時序圖節(jié)點嵌入問題上,并進(jìn)行了相關(guān)實驗,在各個方面驗證了所提出算法的有效性和可擴展性.在屬性缺失的時序圖上是無法使用圖卷積的思想對節(jié)點進(jìn)行表達(dá)學(xué)習(xí)的,所以本文中的嵌入策略無法有效地將節(jié)點的屬性信息嵌入到節(jié)點向量中去.在未來的研究工作中:(1)將考慮基于屬性時序圖的節(jié)點表達(dá)工作的研究,擬在現(xiàn)有圖卷積思想的基礎(chǔ)上研究節(jié)點屬性和節(jié)點時序關(guān)系的關(guān)聯(lián),進(jìn)而提出一種可以在屬性時序圖上進(jìn)行時序圖卷積的圖表達(dá)學(xué)習(xí)的策略;(2)本文也嘗試了面向圖數(shù)據(jù)的重點采樣工作,在后續(xù)的研究工作中,會對樣本節(jié)點做出更充分的考慮,不僅僅只是局限于節(jié)點的拓?fù)浣Y(jié)構(gòu),同樣也將考慮節(jié)點間的屬性關(guān)系,借助于圖數(shù)據(jù)相關(guān)挖掘算法進(jìn)行重要節(jié)點的選取,力求使得所選取的節(jié)點向量更具有代表性和統(tǒng)一性,從而能更好、更快地在神經(jīng)網(wǎng)絡(luò)中訓(xùn)練出所需的權(quán)重參數(shù).