Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP — what it means for business leaders

A dual-channel AI selector that learns from both global and local graph features to choose the fastest exact solver for the Maximum Clique Problem — reducing runtimes and stabilizing performance across diverse networks.

1. What the method is

The paper presents a learning-based framework that predicts the best-performing Maximum Clique Problem (MCP) solver for each input graph. The approach benchmarks four state-of-the-art exact algorithms, then uses their performance on a diverse dataset to train classifiers. Its flagship model, GAT-MLP, combines a Graph Attention Network that captures local topological patterns with a multilayer perceptron that processes 12 global statistical features. The two channels’ outputs are fused to score candidate solvers, enabling instance-aware routing that outperforms one-size-fits-all execution strategies.

2. Why the method was developed

No single MCP solver dominates across all graph types — dense, sparse, modular, or irregular — forcing costly trial-and-error. Other domains (SAT solving, TSP) have benefited from algorithm selectors, but MCP lacked a dedicated, data-driven solution. The authors designed this method to cut compute cost, avoid long-tail slowdowns, and maintain optimality by picking the right solver up front. Their dual-channel architecture addresses classical ML’s blind spots on local structures, aiming for high predictive accuracy and cross-domain generalization.

3. Who should care

Leaders in sectors using graph analytics — from fraud detection and cybersecurity to bioinformatics and social network analysis — gain faster, more predictable exact clique computations. MLOps and platform teams benefit from automated, per-instance solver selection that manages latency and compute budgets. Researchers and vendors embedding combinatorial optimization into products can adapt the dual-channel design to other NP-hard graph problems with algorithm performance variability.

4. How the method works

The process starts with collecting graph instances and extracting both global metrics (node/edge counts, density, clustering, k-core stats) and per-node features (degree, core number). Each instance is labeled with the solver that finds the largest clique fastest. Classical ML baselines (SVM, RF, KNN, DT) and the proposed GAT-MLP are trained to map features to solver choice. In GAT-MLP, a two-layer GAT encodes local structure; an MLP encodes normalized global features; their embeddings are concatenated and classified. Training uses Adam with dropout and early stopping, and inference runs only the predicted solver.

5. How it was evaluated

The authors built a dataset of 574 labeled graphs from benchmarks (DIMACS, BHOSLIB, CSPLIB) and miscellaneous networks, covering 28 to 55k nodes and densities from <0.001 to ~1.0. Four MCP solvers were run per graph under strict time limits to establish ground truth. Models were compared by accuracy, Macro-F1, and Weighted-F1. RF was the strongest classical baseline; feature importance analysis confirmed density, average degree, and k-core number as key predictors. The dual-channel model was also benchmarked against ablations removing one branch or replacing GAT with a GCN.

6. How it performed

GAT-MLP achieved 89.13% accuracy, Macro-F1 of 0.6801, and Weighted-F1 of 0.8694 — the best across all tested models. Removing either the structural or statistical branch significantly degraded performance, confirming their complementarity. The approach delivered large runtime savings on hard instances by routing them to the optimal solver, offering both speed and stability in production contexts. (Source: arXiv 2508.08005, 2025)