PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph neural networks and the energetic cavity method for combinatorial optimization

Joe Bacchus George, George T. Cantwell

arXiv:2609.07456v1cond-mat.dis-nncs.LG

TL;DR

Many combinatorial optimization problems can be formulated as Ising ground-state searches, and the paper incorporates min-sum into a graph neural network by initializing the network to implement that heuristic. The combined approach improves performance, but Monte Carlo methods remain reliably better even under O(n log n) runtime limits.

  • Problem

    Many combinatorial optimization problems can be formulated as Ising ground-state searches, motivating practical methods for problems that are difficult to solve exactly.

    Source: §I · p. 1

  • Method

    The network is initialized to implement the min-sum algorithm, also called the energetic cavity method, before training.

    Source: §I · p. 1

  • Results

    The min-sum neural network improves performance and is effective on some problems, but Monte Carlo methods reliably find better solutions even under O(n log n) runtime limits.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    Incorporating well-understood heuristics into neural-network architecture can considerably improve performance, though the learned method still falls short of simulated annealing.

    Source: §V · p. 8, D. Further tasks · p. 8

    The learned method still falls short of simulated annealing, so the authors do not consider it a reliable tool in practice.

    Source: D. Further tasks · p. 8

Abstract

from arXiv · show

We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.

I. INTRODUCTION

The paper studies graph neural networks for Ising-formulated combinatorial optimization and incorporates established heuristics into their design. The authors report improved performance from this integration, while Monte Carlo methods remain stronger under comparable runtime limits.

I. INTRODUCTION

  • Combinatorial optimization seeks the best option from a finite set, and many such problems can be formulated as Ising ground-state searches.The passage notes that a finite domain does not make these problems easier and that practical algorithms remain important.Source: §I · p. 1
  • The efficacy of neural networks for combinatorial optimization remains unclear because they may lose to simple conventional methods while using more computing resources.The cited prior work reports this concern for neural-network approaches.Source: §I · p. 1
  • The paper initializes a neural network to implement min-sum, also called the energetic cavity method, so training starts from that heuristic.The authors expect training to improve performance from this initialization.Source: §I · p. 1
  • Earlier hybrid approaches range from replacing belief-propagation equations with neural networks to augmenting retained equations with a graph neural network.This work instead builds from min-sum for optimization and studies problems larger by orders of magnitude.Source: §I · p. 1
  • Monte Carlo methods reliably outperform neural networks, even when runtime is limited to O(n log n).The combined min-sum neural network is effective on some problems and handily outperforms the heuristic it builds on.Source: §I · pp. 1–2

II. PROBLEM AND MODEL SETUP

  • For MaxCut, the task is to divide graph nodes into two groups so that as many edges as possible cross between them; its Ising form uses zero fields and couplings J_ij = −A_ij.Here A is the adjacency matrix, and the corresponding model is an antiferromagnet without an external field.Source: §II · p. 2

A. Graph neural networks

The graph neural network constructs node embeddings through repeated graph-based updates with learned parameters. To train it for Ising problems, the paper uses relaxed spin values and an unsupervised objective based on energy.

A. Graph neural networks

  • A graph neural network builds node embeddings through layers that apply nonlinear transformations and aggregate information from nodes.The model’s free parameters are learned during training.Source: A. Graph neural networks · p. 2
  • For the Ising problem, the network starts from random node noise and applies sequential updates to produce an assignment.The supplied passages describe the update process and final-layer assignment, but do not provide complete equations.Source: A. Graph neural networks · p. 2
  • Training replaces binary spins with a differentiable relaxation, inserts the relaxed values into the energy, and optimizes network weights using sampled problems.The approach is unsupervised and does not require solved instances for training.Source: A. Graph neural networks · p. 2

III. GNN EXPERIMENTS

The experiments use MaxCut on random graphs and establish the Laplacian cut as a simple baseline. This baseline is itself equivalent to a parameter-free, unit-width GNN, making it a direct reference for learned models.

III. GNN EXPERIMENTS

  • The experiments test GNNs on MaxCut for random graphs, using random k-regular graphs as a testing ground with prior numerical and theoretical study.The paper first establishes an appropriate baseline before reporting GNN results because prior findings were mixed to poor.Source: §III · pp. 2–3

A. Laplacian cut as a baseline

  • The Laplacian cut uses an eigenvector associated with the largest eigenvalue of the normalized Laplacian to construct a cut.The normalized Laplacian is defined using the identity matrix and the diagonal matrix of node degrees.Source: A. Laplacian cut as a baseline · p. 3
  • The baseline is simple, has no free parameters or further optimization, and should be consistently outperformed by any practically useful method.The paper describes the Laplacian heuristic as a unit-width GNN with no free parameters.Source: A. Laplacian cut as a baseline · p. 3
  • The Laplacian heuristic is equivalent to a GNN of width one, so a GNN can be constructed to perform at least as well on MaxCut.The resulting question is whether training can improve on this baseline.Source: A. Laplacian cut as a baseline · p. 3

