【论文阅读】Circinus: Fast Redundancy-Reduced Subgraph Matching

Jin T, Li B, Li Y, et al. Circinus: Fast redundancy-reduced subgraph matching[J]. Proceedings of the ACM on Management of Data, 2023, 1(1): 1-26.

1 INTRODUCTION

子图匹配是图分析中的一个基本问题，它具有广泛的应用领域，如生物信息学[27]、化学[45]、金融[5]和社会网络分析[35]。给定一个数据图𝐺和一个查询图𝑞，其中𝐺和𝑞中的顶点可以被标记或不标记，子图匹配的问题是找到𝐺的所有与𝑞同构的子图。
大多数现有的图查询系统(1、6、8、11、12、17、19、29、34、37-39、46]和算法[2-4、14、16、18、31、33、47]处理子图匹配查询的经典Ullmann [40]回溯方法。我们在本文中重点关注基于回溯的解决方案。在回溯过程中，查询顶点（即查询中的顶点）将按照匹配的顺序映射到数据顶点（即数据图中的顶点）。回溯过程可以看作是一个深度优先搜索（DFS）树，其中来自根的任何简单路径都对应于查询的部分/完全匹配。例如，图1显示了用于在数据图𝐺中匹配查询𝑞的DFS树，其中匹配的顺序是𝑢1≺𝑢2≺𝑢3≺𝑢4≺𝑢5。DFS树中最左边的路径将查询顶点（𝑢1，𝑢2，𝑢3，𝑢4，𝑢5）映射到数据顶点（𝑣0，𝑣3，𝑣2，𝑣9，𝑣6），，它对应于𝐺中𝑞的完全匹配，即由{𝑣0，𝑣3，𝑣2，𝑣9，𝑣6}诱导的𝐺的子图是𝑞的匹配。第二条路径将（𝑢1，𝑢2，𝑢3，𝑢4）映射到（𝑣0，𝑣3，𝑣2，𝑣10），，它对应于𝑞的部分匹配，但不能进一步扩展到匹配𝑢5（因为𝑣10映射到𝑢4，𝑢5是𝑢4，𝑣10的邻居，必须在𝐺中有一个标记为‘E’的邻居才能匹配𝑢5）。

现有的解决方案和限制。虽然图挖掘系统[7,11,17,24,38,42,44]和图数据库[6,10,19,29,37]可以用于处理子图匹配查询，但专门的子图匹配系统[1,8,12,23,34,46]和算法[2-4,14-16,18,20,30,47]已经被提出以提供更好的性能（第6节）。这些专门的解决方案使用了各种技术来减少冗余计算，包括消除由图自同构[1,8,11,12,17,34,38,39,46]引起的重复匹配，具有等价关系[15,20,30,34]的查询顶点之间的计算共享，候选剪枝[2,3,14,16,18,20,47]，以及匹配顺序选择来减少回溯搜索空间[3,14,18,33,34]。
虽然现有的解决方案有效地减少了大量冗余计算，但在子图匹配中存在一种关键的重复计算在很大程度上被忽略了。1当我们在回溯树的同一级别上扩展部分匹配时，就会出现这种重复的计算。例如，在图1c中，有三条路径映射到𝑢3到𝑣2，𝑢4映射到𝑣9。为了扩展这三条路径以匹配𝑢5，它是𝑢3和𝑢4的共同邻居，现有的解决方案与这三条路径的𝑣2和𝑣9的邻居集相交。因此，同一邻居集的交集操作被重复三次。这种冗余计算在图的密集簇和幂律图中非常常见。
虽然现有的解决方案有效地减少了大量冗余计算，但在子图匹配中存在一种关键的重复计算在很大程度上被忽略了。1当我们在回溯树的同一级别上扩展部分匹配时，就会出现这种重复的计算。例如，在图1c中，有三条路径映射到𝑢3到𝑣2，𝑢4映射到𝑣9。为了扩展这三条路径以匹配𝑢5，它是𝑢3和𝑢4的共同邻居，现有的解决方案与这三条路径的𝑣2和𝑣9的邻居集相交。因此，同一邻居集的交集操作被重复三次。这种冗余计算在图的密集簇和幂律图中非常常见。
我们可以使用大规模的并行化来处理丰富的集合交集，以减少查询延迟，例如，使用gpu[8,12,13]。然而，一种较弱的方法是通过有效地共享重复集合的交集。不幸的是，在回溯树中的不同路径之间启用这种计算共享并不容易，因为重复的交集可能不属于共享相同前缀的路径（如图1c所示），而且这些路径可能不会被执行连续地当并行化发生时，计算共享变得更加困难，因为不同的路径可能共享相同的集合交集，并且这些路径可能在不同的时间由不同的线程处理。非连续出现和并行化的问题也使交叉结果的缓存无效。我们也可以使用BFS方法来消除这种冗余，通过分组共享相同交集和处于搜索树的同一级别的部分匹配，但是BFS的内存开销通常是禁止的[7,8,38,42]。因此，需要一种新的机制来实现部分匹配之间的计算共享，同时保持基于dfs的内存效率。
在本文中，我们提出了一种新的基于压缩的回溯方法，它可以生成压缩的部分匹配组，以便计算可以在每个组内共享。我们还设计了一个优化策略来选择压缩方案，给予最低的估计计算冗余。为了将我们的基于压缩的回溯方法应用于现有的解决方案（例如，CFL [3]和GQL [16]）来提高它们的性能，我们提出了一个通用的子图匹配框架，称为Circinus，它包括一个模块化的优化工作流和一个基于操作员的执行管道。我们将基于压缩的回溯方法作为Circinus中的一个模块来实现，并提出了特定于压缩的优化，以加快查询执行。大量的实验结果表明，在现有的优化技术的基础上，进一步大大减少了重复计算。与现有方法[3,13,16,17,28,34,36,41]相比，减少的计算性能有效地提高了几个数量级。

2 MOTIVATION

尽管以往曾努力减少冗余计算，但在子图匹配的回溯过程中仍存在着冗余计算的内在来源。
观察。考虑回溯树中的第𝑖级。对于第𝑖级的每个节点𝑤，根到𝑤路径匹配根据给定匹配顺序匹配𝑖第一个查询顶点的部分匹配。设𝑢𝑖+1为（𝑖+1）个查询顶点，如果𝑢𝑗是𝑢𝑖+1的邻居并且在𝑢𝑖+1之前排序，则𝑢𝑗为𝑢𝑖+1的父查询顶点。在部分匹配中，映射到𝑢𝑗的数据顶点𝑣𝑗被称为𝑢𝑖+1的父数据顶点。设𝑢𝑖+1的父数据顶点集为P𝑖+1。为了在第𝑖级扩展每个部分匹配以匹配𝑢𝑖+1，我们执行一个Exthend操作，计算N个𝑝∈P𝑖+1𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠（𝑝），即𝑢𝑖+1的所有父数据顶点的邻居集的交集。例如，在图1中，如果是𝑢𝑖+1=𝑢5，则它的父查询顶点𝑢𝑗为𝑢3和𝑢4。在图1c中，（𝑣0，𝑣3，𝑣2，𝑣9）对应于（𝑢1，𝑢2，𝑢3，𝑢4）的部分匹配，因此𝑣2和𝑣9是𝑢5的父数据顶点。为了扩展（𝑣0，𝑣3，𝑣2，𝑣9）来匹配𝑢5，我们与𝑣2的邻域集相交和𝑣9找到他们的共同邻居有相同的标签，这给出了𝑣6，因此扩展匹配（𝑣0，𝑣3，𝑣2，𝑣9，𝑣6）。
我们可以观察到，交集只涉及父数据顶点的邻居集，而映射到其他查询顶点的数据顶点则是无关的。这提供了一个计算共享机会：如果每个级别上的部分匹配由父数据顶点分组，那么它们可以在执行“扩展”操作时共享交集结果。以图1c为例，扩展（𝑣0，𝑣3，𝑣2，𝑣9）、（𝑣0，𝑣4，𝑣2，𝑣9）和（𝑣1，𝑣8，𝑣2，𝑣9）匹配𝑢5，我们可以将它们按（𝑣2，𝑣9）分组，与𝑣2和𝑣9的相邻集相交一次，得到𝑣6（匹配𝑢5）。
验证。我们报告了两种重要的子图匹配方法，CFL [3]和GQL [16]，以及最近的一个系统游隼[17]的计算冗余。我们测量了每种方法中集合交集计算的数量。作为参考，我们还计算了每种方法的集合交集调用的最优数量，这些方法是通过在回溯树的同一级别上的所有部分匹配之间共享计算来实现的。我们将对实验设置的完整描述推迟到第5.3节。我们发现，对于所有的三个解，实际的交点计数和相应的最优数之间的差值可以是一到两个数量级。即重复计算占总集合交集计算的90%-99%，为计算共享提供了很大的空间。

