TY - GEN

T1 - REVISED NOTE on LEARNING QUADRATIC ASSIGNMENT with GRAPH NEURAL NETWORKS

AU - Nowak, Alex

AU - Villar, Soledad

AU - Bandeira, Afonso S.

AU - Bruna, Joan

N1 - Funding Information:
JB was partially supported by Samsung Electronics (Improving Deep Learning using Latent Structure), DOA W911NF-17-1-0438. ASB was partially supported by NSF DMS-1712730 and NSF DMS-1719545. SV was partially supported by the Simons Algorithms and Geometry (A&G) Think Tank.
Publisher Copyright:
© 2018 IEEE.

PY - 2018/8/17

Y1 - 2018/8/17

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85053131950&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053131950&partnerID=8YFLogxK

U2 - 10.1109/DSW.2018.8439919

DO - 10.1109/DSW.2018.8439919

M3 - Conference contribution

AN - SCOPUS:85053131950

SN - 9781538644102

T3 - 2018 IEEE Data Science Workshop, DSW 2018 - Proceedings

SP - 229

EP - 233

BT - 2018 IEEE Data Science Workshop, DSW 2018 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE Data Science Workshop, DSW 2018

Y2 - 4 June 2018 through 6 June 2018

ER -