Resistance Distance and Linearized Optimal Transport on Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908944570515456 |
|---|---|
| author | Robertson, Sawyer Wan, Zhengchao Cloninger, Alexander |
| author_facet | Robertson, Sawyer Wan, Zhengchao Cloninger, Alexander |
| contents | 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 {M}arkov 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 $ν$ 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 $(μ-ν)^\top L_w^\dagger (μ-ν)$, 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 $χ^2$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15261 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Resistance Distance and Linearized Optimal Transport on Graphs Robertson, Sawyer Wan, Zhengchao Cloninger, Alexander Optimization and Control Discrete Mathematics Machine Learning Probability 49Q22, 05C21, 90C25, 68R10, 05C50 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 {M}arkov 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 $ν$ 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 $(μ-ν)^\top L_w^\dagger (μ-ν)$, 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 $χ^2$ 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. |
| title | Resistance Distance and Linearized Optimal Transport on Graphs |
| topic | Optimization and Control Discrete Mathematics Machine Learning Probability 49Q22, 05C21, 90C25, 68R10, 05C50 |
| url | https://arxiv.org/abs/2404.15261 |