3 COMPRESSION-BASED BACKTRACKING

我们提出了一种新的基于压缩的回溯方法，该方法通过在回溯搜索树的每个级别上对部分匹配进行分组来实现计算共享，同时仍然遵循DFS方法来有效地使用内存。

3.1 Subgraph Compression

我们首先用一个例子来说明其主要思想。考虑图1中所示的查询𝑞和匹配的顺序𝑢1≺𝑢2≺𝑢3≺𝑢4≺𝑢5。对于1≤𝑖≤5，设𝑞𝑖为由{𝑢1，𝑢2，……，𝑢𝑖}诱导的𝑞的子图，如图2所示，设𝑀𝑖为图1中DFS树的𝑖级的部分匹配集，即𝑞𝑖的匹配。例如，𝑀4由{𝑣0，𝑣3，𝑣2，𝑣9}，{𝑣0，𝑣3，𝑣2，𝑣10}，{𝑣0，𝑣4，𝑣2，𝑣9}，和{𝑣1，𝑣8，𝑣2，𝑣9}，诱导的𝐺的四个子图组成，它们都与𝑞4相匹配（如图2所示）。

我们的目标是在将𝑀𝑖扩展到𝑀𝑖+1时（按键）分组每个𝑀𝑖中的子图（即匹配𝐺中的𝑞𝑖+1），以最大化计算共享。考虑将𝑀4扩展到𝑀5，最优分组将是使用{𝑢3，𝑢4}（即{𝑣2，𝑣9}，{𝑣2，𝑣10}）的映射作为键，它允许𝑣2和𝑣9的邻居集的交集在𝑀4中的三个部分匹配之间共享。然而，这种最优分组需要完全计算𝑀𝑖，这本质上是一种BFS方法，而且内存禁止。
我们能否为每个级别一次计算一个组，而不是像BFS方法那样计算所有组，同时仍然有效地共享计算？受CBF2 [28]中压缩技术的启发，我们建议使用𝑞𝑖的顶点覆盖（VC）来设置分组键。对于每个𝑀𝑖，映射到顶点覆盖物中的查询顶点的数据顶点被设置为分组键。
考虑到𝑞4，并使用{𝑢1，𝑢3，𝑢4}作为其VC。在𝑀4中的部分匹配中映射到（𝑢1、𝑢3，𝑢4）的数据顶点为（𝑣0、𝑣2、𝑣9）、（𝑣0、𝑣2、𝑣10）、（𝑣0、𝑣2、𝑣9）、（𝑣1，𝑣2，𝑣9）。因此，如果我们使用映射数据顶点作为键，𝑀4被分为三组：（𝑣0，{𝑣3，𝑣4}，𝑣2，𝑣9），（𝑣0，{𝑣3}，𝑣2，𝑣10），（𝑣1，{𝑣8}，𝑣2，𝑣9），其中（𝑣0，𝑣3，𝑣2，𝑣9）和（𝑣0，𝑣4，𝑣2，𝑣9）被压缩成一个组（𝑣0，{𝑣3，𝑣4}，𝑣2，𝑣9），可以通过共享𝑣2和𝑣9的邻居的交集来进行扩展。请注意，在这个示例中，压缩（以及计算共享）在这个玩具示例中并不令人印象深刻，但在如图11所示的真实数据图中非常重要，我们将在第5.3节中展示更多内容。

3.2 Compression-based Extend Operator

利用基于vc的分组，我们设计了一个新的Extend算子，它计算压缩组上的扩展，并将标准的回溯过程转换为基于压缩的回溯。
设计选择。在我们对Extend操作符的设计中，我们做了以下三个设计选择来绑定内存使用，并确保低分组开销。
首先，我们强制执行每个分组键必须是组中子图的VC，这样Extend就可以在每个级别上一次生成一组部分匹配，而不像基于BFS的方法那样存储整个级别的部分匹配。对于每一组部分匹配，基于vc的压缩[28]避免了枚举组中集合的交叉积，即，对于没有压缩的组（𝑣1，{𝑥1，…，𝑥𝑚}，𝑣2，{𝑦1，…，𝑦𝑛}），，我们需要以（𝑣1，𝑥𝑖，𝑣2，𝑦𝑗）.的形式枚举𝑂（𝑚𝑛）部分匹配因此，基于vc的压缩减少了内存开销。特别是，在回溯的每一步中，压缩组所需的内存受到非vc查询顶点的映射数据顶点总数加上一个小常量的限制。因此，实际中内存使用很小（第5.2.3节）。
其次，我们要求𝑞𝑖的顶点覆盖𝑈𝑖包含在𝑞𝑖+1的顶点覆盖𝑈𝑖+1中，即𝑈𝑖⊆𝑈𝑖+1。这是因为当我们匹配𝑞𝑖+1时，如果是𝑈𝑖⊆𝑈𝑖+1，则需要同时生成和处理许多𝑞𝑖匹配组，以便将𝑞𝑖+1的匹配组重新分组，这将导致很高的开销。
第三，Extend操作符直接以压缩格式计算扩展，并通过直接使用交集结果将非vc集维护在压缩组中，以避免压缩和解压缩的额外计算。
扩展算法。算法1给出了扩展算子。给定子查询𝑞𝑖的部分匹配的压缩组𝐶𝑖，其中部分匹配基于𝑞𝑖的顶点覆盖𝑈𝑖具有相同的分组键，Extend扩展𝐶𝑖以匹配（𝑖+1）个查询顶点𝑢，如下所示。设𝑃为𝑢的父查询顶点的集合，即那些与𝑢相邻但在𝑢之前的查询顶点，𝑈𝑖+1为𝑞𝑖+1所选择的VC。有三种情况：
1 𝑃⊆𝑈𝑖+1；
2 𝑃∩𝑈𝑖+1=∅；
3 𝑃∩𝑈𝑖+1=∅和𝑃⊆𝑈𝑖+1。
请注意，案例2和案例3的𝑢∈𝑈𝑖+1，否则，连接𝑢和𝑃中的父顶点的一些边没有被覆盖。表示与父查询顶点𝑝匹配的𝑣的邻居集为A𝑢𝑝（𝑣），其中的邻居是目标查询顶点𝑢的候选对象。由于剪枝采用了各种过滤规则，如通过查询顶点标签进行过滤，避免同一部分匹配中的重复顶点，因此匹配不同𝑢的𝑣邻居可能会不同。
在案例1（行1-5），映射集𝑆𝑢（即，用于映射到𝑢的数据顶点）计算通过调用扩展计算的邻居集的交集数据顶点𝐶𝑖映射到𝑃查询顶点。具体来说，在第16行中，get邻域交集（𝑢，𝑃𝑘𝑒𝑦，𝐶𝑖）计算N𝑝∈𝑃𝑘𝑒𝑦A𝑢𝑝（𝐶𝑖.getKey（𝑝））。如果𝑢在顶点覆盖𝑈𝑖+1中，则对于每个顶点𝑣∈𝑆，调用addKey将𝑣添加到𝐶𝑖中以生成新的组𝐶𝑖+1，并将𝑣添加到𝐶𝑖+1的分组键中。否则，调用addSet将𝑆添加到𝐶𝑖以生成一个新的组𝐶𝑖+1。图2显示了一个示例，其中黑色顶点是每个子查询𝑞𝑖的VC。考虑将𝑞1扩展到𝑞2，我们有𝑢=𝑢2和𝑃={𝑢1}和𝑈𝑖+1=𝑈2={𝑢1}，，从𝑃⊆𝑈2.开始，它是Case 1有两个压缩组匹配（𝑢1）：（𝑣0）和（𝑣1）。为了扩展𝐶1=（𝑣0），我们首先从𝑣0的邻居集（所有属于𝑣0的邻居集）中得到𝑢的映射集标签不是‘B’被过滤掉了，参见图1b中的𝑣0的邻居)，这给出了𝑆={𝑣3，𝑣4}。由于𝑢2不在𝑈2中，所以我们只需将𝑆添加到𝐶1中，以获得𝐶2=（𝑣0，{𝑣3，𝑣4}），如图2所示。在这里，𝐶2是一个压缩组，存储两个部分匹配项（𝑣0，𝑣3）和（𝑣0，𝑣4）。

