Metric spaces of walks and Lipschitz duality on graphs
This work addresses the challenge of quantifying walk distances in graphs for applications like reinforcement learning, but it appears incremental as it builds on existing metric space and Lipschitz duality concepts without claiming major breakthroughs.
The paper tackles the problem of measuring distances between walks on graphs by introducing a weighted metric for sequences, enabling stepwise vertex distance calculations and weighted norms. It provides representation formulas for proximities and extends Lipschitz functions to subspaces of walks, with potential applications in reinforcement learning and Lipschitz regression on networks.
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.