PaperlayerView exact revision on arXiv

Source-linked AI summary

Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation

Alessio Pellegrino, Jacopo Mauro

arXiv:2610.12119v1cs.LGcs.AI

TL;DR

Algorithm selection matters because solver performance varies across instances, while traditional instance-level features may miss problem structure. The paper converts constraint instances to graphs and extracts Weisfeiler-Lehman features, including a cut-based representation. Across two MiniZinc Challenge tasks, cut-based features outperform fzn2feat with SVMs, while RF and MLP results are closer.

  • Problem

    Traditional instance-level statistics may fail to capture underlying problem structure, motivating structural features for algorithm selection.

    Source: §1 · p. 1, §3.1 · p. 2

  • Method

    The paper converts constraint instances to graphs and applies Weisfeiler-Lehman features, including a cut-based representation that models structural partitions.

    Source: §1 · p. 1

  • Results

    Cut-based features outperform fzn2feat with SVMs on both tasks, while results with RFs and MLPs are closer and several RF configurations slightly favor fzn2feat.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The conclusions report that WL and WLc provide strong predictive signals across machine-learning models and show stability across diverse tasks.

    Source: §7 · p. 8

    The WL feature-extraction pipeline is not fully optimised, although the vast majority of instances take less than one second to extract even with cut-based features.

    Source: §6.3 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the gap between instance-level features that may miss problem structure and structure-aware models with substantial computational overhead. It introduces graph-based Weisfeiler-Lehman features, including a cut-based representation, and evaluates them on MiniZinc Challenge instances.

1 Introduction

  • Traditional instance-level statistics may miss latent structure, while graph-based methods are often coupled with models that require substantial computational overhead.Source: §1 · p. 1
  • The proposed graph conversion and Weisfeiler-Lehman features include a cut-based representation that models structural partitions for a more nuanced predictive signal.The graph conversion is designed to be compatible with classical and deep machine-learning paradigms.Source: §1 · p. 1
  • Cut-based features outperform fzn2feat with SVMs on both tasks, while RF and MLP comparisons are closer and several RF configurations slightly favor fzn2feat.The tasks use instances from the 2023, 2024, and 2025 MiniZinc Challenges.Source: §1 · p. 1

2 Background

The background introduces constraint optimisation and algorithm selection, then describes the Weisfeiler-Lehman algorithm and its limits. Together, these concepts frame the paper’s use of graph structure to represent instances for selecting algorithms.

2.1 Combinatorial Optimisation

  • Constraint Programming models combinatorial optimisation with variables, domains, and constraints, while solvers use methods such as propagation, branch and bound, and clause learning.Portfolio approaches run multiple solvers with different strategies simultaneously.Source: §2.1 · pp. 1–2

2.2 The Algorithm Selection Problem

  • Algorithm selection maps problem instances to portfolio algorithms to optimise an expected performance metric, commonly using machine-learning features of each instance.Examples of metrics include runtime, penalized average runtime, and solution quality.Source: §2.2 · p. 2

2.3 The WL Algorithm

  • The WL algorithm iteratively refines node colours by aggregating neighbouring colours, using graph colour histograms to assess whether two graphs may be isomorphic.Source: §2.3 · p. 2
  • 1-WL is not a complete isomorphism test, and k-WL can distinguish more graphs but has computational complexity that grows exponentially with k.Equally sized regular graphs with the same degree remain indistinguishable by 1-WL when all nodes start with the same colour.Source: §2.3 · p. 2

3 Related Work

Related work covers algorithm selectors and handcrafted features, graph representations for constraint problems, and graph kernels and GNNs. It identifies a need for informative structural representations alongside practical feature extraction.

3.1 Algorithm Selectors and Handcrafted Features

  • Algorithm selectors have used methods such as Random Forests and k-nearest neighbours, while handcrafted FlatZinc features summarize variables, constraints, domains, and graph statistics.Such features can be costly to design, may generalize poorly across domains, and compress combinatorial substructures into flat statistics.Source: §3.1 · p. 2

3.2 Graph Representations for Constraint Problems

  • Constraint problems have been represented as bipartite or tripartite graphs, or decomposed into smaller components in syntax-tree-like graphs.The approaches differ in which problem elements become nodes and how their relationships are encoded.Source: §3.2 · p. 2

