Current browse context:
math.OC
Change to browse by:
References & Citations
Mathematics > Optimization and Control
Title: All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs
(Submitted on 23 Apr 2024 (v1), last revised 26 Apr 2024 (this version, v2))
Abstract: The fields of effective resistance and optimal transport on graphs are filled with rich connections to combinatorics, geometry, machine learning, and beyond. In this article we put forth a bold claim: that the two fields should be understood as one and the same, up to a choice of $p$. We make this claim precise by introducing the parameterized family of $p$-Beckmann distances for probability measures on graphs and relate them sharply to certain Wasserstein distances. Then, we break open a suite of results including explicit connections to optimal stopping times and random walks on graphs, graph Sobolev spaces, and a Benamou-Brenier type formula for $2$-Beckmann distance. We further explore empirical implications in the world of unsupervised learning for graph data and propose further study of the usage of these metrics where Wasserstein distance may produce computational bottlenecks.
Submission history
From: Sawyer Robertson [view email][v1] Tue, 23 Apr 2024 17:50:52 GMT (700kb,D)
[v2] Fri, 26 Apr 2024 17:25:56 GMT (700kb,D)
Link back to: arXiv, form interface, contact.