Logo image
Back
SampleMine: A Framework for Applying Random Sampling to Subgraph Pattern Mining through Loop Perforation
Conference proceeding   Open access

SampleMine: A Framework for Applying Random Sampling to Subgraph Pattern Mining through Loop Perforation

Peng Jiang, Yihua Wei, Jiya Su, Rujia Wang and Bo Wu
PACT '22: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, pp.185-197
01/27/2023
DOI: 10.1145/3559009.3569658
Appears in  UI Libraries Support Open Access
url
https://doi.org/10.1145/3559009.3569658View
Published (Version of record) Open Access

Abstract

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.
 loop perforation subgraph pattern mining UIOWA OA Agreement

Details

Metrics

7 Record Views
6 Times Cited - Web of Science
Logo image