# Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2017.

## Built on by (most cited first, 28 of 28)

- [Scalars are universal: Equivariant machine learning, structured like classical physics](https://mlsanity.com/paper/2106.06610/) (2021)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem](https://mlsanity.com/paper/2304.09407/) (2023)
- [H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2304.09395/) (2023)
- [Equivariant Deep Weight Space Alignment](https://mlsanity.com/paper/2310.13397/) (2023)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems](https://mlsanity.com/paper/2102.05875/) (2021)
- [Solve routing problems with a residual edge-graph attention neural network](https://mlsanity.com/paper/2105.02730/) (2021)
- [Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks](https://mlsanity.com/paper/2107.01410/) (2021)
- [Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning](https://mlsanity.com/paper/2210.17178/) (2022)
- [Reversible Action Design for Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/2102.07210/) (2021)
- [Neural Airport Ground Handling](https://mlsanity.com/paper/2303.02442/) (2023)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems](https://mlsanity.com/paper/2506.16428/) (2025)
- [Learning to Branch in Combinatorial Optimization with Graph Pointer Networks](https://mlsanity.com/paper/2307.01434/) (2023)
- [A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2308.04639/) (2023)
- [Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey](https://mlsanity.com/paper/2108.04462/) (2021)
- [Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing](https://mlsanity.com/paper/2207.02087/) (2022)
- [Fast Decision Support for Air Traffic Management at Urban Air Mobility Vertiports using Graph Learning](https://mlsanity.com/paper/2308.09075/) (2023)
- [Boosting Graph Search with Attention Network for Solving the General Orienteering Problem](https://mlsanity.com/paper/2109.04730/) (2021)
- [Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings](https://mlsanity.com/paper/2505.13087/) (2025)
- [Graph Learning-based Fleet Scheduling for Urban Air Mobility under Operational Constraints, Varying Demand & Uncertainties](https://mlsanity.com/paper/2401.04851/) (2024)
- [Test-Time Augmentation for Traveling Salesperson Problem](https://mlsanity.com/paper/2405.04767/) (2024)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)

## Abstract (arXiv)

Inverse problems correspond to a certain type of optimization problems formulated over appropriate input distributions. Recently, there has been a growing interest in understanding the computational hardness of these optimization problems, not only in the worst case, but in an average-complexity sense under this same input distribution. In this revised note, we are interested in studying another aspect of hardness, related to the ability to learn how to solve a problem by simply observing a collection of previously solved instances. These 'planted solutions' are used to supervise the training of an appropriate predictive model that parametrizes a broad class of algorithms, with the hope that the resulting model will provide good accuracy-complexity tradeoffs in the average sense. We illustrate this setup on the Quadratic Assignment Problem, a fundamental problem in Network Science. We observe that data-driven models based on Graph Neural Networks offer intriguingly good performance, even in regimes where standard relaxation based techniques appear to suffer.