{
  "id": "1706.07450",
  "version": "v1",
  "published": "2017-06-22T18:18:58.000Z",
  "updated": "2017-06-22T18:18:58.000Z",
  "title": "A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks",
  "authors": [
    "Alex Nowak",
    "Soledad Villar",
    "Afonso S. Bandeira",
    "Joan Bruna"
  ],
  "categories": [
    "stat.ML",
    "cs.LG"
  ],
  "abstract": "Many inverse problems are formulated as optimization problems over certain 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 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 are used to supervise the training of an appropriate predictive model that parametrizes a broad class of algorithms, with the hope that the resulting \"algorithm\" 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-22T18:18:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "learning algorithms",
      "graph neural networks offer",
      "optimization problems",
      "quadratic assignment problem",
      "appropriate input distributions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}