A heuristic approach to optimise accuracy and performance in the maximum weight clique

A fundamental characteristic of QClique is its tunable parameter that trade-off between accuracy and execution time, making it flexible enough to accommodate wide-range application requirements and computational limitations. Three distinct variations of the MWC problem are examined using the QClique algorithm (QClique-V, QClique-E and QClique-T): The Maximum Vertex-Weighted Clique Problem (MVWCP), the Maximum Edge-Weighted Clique Problem (MEWCP)and the Maximum Total-Weighted Clique Problem (MTWCP).

QClique-V applied to the MVWCP achieves an average speedup of 9.8 to 82.3 times compared to both the previous state-of-the-art approximate and exact MVWCP algorithms. It also maintains an accuracy range of 79% to 100%. In the MEWCP, QClique-E achieves an average speedup of 80.7-976.5 times while keeping an accuracy range of 70% to 100% compared to the current exact algorithms.

QClique-T was introduced and further optimised in the MTWCP case. When compared to its initial version, the optimised version provides an average speedup of 3.8 times while maintaining100% accuracy. The limitations on the accuracy of QClique are addressed by introducing a technique to accelerate exact MWC algorithms.

QClique significantly decreases runtime by providing a near-optimal initial clique, which primes exact MWC algorithms to explore only promising regions. This approach accelerates a state-of-the-art exact MWC algorithm, by 5.2 times, on average. The incorporation of QClique-V into the GABI algorithm reveals new factors in kidney, breast, and ovarian cancers, illustrating its practical importance.

It helps to investigate the clinical outcomes that are important to do survival analysis of cancer patients. QClique solves the MVWCP instances that occur in GABI 12 times faster than the existing state-of-the-art exact algorithm while achieving 100% accuracy.