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 -