图粗化热启动让MAX-CUT跳出局部最优，2万顶点实例内存直降3333倍！
Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
📖 AI 总结
本文研究计算资源受限条件下非凸MAX-CUT问题的求解，针对其二元优化景观中局部最优解数量随规模指数增长、对初始化高度敏感的核心难题，提出将粒子多项式松弛（PPR）与组合多重网格（CMG）谱图粗化方法相结合的求解框架。CMG以近线性时间生成结构感知的初始解，无需训练数据，为PPR提供热启动，从而有效逃离局部最优。在已知精确最优解的t2g20基准（n=400）上，CMG+PPR平均达到最优值的97.5%，最佳运行达98.4%；加入离散局部搜索精化的扩展版本在近期神经分支定界方法评估的全部60个Biq Mac实例上均达到已发表最优值。采用稀疏CSR表示后，该方法可扩展至多达20000个顶点的G-set实例，内存需求最多降低3333倍，同时保持对CMG热启动的稳定改进。增益在稀疏加权图上最为显著，稠密图则辅以谱稀疏化处理。该工作表明，经典谱粗化与矩松弛的结合可在有限算力下显著提升非凸组合优化的求解质量与可扩展性。
🔑 关键词速览
| MAX-CUT | 最大割问题，图论中的经典NP难组合优化问题，目标是将顶点划分为两个集合使割边权重最大。 |
| Particle Polynomial Relaxation (PPR) | 粒子多项式松弛，一种基于矩的非凸连续重构方法，用于将离散优化问题转化为连续形式以改善优化景观。 |
| Combinatorial Multigrid (CMG) | 组合多重网格，一种谱图粗化方法，能在近线性时间内生成结构感知的初始解，无需训练数据。 |
| Spectral Graph Coarsening | 谱图粗化，通过合并顶点或边来减小图规模，同时保留图的谱特性，常用于加速图算法。 |
| Sparse CSR Representation | 稀疏CSR（压缩稀疏行）表示，一种高效存储稀疏矩阵的格式，可显著减少内存占用并加速计算。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