# Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

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

- [Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison](https://mlsanity.com/paper/2108.10004/) (2021)
- [Dissecting graph measure performance for node clustering in LFR parameter space](https://mlsanity.com/paper/2202.09827/) (2022)

## Abstract (arXiv)

This work elaborates on the important problem of (1) designing optimal randomized routing policies for reaching a target node t from a source note s on a weighted directed graph G and (2) defining distance measures between nodes interpolating between the least cost (based on optimal movements) and the commute-cost (based on a random walk on G), depending on a temperature parameter T. To this end, the randomized shortest path formalism (RSP, [2,99,124]) is rephrased in terms of Tsallis divergence regularization, instead of Kullback-Leibler divergence. The main consequence of this change is that the resulting routing policy (local transition probabilities) becomes sparser when T decreases, therefore inducing a sparse random walk on G converging to the least-cost directed acyclic graph when T tends to 0. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results. The sparse RSP is therefore a promising model of movements on a graph, balancing sparse exploitation and exploration in an optimal way.