時(shí)態(tài)圖上圖模式匹配研究綜述

李發(fā)明，鄒兆年，李建中

（哈爾濱工業(yè)大學(xué) 計(jì)算學(xué)部，哈爾濱 150001）

0 引言

在眾多圖研究問題中，圖模式匹配（graph pattern matching）問題一直占據(jù)著重要的地位。現(xiàn)有的研究一般根據(jù)子圖同構(gòu)（subgraph isomorphism）定義圖模式匹配問題［1］。給定一個查詢模式圖Q和數(shù)據(jù)圖G，圖模式匹配問題是在G中查找Q的所有匹配。Q的一個匹配是滿足如下條件的G的一個子圖H：存在一個從Q的頂點(diǎn)集到H的頂點(diǎn)集的雙射函數(shù)（bijective function），使得當(dāng)且僅當(dāng)（f（v），f（v＇））是H中的一條邊時(shí)，（v，v＇）是Q中的一條邊。如果圖中頂點(diǎn)存在標(biāo)簽，則要求Q中頂點(diǎn)v的標(biāo)簽同H中頂點(diǎn)f（v）的標(biāo)簽相同。H則稱為Q在G中的一個匹配。圖模式匹配問題是很多研究的基礎(chǔ)，例如，圖數(shù)據(jù)庫、知識圖譜查詢處理、圖挖掘、計(jì)算機(jī)視覺等等。然而，現(xiàn)有的圖模式匹配研究主要關(guān)注查詢模式圖的結(jié)構(gòu)，常常忽略了圖數(shù)據(jù)上的時(shí)態(tài)圖信息。下面兩個實(shí)際例子說明了時(shí)態(tài)信息在圖模式匹配問題中的重要性。

（1）美國通訊公司Verizon 每年都會公布安全事故報(bào)告，而這些安全事故中的攻擊模式都帶有時(shí)態(tài)信息，即這些模式都可以表示成帶有時(shí)態(tài)信息的圖模式。圖1 中給出了其中一種攻擊模式，圖中頂點(diǎn)表示服務(wù)器或者被攻擊的終端，頂點(diǎn)之間的邊表示服務(wù)器和終端之間的通信，邊上的t表示通信時(shí)間，圖模式對通信時(shí)間要求是t1＜t2＜t3＜t4＜t5。監(jiān)測這種常見的攻擊模式將有利于識別惡意軟件及其服務(wù)器。

圖1 攻擊模式Fig.1 Cyber－attach pattern

（2）圖2 給出3 個科研人員以合作的模式在同一個會議上發(fā)表論文的情況，其中頂點(diǎn)表示研究人員，頂點(diǎn)之間的邊表示合作關(guān)系，圖下面的文字表示會議的名稱及合作的時(shí)間。了解不同科研人員之間的合作模式及持續(xù)時(shí)間將更好地發(fā)現(xiàn)研究團(tuán)隊(duì)及研究方向。

圖2 長期合作模式Fig.2 Durable cooperation

鑒于時(shí)態(tài)信息對于圖數(shù)據(jù)查詢、分析的重要性，而現(xiàn)有關(guān)于圖模式匹配的研究又很少考慮時(shí)態(tài)信息，本文從時(shí)態(tài)圖的不同模型和時(shí)態(tài)信息的不同特性出發(fā)，對時(shí)態(tài)圖上的圖模式匹配問題進(jìn)行了全面地綜述。

1 常見時(shí)態(tài)圖模型

時(shí)態(tài)圖數(shù)據(jù)（temporal graph data），也稱為演化圖數(shù)據(jù)（evolving graph data）、歷史圖數(shù)據(jù)（historical graph data），是在靜態(tài)圖數(shù)據(jù)基礎(chǔ)上演變的一種包含時(shí)態(tài)信息的新型圖數(shù)據(jù)［2］。時(shí)態(tài)圖中頂點(diǎn)、邊、頂點(diǎn)上的屬性、邊上屬性等都可以隨時(shí)間發(fā)生改變，一個典型的時(shí)態(tài)圖如圖3 所示，邊上的整數(shù)表示時(shí)間戳，即兩個頂點(diǎn)之間發(fā)生聯(lián)系的時(shí)間，例如：在社交網(wǎng)絡(luò)中，該時(shí)間可以表示兩個用戶發(fā)生通信的時(shí)間；在交通網(wǎng)絡(luò)中，該時(shí)間可以表示飛機(jī)從一個城市起飛并飛往另一個城市的時(shí)間；在銀行轉(zhuǎn)賬網(wǎng)絡(luò)中，該時(shí)間可以表示一個賬戶向另一個賬戶轉(zhuǎn)賬的時(shí)間等等。關(guān)聯(lián)時(shí)間的邊也被稱為時(shí)態(tài)邊。根據(jù)邊上時(shí)間的表示方式和存儲時(shí)態(tài)圖方式的不同，常見的時(shí)態(tài)圖模型有3 個，即快照模型、邊流模型和時(shí)間區(qū)間模型。

