Binarizing Physics-Inspired GNNs for Combinatorial Optimization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
The recent work ``Combinatorial Optimization with Physics-Inspired Graph Neural Networks'' [Nat Mach Intell 4 (2022) 367] introduces a physics-inspired unsupervised Graph Neural Network (GNN) to solve combinatorial optim…
Combinatorial OptimizationGraph Neural NetworkMGNN: Graph Neural Networks Inspired by Distance Geometry Problem
Graph Neural Networks (GNNs) have emerged as a prominent research topic in the field of machine learning. Existing GNN models are commonly categorized into two types: spectral GNNs, which are designed based on polynomial…
Combinatorial OptimizationMetric LearningBrain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization
Graph neural networks (GNNs) with unsupervised learning can solve large-scale combinatorial optimization problems (COPs) with efficient time complexity, making them versatile for various applications. However, since this…
Combinatorial OptimizationGraph Neural NetworkAssessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems
Combinatorial optimization (CO) problems are challenging as the computation time grows exponentially with the input. Graph Neural Networks (GNNs) show promise for researchers in solving CO problems. This study investigat…
Combinatorial OptimizationCombinatorial Optimization with Automated Graph Neural Networks
In recent years, graph neural networks (GNNs) have become increasingly popular for solving NP-hard combinatorial optimization (CO) problems, such as maximum cut and maximum independent set. The core idea behind these met…
Combinatorial OptimizationGraph EmbeddingGraph LearningNeural Architecture Search