This benchmark finds k-cliques in an undirected graph. A k-clique is a complete subgraph with k vertices.
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 (vertices). Each embedding is checked if it is a clique. If yes, the counter is increased by 1. No isomorphism test is needed.
We present timing on NVIDIA V100 GPU (32G memory) with k=4 and k=5
|Graph||k=4 Time (s)||k=5 Time (s)|
Please read the following paper for detailed performance evaluation:
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