来自互联网及生活中的海量数据之间存在紧密的关联性，图作为一种被广泛应用的数据结构，非常适合刻画这种具有关联性的数据，图中的每个顶点代表现实世界中的实体对象，顶点之间的边表示实体之间的关系.图模式匹配是在一个数据图G中找到所有和给定模式图P相同或相似的子图.图模式匹配被广泛地应用于社交网络分析、Web网络分析、知识发现和生物信息学等领域，如在万维网中用于进行Web文档分类[1]，在软件工程领域用于软件代码剽窃检测[2]等.

https://www.bitpiepaz.com

在大数据时代，图数据规模急剧增长，例如，Facebook中的好友网络包含16亿个节点和1 500亿条边，而万维网包含超过500亿个网页以及万亿量级的链接.对如此大规模的数据图进行一次完整的图模式匹配会耗费大量的时间和资源，因此，部分研究人员研究了动态图模式匹配[3，4，5，6]，主要研究方向是模式图不变、数据图动态变化时的增量图模式匹配算法.通过引入增量处理技术，当数据图更新时，仅对图中更新的数据进行分析和重新匹配，避免对整体数据的重复计算.然而在实际生活中，模式图发生变化的情况也非常普遍，例如，在生物信息学领域，代表蛋白质和流感病毒的图通常被作为模式图，蛋白质变性、流感病毒变异时有发生;在网络安全领域，描述计算机病毒和网络攻击模式的图经常被作为模式图，病毒经常发生变种，网络攻击模式也不断变化.先前的增量图模式匹配算法不适用于模式图发生变化时的图模式匹配，随着图数据规模的增加，当代表蛋白质、病毒等的模式图P发生变化时，若重新在整个数据图G中查找P，则将耗费大量的时间和资源，因此，研究支持模式图变化的增量图模式匹配算法具有非常重要的意义.与传统的重新进行匹配的重计算算法(ReComuputing)不同，面向模式图变化的增量图模式匹配算法将能够根据P的变化ΔP，利用原来的匹配结果M，得到匹配结果的变化ΔM.

本文研究在固定不变的数据图上对发生变化的模式图进行匹配的增量图模式匹配问题.首先，提出了面向模式图变化的增量图模式匹配算法(pattern graph change oriented incremental graph pattern matching，简称PGC_IncGPM)的基本框架;其次，提出了一种增强的图模式匹配算法(graph pattern matching strengthened，简称GPMS)，该算法除了能够在模式图匹配的过程中更高效地计算出当前的匹配结果以外，还能记录适当的中间结果作为索引，用于后续的模式匹配，减少后续匹配中不必要的重复计算;接着，分别针对模式图的两种基本变化情况(增加边和减少边)，提出如何利用之前的匹配结果和索引进行增量图模式匹配的算法;最后，在真实数据和合成数据上对本文提出的算法进行实验，分析和验证了本文所提出算法的效率.

1 相关工作 1.1 图模式匹配

近年来，图模式匹配成为大数据研究的热点.典型的图模式匹配定义为子图同构，通常采用基于连接的方法或基于探测的方法实现.基于连接的方法的思路是:首先，根据顶点标签，为模式图中的每个顶点产生候选匹配点;然后，不断连接这些候选匹配点，得到一个更大的局部匹配结果;最后，找到准确的匹配结果.在该方法中，连接顺序影响算法效率[7， 8].基于探测的方法的思路是:从数据图的一个顶点出发，根据模式图中的结构关系对数据图进行探测，检测被访问的点是否在一个匹配的子图中[9].

由于子图同构是NPC问题并且应用于社交网络等数据图时过于严格，因此现实生活中图模式匹配通常定义为近似匹配.匹配的方法通常是先根据节点的标签为模式图中的每一个节点产生一个候选匹配集，再根据对模式图中点的前驱和后继的不同近似程度要求过滤掉不匹配的节点.按照实际应用对匹配近似程度的不同要求，图模式匹配可以定义为图模拟(graph simulation)[10]、受限模拟(bounded simulation)[11]、强模拟(strong simulation)[12]、双向模拟(dual simulation)[13]和严格模拟(strict simulation)[13]等.与子图同构相比，图模拟只要求匹配点保持模式图中对应点的后继关系;受限模拟把模式图中的边对应到数据图中的一条路径，数据图中的一个点只要存在一个子孙节点能与模式图中对应点的后继节点匹配，就认为该点与对应点匹配;双向模拟在图模拟的基础上，还要求匹配点保持模式图中对应点的前驱关系;强模拟在双向模拟的基础上，进一步要求匹配点所在子图(子图中包含非匹配点)的半径不大于模式图的直径;严格模拟比强模拟要求更严格，要求完全由匹配点构成的子图的半径不大于模式图的直径.按约束关系由弱到强的顺序对各种图模式匹配进行排序，其结果是:受限模拟、图模拟、双向模拟、强模拟、严格模拟.由于受限模拟和图模拟要求太松，在实际应用中会产生大量没有实际利用价值的匹配点，淹没有用信息;而强模拟和严格模拟的要求仍然较严格导致匹配算法时间复杂度较高，在实际应用中响应时间长.因此，双向模拟在模拟结果的有效性和响应及时性方面具有更好的平衡性，具有更高的实用价值.综上，本文中图模式匹配定义为双向模拟.

1.2 数据图变化的增量图算

