李发明，邹兆年，李建中

（哈尔滨工业大学 计算学部，哈尔滨 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 个科研人员以合作的模式在同一个会议上发表论文的情况，其中顶点表示研究人员，顶点之间的边表示合作关系，图下面的文字表示会议的名称及合作的时间。……