Binarizing Physics-Inspired GNNs for Combinatorial Optimization

• URL: http://arxiv.org/abs/2507.13703v2
• Date: Fri, 01 Aug 2025 14:44:43 GMT
• Title: Binarizing Physics-Inspired GNNs for Combinatorial Optimization
• Authors: Martin Krutský, Gustav Šír, Vyacheslav Kungurtsev, Georgios Korpas,
• Abstract summary: We show that the performance of PI-GNNs plummets with an increasing density of the problem graphs.<n>We propose principled alternatives to the naive strategy used in PI-GNNs by building on insights from fuzzy logic and binarized neural networks.<n>Our experiments demonstrate that the portfolio of proposed methods significantly improves the performance of PI-GNNs in increasingly dense settings.
• Score: 2.5782973781085383
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Learn Singularly Perturbed Solutions via Homotopy Dynamics [7.890817997914349]
  Training neural networks for singularly perturbed problems is challenging due to certain parameters in the PDEs that introduce near-singularities in the loss function.<n>We introduce a novel method based on homotopy dynamics to effectively manipulate these parameters.<n> Experimentally, we demonstrate that our approach significantly accelerates convergence and improves the accuracy of these singularly perturbed problems.
  arXiv  Detail & Related papers  (2025-02-01T16:26:53Z)
• Which Optimizer Works Best for Physics-Informed Neural Networks and Kolmogorov-Arnold Networks? [1.8175282137722093]
  We compare PINNs and PIKANs on key challenging linear, stiff, multi-scale non-linear PDEs including Burgers, Allen-Cashinsky, Ginzburg-Landau equations.<n>Our results reveal improvements without the use of any other enhancements typically employed in PINNs and PIKANs.
  arXiv  Detail & Related papers  (2025-01-22T21:19:42Z)
• Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization [2.0643665408482517]
  Annealing Machines (AM) have shown increasing capabilities in solving complex problems.<n>Graph Neural Networks (GNN) have been recently adapted to solve problems.<n>We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs.
  arXiv  Detail & Related papers  (2025-01-10T10:36:46Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Graph Convolutional Branch and Bound [1.8966938152549224]
  We propose using neural networks to learn informatives-most notably, an optimality score that estimates a solution's proximity to the optimum.<n>This score is used to evaluate nodes within a branch-and-bound framework, enabling a more efficient of the solution space.
  arXiv  Detail & Related papers  (2024-06-05T09:42:43Z)
• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  Graph neural networks are recognized for their strong performance across various applications. BP has limitations that challenge its biological plausibility and affect the efficiency, scalability and parallelism of training neural networks for graph-based tasks. We propose DFA-GNN, a novel forward learning framework tailored for GNNs with a case study of semi-supervised learning.
  arXiv  Detail & Related papers  (2024-06-04T07:24:51Z)
• Dynamically configured physics-informed neural network in topology optimization applications [4.403140515138818]
  The physics-informed neural network (PINN) can avoid generating enormous amounts of data when solving forward problems. A dynamically configured PINN-based topology optimization (DCPINN-TO) method is proposed. The accuracy of the displacement prediction and optimization results indicate that the DCPINN-TO method is effective and efficient.
  arXiv  Detail & Related papers  (2023-12-12T05:35:30Z)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  Graph networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data.<n>There remains a lack of analysis comparing GNNs and generalizations from an optimization and generalization perspective.
  arXiv  Detail & Related papers  (2023-06-24T10:21:11Z)
• Implicit Stochastic Gradient Descent for Training Physics-informed Neural Networks [51.92362217307946]
  Physics-informed neural networks (PINNs) have effectively been demonstrated in solving forward and inverse differential equation problems. PINNs are trapped in training failures when the target functions to be approximated exhibit high-frequency or multi-scale features. In this paper, we propose to employ implicit gradient descent (ISGD) method to train PINNs for improving the stability of training process.
  arXiv  Detail & Related papers  (2023-03-03T08:17:47Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
  Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors. It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features. We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
  arXiv  Detail & Related papers  (2020-06-26T17:03:06Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  We present two techniques, GNNs over dense fixed graphs for low-dimensional problems and sampling-based GNNs for high-dimensional problems. We examine the ability of a GNN to tackle planning problems such as identifying critical nodes or learning the sampling distribution in Rapidly-exploring Random Trees (RRT) Experiments with critical sampling, a pendulum and a six DoF robot arm show GNNs improve on traditional analytic methods as well as learning approaches using fully-connected or convolutional neural networks.
  arXiv  Detail & Related papers  (2020-06-11T08:19:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.