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。
正文 · AI 翻译
摘要：算法选择对于高效的约束编程至关重要。多年来，许多基于机器学习方法的算法选择器已成功应用，但传统的特征提取方法往往依赖于人工确定的实例级统计量，无法捕捉底层问题结构。
在本文中，我们旨在弥合这一差距，引入一种新颖的自动化特征提取方法，该方法结合图转换和 Weisfeiler-Lehman 图核，以生成问题实例的稳健结构表示。1-WL 测试界定了标准消息传递图神经网络（GNN）的图区分能力，而合适的 GNN 架构可达到这一界限 \citep{Xuetal2018}。基于 WL 的特征提供了一种无需训练 GNN 的替代方案。我们的主要贡献是一种基于割的表示（\texttt{WLc}），旨在对结构划分进行建模并提供更细致的预测信号。我们在 2023--2025 年 MiniZinc 挑战赛的实例上评估了我们的方法，涉及两个任务：最大化 Borda 计数得分和最大化预测准确率。在支持向量机、随机森林和多层感知机上的实验结果表明，基于割的特征在使用 SVM 时优于 \texttt{fzn2feat}，而使用 RF 和 MLP 时结果更为接近。
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI） |
| ACM 分类： | I.2.6 |
| 引用为： | arXiv:2610.12119 [cs.LG] |
| （或 arXiv:2610.12119v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.12119 arXiv 颁发的 DOI 通过 DataCite（待注册） |
提交历史
来自：Alessio Pellegrino [查看电子邮件]
[v1]
2026年10月8日星期四 15:16:16 UTC（324 KB）
来源：arXiv cs.AI · arxiv.org