在案例1中有一个特殊的场景，当𝑃⊆𝑈𝑖+1，但是𝑃⊆𝑈𝑖，即，一些映射到𝐶𝑖中的集合的父查询顶点被添加到𝑞𝑖+1的VC中。在这种情况下，我们需要部分解压𝐶𝑖，并通过枚举这些映射集的乘积来生成多个组。然后我们对每个生成的组调用扩展。
在情况2（第6-10行）中，我们首先选择一个具有最小映射集𝑆𝑚𝑖𝑛的父查询顶点𝑝𝑚𝑖𝑛。然后，我们计算一个𝑢的候选集𝑆作为𝑆𝑚𝑖𝑛中所有顶点的邻域集的并集，即𝑆←Ð𝑣∈𝑆𝑚𝑖𝑛A𝑢𝑝𝑚𝑖𝑛（𝑣）。对于每个候选的𝑣∈𝑆，𝑣是一个数据顶点，如果𝑣是𝑢的所有父数据顶点的邻居，则可以用于映射到𝑢。因此，对于每个𝑣∈𝑆，我们调用扩展fromSet来计算𝑣的邻居集和每个𝑝∈𝑃的映射集之间的交集。如果交叉点（对于所有的𝑝∈𝑃）不是空的，则找到𝑢的映射数据顶点𝑣并生成一个新的组，并将𝑣添加到分组键中（因为𝑢在VC中）。为了说明这一点，考虑在图2中将𝑞3扩展到𝑞4，我们有𝑢=𝑢4，𝑃={𝑢2}和𝑈4={𝑢1，𝑢3，𝑢4}，，这是𝑃N𝑈4=∅.以来的Case 2考虑扩展𝑞3的压缩组（𝑣0，{𝑣3，𝑣4}，𝑣2），我们有𝑝𝑚𝑖𝑛=𝑢2 and𝑆𝑚𝑖𝑛={𝑣3，𝑣4}。我们通过𝑣3和𝑣4的邻居集的并集来计算𝑆={𝑣9，𝑣10}（所有标签不是D的邻居都被过滤掉）。然后我们将扩展集调用为将𝑣9的邻域集与𝑢2的映射集相交，它给出了{𝑣3，𝑣4}和一个新的𝑞4的压缩群（𝑣0，{𝑣3，𝑣4}，𝑣2，𝑣9）。我们还将𝑣10的邻域集和𝑢2的映射集相交，它给出了{𝑣3}和另一组𝑞4（𝑣0，{𝑣3}，𝑣2，𝑣10）。
在案例3（第11-14行）中，我们将𝑃分为两个集合：𝑃𝑘𝑒𝑦是VC的一部分，而𝑃𝑠𝑒𝑡是𝑃中剩余的顶点。我们使用𝑃𝑘𝑒𝑦计算案例1中的𝑢的映射集，对于每个𝑣∈𝑆，使用案例2中的𝑃𝑠𝑒𝑡生成新的压缩组。

3.3 Backtracking

算法2显示了整个回溯过程。我们可以通过以给定的匹配顺序初始化第一个查询顶点𝑢1的压缩组(s)来开始匹配一个查询。如果在VC中选择𝑢1，则𝑢1的每个映射数据顶点形成一个压缩组（第4行）；否则，𝑢1的映射数据顶点集形成一个压缩组（第5行）。然后，该算法递归地扩展每个压缩组，通过DFS找到𝑞的匹配，使用Extend作为生成器。

3.4 Selection of Vextex Covers

我们首先分析了基于压缩的回溯如何减少冗余计算，然后引入了一种为每个子查询选择VC的策略。
让我们来考虑一下𝑈𝑖⊆𝑃吧。在这种情况下，包含𝑢的相同父数据顶点的所有𝑞𝑖匹配项都必须在同一个压缩组中，因此它们可以共享集合的交集结果。因此，将𝑞𝑖的匹配扩展到𝑞𝑖+1的匹配，而可以通过任何更好的分组保存的匹配，没有冗余。现在考虑𝑈𝑖⊆𝑃，包含𝑢的相同父数据顶点的𝑞𝑖匹配，由于分组键中的非父数据顶点的不同，即映射到𝑤∈𝑈𝑖\（𝑈𝑖∩𝑃）的数据顶点。因此，对于较少的计算冗余，首选一个导致较少这样的分组密钥的VC。
成本模型。我们设计了一个成本模型来估计扩展𝑞𝑖到𝑞𝑖+1所需的计算成本：

