论文导读 | 子图匹配最新进展

图谱学苑 2025-05-13

453

前言

子图匹配问题是图算法领域经久不衰的研究问题，它是图分析系统的基石。该问题定义为：给定数据图和查询图，找到中所有与匹配的子图。下图展示了一个子图匹配的例子。查询图存在两个匹配。

子图匹配算法一般分为 3 个步骤，分别是过滤，搜索顺序生成以及匹配枚举。其中过滤过程会通过特定的过滤规则获得每个查询节点的候选集。接着算法会根据查询图拓扑结构以及一些估计技术生成搜索顺序，用于指导枚举过程。最终，枚举过程搜索出所有的匹配。

下图展示了一个子图匹配的搜索流程：

在去年的报告中，有同学已经报告了一篇关于子图匹配的综述 [1]。这篇综述详细介绍了截止至24年的子图匹配算法和技巧。因此，本次报告的内容为这篇综述之后的子图匹配的最新进展。

BICE

这篇工作发表在 vldb‘23 上。该篇工作的核心思路是使用二分图匹配在搜索过程中进行剪枝。算法会在搜索过程中维护一个二分图，该二分图的左部是查询节点，右部是数据节点节点。如果左部的查询节点和右部数据节点有连边说明该数据节点是查询节点的候选节点。下图为展示了一个例子：其中查询图 u1 的候选集为 {v1,v2}, 因此二分图中查询节点 u1 连向 v1 和 v2。

不难看出，当子图匹配存在时二分图的最大匹配的大小要等于 Q 的节点数。因为该子图匹配对应了一个二分图的最大匹配。基于这样的思路， BICE 在搜索过程通过二分图进行剪枝。继续上图的例子，假设搜索顺序为 u1,u2,u3,u4,u5，当我们搜索到部分匹配 {v1,v3,v5} 时，由于 u1,u2,u3 的取值固定了，因此我们在二分图中固定它们匹配边。我们用绿色表示这样的匹配边，此时我们只需要看 u4 和 u5 能否得到匹配。然而，u5 唯一的可能匹配节点 v3 被u2 占用了。因此，这个部分匹配不可能拓展成完整的匹配，该分支就可以被剪掉了。

基于这个思路，在搜索过程中，每次确定一个查询节点的取值，我们只需要固定住对应的匹配边。然后在更新的图上进行二分图匹配，通过最大匹配大小判断能够进行剪枝。

基于二分图的剪枝技术还可以和 failing set [2] 技术进行结合。并且本篇工作还使用了搜索合并的技术，这个技术类似于 [3] 中的工作。由于篇幅原因，我们不展开进行介绍了。

在实验方面 BICE 在大部分的情况下都能够有比较好的效果。然而在小部分情况下不如 VEQ [2] 算法或者 Rapidmatch [4] 算法。这是因为当平均度数高的时候，二分图的过滤效果并不好，并且二分图此时很大，维护代价很高。

IVE

该篇工作发表在 ICDE’24 上。该篇工作的核心思路是最大化孤立节点，来减少搜索过程中需要指数级枚举的部分。孤立节点定义为：给定查询图和搜索顺序，没有后向边的节点。其中对于一个节点，后向边是指从它出发连向搜索顺序在它之后的节点的边。例如下图中，1，3，4，6 就是孤立节点。

当我们枚举完非孤立节点的部分匹配，孤立节点的可匹配节点集合就被固定了。此时，我们只需要判断孤立节点的候选点的选取会不会有冲突的情况，判断这个只需要构建孤立节点对应的二分图（类似 BICE），然后求最大匹配即可。通过这种方式，我们只需要枚举非孤立节点的部分匹配，因此时间复杂度的指数下降到了非孤立节点的数量。事实上，为了得到完整的匹配，我们还是需要进行孤立节点的匹配枚举。

显然，孤立节点的数量取决于搜索顺序。因此，这篇工作提出了一个启发式算法尝试获得一个搜索顺序最大化孤立节点的数量。该算法每次会选去度数最大的节点，把该节点加入搜索顺序中，并且将它从查询图中删去。接着，算法会在残留的查询图中重复该步骤，直到搜索顺序被确定。

