Listing k-cliques plays a fundamental role in various data mining tasks, such as community detection and mining of cohesive substructures. Existing algorithms for the k-clique listing problem are built upon a general framework, which finds k-cliques by recursively finding \((k-1)\) -cliques within subgraphs induced by the out-neighbors of each vertex. However, this framework has inherent inefficiency of finding smaller cliques within certain subgraphs repeatedly. In this paper, we propose an algorithm DIST for the k-clique listing problem. In contrast to existing works, the main idea in our approach is to compute each clique in the given graph only once and store it into a data structure called Induced Subgraph Trie, which allows us to retrieve the cliques efficiently. Furthermore, we propose a simple yet effective technique to prune search space based on a novel concept called soft embedding of binomial tree, which further improves the running time. We show the superiority of our approach in terms of time and space usage through comprehensive experiments conducted on real-world networks; DIST outperforms the state-of-the-art algorithm by up to two orders of magnitude in both single-threaded and parallel experiments.