其中，𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）是为扩展𝑞𝑖而处理的压缩组的（估计的）数量，这些压缩组是基于一个顶点覆盖𝑈生成的。方程中的第一项对应于所有扩展键调用的估计交点总数，其中|𝑃𝑘𝑒𝑦|是一个扩展键调用中的交点数。第二项对应于估计的交叉口总数扩展调用，其中|𝑃𝑠𝑒𝑡|十字路口的数量在一个扩展调用，和𝑐𝑎𝑟𝑑𝑞𝑖+1（𝑈∪{𝑢}）估计的所有𝑆的总大小在案例2或3所有𝑞𝑖𝐶𝑖（即，调用时𝑃𝑠𝑒𝑡=∅）.请注意，𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）≤𝑐𝑎𝑟𝑑𝑞𝑖（𝑈∪{𝑢}），因为将𝑢添加到分组键中，因此只会创建更精细的组。因此，与𝑃重叠更小的顶点覆盖𝑈可能得到更小的𝑐𝑜𝑠𝑡𝑖（𝑈）。
为了估计𝑐𝑎𝑟𝑑𝑞𝑖（𝑈），我们使用𝑈中每个查询顶点的候选点（即可能匹配）基数的乘积（例如，使用基于查询顶点的标签和度的数据图中的标签频率或度分布）。或者，当生成查询顶点的匹配集时，我们可以计算𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）作为[3,14]中路径权值计算后可能的回溯搜索空间，以进行更紧密的估计。
搜索策略。算法3展示了如何生成风投。让𝑞1，𝑞2，……，𝑞𝑛是由匹配顺序定义的子查询序列，其中𝑛是给定查询𝑞中的顶点数。即使在包含约束𝑈𝑖⊆𝑈𝑖+1下（在上面的“设计选择”中讨论过），为每个𝑞𝑖找到最佳VC的搜索空间也很大。
我们没有搜索整个空间，即𝑂（2𝑛（𝑛+1）/2）大小的𝑛级别组合，每个级别𝑖有2个𝑖枚举，而是生成一个相对较小的搜索空间U，大小为𝑂（𝑛2），如第1-10行所示。我们首先通过分支和绑定（第3行）为每个子查询𝑞𝑖生成一个最小权重的顶点覆盖𝑈𝑖𝑖，使用𝑐𝑎𝑟𝑑𝑞𝑖（{𝑢}）作为𝑞𝑖中每个查询顶点𝑢的权重。接下来，对于每个𝑖，我们为每个𝑞𝑗计算一个最小权重顶点覆盖𝑈𝑗𝑖，其中1≤𝑗≤𝑛和𝑗=𝑖，同时强制执行包含约束𝑈𝑗𝑖⊆𝑈𝑗𝑖+1。具体来说，我们使用一个赋值表来根据𝑈𝑖𝑖预先分配顶点，并在具有空赋值的顶点上运行分支和绑定。
然后，我们使用动态规划（DP）来寻找最小化总成本𝑇𝐶=I𝑛−1𝑖=1𝑐𝑜𝑠𝑡𝑖（𝑈𝑖）来匹配𝑞=𝑞𝑛（行11-18）。我们定义了一个DP表𝑇，其中𝑇（𝑖，𝑈𝑖𝑘）记录了当选择𝑈𝑖𝑘作为𝑞𝑖的VC时，匹配𝑞𝑖+1的最小总成本。我们为每个𝑈1𝑘初始化𝑇（1，𝑈1𝑘）（注𝑈1𝑘={𝑢1}或∅）：

然后，我们递归地计算1个<𝑖<𝑛和𝑈𝑖𝑘∈U𝑖的𝑇（𝑖，𝑈𝑖𝑘）。我们将ˆ𝑈𝑖−1设置为𝑈𝑖𝑘的父项，用于DP表中的回溯跟踪（第17行）。为了检索vc的最佳序列，我们选择了最小化𝑇𝐶=𝑇（𝑛−1，𝑈𝑛−1）的顶点覆盖𝑈𝑛−1∈𝑈𝑛−1，并递归追溯。对于𝑞的VC，我们采用最小权重顶点覆盖𝑈𝑛⊇𝑈𝑛−1（Line19行）。DP的时间复杂度为𝑂（𝑛2·𝑡），其中𝑛（𝑡=Ω，𝑛）为计算𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）的复杂度。

3.5 Discussion

我们如何与BFS/DFS方法进行比较？我们的方法在压缩组的粒度上进行DFS。与现有的单独处理部分匹配的BFS和DFS方法相比，我们的方法可以归类为一种BFS/DFS混合方法，但与所有现有的混合方法具有不同的目标和技术解决方案。现有的结合BFS和DFS [7,12,39,44,46]的工作旨在平衡内存使用和并行化效率。他们使用BFS来增加并行性，而不是减少重复的计算。事实上，基于BFS的方法被广泛用于基于gpu的解决方案[8,12,13]或分布式解决方案[7,38,44]利用大规模并行性并提供良好的负载平衡（第6节）。从技术角度来看，现有的混合方法要么采用基于批处理的方法（例如，以DFS方式处理批，但在每个批处理BFS）[7,12,44]，要么根据生成的部分匹配的数量在BFS和DFS [39,46]之间动态切换。批处理或切换要么基于预设的阈值或运行时内存可用性，这与查询无关。例如，PBE-repess[13]将可用的内存分配给回溯树的每个级别以存储中间结果，并在当前级别的缓冲区满时从BFS切换到DFS。相比之下，我们的解决方案利用了查询模式来最大化计算共享。BFS实际上发生在压缩组中（这里，“虚拟”表示组中的部分匹配没有真正枚举），而组则以DFS方式计算。此外，我们的方法可以应用于单线程解决方案（例如，CFL、GQL），以提高其性能（第5.2.1节），而现有的混合方法仅适用于并行场景。

我们如何与最坏情况下的最优连接进行比较？同构子图匹配是npp完整的[9]。这个问题可以表示为数据库研究中的一个连接问题，其中每个查询边表示一个关系，每个查询顶点表示一个属性。最坏情况下的最优连接（WCOJ）保证了运行时间与最坏情况下的输出大小成正比，这在理论上优于二进制连接。我们将讨论我们的方法与WCOJ之间的关系。
Ngo等人[26]提出了一种通用的WCOJ算法，该算法推广了包括WCOJ TrieJoin [41]在内的重要算法。在子图匹配的上下文中，WCOJ在单个多路连接中处理与查询顶点𝑢相关联的所有关系，其时间复杂度与最小的关系大小成正比。WCOJ使用回溯并处理“一次查询顶点”，Circinus也是如此，而二进制连接则处理“一次查询边”。Circinus是通用WCOJ算法[26]的一个实例化（具有共享计算），当顶点覆盖只启用算法1中的情况1时。具体来说，通用的WCOJ算法允许对查询顶点集进行任意分区以进行递归查询分解，并且只有情况1的循环算法将（子）查询𝑞𝑖由{𝑢1、···、𝑢𝑖−1}和{𝑢𝑖}进行分区。扩展fromkey本质上是一个多路排序合并连接，其运行时间与最小的邻居集大小3成比例。对于情况2和情况3，不能保证候选集𝑆的计算的运行时间与最小关系（即最小父邻居集）的大小成正比。然而，Circinus使用成本模型（参考第3.4节）进行计划优化，当它比只有案例1的替代方案便宜时，只允许案例2和案例3。我们在第5.2节中与跳蛙三化join进行了比较。
现有的解决方案可以轻松地扩展到基于压缩的回溯吗？我们的基于压缩的方法是为基于回溯的解决方案而设计的，并与许多优化匹配顺序、候选过滤或数据图布局的现有技术相正交。我们在第5.2节中证明，我们的方法可以应用于现有的算法（即CFL和GQL），并进一步显著提高了它们的性能。但是，从实现的角度来看，现有的子图匹配解决方案不能轻易地扩展到支持基于压缩的回溯，原因如下。在现有的解决方案中，子图匹配的逻辑是在一个嵌套的for循环中编写的，并且优化逻辑（如自同构消除和候选过滤）和查询评估逻辑（如集合交集和枚举）都与存储部分匹配的数据结构紧密集成。然而，基于压缩的回溯使用压缩组来表示部分匹配，这需要我们更改数据结构，以在现有解决方案中存储部分匹配，而这本身就需要修改现有解决方案中的大部分代码库。这促使我们建立一个总体框架。我们提供了一个带有抽象回溯逻辑的“扩展”操作符的模块化设计，一个用于生成带有附加过滤器和检查的操作符链的优化器，以及一个基于推送的执行模型。通过这种设计，基于压缩的优化和其他技术可以很容易地结合起来，以处理需要不同技术的不同类型的查询和图（例如，已标记的、未标记的）。

