Dey, Tamal K. ;
Shi, Dayu ;
Wang, Yusu
Comparing Graphs via Persistence Distortion
Abstract
Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graphlike, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the nonlinear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistencedistortion 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 persistencedistortion 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 persistencedistortion 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 persistencedistortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster.
BibTeX  Entry
@InProceedings{dey_et_al:LIPIcs:2015:5128,
author = {Tamal K. Dey and Dayu Shi and Yusu Wang},
title = {{Comparing Graphs via Persistence Distortion}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {491506},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5128},
URN = {urn:nbn:de:0030drops51285},
doi = {10.4230/LIPIcs.SOCG.2015.491},
annote = {Keywords: Graph matching, metric graphs, persistence distortion, topological method}
}
2015
Keywords: 

Graph matching, metric graphs, persistence distortion, topological method 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

2015 