Comparing Graphs via Persistence Distortion

DOI10.4230/LIPICS.SOCG.2015.491MaRDI QIDQ5368708zbMATH OpenOpenAlexFDO

Authors Dayu Shi, Yusu Wang, Tamal K. Dey

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1503.07414

zbMATH Keywords

graph matchingmetric graphspersistence distortiontopological method

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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. We also provide some preliminary experimental results to demonstrate the use of the new distance measure.

Recommendations

• Comparison of persistence diagrams
• A new dissimilarity measure for comparing labeled graphs
• Comparing eccentricity-based graph invariants
• Comparative study of distance-based graph invariants
• Graph similarity and distance in graphs
• A descriptive tolerance nearness measure for performing graph comparison
• Reconstructing embedded graphs from persistence diagrams

Cited in

(10)

• Local versus global distances for zigzag and multi-parameter persistence modules
• Decorated merge trees for persistent topology
• The fiber of persistent homology for simplicial complexes
• New families of stable simplicial filtration functors
• Comparing dynamical systems by a graph matching method
• Distances between immersed graphs: metric properties
• GERoMe -- a novel graph extraction robustness measure
• Inverse problems in topological persistence
• The relationship between the intrinsic Čech and persistence distortion distances for metric graphs
• Distance measures for geometric graphs

This page was built for publication: Comparing Graphs via Persistence Distortion

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