Optimal transport distances for directed, weighted graphs: a case study with cell-cell communication networks

• URL: http://arxiv.org/abs/2309.07030v3
• Date: Thu, 14 Mar 2024 10:23:57 GMT
• Title: Optimal transport distances for directed, weighted graphs: a case study with cell-cell communication networks
• Abstract summary: 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.
• Score: 5.079602839359521
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Comparing graphs by means of optimal transport has recently gained significant attention, as the distances induced by optimal transport provide both a principled metric between graphs as well as an interpretable description of the associated changes between graphs in terms of a transport plan. As the lack of symmetry introduces challenges in the typically considered formulations, optimal transport distances for graphs have mostly been developed for undirected graphs. Here, we propose two distance measures to compare directed graphs based on variants of optimal transport: (i) an earth movers distance (Wasserstein) and (ii) a Gromov-Wasserstein (GW) distance. We evaluate these two distances and discuss their relative performance for both simulated graph data and real-world directed cell-cell communication graphs, inferred from single-cell RNA-seq data.

Related papers

• Optimal Transport for Network Comparison: A Review with Machine Learning Applications [0.0]
  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.
  arXiv  Detail & Related papers  (2026-08-27T02:13:27Z)
• Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs [43.98782445210996]
  Optimal transport between graphs is a powerful tool for comparing and aligning graph structures.<n>We present Unbalanced Transport (ULOT) as a method to solve this problem.
  arXiv  Detail & Related papers  (2025-05-21T09:29:19Z)
• Robust Graph Matching Using An Unbalanced Hierarchical Optimal Transport Framework [30.05543844763625]
  We propose a novel and robust graph matching method based on an unbalanced hierarchical optimal transport framework. We make the first attempt to exploit cross-modal alignment in graph matching. Experiments on various graph matching tasks demonstrate the superiority and robustness of our method compared to state-of-the-art approaches.
  arXiv  Detail & Related papers  (2023-10-18T16:16:53Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• On a linear fused Gromov-Wasserstein distance for graph structured data [2.360534864805446]
  We propose a novel distance between two graphs, named linearFGW, defined as the Euclidean distance between their embeddings. The advantages of the proposed distance are twofold: 1) it can take into account node feature and structure of graphs for measuring the similarity between graphs in a kernel-based framework, 2) it can be much faster for computing kernel matrix than pairwise OT-based distances.
  arXiv  Detail & Related papers  (2022-03-09T13:43:18Z)
• 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)
• Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance [63.203951161394265]
  In modern machine learning it is common to encounter large graphs that arise via interactions or similarities between observations in many domains. We propose to compare and organize such datasets of graph signals by using an earth mover's distance (EMD) with a geodesic cost over the underlying graph. In each case, we show that UDEMD-based embeddings find accurate distances that are highly efficient compared to other methods.
  arXiv  Detail & Related papers  (2021-07-26T17:19:02Z)
• SGCN:Sparse Graph Convolution Network for Pedestrian Trajectory Prediction [64.16212996247943]
  We present a Sparse Graph Convolution Network(SGCN) for pedestrian trajectory prediction. Specifically, the SGCN explicitly models the sparse directed interaction with a sparse directed spatial graph to capture adaptive interaction pedestrians. visualizations indicate that our method can capture adaptive interactions between pedestrians and their effective motion tendencies.
  arXiv  Detail & Related papers  (2021-04-04T03:17:42Z)
• Graph Optimal Transport for Cross-Domain Alignment [121.80313648519203]
  Cross-domain alignment is fundamental to computer vision and natural language processing. We propose Graph Optimal Transport (GOT), a principled framework that germinates from recent advances in Optimal Transport (OT) Experiments show consistent outperformance of GOT over baselines across a wide range of tasks.
  arXiv  Detail & Related papers  (2020-06-26T01:14:23Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• COPT: Coordinated Optimal Transport for Graph Sketching [15.127728811011245]
  COPT is a novel distance metric between graphs defined via an optimization routine. We show theoretically that our method preserves important global structural information on graphs. Empirically, COPT outperforms state of the art methods in graph classification on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-03-09T02:30:23Z)

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.