Optimal Transport Distances for Directed, Weighted Graphs: A Case Study With Cell-Cell Communication Networks

James Shiniti Nagai, Ivan G. Costa, Michael T. Schaub

TL;DR

Comparing directed, weighted graphs is notoriously difficult because standard distance metrics often ignore edge directionality. This paper introduces two new frameworks based on Optimal Transport (OT)—specifically Wasserstein and Gromov-Wasserstein distances—that leverage directed node-to-node metrics like hitting times and effective resistance. The authors demonstrate that these methods can accurately cluster complex biological networks, such as cell-cell communication maps, where traditional undirected methods fail.

What Problem Does This Paper Address?

In many fields, from social science to biology, data is best represented as a directed graph (where connections have a specific "from-to" orientation). While we have many ways to compare undirected graphs, comparing directed ones is a challenge. Most existing tools either ignore the direction of the edges or rely on "graph features" (like counting triangles) that don't capture the global structure or "flow" of the network.

Optimal Transport (OT) has emerged as a powerful way to compare graphs because it doesn't just give a distance number; it provides a "transport plan" showing how one graph can be transformed into another. However, OT usually requires a symmetric distance between nodes (like the shortest path), which doesn't naturally exist in directed graphs. This paper fills that gap by adapting OT for directed, weighted networks, specifically targeting the noisy and sparse data found in single-cell biology.

Methods

The authors propose a two-step approach: first, define how far apart two nodes are within a directed graph, and second, use those distances to compare two different graphs.

  1. Node-to-Node Distances for Directed Graphs:
    • Generalized Effective Resistance (GRD): This treats the graph like an electrical circuit. While standard resistance is for undirected wires, GRD uses a "grounded" Laplacian and Lyapunov equations to account for directed "flow."
    • Hitting Time Distance (HTD): This is based on Markov chains. It measures how long a random walker would take to travel from node A to node B.
  2. Graph-to-Graph Distances:
    • Gromov-Wasserstein (GW): This compares the internal "geometries" of two graphs. It looks for a mapping that preserves the relative distances between nodes as much as possible.
  3. Wasserstein (Earth Mover's Distance) via Linegraphs: This is a clever trick. The authors convert the original graph into a "linegraph," where the edges of the original graph become the nodes of the new one. They then treat the edge weights as a probability distribution and use standard OT to compare them.

Datasets

  • Synthetic Graphs: A "cycle of cycles" model. This consists of four local cycles connected in a larger global cycle. It was designed to test if the metrics could distinguish between "local" edge flips and "global" edge flips.
  • Real-World Biological Data:
    • Pancreas Cancer (n=35): Cell-cell communication networks inferred from single-cell RNA-seq data.
  • Heart Myocardial Infarction (n=20): Similar communication networks used to distinguish between healthy and diseased states.

Key Insights and Ideas

  • Directionality is Non-Negotiable: In the synthetic "cycle of cycles" test, undirected metrics (like the Frobenius norm or standard Graph Optimal Transport) assigned a distance of zero to graphs that were structurally different but identical if you ignored arrow directions. The proposed directed metrics successfully distinguished them.
  • The "Global" vs. "Local" Effect: The authors found that flipping a "global" edge (one that connects major clusters) results in a much larger distance than flipping a "local" edge. This suggests these metrics capture the "flow circulation" of the network.
  • Wasserstein > Gromov-Wasserstein for Noise: For the biological case studies, the Wasserstein formulation (using the linegraph approach) significantly outperformed the Gromov-Wasserstein approach. The authors hypothesize that the linegraph construction is more adaptive and robust to the "dropouts" (missing data) common in single-cell sequencing.

Key Results

The primary evaluation metric was the Adjusted Rand Index (ARI), which measures how well the graph distances allowed a k-means algorithm to cluster patients into their correct clinical groups (e.g., healthy vs. cancer).

  • Pancreas Cancer: The Wasserstein-based methods achieved an ARI of 0.88, vastly outperforming baseline methods like PCA (-0.04) or undirected correlation (-0.03).
  • Heart Myocardial Infarction: The Wasserstein-based methods achieved an ARI of 0.45, while baselines struggled to exceed 0.31.
  • Baseline Failure: Standard undirected OT methods (like GWOT) were unable to distinguish the synthetic perturbations, whereas the new directed formulations captured them clearly.

Limitations and Future Work

  • Scalability: While OT is powerful, it can be computationally expensive for very large graphs. The authors mention the need to improve the robustness of the structural comparisons.
  • Explainability: While the "transport plan" is theoretically interpretable, the authors suggest that future work should focus on making these maps easier for biologists to read—for example, by highlighting exactly which cell-cell pairs contribute most to the difference between a healthy and a diseased state.
  • Synthetic Diversity: The study used a limited range of synthetic models; testing on a wider variety of directed graph topologies would further validate the approach.

Summary updated

BibTeX
@inproceedings{nagai2024optimal,
  author = {James Shiniti Nagai and Ivan G. Costa and Michael T. Schaub},
  title = {{Optimal Transport Distances for Directed, Weighted Graphs: A Case Study With Cell-Cell Communication Networks}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  doi = {10.1109/icassp48485.2024.10446503},
}
Figure