在大数据时代, 随着信息科技与互联网的快速发展, 数据规模不断增长, 数据类型不断增多, 不同领域关注的实体对象之间的关系变得更加复杂.如何分析和挖掘大数据中蕴含的复杂关系, 成为当前的研究热点.图(graph)作为一种广泛使用的数据结构, 非常适合刻画这种存在内在关联性的数据, 图中的每个节点代表现实世界中的实体对象, 节点之间的边表示实体之间的关系.例如:在社交网络(新浪微博、微信等)中, 图可以用来刻画用户之间的交互关系; 在网络安全领域中, 图可以刻画主机间进行通信、用户的登录和IP地址的切换等交互关系; 在计算生物学领域中, 图则可以刻画蛋白质和酶之间发生的复杂交互、调控与代谢关系等.

然而在现实世界中, 描述实体对象图数据的结构和内容往往会随着时间的推移而发生变化.以社交网络为例, 根据Facebook网站2010年的年鉴报告, 仅2010一年期间, 用户从3.37亿人增加到5.85亿人, 平均每分钟都会有47 553对好友之间建立或者解除关系.2011年, Google+在上线后的两周时间增长了1 000万的用户^[1].这些数据表明, 现实世界中的实体对象和它们之间的关系无时无刻都可能经历着变化.因此, 如何应对大规模图数据中的动态变化, 吸引了研究学者的关注.

动态图模式匹配技术(dynamic graph pattern matching techniques)是分析动态图数据上高效查询的重要手段, 广泛应用于众多重要领域.动态图模式匹配技术是指在一个实时更新的图中找到与给定模式图相匹配的子图, 这里的匹配是指结构相同以及满足特定的语义关系等.例如:在社交网络中, 实体对象以及它们之间的关系可以转化为图的形式, 公司的HR可以通过动态图模式匹配技术在实时更新的社会群体中找到目标客户群体^[2]; 在网络安全领域中, 网络管理员可以通过动态图模式匹配技术对一个实时更新的动态网络进行监测, 看是否存在异常的网络攻击行为^[3]; 在计算生物学领域中, 蛋白质与酶之间的交互作用会使蛋白质的结构不断地发生变化, 通过动态图模式匹配技术对已知性质的蛋白质结构进行匹配, 来分析变化后的蛋白质的性质^[4].可见, 动态图匹配技术与人们的生活息息相关, 发挥着巨大作用.

目前, 研究学者已经对静态图匹配技术进行了大量的研究, 例如:Lee等人^[5]采用相同的编程环境以及通用框架, 对5种经典的静态图匹配算法(VF2, QuickSI, GraphQL, GADDI, SPath)进行了综合对比, 并分析解释了在特定图数据上算法性能提升的原因.于静等人^[4]从应用出发对图匹配进行分类, 包括结构匹配和语义匹配、精确匹配和近似匹配、静态图匹配和动态图匹配以及最优算法和近似算法.文章对动态图模式匹配的描述仅限于简单的介绍, 详细描述了静态图的精确图匹配技术, 并对匹配算法的性能进行评价.但是传统的静态图匹配模型无法描述图数据随时间发生变化的情况, 因而并不适用于解决动态图数据上的模式匹配问题.如何对动态图数据进行有效且高效的匹配分析面临诸多挑战.

1) 数据更新频繁.例如网络社交网络、数据中心网络和金融网络等网络系统对应的图数据每时每刻都经历着更新, 传统的静态图匹配技术需要在每一次更新时都对更新后的图数据建立索引并进行匹配, 耗时耗力, 不适用于解决动态图匹配问题;

2) 数据规模大.由于不断被更新, 动态图的规模相对于静态图更加庞大, 增加了图匹配问题的难度;

3) 实时分析要求高.在许多实时分析应用中, 每当动态图被更新时, 需要及时给出更新后的匹配结果, 否则会使匹配结果的应用价值降低或丧失.例如, 网络安全领域需要对可疑的数据传输模式进行实时匹配监控, 若匹配分析结果滞后, 可能会导致网络瘫痪.

针对上述问题, 现有动态图数据匹配相关研究工作主要从以下几个方面展开.

1) 针对动态图数据频繁更新的特性, 研究增量处理技术, 仅对动态图数据更新的部分进行分析和匹配;

2) 针对动态图数据规模大的特性, 研究如何利用分布式并行图处理框架, 例如谷歌的Pregel^[6]、微软的Trinity^[7]、Apache的Giraph^[8]、Yan等人的Blogel^[9]以及Fan等人的最新研究GRAPE^[10]等, 来加速动态图的匹配计算;

3) 针对动态图分析实时性要求高的特性, 除了综合运用增量处理技术和分布式并行图处理框架降低匹配处理时延之外, 还有学者研究图匹配的近似计算技术, 在求解时延和匹配结果假阳性错误率之间做权衡.已有一些关于图模式匹配的综述论文^{[4, 5]}, 但是文献[4]虽然提到动态图匹配, 但仅限于对动态图模式匹配的简单介绍, 并没有针对动态图模式匹配技术展开详细讨论, 也没有对相关研究进展进行介绍; 文献[5]则完全是针对静态图匹配算法进行讨论.本文从关键技术、代表性算法和性能评价方面对动态图模式匹配技术的最新研究进展进行综述和讨论.目前, 动态图模式匹配还处于起步阶段, 但是已经引起了广泛的关注.

在实际应用中, 不同的应用场景会产生不同的动态图匹配问题, 本文第1节详细给出动态图匹配的相关定义, 并对动态图匹配问题进行了分类介绍.第2节和第3节按照动态图的两种不同更新方式, 分别对不同类型的动态图匹配问题进行问题描述和研究现状分析.第4节对不同类型匹配算法的性能进行比较分析, 并给出结论.第5节介绍动态图匹配技术的应用现状.第6节对动态图匹配技术的未来发展趋势进行展望.

1 动态图匹配问题的定义和分类 1.1 基本动态图匹配问题

通常用三元组(V, E, L)对图数据进行形式化描述, 其中, V表示图中的节点集; E表示图中边的集合, 图中的边和节点可以带有属性信息; L表示属性映射函数, 将节点或边映射到一个或者一组属性上.图中的任意一条边e∈E可由节点对(v_i, v_j)表示, 其中, v_i, v_j∈V.本文用符号G, P, u, v分别表示数据图、模式图(或查询图)、单个数据图节点和单个模式图节点.目前, 业界所使用的数据图G的类型可以分为两种:第1种数据图是超大图, 例如社交网络就是一张超大图; 另一种数据图是由大量的小图组成, 例如AIDS Antiviral数据集^[11]由表示化学物质原子结构的大量小图构成.据调研, 目前的动态图匹配问题主要针对数据图是超大图的情况, 因而本文集中讨论数据图为超大图情况下的动态图匹配问题.

动态图又称图流(graph streams), 是指会随时间发生变化的图.动态图的更新形式可分为以下两类:(1)图结构更新, 随着时间推移, 图数据中的节点和边会被插入和删除, 从而导致图数据的结构发生变化; (2)图内容更新, 随着时间推移, 图数据中的节点和边所关联的数据对象的内容或属性会发生改变, 从而导致图数据的内容发生变化.下面给出这两种更新条件下动态图的匹配定义, 由于目前的研究工作主要集中于数据图的结构更新, 因此仅在图结构更新中给出动态图的定义.

(1) 图结构更新

定义1(动态图).已知初始数据图G, 引发数据图更新的操作可以用三元组 < op, u_i, u_j>表示.其中, op={I, D}表示操作类型, op=I时表示增加边操作, op=D时表示删除边操作; u_i和u_j表示数据图中与操作op相关的两个图节点.向数据图中增加一个节点, 可以用与该节点相关的一系列增加边的操作来表示.与此类似, 向数据图中删除一个节点, 可以用跟该节点相关的一系列删除边的操作来表示.若用更新操作集合GC_t={ < op₁, u₁, u₂>, …, < op_k, u_k, u_k+1>}(k≥1)表示数据图G在t时刻的所有更新操作, 用GC:G→G'表示数据图G基于更新操作集合GC更新后得到新数据图G'的过程, 则时间域[0, T]上的动态图$G_{D}^{[0,T]}$ 是一个数据图序列, 定义为

$ \begin{align} &G_{D}^{[0, T]}=\{{{G}_{0}}, {{G}_{1}}, {{G}_{2}}, ..., {{G}_{T}}\}, \\ &{{G}_{0}}=G, \text{ }G{{C}_{0}}=\varnothing, \text{ }G{{C}_{t}}:{{G}_{t-1}}\to {{G}_{t}}(1\leqslant t\leqslant T). \\ \end{align} $

定义2(动态图同构匹配).已知一个模式图P(V_p, E_p, L_p)和一个动态图$G_{D}^{[0, T]}=\{{{G}_{0}}, {{G}_{1}}, {{G}_{2}}, ..., {{G}_{T}}\}$ , 动态图同构匹配问题是指模式图P和动态图$G_{D}^{[0, T]}$ 在t时刻的数据图G_t的数据子图G_sub-t=(V_sub-t, E_sub-t, L_sub-t)(G_sub-t⊆G_t)之间存在一个双射函数f, 且f满足:

