arXiv cs.AI· Alessio Pellegrino, Jacopo Mauro·· 9 天前AI 评分20
用 Weisfeiler-Leman 特征做约束优化中的算法选择
Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation
AI 导读
研究者提出一种自动化特征提取方法，将问题实例转为图并用 Weisfeiler-Lehman 图核生成结构表示，核心是基于割的表示 WLc，用于刻画结构划分并提供更细粒度的预测信号。在 2023–2025 MiniZinc Challenge 实例上，以最大化 Borda 分数和预测准确率为任务，WLc 在 SVM 上优于 fzn2feat，在随机森林和 MLP 上结果接近。该方法无需训练 GNN。
正文 · 原文
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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| ACM classes: | I.2.6 |
| Cite as: | arXiv:2610.12119 [cs.LG] |
| (or arXiv:2610.12119v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12119 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Alessio Pellegrino [view email]
[v1]
Thu, 8 Oct 2026 15:16:16 UTC (324 KB)
来源：arXiv cs.AI · arxiv.org