文章信息

文章题目为《Combinatorial optimization with physics-inspired graph neural networks》。于2022发在Nature Machine Intelligence上的一篇文章（计算机科学1区，IF:23.9）。

摘要

组合优化问题在科学和工业中普遍存在。现代深度学习工具准备以前所未有的规模解决这些问题，但一个统一的框架，结合了统计物理的见解仍然是突出的。在这里，我们展示了如何图神经网络可以用来解决组合优化问题。我们的方法是广泛适用于典型的NP-二次无约束二元优化问题形式的硬问题，例如最大割，最小顶点覆盖，最大独立集，以及伊辛自旋眼镜和更高的-阶推广的多项式无约束二元优化问题的形式。我们应用松弛策略的问题哈密尔顿生成一个可微的损失函数，我们用它来训练图神经网络，并在无监督训练过程完成后将一个简单的投影应用到整数变量上。我们用数值结果展示了我们对规范最大割和最大独立集问题的方法。我们发现，图神经网络优化器的性能与现有的求解器相当或优于现有的求解器，有能力超越现有技术，解决数百万个变量的问题。

简介

组合优化问题（如最大割、最大独立集、最小顶点覆盖等）在交通物流、电信、金融等领域应用广泛，但传统求解方法存在普适性差、 scalability 有限等问题 —— 例如量子退火设备、相干伊辛机等物理启发式方法，或受变量数量限制（如富士通数字退火器最多处理 8192 个变量），或面临精度与规模的权衡。而深度学习领域中，GNN 因擅长处理图结构数据、可通过 “消息传递” 聚合节点邻域信息，为大规模组合优化提供了新可能。

文章提出的核心方法为：将组合优化问题（如最大割、最大独立集）转化为二次无约束二元优化（QUBO）或多项式无约束二元优化（PUBO）形式，通过哈密顿量（成本函数）编码问题；对哈密顿量进行松弛处理，生成可微损失函数，用于 GNN 的无监督训练（无需标注数据）；训练完成后，通过简单投影策略将 GNN 输出的连续概率参数（软分配）映射回 0/1 整数变量，得到最终解。该框架不依赖手工设计损失函数，同一 GNN 架构可适配不同 QUBO 问题，且无需针对具体问题调整结构。

在数值实验中，文章以最大割（MaxCut）和最大独立集（MIS）为基准问题验证效果：针对随机 d - 正则图，小规模问题（数百节点）上，GNN 求解性能与经典的 Goemans-Williamson 算法相当，且在节点数≥100 时展现出 runtime 优势；大规模问题（10⁴至 10⁶个节点）上，GNN 能稳定获得高质量解（如最大割规模接近理论上界的 90%），且 runtime 随节点数呈近似线性增长，甚至可通过分布式训练处理数百万变量的问题。此外，在 Gset 数据集（标准最大割基准）上，该方法求解结果与现有最优解的相对误差通常在 1% 以内，进一步证明其有效性。

预备知识

A、组合优化

    组合优化聚焦于在有限但通常规模庞大的候选解集合中寻找目标函数最小值（或最大值）的问题，核心场景是需做出大量“是 / 否” 决策，且每个决策组合对应特定成本或收益值，需对其进行优化。这类问题在交通物流、电信、金融等领域应用广泛，典型问题包括最大割（MaxCut）、最大独立集（MIS）、最小顶点覆盖、最大团、集合覆盖等。对于规模足够大的系统，由于解空间随变量数量呈指数级增长，组合优化问题的精确解往往难以获取。虽然针对特定问题可设计定制化近似算法，但此类算法普适性有限。而二次无约束二元优化（QUBO）框架为统一大量 NP 难组合优化问题提供了有效途径，其成本函数可通过哈密顿量表示：

B、图神经网络

图神经网络是一类擅长处理图结构数据的神经网络，核心能力是通过学习聚合图中信息，实现对节点、边或整个图的有效特征表示。一个典型的GNN 层通常包含三个核心函数：一是消息传递函数，支持节点间通过边交换信息；二是聚合函数，将接收的多个消息组合为固定长度的表示；三是更新激活函数（通常为非线性），结合前一层节点表示与聚合信息，生成当前层节点表示。文章中具体采用图卷积网络（GCN）作为 GNN 架构，其节点表示更新公式明确为：

模型

    模型的核心设计逻辑围绕“问题编码 - 损失函数构建 - GNN 训练 - 解投影” 四步展开，下面将依次介绍：