1.1 快照模型

快照模型（snapshot model）是時(shí)態(tài)圖研究中一種常用的數(shù)據(jù)模型。該模型將一個時(shí)間區(qū)間（time interval，即一段時(shí)間）內(nèi)的時(shí)態(tài)邊映射到同一張靜態(tài)圖上，即一張快照［3］。如果圖中某兩點(diǎn)之間在該時(shí)間區(qū)間內(nèi)存在多條時(shí)態(tài)邊，則多條時(shí)態(tài)邊只映射成兩點(diǎn)之間的一條邊。圖3 中的時(shí)態(tài)圖在快照模型下的表示如圖4 所示，其中時(shí)間區(qū)間大小為1。由于時(shí)間區(qū)間的大小設(shè)置為1，所以圖4 中的快照數(shù)目為4。需要注意的是不同大小的時(shí)間區(qū)間會導(dǎo)致同一個時(shí)態(tài)圖轉(zhuǎn)化為快照表示后快照數(shù)量不同、快照內(nèi)邊的數(shù)目不同。

圖3 時(shí)態(tài)圖示例Fig.3 An Example of temporal graph

圖4 快照模型Fig.4 Snapshot model

1.2 邊流模型

邊流模型（edge－stream model）采用類似日志的形式將每條時(shí)態(tài)邊單獨(dú)表示，該模型詳細(xì)地記錄了每一條邊每一次的變化。在通常情況下，所有的時(shí)態(tài)邊根據(jù)邊上的時(shí)態(tài)圖信息升序排列。在邊流模型中，一條邊一般采用三元組表示，三元組中包含兩個頂點(diǎn)及一個時(shí)刻，表示兩個點(diǎn)之間建立聯(lián)系的具體時(shí)間。圖3 中時(shí)態(tài)圖的對應(yīng)的邊流表示，如圖5 所示。邊流模型完整地記錄了時(shí)態(tài)圖所有的變化情況。

圖5 邊流模型Fig.5 Edge－stream model

1.3 區(qū)間模型

區(qū)間模型（interval model）不同于以上兩個模型表示離散時(shí)間的時(shí)態(tài)圖，區(qū)間模型關(guān)注的是邊上關(guān)聯(lián)時(shí)間區(qū)間的情況，即邊上的時(shí)態(tài)信息是連續(xù)的。時(shí)間區(qū)間表示兩點(diǎn)之間關(guān)系持續(xù)的時(shí)長，時(shí)間區(qū)間一般使用開始時(shí)間和終止時(shí)間表示。一個適用區(qū)間模型表示的時(shí)態(tài)圖，如圖6 所示。

圖6 區(qū)間模型Fig.6 Interval model

2 時(shí)態(tài)圖上圖模式匹配相關(guān)工作

相比于靜態(tài)圖上大量關(guān)于圖模式匹配的研究工作，時(shí)態(tài)圖上圖模式匹配的研究比較少。同靜態(tài)圖上的圖模式匹配相比較，時(shí)態(tài)圖上的圖模式匹配問題除了需要考慮查詢模式圖引入的結(jié)構(gòu)約束，還需要考慮定義在查詢模式圖的頂點(diǎn)或邊上的時(shí)態(tài)約束。所以，時(shí)態(tài)圖上的圖模式匹配問題相較于靜態(tài)圖上的圖模式匹配問題更加復(fù)雜［4］。根據(jù)時(shí)態(tài)數(shù)據(jù)的特點(diǎn)，本文總結(jié)出時(shí)態(tài)數(shù)據(jù)的3 個重要性質(zhì)，即時(shí)序性、持久性和演化性?；谶@3 個性質(zhì)，對時(shí)態(tài)圖上圖模式匹配相關(guān)工作進(jìn)行綜述。

（1）時(shí)序性（Temporality）：由于數(shù)據(jù)對象本身關(guān)聯(lián)時(shí)態(tài)信息，時(shí)態(tài)數(shù)據(jù)天然滿足時(shí)序性，即根據(jù)數(shù)據(jù)對象上關(guān)聯(lián)的時(shí)態(tài)信息，可以在數(shù)據(jù)全集上定義全序關(guān)系。在時(shí)態(tài)圖數(shù)據(jù)上，時(shí)序性可以表現(xiàn)為任意兩條邊或者兩個頂點(diǎn)在時(shí)態(tài)圖中的出現(xiàn)存在先后順序。