●  ∀v∈V_p, L_p(v)=L_sub-t(f(v));

●  ∀(u_i, u_j)∈E_p, (f(v_i), f(v_j))∈E_sub-t, 且L_p(u_i, u_j)=L_sub-t(f(v_i), f(v_j)),

其中, f(v)表示数据图中与模式图节点v满足双射关系的节点, 即, 数据图中与节点v相匹配的节点.

图 1中的虚线框展示了初始数据图G在进行GC₁={ < I, u₅, u₈>}更新操作变成G₁之后, 产生的与模式图P相匹配的子图M=[(v₁, u₃), (v₂, u₆), (v₃, u₅), (v₄, u₈)].

子图同构是NP完全问题, 基于子图同构的概念完成模式图与数据图之间的匹配, 对于社交网络等对匹配精确度要求不严格的应用而言过于苛刻, 制约了匹配效率.因而, 不少研究工作定义了近似图模式匹配方案, 并按照实际应用对匹配近似程度的不同要求由弱到强分为受限模拟(bounded simulation)匹配、图模拟(graph simulation)匹配、双向模拟(dual simulation)匹配、强模拟(strong simulation)匹配和严格模拟(strict simulation)匹配, 以上统称为模拟匹配.受限模拟匹配将数据图和模式图边与边之间的严格匹配放松至数据图的一条路径和模式图的一条边进行匹配, 数据图节点与模式图节点的匹配条件只要满足节点属性值相同且数据图节点的一个子孙节点与模式图节点的后继节点的属性值相同即可; 图模拟匹配与受限模拟相比, 要求数据图中的匹配节点保持与模式图中对应节点的后继关系, 即, 数据图节点存在后继节点与模式图节点的后继节点的属性值相同; 双向模拟匹配在图模拟匹配的基础上, 还要求数据图中的匹配节点保持与模式图中对应节点的前驱关系; 强模拟匹配在双向模拟匹配的基础上, 进一步要求匹配节点所在子图(子图中可能包含非匹配点)的半径不大于模式图的直径; 严格模拟匹配比强模拟匹配要求更严格, 要求完全由匹配节点构成的子图的半径不大于模式图的直径.模拟匹配类是一种可以容忍结果中存在一定噪声和错误的匹配算法, 在社交网络分析和Web网络分析等应用中发挥着重要作用.模拟匹配的匹配结果与模式图之间存在一定的差别, 但通常可以满足实际应用的需求, 因此也通常被看做是正确的匹配结果.

下面以图模拟匹配为例, 对动态图的图模拟匹配进行定义.

定义3(动态图的图模拟匹配).已知一个模式图P(V_p, E_p, L_p)和一个动态图$G_{D}^{[0, T]}=\{{{G}_{0}}, {{G}_{1}}, {{G}_{2}}, ..., {{G}_{T}}\}$ , 动态图的图模拟匹配是指模式图P和t时刻数据图G_t(V_t, E_t, L_t)之间存在二元关系S⊆V_P×V_t, 其中, V_P和V_t分别表示模式图节点和数据图节点的集合, 且S满足:

● 节点约束:if M=[(v₂, u₂), (v₃, u₃), (v₄, u₄)] then L_p(v)=L_t(u);

● 边约束:∀(v, v')∈E_p,$ \exists$(u, u')∈E_t:(u', v')∈S;

● 图约束:∀v∈V_p, $\exists$u∈V_t:(u, v)∈S.

如图 2所示:初始数据图G中, 节点u₂的属性与模式图P中的节点v₂的属性相同; 同时, u₂的后继节点u₄的属性与v₂的后继节点v₄属性相同, 因此, u₂与v₂匹配.同理, 由于模式图P中的节点v₃的后继节点为空, 则v₃与u₃相匹配.而u₄的后继节点中不存在属性与v₄的后继节点v₃相同的节点, 因此u₄与v₄不匹配.在t=1时刻, 初始数据图G在进行GC₂={ < I, u₄, u₆>}更新操作之后, u₄与v₄满足了匹配条件, 按照图模拟匹配的定义产生的与模式图匹配的子图M₁=[(v₂, u₂), (v₃, u₃), (v₄, u₄)]和M₂=[(v₂, u₂), (v₃, u₆), (v₄, u₄)].可以发现, 其中M₁与模式图P的结构不同, 但仍然认为是与模式图P相匹配的结果.

(2) 图内容更新

图内容被更新的情况指节点或边的属性值或者对图中某一特定对象的评价方式会随着时间发生变化.如图 3所示:在t=1时刻, 初始数据图G中, 节点u₃和u₆的属性发生变化, 此时, 虚线框展示了数据图更新后得到的与模式图相匹配的子图M=[(v₁, u₃), (v₂, u₆), (v₃, u₅), (v₄, u₈)].

1.2 动态图匹配问题分类

本节从应用出发, 根据图数据的不同特点对动态图匹配问题进行分类, 并分别介绍每类问题的代表性算法.这里所采用的分类方法并不相互独立, 因此, 在每类中介绍的匹配算法通常也运用了其他类型的匹配.

(1) 面向结构变化的匹配和面向内容变化的匹配

动态图匹配问题按图中的拓扑结构关系是否发生变化分为面向结构变化的匹配和面向内容变化的匹配.目前, 动态图匹配的很多研究工作都围绕着数据图中的节点或边随着时间推移发生动态增删, 导致图的拓扑结构发生变化这种情况展开讨论, 称为面向结构变化的动态图匹配问题, 主要应用于网络异常攻击检测和社交网络关系检测等场景.面向结构变化的动态图匹配问题最早在2009年由Wang和Chen提出, 他们构建邻节点树(NNT)^[12]并依此对匹配候选集进行过滤, 从而有效减少假阳性匹配结果的产生.这之后的代表性算法包括IncIsoMatch^[13]、SJ-Tree^[14]、graph simulation(DDST^[15]、IncBMatch^[13])等, 对子图匹配的执行效率进一步提升.随着数据中心的出现, 许多研究工作将数据中心的网络拓扑结构抽象为数据图进行相关分析, 图中的每个节点代表一台服务器, 节点之间的边代表服务器间的链路.在这种情况下, 图数据的拓扑结构不会频繁发生改变, 而图数据中节点的属性值(例如服务器的空闲内存量)和边的属性值(例如链路的有效带宽)会随时间频繁发生变化, 称为面向内容变化的动态图匹配问题.为了有效应对数据图中节点属性值或边属性值的频繁变化, Zhong等人提出了Gradin算法^[16], 将数据图的频繁子图中的每个节点的属性值作为一个数据维度, 从而使一个包含n个节点的频繁子图可以表征成n维网格索引中的一个n维坐标向量, 用这种方式索引数据图的所有频繁子图.网格索引适合索引动态变化的数据, 因此当频繁子图中的节点属性值频繁发生改变时, 也能保证索引的维护性能.基于n维网格索引, 可以快速对节点标签值不满足匹配要求的中间结果进行过滤, 有效提高了数据图和模式图的匹配效率, Gradin算法也可以直接运用于数据图中边的属性值频繁更新的情况.

(2) 同构匹配和模拟匹配

动态图匹配问题是按照基于双射函数判定还是基于二元关系判定, 可以相应地被称为同构匹配(isomorphism matching)和模拟匹配(simulation matching).如果模式图和数据子图之间存在一个双射函数, 则称为同构匹配, 这种匹配需要保证节点周围有相同的连通结构, 要求与模式图完全一致, 主要用于蛋白质分子的相互作用^[4]、网络异常行为监测^[3]等对结构要求比较严格的图数据分析应用.如果模式图和数据图之间存在二元关系, 则称为模拟匹配.模拟匹配属于近似匹配, 通常先根据数据图节点的标签为模式图中的每一个节点产生匹配候选集, 再根据模式图中对节点的前驱和后继的不同近似匹配程度要求过滤掉不匹配的节点.代表性的算法包括DDST^[15]和IncBMatch^[13]等.其中, IncBMatch算法得到的结果满足即使模式图的结构与数据子图不一样, 但是仍然符合匹配条件, 效率更高, 匹配过程能在多项式时间内完成.除了有效提升匹配效率之外, 与同构匹配相比, 模拟匹配的灵活性更高, 能够识别更多有用的匹配结果.主要用于路网中引发交通事故监测^[15]、人群和各类团体(例如毒品交易关系网络)之间的相互关系监测^[13]等更加侧重挖掘节点之间的相互关系的图数据分析应用.

(3) 精确算法和近似算法

按照是否能够获得准确结果, 动态图匹配算法分为精确算法和近似算法.精确算法能够保证匹配的结果完全精确, 主要应用在网络异常检测和生物数据分析等这类对匹配的结果准确率有严格要求的领域.例如, 同构匹配问题的精确算法可以保证计算结果与模式图完全同构, 模拟匹配问题的精确算法可以获得与模式图满足二元关系的一系列结果.使用精确算法对数据图和模式图进行匹配的代表性算法包括IncIsoMatch算法、SJ-Tree算法和Gradin算法等.另一方面, 许多实时性要求高的应用中要求快速返回所有匹配结果, 不适合使用计算复杂度高的精确匹配算法, 同时, 考虑到该类应用可容忍匹配的结果中除了正确的结果之外还可包含一部分错误的结果(即假阳性结果), 近似图匹配算法应运而生.近似算法不同于模拟匹配, 近似算法通常基于概率统计等数学模型, 计算结果中除了正确的结果之外, 还包含一部分错误的结果, 可以通过参数调整将错误比率控制在一定范围内.以NNT^[12]、Replication mechanism^[17]、SSD^[18]为代表的研究工作提出了近似图匹配算法, 以牺牲匹配精度换取匹配效率的方式, 将图匹配问题的转换为较易计算的问题, 例如将图匹配问题转化为向量空间的关系检测问题, 可将图匹配的时间复杂度降低至多项式级别.

