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
Algorithm Selection for the Maximum Clique Problem: Using Machine Learning and Graph Neural Networks
Wu, Wang, Xiao · 2026 · Subscription
NobleIDark:/48914/w1/20261105/4B23A87DDOI10.22541/authorea.15007850/v1
The full text is at the publisher
You can read the abstract here, or open it 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.