Spectral distances on graphs

Abstract

By assigning a probability measure via the spectrum of the normalized Laplacian to each graph and using L^p Wasserstein distances between probability measures, we define the corresponding spectral distances d_p on the set of all graphs. This approach can even be extended to measuring the distances between infinite graphs. We prove that the diameter of the set of graphs, as a pseudo-metric space equipped with d_1, is one. We further study the behavior of d_1 when the size of graphs tends to infinity by interlacing inequalities aiming at exploring large real networks. A monotonic relation between d_1 and the evolutionary distance of biological networks is observed in simulations.

25 pages, 12 figures

References in corpus (3)

• Multi-way dual Cheeger constants and spectral bounds of graphs
• Spectral classes of regular, random, and empirical graphs
• Laplacian Spectrum and Protein-Protein Interaction Networks

Cited by in corpus (8)

• GOT: An Optimal Transport framework for Graph comparison
• Few-Shot Learning on Graphs via Super-Classes based on Graph Spectral Measures
• Fractality and degree correlations in scale-free networks
• A graph complexity measure based on the spectral analysis of the Laplace operator
• Novel diffusion-derived distance measures for graphs
• ${\ell }^1$-Cospectrality of graphs
• Spectral classes of hypergraphs
• Graph Coarsening with Preserved Spectral Properties