Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel automated feature extraction methodology for algorithm selection in Constraint Programming, leveraging Weisfeiler-Lehman (WL) graph kernels to capture problem instance structure. By employing a cut-based representation (\texttt{WLc}) derived from the 1-WL test, the approach generates robust structural features without requiring GNN training. Experiments on MiniZinc Challenge instances show that \texttt{WLc} features outperform traditional instance-level statistics with SVMs, indicating improved predictive power for algorithm selection.
Weisfeiler-Lehman graph kernels unlock superior structural features for algorithm selection, outperforming traditional methods on challenging constraint satisfaction problems.
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.