T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph
T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph
复制标题
DOI：
10.1145/3588928
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Lyuheng Yuan;Da Yan;Wenwen Qu;Saugat Adhikari;J. Khalil;Cheng Long;Xiaoling Wang
中科院分区：
文献类型：
--
作者：
Lyuheng Yuan;Da Yan;Wenwen Qu;Saugat Adhikari;J. Khalil;Cheng Long;Xiaoling Wang
在一个大图中寻找频繁子图模式是一个重要的问题，在许多应用中，如分类化合物和建立索引，以加快图查询。由于这个问题是NP难的，最近已经开发了一些并行系统来加速挖掘。然而，它们通常具有巨大的内存开销、非常长的运行时间、次优的负载平衡以及可能不准确的结果。在本文中，我们提出了一个高效的系统称为T-FSM的并行挖掘的频繁子图模式在一个大的图。T-FSM采用新颖的基于任务的执行引擎设计，确保高并发性、有限的内存消耗和有效的负载平衡。它还支持一种名为Fraction-Score的新反单调频率度量，该度量比广泛使用的MNI度量更准确。我们的实验表明，T-FSM是数量级的速度比SOTA系统的频繁子图模式挖掘。我们的系统代码已在https://github.com/lyuheng/T-FSM上发布。
Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, and possibly inaccurate results. In this paper, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM adopts a novel task-based execution engine design to ensure high concurrency, bounded memory consumption, and effective load balancing. It also supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. Our experiments show that T-FSM is orders of magnitude faster than SOTA systems for frequent subgraph pattern mining. Our system code has been released at https://github.com/lyuheng/T-FSM.