# Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization

arXiv: https://arxiv.org/abs/2511.19573 · HTML: https://mlsanity.com/paper/2511.19573/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 57 references that are in the map.
- First posted on arXiv 24 Nov 2025.

## Builds on (most cited first, 30 of 31)

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Trajectory balance: Improved credit assignment in GFlowNets](https://mlsanity.com/paper/2201.13259/) (2022)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [Learning GFlowNets from partial episodes for improved convergence and stability](https://mlsanity.com/paper/2209.12782/) (2022)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Better Training of GFlowNets with Local Credit and Incomplete Trajectories](https://mlsanity.com/paper/2302.01687/) (2023)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2302.05636/) (2023)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [No Representation, No Trust: Connecting Representation, Collapse, and Trust Issues in PPO](https://mlsanity.com/paper/2405.00662/) (2024)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Learning-Augmented Streaming Algorithms for Approximating MAX-CUT](https://mlsanity.com/paper/2412.09773/) (2024)
- [Learning to Branch in Combinatorial Optimization with Graph Pointer Networks](https://mlsanity.com/paper/2307.01434/) (2023)

## Abstract (arXiv)

Neural solvers provide fast solutions to graph combinatorial optimization problems, but training alone does not guarantee solution quality. Exact methods guarantee optimality but can be prohibitively expensive. We propose Neural Fixed-Parameter Tractable (N-FPT), a neural-model-agnostic framework that uses parameterized algorithms to improve neural solutions without retraining and guide learning. It restricts neural advice to a treewidth modulator and completes the bounded-treewidth remainder exactly. It returns and certifies the best achievable solution under any valid advice, improving the neural solution whenever a better compatible completion exists. We prove this guarantee and global optimality under perfect advice. Its incremental-confidence N-FPT (NIC-FPT) and randomized-deferral N-FPT (NRD-FPT) variants consolidate neural advice. Beyond inference, N-FPT feedback becomes available as neural decisions make exact completion tractable. From that state onward, it supplies what final solution rewards lack: the first decision that rules out every optimal completion and alternatives that preserve one. One exact computation supplies reusable guidance for continuations from that state, even when neural samples miss its optimum. Experiments across graph combinatorial optimization problems demonstrate solution-quality gains with different neural models and robustness to graph-size and distribution shifts. The learned completion model reaches optimal completions more often than reinforcement learning (RL) alone, without an exact solver at inference. N-FPT thus uses graph structure to improve neural solutions and guide learning toward optimal completion.