時序優先級約束的時序模式圖強模擬匹配

金浩宇,霍 宏,方 濤

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

0 引 言

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

圖1 任務合作時序圖

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

針對時序圖特有的時序屬性兼顧其拓撲結構,提出了時序優先級約束的時序模式圖強模擬匹配算法,該算法在匹配過程中,不僅對拓撲結構進行檢查,還將各條邊的時序優先級作為局部約束,并設置了冗余頂點過濾規則來縮小搜索范圍,以及對時序檢查的隊列順序進行優化使得算法能夠提前剪枝,減少了計算復雜度,所提出的方法兼具子圖同構和圖模擬的優勢,實現了既準確又高效的圖匹配。在三個時序數據集上的大量實驗表明,相比傳統的強模擬算法,所提算法能夠有效過濾錯誤結果,并且在不同規模的數據圖上均具有良好的性能表現。

1 相關工作

1.1 近似匹配

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

1.2 時態圖及其圖模式匹配

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

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

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

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

定義1 雙向模擬。給定一個模式圖Q=(Vq,Eq,Lq)和一個數據圖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)和一個數據圖G=(V,E,L),若在G中存在一個頂點v和一個連通子圖Gs(Vs,Es)滿足以下條件,則說G通過強模擬匹配Q：

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

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

時態圖的邊具有時間屬性,其形式化描述為：

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

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

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

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

3 文中算法

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

3.1 TPC-GPSSM算法

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

算法1 TPC-GPSSM

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

輸出：匹配結果集合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給出了拓撲結構檢查的偽代碼CheckTopology,主要功能是對球內的子圖進行檢查,去除在時序優先級約束下因刪除時態邊而產生的不符合QT拓撲結構要求的頂點和邊。對頂點候選集sim(v)中的任意頂點u,首先檢查其后繼關系,后繼頂點集合為succ(u),后繼頂點候選集為sim(v'),若succ(u)∩sim(v')=?,則將該節點及其關聯的邊從候選集合中刪除;然后檢查其前驅關系,前驅頂點集合為pred(u),前驅頂點候選集為sim(v''),若pred(u)∩sim(v'')=?,則將相關頂點和邊刪除(見第1-5行)。若頂點和邊候選集均非空,則將其構造成一個子圖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在球的建立過程花費了很多時間,主要因為每個球包含了很多無用的拓撲結構信息,并且在時序檢查過程中存在重復檢查的問題。如果能減少每個球的計算量, 避免時序的重復檢查,將大大提升算法的效率。

3.2 TPC-GPSSM算法優化方法

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

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

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

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

算法5 優化后的TPC-GPSSM算法

輸入：時序模式圖QT=(Vq,Eq,Lq)及其直徑dq,時態圖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

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

4 實驗與結果分析

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

表1 數據集

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

4.1 算法有效性實驗

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

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

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

圖2 不同數據集上匹配質量的評價

4.2 算法效率實驗

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

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

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

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

圖4 時序優先級數量對匹配結果的影響

5 結束語

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