A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks

By Alex W. Nowak, Soledad Villar, Afonso S. Bandeira, Joan Bruna. 2017

127 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Relational inductive biases, deep learning, and graph networks (2018, background): “…about discrete entities and structure, have also been explored with graph neural networks, such as combinatorial optimization (Bello et al., 2016; Nowak et al., 2017; Dai et al., 2017), boolean satisﬁability (Selsam et al., 2018), program representation and veriﬁcation (Allamanis et al., 2018;…”
Attention-based Graph Neural Network for Semi-supervised Learning (2018, methodology): “GNNs have been successfully applied in diverse applications such as molecular activation prediction [19], community detection [9], matrix completion [6], combinatorial optimization [14, 34], and detecting similar binary codes [44].”
Attention, Learn to Solve Routing Problems! (2018, unknown): “Nowak et al. (2017) train a Graph Neural Network in a supervised manner to directly output a tour as an adjacency matrix, which is converted into a feasible solution by a beam search.”
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search (2018, background): “[30] describes an application of graph neural networks to the quadratic assignment problem.”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, methodology): “Comparatively poor performance of SL methods [Vinyals et al., 2015, Nowak et al., 2017] have supported the argument in favour of reinforcement learning.”
Learning Improvement Heuristics for Solving Routing Problems (2019, methodology): “In [26], GNN is also used to learn normalized embeddings, which is used to reconstruct adjacent matrix of TSP graph, in supervised way.”
Can graph neural networks count substructures? (2020, background): “In the past few years, graph neural networks (GNNs) have achieved empirical success on processing data from various fields such as social networks, quantum chemistry, particle physics, knowledge graphs and combinatorial optimization (Scarselli et al., 2008; Bruna et al., 2013; Duvenaud et al., 2015;”
Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon (2018, background): “Emami and Ranka (2018) and Nowak et al. (2017) explore a different approach by directly approximating a double stochastic matrix in the output of the neural network to characterize the permutation.”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, unknown): “The matrix min(A(2), 1) has been used in [5] in graph neural networks for community detection and in [21] for the quadratic assignment problem.”
Attention Solves Your TSP (2018, methodology): “Nowak et al. (2017) train a Graph Neural Network in a supervised manner to directly output the optimal tour in the form of an adjacency matrix which is converted into a feasible solution by a beam search.”