Graph Joinings and Reversible Markov Chains

Every weighted, undirected graph describes a random walk on its vertex set, which is reversible Markov chain. I will describe recent work on graph joinings, which leverages this connection and ideas from optimal transport to gain insights into both graph isomorphisms and couplings of Markov chains. A joining of two graphs is a product graph that describes a reversible coupling of their random walks. Given two graphs with labeled vertices, the optimal graph joining (OGJ) problem identifies a joining that minimizes the total weight of vertex pairs with different labels. I will present new results showing that, for suitable families of labeled graphs, OGJ can detect and identify isomorphisms between graphsin the family. In the opposite direction, the study of joinings leads naturally to a notion of disjointness that quantifies structural discordance between graphs. I will present a simple characterization of weak disjointness, and show how this yields new insights into reversible couplings of reversible Markov chains.

Joint work with Yang Xiang, Phuong Hoang, Bongsoo Yi, and Kevin McGoff.