Optimal Transport for Network Comparison: A Review with Machine Learning Applications

• URL: http://arxiv.org/abs/2608.27500v2
• Date: Wed, 02 Sep 2026 05:52:25 GMT
• Title: Optimal Transport for Network Comparison: A Review with Machine Learning Applications
• Abstract summary: We show how optimal transport compares undirected, unweighted graphs using three primary distances.<n>We show how the transport plans of the Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein distances visualize how mass is shifted to transform one network into another.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Network comparison using optimal transport is a growing area of research in network science. Unlike standard graph metrics, optimal transport computes both network dissimilarity and a transport plan that explains how one graph morphs into another. In this paper, we review how optimal transport compares undirected, unweighted graphs using three primary distances: the Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein distances. We examine the closed form of the Wasserstein distance in one dimension via node feature probability distributions, and show how the transport plans of the Wasserstein and Gromov-Wasserstein distances visualize how mass is shifted to transform one network into another. For the Bures-Wasserstein distance, we derive bounds in terms of the Laplacian spectra. Finally, we evaluate these distances using a synthetic network dataset for clustering and a real-world temporal network.

Related papers

• Fast Estimation of Wasserstein Distances via Regression on Sliced Wasserstein Distances [70.94157767200342]
  We propose a fast estimation method based on regressing Wasserstein distance on sliced Wasserstein distances.<n>We show that accurate models can be learned from a small number of distribution pairs.<n>Our method consistently provides a better approximation of Wasserstein distance than the state-of-the-art Wasserstein embedding model, Wasserstein Wormhole.
  arXiv  Detail & Related papers  (2025-09-24T19:30:53Z)
• All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
  We claim that effective resistance and optimal transport on graphs should be understood as one and the same, up to a choice of $p$.<n>We show explicit connections to optimal stopping times and random walks on graphs, graph Sobolev spaces, and a Benamou-Brenier type formula for $2$-Beckmann distance.<n>We propose further study of the usage of these metrics where Wasserstein distance may produce computational bottlenecks.
  arXiv  Detail & Related papers  (2024-04-23T17:50:52Z)
• Stereographic Spherical Sliced Wasserstein Distances [9.605542733966201]
  We introduce a high-speed and highly parallelizable distance for comparing spherical measures using the stereographic projection and the generalized Radon transform. We evaluate the performance of the proposed metrics and compare them with recent baselines in terms of both speed and accuracy.
  arXiv  Detail & Related papers  (2024-02-04T05:03:06Z)
• Point Cloud Classification via Deep Set Linearized Optimal Transport [51.99765487172328]
  We introduce Deep Set Linearized Optimal Transport, an algorithm designed for the efficient simultaneous embedding of point clouds into an $L2-$space. This embedding preserves specific low-dimensional structures within the Wasserstein space while constructing a classifier to distinguish between various classes of point clouds. We showcase the advantages of our algorithm over the standard deep set approach through experiments on a flow dataset with a limited number of labeled point clouds.
  arXiv  Detail & Related papers  (2024-01-02T23:26:33Z)
• Federated Wasserstein Distance [16.892296712204597]
  We introduce a principled way of computing the Wasserstein distance between two distributions in a federated manner. We show how to estimate the Wasserstein distance between two samples stored and kept on different devices/clients whilst a central entity/server orchestrates the computations.
  arXiv  Detail & Related papers  (2023-10-03T11:30:50Z)
• Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance [18.522233517515975]
  We introduce an extension of Gromov-Wasserstein distance for comparing graphs whose both nodes and edges have features. We empirically show the effectiveness of the novel distance in learning tasks where graphs occur in either input space or output space.
  arXiv  Detail & Related papers  (2023-09-28T17:05:03Z)
• Optimal transport distances for directed, weighted graphs: a case study with cell-cell communication networks [5.079602839359521]
  We propose two distance measures to compare directed graphs based on variants of optimal transport. We evaluate these two distances and discuss their relative performance for both simulated graph data and real-world directed cell-cell communication graphs.
  arXiv  Detail & Related papers  (2023-09-13T15:36:39Z)
• Fast Optimal Transport through Sliced Wasserstein Generalized Geodesics [14.259614797710224]
  min-SWGG is a proxy of the squared WD based on an optimal one-dimensional projection of the two input distributions. We show that min-SWGG is an upper bound of WD and that it has a complexity similar to Sliced-Wasserstein. Empirical evidences support the benefits of min-SWGG in various contexts.
  arXiv  Detail & Related papers  (2023-07-04T15:20:41Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
  arXiv  Detail & Related papers  (2022-10-15T08:01:08Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance approximation.
  arXiv  Detail & Related papers  (2021-09-09T17:43:07Z)
• Fast and Scalable Optimal Transport for Brain Tractograms [4.610968512889579]
  We present a new multiscale algorithm for solving regularized Optimal Transport problems on a linear memory footprint. We show the effectiveness of this approach on brain tractograms modeled either as bundles of fibers or as track density maps.
  arXiv  Detail & Related papers  (2021-07-05T13:28:41Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
  arXiv  Detail & Related papers  (2021-02-05T04:25:28Z)
• Max-Sliced Wasserstein Distance and its use for GANs [55.09958914575673]
  Generative adversarial nets (GANs) and variational auto-encoders have significantly improved our distribution modeling capabilities.<n>We show that the sample complexity of the distance metrics remains one of the factors affecting GAN training.<n>We show that a proposed distance trains GANs on high-dimensional images up to a resolution of 256x256 easily.
  arXiv  Detail & Related papers  (2019-04-11T17:59:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.