A、问题编码

    首先，将待求解的组合优化问题映射为图结构与对应的哈密顿量（成本函数）—— 以无向图G=(V,E)表示问题，其中顶点集合V对应二元决策变量，边集E捕捉变量之间的相互作用，再通过QUBO形式的哈密顿量编码优化目标，Q矩阵则用于存储问题的具体约束与成本信息。

B、损失函数构建

    由于哈密顿量的非可微性（无法直接用于GNN训练），本文采用松弛策略将二元决策变量推广为连续的概率参数，进而生成可微的损失函数，该损失函数直接关联问题的优化目标，无需手工设计。

C、GNN训练

    基于图卷积网络（GCN）架构实现 GNN 训练，GCN 采用递归邻域聚合策略，通过消息传递机制让每个节点聚合其 k 跳邻域内的信息，逐步更新节点特征表示 。

D、解投影

    在训练完成后，通过简单投影启发式方法将软分配概率映射回 0/1 整数变量，得到符合原问题要求的二元解，同时可通过多轮训练（不同随机种子）与解筛选，进一步提升解的质量。

实验

    本文通过数值实验验证所提物理启发式GNN（PI-GNN）求解器在组合优化问题上的性能，核心围绕最大割（MaxCut） 和最大独立集（MIS） 两大经典 NP 难问题展开 —— 前者是图分区领域的代表性问题，后者在网络设计、金融等场景应用广泛，且二者均能通过 QUBO 框架统一建模，可充分覆盖模型的核心适用场景。实验设计从 “模型配置一致性”“基准对比合理性”“规模扩展性验证” 三个维度出发，确保结果的可靠性与参考价值。

实验一：最大割（MaxCut）问题验证

    MaxCut 问题的目标是将图顶点集划分为两个子集，使连接不同子集的边（割边）数量最大化，实验通过 “小规模对比经典算法”“大规模验证理论边界”“标准数据集对标最优解” 三层验证模型性能。

1.小规模问题：与 Goemans-Williamson（GW）算法对比

    GW 算法是 MaxCut 问题的经典近似算法，通过半定规划与随机舍入实现，对通用图的近似比可达0.878，对 3 - 正则图（每个顶点连接 3 条边）的近似比更高0.9326，是小规模问题的核心对比基准。

2.大规模问题：对标理论边界

    在超过10000个节点时的大规模图，缺乏现有算法的数值基准，采用理论边界作为参考：

                    

实验结果如下：

实验二：最大独立集（MIS）问题验证

        MIS 问题的目标是找到图中最大的 “独立集”（子集内顶点无连接边），实验设计与 MaxCut 保持一致，核心对比传统的 Boppana-Halldórsson（BH）算法（NetworkX 库实现）与理论边界。

1. 小规模问题：与 BH 算法对比

        BH 算法是 MIS 的经典近似算法，对 d - 正则图的近似性能优于多数启发式方法，是小规模问题的核心基准。

2. 大规模问题：对标理论边界

        d - 正则图的独立集大小与顶点数比值为：

实验结果如下：

    综合两大问题的实验结果，PI-GNN 求解器展现出 “小规模性能持平经典算法、大规模性能与效率双优、普适性覆盖多类图拓扑” 的核心优势：

（1）性能上，在小规模问题（<500）与经典算法相当，在大规模问题(>10000)上解质量接近理论上限，且在标准数据集上与现有最优解误差极小；

（2）效率上，runtime 随节点数的增长复杂度远低于传统算法（线性 / 弱超线性 vs 超线性），可通过单 GPU 处理百万级变量，结合分布式训练可进一步突破规模上限；

（3）普适性上，同一模型架构无需调整即可适配 MaxCut、MIS 等不同 QUBO 问题，为其他组合优化问题（如最小顶点覆盖）的求解提供了可复用框架。

欢迎关注微信公众号《当交通遇上机器学习》！如果你和我一样是轨道交通、道路交通、城市规划相关领域的，也可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望我们共同进步！

往

期

回

顾

重磅发布 | 《Artificial Intelligence for Transportation》新刊上线！

团队研究成果|大型活动期间城轨短时客流预测

团队研究成果|城市轨道交通短时交通客流OD预测

团队研究成果|城市轨道交通新线客流预测

团队研究成果|城市轨道交通疫情期间短时客流预测

团队研究成果|基于物理信息引导的突发事件期间的城市轨道交通短时OD需求预测

我知道你在看哟