Optimal Graph Joining and Graph Isomorphism

Music City Center 

In this talk, we will introduce a new notion of optimal joinings for undirected graphs, which is based on constrained optimal transport between the simple random walks on the graphs. After giving the definition of optimal joinings for undirected graphs, we will state some of the basic mathematical properties and then present results indicating that these optimal joinings can be used to detect and identify graph isomorphisms. We also present some numerical experiments with random graphs such as Erdos-Renyi models, stochastic block models. This is a joint work with Yang Xiang, Bongsoo Yi, Kevin McGoff, and Andrew B. Nobel.

joinings

optimal transport

graph isomorphism

random walks 

Section on Statistical Learning and Data Science