精确算法和近似算法是决定匹配结果准确率的两种算法, 而同构匹配和模拟匹配则是不同类型的图匹配模型, 概念上有明显区别.

(4) 集中式匹配和分布式匹配

按照是否部署在分布式的平台上, 动态图匹配问题分为集中式匹配和分布式匹配.集中式匹配在单台计算机上运行, 主要处理规模相对较小的图数据.目前, 动态图集中式匹配主要采用基于连接(join)的匹配方法或者基于探索(exploration)^[19]的匹配方法实现.基于连接的匹配方法采用将查询图进行分解的策略, 对每一个查询分片进行匹配后将得到的结果进行连接, 一般需要构建索引.而基于探索的方法是从数据图的一个节点出发, 根据模式图的结构关系对数据图进行探索, 一般不需要构建索引.分布式动态图匹配技术主要依托于分布式并行图处理框架实现, 用来处理规模庞大且计算复杂度高的动态图数据.目前, 主流的分布式并行图计算系统的类型包括3种, 分别是中心节点模型(包括Pregel^[6]、Trinity^[7]、Giraph^[8]、GraphLab^[20]等)、中心块模型(Blogel^{[9, 21]})以及自动并行化模型(GRAPE^[10]).其中, 中心节点模型和中心块模型需要根据模型的特点来改造算法, 而Fan等人研究的自动并行化模型则不需要考虑模型的特点, 用户只需要提供局部匹配、增量计算、结果拼接这3种连续的算法即可, 不用对算法的逻辑进行修改.这3种分布式并行图计算系统都遵循BSP^[22]模型.表 1展示了不同类型分布式并行图计算系统在最短路径查询方面的性能, 采用美国路网作为数据集, 可以发现, GRAPE系统的性能明显优于其他类型系统.由于要实现对匹配结果进行增量更新的需求, 因此分布式匹配一般采用基于探索的方法.分布式并行图计算框架包含多个超级步(super-step), 每一步只发送当前状态的消息而忽略前次的状态, 因此会产生不一致的结果, 文献[23]解释了这种不一致结果产生的原因, 并提出Stp(Q)算法来解决因不一致性而产生的结果准确率问题.

综上, 算法所针对的应用背景不同, 所解决的图匹配问题的类型也就不同.表 2总结了迄今为止具有代表性的动态图匹配算法以及所解决的图匹配问题的类型.以下将按照面向结构变化和面向内容变化这种分类方式对动态图匹配技术展开细致介绍, 将每一类图匹配技术的主要问题、代表性算法和研究现状进行分析对比.由于目前的大部分研究工作都围绕着面向结构变化的动态图匹配问题展开, 本文将重点介绍面向结构变化的图匹配技术的最新研究进展.

2 面向结构变化的动态图匹配技术

面向结构变化的动态图模式匹配技术在目前应用最为广泛, 其所处理的图数据结构会随着时间发生变化.从算法设计的角度来说, 可以将其分为基于快照处理的匹配技术和基于增量处理的匹配技术.基于快照处理的匹配技术就是将每一个时间戳上更新的数据图看成一个静态图来进行匹配处理, 通常适用于增加边数目比较多的情形, 该情形下可以一次性完成所有增加边操作, 并基于更新后的数据图快照进行匹配计算.邻节点树(NNT)算法是最早提出的基于快照处理的动态图匹配算法, 之后的代表性算法包括DeltaGraph^[24]和DDST^[15]等.第2.1节将重点介绍NNT算法, 并简要介绍其他相关算法.

基于增量处理的匹配技术仅对数据图中更新的部分进行分析和匹配, 避免对整体数据图进行重新匹配所带来的重复计算.Fan等人^[13]最早将增量处理技术应用到动态图匹配计算当中, 提出了IncSimMatch算法和IncBMatch算法, 并与各自对应的批处理(快照)算法, 即Match_s和Match_bs, 进行对比.实验结果表明:当增加边或者删除操作的数目不超过初始数据图边总数的某一百分比时, 基于增量处理的匹配技术的执行效率更高.之后, 增量计算的思路广泛应用于动态图模式匹配算法的设计中, 其他代表性的基于增量处理的动态图匹配算法包括SJ-Tree^[14]、Lazy-Search^[25]和Distributed-IncSimMatch^[26].这些算法是在Fan等人提出的增量图匹配技术的基础上加入其他的查询优化策略对匹配过程进行改进, 其中以SJ-Tree算法最具代表性.动态图增量匹配算法在子图匹配的过程中可以采用基于连接的匹配技术、基于探索的匹配技术或基于图模拟匹配技术实现, 其中, 基于连接的匹配技术由于会产生大量的中间结果, 因此不适用与分布式并行图处理框架.第2.2节将分别介绍这3类算法.图 4总结了面向结构变化的动态图匹配技术的分类与相应代表性算法.

2.1 基于快照的匹配技术

动态图匹配问题实际上也是大规模的静态图查找问题, 可以将每一时刻更新后的数据图看成静态图, 然后对这些连续的静态图进行模式匹配.这种基于快照的匹配技术包括两部分:更新操作和匹配操作.下面分别从这两部分进行介绍.

(1) 数据图更新

文献[12]最早提出了关于动态图的模式匹配问题, 将不断更新的图数据看成图流的形式, 并提出了基于快照的动态图模式匹配算法——NNT算法, 在性能方面取得了较好的结果.NNT算法采用为数据图G和模式图P中的每个节点u都构造一棵邻节点树, 记为NNT(u).以数据图G举例, 给定——深度值L, NNT(u)(u∈G)存储了数据图G中以u为根节点且长度不超过L的所有路径.如图 5(a)所示, T₁~T₄分别为数据图G中的节点1~节点4对应的深度值L=2的邻节点树, 其中, 大写字母表示节点的属性.其中, T₁和T₂内容相同.图 5(b)则为这些邻节点树构建倒排索引, 用来查找数据图中的节点和边对应的各个邻节点树中的节点和边, 其中, *表示倒排索引中的省略部分.

面向结构变化的动态图更新操作包括删除边操作和增加边操作, 下面以基于邻节点树构建的倒排索引为例, 分别介绍执行这两种操作时如何对索引进行更新.

● 删除边操作:如图 5所示, 假设在t时刻删除数据图G中的边(1, 3), 则同时需要从倒排索引中删除该边在所有邻节点树中对应的边, 且如果对应的边存在子边, 则这些子边也要被删除.此例中, 边(1, 3)在T₁ & T₂中对应的边(a, c)以及(a, c)的子边(c, e)和(c, f), 以及和这些边相关的节点都要从倒排索引中删除;

● 增加边操作:假设在t时刻向图 5所示的数据图G中增加一条边(1, 4), 首先, 根据倒排索引找到节点1对应的每棵邻节点树中的节点.然后, 从每棵树中与节点1相对应的节点开始, 将数据图G中新产生的L=2的路径加入到邻节点树中.如T₁中从节点a出发增加路径(a→g→h), 其中, 节点g和节点h的属性分别为C和B.在T₂中, 从节点b增加路径(b→g), 其中, g的属性为C.直到所有与节点1对应的节点都完成即可.最后, 将新加的节点和边添加到倒排索引中.同样的, 对节点4也需进行相同的操作更新索引结构.

NNT算法将模式图与数据图每一时刻的快照图进行匹配, 并不能体现图随时间的演变过程.文献[27]首次提出一种针对大规模动态图的索引结构BR-Index, 将数据图划分为一系列重叠的索引域, 每一个索引域包含若干个相互独立的核心域.提取每个索引域的最大特征, 然后构建一个特征点阵用来维护和查找这些特征.BR-Index还维护了一个基于哈希原理实现的节点查找表, 用来存储每一个索引域中的数据图节点以及该节点处于索引域中的哪一个核心域.当数据图更新时, 可以基于该查找表快速定位更新部分.文献[15]提出了基于时间窗口的子图匹配算法DDST, 窗口内包含所有满足时间约束的图快照信息.而且数据图中每一条边上都有一个时间常量记录了该边的生成时间.这样就能判断一个数据子图是否在给定的时间窗口内存在(或称“合法”), 只有窗口内合法的数据子图满足匹配条件后才会成为匹配的结果.与NNT算法相比, 使用时间窗口的好处是可以反映出图随时间的一个演变过程, 即:只有时间窗口内的图快照满足匹配条件后才是“合法”的结果, 更加符合实际的应用.文献[24]提出了一种树形索引结构DeltaGraph, 该索引结构类似二叉树, 每个叶子节点都存储按时间顺序排列的一个快照图信息, 内部节点存储的信息则是由其孩子节点存储的信息通过取交函数运算得到, 其中, 根节点表示源节点, 叶子节点表示目标节点, 每条边都保存有从源节点到目标节点的信息.当数据图执行增加或删除边操作时, 这种索引结构只需要将该时刻的数据图快照添加到叶子节点即可.

