Novel diffusion-derived distance measures for graphs
  We define a new family of similarity and distance measures on graphs, and
explore their theoretical properties in comparison to conventional distance
metrics. These measures are defined by the solution(s) to an optimization
problem which attempts find a map minimizing the discrepancy between two graph
Laplacian exponential matrices, under norm-preserving and sparsity constraints.
Variants of the distance metric are introduced to consider such optimized maps
under sparsity constraints as well as fixed time-scaling between the two
Laplacians. The objective function of this optimization is multimodal and has
discontinuous slope, and is hence difficult for univariate optimizers to solve.
We demonstrate a novel procedure for efficiently calculating these optima for
two of our distance measure variants. We present numerical experiments
demonstrating that (a) upper bounds of our distance metrics can be used to
distinguish between lineages of related graphs; (b) our procedure is faster at
finding the required optima, by as much as a factor of 10^3; and (c) the upper
bounds satisfy the triangle inequality exactly under some assumptions and
approximately under others. We also derive an upper bound for the distance
between two graph products, in terms of the distance between the two pairs of
factors. Additionally, we present several possible applications, including the
construction of infinite "graph limits" by means of Cauchy sequences of graphs
related to one another by our distance measure.
