Randomized Optimal Transport on a Graph: Framework and New Distance Measures

This problem is faced in many applications such as link prediction, community detection, node classification, and network visualization, among others. Now, it has been shown that the standard shortest path distance and the resistance distance (Klein & Randić, 1993) suffer from important drawbacks in some situations, which sometimes hinders their use as distance measures between nodes in some applications. More precisely, the shortest path distance does not integrate the concept of high connectivity between the two nodes (it only considers the shortest paths, see, e.g., (Fouss et al., 2016)), while the resistance distance provides useless results when dealing with large graphs (the so-called "lost-in-space effect" (von Luxburg, Radl, & Hein, 2010, 2014)). Another drawback of the shortest path distance is that it provides lots of ties when comparing distances, especially on unweighted undirected graphs. In order to avoid the drawbacks of the shortest path and resistance distances, new families of distance measures, interpolating between these two extremes, were recently suggested based on a bag-of-paths (BoP) framework (Françoisse et al., 2017; Kivimäki, Shimbo, & Saerens, 2014; Mantrach et al., 2010). This framework defines a Gibbs-Boltzmann probability distribution over paths on a graph, which focuses on the shortest paths, but spreads also on longer paths and random walks.