BLITZ：一个灵活高效的图挖掘系统

《IEEE Transactions on Knowledge and Data Engineering》：BLITZ: A Flexible and Efficient Graph Mining System

图模式挖掘（GPM）面临高计算成本、扩展性不足等问题，本文提出gDAG模型与BLITZ系统，通过路径合并和快速计数优化技术，实现平均10倍提速，显著降低执行时间，并为未来研究提供框架。

　　

摘要：

图模式挖掘（Graph Pattern Mining, GPM）对于揭示图数据中的复杂模式和关系至关重要，其应用范围涵盖社交网络分析、生物信息学和推荐系统等领域。然而，现有的GPM系统面临诸多挑战，包括高计算成本、有限的扩展性以及处理大型数据集时的效率低下。这些系统可以分为两大类：以嵌入为中心的系统（embedding-centric systems），它们难以应对搜索空间的指数级增长；以及以模式为中心的系统（pattern-centric systems），这些系统往往无法充分利用输入模式的潜力。尽管这两种方法各有优势，但在理解它们之间的比较局限性和影响性能的具体瓶颈方面仍存在重要的研究空白。为了解决这些问题，我们提出了gDAG模型，这是一个统一了这两种计算过程的新型框架，能够进行全面性能分析。gDAG模型是我们BLITZ系统的基础，该系统结合了诸如路径合并（path merging）和快速计数（quick counting）等创新优化技术。实验结果表明，与现有方法相比，BLITZ在挖掘时间上平均提升了10倍，显著缩短了执行时间。此外，BLITZ不仅改善了执行效率，还为未来的研究提供了坚实的框架。

引言

图模式挖掘（GPM）对于从复杂的图结构中提取有意义的见解至关重要。其应用领域非常广泛，包括生物学[5]、欺诈检测[31][45]、计算机视觉[12]以及社交网络分析[34][48]等。GPM的目标是在数据图中识别用户指定的模式的嵌入表示。嵌入被定义为与同构的子图。然而，由于搜索空间庞大，执行GPM任务可能会耗费大量计算资源，尤其是在处理大规模数据图时[22]。例如，现有的GPM系统可能需要数小时才能处理具有复杂模式的大型图，这在时间敏感的应用场景（如欺诈检测）中构成了重大挑战。