对于数据图发生变化的情况，Ramalingam等人[14]研究了针对最短路径问题的增量算法，对由于插入和减少边而导致最短路径有可能变化的点的最短路径进行重新计算.Fan等人[3]通过借鉴Ramalingam的解决最短路径问题的算法提出了针对图模拟的增量算法:先根据数据图的变化确定受影响区域(即匹配状态会改变的节点集);然后，按照图模式匹配的定义对受影响节点重新进行匹配.文献[4]提出了子图同构的增量匹配算法.文献[5]提出了快速不精确图模式匹配算法及增量算法:利用一个指数级的索引，近似确定在一组图流中是否包含一组给定的模式图.该算法把近似子图搜索问题转化为向量空间的关系检测，当图中增加边或减少边时，会修改相关节点的向量，重新检查新的向量是否依然包含模式图的向量即重新确定匹配状态.文献[15]提出了增量simrank算法:首先，根据矩阵操作的特点采用一些技巧，使得链路更新时，相似矩阵的更新操作转变为部分行和列的更新操作;在此基础上又提出有效的剪枝技术，以获得受影响区域的相似性变化，在不影响准确性的情况下减少不必要的计算.文献[16， 17]提出了一种在数据图上的基于等价关系的增量互模拟算法，当数据图发生变化时，先标识已有的划分中需要改变的部分，然后对其进行重新计算.上述增量算法的思路基本相同:在模式图不变的前提下，根据数据图的变化分析并确定可能受影响的区域，对动态变化部分、受影响的子图进行重新计算，得到变化的匹配结果.

先前的增量算法面向的是数据图动态变化的情况，不适用于模式图动态变化的情形.在实际生活中，模式图动态变化的情况也非常普遍.针对这种应用场景，本文提出一种面向模式图变化的增量图模式匹配算法.

2 模式图变化的增量图模式匹配的形式化描述

首先，我们将给出图模式匹配的基本定义;然后，在此基础上提出面向模式图变化的增量图模式匹配的形式化描述.对于图模式匹配，模式图和数据图都是带标签的有向图，图中的每个节点有且仅有一个标签，该标签定义了节点的属性(如关键词、技能、等级、姓名、公司等).

定义1(图). G=(V，E，L)是一个图，V是节点集，E⊆V×V是边集，L是一个标签函数，V中的每个节点都有一个标签att，即L(v)=att，att是v的属性.

定义2(图模式匹配). 假设有一个模式图P=(Vp，Ep，Lp)和一个数据图G=(V，E，L)，u和v分别是P和G中的节点.如果存在一个二元关系R⊆Vp×V，满足以下条件，则说G匹配P，R是一个匹配:

(1) 如果(u，v)∈R，那么u和v有相同的标签，即Lp(u)=L(v).

(2) 对Vp中的任意一个节点u，V中都存在一个节点v，使得(u，v)∈R，且

   (a) 对Ep中的任意一条边(u，u')，在E中都存在一条边(v，v’)，使得(u'，v')∈R;

   (b) 对Ep中的任意一条边(u"，u)，在E中都存在一条边(v"，v)，使得(u"，v")∈R;

条件(a)保证了匹配点v保持了u的后继关系，条件(b)保证匹配点v保持了u的前驱关系.显然，对于任意P和G，如果G匹配P，则一定存在一个最大的匹配关系RM.图模式匹配问题就是找出RM，根据RM建立匹配结果 图Gr.

定义3(模式图变化的增量图模式匹配). 给定一个数据图G，一个模式图P，模式图变化前G匹配P的结果为M(P，G).当模式图发生变化ΔP以后，增量图模式匹配能够找到匹配结果的变化ΔM，使得增量图模式匹配结果M(P⊕ΔP，G)满足如下关系:M(P⊕ΔP，G)=M(P，G)⊕ΔM，即，当P变化时，增量图模式匹配算法能够利用以前的计算结果M(P，G)，通过获得ΔM且与ΔM进行运算，获得新的匹配结果，达到减少不必要的重复计算的目的.

3 面向模式图变化的增量图模式匹配算法PGC_IncGPM

根据上一节中的定义3，为了在模式图P发生变化后通过增量式的算法获得新的匹配结果，除了需要使用原来的匹配结果M(P，G)以外，还需要获得匹配结果的变化ΔM，其中，如何获得ΔM以及如何根据M(P，G)和ΔM得出新的匹配结果M(P⊕ΔP，G)，成为整个算法的关键.为了快速获得ΔM，可以预先选择数据图中的特征建立索引，使得增量模式匹配时可以根据索引快速缩小搜索空间.建立的索引越多，增量匹配的搜索空间越少，获得ΔM所需的时间越少，但是保存索引所占存储空间也越大.对于大规模图来说，一方面需要减少匹配时间，另一方面也需要尽量减少存储开销.我们在平衡考虑索引对存储开销和时间开销的影响之后，提出在原来匹配过程中记录以下3类集合作为索引:

(1) cand(·)集合:对P中的任一节点u，cand(u)包含G中所有仅仅标签和u相同的节点;

(2) sim(·)集合:对P中的任一节点u，sim(u)包含G中所有保持u的后继关系的节点;

(3) mat(·)集合:对P中的任一节点u，mat(u)包含G中所有与u匹配的节点，mat(·)集合中的所有点都在匹配结果图中.

3.1 PGC_IncGPM算法基本框架

面向图模式变化的增量图模式匹配算法PGC_IncGPM的基本框架如图 1所示.

Fig.1 Basic framework of PGC_IncGPM algorithm 图 1 PGC_IncGPM算法的基本框架

首先使用增强的图模式匹配算法GPMS，用于第一次在整个数据图G上对模式图P进行图模式匹配，一方面获得匹配结果图Gr，另一方面建立后续增量匹配所需的索引index.由于模式图的变化可以分解为由“增加边”(+e)操作或“减少边”(-e)操作或两种操作的联合作用导致的变化，因此，模式图的变化ΔP中可能有增加的边，也可能有减少的边，我们分别用E+和E-表示所有增加的边的集合和所有减少的边的集合.增量图模式匹配算法 将分解为依次根据E+和E-进行增量式匹配的过程:先对E+，调用子算法AddEdges，获得匹配结果G'r和索引index';再对E-，调用子算法SubEdges，获得匹配结果图G"r和索引index".G"r就是模式图变化ΔP后的新匹配结果图;index"是目前状态下的索引，可以继续用于模式图再次发生变化后进行后续的增量匹配.如果模式图的变化仅包含一种操作，即，仅“增加边”或仅“减少边”，则以上两个步骤可以省略一个.若模式图继续发生变化，则继续调用AddEdges和SubEdges子算法，产生下一轮匹配结果.下面依次详细阐述增强的图模式匹配算法GPMS、面向模式图增边的子算法AddEdges和面向模式图减边的子算法SubEdges.

3.2 增强的图模式匹配算法GPMS

由于PGC_IncGPM算法中AddEdges和SubEdges子算法的执行依赖于在整个数据图G上对P进行图模式匹配产生的匹配结果图Gr和建立的索引index，因此，整个数据图上的图模式匹配算法是增量图匹配算法的基础.为了高效实现PGC_IncGPM算法，我们对传统的图模式匹配算法GPM进行了改进:

• 一方面，GPMS算法在执行图模式匹配过程中增加了建立用于后续匹配的索引的过程.

使用GPM算法时，在整个数据图G上进行图模式匹配仅输出匹配结果图Gr，而使用GPMS算法除了能够得到Gr以外，还能对P中的每个节点u，产生cand(u)，sim(u)和mat(u)这3个互斥的集合作为索引，用于支持后续的增量图模式匹配.3个集合中，cand(u)保存了G中所有仅仅标签和u相同的节点，sim(u)保存了G中所有只保持u的后继关系的节点，mat(u)保存了G中所有与u匹配的节点.

• 另一方面，GPMS算法对GPM算法中的候选点筛选顺序进行了优化，减少了执行时间.

GPM算法在模式图匹配时，先根据标签匹配为P中每个节点产生候选匹配集，然后对候选匹配集中的各点根据其前驱和后继关系进行筛选过滤，直到候选匹配集不再变化为止.这种方法会造成筛选过程的反复迭代，导致算法执行时间较长.由于图一般采用邻接表的方式存储，访问节点后继比较容易，而访问节点前驱的时间复杂度很高，所以我们按如下方法对GPM算法中的候选点筛选顺序进行优化:首先，按照P的逆拓扑序列的次序，根据后继关系依次筛选P中各节点的候选匹配集;其次，按照P的拓扑序列的次序，根据节点前驱进一步筛选各节点的候选匹配集;最后，在规模已经很小的候选匹配集上对各节点根据后继、前驱分别筛选，直到候选匹配集不再变化为止，得到最终的匹配集.模式图P中有可能存在强连通分量(strong connected component，简称SCC)，对于这种情况，先把P转化为一个有向无环图P'，方法为:a) 找出P中所有强连通分量;b) 把每个强连通分量汇聚成一个节点，得到一个图P';c) 对P'进行拓扑排序，然后再把每个强连通分量汇聚点用原来的节点集替换，得到P的类拓扑序列.

