Scaling Up k-Clique Densest Subgraph Detection

In this paper, we study the 𝑘-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of 𝑘-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the 𝑘-cliques, which are not scalable to handle large 𝑘 values on large-scale graphs. In this paper, by utilizing the idea of "pivoting", we propose the SCT * -Index to compactly organize the 𝑘-cliques. Based on the SCT * -Index, our SCTL algorithm can directly obtain the 𝑘-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL * that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited 𝑘-cliques, respectively. As evaluated in our experiments, SCTL * significantly outperforms existing approaches by up to two orders of magnitude. In addition, we propose a sampling-based approximate algorithm that can provide reasonable approximations for any 𝑘 value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.