Abstract
子图查询处理（也称为子图搜索）和子图匹配是许多应用领域中的基本图问题。为解决这些问题制定实际的解决办法，人们已经作出了许多努力。尽管付出了这些努力，但现有的算法在处理大型图和/或许多图时显示出了有限的运行时间和可伸缩性。在本文中，我们提出了一个新的子图搜索算法使用等价的顶点为了减少搜索空间：
(1)静态等价的顶点的查询图，导致一个有效的匹配顺序的顶点；(2)动态等价的候选顶点的数据图，使我们能够捕获和删除冗余的搜索空间。
这些子图搜索技术也导致了一种改进的子图匹配算法。实验表明，我们的方法在查询处理时间上优于最先进的子图搜索和子图匹配算法多达几个数量级。
1 Introduction
在过去的几十年里，由于公开的各种图数据，人们为开发NP-hard图问题的实际解决方案做出了大量的努力[36]。一方面，研究人员已经被激励去开发可伸缩和高效的算法来分析大型图，如社交网络和资源描述框架（RDF）数据。大图最著名的问题之一是子图匹配。给定一个数据图G和查询图q，子图匹配问题是在G中找到所有匹配的q.另一方面，较小的图数据包括蛋白质相互作用（PPI）网络和化合物鼓励研究人员获得快速和可扩展的算法来处理大量的图。子图查询处理（也称为子图搜索）是这些图的集合中的一个众所周知的问题。给定一组数据图和一个查询图，子图搜索是检索D中包含q作为子图的所有数据图。
子图匹配和子图搜索都有多种现实世界的应用：社会网络分析[10,38]、RDF查询处理[20,21]、PPI网络分析[6,31]和化学化合物搜索[46]。然而，这些问题是np困难的，因为它们包括寻找子图同构，这是一个np困难的问题。也就是说，解决这些问题是应用程序的瓶颈。
尽管这两个问题彼此密切相关，但对每个问题的研究直到最近都是单独进行的。现有的子图搜索的工作[4,9,12,22,46,50,51]主要采用索引过滤验证策略： (1)给定一组数据图，数据结构由子结构（即特征）的数据图索引阶段，(2)给定一个查询图q，数据图的特征被过滤在过滤阶段，和(3)子图在验证阶段对每个剩余的候选图进行同构测试。同时，最近对子图匹配[3,13,14,40]的研究提出了基于预处理枚举框架的[3,13,14,40]算法：在查询图和数据图上构建辅助数据结构，并利用数据结构找到查询图的所有匹配情况。这些算法极大地提高了查询处理的性能。研究人员最近利用现有的子图匹配算法有效地解决了子图搜索问题[39]。然而，它在处理大型查询图或许多数据图时显示出了有限的响应时间和可伸缩性。
本文提出了一种新的基于静态等价和动态等价的子图搜索算法来解决其中的局限性。首先，我们将查询顶点的邻域等价性应用于回溯的匹配顺序，从而导致验证阶段的搜索空间更小。其次，我们基于候选数据顶点的邻域等价性，捕获搜索空间的子树的运行时等价性，并剔除搜索空间的冗余性（即等效子树）。此外，我们提出了一种称为邻居安全的高效过滤方法，使我们能够在查询图和数据图上构建一个紧凑的辅助数据结构，以获得尽可能少的候选数据。我们在几个著名的真实数据集和合成数据集上进行了广泛的实验，以比较我们的方法与现有的算法。此外，我们的子图搜索技术反过来导致了一种改进的子图匹配算法VEQM。实验结果表明，该方法在查询处理时间方面比现有的子图搜索和子图匹配算法的性能要好几个数量级。我们的算法、数据集和查询集的可执行文件都是公开可用的。
本文的其余部分组织如下。第2节提供了定义、问题陈述和相关的工作。第3节概述了我们的方法。第4节介绍了我们的过滤技术。第5节描述了我们基于静态等价的查询顶点匹配顺序。6提出了一种利用动态等价性的方法来检测和去除部分搜索空间的新技术。第7节与以前的工作进行了广泛的实验比较。8总结了论文。
2 Preliminaries
在本文中，我们主要关注带有标记顶点的无向连通图。我们的技术可以很容易地扩展到带有标记边的有向图或不连通图。图g =（V (g)，E (g)，Lg）由集合V (g)顶点、集合E (g)边和标记函数Lg： V (g)→∑组成，它为每个顶点分配一个标签，其中∑是一组标签。对于V (g)的一个子集S，诱导子图g[S]表示g的子图，g的顶点集为S，其边集包含E (g)中的所有边，它们在S中都有两个端点。
给定一个图q =（V (q)、E (q)、Lq）和图G =（V (G)、E (G)、LG），q在G中的嵌入是一个映射M：V(q)→V(G)，这样
(1)M(即M (u)≠M（u’），(2)对于每个V（q）中的u，Lq(u)=LG(M(u))，以及(3)（M(u),M(u’)）∈E(G））对于每个（u,u’）∈E (G)。
我们称q是与G同构的子图，用q⊆G表示，如果q在G中存在一个嵌入。一个满足(2)和(3)的映射被称为同态，即，它可能不是内射的。q的诱导子图在G中的嵌入称为部分嵌入。为了便于可追溯性，我们按照在回溯过程中添加到M的顺序枚举部分嵌入M中的映射对。
我们将使用有向无环图（DAG）作为工具来构建q和g的辅助数据结构。给定DAG g，如果顶点没有入边，则是根，如果顶点没有出边，顶点是叶子。如果只有一个根，那么一个DAG g就是一个有根的DAG。设Child (u)表示V (g)中的一组顶点，它们有来自u的输入边。根于u的g的子dag，用gu表示，是g的诱导子图，其顶点是u和u的所有后代。
2.1 Problem statement
子图搜索。给定一个查询图q和一组数据图D，子图搜索问题是找到D中包含q作为子图的所有数据图。即，子图搜索是计算答案集Aq = {G∈D | q⊆G}。
子图的匹配。给定一个查询图q和一个数据图G，子图匹配问题是找到q在G中的所有嵌入。
上述问题与[39]之间密切相关。给定一个查询图q和一组D的数据图，我们可以解决子图搜索问题通过一个修改子图匹配算法，也就是说，对于每个数据图G∈D报告G和终止一旦发现第一个嵌入qG.自子图同构（即，“G包含一个子图同构q？”）是np完备的[11]，这两个问题都是np困难的。
2.2 Related work
子图搜索。许多早期的子图搜索算法都采用了索引-过滤-验证策略。根据算法提取特征[18,39]的方法，这些算法可以分为以下两组。
首先，在特征挖掘方法中，提取了数据图中经常出现的常见特征。gIndex [46]从数据图中提取频繁的子图，并从这些特征中构建一个前缀树。Tree+[50]将频繁的树挖掘到预定的大小，并将它们存储为哈希表。这些方法在索引构建[15,18]中是昂贵的。
其次，达到用户定义大小的所有特性都在特性枚举方法中进行枚举和索引。GCode [51]枚举所有路径，并通过使用这些路径在数据图中生成顶点签名。CT索引[22]枚举树和循环特征，而SING [9]、GraphGrepSX [4]和Grapes [12]列出了所有有界长度的路径。由于数据图的所有特征都是枚举的，因此这些方法中的索引构造需要大量的内存，从而导致索引很大。
上述两种方法的目的是通过使用它们的索引来过滤掉尽可能多的错误答案，以避免探索在验证中没有发现嵌入的错误图的整个搜索空间；然而，这些方法的索引构建通常需要大量的时间和空间。
研究人员最近使用了一种不构建索引的过滤-验证策略。CFQL [39]利用现有的子图匹配算法来加快子图的搜索速度。具体来说，分别采用CFL-Match的预处理技术和GraphQL的搜索方法进行过滤和验证。在没有构建索引的情况下，CFQL优于索引滤波验证算法，得益于现有子图匹配算法的滤波能力和高效的验证技术。
子图匹配。基于乌尔曼的回溯[43]，提出了许多子图匹配算法[3,8,13,14,16,23,37,40,48,49]。这种方法通常工作如下： (1)对于每个查询顶点u，一个候选集C (u)通过过滤过程，其中C (u)是一组候选数据顶点，你可以映射到，和(2)匹配的查询顶点确定，和每个查询顶点迭代映射到一个候选顶点通过匹配的顺序。虽然这些算法是基于这个通用框架设计的，但它们在性能上差异很大，这依赖于过滤方法、匹配顺序和在回溯过程中删除搜索空间的技术。
早期的子图匹配算法如Ullmann [43]、VF2[8]、QuickSI[37]和SPath [49]通过使用考虑顶点邻域的局部过滤器获得候选集；然而，最近的算法如GraphQL [16]、Turboiso [14]、CFL-Match [3]，CECI [2]和DAF [13]在查询图和数据图上构建辅助数据结构，以获得小的候选集。此外，Turboiso、CFL-Match和DAF通过利用辅助数据结构，尽可能精确地估计搜索成本，从而产生有效的匹配顺序。一些算法消除了源于回溯性质的冗余计算（例如，[13]中的失败集）。
[26,27,40]全面地覆盖和研究了最近从几个不同的社区发展起来的各种子图匹配算法。在人工智能中，格拉斯哥子图求解器（格拉斯哥）[28]是专门针对子图同构进行优化的，但它也提供了子图匹配。与其他现有的方法不同，格拉斯哥将子图同构作为一个约束规划问题。
在生物信息学社区，RI [5]提出了一种基于全局匹配顺序的回溯方法。
特别是，Sun和Luo的深入研究[40]是一项开创性的工作，它不仅为有效的子图匹配算法提出了设计指导方针，而且还开发了最快的子图匹配算法（结合了现有算法的不同技术）。因此，我们认为该算法（GQLfs和RIfs）是最先进的方法，在第七节我们的方法与之进行了比较。
有些方法侧重于采用批处理查询处理的子图匹配的综合技术。MQOsubiso [34]计算查询执行顺序，以便可以利用缓存的中间结果。给定一个查询工作负载，WaSQ [25]预先缓存该工作负载的每个查询的嵌入。接下来，给定一个新的查询q，它重用查询工作负载和缓存的嵌入来有效地找到q的嵌入（工作负载感知的子图匹配）。
诱导子图匹配。子图同构在其他领域中有两种不同的定义，如人工智能和生物信息学：非诱导子图同构和诱导子图同构。非诱导子图同构是指在第二节中定义的嵌入。2，这是在数据管理界中常用的子图同构的概念。诱导子图同构还需要非邻接条件（这意味着应该存在一条q的边，它对应于G的匹配顶点之间的每条边）。在这两种定义之间，VF3 [7]、Glasgow和RI主要处理诱导子图同构（或诱导子图匹配）。相比之下，我们的研究主要集中在非诱导子图匹配上。
多路连接。由于一个多路连接可以用一个图来表示，所以许多基于连接的算法都枚举了所有的同态（在Sect中定义）。2)在一个数据图中的一个查询图。虽然嵌入必须是内射的，但同态不需要是内射的，也就是说，同态允许结果中包含重复的数据顶点，而嵌入不包含。
基于最坏情况最优连接（WCOJ）设计了几种最近的图同态算法，即一个运行时间受查询图输出数量限制的连接算法的集合。[1]和图形[17]采用最坏情况最优连接来生成专门为小查询的连接计划。RapidMatch [42]最近提出了一种基于连接的图同态引擎，它可以评估小型和大型查询。研究人员还开发了通过选择查询顶点顺序来优化最坏情况最优计划的方法。具体地说，[29]提出了一个动态规划优化器，它生成计划（通过执行两个较小的子查询的二进制连接或扩展一个查询顶点扩展一个交点的子查询）和一种选择最坏情况下最优子计划的查询顶点顺序的自适应技术。
总结和压缩。图摘要是将图转换为更紧凑的表示，同时保留它们的结构属性或查询的输出。对于子图匹配，SGMatch [35]将查询图和数据图分解为一组图集，并按照其图集的匹配顺序将查询图的图与数据图的相应图进行匹配。
一些压缩范例，如输入压缩和输出压缩，旨在减轻子图匹配中的繁重计算。作为一种输入压缩技术，BoostIso [33,45]通过在预处理中合并对称顶点（在将查询图作为输入之前）来压缩数据图。对于输出压缩，基于顶点覆盖的压缩（VCBC）[32]将输出嵌入到大小大于嵌入的压缩编码中，基于晶体的计算框架（CBF）[32]实现的不是嵌入，而是它们的代码，以降低子图匹配的总体成本。
与上述方法不同，我们的方法采用查询顶点的等价邻域来决定匹配顺序，并在辅助数据结构中基于等价邻域找到等价子树。
3 Overview of our approach
我们首先概述了我们的子图匹配算法，然后对子图搜索进行了修改。
子图匹配。给定一个查询图q和一个数据图G，我们的子图匹配算法包括以下三个步骤。
(i)构建查询DAG。
我们构建了一个查询DAG qD，这是一个由q通过为q中的边分配方向而构建的DAG（例如，图2中它的反向qD−1是查询DAG）。选择标签不频繁且程度大的顶点作为量子D的根，从r进行BFS遍历，构建量子D[13]。我们还在q中的所有1次顶点中找到了邻域等价类（NEC），并将同一NEC中的顶点合并为qD中的单个顶点，其中NEC是一组具有相同标签和的查询顶点同样的邻居[14]。在图2的查询DAG qD中，qD中顶点u5的邻域等价类（即NEC（u5））对应于q中的一个单例集{u5}。
(ii)建设候选空间。
我们在q和G上建立了一个辅助数据结构候选空间（CS）。q和G上的A CS由每个顶点u∈V (q)的候选集C (u)和候选顶点之间的边组成：
(a)对于每个u∈V (q)，都有一个候选集C (u)，它是G中u可以映射到的顶点集。(映射的确切条件在第四章节中描述。)
(b)当且仅当（u，u’）∈E（q）和（v，v’）∈E (G)时，v∈C (u)和v’∈C（u’）之间有一条边。
图3a为图2中q上的CS和图1中的G1。三个候选的v1、v2、v9在C（u1）中，在v2∈C（u1）和v5∈C（u2）之间有一条边。CS是[13]中使用的一种辅助数据结构，但我们的CS构造与[13]不同。我们通过使用扩展的dag图DP（动态规划）和一个附加的过滤函数，利用一个称为邻居安全的概念。 4).如果有任何u∈V (q)使得C (u) =∅，我们不返回任何结果（因为如果有任何空的候选集，就不能在G中嵌入q）；否则继续下一步。
(iii)匹配。
我们通过新的匹配顺序匹配查询顶点u∈V (q)与CS的C (u)中的候选顶点，该匹配顺序是基于u的未映射可扩展候选顶点的数量和NEC (u)的大小(第五节).此外，我们提出了一种新的技术，利用动态等价的子树来去除搜索空间的重复子树。 6).我们还在我们的算法中应用了失败的[13]集。
子图搜索。
在子图搜索的一般框架中，根据给定的数据图集建立索引I。给定一个查询图q、一组数据图的D和索引I，我们可以执行以下步骤，并输出一组答案图的Aq。
（i）使用索引进行过滤。对于I中不包含q的每个特征，带有该特征的数据图将被过滤掉。D中剩余的数据图集用Bq表示。接下来，我们继续对q和每个数据图G∈Bq进行以下步骤。
（ii）构建一个查询DAG。以与子图匹配相同的方式从q构建一个查询DAG qD。
（iii）建设候选空间。对于查询的DAG qD和数据图G，我们采用与子图匹配相同的方法构建CS。
（iv）搜索。与上面的匹配不同，我们在G中找到最多一个q的嵌入。如果在G中找到一个q的嵌入，这一步返回G作为答案；或者没有。
我们在上面将我们的子图搜索算法描述为一个更一般的子图搜索框架，因为我们的技术可以用作索引-过滤-验证框架的过滤和搜索阶段，其中任何索引都可以应用于索引和过滤阶段。基于我们的实证研究，使用索引建立一个现有的索引和过滤会产生相当大的开销，但对大多数查询没有获得更高的过滤能力，这已经被[39]证实；事实上，最先进的子图搜索算法CFQL [39]已经表明，现有的索引方法以及最近的预处理和枚举技术在广泛使用的数据集如PDBS、PCM和PPI的查询处理中效率低下（因此CFQL逐个在多个数据图上运行子图搜索）。因此，我们不使用索引，而将Bq视为数据图的D。然而，可以在出现时利用索引（例如，I/O密集型应用）。
4 Filtering by neighbor-safetdy
在本节中，我们描述了一种动态规划方法与滤波技术相结合，以获得一个紧凑的CS。
假设DAG q的路径树T (q)为树，使得每个根叶路径对应q中不同的根叶路径，并且T (q)共享q的根叶路径的共同前缀（见图2）。将具有v∈V (G)的根DAG q的弱嵌入M定义为T (q)的同态，使M (u) = v。这些概念最初是由[13]提出的。
给定一个CS，我们为u∈V (q)和v∈V (G)定义了一个动态规划（DP）表： D[u，v] = 1，如果v∈C (u)，以及以下必要条件，将嵌入映射到v保持；否则D[u，v] = 0。
(1)在v处存在一个子dagqu的弱嵌入M（即T（qu）的同态，使得M (u) = v）。
(2)对于将u映射到v的嵌入的任何必要条件h（u、v）（条件(1）除外），在CS中都是正确的。（下面我们提出了一个新的必要条件h (u、v）。）
D[u，v]可以使用以下从叶顶点到根顶点的自下而上的递归顺序来计算，即，u在q中的所有子节点被处理后被处理：
其中，一个主函数f（D[uc，·]，v）为1，如果在CS中有vc与v相邻，否则D[uc，vc] = 1；0。在动态规划中比单独应用f更有效。
经过动态规划后，新的候选集计算如下：v在新的C (u)中，当且仅当D[u，v] = 1。（注意，候选集C (u)作为d的紧凑表示）这种优化技术将被称为扩展的DAG-graph DP。让从递归(2)中省略h（u，v）的优化是简单的DAGgraph DP。请注意，DAF [13]使用了简单的DAG-图DP，它只利用了上面的条件(1)。
我们提出一个必要的条件，确认有标签l的v∈C (u)在CS中是足够被映射到u的有标签l的邻居，当一个查询节点v被映射到他的候选v∈C (u)。给定图2的查询图和图3的CS，用标签A将u2映射到v3不足以支撑u2的邻居（例如v1和v2）和标签A。
现在我们定义了一个嵌入的必要条件h。
定义1对于每个顶点u∈V (q)和一个标签l∈∑，一个邻集Nbrq（u，l）是u标签为l的邻集的集合。对于每个顶点v∈C (u)和一个标签l∈∑，一个邻域集NbrCS（u，v，l）被定义为∪un∈Nbrq（u，l）{vn∈C（un）| vn是v，v∈C (u)在CS中的毗邻。
定义2给定一个查询图q和一个q和G上的CS，我们说v∈C（u）是邻居安全的，关于u如果每个标签l∈∑，|Nbrq(u，l)|≤|NbrCS（u，v，l）|。
示例1在图2的查询图q，Nbrq（u2，A）={u1，u4}，Nbrq（u2，B）={u3，u5}，图三a中的CS，NbrCS（u2，v3，A）={v1}，NbrCS（u2，v5，B）={v3,v4,v6}。根据定义2，v3对于u2不是邻居安全的，因为|Nbrq（u2，A）|＞|NbrCS（u2，v3，A）|，而v5对于u2是邻居安全的。
引理1假设我们在q和g上有一个CS。对于每个顶点u∈V (q)，将u映射到一个候选顶点v∈C(u)不能导致q的嵌入。
证明我们用矛盾证明了引理。假设存在v∈C (u)，当映射u到v的嵌入M时，对u是不安全的。因为∈不是邻居安全关于u（例如，存在这样|Nbr顶点∈q（u，l）| > |NbrCS（u，v，l）|），至少有两个不同的ui和ujNbrq（u，l）映射到相同的∈∈NbrCS（u，v，l）M（即M（ui）= M（u j）= vn）。这与在嵌入的定义中，M是内射的条件（即，M（ui）= M（u j）为ui= u j）相矛盾。通过引理1，我们定义了h（u，v），这样h（u，v）= 1，如果v是邻居安全的，否则，h（u，v）= 0。
引理2给定q和G上的一个CS，扩展的|图DP在CS上的时间复杂度为O（|E(q)|×|E(G)|）。
在扩展的dag图DP之前，为每个u∈V (q)和l∈计算一个邻居集Nbrq（u，l）。现在，对于每个u∈V (q)，必须为每个v∈C (u)和l∈计算邻居集NbrCS（u，v，l）。为了做到这一点，对于一个固定的u∈V (q)，我们需要检查v和vn之间的所有v∈C (u)和所有vn∈C（un）的边，其中un∈Nbrq（u，l）的定义为4.1。对于固定的u∈V (q)，所有的邻集Nbrq（u，l）都是不相交的，并且覆盖了u的所有邻集，因此我们在这个计算中只看u的每个邻集un一次。根据∈C (u)的条件(b)，候选∈C（un）和所有的vn∈C（un）之间的边数最多为O（|E (G)|）。 3.因此，对所有u∈V (q)的邻域安全计算需要u∈V(q){deg(u)×O（|E (G)|）} = O（|E (q)||E (G)|）时间。
上述时间复杂度包括邻居安全的计算，但它与[13]中DP的复杂度相同。
一个紧凑型CS的构造。
通过使用上述优化技术，多次使用不同的查询DAG，我们可以过滤尽可能多的候选顶点，从而计算一个紧凑的CS。
在开始时，构造了一个初始的CS。对于每个u∈V（q），C（u）被初始化为顶点集v∈v(G)，如LG (v) = Lq (u)。此外，邻域标签频率（NLF）滤波器[14]可以去除v∈C(u)，这样就有一个满足|Nbrq（u，l）| > |NbrG（v，l）|的标签l∈∑。我们将NLF实现为一个位数组，包含4个|||V(g)|位，以表示每个v∈V (g)和l∈的|||（v，l）|最多4个。因此，它可以用|NbrG（v，l）| < 4过滤v∈C (u)，从而使|Nbrq（u，l）| > |NbrG（v，l）|。图3a说明了图2中的查询图q上的初始CS和图1中的数据图G1。
由于DP是基于一个查询的DAG来执行的，所以我们使用DAG qD及其反向的qD−1（在图2中）来细化候选集。在细化的第一步中，我们使用qD−1对初始CS运行简单的DAGgraph DP。在第二步中，我们通过DAG-图DP进行子图搜索或扩展的DAG-图DP进行子图匹配。在第三步中，我们使用qD−1执行扩展的dag图DP。
示例2给出图2中的qD−1和图3a中的CS，我们首先细化C（u1），然后细化C（u2），以此类推。在对图3b中的C（u1）和C（u2）进行细化后，v3和v4从C（u2）中去除，因为它们对u2是不安全的。因此，在对图3c中的C（u5）进行细化后，v5从C（u5）中移除，因为v5附近没有vc∈C（u2）。在同一图中，v3、v4∈C（u3）对于u3是不安全的，而v5∈C（u3）在inC（u2）中没有邻居，因此它们从C（u3）中移除。
最后，如果存在一个空的候选集，即C (u) =∅，我们就终止。否则，经过多次优化执行，我们得到最终的CS。我们可以通过交替qD和qD−1重复扩展的DAG图DP，直到候选集合没有发生变化，但从我们的实证研究来看，DP的三个步骤就足够了。事实上，[13]实验证实了不需要改进超过三次的事实。
综上所述，VEQ中的扩展DAG-图DP和DAF [13]中的简单DAG-图DP都通过三种改进构造CS，每一种都将DP和查询DAG的反向拓扑顺序处理DP。然而，与简单的DAG-graph DP不同，扩展的DAG-图DP是一个更通用的框架，它可以添加嵌入的任何必要条件。我们采用邻居安全（即定义2）作为这个必要条件。
在VEQ中通过邻居安全过滤和在VF3 [7]中探索可行的部分映射有两个主要区别。首先，当VF3在查询图和数据图上计算可行性集时，我们将邻居安全应用于只保留候选集中存活顶点之间的边的CS。邻居的安全只取决于这些边缘，因此导致高过滤能力，以去除不希望的候选者。其次，VF3在搜索（或枚举）阶段试图扩展部分映射（因为可行性集是从当前部分映射计算出来的）时，会在可行性规则中考虑每个部分映射，但邻居安全是搜索阶段之前使用的一种过滤技术。
邻域集与邻域标签等价类（NLEC）[41]相同。伪星同构约束（PSIC）[41]是一个嵌入的必要条件，它推广了定义2。给定一个Nbrq（u，l）序列，对于1≤i≤|Nbrq（u，l）|，PSIC增量地将该序列中u的第一个i邻域的数（即i）与与v相邻的候选邻域的并集大小进行比较。同时，定义2只比较了|Nbrq（u，l）|和CS中与v相邻的所有候选邻居的并集大小。根据我们的实证研究，PSIC的滤波能力对定义2的提高可以忽略不计。在我们的工作中，我们首先将引理1和dag图DP的滤波方法结合在一个单一的框架中。
邻居安全利用紧凑辅助数据结构CS中邻居的标签频率。这不会给沉重的搜索阶段产生额外的计算开销。（请注意，预处理步骤需要多项式时间，而搜索步骤在最坏的情况下需要指数级时间。）
5 Matching order based on static equivalence
在本节中，我们提出了一种改进的自适应查询顶点的匹配顺序，利用顶点的静态等价性。假设我们试图在搜索过程中扩展部分嵌入M。
查询图q中一个未映射的顶点u在M中被称为可扩展，关于M如果至少有一个邻居的u匹配M，和设置CM (u)的可扩展的候选人u关于M被定义为一组顶点v∈C (u)相邻M（un）CS每个映射的邻居u。我们选择一个可扩展的顶点u作为下一个顶点，并将u与u的每个可扩展的候选顶点进行匹配。
然而，我们的自适应匹配顺序与现有的算法有所不同。最先进的子图匹配算法[3,13]采用叶分解策略，将查询图中的顶点分解为1度顶点集和其余的顶点集，并在将非1度顶点匹配后匹配1度顶点。这种方法通常有助于延迟冗余笛卡尔积[3]；然而，它有时花费不必要的搜索空间，特别是在有小的1度顶点候选点的数量。我们在自适应匹配顺序中考虑了所有的查询顶点，以减少搜索空间。
示例3考虑图2中q的查询DAG qD和图1中的数据图G2。请注意，在g2中没有嵌入q。图4中的搜索树说明了搜索过程。一个节点（u，v）表示一个部分嵌入M的最后一对映射对，让M表示一个节点和一个部分嵌入。一个节点（u、v）！表示映射冲突，即v已经匹配，因此u不能映射到v。设（u，{v1，…，vn}）表示G中的n个顶点与qD中的一个顶点u匹配，其中n个= |NEC (u)|。根据图4a所示的叶分解，在匹配非1次顶点后，匹配叶顶点u5。具体来说，给定一个部分嵌入M = {（u1，v1），（u2，v2）}，我们选择u3作为下一个可扩展顶点，然后匹配u4和u5；然而，没有部分嵌入导致嵌入。因此，将u4和u5与所有可扩展候选对象匹配，会推迟v3处u3和u5的映射冲突，从而导致巨大的冗余搜索空间。
新的匹配顺序。在我们的自适应匹配顺序来选择下一个可扩展的顶点时，我们可以通过允许对1度顶点的匹配顺序的灵活性来节省大量的搜索空间。假设我们正试图扩展一个部分嵌入的M。
-如果有一个一度可扩展顶点u，使|NEC (u)|≥|UM (u)|，其中UM (u)表示CM (u)中u的未映射的可扩展候选集，-如果|NEC (u)| > |UM (u)|，回溯。。
–否则（例如，如果|NEC (u)|=|UM (u)|），则选择u作为下一个顶点。
-否则，如果只有一个可扩展顶点，选择其中一个作为下一个顶点。
-否则，选择一个可扩展的顶点u，使|CM (u)|是非单次顶点中的最小值。
示例4考虑了图4b中新的匹配顺序的搜索树。回想一下，qD中顶点u5的邻域等价类NEC（u5）对应于q中的一个单例集合{u5 (}。给定一个部分嵌入的M = {（u1，v1），u2，v2)}和UM（u5）= {v3}，我们选择u5作为下一个顶点来匹配，因为|NEC（u5）|=|UM（u5）|。在我们将M扩展到M∪{（u5，{v3}）}之后，没有一次可扩展的顶点，所以我们选择u3作为下一个要匹配的顶点。因此，我们可以在不匹配u4的情况下，尽早在v3处检测到u3和u5的映射冲突。
6 Run-time pruning by dynamic equivalence
在本节中，我们开发了一种基于CS中候选顶点的邻域等价性来动态去除搜索树的等价子树的新技术。一旦我们访问一个新节点（即一个新的部分嵌入）M，我们探索子树根于M和回到节点M.利用邻居等价的候选人和知识的探索子树根于M，我们可以删除一些部分嵌入节点的兄弟姐妹M。
定义3 假设我们给定一个q和G上的CS。对于V（q）的节点u和C（u）中的两个候选节点vi和vj，我们说vi和vj共享邻居，如果对于每个q中的u的邻居un，vi和vj在C（un）中有共同的邻居。然后一个cell 派（u，v）被定义为，在CS中和v共享邻居的节点集，v‘属于C（u）。
作为一个新的运行示例，我们使用了图5中的查询图q和数据图G3。注意，v3、v4和v5在G3中有不同的邻居集。两个图之间，CS图6构造，v3v4和v5C（u5）共享邻居在CS（即π（u5v3）=π（u5v4）=π（u5v5）={v3，v4，v5）)，而只有v3和v4C（u2）共享邻居在CS（即π（u2、v3）= π（u2、v4）= {v3、v4}）。
假设在本节的其余部分中，我们在探索了植根于M∪{（u，vi）}的子树后，给出了一个部分嵌入的M，一个可扩展的顶点u∈V (q)和vi∈CM (u)。设TM（u，vi）表示在基于M∪{（u，vi）}的子树中找到的嵌入集合。对于一些未映射的可扩展候选对象vj∈CM (u)，我们的目标是避免探索基于M∪（u，v j）的子树（例如，如果基于M∪（u，vi）的子树和基于M∪（u，v j）的子树是等价的，定义如下）。
定义4给定一个（部分）嵌入M∗，根于M∪{（u，vi）}，（部分）嵌入Ms∗∈TM（u，v j）对称到M∗是M∗−（u，vi）∪（u，vj）如果vj没有映射到M∗；∗−（u，vi），（u’，vj）∪（u，vj），（u’，vi）如果vj在M∗中映射到u’。
定义5在M∪（vi）上的子树和在M∪（vj）上的子树在以下情况下是等价的：
当子树根M∪{（vi）}没有嵌入（即TM（vi）=∅），子树根M∪{(v)}也没有嵌入，当TM（uvi）=∅，对于每个嵌入M∗∈TM（uvi）存在一个嵌入女士∗∈TM（u，v j）对称到M∗，反之亦然。
假设我们给出一个根于M∪{（u，vi）}的子树Ti，以及它对应的子树Tj根于M∪{（u，v j）}，如图7、8和9所示。
图7显示了在Ti中没有发现嵌入的情况。在Ti中，u不能与vi匹配，因为vi已经与u匹配，然后u与vj匹配，但最终在Ti中没有发现嵌入。在Tj中，除了vi和vj的角色交换外。然后将vi和vj包含在负细胞πM−（u，vi）中，其定义见定义6。
图8显示了与图7相似的情况，但在Ti中发现了一个嵌入。即u与vj匹配，在Ti中发现嵌入M∗。Tj的情况与Ti的情况相同，只是vi和vj的角色是交换的。因此，对称嵌入的Ms∗中包含（u，v j）和（u，vi），而不是（u，vi）和（u，v j）。在这种情况下，vi和vj包含在阳性细胞πM +（u，vi）中。
图9显示了在Ti中发现了嵌入的M∗，但在Tj中没有发现对称嵌入的Ms∗的情况。在这种情况下，vi不包括在单元格π（u，v j）中，而vi则包括在Figs的π（u，v j）中。7和8。在Ti中，vi从未被访问过作为u的候选者，因为vi不包括在π（u，v j）中。u与vj匹配，得到嵌入M∗。在Tj中，vi将不作为u的候选者被访问，因为vi不包括在π（u，v j）中。而u将不会与vj匹配，因为vj已经与u匹配，所以将不会找到对称嵌入的Ms∗。如果在Ti中访问的单元格π（u，v j）不包含vi，那么vj就包含在增量集δM（u，vi）中。
现在我们将正式定义保证等价性的条件。
定义6让我（uvi）的所有映射（u，，）冲突(u)6∈厘米(u)子树根于M∪（，），和我（uvi）的所有映射（u，v）访问的子树π（u，v）vi。关于M的负单元格π−M（u，vi）是π（u，vi）∩{∩（u，vi）∈IM（u，vi）π（u，vi）}，如果在子树的vi处至少有一个映射冲突；否则π（u，vi）。A positive cell πM +(u, vi) regarding M is πM −(u, vi) − δM (u, vi) where delta set δM (u, vi) = ∪(u ,v )∈OM (u,vi)π(u , v ).关于M的等价集πM（u，vi）的定义如下：
到节点M∪（u3，v9），在探索了基于M∪（u3，v9）的子树之后，M=（u1，v1），（u2，v3），（u4，v8）。关于M的等价集πM（u3，v9）是π−M（u3，v9）= π（u3，v9）= {v8，v9，v10}，因为在v9处不存在映射冲突。M∪{（u2，v3）}M={（u1v1）}，有一个映射冲突v3后的探索子树根于M∪{（u2v3）}没有嵌入发现，因此πM（u2v3）πM−（u2v3）=π（u2v3）∩π（u5v3）={v3，v4}。
例6（正单元格）作为图10搜索树中的一个具体例子，假设我们在探索了M∪（u4，v10）之后，在M∪（u4，v10）之后，回到M = {（u1，v2），（u2，v6）}。在勘探过程中没有出现映射冲突，πM−（u4，v10）为π（u4，v10）= {v10，v11，v12}。在这次探索中，我们还访问了一个映射（u3，v11），这样π（u3，v11）v10，因此πM+（u4，v10）=π−M（u4，v10）−δM（u4，v10）= {v10，v12}，其中δM（u4，v10）= π（u3，v11）= {v11}。由于我们在勘探过程中发现了嵌入物，所以πM（u4，v10）就是πM +（u4，v10）。
现在我们声称等价集πM（u，vi）导致了每个vj∈πM（u，vi）的M∪{（u，v j）}的子树之间的等价性。
引理3对于每一个vj∈πM（u，vi），根于M∪{（u，vi）}的子树和根于M∪{（u，v j）}的子树是等价的（即，πM是保证等价性的条件）。
对vi成分的证明。∈C (u)和vj∈C (u)，我们需要遵循
(i)C(u）中的两个候选者vi和vj共享邻居。
（ii）对于在M∪（u，vi）的子树中与u发生冲突的顶点u，存在vj∈C（u）与vi∈C（u）共享邻居。
（iii）对于基于M∪（u，vi）的子树中映射到vj的每个顶点u，存在vi∈C（u）与vj∈C（u）共享邻居。
vi和vj在πM（u，vi）中的事实可以重写如下。
-如果TM（u，vi）=∅，(i)和（ii）保持。–否则，(i)、（ii）和（iii）持有。
设TM（u，vi）TM（u，v j）表示对于每个嵌入M∗∈TM（u，vi）都存在一个对称于M∗的嵌入Ms∗∈TM（u，v j）。那么子树的等价性的定义可以描述如下。
-如果为TM（u，vi）=∅，则为TM（u，v j）=∅，即TM（u，vi）TM（u，v j）。–否则，TM（u，vi）TM（u，v j）和TM（u，vi）TM（u，v j）。
我们用矛盾法证明了该引理，即如果TM（u，vi）TM（u，v j），则vj/∈πM（u，vi）。设u是第一个与u具有相同标签的查询顶点，如果存在这样的顶点，则以匹配的顺序出现在u后面；否则。
假设TM（u，vi）TM（u，v j），即存在一个嵌入M∗∈TM（u，v j），在TM（u，vi）中不对称。也就是说，在根于M∪{（u，vj）}的子树中存在一个部分嵌入M2，导致M∗，但对称于M2的部分嵌入M1必须不存在于根于M∪{（u，vi）}的子树中，或者永远不会导致嵌入在TM（u、vi）中。假设M1 = M∪{（u，vi），…，（u，v j）}和M2 = M∪{（u，v j），…，（u，vi）}如果u=u；M1 = M∪{（u，vi）}和M2 = M∪{（u，v j）}否则。在u及其候选的vn∈C（un）中存在一个邻居un，使得M2扩展到一个不能被M1扩展的映射（un，vn）。这意味着vj∈C（u）与vn∈C（un）相邻，而vi∈C（u）不相邻，这与vi，v j∈C（u）共享邻居相矛盾，即，该声明与条件（ii）如果u=u；条件(i)如果u=u。
假设TM（u，vi）为TM（u，v j）。与上述相同，这个假设导致与条件（iii）如果u=u；条件(i)如果u=u。
示例7（通过负单元格进行修剪）再次考虑图10中的搜索树。当我们回到节点M∪{（u3v9）}M={（u1v1），（u2v3），（u4v8）}后的探索子树基于M∪{（u3v9）}，我们找不到任何嵌入的q，没有映射冲突v9在探索。因此，无论πM（u3，v9）中的哪个顶点与u3匹配，它都不会导致q的嵌入，因为所有可能的扩展都将以同样的方式以失败告终。因此，我们不需要为每个vj∈πM（u3，v9）扩展节点M∪{（u3，v9）}的兄弟节点M∪{（u3，v j）}。类似地，假设我们在探索了节点M∪{（u2，v3）}之后，回到了其中M = {（u1，v1）}。我们找不到q的任何嵌入，在勘探过程中在v3处有一个映射冲突，所以πM（u2，v3）= {v3，v4}。这意味着根于M∪{（u2，v4）}的子树将与根于M∪{（u2，v3）}的子树相同，除了映射冲突发生在（u5，v4）而不是（u5，v3）。因此，M∪{（u2，v4）}不会导致嵌入，因此我们不需要扩展节点M∪{（u2，v3）}的兄弟M∪{（u2，v4）}。
示例8（通过阳性单元格进行修剪）请再次考虑图10中的搜索树。假设我们探索了根于M∪{（u4、v10）}的子树，其中M = {（u1、v2）、（u2、v6）}，并回到节点M∪{（u4、v10）}。我们在TM（u4，v10）中发现了两个嵌入，得到了πM（u4，v10）= {v10，v12}，这意味着M∪{（u4，v12）}将导致对每个M∗∈TM（u4，v10）的嵌入对称，即相同的嵌入如M∗∈TM（u4，v10），除了u4被映射到v12。注意，v11∈CM（u4）不在πM（u4，v10）中，因为我们可能由于u4和u3在v11处的映射冲突，没有发现任何从M∪{（u4，v11）}扩展出来的嵌入。
搜索过程。算法1中的匹配是我们在CS中找到所有q嵌入的搜索过程。如果|M|=|V（qD）|（第1行），我们报告M作为q的嵌入；否则，我们在第3行选择一个可扩展的顶点（||=0首先选择qD的根顶点），对于每个未访问的v∈CM (u)，将当前的部分嵌入M扩展到M‘=M∪{（u，v）}，并递归地执行与M的匹配（第5-24行）。然而，我们的回溯过程不同于现有的算法如下。
一方面，我们根据新的自适应匹配顺序，在多个可扩展顶点中选择下一个可扩展顶点u。5（第3行）。更多的另一方面，引理3的剪枝技术是v∈CM (u)，v被初始化为“不等价”（第4行）。让eqM(u, v)为πM(u, v)中的顶点。中的顶点，该顶点已经在M的扩展中与u匹配。M. 对于每个未访问的候选者v∈CM（u），我们报告一个嵌入Ms∗∈TM（u，v）对称于M∗的每个嵌入M∗从M∪{(u, eqM (u, v))}扩展而来，并且如果v∈CM（u）是等价的，则转到第5行（第7-9行）；否则，初始化πM-(u, v)和δM (u, v)，并更新δM (u , v )为搜索树中(u, v)的每一个祖先(u , v )更新δM，以便的每一个祖先(u , v )更新δM (u , v )，使va /∈π(u, v)和π(ua, va) ∩π(u, v)=∅。递归调用匹配（第12-14行）。在递归调用匹配之后，πM表示πM−（u，v），如果子树中没有嵌入πM∪（u，v）}；πM +（u，v）= πM−（u，v）−δM（u，v），否则（第17-18行）。接下来，我们让eqM（u，v）为v，并将“等价”设置为πM（u，v）中的每个v（第19-21行）。如果v已经被访问（第22行），则会发生M−1(v)和u在v处的映射冲突，因此我们更新一个负细胞πM−p（M−1(v)，v）（第23-24行）。
子图搜索，我们修改算法1，这样它发现一个嵌入q在每个G∈∈首先，我们终止并返回真一旦找到第一个嵌入m，一个可扩展的顶点u和一个未访问的可扩展候选人v∈厘米(u)，v是等价的，我们去第5行（第8行删除）。最后，不再需要δM（u，v）的计算（第13-14行被移除）。
引理4给定一个顶点u∈V (q)和可扩展候选项的集合CM (u)，计算所有v∈CM (u)的单元格π（u，v）的时间复杂度为O（deg(u)|V (G)||CM (u)|）。证明我们可以通过CM (u)数组上的分治范式获得细胞π（u，v）：(1)选择一个新的轴候选vn∈u邻居un（un），(2)分区元素数组的两个子数组根据每个元素v∈CM (u)是否邻居的c，和(3)重复每个子数组的步骤，直到子数组是一个单例或所有可能的枢轴vn∈C（un）为所有邻居u检查。在q中有u的deg (u)个邻居。对于u的每个邻居un，在所有v∈CM (u)的C（un）中都有O（|V (G)|）邻域。因此，所有可能的枢轴的数量为O（deg(u)|V (G)|）。因此，计算所有v∈CM (u)的单元格π（u，v）的时间复杂度为O（deg(u)|V (G)||CM (u)|）。
在实现中，不需要为每个u∈V (q)和v∈C (u)计算π（u，v），因为一个人只能访问发现一些v∈C (u)，并在子图搜索中嵌入（或一些子图匹配中嵌入）后终止。因此，细胞不是在CS构建后计算CS中的所有候选细胞的，而是在第一次计算v∈CM (u)时计算CM (u)；事实上，为所有v∈CM (u)计算细胞π（u，v）需要合理的时间，因为|CM (u)||C (u)|。我们使用单元格id来实现实现效率和更好的表示。在实现中，我们将每个不同的单元格与一个唯一的ID关联起来。一旦获得了π（u，v），每个v∈C（∈）的ID，这样v∈π（u，v），因此当以后访问v∈C (u)时，π（u，v）可以通过ID重用和访问。对于一些候选的v∈π（u，v），一旦我们计算πM（u，v），我们将v∈πM（u，v）标记为“等价的”，这样只要当前的部分嵌入M保持不变，我们就可以重用πM（u，v）。
7 Performance evaluation
在本节中，我们评估了子图搜索和子图匹配的竞争算法的性能。所有的源代码均来自之前论文的作者，并在C++中实现。实验在一台运行CentOS的机器上进行，该机器有两个IntelXeonE5-2680v3 2.5 GHz cpu和256GB内存。
由于这些问题是np困难的，算法不能在合理的时间内处理一些查询；因此，我们为每个查询设置了10分钟的时间限制。如果算法在时间限制内不处理查询，我们将查询的处理时间视为10分钟。我们说在时间内完成的查询被解决。每个查询集由100个查询图组成。对于每个查询集，我们测量在之前的工作[13,18,39]中常用的度量的平均值：
- 假阳性率FPq=|Cq|−|Aq||Cq|查询图q：我们评估子图搜索算法的过滤能力，其中Cq是q过滤后剩余数据图的集合，Aq是q的答案图的集合。
- 辅助数据结构的大小：我们测量候选集的大小之和，即u∈V(q)|C(u)|，以评估子图匹配算法的有效性。
- 查询处理时间：我们测量子图搜索的过滤时间和验证时间之和，或者子图匹配的预处理时间（即构建辅助数据结构的时间）和搜索时间（即枚举前105个嵌入的时间）之和。为了进行合理的比较，我们计算了处理由至少一种竞争算法求解的查询图的平均时间。
- 过滤时间与验证时间的比：这显示了查询处理时间占多少过滤或验证时间。
尽管诸如Grapes等子图搜索的索引过滤验证方法显然在索引数据集上花费了大量的时间和空间，但索引时间和索引大小将不会被视为评估的度量，因为所有其他子图搜索算法都没有索引地处理查询。
7.1 Induced versus non-induced
“诱导”子图匹配和“非诱导”子图匹配是不同的问题。这两个问题中的哪一个更难解决？由于不同的算法使用不同的技术，因此通过比较不同的算法并不容易回答上述问题。幸运的是，RI [5]和Glasgow [28]同时解决了诱导和非诱导子图匹配问题，因此我们试图通过测量这些算法在诱导和非诱导问题中的搜索空间和查询处理时间来回答上述问题。我们在实验中加入了VF3 [7]和VEQM作为参考。
图11显示了这些算法的搜索空间的大小（即搜索树中的节点数）和查询时间，其中(I)和(N)分别表示“诱导的”和“非诱导的”。在这个实验中，我们只运行每个算法在10分钟的时限内找到所有匹配的查询，以便我们可以测量搜索空间的大小。RI (N)和Glasgow (N)的搜索空间分别比RI (I)和Glasgow (I)大得多，说明非诱导子图匹配是比诱导子图匹配的搜索空间更大的问题。因此，诱导算法与非诱导算法之间的搜索空间的差距导致了它们之间的查询处理时间的差距。VEQM的性能始终优于其他非诱导算法。因此，即使对于同一算法，这两个问题也显示出显著的困难差距。因此，在接下来的实验中，我们主要将我们的算法与非诱导子图搜索或子图匹配算法进行比较。
7.2 Subgraph search
由于CFQL [39]明显优于现有的子图搜索算法，而Grapes [12]在现有的索引-过滤-验证算法[18,39]中查询处理速度最快的，因此我们选择这两种算法与我们的子图搜索算法VEQS进行比较。此外，我们修改了最先进的子图匹配算法DAF [13]来解决子图搜索，并将其（在本节中称为DAFS）包括在我们的比较中。真实数据集。实验在真实数据集上进行，其中[12,18,39]中使用的PDBS，PCM，PPI，和IMDB，REDDIT，由[47]提供。PDBS是一组代表DNA、RNA和蛋白质的图表。PCM是一套氨基酸的蛋白质接触图。PPI是一个蛋白质-蛋白质相互作用网络的数据库。IMDB是一个电影协作数据集。REDDIT是一个在线讨论社区的数据集，而协作”是一个科学协作数据集。由于没有关于IMDB、REDDIT和合作的标签信息，我们随机分配了一个标签每个顶点都有10个不同的标签。表2总结了这些数据集的特征。
查询集。为了检验这些算法，我们采用了两种与以往研究相似的查询生成方法，即随机游走[18,39]和宽度优先搜索（BFS）[39,44]。对于每个数据集D，我们生成8个查询集QiR（即随机游走）和QiB（即BFS），其中i∈{8,16,32,64}是一个查询图的边数。通过随机游走方法生成查询图如下： (1)从随机选择的图G∈D中均匀随机选择一个顶点；(2)从选定的顶点进行随机游走，直到我们访问i条不同的边，从中提取一个带有这些边的子图。在BFS方法中，我们从选定的顶点执行一个BFS，直到我们访问i条不同的边。
假阳性比率。图12显示了真实数据集上的子图搜索算法的假阳性率（collab的Q64R中的假阳性率缺失，因为除了VEQS之外，没有任何算法在时限内完成COLLAB的Q64R中的任何查询）。DAFS在过滤假答案方面最差，但在大多数查询集中，平均假阳性率小于0.1。假阳性比的很大提高源于利用邻居安全的扩展dag图DP。查询处理时间。图13显示了这些算法的查询处理时间的算术平均值。VEQS通常是最快的（除了一些小尺寸的查询集），这不仅是因为扩展的DAG-graph DP获得的假阳性答案更少，而且由于动态等价缩小的基于静态等价的匹配顺序的搜索树也更小。VEQS比DAFS快两个数量级，比CFQL快3个数量级。在IMDB的Q32B中，VEQS比葡萄高出5个数量级。然而，VEQS的查询处理时间略大于CFQL Q8R和Q8B PDBS，PCM，PPI因为嵌入一个小的查询图可以很容易地找到所有的算法，因此利用扩展DAG-graph DP或修剪技术VEQS可能招致开销。
每个算法的查询处理时间根据查询图的大小和数据集的特征而有很大的变化。一般来说，VEQS和其他图之间的性能差距会随着查询图大小的增大而增大。虽然grap显示了在PDBS上的性能稳定，但其查询处理时间随着查询图大小的增长而呈指数增长。在除PDBS之外的所有数据集的CFQL结果中，也可以观察到大型查询的查询处理时间的峰值。然而，DAFS在稀疏数据图REDDIT和PDBS中需要几乎恒定的查询处理时间，并且比在其他的CFQL和PDBS中显示出更稳定的性能。除了PPI（最大的数据图）和协作（大量最密集的数据图）外，随着所有数据集的查询图大小的增加，VEQS的查询处理时间保持稳定。
些结果来源于过滤时间与验证时间的比值，如表3所示。对于所有的竞争算法，验证在最坏的情况下需要指数级时间而滤波需要多项式时间。实际上，在表3中，Grapes花费了大部分的查询处理时间来验证候选图，这降低了整体性能。CFQL的验证时间占了除PDBS外的大部分查询处理时间。虽然DAFS的验证时间在PPI、IMDB和COLLAB上占其查询处理时间的60%以上，但验证时间的比例始终小于CFQL。不像其他的算法，VEQS花费的验证时间少于或与过滤时间相当，这证实了它比其他过滤时间的性能更稳定。为了进一步量化和分析查询之间的性能差距，我们在图14中测量了查询处理时间的几何平均值。我们还在图15中给出了查询处理时间的分布情况。对于每个算法，每个数据集上的查询都按图15中该算法的查询处理时间的升序进行排序。查询处理时间的分布和算法的行为因数据集而异。在PDBS中，每个算法的查询处理时间都在逐渐增加。在IMDB和PCM中，由于VEQS的开销，对于大约80%的查询，CFQL和DAFS的查询处理时间都小于VEQS。(图中CFQL和DAFS的几何平均值小于VEQS的几何平均值，证实了这一结果。 14.)相比之下，VEQS对大多数查询显示了相对恒定的查询处理时间，不像其他的查询处理时间急剧增加硬查询。在REDDIT中，Grapes和CFQL提前达到了硬查询的时间限制，而VEQS则显示出稳定的性能。对于PPI和COLLAB，所有的算法都有非常困难的查询，其查询处理时间超过了时间限制（即10分钟）。葡萄首先达到时间限制，然后DAFS达到极限，然后是CFQL。同时，VEQS只有少数查询的运行时间超过了时间限制。敏感性分析。我们通过改变一组D的数据图的几个特征来评估算法。我们使用演化图[30]升级PPI的最小数据图（有2008条边），生成每个数据图G∈D，并根据幂律分布为顶点分配标签。我们改变了以下参数：
-在： 10、20、40、80中不同标签的数量
-在D： 2、4、8、16中数据图的比例因子s
-在D： 102、103、104、105中数据图的数量
s表示|E (G)|倍大于输入数据图的|倍，而演化图通过相应地增加|V (G)|来保持G相同的统计特性。与现有的工作[18,39]类似，我们将| | = 20、s = 2和|D| = 103设置为默认值；事实上，我们选择s = 2，以便默认的|V(现有工作的压力测试。如果未指定，则参数被设置为其默认值。我们在每个数据集d上使用查询集Q16R和Q16B。假阳性比率。这些算法在合成数据集上的假阳性率显示在图16的左列。由于内存使用过多，Grapes无法完成使用s = 16或使用|D| = 105的数据图的索引。VEQS在假阳性比率方面始终优于其他公司。总的来说，假阳性率随着不同标签数量的增加而减少，因为顶点上有更多的不同标签，使算法能够提取不同的特征或获得更少的候选特征，从而导致过滤更多的错误答案。随着数据图的大小（即比例因子s）的增大，假阳性比率通常也会降低，特别是对于随机游走查询集。
查询处理时间。算法对合成数据集的查询处理时间如图17右列所示。查询处理时间随着不同标签数量的增加而减少，因为我们可以通过利用更多的标签来过滤更多的数据图，并验证更少的候选图。查询处理时间随着数据图的增加而增加，因为验证假阳性数据图的时间可能会显著增加。时间也会随着数据图数量的增加而增加，因为更多的假阳性答案可能会以指数级增加验证时间。
综上所述，VEQS在过滤错误答案方面优于其他算法，并且在验证中占用的查询处理时间较少。我们观察的实验验证通常需要更多的时间在一个假阳性的答案比一个答案，因为一个算法必须探索整个搜索空间来验证没有嵌入假阳性图而终止一旦发现一个嵌入答案图。因此，假阳性答案的数量越少，探索整个搜索空间的尝试就越少。然而，在验证阶段，在答案图中找到一个嵌入物有时会花费很多钱。因此，一种更先进的验证技术可以通过避免频繁的回溯，快速地找到在答案图中嵌入查询图。因此，降低假阳性答案（通过具有邻居安全的扩展dag-grapDP）和减少搜索空间（通过基于静态等价匹配和动态等价运行时修剪）可以缩短验证时间，从而显著提高整体性能。
7.3 Subgraph matching
为了评估我们的子图匹配算法VEQM的性能，我们将VEQM与来自数据管理社区的最近的子图匹配算法CFL-Match [3]、DAF [13]、RIfs [40]和GQLfs[40]以及来自AI社区的格拉斯哥[28]进行了比较。
数据集。我们用表4中的真实数据集来测试算法，这些数据集在以前的工作中被广泛使用[3,13,14,23].酵母、HPRD和人类是蛋白质-蛋白质相互作用的网络。电子邮件通信网络和DBLP协作网络来自斯坦福大型网络数据集收集[24]。YAGO是一个RDF数据集。
查询集。我们使用与[3]和[13]相同的实验设置。我们生成稀疏查询集Qi S和非稀疏查询集Qi N，其中i是查询图中的顶点数，这样对于酵母和HPRD的i∈{50、100、150、200}，其余数据集的i∈{10、20、30、40}。Qi S和Qi N中的每个查询图的平均度分别为≤3和>3。查询图的生成如下： (1)均匀随机选择一个顶点，(2)对数据图进行随机游走，直到我们访问i个不同的顶点，(3)提取一个子图，包含访问的顶点和这些顶点之间的一些边。辅助数据结构的尺寸。为了评估我们的CS与最优的距离，我们比较了我们的CS和Steady的大小。稳态重复精炼C (u)达到一个稳定状态，其中对于每个v∈C (u)和u∈(q)，v满足以下约束：对于一个邻域u，C（u）和一组v的邻居至少有一个共同的顶点。采用稳态作为[40]中的最优CS。
图18显示了每个算法和Steady的辅助数据结构的平均大小。其规模越小，算法的搜索空间就越小。辅助数据结构的大小会随着查询图的增大而增大。由于扩展的DAG-图DP具有邻居安全性，VEQM始终比DAF和CFL-Match的候选数据数量更少。
在大多数查询集中，在我们扩展的dag图DP后剩余的候选数量略大于Steady，但有时小于稳态，因为弱嵌入和邻居安全（即我们的过滤条件）的结合略强于Steady的过滤条件。与DAF中的CS大小相比，扩展的DAG图DP在酵母和电子邮件中减少了10%以上，在DBLP中减少了20%；事实上，DAF只使用简单的DAG图DP，所以对于每个u∈V (q)，VEQM的CS中的C (u)是DAF的一个子集。
图19显示了扩展的DAg图DP、CFL-Match、DAF和Steady的过滤时间。一方面，延伸由于邻居安全计算，DAG-graph DP通常比CFLMatch或DAF花费更多的时间，但这反过来会在合理的时间内产生更紧凑的CS（除YAGO外，大多数情况下，<为10 ms，YAGO中约为100 ms）。另一方面，扩展的dag图DP比Steady快三个数量级以上（因为我们的过滤使用了三次细化，而Steady无限期地使用它们）。结果表明，VEQis的滤波方法足够快，可以在实际应用中使用，同时得到了接近Steady的大小。
查询处理时间。图20显示了这些算法的平均查询处理时间。格拉斯哥的DBLP和YAGO上的内存不足。由于前面几节中描述的三种主要技术，VEQM的性能通常优于GQLfs和RIfs，其次是DAF、CFL-Match和格拉斯哥。特别是，VEQM在人类Q40S中比RIfs强三个数量级，在酵母Q50S、人类Q40S、Q40N和DBLP中比GQLfs强两个数量级。在酵母、电子邮件、DBLP和Human的许多查询集中，VEQM比CFL-Match和DAF快超过3个数量级。与VEQS不同的是，VEQM在一个数据图中搜索多个嵌入，因此它可以通过使用等价集同时输出大量的对称嵌入。但是，由于在HPRD和Email的一些查询集中，由于扩展的HPRD图DP的开销和等价集的计算，VEQM的查询处理时间略高于其他查询处理时间。例如，HPRD体积小，有许多不同的标签，因此，HPRD的大多数查询在100 ms内完成，这意味着它们对于所有算法都是简单的实例。
图21展示了所有算法的查询处理时间的分布（该分布比几何平均值更能反映查询之间的性能差距，因此这里只给出了该分布）。对于每个算法，它的查询处理时间按升序排序，以便更快（或更容易）的查询更早出现。对于酵母、电子邮件、DBLP和Human，VEQM在处理简单查询方面比CFL-Match和DAF花费更多的时间，因为VEQM在过滤和修剪方面有计算开销；然而，VEQM在硬查询方面比其他的性能更好。特别是在酵母和人类中，每个算法都以不同的百分比达到时间限制。CFL-Match首先达到时间限制，其次是格拉斯哥和DAF，而VEQM在最右边的几个查询中几乎没有接近顶部，其次是运行正常的GQLfs。此外，VEQM甚至没有达到Email和DBLP的时间限制，即VEQM的查询处理时间通常是稳定的。对于简单的数据集HPRD，DAF和CFL-Match对于大多数查询比VEQM花费更少的时间。相比之下，VEQM在查询处理时间上通常是稳定的，而对于硬查询，其他算法的运行时间会逐渐增加。在YAGO中，VEQM对于大多数查询都是最快的。对于硬查询，VEQM的运行时间逐渐增加，而其他查询的运行时间则急剧增加。
由于我们在数据图中找到了针对子图匹配问题的大量嵌入，所以除HPRD外，所有数据集中的搜索时间所花费的时间都远远超过预处理时间。在预处理搜索方法中，VEQM和GQLfs在搜索阶段平均花费68%的查询处理时间，而RIfs、DAF和CFL-Match的查询处理时间分别为72%、93%和96%。因此，我们获得紧的候选集和减少搜索空间的策略得到了一种有效的子图匹配算法。
7.4 Comparison with a workload-aware algorithm
我们在实验中比较了VEQM和WaSQ [25]。请注意，我们的工作和WaSQ解决了不同的问题。WaSQ解决了工作负载感知的子图匹配，即给定一个查询工作负载（一组查询），WaSQ预先缓存工作负载的每个查询的嵌入，然后给定一个新的查询q，它重用查询工作负载和缓存的嵌入来有效地找到q的嵌入。
图22为WaSQ和VEQM的查询处理时间。与我们工作中的其他实验一样，我们为每个查询设置了10分钟的时间限制。由于WaSQ将一个查询工作负载作为输入，因此我们为包含100个查询的每个查询工作负载，将WaSQ的时间限制设置为1000分钟。图中的空条表示WaSQ没有在时间限制内完成。尽管WaSQ重用了以前的查询结果，而VEQ没有重用，但在大多数情况下，VEQM的性能都优于WaSQ或可以与WaSQ相当。
现代图查询处理系统建立给定数据图的数据库，以有效地找到图24EmptyHeaded和VEQM的查询处理时间。x轴上的T、L、B分别表示三角形、棒棒糖、杠铃查询，例如，THPRD表示HPRD固定模式中的三角形查询。有些系统是专门为SPARQL查询或批处理查询而设计的。因此，我们的方法可以应用于图形处理系统以两种方式： (1)信息（例如，邻居标签频率或特定子结构如三角形）发现数据图可以计算和存储之前查询图，和(2)我们的方法可以扩展到多个查询处理或RDF查询处理。
7.5 Comparison with join-based algorithms
在本小节中，我们将VEQM与现有的基于连接的子图查询引擎进行比较，如经验[1]、图形流[29]和快速匹配[42]。这些算法来自于DBMS中的连接操作，因为一个多路自然连接可以用一个图来表示，其中一个属性和一个关系分别对应于一个顶点和一条边。经验头、图形流和快速匹配的源代码可以在GitHub上公开获得。
图23显示了图形流、快速匹配(H)（用于查找同态的快速匹配）、快速匹配(E)（用于查找嵌入的快速匹配）和VEQM的查询处理时间。图流不包含在HPRD和YAGO的结果中，因此图流不能生成子图目录。总的来说，VEQM的性能优于其他的，而且它在大型图形中扩展得很好。在酵母中，VEQM的表现一直优于其他的。在人类实验中，VEQM始终领先于执行图形流和快速匹配(E)。在电子邮件、DBLP和YAGO中，VEQM在大型查询方面的性能优于其他VEQM。对于除酵母之外的数据集上的一些小查询，RapidMatch (H)通常比VEQM表现得更好，因为RapidMatch (H)搜索的同态与嵌入不同，不一定是内射的(见第二节。2)，因此，RapidMatch (H)可能比搜索嵌入的VEQM需要更小的搜索空间来发现一个小的（或简单的）查询图的前105个匹配项。
图24显示了“经验”和“VEQM的查询处理时间。由于经验在码头容器中运行，VEQ也在同一容器中进行了实验。empty头没有针对大型复杂图查询[1]进行优化，因此我们使用了[1]中使用的三个代表性查询（即三角形、棒棒糖和杠铃查询），这些查询可以通过经验头的最坏情况最优连接有效地处理。x轴上的T、L和B分别表示三角形、棒棒糖和杠铃查询，例如，THPRD表示对HPRD的三角形查询。在这里，我们运行VEQM来查找查询图的所有嵌入。在大多数情况下，VEQM比经验占用的查询处理时间更少。
7.6 Effectiveness of individual techniques
在本小节中，我们将评估单个技术在减少总体查询处理时间方面的有效性。我们运行DAF和以下算法的变体来衡量每种技术所获得的性能增益：
-DAF：用于比较的基线。
–VEQS-NS：采用简单的dag图DP进行过滤，基于静态等价进行匹配顺序，通过动态等价进行运行时剪枝。
–VEQM-SEQ-DEQ：在滤波中使用具有邻域安全性的扩展DAG-图DP，在回溯中使用DAF的自适应匹配顺序。
–VEQM-DEQ：使用扩展的dag图DP和基于静态等价的匹配顺序。
-VEQS和VEQM：利用扩展的dag图DP，建立基于静态等价的匹配顺序，并通过动态等价进行运行时剪枝。
图25显示了这些算法对子图匹配的查询处理时间。
邻居安全的有效性。对于子图匹配问题，VEQM-SEQ-DEQ将酵母的Q50S、电子邮件的Q40S Q30N和酵母的Q100N的DAFM提高了两个数量级。我们计算每个查询图q的最大mq=maxu∈V(q)，l∈|Nbrq（u，l）|。性能提高最大的前10个查询图的平均mq远远大于所有查询。也就是说，当查询图中存在具有更多具有相同标签的邻居的顶点时，性能增益更大，因为邻居安全条件可以利用该查询顶点过滤出该顶点的不合格候选项。对于子图搜索，VEQS在IMDB和REDDIT上将VEQS-NS提高了两个数量级，PPI和合作显示了显著的性能提高，尽管邻居安全过滤略微增加了PDBS和PCM上的查询处理时间（见图26）。注意，VEQS-NS表示的算法与VEQS完全相同，只是邻居安全过滤被关闭。我们观察到，是否打开邻居安全滤波会导致滤波时间与验证时间之比的波动。表5给出了VEQS和VEQS-NS的过滤时间与验证时间的平均比值。显然，VEQS始终比VEQS-NS在过滤上花费更多的部分查询处理时间。特别是，PPI，IMDB，和合作，其中的算法花费最多的时间在验证上，受益于邻居安全过滤，因为这种技术有助于大大减少验证的部分时间。
应用邻居安全条件可持续降低假阳性比，如图所示。12和16，同时略微增加了过滤时间，如图19所示。在这里，DAF的滤波方法与VEQSNS相同。
基于静态等价性的匹配顺序的有效性。VEQM-DEQ按照我们的匹配顺序考虑所有查询顶点，而VEQM-SEQ-DEQ只按照DAF的匹配顺序考虑非一次查询顶点。VEQM-DEQ在酵母的Q50N、Q150N、Q200N和电子邮件的Q30S方面的性能比VEQM-SEQ-DEQ高出两个数量级。这两种方法之间的性能差距可能会增加，特别是当存在一级查询顶点具有与非一级查询顶点相同的标签时。
利用动态等效法实现运行时剪枝的有效性。修剪搜索树的等效子树可以带来很大的性能提高，特别是在图25的YAGO中。在这些数据图上，CS中通常有更多的邻域等价的候选细胞，导致许多或大的细胞是剪枝能力的潜在来源。剪枝技术的有效性是以计算单元格和等价集的额外开销为代价而获得的，因此处理一些查询图的时间略有增加。搜索空间的大小。为了证明我们的技术的有效性，我们测量了搜索树中的节点数，这表明了搜索空间的大小(图。27日和28日)。我们比较了DAF匹配顺序的搜索树节点数量和新匹配顺序的搜索树节点数量（两种方法都关闭运行时剪枝，只评估匹配顺序的性能）。在这个图中，VEQ-SEQ-DEQ和VEQ-DEQ分别代表发送DAF和VEQ的匹配顺序。表6给出了新的匹配顺序（即（大小（VEQ-SEQ-DEQ）-大小（VEQ-Deq））/大小（VEQ-SEQDEQ））降低的比率，对于酵母的稀疏查询和PPI的随机游走查询（比BFS查询稀疏）的比例特别高。也就是说，新的匹配顺序更利用了稀疏查询图，这些图可能有更多的稀疏顶点。
我们还比较了图28中没有运行时剪枝的算法和有运行时剪枝的算法之间的搜索空间大小的差异。当动态等价性开启时，搜索空间的大小就会持续变小。表7显示了动态等价（即（大小（VEQ-DEQ）-大小（VEQ））/大小（VEQ-DEQ）)的修剪比率，这在大多数情况下非常高。一般来说，修剪后的比率会随着查询图的大小的增长而增加。
基于静态等价性的匹配阶数的统计分析。我们的匹配顺序通过利用两种情况减少了搜索空间，即(1)|NEC (u)| > |UM (u)|和(2) |NEC (u)|=|UM (u)|。 5.NEC不需要是非单例才能进行修剪；如果一个单例NEC没有候选顶点（例如，当|NEC (u)| = 1和|UM (u)| = 0）时，我们将回溯。
我们计算了这些情况的数量，并测量了基于静态等价的匹配顺序所减少的搜索空间的大小（在表6中，在许多情况下所减少的比例相当高）。进一步分析，表8总结了匹配的匹配和效果的可能性，在符号“>”和“=”表示比率（单位： %）的数量可扩展的顶点u|NEC(u)|>|嗯(u)|和|NEC(u)|=|嗯(u)|，分别在所有可扩展的顶点u∈V (q)搜索树。“Else”表示剩余的可扩展顶点的比率。请注意，在大多数情况下，||(u)|=|UM(u)|比|NEC (u)| > |UM (u)|发生的频率更高。
当|NEC(u)|≥|UM(u)|用“#减少/seq”表示时，每个可扩展顶点u减少的搜索树节点的平均数量。尽管|NEC (u)|≥|UM (u)|的比例很小，因为这只发生在1度顶点上，但#减少/seq在许多情况下是很大的，这导致了表2中相对较高的减少比率。请注意，稀疏查询上的#简化/seq高于非稀疏查询，因为稀疏查询图通常有更多的1次顶点。
利用动态等效法对运行时剪枝的统计分析。以前，表7给出了在大多数情况下具有高修剪比率的修剪搜索空间的大小。为了进一步分析，我们计算在回溯中发生的运行时等价的数量，以衡量等价的可能性。表9总结了可能性，其中“负”和“正”表示未映射可扩展候选与∈CM (u)的比率第1节第5号定义的第一个条件和第二个条件。在搜索树中访问过的所有未映射的可扩展候选对象中的6个。“Else”表示剩余未映射的可扩展候选节点的比例，“#修剪/deq”是指每个负v或正v所修剪的搜索树节点的数量。
一般来说，未映射的v∈CM (u)上的运行时等价更有可能发生在更大或更密集的查询图上。表9中相对较高的比率，+阴性阳性病例加上较高的#修剪/deq，导致表7中非常高的修剪比率。与DBLP上的子图匹配不同，合作上的子图搜索的正比为零，我们最多找到一个嵌入。因此，我们可以在子图匹配中充分利用动态等价性。
表10给出了表9的查询图的核心结构[3,41]的动态等价的可能性和影响。这里，核心结构作为表9实验的输入。对于DBLP的小查询（Q10S、Q20S、Q10N、Q20N），“正”所占的百分比高于表9，这表明核心结构中的顶点更有可能成为正单元格。对于DBLP的大型查询（Q30S、Q40S、Q30N、Q40N），“积极”所占的比例较低。对于与表9不同的每个协作查询集，“Else”案例超过80%。同时，对于随机游走查询集，搜索树节点的数量修剪阳性比表9的大两到三个数量级，这表明随机游走查询中的核心顶点可以通过使用负单元格比非核心顶点修剪更多的搜索空间。
单元格的大小和等价性集。一个单元格中的候选顶点在CS中必须具有相同的邻居，并且一个等价集必须是该单元格的一个子集。那么一个单元格或一个等价集在真实数据集中通常包含多少个顶点呢？为了回答这个问题，我们测量了在COLLAB和DBLP上的所有查询的不同单元格和不同的等价集的大小。对于合作，一个单元格和一个等价集的平均大小分别为2.12和3.23。对于DBLP，其大小分别为1.62和3.74。一个等价集的平均大小大于一个单元格的平均大小，因为一个大单元格的许多不同的子集变成了等价集大小范围为2-10，这是等价集的大小中的大多数，而1是大多数大小的细胞。表11证实了这一现象，表11显示了细胞和等价集的分布。在COLLAB和DBLP中，超过70%的细胞的大小为1，而超过80%的等效集的大小在2到10之间，我们可以在运行时剪枝方法中利用这一点。一个尺寸出现的频率通常会随着尺寸的增加而减小。特别是，1.03×10−6%的细胞（即一个细胞）在51-60大小范围内，1.45×10−8%的等效细胞（即3个细胞）大小在51-60之间，这种情况很少发生。
7.7 Varying degree of query graphs
我们对顶点数相同但平均度不同的查询图进行了性能研究。图29显示了不同程度的查询图的查询处理时间。我们从每个数据图中提取查询图。稀疏、中等和密集查询图的平均度≤分别为3，在3到6之间，≥为6。在酵母中，查询处理时间随着度的增加而减少，但在其他数据集中，查询处理时间对度相当不敏感，这在图25中也可以看出。文章来源：https://www.toymoban.com/news/detail-774250.html
8 Conclusion
为了加快子图的搜索和子图的匹配速度，我们引入了通用的等价性： (i)查询顶点的等价性；以及（ii）候选数据顶点的等价性。在前者中，我们将查询顶点的静态等价性应用于回溯的匹配顺序。在后者中，我们使用候选顶点的邻域等价性来获得搜索树的子树之间的动态等价性，以便在回溯过程中剔除这些冗余的子树。我们还提出了一种通过扩展的dag图DP的邻居安全滤波技术。这三种技术改进了子图搜索和子图匹配的算法。大量的实验表明，我们的算法在子图搜索或子图匹配方面比最先进的算法要多出一个数量级。
我们的方法可以应用于有向图。假设我们给定一个有向查询图q和有向数据图g然后我们认为有向查询图作为无向图，我们建立一个查询，每条边贴上1如果方向新分配的DAG匹配方向输入查询图；否则0。在查询DAG中，从一条边（u，v）中，如果x为1，我们得到一条有向边（u，v）；如果x为0，则为一条有向边（v，u）。
本文中的算法已经处理了一般的无向图（包括无向循环）作为输入。因此，它可以通过上述变换来处理循环有向图。文章来源地址https://www.toymoban.com/news/detail-774250.html
到了这里，关于【论文阅读】Fast subgraph query processing and subgraph matching via static and dynamic equivalences的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