综上，GPMS算法的描述如算法1所示，其步骤如下:

• 第1步，根据标签匹配为P中每个节点u产生候选匹配集sim(u)(第1行、第2行).

• 第2步，按P的逆拓扑序列，依次根据节点的后继筛选P中各节点的候选集sim(·)，得到满足后继匹配条件的结果sim(·)(SCC内的节点的候选集要筛选多遍，直至SCC内各节点的sim(·)无变化为止)，从sim(·)中删除的节点加入cand(·)(第3行~第6行).

• 第3步，按P的拓扑序列，依次根据节点的前驱筛选P中各节点的sim(·)，满足前驱匹配条件的候选点加入mat(·)(第7行~第10行).

• 第4步，反复对各节点的mat(·)集根据后继和前驱进行筛选，直至无变化，得出最终的匹配集mat(·)(第11行、第12行).

• 第5步，根据mat(·)组合得出最大匹配集RM，由mat(·)中节点及它们之间的边构建出匹配结果图Gr=(Er， Vr)(第13行、第14行).

算法1. 增强的图模式匹配算法GPMS.

输入:模式图P，数据图G.

输出:结果图Gr，cand(·)，sim(·)和mat(·).

1)   for each u∈VPdo

2)       sim(u)={v|v∈V∧L(v)=Lp(v)} $cand\left( u \right) = \emptyset$ ; $mat\left( u \right) = \emptyset$;

3)    for each ordered u∈VP do //according to the inverse topological sort order of P

4)       for each w∈sim(u) do

5)         ifthere exist u'∈succ(u) such that succ(w)∩sim(u')=$\emptyset$ then //succ(u) is the set of succsor nodes of u

6)            sim(u)=sim(u)\{w}; cand(u)=cand(u)∪{w};

7)    for each ordered u∈VP do //according to the topological sort order of P

8)      for each w∈sim(u) do

9)         iffor any u"∈pre(u) such that pre(w)∩mat(u"$\ne \emptyset$) then //pre(u) is the set of precursor nodes of u

10)            $mat\left( u \right) = mat\left( u \right) \cup \left\{ w \right\};sim\left( u \right) = sim\left( u \right)\backslash \left\{ w \right\};$

11) while there exist u∈VP， w∈mat(u) and u"∈pre(u) such that pre(w)∩mat(u")=$\emptyset$ or u'∈succ(u) such that

succ(w)∩mt(u')=$\emptyset $ do

12)         $mat\left( u \right) = mat\left( u \right)\backslash \left\{ w \right\};sim\left( u \right) = sim\left( u \right) \cup \left\{ w \right\};$

13) ${R_M} = \{ \left( {u，tp官网下载w} \right)|u \in {V_p}， tp官方下载安卓最新版2025w \in mat\left( u \right)\} \} ;$

14) Construct Gr according to the nodes in mat(·) and the relations between them;

下面以一个图模式匹配的实例解释GPMS算法的工作过程，如图 2所示.图 2左边是模式图P，中间是数据图G.P中的D和E构成一个强连通分量，把D和E看成一个汇聚点，对P进行拓扑排序得到P的类拓扑序列为{A，B，C，{D，E}}.按照GPMS算法:

Fig.2 An example of graph pattern matching using GPMS algorithm 图 2 使用GPMS算法进行图模式匹配的一个实例

• 第1步产生各节点的初始sim(·)集，见表 1(a).

Table 1 Index built during the process of graph pattern matching for the example in Fig. 2表 1 对图 2实例进行图模式匹配建立的索引

