Weisfeiler-Lehman graph features improve algorithm choice for constraint problems
Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation
Machine LearningArtificial Intelligence
Summary
Choosing the right algorithm for solving constraint problems can be tricky because existing methods rely on simple statistics that miss deeper problem structures. The authors use a technique involving graphs and the Weisfeiler-Lehman (WL) test to automatically create better features that capture the problem’s structure. Their new 'cut-based' WL features help predict which algorithm will perform best, doing better than some traditional features on test cases from recent competitions. This approach works well with various machine learning models like support vector machines and random forests.
What this means in practice
- •For constraint programming engineers: Improve automatic selection of solving algorithms by using WL-based structural features to better capture problem instance characteristics.
- •For machine learning practitioners: Develop better feature sets for predictive models in combinatorial optimization domains by employing graph kernels that capture structural patterns.
Authors
Alessio Pellegrino, Jacopo Mauro
Abstract
Algorithm Selection is essential for efficient Constraint Programming. Over the years, many algorithm selectors based on machine learning methods have been successfully applied, yet traditional feature extraction methods often rely on manually decided instance-level statistics that fail to capture the underlying problem structure. In this paper we aim to bridge this gap by introducing a novel, automated feature extraction methodology that integrates graph conversion and Weisfeiler-Lehman graph kernels to generate robust structural representations of problem instances. The 1-WL test bounds the graph-distinguishing power of standard message-passing Graph Neural Networks (GNNs), and suitable GNN architectures match this bound \citep{Xuetal2018}. WL-based features offer an alternative that does not require training a GNN. Our primary contribution is a cut-based representation (\texttt{WLc}) designed to model structural partitions and provide a more nuanced predictive signal. We evaluate our approach on instances from the 2023--2025 MiniZinc Challenges across two tasks: maximizing Borda count scores and maximizing predictive accuracy. Experimental results across Support Vector Machines, Random Forests, and Multi-Layer Perceptrons demonstrate that cut-based features outperform \texttt{fzn2feat} with SVMs, while results with RFs and MLPs are closer.