Abstract: Comparing metric graphs is a fundamental challenge in data analysis, often hindered by the computational complexity of the Gromov-Hausdorff (GH) distance. This paper introduces the persistence-distortion distance ($d_{PD}$), a novel metric that blends topological persistence with metric geometry. By representing graphs as collections of persistence diagrams derived from shortest-path distance functions, the authors provide a stable, continuous distance measure that is computable in polynomial time.
The Challenge of Graph Comparison
Comparing graphs is essential across various domains, from computer vision to biology. Traditional graph matching often relies on discrete alignments of nodes. However, this approach fails when graphs represent the same underlying structure but are discretized differently—for instance, if one graph contains an additional node along an edge.
The "gold standard" for comparing metric graphs (where edges have defined lengths) is the Gromov-Hausdorff distance. While theoretically robust, GH distance is NP-hard to compute or even approximate within a constant factor. Researchers have long sought a "weaker" version of this distance that remains physically meaningful and stable while being computationally feasible.
Methodology: Bridging Topology and Geometry
The authors propose a new framework using Persistent Homology to create a topological "fingerprint" of a graph. The process follows a specific sequence:
- Basepoint Functions: For every point $s$ in a graph $G$, a function is defined based on the shortest-path distance from $s$ to all other points in the graph.
- Persistence Diagrams: Using 0-th dimensional persistent homology, the method tracks how connected components appear and merge as distance values increase. This results in a persistence diagram—a 2D plot representing the graph's topology from the perspective of point $s$.
- The Distance Metric: A graph is represented as an infinite set of these diagrams (one for every point on every edge). The persistence-distortion distance ($d_{PD}$) is defined as the Hausdorff distance between these two sets of diagrams, utilizing the "bottleneck distance" to compare individual diagrams.
To move from a continuous to a discrete, computable model, the authors analyzed how these diagrams evolve as the basepoint $s$ moves along an edge. They demonstrated that the trajectories of points in the diagrams (called "vines") are piecewise linear, allowing the identification of a finite number of "critical events" where the topology changes.
Key Insights and Stability
- Continuity and Discretization: By considering every point on every edge, the distance becomes insensitive to specific node placements. Two versions of the same graph with different discretizations will have a distance of zero.
- Theoretical Stability: The authors prove that $d_{PD}(G_1, G_2) \leq 6 d_{GH}(G_1, G_2)$. This ensures that if two graphs are close in the ideal GH sense, they remain close in the $d_{PD}$ metric, providing robustness against noise.
- Polynomial Feasibility: Despite comparing infinite sets of points, the underlying geometry of shortest paths allows the problem to be solved exactly in polynomial time. The continuous distance can be computed in $O(m^{12} \log m)$ time, while a discrete version (using only nodes as basepoints) is significantly faster at $O(n^2 m^{1.5} \log m)$.
Experimental Results
The method was validated using two primary datasets:
- Road Networks: Testing against the road map of Athens demonstrated the measure's stability when comparing original graphs to noisy samples.
- 3D Surface Meshes: Using the 1-skeleton of 16 models (including humans, horses, and wolves), the distance successfully clustered similar objects. It proved capable of distinguishing between different classes of objects while remaining invariant to different poses of the same object, capturing intrinsic shape rather than simple coordinate alignment.
Conclusion and Future Work
The persistence-distortion distance represents a significant advancement in graph comparison, offering the first polynomial-time result for continuous metric graph comparison. While the $m^{12}$ complexity remains a theoretical benchmark rather than a practical one for massive graphs, the discrete version offers immediate utility. Future work may involve incorporating 1st-dimensional persistence (loops and cycles) to increase discriminative power, potentially at the cost of higher computational complexity.
Summary updated