Motif Counting

Application Description

This benchmark counts all connected k-motifs in an undirected graph. A k-motif is a pattern (template subgraph) with k vertices.

Algorithm

The algorithm is called extend-reduce. A initial worklist contains initial embedding (single vertex or edge). It extends each embedding with a vertex, and insert the new embeddings to the next worklist. Extension is repeated until the size of embedding is k. Each embedding is checked to identify its pattern, the corresponding counter is increased by 1.

Performance

We present timing on NVIDIA V100 GPU (32G memory) with k=3 and k=4

Graph	k=3 Time (s)	k=4 Time (s)
mico	0.02	7.0
patent_citations	0.09	5.4

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