# Embedding networks with the random walk first return time distribution

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 70 references that are in the map.
- First posted on arXiv 2 Dec 2025.

## Builds on (most cited first, 15 of 15)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [RetGK: Graph Kernels based on Return Probabilities of Random Walks](https://mlsanity.com/paper/1809.02670/) (2018)
- [Contact patterns among high school students](https://mlsanity.com/paper/1409.5318/) (2014)
- [Role Discovery in Networks](https://mlsanity.com/paper/1405.7134/) (2014)
- [Multiscale dynamical embeddings of complex networks](https://mlsanity.com/paper/1804.03733/) (2018)
- [Social Networking by Proxy: A Case Study of Catster, Dogster and Hamsterster](https://mlsanity.com/paper/1501.04527/) (2015)
- [An approximation for return time distributions of random walks on sparse networks](https://mlsanity.com/paper/2405.20166/) (2024)

## Abstract (arXiv)

We propose the first return time distribution (FRTD) of a random walk as an interpretable and mathematically grounded node embedding. The FRTD assigns a probability mass function to each node, allowing us to define a distance between any pair of nodes using standard metrics for discrete distributions. We present several arguments to motivate the FRTD embedding. First, we show that FRTDs are strictly more informative than eigenvalue spectra, yet insufficient for complete graph identification, thus placing FRTD equivalence between cospectrality and isomorphism. Second, we argue that FRTD equivalence between nodes captures structural similarity. Third, we empirically demonstrate that the FRTD embedding outperforms manually designed graph metrics in network alignment tasks. Finally, we show that random networks that approximately match the FRTD of a desired target also preserve other salient features. Together these results demonstrate the FRTD as a simple and mathematically principled embedding for complex networks.