### 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 language | English (US) |
---|---|

Title of host publication | 2018 IEEE Data Science Workshop, DSW 2018 - Proceedings |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 229-233 |

Number of pages | 5 |

ISBN (Print) | 9781538644102 |

DOIs | |

State | Published - Aug 17 2018 |

Event | 2018 IEEE Data Science Workshop, DSW 2018 - Lausanne, Switzerland Duration: Jun 4 2018 → Jun 6 2018 |

### Publication series

Name | 2018 IEEE Data Science Workshop, DSW 2018 - Proceedings |
---|

### Other

Other | 2018 IEEE Data Science Workshop, DSW 2018 |
---|---|

Country | Switzerland |

City | Lausanne |

Period | 6/4/18 → 6/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

*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