Abstract

Every weighted, undirected graph describes a simple random walk on its vertex set, which is a reversible Markov chain. In this talk I will describe recent work on graph joinings that leverages this elementary connection, in conjunction with ideas from optimal transport, to gain insights into both graph isomorphism and couplings of reversible Markov chains. Informally, a joining of two graphs is a product graph from which the given graphs can be recovered via marginalization. Given two graphs with labeled vertices, the optimal graph joining (OGJ) problem identifies a joining that minimizes the weighted degree of vertex pairs with different labels. For suitable families of labeled graphs, including trees and forests, OGJ can detect and identify isomorphisms between any two graphs in the family. In a different direction, I will describe several results showing how graph joinings yield new insights into the rigidity of reversible couplings of reversible Markov chains.

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