(2) 子图匹配

在匹配的过程中, 如果采用子图同构的方式进行匹配计算, 则时间复杂度很高.例如, NNT算法若采用子图同构的方法进行匹配计算, 其时间复杂度高达O(n₁xn₂(|T₁|^1.5/log|T₁|)|T₂|)^[27].其中, n₁表示模式图节点的数目, n₂表示每一时刻数据图中的节点数目, |T₁|和|T₂|分别表示模式图和数据图所对应的邻节点树的最大个数.可见:若采用子图同构的方式进行匹配计算, NNT算法的执行效率会受到严重制约, 不满足动态图匹配的实时性的需求, 因此, 若应用允许要尽可能避免采用子图同构的方式进行匹配计算.

NNT算法实际上采用的是近似算法, 通过比较两个节点的邻节点树中的路径进行子图匹配计算:如果模式图每一个节点构建的邻节点树中的所有路径在数据子图中与其对应的节点构建的邻节点树中都存在, 则模式图与该数据子图相匹配.这种子图匹配计算方法的时间复杂度为O(n₁n₂r^l), 其中, r表示数据图节点最大的度, l表示选取的深度值.由于每次匹配都需要对所有可能的节点对进行匹配计算, 开销仍然很大.因此, 算法还提出了一种编码方式, 将邻节点树转化成数字向量, 并统计所有邻节点树中不同路径的数目, 以达到进一步降低计算开销的目的.如图 5(a)所示, 邻节点树T₁~T₄共存在8种不同的路径, 因而每个节点的邻节点树都可以用8维向量表示, 其中, 第i维记录了该邻节点树中存在第i类路径的数目.这样就可以将模式图和数据子图转化成多维数字向量的形式, 如果模式图中每一维度的值都小于等于数据子图中对应维度的值, 则满足匹配条件.进行

以上优化后的匹配时间复杂度为$O(\bar{L}{{n}_{1}}{{n}_{2}}), $ 其中, L表示数字向量中非零项的数目.

BR-Index算法首先提取模式图的最大特征集合, 在子图匹配的过程中, 根据提取的模式图最大特征集合找到数据图中包含这些特征集合的索引域; 然后, 在对应的索引域中找到最大特征的候选集; 最后将候选集进行组合, 即可得到模式图的匹配结果.DDST算法采用模拟匹配的方式来完成子图匹配计算, 因为模拟匹配比同构匹配更灵活, 可以识别更多有用的结果.由于传统的图模拟匹配技术只需要数据图中的匹配节点保持与模式图中对应节点的后继关系, 放宽了同构匹配的约束条件, 因此很难获取与模式图一致的拓扑结构.DDST算法在图模拟匹配的基础上加入了两个约束条件Dual simulation和Locality^[28], 即为模式图构建一个签名, 签名包括边和节点的标签以及所有节点的入度和出度信息, 若数据图子图的签名与模式图一致, 则继续采用二元模拟的匹配技术进行匹配计算.同时提出模式图中的边在时间域上的偏序关系, 数据子图中各条边的时间属性只有满足时间域上既定的先后顺序才满足匹配条件.树形索引DeltaGraph则采用分布式并行图处理框架完成子图匹配计算, 即:将快照信息存储在内存中, 给定一个模式图, 可以直接从根节点开始根据边上的构建信息找到与该模式图匹配的快照图.

综上, 采用子图同构的方式进行子图匹配计算效率低、耗时高, 因此可以采用近似匹配算法或者模拟匹配技术来设计基于快照的匹配技术.近似算法用少量假阳性的结果降低匹配时间, 模拟匹配则直接采用二元关系匹配来代替子图同构匹配.模拟匹配主要适用于更加侧重于挖掘节点之间关系的应用, 用户需针对不同的应用背景来选择合适的子图匹配算法.

2.2 基于增量处理的匹配技术

动态图模式匹配属于NP完全问题.在匹配的过程中, 如果按照基于快照的重复查找策略, 需要在每一次数据图更新后都对完整的数据图进行匹配, 当更新操作数量较少时, 造成大量冗余计算, 无法满足动态图高效分析处理的潜在需求.因此在设计算法的时候可以采用增量处理技术, 通过数据图局部匹配技术或者利用之前匹配的结果来减少冗余的匹配计算.

文献[13, 29]介绍了增量图计算的思想, 增量图计算是指给定一个数据图G、模式图P、初始的模式图匹配结果P(G)、数据图的更新ΔG, 计算数据图更新后新增加的匹配结果集ΔO, 即P(G⊕ΔG)=P(G)⊕ΔO.其中, ⊕表示操作符, 用来将变化的内容加入到原始数据当中.文献[13]提出增量图模拟匹配(IncSimMatch)算法, 在局部匹配的基础上, 充分利用之前的匹配结果, 并提出辅助的数据结构match(v)和candt(v)加速匹配计算.其中:v表示模式图节点, match(v)表示数据图中与节点v匹配的节点; candt(v)表示数据图中与节点v属性相同但是不满足其他匹配条件的节点.与基于快照处理的匹配技术相同, 数据图更新时对匹配结果的影响可基于增加边和删除边这两种情况分别展开讨论.

● 删除边操作:IncSimMatch算法中, 当从数据图中删除边时不会导致匹配结果增加.只有当删除的边, 例如删除(u_i, u_j), 满足u_i∈match(·), u_j∈match(·)才会导致匹配结果的减少, 即, 将之前的匹配结果集中所有包含该边的匹配结果移除即可;

● 增加边操作:IncSimMatch算法中, 当从数据图中增加边时不会导致匹配结果的减少.只有当增加的边, 例如增加(u_i, u_j), 满足u_i∈candt(·), u_j∈match(·)或者u_i∈candt(·), u_j∈candt(·)时才会产生新的匹配结果.此时, 可以通过局部匹配的方法来找出所有匹配结果.

文献[29]介绍了4种图查询问题, 分别是RPQ(regular path queries)、SCC(strongly connected components)、KWS(keyword search)和ISO(subgraph isomorphism), 并提出了针对这4种图查询问题的增量计算方法.其中, 前3类图查询问题与本文的主旨子图模式匹配不符, 因此不做详细讨论.与本文相关的是第4类ISO子图同构查询.文献[29]针对ISO查询问题提出了增量计算方法IncISO, 当数据图更新时, 只需对更新边周围模式图直径范围内的数据图节点进行重新匹配即可, 避免对整个数据图的重复计算.

朴素增量匹配是一种基于增量图计算的思想, 通过局部匹配的方式, 检查数据图中每一条新增加的边是否与模式图中的边相匹配, 即, 检查模式图中是否有与数据图新增加边的属性相同的边, 而且数据图中新增加的边的端点与模式图中相对应边的端点的属性也是相同的.满足上述条件后, 检查新得到的局部匹配结果图与已经存在的局部匹配结果图之间能否组合成一个更大的匹配结果图.如图 6所示, 在t₀时刻, 找到所有模式图中与数据图中边(u₁, u₂)相匹配的边.同理, 在t₁时刻找到所有模式图中与数据图中边(u₂, u₃)和(u₂, u₄)相匹配的边.t₁时刻的匹配结果能够与t₀时刻的匹配结果结合产生更大的匹配结果M₁和M₂, 且M₁和M₂均是与模式图P相匹配的结果.

在子图匹配过程中, 动态图模式匹配与静态图模式匹配相似, 因此可根据静态图模式匹配的分类方法, 按是否需要将模式图分解, 可分为基于连接的匹配技术和基于探索的匹配技术.除此之外, 在动态图子图匹配中, 运用基于图模拟的匹配技术也得到了较好的实验结果.下面分别从这3个方面对动态图模式匹配技术进行深入介绍.

2.2.1 基于连接的动态图数据匹配技术

研究发现:当模式图规模较大时, 如果每次数据图更新时都对整个模式图进行查找会浪费大量时间, 因此可以将模式图进行分解.如图 7所示:将模式图P分解成一系列更小的子模式图, 表示为p₁, …, p_k.接着, 分别对这些子模式图进行匹配, 将匹配的结果进行连接整合即可得到整个模式图匹配的结果.

在静态图模式匹配中, 基于连接的方法应用比较广泛, 代表性算法包括gIndex算法^[30]和GraphGrep算法^[31]等.基于连接的方法通过挖掘数据图中具有识别能力的特征, 例如路径^{[31, 32]}、树^{[33, 34]}和子图^{[30, 35, 36]}等, 一方面根据这些特征在数据图上构建索引; 另一方面, 利用这些特征分解模式图.但是, 在将该方法直接应用到动态图匹配过程中, 则会产生一系列问题.例如, gIndex算法^[30]需要在每一时刻挖掘数据图子图的特征, 这显然不适用于实时分析要求高的动态图匹配处理.GraphGrep算法^[31]可以满足实时性需求, 但是其仅仅使用路径这种识别度不高的特征进行核实过滤, 可能会产生大量错误的匹配结果.可见:将基于连接的方法运用于动态图匹配分析时, 如何实现高效数据图特征提取, 是核心挑战问题.

