All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs
This work addresses computational bottlenecks in graph-based machine learning by proposing new metrics, but it appears incremental as it builds on existing theories of effective resistance and optimal transport.
The paper claims that effective resistance and optimal transport on graphs are equivalent, introducing a family of p-Beckmann distances and relating them to Wasserstein distances, with results including connections to random walks and graph Sobolev spaces, and empirical implications for unsupervised learning on graph data.
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.