k-Clique Listing

Application Description

This benchmark finds k-cliques in an undirected graph. A k-clique is a complete 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 (vertices). Each embedding is checked if it is a clique. If yes, the counter is increased by 1. No isomorphism test is needed.

Performance

Graph	k=4 Time (s)	k=5 Time (s)
mico	0.9	34.9
patent_citations	0.4	0.5

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

Machine Description

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.