在社交网络应用中构建的数据图往往是多关系图, 即:实体之间边的属性不仅表示连通性, 还表示实体之间的相互关系.因此在这类应用中, 可以用数据图实体之间的相互关系(即边的类型)作为数据图特征对模式图进行分解.文献[14]提出了一种树形索引结构SJ-Tree.SJ-Tree树是一棵二叉树, 它的根节点表示模式图, 内部节点表示模式图的子图, 内部节点的孩子节点由该节点中的子图进一步分解得到, 叶子节点则表示将模式图最终分解后得到的分解结果.如图 8所示, SJ-Tree树中的每一个节点都存储了它的兄弟节点和父节点的信息并维护了一个哈希表存放该节点的匹配结果.当数据图被更新时, 在SJ-Tree树上迭代搜索所有叶子节点以获取包含新增加边的匹配结果, 并将匹配结果存放在SJ-Tree树相应节点的哈希表中.同时, 检查该叶子节点的兄弟节点所维护的哈希表中存储的兄弟节点的匹配结果能否与其连接整合成更大的匹配结果.如果存在更大的匹配结果, 则将该结果存放至父节点的哈希表中, 直到产生与整个模式图相匹配的结果.例如图 8中, SJ-Tree叶子节点的候选集{(“George”, “friend”, “Join”)}和{(“Join”, “like”, “Santana”)}相连接整合, 可以得到更大的匹配结果.

如图 8所示:由于模式图包含friend关系, 在子图匹配的过程中, 如果数据图中friend关系频繁出现, 则需要追踪所有的与friend相匹配的边, 这无疑将花费大量时间.因此, 可以选择将模式图的分解结果friend边推迟匹配, 优先匹配在数据图中出现相对不频繁的模式图的分解结果.基于此思想, 文献[37]提出一种基于选择度的Lazy-search算法.给定初始的数据图G, 则图G中的k边子图g的选择度为g在数据图G中出现的次数与G中所有k边子图数的比值.其中, g被称为选择度基元.为了限制子图同构的计算代价, 同时也为了使选择度基元在数据图变化的过程中仍然有效, 一般选择单边或者双边子图作为选择度基元.Lazy-search算法用离线方式计算出数据图包含的所有类型的单边或双边子图的选择度, 并将这些选择度基元按其选择度值递增排序, 排在前面的选择度基元的选择度值越低, 识别能力则越高.后续将查询图按照这些选择度基元的先后顺序进行分解.在匹配的过程中, 为了保证SJ-Tree树中相邻叶子节点的匹配结果在数据图上仍然相邻, 构建了一个位图索引结构, 如图 9(b)所示.图 9(b)中, 行表示数据图中所有节点, 列表示满足邻接关系的模式图分解结果.图 9(a)展示了模式图P的两个相邻分解结果g₁和g₂.如果数据图节点在查询分片g₁的匹配结果中, 则相应比特位置1, 其他比特位置0.例如, g₁与数据图中的边(u₁, u₂)相匹配, 则位图中g₁对应的u₁和u₂的比特位分别置1, 其比特位置0.对g₂进行匹配时, 只需要在数据图中g₁所在位图向量对应值为1的节点(即u₁和u₂)周围查找与g₂满足匹配的结果即可.这样匹配的好处是:利用模式图分解结果相邻的特性, 保证匹配结果在数据图上仍然相邻, 能够避免产生不满足邻接关系匹配结果, 减小查找空间, 加快匹配速度.

基于连接的匹配技术采用子图同构的方式进行子图匹配计算, 可以得到精确的匹配结果, 但是代价高昂.虽然利用查询分解的方法可以控制待匹配子图的规模从而限制子图同构的代价, 但是仍会产生很多无效的中间结果.如果再对数据图构建索引以降低无效中间结果的数目, 也需要考虑索引的构建和维护代价.同时, 如何在频繁更新的动态图数据中挖掘特征结构进行查询分解, 仍是当前需要重点解决的问题.

2.2.2 基于探索的匹配技术

文献[19]提出了一种基于探索的匹配技术, 该方法得到的结果是近似结果而不是精确结果.探索的过程如图 10所示:给定模式图P和数据图G, 首先从模式图中的节点a出发, 找到数据图G中与其相匹配的节点a₁; 然后从节点a₁开始探索数据图G, 找到节点b₁, 发现数据图中的边(a₁, b₁)与模式图中的边(a, b)相匹配; 接着从节点b₁出发探索数据图G, 找到节点c₁和c₂, 发现数据图中的边(b₁, c₁), (b₁, c₂)与模式图中的边(b, c)相匹配.这样就可以获得数据图中和模式图相匹配的子图, 而不用像基于连接的匹配技术那样需要对大量的中间匹配结果进行连接计算, 也不需要在数据图上构建和维护索引.

相比基于连接的动态图匹配技术, 基于探索的动态图匹配技术更适合于在分布式并行图处理框架中实现.主流的分布式并行图处理框架, 以谷歌的Pregel^[6]系统为例, 均采用以节点为中心的计算模型框架.该模型框架中:每个节点都维护一个信息输入队列和一个信息输出队列; 每个计算任务由一系列超级步(super-step)组成, 且每个超级步中节点从信息输入队列接收输入信息后, 会按用户自定义的脚本程序对信息进行处理, 最后将处理结果输出至信息输出队列.由于这种以节点为中心的计算模型强调存储和处理单元均是节点, 考虑到基于连接的动态图匹配技术会产生大量中间结果, 这无疑加重了模型框架中节点的处理、存储和数据传输代价, 因而基于连接的动态图匹配技术不太适用于在分布式并行图处理框架中实现.相反, 基于探索的方法因为不需要构建索引且不会产生和处理大量的中间结果, 则更加适用于在分布式并行图处理框架中实现, 并且天然满足增量计算的潜在需求.PathMatch算法是在分布式并行图处理框架中采用的基于探索的匹配技术, 该算法首先找到模式图中的一条哈密顿路径, 哈密顿路径指能够访问到图中每一个节点的路径, 然后基于该路径进行信息传递来完成探索匹配.然而, 将基于探索的动态图匹配技术在分布式并行图处理框架中实现仍然面临以下问题:

● 基于探索的方法得到的结果是近似匹配结果而不是精确匹配结果;

● 在解决一些动态图匹配问题时, 使用基于探索的动态图匹配技术会比使用基于连接的动态图匹配技术的计算代价昂贵得多;

● 并不是所有的图匹配步骤仅仅依靠探索的思路就可以完成, 例如检查需要探索的下一个节点是否是最开始的匹配节点.

针对以上问题, 可以采用基于连接和基于探索相结合的方式解决.即:宏观上使用基于连接的动态图匹配技术的框架, 而在子图匹配的过程中, 使用基于探索的方法找到匹配结果.换言之, 在子图匹配的过程中仍采用模式图分解的方法, 基于模式图中信息的传递而不是基于数据图中提取的特征子图对模式图进行分解.接着, 将每个模式图的分解结果存储到分布式并行图处理框架的一个节点上, 并编写节点的处理脚本, 让节点基于探索的匹配方法实现图匹配.例如, STwigMatch算法^[19]即为基于连接与基于探索相结合的方式, 将模式图分解成一系列小的twigs, 然后对这些小的twigs按照基于探索的匹配技术进行匹配.这种方法的好处是可以权衡匹配计算代价和匹配结果准确率这两个重要因素.

文献[18]采用了分布式框架Giraph, 并提出了基于探索的SSD算法.下面以图 11为例说明SSD算法的计算过程:首先, 将模式图中度最大的节点定为汇点; 然后从汇点出发, 利用宽度优选搜索策略决定边的方向.这样可将模式图转化为单汇点有向无环图(DAG).图 11(b)给出了图 11(a)所示的模式图进行转化后得到的DAG图, 其中, 节点3为汇点, 可以接收到所有其他边传递来的信息.基于汇点可以将图 11(b)所示的DAG图分解成3个子DAG图, 且每一个子DAG中会存在一个入度为0的节点, 被称为源点, 例如, 0号子DAG图中的节点0即是该子DAG图的源点.图 11(c)展示了子图匹配的过程, 在0号子DAG图中, 信息从节点0出发, 传递到其所有邻节点, 即节点1和节点2.信息在这两个节点中经过转换后, 继续向下游的邻节点传递并最终到达节点3, 从而得到从源点开始的信息传递规则.然后, 将这种从源点开始的信息传递规则映射到数据图中, 并基于该规则从与源点属性相同的节点中开始检查后续节点是否匹配.例如图 11(c)中, 源点0与数据图节点a相匹配, 接下来由一系列超级步来完成匹配任务:在第1超级步中, 节点a将信息传递到其相邻的节点; 在第2超级步中, 节点b, c收到信息后并将信息传递给节点d.节点d发现收到的来自相同节点的两条信息, 与0号子DAG图的信息传递规则相同, 则可证明匹配子图的存在.

SSD算法存在一个问题, 即在Super-step 2中, 如果在节点b和节点c将信息传递给节点d的同时, 边(a, b)被删除, 则节点d收到信息后会返回过期的不准确匹配的结果.为了解决这个问题, 文献[23]提出了Stp(Q)算法.

