pith. sign in

arxiv: 2404.15261 · v4 · submitted 2024-04-23 · 🧮 math.OC · cs.DM· cs.LG· math.PR

Resistance Distance and Linearized Optimal Transport on Graphs

Sawyer Robertson , Zhengchao Wan , Alexander Cloninger This is my paper

Pith reviewed 2026-05-24 02:09 UTC · model grok-4.3

classification 🧮 math.OC cs.DMcs.LGmath.PR
keywords resistance distanceoptimal transport on graphsgraph LaplacianMaas distancerandom walkspectral gaplinearization
0
0 comments X

The pith

For small perturbations of a reference measure on a connected graph, the squared Maas transportation distance is bounded by the quadratic form of the pseudoinverse of a re-weighted Laplacian.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a local linearization result for the discrete optimal transport distance introduced by Maas on finite graphs. When a probability measure ν differs from a fixed reference μ by a small additive perturbation, the square of their transport distance is comparable to a quadratic form involving the pseudoinverse of a Laplacian matrix whose weights depend on μ. In the special case where μ is stationary for the simple random walk, this reduces to a resistance distance between measures that admits several equivalent definitions, including one based on spanning forests and one based on random walk hitting times. The same construction turns the space of measures into a manifold where the continuous-time random walk is the gradient flow of the chi-squared divergence, and the rate of convergence is governed by the spectral gap of the normalized Laplacian.

Core claim

The central claim is a nonasymptotic local linearization theorem: if ν is a small additive perturbation of μ on a connected weighted graph, then the squared Maas transport distance between them is controlled from above and below by the quadratic form of the pseudoinverse of a re-weighted graph Laplacian. When μ is the stationary distribution, the weights are the original edge weights and the expression becomes the resistance distance (μ − ν)⊤ L† (μ − ν), which equals the minimal Beckmann flow cost, a dual Sobolev norm, a sum over spanning 2-forests, and an expression in terms of hitting times.

What carries the argument

The pseudoinverse of the re-weighted graph Laplacian, whose quadratic form provides the local approximation to the squared discrete transportation distance.

If this is right

  • The resistance distance admits a Beckmann formula as the minimal cost of a flow with given divergence.
  • It equals a homogeneous Sobolev norm in the dual formulation.
  • A spanning 2-forest formula gives an explicit combinatorial expression.
  • The gradient flow of the χ² functional on the resistance manifold is the continuous-time random walk.
  • The geodesic strong convexity modulus of the χ² functional equals the spectral gap of the normalized Laplacian.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This identification may allow the use of fast Laplacian solvers to approximate transport distances for nearby measures.
  • The manifold structure could extend to the study of other convex functionals on the space of measures.
  • The connection to hitting times suggests possible links to mixing time analysis in Markov chains.

Load-bearing premise

The graph is connected, the reference density μ is positive on all vertices, and the perturbation to obtain ν is sufficiently small.

What would settle it

On a small cycle graph with uniform μ, pick a small signed perturbation h with sum zero, compute both the exact Maas transport distance squared and the quadratic form h^T L^dagger h, and verify whether the ratio lies between the explicit constants given by the theorem.

Figures

Figures reproduced from arXiv: 2404.15261 by Alexander Cloninger, Sawyer Robertson, Zhengchao Wan.

