Binarizing Physics-Inspired GNNs for Combinatorial Optimization
This addresses a specific bottleneck in unsupervised combinatorial optimization for researchers, though it is incremental as it builds on existing PI-GNN frameworks.
The paper tackled the performance drop of physics-inspired graph neural networks (PI-GNNs) in dense combinatorial optimization problems, showing that proposed binarization methods significantly improved results in such settings.
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.