基于探索的匹配技术更加适用于处理规模庞大的图, 但是由于匹配的不一致性会产生不精确的匹配结果, 因而该类方法适用于那些对结果准确率要求不严格的应用, 例如社交网络分析等.如何将基于探索与基于连接这两种方法有效地结合, 用以权衡子图匹配效率与子图匹配准确率这两个重要因素, 是目前研究的热点问题之一.

2.2.3 基于模拟的匹配技术

基于连接的匹配技术可以产生精确的匹配结果但是连接操作代价较为昂贵, 基于探索的匹配技术则会产生不精确的匹配结果, 且这两种方法都采用NP难的子图同构图匹配计算方式, 限制了这两类技术在执行效率上的提升.因此, 基于模拟的匹配技术成为当前动态图匹配技术研究领域的研究热点之一.基于模拟的匹配技术通常先根据节点的标签为模式图中的每个节点产生一个匹配候选集, 然后根据模式图中节点前驱和后继的不同近似程度要求过滤掉不匹配的节点(详见本文第1.1节模拟匹配定义).

文献[13]在原始图模拟匹配的定义上进行了扩展, 提出了受限模拟(bounded simulation)的概念, 重新定义了带有边权重的模式图.模式图中每一条边都维护了常量k, 数据图中的一个节点只要在k跳范围内能与模式图中对应节点的后继节点匹配, 就认为该节点与对应节点匹配.因此, 即使匹配得到的数据子图的结构和模式图的结构不一样, 仍然符合匹配的条件.受限模拟匹配的好处是可以将匹配过程在多项式的时间内完成, 有效提高了子图匹配的效率.该作者同时将受限模拟匹配技术应用到动态图模式匹配中, 提出了增量IncBMatch算法.增量IncBMatch算法与本文第2.2节提到的IncSimMatch算法的增量计算思路相同, 解决了同构匹配复杂度高的问题, 取得了较好的效果.文献[26]首次将IncSimMatch算法应用到以节点为中心的分布式并行图处理框架中, 实现了动态图模拟匹配的分布式并行计算.在匹配过程中, 用框架中的一个节点存放更新的图数据, 并编写执行脚本让该节点过滤掉那些肯定不会产生新匹配结果的边.接着, 再用框架中的一个节点检查这些边是否满足图模拟匹配中对边的约束关系, 当主进程收到来自所有节点的处理信息之后, 检查这些子图是否满足图模拟匹配中边的约束关系, 即可得到最终匹配结果.

基于模拟的匹配方式由于采用二元关系进行匹配, 会产生与模式图结构不一致的结果, 因此主要适用于处理类似社交网络分析这类对图结构匹配要求不是很严格的应用.模拟匹配也可以用来进行候选集的剪枝, 文献[39]提出了一种分布式的动态图剪枝算法D-IDS, 采用构建在图模拟匹配为基础的双向模拟匹配方式对数据图进行剪枝, 双向模拟要求当前节点的所有孩子节点符合二元关系的同时, 其父节点也要符合二元关系.当数据图更新时, 通过二元模拟的思想对数据图进行剪枝, 可以将一个大的数据图剪枝成相对较小的数据图, 并持续地维护该数据图, 在匹配的过程中只需对小图进行增量匹配即可.

模拟匹配的匹配效率高, 不论是分布式环境还是集中式环境下都适用, 具有其独特的优势, 这种优势在处理动态图匹配中更加明显.其中, 构建在以图模拟匹配基础的双向模拟匹配更能很好地权衡模拟匹配结果的有效性和及时性, 同时获得与模式图结构一致性相对更高的匹配结果, 从而有效弥补了基于连接的匹配技术和基于探索的匹配技术的缺陷.

3 面向内容变化的动态图匹配技术

除了面向拓扑结构变化的动态图模式匹配技术之外, 面向内容变化的动态图模式匹配技术也得到了广泛应用.例如:基于该技术, 可以在频繁更新的数据中心网络^[40]中找到满足用户需求的服务器部署方案; 可以在频繁变化的社交网络中帮助广告商找到互相联系紧密的人员团体以便于投放广告等.这些应用中, 节点或者边的属性会随时间发生频繁变化.目前, 对面向内容变化的动态图模式匹配技术的研究工作相对较少, 下面对几个典型的研究工作进行介绍.

以数据中心网络中的资源分配为应用背景, 文献[16]提出了Gradin算法解决了用户按需定制的资源模式图和拓扑结构相对稳定、节点或边的属性频繁变化的数据中心网络图之间的动态匹配问题.在数据中心网络图中, 节点和边的属性分别表示随时间频繁变化的服务器的剩余内存值和网络的有效带宽值.匹配过程包含以下两个阶段.

● 离线索引构建

在离线索引构建的过程中, 考虑到图的拓扑结构固定不变, 可以采用基于连接的匹配技术在数据图中挖掘具有辨识力的频繁子图作为索引元素^[30], 然后基于这些频繁子图在数据图上构建倒排索引.同时, 将模式图基于这些频繁子图进行分解, 得到若干模式图分片, 便于后续基于倒排索引进行检索和匹配.

● 在线查询

由于数据中心网络图的拓扑结构相对稳定, 而节点或边的属性则会发生频繁变化, 因此可以采用网格索引(grid index)结构对数据图中的频繁子图构建索引.具体而言, Gradin算法将带有节点/边的属性值的频繁子图转化为多维向量, 然后将多维向量映射至多维网格结构当中.如图 12所示:s₁表示一个从数据图中挖掘得到的频繁子图, 将数据图中所有与s₁结构相同的子图基于由它们两个节点的属性值构成的二维向量可映射至二维网格索引中.如图 12中所示, 网格索引中的每个圆点均表示数据图中与s₁结构相同的子图.同时, 也按此原理将模式图中与s₁结构相同的子模式图映射至该网格索引中, 如图 12中的方点所示.由于模式图和数据图的子图进行匹配时要求它们之间相应节点的属性值满足偏序关系, 因此, 根据方点位置可以将该二维网格划分为3个区域:落在阴影区域R₁的圆点所对应的数据图子图肯定满足子模式图的匹配要求; 落在阴影区域R₃的圆点所对应的数据图子图肯定不满足子模式图的匹配要求, 因此只需对落在阴影区域R₁和阴影区域R₃之间的区域(即R₂区域)内的圆点所对应的数据图子图进行匹配计算, 即可得到匹配结果.Gradin算法平均需要进行$\frac{dns}{{{\lambda }^{d}}}{{\left(\frac{\lambda +1}{2} \right)}^{d-1}}$ 次匹配, 其中, λ为网格索引的密度, d为网格索引的维度, n_s表示离线索引构建过程中模式图分片的数目.

当数据图的节点或边的属性值遭遇频繁更新时, 网格索引比其他索引结构的维护代价更低, 平均每一次图更新只需对网格索引中的数据图分片进行2(1-1/λ^d)次操作.Gradin算法也可以直接运用于数据图中边的属性值频繁更新的情况.除了采用数据图中的频繁子图对模式图进行分解, 也可以采用目前学术界通用的高等级子图结构对模式图进行分解.文献[41]设计了CASQD系统, 该系统整合了基于探索的图匹配技术和基于连接的图匹配技术, 并选择团、星、双边团等这些具有高识别能力的结构对模式图进行分解.这样设计的好处是不需要对数据图进行频繁子图挖掘, 且高等级结构可以并入到任何支持子图模式匹配的查询语言当中.

4 动态图模式匹配算法的性能比较 4.1 面向拓扑结构变化的动态图匹配算法性能比较

近年来, 动态图匹配技术的应用得到了学术界和工业界的广泛关注.越来越多的动态图匹配算法应运而生, 不同类型的算法有不同的评价标准.按照第2节的分类方式, 将基于拓扑结构变化的动态图匹配技术分为基于快照技术的匹配和基于增量技术的匹配两类, 本节将对这两类算法的性能进行介绍.

4.1.1 基于快照技术的匹配算法性能比较

算法的性能可以通过有效性和效率两方面进行评价.文献[4]将提出的NNT算法与gIndex^[30]以及GraphGrep^[31]算法进行了比较, 采用真实数据与合成数据作为数据集, 其中, 真实数据来自MIT媒体实验室的手机通信信息^[42], 使用2004年1月~2005年5月间97个固定人员的手机通信信息的子集作为实验的数据集, 总共产生了由300个图快照组成图流, 每一个快照代表当前时刻的动态图状态.合成数据用图生成工具^[43]产生.实验结果表明:

● 在有效性方面(如图 13(a)所示), GraphGrep算法会将50%以上匹配的结果对作为候选集, 剪枝能力差, 有效性偏低; 而NNT算法和gIndex算法的有效性相差不大, 其中, NNT算法会产生低于6%的候选集, gIndex算法的候选集则在6%~10%之间;

● 在效率方面(如图 13(b)所示), gIndex算法的查询时间则明显高于另外两种算法.这是因为gIndex算法采用的是频繁子图挖掘的方法, 虽然使得匹配结果的有效性高, 但是在每一个快照都需要挖掘数据图的频繁子图, 因此耗费了大量的时间.而NNT算法与GraphGrep则不需要挖掘子图特征, 因此算法效率较高.