• 第2步，按P的逆拓扑序列{{D，E}，C，B，A}对各节点的sim(·)集根据后继进行筛选:先筛选sim(D)，此时， sim(D)中各节点已满足后继匹配，对其筛选完成;再筛选sim(E)，由于E4没有后继匹配D，所以从sim(E)中删除E4，并将其加入cand(E)，由于D和E构成一个强连通分量，因此，sim(E)发生变化后还要继续筛选sim(D)，将D4从sim(D)中删除，并将其加入cand(E)，然后再筛选sim(E)，最终，E3，D3也依次从sim(E)和sim(D)中删除，并加入到cand(E)和cand(D)中，至此，sim(E)和sim(D)不再变化，对它们的筛选完成;接下来依次筛选sim(C)，sim(B)，sim(A)，C3，A3依次从对应的sim(·)中删除，并加入到cand(·)中.至此，索引状态见表 1(b).

• 第3步，按P的类拓扑序列{A，B，C，{D，E}}对各节点的sim(·)集根据前驱进行筛选:sim(A)中的所有节点都满足前驱匹配，因此全部从sim(A)中移到mat(A)中;由于B3没有能够匹配A的前驱，所以只能留在sim(B)中而不能加入mat(B).依此类推，对其余sim(·)集按照相同的方法进行筛选.至此，索引状态见表 1(c).

• 第4步，对mat(·)中的点根据前驱和后继分别筛选，将不满足前驱或后继匹配的节点从mat(·)移动到sim(·)中.在该实例中，本步骤未引起索引状态变化.

• 第5步，把mat(·)中的各点用它们之间的边连起来，得到结果图Gr，如图 2中最右边的Gr所示.

3.3 面向模式图增边的子算法AddEdges

如果模式图P增加一条或者多条边，那么匹配结果图Gr中有些点可能就不再匹配，ΔM即为所有这些不再匹配部分的集合，此时，需要对原来的匹配结果进行筛选，增量模式匹配将从原来的匹配结果中去除ΔM，是一个对原匹配结果的精简过程.

对于增加边后的模式图P+，增量匹配算法的思路是对每一条增加的边(u，u')执行如下操作:

• 首先，对任一v∈mat(u)，检查v是否有后继节点匹配u'，如果没有，则v不再匹配u;对任一v'∈mat(u')，检查其是否有前驱节点匹配u，如果没有，则v不再匹配u;如果v原来匹配u，但在新的模式图P+下v不再匹配u，那么原来匹配结果中v的前驱和后继也可能不再匹配，因此还要继续检查v的前驱和后继是否匹配.以上操作会使mat(·)中的某些节点加入cand(·)或者sim(·)，在得到新的匹配结果图的同时，也会更新索引.

• 其次，由于增加边(u，u')后sim(u)中的节点w也有可能不再满足u的后继关系，为了保证索引数据一致性，还需要把w从sim(u)中移出加入cand(u);另外，w状态的变化可能会影响到它的所有前驱节点，因此对其前驱也需进行同样的处理.以上操作会进一步更新索引.

综上，面向模式图增边的子算法AddEdges如算法2所示:

• 依次对插入的每一条边(u，u')进行后面的处理，队列Q中保存原来匹配结果中在新的模式图下不再匹配的节点，其初始化为空(第2行).

• mat(u)中没有后继匹配u'的节点放入Q中(第3行~第5行)，mat(u')中没有前驱匹配u的节点也放入Q中(第6行~第8行).

• 当Q不空时，我们从Q中删除队头元素(u，v)，将v从Vr和mat(u)中删除(第11行).

• 然后检查v是否保持u的后继关系:如果满足，则v加入sim(u);否则，v加入cand(u)(第12~16行).

• 接下来，对结果图Gr中v的每个前驱v1，首先从Gr中减少边(v1，v)，然后根据后继关系检查v1的匹配状态是否改变，若改变，则把v1加入Q中(第17行~第21行);对Gr中v的每个后继v2，根据前驱关系检查v2的匹配状态是否改变，若改变，则把v2加入Q中(第22行~第26行).

• 对sim(u)中的任一节点w，检查其是否保持新模式图下u的后继关系，若不满足，则将w从sim(u)中移出加入cand(u);同时，对w的所有前驱继续进行同样的处理(第27行~第30行).

• 最后，返回新的匹配结果图(第31行).

算法2. 面向模式图增边的子算法AddEdges.

输入:模式图P，结果图Gr=(Vr，Er)，mat(·)，sim(·)，cand (·)，P中插入的边的集合E+;

输出:新的匹配结果图Gr，更新后的索引cand(·)，sim(·)和mat(·).

1)   for each (u，u') in E+ do

2)      Queue Q=Ø

3)      for each v∈mat(u) do

4)         if succ(v)∩mat(u')=Ø then

5)           push(Q，(u，v));

6)     for each v'∈mat(u) do

7)         if(pre(v')∩mat(u)=Ø) then

8)           push(Q，(u'，v'));

9)     while (Q is not empty) do

10)         (u，v)=pop(Q);

11)         Vr=Vr\{v}; mat(u)=mat(u)\{v};

12)         check if v can match u according to the subsequence relationships of u;

13)         if vcan match u according to subsequence relationships of u then

14)           sim(u)=sim(u)∪{v}

15)         else

16)           cand(u)=cand(u)∪{v}

17)         for each ep=(u1，u) that er=(v1，v) can match do

18)           Er=Er\(v1，v);

19)           check if v1 can match u1 according to subsequence relationships of u1;

20)           ifv1 can’t match u1 then

21)           push(Q，(u1，v1));

22)         for each ep=(u，u2) that er=(v，v2) can match do

23)           Er=Er\(v，v2);

24)           check if v2 can match u2 according to the precursor relationships of u2;

25)           ifv2 can’t match u2 then

26)           push(Q，(u2，v2));

27)   for eachw∈sim(u) do

28)         check if w can match u according to subsequence relationships of u;

