mlsanityData to 14 Oct 2026

Binarizing Physics-Inspired GNNs for Combinatorial Optimization

arXiv 2507.13703 ↗First posted 18 Jul 2025cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 64 references that are in the map. First posted on arXiv 18 Jul 2025.

Builds on

29 of 64 references.

References · 29

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2013Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computationcited by 2,079
  4. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  5. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  6. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  7. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  8. 2013Ising formulations of many NP problemscited by 207
  9. 2020Tempered Sigmoid Activations for Deep Learning with Differential Privacycited by 122
  10. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  11. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  12. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
17 more
  1. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  2. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  3. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 20
  4. 2022Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cutcited by 19
  5. 2022Application of QUBO solver using black-box optimization to structural design for resonance avoidancecited by 17
  6. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  7. 2023Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 9
  8. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  9. 2023Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problemscited by 5
  10. 2024Combinatorial Optimization with Automated Graph Neural Networkscited by 5
  11. 2024Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Updatecited by 4
  12. 2022Combinatorial optimization solving by coherent Ising machines based on spiking neural networkscited by 3
  13. 2023Approaching Collateral Optimization for NISQ and Quantum-Inspired Computingcited by 2
  14. 2023Lightsolver challenges a leading deep learning solver for Max-2-SAT problemscited by 1
  15. 2023A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learningcited by 1
  16. 2024Scalable Quantum-Inspired Optimization through Dynamic Qubit Compressioncited by 1
  17. 2025Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimizationcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Graph Q-Learning for Combinatorial Optimization
  2. 2025A Distributed Training Architecture For Combinatorial Optimization
  3. 2023COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems
  4. 2022Combinatorial optimization for low bit-width neural networks
  5. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networks
  6. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
  7. 2025Physics-Inspired Binary Neural Networks: Interpretable Compression with Theoretical Guarantees
  8. 2026Revealing Combinatorial Reasoning of GNNs via Graph Concept Bottleneck Layer