A linear-time algorithm and analysis of graph Relative Hausdorff distance

Graph similarity metrics serve far-ranging purposes across many domains in data science. As graph datasets grow in size, scientists need comparative tools that capture meaningful differences, yet are lightweight and scalable. Graph Relative Hausdorff (RH) distance is a promising, recently proposed measure for quantifying degree distribution similarity. In spite of recent interest in RH distance, little is known about its properties. Here, we conduct an algorithmic and analytic study of RH distance. In particular, we provide the first linear-time algorithm for computing RH distance, analyze examples of RH distance between pairs of real-world networks as well as structured families of graphs, and prove several analytic results concerning the range, density, and extremal behavior of RH distance values.