跳到正文
返回论文列表
cs.LG提交于 已译

Scone: 对称性感知的神经组合优化用于图着色

Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring

Paolo Pellizzoni · Melanie Weber

中文摘要

图着色要求为节点分配颜色使相邻节点颜色不同,是基础组合优化问题;给定固定调色板寻找无单色边的节点着色通常是 NP-hard 的。这促使基于学习的方法利用实例间重复结构高效生成高质量着色。着色的有效性对颜色排列不变,利用该对称性可缩小模型学习策略的有效状态空间;但着色算法也需打破部分对称性,例如为同一自同构轨道内两个相邻节点分配不同颜色。为此提出 Scone,使用颜色等变图神经网络顺序构造着色,使先前分配信息传播并打破节点对称性。Scone 在 sudoku_extreme、寄存器分配等多个图着色任务上以低推理时间达到完美解质量,并展示了对训练中未见图家族的泛化能力。

关键要点

  1. 01问题:固定调色板下无单色边图着色为 NP-hard,需利用实例结构学习高效着色。
  2. 02方法:用颜色等变图神经网络顺序构造着色,利用颜色排列对称性缩小有效状态空间。
  3. 03机制:顺序构造使先前分配信息传播,从而打破同一自同构轨道内相邻节点的对称性。
  4. 04结果:在 sudoku_extreme、寄存器分配等任务上以低推理时间达到完美解质量。
  5. 05局限:摘要未提及具体局限,仅展示对训练未见图家族的泛化。

解读

尚无解读。

原始英文摘要

arXiv:2611.25273v1 Announce Type: new Abstract: Graph coloring, which entails assigning colors to nodes such that no adjacent nodes have the same color, is a fundamental combinatorial optimization problem. In general, however, finding a node coloring with no monochromatic edges given a fixed palette is NP-hard. This motivates learning-based methods that can learn to exploit recurring structure across instances to efficiently produce high-quality colorings. Crucially, the validity of a coloring is invariant to permutations of the colors, and we show that exploiting this symmetry reduces the size of the effective state space over which the model has to learn its policy. At the same time, the coloring algorithm must be able to break some symmetries, for example to assign different colors to two adjacent nodes belonging to the same automorphism orbit. In this paper, we introduce Scone, a model that uses a color-equivariant graph neural network to construct colorings sequentially, allowing information from previous assignments to propagate and break node symmetries. Scone achieves perfect solution quality with low inference times across several graph coloring tasks, including on sudoku_extreme and register allocations, and showcases generalization to graph families not encountered during training.

同方向论文 · cs.LG

查看全部 →