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

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

Introduction

In many scientific domains, from social network analysis to systems biology, data is most naturally represented as a directed graph, where connections possess a specific "from-to" orientation. While methodologies for comparing undirected graphs are well-established, comparing directed ones remains a significant challenge. Most existing tools either ignore edge directionality entirely or rely on local "graph features"—such as counting specific motifs like triangles—which fail to capture the global structure or the "flow" of the network.

Optimal Transport (OT) has recently emerged as a powerful framework for graph comparison. Unlike simple distance metrics, OT provides a "transport plan" that illustrates how one graph can be transformed into another. However, standard OT formulations typically require a symmetric distance between nodes (e.g., shortest path), which does not naturally exist in directed graphs. This paper addresses this gap by adapting OT for directed, weighted networks, specifically targeting the noisy and sparse data environments common in single-cell biology.

Methodology

The authors propose a two-step framework: first, defining internal node-to-node distances that respect directionality, and second, utilizing these distances to compare distinct graphs.

Node-to-Node Distances for Directed Graphs

To capture the directed nature of the networks, the authors introduce two primary metrics:

  • Generalized Effective Resistance (GRD): This metric treats the graph as an electrical circuit. While standard resistance applies to undirected wires, GRD utilizes a "grounded" Laplacian and Lyapunov equations to account for directed flow, providing a measure of connectivity that respects orientation.
  • Hitting Time Distance (HTD): Grounded in Markov chain theory, HTD measures the expected number of steps a random walker takes to travel from node A to node B. This inherently asymmetric measure captures the reachability and flow within the network.

Graph-to-Graph Comparison Frameworks

With node distances defined, the authors employ two OT-based methods for graph comparison:

  • Gromov-Wasserstein (GW): This method compares the internal "geometries" of two graphs by seeking a mapping that preserves relative distances between nodes as much as possible.
  • Wasserstein via Linegraphs: In a novel approach, the authors convert the original graph into a "linegraph," where the edges of the original graph become the nodes of the new one. By treating edge weights as a probability distribution, they can apply standard Wasserstein distance (Earth Mover's Distance) to compare the networks.
Figure 1: Synthetic graph tests demonstrating that proposed directed metrics distinguish between local and global edge swaps, whereas undirected baselines like GOT fail to differentiate them from the reference.

Experimental Results

The proposed frameworks were rigorously tested on both synthetic models and real-world biological datasets to validate their effectiveness.

Synthetic "Cycle of Cycles" Analysis

The authors designed a "cycle of cycles" model—consisting of four local cycles connected in a larger global cycle—to test sensitivity to structural perturbations. As shown in Figure 1, undirected metrics like standard Graph Optimal Transport (GOT) assigned a distance of zero to graphs that were structurally different but identical if arrow directions were ignored. In contrast, the proposed directed metrics successfully distinguished these perturbations. Notably, they found that flipping a "global" edge (one connecting major clusters) resulted in a significantly larger distance than flipping a "local" edge, indicating that these metrics effectively capture the "flow circulation" of the network.

Real-World Biological Case Studies

The methods were applied to cell-cell communication networks inferred from single-cell RNA-seq data across two clinical datasets: Pancreas Cancer (n=35) and Heart Myocardial Infarction (n=20). Clustering performance was evaluated using the Adjusted Rand Index (ARI), which measures how accurately a k-means algorithm can group patients based on their graph distances.

Table 1: Clustering performance (ARI) on biological datasets. Proposed Wasserstein-based methods significantly outperform PCA and correlation baselines.

As detailed in Table 1, the Wasserstein-based methods achieved an ARI of 0.88 for Pancreas Cancer and 0.45 for Heart Myocardial Infarction. These results vastly outperform baseline methods such as PCA (ARI ≈ -0.04) or undirected correlation (ARI ≈ -0.03 to 0.31). A key insight was that the linegraph-based Wasserstein approach was more robust to the "dropouts" and noise inherent in single-cell sequencing compared to the Gromov-Wasserstein formulation.

Conclusion and Future Work

This study demonstrates that directionality is a critical feature of complex networks. By integrating directed node distances into an Optimal Transport framework, the authors provide a robust and sensitive tool for comparing weighted, directed graphs.

While powerful, the authors acknowledge limitations regarding computational scalability for very large graphs. Future work will focus on optimizing these algorithms and enhancing the explainability of the resulting "transport plans." Making these maps more interpretable for biologists—for instance, by highlighting specific cell-cell pairs that drive the differences between healthy and diseased states—will be crucial for translating these mathematical frameworks into clinical insights.

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