Figure 1
Figure 1. Figure 1: A side-by-side comparison of optimal flows for the 1-Beckmann and 2-Beckmann problems on a 4 × 4 hexagonal lattice graph. The masses of µ, ν at each node are rendered proportionally to opacity; and similarly the optimal flow values at each edge are rendered proportionally to opacity. The arrows indicate orientation of the flow value; i.e., ◦ → ◦′ if the optimal flow J satisfies J(◦, ◦ ′ ) > 0 and ◦ ← ◦′ if… view at source ↗
Figure 2
Figure 2. Figure 2: (a)-(b) Illustrations of two measures µ, ν and their edge cdfs Kµ, Kν for the fixed path graph P3. (c)-(d) Plots of the empirical cdfs Fµb and Fνb, as well as their inverses. Note that the shaded regions are reflections of each other; and that for p = 1 their common area is B1(µ, ν) = W1(µ, ν). This also demonstrates the divergence of the metrics for p > 1 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Two illustrations of 1000 simulated simple random walks on the dodecahedral graph with given initial distribution, illustrated with node opac￾ity proportional to density; and na¨ıve stopping rule according to the given stopping distribution, illustrated with opposite node color and opacity pro￾portional to density. The edges are dashed only to indicate depth, and edge opacity is proportional to the total n… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the preprocessing pipeline for the digits data, with an example from the class of handwritten zeros. The first step is a mass normalization to convert the pixel values into a fixed-sum distribution viewed on the nodes V of the 8 × 8 lattice graph. The second step is an embedding µ 7→ L −1/2µ, such that ℓ2 distance in the target corresponds to 2-Beckmann distance in P(V ). When computing … view at source ↗
Figure 5
Figure 5. Figure 5: Using the digits dataset, and for each pair of digit classes, we computed the pairwise 2-Beckmann and 2-Wasserstein distances for each pair of samples originating from the respective digit classes (with around 30,000 pairs of distances per pair of digit classes). Within each tile of the grid, we render a scatterplot of the distances over the overall linear regression between B2 and W2 for the experiment gi… view at source ↗
Figure 6
Figure 6. Figure 6: (a)-(b) Using the digits dataset, we demonstrate the results of an unsupervised clustering algorithm with different choices of similarity kernel. Each node corresponds to an image of a digit, which we featurize as a distribution on the 8 × 8 square lattice graph. We built a k = 42 nearest neighbor graph on the nodes (shown), and then apply spectral clustering [87] to create predicted classes. The text labe… view at source ↗
Figure 7
Figure 7. Figure 7: A sketch of a vertex neighborhood in an oriented tree. Proof of Proposition 2.15. Once again the proof of this result is a matter of rigid feasi￾bility: there can only really be one feasible flow J ∈ ℓ(E ′ ) satisfying BJ = µ − ν owing to, e.g., rank considerations for Laplacians on trees. Thus it is enough only to establish that B(Kµ − Kν) = µ − ν. Let i ∈ V be fixed, and suppose i has N incoming oriented… view at source ↗
read the original abstract

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 $\mu$ on its vertices, our main result is a nonasymptotic local linearization theorem showing that if $\nu$ is a small additive perturbation of $\mu$ 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 $(\mu-\nu)^\top L_w^\dagger (\mu-\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 $\chi^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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper establishes a nonasymptotic local linearization result for the Maas transportation distance on finite weighted graphs. For a connected graph with reference probability μ, if ν is a sufficiently small additive perturbation of μ, the squared distance is bounded above and below by the quadratic form (μ−ν)^⊤M^†(μ−ν) where M is a re-weighted Laplacian; when μ is stationary this reduces to the effective-resistance quadratic form (μ−ν)^⊤L_w^†(μ−ν). The work supplies combinatorial and variational characterizations of this form (Beckmann, Benamou–Brenier, dual Sobolev, spanning 2-forest, hitting-time) and shows that the induced resistance manifold makes the χ² gradient flow coincide with the continuous-time random walk whose geodesic strong-convexity modulus equals the normalized-Laplacian spectral gap, thereby recovering the classical exponential convergence rate.

Significance. The result supplies a direct, parameter-free link between linearized optimal transport on graphs and the resistance distance induced by the graph Laplacian. The recovery of the spectral-gap convergence fact via the geometry of the resistance manifold is a clean consistency check. The listed characterizations (especially the spanning-forest and hitting-time formulas) are useful and the derivation appears internally consistent with the Maas construction and standard spectral graph theory.

major comments (2)
  1. [Theorem 3.1] Theorem 3.1 (or the main linearization statement): the constants C1, C2 in the two-sided bound are stated to depend only on μ and the graph, but the proof sketch does not make the dependence on the minimal edge weight or the diameter explicit; an explicit (even if non-sharp) expression would strengthen the non-asymptotic claim.
  2. [Section 4.2] Section 4.2, the spanning-2-forest formula: the factor 2^{n-2} appears without derivation; a short verification that the formula reduces to the known Kirchhoff matrix-tree count when μ=ν would be helpful for readers.
minor comments (2)
  1. [§2.3 and Theorem 3.1] Notation: the re-weighted Laplacian M is introduced in §2.3 but its precise dependence on the perturbation size is not restated in the statement of the main theorem; a one-line reminder would improve readability.
  2. [Figure 1] Figure 1: the caption does not indicate whether the plotted curves are for the exact Maas distance or its quadratic approximation; adding this information would clarify the numerical illustration.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation for minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [Theorem 3.1] Theorem 3.1 (or the main linearization statement): the constants C1, C2 in the two-sided bound are stated to depend only on μ and the graph, but the proof sketch does not make the dependence on the minimal edge weight or the diameter explicit; an explicit (even if non-sharp) expression would strengthen the non-asymptotic claim.

    Authors: We agree that an explicit (even if non-sharp) dependence on the minimal edge weight and diameter would strengthen the non-asymptotic claim. In the revised version we will add such bounds, derived from the existing proof by tracking the constants through the estimates on the graph distance and the minimal conductance. revision: yes

  2. Referee: [Section 4.2] Section 4.2, the spanning-2-forest formula: the factor 2^{n-2} appears without derivation; a short verification that the formula reduces to the known Kirchhoff matrix-tree count when μ=ν would be helpful for readers.

    Authors: We thank the referee for pointing this out. We will insert a short paragraph deriving the factor 2^{n-2} from the weighted matrix-tree theorem and verifying that the formula collapses to the classical Kirchhoff count (up to the normalization by μ) when μ=ν. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central result is a nonasymptotic local linearization of the Maas transportation distance for small perturbations ν of a reference measure μ on a connected graph. This bound is derived directly from the definition of the discrete transportation distance (originally due to the external 2011 Maas reference) by expanding the distance functional to second order and identifying the resulting quadratic form with the pseudoinverse of a re-weighted Laplacian; the derivation does not presuppose the quadratic form or fit parameters to data. When μ is stationary the weights recover the standard graph Laplacian, yielding the known resistance quadratic form whose combinatorial and variational characterizations (Beckmann, Benamou-Brenier, spanning forests, hitting times) are standard facts about effective resistance and are invoked only after the linearization step. The final geometric claim equating the strong-convexity modulus of the χ² flow to the normalized Laplacian spectral gap follows from the same quadratic form and the variational characterization of the spectral gap; none of these steps reduce by construction to the paper's inputs or rely on load-bearing self-citations. The derivation is therefore self-contained against the external Maas construction and classical graph-Laplacian theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The work rests on the prior definition of Maas' discrete transportation distance and standard facts from graph theory; no free parameters are fitted and the only new object is the resistance manifold constructed from the derived distance.

axioms (2)
  • domain assumption The graph is finite and connected with a reference density μ on its vertices.
    Explicitly required for the statement of the main linearization theorem.
  • standard math Standard algebraic properties of the graph Laplacian and its Moore-Penrose pseudoinverse hold.
    Used to define the quadratic form that bounds the transportation distance.
invented entities (1)
  • resistance manifold no independent evidence
    purpose: Geometric space of probability measures equipped with the derived resistance distance
    Constructed in the paper from the quadratic form; no independent evidence outside the construction is supplied.

pith-pipeline@v0.9.0 · 5826 in / 1427 out tokens · 54897 ms · 2026-05-24T02:09:56.836462+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

93 extracted references · 93 canonical work pages · 2 internal anchors

  1. [1]

    Geometry of graph partitions via optimal transport.SIAM Journal on Scientific Computing , 42(5), 2020

    Tara Abrishami, Nestor Guillen, Parker Rule, Zachary Schutzman, Justin Solomon, Thomas Weighill, and Si Wu. Geometry of graph partitions via optimal transport.SIAM Journal on Scientific Computing , 42(5), 2020

    work page 2020

  2. [2]

    Phase transition in the family of p-resistances

    Morteza Alamgir and Ulrike Luxburg. Phase transition in the family of p-resistances. Advances in neural information processing systems , 24, 2011

    work page 2011

  3. [3]

    Alpaydin and Fevzi

    E. Alpaydin and Fevzi. Alimoglu. Pen-Based Recognition of Handwritten Digits. UCI Machine Learning Repository, 1998

    work page 1998

  4. [4]

    Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator

    Frank Bauer, J¨ urgen Jost, and Shiping Liu. Ollivier-Rricci curvature and the spectrum of the normalized graph laplace operator. arXiv preprint arXiv:1105.3803 , 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  5. [5]

    A continuous model of transportation

    Martin Beckmann. A continuous model of transportation. Econometrica: Journal of the Econometric Society, 1952

    work page 1952

  6. [6]

    Contributions to the theory of generalized inverses

    Adi Ben-Israel and A Charnes. Contributions to the theory of generalized inverses. Journal of the Society for Industrial and Applied Mathematics , 11(3), 1963

    work page 1963

  7. [7]

    A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem.Numerische Mathematik, 84(3):375–393, 2000

    Jean-David Benamou and Yann Brenier. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem.Numerische Mathematik, 84(3):375–393, 2000

    work page 2000

  8. [8]

    A hitting time formula for the discrete Green’s function

    Andrew Beveridge. A hitting time formula for the discrete Green’s function. Combina- torics, Probability and Computing , 25(3), 2016

    work page 2016

  9. [9]

    Exit frequency matrices for finite markov chains

    Andrew Beveridge and L´ aszl´ o Lov´ asz. Exit frequency matrices for finite markov chains. Combinatorics, Probability and Computing , 19(4), 2010

    work page 2010

  10. [10]

    Ef- fective resistance in metric spaces

    Robi Bhattacharjee, Alexander Cloninger, Yoav Freund, and Andreas Oslandsbotn. Ef- fective resistance in metric spaces. arXiv preprint arXiv:2306.15649 , 2023

    work page arXiv 2023

  11. [11]

    Statistical data analysis in the Wasserstein space.ESAIM: Proceedings and Surveys, 68, 2020

    J´ er´ emie Bigot. Statistical data analysis in the Wasserstein space.ESAIM: Proceedings and Surveys, 68, 2020

    work page 2020

  12. [12]

    Understanding over- squashing in GNNs through the lens of effective resistance

    Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding over- squashing in GNNs through the lens of effective resistance. In International Conference on Machine Learning, pages 2528–2547. PMLR, 2023

    work page 2023

  13. [13]

    Automated identification of stratifying signatures in cellular subpopulations

    Robert V Bruggner, Bernd Bodenmiller, David L Dill, Robert J Tibshirani, and Garry P Nolan. Automated identification of stratifying signatures in cellular subpopulations. Proceedings of the National Academy of Sciences , 111(26), 2014

    work page 2014

  14. [14]

    API design for machine learning software: experiences from the scikit-learn project

    Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Ga¨ el Varoquaux. API design for machine learning software: experiences from the scikit-learn project. InECML PKDD Workshop: Lan...

    work page 2013

  15. [15]

    Spanning tree methods for sampling graph partitions

    Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule. Spanning tree methods for sampling graph partitions. arXiv preprint arXiv:2210.01401 , 2022

    work page arXiv 2022

  16. [16]

    Optimal transport graph neural networks

    Benson Chen, Gary B´ ecigneul, Octavian-Eugen Ganea, Regina Barzilay, and Tommi Jaakkola. Optimal transport graph neural networks. arXiv preprint arXiv:2006.04804 , 2020

    work page arXiv 2006

  17. [17]

    Weisfeiler-Lehman meets Gromov-Wasserstein

    Samantha Chen, Sunhyuk Lim, Facundo M´ emoli, Zhengchao Wan, and Yusu Wang. Weisfeiler-Lehman meets Gromov-Wasserstein. InInternational Conference on Machine Learning, pages 3371–3416. PMLR, 2022

    work page 2022

  18. [18]

    Ranking and sparsifying a connection graph

    Fan Chung, Wenbo Zhao, and Mark Kempton. Ranking and sparsifying a connection graph. Internet Mathematics, 10(1-2), 2014. ALL YOU NEED IS RESISTANCE 27

    work page 2014

  19. [19]

    Random walks, conductance, and resistance for the connection graph Laplacian

    Alex Cloninger, Gal Mishne, Andreas Oslandsbotn, Sawyer Jack Robertson, Zhengchao Wan, and Yusu Wang. Random walks, conductance, and resistance for the connection graph Laplacian. SIAM Journal on Matrix Analysis and Applications , 45(3), 2024

    work page 2024

  20. [20]

    People mover’s distance: Class level geometry using fast pairwise data adaptive transportation costs

    Alexander Cloninger, Brita Roy, Carley Riley, and Harlan M Krumholz. People mover’s distance: Class level geometry using fast pairwise data adaptive transportation costs. Applied and Computational Harmonic Analysis , 47(1), 2019

    work page 2019

  21. [21]

    Lin- earized Wasserstein dimensionality reduction with approximation guarantees

    Alexander Cloninger, Keaton Hamm, Varun Khurana, and Caroline Moosm¨ uller. Lin- earized Wasserstein dimensionality reduction with approximation guarantees. arXiv preprint arXiv:2302.07373, 2023

    work page arXiv 2023

  22. [22]

    Discrete curvature on graphs from the effective resistance

    Karel Devriendt and Renaud Lambiotte. Discrete curvature on graphs from the effective resistance. Journal of Physics: Complexity , 3(2), 2022

    work page 2022

  23. [23]

    Graph curvature via resis- tance distance

    Karel Devriendt, Andrea Ottolini, and Stefan Steinerberger. Graph curvature via resis- tance distance. Discrete Applied Mathematics, 348, 2024

    work page 2024

  24. [24]

    CVXPY: A Python-embedded modeling language for convex optimization

    Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research , 2016

    work page 2016

  25. [25]

    Random walks and electric networks , volume 22

    Peter G Doyle and J Laurie Snell. Random walks and electric networks , volume 22. American Mathematical Soc., 1984

    work page 1984

  26. [26]

    Nonlocal discrete reg- ularization on weighted graphs: a framework for image and manifold processing

    Abderrahim Elmoataz, Olivier Lezoray, and S´ ebastien Bougleux. Nonlocal discrete reg- ularization on weighted graphs: a framework for image and manifold processing. IEEE transactions on Image Processing, 17(7), 2008

    work page 2008

  27. [27]

    On the p-Laplacian and infinity-Laplacian on graphs with applications in image and data processing

    Abderrahim Elmoataz, Matthieu Toutain, and Daniel Tenbrinck. On the p-Laplacian and infinity-Laplacian on graphs with applications in image and data processing. SIAM Journal on Imaging Sciences , 8(4), 2015

    work page 2015

  28. [28]

    Quadratically regularized optimal transport on graphs

    Montacer Essid and Justin Solomon. Quadratically regularized optimal transport on graphs. SIAM Journal on Scientific Computing , 40(4), 2018

    work page 2018

  29. [29]

    Partial differential equations and Monge-Kantorovich mass transfer

    Lawrence C Evans. Partial differential equations and Monge-Kantorovich mass transfer. Current developments in mathematics , 1997(1), 1997

    work page 1997

  30. [30]

    Differential equations methods for the Monge- Kantorovich mass transfer problem

    Lawrence C Evans and Wilfrid Gangbo. Differential equations methods for the Monge- Kantorovich mass transfer problem . American Mathematical Soc., 1999

    work page 1999

  31. [31]

    Wasserstein graph dis- tance based on l1–approximated tree edit distance between Weisfeiler–Lehman subtrees

    Zhongxi Fang, Jianming Huang, Xun Su, and Hiroyuki Kasai. Wasserstein graph dis- tance based on l1–approximated tree edit distance between Weisfeiler–Lehman subtrees. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, 2023

    work page 2023

  32. [32]

    Optimal transport methods in economics

    Alfred Galichon. Optimal transport methods in economics . Princeton University Press, 2018

    work page 2018

  33. [33]

    The geometry of optimal transportation

    Wilfrid Gangbo and Robert J McCann. The geometry of optimal transportation. Acta Mathematica, 177, 1996

    work page 1996

  34. [34]

    Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs

    Jun Ge and Fengming Dong. Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs. Discrete Applied Mathematics, 283, 2020

    work page 2020

  35. [35]

    Benamou-Brenier’s approach for ott

    Augusto Gerolin. Benamou-Brenier’s approach for ott. In Optimal Transport and Ap- plications. Summer School, Lake Arrowhead, 2013

    work page 2013

  36. [36]

    Resistance distance in complete n-partite graphs

    Severino V Gervacio. Resistance distance in complete n-partite graphs. Discrete Applied Mathematics, 203, 2016

    work page 2016

  37. [37]

    On a linearization of quadratic Wasserstein distance

    Philip Greengard, Jeremy G Hoskins, Nicholas F Marshall, and Amit Singer. On a linearization of quadratic Wasserstein distance. arXiv preprint arXiv:2201.13386, 2022

    work page arXiv 2022

  38. [38]

    Optimal mass trans- port for registration and warping

    Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent. Optimal mass trans- port for registration and warping. International Journal of computer vision , 60, 2004. 28 ROBERTSON, W AN, CLONINGER

    work page 2004

  39. [39]

    Comparing partitions

    Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification , 2, 1985

    work page 1985

  40. [40]

    Operator theory and analysis of infinite networks , volume 7

    Palle Jorgensen and Erin PJ Pearse. Operator theory and analysis of infinite networks , volume 7. World Scientific, 2023

    work page 2023

  41. [41]

    On the translocation of masses

    Leonid V Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), volume 37, 1942

    work page 1942

  42. [42]

    Large scale spectral clustering using re- sistance distance and spielman-teng solvers

    Nguyen Lu Dang Khoa and Sanjay Chawla. Large scale spectral clustering using re- sistance distance and spielman-teng solvers. In Discovery Science: 15th International Conference, DS 2012, Lyon, France, October 29-31, 2012. Proceedings 15 . Springer, 2012

    work page 2012

  43. [43]

    Su- pervised learning of sheared distributions using linearized optimal transport

    Varun Khurana, Harish Kannan, Alexander Cloninger, and Caroline Moosm¨ uller. Su- pervised learning of sheared distributions using linearized optimal transport. Sampling Theory, Signal Processing, and Data Analysis , 21(1), 2023

    work page 2023

  44. [44]

    From word embeddings to document distances

    Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document distances. In International conference on machine learning . PMLR, 2015

    work page 2015

  45. [45]

    Tree-sliced variants of Wasserstein distances

    Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of Wasserstein distances. Advances in neural information processing systems , 32, 2019

    work page 2019

  46. [46]

    Sobolev transport: A scalable metric for probability measures with graph metrics

    Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen. Sobolev transport: A scalable metric for probability measures with graph metrics. InInternational Conference on Artificial Intelligence and Statistics , pages 9844–9868. PMLR, 2022

    work page 2022

  47. [47]

    Scalable unbalanced Sobolev transport for measures on a graph

    Tam Le, Truyen Nguyen, and Kenji Fukumizu. Scalable unbalanced Sobolev transport for measures on a graph. In International Conference on Artificial Intelligence and Sta- tistics. PMLR, 2023

    work page 2023

  48. [48]

    Generalized Sobolev transport for prob- ability measures on a graph

    Tam Le, Truyen Nguyen, and Kenji Fukumizu. Generalized Sobolev transport for prob- ability measures on a graph. arXiv preprint arXiv:2402.04516 , 2024

    work page arXiv 2024

  49. [49]

    An efficient earth mover’s distance algorithm for robust histogram comparison

    Haibin Ling and Kazunori Okada. An efficient earth mover’s distance algorithm for robust histogram comparison. IEEE transactions on pattern analysis and machine in- telligence, 29(5), 2007

    work page 2007

  50. [50]

    Random walks on graphs.Combinatorics, Paul erdos is eighty , 2(1-46), 1993

    L´ aszl´ o Lov´ asz. Random walks on graphs.Combinatorics, Paul erdos is eighty , 2(1-46), 1993

    work page 1993

  51. [51]

    Efficient stopping rules for Markov chains

    L´ aszl´ o Lov´ asz and Peter Winkler. Efficient stopping rules for Markov chains. InPro- ceedings of the twenty-seventh annual ACM symposium on Theory of computing , 1995

    work page 1995

  52. [52]

    Mixing of random walks and other diffusions on a graph

    L´ aszl´ o Lov´ asz and Peter Winkler. Mixing of random walks and other diffusions on a graph. London Mathematical Society Lecture Note Series , 1995

    work page 1995

  53. [53]

    Wasserstein distance and metric trees

    Maxime Mathey-Prevot and Alain Valette. Wasserstein distance and metric trees. L’Enseignement Math´ ematique, 69(3), 2023

    work page 2023

  54. [54]

    Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space

    Quentin M´ erigot, Alex Delalande, and Frederic Chazal. Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space. InInternational Conference on Artificial Intelligence and Statistics . PMLR, 2020

    work page 2020

  55. [55]

    The problem of redistricting: the use of centroidal Voronoi diagrams to build unbiased congressional districts

    Stacy Miller. The problem of redistricting: the use of centroidal Voronoi diagrams to build unbiased congressional districts. Senior project, Whitman College , 2007

    work page 2007

  56. [56]

    M´ emoire sur la th´ eorie des d´ eblais et des remblais.Mem

    Gaspard Monge. M´ emoire sur la th´ eorie des d´ eblais et des remblais.Mem. Math. Phys. Acad. Royale Sci., 1781

    work page

  57. [57]

    Kantorovich distance on a weighted graph

    LUIGI Montrucchio and Giovanni Pistone. Kantorovich distance on a weighted graph. arXiv preprint arXiv:1905.07547 , 1420, 2019. ALL YOU NEED IS RESISTANCE 29

    work page arXiv 1905

  58. [58]

    Linear optimal transport embedding: Provable Wasserstein classification for certain rigid transformations and perturbations

    Caroline Moosm¨ uller and Alexander Cloninger. Linear optimal transport embedding: Provable Wasserstein classification for certain rigid transformations and perturbations. arXiv preprint arXiv:2008.09165 , 2020

    work page arXiv 2008

  59. [59]

    Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds

    Florentin M¨ unch and Rados law K Wojciechowski. Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds. Advances in Mathematics, 356, 2019

    work page 2019

  60. [60]

    New resistance distances with global infor- mation on large graphs

    Canh Hao Nguyen and Hiroshi Mamitsuka. New resistance distances with global infor- mation on large graphs. In Artificial intelligence and statistics . PMLR, 2016

    work page 2016

  61. [61]

    Statistical aspects of Wasserstein distances.Annual review of statistics and its application , 6, 2019

    Victor M Panaretos and Yoav Zemel. Statistical aspects of Wasserstein distances.Annual review of statistics and its application , 6, 2019

    work page 2019

  62. [62]

    Computational optimal transport

    Gabriel Peyr´ e, Marco Cuturi, et al. Computational optimal transport. Center for Re- search in Economics and Statistics Working Papers , 1(2017-86), 2017

    work page 2017

  63. [63]

    Comparison between w2 distance and h- 1 norm, and localization of Wasser- stein distance

    R´ emi Peyre. Comparison between w2 distance and h- 1 norm, and localization of Wasser- stein distance. ESAIM: Control, Optimisation and Calculus of Variations , 24(4), 2018

    work page 2018

  64. [64]

    On Wasserstein two-sample testing and related families of nonparametric tests

    Aaditya Ramdas, Nicol´ as Garc´ ıa Trillos, and Marco Cuturi. On Wasserstein two-sample testing and related families of nonparametric tests. Entropy, 19(2), 2017

    work page 2017

  65. [65]

    On a general- ization of Wasserstein distance and the Beckmann problem to connection graphs

    Sawyer Robertson, Dhruv Kohli, Gal Mishne, and Alexander Cloninger. On a general- ization of Wasserstein distance and the Beckmann problem to connection graphs. arXiv preprint arXiv:2312.10295, 2023

    work page arXiv 2023

  66. [66]

    V-measure: A conditional entropy-based exter- nal cluster evaluation measure

    Andrew Rosenberg and Julia Hirschberg. V-measure: A conditional entropy-based exter- nal cluster evaluation measure. In Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL), 2007

    work page 2007

  67. [67]

    Vector and matrix op- timal mass transport: theory, algorithm, and applications

    Ernest K Ryu, Yongxin Chen, Wuchen Li, and Stanley Osher. Vector and matrix op- timal mass transport: theory, algorithm, and applications. SIAM Journal on Scientific Computing, 40(5), 2018

    work page 2018

  68. [68]

    Multi-class graph clustering via approximated effective p-resistance

    Shota Saito and Mark Herbster. Multi-class graph clustering via approximated effective p-resistance. In International Conference on Machine Learning . PMLR, 2023

    work page 2023

  69. [69]

    Improving GANs Using Optimal Transport

    Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving GANs using optimal transport. arXiv preprint arXiv:1803.05573 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  70. [70]

    Com- parative analysis of two discretizations of Ricci curvature for complex networks

    Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and J¨ urgen Jost. Com- parative analysis of two discretizations of Ricci curvature for complex networks. Scien- tific reports, 8(1), 2018

    work page 2018

  71. [71]

    Optimal transport for applied mathematicians

    Filippo Santambrogio. Optimal transport for applied mathematicians. Birk¨ auser, NY, 55(58-63), 2015

    work page 2015

  72. [72]

    Optimal- transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming

    Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, et al. Optimal- transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4), 2019

    work page 2019

  73. [73]

    On general minimax theorems

    Maurice Sion. On general minimax theorems. Pacific J. Math. , 8(4), 1958

    work page 1958

  74. [74]

    Optimal transport on discrete domains

    Justin Solomon. Optimal transport on discrete domains. AMS Short Course on Discrete Differential Geometry, 2018

    work page 2018

  75. [75]

    Earth mover’s distances on discrete surfaces

    Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. Earth mover’s distances on discrete surfaces. ACM Transactions on Graphics (ToG), 33(4), 2014

    work page 2014

  76. [76]

    Graph sparsification by effective resistances

    Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium on Theory of computing , 2008. 30 ROBERTSON, W AN, CLONINGER

    work page 2008

  77. [77]

    A Wasserstein inequality and minimal green energy on compact manifolds

    Stefan Steinerberger. A Wasserstein inequality and minimal green energy on compact manifolds. Journal of Functional Analysis , 281(5), 2021

    work page 2021

  78. [78]

    Kron reduction and effective resistance of di- rected graphs

    Tomohiro Sugiyama and Kazuhiro Sato. Kron reduction and effective resistance of di- rected graphs. SIAM Journal on Matrix Analysis and Applications , 44(1), 2023

    work page 2023

  79. [79]

    Supervised tree-Wasserstein dis- tance

    Yuki Takezawa, Ryoma Sato, and Makoto Yamada. Supervised tree-Wasserstein dis- tance. In International Conference on Machine Learning . PMLR, 2021

    work page 2021

  80. [80]

    Fixed support tree-sliced wasserstein barycenter

    Yuki Takezawa, Ryoma Sato, Zornitsa Kozareva, Sujith Ravi, and Makoto Yamada. Fixed support tree-sliced wasserstein barycenter. IEICE Technical Report; IEICE Tech. Rep., 122(325), 2022

    work page 2022

Showing first 80 references.