時態圖上圖模式匹配研究綜述

李發明，鄒兆年，李建中

（哈爾濱工業大學 計算學部，哈爾濱 150001）

0 引言

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

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

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

（2）圖2 給出3 個科研人員以合作的模式在同一個會議上發表論文的情況，其中頂點表示研究人員，頂點之間的邊表示合作關系，圖下面的文字表示會議的名稱及合作的時間。了解不同科研人員之間的合作模式及持續時間將更好地發現研究團隊及研究方向。

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

鑒于時態信息對于圖數據查詢、分析的重要性，而現有關于圖模式匹配的研究又很少考慮時態信息，本文從時態圖的不同模型和時態信息的不同特性出發，對時態圖上的圖模式匹配問題進行了全面地綜述。

1 常見時態圖模型

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

1.1 快照模型

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

圖3 時態圖示例Fig.3 An Example of temporal graph

圖4 快照模型Fig.4 Snapshot model

1.2 邊流模型

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

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

1.3 區間模型

區間模型（interval model）不同于以上兩個模型表示離散時間的時態圖，區間模型關注的是邊上關聯時間區間的情況，即邊上的時態信息是連續的。時間區間表示兩點之間關系持續的時長，時間區間一般使用開始時間和終止時間表示。一個適用區間模型表示的時態圖，如圖6 所示。

圖6 區間模型Fig.6 Interval model

2 時態圖上圖模式匹配相關工作

相比于靜態圖上大量關于圖模式匹配的研究工作，時態圖上圖模式匹配的研究比較少。同靜態圖上的圖模式匹配相比較，時態圖上的圖模式匹配問題除了需要考慮查詢模式圖引入的結構約束，還需要考慮定義在查詢模式圖的頂點或邊上的時態約束。所以，時態圖上的圖模式匹配問題相較于靜態圖上的圖模式匹配問題更加復雜［4］。根據時態數據的特點，本文總結出時態數據的3 個重要性質，即時序性、持久性和演化性。基于這3 個性質，對時態圖上圖模式匹配相關工作進行綜述。

（1）時序性（Temporality）：由于數據對象本身關聯時態信息，時態數據天然滿足時序性，即根據數據對象上關聯的時態信息，可以在數據全集上定義全序關系。在時態圖數據上，時序性可以表現為任意兩條邊或者兩個頂點在時態圖中的出現存在先后順序。

（2）演化性（Evolvability）：演化性表現為數據對象或數據對象間的關系發生變化，即數據對象或者數據對象間的關系隨時間發生變化［5］。在時態圖數據上，演化性可以表現為若干頂點的一個導出子圖隨時間變化為另一個導出子圖［6］。

（3）持久性（Durability）：持久性表現為數據對象或者數據對象間關系不隨時間發生變化，即數據對象或數據對象間的關系在多個時間不發生改變［7］。在時態圖數據上，持久性可以表現為一個子圖的結構在多個時間不發生改變［8－9］。

根據時態數據的3 個性質，下面對時態圖上圖模式匹配的相關工作進行詳細闡述。

2.1 時態圖上基于時序性定義的圖模式匹配

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

2.2 時態圖上基于持久性定義的圖模式匹配

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

2.3 時態圖上基于演化性定義的圖模式匹配

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

3 現有工作的不足

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

表1 時態圖上圖模式匹配總結Tab.1 Summary of graph pattern matching on temporal graphs

具體的說明如下。

（1）時序圖模式匹配：現有時態圖上的時序圖模式匹配算法主要基于連接子查詢的匹配的方式實現，這種方式會產生大量的中間結果，從而占用大量的內存。同時，驗證連接后得到的結果，特別是那些不合格的匹配，會浪費大量的時間。基于以上原因導致現有方法在處理大規模時態圖或稠密的查詢模式圖時時間效率差。

（2）持續圖模式匹配：現有時態圖上的時序圖模式匹配算法主要利用位圖構建索引降低驗證匹配持續時間的代價。然而，索引占用的空間大小與時態圖中的快照數目成正比。當時態圖的規模變大或者時態圖中快照數目較多時，索引將需要極大的存儲空間，進而導致算法處理查詢的時間效率變差。

（3）演化圖模式匹配：在現有的工作中，沒有發現時態圖上演化圖模式匹配的定義，只發現一個已有的工作可以處理演化圖模式匹配問題，該工作需要對組成查詢模式圖的子圖進行編碼并構建索引，而索引的大小與時態圖中快照的數目以及子圖的匹配的數目成正比。當時態圖的規模變大或者時態圖中快照數目較多時，索引將耗費極大內存空間，進而導致算法處理查詢的時間效率變差。

4 結束語

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