Source-linked AI summary
Combinatorial Optimization with Physics-Inspired Graph Neural Networks
Martin J. A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber
TL;DR
The paper addresses the need for scalable, unified methods for hard combinatorial optimization. It trains graph neural networks using differentiable relaxations of physics-based problem Hamiltonians, then projects soft outputs to binary solutions. Across MaxCut and MIS, the approach achieves competitive solution quality while scaling to instances with millions of variables.
Problem
Many combinatorial optimization problems are difficult to solve at large scale, while existing approaches lack a unified framework combining statistical-physics formulations with modern deep learning.
Method
The method maps optimization variables to graph nodes, relaxes Ising/QUBO/PUBO Hamiltonians into differentiable losses, trains a GNN without labels, and projects soft assignments to binary variables.
Results
The GNN optimizer performs on par with or better than existing solvers and reaches high-quality MaxCut and MIS solutions on instances with millions of variables.
Takeaways & Limitations
A single physics-inspired GNN framework can address multiple canonical QUBO problems while extending optimization experiments to substantially larger instances.
Takeaways & Limitations
The authors call for systematic benchmarking across more optimization problems and GNN architectures to better understand the approach’s limitations.
Abstract
from arXiv · showhide
Combinatorial optimization problems are pervasive across science and industry. Modern deep learning tools are poised to solve these problems at unprecedented scales, but a unifying framework that incorporates insights from statistical physics is still outstanding. Here we demonstrate how graph neural networks can be used to solve combinatorial optimization problems. Our approach is broadly applicable to canonical NP-hard problems in the form of quadratic unconstrained binary optimization problems, such as maximum cut, minimum vertex cover, maximum independent set, as well as Ising spin glasses and higher-order generalizations thereof in the form of polynomial unconstrained binary optimization problems. We apply a relaxation strategy to the problem Hamiltonian to generate a differentiable loss function with which we train the graph neural network and apply a simple projection to integer variables once the unsupervised training process has completed. We showcase our approach with numerical results for the canonical maximum cut and maximum independent set problems. We find that the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables.
I. INTRODUCTION
The paper motivates a scalable, general approach for difficult combinatorial optimization problems by combining graph neural networks with physics-inspired loss functions. The method trains soft node assignments without labels and projects them to binary solutions.
- Motivation: Combinatorial optimization has broad applications, but many problems remain intractable, particularly in structured real-world settings.The paper identifies transportation, logistics, telecommunications, and finance among the application domains.
- Motivation: Existing physics-inspired hardware and approaches face scalability limitations, motivating alternatives for much larger problem instances.Examples include precision–size trade-offs in coherent Ising machines and an 8192-variable limit for the Fujitsu Digital Annealer.
- Approach: The proposed solver maps optimization variables to graph vertices and trains a GNN with a differentiable loss obtained by relaxing the problem Hamiltonian.The GNN recursively aggregates neighborhood information to update node representations.
- Approach: After unsupervised training, soft node assignments are projected to binary variables, producing a solution bit string for the optimization problem.The projection uses the final GNN outputs, which represent soft assignments.
- Workflow: The workflow combines graph-based message passing, problem-specific loss encoding, and final integer projection.The paper presents the method schematically as an end-to-end optimization pipeline.
II. RELATED WORK
Prior neural approaches include supervised, reinforcement, and unsupervised methods, but the paper seeks a more unified and scalable framework. Its physics-inspired GNN connects Ising, QUBO, and PUBO formulations without hand-crafted loss functions.
- Existing neural approaches: Supervised approaches learn mappings from problem representations to target solutions using empirical losses, while reinforcement learning avoids labelled targets through reward optimization.The reviewed methods include pointer networks and policy-learning approaches.
- Existing neural approaches: Unsupervised methods avoid labelled datasets, but prior work on some problems relied on empirically selected hand-crafted loss functions.RUN-CSP was reported on several problems, including MaxCut and MIS, with instances up to 5000 nodes.
- Proposed framework: The proposed framework directly relates Ising, QUBO, PUBO, and differentiable GNN losses, unifying a broad class of optimization problems.The framework uses the same GNN optimizer across different QUBO problems without changing the architecture or loss function.
- Proposed framework: The authors present the framework as a generic solver that scales to problem instances orders of magnitude larger than many traditional QUBO solvers can handle.Its scope includes hard combinatorial optimization problems with up to millions of variables.
III. PRELIMINARIES
The preliminaries formulate combinatorial problems through binary variables, graph structures, and QUBO or related Hamiltonians. They also introduce GNN message passing, which supplies node representations for downstream classification or optimization.
- Combinatorial optimization: Combinatorial optimization assigns yes/no decisions whose resulting objective value is optimized over a large solution space.Canonical examples include MaxCut, MIS, minimum vertex cover, and maximum clique.
- QUBO and related models: QUBO represents the objective as a quadratic Hamiltonian xᵀQx, where binary variables encode decisions and Q stores problem-specific coefficients.Constraints can be incorporated through penalty terms rather than explicitly imposed.
- QUBO and related models: QUBO is closely related to Ising models through the mapping z_i = 2x_i − 1, while PUBO extends the formulation with higher-order variable interactions.Higher-order terms use real-valued coupling coefficients over groups of binary variables.
- Graph formulation: Graph formulations associate a binary variable with each vertex, allowing assignments to be visualized as two-tone graph colorings.This representation supports canonical graph problems such as MaxCut and MIS.
- Graph neural networks: GNN layers exchange messages, aggregate neighborhood information, and update node representations recursively across the graph.Stacking layers expands each node’s receptive field beyond its immediate neighbors.
IV. COMBINATORIAL OPTIMIZATION WITH GRAPH NEURAL NETWORKS
The method treats combinatorial optimization as unsupervised node classification: GNN outputs become continuous assignment probabilities, which enter a differentiable relaxed objective before projection to binary decisions.
- Training setup: The approach initializes node embeddings randomly and trains without labelled data, framing optimization as an unsupervised node-classification task.The native problem Hamiltonian supplies the basis for the training objective.
- Differentiable relaxation: Binary decision variables are relaxed to continuous values so the resulting loss is differentiable with respect to GNN parameters.This enables standard backpropagation and gradient-based optimization.
- Differentiable relaxation: The final GNN embeddings produce soft assignments p_i ∈ [0,1] that can be interpreted as class probabilities and passed to the loss function.A nonlinear softmax activation generates the assignments.
- Projection: After training, projection heuristics convert soft assignments into integer variables, for example using x_i = int(p_i).This produces the discrete solution required by the original optimization problem.
- Implementation: The approach exposes hyperparameters such as layer count, embedding dimensionality, and learning rate for outer-loop tuning.Grid search and Bayesian optimization are suggested for this tuning stage.
- Implementation: A two-layer GCN implementation is illustrated on a 100-vertex 3-regular MaxCut instance, achieving a cut size of 132.The implementation can use open-source graph-learning libraries.
V. NUMERICAL EXPERIMENTS
The numerical experiments evaluate a physics-inspired GNN optimizer on MaxCut and MIS, comparing solution quality and runtime with established solvers across graph sizes. The approach remains competitive on smaller instances and scales to graphs with millions of variables while maintaining high-quality solutions.
- Experimental setup: The experiments benchmark a consistent two-layer GCN architecture on MaxCut and MIS instances, while seeking robust performance without instance-by-instance hyperparameter tuning.The model uses graph convolutions and sigmoid outputs for binary decisions; multiple shots can mitigate local optima at increased runtime.
- MaxCut: MaxCut is evaluated on random unweighted d-regular graphs and additional Gset benchmark instances against Goemans-Williamson and other published solvers.The d-regular experiments use theoretical upper and randomized lower bounds, while Gset reports relative error against the best known cut size.
- MaxCut: The GNN performs on par with Goemans-Williamson on smaller MaxCut graphs, while its runtime scales approximately linearly for n between 10^5 and 10^6.The observed GW runtime scales approximately as n^3.5 for n ≲250, reflecting the semidefinite-program solver used internally.
- MaxCut: cut⋆≳0.9 · cutub for d = 3 and d = 5 on graphs with n ≈10^4 to 10^6, with runtime reaching approximately 10 minutes at n = 10^6.For large d-regular graphs, cut⋆ scales approximately linearly with n, with γ3 ≈1.28 and γ5 ≈1.93.
- MaxCut: On Gset MaxCut instances, the general-purpose GNN approach is typically within ∼1% of the best published results.The table reports PI-GNN cut sizes, sourced comparison results, best-known values, and relative error ε.
- Maximum Independent Set: For MIS on large d-regular graphs, α3/n ≈0.416 and α5/n ≈0.338, corresponding to estimated approximation ratios of ∼0.92 and ∼0.88.The total runtime scales as ∼n^1.7 for n ≳10^5, compared with ∼n^2.9 for the Boppana-Halldorsson solver at n ≲500.
VI. APPLICATIONS IN INDUSTRY
The section shows how QUBO formulations connect the general-purpose solver to industry applications, including finance, scheduling, and water-network sensor placement.
- Once an application is expressed as QUBO, it can be plugged into the general-purpose physics-inspired GNN solver.
- QUBO provides a broad modeling framework for optimization problems including knapsack, resource allocation, and capital budgeting.
- Risk diversification: The framework describes risk diversification using expected returns and asset covariances, linking the model to a discretized mean-variance strategy.
- Interval scheduling: Interval scheduling models overlapping resource requests as clashes that cannot be assigned to the same machine.
- Sensor placement in water distribution networks: Water-network sensor placement is cast as QUBO on a graph whose nodes represent tanks or junctions and edges represent pipes.
- Sensor placement in water distribution networks: The minimum vertex-cover formulation minimizes sensor costs while penalizing violations of xi+xj ≥1 on every edge, then maps to a relaxed trainable loss.
VII. CONCLUSION AND OUTLOOK
The paper concludes that its physics-inspired GNN solver offers a scalable framework for broad classes of graph optimization problems, while identifying benchmarking and architecture studies as future work.
- The solver applies to any k-local Ising model, including maximum cut, maximum clique, minimum vertex cover, and maximum independent set.
- Relaxing integrality constraints produces a differentiable loss for unsupervised GNN training, followed by projection of soft assignments to binary labels.
- The approach can compete with existing special-purpose solvers such as Goemans-Williamson for maximum cut.
- Outlook: Systematic benchmarking across optimization problems and GNN architectures is proposed to better understand the method's limitations.
- Outlook: Distributed mini-batch training could extend the approach to problem sizes with hundreds of millions of nodes.
I. CORE GCN CODE BLOCK
The core code defines a two-layer graph convolutional network with sigmoid binary outputs and a custom QUBO loss evaluated on soft assignments.
- The example script imports DGL, PyTorch, and GraphConv to implement the GNN solver.
- The GCN class is initialized with input features, a hidden dimension, and output classes.
- Two graph-convolution layers transform node features from the input dimension through a hidden layer to the class output.
- The forward pass applies ReLU between graph convolutions and sigmoid at the output for binary classification.
- The custom loss computes the QUBO cost by evaluating probs_^T Q_mat probs_ for soft assignments.
II. HYPERPARAMETERS FOR G-SET EXPERIMENTS
The G-Set experiments use a configurable base GCN architecture, with numerical results and solver hyperparameters documented for the MaxCut instances.
- The PI-GNN model configurations specify hyperparameters used to solve G-Set instances, with results reported in Table I and settings in Table II.
- The base GCN architecture has a tunable number of layers K.
- Table II reports numerical MaxCut results for G-Set instances alongside the PI-GNN solver's hyperparameters.
- The base implementation constructs a layer-size sequence from input features, hidden sizes, and output classes.