Authors: Kalsuda Lapborisuth, Rajarshi Ghoshal, and Srinivas Aluru (Georgia Institute of Technology)
Abstract: We propose a new parallel algorithm for k-clique counting, a fundamental primitive in graph analytics. The state-of-the-art algorithm combinatorially counts k-cliques within maximal cliques to reduce the search tree size. However, its parallel performance degrades rapidly with clique size, due to (1) wasted work exploring subproblems that contain no k-cliques, and (2) load imbalance from highly irregular subproblem sizes. We introduce a hierarchical BFS-based algorithm, Calico, that restricts the search to a reduced edge set. To mitigate load imbalance, Calico also limits search tree depth by reformulating dense subproblems as counting independent sets on their corresponding complement graphs. Calico achieves up to 16,631× speedup over parallel baselines with scaling up to 192 cores on large real-world graphs. Calico is the first to count k-cliques of any specified size on the previously intractable com-LiveJournal graph, reducing the reported runtime from approximately 62 hours (k ≤ 13) to under 14 seconds.
Presentation: file