Optimal transport for stationary Markov chains with an application to the comparison and alignment of weighted graphs

Informally, the optimal transport problem is to align, or couple, two distributions of interest as best as possible with respect to some prespecified cost. This problem has long attracted the interest of researchers and practitioners in a wide range of fields. Recent algorithmic advances and new applications have led to a boom in popularity for transport-based techniques in the statistics and machine learning communities. Ideas from optimal transport have contributed to novel approaches in clustering, classification, estimation, modeling, and other tasks. In this talk, I will give an introduction to optimal transport, focusing on computational techniques and applications in statistics and machine learning. After doing this, I will discuss our work adapting the optimal transport problem to Markov chains. In particular, we introduce a new problem referred to as the optimal transition coupling problem that incorporates the Markov structure of the marginal chains directly. Intuitively, this new problem aims to synchronize the two Markov chains of interest as best as possible with respect to a cost specified by the user. Finally, I will describe how the optimal transition coupling problem may be used to compare and align weighted graphs. We demonstrate that this new approach to graph optimal transport is sensitive to differences in both local and global structure and improves upon existing approaches in a graph classification task.

This is based on joint work with Andrew Nobel, Kevin McGoff, and Bongsoo Yi.

Share this Event