2026-07-23T13:07:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5128 2024-03-06T10:35:54Z ddc:004 open_access

Comparing Graphs via Persistence Distortion Dey, Tamal K. Shi, Dayu Wang, Yusu Graph matching metric graphs persistence distortion topological method Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graph-like, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistence-distortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistence-distortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistence-distortion distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistence-distortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamal K. Dey and Dayu Shi and Yusu Wang 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.491 urn:nbn:de:0030-drops-51285 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.491 eng https://creativecommons.org/licenses/by/3.0/legalcode