Stationary Optimal Transport with Applications to Graph Alignment

Andrew Nobel – University of North Carolina at Chapel Hill

Abstract

Optimal transport seeks to find couplings of two given distributions with minimum expected cost. This talk considers the setting in which the distributions of interest are stationary stochastic processes, and the cost function depends only on a finite number of coordinates. In this setting, I will argue that it is appropriate, and desirable, to restrict attention to stationary couplings, also known as joining.

The first part of the talk will address estimation of optimal joinings from observations of two ergodic processes. The second part of the talk addresses optimal transport for Markov chains via transition couplings. As an illustration, I will show how optimal transition couplings of Markov chains can be used to effectively compare two weighted graphs with potentially different node sets. This approach yields interpretable alignments of nodes and edges, has a desirable edge-preserving property, and accounts for graph factors when these exist.