提升密集图上组合优化的GNN性能，通过二值化改进物理启发模型
Binarizing Physics-Inspired GNNs for Combinatorial Optimization
- 基于模糊逻辑与二值化网络，改进原有PI-GNN的输出机制
- 在高密度图上使准确率提升显著，解决实数输出与二值解的偏差问题
- 适合需要高效求解密集组合优化问题的研究者
物理启发图神经网络（PI-GNNs）作为无监督框架，在编码为特定图结构和损失函数的组合优化问题中表现出色，能反映变量间的依赖关系。然而我们发现，随着问题图密度增加，PI-GNN性能系统性下降。分析揭示训练动态存在相变现象，对应于稠密问题中的退化解，暴露出松弛后的实数值输出与实际二值解之间的不匹配。为此，我们借鉴模糊逻辑与二值化神经网络的思想，提出更合理的替代方案。实验表明，所提方法组合在高密度设置下显著提升了PI-GNN性能。
原文摘要 · Abstract (English)
Physics-inspired graph neural networks (PI-GNNs) have been utilized as an efficient unsupervised framework for relaxing combinatorial optimization problems encoded through a specific graph structure and loss, reflecting dependencies between the problem's variables. While the framework has yielded promising results in various combinatorial problems, we show that the performance of PI-GNNs systematically plummets with an increasing density of the combinatorial problem graphs. Our analysis reveals an interesting phase transition in the PI-GNNs' training dynamics, associated with degenerate solutions for the denser problems, highlighting a discrepancy between the relaxed, real-valued model outputs and the binary-valued problem solutions. To address the discrepancy, we propose principled alternatives to the naive strategy used in PI-GNNs by building on insights from fuzzy logic and binarized neural networks. Our experiments demonstrate that the portfolio of proposed methods significantly improves the performance of PI-GNNs in increasingly dense settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。