時序優(yōu)先級約束的時序模式圖強模擬匹配

金浩宇,霍 宏,方 濤

(上海交通大學 電子信息與電氣工程學院,上海 200240)

0 引 言

圖模式匹配是指在圖數(shù)據(jù)中搜索與待查詢模式圖相同或相似的子圖的一類算法,是實現(xiàn)圖數(shù)據(jù)高效率查詢的重要手段,已經(jīng)應用于眾多的領域。例如社交網(wǎng)絡分析[1]、知識分析[2]等。現(xiàn)有的圖模式匹配方法大多僅適用于靜態(tài)圖,不適用于在現(xiàn)實世界中廣泛存在的時態(tài)圖[3-4],即圖數(shù)據(jù)中的兩個頂點之間的邊具有時間屬性,其記錄了兩個頂點之間關系的開始與結(jié)束時間。圖1(a)給出了一個任務合作時序圖,圖中每個頂點表示一個人,頂點標簽A,B,C,D,E表示不同的職業(yè),頂點之間的有向邊表示兩個人之間交接任務的方向,每條邊上都有一個時間區(qū)間(s,f)表示任務交接的開始時間s與結(jié)束時間f。

圖1 任務合作時序圖

假設有一個任務合作模式圖QT,如圖1(b)所示,QT中每條邊ei都具有一個時序優(yōu)先級,時序優(yōu)先級規(guī)定了低優(yōu)先級邊的開始時間一定要晚于高優(yōu)先級邊的結(jié)束時間,即模式圖QT隱含著一種時序約束,該文稱其為時序模式圖,其中A先與B交接任務,然后A在接收了B和E的交接信息后,再與C進行交接,最后C與D完成任務交接?，F(xiàn)要在如圖1(a)所示的任務合作時序圖上查詢與QT相同或相似的子圖。如果采用靜態(tài)的圖模擬匹配方法,可以得到的一個匹配結(jié)果的邊集合為{e1,e2,e3,e4,e6,e7},顯然,由于沒有考慮邊具有的時序?qū)傩?邊e7并不滿足模式圖QT中的時序約束,而正確的匹配結(jié)果如圖1(c)所示。除了時序約束外,觀察圖1(b),不難發(fā)現(xiàn)模式圖QT中還存在環(huán)路,如A→B→A等,而現(xiàn)有的時態(tài)圖模式匹配方法無法處理模式圖中的環(huán)路。因此,需要研究適合于時態(tài)圖并能處理環(huán)路的時序模式圖匹配方法。

針對時序圖特有的時序?qū)傩约骖櫰渫負浣Y(jié)構(gòu),提出了時序優(yōu)先級約束的時序模式圖強模擬匹配算法,該算法在匹配過程中,不僅對拓撲結(jié)構(gòu)進行檢查,還將各條邊的時序優(yōu)先級作為局部約束,并設置了冗余頂點過濾規(guī)則來縮小搜索范圍,以及對時序檢查的隊列順序進行優(yōu)化使得算法能夠提前剪枝,減少了計算復雜度,所提出的方法兼具子圖同構(gòu)和圖模擬的優(yōu)勢,實現(xiàn)了既準確又高效的圖匹配。在三個時序數(shù)據(jù)集上的大量實驗表明,相比傳統(tǒng)的強模擬算法,所提算法能夠有效過濾錯誤結(jié)果,并且在不同規(guī)模的數(shù)據(jù)圖上均具有良好的性能表現(xiàn)。

1 相關工作

1.1 近似匹配

近似匹配放松了圖匹配條件,成為廣泛采用的一種圖模式匹配方法,主要包括圖模擬[5]、雙向模擬[6]、強模擬[7]、受限模擬[8]、量化模擬[9-10]等。圖模擬要求匹配每個節(jié)點以及其子節(jié)點。雙向模擬在圖模擬的基礎上還要匹配父節(jié)點。強模擬在雙向模擬基礎上還需考慮匹配子圖的局部特性。受限模擬是指在模式圖上對跳躍次數(shù)進行了限制。量化模擬關注了圖上的具有計數(shù)量詞的表達模式。上述的近似匹配方法都只考慮了圖的拓撲結(jié)構(gòu),而忽略了圖上的時間信息,無法用來解決在時態(tài)圖上的匹配問題。

