The Power of Core Clique Removal for Exact Clique Enumeration

Clique enumeration, including maximal clique enumeration and k -clique enumeration, is a fundamental problem in graph analysis. However, existing clique enumeration algorithms often struggle to efficiently handle complex real-world graphs. To address this issue, we propose a novel Core Clique Removal (CCR) technique that removes a large core clique from the original graph. After removing the core clique, the remaining graph is expected to become sparser. We show that the clique enumeration problem on the original graph can be reduced to the problem of enumerating cliques in the remaining sparser graph, thus reducing computational complexity. Building upon the CCR technique, we propose two innovative and efficient algorithms: CCRMCE for maximal clique enumeration and CCRKCE for k -clique enumeration. Both algorithms are non-trivial and offer substantial improvements over previous approaches. Our extensive experiments on 20 real-world graphs highlight the efficiency of our methods. CCRMCE demonstrates multiple times faster performance, while CCRKCE achieves an order of magnitude speedup compared to state-of-the-art algorithms.