NobleBlocks

Research indexPreprint

Algorithm Selection for the Maximum Clique Problem: Using Machine Learning and Graph Neural Networks

Wu, Wang, Xiao

25 Aug 2026

NobleIDark:/48914/w1/20261105/4B23A87DDOI10.22541/authorea.15007850/v1

Paywalled

The full text is at the publisher

You can read the abstract here, or open it at the publisher.

Read at the publisher

Abstract

The Maximum Clique Problem (MCP) is a core NP-hard problem in graph theory with critical applications in bioinformatics, social network analysis, and combinatorial optimization. Although advanced algorithms like CliSAT and MoMC perform well on specific instances, no single solver achieves consistently optimal performance across all cases, particularly under strict runtime constraints. This variation underscores the necessity of an intelligent algorithm selection framework to dynamically recommend the most efficient solver. To our knowledge, this work presents the first comprehensive study on algorithm selection specifically tailored for the MCP. We address this research gap by developing a novel predictive framework that integrates traditional machine learning classifiers with advanced graph neural network (GNN) architectures. Beyond conventional classification accuracy, we evaluate our models using cost-sensitive business metrics, including Penalized Average Runtime (PAR2) and Success Rate. Our experimental results demonstrate that GNN-based selectors significantly outperform traditional ensemble methods by directly exploiting graph topology through message passing and adaptive neighborhood aggregation.

Discussion

More

Suggest a correction or report