Source-linked AI summary
Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP
Marcelo O. R. Prates, Pedro H. C. Avelar, Henrique Lemos, Luis Lamb, Moshe Vardi
TL;DR
The paper asks whether GNNs can solve an NP-Complete problem combining symbolic graph structure with numerical edge weights. It uses weighted edge-and-vertex message passing for decision TSP and reports 80% accuracy at ±2% deviations, with stronger performance for relaxed deviations and some generalization.
Problem
The paper investigates whether GNNs can solve NP-Complete problems involving both symbolic relationships and numerical edge weights.
Method
The model assigns embeddings to vertices and weighted edges, performs learned recurrent message passing, and aggregates edge votes into a decision prediction.
Results
80% accuracy was obtained on unseen test instances with −2%, +2% deviations, while other distributions reached 82% at 5% and 96% at 10% deviation.
Takeaways & Limitations
GNNs can learn a message-passing procedure for a decision problem that combines graph relationships with numerical edge information.
Abstract
from arXiv · showhide
Graph Neural Networks (GNN) are a promising technique for bridging differential programming and combinatorial domains. GNNs employ trainable modules which can be assembled in different configurations that reflect the relational structure of each problem instance. In this paper, we show that GNNs can learn to solve, with very little supervision, the decision variant of the Traveling Salesperson Problem (TSP), a highly relevant $\mathcal{NP}$-Complete problem. Our model is trained to function as an effective message-passing algorithm in which edges (embedded with their weights) communicate with vertices for a number of iterations after which the model is asked to decide whether a route with cost $<C$ exists. We show that such a network can be trained with sets of dual examples: given the optimal tour cost $C^{*}$, we produce one decision instance with target cost $x\%$ smaller and one with target cost $x\%$ larger than $C^{*}$. We were able to obtain $80\%$ accuracy training with $-2\%,+2\%$ deviations, and the same trained model can generalize for more relaxed deviations with increasing performance. We also show that the model is capable of generalizing for larger problem sizes. Finally, we provide a method for predicting the optimal route cost within $2\%$ deviation from the ground truth. In summary, our work shows that Graph Neural Networks are powerful enough to solve $\mathcal{NP}$-Complete problems which combine symbolic and numeric data.
Introduction
The paper positions graph neural networks as differentiable message-passing models for symbolic problems and asks whether they can solve numerical NP-Complete problems such as decision TSP.
- Deep learning has advanced image recognition, natural language processing, and reinforcement learning, while direct application to symbolic domains remains incipient.
- GNNs assemble trainable neural modules according to a problem instance’s graph representation and learn messages exchanged between nodes.These messages form a differentiable algorithm whose parameters can be improved through gradient descent.
- NeuroSAT demonstrated approximately 85% accuracy on small Boolean satisfiability instances and improved with more message-passing timesteps.The model could also extract satisfying assignments despite not being explicitly trained to produce them.
- The paper investigates whether GNNs can solve decision TSP, which asks whether a graph has a Hamiltonian route with cost no greater than C.
- Decision TSP extends the challenge beyond Boolean structure by requiring the model to consider edge weights and a target cost C.
A GNN Model for the Decision TSP
The proposed Decision TSP solver represents both vertices and weighted edges, iteratively exchanges learned messages, and aggregates edge votes into a graph-level prediction.
- The model assigns multidimensional embeddings to vertices and edges and updates them through repeated neural message passing.Messages are computed along adjacencies, aggregated, and used by recurrent units to update embeddings.
- Edge embeddings preserve edge-weight information that would be lost in a vertex-only representation.The architecture replaces vertex-to-vertex adjacency with edge-to-vertex connectivity.
- The model initializes vertex embeddings and computes edge embeddings from each edge weight w and target cost C.
- MLPs compute vertex-to-edge and edge-to-vertex messages, while recurrent update functions refine both vertex and edge embeddings.
- Edge embeddings produce logits whose arithmetic mean is transformed by a sigmoid into the final prediction.Algorithm 1 summarizes this message-passing and voting procedure.
Training the Model
The model is trained by supervised optimization on weighted graph instances labeled according to whether their target-cost decision is positive or negative.
- Training uses edge-incidence matrices, edge weights, and target cost C, optimizing binary cross entropy with TensorFlow’s Adam implementation.
- Batched training forms disjoint unions of graphs so message passing remains independent across instances.
- Training graphs contain 20–40 random points in a square, Euclidean pairwise distances, complete adjacency, and Concorde-derived optimal tour costs.
- The implementation uses 64-dimensional vertex and edge embeddings, three-layer (64,64,64) ReLU MLPs, and 32 message-passing steps.
Experimental Results and Analyses
The trained GNN solves decision-TSP instances near the optimal cost, generalizes to relaxed deviations and larger graphs with declining accuracy, and supports route-cost prediction. Performance also varies across graph distributions and exceeds two heuristic baselines on tested deviations.
- Training and decision accuracy: 80.16% training accuracy and 80% test accuracy were achieved after 2000 epochs on instances with ±2% deviations.The test set contained 2048 previously unseen instances generated with the same n ∼U(20, 40) configuration.
- Extracting route costs: The acceptance curve is S-shaped, with confident NO predictions for sufficiently small costs, confident YES predictions for sufficiently large costs, and a phase transition near zero deviation.Larger instances shift the critical point toward smaller deviations; the curves are averaged over 1024 instances.
- Training and decision accuracy: >95% accuracy was reached for 10% deviation in 200 epochs, whereas 2% deviation required 2000 epochs for 85% accuracy.The model learns faster as the target-cost deviation becomes more relaxed.
- Extracting route costs: 1.5% average absolute deviation from the optimal route cost was obtained using binary search, with an average of 8.9 iterations.Algorithm 2 used δ = 0.01 on 1024 test graphs with n ∼U(20, 40).
- Generalizing to Other Distributions: 64% accuracy was obtained on random metric instances at 2% deviation, while non-metric instances stayed at the 50% baseline; on real-world instances, the GNN outperformed simulated annealing on 6 of 9 cases.For random metric instances, accuracy increased to 82% at 5% and 96% at 10% deviation; against NN and SA, the GNN exceeded 90% TPR from 4% deviation onward.
Conclusions and Future Work
The proposed GNN solves Decision TSP from paired decision instances, generalizes to some larger sizes and distributions, and supports optimal-cost prediction through acceptance curves and binary search.
- The GNN assigns multidimensional embeddings to vertices and edges, refines them through message passing, and combines vertex votes into a route-existence prediction.
- 80% accuracy was obtained with −2%, +2% deviations, while accuracy increased to 96% at −5%, +5% deviations.
- The model generalizes to some extent across larger problem sizes and different distributions.
- Acceptance curves reveal phase-transition-like behavior, and binary search uses them to predict optimal TSP costs despite yes-or-no training.
- Future work includes engineering training data for negative-by-default inference, extracting routes, and evaluating broader real, random, and larger graphs.