组合优化Combinatorial optimization问题，广泛存在于科学和工业过程。现代深度学习deep learning工具，以前所未有的规模处理了这些问题，不外，结合统计理学学见解的统一框架，仍然很迫切。
近期，美国 亚马逊AWS 量子处理方法实验室(Amazon Quantum Solutions Lab) Martin J. A. Schuetz，J. Kyle Brubaker，Helmut G. Katzgraber，在Nature Machine Intelligence上发帖，报告演示了图神经网络graph neural networks处理组合优化问题。
该办法广泛适用于二次无约束二元优化问题形式的典型NP-hard问题，如最大割maximum cut、最小顶点覆盖minimum vertex cover、最大独立集，以及多项式无约束二元优化问题形式的Ising Spin Glasses及其高阶推广许多方面。
同期，一种驰豫策略relaxation strategy应用于问题哈密顿量，以生成可微分的损失函数，该损失函数可用来训练图神经网络，并在无监督训练过程完成后，简单投影应用于整数变量。标准最大割集和最大独立集问题的数值结果验证了这一办法。
科研发掘，图神经网络优化器性能，相当或优于现有解算器，并且能够扩展到超过现有技术水平，以处理拥有数百万变量的问题。
Combinatorial optimization with physics-inspired graph neural networks
基于理学图神经网络的组合优化。
图1：组合优化图神经网络graph neural networks，GNN办法示意图。
图2：受理学学启发图神经网络GNN优化器的端到端工作流程图。
图3：n=100节点的随机3-正则图的最大割MaxCut示例解。
图4：最大割MaxCut数值结果。
图5：最大独立集maximum independent set，MIS问题的数值结果。
该项科研，提出并分析了一种多功能、可扩展的通用求解器，该求解器由图神经网络GNNS供给支持，并借鉴了统计理学学理念。该办法适用于任何k-局部伊辛k-local Ising模型，包含典型NP-hard组合优化问题，如最大割、最大团、最小顶点覆盖或最大独立集问题等66。从伊辛Ising公式出发，去掉决策变量上的完整性约束，并将驰豫策略relaxation strategy应用于问题哈密顿量，以生成可微损失函数，该损失函数对图神经网络GNN的节点暗示，进行无监督训练。而后，针对图中的每一个顶点，图神经网络GNN训练以生成软分配，预测属于两个类之一的可能性。为了找到与原始问题公式一致二元（双色）标记，采用简单的投影启发式projection heuristics 。
总体而言，这种办法，能够与现有专用求解器竞争，例如设计用于处理最大切割问题的Goemans–Williamson算法，并有可能利用统计理学学的丰富工具箱，例如包含相变科研。在当前中等规模量子时代，该办法能够做为新兴量子技术（包含专用量子6和量子启发退火20）的广泛适用、可扩展基准，同期不受资源限制，亦不局限于QUB形式，相干伊辛机Ising machines亦是如此。
展望：
1、为更好地理解图神经网络GNN，在组合优化环境中的局限性，进一步科研是有序的、系统的图神经网络GNN，与一大类优化问题的最先进解算器，进行基准测试，同期利用图神经网络GNN实现全部全局，包含例如Graphsage或Graph Attention Networks(GATS)，以潜在地利用重视力机制，提高图神经网络GNN ansatz，该重视力机制，使得顶点能够在聚合过程时期，对相邻描述neighbour representations进行加权。
2、当在设备集群上，以小批量方式利用分布式训练时，所提出的图神经网络GNN办法，应该能够适应数亿个节点的问题规模，从而挑战几个现有解算器的能力。尽管日前实例，重点触及随机初始化过程，初始节点嵌入问题，但在将来，运用预先训练的权重（迁移学习）起步训练过程，能够加强处理问题的时间。
3、随机投影randomized projection方法，有望潜在地加强优化器性能，或贪心后处理greedy post-processing，加强这些策略，该后处理例程，经过一系列局部位翻转，检测局部最优性。
4、该办法能够推广到超图hypergraphsPUBO问题，其中超边hyper-edges 能够包括两个以上的节点，而不需要资源密集型度缩减方法，这与资源受限QUBO求解器相反。还有潜在的应用，涵盖了多体相互功效的现实世界优化问题，如在调度 scheduling 问题，或化学发掘问题。
总之，设备学习、运筹学和理学学之间的交叉融合，开辟了许多新兴的科研方向，最后目的是进一步加强处理组合优化问题的能力。
文献链接：https://www.nature.com/articles/s42256-022-00468-6
DOI: https://doi.org/10.1038/s42256-022-00468-6
本文译自Nature。
发表于 2024-8-31 12:06:32