提出更强大的图神经网络，能高效求解线性半定规划问题。
On the Expressive Power of GNNs to Solve Linear SDPs
- 设计了能捕捉半定规划结构的新型图神经网络架构
- 在合成数据和SdpLib上误差和目标差距显著更低
- 用学习结果预热求解器可提升80%实际速度
半定规划（SDPs）是凸优化的强大框架，常用于构建难解组合问题的强松弛。但大规模SDP求解计算成本高，促使使用机器学习模型作为快速替代方案。图神经网络（GNNs）因对稀疏性敏感且能建模变量-约束交互，成为自然选择。本文研究恢复最优SDP解所需的表达能力。首先证明标准GNN架构无法恢复线性SDP解。随后提出更具表达力的架构，可捕获SDP核心结构，并能模拟标准一阶求解器的更新过程。实验表明，在各类合成数据和SdpLib基准上，该架构预测误差与目标差距均显著优于理论更弱的基线。进一步利用学习到的高质量初始解预热一阶求解器，实现最高达80%的实际加速。
原文摘要 · Abstract (English)
Semidefinite programs (SDPs) are a powerful framework for convex optimization and for constructing strong relaxations of hard combinatorial problems. However, solving large SDPs can be computationally expensive, motivating the use of machine learning models as fast computational surrogates. Graph neural networks (GNNs) are a natural candidate in this setting due to their sparsity-awareness and ability to model variable-constraint interactions. In this work, we study what expressive power is sufficient to recover optimal SDP solutions. We first prove negative results showing that standard GNN architectures fail on recovering linear SDP solutions. We then identify a more expressive architecture that captures the key structure of SDPs and can, in particular, emulate the updates of a standard first-order solver. Empirically, on both synthetic and \textsc{SdpLib} benchmarks of various classes of SDPs, this more expressive architecture achieves consistently lower prediction error and objective gap than theoretically weaker baselines. Finally, using the learned high-quality predictions to warm-start the first-order solver yields practical speedups of up to 80%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。