（2）演化性（Evolvability）：演化性表現(xiàn)為數(shù)據(jù)對象或數(shù)據(jù)對象間的關(guān)系發(fā)生變化，即數(shù)據(jù)對象或者數(shù)據(jù)對象間的關(guān)系隨時(shí)間發(fā)生變化［5］。在時(shí)態(tài)圖數(shù)據(jù)上，演化性可以表現(xiàn)為若干頂點(diǎn)的一個導(dǎo)出子圖隨時(shí)間變化為另一個導(dǎo)出子圖［6］。

（3）持久性（Durability）：持久性表現(xiàn)為數(shù)據(jù)對象或者數(shù)據(jù)對象間關(guān)系不隨時(shí)間發(fā)生變化，即數(shù)據(jù)對象或數(shù)據(jù)對象間的關(guān)系在多個時(shí)間不發(fā)生改變［7］。在時(shí)態(tài)圖數(shù)據(jù)上，持久性可以表現(xiàn)為一個子圖的結(jié)構(gòu)在多個時(shí)間不發(fā)生改變［8－9］。

根據(jù)時(shí)態(tài)數(shù)據(jù)的3 個性質(zhì)，下面對時(shí)態(tài)圖上圖模式匹配的相關(guān)工作進(jìn)行詳細(xì)闡述。

2.1 時(shí)態(tài)圖上基于時(shí)序性定義的圖模式匹配

在時(shí)序圖模式匹配的定義中，查詢模式圖中除了給定結(jié)構(gòu)約束以外，還在邊集上定義了先后順序，即查詢模式圖中的邊在時(shí)態(tài)數(shù)據(jù)圖中的匹配邊上的時(shí)間應(yīng)該滿足事先定義的順序［10］。針對時(shí)序圖模式匹配問題，已有的研究主要關(guān)注小的查詢模式圖［4，11－12］，即查詢模式圖中點(diǎn)的數(shù)目一般小于6。該類方法主要采用遍歷時(shí)態(tài)圖方式搜索滿足條件的匹配。除了要求匹配滿足以上定義，Kosyfaki 等人的研究還對匹配的邊上的權(quán)值和進(jìn)行限制［13］；Li 等人和Sun 等人針對任意大小的查詢模式圖進(jìn)行研究，首先根據(jù)定義在邊集上的偏序關(guān)系將一個查詢模式圖分解成若干個小的子查詢模式圖；其次，在輸入的圖流中查找這些子查詢模式圖的匹配，并將合格的匹配存儲到索引中；最后，連接這些子查詢模式圖的匹配得到查詢模式圖的匹配［14－15］。Kumar 等人和潘敏佳等人主要關(guān)注時(shí)態(tài)圖中一類特殊的結(jié)構(gòu)—時(shí)態(tài)環(huán)，即起始頂點(diǎn)和結(jié)束頂點(diǎn)相同的一條簡單的時(shí)態(tài)路徑，都采用兩階段深度優(yōu)先搜索的方法查找環(huán)結(jié)構(gòu)［16－17］。以上的研究都是基于時(shí)態(tài)圖的圖流模型定義的圖模式匹配。不同于之前采用的圖流模型，Xu 等人在區(qū)間模型下定義圖模式匹配問題，即在查詢模式圖和時(shí)態(tài)數(shù)據(jù)圖的邊上包含具體的時(shí)間區(qū)間［18］，該定義中要求對于任何查詢模式圖的匹配的邊關(guān)聯(lián)的時(shí)間區(qū)間同查詢模式圖中邊上的時(shí)間區(qū)間必須重疊。Ma 等人首次根據(jù)圖模擬和時(shí)態(tài)路徑定義時(shí)態(tài)圖上的圖模式匹配基于連接的方式枚舉匹配［19］。

2.2 時(shí)態(tài)圖上基于持久性定義的圖模式匹配

在持續(xù)圖模式匹配的定義中，查詢模式圖中除了給定結(jié)構(gòu)約束以外，還要求查詢模式圖的匹配在時(shí)態(tài)數(shù)據(jù)圖中的多個時(shí)間出現(xiàn)。該定義是基于時(shí)態(tài)圖的快照模型給出的，Semertzidis 等人使用位圖（bitmap）位圖構(gòu)建索引，索引的大小同時(shí)態(tài)圖中快照的個數(shù)成正比［8，20］。在搜索匹配的過程中，算法利用位圖之間的位運(yùn)算快速確定一個匹配持續(xù)的時(shí)間。

