The graph optimal transport distance introduced by [1]} has shown to successfully capture the global structure of graphs, representing their topology through smooth signal distributions. The work has been extended by [2]} to accommodate for comparison of graphs of different sizes using a one-to-many framework, and by [3]} for graph sketching. However,
while smooth graph signals efficiently capture global graph properties, they can lack descriptiveness for other potentially interesting properties.
Several graph distances based on heat diffusion have been proposed. [4]} propose a direct comparison of graph heat diffusion matrices, but stay limited to graphs of the same size. A spectral method proposed by [5]} circumvents this problem by comparing heat kernel traces, but it still does not address the graph alignment problem. Closer to our work, a fast heat kernel distance based on optimal transport has recently been proposed by [6]}. The authors apply the Wasserstein distance between signals only after a graph filtering step, encoding the structural information of the graph into the filtered signals. However, this distance compares graphs through available signals, whereas our method uses the representation of graphs through signal distributions and therefore does not need to rely on actual signal availability.
Furthermore, the above methods are limited only to heat diffusion models, while more general distances could often be of interest in practice.
