Dimension reduction in physical and data sciences

Permutation Invariance and Combinatorial Optimizations with Graph Deep Learning

Radu Balan

University of Maryland
[SLIDES]

In this talk we discuss two problems seemingly unrelated: representations of permutation invariant data sets and quadratic assignment optimization problems. Two matrices of same size are called permutation equivalent if they are equal to one another up to a row permutation. The first problem asks for an Euclidian embedding of the quotient space induced by the row permutation equivalence relation. As we shall see, the problem admits several equivalent formulations. We shall discuss representations inspired by results from commutative algebra theory, measure theory, and reproducing kernel Hilbert space theory. This problem has direct application to graph classification problems where the underlying network has a natural equivariance property. The quadratic assignment problem is a NP hard optimization problem. We shall analyze an approach using graph convolution networks (GCN). We prove that a specially designed GCN produces the optimal solution for a broad class of assignment problems.