Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation

Alessio Pellegrino; Jacopo Mauro

cs.LGOct 8, 2026

Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation

Authors: Alessio Pellegrino, Jacopo Mauro

Organizations: University of Southern Denmark, Denmark

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.

Figures & tables

Panel of Figure 1 — Figure 1 : Conversion of a constraint model (left) to a graph (right). Variables in yellow, Parameters in blue, Operators in red, Constraints in purple, and Solve in green. The area in gray represents the constraint 3*x <= y . Lead edges are labelled as L, Trailing as T and Global as G.

Figure 2 : Feature extraction process using the WL algorithm on a simple, undirected graph. The colour refinement is executed only once. At first, all nodes get the same colour, then node A aggregates its colour (blue) with its 3 neighbours’ colours (blue), getting, as a result, (blue, blue,blue,blue). This produces a new colour, red. C and D, having only two neighbours, get, as aggregation (blue, blue,blue), resulting in the new colour yellow and, finally, node B, having only one neighbour, aggregates to (blue, blue), getting as new colour orange. In the final steps, we count the number of occurrences of each colour, and we get 4 blues from the original initialisation and 1 red, 1 orange and 2 yellow after the first aggregation step.

Figure 4 : Performance results for SVM models trained on WL -based and fzn2feat features for the Borda count maximization task. Scores (top) are normalized as

S_{norm}=\frac{S-S_{sbs}}{S_{vbs}-S_{sbs}}

, where

S

is the model score,

sbs

is the Single Best Solver, and

vbs

is the Virtual Best Solver.

Figure 5 : Comparative performance of cut-based features ( WLc-n/WLc-ne ) against the fzn2feat baseline for the Borda count maximization task. Scores are normalised relative to the Single Best Solver and Virtual Best Solver. Results on the left are obtained by training RF models, while those on the right are obtained by training MLPs.

	Mean	Median
fzn2feat	0.45	0.47
Wlc-n-1	0.48	0.51
Wlc-n-2	0.47	0.50
Wlc-ne-1	0.46	0.51
Wlc-ne-2	0.48	0.48

Table 1 : Mean and median results of cut features and fzn2feat . Results show the best performing scores obtained using SVM for cut features and RF for fzn2feat .

Figure 6 : Predictive accuracy for SVM models trained on WL -based and fzn2feat features.

Figure 7 : Comparative performance of cut-based features ( WLc-n/WLc-ne ) against fzn2feat and the majority classifier (MC) baseline. Results on the left are obtained by training RF models, while those on the right are obtained by training MLPs.

	Mean	Median
fzn2feat	0.66	0.67
Wlc-n-1	0.69	0.68
Wlc-n-2	0.69	0.69
Wlc-ne-1	0.69	0.69
Wlc-ne-2	0.69	0.69

Table 2 : Mean and median results of cut features and fzn2feat . Results show the best performing scores obtained using SVM for cut features and RF for fzn2feat .

Figure 8 : Feature extraction cost comparison between WLc-n / WLc-ne and fzn2feat . The distribution of extraction times (left) is supplemented by pairwise performance comparisons (centre, right). The blue line corresponds to x = y.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Name	Type	Subtype	Is Cut	Is Global	Description
Variable	variable	–	No	No	Problem variable
Parameter	parameter	–	No	No	Literal value or parameter
Multiply	operator	mul_node	No	No	Multiplication operator
Linear Sum	operator	lin_sum_node	Yes	No	Weighted sum of variables
Sum	operator	sum_node	No	No	Sum operator
Equality	constraint	equality_node	No	No	Equality constraint

Appendix

Table 3 : Node types used in our graphs converted from FlatZinc.

Figure 10 : Results of all feature sets trained with the RF classifier on the Borda count maximisation task.

Figure 11 : Results of all feature sets trained with the MLP classifier on the Borda count maximisation task.

Figure 12 : Results of all feature sets trained with the RF classifier on the Algorithm Selection accuracy maximisation task.

Figure 13 : Results of all feature sets trained with the MLP classifier on the Algorithm Selection accuracy maximisation task.

Table 4 : Results of the ML models trained for Borda count maximisation on WL features with (all-levels) and without (last) all aggregation levels. Results report mean and median scores, as well as the p-value calculated with the Wilcoxon test.

Table 5 : Results of the ML models trained for algorithm selection accuracy maximisation on WL features with (all-levels) and without (last) all aggregation levels. Results report mean and median scores, as well as the p-value calculated with the Wilcoxon test.

Table 6 : Results of the ML models trained for parallel prediction on WL features with (all-levels) and without (last) all aggregation levels. Results report mean and median scores, as well as the p-value calculated with the Wilcoxon test.

Explore similar work

LLM-Guided Graph Generation for Structure-Based Local Improvement Methods
Aug 13, 2026Hai Xia, Vaidyanathan Peruvemba Ramaswamy, Stefan SzeiderAutomated Heuristic Design Metaheuristic Optimization
Algorithms and Complexity Group, TU Wien, Austria
Algorithm Selection with Zero Domain Knowledge via Text Embeddings
Mar 20, 2026Stefan SzeiderAlgorithm Selection
Algorithms and Complexity Group TU Wien, Vienna, Austria
Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
Feb 16, 2026Sungwoo KangAlgorithm Selection Combinatorial Optimization
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea

Aug 13, 2026, cs.AIJ/K move · Enter open · S save

LLM-Guided Graph Generation for Structure-Based Local Improvement Methods

Hai Xia, Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider

Algorithms and Complexity Group, TU Wien, Austria

Automated Heuristic Design Metaheuristic Optimization Large Language Model-Guided Optimization Constraint Programming Large Neighborhood Search

Open paper AskPDF arXiv

Large neighborhood search normally selects a random subset of decision variables for iterative optimization. For efficiently solving different problems, researchers tend to design variable selection strategies by taking into account structural features from different domains. In this paper, we build an automatic pipeline that is problem-agnostic to all problems in the MiniZinc format. By prompting an LLM with our semantic guidelines, we guide the LLM to produce a graph generator that maps any instance of a problem type to a uniform weighted graph, where nodes represent decision variables and edges represent constraint relationships. These problem-agnostic graphs guide our structure-based local improvement framework (SLIM) in variable selection. Meanwhile, the weighted graph enables all problem instances to share the same generic graph representation, from which the same graph features can be extracted and used for configuration selection. We evaluated our pipeline on instances across 20 MiniZinc competition problems, finding that algorithm selection achieves a 39.5% average problem-weighted win rate against a one-shot Gurobi baseline, more than doubling the best single configuration (19.3%). Configuration and feature ablation boost the performance further to 44.0%, demonstrating that LLM-based semantic generation enables effective automated structure extraction and feature extraction for constraint optimization.

Abstract

Explore similar work

LLM-Guided Graph Generation for Structure-Based Local Improvement Methods

Algorithm Selection with Zero Domain Knowledge via Text Embeddings

Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks