Less is More: Faster Maximum Clique Search by Work-Avoidance
By: Hans Vandierendonck
Potential Business Impact:
Finds the biggest group of connected things faster.
The maximum clique (MC) problem is a challenging graph mining problem which, due to its NP-hard nature, can take a substantial amount of execution time. The MC problem is dominated by set intersection operations similar to Maximal Clique Enumeration, however it differs in requiring to find only a clique of maximum size. As such, key to the problem is to demonstrate efficiently that a particular part of the search space does not contain a maximum clique, allowing to skip over major parts of the search space. We present a number of techniques to optimize MC search in light of leaving major parts of the search space unvisited, including (i) an efficient, lazily constructed graph representation; (ii) filtering prior to initiating a detailed search; (iii) efficient early-exit intersection algorithms; (iv) exploiting algorithmic choice. These techniques result in a speedup of up to 38.9x compared to PMC, which is the most comparable algorithm, and a speedup up to 11x over MC-BRB.
Similar Papers
Engineering Algorithms for $\ell$-Isolated Maximal Clique Enumeration
Data Structures and Algorithms
Filters out unimportant groups in complex networks.
Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP
Machine Learning (CS)
Helps computers pick the best way to solve hard problems.
Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
Data Structures and Algorithms
Finds best solutions for hard computer puzzles faster.