以下是该篇工作的实验，可以看到 IVE 的效果超过了其它的子图匹配的算法。

BSX

最后一篇工作发表在 SIGMOD‘25。这篇工作采用批量的搜索策略，算法每次搜索的结果不再是单个匹配而是一批匹配。为了实现批量搜索，这篇工作提出了 box 的概念：给定一个查询图， box 包含个集合，每个集合是对应查询节点的候选点集合，我们使用来表示 box 中的候选集。box 和 filter 阶段得到结果类似。接着，我们定义对称的概念：对于一个查询节点，如果和都属于，并且在 box 内有相同的邻居，那么这两个节点就是对称的。显然，如果两个节点对称，那么对于包含的任意子图同态匹配都可以将其中的替换成。基于以上概念，我们再定义正交的概念：对于一个查询节点 , 如果中的节点都互相对称，那么该查询节点是正交的。基于正交的概念，我们可以进一步得到一个有用的推论：如果所有查询节点都是正交的，那么都是同态匹配。下图展示了一个例子：假设 box 为。此时所有查询节点都是正交的，因此是所有的同态匹配。

因此 BSX 算法就是搜索出所有每个查询节点都正交的 Box。

BSX 通过几何的思想将 Box 映射到高维空间中，并在这种语义下设计了搜索流程。下图是 BSX 的搜索流程。初始化时，BSX 将 filter 的结果作为初始的 box。在每次递归时，BSX 会选取 box 中一个没有正交的维度，然后从中抽取出一个正交的子集，作为新的 box。接着，子集抽取可能会导致相邻的维度的候选集的不再满足候选集的条件。因此，BSX 进行了过滤，删除了不合法的候选节点。重复以上步骤，直到 box 的每一维都正交。

在维度选择的时候，BSX 只会选取非正交的维度。除此之外，BSX 会通过最大独立集算法将查询节点分成主动的和被动的。被动的维度会通过主动的维度来影响到。因此 BSX 只会选取主动的维度。在这种情况下，BSX 再优先选取具有最小候选集。如果具有多个节点维度满足，BSX 就会优先选取连接到更多主动维度的维度。

搜索过程中的过滤类似于预处理阶段的过滤过程，找到所有并删去不合法的候选节点。

文章还有一些实现上的细节：例如，由于要求选取的子集要求是正交的过于严格，因此设置参数来调节选取子集的过程。还有通过设置参数来调节过滤阶段的耗时等。由于篇幅关系，不进行展开。

以下是实验结果， BSX 能够在吞吐量的指标下大幅度提升子图匹配的效率。

参考文献

[1] Zhang, Zhijie, et al. "A comprehensive survey and experimental study of subgraph matching: trends, unbiasedness, and interaction." Proceedings of the ACM on Management of Data 2.1 (2024): 1-29.

[2] Han, Myoungji, et al. "Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together." Proceedings of the 2019 international conference on management of data. 2019.

[3] Kim, Hyunjoon, et al. "Versatile equivalences: Speeding up subgraph query processing and subgraph matching." Proceedings of the 2021 international conference on management of data. 2021.

[4] Sun, Shixuan, et al. "Rapidmatch: A holistic approach to subgraph query processing." Proceedings of the VLDB Endowment 14.2 (2020): 176-188.

[5] Lu, Yujie, Zhijie Zhang, and Weiguo Zheng. "BⓈ X: Subgraph Matching with Batch Backtracking Search." Proceedings of the ACM on Management of Data 3.1 (2025): 1-27.

[6] Choi, Yunyoung, Kunsoo Park, and Hyunjoon Kim. "Bice: Exploring compact search space by using bipartite matching and cell-wide verification." Proceedings of the VLDB Endowment 16.9 (2023): 2186-2198.

[7] Jiang, Zite, et al. "Ive: accelerating enumeration-based subgraph matching via exploring isolated vertices." 2024 IEEE 40th International conference on data engineering (ICDE). IEEE, 2024.