# Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs

arXiv: https://arxiv.org/abs/1909.09772 · HTML: https://mlsanity.com/paper/1909.09772/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)

## Abstract (arXiv)

Gromov-Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov-Hausdorff distance is equivalent to solving an NP-Hard optimization problem, deeming the notion impractical for applications. In this paper we propose polynomial algorithm for estimating the so-called modified Gromov-Hausdorff (mGH) distance, whose topological equivalence with the standard Gromov-Hausdorff (GH) distance was established in M'emoli F, 2012. We implement the algorithm for the case of compact metric spaces induced by unweighted graphs as part of Python library verb|scikit-tda|, and demonstrate its performance on real-world and synthetic networks. The algorithm finds the mGH distances exactly on most graphs with the scale-free property. We use the computed mGH distances to successfully detect outliers in real-world social and computer networks.