B. GNN depth and weight initialization

Standard GNN performance varies sharply with depth, while a Laplacian-informed initialization lets a deep model improve on the baseline. The experiments use the learned improvement to motivate incorporating stronger heuristic structure.

B. GNN depth and weight initialization

  • Sparse graphs may require deep networks for information to propagate across macroscopic distances, despite typical GNNs being shallow and deep models facing oversmoothing concerns.The passage says sparse-graph diameter typically grows logarithmically with n and suggests depth growing at least as fast as log(n).Source: B. GNN depth and weight initialization · p. 3
  • Standard GNNs fail to beat the Laplacian baseline at shallow depths, become competitive around 16 layers, then collapse toward chance at greater depths.The paper attributes failure to poor weight selection because the Laplacian method is equivalent to a very deep GNN with no free parameters.Source: B. GNN depth and weight initialization · p. 3
  • At 256 layers, the Laplacian-initialized spectral GNN considerably outperforms the standard Laplacian cut on MaxCut graphs of size 8192.The figure reports results for random 3-regular and Watts–Strogatz graphs, averaging over 100 instances and taking the best of 10 trials per instance.Source: Figure 1 · p. 4, B. GNN depth and weight initialization · p. 4
  • The spectral GNN is initialized so that, before training, it implements the iterative Laplacian cut, giving it a reasonable baseline starting point.The initialization modifies weights rather than the neural architecture.Source: B. GNN depth and weight initialization · pp. 3–4
  • Because the spectral GNN improves beyond its Laplacian initialization, the paper next turns to modifying the architecture to improve the more competitive min-sum algorithm on locally tree-like graphs.The authors present this as evidence for incorporating heuristic knowledge into GNN design.Source: B. GNN depth and weight initialization · p. 4

IV. MIN-SUM EXPERIMENTS

The section presents min-sum as an approximate ground-state heuristic and asks whether a GNN can improve it, particularly where the algorithm’s tree assumption is problematic. It also describes how the method is derived and used on graphs with cycles.

IV. MIN-SUM EXPERIMENTS

  • Min-sum, also called the energetic cavity method, is a heuristic for finding approximate ground states in Ising-like models.Source: §IV · p. 4
  • The derivation defines constrained minimum energies and removes node i to define cavity energies, yielding a relation that holds if the graph is a tree.Source: §IV · p. 4
  • On a tree, iterating the closed equations for the cavity energies gives the exact ground state at convergence.The procedure iteratively solves Eqs. (21) and (20), and is called the min-sum algorithm.Source: §IV · p. 4
  • For graphs with cycles, decimation sequentially fixes a proportion of spins after each round and reruns min-sum with those spins fixed.Source: §IV · p. 5
  • On random regular graphs, min-sum considerably outperforms the spectral GNN and several other deep-learning methods.Decimation is described as a competitive heuristic for graphs with cycles, though it generally does not find true minima.Source: §IV · p. 5
  • Min-sum assumes the graph is a tree, so it is expected to work best on locally tree-like graphs and less well on graphs rich in short cycles.The section asks whether a GNN can build on min-sum to address these shortcomings.Source: §IV · p. 5

A. Min-Sum GNN

The min-sum GNN augments min-sum messages with learned node features while retaining the min-sum update. It is initialized to perform min-sum before training, and outperforms min-sum alone at the tested graph sizes.

A. Min-Sum GNN

  • The model appends a d-dimensional feature to each min-sum message, creating augmented min-sum messages for each node at every iteration.Source: A. Min-Sum GNN · p. 5
  • Each edge update retains the standard min-sum rule for one component and uses a GNN rule for the remaining d components.A learned matrix allows information exchange between the min-sum and GNN-style updates.Source: A. Min-Sum GNN · p. 5
  • The parameters are initialized so the untrained GNN performs min-sum for T iterations.Training then tests whether the network can improve on min-sum alone.Source: A. Min-Sum GNN · p. 5
  • At all tested sizes, min-sum-GNN performs better than min-sum alone, with or without decimation.The standard GNN is systematically worse than min-sum with decimation.Source: Figure 2 · p. 6

B. MaxCut on random regular graphs

On random regular graphs, min-sum-GNN outperforms the other methods considered so far, including standard min-sum, and appears to generalize beyond its training size. It is comparable to simulated annealing at linear runtime, but annealing finds better solutions when allowed O(n log n) time.

