  Metric graphs are ubiquitous in science and engineering. For example, many
data are drawn from hidden spaces that are graph-like, such as the cosmic web.
A metric graph offers one of the simplest yet still meaningful ways to
represent the non-linear structure hidden behind the data. In this paper, we
propose a new distance between two finite metric graphs, called the
persistence-distortion distance, which draws upon a topological idea. This
topological perspective along with the metric space viewpoint provide a new
angle to the graph matching problem. Our persistence-distortion distance has
two properties not shared by previous methods: First, it is stable against the
perturbations of the input graph metrics. Second, it is a continuous distance
measure, in the sense that it is defined on an alignment of the underlying
spaces of input graphs, instead of merely their nodes. This makes our
persistence-distortion distance robust against, for example, different
discretizations of the same underlying graph. Despite considering the input
graphs as continuous spaces, that is, taking all points into account, we show
that we can compute the persistence-distortion distance in polynomial time. The
time complexity for the discrete case where only graph nodes are considered is
much faster. We also provide some preliminary experimental results to
demonstrate the use of the new distance measure.
