{"ID":2883763,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.08005","arxiv_id":"2508.08005","title":"Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP","abstract":"The Maximum Clique Problem (MCP) is a foundational NP-hard problem with wide-ranging applications, yet no single algorithm consistently outperforms all others across diverse graph instances. This underscores the critical need for instance-aware algorithm selection, a domain that remains largely unexplored for the MCP. To address this gap, we propose a novel learning-based framework that integrates both traditional machine learning and graph neural networks. We first construct a benchmark dataset by executing four state-of-the-art exact MCP solvers on a diverse collection of graphs and extracting their structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Building on these insights, we develop GAT-MLP, a dual-channel model that combines a Graph Attention Network (GAT) to encode local graph structure with a Multilayer Perceptron (MLP) to model global features. Extensive experiments demonstrate that GAT-MLP achieves superior and consistent performance, significantly outperforming all baseline methods. Our results highlight the effectiveness of the dual-channel architecture and the promise of graph neural networks for combinatorial algorithm selection, achieving 90.43% accuracy in choosing the optimal solver. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.","short_abstract":"The Maximum Clique Problem (MCP) is a foundational NP-hard problem with wide-ranging applications, yet no single algorithm consistently outperforms all others across diverse graph instances. This underscores the critical need for instance-aware algorithm selection, a domain that remains largely unexplored for the MCP....","url_abs":"https://arxiv.org/abs/2508.08005","url_pdf":"https://arxiv.org/pdf/2508.08005v3","authors":"[\"Xiang Li\",\"Shanshan Wang\",\"Chenglong Xiao\"]","published":"2025-08-11T14:09:58Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.AI\"]","methods":"[\"Graph Neural Network\"]","project_urls":"[\"https://anonymous.4open.science/r/GAT-MLP-7E5F\"]","has_code":false}