1.2 時態(tài)圖及其圖模式匹配

時態(tài)圖主要用于對實體及其之間涉及的時態(tài)關系進行建模,是在靜態(tài)圖的基礎上演變的一種新型圖數(shù)據(jù)[11]。目前,關于時態(tài)圖的研究主要包括可達性查詢[12]、最小生成樹[13]、最短時態(tài)路徑[14]等。

時態(tài)圖上的圖模式匹配問題的研究才剛剛起步,Xu等[15]研究了時態(tài)圖同構(gòu)匹配,提出了時間約束的模式圖匹配算法(Time-Constrained Graph Pattern Matching,TCGPM),但同構(gòu)匹配要求匹配到與查詢模式圖完全相同的子圖,過于嚴格。Song等[16]研究了圖流上的事件模式匹配,將時間窗口概念引入了子圖匹配并提出了DDST(Degree-Preserving Dual Simulation with Timing Constraints)算法,且基于標簽過濾與度約束的思想提出了兩個優(yōu)化算法DDST-SIGNATURE和COLORING以提升算法的運行效率,但是這些算法將給定時間窗口的時態(tài)圖快照作為靜態(tài)圖處理,容易導致遺漏部分結(jié)果。Ma等[17]根據(jù)受限模擬和時態(tài)路徑定義了時態(tài)圖上的圖模式匹配并基于連接的方式枚舉匹配結(jié)果,但是這種方法的匹配條件過于寬松,并且不允許模式圖中出現(xiàn)環(huán)路。

2 模式圖匹配與時序模式圖匹配的形式化描述

雙向模擬和強模擬是經(jīng)典的模式圖匹配算法,兩者的形式化描述如下：

定義1 雙向模擬。給定一個模式圖Q=(Vq,Eq,Lq)和一個數(shù)據(jù)圖G=(V,E,L),如果存在一個二元匹配關系S?Vq×V且滿足下列條件,則說G通過雙向模擬匹配Q：

(1)每一對(u,v)∈S,u和v都有相同的標簽;

(2)對每個v∈Vq,存在u∈V滿足(u,v)∈S且每一條邊e'(v,v1)∈Eq都存在一條邊e(u,u1)∈E使得(u1,v1)∈S;

(3)對每個v∈Vq,存在u∈V滿足(u,v)∈S且每一條邊e'(v2,v)∈Eq都存在一條邊e(u2,u)∈E使得(u2,v2)∈S。

定義2 強模擬。給定一個模式圖Q=(Vq,Eq,Lq)和一個數(shù)據(jù)圖G=(V,E,L),若在G中存在一個頂點v和一個連通子圖Gs(Vs,Es)滿足以下條件,則說G通過強模擬匹配Q：

(1)Q對Gs滿足雙向模擬匹配,且有最大二元匹配關系S,即Q在G上的任意二元匹配關系SA都有SA?S。