29)         if w can not match u then

30)           remove w from sim(u) to cand(u) and continue to handle the precursor nodes of w;

31) return Gr;

仍然以图 2中的图模式匹配为例，如果在图 2中P上插入一条边(B，C)，首先对原来的匹配结果Gr进行检查， B2和C2不再匹配，B2加入cand(B)，C2加入sim(C);对B2和C2的前驱和后继进行检查和处理，A2~E2构成的子图从Gr中移出.A1~E1构成的子图中加入一条边(B2，C2)即为新的Gr，如图 3所示.更新后的索引见表 2.

Fig.3 Match result of AddEdges when the edge (B，C) is added to P 图 3 P增加边(B，C)后，执行AddEdges得到的匹配结果 Table 2 Index updated by AddEdges when the edge (B，C) is added to P表 2 P增加边(B，C)后，执行AddEdges得到的索引 3.4 面向模式图减边的子算法SubEdges

如果P中删除一条或多条边，原来的匹配结果依然是匹配的，原来不匹配的节点可能会匹配，ΔM即为所有新增的匹配节点的集合，增量模式匹配将在原来的匹配结果中增加ΔM，是一个扩充匹配结果的过程.对减少边后的模式图P-，增量匹配算法更新匹配结果;同时，为了能够支持模式图的再次变化，继续执行后续的增量图模式匹配，还需要对索引进行同步更新.

对于P-，增量匹配算法的思路是对每一条删除的边(u，u')执行如下操作:由于边(u，u')被删除，cand(u)中有些节点w可能满足了u的后继关系，需要加入sim(u)中;w匹配状态的改变会影响到w的前驱节点，继而又影响到该前驱节点的前驱节点.依此类推，影响会逐级扩散下去.因此，对所有受影响的节点的匹配状态进行重新检测.

对所有删除的边进行上述操作后，再在更新的sim(·)上采用和GPMS第4步一样的方法，根据前驱和后继进行筛选，同时满足前驱和后继关系的点从sim(·)中移到mat(·)中.当sim(·)和mat(·)不再变化时，就获得了新的匹配结果图和更新后的索引.

面向模式图减边的子算法SubEdges如算法3所示:

• 依次对删除的每一条边(u，u')进行处理，以更新由于该边的删除而引起的cand(·)，sim(·)和mat(·)的变化.队列Q中保存cand(·)中那些由于模式图中(u，u')的删除而有可能满足节点后继匹配条件的节点，其初始化为空(第2行).

• cand(u)中的任一节点匹配状态都有可能改变，因此把它们都放入Q中(第3行、第4行).

• 当Q不空时，从Q中删除队头元素(u，v)，检查v是否满足u的后继关系匹配(第6行、第7行):如果满足，则v从cand(u)中移出加入sim(u);同时，v的前驱的匹配状态也有可能改变，因此，v的前驱也都插入到Q中(第8行~第12行).

• 当所有边处理完毕后，对P中的每个节点u和sim(u)中的每个节点v，根据u的前驱和后继检查v是否匹配u:若匹配，则将v从sim(u)中移出加入mat(u);同时，将v和v相关联的边加入Gr(第13行~第17行).

• 最后，返回新的匹配结果图(第18行).

算法3. 面向模式图减边的子算法SubEdges.

输入:模式图P，结果图Gr=(Vr，Er)，mat(·)，sim(·)，cand (·)，P中删除的边的集合E+;

输出:新的结果图Gr，更新后的索引cand(·)，sim(·)和mat(·).

1)   for each (u，u') in E- do

2)      Queue Q=Ø

3)      for each v∈ cand(u) do

4)           push(Q，(u，v));

5)      while (Q is not empty) do

6)           (u，v)=pop(Q);

7)           check if v can match u according to according to subsequence relationships of u;

8)           if v can match u according to according to subsequence relationships of u then

9)             sim(u)=sim(u)∪{v}; cand(u)=cand(u)\{v};

10)             for each ep=(u1，u) do

11)               for each v1∈cand(u1)∩pre(v) do

12)                 push(Q，(u1，v1));

13)for each u∈VP and each w∈sim(u) do

14)   check if w can match u according to precursor and subsequence relationships of u;

15)   if wcan match u then

16)      mat(u)=mat(u)∪{w}; sim(u)=sim(u)\{w};

17)      add w and the edges associated with it to Gr;

18) return Gr;

继续以图 2中的图模式匹配为例，如果从P上删除边(E，D)，则E4，D4，E3，D3，C3，A3依次从对应的cand(·)中移出并加入sim(·).在更新的sim(·)上进行前驱后继检查的结果是A3~E3也匹配，需加入mat(·)，把这些点及相关的边加入原来的匹配结果图中，即得到新的匹配结果图，如图 4所示.更新后的索引见表 3.

Fig.4 Match result of SubEdges when the edge (E，D) is deleted from P 图 4 P减少边(E，D)后，执行SubEdges得到的匹配结果 Table 3 Index updated by SubEdges when the edge (E，D) is deleted from P 表 3 P减少边(E，D)后，执行SubEdges得到的索引 4 实验与分析

本节将通过实验评估我们提出的PGC_IncGPM算法，使用执行时间作为考察图模式匹配算法的关键技术指标，同时定义改进比率(improved ratio，简称IR)指标，即，提出的算法与传统算法相比执行时间缩短的比率，用于直观反映提出算法的有效性.首先，通过比较GPMS算法和传统的GPM算法，对GPMS算法进行对比评估;然后，对PGC_IncGPM算法和基于GPMS的重新计算(ReComputing)算法进行评估，比较和分析两种算法的执行时间，评估PGC_IncGPM算法的改进比率.由于算法执行时间与模式图和数据图的规模有关，因此我们还考察了模式图规模和数据图规模分别发生变化对PGC_IncGPM算法的执行时间的影响.实验使用两个真实的数据集: Epinions和Slashdot，它们均来自于斯坦福大学的共享数据集()，前者是一个信任网络，有75 879个节点和508 837条边;后者是一个社交网络，有82 168个节点和948 464条边.实验使用的合成数据集为6个不同规模的数据集.所有的数据图上的每个节点都被随机设置一个标签，标签共10种(A~J).在实际应用中，模式图通常不大，在本领域先前的相关研究中，当模式图不变而数据图发生变化时，增量图匹配算法中模式图的规模一般设置为3~8个节点和3~8条边[3].在模式图规模的选取上，我们首先参考之前的相关研究选取了通常规模的模式图;另外，为了验证本文所提出算法的有效性和适用范围，我们还构造了较大规模的模式图进行实验.每次实验中，使用3个不同的模式图，每个模式图边的变化选取5种不同的方式，通过多次图模式匹配实验，取平均结果作为最终的实验结果.

