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.
|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
Performance numbers are collected on a 4 package (14 cores per package) Intel(R) Xeon(R) Gold 5120 CPU machine at 2.20GHz from 1 thread to 56 threads in increments of 7 threads. The machine has 192GB of RAM. The operating system is CentOS Linux release 7.5.1804. All runs of the Galois benchmarks used gcc/g++ 7.2 to compile.