Resistance Distance and Linearized Optimal Transport on Graphs

We study the linearization of a discrete transportation distance between probability distributions on finite weighted graphs originally due to Maas (``Gradient flows of the entropy for finite Markov chains,'' J. Funct. Anal. 261(8), 2011) which demonstrates various connections to the underlying combinatorial structure of the graph. For a connected graph and a reference density μ on its vertices, our main result is a nonasymptotic local linearization theorem showing that if nu is a small additive perturbation of μ then their squared discrete transportation distance is controlled above and below by the quadratic form of the pseudoinverse of a re-weighted graph Laplacian matrix. When the reference measure is stationary for the simple random walk on the graph, the weights agree with the original graph and this yields the quadratic form (μ-nu)^top Lw^dagger (μ-nu), which can be viewed as a form of resistance distance between probability measures. This distance has a number of combinatorial and variational characterizations, including Beckmann and Benamou--Brenier formulas, a dual homogeneous Sobolev norm formula, a spanning 2-forest formula, and a representation through random walk hitting times. Finally, we show that on the resulting ``resistance manifold,'' the gradient flow of the chi2 functional is the continuous-time random walk and that its geodesic strong convexity modulus equals the spectral gap of the normalized Laplacian. From this geometric vantage point, one recovers the classical fact that the spectral gap of the normalized Laplacian controls the exponential convergence rate of the random walk to stationarity.