(2)Gs是S構(gòu)成的圖,即(a)有一個頂點w∈Vs當且僅當它存在于S。(b)有一條邊e(w,w')∈Es當且僅當在Q中存在一條邊e'(u,u')使得(u,w)∈S且(u',w')∈S。

時態(tài)圖的邊具有時間屬性,其形式化描述為：

定義3 時態(tài)圖。給定一個有向帶標簽的圖GT=(V,E,L),其中V是頂點的集合;E∈V×V是有向時態(tài)邊的集合;L是一個標簽函數(shù),可將每個頂點u∈V映射到其對應的標簽L(u)。假設圖中一條有向時態(tài)邊ei∈E連接了兩個頂點u,v∈V,可表示為一個四元組(u,v,si,fi),該四元組的含義為兩個頂點u和v的關系從時間點si開始到時間點fi結(jié)束。

時態(tài)圖的模式圖及其強模擬匹配算法的形式化描述如下：

定義4 時序模式圖。一個時序模式圖表示為QT=(Vq,Eq,Lq),其中Vq是頂點的集合,Lq是一個標簽函數(shù),Eq∈Vq×Vq是有向時序優(yōu)先級邊的集合。一條有向時序優(yōu)先級邊ei∈Eq可表示為一個三元組(u,v,pi),其中pi為ei的時序優(yōu)先級。時序模式圖不關心具體的時間范圍,而是通過時序優(yōu)先級規(guī)定每條邊代表的事件發(fā)生的先后順序,時序優(yōu)先級低的事件必須在時序優(yōu)先級高的事件結(jié)束之后發(fā)生。

定義5 時序強模擬匹配。給定一個時序模式圖QT=(Vq,Eq,Lq)和一個時態(tài)數(shù)據(jù)圖GT=(V,E,L),如果滿足以下條件,則稱G通過時序強模擬匹配QT：

3 文中算法

該文提出的時序優(yōu)先級約束的時序模式圖強模擬匹配算法(Temporal Priority Constrained Graph Pattern Strong Simulation Matching,TPC-GPSSM)針對時序圖特有的時序特性,將各條邊的時序優(yōu)先級作為局部約束,在匹配過程中,能夠同時兼顧時序圖邊具有的時序優(yōu)先級及其拓撲結(jié)構(gòu),也適用于帶環(huán)路的時序模式圖的匹配。

3.1 TPC-GPSSM算法

TPC-GPSSM算法主要先在時態(tài)圖上構(gòu)建球,然后在球上進行時序優(yōu)先級約束的強模擬匹配。在時態(tài)圖上構(gòu)建球采用廣度優(yōu)先遍歷(Breath First Search,BFS)算法[18],以每個頂點為球心,構(gòu)造半徑為時序模式圖直徑的球,可將構(gòu)建好的每個球看作是時態(tài)圖的一個子圖。然后,將每個球與時序模式圖進行雙向模擬匹配,在匹配過程中,一方面要計算每個球其所包含的二元匹配關系,并檢查時序優(yōu)先級約束,找到最大的二元匹配關系。另一方面,在匹配的同時還進行拓撲結(jié)構(gòu)檢查,以保證匹配的子圖與時序模式圖匹配。

算法1 TPC-GPSSM

輸入：時序模式圖QT=(Vq,Eq,Lq)及其直徑dq,時態(tài)圖GT=(V,E,L)

輸出：匹配結(jié)果集合S

1.S：=?,B：=?

2.for eachvinVdo

6.sim(v),sim(e')：=TemporalFilter(QT,sim(v),sim(e'))

7.Gs：=CheckTopology(QT,sim(v),sim(e'))

8.ifGs≠? then

9.S：=S∪Gs

10.returnS

算法2 DualSimMatch

輸出：候選頂點集合sim(v),候選邊集合sim(e')

1.for eachv∈Vqdo

2.sim(v)：={u|uis inG[v,dq] andLq(u)}

3.for eache(v,v1)∈Eqdo

4.sim(e')：={e|e(u,u1)is inG[v,dq],u∈sim(v),u1∈sim(v1)}

5.while there are changes do

6. for eachu∈sim(v) do

7. for eache(v,v') inEqdo

9.Removeuand edges containingufrom sim(v) and sim(e')

10. for eache(v',v) inEqdo

12.Removeuand edges containingufrom sim(v) and sim(e')

13.return sim(v),sim(e')

算法3 TemporalFilter

輸入：時序模式圖QT,候選頂點集合sim(v),候選邊集合sim(e')

輸出：候選頂點集合sim(v),候選邊集合sim(e')

1.while there are changes do

4. ifp1>p2ands1

7. Removeu,u1and all edges containingu,u1from sim(v) and sim(e')

8.return sim(v),sim(e')

算法4給出了拓撲結(jié)構(gòu)檢查的偽代碼CheckTopology,主要功能是對球內(nèi)的子圖進行檢查,去除在時序優(yōu)先級約束下因刪除時態(tài)邊而產(chǎn)生的不符合QT拓撲結(jié)構(gòu)要求的頂點和邊。對頂點候選集sim(v)中的任意頂點u,首先檢查其后繼關系,后繼頂點集合為succ(u),后繼頂點候選集為sim(v'),若succ(u)∩sim(v')=?,則將該節(jié)點及其關聯(lián)的邊從候選集合中刪除;然后檢查其前驅(qū)關系,前驅(qū)頂點集合為pred(u),前驅(qū)頂點候選集為sim(v''),若pred(u)∩sim(v'')=?,則將相關頂點和邊刪除(見第1-5行)。若頂點和邊候選集均非空,則將其構(gòu)造成一個子圖Gs(見第6-8行)。

算法4 CheckTopology

輸入：時序模式圖QT,候選頂點集合sim(v),候選邊集合sim(e')

輸出：匹配子圖Gs

1.While there are changes do

2. for eachu∈sim(v) do

3. if succ(u)∩sim(v')=? or pred(u)∩sim(v'')=? then

4.sim(v)：=sim(v){u}

5.remove all edges containingufrom sim(e')

6.if sim(v),sim(e')≠? then

7. constructGsfrom sim(v),sim(e')

8.returnGs

TPC-GPSSM在球的建立過程花費了很多時間,主要因為每個球包含了很多無用的拓撲結(jié)構(gòu)信息,并且在時序檢查過程中存在重復檢查的問題。如果能減少每個球的計算量, 避免時序的重復檢查,將大大提升算法的效率。

3.2 TPC-GPSSM算法優(yōu)化方法

針對上文提及的TPC-GPSSM算法存在很多重復計算的問題,進一步對球的建立過程、時態(tài)優(yōu)先級約束等方面進行優(yōu)化,算法5給出了優(yōu)化后的TPC-GPSSM算法的偽代碼,主要包括：

第一,在球的建立過程中,TPC-GPSSM算法對數(shù)據(jù)圖中每個頂點,都作為中心建立了球,然而其中大量的球并沒有包含能夠匹配模式圖的子圖,對這些球的計算浪費了大量時間。在建球之前先進行雙向模擬匹配(見第2行),能夠過濾掉大量的節(jié)點與邊,這樣既能減少需要建立的球的數(shù)量,也能使每個球包含的子圖規(guī)模減小。

第二,在對球心的選擇方面,只選擇與模式圖中距離最遠的兩個節(jié)點相匹配的節(jié)點(見第3-8行),如圖1(b)所示,E、D是模式圖中距離最遠的兩個點,以E對應的頂點E2為球心建球得到的結(jié)果與以A1為球心建立球得到的結(jié)果相同,因此計算以A1為球心的球是冗余的。

第三,在時序優(yōu)先級約束過程中,先對模式圖中的邊根據(jù)時序優(yōu)先級進行排序,從高優(yōu)先級的邊開始依次檢查,每一條邊只檢查與其相鄰的時序優(yōu)先級更高的邊的之間的時序關系,可避免重復時序檢查。

算法5 優(yōu)化后的TPC-GPSSM算法

輸入：時序模式圖QT=(Vq,Eq,Lq)及其直徑dq,時態(tài)圖GT=(V,E,L)

輸出：子圖集合S

1.S：=?,B：=?

3.vf1,vf2are the farthest two nodes inQ

4.for eachv∈sim(vf1) or sim(vf2) do

10. forpfrom the highest priority to the lowest priority do

11.simb(v),simb(e')：= TemporalFilter(QT,simb(v),simb(e))

12.Gs：=CheckTopology(QT,simb(v),simb(e))

13. ifGs≠? then

14.S：=S∪Gs

15.ReturnS

優(yōu)化后的TPC-GPSSM算法大幅減少了球的數(shù)量,同時避免了球之間因為交集而進行的重復計算,且保證了對每條時序邊只檢查一次,解決了重復檢查的問題。

4 實驗與結(jié)果分析

本章節(jié)對分別從算法有效性以及算法效率兩個維度來評估提出的算法,并對普通的強模擬匹配算法[19](General Strong Simulation,GSS)與TPC-GPSSM及優(yōu)化后的TPC-GPSSM算法進了比較。實驗采用三個時態(tài)數(shù)據(jù)集,分別是：(1)BMC[20],一個小學師生相互接觸時態(tài)網(wǎng);(2)Enron[21],一個電子郵件傳輸網(wǎng)絡;(3)Wikitalk-Russian[22],一個Russian Wikipedia上的交流網(wǎng)絡。表1列出了這些數(shù)據(jù)集的詳細參數(shù),其中|V|、|E|、|T|、#labels分別是數(shù)據(jù)集的頂點數(shù)量、邊的數(shù)量、邊的平均時間區(qū)間、標簽數(shù)量。

表1 數(shù)據(jù)集

模式圖由一個自行開發(fā)的模式圖生成器提供。給定模式圖的頂點數(shù)量和標簽集合,模式圖生成器隨機生成包含不同時序優(yōu)先級數(shù)量的模式圖。實驗對每個數(shù)據(jù)集分別生成了100個模式圖,對其平均結(jié)果進行評估。

4.1 算法有效性實驗

首先,對TPC-GPSSM算法的有效性進行了實驗驗證。TPC-GPSSM算法相比傳統(tǒng)強模擬匹配算法,能夠有效地過濾不符合時態(tài)要求的邊。為了定量地描述算法有效性,定義了一個評價指標——時態(tài)邊聚合度(Temporal Edge Closeness,TEC)。

給定一個時序模式圖QT=(Vq,Eq,Lq),以及一組作為匹配結(jié)果返回的子圖{M1,M2,…,Mn},TEC定義如下式：

其中,|EMj|是Mj中時態(tài)邊的數(shù)量,|Eq|是模式圖的邊數(shù)量,TEC的值越小說明對時態(tài)邊的過濾效果越明顯。對三個數(shù)據(jù)集的實驗結(jié)果如圖2所示,實驗改變時序模式圖頂點數(shù)量|Vq|從2到5,分別在三個數(shù)據(jù)集上進行測試。其中,GSS由于沒有考慮時態(tài)邊的順序,所以得到了最大的TEC值,而TPC-GPSSM及其改進算法對不合模式圖需求的時態(tài)邊進行了過濾,得到了更優(yōu)的TEC值。

圖2 不同數(shù)據(jù)集上匹配質(zhì)量的評價

4.2 算法效率實驗

這里通過二個實驗,分別考察時序模式圖、不同時序優(yōu)先級數(shù)量對TPC-GPSSM算法效率和性能的影響。

(1)時序模式圖頂點數(shù)量|Vq|對算法效率的影響。設置了2到10不同大小的|Vq|,在三個數(shù)據(jù)集上進行了實驗。實驗結(jié)果如圖3所示,可以觀察到,三種算法的匹配時間都隨著|Vq|的增大而增加,這是因為當|Vq|增大時,需要匹配的節(jié)點和邊的數(shù)量也同時增加,這將增加計算的時間花銷。優(yōu)化后的TPC-GPSSM算法采用了先進行雙向模擬匹配,再建立球進行局部性檢查,使得球的數(shù)量大幅減少,取得了更加良好的性能表現(xiàn)。

圖3 時序模式圖大小對算法效率的影響

(2)不同時序優(yōu)先級數(shù)量對匹配結(jié)果的影響。實驗中固定模式圖的|Vq|為10,改變其中的時序優(yōu)先級數(shù)量,實驗結(jié)果如圖4所示。當時序優(yōu)先級數(shù)量增加時,意味著匹配條件更加嚴格,符合條件的子圖數(shù)量也隨之減少,而GSS不考慮時序關系,時序優(yōu)先級數(shù)量不影響它的匹配結(jié)果。

圖4 時序優(yōu)先級數(shù)量對匹配結(jié)果的影響

5 結(jié)束語

針對時態(tài)圖上的模式圖匹配,提出了一種時序優(yōu)先級約束的時序模式圖強模擬匹配算法(TPC-GPSSM),該算法將時序優(yōu)先級作為局部約束,在模式圖的匹配過程中考慮了時態(tài)圖中不同時態(tài)邊之間的時序優(yōu)先級,并兼顧圖的拓撲結(jié)構(gòu),通過設置冗余頂點過濾規(guī)則來縮小搜索范圍,優(yōu)化時序檢查的隊列順序,以達到提前剪枝、減少計算復雜度的目的。提出并利用時態(tài)邊聚合度作為評價指標,在三個時序數(shù)據(jù)集上的大量實驗表明,相比普通的強模擬算法,所提算法能夠有效過濾錯誤結(jié)果,并且在不同規(guī)模的數(shù)據(jù)圖上均具有良好的性能表現(xiàn)。該算法可應用于涉及前后時序關系的場景,如任務交接分析、交通網(wǎng)絡分析等,特別是在任務交接中存在環(huán)路的情況下該算法也能進行有效的處理。在下一步的工作中,一個方向是考慮不同時間窗口的約束,另一個方向是在分布式環(huán)境中開發(fā)更性能更高的算法。