  Counting k-cliques in a graph is an important problem in graph analysis with
many applications. Counting k-cliques is typically done by traversing search
trees starting at each vertex in the graph. An important optimization is to
eliminate search tree branches that discover the same clique redundantly.
Eliminating redundant clique discovery is typically done via graph orientation
or pivoting. Parallel implementations for both of these approaches have
demonstrated promising performance on CPUs. In this paper, we present our GPU
implementations of k-clique counting for both the graph orientation and
pivoting approaches. Our implementations explore both vertex-centric and
edge-centric parallelization schemes, and replace recursive search tree
traversal with iterative traversal based on an explicitly-managed shared stack.
We also apply various optimizations to reduce memory consumption and improve
the utilization of parallel execution resources. Our evaluation shows that our
best GPU implementation outperforms the best state-of-the-art parallel CPU
implementation by a geometric mean speedup of 12.39x, 6.21x, and 18.99x for k =
4, 7, and 10, respectively. We also evaluate the impact of the choice of
parallelization scheme and the incremental speedup of each optimization. Our
code will be open-sourced to enable further research on parallelizing k-clique
counting on GPUs.