4 QUERY EXECUTION

为了应用基于压缩的回溯算法，我们提出了一个子图匹配框架，称为Circinus，以及一些查询执行的优化。

4.1 The Circinus Framework

为了使我们的方法作为一种通用的优化，可以应用于现有的解决方案，以提高其性能，我们将Circinus设计为一个通用的优化和执行框架。该框架是一个模块化设计，因此可以很容易地插入用来优化子图匹配的每一步的各种技术。图3显示了该框架的概述，它包括七个模块及其之间的流动。在右边，我们还列出了在每个模块中使用的代表性技术的摘要。

模块1到4是用于基于回溯的子图匹配的通用，这些模块中的一些优化技术在现有的解决方案中常用。模块1～3形成查询规划逻辑，首先在没有数据图或执行层知识的情况下分析查询图，然后使用分析结果生成逻辑计划，最后基于逻辑计划和来自执行层的信息构造物理计划。然后，模块4通过回溯来执行物理计划，并可能使用并行化来进行密集的计算。
模块5和模块6支持专门的优化，如各种修剪规则（例如，数据顶点标签、度、邻域标签频率、候选集中是否存在邻居等）。为每个查询顶点修剪候选匹配项。辅助数据结构也可以使用改进的候选数据集来构建，以促进回溯。特定于查询的成本（例如，子图计数的估计和扩展成本）是从辅助数据结构或数据图中计算出来的，可用于计算替代匹配顺序的成本。模块7生成一个基于压缩的计算共享查询计划（第3节）。
图3显示了Circinus中的一般工作流程，包括两个计划阶段和两个执行阶段。第一个规划阶段包括模块1和模块5，然后是第一个执行阶段的模块6。如果不需要在模块5中生成候选集，则会跳过模块6中的执行。第二个规划阶段由模块2、模块7和模块3组成，然后由模块4最终执行。

4.2 Compression Specific Optimizations

Circinus支持几种特定于基于压缩的回溯的优化。对压缩组的战略性修剪。在回溯过程中，只有当我们输出匹配的子图时，一个被压缩的组才会被完全解压缩。但是，由于将相同的数据顶点匹配到多个查询顶点，可以找到一些压缩组没有有效匹配。这是有两个原因。首先，当同一压缩组中的多个映射集匹配相同标签的查询顶点时，它们可能包含重叠的数据顶点。具体来说，如果有𝑘个这样的映射集，但它们共同包含少于𝑘个的不同顶点，整个压缩组都无效，应尽早进行修剪。其次，当一个顶点作为键添加到压缩组时，它可能会出现在一些现有的映射集中。
我们设计了一个修剪策略，在每个压缩组生成时适用于它，以避免对无效组的无用计算。考虑一个与𝑞𝑖匹配的压缩组，让𝑢𝑖的标签为𝑙。我们设置了一个剪枝阈值𝜃𝑙，它是在𝑞𝑖中带有标签𝑙的查询顶点的数量。我们提取所有标签为𝑙和大小小于𝜃𝑙的映射集。然后，我们检查在它们的笛卡尔乘积中是否至少有一个元组没有重复，也不与标签𝑙的键重叠。如果没有找到元组，我们将修剪压缩的组。
注意，对于有效的压缩组，不同的映射集中可能存在重叠顶点，但这不会导致无用的计算，因为： (1)在扩展fromkey的情况下，映射集不参与计算，并且有效和无效部分匹配的计算在组中共享；(2)在扩展的情况下，通过相交父查询顶点与目标数据顶点的邻居顶点关联的映射集独立更新。
支持使用辅助数据结构的算法。GQL [16]和CFL [3]等算法为每个查询顶点计算一个候选顶点集，并建立辅助的二部图来处理每个给定的查询。构建二部图的空间复杂度较高，即𝑂（|𝐸𝐺|×|𝐸𝑞|），其中|𝐸𝐺|为数据图𝐺中的边数，|𝐸𝑞|为查询𝑞中的边数。因此，为了获得更好的可伸缩性，我们避免构造二部图，而是在扩展fromkey中添加目标查询顶点的候选集，并动态计算候选边。请注意，由于Circinus已经避免了重复计算，因此它从使用二部图（用空间交换时间）中获益不多。
来自压缩集的自适应扩展。在算法1的情况2中，通过并集计算一个目标集𝑆。当使用GQL [16]和CFL [3]等算法，为目标查询顶点生成一个小的候选集，其大小小于估计的并集大小时，可以通过直接使用候选集作为𝑆而不是计算并集来减少计算。𝑆的计算在运行时被调整，用于每个压缩组的扩展。

4.3 Parallelization and Load Balancing

为了支持高效的并行计算，Circinus使用分块和最低级任务分割策略进行负载平衡。
块。在多线程执行的情况下，Circinus将初始的部分匹配划分为块。分配一个任务来在一个块上运行整个执行管道。由于从每个初始部分匹配开始的搜索空间可能不同，Circinus利用在查询计划阶段计算的初始部分匹配的成本来生成负载平衡块。如果所选的规划策略不计算成本，则使用映射到第一个查询顶点的数据顶点的程度。
最低级任务分割。由于用于生成块的成本可能不准确，Circinus在查询执行过程中动态地维护负载平衡。如果未完成任务的数量小于可用线程，则向正在运行的任务发送信号以进行任务分割。当接收到信号时，任务不是在DFS树的当前级别计算和分割一批输出，而是首先在其输入块中分割部分匹配以创建新任务。当在当前最低级别没有要拆分的部分匹配时（即，最接近DFS树根的未完成级别）时，任务计算下一级别的部分匹配，并将它们拆分以创建新任务。因此，该任务总是在尽可能低的级别上进行计算和分割。这个底层策略的原因是部分匹配在较低的期望有更多的计算，和分裂在底层首先使原始任务和新任务搜索子树根在同一级别，这样他们有类似的负荷。

5 EXPERIMENTAL EVALUATION

我们在不同的数据集和查询设置上评估了Circinus，以回答以下三个问题：
(1)Circinus与最先进的解决方案相比如何？
(2)圆如何有效地减少冗余计算？
(3)Circinus中的各种设置（如𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）、并行性）如何影响其性能？

5.1 Experimental Setup

数据集。我们使用了6个真实世界的数据集，这些数据集通常用于评估之前的子图匹配方法[3,17,22,24,36]。表1列出了它们的统计数据。HM是一个带有标签的生物网络。YT2描述了从2007年2月到5月发布的Youtube视频，每个视频都用一个顶点表示，如果两个视频是相关的，就有一条边，视频类别就是标签。其他数据集是未标记的社交网络，它的标签被随机分配到之前的标签集的数据顶点。
查询。我们使用了8个未标记的查询，如图4所示，其中𝑞1-𝑞7也被用于评估游隼[17]，CBF [28]和PBE [12,13]（PBE使用了𝑞1，𝑞2和𝑞5）。对于有标记的查询，我们通过随机游走和BFS从每个数据集中提取子图来生成查询，遵循之前的工作[2,3,14,15,30,36]。我们生成了4组查询，{𝑄6，𝑄8，𝑄12，𝑄16}，其中每个集合𝑄𝑛由200个查询组成，𝑛∈{6,8,12,16}是每个查询中的顶点数量。除非另有说明，所有实验都是在两个2.1 GHz Intel ® Xeon ®银色4110 CPU的机器上运行的，超线程（16核，32个超线程）和128GB RAM，运行64位Debian9.8版本。

