Discovery of δ-Tolerance Closed Subgraphs on GPGPU
Tatsuya Toki, Tomonobu Ozaki · 2017
Frequent subgraph mining, i.e. a complete enumeration of subgraph patterns frequently appearing in graph databases, often generates unmanageable number of patterns and requires a long computation time. In this paper, to solve these two essential drawbacks in subgraph mining at a time, we develop a GPU-based pattern miner for δ-tolerance closed subgraphs. The δ-tolerance closed subgraph is an extension of closed subgraph for handling noise, and it can represent closed and maximal subgraphs by setting the value of δ appropriately. A fundamental enumeration algorithm for δ-tolerance closed subgraphs consists of frequent subgraph enumeration, δ-transaction matching for checking the closedness and occurrence matching for the pruning. We develop a GPU-based algorithm for mining δ-tolerance closed subgraphs by incorporating δ-transaction and occurrence matching on GPU with an existing GPU-based frequent subgraph mining. The performance improvements are observed in intensive experiments using real and synthetic datasets.