3.3 Graph Kernels and GNNs in Combinatorial Optimisation

  • Graph feature methods include graph kernels such as WL, graphlet, and random-walk kernels, while standard message-passing GNNs are bounded in expressive power by 1-WL.GNNs require substantial training data and incur inference latency; WL kernels are presented as a fast alternative for algorithm selection.Source: §3.3 · pp. 2–3

4 Graph Conversion

The graph conversion decomposes constraint models into a syntax-tree-like representation, inspired by Boisvert et al. It omits domain values for practical reasons and uses directed, typed edges to encode model structure.

4 Graph Conversion

  • The conversion is inspired by Boisvert et al.’s syntax-tree-like representation, which decomposes complex constraints into simpler reusable elements.Source: §4 · p. 3
  • Domain values are omitted because large domains could make graphs intractable and add noise that weakens the signal from other nodes.One cited 2025 instance had 3,646,705 possible values in a single objective-function domain.Source: §4 · p. 3
  • The conversion defines nodes for variables, solutions, parameters or literals, operators, and constraints, with operator and constraint subcategories.Source: §4 · p. 3
  • Directed edges encode model relationships, with lead edges for order-insensitive operands or left-side operands and trailing edges for right-side operands when order matters.Global edges distinguish connections to global constraints from connections to ordinary constraints.Source: §4 · pp. 3–4
  • Figure 1 illustrates conversion from a constraint model to a graph, using node colours for types and L, T, and G labels for edge types.The gray area marks the example constraint 3*x <= y.Source: Figure 1 · p. 4

5 Extracting Features Using The Weisfeiler-Leman Algorithm

The section extracts graph-structural features through WL refinement, extending node and edge information and adding a cut-based representation. It also supplements and standardizes the histograms to represent instances consistently.

5.1 WL For Feature Extraction

  • WL features count node colours after refinement, using the final histogram alone because it represents the most refined partition and performed comparably to concatenated histograms in the reported tests.The comparison found no statistically significant performance difference across two tasks and three models, except one SVM accuracy comparison favoring the single histogram.Source: §5.1 · p. 4

5.2 Enhancing Features’ Expressiveness

  • Node-information and edge-information extensions encode node types and subtypes, incoming edge types, and directed incoming-neighbour colours in the WL updates.The resulting variants are WL, WLn, WLe, and WLne, depending on which extensions are applied.Source: §5.2 · pp. 4–5

5.3 The “Cut”

  • The cut makes variable-arity constraints and operators less sensitive to degree by ignoring their incoming edges during refinement and updating them from a set of incoming node colours.This shifts the local equivalence criterion from multiset-based counting toward set-based neighbor-type presence; pair histograms then retain degree information.Source: §5.3 · p. 5

5.4 Auxiliary Structural Features

  • Auxiliary features add average variable out-degree and average parameter out-degree to the histogram representation.The cut is illustrated with all-different constraints: matching incoming node types yield the same cut colour, while different degrees yield different pair histograms.Source: §5.4 · p. 5, Figure 3 · p. 5

5.5 Feature Normalisation and Vocabulary Alignment

  • Colour histograms are normalized by the number of nodes and pair histograms by the number of pairs, while a training-set colour vocabulary aligns feature vectors across instances.Unseen test-instance colours absent from that vocabulary are discarded.Source: §5.5 · p. 5

5.6 Remarks on Graph Dynamics and Depth

  • Directed local decompositions have short paths, typically 1–4 edges, with effective propagation depth reduced to 2 under the cut in the example.This local depth is distinct from the diameter of the entire instance graph, and cut-node updates deliberately ignore incoming multiplicities.Source: §5.6 · pp. 5–6

6 Experimental Results

Across two algorithm-selection tasks, cut-based Weisfeiler–Lehman features perform strongest with SVMs, while RF and MLP comparisons are closer. The evaluation also examines extraction cost, where the current WL pipeline is slower than fzn2feat in absolute terms.

6 Experimental Results

  • The experiments use 300 MiniZinc Challenge instances from 2023–2025, three solvers, three model families, and repeated five-fold nested cross-validation across 10 seeds.The Borda task's final dataset comprised 289 instances after exclusions; its reported scores exclude feature-extraction costs.Source: §6 · p. 6, §6.1 · p. 6

