# Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture

arXiv: https://arxiv.org/abs/2508.08005 · HTML: https://mlsanity.com/paper/2508.08005/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 11 Aug 2025.

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation](https://mlsanity.com/paper/2311.13184/) (2023)
- [Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage](https://mlsanity.com/paper/1302.6256/) (2013)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem](https://mlsanity.com/paper/2006.15968/) (2020)
- [Comparing Algorithm Selection Approaches on Black-Box Optimization Problems](https://mlsanity.com/paper/2306.17585/) (2023)
- [Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection](https://mlsanity.com/paper/1411.7460/) (2014)
- [Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks](https://mlsanity.com/paper/2302.04035/) (2023)
- [A Fast Maximum Clique Algorithm Based on Network Decomposition for Large Sparse Networks](https://mlsanity.com/paper/2404.11862/) (2024)
- [An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery](https://mlsanity.com/paper/2408.14022/) (2024)
- [An experimental survey and Perspective View on Meta-Learning for Automated Algorithms Selection and Parametrization](https://mlsanity.com/paper/2504.06207/) (2025)

## Abstract (arXiv)

Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local 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. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.