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

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

Graph	k=4 Time (s)	k=5 Time (s)
mico	0.1	8.8
patent_citations	0.02	0.03

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