Simulations of Wasserstein Eigendistances

Wasserstein Eigendistances

Wasserstein eigendistances are intrinsic distances of a Markov chain. Here I considered simple random walks on various finite graphs. The distance between two vertices is a measure for how easy it is for the random walk to distinguish the two vertices.


The simulations show convergence to Wasserstein eigendistances starting from the trivial distance, where any two distinct nodes have distance 1. That is, we consider the map $$W(\rho)(x,y) = \inf_{\pi_{xy}}\int \rho \;d\pi,$$ where \(\pi_{xy}\) is a coupling of \(P_x\) and \(P_y\), the transition kernel of the random walk when starting in \(x\) or \(y\). Then we let \(\rho_0(x,y)=\delta_x(y)\) and \(\rho_{n+1}=\frac{W(\rho_n)}{\sup_{x,y}W(\rho_n)(x,y)}\). The numerical solutions are then embedded in the plane so that distances across an edge \(xy\) are close to \(\rho_n(x,y)\). The number of iterations increases in each time step to better illustrate the convergence.

6x6 grid

6x4 grid

Two connected 5x5 grids

Erdős–Rényi random graph

Another Erdős–Rényi random graph

Largest component of above graph

A ring of Erdős–Rényi random graphs

Cluster detection

The initial graph, embedded according to graph distance

Clustering based on Wasserstein eigendistances across edges less than 0.1

Same, but embedding corresponding to Wasserstein eigendistance