A bag-of-paths graph framework with Poisson-distributed path lengths

Abstract

This paper investigates a theoretical extension of the entropyregularized least-cost problem on a graph from a bag-of-paths perspective. This extension constrains the a priori probability distribution on the length of the paths in order to follow a Poisson distribution. Therefore, this framework allows us to weigh the global impact of path lengths, depending on the structure of the graph, which proves useful in node classification and clustering problems. Accordingly, a novel distance measure between nodes of the graph can be defined from the probability of drawing an i-j path derived from the new bag-ofpaths model. Experiments on supervised classification problems show that the proposed distance is competitive with other state-of-the-art
distances and kernels on a graph.