2.3 時(shí)態(tài)圖上基于演化性定義的圖模式匹配

在演化圖模式匹配的定義中，查詢模式圖中除了給定結(jié)構(gòu)約束以外，還要求查詢模式圖中的邊在時(shí)態(tài)數(shù)據(jù)圖中的匹配邊在不同時(shí)間表現(xiàn)為不同的狀態(tài)。該定義是基于時(shí)態(tài)圖的快照模型給出的。Zufle等人通過在查詢模式圖的邊上指定時(shí)間集合限制其匹配邊上的時(shí)間集合定義時(shí)態(tài)圖上的圖模式匹配問題，并利用字符串編碼子圖結(jié)構(gòu)加快匹配的搜索過程［21］。

3 現(xiàn)有工作的不足

通過以上綜述可以看出，在時(shí)態(tài)圖數(shù)據(jù)相關(guān)的眾多研究問題中，時(shí)態(tài)圖上的圖模式匹配研究則剛剛開始。表1 從定義、內(nèi)存消耗、算法效率等方面給出現(xiàn)有時(shí)態(tài)圖上圖模式匹配工作的不足。

表1 時(shí)態(tài)圖上圖模式匹配總結(jié)Tab.1 Summary of graph pattern matching on temporal graphs

具體的說明如下。

（1）時(shí)序圖模式匹配：現(xiàn)有時(shí)態(tài)圖上的時(shí)序圖模式匹配算法主要基于連接子查詢的匹配的方式實(shí)現(xiàn)，這種方式會產(chǎn)生大量的中間結(jié)果，從而占用大量的內(nèi)存。同時(shí)，驗(yàn)證連接后得到的結(jié)果，特別是那些不合格的匹配，會浪費(fèi)大量的時(shí)間?；谝陨显?qū)е卢F(xiàn)有方法在處理大規(guī)模時(shí)態(tài)圖或稠密的查詢模式圖時(shí)時(shí)間效率差。

（2）持續(xù)圖模式匹配：現(xiàn)有時(shí)態(tài)圖上的時(shí)序圖模式匹配算法主要利用位圖構(gòu)建索引降低驗(yàn)證匹配持續(xù)時(shí)間的代價(jià)。然而，索引占用的空間大小與時(shí)態(tài)圖中的快照數(shù)目成正比。當(dāng)時(shí)態(tài)圖的規(guī)模變大或者時(shí)態(tài)圖中快照數(shù)目較多時(shí)，索引將需要極大的存儲空間，進(jìn)而導(dǎo)致算法處理查詢的時(shí)間效率變差。

（3）演化圖模式匹配：在現(xiàn)有的工作中，沒有發(fā)現(xiàn)時(shí)態(tài)圖上演化圖模式匹配的定義，只發(fā)現(xiàn)一個已有的工作可以處理演化圖模式匹配問題，該工作需要對組成查詢模式圖的子圖進(jìn)行編碼并構(gòu)建索引，而索引的大小與時(shí)態(tài)圖中快照的數(shù)目以及子圖的匹配的數(shù)目成正比。當(dāng)時(shí)態(tài)圖的規(guī)模變大或者時(shí)態(tài)圖中快照數(shù)目較多時(shí)，索引將耗費(fèi)極大內(nèi)存空間，進(jìn)而導(dǎo)致算法處理查詢的時(shí)間效率變差。

4 結(jié)束語

本文根據(jù)時(shí)態(tài)圖的快照模型、邊流模型和區(qū)間模型以及時(shí)態(tài)圖數(shù)據(jù)的時(shí)序性、持續(xù)性和演化性對時(shí)態(tài)圖上圖模式匹配問題進(jìn)行了綜述。相比于靜態(tài)圖上圖模式匹配問題豐碩的研究成果，時(shí)態(tài)圖上圖模式匹配問題的研究則剛剛開始?，F(xiàn)有的時(shí)態(tài)圖上圖模式匹配研究在處理大規(guī)模時(shí)態(tài)圖或者稠密的查詢模式圖時(shí)表現(xiàn)較差，而一些圖模式匹配問題在時(shí)態(tài)圖上還沒有形式化定義。作為圖研究領(lǐng)域一個重要的研究方向，時(shí)態(tài)圖上圖模式匹配問題從深度到廣度、從理論到算法有待進(jìn)一步的深入研究。