5.2 Performance Comparison

我们首先报告了Circinus (1)与游隼[17]、青蛙Trie（LFTJ）[41]，CFL[3]和GQL [16]对标记查询的比较结果，以及(2)与游隼、LFTJ、GraphPi[34]，PBE-重用[13]和CBF [28]对未标记查询的比较结果。CFL和GQL是两种有效的标记子图匹配算法。游隼是一种最先进的图挖掘系统，它支持子图匹配。LFTJ是商业数据库LogicBlox中采用的一种开创性的最坏情况最优连接算法。PBE重用和CBF是专门的无标记子图匹配方法，其中PBE重用是一个多线程系统，CBF基于MapReduce。对于CFL和GQL，我们使用了[36]中提供的CFL和GQLfs的实现（GQLfs [36]在最先进的标记查询算法中提供了最好的整体性能）。对于游隼、PBE-重用和GraphPi，我们从作者那里获得了源代码。对于PBE-重用，我们使用了它的多线程实现。对于LFTJ，我们通过严格遵循[41]中的规范（包括三次迭代器接口和连接逻辑）来实现该算法。由于LFTJ没有指定匹配顺序，我们使用GQL的匹配顺序来运行LFTJ，因为GQL的排序策略在最先进的子图匹配方法[36]中是最有效的。[41]不讨论其他查询优化（例如，自同构处理）或如何并行化单线程算法，我们也实现了LFTJ的连接逻辑（不使用特里迭代器关系，但优化直接访问CSR）和禁用压缩，我们表示这个实现LFTJ-Circinus。
由于LFTJ、CFL和GQL都是单线程算法，所以我们通过在一个线程上运行，将Circinus与它们进行了比较。对于游隼、GraphPi、CBF和PBE-重用，我们在使用所有32个超线程的机器上与它们进行了比较。对于CBF，我们使用推荐的每个容器1核和4 GB内存，除了最大的数据集FR每个容器使用6GB内存。

5.2.1 Results for Labeled Queries

对于标记查询，我们将Circinus与CFL [3]和GQL [16]进行了比较，它们利用候选过滤规则和辅助数据结构进行查询优化，以及LFTJ。Circinus只使用一般模块（即模块1- 4）和模块7，而Circinus-CFL和Circinus-GQL进一步包括CFL和GQL的匹配顺序和候选滤波策略（在模块5-6中实现）。
单线程处理。图5a报告了在HM和YT2上处理查询集𝑄8、𝑄12和𝑄16的六种方法的时间。我们使用标准的方框图[43]来报告每一组查询的时间。基于CFL/GQL的解决方案比LFTJ具有更多的优势，特别是在处理更复杂的查询方面，这要感谢它们先进的修剪策略。环组-CFL和GQL显著提高了CFL和GQL的性能对于不同大小的查询，我们可以回溯HM和YT2，尽管CFL和GQL都已经有了先进的优化，通过匹配顺序和候选过滤来减少冗余计算。通过与CFL/GQL进行比较，我们发现环轮的计算共享明显比CFL/GQL的候选滤波更有效，但其性能与YT2相当。这是因为HM是一个更密集的图，它提供了更多的计算共享机会，因为同一组数据顶点可能出现在许多部分匹配中。
由于单个线程的计算能力不足，可能需要很长时间来处理查询，如果不能在1800秒内完成，我们就杀死一个查询（我们从图5a中排除了CFL、GQL、LFTJ和Circinus无法完成的查询）。表2报告了由每个方法完成的查询的数量。在计算共享的帮助下，Circinus-CFL和Circinus-GQL完成了更多的查询。
并行处理。然后，我们比较了环隼与LFTJ（实现）的并行查询处理性能。然而，Peregrine不能在合理的时间内处理更大的查询，而且处理HM（HM的图最小，但密度很大）和FR也需要太长的时间。因此，我们选择了YT2和OR，并使用了查询集𝑄6和𝑄8。我们将在后续的实验中报告Circinus在更大的查询和其他数据集上的结果。
图5b报告了结果，其中所有的解决方案都使用了32个线程。游隼和游隼-cfl的性能都优于游隼和LFTJ-游隼，而且它的速度比游隼快两个数量级。游隼和圆直接对数据图进行回溯，而不使用复杂的候选滤波或辅助数据结构。因此，圆比游隼的性能提高主要是由于基于压缩组的回溯的计算共享。虽然圆没有提供LFTJ-圆的最坏情况最优保证，但圆的性能明显优于LFTJ，因为圆具有基于实际成本模型的计算共享优势（见3.5节中关于最坏情况最优连接的讨论）。
Circinus甚至优于Circinus-CFL（也叫Circinus-GQL），这是因为CFL候选生成的开销大于CFL带来的好处。Circinus对HM/YT2和OR的不同性能可以用数据图中的标签分布来解释。HM和YT2的标签分布呈偏态分布，而OR的标签分布呈均匀分布。因此，在OR的情况下，CFL/GQL的复杂滤波规则几乎不比简单的基于标签/度的滤波具有更强的剪枝能力。

5.2.2 Results for Unlabeled Queries

图6报告了未标记查询的执行时间。我们对LFTJ和Circinus使用了相同的匹配顺序。一些基线系统可能需要很长时间来处理查询，因为未标记查询的匹配数量可能非常大。因此，当处理查询超过12小时时，我们杀死了它。对于最大的图FR，所有的系统都超过12小时，我们在图6中省略了这些查询的结果。图6还跳过了𝑞8对CBF的结果，因为CBF需要手工优化的MapReduce实现，并且我们只运行它的内置查询（即𝑞1-𝑞7）。
在这些系统中，即环轮、GraphPi、LFTJ、PBE-重用、游隼和CBF，没有单一的赢家。总的来说，除了与GraphPi比较外，圆在大多数情况下都明显优于其他方法。对于小的无标记查询，图的自同构性和具有等价邻域的查询顶点是计算冗余性的主要因素。GraphPi通过其基于2周期的自同构消除和计算避免技术解决了这些问题。然而，虽然GraphPi是专门用于无标记子图匹配的最先进的系统，但它的技术对标记子图匹配的影响有限。相比之下，Circinus对已标记和未标记的查询都有良好的性能。PBE重用是一种基于缓存的方法，专门用于未标记的子图匹配，它通过生成一个执行计划来利用缓存集的交集结果来扩展PBE [12]。然而，PBE重用在执行过程中搜索缓存结果效率低，而且内存占用也很大。CBF具有通过大规模物化重用计算的优势，但它存在高内存占用和磁盘读写开销。虽然物化三角形允许更多的计算重用，但开销可能超过好处，特别是在处理更小和更密集的查询（例如，𝑞1，𝑞2，𝑞5）。相比之下，游隼通过回溯在内存使用方面是有效的，但由于第2节中分析的DFS方法的常见问题，游隼存在很多冗余计算。特别是对于较大的查询（例如，𝑞6-𝑞8），当回溯搜索空间增大时，重复搜索空间迅速增加，游隼表现不佳。相比之下，Circinus既具有基于压缩分组的回溯所带来的内存效率和计算共享的优点，并具有最佳的整体性能。在大多数情况下，它的性能从游隼和CBF好几倍到一个数量级。由于其基于压缩的计算共享策略，圆环菌株的性能始终优于LFTJ-Circinus。

5.2.3 Memory Usage Analysis

