SampleMine: A Framework for Applying Random Sampling to Subgraph Pattern Mining through Loop Perforation
SampleMine: A Framework for Applying Random Sampling to Subgraph Pattern Mining through Loop Perforation
复制标题
DOI：
10.1145/3559009.3569658
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Peng Jiang;Yihua Wei;Jiya Su;Rujia Wang;Bo Wu
中科院分区：
文献类型：
--
作者：
Peng Jiang;Yihua Wei;Jiya Su;Rujia Wang;Bo Wu
子图模式挖掘（SPM）是一类重要的图应用程序，旨在发现图中的结构模式。由于巨大的探索空间，SPM通常在计算上具有挑战性。为了加速SPM，已经提出了许多随机采样技术。虽然现有的采样技术是有效的传统SPM任务，如模体计数和频繁子图挖掘，他们不能很容易地适应新的应用程序。在这项工作中，我们提出了SampleMine，一个框架应用随机抽样到任何非上市SPM任务。我们的主要思想是将子图的探索表示为一个嵌套的循环，并对带有循环穿孔的子图进行采样。首先，我们提出了一个两个顶点的探索技术，以加快子图的探索过程。然后，我们提供了两个采样策略下的循环穿孔框架，并表明他们可以取得良好的结果计数和频繁子图挖掘任务。实验结果表明，我们的系统实现了显着的加速对国家的最先进的图挖掘系统的准确性损失很小。
Subgraph Pattern Mining (SPM) is an important class of graph applications that aim to discover structural patterns in a graph. Due to the enormous exploration space, SPM is in general computationally challenging. To accelerate SPM, many random sampling techniques have been proposed. While the existing sampling techniques are effective for conventional SPM tasks such as motif counting and frequent subgraph mining, they cannot be easily adapted for new applications. In this work, we propose SampleMine, a framework for applying random sampling to any non-listing SPM task. Our main idea is to express subgraph exploration as a nested loop and sample the subgraphs with loop perforation. We first propose a two-vertex exploration technique to accelerate the subgraph exploration procedure. Then, we provide two sampling strategies under the loop perforation framework and show that they can achieve good results for counting and frequent subgraph mining tasks. The experimental results show that our system achieves significant speedups against the state-of-the-art graph mining systems with little accuracy loss.