B. MaxCut on random regular graphs

  • Min-sum-GNN outperforms all methods considered so far, including original min-sum, and also surpasses decimation.The min-sum-GNN is built on standard min-sum without decimation, while the reported size comparison shows it outperforming decimation.Source: B. MaxCut on random regular graphs · p. 6
  • Trained on graphs with n = 512 nodes, the methods appear to generalize to larger graphs, with min-sum-GNN gains persisting beyond standard min-sum and decimation.Standard min-sum performance declines on larger graphs, whereas decimated min-sum remains roughly consistent across sizes.Source: B. MaxCut on random regular graphs · p. 6
  • At O(n log n), simulated annealing finds better MaxCut solutions than min-sum-GNN, which is comparable to annealing at linear runtime.The figure compares solution quality across graph sizes; the text describes the linear-time comparison and the higher quality reached with log-linear annealing.Source: Figure 3 · p. 6, B. MaxCut on random regular graphs · p. 6
  • GFlowNets and S2V-DQN find significantly worse solutions and take more than 1000 times longer to run.ANYCSP finds solutions competitive with min-sum-GNN and simulated annealing, but takes more than 500 times longer than simulated annealing.Source: B. MaxCut on random regular graphs · p. 6
  • GNN methods add training expenses and unpredictable out-of-distribution performance, while simulated annealing remains the most reliable heuristic for this task.The comparison also reports CPU and GPU runtimes and averages results over 100 instances.Source: B. MaxCut on random regular graphs · p. 6, Figure 4 · p. 7

C. MaxCut on Watts-Strogatz graphs

On Watts-Strogatz graphs, standard min-sum performs poorly across a wide range of rewiring probabilities because graphs with p < 1 are not locally tree-like. Min-sum-GNN improves on traditional min-sum across the range, but still underperforms simulated annealing.

C. MaxCut on Watts-Strogatz graphs

D. Further tasks

Across MaxCut, BinSG, and EA, min-sum is exact on trees, while on other topologies simulated annealing outperforms it and min-sum-GNN closes 90% of the gap on average. The authors also report that min-sum-GNN remains short of simulated annealing overall and is not reliable in practice.

D. Further tasks

  • The reported results cover 16 combinations of problems and topologies, including random recursive trees and Barabási-Albert graphs.The paper also considers random regular and Watts-Strogatz graphs.Source: D. Further tasks · pp. 7–8
  • On trees, min-sum is exact; on other topologies, simulated annealing outperforms min-sum and min-sum-GNN closes 90% of the gap on average.This pattern is consistent across MaxCut, BinSG, and EA.Source: D. Further tasks · p. 8
  • For the random field Ising model, min-sum is as good as or better than annealing on locally tree-like graphs; on Watts-Strogatz graphs, min-sum-GNN's improvement may correct for short cycles.With ferromagnetic bonds, finding the random-field Ising ground state is a computationally easy minimum-cut problem.Source: D. Further tasks · p. 8
  • Despite its improved solution quality over other GNNs, min-sum-GNN still falls short of simulated annealing and is not considered reliable in practice.Source: D. Further tasks · p. 8

V. DISCUSSION

The discussion argues that incorporating physics-informed heuristics improves GNN performance, but does not establish a general advantage over simulated annealing. A plausible use case is narrow: fixed problem distributions, strict time limits, and GPU access.

V. DISCUSSION

  • Incorporating domain knowledge from random-graph physics through simple GNN adjustments considerably improves performance.The discussion frames effective neural-network construction as building on traditional methods.Source: §V · p. 8
  • Laplacian mean-field weight initialization lets deep GNNs avoid oversmoothing, while energetic-cavity-inspired message passing brings their performance closer to simulated annealing.The discussion notes that competitive optimization performance requires deep models.Source: §V · p. 8
  • The min-sum-GNN improves on min-sum and can match short-run simulated annealing, but no neural network systematically outperforms simulated annealing.Simulated annealing can readily improve with more runtime.Source: §V · p. 8
  • Neural-network training has considerable upfront cost that the experiments do not account for, and performance can degrade badly on substantially different instances.The discussion also identifies out-of-distribution issues even if training costs could be amortized.Source: §V · p. 8
  • The authors identify only a narrow potential use case: a guaranteed fixed problem distribution, strict time constraints, and access to GPUs.They report no compelling reason to deploy GNNs for these tasks for now.Source: §V · p. 8

Appendix A: Experimental procedure

The appendix describes training on newly generated random instances and reports comparisons of simulated annealing, min-sum, and min-sum-GNN across four problems and four graph topologies. The min-sum-GNN closes most of the min-sum-to-annealing gap when min-sum is not approximately correct, with one stated exception.

Appendix A: Experimental procedure

  • Training instances are newly generated at random and grouped into batches of size 215/n.The passage gives the batch-size expression as printed.Source: Appendix A · p. 8
  • The min-sum-GNN closes more than 80% of the gap between min-sum and simulated annealing except for RFIM-WS, improving over min-sum where that method is not approximately correct.The table covers four problems on four topologies, with 8192-node graphs; results average 100 instances using the best of 10 trials per instance.Source: Table I · p. 9
  • Training runs for 500 epochs with Adam; GNNs use depth T = 256 and width d = 32 unless otherwise stated.The learning rate at epoch t is ηt = 0.001 × 0.99t, and initialization uses PyTorch Geometric defaults.Source: Appendix A · p. 9
Loading 2609.07456v1…