REVISED NOTE on LEARNING QUADRATIC ASSIGNMENT with GRAPH NEURAL NETWORKS

Alex Nowak, Soledad Villar, Afonso S. Bandeira, Joan Bruna

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE Data Science Workshop, DSW 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages229-233
Number of pages5
ISBN (Print)9781538644102
DOIs
StatePublished - Aug 17 2018
Event2018 IEEE Data Science Workshop, DSW 2018 - Lausanne, Switzerland
Duration: Jun 4 2018Jun 6 2018

Publication series

Name2018 IEEE Data Science Workshop, DSW 2018 - Proceedings

Other

Other2018 IEEE Data Science Workshop, DSW 2018
CountrySwitzerland
CityLausanne
Period6/4/186/6/18

ASJC Scopus subject areas

  • Artificial Intelligence
  • Safety, Risk, Reliability and Quality
  • Water Science and Technology
  • Control and Optimization

Fingerprint Dive into the research topics of 'REVISED NOTE on LEARNING QUADRATIC ASSIGNMENT with GRAPH NEURAL NETWORKS'. Together they form a unique fingerprint.

  • Cite this

    Nowak, A., Villar, S., Bandeira, A. S., & Bruna, J. (2018). REVISED NOTE on LEARNING QUADRATIC ASSIGNMENT with GRAPH NEURAL NETWORKS. In 2018 IEEE Data Science Workshop, DSW 2018 - Proceedings (pp. 229-233). [8439919] (2018 IEEE Data Science Workshop, DSW 2018 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DSW.2018.8439919