BEE：通过块分隔分解减少子图匹配中的冗余

《Proceedings of the ACM on Management of Data》：BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching

针对子图匹配中的冗余搜索问题，提出BEE方法，通过块分隔符分解和块参考结构优化，有效检测全局与局部冗余，实验证明其性能显著优于现有算法。

　　

摘要

子图匹配是图分析中的一个基本问题，已经开发了许多算法来减少回溯搜索过程中的冗余。然而，现有的冗余检测方法在适用范围上存在局限性，因为它们主要针对局部冗余（例如搜索树中的兄弟节点），并且依赖于完全层级剪枝（只有当子树完全相同时才会被删除），这限制了它们的整体效率。为了解决这些限制，我们提出了一种新的回溯方法，即BEE，该方法通过块分隔器分解来最小化回溯过程中的重复搜索。BEE能够有效检测和消除全局范围内的冗余以及部分范围内的冗余。我们对子图匹配的块分隔器树优化问题进行了形式化描述，并证明了其NP难度。因此，我们开发了一种高效的贪心算法，将查询图分解为更小的块，从而能够检测到更细粒度的冗余。此外，我们还提出了一种块引用结构，该结构在检测到冗余时能够通过检索嵌入信息来有效减少重复搜索。大量的实验结果表明，BEE的性能显著优于现有的最先进算法，在EPS（每秒嵌入次数）指标下实现了多个数量级的加速。