6.1 Borda Count Score Maximization

  • Cut-based features significantly outperform all other variants on Borda maximization, while the number of aggregation steps has negligible impact.SVM results also show node information improves over standard WL features, whereas edge information adds no substantial predictive signal.Source: §6.1 · pp. 6–7
  • RF and MLP comparisons are closer: fzn2feat is marginally better for Borda RFs except WLc-ne-2, while accuracy results show minimal RF differences and slightly better cut-feature MLP results.The best paired accuracy results also favor cut features over fzn2feat in mean and median.Source: §6.1 · p. 7, §6.2 · p. 7

6.2 Algorithm Selection with Accuracy Maximisation

  • For accuracy maximization, cut-based features significantly outperform alternatives and fzn2feat with SVMs, and all feature configurations improve over the majority-classifier baseline.The marginal benefit of node information is less pronounced than in the Borda task.Source: §6.2 · p. 7

6.3 Feature Extraction Cost

  • fzn2feat has lower absolute extraction times, but most instances take less than one second with cut-based features; the WL extraction implementation is not fully optimized.Compilation time is excluded from the extraction-cost comparison.Source: §6.3 · p. 8

7 Conclusions and Discussion

The paper presents graph-based feature extraction for Constraint Programming, focusing on cut-based representations and their integration with FlatZinc. It reports versatility and stability across models and tasks, and identifies efficiency and broader integration as future work.

7 Conclusions and Discussion

  • The method integrates graph-based feature extraction into the FlatZinc ecosystem, with particular focus on cut-based representations (WLc).The authors describe this as bridging structural graph representations and classical machine learning paradigms.Source: §7 · p. 8
  • WL and WLc features provide strong predictive signals across different machine-learning models and exhibit stability across diverse tasks.Source: §7 · p. 8
  • Future work will optimize extraction efficiency, explore dynamic online selection and feature-set combinations, and extend the features to other relevant Constraint Programming tasks.Source: §7 · p. 8

A Node Types for FlatZinc

Table 3 describes node types used to convert FlatZinc models into graphs. The authors expect the types to generalize to other languages, except for global nodes, which depend on the solver used for conversion.

A Node Types for FlatZinc

B The Cut Algorithm

The cut algorithm refines graph-node colours while treating cut nodes differently, then combines colour histograms with neighbour-pair counts. In the illustrated graph conversion, applying a cut reduces the effective propagation depth.

B The Cut Algorithm

  • The edge-enhanced WLc-ne variant includes edge types alongside neighbour colours during aggregation.Source: B The Cut Algorithm · p. 10
  • Initial node colours encode node type and subtype, and standard Weisfeiler-Leman refinement updates non-cut nodes from incoming-neighbour colours while cut nodes skip that aggregation but still propagate colours downstream.Source: B The Cut Algorithm · p. 10
  • After refinement, cut nodes aggregate the set of incoming neighbour types, giving same-type nodes with the same incoming types the same colour regardless of arity; directed neighbour-cut pairs retain discarded degree information.Source: B The Cut Algorithm · p. 10
  • The final feature vector concatenates histograms of refined non-cut-node colours and neighbour pairs.Source: B The Cut Algorithm · p. 10

C On The Shallowness of the Graphs

D All Borda Count Results

The Borda-count results vary by classifier: RF results are similar across WL features with node information and fzn2feat, while MLP results favor cut features. Figures 10 and 11 show the RF and MLP results, respectively.

D All Borda Count Results

E All Algorithm Selection Accuracy Results

For algorithm-selection accuracy, MLP results favor cut features over other WL-based features, while RF results are similar across node-information WL features and fzn2feat.

E All Algorithm Selection Accuracy Results

  • MLP results show cut features significantly outperforming the other WL-based features on algorithm-selection accuracy.The gap over fzn2feat is larger than for other WL features, though less pronounced than in the Borda count task.Source: E All Algorithm Selection Accuracy… · p. 12
  • For RFs, results are similar across WL-based features that include node information and fzn2feat features.This pattern is similar to the Borda count counterpart.Source: E All Algorithm Selection Accuracy… · p. 12

F Ablation Study on the Importance of Concatenating All Aggregation Levels

The ablation compares last-level-only WL features with features using all aggregation levels across tasks and models. Results are generally not statistically significant, with one significant case favoring last-level-only features.

F Ablation Study on the Importance of Concatenating All Aggregation Levels

Loading 2610.12119v1…