4.1 GPMS算法的执行时间和改进比率

为了评估GPMS算法对传统的GPM的改进，我们在Epinions上对不同规模的模式图(节点个数|Vp|分别为5，6，7，8，初始边数|Ep|按照公式|Ep|=|Vp|1.2选取)使用两种算法分别进行图模式匹配，结果如图 5所示:随着模式图规模的增加，两种算法的执行时间都会增加;但是无论对于哪种情况，GPMS算法的执行时间都比GPM算法的执行时间短;当模式图节点个数分别为5，6，7和8时，GPMS算法的改进比率IR分别达到了27.97%，29.04%， 27.27%和23.08%，平均为26.84%.

Fig.5 Execution time and improved ratio of GPMS algorithm 图 5 GPMS算法的执行时间与改进比率 4.2 PGC_IncGPM算法的执行时间和改进比率

为了评估PGC_IncGPM算法的执行时间和改进比率，分别假设模式图仅增加边、仅减少边和既增加边又减少边这3种情况.首先对通常规模的模式图进行实验，实验中，仅增加边时，模式图P的节点个数|Vp|为6，边数|Ep|为5，分别增加1~4条边后的模式图P+的边数|Ep|为6~9(新增加边数最多达到新模式图总边数的44.4%).仅减少边时，模式图P的节点个数|Vp|为6，边数|Ep|为9，分别减少1~4条边后的模式图P-的边数|Ep|为8~5(减少边数最多达到原模式图总边数的44.4%).既增加边又减少边时，模式图P的节点个数|Vp|为6，边数|Ep|为6.为了平衡考虑增加边和减少边对算法执行时间的影响，假设增加边的数目与减少边的数目相同，因此这种情况下.新模式图边数与原模式图的边数相同，|Ep|维持6不变.实验结果如图 6所示.

Fig.6 Execution time of different algorithms when the edges in pattern graph with normal size are changed 图 6 通常规模的模式图的边变化时算法的执行时间

当模式图仅增加边时，PGC_IncGPM算法只需调用AddEdges子算法.图 6(a)和图 6(b)表示了模式图仅增加边时，PGC_IncGPM算法和ReComputing算法分别在Epinions和Slashdot数据集上的执行时间，图中横坐标为模式图边数的变化，“+1”表示模式图中增加了一条边，“+2”表示模式图增加了两条边，依此类推;柱状图表示两个算法在不同情况下的实际执行时间，折线表示PGC_IncGPM算法相对于ReComputing算法的改进比率.如图所示:对于模式图增加1到4条边的情况，与ReComputing算法相比，PGC_IncGPM算法的执行时间显著减少.例如，对于Epinions数据集，当模式图增加1条边时，ReComputing算法的执行时间为9.5s，PGC_IncGPM算法的执行时间为1.5s，改进比率为84.21%.通过对两个数据集上的实验数据进行统计分析，当模式图仅增加边时， PGC_IncGPM算法的平均改进比率为76.73%.改进的原因分析如下:当模式图中仅增加边时，只需调用AddEdges子算法，算法执行时间分为两部分:第1部分时间用于在GPMS的匹配结果中根据模式图增加的边进行过滤，精简结果图，修改mat(·)，因为结果图相对于数据图规模很小，所以精简结果图的时间相对很短;第2部分时间用于对匹配状态可能受影响的节点根据后继关系重新检测，以更新sim(·)和cand(·)的操作，与Recomputing算法需要在整个数据图中对所有节点计算sim(·)以及在sim(·)上根据前驱和后继反复筛选节点相比，AddEdges子算法需要处理的节点数显著减少，并且不需要根据前驱进行筛选，因此这部分时间也很短.总体来看，PGC_ IncGPM算法获得了明显的执行时间改进比率.

当模式图仅减少边时，PGC_IncGPM算法只需调用SubEdges子算法.图 6(c)和图 6(d)表示了模式图仅减少边时，PGC_IncGPM算法和ReComputing算法分别在Epinions和Slashdot数据集上的执行时间，图中横坐标中“-1”表示模式图中减少了一条边，“-2”表示模式图中减少了两条边，依此类推.如图 6所示，对于删除1到4条边的情形，无论是在Epinions还是Slashdot数据集上，PGC_IncGPM算法在执行时间上均获得了一定程度的优化，平均改进比率为21.13%.与模式图增加边相比，当减少边时，算法对执行时间的改进相对较小，主要是因为:减少边时，除了需要在数据图中对匹配状态可能发生改变的点根据后继关系重新进行检测以更新sim(·)和cand(·)外，还需要在更新的sim(·)上对所有点根据前驱和后继反复筛选，以产生新的mat(·)，这些操作所需时间相当于在一个较小规模数据图上进行模式匹配，与在完整的数据图上进行模式匹配的Recomputing算法相比，尽管数据图规模的减小能够获得执行时间的改进，但是由于数据图规模减小幅度有限，因此执行时间改进比率有限.进一步分析数据可以发现以下现象:PGC_IncGPM算法的执行时间并不是随着减少边条数的增加而线性增加.造成该现象的原因是:随着模式图减少边条数的增加，一方面，算法用于在数据图中修改sim(·)和cand(·)的时间逐渐增加;另一方面，减少边数越多，则P-中边越少，P-中各节点的前驱和后继也越少，因此，对sim(·)中各点根据前驱和后继筛选产生mat(·)的时间越少.综合作用下，PGC_IncGPM算法的总执行时间取决于以上两方面中哪个方面占主导.

图 6(e)和图 6(f)表示了模式图既增加边又减少边时，两种算法分别在Epinions和Slashdot数据集上的执行时间.此时，PGC_IncGPM算法将先调用AddEdges子算法，再调用SubEdges子算法.横坐标中“+n-n”表示模式图增加了n条边，减少了另外n条边，其中，n为1~4.如图所示，对于模式图既增加边又减少边的情形，PGC_IncGPM算法在执行时间上仍获得了一定程度的优化，通过统计在Epinions和Slashdot数据集上的实验数据，算法的平均改进比率为18.33%.模式图既增加边又减少边时，PGC_IncGPM算法的执行时间由AddEdges子算法和SubEdges子算法各自的执行时间共同决定.由于SubEdges子算法执行时间占总执行时间的比例更大，因此，总执行时间的改善比率主要取决于模式图减少边时的改进比率.

从图 6(a)、图 6(b)的实验结果也可以看出，对于仅增加边的情形，随着模式图增加的边的数目的增多，传统的Recomputing算法的耗时逐渐降低，而PGC_IncGPM算法的执行时间逐渐增加.因此，PGC_IncGPM算法的有效性和模式图的变化幅度密切相关.当模式图的变化幅度达到一定的程度时，PGC_IncGPM算法是否仍然能够比Recomputing算法具有更短的执行时间是一个非常重要的问题.为了充分考量PGC_IncGPM算法的有效性和适用范围，我们使用规模较大的模式图做进一步的实验.实验环境设置如下:使用Epinions数据集，固定模式图中节点个数|Vp|为20，逐步增大模式图上增加、减少边的条数，测试PGC_IncGPM算法和Recomputing算法的执行时间，并计算改进比率.实验中，仅增加边时，模式图边数|Ep|为19;仅减少边时，模式图边数|Ep|为39;既增加边又减少边时，假定增加边的条数和减少边的条数相同，模式图边数|Ep|为20.实验中，对于增加边和减少边的条数均从5开始以5为间隔逐步增加直到30，实验结果如图 7所示.

Fig.7 Execution time of different algorithms when pattern graphs with different sizes changed 图 7 较大规模的模式图的边变化时算法的执行时间

从图 7(a)中可以看出:

• 当增加边的条数从5，10，15依次变化到20时，新增加边的数目分别占新模式图总边数的20.83%， 34.48%，44.12%和51.28%;PGC_IncGPM算法的执行时间均小于Recomputing算法的执行时间，改进比率分别为83.16%，68.18%，50%和38.24%，平均为59.89%，改进效果仍很明显.

• 当增加边的条数达到25时，新增加边数达到新模式图总边数的56.82%，此时，PGC_IncGPM算法的有效性达到边界点，其执行时间开始大于Recomputing算法的执行时间，不再适合进行模式图边数继续增加情况下的图模式匹配.

从图 7(b)中可以看出:

• 当减少边的条数逐渐增加到20条时，PGC_IncGPM算法的执行时间均小于Recomputing算法的执行时间，改进比率平均为38.49%.

• 当减少边的条数从20开始继续增加到30时，新减少边数达到原模式图总边数的76.92%，此时， PGC_IncGPM算法的执行时间虽然仍逐渐增加，但是均小于Recomputing算法的执行时间，因此， PGC_IncGPM算法的有效性还未达到边界点.

从图 7(c)中可以看出:

• 当增加的边的条数和减少的边的条数均从5变化到20时，PGC_IncGPM算法的执行时间均小于Recomputing算法的执行时间，改进比率平均为17.48%.

• 当增加的边的条数和减少的边的条数达到并超过25时，PGC_IncGPM算法的有效性达到边界点，其执行时间开始大于Recomputing算法的执行时间.

分析以上结果可知，当模式图变化的边的数目不超过不变的边的数目时，PGC_IncGPM算法均有效.

综上，我们提出的PGC_IncGPM增量算法的应用场景是模式图发生一定幅度变化且变化的边的数目不超过不变的边的数目时的图模式匹配，该类应用场景在现实生活中非常常见，通常发生变化的边的条数比不变的条数少，否则，模式图已经“面目全非”，模式图的根本特性已经被淹没.对于我们的算法，可以接受“模式图中变化的边的数目不超过不变的边的数目”这样的变化幅度，该幅度已经达到了模式图继承原有特性前提下的极限，因此，PGC_IncGPM算法具有很好的实用性和适应性.当模式图发生较大变化(模式图中变化的边的数目超过不变的边的数目)时，新的模式图中从原始模式图中继承的特性已不占主导，这种情况下不再适合使用增量算法.

4.3 模式图规模对算法的影响

为了考察模式图规模对算法执行时间的影响，我们在Epinions上用不同规模的模式图(模式图节点个数|Vp|为6~8)分别进行仅增加边、仅减少边、既增加边又减少边的图模式匹配.实验结果如图 8所示，柱状图中每一个图柱分为两部分:深色部分为PGC_IncGPM算法的执行时间，浅色部分为ReComputing算法比PGC_IncGPM算法多出的执行时间，两部分的和即为ReComputing算法的执行时间.

