Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
(2020) , 41 pages
Files
2020-07_PierreLeleuxetSylvainCourtain_conf.pdf
Closed Access - Adobe PDF
- 602.43 KB
Details
- Authors
Courtain, Sylvain 
- Abstract
- 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 (RSP) formalism 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.
- Affiliations
Citations
Leleux, P., Courtain, S., Guex, G., & Saerens, M. (2020). Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization (Louvain Research Institute in Management and Organizations Working Paper Series 2020/07). https://hdl.handle.net/2078.5/167503