The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


Quadratic assignment, semidefinite programming, and graph neural networks.

Soledad Villar, NYU

Date and Time: Apr 25, 2018 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Quadratic assignment is a very general problem in theoretical computer science. It includes graph matching, the traveling salesman problem, and the Gromov-Hausdorff distance between finite metric spaces as particular cases. Quadratic assignment is in general NP-hard and even hard to approximate, but in fact the problem can be tractable for a large subset of instances. In this talk we present different algorithmic approaches that lead to meaningful results for different data models. A semidefinite relaxation provides a pseudometric that can be computed in polynomial-time and has similar topological properties to the GH distance. A projected power iteration algorithm succeeds at aligning noisy networks. And a graph neural network can actually learn an algorithm to solve network alignment and the traveling salesman problem from solved problem instances.