图 8(a)是模式图中仅增加边时，不同规模模式图下的实验结果，模式图初始边数|Ep|按照|Ep|=|Vp|-1设置.如图所示，随着模式图规模的增大，ReComputing算法的执行时间逐渐增加.因为当模式图规模增大时， ReComputing算法会产生更多的候选匹配集，增加对候选点根据边筛选过滤的次数，导致执行时间变长.PGC_ IncGPM算法的执行时间随着模式图规模的增加可能增加也可能下降，原因如下:当模式图增加边(u，u')时，执行时间取决于两个方面:一个方面是对mat(u)和sim(u)集合中所有点的匹配状态进行检测的时间，模式图规模增大后，mat(u)和sim(u)集合变小，检测的时间变短;另一方面是检查由于模式图变化而导致匹配状态发生变化的节点的祖先节点，这部分的时间取决于u的祖先节点的多少，数目越多，则检查所需的时间越多.最终，执行时间的变化取决于哪个方面占主导.由于在实验中采用常规的树形模式图，增加的边通常在树中的深度较大，图规模越大，则u的祖先节点越多，所以PGC_IncGPM算法的执行时间取决于上述第2方面的影响，随着模式图规模的增大而增加.但是对于增加的边在树中的深度较浅的情况，算法执行时间取决于上述第1个方面的影响，此时，执行时间会随着模式图规模增大而减少.例如图 7(a)中模式图发生“+4”变化，当模式图节点数|Vp|从7变化到8时，由于增加的边深度的较浅，所以PGC_IncGPM算法执行时间反而减小.

图 8(b)是模式图中仅减少边时，不同规模模式图下的实验结果，模式图初始边数|Ep|按照|Ep|=|Vp|1.2设置.如图所示，随着模式图中节点个数的增大，PGC_IncGPM算法的执行时间也逐渐增加.在仅减少边的情况下，PGC_ IncGPM调用SubEdges子算法，先在数据图中对cand(·)中的节点进行检测，判断其是否满足后继匹配，再在更新的sim(·)上，根据前驱和后继进行筛选，以产生mat(·).由于随着模式图规模的增加，sim(·)中节点个数增加，在sim(·)上，根据前驱和后继进行筛选的时间增加，从而导致算法执行时间增加.

图 8(c)是模式图中既增加边又减少边时，不同规模模式图下的实验结果，模式图初始边数|Ep|按照|Ep|=|Vp|设置.如图所示，随着模式图规模的增加，PGC_IncGPM算法的执行时间有增加也有减少的情况.原因是，此时， PGC_IncGPM算法的执行时间由AddEdges子算法和SubEdges子算法各自的执行时间共同决定.随着模式图规模的增大，AddEdges子算法的执行时间可能增加也可能减少，SubEdges子算法的执行时间增加.最终， PGC_IncGPM算法执行时间的变化取决于哪个子算法对执行时间的影响占主导.

4.4 数据图规模对算法的影响

为了测试数据图的规模对算法执行时间的影响，我们固定模式图的变化情况，通过分别修改数据图的节点个数|V|和边密度a(|V|a等于图的边数)两个关键参数改变数据图的规模，考察模式图变化情况下，增量算法在不同规模的数据图上进行图模式匹配的执行时间.设置模式图初始的的节点数和边数都为5，模式图的变化固定为，在模式图中增加两条边并减少另两条边.图 9为数据图规模变化时的算法执行时间和改进比率.

Fig. 9 Execution time of different algorithms over data graphs with different sizes 图 9 不同规模的数据图上算法的执行时间

图 9(a)给出了数据图的边密度a为1.2、节点个数|V|分别为50 000，75 000和100 000时的算法执行时间.如图所示，随着数据图中节点个数的增加，PGC_IncGPM算法的执行时间随之增加.因为当数据图中节点个数增加时，候选匹配集(cand(·)，sim(·))和匹配集mat(·)的规模也增加，使得对已有匹配集和候选匹配集的筛选时间增加，从而算法的执行时间增加.图 9(b)给出了数据图节点个数|V|为75 000，边密度a分别为1.1，1.15和1.2时的算法执行时间.如图所示，随着数据图边密度的增加，PGC_IncGPM算法的执行时间也随之增加.因为数据图边密度增加时，数据图中满足模式图中前驱后继关系的点增加，使得候选匹配集和匹配集规模都随之增加，对已有匹配集和候选匹配集的处理时间相应增加，从而算法的执行时间增加.ReComputing算法的执行时间同样随数据图规模的增大而增加，但增加的幅度大于PGC_IncGPM算法执行时间增加的幅度.随着数据图节点个数和边密度的增加，图 9(a)中，PGC_IncGPM算法的改进比率从64.03%增加到69.15%;图 9(b)中，PGC_IncGPM算法的改进比率从56.18%增加到68.83%.可见，PGC_IncGPM算法在更大规模的数据图上能够获得更加显著的改进比率，因此在大数据图上具有更好的适用性.

5 总 结

本文研究了面向模式图变化的增量图模式匹配算法，提出了PGC_IncGPM算法基本框架.该算法能够在数据图固定不变、模式图发生各种变化时进行增量图模式匹配.在改进传统的图模式匹配算法GPM的基础上，提出了GPMS算法用于在整个数据图上进行图模式匹配，一方面能够建立后续增量匹配所需的索引，另一方面减少了整个数据图匹配的执行时间.设计实现了面向增边的子算法AddEdges和面向减边的子算法SubEdges两个核心子算法，用于增量图模式匹配.选取真实数据集和合成数据集两类数据集进行实验，结果表明:

(1) 与GPM算法相比，GPMS算法能够平均减少26.84%的执行时间.

(2) 与基于GPMS的ReComputing算法相比，当模式图中变化的边的数目不超过不变的边的数目时，PGC_IncGPM算法都能有效减少图模式匹配的执行时间.可见，PGC_IncGPM算法的适用场景是模式图发生一定幅度变化且模式图中变化的边的数目不超过不变的边的数目时的图模式匹配.此时，新的模式图中从原始模式图中继承的特性占主导，PGC_IncGPM算法具有较好的加速效果.

(3) PGC_IncGPM算法在更大规模的数据图上能够获得更加显著的执行时间改进比率，在大数据图上具有更好的适用性.

下一步，我们将研究面向模式图变化的分布式图模式匹配算法.另外，在数据图和模式图同时发生变化的情况下，研究如何进行增量式图模式匹配也是一个非常有意义且具有挑战性的课题，是我们未来的研究方向.

致谢 感谢中南大学信息科学与工程学院计算机软件与理论研究所提供实验平台，感谢国家自然科学基金委员会和湖南省教育厅对本研究的资助.