This paper presents an unsupervised learning framework for solving combinatorial optimization problems using physics-inspired graph neural networks (PI-GNNs). PI-GNNs show good performance on various combinatorial optimization problems, but their performance deteriorates rapidly as the density of the problem graph increases. Through analysis, we show that this is due to the degenerate solutions for high-density problems and the mismatch between the real-valued output of PI-GNNs and the binary-valued problem solutions. To address this issue, we propose novel methods that improve the simple strategy of existing PI-GNNs based on insights from fuzzy logic and binarized neural networks. Experimental results show that the proposed methods significantly improve the performance of PI-GNNs in high-density environments.