我们报告了我们在上述实验中比较的解决方案的峰值内存消耗。结果（图7和图8）显示，Circinus的内存开销很小（并不比基于dfs的方法大多少，与BFS方法相比可以忽略不计）。
图7a报告了与图5a对应的已标记查询的单线程处理的峰值内存使用情况。与CFL和GQL相比，GQL、CFL和GQL在HM上的峰值记忆使用量相当。圆环藻也有与DFS方法LFTJ相当的峰值内存使用量。Circinus计算一个压缩组，与DFS方法相比回溯的开销是由非顶点覆盖查询顶点的数量（即压缩组中映射集的数量）乘以数据图中的最大程度（即映射集的最大大小）。因此，压缩时的内存开销通常很小。对于YT2，Circinus的内存使用比CFL和GQL要少得多，因为Circinus避免了构建辅助数据结构（如4.2中所述）。CFL和GQL构建了用于计算重用的辅助结构，而YT2的辅助结构的内存占了90%以上的内存使用，因为YT2有一个偏态的标签分布。
图7b和图8报告了与图5b和图6对应的并行处理的内存使用峰值。从图7b中可以看出，基于压缩的解决方案（即环桂和环桂-cfl）在YT2上比基于dfs的解决方案（即游隼和LFTJ-环桂）有更多的内存使用，但它们在OR上的内存使用具有可比性。请注意，额外的内存使用并不仅仅是由于压缩，因为Circinus和LFTJ在单线程情况下具有类似的内存使用情况（图7a），但这也是因为Circinus中的并行化机制。当一个线程变得空闲并试图从其他线程窃取工作时，Circinus会使运行时间最长的任务一次生成多个组。由于YT2有一个偏态分布，线程之间的负载往往是不平衡的。因此，任务分裂发生得更频繁，并产生许多组，从而导致更高的内存开销。然而，如图8所示，与BFS方法（即PBE重用）相比，基于dfs的方法(Circinus对于较小的图（YT、LJ，OR）的内存使用可以忽略不计，而对于大图FR的内存使用也明显较小。我们没有在图8中报告CBF的内存使用情况，因为它在开始时为容器分配了所有内存，并且CBF有非常高的内存需求以及磁盘I/O使用情况来处理BFS中的大量中间结果。因此，我们可以得出基于压缩的方法的内存开销是合理的，Circinus实现了内存效率和计算共享的目标。
在下面的部分中，我们将关注标记查询，因为只有少量的未标记查询的处理时间是可以接受的，也就是说，只有某些小的查询图，而大多数查询使用任何现有方法进行处理都很昂贵。

5.3 Effectiveness of Redundancy Reduction

在这组实验中，我们首先证明了圆轮的性能增益主要来自于冗余计算的减少。然后，我们展示了哪些查询大小和数据集的冗余减少更有效。我们计算每种情况下所需的集合交集的数量。圆轮和基线之间的交集计数的差异反映了保存的计算。
减少冗余的影响。图9报告了C GQL、C GQL GQL、C GQL、CFL和GQL的回溯时间（不包括计划和候选生成的时间）和交叉计数。图9a中的回溯时间模式与图9b中的交集计数相似，表明交集计数对回溯时间有直接影响。需要注意的是，Circinus-CFL/GQL采用了与CFL/GQL相同的候选过滤策略和匹配顺序，这导致了类似的回溯搜索空间。交集计数的差异主要来自于Circinus的基于压缩组的回溯。结果表明，验证了基于压缩组的回溯是一种有效的冗余减少技术，是CFL和GQL性能提高的主要因素。
冗余减少程度。我们还评估了圆圈减少重复计算的程度。我们对标记查询using𝑄8运行CFL和GQL，对未标记查询𝑞1和𝑞3运行游隼。我们报告了图114中的交集计数和相应的最优交集计数，通过消除在回溯的每个级别上的所有重复计算，可以实现这些计数。我们已经讨论了第2节中的结果，以验证我们的观察结果。虽然使用基于dfs的方法很难实现最优数字，但与基线相比，Circinus有效节省了96.45%的冗余计算，标记情况下平均节省了87.30%的冗余计算。
对查询大小和数据图的敏感性。我们在Circinus中禁用了基于vc的组压缩，如图10中的Circinus表示，并评估了基于不同的组vc压缩对查询性能的影响。CFL和GQL的候选过滤和匹配顺序也被启用，如图10中𝑥轴上的CFL和GQL所标记。图10a-10d显示，在所有查询大小和数据图中，Circinus的性能显著优于Circinus，从而验证了基于vc的组压缩的有效性。结果还表明，减少的冗余度（即从圆环到圆环的交点计数的减少）有效地转化为圆环的性能增益（即缩短的回溯时间）。
图10b显示，基于vc的组压缩可以为更大的查询减少更多的交叉，这也导致图10a中的回溯时间更大的减少（注意，𝑦轴是对数尺度的）。图10d进一步显示，减少十字路口的更大的数据集（即FR）和数据集与倾斜标签分布（即YT2），和图10c显示查询这些数据集也更昂贵的过程和显著减少交集数量反映在一个巨大的减少回溯时间。

5.4 Influence of Vertex Covers

我们通过与一种使用输入查询图𝑞的最小权重VC进行压缩的替代方法（用图12中的MWVC表示）进行比较，来评估Circinus的VC选择方法的质量。MWVC通过相交于最小权重来计算𝑞的每个子查询𝑞𝑖的VC𝑞的顶点集为𝑞𝑖的顶点集。图12报告了MWVC和Circinus的回溯时间。Circinus在所有数据集和查询方面都优于MWVC。请注意，MWVC实际上优化了输出的压缩比。相比之下，圆轮选择风投的目标是设定交集的减少。

5.5 Sensitivity to 𝑐𝑎𝑟𝑑𝑞𝑖(𝑈 ) Estimation

我们比较了𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）的两种估计方法： (1)通过基于CFL和GQL构造的辅助数据结构，计算树状路径权值，用CFLPath和GQL-Path表示；(2)计算𝑈中查询𝑈中候选顶点的基数的乘积，用GQL积表示。为简单起见，这里我们使用CFL/GQL来引用Circinus-CFL/GQL。我们想证明一个简单而有效的估计方法，如乘积，也是有效的。
图13报告了在四个数据集上运行𝑄8和𝑄12的回溯时间。尽管使用路径权值来估计𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）比使用乘积更准确，但对于我们的目的来说，不那么准确的估计并不一定是不那么有效的。事实上，对于大多数查询，所选的VC序列使用其中的任何一种估计方法都是相同的。这是因为不同𝑈的𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）的差异主要由𝑈的大小决定，而不管使用的路径权重或产品，因为大多数查询顶点都有大量的匹配。因此，在方程1中，𝑐𝑎𝑟𝑑𝑞𝑖（𝑈∪{𝑢}）通常比𝑐𝑎𝑟𝑑𝑞𝑖（𝑈）大得多，因此最小化代价会导致选择一个更小的顶点覆盖𝑈，它与父顶点集𝑃有更多的交集。

5.6 Performance of Parallelization

我们通过将线程的数量从1改变到32来评估Circinus的性能，用于处理最大数据集FR上的查询集𝑄16。图14a报告了在单个线程上使用多个线程的执行时间的加速。Circinus实现了多达8个线程的几乎线性可伸缩性，然后加速速度从8个线程减慢到16个线程。可伸缩性的退化可以用我们的机器中的硬件来解释，它有16个物理内核（32个超线程），每个套接字有8个内核。当Circinus使用超过8个线程时，就使用了两个以上的套接字，因此性能会受到NUMA效应的影响。此外，当使用超过16个线程时，由于超线程，计算能力不会比使用更多的物理核增加那么多。
图14b报告了峰值内存消耗（标记为峰值）和用于存储输入图的内存（标记为图）。通过基于压缩组的回溯，Circinus在查询处理中实现了较小的内存使用（即，峰值和图之间的差异）。当线程从1增加到16时，峰值内存缓慢增加，当线程数进一步增加到32时，峰值内存保持在29.56GB左右。结果表明，循环性能稳定，内存使用量低。

6 RELATED WORK

图形挖掘系统。有几个图挖掘系统支持已标记/未标记的子图匹配[7,11,17,24,38,42,44]（在这里，我们排除了那些不支持子图匹配的图挖掘系统）。阿拉伯式的[38]提供了用于指定挖掘过程的高级api，并提出了“像嵌入一样思考”的概念。G-Miner [7]、G-思想家[44]和RStream [42]采用了类似于阿拉伯式的高级抽象。G-Miner提出了一个面向任务的处理框架来优化内存使用和提高处理速度。G-fisher为用户提供了一个直观的图形探索API来实现图形挖掘算法，并通过在基于磁盘的优先级队列中缓冲多余的任务来解决高内存使用问题。RStream是第一个单机、核外图挖掘系统，它具有一组关系代数操作，将挖掘任务表示为关系连接。正如在[24]中所指出的，上述四个系统由于其类似于BFS的执行方法，仍然存在很高的内存使用量，因此计算效率低下。AutoMine [24]、分形[11]和游隼[17]是最新的图形挖掘系统，它们采用了DFS方法来有效地使用内存。分形将“像嵌入一样思考”扩展到分形，以允许边缘诱导、顶点诱导的智能规划或模式诱导的执行。AutoMine提出了一种基于集的表示来节省空间，并为其代码生成的编译技术提供了基础。游隼提供了一个基于反边/顶点语义的基于模式的编程模型。游隼也采用了AutoMine的集合表示。在这些系统中，游隼和分形利用自同构消去来减少子图匹配的计算冗余。我们在第5节中比较了Circinus和游隼，因为它是一个最近的图形挖掘系统，并已被证明优于其他系统[7,11,38,42]。
子图匹配系统和算法。与图挖掘系统相比，专门的子图匹配系统提供了更复杂的优化。图零[23]利用群理论改进了自挖掘来打破查询图中的对称性，以实现自同构消除。它允许通过要求更高程度的顶点具有更小的id来对任意模式进行方向优化。GraphPi [34]通过生成多个自同构消除的偏阶改进了图零，并使用代价模型联合选择匹配的阶和偏阶。GraphPi还在顶点集上使用包含-不相容原理来优化子图计数。PBE [12]和穿山甲[8]利用GPU来加速计算。穿山甲提出了一种用于GPU处理的高级扩展-简化-过滤器模型，并使用了一种基于BFS的方法来利用GPU的并行性。PBE建议分区数据图和共享执行方法来找到分区间匹配。PBE-repes[13]通过基于缓存的方法扩展PBE重用集交叉结果，并提供了GPU和CPU多线程实现。HUGE [46]和aDFS [39]可以在BFS和DFS之间切换，以在内存效率和并行性之间取得平衡。HUGE是一个基于分布式连接的分布式框架，具有推拉混合通信模型。它侧重于优化分布式（散列和最坏情况下最优）连接操作。当需要更多的本地并行工作时，aDFS使用异步的基于dfs的回溯来绑定内存消耗，并在相同的回溯级别上切换到BFS。
目前已经提出了许多子图匹配算法。我们只讨论最相关的问题，并让读者参考最近的调查[36]。GQL[16]，Turbo𝑖𝑠𝑜[15]，CFL [3]，CECI [2]，DAF [14]和VEQ [20]通过遵循“预处理-枚举”[36]方法来修剪回溯搜索空间来支持标记查询。它们首先使用各种过滤规则为每个查询顶点生成一个候选集，然后构建一个辅助数据结构，它由对应于查询边的二部图组成。在辅助数据结构的基础上，采用启发式方法选择匹配顺序并进行回溯。Turbo𝑖𝑠𝑜根据顶点邻域集的等价性来压缩查询图，以进行重用计算。Boost𝑖𝑠𝑜[30]通过压缩基于邻集等价集的数据图，以减少计算冗余。SEED [21]和CBF [28]支持遵循基于连接的方法[1]的无标记查询，并在MapReduce上实现。SEED在数据图中预先计算一组不重叠的团团来进行压缩，以避免部分匹配的物化。CBF提出了一种基于vc的压缩技术，以降低输出和存储子图匹配的成本，并通过连接边和团系来计算匹配。
与现有的子图匹配系统和算法相比，Circinus解决一个内在的问题重复计算基于回溯的子图匹配[2、3、11、12、14-17、23日，24、34、39、41、46]，我们在第5节表明，我们的方法明显优于最先进的方法[3,12,16,17,28,36]。Circinus也是一个通用的框架，它允许灵活地组合许多优化技术，来优化不同的数据集和查询集的处理。
使用压缩和顶点覆盖。Boost𝑖𝑠𝑜[30]和SEED [21]使用数据图压缩来减少计算冗余，但它们有很大的预处理成本，而且好处需要特殊的局部结构（例如，许多具有相似邻居或大的团的顶点）。圆圈减少计算预余不需要预处理，因为它在回溯过程中实时压缩部分匹配，因此可以用于动态图处理。游隼[17]使用VC来减少同构检查开销，CBF [28]使用最小的VC压缩输出子图以节省磁盘写入和存储成本，而PBE [12]使用VC来延迟部分匹配的物化。他们对VC的使用不同于Circinus，后者使用VC对部分匹配进行分组以进行计算共享，并取得了比第5.2节中报道的游隼、CBF和PBE更好的性能。
图形数据库系统。图数据库[6,10,29,37]支持同构或同态子图匹配的不同语义。它们采用属性图模型，并支持Cypher和Gremlin等查询语言。与上述同构子图匹配解决方案不同，其工作负载具有复杂的查询拓扑和密集的全图访问，属性图数据库是为具有选择性属性过滤器和简单查询拓扑的特征（例如，流行的LDBC基准测试）的工作负载设计的。因此，双方采用了非常不同的技术。具体来说，处理类似LDBC的工作负载的系统的性能在很大程度上取决于图形数据库的索引设计和图形布局。例如，Neo4J [37]支持单个或多个属性上的b-树索引，以加速顶点/边的检索。重构图[29]支持单属性索引。它通过边标签对图的邻接矩阵进行分区，并表示内存中CSR中的每个分区，以允许对具有特定标签的边进行快速的基于线性代数的遍历。TigerGraph [10]对属性图应用同态编码进行紧凑存储，允许快速的单顶点/边检索和索引更新。Grasper [6]在分布式集群中划分一个属性图，并通过基于RDMA的本地图存储设计优化对图拓扑和属性的访问。总之，虽然同构子图匹配解和图数据库的核心工作是相同的问题，但它们被设计用于处理具有不同特征的查询。

7 CONCLUSIONS

我们提出了一种子图匹配系统，它提供了一种新的基于压缩的方法来减少回溯过程中的计算冗余。该方法可与现有的优化技术结合应用，如CFL、GQL和 Peregrine。我们的实验结果表明，Circinus在保持低内存占用的同时显著减少了重复计算，这将转移到比最先进的解决方案更好的性能好几个数量级。文章来源地址https://www.toymoban.com/news/detail-775205.html

到了这里，关于【论文阅读】Circinus: Fast Redundancy-Reduced Subgraph Matching的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！