提出新基准测试图神经网络在难解约束满足问题上的表现
Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
- 基于统计物理构建随机难例基准
- 经典算法性能仍优于现有GNN模型
- 适合评估优化类GNN的真正能力
图神经网络（GNN）被越来越多地应用于求解困难的优化问题，常宣称其性能优于传统启发式方法。然而，此类宣称可能缺乏坚实基础，因缺乏对真正难题实例的标准基准测试。本文从统计物理视角出发，提出基于随机问题的新难题基准，并提供经典启发式算法与GNN在这些基准上的性能结果。公平对比显示，经典算法仍显著优于当前GNN模型。我们分析了神经网络在此领域面临的挑战。未来若要更稳健地宣称性能优越性，可使用本研究所提供的基准，相关数据集已开源：https://github.com/ArtLabBocconi/RandCSPBench。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical heuristics. However, such claims risk being unsolid due to a lack of standard benchmarks on truly hard instances. From a statistical physics perspective, we propose new hard benchmarks based on random problems. We provide these benchmarks, along with performance results from both classical heuristics and GNNs. Our fair comparison shows that classical algorithms still outperform GNNs. We discuss the challenges for neural networks in this domain. Future claims of superiority can be made more robust using our benchmarks, available at https://github.com/ArtLabBocconi/RandCSPBench.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。