Machine Learning Selects Optimal Maximum Clique Solvers with 90% Accuracy

A new study on arXiv addresses a longstanding challenge in combinatorial optimization: selecting the right algorithm for the maximum clique problem based on instance characteristics.

The maximum clique problem (MCP)—finding the largest subset of vertices in a graph where every pair is connected—is a fundamental NP-hard problem with applications in bioinformatics, network analysis, and social computing. While multiple state-of-the-art solvers exist, no single algorithm dominates across all types of graphs.

The Dual-Channel Approach#

Rather than relying on one solver, the researchers propose GAT-MLP, a hybrid model combining:

• Graph Attention Networks (GAT): Captures local structural patterns in the graph
• Multilayer Perceptron (MLP): Models global topological features

Results#

The framework achieved 90.43% accuracy in selecting the optimal solver from a portfolio of four exact MCP algorithms. Key findings include:

• Connectivity and topological features are the strongest predictors of solver performance
• Random Forest established a competitive baseline among traditional classifiers
• The dual-channel architecture significantly outperforms any single solver choice

The researchers built their approach on a comprehensive benchmark dataset generated by running multiple state-of-the-art MCP solvers on diverse graph instances, extracting both structural features and solver performance data.

This work demonstrates that instance-aware algorithm selection—matching problems to solvers based on their characteristics—is feasible for complex combinatorial problems, potentially speeding up solutions across applications where maximum clique computations are critical.