用退火机指导图神经网络，解决超大规模组合优化问题
Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization
- 用退火机生成部分解，指导图神经网络特征初始化
- 在标准测试中突破退火机原始规模限制，有效求解更大问题
- 适合需要高精度与可扩展性的组合优化研究者
尽管退火机（AM）在求解复杂组合问题上展现出日益增强的能力，被视为未来全量子解决方案的更现实替代，但仍存在扩展性瓶颈。与此同时，图神经网络（GNN）被用于求解组合优化问题，表现出良好性能，并因分布式特性具备潜在高可扩展性。本文提出一种融合方法，旨在保留退火机的高精度与图神经网络的表征灵活性及可扩展性。模型先进行压缩处理，随后通过监督交互，利用退火机获得的部分解来引导局部GNN，获取节点特征表示，并将其组合以初始化一个额外的基于GNN的求解器，该求解器负责处理原始图的目标问题。直观上，退火机通过知识注入的方式间接求解组合问题。在经典优化问题上的实验表明，该方法可行，能有效让退火机求解超出其原始规模限制的问题。
原文摘要 · Abstract (English)
While Annealing Machines (AM) have shown increasing capabilities in solving complex combinatorial problems, positioning themselves as a more immediate alternative to the expected advances of future fully quantum solutions, there are still scaling limitations. In parallel, Graph Neural Networks (GNN) have been recently adapted to solve combinatorial problems, showing competitive results and potentially high scalability due to their distributed nature. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs. Our model considers a compression step, followed by a supervised interaction where partial solutions obtained from the AM are used to guide local GNNs from where node feature representations are obtained and combined to initialize an additional GNN-based solver that handles the original graph's target problem. Intuitively, the AM can solve the combinatorial problem indirectly by infusing its knowledge into the GNN. Experiments on canonical optimization problems show that the idea is feasible, effectively allowing the AM to solve size problems beyond its original limits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。