# Metric spaces of walks and Lipschitz duality on graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 27 Aug 2025.

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

- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2010.05313/) (2020)
- [Chemi-net: a graph convolutional network for accurate drug property prediction](https://mlsanity.com/paper/1803.06236/) (2018)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [Accounting for the Role of Long Walks on Networks via a New Matrix Function](https://mlsanity.com/paper/1607.06807/) (2016)
- [Graph distances for determining entities relationships: a topological approach to fraud detection](https://mlsanity.com/paper/1905.08040/) (2019)
- [Dynamic Metric Embedding into ℓp Space](https://mlsanity.com/paper/2406.17210/) (2024)

## Abstract (arXiv)

We study the metric structure of walks on graphs, understood as Lipschitz sequences. To this end, a weighted metric is introduced to handle sequences, enabling the definition of distances between walks based on stepwise vertex distances and weighted norms. We analyze the main properties of these metric spaces, which provides the foundation for the analysis of weaker forms of instruments to measure relative distances between walks: proximities. We provide some representation formulas for such proximities under different assumptions and provide explicit constructions for these cases. The resulting metric framework allows the use of classical tools from metric modeling, such as the extension of Lipschitz functions from subspaces of walks, which permits extending proximity functions while preserving fundamental properties via the mentioned representations. Potential applications include the estimation of proximities and the development of reinforcement learning strategies based on exploratory walks, offering a robust approach to Lipschitz regression on network structures.