Efficient estimation of a Gromov--Hausdorff distance between unweighted graphs

arXiv1909.09772MaRDI QIDQ6325720FDOQ6325720

Nathan Lemons, Alexander Panchenko, Vladyslav Oles

Publication date: 21 September 2019

Abstract: 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 cite{memoli12} (M'emoli, F, extit{Discrete & Computational Geometry, 48}(2) 416-440, 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.

This page was built for publication: Efficient estimation of a Gromov--Hausdorff distance between unweighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325720)