与运用在静态图上基于连接的匹配技术(gIndex算法等)相比, 基于快照的动态图匹配可以从两方面进行改进:第一, 设计有效的索引结构, 可以高效地处理数据图的更新, 同时利用索引的剪枝能力来有效约减匹配候选集的规模; 第二, 采用近似算法, 牺牲部分准确率来换取更高的匹配效率.

文献[15]介绍了动态图的真实数据集, 包括路网交通数据、电话通信数据、专利引用数据以及推特数据, 并对数据集的最大入度/出度、增加边的平均时间间隔、节点以及边的数目进行了描述, 表 3对这些数据进行了详细统计.同时, 将提出的DDST算法与NNT算法进行了比较, 两者采用的模型不同, NNT算法没有考虑窗口下的时间约束关系, 采用的是基于同构匹配问题的近似算法, 得到的匹配结果中存在错误的结果.而DDST算法不仅考虑了数据图更新边上的时间约束关系, 且采用的是基于模拟匹配问题的精确算法, 结果不存在准确率的问题.由于算法的性能需要在相同的实验环境下进行对比, 因此在比较的过程中, 需要忽略时间上的约束关系以及结果的准确率信息, 仅从吞吐率方面对算法的效率进行对比, 吞吐率表示算法每秒能处理的数据图边的数目, 可以衡量算法的效率.如图 14所示, 实验结果表明:无论是在Road数据集还是Phone数据集, DDST算法的吞吐率都明显高于NNT算法; 同时, 随着窗口范围的增大, NNT算法吞吐率下降的幅度相对更大.这是因为NNT算法在索引的维护上要花费大量的开销, 对数据的增加比较敏感, 且采用同构匹配的方式, 限制性强.而DDST则采用的是图模拟的方法, 因此, DDST在吞吐率方面(效率)更好一些.

综上, 为了满足实时性的需求, 基于快照的匹配技术可以从两方面进行设计.

● 若采用同构匹配, 需要设计高效的索引结构, 在数据图更新的过程中, 不会产生过高的索引维护代价; 同时, 需要设计一个近似算法来提升算法的效率;

● 若采用模拟匹配, 可以在图模拟的基础上加上一些限制条件, 更加符合实际应用的需求; 同时, 设计基于该模拟匹配二元关系的精确算法来提升算法的匹配效率.

需要注意的是:同构匹配和模拟匹配的选择, 需要根据具体的应用背景来决定.

4.1.2 基于增量技术的匹配算法性能比较

随着增量技术在动态图匹配中出现, 越来越多的研究工作开始围绕着基于增量技术的动态图匹配进行, 而增量技术也更加适合实时更新的图数据.基于增量技术的匹配算法可以分为基于连接、基于探索以及基于图模拟匹配这3类, 下面分别对这3类动态图匹配算法性能进行分析比较.

(1) 基于连接的匹配技术

文献[14]将SJ-Tree与IncIsoMatch算法进行了比较, 采用真实的2011年8月~10月的《纽约时报》数据集, 包含39 523的节点、68 682条边.并用递增的方式来处理1 000条《纽约时报》更新的数据, 将处理的时间作为评价指标.如图 15所示, 实验结果表明:使用SJ-Tree进行查询的时间更低, 速度更快, 而且这种性能差距会随着数据图的增加变得更大.因为增量匹配技术在匹配的过程中需要在每一个新到来的边的周围进行查找.若采用IncIsoMatch算法, 当一条新的边到来时, 要查找该边端点周围所有k跳范围内的节点, 其中, k表示模式图的直径.当数据图比较密集时, k跳范围内的子图将会累积大量的边, 从而使查找的代价更加昂贵, 查询速率更慢.而SJ-Tree树这种基于查询分解的方法将一个大的匹配转化成一系列小的匹配, 从而使算法的效率更高.

文献[25]在SJ-Tree的基础上提出了一种基于选择度的方法Lazy-Search, 首先选取具有识别能力的结构进行过滤, 减少查找空间.实验结果表明:在查询的过程中, 子图同构操作占据了总查询时间的95%.因此, 减少子图同构的次数, 能够有效增加算法的性能, 其查找速度是VF2算法^[44]的10倍~100倍.

从上述的实验结果可以看出:在进行增量匹配时, 如果将整个模式图进行匹配效率很低, 尤其对密集的数据图.因此, 可以采用将模式图分解的方法, 但是这种方法会产生很多无效的中间结果.同时, 基于连接的匹配技术采用的是子图同构的核实方法, 无效的中间结果会导致匹配效率降低.因此, 可以选择特征结构进行查询分解, 从而过滤无效的中间结果, 加快匹配速率.

(2) 基于探索的匹配技术

文献[18]在分布式的平台Giraph^[8]上进行实验, 将SSD算法与文献[19]的工作以及PathMatch方法进行比较, 并采用真实数据集livejournal.livejournal是综合型SNS交友网站, 有4 847 571个节点、68 993 773条边.其中, 文献[19]采用的是基于STwig的分解框架以及基于探索的匹配方法, 用STwigMatch表示; 而PathMatch方法采用精确的基于探索的匹配方法.实验以查询响应时间以及总的传递信息作为评价标准.如图 16所示, 实验结果表明:SSD算法与STwigMatch方法的性能要整体优于PathMatch方法, 且SSD算法需要传递的信息最少.由于PathMatch方法与STwigMatch方法传递信息巨大, 导致耗费了大量的时间; 而SSD算法采用DAG分解的方式, 可以有效减少消息的传递, 降低查询响应时间.除此之外, 无论是STwigMatch方法还是PathMatch算法, 在测试使用的数据集中都无法处理大小超过7的模式图, 否则会超出内存的限制, 导致查询过程很慢.文献[23]在SSD的基础上提出了Stp(Q), 解决了SSD算法在数据图变化过程中每一个超级步结果的不一致性问题.如图 17所示, 其中, Update ratio表示数据图的更新比率, 例如:0.03表示数据图中有3%新加入的边, 同时有3%的边被移除.实验结果表明:SSD算法的准确率会随着数据图更新程度的增加或者模式图的增大相应降低; 而SSD算法采用Stp(Q)之后, 准确率可以一直保证达到100%, 有效保证了结果的准确率.

从实验结果可以看出, 仅仅使用基于探索的匹配方式性能很差.因此, 可以将基于连接的方法与基于探索的方法相结合, 采用基于连接方法的查询分解框架, 在匹配的过程中采用基于探索的方法.如何有效地利用信息的传递方式对模式图分解, 是这种方法的关键部分, 好的分解方式可以使总的信息传递量减少, 从而提高查询效率.同时, 也需要设计高效的算法来提高结果的准确率.

(3) 基于模拟的匹配技术

文献[13]将IncSimMatch算法、IncBMatch算法和对应的批处理算法Match_s与Match_bs进行比较, 采用真实的YouTube和citation network数据集, 其中:YouTube有14 829个节点、58 901条边, 每一个节点代表一个视频对象, 记录了视频的长度、种类等属性; citation network有17 292个节点、61 351条边, 每一个节点代表一篇论文对象, 记录了论文的题目、作者和发表年份这几个属性.如图 18所示, 实验结果表明:对于IncSimMatch算法(如图 18(a)所示), 当一次边的增加或删除更新所涉及边的数目不超过数据图边总数的40%时, 增量算法要优于批处理算法.对于IncBMatch算法(如图(18b)所示), 当一次边的增加或删除更新所涉及边的数目不超过数据图边总数的20%时, 增量算法要优于批处理算法.当数据图更新部分的大小相同时, IncBMatch算法中增加边操作比删除边操作处理的时间要长很多.文献[39]将提出的剪枝算法D-IDS与IncBMatch算法进行比较, IncBMatch通过受限模拟的方式对数据图进行剪枝, 但产生的结果与模式图结构一致性较低, 而D-IDS算法通过二元模拟匹配则会产生与模式图更加一致的结果.实验结果表明, D-IDS算法平均可以将数据图的大小减小60%.对于直径较小的数据图, 性能提升较高.对于直径较大的数据图, 效率也会有所提高, 但不够明显.文献[38]将分布式的增量算法与批处理算法进行比较, 实验结果表明:在第12次更新之后, 采用增量算法的匹配速率是批处理算法的3倍~10倍, 并且可以过滤掉60%以上的无效更新.

综上, 基于增量技术的动态图模式匹配研究越来越广泛, 一般从3个方面考虑算法的性能提升:第一是设计增量算法, 充分利用之前的匹配结果过滤掉无效的更新; 第二是设计高效的增量子图匹配算法, 在新增加的边周围找到可能是匹配结果的候选集; 第三是设计一种剪枝策略, 进一步在匹配的候选集中过滤掉无效的结果.

针对不同的应用背景, 也需要采取合适的方法.从准确率方面来说, 基于连接的方法可以获得精确的匹配结果, 适合处理对图的拓扑结构要求比较严格的应用.从效率方面来说, 基于连接的匹配技术会产生大量的中间结果, 效率很低.而基于探索的方法会提高匹配效率, 但是准确率不高, 因此可以采用两者相结合的匹配方式.特别地, 针对那些对拓扑结构要求不是严格的应用, 可以采用基于图模拟的匹配方式, 而一些扩展的图模拟匹配则可以获得与模式图结果一致性更高的匹配结果, 从而弥补基于连接与基于探索方法的不足.

