Optimal transport distances for directed, weighted graphs: a case study with cell-cell communication networks
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal transport with some directed distances
We present a toolkit of directed distances between quantile functions. By employing this, we solve some new optimal transport (OT) problems which e.g. considerably flexibilize some prominent OTs expressed through Wassers…
Distances for Markov Chains, and Their Differentiation
(Directed) graphs with node attributes are a common type of data in various applications and there is a vast literature on developing metrics and efficient algorithms for comparing them. Recently, in the graph learning a…
Graph LearningOptimal Transport for structured data with application on graphs
This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance (i.e. t…
ClusteringGraph ClassificationGraph ClusteringTime Series AnalysisEntropic Optimal Transport in Random Graphs
In graph analysis, a classic task consists in computing similarity measures between (groups of) nodes. In latent space random graphs, nodes are associated to unknown latent variables. One may then seek to compute distanc…
Embedding Directed Graphs in Potential Fields Using FastMap-D
Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, E…