More Than Pivot for Maximal Clique Enumeration

The Maximal Clique Enumeration (MCE) problem is a classic and fundamental task in graph data mining and analysis. It has attracted widespread attention due to its broad applications in areas such as social network analysis and bioinformatics. A widely adopted framework for solving the MCE problem is the Bron-Kerbosch (BK) algorithm. Its efficiency can be significantly improved by incorporating the pivot strategy, which is the most effective pruning technique in BK-based algorithms. However, the pivot strategy is not an optimal solution for reducing search branches, and there remains room for further pruning unnecessary branches. To fill this gap, we propose a new heuristic pruning algorithm, called moreThanPivot, which focuses on further reducing search branches in the BK framework. This algorithm iteratively selects multiple vertices as splitters. For each splitter, the algorithm constructs its Residual Cover Set and Residual Pillar Set, ultimately returning refined search branches with fewer branches than the pivot strategy. Three alternative selection ranges and three greedy objectives are further proposed for selecting new splitters. Extensive experimental results on 14 real-world datasets demonstrate the superiority of our method. And experiments on synthetic datasets reflect that our method is especially effective on graphs with high edge density.