# A metric on directed graphs and Markov chains based on hitting probabilities

arXiv: https://arxiv.org/abs/2006.14482 · HTML: https://mlsanity.com/paper/2006.14482/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2020.

## Built on by (most cited first, 3 of 3)

- [A Probabilistic Generative Model of Free Categories](https://mlsanity.com/paper/2205.04545/) (2022)
- [Optimal transport distances for directed, weighted graphs: a case study with cell-cell communication networks](https://mlsanity.com/paper/2309.07030/) (2023)
- [Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits](https://mlsanity.com/paper/2602.03970/) (2026)

## Abstract (arXiv)

The shortest-path, commute time, and diffusion distances on undirected graphs have been widely employed in applications such as dimensionality reduction, link prediction, and trip planning. Increasingly, there is interest in using asymmetric structure of data derived from Markov chains and directed graphs, but few metrics are specifically adapted to this task. We introduce a metric on the state space of any ergodic, finite-state, time-homogeneous Markov chain and, in particular, on any Markov chain derived from a directed graph. Our construction is based on hitting probabilities, with nearness in the metric space related to the transfer of random walkers from one node to another at stationarity. Notably, our metric is insensitive to shortest and average walk distances, thus giving new information compared to existing metrics. We use possible degeneracies in the metric to develop an interesting structural theory of directed graphs and explore a related quotienting procedure. Our metric can be computed in O(n3) time, where n is the number of states, and in examples we scale up to n=10,000 nodes and ≈ 38M edges on a desktop computer. In several examples, we explore the nature of the metric, compare it to alternative methods, and demonstrate its utility for weak recovery of community structure in dense graphs, visualization, structure recovering, dynamics exploration, and multiscale cluster detection.