4.2 面向内容变化的动态图匹配算法性能比较

基于内容变化的动态图匹配算法一般从查询时间、可扩展性方面对算法的性能进行比较.文献[16]将Gradin与VF2, UpdAll, NaiveGrid以及UpdNo算法进行比较, 其中, VF2是无索引的子图匹配算法, UpdAll将查询分片部署到多维查找树中, NaiveGrid是指使用传统核实算法的网格索引, 而UpdNo则采用倒排索引.实验采用真实的数据集BCUBE, BCUBE是数据中心的一个网络体系结构, 选择其中的3 000个节点作为实验的数据集.如图 19所示, 实验结果表明:Gradin算法的剪枝速率、查询时间与UpdAll算法相似, 但是索引构建时间是UpdAll算法的4倍~10倍; 同时, Gradin算法的剪枝速率是UpdNo算法的10倍, 是NaiveGrid算法的5倍之多.Gradin算法采用基于连接的匹配方式, 可以加速图匹配过程, 使得其查找速度最快.

目前面向内容变化的动态图模式匹配研究相对较少, 主要用于数据中心方面.一般从两方面进行考虑:第一, 对于属性更新不是很频繁的应用可以采用基于连接的匹配技术, 类似于静态图匹配; 第二, 对于属性频繁更新的应用, 如果采用基于连接的匹配方式则会不断产生大量的中间结果, 因此可以采用基于探索的匹配方式.

5 动态图匹配技术的应用分析

近年来, 图数据广泛地应用于刻画现实世界中各类实体间的复杂关系, 且这种复杂的关系在现实世界中时刻经历着变化.因此, 与传统的静态图模式匹配技术相比, 动态图模式匹配技术的应用场景更加广泛.本节对动态图数据匹配技术的应用现状进行了总结.

(1) 犯罪行为分析

目前, 毒品交易、恐怖袭击事件等犯罪行为给国家造成了严重的危害.可建立以人物为节点、活动关系为边的行为关系图作为数据图, 同时定义犯罪团体行为关系图作为模式图, 从而利用模式图和动态数据图之间的模式匹配技术发现和预测潜在的犯罪团伙.

例如, 文献[13]采用面向动态图的受限模拟匹配技术分析有潜在毒品贩卖行为团伙.如图 20所示:P₀为模式图, 图中的节点表示犯罪人员, 边表示他们之间的贩卖关系, 边(AM, FW)上的边属性值为3, 意味着从AM这个人到FW这个人需要满足在3跳之内贩卖约束.基于该模式图, 在大规模动态变化的行为关系图中进行匹配查找, 即可及时发现潜在的毒品贩卖关系团伙, 为犯罪案件的侦破提供有力依据.据悉, 美国著名的情报公司Palantir还利用该技术完成了特定场景的侦查分析任务.

(2) 路网监测

城市的道路交通监测是动态图模式匹配技术的重要应用.城市路网可以表示为图的形式, 其中, 节点表示路口, 边表示路段.同时, 用户可以根据交通事故发生后周围的典型路况定义模式图, 将该模式图与动态变化的路网数据图进行匹配, 以完成对交通事故的实时监测.以文献[15]中的路网检测为例, 如图 21所示, 其中, 图 21(a)表示交通事故发生后周围的典型路况, 图中边的属性表示该边所对应的道路的拥堵情况(cong.表示拥堵, smooth.表示畅行).在匹配的过程中, 需要满足时间上的偏序关系, 这种时间上的偏序关系可以定义成如图 21(b)所示的时间关系图, 图中的每一个节点对应图 21(a)中的每一条边.模式图和数据图的相应子图之间只有满足图 21(b)定义的时间域上的先后顺序, 才能成为最终匹配结果.每一次的道路交通拥塞报告都可以看做是对路网图数据的更新, 且更新的部分需要在如图 21(c)所示的时间窗口范围内才认为有效.图 21(d)和图 21(e)分别表示路网数据图在不同时间点上的两个快照, 图中括号内的数字表示时间.可以将图 21(a)所示的交通事故发生模式图和不同时刻动态变化的路网数据图(例如图 21(d)和图 21(e))进行模式匹配, 完成对交通事故的实时检测.此例中, 图 21(e)存在与模式图相匹配的子图.

(3) 网络安全监测

随着互联网行业的快速发展, 网络安全问题越发突出.以文献[25]中的网络攻击监测为例, 图 22展示了3个用户定义的网络攻击行为模式图, 图中的节点表示主机, 边表示主机间的通信、用户登录等交互关系.基于动态图模式匹配技术将网络攻击行为模式图和动态变化的网络图进行模式匹配, 可及时发现网络中的网络攻击事件或潜在网络攻击事件, 达到对网络攻击行为进行检测甚至预测的效果.

(4) 计算生物学数据分析

生物学中研究的分子结构数据可以表示为图的形式.在蛋白质交互作用网络(protein-interaction network)中, 蛋白质可能会与某种酶发生反应导致变异.通过将已知性质的蛋白质网络和动态变化的蛋白质交互作用网络进行匹配, 可以从蛋白质交互作用网络中快速地找到发生变异的蛋白质结构, 为研究生物组织的结构及功能提供重要依据.例如, 文献[45]在对包含1.8万个蛋白质(节点)和4.4万种蛋白质之间的相互关系(边)的蛋白质交互作用网络进行研究的过程中, 通过计算蛋白质交互作用网络的连通性、中心性以及匹配已知性质的结构, 发现介数中心性(betweenness)大且连联通性小的蛋白质在人类基因中是冗余的蛋白质, 这无疑为分析基因和蛋白质功能提供了重要的依据.

6 结论与展望

动态图作为目前广泛使用的数据模型, 对动态图数据匹配方面的研究具有十分重要的理论意义和应用前景, 引起了学术和工业界越来越多的关注.随着大数据时代的到来, 数据规模的激增, 数据更新越发频繁, 数据之间的关系越发复杂, 这无疑给动态图数据匹配技术的研究和应用提出了新的挑战, 也产生了新的机遇, 可以从以下几个方面开展研究.

● 面对图数据规模激增的现状, 可以研究如何基于主流的分布式并行图处理框架系统, 例如谷歌的Pregel和Apache的Giraph, 来实现图匹配的并行分布式处理, 提高匹配技术应对大规模图数据的可扩展性.这些主流的分布式并行图处理框架系统通常采用以节点为中心的处理模式.以节点为中心的处理模式的基本计算单元是节点, 其将数据图进行划分, 由计算框架中的每个节点存储和处理一个分区的图数据.文献[29]还提出了一种动态图处理框架BLADYG, 提出用以块为中心的分布式并行计算模型来处理大规模数据图.中心块计算模型的基本计算单元是块, 每一个块存储和处理的是数据图的一个连通子图.这两种分布式并行图处理模型各有优劣, 研究人员可以根据应用需求灵活选择;

● 面对图数据更新越发频繁的现状, 采用快照的匹配方法很难满足动态图匹配的实时性需求, 因此需要研究高效的面向动态图特点的匹配方式和查询优化策略.当前, 研究者可以从增量算法设计和候选集剪枝两方面进行研究, 从而缩小查询范围, 提高匹配效率;

● 基于连接的匹配技术是实现动态图模式匹配的有效手段, 从模式图或数据图中提取优质的特征, 是该技术面临的核心问题之一.为了避免发生数据图更新导致特征失效的情况, 目前的研究工作一般选择单边子图或双边子图这类简单子图作为数据图的特征.然而, 这类简单子图的可识别特性不强, 导致中间匹配结果激增, 加重了子图连接阶段的处理代价.因而, 如何提取更加有识别度的特征, 同时设计高效的特征维护方案, 是当前研究的主要问题.另一方面, 基于探索的动态图匹配方式有其特有的优势, 但却面临着匹配结果准确率偏低的问题, 可以研究基于探索的动态图匹配技术与基于连接的动态图匹配技术相结合的新型处理方案, 重点考虑结合过程中如何发挥各自技术类型的优势, 从而弥补各自技术类型的缺憾.基于模拟的匹配技术是当前研究的热点, 它避免了复杂的子图同构匹配计算, 对模拟匹配技术进行扩展研究, 将是另一个研究关注点.另外, 设计面向应用需求的图匹配相似度度量模型、开发更有效的图匹配近似算法, 也是未来的研究方向;

● 目前, 大部分研究涉及的动态图数据匹配问题都是针对模式图不变、数据图随时间动态变化的情况, 然而在实际生活中, 模式图发生变化的情况也非常普遍.例如:网络安全领域, 病毒经常发生变种, 网络攻击模式也在不断发生演变; 在计算生物学领域, 蛋白质变性、流感病毒变异也时常发生.文献[38]研究了数据图不变、模式图发生动态变化时的图模式匹配增量算法.研究者们一方面可以开拓研究这方面的增量处理技术; 另一方面, 也可以将模式图变化与数据图变化结合起来, 拓展动态图数据匹配技术的应用领域.