Frequent Subgraph Mining

Application Description

This benchmark finds frequent subgraphs in an undirected graph. Arguments: k, the maximum size of subgraphs, i.e., k-1 edges; minsup, minimum support, i.e., the threshold of support of frequent patterns.

Algorithm

The algorithm is called extend-reduce. A initial worklist contains initial embedding (single edge). It extends each embedding with an edge, and insert the new embeddings to the next worklist. Extension is repeated until the size of embedding is k-1 (edges). Each embedding is checked to identify its pattern, and the domain support (MNI) is accumulated into the support map. The patterns with support below threshold are removed at the end of each extension, as well as all their embeddings.

Performance

We present timing on NVIDIA V100 GPU (32G memory) with k=2 and minsup=300

Graph	Time (ms)
mico	0.6
patent_citations	2.7

Please read the following paper for detailed performance evaluation:

(VLDB 2020) [PDF] [Code]
Xuhao Chen, Roshan Dathathri, Gurbinder Gill, Keshav Pingali,
Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU,
PVLDB, 13(8): 1190-1205, 2020