Binarizing Physics-Inspired GNNs for Combinatorial Optimization
Martin Krutský, Gustav Šír, Vyacheslav Kungurtsev, Georgios Korpas · 2025
Read Binarizing Physics-Inspired GNNs for Combinatorial Optimization by Martin Krutský, Gustav Šír, Vyacheslav Kungurtsev, Georgios Korpas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13703.txt.
Introduction
Krutský, Šír, Kungurtsev, and Korpas fix a failure mode of physics-inspired neural solvers as puzzle graphs grow dense. These graph networks relax yes-no problems into smooth values and have solved many sparse cases well. The authors show performance falls off a cliff as graphs densify, with training sliding into degenerate answers far from valid binary ones.
Borrowing from fuzzy logic and from binarized networks, they craft principled ways to force outputs toward clean binary values during training. The resulting portfolio of methods restores much of the lost performance on dense problems. Their 2025 study also maps the phase change in training behavior behind the collapse. The authors aim the fixes at hard combinatorial optimization in industry and research.
Catalog record
| CREATOR | Martin Krutský, Gustav Šír, Vyacheslav Kungurtsev, Georgios Korpas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Binarizing Physics-Inspired GNNs for Combinatorial Optimization Martin Krutský, Gustav Šír, Vyacheslav Kungurtsev, Georgios Korpas 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. † † paperid: 1329 † † orcid: 0009-0000-9710-1147 † † orcid: 0000-0001-6964-4232 † † orcid: 0000-0003-2229-8824 † † orcid: 0000-0003-3850-4979 1 Introduction With the advent of deep learning and its penetration into classical AI fields, such as automated planning and logical reasoning, combinatorial optimization (CO) has emerged as another promising area for its application. Among various deep learning approaches to CO, ranging from end-to-end machine learning algorithms to hybrid systems ( Cappart et al. 2023 ) , physics-inspired graph neural networks (PI-GNNs) ( Schuetz et al. 2022a ) have gained particular attention due to their generality and interpretable physical intuition. PI-GNNs leverage a specific loss function to encode the objective of an optimization problem, enabling unsupervised training to converge on solutions that minimize the objective. This formulation is highly adaptable across various combinatorial optimization domains, establishing PI-GNNs as a promising general-purpose CO-solving framework. The theoretical promise of PI-GNNs draws on insights from the overparameterization regime of neural networks, where multiple studies have shown that—under specific assumptions—the noise in stochastic gradient descent leads to convergence to global minima ( Mei et al. 2018 ; Zou et al. 2020 ) . Coupled with their inherent parallelizability and computational power of modern GPUs, PI-GNNs emerge as a potentially more scalable and efficient alternative to classical solvers. Despite their potential, PI-GNNs have recently faced critique for underperforming relative to efficient domain-specific heuristics on sparse graphs ( Angelini and Ricci-Tersenghi 2023 ; Boettcher 2023 ) . In response, it has been argued that PI-GNNs exhibit superior performance on dense graph instances ( Schuetz et al. 2023a ) , considered better suited for the natively parallel deep learning-based approach ( Schuetz et al. 2023b ) . However, the experimental analysis has focused merely on sparse d -regular graphs ( d=3 , d=5 ), 1 1 1 with edge density ( Diestel 2000 ) \rho(\mathcal{G})\leq 0.051 across all experiments. Schuetz et al. 2023b claim that 7 MaxCut problems from the Gset dataset ( Ye 2003 ) are an exception, but their density is low, as well: \rho(\mathcal{G})\leq 0.015 . Truly dense problems were tackled only within a different domain ( Schuetz et al. 2022b ) . despite denser graphs having an essential status in domains involving network analysis ( Melancon 2006 ; Nanavati et al. 2008 ) . To investigate the setting, this work addresses the performance of PI-GNNs on graphs with progressively increasing density. Our results confirm favorable performance on the, originally-selected, sparse instances ( Schuetz et al. 2022a ) ; however, contrary to the previous claims ( Schuetz et al. 2023a ; Schuetz et al. 2023b ) , we demonstrate that the performance of PI-GNNs consistently plummets as the density increases. Our analysis of the training dynamics of PI-GNNs reveals an intriguing phenomenon: in sparse settings, the distribution of model output values undergoes a phase shift where all the values initially converge toward near-zero and, subsequently, for the selected nodes, toward near-one values. This behavior appears essential for the successful convergence of the original PI-GNNs; however, it rapidly diminishes as the graph density increases. To address this phenomenon, we focus on the employed relaxation strategy of PI-GNNs, currently trained as standard deep learning models, with continuous outputs that are only thresholded after training to produce the binary solution for the underlying combinatorial problem. In contrast, we propose to inform the training process about the binary nature of the underlying task through principled binarization techniques. Specifically, using concepts from fuzzy logic ( Klir and Yuan 1995 ) and binarized neural networks ( Hubara et al. 2016 ) , we resolve the phase shift issues and significantly outperform the original PI-GNNs across graphs of varying connectivity, especially in denser settings. 2 Background We target physics-inspired ( Section 2.2 ) GNN models ( Section 2.3 ) for solving combinatorial optimization problems ( Section 2.1 ). 2.1 Combinatorial Optimization Combinatorial optimization (CO) formalizes problems with a discrete solution space, making traditional efficient continuous optimization techniques, such as gradient-based methods, not directly applicable. Definition 1 (Combinatorial Optimization Problem) . An instance of a combinatorial optimization problem is a triplet (\Omega,\mathcal{F},c) , where \Omega is a finite set, \mathcal{F}\subseteq 2^{\Omega} is the set of feasible solutions, and c:2^{\Omega}\to\mathbb{R} is a cost function. The solution to such a problem is S^{*}={\argmin}_{S\in\mathcal{F}}\ c(S) . Solving combinatorial optimization problems thus requires selection of an optimal subset of a finite (or countable) domain set. Due to a combinatorial explosion, the number of candidates can be enormous. Therefore, many combinatorial optimization problems are notoriously hard to solve, with no general algorithmic solutions that would run in polynomial time w.r.t. the input size ( Cook 1971 ) . Figure 1: Schematic of an Ising spin chain in 1D, with arrow/spin down corresponding to assignment 0 , and up to 1 , respectively. Graph Representation in CO When Karp 1972 introduced the hierarchy of 21 combinatorial NP -complete problems, a significant subset shared a common structure, being defined over graphs. These include problems of maximum cut , maximum independent set , maximum clique , and graph partitioning , among others. Moreover, Karp demonstrated that even the remaining problems in this hierarchy can be polynomially reduced to one of these graph-based problems. Here we introduce two NP -hard CO problems that will be used in the paper. Definition 2 (Maximum Cut) . Given an undirected graph \mathcal{G}=(\mathcal{V},\mathcal{E}) , partition \mathcal{V} into two disjoint sets \mathcal{V}_{1},\mathcal{V}_{2} , such that the number of edges with one node in \mathcal{V}_{1} and the other in \mathcal{V}_{2} is maximal: \max_{\mathcal{V}_{1}\subseteq\mathcal{V}}|\{e\ |\ e=\{v_{i},v_{j}\},v_{i}\in\mathcal{V}_{1}\Leftrightarrow v_{j}\notin\mathcal{V}_{1}\}| (1) Definition 3 (Maximum Independent Set) . Given an undirected graph \mathcal{G}=(\mathcal{V},\mathcal{E}) and an indicator function i:\mathcal{V}\rightarrow\{0,1\} , the maximum independent set is a subset of maximal size consisting of vertices that do not share an edge: \max\limits_{V\subseteq\mathcal{V}}|\{v\ |\ i(v)=1,\forall v^{\prime}\in\mathcal{V}:\{v,v^{\prime}\}\in\mathcal{E}\Rightarrow i(v^{\prime})=0\}| (2) Relaxation of CO Problems Due to their computational complexity, solving CO problems often involves tackling a relaxation , where the discrete decision variables, indicating the solution subset, are replaced with continuous ones. Ideally, the solution to the relaxed problem is naturally integral, coinciding with the optimal solution of the original problem. However, in most practical scenarios, relaxation techniques provide solutions that either need to be appropriately rounded or act as intermediate solutions. This fact plays a prominent role in CO approaches, such as